關(guān)聯(lián)規(guī)則挖掘是一種基于規(guī)則的機器學(xué)習(xí)算法，該算法可以在大數(shù)據(jù)庫中發(fā)現(xiàn)感興趣的關(guān)系然爆。它的目的是利用一些度量指標來分辨數(shù)據(jù)庫中存在的強規(guī)則绎秒。也即是說關(guān)聯(lián)規(guī)則挖掘是用于知識發(fā)現(xiàn)，而非預(yù)測呢灶，所以是屬于無監(jiān)督的機器學(xué)習(xí)方法吴超。
“尿布與啤酒”是一個典型的關(guān)聯(lián)規(guī)則挖掘的例子，沃爾瑪為了能夠準確了解顧客在其門店的購買習(xí)慣鸯乃，對其顧客的購物行為進行購物籃分析鲸阻，想知道顧客經(jīng)常一起購買的商品有哪些。沃爾瑪利用所有用戶的歷史購物信息來進行挖掘分析，一個意外的發(fā)現(xiàn)是："跟尿布一起購買最多的商品竟是啤酒鸟悴！
關(guān)聯(lián)規(guī)則挖掘算法不僅被應(yīng)用于購物籃分析陈辱，還被廣泛的應(yīng)用于網(wǎng)頁瀏覽偏好挖掘，入侵檢測细诸，連續(xù)生產(chǎn)和生物信息學(xué)領(lǐng)域沛贪。
與序列挖掘算法不同的是，傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法通常不考慮事務(wù)內(nèi)或者事件之間的順序震贵。
支持度和置信度
那么我們?nèi)绾文軌驈乃锌赡芤?guī)則的集合中選擇感興趣的規(guī)則呢利赋？需要利用一些度量方法來篩選和過濾，比較有名的度量方法是最小支持度（minimum support）和最小置信度（minimum confidence）屏歹。
假定我們一個數(shù)據(jù)庫包含5條事務(wù)隐砸，每行表示一個購物記錄，1 表示購買蝙眶，0 表示沒有購買季希，如下圖表格所示：
ID | milk | bread | butter | beer | diapers
----|------|------|------|----
1 | 1| 1 | 0 | 0 | 0
2| 0| 0| 1| 0| 0
3| 0| 0| 0| 1| 1
4| 1| 1| 1| 0| 0
5| 0| 1| 0| 0| 0
讓 X，Y 各表示為一個 item-set, X ? Y 表示為一條規(guī)則（尿布 ? 啤酒 就是一條規(guī)則）幽纷，用 T 表示為事務(wù)數(shù)據(jù)庫（并不是說只局限于事務(wù)數(shù)據(jù)庫）式塌。
支持度（Support）
支持度表示 item-set 在整個 T 中出現(xiàn)的頻率。假定 T 中含有 N 條數(shù)據(jù)友浸，那么支持度的計算公式為：
譬如在上面的示例數(shù)據(jù)庫中峰尝，{beer, diaper} 的支持度為 1/5 = 0.2。5 條事務(wù)中只有一條事務(wù)同事包含 beer和 diaper 收恢，實際使用中我們會設(shè)置一個最低的支持度（minimum support）武学，那些大于或等于最低支持度的 X 稱之為頻繁的 item-set 。
置信度（Confidence）
置信度表示為規(guī)則 X ? Y 在整個 T 中出現(xiàn)的頻率伦意。而置信度的值表示的意思是在包含了 X 的條件下火窒，還含有 Y 的事務(wù)占總事務(wù)的比例。同樣假定 T 中含有 N 條數(shù)據(jù)驮肉，那么置信度的計算公式為：
譬如再上面的示例數(shù)據(jù)庫中熏矿，{beer, diaper} 的置信度為 0.2/0.2 = 1。表面在所有包含 beer 的事務(wù)中都會一定包含 diaper离钝。同樣的票编，在實際使用中我們會設(shè)置一個最低置信度，那些大于或等于最小置信度的規(guī)則我們稱之為是有意義的規(guī)則卵渴。
相關(guān)性度量
有時候使用支持度和置信度挖掘到的規(guī)則可能是無效的慧域。
舉個例子：
10000 個事務(wù)中, 6000 個事務(wù)包含計算機游戲, 7500 個包含游戲機游戲, 4000 個事務(wù)同時包含兩者。關(guān)聯(lián)規(guī)則（計算機游戲 ? 游戲機游戲） 支持度為 0.4 浪读，看似很高吊趾，但其實這個關(guān)聯(lián)規(guī)則是一個誤導(dǎo)宛裕。在用戶購買了計算機游戲后有 (4000÷6000) = 0.667 的概率的去購買游戲機游戲，而在沒有任何前提條件時论泛，用戶反而有 (7500÷10000) = 0.75的概率去購買游戲機游戲，也就是說設(shè)置了購買計算機游戲這樣的前置條件反而會降低用戶去購買游戲機游戲的概率蛹屿，所以計算機游戲和游戲機游戲是相斥的屁奏，也即表明是獨立的。
因此我們可以通過下面的一些相關(guān)性度量方法來篩選挖掘到的規(guī)則错负。
提升度（Lift）
提升度可以用來判斷規(guī)則 X ? Y 中的 X 和 Y 是否獨立坟瓢，如果獨立，那么這個規(guī)則是無效的犹撒。
計算提升度的公式如下：
如果該值等于 1 ,說明兩個條件沒有任何關(guān)聯(lián)折联。如果小于 1 ,說明 X 與 Y 是負相關(guān)的關(guān)系，意味著一個出現(xiàn)可能導(dǎo)致另外一個不出現(xiàn)识颊。大于 1 才表示具有正相關(guān)的關(guān)系诚镰。一般在數(shù)據(jù)挖掘中當(dāng)提升度大于 3 時,我們才承認挖掘出的關(guān)聯(lián)規(guī)則是有價值的。
他可以用來評估一個出現(xiàn)提升另外一個出現(xiàn)的程度祥款。
提升度是一種比較簡單的判斷手法清笨，實際中受零事務(wù)（也即不包含 X 也不包含 Y 的事務(wù)）的影響比較大。所以如果數(shù)據(jù)中含有的零事務(wù)數(shù)量較大刃跛，該度量則不合適使用抠艾。
全置信度 和 最大置信度
給定兩個項集 X 和 Y ，其全置信度為
不難知道桨昙，最大置信度為
全置信度和最大置信度的取值都是從 0 ~ 1 检号，值越大，聯(lián)系越大蛙酪。
該度量是不受零事務(wù)影響的齐苛。
KULC 度量 + 不平衡比（IR）
給定兩個項集 X 和 Y，其 Kulczynski(Kulc) 度量定義為：
可以看做是兩個置信度的平均值滤否，同樣取值也是從 0 ~ 1脸狸，值越大，聯(lián)系越大藐俺，關(guān)系越大炊甲。
該度量同樣也是不受零事務(wù)影響的。
Apriori 算法
在執(zhí)行算法之前欲芹，用戶需要先給定最小的支持度和最小的置信度卿啡。
生成關(guān)聯(lián)規(guī)則一般被劃分為如下兩個步驟：
1、利用最小支持度從數(shù)據(jù)庫中找到頻繁項集菱父。
給定一個數(shù)據(jù)庫 D 颈娜，尋找頻繁項集流程如下圖所示
C1 中 {1} 的支持度為 2/4 = 0.5 表示在 D 中的 4 條事務(wù)中剑逃，{1} 出現(xiàn)在其中的兩條事務(wù)中，以后幾個步驟的支持度計算方式也是類似的官辽。假定給定的最小支持度為 0.5蛹磺，那么最后我們可以得到一個包含 3 個項的頻繁項集 {2 3 5}。
另外同仆，從圖中我們可以看到 itemset 中所包含的 item 是從 1 增長到 3 的萤捆。并且每次增長都是利用上一個 itemset 中滿足支持度的 item 來生成的，這個過程稱之為候選集生成（candidate generation）俗批。譬如說 C2 里就不包含 C1 中的 4 俗或。
2、利用最小置信度從頻繁項集中找到關(guān)聯(lián)規(guī)則岁忘。
同樣假定最小的置信度為 0.5 辛慰，從頻繁項集 {2 3 5} 中我們可以發(fā)現(xiàn)規(guī)則 {2 3} ? {5} 的置信度為 1 > 0.5 ，所以我們可以說 {2 3} ? {5} 是一個可能感興趣的規(guī)則干像。
從第一步中我們看出每次計算支持度都需要掃描數(shù)據(jù)庫帅腌，這會造成很大的 I/O 開銷，所以有很多變種的算法都會在該問題上進行優(yōu)化（FP-Growth）蝠筑。此外如何有效的生成候選集也是很多變種算法優(yōu)化的問題之一(Apriori-all)狞膘。
總結(jié)
- 關(guān)聯(lián)規(guī)則是無監(jiān)督的學(xué)習(xí)算法，能夠很好的用于知識的發(fā)現(xiàn)什乙。
- 缺點是很難嚴重算法的有效性挽封，一般只能夠通過肉眼觀察結(jié)果是否合理。
>> 下一篇：加權(quán)關(guān)聯(lián)規(guī)則挖掘算法
