Участник:IanaV/Алгоритм k means: различия между версиями
IanaV (обсуждение | вклад) |
IanaV (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
* количество кластеров <math>k \in N, k \leq 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>, i \neq j; <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>, i \neq j; | |||
* <math>X = {\bigcup \limits _{i = 1}^k S_i} </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> | <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> | ||
Версия от 19:05, 12 октября 2016
Авторы страницы: Валуйская Я.А. и Глотов Е.С.
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм k-means (k средних) - один из наиболее популярных алгоритмов кластеризации. Алгоритм был изобретён в 1950-х годах математиком Гуго Штейнгаузом, и почти одновременно его изобрел Стюарт Ллойд. Особую популярность алгоритм снискал после работы Маккуина.
Алгоритм кластеризации k-means решает задачу распределения N наблюдений по K кластерам так, чтобы наблюдение принадлежало одному кластеру, который имеет наименьшее удаление от наблюдения.
Математическое описание алгоритма
Входные данные:
- множество наблюдений [math]\displaystyle{ X = \{x_1, x_2, ..., x_n\} }[/math], где каждое наблюдение [math]\displaystyle{ x_i \in R^d, i = 1, ..., n }[/math];
- количество кластеров [math]\displaystyle{ k \in N, k \leq n }[/math]
Цель алгоритма k-means - распределить наблюдения из входного множества [math]\displaystyle{ X }[/math] по [math]\displaystyle{ k }[/math] кластерам [math]\displaystyle{ S = \{S_1, S_2, ..., S_k \}: * S_i \bigcap S_j = \emptyset }[/math], i \neq j;
- [math]\displaystyle{ X = {\bigcup \limits _{i = 1}^k S_i} }[/math]
таким образом, чтобы сумма квадратов расстояний от каждой точки кластера до его центра по всем кластерам была минимальной:
[math]\displaystyle{ \arg\min_{S} \sum_{i=1}^{k} \sum_{x \in S_i} \left\| \mathbf x - \mu_i \right\|^2 }[/math],
где [math]\displaystyle{ \mu_i }[/math]- центр масс векторов [math]\displaystyle{ x \in S_i }[/math], [math]\displaystyle{ i = 1, ..., k }[/math]
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Масштабируемость алгоритма и его реализации
Существующие реализации алгоритма
Существуют следующие 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