初探机器学习-用js玩一波KNN算法-逐梦个人博客

在这个互联网高度发的的新时代里，人工智能已经深入到我们生活的方方面面，AI智能音箱，扫地机器人等等，人工智能的衍生品在我们的生活中已经随处可见，机器学习必将是未来的一种发展趋势，作为这个时代里的程序员，我也想玩玩机器学习，用机器学习的思维来让我更方便的解决生活工作中的一些繁琐反复事情。本文主要介绍的是KNN算法，在开始介绍KNN算法之前我们先简单了解一下机器学习。

1、什么是机器学习？

机器学习是实现人工智能的一种途径，通过算法设计，让计算机能够白动地从数据中“学习”规律，并利用规律对未知数据进行预测。机器学习可以分为以下五个大类：

(1) 监督学习：从给定的训练数据集中学习出一个函数，当新的数据到来时，可以根据这个函数预测结果。监督学习的训练集要求是输人和输出，也可以说是特征和目标。训练集中的目标是由人标注的。常见的监督学习算法包括回归与分类。

(2) 无监督学习：无监督学习与监督学习相比，训练集没有人为标注的结果。常见的无监督学习算法有聚类等。

(3) 半监督学习：这是一"种介于监督学习与无监督学习之间的方法。

(4) 迁移学习：将已经训练好的模型参数迁移到新的模型来帮助新模型训练数据集。

(5 )增强学习：通过观察周围环境来学习。每个动作都会对环境有所影响，学习对象根据观察到的周围环境的反馈来做出判断。

2、什么是KNN算法？

KNN算法（K-Nearest Neighbor），又称K近邻算法，是数据挖掘分类技术中心最简单的算法之一，属于监督学习一类，其核心思想是以已知类别的样本作为参照，计算未知样本与所有已知样本的距离，从中选取与未知样本距离最近的K个已知样本，根据少数服从多数的投票法则，将未知样本与K个最邻近样本中所属类别占比较多的归为一类，从而判断未知样本的类别，通俗点讲就是“近朱者赤，近墨者黑”，通过你的邻居来对你做推断。

3、算法实现

一般做机器学习，用的比较多的语言可能是python，但是对于用惯了js的我来说，还是觉得js比较亲切，所以这里用js来实现KNN算法。这里给定的例子是通过一定数量的颜色点来推断一个点可能是什么颜色，具体描述如下：

建设我们我们一个颜色点数组points, 初始一系列的点，每个点都有自己的颜色，其数据接口如下：

const points = [
  {
    point: { x: 100, y: 200},
    color: '#f00'
  },
  {
    point: { x: 300, y: 100},
    color: '#00f'
  },
  ...
];

然后给点一个点A{x: 10, y: 10}, 通过points来判断点A可能是什么颜色。

之前我们讲了KNN的主要思想是通过你的邻居来推断你，这个过程我们称之为决策，所以要实现KNN算法我们需要先实现一个决策函数：

/*
  * @desc 决策
  * @param  {Object} current 待决策属性的值
  * @param  {Object} points 训练样本集
  * @param  {Object} inField 用于分类的输入值
  * @param  {Object} outField 用于分类的输出值
  * @param  {Number} k 用于选择最近邻的数目
  * @param  {Function} c 自定义比较函数
  * @return {Object}
  */

function decide(current, points, inField, outField, k, c) {
    var result = [];
    var knn = classify0(current, points, inField, outField, k, c);
    var dists = knn.dists;

    // 初始数据
    for (var i of knn.classify) {
        result.push({
            label: i,
            value: 0
        });
    }

    // 统计相同属性的邻居个数
    dists.map(function (item) {
        for (var i of result) {
            if (i.label === item.p[outField]) {
                i.value++;
            }
        }
    });

    // 根据同属性邻居个数做排序
    result.sort(function (a, b) {
        return b.value - a.value;
    });

    return { result: result[0].label, dists: dists };
}

上面的代码很简单，通过代码我们可以看出决策函数主要工作是统计分类数据中同属性邻居的命中次数，然后选择最大命中次数的邻居的属性来作为推断的结果。接下来的的关键点就是如何实现分类函数，我们具体如何实现呢？我们先直接放出代码然后再做解释：

/*
  * @desc 分类
  * @param  {Object} current 待决策属性的值
  * @param  {Object} points 训练样本集
  * @param  {Object} inField 用于分类的输入值
  * @param  {Object} outField 用于分类的输出值
  * @param  {Number} k 用于选择最近邻的数目
  * @param  {Function} c 自定义比较函数
  * @return {Object}
  */
function classify0(current, points, inField, outField, k, c) {
    var dists = [];//存放最接近的
    var classify = [];//分类标识

    // 根据输出属性的所有属性值对数据及做分类
    points.map(function (item) {
        if (classify.indexOf(item[outField]) < 0) classify.push(item[outField]);
        var result = {};
        result.p = item;
        result.d = c(current, item[inField]) ;
        dists.push(result);
    });

    // 通过自定义比较方法排序分类好的数据
    dists.sort(function (a, b) {//排序
        return a.d - b.d;
    });

    // 取出前k个满足条件的数据作决策
    const d = { dists: dists.slice(0, k), classify: classify };
 
    return d;
}

首先通过输出属性（比如我们要判断颜色那么就是color）的所有属性值给数据集分类，然后通过比较函数得出前k个满足条件的数据将次数据交给决策函数做决策, 最终得出结果。

比如这里我们需要判断A点的颜色，我们可以这样使用。

const color = decide(A, points, 'point', 'color', 3, (p1, p2) => {
  //根据欧几里得距离公式计算距离
   var d = Math.sqrt(Math.pow(p2.x - p1.x, 2) + Math.pow(p2.y - p1.y, 2));
   return d;
});

在线demo：http://demo.deanhan.cn/knn/

4、KNN算法的应用

上面讲完了KNN算法的实现，但是在实际开发中有什么应用呢？实际开发中也不会出现要根据数据集来判断点的颜色吧，确实，但是这只是一个例子，他有更好的应用场景，比如交友网站的对象推荐功能，手写识别，花系判别等等，有兴趣的朋友可以去搜索一下，好像是实验楼有现成的实验。

本文到此就结束了，后期本博客会更新更多更精彩实用的文章，敬请持续关注哦。