（计算机应用技术专业论文）基于k近邻集成算法的分类挖掘研究.pdf

摘要 随着数据库和互联网技术的迅猛发展，数据挖掘技术得到了进一步的发展和广泛关 注。分类数据挖掘作为数据挖掘中一个重要的研究内容，已经被广泛应用于模式识别、 人工智能和知识工程等领域。所以，对它进行深入研究不仅有着重要的理论意义，而且 在现实中有着重要的应用价值。 本文主要包含了以下几个方面的内容： 1 概述了数据挖掘中的分类技术，深入分析了分类挖掘的主要算法，重点介绍了k 近邻分类算法的原理及发展现状。 2 提出了基于模拟退火算法的组合k 近邻分类器，通过引入模拟退火技术实现随机 特征子集的选择，然后利用投票法决定组合分类器最终的输出。仿真实验证明该方法的 分类性能优于传统k 近邻方法的分类性能。 3 针对模拟退火算法的搜索过程是随机的，经典模拟退火算法的停止准则不能确保 解的质量这一问题，弓f 入了改进的模拟退火算法。在此基础上，进一步提出了基于改进 模拟退火的组合k 近邻分类算法。仿真实验表明，基于改进模拟退火的组合k 近邻分类 算法较基于模拟退火的组合k 近邻分类算法有更好的分类性能。 4 针对传统k 近邻分类算法在高维数据空间分类速度较慢的问题，提出了基于模糊 粗糙集的快速k 近邻分类算法，考虑由于类的重叠和属性不足导致的模糊和粗糙不确定 性，同时引入p - t r e e 数据结构来改进传统k 近邻分类算法。与传统k 近邻分类算法和模 糊粗糙k 近邻分类算法相比，该方法不仅可以改善分类性能，而且可以提高分类器的速 度。仿真实验证明了该方法的有效性和可行性。 关键词：分类，k 近邻，模拟退火，模糊集，粗糙集 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fd a t a b a s et e c h n o l o g ya n di n t e r n e tt e c h n o l o g y , d a t am i n i n g t e c h n o l o g yh a sb e e nf u r t h e rd e v e l o p m e n ta n dw i d e s p r e a dc o n c e r n m e a n w h i l e ，c l a s s i f i c a t i o n d a t am i n i n ga sa ni m p o r t a n tr e s e a r c hc o n t e n th a sb e e nw i d e l yu s e di np a t t e r nr e c o g n i t i o n ， a r t i f i c i a li n t e l l i g e n c ea n dk n o w l e d g ee n g i n e e r i n g t h e r e f o r e ，r e s e a r c h i n gi n t ot h es u b j e c tn o t o n l yh a si m p o r t a n tt h e o r e t i c a ls i g n i f i c a n c e ，b u ta l s oh a si m p o r t a n ta p p l i c a t i o n si nr e a l i t y t h et h e s i sc o n t a i n st h ef o l l o w i n ga s p e c t s ： 1 a no v e r v i e wo fc l a s s i f i c a t i o n t e c h n o l o g ya n da n a l y s i s o ft h em a i nc l a s s i f i c a t i o n a l g o r i t h m ，f o c u s e so nt h ep r i n c i p l eo fkn e a r e s tn e i g h b o rc l a s s i f i c a t i o na l g o r i t h ma n dt h e d e v e l o p m e n tp r e s e n t 2 a ni m p r o v e dc o m b i n a t i o nkn e a r e s tn e i g h b o r sm e t h o db a s e do ns i m u l a t i o na n n e a l i n gi s p r o p o s e d ，w h i c hi n t r o d u c et h es i m u l a t e da n n e a l i n gt e c h n o l o g yt oa c h i e v er a n d o mf e a t u r e s u b s e ts e l e c t i o n ，a n dt h e nu s ev o t ea c tt od e c i d et h ef i n a lo u t p u to fc o m b i n a t i o nc l a s s i f i e r i t i ss h o w nt h a tt h ec l a s s i f i c a t i o np e r f o r m a n c ei sb e t t e rt h a nt h et r a d i t i o n a lkn e a r e s tn e i g h b o r a l g o r i t h mf r o mt h es i m u l a t i o ne x p e r i m e n t 3 i nv i e wo ft h es e a r c hp r o c e s so fs i m u l a t e da n n e a l i n ga l g o r i t h mi sr a n d o m ，t h ec l a s s i c s i m u l a t e da n n e a l i n ga l g o r i t h ms t o p p i n gc r i t e r i o nd o e sn o te n s u r et h eq u a l i t yo fs o l u t i o n s ，t h e i m p r o v e ds i m u l a t e da n n e a l i n ga l g o r i t h mi si n t r o d u c e d o nt h eb a s i s ，t h ec o m b i n a t i o nk n e a r e s tn e i g h b o r sm e t h o db a s e do ni m p r o v e ds i m u l a t e da n n e a l i n gi sf u r t h e rp r o p o s e d t h e s i m u l a t i o ne x p e r i m e n t a ls h o w st h a tt h ec o m b i n a t i o nkn e a r e s tn e i g h b o r sm e t h o db a s e do n i m p r o v e ds i m u l a t e da n n e a l i n gh a sb e t t e rc l a s s i f i c a t i o np e r f o r m a n c et h a nt h eo n eo ft h e c o m b i n a t i o nkn e a r e s tn e i g h b o r sm e t h o db a s e do nt r a d i t i o n a ls i m u l a t i o na n n e a l i n g 4 an e wf a s tkn e a r e s tn e i g h b o ra l g o r i t h mb a s e do nt h ef u z z y - r o u g hs e t si sp r o p o s e d ， t a k i n gi n t oa c c o u n tf u z z ya n dr o u g hu n c e r t a i n t yd u et ot h eo v e r l a p p i n gc l a s s e sa n dt h e a t t r i b u t ei n s u f f i c i e n c y , i n t r o d u c i n gp - t r e ed a t as t r u c t u r et oi m p r o v et h et r a d i t i o n a lkn e a r e s t n e i g h b o rm e t h o d w i t ht h et r a d i t i o n a lkn e a r e s tn e i g h b o rm e t h o da n df u z z ykn e i g h b o r c l a s s i f i e rc o m p a r i s o ns h o w st h a tt h em e t h o dc a l ln o t o n l yi m p r o v et h e c l a s s i f i c a t i o n p e r f o r m a n c e ，b u ta l s oc a ni m p r o v et h ec l a s s i f i e rs p e e d t h es i m u l a t i o ne x p e r i m e n th a sp r o v e n t h em e t h o d sv a l i d i t ya n df e a s i b i l i t y k e y w o r d s ：c l a s s i f i c a t i o n ，kn e a r e s tn e i g h b o r , s i m u l a t e da n n e a l i n g ，f u z z ys e t ，r o u g hs e t 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名： ：盈蚴 指导教师签名： 7i 一，一 沙i 。年6 月1 日砂i o 年6 月f 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，本 论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西北大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：刨、诟0 包 2 o l o 年6 月1 日 西北大学硕士学位论文 第一章绪论 1 1 选题背景 2 0 世纪6 0 年代以来，随着信息技术、网络技术、数据库技术和计算机硬件技术的 迅猛发展，一方面，人们可以方便地获取和存储大量的数据；而另一方面，面对大规模 的海量数据，传统的数据分析工具只能进行简单的查询、统计等处理，无法获得数据之 间内在的关联和更隐蔽的信息。为了跨越数据和信息之间的鸿沟，摆脱这种“数据丰富， 知识贫乏的困境，迫切需要一种能够自动的智能的把海量数据转换成有用信息和知识 的技术，于是数据挖掘技术f l 。】应运而生。 数据挖掘是从大型数据库或数据仓库中提取隐含的、未知的、有潜在应用价值的信 息或模式，它是数据库研究中很有价值和前途的新领域，它融合了数据库、人工智能、 机器学习、模式识别、统计学等多个领域的理论和技术。数据挖掘是- - f - j q e 常广泛的交 叉学科，多年来它汇集了各种不同领域的研究者。需要特别说明的是，数据挖掘技术从 诞生之初就是面向实际应用的，它可对数据库进行检索查询、宏观和微观推理、分析和 预测，从而更好的指导实际问题的求解。 分类是数据挖掘的重要研究方向，也是数据挖掘的重要任务之一，它是从一组已知 的训练样本中学习和发现分类模型，然后使用该模型来预测待分类样本的类别。分类的 目的是学会一个分类函数或分类模型，该模型可以把数据库中的数据项映射到给定类别 中的某一个类别。其中，分类的输出是离散的类别值当它用于预测的情况时。随着数据 挖掘技术的深入发展，分类数据挖掘在很多领域也得到了广泛而深入的研究和应用。到 目前为止，已经研究出的比较成熟的分类方法主要包括：k 近邻分类算法( kn e a r e s t n e i g h b o r , k n n ) 、决策树( d e c i s i o nt r e e ) 、贝叶斯网络( b a y e s i a nn e t w o r k ) 、粗糙集( r o u g h s e t ) 、模糊集( f u z z ys e t ) 、神经网络( n e u r a ln e t w o r k ) 、遗传算法( g e n e t i ca l g o r i t h m ) 和支 持向量机( s u p p o r tv e c t o rm a c h i n e ) 等。 不同的分类方法具有不同的特点，通常用来比较和评估分类方法的标准主要包括： 分类准确率、分类速度、健壮性、可伸缩性和可解释性。目前普遍认为不存在一种分类 方法能适合各种特点的数据、总是优于其它的分类算法，每一种方法都不是完美的，都 存在缺陷。此外，分类的效果一般和数据的特点有关系，有的数据噪声大、有的含有缺 失值、有的分布稀疏、有的属性是连续的、有的则是离散的或混合式的。 纵观近年来分类算法的发展，主要有三大趋势：一是传统分类算法得到进步发展 第一章绪论 和改进，例如支持向量机算法的不断改进和k n n 方法的发展，传统分类算法的发展主 要利用了机器学习、进化计算、数据挖掘、模式识别等理论中的原理和方法；二是新的 分类算法不断涌现，新分类算法的出现主要得益于人工智能、知识工程、模式识别、进 化计算和粒度计算【2 。3 】等领域中新技术的涌现和发展；三是根据现实应用中具体问题的 需要，有针对性地综合诸多领域的技术和方法，以期提高分类算法的性能。 1 2 研究现状 k n n 4 - 6 是最著名的模式识别和统计学方法之一，从产生到现在已经有4 0 多年的发 展历史。最初的近邻法是由c o v e r 和h a n 7 】提出的，随后得到了理论上深入的分析和研 究，是非参数法中最重要的方法之一，已经被广泛应用于文本分类、模式识别、图形图 像及空间分类【8 1 等领域中。k n n 虽然是一种有效的分类方法，但是它有两个明显的缺 陷：第一，k n n 算法分类的效果在很大程度上取决于k 值( 近邻数) 选择的好坏；第二， 由于k n n 算法是一种懒惰的学习方法，要存储所有的训练样本，所以它对大规模数据 集进行分类时是低效的。 近年来，广大数据挖掘工作者对k n n 算法进行了深入的研究和改进，改进的方向 主要可以分为4 类：一是寻求更接近于实际的距离函数以取代标准的欧氏距离，典型的 工作包括w a k n n t 9 1 、v d m 1 0 】；二是搜索更加合理的k 值以取代指定大小的k 值，典型 的工作包括s n n b 1 1 1 、d k n a w 1 2 】；三是运用更加精确的概率估测方法去取代简单的投 票机制，典型的工作包括k n n d w t l 3 1 、l w n b 1 4 1 、i c l n b 1 习；四是建立高效的索引，以 提高k n n 算法的运行效率，代表性的研究工作包括k d t r e e 1 6 1 、n b t r e e 17 1 ，还有部分 工作综合了多种改进方法。 传统k n n 算法在应用中需要进一步研究的问题主要有： 1 需要主观决定k 值( 近邻数) ，k 值选择的合理与否直接关系到算法的精确度。现实 应用中最佳的k 值通常需要进行一系列的实验验证才能取得。有时，我们会根据个人经 验来决定。 2 应用k n n 算法时，样本间的相似度是根据样本的所有特征来进行计算的。但这 些特征中，有些是与分类弱相关的，还有一些特征是与分类不相关的，只要一部分有时 是很少的一部分是与分类强相关的。因此，如果不加处理，近邻间的距离就会被大量不 相关的特征所支配。因此，特征的选择与结果的正确性有紧密的关系。 3 在高维向量空间中实施k n n 算法时，由于计算量较大导致算法效率大大降低， 分类准确率也不理想。如何在高维向量空间中实施有效的k n n 算法，降低高维向量距 2 西北大学硕士学位论文 离计算的代价，受到了数据挖掘工作者广泛的关注。虽已有文献【1 8 艺0 1 对此提出了不同的 解决方法，但是往往不可避免地遭遇“维数灾难 的困扰。因此，如何在高维向量空间 有效地运行k n n 算法有待进一步深入的研究。 1 3 本文主要工作 针对k n n 算法存在的缺陷，本课题的主要研究内容如下： 1 针对当样本数据的特征属性数量较多并且属性集包含不相关属性或者弱相关属 性、样本的容量较大时，k n n 算法分类效果不是很好这个问题，将模拟退火算法、投 票机制、组合分类方法引入传统k n n 算法中。首先利用模拟退火算法实现随机属性子 集的选择，分别在各个随机属性子集上生成k 近邻分类器，然后利用简单投票方法，组 合多个k 近邻分类器的分类结果进行最终输出。仿真实验表明基于模拟退火算法的组合 k 近邻分类算法可以有效提高分类的效率和精度。 2 由于模拟退火算法的搜索过程是随机的，针对当前解达到最优解时有时要经过恶 化的山脊、经典模拟退火算法的停止准则不能确保解的质量这一问题，提出了改进的模 拟退火算法。通过在经典模拟退火算法中增加一个记忆器，以确保算法中最优解的质量， 在此基础上，进一步提出了基于改进的模拟退火的组合k 近邻分类算法。仿真实验表明， 基于改进的模拟退火组合k 近邻分类算法较基于模拟退火的组合k 近邻分类算法有更好 的分类性能。 3 针对高维向量空间中计算高维向量间距离的代价大，分类效率较低及“维数灾难 的问题，将模糊粗糙集理论、p t r e e 结构与传统k n n 算法相融合。解决了由于类的重 叠引起的训练样本的模糊不确定性，由于属性不足引起的类边界的粗糙不确定性。由于 每个类的特征不同，最优的k 值也是不同的，文中利用每个样本与训练集样本的距离定 义每个样本的邻域空间，从而确定最优的k 值，提高了分类算法的精度和召回率。 1 4 论文组织结构 第一章绪论 概述了分类挖掘的国内外研究现状及主要的分类算法，重点介绍了k 近邻算法的发 展现状、研究背景、意义及需要进一步研究的问题。 第二章分类挖掘与k 近邻算法概述 详细介绍了k 近邻分类算法的原理及优缺点，简要介绍了分类的定义、主要分类算 法及分类的评价标准等。 3 第一章绪论 第三章基于模拟退火的组合k 近邻分类算法 将模拟退火算法、投票机制和组合分类器引入传统k n n 分类算法中，提出了一种 改进的k n n 分类算法一m k n n ( m u l t i p l ek n e a r e s tn e i g h b o r ) ，该算法可以有效提高k n n 算法的分类正确率，并进行了仿真实验。 第四章基于改进的模拟退火的组合k 近邻分类算法 针对模拟退火算法的搜索过程是随机的，经典模拟退火算法的停止准则不能确保解 的质量这一问题，引入了改进的模拟退火算法。在此基础上，进一步提出了基于改进的 模拟退火的组合k 近邻分类算法。仿真实验表明，基于改进的模拟退火的组合k 近邻分 类算法较基于模拟退火的组合k 近邻分类算法有更好的分类性能。 第五章基于模糊粗糙集的快速k 近邻分类算法 将模糊粗糙集理论与传统k n n 算法融合，引入p t r e e 数据结构，提出了一种加快 k n n 在高维向量空间中实施有效检索的新算法一f f 砌蝌( f a s tf u z z yr o u g hn e a r e s t n e i g h b o r ) 算法，并进行了仿真实验。 总结和展望 总结了全文所做的工作与研究成果，指出了目前研究的不足之处，展望了将来有待 进一步开展的工作。 4 目北大学硕十学位论文 第二章分类挖掘与k 近邻算法概述 数据挖掘( d a t am i n i n g ，d m ) 的定义是与“数据库中的知识发现”( k n o w l e d g e d i s c o v e r y m d a t a b a s e s ，k d d l 是密切关联的。一种观点将数据挖掘和知识发现看成是等 价的概念，认为它们都是指发现知识的整个过程。另一种观点e 2 1 i 是知识发现是从大容量 数据库中发现知识的过程，数据挖掘仅仅是知识发现过程中的一个步骤。在此，术文利 用数据挖掘的广义的观点一数据挖掘继承和发展了知识发现领域的优秀研究成果，同时 具有自己独特的内涵和作用。 一般来讲，数据挖掘是指一个从大型数据库中提取隐含的、事先未知的、并且具有 潜在有用价值的信息或知识的非平凡过程。其流程图如图2l 所示。 载镕库 h 一数据准备+ | + 一藏矧蚓 叶卜表i 与* 告+ | 图2 1l 的一股过程 在数据挖掘中，分类( c l a s s i f i c a t i o n ) 数据挖掘是一个重要的研究课题，它可以j l j 来提 取描述重要数据类的模型，也可以用来预测未来的趋势。分类数据挖掘的应用主要包括： 医疗诊断、性能预钡m 、决簧控制等。分类数据挖掘直是统计学、机器学习、模式识别 和专家系统领域的研究热点，已经产生了很多的分类方法。纵观现实中的很多问题都可 以转化为分类问题，从政府管理决策、商业经营运维到科学研究和企业决策支持等众多 领域都用到了分类技术，因此数据挖掘分类技术的应用前景是十分广泛的。例如我们可 以建立一个分类模型，对工厂企业的机器运转情况进行分类以预测机器故障的发生概 率：还可以建立一个分类模型，对银行的全部贷款客户进行分类，从而降低贷款的风险： 此外，还可以通过对互联网用户洲览网页的历史记录，进行相应的w e b 挖掘，挖掘出各 扁 翼j 。 票且 。芦一吾 第二章分类挖掘与k 近邻算法概述 种不同类型的网络用户的浏览习惯、关注的重点，从而针对不同的用户设计相应的网页 链接结构等等。因此，深入研究分类数据挖掘具有重要的现实意义，也为本文的研究工 作提供了契机。 2 1 分类挖掘的定义 数据分类是数据挖掘的重要研究内容，分类首先需要建立分类模型，为了获取分类 模型，一般需要一个训练数据集一样本数据库e ，其中e 中的元组都由多个相同的属性 构成，而且是一个大型数据库w 中的元组，每个元组都具有一个已知的类标识号。分 类就是在数据集中找出一组对象的共同特征，然后把数据依据分类模型划分为不同的类 的过程。 定义2 1 设 d i ，d 2 ，d 。) 是数据集，d ，是元组，其中i = l ，2 ，n ，c = c l ，c 2 ，c k ) 是给定的分类集合，函数f d f c ，表示数据集d ，被划分为c ，个类，j = l ，2 ，k 。 数据分类一般是一个两步的过程，具体过程如下： 首先是建立一个描述数据类集或者概念集的数据模型，接着分析由特征属性描述的 数据库元组并构造模型。这里，一般每个元组属于一个预定义的类别，类别通常由一个 称作类标号的属性来确定。由于每个训练样本的类标号为已知，该步骤称为有指导的学 习。一般情况下，学习模型可以用分类规则、决策树等形式表示。分类的数据又称为样 本或对象，训练数据集中的所有单个元组称作训练样本，并且随机地从样本集中选取。 其次，利用分类模型进行分类。我们首先需要评估模型的预测准确率，对于每个测 试样本，将已知的类标号与样本的学习模型预测的类别进行比较，模型在给定测试数据 集上的准确率是指被模型正确分类的测试样本的百分比。如果模型的准确率可以接受， 我们就可以使用分类模型对未知的数据样本进行分类。 分类方法的评价标准主要包括准确率、速度、健壮性、可伸缩性、可解释性等五个 方面，具体含义不再详述。 2 2 分类挖掘的主要方法 分类作为数据挖掘中的一个重要分支和研究内容，多年来吸引了很多来自不同领域 的学者的广泛关注和研究。除了基本的统计分析方法外，数据挖掘的分类技术主要包括： 决策树、贝叶斯方法、k 近邻算法和基于关联规则挖掘的方法等。 1 决策树( d e c i s i o nt r e e ) 目前较为著名的决策树算法是i d 3 算法【2 2 1 和c 4 5 算法【2 3 】，它们是q u i n l a n 分别在 6 西北大学硕士学位论文 1 9 8 6 年和1 9 9 3 年先后提出的。i d 3 算法的主要思想：为了使分裂时系统的熵最小，每 次都选择信息增益值最大的属性来划分训练数据样本，达到提高算法分类速度和分类正 确率的目的。i d 3 算法的优点是分类速度快、描述简单并且产生的分类规则容易理解， i d 3 算法的缺点是训练正例和反例难控制、抗噪性差及非递增学习算法。c 4 5 算法针对 i d 3 算法的特点作了进一步改进，能够处理连续值属性和离散值属性，然而c 4 5 算法的 一个明显缺陷是也不能进行增量式学习。 s l i q 算法中引入了宽度优先和对样本预排序两项技术，这主要是针对c 4 5 算法产 生的样本反复扫描和排序低效的问题。其中，宽度优先技术可以为决策树中每个叶结点 找到最优分裂标准，预排序技术消除了结点数据集排序。这些技术的引入使得s l i q 算 法不仪可以处理大规模数据样本集，而且可以对包含大量类、属性与样本的数据集进行 分类。s l i q 也是一个可以同时处理离散和连续属性的决策树分类器，其最大的缺点是 内存驻留数据会线性正比增大伴随着输入记录数量的逐渐增加，因此限制了分类训练的 数据量。此外，s l i q 算法的可扩展性比较差，主要是因为它对于非分裂属性的属性列 表进行分裂比较困难。 s p r i n t 算法为了减少驻留于内存的数据量，对决策树的数据结构进行改进，将类 别合并到每个属性列表中，内存中不再驻留类别列表。s p r i n t 算法不受内存的限制， 处理速度很快且可以扩展。 2 贝叶斯方法( b a y e s i a nm e t h o d ) 贝叶斯方法作为一种被广泛应用的统计学分类方法，其核心思想是利用贝叶斯定理 来预测未知类别的样本可能属性，然后选择可能性最大的类别作为未知类别样本的类 别，它是一种统计分类方法。朴素贝叶斯网络是一种高效的分类算法，然而其不符合现 实世界的假设一属性独立性假设大大降低了朴素贝叶斯网络的适用性。然而如果允许属 性之间形成有向图、考虑属性间的依赖关系、增强其表示依赖关系的能力，贝叶斯网络 的结构由于结构的极大任意性将变的难以学习。因此，贝叶斯网络结构的学习问题仍需 要进一步深入研究，仍是一个n p 完全问题。 对于贝叶斯网络的改进主要包括以下几点【2 4 】：一是确保选择的属性间具有最大的属 性独立性的基于属性选择的算法，代表性算法是l a i l 百e ，2 5 1 提出的s b c 算法；二是通过 考虑属性间的依赖关系、降低属性独立性假设来扩展朴素贝叶斯网络的结构，代表性算 法是f r i e d m a n t 2 6 1 提出的t a n 算法；三是基于实例的算法【2 7 1 。前二类算法都属于积极的 7 第二章分类挖掘与k 近邻算法概述 学习方法，因为它们要根据训练集合构造一个分类器，第三类算法属于消极的学习方法。 3 k 近邻算法( k n e a r e s tn e i g h b o r ) k 近邻分类算法的基本思想：首先在多维向量空间中寻找与待分类样本最接近的k 个邻居，然后根据这k 个近邻点的类别决定待分类样本所属的类别，它是最简单有效的 分类算法之一。然而，k 近邻算法存在两个显著的缺点：一是对大规模数据集进行分类 时是低效的；二是分类效果在很大程度上取决于k 值一近邻数选择的好坏。后续章节将 对k 近邻分类算法作更近一步的分析。 4 基于关联规则的分类方法 基于关联规则的分类方法一般由两步组成：首先，使用关联规则分类方法从训练数 据样本集中挖掘出所有同时满足指定置信度和指定支持度的关联规则，置信度主要用来 衡量关联规则的可信程度，支持度主要用来衡量关联规则在整个数据样本集中的统计重 要性；接着，利用启发式方法从第一步挖掘出的类关联规则中选择出一组高质量的规则 并应用于实际分类过程。 1 9 9 3 年，a g r a w a l 等提出了a i s 算法和s e t m 算法，1 9 9 4 年又提出了a p r i o r i 算法 和a p r i o r i t i d 算法。a i s 算法和s e t m 算法的缺点主要是产生很多不必要的数据项集的 生成和计数。后两个算法相对前两个算法的主要改进之处是：对数据库的一次扫描遍历 中，产生候选数据项集及候选数据项被计数的方法。日常生活中，我们很多地方都用到 了关联规则例如目录设计、仓储规划等等，因此通常要考虑关联规则的高效更新问题。 由此，d w e h e u n g 提出了基本框架和a p d o r i 算法一致的增量式更新算法f u p ；考虑当 可信度和最小支持度发生改变时，数据库中的关联规则如何更新的问题，冯玉才等提出 了两种高效的增量式更新算法一砌a 算法和p i u a 算法。 数据挖掘中的分类算法非常多，各有优缺点，并且还在不断的研究和发展中。还有 一些其他的分类算法，如神经网络 2 8 之9 】、遗传算法3 0 3 1 1 、基于数据库的分类算法、基于 属性的归纳分类技术等，这里不再一一论述。 2 3k 近邻算法概述 k 近邻算法是模式识别非参数法中最重要的方法之一，它是一种基于实例的统计学 习方法。最初是由c o v e r 和h a r t 于1 9 6 8 年提出，是一个理论上比较成熟的方法，在过去 的4 0 年里得到了广泛而深入的研究和发展。由于其简单易行，而且分类效果良好，对不 同数据集都有很好的可操作性，目前已经被广泛的应用于基于统计的机器学习中。 8 西北大学硕士学位论文 k 近邻算法的基本思想是：对于给定的待分类样本x ，计算它与训练样本集中所有 样本的相似度，根据相似度找出x 的k 最相似的训练样本，然后根据这k 个样本的类别 决定x 所属的类别，将k 个最相似的训练样本中最普遍的类标记作为预测值赋给待分类 的样本x 。 k 近邻算法包含两个要素：距离度量尺度和近邻数k 。距离度量尺度描述样本间的 相似度，对应一个非负函数。k 是分类时参考的近邻数，对于k 值的选择要通过验证大 量独立的测试数据和模型，才能做出较好选择。 k 近邻算法是一种基于类比学习的非参数分类技术，具有鲁棒性、概念清晰等优点， 具体如下： 1 属于一种非参数化分类方法，适用于概率密度函数的参数形式未知的情况； 2 算法思想很简单，并且容易实现； 3 训练过程简单迅速； 4 不需要产生额外的数据来描述分类规则，它的规则就是训练数据本身； 5 该算法原理上虽然依赖于极限定理，但是采用该方法却可以避免不平衡的样本数 量问题。因为实际具体分类过程中，它其实只与很少量的近邻样本相关。 k 近邻算法也存在一些不足之处： 1 分类速度慢 k 近邻分类算法是一种基于实例学习的懒惰学习方法，对每一个待分样本，它都需 要计算其与训练样本库中所有样本的相似度，才能得到与待分样本最相邻的k 个邻居。 k 近邻算法的时间复杂度和空间复杂度都将会很高，当其遭遇数据集规模较大并且是高 维样本时，其时间复杂度为o ( n m ) ，n 是数据集的大小，m 是样本的特征维数。 2 特征属性作用相同 k 近邻分类算法将所有的特征属性都统一看待，即分类时赋予每一个属性相同的权 重，然后根据数据样本的所有特征属性来计算样本间的距离和衡量相似度。然而，按照 所有的特征权重相同来计算样本间的相似度经常会误导分类过程，因为在这些特征中， 有些特征是与分类弱相关，还有一些特征是与分类不相关，只有部分特征与分类强相关。 3 k 值的确定 k 近邻分类算法分类时必须指定近邻数k ，如果k 值选择不当则分类精度将会受到 影响。实际应用中，通常要尝试采用不同的k 值进行一系列实验，才能最终确定出分类 效果最优的k 值。 9 第二章分类挖掘与k 近邻算法概述 4 分类效果容易受训练数据分布情况的影响 k 近邻分类算法是一种基于统计的分类算法，它得到的分类结果很大程度上取决于 训练数据样本的分布情况。一种非常理想的情况是每一类都聚集在一起，若把数据样本 向n 维向量空间投影，投影后每一类内的数据样本点都比较集中，也就是说，类内的距 离相对比较小，类和类之间的距离相对比较大，类与类之间具有非常明显的界限，即数 据样本点的分布明显是“扎堆”的，我们用肉眼就能看出来。所以，每一堆几乎就是一 个类别。很显然，这样的测试数据是理想的、合格的、规范的。k 近邻分类算法面对这 种分布情况的数据有比较好的分类结果，因为这正好和k 近邻分类算法的基本分类思想 相符合，即首先判断相似度最大的k 个邻域内的样本点，找出样本数最多的类别，然后 得到分类结果。 然而，现实情况很少如此，训练数据样本空间很少出现所谓的“扎堆 现象，数据 样本可能很松散，即投影后的样本点可能遍布于每个角落，数据样本的分布具有极大的 不均匀性。而且，日常生活中我们实际要面对和处理的数据可能来自许多不同的地方， 夹杂着各种不同的规范和表达形式，出自各种不同人的手，甚至数据本身就很“粗糙 一表达不规范、有歧义、包含大量冗余信息及文章主题不明确等等。这种情况，如果用 k 近邻分类算法来处理的话，分类精度肯定将会受到很大的影响。因为大量分布在类边 界的数据样本在很大程度上增加了分类的“噪音 干扰，k 近邻分类算法的分类性能也 大大降低。 2 4k 近邻算法研究现状 k 近邻分类算法的改进方法大体上可以分为四种类型：加快分类速度、对训练样本 库进行维护、优化距离度量和最优k 值确定，具体介绍如下： 1 加快k 近邻算法的分类速度 7 般而言，懒惰学习算法比积极学习算法的学习速度要快。但是，在进行具体的分 类时，懒惰学习算法通常却比积极学习算法慢许多，因为懒惰学习算法一般需要进行大 量的计算。针对该问题，目前很多解决方法都从减少样本数量和加快k 近邻搜索两个方 面来进行了考虑： ( 1 ) 缩减训练样本 当训练样本集中数据样本量比较大时，为了降低计算复杂度，可以先编辑预处理训 练样本数据集，主要是从原始训练样本集中选择出最优的参考子集，再在参考子集上再 进行k 近邻的查询，达到提高运算效率和缩减训练样本的目的。缩减训练样本的方法主 1 0 西北大学硕士学位论文 要包括h a l t 的c o n d e i l s i n g 算法【3 2 】，w i l s o n 的e d i t i n g 算澍3 3 1 和d 州v 盯的m u l t i e d i t 算 法【3 4 】，k u n e h e v a 利用遗传算法也进行了相关的研列3 5 1 。 ( 2 ) 加快k 个近邻的搜索速度 这类方法的出发点是通过引入快速搜索算法，以达到在最短时间内搜索到待分类样 本的k 个近邻的目的。该类方法主要分为三大类【3 6 】：空间数据分区算法、线性化算法和 扫描为基础的算法。该类方法在具体进行搜索时采用一定的快速搜索方法而不是盲目的 搜索，以期加快搜索速度或者减小搜索范围。例如构造交叉索引表的原理就是利用匹配 成功与否的历史来修改样本库的结构，然后利用样本和概念来构建层次或者网络来组织 训练样本集。 2 优化距离度量尺度 为了改进k 近邻算法中所有特征属性同等看待的缺陷，可以通过赋予不同特征不同 的权重来优化度量相似度的距离公式。例如赋予不同特征不同权重的欧氏距离公式中如 公式( 2 1 ) 所示： 一 d ( x ，y ) ：、m ( 前一少) 2 ( 2 1 ) i = 1 其中w i 是第f 个特征的权重。 一般是根据各个特征在分类中所起的作用来设定特征权重的大小【3 7 3 8 1 ，特征在分类 中所起的作用越大，特征的权重越大；特征在分类中所起的作用越小，特征的权重越小。 此外，还可根据其在靠近待分类的测试样本的集合中的分类作用得到权重【3 9 1 。 3 对训练样本库进行维护 维护训练数据样本库以满足k 近邻算法分类的需要，所谓的“维护是利用适当的 方法来保证训练样本集的大小，并不是简单的删除和增加样本。例如可以删除样本库中 符合某种条件的样本，也可以将符合某种条件的样本加入训练样本库中，以保证训练样 本库中的样本可以满足k 近邻算法所需要的比较均匀的特征空间，达到提高k 近邻分类 精度和减少样本量的目的，文献【4 0 4 2 1 从不同角度维护了训练样本库。 然而，训练样本库有时并不能提供所有类的足够多的训练样本，也就是说训练数据 样本库无法满足k 近邻算法分类所需要的相对比较均匀的特征空间，往往单纯增加数据 样本也会带来计算量太大的问题，为了获得一个压缩的且具有普遍性的训练样本集合， p s w a l l i l m 提出了o l p s y n t h e s i s 算法4 3 1 。 4 k 值的选择 ( 1 ) 实际分类中，通常需要通过大量独立的测试数据、多个独立的模型来验证，才能 第二章分类挖掘与k 近邻算法概述 得到最优的k 值。 ( 2 ) 可以事先确定k 值，也可以使用动态的方法，文献【删就采用了动态k 值。然而， 有时各个类别的数据样本分布极不平衡，k 值的选择就非常困难，文献【4 5 1 针对这种情况 提出了k 值的选择方法。 2 5 本章小结 本章概述了分类挖掘的基础理论。着重介绍了常用的几种分类挖掘方法：决策树、 贝叶斯分类方法、k 近邻分类算法、基于关联规则挖掘的分类方法等，分析了它们的优 缺点。最后归纳了k 近邻分类算法的分类原理及研究现状。 本章为后续章节的展开奠定了一定的理论基础。 1 2 西北大学硕士学位论文 第三章基于模拟退火的组合k 近邻分类算法 通常单一的分类算法在面对复杂的分类问题时很难取得理想的分类效果。同时，各 种不同的分类算法之间常常具有互补性，将多个分类器集成起来不但可以提高分类正确 率，而且可以增强分类器的鲁棒性。因此，分类器的组合问题受到了广大学者的关注， 一直是数据挖掘和模式识别领域的研究热点。 3 1 组合分类器理论 分类器组合的初衷是扬长避短，即充分吸取每个分类器的优点，达到既能克服单一 分类器的局限性又能发挥每个分类器的最优性能的目的，从而取得最好的分类性能【倒。 下面将从组合方法的研究现状、分类器的组合方法和成员分类器的生成方法、分类器性 能及评价三个方面介绍组合分类器。 1 组合分类方法的研究现状 一般使用的分类方法，从某种意义上来讲都可以认为是一种映射函数，不同的分类 方法通常采用不同的映射函数。大量的分类实验和研究表明：被某一种映射函数错误映 射的数据样本，如果改用另一种不同的映射函数常常能得到正确的结果；一般而言，不 存在任何一种分类方法一直优于其他的方法。于是，分类器组合一将多个分类器的分类 结果组合起来形成一个组合分类器受到了广大数据挖掘工作者的广泛关注。目前，分类 器组合已经在部分领域得到应用，并表现出了良好的性能。 近些年来，广大学者对分类器组合的研究越来越深入。研究主要包括以下两方面： 第一，更进一步探明组合学习理论这种方法为什么有效及有效范围，以更好的为设计和 实现组合分类器提供理论依据；第二，探究怎么才能设计出更加有效的组合方法，以进 一步提高组合分类器的性能，并将其运用到现实的实际问题中。 分类器组合通常是将一个比较大的特征向量空间划分成多个比较小的特征空间，接 着在每个较小的特征空间上训练分类器，最后再将全部分类器组合成一个较大的分类 器。很显然，组合后的分类器较在整个特征空间上构造一个分类器有更好的时间和空间 效率。通常，通过组合性能较差、结构简单的成员分类器常常可以得到分类性能优于单 一复杂结构分类器的组合分类器。因此，组合分类器不但可以提高分类的正确率，同时 还可以降低分类的时间和空间复杂度，分类器组合的框图如图3 1 所示。 1 3 第三章基于模拟退火的组合k 近邻分类算法 原始样本 分类结果 图3 1 分类器组合结构框图 s c h a p i r e 在1 9 9 0 年利用构造性方法证明了强学习算法和弱学习算法的等价性，其构 造过程通常称之为b o o s t i n g 4 7 1 。b o o s t i n g 算法的主要思想是：当前分类器的训练数据样 本集取决于它之前的成员分类器，被之前的成员分类器错误分类的样本出现在当前分类 器的训练数据集中的概率将比较大；反之，被之前的成员分类器正确分类的样本出现在 当前分类器的训练数据集中的概率将比较小。r a t s c h 等人针对b o o s t i n g 算法边际效应理 论从提高最小边际的角度提出了b o o s t i n g 算法的多种改进算法；主要针对b o o s t i n g 算法 对噪音数据和离群点比较敏感的缺点，进一步提出了鲁棒b o o s t i n g 算法【4 s 】；统计学者 b r e i m a n 于1 9 9 6 年提出了b a g g i n g 算法【4 9 1 。 b o o s t i n g 算法和b a g g i n g 算法是组合分类器研究中最基本的成员分类器生成方法。 多年了，广大研究