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

Mansur: /* Литература */

2023-10-30T20:53:46Z

Литература

← Предыдущая версия		Версия от 20:53, 30 октября 2023
Строка 89:		Строка 89:
	== Литература ==		== Литература ==
	<references />		<references />

	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.

Mansur: $n$

2023-10-30T20:52:33Z

← Предыдущая версия		Версия от 20:52, 30 октября 2023
Строка 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 состоит в том, чтобы найти центры кластеров, которые минимизируют внутриклассовую дисперсию, т.е. сумму квадратов расстояний от каждой кластеризуемой точки данных до ее центроида кластера (центра, который находится ближе всего к ней), то есть разбить ~~'''''~~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-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 состоит в том, чтобы найти центры кластеров, которые минимизируют внутриклассовую дисперсию, т.е. сумму квадратов расстояний от каждой кластеризуемой точки данных до ее центроида кластера (центра, который находится ближе всего к ней), то есть разбить <math>n</math> наблюдений на <math>k</math> кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения. Хотя найти точное решение задачи о 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 имеет, по крайней мере, два основных теоретических недостатка:		Однако алгоритм k-means имеет, по крайней мере, два основных теоретических недостатка:

Mansur: 1.2

2023-10-30T20:51:37Z

1.2

@@ Строка 10: / Строка 10: @@
 # Найденное приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией.
 === Математическое описание алгоритма ===
-# Случайным образом выбрать первый центроид из точек данных.
+'''Дано''':
-# Для каждой точки данных x вычислить ее расстояние D(x) от ближайшего, ранее выбранного центроида.
+* набор из <math display=block>n</math> наблюдений <math display=block>X={x_1,x_2,...,x_n},x_i \in R^d, i=1,...,n;</math>
-# Выбрать следующий центроид из точек данных таким образом, чтобы вероятность выбора точки в качестве центроида была прямо пропорциональна квадрату ее расстоянию D²(x) от ближайшего, ранее выбранного центроида. (т.е. точка, имеющая максимальное расстояние от ближайшего центроида, с наибольшей вероятностью будет выбрана следующей в качестве центроида)
+* <math display=block>k</math> - требуемое число кластеров, <math display=block>k \in N, k \leq n.</math>
-# Повторять шаги 2 и 3 до тех пор, пока не будут отобраны k центроидов.
 Теперь, когда начальные центроиды выбраны, нужно использовать стандартную кластеризацию k-means:
 === Вычислительное ядро алгоритма ===

Mansur: /* Общее описание алгоритма */

2023-10-30T20:10:24Z

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

← Предыдущая версия		Версия от 20:10, 30 октября 2023
Строка 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>
	~~Во-вторых, найденное~~ приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией.		# Найденное приближение может быть сколь угодно плохим по отношению к целевой функции по сравнению с оптимальной кластеризацией.

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

Mansur: km++

2023-10-30T20:05:18Z

km++

← Предыдущая версия		Версия от 20:05, 30 октября 2023
Строка 11:		Строка 11:

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

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

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

Mansur: /* Общее описание алгоритма */

2023-10-30T19:43:20Z

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

← Предыдущая версия		Версия от 19:43, 30 октября 2023
Строка 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 состоит в том, чтобы найти центры кластеров, которые минимизируют внутриклассовую дисперсию, т.е. сумму квадратов расстояний от каждой кластеризуемой точки данных до ее центра кластера (центра, который находится ближе всего к ней). Хотя найти точное решение задачи о 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-средних имеет, по крайней мере, два основных теоретических недостатка:

Mansur: /* Общее описание алгоритма */

2023-10-30T19:41:02Z

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

← Предыдущая версия		Версия от 19:41, 30 октября 2023
Строка 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-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-средних имеет, по крайней мере, два основных теоретических недостатка:

Mansur: 1.1, 3

2023-10-30T19:40:01Z

1.1, 3

← Предыдущая версия		Версия от 19:40, 30 октября 2023
Строка 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 центроидов.

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

Mansur: /* Литература */

2023-10-29T20:50:31Z

Литература

← Предыдущая версия		Версия от 20:50, 29 октября 2023
Строка 51:		Строка 51:
	<references />		<references />

	~~[[en~~:~~Description~~ of ~~algorithm properties~~ and ~~structure]]~~		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.

Mansur: Содержимое страницы заменено на «Данный документ содержит описание схемы, по которой предлагается описы...»

2023-10-29T20:49:05Z

Содержимое страницы заменено на «Данный документ содержит описание схемы, по которой предлагается описы...»

Внесённые изменения

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

Mansur: /* Литература */

Mansur: n

Mansur: 1.2

Mansur: /* Общее описание алгоритма */

Mansur: km++

Mansur: /* Общее описание алгоритма */

Mansur: /* Общее описание алгоритма */

Mansur: 1.1, 3

Mansur: /* Литература */

Mansur: Содержимое страницы заменено на «Данный документ содержит описание схемы, по которой предлагается описы...»

Mansur: $n$