2 Разработка методики использования гибридных метрик

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

При детальном рассмотрении механизма влияния природы исходных данных на результат кластеризации была обнаружена следующая закономерность. Если исходный набор данных представляет собой совокупность объектов с ярко выраженной кластерной структурой без “зашумлений” (рисунок 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-ый атрибут центра кластера.

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

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

,

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

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

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

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

,

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

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