6.挖掘頻繁模式、關(guān)聯(lián)和相關(guān)性：基本概念和方法

頻繁模式（frequent?pattern）是頻繁地出現(xiàn)在數(shù)據(jù)集中的模式。

6.1?基本概念

頻繁模式挖掘搜索給定數(shù)據(jù)集中反復(fù)出現(xiàn)的聯(lián)系，旨在發(fā)現(xiàn)大型事務(wù)或關(guān)系數(shù)據(jù)集中項之間有趣的關(guān)聯(lián)或相關(guān)性，其典型例子就是購物籃分析。

購物籃分析假設(shè)全域是商品的集合，每種商品有一個布爾變量，表示該商品是否出現(xiàn)在購物籃中。每個購物籃是一個布爾向量表示，分析布爾向量，可得到反映商品頻繁關(guān)聯(lián)或同時購買的購買模式，這些模式可用關(guān)聯(lián)規(guī)則（association?rule）形式表示。如購買計算機也趨向于同時購買殺毒軟件，用如下規(guī)則表示：computer=>antivirus_software[support=2%;confidence=60%]。規(guī)則的支持度（support）和置信度（confidence）是規(guī)則興趣度的兩種度量，分別反映所發(fā)現(xiàn)規(guī)則的有用性和確定性。如果規(guī)則滿足最小支持度閾值和最小置信度閾值，則關(guān)聯(lián)規(guī)則是有趣的。

同時滿足最小支持度閾值（min_sup）和最小置信度閾值（min_conf）的規(guī)則稱為強規(guī)則。

項的集合稱為項集，包含k個項的項集稱為k項集。項集的出現(xiàn)頻度是包含項集的事務(wù)數(shù)，稱為項集的頻度、支持度計數(shù)或計數(shù)。項集支持度也稱為相對支持度，而出現(xiàn)頻度稱為絕對支持度。如果項集I的相對支持度滿足預(yù)定義的最小支持度閾值（即?I的絕對支持度滿足對應(yīng)的最小支持度計數(shù)閾值），則I是頻繁項集（frequent?itemset）。頻繁k項集的集合通常記為L_k。關(guān)聯(lián)規(guī)則的挖掘一般兩步：

第一：找出所有的頻繁項集；第二：由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則。

從大型數(shù)據(jù)集中挖掘頻繁項集的主要挑戰(zhàn)是：產(chǎn)生大量滿足最小支持度（min_sup）的閾值的項集。項集X在數(shù)據(jù)集D中是閉的（closed），如果不存在真超項集Y，使得Y與X在D中具有相同的支持度計數(shù)。項集X是數(shù)據(jù)集D中的閉頻繁項集（closed?frequent?itemset），如果X在D中是閉的和頻繁的。項集X是D中的極大頻繁項集（maximal?frequent?itemset）或極大項集（max-itemset），如果X是頻繁的，并且不存在超項集Y，使得并且?Y在D中是頻繁的。

?

6.2?頻繁項集挖掘方法

Apriori算法是一種發(fā)現(xiàn)頻繁項集的基本算法，為布爾關(guān)聯(lián)規(guī)則挖掘頻繁項集的原創(chuàng)性算法。

1）Apriori算法：通過限制候選產(chǎn)生發(fā)現(xiàn)頻繁項集

先驗性質(zhì)：頻繁項集的所有非空子集也一定是頻繁的。也稱為反單調(diào)性（antimonotone），指如果一個集合不能通過測試，則它的所有超集也不能通過相同的測試。

基于先驗性質(zhì)，Apriori算法使用逐層搜索的迭代方法，其中k項集用于探索k+1項集。首先，通過掃描數(shù)據(jù)庫，累計每個項的計數(shù)，并收集滿足最小支持度的項，找出頻繁I項集的集合，記集合L1；然后，使用L1找出頻繁2項集的集合L2，使用L2找出L3，如此下去，直到不能再找到頻繁k項集。找出每個L_k需要一次數(shù)據(jù)庫的完整掃描。

基于先驗性質(zhì)從L_k-1找出L_k，由連接步和剪枝步組成：

連接步：為找出L_k，通過將L_k-1與自身連接產(chǎn)生候選k項集的集合，記為C_k，算法這里假定事務(wù)或項集中的項按字段序排序。

剪枝步：C_k是L_k的超集，C_k中的成員可以是頻繁也可以不是，但所有的頻繁k項集都包含在C_k中。

挖掘布爾關(guān)聯(lián)規(guī)則發(fā)現(xiàn)頻繁項集的Apriori算法如下：

?

2）由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則

