Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дослідження алгоритмів розпізнавання образів. Алгоритм k-внутрішніх групових середніх
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Не вказано
Інформація про роботу
Рік:
2007
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Звіт
про виконання лабораторної роботи №8
на тему:
«Дослідження алгоритмів розпізнавання образів.
Алгоритм k-внутрішніх групових середніх»
Львів – 2007
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в.
Текст програми:
#include<conio.h>
#include<stdio.h>
#include<graphics.h>
#include<stdlib.h>
#include<math.h>
#define k 5
#define N 18
int A[k][N];
typedef struct point
{float x,y;};
typedef struct minimal
{float m;
int i;};
void graphic(int *x,int *y,point *Z,int *K);
main()
{point Z[k],Z1[k];
int X[N]={0,3,2,3,4,3,8,8,20,20,19,22,21,11,12,12,11,11};
int Y[N]={1,1,2,2,2,3,6,7,7,8,10,9,9,10,10,11,11,12};
float D;
minimal min;
int i,j,K[k],l,o=1,jj=0;
float sumx,sumy;
clrscr();
for(i=0;i<k;i++)
{
Z[i].x=X[i+2];
Z[i].y=Y[i+2];
}
start:
for(i=0;i<k;i++)
K[i]=0;
for(i=0;i<N;i++)
{
min.m=sqrt(pow(Z[0].x-X[i],2)+pow(Z[0].y-Y[i],2));
min.i=0;
for(j=0;j<k;j++)
{D=sqrt(pow(Z[j].x-X[i],2)+pow(Z[j].y-Y[i],2));
if(D<min.m) {min.m=D;min.i=j;}
}
A[min.i][K[min.i]]=i;K[min.i]++;}
for(i=0;i<k;i++)
{
sumx=0;sumy=0;
for(j=0;j<K[i];j++)
{
sumx=sumx+X[A[i][j]];
sumy=sumy+Y[A[i][j]];
}
Z1[i].x=sumx/K[i];
Z1[i].y=sumy/K[i];
}
for(i=0;i<k;i++)
if((Z[i].x!=Z1[i].x)||(Z[i].y!=Z1[i].y)) goto bad;
goto stop;
bad:
for(i=0;i<k;i++)
{
Z[i].x=Z1[i].x;
Z[i].y=Z1[i].y;
}
goto start;
stop:
textcolor(2);
cprintf("VUVID TOCHOK:");
for(i=0;i<N;i++)
printf("\nX%d(%d,%d);",i+1,X[i],Y[i]);
printf("\n");
cprintf("VUVID ZENTRIV:");
for(i=0;i<k;i++)
printf("\nZ%d=(%4.2f,%4.2f);",i+1,Z[i].x,Z[i].y);
printf("\n");
cprintf("VUVID CLASTERIV:");
for(i=0;i<k;i++)
{printf("\nA%d={",i+1);
for(j=0;j<K[i];j++)
printf(" X%d(%d,%d)",A[i][j]+1,X[A[i][j]],Y[A[i][j]]);
printf(" }");}
getch();
graphic(X,Y,Z,K);
return 0;}
void graphic(int *x,int *y,point *Z,int *K)
{int m,d,i,j;
int driver=DETECT,mode;
clrscr();
initgraph(&driver,&mode,"");
setcolor(15);
line(11,460,600,460);
for(i=11;i<585;i++)
if(fmod(i,10.0)==0) line(i,457,i,463);
line(600,460,590,455);line(600,460,590,465);
outtextxy(610,460,"X");
outtextxy(10,470,"0");
line(10,460,10,50);
for(i=459;i>61;i--)
if(fmod(i,20.0)==0) line(7,i,13,i);
line(10,50,5,60);line(10,50,15,60);
outtextxy(10,40,"Y");
setfillstyle(1,2);
setcolor(2);
for(i=0,m=1;i<k;i++,m++)
{d=m+8;
setcolor(d);
setfillstyle(1,d);
for(j=0;j<K[i];j++)
{circle(x[A[i][j]]*10+10,(y[A[i][j]]*20-480)*(-1)-20,4);
floodfill(x[A[i][j]]*10+10,(y[A[i][j]]*20-480)*(-1)-20,d);}}
setfillstyle(1,4);
setcolor(4);
for(j=0;j<k;j++)
{circle(Z[j].x*10+10,(Z[j].y*20-480)*(-1)-20,2);
floodfill(Z[j].x*10+10,(Z[j].y*20-480)*(-1)-20,4);}
getch();
closegraph();
return;}
17.07.2020 14:07-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора