Системи та методи прийняття рішень

Размещено на http://www.allbest.ru/

Міністерство освіти і науки, молоді та спорту України

Сумський державний університет

Кафедра комп'ютерних наук

ОБОВ'ЯЗКОВЕ ДОМАШНЄ ЗАВДАННЯ

з дисципліни ,, Системи та методи прийняття рішень ”

Виконав студент гр. ІН-93

Киричок Б.В.

Перевірив викладач

Мартиненко С. С.

Суми 2012

Зміст

• 1. Постановка задачі
• 2. Короткі положення методу функціонально-статистичних випробувань
• 3. Опис алгоритму навчання
• 4. Критерій оптимізації
• 5. Алгоритми екзамену
• 6. Результат моделювання
• Список літератури

1. Постановка задачі

Розробити та програмно реалізувати базовий алгоритм навчання СПР для розпізнавання двох класів (М=2) і алгоритм екзамену для функціонування навчання за методом функціонально-статистичних випробувань (МФСВ). Задано такі параметри:

· Кількість ознак розпізнавання 18.

· Кількість реалізацій образу одного класу 30.

· Інформаційний критерій оптимізації за Шенноном.

· Для базового класу прийняти двійковий еталоний вектор-реалізацію <111111111111111111>

· Для класу сформувати двійковий еталонний вектор-реалізацію за умови, що міжцентрова кодова відстань =8

· Сформувати навчальну бінарну матрицю , взявши за рівень квантування дискрет полігону розподілу частот ознак розпізнавання рівним 0,5.

· Система контрольних допусків: верхній допуск - 40, нижній - 20.

2. Короткі положення методу функціонально-статистичних випробувань

МФСВ - непараметричний інформаційно-екстремальний метод аналізу та синтезу здатної навчатися ІСК, який ґрунтується на прямій оцінці інформаційної здатності системи за умов нечіткої компактності реалізацій образу, та обмеження навчальної вибірки, яка є прийнятною для задач контролю і управління. Метод призначено для розв'язання практичних задач контролю та управління слабо формалізованими системами і процесами шляхом автоматичної класифікації їх функціональних станів за умови невизначеності. програма алгоритм навчання

МФСВ окрім системних та специфічних принципів ґрунтується також на 2-х дистанційних принципах:

1. максимально-дистанційному, який вимагає максимальної міжцентрової відстані між класами;

2. мінімально-дистанційному, вимагає мінімальної середньої відстані реалізацій від центру свого класу.

Класом розпізнавання (образом) називається відбиття властивостей m-го функціонального стану СР і відношень між елементами системи. Клас розпізнавання топологічна категорія, яка задається в просторі ОР областю Б.

Детерміновано-статистичний підхід до моделювання систем вимагає завдання систем нормованих (експлуатаційних) і контрольних допусків на ОР. Нехай базовий клас, який характеризує максимальну функціональну ефективність, тобто є найбільш бажаним для розробника інформаційного забезпечення системи.

Нормованим називається поле допусків , в якому значення і-ї ОР знаходиться з імовірністю р_і=1 або p_i=0, за умови, що функціональний стан відноситься до класу .

Контрольним називається поле допусків , в якому значення і-ї ОР знаходиться з імовірністю 0<рі<1 за умови, що функціональний стан відноситься до класу .

В МФСВ система контрольних допусків (СКД) вводиться з метою рандомізації процесу прийняття рішень, оскільки для повного дослідження об'єкту контролю та управління (ОКУ) необхідно використовувати як детерміновані, так і статистичні характеристики. Зрозуміло, що і базова (відносно класу ) СКД є сталою для всієї абетки класів розпізнавання.

Реалізацією образу називається випадковий структурований бінарний вектор

, ,

де і-та координата вектора, яка приймає одиничне значення, якщо значення і-ї ОР знаходиться в полі допусків , і нульове значення, якщо не знаходиться; мінімальна кількість випробувань, яка забезпечує репрезентативність реалізацій образу.

При обґрунтуванні гіпотези компактності (чіткої, або нечіткої) реалізацій образу за геометричний центр класу приймається вершина бінарного еталонного вектору х_m.

