一種改進(jìn)的基于N-List的頻繁項(xiàng)集挖掘算法

翟 悅 王 璨 孫建言

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

0 引 言

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

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

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

1 相關(guān)工作

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

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

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

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

每個(gè)結(jié)點(diǎn)N由5 個(gè)域組成，分別是N.item、N.count、N.preorder、N.postorder和N.child。其中，item表示項(xiàng)集；count域記錄了項(xiàng)集的支持?jǐn)?shù)；preorder 域?yàn)榍靶虮闅vPPC樹的序號(hào)；postorder 域?yàn)楹笮虮闅vPPC樹的序號(hào)；child域指向N的孩子結(jié)點(diǎn)。另根結(jié)點(diǎn)root.preorder=0,其余各域值均為null。

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

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

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

2 構(gòu)造哈希表存儲(chǔ)的N-List

2.1 引用哈希表存儲(chǔ)N-List

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

表3 使用哈希表存儲(chǔ)N-List的鍵值

定義3[3]N-List結(jié)點(diǎn)由PPC樹結(jié)點(diǎn)中3個(gè)域組成，表示為ppi=Ni.preorder,Ni.postorder,Ni.count。

由定義4，按照文獻(xiàn)[1]提出的N-List建立方法生成哈希存儲(chǔ)的1-項(xiàng)集N-List如圖2所示。其中每個(gè)1-項(xiàng)集的鏈表結(jié)點(diǎn)按照前序遍歷順序鏈接。

圖2 表2對(duì)應(yīng)的哈希存儲(chǔ)的1-項(xiàng)集的N-List

性質(zhì)1K-項(xiàng)集P對(duì)應(yīng)的N-list為NL(P)={pp1,pp2,…,ppn}

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

例如：鍵值為3的哈希表存儲(chǔ)的{a}存在2個(gè)鏈接結(jié)點(diǎn){(1,1),1},{(4,6),3},按照性質(zhì)1可知1-項(xiàng)集{a}的支持?jǐn)?shù)a.count=1+3=4。

2.2 哈希存儲(chǔ)N-list的鏈接方法

性質(zhì)2假設(shè)?ppi，ppj，當(dāng)且僅當(dāng)ppi.preorder< ppj.preorder，且ppi.postorder>ppj.postorder時(shí)，則稱ppi為ppj的前驅(qū)結(jié)點(diǎn)，記為ppi∝ppj。

例如：ppi={(3,10),5},ppj={(11,7),1},因?yàn)閜pi.preorder=3ppj.postorder=7，所以{(3,10),5}為{(11,7),1}的前驅(qū)結(jié)點(diǎn)，記為ppi∝ppj。

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

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

2) 合并NL(XAB)中前序和后序值相同的結(jié)點(diǎn)。

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

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

3 包含因子與N-List相交運(yùn)算

3.1 包含因子的引入

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

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

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

定理1[10]假設(shè)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(shù)(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交集運(yùn)算

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

證明：由于ppj∝ppi，說明所有包含a的事務(wù)項(xiàng)也都包含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>}結(jié)點(diǎn)為{<(6,2),1>, <(9,9),2>}結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則有c∈subsume(d)。

文獻(xiàn)[7-8]提出NList交集運(yùn)算的方法，算法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 頻繁項(xiàng)集挖掘算法HNSFI

4.1 HNSFI算法步驟描述

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

(1) 建立PPC樹；掃描PPC樹生成頻繁1-項(xiàng)集對(duì)應(yīng)的N-List。

(2) 計(jì)算頻繁1-項(xiàng)集對(duì)應(yīng)的包含因子；調(diào)用包含因子生成算法Gen_subsume()搜索頻繁1-項(xiàng)集對(duì)應(yīng)的包含因子。

(3) 將頻繁1-項(xiàng)集對(duì)應(yīng)的包含因子直接合并生成頻繁2-項(xiàng)集插入結(jié)果中，其支持?jǐn)?shù)與頻繁1-項(xiàng)集相同。

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

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

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

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實(shí)例分析

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

表4 頻繁1-項(xiàng)集對(duì)應(yīng)的包含因子

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

圖4 N-List鏈接生成候選2-項(xiàng)集

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

圖5 HNSFI算法挖掘結(jié)果的生成過程

5 實(shí)驗(yàn)結(jié)果

5.1 定性分析

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

5.2 定量分析

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

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

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

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

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

6 結(jié) 語

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

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