章淑云，張守志

基于不確定性數(shù)據(jù)的頻繁閉項(xiàng)集挖掘算法

章淑云，張守志

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，上海 200433)

對(duì)于不確定性數(shù)據(jù)，傳統(tǒng)判斷項(xiàng)集是否頻繁的方法并不能準(zhǔn)確表達(dá)項(xiàng)集的頻繁性，同樣對(duì)于大型數(shù)據(jù)，頻繁項(xiàng)集顯得龐大和冗余。針對(duì)上述不足，在水平挖掘算法Apriori的基礎(chǔ)上，提出一種基于不確定性數(shù)據(jù)的頻繁閉項(xiàng)集挖掘算法UFCIM。利用置信度概率表達(dá)項(xiàng)集頻繁的準(zhǔn)確性，置信度越高，項(xiàng)集為頻繁的準(zhǔn)確性也越高，且由于頻繁閉項(xiàng)集是頻繁項(xiàng)集的一種無(wú)損壓縮表示，因此利用壓縮形式的頻繁閉項(xiàng)集替代龐大的頻繁項(xiàng)集。實(shí)驗(yàn)結(jié)果表明，該算法能夠快速地挖掘出不確定性數(shù)據(jù)中的頻繁閉項(xiàng)集，在減少項(xiàng)集冗余的同時(shí)保證項(xiàng)集的準(zhǔn)確性和完整性。

不確定性數(shù)據(jù)；頻繁閉項(xiàng)集；數(shù)據(jù)挖掘；水平挖掘；置信度概率

1 概述

現(xiàn)實(shí)應(yīng)用中經(jīng)常出現(xiàn)噪聲和不完整的數(shù)據(jù)，比較常見(jiàn)的應(yīng)用有傳感網(wǎng)絡(luò)[1]和隱私保護(hù)[2]等數(shù)據(jù)挖掘應(yīng)用，又如醫(yī)院對(duì)于病人的診斷數(shù)據(jù)也存在許多不確定性因素。因此，如何對(duì)這些不確定性數(shù)據(jù)進(jìn)行分析和挖掘成為了數(shù)據(jù)挖掘中的一個(gè)重要研究領(lǐng)域。

近年來(lái)，有許多關(guān)于不確定性數(shù)據(jù)的頻繁模式挖掘的研究，其中有U-Apriori算法[3]、UF-tree算法[4]、UD-FP-tree算法[5]、U-Eclat算法[6]等，但其均采用項(xiàng)集概率分布的期望值定義頻繁項(xiàng)集，即將期望支持度大于等于最小支持度閾值的項(xiàng)集定義為頻繁項(xiàng)集。但這種對(duì)支持度的估計(jì)方法并未表示出其所估計(jì)的準(zhǔn)確度，因此本文采用文獻(xiàn)[7]提出的概率頻繁項(xiàng)集定義，定義了項(xiàng)集的支持度分布，并用大于等于最小支持度閾值的支持度概率總和定義項(xiàng)集的頻繁概率。傳統(tǒng)意義上頻繁閉項(xiàng)集是對(duì)頻繁項(xiàng)集的一種壓縮無(wú)損表示，從文獻(xiàn)[7]中的概率頻繁項(xiàng)集出發(fā)，文獻(xiàn)[8]對(duì)概率頻繁閉項(xiàng)集作出了進(jìn)一步闡述，定義了項(xiàng)集概率支持度的最大頻繁度，并用概率支持度定義頻繁閉項(xiàng)集。本文從概率頻繁項(xiàng)集和概率頻繁閉項(xiàng)集出發(fā)，利用可能性世界模型表示不確定性數(shù)據(jù)庫(kù)，根據(jù)概率頻繁閉項(xiàng)集的定義，提出一種在不確定性數(shù)據(jù)中進(jìn)行頻繁閉項(xiàng)集挖掘的算法UFCIM (Uncertain Frequent Closed Itemsets Mining)。

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

對(duì)于不確定性數(shù)據(jù)以及可能性世界模型，不同的文獻(xiàn)給出了類似的定義[9-11]。本文采用文獻(xiàn)[7]中的概率矩陣表示不確定性數(shù)據(jù)庫(kù)。項(xiàng)集={1,2,…,x}，事務(wù)集合={1,2,…,t}，其中對(duì)于每一項(xiàng)，都有一個(gè)非零概率(,t)∈[0,1]與之對(duì)應(yīng)，表示該項(xiàng)出現(xiàn)在事務(wù)t中的概率。不確定性數(shù)據(jù)庫(kù)可用一個(gè)×的矩陣表示，其中(,)表示項(xiàng)x在事務(wù)t中存在的概率。例如={1,2,3}，={1,2,3}，項(xiàng)在事務(wù)中出現(xiàn)的概率(∈t)用二元組(,(∈t))表示，見(jiàn)表1。

