第二章+關(guān)聯(lián)規(guī)則挖掘-20140918

10三月20241/91第二章關(guān)聯(lián)規(guī)則挖掘軟件工程學(xué)院鄭皎凌10三月20242/91基本概念Task設(shè)I

={i1,i2,...,im}是項的集合。設(shè)A是一個項集，事務(wù)T包含A當(dāng)且僅當(dāng)A

T

關(guān)聯(lián)規(guī)則是形如A

B的蘊涵式，其中A

I，B

I，并且A

B=

規(guī)則A

B在事務(wù)集D中成立，具有支持度s，置信度c，s=包含A、B的元組數(shù)/元組總數(shù)c=包含A、B的元組數(shù)/包含A的元組數(shù)10三月20243/91TaskAB元組總數(shù)10三月20244/91AllElectronics某分店的事務(wù)數(shù)據(jù)TIDListofitem_ID’sT100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I310三月20245/9110三月20246/91基本概念同時滿足最小支持度閾值(min_sup)和最小置信度閾值(min_conf)的規(guī)則稱作強規(guī)則。項的集合稱為項集。包含k個項的項集稱為k-項集。如果項集滿足最小支持度，則稱它為頻繁項集10三月20247/91關(guān)聯(lián)規(guī)則的挖掘過程找出所有頻繁項集：根據(jù)定義，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持計數(shù)一樣。由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則：根據(jù)定義，這些規(guī)則必須滿足最小支持度和最小置信度。這兩步中，第二步最容易。挖掘關(guān)聯(lián)規(guī)則的總體性能由第一步?jīng)Q定。10三月20248/91關(guān)聯(lián)規(guī)則如何用于決策？10三月20249/9110三月202410/9110三月202411/9110三月202412/91關(guān)聯(lián)規(guī)則R1：烤鴨

面餅、面醬。支持度40%，置信度為66.6%R2：面餅

烤鴨、面醬。支持度40%，置信度為66.6%R3：面醬

面餅、烤鴨。支持度40%，置信度為50%10三月202413/91關(guān)聯(lián)規(guī)則KDD結(jié)果不一定是因果關(guān)系。運用之妙成乎于人。

例如∶用R1，將烤鴨降價以促銷面餅、面醬，很可能會破產(chǎn)用R2將面餅降價，以促銷烤鴨，可能會發(fā)財；用R3，引不起顧客的熱情。10三月202414/91挖掘單維布爾關(guān)聯(lián)規(guī)則Apriori算法FP-樹挖掘頻繁閉相集挖掘10三月202415/91

Apriori算法：使用候選項集找頻繁項集Apriori使用一種稱作逐層搜索的迭代方法，k-項集用于探索(k+1)-項集。首先，找出頻繁1-項集的集合。該集合記作L1。L1用于找頻繁2-項集的集合L2，而L2用于找L3，如此下去直到不能找到頻繁k-項集。找每個Lk需要一次數(shù)據(jù)庫掃描。10三月202416/91Apriori性質(zhì)頻繁項集的所有非空子集都必須也是頻繁的。Apriori性質(zhì)基于如下觀察：根據(jù)定義，如果項集I不滿足最小支持度閾值s，則I不是頻繁的，即P(I)<s。如果項A添加到I，則結(jié)果項集（即，I

A）不可能比I更頻繁出現(xiàn)。因此，I

A也不是頻繁的，即P(I

A)<s。該性質(zhì)屬于一種特殊的分類，稱作反單調(diào)，意指如果一個集合不能通過測試，則它的所有超集也都不能通過相同的測試10三月202417/91連接步：為找Lk，通過Lk-1與自己連接產(chǎn)生候選k-項集的集合。該候選項集的集合記作Ck。設(shè)l1和l2是Lk-1中的項集。記號li[j]表示li的第j項執(zhí)行連接Lk-1

Lk-1

；其中，Lk-1的元素是可連接的，如果它們前(k-2)個項相同；即，Lk-1的元素l1和l2是可連接的，如果(l1

[1]=l2[1])

