（基础数学专业论文）加权knn算法及其应用.pdf

摘要 摘要 k n n ( k n e a r e s tn e i g h b o r ) 分类算法的结果依赖于距离度量的选取。传统的 k 近邻算法选择的相似性度量通常是欧几里德距离的倒数，这种距离通常涉及所有 的特征。在距离公式中引入一些特征权参数后，其分类结果将依赖于这些权值，从 而可以通过调整这些权值来优化分类效果。本文提出了一种学习权值算法以改进分 类准确率。从数学意义上讲，这种权值学习相当于欧氏空间中对一组点进行了一个 线性变换。同时，不同近邻样本本身的权重影响不同。则直接改变测试样本的最终 类别。我们不仅对每个属性学习权值，而且可以对每一个测试样本点的近邻基于它 们到测试点的距离进行加权，使得那些距离较近的近邻获得的权值较高，从而提高 了k n n 算法分类准确性。 针对k - 近邻算法中k 值的学习，本文总结了一种聚类有效性函数，数值实验 证实了其有效性，旨在指导应用于k 近邻分类中：然后还将“扩张能力”的概念引 入k 一近邻算法，根据训练集例子不同的覆盖能力，删除冗余样本，得到数量较d , n 时代表类别情况又比较完全的新的训练集，从而降低查找近邻复杂性。 关键词 k - 近邻；k 一均值；特征权；距离加权；扩张能力 a b s t r a c i i l q l a b s t r a c t t h ep e r f o r m a n c eo fk n 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 md e p e n d so nt h e s e l e c t i o no fd i s t a n c em e t r i c s t h ee u c l i d e a nd i s t a n c ei su s u a l l yc h o s e na st h es i m i l a r i t y m e a s u r ei nt h ec o n v e n t i o n a lk n na l g o r i t h m 。w h i c hu s u a l l yr e l a t e st oa l la t t r i b u t e s w h e nf e a t u r ew e i g h tp a r a m e t e r sa r ei n t r o d u c e dt ot h ed i s t a n c ef o r m u l a ，t h ep e r f o r m a n c e o fc l a s s i f i c a t i o nw i l ld e p e n do nt h ew e i g h tv a l u e sa n da c c o r d i n g l yc a nb ei m p r o v e db y a d j u s t i n gw e i g h tv a l u e s al e a r n i n gf e a t u r ew e i g h t sa l g o r i t h mi si n t r o d u c e dt oi m p r o v e t h ea c c u r a c yo fc l a s s i f i c a t i o n m a t h e m a t i c a l l yi tc o r r e s p o n d st oal i n e a rt r a n s f o r m a t i o n f o ras e to fp o i n t si nt h ee u c l i d e a ns p a c e a tt h es a m et i m e ，d i f f e r e n tn e a rn e i g h b o r s h a v ed i f f e r e n tr o l e st od e t e r m i n et h ef i n a lc l a s s e so ft e s t i n gs a m p l e s w en o to n l yl e a r n e d f e a t u r ew e i g h t sf o re a c hf e a t u r e ，b u ta l s ow e i g h t e dt h ec o n t r i b u t i o no fe a c ho ft h ek n e i g h b o r sa c c o r d i n gt ot h e i rd i s t a n c et ot h et e s t i n gs a m p l e s ，t h a ti s ，g i v eg r e a t e rw e i g h t s t oc l o s e rn e i g h b o r s s ow ec a ni m p r o v et h ea c c u r a c yo fc l a s s i f i c a t i o n f o rkv a l u el e a r n i n gi nk n n ，t h i sp a p e rp u t sf o r w a r dav a l i d i t yf u n c t i o nf o r j u d g ! n gc l u s t e r i n gi no r d e rt ol e a du st ou s ei ti nk n 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 n ；t h e n i n t r o d u c e s “g e n e r a l i z a t i o nc a p a b i l i t yo fac a s e ”t ok - n e a r e s tn e i g h b o r a c c o r d i n gt ot h e p r o p o s e da p p r o a c h ，t h ec a s e sw i t hb e t t e rg e n e r a l i z a t i o nc a p a b i l i t ya r em a i n t a i n e da st h e r e p r e s e n t a t i v ec a s e sw h i l et h o s er e d u n d a n tc a s e sf o u n di nt h e i rc o v e r a g ea r er e m o v e d w ec a nf i n dan e wl e s sb u ta l m o s tc o m p l e t et r a i n i n gd a t as e t ；c o n s e q u e n t l yr e d u c e c o m p l e x i t yo fs e e k i n gn e a rn e i g h b o r s k e y w o r d s ： k - n e a r e s tn e i g h b o r ；k - m e a n s ；f e a t u r e w e i g h t s ；d i s t a n c e w e i g h t e d g e n e r a l i z a t i o nc a p a b i l i t y a b s t r a c t 河北大学 学位论文原创性声明 本人郑重声明；所里交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外。论文中不包含 其他人已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学 位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了致谢。 作者签名： j ：塞日期：a 2 赵年月监日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定。即：学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被奄阅和借阅。学校 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 1 、保密口，在年月曰解密后适用本授权声明。 2 、不保密日。 ( 请在以上相应方格内打“4 ”) 作者签名：j 壹：是日期：笠丛年厶月韭日 导师签名：坦 日期：_ 垒逸堂年厶月监日 。，。，。呈：耋二塑兰二，。，。，。一目! ! ! ! _ e ! ! ! ! ! ! ! ! ! 目_ | _ 口t z | e 目e 目_ _ j e l _ _ _ e e e _ _ _ _ e 目= e j z _ 目一 第1 章绪论 1 1 国内外在该方向的研究现状 1 1 1 数据挖掘 随着数据库技术的飞速发展，人工智能领域的一个分支一一机器学习的研究自 2 0 世纪5 0 年代开始以来也取得了很大进展。用数据库管理系统来存储数据，用机器 学习的方法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了数据库中的 知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，简记k d d ) 的产生。也称作数据挖掘 ( d a t am i n g ，简记d m ) 。 数据挖掘是信息技术自然演化的结果。信息技术的发展大致可以描述为如下的过 程；初期的是简单的数据收集和数据库的构造；后来发展到对数据的管理，包括：数 据存储、检索以及数据库事务处理；再后来发展到对数据的分析和理解，这时候出现 了数据仓库技术和数据挖掘技术。数据挖掘是涉及数据库和人工智能等学科的一门当 前相当活跃的研究领域。 数据挖掘是机器学习领域内广泛研究的知识领域，是将人工智能技术和数据库技 术紧密结合，让计算机帮助人们从庞大的数据中智能地、自动地抽取出有价值的知识 模式，以满足人们不同应用的需要。目前，数据挖掘已经成为一个具有迫切实现需 要的很有前途的热点研究课题。 数据挖掘技术能从数据仓库中自动分析数据，进行归纳性推理，从中发掘出潜在 的模式，或产生联想，建立新的业务模型，这是一个高级的处理过程。高级的处理过 程是指一个多步骤的处理过程，多步骤之间相互影响、反复调整，形成一种螺旋式上 升过程。数据挖掘的功能用于指定数据挖掘任务中要找的模式类型，其任务一般分为 两类：描述和预测。描述性挖掘任务刻画数据库中数据的一般特性，预测性挖掘任务 在当前数据上进行推断，以进行预测。在实际应用中，往往根据模式的实际应用细分 河北大学理学硕士学位论文 为以下六种：( 1 ) 分类模式。( 2 ) 回归模式。( 3 ) 时间序列模式。( 4 ) 聚类模式。( 5 ) 关联模式。( 6 ) 序列模式。在解决实际问题时，经常要同时使用多种模式。分类模式 和回归模式是使用最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受 监督知识，因为在建立模式前数据的结果是已知的，可以直接用来检测模式的准确性， 模式的产生是在受监督的情况下进行的。一般在建立这些模式时，使用一部分数据作 为样本，用另一部分数据来检验、校正模式。聚类模式、关联模式、序列模式则是非 监督知识，因为在模式建立前模式是未知的。模式的产生不受任何髓督1 2 l 。 1 1 2 该方向的研究现状 本课题主要研究的是数据挖掘分类算法中的k 近邻算法。 有关k n n 算法例如文献【3 ，4 】谈到过计算复杂性的优化和分析，减少计算量。香 港中文大学的w a il a i n 等人将k n n 方法和线性分类器结合，取得了较好效果，在 召回率接近9 0 时准确率超过8 0 晡1 。w t o d z i s t a wd u c h 提出了通过选取特征对加权 k - n n 的研究旧】。文献【7 】提出了一种基于近邻搜索的快速k 近邻分类算法超球搜 索法。该方法通过对特征空间的预组织，使分类得以在以待分样本为中心的超球内进 行。超球半径由零开始逐渐增大至超球内包含k 个以上模式样本为止。这一方法有 效地缩小了算法搜索范围，同时预组织和预分类简单明了，无需复杂的训练，不存在 收敛性问题。文献【8 】研究了回归函数k 。一近邻估计的渐进性质，得到了回归函数的 k n 一近邻估计的渐进正态性和它的b o o t s t r a p 统计量的相合性。文献【9 】为近邻算法建 立一个有效的搜索树，提高了查询速率。文献【l o 】提出了一种迭代近邻法，用以解决 k n n 算法在小样本库的环境下分类效果不佳的问题，在无法得到足够的定类样本 时，通过检索的方法将待分样本的局部主题特征放大，进而得到足够定类的相似样本。 文献 1 l 】分析了传统的近邻文本分类方法技术以及w e b 文本的特点，充分利用了w e b 文本的结构信息进行特征词加权，以类轴向量为核心构建分类器。文献 1 2 】提出了加 权k 近邻的方法，对训练集x 内的每一个样本点，给定一个临界半径，对一个待识 别样本，比较其与训练集中每个样本点的加权距离。文献【1 3 针对欧几里德空间的 k 一近邻，给出了其在可重构网孔机器上( r m e s h ) 的并行算法。 1 2 课题研究的目的和意义 近邻方法是在一组历史数据记录中寻找一个或者若干个与当前记录最相似的相 似历史纪录的已知特征值来预测当前记录的未知或遗失特征值【i 。k n n ( k 一近邻) 是基于统计的分类方法”】。近邻方法是数据挖掘分类算法中比较常用的一种方法。 k - n n 分类算法根据待识样本在特征空间中k 个最近邻样本中的多数样本的类别来进 行分类，因此具有直观、无需先验统计知识、无师学习等特点，从而成为非参数分类 的一种重要方法。但是基本k n n 分类算法需要进行全局搜索，计算的时阋复杂性大， 速度慢。 大多数分类方法是基于向量空间模型的。当前在分类方法中，对任意两个向量 x = ( ，x ：，“) 与x = ( z ：，t ) ，存在3 种最通用的距离度量；欧氏距离、余 弦距离1 和内积”】。有两种常用的分类策略。一种是计算待分类向量到所有文本向 量( 训练集中) 的距离；如k 一近邻选择k 个距离最小的向量然后进行综合，以决定 其类别。另一种是用训练集中的向量构成类别向量，仅计算待分类向量到所有类别向 量的距离，选择一个距离最小的类别向量决定类别的归属。很明显，距离计算在分类 中起关键作用。由于以上3 种距离度量不涉及向量中特征之间的关系，这使得距离的 计算不精确，从而影响分类的精度。 下面分3 种情况说明： ( 1 ) 无用特征的影响：在分类算法的向量空间模型中，向量的维数常常是很多维 的a 所谓无用特征是指与类别无关的特征。也就是各个类别中均可以出现的特征，它 不代表类别的特点。必须要进行删除，否则他们将会导致距离的计算4 i 准确，即向量 阃的距离远近将被无关特征的出现与否所影响。 ( 2 ) 特征间关系的影响；我们认为如果不考虑特征间的关系，距离的计算同样会 存在问题。例如在文本分类中，可分两种情况说明：一种是同义词的影响，另种是 具有某种语义关联词的影响。 ( 3 ) 特征间地位不平等性的影响：特征对类别支持作用大小尽管可用权值大小来 体现，但我们觉得还不够。存在一些特征对类别具有强的支持作用( 决策特征) ，它 们的存在可以在很大程度上决定类别的归属。而在向量空间模型中，这种决策作用将 4 i 2 1 拘存在可咀在很大程度上决定类别的归属。而在向量空间模型中，这种决策作用将 河北大学理学硕士学位论文 可能被众多非决策特征的影响所淹没掉”引。 针对于k 一近邻算法中，选取不同的k 值对分类结果有很大的影响，也就是说， 不同的k 值直接决定分类结果的正确率f 蝤】。如图1 1 所示： 图1 1 近邻k 值的影响 其中具有星号和加号丽类数据，圆心测试数据点如果采用1 近邻则应该属于加 号类，如果采用6 近邻则属于星号类。所以说，采用怎样的k 近邻个数是分类结果 正确与否的关键条件之一。 查找近邻的效率问题也是值得研究的一项内容。k 近邻分类算法需要进行全局搜 索，计算的时间复杂性大速度慢。当训练集数据量非常大时。寻找近邻就需要相应 的提高效率算法，使得查找速度提高。像在文中1 1 2 中所述的，目前已有的一些快 速k 一近邻分类算法，尽管在提高快速性方面作了一些改进，但是有的需要事先进行 大量复杂的训练并且存在着收敛性问题，有的同样需要进行全局搜索并且对搜索顺序 敏感。 分类算法中，k - n n 算法是实现简单同时正确率较高的一种方法，所以对它进一 步的研究可以优化原算法性能，使其对数据分类更具有全面性。在原始算法中采用加 权思想，可以提高k n n 算法分类准确性，有效处理噪音数据。本文同时对k 值的 确定以及查询效率的问题做了相关研究，提出了改善性能的方法，解决了全局搜索的 麻烦。 第1 章绪论 | 自o _ _ _ e _ _ 目e 目_ _ _ e _ i i _ _ l _ _ l l - _ _ - - _ _ _ _ - _ _ l _ _ _ _ | _ - _ l _ _ _ _ j l ! l ! 目e 目_ g ! s _ 1 3 主要研究内容 本文的主要研究内容是加权k 一近邻算法及其应用。 第1 章主要叙述了国内外在本方向的研究现状，以及本课题研究的目的和意义。 本文分析了原始的距离度量不涉及向量中特征之间的关系，使得距离计算不精确，不 能反映各个特征之间的重要程度因此，本文提出了相似度量的特征权值学习方法； 同时对于近邻的范围内，不同近邻样本本身的权重影响不同，则直接改变测试样本的 最终类别。所以还可以对每一个测试样本点的近邻基于它f f f l - n n 试点的距离进行加 权。分类算法中k 一近邻算法的k 值一直没有方法找到合适取值，因此提出经验性取 值结论很有必要。本文力求找到合适的方法对k 值进行确定，在提高查找效率的基 础上简化k 值寻找的过程。 第2 章介绍了k 一近邻分类算法的基本原理知识。近邻算法是数据挖掘分类算法 中比较常用的一种方法。k 一近邻是基于统计的分类方法。主要介绍了k 近邻分类算 法原理和基本思想，以及算法本身的缺点分析，为第3 章提供了研究依据。 第3 章详细叙述了本文研究课题的内容，是本文学习研究的主体。首先是学习特 征权值对k 一近邻分类算法的优化，体现了不同特征不同的重要程度；随后对每一个 测试样本点的近邻基于它们到测试点的距离进行加权，使得那些距离较近的近邻获得 的权值较高：然后将聚类有效性判断应用在k 近邻算法中，当数据集分布满足函数 条件时，采用最近邻方法以提高近邻选择的效率；最后提出了“扩张能力”的概念， 在k 一近邻算法中将训练集例予根据其不同的覆盖能力，删除冗余样本，从而能够提 高算法查找的效率。 第4 章是本文的结论与展望。主要分析了本文对k - 近邻分类算法中特征权学习、 距离加权学习、k 值分析的优点和不足，并对进一步的研究内容提出了展望，在k 值确定方法以及优化算法的应用都是值得继续深入的方向。 河北大学理学硕士学位论文 2 1 分类算法 第2 章k 一近邻分类算法 分类模式挖掘技术作为数据挖掘的重要分支将对电信、银行、保险、零售、医疗等 诸多行业提供决策支持，对未来商业和人们的生活也将产生深远的影响。 数据分类( d a t ac l a s s i f i c a t i o n ) 是数据挖掘中一项非常重要的任务，目前在商业上 应用最多。分类的1 7 1 的是学会一个分类函数或者分类模型( 也常常称为分类器) ，该模 型能把数据库中的数据项映射到给定类别中的某一个。例如：可以建立一个分类模型， 对银行贷款的安全或风险进行分类。许多分类的方法已被机器学习、专家系统、统计学 和神经生物学方面的研究者提出。 数据分类实际上就是从数据库对象中发现共性，并将数据对象分成不同几类的一个 过程，可以分成两步进行( 图2 1 ) 。第一步，建立一个模型，描述预定的数据类集或概 念集。通过分析由属性描述的数据库元组来构造模型。假定每个元组属于一个预定义的 类，有一个类标号属性( c l a s sl a b e la t t r i b u t e ) 的属性确定。对于分类，数据元组也称 为样本、实例或者对象。为建立模型而被分析的数据元组形成训练数据集( t r a i n i n gs e t ) 。 训练数据集中的单个元组称为训练样本，并随机的由样本集中选取。由于预先知道每个 训练样本的类标号，这个建立模型的学习过程属于有指导的学习( 即模型的学习在知道 每个训练样本属于哪个类的指导下进行) 。这不同于无指导的学习( 如聚类) ，无指导的 学习中每个训练样本的类标号事先是未知的，要学习的类集合或者数量也是事先不知 道，整个学习的过程是在无指导的情况下进行的。 通常，通过第一步的学习建立的模型用分类规则、决策树或数据公式的形式表示。 例如：给定一个顾客信用信息的数据库，通过分类算法学习得出分类规则，根据这些规 则，决定顾客的信誉好坏。即这些规则就是分类模型，可以利用这个模型为其他数据样 本进行分类，同时也能对数据库的内容提供更好的理解( 图2 1 a ) 。 第二步( 图2 1 b ) ，使用建好的模型进行分类。首先要评估模型的预测准确率。最 第2 章k - 近邻分类算法 常用的一种方法是保持( h o l do u t ) 方法，该方法使用类标号样本测试集，这些样本随 机选取，并独立于训练样本集，即测试样本集完全不同于训练样本集。模型在测试样本 集上的准确率是指正确被模型分类的测试样本的百分比。对于每个测试样本，按照分类 模型学习得山的预测类与已知的类标号比较，如果相同，则表示分类成功；不相同，则 表示分类不成功。之所以使用完全不同于训练样本集的测试样本集，是因为学习模型倾 向子过分适合数据，即是学习模型可能并入训练数据中某些特别的异常数据，而这些异 常不出现在总体样本集中。如果仍使用训练数据评估分类模型，则可能评估总是乐观的。 如果认为模型的准确率可以接受，就可以利用这个模型对类标号未知的数据元组或 对象进行分类。例如：在通过分析现有顾客数据学习得到的分类规则可以预测新的顾客 信誉的好坏1 9 鲫。 分类具有广泛的应用，包括信誉证实、学习用户兴趣、性能预测、市场调查m 1 、新 闻分发、邮件分类以及医疗诊断2 4 蝽。 、，、 a ) 学习：在训练数据上用分类算法学习，学习模型用分类规则的形式表示 b ) 分类： 在测试数据上评估分类规则的准确率，如果准确率可以接受则分类规则可用于新的数 据元组的分类 图2 1 数据分类的过程 目前，有多种分类方法和算法，主要有统计方法、机器学习方法、神经网络方法等。 分类算法一般分为l a z y 和e a g e r 两种类型。称之为l a z y 学习算法的原因是它从局部出 发，推迟对训练例子的归纳过程，直到一个新的测试例子出现，例如k 近邻( k - n e a r e s t n e i g h b o r ) 算法、局部加权回归( l o c a l l yw e i g h t e dr e g r e s s i o n ) 、基于案例的推理 ( c a s e 。b a s e dr e a s o n i n g ) 等：而e a g e r 学习算法则是从全局出发，在新的测试例子出现 之前，由训练例子总结归纳出相似判断的目标函数，这个目标函数应用于训练数据和测 试数据，例如决策树( d e c i s i o nt r e e ) 、b p ( b a c k p r o p a g a t i o n ) 神经网络算法、径向基 河北大学理学硕士学位论文 函数( r a d i a lb a s i sf u n c t i o n s ) 、遗传分类方法、粗糙集分类方法等。l a z y 算法我们将在 2 3 中以k 近邻举例介绍，而e a g e r 方法我们以决策树为例进行介绍。 归纳学习旨在从大量的经验数据中归纳拙取一般的判定规则和模式，它是机器学习 最核心、最成熟的分支。决策树归纳学习算法以q u i n l a n 在1 9 8 6 年提出的i d 3 为代表， 它是一种基于信息增益的典型自上而下的决策树归纳方法。以决策树为知识表达形式， 具有描述简单、分类速度快、计算量小的特点，能归纳出一种较“好”的树，且适用于 大规模数据集的学习问题。模糊i d 3 算法( f u z z y i d 3 ) 是传统i d 3 算法在模糊环境下 的一种推广，这种算法能处理与人的思维和感觉有关的不确定性，因而应用更为广泛。 模糊i d 3 算法的核心是使用模糊信息熵来选择扩展属性，根据所选的属性来分割决策树 中当前节点的数据，从而生成一棵决策树。模糊决策树产生过程包括以下几个步骤： 1 ) 训练数据的模糊化。将数据集按一定比例分成训练集和测试集，模糊化过程使 用所有训练例子，根据迭代自组织的模糊聚类算法产生全局中心，并由此中心模糊化所 有训练例子及测试例子。 2 ) i d 3 算法是在模糊化后的所有训练例子的基础上进行。树的建立过程如下： 对每属性计算信息增益，用具有最大信息增益的属性来扩展根节点。 删除节点的空分支，对节点的每一非空分支计算属于这一分支的所有对象分到 每一类的真实水平矗若分到某一类的真实水平超过阈值，则终止这一分支作为 一个叶子( 标记为当前类) 。否则考察另一个属性是否能继续分割这个分支并进一 步增加信息增益。如果能，则选择具有最大信息增益的属性作为决策节点，如果不 能- 则终止这一分支作为一个叶子。在叶子节点，所有的对象以最高的真实水平属 于同一类。 对于每一新生成的决策节点重复第2 步，直到不能向下扩展。决策树建立完成。 3 ) 将决策树转化为一组规则，其中每条规则是从根节点出发到叶子节点的一条路 径。 4 ) 将得到的这组全局规则应用于训练例子，得到分类的训练准确率；然后将所有 测试例子与规则逐一匹配。得到分类的测试准确率。 从二者的算法中，我们可以看出l a z y 和e a g e r 这两种分类方法有本质的不同。从 计算时间的角度讲，训练阶段l a z y 方法基本不需要计算时间，但是当个新例子到来 第2 章k l 近邻分类算法 时就需要对其预测目标函数值，所以测试阶段的计算量比较大。而e a g e r 方法则与之相 反，训练阶段需要计算得到目标函数，所以训练阶段的计算量比较大；从对新例子分类 的角度讲，l a z y 总是当新例子到来时才开始预测，而e a g e r 在训练阶段就完成了对所有 例子目标函数的建立。因此，它们的归纳偏好不同，l a z y 侧重当前具体例子具体分析， 而e a g e r 在遇到测试例子之前就已经为其选择了对应的目标函数。这两种分类方法哪一 种更具有概括性昵? 假设在同样的假说空间解决问题，l a z y 方法明显具有更丰富的假说 空间，因为它可以选择多个局部相似的组合来表示目标函数；e a g e r 方法则在训练阶段 必须确定一个全局相似。所以通过实验对两者进行研究比较，从而可以对实际应用算法 选择提供经验性结论，具有很好的实际意义2 4 】。 除上面的分类算法之外，还有用关联规则进行分类的方法：聚类关联规则进行分类 的方法( a r c s 分类) 、基于关联的分类方法、聚集显露模式分类法( c a p e 分类) 。提 高分类法准确率的技术：装袋( b a g g i n g ) 技术和推进( b o o s t i n g ) 技术 2 5 - 2 8 】。 现在广泛应用的基于统计的模型有向量空间模型、n a i v eb a y e s 概率模型、实例映 射模型和支撑向量机模型。n a i v eb a y e s 模型是基于两项假设之上的一种概率分类模型。 支撑向量机是一个用于解决模式识别问题的机器学习方法。它是基于结构风险最小化原 理。映射模型的主要思想是把分类问题转化为矩阵变换的问题。其中变换矩阵用奇异值 分解的方法求得。但实例映射模型需要大量的良好代表性文档。相对于向量空间，实例 映射模型计算量大，分类速度慢且精度较低。 向量空间模型( v e c t o rs p a c em o d e l v s m ) 是由gs a l t o n 等人在2 0 世纪6 0 年代提 出的。它把文档分类简化为以项的权重为分量的向量表示，把分类过程简化为空间向量 的运算，使得问题的复杂性大大减低。此外，向量空间模型对项的权重评价、相似度的 计算都没有作出统一的规定，只是提供一个理论框架，可以使用不同的权重评价函数和 相似度计算方法，使得此模型有广泛的适应性1 8 】。 2 2 基于实例的学习算法 基于实例的学习算法并不像上面介绍的决策树算法等分类算法一样建立明确的分 类规则，而是直接存储训练样本，并没有在训练样本的基础上获取一个模拟输出函数。 当一个测试样本点到来时，才开始计算训练样本与其的相似度，从而确定未知样本的分 河北大学理学硕士学位论文 类。也就是说，基于实例的学习算法是对每一个测试样本点都创建相应不同的目标输出 函数，这是跟神经网络算法、决策树算法不同的思想。事实上，很多技术都对测试样本 点的浆一个近邻范围内创矬局 _ | ；模拟函数，而不是在挫个训练样本空间传见测试样水的 模拟输山函数。这种局部近似的优点是当目标函数比较复杂时，可以选择相对简单的局 部模拟函数进行分类输出， 但是基于实例的学习算法有一个明显的缺点是对每一个测试样本点分类的计算代 价相对较高。这主要是因为算法把所有的计算都在一个测试样本点到来的时候开始的。 因此在查询时间内减少计算复杂度是有效提高算法的实际问题。基于实例学习算法的另 一个缺点是在寻求测试样本点与训练样本点的相似度时，考虑了描述样本点的所有属 性，那么就有可能出现第一章1 2 中叙述的，如果不考虑所有属性而只参考一部分属性 的话，两个样本点可能相似度会有很大的变化【2 4 1 。 2 3k 一近邻分类算法 近邻算法是基于实例学习的分类算法中比较常用的一种方法。k 近邻是基于统计的 分类方、法【2 引，是根据测试样本在特征空间中k 个最近邻样本中的多数样本的类别来进 行分类，因此具有直观、无需先验统计知识等特点，从而成为非参数分类的一种重要方 法。 算法假定所有的例子都处于维空问，一般每个例子x 都被表示为特征向量 ，这里n ，( 曲表示例子工的第r 个属性值。那么两个例子而，x ，之间 的相似度量可以采用欧氏距离： r = _ 一 d ( x i , x j ) = j z , a , ( 一) 一a ，( x j ) ) 2 ( 2 1 ) 算法的基本思想是： 1 ) 产生训练集，使得训练集按照已有的分类标准划分成离散型数值类，或者是连 续型数值类输出。 2 ) 以训练集的分类为基础，对测试集每个样本寻找k 个近邻，采用欧氏距离作为 样本间的相似程度的判断依据，相似度大的即为最近邻。一般近邻可以选择1 个或者多 第2 章k 近邻分类算法 个。 3 ) 当类为连续型数值时，测试样本的最终输出为近邻的平均值：当类为离散值时， 测试样本的最终输出为近邻类中个数最多的那一类。 对于离散值目标函数输出形式为： f ：9 1 “_ v ，w h e r e v i s t h e f i n i t es e t f v l ，仉 对于连续值目标函数输出形式为： 、善“x i ) ( 2 2 ) f ( x 口) 卜旦_ 一 判断近邻就是使用欧氏距离测试两个例予之间的距离，距离值越小的表明相似性越 大，反之则表明相似性越小。 k 近邻算法的一个明显缺点是不同的数据库采用k 近邻算法，很难确定合适的k 值，需要经过不断地实验找到合适的取值。目前的研究中只是给出了大概范围1 。万( 表示数据库中训练样本个数) 2 5 2 9 。 同时，跟一般的基于实例的学习算法一样，由于k 一近邻算法目前采用的相似度测 量使用的是欧氏距离或者是余弦距离和内积，因此对于属性的相关性比较敏感。当属性 无关的比较多时，找到的“近邻”就不是真正的“近邻”。即判断近邻的距离度量不涉 及向量中特征之间的关系，这使得距离的计算不精确，从而影响分类的精度。这样得出 的实验结果就不准确了。因此进一步解决无关属性问题是近邻算法的主要优化目标之 一。所以在原始算法中采用加权思想，可以提高k n n 算法分类准确性，有效处理噪音 数据。 k 一近邻分类算法也是在每一个测试样本点到来时才进行全局搜索，与所有的训练样 本点比较相似度，计算的时间复杂性大，速度慢。因此查找近邻的效率问题也是值得研 究的一项内容。 河北大学理学硕士学位论文 i ii i 第3 章加权k 一近邻算法及其应用 3 1 学习特征权值对k 一近邻分类算法的优化 3 1 1 特征权值的学习 大多数分类方法是基于向量空间模型的。当前在分类方法中，对任意两个向量 x = ( x 。，工：，x 。) 与x = ( 墨，x ：，z ：) ，存在3 种最通用的距离度量：欧氏距离、余弦 距离和内积7 1 。 传统的k 近邻算法选择的相似性度量通常是欧几里德距离的倒数，也就是说两者 的距离越小表示两者的相似性趟大，反之则相似性越小。由欧氏距离式( 2 1 ) 可见这种 距离通常涉及到所有的属性，且认为这些属性对距离影响的程度是等同的。 “同等重要地依赖所有属性的相似性度量会引起误导，这种由不相关属性引起误导 的现象被称作维数陷阱”。k 近邻算法对这个问题是非常敏感的。例如：假定要分类的 向量具有2 0 维属性，其中只有2 维属性对分类最相关，这2 维属性具有相似值的向量 在2 0 维属性空间中却有可能距离最远，此时由2 0 维属性等同作用的相似度量就引起了 误导州。克服此问题的有效方法之一就是为每一个属性加一个特征权参数，让不同的属 性在分类中起不同的作用。从欧氏空间上来说就是拉长相关属性对应的轴，缩短无关属 性对应的轴。本文的主要工作是如何学习加权距离式( 3 1 ) d ( x k ，c i ) = ( w ，( 一勺) ) 2( 3 1 ) j = l 中的特征权值w ，以改进k 近邻算法的分类性能。 当距离公式( 2 1 ) 式中的0 以一c i 旷用( 3 1 ) 式中的( w ( 一c 口) ) 2 来代替时，向 j = l 量间相似程度将依赖于( 3 1 ) 式中的权值w ，。如何调整权值w j 决定在相似度量中确定 第3 章加权k 近邻算法及其应用 属性的重要程度，学习特征权值是一种改进k 近邻分类算法的有意义的工作。以下我 们提山了一剃t 学习权值w j 的方法。 加权相似矩阵将向量e 。和e 。的相似度量表示为： p 等k 南 ( 3 。2 ) ，。、1 ，2 d 努= d 1 ( e ，) = iz w j x 。一) 2l ( 3 - 3 ) 其中，q ；( _ 。，：，x i m ) ，为向量岛的属性分量，卢是一个正参数， 当w = ( 1 ，l ，1 ) 时，p 等即为权值没有调整的相似度量值。由式( 3 t 3 ) 我们可以看 到两个向量间的相似程度与权值的具体取值有关。 s a n k a p a l 在 3 0 1 q b 注意到一个简单的函数：f ( x ，y ) = x ( 1 - y ) + y ( 1 - x ) ( 1 x ，y 曼1 ) 。 由于罢= 1 2 y ，它具有以下的性质：如果y o ；如果y o 5 ，则娑 0 5 ，则f ( x y ) 随着x 的增加而单调递减，从而达到极小的充要条件为 x - 1 如果y 0 5 ，则f ( x ，y ) 随着鼻的增加而单调递增，从而达到极小的充要条件为 x _ 0 。 基于这个性质可以构造下面的一个评价函数，通过极小化这个评价函数来降低相似 矩阵的模糊性： f ( 计。丽2 丽q o 5 时) 或p 嚣_ o 【当 硝 0 5 时，新的相似性p 嚣将趋向于最大值i 。 ( b ) 当旧的棚似性p 等 0 ，应用公式w j + a w j 更新权值w j 。 6 ) 重复( 3 ) ，( 4 ) 和( 5 ) 步骤。如果可w ) 的值低于或等于一个最小闽值或者迭代次数超 过某一次数闽值时结束学习。 一般特征权值可以控制在o 1 之间，可以使用正则化方法减小搜索空间的大小，当 然，也可以不限制权值的取值范围。 当原型中一组向量相似性较大( o 5 ) 时，可以通过学习特征权值改变它们属于同 一类的程度，使其相似性变大。当原型中一组向量相似性较小( o 5 ) 时，可以通过学 习特征权值减小它们的相似性。因此这样通过极小化e 。( w ) 学习到的即为特征向量的权 值，确定了不同特征向量在相似度量上的不同作用，从而改善了分类性能。 为了解释以上的学习思想，我们从u c i 机器学习数据库3 3 1 ( m a c h i n el e a r n i n g r e p o s i t o r y ) 中选取了i r i s 数据作为图示数据，如图3 1 、3 2 所示( 同一组数据的不同表 示) 。图3 1 特征权值为( 1 ，1 ，0 。o ) ，图3 2 特征权值为( o ，0 ，1 ，1 ) 。实验分析得出，在权值为 原始( 1 ，1 ，1 ，1 ) 的情况时分类情况介于图3 1 与图3 2 之间，说明权值学习的好坏直接影响 分类效果。由于四维数据无法用图形表示，所以我们选择了权值为( 1 ，1 ，0 ，o ) 和( 0 ，o , 1 ，1 ) 作 为比较。其中特征权值为o 相当于各数据轴拉伸收缩后从四维空间到二维空间的投影 ( 这里只选取了原数据中的两类) 。 通过图示我们发现，在图3 1 中两类间存在混合交叉，图3 2 分类效果要优于图3 1 ， 在图3 2 中两类间的界限相对清晰，通过投影效果使得分类结果有所改善，这说明了分 类结果的确依赖于特征权值。权值学习的好，那么对应的分类效果也好。对于图3 1 ， 加权后k 一近邻分类测试准确率为7 2 ；而对于图3 2 ，计算加权后k 近邻分类测试准 确率为9 8 。从而说明在分类问题中相关属性的确定是很有必要的尤其是当原始数据 中无关属性较多的时候。 通过以上理论及实验证明，学习的特征权值是正确和有效的。分类结果的确依赖于 特征权值。权值学习的好，那么对应的分类效果也好。当原始数据对应的无关属性较多， 也就是属性的决定作用互不相等时，即属性对应的权值不是原始的相同值1 ，采用此方 f i f f 1 l g 入学理学碘上学位论文 法是比较有效的。如图3 1 和3 2i ：lj ，数据不同属性的决策价值就不尽相同，不同的权 值决定了不同的分类准确牢第三个、第四个j 蟊 性比第一个、第二个属性要重要使用 它们可以获得更高的准确率。 图3 1 权值( 1 ，1 ，0 ，0 ) 图示图3 2 权值( 0 ，0 ，1 ，1 ) 图示 3 1 2 数值实验及分析 为了进一步证明学习特征权值的有效性和正确性，我们从u c i 机器学习数据库中选 取了5 个数据库，它们是( 1 ) i r i sd a t a ，( 2 ) r i c e t a s t e d a t a ，( 3 ) p i m a ，( 4 ) e c o l i 。( 5 ) g l a s s 。 对这些数据库，我们比较了k 一近邻算法在加权前后测试准确率变化的情况。学习权值 前应用近邻算法得到的测试准确率写作a j ，学习权值后应用近邻算法得到的测试准确 率写作a 2 ，如表3 1 所示。 表3 1 学习特征权值前后分类性能比较 实验分析及说明： 1 ) 通过上面数值实验对加权前后近邻算法测试准确率的比较，可以证实学习特征权值 的确可以提高k 一近邻分类算法的性能，例如在数据库g l a s s 、e c o l i 中测试准确率比 学习之前有很大提高，其有效性是非常明显的。 第3 章加权k 一近邻算法及其应用 2 ) 学习特征权值使得无关属性的影响尽量减小，甚至权值可以学习为零。从这种意义 上讲，特征权值的学习是特征选取的一种推广。它不仅可以提高分类算法的性能， 同时可以减少特征维数，将一些不重要的属性删去不用。 3 ) 学习特征权值方法改善分类性能的好坏一般依赖于具体数据库和各种具体特征。例 如数据库g l a s s 、e c o l i 、i r i sd a t a 测试准确率提高较多。原