Еталонний вектор (ЕВ) x_m це математичне сподівання реалізацій класу . Він подається у вигляді детермінованого структурованого бінарного вектора

x_m = <x_m,1 , …, x_m,і , …, x_m,N >, m = ,

де х_m,і і-та координата вектора, яка приймає одиничне значення, якщо значення і-ї ОР

знаходиться в нормованому полі допусків , і нульове значення, якщо не знаходиться.

Основною задачею етапу навчання за МФСВ є розбиття простору ОР за поданою навчальною матрицею на області класів розпізнавання деяким оптимальним в інформаційному сенсі способом, який забезпечує на етапі екзамену прийняття рішень з достовірністю, наближеною до максимальної асимптотичної достовірності.

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

Як критерій оптимізації процесу навчання системи прийняттю рішень в рамках МФСВ застосовується статистичний інформаційний КФЕ, який є природною мірою різноманітності (або схожості) класів розпізнавання і одночасно функціоналом асимптотичних точнісних характеристик СПР. При цьому важливо, щоб параметри навчання були оптимальними в інформаційному розумінні, тобто забезпечували максимальну функціональну ефективність СПР, яка визначається достовірністю прийняття рішень на екзамені.

Достовірність класифікатора залежить від геометричних параметрів роздільних гіперповерхонь класів розпізнавання.

Для загального випадку, коли класи розпізнавання перетинаються розглянемо відносний коефіцієнт нечіткої компактності реалізації образу для класу .

Процес навчання полягає в мінімізації цього виразу.

В МФСВ, який ґрунтується на допущенні гіпотези компактності (чіткої або нечіткої) реалізацій образу, як наближення точної роздільної гіперповерхні для класу розглядається гіперсфера, центром якої є ЕВ хm, а радіусом кодова відстань, яка у просторі Хеммінга визначається як



,

де і-та координата вектора ; i-тa координата деякого вектора-реалізації m, вершина якого знаходиться на роздільні гіперповерхні класу ; операція складання за модулем два.

Оптимальною кодовою відстанню (радіусом) між вектором і контейнером називається екстремальне значення , яке визначає максимум інформаційного КФЕ

E_m,

де {d} - послідовність збільшень радіуса контейнера .

Побудова оптимальної в інформаційному сенсі РГП у вигляді гіперсфери за МФСВ зводиться до оптимізації радіуса роздільної гіперсфери , яка відбувається за ітераційним алгоритмом

де змінна числа збільшень радіуса РГП; ; крок збільшення.

Процедура закінчується при знаходженні екстремального значення критерію



де = множина радіусів концентрованих гіперсфер, центр яких визначається вершиною еталонного вектора еталонний вектор найближчого (до ) класу .

Математична модель процесу навчання.

Розглянемо математичну модель ІСК, яка реалізує класичну задачу розпізнавання образів за МФСВ. Математична модель повинна включати як обов'язкову складову частину вхідний математичний опис, який подамо на рівні системного аналізу у вигляді теоретико-множинної структури

,

де G простір вхідних сигналів (факторів); T множина моментів часу зняття інформації; Щ простір ознак розпізнавання; Z - простір можливих станів; Y множина сигналів після первинної обробки інформації; П:GTЩZ оператор переходів, що відбиває механізм зміни станів під дією внутрішніх і зовнішніх збурень; Ф:GTЩZY оператор оброблення зображення (формування вибіркової множини Y на вході СПР), який є реакцією на внутрішні і зовнішні збурення. Як універсум випробувань W розглядається декартовий добуток: W=GTЩZ.

Для чіткого детермінованого розбиття потужності M, оператор побудови розбиття з задає відображення з:Y. Апріорно оператором будується покриття , яке визначає абетку класів розпізнавання і на якому на відміну від розбиття відношення еквівалентності відсутнє. Оператор ж переводить апостерірно розбиття в покриття і замикає комутативне кільце. Перевірка гіпотези про належність реалізацій образу здійснюється оператором класифікаціъ



де множина допустимих гіпотез (рішень). При цьому гіпотеза означає відмову від класифікації. У загальному випадку математичну модель будь-якої ІСК, яка розв'язує задачу класифікаційного аналізу , подамо у вигляді діаграми відображень відповідних множин:

