На какой идее основан алгоритм k means

Метод k-средних (K-means)

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

1. Выбирается число кластеров k .
2. Из исходного множества данных случайным образом выбираются k наблюдений, которые будут служить начальными центрами кластеров.
3. Для каждого наблюдения исходного множества определяется ближайший к нему центр кластера (расстояния измеряются в метрике Евклида). При этом записи, «притянутые» определенным центром, образуют начальные кластеры.
4. Вычисляются центроиды — центры тяжести кластеров. Каждый центроид — это вектор, элементы которого представляют собой средние значения соответствующих признаков, вычисленные по всем записям кластера.
5. Центр кластера смещается в его центроид, после чего центроид становится центром нового кластера.
6. 3-й и 4-й шаги итеративно повторяются. Очевидно, что на каждой итерации происходит изменение границ кластеров и смещение их центров. В результате минимизируется расстояние между элементами внутри кластеров и увеличиваются междукластерные расстояния.

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

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

Существуют методы кластеризации, которые можно рассматривать как происходящие от k-средних. Например, в методе k-медиан (k-medians) для вычисления центроидов используется не среднее, а медиана, что делает алгоритм более устойчивым к аномальным значениям в данных.

Алгоритм g-средних (от gaussian) строит кластеры, распределение данных в которых стремится к нормальному (гауссовскому) и снимает неопределенность выбора начальных кластеров. Алгоритм C-средних использует элементы нечеткой логики, учитывая при вычислении центроидов не только расстояния, но и степень принадлежности наблюдения к множеству объектов в кластере. Также известен алгоритм Ллойда, который в качестве начального разбиения использует не множества векторов, а области векторного пространства.

Идея метода k-средних была одновременно сформулирована Гуго Штейнгаузом и Стюартом Ллойдом в 1957 г. Сам термин «k-средних» был впервые введен Дж. Маккуинном в 1967 г.

Алгоритм k средних (k-means)

Алгоритм k средних (англ. k-means) — один из алгоритмов машинного обучения, решающий задачу кластеризации. Этот алгоритм является неиерархическим [1] , итерационным методом кластеризации [2] , он получил большую популярность благодаря своей простоте, наглядности реализации и достаточно высокому качеству работы. Был изобретен в 1950-х годах математиком Гуго Штейнгаузом [3] и почти одновременно Стюартом Ллойдом [4] . Особую популярность приобрел после публикации работы МакКуина [5] в 1967.

Алгоритм представляет собой версию EM-алгоритма [6] , применяемого также для разделения смеси гауссиан. Основная идея алгоритма k-means заключается в том, что данные произвольно разбиваются на кластеры, после чего итеративно перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике.

Цель алгоритма заключается в разделении [math]n[/math] наблюдений на [math]k[/math] кластеров таким образом, чтобы каждое наблюдение принадлежало ровно одному кластеру, расположенному на наименьшем расстоянии от наблюдения.

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

• набор из [math]n[/math] наблюдений [math]X=\<\mathbf_1, \mathbf_2, . \mathbf_n\>, \mathbf_i \in \mathbb^d, \ i=1. n[/math] ;
• [math]k[/math] — требуемое число кластеров, [math]k \in \mathbb, \ k \leq n[/math] .

Разделить множество наблюдений [math]X[/math] на [math]k[/math] кластеров [math]S_1, S_2, . S_k[/math] :

• [math]S_i \cap S_j= \varnothing, \quad i \ne j[/math]

• [math]\bigcup_^ S_i = X[/math]

Действие алгоритма:

Алгоритм k-means разбивает набор [math]X[/math] на [math]k[/math] наборов [math]S_1, S_2, . S_k,[/math] таким образом, чтобы минимизировать сумму квадратов расстояний от каждой точки кластера до его центра (центр масс кластера). Введем обозначение, [math]S=\[/math] . Тогда действие алгоритма k-means равносильно поиску:

[math]\arg\min_ \sum\limits_^k \sum\limits_ <\mathbf\in S_i> \rho(\mathbf, \mathbf<\mu>_i )^2,[/math]

[math](1)[/math]

где [math]\mathbf<\mu>_i[/math] – центры кластеров, [math]i=1. k, \quad \rho(\mathbf, \mathbf<\mu>_i)[/math] – функция расстояния между [math]\mathbf[/math] и [math]\mu_i[/math]

Шаги алгоритма:

1. Начальный шаг: инициализация кластеров Выбирается произвольное множество точек [math]\mu_i, \ i=1. k,[/math] рассматриваемых как начальные центры кластеров: [math]\mu_i^ = \mu_i, \quad i=1. k[/math]
2. Распределение векторов по кластерамШаг [math]t: \forall \mathbf_i \in X, \ i=1. n: \mathbf_i \in S_j \iff j=\arg\min_\rho(\mathbf_i,\mathbf<\mu>_k^)^2[/math]
3. Пересчет центров кластеровШаг [math]t: \forall i=1. k: \mu_i^ = \cfrac<|S_i|>\sum_<\mathbf\in S_i>\mathbf[/math]
4. Проверка условия останова:
   • if [math]\exists i\in \overline: \mu_i^ \ne \mu_i^[/math] then
     • [math]t = t + 1[/math] ;
     • goto 2;
   • else
     • stop

1.3 Вычислительное ядро алгоритма

Вычислительным ядром являются шаги 2 и 3 приведенного выше алгоритма: распределение векторов по кластерам и пересчет центров кластеров.

Распределение векторов по кластерам предполагает вычисление расстояний между каждым вектором [math]\mathbf_i \in X, \ i= 1. n[/math] и центрами кластера [math]\mathbf<\mu>_j, \ j= 1. k[/math] . Таким образом, данный шаг предполагает [math]kn[/math] вычислений расстояний между [math]d[/math] -мерными векторами.

Пересчет центров кластеров предполагает [math]k[/math] вычислений центров масс [math]\mathbf<\mu>_i[/math] множеств [math]S_i, \ i=1. k,[/math] представленных выражением в шаге 3 представленного выше алгоритма.

1.4 Макроструктура алгоритма

Инициализация центров масс [math]\mu_1, . \mu_k[/math] .

Наиболее распространенными являются следующие стратегии:

• Метод Forgy
  В качестве начальных значений [math]\mu_1, . \mu_k[/math] берутся случайно выбранные векторы.
• Метод случайно разделения (Random Partitioning)
  Для каждого вектора [math]\mathbf_i \in X, \ i=1. n,[/math] выбирается случайным образом кластер [math]S_1, . S_k[/math] , после чего для каждого полученного кластера вычисляются значения [math]\mu_1, . \mu_k[/math] .

Распределение векторов по кластерам

Для этого шага алгоритма между векторами [math]\mathbf_i \in X, \ i=1. n,[/math] и центрами кластеров [math]\mu_1. \mu_k[/math] вычисляются расстояния по формуле (как правило, используется Евлидово расстояние):

[math] \mathbf_1, \mathbf_2 \in \mathbb^d, \quad \rho(\mathbf_1, \mathbf_2) = \lVert \mathbf_1- \mathbf_2 \rVert= \sqrt^(\mathbf_ — \mathbf_)^2>[/math]

[math](2)[/math]

Пересчет центров кластеров

Для этого шага алгоритма производится пересчет центров кластера по формуле вычисления центра масс:

[math] \mu = \cfrac<|S|>\sum_<\mathbf\in S>\mathbf[/math]

[math](3)[/math]

1.5 Схема реализации последовательного алгоритма

1. Инициализировать центры кластеров [math]\mathbf<\mu>_i^, \ i=1. k[/math]
2. [math]t \leftarrow 1[/math]
3. Распределение по кластерам
[math]\quad S_i^=\<\mathbf_p: \lVert\mathbf_p-\mathbf<\mu>_i^\rVert^2 \leq \lVert\mathbf_p-\mathbf<\mu>_j^\rVert^2 \quad \forall j=1. k\>,[/math]
[math]\quad[/math] где каждый вектор [math]\mathbf_p[/math] соотносится единственному кластеру [math]S^[/math]
4. Обновление центров кластеров
[math]\quad \mathbf<\mu>_i^ = \frac<|S^_i|> \sum_<\mathbf_j \in S^_i> \mathbf_j [/math]
5. if [math]\exists i \in \overline: \mathbf<\mu>_i^ \ne \mathbf<\mu>_i^[/math] then
[math]\quad t = t + 1[/math] ;
[math]\quad[/math] goto 3;
[math]~~~[/math] else
[math]\quad[/math] stop

1.6 Последовательная сложность алгоритма

Обозначим [math]\Theta_^[/math] временную сложность вычисления центорида кластера, число элементов которого равна [math]m[/math] , в d-мерном пространстве.

Аналогично [math]\Theta_^d[/math] – временная сложность вычисления расстояния между двумя d-мерными векторами.

Сложность шага инициализации [math]k[/math] кластеров мощности [math]m[/math] в d-мерном пространстве – [math]\Theta_^[/math]

