МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” ІНСТИТУТ КОМП’ЮТЕРНИХ НАУК ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ Кафедра “Системи автоматизованого проектування”
ЗВІТ до лабораторної роботи №6 на тему «ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. ЗАДАЧА ВИЗНАЧЕННЯ КОЕФІЦІЄНТІВ ЛРФ ДЛЯ КІЛЬКОХ МНОЖИН ОБРАЗІВ» з курсу «Системи штучного інтелекту» Львів-2008 1.Мета роботи Вивчити принципи алгоритмів побудови лінійних рішаючих функцій для кількох класів. Написати програму реалізації алгоритму з графічним інтерфейсом користувача. Короткі теоретичні відомості 2.1. Машина перцептрона. Перцептронний підхід до розпізнавання образів Структура машини перцептрона була запропонована у 1957 році як модель машини, здатної до навчання. Рис. 1. Структура машини перцептрона Ця машина складається з наступних частин: Сенсори (давачі), які сприймають зовнішню інформацію Асоціативний шар. Кожен давач з'єднаний з кожним блоком асоціативного шару. Виходом цього шару є ознаки
. Блок вагових коефіціентів. За допомогою цього блоку ознаки зважуються (
). Загальний суматор - в ньому отримується значення реакції
. Блок рішення - сюди поступає значення реакції із загального суматора. По значенню
визначається налажність образу до того чи іншого класу. Якщо поступає образ класу
(
), а на виході отримується
тоді коректуються вагові коефіціенти. Значення вектора
вважається знайденим правильно, якщо для будь-яких образів з класів
і
класифікація відбувається правильно. Така машина є типовою архітектурою машини із здатністю до самонавчання. Алгоритм роботи машини перцептрона грунтується на ідеї "заохочення-покарання". Робота починається з де-якого початкового наближення
. Нехай ми знаходимось на k-ому кроці і нехай ми перевіряємо якийсь k-ий образ з множини вибірки
. Припустимо, що ми розглядаємо лінійну рішаючу функцію для двох класів
і
, причому значення лінійної рішаючої функції в класі
більше нуля, а в класі
- менше нуля. На k-ому кроці ми перевіряємо значення лінійної рішаючої функції для заданого вектора
, причому
. Якщо виконується умова
тоді ніяких корекцій вагових коефіцентів робити непотрібно. Якщо ж
тоді потрібно здійснювати корекцію вагових коефіцентів. Вона здійснюється за наступним алгоритмом:
, де
- коректуючий приріст В більшості випадків приймають
. Якщо ми вибираємо вектор
з області
тоді перевіряємо значення
. Якщо
тоді ніяких корекцій вагових коефіцентів робити непотрібно. Якщо ж
тоді корекція здійснюється за наступним правилом:
Вагові коефіціенти вважаються знайденими правильно, якщо для всіх образів, що належать класам
і
правильно визначається знак лінійної рішаючої функції. Існують наступні варіанти вибору коректуючого приросту
: Алгоритм фіксованого приросту:
,
Алгоритм корекції абсолютної величини:
- по цій різниці здійснюють оцінку параметра
.
,
,
Алгоритм дробової корекції:
- найбільше ціле число, яке не перевищує
. Алгоритм перцептрона збіжний лише в отму випадку, коли класи лінійно розділимі. Якщо ж класи лінійно нерозділимі, тоді алгоритм перцептрона зациклюється. 2.2. Процедура навчання класифікаторів для декількох класів Нехай ми маємо
класів. Тоді на k-ому кроці навчання в систему поступає образ
, обчислюється
значень лінійних рішаючих функцій:
Припустимо, що
. Тоді, якщо виконується умова
для будь-якого
, тоді корекції вагових коефіціентів здійснювати непотрібно, тобто
. Нехай для деякого


тоді потрібно виконати наступну корекцію:
для всіх решта векторів вагових коефіціентів
. Якщо класи лінійно розмежовані, тоді цей алгоритм збігається. 2.3. Вибір математичної моделі Для простоти будемо розглядати двовимірний випадок, тобто вектор ознак
є двокомпонентним. Також необхідно вибрати спосіб за яким буде визначатись належність образу до того чи іншого класу. Виберемо наступний варіант:
, тоді
. При проведенні корекції вектора вагових коефіціентів використовується коректуючий приріст
, для вибору якого відомі де-кілька способів. Виберемо алгоритм корекції абсолютної величини:
. 2.4. Опис алгоритму Нехай ми маємо
класів. Тоді на k-ому кроці навчання в систему поступає образ
, обчислюється
значень лінійних рішаючих функцій:
Припустимо, що
. Тоді, якщо виконується умова
для будь-якого
, тоді корекції вагових коефіціентів здійснювати непотрібно, тобто
. Нехай для деякого


