Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритм максимінної відстані
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
КН
Кафедра:
Системи автоматизованого проектування
Інформація про роботу
Рік:
2009
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Системи штучного інтелекту
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ІНСТИТУТ КОМП’ЮТЕРНИХ НАУК
ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
Кафедра “Системи автоматизованого проектування”
ЗВІТ
до лабораторної роботи №2
на тему
«Алгоритм максимінної відстані»
з курсу
«Системи штучного інтелекту»
1.Мета роботи
Вивчити принципи роботи максимінного алгоритму розпізнавання образів.
Написати програму реалізації алгоритму з графічним інтерфейсом користувача.
2. Короткі теоретичні відомості
2.1. Максимінний алгоритм розпізнавання образів
Алгоритм використовує евклiдову вiдстань. Алгоритм, у принципi, аналогiчний схемi евристичного алгоритму порогової величини, за виключенням тiєї обставини, що, в першу чергу, вин виявляє найвiддаленiшi кластори. Один з об'єктiв (X1) довiльним чином назначається центром першого кластера. Потiм вiдшукується образ, розмiщений вiд образа X1 найдалi, який призначається центром кластера Z2. На третьому кроцi алгоритму здiйснюється обчислення вiдстаней мiж всiма iншими образами вибiрки i центрами кластерiв Z1 i Z2. В кожнiй парi цих вибірок вибирається мiнiмальне. Пiсля цього видiляється максимальне з цих мiнiмальних вiдстаней. Якщо останнє складає значну частину вiдстанi мiж кластерами Z1 i Z2 (половина цiєї вiдстанi), вiдповiдний образ призначається центром кластера Z3. Iнакше - виконання алгоритму припиняється.
В загальному випадку описана процедура повторюється до тих пiр, поки на якомусь кроцi не буде отримане максимальне значення вiдстанi, для якої умова, що викликає видiлення кластера, не виконується.
(
1. Z1=X1
2. Обчислити Di1
3. Вибрати Ki(1)=max{Di1} ( i(1 ; L1=Ki(1)
(
4. Z2=Xi
5. Обчислити Di1, Di2 ( i(1,2
6. Обчислити Ai=min{Di1,Di2} ( i(1,2
7. Обчислити Ki(2)=max{Ai} ( i(1,2 ; L2=Ki(2)
(
8. Якщо L2>0.5L1, тодi Z3=Xi. Iнакше - STOP.
9. Визначити середню арифметичну величину попереднiх максимальних
вiдстаней:
Lc.a.=(L1+L2)/2
10. Обчислити Di1, Di2, Di3 ( i(1,2,3
11. Обчислити Ai=min{Di1, Di2, Di3}
12. Обчислити Ki(3)=max{Ai} ; L3=Ki(3)
(
13. Якщо Li>0.5La.c., тодi Z4=Xi. Iнакше - STOP.
14. Обчислити Lc.a.=(L1+L2+L3)/3
Індивідуальне завдання
N
2
0
1
0
2
0
3
4
1
5
1
5
2
5
3
6
9
8
6
9
2
9
5
9
6
9
7
10
1
10
2
10
3
11
3
Текст програми:
Program Laba_1;
Uses CRT;
const q = 17 ;
type dis = record
v:array [1..q] of real;
end;
var
x : array [1..q] of integer;
y : array [1..q] of integer;
j,i,k:integer;
n:array [1..q] of integer;
d: array [1..q] of dis;
ser:real; t:string;
min:array [1..q] of real;
dmax_Z:array[1..q] of real;
centre: array [1..q] of integer;
centrex: array [1..q] of integer;
centrey: array [1..q] of integer;
xg:real;
Label next,quit;
BEGIN
clrscr;
writeln;
x[1]:= 0 ; y[1]:=1;x[2]:= 0 ; y[2]:=2;
x[3]:= 0 ; y[3]:=3;x[4]:= 4 ; y[4]:=1;
x[5]:= 5 ; y[5]:=1;x[6]:= 5 ; y[6]:=2;
x[7]:= 5 ; y[7]:=3;x[8]:= 6 ; y[8]:=9;
x[9]:= 8 ; y[9]:=6;x[10]:=9 ; y[10]:=2;
x[11]:=9 ; y[11]:=5;x[12]:=9 ; y[12]:=6;
x[13]:=9 ; y[13]:=7;x[14]:=10; y[14]:=1;
x[15]:=10; y[15]:=2;x[16]:=10; y[16]:=3;
x[17]:=11; y[17]:=3;
t:=' ';
textcolor(8);
writeln;
n[1]:=1;
centre[1]:=1;
centrex[1]:=x[1];
centrey[1]:=y[1];
textcolor(14);
writeln(' Z1(',centrex[1],';',centrey[1],')');
textcolor(15);
For i:=1 to q do
begin
if i<10 then write(' x',i,' (',x[i],';',y[i],')',' ')
else
if i=12 then write(' x',i,'(',x[i],';',y[i],')',' ')
else
write(' x',i,'(',x[i],';',y[i],')',' ');
d[1].v[i]:=sqrt(sqr((centrex[1]-x[i]))+sqr((centrey[1]-y[i])));
writeln(d[1].v[i]:2:1);
end;
dmax_z[1]:=d[1].v[1];
centre[2]:=1;
For i:=1 to q do
if d[1].v[i]>dmax_z[1] then
begin
dmax_z[1]:=d[1].v[i];
centre[2]:=i;
end;
textcolor(3);
writeln(' NOVYJ CENTR = X(',centre[2],') d_max = ',dmax_z[1]:2:1);
textcolor(15);
centrex[2]:=x[centre[2]];
centrey[2]:=y[centre[2]];
writeln;
textcolor(14);
writeln(' Z1(',centrex[1],';',centrey[1],')',' Z2(',centrex[2],';',centrey[2],')'); textcolor(15);
For i:=1 to q do
begin
if i<10 then
write(' x',i,' (',x[i],';',y[i],')',' ',d[1].v[i]:2:1,t)
else
if i=12 then
write(' x',i,'(',x[i],';',y[i],')',' ',d[1].v[i]:2:1,t)
else
write(' x',i,'(',x[i],';',y[i],')',' ',d[1].v[i]:2:1,t);
d[2].v[i]:=sqrt(sqr((centrex[2]-x[i]))+sqr((centrey[2]-y[i])));
writeln(d[2].v[i]:2:1);
end;
For i:=1 to q do
begin
if d[1].v[i]>d[2].v[i] then
min[i]:=d[2].v[i]
else
min[i]:=d[1].v[i];
end;
writeln;
dmax_z[2]:=min[1];
For i:=1 to q do
if min[i]>dmax_z[2] then
begin
dmax_z[2]:=min[i];
centre[3]:=i;
end;
if dmax_z[2] >= 0.5*(dmax_z[1]/1) then
begin
textcolor(3);
writeln(' NOVYJ CENTR = X(',centre[3],') d_max = ',dmax_z[2]:2:1); textcolor(15);
end
else
begin
textcolor(4);
writeln('***NEMAJE BILSHE KLASTERIV*** !!!');
textcolor(15);
goto quit;
end;
k:=3;
NEXT:;
readln;
centrex[k]:=x[centre[k]];
centrey[k]:=y[centre[k]];
textcolor(14);
writeln(' min',' Z',k,'(',centrex[k],';',centrey[k],')');
textcolor(15);
For i:=1 to q do
begin
if i<10 then
write(' x',i,' (',x[i],';',y[i],')',t,min[i]:2:1,t)
else
if i=12 then
write(' x',i,'(',x[i],';',y[i],')',' ',min[i]:2:1,t)
else
write(' x',i,'(',x[i],';',y[i],')',t,min[i]:2:1,t);
d[k].v[i]:=sqrt(sqr((centrex[k]-x[i]))+sqr((centrey[k]-y[i])));
writeln(d[k].v[i]:2:1);
end;
For i:=1 to q do
if d[k].v[i]<min[i] then
min[i]:=d[k].v[i];
writeln;
dmax_z[k]:=min[1];
For i:=1 to q do
if min[i]>dmax_z[k] then
begin
dmax_z[k]:=min[i];
centre[k+1]:=i;
end;
ser:=0;
j:=0;
For i:=k-1 downto 1 do
begin
ser:=ser+dmax_z[i];
j:=j+1;
end;
ser:=ser/j;
ser:=0.5*ser;
if dmax_z[k] >= ser then
begin
textcolor(3);
writeln(' NOVYJ CENTR = X(',centre[k+1],') d_max = ',dmax_z[k]:2:1);
textcolor(15);
k:=k+1;
goto next;
end
else
begin
textcolor(4);
writeln(' ***NEMAJE BILSHE KLASTERIV*** ');
textcolor(15);
goto quit;
end;
quit:;
writeln;
readln;
END.
Висновок
На цій лабораторній роботі я вивчив принципи роботи алгоритму k-внутрішніх групових середніх розпізнавання образів.
Написав програму реалізації алгоритму.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора