S.l. dr. ing. Andrei -Horia Mogoș [602043]

Licență

S.l. dr. ing. Andrei -Horia Mogoș [602043]

Byadmin ianuarie 1, 2024

UNIVERSITATEA POLITEHNICA BUCUREȘTI
FACULTATEA DE AUTOMATICĂ ȘI CALCULATOARE
DEPARTAMENTUL CALCULATOARE

PROIECT DE DIPLOMĂ

Algoritmi de inteligență a roiurilor
pentru probleme de cl asificare

Coordonator științific:
S.l. dr. ing. Andrei -Horia Mogoș

Absolvent: [anonimizat]
2015

Abstract

Algoritmii de inteligență a roiurilor (swarm intelligence) au fost modificați recent pentru a
putea rezolva problemele de clusterizare pe date. Acești algoritmi realizează cu succes clusterizarea
pe date, obținând rezultate mai bune decât algoritmii clasic i de clusterizare. În această lucrare vor fi
utilizați algoritmul Particle Swarm Optimization (PSO) și algoritmul Cat Swarm Optimization (CSO)
împreună cu variantele modificate ale acestora, prin adăugarea unei ponderi de inerție sau a unui
factor de comp rimare la algoritmii standard. Pe lângă acești algoritmi, va mai fi utilizat si un algoritm
clasic de clusterizare, k -means, pentru a compara performanțele algoritmilor clasici cu
performanțele algoritmilor de inteligență a roiurilor. Pentru a realiza mai ușor comparațiile, se va
utiliza un framework, implementat în C++.

Cuprins

1. Introducere ………………………….. ………………………….. ………………………….. ………………………… 1
2. Problema de clusterizare pe date ………………………….. ………………………….. …………………………. 2
2.1. Descrierea problemei de clusterizare pe date ………………………….. ………………………….. ……. 2
2.2. Descrierea altor abordări pentru rezolvarea problemei de clusterizare pe date …………………. 3
3. Algoritmi utilizați ………………………….. ………………………….. ………………………….. …………………. 7
3.1. Algoritmul Particle Swarm Optimization (PSO) ………………………….. ………………………….. ….. 7
3.2. Algoritmul Cat Swarm Optimi zation (CSO) ………………………….. ………………………….. ………… 8
3.3. Algoritmul K -means ………………………….. ………………………….. ………………………….. ………. 10
3.4. Indici de validare a clusterizării ………………………….. ………………………….. …………………….. 10
4. Descrierea sistemului ………………………….. ………………………….. ………………………….. ………….. 12
4.1. Arhitectura sistemului ………………………….. ………………………….. ………………………….. …… 12
4.1.1. Descrierea modulelor aplicației ………………………….. ………………………….. ………………. 12
4.2. Pseudocod module ………………………….. ………………………….. ………………………….. ……….. 15
4.2.1. Metoda Draw() ………………………….. ………………………….. ………………………….. ………. 15
4.2.2. Metoda Key() ………………………….. ………………………….. ………………………….. …………. 15
4.2.3. Metoda Mouse() ………………………….. ………………………….. ………………………….. …….. 16
4.2.3.1. Metoda Generate() ………………………….. ………………………….. ………………………….. .. 16
4.2.3.1. Metoda Compare() ………………………….. ………………………….. ………………………….. .. 17
5. Implementarea sistemului ………………………….. ………………………….. ………………………….. ……. 18
5.1. Descrierea claselor ………………………….. ………………………….. ………………………….. ……….. 18
5.2. Interfața grafică ………………………….. ………………………….. ………………………….. ……………. 20
6. Rezultate experimentale ………………………….. ………………………….. ………………………….. ……… 27
6.1. Set de date cu clustere bine separate ………………………….. ………………………….. ……………. 27
6.2. Set de date cu un cluster bine separat și două clustere apropiate ………………………….. …….. 28
6.3. Set de date cu clustere mari, dar înguste, poziționate circular ………………………….. …………. 29
6.4. Set de date cu clustere apropiate ………………………….. ………………………….. …………………. 30
6.5. Set de date cu clustere pătrate sau dreptunghiulare ………………………….. ……………………… 31
6.6. Set de date cu clustere cu forme neregulate ………………………….. ………………………….. …… 32
6.7. Set de date ce conține cinci clustere ………………………….. ………………………….. ……………… 33
6.8. Set de date ce conține șapte clustere ………………………….. ………………………….. …………….. 34
6.9. Rezultate obținute ………………………….. ………………………….. ………………………….. ………… 35
7. Concluzii și dezvoltări ulterioare ………………………….. ………………………….. ………………………… 40
Bibliografie ………………………….. ………………………….. ………………………….. ………………………….. . 41

1
1. Introducere

În această lucrare, vor fi studiați doi algoritmi de inteligență a roiurilor și algoritmul de
clusterizare k -means. Cei doi algoritmi sunt: Particle Swarm Optimization (PSO) și Cat Swarm
Optimization (CSO). Se vor studia performanțele acestor algoritmi pen tru diferite teste și vor fi
comparate cu performanțele variantelor modificate ale acestor algoritmi. Variantele modificate
constau în adăugarea unei ponderi de inerție sau a unui factor de comprimare pentru a crește viteza
de convergență.
Pentru a studia și compara mai ușor acești algoritmi, se va implementa un framework de
utiliza re. În acest framework va exista posibilitatea de a genera un set de date nou pe baza unor
parametri , de a genera grafice cu evoluția algoritmilor pe anumite teste și de a genera tabele cu
rezultatele rulărilor. Framework -ul va oferi și posibilitatea de a rula algoritmii pas cu pas pentru a
urmări procesul de clusterizare.
Clusterizarea pe date este un proces de împărțire a unui set de înregistrări în mai multe
subseturi, numite clustere, în așa fel încât înregistrările din același cluster să fie asemănătoare, dar
diferite de înregistrările din alte clustere [2]. Acest proces va fi realizat de algoritmii menționați mai
sus. Pentru a verifica corectitudinea clusterizării, se vor folosi doi indici de validare. Acești indici vor
înlocui funcțiile de fitness din algoritmii standard PSO și CSO.
Algoritmul PSO a fost de zvoltat de Kennedy și Eberhart în 1995, fiind bazat pe
comportamentul în natură al bancurilor de pești și al stolurilor de păsări. Mulți algoritmi , precum Ant
Colony Optimization (ACO) și Virtual Ant folos esc comportamentul așa -numitei inteligență a roiurilor .
PSO poate avea câteva asemănări cu algoritmii genetici sau algoritmii ACO, dar este mult mai simplu,
deoarece nu folosește operatori de mutație, operatori de recombinare sau feromoni. În schimb,
folosește comunicarea globală dintre particulele roiului și numere reale aleatoare. [9]
Algoritmul CSO a fost dezvoltat de Shu -Chuan Chu și Pei -wei Tsai, fiind bazat pe
comportamentul pisicilor. Pisicile domestice manifestă o curiozitate puternică pentru obiectele în
mișcare. Deși toate pisicile manifestă această curiozit ate puternică, petrec cel mai mult din timpul
lor relaxându -se, chiar și atunci când nu dorm. Pisicile au un grad foarte ridicat de vigilență. Acestea
sunt vigilente chiar și atunci când se relaxează. Pisicile par a fi leneșe, dar dacă sunt examinate mai
amănunțit, se va observa că stau cu ochii larg deschiși, observând mediul înconjurător. Acestea sunt
ființe foarte deștepte și prudente. [12]
CSO modelează cele două comportamente ale pisicilor în două moduri: modul de căutare și
modul de urmărire. Modul de căutare este utilizat pentru a modela pisicile în timp ce acestea se
relaxează, fiind vigilente, analizând mediul înconjurător pentru următoarea mutare. Modul de
urmărire este folosit pentru a modela cazurile în care pisicile urmăresc țintele. Prin c ombin area
acestor două moduri , CSO se poate ocupa de problema de optimizare . [12]
Algoritmul K -means este un algoritm de clusterizare simplu, care încearcă să găsească k
clustere care nu se suprapun. Acest algoritm generează la pasul inițial un număr de centroi zi, poziția
acestora fiind aleato are. Un centroid își modifică poziția în funcție de punctele asociate acestuia,
calculând media acestora. Algoritmul se oprește atunci când niciun centroid nu își mai modifică
poziția.
Problema de clusterizare pe date și alte abordări în rezolvarea problemei de clusterizare vor
fi descrise în Capitolul 2, iar algoritmii utilizați și indicii folosiți pentru validarea clusterizării vor fi
prezentați în capitolul 3. Modulele aplicației și p seudocodul pentru câteva dintre acestea vor fi
descrise în Capitolul 4 , iar în Capitolul 5 vor fi descri se pe scurt clasele cu relațiile dintre acestea și
interfața grafică a aplicației. Seturile de date folosite în realizarea comparațiil or și rezultatele
obținute pe acestea vor fi descrise în Capitolul 6, după care, în Capitolul 7 se vor trage concluziile pe
baza rezultatelor obținute și se vor preciza dezvoltările ulterioare.

2
2. Problem a de cluster izare pe date

În acest capitol sunt descrise procesul de clusterizare pe date, etapele acestuia și alte
abordări pentru rezolv area problemei de clusterizare. În prima parte din acest capitol este descrisă
problema de clusterizare pe date și sunt prezentate pe scurt câteva aplicații ale clusterizării, iar în a
doua parte, sunt descrise câteva abordări pentru rezolvarea acestei probleme, diferite de cele
utilizate în această aplicație. Pe lângă aceste abordări, mai sunt descriși câțiva algoritmi de
inteligență a roiurilor , modificați recent pentru a putea rezolva problema de clusterizare pe date.

2.1. Descrierea problemei de clusteri zare pe date

Clusterizarea este un tip de clasificare , efectuată pe un set finit de obiecte. Relația dintre
obiecte este reprezentată într -o matrice de proximitate în care rândurile și coloanele corespund
obiectelor. Dac ă obiectele sunt caracterizate ca șabloane sau puncte într -un spațiu metric
multidimensional, proximitățile pot fi distanțe dintre perechi de puncte, cum ar fi distanța
euclidiană. Dacă o măsură semnificativă a distanței dintre perechi de obiecte nu a fost stabilită, nicio
analiză semnificativă a clusterului nu este posibilă. Matricea de proximitate este singura intrare într –
un algoritm de clusterizare. [1]
Clusterizarea pe date este un proces de împărțire a unui set de înregistrări în mai multe
subseturi, numite clustere , în așa fel încât înregistrările din același cluster să fie asemănătoare, dar
diferite de înregistrările din alte clustere. O înregistrare poate fi un punct de date, un mo del, un
obiect, un individ, un element sau un tuplu. Într-un spațiu multidimensional, o înregistrare este
caracterizată printr -un set de atribute , variabile sau feature -uri. Un proces de clusterizare implic ă
următorii pa și: reprezentarea șablonului, definirea măsurii de disimilaritate, clusterizarea,
abstractizarea datelor și evaluarea rezultatului. [2]
În pasul de reprezentare a șablonului se determină numărul și tipul atributelor. Dacă este
necesar, se execută două proces e: selecție caracteristică și extracție caracteristică . Selecția
caracteristică presupune identificarea celui mai eficient subset din setul original de atribute pentru a
fi utilizat în clusterizare . Extracția caracteristică presupune transformare a atribute lor originale în
atribute noi. [2]
În pasul de definire a măsurii de disimilaritate se va defini o metodă de măsurare a distanței ,
apropiat ă de domeniul datelor. Au fost dezvoltate diverse metode de m ăsurare a distanței , cea mai
cunoscut ă fiind distan ța euclidian ă[2]. În această lucrare se vor folosi doi indici de validare a
clusterizării ca metode de măsurare : Dunn și Davies Bouldin . Indicii de validare sunt folosiți pentru a
măsura rezultatul clusterizării. Aceștia sunt potriviți pentru măsurarea cluster elor liniar
separabile [3]. Două clustere sunt liniar separabile dacă pot fi separate printr -o linie dreapta .
Clusterizarea presupune utilizarea unui algoritm pentru a grupa un set de înregistrări într -un
număr semnificativ de clustere. Aceasta poat e fi dură, unde o înregistrare aparține unui singur
cluster, sau neclar ă, unde o înregistrare poate să aparțină de două sau mai multe clustere cu o
anumită probabilitate. Algoritmii de clusterizare pot fi ierarhici, unde sunt produse o serie de
partiționăr i, sau de partiționare, unde se identifică o singură partiționare . [2]
Abstractizarea datelor este un proces simplu și compact de reprezentare a unui set de date.
Simplitatea este dată din perspectiva analizei automate , astfel încât o mașină să poată efectua
procese ulterioare eficient, sau este orientată pe capacitățile umane pentru o înțelegere mai ușoară
și intuitivă a reprezentării obținute. În procesul de clusterizare, o abstractizare de date reprezintă o
descriere compactă a fiecărui cluster, de obicei în termeni de prototipuri de clustere sau șabloane
reprezentative, cum ar fi centroizii. [4]
În pasul final se evaluează rezulta tul algoritmului de clusterizare . Există trei tipuri de
evalu ări: externe, interne și relative. În evalu ările externe, structura de date obținută este
comparat ă cu o structur ă anterioară . În evaluarea intern ă, se încearc ă să se determine dac ă

