1頻繁模式2頻繁項挖掘算法3頻繁模式挖掘算法4頻繁模式挖掘的其他問題5小結頻繁項從每天的銷售數(shù)據(jù)中統(tǒng)計賣的最好的產(chǎn)品、查看最多的產(chǎn)品……頻繁項集3能否看一下，都有哪些商品會被用戶同時放在購物車中——哪些商品組合出現(xiàn)頻次最高？頻繁項&頻繁項集4思考一下，如何實時推薦歌單？頻繁項集頻繁項項，是數(shù)據(jù)集的元素如果項的出現(xiàn)頻率滿足預定義的最小閾值即頻繁項頻繁項集項的集合稱為項集包含k個項的項集稱為k-項集項集的出現(xiàn)頻率是包含項集的事務數(shù)，簡稱為項集的頻率，支持度計數(shù)或計數(shù)如果項集的出現(xiàn)頻率滿足預定義的最小閾值即頻繁項集5頻繁模式頻繁模式是頻繁的出現(xiàn)在數(shù)據(jù)集中的模式如項集、子序或者子結構頻繁模式挖掘是發(fā)現(xiàn)數(shù)據(jù)中蘊含的內(nèi)在規(guī)律哪些產(chǎn)品經(jīng)常被一起購買？（啤酒和紙尿褲）買了PC之后接著都會買些什么？（PC

移動硬盤）應用購物籃分析、Web日志分析、捆綁銷售6

頻繁模式的定義

7

頻繁模式的定義

8頻繁項集、頻繁序列、頻繁子圖、頻繁子樹例子

9

N=5

Apriori算法核心思想：任何頻繁項集的子集都是頻繁項集迭代算法首先，找出所有的頻繁1-項集；然后，找出所有的頻繁2-項集；……10ABACADBCBDCDABCDABCABDACDBCDApriori算法—過程示例

11第1次遍歷

C1={1}:2,{2}:3,{3}:3,{4}:1,{5}:3 候選集 F1={1}:2,{2}:3,{3}:3,{5}:3 頻繁項集 C2={1,2},{1,3},{1,5},{2,3},{2,5},{3,5}第2次遍歷

C2={1,2}:1,{1,3}:2,{1,5}:1,{2,3}:2,{2,5}:3,{3,5}:2

F2={1,3}:2,{2,3}:2,{2,5}:3,{3,5}:2

C3={2,3,5}第3次遍歷

C3={2,3,5}:2

F3={2,3,5}:2T100T200T300T4001,3,42,3,51,2,3,52,5N=4>2取交集取交集Apriori算法——頻繁項

12Apriori算法——候選集Function

candidate-gen(Fk-1) Ck

; forall

f1,f2

Fk-1 withf1={i1,…,ik-2,ik-1} andf2={i1,…,ik-2,i’k-1} andik-1<i’k-1

do c

{i1,…,ik-1,i’k-1}; //合并f1和f2 Ck

Ck

{c}; foreach(k-1)-subsetsofc

do if(s

Fk-1)then deletecfromCk; //若k-1子集非頻繁項集，則剪枝 end end returnCk;13Apriori算法—思考Apriori算法能用于流數(shù)據(jù)的頻繁模式挖掘嗎？挖掘頻繁項時，每個項一個計數(shù)器（存不下）挖掘頻繁項集時，需進行多次遍歷（行不通）14流數(shù)據(jù)分析特點：進行一次遍歷記住重要信息允許有限誤差1頻繁模式2頻繁項挖掘算法3頻繁模式挖掘算法4頻繁模式挖掘的其他問題5小結有損計數(shù)頻繁項挖掘16有損計數(shù)算法

17項的實際頻次

有損計數(shù)算法

18注意：并不能準確預計流數(shù)據(jù)的基數(shù)，即不同類型項目的數(shù)量哈希表頻次計數(shù)器的項數(shù)如何定？有損計數(shù)算法19第一步：劃分窗口

