Методы кластеризации

Пусть множество объектов \(\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)\) степень схожести между объектами (чаще всего это расстояние), а ε - максимальное значение порога, формирующего один кластер.

Критерий схожести двух елементов. Общие понятия.

Наиболее используемыми мерами схожести является понятие расстояния между двумя точками \(\|x_i-x_j\|\). Приведем некоторые наиболее часто используемые определения расстояния.

Евклидово (среднеквадратическое или ℓ₂) расстояние \[d_2(x_i,x_j)=\|x_i-x_j\|_2=\sqrt{\sum_{\nu=0}^m\left(t_\nu^i-t_\nu^j\right)^2}\]

Рис.1. Иллюстрация Евклидова расстояния.
расстояние ℓ₁ (в англоязычной литературе – манхеттеновское или городское расстояние) \[d_1(x_i,x_j)=\|x_i-x_j\|_1=\sum_{\nu=0}^m\left|t_\nu^i-t_\nu^j\right|\]

Рис. 2. Иллюстрация расстояния ℓ₁.
используется в том случае, когда нужно уменьшить влияние отдельных выбросов;
Чебышевское (равномерное или ℓ_∞) расстояние \[d_\infty(x_i,x_j)=\|x_i-x_j\|_\infty=max\left\{\left.\left|t_\nu^i-t_\nu^j\right|\right|\nu=0,..,m\right\}\]

Рис. 3. Иллюстрация расстояния Чебышева.
используется если нужно увеличить влияние отдельных выбросов;
расстояние Махалонобиса \[d_M(x_i,x_j)=\|x_i-x_j\|_M=\sqrt{(x_i-x_j)^T\Sigma^{-1}(x_i-x_j)}\] используется в случае, если нужно учесть корреляцию на конкретном классе. Здесь Σ корреляционная матрица.

Заметим, что во многих случаях вместо расстояния в качестве критерия близости используется значение косинуса угла между двумя векторами \[ \cos{\varphi_{i,j}=\frac{x_i^Tx_j}{\|x_i\|_2\|x_j\|_2}}, \] тогда степень сходства между векторами (точками) \(x_i,x_j\) можно записать в виде \[ d_{cos}(x_i,x_j)=1-\frac{x_i^Tx_j}{\|x_i\|_2\|x_j\|_2}. \] Корреляция Пирсона (Pearson) измеряет степень линейной зависимости между двумя профилями, в этом случае степень сходства будет иметь вид \[ d_{cor}(x_i,x_j)=1-\frac{\sum_{\nu=1}^m\left(t_\nu^i-\bar{t}^i\right)\left(t_\nu^j-\bar{t}^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}} \] Метод r-ранговой корреляции Спирмена (Spearman) позволяет определить тесноту (силу) и направление корреляционной связи между двумя элементами или двумя профилями (иерархиями) признаков, и степень сходства можно записать в виде \[ d_{spear}(x_i,x_j) = 1-r\left(x_i,x_j\right)=1 - \frac{\sum\limits_{\nu=1}^m (\tau_\nu^i - \bar{\tau}^i)(\tau_\nu^j - \bar{\tau}^j)} {\sqrt{\sum\limits_{\nu=1}^m(\tau_\nu^i - \bar{\tau}^i)^2 \sum\limits_{\nu=1}^m(\tau_\nu^j -\bar{\tau}^j)^2}} \]
где \(\{\tau^i_\nu\} = rank(\{t^i_\nu\})\) и \(\{\tau^j_\nu\} = rank(\{t^j_\nu\})\).

Метод корреляции Кендалла (Kendall) измеряет соответствие между ранжированием переменных \(x_i\) и \(x_j\) и является альтернативой корреляции Спирмена. Он предназначен для определения взаимосвязи между двумя ранговыми переменными. Интерпретация результатов вычисления коэффициента ранговой корреляции Кендалла определяется как разность вероятностей совпадения и инверсии в рангах. Коэффициент ранговой корреляции \(\tau\) Кендалла, как и коэффициент ранговой коррелеяции Спирмена, предназначен для определения взаимосвязи между двумя ранговыми переменными. Для одних и тех же значений переменных значения коэффициента корреляции Спирмена будут всегда немного больше, чем значения коэффициента ранговой корреляции Кендалла, тогда как уровень значимости будет одинаков или же у коэффициента корреляции Кендалла будет немного больше.
Формула вычисления коэффициента ранговой корреляции Кендалла может быть следующим образом: \[\tau= \frac{m_c - m_d}{\frac{1}{2}m(m-1)}, \]
где \(m_c\) — число совпадений, \(m_d \)— число инверсий, m — объем выборки

При наличии связанных рангов формула изменяется с учетом поправки на связанные ранги: \[\tau=\frac {m_c - m_d}{\sqrt{\left[m\frac{(m-1)}{2}\right] - K_i} \sqrt{\left[m\frac{(m-1)}{2}\right] - K_j}}, \]
где \(K_i\) поправка на связи рангов переменной \(x_i\), \(K_j\) — поправка на связи рангов переменной \(x_j\) \[K_i=0,5\Sigma_is_i(s_i - 1),\]
где \(i\) — количество групп связей по \(x_i\), \(s_i\) — численность группы \(x_i\) \[K_j=0,5\Sigma_js_j(s_j - 1),\]
где \(j\) — количество групп связей по \(x_j\), \(s_j\) — численность группы \(x_j\).

Таким образом, общее число возможных наблюдений для сравнения значений признаков равно \(m(m-1)/2\). Вначале нужно упорядочить пары по значениям \(x_i\). Если \(x_i\) и \(x_j\) коррелированы, то они будут иметь одинаковые порядки относительного ранга. Теперь для каждого \(\nu\gt \xi\) нужно подсчитать число \(t^j_\nu\ge t^j_\xi\) (согласованные пары (c)) и число \(t^j_\nu\lt t^j_\xi\) (несогласованные пары (d)). Расстояние согласно корреляции Кендалла определяется следующим образом: \[ d_{kend}(x_i, x_j) = 1 - \frac{m_c - m_d}{\frac{1}{2}m(m-1)} \]

Выбор степени схожести очень важен, так как он оказывает сильное влияние на результаты кластеризации (что видно на примере). Для большинства распространенных методов кластеризации по умолчанию это евклидово расстояние. В зависимости от типа данных и поставленных задач одни критери схожести могут быть предпочтительнее других. Например, расстояние, основанное на корреляции, часто используется в анализе данных в медицине. Расстояние на основе корреляции рассматривает два объекта одинаковыми, если их особенности сильно коррелированы, хотя наблюдаемые значения могут быть далеки друг от друга в терминах евклидова расстояния. Расстояние между двумя объектами равно 0, когда они отлично коррелированы. Корреляция Пирсона довольно чувствительна к выбросам. В случае, если наличие выбросов не принципиально, их влияние можно смягчить, используя корреляцию Спирмена вместо корреляции Пирсона.

Нормализация (стандартизация) данных.

Для задачи кластеризации очень важно, чтобы все данные были соизмеримы, т.е. чтобы не получилось, что одна часть данных измеряется в упаковках, а другая – в килограммах, другими словами, на первом этапе кластеризации всегда нужно проводить нормализацию данных.
Значение дистанционных мер тесно связано со шкалой, на которой производятся измерения. Поэтому перед анализом имеющихся данных, их вначале часто масштабируют (т.е. стандартизируют). Это особенно рекомендуется, если одни и те же переменные измеряются в разных масштабах (например: килограммы, километры, сантиметры, ...), в противном случае данные, имеющиеся незначительные отклонения, могут оказать серьезное влияние на полученный результат.
Цель состоит в том, чтобы сопоставить переменные. Обычно переменные масштабируются так, чтобы стандартное отклонение было равно нулю: \[ \frac{x_i - center(x)}{scale(x)}, \] где \(center(x)\)может быть средним или медианным значений х, а \(scale(x)\) может быть стандартным отклонением, межквантильным диапазоном или средним абсолютным отклонением.
Однако, нужно заметить, что стандартизация делает меры измерения расстояния - Евклида, Манхэттена и корреляции более похожими. Так при стандартизации данных существует функциональная зависимость между коэффициентом корреляции Пирсона и евклидовым расстоянием: \[ d_{euc}(x_i, x_j) = \sqrt{2m[1 - r(x_i, x_j)]}, \] где \(x_i, x_j\) - два стандартизированных \(m\)-вектора с нулевым средним значением и единичной длиной. Поэтому результат, полученный с помощью корреляционных мер Пирсона и стандартизованных евклидовых расстояний, сопоставим.
Если выбрано евклидово расстояние, то наблюдения с большими значениями характеристик будут сгруппированы вместе. То же самое справедливо и для наблюдений с низкими значениями признаков.

