Неиерархический кластерный анализ

В методах неиерархического кластерного анализа число кластеров R считается фиксированным и заданным заранее. В алгоритмах кластеризации часто используется понятие центра A_t кластера X_t, t=1,…, R, который находится как решение задачи минимизации некоторого функционала от расстояния, например, следующего вида:

J (A_t, X_t) =.(5).

Функционал J (A_t, X_t) по своему содержанию близок критерию K (X_r^#) компактности кластера и характеризует своего рода «кучность» распределения объектов в признаковом пространстве. Заметим, что в нашем случае центр A_t кластера X_t может совпадать с одним из реально имеющихся объектов A_i из совокупности A, или быть так называемым «фантомным» объектом, сконструированным из признаков x_j в виде (1), но реально отсутствующим в исходной совокупности объектов A.

Обобщенная схема неиерархической кластеризации совокупности объектов A={A₁,…, A_n}, представленных мультимножествами, включает следующие основные этапы.

Шаг 1. Выбрать некоторое начальное разбиение совокупности объектов A на R кластеров A ={X₁,…, X_R}.

Шаг 2. Распределить все объекты A_i по кластерам X_t (t=1,…, R) в соответствии с некоторым правилом. Например, вычислить расстояния d (A_i, X_t) между каждым объектом A_i и кластерами X_t, и поместить объект A_i в ближайший из кластеров X_r, который определяется условием d (A_i, X_r)= =d (A_i, X_t). Или определить центр A_t для каждого кластера X_t, решив уравнение (5), и поместить каждый объект A_i в кластер с ближайшим центром A_s, задаваемый условием d (A_i, A_s) =d (A_i, A_t).

Шаг 3. Если после распределения всех объектов A_i по кластерам X_t объекты не изменят своей кластерной принадлежности, заданной первоначальным разбиением, то остановиться и вывести результат. В противоположном случае вернуться к шагу 2.

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

H (X_opt) = min, (6).

где функционал J (A_i, X_t) определяется, например, выражением (5). В общем случае решение задачи (6) неоднозначно, поскольку функционал H (X_opt) качества разбиения является функцией, имеющей много локальных экстремумов. Конечный результат зависит и от первоначального (близко или далеко от оптимального) распределения объектов по классам.