K-近邻分类算法-题解

这个KNN算法应该是基础入门的了，容易出考题。

首先得明确K是什么？

K指的是距离需要判决的点最近的K个点，一般是奇数，为了投票使用。

K = 1， 最近的一个

K = 3， 最近的三个，然后投票

K = 5， 最近的五个，然后投票

K最大可以是样本的个数。

一般考题应该用不上算距离，那太复杂了。

看个题目：

我们在广场上搜集了一批群众的数据，具体如下:

年龄 喜好

20 苹果

21 苹果

21 香蕉

22 苹果

23 香蕉

请问老王今年216岁，他喜好是如何的？

老师说要用K近邻

K = 1， 216离22最近，所以是苹果；

K = 3， 21，21，22， 三者投票，还是苹果；

K = 5， 全部5项投票，还是苹果。

综上，所以老王喜好苹果。

做题目，做练习依然是学习的不二法门

  从理论基础、手写数字识别算法、手写数字识别实例等角度介绍K近邻算法。

   K近邻算法的本质是将指定对象根据已知特征值分类。

  例如，看到一对父子，一般情况下，通过判断他们的年龄，能够马上分辨出哪位是父亲，哪位是儿子。这是通过年龄属性的特征值来划分的。

  上述例子是最简单的根据单个特征维度做的分类，在实际场景中，情况可能更复杂，有多个特征维度。

  例如，为一段运动视频分类，判断这段视频是乒乓球比赛还是足球比赛。

  为了确定分类，需要定义特征。这里定义两个特征，一个是运动员“挥手”的动作，另一个是运动员“踢脚”的动作。当然，我们不能一看到“挥手”动作就将视频归类为“乒乓球比赛”，因为我们知道某些足球运动员习惯在运动场上通过挥手来跟队友进行交流。同样，我们也不能一看到“踢脚”动作就将视频归类为“足球比赛”，因为有些乒乓球运动员会通过“踢脚”动作来表达自己的感情。

  我们分别统计在某段特定时间内，视频中“挥手”和“踢脚”动作的次数，发现如下规律：

● 在乒乓球比赛的视频中，“挥手”的次数远多于“踢脚”的次数。

● 在足球比赛的视频中，“踢脚”的次数远多于“挥手”的次数。

根据对一组视频的分析，得到如表20-1所示的数据。

为了方便观察，将上述数据绘制为散点图，如图20-1所示。

从图20-1中可以看到，数据点呈现聚集特征：

● 乒乓球比赛视频中的数据点聚集在x轴坐标为[3000, 5000], y轴坐标为[1,500]的区域。

● 足球比赛视频中的数据点聚集在y轴坐标为[3000, 5000], x轴坐标为[1,500]的区域。

  此时，有一个视频Test，经过统计得知其中出现2000次“挥手”动作，100次“踢脚”动作。如果在图20-1中标注其位置，可以发现视频Test的位置最近的邻居是乒乓球比赛视频，因此可判断该视频是乒乓球比赛视频。

  上面的例子是一个比较极端的例子，非黑即白，而实际的分类数据中往往参数非常多，判断起来也不会如此简单。因此，为了提高算法的可靠性，在实施时会取k个近邻点，这k个点中属于哪一类的较多，然后将当前待识别点划分为哪一类。为了方便判断，k值通常取奇数，这和为了能得到明确的投票结果通常将董事会成员安排为奇数的道理是一样的。

  例如，已知某知名双胞胎艺人A和B长得很像，如果要判断一张图像T上的人物到底是艺人A还是艺人B，则采用K近邻算法实现的具体步骤如下：

以上所述就是K近邻算法的基本思想。

11 Cover和Hart在1968年提出了最初的邻近算法。

12 分类(classification)算法。

13 输入基于实例的学习(instance-based learning),或则是懒惰学习(lazy learning)。-----（为什么叫懒惰学习了？因为在处理大量的训练集的时候并没有建立大量的模型，而是刚开始的时候对于一个未知的实例进行归类的时候我们会根据已知类型实例的比较来进行归类）

目的：求未知的**属于什么类型？ ----可以根据实例的特征值来进行归类（分类）。

31 步骤：

33 举例:

41 算法优点

42 算法缺点