• Стратерия Forgy: вычисления не требуются, [math]\Theta_^ = 0[/math]
• Стратегия случайного разбиения: вычисление центров [math]k[/math] кластеров, [math]\Theta_^ = k \cdot \Theta_^, m \le n[/math]

Cложность шага распределения d мерных векторов по [math]k[/math] кластерам – [math]\Theta_^[/math]

На этом шаге для каждого вектора [math]\mathbf_i \in X, \ i=1. n,[/math] вычисляется [math]k[/math] расстояний до центров кластеров [math]\mathbf<\mu>_1, . \mathbf<\mu>_k[/math]

Сложность шага пересчета центров [math]k[/math] кластеров размера [math]m[/math] в d-мерном пространстве – [math]\Theta_^[/math]

На этом шаге вычисляется [math]k[/math] центров кластеров [math]\mathbf<\mu>_1, . \mathbf<\mu>_k[/math]

Рассчитаем [math]\Theta_^[/math] для кластера, число элементов которого равно [math]m[/math]

[math]\Theta_^[/math] = [math]m \cdot d[/math] сложений + [math]d[/math] делений

Рассчитаем [math]\Theta_^d[/math] в соответствие с формулой [math](2)[/math]

[math]\Theta_^d[/math] = [math]d[/math] вычитаний + [math]d[/math] умножений + [math](d-1)[/math] сложение

Предположим, что алгоритм сошелся за [math]i[/math] итераций, тогда временная сложность алгоритма [math]\Theta_^[/math]

[math]\Theta_^ \le knd+ i(kn(2d-1) + knd) = knd+ i(kn(3d-1)) \thicksim O(ikdn)[/math]

[math]\Theta_^ \le kd + i(knd + kd) = kd + ikd(n+1) \thicksim O(ikdn) [/math]

Получаем, что временная сложность алгоритма k-means кластеризации [math]n[/math] d-мерных векторов на [math]k[/math] кластеров за [math]i[/math] итераций:

[math] \Theta_^ \thicksim O(ikdn) [/math]

1.7 Информационный граф

Рассмотрим информационный граф алгоритма. Алгоритм k-means начинается с этапа инициализации, после которого следуют итерации, на каждой из которых выполняется два последовательных шага (см. «Схема реализации последовательного алгоритма»):

• распределение векторов по кластерам
• перерасчет центров кластеров

Поскольку основная часть вычислений приходится на шаги итераций, распишем информационные графы данных шагов.

Распределение векторов по кластерам

Информационный граф шага распределения векторов по кластерам представлен на рисунке 1. Исходами данного графа является исходные векторы [math]\mathbf_1, . \mathbf_n[/math] , а также центры кластеров [math]\mathbf<\mu>_1, . \mathbf<\mu>_k[/math] , вычисленные ранее (на шаге инициализации, если рассматривается первая итерация алгоритма, или на шаге пересчета центров кластеров предыдущей итерации в противном случае). Каждая пара векторов данных [math]\mathbf_i, \ i=1. n,[/math] и центров кластера [math]\mathbf<\mu>_j, \ j=1. k[/math] : ( [math]\mathbf_i[/math] , [math]\mathbf<\mu>_j[/math] ) подаются на независимые узлы «d» вычисления расстояния между векторами (более подробная схема вычисления расстояния представлена далее, рисунок 2). Далее узлы вычисления расстояния «d», соответствующие одному и тому же исходному вектору [math]\mathbf_i[/math] передаются на один узел «m», где далее происходит вычисление новой метки кластера для каждого вектора [math]\mathbf_i[/math] (берется кластер с минимальным результатом вычисления расстояния). На выходе графа выдаются метки кластеров , [math]L_1, . L_n[/math] , такие что [math]\forall \mathbf_i, \ i=1. n, \ \mathbf_i \in S_j \Leftrightarrow L_i = j[/math] .

Рис. 1. Схема распределения векторов по кластерам. d – вычисление расстояния между векторами; m – вычисление минимума.

Вычисление расстояния между векторами

Подробная схема вычисления расстояния между векторами [math]\mathbf_i, \mathbf<\mu>_j[/math] представлена на рисунке 2. Как показано на графе, узел вычисления расстояния между векторами «d» состоит из шага взятия разности между векторами (узел » [math]-[/math] «) и взятия нормы получившегося вектора разности (узел » [math]||\cdot||^2[/math] «). Более подробно, вычисление расстояния между векторами [math]\mathbf_i = , . >>, \mathbf<\mu>_j = <\mu_, . \mu_>[/math] может быть представлено как вычисление разности между каждой парой компонент [math](x_, \mu_), \ z=1. d[/math] (узел » [math]-[/math] «), далее возведение в квадрат для каждого узла » [math]-[/math] » (узел » [math]()^2[/math] «) и суммирования выходов всех узлов » [math]()^2[/math] » (узел » [math]+[/math] «).

Рис. 2. Схема вычисления расстояния между вектором и центром кластера.

Пересчет центров кластеров

Информационный граф шага пересчета центров кластеров представлен на рисунке 3. Исходами данного графа является исходные векторы [math]\mathbf_1, . \mathbf_n[/math] , а также им соответствующие метки кластера, [math]L_1, . L_n[/math] , такие что [math]\forall x_i, \ i=1. n, \ \mathbf_i \in S_j \Leftrightarrow L_i = j[/math] , вычисленные на этапе распределения векторов по кластерам. Все векторы [math]\mathbf_1, . \mathbf_n[/math] подаются в узлы [math]+_1, . +_k[/math] , каждый узел [math]+_m, \ m = 1. k,[/math] соответствует операции сложения векторов кластера с номером [math]m[/math] . Метки кластера [math]L_1, . L_n[/math] также совместно передаются на узлы [math]S_m, \ m=1. k[/math] , на каждом из которых вычисляется количество векторов в соответствующем кластере (количество меток с соответствующим значением). Далее каждая пара выходов узлов [math]+_m[/math] и [math]S_m[/math] подается на узел » [math]/[/math] «, где производится деление суммы векторов кластера на количество элементов в нем. Значения, вычисленные на узлах » [math]/[/math] «, присваиваются новым центрам кластеров (выходные значения графа).

Рис. 3. Схема пересчета центров кластеров

1.8 Ресурс параллелизма алгоритма

Работа алгоритма состоит из [math]i[/math] итераций, в каждой из которых происходит распределение [math]d[/math] -мерных векторов по [math]k[/math] кластерам, а также пересчет центров кластеров в [math]d[/math] -мерном пространстве. В шаге распределения [math]d[/math] -мерных векторов по [math]k[/math] кластерам расстояния между вектором и центрами кластеров вычисляются независимо (отсутствуют информационные зависимости). Центры масс кластеров также пересчитываются независимо друг от друга. Таким образом, имеет место массовый параллелизм. Вычислим параллельную сложность [math]\Psi_*[/math] каждого из шагов, а также параллельную сложность всего алгоритма, [math]\Psi_[/math] . Будем исходить из предположения, что может быть использовано любое необходимое число потоков.

Распределение [math]d[/math] -мерных векторов по [math]k[/math] кластерам

Поскольку на данном шаге для каждой пары векторов [math]\mathbf_i, \ i=1. n[/math] и [math]\mathbf<\mu>_j, \ j=1. k,[/math] операции вычисления расстояния не зависят друг от друга, они могут выполняться параллельно. Тогда, разделив все вычисление расстояний на [math]n[/math] потоков, получим, что в каждом потоке будет выполняться только одна операция вычисления расстояния между векторами размерности [math]d[/math] . При этом каждому вычислительному потоку передаются координаты центров всех кластеров [math]\mathbf<\mu>_1, . \mathbf<\mu>_k[/math] . Таким образом, параллельная сложность данного шага определяется сложностью параллельной операции вычисления расстояния между [math]d[/math] -мерными векторами, [math]\Psi_^d[/math] и сложностью определения наиболее близкого кластера (паралельное взятие минимума по расстояниям), [math]\Psi_^k[/math] . Для оценки [math]\Psi_^d[/math] воспользуемся параллельной реализацией нахождения частичной суммы элементов массива путем сдваивания. Аналогично, [math]\Psi_^k = \log(k)[/math] . В результате, [math]\Psi_^d = O(\log(d))[/math] . Таким образом:

Пересчет центров кластеров в d-мерном пространстве

Поскольку на данном шаге для каждого из [math]k[/math] кластеров центр масс может быть вычислен независимо, данные операции могут быть выполнены в отдельных потоках. Таким образом, параллельная сложность данного шага, [math]\Psi_^[/math] , будет определяться параллельной сложностью вычисления одного центра масс кластера размера [math]m[/math] , [math]\Psi_^[/math] , а так как [math]m \le n \Rightarrow \Psi_^ \le \Psi_^[/math] . Сложность вычисления центра масс кластера [math]d[/math] -мерных векторов размера n аналогично предыдущим вычислениям равна [math]O(\log(n))[/math] . Тогда:

Общая параллельная сложность алгоритма

На каждой итерации необходимо обновление центров кластеров, которые будут использованы на следующей итерации. Таким образом, итерационный процесс выполняется последовательно [7] . Тогда, поскольку сложность каждой итерации определяется [math]\Psi_^[/math] и [math]\Psi_[/math] , сложность всего алгоритма, [math]\Psi_[/math] в предположении, что было сделано [math]i[/math] операций определяется выражением

1.9 Входные и выходные данные алгоритма

Входные данные

• Матрица из [math]n \cdot d[/math] элементов [math]x_ \in \mathbb, \ i=1. n, \ j=1. d,[/math] – координат векторов (наблюдений).
• Целое положительное число [math]k, \ k \le n[/math] – количество кластеров.

Объем входных данных
[math]1[/math] целое число + [math]n \cdot d[/math] вещественных чисел (при условии, что координаты – вещественные числа).

Выходные данные
[math]n[/math] целых положительных чисел [math]L_1, . L_n[/math] – номера кластеров, соотвествующие каждому вектору (при условии, что нумерация кластеров начинается с [math]1[/math] ).

Объем выходных данных
[math]n[/math] целых положительных чисел.

1.10 Свойства алгоритма

Вычислительная мощность алгоритма k-means равна [math]\frac = ki [/math] , где [math]k[/math] – число кластеров, [math]i[/math] – число итераций алгоритма.

Алгоритм k-means является итерационным. Количество итераций алгоритма в общем случае не фиксируется и зависит от начального расположения объектов в пространстве, параметра [math]k[/math] , а также от начального приближения центров кластеров, [math]\mu_1, . \mu_k[/math] . В результате этого может варьироваться результат работы алгоритма. При неудачном выборе начальных параметров итерационный процесс может сойтись к локальному оптимуму [8] . По этим причинам алгоритм не является ни детермирированным, ни устойчивым.

Соотношение последовательной и параллельной сложности алгоритма

Сильные стороны алгоритма:

• Сравнительно высокая эффективность при простоте реализации
• Высокое качество кластеризации
• Возможность распараллеливания
• Существование множества модификаций

Недостатки алгоритма [9] :

• Количество кластеров является параметром алгоритма
• Чувствительность к начальным условиям Инициализация центров кластеров в значительной степени влияет на результат кластеризации.
• Чувствительность к выбросам и шумам Выбросы, далекие от центров настоящих кластеров, все равно учитываются при вычислении их центров.
• Возможность сходимости к локальному оптимуму Итеративный подход не дает гарантии сходимости к оптимальному решению.
• Использование понятия «среднего» Алгоритм неприменим к данным, для которых не определено понятие «среднего», например, категориальным данным.

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Возможные способы и особенности параллельной реализации алгоритма

2.3 Результаты прогонов

2.4 Выводы для классов архитектур

В однопоточном режиме на наборах данных, представляющих практический интерес (порядка нескольких десятков тысяч векторов и выше), время работы алгоритма неприемлемо велико. Благодаря свойству массового параллелизма должно наблюдаться значительное ускорение алгоритма на многоядерных архитектурах (Intel Xeon), а также на графических процессорах, даже на мобильных вычислительных системах (ноутбуках), оснащенных видеокартой. Алгоритм k-means также будет демонстрировать значительное ускорение на сверхмощных вычислительных комплексах (суперкомпьютерах, системах облачных вычислений [10] ).

На сегодняшний день существует множество реализаций алгоритма k-means, в частности, направленных на оптимизацию параллельной работы на различных архитектурах [11] [12] [13] . Предлагается множество адаптаций алгоритма под конкретные архитектуры. Например, авторы работы [14] производят перерасчет центров кластеров на этапе распределения векторов по кластерам.

3 Литература

