4.3 Алгоритмы кластеризации

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

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

Методы кластерного анализа можно разделить на две группы:

• иерархические;

• неиерархические.

Каждая из групп включает множество подходов и алгоритмов.

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

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

Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие.

Иерархические агломеративные методы (Agglomerative Nesting, AGNES) характеризуются последовательным объединением исходных элементов и соответствующим уменьшением числа кластеров. В начале работы алгоритма все объекты являются отдельными кластерами. На первом шаге наиболее похожие объекты объединяются в кластер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер.

Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA) являются логической противоположностью агломеративным методам. В начале работы алгоритма все объекты принадлежат одному кластеру, который на последующих шагах делится на меньшие кластеры, в результате образуется последовательность расщепляющих групп.

Принцип работы описанных выше групп методов в виде дендрограммы показан на рис. 3.1.

Рисунок 4.1 - Дендрограмма агломеративных и дивизимных методов

Иерархические методы кластеризации различаются правилами построения кластеров. В качестве правил выступают критерии, которые используются при решении вопроса о "схожести" объектов при их объединении в группу (агломеративные методы) либо разделения на группы (дивизимные методы).

Иерархические методы кластерного анализа используются при небольших объемах наборов данных. Преимуществом иерархических методов кластеризации является их наглядность.

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

Рисунок 4.2 - Пример вертикальной дендрограммы

Числа 11, 10, 3 и т.д. соответствуют номерам объектов или наблюдений исходной выборки. Мы видим, что на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На втором шаге продолжается объединение в кластеры: наблюдения 11, 10, 3, 4, 5 и 7, 8, 9. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер.

Неиерархические методы кластерного анализа

Одной из широко используемых методик кластеризации является разделительная кластеризация, в соответствии с которой для выборки данных, содержащих n записей (объектов), задается число кластеров k, которое должно быть сформировано. Затем алгоритм разбивает все объекты выборки на k групп (k<n), которые и представляют собой кластеры.

К наиболее простым и эффективным алгоритмам кластеризации относится k-means или в русскоязычном варианте k-средних. Он состоит из четырех шагов.

Алгоритм k-means

Конструктивно алгоритм представляет собой итерационную процедуру следующего вида.

1. Задается число кластеров k, которое должно быть сформировано из объектов исходной выборки.

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

3. Для каждой записи исходной выборки определяется ближайший к ней центр кластера.

4. Производится вычисление центроидов – центров тяжести кластеров. Это делается путем определения среднего для значений каждого признака всех записей в кластере. Например, если в кластер вошли три записи с наборами признаков (x₁, y₁), (x₂, y₂), (x₃, y₃), то координаты его центроида будут рассчитываться следующим образом:

.

Затем старый центр кластера смещается в его центроид. Таким образом, центроиды становятся новыми центрами кластеров для следующей итерации алгоритма.

Шаги 3 и 4 повторятся до тех пор, пока выполнение алгоритма не будет прервано либо пока не будет выполнено условие в соответствии с некоторым критерием сходимости.

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

Рисунок 4.3 – Пример работы алгоритма k-means