注意：在选择k的时候，一般k为奇数，因为保证了结果相等的出现情况被排除了，如果选择偶数，可能会出现结果相等

考虑距离，根据距离加上权重（ 比如: 1/d (d: 距离）---表示加权重来计算大小）

源于数据挖掘的一个作业， 这里用Nodejs技术来实现一下这个机器学习中最简单的算法之一k-nearest-neighbor算法(k最近邻分类法)。

k-nearest-neighbor-classifier

还是先严谨的介绍下。急切学习法（eager learner）是在接受待分类的新元组之前就构造了分类模型，学习后的模型已经就绪，急着对未知的元组进行分类，所以称为急切学习法，诸如决策树归纳，贝叶斯分类等都是急切学习法的例子。惰性学习法（lazy learner）正好与其相反，直到给定一个待接受分类的新元组之后，才开始根据训练元组构建分类模型，在此之前只是存储着训练元组，所以称为惰性学习法，惰性学习法在分类进行时做更多的工作。

本文的knn算法就是一种惰性学习法，它被广泛应用于模式识别。knn基于类比学习，将未知的新元组与训练元组进行对比，搜索模式空间，找出最接近未知元组的k个训练元组，这里的k即是knn中的k。这k个训练元祖就是待预测元组的k个最近邻。

balabala了这么多，是不是某些同学想大喊一声speak Chinese! 还是来通俗的解释下，然后再来看上面的理论应该会明白很多。小时候妈妈会指着各种各样的东西教我们，这是小鸭子，这个红的是苹果等等，那我们哼哧哼哧的看着应答着，多次被教后再看到的时候我们自己就能认出来这些事物了。主要是因为我们在脑海像给这个苹果贴了很多标签一样，不只是颜色这一个标签，可能还有苹果的形状大小等等。这些标签让我们看到苹果的时候不会误认为是橘子。其实这些标签就对应于机器学习中的特征这一重要概念，而训练我们识别的过程就对应于泛化这一概念。一台iphone戴了一个壳或者屏幕上有一道划痕，我们还是能认得出来它，这对于我们人来说非常简单，但蠢计算机就不知道怎么做了，需要我们好好调教它，当然也不能过度调教2333，过度调教它要把其他手机也认成iphone那就不好了，其实这就叫过度泛化。

所以特征就是提取对象的信息，泛化就是学习到隐含在这些特征背后的规律，并对新的输入给出合理的判断。

我们可以看上图，绿色的圆代表未知样本，我们选取距离其最近的k个几何图形，这k个几何图形就是未知类型样本的邻居，如果k=3，我们可以看到有两个红色的三角形，有一个蓝色的三正方形，由于红色三角形所占比例高，所以我们可以判断未知样本类型为红色三角形。扩展到一般情况时，这里的距离就是我们根据样本的特征所计算出来的数值，再找出距离未知类型样本最近的K个样本，即可预测样本类型。那么求距离其实不同情况适合不同的方法，我们这里采用欧式距离。

综上所述knn分类的关键点就是k的选取和距离的计算。

2 实现

我的数据是一个xls文件，那么我去npm搜了一下选了一个叫node-xlrd的包直接拿来用。

// nodejs用来读取xls文件的包

var xls = require('node-xlrd');

然后直接看文档copy实例即可，把数据解析后插入到自己的数据结构里。

var data = [];// 将文件中的数据映射到样本的属性var map = ['a','b','c','d','e','f','g','h','i','j','k'];// 读取文件

xlsopen('dataxls', function(err,bk){

if(err) {consolelog(errname, errmessage); return;}

var shtCount = bksheetcount;

for(var sIdx = 0; sIdx < shtCount; sIdx++ ){

var sht = bksheets[sIdx],

rCount = shtrowcount,

cCount = shtcolumncount;

for(var rIdx = 0; rIdx < rCount; rIdx++){

var item = {};

for(var cIdx = 0; cIdx < cCount; cIdx++){

item[map[cIdx]] = shtcell(rIdx,cIdx);

}

datapush(item);

}

}

// 等文件读取完毕后 执行测试

run();

});

然后定义一个构造函数Sample表示一个样本，这里是把刚生成的数据结构里的对象传入，生成一个新的样本。

// Sample表示一个样本

var Sample = function (object) {

// 把传过来的对象上的属性克隆到新创建的样本上

for (var key in object)

{

// 检验属性是否属于对象自身

if (objecthasOwnProperty(key)) {

this[key] = object[key];

}

}

}

再定义一个样本集的构造函数

// SampleSet管理所有样本 参数k表示KNN中的kvar SampleSet = function(k) {

thissamples = [];

thisk = k;

};

