Участник:Mansur/Алгоритм K-means++: различия между версиями
Mansur (обсуждение | вклад) 1.1, 3 |
Mansur (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
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++<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-средних имеет, по крайней мере, два основных теоретических недостатка: | Однако алгоритм k-средних имеет, по крайней мере, два основных теоретических недостатка: | ||
Версия от 19:41, 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.