22. Алгоритм МГУА для синтеза критериев

Шаг 1. На первом ряду селекции множество простейших критериев используется для классификации объектов обучающегося множества M На два указанных класса M1 и M2.

Шаг 2. Для каждого простейшего критерия множества K1 Подсчитывается показатель качества работы критерия, например, число правильно проклассифицированных объектов исходного обучающего множества M.

Шаг 3. По показателям качества отбирается наперед заданное число R Критериев которые правильно выполнили классификацию наибольшего числа объектов из обучающего множества M. Если хотя бы один из критериев правильно проклассифицировал все объекты множества M, то необходимый критерий найден, и работа алгоритма прекращается.

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

Шаг 5. Критерии множества пропускаются во второй ряд селекции (или второй этап работы алгоритма) и с их помощью синтезируется множество двучленных критериев вида:

;

;

..…………………..………………………………

; (2.3)

;

……………………….…………………………….

,

Где - положительные константы, удовлетворяющие условиям: - число сочетаний из по 2.

Шаг 6. Каждый критерий из множества Где используется для классификации объектов обучающегося множества M На два указанных класса M1 и M2. При этом для каждого критерия из множества подсчитывается показатель качества работы критерия.

Шаг 7. По показателям качества отбирается наперед заданное число R Лучших критериев которые правильно выполнили классификацию наибольшего числа объектов из обучающего множества M. Если один или несколько лучших критериев правильно выполнили классификацию всех объектов обучающего множества M, то цель синтеза критериев достигнута, и работа алгоритма по получению новых критериев прекращается.

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

Шаг 9. Критерии множества пропускаются в третий ряд селекции, где синтезируется множество критериев вида

;

;

…………………………………………….

,

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

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

Пример 2.1. Рассмотрим в качестве примера синтез критерия для функции реализации, содержащей 8 альтернатив и 7 состояний внешней среды, и приведенной ниже в табл. 2.1. В примере в качестве обучающего множества M Используется множество альтернатив Множество M Разделено на два подмножества: лучших альтернатив и худших альтернатив Требуется с помощью обучающего множества M Синтезировать критерий, позволяющий правильно классифицировать альтернативы, относящиеся к тем же классам, что и альтернативы обучающего множества.

Таблица 2.1

	3	7	8	9	10	11	12	3	12	8,57	6	2,00· ·106	10,28	7,00
	2	3	7	8	4	5	12	2	12	5,86	8	0,81· ·105	8,93	6,04
	8	6	5	10	6	7	8	5	10	7,14	7	0,81· ·105	8,57	5,04
	7	5	5	3	10	13	6	3	13	7,00	9	0,41· ·106	10,00	6,70
	4	10	11	12	9	8	7	4	12	8,71	5	2,66· ·106	10,35	7,33
	8	2	12	1	12	11	6	1	12	7,43	11	0,15· ·106	9,71	6,07
	9	3	11	11	10	9	10	3	11	9,00	7	2,94· ·106	10,00	6,97
	5	6	5	11	7	11	10	5	11	7,86	7	1,27· ·106	9,43	6,13
	-	-	-	-	-	-	-	4	2	4	2	4	8	8

Используем вначале для классификации альтернатив классические критерии: максиминный (1.3), азартного игрока (1.4), нейтральный (1.5), Сэвиджа (1.6) и критерий произведений (1.14).

Результаты применения критериев приведены в табл. 2.1. Анализ таблицы показывает, что максиминный критерий в число трех лучших альтернатив включает альтернативы имеющие более высокие показатели по критерию (). На четвертое место в подмножестве претендует сразу три альтернативы: все имеющие одинаковое значение критерия () и входящие в обучающее подмножество множества M. В связи с этим можно принять, что максиминный критерий разделил множество M на следующие два подмножества: В множество лучших альтернатив правильно включены альтернативы и ошибочно -

Показатель качества () работы любого критерия () определим следующим образом:

