關(guān)聯(lián)規(guī)則挖掘中改進型Ｄｉｆｆｓｅｔｓ算法

摘 要：頻繁項集挖掘是關(guān)聯(lián)規(guī)則挖掘中至關(guān)重要的一步。對于稠密數(shù)據(jù)集的頻繁項集挖掘，傳統(tǒng)的挖掘算法往往產(chǎn)生大量無用的中間結(jié)果，造成內(nèi)存利用率的極大浪費，尤其是在支持度較低的情況下。Diffsets算法通過引入“差集”的概念，在一定程度上解決了挖掘過程中產(chǎn)生的大量中間結(jié)果與內(nèi)存容量之間的矛盾。改進型Diffsets算法是在原算法的基礎(chǔ)上，在差集運算過程中根據(jù)差集中所包含的事務(wù)標(biāo)識個數(shù)進行遞減排序，進一步減少了挖掘過程中產(chǎn)生的中間結(jié)果數(shù)量。分析與實例表明，改進后的算法在執(zhí)行過程中將占用更少的內(nèi)存空間，加快了算法的收斂速度。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則挖掘；頻繁項集挖掘；Diffsets

中圖分類號：TP311文獻標(biāo)識碼：B

文章編號：1004-373X(2008)22-080-04

Improved Diffsets Algorithm in Association Rules Mining

SUN Zhichang，F(xiàn)ENG Zuhong

(Institute of Computer Science and Engineering，North Nationality University，Yinchuan，750021，China)

Abstract：Mining frequent items is a key step in association rules mining.As to the mining frequent items of dense datasets，the traditional mining algorithm always turn out a great deal of useless intermediate results which occupies a large proportion of the memory，especially in a low values of support.Diffsets algorithm introduces the conception of differences，and to some extent，it provides a solution of dealing with the contradiction between those multi-intermediate results and the memory capacity.This improved Diffsets algorithm on the basis of original algorithm ranks the number of tids in a degressive way during the the calculation course，in this way，the amount of intermidiate results can be decreased.The analysis and examples show that this imporved algorithm takes less memory space in the operation process and accelerates the convergence pace of the algorithm.

Keywords：data mining;association rules mining;mining frequent items;Diffsets

1 引 言

在過去的數(shù)十年中，人們收集數(shù)據(jù)的能力迅速提高。許多商務(wù)、科學(xué)和行政事務(wù)的計算機化，特別是萬維網(wǎng)的流行，已經(jīng)將人們淹沒在數(shù)據(jù)和信息的海洋中。存貯數(shù)據(jù)的爆炸性增長已激發(fā)對新技術(shù)和自動工具的需求，以便幫助人們將海量數(shù)據(jù)轉(zhuǎn)換成信息和知識。關(guān)聯(lián)規(guī)則挖掘就是按企業(yè)既定的業(yè)務(wù)目標(biāo)，對大量的企業(yè)數(shù)據(jù)進行探索和分析，揭示隱藏的、未知的或驗證已知的商業(yè)規(guī)律，且進一步將其模式化的數(shù)據(jù)處理方法。它的最大特點是能夠建立預(yù)測模型，預(yù)測未來的情況。目前，關(guān)聯(lián)規(guī)則挖掘技術(shù)在各種類型的風(fēng)險分析、資信評估、醫(yī)療診斷決策和市場開發(fā)等諸多領(lǐng)域得到了應(yīng)用。以關(guān)聯(lián)規(guī)則挖掘技術(shù)為基礎(chǔ)的信用卡分析市場規(guī)模已超過2 000億美元。

關(guān)聯(lián)規(guī)則挖掘通常分解為2個主要的子任務(wù)：一是頻繁項集的產(chǎn)生，其目標(biāo)是發(fā)現(xiàn)滿足最小支持度閾值的所有項集；二是規(guī)則的產(chǎn)生，其目標(biāo)是從上一步發(fā)現(xiàn)的頻繁項集中提取所有高置信度的規(guī)則^［1］。通常，頻繁項集產(chǎn)生所需要的計算開銷遠(yuǎn)遠(yuǎn)大于規(guī)則產(chǎn)生所需的計算開銷。

