Кластеризация объектов

Задача группирования складывается в делении совокупности объектов на группы таким образом, чтобы объекты каждой из образованных при этом групп были в некотором содержании «близкие» один к одному, а объекты, которые принадлежат разным группам, возможно более далекие [39].

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

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

Пусть каждый объект из исходной совокупности отображается точкой в р-мерном пространстве координат. Обозначим через aij – j-ю координату і-го объекта. Отстань между точками Аs и Aq может быть вычислено, например, в метрике Колмогорова по формуле:

Ясно, что при h=2 одержимо обычную евклидову метрику.

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

2.5.1 Выбор центров группирования

Центры группирования выбираются произвольно.

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

являются максимально возможным.

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

2.5.2 Процедура подключения точек к группам

Для подключения дежурной точки вычисляется расстояние от этой точки к каждому из центров группирования. Точка присоединяется к группе, расстояние до центра группирования которой является минимальным. При этом точка l присоединяется к группе k0, если

, (2.12)

Здесь – центр группирования к-ой группы.

Для каждого кластера, что содержит не менее двух точек, вычисляется центр веса. При этом для к-ого кластера, что содержит, например, nk точек, координаты центра веса вычисляется по формулах:

, j=1, 2.,p... (2.13)

Здесь Ek – множество номеров объектов, которые вошли в к-й кластер.

Теперь присоединение l-ої точки к группе k0 будет выполнен, если

, (2.14)

Так же, как и в предыдущей процедуре для каждой точки вычисляются расстояния до центров тяжести кластеров и выбирается минимальное из них. Теперь первой присоединяется и точка l0, для которой избранная минимальное расстояние является наименьшим. Для этой точки l0 выполняется соотношение:

, (2.15)

Для каждой точки вычисляется сумма расстояний ко всем точкам каждого из кластеров, а затем среднее расстояние к кластерам. Точка присоединяется до того из кластеров, среднее настояние к которому минимально. При этом точка l будет присоединена к кластеру k0, если

, (2.16)

Так же, как и в предыдущей процедуре может быть установлен рациональный порядок присоединения точек. При этом для дежурной точки, что присоединяется, l0 выполняется соотношение

, (2.17)

2.5.3 Коррекция положения центров группирования

После того, как все точки распределены, вычисляется критерий качества кластеризации по формуле

(2.18)

Числитель этого выражения характеризует степень компактности полученных кластеров, выделяя самый «пышный» из них. Желательно, чтобы значение числителя было минимальным.

Знаменатель определяет расстояние между центрами веса двух ближайших кластеров. Желательно, чтобы это значение было максимально возможным. Таким образом, для заданного числа кластеров наилучшему варианту группирования будет отвечать минимальное значение критерия h.

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

1) как новые центры группирования выбираются центры веса образованных кластеров;

2) в варианте с гиперсферой (в двумерном случае) выполняется сдвиг положения центров группирования вдоль окружности на некоторый угол . Оценивается критерий качества группирования при новом положении центров группирования.

Процедура поворота выполняется раз. Решению задачи отвечает положение центров группирования, для какого значения h минимально.