不确定数据中的代表频繁项集近似挖掘

陈凤娟

(1.辽宁对外经贸学院 大连 116052)(2.大连海事大学信息科学技术学院 大连 116023)

不确定数据中的代表频繁项集近似挖掘

陈凤娟1,2

(1.辽宁对外经贸学院 大连 116052)(2.大连海事大学信息科学技术学院 大连 116023)

不确定数据的频繁项集挖掘作为很多数据挖掘任务的基本步骤,引起了很多学者的关注。但是当不确定数据集的规模很大时,会产生数目巨大的频繁项集,给后续挖掘工作带来难题。为解决这一问题,论文提出不确定数据集中的代表频繁项集概念,并利用VC维的概念,确定抽样空间,提出一种基于随机抽样的代表频繁项集近似挖掘算法,在保证挖掘效果的前提下,减少了挖掘出的频繁项集的数量,提高算法的效率。

不确定数据; 代表频繁项集; 近似算法; VC维

Class Number TP311

1 引言

不确定数据广泛存在于各种应用中,如无线传感器网络、社交网络和各种科学研究的实验,对不确定数据的挖掘和分析不仅可以为决策提供有力的工具,也可以发现这些不确定数据中隐藏的重要的规律[1～3]。

不确定数据集包含了很多有用的信息,可以通过在不确定数据中挖掘频繁项集来发现这些信息。频繁项集挖掘是很多数据挖掘任务的基础步骤,尤其是关联规则挖掘[4～5]和图挖掘等,它能找出数据集中多次共同出现的数据项。随着各种技术的发展,需要分析的不确定数据的数据量在不断增加,在这种大规模的不确定数据中,频繁项集的数量也是巨大的,不利于后续工作的进行。为了减少频繁项集的冗余,可以用最大频繁项集、频繁闭项集或代表频繁项集来压缩表示频繁项集[6～8],而代表频繁项集可以通过参数的设置来调节压缩效果,是一种比较好的压缩表示。文献[8]提出一种在不确定数据集中挖掘概率代表频繁项集的近似算法,该方法提出概率代表频繁项集的概念并给出挖掘概率代表频繁项集的近似算法,但是该算法不适用于大规模不确定数据集。

为了解决大规模不确定数据集中的代表频繁项集挖掘问题,本文给出了一个适用于大数据集的代表频繁项集的概念,然后定义ε-近似频繁项集,并提出一种基于VC维理论保证在至少是1-δ的概率下,挖掘不确定数据集的代表ε-近似频繁项集的随机抽样的算法,实现从大规模不确定数据集中挖掘代表频繁项集的近似集合,由于算法每次抽取的样本量远远小于整个数据集的大小,因此,算法可扩展性好,能适用于大规模不确定数据集。

2 基本概念及问题描述

2.1 不确定数据集中的频繁项集

假设存在一个项的集合I和一个事务的集合T,其中,I={x1,x2, …,xm},T={t1,t2,…,tn}。I中的每个元素x称为项,I中任意个项的组合称为项集X,T中的每个元素t称为一个事务,并且,T中的每条事务t都是由I中的某些项x和P(x∈t)组成的。对于任意的项x∈I,都有一个存在概率P(x∈tj)∈[0,1],表示项x在事务tj中出现的可能性大小。当P(x∈tj)=0时, 表示项x在事务tj中不存在；当P(x∈tj)=1时, 表示项x在事务tj中一定存在；当0

在不确定数据集中,可以根据每个项的存在概率,得到不确定数据集的可能世界的语义解释,根据项是否在某个事务中出现,不确定数据集会出现2|T|*|I|个可能世界。在假设不确定数据集中的事务是相互独立的前提下,每个可能世界w的概率P(w)定义为[10]

(1)

对于不确定数据集中的频繁项集,存在两种定义方式,一种是以项集的期望支持度为标准进行判断,另一种是以项集的频繁概率为标准进行判断[11]。基于期望支持度的概念,计算简单,但是会丢失一部分有用的信息,而基于频繁概率的定义,能很好的保留不确定数据集中的全部有用信息,但是计算量很大。文献[12]中已给出详细的分析,并证明了在数据量很大的情况下,可以用期望支持度来代替频繁概率,作为挖掘频繁项集的标准,既能减少运算量,也能保证算法的精度。本文研究的是大规模不确定数据集中的频繁项集的压缩挖掘,因此,采用下面的期望支持度的定义。

定义1 在不确定数据集T中,对于任意一个项集X,它的期望支持度定义为该项集在所有的事务中出现的概率之和,记为ESup(X),即

(2)

文献[9]根据定义1,提出了不确定数据中的频繁项集挖掘问题,即对于一个不确定数据集T,给定一个最小的期望支持度阈值minESup,如果项集X的期望支持度大于给定的minESup,则称X在该不确定数据集中是频繁的,否则,X是不频繁的。

2.2 不确定数据中的代表频繁项集

在确定数据中,文献[13～14]定义了两个项集的距离测量方式和近似覆盖概念,并基于这两个概念,提出了确定数据库中的代表频繁项集。

给定一个实数τ,τ∈[0,1],如果X1⊆X2并且dist(X1,X2)≤τ,则称项集X1被项集X2τ-近似覆盖。

