第六章數(shù)據(jù)挖掘基本算法

第六章數(shù)據(jù)挖掘基本算法

吳聯(lián)規(guī)貝!J

AssociationRules

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植

內(nèi)容提要

.?引言

■Apriori算法

■Frequent-patterntree和FP-growth算法

-多維關(guān)聯(lián)規(guī)則挖掘

-相關(guān)規(guī)則

■基于約束的關(guān)聯(lián)規(guī)則挖掘

?總結(jié)

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植2

關(guān)聯(lián)規(guī)則

■關(guān)聯(lián)規(guī)則表示了項(xiàng)之間的關(guān)系

■示例：

谷物，牛奶=>水果

''買谷類食品和牛奶的人也會買水果」

商店可以把牛奶和谷類食品作特價(jià)品以使人們買更多的水

果.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植3

市場購物籃分析

■分析事務(wù)數(shù)據(jù)庫表

PersonBasket

A薯片，沙司，曲奇，餅干，可樂，啤酒

B生菜，菠菜，木籽，芹菜，蘋果，葡萄

C薯片，沙司，披薩，蛋糕

D生菜,菠菜，牛奶，黃油

■我們是否可假定?

■薯片=>沙司生菜=>菠菜

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植4

基本概念

-通常，數(shù)據(jù)包含:

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植5

關(guān)聯(lián)規(guī)則挖掘

■在事務(wù)數(shù)據(jù)庫,關(guān)系數(shù)據(jù)庫和其它信

息庫中的項(xiàng)或?qū)ο蟮募现g，發(fā)現(xiàn)

頻繁模式,關(guān)聯(lián),相關(guān),或因果關(guān)系的

結(jié)構(gòu).

■頻繁模式：數(shù)據(jù)庫中出現(xiàn)頻繁的模式

（項(xiàng)集，序列，等等）

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植6

基本概念

-項(xiàng)集

Transaction-idItemsbought

■事務(wù)10A,B,C

匚

TI20A,C

■關(guān)聯(lián)規(guī)則

30A,D

AnB40B,E,F

AuI,BuI,AcB=0

■D-事務(wù)數(shù)據(jù)集（例如右圖）

■事務(wù)標(biāo)識TID

每一個(gè)事務(wù)關(guān)聯(lián)著一個(gè)標(biāo)識，稱作TID.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植7

度量有趣的關(guān)聯(lián)規(guī)則

■支持度S

-D中包含力和B的事務(wù)數(shù)與總的事務(wù)數(shù)的比值

s(…)J…)…和

11^II

規(guī)則An8在數(shù)據(jù)集D中的支持度為s,其中s表示D中

包含AUB（即同時(shí)包含A和B）的事務(wù)的百分率，即可用

條件概率HAUB）表示,

support。nB）=RAUB）.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植8

度量有趣的關(guān)聯(lián)規(guī)則

■可信度C

-D中同時(shí)包含A和B的事務(wù)數(shù)與只包含A的事務(wù)數(shù)的比值

\\{TED\A^JBT}\\

c(A=>B)=-------------------------------------

\\{TED\A^T}||

規(guī)則An8在數(shù)據(jù)集D中的可信度為c,其中c表示D中包含A的

事務(wù)中也包含B的百分率.即可用條件概率P出/4表示,

confidence^nB)=P(B/A)

條件概率P(B/A)表示A發(fā)生的條件下B也發(fā)生的概率.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植9

度量有趣的關(guān)聯(lián)規(guī)則

■關(guān)聯(lián)規(guī)則根據(jù)以下兩個(gè)標(biāo)準(zhǔn)（包含或排除）：

■最小支持度-表示規(guī)則中的所有項(xiàng)在事

務(wù)中出現(xiàn)的頻度

-最小可信度-表示規(guī)則中左邊的項(xiàng)（集）

的出現(xiàn)暗示著右邊的項(xiàng)（集）出現(xiàn)的頻度

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植10

市場購物籃分析

PersonBasket

