Участник:IanaV/Алгоритм k means

Авторы страницы: Валуйская Я.А. и Глотов Е.С.

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Алгоритм k-means (k средних) - один из наиболее популярных алгоритмов кластеризации. Алгоритм был изобретён в 1950-х годах математиком Гуго Штейнгаузом, и почти одновременно его изобрел Стюарт Ллойд. Особую популярность алгоритм снискал после работы Маккуина.

Алгоритм кластеризации k-means решает задачу распределения N наблюдений по K кластерам так, чтобы наблюдение принадлежало одному кластеру, который имеет наименьшее удаление от наблюдения.

1.2 Математическое описание алгоритма

Входные данные:

• множество наблюдений [math]X[/math] = [math]\{x_1, x_2, ..., x_n\}[/math], где каждое наблюдений [math]x_i \in R^d[/math];
• количество кластеров [math]k \in N, k \lt = n[/math]

2 Программная реализация алгоритма

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