6.挖掘頻繁模式、關聯和相關性：基本概念和方法

頻繁模式（frequent?pattern）是頻繁地出現在數據集中的模式。

6.1?基本概念

頻繁模式挖掘搜索給定數據集中反復出現的聯系，旨在發現大型事務或關系數據集中項之間有趣的關聯或相關性，其典型例子就是購物籃分析。

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

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

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

第一：找出所有的頻繁項集；第二：由頻繁項集產生強關聯規則。

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

?

6.2?頻繁項集挖掘方法

Apriori算法是一種發現頻繁項集的基本算法，為布爾關聯規則挖掘頻繁項集的原創性算法。

1）Apriori算法：通過限制候選產生發現頻繁項集

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

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

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

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

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

挖掘布爾關聯規則發現頻繁項集的Apriori算法如下：

?

2）由頻繁項集產生關聯規則

????一旦數據庫D中的事務找出頻繁項集，就可以直接產生強關聯規則（強關聯規則滿足最小支持度和最小置信度）。

3）提高Apriori算法的效率

提高基于Apriori挖掘的效率：

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

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

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

抽樣：對給定數據的一個子集上挖掘。

動態項集計數：在掃描不同點添加候選項集，動態項集計數將數據庫劃分為用開始點標記的塊。

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

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

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

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

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

輸入：D:事務數據庫

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

輸出：頻繁模式的完全集

方法：

?????1.按以下步驟構造?FP?樹：

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

???????b.創建FP樹的根節點，以null標記它，對于D中每個事務Trans，執行：

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

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

??????2.FP樹的挖掘同構調用FP_growth(PF_tree,null)實現，該過程實現如下：

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

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

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

???????????????產生模式a?∪?b?，其支持度計數support_count等于b?中結點的最小支持度計數

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

?????????????產生一個模式b=a?∪?a_i，其支持度計數support_count=a_i.support_count；

?????????????構造b的條件模式基，然后構造b的條件FP樹Tree_b；

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

????????????????調用FP_growth(Tree_b,b);

?????????}

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

5）使用垂直數據格式挖掘頻繁項集

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

垂直數據格式，商品項為行，事務為列。

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

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

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

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

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

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

????當一個新的頻繁項集導出后，要進行兩種閉包檢查：超集檢查，檢查新的頻繁項集是否是某個具有相同支持度的、已經發現的、閉項集的超集；子集檢查，檢查新發現的項集是否是某個具有相同支持度的、已經發現的、閉項集的子集。

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

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

1）強規則不一定有趣的

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

2）從關聯分析到相關分析

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

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

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

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

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

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

6.4?小結

1）大量數據中的頻繁模式、關聯和相關關系的發現在選擇性銷售、決策分析和商務管理方面是有用的。一個流行的應用領域是購物籃分析，同構搜索經常一起（或依次）購買的商品的集合，研究顧客的購買習慣。

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

3）對于頻繁項集挖掘，已有許多有效的、可伸縮的算法，可導出關聯和相關規則，分成三類：類Apriori算法、基于頻繁模式增長的算法，如FP-growth；3）使用垂直數據格式的算法。

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

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

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

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

?

6.5?項目課題

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

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。