簡介
????關(guān)于頻繁模式挖掘的一個(gè)經(jīng)典例子應(yīng)該就是"啤酒和尿布"了，雖然看到很多人都說這個(gè)是編造的，但是也不妨礙用它來說明頻繁模式挖掘到底是干什么的。簡單來說，頻繁模式就是當(dāng)出現(xiàn)物品A時(shí)也經(jīng)常出現(xiàn)物品B，比如在分析超市的購物清單時(shí)，發(fā)現(xiàn)買啤酒的人經(jīng)常也買尿布。
基本概念
事務(wù)：它由一組物品組成，可看作一個(gè)訂單中的物品集合。
支持度：某幾個(gè)物品一起出現(xiàn)在事物中的次數(shù)或在數(shù)據(jù)庫中所占的比例
置信度：在出現(xiàn)A時(shí)出現(xiàn)B的概率，就是P(B|A) = P(A B) / P(A)
Apriori
????Apriori類的方法基于的基本思想是頻繁k+1項(xiàng)集是由頻繁k項(xiàng)集構(gòu)成，那么就可以通過一遍一遍地掃描數(shù)據(jù)集來發(fā)現(xiàn)頻繁模式，首先找到頻繁１項(xiàng)集，再掃描數(shù)據(jù)庫由頻繁１項(xiàng)集找到頻繁２項(xiàng)集，等等。
FP-growth
????FP-growth是一種新的方法，它只需要掃描兩次數(shù)據(jù)集。FP-growth包含兩部分內(nèi)容，首先需要構(gòu)造FP-tree，它高度壓縮了數(shù)據(jù)庫中的信息。然后在FP-tree上挖掘出頻繁模式。
構(gòu)造FP-tree
????FP-tree的基本思想是通過共享事務(wù)的前綴來壓縮數(shù)據(jù)庫，樹中的每個(gè)節(jié)點(diǎn)包含４部分信息：物品的標(biāo)識、節(jié)點(diǎn)的計(jì)數(shù)(表示從根節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)的路徑出現(xiàn)的次數(shù))、指向孩子的鏈接以及指向父節(jié)點(diǎn)的鏈接。
????構(gòu)造FP-tree只需遍歷兩次數(shù)據(jù)庫，首先掃描一次數(shù)據(jù)庫，統(tǒng)計(jì)出每個(gè)物品出現(xiàn)的次數(shù)，過濾掉支持度不夠的物品，也就是尋找頻繁一項(xiàng)集。得到頻繁一項(xiàng)集后將它們按出現(xiàn)次數(shù)從大到小排序，然后創(chuàng)建一個(gè)對應(yīng)的鏈表，鏈表中的每個(gè)節(jié)點(diǎn)都是一個(gè)指向鏈表的表頭，這個(gè)鏈表中的節(jié)點(diǎn)是那個(gè)對應(yīng)物品在樹種出現(xiàn)的所有結(jié)點(diǎn)。然后再一次地掃描數(shù)據(jù)庫，對于其中的每個(gè)事務(wù)(item1,item2,item3...)，將其按物品出現(xiàn)的次數(shù)排序。此時(shí)，需從樹的根節(jié)點(diǎn)開始添加這個(gè)排好序的事務(wù)，對于事務(wù)中的每個(gè)物品，如果這個(gè)物品出現(xiàn)在樹中當(dāng)前路徑之下，則將那個(gè)節(jié)點(diǎn)的計(jì)數(shù)+1；否則在當(dāng)前路徑之下添加一個(gè)新的節(jié)點(diǎn)，設(shè)置計(jì)數(shù)為1，并將這個(gè)新的節(jié)點(diǎn)加入到節(jié)點(diǎn)鏈表中相應(yīng)的鏈表尾部。
比如當(dāng)數(shù)據(jù)庫如下圖所示:
第一次掃描計(jì)數(shù)結(jié)果為：(a:3),(b:3),(c:4),(d:1),(e:1),(f:4),(g:1),(h:1),(i:1),(j:1),(k:1),(l:2),(m:3),(n:1),(o:2),(p:3)。按最小支持度為３過濾并排序后的結(jié)果為：
(f:4),(c:4),(a:3),(b:3),(m:3),(p:3)。第二次掃描數(shù)據(jù)庫時(shí)，對于事務(wù)100，排好序后為(f,c,a,m,p)，此時(shí)樹只有根節(jié)點(diǎn)，只需依次添加新節(jié)點(diǎn)即可。而對于事務(wù)200，排好序后為(f,c,a,b,m)，此時(shí)樹中已經(jīng)存在路徑(f,c,a)，那么將這個(gè)前綴路徑中的節(jié)點(diǎn)計(jì)數(shù)都+1，并在a節(jié)點(diǎn)后添加b、m節(jié)點(diǎn)即可。構(gòu)造出的樹如下圖所示：
圖中左側(cè)為物品鏈表頭，虛線表示這個(gè)鏈表的鏈接，實(shí)線表示樹中的鏈接。
在FP-tree中挖掘頻繁模式
????利用構(gòu)造好的FP-tree可快速地挖掘出頻繁模式，只需從低向上處理節(jié)點(diǎn)鏈表即可。對于鏈表中的每一個(gè)物品，利用父結(jié)點(diǎn)求出樹中所有這個(gè)物品的前綴路徑，利用這些路徑便可挖掘出所有包含這個(gè)物品的頻繁項(xiàng)集。比如對于m結(jié)點(diǎn)，樹中的前綴路徑為(f:2,c:2,a:2,m:2)以及(f:1,c:1,a:1,b:1,m:1)，這叫做條件模式基(conditional pattern base)。最終其它物品與m共同出現(xiàn)的次數(shù)就為(f:3,c:3,a:3,b:1)，所以所有包含m結(jié)點(diǎn)的頻繁項(xiàng)集就為{(m),(f,m),(c,m),(a,m),(f,c,m),(f,a,m),(c,a,m),(f,a,c,m)}。這個(gè)過程如圖所示：
代碼實(shí)現(xiàn)
參考文獻(xiàn)
1: Mining Frequent Patterns without Candidate Generation
