Метод k средних

Описание

• Википедия
• GeekForGeeks
• Яндекс.Образование - Кластеризация
• YouTube
• GitHub

Метод k средних (k-means) - наиболее популярный метод кластеризации. Он относится к методам машинного обучения без учителя (unsupervised).

Действие алгоритма таково, что он стремится минимизировать суммарное квадратичное отклонение точек кластеров от центров этих кластеров:

где k - число кластеров, Sⁱ - полученные кластеры, i = 1, 2, ..., k, а μⁱ - центры масс (центроиды) всех векторов x из кластера Sⁱ.

Принцип работы

Алгоритм разбивает множество элементов векторного пространства на заранее известное число кластеров k.

Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Для вычисления схожести между центром масс и векторами данных часто используется евклидова метрика.

Использование теоремы Пифагора для вычисления евклидова расстояния на плоскости

Алгоритм завершается, когда на какой-то итерации не происходит изменения внутрикластерного расстояния. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение V уменьшается, поэтому зацикливание невозможно.

Действие алгоритма в двумерном случае. Начальные точки выбраны случайно

Последовательность шагов:

• проверяется валидность/согласованность данных
• инициализируется k центроидов с начальными/произвольными k точками
• вычисляется расстояние каждой точки до каждого центроида
• каждой точке присваивается значение метки ближайшего кластера
• вычисляется центроид каждого кластера на основе содержащихся в нем точек
• цикл повторяется до тех пор, пока положение центроидов не перестанет меняться

Визуализация для лучшего понимания:

Проблемы k-средних

• не гарантируется достижение глобального минимума суммарного квадратичного отклонения V, а только одного из локальных минимумов

Типичный пример сходимости метода k средних к локальному минимуму. В этом примере результат кластеризации указанным методом противоречит очевидной кластерной структуре множества данных. Маленькими кружками обозначены точки данных, четырехлучевые звезды - центроиды. Принадлежащие им точки данных окрашены в тот же цвет

• результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен

Результат кластеризации методом k средних для ирисов Фишера и реальные виды ирисов, визуализированные с помощью ELKI. Центры кластеров отмечены с помощью крупных, полупрозрачных маркеров

• число кластеров надо знать заранее

Применение

В алгоритмах глубокого обучения метод k средних иногда применяют не по прямому назначению (классификация разбивкой на кластеры), а для создания так называемых фильтров (ядер свертки, словарей). Например, для распознавания изображений в алгоритм k средних подают небольшие случайные кусочки изображений обучающей выборки, допустим, размером 16х16 в виде линейного вектора, каждый элемент которого кодирует яркость своей точки. Количество кластеров k задается большим, например 256. Обученный метод k средних при определенных условиях вырабатывает при этом центры кластеров (центроиды), которые представляют собой удобные базисы, на которые можно разложить любое входное изображение. Такие "обученные" центроиды в дальнейшем используют в качестве фильтров, например для сверточной нейронной сети в качестве ядер свертки или других аналогичных систем машинного зрения.

Реализация

// algorithms/machine-learning/k-means.js
// Утилиты для матричных вычислений
import * as matrix from '../math/matrix'
// Функция для вычисления евклидова расстояния
import euclideanDistance from '../math/euclidean-distance'

/** Функция принимает:
 * data - данные
 * k    - количество кластеров
 */
export default function kMeans(data, k = 1) {
  if (!data) {
    throw new Error('Отсутствуют данные для классификации')
  }

  // Количество измерений
  const dimension = data[0].length
  // Центроиды
  const centroids = data.slice(0, k)

  // Матрица расстояний от каждой точки до каждого центроида
  const distances = matrix.zeros([data.length, k])

  // Классы векторных точек данных.
  // - 1 означает, что класс еще не назначен
  const classes = new Array(data.length).fill(-1)

  // Индикатор итерации
  let iterate = true
  while (iterate) {
    iterate = false

    // Вычисляем и сохраняем расстояние каждой точки от каждого центроида
    for (let i = 0; i < data.length; i++) {
      for (let j = 0; j < k; j++) {
        distances[i][j] = euclideanDistance([centroids[j]], [data[i]])
      }

      // Присваиваем метку ближайшего кластера каждой точке
      const closestClusterIndex = distances[i].indexOf(
        Math.min(...distances[i]),
      )

      // Проверяем, был ли класс точки изменен
      // и нужно ли повторить итерацию
      if (classes[i] !== closestClusterIndex) {
        iterate = true
      }

      classes[i] = closestClusterIndex
    }

    // Пересчитываем положение центроида кластера
    // на основе содержащихся в нем точек
    for (let i = 0; i < k; i++) {
      // Сбрасываем координаты центроида, поскольку нам нужно их пересчитать
      centroids[i] = new Array(dimension).fill(0)
      let clusterSize = 0
      for (let j = 0; j < data.length; j++) {
        if (classes[j] === i) {
          // Регистрируем еще одну точку текущего кластера
          clusterSize += 1
          for (let l = 0; l < dimension; l++) {
            centroids[i][l] += data[j][l]
          }
        }
      }

      // Вычисляем среднее значение каждой координаты центроида
      for (let j = 0; j < dimension; j++) {
        centroids[i][j] = parseFloat(
          Number(centroids[i][j] / clusterSize).toFixed(2),
        )
      }
    }
  }

  return classes
}

// algorithms/machine-learning/__tests__/k-means.test.js
import KMeans from '../k-means'

describe('kMeans', () => {
  it('при невалидных данных должно выбрасываться исключение', () => {
    expect(() => {
      KMeans()
    }).toThrowError('Отсутствуют данные для классификации')
  })

  it('при несогласованных данных должно выбрасываться исключение', () => {
    expect(() => {
      KMeans([[1, 2], [1]], 2)
    }).toThrowError('Матрицы имеют разную форму')
  })

  it('должен выполнить кластеризацию', () => {
    const data = [
      [1, 1],
      [6, 2],
      [3, 3],
      [4, 5],
      [9, 2],
      [2, 4],
      [8, 7],
    ]
    const k = 2
    const expectedClusters = [0, 1, 0, 1, 1, 0, 1]
    expect(KMeans(data, k)).toEqual(expectedClusters)

    expect(
      KMeans(
        [
          [0, 0],
          [0, 1],
          [10, 10],
        ],
        2,
      ),
    ).toEqual([0, 0, 1])
  })

  it('должен выполнить кластеризацию точек на одинаковых расстояниях', () => {
    const dataSet = [
      [0, 0],
      [1, 1],
      [2, 2],
    ]
    const k = 3
    const expectedCluster = [0, 1, 2]
    expect(KMeans(dataSet, k)).toEqual(expectedCluster)
  })

  it('должен выполнить кластеризацию точек в трехмерном пространстве', () => {
    const dataSet = [
      [0, 0, 0],
      [0, 1, 0],
      [2, 0, 2],
    ]
    const k = 2
    const expectedCluster = [1, 1, 0]
    expect(KMeans(dataSet, k)).toEqual(expectedCluster)
  })
})

Запускаем тесты:

npm run test ./algorithms/machine-learning/__tests__/k-means