1. ↑ «https://ru.wikipedia.org/wiki/Иерархическая_кластеризация»
2. ↑ «https://ru.wikipedia.org/wiki/Кластерный_анализ»
3. ↑ Steinhaus, Hugo. «Sur la division des corp materiels en parties.» Bull. Acad. Polon. Sci 1.804 (1956): 801.
4. ↑ Lloyd, S. P. «Least square quantization in PCM. Bell Telephone Laboratories Paper. Published in journal much later: Lloyd, SP: Least squares quantization in PCM.» IEEE Trans. Inform. Theor.(1957/1982).
5. ↑ MacQueen, James. «Some methods for classification and analysis of multivariate observations.» Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. Vol. 1. No. 14. 1967.
6. ↑ «https://ru.wikipedia.org/wiki/EM-алгоритм»
7. ↑ Zhao, Weizhong, Huifang Ma, and Qing He. «Parallel k-means clustering based on mapreduce.» IEEE International Conference on Cloud Computing. Springer Berlin Heidelberg, 2009.
8. ↑ Von Luxburg, Ulrike. Clustering Stability. Now Publishers Inc, 2010.
9. ↑ Ortega, Joaquín Pérez, Ma Del Rocío Boone Rojas, and María J. Somodevilla. «Research issues on K-means Algorithm: An Experimental Trial Using Matlab.»
10. ↑ «Issa. «Performance characterization and analysis for Hadoop K-means iteration». Journal of Cloud Computing, 2016″
11. ↑ «Raghavan R. A fast and scalable hardware architecture for K-means clustering for big data analysis : дис. – University of Colorado Colorado Springs. Kraemer Family Library, 2016.»
12. ↑ «Yang, Luobin, et al. «High performance data clustering: a comparative analysis of performance for GPU, RASC, MPI, and OpenMP implementations.» The Journal of supercomputing 70.1 (2014): 284-300.»
13. ↑ «Li, You, et al. «Speeding up k-means algorithm by GPUs.» Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE, 2010.»
14. ↑ «Kanan, Gebali, Ibrahim. «Fast and Area-Efficient Hardware Implementation of the K-means Clustering Algorithm». WSEAS Transactions on circuits and systems. Vol. 15. 2016″

• Уровень алгоритма
• Статьи в работе

Метод k-means

Итеративный алгоритм кластерного анализа к- means (к-средних) группировки документов по фиксированному количеству кластеров заключается в следующем: случайным образом выбирается к векторов, которые определяются как центроиды (наиболее типичные представители) кластеров.

Затем к кластеров

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

где х — документ, центроид кластера N — размерность пространства термов.

После этого вектор приписывается к тому кластеру, к которому он наиболее близок. Далее векторы группируются и перенумеровываются соответственно принадлежности к кластерам. Потом для каждого из новых кластеров заново определяется центроид — вектор, наиболее

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

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

Алгоритм к-means максимизирует функцию качества кластеризации Q:

В отличие от метода LSI, k-means может использоваться для группирования динамических информационных потоков благодаря своей вычислительной простоте — O(kn), где n -количество объектов группирования (документов). Недостатком метода является то, что каждый документ может попасть всего лишь в один кластер.

Иерархическое группирование-объединение

Иерархическое группирование-объединение (Hierarchical Agglomerative Clustering, HAC) начинается с того, что каждому объекту в соответствие ставится отдельный кластер, а затем происходит объединение кластеров, которые наиболее близки друг к другу, в соответствии с выбранным критерием. Алгоритм завершается, когда все объекты объединяются в единый кластер. История объединений образует бинарное дерево иерархии кластеров.

Разновидности алгоритма HAC различаются выбором критериев близости (подобия) между кластерами. Например, близость между двумя кластерами может вычисляться как максимальная близость между объектами из этих кластеров.

Иерархическая кластеризация очень часто применяется при социологическом анализе, в биологии, экономике и т.д. Главным образом там, где заранее неизвестно количество кластеров.

Для иерархической кластеризации необходимо каким-либо образом определить расстояние между узлами нашего графа (сети). Т.е. нам необходимо получить количественную оценку близости узлов, аналогичную расстоянию в обычном евклидовом пространстве. Рассмотрим два наиболее используемых определения. Первое это Евклидово расстояние (Euclidean distance), определяется следующим образом:

здесь N — число узлов в сети. Евклидово расстояние точно равно нулю для полностью структурно — эквивалентных узлов и увеличивается для узлов, которые не имеют общих соседей. Второе определение базируется на корреляции Пирсона между строками (столбцами) матрицы инцидентности.

Здесь структурно эквивалентные узлы те, которые имеют большой коэффициент корреляции.

После того как мы любым способом определили матрицу расстояний можно приступать непосредственно к иерархической кластеризации. Остановимся подробнее на англомеративном алгоритме. Вначале опишем идею алгоритма. Пусть у нас есть точки xl,x2. xNи матрица относительных расстояний xtj. На первом шаге каждую точку считаем отдельным кластером. Затем ближайшие (в смысле расстояния) точки объединяем и считаем одним кластером, и так далее пока не задействуются все точки. На выходе мы получим дерево (дендограмму). При подсчете расстояний между кластерами наиболее часто используют один из двух следующих алгоритмов. Single-link алгоритм считает минимум из возможных расстояний между парами узлов, находящихся в кластере, Complete-link алгоритм считает максимум из этих расстояний.

Приведем пошаговый пример для Single-link алгоритма. Пусть есть граф, показанный на рис. 2.5.1.

Рис. 2.5.1 — Пример графа

