Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

ІНДИВІДУАЛЬНЕ ЗАВДАННЯ



ЛЬВІВ 2013

Мета роботи

Ознайомитись із поняттям кластеризації. Навчитись застосовувати методи розпізнавання образів, зокрема такі як :

1) алгоритм порогової величини;

2) максимінного алгоритму;

3) алгоритм К-внутрішніх групових середніх.

А також навчитись застосовувати їх на практиці при складанні програм.

 

Короткі теоретичні відомості

Основним завданням процесу кластеризації є розподіл заданої множини образів на класи (кластери), котрі дають змогу досліджувати подібність і відмінність між образами в класах і робити обґрунтовані висновки про кластерні образи в кластерах.

На етапі вибору алгоритму кластеризації здійснюється вибір одного із алгоритмів, котрі містяться у бібліотеці алгоритмів кластеризації. Цей етап передбачає вибір міри подібності образів у кластері та критеріїв кластеризації.

Бібліотека алгоритмів містить відомий алгоритм порогової величини .

Цей алгоритм полягає у обчисленні кластерів для кожної точки образу заданої множини .Відтак обчислюють кількості точок образів у кожній області кластеризації і за перший

кластер приймають область з максимальною кількістю точок образів. Ця множина точок

вилучається з подальшого розглядуце роблять доти, доки не отримаємо пусту множину точок образів. Очевидно, що цей алгоритм має найвищу складність серед усіх алгоритмів бібліотеки.

Основним недоліком алгоритму є те, що він вимагає задання порогової величини Т і результат його роботи залежить від вибору початкової точки – першого центра кластера.

Максимінний алгоритм використовує евклiдову вiдстань. Один з об'єктiв (X1) довiльним чином назначається центром першого кластера. Потiм вiдшукується образ, розмiщений вiд образа X1 найдалi, який призначається центром кластера Z2. На третьому кроцi алгоритму здiйснюється обчислення вiдстаней мiж всiма iншими образами вибiрки i центрами кластерiв Z1 i Z2. В кожнiй парi цих вибірок вибирається мiнiмальне. Пiсля цього видiляється максимальне з цих мiнiмальних вiдстаней. Якщо останнє складає значну частину вiдстанi мiж кластерами Z1 i Z2 (половина цiєї вiдстанi), вiдповiдний образ призначається центром кластера Z3. Iнакше - виконання алгоритму припиняється. В загальному випадку описана процедура повторюється до тих пiр, поки на якомусь кроцi не буде отримане максимальне значення вiдстанi, для якої умова, що викликає видiлення кластера, не виконується.

Для алгоритму К-середніх вибираються центри кластерiв Z1(1), Z2(1),...,Zk(1).

Потім на 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льним чином.

Потім на основi результатів кроку 2 визначаються новi центри кластерiв Zj(k+1), j=1,2,...,k, які вибираються таким чином, щоб мiнiмiзувати показник якостi.

Центр Zj(k+1), що забезпечує мiнiмiзацiю показника якостi, є, по сутi, вибiрковим середнiм, визначеним по множинi Sj(k).

Рiвнiсть Zj(k+1) при j=1,2,...,k є умовою збiжностi алгоритму, i при її досягненнi виконання алгоритму припиняється. Інакше процедура повторюється.

Практичне застосування алгоритму вимагає проведення експериментiв, пов'язаних iз вибором рiзних значень параметра k i початковим розмiщенням центрiв кластерів.

ІНДИВІДУАЛЬНЕ ЗАВДАННЯ

Варіант 14

 

Значення: Х1(1,1), Х2(1,2), Х3(4,5), Х4(4,6), Х5(12,13), Х6(12,14) , Х7(7,8), Х8(6,8), Х9(7,5), Х10(0,1).

 

Здійснити розпізнавання образів із застосуванням:

a) алгоритму порогової величини, Т=2;

b) максимінного алгоритму;

c) алгоритму К-внутрішніх групових середніх, K=3.

 

 

Код програми розпізнавання образів алгоритмом порогової величини Т=2

 

#include <iostream>

#include <math.h>

using namespace std;

 

struct point

{

float x;

float y;

int center;

int naleg;

};

 

float vids (point a, point b) {

float len=0;

len=sqrt(pow((a.x-b.x),2)+pow((a.y-b.y),2));

return len;

}

 

int main ()

{

int n=0;

float T=2;

cout<<"T= "<<T<<endl;

cout<<" n=10 "<<endl;

n=10;

n--;

point mas[n];

for (int i=0; i<=n; i++)

{

mas[i].center=mas[i].naleg=mas[i].x=mas[i].y=0;

}

 

mas[0].x=1.0; mas[0].y=1.0;

mas[1].x=1.0; mas[1].y=2.0;

mas[2].x=4.0; mas[2].y=5.0;

mas[3].x=4.0; mas[3].y=6.0;

mas[4].x=12.0; mas[4].y=13.0;

mas[5].x=12.0; mas[5].y=14.0;

mas[6].x=7.0; mas[6].y=8.0;

mas[7].x=6.0; mas[7].y=8.0;

mas[8].x=7.0; mas[8].y=5.0;

mas[9].x=0.0; mas[9].y=1.0;

 

 

//Print array

cout<<"Array: "<<endl;

cout<<"[N] [x:y]"<<endl;

for(int i=0; i<=n; i++)

{

cout<<"["<<i<<"] ["<<mas[i].x<<":"<<mas[i].y<<"]"<<endl;

}

 

int nofc=-1;

int masofc[n];

for(int i=0; i<=n; i++)

{

masofc[i]=0;

}

//pruznachennya 1 centa

mas[0].center=1;

mas[0].naleg=1;

nofc++;

masofc[nofc]=1;

float maslen[n][n];

for (int i=0; i<=n; i++)

{

for (int j=0; j<=nofc; j++)

{

maslen[i][j]=vids(mas[i],mas[masofc[j]]);

}

float minlen=maslen[i][0];

int minp=0;

for (int j=0; j<=nofc; j++ )

{

if (maslen[i][j]<minlen)

{

minlen=maslen[i][j];

minp=j;

}

}

if (minlen<=T)

{

mas[i].naleg=masofc[minp];

}

if (minlen>T)

{

nofc++;

masofc[nofc]=i;

mas[i].center=i;

mas[i].naleg=i;

}

}

cout<<"Rezultal: "<<endl;

cout<<"[N] [x:y] [c] [n]"<<endl;

for (int i=0; i<=n; i++)

{

cout<<"["<<i<<"] ["<<mas[i].x<<":"<<mas[i].y<<"] ["<<mas[i].center<<"] ["<<mas[i].naleg<<"]"<<endl;

}

cout<<"Program Done!"<<endl;

return 0;

}

 

Результат виконання:

 

 

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.