分类关联规则归纳算法及应用研究

论文题目: 分类关联规则归纳算法及应用研究

论文类型: 博士论文

论文专业: 计算机应用技术

作者: 许孝元

导师: 韩国强,闵华清

关键词: 数据挖掘,机器学习,分类关联规则,分类,遗传算法,知识要点,原子关联规则分类法,自适应置信度阈值,相对支持度阈值,大规模数据挖掘

文献来源: 华南理工大学

发表年度: 2005

论文摘要: 随着社会信息化程度的提高,数据量呈指数增长。从大量数据中挖掘有价值的知识在当今信息时代具有重要意义。关联规则挖掘是数据挖掘领域中的重要课题之一。特别是分类关联规则既能用于概念描述又能用于分类预测与决策,在数据挖掘中发挥重要作用。目前分类关联规则挖掘技术在学术界与产业界受到广泛关注。自1998 年出现第一个基于关联的分类算法(CBA)以来,关联分类算法的设计及应用研究一直非常活跃。目前,在关联分类问题上存在的共识是:关联分类的准确度总体上显著地高于传统的决策树分类,但关联分类存在的主要问题是产生太多的关联规则,导致计算速度慢、内存开销大、分类模型难以理解。本文研究分析了现有的分类关联规则归纳算法,给出了关联分类的有关定义及形式化描述,提出基于数据挖掘标准的分类规则质量评价新函数,首次提出挖掘知识要点的新思想, 创立了基于原子关联规则的分类新技术CAAR(Classification based on Atomic Association Rules),从根本上解决了关联分类执行效率低、内存开销大、分类模型较复杂的问题。将CAAR 分类新技术应用于有监督的图像内容分类学习和大规模数据机器学习取得了很好的效果。本文的创新点主要表现在以下五个方面: 1)首次提出置信度主导的、基于置信度和支持度加权和的分类规则质量评价函数。目前,在机器学习领域内,广泛采用的分类规则质量评价函数是基于混淆矩阵计算的灵敏度(Se)和选择性(Sp)的乘积。这种传统方法被称为评价分类规则质量的“黄金标准”。然而,从数据挖掘的角度分析灵敏度和选择性后,我们发现传统的方法不及我们提出的基于规则置信度和支持度加权和的新方法。为了在较大的分类关联规则搜索空间上验证我们提出的新函数,采用遗传算法进行了实验。结果表明基于数据挖掘的新函数显著地优于传统的分类规则质量评价函数。2)首次提出挖掘知识要点的新思想。采用原子型分类关联规则导向的知识要点挖掘技术能快速地发现不完全的、非精确的描述性分类知识。知识要点包括通过一次扫描数据集得到的精确原子型分类关联规则和通过组合计算得到的不完全的、非精确的复合型分类关联规则。算法能计算复合型分类关联规则的支持度和置信度的边界值。对于一个复合型分类关联规则,如果规则的支持度和置信度的下界都分别超过支持度阈值和置信度阈值,则称该规则的存在性是确定的;如果规则的支持度和置信度各自的上界与下界之差小于一个给定的常量,则认为规则的度量参数是确定的。因此复合型分类关联规则可分为三种类型:(1)确定型:

论文目录:

摘要

ABSTRACT

第一章 绪论

1.1 本课题的研究背景及意义

1.1.1 数据挖掘的兴起

1.1.2 数据挖掘的理论与技术

1.1.3 数据挖掘的应用领域与发展前景

1.2 与本课题相关的国内外研究进展

1.2.1 关联规则挖掘算法综述

1.2.2 分类关联规则归纳算法研究

1.2.3 关联分类技术的发展与研究现状

1.3 本课题研究的目标与内容

1.3.1 研究的目标

1.3.2 研究的内容

1.4 本课题解决的关键问题

1.5 本文的组织

第二章 有关的术语及形式化描述

2.1 基本术语

2.2 关联规则与分类关联规则描述

2.3 分类问题描述

2.3.1 度量分类模型的指标体系

2.3.2 分类规则质量评价函数

2.3.3 分类模型的评价方法

2.4 分类基准算法C4.5

2.5 分类关联规则的搜索空间分析