У діаграмі (1) оператор зворотного зв'язку корегує геометричні параметри розбиття з метою поліпшення точнісних характеристик СПР. Саме спосіб реалізації оператора породжує різні методи та підходи до розв'язання проблеми адаптивного навчання ІСК.

При обґрунтуванні гіпотези нечіткої компактності має місце нечітке розбиття Щ.

Тоді замість оператора застосуємо оператор и нечіткої факторизації простору ознак: и:Y. Нехай оператор класифікації :I| l | визначає перевірку основної статистичної гіпотези про належність реалізацій {|j=} класу , де l кількість статистичних гіпотез. Принциповою відмінністю МФСВ від відомих методів автоматичної класифікації є ітераційна оптимізація процесу навчання за інформаційним КФЕ. Для обчислення КФЕ оператор г: I| l | | q | шляхом оцінки прийнятих гіпотез l формує множину



ТХ | q |

де q=l 2 - кількість ТХ, а оператор |q| E обчислює множину значень інформаційного КФЕ, який є функціоналом від ТХ. Ітераційний процес оптимізації геометричних параметрів розбиття реалізується оператором r:E шляхом пошуку максимуму КФЕ

,

де множина кроків навчання розпізнаванню реалізацій класу . Структурна діаграма процесу навчання за МФСВ для випадку нечіткого розбиття має вигляд

Таким чином, у діаграмі (2) контур операторів безпосередньо оптимізує геометричні параметри розбиття . Оператор U: EGTЩZ регламентує процес навчання. Оскільки в цьому контурі також застосовано процедуру обчислення інформаційного критерію, то він дозволяє розв'язувати задачу оптимізації параметрів плану навчання, які визначають, наприклад, обсяг і тривалість випробовувань, потужність словника ОР, черговість подання для навчання класів розпізнавання та інше.

3. Опис алгоритму навчання

Вхідною інформацією для навчання за базовим алгоритмом є дійсний, в загальному випадку, масив реалізацій образу ; система полів контрольних допусків і рівні селекції , які за умовчанням дорівнюють 0,5 для всіх класів розпізнавання.

Розглянемо етапи реалізації алгоритму:

1.Формування бінарної навчальної матриці , елементи якої дорівнюють

2.Формування масиву еталонних двійкових векторів , елементи якого визначаються за правилом:

де m рівень селекції координат вектору .

3. Розбиття множини еталонних векторів на пари найближчих сусідів:

=<x_mРазмещено на http://www.allbest.ru/

, x_l >

де x_l еталонний вектор сусіднього класу , за таким алгоритмом:

а) структурується множина еталонних векторів, починаючи з вектора x₁ базового класу , який характеризує найбільшу функціональну ефективність ІСК;

б) будується матриця кодових відстаней між еталонними векторами розмірності M M;

в) для кожної строки матриці кодових відстаней знаходиться мінімальний елемент, який належить стовпчику вектора найближчого до вектора, що визначає строку. При наявності декількох однакових мінімальних елементів вибирається з них будь-який, оскільки вони є рівноправними;

г) формується структурована множина елементів попарного розбиття , яка задає план навчання.

4. Оптимізація кодової відстані dm відбувається за рекурентною процедурою. При цьому приймається .

5.Процедура закінчується при знаходженні максимуму КФЕ в робочій області його визначення:

де множина радіусів концентрованих гіперсфер, центр яких визначається вершиною .

Таким чином, базовий алгоритм навчання :

