АЛГОРИТМ К-ВНУТРIШНIХ ГРУПОВИХ СЕРЕДНІХ.. Лабораторна робота з Основи проектування систем штучного інтелекту. Робота № 200735

АЛГОРИТМ К-ВНУТРIШНIХ ГРУПОВИХ СЕРЕДНІХ.

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Системи автоматизованого проектуваня

Інформація про роботу

Рік:

2015

Тип роботи:

Лабораторна робота

Предмет:

Основи проектування систем штучного інтелекту

Група:

КН-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, 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-внутрішніх групових середніх розпізнавання образів. Написали програму реалізації алгоритму з графічним інтерфейсом користувача.

Лабораторна робота Основи проектування систем штучного інтелекту

2015

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись