Список функций Fuzzy Logic Toolbox

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

Синтаксис:

[V, M, obj_fcn] = fcm(X, c)

[V, M, obj_fcn] = fcm(X, c, options)

Описание:

На основе нечеткого c-means алгоритма выполняет кластеризацию данных. Этот алгоритм кластеризации предложил Джеймс Бэздэк (James Bezdek) в 1981 году.

Задача нечеткой кластеризации ставится следующим образом.

Дано:

•  – объекты, подлежащие кластеризации (n – количество объектов). Каждый объект представляет собой точку в p-мерном пространстве признаков ();
• c – количество кластеров ().

Необходимо каждому элементу множества X поставить в соответствие степени принадлежности с классам.

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

;
;
.

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

Любое разбиение множества на нечеткие подмножества () может быть полностью описано функцией принадлежности .

Обозначим через  - степень принадлежности объекта к подмножеству , т. е. , и через  - множество всех действительных матриц размером . Тогда нечетким c-разбиением (или матрицей степеней принадлежности) называется матрица при выполнении следующих условий:

1. , , ;
2. , ;
3. , .

В отличие от четкого, при нечетком c-разбиении любой объект одновременно принадлежит к различным кластерам, но с разной степенью. Условия (2) и (3) требуют только, чтобы сумма степеней принадлежности объекта ко всем кластерам была нормализована к 1, а также, чтобы количество кластеров, к которым принадлежит объект, не превышало .

Обозначим центры кластеров, т. е. точки в p-мерном пространстве, вокруг которых сконцентрированы соответствующие объекты, через , .

При использовании эвклидового расстояния задача нечеткой кластеризации состоит в нахождении такой матрицы степеней принадлежности и таких координат центров кластеров , которые обеспечивают минимум следующего критерия:

,

где  - центр i-го кластера, ;  - так называемый экспоненциальный вес ().

Значение экспоненциального веса устанавливается до начала кластеризации. Экспоненциальный вес влияет на матрицу степеней принадлежности. Чем больше , тем конечная матрица c-разбиения становится более “размазанной”, и при она примет вид , что является очень плохим решением, т. к. все объекты принадлежат ко всем кластерам с одной и той же степенью. Также, экспоненциальный вес позволяет при формировании координат центров кластеров усилить влияние объектов с большими значениями степеней принадлежности и уменьшить влияние объектов с малыми значениями степеней принадлежности. На сегодня не существует теоретически обоснованного правила выбора значения . Обычно устанавливают .

Аналитического решения задачи нахождения оптимальных координат центров кластеров и матрицы степеней принадлежности не существует, поэтому она решается численно. Один из итерационных алгоритмов решения этой задачи реализован в функции fcm.

Функция fcm может иметь три входных аргумента:

1. X – матрица, представляющая данные, подлежащие кластеризации. Каждая строка матрицы соответствует одному объекту (образу);
2. c – количество кластеров, которое должно быть получено в результате выполнения функции fcm. Количество кластеров должно быть больше 1 и меньше числа образов, заданных матрицей X;
3. options – необязательный аргумент, устанавливающий параметры алгоритма кластеризации:

   options(1) – значения экспоненциального веса (значение по умолчанию – 2.0);
   options(2) – максимальное количество итераций алгоритма кластеризации (значение по умолчанию – 100);
   options(3) – минимально допустимое значение улучшения целевой функции за одну итерацию алгоритма (значение по умолчанию – 0.00001);
   options(4) – вывод промежуточных результатов во время работы функции fcm (значение по умолчанию – 1).
   Для использования значений по умолчанию можно вести NaN в качестве значения соответствующей координаты вектора options.

Алгоритм кластеризации останавливается когда выполнено максимальное количество итераций или когда улучшение значения целевой функции за одну итерацию меньше указанного минимально допустимого значения.

Функция fcm имеет три выходных аргумента:

1. V – матрица координат центров кластеров, полученных в результате кластеризации. Каждая строка матрицы соответствует центру одного кластера;
2. M – матрица степеней принадлежности образов к кластерам. Каждая строка матрицы соответствует функции принадлежности одного кластера.
3. obj_fcn – вектор значений целевой функции на каждой итерации алгоритма кластеризации.

Примечание: при описании нечеткого c-means алгоритма использована книга Zimmermann H.-J. Fuzzy Set Theory - and Its Applications.3^rd ed.- Kluwer Academic Publishers, 1996.- 435p.

Пример.

Проводится кластеризация объектов, образующих фигуру типа “бабочка”. Результаты кластеризации приведены ниже на рисунке. Центры кластеров указаны маркером ‘+’. Размер маркера ‘o’ пропорционален степени принадлежности объекта кластеру. Расположенный в центре объект имеет одинаковые степени принадлежности к красному и к синему кластерам. Это обеспечивает симметричное разбиение объектов по кластерам, что невозможно при четкой кластеризации.

X=[1 1; 1 4; 1 7; 3 2; 3 4; 3 6; 5 4; 7 4; 9 4; 11 2; 11 4; 11 6; 13 1; 13 4; 13 7];
[V M opt]=fcm(X, 2)
subplot(2,1,1);
plot(X(:,1), X(:,2), 'ko', 'markersize', 6)
text='Исходные данные';
title(text)
xlim([0 14])
ylim([0 8])
subplot(2,1,2);
plot(V(1,1), V(1,2), 'r+', 'markersize', 10)
hold on
plot(V(2,1), V(2,2), 'b+', 'markersize', 10)
for i=1:15
plot(X(i,1), X(i,2)+.05, 'ro', 'markersize', M(1,i)*8+2);
plot(X(i,1), X(i,2)-.05, 'bo', 'markersize', M(2,i)*8+2);
end
xlim([0 14])
ylim([0 8])
text='Результаты кластеризации';
title(text)

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