不確定數(shù)據(jù)中的代表頻繁項集近似挖掘

陳鳳娟

(1.遼寧對外經(jīng)貿(mào)學(xué)院 大連 116052)(2.大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 大連 116023)

不確定數(shù)據(jù)中的代表頻繁項集近似挖掘

陳鳳娟1,2

(1.遼寧對外經(jīng)貿(mào)學(xué)院 大連 116052)(2.大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院 大連 116023)

不確定數(shù)據(jù)的頻繁項集挖掘作為很多數(shù)據(jù)挖掘任務(wù)的基本步驟,引起了很多學(xué)者的關(guān)注。但是當(dāng)不確定數(shù)據(jù)集的規(guī)模很大時,會產(chǎn)生數(shù)目巨大的頻繁項集,給后續(xù)挖掘工作帶來難題。為解決這一問題,論文提出不確定數(shù)據(jù)集中的代表頻繁項集概念,并利用VC維的概念,確定抽樣空間,提出一種基于隨機抽樣的代表頻繁項集近似挖掘算法,在保證挖掘效果的前提下,減少了挖掘出的頻繁項集的數(shù)量,提高算法的效率。

不確定數(shù)據(jù); 代表頻繁項集; 近似算法; VC維

Class Number TP311

1 引言

不確定數(shù)據(jù)廣泛存在于各種應(yīng)用中,如無線傳感器網(wǎng)絡(luò)、社交網(wǎng)絡(luò)和各種科學(xué)研究的實驗,對不確定數(shù)據(jù)的挖掘和分析不僅可以為決策提供有力的工具,也可以發(fā)現(xiàn)這些不確定數(shù)據(jù)中隱藏的重要的規(guī)律[1～3]。

不確定數(shù)據(jù)集包含了很多有用的信息,可以通過在不確定數(shù)據(jù)中挖掘頻繁項集來發(fā)現(xiàn)這些信息。頻繁項集挖掘是很多數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)步驟,尤其是關(guān)聯(lián)規(guī)則挖掘[4～5]和圖挖掘等,它能找出數(shù)據(jù)集中多次共同出現(xiàn)的數(shù)據(jù)項。隨著各種技術(shù)的發(fā)展,需要分析的不確定數(shù)據(jù)的數(shù)據(jù)量在不斷增加,在這種大規(guī)模的不確定數(shù)據(jù)中,頻繁項集的數(shù)量也是巨大的,不利于后續(xù)工作的進行。為了減少頻繁項集的冗余,可以用最大頻繁項集、頻繁閉項集或代表頻繁項集來壓縮表示頻繁項集[6～8],而代表頻繁項集可以通過參數(shù)的設(shè)置來調(diào)節(jié)壓縮效果,是一種比較好的壓縮表示。文獻[8]提出一種在不確定數(shù)據(jù)集中挖掘概率代表頻繁項集的近似算法,該方法提出概率代表頻繁項集的概念并給出挖掘概率代表頻繁項集的近似算法,但是該算法不適用于大規(guī)模不確定數(shù)據(jù)集。

為了解決大規(guī)模不確定數(shù)據(jù)集中的代表頻繁項集挖掘問題,本文給出了一個適用于大數(shù)據(jù)集的代表頻繁項集的概念,然后定義ε-近似頻繁項集,并提出一種基于VC維理論保證在至少是1-δ的概率下,挖掘不確定數(shù)據(jù)集的代表ε-近似頻繁項集的隨機抽樣的算法,實現(xiàn)從大規(guī)模不確定數(shù)據(jù)集中挖掘代表頻繁項集的近似集合,由于算法每次抽取的樣本量遠遠小于整個數(shù)據(jù)集的大小,因此,算法可擴展性好,能適用于大規(guī)模不確定數(shù)據(jù)集。

2 基本概念及問題描述

2.1 不確定數(shù)據(jù)集中的頻繁項集

