Полная версия

Главная

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

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

Метод 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.

 
<<   СОДЕРЖАНИЕ   >>