基于差異點(diǎn)集的頻繁項(xiàng)集挖掘算法

尹 遠(yuǎn)，朱璐偉，文 凱

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

0 引 言

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

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

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

1 相關(guān)知識(shí)

1.1 頻繁項(xiàng)集

定義1k-項(xiàng)集：對(duì)于集合P屬于I，稱集合P為一個(gè)項(xiàng)集，包含k個(gè)項(xiàng)目的項(xiàng)集稱為k-項(xiàng)集。

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

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

1.2 差異點(diǎn)集(DiffNodeset)

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

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

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

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

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

(1)

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

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

(2)

詳細(xì)證明過(guò)程請(qǐng)參考文獻(xiàn)[7]。

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

DNP=DN2/DN1

(3)

其中，/表示集合差。

詳細(xì)證明過(guò)程請(qǐng)參考文獻(xiàn)[7]。

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

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

(4)

詳細(xì)證明過(guò)程請(qǐng)參考文獻(xiàn)[7]。

2 DNTK算法

2.1 改進(jìn)的1-項(xiàng)集連接方法

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

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

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

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

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

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返回為空， 且整個(gè)循環(huán)結(jié)束

(22) end if

(23) Endwhile

//若返回不為空值， 把ix的剩余節(jié)點(diǎn)都?xì)w為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

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

2.2 基于包含索引的頻繁2-項(xiàng)集挖掘

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

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

(5)

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

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

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

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

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

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

3 算法描述

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

圖1 DNTK算法流程

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

圖2 運(yùn)行時(shí)間比例

圖3 運(yùn)行時(shí)間對(duì)比

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

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

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

5 結(jié)束語(yǔ)

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