Кластеризация - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:11:17Z

rollbackEdits.php mass rollback

185.220.100.252 в 06:13, 1 сентября 2022

2022-09-01T06:13:45Z

178.252.127.225: /* Меры качества кластеризации */

2021-12-07T20:34:25Z

‎Меры качества кластеризации

Evaleria: /* Метод K-средних (Алгоритм Ллойда) */

2021-02-08T16:20:06Z

‎Метод K-средних (Алгоритм Ллойда)

Forliss: /* DBSCAN */

2021-01-14T16:05:14Z

‎DBSCAN

Forliss: /* DBSCAN */

2021-01-14T15:50:17Z

‎DBSCAN

Forliss: /* DBSCAN */

2021-01-14T15:32:31Z

‎DBSCAN

Forliss: /* DBSCAN */

2021-01-13T20:38:33Z

‎DBSCAN

Forliss: /* DBSCAN */

2021-01-13T20:31:52Z

‎DBSCAN

Forliss: /* DBSCAN */

2021-01-13T20:23:11Z

‎DBSCAN

@@ Строка 1: / Строка 1: @@
 [[Файл:clusters.png|thumb|300px|Пример кластеризации]]
 '''Кластеризация''' (англ. ''cluster analysis'') {{---}} задача группировки множества объектов на подмножества ('''кластеры''') таким образом,
@@ Строка 33: / Строка 12: @@
 {{Определение
 |definition =
-'''Алгоритм кластеризации''' — функция <tex>a\colon X\to Y</tex>, которая любому объекту <tex>x\in X</tex> ставит в соответствие идентификатор кластера <tex>y\in Y</tex>.
+'''Алгоритм кластеризации''' — функция <tex>a\colon X\to Y</tex>, которая любому объекту <tex>x\in X</tex> ставит в соответствие идентификатор кластера <tex>y\in Y</tex>.
 }}
 Множество <tex>Y</tex> в некоторых случаях известно заранее, однако чаще ставится задача

@@ Строка 1: / Строка 1: @@
 [[Файл:clusters.png|thumb|300px|Пример кластеризации]]
 '''Кластеризация''' (англ. ''cluster analysis'') {{---}} задача группировки множества объектов на подмножества ('''кластеры''') таким образом,
@@ Строка 12: / Строка 33: @@
 {{Определение
 |definition =
-'''Алгоритм кластеризации''' — функция <tex>a\colon X\to Y</tex>, которая любому объекту <tex>x\in X</tex> ставит в соответствие идентификатор кластера <tex>y\in Y</tex>.
+'''Алгоритм кластеризации''' — функция <tex>a\colon X\to Y</tex>, которая любому объекту <tex>x\in X</tex> ставит в соответствие идентификатор кластера <tex>y\in Y</tex>.
 }}
 Множество <tex>Y</tex> в некоторых случаях известно заранее, однако чаще ставится задача

@@ Строка 102: / Строка 102: @@
 == Меры качества кластеризации ==
 Для оценки качества кластеризации задачу можно переформулировать в терминах задачи дискретной оптимизации.
-Необходима так сопоставить объектам из множества <tex>X</tex> метки кластеров, чтобы значение выбранного функционала качества приняло наилучшее значение.
+Необходимо так сопоставить объектам из множества <tex>X</tex> метки кластеров, чтобы значение выбранного функционала качества приняло наилучшее значение.
 В качестве примера, стремятся достичь минимума среднего внутрикластерного расстояния <tex>F_0 = \dfrac{\sum_{i<j}{[y_i=y_j]\cdot\rho(x_i, x_j)}}{\sum_{i<j}[y_i=y_j]}</tex> или максимума среднего межкластерного расстояния <tex>F_1 = \dfrac{\sum_{i<j}{[y_i\neq y_j]\cdot\rho(x_i, x_j)}}{\sum_{i<j}[y_i\neq y_j]}</tex>.

@@ Строка 130: / Строка 130: @@
 == Псевдокод некоторых алгоритмов кластеризации ==
 === Метод K-средних (Алгоритм Ллойда) ===
 Алгоритм минимизирует сумму квадратов внутрикластерных расстояний:
 <tex> \sum_{i = 1}^{m} ||x_i - \mu_{a_i}||^2 \: \to \: \min_{ \{a_i\}, \{\mu_a\}}, \: \: ||x_i - \mu_a||^2 = \sum_{j = 1}^{n} (f_j(x_i) - \mu_{a_j})^2</tex>

@@ Строка 194: / Строка 194: @@
    <font color="blue"><tex>return</tex></font> <tex>a, \: A, \: mark</tex>  <font color="gray"># Возвращаем количество кластеров, распределение по кластерам и метки объектов (внутренние, граничные или шумовые)</font>
