Участник:Mansur/Алгоритм K-means++: различия между версиями
Перейти к навигации
Перейти к поиску
Mansur (обсуждение | вклад) |
Mansur (обсуждение | вклад) 1.1, 3 |
||
| Строка 1: | Строка 1: | ||
== Свойства и структура алгоритмов == | |||
=== Общее описание алгоритма === | |||
k-means++<ref>Arthur, D.; Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding" (PDF). Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 1027–1035.</ref> | |||
— улучшенная версия алгоритма кластеризации k-means. Суть улучшения заключается в нахождении более «хороших» начальных значений центроидов кластеров. Задача k-means состоит в том, чтобы найти центры кластеров, которые минимизируют внутриклассовую дисперсию, т.е. сумму квадратов расстояний от каждой кластеризуемой точки данных до ее центра кластера (центра, который находится ближе всего к ней). Хотя найти точное решение задачи о k-средних для произвольных входных данных NP-сложно, <ref>Drineas, P.; Frieze, A.; Kannan, R.; Vempala, S.; Vinay, V. (2004). "Clustering Large Graphs via the Singular Value Decomposition". Machine Learning. 56 (1–3): 9–33. doi:10.1023/B:MACH.0000033113.59016.96</ref> стандартный подход к нахождению приближенного решения широко используется и часто быстро находит разумные решения. | |||
Однако алгоритм k-средних имеет, по крайней мере, два основных теоретических недостатка: | |||
Во-первых, было показано, что наихудшее время выполнения алгоритма является супер-полиномиальным по размеру входных данных.<ref>Arthur, D.; Vassilvitskii, S. (2006). "How slow is the k-means method?". Proceedings of the twenty-second annual symposium on Computational geometry. ACM New York, NY, USA. pp. 144–153. | |||
</ref> | |||
Во-вторых, найденное приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией. | |||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
# Случайным образом выберите первый центроид из точек данных. | |||
# Для каждой точки данных вычислите ее расстояние от ближайшего, ранее выбранного центроида. | |||
# Выбрать следующий центроид из точек данных таким образом, чтобы вероятность выбора точки в качестве центроида была прямо пропорциональна ее расстоянию от ближайшего, ранее выбранного центроида. (т.е. точка, имеющая максимальное расстояние от ближайшего центроида, с наибольшей вероятностью будет выбрана следующей в качестве центроида) | |||
# Повторять шаги 2 и 3 до тех пор, пока не будут отобраны k центроидов. | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
Версия от 19:40, 30 октября 2023
Свойства и структура алгоритмов
Общее описание алгоритма
k-means++[1]
— улучшенная версия алгоритма кластеризации k-means. Суть улучшения заключается в нахождении более «хороших» начальных значений центроидов кластеров. Задача k-means состоит в том, чтобы найти центры кластеров, которые минимизируют внутриклассовую дисперсию, т.е. сумму квадратов расстояний от каждой кластеризуемой точки данных до ее центра кластера (центра, который находится ближе всего к ней). Хотя найти точное решение задачи о k-средних для произвольных входных данных NP-сложно, [2] стандартный подход к нахождению приближенного решения широко используется и часто быстро находит разумные решения.
Однако алгоритм k-средних имеет, по крайней мере, два основных теоретических недостатка:
Во-первых, было показано, что наихудшее время выполнения алгоритма является супер-полиномиальным по размеру входных данных.[3] Во-вторых, найденное приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией.
Математическое описание алгоритма
- Случайным образом выберите первый центроид из точек данных.
- Для каждой точки данных вычислите ее расстояние от ближайшего, ранее выбранного центроида.
- Выбрать следующий центроид из точек данных таким образом, чтобы вероятность выбора точки в качестве центроида была прямо пропорциональна ее расстоянию от ближайшего, ранее выбранного центроида. (т.е. точка, имеющая максимальное расстояние от ближайшего центроида, с наибольшей вероятностью будет выбрана следующей в качестве центроида)
- Повторять шаги 2 и 3 до тех пор, пока не будут отобраны k центроидов.
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Локальность данных и вычислений
Возможные способы и особенности параллельной реализации алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
- ↑ Arthur, D.; Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding" (PDF). Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 1027–1035.
- ↑ Drineas, P.; Frieze, A.; Kannan, R.; Vempala, S.; Vinay, V. (2004). "Clustering Large Graphs via the Singular Value Decomposition". Machine Learning. 56 (1–3): 9–33. doi:10.1023/B:MACH.0000033113.59016.96
- ↑ Arthur, D.; Vassilvitskii, S. (2006). "How slow is the k-means method?". Proceedings of the twenty-second annual symposium on Computational geometry. ACM New York, NY, USA. pp. 144–153.
Arthur, D.; Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding" (PDF). Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 1027–1035.