Записав матрицу Евклидовых расстояний (1), видим, что минимальное расстояние равное нулю соответствует узлам 1 и 5. Поэтому на первом шаге объединяем эти узлы в один кластер.

На втором шаге снова записываем матрицу расстояний, используя алгоритм Single-link. Следующее расстояние после нулевого расстояния равно единице. И на этом шаге мы получаем два кластера, которые суммарно включают все узлы сети.

Если разрезать дендограмму вдоль пунктирной линии 1 — то мы получим два кластера содержащие узлы (1, 5, 2) и (3, 4, 6) соответственно. Что соответствует и интуитивному разбитию на кластера, см. рис. 1. Если резать вдоль второй пунктирной линии, то получаем три кластера (1, 5), (2) и (3, 4, 6).

На рис. 2.5.2 показана окончательная дендограмма

Рис. 2.5.2 — Использован алгоритм Single-link

Если при иерархической кластеризации использовать алгоритм Complete-link, то получим немного другую дендограмму, см рис. 2.5.3.

Отличие в алгоритмах проявится на втором шаге построения. При использовании алгоритма Single-link в один кластер к узлам (4, 6) добавляется узел 3, поскольку он связан с узлом 6 единичным расстоянием, таким же, как и внутрекластерное расстояние. А при использовании Complete-link алгоритма, узел 3 присоединяется на следующем шаге т.к. здесь необходимо смотреть по максимальному расстоянию, т.е. по расстоянию от узла 3 до узла 4, которое больше внутрикластерного расстояния между узлами 4 и 6.

Рис. 2.5.3 — Использован алгоритм Complete-link

Кластеризация пространственных данных – k-means и иерархические алгоритмы

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

Для иллюстрации каждого алгоритма рассмотрим пример кластеризации пациентов, выделенных по одной болезни. Наша цель – определить, какой метод лучше подходит, чтобы кластеризовать точки и выделить места скопления заболевших.

Что есть в этой статье:

• Пара слов о кластеризации
• Разделительные алгоритмы и их типы
• Алгоритм кластеризации k-means
• Работа с k-means с примерами кода на Python
• Иерархические алгоритмы и их типы
• Агломеративная кластеризация с примерами кода на Python

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

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

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

Три основных типа алгоритмов кластеризации:

• разделительные – основаны на поэтапном улучшении разбиения исходного набора данных;
• иерархические – создают иерархию вложенных разбиений;
• алгоритмы на основе плотности – разбивают объекты на кластеры на основе оценки плотности распределения.

Поговорим подробнее о разделительных и иерархических алгоритмах.

Разделительные алгоритмы и их типы

Разделительные алгоритмы (partition clustering) делят объекты данных на непересекающиеся группы. Ни один объект не может находится в более чем одном кластере, и в каждом кластере должен быть хотя бы один объект.

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

Примеры разделительных алгоритмов:

• K-means (ниже рассмотрим, как он работает)
• CLARANS (кластеризация больших приложений на основе рандомизированного поиска)

Где используются разделительные алгоритмы:

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

Алгоритм кластеризации k-means

K-means (или метод k-средних) – один из наиболее популярных методов кластеризации. Он не сильно подходит для пространственных данных, но является простым и важным для понимания.

Например, если данных очень много, использовать другие алгоритмы будет затруднительно, и даже в случае геоданных удобнее применить k-means.

Основная идея метода — итеративное повторение двух шагов:

• распределение объектов выборки по кластерам;
• пересчет центров кластеров.

Шаги работы алгоритма кластеризации K-means

1. В начале работы алгоритма выбираются K случайных центров.
2. Каждый объект выборки относят к тому кластеру, к центру которого объект оказался ближе.
3. Далее центры кластеров подсчитывают как среднее арифметическое векторов признаков всех вошедших в этот кластер объектов (то есть центр масс кластера). Центры кластеров обновляются.
4. Объекты заново перераспределяются по кластерам, а затем можно снова уточнить положение центров.
5. Процесс продолжается до тех пор, пока центры кластеров не перестанут меняться.

Преимущества алгоритма K-means

1. Алгоритм k-средних хорошо справляется с задачей кластеризации в случае, когда кластеры линейно разделимы и представляют собой отдельные скопления точек.
2. Быстрая работа алгоритма.

Недостатки алгоритма K-means

1. Не гарантируется достижение глобального минимума суммарного квадратичного отклонения V, а только одного из локальных минимумов.
2. Результат зависит от выбора исходных центров кластеров, их оптимальный выбор неизвестен.
3. Число кластеров надо знать заранее.

Реализация k-means на примере

Все расчеты проводились в Python с библиотекой sk-learn.

