javascript - 如何使 k 均值算法发挥作用

Question

我在 javascript 中有一个非常基本的 k-means 实现(我知道，但它需要在浏览器中运行)。我想了解的是 - 如何才能使其更实用？

它目前充满了循环，并且极难遵循/推理，代码如下:

export default class KMeans {
  constructor(vectors, k) {
    this.vectors = vectors;
    this.numOfVectors = vectors.length;
    this.k = k || bestGuessK(this.numOfVectors);
    this.centroids = randomCentroids(this.vectors, this.k);
  }

  classify(vector, distance) {
    let min = Infinity;
    let index = 0;

    for (let i = 0; i < this.centroids.length; i++) {
      const dist = distance(vector, this.centroids[i]);
      if (dist < min) {
        min = dist;
        index = i;
      }
    }

    return index;
  }

  cluster() {
    const assigment = new Array(this.numOfVectors);
    const clusters = new Array(this.k);

    let movement = true;

    while (movement) {
      // update vector to centroid assignments
      for (let i = 0; i < this.numOfVectors; i++) {
        assigment[i] = this.classify(this.vectors[i], euclidean);
      }

      // update location of each centroid
      movement = false;
      for (let j = 0; j < this.k; j++) {
        const assigned = [];

        for (let i = 0; i < assigment.length; i++) {
          if (assigment[i] === j) assigned.push(this.vectors[i]);
        }

        if (!assigned.length) continue;
        const centroid = this.centroids[j];
        const newCentroid = new Array(centroid.length);

        for (let g = 0; g < centroid.length; g++) {
          let sum = 0;
          for (let i = 0; i < assigned.length; i++) {
            sum += assigned[i][g];
          }
          newCentroid[g] = sum / assigned.length;

          if (newCentroid[g] !== centroid[g]) {
            movement = true;
          }
        }
        this.centroids[j] = newCentroid;
        clusters[j] = assigned;
      }
    }

    return clusters;
  }
}

Answer 1

当然可以。

你可以从这个开始:

  classify(vector, distance) {
    let min = Infinity;
    let index = 0;

    for (let i = 0; i < this.centroids.length; i++) {
      const dist = distance(vector, this.centroids[i]);
      if (dist < min) {
        min = dist;
        index = i;
      }
    }

    return index;
  }

为什么这是一个成员函数？纯函数 const Classify = (centroids, vector, distance) => {...} 不是更干净吗？

然后，为了实现，我们稍微更改一下distance 签名。如果我们将其柯里化(Currying)为 const distance = (vector) => (centroid) => {...}，我们就可以这样写

const classify = (centroids, vector, distance) =>
  minIndex (centroids .map (distance (vector)))

如果 distance API 超出了我们的控制范围，那也没什么困难:

const classify = (centroids, vector, distance) =>
  minIndex (centroids .map (centroid => distance (vector, centroid)))

当然，我们还没有编写 minIndex，但我们已经将问题分解为使用更有意义的抽象。而且 minIndex 并不难写。您可以像原始 classify 函数那样强制执行此操作，或者使用类似以下内容:

const minIndex = (xs) => xs.indexOf (Math.min (...xs))

请注意，这里的distance 是一个稍有误导性的名称。我必须更仔细地阅读它，因为我认为这样的名字代表着……，嗯，一段距离。相反，它是一个用于计算距离的函数。也许名称 metric 或诸如 distanceFunction、distanceFn 或 distanceImpl 之类的名称会更明显。

<小时/>

现在让我们继续这一点:

const newCentroid = new Array(centroid.length);

for (let g = 0; g < centroid.length; g++) {
  let sum = 0;
  for (let i = 0; i < assigned.length; i++) {
    sum += assigned[i][g];
  }
  newCentroid[g] = sum / assigned.length;

  if (newCentroid[g] !== centroid[g]) {
    movement = true;
  }
}

此代码有两个职责:创建 newCentroid 数组，并在任何值发生更改时更新 movement 的值。

让我们把这两者分开。

首先，创建新的质心。我们可以将嵌套的 for 循环清理为如下所示:

const makeNewCentroid = (centroid, assigned) =>
  centroid .map ((c, g) => mean (assigned .map ((a) => a[g])))

这取决于 mean 函数，我们将其与其所需的 sum 函数一起编写，如下所示:

const sum = (ns) =>  ns .reduce ((t, n) => t + n, 0)
const mean = xs => sum (xs) / xs.length

然后我们需要更新运动。我们可以基于 centroids 和 newCentroids 轻松做到这一点:

movement = centroids.some((c, i) => c !== newCentroids[i])

<小时/>

显然，你可以按照这种方式继续。每个 for 循环都应该有一个基本目的。找到该目的并查看 Array.prototype 方法之一是否可以更好地表达它。对于上面的第二部分，我们发现了两个目的，并将它们分成两个单独的 block 。

这应该为您提供一个良好的开端，让其变得更加实用。没有 Elixir 。但是，如果您考虑不可变数据上的纯函数以及强关注点分离，那么您通常可以朝函数方向发展。