Участник:IanaV/Алгоритм k means: различия между версиями
Перейти к навигации
Перейти к поиску
IanaV (обсуждение | вклад) |
IanaV (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
Алгоритм k-means (k средних) - один из наиболее популярных алгоритмов кластеризации. Был изобретён в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом. Особую популярность приобрёл после работы Маккуина. | Алгоритм k-means (k средних) - один из наиболее популярных алгоритмов кластеризации. Был изобретён в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом. Особую популярность приобрёл после работы Маккуина. | ||
| + | |||
Алгоритм кластеризации k-means решает задачу распределения N наблюдений (d-мерные вектора) по K кластерам так, чтобы наблюдение принадлежало одному кластеру, который имеет наименьшее удаление от наблюдения. | Алгоритм кластеризации k-means решает задачу распределения N наблюдений (d-мерные вектора) по K кластерам так, чтобы наблюдение принадлежало одному кластеру, который имеет наименьшее удаление от наблюдения. | ||
Версия 23:06, 10 октября 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 наблюдений (d-мерные вектора) по K кластерам так, чтобы наблюдение принадлежало одному кластеру, который имеет наименьшее удаление от наблюдения.
1.2 Математическое описание алгоритма
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
