20
правок
Изменения
Добавлен псевдокод некоторых алгоритмов кластеризации
* Подбор рекомендаций для пользователя на основе предпочтений других пользователей в данном кластере;
* Определение аномалий путем построения кластеров и выявления неклассифицированных объектов.
== Псевдокод некоторых алгоритмов кластеризации ==
=== Метод 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>
На вход алгоритму подаётся выборка <tex>X^m = \{ x_1, \dots, x_m \}</tex> и количество кластеров <tex>K = |Y|</tex>.
На выходе получаем центры кластеров <tex>\mu_a</tex> для кластеров <tex>a \in Y</tex>.
<tex>\mu_a := init(X^m)</tex> <font color="gray"># Инициализируем произвольно начальное приближение для центров кластеров <tex>a \in Y</tex></font>. (Можно наиболее удалённые друг от друга объекты выборки)
<tex>A := [ -1 \: | \: for \: x_i \in X^m ]</tex> <font color="gray"># Инициализируем массив отображений из объектов выборки в их кластеры</font>
<tex>changed := True</tex>
<font color="blue"><tex>while</tex></font> <tex>changed</tex>: <font color="gray"># Повторяем пока <tex>A_i</tex> изменяются</font>
<tex>changed := False</tex>
<font color="blue"><tex>for</tex></font> <tex>x_i \in X^m</tex>: <font color="gray"># Относим каждый <tex>x_i</tex> к ближайшему центру</font>
<tex>A_{i, old} := A_i</tex>
<tex>A_i := arg \min_{a \in Y} ||x_i - \mu_a||</tex>
<font color="blue"><tex>if</tex></font> <tex>A_i \neq A_{i, old}</tex>:
<tex>changed := True</tex>
<font color="blue"><tex>for</tex></font> <tex>a \in Y</tex>: <font color="gray"># Вычисляем новые положения центров</font>
<tex>\mu_a := \frac{\sum_{i = 1}^{m}[A_i = a] x_i}{\sum_{i = 1}^{m}[A_i = a]}</tex>
<font color="blue"><tex>return</tex></font> <tex>\mu_a, \: A</tex> <font color="gray"># Возвращаем центры кластеров и распределение по ним объектов выборки</font>
=== DBSCAN ===
На вход алгоритму подаётся выборка <tex>X^m = \{ x_1, \dots, x_m \}</tex>, параметры <tex>\epsilon</tex> и <tex>m</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>
<tex>A := [ -1 \: | \: for \: x_i \in X^m ]</tex> <font color="gray"># Инициализируем массив отображений из объектов выборки в их кластеры</font>
<tex>a := 0</tex> <font color="gray"># Количество кластеров</font>
<font color="blue"><tex>while</tex></font> <tex>U \neq \varnothing</tex>: <font color="gray"># Пока в выборке есть непомеченные объекты</font>
<tex>x := rand(U)</tex> <font color="gray"># Берём случайную непомеченную точку</font>
<font color="blue"><tex>if</tex></font> <tex>|U_{\epsilon}(x) < m|</tex>:
<tex>mark[x]</tex> <tex>:=</tex> "<tex>noise</tex>" <font color="gray"># Пометим <tex>x</tex> как, возможно, шумовой</font>
<font color="blue"><tex>else</tex></font>:
<tex>K := U_{\epsilon}(x)</tex>
<tex>a := a + 1</tex> <font color="gray"># Создадим новый кластер K</font>
<font color="blue"><tex>for</tex></font> <tex>x' \in K</tex>:
<font color="blue"><tex>if</tex></font> <tex>x' \in U</tex> || <tex>mark[x']</tex> <tex>==</tex> "<tex>noise</tex>": <font color="gray"># Если <tex>x'</tex> не помечен или помечен как шумовой</font>
<font color="blue"><tex>if</tex></font> <tex>|U_{\epsilon}(x')| \geq m</tex>:
<tex>mark[x'] :=</tex> "<tex>interior</tex>" <font color="gray"># Пометим <tex>x'</tex> как внутренний кластера <tex>K</tex></font>
<tex>K := K \cup U_{\epsilon}(x')</tex> <font color="gray"># Добавим вместе с <tex>x'</tex> всю его окрестность</font>
<font color="blue"><tex>else</tex></font>:
<tex>mark[x'] :=</tex> "<tex>frontier</tex>" <font color="gray"># Пометим <tex>x'</tex> как граничный кластера <tex>K</tex></font>
<font color="blue"><tex>for</tex></font> <tex>x_i \in K</tex>:
<tex>A_i := a</tex>
<tex>U := U \setminus K</tex>
<font color="blue"><tex>return</tex></font> <tex>a, \: A, \: mark</tex> <font color="gray"># Возвращаем количество кластеров, распределение по кластерам и метки объектов (внутренние, граничные или шумовые)</font>
== Пример кода ==
