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].

Реализация на Python включена в библиотеку Scikit-learn.

Примечания

[править | править код]
  1. Commons Math: The Apache Commons Mathematics Library. Дата обращения: 20 сентября 2013. Архивировано 6 октября 2014 года.