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

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

1. Агломеративные, при которых создание кластеров происходит благодаря группировке мелких. Кластер-дерево начинает формироваться от листьев к стволу.
2. Дивизионные – формируются обратным способом, когда происходит дробленее крупных кластеров. Кластер дерево формируется от ствола к листьям.

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

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

Кластеризация проводится в несколько этапов.

1. Отбор данных для группировки.
2. Определение ключевых переменных для группировки объектов в массиве. Если потребуется, то проводится нормализация значений.
3. Определение значений, задающих похожесть объектов.
4. Применение выбранного метода кластерного анализа, позволяющего образовать группы. Стоит учесть, что при выборе разных способов формирование групп может происходить по-разному.
5. Получение результатов анализа для дальнейшего исследования.

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

Как же происходит определение «похожести» объектов? Первым делом создается вектор характеристик. Его можно применять для всех объектов в массиве. Чаще всего он представляется в виде набора чисел. Например: рост, вес, возраст человека. Но существуют и методы, которые работают не с числовыми, а качественными характеристиками. Однако их все же можно выразить с помощью перевода к числовому виду. Простейший пример – обозначение места жительства человека путем перевода его в код региона. Москва – 495, Сахалин – 65 и т.д.

После того как было выполнено определение вектора, необходимо провести нормализацию, чтобы каждый компонент давал соответствующий вклад, когда будет вестись подсчет «расстояния». При нормализации может выбираться произвольный, удобный для восприятия диапазон. Он может быть, например, от 1 до 100, от -1 до 1 и т.д.

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

Метрика	Когда применяется	Формула
Евклидово расстояние	Часто используемый способ. Позволяет определить геометрическое расстояние в рамках многомерного пространства.
Квадрат Евклидова расстояния	Обеспечивает придание большего расстояния объектам массива, находящимся на большом удалении друг от друга.
Манхэттенское расстояние	Чаще всего результат вычислений такой же, как при определении Евклидова расстояния, но воздействие выбросов уменьшается из-за отсутствия возведения данных в квадрат.
Расстояние Чебышева	Позволяет обозначить объекты как «различные» при их разнице по какой-нибудь координате.
Степенное расстояние	В случаях, когда требуется увеличение или уменьшение веса, который относится к размерности. В ситуациях, когда анализируемые объекты имеют значительное отличие.

Выбор метрики напрямую зависит от исследователя. Можно использовать сразу несколько метрик для проведения анализа.

Существует большое разнообразие классификации методов кластеризации. Среди них можно выделить две наиболее простые.

• Иерархические и плоские. Плоские подразумевают разбиение на кластеры, которые не пересекаются. Метод иерархической кластеризации включает построение не одного разбиения массива на кластеры, которые не будут пересекаться, а системы сложных, вложенных разбиений. Результатом иерархической кластеризации является дерево кластеров. В качестве корня выступает сама выборка, а листьями дерева становятся самые мягкие кластеры.
• Четкие и нечеткие. Первые – алгоритмы, формирующиеся без пересечений. Объект может принадлежать только одному кластеру. Нечеткие позволяют причислять один объект к целому ряду кластеров за счет их разных характеристик. Значения, которые имеют объекты в этом случае, позволяют оценивать степень их отношения к тому или иному кластеру. Другими словами, в алгоритме каждый объект массива данных относится в разной степени к тому или иному кластеру.

Если для проведения исследования были выбраны иерархические алгоритмы кластеризации, то возникает 2 вопроса: как выполнить объединение кластеров друг с другом, а также как измерить «расстояние». Для этого используется несколько метрик.

1. Одиночная связь. При этой методике находится минимальное от объектов и кластеров одного массива. Объекты, находящиеся на наименьшем удалении, становятся одним кластером.
2. Полная связь. Находится путем нахождения максимального расстояния между парой объектов и построения вокруг них кластеров.
3. Невзвешенное попарное среднее. В вычислениях необходимо отыскать среднее расстояние между парами, являющимися частью группировки.
4. Взвешенное попарное среднее. Способ схож с предыдущим, однако размер кластера вычисляется на основании числа объектов, которые содержатся в них. Он играет роль весового коэффициента. Метод пригоден, когда предполагается, что в результате анализа должны получиться разноразмерные кластеры.
5. Невзвешенный центроидный метод. При использовании такого метода, расстояние между кластерами равно расстоянию между их центрами тяжести.
6. Медиана. Схож с предыдущим, однако используется вес кластера, чтобы учитывать разницу кластерных размеров. Когда подразумевается расширение кластера или в случаях, когда один должен получиться больше другого – стоит использовать этот метод вместо предыдущего.

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

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

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

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

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

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

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