不确定数据频繁闭项集挖掘算法

1、不确定数据频繁闭项集挖掘算法： Due to the downward closure property over uncertain data ， existing solutions of mining all the frequent itemsets may lead an exponential number of results. In order to obtain a reasonable result set with small size，frequent closed itemsets discovering over uncertain data were studie

2、d ， and a new algorithm called Normal Approximationbased Probabilistic Frequent Closed Itemsets Mining （ NAPFCIM） was proposed. The new method regarded the itemset mining process as a probability distribution function ， and mined frequent itemsets by using the normal distribution modelwhich supports

3、 large databases and canextract frequent itemsets with a high degree of accuracy. Then，the algorithm adopted the depthfirst search strategy to obtain all probabilistic frequent closed itemsets ， so as to reduce the search space and avoid redundant computation. Two probabilistic pruning techniques in

4、cluding superset pruning and subset pruning were also used in this method. Finally ， the effectiveness and efficiency of the proposed methods were verified by comparing with the Possion distribution based algorithm called APFCIM. The experimental results show that NAPFCIM can decrease the number of

5、extending itemsets and reduce the complexity of calculation ， it has better performance than the compared algorithm.0 引言频繁项集挖掘 1 是数据挖掘研究中的一个重要内容，在关 联规则、序列模式等方面有着广泛研究。尽管大量文献 2-7 就 频繁项集挖掘提出了各种算法， 但挖掘所得到的频繁项集的数量 往往大得惊人，影响着结果的理解和应用。针对以上问题，研究 者们提出了一些改进方案， 主要思路是只产生频繁项集中具有代 表性的子集， 如最大频繁项集和频繁闭项集， 前者可满足某些具 体

6、问题的需要， 但不记录最大频繁项集子集的支持度， 因而不便 于产生关联规则， 而频繁闭项集则是所有频繁项集的无损压缩表 示。频繁项集F,最大频繁项集 M频繁闭项集C三者之间的关 系是MCF文献8-10普遍认为挖掘频繁闭项集是比较好的一个 选择。由于不确定数据的广泛存在，Tang等11提出了一个挖掘 概率频繁闭项集的算法，只挖掘那些概率频繁项集 I ，满足的条 件是找不到I的任何超集I '（即I ' I）的概率支持度等于I的 概率支持度。该算法用的主要思想仍是Bernecker 等4 中的动态规划方法计算给定项集的概率支持度，以及基于 Apriori 的候选枚举算法。 Peter

7、son 等12 提出了用泊松分布近似泊松二项分布的方法计算不确定数据中项集的支持度概率质量函数， 挖掘 近似的概率频繁闭项集。 Bernecker 等 13 又提出了在不确定数 据上挖掘频繁项集的基于模型的算法。 主要考虑了用两种概率分 布模型 （泊松分布和正态分布） 来计算项集的支持度概率质量函 数值。他们用大量的实验证明了正态分布模型的结果要优于泊松 分布模型。 泊松近似虽然容易实现高效的计算，但是为 了获得好的近似结果， 这个模型几乎要求所有的事务都要以一个 较低的概率包含项集 I 。这个要求在真实的数据中是难以符合的， 因为真实的数据集一般会存在某一事务中含有 I 的概率是 1。所 以

8、，泊松模型的鲁棒性不强， 稍大一些的概率就会显著降低近似 质量。采用正态近似必须确保使用连续性校正， 才能获得最好的 结果。对于近似的质量， 即准确度， 正态分布是目前结果最好的。 即使少量的泊松实验， 正态分布也能产生较高精度的结果。 很多 真实的数据集可以用正态分布很好地描述。 因此， 本文也倾向于 使用正态分布的近似方法。同时一些研究确定性数据的文献中 8 ， 14证明了通过一些剪枝策略深度优先搜索在判断项集是否 封闭时比广度优先效果更好，效率更高，因此，本文提出了将正 态分布概率模型与深度优先搜索策略相结合的算法， 来挖掘频繁 闭项集。1 相关定义1.1 确定数据上的频繁闭项集给定不同

9、项的集合I=i1 , i2，称I的一个非空子集X 为一个项集。如果X中有k个项组成，则称X为k项集。给定一 个确定性的事务数据库 D,每条事务都用一个元组tid , X表 示，其中tid是事务标识符。D中包含X的事务数记为X的支持 度，用support （X）表示。定义1频繁项集。给定一个最小支持度阈值 minsup，项集X 是频繁的，当且仅当support （ X）大于等于min sup。定义2封闭项集。项集X是封闭的，当且仅当找不到X的任 何超集 Y 满足 support （ Y） =support （ X）。定义3频繁闭项集。项集X是频繁闭项集，当且仅当它是频繁的，且找不到任何超集 Y

10、（YX）满足support （Y）=support（ X）。1.2 不确定数据上的频繁闭项集在不确定数据中，只有项集X的支持度概率分布，该分布服 从高斯分布。本文可以按照文献 4， 9， 11， 15定义频繁概率和 概率频繁项集。定义4频繁概率。给定一个最小支持度阈值 minsup，项集X 的频繁概率是指X的支持度大于等于min sup的概率，记作Prfreq（ X）。定义5概率频繁项集。给定一个最小支持度minsup 0 ,n，和置信度（概率频繁阈值）t 0 , 1，如果项集X的频繁 概率大于概率频繁阈值，则 X 是一个概率频繁项集，即Pr (support (X)> min sup)

