Участник:IanaV/Алгоритм k means: различия между версиями
Перейти к навигации
Перейти к поиску
IanaV (обсуждение | вклад) |
IanaV (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Входные данные: | |||
* множество наблюдений <math>X</math> = <math>\{x_1, x_2, ..., x_n\}</math>, где каждое наблюдений <math>x_i \in R^d</math>; | |||
* количество кластеров <math>k \in N, k <= n</math> | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
Версия от 18:49, 12 октября 2016
Авторы страницы: Валуйская Я.А. и Глотов Е.С.
Свойства и структура алгоритма
Общее описание алгоритма
Алгоритм k-means (k средних) - один из наиболее популярных алгоритмов кластеризации. Алгоритм был изобретён в 1950-х годах математиком Гуго Штейнгаузом, и почти одновременно его изобрел Стюарт Ллойд. Особую популярность алгоритм снискал после работы Маккуина.
Алгоритм кластеризации k-means решает задачу распределения N наблюдений по K кластерам так, чтобы наблюдение принадлежало одному кластеру, который имеет наименьшее удаление от наблюдения.
Математическое описание алгоритма
Входные данные:
- множество наблюдений [math]\displaystyle{ X }[/math] = [math]\displaystyle{ \{x_1, x_2, ..., x_n\} }[/math], где каждое наблюдений [math]\displaystyle{ x_i \in R^d }[/math];
- количество кластеров [math]\displaystyle{ k \in N, k \lt = n }[/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