有損計數(shù)算法20第二步：計數(shù)

為什么需要記錄窗口序號？如果所有項幾乎都不同會怎樣？

21有損計數(shù)算法第三步：在窗口邊界調(diào)整計數(shù)器

為什么需要刪除計數(shù)器？22有損計數(shù)算法第四步：處理下一個窗口繼續(xù)計數(shù)，并在邊界處調(diào)整計數(shù)器

刪除計數(shù)器會帶來多少計數(shù)誤差？23有損計數(shù)算法第五步：查詢輸出

項的估計頻次

沒有漏報?。∮袚p計數(shù)算法最后得到的是什么

2425有損計數(shù)算法總過程

邊界調(diào)整，刪除

邊界調(diào)整，刪除

邊界調(diào)整

誤差最大的是

如果刪掉了Ci滿足有損計數(shù)算法—可行性內(nèi)存開銷能否滿足流數(shù)據(jù)要求？計數(shù)器的最大內(nèi)存開銷：

隨數(shù)據(jù)流長度增長?。?shù)學歸納法證明，證明參見G.S.Manku,R.Motwani,Approximatefrequencycountsoverdatastreams,inProc.28thVLDB(2002),pp.356–357.

26

粘性抽樣頻繁項挖掘27粘性抽樣算法

28項的實際頻次

粘性抽樣算法過程

2930粘性抽樣算法過程

第一步：劃分窗口

粘性抽樣算法過程31第二步：采樣+計數(shù)

粘性抽樣算法過程32第三步：窗口邊界處調(diào)整計數(shù)器第四步：處理下一個窗口對每個計數(shù)器投擲均勻硬幣反面則刪除一個元素正面則跳至下個計數(shù)器元素刪除完則刪除計數(shù)器即：以1/2概率保留老窗口的入選概率變?yōu)檎麄€數(shù)據(jù)流都按照最新的概率抽樣??！

原窗口新窗口

新窗口入選概率是老窗口入選概率的

33粘性抽樣算法過程

第五步：查詢輸出項的實際頻次

項的估計頻次

沒有漏報??！粘性抽樣算法可行性34

wrN2t12t2t2rt+2t4t3rt+4t8t4rt+8t

粘性抽樣算法可行性

35A,

A,

A,

A,

A,

B,

B,

B,

B,

BA,

A,

A,

A,

A,

A,

B,

B,

B,

B

粘性抽樣算法可行性36

KPS算法頻繁項挖掘37KPS算法

38KPS算法

39KPS算法40

ABCDE2211111ABC221AB121ABF

計數(shù)器++夠5個，開始刪除計數(shù)器-1剩余

A、B滿足，F(xiàn)不滿足KPS算法

41算法對比頻繁項挖掘42算法比較各種算法的比較43特征有損計數(shù)算法粘性采樣算法KPS算法查詢結果誤差??以至少?????的概率保證誤差??超集誤差無保證內(nèi)存空間理論性能精確較精確保證精度時需兩次遍歷1頻繁模式2頻繁項挖掘算法3頻繁模式挖掘算法4頻繁模式挖掘的其他問題5小結頻繁項集頻繁項

頻繁項集45ZHAOYUN,YANGWEN,WANG,WULI,LAN,LONG,LIUCAI,CAO,CHA,CHANG,CHAO,CHEN如何保存和判斷？CA =2LI =2AN =3AO =3NG =4CH =4CHA =3頻繁項集頻繁項集的判斷頻繁項（哈希表）

頻繁項集（Trie樹）Trie樹用于快速檢索的多叉樹結構最大限度地減少無謂的字符串比較，查詢效率比哈希表高46ZHAOYUN,YANGWEN,WANG,WULI,LAN,LONG,LIUCAI,CAO,CHA,CHANG,CHAO,CHEN如果{L,I}不是頻繁項集，那么{L,I,U}也不是頻繁項集的有損計數(shù)算法