假設(shè)存在一個項的集合I和一個事務(wù)的集合T,其中,I={x1,x2, …,xm},T={t1,t2,…,tn}。I中的每個元素x稱為項,I中任意個項的組合稱為項集X,T中的每個元素t稱為一個事務(wù),并且,T中的每條事務(wù)t都是由I中的某些項x和P(x∈t)組成的。對于任意的項x∈I,都有一個存在概率P(x∈tj)∈[0,1],表示項x在事務(wù)tj中出現(xiàn)的可能性大小。當(dāng)P(x∈tj)=0時, 表示項x在事務(wù)tj中不存在；當(dāng)P(x∈tj)=1時, 表示項x在事務(wù)tj中一定存在；當(dāng)0

在不確定數(shù)據(jù)集中,可以根據(jù)每個項的存在概率,得到不確定數(shù)據(jù)集的可能世界的語義解釋,根據(jù)項是否在某個事務(wù)中出現(xiàn),不確定數(shù)據(jù)集會出現(xiàn)2|T|*|I|個可能世界。在假設(shè)不確定數(shù)據(jù)集中的事務(wù)是相互獨立的前提下,每個可能世界w的概率P(w)定義為[10]

(1)

對于不確定數(shù)據(jù)集中的頻繁項集,存在兩種定義方式,一種是以項集的期望支持度為標(biāo)準(zhǔn)進行判斷,另一種是以項集的頻繁概率為標(biāo)準(zhǔn)進行判斷[11]?；谄谕С侄鹊母拍?計算簡單,但是會丟失一部分有用的信息,而基于頻繁概率的定義,能很好的保留不確定數(shù)據(jù)集中的全部有用信息,但是計算量很大。文獻[12]中已給出詳細的分析,并證明了在數(shù)據(jù)量很大的情況下,可以用期望支持度來代替頻繁概率,作為挖掘頻繁項集的標(biāo)準(zhǔn),既能減少運算量,也能保證算法的精度。本文研究的是大規(guī)模不確定數(shù)據(jù)集中的頻繁項集的壓縮挖掘,因此,采用下面的期望支持度的定義。

定義1 在不確定數(shù)據(jù)集T中,對于任意一個項集X,它的期望支持度定義為該項集在所有的事務(wù)中出現(xiàn)的概率之和,記為ESup(X),即

(2)

文獻[9]根據(jù)定義1,提出了不確定數(shù)據(jù)中的頻繁項集挖掘問題,即對于一個不確定數(shù)據(jù)集T,給定一個最小的期望支持度閾值minESup,如果項集X的期望支持度大于給定的minESup,則稱X在該不確定數(shù)據(jù)集中是頻繁的,否則,X是不頻繁的。

2.2 不確定數(shù)據(jù)中的代表頻繁項集

在確定數(shù)據(jù)中,文獻[13～14]定義了兩個項集的距離測量方式和近似覆蓋概念,并基于這兩個概念,提出了確定數(shù)據(jù)庫中的代表頻繁項集。

給定一個實數(shù)τ,τ∈[0,1],如果X1?X2并且dist(X1,X2)≤τ,則稱項集X1被項集X2τ-近似覆蓋。

代表頻繁項集是指能τ-近似覆蓋所有頻繁項集的最小項集的集合。

本文把這些概念推廣到不確定數(shù)據(jù)集中,提出不確定數(shù)據(jù)集中兩個項集的距離測量和近似覆蓋以及代表頻繁項集的概念。

根據(jù)文獻[9]中期望支持度的概念可得,如果X1?X2,則有

(3)

定義3 給定一個不確定數(shù)據(jù)集T,項集X1和X2,實數(shù)τ∈[0,1],如果X1?X2并且Udist(X1,X2)≤τ,則稱項集X1被項集X2τ-近似覆蓋,若項集X1是頻繁項集,則稱X2是X1在不確定數(shù)據(jù)集中的代表頻繁項集。

