Міністерство освіти і науки України Національний університет «Львівська політехніка» кафедра САПР
Лабораторна робота №3 з курсу “Основи проектування систем штучного інтелекту” тема: АЛГОРИТМ К-ВНУТРIШНIХ ГРУПОВИХ СЕРЕДНІХ. Львів-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, ij, де 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-внутрішніх групових середніх розпізнавання образів. Написали програму реалізації алгоритму з графічним інтерфейсом користувача.