用js进行机器学习(1)-KNN

echosoar 原创发表于 2019/01/08 21:10:16

前言

虽说就目前而言机器学习的热度有所下降,但是对于一名程序员来说,掌握一些基础的机器学习算法和只是也是很有必要的,市面上目前大部分的机器学习方面的教程都是基于python,而且大部分js的开发者来说对算法的了解并不深入,因此计划写一系列使用js这门语言来实现各种机器学习算法的文章,这也算是对我自己知识的一种积累。当然就我自身而言对于算法了解的也很浅薄,所以如果文章中有所疏漏,欢迎指正。
对于机器学习的大图可以去 github - homemade-machine-learning 了解一下。

有监督学习与泛化

举一个很简单的例子,我们通常对一个身高170cm的男生的感觉,体重60kg觉得看着挺舒服的,体重50kg就觉得有点瘦了,如果体重有80kg,那就觉得这个人很胖,上面的这些对比数据已经存在与我们的认知中了,当出现一个身高175cm,体重65kg的男生时,我们就会依照我们脑海中曾经判断过的数据,基于我们的的认知对这个人的胖瘦进行对比,看他和哪个分类更相符和。
上面例子的这个过程中,我们其实最开始是有一个认知的学习过程,这就像是小时候妈妈指着一只鸭子和我们说:这种腿在身体后方,白色的羽毛,走路摇摇摆摆,嘴大脖子短,能在水里游的动物就是鸭子。这个时候我们就有了这样的一种认知,所以当我们见到一只鸡的时候一看嘴巴不像,再看走路的姿势也不像,就知道了这不是一只鸭子。然而有一天我们又发现了一种动物,除了颜色是灰色的外其他的都像鸭子,这个时候我们问妈妈这是什么动物,也不是鸭子啊,妈妈又和我们说灰色羽毛的也是鸭子,叫做麻鸭,这个时候我们的认知有多了一些,就在这样的过程中我们最终学会了如何辨别什么是鸭子。这就是所谓的"泛化",在有监督学习(Supervised Learning)算法中是一个非常重要的概念。
如果我们对于一项事物的“泛化”程度不是恰到好处,以偏概全,那么就会对最终的认知结果产生重大的影响。所以说在学习的时候要先确定好基于物体的哪些特征来进行学习,比如判断一个人胖或瘦肯定不能只看体重,而是要身高和体重一起来看,如果要更细致那还要看性别,因为胖瘦在男女性别上也有很大的差异(当然对于女生来说每个人无论多瘦都会觉得自己胖)。

KNN

KNN是最近邻算法(k-nearest-neighbor)的缩写,这也是最基础最简单的一个算法,通过一系列有明确分类的值对一个随机值识别出属于哪个分类。 对于算法原理简单的说,把一个随机值的各种可以量化为数字的特征与已经标注好分类的值的相应特征去计算欧式距离,在距离最近的前K个值里面,哪个分类占比最多,那么这个随机值就属于哪个分类。
还是用胖瘦的这个例子,我们根据BMI指数有如下一些数据:
152cm 44kg 偏瘦
152cm 52kg 标准
152cm 60kg 偏胖
156cm 46kg 偏瘦
156cm 53kg 标准
156cm 63kg 偏胖
160cm 47kg 偏瘦
160cm 55kg 标准
160cm 61kg 偏胖
164cm 49kg 偏瘦
164cm 56kg 标准
164cm 64kg 偏胖
168cm 50kg 偏瘦
168cm 58kg 标准
168cm 72kg 偏胖
172cm 51kg 偏瘦
172cm 60kg 标准
172cm 75kg 偏胖
176cm 52kg 偏瘦
176cm 63kg 标准
176cm 78kg 偏胖
180cm 55kg 偏瘦
180cm 66kg 标准
180cm 80kg 偏胖
184cm 60kg 偏瘦
184cm 70kg 标准
184cm 82kg 偏胖
188cm 61kg 偏瘦
188cm 73kg 标准
188cm 85kg 偏胖
这个时候有一个身高176.5cm,体重79kg的男生,那么就可以计算基于体重和身高这两个维度的欧式距离与哪个分类更近。 在进行计算之前我们要先把这两个维度进行归一化处理,来保证每个维度对结果的影响是一样的。归一化的操作就是找到每个维度最大值与最小值的差距,用当前值与最小值的差去除范围得到:
let highRange = high.max - high.min;
let nodeHigh = (node.high - high.min) / highRange;
然后计算与邻居节点基于两个维度的欧式距离:
let distHigh = nodeHigh - neighborHigh;
let distWeight = nodeWeight - neighborWeight;
let distance = Math.sqrt(distHigh * distHigh + distWeight * distWeight);
计算后的结果是
176cm 78kg 偏胖 distance: 0.028067512041297236
180cm 80kg 偏胖 distance: 0.10023494645804738
172cm 75kg 偏胖 distance: 0.1585658978529981
184cm 82kg 偏胖 distance: 0.22080927008701867
168cm 72kg 偏胖 distance: 0.29137222357926673
184cm 70kg 标准 distance: 0.3026357242379613
180cm 66kg 标准 distance: 0.33164371860731146
188cm 73kg 标准 distance: 0.351369573242699
188cm 85kg 偏胖 distance: 0.351369573242699
176cm 63kg 标准 distance: 0.390490978929612
172cm 60kg 标准 distance: 0.47997721106422075
164cm 64kg 偏胖 distance: 0.5043928737299355
184cm 60kg 偏瘦 distance: 0.5080904456086193
188cm 61kg 偏瘦 distance: 0.5429430617619587
168cm 58kg 标准 distance: 0.563996719618783
180cm 55kg 偏瘦 distance: 0.5933846502254793
160cm 61kg 偏胖 distance: 0.6346746092868966
176cm 52kg 偏瘦 distance: 0.6586830311309729
164cm 56kg 标准 distance: 0.6597400293647216
156cm 63kg 偏胖 distance: 0.6903312818491428
172cm 51kg 偏瘦 distance: 0.6942723198676755
160cm 55kg 标准 distance: 0.7434531774589652
168cm 50kg 偏瘦 distance: 0.7456848521922205
164cm 49kg 偏瘦 distance: 0.8099128776994201
152cm 60kg 偏胖 distance: 0.8233522862897257
156cm 53kg 标准 distance: 0.8522960505012772
160cm 47kg 偏瘦 distance: 0.9051136160768987
152cm 52kg 标准 distance: 0.9470091332520765
156cm 46kg 偏瘦 distance: 0.985949110612372
152cm 44kg 偏瘦 distance: 1.0917365805369899
取K为3,也就是取距离最近的前三个数据来判断,其中占比最多的分类是偏胖,那么也就可以将身高176.5cm,体重79kg的男生认为是偏胖了。 下面是代码:
class Node {
  constructor(obj) {
    obj && this.initByObj(obj);
  }

  initByObj(obj) {
    for (var key in obj) {
      this[key] = obj[key];
    }
  }
}

class NodeList {
  constructor(k) {
    this.nodes = [];
    this.k = k; // k为有多少个邻居表决决定,比如说k为3,即由距离最近的3个邻居中占多数的进行表决
  }

  // 遍历出来nodes中含有哪些数字类型的值
  findParams() {
    if (!this.nodes[0]) return;
    this.range = Object.keys(this.nodes[0]).filter(key => {
      if (typeof this.nodes[0][key] == 'number') return true;
      return false;
    }).map(key => {
      return { key, min: this.nodes[0][key], max: this.nodes[0][key] };
    });
  }

  // 计算每一个节点参数的范围
  calculateRanges() {
    for (let i in this.nodes) {
      for (let j in this.range) {
        let key = this.range[j].key;
        if (this.nodes[i][key] == null) continue;
        if (this.nodes[i][key] < this.range[j].min) {
          this.range[j].min = this.nodes[i][key];
        }
        if (this.nodes[i][key] > this.range[j].max) {
          this.range[j].max = this.nodes[i][key];
        }
      }
    }
  }

  add(node) {
    this.nodes.push(node);
  }

  guess(node) {
    this.calculateRanges();
    node.neighbors = this.nodes.map(node => {
      return new Node(node);
    }).map(neighbor => {
      let distance = 0;
      this.range.map(range => {
        let rangeDelta = range.max - range.min;
        if (node[range.key] == null || neighbor[range.key] == null || !rangeDelta) return;
        let temDistance = (neighbor[range.key] - node[range.key]) / rangeDelta;
        distance += temDistance * temDistance;
      });
      neighbor.distance = Math.sqrt(distance);
      return neighbor;
    }).sort((a, b) => {
      return a.distance - b.distance;
      });

    let types = {};
    for (let i in node.neighbors.slice(0, this.k)) {
      var neighbor = node.neighbors[i];
      if (!types[neighbor.type] ) {
        types[neighbor.type] = 0;
      }
      types[neighbor.type] += 1;
    }

    let guess = {type: false, count: 0};
    for (let type in types) {
      if (types[type] > guess.count) {
        guess.type = type;
        guess.count = types[type];
      }
    }
    node.type = guess.type;

    this.add(node);
   
  }
}


let inData = [
  { high: 152, weight: 44, type: "偏瘦" },
  { high: 152, weight: 52, type: "标准" },
  { high: 152, weight: 60, type: "偏胖" },
  { high: 156, weight: 46, type: "偏瘦" },
  { high: 156, weight: 53, type: "标准" },
  { high: 156, weight: 63, type: "偏胖" },
  { high: 160, weight: 47, type: "偏瘦" },
  { high: 160, weight: 55, type: "标准" },
  { high: 160, weight: 61, type: "偏胖" },
  { high: 164, weight: 49, type: "偏瘦" },
  { high: 164, weight: 56, type: "标准" },
  { high: 164, weight: 64, type: "偏胖" },
  { high: 168, weight: 50, type: "偏瘦" },
  { high: 168, weight: 58, type: "标准" },
  { high: 168, weight: 72, type: "偏胖" },
  { high: 172, weight: 51, type: "偏瘦" },
  { high: 172, weight: 60, type: "标准" },
  { high: 172, weight: 75, type: "偏胖" },
  { high: 176, weight: 52, type: "偏瘦" },
  { high: 176, weight: 63, type: "标准" },
  { high: 176, weight: 78, type: "偏胖" },
  { high: 180, weight: 55, type: "偏瘦" },
  { high: 180, weight: 66, type: "标准" },
  { high: 180, weight: 80, type: "偏胖" },
  { high: 184, weight: 60, type: "偏瘦" },
  { high: 184, weight: 70, type: "标准" },
  { high: 184, weight: 82, type: "偏胖" },
  { high: 188, weight: 61, type: "偏瘦" },
  { high: 188, weight: 73, type: "标准" },
  { high: 188, weight: 85, type: "偏胖" }
];

let nodeList = new NodeList(3);

inData.map(data => {
  nodeList.add(new Node(data));
});

nodeList.findParams();
nodeList.guess({ high: 176.5, weight: 79});