Участник:IanaV/Алгоритм k means: различия между версиями
IanaV (обсуждение | вклад) |
IanaV (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
''Входные данные:'' | ''Входные данные:'' | ||
* множество наблюдений <math>X = \{x_1, x_2, ..., x_n\}</math>, где каждое наблюдение <math>x_i \in R^d, i = 1, ..., n</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 | + | * количество кластеров <math>k \in N, k \leq n</math> |
''Цель алгоритма k-means'' - распределить наблюдения из входного множества <math>X</math> по <math>k</math> кластерам <math>S = \{S_1, S_2, ..., S_k \}: S_i \bigcap S_j = \emptyset</math>, <math>X = {\bigcup \limits _{i = 1}^k S_i} </math> таким образом, чтобы сумма квадратов расстояний от каждой точки кластера до его центра по всем кластерам была минимальной: | ''Цель алгоритма k-means'' - распределить наблюдения из входного множества <math>X</math> по <math>k</math> кластерам <math>S = \{S_1, S_2, ..., S_k \}: S_i \bigcap S_j = \emptyset</math>, <math>X = {\bigcup \limits _{i = 1}^k S_i} </math> таким образом, чтобы сумма квадратов расстояний от каждой точки кластера до его центра по всем кластерам была минимальной: | ||
Версия 22:03, 12 октября 2016
Авторы страницы: Валуйская Я.А. и Глотов Е.С.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
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 \}: S_i \bigcap S_j = \emptyset[/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.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
