МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ Національний унiверситет "Львiвська полiтехнiка" Кафедра САПР
ЗВІТ до лабораторної роботи № 8 на тему: ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. АЛГОРИТМ МАКСИМIННОЇ ВIДСТАНI Перевірив: Денисюк П. Ю. Львiв 2007 1.Мета роботи Вивчити принципи роботи алгоритму k-внутрішніх групових середніх розпізнавання образів. 2. Короткі теоретичні відомості Алгоритм 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в. 3. Текст програми #include <stdio.h> #include <conio.h> #include <stdlib.h> #include <math.h> #include <graphics.h> #define np 12 #define nc 4 struct point { float x,y; int cluster; }; struct st_cl { float x,y; }; float get_distance(point, st_cl); void show_clusters (st_cl *); void show_points (point *); void main (void) { clrscr(); point mas[np]; st_cl cl[nc], cl2[nc]; printf("\n Enter points\n"); for (int i=0;i<np;i++) { scanf(" %f",&mas[i].x); scanf(" %f",&mas[i].y); mas[i].cluster=10; }; for (i=0;i<nc;i++) { cl[i].x=mas[i].x; cl[i].y=mas[i].y; } int key=1; while (key) { for (i=0;i<np;i++) { float d=get_distance(mas[i],cl[0]); mas[i].cluster=0; for (int j=1;j<nc;j++) if (get_distance(mas[i],cl[j])<d) {mas[i].cluster=j; d=get_distance(mas[i],cl[j]);} } for (int j=0;j<nc;j++) { float ax=0, ay=0; int counter=0; for (i=0;i<np;i++) if (mas[i].cluster==j) { ax+=mas[i].x; ay+=mas[i].y; counter++; } cl[j].x=ax/counter; cl[j].y=ay/counter; } key=0; for (i=0;i<nc;i++) if ((cl2[i].x!=cl[i].x) || (cl2[i].y!=cl[i].y)) key=1; for (i=0;i<nc;i++) cl2[i]=cl[i]; } show_clusters(cl); getch(); } float get_distance(point p1, st_cl p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); } void show_clusters (st_cl * cl) { printf("\n CLUSTERS\n"); for (int i=0;i<nc;i++) printf(" cluster %d - ( %f : %f ) \n",i,(cl+i)->x,(cl+i)->y); } void show_points (point * mas) { printf("\n POINTS\n"); for (int i=0;i<np;i++) printf(" (%f:%f) cluster - %d \n",(mas+i)->x,(mas+i)->y,(mas+i)->cluster); } 4. Висновок Виконав[ім’я автора приховано]