代表频繁项集是指能τ-近似覆盖所有频繁项集的最小项集的集合。

本文把这些概念推广到不确定数据集中,提出不确定数据集中两个项集的距离测量和近似覆盖以及代表频繁项集的概念。

根据文献[9]中期望支持度的概念可得,如果X1⊆X2,则有

(3)

定义3 给定一个不确定数据集T,项集X1和X2,实数τ∈[0,1],如果X1⊆X2并且Udist(X1,X2)≤τ,则称项集X1被项集X2τ-近似覆盖,若项集X1是频繁项集,则称X2是X1在不确定数据集中的代表频繁项集。

给定一个不确定数据集T,频繁项集F,任意实数τ∈[0,1],代表频繁项集挖掘是找出最小的频繁项集集合R,使得对于任意的一个频繁项集X,X∈F,都存在一个代表频繁项集X′,X′∈R,满足X′能τ-近似覆盖X。

3 代表频繁项集的近似挖掘

代表频繁项集可以压缩表示频繁项集,减小集合中项集的个数,一种简单的挖掘频繁项集的方法是先挖掘出不确定数据集的频繁项集,然后根据代表频繁项集的定义,从中找出代表频繁项集。但是这种方法不适用于大规模数据集,因为频繁项集的挖掘需要消耗大量的时间。为了在大规模数据集中快速的挖掘出代表频繁项集,下面提出一种基于抽样的近似算法,挖掘在1-δ的概率保证下,不确定数据集的代表ε-近似频繁项集。首先给出ε-近似频繁项集的定义,然后介绍近似挖掘的理论依据,最后给出近似挖掘算法的框架。

3.1ε-近似频繁项集

由于算法采用对大规模数据集进行抽样的策略进行挖掘,因此,给出频繁项集的绝对近似集的定义。

定义4 设T是一个不确定事务数据集,它的所有项的集合是I,最小期望支持度是minESup,该数据集的频繁项集记为F,0<ε<1,集合A是由项集X和该项集的近似期望支持度AEsup(X)构成的数据对组成的集合,即A={X,AEsup(X)|A∈2I,AEsup(X)∈[0,1]}。如果A满足下面的三个条件,则称集合A是频繁项集F的绝对ε-近似。

1)A中包含F中出现的所有项集。

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

3)A中任意一个数据对(X,AEsup(X)),都满足|ESup(X)-AEsup(X)|≤ε。

在对数据集进行抽样的过程中,要保证挖掘出的近似频繁项集是原有频繁项集的ε-近似,这样在这个频繁项集基础上得到的代表项集才能满足后续任务的需求。

3.2 不确定数据集的VC维

空间中一些点的VC维是一种衡量空间上定义的指导函数族的复杂度的方法,一个结构的VC维的有限边界表明该结构上的一个近似学习所需要的随机抽样个数的边界[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 设S=(X,R)是一个范围空间,S的VC维是X被打碎的子集的最大基数,记为VC(S)。

定义8 设T是一个不确定事务数据集,它的所有项的集合是I,则当满足条件(1)和(2)时,称S=(X,R)是与T相关联的一个范围空间。

1)X=T

2)R={UT(X)|X⊆I}是事务的集合族,满足对于任意的项集X,集合UT(X)={t∈T|X⊆t}是R的一个元素。

定义9 设T是一个不确定数据集,T中包含至少d条长度至少为d的事务,那么这个最大的整数d称为该数据集的d-索引。

3.3 代表频繁项集的近似挖掘

在创建抽样时,可以通过下面的定理获得样本空间大小的上界。

对于抽样空间上的不确定数据,具体的算法描述如下。

输入：抽样的不确定数据集S,用户给定的最小期望支持度minESup,用户指定的参数ε,δ,τ。

输出：代表ε-近似频繁项集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所示,图中比较了在选取不同的最小期望支持度阈值时所用的时间。在最小期望支持度阈值较大时,不确定数据集的d-索引较小,使得抽样的数量减少,因此需要的运行时间会更少。算法的压缩质量如图2所示,当δ,ε设置为0.1时,随着τ从0.1增加到0.5,压缩率增加,得到的代表频繁项集的个数在减少。

图1 算法的运行时间

图2 算法的压缩质量

5 结语

在不确定数据集中,当数据量很大时,挖掘频繁项集会得到数目巨大的频繁项集,而采用挖掘代表频繁项集的方法可以减少得到的项集数量。为了使算法能适用于大规模数据,采用对数据集进行随机抽样的方法实现近似挖掘,这样可以改善算法的可扩展性,提高算法的效率。在未来的研究中,将进一步对不确定流数据进行频繁项集的挖掘。

[1] 汪金苗,张龙波,邓齐志等. 不确定数据频繁项集挖掘方法综述[J].计算机工程与应用,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] 李海峰,章宁,柴艳妹.不确定性数据上频繁项集挖掘的预处理方法[J].计算机科学, 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] 李建中,于戈,周傲英.不确定性数据管理的要求与挑战[J].中国计算机学会通讯,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日

陈凤娟,女,博士研究生,副教授,研究方向：数据挖掘和粗糙集。

TP311

10.3969/j.issn.1672-9722.2017.02.014