3
structura es te intrinsec apropiat ă de date. În evaluarea relativă, un test este efectuat pentru a
compara dou ă structuri și a m ăsura meritele lor relative . [2]
Clusterizarea oferă foarte multe avantaje asupra unui proces manual de grupare. Un
program de clusterizare poate aplica un anumit criteriu pentru a forma grupurile. Oamen ii găsesc
ușor clusterele în două și câteodată în trei dimensiuni, dar nu sunt identificate întotdeauna aceleași
clustere în setul de date de persoane diferite, în special atunci când cl usterele nu sunt bine separate.
Un algoritm de clusterizare pe date es te rapid, fiabil și consistent. Acesta poate forma clustere într –
un timp mult mai scurt decât în cazul unei clusterizări manuale, mai ales dacă fiecare obiect are
asociată o listă lungă de descriptori sau feature -uri. [1]
Clusterizarea este utilă, de aseme nea, și în implementarea strategiei „divide și cucerește”
prin reducerea complexității computaționale pentru diverși algoritmi de decizie cu recunoaștere a
șabloanelor. De exemplu, regula de decizie pentru cel mai apropiat vecin este o tehnica populară în
recunoașterea șabloanelor. Totuși, găsirea celui mai apropiat vecin al unui șablon de test poate dura
foarte mult dacă numărul de șabloane de antrenare sau prototipuri este foarte mare. Fukunaga și
Narendra au utilizat un algoritm de clusterizare prin par tiționare, ISODATA, pentru a descompune
șabloanele și apoi, folosind metoda de ramificare și limitare au obținut un algoritm eficient de
calculare a celui mai apropiat vecin. Similar, Fukunaga și Short au utilizat clusterizarea pentru
problema localizării, unde o simplă regulă de decizie poate fi implementată în regiuni locale sau în
clustere din spațiul șabloanelor. Aplicațiile clusterizării sunt din ce în ce mai multe. [1]
Clusterizarea este una din cele mai folosite tehnici în aplicațiile multimedia. Clusterizarea
multimedia reprezintă un domeniu larg și interesant de cercetare care are de -a face cu clustere din
diferite spații și cu diferite nivele de granularitate. În c ontrast cu abordările convenționale de
clusteri zare care se ocupa cu simpla genera re și atribuire de documente clusterelor, clusterizarea
multimedia depășește cu mult aceste abordări. În domeniul multimedia, clusterizările de nivele și
spații diferite pot fi semnificative și se pot completa una pe cealaltă pentru a forma o interpretare
mai consistentă și robustă și a înțelege documentele multimedia. [4]
Aplicațiile multimedia variază de la construcția vocabularelor vizuale ca o procedura de
procesare a datelor multimedia până la structurare a video automată și sumarizarea conținutului
imaginilor. Din cauza rolului vital în multe aplicații, metodele de clusterizare au fost studiate pe scară
largă în diferite nivele de granularitate, de la nivele scăzute de feature -uri până la nivele ridicate de
concepte. Reprezintă o problemă provocatoare d in moment ce datele multimedia sunt pe scară
largă, în dimensiuni su perioare, multimodale și chiar cu zgomot și sunt prezente în multe aplicații
multimedia. [4]

2.2. Descrierea altor abordări pentru rezolvarea problemei de clusterizare pe date

S-au dezvoltat mai mulți algoritmi pentru rezolvarea problemei de clusterizare. Aceștia au
fost grupați în 2 categorii: algoritmi ierarhici și algoritmi de partiționare. Algoritmii de clusterizare
ierarhici divid un set de date într -o secvență de clustere imbri cate. Aceștia pot fi clasificați mai
departe în două categorii: aglomerativi și divizivi. Algoritmii de clusterizare prin partiționare divid un
set de date într -o singură partiție. Aceștia pot fi clasificați mai departe în algoritmi de clusterizare
duri și algoritmi de clusterizare neclari. [2]
Algoritmii ierarhici aglomerativi construiesc inițial o matrice de disimilaritate, folosind o
anumită măsură de proximitate, iar toate punctele de date sunt reprezentate la baza dedrogramei (o
structura de date bazată pe arbori binari). Cele mai apropiate seturi de clustere sunt unite la fiecare
nivel, actualizându -se corespunzător matricea de disimilaritate. Acest proces de unire aglomerativă
se repetă până când se obține un singur cluster ce conține toate punc tele de date. [5] Aceștia se
împart în algoritmi cu legătură simplă, algoritmi cu legătură completă, algoritmi bazați pe media
grupului, algoritmii lui Ward, algoritmi bazați pe centroizi și algoritmi mediani [2].

4
Spre deosebire de algoritmii de clusterizar e aglomerativi, cei divizivi construiesc inițial un
cluster rădăcină ce conține toate punctele de date și îl împarte recursiv pentru a construi
dendrograma. Această metodă este mai eficientă decât clusterizarea aglomerativă în special atunci
când nu este n ecesar să se genereze o ierarhie completă până la nodurile frunză. Poate fi
considerată ca fiind o abordare globală din moment ce conține informații complete înainte să
înceapă împărțirea datelor. Algoritmii de clusterizare divizivi se împart în algoritmi monotetici și
algoritmi politetici. [5]
Algoritmii de clusterizare prin partiționare divid un set de date într -o singură partiție. Aceștia
pot fi clasificați mai departe în algoritmi de clusterizare duri și algoritmi de clusterizare neclari
(fuzzy). În alg oritmii de clusterizare duri, fiecare înregistrare corespunde unui singur cluster. În
algoritmii de clusterizare neclari, o înregistrare are o probabilitate de apariție în două sau mai multe
clustere. În continuare vor fi prezentate pe scurt câteva tipuri de algoritmi de partiționare. [2]
Algoritmii de clusterizare bazați pe centre utilizează un centru pentru a reprezenta un
cluster. Aceștia au două proprietăți importante: au o funcție obiectiv clar definită și au costul de
rulare redus. Algoritmul standard k-means este un algoritm de clusterizare bazat pe centre și este de
asemenea cel mai popular și simplu algoritm de clusterizare. Acest algoritm minimizează funcția
obiectiv folosind un proces iterativ. [2]
Algoritmii de clusterizare bazați pe căutare au fo st dezvoltați, deoarece majoritatea
algoritmilor de c lusterizare se opresc atunci când găsesc o partiționare optimă locală a setului de
date. De exemplu, algoritmul k -means este convergent, dar se poate opri la un minim local al
problemei de optimizare. Al goritmii de clusterizare bazați pe căutare sunt folosiți pentru a căuta
partiționarea optimă globală a unui set de date prin explorarea spațiului soluției care stă la baza
problemei de optimizare. [2]
Algoritmii de clusterizare bazați pe grafic reprezintă punctele de date sau înregistrările sub
formă de grafic. Un grafic este o colecție de vârfuri și laturi. Un vârf reprezi ntă un punct de date sau
o înregistrare, iar o latură ce unește două vârfuri reprezintă similaritatea dintre două înregistr ări
reprezent ate de cele două vârfuri. Un cluster, în general, corespunde unui subgraf foarte bine
conectat. [2]
Algoritmii de clusterizare bazați pe grid sunt foarte eficienți pentru clusterizarea seturilor
foarte mari de date, din moment ce acești algoritmi efectueaz ă clusterizarea pe celulele grid -ului în
loc de puncte de date individuale. Un algoritm tipic bazat pe grid constă în următorii pași:
construirea structurii unui grid prin divizarea spațiului de date într -un număr finit de celule,
calcularea densității pen tru fiecare celulă, sortarea celulelor pe baza intensității acestora,
identificarea centrelor clusterelor și traversarea celulelor vecine. [4]
Algoritmii de clusterizare bazați pe densitate sunt capabili să găsească clustere cu forme
arbitrare. În acești a lgoritmi, un cluster este definit ca o regiune densă înconjurată de regiuni cu
densitate redusă. De obicei, algoritmii bazați pe densitate nu necesită specificarea numărului de
clustere din moment ce acești algoritmi pot să detecteze automat clusterele și numărul de clustere.
Un dezavantaj al majorității algoritmilor bazați pe densitate este dificultatea determinării anumitor
parametri , cum ar fi pragul de densitate. [4]
Algoritmii de clusterizare bazați pe modele sunt algoritmii bazați pe șabloane de
proba bilitate. Termenul de model se referă, de obicei, la tipul de constrângeri și la proprietățile
geometrice ale covarianțelor matricelor. În clusterizarea bazată pe model, datele sunt văzute ca
exemple venind de la un amestec de probabilități de distribuție, fiecare dintre acestea reprezentând
un cluster. Acești algoritmi folosesc două abordări pentru un model de compunere a clusterelor:
abordarea probabilității de clasificare și abordarea probabilității de amestec. [4]
Algoritmii de clusterizare a subspațiil or sunt capabili să găsească clustere încorporate în
subspațiile setului original de date. Cei mai mulți algoritmi de clusterizare a subspațiilor sunt
clasificați în două categorii majore: de sus în jos (top -down) și de jos în sus (bottom -up). În algoritmi i
de clusterizare top -down, o clusterizare convențională este efectuată, iar apoi subspațiile fiecărui
cluster sunt evaluate. Exemplu de algoritmi top -down: PART, PROCLUS, ORCLUS, FINDIT. În algoritmii

5
de clusterizare bottom -up sunt identificate regiunile dense din spațiile dimensionale , apoi aceste
regiuni sunt combinate pentru a forma un cluster. Exemplu de algoritmi bottom -up: CLIQUE,
ENCLUS, MAVIA, CLTree, DOC, CBF. Există și algoritmi care nu se găsesc în niciuna din categoriile
menționate mai sus: FSC, SUBSCAD, MSSC. [2]
Algoritmii de clusterizare bazați pe rețele neurale sunt legați de conceptul de învățare
competitivă. Există două tipuri de paradigme de învățare competitivă: învățare competitivă dură și
învățare competitivă slabă. Învățarea compet itivă dură mai este cunoscută și ca învingătorul ia tot
sau învățare competitivă aspră. În învățarea competitivă dură, doar unui anumit neuron câștigător,
care se potrivește cel mai bine cu șablonul dat la intrare, îi este permis să învețe. În învățarea
competitivă slabă, toți neuronii au oportunitatea de a învăța bazându -se pe șablonul dat la intrare.
Prin urmare, învățarea competitivă slabă mai este cunoscută și ca învingătorul ia cel mai mult. [2]
Un algoritm de clusterizare neclar (fuzzy) generează o pa rtiție neclară pentru a furniza gradul
de membru pentru fiecare obiect dintr -un cluster dat. O abordare a algoritmilor de clusterizare
neclari este mai puțin înclinată către minimul local decât algoritmii de clusterizare duri (crisp), din
moment ce ia deci zii ușoare în fiecare iterație pr in folosirea funcțiilor membru. [5] Algoritmii de
clusterizare neclari (fuzzy) permit unei înregistrări sa aparțină de două sau mai multe clustere cu o
anumită probabilitate * 2].
În această lucrare sunt ut ilizați doi algorit mi de inteligență a roiurilor pentru rezolvarea
problemei de clusterizare și algoritmul k-means ca algoritm de comparație. Cei doi algoritmi sunt
Particle Swarm Optimization și Cat Swarm Optimization . Pe lângă acești algoritmi au mai fost
modificați recent și alți algoritmi de inteligență a roiurilor pentru rezolvarea problemei de
clusterizare. Printre acești algoritmi se numără Ant Colony Optimization (ACO) , Bee Colony
Optimization (BCO) și Bacterial Evolutionary Algorithm (BEA) .
Algoritmii de clusterizare bazați pe furnici (Ant -based) sunt inspirați din comportamentul
biologic al furnicilor. Furnicile aparțin unei categorii sociale, ceea ce înseam nă că furnicile sunt
capabile s ă supravie țuiască pe cont propriu. Coloniile de furnici pot manifesta o coordona re
remarcabilă între indivizi. C ând furnicile caută mâncare, se deplasează inițial aleator pentru a căuta
în vecinătatea locală. Cât timp acestea se deplasează, lasă în urma lor o substanță chimică numită
feromon. Această substanță este percepută de celela lte furnici, ajutându -le să ia decizii pentru
următoarea mutare. Cantitatea de feromon lăsată este proporțională cu numărul de furnici care au
folosit acea rută. Comunicarea dintre agenți în timpul procesului de căutare este indirect ă,
comunicând indirect prin modificarea mediului cu care se confruntă fiecare agent. [6]
Furnicile se deplasează în linie dreaptă de la stup până la sursa de mâncare. Dacă acestea
întâlnesc un obstacol, fiecare furnică se deplasează aleator la stânga sau la dreapta pentru a ocoli
obstacolul. Să presupunem că furnicile se deplasează cu aceeași viteză și lasă în urma lor feromon
uniform. Furnicile care au ales să meargă la stânga vor ajunge mai rapid, pe când cele care au ales să
meargă la dreapta vor avea o cale mai lungă de parcurs. Intensitatea feromonului lăsat pe calea mai
scurtă este mai mare decât a celui lăsat pe calea mai lungă, prin urmare, furnicile vor fi ghidate în
număr cât mai mare să se deplaseze pe calea cea mai scurtă. Intensitatea feromonul ui lăsat este
unul din cei mai importanți factori pentru furnici în găsirea drumului cel mai scurt. [6]
Algoritmii de clusteri zare bazați pe furnici sunt o alternativă apropiată a algoritmilor de
clusterizare tradiționali. Algoritmul are abilitatea de a de scoperi automat numărul de clustere.
Natura algoritmul îl face destul de robust la efectele anomaliilor din interiorul setului de date.
Cercetarea algoritmilor bazați pe furnici este încă în desfășurare. Cercetarea se bazează pe
îmbunătățirea performanței, stabilității, convergenței, vitezei, robusteții și a altor feature -uri cheie
care ar permite utilizarea acestor metode în aplicațiile din viața reală. [6]
BCO este o metodă metaeuristică inspirată din natură, care este similară cu modul în care
albinele î și caută hrana în natură. Performanța algoritmului BCO a fost comparată cu alți algoritmi
euristici moderni cunoscuți, cum ar fi algoritmul genetic, algoritmul PSO pentru probleme de
optimizare fără constrângeri. BCO aparține claselor cu tehnici bazate pe populație și tehnici de
inteligență a roiurilor , care sunt aplicate în găsirea soluțiilor pentru problemele de optimizare

6
combinatoriale dificile. Ideea principală din spatele BCO este de a crea un sistem multi agent capabil
să rezolve eficient problemele d e optimizare combinatoriale dificile. [7]
Coloniile artificiale de albine (Artificial Bee Colony) se comportă într -o anumită măsura
similar dar și într -un mod diferit față de coloniile de albine din natură. Acestea explorează prin
spațiul de căutare căutân d posibile soluții. Pentru a descoperi soluții superioare, albinele artificiale
cooperează între ele și schimbă informații. Acestea se focusează pe zone mai promițătoare și elimină
treptat soluțiile din zonele mai puțin promițătoare prin cunoștințe colecti ve și schimbând informații
între ele. [7]
În rezolvarea problemei de clusterizare, albinele sunt localizate în stup la începutul
procesului de căutare. Fiecare albină artificială alocă date corespunzătoare clusterului cu
probabilități speciale în fiecare s tagiu și în acest fel construiește incremental o soluție a problemei.
Albinele adaugă componentele soluției la soluția parțială curentă până când au vizitat toate stagiile.
Procesul de căutare este compus din iterații. Sfârșitul primei iterații este atunci când albinele creează
o posibilă soluție. Cea mai bună soluție descoperită în timpul primei iterații este salvată și apoi
începe a doua iterație. În fiecare iterație, pentru fiecare cluster (stagiu), toate albinele părăsesc
stupul pentru a aloca unele in formații despre datele clusterului cu probabilități speciale și se
întoarce la stup pentru a vedea ce au descoperit cel elalte albine până acum ș i decid dacă vor
continua pe calea găsită sau vor continua pe una din căile găsite de celelalte albine. [7]
BEA poate parti ționa automat un set de date într-un număr optim de grupuri printr -o
singură încercare de optimizare. Acest algoritm se inspiră din fenomenul biologic al evoluției
microbiene. Spre deosebire de operațiile de mutație, recombinare și de selecție d in algoritmii
genetici, BEA integrează două operații speciale pentru evoluția populației, numite mutație
bacteriană și operația de transfer de gene. Mutația și operația de transfer de gene se repetă până
când un număr maxim de generații a fost depășit. Ace ste operații au fost modificate pentru a
manipula lungimea variabilă a cromozomilor care codifică diferite grupări de clustere. [8]
Mutația bacteriană imită un proces ce se petrece în bacterii la nivel genetic și urmărește să
îmbunătățească p ărțile din cromozomi. După generarea inițială a populației, mutația bacteria nă este
aplicată pe fiecare cromozom. Operatorii de mutație ai algoritmului de clusterizare automată BEA
diferă de cei ai algoritmului clasic BEA. Aceștia sun t special concepuți pentru a perm ite lungimii
cromozomului să se modifice dinamic în timpul procesului de învățare evoluționară. Î n mutația
bacteriană. primul cromozom este ales și apoi este reprodus în mai multe clone. Clonele sunt apoi
evaluate conform unor funcții de fitness. Cel mai b un cromozom este selectat să rămână în
populație, iar restul de cromozomi sunt eliminați. Această operație genetică este aplicată tuturor
cromozomilor din populația curentă. [8]
Operația de transfer al genelor se ocupă cu transferul informației dintre crom ozomii
populației. Prin acest mecanism, o bacterie poate să își răspândească informațiile genetice către
celelalte celule fără a fi necesară o operație de recombinare. Inițial, populația este sortată în două
jumătăți, una cu indivizii cu cele mai bune valo ri de fitness numită jumătatea superioară și una cu
restul de indivizi numită jumătatea inferioară. Un cromozom este ales din jumătatea superioară,
fiind numit cromozom sursă și unul din jumătatea inferioară, fiind numit cromozom destinație.
Conform unor c riterii date, o parte sau genă bună din cromozomul sursă este transferată către
cromozomul destinație. În cromozomul destinație, gena sosită înlocuiește o genă cu o valoare mică
selectată aleator. După acest transfer, gena trece printr -un mecanism de repar are, unde toate
genele cromozomului sunt scanate pentru a elimina datele duplicat ce apar în mai multe gene. [8]

7
3. Algoritmi utilizați

Acest capitol detaliază algoritmii de inteligență a roiurilor utilizați. În această lucrare sunt
utilizați doi algor itmi de inteligență a roiurilor , PSO, CSO și un algoritm de clusterizare, k-means . Tot
în acest capitol mai sunt prezentate și variantele de optimizare ale acestor algoritmi, cu pondere de
inerție și cu factor de comprimare. Pe lângă acești algoritmi, mai sunt descrise și două metode de
validare a clusterizări i, folosite pentru calcularea valorii de fitness a algoritmilor de mai sus.

3.1. Algoritmul Particle Swarm Optimization (PSO)

Algoritmul PSO a fost dezvoltat de Kennedy și Eberhart în 1995, fiind baz at pe
comportamentul în natură al bancurilor de pești și a l stolurilor de păsări. Mul ți algoritmi cum ar fi
ACO și Virtual Ant Colony folos esc comportamentul așa -numitei inteligență a roiurilor . PSO poate
avea câteva asemănări cu algoritmii genetici sau algoritmii ACO , dar este mult mai simplu, deoarece
nu folosește operatori de mutație , operatori de recombinare sau feromoni. În schimb, folosește
comunicarea globală dintre particulele roiului și numere reale aleatoare . [9]
PSO este ușor de implementat din moment ce nu codifică sau decodifică parametrii în șiruri
binare , cum fac algoritmii genetici care pot sa utilizeze , pe lângă șirurile binare, șiruri de numere
reale. Acest algoritm caută în spațiul funcției obie ctiv prin ajustarea traiectoriilor agenților
individuali, numiți particule, pentru a form a trasee pe porțiuni într -o manieră cvasi -stocastică.
Mișcarea unui roi de particule constă în două componente majore: o componentă stocastică și o
componentă deterministă. [9]
Fiecare particulă este a trasă către poziția global ă curentă cea mai bună (global best ) și
poziția proprie cea mai bună până în acel moment (local best ), dar în același timp are te ndința de a
se deplasa aleator . Dacă o particulă găsește o locație mai bună decât locațiile găsite anterior, setează
local best -ul ca fiind poziția curent ă. Fiecare particulă are în orice moment de timp un local best la
fiecare iterație. Scopul este de a căuta global best -ul printre to ate local best -urile găsite , până când
poziția globală nu se mai îmbunătățește sau până când a fost parcurs un anumit număr de iterații .[9]
Pașii care trebuie efectuați pentru a se găsi global best -ul sunt [10]:
1. Se creează o „populație” de agenți (numiți particule) uniform definită peste spațiul de
căutare
2. Se evaluează poziția fiecărei particule conform funcție i obiectiv
3. Dacă poziția curentă a particulei este mai bună decât poziția ei anterioară cea mai bună,
se actualizează poziția cea mai bună
4. Se determi nă cea mai bună particulă (conform pozițiilor cele mai bune al e particulei)
5. Se actualizează vitezele particulelor conform ecuației ( 1)

( ) (1)

6. Se actualizează poziția fiecărei particule conform ecuației ( 2)

(2)

7. Se repetă pasul 2 până când condiția de oprire este satisfăcută

Există multe variante c e extin d algoritmul standard PSO. În ac eastă lucrare se vor utiliza două
dintre aceste variante. Cele două variante constau în modificarea ecuației vitezei, prin adăugarea
unor factori . Adăugând o pondere de inerție sau un factor ce comprimare, se observă că algoritmul
are o viteză de convergență mai mare decât algoritmul standard PSO.

8
Ponderea de inerție este utilizat ă în ecuația vitezei (1) pentru a stabiliza mișcarea
particulelor. Această pondere se adaugă la viteza inițială (3) și poate fi o funcție care returnează o
valoare cuprinsă între 0 și 1 sau o constantă cu o valo are cuprins ă între 0.5 și 0.9 . Deoarece ace astă
pondere stabilizează mișcarea particulelor, algoritmul va trebui s ă aibă o viteză de convergență mai
mare . [9]

Ecuația vitezei atunci când se aplică ponderea de inerție este:

( ) , (3)

unde w este ponderea de inerție

Factorul de comprimare a fost adăugat pentru a asigura o convergență stabilă. Eberhart și
Shi au condus o analiz ă comparativ ă dintre ponderile de inerție și factorii de comprimare și au
descoperit că definind viteza maximă ca fiind limita maxim ă a pozi ției atunci când un factor de
comprimare este aplicat, se ob ține cel mai bun efect de convergență. [11]

Ecuația vitezei atunci c ând se utilizează factorul de comprimare este următoarea:

[ ( )]

√ (4)

În această ecuație, K este factorul de comprimare , iar valoarea constant ei este dată de
suma factorilor de învățare c1 și c2. Kennedy și Clerc au descoperit în studiul lor că atunci când
constanta este mai mică decât patru, convergența întregului roi (swarm) nu poate fi asigurat ă. În
schimb, atunci când este mai mare decât patru , nu numai că particulele se mișcă mai rapid și ajung la
convergență, dar convergenț a poate avea loc pentru o viteză adecvat ă. În mod normal, set ările
pentru aceste constante sunt K = 0.72984 și c1 = c2 = 2.05 . [11]

3.2. Algoritmul Cat Swarm Optimization (C SO)

Algoritmul CSO a fost dezvoltat de Shu -Chuan Chu și Pei -wei Tsai, fiind bazat pe
comportamentul pisicilor. Există aproximativ 30 de specii de feline, conform clasificării biologice, de
exemplu: leu, tigru, pisică, ghepard, panteră etc. Deși multe feline au diferite medii de viață, acestea
manifestă comportamente similare. Abilitățile de vânătoare sunt dobândite prin antrenament,
așadar nu sunt înnăscute . Pentru felinele sălbatice, abilitățile de vânătoare asigură hrana și
supraviețuirea speciei. [12]
Pisicile domestice manifestă aceleași abilități naturale de vânătoare și o curiozitate puternică
pentru obiectele în mișcare. Deși toate pisicile manifestă această curiozitate puternic ă, petrec cel
mai mult din timpul lor relaxându -se, chiar și atunci când nu dorm. Pisicile au un grad foarte ridicat
de vigilență. Acestea sunt vigilen te chiar și atunci când se relaxea ză. Pisicile par a fi leneșe , dar dacă
sunt examinate mai amănunțit, se va observa că stau cu ochii larg deschiși , observând mediul
înconjurător . Acestea sunt ființe foarte deștepte și prudente. Se spune că pisicile au nouă vieți ,
această afirmație referindu -se la vitalitatea puternic ă a pisicilor. Pisicile domestice scot adesea un
sunet la o frecvență foarte joasă , torsul. Pisicile torc atunci când sunt mulțumite, în pericol sau
bolnave. Se crede că frecvența scăzută a torsulu i ajută la repararea ce lulelor. [12]
CSO modelează cele două comportamente ale pisicilor în două moduri: modul de căutare și
modul de urmărire . Modul de căutare este utilizat pentru a modela pisicile în timp ce acestea se
relaxează, fiind vigilente, analizând mediul înconjurător pentru următoarea mutare. Modul de

9
urmărire este folosit pentru a modela cazurile în care pisicile urmăresc țintele. Prin combinarea
acestor două moduri, CSO se poate ocupa de problema de optimizare .[13] În continuare , vom folosi
termenul de agent pentru a descrie o pisică.
Modul de căutare are patru factori esențiali: spațiul memoriei de căutare ( SMP – Seeking
Memory Pool), căutarea limitelor dimensiunii selectate (SRD – Seeking Range of the selected
Dimension ), numărul de dimensiuni de schimbat (CDC – Counts of Dimension to Change ),
considerarea poziției proprii ( SPC – Self Position Consideration ). SMP este utilizat pentru a defini
dimensiunea memoriei de căutare pentru fiecare agent . Agentul va alege un punct din memor ia de
căutare, conform anumitor reguli. SRD declară probabilitatea de mutație pentru dimensiunile
selectate. Dacă o dimensiune este selectată pentru mutație, diferența dintre valoarea veche și cea
nouă nu trebuie sa depășească limitele definite de SRD. CDC spune câte dimensiuni vor fi va riate.
Toți acești factori joacă un rol important în modul de căutare. SPC este o variabilă booleană care
indică dacă punctul în care se află agentul va fi un candidat la care să se mute. SPC nu influențează
valoarea lui SMP . [12]

Acest mod poate fi descr is prin următorii pași [12]:
Pasul 1: Se creează j copii ale poziției curente a agentului k, unde j = SMP. Dacă valoarea lui
SPC este adevărată, setează j = SMP – 1, apoi reține poziția curentă ca unul dintre candidați.
Pasul 2: Pentru fiecare copie, confo rm CDC, se adaugă sau scad SRD procente din valoarea
curentă și se înlocuiește valoarea veche.
Pasul 3: Se calculează valoarea de fitness pentru fiecare candidat.
Pasul 4: Dacă toate valorile de fitness sunt egale, se setează probabilitatea pentru fiecare
candidat ca fiind 1, altfel se calculează probabilitatea de selecție conform ecuației ( 5).
Pasul 5: Se alege aleator punctul către care să se deplaseze din lista de candidați și s e
înlocuiește poziția agentului k.

| |
(5)

Dacă scopul funcției de fitness este de a găsi minimul soluției, atunci , altfel

Modul de urmărire este utilizat pentru a modela cazul în care pisicile își urmăresc țint a. O
dată ce agentul intră în modul de urmărire, aceasta se deplasează conform vitezelor proprii pentru
fiecare dimensiune [13]. Acest mod poate fi descris prin următorii pași [12]:
Pasul 1: Se actualizează vitezele pentru fiecare dimensiune ( ) conform ecuației ( 6).
Pasul 2: Se verifică dacă vitezele depășesc valoarea maximă. În caz ca noua viteză depășește
valoarea maximă, aceasta este setată ca fiind viteza maxima.
Pasul 3: Actualizează poziția agentului k conform ecuației ( 7).

( ) (6)

(7)

este poziția agentului care are cea mai bună valoare de fitness
este poziția agentului k, este o constantă, iar este o valoare aleatoare în intervalul
[0,1]

La algoritmul propus, se adaugă o pondere de inerție la ecuația vitezei . Viteza este
actualizată pentru fiecare dimensiune. Utilizând acest parametru, se realizează o balanță între
abilitatea de căutare globală și cea locală. O valoare mare a factorului de inerție favorizează căutarea
globală, în timp ce o valoare mică a factorului de inerție favorizează căutarea local ă. Prima data se

10
utilizează o valoare mare, ce va fi redusă gradual până la valoarea cea mai mică folosind ecuația ( 8).
[14]

(8)

Ecuația ( 8) indică faptul că factorul de inerție se va actualiza adaptiv, unde este inerția
inițiala sau de pornire, este dimensiunea maximă a benchmark -ului și i este dimensiunea
curentă. Așadar, valoarea ma ximă a inerției se utilizează în prima dimensiune a fiecărei iterații și va fi
actualizată, prin scăderea valorii acesteia, în fiecare dimensiune. În algoritmul propus, este egal
cu 0. 9. De asemenea, c1 este un coeficient de accelerație pentru extinde rea vitezei de deplasare a
unei pisici în spațiul soluției. Acest parametru are o valoare constantă și este de obicei egal cu 2.05.
[14]

3.3. Algoritmul K -means

