Участник:Илья Егоров/Алгоритм k-средних

Алгоритм k-средних (k-means)
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n*k*d) }[/math]
Объём входных данных	[math]\displaystyle{ n*d }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/math]

Страница создана группой "Илья Егоров — Евгений Богомазов"

ЧАСТЬ. Свойства и структура алгоритмов

Общее описание алгоритма

Алгоритм кластеризации k-средних впервые был предложен в 1950-х годах математиками Гуго Штейнгаузом и Стюартом Ллойдом независимо друг от друга. Наибольшую популярность он получил после работы Маккуина.

Алгоритм позволяет при заданном числе [math]\displaystyle{ k }[/math] построить [math]\displaystyle{ k }[/math] кластеров, расположенных на максимальном расстоянии друг от друга. Таким образом, наибольшей точности результат выполнения алгоритма достигает при полной осведомленности Пользователя о характере кластеризуемых объектов и, как следствие, при обладании максимально корректной информацией о числе кластеров.

В общем случае выбор числа [math]\displaystyle{ k }[/math] может базироваться на любых значимых факторах, в том числе на результатах предшествующих исследований, теоретических соображениях или интуиции.

Математическое описание алгоритма

Исходные данные:

• Совокупность n d-мерных векторов [math]\displaystyle{ X = \{x_1 \dots x_n\} , }[/math] где [math]\displaystyle{ x_i = \{x_{i1} \dots x_{id}\} }[/math]
• Предполагаемое количество кластеров k

Выходные данные:

• Разбиение X на множество [math]\displaystyle{ S = \{S_1 \dots S_k \}, \bigcup S_i = X, S_i \cap S_j = \emptyset, i \neq j }[/math]
• k центров кластеров [math]\displaystyle{ \Mu = \{\mu_1 \dots \mu_k \} }[/math], где [math]\displaystyle{ \mu_i = \{\mu_{i1} \dots \mu_{id} \} }[/math] такие, что

[math]\displaystyle{ \begin{cases}\tilde{\mu_i} = \underset{y}{argmin } \sum_{x \in S_i} ||x-y||^2_E \\ \Mu = \underset{\tilde{\Mu}}{argmin } \sum_{i \in k} \sum_{x \in S_i} ||x-\tilde{\mu_i}||^2_E \end{cases} }[/math]

Алгоритм:

1) [math]\displaystyle{ \mu_{ij} = random }[/math]

2) [math]\displaystyle{ S_i = \{x \in S | \underset{j}{argmin } ||x-\mu_j||_E = i\} i = 1 \dots k }[/math]

3) [math]\displaystyle{ \tilde{\mu_{i}} = E_{x \in S_i}(x) }[/math]

4) Если для [math]\displaystyle{ \forall i: \mu_i = \tilde{\mu_i} }[/math] то алгоритм завершен, иначе [math]\displaystyle{ \mu_i = \tilde{\mu_i} }[/math] и перейти на пункт 2)

Вычислительное ядро алгоритма

Вычислительным ядром алгоритма является второй этап, а точнее нахождение матрицы расстояний между [math]\displaystyle{ X }[/math] и [math]\displaystyle{ \Mu }[/math]. Для d-мерного вектора [math]\displaystyle{ a: }[/math]

[math]\displaystyle{ ||a||=\sqrt{\sum_{i=1\dots d} a_i^2} }[/math], поэтому заполнение одной ячейки такой матрицы потребует [math]\displaystyle{ d }[/math] операций умножения, [math]\displaystyle{ d-1 }[/math] операций сложения и одну операция вычисления квадратного корня. Но так как эти расстояния используются только для сравнения, а sqrt является монотонно возрастающей функцией, то ее можно не вычислять. Поэтому нахождения матрицы расстояний потребует всего [math]\displaystyle{ n*k*d }[/math] операций умножений и [math]\displaystyle{ n*k*(d-1) }[/math] операций сложений.

Макроструктура алгоритма