A薯片，沙司，曲奇，餅干，可樂，啤酒

B生菜，菠菜，桔子，芹菜，蘋果，葡萄

C薯片,沙司，披薩，蛋糕

D生菜,菠菜，牛奶，黃油

項(xiàng)集I是什么？

事務(wù)IDB的T是什么？

s（薯片二＞沙司）是什么?

c（薯片二＞沙司）是什么?

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植11

頻繁項(xiàng)集

■項(xiàng)集-任意項(xiàng)的集合

■k-項(xiàng)集-包含k個(gè)項(xiàng)的項(xiàng)集

■頻繁（或大）項(xiàng)集-滿足最小支持度的項(xiàng)集

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植12

強(qiáng)關(guān)聯(lián)規(guī)則

■給定一個(gè)項(xiàng)集，容易生成關(guān)聯(lián)規(guī)則.

■項(xiàng)集：｛薯片，沙司，啤酒｝

.啤酒，薯片=>沙司

-啤酒，沙司=>薯片

-薯片，沙司=>啤酒

■強(qiáng)規(guī)則是有趣的

■強(qiáng)規(guī)則通常定義為那些滿足最小支持度和最小

可信度的規(guī)則.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植13

關(guān)聯(lián)規(guī)則挖掘

-兩個(gè)基本步驟

.找出所有的頻繁項(xiàng)集

■滿足最小支持度

.找出所有的強(qiáng)關(guān)聯(lián)規(guī)則

-由頻繁項(xiàng)集生成關(guān)聯(lián)規(guī)則

■保留滿足最小可信度的規(guī)則

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植14

容提要

㈡.Apriori算法

■Frequent-patterntree和FP-growth算法

-多維關(guān)聯(lián)規(guī)則挖掘

■相關(guān)規(guī)則

■基于約束的關(guān)聯(lián)規(guī)則挖掘

■總結(jié)

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植15

生成頻繁項(xiàng)集

■Naivealgorithm

n<-|D|

foreachsubsetsofIdo

1<-0

foreachtransactionTinDdo

ifsisasubsetofTthen

1<-1+1

ifminimumsupport<=1/nthen

addstofrequentsubsets

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植16

生成頻繁項(xiàng)集

■naivealgorithm的分析

■/的子集：0(2m)

■為每一個(gè)子集掃描n個(gè)事務(wù)

■測試s為T的子集：0(2mn)

■隨著項(xiàng)的個(gè)數(shù)呈指數(shù)級增長！

■我們能否做的更好？

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植17

Apriori性質(zhì)

■定理（Apriori性質(zhì)）：若A是一個(gè)頻繁項(xiàng)集，則A的每

一個(gè)子集都是一個(gè)頻繁項(xiàng)集.

■證明:設(shè)n為事務(wù)數(shù),假設(shè)A是I個(gè)事務(wù)的子集，若A，

匚人，則人，為I，（P21）個(gè)事務(wù)的子集,因此，l/n

2s（最小支持度），I'/n2s也成立.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植18

Apriori算法

■Apriori算法是一種經(jīng)典的生成布爾型關(guān)聯(lián)規(guī)則的頻

繁項(xiàng)集挖掘算法,算法名字是緣于算法使用了頻繁項(xiàng)

集的性質(zhì)這一先驗(yàn)知識.

■思想：

首先找出頻繁1-項(xiàng)集，以L1表示.L1用來尋找L2,即頻

繁2-項(xiàng)集的集合.L2用來尋找L3,以此類推，直至沒有

新的頻繁k-項(xiàng)集被發(fā)現(xiàn).每個(gè)Lk都要求對數(shù)據(jù)庫作一

次完全掃描..

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植19

生成頻繁項(xiàng)集

■中心思想：由頻繁(k-1)一項(xiàng)集構(gòu)建候選k-項(xiàng)集

■方法

■找到所有的頻繁1-項(xiàng)集

■擴(kuò)展頻繁(k-1)一項(xiàng)集得到候選k-項(xiàng)集