Algoritmul K-means este un algoritm de clusterizare simplu, care încearcă să găsească k
clustere care nu se suprapun. Aceste clustere sunt reprezentate de proprii centroizi (un centroid este
reprezentat de media punctelor din cluster). Acest algoritm are câteva avantaje dist incte în
comparație cu alți algoritmi de clusterizare: este foarte simplu și robust, foarte eficient și poate fi
aplica t pentru o varietate mare de ti puri de date [15]. Are și dezavantaje, cum ar fi performanța
slabă pentru clusterele neglobulare și sens ibilitatea la anomalii [15]. Unul din punctele slabe ale
acestui algoritm este că algoritmul, în procesul de iterație, poate să conveargă la un minim local sau
chiar un punct de zgomot. [15]
Inițial sunt selectați aleator k centroizi, unde k este specificat de utilizator și indică numărul
de clustere dorite. Fiecare punct din setul de date este atribuit celui mai apropiat centroid, iar
fiecare colecție de puncte atribuită unui centroid formează un cluster. Centroidul fiecăr ui cluster
este actualizat pe baza punctel or atribuite acelui cluster (9). Acest proces se repetă până când niciun
punct nu îș i mai schimbă clusterul [15].
Ecuația cu care se actualizează centroizii este:

| | ∑ , (9)

Unde este clusterul i, | | este numărul de puncte din clusterul i și x este un punct din
clusterul i. Coordonatele noului centroid sunt calculate folosind formula de mai sus pe fiecare
dimensiune a punctului x.

3.4. Indici de validare a clusterizării

Pentr u algoritmii de inteligență a roiurilor menționați mai sus, se vor folosi doi indici de
validare a clusterizării ca metode de măsurare: Dunn și Davies Bouldin.
Dunn returnează o valoare cât mai mare pentru o clusterizare cu o con Figura ție cât mai
bună. Dac ă setul de date conține clustere liniar separabile, distanța dintre clustere este de obicei
mare, iar diametrele clusterelor ar trebui sa fie mici. Principalele dezavantaje ale acestui indice sunt
durata mare de execuție și sensibilitatea la zgomot. Acest indice este definit de ecuația ( 10). [3]

11
{ ( ( )
( ))}
( ) (10)

Davies Bouldin returnează o valoare cât mai mică pentru o clusterizare cu o con Figura ție
cât mai bună. Acest indice se bazează pe măsurarea asemănării dintre clustere ( ), care are la bază
măsurarea dispersiei unui cluster ( ) și măsurarea diferenț elor dintre clustere ( ). poate fi
definit liber, dar trebuie sa îndeplinească următoarele condiții *3+:
–
–
– dacă și atunci
– dacă și atunci
– dacă și atunci

De obicei, este definit prin ecuația (1 1):

, unde
( )
‖ ‖∑ , centrul clusterului i (11)

Indicele de validare, Davies Bouldin, este definit de ecuația (1 2).

∑

( ) (12)

12

4. Descrierea sistemului

În acest capitol vor fi descrise arhitectura sistemului, modulele aplicației și implementarea
unor module în pseudocod. În prima parte a capitolului, vor fi precizate con Figura țiile sistemului,
limbajul folosit, librăriile grafice utilizate și utilitarele de care depinde aplicația. După aceea vor fi
descrise pe scurt modulele aplicației, iar mai spre finalul capitolului, va fi descrisă implementarea
unor module prin pseudocod.

4.1. Arhitectura sistemului

Aplicația a fost implementată în Visual Studio, folosind sistemul de operare Windows 7 pe 32
de biți. Limbajul de programare utilizat este C++, iar librăria grafică utilizată este OpenGLES. Pentru a
putea accesa toate funcționalitățile aplicației, se recomandă instalarea utilitarului „gnuplot” pentru
windows. Acest utilitar este folosit pentru generarea graficelor direct din aplicație. Aplicația poate
rula și fără acest utilitar, dar cu imposibilitatea de a genera grafice.

4.1.1. Descrierea modulelor aplicației

Figura 1. Diagrama cu relațiile dintre modulele aplicației

Pentru a porni aplicația, utilizatorul trebuie sa pornească modulul de încărcare. Odată pornit
acest modul, se începe încărcarea tuturor elementelor ce trebuie afișate în modulul de afișare și în
modulul de control. Pe durata încărcării elementelor, modulul afișează o bară de încărcare și un
procent ce se actualizează după încărcarea fiecărui element. La terminarea încărcării datelor, se

13
încarcă modulul de afișare în care sunt afișate toate punctele din se tul de date și modulul de control
ce poate fi accesat numai de utilizator. Modul ul de încărcare mai poate fi apelat și de alte module
pentru a afișa progresul unei acțiuni de comparare, generare sau de salvare.
În modulul de afișare se pot vedea punctele d in setul de date, particulele oferite de
algoritmii de clusterizare și tabelul cu rezultatele salvate în urma rulării testelor. La rulare, punctele
din setul de date vor avea atribuită o culoare în funcție de clusterul de care aparțin. Pentru a afișa
tabel ul cu rezultatele salvate, se apasă butonul „Show table” și se selectează metoda de validare a
clusterizării, Dunn sau Davies Bouldin. Rezultatele din tabel sunt sortate descrescător de la cea mai
bună valoare a funcției de fitnes s. În tabel sunt afișate d oar rezultatele pentru indicele de validare
selectat . Tabelul conține numele algoritmului utilizat, numele testului, parametrii cu care a fost rulat
testul și valoarea funcției de fitness. Pentru a ascunde tabelul se apasă butonul „Hide table”.
Utilizatoru l poate face zoom pentru a vedea mai bine punctele, utilizând modulul de zoom.
Acest modul poate efectua două acțiuni: zoom in și zoom out . Operația de zoom in este activată
atunci când se face dublu click pe modulul de afișare sau când se apasă tasta „i”. După activare,
distanța dintre puncte este mărită pentru a permite utilizatorului să vadă punctele mai bine. Pentru
a face zoom out, utilizatorul trebuie să a pese click dreapta pe modulul de afișare sau tasta „o”.
Această operație micșorează distanța dintre puncte. Pentru a face scroll pe puncte, utilizatorul poate
folosi bar a de scroll , această operație mai putând fi realizată dacă utilizatorul face click stân ga pe
modulul de afișare, ține click -ul apăsat și deplasează cursorul pe ecran. Operațiile de zoom in , zoom
out și de scroll pot fi accesate în oricare din cele 3 module principale ale modulului de control.
Pentru a efectua operații de comparare, generare sau rulare, utilizatorul trebuie sa acceseze
modulul de control. Acest modul conține 3 module principale: de comparare, de generare și de
rulare. Pentru a naviga printre aceste module, utilizatorul trebuie sa interogheze modulul de control.
Acest modul int eroghează modulul corespunzător și îi trimite utilizatorului un răspuns vizual.
Răspunsurile vizuale constau în activarea butoanelor, afișarea informațiilor pe ecran, durata
anumitor acțiuni afișând o bară de încărcare, ș.a.
Pentru a compara doi sau mai mu lți algoritmi, utilizatorul va trimite cereri modulului de
control pentru a interoga modulul de comparare. În modulul de comparare, utilizatorul poate solicita
încărcarea unui nou set de date interogând modulul de încărcare test , generarea unui grafic,
com pararea algoritmilor sau afișarea unui tabel. Setul de date este ales dintr -o listă ce apare în
modul ul de afișare . Odată selectat un test, acesta este încărcat, iar punctele din setul de date sunt
afișate în modulul de afișare. După ce utilizatorul s -a de cis în privința cărui set de date va fi utili zat
pentru a compara algoritmii, numărul de iterații și numărul de ciclii, acesta poate porni procesul de
comparare apăsând pe butonul „Compare” din interiorul modulului de comparare.
Dacă butonul „Compare” a fo st apăsat, modulul de control va returna o fereastră în care
utilizatorul va seta parametrii și algoritmii pentru comparare. Această fereastră conține o listă de
algoritmi, parametrii pentru fiecare algoritm, un buton pentru modificarea parametrilor, un bu ton
pentru începerea comparării și un buton pentru anularea acestei comenzi. Pentru a începe
compararea se selectează algoritmii doriți și se apasă pe butonul „Start comparing ”. Când doi sau
mai mulți algoritmi sunt comparați, se afișează o bară de încărca re ce se actualizează la fiecare
iterație. Pentru a anula procesul de comparare, se va apăsa tasta „ESC” și proces ul de comparare va
fi întrerupt, revenindu -se la modulul de afișare și cel de control.
Pentru a genera un grafic, se folosește modul de generare grafic. Acest modul deschide o
fereastră nouă în care utilizatorul va trebui sa aleagă algoritmii pe care sa îi utilizeze , în trei pași. În
primul pas, utilizatorul va alege unul din teste pentru un anumit număr de ciclii și de iterații. În cel
de-al doilea pas, utilizator va alege unul sau mai mulți algoritmi în funcție de valorile ponderii de
inerție sau factorului de comprimare cu care au fost rulați. În pasul final, se selectează parametrii
pentru fiecare algoritm ales la pașii anteriori și se începe generarea graficului.
Dacă utilizatorul va dori să selecteze un algoritm va interog a modulul de selectare algoritm,
selectând algoritmul dintr -o listă dată. Dacă utilizatorul se află în modulul de rulare, un singur
algoritm va putea fi selectat din lista de algoritmi, rândul din listă corespunzător algoritmului curent

14
fiind colorat cu albastru. La editarea parametrilor, când utilizatorul selectează un algoritm din listă,
rândul din listă, corespunzător algoritmului selectat va fi colorat cu verde, ia r parametrii necesari
acestui algoritm vor fi activați pentru a putea fi modificați. Pentru a porni procesul de comparare, se
selectează cel puțin doi algoritmi, aceștia putând fi deselectați dacă se apasă încă o dată pe acea
intrare. Algoritmii vor fi rul ați în ordinea în care au fost selectați, iar rezultatul rulării algoritmilor va
fi afișat într -un grafic.
Pentru a edita parametrii algoritmilor, utilizatorul va trebui sa apese pe butonul „Edit
parameters ” din fereastra de comparare sau din modulul de r ulare. Acest buton va po rni modulul de
setare parametri . În acest modul, utilizatorul va putea să modifice parametrii activați pentru
algoritmul selectat. Parametrii care nu sunt necesari pentru algoritmul selectat vor fi dezactivați.
După ce a terminat de modificat parametrii unui algoritm, pentru a salva modifi cările se apasă
butonul „ Apply ”, dacă utilizatorul se află în modulul de comparare sau butonul „OK” dacă utilizatorul
se află în modulul de rulare.
Generarea unui test sau editarea testului curent s e poate face din modulul de generare.
Pentru a accesa acest modul, utilizatorul va trebui sa apese pe tab -ul „Generate” din modulul de
control. În acest modul, utilizatorul va trebui să seteze parametrii pentru generarea t estului dorit.
Acești parametri constau în numărul de puncte pentru fiecare cluster, distanța dintre clustere,
diametrul clusterului și numărul de clustere. După ce utilizatorul s -a decis în privința parametrilor,
poate apăsa pe butonul „Generate” pentru a genera un nou set de date.
Genera rea unui nou set de date se face folosind parametrii setați în modulul de mai sus.
Acest proces folosește modulul de generare test. Inițial se generează primul cluster, generându -se
toate punctele asociate acestuia. După ce a fost generat primul cluster, s e generează al 2 -lea cluster
la o distanță mai mare sau egală cu distanța minimă dintre clustere setată în modulul anterior.
Începând cu al 3 -lea cluster, se caută un centru care sa fie la o distanță mai mare sau egală cu
distanța minimă dintre clustere adunată cu diametrele clusterelor deja existente și diametrul noului
cluster. Toate clusterele generate vor avea o distanță minimă egală cu distanța precizată. Setul de
date generat poate fi salvat sau utilizat în modulul de rulare.
Dacă se dorește editarea unui test, se apasă butonul „Edit Test” din modulul de generare.
Acest buton apelează modulul de editare test. Atâta timp cât butonul „Edit Test” este activ, se pot
adăuga sau elimina puncte folosind mouse -ul. În timpul editării se poate face, de asemenea, zoom
sau scroll. Pentru a adăuga un punct, se face click în modulul de afișare într -un loc în care nu există
puncte. Pentru a elimina un punct, se face click pe un punct deja existent și acesta va dispărea. Dacă
s-a adăugat sau el iminat un punct, numărul de clustere din modulul de generare va fi setat pe 0.
Dacă numărul de clustere este 0, utilizatorul va rămâne blocat pe modulul de generare până când
numărul de clustere va fi mai mare decât 0. Dacă numărul de clustere este mai mar e decât 0, iar
testul a fost editat sau generat, butonul de salvare va fi activat pentru a putea salva testul generat
sau modificările efectuate.
Salvarea unui test generat sau editat se face apăsând butonul „ Save ” atunci când acesta este
activ. Dacă un te st a fost generat sau editat, acest buton va deveni activ atunci când numărul de
clustere este setat pe o valoare mai mare decât 0. Acest buton apelează modulul de salvare test,
care interoghează lista de teste și generează un nume nou pentru test. Numele testului este format
din „t” + primul număr disponibil, ce nu a fost folosit de alte teste. În fișier sunt salvate rezultatele
celui mai bun ciclu, iar pe prima linie este trecuta cea mai bună valoare a funcției de fitness obținută
în timpul rulării , cu „# ” în față . Această valoare va fi folosită în tabel.
În modulul de rulare se pot efectua mai multe acțiuni. Aceste acțiuni pot fi de selectare test,
selectare algoritm, modificare culori, rulare al goritmi sau de setare parametri pentru algoritmi.
Culorile s unt reprezentate în sistemul RGB, iar modificarea acestora poate fi realizată utilizând
sliderele pentru fiecare culoare. Culorile se modifică instantaneu în modulul de afișare. Selectarea
unui test sau a unui algoritm se face folosind modulul de selectare descris mai sus. În funcție de
algoritmul selectat, vo r fi activați anumiți parametri . Acești parametri pot fi modificați folos ind
modulul de setare parametri . Parametrii ce nu sunt necesari algoritmului curent sunt dezactivați.

15
Pentru a rula algoritmul, se folosește butonul „Start”, iar algoritmul va rula până câ nd butonul
„Stop” va fi apăsat.

4.2. Pseudocod module

Aplicația rulează în paralel mai multe funcționalități. Acestea sunt: desenarea obiectelor și a
seturilor de date pe ecran, interpretarea comenzilor de la tastatură și interpretarea comenzilor
mouse -ului. În continuare va fi descrisă implementarea acestor funcționalități prin pseudocod.
Pornind de la aceste funcționalități, vor f i descrise implementările modu lelor prezentate mai sus
folosind pseudocod.

