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

Версия 22:40, 30 октября 2023

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритма
3 Литература

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

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

k-means++^[1]

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

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

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

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

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

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 Литература

↑ 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.

[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.

[1]

[2]

[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-средних имеет, по крайней мере, два основных теоретических недостатка:
-Свойства алгоритмов никак не зависят от вычислительных систем, и с этой точки зрения данная часть AlgoWiki имеет безусловную собственную ценность. Описание алгоритма делается один раз, после чего многократно используется для его реализации в различных программно-аппаратных средах. Несмотря на то, что в данной части мы рассматриваем лишь машинно-независимые свойства алгоритмов, соображения, важные на этапе реализации, или же ссылки на соответствующие пункты [[#ЧАСТЬ. Программная реализация алгоритмов|части II AlgoWiki]], здесь также вполне уместны.
-=== Общее описание алгоритма ===
+Во-первых, было показано, что наихудшее время выполнения алгоритма является супер-полиномиальным по размеру входных данных.<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 центроидов.
 === Вычислительное ядро алгоритма ===