關聯規則挖掘方法探究論文

導語：關聯規則挖掘方法探究論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要從大量事務記錄中發現有意義的關聯規則，可以幫助做出許多商務決策，如分類設計、交叉購物，從而提高銷售額和利潤。本文提出了一種基于鏈表族數據結構的關聯規則挖掘的改進方法，性能明顯優于Apriori算法。由于該方法只需訪問數據庫一次，對于挖掘海量數據其性能尤為明顯。

關鍵詞數據挖掘；關聯規則；支持度

1問題概述

關聯規則的挖掘的形式化描述如下：令I={i1，i2，…im}為項目集(也稱為模式)，D為事務(又稱交易)數據庫，其中每個事務T是I中一組項目集合，即TI，并令其有一個唯一的標識符TID。如果對于I中的子集X有XT，則事務包含項目集X。關聯規則就是形如XY的邏輯蘊涵式，其中XI，YI，且X∩Y=。如果D中S%交易包含X∪Y，關聯規則XY在D中具有支持s。如果D中c%的包含X的交易也同時包含Y，則關聯規則XY在D中可信度c成立。關聯規則挖掘一般分為兩步：①發現所有的頻繁項目集，也就是說這些項目集在數據庫中的支持計數必須不小于預先設定的一個閾值，即最小支持度；②由頻繁項目集產生強關聯規則，也就是說這些強關聯規則必須滿足最小支持度和最小可信度。其中第2步，一般采用如下方法：對于一個頻繁項目集l的每一個非空子集s如果support_count(1)/support_count(s)≥min_conf，(其后support_count(1)表示項目集l在數據庫中的支持計數，而min_conf表示最小可信度)則規則輸出：“s(1-s)”，該規則也稱為強關聯規則，第2步相對比較簡單，目前大部分研究工作都針對第1步，以改進尋找頻繁項目集的效率，本文針對第1步提出了一種稱為ALT的改進算法。

2研究現狀

目前，關聯規則挖掘算法中，最有影響的是AGRWAL和SRIKANT于1994年提出的Apriori算法[1]。在許多情況下，Apriori的候選產生-檢查方法大幅度壓縮了候選項目集的大小，并導致很好的性能，然而，它有兩種開銷微不足道：①可能產生大量候選項目集；②可能需要重復地掃描數據庫，通過模式匹配檢查有一個很大的候選集合，但有一種有趣的稱為頻繁模式增長(Frequent_PatternGrowth)，或簡稱FP-增長解決了此問題。它采用如下分治策略：將提供頻繁項目集的數據庫壓縮到一棵頻繁模式樹(FP-樹)，并仍保留項目集關聯信息；然后將這種壓縮后的數據庫分成一組條件數據庫(一種特殊類型的投影數據庫)，每個關聯一個頻繁項，并分別挖掘每個數據庫。對于挖掘長的和短的頻繁模式，FP-樹方法都是有效的和可伸縮的，并且比Apriori方法快一個數量級。其它關聯規則挖掘方法還有參考文獻[1]中討論且給出的AIS算法，參考文獻[2]給出的SETM算法及文獻[3]給出的IUA算法。

3ALT算法

Alt算法只需遍歷事務數據庫一次，用來生成頻繁1—項目集。并由此可以得到頻繁2—項目集，頻繁3—項目集，……，頻繁k項目集。對于頻繁i(1≤i≤k)—項目集，采用了一種特殊的數據結構——鏈表簇來存貯。簇中的每一鏈表用來表示頻繁i—項目集各項目的信息，表頭節點(patternData)和表節點(tidData)存儲結構如圖1所示。

nextLpatternnewedcountnextP

(patternData)

tidnextP

(tidData)

圖1存儲結構

圖1中nextL是一指針，用來鏈接簇中下一鏈表；pattern用來存儲頻繁i—項目集某一項目；newed用來標示項目集pattern域是否生成了新的頻繁項目集，同時也作為最大頻繁項目集判斷條件，初始值為false，若由pattern域產生了新的頻繁項目集，其值變為true，當新的頻繁K+1項目集的鏈表族生成后，若某頻繁k項目集對應newed域值仍然為false，則該頻繁-k項目集鏈表對應的pattern域值為一最大頻繁項目集；count是該項目集的支持計數；nextP用來鏈接表節點。對于tidDada，tid是支持項目集pattern的事務標識，保持字典遞增有序，nextP用來鏈接下一個支持項目集pattern節點。

例：有如表1所示事務數據庫，最小支持計數為3。

定義：最大頻繁項目集——如果某一頻繁項目集的所有超集都是非頻繁項目集，則該頻繁項目集稱為最大頻繁項目集。

