Участник:IanaV/Алгоритм k means

Авторы страницы: Валуйская Я.А. и Глотов Е.С.

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

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

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

Алгоритм кластеризации k-means решает задачу распределения N наблюдений по K кластерам так, чтобы наблюдение принадлежало одному кластеру, который имеет наименьшее удаление от наблюдения.

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

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

• множество наблюдений $X = \{x_1, x_2, ..., x_n\}$, где каждое наблюдение $x_i \in R^d, i = 1, ..., n$;
• количество кластеров $k \in N, k \leq n$

Цель алгоритма k-means - распределить наблюдения из входного множества $X$ по $k$ кластерам $S = \{S_1, S_2, ..., S_k \}$:

• $S_i \bigcap S_j = \emptyset, i \neq j$;
• $X = {\bigcup \limits _{i = 1}^k S_i}$

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

$\arg\min_{S} \sum_{i=1}^{k} \sum_{x \in S_i} \left\| \mathbf x - \mu_i \right\|^2$,

где $\mu_i$- центр масс векторов $x \in S_i$, $i = 1, ..., k$

Алгоритм состоит из следующих шагов:

1. Инициализация центров масс: На данном шаге задаются начальные значения центров масс $\mu_1^0, ..., \mu_k^0$. Существует несколько способов их выбора. Они будут рассмотрены ниже.
2. Распределение векторов по кластерам: На данном шаге каждый вектор $x \in X$ распределяется в свой кластер $S_i^t$ так, что: $S_i^t = \arg \min_{S_j} \left\| \mathbf x - \mu_j^t \right\|^2$
3. Пересчет центров масс кластеров: На данном шаге происходит пересчет центров масс кластеров, полученных на предыдущем этапе: $\mu_i^{t+1} = \frac{1}{|S_i^t|} \sum_{x \in S^_i^t} x$

2 Программная реализация алгоритма

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

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

• ELKI - содержит реализацию алгоритма k-means на языке Java (в том числе реализацию улучшенного алгоритма k-means++)
• Weka - содержит реализацию k-means на языке Java
• Apache Mahout - содержит реализацию k-means в парадигме MapReduce
• Spark Mllib - содержит распределенную реализацию k-means
• Accord.NET - содержит реализацию k-means на C# (в том числе реализацию улучшенного алгоритма k-means++)
• MLPACK - содержит реализацию k-means на языке C++
• OpenCV - содержит реализацию k-means на C++. А также есть обертки для языков Python и Java
• SciPy - содержит реализацию k-means на языке Python
• Scikit-learn - содержит реализацию k-means на языке Python
• Julia - содержит реализацию алгоритма k-means на языке Julia
• Octave - содержит реализацию k-means на языке Octave
• R - содержит реализацию k-means на языке R
• Torch - содержит реализацию k-means на языке Lua