使用Node.js如何实现K最近邻分类算法

源于数据挖掘的一个作业， 这里用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的门，会有点小小的成就感。

（1）简单，易于理解，易于实现，无需估计参数。

（2）训练时间为零。它没有显示的训练，不像其它有监督的算法会用训练集train一个模型（也就是拟合一个函数），然后验证集或测试集用该模型分类。KNN只是把样本保存起来，收到测试数据时再处理，所以KNN训练时间为零。

（3）KNN可以处理分类问题，同时天然可以处理多分类问题，适合对稀有事件进行分类。

（4）特别适合于多分类问题(multi-modal,对象具有多个类别标签)， KNN比SVM的表现要好。

（5）KNN还可以处理回归问题，也就是预测。

（6）和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感。

（1）计算量太大，尤其是特征数非常多的时候。每一个待分类文本都要计算它到全体已知样本的距离，才能得到它的第K个最近邻点。

（2）可理解性差，无法给出像决策树那样的规则。

（3）是慵懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢。

（4）样本不平衡的时候，对稀有类别的预测准确率低。当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。

（5）对训练数据依赖度特别大，对训练数据的容错性太差。如果训练数据集中，有一两个数据是错误的，刚刚好又在需要分类的数值的旁边，这样就会直接导致预测的数据的不准确。

需要一个特别容易解释的模型的时候。
比如需要向用户解释原因的推荐算法。

通过此次实验我了解了K近邻算法及其思路，该方法的思路是：如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。
所谓k近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例。

1、计算已知类别数据集中每个点与当前点的距离；
2、选取与当前点距离最小的K个点；
3、统计前K个点中每个类别的样本出现的频率；
4、返回前K个点出现频率最高的类别作为当前点的预测分类。
主要函数：

KNN利用数据在各个维度上的相关性对数据中的缺失值或者异常值进行填补和修正

本文中讨论的数据集是来源于分布于某地各站点测得的空气污染物浓度数值随着时间的变化记录，在某些地点或某些时刻存在数据缺失，而我们已知，在该批数据中，测点浓度值在 距离 和 时间 上呈现出相关性，即，空间距离越接近，时间越接近的测量点测得的数值也会越相关，所以可以使用KNN算法从经度、纬度和时间三个维度入手进行数据的处理
在上图中，我们没有获得某时刻目标点处的测量值 ，但我们可以获得其周围若干测量值情况 , , ,  ，这样我们便可使用已有数据对目标值c_x进行估计：
其中权重 与邻点与目标点的距离成反相关，如：
实际使用时可以自行定义权重与距离的关系

在使用KNN算法对数据进行填补时，需要对每条样本寻找其近邻点，所以我们首先需要计算不同样本之间的距离，这里可以使用sklearnneighbors中的NearestNeighbors来解决

nbrs = NearestNeighbors(n_neighbors, algorithm = 'ball_tree')fit(X)

distances, indices = nbrskneighbors(X)

获得了距离矩阵后我们便可以对每个样本寻找其与其他样本的距离，使用前面的公式便可计算出其对应的估计值 这里需要注意，样本距离是指样本在指定的维度上的欧式距离，样本在指定的维度上均满足距离和测量值上的相关性，比如我们可以把样本的经纬度和测量时间作为计算样本距离的维度 ，这样目标点周围那些空间距离越近、测量时间越接近的邻点测量值对目标点估计值 的影响就越大

这个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项投票，还是苹果。
综上，所以老王喜好苹果。

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

---