析取空间中频繁项集精简表示模型研究

发布时间：2020-06-05 21:21

【摘要】：频繁模式挖掘是数据挖掘领域的经典课题。频繁模式挖掘在实际应用中的基本问题是频繁模式通常数量庞大,冗余严重。究其原因,主要是因为传统挖掘方法基于刚性的支持度-置信度阈值来区分模式,由于受到数据中随机噪声的影响,容易导致实际相同的模式因为细微差异而被挖掘系统认作了不同的模式。为此本文致力于研究利用析取空间的项集模式来设计频繁模式精简表示模型,以消除频繁模式挖掘结果集中存在的冗余。本文的主要研究工作如下:(1)针对析取空间中的析取模式,本文研究发现,析取模式集中仍然存在着模式冗余现象,因随机噪声造成的这一类冗余,具有局部和扰动量微小等特点。为此,本文引入析取模式的δ-邻域概念,以消除随机噪声造成的冗余,并以此为基础,提出一种新的频繁模式精简表示模型。分析了此模型的性质和频繁模式恢复的精度和算法策略等问题,并利用深度优先递归搜索方法,辅以启发性策略,设计了高效率的精简的析取模式集挖掘算法DCPM。实验结果表明,通过该模型得到的精简集,规模比传统析取闭合项集明显减少,并且恢复全体频繁项集的支持度错误也较小。(2)在δ-邻域划分过程中,本文研究发现,多组不同δ-邻域之间会存在重叠现象,而且这种重叠现象十分广泛,对于重叠现象处理不当,会导致支持度恢复误差加大,甚至在最终结果集中引入冗余。本文提出从中继节点、交叉节点和替代集析取支持度等三个方面,来解决δ-邻域划分的最优化问题,并据此对算法DCPM进行改造形成了新算法NDCPM。利用DCPM算法中使用的有效技术改造MEP形成了算法NFMEP。实验结果表明,NDCPM算法挖掘结果更精确,NFMEP具有较高的执行效率。
【图文】：

流程图,核心项,流程,最小支持度

对于表２．１示例数据库Ｚ），给定最小支持度／ｍ＿ｍｗｐ＝０．１２５。以项集丨ＡＣＤ｝和逡逑｛ＡＣ｝为例，，分析它们是否是频繁核心项集的过程。判断她们是否是频繁核心项集逡逑的过程如图３．２所示。为了直观地表示某个项４是否在事务中出现，用０和１逡逑进行描述。若项４在事务／；．中出现，则它们之间构成的二元关系的对应位用１表逡逑不，否则用０表不。逡逑对于表２．１示例数据库，给定最小支持度Ｍｆｒａｗｐ＝０．１２５。根据定理３．１，｛ＡＣ｝逡逑和｛ＡＣＤ丨是否是频繁核心项集的判断流程如下：｛ＡＣ｝ｅ／，ｇ（ＡＣ）Ｑ／（Ａ）＝｛５，８｝，逡逑２３逡逑

邻域,性质,核心项,深度优先搜索树

逑剪枝步３．２：由性质３．６可知，在求解７的矣邻域过程中，若Ｚ逡逑的子集都不属于７的邻域。如图３．３所示，／ｍ＞ｍ（ｐ＝０．１２５，５＝ｌ时，NBＳｃｔ／？ｅ／？（ＡＢＣ，Ｊ），逡逑求解ＡＢＣ的表邻域时，ＡＢ的子集都不需要进行判断。逡逑深度优先搜索树逡逑频繁核心项集搜索过程中，存在路径逡逑、Ｉ邋＾逦ｒｏｏｔ—＞邋Ａ—＞邋ＡＣｒ＾邋ＡＣＤ；逡逑３＾－Ｌｖ逦有：ＡＣｃＡＳｗＸｖＡＱ＾ｗＡｖＡＣＤ），逡逑逦（Ａ）逦则：ＡＣＤ＜ｚｆ。逡逑／＂逦性质３．５可知：ＡＣＤ剪枝，不再向下拓展。逡逑ｉｒＱｐ邋？逡逑Ｈ，邋Ｔ逦，邋＾逦求ＡＢＣ的邻域时，对于路径逡逑（＾ＡＣＤ＾）逦ｒｏｏｔ－＞邋Ａ－＞ＡＢ－＞邋ＡＢＣ：逡逑ＶＬｙ逦有：／ｒ（ＡＢＣ＞＝ＡＢＣＤ，ＡＢ＜ｚ／ｔｅ／？（ＡＢＣ，ｌ），ＡｅＡＢ，逡逑＊（ＡＢＣ）＝｛ＡＢＣＤ｝逦性质３．６可知：ＡＢ的子集不属于ＡＢＣ＾Ｊ邻域集合
【学位授予单位】：合肥工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13

【参考文献】