Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
3.2.2.7. Другие алгоритмы оптимизационного подходаподробно рассматриваются в работах [46], [64], [85], [101], [108], [167], [185] и, в основном, представляют собой различные версии рассмотренных выше нечетких оптимизационных кластер-процедур. Дж. Беждеком [59] рассматриваются различные модификации критерия Q” (Р) и соответствующие им алгоритмы нахождения оптимума, такие, к примеру, как FCV алгоритм (fuzzy с-varieties). Алгоритм, предложенный Д. Е. Густафсоном и В. С. Кесселем [92] и минимизирующий критерий Некоторые подходы используют методы нечеткой математики для усовершенствования статистических процедур; наиболее интересным с этой точки зрения представляется метод, предложенный Я. В. Овсиньским и С. Задрожным в работе [133], совершенствующий процедуру, отыскивающую субоптимум целевой функции [132], на основе шести предложенных правил. Ниже рассмотрены некоторые малоизвестные процедуры, представляющие интерес с теоретической точки зрения, а также ряд модификаций рассмотренных выше методов. Алгоритм Распини, минимизирующий один из функционалов рассмотрение оказывается нелишним с теоретической точки зрения. Однако перед изложением общей схемы процедуры следует привести формулировки двух теорем, используемых в ней. Как и функционал
Теорема 3.1. Если для некоторого разбиения
выполняется Теорема 3.2. Если при условиях предыдущей теоремы для некоторого Параметры алгоритма: с — число нечетких кластеров в искомом разбиении Р; Схема алгоритма: 1. Для некоторого разбиения 2. Из множества значений частных производных 3. Если выполняется равенство 4. Если для некоторой j-й точки, условием теоремы 3.2; 5. Если для всех Теоремы 3.1 и 3.2 показывают, что предложенный градиентный метод сходится при указанных ограничениях. Важность рассмотренного метода заключается в том, что минимизация функционала достигается изменением значений принадлежности В работе Алгоритм расстановки меток [72, с. 173-174] применяется для присвоения названий классов центрам нечетких кластеров, что в значительной степени облегчает интерпретацию результатов. Обычно хотя бы для части объектов исследуемой совокупности точно известно, какой объект принадлежит какому классу. Данная информация может послужить основой процесса присвоения названий классов центрам нечетких кластеров, именуемым расстановкой меток (labeling). В случае, когда априорная информация о принадлежности некоторых объектов классам отсутствует, то она может быть получена уже после процедуры классификации объектов, в данном случае методом нечетких с-средних. Пусть в результате работы алгоритма Беждека — Данна построено нечеткое разбиение на с классов и результат представлен в виде соответствующей матрицы Параметры алгоритма: с — число нечетких кластеров в разбиении Р; у — показатель нечеткости классификации, Схема алгоритма: 1. Всем элементам матрицы меток 2. Вычисляется значение функции принадлежности
3. Полагается 4. Если 5. Определяется метка 6. Производится присвоение меток Следует указать, что процедура расстановки меток терпит неудачу, если метка присвоена двум или более классам, что означает, что центр кластера не найден для всех меток классов. Иногда может случиться, что максимальное значение матрицы меток на шаге 5 однозначно не устанавливается. В обеих указанных ситуациях алгоритм останавливает работу и выдает сообщение об ошибке. Модификация Либерта — Рубенса MND2 алгоритма [119, с. 418], в которой полагается, что Параметры алгоритма: с — число нечетких кластеров в искомом разбиении Р; Схема алгоритма: 1. Выбирается начальное разбиение 2. Полагается 3. Полагается
что приводит К
4. Полагается 5. Если 6. В зависимости от результата сравнения полученного разбиения с предыдущим разбиением осуществляется переход на шаг 2 или останов алгоритма. М. П. Уиндхем отмечал, что «алгоритм Рубенса основан на очень простом оптимизационном критерии, но первоначально сформулированная численная процедура неустойчива. Модификации, описанные Либертом и Рубенсом, приводят к более стабильной технике, но если типы явно неотличимы друг от друга, полезные результаты могут не быть получены» [186, с. 159]. Модификация Даве — Сена FCM алгоритма (R-FCM algorithm) [73, с. 716] минимизирует функционал неизменной, тогда как значения принадлежностей вычисляются по формуле (3.70). Модификация Даве — Сена MND2 алгоритма (R-MND2 algorithm) [73, с. 716] минимизирует функционал
Модификация Даве — Сеиа FRC алгоритма (R-FRC algorithm) [73, с. 716] является робастной версией FRC алгоритма и минимизирует функционал В работе [73] представлена также робастная версия функционала, предложенного Р. Дж. Гэтевеем, Дж. В. Девенпортом и Дж. Беждеком, так что минимизирующий робастную версию функционала Р. Дж. Гэтевея, Дж. В. Девенпорта и Дж. Беждека алгоритм получил название R-RFCM алгоритма. Кроме того, Р. Н. Даве и С. Сеном рассматривается версия FRC алгоритма, отыскивающая оптимальное разбиение при условии, что для расстояния Модификация Кеймака — Сетнеса GK алгоритма (E-GK algorithm) [109, с. 708-709] минимизирует критерий Параметры алгоритма: с — число нечетких кластеров в разбиении;
Схема алгоритма: 1. Выбирается начальное число кластеров 2. Полагается 3. Пусть построено некоторое 4. На основании ковариационной матрицы 5. Вычисляются расстояния до объемных прототипов кластеров:
6. Производится пересчет значений принадлежности в матрице разбиения
7. Выбирается пара наиболее близких кластеров:
8. Производится объединение наиболее близких кластеров в соответствии с правилом: при - 9. Производится сравнение Модификация Кеймака — Сетнееа FCM алгоритма (E-FCM algorithm) [109, с. 708-709] минимизирует критерий
Результаты вычислительных экспериментов, представленные У. Кеймаком и М. Сетнесом [109, с. 709], демонстрируют высокую эффективность расширенных версий нечетких кластер-процедур оптимизационного направления по сравнению с обычными нечеткими оптимизационными методами кластер-анализа. При проведении экспериментов У. Кеймаком и М, Сетнесом полагалось В заключение рассмотрения оптимизационных алгоритмов нечеткого подхода к решению задачи кластер-анализа следует отметить общую особенность всех рассмотренных кластер-процедур [109, с. 705]: результаты работы оптимизационных алгоритмов зависят от начального разбиения, которое инициализируется, как правило, случайным образом, так что при неудовлетворительном начальном разбиении могут быть получены некорректные результаты. В связи с этим У. Кеймак и М. Сетнес отмечают, что для получения корректных результатов целесообразно проведение ряда экспериментов с различными начальными разбиениями [109, с. 705].
|
1 |
Оглавление
|