论文部分内容阅读
关联规则是数据挖掘研究的一个重要内容,通过采用支持度和置信度去除非频繁项获得目标关联规则。对支持度分布严重倾斜的数据集挖掘时,传统的频繁项集挖掘算法不能有效适用于一些重要的挖掘任务,支持度阈值很难确定,过高则会有置信度较高的规则遗漏,过低则会得到大量可信度较低的冗余规则。挖掘关联规则效率和准确性,是数据挖掘研究的重点。极大团是无向图G最大的全连通分量,旨在将关联性强、可能产生极大频繁项的项集生成极大团,之后再针对每一个极大团求解极大频繁项集。并快速产生所有可靠关联规则,提高时间效率。本文通过对经典算法APriori算法和FP-growth算法的工作原理和机制以及极大团算法等理论进行深入研究,总结它们的优缺点。在此基础上,针对目前关联规则存在的问题展开研究,主要的研究工作如下：1.针对挖掘项目支持度不均匀分布的数据集很难设置合适的支持度阈值的问题,提出了基于极大团的加权可信关联规则算法MCWCAR (Maximum Clique Weighted Credible Association Rule)。通过定义加权可信关联规则和2-项加权可信集的基本概念,并利用2-项邻接矩阵来产生2-项加权可信集,得到对应的稀疏图；对于由稀疏图求出的每个连通分量,由前k-1个顶点构成所有极大团,再将第k个顶点加入(k-1)-极大团中,得到k-项加权可信集,完成极大团的加权可信关联规则挖掘过程。以解决不均匀分布的数据集难设置合适的支持度阈值的问题,并避免多次扫描数据库和频繁生成模式树,减少项集支持度的计算量。最后通过实验验证所提出的算法MCWCAR比传统算法在挖掘关联规则的时间性能和准确性具有更高的效率。2.针对目前数据挖掘中存在对长模式挖掘效率低和挖掘方式不完整等问题,提出基于动态图的Top-N极团模式挖掘算法CSDGMPA (Clique Search With Dynamic Update Of Graph Based Maximum Pattern Mining Algorithm).算法在提出2个剪枝规则的基础上,通过剪枝无效团和扩展团两个阶段精确地识别Top-N极大团,最后采用深度优先分支定界的算法寻找长度为Top-N的极大模式。所提出的算法能在基于K-项模式图构建的图中发现以团的形式出现的目标模式。随着图表动态地稀疏化,使得寻找团的过程更加高效,优化了搜索过程,提高剪枝准确性。最后,通过仿真实验,将CSDGMPA算法和传统算法MAXIA和LCM进行对比,验证了CSDGMPA算法在时间花销等方面的优越性。