可信关联规则挖掘算法研究

论文摘要

关联规则挖掘是数据挖掘领域中一个重要研究内容。传统的关联规则挖掘算法大都基于支持度-置信度框架,利用支持度去除非频繁项集,利用置信度得到较为有效的关联规则。对支持度分布严重倾斜的数据集挖掘时,人们发现现有算法无法选择合适的支持度阈值。若将最小支持度设置较高,会遗漏支持度较低但令人感兴趣的规则,若设置较低,则挖掘结果会含有大量虚假规则,对用户没有实际意义。本论文针对上述问题,围绕如何得到可信有效的关联规则展开研究,创新点和主要工作如下：1.提出可信关联规则的概念可信关联规则中各个项目的支持度处于同一数量级,一个项目的出现很强的暗示了规则中其他项目也会出现,即规则中的各个项目在很大程度上是同现的。挖掘这种规则时,可以忽略支持度阈值,因此可同时得到频繁模式和非频繁模式。对于可信关联规则的兴趣度量,本文提出基于可信度的度量,并引入基于距离测度的度量及h-置信度等。实验结果表明,可信关联规则在很多数据集中都会存在,其可信程度远远大于传统的关联规则,可广泛应用到诸多领域。2.提出基于极大团挖掘可信关联规则的MaxCliqueMining算法MaxCliqueMining算法采用邻接矩阵产生2-项可信集,不需要对数据库进行多次扫描,就能利用极大团思想产生所有可信关联规则,提高时间性能。该算法可以挖掘基于可信度、提升度、余弦度量以及相关度度量的可信关联规则,对于不同度量,算法只在生成2-项可信集时有所区别,后续挖掘过程完全一致。实验结果表明,本算法在倾斜支持度分布的数据集中挖掘可信关联规则具有较高的效率和准确性。3.提出统一挖掘超团模式和极大超团模式的HHCP-growth算法超团模式和极大超团模式都是基于h-置信度度量的可信关联规则的特定类型。挖掘两种模式的标准算法是完全不同的。本文提出基于FP-tree的HHCP-growth算法统一了两种模式的挖掘。算法采用了递归挖掘思想,无需保存大量候选项集。除了应用传统的最小支持度剪枝策略外,还引入最大支持度剪枝、项目自剪枝以及剩余项目剪枝等策略,减少遍历和递归的次数。本文证明了剪枝策略的有效性和算法的正确性。实验结果表明,HHCP-growth算法与传统的超团模式挖掘算法和极大超团模式挖掘算法相比,具有更高的效率,尤其在大数据集或低支持度条件下更为显著。4.制作并发布可作为告警关联分析和研究使用的标准告警数据集采集了某省移动公司GPRS网络管理系统及某设备生产商模拟网管理系统部分时段的告警数据。这些真实数据经过预处理,去除噪声和敏感信息后,被转换为可进行直接挖掘的标准数据格式。告警数据集在网站上提供免费下载,可作为告警关联分析和研究使用的标准数据集。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 论文的研究背景和意义
• 1.2 数据挖掘概述
• 1.2.1 数据挖掘的概念
• 1.2.2 数据挖掘的任务
• 1.2.3 数据挖掘的应用领域
• 1.2.4 数据挖掘的挑战
• 1.2.5 关联规则挖掘
• 1.3 论文主要研究内容
• 1.4 论文结构安排
• 本章参考文献
• 第二章 关联规则挖掘定义及主要算法
• 2.1 问题定义
• 2.2 数据分布
• 2.2.1 水平数据分布
• 2.2.2 垂直数据分布
• 2.3 关联规则挖掘算法
• 2.3.1 关联规则挖掘算法分类
• 2.3.2 Apriori算法基本原理
• 2.3.3 FP-growth算法基本原理
• 2.3.4 序列模式挖掘算法
• 2.4 本章小结
• 本章参考文献
• 第三章 可信关联规则及其兴趣度度量
• 3.1 传统关联规则的局限性
• 3.1.1 网络告警数据特点分析
• 3.1.2 网络告警标准数据集
• 3.1.3 挖掘倾斜分布数据集的局限性分析
• 3.2 可信关联规则概念
• 3.3 可信度度量性质
• 3.4 可信关联规则的其他兴趣度度量
• 3.4.1 提升度度量
• 3.4.2 相关度度量
• 3.4.3 向量夹角余弦度量
• 3.4.4 h-置信度度量与超团模式
• 3.4.5 各种度量的比较
• 3.5 本章小结
• 本章参考文献
• 第四章 基于极大团挖掘可信关联规则
• 4.1 用邻接矩阵求2-项可信集
• 4.2 由k-项可信集生成（k+1）-项可信集
• 4.3 基于极大团的可信关联规则挖掘算法
• 4.3.1 算法描述
• 4.3.2 求解极大团的改进算法
• 4.3.3 算法性能分析
• 4.4 实验结果分析
• 4.4.1 数据集及实验环境描述
• 4.4.2 MaxCliqueMining算法挖掘结果分析
• 4.4.3 MaxCliqueMining算法与其他算法的比较
• 4.5 基于其他度量挖掘可信关联规则
• 4.5.1 基于提升度度量产生2-项可信集邻接矩阵
• 4.5.2 基于余弦度量产生2-项可信集邻接矩阵
• 4.5.3 基于相关度度量产生2-项可信集邻接矩阵
• 4.5.4 实验结果分析
• 4.6 本章小结
• 本章参考文献
• 第五章 基于FP-tree挖掘超团模式和极大超团模式
• 5.1 基于FP-tree挖掘超团模式
• 5.2 基于FP-tree统一挖掘超团模式和极大超团模式
• 5.3 HHCP-growth算法分析
• 5.4 实验结果分析
• 5.4.1 数据集及实验环境描述
• 5.4.2 HHCP-growth算法挖掘结果分析
• 5.4.3 HHCP-growth与Hyperclique Miner性能比较
• 5.4.4 HHCP-growth与Hybrid性能比较
• 5.5 本章小结
• 本章参考文献
• 第六章 结束语
• 6.1 本文的总结
• 6.2 下一步工作
• 致谢
• 博士期间发表的论文