Материал: Кластеризация
Этапы кластеризации
1.Евклидово расстояние. Наиболее распространенная функция расстояния. Представляет собой геометрическим расстоянием в многомерном пространстве:
2.Квадрат евклидова расстояния. Применяется для придания большего веса более отдаленным друг от друга объектам. Это расстояние вычисляется следующим образом:
3.Расстояние городских кварталов (манхэттенское расстояние). Это расстояние является средним разностей по координатам. В большинстве случаев эта мера расстояния приводит к таким же результатам, как и для обычного расстояния Евклида. Однако для этой меры влияние отдельных больших разностей (выбросов) уменьшается (т.к. они не возводятся в квадрат). Формула для расчета манхэттенского расстояния:
6
Этапы кластеризации
4.Расстояние Чебышева. Это расстояние может оказаться полезным, когда нужно определить два объекта как «различные», если они различаются по какой-либо одной координате. Расстояние Чебышева вычисляется по формуле:
5.Степенное расстояние. Применяется в случае, когда необходимо увеличить или уменьшить вес, относящийся к размерности, для которой соответствующие объекты сильно отличаются. Степенное расстояние вычисляется по следующей формуле:
где r и p – параметры, определяемые пользователем. Параметр p ответственен за постепенное взвешивание разностей по отдельным координатам, параметр r ответственен за прогрессивное взвешивание больших расстояний между объектами. Если оба параметра
– r и p — равны двум, то это расстояние совпадает с расстоянием Евклида. |
7 |
Методы кластеризации
1. K-средних. версия EM-алгоритма, применяемого также для разделения смеси гауссиан. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k.
2. Алгоритм FOREL. Алгоритм кластеризации, основанный на идее объединения в один кластер объектов в областях их наибольшего сгущения.
8
Методы кластеризации
3.Иерархическая кластеризация или таксономия
4.Нейронная сеть Кохонена
5.Ансамбль кластеризаторов
9
Иерархическая кластеризация
Дендограмма |
Множество алгоритмов кластеризации, направленных на создание иерархии |
|
|
|
вложенных разбиений исходного множества объектов. |
|
Функции расстояния между кластерами: |
10