(l1[2]=l2[2])

...

(l1[k-2]=l2[k-2])

(l1[k-1]<l2[k-1])。連接l1和l2產(chǎn)生的結(jié)果項集是l1[1]l1[2]...l1[k-1]l2[k-1]。10三月202418/91通過連接步得到的候選相集會不會漏掉頻繁相集？不會l[1]l[2]...l[k-1]l[k]頻繁則l[1]l[2]...l[k-1]

頻繁則l[1]l[2]...l[k]

頻繁必然會連接l[1]l[2]...l[k-1]

和l[1]l[2]...l[k-2]l[k]10三月202419/91剪枝步：Ck是Lk的超集；即，它的成員可以是，也可以不是頻繁的，但所有的頻繁k-項集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每個候選的計數(shù)，從而確定Lk（即，根據(jù)定義，計數(shù)值不小于最小支持度計數(shù)的所有候選是頻繁的，從而屬于Lk）。然而，Ck可能很大，這樣所涉及的計算量就很大。為壓縮Ck，可以用以下辦法使用Apriori性質(zhì)：任何非頻繁的(k-1)-項集都不是可能是頻繁k-項集的子集。因此，如果一個候選k-項集的(k-1)-子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以由Ck中刪除。10三月202420/91AllElectronics某分店的事務(wù)數(shù)據(jù)TIDListofitem_ID’sT100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I310三月202421/9110三月202422/91Apriori算法

使用逐層迭代找出頻繁項集輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值。輸出：D中的頻繁項集L。方法：L1=find_frequent_1_itemsets(D);for(k=2;Lk-1

;k++){Ck=aproiri_gen(Lk-1,min_sup);foreachtransactiont

D{//scanDforcountCt=subset(Ck,t);//getsubsetsoftthatarecandidatesforeachcandidatec

Ctc.count++;}Lk={c

Ck|c.count

min_sup}}returnL=

kLk；10三月202423/91procedureapriori_gen(Lk-1:frequent(k-1)-itemset;min_sup:support)foreachitemsetl1

Lk-1foreachitemsetl2

Lk-1if(l1[1]=l2[1])

...

(l1[k-2]=l2[k-2])

(l1[k-1]<l2[k-2])//通過Lk-1與自己連接產(chǎn)生候選k-項集的集合

//Lk-1的元素是可連接的，如果它們前(k-2)個項相同

//條件(l1[k-1]<l2[k-1])是簡單地保證不產(chǎn)生重復(fù)。//連接l1和l2產(chǎn)生的結(jié)果項集是l1[1]l1[2]...l1[k-1]l2[k-1]

then{c=l1l2;//joinstep:generatecandidatesifhas_infrequent_subset(c,Lk-1)thendeletec;//prunestep:removeunfrequentcadidateelseaddctoCk;}returnCk;10三月202424/91procedurehas_infrequent_subset(c:candidatek-itemset;Lk-1:frequent(k-1)-itemset)//useprioriknowledgeforeach(k-1)-subsetsofcifc

Lk-1thenreturnTRUE;returnFALSE;10三月202425/91由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則對于每個頻繁項集l，產(chǎn)生l的所有非空子集。對于l的每個非空子集s，如果，則輸出規(guī)則“s

(l-s)”。其中，min_conf是最小置信度閾值。10三月202426/91例AllElectronics事務(wù)數(shù)據(jù)庫。假定數(shù)據(jù)包含頻繁項集l={I1,I2,I5}，可以由l產(chǎn)生下列關(guān)聯(lián)規(guī)則？l的非空子集有{I1,I2},{I1,I5},{I2,I5},{I1},{I2}和{I5}。結(jié)果關(guān)聯(lián)規(guī)則如下，每個都列出置信度。10三月202427/91I1

I2

I5,I1I5

I2,I2I5

I1,I1I2

I5,I2I1

I5,I5I1

I2,confidence=2/4=50%confidence=2/2=100%confidence=2/2=100%confidence=2/6=33%confidence=2/7=29%confidence=2/2=100%如果最小置信度閾值為70%，則只有2、3和最后一個規(guī)則可以輸出，因為只有這些是強的。

10三月202428/91

提高Apriori的有效性基于散列的技術(shù)（散列項集計數(shù)）：一種基于散列的技術(shù)可以用于壓縮候選k-項集Ck

(k>1)。例如，當(dāng)掃描數(shù)據(jù)庫中每個事務(wù)，由C1中的候選1-項集產(chǎn)生頻繁1-項集L1時，我們可以對每個事務(wù)產(chǎn)生所有的2-項集，將它們散列（即，映射）到散列表結(jié)構(gòu)的不同桶中，并增加對應(yīng)的桶計數(shù)10三月202429/91提高Apriori的有效性事務(wù)壓縮（壓縮進一步迭代掃描的事務(wù)數(shù)）：不包含任何k-項集的事務(wù)不可能包含任何(k+1)-項集。這樣，這種事務(wù)在其后的考慮時，可以加上標(biāo)記或刪除，因為為產(chǎn)生j-項集(j>k)，掃描數(shù)據(jù)庫時不再需要它們。10三月202430/91提高Apriori的有效性劃分（為找候選項集劃分數(shù)據(jù)）：它包含兩遍。在第I遍，算法將D中的事務(wù)劃分成n個非重疊的部分。如果D中事務(wù)的最小支持度閾值為min_sup，則每個部分的最小支持度計數(shù)為min_sup

該部分中事務(wù)數(shù)。對每一部分，找出該部分內(nèi)的頻繁項集。這些稱作局部頻繁項集。局部頻繁項集可能不是整個數(shù)據(jù)庫D的頻繁項集。D的任何頻繁項集必須作為局部頻繁項集至少出現(xiàn)在一個部分中。這樣，所有的局部頻繁項集作為D的候選項集。所有部分的頻繁項集的集合形成D的全局候選項集。在第II遍，第二次掃描D，評估每個候選的實際支持度，以確定全局頻繁項集。10三月202431/91不產(chǎn)生候選挖掘頻繁項集Apriori有兩種開銷可能并非微不足道：它可能需要產(chǎn)生大量候選項集。如果有104個頻繁1-項集，則Apriori算法需要產(chǎn)生多達107個候選2-項集，累計并檢查它們的頻繁性。此外，為發(fā)現(xiàn)長度為100的頻繁模式，如{a1,...,a100}，它必須產(chǎn)生多達2100

1030個候選。它可能需要重復(fù)地掃描數(shù)據(jù)庫，通過模式匹配檢查一個很大的候選集合。對于挖掘長模式尤其如此。10三月202432/91FP-增長(FP-growth)頻繁模式增長(FP-增長):它采取如分治策略將提供頻繁項集的數(shù)據(jù)庫壓縮到一棵頻繁模式樹（或FP-樹），但仍保留項集關(guān)聯(lián)信息；將這種壓縮后的數(shù)據(jù)庫分成一組條件數(shù)據(jù)庫（一種特殊類型的投影數(shù)據(jù)庫），每個關(guān)聯(lián)一個頻繁項，并分別挖掘每個數(shù)據(jù)庫。10三月202433/91FP-樹構(gòu)造數(shù)據(jù)庫的第一次掃描與Apriori相同，它導(dǎo)出頻繁項（1-項集）的集合，并得到它們的支持度計數(shù)（頻繁性）。設(shè)最小支持度計數(shù)為2。頻繁項的集合按支持度計數(shù)的遞減序排序。結(jié)果集或表記作L。AllElectronics某分店的事務(wù)數(shù)據(jù)的頻繁項L=[I2:7,I1:6,I3:6,I4:2,I5:2]。10三月202434/91FP-樹構(gòu)造L=[I2:7,I1:6,I3:6,I4:2,I5:2]。TIDListofitem_ID’sT100T200T300T400T500T600T700T800T900I1,I2,I5I2,I4I2,I3I1,I2,I4I1,I3I2,I3I1,I3I1,I2,I3,I5I1,I2,I310三月202435/91FP-樹構(gòu)造將這種壓縮后的數(shù)據(jù)庫分成一組條件數(shù)據(jù)庫（一種特殊類型的投影數(shù)據(jù)庫），每個關(guān)聯(lián)一個頻繁項，并分別挖掘每個數(shù)據(jù)庫。10三月202436/91FP-樹挖掘由長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基（一個“子數(shù)據(jù)庫”，由FP-樹中與后綴模式一起出現(xiàn)的前綴路徑集組成）。然后，構(gòu)造它的（條件）FP-樹，并遞歸地在該樹上進行挖掘。模式增長通過后綴模式與由條件FP-樹產(chǎn)生的頻繁模式連接實現(xiàn)。10三月202437/91FP-樹挖掘算法算法：FP-增長。使用FP-樹，通過模式段增長，挖掘頻繁模式。輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值min_sup。輸出：頻繁模式的完全集。方法：按以下步驟構(gòu)造FP-樹：掃描事務(wù)數(shù)據(jù)庫D一次。收集頻繁項的集合F和它們的支持度。對F按支持度降序排序，結(jié)果為頻繁項表L。創(chuàng)建FP-樹的根結(jié)點，以“null”標(biāo)記它。對于D中每個事務(wù)Trans，執(zhí)行：選擇Trans中的頻繁項，并按L中的次序排序。設(shè)排序后的頻繁項表為[p|P]，其中，p是第一個元素，而P是剩余元素的表。調(diào)用insert_tree([p|P],T)。該過程執(zhí)行情況如下。如果T有子女N使得N.item-name=p.item-name，則N的計數(shù)增加1；否則創(chuàng)建一個新結(jié)點N，將其計數(shù)設(shè)置為1，鏈接到它的父結(jié)點T，并且通過結(jié)點鏈結(jié)構(gòu)將其鏈接到具有相同item-name的結(jié)點。如果P非空，遞歸地調(diào)用insert_tree(P,N)。FP-樹的挖掘通過調(diào)用FP_growth(FP_tree,null)實現(xiàn)。該過程實現(xiàn)如下：10三月202438/91FP-樹挖掘算法procedure

FP_growth(Tree,

)if

Tree

含單個路徑P

then

for

路徑P中結(jié)點的每個組合（記作

）產(chǎn)生模式

，其支持度support=

中結(jié)點的最小支持度;elseforeach

ai

在Tree的頭部{產(chǎn)生一個模式

=ai

，其支持度support=ai.support；構(gòu)造

的條件模式基，然后構(gòu)造

的條件FP-樹Tree

；ifTree

then調(diào)用FP_growth(Tree

,

)；}10三月202439/91FP-growth頻繁模式增長挖掘全部頻繁項集而不產(chǎn)生候選構(gòu)造FP-樹：掃描DB一次,找出1-itemset頻繁項集按頻數(shù)遞減順序把頻繁項排序：f-list掃描DB再一次,構(gòu)造FP-樹10三月202440/91FP-growth步驟一：掃描DB一次,找出頻繁1-項集{I2:7,I1:6,I3:6,I4:2,I5:2}步驟二：第2次掃描DB，構(gòu)造FP-樹。null{}I2:I1:I5:I3:I4:I3:I4:I5:I1:I3:TID項ID的列表T100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I37412112221項IDsup節(jié)點鏈I27I16I36I42I5210三月202441/91FP-樹挖掘算法I3的條件模式基是{(I2I1:2),(I2:2),(I1:2)}。它的條件FP-樹有兩個分枝<I2:4,I1:2>和<I1:2>，如圖6.9所示，它產(chǎn)生模式集：{I2I3:4,I1I3:2,I2I1I3:2}。最后，I1的條件模式基是{(I2,4)}，它的FP-樹只包含一個結(jié)點<I2:4>，產(chǎn)生一個頻繁模式I2I1:4。挖掘過程總結(jié)在圖6.10。

10三月202442/91FP-growth由FP-樹產(chǎn)生頻繁模式由長度為1的頻繁模式開始，構(gòu)造它的條件模式基，然后構(gòu)造它的條件FP樹，并遞歸地在該樹上進行挖掘。null{}I2:I1:I5:I3:I4:I3:I4:I5:I1:I3:741211221項IDsup節(jié)點鏈I27I16I36I42I522I5<(I2,I1:1)>,<(I2,I1,I3:1)><I2:2,I1:2>I2I5:2,I1I5:2,I2I1I5:2I4<(I2,I1:1)>,<(I2:1)><I2:2>I2I4:2I3<(I2,I1:2)>,<(I2:2)>,<(I1:2)><I2:4,I1:2>,<I1:2>I2I3:4,I1I3:4,I2I1I3:2I1<(I2:4)><I2:4>I2I1:4Item條件模式基條件FP樹產(chǎn)生的頻繁模式10三月202443/91CompactnessofFP-tree10三月202444/91CompactnessofFP-treeAlphabeticalFP-tree.Itincludesthespaceofallthelinks.However,insuchanFP-tree,thealphabeticalorderofitemsareusedinsteadoffrequencydescendingorder.OrderedFP-tree.thesizecoversthatofalllinks.InsuchanFP-tree,theitemsaresortedaccordingtofrequencydescendingorder.Transactiondatabase.Eachiteminatransactionisstoredasaninteger.Itissimplythesumofoccurrencesofitemsintransactions.Frequenttransactiondatabase.Thatisthesub-databaseextractedfromtheoriginalonebyremovingallinfrequentitems.10三月202445/91Scalabilitystudy10三月202446/91FP-樹挖掘算法的優(yōu)點FP-增長方法將發(fā)現(xiàn)長頻繁模式的問題轉(zhuǎn)換成遞歸地發(fā)現(xiàn)一些短模式，然后與后綴連接。它使用最不頻繁的項作后綴，提供了好的選擇性。該方法大大降低了搜索開銷。當(dāng)數(shù)據(jù)庫很大時，構(gòu)造基于內(nèi)存的FP-樹是不現(xiàn)實的。一種有趣的替換是首先將數(shù)據(jù)庫劃分成投影數(shù)據(jù)庫的集合（上一張），然后在每個投影數(shù)據(jù)庫上構(gòu)造FP-樹并挖掘它。該過程可以遞歸地用于投影數(shù)據(jù)庫，如果它的FP-樹還不能放進內(nèi)存。10三月202447/91最大的頻繁模式最大的頻繁模式是頻繁模式p，使得p的任何真超模式都不是頻繁的。I2I5:2,I1I5:2,I2I1I5:2，I2I4:2，I2I3:4,I1I3:4,I2I1I3:2，I2I1:410三月202448/91最大的頻繁模式最大的頻繁模式是頻繁模式p，使得p的任何真超模式都不是頻繁的。I2I5:2,I1I5:2,I2I1I5:2，I2I4:2，I2I3:4,I1I3:4,I2I1I3:2，I2I1:410三月202449/91頻繁閉項集頻繁閉項集是一個頻繁的、閉的項集；其中，項集c是閉的，如果不存在c的真超集c’，使得每個包含c的事務(wù)也包含c’使用最大模式和頻繁閉項集可以顯著地壓縮挖掘所產(chǎn)生的頻繁項集數(shù)。I2I5:2,I1I5:2,I2I1I5:2，I2I4:2，I2I3:4,

I1I3:4,I2I1I3:2，I2I1:410三月202450/91由關(guān)聯(lián)挖掘到相關(guān)分析強關(guān)聯(lián)規(guī)則關(guān)聯(lián)分析vs相關(guān)分析興趣度10三月202451/91由關(guān)聯(lián)挖掘到相關(guān)分析數(shù)據(jù)挖掘系統(tǒng)如何篩選出用戶感興趣的關(guān)聯(lián)規(guī)則？支持度和置信度閾值強關(guān)聯(lián)規(guī)則一定有趣嗎？相關(guān)分析相關(guān)性度量10