給定一個不確定數(shù)據(jù)集T,頻繁項集F,任意實數(shù)τ∈[0,1],代表頻繁項集挖掘是找出最小的頻繁項集集合R,使得對于任意的一個頻繁項集X,X∈F,都存在一個代表頻繁項集X′,X′∈R,滿足X′能τ-近似覆蓋X。

3 代表頻繁項集的近似挖掘

代表頻繁項集可以壓縮表示頻繁項集,減小集合中項集的個數(shù),一種簡單的挖掘頻繁項集的方法是先挖掘出不確定數(shù)據(jù)集的頻繁項集,然后根據(jù)代表頻繁項集的定義,從中找出代表頻繁項集。但是這種方法不適用于大規(guī)模數(shù)據(jù)集,因為頻繁項集的挖掘需要消耗大量的時間。為了在大規(guī)模數(shù)據(jù)集中快速的挖掘出代表頻繁項集,下面提出一種基于抽樣的近似算法,挖掘在1-δ的概率保證下,不確定數(shù)據(jù)集的代表ε-近似頻繁項集。首先給出ε-近似頻繁項集的定義,然后介紹近似挖掘的理論依據(jù),最后給出近似挖掘算法的框架。

3.1ε-近似頻繁項集

由于算法采用對大規(guī)模數(shù)據(jù)集進行抽樣的策略進行挖掘,因此,給出頻繁項集的絕對近似集的定義。

定義4 設(shè)T是一個不確定事務(wù)數(shù)據(jù)集,它的所有項的集合是I,最小期望支持度是minESup,該數(shù)據(jù)集的頻繁項集記為F,0<ε<1,集合A是由項集X和該項集的近似期望支持度AEsup(X)構(gòu)成的數(shù)據(jù)對組成的集合,即A={X,AEsup(X)|A∈2I,AEsup(X)∈[0,1]}。如果A滿足下面的三個條件,則稱集合A是頻繁項集F的絕對ε-近似。

1)A中包含F(xiàn)中出現(xiàn)的所有項集。

2)A不包括期望支持度ESup(X)≤minESup-ε的項集X。

3)A中任意一個數(shù)據(jù)對(X,AEsup(X)),都滿足|ESup(X)-AEsup(X)|≤ε。

在對數(shù)據(jù)集進行抽樣的過程中,要保證挖掘出的近似頻繁項集是原有頻繁項集的ε-近似,這樣在這個頻繁項集基礎(chǔ)上得到的代表項集才能滿足后續(xù)任務(wù)的需求。

3.2 不確定數(shù)據(jù)集的VC維

空間中一些點的VC維是一種衡量空間上定義的指導(dǎo)函數(shù)族的復(fù)雜度的方法,一個結(jié)構(gòu)的VC維的有限邊界表明該結(jié)構(gòu)上的一個近似學(xué)習(xí)所需要的隨機抽樣個數(shù)的邊界[15～17]。

定義5 范圍空間是一個(X,R)對,其中,X是一個有限(或無限)集合,而R是X的子集的有限(或無限)族。X中的成員稱為點,R中的成員稱為范圍。A是X的真子集,R在A上的映射PR(A)為PR(A)={r∩A:r∈R}。如果PR(A)=2A,則稱A被R打碎。

定義6 設(shè)S=(X,R)是一個范圍空間,S的VC維是X被打碎的子集的最大基數(shù),記為VC(S)。

定義8 設(shè)T是一個不確定事務(wù)數(shù)據(jù)集,它的所有項的集合是I,則當(dāng)滿足條件(1)和(2)時,稱S=(X,R)是與T相關(guān)聯(lián)的一個范圍空間。

1)X=T

2)R={UT(X)|X?I}是事務(wù)的集合族,滿足對于任意的項集X,集合UT(X)={t∈T|X?t}是R的一個元素。

定義9 設(shè)T是一個不確定數(shù)據(jù)集,T中包含至少d條長度至少為d的事務(wù),那么這個最大的整數(shù)d稱為該數(shù)據(jù)集的d-索引。

3.3 代表頻繁項集的近似挖掘

在創(chuàng)建抽樣時,可以通過下面的定理獲得樣本空間大小的上界。

對于抽樣空間上的不確定數(shù)據(jù),具體的算法描述如下。

輸入：抽樣的不確定數(shù)據(jù)集S,用戶給定的最小期望支持度minESup,用戶指定的參數(shù)ε,δ,τ。

輸出：代表ε-近似頻繁項集R。

1.C←{X|X∈I}; //把所有的單項集存入集合C

3.C′←Apriori-Gen(L); //用Apriori-Gen()算法生成k+1項集

4.WhileC′≠φdo

5.ForeachX∈C′do

7.L′←L′∪X;

8.X.ES=ESup(X);

9.Endif

10.Endfor

11.ForeachY∈Ldo

12.flag←true;

13.ForeachZ∈L′do

14.IfY?Z∧Udist(X1,X2)≤τthen

15.flag←false;

16.Break;

17.Endif

18.Endfor

19.Ifflagthen

20.OutputY; //輸出代表ε-近似頻繁項集

21.Endif

22.Endfor

23.L←L′;

24.C′←Apriori-Gen(L);

25.Endwhile

4 實驗與性能分析

算法的運行時間如圖1所示,圖中比較了在選取不同的最小期望支持度閾值時所用的時間。在最小期望支持度閾值較大時,不確定數(shù)據(jù)集的d-索引較小,使得抽樣的數(shù)量減少,因此需要的運行時間會更少。算法的壓縮質(zhì)量如圖2所示,當(dāng)δ,ε設(shè)置為0.1時,隨著τ從0.1增加到0.5,壓縮率增加,得到的代表頻繁項集的個數(shù)在減少。

圖1 算法的運行時間

圖2 算法的壓縮質(zhì)量

5 結(jié)語

在不確定數(shù)據(jù)集中,當(dāng)數(shù)據(jù)量很大時,挖掘頻繁項集會得到數(shù)目巨大的頻繁項集,而采用挖掘代表頻繁項集的方法可以減少得到的項集數(shù)量。為了使算法能適用于大規(guī)模數(shù)據(jù),采用對數(shù)據(jù)集進行隨機抽樣的方法實現(xiàn)近似挖掘,這樣可以改善算法的可擴展性,提高算法的效率。在未來的研究中,將進一步對不確定流數(shù)據(jù)進行頻繁項集的挖掘。

[1] 汪金苗,張龍波,鄧齊志等. 不確定數(shù)據(jù)頻繁項集挖掘方法綜述[J].計算機工程與應(yīng)用,2010,47(20):121-125. WANG Jinmiao, ZHANG Longbo, DENG Qizhi, etc., Survey on algorithm of mining frequent itemsets from uncertain data[J]. Computer Engineering and Applications, 2011, 47(20):121-125.

[2] 李海峰,章寧,柴艷妹.不確定性數(shù)據(jù)上頻繁項集挖掘的預(yù)處理方法[J].計算機科學(xué), 2012,39(7):161-164,199. LI Haifeng, ZHANG Ning, CHAI Yanmei. Uncertain data preconditioning method in frequent itemset mining. Computer Science, 2012,39(7):161-164,199.

[3] 李建中,于戈,周傲英.不確定性數(shù)據(jù)管理的要求與挑戰(zhàn)[J].中國計算機學(xué)會通訊,2009,5(4):6-14. LI Jianzhong, YU Ge, ZHOU Aoying. Demand and challenge of managing uncertain data[J]. Communications of the CCF,2009,5(4):6-14.

[4] R. Agrawal, R. Srikant. Fast algorithms for mining association rules[C]//20thInternational Conference on Very Large Data Bases,1994:487-499.

[5] C. Aggarwal, P. Yu. A survey of uncertain data algorithms and applications [J].IEEE Transactions on Knowledge and Data Engineering,2009,21(5):609-623.