????一旦數(shù)據(jù)庫D中的事務(wù)找出頻繁項集，就可以直接產(chǎn)生強關(guān)聯(lián)規(guī)則（強關(guān)聯(lián)規(guī)則滿足最小支持度和最小置信度）。

3）提高Apriori算法的效率

提高基于Apriori挖掘的效率：

采用基于散列的技術(shù)（散列項集到對應(yīng)的桶中）：一種基于散列的技術(shù)可用于壓縮候選k項集的集合Ck(k>1)。

事務(wù)壓縮（壓縮進一步迭代掃描的事務(wù)數(shù)）：不包含任何頻繁k項集的事務(wù)不可能包含任何頻繁(k+1)項集。

劃分（為找候選項集劃分?jǐn)?shù)據(jù)）：第一階段把D中的事務(wù)化分成n個非重疊的分區(qū)；第二階段評估每個候選的實際支持度，確定全局頻繁項集。

抽樣：對給定數(shù)據(jù)的一個子集上挖掘。

動態(tài)項集計數(shù)：在掃描不同點添加候選項集，動態(tài)項集計數(shù)將數(shù)據(jù)庫劃分為用開始點標(biāo)記的塊。

4）挖掘頻繁項集的模式增長方法

Apriori可能產(chǎn)生大量的候選項集，需要重復(fù)地掃描整個數(shù)據(jù)庫，通過模式匹配檢查一個大的候選集合，這個開銷比較大。因此，提出一種頻繁模式增長的方法（Frequent-Pattern?Growth,FP-growth），該方法采用分治策略。首先將代表頻繁項集的數(shù)據(jù)庫壓縮到一顆頻繁模式樹（FP樹），該樹保留項集的關(guān)聯(lián)信息；然后把壓縮后的數(shù)據(jù)庫劃分成一組條件數(shù)據(jù)庫（一種特殊類型的投影數(shù)據(jù)庫），每個數(shù)據(jù)庫關(guān)聯(lián)一個頻繁項或模式段，并分別挖掘每個條件數(shù)據(jù)庫。對于每個模式片段，只考察與它相關(guān)聯(lián)數(shù)據(jù)集。

FP樹的挖掘：由長度為1的頻繁模式（初始后綴模式）開始，構(gòu)造它的條件模式基（一個子數(shù)據(jù)庫，由FP樹中與該后綴模式一起出現(xiàn)出現(xiàn)的前綴路徑集組成）。然后，構(gòu)造它的條件FP樹，并遞歸地在該樹上進行挖掘。模式增長通過后綴模式與條件FP樹產(chǎn)生的頻繁模式連接實現(xiàn)。

FP-growth方法將發(fā)現(xiàn)長頻繁模式的問題轉(zhuǎn)換成在較小的條件數(shù)據(jù)庫中遞歸地搜索一些較短模式，然后連接后綴。使用最不頻繁的項做后綴，提供了很好的選擇性，顯著地降低了搜索開銷。

算法：FP-Growth，使用FP樹，通過模式增長挖掘頻繁模式

輸入：D:事務(wù)數(shù)據(jù)庫

??????min_sup：最小支持度閾值

輸出：頻繁模式的完全集

方法：

?????1.按以下步驟構(gòu)造?FP?樹：

???????a.掃描事務(wù)數(shù)據(jù)庫D一次，收集頻繁項的集合F和它們的支持度計數(shù)，對F按支持度計數(shù)降序???排序，結(jié)果為頻繁項列表L。

???????b.創(chuàng)建FP樹的根節(jié)點，以null標(biāo)記它，對于D中每個事務(wù)Trans，執(zhí)行：

選擇Trans中的頻繁項，并按L中次序排序。設(shè)Trans排序后的頻繁項列表為[p|P]，其中p是第一個元素，而P是剩余元素的列表。調(diào)用insert_tree([p|P],T)。

如果T有子女N使得N.item_name=p.item_name，則N的計數(shù)增加1；否則創(chuàng)建一個新結(jié)點N，將其計數(shù)置為1，鏈接到它的父節(jié)點T，并且通過結(jié)點鏈結(jié)構(gòu)將其鏈接到具有相同item_name的結(jié)點。如果P非空，則遞歸地調(diào)用insert_tree(P,N)。

??????2.FP樹的挖掘同構(gòu)調(diào)用FP_growth(PF_tree,null)實現(xiàn)，該過程實現(xiàn)如下：

??????Procedure?FP_growth(Tree,a)

?????????if?Tree包含單個路徑P?then

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