(2.4)

Где - соответственно число правильно и неправильно проклассифицированных альтернатив.

Чем больше величина Nj, тем лучше критерий Kj классифицирует альтернативы обучающего множества M. Отметим, что в качестве показателя качества работы критериев могут использоваться и каждый отдельный одночлен правой части выражения (2.4).

Максиминный критерий при классификации альтернатив сделал только две ошибки, поэтому по соотношению (2.4) имеем:

Аналогичным образом получены показатели качества работы и остальных критериев, эти показатели приведены в последней строке табл. 2.1. Анализ показателей качества работы критериев показывает, что ни один из примененных критериев не решает правильно задачу разделения множества альтернатив на два заданных подмножества. В связи с этим выполним синтез двухкомпонентных критериев. Формально с помощью соотношений (2.3) будут получены следующие критерии:

; (2.5)

; (2.6)

; (2.7)

; (2.8)

; (2.9)

; (2.10)

; (2.11)

; (2.12)

; (2.13)

(2.14)

Критерии (2.7), (2.10), (2.12), (2.14), в которые одним из компонент входит критерий Сэвиджа, использовать непосредственно затруднительно, так как в критерии Сэвиджа последняя операция min. Она выделяет минимальный элемент, а в остальных критериях последняя операция max, выделяющая максимальный элемент из чисел, характеризующих альтернативы. В этом случае ни минимальная, ни максимальная или взвешенная сумма числовых значений критериев не гарантирует правильного выбора альтернативы. В связи с этим необходимо каким-либо образом изменить в одном из компонентов последнюю операцию на противоположную, чтобы оба слагаемых составного критерия или минимизировались, или максимизировались. Естественно, что при этом упорядочивание альтернатив с помощью преобразованного критерия должно остаться таким же, как и у исходного. Преобразуем критерий Сэвиджа к виду:

(2.15)

Где - элементы матрицы сожалений.

Для рассматриваемого примера элементы матрицы сожалений приведены в табл. 2.2. В двух последних столбцах таблицы приведены и результаты работы критериев , которые подтверждают идентичность ранжирования ими альтернатив. Критерий Сэвиджа ранжирует альтернативы следующим образом: X5, X1, X3, X7, X8, X2, X4, X6. При этом альтернатива X5 является лучшей, а альтернатива X6 – худшей, альтернативы X3, X7, X8 – равноценны. Критерий упорядочивает альтернативы таким же образом. Для оценки альтернатив рассматриваемого примера не имеет смысла непосредственно использовать и критерии (2.8), (2.11), (2.13 – 2.14), содержащие в качестве компонент критерий произведений. Анализ данных табл. 2.1 показывает, что числовые значения, характеризующие альтернативы и получаемые с помощью критерия произведений, на 4 - 6 порядков больше числовых значений, получаемых с помощью других критериев. В связи с этим критерий произведений в соотношениях (2.8), (2.11), (2.13), (2.14) необходимо использовать с весовым коэффициентом

Таким образом, для синтеза двухкомпонентных критериев должны использоваться следующие выражения:

; (2.16)

; (2.17)

; (2.18)

; (2.19)

; (2.20)

; (2.21)

; (2.22)

; (2.23)

; (2.24)

(2.25)

Таблица 2.2

	6	3	4	3	2	2	0	6	5
	7	7	5	4	8	8	0	8	3
	1	4	7	2	6	6	4	7	4
	2	5	7	9	2	0	6	9	2
	5	0	1	0	3	5	5	5	6
	1	8	0	11	0	2	6	11	0
	0	7	1	1	2	4	2	7	4
	4	4	7	1	5	2	2	7	4
	-	-	-	-	-	-	-	2	2

В табл. 2.1 в двух последних столбцах приведены результаты успешной классификации множества альтернатив с помощью критерия (2.20) при и критерия (2.22) при .

< Предыдущая		Следующая >