關聯規則挖掘中改進型Ｄｉｆｆｓｅｔｓ算法

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

關鍵詞：數據挖掘；關聯規則挖掘；頻繁項集挖掘；Diffsets

中圖分類號：TP311文獻標識碼：B

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

Improved Diffsets Algorithm in Association Rules Mining

SUN Zhichang，FENG 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 引 言

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

關聯規則挖掘通常分解為2個主要的子任務：一是頻繁項集的產生，其目標是發現滿足最小支持度閾值的所有項集；二是規則的產生，其目標是從上一步發現的頻繁項集中提取所有高置信度的規則^［1］。通常，頻繁項集產生所需要的計算開銷遠遠大于規則產生所需的計算開銷。

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

2 Diffsets算法介紹

2.1 關聯規則挖掘介紹

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

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

圖1 頻繁項集挖掘

圖2列舉了關聯規則挖掘中事務數據庫常用的數據表示格式。在傳統的水平數據表示格式中，每個事務對應的項集都存在惟一的事務標識。而垂直數據標出的是各項在事務中出現的位置，Eclat^［6］、Charm^［7］和Partion^［8］等算法都是利用此種格式進行數據挖掘。

圖2 常用數據表示格式

垂直挖掘向對于以前水平挖掘有很多優勢，其中最大的優勢在于它可以只用交集操作就能得到潛在可能的頻繁項集。而傳統的基于水平數據格式的挖掘算法需要建立復雜的數據結構。還有一些算法(如Viper^［9］)利用壓縮的二進制格式來代替事務標識。

2.2 垂直數據挖掘與Diffsets算法

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

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

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

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

圖3 典型垂直挖掘過程

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

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

根據定義：

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的支持度。根據定義可以得到：

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}，將和前面得到同樣的計算結果。惟一不同的是對于稠密數據集，如果初始就用差集表示將會占用更少的內存空間。再用差集來計算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中整個數據集需要23個事務標識來表示，而在圖4中差集只需要7個事務標識。基于交集運算的垂直挖掘過程共產生76個事務標識，而基于差集的運算只產生22個事務標識。由此可以看出，對于稠密數據集，Diffsets算法在一定程度上減少了挖掘過程中產生的中間結果。

3 Diffsets算法進一步改進

3.1 Diffsets算法改進的思想

在稠密數據集中，差集表示法在一定程度上減少了內存中需要存儲的事務標識的個數。但是可以通過對算法的改進，使挖掘過程中產生的結果更少。

改進算法描述如下：

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

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

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

(4) 當下一層潛在的頻繁項集全部產生后，在內存中刪除當前層；

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

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

令：|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 算法改進的偽碼及其應用舉例

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

Input P，smin_support；

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

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；//刪除當前層的數據集

Return New P；

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

圖5 改進后的Diffsets挖掘過程

4 結 語

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

參考文獻

［1］PangNing Tan，Michael Steinbach，Vipin Kumar.數據挖掘導論［M］.北京:人民郵電出版社，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］陳莉平，屈百達.基于關聯規則的數據挖掘算法的研究與應用.現代電子技術，2007，30(20):71-74.

作者簡介

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

馮祖洪 男，1956年出生，江蘇人，教授，碩士生導師。

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