[6] Tong, Chen, Ding, Discovering threshold-based frequent closed itemsets over probabilistic data[C]//IEEE 28thInternational Conference on Data engineering,2012:270-281.

[7] Tang, Peterson, Mining probabilistic frequent closed itemsets in uncertain databases[C]//ACM Southeast Conference:2011,86-91.

[8] Liu, Chen, Zhang, Summarizing probabilistic frequent patterns: a fast approach[C]//ACM SIGKDD Conference on knowledge discovery and data mining, 2013:527-535.

[9] C. Chui, B. Kao, E. Hung, Mining frequent itemsets from uncertain data[C]//The Pacific-Asia Conference on Knowledge Discovery and Data Mining. Berlin Heidelberg: Springer-verlag, 2007:47-58.

[10] C. Chui, B. Kao, A decremental approach for mining frequent itemsets from uncertain data[C]//The Pacific-Asia Conference on Knowledge Discovery and Data Mining,2008：64-75

[11] T. Bernecker, H.-P. Kriegel, M. Renz, etc., Probabilistic frequent itemset mining in uncertain databases[C]//ACM SIGKDD Conference on knowledge discovery and data mining, 2009:152-161

[12] L. Wang, D.W. Cheung,R. Cheng, etc. Efficient mining of frequent itemsets on large uncertain databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2011,23(3):367-381

[13] Leung C K S, Carmichael C L, Hao B. Efficient mining of frequent patterns from uncertain data[C]// Workshops of IEEE International Conference on data mining,2007:489-494

[14] Liu, C., Chen,etc., Mining probabilistic representative frequent pattern from uncertain data[C]//SIAM International Conference on data mining,2013,73-81.

[15] Alon, N., Spencer, J.H, The Probabilistic Method[M]. 3rd. New Jersey: Wiley,2008

[16] Chazelle, B.. The discrepancy method: randomness and complexity[M]. Cambridge,2000.

[17] Vapnik, V.N., The Nature of Statistical Learning Theory[M]. New Jersey: Springer-Verlag,1999.

[18] M.Riondato, Eli Upfal, Efficient discovery of association rules and frequent itemsets through sampling with tight performance guarantees[J]. ACM Transaction Knowledge Discovery from Data, 2014,8(2):25-41.

[19] S. Har-Peled, M. Sharir. Relative (p,ε)-approximations in geometry[J]. Discrete & Computational Geometry, 2011, 45(3):462-496.

[20] Y. Li, P. M. Long, A. Srinivasan, Improved bounds on the sample complexity of learning[J]. Computer System Science, 2011,62,(3):516-527.

[21] Lffler, M., Phillips, J.M. Shape fitting on point sets with probability distributions[J]. LNCS,2009,5757,313-324.

Approximation of Representative Frequent Itemsets Mining in Uncertain Data

CHEN Fengjuan1,2

(1. Liaoning University of International Business and Economics, Dalian 116052) (2. College of Information Science and Technology, Dalian Maritime University, Dalian 116023)

Since mining frequent itemsets in uncertain data is the fundamental step of many data mining tasks, it has attracted much attention from lots of researchers. However, this work will find large amount of frequent itemsets when the dataset is huge. It puts an obstacle to the next work. To address this problem, an efficient approximation mining algorithm of representative frequent itemsets is proposed in this paper. In the method, the VC-dimension theory is used to reduce the size of sample and provide satisfactory performance guarantees on the quality of the approximation. The algorithm is based on random sampling to mine representative frequent itemsets. It improves efficiency of mining task and reduces the number of frequent itemsets.

uncertain data, representative frequent itemset, approximation algorithm, VC-dimension

2016年8月13日,

2016年9月25日

陳鳳娟,女,博士研究生,副教授,研究方向：數(shù)據(jù)挖掘和粗糙集。

TP311

10.3969/j.issn.1672-9722.2017.02.014