■剪除不滿足最小支持度的候選項(xiàng)集

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植20

Apriori:一種候選項(xiàng)集生成一測試方法

-Apriori剪枝原理:若任一項(xiàng)集是不頻繁的，則其超集

不應(yīng)該被生成/測試！

■方法：

■由頻繁k-項(xiàng)集生成候選(k+1)-項(xiàng)集，并且

■在DB中測試候選項(xiàng)集

■性能研究顯示了Apriori算法是有效的利可伸縮

(scalablility)的.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植21

TheApriori算法一一個(gè)示例

Itemsetsup

Itemsetsup

DatabaseTDB{A}2J

{A}2

Items{B}3

{B}3

10A,C,D{C}3

1stscan{C}3

20B,C,E{D}1

{E}3

30A,B,C,E{E}3

40B,E

L?Itemsetsup

{A,C}2

{B,C}2

{B,E}3

{C,E}2

Itemset

{B,C,E}

{B,C,E)2

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植22

Aprjpri

Algorithm:Apriori

輸入:Database,D,oftransactions;minimumsupportthreshold,min_sup.

輸出:L,freuqentitemsetsinD.

過程:

以：Candidateitemsetofsizek

Lk:frequentitemsetofsizek

L]=find_frequent_l_itemsets(D);

for(Zr=2;Lk+1!=0;k++)dobegin{

Ck=apriori_gen(3,min_sup);

foreachtransactiontindatabaseDdo{//scanDforcounts

Ct=subset(Q,t);//getthesubsetsoftthatarecandidates

ForeachcandidateCGCt

c.count++;

)

Lk=candidatesinQwithmin_support

}end

returnL=u44；

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植23

Apriori_

ProcedureapriorLgenCL^:frequent(k-l)-itemsets;min_sup:minimum

supportthreshold)

foreachitemsetL^

foreachitemsetI2e4.7

if(l1[l]=l2[l])A(l1[2]=l2[2])A...(I1[k-l]=l2[k-l])

Then{

c=join(l1,l2)//joinstep:generatecandidates

ifhas_infrequent_subset(c,)then

deletec;//prunestep:removeunfruitfulcandidate

elseaddctoQ

)

returnCk

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植24

Aprjpri

JoinisgeneratecandidatessetofitemsetsCkfrom2

itemsetsinLk_t

Procedurejoin(p.q)

insertintoCk

selectpJtemppjtem2,-,.,pjterrik.p

q.iterrik.i

fromLip,Liq

wherep-item^qJtemppJtemk_2=qjtemk_2,

pJtem^!=q-item^!

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植25

Aprjpri

Procedurehas_infrequent_subset(c:candidatek-itemse^L^:frequent(k-l)-

itemsets-)ll\ise.priorknowledge

foreach(k-l)-subsetsofc

ifseLythen

returnTRUE;

returnFALSE.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植26

Apriori算法的重要細(xì)節(jié)

■如何生成候選項(xiàng)集？

■步驟1：自連接Lk

-步驟2:剪枝

■如何計(jì)算候選項(xiàng)集的支持度？

■候選項(xiàng)麻生成的示例

■L3={abe,abd,acd,ace,bed}

■自連接：L3*L3

■由abc和abd連接得至Uabed

■由acd和ace連接得至（Jacde

■剪枝：

-因?yàn)閍de不在。中acde被剪除

■C^abcd}

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植27

如何生甲性選項(xiàng)集？

■假定中的項(xiàng)以一定順序排列

■步驟1:自連接L-

insertintoCk

selectpjtem^p?item2r?,“p.itemk_uqjtem^!

fromLipfLk.iq

?

wherep./te/n2=q.item1/,“pjtemk_2=qjtemk_2rp.item^<

qjtem^

-步驟2:剪枝

fora11itemsetscinQdo

fora11(k-1)-subsetssafedo

if(sisnotinLk_t)thendeleteefromCk

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植28

如何計(jì)算候選項(xiàng)集的支持度？