4.2.1. Metoda Draw()
Această metoda este folosită pentru desenare a obiectelor și a seturilor de date .

4.2.2. Metoda Key()
Această metodă citește comenzile de la tastatură și le interpretează.

4.2.3. Metoda Mouse()
Această metodă interpretează comenzile mouse -ului

Acțiunile butoanelor pot fi: generare test, comparare algoritmi, rulare test, gen erare grafic,
editare parametri , selectare algoritmi ș.a. În continuare vor fi prezentate câteva din tre aceste
acțiuni.

4.2.3.1. Metoda Generate()
Această metodă generează un set de date nou.

4.2.3.1. Metoda Compare()
Această metodă este utilizată pentru a compara algoritmii.

18

5. Implementarea sistemului

În acest capitol vor fi prezentate pe scurt clasele utilizate de aplicație și vor fi descrise
detaliat funcționalitățile aplicației. Relațiile dintre clase sunt prezentate în diagrama din Figura 2. În a
doua secțiune a capitolului vor fi descrise funcționalitățile aplicației și interfața cu utilizatorul pe
baza unor screenshot -uri. Acest capitol conține toate instrucțiunile de utilizare a interfeței cu
utilizatorul.

5.1. Descrierea claselor
Figura 2. Diagrama cu relațiile dintre clase

Diagrama din Figura 2 conține clasele cele mai importante utilizate în aplicație și relațiile
dintre acestea. Pe lângă aceste clase, au mai fost folosite alte trei clase din librăria OpenGLES pentru
afișarea obiectelor pe ecran. Aplicația conține un shader pentru desenarea setului de date sau al
particulelor algoritmilor și un shader pentru desenarea butoanelor, tabelelor, panoului de control,
ș.a. În continuare, vor fi descrise pe scurt aceste clase.
„Data ” conține inf ormații necesare pentru desenarea obiectelor sau a particulelor. Această
clasă definește o structură necesară pentru desenarea unui punct 2D/3D, Vector2/Vector3, o
structura pentru reprezentarea unei particule, „Particle ”, și o structură pentru reprezentarea unui
cluster. Aceste structuri sunt folosite atât în desenarea punctelor pe ecran, cât și în algoritmii de
inteligență a roiurilor .

19
Clasa „Table ” este folosită pentru inserarea datelor în tabel și pentru afișarea acest ora pe
ecran. Această clasă include clasa pentru generarea unui text 2D, „ Text2d”, și clasa „ Utilities ” care
include clasele din librăria de OpenGLES necesare pentru afișarea datelor pe ecran. Pentru
generarea unui tabel, se creează inițial rândurile și coloanele în care se adaugă obiecte de tip text din
clasa „Text2d”. Deoarece tabelul poate conține un număr mare de înregistrări, s -a mai adăugat o
funcționalitate de scroll pentru a vedea și restul datelor din tabel.
Clasele „Pso”, „Cso” și ”KMeans” conțin algoritmii de inteligență a roiurilor și algoritmul de
clusterizare KMeans. În aceste clase se calculează valoarea de fitness a fiec ărei particule pentru o
singură iterație, se setează valoarea globală a fitness -ului și se returnează valoarea setată. Valoa rea
de fitness se obține aplicând unul din indicii de validare a clusterizării din clasa „ Validation ”. Indicii
de validare returnează o valoare ce depinde de distanța dintre cluste re, de diametrul clusterelor și
de alte caracteristici ale clusterelor.
Pent ru generarea testelor se folosește clasa „Generate” care include clasa „ Loading ”,
necesară pentru afișarea progresului generării. Această clasă folosește parametrii transmiși de la
interfață pentru a genera clust erele. Distanța dintre clustere și diametrul acestora sunt calculate
folosind distanța euclidiană. În timpul generării setului de date, clasa „ Loading ” va afișa o bară cu
progresul acestei operații și informații pentru întreruperea acesteia.
Clasa „TestsList” generează o listă în care sunt adăugate toate numele testelor. Pentru a crea
această listă, se generează un număr de înregistrări de tip obiect din clasa „ Object ” și se adaugă
numele testelor în aceste înregistrări . Un obiect este format dintr -un patrulater pe care se aplică o
textură. Pentru a încărca o textură, se folosește clasa „ Shaders ”. Această clasă transmite informații
către shadere, care sunt transmise mai departe la placa grafică pentru o desenare mai rapidă. Pe
listele generate se pot efectua operații de selectare sau de scroll. Când u n câmp este selectat , se
înlocuiește testul curent cu testul selectat .
Clasa în care se execută operații de desenare, de inițializare și de interpretare a comenzilor
transmise de utilizator este „Main”. Această clasă, pe lângă funcțiile principale, setează culorile din
clasa „Color” și variabilele globale din clasa „Globals” ce reprezintă dimensiunile ferestrei . Culorile
sunt folosite pentru fundal și pentru identificarea clusterelor, putând fi modificate folosind sliderele
definite în clasa „Slider”. Main -ul mai este responsabil pentru operațiile de zoom și pentru
normalizarea setului de date.
Pentru generarea graficelor, se folosește clasa „Wizard”. Această clasa pune utilizatorului la
dispoziție 3 pași pentru selectarea testului dorit. În primul pas, util izatorul trebuie să selecteze dintr –
o listă, un test rulat cu un anumit număr de iterații și de cicluri. În pasul al doilea, se vor selecta unul
sau mai mulți algoritmi ce vor fi adăugați în grafic. În pasul final, se vor alege constantele dorite
pentru al goritmii selectați, după care se va începe generarea graficului.

20

5.2. Interfața grafică

Figura 3. Modulul de comparare

În Figura 3 este afișat modulul de comparare. Acest modul este activat selectând tab -ul
„Compare”. Din acest modul se pot efectua operații de selectare test, afișare tabel, generare grafic
sau comparare. Pentru a afișa un tabel, se apasă pe butonul „Show table”. Câ nd tabelul este afișat
pe ecran, acest buton își schimbă denumirea în „Hide table”. În acest tabel sunt afișate doar
rezultatele pentru indicele de validare selectat. Tabelul din Figura de mai sus conține doar
rezultatele pentru indicele „Dunn”. Dacă buton ul „Davies Bouldin” este apăsat, se vor încărca în
tabel rezultatele pentru indicele „Davies Bouldin”. Pentru a ascunde tabelul, se va apăsa butonul
„Hide table”. În această figură este selectat testul t03.
Pentru a începe un proces de comparare, se va selecta mai întâi indicele de validare dorit și
se va modifica numărul de cicluri și numărul de iterații, dacă este nevoie. Pentru a modifica numărul
de iterații sau numărul de ciclii, se face click pe c aseta de text respectivă și se introduce noua valoare
de la tastatură. Numărul de ciclii sau numărul de iterații poate fi format din maxim patru cifre. După
ce s-au făcut setările dorite, se va apăsa butonul „Compare” ce va afișa o fereastră nouă.
După cum se ve de și în figură, lista de teste și tabelul au o bară de scroll. Această bară este
folosită pentru a naviga prin rezultate sau prin lista de teste și pentru a afișa toate valorile din listă
sau din tabel. Dacă se selectează un test din lista de teste, setul de date curent va fi înlocuit cu setul
de date din noul test și va fi afișat pe ecran. Testul curent este colorat în lista de teste într -un
albastru de o nuanță mai deschisă.
Tabelul conține o coloană pentru denumirea algoritmului ce a fost rulat, testul folosit la
rulare, numărul de ciclii și numărul de iterații care au fost efectuate, parametrii algoritmilor și
valoarea funcției de fitness. Dacă unul din parametrii lipsește, în dreptul acestui va apărea ”-”. În

21

această aplicație funcția de fitness este î nlocuită de indicii de validare. Acești indici calculează
corectitudinea clusterizării. Valorile de fitness din tabel sunt sortate de la cea mai bună la cea mai
slabă.

Figura 4. Fereastra de inițiere a procesului de comparare

În Figura 4 este prezentată fereastra în care se aleg algoritmii pentru comparare. În această
fereastră se selectează algoritmii doriți și se pornește procesul de comparare. Pentru a selecta sau
deselecta un algoritm, se face click pe numele acestuia din lista de a lgoritmi. Procesul de comparare
începe numai daca a fost selectat cel puțin un algoritm. Dacă se selectează numai un algoritm,
aplicația va arăta evoluția algoritmului selectat pentru numărul de ciclii, numărul de iterații și
indicele de validare precizat. Dacă se dorește schimbarea indicelui de validare sau a numărului de
iterații sau de ciclii, se apasă butonul „Cancel”, se aleg setările dorite și se a pasă din nou butonul
„Compare” și se revene la setările anterioare. Dacă nu se selectează un algoritm, la apăsarea
butonului „Start comparing” nu se va întâmpl a nimic, aplicația așteptând ca utilizatorul sa precizeze
algoritmii sau sa anuleze operația.
Dacă se bifează opțiunea „Overwrite existing results”, la terminarea rulării unui algoritm,
dacă există rezu ltate pentru acest algoritm, acestea vor fi șterse și înlocuite cu rezultatele obținute în
urma rulării. Dacă nu se bifează această opțiune, se verifică mai întâi dacă există un rezultat pentru
algoritmul selectat și dacă există, folosește acel rezultat și trece la următorul algoritm. Algoritmii
sunt rulați în ordinea în care au fost selectați. După ce au fost rulați toți algoritmii, toate rezultatele
obținute vor fi introduse într -un grafic. După ce se închide graficul, se afișează un tabel . asemănător
cu cel din Figura 3, în care sunt afișate doar rezultatele pentru algoritmii selectați pentru comparare.

22

Figura 5. Fereastra de con Figura re a parametrilor algoritmi lor

Pentru a modifica parametrii unui algoritm, se apasă pe butonul „Edit parameters” din
Figura 4. După ce se apasă acest buton, toți algoritmii vor fi deselectați, iar butoanele din fereastră
vor fi modificate. Când se modifică parametrii, numai un singur algoritm poate fi selectat. Inițial,
butonul „ Apply ” este dezactivat și are o textură su gestivă. Acest buton se activează atunci când sunt
modificați parametrii algoritmilor.
În modul de editare al parametrilor, algoritmul selectat va avea culoare verde. Când se
selectează un algoritm, parametrii folosiți de acel algoritm sunt activați, iar r estul rămân dezactivați.
În Figura 5, pentru algoritmul PSO cu factor de comprimare, sunt activați doar parametrii pentru
factorul de comprimare și pentru constantele algoritmului, c1 și c2. Parametrii pentru ponderea
inițială și ponderea finală nu sunt utilizați de acest algoritm, motiv pentru care aceștia sunt
dezactivați.
Pentru a edita un parametru, se face click pe acesta și căsuța de text se va modifica la fel ca
la parametrul c1 din Figura 5, devenind activă. Cât timp căsuța de text este activă, utilizatorul poate
să șteargă folosind tasta „Backspace” sau poate sa adauge o nouă valoare introducând cifre de la
tastatură. Dacă în c aseta de text valoarea este zecimală, după prima cifră se pune automat virgulă.
Când o c asetă de text este activată, se activează și butonul „Apply”. Dacă utilizatorul dorește să
salveze modificările făcute, apasă pe acest buton. Dacă nu se dorește salvarea modificărilor făcute,
se selectează alt algoritm sau se apasă pe butonul „OK”. Dacă modificările făcute sunt salvate,
parametrii algoritmilor vor fi modificați în toată aplicația.
Dacă se dorește revenirea la parametrii inițiali, se apasă butonul „Reset”. Acest buton
setează pentru algoritmi parametrii utilizaț i la porn irea aplicați ei. Orice modificare a parametrilor
rămâne salvată cât timp aplicația este pornită. Dacă aplicația este oprită, parametrii se resetează.
După ce s -au realizat modificările dorite, utilizatorul trebuie să apese pe butonul „OK” pentru a
reveni la fereastra anterioară, Figura 4. Fereastra din Figura 4, cât și cea din Figura 5 pot fi închise
oricând apăsând tasta „ESC”.

23

Figura 6. Fereastra de generare grafic

Pentru a genera un grafic se apasă pe butonul „Graphic”, iar acest buton va des chide o
fereastră nouă la fel ca în Figura 6. În această fereastră va apărea o listă care inițial va conține toate
testele pentru care s -au obținut rezultate și numărul de ciclii și iterații cu care au fost rulate. Pe lângă
această listă, fereastra mai con ține un mesaj cu instrucțiuni, un buton „Back”, care inițial e
dezactivat, un buton „Next” care face trecerea la următorul pas și un buton „Cancel” care anulează
procesul de generare al graficului.
După ce a fost selectat testul dorit, se apasă butonul „Ne xt” și se trece la pasul următor. La
cel de -al doilea pas, lista va conține o listă cu algoritmii ce au fost rulați pentru testul selectat și
valoarea ponderii de inerție sau valoarea factorului de comprimare cu care a fost rulat testul. Dacă
algoritmul nu folosește pondere de inerție sau factor de comprimare, va apărea doar numele
algoritmului. Din această listă se pot selecta mai mulți algoritmi. Butonul „Back” la acest pas va fi
activat, iar dacă acesta este apăsat, se va trece la pasul anterior. Mesajul cu instrucțiuni va fi
modificat la trecerea către pasul al doilea.
După ce au fost selectați algoritmii doriți, se apasă din nou butonul „Next” și se trece la pasul
al treilea, care este și ultimul pas. La acest pas, lista va conține algoritmii selectați la pașii anteriori și
parametrii cu care au fost rulați. Fiecare algoritm va avea în fața numelui acestuia o inițială, „(I)” sau
„(C)” dacă algoritmii au fost rulați cu pondere de inerție sau factor de comprimare , iar numele se va
termina cu valorile const antelor algoritmilor, dacă există. Pot fi aleși mai mulți algoritmi. Numele
butonului „Next” va fi modificat în „Generate”, iar la apăsarea acestui buton, se va genera un grafic
ce va conține algoritmii selectați în cei trei pași. Dacă la pasul final nu es te ales niciun algoritm și se
apasă butonul „Generate”, graficul nu va fi generat, iar fere astra de generare va fi închisă; butonul
se va comport a la fel ca butonul „Cancel”.

24

Figura 7. Modulul de generare și editare seturi de date

