K最近邻算法KNN

简介

KNN（K- Nearest Neighbor）法即K最邻近法，最初由 Cover和Hart于1968年提出，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路非常简单直观：如果一个样本在特征空间中的K个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别

该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最邻近点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。另外还有一种 Reverse KNN法，它能降低KNN算法的计算复杂度，提高分类的效率

KNN算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分

算法步骤

准备数据，对数据进行预处理。
计算测试样本点（也就是待分类点）到其他每个样本点的距离
对每个距离进行排序，然后选择出距离最小的K个点
对K个点所属的类别进行比较，根据少数服从多数的原则，将测试样本点归入在K个点中占比最高的那一类

特征抽取

使用毕达哥拉斯公式计算A和B的相似性（距离），值越小，相似性越大

回归

代码

原理上挺简单的，所以没解释，直接上代码，包含两个函数，一个毕达哥拉斯公式，一个KNN算法

// 毕达哥拉斯  Math.sqrt((x1-x2)² + (y1 - y2)²)
// 传参：目标对象1，目标对象2，是否返回详细结果（默认否）
function pythagoras(obj1, obj2, returnDetail = false) {
  let res = [];
  let common = [];

  for (const key in obj1) {
    if (obj2[key]) {
      res.push(Math.pow(parseFloat(obj1[key]) - parseFloat(obj2[key]), 2)); //差值取平方
      common.push(key);
    }
  }
  res = Math.sqrt(res.reduce((cur, next) => (cur += next), 0)).toFixed(2); //累加取平方根且保留两位小数

  if (returnDetail) return { res, common };
  return res;
}

// 算法-KNN-毕达哥拉斯比较距离
// 传参：对象集合，当前对象，是否返回详细结果（默认否）
function kNN(objs, newObj, returnDetail = false) {
  let allDistance = []; //存储所有距离
  let minDistance = Number.MAX_VALUE; //存储最小距离,默认js能读的最大数值
  let minObjName; //存储最小对象名

  for (const key in objs) {
    let res = pythagoras(objs[key], newObj); //对每个对象执行毕达哥拉斯公式
    allDistance.push({ distance: res, targetName: key }); //将所有结果压入
    // res < minDistance && ((minDistance = res), (minObjName = key));
  }

  // 遍历查找最小距离对象
  let resultObj = allDistance.sort((a, b) => a.distance - b.distance)[0];
  minObjName = resultObj['targetName'];
  minDistance = resultObj['distance'];

  if (returnDetail) return { allDistance, minDistance, minObjName };
  return minObjName;
}

模拟数据以及测试

// test
//数据库已有用户及其喜欢的电影类型的打分
let favoriteType = {
  xiaoming: {
    terror: 5,
    comedy: 1,
    love: 3,
    action: 1,
    scienceFiction: 3,
  },
  xiaohong: {
    terror: 1,
    comedy: 5,
    love: 4,
    action: 1,
    scienceFiction: 3,
  },
  xiaolv: {
    terror: 5,
    comedy: 1,
    love: 1,
    action: 5,
    scienceFiction: 4,
  },
  xiaozi: {
    terror: 1,
    comedy: 1,
    love: 5,
    action: 5,
    scienceFiction: 4,
  },
  xiaoqi: {
    terror: 1,
    comedy: 2,
    love: 5,
    action: 3,
    scienceFiction: 5,
  },
  xiaoquan: {
    terror: 5,
    comedy: 5,
    love: 5,
    action: 5,
    scienceFiction: 5,
  },
};


let res = kNN(favoriteType, { terror: 1, comedy: 4, love: 2, action: 5, scienceFiction: 5 }, true);
console.log(res);

结果

{
  allDistance: [
    { distance: '4.12', targetName: 'xiaoqi' },
    { distance: '4.36', targetName: 'xiaozi' },
    { distance: '5.00', targetName: 'xiaohong' },
    { distance: '5.10', targetName: 'xiaoquan' },
    { distance: '5.20', targetName: 'xiaolv' },
    { distance: '6.78', targetName: 'xiaoming' }
  ],
  minDistance: '4.12',
  minObjName: 'xiaoqi'
}