使用js实现Kmeans聚类算法进行图片颜色数据分类

最近在玩一些数据分析相关的项目，接触到了一些数据分类的算法，这里介绍一些新学的kmeans聚类算法。kmeans和knn算法比较像都是利用过计算数据的距离进行分类，不同的是knn邻近算法需要给出已经经过分类的数据用来作为分类的依据，而kmeans算法则是只要给出要分几类，直接从需要分类的数据进行.

个人原创，版权所有，转载请注明原文出处，并保留原文链接：

https://www.embbnux.com/2015/10/15/use_kmeans_for_data_classification/

参考文章：Using python and k-means to find the dominant colors in images

一 kmeans聚类算法原理介绍

kmeans是数据挖掘算法里面一个比较基础的算法，输入一个k值，用来指定要区分多少类，还有一组需要被区分的数据data。

主要算法流程：

1. 在需要被分类的数据data随机选出k个数据，作为当前的k个类

2. 遍历所有需要聚类的数据，计算每一个需要聚类的数据与之前选的k个类的距离，把该数据关联到距离最近的类

3. 利用k个类所关联的数据重新算出一个类，替换与之关联的类，这个类称为新类，之前的类称为旧类。这个计算出的新的类称作引力中心

4. 计算k个类中旧类与新类的距离，这个称为类的移动距离，当k个类的移动距离小于某个设定的阈值，则完成算法，这k个类就是被聚类完成的k个类

二 使用js使用kmeans聚类算法用于获取图片主要颜色

kmeans的关键在于距离算法与引力中心算法，不同的应用场景主要的不同就是距离算法与引力中心算法，这里我以用js算出图片主要颜色为例:

首先要获取图片的数据，这里通过画到canvas再读出来实现图片每个像素颜色的获取:

function getImageData(image){
  var ctx = document.getElementById('canvas').getContext('2d');
  img = new Image();
  img.src = image.src;
  ctx.drawImage(img, 0, 0, 100, 100);
  data = ctx.getImageData(0, 0, 200, 200).data;
  var points = []
  for (var i = 0, l = data.length; i < l; i += 4) {
    var r = data[i];
    var g = data[i+1];
    var b = data[i+2];
    points.push([r, g, b]);
  }
  return points
}

计算点与点的距离，这里及颜色之间的差别

function euclidean(p1, p2) {
  var s = 0;
  for (var i = 0, l = p1.length; i < l; i++) {
    s += Math.pow(p1[i] - p2[i], 2)
  }
  return Math.sqrt(s);
}

计算引力中心算法

function calculateCenter(points, n) {
 var vals = [];
 var plen = 0;
 for (var i = 0; i < n; i++) { vals.push(0); }
 for (var i = 0, l = points.length; i < l; i++) {
   plen++;
   for (var j = 0; j < n; j++) {
     vals[j] += points[i][j];
   }
 }
 for (var i = 0; i < n; i++) {
   if (plen > 0){
     vals[i] = vals[i] / plen;
   }
 }
 return vals;
}

最终的Kmeans算法:

function kMeans(points, k, min_diff) {
 plen = points.length;
 clusters = [];
 seen = [];
 while (clusters.length < k) {
   idx = parseInt(Math.random() * plen);
   found = false;
   for (var i = 0; i < seen.length; i++ ) {
     if (idx === seen[i]) {
       found = true;
       break;
     }
   }
   if (!found) {
     seen.push(idx);
     clusters.push([points[idx], [points[idx]]]);
   }
 }

 while (true) {
   plists = [];
   for (var i = 0; i < k; i++) {
     plists.push([]);
   }
   for (var j = 0; j < plen; j++) {
     var p = points[j];
     var smallest_distance = 10000000;
     var idx = 0;
     for (var i = 0; i < k; i++) {
       var distance = euclidean(p, clusters[i][0]);
       if (distance < smallest_distance) {
        smallest_distance = distance;
        idx = i;
       }
     }
     plists[idx].push(p);
   }
   var diff = 0;
   for (var i = 0; i < k; i++) {
     var old = clusters[i];
     var list = plists[i];
     var center = null;
     if (list.length > 0){
       center = calculateCenter(plists[i], 3);
     }else{
       center = calculateCenter(clusters, 3);
     }
     var new_cluster = [center, [center]];
     var dist = euclidean(old[0], center);
     clusters[i] = new_cluster;
     diff = diff > dist ? diff : dist;
   }
   if (diff < min_diff) {
     break;
   }
 }
 return clusters;
}

完成。