翟 悅 王 璨 孫建言

(大連科技學院信息科學系 遼寧 大連 116052)

0 引 言

頻繁項集挖掘是數(shù)據(jù)挖掘研究中最為突出的任務之一，也是數(shù)據(jù)挖掘中最為耗時的部分，一旦挖掘出所有的頻繁項集，關聯(lián)規(guī)則即可通過簡單的數(shù)學計算得到，可以說頻繁項集挖掘算法的效率直接影響著整個數(shù)據(jù)挖掘的效率，因此十分有必要深入研究頻繁項集挖掘算法。傳統(tǒng)數(shù)據(jù)頻繁項集挖掘算法主要分為兩類: 一類是以Apriori算法為代表的產(chǎn)生候選頻繁項集的挖掘算法，Apriori類算法具有需要重復掃描數(shù)據(jù)庫及產(chǎn)生大量候選項集等缺陷；另一類是FP-growth為代表的采用分而治之策略挖掘頻繁項集算法，該種采用頻繁模式增長類的算法將數(shù)據(jù)壓縮到FP-tree，需要遞歸構建條件FP-tree，時間性能無法保證。

盡管近年來研究者提出諸多改進的頻繁項集挖掘算法，但當事務數(shù)據(jù)庫非常稠密,并且最小支持度設定非常低時, 頻繁項集數(shù)量會隨著其長度呈指數(shù)型增長，頻繁項集挖掘時間復雜度仍然存在下降空間。因此，Deng等[3-4]提出了基于PPC-tree結構的挖掘算法PrePost，利用一種新的數(shù)據(jù)結構N-List，通過N-List的交集運算求得項集支持度，它在頻繁項集挖掘中有很高的效率。Song等[2]提出的包含因子概念提高了頻繁項集的挖掘速度。

本文提出一種借鑒包含因子概念融入PrePost算法，結合兩種策略的優(yōu)勢，給出HNSFI算法。該算法利用哈希表存儲N-List數(shù)據(jù)結構所表示的項集，N-List表示的項集與FP-tree相比擁有較高的壓縮率，哈希表存儲利用空間換時間的方法進一步降低N-List相交運算的時間復雜度，并可根據(jù)性質快速計算項集的支持度，同時結合項集的包含因子概念省略某些情況下N-List相交運算過程。包含因子及其相關定理可直接生成頻繁項集，當數(shù)據(jù)集比較稠密時，包含因子的生成時間代價遠遠小于大量N-List相交運算以及支持度計算時間，因此本文算法特別適合應用在稠密數(shù)據(jù)庫。

1 相關工作

設I={i1,i2,…,in}是n個不同項目的集合，如果對一個集合X，有:X?I且k=|X|，則X稱為k項集。記D為事務T的集合，T?I。對于如表1所示給定事務數(shù)據(jù)庫D共有n條記錄, 包含項集X的事務集合記為g(X)={t∈D|?i∈X,i∈t},集合X的支持數(shù)為D中包含X的事務個數(shù)，記為X.count；X的支持度為sup(X)=X.count/n，用戶可自定義一個最小支持度,記為minsup[5]。

表1 事務數(shù)據(jù)庫D

定義1[11]給定事務數(shù)據(jù)庫D和minsup，對于項集X?I，若sup(X)≥minsup，則稱X為D中的頻繁項集。

定義2[1]PPC樹定義如下：

每個結點N由5 個域組成，分別是N.item、N.count、N.preorder、N.postorder和N.child。其中，item表示項集；count域記錄了項集的支持數(shù)；preorder 域為前序遍歷PPC樹的序號；postorder 域為后序遍歷PPC樹的序號；child域指向N的孩子結點。另根結點root.preorder=0,其余各域值均為null。

如表1所示數(shù)據(jù)，對每個事物項按照出現(xiàn)頻度降序排列，如表2所示，根據(jù)文獻[3]提出的prepost算法生成PPC樹如圖1所示。

表2 按事物項出現(xiàn)頻度降序排列事務數(shù)據(jù)庫D

圖1 事務數(shù)據(jù)庫D生成的PPC樹

2 構造哈希表存儲的N-List

2.1 引用哈希表存儲N-List

