Оптимум хаус отзывы

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

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

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

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

,
,

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

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

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

.

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

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

,

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

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

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

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

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

.

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

.

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

2.4. Синтез нечетких правил по результатам нечеткой кластеризации

Нечеткие правила можно синтезировать по результатам
нечеткой кластеризации. Пусть объекты кластеризации имеют два признака ().Тогда результаты нечеткого разбиения можно представить
трехмерным графиком: для каждого объекта отложить по осям абсцисс и ординат
значения признаков, а по оси аппликат – степень принадлежности объекта
нечеткому кластеру. Количество таких графиков будет равно числу кластеров (n).

Пример А. Данные представлены
следующей таблицей:

Графическое изображение
этих данных представляет собой “бабочку” ‑ хорошо
известный в теории распознавания образов пример кластеризации. Установим такие
параметры алгоритма нечетких c-средних: c=2, m=2 и . После 8-ми итераций получаем следующее нечеткое разбиение:

Значение критерия (2.5)
для этого нечеткого разбиения равно 82.94. Трехмерные изображения нечетких
кластеров приведены на рис. 2.3.

Рисунок 2.3 –
Нечеткие кластера из примера А

Функции принадлежности нечетких кластеров
(рис. 2.3) напоминают нечеткие отношения. Следовательно, каждому кластеру
можно поставить в соответствие одно нечеткое правило. По результатам нечеткой
кластеризации можно синтезировать нечеткие правила различных баз знаний:
синглтоной, Мамдани и Сугено. Функции принадлежности термов в посылках правила
получаются проецированием степеней принадлежности соответствующего кластера
(строчки матрицы нечеткого разбиения ) на входные переменные. Затем полученные множества степеней
принадлежностей аппроксимируют подходящими параметрическими функциями
принадлежности.

В качестве заключения правила синглтоной базы
знаний выбирают координату центра кластера. Заключения правил базы знаний
Мамдани находят также как и функции принадлежности термов входных переменных.
Заключения правил базы знаний Сугено находят по методу наименьших квадратов.
При кластеризации с использованием нормы Махалонобиса в качестве заключений
правил типа Сугено могут быть выбраны уравнения длинных осей гиперэллипсоидов.

Пример Б. Данные для кластеризации
изображены на рис. 2.4. На этом рисунке также показаны центры двух
нечетких кластеров и изолинии для следующих значений функций принадлежности
нечетким кластерам: 0.95, 0.9, 0.85, 0.8, 075, 0.7 и 0.65. Функции
принадлежности нечетких кластеров также изображены двумя трехмерными
поверхностями. Они интерпретируются следующими нечеткими правилами:

Если x=низкий, то
y=низкий,

Если x= высокий, то
y=высокий,

с функциями принадлежности
термов, показанными на рис. 2.5. Функции принадлежности получены
проецированием поверхностей с рис. Б на переменные x и y. Маркеры на
графиках функций принадлежности соответствует одному объекту кластеризации.

Рисунок 2.4 – К
примеру Б: экстракция нечетких правил через нечеткую кластеризацию

Рисунок 2.5 – К
примеру Б: функции принадлежности

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

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

Список источников

• ami.nstu.ru