Алгоритм k-средних базируется на алгоритме вычисления расстояния между векторами, расстояние на каждом шаге высчитывается [math]\displaystyle{ k\cdot n }[/math] раз.

Помимо этого, в конце каждого шага вычисляется центр масс объектов кластера, для всех объектов потребуется [math]\displaystyle{ n-1 }[/math] суммирование и [math]\displaystyle{ k }[/math] делений.

Схема реализации последовательного алгоритма

Последовательность шагов алгоритма следующая:

   1. Инициализация центроидов [math]\displaystyle{ \Mu }[/math], [math]\displaystyle{  iter = 1  }[/math], задание максимального количество итераций [math]\displaystyle{ maxiter }[/math]
       
   2a. Нахождение матрицы расстояний [math]\displaystyle{ dist: }[/math]
   
       [math]\displaystyle{ dist_{ij} = \sum_{l = 1\dots d} (x_{il}-\mu_{jl})^2 }[/math]
       
   2b. Нахождение вектора распределения объектов по кластерам [math]\displaystyle{ index:  }[/math]
   
       [math]\displaystyle{ index_{i} =   \underset{j}{argmin }~dist_{ij}  }[/math]
   
   3. Пересчет центроидов [math]\displaystyle{ \tilde{\Mu}: }[/math]
   
       [math]\displaystyle{ \tilde{\mu_{ij}} = \sum_{l \in \tilde{S_i}} \dfrac{x_{lj}}{|\tilde{S_i}|}  }[/math], где [math]\displaystyle{ \tilde{S_i} = \{l~|~l \in 1\dots n, index_l = i\}   }[/math]
   
   4. Проверка критерия останова:
   
       Если [math]\displaystyle{  \exists i: \tilde{\mu_i} \neq \mu_i }[/math], [math]\displaystyle{  iter \lt  maxiter  }[/math],
   
       то [math]\displaystyle{  inc(iter), \Mu=\tilde{\Mu}, }[/math] GOTO 2.а.

Последовательная сложность алгоритма

   1) Сложность инициализации в общем случае зависит от применяемого метода генерации/получения случайных чисел, но ей можно пренебречь
   
   2a) Вычисление матрицы расстояний требует [math]\displaystyle{  n*k*d  }[/math] операций умножений и [math]\displaystyle{  n*k*(d-1)  }[/math] операций сложений
   
   2b) Нахождение вектора распределения требует [math]\displaystyle{  n*(k-1)  }[/math] операций сравнений
   
   3) Для вычисления [math]\displaystyle{  \tilde{\Mu}  }[/math] требуется [math]\displaystyle{  (n - k + 1) * d  }[/math] операций сложений и [math]\displaystyle{  k * d  }[/math] операций деления
   
   4) Для критерия останова требуется [math]\displaystyle{  n*d  }[/math] сравнений

Итого: так как максимальное количество итераций задается в алгоритме заранее и не зависит от входных данных, то количество итераций ограничено константой. Тогда сложность алгоритма:

• [math]\displaystyle{ O(n*k*d) }[/math] операций сложений/вычитаний
• [math]\displaystyle{ O(n*k*d) }[/math] операций умножений, [math]\displaystyle{ O(k*d) }[/math] операций делений

Ресурс параллелизма алгоритма

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

2a) Нахождение каждой ячейки матрицы [math]\displaystyle{ dist }[/math] может происходить полностью независимо, так как они находятся на одном ярусе. При рассмотрении операции вычисления значения конкретной ячейки [math]\displaystyle{ dist_{ij} }[/math] можно заметить, что все операции умножения также независимы между собой, поэтому понадобится всего одно умножение. Конечный результат получается в результате суммирования всех слагаемых и достигается параллельно за [math]\displaystyle{ \log(d) }[/math] бинарных операций сложения при помощи стандартной методологии reduction.

2b) Нахождение вектора распределений заключается в нахождении минимального элемента в каждой строке матрицы [math]\displaystyle{ dist }[/math]. При использовании методологии reduction эту операцию можно выполнить за [math]\displaystyle{ \log(k) }[/math] бинарных операций сравнения.

