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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 10: Строка 10:
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
  
−
Входные данные:  
+
''Входные данные:''
−
* множество наблюдений <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>, где каждое наблюдений <math>x_i \in R^d</math>;
+
* множество наблюдений <math>X = \{x_1, x_2, ..., x_n\}</math>, где каждое наблюдение <math>x_i \in R^d, i = 1, ..., n</math>;
 
* количество кластеров <math>k \in N, k <= n</math>
 
* количество кластеров <math>k \in N, k <= n</math>
 +
 +
Цель алгоритма k-means - распределить наблюдения из входного множества <math>X</math> по <math>k</math> кластерам <math>S = \{S_1, S_2, ..., S_k \}</math> таким образом, чтобы сумма квадратов расстояний между от каждой точки кластера до его центра по всем кластерам была минимальной:
 +
 +
<p align="center"><math>\arg\min_{S} \sum_{i=1}^{k} \sum_{x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 </math>,</p> где <math>\mu_i</math>- центр масс векторов <math>x \in S_i</math>, <math>i = 1, ..., k</math>
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===

Версия 21:59, 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 \lt = n[/math]

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

Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:IanaV/Алгоритм_k_means&oldid=5957