11、 =Prfreq (X)> t (1)定义6概率支持度。项集X在置信度t下的概率支持度ProbSup (X, t)定义如下：ProbSup (X, t ) =arg maxi 0 , n (Pr (support (X)> i )> t)( 2)定义7概率频繁闭项集。项集X是概率频繁闭项集当且仅当Prfreq ( X)>t，且找不到任何项集 X的超集Y (YX),满足 ProbSup( Y, t ) =ProbSup( X, t )。本文以表 1中的不确定数据为例进行介绍。 表 1记录了顾客 Jack 和 Mary 的购买行为细节,每一项后面的值表示顾客在不久 的将来可

12、能购买该物品的可能性。 这些概率值可以通过分析用户 的浏览历史得到。例如,如果 Jack 在之前的一周访问了商场 10 次,其中 video 这个物品被点击了 5 次,那么可以得出 Jack 有 50%的可能买 video 。假设 X=video , t =0.5 , minsup=1。X 出现 0 次的概率 P0 (X)指在两条事务中都不出现的概率，X出现1次的概率P1 (X)指在两条事务中各出现1次的概率，出现两次的概率 P2 (X)指 在两条事务中均出现的概率。计算结果如下：第1)10)行用于计算 卩I和彷12 ;第12)13)行判 断项集的频繁性，如果项集I出现min sup次的概率小

13、于t ,返 回-1 ,说明该项集不是概率频繁的;第15) 20)行在项集 I满足概率频繁的条件之后,获得项集 I 的概率支持度,返回的 i-1 即是项集 I 的概率支持度。2.2 基于深度优先搜索策略的挖掘树前缀挖掘树（Mining Tree , MT）中的每个节点存储以下信 息：1）项集I本身nI ; 2）节点nI的类型；3）项集I的概率 支持度 ProbSup（ nI ）。同时，用一个哈希表 hashclosed 来维 护概率频繁封闭项集，其中存放项集信息及对应的概率支持度。 相对于挖掘频繁项集来说，挖掘频繁闭项集有更高的算法复杂 度，耗时更长，所以希望在挖掘频繁闭项集时，用深度优先搜索

14、的方法代替挖掘频繁项集时的广度优先算法，同时在前缀树中， 使用超集修剪和子集修剪策略删减项集， 缩小搜索空间， 以获得 更高的挖掘效率。1） 超集修剪。给定一个项集 X，它的大小是|X|，X的超集 X+ei，大小为|X|+1，如果ei在词典序上比X中的至少一个项还 小（即按照词典序，X不是X+ei的前缀），且ProbSup（X）=ProbSup（X+ei），那么X不是频繁闭项集，且按照词典序以X为前缀的所有超集也不是频繁闭项集。2）子集修剪。给定一个项集 X，X的子集X-ei，按照词典 序 ei 是 X 中的最后一项。如果 ProbSup（X） =ProbSup（X-ei ）， 那么 X-ei

15、 不是频繁闭项集，且大小为 |X| ，有相同前缀 X-ei 的 项集不是频繁闭项集。基于以上两条规则，可以删减所建树结构中的大量无用节 点，减少内存占用及搜索空间，提高效率。hashcheck （ nI ）其实就是超集修剪，它是直接查找哈希表hashclosed ，看是否存在已经找到的和 nI 有相同概率支持度， 且包含 nI 的概率频繁闭项集。如果 hashcheck （nI ）为 true ， 表示找到了满足条件的概率频繁闭项集，那么 nI 就不可能是封 闭的，不再向下扩展 nI ；如果 hashcheck （nI ）为 false ，则扩 展nI ,将频繁的右兄弟节点和nI组合生成孩子节

16、点。第1）3） 行判断项集的频繁性，只处理频繁的项集；第5 ）12）行扩展项集，生成后代节点；第 13） 17）行判断项集的封闭性，其 中第 13）14）行是子集修剪，判断完毕之后，将概率频繁闭 项集压入哈希表中。3 实验结果与分析下面将NAPFCIMI法与基于泊松分布的频繁闭项集挖掘算 法APFCIM算法12进行对比。实验算法用C+语言编写，在VS2010环境下编译运行，运行环境是Intel Core i3 2.13GHzCPU 2GB内存，Windows7操作系统。由于无法获得真实的不确 定数据集， 所以按照文献 12 中的实验方法， 由真实的确定数据 集和仿真的确定数据集生成不确定的数据

17、集，使用的方法如下： 将事务中的每个确定的项复制到新的不确定数据集中； 对该项按 照a =5, B =1的beta分布随机生成一个概率 p（ 0, 1；最 后，将 p 和 1-p 以 1/2 的概率分配给该项。 实验数据集按照文献 12 ，以常用的几个数据集 （T10I4D100K、Accidents 、Mushroom、 Chess）作比较。数据集特性如表 2所示。由于，min sup/n和t是用户可以自定义的两个参数，因此，本文将NAPFCIM和APFCIM在四个数据集上调整这两个参数后的 运行时间变化进行实验比较。图1是t =0.9 , min sup/n （n为数据集中的事务数）变化时

18、， 两个算法在以上四个数据集上的运行时间。 minsup/n 越大，表 示满足条件的频繁项集越少， 即所要扩展的项集规模减小。 因此， 随着 minsup 的增加，运行时间逐渐减小。可以注意到， T10I4D100k 基本不受 minsup/n 参数的影响，原因是该数据集比 较大且稀疏，所以即使对于 minsup/n 取很小的值的情况下，也 不受影响。图 2 是 minsup/n=0.35 ，t 变化时， 两个算法在以上四个数 据集上的运行时间。由于不管 t 如何变化，每次都需要对频繁 项集的概率与 t 比大小，才能获得概率支持度，所以，运行时 间的变化不会随着 t 的变化有所影响；而且还可看出运行时间 与 t 呈线性关系。从图12的对比可看出：本文算法在每个数据集上的运行 时间