Modulul de generare este reprezentat în Figura 7. Acest modul poate fi selectat apăsând pe
tab-ul „Generate”. În acest modul se generează un nou set de date pe baza parametrilor introduși
sau se editează un set de date curent. Utilizatorul trebuie să preci zeze un interval pentru numărul de
puncte, numărul de clustere dorit, un interval pentru distanța dintre clustere și un interval pentru
diametrul unui cluster.
La apăsarea butonului generate, se va genera un număr de puncte aleator din intervalul
precizat pentru fiecare cluster. Centrele clusterelor vor fi poziționate unul față de altul la o distanță
egală cu un număr generat aleator din intervalul distanței dintre clustere, la care se adaugă
diametrul celor două clustere. Toți parametrii sunt respectați me reu cu excepția distanței maxime
dintre clustere. Dacă sunt generate mai multe clustere și distanța dintre oricare două clustere nu
poate fi în intervalul precizat, noul cluster se va genera la o distanță cel puțin egală cu distanță
minimă. Noul cluster va fi poziționat în așa fel încât distanța dintre oricare două clustere să fie
minimă . În timpul generării va apărea pe ecran o bară de încărcare ce va arăta progresul operației de
generare. Acest proces poate fi anulat apăsând tasta „ESC”.
Pentru a edita un test, se apasă butonul „Edit Test”. Butonul va rămâne activ până când va fi
apăsat încă o dată sau până când se schimbă tab -ul curent. Cât timp butonul este apăsat, utilizatorul
poate adăuga puncte făcând click stânga în modulul de afișare. Pentru elimina rea unui punct se face
click stânga pe un punct, iar acesta va fi eliminat din setul de date. Dacă se face dublu click pe
modulul de afișare se va face zoom in , distanța dintre puncte mărindu -se. Zoom -ul ajută la
adăugarea punctelor cu o precizie mai bună. Pentru a face zoom out , se apasă click dreapta pe
modulul de afișare, distanța dintre puncte micșorându -se. Pentru a face scroll, se face click pe bara
de scroll sau se face click stânga pe modulul de a fișare, se tine apăsat și se deplasează cursorul
mouse -ului.

25

Inițial, butonul de salvare este dezactivat, deoarece nu au fost efectuate modificări. După ce
se generează un test, butonul „Save” va deveni activ, iar utilizatorul va putea să salveze testul c urent
sau să îl folosească fără să î l salveze. Dacă un test a fost modificat, numărul de clustere va 0, iar
utilizatorul va fi blocat pe tab -ul de generare până când setează un număr de clustere. Dacă numărul
de clustere este 0, butonul de salvare va fi de zactivat. Dacă numărul de clustere este mai mare decât
0, iar pe testul curent s -au efectuat modificări sau s -a generat un nou test, butonul „Save” va deveni
activ. Pentru a genera un set de date gol, se setează numărul de puncte sau numărul de clustere 0 și
se apasă butonul de generare. În Figura 7, testul curent a fost modificat, drept urmare, numărul de
clustere a fost șters (setat 0) și butonul de salvare a fost dezactivat.
Figura 8. Modulul de rulare algoritmi

În Figura 8 este prezentat modulul de ru lare. În acest modul se pot modifica culorile
fundalului folosind sliderele din imagine. Culorile sunt în sistemul RGB, iar fiecare slider modifică una
din componentele acestui sistem. Culoarea fundalului se modifică în timp real. Mai jos se observă o
case tă de text și două săgeți pentru schimbarea valorii din aceasta. Numărul din casetă reprezintă un
id al unei culori. În Figura 8, sunt prezente 5 culori, 3 culori sunt folosite pentru reprezentarea
clusterelor, o culoare (galben) pentru reprezentarea parti culei cu valorile cele mai bune . Cea de -a
cincea culoare (roz) este folosită pentru a identifica o particulă atunci când se trece cu mouse -ul
peste un punct din aceasta. Pătratul colorat de sub caseta de text reprezintă culoarea pentru id -ul
din aceasta. L a modificarea id -ului din casetă, culoarea pătratului se modifică într -o culoare dată de
id, iar pozițiile sliderelor se modifică pentru a indica această culoare.
Caseta de text din dreptul textului „Delay” reprezintă timpul în milisecunde dintre două
iterații. Valoarea acestei casete se poate modifica făcând click pe aceasta și introducând datele de la
tastatură sau apăsând pe săgețile din dreptul acesteia care cresc sau scad durata întârzierii cu 100

26
milisecunde. Această casetă poate fi modificată când al goritmul nu rulează, dar și în timpul rulării
unui algoritm, durata modificându -se instantaneu.
Atunci când b utonul „Select Test” este apăsat , se afișează o listă cu toate testele disponibile.
După ce s -a selectat un test, această listă dispare, testul este încărcat în modulul de afișare și
particulele algoritmului curent sunt resetate. Resetarea constă în ștergerea particulelor curente și
generare a unor particule noi care să corespundă testului selectat . Lista poate fi ascunsă dacă se
selectează un test sau dacă se apasă tasta „ESC”.
Pentru a schimba algoritmul curent, se apasă butonul „Select Algorithm”. Acest buton
afișează o listă de algoritmi s tandard și algoritmi modificați. La selectarea unui algoritm, particulele
algoritmului sunt generate și se încarcă parametrii salvați pentru algoritmul selectat. Parametrii pot
fi modificați folosind butonul „Edit parameters”. Acest buton deschide o f ereas tră cu mai mulți
parametri . În funcție de algoritmul selectat, parametrii sunt activați sau dezactivați. Parametrii
activați pot fi modificați când se face click pe aceștia. Dacă se dorește salvarea modificărilor, se
apasă butonul „OK”. Dacă se dorește ren unțarea la modificări, se apasă butonul „Cancel”, iar
parametrii revin la valorile salvate anterior sau la valorile implicite dacă nu au fost efectuate
modificări.
Butoanele „Dunn ”și „Davies Bouldin” sunt folosite pentru a schimba indicele de validare. În
Figura 8, indicele utilizat este Davies Bouldin. La selectarea butonului „Dunn”, acesta va fi activat, iar
butonul „Davies Bouldin” nu va mai fi activat. La schimbarea indicelui de validare, toți algoritmii vor
fi înștiințați de această modificare și vor actualiza local indicele de validare. La activarea unui indice
diferit, se va activa același indice și în modulul de comparare.
Butonul „Start” începe rularea algoritmului folosind algoritmul curent, parametrii pentru
acesta și indicele selectat. În timpul rulării, pozițiile particulelor din modulul de afișare vor fi
actualizate după fiecare iterație. La apăsarea acestui buton, acesta se va modifica într -un buton de
oprire, „Stop”. Algoritmul va rula până când se apasă acest buton sau până când se selecteaz ă un
test nou, un algoritm nou sau se apasă pe butonul „Next Step” sau butonul „Reset”. Butonul „Next
Step” rulează o singură iterație pentru algoritmul și testul curent, după care așteaptă următoarea
comandă, fără a rula în continuare. Butonul „Reset”, re setează toți algoritmii la valorile implicite,
selectează algoritmul PSO standard, indicele de validare Dunn și generează particulele.
Pe ecran, apar mai multe puncte cu o culoare foarte deschisă. Aceste puncte reprezintă
particulele algoritmului. Pentru a afișa aceste puncte, se apasă butonul „Show all points”, iar pentru
a le ascunde, se apasă butonul „Hide points”. După apăsarea butonului „Show all points”, acesta se
modifică în „Hide points”. Pentru a vedea o particulă, se pune cursorul peste unul din p unctele
deschise la culoare și toate punctele asociate acelei particule vor fi c olorate cu roz, ca în Figura 8. În
partea stângă sus se poate vedea valoarea funcției de fitness, în cazul nostru valoarea returnată de
indicele de validare pentru iterația cur entă, iar în partea dreaptă sus a modulului de afișare se poate
vedea numele algoritmului și numele testului selectat , separate prin „ -”.
Butonul „Exit” este prezent în fiecare modul și acesta poate fi apăsat în orice moment de
timp. La apăsarea acestui bu ton, resursele alocate sunt eliberate, iar aplicația este închisă. Deoarece
foarte multe resurse sunt eliberate la apăsarea acestui buton, se recomandă oprirea aplicației prin
intermediul acestuia, deoarece în felul acesta, gradul de fragmentare al memorie i nu va fi modificat.
Dacă aplicația este închisă folosind combinația de taste „Alt + F4” sau folosind task manager -ul,
memoria nu va fi eliberată.

27

6. Rezultate experimentale

Algoritmii ce folosesc pondere de inerție, au valoarea inițială a ponderii egală cu 0.9 pentru a
favoriza o căutare locală și scade la fiecare iterație până la valoarea 0.5 pentru a favoriza o căutare
globală [9]. Pentru o eficiență cât mai bună a algoritmului PSO cu factor de comprimare, valoarea
acestui factor trebuie să fie K = 0.72984, iar c1 = c2 = 2.05 , factorul fiind calculat folosind formula (4)
[11]. Testele de mai jos au fost rulate pe un număr de 20 de cicluri și 100 de iterații, deoarece
indicele Dunn necesită mult timp pentru o iterație, iar daca s -ar realiza un număr mare de iterații,
acesta va avea nevoie de multe ore pentru a termina toate cele 20 de rulări.

6.1. Set de date cu clustere bine separate
Figura 9. Testul 1 cu clustere bine separate

Acest test este format din 3 clustere foarte bine separate și este utilizat pentru a verifica
dacă algoritmii funcționează cum trebuie. Algoritmii de inteligență a roiurilor nu au probleme în
găsirea soluției, în schimb, algoritmul k -means întâmpină dificultăți, deoarece centroizii inițiali sunt
aleși aleator , iar poziția unui centroid se modifică în funcție de punctele din setul de date ce aparțin
centroidului . Fiecare algoritm este rulat de mai multe ori, iar la final se păstrează rezultatul pentru
rularea care a ajuns la un rezultat cât mai bun. După un număr semnificat iv de rulări pe testul din
Figura 9, toți algoritmii realizează o clusterizare corectă .
Pentru a recrea acest test, se gener ează un test gol, după care se editează din aplicație sau
se creează un fișier text în care sunt trecute pe prima linie numărul de p uncte ce vor fi generate, pe a
doua linie numărul de clustere, iar pe următoarele linii coordonatele punctelor separate prin virgulă.
Clusterele pot fi poziționate oriunde, atâta timp cât distanțele dintre oricare două clustere sunt
aproximativ egale și clusterele se află la o distanță mare unul de celălalt.

28

6.2. Set de date cu un cluster bine separat și două clustere apropiate

Figura 10. Testul 2 cu două clustere apropiate și unul îndepărtat

Testul din Figura 10 este puțin mai provocator decât primul test. Acest test verifică dacă
algoritmii pot să deosebească bine clusterele. Deoarece cele două clustere sunt la o distanță mică
unul de celălalt, la folosirea indicelui Davies Bouldin, algoritmul CSO va avea dific ultăți în găsirea
clusterizării corecte, acesta ajungând la convergență după un număr de iterații mult mai mare decât
ceilalți algoritmi. Dacă se adaugă o pondere de inerție la acest algoritm, convergența se va realiza
mai rapid. La utilizarea indicelui Du nn, toți algoritmii ajung la convergență după un număr foarte mic
de iterații.
Pentru a reproduce acest test, se vor genera două clustere cu o distanță mică între ele și un
cluster mai îndepărtat , la o distanță aproximativ egală față de celelalte clustere. În Figura 10,
clusterele au fost colorate în urma rulării algoritmului PSO, fiecare clu ster având o culoare unică.
Clusterele trebuie să fie circulare, iar numărul de puncte generate nu trebuie să fie identic cu
numărul de puncte din imagine. Cel mai simp lu mod de a genera acest test este folosirea editorului
de teste din aplicație.
Dacă în pasul inițial, doi dintre cent roizi sunt generați în clusterul îndepărtat, algoritmul k –
means va converge către o clusterizare greșită. Algoritmii de inteligență a roiurilor nu depind de
poziția inițială a particulelor. Aceștia aleg dintr -un număr mare de particule, o particulă care
realizează clusterizarea cea mai bună, iar celelalte particule se vor deplasa spre această particulă
până când o clusterizare mai bună e ste găsită. Fiecare particulă din algoritmul PSO ține cont și de cea
mai bună poziție în care a realizat clusterizarea cea mai bună atunci când își actualizează poziția.

29

6.3. Set de date cu clustere mari, dar înguste, poziționate circular
Figura 11. Testul 3 cu clustere sub formă de săgeți

Testul din Figura 11 conține un set de date ce favorizează algoritmul k -means. Indiferent de
pozițiile centroizilor inițiali, algoritmul k -means va ajunge întotdeauna la o clusterizare corectă.
Deoarece indicii de validare folosesc diametrele clusterelor și distanțele dintre acestea, valoarea
obținută de k -means nu este valoarea cea mai bună. Algoritmii de inteligență a roiurilor ajung cu
greu la o clusterizare corectă, iar valoarea returnată de indicii de validare pentru acești algoritmi
este mai mică pentru o clusterizare apropiată de cea corectă decât valoarea returnată pentru k –
means.
Setul de date are punctele poz iționate într -o formă asemănătoare cu simbolul pentru
reciclare. Testul conține trei clustere sub formă de săgeți, fiecare indicând către următorul cluster.
Distanțele dintre clustere nu sunt mari, dar clusterele sunt liniar separabile. Pentru a reproduce
acest test, se generează trei clustere sub formă de săgeți puțin curbate, de o grosime medie și cu o
distanță mare față de un punct imaginar ce se află la o distanță egală față de fiecare cluster.
Setul de date din Figura 11 a fost clusterizat folosind alg oritmul k -means, fiecare cluster
având o culoare unică. Indiferent de poziția inițială a centroizilor, fiecare centroid va avea puncte din
maxim două clustere, poziția unui centroid modificându -se către clusterul care are numărul cel mai
mare de puncte as ociate centroidului. După un număr mic de iterații fiecare centroid va avea
asociate puncte dintr -un singur cluster. Deoarece în algoritmii de inteligență a roiurilor particulele se
deplasează parțial aleator, aceștia ajung foarte greu la soluția corectă. În cazul folosirii unei ponder i
de inerție sau a unui factor de comprimare pentru algoritmul PSO, dacă după un număr de iterații,
poziția globală sau cea locală nu se mai îmbunătățe sc, viteza se va stabiliza și va fi apropiată de 0.
Dacă până în acel momen t nu s -a ajuns la soluția corectă, algoritmul nu va mai ajunge la o
clusterizare corectă în acea rulare.