表1 不確定性數(shù)據(jù)庫(kù)

概率(∈t)所對(duì)應(yīng)概率矩陣為：

文獻(xiàn)[7]中Bernecker證明項(xiàng)集的概率分布P()可以不經(jīng)計(jì)算各個(gè)可能性世界存在的概率(w)所得，其中，為的子集；P()為的支持度為的概率。

定義1 假設(shè)P()為的支持度為的概率(簡(jiǎn)稱支持度概率)，則P()與可能性世界存在概率(w)無(wú)關(guān)的表示為：

定義2P()為支持度為的概率，≥()為支持度至少為的概率：

根據(jù)式(1)，式(2)可轉(zhuǎn)化為：

定義3 給定置信度閾值，最小支持度閾值，為概率頻繁項(xiàng)集需要滿足：

概率頻繁項(xiàng)集的支持度大于等于最小支持度，且大于等于最小支持度的概率大于等于置信度。

定義4給定項(xiàng)集、不確定性事務(wù)數(shù)據(jù)庫(kù)、置信度閾值，項(xiàng)集的概率支持度為：

項(xiàng)集的概率支持度定義了滿足支持度概率大于等于置信度的最大支持度。

定義5給定項(xiàng)集、不確定性事務(wù)數(shù)據(jù)庫(kù)、置信度閾值、最小支持度，為頻繁閉項(xiàng)集需滿足2個(gè) 條件：

且不存在長(zhǎng)度為||+1的的超集，使得下式成立：

式(6)中的條件保證項(xiàng)集為頻繁項(xiàng)集，式(7)中的條件保證項(xiàng)集為閉項(xiàng)集。第2個(gè)條件為不存在的超集，()=()，但可證明滿足式(7)中的條件即對(duì)所有的超集均成立，證明見(jiàn)文獻(xiàn)[8]。

3 概率頻繁閉項(xiàng)集UFCIM算法

3.1 概率支持度

由式(5)可看出，求解概率支持度需要計(jì)算項(xiàng)集支持度，滿足≥()≥，由式(1)可看出，計(jì)算P()的復(fù)雜度為指數(shù)級(jí)。本文利用文獻(xiàn)[12]中概率top-k查詢的動(dòng)態(tài)編程模式方法計(jì)算≥()。

定義6項(xiàng)集、支持度、事務(wù)中前個(gè)事務(wù)，項(xiàng)集在個(gè)事務(wù)中支持度大于等于的概率為：

(8)

圖1表明動(dòng)態(tài)計(jì)算模式算法能夠在(||)時(shí)間復(fù)雜度下計(jì)算出項(xiàng)集支持度至少為的概率。其計(jì)算過(guò)程由下至上、由左至右。如圖1所示，灰色區(qū)域?yàn)樾枰?jì)算的概率值，圖中每個(gè)方格表示概率值≥()；詳細(xì)計(jì)算過(guò)程可參考文獻(xiàn)[8]。

圖1 動(dòng)態(tài)計(jì)算模式

將計(jì)算項(xiàng)集的支持度概率擴(kuò)展到概率支持度中，即循環(huán)在支持度達(dá)到最小支持度()，且此時(shí)求得概率值大于等于置信度時(shí)并不終止，而是繼續(xù)計(jì)算+1、+2的支持度概率，直至在該支持度下項(xiàng)集的支持度概率小于，返回當(dāng)前支持度值-1。所得值為項(xiàng)集的概率支持度。概率支持度算法描述如下：

算法1概率支持度算法ProbSup

輸入項(xiàng)集，置信度，最小支持度

輸出項(xiàng)集的概率支持度

(1)ProbSup(Itemset X,float δ,int minsup):

(2)For j=0 to |T|

Foreach i in X

P[j]*=M[j][i]; //M為不確定數(shù)據(jù)庫(kù)的概率矩陣，P為項(xiàng)集在事//務(wù)中出現(xiàn)的概率

(3)For i=0 to |T|