Кроме того, при проведении процедуры кластеризации нужно заранее задаваться либо числом кластеров, либо критерием, характеризующем близость элементов внутри кластера либо удаленность самих кластеров друг от друга.

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

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

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

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

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

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

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

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

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

Fuzzy C-Means (FCM)

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

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

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

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

Нечеткая кластеризация, с учетом помех (шум, выбросы).

Все алгоритмы, основанные на методе наименьших квадратов, в том числе, 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\), который также определяет разбиение на кластеры, называется степенью нечеткой энтропии. Рассмотрим следующие частные случаи

\(w\to\infty\) имеем \(u_{i,j}\to C^{-1}\), каждый признак одинаково назначен кластерам C, поэтому имеем только один кластер.
\(w\to 0\) имеем \(u_{i,j}\to 0\) или 1, и кластеризация сводится к четкой кластеризации.

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

Кластеризация может быть связана с вероятностной кластеризацией путем определения расстояния \[ 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\) и использовании данного расстояния, нечеткая кластеризация сводится к разделению гауссовой смеси. Другими словами, разделение гауссовой смеси можно рассматривать как метод нечеткой кластеризации.

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

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

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

Основные понятия и определения

С математической точки зрения граф представляет собой совокупность множества объектов, называемых вершинами, и связей между ними. Эти вершины называют узлами графа, а связи - дугами или рёбрами. При использовании графов, им придаются различные свойства, так графы могут различаться направленностью, ограничениями на количество связей и разными дополнительными данными о вершинах или рёбрах.
Основные из них:

Неориентированный граф, G-граф - это упорядоченная пара G = (V, E), для которой выполнены следующие условия:
- V={v} - это непустое множество вершин, или узлов,
- E={e} - это множество пар (в данном случае неупорядоченных) вершин, называемых рёбрами.
в рассматриваемых нами случаях V (ну и E, естественно) будут конечными множествами.
Порядок графа |V| - число вершин в графе. Размер графа |E| - число его рёбер.
Концевые вершины графа - это вершины, соединяющие множество ребер.
- Две концевые вершины одного и того же ребра называются соседними.
- Два ребра называются смежными, если они имеют общую концевую вершину.
- Два ребра называются кратными, если множества их концевых вершин совпадают.
- Ребро называется петлёй, если его концы совпадают.
- Степенью вершины V называют количество инцидентных ей рёбер (при этом петли считают дважды).
- Вершина называется изолированной, если она не является концом ни для одного ребра.
- Вершина называется листом, если она является концом ровно одного ребра.
Ориентированный граф G — это упорядоченная пара G = (V, A), для которой выполнены следующие условия:
- V — это непустое множество вершин или узлов.
- A — это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.
- Дуга — это упорядоченная пара вершин \((v, w)\), где вершину \(v\) называют началом, а \(w\) — концом дуги. Можно сказать, что дуга \(v \to w\) ведёт от вершины \(v\) к вершине \(w\).
Смешанный G-граф - это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Записывается упорядоченной тройкой G = (V, E, A).
Ориентированный и неориентированный графы являются частными случаями смешанного.
Изоморфный граф - это некоторый граф G, для которого существует биекция \(f\) из множества вершин графа G в множество вершин другого графа H, которому он изоморфен, обладающая следующим свойством: если в графе G есть ребро из вершины \(A\) в вершину \(B\), то в графе H должно быть ребро из вершины \(f(A)\) в вершину \(f(B)\) и наоборот - если в графе H есть ребро из вершины \(A\) в вершину \(B\), то в графе G должно быть ребро из вершины \(f^{-1}(A)\) в вершину \(f^{-1}(B)\). В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.
Путь графа, цепь графа - это конечная последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
- Ориентированный путь (в ориентированном графе) - это конечная последовательность вершин \(v_i (i=1, …,k)\), для которой все пары \((v_i, v_{i+1}) (i=1,… k-1)\) являются (ориентированными) рёбрами.
- Цикл - это путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Если вершины \(v\) и \(w\) являются концами некоторого ребра, то последовательность \((u,v,u)\) является циклом.
- Простой путь (простой цикл) - это такой путь, в котором ребра не повторяются.
- Элементарный путь - это простой путь в графе, вершины в котором не повторяются.
Заметим, что любой путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.
Любой простой неэлементарный путь содержит элементарный цикл.
Любой простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).
Петля - это элементарный цикл.
Бинарное отношение на множестве вершин графа, заданное как “существует путь из \(u\) в \(v\)”, является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа.