傳統(tǒng)的頻繁項集挖掘算法大多采用水平數(shù)據(jù)格式來存儲項集與事務(wù)集，如經(jīng)典的Apriori^［2］算法。DepthProject ^［3］和MaxMiner^［4］算法也利用這種格式來進行最大頻繁項集的挖掘。后來人們又提出許多性能優(yōu)異的垂直挖掘算法。對于稠密數(shù)據(jù)集，如中國移動的通話記錄，Diffsets^［5］算法表現(xiàn)出良好的性能。Diffsets算法較好地解決了交集計算產(chǎn)生的中間結(jié)果與內(nèi)存容量之間的矛盾。它只保留了候選項之間不同的事務(wù)標(biāo)識號，這種方法極大地減少了中間結(jié)果對內(nèi)存的需求量。本文通過對Diffsets算法的改進，進一步減少了中間計算結(jié)果，進而提高了算法的整體性能。

2 Diffsets算法介紹

2.1 關(guān)聯(lián)規(guī)則挖掘介紹

關(guān)聯(lián)規(guī)則反映的是一個事物與其他事物之間的相互依存性和關(guān)聯(lián)性。如果兩個或者多個事物之間存在一定的關(guān)聯(lián)關(guān)系，那么其中一個事物就能夠通過對其他事物的預(yù)測而得到。典型的關(guān)聯(lián)規(guī)則問題是對超市中的購物籃數(shù)據(jù)進行分析，通過發(fā)現(xiàn)顧客所購不同商品之間的關(guān)系來分析顧客的購買習(xí)慣。

關(guān)聯(lián)規(guī)則定義如下：設(shè)I={i1，i2，…，im}為所有項目的集合，D為事務(wù)數(shù)據(jù)庫，T={t1，t2，…tn}是所有事務(wù)的集合。每個事務(wù)ti包含的項集都是I的子集。每一個事務(wù)都具有惟一的事務(wù)標(biāo)識TID。包含0個或多個項的集合被稱為項集，如果一個項集包含k個項，則稱它為k-項集。項集A在事務(wù)數(shù)據(jù)庫D中出現(xiàn)的次數(shù)占D中總事務(wù)數(shù)的百分比叫作項集的支持度。如果項集的支持度超過用戶給定的最小支持度閾值，就稱該項集是頻繁項集。關(guān)聯(lián)規(guī)則是形如XY的邏輯蘊含式，其中XI，YI，且X∩Y=。如果事務(wù)數(shù)據(jù)庫D中有s%的事務(wù)包含X∪Y，則稱關(guān)聯(lián)規(guī)則XY的支持度為s%。實際上，支持度是一個聯(lián)合概率值。若項集X的支持度記為support(X)，規(guī)則的置信度為support(X∪Y)/support(X)。這是一個條件概率P(Y|X)。也就是：support(XY)=P(X∪Y)，confidence(XY)=P(Y| X)。關(guān)聯(lián)規(guī)則挖掘就是找出支持度和置信度分別滿足用戶給定閾值的規(guī)則。例如數(shù)據(jù)庫中有5個不同的項，I={A，C，D，T，W}，6個事務(wù)T={1，2，3，4，5，6}，如圖1所示。表的右側(cè)列出了在最小支持度為50%時，產(chǎn)生的19個頻繁項集。關(guān)聯(lián)規(guī)則挖掘過程主要分為頻繁項集的產(chǎn)生和規(guī)則的產(chǎn)生，其中頻繁項集產(chǎn)生所需的計算開銷遠(yuǎn)遠(yuǎn)大于規(guī)則產(chǎn)生所需的開銷。

圖1 頻繁項集挖掘

圖2列舉了關(guān)聯(lián)規(guī)則挖掘中事務(wù)數(shù)據(jù)庫常用的數(shù)據(jù)表示格式。在傳統(tǒng)的水平數(shù)據(jù)表示格式中，每個事務(wù)對應(yīng)的項集都存在惟一的事務(wù)標(biāo)識。而垂直數(shù)據(jù)標(biāo)出的是各項在事務(wù)中出現(xiàn)的位置，Eclat^［6］、Charm^［7］和Partion^［8］等算法都是利用此種格式進行數(shù)據(jù)挖掘。

圖2 常用數(shù)據(jù)表示格式