For j=i to |T|-minsup+i

if(i==0)

Matrix[i][j]=1;continue;//初始化矩陣的第1行

if(i==j)

Matrix[i][j-1]=0;//當(dāng)i>j時(shí)，概率為0

Matrix[i][j]=matrix[i-1][j-1] * P[j] + matrix[i][j-1] * (1-P[j]);

End

if(matrix[i][j-1] <δ) //直至支持度概率小于置信度

Return i-1;

Return i-1;

以圖1中概率矩陣對(duì)應(yīng)的不確定性數(shù)據(jù)庫(kù)為例，= {0,1,2}，={0,1,2}，以項(xiàng)集={0,1}為例，設(shè)=0.2，= 1；≥1,1(X)=1×[1][0]×[1][1]+0=0.8×0.3=0.24；繼而計(jì)算出≥1,2()=0.285 6>；繼續(xù)計(jì)算≥2,2()=0.014 4<，所以項(xiàng)集={0,1}的概率支持度為1。

3.2 UFCIM算法

上文介紹了概率支持度的計(jì)算方法，通過(guò)計(jì)算K-項(xiàng)集的概率支持度，找出頻繁項(xiàng)集，即概率支持度大于等于最小支持度的項(xiàng)集；采用水平生成候選集的方法，生成K+1-項(xiàng)集并計(jì)算它們的概率支持度，找出K+1-頻繁項(xiàng)集；將K-頻繁項(xiàng)集與K+1-頻繁閉項(xiàng)集一一比較，若有K+1-頻繁閉項(xiàng)集的子集K-頻繁項(xiàng)集與其支持度相等，將其舍去，最后輸出K-頻繁項(xiàng)集，其不存在K+1-頻繁閉項(xiàng)集為其超集，且概率支持度相等。頻繁閉項(xiàng)集的挖掘算法UFCIM描述如下：

算法2頻繁閉項(xiàng)集挖掘算法UFCIM

輸入,float,int//為初始項(xiàng)的集合，為置信//度閾值，為最小支持度

輸出//頻繁閉項(xiàng)集

Foreach Iiin I

Ii.MS = ProbSup(Ii,δ,minsup); //項(xiàng)集域包括概率支持度與項(xiàng)//集數(shù)組

if(Ii.MS ≥ minsup)

Lk.add(Ii);

End

Lk+1= AprioriGen_Order(Lk); //生成候選集

While(Lk+1.empty()== false)

Foreach X in Lk+1

X.MS = ProbSup(X,δ,minsup);

if(X.MS ≥ minsup)

FLk+1.add(X);

End

Foreach X in Lk

Flag = true;

Foreach Y in FLk+1

if(Y.contain(X) && Y.MS == X.MS)

Flag =false;

Break;

if(flag)

C.add(X);

End

End

Lk=FLk+1;

FLk+1.clear();

Lk+1= AprioriGen_Order(Lk);

End

Return C;

在上述算法中，I是初始項(xiàng)集合中的所有單項(xiàng)集的集合，首先計(jì)算各個(gè)單項(xiàng)集的概率支持度，將支持度存入項(xiàng)集的概率支持度域。將概率支持度大于等于最小支持度閾值的項(xiàng)集存入列表L，然后利用生成長(zhǎng)度為2的候選集L+1，候選集生成方法與類似，但其復(fù)雜度遠(yuǎn)比低，因本文中項(xiàng)均用整數(shù)表示，算法掃描K-項(xiàng)集集合中的每2項(xiàng)(不重復(fù))，利用兩順序列表集合的并集操作生成候選項(xiàng)，遇到長(zhǎng)度大于+1的項(xiàng)集及時(shí)退出，大大降低了時(shí)間復(fù)雜度。FL+1為當(dāng)前K-頻繁項(xiàng)集所生成的候選集K+1-頻繁項(xiàng)集，對(duì)K-頻繁項(xiàng)集一一檢測(cè)，檢查是否有K-頻繁項(xiàng)集的超集為K+1-頻繁項(xiàng)集且其支持度相等，從而輸出頻繁閉項(xiàng)集。

