頻繁模式和關(guān)聯(lián)規(guī)則
頻繁模式是數(shù)據(jù)集中頻繁出現(xiàn)的項(xiàng)集串结、序列或子結(jié)構(gòu)蒿柳。例如，在購物籃分析中岳枷，會(huì)分析哪些商品頻繁的被客戶同時(shí)購買芒填；在網(wǎng)頁日志分析中，會(huì)分析用戶在瀏覽“手機(jī)”頁面后空繁，通常會(huì)繼續(xù)瀏覽哪些頁面殿衰。這些都是頻繁模式挖掘的典型例子。頻繁模式挖掘是關(guān)聯(lián)規(guī)則盛泡、相關(guān)分析闷祥、因果分析的基礎(chǔ)，對分類傲诵、聚類也有很大幫助凯砍。它在實(shí)際中的應(yīng)用非常廣泛，例如拴竹，購物籃分析悟衩、網(wǎng)頁日志分析、DNA序列分析等栓拜。因此座泳，頻繁模式挖掘是一項(xiàng)非常重要的數(shù)據(jù)挖掘任務(wù)。
頻繁項(xiàng)集基本概念
- 項(xiàng)集（itemset）：最基本的模式是項(xiàng)集幕与，它是指若干個(gè)項(xiàng)的集合挑势。例如，某用戶在一次購物過程中購買了啤酒纽门、咖啡和雞蛋薛耻，那么集合{“啤酒”, “咖啡”, “雞蛋”}是一個(gè)項(xiàng)集。包含k個(gè)項(xiàng)的項(xiàng)集稱為k項(xiàng)集（k-itemset）
- 數(shù)據(jù)集：典型的數(shù)據(jù)集是事物（Transaction）的集合赏陵，每一個(gè)事物是一個(gè)非空項(xiàng)集饼齿，并擁有一個(gè)標(biāo)識TID（表1）饲漾。用戶購物日志是一個(gè)典型例子，其中用戶的每一次購物行為是一個(gè)事物缕溉。數(shù)據(jù)集也可以表示為Data Matrix的形式（表2）考传。
| TID | Itemset |
|---|---|
| 1 | {Beer, Coffee, Milk} |
| 2 | {Beer, Milk} |
| 3 | {Beer, Coffee, Milk, Fish} |
| TID | Beer| Coffee | Milk | Fish |
| :-------- | :--------| :--------| :--------|
| 1 |1|1|1|0|
| 2 |1|0|1|0|
| 3 |1|1|1|1|
- 支持度計(jì)數(shù)/絕對支持度（support count）：數(shù)據(jù)集中包含項(xiàng)集X的事物數(shù)
- 相對支持度（support）：項(xiàng)集X的絕對支持度與數(shù)據(jù)集事物總數(shù)的比值
- 頻繁項(xiàng)集（frequent itemset）：項(xiàng)集X的支持度超過最小門限值min_sup時(shí)，稱X為頻繁項(xiàng)集
頻繁項(xiàng)集的壓縮表示
易知证鸥，一個(gè)頻繁項(xiàng)集的子集都是頻繁的僚楞。當(dāng)數(shù)據(jù)集很大時(shí)，通常會(huì)挖掘出大量的頻繁項(xiàng)集枉层，很難計(jì)算和存儲泉褐。所以，我們引入了閉頻繁項(xiàng)集（closed frequent itemset）和極大頻繁項(xiàng)集（maximal frequent itemset）來對數(shù)據(jù)集D的全部頻繁項(xiàng)集進(jìn)行壓縮表示鸟蜡。
- 閉頻繁項(xiàng)集（closed frequent itemset）：當(dāng)項(xiàng)集X是頻繁項(xiàng)集膜赃，且數(shù)據(jù)集D中不存在X的真超集Y，使得X和Y的支持度相等揉忘，則X是閉頻繁項(xiàng)集跳座。閉頻繁項(xiàng)集的表示是無損壓縮，不會(huì)丟失支持度的信息泣矛。通過閉頻繁項(xiàng)集可以反推出所有的頻繁項(xiàng)集以及相應(yīng)的支持度
- 極大頻繁項(xiàng)集（maximal frequent itemset）：當(dāng)項(xiàng)集X是頻繁項(xiàng)集疲眷，且數(shù)據(jù)集D中不存在X的真超集Y，使得Y是頻繁項(xiàng)集您朽，則X是極大頻繁項(xiàng)集狂丝。極大頻繁項(xiàng)集的表示是有損壓縮，失去了頻繁項(xiàng)集的支持度信息哗总，我們可以根據(jù)極大頻繁項(xiàng)集判斷任意項(xiàng)集是否是頻繁的美侦，但無法得到相應(yīng)的支持度
實(shí)際中，需要根據(jù)應(yīng)用的特點(diǎn)來選擇相應(yīng)的表示方法魂奥。這里的項(xiàng)集可以推廣到其他的模式（pattern）
關(guān)聯(lián)規(guī)則
由頻繁項(xiàng)集，我們引入關(guān)聯(lián)規(guī)則的概念易猫。關(guān)聯(lián)規(guī)則（association rules）是形如X→Y(s,c)的表達(dá)式耻煤，其中X
和Y均為項(xiàng)集，且X∩Y=?准颓。
s代表支持度（support）哈蝇，反映了規(guī)則的可用性。支持度一個(gè)事物包含X∪Y的概率
c代表置信度（confidence）攘已，反映了規(guī)則的確定性炮赦。置信度是一個(gè)事物在包含X的同時(shí)也包含Y的條件概率
同時(shí)滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強(qiáng)規(guī)則
一般而言，關(guān)聯(lián)規(guī)則的挖掘分為兩步：
- 找出所有頻繁項(xiàng)集样勃，即候選規(guī)則
- 對所有候選規(guī)則計(jì)算置信度吠勘，找出其中的強(qiáng)規(guī)則
頻繁項(xiàng)集挖掘算法
頻繁項(xiàng)集的挖掘算法基于Downward Closure性質(zhì)性芬。具體的說，如果一個(gè)項(xiàng)集X是頻繁的剧防，那么它的所有子集也是頻繁的植锉。反過來說，一個(gè)項(xiàng)集S是非頻繁的峭拘，那么它的所有超集也是非頻繁的俊庇。根據(jù)這個(gè)性質(zhì)，誕生了一系列經(jīng)典算法：
- Apriori ：(Agrawal & Srikant@VLDB’94)
- Eclat (Zaki, Parthasarathy, Ogihara, Li @KDD’97)
- FP-Growth (Han, Pei, Yin @SIGMOD’00)
