С.Д.Штовба "Введение в теорию нечетких множеств и нечеткую логику"

В оглавление книги \ К следующему разделу \ К предыдущему разделу

12.1.3. Обобщения алгоритма нечетких c-средних

В базовом алгоритме нечетких c-средних расстояние между объектом и центром кластера рассчитывется через стандартную Евклидову норму: . В кластерном анализе применяются и другие нормы, среди которых часто используется диагональная норма и норма Махалонобиса.

В общем виде норму можно задать через симметричную положительно определенную матрицу B размером следующим образом:

,

где T - операция транспонирования.

Для Евклидовой нормы матрица B представляет собой единичную матрицу:

.

Евклидова норма позволяет выделять кластеры в виде гиперсфер.

Для диагональной нормы матрица B задается следующим образом:

.

Элементы главной диагонали матрицы интерпретируются как веса координат. Диагональная норма позволяет выделять кластеры в виде гиперэллипсоидов, ориентированных вдоль координатных осей.

Для нормы Махалонобиса матрица B рассчитывается через ковариационную матрицу от :

,

где   - ковариационная матрица;

  - вектор средних значений данных.

Норма Махаланобиса позволяет выделять кластеры в виде гиперэллипсоидов, оси которых могут быть ориентированы в произвольных направлениях.

Примеры изолиний различных норм, показаны на рис. 11.1. На рис. 11.2 приведен пример нечеткой кластеризации методом нечетких c-средних при Евклидовом расстоянии. На левой части рисунка показаны данные для кластеризации. На правой части рисунка приведены результаты нечеткой кластеризации. Центры нечетких кластеров обозначены символами '+'. Восемь изолиний функций принадлежности нечетких кластеров построены для значений 0.67, 0.71, 0.75, 0.79, 0.83, 0.87, 0.91 и 0.95.

Рисунок 11.1  - Изолинии различных норм

Рисунок 11.2 - Нечеткая кластеризация при Евклидовой норме

Для некоторых наборов данных "глазная кластеризация" позволяет выделить скопления данных в виде различных геометрических фигур: сферы, эллипсоиды разной ориентации, цепочки и т.п. В результате алгоритмов кластеризации с фиксированной нормой форма всех кластеров получается одинаковой. Алгоритмы кластеризации как-бы навязывают данным неприсущую им структуру, что приводит не только к неоптимальным, но иногда и к принципиально неправильным результатам, Для устранения этого недостатка предложено несколько методов, среди которых выделим алгоритм Густавсона-Кесселя (Gustafson-Kessel algorithm) [5].

Алгоритм Густавсона-Кесселя использует адаптивную норму для каждого кластера, т.е. для каждого i-го кластера существует своя норм-порождающая матрица . В этом алгоритме при кластеризации оптимизуруются не только координаты центров кластеров и матрица нечеткого разбиения, но также и норм-порождающие матрицы для всех кластеров. Это позволяет выделять кластера различной геометрической формы. Критерий оптимальности (11.9) линеен относительно относительно , поэтому для получения ненулевых решений, вводят некоторые ограничения на норм-пораждающие матрицы. В алгоритме Густавсона-Кесселя это ограничение на значение определителя норм-пораждающих матриц:

.

Оптимальное решение находится посредством метода неопределенных множителей Лагранжа. Алгоритм Густавсона-Кесселя, по сравнению с алгоритмом нечетких c-средних, обладает значительно большей вычислительной трудоемкостью.

В оглавление книги \ К следующему разделу \ К предыдущему разделу