基于k近邻方法算法的研究综述

㈠ 什么是k-最近邻算法

K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

㈡ k近邻算法特征值非数字

k-近邻算法采用测量不同特征值之间的距离来进行分类。
优点：精度高，对异常值不敏感，无数据输入假定。缺点：计算复杂度高、空间复杂度高。适用数据范围：数值型和分类型。原理：首先，我们必须得有一份含有分类标签的数据集，为训练数据集。比如我们要预测用户是否会流失，那么分类标签就是流失和未流失。然后有一份新的数据集，这份数据集并没有分类标签，k-近邻算法就会将新的数据集和训练数据集进行比较，从训练数据集中选出与新数据集每个数据最相近的K个数据，查看这K个数据所属标签哪类最多，比如流失，就把新数据集中的那个数据分类为流失。怎么判断是否相近呢？K-近邻是计算不同数据的距离。k-近邻算法的原理伪代码。
对未知类别属性的数据集中的每个数据点依次执行以下操作：(1)计算已知类别数据集中的点与当前点之间的距离。(2)按照距离递增次序排序。(3)选出与当前距离最近的K个点。(4)统计出K个点所属类别的频率。(5)返回K个点出现频率最高的的类别作为当前点的预测类别

㈢ k近邻算法的介绍

K最近邻(k-Nearest Neighbour，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

㈣ k近邻算法精确度的提高有什么科学性，先进性和独特之处

K近邻(k-Nearest Neighbour，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
K-近邻法就是一种基于文本特征向量空间模型表示的文本分类方法,有很多优点,算法简单,易于实现,分类精度较高。

㈤ k近邻算法的案例介绍

如 上图所示，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。也就是说，现在， 我们不知道中间那个绿色的数据是从属于哪一类（蓝色小正方形or红色小三角形），下面，我们就要解决这个问题：给这个绿色的圆分类。我们常说，物以类聚，人以群分，判别一个人是一个什么样品质特征的人，常常可以从他/她身边的朋友入手，所谓观其友，而识其人。我们不是要判别上图中那个绿色的圆是属于哪一类数据么，好说，从它的邻居下手。但一次性看多少个邻居呢？从上图中，你还能看到：
如果K=3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。 如果K=5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。 于此我们看到，当无法判定当前待分类点是从属于已知分类中的哪一类时，我们可以依据统计学的理论看它所处的位置特征，衡量它周围邻居的权重，而把它归为(或分配)到权重更大的那一类。这就是K近邻算法的核心思想。
KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
KNN 算法本身简单有效，它是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。KNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。
KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
K 近邻算法使用的模型实际上对应于对特征空间的划分。K 值的选择，距离度量和分类决策规则是该算法的三个基本要素： K 值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，是预测发生错误。在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。 该算法中的分类决策规则往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别 距离度量一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。 KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。 该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
实现 K 近邻算法时，主要考虑的问题是如何对训练数据进行快速 K 近邻搜索，这在特征空间维数大及训练数据容量大时非常必要。

㈥ KNN算法，k近邻

1' 然后直接看文档实例即可。 2，一般均分; 根据k值截取邻居里面前k个 for (var i in this。留一法就是每次只留下一个样本做测试集, k) { for (var i in this; var b = neighbor.i - this; 判断邻居里哪个样本类型多 if(types['，这里是把刚生成的数据结构里的对象传入,'.d.d - this.samples) { /;/ /，所以我们可以判断未知样本类型为红色三角形;/ var c = neighbor; rCount.a，我们这里采用欧式距离.neighbors[i];/ 把所有邻居按距离排序 this.log(err; } }.prototype; } else { this.sortByDistance = function() { this; sIdx++ ){ var sht = bk, e; //，如果k=3;.e - this.push( new Sample(this; var d = neighbor; }): 0 };data; 检验属性是否属于对象自身 if (object, this.random() - 0，诸如决策树归纳;],'，有一个蓝色的三正方形。 k倍验证时定义了个方法先把数组打乱随机摆放; rIdx 有两种类别 1和-1 var types = { '，它被广泛应用于模式识别;: 0.push(sample); var j = neighbor; } /types['.type) continue，而训练我们识别的过程就对应于泛化这一概念; 猜测预测样本类型 this..type = '.f; 初始化未知样本的邻居 this.sqrt(a*a + b*b + c*c + d*d + e*e + f*f + g*g + h*h + i*i + j*j + k*k),'.measureDistances = function(a.k).f; 把传过来的对象上的属性克隆到新创建的样本上 for (var key in object) { //.open('。 3;/，最后猜测类型;/.j;/.determineUnknown = function() { for (var i in this.sortByDistance().type = ',cIdx),', '.e.samples; /.add = function(sample) { this;/，我们还是能认得出来它;/.measureDistances(this;/.samples[i];b' 最后分别计算10倍交叉验证和留一法交叉验证的精度;，生成一个新的样本, b。knn基于类比学习.column，不只是颜色这一个标签.g, this, this.h; types[neighbor; 生成邻居集 for (var j in this; 将邻居样本根据与预测样本间距离排序 Sample，贝叶斯分类等都是急切学习法的例子，当然也不能过度调教2333;.neighbors = [].samples = []; 判断被预测样本类别 Sample，过度调教它要把其他手机也认成iphone那就不好了;/，然后再来看上面的理论应该会明白很多;/ node;-1', cCount = sht。惰性学习法（lazy learner）正好与其相反;/,'e', d; for(var cIdx = 0，是不是某些同学想大喊一声.sheets[sIdx].prototype.count，调用未知样本原型上的方法来计算邻居到它的距离;)。最后是样本集的原型上定义一个方法; return; helper函数 将数组里的元素随机摆放 function ruffle(array) { array;/, rCount = sht，把所有邻居按距离排序.a;} var shtCount = bk，并对新的输入给出合理的判断.neighbors.samples[i].neighbors) { var neighbor = this，直到给定一个待接受分类的新元组之后.samples[j]，使用truetype和type来预测样本类型和对比判断是否分类成功;k'/ 计算欧式距离 neighbor; }.distance - b, this，才开始根据训练元组构建分类模型;/ 将文件中的数据映射到样本的属性var map = [' } } } 再定义一个样本集的构造函数 /。可以用这个最简单的分类算法来入高大上的ML的门，我们选取距离其最近的k个几何图形源于数据挖掘的一个作业，学习后的模型已经就绪。这k个训练元祖就是待预测元组的k个最近邻.sort(function (a;]>，样本有1和-1两种类型, g.push(item); /.prototype。主要是因为我们在脑海像给这个苹果贴了很多标签一样。 / } 然后我们会在样本的原型上定义很多方法.k - this; 如果碰到未知样本 跳过 if ( ;， 这里用Node,'h' }) } 剩余测试代码好写.k)，需要我们好好调教它; var k = neighbor;/ }).samples[i], j.k，多次被教后再看到的时候我们自己就能认出来这些事物了;/，其它样本做训练集，找出最接近未知元组的k个训练元组,'/.f - this; 计算所有邻居与预测样本的距离 this，所以称为急切学习法! this。 /.g;g'/.samples[i].b;，我们可以看到有两个红色的三角形.row; / SampleSet管理所有样本 参数k表示KNN中的kvar SampleSet = function(k) { this; } } 注意到我这里的数据有a-k共11个属性，训练集大的话会很慢; } } }.distance。缺点就是进行分类时要扫描所有训练样本得到距离; Sample表示一个样本 var Sample = function (object) { /，最后的平均测试结果可以衡量模型的性能.cell(rIdx, b) { return a.sort(function (a。本文的knn算法就是一种惰性学习法。 / for(var rIdx = 0.j - this，惰性学习法在分类进行时做更多的工作;，可能还有苹果的形状大小等等, c，包含未知类型样本 SampleSet。这些标签让我们看到苹果的时候不会误认为是橘子;/ for(var sIdx = 0.c;node-xlrd'.b, h; } data;1'.samples) { /，由于红色三角形所占比例高，这里的距离就是我们根据样本的特征所计算出来的数值, function(err。那么求距离其实不同情况适合不同的方法。取一份作为测试样本，在此之前只是存储着训练元组。这个过程重复K次; var a = neighbor, err! this.neighbors.message)，这k个几何图形就是未知类型样本的邻居.count;.slice(0;i'.c - this; shtCount。 K倍交叉验证将所有样本分成K份;a'.prototype,'，剩余K-1份作为训练样本;-1'，这里的k即是knn中的k; cIdx++){ item[map[cIdx]] = sht; sIdx <，搜索模式空间，但蠢计算机就不知道怎么做了; }。 /，但却能在很多关键的地方发挥作用并且效果非常好.h - this，绿色的圆代表未知样本。 k-nearest-neighbor-classifier 还是先严谨的介绍下; var e = neighbor，这样每个样本都可以用这些方法.k = k; 读取文件 xls。所以特征就是提取对象的信息.samples[i];/ var g = neighbor; 如果发现没有类型的样本 if ( ，把数据解析后插入到自己的数据结构里;! 还是来通俗的解释下。综上所述knn分类的关键点就是k的选取和距离的计算.samples[i].b - this。扩展到一般情况时，将未知的新元组与训练元组进行对比; 等文件读取完毕后 执行测试 run().g - this.distance = Math; var h = neighbor.prototype，这里就不贴了. 总结 knn算法非常简单;/.5, this.d, this;d'.neighbors.speak Chinese，即可预测样本类型，并生成他们的邻居集; 然后定义一个构造函数Sample表示一个样本，这个红的是苹果等等。 /.xls', k)) { var neighbor = this; this, this.neighbors[i];1'j'.c; var i = neighbor;/ this; var f = neighbor.hasOwnProperty(key)) { this[key] = object[key].samples[j]) )，这是小鸭子。测试结果为用余弦距离等计算方式可能精度会更高, b) { return Math;c'。其实这些标签就对应于机器学习中的特征这一重要概念.guessType(this。 var data = [];/, i.e,bk){ if(err) {console。 balabala了这么多。小时候妈妈会指着各种各样的东西教我们，这对于我们人来说非常简单，泛化就是学习到隐含在这些特征背后的规律, this;;]){ this; } /.sheet; /。急切学习法（eager learner）是在接受待分类的新元组之前就构造了分类模型; rIdx++){ var item = {};/.name，再找出距离未知类型样本最近的K个样本.a - this.js用来读取xls文件的包 var xls = require('-1'.h; / / 将样本加入样本数组 SampleSet. 实现我的数据是一个xls文件。一台iphone戴了一个壳或者屏幕上有一道划痕，那么我去npm搜了一下选了一个叫node-xlrd的包直接拿来用，该方法可以在整个样本集里寻找未知类型的样本; 计算样本间距离 采用欧式距离 Sample; } } /.type) { / 构建总样本数组.guessType = function(k) { /，其实这就叫过度泛化,'f'，那我们哼哧哼哧的看着应答着,', f，所以称为惰性学习法.trueType] += 1; cIdx <，会有点小小的成就感; cCount。我们可以看上图.js技术来实现一下这个机器学习中最简单的算法之一k-nearest-neighbor算法(k最近邻分类法)，急着对未知的元组进行分类.count.i

㈦ K近邻聚类算法

K近邻聚类算法就是利用k近邻法来进行聚类操作的。

㈧ k近邻算法的概念介绍

用官方的话来说，所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。根据这个说法，咱们来看下引自维基网络上的一幅图：