用Node.js实现机器学习中的K最近邻分类算法

1. 简介

源于数据挖掘的一个作业, 这里用Node.js来实现一下这个机器学习中最简单的算法之一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那就不好了,其实这就叫过度泛化。

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

用Node.js实现机器学习中的K最近邻分类算法

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

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

2. 实现

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

    // node.js用来读取xls文件的包    var xls = require('node-xlrd'); 

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

var data = http://www.netofthings.cn/JieJueFangAn/2016-11/[];'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;}    var shtCount = bk.sheet.count;    for(var sIdx = 0; sIdx < shtCount; sIdx++ ){        var sht = bk.sheets[sIdx],            rCount = sht.row.count,            cCount = sht.column.count;        for(var rIdx = 0; rIdx < rCount; rIdx++){            var item = {};            for(var cIdx = 0; cIdx < cCount; cIdx++){                item[map[cIdx]] = sht.cell(rIdx,cIdx);            }            data.push(item);        }    }    // 等文件读取完毕后 执行测试    run();});

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

    // Sample表示一个样本    var Sample = function (object) {        // 把传过来的对象上的属性克隆到新创建的样本上        for (var key in object)        {            // 检验属性是否属于对象自身            if (object.hasOwnProperty(key)) {                this[key] = object[key];            }        }    }

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

// SampleSet管理所有样本 参数k表示KNN中的kvar SampleSet = function(k) {     this.samples = [];    this.k = k;};// 将样本加入样本数组SampleSet.prototype.add = function(sample) {    this.samples.push(sample);}