// 将样本加入样本数组

SampleSetprototypeadd = function(sample) {

thissamplespush(sample);

}

然后我们会在样本的原型上定义很多方法，这样每个样本都可以用这些方法。

// 计算样本间距离 采用欧式距离

SampleprototypemeasureDistances = function(a, b, c, d, e, f, g, h, i, j, k) {

for (var i in thisneighbors)

{

var neighbor = thisneighbors[i];

var a = neighbora - thisa;

var b = neighborb - thisb;

var c = neighborc - thisc;

var d = neighbord - thisd;

var e = neighbore - thise;

var f = neighborf - thisf;

var g = neighborg - thisg;

var h = neighborh - thish;

var i = neighbori - thisi;

var j = neighborj - thisj;

var k = neighbork - thisk;

// 计算欧式距离

neighbordistance = Mathsqrt(aa + bb + cc + dd + ee + ff + gg + hh + ii + jj + kk);

}

};

// 将邻居样本根据与预测样本间距离排序

SampleprototypesortByDistance = function() {

thisneighborssort(function (a, b) {

return adistance - bdistance;

});

};

// 判断被预测样本类别

SampleprototypeguessType = function(k) {

// 有两种类别 1和-1

var types = { '1': 0, '-1': 0 };

// 根据k值截取邻居里面前k个

for (var i in thisneighborsslice(0, k))

{

var neighbor = thisneighbors[i];

types[neighbortrueType] += 1;

}

// 判断邻居里哪个样本类型多

if(types['1']>types['-1']){

thistype = '1';

} else {

thistype = '-1';

}

}

注意到我这里的数据有a-k共11个属性，样本有1和-1两种类型，使用truetype和type来预测样本类型和对比判断是否分类成功。

最后是样本集的原型上定义一个方法，该方法可以在整个样本集里寻找未知类型的样本，并生成他们的邻居集，调用未知样本原型上的方法来计算邻居到它的距离，把所有邻居按距离排序，最后猜测类型。

// 构建总样本数组，包含未知类型样本

SampleSetprototypedetermineUnknown = function() {

for (var i in thissamples)

{

// 如果发现没有类型的样本

if ( ! thissamples[i]type)

{

// 初始化未知样本的邻居

thissamples[i]neighbors = [];

// 生成邻居集

for (var j in thissamples)

{

// 如果碰到未知样本 跳过

if ( ! thissamples[j]type)

continue;

thissamples[i]neighborspush( new Sample(thissamples[j]) );

}

// 计算所有邻居与预测样本的距离

thissamples[i]measureDistances(thisa, thisb, thisc, thisd, thise, thisf, thisg, thish, thisk);

// 把所有邻居按距离排序

thissamples[i]sortByDistance();

// 猜测预测样本类型

thissamples[i]guessType(thisk);

}

}

};

最后分别计算10倍交叉验证和留一法交叉验证的精度。

留一法就是每次只留下一个样本做测试集，其它样本做训练集。

K倍交叉验证将所有样本分成K份，一般均分。取一份作为测试样本，剩余K-1份作为训练样本。这个过程重复K次，最后的平均测试结果可以衡量模型的性能。

k倍验证时定义了个方法先把数组打乱随机摆放。

// helper函数 将数组里的元素随机摆放

function ruffle(array) {

arraysort(function (a, b) {

return Mathrandom() - 05;

})

}

剩余测试代码好写，这里就不贴了。

测试结果为

用余弦距离等计算方式可能精度会更高。

3 总结

knn算法非常简单，但却能在很多关键的地方发挥作用并且效果非常好。缺点就是进行分类时要扫描所有训练样本得到距离，训练集大的话会很慢。

可以用这个最简单的分类算法来入高大上的ML的门，会有点小小的成就感。

以上就是关于K-近邻分类算法-题解全部的内容，包括:K-近邻分类算法-题解、K近邻算法的理论基础、最邻近规则分类（K-Nearest Neighbor）KNN算法（七）等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！