Clusterization

Кластеризация — процесс разбиения заданной выборки объектов (наблюдений) на подмножества (как правило, непересекающиеся), называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов, а объекты разных кластеров существенно отличались.
Различные инструменты для кластеризации данных можно найти на веб-сайте Science Hunter.
Одной из целей кластеризации является выявление внутренних связей между данными путём определения кластерной структуры. Разбиение наблюдений на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятие решений, применяя к каждому кластеру свой метод анализа - “divide et impera” (стратегия «разделяй и властвуй»).
Одним из приложений кластеризации является решение задачи сжатия данных. В случае, если исходная выборка избыточно большая, то можно сократить её, оставив несколько наиболее характерных представителей от каждого кластера.
Другой сферой использования кластеризация является обнаружение новизны в исследуемом множестве объектов. Выделяются нетипичные объекты, которые не удаётся присоединить ни к одному из кластеров. Для решения задач методами кластерного анализа, необходимо задавать количество кластеров заранее. В одном случае число кластеров стараются сделать поменьше. В другом случае важнее обеспечить высокую степень сходства объектов внутри каждого кластера, а кластеров может быть сколько угодно. В третьем случае наибольший интерес представляют отдельные объекты, не вписывающиеся ни в один из кластеров.

Пусть множество объектов \(\Im=\left\{x_i\right\}_{i=1}^n\), представленных набором атрибутов \(x_i=\left\{t_1^i,t_2^i,...,t_m^i\right\}_{i=1}^n\), где \(t_\nu^i\) принимает значения из заданного множества \(T^i_\nu\).
Задача кластеризации состоит в построении множества C=\(\left\{C_\nu\right\}_{\nu=1}^k\) и отображения \(F:\Im\to\)C заданного множества объектов на множество кластеров.
Кластер содержит объекты из \(\Im\) похожие (по заданному критерию) друг на друга \(x_i\in C_\nu,x_j\in C_\nu \Rightarrow d(x_i,x_j)\lt\varepsilon\), где \(d(\bullet,\circ)\) степень схожести между объектами (чаще всего это расстояние), а ε - максимальное значение порога, формирующего один кластер.

Условно методы кластеризации разбиваются на два класса - иерархические и неиерархические.
В неиерархических алгоритмах присутствует наличие условия остановки и количества кластеров. Основой этих алгоритмов является гипотеза о сравнительно небольшом числе скрытых факторов, которые определяют структуру связи между признаками.
Иерархические алгоритмы не завязаны на количестве кластеров. Эта характеристика определяется по динамике слияния и разделения кластеров во время построения дерева вложенных кластеров (дендрограммы). В свою очередь, иерархические алгоритмы делятся на агломеративные, которые строятся путем объединения элементов, то есть уменьшением количества кластеров, и дивизимные, основанные на разделении (расщеплении) существующих групп (кластеров).

Иерархические алгоритмы.

Пусть имеем \(n\) точек в \(d\)-мерном пространстве. Целью иерархической кластеризации является создание последовательности вложенных разделов, которые можно удобно визуализировать с помощью дерева или иерархии кластеров, называемых кластерной дендрограммой.
Кластеры в иерархиях варьируются от мелкозернистого до крупнозернистого - самый низкий уровень дерева (листья) состоит из каждой точки в своем кластере, тогда как самый высокий уровень (корень) состоит из всех точек в одном кластере. Оба эти случая могут считаться тривиальными кластерами. На каком-то промежуточном уровне можно найти необходимые значимые кластеры. Если пользователю необходимое заданное количество кластеров \(k\), то можно выбрать уровень, на котором есть k кластеров.
Существует два основных алгоритмических подхода к иерархической кластеризации - агломеративный и дивизимный. Агломеративные стратегии работают снизу вверх, начиная с каждой из n точек в отдельном кластере, они пытаются объединить наиболее похожие пары кластеров, пока все точки не станут членами одного и того же кластера.
Дивизимные стратегии делают как раз наоборот, работая сверху вниз, начиная со всех точек в одном кластере, они рекурсивно разделяют кластеры, пока все точки не будут находится в отдельных кластерах.

Иерархические агломеративные алгоритмы.

Рассмотрим набор данных \(D = \{x_1, ..., x_n\}\), где \(x_i \in R^d\) и кластеризацию C = \(\{C_1, ..., C_k\}\), разделяющую множество \(D\), то есть каждый кластер представляет собой множество точек \(C_i \in D\), так что кластеры попарно не пересекаются CiCj = ∅ (для всех \(i\ne j\)) и \(\bigcup_{i=1}^kC_i=D\). Кластеризация \(A = \{A_1,..., A_r\}\) называется вложенной в другую кластеризацию \(B = \{B_1, ..., B_s\}\), если, как только \(r> s\) и для каждого кластера \(A_i \in A\) существует кластер \(B_j \in B\), такой, что \(A_i \subseteq B_j\). Иерархическая кластеризация дает последовательность из n вложенных множеств C1 , ..., Cn , начиная от тривиальной кластеризации C1 =\(\{\{x_1\}, ..., \{x_n\}\}\), где каждый элемент находится в отдельном кластере, до другой тривиальной кластеризации Cn =\(\{\{x_1, ..., x_n\}\}\), где все точки находятся в одном кластере. В общем случае кластеризация Ct-1 вложена в кластеризацию Ct .
Дендрограмма кластера представляет собой корневое двоичное дерево, которое описывает структуру вложенности с ребрами между кластерами CiCt-1 и кластером CjCt, если Ci вложено в Cj, т.е. если CiCj. Таким образом, дендрограмма захватывает всю последовательность вложенных кластеров.

Кластеризация областей Украины по размеру средней зарплаты на 2017 год

В агломерационной иерархической кластеризации процесс начинается с того, что каждой из n точек ставится в соответствие отдельный кластер. Далее идет итерационное объединение двух ближайших кластеров в один, пока все точки не будут членами одного и того же кластера.
Формально, учитывая набор кластеров C = \(\{C_1, C_2, ..., C_m\}\), найдем ближайшую пару кластеров \(C_i\) и \(C_j\) и объединим их в новый кластер \(C_{ij} = C_i \bigcup C_j\). Затем обновим набор кластеров, удалив \(C_i\) и \(C_j\) и добавим \(C_{ij}\): C =C\{{Ci}\(\bigcup\) {Cj}} \(\bigcup \){Cij}. Мы повторяем процесс до тех пор, пока C не будет содержать только один кластер. Поскольку на каждом шаге количество кластеров уменьшается на единицу, этот процесс приводит к последовательности n вложенных кластеров. По требованию можно остановить процесс объединения, когда осталось ровно k кластеров.

Алгоритм агломеративной иерархической кластеризации

  1. C ← {Ci = {xi} | xi ∈ D} // Каждая точка в отдельном кластере
  2. Δ ← {d(xi, xj): xi, xj ∈ D} // Вычислить матрицу расстояний
  3. повторить до |C| = k
