K-NearestNeighborClassificationAlgorithm

inMachineLearningwithNode.js1.简介来源于一份数据挖掘的工作。这里使用Node.js来实现机器学习中最简单的算法之一，k-nearest-neighboralgorithm（k近邻分类法）。k-nearest-neighbor-classifier仍然是一个严谨的介绍。渴望学习者在接受要分类的新元组之前构建分类模型。学习到的模型准备好并渴望对未知的元组进行分类，因此称为渴望学习，如决策树Induction、贝叶斯分类等都是渴望学习方法的例子。懒惰的学习者正好相反。直到给出一个新的待分类元组，它才开始基于训练元组建立分类模型。在此之前，它只存储训练元组，因此被称为惰性学习方法，惰性学习方法在分类过程中做更多的工作。本文中的knn算法是一种惰性学习方法，广泛应用于模式识别。knn基于类比学习，将未知的新元组与训练元组进行比较，搜索模式空间，找到与未知元组最接近的k个训练元组，其中k为knn中的k。k个训练元组是要预测的元组的k个最近邻。我balabala那么多，是不是有些同学想喊出来..说中文！下面简单的解释一下，再看看上面的理论，应该就明白很多了。小时候，妈妈会指着各种东西教我们，这是小鸭子，这个红的是苹果等等，然后我们看着它回答，当我们教了很多之后看到它时很多时候，我们自己都能认出这些东西。主要是因为我们在脑海里给这个苹果贴上了很多标签，不仅仅是颜色的标签，还有苹果的形状大小等等。这些标签帮助我们不把苹果误认为橘子。事实上，这些标签对应着机器学习中特征的重要概念，训练我们识别的过程对应着泛化的概念。iphone戴壳或者屏幕有划痕，我们还是可以识别的，这对我们来说很简单，但是笨电脑不知道怎么做，我们需要调试它，当然可以'tOver-tuning2333，过调到把其他手机识别成iphone是不好的，其实这叫over-generalization。因此，特征是提取对象的信息，泛化是学习这些特征背后的规律，对新的输入做出合理的判断。我们可以看上图，绿色圆圈代表未知样本，我们选择k个最近的几何图形，这k个几何图形是未知类型样本的邻居，如果k=3，我们可以看到有两个redTriangle，有一个蓝色的三个正方形，因为红色三角形的比例高，所以我们可以判断未知样本类型是红色三角形。当扩展到一般情况时，这里的距离就是根据样本的特征计算出来的值，然后找到距离未知类型样本最近的K个样本来预测样本类型。那么，求距离其实在不同的情况下适用不同的方法。我们在这里使用欧氏距离。综上所述，knn分类的关键在于k的选取和距离的计算。2.意识到我的数据是一个xls文件，于是在npm上搜索了一下，选择了一个叫node-xlrd的包直接使用。//node.js读取xls文件使用的包varxls=require('node-xlrd');然后直接看文档复制实例，解析数据插入到自己的数据结构中即可。vardata=[];//将文件中的数据映射到样本的属性上varmap=['a','b','c','d','e','f','g','h','i','j','k'];//读取文件xls.open('data.xls',function(err,bk){if(err){console.log(err.name,err.message);return;}varshtCount=bk.sheet.count;for(varsIdx=0;sIdxtypes['-1']){this.type='1';}else{this.type='-1';}}注意到我这里的数据从a到k一共有11个属性，样本有两种类型：1和-1。使用truetype和type预测样本类型，对比判断分类是否成功。最后，在样本集上定义一个原型方法，该方法可以在整个样本集中找到未知类型的样本，并生成它们的邻居集，调用未知样本原型上的方法计算邻居到它的距离，将所有的邻居按距离排序，最后猜出类型。//构建一个总样本数组，包括未知类型的样本SampleSet.prototype.determineUnknown=function(){/**一旦找到未知类型的样本，所有已知样本*被克隆为未知样本的邻居序列.*这样做的原因是我们需要计算这个未知样本和所有已知样本之间的距离。*/for(variinthis.samples){//如果找到没有类型的样本if(!this.samples[i].type){//初始化未知样本的邻居this.samples[i].neighbors=[];//为(varjinthis.samples)生成邻居集{//如果遇到未知样本则跳过if(!this.samples[j].type)continue;this.samples[i].neighbors.push(newSample(this.samples[j]));}//计算所有邻居和预测样本之间的距离this.samples[i].measureDistances(this.a,this.b,this.c,this.d,this.e,this.f,this.g,this.h,这个.k);//按距离对所有邻居进行排序this.samples[i].sortByDistance();//猜测预测样本类型this.samples[i].guessType(this.k);}}};最后分别计算10折交叉验证和留一法交叉验证的准确率。留一的方法就是每次只留一个样本作为测试集，其他样本作为训练集。K-foldcross-validation将所有样本分成K份，一般均分。取一个作为测试样本，剩下的K-1个作为训练样本。这个过程重复K次，最后的平均测试结果可以衡量模型的性能。k折验证的时候，定义了一个方法，先把数组打乱，然后随机排列。//辅助函数随机排列数组中的元素functionruffle(array){array.sort(function(a,b){returnMath.random()-0.5;})}剩下的测试代码很容易写吧，这里就不写贴了。测试结果表明，计算邻居到未知样本的距离主要有欧几里德距离、余弦距离、汉明距离、曼哈顿距离等，在这种情况下，余弦距离等计算方法可能具有更高的精度。3.总结knn算法很简单，但是可以在很多关键的地方起作用，效果很好。缺点是分类时需要扫描所有的训练样本得到距离。如果训练集很大，会很慢。看似高深的机器学习，其实是基于计算机科学、统计学、数学的一些实现。相信通过这个最简单的入门算法，我们可以对机器学习有一点感悟和体会。完整的代码和文件在：https://github.com/Lunaticf/D...参考：http://burakkanber.com/blog/m...