3) В случае, если существует методология быстрого разделения n объектов на k множеств при помощи вектора индексации (косвенной адресации), все [math]\displaystyle{ \tilde{S_i} }[/math] могут быть обработаны параллельно. В рамках каждого отдельного [math]\displaystyle{ \tilde{S_i} }[/math] можно проводить распараллеливание дальше, так как [math]\displaystyle{ x_{lj} }[/math] также не зависят друг от друга. Таким образом, вычисление всех слагаемых для всех [math]\displaystyle{ \tilde{\mu_{ij}} }[/math] может быть выполнено за одно параллельное деление, а нахождение суммы всех этих слагаемых для каждого [math]\displaystyle{ \tilde{\mu_{ij}} }[/math] может быть выполнено за [math]\displaystyle{ O(log(n)) }[/math] в худшем случае (при вхождении почти всех объектов в один кластер).

Если же такой методологии не существует, то узким местом становится процесс распределения на множества согласно вектору [math]\displaystyle{ index }[/math], который можно выполнить за [math]\displaystyle{ n }[/math] операций косвенных адресаций.

4) Все сравнения для критерия останова также независимы между собой и могут быть выполнены за одну операцию сравнения, а финальный результат может быть получен за одну операцию сложения при работе над общей памятью (к примеру, прибавление единицы при несовпадении в общую память и сравнение ее с 0 по завершению) или за [math]\displaystyle{ \log(k*d) }[/math] сложений иначе.

Так как количество итераций ограничено константой, то на сложность оно не влияет. В итоге, параллельная сложность алгоритма k-means такова:

• [math]\displaystyle{ O(\log(n*d)) }[/math] операций сложения
• [math]\displaystyle{ O(\log(k)) }[/math] операций сравнения
• [math]\displaystyle{ O(1) }[/math] операций умножения и деления

Входные и выходные данные алгоритма

Входные данные: Количество кластеров k, n кластеризуемых элементов

Дополнительные ограничения:

• k — положительное число, т. е. k > 0.
• Для кластеризуемых элементов определена метрика (расстояние между объектами)

Объём входных данных: n [math]\displaystyle{ \cdot }[/math] d + 1 (кластеризуемые объекты в виде векторов и число k)

Выходные данные: Массив, в который записаны принадлежности каждого элемента кластеру (допустим вывод в другой эквивалентной более удобной структуре).

Объём выходных данных: Размер массива равен 2 [math]\displaystyle{ \cdot }[/math] n.

Свойства алгоритма

Ограничения алгоритма

Алгоритм эффективно работает только на небольших объемах данных.

Преимущества алгоритма

• Простота использования
• Быстрота использования
• Понятность и прозрачность описания
• Обладает вычислительной устойчивостью
• Предрасположенность к распараллеливанию
• Достаточно популярный, поэтому имеет множество реализаций и вариаций

Недостатки алгоритма

• Нет проверки корректности выбора числа кластеров
• Алгоритм чувствителен к количеству кластеров
• Алгоритм чувствителен к выбору начальных элементов в качестве центроидов
• Алгоритм крайне чувствителен к выбросам по данным
• Медленная работа на больших объемах данных

ЧАСТЬ. Программная реализация алгоритма

Существующие реализации алгоритма

Бесплатный доступ

Десктопные программы

• Weka
• Orange

Фреймворки для языков

• Python:
  • scikit-learn
  • SciPy
• C++:
  • MLPACK
  • OpenCV
  • Octave
• C#:
  • Accord.NET
• Java:
  • ELKI
  • Mahout
• Lua
  • Torch

Языки R и Julia содержат алгоритм k-means в базовой реализации.

Платный доступ/лицензия

Существует целый перечень мощных статистических и математических пакетов для разных ОС:

• MATLAB
• Mathematica
• Stata
• SAS
• SAP HANA
• RapidMiner
• ...

Литература

[1] Нейский И.М. Классификация и сравнение методов кластеризации http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf

[2] https://ru.wikipedia.org/wiki/K-means