垂直挖掘向?qū)τ谝郧八酵诰蛴泻芏鄡?yōu)勢，其中最大的優(yōu)勢在于它可以只用交集操作就能得到潛在可能的頻繁項集。而傳統(tǒng)的基于水平數(shù)據(jù)格式的挖掘算法需要建立復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。還有一些算法(如Viper^［9］)利用壓縮的二進制格式來代替事務(wù)標(biāo)識。

2.2 垂直數(shù)據(jù)挖掘與Diffsets算法

定義1 等價關(guān)系：I為項集，定義函數(shù)p，P(I)×N→P(I)，其中p(X，k)=X(1∶K)，k是前綴X的長度。在子集樹上定義等價關(guān)系θk：X，Y∈P(I)，X≡θkYp(X，k)=p(Y，k)。也就是說，如果兩個項集享有共同的k長度前綴，它們就是同一個類。θk被稱為基于前綴的等價關(guān)系^［10］。

等價關(guān)系的優(yōu)勢在于它將傳統(tǒng)的搜索空間劃分為一些獨立的子問題，每個帶有前綴的分類都可以作為一個新問題來對待。如果確定了某個前綴類是頻繁的，就可以遞歸地擴展出下面所有的頻繁項集。如對于給定的以P為前綴的類，［P］={X1，X2，…，Xn}是頻繁的，將PXi與所有的Xj進行組合，這樣就可以得到下面所有頻繁的子集。

傳統(tǒng)的垂直挖掘算法(如Viper^［9］)是在兩個頻繁項的事務(wù)標(biāo)識間做交集運算來產(chǎn)生潛在可能的頻繁項集。圖3展示了一個典型的垂直挖掘過程。事務(wù)集A(t(A)={1，3，4，5})，D(t(D)={2，4，5，6})，這時將A和D進行交集運算，得到AD(t(AD)={4，5})。通過支持度計算可知，項集AD不是頻繁項集。在對稠密數(shù)據(jù)集進行挖掘過程中，會產(chǎn)生大量的中間結(jié)果，大量的交集操作將需要許多時間。而當(dāng)結(jié)果達到一定數(shù)量時，又不得不對這些中間結(jié)果進行壓縮，把它存儲到硬盤上。如果遇到這樣的情況，垂直挖掘算法將失去原有的優(yōu)勢。

Diffsets的做法是避免存儲候選項所在的每個事務(wù)標(biāo)識，它只保留了兩個候選項之間的差集。在根部，差集是每個候選項所在的事務(wù)標(biāo)識與整個數(shù)據(jù)集所包含的事務(wù)標(biāo)識的差集。如項A(t(A)={1，3，4，5})，整個事務(wù)的標(biāo)識T為{1，2，3，4，5，6}，這時Diffsets只存儲t(A)與T的差異之處，即{2，6}。通過根部的每個候選項的集合，可以通過計算每兩個項之間的差集來得到所有的子節(jié)點。

圖3 典型垂直挖掘過程

下面是Diffsets形式化的表示方法：

給定一個帶有前綴P的類，令t(X)代表項X所在的事務(wù)標(biāo)識，d(X)代表X的差集，定義d(PX)=t(P)-t(X)，也就是用集合P減去集合P與集合X的交集。同樣的方法，也可以得到d(PY)。這里首先要注意的是項集的支持度已經(jīng)不是差集中所包含的項集個數(shù)與整個事務(wù)數(shù)的比值，而是由如下公式來計算：σ(PX)=σ(P)-|d(PX)|，其中σ代表了項集的支持度計數(shù)，|d(PX)|代表差集PX所包含事務(wù)標(biāo)識的個數(shù)。為了得到σ(PXY)，需遞歸的進行計算。σ(PXY)=σ(PX)-|d(PXY)|，所以需要計算d(PXY)。

根據(jù)定義：

d(PXY)=t(PX)-t(PY)=t(PX)-t(PY)+

t(P)-t(P)

=t(P)-t(PY)-(t(P)-t(PX))

=d(PY)-d(PX)

由上式可知，可以不用t(PX)-t(PY)來計算d(PXY)，而是用d(PY)-d(PX)來計算。

下面舉例說明在在差集的計算過程。從根部開始，如圖4所示，如計算項集AD的支持度。根據(jù)定義可以得到：

d(AD)=t(A)-t(D)={1，3}，σ(AD)