本文提出利用2級的哈希表存儲N-List，這樣可以加快N-List相交計算的運算速度，改進文獻[3]提出N-List交集算法性能。為了避免1級哈希表在鍵值上的沖突，本文設置2級的哈希表結構如下：1)第1級，使用項目集的長度定為鍵值；2)第2級，項目集中包含的各個項的鍵值累加和作為新鍵值存儲；為了進一步避免不同的項目級對應的鍵值產(chǎn)生沖突，本文使用素數(shù)序列作為1-項集的鍵值Key。如表3中列出1-項集的鍵值序列為素數(shù)序列，2-項集中項集ab的鍵值計算為：Key(a)+Key(b)=3+5=8。

表3 使用哈希表存儲N-List的鍵值

定義3[3]N-List結點由PPC樹結點中3個域組成，表示為ppi=Ni.preorder,Ni.postorder,Ni.count。

由定義4，按照文獻[1]提出的N-List建立方法生成哈希存儲的1-項集N-List如圖2所示。其中每個1-項集的鏈表結點按照前序遍歷順序鏈接。

圖2 表2對應的哈希存儲的1-項集的N-List

性質1K-項集P對應的N-list為NL(P)={pp1,pp2,…,ppn}

可知P.count=pp1.count+pp2.count+…+ppn.count

例如：鍵值為3的哈希表存儲的{a}存在2個鏈接結點{(1,1),1},{(4,6),3},按照性質1可知1-項集{a}的支持數(shù)a.count=1+3=4。

2.2 哈希存儲N-list的鏈接方法

性質2假設?ppi，ppj，當且僅當ppi.preorder< ppj.preorder，且ppi.postorder>ppj.postorder時，則稱ppi為ppj的前驅結點，記為ppi∝ppj。

例如：ppi={(3,10),5},ppj={(11,7),1},因為ppi.preorder=3ppj.postorder=7，所以{(3,10),5}為{(11,7),1}的前驅結點，記為ppi∝ppj。

定義5假設XA與XB是兩個前綴同為X的k-1項集，由其對應的NL(XA)與NL(XB)合并生成k-項集的N-list的步驟如下：

1) ?ppXA∈NL(XA), ?ppXB∈NL(XB),如果ppXA∝ppXB，則生成結點(ppXA.pre,ppXA.post,ppXB.count)∈NL(XAB)。

2) 合并NL(XAB)中前序和后序值相同的結點。

由定義5可知，NL(c)={(3，10)，5}，NL(d)={<(6,2),1>,<(9,9),2>},NL(cd)生成過程如圖3所示。根據(jù)性質2可知結點{(3,10),5}為結點{(6,2),1}的前驅結點，因此將結點{(3,10)，1}插入NL(cd)中，同理結點{(3,10),5}∝{(9,9),2}，故{(3,10)，2}也同樣插入NL(cd)中。

圖3 N-list合并生成cd的過程

3 包含因子與N-List相交運算

3.1 包含因子的引入

定義6[6]假設i為一個項目集，如果存在另一個項目集j,使得滿足j∈I，且g(i)?g(j),則稱j為i的一個包含因子，記為subsume(i)。例如：g(b)={1,2,4},g(a)={1，2，3，4},因為g(b)?g(a),故subsume(b)=a。

性質3假設項集x的包含因子subsume(x)={a1,a2,…，am},由x與其包含因子合并生成的2m-1個非空子集的支持數(shù)均為x.count。

例如：subsume(b)=a，那么無需進行進一步計算即可得知：b.count=ab.count=3。

定理1[10]假設a，b，c∈I1，如果a∈subsume(b)，且b∈subsume(c)，則有a∈subsume(c)。

證明：由于a∈subsume(b)，b∈subsume(c),根據(jù)定義6可知g(b)?g(a),g(c)?g(b)。必然有g(c)?g(a)。因此得出a∈subsume(c)。

包含因子生成算法Gen_subsume()描述如下：

Gen_subsume(I1)

1：for i=1 to |I1|

2: for j=i-1 to 0

3: if j∈i1[i].subsume continue

4: if checkSubsume(I1[i].NL,i1[j].NL)==true

5: 添加I1[j].item和其索引j到I1[i].subsume中

6: 將I1[j].subsume元素添加到I1[i].subsume中

//根據(jù)定理2

checkSubsume(NL(a),NL(b))

//根據(jù)定理1

1: while j<|a| && i<|b| do

2:if b[i].preorder

b[i].postorder>a[j].postorder then j++

3: else i++

4:if j==|a| return true

5:else return false

3.2 N-List交集運算

定理2假設a為頻繁1-項集I1，如果?ppi∈NL(a), ppj∈NL(b)，都有ppj∝ppi, 則有b∈ subsume(a)。

