面向不确定数据的闭项集挖掘方法

摘要

本发明公开了一种面向不确定数据的闭项集挖掘方法，用于解决现有闭项集挖掘方法精度差的技术问题。技术方案是：在挖掘闭项集时，首先将不确定数据转换为确定数据，再通过递归调用DCI_Closed()算法来建立新的生成子和相应的闭项集。在概率频繁闭项集过滤时，首先计算闭项集集合中单项集的概率频繁；再计算所有闭项集子集的概率频繁，利用卷积的计算方式得到项集的频次分布特征。最后，在项集生成的过程中，使用合理的剪枝技术加快项集的生长过程。本发明方法直接从不确定数据对应的原始数据中挖掘闭项集，再对其进行概率频繁特性的过滤，挖掘不确定数据中的概率频繁闭项集的精度高，而且进一步提高了挖掘效率。

主权项

一种面向不确定数据的闭项集挖掘方法，其特征在于包括以下步骤：步骤一、挖掘闭项集；首先，将不确定数据作为确定数据；数据集D扫描决定1‑频繁项建立垂直数据集VD；VD包括tid列表g(i)，假设和记录所包含的项集，如果有的话，这个单项会出现在数据集中的所有事务中；通过利用POST_SET中的项拓展CLOSED_SET以产生所有可能生成子，非频繁且不保序的生成子是被当作无效的；记录这些属于POST_SET的项，如果曾经是包含在上述生成子之中的，在随后的递归调用过程是不再被考虑的，只有有效的生成子可以被拓展；每一个生成子new_gen←CLOSED_SET∪i是严格的依据保序性被拓展的，通过使用所有属于POST_SET的项拓展，记录POST_SET中所有的不属于生成子和用于下次递归调用的项j(i<j)；产生一个新的闭合集CLOSED_SET_new←c(new_gen)；从新的闭项集中，通过递归调用DCI_Closed()来建立新的生成子和相应的闭项集；最后，为了能够按词典序的顺序访问，必须按照字典序的顺序从POST_SET中提取项；使用DCI算法挖掘出所有的闭项集，Cset＝{{a b},{a b c}}；步骤二、概率频繁闭项集过滤；根据确定数据挖掘的频繁闭项集及其子集和不确定数据的闭项集等价，计算由步骤一得到的闭项集及其子集的频繁闭概率值，过滤概率非频繁项集；基于边界的Chernoff‑Hoeffding剪枝：给定项集X，不确定数据集UD，X的预期支持度μ，最小的支持度阈值min_sup，频繁闭概率的阈值pfct，项集X是概率非频繁的条件是：$\left\{\begin{array}{cc}{e}^{-2n^2{\delta }^2}<\mathrm{pfct},& \delta >\mu \\ e^{-2n{\delta }^2}<\mathrm{pfct},& \delta <\mu \end{array}\right.$δ＝(min_sup‑μ‑1)/n，n是UD中事务的数量；超集剪枝：给定长度为|X|的项集，不确定数据集UD和X的长度为|X|+1的超集X+e_i；按照字母顺序，至少小于X中的一个项，即X不是X+e_i的前缀，并且X.sup＝(X+e_i).sup能够得到如下的两个结果：1)X的频繁概率是0，X必然不是概率频繁项集；2)基于字母顺序，所有以X为前缀的超集必然不是概率频繁项集；以{a}为前缀基于深度优先搜索的超集剪枝方法，能够避免生长{ac,fcp:0}，{bc,fcp:0}；子集剪枝：给定不确定数据集UD，项集X，X是X‑e_i的超集，e_i是X的最后一个项，如果X.sup＝(X‑e_i).sup，得到以下两个结果：1)X‑e_i的频繁概率是0，必然不是概率频繁项集；2)含有X‑e_i作为前缀的项集，如果长度相同，则能够判断必然不是频繁的概率项集，这样的项集超集也必然不是频繁的概率项集。