Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
АЛГОРИТМ К-ВНУТРIШНIХ ГРУПОВИХ СЕРЕДНІХ.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Системи автоматизованого проектуваня
Інформація про роботу
Рік:
2008
Тип роботи:
Лабораторна робота
Предмет:
Основи проектування систем штучного інтелекту
Група:
КН-3
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет
«Львівська політехніка»
кафедра САПР
Лабораторна робота №3
з курсу “Основи проектування систем штучного інтелекту”
тема: АЛГОРИТМ К-ВНУТРIШНIХ ГРУПОВИХ СЕРЕДНІХ.
Виконав:
cт. гр. КН-3
Львів-2008
1.Мета роботи
Вивчити принципи роботи алгоритму k-внутрішніх групових середніх розпізнавання образів.
Написати програму реалізації алгоритму з графічним інтерфейсом користувача.
2. Короткі теоретичні відомості
2.1. Алгоритм k-внутрішніх групових середніх розпізнавання образів
КРОК 1.
Вибираються к початкових центрiв кластерiв Z1(1), Z2(1),...,Zk(1).
Цей вибір здiйснюється довiльно i, звичайно, в якостi початкових центрiв використовуються першi k результатiв вибiрки з заданої множини образiв.
КРОК 2.
На k-му кроцi iтерацiї задана множина образiв розподiляється по k кластерах за таким правилом : XєSj(k), якщо ||X-Zj(k)||<=||X-Zj(k)||, для всiх i=1,2,...,k, ij, де Sj(k) - множина образiв, якi входять в кластер з центром Zj(k). У випадку рiвностi рiшення приймаються довiльним чином.
КРОК 3.
На основi результатів кроку 2 визначаються новi центри кластерiв Zj(k+1), j=1,2,...,k, виходячи з умови, що сума квадратiв вiдстаней мiж усiма образами, що належать множині Sj(k), i новiм центром кластера повинна бути мiнiмальною. Iншими словами, новi центри кластерiв Zj(k+1) вибираються таким чином, щоб мiнiмiзувати показник якостi
Jj=||X-Zj(k+1)||^2, j=1,2,...,k. XєSj(k)
Центр Zj(k+1), що забезпечує мiнiмiзацiю показника якостi, є, по сутi, вибiрковим середнiм, визначеним по множинi Sj(k). Вiдповiдно, новi центри кластерiв визначаються як:
Zj(k+1)=(1/Nj)X, j=1,2,...,k, XЄSj(k),
де Nj- число вибiркових образiв, що входять в множину типу Sj(k).
Очевидно, що назва алгоритму "К внутрiшнiх групових" визначається способом, прийнятим для послiдовної корекцiї призначення центрiв кластерiв.
КРОК 4.
Рiвнiсть Zj(k+1) при j=1,2,...,k є умовою збiжностi алгоритму, i при її досягненнi виконання алгоритму припиняється. Iнакше, крок 2. Якiсть залежить:
вiд кiлькостi вибираємих центрiв кластерiв;
вiд вибору початкових центрiв кластерiв;
вiд послiдовностi проглядання образiв;
вiд геометричної особливостi даних.
Практичне застосування алгоритму вимагає проведення експериментiв, пов'язаних iз вибором рiзних значень параметра k i початковим розмiщенням центрiв кластерiв.
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
4.6. Х1(0,3), Х2(0,5), Х3(0,6), Х4(1,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(6,1), Х9(5,5), Х10(6,6), Х11(7,7), Х12(10,10), Х13(20,8), Х14(20,9). K=4
Текст програми:
Program Laba_1;
Uses CRT;
const q = 14 ; kl = 4;
type dis = record
v:array [1..q] of real;
t:array [1..q] of integer;
end;
var
x : array [1..q] of integer;
y : array [1..q] of integer;
j,i,k:integer;
d: array [1..kl] of dis;
serx,sery:real;
centre: array [1..kl] of integer;
centrex: array [1..kl] of real;
centrey: array [1..kl] of real;
cx: array [1..kl] of real;
cy: array [1..kl] of real;
min:real; ok:boolean;
Label next,quit;
BEGIN
clrscr;writeln;
x[1]:= 0 ; y[1]:=3;
x[2]:= 0 ; y[2]:=5;
x[3]:= 0 ; y[3]:=6;
x[4]:= 1 ; y[4]:=4;
x[5]:= 5 ; y[5]:=0;
x[6]:= 6 ; y[6]:=0;
x[7]:= 7 ; y[7]:=0;
x[8]:= 6 ; y[8]:=1;
x[9]:= 5 ; y[9]:=5;
x[10]:=6 ; y[10]:=6;
x[11]:=7 ; y[11]:=7;
x[12]:=10; y[12]:=10;
x[13]:=20; y[13]:=8;
x[14]:=20; y[14]:=9;
textcolor(8);
writeln(' (C) Copyright Demon KN-316/L3-v:18. 2008 ');
writeln; writeln; textcolor(15);
For i:=1 to kl do begin
centre[i]:=i; centrex[i]:=x[i]; centrey[i]:=y[i];
writeln(' CENTRE ',i,' --- Z',i,'(',centrex[i]:1:1,';',centrey[i]:1:1,');');
end;
NEXT:;
writeln; readln; textcolor(14);
write(' Z1(',centrex[1]:1:1,';',centrey[1]:1:1,') ');
For i:=2 to kl do
if i=kl then writeln('Z',i,'(',centrex[i]:1:1,';',centrey[i]:1:1,')') else
write('Z',i,'(',centrex[i]:1:1,';',centrey[i]:1:1,')',' ');
textcolor(15); writeln;
For i:=1 to kl do
For j:=1 to q do
d[i].v[j]:=sqrt(sqr((centrex[i]-x[j]))+sqr((centrey[i]-y[j])));
For i:=1 to q do begin
if i<10 then write(' X',i,' (',x[i],';',y[i],')',' ') else
if i>=13 then write(' X',i,'(',x[i],';',y[i],')',' ') else
write(' X',i,'(',x[i],';',y[i],')',' ');
For j:=1 to kl do begin textcolor(j*2);
if j=kl then writeln(d[j].v[i]:2:1) else
write(d[j].v[i]:2:1,' '); textcolor(15);
end;
end;
readln;
For i:=1 to kl do
For j:=1 to q do
d[i].t[j]:=0;
For i:=1 to q do begin
min:=d[1].v[i]; k:=1;
For j:=1 to kl do begin
if min>d[j].v[i] then begin
min:=d[j].v[i];
k:=j; end;
end;
d[k].t[i]:=1;
end;
{For i:=1 to q do
writeln(d[1].t[i],' ',d[2].t[i],' ',d[3].t[i],' ',d[4].t[i]);}
{--------------------------------------------------------------}
For i:=1 to kl do begin
serx:=0; sery:=0; k:=0;
For j:=1 to q do
if d[i].t[j]=1 then begin
serx:=serx+x[j];
sery:=sery+y[j];
k:=k+1;
end;
if k<>0 then begin
cx[i]:=serx/k;
cy[i]:=sery/k;
end; end;
textcolor(3);
For i:=1 to kl do
writeln(i,' (x=',cx[i]:2:1,' y=',cy[i]:2:1,')'); textcolor(15);
readln;
ok:=true;
For i:=1 to kl do
if (cx[i]<>centrex[i])and(cy[i]<>centrey[i]) then ok:=false;
textcolor(4);writeln(ok);textcolor(15);
if ok=false then begin
For i:=1 to kl do begin
centrex[i]:=cx[i];
centrey[i]:=cy[i];
end; goto next; end;
quit:;
readln;
END.
Результат виконання:
CENTRE 1 --- Z1(0.0;3.0);
CENTRE 2 --- Z2(0.0;5.0);
CENTRE 3 --- Z3(0.0;6.0);
CENTRE 4 --- Z4(1.0;4.0);
Z1(0.0;3.0) Z2(0.0;5.0) Z3(0.0;6.0) Z4(1.0;4.0)
X1 (0;3) 0.0 2.0 3.0 1.4
X2 (0;5) 2.0 0.0 1.0 1.4
X3 (0;6) 3.0 1.0 0.0 2.2
X4 (1;4) 1.4 1.4 2.2 0.0
X5 (5;0) 5.8 7.1 7.8 5.7
X6 (6;0) 6.7 7.8 8.5 6.4
X7 (7;0) 7.6 8.6 9.2 7.2
X8 (6;1) 6.3 7.2 7.8 5.8
X9 (5;5) 5.4 5.0 5.1 4.1
X10(6;6) 6.7 6.1 6.0 5.4
X11(7;7) 8.1 7.3 7.1 6.7
X12(10;10) 12.2 11.2 10.8 10.8
X13(20;8) 20.6 20.2 20.1 19.4
X14(20;9) 20.9 20.4 20.2 19.6
1 (x=0.0 y=3.0)
2 (x=0.0 y=5.0)
3 (x=5.0 y=8.0)
4 (x=8.3 y=4.0)
FALSE
Z1(0.0;3.0) Z2(0.0;5.0) Z3(5.0;8.0) Z4(8.3;4.0)
X1 (0;3) 0.0 2.0 7.1 8.4
X2 (0;5) 2.0 0.0 5.8 8.4
X3 (0;6) 3.0 1.0 5.4 8.5
X4 (1;4) 1.4 1.4 5.7 7.3
X5 (5;0) 5.8 7.1 8.0 5.2
X6 (6;0) 6.7 7.8 8.1 4.6
X7 (7;0) 7.6 8.6 8.2 4.2
X8 (6;1) 6.3 7.2 7.1 3.8
X9 (5;5) 5.4 5.0 3.0 3.4
X10(6;6) 6.7 6.1 2.2 3.0
X11(7;7) 8.1 7.3 2.2 3.3
X12(10;10) 12.2 11.2 5.4 6.2
X13(20;8) 20.6 20.2 15.0 12.4
X14(20;9) 20.9 20.4 15.0 12.7
1 (x=0.5 y=3.5)
2 (x=0.0 y=5.5)
3 (x=7.0 y=7.0)
4 (x=10.7 y=3.0)
FALSE
Z1(0.5;3.5) Z2(0.0;5.5) Z3(7.0;7.0) Z4(10.7;3.0)
X1 (0;3) 0.7 2.5 8.1 10.7
X2 (0;5) 1.6 0.5 7.3 10.9
X3 (0;6) 2.5 0.5 7.1 11.1
X4 (1;4) 0.7 1.8 6.7 9.7
X5 (5;0) 5.7 7.4 7.3 6.4
X6 (6;0) 6.5 8.1 7.1 5.5
X7 (7;0) 7.4 8.9 7.0 4.7
X8 (6;1) 6.0 7.5 6.1 5.1
X9 (5;5) 4.7 5.0 2.8 6.0
X10(6;6) 6.0 6.0 1.4 5.5
X11(7;7) 7.4 7.2 0.0 5.4
X12(10;10) 11.5 11.0 4.2 7.0
X13(20;8) 20.0 20.2 13.0 10.6
X14(20;9) 20.3 20.3 13.2 11.1
1 (x=2.0 y=2.3)
2 (x=0.0 y=5.5)
3 (x=7.0 y=7.0)
4 (x=11.8 y=3.6)
FALSE
Z1(2.0;2.3) Z2(0.0;5.5) Z3(7.0;7.0) Z4(11.8;3.6)
X1 (0;3) 2.1 2.5 8.1 11.8
X2 (0;5) 3.3 0.5 7.3 11.9
X3 (0;6) 4.2 0.5 7.1 12.0
X4 (1;4) 1.9 1.8 6.7 10.8
X5 (5;0) 3.8 7.4 7.3 7.7
X6 (6;0) 4.6 8.1 7.1 6.8
X7 (7;0) 5.5 8.9 7.0 6.0
X8 (6;1) 4.2 7.5 6.1 6.4
X9 (5;5) 4.0 5.0 2.8 6.9
X10(6;6) 5.4 6.0 1.4 6.3
X11(7;7) 6.8 7.2 0.0 5.9
X12(10;10) 11.1 11.0 4.2 6.6
X13(20;8) 18.9 20.2 13.0 9.3
X14(20;9) 19.2 20.3 13.2 9.8
1 (x=4.8 y=0.8)
2 (x=0.3 y=5.0)
3 (x=7.0 y=7.0)
4 (x=20.0 y=8.5)
FALSE
Z1(4.8;0.8) Z2(0.3;5.0) Z3(7.0;7.0) Z4(20.0;8.5)
X1 (0;3) 5.3 2.0 8.1 20.7
X2 (0;5) 6.4 0.3 7.3 20.3
X3 (0;6) 7.1 1.1 7.1 20.2
X4 (1;4) 5.0 1.2 6.7 19.5
X5 (5;0) 0.8 6.8 7.3 17.2
X6 (6;0) 1.4 7.6 7.1 16.4
X7 (7;0) 2.3 8.3 7.0 15.5
X8 (6;1) 1.2 6.9 6.1 15.9
X9 (5;5) 4.2 4.7 2.8 15.4
X10(6;6) 5.3 5.8 1.4 14.2
X11(7;7) 6.6 7.0 0.0 13.1
X12(10;10) 10.6 10.9 4.2 10.1
X13(20;8) 16.8 19.9 13.0 0.5
X14(20;9) 17.3 20.1 13.2 0.5
1 (x=6.0 y=0.3)
2 (x=0.3 y=4.5)
3 (x=7.0 y=7.0)
4 (x=20.0 y=8.5)
FALSE
Z1(6.0;0.3) Z2(0.3;4.5) Z3(7.0;7.0) Z4(20.0;8.5)
X1 (0;3) 6.6 1.5 8.1 20.7
X2 (0;5) 7.7 0.6 7.3 20.3
X3 (0;6) 8.3 1.5 7.1 20.2
X4 (1;4) 6.3 0.9 6.7 19.5
X5 (5;0) 1.0 6.5 7.3 17.2
X6 (6;0) 0.3 7.3 7.1 16.4
X7 (7;0) 1.0 8.1 7.0 15.5
X8 (6;1) 0.8 6.7 6.1 15.9
X9 (5;5) 4.9 4.8 2.8 15.4
X10(6;6) 5.8 5.9 1.4 14.2
X11(7;7) 6.8 7.2 0.0 13.1
X12(10;10) 10.5 11.2 4.2 10.1
X13(20;8) 16.0 20.1 13.0 0.5
X14(20;9) 16.5 20.3 13.2 0.5
1 (x=6.0 y=0.3)
2 (x=0.3 y=4.5)
3 (x=7.0 y=7.0)
4 (x=20.0 y=8.5)
TRUE
Висновок: У даній лабораторній роботі ми вивчили принципи роботи алгоритму k-внутрішніх групових середніх розпізнавання образів.
Написали програму реалізації алгоритму з графічним інтерфейсом користувача.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора