趙學(xué)健，熊肖肖，張欣慧，孫知信

(1.南京郵電大學(xué) 現(xiàn)代郵政學(xué)院，江蘇 南京 210003;2.南京郵電大學(xué) 物聯(lián)網(wǎng)學(xué)院，江蘇 南京 210023)

1 概 述

近年來，數(shù)據(jù)挖掘技術(shù)在各行各業(yè)的決策支持活動(dòng)中扮演著越來越重要的角色。頻繁項(xiàng)集挖掘作為數(shù)據(jù)挖掘最活躍的研究領(lǐng)域之一，是指發(fā)現(xiàn)事務(wù)數(shù)據(jù)中頻繁出現(xiàn)的模式的過程，是發(fā)現(xiàn)大型事務(wù)數(shù)據(jù)集中關(guān)聯(lián)規(guī)則的重要手段，在精準(zhǔn)營銷、個(gè)性化推薦、網(wǎng)絡(luò)優(yōu)化與管理、醫(yī)療診斷等領(lǐng)域均有廣泛的應(yīng)用[1]。當(dāng)前，針對確定性數(shù)據(jù)的頻繁模式挖掘理論日趨成熟，然而隨著信息采集技術(shù)和數(shù)據(jù)處理技術(shù)的快速發(fā)展，各種形式復(fù)雜的數(shù)據(jù)逐漸出現(xiàn)在人們面前，不確定數(shù)據(jù)就是其中之一。

不確定數(shù)據(jù)是指每一條事務(wù)中項(xiàng)目的存在不再是百分百確定的，而是依據(jù)某種相似性度量或是概率形式存在。不確定數(shù)據(jù)主要是由于數(shù)據(jù)本身的特點(diǎn)或者數(shù)據(jù)在產(chǎn)生、收集、存儲(chǔ)和傳輸過程中存在大量隨機(jī)性導(dǎo)致的，比如說通過對購物籃分析從而預(yù)測商品需求量時(shí)，購物籃中的商品用戶并不是肯定要購買的。目前，不確定數(shù)據(jù)廣泛應(yīng)用于傳感器網(wǎng)絡(luò)、RFID應(yīng)用、Web應(yīng)用、商業(yè)決策等諸多領(lǐng)域[2]。

數(shù)據(jù)的不確定性給頻繁模式挖掘帶來了極大挑戰(zhàn)，一方面是相對于數(shù)據(jù)規(guī)模呈指數(shù)增長的可能世界實(shí)例的數(shù)量，另一方面是新出現(xiàn)的概率維度，這導(dǎo)致傳統(tǒng)的針對確定性數(shù)據(jù)的頻繁模式挖掘算法的準(zhǔn)確性和時(shí)效性大大降低，不能滿足具體的應(yīng)用需求。因此，迫切需要提出新的理論模型和算法解決不確定數(shù)據(jù)的頻繁模式挖掘問題。

但是，當(dāng)前面向不確定數(shù)據(jù)的頻繁項(xiàng)集挖掘研究尚處于研究的初始階段，大多數(shù)研究都假設(shè)事務(wù)數(shù)據(jù)庫中的項(xiàng)目具有相同的重要性。然而，現(xiàn)實(shí)應(yīng)用中對于用戶來講，往往不同的項(xiàng)目其重要性和價(jià)值是有巨大差別的，比如在商品銷售過程中價(jià)格昂貴的奢侈品和價(jià)格低廉的生活用品所帶來的利潤是不可同日而語的。

為了解決該問題，最有效的辦法是給不同的項(xiàng)目賦予不同的權(quán)重值。權(quán)重值可以由用戶根據(jù)專業(yè)領(lǐng)域知識或者特定應(yīng)用需求進(jìn)行設(shè)定，可以用來表示項(xiàng)目的利潤、風(fēng)險(xiǎn)、代價(jià)等。這樣一來，頻繁項(xiàng)集的挖掘就能夠兼顧項(xiàng)目的權(quán)重和存在概率，從而克服了傳統(tǒng)頻繁項(xiàng)集挖掘算法只考慮項(xiàng)目的存在概率，容易遺漏大量具有重要潛在價(jià)值的頻繁項(xiàng)集的問題。然而，項(xiàng)目權(quán)重值的引入使得頻繁項(xiàng)集不再滿足向下閉包特性，也就是說即使某項(xiàng)集是非頻繁項(xiàng)集，其超集仍有可能是頻繁項(xiàng)集。這給頻繁項(xiàng)集的挖掘帶來了巨大挑戰(zhàn)，因?yàn)椴荒茉俑鶕?jù)向下封閉特性對頻繁項(xiàng)集的搜索空間進(jìn)行壓縮。

針對不確定數(shù)據(jù)的加權(quán)頻繁項(xiàng)集挖掘問題，兼顧項(xiàng)目的權(quán)重和存在概率，文中提出一種Top-K加權(quán)頻繁項(xiàng)集挖掘算法(Top-K Frequent Itemset Mining，TK-FIM)，以提高算法的時(shí)間效率，有利于迅速找出對用戶具有重要價(jià)值和意義的頻繁項(xiàng)集。

2 相關(guān)工作

2.1 不確定數(shù)據(jù)頻繁項(xiàng)集挖掘算法

面向不確定數(shù)據(jù)的頻繁項(xiàng)集挖掘算法大致可分為基于Apriori算法[3]的頻繁項(xiàng)集挖掘算法和基于FP-growth算法[4]的頻繁項(xiàng)集挖掘算法兩大類。

Chui等在傳統(tǒng)Apriori算法的基礎(chǔ)上提出了不確定數(shù)據(jù)的頻繁模式挖掘算法U-Apriori[5]，U-Apriori算法同樣需要多次掃描數(shù)據(jù)庫，并會(huì)產(chǎn)生大量的候選頻繁模式。文獻(xiàn)[6]對U-Apriori算法做了進(jìn)一步改進(jìn)，提出了MBP算法，實(shí)驗(yàn)結(jié)果表明MBP算法無論在時(shí)間上還是空間上都優(yōu)于U-Apriori算法。文獻(xiàn)[7]將不確定數(shù)據(jù)的概率頻繁模式模型加入到MBP算法中，進(jìn)而提出了IMBP算法，該算法能夠得到比較準(zhǔn)確的不確定數(shù)據(jù)頻繁項(xiàng)集挖掘結(jié)果，而且數(shù)據(jù)挖掘效率得到了進(jìn)一步提升。文獻(xiàn)[8]將Apriori算法與啟發(fā)式算法進(jìn)行結(jié)合，提出了GA-Apriori算法和PSO-Apriori算法，大大提高了頻繁項(xiàng)集的挖掘效率，但是這兩種算法不能精確地挖掘出不確定數(shù)據(jù)集中的所有頻繁項(xiàng)集。

Leung等提出了基于樹的UF-growth算法[9]，該算法大大加快了不確定數(shù)據(jù)頻繁項(xiàng)集挖掘算法的運(yùn)行速度。然而相對于FP-growth算法來說，UF-growth算法在建樹過程中項(xiàng)目的合并條件更為苛刻，導(dǎo)致了UF-growth算法需要耗費(fèi)大量的內(nèi)存空間。文獻(xiàn)[10]提出了基于樹的不確定數(shù)據(jù)頻繁項(xiàng)集挖掘算法UFP-growth，該算法在挖掘過程中會(huì)產(chǎn)生大量條件模式樹，相應(yīng)的計(jì)算量也會(huì)大大增加。Lin等提出了CUFP-Mine算法[11]，該算法將所有事務(wù)項(xiàng)壓縮到CUFP-tree上，在構(gòu)建CUFP-tree樹的過程中，如果插入項(xiàng)已在樹中，將此項(xiàng)的期望支持度累加，并且計(jì)算此項(xiàng)超集的期望支持度；否則，創(chuàng)建新的節(jié)點(diǎn)并加入到相應(yīng)路徑尾端，存入此項(xiàng)的期望支持度及其超集的期望支持度。Length等提出了基于上界的不確定數(shù)據(jù)頻繁模式增長算法CUF-Growth[12]，以及基于前綴上界的不確定數(shù)據(jù)頻繁模式增長算法PUF-Growth[13]。這兩種算法雖然可以構(gòu)建結(jié)構(gòu)更加壓縮的樹結(jié)構(gòu)，減少了對內(nèi)存空間的占用，但是仍然需要通過探索、合并的方式發(fā)現(xiàn)概率頻繁項(xiàng)集，導(dǎo)致發(fā)現(xiàn)概率頻繁項(xiàng)集耗時(shí)較多。文獻(xiàn)[14]提出的TPC-growth算法在PUF-growth算法的基礎(chǔ)上進(jìn)行了改進(jìn)，采用過估計(jì)的方法使上界更加逼近期望支持度，但是該算法仍不能從給定的不確定數(shù)據(jù)庫中提取出精確的頻繁模式。文獻(xiàn)[15]在分析當(dāng)前基于樹結(jié)構(gòu)的頻繁項(xiàng)集挖掘算法的基礎(chǔ)上，提出一種基于列表的數(shù)據(jù)結(jié)構(gòu)和修剪技術(shù)，該算法可以準(zhǔn)確地挖掘不確定數(shù)據(jù)集中的頻繁項(xiàng)集，并且具有較高的效率。文獻(xiàn)[16]提出一種新的算法SRUF-mine用于挖掘流頻繁項(xiàng)集，理論和實(shí)驗(yàn)結(jié)果表明SRUF-mine算法是一種有效的挖掘不確定性數(shù)據(jù)流頻繁項(xiàng)集的算法，具有良好的時(shí)空效率和擴(kuò)展性。

2.2 加權(quán)頻繁項(xiàng)集挖掘算法

在頻繁項(xiàng)集挖掘的過程中，引入權(quán)重的概念，有利于從海量數(shù)據(jù)中挖掘出對用戶真正有意義，有價(jià)值的信息。因此，針對加權(quán)頻繁項(xiàng)集挖掘算法的研究近年來引起了研究人員的廣泛關(guān)注。

Abraham等基于頻繁模式增長范式對加權(quán)事務(wù)數(shù)據(jù)庫進(jìn)行分析，并提出了用于加權(quán)頻繁項(xiàng)集挖掘的FWIHT(frequent weighted itemset mining using homologous transaction)算法和用于稀有頻繁項(xiàng)集挖掘的RWIHT(rare weighted itemset mining using homologous transaction)算法[17]。Baralis等將單樣本基因的表達(dá)值作為權(quán)重，提取加權(quán)頻繁項(xiàng)集，發(fā)現(xiàn)基因間的關(guān)聯(lián)性，避免了對基因數(shù)據(jù)庫分析的離散化過程，從而提高了基因分析的效率[18]。Lee等提出一種用于動(dòng)態(tài)數(shù)據(jù)庫的基于樹的可刪除項(xiàng)集挖掘算法，算法考慮了不同項(xiàng)目的權(quán)重因素，并采用樹和列表數(shù)據(jù)結(jié)構(gòu)輔助挖掘，有利于有效地執(zhí)行挖掘操作[19]。

上述算法均是針對二元數(shù)據(jù)庫的加權(quán)頻繁項(xiàng)集挖掘問題提出的有效算法，但是針對不確定數(shù)據(jù)庫的加權(quán)頻繁項(xiàng)集挖掘問題研究尚未引起重視，研究成果極少。Lin等最近提出了用于不確定數(shù)據(jù)庫加權(quán)頻繁項(xiàng)集挖掘的HEWI-Uapriori算法[20]，該算法使用帶上限的期望加權(quán)向下閉包特性對非頻繁項(xiàng)集進(jìn)行縮減，以提高算法的時(shí)間效率。

3 相關(guān)定義與問題描述

3.1 相關(guān)定義

