用js进行机器学习(2)-K-Means

echosoar 原创发表于 2019/01/18 09:31:35
先举一个例子,之前做过一个分析图像颜色值分布的工具,最初是遍历图像的每一个像素,将相同的颜色值都放在一起,然后进行一下排序,在这个过程中发现了一个很严重的问题:有很多渐变颜色的时候就会有很多差不多的颜色因为rgb某个分量上面的一些细微之处的差别导致被认为是两个颜色,例如:rgb(233, 56, 79)rgb(232, 57, 80)
rgb(233, 56, 79)
rgb(232, 57, 80)
这两个颜色在我们通过肉眼看的时候是看不出来有什么差别的,因此我们需要通过一种方法把这两种颜色给判定为是一种,也就是将类似差不多的颜色进行聚类。

K-Means

k-平均聚类的目的是:把 n个点(可以是样本的一次观察或一个实例)划分到k个聚类中,使每个点都在距离它最近的聚类中心所在的聚类中。 首先简单的列举一下K-Means的算法流程:
  1. 随机从数据集中选取K个数据作为初始中心,也就是要把数据分为K个聚类。
  2. 计算每一个数据距离每一个中心的欧式距离,把这个数据放入距离最短的中心所在的聚类中。
  3. 当所有数据都放入一个聚类中的时候重新计算每一个聚类的中心,也就是计算聚类中所有数据在每个分量上的平均值。
  4. 重复进行第2、3步骤,直至聚类中心不再变化时认为聚类完成。
class Kmeans {
  constructor(k, data, center) {
    this.k = k;
    this.data = data;
    this.center = center || [];
    this.initRange();
    this.initCenter();
    this.exec();
  }

  exec() {
    let isNewCenter = true;
    while (isNewCenter) {
      this.group();
      isNewCenter = this.calcCenter();
    }
  }

  // 生成数据每一个纬度的最大值与最小值,方便进行归一化处理
  initRange() {
    let range = [];
    for (let index in this.data) {
      let point = this.data[index];

      for (let weidu in point) {
        if (!range[weidu]) {
          range[weidu] = {
            min: point[weidu],
            max: point[weidu]
          }
        }
        if (point[weidu] < range[weidu].min) range[weidu].min = point[weidu];
        if (point[weidu] > range[weidu].max) range[weidu].max = point[weidu];
      }
    }
    this.range = range;
  }


  // 随机生成中心点
  initCenter() {
    let need = this.k - this.center.length;
    while (need--) {
      let point = [];
      for (let weidu in this.range) {
        let min = this.range[weidu].min;
        let rangeSize = this.range[weidu].max - min;
        point[weidu] = min + (Math.random() * rangeSize);
      }
      this.center.push(point);
    }
  }

  // 根据中心点进行分组
  group() {
    let pointGroupIndex = [];
    let groupPoint = [];
    for (let i in this.data) {
      let point = this.data[i];
      let distances = [];
  
      for (let groupIndex in this.center) {
        let centerPoint = this.center[groupIndex];
        let distanceSum = 0;
  
        for (let weidu in point) {
          let difference = point[weidu] - centerPoint[weidu];
          difference *= difference;
          distanceSum += difference;
        }
  
        let distancesTem = Math.sqrt(distanceSum);
        distances.push(distancesTem);
      }
      let index = distances.indexOf( Math.min.apply(null, distances) );
      pointGroupIndex.push(index);
      if (groupPoint[index] == null ) groupPoint[index] = [];
      groupPoint[index].push(point);
    }
    this.pointGroupIndex = pointGroupIndex;
    this.groupPoint = groupPoint;
  }

  // 重新计算中心点
  calcCenter() {
    let isNewCenter = false;

    for( let i = 0; i< this.k; i ++) {
      let cluster = this.groupPoint[i] || [];
      if (!cluster.length) { //当前中心不存在
        let point = [];
        for (let weidu in this.range) {
          let min = this.range[weidu].min;
          let rangeSize = this.range[weidu].max - min;
          point[weidu] = min + Math.random() * rangeSize;
        }

        this.center[i] = point;
        isNewCenter = true;
        continue;
      }

      let sums = (new Array(this.center[i].length)).fill(0);

      for (let clusterIndex = 0; clusterIndex < cluster.length; clusterIndex ++) {
        let clusterItem = cluster[clusterIndex];
        for (let clusterItemIndex = 0; clusterItemIndex < clusterItem.length; clusterItemIndex++) {
          sums[clusterItemIndex] += clusterItem[clusterItemIndex];
        }
      }

      let newPoint = sums.map((sum, index) => {
        return sum / cluster.length;
      });

      if (newPoint.toString() != this.center[i].toString()) {
        this.center[i] = newPoint;
        isNewCenter = true;
      }
    }
    return isNewCenter;
  }

  result() {
    return this.center;
  }
}