На рис.1 наведено структурну схему базового алгоритму навчання. Тут показано такі вхідні дані: {Y[J,I,K]} масив навчальних вибірок, J=1..NM змінна кількості випробувань, де NM мінімальний обсяг репрезентативної навчальної вибірки, I=1..N змінна кількості ознак розпізнавання, K=1..M змінна кількості класів розпізнавання; {NDK[I]}, {VDK[I]} масиви нижніх і верхніх контрольних допусків на ознаки відповідно. Результатом реалізації алгоритму є: {DOPT[K]} цілий масив оптимальних значень радіусів контейнерів класів розпізнавання у кодовій відстані Хеммінга; {EV[K]} масив еталонних двійкових векторів класів розпізнавання; {EM[K]} дійсний масив максимальних значень інформаційного КФЕ процесу навчання; {D1[K]}, {A[K]}, {B[K]}, {D2[K]} дійсні масиви оцінок екстремальних значень точнісних характеристик процесу навчання для відповідних класів розпізнавання: перша вірогідність, помилки першого та другого роду і друга вірогідність відповідно. Змінна D є робочою змінною кроків навчання, на яких послідовно збільшується значення радіуса контейнера. У структурній схемі алгоритму (рис. 1) блок 3 формує масив навчальних двійкових вибірок {X[J,I,K]} шляхом порівняння значень елементів масиву {Y[J,I,K]} з відповідними контрольними допусками за правилом (1) і формує масив еталонних двійкових векторів {EV[K]} шляхом статистичного усереднення стовпців масиву {X[J,I,K]} за правилом (2) при відповідному рівні селекції, який за умовчанням дорівнює .

Блок 4 здійснює розбиття множини еталонних векторів на пари “найближчих сусідів”. Блок 11 обчислює на кожному кроці навчання значення інформаційного КФЕ і оцінки точнісних характеристик процесу навчання. При невиконанні умови блоку порівняння 12 блок 13 оцінює належність поточного значення критерію робочій області визначення його функції і при позитивному рішенні блоку 13 це значення запам'ятовується блоком 14. При негативному рішенні блока порівняння 15, в якому величина дорівнює кодовій відстані між парою сусідніх еталонних векторів, блок 16 здійснює у робочій області пошук глобального максимуму КФЕ - EM[K] і визначає для нього екстремальне значення радіуса гіперсфери - DOPT[K]. Аналогічно будуються оптимальні контейнери для інших класів. Якщо параметри навчання {DOPT[K]} і {EV[K]} є вхідними даними для екзамену, то значення КФЕ та екстремальних оцінок точнісних характеристик використовуються для аналізу ефективності процесу навчання. Таким чином, основною процедурою базового алгоритму навчання за МФСВ є обчислення на кожному кроці навчання статистичного інформаційного КФЕ і організація пошуку його глобального максимуму в робочій області визначення функції критерію.

4. Критерій оптимізації

Нехай в якості КФЕ виступає нормована інформаційна міра Шеннона :

- апріорна (безумовна) ентропія;

апостеріорна (умовна) ентропія, що характеризує залишкову невизначеність після прийняття рішення; безумовна ймовірність прийняття гіпотези ; апостеріорна ймовірність прийняття рішення за умови, що прийнята гіпотеза ; М кількість гіпотез.

Для двохальтернативної системи оцінок (М=2) і рівноймовірних гіпотез, що характеризує найбільш важкий у статистичному сенсі випадок прийняття рішень, після заміни в (4) апостеріорних імовірностей на апріорні за формулою Байєса отримаємо



(5)

де точнісні характеристики (ТХ): помилки першого та другого роду, перша та друга достовірності відповідно. Отже, критерій (5) є нелінійним функціоналом від ТХ процесу навчання. Крім того, він є неоднозначним, що потребує визначення в процесі навчання робочої області для його значень. Оскільки навчальна вибірка (НВ) є обмеженою за обсягом, то надалі замість ТХ будемо оперувати їх оцінками (емпіричними частотами):

(6)

де кількість подій, які означають належність та неналежність реалізацій класу відповідно, якщо ; кількість подій, які означають належність і неналежність реалізацій класу , якщо вони дійсно не належать класу ; n обсяг вибірки. Тоді після підстановки (6) в (5) отримаємо робочу формулу КФЕ за Шенноном:

5. Алгоритми екзамену

Алгоритми екзамену за МФСВ можуть мати різну структуру залежно від розподілу реалізацій образу, що розпізнаються. Обов'язковою умовою їх реалізації є забезпечення однакових структурованості і параметрів формування як для навчальної, так і для екзаменаційної матриць.

За наявності чіткого розбиття, яке було утворено на етапі навчання, алгоритм екзамену за МФСВ має такі вхідні дані:

- M кількість класів, які СПР навчена розпізнавати;

