K-means++

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

k-means++ — улучшенная версия алгоритма кластеризации k-means. Суть алгоритма заключается в нахождении более «хороших» начальных значений центроидов кластеров. Оригинальный k-means не регламентирует то, как выполняется этот этап алгоритма, и поэтому является нестабильным. Алгоритм предложен в 2007 году Дэвидом Артуром и Сергеем Вассильвитским. Также есть другие похожие методы, открытые другими учёными независимо.

Инициализация[править | править вики-текст]

  1. Выбрать первый центроид случайным образом (среди всех точек)
  2. Для каждой точки найти значение квадрата расстояния до ближайшего центроида (из тех, которые уже выбраны) dx²
  3. Выбрать из этих точек следующий центроид так, чтобы вероятность выбора точки была пропорциональна вычисленному для неё квадрату расстояния
    Это можно сделать следующим образом. На шаге 2 нужно параллельно с расчётом dx² подсчитывать сумму Sum(dx²). После накопления суммы найти значение Rnd=random(0.0,1.0)*Sum. Rnd случайным образом укажет на число из интервала [0; Sum), и нам остаётся только определить, какой точке это соответствует. Для этого нужно снова начать подсчитывать сумму S(dx²) до тех пор, пока сумма не превысит Rnd. Как только это случится, суммирование останавливается, и мы можем взять текущую точку в качестве центроида.
    При выборе каждого следующего центроида специально следить за тем, чтобы он не совпал с одной из уже выбранных в качестве центроидов точек, не нужно, так как вероятность повторного выбора некоторой точки равна 0.
  4. Повторять шаги 2 и 3 до тех пор, пока не будут найдены все необходимые центроиды.

Далее выполняется основной алгоритм K-Means.

Реализации[править | править вики-текст]

Реализация на языке Java включена в популярную библиотеку Apache[1].

Примечания[править | править вики-текст]