Участник:Msindeeva/Алгоритм k средних - История изменений

Msindeeva в 01:26, 1 декабря 2017

2017-12-01T01:26:48Z

← Предыдущая версия		Версия от 01:26, 1 декабря 2017
Строка 17:		Строка 17:
	Также входным параметром можно считать метрику для векторов, например евклидово расстояние <math>d(x, y) = \sum_{i = 1}^{l} (x_i - y_i )^2</math> - одна из самых популярных используемых метрик.		Также входным параметром можно считать метрику для векторов, например евклидово расстояние <math>d(x, y) = \sum_{i = 1}^{l} (x_i - y_i )^2</math> - одна из самых популярных используемых метрик.

	Формально нам необходимо найти такое разделение <math>(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)</math> на подмножества <math>G = (G_1, .. G_k)</math>, ~~так чтобы минимизировать~~ сумму квадратов расстояний до их центров, или суммарное квадратичное отклонение:		Формально нам необходимо найти такое разделение <math>(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)</math> на подмножества <math>G = (G_1, .. G_k)</math>, минимизирующие сумму квадратов расстояний до их центров, или суммарное квадратичное отклонение:
	:<math>		:<math>
	J = \underset{\mathbf{G}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x \in G_i} d(\mathbf x, \boldsymbol\mu_i)^2,		J = \underset{\mathbf{G}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x \in G_i} d(\mathbf x, \boldsymbol\mu_i)^2,
Строка 52:		Строка 52:
	# Инициализация центроидов <math>\mu_1, ... \mu_k</math>.		# Инициализация центроидов <math>\mu_1, ... \mu_k</math>.
	# Последовательное вычисление расстояний векторов до этих центроидов и разбиение по кластерам с этими центрами.		# Последовательное вычисление расстояний векторов до этих центроидов и разбиение по кластерам с этими центрами.
	# Нахождение изменения метрики <math>J</math>. Если оно ~~больше~~ некоего заданного порога, то центроиды найдены.		# Нахождение изменения метрики <math>J</math>. Если оно меньше некоего заданного порога, то центроиды найдены.
	# Пересчет центроидов в новых кластерах.		# Пересчет центроидов в новых кластерах.
	# Переход к шагу 2.		# Переход к шагу 2.

Msindeeva в 00:11, 1 декабря 2017

2017-12-01T00:11:37Z

← Предыдущая версия		Версия от 00:11, 1 декабря 2017
Строка 116:		Строка 116:
	На графике показана зависимость производительности (количество операций в секунду) от числа процессов и числа векторов.		На графике показана зависимость производительности (количество операций в секунду) от числа процессов и числа векторов.

			[[Файл:Scalability_k_means.png\|thumb\|none\|500px\|Рисунок 2. Масштабируемость алгоритма k средних]]
	[[Файл:Scalability_k_means.png\|thumb\|none\|500px\|Рисунок 2. Масштабируемость]]

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

Msindeeva: Финальная версия

2017-12-01T00:02:16Z

Финальная версия

@@ Строка 101: / Строка 101: @@
 * Результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен.
 * Число кластеров надо знать заранее.
 == Программная реализация алгоритма ==
 == Литература ==
 * MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations"
 * MacKay, David (2003). "An Example Inference Task: Clustering"

Msindeeva: /* Свойства и структура алгоритма */ Добавлены все отсутствовавшие разделы

2017-11-30T19:57:54Z

Свойства и структура алгоритма: Добавлены все отсутствовавшие разделы

@@ Строка 19: / Строка 19: @@
 Формально нам необходимо найти такое разделение <math>(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)</math> на подмножества <math>G = (G_1, .. G_k)</math>, так чтобы минимизировать сумму квадратов расстояний до их центров, или суммарное квадратичное отклонение:
 :<math>
-F = \underset{\mathbf{G}} {\operatorname{arg\,min}}  \sum_{i=1}^{k} \sum_{\mathbf x \in G_i} d(\mathbf x, \boldsymbol\mu_i)^2,
+J = \underset{\mathbf{G}} {\operatorname{arg\,min}}  \sum_{i=1}^{k} \sum_{\mathbf x \in G_i} d(\mathbf x, \boldsymbol\mu_i)^2,
 </math>
 где <math>\boldsymbol\mu_i</math> - центр кластера <math>G_i</math>
@@ Строка 28: / Строка 28: @@
 * Переразбить векторы на кластеры в соответствии с расстоянием до новых посчитанных центров: <math>z_i = \underset{\mathbf{j}} {\operatorname{arg\,min}} \{d(\mathbf x_i, \boldsymbol \mu_j)\}, i = 1, 2, .. n</math>
-Алгоритм завершается, когда на какой-то итерации не происходит изменения центра масс кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение F не увеличивается, поэтому зацикливание невозможно.
+Алгоритм завершается, когда на какой-то итерации не происходит изменения центра масс кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение <math>J</math> не увеличивается, поэтому зацикливание невозможно.
 Такой алгоритм сходится при любом начальном приближении разбиения на кластеры, поэтому в качестве нулевого шага часто выбирают <math>k</math> случайных векторов среди  <math>(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)</math>.
 == Программная реализация алгоритма ==

Msindeeva в 20:18, 30 октября 2017

2017-10-30T20:18:39Z