假設(shè)D是待挖掘的不確定數(shù)據(jù)庫，數(shù)據(jù)庫D中包含一組事務(wù)集合，即D={T1,T2,…,Tm}，并且每個(gè)事務(wù)包含一個(gè)特定的事務(wù)號TID。數(shù)據(jù)庫D中包含的項(xiàng)目集合為I={I1,I2,…,In}，則有Tq?I，1≤q≤m。數(shù)據(jù)庫D中，每個(gè)事務(wù)Tq中的項(xiàng)目Ij,1≤j≤n都對應(yīng)一個(gè)確定的存在概率，記為p(Ij,Tq)，表示項(xiàng)目Ij在事務(wù)Tq中出現(xiàn)的概率。此外，數(shù)據(jù)庫D中的每個(gè)項(xiàng)目Ij都對應(yīng)一個(gè)權(quán)重值wj，項(xiàng)目集合I中的所有項(xiàng)目對應(yīng)的權(quán)重值構(gòu)成權(quán)重向量w={w1,w2,…,wn}。如果項(xiàng)集X包含k個(gè)不同的項(xiàng)目，稱項(xiàng)目X為k項(xiàng)集。如果X?Tq，稱項(xiàng)集X出現(xiàn)在事務(wù)Tq中。為了進(jìn)行加權(quán)頻繁項(xiàng)集的挖掘，需要事先給出最小期望加權(quán)支持度閾值ε，為加權(quán)頻繁項(xiàng)集的判定提供依據(jù)。文中給出的不確定數(shù)據(jù)庫D包含10個(gè)事務(wù)，分別為T1-T10，包含4個(gè)項(xiàng)目為A-D。

定義1(項(xiàng)目權(quán)重)：項(xiàng)目權(quán)重是用戶根據(jù)喜好或?qū)I(yè)知識設(shè)置的用于描述項(xiàng)目重要性的值，項(xiàng)目Ij的權(quán)重值記為w(Ij)，w(Ij)∈(0,1]。

定義2(項(xiàng)集權(quán)重)：項(xiàng)集X的權(quán)重為該項(xiàng)集所包含各項(xiàng)目權(quán)重的平均值，記為w(X)：

(1)

其中，|k|為項(xiàng)集X所包含的項(xiàng)目數(shù)量。

定義3(項(xiàng)集在事務(wù)中的出現(xiàn)概率)：項(xiàng)集X在事務(wù)Tq中的出現(xiàn)概率記為p(X,Tq)，等于項(xiàng)集中各項(xiàng)目在事務(wù)Tq中出現(xiàn)概率的乘積。

即：

(2)

其中，Ij為項(xiàng)集X的第j個(gè)項(xiàng)目。

定義4(項(xiàng)集的期望支持度)：項(xiàng)集X在不確定數(shù)據(jù)庫D中的期望支持度記為expSup(X)，等于項(xiàng)集X在包含該項(xiàng)集的所有事務(wù)中的出現(xiàn)概率之和。

即：

定義5(頻繁項(xiàng)集)：在不確定數(shù)據(jù)庫D中，當(dāng)項(xiàng)集X的期望支持度大于等于最小期望支持度時(shí)(最小期望支持度為最小期望支持度閾值δ與數(shù)據(jù)庫D中所包含事務(wù)數(shù)的乘積)，則項(xiàng)集X為頻繁項(xiàng)集，記為FIS。即當(dāng)expSup(X)≥δ×|D|時(shí)，項(xiàng)集X為頻繁項(xiàng)集。

定義6(項(xiàng)集的期望加權(quán)支持度)：項(xiàng)集X在不確定數(shù)據(jù)庫D中的期望加權(quán)支持度記為expwSup(X)，等于項(xiàng)集X的期望支持度與項(xiàng)集X的權(quán)重的乘積，即：

(4)

定義7(加權(quán)頻繁項(xiàng)集)：在不確定數(shù)據(jù)庫D中，當(dāng)項(xiàng)集X的加權(quán)期望支持度大于等于最小期望加權(quán)支持度時(shí)(最小期望加權(quán)支持度為最小期望加權(quán)支持度閾值ε與數(shù)據(jù)庫D中所包含事務(wù)數(shù)的乘積)，則項(xiàng)集X為加權(quán)頻繁項(xiàng)集，記為加權(quán)頻繁項(xiàng)集WFIS。即當(dāng)expwSup(X)≥ε×|D|時(shí)，項(xiàng)集X為加權(quán)頻繁項(xiàng)集。

3.2 問題描述

根據(jù)上述定義，對不確定數(shù)據(jù)庫中加權(quán)頻繁項(xiàng)集挖掘問題可進(jìn)行如下形式化描述。在不確定數(shù)據(jù)庫D中，若用戶給定了數(shù)據(jù)庫中各元素的權(quán)重w和最小期望加權(quán)支持度閾值ε，挖掘加權(quán)頻繁項(xiàng)集即判斷項(xiàng)集X是否滿足expwSup(X)≥ε×|D|的過程。加權(quán)頻繁項(xiàng)集的挖掘綜合考慮了項(xiàng)目的權(quán)重和存在概率因素，因此得到的加權(quán)頻繁項(xiàng)集對用戶來說具有更好的價(jià)值和意義。

