不确定性数据流上的频繁项集挖掘关键技术研究

静态不确定性数据的挖掘算法开销庞大，难以应用到快速、无限且动态变化的数据流环境中。本项目将围绕计算效率、存储开销、结果实用性和实际应用四个大问题展开系统研究，旨在提出数据流环境中计算资源和存储资源受限时不确定性数据的高质量实时挖掘方法：首先建立不确定性数据频繁项集的合理概念，研究该定义的增量式计算模型和存储方法，采用混合遍历方式和基于数学模型的剪枝策略实现高效实时的挖掘算法；然后提出基于存在概率的项集精简表示方法和挖掘算法，以减少存储开销；进一步，探讨利用参数自适应的Top-k方法实现不确定性数据挖掘的结果质量优化策略，采用SKYLINE方法建立频繁项集挖掘的多目标优化机制；最后，重新定义不确定性数据的关联规则，实现动态的关联规则挖掘算法。本项目的研究可望加强对不确定性数据挖掘问题的认知，为数据挖掘基本技术的研究方向提供新思路，同时算法效率和实用性的提高可以推进信息技术在社会发展中的应用。

本项目对不确定性数据上的频繁项集挖掘算法展开了全面而系统的研究工作，目前已经在不确定性数据的预处理、时间敏感数据流上的频繁项集挖掘、闭合频繁项集挖掘、最大频繁项集挖掘等4个主要方面取得了进展，并在自适应频繁项集挖掘方面和关联规则挖掘方面有了初步的研究结论。.1）提出了基于主成分分析的不确定数据的预处理方法，该方法能够在频繁项集挖掘的过程中有效缩减数据的维度和规模，能够提高数据挖掘的效率。.2）提出了不确定性数据的静态和动态最大频繁项集的挖掘算法，利用Chernoff Bound来构建概率支持度计算的范围，利用数据分布的特性来近似计算概率支持度，将计算代价降低了一个数量级。.3）提出了不确定性数据流上的频繁项集挖掘的算法，分别以滑动窗口模型和界桩模型分别实时和批处理实现频繁项集挖掘，能够精确的或者近似的获取数据挖掘的结果。同时，讨论了关联规则的挖掘方法。.4）提出了数据流上基于界碑模型的最大频繁项集挖掘算法，采用一种称为MFIODSLT的数据结构增量的维护最大频繁项集与部分附属信息，能够实现快速的项集查找和裁剪。提出了另外一种最大频繁项集挖掘的算法，利用一种FP-FOREST的数据结构，结合已有算法对数据进行压缩和动态维护，能够提供挖掘的效率。提出了一种结果为False Negative的最大频繁项集挖掘算法，利用Chernoff Bound来减少由于数据流挖掘产生的冗余挖掘结果，大大降低了内存使用的代价。.5）提出了针对时间敏感数据流的频繁项集挖掘的算法，引入了类型变化界限的概念，将项集进行动态分类，根据滑动窗口大小的变化对项集进行延迟处理，仅当项集的类型变化界限超出一定阈值的时候才进行支持度的重新计算，使得剪枝后算法的效率大大增强。.6）提出了改进的时间敏感数据流的频繁项集挖掘的算法，利用启发式规则扩展类型变化界限，使得大量的冗余计算得以忽略，从而提高算法的效率。.基于以上研究，目前共有13篇学术论文被发表和录用，9篇论文被SCI或EI收录。其中，1篇发表在SCI国际期刊《Knowledge-based Systems》，2篇发表在EI国际期刊《Journal of Software》和《Journal of Information & Computational Science》，2篇发表在一级期刊《计算机学报》上，4篇发表在《计算机科学》等国内核心期刊。