Ключевым элементом алгоритма является определение ближайшей пары кластеров, то есть выбор критерия схожести. Как уже отмечалось, наиболее распространенным критерием схожести является метрика (расстояние). Некоторые из критериев схожести уже были рассмотрены. Заметим, что выбор этого критерия существенно сказывается на результате кластеризации.
В методе Уорда (Ward, J. H., Jr. (1963), "Hierarchical Grouping to Optimize an Objective Function", Journal of the American Statistical Association, 58, 236–244.) в качестве расстояния между кластерами берётся прирост суммы квадратов расстояний объектов до центров кластеров, получаемый в результате их объединения. На каждом шаге алгоритма объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, то есть внутригрупповой суммы квадратов. Этот метод направлен на объединение близко расположенных кластеров.
Расстояние между двумя кластерами определяется как увеличение суммы квадрата ошибок при объединении двух кластеров. Для данного кластера \(C_i\) ошибку можно записать следующим образом \[\sum_{x\in C_i}\|x-\mu_i\|^2=\sum_{x\in C_i}{x^Tx}-2\sum_{x\in C_i}{x^T\mu_i}+\sum_{x\in C_i}{\mu_i^T\mu_i}= \left(\sum_{x\in C_i}{x^Tx}\right)-n_i\mu_i^T\mu_i.\] Ошибка кластеризации C = {C1, ..., Cm} задается как \[\sum_{i=1}^m\sum_{x\in C_i}\|x-\mu_i\|^2\] Мера Уорда определяет расстояние между двумя кластерами \(C_i\) и \(C_j\) как изменение значения ошибки при объединении \(C_i\) и \(C_j\) в \(C_{ij}\), заданное как \[\delta(C_i,C_j)=\sum_{x\in C_{ij}}\|x-\mu_{ij}\|^2-\sum_{x\in C_i}\|x-\mu_i\|^2-\sum_{x\in C_j}\|x-\mu_j\|^2.\] Поскольку \(C_{ij} = C_i\) ∪ \(C_j\) и \(C_i\) ∩ \(C_j\) = ∅, мы имеем \(|C_{ij}|=n_{ij} = n_i + n_j\) и поэтому \[\delta(C_i,C_j)=\sum_{z\in C_{ij}}\|z-\mu_{ij}\|^2-\sum_{x\in C_i}\|x-\mu_i\|^2-\sum_{y\in C_j}\|y-\mu_j\|^2\] \[=\sum_{z\in C_{ij}}{z^Tz}-n_{ij}\mu_{ij}^T\mu_{ij}-\sum_{x\in C_{i}}{x^Tx}+n_{i}\mu_{i}^T\mu_{i}- \sum_{y\in C_{j}}{y^Ty}+n_{j}\mu_{j}^T\mu_{j}\] \[=n_{i}\mu_{i}^T\mu_{i}+n_{j}\mu_{j}^T\mu_{j}-(n_{i}+n_j)\mu_{ij}^T\mu_{ij}.\] Отсюда и из того факта, что \[\sum_{z\in C_{ij}}{z^Tz}=\sum_{x\in C_{i}}{x^Tx}+\sum_{y\in C_{j}}{y^Ty}\] сразу получаем \[ \mu_{ij}=\frac{n_i\mu_i+n_j\mu_j}{n_i+n_j}, \] тогда \[ \mu_{ij}^T\mu_{ij}=\frac{1}{\left(n_i+n_j\right)^2}\left(n_i^2\mu_{i}^T\mu_{i}+2n_in_j\mu_{i}^T\mu_{j}+n_j^2\mu_{j}^T\mu_{j}\right). \] Изменение значения ошибки при объединении кластеров примет вид \[\delta(C_i,C_j)=n_i\mu_{i}^T\mu_{i}+n_j\mu_{j}^T\mu_{j}- \frac{1}{\left(n_i+n_j\right)}\left(n_i^2\mu_{i}^T\mu_{i}+2n_in_j\mu_{i}^T\mu_{j}+n_j^2\mu_{j}^T\mu_{j}\right) \] \[ =\frac{1}{n_i+n_j}\left(n_i\left(n_i+n_j\right)\mu_{i}^T\mu_{i}+n_j\left(n_i+n_j\right)\mu_{j}^T\mu_{j}- n_i^2\mu_{i}^T\mu_{i}-2n_in_j\mu_{i}^T\mu_{j}-n_j^2\mu_{j}^T\mu_{j}\right) \] \[ =\frac{n_in_j\left(\mu_{i}^T\mu_{i}-2\mu_{i}^T\mu_{j}+\mu_{j}^T\mu_{j}\right)}{n_i+n_j} \] \[ =\frac{n_in_j}{n_i+n_j}\|\mu_i-\mu_j\|^2. \] Таким образом, мера Уорда является взвешенной версией среднего расстояния между кластерами, кстати, при использовании евклидова расстояния среднее расстояние можно переписать в виде \(\delta\left(\mu_{i},\mu_{j}\right)=\|\mu_i-\mu_j\|^2.\) Как видно, единственное отличие состоит в том, что мера Уорда изменяет расстояние между кластерами на половину гармонического среднего для размеров кластера \[ \frac{2}{\frac{1}{n_1}+\frac{1}{n_2}}=\frac{2n_1n_2}{n_1+n_2}. \]
Предложенная конструкция (А.А.Шумейко, С.Л.Сотник Использование агломеративной кластеризации для автоматической рубрикации текстов // Системні технології. Регіональний міжвузівський збірник наукових праць. – Випуск 3(74).- Дніпропетровськ, 2011, c. 131-137) в качестве степени похожести использует коэффициент обобщенной корреляции, и является естественным обобщением использования корреляции Пирсона.
На нижнем уровне построения дендрограммы будут пары элементов \(c_{i,j}=(x_i,x_j)\), характеризуемые коэффициентом обобщенной корреляции \[ d_{c}(x_i,x_j)=\frac{\sum_{\nu=1}^m\left(t_\nu^i-\bar{t}^i\right)\left(t_\nu^j-\bar{t}^j\right)\omega\left(x_i,x_j\right)} {\sqrt{\sum_{\nu=1}^m\left(t_\nu^i-\bar{t}^i\right)^2\sum_{\nu=1}^m\left(t_\nu^j-\bar{t}^j\right)^2}} \] где \(\omega\left(x_i,x_j\right)\) представляет собой весовую функцию общего вида, которая может зависеть как от конкретных элементов векторов, так и от каких-то их общих характеристик (например, норм векторов).
Среди всех элементов нижнего уровня выберем элемент с наибольшим коэффициентом обобщенной корреляции. Пусть это будет элемент \(c_{i,j}\). Для всех \(c_{i,\nu} (\nu\ne j)\) построим обобщенную корреляционную матрицу \[ \mathcal{R}_{i,j,\nu}= \left( \begin{array}{lll} d_{c}(x_i,x_i)& d_{c}(x_i,x_j)& d_{c}(x_i,x_\nu) \\ d_{c}(x_j,x_i)& d_{c}(x_j,x_j)& d_{c}(x_j,x_\nu) \\ d_{c}(x_\nu,x_i)& d_{c}(x_\nu,x_j)& d_{c}(x_\nu,x_\nu) \end{array} \right) \] Через \[ \Lambda=\mathcal{R}_{i,j,\nu}^{-1}= \left( \begin{array}{lll} \lambda_{i,i}& \lambda_{i,j}&\lambda_{i,\nu} \\ \lambda_{j,i}& \lambda_{j,j}&\lambda_{j,\nu} \\ \lambda_{\nu,i}& \lambda_{\nu,j}&\lambda_{\nu,\nu} \end{array} \right) \] Обозначим матрицу, обратную к ней. В качестве меры корреляции между \(x_i\), \(x_j\) и \(x_\nu\) будем использовать сводный коэффициент обобщенной корреляции \[ \rho_{i,j}=\sqrt{1-\frac{1}{\lambda_{i,j}d_{c}(x_i,x_j)}} \] Среди всех \(\rho_{i,j}\) выберем коэффициент \(\rho^0\) с наибольшим значением. Предполагая, что случайные величины имеют нормальное распределение, взаимосвязь между случайными величинами вычисляется в соответствии с критерием Стьюдента \[ \xi_{i,j,\nu}=\frac{1}{2}\ln{\frac{(1+d_{c}(x_i,x_j))(1-\rho^0)}{(1-d_{c}(x_i,x_j))(1+\rho^0)}}\sqrt{\frac{n-3}{2}}. \] Для наибольшего \(\xi_{i,j,\nu}\) из элементов нижнего уровня удалим \(с_{i,j}\) и \(с_{j,\nu}\). Полученная тройка \(c_{i,j,\nu}\) формирует элемент следующего уровня.
Далее этот процесс повторяем, в результате получаем дерево, определяемых только значением сводного коэффициента корреляции.
В качестве весовой функции использовалась функция вида \[ \omega\left(x_i,x_j\right)=2^n\left( \frac{\sqrt{\sum_{\nu=1}^m\left(t_\nu^i-\bar{t}^i\right)^2}} {\sqrt{\sum_{\nu=1}^m\left(t_\nu^j-\bar{t}^j\right)^2+\varepsilon}}+ \frac{\sqrt{\sum_{\nu=1}^m\left(t_\nu^j-\bar{t}^j\right)^2}} {\sqrt{\sum_{\nu=1}^m\left(t_\nu^i-\bar{t}^i\right)^2+\varepsilon}}+\varepsilon \right)^{-n}. \] Данный вид весовой функции позволил выделять взаимосвязанные элементы при сравнительно небольшом шуме. Здесь \(\varepsilon\)- небольшое число, например \(10^{-6}\), необходимое, чтобы избежать деления на ноль. Параметром \(n\) можно регулировать крутизну наклона характеристики.

Дивизимная иерархическая кластеризация

Этот вид кластеризации является менее распространенной кластеризацией, он работает аналогично агломерационной кластеризации, но в противоположном направлении. Дивизионная иерархическая кластеризация начинается с одного кластера, содержащего все объекты данных. Начальный кластер делится на два кластера так, что объекты данных в одном кластере далеки от объектов данных в другом, затем метод последовательно разбивает результирующие кластеры до тех пор, пока каждый элемент не будет находится в своем собственном кластере.
Одним из наиболее известных дивизимной кластеризации является алгоритм DIANA ( L. Kaufman and P. Rousseeuw, Finding Groups in Data: An Introduction to Cluster Analysis, J. Wiley and Sons, New York, 1990.). Алгоритм DIANA основан на расстоянии между объектом \(x_i\) и кластером \(C_k\). Расстояние определяется следующим образом \[ d(x_i,C_k)=\left\{ \begin{array}{ll} \frac{1}{|C_k|-1}\sum_{x_j\in C_k,j\neq i}d(x_i,x_j), & x_i\in C_k, \\ \frac{1}{|C_k|}\sum_{x_j\in C_k}d(x_i,x_j), & x_i\notin C_k. \end{array} \right. \] Опять же, \(|C_k|\) - количество объектов данных в кластере \(C_k\).
Алгоритм дивизимной иерархической кластеризации DIANA на каждом шаге определяем кластер, содержащий два объекта данных с самым большим расстоянием и разделяет их.

Неиерархические алгоритмы.

Неиерархические алгоритмы приобрели большую популярность, ввиду того, что в их основе лежит та или иная задача оптимизации, то есть группирование исходного множества объектов в кластеры является решением некоторой экстремальной задачи. Рассмотрим несколько наиболее популярных методов.
Одним из самых популярных методов численного анализа является метод наименьших квадратов. Для задачи кластеризации он выглядит следующим образом \[\sum_{j=1}^k\sum_{i=1}^{n_i}\left|x_i-s_j\right|^2\to\min\] по всем si и k.
Численная реализация этой задачи называется методом k-средних (McQueen J. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 281–297.).

Метод k-средних.

Идея метода состоит в следующем - вначале выбирается k произвольных исходных центров из множества \(\Im\). Далее все объекты разбиваются на k групп, наиболее близких к соответствующему центру. На следующем шаге вычисляются центры найденных кластеров. Процедура повторяется итерационно до тех пор, пока центры кластеров не стабилизируются.
Алгоритм разбиения объектов xi (i=0,1,…,n) основан на минимизации межкластерного расстояния, в случае, если в качестве расстояния используется среднеквадратичная норма ℓ2, то есть целевой функцией является \[ J=\sum_{j=1}^k{\sum_{x_i\in C_j}\|x_i-\mu_j\|^2}, \] где xi-i-й объект, а cj представляет собой j-й кластер с центром μj.
Структура алгоритма состоит в следующем:
  1. Для инициализации алгоритма выбираем k центров кластеров.
  2. Каждому из n объектов ставим в соответствие кластер, исходя из минимизации ℓ2 нормы между объектом и центром соответствующего кластера.
  3. Пересчитываем центры вновь полученных кластеров
    Для решения этой задачи среди всех элементов кластера \(x\in C_j\) найдем элемент \(\mu_j\), минимизирующий уклонение \(\sum_{x\in C_j}\|x-\mu_j\|^2_2\), для чего найдем решение задачи \[\frac{\partial}{\partial \mu_j}\sum_{x\in C_j}\|x-\mu_j\|^2_2=\frac{\partial}{\partial \mu_j}\sum_{x\in C_j}\left(\|x\|^2_2-2x^T\mu_j+\|\mu_j\|^2_2\right)= \sum_{x\in C_j}(-x+\mu_j)=0, \] то есть
    \[ \mu_j=\frac{1}{n_j}\sum_{x\in C_j}x. \]
  4. Для каждого i, такого, что xiCj вычислим \[ h=arg min\left\{\frac{n_j\|x_i-\mu_j\|_2}{n_j-1}\right\}, \] где nj число объектов кластера Cj.
  5. Если выполняется условие \[ \frac{n_h\|x_i-\mu_h\|_2}{n_h-1}<\frac{n_j\|x_i-\mu_j\|_2}{n_j-1}, \] то следует переместить объект xi из кластера Cj в кластер Ch, после чего пересчитать значения центров кластеров.
  6. Если i< n, то переходим к шагу 4, иначе к шагу 3.
Критерием остановки алгоритма может служить либо достижение заданного числа итераций алгоритма, либо достижение функцией цели заданного значения порога.

Метод эффективен в случае, если данные делятся на компактные группы, которые можно описать сферой.

позволяет упростить запись базового алгоритма и записать в следующем виде:
Пусть C=\(\left\{C_\nu\right\}_{\nu=1}^k\) множество кластеров с центрами \[ \mu_\nu=\frac{\sum\left\{x_i\left|x_i\in C_\nu\right.\right\}}{\sum\left\{1\left|x_i\in C_\nu\right.\right\}}= \frac{\sum_{i=1}^nu_i^\nu x_i}{\sum_{i=1}^nu_i^\nu}, \] где \(u_i^\nu\) индикаторная функция, то есть \[ u_i^\nu=\left\{ \begin{array}{ll} 1, & если &x_i\in C_\nu, \\ 0, & если &x_i\notin C_\nu, \end{array} \right. \] Целевая функция \[ J^\nu(C,\Im)=\sum_{\nu=1}^k\sum_{i=1}^n u_i^\nu d(x_i,\mu_\nu), \] и условия \[ \sum_{\nu=1}^k u_i^\nu \le n, \sum_{i=1}^n u_i^\nu =1. \] то есть, каждый элемент может быть только в одном кластере, и, кластер не может быть пустым или содержать элементов больше, чем их исходное количество.
Условие остановки выполнения алгоритма после ν-го шага будет иметь вид \[ \left|J^\nu(C,\Im)-J^{\nu-1}(C,\Im)\right|<\varepsilon, \] где ε выбранный порог.
Заметим, что при вычислении критерия принадлежности, можно учитывать размер кластера, что позволяет улучшить эффективность алгоритма. Критерий того, что i-й элемент принадлежит j-му, а не m-му кластеру будет иметь вид: \[ \frac{n_j}{n_j-1}d\left(x_i,\mu_j\right)<\frac{n_m}{n_m-1}d\left(x_i,\mu_m\right), \] где ni количество элементов, соотнесенных кластеру ci. Скорость сходимости метода -O(n).

Недостатки метода.

К недостаткам этого метода, прежде всего, нужно отнести:

К-во кластеров










Визуализация данных является важным элементом анализа числовой информации. В визуализации относятся - диаграммы разного вида, графики и, конечно, инфографика.
Инфографика позволяет связать разнородные данные и представить их в удобном, визуальном виде. Проблема связывания данных разной природы сама по себе нетривиальна, и не может быть единого, универсального подхода.
Рассмотрим применение кластеризации к построению инфографики.
Задача состоит в кластеризации данных, которые представляют собой независимую слувайную величину, закон распределения которой неизвестен. В качестве этого примера используются данные о том, куда переселились беженцы с Донбасса и Крыма. Переселение людей представляет собой независимую случайную величину. При этом, нужно учесть, что если центры кластеров можно найти, используя традиционный метод k- средних, то размеры кластера, определяемые разрешающим правилом, зависят от количества беженцев в том или ином кластере. Для построения кластеров было решено использовать множество многоугольников Парето, причем размеры многоугольника вычисляются попарно с соседними элементами в отношении \(|C_i|/|C_j|\), где \(|C_i|\)- количество беженцев в i-м кластере. Таким образом чем больше площадь многоугольника, определяющего кластер, тем более этот район предпочтителен беженцами.

Регионы, в которых осели беженцы из Донбасса




Количество кластеров

Модификации метода k-средних

Еще одна из модификаций k- средних. Отличие состоит в том, что под близостью элементов в кластере понимается покрытие их сферой заданного радиуса.
Схема работы алгоритма состоит в следующем - берется центр кластера (на первом шаге это произвольный элемент), и, к кластеру приписываются все элементы, которые удалены от центра не более чем на заданное расстояние R. Потом пересчитывается центр, в качестве которого берется средняя точка полученного кластера, и, заново пересчитываются элементы кластера. Так продолжается до тех пор, пока центр не стабилизируется.
Медоид — элемент, принадлежащий набору данных или кластеру, различие которого с другими элементами в наборе данных или кластере минимально. В отличие от центроида (центр масс кластера), используемых в методе k-средних, медоиды являются элементом, принадлежащим кластеру, и как правило используются в тех случаях, когда невозможно использовать средние координаты или центр масс кластера.
Метод кластеризации k-medoids на каждой итерации ищет центры кластеров не как среднее значение элементов кластера, а как их медоиды, таким образом, центр кластера должен обязательно совпадать с одним из его элементов.

PAM (Partitioning Around Medoids) алгоритм метода k- medioids (Kaufman and Rousseeuw (1990)).

  1. Для инициализации на первом шаге нужно произвольно выбрать k элементов из данных в качестве медоидов.
  2. Рассмотрим замену пары объектов xi, xh, где xi из множества выбранных объектов и xh из невыделенных объектов. Обозначим этот обмен как i ↔ h . Пусть d(xi; xh) - расстояние между двумя элементами xi и xh.
    Теперь рассмотрим еще один невыбранный объект xj.
    Пусть Ti,h=∑jsj,i,h общий вклад обмена i ↔ h , где sj,i,h - вклад в i ↔ h из объекта xj.
    При вычислении sj,i,h существует четыре возможности.
    • Если xj принадлежит кластеру, определенному медоидом xi, тогда в качестве вклада рассмотрим расстояние d(xj; xh) между xj и xh.
    • Если xh дальше от xj, чем вторая лучшая медоида xi0 из j-го кластера, то вклад объекта xj в Ti,h равен sj,i,h=d(xj; xi0)-d(xj; xi)
      Результатом i ↔ h было бы то, что теперь объект xj принадлежит кластеру i0. Иначе, если xh ближе к xj, чем xi0 к xj, вклад xj в Ti,h равен sj,i,h=d(xj; xh)-d(xj; xi).
      Результатом i ↔ h было бы то, что теперь объект xj принадлежит кластеру h.
    • Если xj принадлежит кластеру k, где k ≠ i, используем расстояние d(xj; xh).
    • Если xh дальше от xj, чем медоид k из j, то вклад от объекта xj равен sj,i,h=0.
      Результатом i ↔ h было бы то, что объект xj все еще принадлежит кластеру k. Иначе, если xh ближе к xj, чем xk к xj, вклад xj равен sj,i,h=d(xj; xh)-d(xj; xk).
      Результатом i ↔ h было бы то, что теперь объект xj принадлежит кластеру h.
  3. Пусть (i*; h *) = arg mini,h Ti,h. Если Ti*,h* <0, то нужно произвести замену i * ↔ h * . Теперь объект xh будет в множестве выбранных объектов и xi из невыбранных.
  4. Перейти к шагу 2.
  5. Поставить в соответствие каждый невыбранный объект кластеру, определенному ближайшим медоидом.
Самым привлекательным свойством этого метода является его надежность. Использование медоидов для определение кластеров делает этот метод очень устойчивым к выбросам в данных. Для этого не нужно хранить большой объем информации в дополнение к исходным данным, все, что для этого требуется, так это метка выбранного объекта.

Алгоритм k-медоидов имеет ряд недостатков, а именно:


Иллюстрация сравнения работы алгоритмов k-средних и k- medioids.

Fuzzy C-Means (FCM)

Для классических методов кластеризации существует эффект «бабочки», который характеризуется тем, что несколько элементов исходного набора данных относятся к большему чем один количеству кластеров. В этом случае использование нечетких алгоритмов позволяет построить более эффективные методы, чем четкие.
Нечеткая кластеризация играет важную роль в решении проблем в областях распознавания образов и нечеткой идентификация модели. Алгоритм FCM больше подходит для данных, которые более или менее равномерно распределены вокруг кластерных центров. и позволяет использовать принадлежность части данных двум или более кластерам. Этот метод, разработанный Dunn (1. Dunn, J.C. 1973. A fuzzy relative of the ISODATA process and its use in detecting compact well separated clusters. Journal of Cybernetics, 3, pp.32-57.) и улучшенный Bezdek (2. J.C. Bezdek, “Pattern Recognition with Fuzzy Objective Function Algorithms”, New York: Prenum Press, 1981, 256 p.) часто используется при распознавании образов. Он основан на минимизации следующей функции \[ J_m=\sum_{i=1}^n\sum_{j=1}^Cu^m_{i,j}d^2(x_i,c_j), \] где \(m (1\le m\le \infty)\) - любое действительное число, большее 1, которое характеризует нечеткую степень принадлежности элемента кластеру, \(u_{i,j}\)- степень принадлежности элемента \(x_i\) j-му кластеру, \(c_j\)- центр кластера и \(d(\bullet,\circ)\)- любая норма, выражающая сходство между любыми измеряемыми данными.

Для степени принадлежности \(u_{i,j}\) элемента \(x_i\) кластеру с центром \(c_j\) естественно выполнение условия \( \sum_{j=1}^Cu_{i,j}=1, \) то есть каждый элемент наверняка лежит в каких-то кластерах.

Алгоритм FCM состоит из следующих шагов:

  1. Пусть нужно сгруппировать известные данные \(x_i(i = 1, 2, ..., n)\).
  2. Предположим, что количество кластеров известно и равно \(C\), где \(2 \le C \le n\).
  3. Выберем подходящий уровень нечеткости кластера \(m\gt 1\).
  4. Инициализировать матрицу принадлежности \(U=\{u_{i,j}\}\) случайным образом, так, чтобы \(u_{i,j}\in [0,1]\) и \(\sum_{j=1}^Cu_{i,j}=1\) для каждого \(i\) и фиксированного значения \(m\).
  5. Определить центры кластеров \(c_j\): \[ c_j=\frac{\sum_{i=1}^nu^m_{i,j}x_i}{\sum_{i=1}^nu^m_{i,j}} \]
  6. Найти степень сходства между \(i\)-й точкой данных и центом \(j\)-го кластера \(d(x_i,c_j)\)
  7. Обновить матрицу нечеткой принадлежности \(U\). Если \(u_{i,j}>0\) \[ u_{i,j}=\left(\sum_{k=1}^C\left(\frac{d^2(x_i,c_j)}{d^2(x_i,c_k)}\right)^{\frac{1}{m-1}}\right)^{-1}. \] Если \(u_{i,j}=0\), то точка данных совпадает с соответствующей точкой данных и имеет полное значение принадлежности, то есть \(u^m_{i,j}=1\).
  8. Если выполнится условие \( \max_{i,j}\left|u_{i,j}(k+1)-u_{i,j}(k)\right|\lt\varepsilon, \) где \(\varepsilon\) -критерий завершения и k - этапы итерации, то итерацию прекратить, иначе перейти к шагу 5.

Эта процедура сходится к локальному минимуму или к седловой точке. Седловая точка – это точка в области функции, являющейся стационарной точкой, но не локальным экстремумом.
Для приведенных результатов значение m характеризует нечеткую принадлежность элемента кластеру и при \(m\to 1\) данный алгоритм дает четкую принадлежность.
FCM является одним из самых популярных методов нечеткой кластеризации.

Как уже отмечалось, метод Fuzzy C-Means сводится к решению экстремальной задачи \[ J_m=\sum_{i=1}^n\sum_{j=1}^Cu^m_{i,j}d^2(x_i,c_j)\to\min \] при выполнении условия \(\sum_{j=1}^Cu_{i,j}=1\) для каждого \(x_i\).
Для ее решения выпишем функцию Лагранжа \[ L\left(\left\{u_{i,j}\right\},\left\{\lambda_{i}\right\}\right)= \sum_{i=1}^n\sum_{j=1}^Cu^m_{i,j}d^2(x_i,c_j)+\sum_{i=1}^n\lambda_i\left(1-\sum_{j=1}^Cu^m_{i,j}\right) \] и найдем ее производные \[ \frac{\partial}{\partial u_{\nu,\mu}}L\left(\left\{u_{i,j}\right\},\left\{\lambda_{i}\right\}\right)= 1-\sum_{j=1}^Cu^m_{i,j}, \] \[ \frac{\partial}{\partial\lambda_i}L\left(\left\{u_{i,j}\right\},\left\{\lambda_{i}\right\}\right)= m\cdot u^{m-1}_{\nu,\mu}d^2(x_i,c_j)-\lambda_\nu, \] и приравняем их нулю.
Из последнего соотношения получаем \[ u_{\nu,\mu}=\left(\frac{\lambda_\nu}{m\cdot d^2(x_\nu,c_\mu)}\right)^{\frac{1}{m-1}}, \] а из первого \[ 1=\sum_{j=1}^Cu_{i,j}=\sum_{j=1}^C\left(\frac{\lambda_i}{m\cdot d^2(x_i,c_j)}\right)^{\frac{1}{m-1}}= \left(\frac{\lambda_i}{m}\right)^{\frac{1}{m-1}}\sum_{j=1}^C\left(\frac{1}{d^2(x_i,c_j)}\right)^{\frac{1}{m-1}}. \] Таким образом, для любого \(x_i\) \[ \left(\frac{\lambda_i}{m}\right)^{\frac{1}{m-1}}= \left(\sum_{j=1}^C\left(\frac{1}{d^2(x_i,c_j)}\right)^{\frac{1}{m-1}}\right)^{-1}. \] Отсюда получаем значение принадлежности элемента \(x_\nu\) кластеру с центром \(c_\mu\) \[ u_{\nu,\mu}=\left(\sum_{j=1}^C\left(\frac{1}{d^2(x_\nu,c_j)}\right)^{\frac{1}{m-1}}\right)^{-1} \left(\frac{1}{d^2(x_\nu,c_\mu)}\right)^{\frac{1}{m-1}}= \left(\sum_{j=1}^C\left(\frac{d^2(x_\nu,c_\mu)}{d^2(x_\nu,c_j)}\right)^{\frac{1}{m-1}}\right)^{-1}. \] Отсюда сразу следует описанный ранее итерационный алгоритм Fuzzy C-Means.

Кластеризация Гюстафсона-Кесселя

Кластеризация данных с помощью классического метода k-средних не дает удовлетворительных результатов в силу ряда недостатков методов связанных, в первую очередь, с использованием евклидовой метрики и игнорирования статистической зависимости между признаками, по которым осуществляется кластеризация.
В случае использования выборок, имеющих несферические классы, применение «классического» метода k-средних приводит к неверным результатам (формируются «лишние» классы либо сливаются априорно различные классы в зависимости от выбора мер точности и грубости), в связи с тем, что в алгоритме используется «сферическое» евклидово расстояние (см. рисунок ниже).
На рисунке отражены результаты кластеризации двумерной выборки с тремя сильно вытянутыми кластерами (то есть высокой степенью корреляции между признаками): большие точки – центры кластеров, полученных классическим методом k-средних.
,
Одним из методов устранения такого рода недостатков классического метода k-средних является использование метода кластеризации Гюстафсона-Кесселя. Этот метод отличается от "классического" метода, предложенного МакКвином, использованием вместо метрики Евклида, расстояния Махалонобиса \[\|x_i-x_j\|_M=\sqrt{(x_i-x_j)^T\Sigma^{-1}(x_i-x_j)},\] где Σ корреляционная матрица. Использование метрики Махаланобиса позволяет учитывать статистическую зависимость между признаками наблюдений и при наличии этой зависимости, улучшить качество кластеризации.

Как и для метода \(k\)-средних, алгоритм Гюстафсона-Кесселя итерационный.
Для стартового множества \(u_{i,\nu}^m\) (центры могут быть выбраны каким-либо регулярным способом) и ковариационной матрицы, например, со значением определителя, равным единице, то есть \(\sigma_\nu=1\), проведем следующие шаги

  1. Найдем центры кластеров \[\mu_\nu=\frac{\sum_{i=1}^nu_{i,\nu}^m x_i}{\sum_{i=1}^nu_{i,\nu}^m},\]
  2. Вычислим ковариационную матрицу \[ F_\nu=\frac{\sum_{i=1}^nu_{i,\nu}^m (x_i-\mu_\nu)^T (x_i-\mu_\nu)}{\sum_{i=1}^nu_{i,\nu}^m}. \]
  3. Определим для \(i=1,...,n; \nu=1,...,k\) расстояния \[ d^2_M(x_i,\mu_\nu)=(x_i-\mu_\nu)^T \sigma_\nu det(F_\nu)^{1/k}F_\nu^{-1} (x_i-\mu_\nu) \]
  4. Найдем значения индексной функции:
    если \(d_M(x_i,\mu_\nu)>0\) для \(\nu=0,1,...,k\), то \[ u_{i,\nu}=\left(\sum_{j=1}^k\left(\frac{d_M(x_i,\mu_\nu)}{ d_M(x_i,\mu_j)}\right)^{\frac{2}{m-1}}\right)^{-1}. \] иначе \(u_{i,\nu}=0\).
Процесс повторяется до стабилизации центров кластеров.
Для кластеризации Гюстафсона-Кесселя требуется решить следующую экстремальную задачу: \[ J=\sum_{\nu=1}^k\sum_{i=1}^nu_{i,\nu}^m \delta_M(x_i,\mu_\nu)\to\min, \] где \[\delta_M(x_i,\mu_\nu)=(x_i-\mu_\nu)^TM_\nu (x_i-\mu_\nu),\] и \[ \sum_{\nu=1}^ku_{i,\nu}=1,\forall i=1,...,n, \sum_{i=1}^nu_{i,\nu}>0,\forall \nu=1,...,k, det(M_\nu)=\left|M_\nu\right|=\sigma_\nu. \] Для решения этой задачи выпишем функцию Лагранжа \[ L=\sum_{\nu=1}^k\sum_{i=1}^n u_{i,\nu}^m \delta_M(x_i,\mu_\nu)+\lambda\left(\sum_{\nu=1}^ku_i^\nu-1\right)+\Lambda \left(\left|M_\nu\right|-\sigma_\nu\right) \]

Возьмем частные производные по неизвестным и приравняем их нулю. Из \(\frac{\partial L}{\partial u_{i,\nu}}=0\) получаем \[ u_{i,\nu}=\left(\sum_{j=1}^k\left(\frac{m\cdot \delta_M(x_i,\mu_\nu)}{m\cdot \delta_M(x_i,\mu_j)}\right)^{\frac{1}{m-1}}\right)^{-1}, \] из \[ \frac{\partial L}{\partial M_\nu}=\sum_{i=1}^nu_{i,\nu}^m(x_i-\mu_\nu)^T (x_i-\mu_\nu)+\Lambda |M_\nu|M_\nu^{-1}=0, \] получаем \[ M_\nu=|F_\nu|^{1/k}\sigma_\nu^{1/k}F_\nu^{-1},\] где \[ \mu_\nu=\frac{\sum_{i=1}^nu_{i,\nu}^m x_i}{\sum_{i=1}^nu_{i,\nu}^m} и F_\nu=\frac{\sum_{i=1}^nu_{i,\nu}^m (x_i-\mu_\nu)^T (x_i-\mu_\nu)}{\sum_{i=1}^nu_{i,\nu}^m}. \] Таким образом приходим к описанному итерационному алгоритму.
Все алгоритмы, основанные на методе наименьших квадратов, в том числе, k-средних и с-средних, весьма чувствительны к шуму и к выбросам. В этом случае, алгоритм пытается учесть все имеющиеся данные, что приводит к искажению общей картинки распределения данных. R.N.Dave (R. N. Dave, Charaсterization and deteсtion of noise in сlustering", Pattern Reсognition Lett., vol. 12, no. 11, pp. 657-664, 1991.) была предложена идея представить шум как отдельный класс, который имеет постоянное расстояние \(\delta\) от всех векторов признаков. Значение принадлежности \(\tilde{u}_i\) вектора \(x_i\) кластеру шума, определена следующим образом \[ \tilde{u}_i=1-\sum_{j-1}^Cu_{i,j},i=1,...,n. \] Поэтому ограничение принадлежности для «хороших» кластеров ослабляется до \[ \sum_{j-1}^Cu_{i,j}\lt 1,i=1,...,n. \] Это позволяет зашумленным данным и выбросам иметь сколь угодно малые значения принадлежности в хороших кластерах. Для данного случая целевая функция примет вид \[ J\left(\left\{u_{i,j}\right\}\}\right)= \sum_{i=1}^n\sum_{j=1}^Cu^m_{i,j}d^2(x_i,c_j)+\sum_{i=1}^n\delta^2\left(1-\sum_{j=1}^Cu_{i,j}\right)^m. \] Минимизируя целевую функцию, получаем \[ u_{i,j}= \left(\sum_{k=1}^C\left(\frac{d^2(x_i,c_j)}{d^2(x_i,c_k)}\right)^{\frac{1}{m-1}}+ \left(\frac{d^2(x_i,c_j)}{\delta^2}\right)^{\frac{1}{m-1}}\right)^{-1}. \] Второе слагаемое в знаменателе становится довольно большим для выбросов, что приводит к небольшим значениям принадлежности для выбросов во всех хороших кластерах при условии нахождения подходящего значения для постоянного расстояния \(\delta\).

Относительная энтропия и нечеткая кластеризация.

Другой подход к задаче кластеризации зашумленных данных заключается в том, что относительная энтропия добавляется к целевой функции в качестве функции регуляризации, чтобы максимизировать несходство между кластерами. Рассмотрим функцию \[ H_n\left(\left\{u_{i,j}\right\}\right)= \sum_{i=1}^n\sum_{j=1}^Cu_{i,j}d^2(x_i,c_j)+w\sum_{i=1}^n\sum_{j=1}^Cu_{i,j}\log{u_{i,j}}, \] где \(n>0,\left\{u_{i,j}\right\}\) принадлежность вектора \(x_i j\)-му кластеру и \(d^2(x_i,c_j)\)- степень сходства \(x_i\) и центра соответствующего кластера, при этом выполняются условия \(\sum_{j=1}^Cu_{i,j}=1\) для любого \(i\), а также \(0\lt \sum_{i=1}^nu_{i,j}\lt n\) для любого \(j\).
Эти условия обозначают, что каждый элемент принадлежит какому-то кластеру из С, и ни один из кластеров не пуст.
Первое слагаемое в правой части \(H_n\left(\left\{u_{i,j}\right\}\right)\) представляет собой функцию цели для строгой (четкой) кластеризации, а со вторым слагаемым сейчас разберемся. Рассмотрим функцию \[ E(U)=-\sum_{i=1}^n\sum_{j=1}^Cu_{i,j}\log{u_{i,j}}, \] где \(U=\left\{u_{i,j}\right\}\).
Функция \(E (U)\) принимает максимальное значение при \(u_{i,j}=C^{-1}\) для любого \(j\), и минимальное, если для любого \(\nu=1,2,...,C\) \[ u_{i,j}=\left\{ \begin{array}{ll} 1, & j=\nu, \\ 0, & j\ne \nu . \end{array} \right. \] Для минимизации функции \(H_n\left(\left\{u_{i,j}\right\}\right)\), с учетом рассмотренных ограничений, выпишем функцию Лагранжа \[ L\left(\left\{u_{i,j}\right\},\left\{\lambda_{i}\right\}\right)= \sum_{i=1}^n\sum_{j=1}^Cu_{i,j}d^2(x_i,c_j)+ w\sum_{i=1}^n\sum_{j=1}^Cu_{i,j}\log{u_{i,j}}+ \sum_{i=1}^n\lambda_i\left(\sum_{j=1}^Cu_{i,j}-1\right) \] Для нахождения экстремума найдем частные производные по \(u_{i,j}\) и по \(\lambda_j\) и приравняем нулю, в результате получим систему \[ \left\{ \begin{array}{ll} \frac{\partial}{\partial u_{i,j}}L\left(\left\{u_{i,j}\right\},\left\{\lambda_{i}\right\}\right)= d^2(x_i,c_j)+w(1+\log{u_{i,j}})+\lambda_j=0, \\ \frac{\partial}{\partial \lambda_{j}}L\left(\left\{u_{i,j}\right\},\left\{\lambda_{j}\right\}\right)= \sum_{j=1}^Cu_{i,j}-1=0. \end{array} \right. \] Отсюда \[ \log{u_{i,j}}=-\frac{d^2(x_i,c_j)+\lambda_{j}}{w}-1, \] что эквивалентно \[ u_{i,j}=S_j\exp\left(-\frac{d^2(x_i,c_j)}{w}\right)=S_j\left(\exp\left(d^2(x_i,c_j)\right)\right)^{-\frac{1}{N}}, S_j=\exp\left(-1-\frac{\lambda_j}{w}\right). \] Отсюда и из условия \(\sum_{j=1}^Cu_{i,j}=1\), получаем нормализованные значения принадлежности \[ \bar{u}_{i,j}=\left(\sum_{k=1}^C\left(\frac{\exp\left(d^2(x_i,c_j)\right)}{\exp\left(d^2(x_i,c_k)\right)}\right)^{\frac{1}{w}}\right)^{-1}. \] Таким образом, имеем \( 0\le \bar{u}_{i,j}\le 1\) , то есть, значения принадлежности нечеткие и, следовательно, получаем нечеткое разбиение на кластеры. В этом случае функция \(E(U)\) называется функцией нечеткой энтропии. Кластеры рассматриваются как нечеткие множества, а функция нечеткой энтропии выражает неопределенность в определении того, принадлежит ли \(x_i\) к данному кластеру или нет. Другими словами, функция \(E (U)\) выражает среднюю степень непринадлежности элементов в нечетком множестве (D.Tran, M. Wagner, Fuzzy entropy clustering, in: The Ninth IEEE International Conference on Fuzzy System, FUZZ IEEE, vol. 1, 2000, pp. 152–157).

Степень нечеткой энтропии \(w\)

Весовой коэффициент \(w> 0\), который также определяет разбиение на кластеры, называется степенью нечеткой энтропии. Рассмотрим следующие частные случаи

Вероятностная кластеризация.

Кластеризация может быть связана с вероятностной кластеризацией путем определения расстояния \[ d^2(x_i,c_j)=-\log P\left(\left. x_i,c_j\right|\theta\right)=-\log \left(\omega_jN(x_i,\mu_j,\Sigma_j)\right), \] где \(P\left(\left. x_i,c_j\right|\theta\right)\) - совместная вероятность \(j\)-го кластера и данных \(x_i\), \(\omega_j\)- вес смеси, \(\mu_j\)- среднее значение, \(\Sigma_j\) ковариационная матрица и \(N(x_i,\mu_j,\Sigma_j)\) Гауссиан в \(d\)-мерном пространстве \[ N(x_i,\mu_j,\sigma_j)=\frac{1}{(2\pi)^{d/2}\left|\Sigma_j\right|^{1/2}} \exp\left(-\frac{1}{2}\left(x_i-\mu_j\right)^T\Sigma^{-1}_j\left(x_i-\mu_j\right)\right), \] здесь \(\left|\Sigma_j\right|\) определитель матрицы \(\Sigma_j\).
Перепишем введенное расстояние \[ d^2(x_i,c_j)=\left(x_i-\mu_j\right)^T\Sigma^{-1}_j\left(x_i-\mu_j\right)-\log{\omega_j}+\frac{d}{2}\left(2\pi\left|\Sigma_j\right|\right). \] Выписывая, аналогично предыдущему, функцию цели, и минимизируя ее, получаем \[ \bar{u}_{i,j}=\frac{P^{1/w}\left(\left. x_i,c_j\right|\theta\right)}{\sum_{k=1}^CP^{1/w}\left(\left. x_i,c_k\right|\theta\right)}, \bar{\omega}_j=\frac{1}{n}\sum_{i=1}^n\bar{u}_{i,j}, \bar{\mu}_j=\frac{\sum_{i=1}^n\bar{u}_{i,j}x_i}{\sum_{i=1}^n\bar{u}_{i,j}}, \bar{\Sigma}_j=\frac{\sum_{i=1}^n\bar{u}_{i,j}\left(x_i-\bar{\mu}_j\right)^T\left(x_i-\bar{\mu}_j\right)}{\sum_{i=1}^n\bar{u}_{i,j}}. \] Коэффициент \(\bar{\omega}_j\) называется весом нечеткой смеси и характеризует плотность данных в \(j\)-м кластере.
Следует отметить, что при \(w = 1\) значение \(\bar{u}_{i,j}\) становится равным \[ \bar{u}_{i,j}=\frac{P\left(\left. x_i,c_j\right|\theta\right)}{\sum_{k=1}^CP\left(\left. x_i,c_k\right|\theta\right)}= P\left(\left. x_i,c_j\right|\theta\right), \] где \(P\left(\left. x_i,c_j\right|\theta\right)\) - апостериорная вероятность в гауссовой кластерной смеси. Поэтому можно сказать, что при \(w = 1\) и использовании данного расстояния, нечеткая кластеризация сводится к разделению гауссовой смеси. Другими словами, разделение гауссовой смеси можно рассматривать как метод нечеткой кластеризации.
Этот пример имеет принципиально иную природу от рассмотренного ранее.
Есть высшие учебные заведения и научно-исследовательские институты, нужно определить регионы Украины тяготеют к которым научным центрам.
Решение этой задачи связано с тем, что данные не является независимой случайной величиной. Если в регионе малое число учебных заведений, то откуда взяться ресурсу для роста научной деятельности. И если есть наличие большого количества учебных заведений, то этот факт способствует формированию в регионе большого количества как преподавателей, так и студентов, часть из которых становится преподавателями и научными работниками, усиливает данный регион с точки зрения привлекательности проведения научных исследований.
Таким образом, научные центры (и высшие учебные заведения "тяготеют" друг к другу, что принципиально отлично от традиционных методов кластеризации.
То есть в рамках кластера модель напоминает галактику, которая вращается около некоторого центра масс, в котором может и не быть никакого элемента кластера.
Предложено для построения кластера использовать закон притяжения \[F=\gamma\frac{m\times M}{r^2},\] где в качестве массы M элемента кластера берется величина an, где n- количество вузов и нии, масса одного одного из них m равна единице, «гравитационная постоянная» γ = 1. Параметр a выбирается исключительно с целью визуализации.
Центр кластера представляет собой центр масс элементов кластера, а разрешающим правилом является условие, что данная точка больше тяготеет к центру того или иного кластера. Таким образом, критерием качества, в отличие от рассмотренных ранее модификаций, является не понятие "ближе-дальше", критерий "сильнее-слабее".

Кластеризация научных ресурсов Украины




Количество кластеров

Кластеризация по плотности элементов. Метод DBSCAN.

Идея метода DBSCAN (Density Based Spatial Clustering of Application with Noise) основана на гипотезе, что элементы одного кластера формируют область, плотность объектов внутри которого, по некоторому заданному порогу ε, превышает плотность за его пределами (Martin Ester, Hans-Peter Kriegel, J&g Sander, Xiaowei Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise, KDD’96. – Р. 226-231). В кластере должна присутствовать некоторая «непрерывность» данных, другими словами, если точки лежат недалеко друг от друга, то и значения функции в них не должны сильно отличаться.
Итак, пусть дано множество точек ℙ={Pi} (i=1,2,...,n) и Sε(Pi)- сфера с центром в точке Pi радиуса ε. Через Mε (Pi) обозначим множество точек из ℙ, лежащих в сфере Sε(Pi), и пусть |Mε (Pi)| их количество. Зафиксируем два числа – ε, m (порог и минимальное количество точек, которые расположены ближе всего к данной точке согласно радиусу ε) и введем обозначения- Достижимость по плотности – это транзитивное замыкание непосредственно достижимой по плотности точки. Если точка P' достижима по плотности из точки pi, то это не говорит о том, что точка pi достижима по плотности из точки P'.

Иллюстрация достижимости по плотности с m=3.
Точка p достижима от о, но не наоборот.

Алгоритм кластеризации DBSCAN является одним из немногих алгоритмов кластеризации, который позволяет находить кластеры внутри кластеров. Алгоритм по существу работает как поток жидкостей на местности. Он начинается в точке на местности и течет по рельефу, где есть наименьшее сопротивление. Результирующий кластер - это область, покрытая жидкостью. Можно представить различные жидкости с различной плотностью, которые покрывают рельеф в различных слоях.

Epsilon: 20
Min pts: 1
Очистить

Кластеризация на графах

Кластеризация на основе минимального остовного дерева

Пусть есть взвешенный граф G, у которого весами W являются расстояния между объектами. Построим для него минимальное остовное дерево и удалим \(k-1\) ребро с максимальными весами. В результате получим \(k\) компонент связности, которые можно интерпретировать как кластеры.
Ясно, что изменяя количество кластеров, можно получить дендрограмму, позволяющую разбить граф на любое количество кластеров от одного до количества верпшин этого графа.

Матрица смежности и визуализация связи объектов.

Для набора данных \(D = {x_i}_{i=1}^n\), состоящего из n точек в пространстве \(R^d\), обозначим через \(\textbf{A}\) симметричную матрицу подобия (сходства) между точками, это матрица размером n × n заданная как \[ \textbf{A}= \left( \begin{array}{llll} a_{11}& a_{12}& \ldots &a_{1n} \\ a_{21}& a_{22}& \ldots &a_{2n} \\ \vdots & \vdots& \ddots & \vdots \\ a_{n1}& a_{n2}& \ldots &a_{nn} \end{array} \right) \] где \(a_{ij}\) обозначает подобие или сходство между точками \(x_i\) и \(x_j\), при этом сходство должно быть симметричным и неотрицательным, т. е. \(a_{ij} = a_{ji}\) и \(a_{ij}\ge 0\), соответственно. Матрицу \(\textbf{A}\) можно рассматривать как взвешенную матрицу смежности взвешенного (неориентированного) графа \(G = (V, E)\), где каждая вершина является точкой и каждое ребро соединяет пару точек, т.е. \[ V=\{x_i|i=1,...,n\}, E=\{(x_i,x_j)|1\le i,j \le n\}. \] Кроме того, матрица подобия \(\textbf{A}\) задает вес на каждом ребре и \(a_{ij}\) обозначает вес ребра \((x_i, x_j)\). Если все коэффициенты сходства равны нулю или единицам, то \(\textbf{A}\) представляет регулярное смежное отношение между вершинами.

Для вершины \(x_i\) через \(d_i\) обозначим степень вершины, определяемую как \(d_i=\sum_{j=1}^na_{i,j}.\) Определим матрицу степени Δ графа G как диагональную матрицу n × n \[ \Delta= \left( \begin{array}{llll} d_{1}& 0& \ldots & 0 \\ 0& d_2& \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0& 0& \ldots & d_{n} \end{array} \right)= \left( \begin{array}{llll} \sum_{j=1}^na_{1,j}& 0& \ldots & 0 \\ 0& \sum_{j=1}^na_{2,j}& \ldots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0& 0& \ldots & \sum_{j=1}^na_{n,j} \end{array} \right) \] Нормализованная матрица смежности получается путем деления каждой строки матрицы смежности на степень соответствующего узла. \[ \textbf{M}=\Delta^{-1}A= \left( \begin{array}{llll} \frac{a_{11}}{d_1}& \frac{a_{12}}{d_1}& \ldots &\frac{a_{1n}}{d_1} \\ \frac{a_{21}}{d_2}& \frac{a_{22}}{d_2}& \ldots &\frac{a_{2n}}{d_2} \\ \vdots & \vdots& \ddots & \vdots \\ \frac{a_{n1}}{d_n}& \frac{a_{n2}}{d_n}& \ldots &\frac{a_{nn}}{d_n} \end{array} \right) \] При этом, если \(\textbf{M}=\{m_{i,j}\}\), то \(\sum_{j=1}^nm_{i,j}=\sum_{j=1}^n\frac{a_{i,j}}{d_i}=\frac{d_i}{di}=1.\)

Марковская кластеризация

Рассмотрим метод кластеризации, основанный на моделировании случайного блуждания на взвешенном графе. Основная идея заключается в том, что если переходы от узла к узлу по ребрам их соединяющим, отражают веса этих ребер, то в пределах кластера, переходы от одного узла к другому короче, чем переходы между узлами из разных кластеров. Причина этого в том, что узлы внутри кластера имеют более высокие сходства или веса, а узлы из разных кластеров имеют более низкое сходство.
Нормализованную матрицу смежности \(\textbf{M}\) можно интерпретировать как матрицу перехода. При этом значения \(m_{i,j}=\frac{a_{i,j}}{d_i}\) можно интерпретировать как вероятность перехода или перехода от узла i к узлу j в графе G.
Более того, учитывая, что
  1. элементы матрицы \(\textbf{M}\) неотрицательны, т.е. \(m_{ij}\gt 0\),
  2. строки из \(\textbf{M}\) являются векторами вероятности, т.е. \(\sum_{j=1}^nm_{i,j}=1,\)
таким образом, можно считать, что матрица \(\textbf{M}\) является матрицей перехода для цепи Маркова или марковским случайным блужданием на графе G. Цепочка Маркова является случайным процессом дискретного времени \(t\) над множеством состояний, в нашем случае это множество вершин V. Цепочка Маркова реализует переход от одного узла к другому на дискретных шагах \(t = 1,2,...\) с вероятностью перехода от узла i к узлу j, заданного как \(m_{ij}\). Пусть случайная величина \(X_t\) обозначает состояние в момент времени t.
Рассмотрим случай, когда вероятность перехода от узла i к узлу j завышена, и принимает значеие \(m_{ij}^r\), где степень \(r\ge 1\). Для матрицы перехода \(\textbf{M}\) определим оператор \(Υ\) следующим образом \[ Υ (\textbf{M}, r) =\left\{\frac{m_{ij}^r}{\sum_{\nu=1}^nm_{i\nu}^r}\right\}_{i,j=1}^n. \] Эта операция к трансформированной или раздутой матрице вероятности перехода, но элементы ее остаются неотрицательными, и каждая строка нормирована на сумму к 1. Чистый эффект этого оператора заключается в увеличении большей вероятности переходов и уменьшения более низких вероятностных переходов.

Markov Clustering Algorithm (MCL)

  1. \(t\leftarrow 0\).
  2. Заполнить матрицу смежности \(\textbf{A}\).
  3. \(\textbf{M}_t\leftarrow \Delta^{-1}\textbf{A}\).
  4. \(t\leftarrow t+1\).
  5. \(\textbf{M}_t\leftarrow \textbf{M}_{t-1}\times \textbf{M}_{t-1}\).
  6. \(\textbf{M}_t\leftarrow Υ (\textbf{M}, r)\).
  7. Если выполняется условие \(\|\textbf{M}_{t}-\textbf{M}_{t-1}\|_F\le\varepsilon\), то итерационный процесс завершить, иначе перейти на шаг 4.
  8. \(G_t\leftarrow\) направленный граф, индуцированный матрицей \(\textbf{M}_t\).
  9. \(\mathcal{C} \leftarrow\){слабосвязанные компоненты \(G_t\)}.
Марковский метод кластеризации - это итерационный метод, который перемежает разрастание матрицы и шаги инфляции (использование оператора \(Υ (\textbf{M}, r)\)).
Матричное разложение соответствует взятию последовательных степеней матрицы перехода, что приводит к случайным блужданиям большей длины. С другой стороны, использование оператора инфляции \(Υ (\textbf{M}, r)\) увеличивает вероятность более вероятных переходов и уменьшает менее вероятные переходы. Поскольку узлы в одном кластере должны иметь более высокий вес и, следовательно, более высокие вероятности переходов между ними, то оператор \(Υ (\textbf{M}, r)\) делает этот переход более вероятным, то есть оставляет узлы внутри кластера. Таким образом, это ограничивает масштабы случайного блуждания.
Вместо того, чтобы полагаться на заданное пользователем число \(k\) выходных кластеров, MCL принимает в качестве входного параметра значение \(r\gt 1\). Более высокие значения \(r\) приводят к большему количеству меньших кластеров, тогда как меньшие значения приводят к малому числу, но больших кластеров. Однако предварительно точное число кластеров не может быть определено.
В принципе, MCL сначала добавляет петли или собственные ребра к \(\textbf{A}\), если они не существуют, но если \(\textbf{A}\) - матрица смежности, то это не требуется, так как узел наиболее похож на себя, и, следовательно, \(\textbf{A}\) должен иметь высокие значения на диагоналях.
Итеративный процесс расширения и инфляции MCL прекращается, когда матрица перехода сходится, т.е. когда разность между матрицей перехода от двух последовательных итераций становится меньше порога \(\varepsilon>0\). Матричная разность ищется в терминах нормы Фробениуса \[ \left\|\textbf{M}_t-\textbf{M}_{t-1}\right\|_F=\sqrt{\sum_{i=1}^n\sum_{j=1}^n\left|\textbf{M}_t(i,j)-\textbf{M}_{t-1}(i,j)\right|^2}. \] Окончательно кластеры можно найти, перечислив слабосвязанные компоненты в направленном графе, индуцированные окончательной матрицей перехода \(\textbf{M}_t\).
Направленный граф, индуцированный \(\textbf{M}_t\), обозначается как \(G_t = (V_t, E_t)\). Множество вершин такое же, как набор узлов в исходном графе, т.е. \(V_t = V\), и множество ребер задано в виде \[ E_t =\left\{(i, j) | \textbf{M}_t (i, j)> 0\right\}. \] Другими словами, направленное ребро \((i, j)\) существует только в том случае, если узел \(i\) может перейти в узел \(j\) в пределах \(t\) шагов процесса расширения и инфляции. Узел \(j\) называется аттрактором, если \(\textbf{M}_t(j,j)>0\), и мы говорим, что узел \(i\) притягивается к аттрактору \(j\), если \(\textbf{M}_t(i,j)>0\).
Процесс MCL дает набор узлов аттрактора \(V_a \subseteq V\), так что другие узлы притягивается, по крайней мере, к одному аттрактору из \(V_a\). То есть для всех узлов \(i\) существует узел \(j\in V_a\),такой что \((i, j) \in E_t\). Сильно связная компонента в ориентированном графе определяет максимальный подграф такой, что существует направленный путь между всеми парами вершин в подграфе. Чтобы извлечь кластеры из \(G_t\), MCL сначала обнаруживает сильно связанные компоненты \(S_1, S_2,...., S_q\) над множеством аттракторов \(V_a\). Далее, для каждого сильно связанного множества аттракторов \(S_j\) MCL обнаруживает слабосвязанные компоненты, состоящие из всех узлов \(i \in V_t - V_a\), притягиваемых к аттрактору из \(S_j\). Если узел \(i\) притягивается к множеству сильно связанных компонентов, он добавляется к каждому такому кластеру, в результате чего возможны перекрывающиеся кластеры.

Пример

Пусть дан граф
с матрицей смежности
Для него матрица степени графа будет равна
Нормализованная матрица графа равна
Выберем значение r=2.65.
Найдем матрицы перехода, пока норма Фробениуса отклонения от матрицы, полученной на предыдущем шаге итерации не станет меньше \(\varepsilon=0.0001\)
Результатом будет следующее:

Полезная литература. Книги.

  1. Berry L. Data Mining Techniques For Marketing, Sales, and Customer Relationship Management / L.Berry, G.Linoff; Second Edition .— Indianapolis, Indiana: Wiley Publishing, Inc., 2004 .— 672 p.
  2. Berry M. Lecture Notes in Data Mining / M.Berry, M.Browne .— Singapore: World Scientific Publishing Co., 2006 .— 237 p.
  3. Charu C. Aggarwal Data Mining. The Textbook. / C.A.Charu; — Springer, 2015 .— 746 p.
  4. Christopher M. Bishop Pattern Recognition and Machine Learning / M.B.Christopher .— Springer, 2006 .— 758 p.
  5. Data Analysis, Machine Learning and Applications / C.Preisach, H.Burkhardt, L.Schmidt-Thieme, R.Decker and etc.; Proceedings of the 31st Annual Conference of the Gesellschaft für Klassifikation, Albert-Ludwigs-Universität Freiburg, March 7–9, 2007 .— Berlin Heidelberg: Springer-Verlag, 2008 .— 703 p.
  6. de Oliveira J. Valente Advances in Fuzzy Clustering and its Applications / J. Valente de Oliveira, W. Pedrycz .— West Sussex England: John Wiley & Sons Ltd, 2007 .— 457 p.
  7. Han J. Data Mining Concepts and Techniques / J.Han, M.Kamber, J.Pei; Third Edition .— 225 Wyman Street, Waltham, MA 02451, USA: Morgan Kaufmann Publishers is an imprint of Elsevier, 2012 .— 740 p.
  8. Hastie T. The Elements of Statistical Learning Data Mining, Inference, and Prediction / T.Hastie, R.Tibshirani, J.Friedman; Second Edition .— Springer, 2017 .— 764 p.
  9. Nisbet R. Handbook of statistical analysis and data mining applications / R.Nisbet, J.Elder, G.Miner .— Elsevier Inc., 2009 .— 860 p.
  10. Pattern Recognition and Machine Intelligence / Sergei O. Kuznetsov Deba P. Mandal Malay K. Kundu Sankar K. Pal (Eds.); 4th International Conference, PReMI 2011 Moscow, Russia, June 27 – July 1, 2011 Proceedings .— Springer, 2011 .— 495 p.
  11. Poncelet P. Data Mining Patterns: New Methods and Applications / P.Poncelet, M.Teisseire, F.Masseglia .— NY: Information Science Reference, 2008 .— 324 p.
  12. Sammut C. Encyclopedia of Machine Learning / C.Sammut, G.Webb .— NY: Springer Science+Business Media, 2010 .— 1059 p.
  13. The Top Ten Algorithms in DataMining; Vipin Kumar (Editor) .— Taylor & Francis Group, LLC, 2009 .— 2006 p.
  14. Venugopal K.R. Soft Computing for Data Mining Applications / K.R.Venugopal, K.G.Srinivasa, L.M.Patnaik; Studies in Computational Intelligence,Volume 190 .— Berlin Heidelberg: Springer-Verlag, 2009 .— 354 p.
  15. Wang J. Encyclopedia of Data Warehousing and Mining / J.Wang; Second Edition .— Hershey: Information Science Reference, 2009 .— 2227 p.
  16. Witten I.H. Data Mining. Practical Machine Learning Tools and Techniques / Ian H. Witten, Eibe Frank; Second Edition .— San Francisco: Elsevier Inc., 2005 .— 558 p.
  17. Zaki M.J. Data Mining and Analysis: Fundamental Concepts and Algorithms / M.J.Zaki, W.Meira .— New York: Cambridge University Press, 2014 .— 660 p.
  18. Дюран Б., Оделл П. Кластерный анализ.-М.: Статистика, 1977.- 128 с.
  19. Шумейко А.А., Сотник С.Л. Интеллектуальный анализ данных (Введение в Data Mining).-Днепропетровск:Белая Е.А., 2012.- 212 с.

Полезная литература. Статьи.

  1. Babuska R. Improved Covariance Estimation for Gustafson-Kessel Clustering / R.Babuska, d.V.van, U.Kaymak // 2002 IEEE International Conference on Fuzzy Systems FUZZ-IEEE '02 .— Honolulu, HI, USA, 2002 .— P.1081- 1085.
  2. Biemann С. Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems / С.Biemann // Workshop on TextGraphs at HTL-NAACL .— New York City, June 2006. .— P.73-80 .— Режим доступу: https://www.researchgate.net/publication/228670574_Chinese_whispers_An_efficient_graph_clustering_algorithm_and_its_application_to_natural_language_processing_problems
  3. Chin-Tang Chang A Fuzzy K-means Clustering Algorithm Using Cluster Center Displacement / Chin-Tang Chang, Jim Z.C. Lai and Mu-Der Jeng // Journal of Information Science and Engineering .— 2011 .— №27 .— P.995-1009.
  4. Clustering with Minimum Spanning Trees / Y.Zhou, O.Grygorash, T.F.Hain та ін. .— Elsevier, 2010 .— 22 p.
  5. Jain A.K. Data Clustering: A Review / A.K.Jain, M.Murty, P.J.Flynn // ACM Computing Surveys .— 1999 .— Vol. 31, No. 3 .— P.264-323.
  6. Mercer D.P. Clustering large datasets / D.P.Mercer .— Linacre College, 2003 .— 50 p.
  7. Semi-supervised graph clustering: a kernel approach / B.Kulis, S.Basu, I.Dhillon, R.Mooney // Mach Learn .— 2009 .— №74 .— P.1-22.
  8. Ильев В.П. О задачах кластеризации графов / В.П.Ильев, С.Ильева // Вестн. Ом. ун-та .— . 2016 .— №2 .— C.16–18.
  9. Классификация и сравнение методов кластеризации. [Електронний ресурс] // Нейский И.М. .— Режим доступу: http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf
  10. Клышинский Э.С. Метод кластеризации на основе анализа плотности точек / Э.С.Клышинский // Новые информационные технологии в автоматизированных системах .— 2014 .— C.150-159.
  11. Пестунов И.А. Алгоритмы кластеризации в задачах сегментации спутниковых изображений / И.А.Пестунов, Ю.Н.Синявский // Вестник КемГУ .— 2012 .— №4 (52) Т. 2 .— C.110-125.
  12. Современные тенденции в кластерном анализе [Електронний ресурс] // В.Б. Бериков, Г.С. Лбов .— Режим доступу: http://www.ict.edu.ru/ft/005638/62315e1-st02.pdf
  13. Солнцева М.О. Применение методов кластеризации узлов на графах с разреженными матрицами смежности в задачах логистики / М.О.Солнцева, Б.Г.Кухаренко // ТРУДЫ МФТИ. Информатика, математическое моделирование, экономика .— 2013 .— Том 5, № 3 .— C.75-83.
  14. Статистические алгоритмы кластеризации данных в адаптивных обучающих системах / С.А.Батуркин, Е.Батуркина, В.А.Зименко, И.В.Сигинов // Вестник РГРТУ .— 2010 .— №1(31) .— C.1-4.
  15. Суслов С.И. Кластеры Петербургских политических онлайн-сообществ «ВКОНТАКТЕ» / С.И.Суслов // Вестник Санкт-Петербургского университета.Сер. 12. Социология .— 2016 .— №6(4) .— C.69-87.
  16. Цициашвили Г.Ш. Алгоритмы кластеризации графов / Г.Ш.Цициашвили, М.Осипова, А.С.Лосев // Вестник ВГУ. Серия:физика. Математика .— 2016 .— №1 .— C.145-149.
  17. Чапланов А.П. Кластеризация объектов с помощью алгоритма DBSCAN / А.П.Чапланов, Е.Чапланова // Системи обробки інформації .— 2006 .— №9 (58) .— C.82-85.

Вопрос-ответ.

Задать вопрос: