陳鳳娟

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

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

陳鳳娟1,2

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

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

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

Class Number TP311

1 引言

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

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

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

2 基本概念及問題描述

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

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

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

(1)

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

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

(2)

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

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

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

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

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

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

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

(3)

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

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

3 代表頻繁項(xiàng)集的近似挖掘

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

3.1ε-近似頻繁項(xiàng)集

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

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

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

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

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

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

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

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

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

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

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

1)X=T

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

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

3.3 代表頻繁項(xiàng)集的近似挖掘

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

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

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

輸出：代表ε-近似頻繁項(xiàng)集R。

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

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

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; //輸出代表ε-近似頻繁項(xiàng)集

21.Endif

22.Endfor

23.L←L′;

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

25.Endwhile

4 實(shí)驗(yàn)與性能分析

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

圖1 算法的運(yùn)行時(shí)間

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

5 結(jié)語

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

[1] 汪金苗,張龍波,鄧齊志等. 不確定數(shù)據(jù)頻繁項(xiàng)集挖掘方法綜述[J].計(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ù)上頻繁項(xiàng)集挖掘的預(yù)處理方法[J].計(jì)算機(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].中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊,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