Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. ЗАДАЧА ВИЗНАЧЕННЯ КОЕФІЦІЄНТІВ ЛРФ ДЛЯ КІЛЬКОХ МНОЖИН ОБРАЗІВ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Системи автоматизованого проектуваня
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Системи штучного інтелекту
Група:
КН-3
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
іНСТИТУТ КОМП’ютерних НАУК
та ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
Кафедра “Системи автоматизованого проектування”
ЗВІТ
до лабораторної роботи №6
на тему
«ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. Задача визначення КОЕФІЦІЄНТІВ ЛРФ для КІЛЬКОХ множин образів»
з курсу
«Системи штучного інтелекту»
Виконав: ст. гр. КН-3
Львів-2008
1.Мета роботи
Вивчити принципи алгоритмів побудови лінійних рішаючих функцій для кількох класів.
Написати програму реалізації алгоритму з графічним інтерфейсом користувача.
Короткі теоретичні відомості
2.1. Машина перцептрона. Перцептронний підхід до розпізнавання образів
Структура машини перцептрона була запропонована у 1957 році як модель машини, здатної до навчання.
Рис. 1. Структура машини перцептрона
Ця машина складається з наступних частин:
Сенсори (давачі), які сприймають зовнішню інформацію
Асоціативний шар. Кожен давач з'єднаний з кожним блоком асоціативного шару. Виходом цього шару є ознаки EMBED Equation.3.
Блок вагових коефіціентів. За допомогою цього блоку ознаки зважуються (EMBED Equation.3).
Загальний суматор - в ньому отримується значення реакції EMBED Equation.3.
Блок рішення - сюди поступає значення реакції із загального суматора. По значенню EMBED Equation.3 визначається налажність образу до того чи іншого класу.
Якщо поступає образ класу EMBED Equation.3(EMBED Equation.3), а на виході отримується EMBED Equation.3 тоді коректуються вагові коефіціенти.
Значення вектора EMBED Equation.3вважається знайденим правильно, якщо для будь-яких образів з класів EMBED Equation.3і EMBED Equation.3класифікація відбувається правильно.
Така машина є типовою архітектурою машини із здатністю до самонавчання. Алгоритм роботи машини перцептрона грунтується на ідеї "заохочення-покарання". Робота починається з де-якого початкового наближення EMBED Equation.3. Нехай ми знаходимось на k-ому кроці і нехай ми перевіряємо якийсь k-ий образ з множини вибірки EMBED Equation.3. Припустимо, що ми розглядаємо лінійну рішаючу функцію для двох класів EMBED Equation.3і EMBED Equation.3, причому значення лінійної рішаючої функції в класі EMBED Equation.3більше нуля, а в класі EMBED Equation.3- менше нуля. На k-ому кроці ми перевіряємо значення лінійної рішаючої функції для заданого вектора EMBED Equation.3, причому EMBED Equation.3. Якщо виконується умова EMBED Equation.3 тоді ніяких корекцій вагових коефіцентів робити непотрібно. Якщо ж EMBED Equation.3 тоді потрібно здійснювати корекцію вагових коефіцентів. Вона здійснюється за наступним алгоритмом:
EMBED Equation.3, де EMBED Equation.3- коректуючий приріст
В більшості випадків приймають EMBED Equation.3.
Якщо ми вибираємо вектор EMBED Equation.3 з області EMBED Equation.3тоді перевіряємо значення EMBED Equation.3. Якщо EMBED Equation.3 тоді ніяких корекцій вагових коефіцентів робити непотрібно. Якщо ж EMBED Equation.3 тоді корекція здійснюється за наступним правилом:
EMBED Equation.3
Вагові коефіціенти вважаються знайденими правильно, якщо для всіх образів, що належать класам EMBED Equation.3і EMBED Equation.3 правильно визначається знак лінійної рішаючої функції.
Існують наступні варіанти вибору коректуючого приросту EMBED Equation.3:
Алгоритм фіксованого приросту: EMBED Equation.3, EMBED Equation.3
Алгоритм корекції абсолютної величини: EMBED Equation.3- по цій різниці здійснюють оцінку параметра EMBED Equation.3. EMBED Equation.3, EMBED Equation.3, EMBED Equation.3
Алгоритм дробової корекції: EMBED Equation.3- найбільше ціле число, яке не перевищує EMBED Equation.3.
Алгоритм перцептрона збіжний лише в отму випадку, коли класи лінійно розділимі. Якщо ж класи лінійно нерозділимі, тоді алгоритм перцептрона зациклюється.
2.2. Процедура навчання класифікаторів для декількох класів
Нехай ми маємо EMBED Equation.3 класів. Тоді на k-ому кроці навчання в систему поступає образ EMBED Equation.3, обчислюється EMBED Equation.3значень лінійних рішаючих функцій:
EMBED Equation.3
Припустимо, що EMBED Equation.3. Тоді, якщо виконується умова EMBED Equation.3 для будь-якого EMBED Equation.3, тоді корекції вагових коефіціентів здійснювати непотрібно, тобто EMBED Equation.3.
Нехай для деякого EMBED Equation.3 EMBED Equation.3EMBED Equation.3 тоді потрібно виконати наступну корекцію:
EMBED Equation.3
для всіх решта векторів вагових коефіціентів EMBED Equation.3.
Якщо класи лінійно розмежовані, тоді цей алгоритм збігається.
2.3. Вибір математичної моделі
Для простоти будемо розглядати двовимірний випадок, тобто вектор ознак EMBED Equation.3є двокомпонентним. Також необхідно вибрати спосіб за яким буде визначатись належність образу до того чи іншого класу. Виберемо наступний варіант:
EMBED Equation.3, тоді EMBED Equation.3.
При проведенні корекції вектора вагових коефіціентів використовується коректуючий приріст EMBED Equation.3, для вибору якого відомі де-кілька способів. Виберемо алгоритм корекції абсолютної величини:
EMBED Equation.3.
2.4. Опис алгоритму
Нехай ми маємо EMBED Equation.3 класів. Тоді на k-ому кроці навчання в систему поступає образ EMBED Equation.3, обчислюється EMBED Equation.3значень лінійних рішаючих функцій:
EMBED Equation.3
Припустимо, що EMBED Equation.3. Тоді, якщо виконується умова EMBED Equation.3 для будь-якого EMBED Equation.3, тоді корекції вагових коефіціентів здійснювати непотрібно, тобто EMBED Equation.3.
Нехай для деякого EMBED Equation.3 EMBED Equation.3EMBED Equation.3 тоді потрібно виконати наступну корекцію:
EMBED Equation.3
для всіх решта векторів вагових коефіціентів EMBED Equation.3.
Якщо класи лінійно розмежовані, тоді цей алгоритм збігається.
Індивідуальне завдання
Варіант 11: W1:{(1,8)}, W2:{(8,11)}, W3:{(15,9)}
Текст програми
#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): 1 8
Uvedit' x2(x;y): 8 11
Uvedit' x3(x;y): 15 9
x1(1;8;1);
x2(8;11;1);
x3(15;9;1);
x1: d1[x1]=0.000000 d2[x1]=0.000000 d3[x1]=0.000000
Potribna korekcija
Iteracija: 1
x1: d1[x1]=66.000000 d2[x1]=-66.000000 d3[x1]=-66.000000
x2: d1[x2]=97.000000 d2[x2]=-97.000000 d3[x2]=-97.000000
Potribna korekcija
Iteracija: 2
x2: d1[x2]=-89.000000 d2[x2]=89.000000 d3[x2]=-283.000000
x3: d1[x3]=-132.000000 d2[x3]=132.000000 d3[x3]=-308.000000
Potribna korekcija
Iteracija: 3
x3: d1[x3]=-439.000000 d2[x3]=-175.000000 d3[x3]=-1.000000
x1: d1[x1]=-119.000000 d2[x1]=-57.000000 d3[x1]=-75.000000
Potribna korekcija
Iteracija: 4
x1: d1[x1]=-53.000000 d2[x1]=-123.000000 d3[x1]=-141.000000
x2: d1[x2]=-212.000000 d2[x2]=-228.000000 d3[x2]=-160.000000
Potribna korekcija
Iteracija: 5
x2: d1[x2]=-398.000000 d2[x2]=-42.000000 d3[x2]=-346.000000
x3: d1[x3]=-571.000000 d2[x3]=-43.000000 d3[x3]=-309.000000
Potribna korekcija
Iteracija: 6
x3: d1[x3]=-878.000000 d2[x3]=-350.000000 d3[x3]=-2.000000
x1: d1[x1]=-238.000000 d2[x1]=-114.000000 d3[x1]=-150.000000
Potribna korekcija
Iteracija: 7
x1: d1[x1]=-172.000000 d2[x1]=-180.000000 d3[x1]=-216.000000
x2: d1[x2]=-521.000000 d2[x2]=-359.000000 d3[x2]=-223.000000
Potribna korekcija
Iteracija: 8
x2: d1[x2]=-707.000000 d2[x2]=-173.000000 d3[x2]=-409.000000
x3: d1[x3]=-1010.000000 d2[x3]=-218.000000 d3[x3]=-310.000000
Potribna korekcija
Iteracija: 9
x3: d1[x3]=-1317.000000 d2[x3]=-525.000000 d3[x3]=-3.000000
x1: d1[x1]=-357.000000 d2[x1]=-171.000000 d3[x1]=-225.000000
Potribna korekcija
Iteracija: 10
x1: d1[x1]=-291.000000 d2[x1]=-237.000000 d3[x1]=-291.000000
Potribna korekcija
Iteracija: 11
x1: d1[x1]=-225.000000 d2[x1]=-303.000000 d3[x1]=-357.000000
x2: d1[x2]=-733.000000 d2[x2]=-587.000000 d3[x2]=-383.000000
Potribna korekcija
Iteracija: 12
x2: d1[x2]=-919.000000 d2[x2]=-401.000000 d3[x2]=-569.000000
x3: d1[x3]=-1361.000000 d2[x3]=-481.000000 d3[x3]=-399.000000
x1: d1[x1]=-322.000000 d2[x1]=-206.000000 d3[x1]=-454.000000
Potribna korekcija
Iteracija: 13
x1: d1[x1]=-256.000000 d2[x1]=-272.000000 d3[x1]=-520.000000
x2: d1[x2]=-822.000000 d2[x2]=-498.000000 d3[x2]=-666.000000
x3: d1[x3]=-1273.000000 d2[x3]=-569.000000 d3[x3]=-487.000000
x1: d1[x1]=-256.000000 d2[x1]=-272.000000 d3[x1]=-520.000000
x2: d1[x2]=-822.000000 d2[x2]=-498.000000 d3[x2]=-666.000000
x3: d1[x3]=-1273.000000 d2[x3]=-569.000000 d3[x3]=-487.000000
W1(-23.000000;-1.000000;-19.000000)
W2(-31.000000;-5.000000;7.000000)
W3(-65.000000;-7.000000;-256.000000)
Висновки
На цій лабораторній роботі я вивчив принципи алгоритмів побудови лінійних рішаючих функцій для кількох класів.
Написав програму реалізації алгоритму з графічним інтерфейсом користувача.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора