3.3.2. Описание алгоритмов

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

3.3.2.1. Алгоритм Ватады — Танаки — Асаи

[182] является эвристической процедурой и строит иерархию четких кластеров по уровням матрицы транзитивного отношения, вычисляемой на основе матрицы исходных данных, в свою очередь, представляющей собой некоторую нечеткую толерантность.

Основные понятия и определения

Пусть — исследуемая совокупность объектов, данные о которых представлены в виде матрицы «объект-объект» (1.3), элементы которой представляют собой значения нечеткой толерантности Т, определенной на множестве X, то есть Если элементы матрицы нечеткого отношения Т упорядочить в возрастающем порядке, так что

где располагается в позиции в последовательности (3.97), то для обозначения номера этой позиции будет использоваться обозначение так что

Задача заключается в построении такого нечеткого отношения Т на множестве, которое минимизирует функционал

при выполнении условия (max-min)-транзитивности (2.26). Задача минимизации критерия 200 (3.98) представляет собой задачу нелинейного программирования, так что при указанном ограничении вполне естественно для минимизации использовать эвристический метод. С этой целью авторы метода вводят понятия max-транзитивной матрицы Г, которая представляет собой матрицу (max-min)-транзитивного замыкания нечеткого отношения Т и min-транзитивной матрицы Т, которая представляет собой матрицу, двойственную матрице Т. Иными словами, матрица Т строится рекурсивно путем увеличения значения элементов что авторы метода определяют следующим образом:

а матрица Г строится рекурсивно путем уменьшения значения элементов и/или так что

В качестве примера [182, с. 152-153] рассмотрим матрицу нечеткого отношения F и соответствующих ей матриц F и

Таким образом, искомая матрица Г, минимизирующая отыскивается рекурсивно путем увеличения и/или уменьшения значений элементов исходной матрицы Т, так что

    (3.101)

Процедура построения матрицы Т предусматривает следующие основные этапы:

1. Вычисляются -уровни, , нечеткой толерантности Т и для каждого строится матрица Т в соответствии с формулой (2.38);

2. Вводятся три индекса, относящиеся к измерению «совершенствования» транзитивности, и выбирается одна из двух стратегий декомпозиции;

3. Для каждого в [0,1] вычисляется транзитивная матрица Т, соответствующая трем введенным индексам;

4. Строится транзитивная матрица Т по всем -уровням Т в соответствии с формулой (2.39).

a-уровень нечеткой толерантности Т представляет собой ни что иное, как уровень декомпозиции отношения Т, так что в соответствии с теоремой декомпозиции отношения Та для образуют иерархию Н; аналогично соответствующие иерархии образуют отношения . Таким образом, стратификационный индекс иерархии Н транзитивных матриц Т для любого в последовательности может быть определен как так что упомянутые выше две стратегии декомпозиции могут быть определены следующим образом:

1) строятся для для такие, что матрица является транзитивной, после чего отыскивается Т для такая, что матрица также транзитивна, и так далее вплоть до данная стратегия именуется восходящим анализом;

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

Процедура, реализующая восходящую стратегию, представляет собой дивизимную кластер-процедуру, тогда как процедура, реализующая нисходящую стратегию, представляет собой агломеративную

кластер-процедуру. Описанная ниже версия алгоритма реализует восходящую стратегию.

Очевидно, что для выполняется

    (3.102)

Матрицы представляют собой -уровни матриц соответственно, так что выполняется

    (3.103)

откуда можно выдвинуть следующее предложение: при имеет место

    (3.104)

Пусть для рассмотренной выше матрицы F при некотором матрицы определяются следующим образом [182,

тогда, учитывая, что

так что, в соответствии с (3.104), имеет место неравенство откуда

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

a-уровень нечеткой толерантности Т представляет собой матрицу, для элементов которой справедливо Нетранзитивность также может быть выражена условием

    (3.106)

Для приведения матрицы к транзитивной матрице авторами предлагаются следующие преобразования:

1) изменение 1: в левой части выражения (3.106) элемент изменяется с 0 на 1;

2) изменение 2: в правой части выражения (3.106) изменяется с 1 на 0 элемент и/или элемент

Для получения -транзитивной матрицы Т используется изменение 1, а для получения -транзитивной матрицы Та используется изменение 2; в дальнейшем будет показано, что для получения матрицы Т используются оба изменения.

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

Индекс 1 уровня декомпозиции имеет обозначение и определяется выражением

показывает те элементы, к которым необходимо применить изменение 1: в соответствии с изменением 1 должны быть преобразованы те элементы матрицы для которых значение является максимальным.

Например, если при некотором для рассмотренной выше матрицы F матрица будет иметь вид

то матрица для будет выглядеть следующим образом:

Индекс 2 уровня декомпозиции имеет обозначение и определяется выражением

где М в знаменателе каждого из слагаемых представляет собой некоторое достаточно большое число. Так же, как показывает эффективность применения изменения 1 к элементам матрицы Та, индекс показывает эффективность применения к ним изменения 2.

Индекс 3 уровня декомпозиции имеет обозначение и определяется в зависимости от стратегии декомпозиции.

Если декомпозиция производится в соответствии со стратегией восходящего анализа, то определяется в соответствии с формулой

Если же декомпозиция производится в соответствии со стратегией нисходящего анализа, то определяется в соответствии с формулой

В случае так что должно выполняться равенство . В свою очередь, в случае, когда значение индекса 3, соответствующее элементам, обозначенным символом в матрице в рассмотренном выше примере, принимает значение

В случае, когда то а когда то Таким образом, изменение 1 должно быть применено к элементу матрицы минимизируя выражение при условии выполнения тогда как изменение 2 должно быть применено к элементу матрицы минимизируя выражение при условии, что выполняется неравенство

Например, для рассмотренных выше матрицы F и матриц определенных для F при некотором матрица будет выглядеть следующим образом:

Индексы обозначают различные аспекты нетранзитивности элементов, и взаимосвязь индексов выражается соотношением

где Справедливость соотношения (3.111) следует из преобразования

а также

Таким образом, выражение (3.111) указывает, что сумма значений каждое из которых показывает эффективность применения изменения 1, эквивалентна сумме значений каждое из которых, в свою очередь, показывает эффективность применения изменения 2.

Параметры алгоритма:

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

Схема алгоритма:

1. Для исходной матрицы строится матрица (max-min)-транзитивного замыкания Г и min-транзитивная матрица Т в соответствии с формулами (3.99) и (3.100) соответственно;

2. Вычисляются значения а-уровней, и производится их нумерация, так что выбирается порог а такой, что и полагается

3. Для уровня производится декомпозиция нечетких матриц для получения матриц соответственно;

4. Для матриц строится в соответствии с формулой (3.109);

5. Для матрицы Т строятся в соответствии с формулами (3.107) и (3.108);

6. Выбирается элемент которому в матрицах соответствует наибольшее положительное число;

7. Если на предыдущем шаге выбран по крайней мере один элемент то осуществляется переход на шаг 8, в противном случае осуществляется переход на шаг 10;

8. К элементам, выбранным на шаге 6, применяются изменение 1 и/или изменение 2;

9. Если матрица Т транзитивна, осуществляется переход на шаг 15, в противном случае осуществляется переход на шаг 5;

10. Если для превышено предельное значение в последовательности, определяемой формулой (3.97), осуществляется переход на шаг 12, в противном случае осуществляется переход на шаг 11;

11. Полагается где N обозначает откорректированное предельное значение индекса так что и осуществляется переход на шаг 6;

12. Если число итераций для реконструкции превышает заданное, осуществляется переход на шаг 14, в противном случае осуществляется переход на шаг 13;

13. Производится реконструкция так что измененные элементы просматриваются опять, полагается число итераций увеличивается на 1 и осуществляется переход на шаг 11;

14. Полагается и осуществляется переход на шаг 16;

15. Полагается

16. Составляется матрица Г в соответствии с правилом

17. Если осуществляется переход на шаг 19, в противном случае осуществляется переход на шаг 18;

18. Полагается и осуществляется переход на шаг 3;

19. Алгоритм прекращает работу.

В работе [182] приводится пример применения процедуры к анализу совокупности пятнадцати различных прохладительных напитков. В сравнении с иерархической версией процедуры Тамуры — Хигути — Танаки алгоритм показал гораздо лучшие результаты.