關(guān)聯(lián)規(guī)則挖掘方法探究論文

導(dǎo)語：關(guān)聯(lián)規(guī)則挖掘方法探究論文一文來源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要從大量事務(wù)記錄中發(fā)現(xiàn)有意義的關(guān)聯(lián)規(guī)則，可以幫助做出許多商務(wù)決策，如分類設(shè)計、交叉購物，從而提高銷售額和利潤。本文提出了一種基于鏈表族數(shù)據(jù)結(jié)構(gòu)的關(guān)聯(lián)規(guī)則挖掘的改進(jìn)方法，性能明顯優(yōu)于Apriori算法。由于該方法只需訪問數(shù)據(jù)庫一次，對于挖掘海量數(shù)據(jù)其性能尤為明顯。

關(guān)鍵詞數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；支持度

1問題概述

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

2研究現(xiàn)狀

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

3ALT算法

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

nextLpatternnewedcountnextP

(patternData)

tidnextP

(tidData)

圖1存儲結(jié)構(gòu)

圖1中nextL是一指針，用來鏈接簇中下一鏈表；pattern用來存儲頻繁i—項目集某一項目；newed用來標(biāo)示項目集pattern域是否生成了新的頻繁項目集，同時也作為最大頻繁項目集判斷條件，初始值為false，若由pattern域產(chǎn)生了新的頻繁項目集，其值變?yōu)閠rue，當(dāng)新的頻繁K+1項目集的鏈表族生成后，若某頻繁k項目集對應(yīng)newed域值仍然為false，則該頻繁-k項目集鏈表對應(yīng)的pattern域值為一最大頻繁項目集；count是該項目集的支持計數(shù)；nextP用來鏈接表節(jié)點(diǎn)。對于tidDada，tid是支持項目集pattern的事務(wù)標(biāo)識，保持字典遞增有序，nextP用來鏈接下一個支持項目集pattern節(jié)點(diǎn)。

例：有如表1所示事務(wù)數(shù)據(jù)庫，最小支持計數(shù)為3。

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

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

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

圖2頻繁1-項目集鏈表簇構(gòu)造

性質(zhì)：頻繁項目集的所有子集都是頻繁的。

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

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

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

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

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

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

③依次處理頻繁K—項目集對應(yīng)的鏈表，據(jù)此得到最大頻繁項目集。

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

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

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

while(pvn≠null){

pvhw=pvh→nextP；pvnw=pvn→nextP/*初始化pvhw為pvh指針?biāo)竼捂湵淼墓ぷ髦羔槪跏蓟痯vnw為pvn所指單鏈表的工作指針*/

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

/*用pvh，pvn所在鏈表頭結(jié)點(diǎn)的項目集生成新的項目集pattern，如果pattern符合條件，計算對應(yīng)事務(wù)數(shù)是否大于閾值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；/*表明這兩條鏈表產(chǎn)生了頻繁(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中的事務(wù)數(shù)據(jù)庫，其產(chǎn)生頻繁2—項目集鏈表族如圖3所示，以及最終頻繁4—項目集如圖4所示。

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

4結(jié)論

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

該算法借助特殊數(shù)據(jù)結(jié)構(gòu)實現(xiàn)了最大頻繁項目集的挖掘，從而實現(xiàn)了關(guān)聯(lián)規(guī)則的快速發(fā)現(xiàn)。由于該算法只需一次訪問事務(wù)數(shù)據(jù)庫，可以避免頻繁訪問數(shù)據(jù)庫造成時間上的巨大浪費(fèi)。對于數(shù)量級別越高的數(shù)據(jù)庫其優(yōu)越性表現(xiàn)尤為明顯。

參考文獻(xiàn)

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

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

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

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