一種基于Top-K查詢的加權頻繁項集挖掘算法

趙學健，熊肖肖，張欣慧，孫知信

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

1 概 述

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

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

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

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

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

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

2 相關工作

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

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

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

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

2.2 加權頻繁項集挖掘算法

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

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

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

3 相關定義與問題描述

3.1 相關定義

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

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

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

(1)

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

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

即：

(2)

其中，Ij為項集X的第j個項目。

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

即：

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

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

(4)

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

3.2 問題描述

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

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

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

4 TK-FIM算法

為了提高頻繁項集挖掘算法的時空效率，文中提出了適用于加權頻繁項集挖掘的TK-FIM算法，以對加權頻繁項集的搜索空間進行壓縮，提高挖掘效率。該算法的偽代碼如下所示。

TK-FIM算法：

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

輸出：加權頻繁項集集合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項集集合為不確定數(shù)據(jù)庫D對應的項目集合I，令CFIS1中期望加權支持度Top-K的項集集合為TKWFIS1。掃描不確定數(shù)據(jù)庫D，對候選1項集集合CFIS1中的1項集進行驗證，根據(jù)定義7生成加權頻繁1項集WFIS1，并將WFIS1加入加權頻繁項集集合。

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

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

最終，運行TK-FIM算法得到的加權頻繁項集為WFIS=WFIS1∪WFIS2∪…∪WFISk。

5 實驗與結果分析

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

5.1 實驗設置及相關說明

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

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

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

5.2 時間效率分析

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

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

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

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

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

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

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

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

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

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

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

6 結束語

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