тоді потрібно виконати наступну корекцію:
для всіх решта векторів вагових коефіціентів
. Якщо класи лінійно розмежовані, тоді цей алгоритм збігається. Індивідуальне завдання Варіант 2: W1:{(2,8)}, W2:{(9,12)}, W3:{(14,6)} Текст програми #include <stdio.h> #include <conio.h> double W1[3]={0,0,0}, W2[3]={0,0,0}, W3[3]={0,0,0},d1[3],d2[3], d3[3]; int x1[3]={0,0,1},x2[3]={1,1,1},x3[3]={-1,1,1}; int z; unsigned long dms=1; void korekcija(int w) { if(w==1) { W1[0]=W1[0]+x1[0];W1[1]=W1[1]+x1[1];W1[2]=W1[2]+x1[2]; W2[0]=W2[0]-x1[0];W2[1]=W2[1]-x1[1];W2[2]=W2[2]-x1[2]; W3[0]=W3[0]-x1[0];W3[1]=W3[1]-x1[1];W3[2]=W3[2]-x1[2]; } if(w==2) { W1[0]=W1[0]-x2[0];W1[1]=W1[1]-x2[1];W1[2]=W1[2]-x2[2]; W2[0]=W2[0]+x2[0];W2[1]=W2[1]+x2[1];W2[2]=W2[2]+x2[2]; W3[0]=W3[0]-x2[0];W3[1]=W3[1]-x2[1];W3[2]=W3[2]-x2[2]; } if(w==3) { W1[0]=W1[0]-x3[0];W1[1]=W1[1]-x3[1];W1[2]=W1[2]-x3[2]; W2[0]=W2[0]-x3[0];W2[1]=W2[1]-x3[1];W2[2]=W2[2]-x3[2]; W3[0]=W3[0]+x3[0];W3[1]=W3[1]+x3[1];W3[2]=W3[2]+x3[2]; } printf("Iteracija: %d\n",dms); dms++; } void main() { clrscr(); z=0; printf("Uvedit' x1(x;y): ");scanf("%d%d",&x1[0],&x1[1]); printf("Uvedit' x2(x;y): ");scanf("%d%d",&x2[0],&x2[1]); printf("Uvedit' x3(x;y): ");scanf("%d%d",&x3[0],&x3[1]); printf("\nx1(%d;%d;%d);\nx2(%d;%d;%d);\nx3(%d;%d;%d);\n",x1[0],x1[1],x1[2],x2[0],x2[1],x2[2],x3[0],x3[1],x3[2]); getch(); do { z=0; k1:d1[0]=W1[0]*x1[0]+W1[1]*x1[1]+W1[2]*x1[2]; d1[1]=W2[0]*x1[0]+W2[1]*x1[1]+W2[2]*x1[2]; d1[2]=W3[0]*x1[0]+W3[1]*x1[1]+W3[2]*x1[2]; printf("x1: d1[x1]=%lf d2[x1]=%lf d3[x1]=%lf\n",d1[0],d1[1],d1[2]); if ((d1[0]<=d1[1])||(d1[0]<=d1[2])) {printf(" Potribna korekcija\n");korekcija(1);z=1;goto k1;} k2:d2[0]=W1[0]*x2[0]+W1[1]*x2[1]+W1[2]*x2[2]; d2[1]=W2[0]*x2[0]+W2[1]*x2[1]+W2[2]*x2[2]; d2[2]=W3[0]*x2[0]+W3[1]*x2[1]+W3[2]*x2[2]; printf("x2: d1[x2]=%lf d2[x2]=%lf d3[x2]=%lf\n",d2[0],d2[1],d2[2]); if ((d2[1]<=d2[0])||(d2[1]<=d2[2])) {printf(" Potribna korekcija\n");korekcija(2);z=1;goto k2;} k3:d3[0]=W1[0]*x3[0]+W1[1]*x3[1]+W1[2]*x3[2]; d3[1]=W2[0]*x3[0]+W2[1]*x3[1]+W2[2]*x3[2]; d3[2]=W3[0]*x3[0]+W3[1]*x3[1]+W3[2]*x3[2]; printf("x3: d1[x3]=%lf d2[x3]=%lf d3[x3]=%lf\n\n",d3[0],d3[1],d3[2]); if ((d3[2]<=d3[0])||(d3[2]<=d3[1])) {printf(" Potribna korekcija\n");korekcija(3);z=1;goto k3;} getch(); }while (z==1); printf("W1(%lf;%lf;%lf)\nW2(%lf;%lf;%lf)\nW3(%lf;%lf;%lf)\n",W1[1],W1[2],W1[3],W2[1],W2[2],W2[3],W3[1],W3[2],W3[3]); } Peзультати виконання програми Uvedit' x1(x;y): 2 8 Uvedit' x2(x;y): 9 12 Uvedit' x3(x;y): 14 6 x1(2;8;1); x2(9;12;1); x3(14;6;1); x1: d1[x1]=0.000000 d2[x1]=0.000000 d3[x1]=0.000000 Potribna korekcija Iteracija: 1 x1: d1[x1]=69.000000 d2[x1]=-69.000000 d3[x1]=-69.000000 x2: d1[x2]=115.000000 d2[x2]=-115.000000 d3[x2]=-115.000000 Potribna korekcija Iteracija: 2 x2: d1[x2]=-111.000000 d2[x2]=111.000000 d3[x2]=-341.000000 x3: d1[x3]=-122.000000 d2[x3]=122.000000 d3[x3]=-276.000000 Potribna korekcija Iteracija: 3 x3: d1[x3]=-355.000000 d2[x3]=-111.000000 d3[x3]=-43.000000 x1: d1[x1]=-123.000000 d2[x1]=-31.000000 d3[x1]=-107.000000 Potribna korekcija Iteracija: 4 x1: d1[x1]=-54.000000 d2[x1]=-100.000000 d3[x1]=-176.000000 x2: d1[x2]=-195.000000 d2[x2]=-203.000000 d3[x2]=-257.000000 Potribna korekcija Iteracija: 5 x2: d1[x2]=-421.000000 d2[x2]=23.000000 d3[x2]=-483.000000 x3: d1[x3]=-477.000000 d2[x3]=11.000000 d3[x3]=-319.000000 Potribna korekcija Iteracija: 6 x3: d1[x3]=-710.000000 d2[x3]=-222.000000 d3[x3]=-86.000000 x1: d1[x1]=-246.000000 d2[x1]=-62.000000 d3[x1]=-214.000000 Potribna korekcija Iteracija: 7 x1: d1[x1]=-177.000000 d2[x1]=-131.000000 d3[x1]=-283.000000 Potribna korekcija Iteracija: 8 x1: d1[x1]=-108.000000 d2[x1]=-200.000000 d3[x1]=-352.000000 x2: d1[x2]=-390.000000 d2[x2]=-406.000000 d3[x2]=-514.000000 Potribna korekcija Iteracija: 9 x2: d1[x2]=-616.000000 d2[x2]=-180.000000 d3[x2]=-740.000000 x3: d1[x3]=-755.000000 d2[x3]=-177.000000 d3[x3]=-439.000000 Potribna korekcija Iteracija: 10 x3: d1[x3]=-988.000000 d2[x3]=-410.000000 d3[x3]=-206.000000 x1: d1[x1]=-300.000000 d2[x1]=-162.000000 d3[x1]=-390.000000 Potribna korekcija Iteracija: 11 x1: d1[x1]=-231.000000 d2[x1]=-231.000000 d3[x1]=-459.000000 Potribna korekcija Iteracija: 12 x1: d1[x1]=-162.000000 d2[x1]=-300.000000 d3[x1]=-528.000000 x2: d1[x2]=-585.000000 d2[x2]=-609.000000 d3[x2]=-771.000000 Potribna korekcija Iteracija: 13 x2: d1[x2]=-811.000000 d2[x2]=-383.000000 d3[x2]=-997.000000 x3: d1[x3]=-1033.000000 d2[x3]=-365.000000 d3[x3]=-559.000000 Potribna korekcija Iteracija: 14 x3: d1[x3]=-1266.000000 d2[x3]=-598.000000 d3[x3]=-326.000000 x1: d1[x1]=-354.000000 d2[x1]=-262.000000 d3[x1]=-566.000000 Potribna korekcija Iteracija: 15 x1: d1[x1]=-285.000000 d2[x1]=-331.000000 d3[x1]=-635.000000 x2: d1[x2]=-895.000000 d2[x2]=-697.000000 d3[x2]=-913.000000 x3: d1[x3]=-1189.000000 d2[x3]=-675.000000 d3[x3]=-403.000000 Висновки На цій лабораторній роботі я вивчив принципи алгоритмів побудови лінійних рішаючих функцій для кількох класів. Написав програму реалізації алгоритму з графічним інтерфейсом користувача.