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

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

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：B

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

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

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

2 Diffsets算法介紹

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

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

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

圖1 頻繁項(xiàng)集挖掘

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

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

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

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

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

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

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

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

圖3 典型垂直挖掘過程

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

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

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

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

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

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

圖4 Diffsets挖掘過程

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

3 Diffsets算法進(jìn)一步改進(jìn)

3.1 Diffsets算法改進(jìn)的思想

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

改進(jìn)算法描述如下：

(1) 計(jì)算原始各項(xiàng)差集；

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

(3) 進(jìn)行正常的差集運(yùn)算；

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

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

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

令：|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 算法改進(jìn)的偽碼及其應(yīng)用舉例

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

Input P，smin_support；

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

for all Xi∈［P］do

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

R={Xi，Xj}；//R為項(xiàng)集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ù)上面的例子來說明算法改進(jìn)后的優(yōu)勢(shì)，如圖5所示。原來的Diffsets在頻繁項(xiàng)集的挖掘過程中共產(chǎn)生22個(gè)事務(wù)標(biāo)識(shí)，而改進(jìn)后的算法在挖掘過程中只產(chǎn)生了14個(gè)事務(wù)標(biāo)識(shí)?？梢钥闯鏊惴ㄔ诟倪M(jìn)后，在挖掘過程中產(chǎn)生的事務(wù)標(biāo)識(shí)數(shù)減少了1/3左右。上例中，如果事先沒有對(duì)項(xiàng)集的事務(wù)標(biāo)識(shí)列表進(jìn)行排序，那么d(T)將在d(C)之后，d(T)-d(C)將得到包含2個(gè)項(xiàng)的事務(wù)標(biāo)識(shí)列表，而排序后得到的結(jié)果為空集。這表明算法改進(jìn)后不但節(jié)省了更多的存儲(chǔ)空間，還加快了算法的收斂速度。

圖5 改進(jìn)后的Diffsets挖掘過程

4 結(jié) 語

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

參考文獻(xiàn)

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

作者簡(jiǎn)介

孫志長(zhǎng) 男，1982年出生，遼寧人，碩士研究生。主要研究方向?yàn)閿?shù)據(jù)挖掘和分布式計(jì)算。

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

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