■為何候選項(xiàng)集的支持度的計(jì)算是一個(gè)問題?

■候選項(xiàng)集的總數(shù)可能是巨大的

■一個(gè)事務(wù)可能包含多個(gè)候選項(xiàng)集

■方法：

■候選項(xiàng)集被存儲在一個(gè)哈希樹

-基于劃分的方法

-采樣方法，在給定數(shù)據(jù)的一個(gè)子集挖掘

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植29

頻繁模式挖掘的挑戰(zhàn)

-挑戰(zhàn)

?多次掃描事務(wù)數(shù)據(jù)庫

■巨大數(shù)量的候選項(xiàng)集

?繁重的計(jì)算候選項(xiàng)集的支持度工作

■改進(jìn)Apriori:大體的思路

■減少事務(wù)數(shù)據(jù)庫的掃描次數(shù)

■縮減候選項(xiàng)集的數(shù)量

■使候選項(xiàng)集的支持度計(jì)算更加方便

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植30

容提要

匚AFrequent-patterntree和FP-growth算法

■多維關(guān)聯(lián)規(guī)則挖掘

■相關(guān)規(guī)則

■基于約束的關(guān)聯(lián)規(guī)則挖掘

■總結(jié)

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植31

頻繁模式挖掘的瓶頸

■多次掃描數(shù)據(jù)庫是高代價(jià)的

-長模式的挖掘需要多次掃描數(shù)據(jù)庫以及生成許多的

候選項(xiàng)集

■找出頻繁項(xiàng)集i外…iloo

?掃描次數(shù)：100

■候選項(xiàng)集的數(shù)量：(wo1)+(1002)+…+(J?！?。°)=2100-

1=1.27*103。！

■瓶頸:候選項(xiàng)集-生成-測試

■我們能否避免生成候選項(xiàng)集？

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植32

不生成候選堊集的頻繁模式挖掘

-利用局部頻繁的項(xiàng)由短模式增長為長模式

?“abc”是一個(gè)頻繁模式

-得到所有包含“abc”的事務(wù)：DB|abc

?"d”是DB|abc的一個(gè)局部頻繁的項(xiàng)今abed

是一個(gè)頻繁模式

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植33

FPGrowth算法(Han,Pei,Yin2000)

■Apriori算法的一個(gè)有問題的方面是其候選項(xiàng)

集的生成

■指數(shù)級增長的來源

■另一種方法是使用分而治之的策略(divide

andconquer)

■思想：將數(shù)據(jù)庫的信息壓縮成一個(gè)描述頻繁

項(xiàng)相關(guān)信息的歐繁模式物

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植34

利用FP-樹進(jìn)行頻繁模式挖掘

■思想：頻繁模式增長

■遞歸地增長頻繁模式借助模式和數(shù)據(jù)庫劃分

■方法

■對每個(gè)頻繁項(xiàng)，構(gòu)建它的條件模式基，然后構(gòu)建它

的條件FP-樹.

■對每個(gè)新創(chuàng)建的條件FP-樹重復(fù)上述過程

■直至結(jié)果FP-樹為空，或者它僅包含一個(gè)單一路徑.

該路徑將生成其所有的子路徑的組合，每個(gè)組合

都是一個(gè)頻繁模式.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植35

頻繁1-項(xiàng)集

事務(wù)數(shù)據(jù)庫"支持度計(jì)數(shù)標(biāo)白一項(xiàng)集

TIDItemsItemsetSupport

111,12,15countItemsetSupportcount

12,14{11}6

2{11}6

312,13,16{12}7

{12}7

411,12,14{13}6

{13}6

511,13{14}2

{14}2

612,13{15}2

{15}2

711,13{16}1

811,12,13,15

911,12,13

■最小支持度為20%（計(jì)數(shù)為2）

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植36

FP-樹構(gòu)建

按支持度降序排列

ItemsetSupportcountItemsetSupportcount

{11}6{12}7

{12}7{11}6

{13}6{13}6

