Участник:IanaV/Алгоритм k means: различия между версиями

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

Версия 22:39, 12 октября 2016

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

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

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

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

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

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

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

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


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

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

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

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

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


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

1. Инициализация центров масс

На данном шаге задаются начальные значения центров масс [math] \mu_1^0, ..., \mu_k^0[/math]. Существует несколько способов их выбора. Они будут рассмотрены ниже.

2. Распределение векторов по кластерам

На данном шаге каждый вектор [math]x \in X[/math] распределяется в свой кластер [math]S_i^t[/math] так, что:

[math]S_i^t = \arg \min_{S_j^t} \left\| \mathbf x - \mu_j^t \right\|^2 [/math]

3. Пересчет центров масс кластеров

На данном шаге происходит пересчет центров масс кластеров, полученных на предыдущем этапе:

[math]\mu_i^{t+1} = \frac{1}{|S_i^t|} \sum_{x \in S_i^t} x[/math]

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

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

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

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

1.7 Информационный граф

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

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

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

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

2.1 Масштабируемость алгоритма и его реализации

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

3 Литература