基于差異點集的頻繁項集挖掘算法

尹 遠，朱璐偉，文 凱

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065；3.重慶信科設(shè)計有限公司， 重慶 401121；4.中國電信股份有限公司 重慶分公司，重慶 401121)

0 引 言

挖掘關(guān)聯(lián)規(guī)則之前最重要且繁瑣的一步是頻繁項集的挖掘，頻繁項集挖掘算法可分為兩種：①水平逐級搜索，例如崔馨月等[1]提出的Eclat改進算法，該算法采用位存儲結(jié)構(gòu)，減少了進行交集運算的項目所占內(nèi)存；宋文慧等[2]提出基于矩陣的Apriori算法(M-Apriori)，該算法將數(shù)據(jù)庫用上三角矩陣表示，可直接獲取頻繁1、2-項集，減少大量項候選項集的產(chǎn)生。②分而治之，例如何晴等[3]提出新的FP-Growth算法，該算法采用改進的哈希頭表代替?zhèn)鹘y(tǒng)FP-Growth頭表，通過合并最小支持度相同的節(jié)點壓縮FP-tree，從而減少建樹所占用的內(nèi)存；李校林等[4]采用B-list結(jié)構(gòu)表示項集，并結(jié)合子父等價修剪策略對搜索空間進行挖掘，時間性能大大提高。

針對傳統(tǒng)閾值設(shè)置過大或過小帶來不理想頻繁項集數(shù)量的影響，Giang等[5]采用Top-rank-k挖掘模式挖掘可擦除項集，并提出一種新的dPID-list結(jié)構(gòu)，減少了節(jié)點信息冗余度。Deng等[6]采用Node-list結(jié)構(gòu)表示項集，并可通過項集交集運算快速獲取項集支持度，提高了算法時間效率。

本文提出的基于差異點集[7]的DNTK算法，采用差異點集結(jié)構(gòu)中特有的差集運算方法，避免了項集間復(fù)雜的連接過程；結(jié)合一種線性時間復(fù)雜度連接方法和早期修剪策略[8]，提出一種更為高效的1-項集連接方法來避免項集節(jié)點間無效連接；采用包含索引策略[9]來減少項集連接次數(shù)。

1 相關(guān)知識

1.1 頻繁項集

定義1k-項集：對于集合P屬于I，稱集合P為一個項集，包含k個項目的項集稱為k-項集。

定義2 頻繁k-項集：對于給定的事務(wù)數(shù)據(jù)庫DB，min-sup為用戶給定的最小支持度，如果sup(X)≥min-sup×|DB|, 則稱X為頻繁項集。如果X為k-項集，則稱為頻繁k-項集。

定義3Top-rank-k頻繁項集：給定一個數(shù)據(jù)集DB和閾值k，當(dāng)且僅當(dāng)RP≤k，項集P稱為Top-rank-k頻繁項集(RP為支持度大于等于項集P支持度的項集個數(shù))。

1.2 差異點集(DiffNodeset)

近些年，許多數(shù)據(jù)結(jié)構(gòu)被提出用來提高挖掘頻繁項集的效率，例如Node-list，N-list[9]和Nodeset[10]。這三者都使用前綴編碼樹來表示項集信息，Nodeset結(jié)構(gòu)與前兩者不同之處在于Nodeset只需用pre-order或post-order來表示項集信息，因此其內(nèi)存消耗較小，但隨著數(shù)據(jù)集的增大，Nodeset的基數(shù)也會隨之變大。針對該問題，本文將差異點集結(jié)構(gòu)運用到Top-rank-k挖掘模式中，該結(jié)構(gòu)所產(chǎn)生基數(shù)較Nodeset要小得多。

定義4 設(shè)L1為按支持度降序排列的頻繁1-項集，對于任何兩個項目i1和i2(i1,i2∈L1)， 我們表示i1

定義5 PP-code：對于PPC-tree中的每一個節(jié)點N，記PPN=[(N.pre-order，N.post-order，N.count)]， 因 (N.pre-order，N.count) 和 (N.post-order，N.count) 都可以表示N節(jié)點，因此這兩種表示方法是等價的。

定義6 1-項集的Nodeset：對于給定的PPC-tree與節(jié)點P,所有名為P的節(jié)點的所有PP-code構(gòu)成的集合稱為其對應(yīng)的Nodeset，記為NSP。其中所有PP-code按pre-order遞增順序排列。

定義7 2-項集的差異點集：設(shè)項目i1和i2(i1i2∈L1∩i1

(1)

性質(zhì)1 設(shè)2-項集i1i2的DiffNodeset為DN12，項集i1i2的支持度表示為

sup(i1i2)=sup(i1)-∑(E∈DN12)E.count

(2)

詳細證明過程請參考文獻[7]。

性質(zhì)2 設(shè)項集P=i1i2i3…ik(ij∈L1且i1

DNP=DN2/DN1

(3)

其中，/表示集合差。

詳細證明過程請參考文獻[7]。

性質(zhì)3 設(shè)項集P=i1i2i3…ik且P1=i1i2…ik-2ik-1， 則項集P的支持度可按以下公式計算

sup(P)=sup(P1)-∑(E∈DNP)E.count

(4)

詳細證明過程請參考文獻[7]。

2 DNTK算法

2.1 改進的1-項集連接方法

早期修剪策略的算法步驟：

(1)分別計算1-項集ix和iy的Nodeset計數(shù)值，并表示為Cx和Cy；

(2)每一步，判定節(jié)點PPz若無父子關(guān)系，需確定PPz屬于1-項集ix的Nodeset還是iy的Nodeset，若屬于ix的Nodeset，更新Cx=Cx-PPz.count， 若屬于iy的Nodeset，更新Cy=Cy-PPz.count；

(3)判定Cx或Cy，若小于閾值，則停止計算并返回空值。

文獻[7]中項集連接方法Build_2-itemset_DN()可將兩個項集的連接線性時間復(fù)雜度降為O(m+n),m和n分別代表兩個項集的Nodeset大小。結(jié)合該項集連接方法和早期修剪策略，本文提出一種更為高效的項集連接算法Improved Build_2-itemset_DN()，該算法在項集連接過程中可及時判斷其連接的可行性，避免了多次無效運算，偽代碼如下：

Procedure Improved Build_2-itemset_DN(ixiy)

(1) DNxy=?；

(2) k=0 and j=0；

(3) Cxbe the count of Nx(Nodesets of ix) and Cybe the count of Ny(Nodesets of iy)； //Cx:ix的支持度

(4) Let m=1;

(5) While k

(6) If Nx[k].post-order> Ny[j].post-order then

(7) Cy=Cy-m*Ny[j++].count；

(8) m=1；

(9) Else

(10) If Nx[k].post-orderNy[j].pre-order then

(11) m=0；

(12) k++;

(13) Else

(14) DNxy←DNxy∪{(Nx[k].post-order，Nx[k].count)}；

(15) Cx=Cx-Nx[k++].count；

(16) m=1；

(17) Endif

(18) Endif

(19) if(Cx

(20) k=Nx.size； //停止繼續(xù)獲取DNxy

(21) return NULL//DNxy返回為空， 且整個循環(huán)結(jié)束

(22) end if

(23) Endwhile

//若返回不為空值， 把ix的剩余節(jié)點都歸為DN(ixiy)

(24) If k

(25) While k

(26) DNxy←DNxy∪{(Nx[k].post-order， Nx[k].count)}；

(27) k++；

(28) Endwhile

(29) Endif

(30) Return DNxy

以文獻[7]中PPC-tree為例，項集e和c的Nodeset分別為 {5,8} 和 {{2,2},{7,1},{10,2}}。 設(shè)閾值為4，首先比較節(jié)點2和節(jié)點5，由于節(jié)點2的前后序編碼分別小于節(jié)點5的前后序編碼，按偽代碼第(13)行，則存在Nx[k].post-order

2.2 基于包含索引的頻繁2-項集挖掘

定義8 頻繁項集A的包含索引表示為subsume(A)，定義為

subsume(A)={B∈I|g(A)?g(B)}

(5)

其中，g(A)表示項集A的事務(wù)集合。

性質(zhì)4 設(shè)項集P包含索引為subsume(P)={p1,p2…pm}， 項集P和集合 {p1,p2…pm} 的任何子集相結(jié)合的支持度等于項集P的支持度。詳細證明過程參考文獻[9]。

性質(zhì)5 設(shè)項集A∈subsume(B),B∈subsume(C), 則項集A∈subsume(C)。 詳細過程參考文獻[9]。

本文將包含索引策略與改進后的1-項集連接方法Improved Build_2-itemset_DN()有效結(jié)合，即先將頻繁1-項集X與其非包含索引子集的1-項集進行結(jié)合獲取候選2-項集，然后利用Improved Build_2-itemset_DN()方法計算其差異點集，因此不需要產(chǎn)生項集X與其包含索引子集結(jié)合的候選2-項集，減少了項集連接次數(shù)，提高了算法時間效率。

2.3 基于包含索引的頻繁k(k>2)-項集挖掘

根據(jù)性質(zhì)2和性質(zhì)3，可直接利用項集的差異點集做差集運算來獲取k(>2)項集的支持度，避免了項集間利用子父關(guān)系進行連接，提高了時間效率。本文將包含索引策略和此差集方法進行有效結(jié)合，不需產(chǎn)生項集與其包含索引子集結(jié)合的候選項集，減少了項集連接次數(shù)，時間效率得到提高。

3 算法描述

DNTK算法具體流程如圖1所示。

圖1 DNTK算法流程

(1)支持度設(shè)為0，獲取所有頻繁1-項集，掃描數(shù)據(jù)庫，建立PPC-tree；

(2)掃描PPC-tree，獲取所有1-項集的Nodeset；

(3)獲取所有1-項集的包含索引；

(4)設(shè)定值k，遍歷每個1-項集并將其插入Top-rank-ktable中，該表中包含項集和支持度，支持度相同的項集在同一個條目中，條目的數(shù)量不超過k，并更新閾值為表中最小支持度；

(5)先遍歷table中每個k-項集Y1，后遍歷前k-1個項目與Y1前k-1個項目相同；最后一個項目與Y1最后一個項目不同且不為Y1的包含索引子集的每個k-項集Y2。若Y1和Y2滿足閾值并且k=1，運用Improved Build_2-itemset_DN(ixiy)方法對項集Y1和Y2進行連接，并將項集Y1Y2的包含索引更新為Y1的包含索引，若兩個項集連接后返回不為空值，將其插入表中，刪除條目值大于k的條目并更新閾值為表中最小支持度。若Y1和Y2滿足閾值并且k>1，將Y1和Y2進行差集運算，并將項集Y1Y2的包含索引更新為Y1的包含索引，若項集Y1Y2的支持度滿足閾值，將其插入表中，刪除條目值大于k的條目并更新閾值為表中最小支持度；

(6)重復(fù)步驟(5)，直到?jīng)]有新的項集產(chǎn)生；

(7)將表中包含索引不為空集的項集與其包含索引每個子集進行結(jié)合產(chǎn)生新的項集，根據(jù)性質(zhì)4，可直接將其插入到Top-rank-ktable中。

4 實驗結(jié)果分析

本文將DNTK*與DNTK算法的運行時間比例在不同數(shù)據(jù)集中作對比(DNTK*為未采用包含索引策略的DNTK算法)，以測試采用了包含索引策略的DNTK算法因減少項集連接次數(shù)所帶來的時間效益。并且本文將DNTK算法與FAE和NTK算法在運行時間和內(nèi)存占用方面進行比較，以驗證該算法的整體性能。用java語言在實驗環(huán)境為Inter(R) Core(TM) i5 3317U @ 1.7GHz CPU，內(nèi)存4 GB，64位操作系統(tǒng)設(shè)備上實現(xiàn)以上算法比較，各組實驗中每種算法所挖掘的頻繁項集數(shù)量和內(nèi)容是相同的，確保了實驗公平性。實驗所用數(shù)據(jù)集為常用數(shù)據(jù)集Retail，Connect，T10I4D100K和T2K50K1D，見表1。實驗通過改變top rank value(k)的大小來測試算法運行時間和內(nèi)存占用的情況。DNTK*算法與DNTK算法的運行時間比例實驗結(jié)果如圖2所示，DNTK算法與FAE和NTK算法的運行時間和內(nèi)存占用對比實驗結(jié)果分別如圖3和圖4所示。

表1 數(shù)據(jù)集參數(shù)

圖2 運行時間比例

圖3 運行時間對比

圖4 內(nèi)存消耗對比

如圖2所示，DNTK*算法與DNTK算法的運行時間比例在Connect和T2K50K1D數(shù)據(jù)集中隨著k值增大而增大，在T2K50K1D數(shù)據(jù)集中運行時，當(dāng)k接近800的時候，DNTK算法時間效率比DNTK*算法快約兩倍。因此可得出以下結(jié)論：采用了包含索引策略的DNTK算法因減少了項集連接次數(shù)，其時間效率得到提高；尤其在k值增大的時候，項集連接減少的次數(shù)會隨之增加。

如圖3所示，3種算法的運行時間都隨著k值增大而增大，在T10I4D100K數(shù)據(jù)集上運行時，DNTK算法的時間效率優(yōu)于FAE和NTK算法尤其是在Table-rank-value(k)越來越大的時候。在數(shù)據(jù)集Retail上運行時，當(dāng)k值接近500的時候，DNTK算法比FAE算法快約5倍，比NTK算法快約3倍。隨著k值越來越小，DNTK算法的時間效率優(yōu)勢也越來越不明顯。如圖4所示，在內(nèi)存消耗方面，這3種算法在不同數(shù)據(jù)集上的內(nèi)存消耗都隨著k值增大而增大，當(dāng)k值較大時，由于差異點集的結(jié)構(gòu)性優(yōu)勢，DNTK算法的內(nèi)存消耗明顯少于FAE和NTK算法。實驗結(jié)果表明DNTK算法在不同類型數(shù)據(jù)集中都有著較高的時間效率與空間效率。

5 結(jié)束語

本文提出一種頻繁模式挖掘算法-DNTK。該算法將一種樹形結(jié)構(gòu)差異點集運用在Top-rank-k挖掘模式中，利用差集運算快速獲取k(>2)項集支持度；結(jié)合Build_2-itemset_DN()項集連接方法和早期修剪策略，本文提出一種更為高效的項集連接方法，該方法可及時發(fā)現(xiàn)項集連接的可行性，提高時間效率；在DNTK算法中引入包含索引策略，減少了項集連接次數(shù)，提高了時間效率。實驗結(jié)果表明DNTK算法在不同的數(shù)據(jù)集中性能優(yōu)于FAE和NTK算法。考慮數(shù)據(jù)集越來越大的情況和當(dāng)前大數(shù)據(jù)環(huán)境，DNTK算法與Spark平臺結(jié)合[11]將會是下一步的研究方向。