Участник:Mansur/Алгоритм K-means++: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(km++)
Строка 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. Суть улучшения заключается в нахождении более «хороших» начальных значений центроидов кластеров. Задача 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-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 состоит в том, чтобы найти центры кластеров, которые минимизируют внутриклассовую дисперсию, т.е. сумму квадратов расстояний от каждой кластеризуемой точки данных до ее центроида кластера (центра, который находится ближе всего к ней), то есть разбить '''''n''''' наблюдений на '''''k''''' кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения. Хотя найти точное решение задачи о 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-means имеет, по крайней мере, два основных теоретических недостатка:
  
−
Во-первых, было показано, что наихудшее время выполнения алгоритма является супер-полиномиальным по размеру входных данных.<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>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>
 
</ref>
−
Во-вторых, найденное приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией.
+
# Найденное приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией.
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===

Версия 23:10, 30 октября 2023

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

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

k-means++[1] — улучшенная версия алгоритма кластеризации k-means. Суть улучшения заключается в нахождении более «хороших» начальных значений центроидов кластеров. Задача k-means состоит в том, чтобы найти центры кластеров, которые минимизируют внутриклассовую дисперсию, т.е. сумму квадратов расстояний от каждой кластеризуемой точки данных до ее центроида кластера (центра, который находится ближе всего к ней), то есть разбить n наблюдений на k кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения. Хотя найти точное решение задачи о k-средних для произвольных входных данных NP-сложно, [2] стандартный подход к нахождению приближенного решения широко используется и часто быстро находит разумные решения.

Однако алгоритм k-means имеет, по крайней мере, два основных теоретических недостатка:

  1. Было показано, что наихудшее время выполнения алгоритма является супер-полиномиальным по размеру входных данных.[3]
  2. Найденное приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией.

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

  1. Случайным образом выбрать первый центроид из точек данных.
  2. Для каждой точки данных x вычислить ее расстояние D(x) от ближайшего, ранее выбранного центроида.
  3. Выбрать следующий центроид из точек данных таким образом, чтобы вероятность выбора точки в качестве центроида была прямо пропорциональна квадрату ее расстоянию D²(x) от ближайшего, ранее выбранного центроида. (т.е. точка, имеющая максимальное расстояние от ближайшего центроида, с наибольшей вероятностью будет выбрана следующей в качестве центроида)
  4. Повторять шаги 2 и 3 до тех пор, пока не будут отобраны k центроидов.

Теперь, когда начальные центроиды выбраны, нужно использовать стандартную кластеризацию k-means:

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. ↑ 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.
  2. ↑ 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
  3. ↑ 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.

Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Mansur/Алгоритм_K-means%2B%2B&oldid=29388