證明：由于ppj∝ppi，說明所有包含a的事務項也都包含b，可知g(b)?g(a)，因此得出b∈subsume(a)

例如：NL(c)={<(3,10),5>}, NL(d)={<(6,2),1>,<(9,9),2>},根據(jù)定理1，滿足{<(3,10),5>}結點為{<(6,2),1>, <(9,9),2>}結點的前驅結點，則有c∈subsume(d)。

文獻[7-8]提出NList交集運算的方法，算法NL_intersection ()描述如下：

Function NL_intersection(NL1,NL2)

1:NL3=? i=0,j=0

2:while i<|NL1| and j<|NL2|

3:if NL1[i].preorder

4: if NL1[i].postorder

5: NL3.add(NL1[i].preorder, NL1[i].postorder, NL2[j].count)

6： else j++

7: else i++

8:return NL3

4 頻繁項集挖掘算法HNSFI

4.1 HNSFI算法步驟描述

基于哈希存儲的N-List與包含因子的頻繁模式挖掘算法包括以下5個步驟：

(1) 建立PPC樹；掃描PPC樹生成頻繁1-項集對應的N-List。

(2) 計算頻繁1-項集對應的包含因子；調用包含因子生成算法Gen_subsume()搜索頻繁1-項集對應的包含因子。

(3) 將頻繁1-項集對應的包含因子直接合并生成頻繁2-項集插入結果中，其支持數(shù)與頻繁1-項集相同。

(4) 合并生成候選2-項集。使用X與不屬于其包含因子的其他頻繁1-項集合并生成候選2-項集，選擇滿足最小支持度條件的插入結果中。

(5) 針對每個頻繁2-項集計算包含因子，將X與其包含因子根據(jù)性質3合并能生成2m-1個項集直接插入結果中。然后再生成候選3-項集，選擇選擇滿足最小支持度條件的插入結果中。

(6) 重復步驟4和步驟5，生成頻繁t-項集。直到不再有新的候選t+1頻繁模式生成算法結束。

HNSFI算法描述如下：

HNSFI (DB)

1:call function create-ppc-tree()

2:create frequent 1-pattern N-List of I1

3:call Gen_subsume(),find the subsume of each item in I1

4: insert frequent-1-pattern and combined with 2m-1 subset from subsume into Lattice

5: for(i=1;Lj-1≠?;j++)

6:CIj← gen_candidate(Lj-1)

7: for c∈CIj,C is generated by p1 and p2

8: C.NL←NL-interseaction(p1.NL,p2.NL);

9: if c.count≥ minsup*n

10: insert c into Lattice

11: if c.subsume≠?

12：insert each subset from c.subsume into lattice

Function gen_candidate (Lj-1)

1: CIj=?

2: for each Cu∈Lj-1

3: for each Cv∈Lj-1(Cu≠Cv)

4: if(Cv[1]?Cu.subsume )and (Cv[1] ≠Cu[1]&& Cv[2] ≠Cu[2]&&…&& Cv[j-1] ≠Cu[j-1])

5: then C← Cu[1] Cv[1] …Cu[j-1]Cv[j-1]

6: C.subsume.add(Cu.subsume)

7: if each (j-1)-subset of C belongs to Lj-1then

8: CIj←CIj∪{C}

9:return CIj

4.2 HNSFI實例分析

以表1數(shù)據(jù)為例，minsup=30%，圖1為其對應的PPC樹，掃描PPC樹生成頻繁1-項集N-list，并按照2.1節(jié)所示存儲方法進行Hash存儲結果如圖2所示，因為1-項集{f}不滿足minsup，故不存儲該結點。將搜索完成的頻繁1-項集{c}、{a}、、rdxflp5、{e}按照支持數(shù)從大到小插入如圖3所示結果的第一層中，調用算法Gen_subsume()搜索頻繁1-項集所對應的包含因子如表4所示。

表4 頻繁1-項集對應的包含因子

由性質3可知結點{ba，dc，ec}可無需計算直接插入結果第二層結點中，由包含因子直接生成的結點插入結果使用虛線表示。然后由1-項集結點與不屬于包含因子的其他頻繁1-項集通過N-List鏈接生成候選2-項集為{ac，bc，da，db，ea，eb，ed}，鏈接過程如圖4所示。鏈接過程中由于使用的哈希存儲能夠縮減候選項集的生成時間，其中滿足minsup的頻繁2-項集為{ca，cb，ae}，將此3個結點插入結果中，使用實線表示。

圖4 N-List鏈接生成候選2-項集

接下來調用算法Gen_subsume()計算2-項集的包含因子，bc.subsume=a,ea.subsume=c, 由性質3直接生成結點{cab,cae}插入結果中，尋找3-項集的候選項集，發(fā)現(xiàn)無候選3-項集生成，算法結束。算法最終的執(zhí)行結果如圖5所示。由圖5可得出本文HNSFI算法無需存儲與計算N-list中的結點{ab,cd,ec,cab,cae},這些結點均使用包含因子直接生成從而大大減少了算法的運行時間。

圖5 HNSFI算法挖掘結果的生成過程

5 實驗結果

5.1 定性分析

本文提出的HNSFI算法通過使用二級哈希表存儲N-list頭結點，引入素數(shù)序列為項集設置鍵值不易發(fā)生沖突，盡管由此帶來了一些空間上的代價，但取出任意N-List頭結點的時間復雜度為O(1)。文獻[9]提出了改進的N-list交集運算，對于任意的兩個N-List鏈，交集運算的時間復雜度已由O(m×n)下降到O(m+n)，其中m、n為兩條N-List鏈的長度。而本文提出的HNSFI算法使用了文獻[6]提出的包含因子概念，該算法無需遍歷N-List中所有的頭結點，在某些情況下可通過包含因子直接生成頻繁項集。

5.2 定量分析

為了進一步驗證算法的時間性能，我們主要比較本文HNSFI算法與文獻[3]所提到的PrePost算法之間在運行時間上的性能差異。測試的硬件平臺為：Intel Core i7-4510 CPU 2 GHz、16 GB 內存。兩個算法均采用Java編程語言實現(xiàn)，實驗數(shù)據(jù)使用從 http://fimi.ua.ac.be/ data/下載上獲得的Chess、Retail和mushroom3個數(shù)據(jù)集進行頻繁項集挖掘實驗，其中chess數(shù)據(jù)庫共有75個不同的項，3 196個事務，Retail數(shù)據(jù)庫共有16 470個不同的項，88 162個事務。Mushroom數(shù)據(jù)庫共有119個不同的項，8 124個事務。運行時間的實驗結果如圖6-圖8所示。

圖6 retail數(shù)據(jù)庫兩種算法執(zhí)行時間對比

圖7 chess數(shù)據(jù)庫的兩種算法執(zhí)行時間對比

圖8 mushroom數(shù)據(jù)庫的兩種算法執(zhí)行時間對比

由圖6所示的對比結果可以發(fā)現(xiàn)，本文提出的HNSFI算法針對于類似Retail數(shù)據(jù)庫這種擁有較少頻繁項目集的稀疏數(shù)據(jù)庫，時間耗費大于PrePost算法，因為本文引入的查找包含因子需要計算時間，而對于有較少項集的稀疏數(shù)據(jù)庫來說通過包含因子直接生成項集節(jié)省的時間小于計算包含因子的時間。而針對chess與mushroom這兩個數(shù)據(jù)庫，由于哈希表使用以及包含因子的計算可以減少頻繁項集挖掘時間，如圖7-圖8所示，針對于稠密數(shù)據(jù)庫，包含因子直接生成的頻繁項集能夠大大節(jié)省時間使得因子計算的時間可以忽略不計。通過實驗可以得知本文提出的HNSFI算法對于稠密數(shù)據(jù)庫，算法執(zhí)行具有一定的穩(wěn)定性，隨著minsup不斷降低，本文HNSFI算法有明顯的優(yōu)勢。

6 結 語

本文提出了一種高效地利用N-List生成頻繁項集的方法。與文獻[9-12]提出的眾多PrePost改進方法方法不同，HNSFI算法特點為：1)使用了哈希表存儲N-List結構，從而進一步加快了通過N-List相交生成頻繁項集的速度。2)通過引入包含因子以及其相關性質可以在某些情況下省去對N-List的鏈接操作直接生成頻繁項目集。HNSFI算法盡管在稀疏數(shù)據(jù)庫中的性能比不上PrePost，但針對與稠密數(shù)據(jù)庫的時間性能具有優(yōu)勢。

在今后的研究工作中可以考慮將本文算法推廣到挖掘頻繁閉項集[14]或加權頻繁項集[15]中，可以為每個項目引入帶有某種含義的權值，使算法挖掘的結果更具參考價值。此外還可以借助分布式計算的思想，研究并行處理條件下頻繁項集增量挖掘[16]，從而提高頻繁項集挖掘的工作效率擴寬應用范圍。