Компонента графа, связная компонента графа - это всякий максимальный связный подграф G-графа. Слово "максимальный" означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

Рис. Связные компоненты графа.

Если у графа ровно одна компонента связности, то граф связный.
Мост - это ребро графа, удаление которого увеличивает число компонент графа.
Связный граф - это граф, в котором для любых вершин \(u,v\) есть путь из \(u\) в \(v\). Сильно связный, ориентированно связный граф - это ориентированный граф, в котором из любой вершины в любую другую имеется ориентированный путь.
Дерево - это связный граф, не содержащий простых циклов.
Полный граф - это граф, в котором любые его две (различные, если не допускаются петли) вершины соединены ребром.
Двудольный граф - это граф, в котором вершины можно разбить на два непересекающихся подмножества \(V_1\) и \(V_2\) так, что всякое ребро соединяет вершину из \(V_1\) с вершиной из \(V_2\).
- k-дольный граф - это граф, в котором вершины можно разбить на k непересекающихся подмножеств \(V_1, V_2, ..., V_k\) так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
- Полный двудольный граф - это граф, в котором каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
Взвешенный граф - это граф, в котором каждому ребру поставлено в соответствие некоторое число, называемое весом ребра.
Планарный граф - это граф, который можно изобразить диаграммой на плоскости без пересечений рёбер. Существуют также k-раскрашиваемые и k-хроматические графы.
Безопасным ребром относительно некоторой компоненты связности К из А назовем ребро с минимальным весом, ровно один конец которого лежит в К.

Список рёбер - это тип представления графа, при которм каждое ребро представляется двумя числами - номерами вершин этого ребра.

Матрица \(A=\|\alpha_{i,j}\|\), в каждой ячейке которой записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу, называется матрицей смежности (Adjacency matrix).
Для невзвешенного графа G=(V,E) \(\alpha_{i,j}\) — количество рёбер, соединяющих вершины \(v_i\) и \(v_j\), причём при \(i=j\) каждую петлю учитываем дважды, если граф не является ориентированным, и один раз, если граф ориентирован.
Для взвешенного графа G=(V,E) \(\alpha_{i,j}\) — вес ребра, соединяющего вершины \(v_i\) и \(v_j\).

Взвешенность графа	Вид графа	Матрица смежности
Невзвешенный граф		\begin{pmatrix} 0 & 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 1 & 1\\ 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 0\\ \end{pmatrix}
Взвешенный граф		\begin{pmatrix} 0 & 40 & \infty & \infty & 18\\ 40 & 0 & 22 & 6 & 15\\ \infty & 22 & 0 & 14 & \infty \\ \infty & 6 & 14 & 0 & 20\\ 18 & 15 & \infty & 20 & 0 \\ \end{pmatrix}

Пусть дан связный, неориентированный граф с весами на ребрах G(V, E), в котором V — множество вершин, а E — множество их возможных попарных соединений (ребер). Пусть для каждого ребра \((u,v)\) однозначно определено некоторое вещественное число \(w(u,v)\) — его вес (для реальных задач это длина, стоимость или некая другая характеристика). Рассмотрим связный ациклический подграф \(T \subset G\), содержащий все вершины, и такой, что суммарный вес его ребер минимален.
Так как \(T\) связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом (spanning tree). Остовное дерево \(T\), у которого суммарный вес его ребер \(w(T)=\sum_{(u,v)\in T}w(u,v)\) минимален, называется минимальным остовным или минимальным покрывающим деревом (minimum spanning tree).

Рис. Минимальное остовное дерево. Суммарный вес дерева равен 37.

Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево.
Хороший обзор алгоритмов построения минимальных остовных деревьев приведен в работе Jeff Erickson. Minimum spanning trees. Lecture notes: Fall 2002 — CS 373: Combinatorial Algorithms.

Алгоритм Крускала (Joseph Kruskal)

