KNN算法及改进 论文.doc

漳州师范学院 毕业论文（设计）KNN算法及改进THE ALGORITHM OF KNN AND IMPROVEMENT姓 名： 程至镖 学 号： 090803158 系 别： 计算机科学与工程系 专 业： 计算机科学与技术 年 级： 09级 指导教师： 周忠眉 2011 年 4 月 24 日34摘要数据挖掘是指从数据库中抽取隐含的、具有潜在使用价值信息的过程，是一种新型的数据分析技术，已被广泛应用于金融、保险、政府、教育、运输以及国防等领域。分类问题是数据挖掘技术中的主要研究课题。分类有很多方法，而KNN算法是利用较广泛的数据挖掘算法之一。本文就KNN算法及改进的KNN算法原理、实施步骤进行了详尽的描述和分析，并给出了具体的挖掘事例，通过例子来阐述KNN算法及改进的KNN算法工作原理和过程。关键词：数据挖掘；分类；算法；KNN算法；距离；欧几里德AbstractData mining means the process of extracting cryptic and potential helpful information from a mass of Data. It is one kind of brand new Data analysis technology and popular in the field of banking finance, insurance, government, education,transportation and national defense etc.The problem of classification is a major subject of research in data mining technology. There are many methods for Data classification, and the K-nearest neighbors classification (KNN) algorithm is one of the much more popular Data mining algorithm.The paper progressively elaborates and labors the algorithm principles and the implementation step of KNN algorithm and the improvement of KNN algorithm, meanwhile, illustrates the working principle as well as the process of KNN algorithm and the improvement of KNN algorithm through specific excavation examples. Key words: Data mining，Classification，Algorithm, KNN,Distance, Euclid of Alexandria目 录摘要IAbstractI1引言21.1数据挖掘的背景，含义及其应用21.2 数据挖掘的步骤21.3 本文的组织结构32 分类算法分析与实现32.1 分类概念与分类方法32.2 分类过程32.3 KNN算法介绍32.3.1 KNN算法的基本概念32.3.2 KNN算法分析与实现43. KNN算法实例说明44.总结与展望33参考文献：34致谢351引言1.1数据挖掘的背景，含义及其应用随着数据库、网络等技术的迅速发展，人们积累的数据越来越多，我们已经被淹没在数据和信息的汪洋大海中。人们需要有新的、更有效的方法对各种大量的数据进行分析、提取以挖掘其潜能，数据挖掘正是在这样的应用需求环境下产生并迅速发展起来的，它的出现为智能地把海量的数据转化为有用的信息和知识提供了新的思路和手段。数据挖掘是一种技术，它将传统的数据分析方法与大量数据的复杂性相结合。数据挖掘是从大量的数据中挖掘出隐含的、未知的、用户可能感兴趣的和对决策有潜在价值的知识和规则。这些规则蕴含了数据库中一组对象之间的特定关系，揭示出一些有用的信息。数据挖掘的主要技术包括特征提取、分类、聚类、相关性分析、偏差分析。数据挖掘的分析方法：分类（Classification）估值（Estimation）预言（Prediction）相关性分组或关联规则（Affinity grouping or association rules）聚焦（Clustering）描述和可视化（Description and Visualization）。以上的六种分析方法可分为两类：直接数据挖掘与间接数据挖掘。直接数据挖掘的目标是利用可用的数据建立一个模型，这个模型对剩余的数据，对一个特定的变量进行描述。间接数据挖掘的目标中没有选出某一具体的变量，用模型进行描述，而是在所有的变量中建立起某种关系。分类、估值、预言属于直接数据挖掘；后三者属于间接数据挖掘。数据挖掘除了用于科学研究，还应用于各种不同的行业。例如，零售业，电信业和信用卡业的市场营销、保险业和金融业的风险分析，欺诈检测、医疗诊断、通信网络管理、Web挖掘等有大量基础数据的行业1-6。1.2 数据挖掘的步骤数据挖掘的全过程描述如图1所示：图1 数据挖掘步骤示意图整个数据挖掘过程是由若干挖掘步骤组成的，主要步骤有：(1)数据清洗(data cleaming)，其作用就是清除数据噪声和与挖掘主题明显无关的数据。(2)数据集成(data integration)，其作用就是将来自多数据源中的相关数据组合到一起。(3)数据转换(data transformation)，其作用就是将数据转换为易于进行数据挖掘的数据存储形式。(4)数据挖掘(data mining)，它是知识挖掘的一个基本步骤，其作用就是利用智能方法挖掘数据模式或规律知识。(5)模式评估(pattern evaluation)，其作用就是根据一定评估标准从挖掘结果筛选出有意义的模式知识。(6)知识表示(knowledge presentation)，其作用就是利用可视化和知识表达技术，向用户展示所挖掘出的相关知识。1.3 本文的组织结构本文的其余部分的安排如下：本文第二节介绍了分类算法以及KNN算法的一些概念及优缺点，第三节介绍了三种方法的实例实现过程，第四节是对数据分类的总结与展望。2 分类算法分析与实现2.1 分类概念与分类方法分类是数据挖掘中应用领域极其广泛的重要技术之一,至今已经提出很多算法。分类是根据数据集的特点构造一个分类器,利用分类器对未知类别的样本赋予类别的一种技术。构造分类器的过程一般分为训练和测试两个步骤。在训练阶段,分析训练数据集的特点,为每个类别产生一个对相应数据集的准确描述或模型。在测试阶段,利用类别的描述或模型对测试进行分类,测试其分类准确度。一般来说,测试阶段的代价远远低于训练阶段7。分类有决策树算法、贝叶斯算法、人工神经网络算法、K近邻算法、遗传算法、支持向量机算法等主要的算法。分类技术在信用卡审批、目标市场定位、医疗诊断、故障检测、图像识别、声音识别、气候变化等领域有着广泛的应用。根据分类各种算法的特点以及权衡实际情况（时间、知识量、软硬件等条件）。2.2 分类过程数据分类是一个两步过程：第一步,建立一个模型，描述预定的数据类或概念集.通过分析由属性描述的数据库元组来构造模型。假定每个元组属于一个预定义的类，由一个称作类标号属性的属性确定.对于分类，数据元组也称作样本、实例或对象.为建立模型而被分析的数据元组形成训练数据集.训练数据集中的单个元组称作训练样本,并随机地由样本群选取.由于提供了每个训练样本的类标号，这个过程也称作有指导的学习(即模型的学习在被告知每个训练样本属于哪个类的“指导”下进行)。第二步，使用模型进行分类.首先评估模型(分类法)的预测准确率。保持(holdout)方法是一种使用类标号样本测试集的简单方法.这些样本随机选取，并独立于训练样本.模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比.对于每个测试样本，将已知的类标号与该样本的学习模型类预测比较。注意，如果模型的准确率根据训练数据集评估，评估可能是乐观的，因为学习模型倾向于过分适合数据(即它可能并入训练数据中某些异常,这些异常不出现在总体样本群中)。如果认为模型的准确率可以接受，就可以用它对类标号未知的数据元组或对象进行分类8。2.3 KNN算法介绍2.3.1 KNN算法的基本概念1.训练集训练集(TrainingSet), 分类过程的输入数据,或称是一条条的数据库记录(Record)组成的。每一条记录包含若干个属性,组成一个特征向量。训练集的每条记录还有一个特定的类标签与之对应。数据挖掘分类就是分析输入数据,通过在训练集中的数据表现出来的特性,为每一个类找到一种准确的描述或者模型9。2. 测试集测试集（TestSet）与训练集相同，也是由已知类别的对象组成的数据集，但它是用来测试分类算法的性能。通过分类算法判定该对象所属的类别，然后把实际类别与判定的类别进行比较，通过对比较结果的统计，可以得到分类算法的分类正确率。测试集一般选取与训练集不同的数据集。3.K“近邻”K近邻分类基于类比学习，训练样本用n 维数值属性描述，每个样本代表n 维空间的一个点，这样，所有的训练样本都存放在n 维模式空间中。给定一个未知样本，k近邻分类法搜索模式空间，找出最接近未知样本的k 个训练样本。计算着k个训练样本中的个数或与未知样本中相同的个数。4. 距离函数距离函数决定训练集中的哪些样本是待测样本的K个邻居，常用距离函数有欧几里德距离，平方差和标准差等。如：2个点和的欧几里德距离是2.3.2 KNN算法分析与实现K近邻分类（K-nearest neighbors ,KNN）是基于类比学习。K近邻分类是把一组已知类别的数据作为训练样本，根据已知样本的类别对新样本进行分类。K近邻分类的思想如下：首先，按照某种距离函数计算新样本与训练集合样本之间的距离，选出其中距离最近的K个邻居；然后，根据这K个邻居找到其中某一个类，该类的个数为最大，则新样本的类别就判定属于该类。本文采用了三种方法来计算距离，将平均相似度作为距离；用测试数据与训练集相同的属性对象的信息熵乘以各自在训练集中的概率，并求和，再求平均，作为距离；用测试数据与训练集相同的属性对象的好坏度乘以各自在训练集中的概率，并求和，再求平均，作为距离。3. KNN算法实例说明 算法中要用到的数据如下表一所示：其中前20条数据作为训练集，后6条作为测试数据。表中A-I表示蘑菇数据中蘑菇的各个条件属性，J表示决策属性（就是表示该蘑菇可吃还是不可吃） 表一：数据集ABCDEFGHIJX1191930556072798289X2591132555976808890X3371435536073818889X43101732555976808390X5391135555872818889X6391433525775808590X7491136545973808889X8491933525675808590X9391137546073818889X103101433556075798290X111101834556072798289X12371934545775818890X133101834556076778289X14471436545975808590X15371131556076778289X16391732556076808890X173101833556073798289X18391936525775818890X19371436556072798289X204101132545976808590X21391937556072818289X22391434545775808290X23391735555973818889X24391934525675808290X25491135556072818889X26391434545675818290X27471731536072808889X28371735535872818889X29491732545976808890X30391737545872818889X31391434525775818890X32471130556073798289X33471933545675818590X341101831556072798289X353101732545976808590X36471736536073808889例一：将测试数据与训练集中每条数据相同个数的平均个数作为距离计算第21条与训练集中每条数据相同的个数记为d（i=1,219,20）d1=6 d2=2 d3=3 d4=2 d5=5 d6=2 d7=1 d8=2 d9=5 d10=4 d11=4d12=3 d13=4 d14=0 d15=4 d16=4 d17=4 d18=4 d19=5 d20=0= = =2.9取大于=2.9的属于89的数：d1=6 d3=3 d5=5 d9=5 d11=4 d13=4 d15=4 d17=4 d19=5 = = =4.44取大于=2.9的属于90的数：d10=4 d12=3 d16=4 d18=4 = =3.75由于大于，所以X21属于89，判断正确计算第22条与训练集中每条数据相同的个数记为d（i=1,219,20）d1=2 d2=2 d3=2 d4=2 d5=2 d6=6 d7=3 d8=3 d9=3 d10=4 d11=2d12=5 d13=3 d14=4 d15=2 d16=3 d17=2 d18=4 d19=3 d20=2取大于=2.95的属于89的数：d7=3 d9=3 d13=3 d19=3 取大于=2.95的属于90的数：d6=6 d8=3 d10=4 d12=5 d14=4 d16=3 d18=4 由于小于，所以X22属于90，判断正确计算第23条与训练集中每条数据相同的个数记为d（i=1,219,20）d1=2 d2=4 d3=5 d4=4 d5=6 d6=2 d7=4 d8=1 d9=5 d10=2 d11=1d12=3 d13=2 d14=1 d15=2 d16=5 d17=3 d18=4 d19=2 d20=1取大于=2.95的属于89的数：d3=5 d5=6 d7=4 d9=5 d17=3 取大于=2.95的属于90的数：d2=4 d4=4 d12=3 d16=5 d18=4 由于大于，所以X23属于89，判断正确计算第24条与训练集中每条数据相同的个数记为d（i=1,219,20）d1=3 d2=2 d3=1 d4=2 d5=2 d6=5 d7=2 d8=6 d9=2 d10=3 d11=2d12=4 d13=3 d14=2 d15=2 d16=3 d17=2 d18=5 d19=2 d20=1取大于=2.7的属于89的数：d1=3 d13=3 取大于=2.7的属于90的数：d6=5 d8=6 d10=3 d12=4 d16=3 d18=5由于小于，所以X24属于90计算第25条与训练集中每条数据相同的个数记为d（i=1,219,20）d1=4 d2=4 d3=4 d4=1 d5=7 d6=1 d7=4 d8=2 d9=5 d10=2 d11=3d12=2 d13=2 d14=1 d15=3 d16=4 d17=2 d18=3 d19=3 d20=2取大于=2.95的属于89的数：d1=4 d3=4 d5=7 d7=4 d9=5 d11=3 d15=3 d19=3 取大于=2.95的属于90的数：d2=4 d16=4 d18=3由于大于，所以X25属于89，判断正确计算第24条与训练集中每条数据相同的个数记为d（i=1,219,20）d1=2 d2=1 d3=3 d4=1 d5=3 d6=4 d7=2 d8=3 d9=4 d10=4 d11=2d12=5 d13=3 d14=3 d15=2 d16=2 d17=2 d18=4 d19=3 d20=1取大于=2.7的属于89的数：d3=3 d5=3 d9=4 d13=3 d19=3 取大于=2.7的属于90的数：d6=4 d8=3 d10=4 d12=5 d14=3 d18=4由于小于，所以X26属于90，判断正确例二：将测试数据中与训练集相同的数的好坏度乘以他们各自在训练集中的概率的和作为距离统计训练集中每个数字在89和90出现的次数，如表二： 表二：属性对象的个数13457910111417181930313233343536378927103434203111012221900631253232030043102052535455565758596072737576777980818901270011844022413903034130420064017282838588896004901144好坏度：|P*|(ln- ln)（P表示测试数据中的数字在训练集中处于89的个数）1：2（ln-ln）=2（0+0.693）=1.3863：7（ln-ln）=7（-0.619+0.693）=0.5184：3（ln-ln）=3（-0.288+0.693）=1.2165：1（ln-ln）=1（0+0.693）=0.6937：3（ln-ln）=3（-0.511+0.693）=0.547 9：5（ln-ln）=5（-0.586+0.693）=0.52610：3（ln-ln）=3（-0.693+0.693）=011：4（ln-ln）=4（-0.405+0.693）=1.15014：3（ln-ln）=3（-0.511+0.693）=0.54717：2（ln-ln）=2（0+0.693）=1.38618：3（ln-ln）=3（0+0.693）=2.079 19：3（ln-ln）=3（-0.288+0.693）=1.21630：1（ln-ln）=1（0+0.693）=0.69331：1（ln-ln）=1（0+0.693）=0.69332：4（ln-ln）=4（0+0.693）=2.77333：3（ln-ln）=3（-0.288+0.693）=1.21634：3（ln-ln）=3（-0.405+0.693）=0.86335：3（ln-ln）=3（0+0.693）=2.07936：2（ln-ln）=2（-0.693+0.693）=037：1（ln-ln）=1（0+0.693）=0.69352：3（ln-ln）=3（0+0.693）=2.07953：1（ln-ln）=1（0+0.693）=0.69354：3（ln-ln）=3（-0.511+0.693）=0.54755：7（ln-ln）=7（-0.452+0.693）=1.68756：1（ln-ln）=1（0+0.693）=0.69357：3（ln-ln）=3（0+0.693）=2.07958：1（ln-ln）=1（0+0.693）=0.69359：4（ln-ln）=4（-0.223+0.693）=1.87960：8（ln-ln）=8（-0.223+0.693）=3.75972：4（ln-ln）=4（0+0.693）=2.77373：4（ln-ln）=4（0+0.693）=2.77375：6（ln-ln）=4（0+0.693）=2.77376：4（ln-ln）=4（-0.405+0.693）=1.15077：3（ln-ln）=3（0+0.693）=2.07979：4（ln-ln）=4（-0.223+0.693）=1.87980：7（ln-ln）=7（-0.134+0.693）=3.91681：3（ln-ln）=3（-0.511+0.693）=0.54382：6（ln-ln）=6（-0.154+0.693）=3.23483：1（ln-ln）=1（0+0.693）=0.69385：4（ln-ln）=4（0+0.693）=2.77388：4（ln-ln）=4（-0.693+0.693）=0统计X21与训练集中相同的数，记为K(X21，Xi（i=1,219,20）)：K(X21，X1)：9，19，55，60，72，82 K(X21，X2)：9，55 K(X21，X3)：3，60，81 K(X21，X4)：3，55 K(X21，X5)：3，9，55，72，81 K(X21，X6)：3，9 K(X21，X7)：9 K(X21，X8)：9，19 K(X21，X9)：3，9，37，60，81 K(X21，X10)：3，55，60,82 K(X21，X11)：55，60，72，82 K(X21，X12)：3，19，81 K(X21，X13)：3，55，60，82 K(X21，X14)： K(X21，X15)：3，55，60，82 K(X21，X16)：3，9，55，60 K(X21，X17)：3，55，60，82 K(X21，X18)：3，9，19，81 K(X21，X19)：3，55，60，72，82 K(X21，X20)： 接下来计算X21与训练集中每条数据的相似度，方法为K(X21，Xi)中的每个数在训练集中的概率乘以他们各自的好坏度，并求和d1=0.526+1.216+1.687+3.759+2.773+3.234 =0.2367+0.2432+0.92785+1.8795+0.5546+1.1319=4.97375d2=0.526+1.687=0.2367+0.92785=1.16455d3=0.518+3.759+0.543=0.3367+1.8795+0.13575=2.35195d4=0.518+1.687=0.3367+0.92785=1.26445d5=0.518+0.526+1.687+2.773+0.543 =0.3367+0.2367+0.92785+0.5546+0.13575 =2.1916d6=0.518+0.526=0.3367+0.2367=0.5734d7=0.526=0.2367d8=0.526+1.216=0.2367+0.2432=0.4799d9=0.518+0.526+0.693+3.759+0.543 =0.3367+0.2367+0.03465+1.8795+0.13575 =2.6233d10=0.518+1.687+0.526+3.234=0.3367+0.92785+0.263+1.1319=2.65945d11=1.687+3.759+2.773+3.234=0.92785+1.8795+0.5546+1.1319=4.49385d12=0.518+1.216+0.543=0.3367+0.2432+0.13575=0.71565d13=0.518+1.687+3.759+3.234=0.3367+0.92785+1.8795+1.1319=4.27595d14=0d15=0.518+1.687+3.759+3.234=0.3367+0.92785+1.8795+1.1319=4.27595d16=0.518+0.526+1.687+3.759=0.3367+0.2367+0.92785+1.8795=3.38075d17=0.518+1.687+3.759+3.234=0.3367+0.92785+1.8795+1.1319=4.27595d18=0.518+0.526+1.216+0.543=0.3367+0.2367+0.2432+0.13575=0.95235d19=0.518+1.687+3.759+2.773+3.234 =0.3367+0.92785+1.8795+0.5546+1.1319=4.83055d20=0= = =2.28取大于=2.28的属于89的数：d1=4.97375 d3=2.35195 d9=2.6233 d11=4.49385 d13=4.27595 d15=4.27595 d17=4.27595 d19=4.83055 = = =4.01取大于=2.28的属于90的数：d10=2.65945 d16=3.38075 = = =3.0201由于大于，所以X21属于89，判断正确统计X22与训练集中相同的数，记为K(X22，Xi（i=1,219,20）)：K(X22，X1)：9，82 K(X22，X2)：9，80 K(X22，X3)：3，14 K(X22，X4)：3，80 K(X22，X5)：3，9 K(X22，X6)：3，9，14，57，75，80 K(X22，X7)：9，54，80 K(X22，X8)：9，75，80 K(X22，X9)：3，9，54 K(X22，X10)：3，14，75，82 K(X22，X11)：34，82 K(X22，X12)：3，34，54，57，75 K(X22，X13)：3，34，82 K(X22，X14)：14，54，75，80 K(X22，X15)：3，82 K(X22，X16)：3，9，80 K(X22，X17)：3，82 K(X22，X18)：3，9，57，75 K(X22，X19)：3，14，82 K(X22，X20)：54，80接下来计算X22与训练集中每条数据的相似度，方法为K(X22，Xi)中的每个数在训练集中的概率乘以他们各自的好坏度，并求和取大于=1.73223的属于89的数：d7=1.93985 取大于=1.73223的属于90的数：d2=1.8031 d4=1.9031 d6=3.42025 d8=2.635 d10=2.43725 d12=1.74665 d14=2.6718 d16=2.1398由于小于，所以X22属于90，判断正确统计X23与训练集中相同的数，记为K(X23，Xi（i=1,219,20）)：K(X23，X1)：9，55 K(X23，X2)：9，55，59，88 K(X23，X3)：3，35，73，81，88 K(X23，X4)：3，17，55，59 K(X23，X5)：3，9，35，55，81，88 K(X23，X6)：3，9 K(X23，X7)：9，58，73，88 K(X23，X8)：9 K(X23，X9)：3，9，73，81，88 K(X23，X10)：3，55 K(X23，X11)：55 K(X23，X12)：3，81，88 K(X23，X13)：3，55 K(X23，X14)：59 K(X23，X15)：3，55 K(X23，X16)：3，9，17，55，88 K(X23，X17)：3，55，73 K(X23，X18)：3，9，81，88 K(X23，X19)：3，55 K(X23，X20)：59接下来计算X23与训练集中每条数据的相似度，方法为K(X23，Xi)中的每个数在训练集中的概率乘以他们各自的好坏度，并求和取大于=1.133的属于89的数：d1=1.16455 d3=1.23495 d5=1.8449 d7=1.26105 d9=1.26375 d13=1.26455 d15=1.26455 d17=1.81915 d19=1.26455取大于=1.133的属于90的数：d2=1.6343 d4=1.8729 d10=1.26455 d16=1.63985 由于小于，所以X23属于90，判断错误统计X24与训练集中相同的数，记为K(X24，Xi（i=1,219,20）)：K(X24，X1)：9，19，82 K(X24，X2)：9，80 K(X24，X3)：3 K(X24，X4)：3，80 K(X24，X5)：3，9 K(X24，X6)：3，9，52，75，80 K(X24，X7)：9，80 K(X24，X8)：9，19，52，56，75，80 K(X24，X9)：3，9 K(X24，X10)：3，75，82 K(X24，X11)：34，82 K(X24，X12)：3，19，34，75 K(X24，X13)：3，34，82 K(X24，X14)：75，80 K(X24，X15)：3，82 K(X24，X16)：3，9，80 K(X24，X17)：3，82 K(X24，X18)：3，9，19，52，75 K(X24，X19)：3，82 K(X24，X20)：80接下来计算X24与训练集中每条数据的相似度，方法为K(X24，Xi)中的每个数在训练集中的概率乘以他们各自的好坏度，并求和取大于=1.714的属于89的数：d7=1.8031 取大于=1.714的属于90的数：d2=1.8036 d4=1.9031 d6=3.28355 d8=3.2247 d10=2.3005 d14=2.3983 d16=2.1398 d18=1.96035由于小于，所以X24属于90，判断正确统计X25与训练集中相同的数，记为K(X25，Xi（i=1,219,20）)：K(X25，X1)：9，55，60，72 K(X25，X2)：9，11，55，88 K(X25，X3)：35，60，81，88 K(X25，X4)：55 K(X25，X5)：9，11，35，55，72，81，88 K(X25，X6)：9 K(X25，X7)：4，9，11，88 K(X25，X8)：4，9 K(X25，X9)：9，11，60，81，88 K(X25，X10)：55，60 K(X25，X11)：55，60，72 K(X25，X12)：81，88 K(X25，X13)：55，60 K(X25，X14)：4 K(X25，X15)：11，55，60 K(X25，X16)：9，55，60，88 K(X25，X17)：55，60 K(X25，X18)：9，81，88 K(X25，X19)：55，60，72 K(X25，X20)：4，11接下来计算X25与训练集中每条数据的相似度，方法为K(X25，Xi)中的每个数在训练集中的概率乘以他们各自的好坏度，并求和取大于=1.874的属于89的数：d1=3.59865 d3=2.22315 d5=2.4078 d9=2.59695 d11=3.36195 d13=2.80735 d15=3.15235 d17=2.80735 d19=3.36195取大于=1.874的属于90的数：d10=2.80735 d16=3.04405 由于小于，所以X25属于90，判断错误统计X26与训练集中相同的数，记为K(X26，Xi（i=1,219,20）)：K(X26，X1)：9，82 K(X26，X2)：9 K(X26，X3)：3，14，81 K(X26，X4)：3 K(X26，X5)：3，9，81 K(X26，X6)：3，9，14，75 K(X26，X7)：9，54 K(X26，X8)：9，56，75 K(X26，X9)：3，9，54，81 K(X26，X10)：3，14，75，82 K(X26，X11)：34，82 K(X26，X12)：3，34，54，75，81 K(X26，X13)：3，34，82 K(X26，X14)：14，54，75 K(X26，X15)：3，82 K(X26，X16)：3，9 K(X26，X17)：3，82 K(X26，X18)：3，9，75，81 K(X26，X19)：3，14，82 K(X26，X20)：54接下来计算X26与训练集中每条数据的相似度，方法为K(X26，Xi)中的每个数在训练集中的概率乘以他们各自的好坏度，并求和取大于=1.095的属于89的数：d1=1.3686 d11=1.26135 d13=1.59805 d15=1.4686 d17=1.4686 d19=1.60535 取大于=1.095的属于90的数：d6=1.54205 d10=2.43725 d12=1.57055 d14=1.1054 d18=1.54105由于小于，所以X24属于90，判断正确例三：将测试数据中与训练集相同的数的好坏度乘以他们各自在训练集中的概率的和作为距离1：-ln-0=0 3：-ln-ln=0.333+0.357=0.6904：-ln-ln=0.347+0.216=0.563 5：0-ln=07：-ln-ln=0.306+0.367=0.673 9：-ln-ln=0.360+0.327=0.68710：-ln-ln=0.347+0.347=0.694 11：-ln-ln=0.270+0.366=0.63614：-ln-ln=0.367+0.306=0.673 17：0-ln=018：-ln-0=0 19：-ln-ln=0.347+0.216=0.56330：-ln-0=0 31：-ln-0=032：0-ln=0 33：-ln-ln=0.347+0.216=0.56334：-ln-ln=0.270+0.366=0.636 35：-ln-0=036：-