30

6.4. Set de date cu clustere apropiate

Figura 12. Testul 4 cu clustere apropiate

Figura 12 conține un set de date format din 3 clustere aflate la o distanță foarte mică unul de
celălalt. Acest algoritm defavorizează algoritmii CSO . Algoritmul k -means este mai rapid decât ceilalți
algoritmi pe acest test , deoarece distanța este foarte mică între clustere, iar centroizii se deplasează
foarte ușor de la un cluster la altul dacă e nevoie. Algoritmul CSO ajunge la o soluție corectă cel mai
greu, deoarece particulele acestui algoritm se deplasează parțial aleator, pe când la PSO, acestea se
deplasează către un local best sau un global best.
Pentru a reproduce acest test, se generează în editorul aplicației 3 clustere la o distanță
foarte mică unul de celălalt. Aceste clustere trebuie să aibă o formă rotundă , deoare ce indicii de
validare folosesc distan ța euclidiană pentru a calcu la distanț a dintre două clustere. În editorul de
teste al aplicației se pot genera punctele apropiate, atâta timp cat distanța dintre clustere este mică.
La încărcări ulterioare ale testului generat, punctele vor fi normalizate . Dacă la generare, clusterele
au fost generate în centru l modulului de afișare , la o distanță mică unul de celălalt , distanța di ntre
puncte va fi mărită, iar punctele vor arăta ca în Figura 12.
Algoritmii modificați ajung mai repede la soluția corectă decât cei standard. Acest lucru se
întâmplă, deoarece aplicând o pondere de inerție sau un factor de comprimare algoritmului PSO,
„explozia de particule” specifică acestui algoritm va fi controlata, iar particulele vor găsi mai ușor o
soluție corectă. La algoritmul CSO, particulele se deplasează parțial aleator, fiind principalul motiv
pentru care algoritmul converge mai greu decât ceilalți. Pentru acest test, adă ugarea unei ponderi
de inerție algori tmul ui CSO, aduce o îmbunătățire foarte mică față de algoritmul standard CSO.
Viteza de convergență atunci când se utilizează ponderea de inerție este puțin mai mare când se
utilizează ponderea de inerție . Distanța mică dintre clustere îngreunează procesul de clusterizare al
algoritmilor, viteza de convergență fiind mai mică decât la testele anterioare.

31

6.5. Set de date cu clustere pătrate sau dreptunghiulare

Figura 13. Testul 5 cu clustere dreptunghiulare

Acest test a fost realizat pentru a studia comportamentul algoritmilor atunci când clusterele
sunt de formă pătrată sau dreptunghiulară . În urma rulării algoritmilor pe acest set de date s -a
constatat că durează mai mult clusterizarea pe clustere dreptunghiulare decât pe clustere rotunde.
Unul din principalii factori care influențează viteza de convergență este metoda de calculare a
distanței. Distanța euclidiană c alculează distanța dintre două puncte. În calculul diametrul ui
clusterelor , distanța dintre punctele extreme clusterului va fi diagonala dreptunghiului . Distanța
dintre oricare două puncte extreme, diametral opuse, variază foarte mult .
Pentru a reproduce acest test, se generează trei clustere în formă de pătrat, la distanțe nu
foarte mari unul de celălalt. În acest test, conturul clusterul ui este mult mai important decât ce se
află în interiorul acestuia, de aceea numărul de puncte din interior poate să fie foarte mic. Diametrul
clusterelor trebuie să fie mai mare decât distanța dintre acestea pentru a obține rezultate
asemănătoare cu cele obținute în această lucrare.
Testul din Figura 13, deși este asemănător cu testul din Figura 12, algoritmii au nevoie de
mai puțin timp pentru a ajunge la soluția corectă , la rularea pe testul din Figura 13 decât pe cel din
Figura 12. În acest test, algori tmii modificați obțin performanțe mai bune decât cei standard.
Algoritmul k -means are rulări în care îi este imposibil să ajungă la soluția corectă. Acest lucru se
datorează faptului că centroizii inițiali sunt poziționați aleator și pot fi poziționați doi în același
cluster. Când se întâmplă acest lucru, un clu ster este împărțit în două, doi centroizi iau câte o
jumătate, iar cel de -al 3-lea centroid ia cele două clustere rămase. Testul din Figura 13 a fost rulat
folsind algoritmul PSO cu factor de comprimare, obținându -se un rezultat corect foarte rapid,
clusterele fiind colorate cu o culoare unică.

32

6.6. Set de date cu clustere cu forme neregulate

Figura 14. Testul 6 cu clustere cu forme neregulate

Setul de date di n Figura 14 a fost realizat, la fel ca și testul 11, pentru a studia
comportamentul algoritmilor pentru diferite forme ale clusterelor. Acest test favorizează algoritmul
PSO cu factor de comprimare și algoritmul CSO cu pondere de inerție . Algoritmul PSO cu factor de
comprimare are viteza de convergență cea mai mare pentru acest test, pe când algoritmul PSO cu
pondere de inerție are viteza de convergență mai mică decât algoritmul standard . Algoritmul CSO
standard ajunge la convergență după un număr de 80 de iterații, iar prin utilizarea unei ponderi de
inerție, convergența va avea loc până în 20 de iterații.
Pentru a reconstitui acest test, se vor genera trei clustere sub formă de obiecte cunoscute cu
forme neregulate. În generarea testului, c lusterul verde p oate fi considerat o mini navă spațială,
clusterul roșu poate fi considerat a fi o pisică, iar clusterul albastru poate fi considerat a fi un pom.
Clusterul albastru trebuie să fie cât mai mare, pentru a încurca algoritmii în găsirea clusterelor.
Deoarece dimensiunile clusterelor variază, diametr ele acestora v or fi, de asemenea, variabil e, iar în
procesul de clusterizare, un centroid va avea asocia te puncte din clusterele mici și puncte din
clusterul mare .
În acest test, toți algoritmii de inteligență a roiurilor ajung destul de repede la o soluție
corectă . Algoritmul k -means are o probabilitate foarte mare de a genera la pasul inițial doi centroizi
în clusterul mare, ceea ce duce la o convergență către o soluție greșită. Pe durata a celor 20 de
rulări, a lgoritmul reușește cel puțin o dată sa ajungă la o clusterizare corectă. Algoritmii de
inteligență a roiurilor obțin o clusterizare mai bună decât algoritmul k -means, conform indicelui de
validare a clusterizării, Davies Bouldin .

33

6.7. Set de date ce conț ine cinci clustere
Figura 15. Testul 7 cu 5 clustere

Acest test a fost realizat pentru a verifica performanțele algoritmilor atunci când se
utilizează mai multe clustere, situate la distanță mică unul față de celălalt. Figura 15 conține 5
clustere care nu favorizează algoritmii cu pondere de inerție . Algoritmii standard au o viteză de
convergență către soluția corectă mai mică decât algoritmii modificați. Algoritm ul PSO cu factor de
comprimare este mult mai rapi d decât ceilalți algoritmi pe acest test.
Pentru a reproduce acest test, se vor genera cinci clustere pozițion ate în formă de V, cu
distanțe mici între acestea. Distanța dintre clustere nu trebuie să depășească diametrele clusterelor.
Pentru indicele Davies Bouldin, nu se obțin rezultate bune pent ru algor itmul CSO cu pondere de
inerție, în schimb, pentru indicele Dunn, toți algoritmii converg către soluția corectă, algoritmii
modificați având o viteză mai mare de convergență decât ceilalți algoritmi.
Deoarece distanțele dintre clustere sunt mici, s e ajunge mai greu la convergență pentru
indicele Davies Bouldin. Acest indice încearcă să deplaseze centroizii cât mai spre centrul clusterelor.
Pe parcursul acestui proces, algoritmii pot ajunge la soluția corectă înainte de a ajunge la
convergență, dar d eoarece indicele încearcă sa aducă punctele în centrul clusterelor, algoritmii pot
părăsi soluția corectă în favoarea uneia apropiata de cea corectă, irosind câteva iterații. Acest indice
efectuează calculele mai rapid decât Dunn, dar are nevoie de mai mul te iterații pentru a ajunge la
soluția corectă, în schimb Dunn efectuează calculele mai încet, dar ajunge la soluția corectă mult mai
repede decât Davies Bouldin atunci când clusterele sunt bine separate .

34

6.8. Set de date ce conține șapte clustere

Figura 16. Testul 8 cu 7 clustere

Cu cât numărul de clustere este mai mare, cu atât algoritmii vor avea dificultăți mai mari în a
găsi soluția corectă. În ca zul setului de date din Figura 16 algoritmul PSO standard ajunge mai greu la
soluția corectă, deo arece viteza de deplasare este mare și poate trece pe lângă global best sau local
best. Distanțele dintre clustere sunt mari, iar indicele Dunn conduce algoritmul mai rapid spre
convergență decât indicele Davies Bouldin.
Acest test a fost generat folosind generatorul din aplicație. Singurul parametru ce a fost
modificat din lista de parametrii impliciți a fost cel pentru numărul de clustere. Pentru a obține un
test asemănător, se poate genera un test folosind generatorul d e teste și apoi edita puțin sau se
poate genera un test gol ce va fi editat să arate asemănător cu cel d in Figura 16. Pentru a obține un
test asemănător mai rapid folosind generatorul se poate modifica limita de puncte sau se pot
micșora intervalele pentru distanța dintre clustere sau pentr u diametrele clusterelor.
Acest set de date favorizează algoritmii PSO modificați, deoarece acești algoritmi au o viteză
de convergență mult mai mare decât ceilalți algoritmi, iar viteza se stabilizează foarte repede. Viteza
acestor algoritmi se stabilize ază de cele mai multe ori la o soluție apropiată de cea corectă. Pe acest
test, deoarece clusterele sunt bine separate, algoritmii ajung la o soluție corectă rapid atunci când se
rulează de un număr mai mare de ori.

35

6.9. Rezultate obținute
Tabelul 1
Rezultatele obținute pentru testele 1 -3, folosind indicele Dunn
Testul 1 Testul 2 Testul 3
PSO 2.707001 0.342978 0.381359
PSO cu pondere de inerție 2.707001 0.342978 0.381359
PSO cu factor de comprimare 2.707001 0.342978 0.381359
CSO 2.707001 0.342978 0.381359
CSO cu pondere de inerție 2.707001 0.342978 0.381359
k-means 2.707001 0.342978 0.381359

Testul 1 conține setul de date din Figura 9. Deoarece clusterele sunt foarte depărtate unul
de celălalt, valoarea returnată de indicele Dunn este foarte mare. Validarea clusterizării folosind
acest indice depinde foarte mult de diametrul clusterelor și de distanțele dintre acestea. Scopul
acestui test este de a verifica funcționalitatea algoritmilor . După cum se observă în Tabelul 1, toți
algoritmii ajung la aceeași valoare, supraunitară, ceea ce înseamnă că a fost realizat ă o clusterizare
corectă.
La rularea algoritmilor pe setul de date din Figura 10, valoarea returnată de indicele de
validare este mică. Acest lucru se datorează faptului că distanța dintre două clustere este mai mică,
iar diametrele clusterelor apropiate sunt mai mari decât diametrele clusterului îndepărtat. Algoritmii
ajung la con vergență , realizând o clusterizare corectă. Viteza de convergență pentru testul 2 este
mai mică decât cea pentru testul 1, deoarece clusterele nu sunt foarte bine separate.
Testul 3 folosește setul din Figura 11 și favorizează algoritmul k -means. Pentru in dicele de
validare Dunn, toți algoritmii ajung la convergență foarte rapid, iar rezultatul obținut este cel pentru
o clusterizare corectă. Deoarece distanța dintre clustere este mică, dar diametrul clusterelor este
mare, valoarea returnată pentru o cluster izare corectă este mai mare decât valoarea returnată în
cazul testului 2, unde diametrul clusterelor este mai mic. În graficul din Figura 17 se poate observa
evoluția testului 3 pentru indicele Dunn .

Figura 17. Grafic pentru testul 3 folosind indicele Dunn

36

Tabel ul 2
Rezultate obținute pentru testele 1 -3, folosind indicele Davies Bouldin
Testul 1 Testul 2 Testul 3
PSO 0.155885 0.402676 0.46 3141
PSO cu pondere de inerție 0.15468 2 0.4023 23 0.460 442
PSO cu factor de comprimare 0.154 681 0.40231 7 0.460 031
CSO 0.185895 0.424778 0.469972
CSO cu pondere de inerție 0.183851 0.415121 0.473382
k-means 0.156630 0.465702 0.532605

Indicele Davies Boul din încearcă să aducă centroizii în centrul clusterelor . Acest indice
returnează o valoare mică pentru o clusterizare corectă. În Tabelul 2, se observă că algoritmii PSO
obține performanțe mai bune pe un set de date cu clustere aflate la distanțe mari decât algoritmii
CSO și k -means. La rularea algoritmilor de inteligență a roiurilor pentru pe setul de date din testul 1,
toți algoritmii realizează o clusterizare corectă pentru după un anumit număr de rulări. Algoritmul k –
means depinde foarte mult de poziția inițială a centroizilor, iar dacă la pasul inițial doi centroizi sunt
generați în același cluster, algoritmul nu va ajunge să găsească o clusterizare corectă .
La rularea algoritmilor pe testul 2, toți algoritmii reușesc să ajungă la soluția corectă, iar
modificările aduse algoritmilor de inteligență a roiurilor nu îmbunătățesc cu mult performanțele.
Algoritmii PSO ajung mai repede la convergență decât ceilalți algoritmi, algoritmul CSO fiind cel care
ajunge ultimul la convergență după un număr de aproximativ 80 iterații. La adăugarea unei pon deri
de inerție pentru algoritmul CSO, acesta va ajunge la convergență după un număr mai mic de iteraț ii,
aproximativ 60 de iterații, dar clusterizare a obținută este puțin mai slabă, conform indicelui Davies
Bouldin.
Testul 3 este favorabil pentru algorit mul k -means. Deși acest algoritm obține o clusterizare
corectă, indicele de validare , deoarece încearcă sa mute centroizii cât mai aproape de centrul
clusterelor, nu returnează valoarea cea mai mică pentru acest algoritm . Algorit mii de inteligență a
roiuri lor au dificultăți în găsirea soluției corecte pentru acest test. După cum se vede în Figura 18,
variantele modificate ale algoritmilor obțin un rezultat mai rapid decât variantele standard.
Figura 18. Grafic pentru testul 3 folosind indicele Davies Bouldin

