基于K近邻的分类算法研究

沈阳航空航天大学ShenyangAerospaceUniversity算法分析题目：基于K-近邻分类算法的研究院系计算机学院专业计算机技术姓名学号指导教师1月摘要数据挖掘是机器学习领域内广泛研究的知识领域,是将人工智能技术和数据库技术紧密结合，让计算机协助人们从庞大的数据中智能地、自动地提取出有价值的知识模式，以满足人们不同应用的需要。K近邻算法（KNN)是基于统计的分类办法，是数据挖掘分类算法中比较惯用的一种办法.该算法含有直观、无需先验统计知识、无师学习等特点，现在已经成为数据挖掘技术的理论和应用研究办法之一。本文重要研究了K近邻分类算法。首先简要地介绍了数据挖掘中的多个分类算法，具体地叙述了K近邻算法的基本原理和应用领域，另首先指出了K近邻算法的计算速度慢、分类精确度不高的因素，提出了两种新的改善办法.针对K近邻算法的计算量大的缺点，构建了聚类算法与K近邻算法相结合的一种办法。将聚类中的K-均值和分类中的K近邻算法有机结合.有效地提高了分类算法的速度。针对分类精确度的问题，提出了一种新的距离权重设定办法。传统的KNN算法普通采用欧式距离公式度量两样本间的距离。由于在实际样本数据集合中每一种属性对样本的奉献作用是不尽相似的,普通采用加权欧式距离公式。本文提出一种新的计算权重的办法。实验表明，本文提出的算法有效地提高了分类精确度.最后，在总结全文的基础上，指出了有待进一步研究的方向。核心词：K近邻，聚类算法，权重,复杂度，精确度ABSTRACTDataminingisawidelyfieldofmachinelearning，anditintegratestheartificialintelligencetechnologyanddatabasetechnology.Ithelpspeopleextractvaluableknowledgefromalargedataintelligentlyandautomaticallytomeetdifferentpeopleapplications.KNNisausedmethodindataminingbasedonStatistic。Thealgorithmhasbecomeoneofthewaysindataminingtheoryandapplicationbecauseofintuitive,withoutprioristatisticalknowledge,andnostudyfeatures。Themainworksofthisthesisisknearestneighborclassificationalgorithm.First，itintroducesmainlyclassificationalgorithmsofdatamininganddescriptstheoreticalbaseandapplication。Thispaperpointsoutthereasonsofslowandlowaccuracyandproposestwoimprovedways.InordertoovercomethedisadvantagesoftraditionalKNN,thispaperusetwoalgorithmsofclassificationandclusteringtoproposeanimprovedKNNclassificationalgorithm.Experimentsshowthatthisalgorithmcanspeedupwhenithasafeweffectsinaccuracy。Accordingtotheproblemofclassificationaccuracy,thepaperproposesanewcalculationofweight.KNNthetraditionalmethodgenerallyusedContinentaldistanceformulameasurethedistancebetweenthetwosamples。Astheactualsampledatacollectionineveryattributeofasampleofthecontributionisnotthesame，oftenusingtheweightedContinentaldistanceformula.Thispaperpresentsacalculationofweight,thatisweightedbasedonthecharacteristicsofKNNalgorithm.AccordingtothisExperimentsonartificialdatasetsshowthatthisalgorithmcanimprovetheaccuracyofclassification.Last，thepaperindicatesthedirectionofresearchinfuturebasedonthefull—text。Keywords：KNearestNeighbor,ClusteringAlgorithm,FeatureWeighted，ComplexDegree,ClassificationAccuracy。前言K近来邻(k-Nearest

\o"neighbor"neighbor，HYPERLINK”/sowiki/KNN?prd=content_doc_search"\o"KNN”KNN)分类算法，是一种理论上比较成熟的办法，也是最简朴的机器学习算法之一.该办法的思路是：如果一种样本在特性空间中的k个最相似(即特性空间中最邻近）的样本中的大多数属于某一种类别，则该样本也属于这个类别。KNN算法中,所选择的邻居都是已经对的分类的对象。该办法在定类决策上只根据最邻近的一种或者几个样本的类别来决定待分样本所属的类别。KNN办法即使从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN办法重要靠周边有限的邻近的样本，而不是靠鉴别类域的办法来拟定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说，KNN办法较其它办法更为适合.KNN算法不仅能够用于分类，还能够用于回归.通过找出一种样本的k个近来邻居，将这些邻居的属性的平均值赋给该样本,就能够得到该样本的属性。更有用的办法是将不同距离的邻居对该样本产生的影响予以不同的权值（weight),如权值与距离成正比。该算法在分类时有个重要的局限性是，当样本不平衡时，如一种类的样本容量很大，而其它类样本容量很小时，有可能造成当输入一种新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“近来的"邻居样本，某一类的样本数量很大，那么或者这类样本并不靠近目的样本,或者这类样本很靠近目的样本。无论如何，数量并不能影响运行成果。能够采用权值的办法（和该样本距离小的邻HYPERLINK”±…权？prd=content_doc_search”\o"居权”居权值大）来改善.