Этот метод был придуман автором в 1956 году, но по сей день является самым быстрым из известных методов (http://rain.ifmo.ru/cat/view.php/theory/graph-spanning-trees/mst-2005).

Алгоритм Крускала объединяет вершины графа в несколько связных компонент, каждая из которых является деревом. На каждом шаге из всех ребер, соединяющих вершины из различных компонент связности, выбирается ребро с наименьшим весом. Необходимо проверить, что оно является безопасным. Так как ребро является самым легким из всех ребер, выходящих из данной компоненты, оно будет безопасным.

Для реализовации выбора безопасного ребра на каждом шаге все ребра графа G перебираются по возрастанию веса. Для очередного ребра проверяется, не лежат ли концы ребра в разных компонентах связности, и если это так, ребро добавляется, и компоненты объединяются.

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

`Make-Set(v)`	Создание множества из набора вершин
`Find-Set(v)`	Возвращает множество, содержащее данную вершину
`Union(u,v)`	Объединяет множества, содержащие данные вершины

Общая схема алгоритма выглядит так:


1: A ← 0

2: foreach (для каждой) вершины v ∈ V[G] 

3:     do Make-Set(v)

4: упорядочить ребра по весам

5: for (u,v) ∈ E (в порядке возрастания веса)

6:     do if Find-Set(u) ≠ Find-Set(v) then

7:         A ← A ∪ {(u,v)}

8:         Union(u,v)

9: return A

На рисунках проиллюстрирована работа алгоритма.

Рис. Начальная фаза. Минимальный покрывающий лес пуст.	Рис. Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его к А.
Рис. Следующее безопасное ребро с весом 6. Добавляем его.	Рис. Следующее безопасное ребро с весом 8.
Рис. Следующее безопасное ребро с весом 9.	Рис. Следующее безопасное ребро с весом 11.
Рис. Следующее безопасное ребро с весом 14.	Рис. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

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

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

Для набора данных \(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.
Более того, учитывая, что

элементы матрицы \(\textbf{M}\) неотрицательны, т.е. \(m_{ij}\gt 0\),
строки из \(\textbf{M}\) являются векторами вероятности, т.е. \(\sum_{j=1}^nm_{i,j}=1,\)

таким образом, можно считать, что матрица \(\textbf{M}\) является матрицей перехода для цепи Маркова или марковским случайным блужданием на графе G. Цепочка Маркова является случайным процессом дискретного времени \(t\) над множеством состояний, в нашем случае это множество вершин V. Цепочка Маркова реализует переход от одного узла к другому на дискретных шагах \(t = 1,2,...\) с вероятностью перехода от узла i к узлу j, заданного как \(m_{ij}\). Пусть случайная величина \(X_t\) обозначает состояние в момент времени t.

Подробнее.

Марковское свойство означает, что распределение вероятности \(X_t\) по состояниям на момент времени \(t\) зависит только от распределения вероятности \(X_{t-1}\), т. е. \[ P (X_t = i | X_0, X_1, ..., X_{t-1}) = P (X_t = i | X_{t-1}) \] Далее, предположим, что цепь Маркова однородна, т.е. вероятность перехода \[ P (X_t = j | X_{t-1} = i) = m_{ij} \] не зависит от шага \(t\).
Для заданного узла i матрица перехода \(\textbf{M}\) задает вероятности достижения любого другого узла j за один шаг. Начиная с узла i при t = 0, рассмотрим вероятность попасть в узел j при t = 2, т. е. после двух шагов. Обозначим через \(m_{ij}(2)\) вероятность достижения j из i за два шага. Мы можем вычислить это следующим образом \[ m_{ij}(2) = P (X_2 = j | X_0 = i) =\sum_{\nu=1}^nP (X_1 = \nu | X_0 = i) P (X_2 = j | X_1 = \nu) = \sum_{\nu=1}^nm_{i\nu}m_{\nu j} = \textbf{m}^T_i M_j, \] где \(\textbf{m}_i = (m_{i1}, m_{i2}, ..., m_{in})^T\) обозначает вектор, соответствующий \(i\)-й строке \(\textbf{M}\) и \(M_j = (m_{1j}, m_{2j}, ..., m_{nj})^T\) обозначает вектор, соответствующий \(j\)-му столбцу \(\textbf{M}\).
Рассмотрим произведение \(\textbf{M}\) самой на себя \[ \textbf{M}^2=\textbf{M}\times \textbf{M}= \left(\begin{array}{c} \textbf{m}_1^T \\ \textbf{m}_2^T \\ \vdots \\ \textbf{m}_n^T \\ \end{array} \right) \times \left( \begin{array}{cccc} M_1 & M_2 & \ldots & M_n\\ \end{array} \right)= \left\{\textbf{m}_i^TM_j\right\}_{i,j=1}^n=\left\{m_{ij}(2)\right\}_{i,j=1}^n. \] Отсюда следует, что \(\textbf{M}^2\) - матрица вероятности перехода для цепи Маркова над двумя шагами. Аналогично, для трех шагов матрица перехода равна \(\textbf{M}^2\times \textbf{M}=\textbf{M}^3\). В общем случае матрица вероятности перехода для t шагов определяется следующим образом \(\textbf{M}_{t-1}\times \textbf{M}= \textbf{M}_t\).
Таким образом, случайное блуждание на графе G соответствует взятию последовательных степеней матрицы перехода \(\textbf{M}\).
Пусть \(\tau_0\) задает вектор вероятности начального состояния, то есть для \(t = 0\). Тогда \(\tau_{0i}= P (X_0 = i)\) - вероятность старта в узле \(i\) для всех \(i = 1, ..., n\). Начиная с \(\tau_0\), мы можем получить вектор вероятности состояния для \(X_t\), т.е. вероятность попасть в узел \(i\) на шаге \(t\) будет следующей \[ \tau_{t}^T=\tau_{t-1}^T\textbf{M} =\left(\tau_{t-2}^T\textbf{M}\right)\times \textbf{M}=\tau_{t-2}^T\textbf{M}^2 =\left(\tau_{t-3}^T\textbf{M}^2\right)\times \textbf{M}=\tau_{t-3}^T\textbf{M}^3 =\ldots =\tau_{0}^T\textbf{M}^t. \] Отсюда сразу получаем \[ \tau_{t}=\left(\textbf{M}^t\right)^T\tau_{0}=\left(\textbf{M}^T\right)^t\tau_{0}. \]

Рассмотрим случай, когда вероятность перехода от узла 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)

\(t\leftarrow 0\).
Заполнить матрицу смежности \(\textbf{A}\).
\(\textbf{M}_t\leftarrow \Delta^{-1}\textbf{A}\).
\(t\leftarrow t+1\).
\(\textbf{M}_t\leftarrow \textbf{M}_{t-1}\times \textbf{M}_{t-1}\).
\(\textbf{M}_t\leftarrow Υ (\textbf{M}, r)\).
Если выполняется условие \(\|\textbf{M}_{t}-\textbf{M}_{t-1}\|_F\le\varepsilon\), то итерационный процесс завершить, иначе перейти на шаг 4.
\(G_t\leftarrow\) направленный граф, индуцированный матрицей \(\textbf{M}_t\).
\(\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.

Для исходных данных в виде изображения

выделить кластеры

и разделить слипшиеся клетки

Задача 2.

По данным государственной службы статистики України средняя заработная плата по видам экономической деятельности в 2017 году составляет

Сельское хозяйство, лесное хозяйство и рыбное хозяйство	из них сельское хозяйство	Промышленность	Строительство	Оптовая и розничная торговля; ремонт автотранспортных средств и мотоциклов	Транспорт, складское хозяйство, почтовая и курьерская деятельность	наземный и трубопроводный транспорт	водный транспорт	авиационный транспорт	складское хозяйство и вспомогательная деятельность в сфере транспорта	почтовая и курьерская деятельность	Временное размещение и организация питания	Информация и телекоммуникации	Финансовая и страховая деятельность	Операции с недвижимым имуществом	Профессиональная, научная и техническая деятельность	из них научные исследования и разработки	Деятельность в сфере административного и вспомогательного обслуживания	Государственное управление и оборона; обязательное социальное страхование	Образование	Здравоохранение и предоставление социальной помощи	из них здравоохранение	Искусство, спорт, развлечения и отдых	деятельность в сфере творчества, искусства и развлечений	функционирования библиотек, архивов, музеев и других учреждений культуры	Предоставление других видов услуг
6383	6149	8055	6537	7935	8220	7960	8296	33689	8752	4126	5112	12725	13257	6174	10162	8334	5798	10346	5782	5005	5017	6433	5792	5466	6884

Провести кластеризацию и проанализировать полученные результаты.

Задача 3.

Для данных

провести кластеризацию областей Украины по экологическому состоянию.

Задача 4.

В таблице приведены данные по концентрации уксусной кислоты, H2S и молочной кислоты в 30 образцах зрелого сыра чеддер. Кроме того, предоставляется субъективная ценность вкуса.

Используя методы кластеризации, дать оценку данным образцам сыра.

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

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

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

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

Clusterization