-DBSCAN находит практическое применение во многих реальных задачах. Например, в маркетинге: необходимо предложить покупателю релевантный товар, который подойдет под его заказ. Выбрать такой товар можно, если посмотреть на похожие заказы других покупателей {{---}} в таком случае похожие заказы образуют кластер вещей, которые часто берут вместе. Похожим образом с помощью DBSCAN можно исследовать и находить общие интересы людей, чтобы таргетировано предлагать другие товары и услуги.
+DBSCAN находит практическое применение во многих реальных задачах, например, в маркетинге: необходимо предложить покупателю релевантный товар, который подойдет под его заказ. Выбрать такой товар можно, если посмотреть на похожие заказы других покупателей {{---}} в таком случае похожие заказы образуют кластер вещей, которые часто берут вместе. Похожим образом с помощью DBSCAN можно исследовать и находить общие интересы людей, делить их на социальные группы, моделировать поведение посетителей сайта. Алгоритм также может использоваться для [[Сегментация изображений|сегментации изображений]].
 == Пример кода ==

@@ Строка 152: / Строка 152: @@
 === DBSCAN ===
-Основная идея метода заключается в том, что алгоритм разделит заданный набор точек в некотором пространстве на группы точек, которые лежат друг от друга на малом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые.
+Основная идея метода заключается в том, что алгоритм разделит заданный набор точек в некотором пространстве на группы точек, которые лежат друг от друга на большом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые.
 На вход алгоритму подаётся набор точек, параметры <tex>\epsilon</tex> (радиус окружности) и <tex>m</tex> (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые.
@@ Строка 170: / Строка 170: @@
 Рассмотрим код:
-Пусть для каждого <tex>x \in X^m</tex> имеем посчитанной его <tex>\epsilon</tex>-окрестность <tex>U_{\epsilon}(x) = \{x' \in X^m \: | \: \rho(x, x') \lt \epsilon\}</tex>
+Пусть для каждого <tex>x \in X^m</tex> имеем посчитанной его <tex>\epsilon</tex>-окрестность <tex>U_{\epsilon}(x) = \{x' \in X^m \: | \: \rho(x, x') \lt \epsilon\}</tex>.
    <tex>U := X^m</tex>  <font color="gray"># Непомеченные объекты</font>

← Предыдущая		Версия 20:38, 13 января 2021
Строка 152:		Строка 152:

	=== DBSCAN ===		=== DBSCAN ===
−	'''Основанная на плотности пространственная кластеризация для приложений с шумами''' (англ. Density-based spatial clustering of applications with noise, '''DBSCAN''')
−
	Основная идея метода заключается в том, что алгоритм разделит заданный набор точек в некотором пространстве на группы точек, которые лежат друг от друга на малом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые.		Основная идея метода заключается в том, что алгоритм разделит заданный набор точек в некотором пространстве на группы точек, которые лежат друг от друга на малом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые.

@@ Строка 154: / Строка 154: @@
 '''Основанная на плотности пространственная кластеризация для приложений с шумами''' (англ. Density-based spatial clustering of applications with noise, '''DBSCAN''')
-Основная идея метода основана на плотности пространства: если дан набор точек в некотором пространстве, то алгоритм сгруппирует вместе все точки, которые лежат друг от друга на малом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые.
+Основная идея метода заключается в том, что алгоритм разделит заданный набор точек в некотором пространстве на группы точек, которые лежат друг от друга на малом расстоянии. Объекты, которые лежат отдельно от скоплений с большой плотностью, будут помечены как шумовые.
 На вход алгоритму подаётся набор точек, параметры <tex>\epsilon</tex> (радиус окружности) и <tex>m</tex> (минимальное число точек в окрестности). Для выполнения кластеризации потребуется поделить точки на четыре вида: основные точки, прямо достижимые, достижимые и шумовые.

← Предыдущая		Версия 20:23, 13 января 2021
Строка 171:		Строка 171:

	Рассмотрим код:		Рассмотрим код:
		+
	Пусть для каждого <tex>x \in X^m</tex> имеем посчитанной его <tex>\epsilon</tex>-окрестность <tex>U_{\epsilon}(x) = \{x' \in X^m \: \| \: \rho(x, x') \lt \epsilon\}</tex>		Пусть для каждого <tex>x \in X^m</tex> имеем посчитанной его <tex>\epsilon</tex>-окрестность <tex>U_{\epsilon}(x) = \{x' \in X^m \: \| \: \rho(x, x') \lt \epsilon\}</tex>