Как сделать алгоритм K-средних функционалом - PullRequest
Новая
       5

Как сделать алгоритм K-средних функционалом

0 голосов
/ 06 марта 2020

У меня очень базовая c реализация k-средних в javascript (я знаю, но она должна работать в браузере). То, что я хотел бы понять, - как можно сделать это более функциональным?

В настоящее время он полон циклов и чрезвычайно сложен для понимания, код ниже: 

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;
  }
}

1 Ответ

2 голосов
/ 08 марта 2020

Это, безусловно, может.

Вы могли бы начать с этого: 

  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. Если мы добавим 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 -l oop примерно так: 

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

Тогда нам нужно обновить movement. Мы можем сделать это легко, основываясь на centroids и newCentroids: 

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

Очевидно, вы можете продолжать в том же духе. Каждый for 1 oop должен иметь фундаментальное назначение. Найдите эту цель и посмотрите, может ли один из Array.prototype методов улучшить express. Во втором разделе, с которым мы работали выше, мы нашли две цели и просто разбили их на два отдельных блока.

Это должно дать вам хорошее начало для повышения функциональности. Там нет волхвов c пуля. Но если вы мыслите в терминах чистых функций неизменяемых данных и сильного разделения интересов, вы обычно можете двигаться в функциональном направлении.

...