Нечеткое разбиение на заданное число кластеров
Нечеткие методы кластеризации позволяют одному и тому же вектору принадлежать одновременно нескольким (или даже всем) кластерам, но с различной степенью принадлежности. Нечеткая кластеризация может быть более естественной, например, для объектов, расположенных на границе кластеров.
Простой алгоритм нечеткой кластеризации — нечеткий алгоритм ^-средних. Нечеткие кластеры описываются матрицей нечеткого разбиения R = е[0,= у = 1,К,
строки которой содержат индикаторные переменные (принадлежности) векторов х; = = кластерам с центрами ц = j - ,К . Единственным отли
чием матрицы принадлежностей нечеткого разбиения от четкого в том, они принимают значения из интервала [0,1], а не из двухэлементного множества {0,1}. В базовом алгоритме нечетких ^-средних расстояние Dtj,i = 1,N,j = ЕЛГ между вектором x,,z = l,A и центром кластера j = 1, К определяется Евклидовой нормой. В результате после серии итераций форма всех кластеров оказывается одинаковой. Алгоритм кластеризации способен навязывать кластерам несвойственную им форму. Для устранения этого недостатка предложено несколько алгоритмов. Ниже рассматривается алгоритм Густафсона-Кесселя.
По отношению к алгоритму ^-средних главное усовершенствование состоит во введении в формулу для расстояний между векторами и центрами кластеров масштабирующей матрицы А;, j = ,К. Собственная матрица A., j = ,К для кластера является симметричной положительно определенной матрицей (т.е. все собственные значения матрицы действительные и положительные). В этом алгоритме при кластеризации оптимизируются не только координаты центров кластеров ji;, j = i,K и матрица нечеткого разбиения U , но также и матрицы А , j = ,К для кластеров. Это позволяет после серии итераций выделять кластера различной геометрической формы (например, эллипсоидальной). В комбинации с алгоритмом нечетких ^-средних он часто используется для инициализации другие нечетких алгоритмов кластеризации.
Алгоритм нечетких к- Алгоритм Густафсона-Кессел я средних
Шаг 1. Устанавливаются параметры алгоритма: К - количество кластеров; т - экспоненциальный вес; ? — параметр остановки алгоритма
Шаг 2. Случайным образом генерируется матрица нечеткого разбиения R .
Л' т ! N т
Шаг 3. Вычисляются центры кластеров: = У (/;,) х, /
i=i / i=i
Шаг 4. Вычисляются рассто- Шаг 4. Вычисляется матрица ковариации для у-ого яния между векторами и центрами кластера: кластеров
,< = Гх,7 = ГТ
х/-Му
/я
Шаг 5. Вычисляются расстояния между векторами и центрами кластеров:
Du = (Х'-M,)(detA7)' ' А/|(х,.-ц.)Т,г = 1Л,./ = 1Ж
Шаг 5. Вычисляются элементы матрицы нечеткого разбиения: если
/ К -1/(«>-1)
к *=1
если
Шаг 6. Проверяется условие по норме Фробениса
||R-R’|| <е, где R - матрица нечеткого разбиения на кластеры на предыдущей итерации алгоритма. Если условие выполняется, то закончить итерации, иначе перейти на шаг 3.
Шаг 6. Вычисляются элементы матрицы нечеткого разбиения: если Dit > О
( К Х-'Л'"-1)
г.= D2tD,-2
k=l )
если Dtj = О
Шаг 7. Проверяется условие по норме Фробениса llR_R1L < ?, где R — матрица нечеткого разбиения на кластеры на предыдущей итерации алгоритма. Если условие выполняется, то закончить итерации, иначе перейти на шаг 3.