但是，通過分析，對于加權(quán)頻繁項(xiàng)集的挖掘，向下閉包特性已經(jīng)不再適用，這增大了加權(quán)頻繁項(xiàng)集挖掘的難度和時(shí)空復(fù)雜度。

因此，提高挖掘算法的時(shí)空效率是加權(quán)頻繁項(xiàng)集挖掘算法需要實(shí)現(xiàn)的首要目標(biāo)。

4 TK-FIM算法

為了提高頻繁項(xiàng)集挖掘算法的時(shí)空效率，文中提出了適用于加權(quán)頻繁項(xiàng)集挖掘的TK-FIM算法，以對加權(quán)頻繁項(xiàng)集的搜索空間進(jìn)行壓縮，提高挖掘效率。該算法的偽代碼如下所示。

TK-FIM算法：

輸入：不確定數(shù)據(jù)庫D，權(quán)重表wT，用戶指定的最小期望加權(quán)支持度閾值ε

輸出：加權(quán)頻繁項(xiàng)集集合WFIS

1.let CFIS1=I,TKWFIS1=Top-K(CFIS1)

2.for each itemIj∈CFIS1inDdo

3.scanDto calculate expwSup(Ij)

4.if expwSup(Ij)>ε×|D| then

5.WFIS1=WFIS1∪{Ij}

6.end if

7.end for

8.WFIS=WFIS1

9.setk=2

10.while WFISk-1≠null do

11.CWFISk=Connection(WFISk-1,TKWFIS1)

12.for each candidatek-itemsetXin CWFISkdo

13.if expwSup(X)>ε×|D| then

14.WFISk=WFISk∪{X}

15.end if

16.end for

17.WFIS=WFIS∪WFISk

18.k=k+1

19.end while

20.return WFIS

TK-FIM算法主要包括以下步驟：

(1)令候選1項(xiàng)集集合為不確定數(shù)據(jù)庫D對應(yīng)的項(xiàng)目集合I，令CFIS1中期望加權(quán)支持度Top-K的項(xiàng)集集合為TKWFIS1。掃描不確定數(shù)據(jù)庫D，對候選1項(xiàng)集集合CFIS1中的1項(xiàng)集進(jìn)行驗(yàn)證，根據(jù)定義7生成加權(quán)頻繁1項(xiàng)集WFIS1，并將WFIS1加入加權(quán)頻繁項(xiàng)集集合。

(2)設(shè)置k值為2，當(dāng)頻繁1項(xiàng)集WFIS1為非空集時(shí)，將頻繁1項(xiàng)集WFIS1與CFIS1中期望加權(quán)支持度Top-K的1項(xiàng)集集合TKWFIS1進(jìn)行連接，從而得到候選加權(quán)頻繁2項(xiàng)集集合CWFIS2，掃描不確定數(shù)據(jù)庫D，對候選加權(quán)頻繁2項(xiàng)集集合CWFIS2中的2項(xiàng)集進(jìn)行驗(yàn)證，根據(jù)定義7得到加權(quán)頻繁2-項(xiàng)集WFIS2，并將WFIS2加入加權(quán)頻繁項(xiàng)集集合，最后設(shè)置k=k+1。

(3)依此類推，可得到WFIS3，…，WFISk，直到WFISk是空集為止。

最終，運(yùn)行TK-FIM算法得到的加權(quán)頻繁項(xiàng)集為WFIS=WFIS1∪WFIS2∪…∪WFISk。

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

本小節(jié)將分別在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上對TK-FIM算法的性能進(jìn)行分析，包括算法的時(shí)間效率分析和算法所生成頻繁模式的數(shù)量及分布情況分析，并將TK-FIM算法的性能與Uapriori算法及HEWI-Uapriori算法的性能進(jìn)行對比分析。

5.1 實(shí)驗(yàn)設(shè)置及相關(guān)說明