=σ(A)-|d(AD)|=4-2=2

由于用戶定義的最小支持度為50%，而σ(AD)/6=2/6，小于50%，所以得到AD不是頻繁項集。如果以差集計算項集AD的支持度，可以得到d(AD)=d(D)-d(A)={1，3}-{2，6}={1，3}，將和前面得到同樣的計算結(jié)果。惟一不同的是對于稠密數(shù)據(jù)集，如果初始就用差集表示將會占用更少的內(nèi)存空間。再用差集來計算AC的支持度。d(AC)=d(C)-d(A)=-{2，6}=，σ(AC)=σ(A)-|d(AC)|=4-0=4，σ(AC)/6=4/6，大于50%，所以項集AC是頻繁的。

圖4 Diffsets挖掘過程

在圖3中整個數(shù)據(jù)集需要23個事務(wù)標(biāo)識來表示，而在圖4中差集只需要7個事務(wù)標(biāo)識。基于交集運算的垂直挖掘過程共產(chǎn)生76個事務(wù)標(biāo)識，而基于差集的運算只產(chǎn)生22個事務(wù)標(biāo)識。由此可以看出，對于稠密數(shù)據(jù)集，Diffsets算法在一定程度上減少了挖掘過程中產(chǎn)生的中間結(jié)果。

3 Diffsets算法進一步改進

3.1 Diffsets算法改進的思想

在稠密數(shù)據(jù)集中，差集表示法在一定程度上減少了內(nèi)存中需要存儲的事務(wù)標(biāo)識的個數(shù)。但是可以通過對算法的改進，使挖掘過程中產(chǎn)生的結(jié)果更少。

改進算法描述如下：

(1) 計算原始各項差集；

(2) 對于輸入集數(shù)據(jù)，根據(jù)差集中所包含的事務(wù)標(biāo)識個數(shù)按降序進行排列；

(3) 進行正常的差集運算；

(4) 當(dāng)下一層潛在的頻繁項集全部產(chǎn)生后，在內(nèi)存中刪除當(dāng)前層；

(5) 返回步驟2，直到產(chǎn)生所有的頻繁項集。

差集的定義是d(PX)=d(X)-d(P)，假如用短的事務(wù)標(biāo)識集減去長的事務(wù)標(biāo)識集，就可能得到較短的差集。上例中，d(CD)=d(D)-d(C)={1，3}-={1，3}，而d(DC)=d(C)-d(D)=-{1，3}=，從而在內(nèi)存中需存儲的事務(wù)標(biāo)識將更少。所以這里的做法是對每次的輸入集根據(jù)它們所包含的事務(wù)數(shù)長短進行遞減排序，這樣通過差集計算得到的下一層的差集將包含更少的事務(wù)標(biāo)識。證明如下：

令：|D(A)|=Am，|D(B)|=Bn

Am

|D(A)∩D(B)|=t≤min{Am，Bn}

有：

|D(A)-D(B)|=|D(A)-D(A)∩D(B)|

=Am-t

|D(B)-D(A)|=|D(B)-D(A)∩D(B)|

=Bn-t

∵ Am

∴ Am-t

∴ |D(A)-D(B)|<|D(B)-D(A)|

證畢

3.2 算法改進的偽碼及其應(yīng)用舉例

程序的輸入集是可以產(chǎn)生子節(jié)點的一組類成員P。首先對這組類成員P按它們所包含的事務(wù)數(shù)長短進行遞減排序，然后通過計算所有項集對之間的差集和檢查這些差集的支持度，就可以得到所有的頻繁項集。這個過程遞歸的進行調(diào)用，就可以得到當(dāng)前層可能產(chǎn)生的所有頻繁項集。在內(nèi)存中，只需要保存2層事務(wù)標(biāo)識集就可以了，一旦下一層所有潛在的頻繁項集都已產(chǎn)生，就可以刪除當(dāng)前層的數(shù)據(jù)集^［4］。改進算法描述如下：

Input P，smin_support；

Sort P descending according to Tids′ length；//按它們所包含事務(wù)數(shù)的長短遞減排序

for all Xi∈［P］do

for all Xj∈［P］ with j>i do

R={Xi，Xj}；//R為項集Xi和Xj組成的集合

d(R)=d(Xj)-d(Xi)；

