Методика применения гибридных метрик

При детальном рассмотрении механизма влияния природы исходных данных на результат кластеризации была обнаружена следующая закономерность. Если исходный набор данных представляет собой совокупность объектов с ярко выраженной кластерной структурой без “зашумлений” (рисунок 2.1), то результаты выполнения алгоритма k-means стабильны и не зависят от выбранной метрики. При этом конечное расположение центров кластеров также не зависит от выбранной метрики.

Рисунок 2.1 – Кластеризация в условия отсутствия зашумлений

При появлении “зашумлений” в исходном наборе данных результаты кластеризации начинают зависеть от выбранной метрики. По всей видимости, это связано со следующей особенностью алгоритма k-means. Дело в том, что на каждой итерации алгоритм определяет принадлежность всех без исключения объектов (в том числе и “шумовых”) к одному из кластеров, а положение центров кластеров на следующей итерации рассчитывается по атрибутам объектов, принадлежащих данному кластеру. И если в кластер попадает “шумовой” объект, то он отклоняет центроид от первоначального положения. А это приводит к тому, что часть объектов, которые по идее должны относиться к одному кластеру, переходят в другой кластер, что приводит к отклонению центроида уже соседнего кластера (рисунок 2.2). И так далее по цепочке.

Рисунок 2.2 – Кластеризация при наличии “шумового” объекта. Крестами указаны центы кластеров, стрелками показано смещение центров кластеров под влиянием “зашумления”

Решение этой проблемы заключается в отсеивании “шумовых” объектов на этапе расчета центров кластеров. Но нужно понять какие из объектов являются “шумовыми”.

В качестве признака “шумового” объекта предложено использовать свойство таких объектов (при прочих равных условия) менять свое отношение к разным кластерам в зависимости от используемой в алгоритме метрики.

Применив вышесказанное к алгоритму k-means можно получить его новую модификацию которая будет состоять из следующих шагов:

1. Формирование набора данных состоящих из n объектов и N атрибутов. Задание необходимого количества k кластеров.

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

3. Расчет от каждого объекта к каждому центру кластера расстояние с использованием метрики Евклида:

где - i-ый атрибут объекта, - i-ый атрибут центра кластера.

Затем для кластера t (t=1…k) формируется множество , в котором содержаться объекты, принадлежащему данному кластеру. Объект относится к тому кластеру, значение метрики с которым у него принимает минимальное значение.

4. Расчет от каждого объекта к каждому центру кластера расстояние с использованием метрики Манхэттена:

где - i-ый атрибут объекта, - i-ый атрибут центра кластера.

5. Расчет от каждого объекта к каждому центру кластера расстояние с использованием метрики Чебышева:

где - i-ый атрибут объекта, - i-ый атрибут центра кластера, max() – функция поиска максимального значения.

6. Таким образом, будут сформированы следующие множества объектов: - множество объектов относящихся к кластеру с номером t по метрике Евклида; - множество объектов относящихся к кластеру с номером t по метрике Манхэттена, - множество объектов относящихся к кластеру с номером t по метрике Чебышева. Для исключения “шумовых” объектов выполняется следующее действие:

7. Затем с использование множества Gib_t производится уточнение координат центра кластера t:

где N – количество атрибутов у объектов, - значение j-го атрибута у i-го объекта, входящего в множество для k-ого кластера.

Шаги 3-7 повторяются рекурсивно до тех пор, пока границы кластеров и расположение центроидов не перестанут изменяться от итерации к итерации.