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

 

Кластеризация – это разбиение множества объектов, между которыми установлено отношение близости (расстояние), на группы наиболее близких между собой объектов. В каждой группе выделяется объект – центр кластера. Максимальное из расстояний от объектов, входящих в кластер, до его центра называется радиусом кластера. Максимальный радиус всех кластеров, на которые разбито множество объектов, называется радиусом кластеризации этого множества.

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

Пусть

- количество объектов множества,

- номера объектов, ,

- мера близости (расстояние) между объектами с номерами ,

- радиус кластеризации множества.

Рассчитывается признак возможности включения объекта с номером в кластер, центром которого является объект с номером

.

Вводятся неопределенные двоичные переменные - признаки того, является ли объект с номером центром кластера. Тогда условия

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

.

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

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

 

,

,

.