???????????????產(chǎn)生模式a?∪?b?，其支持度計數(shù)support_count等于b?中結(jié)點的最小支持度計數(shù)

?????????else?for?Tree的頭表中的每個a_i{

?????????????產(chǎn)生一個模式b=a?∪?a_i，其支持度計數(shù)support_count=a_i.support_count；

?????????????構(gòu)造b的條件模式基，然后構(gòu)造b的條件FP樹Tree_b；

?????????????if?Tree_b?≠???then?

????????????????調(diào)用FP_growth(Tree_b,b);

?????????}

對FP-growth方法的性能研究表明，對于挖掘長的頻繁模式和短的頻繁模式，都是有效的和可伸縮的，并且大約比Apriori算法快一個數(shù)量級。

5）使用垂直數(shù)據(jù)格式挖掘頻繁項集

Apriori算法和FP-growth算法都是以事務(wù)為行、商品項為列，即水平數(shù)據(jù)格式。

垂直數(shù)據(jù)格式，商品項為行，事務(wù)為列。

使用垂直數(shù)據(jù)格式，不需要掃描數(shù)據(jù)庫來確定k+1項集的支持度，因為每個k項集已攜帶了計算支持度的完整信息。

6）挖掘閉模式和極大模式

挖掘閉頻繁項集的剪枝策略包括：

a.項合并：如果包含頻繁項集X的每個事務(wù)都包含項集Y，但不包含?Y?的任何真超集，則?X?∪?Y形成一個閉頻繁項集，并且不必搜索包含X但不包含Y的任何項集。

b.子項集剪枝：如果頻繁項集X是一個已經(jīng)發(fā)現(xiàn)的閉頻繁項集Y的真子集，并且support_count(X)=support_count(Y)，則X和Y在集合枚舉樹種的所有后代都不可能是閉頻繁項集，因此可以剪枝。

c.項跳過：在深度優(yōu)先挖掘閉項集時，每一層都有一個與頭表和投影數(shù)據(jù)庫相關(guān)聯(lián)的前綴項集X；如果一個局部頻繁項p在不同層的多個頭表中都具有相同的支持度，則可以將p從較高層頭表中剪裁掉。

????當(dāng)一個新的頻繁項集導(dǎo)出后，要進行兩種閉包檢查：超集檢查，檢查新的頻繁項集是否是某個具有相同支持度的、已經(jīng)發(fā)現(xiàn)的、閉項集的超集；子集檢查，檢查新發(fā)現(xiàn)的項集是否是某個具有相同支持度的、已經(jīng)發(fā)現(xiàn)的、閉項集的子集。

6.3?那些模式是有趣的：模式評估方法

關(guān)聯(lián)規(guī)則挖掘算法基本都使用支持度-置信度框架。不過低支持度閾值挖掘或挖掘長模式時，會產(chǎn)生很多無趣的規(guī)則，這是關(guān)聯(lián)規(guī)則挖掘應(yīng)用的瓶頸之一。

1）強規(guī)則不一定有趣的

????基于支持度-置信度框架識別出的強關(guān)聯(lián)規(guī)則，不足以過濾掉無趣的關(guān)聯(lián)規(guī)則，需要度量相關(guān)性和蘊涵關(guān)系。

2）從關(guān)聯(lián)分析到相關(guān)分析

為識別規(guī)則的有趣性，需使用相關(guān)性度量來擴充關(guān)聯(lián)規(guī)則的支持度-置信度框架。相關(guān)規(guī)則不僅用支持度和置信度度量，而且還用項集A和B之間的相關(guān)性度量。相關(guān)性度量的方法有：

提升度（lift）：項集A的出現(xiàn)獨立于項集B的出現(xiàn)，如果P(A∪B)=P(A)P(B)；否則，作為事件，項集A和B是依賴的（dependent）和相關(guān)的（correlated），則A和B出現(xiàn)之間的提升度定義為：

lift(A,B)=P(A∪B)/P(A)P(B)

如果lift(A,B)<1，則說明A的出現(xiàn)和B的出現(xiàn)是負相關(guān)的；如果lift(A,B)>1，則A和B是正相關(guān)的，意味每一個的出現(xiàn)蘊涵另一個的出現(xiàn)；如果lift(A,B)=1，則說明A和B是獨立的，沒有相關(guān)性。

這四個度量，度量值僅受A、B和A∪B的支持度的影響，或說是受條件概率P(A|B)和P(B|A)的影響，而不受事務(wù)總個數(shù)的影響。四種度量方法的另一個共同性質(zhì)是：每個度量值都去【0,1】，且值越大，A和B越緊密。