2.5.1 搜索全部关联规则属于NP 难解问题

2.5.2 分类关联规则的搜索空间

2.6 小结

第三章 分类关联规则的演化搜索研究

3.1 研究的目的

3.2 遗传算法

3.2.1 遗传算法的出现和发展

3.2.2 遗传算法的原理

3.2.3 遗传算法的特点

3.2.4 遗传算法求解问题的步骤

3.2.5 基于遗传算法的机器学习

3.3 设计搜索分类关联规则的遗传算法

3.3.1 分类关联规则的染色体编码

3.3.2 分类关联规则的演化方式

3.3.3 基于遗传算法的关联分类

3.4 影响规则演化搜索的主要因素

3.4.1 适应值函数

3.4.2 属性选择概率

3.4.3 遗传算子

3.5 适应值函数的理论研究

3.5.1 混淆矩阵与关联规则度量的关系

3.5.2 分类规则的演化机理研究

3.5.3 一个规则演化实例

3.6 实验结果及分析

3.6.1 实验条件

3.6.2 单因素实验

3.6.3 综合实验

3.7 小结

第四章 原子型分类关联规则导向的知识要点发现

4.1 研究的动机

4.2 基本原理

4.2.1 发现知识要点的机理

4.2.2 复合规则支持度和置信度边界值计算

4.2.3 数据结构

4.2.4 挖掘知识要点的步骤

4.3 算法设计

4.4 算法的复杂度分析

4.5 知识要点在分类中的应用

4.5.1 基于知识要点的分类步骤

4.5.2 分类规则的选择

4.6 实验结果及分析

4.6.1 实验条件

4.6.2 知识要点的发现

4.6.3 基于知识要点的部分分类

4.6.4 从部分分类到完全分类

4.7 小结

第五章 原子关联规则分类算法CAAR

5.1 研究背景

5.2 原子关联规则分类原理

5.2.1 CAAR 算法的分类原理

5.2.2 CAAR 算法与CBA 的分类机理比较

5.2.3 原子关联规则分类的理论计算

5.2.4 CAAR 算法的分类步骤

5.2.5 CAAR 分类的一个范例及演示

5.2.6 CAAR 与1R 算法的比较

5.3 算法设计

5.3.1 CAAR 分类算法设计

5.3.2 CAAR 的强原子规则生成算法

5.3.3 CAAR 的冗余规则剪枝函数

5.4 CAAR 的分类能力度量

5.4.1 P 型和N 型数据集

5.4.2 提高 CAAR 的适应能力

5.5 算法分析

5.5.1 CAAR 算法的时间效率分析

5.5.2 CAAR 算法的空间效率分析

5.5.3 基于χ2 检验的鲁棒性分析

5.6 实验结果及分析

5.6.1 实验条件

5.6.2 剖析 CAAR 的分类过程

5.6.3 P 型和N 型数据集的划分

5.6.4 CAAR 的分类性能实验

5.6.5 CAAR 的鲁棒性实验

5.7 CAAR 在图像内容分类学习中的应用

5.7.1 基于关联规则的图像处理技术

5.7.2 图像数据集

5.7.3 基于 CAAR 的图像内容关联分类实验

5.8 CAAR 在大规模数据挖掘中的应用

5.8.1 大规模数据挖掘技术

5.8.2 基于 Multi-Agents 的分布式关联分类

5.8.3 基于 CAAR 的大规模数据挖掘的特点

5.8.4 实验结果及分析

5.9 小结

结束语

参考文献

攻读博士学位期间发表的与学位论文内容相关的学术论文

攻读博士学位期间主要参与的研究项目

附录:本论文常用符号对照表

致谢

发布时间: 2005-09-15

参考文献

• [1].分类关联规则挖掘及其在复杂工业过程中的应用研究[D]. 任佳.浙江大学2006
• [2].基于形式概念分析分类规则挖掘的关键问题研究[D]. 余远.中国矿业大学（北京）2009

标签：数据挖掘论文;  机器学习论文;  分类关联规则论文;  分类论文;  遗传算法论文;  知识要点论文;  原子关联规则分类法论文;  自适应置信度阈值论文;  相对支持度阈值论文;  大规模数据挖掘论文;