實(shí)驗(yàn)平臺配置為：Intel Core i7-4510U 2.6 GHz處理器，8 G內(nèi)存，Windows 7 64位操作系統(tǒng)。實(shí)驗(yàn)所采用的合成數(shù)據(jù)集T10I4D100K和真實(shí)數(shù)據(jù)集retail均來自http://fimi.ua.ac.be/data/。數(shù)據(jù)集特征如表1所示，其中|D|為數(shù)據(jù)集所包含的事務(wù)數(shù)，|I|為數(shù)據(jù)集所包含的項(xiàng)目數(shù)，AvgLen為平均每條事務(wù)包含的項(xiàng)目數(shù)。

表1 數(shù)據(jù)集特征

此外，還需要說明以下兩點(diǎn)。第一，由于合成數(shù)據(jù)集T10I4D100K和真實(shí)數(shù)據(jù)集retail均為普通的確定數(shù)據(jù)集，不包含項(xiàng)目的權(quán)重信息和項(xiàng)目在事務(wù)中存在的概率信息，因此在分析TK-FIM算法性能之前需要首先為兩個(gè)數(shù)據(jù)集生成項(xiàng)目權(quán)重信息和概率信息。為了避免權(quán)重和概率的取值對算法性能的影響，每一項(xiàng)實(shí)驗(yàn)均采用5組不同的權(quán)重值,5組不同的項(xiàng)目概率值進(jìn)行實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果取25組結(jié)果的平均值。第二，Uapriori為適用于不確定數(shù)據(jù)集的頻繁項(xiàng)集挖掘算法，運(yùn)行Uapriori算法得到的頻繁項(xiàng)集稱為EFIs(expected support frequent itemsets)；HEWI-Uapriori為適用于不確定數(shù)據(jù)集的加權(quán)頻繁項(xiàng)集挖掘算法，運(yùn)行HEWI-Uapriori算法得到的加權(quán)頻繁項(xiàng)集稱為HEWIs(high expected weighted itemsets)；文中提出的TK-FIM算法同樣為適用于不確定數(shù)據(jù)集的加權(quán)頻繁項(xiàng)集挖掘算法，運(yùn)行TK-FIM算法得到的加權(quán)頻繁項(xiàng)集稱為WFIs(weighted frequent itemsets)。在后續(xù)分析中，將EFIs、HEWIs和WFIs統(tǒng)一稱為頻繁模式。對于Uapriori算法采用的最小期望支持度閾值δ，可以看作最小期望加權(quán)支持度閾值ε的特例(所有項(xiàng)目權(quán)重值均為1)，因此在后續(xù)分析中統(tǒng)稱為最小期望加權(quán)支持度閾值ε。

5.2 時(shí)間效率分析

在第一組實(shí)驗(yàn)中，對TK-FIM算法的時(shí)間效率進(jìn)行了分析。分別在retail數(shù)據(jù)集和T10I4D100K數(shù)據(jù)集上，分析了Uapriori算法、HEWI-Uapriori算法及TK-FIM算法運(yùn)行時(shí)間隨最小期望加權(quán)支持度的變化情況，如圖1、圖2所示。

圖1 retail數(shù)據(jù)集算法運(yùn)行時(shí)間對比

圖2 T10I4D100K數(shù)據(jù)集算法運(yùn)行時(shí)間對比

可以看出，三種算法的運(yùn)行時(shí)間均隨最小期望加權(quán)支持度的增大而減小，這是由于隨著最小期望加權(quán)支持度的增大，生成的頻繁項(xiàng)集和加權(quán)頻繁項(xiàng)集數(shù)量逐漸減少，因此在算法運(yùn)行過程中需要被驗(yàn)證的候選頻繁項(xiàng)集數(shù)量也逐漸減少，算法的運(yùn)行時(shí)間自然逐漸減小。