總結(jié)：僅使用支持度和置信度度量來挖掘關(guān)聯(lián)可能產(chǎn)生大量規(guī)則，其中有可能存在用戶不感興趣的；因此，可用模式興趣度度量來擴展支持度-置信度框架，有助于聚焦到強模式聯(lián)系的規(guī)則挖掘上。

6.4?小結(jié)

1）大量數(shù)據(jù)中的頻繁模式、關(guān)聯(lián)和相關(guān)關(guān)系的發(fā)現(xiàn)在選擇性銷售、決策分析和商務(wù)管理方面是有用的。一個流行的應(yīng)用領(lǐng)域是購物籃分析，同構(gòu)搜索經(jīng)常一起（或依次）購買的商品的集合，研究顧客的購買習(xí)慣。

2）關(guān)聯(lián)規(guī)則挖掘首先找出頻繁項集（項的集合，如?A和B，滿足最小支持度閾值，或任務(wù)相關(guān)元組的百分比），然后，由它們產(chǎn)生形如A->B的強關(guān)聯(lián)規(guī)則；這些規(guī)則滿足最小置信度閾值（預(yù)定義的，在滿足A的條件下滿足B的概率）；可進一步分析關(guān)聯(lián)，發(fā)現(xiàn)項集A和B之間具有統(tǒng)計相關(guān)性的相關(guān)規(guī)則。

3）對于頻繁項集挖掘，已有許多有效的、可伸縮的算法，可導(dǎo)出關(guān)聯(lián)和相關(guān)規(guī)則，分成三類：類Apriori算法、基于頻繁模式增長的算法，如FP-growth；3）使用垂直數(shù)據(jù)格式的算法。

4）Apriori算法是為布爾關(guān)聯(lián)規(guī)則挖掘頻繁項集的原創(chuàng)新算法，逐層進行挖掘，利用先驗性質(zhì)：頻繁項集的所有非空子集也都是頻繁的；在第k次迭代（k≥2），根據(jù)頻繁（k-1）項集形成k項集候選，并掃描數(shù)據(jù)庫一次，找出完成的頻繁k項集的集合L_k；使用涉及散列和事務(wù)壓縮技術(shù)的變形使得過程更有效。其他變形包括劃分?jǐn)?shù)據(jù)（對每分區(qū)挖掘，然后合并結(jié)果）和抽樣數(shù)據(jù)（對數(shù)據(jù)子集挖掘）；這些變形可將數(shù)據(jù)掃描次數(shù)減少到一兩次。

5）頻繁模式增長（FP-growth）是一種不產(chǎn)生候選的挖掘頻繁項集方法；構(gòu)造一個高度壓縮的數(shù)據(jù)結(jié)構(gòu)（FP樹），壓縮原來的事務(wù)數(shù)據(jù)庫；和類Apriori方法使用產(chǎn)生-測試策略不同，FP-growth更聚焦于頻繁模式（段）增長，避免了高代價的候選產(chǎn)生，可獲得更好的效率。

6）使用處置數(shù)據(jù)格式挖掘頻繁模式（ECLAT）將給定的、用TID-項集形式的水平數(shù)據(jù)格式事務(wù)數(shù)據(jù)集變換成項-TID-集合形式的垂直數(shù)據(jù)格式；根據(jù)先驗性質(zhì)和附加的優(yōu)化技術(shù)（如diffset），通過TID-集的交，對變換后的數(shù)據(jù)集進行挖掘。

7）并非所有的強關(guān)聯(lián)規(guī)則都是有趣的，應(yīng)用模式評估度量來擴展支持度-置信度框架，識別有效的有趣規(guī)則；一種度量是零不變的，如果它的值不受零事務(wù)（即不包含所考慮項集的事務(wù)）的影響，在許多模式評估度量中，給出了提升度、、全置信度、最大置信度、余弦和Kulczynski。后四種是零不變的；可把Kulczynski度量和不平衡比一起使用，提供項集間的模式聯(lián)系。

?

6.5?項目課題

????DBLP數(shù)據(jù)集（http://www.informatik.unitrier.de/~ley/db/）包括超過100萬篇發(fā)表在計算機科學(xué)會議和雜志上的論文項。這些項中，很多作者有合著關(guān)系，提出一種方法，挖掘密切相關(guān)的（即經(jīng)常一起寫文章的）合著者關(guān)系；根據(jù)挖掘結(jié)果和模式評估度量，分析那種度量方法更有效。

總結(jié)

以上是生活随笔為你收集整理的【数据挖掘笔记六】挖掘频繁模式、关联和相关性：基本概念和方法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。