该办法的另一种局限性之处是计算量较大，由于对每一种待分类的文本都要计算它到全体已知样本的距离，才干求得它的K个近来邻点。现在惯用的解决办法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较合用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分目录TOC\o"1—3"\h\z\u摘要 IABSTRACT I前言 III1绪论 11.1选题背景和研究现状 11。1。1数据挖掘 11.1。2国内外研究现状 21.2研究内容和目的 31。2。1研究内容 31.2.2研究目的 52 K—近邻分类算法 52.1分类算法 52.1。1数据分类 52.1。2分类办法 82。2基于实例的学习算法 102.3K-近邻办法 102.3。1近来邻分类算法介绍 102。3。2K—近邻算法实现 112。4算法分析 122。4。1算法实现 122。4。2算法的优缺点 132。4.3KNN的改善 143 算法应用 163.1k—近邻算法在肝癌检测中的应用 163.2面对延迟敏感性应用 173。3改善的K—近邻算法在中文网页分类的应用 17总结 18致谢 18参考文献 191绪论1.1选题背景和研究现状1。1。1数据挖掘随着数据库技术的飞速发展,人工智能领域的一种分支——机器学习的研究自20世纪50年代开始以来也获得了很大进展.用数据库管理系统来存储数据，用机器学习的办法来分析数据，挖掘大量数据背后的知识，这两者的结合促成了数据库中的知识发现（KnowledgeDiscoveryinDatabases,简记KDD）的产生，也称作数据挖掘（DataMing，简记DM)。数据挖掘是信息技术自然演化的成果.信息技术的发展大致能够描述为以下的过程：早期的是简朴的数据收集和数据库的构造；后来发展到对数据的管理,涉及：数据存储、检索以及数据库事务解决；再后来发展到对数据的分析和理解，这时候出现了数据仓库技术和数据挖掘技术。数据挖掘是涉及数据库和人工智能等学科的一门现在相称活跃的研究领域。数据挖掘是机器学习领域内广泛研究的知识领域，是将人工智能技术和数据库技术紧密结合，让计算机协助人们从庞大的数据中智能地、自动地抽取出有价值的知识模式，以满足人们不同应用的需要[1］。现在，数据挖掘已经成为一种含有迫切实现需要的很有前途的热点研究课题.数据挖掘技术能从数据仓库中自动分析数据，进行归纳性推理，从中发掘出潜在的模式,或产生联想，建立新的业务模型，这是一种高级的解决过程。高级的解决过程是指一种多环节的解决过程，多环节之间互相影响、重复调节，形成一种螺旋式上升过程。数据挖掘的功效用于指定数据挖掘任务中要找的模式类型,其任务普通分为两类：描述和预测。描述性挖掘任务刻画数据库中数据的普通特性,预测性挖掘任务在现在数据上进行推断，以进行预测.在实际应用中，往往根据模式的实际应用细分为下列六种：①分类模式；②回归模式；③时间序列模式；④聚类模式;⑤关联模式；⑥序列模式。在解决实际问题时,经常要同时使用多个模式。分类模式和回归模式是使用最普遍的模式。分类模式、回归模式、时间序列模式也被认为是受监督的知识,由于在建立模式前数据的成果是已知的，能够直接用来检测模式的精确性，模式的产生是在受监督的状况下进行的。普通在建立这些模式时,使用一部分数据作为样本,用另一部分数据来检查、校正模式.聚类模式、关联模式、序列模式则是非监督知识，由于在模式建立前模式是未知的，模式的产生不受任何监[2]。1.1。2国内外研究现状本论文重要研究的是数据挖掘分类算法中的K近邻算法.国内外学者针对此算法做了许多研究工作。例如文献[3]研究了计算复杂性的优化和分析办法以及如何减少计算量的做法等。香港中文大学的WaiLam等人KNN办法和线性分类器结合，获得了较好的分类效果,在召回率靠近90%时精确率超出80%[4］。WlodzislawDuch提出了通过选用特性对加权KNN算法的研究[5］。文献[4]提出了一种基于近邻搜索的快速K近邻分类算法——超球搜索法。该办法通过对特性空间的预组织,使分类能在以待分样本为中心的超球内进行。超球半径由零开始逐步增大至超球内包含K个以上模式样本为止。这一办法有效地缩小了算法搜索范畴，同时预组织和预分类简朴明了，无需复杂的训练，不存在收敛性问题。文献［8］研究了回归函数K—近邻预计的渐进性质，得到了回归函数的K—近邻预计的渐进正态性和它的Bootstrap统计量的相合性。文献［5]为近邻算法建立一种有效的搜索树,提高了查询速率。文献[6］提出了一种迭代近邻法，用以解决KNN算法在小样本库的环境下分类效果不佳的问题，在无法得到足够的定类样本时，通过检索的办法将待分样本的局部主题特性放大，进而得到足够定类的相似样本。文献［7]分析了传统的近邻文本分类办法技术以及Web文本的特点，充足运用了Web文本的构造信息进行特性词加权，以类轴向量为核心构建分类器。文献［8］提出了加权K近邻的办法，对训练集X内的每一种样本点，给定一种临界半径，对一种待识别样本，比较其与训练集中每个样本点的加权距离。文献［9］针对欧几里德空间的K近邻，给出了在可重构网孔机器上（RMESH)的并行算法等.1.2研究内容和目的1。2。1研究内容近邻办法是在一组历史数据统计中寻找一种或者若干个与现在统计最相似的历史纪录的已知特性值来预测现在统计的未知或遗失特性值［9］。近邻办法是数据挖掘分类算法中比较惯用的一种办法.K近邻算法(简称KNN）是基于统计的分类办法[15].KNN分类算法根据待识样本在特性空间中K个近来邻样本中的多数样本的类别来进行分类，因此含有直观、无需先验统计知识、无师学习等特点，从而成为非参数分类的一种重要办法.大多数分类办法是基于向量空间模型的。现在在分类办法中，对任意两个向量：x=（x1,x2,…，xn）与x'=(x1’，x2’，…xn'）存在3种最通用的距离度量：欧氏距离、余弦［16］和内积［17］。有两种惯用的分类方略:一种是计算待分类向量到全部训练集中的向量间的距离：如K近邻选择K个距离最小的向量然后进行综合，以决定其类别。另一种是用训练集中的向量构成类别向量，仅计算待分类向量到全部3类别向量的距离，选择一种距离最小的类别向量决定类别的归属.很明显，距离计算在分类中起核心作用.由于以上3种距离度量不涉及向量的特性之间的关系，这使得距离的计算不精确,从而影响分类的效果.下面分3种状况阐明:①无用特性的影响：在分类算法的向量空间模型中，向量经常是多维的。所谓无用特性是指与类别无关的特性。也就是各个类别中均能够出现的特性，它不代表类别的特点，必须要进行删除,否则他们将会造成距离的计算不精确，即向量间的距离远近将被无关特性的出现所影响。②特性间关系的影响：我们认为如果不考虑特性间的关系，距离的计算同样会存在问题.例如在文本分类中，可分两种状况阐明：一种是同义词的影响，另一种是含有某种语义关联词的影响。③特性间地位不平等性的影响：特性对类别支持作用大小尽管可用权值大小来体现，但我们觉得还不够。存在某些特性对类别含有较强的支持作用（决策特性），它们的存在能够在很大程度上决定类别的归属。而在向量空间模型中，这种决策作用将被众多非决策特性的影响所沉没掉。另首先对于K近邻算法中,选用不同的K值对分类成果有较大的影响,也就是说，不同的K值直接决定分类成果的对的率。如图1.1所示:图1。1K值对分类的影响其中含有空心方格和实心圆圈两类数据，待测数据点（问号代表）如果采用1近邻则其所属类别应当是如图所示的属于方格类,如果采用3近邻则属于圆圈类.因此说，采用如何的K近邻个数是分类成果对的与否的核心条件之一.最后查找近邻的效率问题也是值得研究的一项内容。K近邻分类算法需要进行全局搜索，计算的时间复杂度大，速度慢.当训练集数据量非常大时，寻找近邻就需要对应的提高效率算法，使得查找速度提高.像在文中1.1.2中所述的,现在已有的某些快速K近邻分类算法，尽管在提高快速性方面作了某些改善,但是有的需要事先进行大量复杂的训练并且存在着收敛性问题，有的同样需要进行全局搜索并且对搜索次序有较强的敏感性。分类算法中，KNN算法是实现简朴、分类效果较好的一种办法。1.2.2研究目的本论文重要针对KNN算法的计算速度慢，精确度不高的缺点进行改善,提出一种能在保持精确度的前提下减少搜索范畴、有效提高算法速度的改善办法.即使许多学者都在这两个方面做了大量的研究，但还存在着某些值得研究的问题。针对KNN算法计算量大的缺点，现在提出较多的快速算法重要有分块Voronoi图办法，但是速度的改善均不是很大。本文运用分块的方略，提出一种KNN与聚类算法相结合的改善算法，使得能够在对精确度影响不大的前提下提高算法的收敛速度。另首先针对分类精确度的问题，构造新的相似性度量或特性权重型的距离度量，以达成提高分类的精确度的目的。最后能够尝试有关特性选择方面的研究，以达成能同时提高速度和精确度。以上三个方面在新的算法提出之后能够通过实例验证算法的可行性并与常规分类算法进行比较，以验证算法的优越性。2 K—近邻分类算法2.1分类算法2.1。1数据分类分类模式挖掘技术作为数据挖掘的重要分支将对电信、银行、保险、零售、医疗等诸多行业提供决策支持，对将来商业和人们的生活也将产生深远的影响。数据分类（DataClassification）是数据挖掘中一项非常重要的任务，现在在商业上应用最多.分类的目的是学会一种分类函数或者分类模型（也经常称为分类器)，该模型能把数据库中的数据项映射到给定类别中的某一种。例如:能够建立一种分类模型，对银行贷款的安全或风险进行分类。许多分类的办法已被机器学习、专家系统、统计学和神经生物学方面的研究者提出.数据分类事实上就是从数据库对象中发现共性,并将数据对象分成不同类别的一种过程，可分成两步进行（图2.1）。第一步,建立一种模型，描述预定的数据类集或概念集.通过分析由属性描述的数据元组来构造模型。假定每个元组属于一种预定义的类，有一种类标号属性(ClassLabelAttribute）的属性拟定。对于分类，数据元组也称为样本、实例或者对象。为建立模型而被分析的数据元组形成训练数据集（TrainingSet）。训练数据集中的单个元组称为训练样本,并随机的从样本集中选用。由于预先懂得每个训练样本的类标号,这个建立模型的学习过程属于有指导的学习，即模型的学习是在懂得每个训练样本属于哪个类的指导下进行的。这不同于无指导的学习（如聚类）,无指导的学习中每个训练样本的类标号事先是未知的，要学习的类集合或者数量也是事先不懂得,整个学习的过程是在无指导的状况下进行的。普通，通过第一步的学习建立的模型用分类规则、决策树或数据公式的形式表达。如给定一种顾客信用信息的数据库，通过分类算法学习得出分类规则，根据这些规则，决定顾客的信誉好坏.即这些规则就是分类模型,能够运用这个模型对其它数据样本进行分类,同时也能对数据库的内容提供更加好的理解.图2.1（a）表达一种学习过程：在训练数据上用分类算法学习，学习模型用分类规则的形式表达。图2.1（a)学习过程测试数据分类规则新数据图2。1(b）分类过程第二步图2.1（b）表达一种分类过程：在测试数据上评定分类规则的精确率，如果精确率能够接受,则分类规则可用于新的数据的分类。首先要评定模型的预测精确率。最惯用的一种办法是保持（HoldOut）办法,该办法使用类标号样本测试集，这些样本随机选用，并独立于训练样本集，即测试样本集完全不同于训练样本集.模型在测试样本集上的精确率是指被模型对的分类的测试样本的比例。对于每个测试样本，按照分类模型学习得出的预测类别与已知的类别标号进行比较，如果相似，则表达分类成功；不相似，表达分类不成功。使用完全不同于训练样本集的测试样本集，是由于学习模型倾向于过分适合数据,即学习模型可能并入训练数据中某些特别的异常数据，而这些异常不出现在总体样本集中。如果仍使用训练数据评定分类模型，则可能评定总是乐观的。如果认为模型的精确率能够接受，就能够运用该模型对类标号未知的数据元组或对象进行分类。如在通过分析现有顾客数据学习得到的分类规则能够预测新的顾客信誉的好坏。分类算法含有广泛的应用,涉及信誉证明、学习顾客爱好、性能预测、市场调查［21］、新闻分发[22］、邮件分类以及医疗诊疗等.2.1。2分类办法现在，有多个分类办法和算法，重要有统计办法、机器学习办法、神经网络办法等。分类算法普通分为Lazy和Eager两种类型。Lazy学习算法思想是从局部出发，推迟对训练例子的归纳过程，直到一种新的测试例子出现，例如K近邻（KNearestNeighbor）算法、局部加权回归（LocallyWeightedRegression）、基于案例的推理（Case—basedReasoning)等；而Eager学习算法则是从全局出发，在新的测试例子出现之前，由训练例子总结归纳出相似判断的目的函数，这个目的函数应用于训练数据和测试数据，例如决策树（DecisionTree）、BP(Back-Propagation）神经网络算法、径向基函数（RadialBasisFunctions）、遗传分类办法、粗糙集分类办法等。我们将在2。3中以K近邻举例介绍Lazy算法，现以决策树为例介绍Eager办法。归纳学习旨在从大量的经验数据中归纳和提取普通的鉴定规则和模式，它是机器学习最核心、最成熟的分支。以Quinlan在1986年提出的ID3为代表决策树归纳学习算法,它是一种基于信息增益的典型自上而下的决策树归纳办法.以决策树为知识体现形式,含有描述简朴、分类速度快、计算量小的特点，能归纳出一种较“好”的决策树，且合用于大规模数据集的学习问题。含糊ID3算法(Fuzzy—ID3）是传统ID3算法在含糊环境下的一种推广，这种算法能解决与人的思维和感觉有关的不拟定性，因而应用更为广泛。含糊ID3算法的核心是使用含糊信息熵来选择扩展属性，根据所选的属性来分割决策树中现在节点的数据,从而生成一棵决策树。含糊决策树产生过程涉及下列几个环节:①训练数据的含糊化。将数据集按一定比例分成训练集和测试集,含糊化过程使用全部训练例子，根据迭代自组织的含糊聚类算法产生全局中心,并由此中心含糊化全部训练例子及测试例子。②ID3算法是在含糊化后的全部训练例子的基础上进行。决策树的建立过程以下:对每一属性计算信息增益，用品有最大信息增益的属性来扩展根节点。删除节点的空分支,对节点的每一非空分支计算属于这一分支的全部对象分到每一类的真实水平S。若分到某一类的真实水平超出阈值β,则终止这一分支作为一种叶子(标记为现在类）。否则考察另一种属性与否能继续分割这个分支并进一步增加信息增益。如果能,则选择含有最大信息增益的属性作为决策节点，如果不能，则终止这一分支作为一种叶子。在叶子节点，全部的对象以最高的真实水平属于同一类。对于每一新生成的决策节点重复第2步,直到不能向下扩展。决策树建立完毕.③将决策树转化为一组规则，其中每条规则是从根节点出发到叶子节点的一条途径。④将得到的这组全局规则应用于训练例子，得到分类的训练精确率；然后将全部测试例子与规则逐个匹配，得到分类的测试精确率。从以上二个算法中，我们能够看出Lazy和Eager这两种分类办法有本质的不同。从计算时间的角度讲,Lazy办法的训练阶段基本不需要计算时间，但是当一种新例子到来时就需要预测目的函数值，因此测试阶段的计算量比较大。而Eager办法则与之相反,训练阶段需要计算得到目的函数,因此训练阶段的计算量比较大；从对新例子分类的角度讲，Lazy办法总是当新例子到来时才开始预测，而Eager办法在训练阶段就完毕了对全部例子目的函数的建立。因此，它们的归纳偏好不同，Lazy办法侧重现在具体例子具体分析，而Eager办法在碰到测试例子之前就已经为其选择了对应的目的函数。这两种分类办法哪一种更含有概括性呢？假设在同样的假说空间中解决问题,Lazy办法明显含有更丰富的假说空间，由于它能够选择多个局部相似的组合来表达目的函数；Eager办法则在训练阶段必须拟定一种全局相似。因此通过实验对两者进行研究比较，从而能够对实际应用算法选择提供经验性结论，含有较好的实际意义。现在广泛应用的基于统计的模型有向量空间模型、NaiveBayes概率模型、实例映射模型和支持向量机模型。NaiveBayes模型是基于两项假设之上的一种概率分类模型。支持向量机是一种用于解决模式识别问题的机器学习办法，它重要基于构造风险最小化原理。映射模型的重要思想是把分类问题转化为矩阵变换的问题。其中变换矩阵用奇异值分解的办法求得。但实例映射模型需要大量的良好代表性数据。相对于支持向量机模型,实例映射模型计算量大，分类速度慢且精度较低。向量空间模型(VectorSpaceModel。VSM）是由G。Salton等人在20世纪60年代提出的。它把文档分类简化为以项的权重为分量的向量表达，把分类过程简化为空间向量的运算，使得问题的复杂性大大减低。另外，向量空间模型对项的权重评价、相似度的计算都没有作统一的规定，只是提供了一种理论框架，能够使用不同的权重评价函数和相似度计算办法,使得此模型有广泛的适应性。2。2基于实例的学习算法基于实例的学习算法并不像上面介绍的决策树算法等分类算法同样建立明确的分类规则，而是直接存储训练样本，并没有在训练样本的基础上获取一种模拟输出函数。当一种测试样本点到来时，才开始计算训练样本与其的相似度，从而拟定未知样本的分类。也就是说，基于实例的学习算法是对每一种测试样本点都创立对应不同的目的输出函数，这是与神经网络算法、决策树算法不同的思想。事实上,诸多技术都对测试样本点的某一种近邻范畴内创立局部模拟函数，而不是在整个训练样本空间创立测试样本的模拟输出函数。这种局部近似的优点是当目的函数比较复杂时，能够选择相对简朴的局部模拟函数进行分类输出。但是基于实例的学习算法有一种明显的缺点是对每一种测试样本点分类的计算代价相对较高。这重要是由于算法把全部的计算都在一种测试样本点到来的时候开始的。另一种缺点是在谋求测试样本点与训练样本点的相似度的时侯,考虑了描述样本点的全部属性，那么就有可能出现第一章1。2中叙述的，如果不考虑全部属性而只参考一部分属性的话，两个样本点相似度将会有很大的变化.2.3K-近邻办法2.3。1近来邻分类算法介绍近邻算法是基于实例学习的分类算法中比较惯用的一种办法。令x={x1，…，xn},其中每一种样本xi所属的类别均已知。对于测试样本点x，在集合中X中距离它近来的点记为x’,那么，近来邻规则的分类办法就是把点x分为x'所属的类别。普通近来邻规则办法的误差率比最小可能误差率（即贝叶斯误差率）要大。然而，在无限训练样本的状况下，这个误差至多不会超出贝叶斯误差率的两倍.近来邻点的标记ωi（某个i）是一种随机变量。ωi的概率为后验概率,当样本个数非常大的时候，有理由认为x’距离x足够近，使得p（wi｜x)=p（wi|x）。由于这正好是状态位于wi的概率，因此近来邻规则自然是真实概率的一种有效的近似。2。3。2K—近邻算法实现KNN算法最早是由Cover和Hart提出的一种非参数分类算法，现已广泛应用于模式识别和数据挖掘的各个领域。分类思想是:给定一种待分类的样本x,首先找出与x最靠近的或最相似的K个已知类别标签的训练集样本，然后根据这K个训练样本的类别标签拟定样本x的类别。算法环节：①构建训练样本集合X。②设定K的初值。K值的拟定没有一种统一的办法(根据具体问题选用的K值可能有较大的区别）。普通办法是先拟定一种初始值,然后根据实验成果不停调试,最后达成最优.③在训练样本集中选出与待测样本近来的K个样本.假定样本点x属于n维空间Rn,样本之间的“近邻”普通由欧式距离来度量。2。4算法分析2。4。1算法实现defclassify0（inx，dataset，lables,k）：dataSetSize=dataSet.shape［0］diffMat=tile（inX,（dataSetSize，1）)—dataSetsqDiffMat=diffMat*＊2sqDistances=sqDiffMat。sum(axis=1)distances=sqDistances*＊0。5sorteDistIndicies=distances.argsort()classCount={}foriinrange（k）：voteIlabel=labels［sortedDistIndicies[i］]classCount[voteIlabel］=classCount。get（voteIlabel,0)+1]sortedClassCount=sorted(classCount.iteritems（)，key=operator。itemgetter（1），reverse=True)returnsortedClassCount［0]［0］2。4。2算法的优缺点KNN分类办法是一种非参数的分类技术，对于未知和非正态分布的数据能够获得较高的分类精确率,含有概念清晰、易于实现等诸多优点。但同时也存在分类过程中计算量过大、对样本库过于依赖和度量相似性的距离函数不合用等问题。KNN分类办法的重要优点涉及：①算法简朴直观，易于实现；②不需要产生额外的数据来描述规则,它的规则就是训练数据(样本）本身，并不是规定数据的一致性问题，即能够存在噪音；③KNN办法即使从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。因此，采用这种办法能够较好地避免样本数量的不平衡问题④从分类过程来看，KNN办法最直接地运用了样本之间的关系，减少了类别特性选择不当对分类成果造成的不利影响,能够最大程度地减少分类过程中的误差项。对于某些类别特性不明显的类别而言，KNN法更能体现出其分类规则独立性的优势，使得分类自学习的实现成为可能。传统的KNN办法的局限性之处重要涉及：1)分类速度慢近来邻分类器是基于实例学习的懒惰学习办法，由于它是根据所给训练样本构造的分类器，是将全部训练样本首先存储起来，当要进行分类时,就临时进行计算解决。需要计算待分样本与训练样本库中每一种样本的相似度，才干求得与其近来的K个样本.对于高维样本或样本集规模较大的状况，其时间和空间复杂度较高,时间代价为O(mn)，其中m为向量空间模型空间特性维数，n为训练样本集大小。2）样本库容量依赖性较强对KNN算法在实际应用中的限制较大：有不少类别无法提供足够的训练样本，使得KNN算法所需要的相对均匀的特性空间条件无法得到满足，使得识别的误差较大。3）特性作用相似与决策树归纳办法和神经网络办法相比，传统近来邻分类器认为每个属性的作用都是相似的（赋予相似权重）。样本的距离是根据样本的全部特性（属性）计算的。在这些特性中，有些特性与分类是强有关的，有些特性与分类是弱有关的，尚有某些特性（可能是大部分)与分类不有关.这样，如果在计算相似度的时候，按全部特性作用相似来计算样本相似度就会误导分类过程。4)K值的拟定KNN算法必须指定K值,K值选择不当则分类精度不能确保.2。4.3KNN的改善对于KNN分类算法的改善办法重要能够分为加紧分类速度、对训练样本库的维护、相似度的距离公式优化和K值拟定四种类型。①加紧KNN算法的分类速度就学习而言，懒惰学习办法比主动学习办法要快，就计算量而言，它要比主动学习办法慢许多。由于懒惰学习办法在进行分类时，需要进行大量的计算。针对这一问题，到现在为止绝大多数解决办法都是基于减少样本量和加紧搜索K个近来邻速度两个方面考虑的：1）浓缩训练样本当训练样本集中样本数量较大时，为了减小计算开销，能够对训练样本集进行编辑解决，即从原始训练样本集中选择最优的参考子集进行K近来邻寻找,从而减少训练样本的存储量和提高计算效率。这种途径最重要的办法是Hart的Condensing算法、WilSon的Editing算法和Devijver的MultiEdit算法,Kuncheva使用遗传算法在这方面也进行了某些研究.2)加紧K个近来邻的搜索速度这类办法是通过快速搜索算法,在较短时间内找到待分类样本的K个近来邻。在具体进行搜索时，不要使用盲目的搜索办法，而是要采用一定的办法加紧搜索速度或减小搜索范畴，例如能够构造交叉索引表,运用匹配成功与否的历史来修改样本库的构造，使用样本和概念来构造层次或网络来组织训练样本.这类办法重要可分为三类:空间（数据）分区办法、以扫描作为基础的方法和线性化办法。②相似度的距离公式的优化为了变化传统KNN算法中特性作用相似的缺点，可在相似度的距离公式中给特性赋予不同权重，例如在欧氏距离公式中给不同特性赋予不同权重特性的权重.③对训练样本库的维护对训练样本库进行维护以满足KNN算法的需要，涉及对训练样本库中的样本进行添加或删除。对样本库的维护并不是简朴的增加删除样本，而是可采用适宜的方法来确保空间的大小，如符合某种条件的样本能够加入数据库中，同时能够对数据库库中已有符合某种条件的样本进行删除。从而确保训练样本库中的样本提供KNN算法所需要的相对均匀的特性空间。文献[39,40，41］从不同角度对样本库进行了维护，提高了KNN算法的分类精度和减少了样本量。但有时由于样本库中无法提供每一种类的足够训练样本,使得KNN算法所需要的相对均匀的特性空间条件无法得到满足.并且考虑到单纯靠增加样本也会带来计算量过大的问题，P.Viswannth等提出了OLP—synthesis算法，以获得一种压缩的含有普遍性的训练样本集合.④K值选择K值的选择原则普通为：1）K的选择往往通过大量独立的测试数据、多个模型来验证最佳的选择;2)K值普通事先拟定，也能够使用动态的，例如采用固定的距离指标,只对不大于该指标的样本进行分析。文献[43]就采用了动态K值。有时类别之间样本极为不平衡,K值的选择更为困难，文献［44］针对这种类的样本数量不平衡的状况提出了K值的选择办法.尚有某些其它方面对KNN算法性能进行改善的办法，例如迭代近邻法等。3 算法应用3.1k—近邻算法在肝癌检测中的应用肝癌是一种常见的恶性肿瘤，发病率呈逐年升高态势。临床医学中对肝癌的诊疗精确率规定较高。运用计算机辅助诊疗检测、鉴定肝癌可提高诊疗的速度与精度。如何对的判断肝脏的健康状况及病变类别是肝癌检测的最后任务.现在,重要运用提取肝脏的纹理特性与形状特性,并结合对应的数据挖掘分类算法实现肝癌的具体分类与识别。在肝脏CT图像中，病变肝脏与正常肝脏的区别重要反映为不同的纹理特性,肝癌类别重要反映为不同的形状特性。因而可运用肝脏的纹理特性与形状特性进行肝癌的分类检测.纹理特性用于识别正常肝脏与病变肝脏，形状特性用于肝癌类型的识别。该文将K—NN算法分别应用于基于纹理特性的分类与基于形状特性的分类。3.2面对延迟敏感性应用为了减少顾客访问延迟,延迟敏感型网络应用需要选择适宜的邻近服务节点响应顾客访问请求.分布式K

近邻搜索通过可扩展的选择距任意顾客节点邻近的K

个服务节点,能够有效满足网络应用延迟优化的目的。已有工作在精确度以及可扩展性等方面存在局限性.针对可扩展精确的K

近邻搜索问题，文中提出了分布式K

近邻搜索办法DKNNS（distributed

K

nearestneighborsearch).DKNNS将大量的服务节点组织为邻近性感知的多级环，通过最远节点搜索机制选择优化的K

近邻搜索初始化节点，然后基于回退方式快速的在目的节点邻近区域发现K

个近邻。基于理论分析，模拟测试以及真实环境下的布署实验发现,在不同规模的节点集合下，DKNNS算法能够拟定近似最优的K

个服务节点。且DKNNS的查询延迟,查询开销均明显低于Meridian算法.最后,DKNNS的返回成果相对于Meridian含有较高的稳定性。3。3改善的K—近邻算法在中文网页分类的应用K—邻近算法作为一种比较简朴,易于实现并且错误低的分类算法，广泛应用于网页分类、模式识别和数据挖掘等多个领域中.本文介绍了传统K-邻近算法并分析了该算法在网页相似度值的计算存在的局限性，在此基础上,本文提出了基于类中心向量的K—近邻算法,通过理论分析和仿真实验成果证明了该算法对于中文网页分类含有较好的分类效果。总结模式分类在现实领域有着非常广泛的应用。K近邻算法是模式分类算法中一类惯用的算法。本文针对传统的KNN算法的局限性之处,提出了两点改善方法。针对KNN算法的计算量大、速度慢的缺点，对训练数据采用了预解决的办法.首先采用某一聚类办法对训练数据进行分类，然后再与K近邻办法相结合来判断待测样本的类别.现有的办法都是通过聚类之后拟定类别,按一定的规则挑选出来含有代表性的数据。然后再将这些挑选出来的数据作为训练样本.但这类办法能去除的数据非常有限，因此对计算量大的改善不大，而本文提出的新的算法：在聚类之后，首先计算出来各个类别的中心，然后只需要考虑待测样本和聚类中心的距离就能够。然后再根据最后得到的距离的大小判断该点所属的类别。通过实例验证表明,该办法在算法的时间复杂度方面有一定的改