以圖1對(duì)應(yīng)的概率矩陣為例，={0,1,2}，={0,1,2}，=0.2，=1；利用3.1節(jié)中的計(jì)算概率支持度方法可計(jì)算出({0})=1，({1})=1，({2})=2，均大于等于最小支持度、生成長(zhǎng)度為2的候選集{0,1},{0,2}, {1,2}；計(jì)算得出({0,1})=1，({0,2})=1，({1,2})=1，均為頻繁項(xiàng)集，與長(zhǎng)度為1的頻繁項(xiàng)集相比，可得只有項(xiàng)集{2}為頻繁閉項(xiàng)集；再生成長(zhǎng)度為3的候選集{0,1,2}，計(jì)算得({0,1,2})=0不為頻繁項(xiàng)集，因此所有2頻繁項(xiàng)集均為頻繁閉項(xiàng)集，最終頻繁閉項(xiàng)集為{2},{0,1},{0,2},{1,2}。

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

本節(jié)對(duì)頻繁閉項(xiàng)集算法UFCIM進(jìn)行實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。實(shí)驗(yàn)算法由C++語(yǔ)言編寫(xiě)，在VC6.0環(huán)境下編譯運(yùn)行，運(yùn)行環(huán)境是Intel Core2 Duo 2.40 Hz CPU，2 GB內(nèi)存，Windows7操作系統(tǒng)。

本文實(shí)驗(yàn)所用數(shù)據(jù)集來(lái)自文獻(xiàn)[8]，分別是mushroom、T10I4D100K、accidents、chess。所用數(shù)據(jù)集均可在http:// fimi.cs.helsinki.fi/data/中下載確定性數(shù)據(jù)庫(kù)，使用Matlab R900b中的Beta分布函數(shù)，其中，參數(shù)分別為=5，=1，生成隨機(jī)數(shù)，通常為0.8~1，對(duì)確定性數(shù)據(jù)庫(kù)進(jìn)行掃描，若該項(xiàng)存在于事務(wù)中，其概率值取，對(duì)于事務(wù)中不存在的項(xiàng)，其概率值取1-，實(shí)驗(yàn)證明這種概率分布更加接近現(xiàn)實(shí)中的不確定性數(shù)據(jù)庫(kù)。圖2分析了置信度為0.9時(shí)不同最小支持度/對(duì)運(yùn)行時(shí)間的影響，圖3分析了最小支持度=0.75×?xí)r不同置信度對(duì)運(yùn)行時(shí)間的影響，圖4分析了在/=0.75、置信度=0.9時(shí)數(shù)據(jù)集T10I4D100K中不同事務(wù)數(shù)對(duì)運(yùn)行時(shí)間的影響。

圖2 最小支持度與運(yùn)行時(shí)間的關(guān)系

圖3 置信度δ與運(yùn)行時(shí)間的關(guān)系

圖4 T10I4D100K中事務(wù)數(shù)與運(yùn)行時(shí)間的關(guān)系

從圖2中/對(duì)運(yùn)行時(shí)間的影響可以看出，/與運(yùn)行時(shí)間成指數(shù)關(guān)系。/比例值越低，意味著可生成更多頻繁項(xiàng)集，從而生成更多候選集，生成候選集的時(shí)間與項(xiàng)集數(shù)成指數(shù)關(guān)系，所以比例值與運(yùn)行時(shí)間呈指數(shù)關(guān)系。圖3中顯示了在/固定為0.75時(shí)，置信度與運(yùn)行時(shí)間呈線性關(guān)系，因?yàn)橹С侄容^高，生成的頻繁項(xiàng)集在不同置信度下幾乎沒(méi)有差別，只是計(jì)算每個(gè)項(xiàng)集的支持度時(shí)循環(huán)執(zhí)行的更多，線性增加了運(yùn)行時(shí)間。圖4中事務(wù)數(shù)與運(yùn)行時(shí)間呈拋物線關(guān)系，與圖3相似，增加的時(shí)間為計(jì)算概率支持度時(shí)，因而與運(yùn)行時(shí)間呈拋物線關(guān)系。

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

本文擴(kuò)展Apriori算法在不確定性數(shù)據(jù)挖掘中的應(yīng)用，將其運(yùn)用于不確定性數(shù)據(jù)中的頻繁閉項(xiàng)集挖掘。但與一般不確定性數(shù)據(jù)頻繁項(xiàng)集挖掘中所采用的數(shù)據(jù)表示和頻繁項(xiàng)集定義不同，本文采用更精確的文獻(xiàn)[7]中頻繁項(xiàng)集的定義，進(jìn)而定義頻繁閉項(xiàng)集。本文算法UFCIM用于在不確定數(shù)據(jù)中挖掘頻繁閉項(xiàng)集，通過(guò)實(shí)驗(yàn)分析了不同置信度、最小支持度、事務(wù)數(shù)對(duì)于運(yùn)行時(shí)間的影響，表明算法UFCIM能有效地挖掘頻繁閉項(xiàng)集。