37

Tabel ul 3
Rezultatele obținute pentru testele 4 -6, folosind indicele Dunn
Testul 4 Testul 5 Testul 6
PSO 0.279692 0.429850 0.303287
PSO cu pondere de inerție 0.279692 0.429850 0.303287
PSO cu factor de comprimare 0.279692 0.429850 0.303287
CSO 0.279692 0.429850 0.303287
CSO cu pondere de inerție 0.279692 0.429850 0.303287
k-means 0.279692 0.429850 0.303287

Testul 4 folosește setul de date din Figura 12, în care clusterele se află la o distanță mică .
Clusterele din acest test au un diametru mare, de aceea valoarea returnată de indicel e Dunn este
așa mică. Folosind indicele Dunn, fiecare algoritm ajunge la o clusterizare corectă. Algoritmul CSO
ajunge mai greu la clusterizarea corectă, pe când algoritmul CSO cu pondere de inerție ajunge mult
mai repede la soluția corectă. Singurul algoritm modificat care are performanțe mai proaste decât
algoritmul standard pentru acest test este algoritmul PSO cu pondere de inerție. Acest algoritm are
nevoie de mai multe iterații decât algoritmul standard pentru a ajunge la convergență. Evoluția
acestui test poate fi observată în graficul din Figura 19.
Algoritmii rulați pe testul 5, care conține setul de date din Figura 13, obțin performanțe
foarte bune, chiar dacă forma clusterelor nu este rotundă. Acest test este în defavoarea algoritmului
CSO cu pondere de inerție, deoarece acest algoritm are nevoie de mai multe iterații decât algoritmul
standard CSO pentru a ajunge la convergență. Pentru numărul de rul ări ales, toți algoritmii ajung la
aceeași valoare de convergență .
Testul 6 folosește setul de date din Figura 14, care conține clustere cu forme neregulate și de
diametre diferite. Algoritmii întâmpină mici dificultăți, deoarece centroizii asociați clusterelor cu
diametru mic grupează și puncte din clusterul cu diametrul cel mai mare. Valoarea returnată de
indicele Dunn este mică, deoarece distanța dintre clustere este mică. Toți algoritmii ajung la soluția
corectă, algoritmul k -means având puține di ficultăți în găsirea acestei soluții.

Figura 19. Grafic pentru testul 4 folosind indicele Dunn

38

Tabelul 4
Rezultatele obținute pentru testele 4 -6, folosind indicele Davies Bouldin
Testul 4 Testul 5 Testul 6
PSO 0.526 417 0.473 253 0.407381
PSO cu pondere de inerție 0.525909 0.472608 0.407002
PSO cu factor de comprimare 0.525909 0.472608 0.407002
CSO 0.531195 0.482173 0.411933
CSO cu pondere de inerție 0.531947 0.478360 0.429877
k-means 0.633911 0.549054 0.457604

La rularea algoritmilor pe testul 4, algoritmii PSO obțin performanțe mai bune decât
algoritmii CSO. Modificările aduse algoritmilor aduc îmbunătățiri foarte mici pentru numărul de
iterații selectat. Algoritmii CSO ajung la convergență pentru acest test după un număr de
aproximativ 90 iterații, viteza fiind foarte mică în comparație cu ceilalți algoritmi care ajung la
convergență în mai puțin de 20 de iterații. Algoritmii realizează o clusterizare core ctă pentru o
valoare a indicilor mai mică decât 0.55 , excepție făcând algoritmul k -means care deși realizează o
clusterizare corectă, valoarea indicelui este mai mare . În graficul din Figura 20 se poate observa
evoluția acestui algoritmilor pe acest test.
Algoritmii rulați pe testul 5, care este asemănător cu testul 4, reușesc s ă obțină toți o soluție
corectă într -un timp mai scurt. Singura diferență dintre cele două teste este forma clusterelor și
distanța acestea. Modificările algoritmilor PSO aduc o vite ză de convergență mai mare pentru
algoritmul PSO cu pondere de inerție decât în testul 4 , iar modificările aduse algoritmului CSO
îmbunătățesc cu mult performanțele acestuia.
Testul 6 folosește clustere cu forme neregulate. Clusterele cu alte forme decât cele rotunde
sau sferice nu afec tează foarte mult algoritmii de inteligență a roiurilor . Aceștia ajung la convergență
după aproximativ 20 de iterații, excepție făcând algoritmul standard care ajunge la convergență
după 80 de iterații. După cum se observă î n Tabelul 4, algoritmii PSO obțin la finalul celor 100 de
iterații o clusterizare mai bună decât ceilalți algoritmi.
Figura 20. Grafic pentru testul 4 folosind indicele Davies Bouldin
Tabelul 5

39

Rezultatele obținute pentru testele 7 -8
Dunn Davies Bouldin
Testul 7 Testul 8 Testul 7 Testul 8
PSO 0.574556 0.670179 0.415282 0.384319
PSO cu pondere de inerție 0.574556 0.670179 0.346897 0.397736
PSO cu factor de comprimare 0.574556 0.670179 0.345655 0.402876
CSO 0.574556 0.670179 0.468297 0.684532
CSO cu pondere de inerție 0.574556 0.670179 0.513047 0.665109
k-means 0.574556 0.670179 0.359480 0.286295

Se observă din Tabelul 5 că toți algoritmii ajung la aceeași valoare de convergență pentru
indicele Dunn. Testul 7 conține setul de date din Figura 15, iar testul 8 conține setul de date din
Figura 16. În graficul din Figura 21, se observă că algoritmii de inteligență a roiurilor modificați ajung
mai r apid la soluția corectă decât ceilalți algoritmi pentru testul 7, iar algoritmii standard reușesc să
ajungă la soluția corectă după un număr de aproximativ 50 iterații.
Atunci când se utilizeaz ă indicele Davies Bouldin pentru testul 8, cel mai bun rezultat este
obținut la aplicarea algoritmului k-means . Algoritmul standard CSO are o viteză de convergență mai
mare decât algoritmul CSO cu pondere de inerție. La rularea algoritmilor pe testul 7, algoritmii PSO
modificați obțin performante mai bune decât ceilalți algoritmi, iar algoritmul CSO cu pondere de
inerție obține cele mai slabe rezultate. Pentru testu l 8, algoritmii toți algoritmii PSO obțin rezultate
mai bune decât algoritmii CSO, iar viteza de convergență a algoritmilor PSO este mult mai mare
decât cea a algoritmilor CSO.
Singurii algoritmi care reușesc să ajungă la o soluție corectă atunci când se utilizează
indicele Davies Bouldin sunt algoritmii PSO și algoritmul k -means . Algoritmii CSO nu reușesc să
realizeze o clusterizare corectă pentru numărul de iterații specificat. Algoritmul k -means obține cel
mai bun rezultat, deoarece acest algoritm modifică poziția centroizilor în funcție de media punctelor
asociați acestuia. Atunci când un centroid are asociate toate punctele clusterului, acesta se va
deplasa către centrul clus terului după ce calculează o medie a punctelor, obținând cea mai bună
valoare a indicelui.
Figura 21. Grafic pentru testul 7 folosind indicele Dunn

40
7. Concluzii și dezvoltări ulterioare

Algoritmii de inteligență a roiurilor obțin rezultate mult mai bune decât algoritmii clasici de
clusterizare. Aceștia au o probabilitate mult mai mare să ajungă la o soluție corectă decât algoritmul
k-means utilizat în această lucrare. Variantele modificate ale algoritmilor de inteligență a roiurilor nu
returnează mereu re zultate mai b une decât algoritmii standard. În majoritatea cazurilor, algoritmul
CSO cu pondere de inerție ajunge la o clusterizare corectă mult mai repede decât algoritmul CSO
standard.
Indicele de validare Dunn reușește să aducă algoritmii la o soluție c orectă pe toate testele pe
care rulează. Acest indice este foarte bun pentru clusterizarea datelor, dar are și un mare
dezavantaj. Pentru un număr mare de puncte din setul de date, acest indice necesită un timp foarte
mare pentru fiecare iterație. Indicel e Davies Bouldin este mult mai rapid decât indicele Dunn, dar
algoritmii au nevoie de un număr mai mare de iterații pentru a ajunge la o soluție corectă.
Pentru seturile de date în care clusterele sunt situate la distanțe mari unul de celălalt,
algoritmii au o viteză de convergență foarte mare către soluția corectă. Atunci când se micșorează
distanța dintre clustere, viteza de convergență a algoritmilor scade, la fel și performanța acestora.
Pentru clustere cu forme pătrate, dreptunghiulare sau neregulate, viteza de convergență a
algoritmilor de inteligență a roiurilor nu se modifică foarte mult. Algoritmii PSO modificați obțin în
cele mai multe cazuri, valori ale indicilor de validare a clusterizării mult mai bune decât algoritmii
CSO. Acești algoritmi au o viteză foarte mare de convergență în toate testele efectuate.

Indicele de validare Dunn necesită foarte mult timp pentru validarea clusterizării atunci când
sunt rulate teste cu foarte multe puncte . Compararea algoritmilor durează foarte mult, iar p entru un
număr de 1000 iterații și 50 de rulări, procesul de comparare poate dura până la 2 zile. Aplicația
funcționează corect doar atunci când este rulată din visual studio. Când aplicația este rulată folosind
executabilul, câteva funcționalități nu produc rezultatul dorit .
Pe viitor, doresc să îmbunătățesc performanțele algoritmilor, să măresc viteza indicelui de
validare Dunn și să fac toate funcționalitățile aplicației să producă rezultatul dorit atunci când se
pornește aplicația folosind executabilul , pentru a putea utiliza această aplicație și pe alte
calculatoare.

41
Bibliografie

1. A. K. Jain, R . C. Dubes, „Algorithms for Clustering Data” , Prentice Hall, 1988, pag . 1-3
2. G. Gan , „Data Mining and Knowledge Discovery Series” , CRC Press, 2011, pag. 3 -4
3. F. Kovács, C . Legány, A . Babos , „Cluster Validity Measurement Techniques ”, http://uni –
obuda.hu/conferences/mtn2005/KovacsFerenc.pdf
4. A.K. J ain, M.N. M urty, P.J. F lynn , „Data Clustering: A Review” , ACM Computing Surveys, Vol.
31, No. 3, September 1999 , pag. 265 -323
5. C. C. Aggarwal, C . K. Reddy, „Data Clustering Algorithms and Applications , CRC Press, 2013 ,
pag. 100 -101
6. O.A. Mohamed Jafar and R. Sivakumar , „Ant-based Clustering Algorithms: A Brief Survey ”,
International Journal of Computer Theory and Engineering, Vol. 2, No. 5, October, 2010 , pag.
787-796
7. K. Keshtkar Mizooji, A . T. Haghighat, R . Forsati „Data Clustering Using Bee Colony
Optimization” , The Seventh International Multi -Conference on Computing in the Global
Information Technology , June 24 -29, 2012, Venice, Italy , pag. 189 -190
8. S. Das, A. Chowdhury and A. Abraham, „A Bacterial Evolutionary Algorithm for Automatic
Data Clustering”,
http://ieeexplore.ieee.org/ielx5/4939002/4982922/04983241.pdf?tp=&arnumber=4983241
&isnumber=4982922
9. X. S. Yang, Engineering Optimization: An Introduction with Metaheuristic Appl ications, John
Wiley & Sons, 2010, pag. 203 -205
10. M. A. Montes de Oca, „Particle Swarm Optimization ”, IRIDIA -CoDE, Universit´e Libre de
Bruxelles (U.L.B.), May 7, 2007, pag. 8 -22
11. R. M. Chen, H. F. Shih, „Solving University Course Timetabling Problems Using C onstriction
Particle Swarm Optimization with Local Search”, Algorithms, Vol.6, Issue 2 , 2013, pag. 228 –
244
12. S. C. Chu, P . W. Tsai, „Computational Intelligence Based on the Behavior of Cats”,
International Journal of Innovative Computing, Information and Control, Volume 3, Number
1, February 2007 , pag. 16 3-173
13. Y. Liu, Y. Shen, „Data Clustering with Cat Swarm Optimization” , Journal of Convergence
Information Technology, Volume 5, Number 8, October 2010 , pag. 2 1-28
14. M. Orouskhani, Y . Orouskhani, M . Mansouri, M. Teshnehlab, „A Novel Cat Swarm
Optimization Algorithm for Unconstrained Optimization Problems” , I.J. Information
Technology and Computer Science, 2013, Vol. 11, Issue 4, 32 -41
15. J. Wu, „Advances in K -means Clustering, A Data Mining Thinking”, Springer, 2 012, pag. 9 -11

Copyright Notice

© Licențiada.org respectă drepturile de proprietate intelectuală și așteaptă ca toți utilizatorii să facă același lucru. Dacă consideri că un conținut de pe site încalcă drepturile tale de autor, te rugăm să trimiți o notificare DMCA.

Acest articol: S.l. dr. ing. Andrei -Horia Mogoș [602043] (ID: 602043)

Dacă considerați că acest conținut vă încalcă drepturile de autor, vă rugăm să depuneți o cerere pe pagina noastră Copyright Takedown.

S.l. dr. ing. Andrei -Horia Mogoș [602043]

Copyright Notice

PROMOVAREA TURISMULUI RURAL DIN JUDEȚUL BRAȘOV PRIN INTERMEDIUL SOCIAL MEDIA [305938]

Calificarea : TEHNICIAN ÎN ACTIVITĂȚI ECONOMICE NIVEL I V ÎNDRUMĂTOR: PROF . TĂNASE MIHAI ABSOLVENT: NUME : DAN VANESSA -MIHAELA CLASA a XII -a Ae B… [622443]

Spcializar e: Psihologi e Aplicată În D omeniul S ecurității Național e LUCRARE DE DIS ERTAȚI E Relația dintr e stima d e sine, cognițiil e iraționa… [614655]

Obiectul toxicologiei. Istoric. No țiunea de toxic [619228]

CAPITOLUL I: PRINCIPIUL NEDISCRIMINĂRII ȘI EGALITĂȚII 1.1. Scurt istoric Egalitatea și nediscriminare sunt concepte complexe, cu o dezbatere… [604302]

Microsoft Word – 2003 valente_format_mihai_banciu.doc [306438]

Copyright Notice

Similar Posts