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

章淑云，張守志

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

章淑云，張守志

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

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

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

1 概述

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

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

2 相關(guān)知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 概率頻繁閉項集UFCIM算法

3.1 概率支持度

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

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

(8)

圖1表明動態(tài)計算模式算法能夠在(||)時間復(fù)雜度下計算出項集支持度至少為的概率。其計算過程由下至上、由左至右。如圖1所示，灰色區(qū)域為需要計算的概率值，圖中每個方格表示概率值≥()；詳細計算過程可參考文獻[8]。

圖1 動態(tài)計算模式

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

算法1概率支持度算法ProbSup

輸入項集，置信度，最小支持度

輸出項集的概率支持度

(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ù)庫的概率矩陣，P為項集在事//務(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時，概率為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中概率矩陣對應(yīng)的不確定性數(shù)據(jù)庫為例，= {0,1,2}，={0,1,2}，以項集={0,1}為例，設(shè)=0.2，= 1；≥1,1(X)=1×[1][0]×[1][1]+0=0.8×0.3=0.24；繼而計算出≥1,2()=0.285 6>；繼續(xù)計算≥2,2()=0.014 4<，所以項集={0,1}的概率支持度為1。

3.2 UFCIM算法

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

算法2頻繁閉項集挖掘算法UFCIM

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

輸出//頻繁閉項集

Foreach Iiin I

Ii.MS = ProbSup(Ii,δ,minsup); //項集域包括概率支持度與項//集數(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是初始項集合中的所有單項集的集合，首先計算各個單項集的概率支持度，將支持度存入項集的概率支持度域。將概率支持度大于等于最小支持度閾值的項集存入列表L，然后利用生成長度為2的候選集L+1，候選集生成方法與類似，但其復(fù)雜度遠比低，因本文中項均用整數(shù)表示，算法掃描K-項集集合中的每2項(不重復(fù))，利用兩順序列表集合的并集操作生成候選項，遇到長度大于+1的項集及時退出，大大降低了時間復(fù)雜度。FL+1為當(dāng)前K-頻繁項集所生成的候選集K+1-頻繁項集，對K-頻繁項集一一檢測，檢查是否有K-頻繁項集的超集為K+1-頻繁項集且其支持度相等，從而輸出頻繁閉項集。

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

4 實驗結(jié)果與分析

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

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

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

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

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

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

5 結(jié)束語

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

[1] 戴曉華, 王 智, 蔣 鵬, 等. 無線傳感器網(wǎng)絡(luò)智能信息處理研究[J]. 傳感技術(shù)學(xué)報; 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]. 計算機研究與發(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ù)倉庫，數(shù)據(jù)挖掘；張守志，副教授。

2012-12-10

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

10.3969/j.issn.1000-3428.2014.03.010