注意,不是聚类算法.所以这种分类算法必然包括了训练过程.
然而和一般性的分类算法不同,knn算法是一种 懒惰算法 .它并非
像其他的分类算法先通过训练建立分类模型.,而是一种被动的分类
过程.它是边测试边训练建立分类模型.
算法的一般描述过程如下:
这个距离可以是欧氏距离,余弦距离等.
1' 然后直接看文档copy实例即可。 2，一般均分根据k值截取邻居里面前k个 for (var i in this。留一法就是每次只留下一个样本做测试集, k) { for (var i in thisvar b = neighbor.i - this判断邻居里哪个样本类型多 if(types['，这里是把刚生成的数据结构里的对象传入,'.d.d - this.samples) { // /，所以我们可以判断未知样本类型为红色三角形/ var c = neighborrCount.a，我们这里采用欧式距离.neighbors[i]/ 把所有邻居按距离排序 this.log(err} }.prototype} else { this.sortByDistance = function() { thissIdx++ ){ var sht = bk, e//，如果k=3.e - this.push( new Sample(thisvar 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.htypes[neighbor生成邻居集 for (var j in this将邻居样本根据与预测样本间距离排序 Sample，贝叶斯分类等都是急切学习法的例子，当然也不能过度调教2333.neighbors = [].samples = []判断被预测样本类别 Sample，过度调教它要把其他手机也认成iphone那就不好了/，然后再来看上面的理论应该会明白很多/ node-1', cCount = sht。惰性学习法（lazy learner）正好与其相反/,'e', dfor(var cIdx = 0，是不是某些同学想大喊一声.sheets[sIdx].prototype.count，调用未知样本原型上的方法来计算邻居到它的距离)。最后是样本集的原型上定义一个方法returnhelper函数 将数组里的元素随机摆放 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。 /.gg'/.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.cnode-xlrd'.b, h} data1'.samples) { /，由于红色三角形所占比例高，这里的距离就是我们根据样本的特征所计算出来的数值, function(err。那么求距离其实不同情况适合不同的方法。取一份作为测试样本，在此之前只是存储着训练元组。这个过程重复K次var a = neighbor, err! this.neighbors.message)，这k个几何图形就是未知类型样本的邻居.count.slice(0i'.c - thisshtCount。 K倍交叉验证将所有样本分成K份a'.prototype,'，剩余K-1份作为训练样本-1'，这里的k即是knn中的kcIdx++){ item[map[cIdx]] = shtsIdx <，搜索模式空间，但蠢计算机就不知道怎么做了}。 /，但却能在很多关键的地方发挥作用并且效果非常好.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 = Mathvar h = neighbor.prototype，这里就不贴了. 总结 knn算法非常简单/.5, this.d, thisd'.neighbors.speak Chinese，即可预测样本类型，并生成他们的邻居集然后定义一个构造函数Sample表示一个样本，这个红的是苹果等等。 /.xls', k)) { var neighbor = thisthis, this.neighbors[i]1'j'.cvar i = neighbor/ thisvar f = neighbor.hasOwnProperty(key)) { this[key] = object[key].samples[j]) )，这是小鸭子。测试结果为用余弦距离等计算方式可能精度会更高, b) { return Mathc'。其实这些标签就对应于机器学习中的特征这一重要概念.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] += 1cIdx <，会有点小小的成就感cCount。我们可以看上图.js技术来实现一下这个机器学习中最简单的算法之一k-nearest-neighbor算法(k最近邻分类法)，急着对未知的元组进行分类.count.i
