Итерационные алгоритмы классификации

Метод k-средних

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

В параллельных кластер-процедурах реализуется идея оптимизации разбиения в соответствии с некоторым функционалом качества:

• • для некоторого начального разбиения Rt) вычисляют значение /(Д0);
• • затем каждую из точек х, поочередно перемещают во все кластеры и оставляют в том положении, которое соответствует наилучшему значению функционала качества;
• • работа алгоритма заканчивается, когда перемещение точек не дает улучшения качества разбиения.

Обычно такой алгоритм применяют несколько раз, начиная с разных начальных разбиений , и выбирают наилучший вариант разбиения.

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

Одним из наиболее распространенных среди таких неиерархических алгоритмов кластерного анализа является итерационный алгоритм^{-средних} (k-mens), также называемый быстрым кластерным анализом. В отличие от иерархических методов, которые не требуют предварительных предположений относительно числа кластеров, для использования этого метода необходимо иметь априорную информацию о наиболее вероятном количестве кластеров [29, 32].

Идея метода /е-средних заключается в разбиении множества объектов

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

где  — вектор средних (центр тяжести) для группы .

Постановка задачи. Пусть наблюдения требуется разбить на заданное число р однородных (в смысле некоторой метрики расстояний) классов.

Алгоритм состоит в последовательном уточнении эталонных точек , где v — номер итерации, с соответствующим пересчетом приписываемых им весов

Случайным образом выбираются 4 точек (например, первые) исследуемой совокупности, которые принимаются за центры классов. Таким образом, ef = X); af = 1; i = 1,2,к.

На первом шаге алгоритма извлекается наблюдение Хк+{ и выясняется, к какому из центров ef оно оказалось ближе всего. Именно этот самый близкий к Xk+i центр тяжести (эталон) заменяется новым эталоном, определяемым как центр тяжести старого эталона и присоединенной к нему точки Xj+1 (с увеличением на единицу соответствующего ему веса). Все другие эталоны остаются неизменными.

Пересчет центров тяжести кластеров и их весов на 8-м шаге после извлечения наблюдения Хк+$ происходит для г-го кластера по следующим формулам:

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

При достаточно большом числе итераций или при достижении большой совокупности (и — велико) дальнейший пересчет центров тяжести практически не приводит к изменению, т. е. имеет место сходимость к некоторому пределу. На этом работа итерационного алгоритма метода 4-средних заканчивается.

Достоинства алгоритма 4-средних:

• • простота использования;
• • быстрота использования;
• • понятность и прозрачность алгоритма;
• • возможность наглядной интерпретации кластеров с использованием графика средних значений показателей в кластерах.

Недостатки алгоритма 4-средних:

• • метод не гарантирует достижения глобального минимума суммарного квадратичного отклонения, а только одного из локальных минимумов;
• • алгоритм 4-средних крайне чувствителен к выбору начальных приближений центров. Случайный выбор центров может привести к неудовлетворительным результатам кластеризации (для формирования начального приближения лучше выделить 4 наиболее удаленных точек выборки: первые две точки выделяются по максимуму всех попарных расстояний, а каждая следующая точка выбирается так, чтобы расстояние от нее до ближайшей уже выделенной точки было максимально);
• • число кластеров необходимо знать заранее, для чего требуется либо экспертная информация, либо проведение разведывательного анализа, например на основе использования иерархических кластер-процедур. Если число кластеров будет оценено неправильно, то это может привести к неадекватным результатам;

* алгоритм чувствителен к выбросам, которые могут искажать среднее значение (возможным решением этой проблемы является использование модификации алгоритма — алгоритм k-медианы).

Отдельно отметим, что одним из достоинств метода k-средних является возможность наглядной интерпретации кластеров с использованием графика средних значений показателей в кластерах. Пример такого графика представлен на рис. 6.12.

Рис. 6.12. График средних значений показателей в кластерах:

 — первый кластер;  — второй кластер;  — третий кластер Анализ рис. 6.12 позволяет изучить особенности выделенных кластеров, сопоставить их друг с другом, дать название кластерам, понять процессы, происходящие в них.

Так, например, очевидно, что первый кластер характеризуется наибольшими значениями показателей гь г2 и г5 в то время как регионы третьего кластера — самыми низкими значениями показателей z (, z5 и высоким значением г3. Второй кластер в основном характеризуется самыми низкими значениями рассматриваемых показателей.

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