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

《分类关联规则归纳算法及应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Y1810‘，*类号丁P墙f学校代号1056uDc密级。开鳓聋南≯重以多SOUTHCHNAUNlVERSTY0FTECHNOLOGY博士学位论文分类关联规则归纳算法及应用研究学位申请人导师姓名及职称专业名称研究方向所在学院论文提交日期许孝元韩国强教授计算机应用技术多媒体技术及应用计算机科学与工程学院2005年4月16日摘要随着社会信息化程度的提高，数据量呈指数增长。从大量数据中挖掘有价值的知识在当今信息时代具有重要意义。关联规则挖掘是数据挖掘领域中的重要课题之一。特别是分类关联规则既能用于概念描述又能用于分类预

2、测与决策，在数据挖掘中发挥重要作用。目前分类关联规则挖掘技术在学术界与产业界受到广泛关注。自1998年出现第一个基于关联的分类算法(cBA)以来，关联分类算法的设计及应用研究一直非常活跃。目前，在关联分类问题上存在的共识是：关联分类的准确度总体上显著地高于传统的决策树分类，但关联分类存在的主要问题是产生太多的关联规则，导致计算速度慢、内存开销大、分类模型难以理解。本文研究分析了现有的分类关联规则归纳算法，给出了关联分类的有关定义及形式化描述，提出基于数据挖掘标准的分类规则质量评价新函数，首次提出挖掘知识要点的新

3、思想，创立了基于原子关联规则的分类新技术CAAR(C1assificationbasedonAtomicAssociationRules)，从根本上解决了关联分类执行效率低、内存开销大、分类模型较复杂的问题。将c从R分类新技术应用于有监督的图像内容分类学习和大规模数据机器学习取得了很好的效果。本文的创新点主要表现在以下五个方面：1)首次提出置信度主导的、基于置信度和支持度加权和的分类规则质量评价函数。目前，在机器学习领域内，广泛采用的分类规则质量评价函数是基于混淆矩阵计算的灵敏度(se)和选择性(sp)的乘积。

4、这种传统方法被称为评价分类规则质量的“黄金标准”。然而，从数据挖掘的角度分析灵敏度和选择性后，我们发现传统的方法不及我们提出的基于规则置信度和支持度加权和的新方法。为了在较大的分类关联规则搜索空间上验证我们提出的新函数，采用遗传算法进行了实验。结果表明基于数据挖掘的新函数显著地优于传统的分类规则质量评价函数。2)首次提出挖掘知识要点的新思想。采用原子型分类关联规则导向的知识要点挖掘技术能快速地发现不完全的、非精确的描述性分类知识。知识要点包括通过一次扫描数据集得到的精确原子型分类关联规则和通过组合计算得到的不完

5、全的、非精确的复合型分类关联规则。算法能计算复合型分类关联规则的支持度和置信度的边界值。对于一个复合型分类关联规则，如果规则的支持度和置信度的下界都分别超过支持度闽值和置信度阈值，则称该规则的存在性是确定的；如果规则的支持度和置信度各自的上界与下界之差小于一个给定的常量，则认为规则的度量参数是确定的。因此复合型分类关联规则可分为三种类型：(1)确定型：华南理工大学博士学位论文指规则的存在性和度量参数是确定的；(2)半确定型：指规则的存在性是确定的，但度量参数是不确定的；(3)不确定型：指规则的存在性是不确定的。

6、可以使用一个概率来度量不确定的复合型分类关联规则的存在性。该方法支持用户兴趣导向的探索型知识发现服务，能快速有效地发现描述性的知识要点；能利用知识要点进行部分分类，结合算法设计策略，能进一步实现完全的、精确的分类。3)创立了原子关联规则分类算法cAAR。与知识要点发现算法不同的是：cAAR算法仅挖掘原子型分类关联规则用于分类器构建，避免了一般关联分类遇到的频繁项集“组合爆炸效应”。c从R算法采用“基于原子型分类关联规则的突出特征”进行部分分类，结合“先易后难”策略从根本上解决了关联分类效率低的问题。算法分析和大

7、量的实验结果表明cAAR算法在执行速度上显著地优于关联分类基准算法CBA。而且C从R算法中规则的原予性有效地减少了过学习现象，对数据集中属性值遗失较多的实际应用场合，C从R算法表现出好的鲁棒性。4)首次提出只利用具有最高置信度和接近最高置信度的、强的分类关联规则用于分类器构建，确保了C从R算法的分类预测准确性。10一折交叉验证试验结果表明：cAAR算法显著地优于决策树算法和cBA算法。5)首次提出自适应置信度阈值，使原子关联规则分类算法具有很好的自适应能力；提出的相对支持度阈值能确保C从R算法在数据集中类分布严

8、重不均匀时对少数类实例分类预测的准确性。关键词：数据挖掘：机器学习；分类关联规则；分类；遗传算法；知识要点原子关联规则分类法；自适应置信度阈值；相对支持度闽值；大规模数据挖掘。IlABSTRACTWiththerapiddeVelopmentofsocialint'0rmationization，theamountofdataincreasesexponentially．Extract