Міністерство освіти україни
НАЦІОНАЛЬНИЙ ТРАНСПОРТНИЙ УНІВЕРСИТЕТ
Кафедра Інформаційних систем
Звіт
до лабораторної роботи №2
Дисципліни " Системи розпізнавання образів " для студентів-магістрів спеціальності кн дослідження алгоритмів розпізнавання образів. Алгоритм к-внутрiшнiх групових середніх
|
Виконала: Студент групи
Прийняв: к.т.н., доц.Іванченко Г.Ф
|
Київ: НТУ, 2010 р
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, ij, де 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в.
Програма:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, TeEngine, Series, ExtCtrls, TeeProcs, Chart;
type
TForm1 = class(TForm)
Chart1: TChart;
Series1: TPointSeries;
Button1: TButton;
OpenDialog1: TOpenDialog;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
i: integer;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
type point = record
x,y: double;
index: integer;
cluster: integer;
end;
type dist = record
d: double;
i: integer;
end;
var f: textfile;
x,y: double;
arr: array of point;
z1,z2,z1old,z2old: point;
i,j,k1,k2,a:integer;
d1,d2: array of dist;
label next;
Procedure find(x,y:double;n: integer; var k: integer);
var i: integer;
begin
k:=9999;
for i:=0 to n do
if ((Chart1.SeriesList[0].XValue[i]=x) and (Chart1.SeriesList[0].yValue[i]=y)) then begin
k:=i; break; end;
end;
begin
OpenDialog1.execute;
if OpenDialog1.FileName<>'' then
begin
// read file
assignfile(f,OpenDialog1.filename);
reset(f);
Chart1.SeriesList[0].Clear;
setlength(arr,0);
i:=0;
while not(eof(f)) do begin
readln(f,x,y);
Chart1.SeriesList[0].AddXY(x,y);
setlength(arr,length(arr)+1);
arr[high(arr)].x:=x;
arr[high(arr)].y:=y;
arr[high(arr)].index:=i;
arr[high(arr)].cluster:=0;
inc(i);
end;
closefile(f);
// calculate here
setlength(d1,Length(arr));
setlength(d2,Length(arr));
z1:=arr[0];
z2:=arr[1];
next:
z1old:=z1;
z2old:=z2;
//Chart1.SeriesList[0].ValueColor[0]:=clYellow;
for i:=0 to high(arr) do
begin d1[i].d:=sqrt(sqr(z1.x-arr[i].x) + sqr(z1.y-arr[i].y));
d1[i].i:=arr[i].index;
end;
for i:=0 to high(arr) do
begin d2[i].d:=sqrt(sqr(z2.x-arr[i].x) + sqr(z2.y-arr[i].y));
d2[i].i:=arr[i].index;
end;
k1:=0; k2:=0;
for i:=0 to high(arr) do
begin
if d1[i].d<d2[i].d then
begin
arr[i].cluster:=1; k1:=k1+1;
end else
begin
arr[i].cluster:=2; k2:=k2+1;
end;
end;
z1.x:=0;z1.y:=0;z2.x:=0;z2.y:=0;
for i:=0 to high(arr) do
begin
if arr[i].cluster=1 then
begin
z1.x:=z1.x+arr[i].x;
z1.y:=z1.y+arr[i].y;
end
else begin
z2.x:=z2.x+arr[i].x;
z2.y:=z2.y+arr[i].y;
end;
end;
z1.x:=z1.x/k1;
z1.y:=z1.y/k1;
z2.x:=z2.x/k2;
z2.y:=z2.y/k2;
if ((z1.x<>z1old.x) or (z2.x<>z2old.x)or (z1.y<>z1old.y)or (z2.y<>z2old.y)) then
begin
z1old:=z1;
z2old:=z2;
goto next;
end;
for i:=0 to high(arr) do
begin
find(arr[i].x,arr[i].y,length(arr),a);
if arr[i].cluster=1 then Chart1.SeriesList[0].ValueColor[a]:=clYellow
else Chart1.SeriesList[0].ValueColor[a]:=clBlue;
end;
Chart1.SeriesList[0].AddXY(z1.x,z1.y);
find(z1.x,z1.y,length(arr)+1,a);
Chart1.SeriesList[0].ValueColor[a]:=clGreen;
Chart1.SeriesList[0].AddXY(z2.x,z2.y);
find(z2.x,z2.y,length(arr)+2,a);
Chart1.SeriesList[0].ValueColor[a]:=clGreen;
end;
end;
end.
Результати роботи програми :
0 |
1 |
0 |
3 |
1 |
2 |
2 |
3 |
2 |
8 |
2 |
10 |
3 |
9 |
4 |
5 |
4 |
10 |
7 |
6 |
7 |
7 |
8 |
7 |
8 |
7 |
8 |
8 |
10 |
3 |
11 |
3 |
11 |
2 |
Висновок: В даній лабораторній роботі ми розглянули роботу алгоритму розпізнавання образів та розбили на 2 кластери множину точок на площині за індивідуальним завданням.
Програма:
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, TeEngine, Series, ExtCtrls, TeeProcs, Chart;
type
TForm1 = class(TForm)
Chart1: TChart;
Series1: TPointSeries;
Button1: TButton;
OpenDialog1: TOpenDialog;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
i: integer;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
type point = record
x,y: double;
index: integer;
cluster: integer;
end;
type dist = record
d: double;
i: integer;
end;
var f: textfile;
x,y: double;
arr: array of point;
z1,z2,z1old,z2old: point;
i,j,k1,k2,a:integer;
d1,d2: array of dist;
label next;
Procedure find(x,y:double;n: integer; var k: integer);
var i: integer;
begin
k:=9999;
for i:=0 to n do
if ((Chart1.SeriesList[0].XValue[i]=x) and (Chart1.SeriesList[0].yValue[i]=y)) then begin
k:=i; break; end;
end;
begin
OpenDialog1.execute;
if OpenDialog1.FileName<>'' then
begin
// read file
assignfile(f,OpenDialog1.filename);
reset(f);
Chart1.SeriesList[0].Clear;
setlength(arr,0);
i:=0;
while not(eof(f)) do begin
readln(f,x,y);
Chart1.SeriesList[0].AddXY(x,y);
setlength(arr,length(arr)+1);
arr[high(arr)].x:=x;
arr[high(arr)].y:=y;
arr[high(arr)].index:=i;
arr[high(arr)].cluster:=0;
inc(i);
end;
closefile(f);
// calculate here
setlength(d1,Length(arr));
setlength(d2,Length(arr));
z1:=arr[0];
z2:=arr[1];
next:
z1old:=z1;
z2old:=z2;
//Chart1.SeriesList[0].ValueColor[0]:=clYellow;
for i:=0 to high(arr) do
begin d1[i].d:=sqrt(sqr(z1.x-arr[i].x) + sqr(z1.y-arr[i].y));
d1[i].i:=arr[i].index;
end;
for i:=0 to high(arr) do
begin d2[i].d:=sqrt(sqr(z2.x-arr[i].x) + sqr(z2.y-arr[i].y));
d2[i].i:=arr[i].index;
end;
k1:=0; k2:=0;
for i:=0 to high(arr) do
begin
if d1[i].d<d2[i].d then
begin
arr[i].cluster:=1; k1:=k1+1;
end else
begin
arr[i].cluster:=2; k2:=k2+1;
end;
end;
z1.x:=0;z1.y:=0;z2.x:=0;z2.y:=0;
for i:=0 to high(arr) do
begin
if arr[i].cluster=1 then
begin
z1.x:=z1.x+arr[i].x;
z1.y:=z1.y+arr[i].y;
end
else begin
z2.x:=z2.x+arr[i].x;
z2.y:=z2.y+arr[i].y;
end;
end;
z1.x:=z1.x/k1;
z1.y:=z1.y/k1;
z2.x:=z2.x/k2;
z2.y:=z2.y/k2;
if ((z1.x<>z1old.x) or (z2.x<>z2old.x)or (z1.y<>z1old.y)or (z2.y<>z2old.y)) then
begin
z1old:=z1;
z2old:=z2;
goto next;
end;
for i:=0 to high(arr) do
begin
find(arr[i].x,arr[i].y,length(arr),a);
if arr[i].cluster=1 then Chart1.SeriesList[0].ValueColor[a]:=clYellow
else Chart1.SeriesList[0].ValueColor[a]:=clBlue;
end;
Chart1.SeriesList[0].AddXY(z1.x,z1.y);
find(z1.x,z1.y,length(arr)+1,a);
Chart1.SeriesList[0].ValueColor[a]:=clGreen;
Chart1.SeriesList[0].AddXY(z2.x,z2.y);
find(z2.x,z2.y,length(arr)+2,a);
Chart1.SeriesList[0].ValueColor[a]:=clGreen;
end;
end;
end.
Результати роботи програми :
5 |
5 |
6 |
6 |
7 |
7 |
8 |
8 |
7 |
15 |
8 |
15 |
9 |
15 |
10 |
15 |
11 |
15 |
14 |
2 |
15 |
3 |
16 |
4 |
Висновок: В даній лабораторній роботі ми розглянули роботу алгоритму розпізнавання образів та розбили на 2 кластери множину точок на площині за індивідуальним завданням.
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, TeEngine, Series, ExtCtrls, TeeProcs, Chart;
type
TForm1 = class(TForm)
Chart1: TChart;
Series1: TPointSeries;
Button1: TButton;
OpenDialog1: TOpenDialog;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
i: integer;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
type point = record
x,y: double;
index: integer;
cluster: integer;
end;
type dist = record
d: double;
i: integer;
end;
var f: textfile;
x,y: double;
arr: array of point;
z1,z2,z1old,z2old: point;
i,j,k1,k2,a:integer;
d1,d2: array of dist;
label next;
Procedure find(x,y:double;n: integer; var k: integer);
var i: integer;
begin
k:=9999;
for i:=0 to n do
if ((Chart1.SeriesList[0].XValue[i]=x) and (Chart1.SeriesList[0].yValue[i]=y)) then begin
k:=i; break; end;
end;
begin
OpenDialog1.execute;
if OpenDialog1.FileName<>'' then
begin
// read file
assignfile(f,OpenDialog1.filename);
reset(f);
Chart1.SeriesList[0].Clear;
setlength(arr,0);
i:=0;
while not(eof(f)) do begin
readln(f,x,y);
Chart1.SeriesList[0].AddXY(x,y);
setlength(arr,length(arr)+1);
arr[high(arr)].x:=x;
arr[high(arr)].y:=y;
arr[high(arr)].index:=i;
arr[high(arr)].cluster:=0;
inc(i);
end;
closefile(f);
// calculate here
setlength(d1,Length(arr));
setlength(d2,Length(arr));
z1:=arr[0];
z2:=arr[1];
next:
z1old:=z1;
z2old:=z2;
//Chart1.SeriesList[0].ValueColor[0]:=clYellow;
for i:=0 to high(arr) do
begin d1[i].d:=sqrt(sqr(z1.x-arr[i].x) + sqr(z1.y-arr[i].y));
d1[i].i:=arr[i].index;
end;
for i:=0 to high(arr) do
begin d2[i].d:=sqrt(sqr(z2.x-arr[i].x) + sqr(z2.y-arr[i].y));
d2[i].i:=arr[i].index;
end;
k1:=0; k2:=0;
for i:=0 to high(arr) do
begin
if d1[i].d<d2[i].d then
begin
arr[i].cluster:=1; k1:=k1+1;
end else
begin
arr[i].cluster:=2; k2:=k2+1;
end;
end;
z1.x:=0;z1.y:=0;z2.x:=0;z2.y:=0;
for i:=0 to high(arr) do
begin
if arr[i].cluster=1 then
begin
z1.x:=z1.x+arr[i].x;
z1.y:=z1.y+arr[i].y;
end
else begin
z2.x:=z2.x+arr[i].x;
z2.y:=z2.y+arr[i].y;
end;
end;
z1.x:=z1.x/k1;
z1.y:=z1.y/k1;
z2.x:=z2.x/k2;
z2.y:=z2.y/k2;
if ((z1.x<>z1old.x) or (z2.x<>z2old.x)or (z1.y<>z1old.y)or (z2.y<>z2old.y)) then
begin
z1old:=z1;
z2old:=z2;
goto next;
end;
for i:=0 to high(arr) do
begin
find(arr[i].x,arr[i].y,length(arr),a);
if arr[i].cluster=1 then Chart1.SeriesList[0].ValueColor[a]:=clYellow
else Chart1.SeriesList[0].ValueColor[a]:=clBlue;
end;
Chart1.SeriesList[0].AddXY(z1.x,z1.y);
find(z1.x,z1.y,length(arr)+1,a);
Chart1.SeriesList[0].ValueColor[a]:=clGreen;
Chart1.SeriesList[0].AddXY(z2.x,z2.y);
find(z2.x,z2.y,length(arr)+2,a);
Chart1.SeriesList[0].ValueColor[a]:=clGreen;
end;
end;
end.