關(guān)聯(lián)規(guī)則挖掘是一種基于規(guī)則的機(jī)器學(xué)習(xí)算法，該算法可以在大數(shù)據(jù)庫(kù)中發(fā)現(xiàn)感興趣的關(guān)系。它的目的是利用一些度量指標(biāo)來(lái)分辨數(shù)據(jù)庫(kù)中存在的強(qiáng)規(guī)則。也即是說(shuō)關(guān)聯(lián)規(guī)則挖掘是用于知識(shí)發(fā)現(xiàn)，而非預(yù)測(cè)，所以是屬于無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法。
“尿布與啤酒”是一個(gè)典型的關(guān)聯(lián)規(guī)則挖掘的例子，沃爾瑪為了能夠準(zhǔn)確了解顧客在其門(mén)店的購(gòu)買(mǎi)習(xí)慣，對(duì)其顧客的購(gòu)物行為進(jìn)行購(gòu)物籃分析，想知道顧客經(jīng)常一起購(gòu)買(mǎi)的商品有哪些。沃爾瑪利用所有用戶(hù)的歷史購(gòu)物信息來(lái)進(jìn)行挖掘分析，一個(gè)意外的發(fā)現(xiàn)是："跟尿布一起購(gòu)買(mǎi)最多的商品竟是啤酒！
關(guān)聯(lián)規(guī)則挖掘算法不僅被應(yīng)用于購(gòu)物籃分析，還被廣泛的應(yīng)用于網(wǎng)頁(yè)瀏覽偏好挖掘，入侵檢測(cè)，連續(xù)生產(chǎn)和生物信息學(xué)領(lǐng)域。
與序列挖掘算法不同的是，傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘算法通常不考慮事務(wù)內(nèi)或者事件之間的順序。
支持度和置信度
那么我們?nèi)绾文軌驈乃锌赡芤?guī)則的集合中選擇感興趣的規(guī)則呢？需要利用一些度量方法來(lái)篩選和過(guò)濾，比較有名的度量方法是最小支持度（minimum support）和最小置信度（minimum confidence）。
假定我們一個(gè)數(shù)據(jù)庫(kù)包含5條事務(wù)，每行表示一個(gè)購(gòu)物記錄，1 表示購(gòu)買(mǎi)，0 表示沒(méi)有購(gòu)買(mǎi)，如下圖表格所示：
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 各表示為一個(gè) item-set, X ? Y 表示為一條規(guī)則（尿布 ? 啤酒 就是一條規(guī)則），用 T 表示為事務(wù)數(shù)據(jù)庫(kù)（并不是說(shuō)只局限于事務(wù)數(shù)據(jù)庫(kù)）。
支持度（Support）
支持度表示 item-set 在整個(gè) T 中出現(xiàn)的頻率。假定 T 中含有 N 條數(shù)據(jù)，那么支持度的計(jì)算公式為：
譬如在上面的示例數(shù)據(jù)庫(kù)中，{beer, diaper} 的支持度為 1/5 = 0.2。5 條事務(wù)中只有一條事務(wù)同事包含 beer和 diaper ，實(shí)際使用中我們會(huì)設(shè)置一個(gè)最低的支持度（minimum support），那些大于或等于最低支持度的 X 稱(chēng)之為頻繁的 item-set 。
置信度（Confidence）
置信度表示為規(guī)則 X ? Y 在整個(gè) T 中出現(xiàn)的頻率。而置信度的值表示的意思是在包含了 X 的條件下，還含有 Y 的事務(wù)占總事務(wù)的比例。同樣假定 T 中含有 N 條數(shù)據(jù)，那么置信度的計(jì)算公式為：
譬如再上面的示例數(shù)據(jù)庫(kù)中，{beer, diaper} 的置信度為 0.2/0.2 = 1。表面在所有包含 beer 的事務(wù)中都會(huì)一定包含 diaper。同樣的，在實(shí)際使用中我們會(huì)設(shè)置一個(gè)最低置信度，那些大于或等于最小置信度的規(guī)則我們稱(chēng)之為是有意義的規(guī)則。
相關(guān)性度量
有時(shí)候使用支持度和置信度挖掘到的規(guī)則可能是無(wú)效的。
舉個(gè)例子：
10000 個(gè)事務(wù)中, 6000 個(gè)事務(wù)包含計(jì)算機(jī)游戲, 7500 個(gè)包含游戲機(jī)游戲, 4000 個(gè)事務(wù)同時(shí)包含兩者。關(guān)聯(lián)規(guī)則（計(jì)算機(jī)游戲 ? 游戲機(jī)游戲） 支持度為 0.4 ，看似很高，但其實(shí)這個(gè)關(guān)聯(lián)規(guī)則是一個(gè)誤導(dǎo)。在用戶(hù)購(gòu)買(mǎi)了計(jì)算機(jī)游戲后有 (4000÷6000) = 0.667 的概率的去購(gòu)買(mǎi)游戲機(jī)游戲，而在沒(méi)有任何前提條件時(shí)，用戶(hù)反而有 (7500÷10000) = 0.75的概率去購(gòu)買(mǎi)游戲機(jī)游戲，也就是說(shuō)設(shè)置了購(gòu)買(mǎi)計(jì)算機(jī)游戲這樣的前置條件反而會(huì)降低用戶(hù)去購(gòu)買(mǎi)游戲機(jī)游戲的概率，所以計(jì)算機(jī)游戲和游戲機(jī)游戲是相斥的，也即表明是獨(dú)立的。
因此我們可以通過(guò)下面的一些相關(guān)性度量方法來(lái)篩選挖掘到的規(guī)則。
提升度（Lift）
提升度可以用來(lái)判斷規(guī)則 X ? Y 中的 X 和 Y 是否獨(dú)立，如果獨(dú)立，那么這個(gè)規(guī)則是無(wú)效的。
計(jì)算提升度的公式如下：
如果該值等于 1 ,說(shuō)明兩個(gè)條件沒(méi)有任何關(guān)聯(lián)。如果小于 1 ,說(shuō)明 X 與 Y 是負(fù)相關(guān)的關(guān)系，意味著一個(gè)出現(xiàn)可能導(dǎo)致另外一個(gè)不出現(xiàn)。大于 1 才表示具有正相關(guān)的關(guān)系。一般在數(shù)據(jù)挖掘中當(dāng)提升度大于 3 時(shí),我們才承認(rèn)挖掘出的關(guān)聯(lián)規(guī)則是有價(jià)值的。
他可以用來(lái)評(píng)估一個(gè)出現(xiàn)提升另外一個(gè)出現(xiàn)的程度。
提升度是一種比較簡(jiǎn)單的判斷手法，實(shí)際中受零事務(wù)（也即不包含 X 也不包含 Y 的事務(wù)）的影響比較大。所以如果數(shù)據(jù)中含有的零事務(wù)數(shù)量較大，該度量則不合適使用。
全置信度 和 最大置信度
給定兩個(gè)項(xiàng)集 X 和 Y ，其全置信度為
不難知道，最大置信度為
全置信度和最大置信度的取值都是從 0 ~ 1 ，值越大，聯(lián)系越大。
該度量是不受零事務(wù)影響的。
KULC 度量 + 不平衡比（IR）
給定兩個(gè)項(xiàng)集 X 和 Y，其 Kulczynski(Kulc) 度量定義為：
可以看做是兩個(gè)置信度的平均值，同樣取值也是從 0 ~ 1，值越大，聯(lián)系越大，關(guān)系越大。
該度量同樣也是不受零事務(wù)影響的。
Apriori 算法
在執(zhí)行算法之前，用戶(hù)需要先給定最小的支持度和最小的置信度。
生成關(guān)聯(lián)規(guī)則一般被劃分為如下兩個(gè)步驟：
1、利用最小支持度從數(shù)據(jù)庫(kù)中找到頻繁項(xiàng)集。
給定一個(gè)數(shù)據(jù)庫(kù) D ，尋找頻繁項(xiàng)集流程如下圖所示
C1 中 {1} 的支持度為 2/4 = 0.5 表示在 D 中的 4 條事務(wù)中，{1} 出現(xiàn)在其中的兩條事務(wù)中，以后幾個(gè)步驟的支持度計(jì)算方式也是類(lèi)似的。假定給定的最小支持度為 0.5，那么最后我們可以得到一個(gè)包含 3 個(gè)項(xiàng)的頻繁項(xiàng)集 {2 3 5}。
另外，從圖中我們可以看到 itemset 中所包含的 item 是從 1 增長(zhǎng)到 3 的。并且每次增長(zhǎng)都是利用上一個(gè) itemset 中滿(mǎn)足支持度的 item 來(lái)生成的，這個(gè)過(guò)程稱(chēng)之為候選集生成（candidate generation）。譬如說(shuō) C2 里就不包含 C1 中的 4 。
2、利用最小置信度從頻繁項(xiàng)集中找到關(guān)聯(lián)規(guī)則。
同樣假定最小的置信度為 0.5 ，從頻繁項(xiàng)集 {2 3 5} 中我們可以發(fā)現(xiàn)規(guī)則 {2 3} ? {5} 的置信度為 1 > 0.5 ，所以我們可以說(shuō) {2 3} ? {5} 是一個(gè)可能感興趣的規(guī)則。
從第一步中我們看出每次計(jì)算支持度都需要掃描數(shù)據(jù)庫(kù)，這會(huì)造成很大的 I/O 開(kāi)銷(xiāo)，所以有很多變種的算法都會(huì)在該問(wèn)題上進(jìn)行優(yōu)化（FP-Growth）。此外如何有效的生成候選集也是很多變種算法優(yōu)化的問(wèn)題之一(Apriori-all)。
總結(jié)
- 關(guān)聯(lián)規(guī)則是無(wú)監(jiān)督的學(xué)習(xí)算法，能夠很好的用于知識(shí)的發(fā)現(xiàn)。
- 缺點(diǎn)是很難嚴(yán)重算法的有效性，一般只能夠通過(guò)肉眼觀察結(jié)果是否合理。
>> 下一篇：加權(quán)關(guān)聯(lián)規(guī)則挖掘算法