根據定義知：當一個頻繁i項目集不能據此生成頻繁i＋1項目集，該頻繁項目集是一最大頻繁項目集。

則其頻繁1—項目集的鏈表簇構造如圖2所示。

圖2頻繁1-項目集鏈表簇構造

性質：頻繁項目集的所有子集都是頻繁的。

ALT算法的原理在于先求取所有的最大頻繁項目集，然后依次求取每一個最大頻繁項目集的子集，從而得到頻繁項目集。

ALT算法求最大頻繁項目集如下：

輸入：事務數據庫(T)，最小支持度(根據最小支持度和項目集的個數，可以得到最小支持計數)；

輸出：最大頻繁項目集(Answer)。

①計算最小支持計數，最小支持計數(Minsup)＝最小支持度×事務數；

②生成頻繁1—項目集L，及其對應的鏈表族；

③依次處理頻繁K—項目集對應的鏈表，據此得到最大頻繁項目集。

（1）初始化pvh，pvn為鏈表族表頭結點掃描指針，pvh指向鏈表族第一條單鏈表，pvn指向pvh所指鏈表的下一條鏈表。

（2）while(pvn→next≠null)/*鏈表族中還有待處理鏈表時*/

{/*依次處理各鏈表*/

while(pvn≠null){

pvhw=pvh→nextP；pvnw=pvn→nextP/*初始化pvhw為pvh指針所指單鏈表的工作指針，初始化pvnw為pvn所指單鏈表的工作指針*/

if(pattern=GeneratePattern(pvh->pattern，pvn->pattern)≠null){

/*用pvh，pvn所在鏈表頭結點的項目集生成新的項目集pattern，如果pattern符合條件，計算對應事務數是否大于閾值minsup。*/

count=0；

while(pvhw≠null&&pvnw≠null){

if(pvhw→tid==pvnw→tid)count++；

elseif(pvhw→tid<pvnw→tid)pvhw=pvhw→nextP；

elsepvnw=pvnw→nextP；}

if(count>=minsup){

/*對于項目集pattern生成一個新的鏈表加入到頻繁(k+1)項目集鏈表族中*/

join(ph，pattern，pvh，pvn)；

pvh→newed=true；pvn→newed=true；/*表明這兩條鏈表產生了頻繁(k+1)項目集*/}}

pvn=pvn→nextP；}

if(pvh→newed==false)/*表明該頻繁k項目集沒有生成頻繁(k+1)項目集*/

Answer=answer∪pvh→pattern/*pvh所在頻繁k項目集加入到最大頻繁項目集*/

else{

pvh=pvh→nextP；pvn=pvh→nextP；}

}

（3）由于算法在生成新的項目集時，采用了窮舉法，Answer中某個項目集可能是另外一個項目集的真子集，要將其刪除。

對于表1中的事務數據庫，其產生頻繁2—項目集鏈表族如圖3所示，以及最終頻繁4—項目集如圖4所示。

該事務數據庫中，最大頻繁項目集為Answer={CP，AFM，CFM，ACFM}，又因為AFM，CFM為ACFM的真子集。將其刪除后的Answer={CP，ACFM}。則該事務數據庫的最大頻繁項目集為{CP，ACFM}。

4結論

為驗證該算法，作者在Celeron2.53GHz，512MB內存的微機上進行了試驗，所用數據為mushroom(共8000多條記錄)，并與Apriori算法進行了比較，結果如圖5所示。

該算法借助特殊數據結構實現了最大頻繁項目集的挖掘，從而實現了關聯規則的快速發現。由于該算法只需一次訪問事務數據庫，可以避免頻繁訪問數據庫造成時間上的巨大浪費。對于數量級別越高的數據庫其優越性表現尤為明顯。

參考文獻

[1]AGRAWALR，IMIELINSKIT，SWAMIA.Miningassociationrulesbetweensetsofitemsinlargedatabase[A].ProceedingsofACMSIGODConferenceonManagementofData[C].WashingtonDC，1993，207~216

[2]HOUTSMAM，SWAMIA.Set-orientedminingofassociationrules[R].ResearchReportRJ9567.SanJose：IBMAlmadenResearchCenter，1993

[3]馮玉才，馮劍琳.關聯規則的增量式更新算法[J].軟件學報，1998，9(1)：301~306

[4]STRINANTR，AGRAWALR.Miningquantitativeassociationrulesinlargerelationaltables[A].ProceedingsofACMSIGMODConferenceonManagementofData(SIGMOD’96)[C].Montreal，1996.1-12