МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ
Національний унiверситет "Львiвська полiтехнiка"
Кафедра САПР
ЗВІТ
до лабораторної роботи № 8
на тему:
ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. АЛГОРИТМ МАКСИМIННОЇ ВIДСТАНI
Виконав:
Гр. КН-214
Перевірив:
Денисюк П. Ю.
Льв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(" (%...