{14}2{14}2

{15}2{⑸2

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植37

FP-樹構(gòu)建

?創(chuàng)建根結(jié)點(diǎn)

卷掃描數(shù)據(jù)庫

■事務(wù)1:II,12,15

.排序：12,II,15

④處理事務(wù)

合以項(xiàng)的順序增加結(jié)點(diǎn)

合標(biāo)注項(xiàng)及其計(jì)數(shù)

④維護(hù)索引表

2012-10-9AA12?史忠植38

FP-樹構(gòu)建

TIDItems

111,12,15

212,14

312,13,16

411,12,14

511,13

612,13

711,13

811,12,13,15

911,12,13

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植39

FP-樹構(gòu)建

TIDItems

111,12,15

212,14

312,13,16

411,12,14

511,13

612,13

711,13

811,12,13,15

911,12,13

(15,1)

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植40

FP-樹構(gòu)建

■掃描事務(wù)數(shù)據(jù)庫D一次，得到頻繁項(xiàng)的集合F及它們

的支持度,將F按支持度降序排列成L,L是頻繁項(xiàng)的

列表.

■創(chuàng)建FP-樹的根，標(biāo)注其為NULL,對D中的每個(gè)事務(wù)

進(jìn)行以下操作：

■根據(jù)L中的次序?qū)κ聞?wù)中的頻繁項(xiàng)進(jìn)行選擇和排序.

設(shè)事務(wù)中的已排序的頻繁項(xiàng)列表為[p|PL其中p表

示第一個(gè)元素?表示剩余的列表,調(diào)用

insert_Tree([p|P],T).

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植41

FP-樹構(gòu)建

■Insert_Tree([p|P],T)

IfThasachildNsuchthatN.item-name=

pJtem-name,

thenincrementN'scountby1;

elsecreateanewnodeN,andletitscountbe1,

itsparentlinkbelinkedtoT,anditsnode-

linktothenodeswiththesameitem-name

viathenode-linkstructure,

IfPisnonempty,callinsert_tree(P,N)recursively,

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植42

挖掘FP-tree

■從索引表中的最后一個(gè)項(xiàng)開始

■找到所有包含該項(xiàng)的路徑

■沿著結(jié)點(diǎn)-鏈接(node-links)

■確定條件模式

■路徑中符合頻度要求的模式

■構(gòu)建FP-treeC

■添加項(xiàng)至C中所有路徑,生成頻繁模式

■遞歸地挖掘C(添加項(xiàng))

■從索引表和樹中移除項(xiàng)

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植43

挖掘FP-Tree

(1211,1)

(12II13,1)

令條件路徑

(12II,2)

令條件FP-tree

Qnull

(12,2)0

(11,2)0

?(12II15,2),

(1215,2),

(Il15,2)

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植44

挖掘FP-Tree

項(xiàng)條件模式基條件FP-tree生成的頻繁模式

15{(1211:1)/121113:1)}<I2:2,I1:2>1215:2,

Il15:2,

121115:2

14{(1211:1),(12:1))<I2:2>1214:2

13{(1211:2,(12:2),(11:2))<I2:4,I1:2>,1213:4,

<I1:2>Il13:2,

121113:2

11{(12：4)}<I2:4>1211:4

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植45

挖掘FP-Tree

ProcedureFP__growth（Tree,a）

（i）IfTreecontainsasinglepathPthen

（2）foreachcombination（denoteasp）ofthenodesinthe

pathP

（3）generatepatternpuawithsupport=minisupofnodesinp；

（4）Elseforeacha,intheheaderofTree{

（5）generatepatternp=a）uawithsupport=3,.support;

（6）constructp,sconditionalpatternbaseandthen「'conditional

FP_treeTreep.

（7）IFTree/0then

（8）

callFP_growth（Treepp）;}

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植46

由事務(wù)數(shù)據(jù)庫構(gòu)建FP-樹

TID

C左

G<G

100{f,a,cfd9g94m,p}辦p}

右G

200{a,b,c,f,I,m,o}b,m}

〃

右

300{b9f,hj,o,w}fAminsupport=3

lG

400{b,c,A,s,p}G

右

500{aff,c,e,I,p,m,n}m,p}

()

HeaderTable

L掃描DB一次，找到頻繁1

項(xiàng)（單一項(xiàng)稹式）

Item①head

4

2,按支持度降序?qū)︻l繁項(xiàng)c4c:3y/b:1，,>b:l

排序?yàn)镕-lista3

3,再次掃描DB,構(gòu)建FP-b3

treem3

P3

F-list=f-c-a-b-m-p

p:21m:l

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植47

劃分模式和數(shù)據(jù)庫

-頻繁模式根據(jù)F-list可以被劃分為若干子集

■F-list=f-c-a-b-m-p

■包含p的模式

■包含m但包含p的模式

■包含c但不包含a,b,m,p的模式

■模式f

■完整性和非冗余性

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植48

從P的條件到據(jù)庫找出包含P的模式

■從FP-tree的索引表的頻繁項(xiàng)開始

■沿著每個(gè)頻繁項(xiàng)夕的鏈接遍歷FP-tree

■累積項(xiàng)p的所有轉(zhuǎn)換前綴路徑來形成的夕的條件模式基

HeaderTable

條件模式基

Itemfreq4uencyhead

項(xiàng)條件模式基

4c:3,b:l->b:l

3cf：3

3afc:3

3

3bc:l

>m:2Jb:11mfca:2,fcab:l

p:2m:lpfcam:2,cb:l

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植49

遞歸:挖掘每個(gè)條件FP-tree

{}

I

{}''am〃的條件模式基：(fc:3)f：3

I

Ic:3

f：3

Iam■條件FP-tree

c'3{}

i''cm〃的條件模式基：(f:3)I

a:3f：3

AW-祭步FP-tree

cm-條殍FP-tree

()

I

“cam〃的條件模式基：(f:3)儲

ca/n-條步FP-tree

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植50

一個(gè)特例：FP-tree中的單一前綴路徑

■假定（條件的）FP-treeT有一個(gè)共享的單一前綴路徑P

■挖掘可以分為兩部分

價(jià)■將單一前綴路徑約簡為一個(gè)結(jié)點(diǎn)

I■將兩部分的挖掘結(jié)果串聯(lián)

a:n

I11

a2：n2

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植51

通過DB投影(Projection)使FP-growth可伸縮

■FP-tree不能全放入內(nèi)存?一DB投影

■首先將一個(gè)數(shù)據(jù)庫劃分成一個(gè)由若干投影(Projected)

數(shù)據(jù)庫組成的集合

■然后對每個(gè)投影數(shù)據(jù)庫構(gòu)建和挖掘FP-tree

■Parallelprojectionvs.Partitionprojection技術(shù)

■Parallelprojectionisspacecostly

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植52

Partition-basedProjection

■Parallelprojection需要很多磁注*加

fcamp

盤空間fcabm

■Partitionprojection節(jié)省磁盤

空間

D-projDBDBb-projDBDBoprojDBf-projDB

fcafca

cbfca

------------------------------

am-projDBDB

fc

fc

fc

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植53

改進(jìn)途徑

■使用哈希表存儲候選k-項(xiàng)集的支持度計(jì)數(shù)

-移除不包含頻繁項(xiàng)集的事務(wù)

-對數(shù)據(jù)采樣

-劃分?jǐn)?shù)據(jù)

-若一個(gè)項(xiàng)集是頻繁的，則它必定在某個(gè)數(shù)據(jù)

分區(qū)中是頻繁的.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植54

FP-tree結(jié)構(gòu)的優(yōu)點(diǎn)

■完整性

■保持了頻繁項(xiàng)集挖掘的完整信息

■沒有打斷任何事務(wù)的長模式

■緊密性

■減少不相關(guān)的信息一不頻繁的項(xiàng)沒有了

■項(xiàng)按支持度降序排列：越頻繁出現(xiàn),越可能被共享

■決不會比原數(shù)據(jù)庫更大（不計(jì)結(jié)點(diǎn)鏈接和計(jì)數(shù)域）

■對Connect-4數(shù)據(jù)庫，壓縮比率可以超過100

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植55

FP-Growthvs,Apriori:支持度的可伸縮性

-----?-----D1FP-growthruntime

-----*-----D1Aprioriruntime

d

e

s

o

E

q

U

E

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植56

FP-Growthys,Treg~Proiection:支持度的可｛申縮性

DatasetT25I20D100K

140

120

100

80

60

40

20

0

o0.511.52

Supportthreshold(%)

257

關(guān)聯(lián)規(guī)則可視化：方格圖(PaneGraph)

^DBMinerEnterprise-PM-Associfl^ir]

曲FileMiningAssociatorViewWindowOptionsHelp俯|x]

IH牌Im|闡A|G|?I

畫31畝陋＞17|J

2.T9

ForHelp,pressFl!NUM

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植58

關(guān)聯(lián)規(guī)則可視化：規(guī)則圖(RuleGraph)

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植59

內(nèi)容提要

■Apriori算法

■Frequent-patterntree和FP-growth算法

y多維關(guān)聯(lián)規(guī)則挖掘

y

■相關(guān)規(guī)則

■基于約束的關(guān)聯(lián)規(guī)則挖掘

■總結(jié)

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植60

規(guī)則或規(guī)律_________________

■多層(Multi-level),量化(quantitative)關(guān)聯(lián)規(guī)則，相關(guān)

(correlation)和因果(causality),比率(ratio)規(guī)則，序

列(sequential)模式，浮現(xiàn)(emerging)模式,

temporalassociations,局部周期(partialperiodicity)

■分類(classification),聚類(clustering),冰山立方體

(icebergcubes),等等.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植61

多層關(guān)聯(lián)規(guī)則

■項(xiàng)常常構(gòu)成層次

■可伸縮的(flexible)支持度設(shè)置：在較低層的項(xiàng)預(yù)期有較低的

支持度.

■事務(wù)數(shù)據(jù)庫可以基于維度和層次編碼

■探尋共享多層挖掘

統(tǒng)一支持度減少的支持度

Level1

MilkLevel1

minsup=5%

[support=10%]minsup=5%

Level22%MilkSkimMilkLevel2

minsup=5%[support=6%]i[support=4%]minsup=3%

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植62

可伸縮的支持度約束的多層/多維(ML/MD)關(guān)聯(lián)規(guī)則

-為什么設(shè)置可伸縮的支持度？

-實(shí)際生活中項(xiàng)的出現(xiàn)頻率變化巨大

-在一個(gè)商店購物籃中的鉆石，手表，鋼筆

■統(tǒng)一的支持度未必是一個(gè)有趣的模型

■一個(gè)可伸縮模型

-較低層的，較多維的組合以及長模式通常具有較小的支

持度

■總體規(guī)則應(yīng)該要容易說明和理解

-特殊的項(xiàng)和特殊的項(xiàng)的組合可以特別設(shè)定(最小支持度)

以及擁有更高的優(yōu)先級

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植63

多維關(guān)聯(lián)規(guī)則____________________

-單維規(guī)則：