47<,10,0><,12,0><,6,0>typedef

struct

TrieNode{

NodeKind

kind;//TRUE=分支節(jié)點

union

{

struct

{

KeyType

K;

Record

*infoPtr

}

lf;

//葉子節(jié)點

struct

{

TrieNode

*ptr[128];

int

num

}

bh;

//分支節(jié)點

};}TrieNode,

*TrieTree;頻繁項集的有損計數(shù)算法48第一步：劃分窗口

Q=1Q=2Q=3Q=4Q=5Q=6a1,a2a1,a2,a3a2,a3,a5a1a1,a2,a3,a4a1,a2a2,a3a4a2,a3,a5a1,a3,a5a1,a2,a3a1,a2,a3,a5a3a1,a3a1,a5a1,a4a3,a4a5,a6,a7a2,a6a5,a6a3,a6a5,a6a1,a2a6項集時間β=2w=12,bcurrent=1w=12,bcurrent=2批處理頻繁項集的有損計數(shù)算法49第二步：計數(shù)+窗口邊緣調(diào)整計數(shù)器

Q=1Q=2Q=3Q=4Q=5Q=6a1,a2a1,a2,a3a2,a3,a5a1a1,a2,a3,a4a1,a2a2,a3a4a2,a3,a5a1,a3,a5a1,a2,a3a1,a2,a3,a5a3a1,a3a1,a5a1,a4a3,a4a5,a6,a7a2,a6a5,a6a3,a6a5,a6a1,a2a6項集時間β=2w=12,bcurrent=1w=12,bcurrent=2頻繁項集的有損計數(shù)算法50a1a2a3a4a512,07,04,02,03,0a5a2a3a511,07,03,02,0(itemset,f,Δ)a6a3a4a5a4a62,012,04,08,03,06,0a54,0a36,0第二步：計數(shù)+窗口邊緣調(diào)整計數(shù)器Q=1Q=2Q=3Q=4Q=5Q=6a1,a2a1,a2,a3a2,a3,a5a1a1,a2,a3,a4a1,a2a2,a3a4a2,a3,a5a1,a3,a5a1,a2,a3a1,a2,a3,a5a3a1,a3a1,a5a1,a4a3,a4a5,a6,a7a2,a6a5,a6a3,a6a5,a6a1,a2a6項集時間β=2w=12,bcurrent=1w=12,bcurrent=2

a4a5Trie樹51頻繁項集的有損計數(shù)算法Q=7Q=8Q=9Q=10Q=11Q=12a1,a2,a4a3a2,a3a1a2,a3,a4a1,a2a2,a3,a5a4a3,a5a3,a5a2,a3a1,a2,a3a3,a5a1,a3,a4,a5a1,a3,a5a1,a4,a5a6,a7a4,a5,a6a6,a7a3,a5,a6a3,a6a3,a5,a6a1,a2a4,a6項集時間a1a2a3a6a5a2a3a3a4a5a4a6a4a520,011,05,03,26,019,012,04,02,226,011,018,06,013,0β=2(itemset,f,Δ)w=12,bcurrent=3w=12,bcurrent=4a512,0a39,0a52,2a42,2a63,2a53,2a72,2a72,2第二步：計數(shù)+窗口邊緣調(diào)整計數(shù)器

a5不需要繼續(xù)對分支進行試探52頻繁項集的有損計數(shù)算法

第三步：查詢輸出

課后證明：1頻繁模式2頻繁項挖掘算法3頻繁模式挖掘算法4頻繁模式挖掘的其他問題5小結頻繁模式挖掘的其他問題頻繁序列挖掘在分布式數(shù)據(jù)流中查找Top-k項在數(shù)據(jù)流中尋找大流（HeavyHitters）頻繁子樹挖掘在樹數(shù)據(jù)集中尋找頻繁出現(xiàn)的子結構有根有序樹（OrderedT