Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. ЗАДАЧА ВИЗНАЧЕННЯ КОЕФІЦІЄНТІВ ЛРФ ДЛЯ КІЛЬКОХ МНОЖИН ОБРАЗІВ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
КН
Кафедра:
Системи автоматизованого проектування
Інформація про роботу
Рік:
2008
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Системи штучного інтелекту
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІНСТИТУТ КОМП’ЮТЕРНИХ НАУК
ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
Кафедра “Системи автоматизованого проектування”
ЗВІТ
до лабораторної роботи №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
Висновки
На цій лабораторній роботі я вивчив принципи алгоритмів побудови лінійних рішаючих функцій для кількох класів.
Написав програму реалізації алгоритму з графічним інтерфейсом користувача.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора