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

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

12.2 Кластеризация без задания количества кластеров

В начале раздела излагаются основные идеи метода горной кластеризации, который не требует задания количества кластеров. Метод предложен Р. Ягером и Д. Филевым в 1993 г. Кластеризация по горному методу не является нечеткой, однако, ее часто используют при синтезе нечетких правил из данных. Применение горной кластеризации при проектировании нечетких баз знаний описывается в конце параграфа. Изложение материала базируется на книге [6].

12.2.1 Основные идеи метода горной кластеризации

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

На первом шаге необходимо сформировать потенциальные центры кластеров. Для алгоритма горной кластеризации число потенциальных центров кластеров (Q) должно быть конечным. Ими могут быть объекты кластеризации (строчки матрицы ), тогда . Второй способ выбора потенциальных центров кластеров состоит в дискретизации пространство входных признаков. Для этого диапазоны изменения входных признаков разбивают на несколько интервалов. Проводя через точки разбиения прямые, параллельные координатным осям, получаем "решеточный" гиперкуб. Узлы этой решетки и будут соответствовать центрам потенциальных кластеров. Обозначим через   - количество значений, которые могут принимать центры кластеров по й координате (). Тогда количество возможных кластеров будет равно: .

На втором шаге алгоритма рассчитывается потенциал центров кластеров по следующей формуле:

, ,

где   - потенциальный центр h-го кластера, ;

  - положительная константа

  - расстояние между потенциальным центром кластера () и объектом кластеризации (). В евклидовом пространстве это расстояние рассчитывается по формуле:

.

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

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

,

где   - потенциал на 1-й итерации;

  - потенциал на 2-й итерации;

  - центр первого найденного кластера: ;

  - положительная константа.

Центр второго кластера определяется по максимальному значению обновленного потенциала:

.

Затем снова пересчитывается значение потенциалов:

.

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

12.2.2 Синтез нечеткой базы знаний на основе горной кластеризации

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

Центру кластера () ставится в соответствие одно нечеткое правило:

,

в котором нечеткие термы интерпретируются так:   - и   - . Функции принадлежностей этих нечетких термов задаются гауссовской кривой:

, , ,

где   - параметр алгоритма горной кластеризации.

Литература

1. 1. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир. - 1976. - 511c.

2. 2. Bezdek J.C. Pattern Recognition with Fuzzy Objective Function. New York: Plenum Press. - 1981.

3. 3. Babuska R. Fuzzy Modeling for Control. Boston: Kluwer Academic Publishers. - 1998.

4. 4. Xei X.L., Beni G.A. Validity Measure for Fuzzy Clustering // IEEE Trans. on Pattern Anal. and Machine Intell. 3 (8). - 1991. - P. 841 - 846.

5. 5. Gustafson D.E., Kessel W.C. Fuzzy Clustering with a Fuzzy Covariance Matrix. Proc. of IEEE CDC, San-Diego, USA. - P.761 - 766.

6. 6. Yager R., Filev D. Essentials of Fuzzy Modeling and Control. USA: John Wiley & Sons. - 1984. - 387p.

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