Алгоритм k средних (k-means) - История изменений

ASA в 14:41, 19 июля 2022

2022-07-19T14:41:55Z

ASA в 14:14, 14 марта 2018

2018-03-14T14:14:40Z

← Предыдущая версия		Версия от 14:14, 14 марта 2018
Строка 506:		Строка 506:

	<references />		<references />

			[[Категория:Статьи в работе]]

			[[en:K-means clustering]]

Konshin в 17:40, 16 января 2018

2018-01-16T17:40:36Z

Konshin: /* Ресурс параллелизма алгоритма */

2018-01-16T17:39:31Z

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

← Предыдущая версия		Версия от 17:39, 16 января 2018
Строка 217:		Строка 217:

	<p>		<p>
	Работа алгоритма состоит из <math>i</math> итераций, в каждой из которых происходит <b>распределение d-мерных векторов по <math>k</math> кластерам</b>, а также <b>пересчет центров кластеров в d-мерном пространстве</b>. В шаге <b>распределения d-мерных векторов по <math>k</math> кластерам</b> расстояния между вектором и центрами кластеров вычисляются независимо (отсутствуют информационные зависимости). <b>Центры масс кластеров</b> также пересчитываются независимо друг от друга. Таким образом, имеет место [[глоссарий#Массовый параллелизм\|''массовый параллелизм'']]. Вычислим параллельную сложность <math>\Psi_*</math> каждого из шагов, а также параллельную сложность всего алгоритма, <math>\Psi_{\rm k-means}</math>. Будем исходить из предположения, что может быть использовано любое необходимое число потоков.		Работа алгоритма состоит из <math>i</math> итераций, в каждой из которых происходит <b>распределение <math>d</math>-мерных векторов по <math>k</math> кластерам</b>, а также <b>пересчет центров кластеров в <math>d</math>-мерном пространстве</b>. В шаге <b>распределения <math>d</math>-мерных векторов по <math>k</math> кластерам</b> расстояния между вектором и центрами кластеров вычисляются независимо (отсутствуют информационные зависимости). <b>Центры масс кластеров</b> также пересчитываются независимо друг от друга. Таким образом, имеет место [[глоссарий#Массовый параллелизм\|''массовый параллелизм'']]. Вычислим параллельную сложность <math>\Psi_*</math> каждого из шагов, а также параллельную сложность всего алгоритма, <math>\Psi_{\rm k-means}</math>. Будем исходить из предположения, что может быть использовано любое необходимое число потоков.
	</p>		</p>

	<p><b>Распределение <math>d</math>-мерных векторов по <math>k</math> кластерам</b></p>		<p><b>Распределение <math>d</math>-мерных векторов по <math>k</math> кластерам</b></p>
	<p>		<p>
	Поскольку на данном шаге для каждой пары векторов <math>\mathbf{x}_i, \ i=1,...,n</math> и <math>\mathbf{\mu}_j, \ j=1,...,k,</math> операции вычисления расстояния не зависят друг от друга, они могут выполняться параллельно. Тогда, разделив все вычисление расстояний на <math>n</math> потоков, получим, что в каждом потоке будет выполняться только одна операция вычисления расстояния между векторами размерности d. При этом каждому вычислительному потоку передаются координаты центров всех кластеров <math>\mathbf{\mu}_1, ..., \mathbf{\mu}_k</math>. Таким образом, параллельная сложность данного шага определяется <i> сложностью параллельной операции вычисления расстояния между d-мерными векторами</i>, <math>\Psi_{\rm distance}^d</math> и <i>сложностью определения наиболее близкого кластера</i> (паралельное взятие минимума по расстояниям), <math>\Psi_{\rm min}^k</math>. Для оценки <math>\Psi_{\rm distance}^d</math> воспользуемся [[Нахождение_частных_сумм_элементов_массива_сдваиванием \| параллельной реализацией нахождения частичной суммы элементов массива путем сдваивания]]. Аналогично, <math>\Psi_{\rm min}^k = log(k)</math>. В результате, <math>\Psi_{\rm distance}^d = O(log(d))</math>. Таким образом:		Поскольку на данном шаге для каждой пары векторов <math>\mathbf{x}_i, \ i=1,...,n</math> и <math>\mathbf{\mu}_j, \ j=1,...,k,</math> операции вычисления расстояния не зависят друг от друга, они могут выполняться параллельно. Тогда, разделив все вычисление расстояний на <math>n</math> потоков, получим, что в каждом потоке будет выполняться только одна операция вычисления расстояния между векторами размерности <math>d</math>. При этом каждому вычислительному потоку передаются координаты центров всех кластеров <math>\mathbf{\mu}_1, ..., \mathbf{\mu}_k</math>. Таким образом, параллельная сложность данного шага определяется <i> сложностью параллельной операции вычисления расстояния между <math>d</math>-мерными векторами</i>, <math>\Psi_{\rm distance}^d</math> и <i>сложностью определения наиболее близкого кластера</i> (паралельное взятие минимума по расстояниям), <math>\Psi_{\rm min}^k</math>. Для оценки <math>\Psi_{\rm distance}^d</math> воспользуемся [[Нахождение_частных_сумм_элементов_массива_сдваиванием \| параллельной реализацией нахождения частичной суммы элементов массива путем сдваивания]]. Аналогично, <math>\Psi_{\rm min}^k = log(k)</math>. В результате, <math>\Psi_{\rm distance}^d = O(\log(d))</math>. Таким образом:
	</p>		</p>
	<p align="center"><math>\Psi_{\rm distribute}^{k, d} = \Psi_{\rm distance}^d + \Psi_{\rm min}^k = O(log(d))+O(log(k)) = O(log(kd))</math></p>		<p align="center"><math>\Psi_{\rm distribute}^{k, d} = \Psi_{\rm distance}^d + \Psi_{\rm min}^k = O(log(d))+O(log(k)) = O(log(kd))</math></p>
Строка 228:		Строка 228:
	<p><b>Пересчет центров кластеров в d-мерном пространстве</b></p>		<p><b>Пересчет центров кластеров в d-мерном пространстве</b></p>
	<p>		<p>
	Поскольку на данном шаге для каждого из <math>k</math> кластеров центр масс может быть вычислен независимо, данные операции могут быть выполнены в отдельных потоках. Таким образом, параллельная сложность данного шага, <math>\Psi_{\rm recenter}^{k, d}</math>, будет определяться <i>параллельной сложностью вычисления одного центра масс кластера размера <math>m</math></i>, <math>\Psi_{\rm recenter}^{k, d}</math>, а так как <math>m \le n \Rightarrow \Psi_{\rm recenter}^{d, m} \le \Psi_{\rm recenter}^{d, n}</math>. Сложность вычисления центра масс кластера d-мерных векторов размера n аналогично предыдущим вычислениям равна <math>O(log(n))</math>. Тогда:		Поскольку на данном шаге для каждого из <math>k</math> кластеров центр масс может быть вычислен независимо, данные операции могут быть выполнены в отдельных потоках. Таким образом, параллельная сложность данного шага, <math>\Psi_{\rm recenter}^{k, d}</math>, будет определяться <i>параллельной сложностью вычисления одного центра масс кластера размера <math>m</math></i>, <math>\Psi_{\rm recenter}^{k, d}</math>, а так как <math>m \le n \Rightarrow \Psi_{\rm recenter}^{d, m} \le \Psi_{\rm recenter}^{d, n}</math>. Сложность вычисления центра масс кластера <math>d</math>-мерных векторов размера n аналогично предыдущим вычислениям равна <math>O(log(n))</math>. Тогда:
	</p>		</p>
	<p align="center"><math>\Psi_{\rm recenter}^{k, d} \le \Psi_{\rm recenter}^{d, n} = O(log(n))</math></p>		<p align="center"><math>\Psi_{\rm recenter}^{k, d} \le \Psi_{\rm recenter}^{d, n} = O(log(n))</math></p>

Konshin: /* Математическое описание алгоритма */

2018-01-16T17:32:30Z

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

← Предыдущая версия		Версия от 17:32, 16 января 2018
Строка 69:		Строка 69:
	<b>Проверка условия останова:</b>		<b>Проверка условия останова:</b>
	<p></p>		<p></p>
	'''if''' <math>\~~exist~~ i\in \overline{1,k}: \mu_i^{(t)} \ne \mu_i^{(t-1)}</math> '''then'''		* '''if''' <math>\exists i\in \overline{1,k}: \mu_i^{(t)} \ne \mu_i^{(t-1)}</math> '''then'''
	t = t + 1;		** <math>t = t + 1</math>;
	goto 2;		** goto 2;
	'''else'''		* '''else'''
	'''stop'''		** '''stop'''
	</li>		</li>
	</ol>		</ol>

Konshin в 17:25, 16 января 2018

2018-01-16T17:25:01Z

← Предыдущая версия		Версия от 17:25, 16 января 2018
Строка 11:		Строка 11:

	{{algorithm		{{algorithm
	\| name = Алгоритм <math>k</math> средних (<~~math~~>k</~~math~~>-means)		\| name = Алгоритм <math>k</math> средних (<i>k</i>-means)
	\| serial_complexity = <math>O(ikdn)</math>		\| serial_complexity = <math>O(ikdn)</math>
	\| input_data = <math> dn </math>		\| input_data = <math> dn </math>

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

2018-01-16T17:23:03Z

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

← Предыдущая версия		Версия от 17:23, 16 января 2018
Строка 21:		Строка 21:
	=== Общее описание алгоритма ===		=== Общее описание алгоритма ===

	Алгоритм <b><i>k средних</i></b> (англ. k-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации.		Алгоритм <b><i>k средних</i></b> (англ. <i>k</i>-means) - один из алгоритмов машинного обучения, решающий задачу кластеризации.
	Этот алгоритм является неиерархическим<ref>"https://ru.wikipedia.org/wiki/Иерархическая_кластеризация"</ref>, итерационным методом кластеризации<ref>"https://ru.wikipedia.org/wiki/Кластерный_анализ"</ref>, он получил большую популярность благодаря своей простоте, наглядности реализации и достаточно высокому качеству работы.		Этот алгоритм является неиерархическим<ref>"https://ru.wikipedia.org/wiki/Иерархическая_кластеризация"</ref>, итерационным методом кластеризации<ref>"https://ru.wikipedia.org/wiki/Кластерный_анализ"</ref>, он получил большую популярность благодаря своей простоте, наглядности реализации и достаточно высокому качеству работы.
	Был изобретен в 1950-х годах математиком <i>Гуго Штейнгаузом</i><ref>Steinhaus, Hugo. "Sur la division des corp materiels en parties." Bull. Acad. Polon. Sci 1.804 (1956): 801.</ref> и почти одновременно <i>Стюартом Ллойдом</i><ref>Lloyd, S. P. "Least square quantization in PCM. Bell Telephone Laboratories Paper. Published in journal much later: Lloyd, SP: Least squares quantization in PCM." IEEE Trans. Inform. Theor.(1957/1982).</ref>. Особую популярность приобрел после публикации работы <i>МакКуина</i><ref>MacQueen, James. "Some methods for classification and analysis of multivariate observations." Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. Vol. 1. No. 14. 1967.</ref> в 1967.		Был изобретен в 1950-х годах математиком <i>Гуго Штейнгаузом</i><ref>Steinhaus, Hugo. "Sur la division des corp materiels en parties." Bull. Acad. Polon. Sci 1.804 (1956): 801.</ref> и почти одновременно <i>Стюартом Ллойдом</i><ref>Lloyd, S. P. "Least square quantization in PCM. Bell Telephone Laboratories Paper. Published in journal much later: Lloyd, SP: Least squares quantization in PCM." IEEE Trans. Inform. Theor.(1957/1982).</ref>. Особую популярность приобрел после публикации работы <i>МакКуина</i><ref>MacQueen, James. "Some methods for classification and analysis of multivariate observations." Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. Vol. 1. No. 14. 1967.</ref> в 1967.

Konshin в 17:22, 16 января 2018

2018-01-16T17:22:21Z

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

Konshin: /* Математическое описание алгоритма */

2018-01-16T17:14:55Z

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

← Предыдущая версия		Версия от 17:14, 16 января 2018
Строка 33:		Строка 33:
	<b>Дано:</b>		<b>Дано:</b>
	* набор из <math>n</math> наблюдений <math>X=\{\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n\}, \mathbf{x}_i \in \mathbb{R}^d, \ i=1,...,n</math>;		* набор из <math>n</math> наблюдений <math>X=\{\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n\}, \mathbf{x}_i \in \mathbb{R}^d, \ i=1,...,n</math>;
	* <math>k</math> - требуемое число кластеров, <math>k \in \mathbb{N}, k \leq n</math>.		* <math>k</math> - требуемое число кластеров, <math>k \in \mathbb{N}, \ k \leq n</math>.

	<b>Требуется:</b>		<b>Требуется:</b>

Konshin в 17:12, 16 января 2018

2018-01-16T17:12:25Z

@@ Строка 7: / Строка 7: @@
 [https://algowiki-project.org/ru/Участник:Parkhomenko<b>П.А.Пархоменко</b>] и
 [https://algowiki-project.org/ru/Участник:Ivan.mashonskiy<b>И.Д.Машонский</b>] (раздел 2.4.3),
-[https://algowiki-project.org/ru/Участник:ХХ<b>ХХ</b>] и
+[https://algowiki-project.org/ru/Участник:Илья_Егоров<b>И.Егоров</b>] и
-[https://algowiki-project.org/ru/Участник:ХХ<b>ХХ</b>] (раздел 2.4.4)
+[https://algowiki-project.org/ru/Участник:Богомазов_Евгений<b>Е.Богомазов</b>] (раздел 2.4.4)
 {{algorithm
@@ Строка 427: / Строка 427: @@
 ==== Реализация 4 ====
 === Динамические характеристики и эффективность реализации алгоритма ===

← Предыдущая версия		Версия от 17:40, 16 января 2018
Строка 222:		Строка 222:
	<p><b>Распределение <math>d</math>-мерных векторов по <math>k</math> кластерам</b></p>		<p><b>Распределение <math>d</math>-мерных векторов по <math>k</math> кластерам</b></p>
	<p>		<p>
	Поскольку на данном шаге для каждой пары векторов <math>\mathbf{x}_i, \ i=1,...,n</math> и <math>\mathbf{\mu}_j, \ j=1,...,k,</math> операции вычисления расстояния не зависят друг от друга, они могут выполняться параллельно. Тогда, разделив все вычисление расстояний на <math>n</math> потоков, получим, что в каждом потоке будет выполняться только одна операция вычисления расстояния между векторами размерности <math>d</math>. При этом каждому вычислительному потоку передаются координаты центров всех кластеров <math>\mathbf{\mu}_1, ..., \mathbf{\mu}_k</math>. Таким образом, параллельная сложность данного шага определяется <i> сложностью параллельной операции вычисления расстояния между <math>d</math>-мерными векторами</i>, <math>\Psi_{\rm distance}^d</math> и <i>сложностью определения наиболее близкого кластера</i> (паралельное взятие минимума по расстояниям), <math>\Psi_{\rm min}^k</math>. Для оценки <math>\Psi_{\rm distance}^d</math> воспользуемся [[Нахождение_частных_сумм_элементов_массива_сдваиванием \| параллельной реализацией нахождения частичной суммы элементов массива путем сдваивания]]. Аналогично, <math>\Psi_{\rm min}^k = log(k)</math>. В результате, <math>\Psi_{\rm distance}^d = O(\log(d))</math>. Таким образом:		Поскольку на данном шаге для каждой пары векторов <math>\mathbf{x}_i, \ i=1,...,n</math> и <math>\mathbf{\mu}_j, \ j=1,...,k,</math> операции вычисления расстояния не зависят друг от друга, они могут выполняться параллельно. Тогда, разделив все вычисление расстояний на <math>n</math> потоков, получим, что в каждом потоке будет выполняться только одна операция вычисления расстояния между векторами размерности <math>d</math>. При этом каждому вычислительному потоку передаются координаты центров всех кластеров <math>\mathbf{\mu}_1, ..., \mathbf{\mu}_k</math>. Таким образом, параллельная сложность данного шага определяется <i> сложностью параллельной операции вычисления расстояния между <math>d</math>-мерными векторами</i>, <math>\Psi_{\rm distance}^d</math> и <i>сложностью определения наиболее близкого кластера</i> (паралельное взятие минимума по расстояниям), <math>\Psi_{\rm min}^k</math>. Для оценки <math>\Psi_{\rm distance}^d</math> воспользуемся [[Нахождение_частных_сумм_элементов_массива_сдваиванием \| параллельной реализацией нахождения частичной суммы элементов массива путем сдваивания]]. Аналогично, <math>\Psi_{\rm min}^k = \log(k)</math>. В результате, <math>\Psi_{\rm distance}^d = O(\log(d))</math>. Таким образом:
	</p>		</p>
	<p align="center"><math>\Psi_{\rm distribute}^{k, d} = \Psi_{\rm distance}^d + \Psi_{\rm min}^k = O(log(d))+O(log(k)) = O(log(kd))</math></p>		<p align="center"><math>\Psi_{\rm distribute}^{k, d} = \Psi_{\rm distance}^d + \Psi_{\rm min}^k = O(\log(d))+O(\log(k)) = O(\log(kd))</math></p>

	<p><b>Пересчет центров кластеров в d-мерном пространстве</b></p>		<p><b>Пересчет центров кластеров в d-мерном пространстве</b></p>
	<p>		<p>
	Поскольку на данном шаге для каждого из <math>k</math> кластеров центр масс может быть вычислен независимо, данные операции могут быть выполнены в отдельных потоках. Таким образом, параллельная сложность данного шага, <math>\Psi_{\rm recenter}^{k, d}</math>, будет определяться <i>параллельной сложностью вычисления одного центра масс кластера размера <math>m</math></i>, <math>\Psi_{\rm recenter}^{k, d}</math>, а так как <math>m \le n \Rightarrow \Psi_{\rm recenter}^{d, m} \le \Psi_{\rm recenter}^{d, n}</math>. Сложность вычисления центра масс кластера <math>d</math>-мерных векторов размера n аналогично предыдущим вычислениям равна <math>O(log(n))</math>. Тогда:		Поскольку на данном шаге для каждого из <math>k</math> кластеров центр масс может быть вычислен независимо, данные операции могут быть выполнены в отдельных потоках. Таким образом, параллельная сложность данного шага, <math>\Psi_{\rm recenter}^{k, d}</math>, будет определяться <i>параллельной сложностью вычисления одного центра масс кластера размера <math>m</math></i>, <math>\Psi_{\rm recenter}^{k, d}</math>, а так как <math>m \le n \Rightarrow \Psi_{\rm recenter}^{d, m} \le \Psi_{\rm recenter}^{d, n}</math>. Сложность вычисления центра масс кластера <math>d</math>-мерных векторов размера n аналогично предыдущим вычислениям равна <math>O(\log(n))</math>. Тогда:
	</p>		</p>
	<p align="center"><math>\Psi_{\rm recenter}^{k, d} \le \Psi_{\rm recenter}^{d, n} = O(log(n))</math></p>		<p align="center"><math>\Psi_{\rm recenter}^{k, d} \le \Psi_{\rm recenter}^{d, n} = O(\log(n))</math></p>

	<p><b>Общая параллельная сложность алгоритма</b></p>		<p><b>Общая параллельная сложность алгоритма</b></p>
Строка 236:		Строка 236:
	На каждой итерации необходимо обновление центров кластеров, которые будут использованы на следующей итерации. Таким образом, итерационный процесс выполняется последовательно<ref>Zhao, Weizhong, Huifang Ma, and Qing He. "Parallel k-means clustering based on mapreduce." IEEE International Conference on Cloud Computing. Springer Berlin Heidelberg, 2009.</ref>. Тогда, поскольку сложность каждой итерации определяется <math>\Psi_{\rm distribute}^{k, d}</math> и <math>\Psi_{\rm recenter}</math>, сложность всего алгоритма, <math>\Psi_{\rm k-means}</math> в предположении, что было сделано <math>i</math> операций определяется выражением		На каждой итерации необходимо обновление центров кластеров, которые будут использованы на следующей итерации. Таким образом, итерационный процесс выполняется последовательно<ref>Zhao, Weizhong, Huifang Ma, and Qing He. "Parallel k-means clustering based on mapreduce." IEEE International Conference on Cloud Computing. Springer Berlin Heidelberg, 2009.</ref>. Тогда, поскольку сложность каждой итерации определяется <math>\Psi_{\rm distribute}^{k, d}</math> и <math>\Psi_{\rm recenter}</math>, сложность всего алгоритма, <math>\Psi_{\rm k-means}</math> в предположении, что было сделано <math>i</math> операций определяется выражением
	</p>		</p>
	<p align="center"><math>\Psi_{\rm k-means} \approx i \cdot (\Psi_{\rm distribute}^{k, d} + \Psi_{\rm recenter}^{k, d}) \le i \cdot O(log(kdn))</math></p>		<p align="center"><math>\Psi_{\rm k-means} \approx i \cdot (\Psi_{\rm distribute}^{k, d} + \Psi_{\rm recenter}^{k, d}) \le i \cdot O(\log(kdn))</math></p>

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===
Строка 270:		Строка 270:
	<p><b>Соотношение последовательной и параллельной сложности алгоритма</b></p>		<p><b>Соотношение последовательной и параллельной сложности алгоритма</b></p>

	<math>\frac{\Theta_{\rm k-means}}{\Psi_{\rm k-means}} = \frac{O(ikdn)}{O(i \cdot log(kdn))}</math>		<math>\frac{\Theta_{\rm k-means}}{\Psi_{\rm k-means}} = \frac{O(ikdn)}{O(i \cdot \log(kdn))}</math>

	<b>Сильные стороны алгоритма</b>:		<b>Сильные стороны алгоритма</b>: