K-近邻研究应用.doc

研究基于分类的K-近邻算法设计方案第一章 绪论模式识别又常称作模式分类，从处理问题的性质和解决问题的方法等角度，模式识别分为有监督的分类（Supervised Classification）和无监督的分类(Unsupervised Classification)两种。二者的主要差别在于，各实验样本所属的类别是否预先已知。一般说来，有监督的分类往往需要提供大量已知类别的样本，但在实际问题中，这是存在一定困难的，因此研究无监督的分类就变得十分有必要了。模式还可分成抽象的和具体的两种形式。前者如意识、思想、议论等,属于概念识别研究的范畴,是人工智能的另一研究分支。我们所指的模式识别主要是对语音波形、地震波、心电图、脑电图、图片、照片、文字、符号、生物传感器等对象的具体模式进行辨识和分类。模式识别研究主要集中在两方面,一是研究生物体(包括人)是如何感知对象的，属于认识科学的范畴,二是在给定的任务下,如何用计算机实现模式识别的理论和方法。前者是生理学家、心理学家、生物学家和神经生理学家的研究内容,后者通过数学家、信息学专家和计算机科学工作者近几十年来的努力,已经取得了系统的研究成果。模式识别或者通俗一点讲自动分类的基本方法有两大类，一类是将特征空间划分成决策域，这就要确定判别函数或确定分界面方程。而另一种方法则称为模板匹配1，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。近邻法则在原理上属于模板匹配。分类的方法包括统计的方法、近邻法、神经网络分类法、无监督聚类法和新出现的基于统计学习理论的支持向量机法，K-近邻分类法是近邻分类法的扩展。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻) ，就按最近似的模板的类别作为自己的类别。譬如A类有10个训练样本，因此有10个模板，B类有8个训练样本，就有8个模板。任何一个待测试样本在分类时与这18个模板都算一算相似度，如最相似的那个近邻是B类中的一个，就确定待测试样本为B类，否则为A类。因此原理上说近邻法是最简单的。1.1 课题背景及目的数据挖掘是近年来很多领域竟相研究的一个热点领域，而分类器是数据挖掘的一个研究分支2。为了研究基于分类的K-近邻算法，先对数据挖掘做一个概要的介绍。数据挖掘是八十年代，投资AI研究项目失败后，AI转入实际应用时提出的。它是一个新兴的，面向商业应用的AI研究。数据挖掘是从大量的数据中，抽取出潜在的、有价值的知识（模型或规则）的过程。数据挖掘有分类、估值、预言、相关性分组或关联规则、聚集、描述和可视化六种分析方法。本文讨论的分类就是首先从数据中选出已经分好类的训练集，在该训练集上运用数据挖掘分类的技术，建立分类模型，对于没有分类的数据进行分类。K-近邻法是最显著的模式识别系统统计学方法之一，已经有40多年的历史，它很早就被用于文本分类研究。K-近邻算法的最大优点是：简单，直观，容易实现，应用范围广，几乎可以用于各种不同类型的数据结构；知识以样本的形式表示，不需要进行模型的训练，容易获取，维护方便；在关系数据库中，算法可以用SQL语句来实现；非常适用于分布是计算。缺点是：需要大量的已经准备好的历史数据；在对一个新样本分类时，要搜索所有的训练样本来寻找最近的邻居，计算量大，时间代价高；由于训练数据常驻内存，会占用大量的内存；且分类结果与参数有关。在模板数量很大时其错误率指标还是相当不错的。也就是说近邻法的研究还是有必要的。1.2 国内外研究状况近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高，无数个数据库被用于商业管理、政府办公、科学研究和工程开发等，这一势头仍将持续发展下去。于是，一个新的挑战被提了出来:在这被称之为信息爆炸的时代，信息过量几乎成为人人需要面对的问题。如何才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢?要想使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。因此，面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识发现(DMKD)技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。由于K-近邻法实际应用效果好，但又因算法问题而使其计算量大，时间代价高；由于训练数据常驻内存，会占用大量的内存，增加成本。所以国内外对于K-近邻法的研究主要在分为两部分：一.对其算法的的改进研究辽宁工程技术大学的张宇3提出了一种出了一种利用随机属性子集组合k-近邻分类器的算法通过随机的属性子集组合多个k 近邻分类器, 利用简单的投票, 对多个k-近邻分类器的输出进行组合, 这样可有效地改进k-近邻分类器的精度。广东石油化工学院计算机与电子信息学院的周靖，刘晋胜4采用特征相关性差异优化距离的改进k近邻算法。可以有效地解决 近邻算法训练样本规模及分类精度间的矛盾，提出了一种采用特征相关性差异优化距离的改进算法(FCDKNN)。 该算法将特征熵值与其分布概率的乘积作为特征相关性的概念， 在此基础上定义围绕特征相关性差异的样本距离测度，明确特征在类别上的重要性及相关性，在小样本情况下提取针对分类的大量有效信息，以增强算法的全局优化能力。对比仿真实验结果表明， 该算法在保持效率的情况下分类精度得到了极大地提高。中国地质大学计算机科学系的陆微微, 刘晶6提出了一种一种提高 K- 近邻算法效率的新算法。此方法是基 于凹凸轮廓结构特 征估计轮廓的宽度与高度比值, 进而快速、正确地对粘连字符进行切分,使把部分原本发生在分类阶段的计算移到训练阶段来完成。该算法可以使knn算法的效率提高80%。此外该方法还可用于 KNN 的所有变体 中, 具有 良好的推广能力 。二.对K-近邻法的具体应用。安徽大学计算机科学与技术学院的刘锋，白凡5应用了一种改进的K近邻算法进行网页分类。其针对传统K近邻算法对于噪声词敏感的缺点，结合网页文章构成的特殊性，对文档的特征向量表示模型进行了改进，从而也改进了K近邻算法中特证词的权值以及文档相似度的计算公式，实验结果表明改进后的K近邻算法提高了分类的精度。但此算法增加了网页文本的预处理时间。1.3 课题研究方法knn(k-nearest neighbor)算法是一种在线的分类方法，即分类的时候,直接从训练样本中找出与测试样本最接近的k个样本,以判断测试样本的类属。 Knn算法的可扩展性比较差，因为每判决一个测试样本，都要将其与所有训练样本比较一次，计算距离。但是knn算法对处理与训练样本类似页面的时候的精度比较高。所以在样本比较少而对分类速度要求不高的情况下，即在图像识别是有很多应用。可以使用knn分类器。同样knn分类器也可以应用在只有正例训练样本的情况下。在小规模仿真的时候使用精度较高的knn分类器，在大规模仿真和实际Web检验的时候使用knn分类器就没有有更好推广能力。可以看出，尽管近邻法有其优良品质，但是它的一个严重弱点与问题是需要存储全部训练样本，以及繁重的距离计算量。所以需要改良。1.4 论文构成及研究内容分类方法有许多，在本文我们主要讨论k-近邻分类方法在模式识别中的应用与研究。本文的第1章是绪论，说明本设计课题的来源、目的、意义、国内外研究状况、应解决的问题急应达到的技术要求。本文的第2章介绍的近邻分类器的分类原理，KNN概念，K-近邻法算法研究， K-近邻算法数学模型， K-近邻法研究方法， KNN算法需要解决的问题。其中K-近邻算法必须明确两个基本的因素：最近案例的数目K和距离的尺度。对这个问题进行了讨论，并对KNN算法做出了评价。本文的第3章介绍了分类器的概念和分类器的构造方法。本文的第4章是K-近邻法的分类器的设计与编程实现，主要包括以下几个方面的内容：开发环境的选择，K-近邻法程序实现，数据库连接，程序运行与调试及程序实现结果与分析。最后一章总结论文中的主要工作和结果。第二章 K-近邻算法的研究与分析2.1概述分类问题是数据挖掘邻域研究的一个基本的问题，给定一批具有类标记的训练实例，分类器被构造并被用于预测待分类实例的类标记.通常，一个实例 X用一个 m维的属性向量来表示，其中 xi 表示实例 X的第 i个属性值 令C表示实例的类标记，则实例 X的类标记可表示为C(x) KNN算法作为一种基本的基于实例的分类算法，由于它的有效简单高鲁棒性而被广泛的应用于数据挖掘领域来解决分类问题。近邻法是模式识别非参数法中最重要的方法之一，最初的近邻法是Cover和Hart于1968年提出的，由于该方法在理论上进行了深入分析，直至现在仍是分类方法中最重要的方法之一7。直观的理解，所谓的K近邻，就是考察和待分类样本最相似的K个样本，根据这K个样本的类别来判断待分类样本的类别值。在K近邻分类器中，一个重要的参数是K值的选择，K值选择过小，不能充分体现待分类样本的特点，而如果K值选择过大。则一些和待分类样本实际上并不相似的样本亦被包含近来，造成燥声增加而导致分类效果的降低。2.2最近邻法2.1.1最近邻法概述最近邻是将所有训练样本都作为代表点，因此在分类时需要计算待识别样本x到所有训练样本的距离，结果就是与x最近邻的训练样本所属于的类别。假定有c个类别w1，w2，wc的模式识别问题，每类有标明类被的样本Ni个，i=1,2,c。规定wi类的判别函数为gi(x)=min |x-xik|,k=1,2,Ni。其中xik的角标i表示wi类，k表示wi类Ni个样本中的第k个。决策规则可以写为：若gj(x)=min gi(x),i=1,2,c,则决策xwj。此分类示意图见图2.2所示。 B A？ A B A B A B 图2.1 近邻法分类图示2.1.2最近邻决策规则给定c 个类别 ，每类有标明类别的样本个，近邻法的判别函数为决策法则为直观的说，就是对待识别的模式向量，只要比较与所有已知类别的样本之间的欧式距离，并决策与离它最近的样本同类。 图2.2 最近邻法图示2.1.3最近邻法的错误率分析这里，设采用N个样本的最近邻法的平均错误率 ，并设则有以下的不等式成立：证明：最近邻法属于随机化决策，待分类模式X的近邻随样本集的变化而随机变化，设其最近邻为，错误的条件错误率为。对于取平均 下面我们看一下上面的两个表达式。设对于给定的，概率密度是连续的且不为零。那么，任何样本落入以为中心的一个超球 S 中的概率为N个独立的样本落在 S 外的概率为 即是，一个样本也不落在 S 内的概率为0，也就是说总有一个样本落在 S 内的概率为1。无论S多么小，这个结论也是成立的，所以。上式即是最近法错误率的计算公式2.1.4总结从上面可以看出近邻法有方法简单的优点，但也存在这一些缺点：（1）存储量和计算量都很大；（2）没有考虑决策的风险，如果决策的错误代价很大时，会产生很大的风险；（3）以上的分析渐近平均错误率，都是建立在样本数趋向无穷大的条件下得来的，在实际应用时大多是无法实现的。所以我们要引入具有拒绝决策的k近邻法 2.2 K-近邻法的概念K-近邻算法的思想如下：首先，计算新样本与训练样本之间的距离，找到距离最近的K个邻居；然后，根据这些邻居所属的类别来判定新样本的类别，如果它们都属于同一个类别，那么新样本也属于这个类；否则，对每个后选类别进行评分，按照某种规则确定新样本的类别。取未知样本X的K个近邻，看着K个近邻多数属于哪一类，就把X分为哪一类。即，在X的K个样本中，找出X的K个近邻。K-近邻算法从测试样本X开始生长，不断的扩大区域，直到包含进K个训练样本，并且把测试样本X的类别归为着最近的K个训练样本中出现频率最大的类别。例如，图3.1中K=6的情况，根据判定规则，测试样本X被归类为黑色类别。.。 .。 . . . . . 图3.1 K-近邻法近邻分类是基于眼球的懒散的学习法，即它存放所有的训练样本，并且知道新的样本需要分类时才建立分类。这与决策数和反向传播算法等形成鲜明对比，后者在接受待分类的新样本之前需要构造一个一般模型。懒散学习法在训练时比急切学习法快，但在分类时慢，因为所有的计算都推迟到那时。优点:简单，应用范围广；可以通过SQL语句实现；模型不需要预先构造。缺点:需要大量的训练数据；搜索邻居样本的计算量大，占用大量的内存；距离函数的确定比较困难；分类的结果与参数有关。2.3 K-近邻法算法研究2.3.1 K-近邻法的数学模型用最近邻方法进行预测的理由是基于假设：近邻的对象具有类似的预测值。最近邻算法的基本思想是在多维空间Rn 中找到与未知样本最近邻的k 个点，并根据这k个点的类别来判断未知样本的类。这k个点就是未知样本的k-最近邻。算法假设所有的实例对应于n 维空间中的点。一个实例的最近邻是根据标准欧氏距离定义，设x的特征向量为：其中，ar(x)表示实例x的第r个属性值。两个实例xi和xj间的距离定义为d(xi，xj)，其中：d(xi，xj)=在最近邻学习中，离散目标分类函数为f：Rn-V 其中V是有限集合v1，v2，vs，即各不同分类集。最近邻数k值的选取根据每类样本中的数目和分散程度进行的，对不同的应用可以选取不同的k值。如果未知样本si的周围的样本点的个数较少，那么该k个点所覆盖的区域将会很大，反之则小。因此最近邻算法易受噪声数据的影响，尤其是样本空间中的孤立点的影响。其根源在于基本的k-最近邻算法中，待预测样本的k个最近邻样本的地位是平等的。在自然社会中，通常一个对象受其近邻的影响是不同的，通常是距离越近的对象对其影响越大9。2.3.2 K-近邻法研究方法该算法没有学习的过程，在分类时通过类别已知的样本对新样本的类别进行预测，因此属于基于实例的推理方法。如果取K等于1，待分样本的类别就是最近邻居的类别，称为NN算法。只要训练样本足够多，NN算法就能达到很好的分类效果。当训练样本数趋近于-时，NN算法的分类误差最差是最优贝叶斯误差的两倍；另外，当K趋近于时,KNN算法的分类误差收敛于最优贝叶斯误差。下面对K-近邻算法描述：输入：训练数据集D=(Xi,Yi),1iN，其中Xi是第i个样本的条件属性，Yi是类别,新样本X，距离函数d。输出:X的类别Y。for i=1 to N do 计算X和Xi之间的距离d(Xi,X)；end for对距离排序，得到d(X,Xi1) d(X,Xi2) d(X,XiN)；选择前K个样本：S=(Xi1,Yi1)(XiK,YiK)；统计S中每个类别出现的次数，确定X的类别Y 。2.3.3 K-近邻法需要解决的问题(1) 寻找适当的训练数据集训练数据集应该是对历史数据的一个很好的覆盖，这样才能保证最近邻有利于预测，选择训练数据集的原则是使各类样本的数量大体一致，另外，选取的历史数据要有代表性。常用的方法是按照类别把历史数据分组，然后再每组中选取一些有代表性的样本组成训练集。这样既降低了训练集的大小，由保持了较高的准确度。(2) 确定距离函数距离函数决定了哪些样本是待分类本的K个最近邻居，它的选取取决于实际的数据和决策问题。如果样本是空间中点，最常用的是欧几里德距离。其它常用的距离函是由绝对距离、平方差和标准差。(3) 决定K的取值邻居的个数对分类的结果有一定的影响，一般先确定一个初始值，再进行调整，直到找到合适的值为止。(4) 综合K个邻居的类别多数法是最简单的一种综合方法，从邻居中选择一个出现频率最高的类别作为最后的结果，如果频率最高的类别不止一个，就选择最近邻居的类别。权重法是较复杂的一种方法，对K个最近邻居设置权重，距离越大，权重就越小。在统计类别时，计算每个类别的权重和，最大的那个就是新样本的类别9。2.4小结在KNN算法里对于模型的选择，尤其是k值和距离的尺度，往往是通过对大量独立的测试数据，多个模型来验证最佳的选择。下面是一些被提及的处理KNN的方法：k一般是事先确定，如10，也可以使用动态k值；使用固定的距离指标，这样只对小于该指标的案例进行统计。对于样本的维护，也并不是简单的增加新样本。也可以采取适当的办法来保证空间的大小，如符合某种条件的样本可以加入库里，同时可以对库里已有符合某种条件的样本进行删除等。此外，为考虑提高性能，可以把所有的数据放在内存中，如MBR通常指保存在内存中的K近邻算法。K-近邻算法是一种预测性的分类算法(有监督学习)。它实际并不需要产生额外的数据来描述规则，它的规则本身就是数据(样本)。KNN属于机器学习的基于样本的学习。它区别于归纳学习的主要特点是直接用已有的样本来解决问题，而不是通过规则推导来解决问题。它并不要求数据的一致性问题，即可以通过噪音，并且对样本的修改是局部的，不需要重新组织。K-近邻算法综合与未知样本最近的K 个近邻样本的类别来预测未知样本的类别，而在选择样本时根据一定的距离公式计算与未知样本的距离来确定是否被选择。其优点是方法简单，算法稳定。缺点是需要大量样本才能保证数据的精度，此外，更主要的是它需要计算大量的样本间的距离，导致使用上的不便。对于每个新的样本都要遍历一次全体数据，KNN计算量要比Bayes和决策树大。对时间和空间的复杂性是必须考虑的。KNN常用在较少数据预测时使用8。第三章 分类器概述3.1 分类器的概念分类器的定义：输入的数据含有千万个记录，每个记录又有很多个属性，其中有一个特别的属性叫做类（例如信用程度的高，中，低）。分类器的目的就是分析输入的数据，并建立一个模型，并用这个模型对未来的数据进行分类，数据分类技术在信用卡审批、目标市场定位、医疗诊断、故障检测、有效性分析、图形处理及保险欺诈分析等领域,都可以看到分类器广泛应用。分类是一种典型的有监督的机器学习方法3,其目的是从一组已知类别的数据中发现分类模型,以预测新数据的未知类别。用于分类的数据是一组已知类别的样本，每个样本包含一组相同的属性。根据在分类中的作用，属性可以分为条件属性和目标属性两种。这样，一个样本就可以表示为(X1，X2，.Xm，Y)的形式，其中，Xi是条件属性，Y是目标属性。分类的目的就是发现X1,X2,Xm和Y之间的依赖关系，这种依赖关系又称为分类模型或者分类器。可以认为，分类器就是一个函数，它的输入是未知类别的样本，输出是样本的类别。3.2 分类器的构造方法分类的方法不同，模型的表示形式就不同。利用决策树方法构造的分类模型就可能表示为树状结构或者分类规则，神经网络的分类模型则可表示为由单元和系数构成的网络模型，而贝叶斯分类的模型则表现为数学公式。图3.1描述了分类的三个步骤。数据训练集测试集分类模型类别测试后的分类模型新数据 模型构造 模型测试 模型应用图3.1 分类的三个步骤一个完整的分类过程一般包括模型构造，模型测试和模型应用这三步4。具体地说，每个步骤的功能如下：(1)模型构造分析样本的类别和其具备的一些特征之间的依赖关系，并将这种关系用特定的模型表示出来。例如，分析以往的病历，根据病人的症状和诊断结果，得到疾病诊断模型。用来构造模型的数据集称为训练数据集或者训练样本集，即训练集。(2)模型测试检测模型的准确度,最终得到描述每个类别的分类模型。用来评价模型的数据集称为测试数据集或者测试样本集,简称测试集。测试的过程是对测试数据依次检测，根据模型确定样本的类别，然后与实际类别相比较,如果相同,则称预测结果是正确的，否则说明预测结果是错误的。模型的准确度定义为测试集中结果正确的样本的比例。(3)模型应用利用得到的分类模型，预测在未知的情况下样本所属的类别。这个过程与模型评价基本相同，只是输入数据的类别是未知的。3.3 小结人脸识别的研究始于60年代末，bledsoe以人脸特征点的间距、比率等参数为特征，建成了一个半自动的人脸识别系统。早期的人脸识别方法通常是以人脸器官位置、尺度作为描述人脸的特征。到了20世纪90年代人脸识别技术进一步发展。而基于人脸图像整体特征识别方法，取得了比较好的识别性能。提取有效的特征之后，识别的关键在于设计具有良好分类能力的分类器。通常线性分类器速度较快，而且实现方便，准确率也不错。而K-近邻分类器，由于其方便实用的特点，是目前图像识别领域比较流行的方法。第四章 K-近邻法的分类器的设计与编程实现4.1 开发环境的选择Matlab是当今世界上使用最为广泛的数学软件，它具有相当强大的数值计算、数据处理、系统分析、图形显示，甚至符号运算功能，是一个完整的数学平台，在这个平台上，你只需寥寥数语就可以完成十分复杂的功能，大大提高了工程分析计算的效率。另外由于Matlab的广泛使用，于是出现了为各个领域专门使用的工具箱(即在某一研究领域常用数学工具的函数包)，这些工具箱的出现更加促进了Matlab的流行。但Matlab强大的功能只能在它所提供的平台上才能使用，也就是说，你必需在安装有matlab系统的机器上使用.m文件，这样就给工程计算带来了很大不便；特别是，在matlab中，使用的行解释方式执行代码，这样大大地限制了代码执行速度。而Microsoft.NET使编程工作变得更加容易，开发投资的回报率趋于最大化。 Microsoft.NET减少了程序员要写的代码量。另外，将显示特性与.NET体验分开以便以后加入新的接口技术，比如语音或手写识别，而不必去重写程序。 Microsoft.NET 开创了全新的商业模型，它使得一个公司可以用多种方法来把自己的技术商品化。 Microsoft.NET 对“用户界面友好”作了重新定义。终端用户能够享受一个智能化的、个性化的Internet，它能记住用户的个人设置，并在适当的时候，向用户使用的智能设备上发送适当的数据10。C#是微软公司发布的一种面向对象的、运行于.NET Framework之上的高级程序设计语言。C#独有的特点：(1)中间代码：微软在用户选择何时MSIL应该编译成机器码的时候是留了很大的余地。微软公司很小心的声称MSIL不是解释性的,而是被编译成了机器码。(2)命名空间中的申明：当你创建一个程序的时候，你在一个命名空间里创建了一个或多个类。同在这个命名空间里(在类的外面)你还有可能声明界面，枚举类型和结构体。必须使用using关键字来引用其他命名空间的内容。(3)基本的数据类型：C#拥有比C，C+或者Java更广泛的数据类型。这些类型是bool， byte， ubyte，short， ushort， int， uint，long， ulong， float，double和decimal。象Java一样，所有这些类型都有一个固定的大小。又象C和C+一样,每个数据类型都有有符号和无符号两种类型。与Java相同的是，一个字符变量包含的是一个16位的Unicode字符。C#新的数据类型是decimal数据类型，对于货币数据，它能存放28位10进制数字。(4)两个基本类：一个名叫object的类是所有其他类的基类。而一个名叫string的类也象object一样是这个语言的一部分。作为语言的一部分存在意味着编译器有可能使用它-无论何时你在程序中写入一句带引号的字符串，编译器会创建一个string对象来保存它。(5)参数传递：方法可以被声明接受可变数目的参数。缺省的参数传递方法是对基本数据类型进行值传递。ref关键字可以用来强迫一个变量通过引用传递，这使得一个变量可以接受一个返回值。out关键字也能声明引用传递过程，与ref不同的地方是，它指明这个参数并不需要初始值。(6)与COM的集成：C#对Windows程序最大的特点就是它与COM的无缝集成了，COM就是微软的Win32组件技术。实际上，最终有可能在任何.NET语言里编写COM客户和服务器端。C#编写的类可以子类化一个以存在的COM组件；生成的类也能被作为一个COM组件使用，然后又能使用。所以决定取其两者优点当研究学习时使用matlab作为工具而使用c#.net作为开发应用开发工具。4.2 对k近邻算法的程序的探究由前面的分析可知，需要对K-近邻算法程序的实现和分类程序包括测试数据集的实现。而K-近邻法实际应用效果好，但又因算法问题而使其计算量大，时间代价高；由于训练数据常驻内存，会占用大量的内存，增加成本。所以我们先对传统的k-近邻算法与改进的k-近邻算法进行探究。对于传统k-近邻算法用matlab进行编程其代码如下function result = knnclassification(testsamplesX,samplesX, samplesY, Knn,type)% Classify using the Nearest neighbor algorithm% Inputs:% samplesX - Train samples%samplesY - Train labels% testsamplesX - Test samples%Knn - Number of nearest neighbors % Outputs%result- Predicted targetsif nargin 5 type = 2norm;endL= length(samplesY);%erroe?,length(samplesY),no ,for X,Ys 1dim is equalUc = unique(samplesY);%类别数目if (L Knn), error(You specified more neighbors than there are points.)endN = size(testsamplesX, 1);result = zeros(N,1); switch typecase 2norm for i = 1:N, dist = sum(samplesX - ones(L,1)*testsamplesX(i,:).2,2); m, indices = sort(dist);%SORT(X) sorts the elements of X in ascending order n = hist(samplesY(indices(1:Knn), Uc);%ji suan jie jin na yi lei m, best = max(n); result(i) = Uc(best); endcase 1norm for i = 1:N, dist = sum(abs(samplesX - ones(L,1)*testsamplesX(i,:),2); m, indices = sort(dist); n = hist(samplesY(indices(1:Knn), Uc); m, best = max(n); result(i) = Uc(best); endcase match for i = 1:N, dist = sum(samplesX = ones(L,1)*testsamplesX(i,:),2); m, indices = sort(dist); n = hist(samplesY(indices(1:Knn), Uc); m, best = max(n); result(i) = Uc(best); endotherwise error(Unknown measure function);end测试数据集使用安德森鸢尾花卉数据集，下面简要介绍一下其数据集。安德森鸢尾花卉数据集（英文：Andersons Iris data set），也称鸢尾花卉数据集（英文：Iris flower data set）或费雪鸢尾花卉数据集（英文：Fishers Iris data set），是一类多重变量分析的数据集。它最初是埃德加安德森（Edgar Anderson）从加拿大加斯帕半岛（Gasp Peninsula）上的鸢尾属花朵中提取的地理变异数据11，后由罗纳德费雪（Sir Ronald Aylmer Fisher）作为判别分析的一个例子12，运用到统计学中。其数据集包含了50个样本，都属于鸢尾属下的三个亚属，分别是山鸢尾（Iris setosa）、变色鸢尾（Iris versicolor）和维吉尼亚鸢尾（Iris virginica）。四个特征被用作样本的定量分析，它们分别是花萼和花瓣的长度和宽度。基于这四个特征的集合，费雪发展了一个线性判别分析以确定其属种。我们使用这150个数据集作为测试样本，在其中随机选择75个作为训练样本。对类另外75个使用k-近邻进行识别结果如下：类别第一类第二类第三类错误数043识别率100%84%88%总识别率90.6%下面选取一种改良的k-近邻算法进行研究，选取的是辽宁工程技术大学的张宇提出的一种k-近邻改进算法其主要算法思想如下3： 由于k- 最近邻分类器认为每个属性的作用都是相同的(赋予相同权值) , 这样在属性集包含有许多不相关属性时,就会误导分类过程。 针对此问题可以采用组合分类器的方法。 组合分类器的方法有很多,其中包括投票法,非投票法,动态法和静态法等等。这里我们采用投票法。投票法起源于贝叶斯学习理论。贝叶斯学习理论规定为了取得最大的预测精度, 在假设空间使用所有可容许的方法而不是只使用一种学习方法, 对每种方法利用投票法给出权重。在机器学习领域提出了一些基于Voting 方法的算法,如uniform vot ing 法,就是所有的基分类器对最后的分类有同样的权值。另外一个这样的方法是weightedvoting 法, 每一个基分类器有一个相关的权重。 该权重可以随时间变化。 利用简单投票( uniform voting 法) , 通过随机属性子集组合多个k-近邻分类器进行分类过程中, 虽然单个分类模型有独立的错误,但整体错误会会随着分类器数目的增加单调减少。k-近邻改进算法的思想:随机选择属性子集,构建多个k-近邻分类器,然后对未分类元组进行分类,最后将分类器的分类结果按照简单投票法进行组合, 得票最多的分类器的结果则成为最终组合近邻分类器的输出。我们使用matlab对其算法思想进行实现， 对鸢尾花数据集中的4个属性随机分成3个子属性集每个子属性集包含3个属性，分别进行k-近邻分类，并从结果中选出识别票数最多的作为结果。其第一次分类结果如下：类别第一类第二类第三类错误数033识别率100%88%88%总识别率92%和传统的k-近邻算法相比其识别正确率有了提高，但是由于其算法随机选取子集以排除相关性弱的属性影响但其因为其随机性使识别率提高并不稳定。下表是第二次试验结果：类别第一类第二类第三类错误数023识别率100%92%88%总识别率93.3%可以看出当其所划分子集越多，其准确率越高，但其为了正确率加大了计算量，并没有解决需要大量的已经准备好的历史数据；在对一个新样本分类时，要搜索所有的训练样本来寻找最近的邻居，计算量大，时间代价高；由于训练数据常驻内存，会占用大量的内存；且分类结果与参数有关的缺点。4.3 对k近邻算法的程序的应用设计4.3.1应用设计人脸识别系统以人脸识别技术为核心，而本论文要利用k-近邻算法作为识别算法，做出人脸识别系统。 （1）人脸识别系统研究背景自70年代以来.随着人工智能技术的兴起.以及人类视觉研究的进展.人们逐渐对人脸图像的机器识别投入很大的热情，并形成了一个人脸图像识别研究领域，.这一领域除了它的重大理论价值外，也极具实用价值。进行人脸图像识别研究也具有很大的使用价依。如同人的指纹一样，人脸也具有唯一性，也可用来鉴别一个人的身份。现在己有实用的计算机自动指纹识别系统面世，并在安检等部门得到应用，但还没有通用成熟的人脸自动识别系统出现。人脸图像的自动识别系统较之指纹识别系统、DNA鉴定等更具方便性，因为它取样方便，可以不接触目标就进行识别，从而开发研究的实际意义更大。并且与指纹图像不同的是，人脸图像受很多因素的干扰:人脸表情的多样性;以及外在的成像过程中的光照，图像尺寸，旋转，姿势变化等。使得同一个人，在不同的环境下拍摄所得到的人脸图像不同，有时更会有很大的差别，给识别带来很大难度。因此在各种干扰条件下实现人脸图像的识别，也就更具有挑战性。国外对于人脸图像识别的研究较早，现己有实用系统面世，只是对于成像条件要求较苛刻，应用范围也就较窄，国内也有许多科研机构从事这方而的研究，并己取得许多成果。（2）人脸图像识别的应用前景及意义人脸图像识别除了具有重大的理论价值以及极富挑战性外，还其有许多潜在的应用前景，利用人脸图像来进行身份验证，可以不与目标相接触就取得样本图像，而其它的身份验证手段，如指纹、眼睛虹膜等必须通过与目标接触或相当接近来取得样木，在某些场合，这些识别手段就会有不便之处。就从目前和将来来看，可以预测到人脸图像识别将具有广阔的应用前景，如表1-1中所列举就是其中已经实现或逐步完善的应用。应用优点存在问题信信用卡、汽车驾照、护照以及个人身份验证等图像摄取可控图像分割可控图像质量好需要建立庞大的数据库嫌疑犯照片匹配图像质量不统一多幅图像可用潜在的巨大图像库互联网应用视频信息价值高多人参与存在虚假银行/储蓄安全监控效果好图像分割不可控图像质量较差人群监测图像质量高可利用摄像图像图像分割自由图像质量低、实时性表4-1 人脸识别的应用4.3.2人脸识别系统设计方案首先先读取图像，将图像转化成灰度图像，然后再将图像转化成二值图像，对其进行栅格化，从而读出图像的人脸部分。而后对其进行特征提取，形成数据集，而后使用k-近邻算法进行分类。其主要流程如下：图像加载图像处理图像识别训练样本加载测试样本加载训练样本处理测试样本处理识别结果 图4.1人脸识别系统设计方案4.3.3人脸识别系统实现具体方案（1）打开图像一般来说，图像的获取都是通过摄像头摄取，但摄取的图像可以是真人，也可以是人脸的图片或者为了相对简单，可以不考虑通过摄像头来摄取头像，而是直接给定要识别的图像。使用一个pictureBox，一个button和一个openFileDialog，代码如下： private void button1_Click(object sender, EventArgs e) if (this.openFileDialog1.ShowDialog() != DialogResult.OK) return; try Image img = Image.FromFile(this.openFileDialog1.FileName); this.pictureBox1.Image = img; this.BackgroundImage = img; catch (System.Exception ex) MessageBox.Show(载入图像失败！); （1） 处理图像将图像转化成灰度图像，然后再将图像转化成二值图像，对其进行栅格化，从而读出图像的人脸部分。而后对其进行特征提取，形成数据集。其主要代码如下:openFileDialognamespace Nobugz static class Util public static Bitmap BitmapTo1Bpp(Bitmap img) int w = img.Width; int h = img.Height; Bitmap bmp = new Bitmap(w, h, PixelFormat.Format1bppIndexed); BitmapData data = bmp.LockBits(new Rectangle(0, 0, w, h), ImageLockMode.ReadWrite, PixelFormat.Format1bppIndexed); for (int y = 0; y h; y+) byte scan = new byte(w + 7) / 8; for (int x = 0; x = 0.5) scanx / 8 |= (byte)(0x80 (x % 8); Marshal.Copy(scan, 0, (IntPtr)(int)data.Scan0 + data.Stride * y), scan.Length); return bmp; （2）识别图像使用k-近邻算法对数据集进行计算识别输出结果。其主要代码如下：/ K-近邻法的实现/ 设定不同的 k 值，给每个测试样例予以一个类型/ 距离和权重成反比void knnProcess(vector& test, const vector& train, const vectorvector & dm, unsigned int k)for (vector:size_type i = 0; i != test.size(); +i)multimap dts;for (vector:size_ty