На вход алгоритму k-means необходимо задать гиперпараметр – количество кластеров, на которое будут разбиты данные. Первым шагом необходимо определить это значение. Для этого итерационно запускаем алгоритм с количеством кластеров от 1 до 100 и при этом оптимизируем четыре основные метрики кластеризации (о метриках качества поговорим в следующих статьях).

На выходе функции получаем датасет с количеством кластеров и значением метрик кластеризации. Берем пять первых значений.

В результате мы получили, что оптимальным количеством будет 10, 40, 55, 45, 30 кластеров.

Далее переходим к запуску алгоритма.
Для каждого алгоритма кластеризации были написаны функции:

• Функция, которая принимает на вход данные и список с наилучшим количеством кластеров.
• В ходе работы функции ко всем точкам из датасета добавляется поле с номером кластера, к которому они были отнесены.
• Для более понятной визуализации точки с одинаковым значением кластера объединяются в альфа-форму – полигон, который объединяет самые выпуклые точки. Подсчитывается количество точек в каждой альфе-форме. Файлы с альфа-формами сохраняются в формате geojson.

Давайте посмотрим, какие кластеры у нас получились. На выходе получаем столько видов кластеризации, сколько различных гиперапараметров было задано – в нашем случае получили 5 вариаций.

На картах цветовая шкала кластеров зависит от количества точек. Поверх отображены сами точки.

Результат – с k-means точки довольно четко группируются на кластеры. Заметно, что при 10 кластерах в одном кластере может быть до двух-трех скоплений точек, что в нашем случае не является правильным. При 20 кластерах таких случаев меньше, и кластеры довольно четко разделены.

Если мы берем еще меньшее деление, видно, что некоторые скопления делятся на два и более частей, что неправильно для нашей задачи. Поэтому лучший вариант, основанный на визуальной составляющей – это 20 кластеров.

На всех примерах заметно, что есть значительная часть точек-выбросов, которые находятся далеко от центра кластера, из-за чего альфа-формы получаются неправильной формы. Этого можно избежать, используя плотностные алгоритмы, которые умеют определять выбросы, или заранее отфильтровать датасет и выявить выбросы.

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

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

Типы иерархических алгоритмов кластеризации:

• Агломеративные (от меньшего к большему) – одиночные объекты постепенно объединяются в кластер.
• Разделительная кластеризация (от большего к меньшему): все данные собираются в один кластер и далее происходит деление на два, четыре и так далее кластеров.

Источник: https://quantdare.com/hierarchical-clustering/

Принцип работы алгоритма

Для работы этих алгоритмов определяется матрица близости, которая содержит попарные расстояния между всеми объектами. На основании нее происходит объединение или разделение объектов.

Когда в одном кластере более одного объекта, берется среднее расстояние.
После каждой итерации заново рассчитывается матрица близости.

Условия окончания работы алгоритма

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

1. Получено нужное количество кластеров.
2. Достигнуто определенное условие, связанное с расстоянием между кластерами – например, если оно сильно изменилось с прошлой итерации.
3. Анализ по дендрограмме. На практике обычно кластеризацию проводят вплоть до одного кластера, включающего в себя всю выборку, а затем анализируют получившуюся иерархическую структуру с помощью дендрограммы.

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

Проведем агломеративную кластеризацию, используя в качестве точки остановки заданное количество кластеров.

Для агломеративной кластеризации тоже сначала рассчитаем оптимальное количество кластеров исходя из метрик кластеризации, как и с методом k-means. Для этого напишем функцию, которая разбивает данные от одного до ста кластеров и сравнивает полученные кластеры по трем метрикам.

Оптимальное количество кластеров: 40, 25, 45, 20 и 35.

Следующий шаг – написать функцию, которая производит кластеризацию с нужными гиперпараметрами.

Как и в k-means, на вход этой функции подается датасет с точками. Далее производится кластеризация. В итоге мы получаем альфа-формы и датасет с точками, которые имеет значение кластеров.

Посмотрим на кластеры, которые у нас получились.

В случае алгомеративной кластеризации наиболее оптимальным числом кластеров мне показалось 30. В этом случае четче всего выделяются скопления точек. Однако, как и в алгоритме k-means, мы видим, что кластеры объединяют даже те точки, которые можно было считать выбросами.

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

K-means и иерархическая кластеризация отлично справляются с задачей кластеризации компактных и хорошо разделенных кластеров.

В следующем тексте этой серии рассмотрим плотностные алгоритмы, наиболее подходящие для кластеризации пространственных данных. И если вы хотите узнать больше, мы всегда готовы научить вас работе с геоданными в Python и QGIS.