- масив еталонних двійкових векторів, які визначають центри відповідних оптимальних контейнерів класів розпізнавання, побудованих на етапі навчання;

- {} масив оптимальних радіусів побудованих на етапі навчання відповідних контейнерів;

- масив двійкових векторів-реалізацій образу, що розпізнається;

- оптимальна СКД на ознаки розпізнавання, яку визначено на етапі навчання.

За умовчанням приймається рівень селекції _m= 0,5.

Розглянемо кроки реалізації алгоритму екзамену при застосуванні гіпотези чіткої компактності реалізацій образу:

1. Формування лічильника класів розпізнавання: .

2. Формування лічильника числа реалізацій, що розпізнаються: .

3. Порівняння: якщо , то виконується крок 4, інакше крок 5.

4. Формування лічильника позитивних результатів порівняння.

5. Порівняння: якщо j ? n , то виконується крок 2, інакше - крок 6.

6. Порівняння: якщо k >j / 2, то виконується крок 8, інакше -крок 7.

7. Порівняння: якщо m ? M, то виконується крок 1, інакше - крок 8.

8. Визначення класу , до якого належить екзаменаційна матриця. Якщо в процесі екзамену порівняння на кроці 6 не дало позитивного результату, то може бути запущено алгоритм ФКА, з метою донавчання СПР, або алгоритм прогностичної класифікації, з метою підтвердження необхідності перенавчання СПР.

Для нечіткого розбиття алгоритм екзамену за МФСВ ґрунтується на аналізі значень функції належності, що обчислюється для кожної реалізації, що розпізнається. Розглянемо кроки реалізації алгоритму екзамену при нечіткому розбитті:

1. Формування лічильника класів розпізнавання.

2. Формування лічильника числа реалізацій, що розпізнаються: .

3. Обчислення кодової відстані .

4. Обчислення функції належності за виразом:

5. Порівняння: якщо j ? n , то виконується крок 2, інакще - крок 6.

6. Порівняння: якщо m ? M, то виконується крок 1, інакще - крок 7.

7. Визначення класу , до якого належить екзаменаційна реалізація, наприклад, за умови

де усереднене значення функцій належності для реалізацій класу , або видача повідомлення: «Клас не визначено», якщо ? с. Тут с порогове значення.



6. Результат моделювання

На рисунку 1 подано графічну інтерпретацію утворених бінарних еталонних веторів. Чорним кольором позначено одиничне значення компоненти еталонного вектора, а білим- нульове.

а) б)

Рис 1. Еталонні вектори класв розпізнавання:а) класу;б)класу

На наступному рисунку зображено відповідні бінарні навчальні матриці та матриці яскравості, побудовані відповідно до завдання.

Рис2. Бінарні навчальні матриці класів розпізнавання.

Рис3. Матриці яскравості класів розпізнавання.

Як параметр СКД дельта було обрано 58. Значення рівня квантування(селекції) ознак розпізнавання було обрано рівним 0,5.



Рис4. Графік системи контрольних допусків на ознаки розпізнавання

На наступному рисункові зображено проміжні результати навчання СППР- бінарні навчальні матриці та еталонні вектори.

Рис3. Бінарні навчальні матриці та еталонні вектори класів



Рис4. Графіки оптимізації контейнерів класів розпізавання

На графіках чорним кольором позначено робочу область визначення інформаційного критерію функціональної ефективності. Аналіз рисунку показує, що лише для одного класу вдалося побудувати вирішальне правило, а реалізації іншого класу поглинуті контейнером першого класу. Мале значенння інформаційного критерію є свідченням значного перетину класів розпізнавання, що пояснюється незначною міжцентровою відстанню , а відсутність робочої області у іншого класу - свідченням поглинання реалізацій поточного класу іншим класом.

Список літератури

1. Краснопоясовський А.С. Інформаційний синтез інтелектуальних систем керування: Підхід, що ґрунтується на методі функціонально-статистичних випробувань. - Суми: Видавництво СумДу, 2004. - 261с.

2. Краснопоясовський А.С. Класифікаційний аналіз даних: Навчальний посібник. Суми: Видавництво СумДУ, 2002. 159 с.

Размещено на Allbest.ru

...