Целевые функции кластеризации

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

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

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

Сформулируем некоторые целевые функции, способные оценить качество классификации и выбрать оптимальные варианты.

А. Минимум объектов, не попавших ни в один кластер (потери классификации)

Несмотря на то, что потери объектов при классификации - процесс неизбежный, постановщик задачи, желающий сделать исследование репрезентативным, старается свести эти потери к минимуму:

где:  - объект, который после окончания расчетов не попал ни в один кластер.

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

Если количество объектов, не вошедших ни в один кластер после завершения всех вариантов классификации, достаточно велико, разумно провести специальное исследование причин подобных результатов.

В.Максимально возможная компактность каждого кластера

Компактность кластера можно определить следующим образом:

• разделить исходное множество на кластеры;

• у каждого кластера вычислить условный «центр массы».

С. Максимальное суммарное расстояние между границами (оболочками) кластеров

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

D. Максимальное совпадение признаков (однородность) в каждом кластере

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

Поэтому важно найти объективную целевую функцию кластеризации, которая могла бы оценить схожесть характеристик объектов и на основании близости наибольшего количества показателей сформировать однородные кластеры. Впрочем, подобная целевая функция скрывает в себе немало трудноразрешимых задач: ведь не все показатели необходимы для точной характеристики объектов. Более того, «лишние» признаки способны дезориентировать исследователя, нивелируя интегральные (обобщающие) характеристики объектов изучения.

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

Е. Максимальное приближение реального числа кластеров к теоретически идеальному.

F. Максимальная концентрация объектов в каждом кластере около расчетного ядра.

G. Максимальное приближение расположения объектов в кластерах к теоретически обоснованным законам распределения случайных величин.

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

Методы кластеризации

-K-средних (K-means)

-Графовые алгоритмы кластеризации

-Статистические алгоритмы кластеризации

-Алгоритм ФОРЕЛЬ

-Иерархическая кластеризация или таксономия

-Нейронная сеть Кохонена

-Ансамбль кластеризаторов