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

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

Версия 22:28, 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} \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 Литература