← Предыдущая версия		Версия от 20:18, 30 октября 2017
Строка 1:		Строка 1:
	Алгоритм k средних		'''Алгоритм k средних'''

	Автор статьи: Синдеева Мария, группа 416		Автор статьи: Синдеева Мария, группа 416

Msindeeva в 20:17, 30 октября 2017

2017-10-30T20:17:37Z

← Предыдущая версия		Версия от 20:17, 30 октября 2017
Строка 1:		Строка 1:
			Алгоритм k средних
			Автор статьи: Синдеева Мария, группа 416

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

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

	'''Алгоритм k средних''' - это алгоритм кластерного анализа, используемый в ~~дата майнинге~~. Цель алгоритма - разделить <math>n</math> наблюдений на <math>k</math> кластеров, в которых каждое наблюдение принадлежит к кластеру с ближайшим центром, который служит прототипом всего кластера. Эта задача является NP-сложной, но существуют эффективные эвристические алгоритмы, быстро сходящиеся к локальному минимуму.		'''Алгоритм k средних''' - это алгоритм кластерного анализа, используемый в Data Mining. Цель алгоритма - разделить <math>n</math> наблюдений на <math>k</math> кластеров, в которых каждое наблюдение принадлежит к кластеру с ближайшим центром, который служит прототипом всего кластера. Эта задача является NP-сложной, но существуют эффективные эвристические алгоритмы, быстро сходящиеся к локальному минимуму.

	Алгоритм k средних является наиболее популярным ~~метод~~ кластеризации. Он был изобретён в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом.		Алгоритм k средних является наиболее популярным методом кластеризации. Он был изобретён в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===
Строка 26:		Строка 29:
	Алгоритм завершается, когда на какой-то итерации не происходит изменения центра масс кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение F не увеличивается, поэтому зацикливание невозможно.		Алгоритм завершается, когда на какой-то итерации не происходит изменения центра масс кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение F не увеличивается, поэтому зацикливание невозможно.

	Такой алгоритм сходится при любом начальном приближении разбиения на кластеры, поэтому в качестве нулевого ~~шаге~~ часто выбирают <math>k</math> случайных векторов среди <math>(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)</math>.		Такой алгоритм сходится при любом начальном приближении разбиения на кластеры, поэтому в качестве нулевого шага часто выбирают <math>k</math> случайных векторов среди <math>(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)</math>.

Msindeeva: Первый вариант статьи

2017-10-23T21:00:07Z

Первый вариант статьи

Новая страница

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

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

'''Алгоритм k средних''' - это алгоритм кластерного анализа, используемый в дата майнинге. Цель алгоритма - разделить <math>n</math> наблюдений на <math>k</math> кластеров, в которых каждое наблюдение принадлежит к кластеру с ближайшим центром, который служит прототипом всего кластера. Эта задача является NP-сложной, но существуют эффективные эвристические алгоритмы, быстро сходящиеся к локальному минимуму.

Алгоритм k средних является наиболее популярным метод кластеризации. Он был изобретён в 1950-х годах математиком Гуго Штейнгаузом и почти одновременно Стюартом Ллойдом.

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

Входные параметры: <math>n</math> наблюдений (векторов) <math>(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)</math>, <math>k</math> - число кластеров.

Также входным параметром можно считать метрику для векторов, например евклидово расстояние <math>d(x, y) = \sum_{i = 1}^{l} (x_i - y_i )^2</math> - одна из самых популярных используемых метрик.

Формально нам необходимо найти такое разделение <math>(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)</math> на подмножества <math>G = (G_1, .. G_k)</math>, так чтобы минимизировать сумму квадратов расстояний до их центров, или суммарное квадратичное отклонение:
:<math>
F = \underset{\mathbf{G}} {\operatorname{arg\,min}} \sum_{i=1}^{k} \sum_{\mathbf x \in G_i} d(\mathbf x, \boldsymbol\mu_i)^2,
</math>
где <math>\boldsymbol\mu_i</math> - центр кластера <math>G_i</math>

Алгоритм работает итерационно, каждая итерация алгоритма представляет собой следующее:

* Пересчитать центр масс для каждого кластера, полученного на предыдущем шаге: <math>\boldsymbol \mu_i = \frac{\sum_{\mathbf x_i \in G_i}\mathbf x_i}{|G_i|}, i = 1, 2, .. k</math>
* Переразбить векторы на кластеры в соответствии с расстоянием до новых посчитанных центров: <math>z_i = \underset{\mathbf{j}} {\operatorname{arg\,min}} \{d(\mathbf x_i, \boldsymbol \mu_j)\}, i = 1, 2, .. n</math>

Алгоритм завершается, когда на какой-то итерации не происходит изменения центра масс кластеров. Это происходит за конечное число итераций, так как количество возможных разбиений конечного множества конечно, а на каждом шаге суммарное квадратичное отклонение F не увеличивается, поэтому зацикливание невозможно.

Такой алгоритм сходится при любом начальном приближении разбиения на кластеры, поэтому в качестве нулевого шаге часто выбирают <math>k</math> случайных векторов среди <math>(\mathbf x_1, \mathbf x_2, .. \mathbf x_n)</math>.

== Программная реализация алгоритма ==
== Литература ==
* MacQueen, J. B. (1967). "Some Methods for classification and Analysis of Multivariate Observations"
* MacKay, David (2003). "An Example Inference Task: Clustering"