if σ(R)≥min_support then

Ti=Ti∪{R}；//Ti初始為空集

New P=Ti；

Delete P；//刪除當(dāng)前層的數(shù)據(jù)集

Return New P；

根據(jù)上面的例子來說明算法改進后的優(yōu)勢，如圖5所示。原來的Diffsets在頻繁項集的挖掘過程中共產(chǎn)生22個事務(wù)標(biāo)識，而改進后的算法在挖掘過程中只產(chǎn)生了14個事務(wù)標(biāo)識。可以看出算法在改進后，在挖掘過程中產(chǎn)生的事務(wù)標(biāo)識數(shù)減少了1/3左右。上例中，如果事先沒有對項集的事務(wù)標(biāo)識列表進行排序，那么d(T)將在d(C)之后，d(T)-d(C)將得到包含2個項的事務(wù)標(biāo)識列表，而排序后得到的結(jié)果為空集。這表明算法改進后不但節(jié)省了更多的存儲空間，還加快了算法的收斂速度。

圖5 改進后的Diffsets挖掘過程

4 結(jié) 語

傳統(tǒng)的垂直挖掘算法是通過對兩個項所包含的事務(wù)標(biāo)識進行交集操作來發(fā)現(xiàn)潛在的頻繁項集。對于稠密數(shù)據(jù)集，其致命的弱點是交集操作可能產(chǎn)生大量的非頻繁項集。這不但需要花費大量的計算時間，而且當(dāng)中間結(jié)果達到一定數(shù)量時，不得不對它們進行壓縮，然后存儲到硬盤上。這將失去垂直挖掘算法原有的優(yōu)勢。Diffsets算法通過利用差集，極大地減少了中間結(jié)果的數(shù)量。本文提出一種改進型Diffsets算法，又進一步減少了挖掘過程中產(chǎn)生的事務(wù)標(biāo)識數(shù)量。通過數(shù)學(xué)證明和與原文例子的比較，展示了算法改進后的優(yōu)勢。

參考文獻

［1］PangNing Tan，Michael Steinbach，Vipin Kumar.數(shù)據(jù)挖掘?qū)д摚跰］.北京:人民郵電出版社，2006.

［2］Agrawal R，Mannila H，Srikant R，et al.Fast Discovery of Association Rules［J］.Advances in Knowledge Discovery and Data Mining，AAAI Press，Menlo Park，CA，1996:307-328.

［3］Rakesh C Agrawal，Charu C Aggarwal，Prasad V V V.Depth First Generation of Long Patterns［J］.In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2000)，2000:108-118.

［4］Bayardo R J.Efficiently Mining Long Patterns from Databases Proc［C］.1998 ACM-SIGMOD Int′l Conf.Management of Data (SIGMOD ′98)，1998:85-93.

［5］Zaki M J，Gouda K.Fast Vertical Mining Using Diffsets［Z］.In Proc.of ACM SIGKDD′03.Washington，DC:2003.

［6］Zaki M J.Scalable Algorithms for Association Mining［J］.IEEE Transactions on Knowledge and Data Engineering，2000，12(3):372-390.

［7］Zaki M J.Generating Non-redundant Association Rules［C］.In 6th ACM SIGKDD Int′l Conf.Knowledge Discovery and Data Mining，2000.

［8］Omiecinsky E，Sarasere A，Navathe S.An Efficient Algorithm for Mining Association Rules in Large Databases［J］.In Proc.of the 21st VLDB Conference，Zurich，Switzerland，1995:432-444.

［9］Shenoy P，Haritsa J R，Sudarshan S，et al.Turbo-charging Vertical Mining of Large Databases［C］.In ACM SIGMOD Intl.Conf.Management of Data，2000.

［10］Zaki M J.Scalable Algorithms for Association Mining［J］.IEEE Transactions on Knowledge and Data Engineering，2000，12(3):372-390.

［11］陳莉平，屈百達.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法的研究與應(yīng)用.現(xiàn)代電子技術(shù)，2007，30(20):71-74.

作者簡介

孫志長 男，1982年出生，遼寧人，碩士研究生。主要研究方向為數(shù)據(jù)挖掘和分布式計算。

馮祖洪 男，1956年出生，江蘇人，教授，碩士生導(dǎo)師。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文