buys(X,''milk'Onbuys(X,''bread。

■多維規(guī)則：＞2個(gè)維度或謂詞(predicates)

■跨維度(Inter-dimension)關(guān)聯(lián)規(guī)則(無重復(fù)謂詞)

age(X,”19-25")△occupation(X,"student")n

buys(X,“coke”)

-混合維度(hybrid-dimension)關(guān)聯(lián)規(guī)則(重復(fù)謂詞)

age(X,”19-25")Abuys(X,"popcorn")nbuys(X,“coke”)

■分類(Categorical)屬性

-有限的幾個(gè)可能值，值之間不可排序

■數(shù)量(Quantitative)屬性

2012-10-9■數(shù)值的，值之間有固有的排原聯(lián)規(guī)則史忠植64

多層關(guān)聯(lián)規(guī)則:冗余濾除

-根據(jù)項(xiàng)之間的“先輩"（ancestor）關(guān)系，一些規(guī)則可能是冗

余的.

■示例

■milknwheatbread[support=8%,confidence=70%]

■2%milk=>wheatbread[support=2%,confidence=72%]

■我們說第1個(gè)規(guī)則是第2個(gè)規(guī)則的先輩.

-一個(gè)規(guī)則是冗余的,當(dāng)其支持度接近基于先輩規(guī)則的”預(yù)

期”（expected）值.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植65

多層關(guān)聯(lián)規(guī)則:逐步深化(ProgressiveDeepening)

■一個(gè)自上而下的，逐步深化的方法：

■首先挖掘高層的頻繁項(xiàng)：

milk(15%),bread(10%)

-然后挖掘它們的較低層"較弱"(weaker)頻繁項(xiàng):

2%milk(5%),wheatbread(4%)

■多層之間不同的最小支持度閾值導(dǎo)致了不同的算法：

-如果在多個(gè)層次間采用了相同的最小支持度，若t的任何

一個(gè)先輩都是非頻繁的則扔棄(toss)t.

-如果在較低層采用了減少的最小支持度，則只檢驗(yàn)?zāi)切?/p>

先輩的支持度是頻繁的/不可忽略的派生

(descendents)即可.

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植66

多維關(guān)聯(lián)規(guī)則挖掘的技術(shù)

■搜索頻繁卜謂詞集(predicateset):

■示例：｛age,occupation,buys｝是一個(gè)3-謂詞集

-以age處理的方式，技術(shù)可以如下分類

1.利用數(shù)量屬性的統(tǒng)計(jì)離散(staticdiscretization)方法

利用預(yù)先確定的概念層次對數(shù)量屬性進(jìn)行統(tǒng)計(jì)離散化

2.量化關(guān)聯(lián)規(guī)則

-基于數(shù)據(jù)的分布，數(shù)量屬性被動態(tài)地離散化到不同的容器

空間(bins)

3.基于距離(Distance-based)的關(guān)聯(lián)規(guī)則

-這是一個(gè)動態(tài)離散化的過程，該過程考慮數(shù)據(jù)點(diǎn)之間的距

離

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植67

數(shù)量屬性的統(tǒng)計(jì)離散化

■挖掘之前利用概念層次離散化

■數(shù)值被范圍(ranges)替代.

■關(guān)系數(shù)據(jù)庫中，找出所有的頻繁k-謂詞(predicate)集要求k

或價(jià)1次表掃描.

-數(shù)據(jù)立方體(datacube)非常適合數(shù)據(jù)挖掘.

■N-維立方體的cells與謂詞集(,、

(age)((mcp(me)xlbuys)

predicatesets)相對應(yīng).

-通過數(shù)據(jù)立方體挖掘會非?？煲凰?」…)

(age,income,buys)

2012-10-9AA12關(guān)聯(lián)規(guī)則史忠植68

量化關(guān)聯(lián)規(guī)則

■數(shù)值屬性動態(tài)離散化

-這樣挖掘的規(guī)則的可信度或緊密度最大化

-2-維量化關(guān)聯(lián)規(guī)則:Aquanl△^quan20^cat

■示例

income

age(X,"30-34”)Aincome(X,,924K-

48K”)

nbuys(X,,9highresolutionTV")

2012-10-9

化關(guān)聯(lián)規(guī)則

■ARCS:AssociationRuleClusteringSystem

(關(guān)聯(lián)規(guī)則聚類系統(tǒng))

借鑒了圖像處理中的思想,本質(zhì)上，這種方法映射一對數(shù)量

屬性到滿足給定的分類屬性條件的2-維元組格.然后對柵格

搜索找到聚類點(diǎn),由其生成關(guān)聯(lián)規(guī)則.

■ARCS