此外，由這兩圖還可以看出，在特定的最小期望加權(quán)支持度下，TK-FIM算法的運(yùn)行時(shí)間小于HEWI-Uapriori算法的運(yùn)行時(shí)間，而HEWI-Uapriori算法的運(yùn)行時(shí)間小于Uapriori算法的運(yùn)行時(shí)間。這是由于Uapriori算法中沒有考慮項(xiàng)目的權(quán)重值，所以在相同的最小期望加權(quán)支持度下，Uapriori算法生成的候選頻繁項(xiàng)集數(shù)量遠(yuǎn)大于TK-FIM算法生成的加權(quán)頻繁項(xiàng)集數(shù)量。HEWI-Uapriori算法雖然也采用了向下閉包特性對候選頻繁項(xiàng)集的數(shù)量進(jìn)行壓縮，但是該算法在得到HUBEWIs(high upper-bound expected weighted itemsets)后，還需要二次掃描數(shù)據(jù)集以得到HEWIs。對于HEWI-Uapriori算法與Uapriori算法的時(shí)間效率比較，需要視是否考慮項(xiàng)目的權(quán)重值和二次掃描數(shù)據(jù)集兩種因素，哪個(gè)因素起主導(dǎo)作用決定。對于retail數(shù)據(jù)集和T10I4D100K數(shù)據(jù)集來說，是否考慮項(xiàng)目的權(quán)重值對于算法時(shí)間效率的影響較大，因此HEWI-Uapriori算法的時(shí)間效率優(yōu)于Uapriori算法。

5.3 頻繁模式數(shù)量分析

在第二組實(shí)驗(yàn)中，分析了Uapriori算法、HEWI-Uapriori算法及TK-FIM算法所生成頻繁模式的數(shù)量情況。

圖3和圖4分別描述了retail數(shù)據(jù)集和T10I4 D100K數(shù)據(jù)集上，三種算法所生成的頻繁項(xiàng)集數(shù)量隨最小期望支持度閾值的變化情況。

圖3 retail數(shù)據(jù)集算法生成頻繁模式數(shù)量對比

圖4 T10I4D100K數(shù)據(jù)集算法生成 頻繁模式數(shù)量對比

由圖3和圖4可以看出，無論是在retail數(shù)據(jù)集還是在T10I4D100K數(shù)據(jù)集上，隨著最小期望加權(quán)支持度閾值的增大，三種算法所生成頻繁模式的數(shù)量均呈現(xiàn)出逐漸減少的趨勢。當(dāng)最小期望加權(quán)支持度相同時(shí)，TK-FIM算法生成的頻繁模式(WFIs)數(shù)量少于HEWI-Uapriori算法生成的頻繁模式(HEWIs)數(shù)量，而HEWI-Uapriori算法生成的頻繁模式數(shù)量又遠(yuǎn)少于Uapriori算法生成的頻繁模式(EFIs)數(shù)量。WFIs數(shù)量小于HEWIs數(shù)量，是由于在HEWI-Uapriori算法中采用項(xiàng)集的概率加權(quán)上限值作為項(xiàng)集的期望加權(quán)支持度，這對項(xiàng)集的期望加權(quán)支持度進(jìn)行了放大，顯然使得更多的項(xiàng)集被當(dāng)作加權(quán)頻繁項(xiàng)集挖掘出來。HEWIs數(shù)量少于EFIs數(shù)量，這是因?yàn)閁apriori算法并未引入權(quán)重值，或者說所有項(xiàng)目的權(quán)重值均為1，所以會(huì)生成更多的頻繁項(xiàng)集。

6 結(jié)束語

面向不確定數(shù)據(jù)的加權(quán)頻繁項(xiàng)集挖掘，可以兼顧項(xiàng)目在事務(wù)中的存在概率和項(xiàng)目本身的重要性，有利于發(fā)現(xiàn)對用戶具有重要價(jià)值和意義的頻繁項(xiàng)集。為了提高面向不確定數(shù)據(jù)加權(quán)頻繁項(xiàng)集挖掘算法的時(shí)間效率，提出了TK-FIM算法，該算法縮小了加權(quán)頻繁項(xiàng)集的搜索空間，提高了算法的搜索效率。TK-FIM算法雖然在一定程度上提高了加權(quán)頻繁項(xiàng)集的挖掘效率，但是仍然需要多次掃描數(shù)據(jù)庫，對候選加權(quán)頻繁項(xiàng)集進(jìn)行驗(yàn)證，如何將TK-FIM算法與樹存儲(chǔ)結(jié)構(gòu)相結(jié)合，避免頻繁掃描數(shù)據(jù)庫，進(jìn)一步提高算法的時(shí)間效率，是下一步工作的研究重點(diǎn)。