[1] 戴曉華, 王 智, 蔣 鵬, 等. 無(wú)線傳感器網(wǎng)絡(luò)智能信息處理研究[J]. 傳感技術(shù)學(xué)報(bào); 2006, 9(1): 1-7.

[2] Evfimievski A, Srikant R, Agrawal R, et al. Privacy Preserving Mining of Association Rules[C]//Proc. of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Canada: [s. n.], 2002: 217-228.

[3] Chui C K, Kao B, Hung E. Mining Frequent Itemsets from Uncertain Data[C]//Proc. of the 11th Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin, Germany: Springer-Verlag, 2007: 47-58.

[4] Han Jiawei, Pei Jian, Yin Yiwen. Mining Frequent Patterns Without Candidate Generation[C]//Proc. of ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2000: 1-12.

[5] 高 聰, 申德榮, 于 戈. 一種基于不確定數(shù)據(jù)的挖掘頻繁集方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2008, 45(z1): 71-76.

[6] Calders T, Carboni C, Goethals B. Efficient Pattern Mining of Uncertain Data with Sampling[C]//Proc. of the 14th Pacific- Asia Conference on Knowledge Discovery and Data Mining. Hyderabad, India: [s. n.], 2010: 480-487.

[7] Bernecker T, Kriegel H P, Renz M, et al. Probabilistic Fre- quent Itemset Mining in Uncertain Databases[C]//Proc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France: [s. n.], 2009: 119-128.

[8] Tang Peiyi, Peterson E A. Mining Probabilistic Frequent Closed Itemsets in Uncertain Databases[C]//Proc. of the 49th ACM Southeast Conference. Kennesaw, USA: [s. n.], 2011.

[9] Abiteboul S, Kanellakis P. On the Representation and Query- ing of Sets of Possible Worlds[C]//Proc. of ACM SIGMOD Conference on Management of Data. New York, USA: ACM Press, 1987: 34-48.

[10] Green T J, Tannen V. Models for Incomplete and Probabilistic Information[J]. Lecture Notes in Computer Science, 2006, 29(1): 17-24.

[11] Zhang Qin, Li Feifei, Yi Ke. Finding Frequent Items in Probabilistic Data[C]//Proc. of ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 2008: 819-832.

[12]Ke Yi, Li Feifei, Kollios G, et al. Efficient Processing of Top-K Queries in Uncertain Databases[C]//Proc. of the 24th Inter- national Conference on Data Engineering. Washington D. C., USA: IEEE Computer Society, 2009: 1406-1408.

編輯 任吉慧

Mining Algorithm of Frequent Closed Itemsets Based on Uncertain Data

ZHANG Shu-yun, ZHANG Shou-zhi

(School of Computer Science, Fudan University, Shanghai 200433, China)

For the uncertain data, traditional method of judging whether an itemset is frequent cannot express how close the estimate is, meanwhile frequent itemsets are large and redundant for large datasets. Regarding to the above two disadvantages, this paper proposes amining algorithm of frequent closed itemsets based on uncertain data called UFCIM to mine frequent closed itemsets from uncertain data according to frequent itemsets mining method from uncertain data, and it is based on level mining algorithm Apriori. It uses probability of confidence to express how close the estimate is, the larger that probability of confidence is, the itemsets are more likely to be frequent. Besides as frequent closed itemsets are compact and lossless representation of frequent itemsets, so it uses compacted frequent closed itemsets to take place of frequent itemsets which are of huge size. Experimental result shows the UFCIM algorithm can mine frequent closed itemsets effectively and quickly. It can reduce redundancy and meanwhile assure the accuracy and completeness of itemsets.

uncertain data; frequent closed itemsets; data mining; level mining; probability of confidence

1000-3428(2014)03-0051-04

A

TP311.12

章淑云(1989－)，女，碩士研究生，主研方向：數(shù)據(jù)倉(cāng)庫(kù)，數(shù)據(jù)挖掘；張守志，副教授。

2012-12-10

2013-04-07 E-mail：10210240047@fudan.edu.cn

10.3969/j.issn.1000-3428.2014.03.010