Problema de Clusterizare pe Date

Problema de Clusterizare pe Date

Byadmin ianuarie 1, 2024

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 pentru 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 utilizare. Î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 dezvoltat 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 și Virtual Ant folosesc comportamentul așa-numitei inteligență a roiurilor. PSO poate avea câteva asemănări cu algoritmii genetici sau algoritmii Ant Colony, 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ă 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 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 combinarea 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 centroizi, poziția acestora fiind aleatoare. 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 pseudocodul pentru câteva dintre acestea vor fi descrise în Capitolul 4, iar în Capitolul 5 vor fi descrise pe scurt clasele cu relațiile dintre acestea și interfața grafică a aplicației. Seturile de date folosite în realizarea comparațiilor ș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. Problema de clusterizare pe date

În acest capitol sunt descrise procesul de clusterizare pe date, etapele acestuia și alte abordări pentru rezolvarea 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 clusterizare 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 model, 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ă procese: 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 transformarea atributelor 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 clusterelor 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 poate 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ări, 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ă rezultatul 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ă structura este 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. Oamenii 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 clusterele nu sunt bine separate. Un algoritm de clusterizare pe date este 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 asemenea, ș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 partiț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 contrast cu abordările convenționale de clusterizare care se ocupa cu simpla generare ș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 structurarea 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 din moment ce datele multimedia sunt pe scară largă, în dimensiuni superioare, 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 imbricate. 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 punctele 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].

Spre deosebire de algoritmii de clusterizare 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 necesar 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 algoritmii 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 fost dezvoltați, deoarece majoritatea algoritmilor de clusterizare 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. Algoritmii 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 reprezintă un punct de date sau o înregistrare, iar o latură ce unește două vârfuri reprezintă similaritatea dintre două înregistrări reprezentate 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 pentru 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 algoritmi, 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 probabilitate. 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țiilor 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 algoritmii 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 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 competitivă 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 partiț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 decizii ușoare în fiecare iterație prin 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 utilizați doi algoritmi 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 înseamnă că furnicile sunt capabile să supraviețuiască pe cont propriu. Coloniile de furnici pot manifesta o coordonare 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 celelalte 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 feromonului lăsat este unul din cei mai importanți factori pentru furnici în găsirea drumului cel mai scurt. [6]

Algoritmii de clusterizare bazați pe furnici sunt o alternativă apropiată a algoritmilor de clusterizare tradiționali. Algoritmul are abilitatea de a descoperi 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 combinatoriale dificile. Ideea principală din spatele BCO este de a crea un sistem multiagent capabil să rezolve eficient problemele de 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ând 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 colective ș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 stagiu ș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 informații despre datele clusterului cu probabilități speciale și se întoarce la stup pentru a vedea ce au descoperit celelalte 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 din 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. Aceste 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 bacteriană este aplicată pe fiecare cromozom. Operatorii de mutație ai algoritmului de clusterizare automată BEA diferă de cei ai algoritmului clasic BEA. Aceștia sunt special concepuți pentru a permite 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 bun 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 cromozomii 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 valori 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 criterii 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 reparare, unde toate genele cromozomului sunt scanate pentru a elimina datele duplicat ce apar în mai multe gene. [8]

3. Algoritmi utilizați

Acest capitol detaliază algoritmii de inteligență a roiurilor utilizați. În această lucrare sunt utilizați doi algoritmi 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ării, 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 bazat pe comportamentul în natură al bancurilor de pești și al stolurilor de păsări. Mulți algoritmi cum ar fi ACO și Virtual Ant Colony folosesc 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 obiectiv prin ajustarea traiectoriilor agenților individuali, numiți particule, pentru a forma 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 atrasă 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 tendinț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 toate 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]:

Se creează o „populație” de agenți (numiți particule) uniform definită peste spațiul de căutare

Se evaluează poziția fiecărei particule conform funcției obiectiv

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ă

Se determină cea mai bună particulă (conform pozițiilor cele mai bune ale particulei)

Se actualizează vitezele particulelor conform ecuației (1)

(1)

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

(2)

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

Există multe variante ce extind algoritmul standard PSO. În această 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.

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 valoare cuprinsă între 0.5 și 0.9. Deoarece această 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 constantei 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 (CSO)

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 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. 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 torsului ajută la repararea celulelor. [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 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 memoria 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 variate. 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 descris 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, conform 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 se î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 ținta. 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 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 maximă 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 extinderea 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 distincte în comparație cu alți algoritmi de clusterizare: este foarte simplu și robust, foarte eficient și poate fi aplicat pentru o varietate mare de tipuri de date [15]. Are și dezavantaje, cum ar fi performanța slabă pentru clusterele neglobulare și sensibilitatea 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ărui cluster este actualizat pe baza punctelor 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

Pentru 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 conFiguraț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]

(10)

Davies Bouldin returnează o valoare cât mai mică pentru o clusterizare cu o conFiguraț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

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

, unde

, centrul clusterului i (11)

Indicele de validare, Davies Bouldin, este definit de ecuația (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 conFiguraț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 încarcă modulul de afișare în care sunt afișate toate punctele din setul de date și modulul de control ce poate fi accesat numai de utilizator. Modulul 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 din 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 tabelul 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 fitness. În tabel sunt afișate doar 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”.

Utilizatorul 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ă apese 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 bara de scroll, această operație mai putând fi realizată dacă utilizatorul face click stânga 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 interoghează 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 mulț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, compararea algoritmilor sau afișarea unui tabel. Setul de date este ales dintr-o listă ce apare în modulul 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 decis în privința cărui set de date va fi utilizat 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 fost 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 buton 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ărcare ce se actualizează la fiecare iterație. Pentru a anula procesul de comparare, se va apăsa tasta „ESC” și procesul 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 interoga 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 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, iar 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 rulaț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 rulare. Acest buton va porni 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 modifică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 se 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 testului 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.

Generarea 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, se 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 eliminat 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 mare 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 test 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 algoritmi sau de setare parametri pentru algoritmi. Culorile sunt 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, vor fi activați anumiți parametri. Acești parametri pot fi modificați folosind modulul de setare parametri. Parametrii ce nu sunt necesari algoritmului curent sunt dezactivați. 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 fi descrise implementările modulelor prezentate mai sus folosind pseudocod.

4.2.1. Metoda Draw()

Această metoda este folosită pentru desenarea obiectelor și a seturilor de date.

Draw()

| Do

| | Dacă timp = 0 atunci

| | | start = timp_curent();

| | | curăță(ecran); //șterge toate obiectele de pe ecran

| | | Desenează(set_de_date, particule);

| | | Desenează(obiecte);

| | | Dacă activ(tab[i]) atunci

| | | |_ Desenează(tab[i]);

| | | Înlocuiește(eglDisplay, eglSurface); //inversează bufferele

| | | Afișează(text);

| | | Dacă activ(listă[i]) atunci

| | | |_ Afișează(text_listă[i]);

| | | Dacă activ(fereastră[i]) atunci

| | |_ |_ Afișează(text_fereastră[i]);

| | Dacă timp >= întârziere atunci

| | |_ timp = 0;

| | Altfel

|_ |_ |_ timp = timp_curent()-start;

4.2.2. Metoda Key()

Această metodă citește comenzile de la tastatură și le interpretează.

Key()

| Do

| | Dacă apăsat(cifră) și activ(casetă text) atunci

| | |_ introduce_în_casetă(cifră);

| | Dacă apăsat(BACKSPACE) atunci

| | |_ sterge_ultima_cifră_din_casetă();

| | Dacă apasat(ESC) atunci

| | |_ ascunde_liste_și_ferestre();

| | Dacă apăsat(i) atunci

| | |_ zoom_in();

| | Dacă apăsat(o) atunci

|_ |_ | _ zoom_out();

4.2.3. Metoda Mouse()

Această metodă interpretează comenzile mouse-ului

Mouse()

| Do

| | Dacă dublu_click atunci

| | |_ zoom_in();

| | Dacă click_dreapta atunci

| | |_ zoom_out();

| | Dacă click_stânga atunci

| | | Dacă apăsat(buton) atunci

| | | |_ execută(acțiune_buton);

| | | Dacă apăsat(casetă_text) atunci

| | | | activează(casetă_text); //permite adăugarea valorilor de la

| | | |_ // tastatură

| | Dacă active(listă[i]) atunci

| | | scroll(listă[i]); // actualizează poziția elementelor

| | | // din listă dacă s-a facut click pe

| | | // bara de scroll

| | | selectează(element_listă); // selectează un element din listă

|_ |_ |_ // dacă s-a facut click pe acesta

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

4.2.3.1. Metoda Generate()

Această metodă generează un set de date nou.

Generate()

| generează(centru_cluster(0,0)); // generează primul punct la coordonatele 0,0

| generează(puncte_cluster);

| generează(centru_cluster2); // generează centrul celui de-al doilea cluster

| Dacă distanța_min < distanță(centru1, centru2) < distanța_max atunci

| |_ generează(puncte_cluster);

| Altfel

| | regenerează_centru()

| |_ verifică_condiție();

| pentru număr_cluster = 2 până la număr_total_clustere

| | pentru toate clusterele_generate

| | | verifică(distanță(cluster_generat, cluster_nou)

| | | dacă distanța_min < distanță < distanța_max atunci

| | | |_ generează(centru_cluster, puncte_cluster)

| | | altfel dacă distanța_min < distanță atunci

| | | | generează(centru(min(distanțe_clustere_generate)))

| | | | // generează centru la distanța cea mai mică

| | | | // posibilă, dar mai mare decât distanța minimă

| |_ |_ |_ generează(puncte_cluster)

|_ returnează set_de_date

4.2.3.1. Metoda Compare()

Această metodă este utilizată pentru a compara algoritmii.

Compare()

| pentru fiecare algoritm_selectat

| | pentru fiecare ciclu

| | | pentru fiecare iterație

| | | | rulează(algoritm_selectat) // pseudocodul algoritmilor este

| | | | // descris în capitolul 3

| | | păstrează(cel_mai_bun_rezultat)

| | |_ reinițializează(algoritm_selectat)

| | salvează_în_fișier(rezultat)

| |_ generează_grafic()

|_ generează_tabel()

generează_grafic()

| caută_rezultat(folder_rezultate)

| dacă există(rezultat) atunci

| | citește(rezultat)

| |_ încarcă(rezultat)

| altfel

| returnează eroare_rezultat_negăsit

| dacă încărcat(toate_rezultatele) atunci

|_ |_ generează(grafic)

generează_tabel()

| generează(rânduri, coloane)

| pentru fiecare fișier_rezultate

| | deschide(fișiere)

| | citește(valoare_best)

| | inserează(informații_rulare)

| |_ inserează(valoare_best)

|_ afișează_tabel()

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 informaț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.

Clasa „Table” este folosită pentru inserarea datelor în tabel și pentru afișarea acestora 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ă. Valoarea 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 clustere, de diametrul clusterelor și de alte caracteristici ale clusterelor.

Pentru 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 clusterele. 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 un 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, utilizatorul 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 algoritmii selectați, după care se va începe generarea graficului.

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ă butonul „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 caseta 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 vede ș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 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 algoritmi. 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 apasă 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âmpla 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ă rezultate 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.

Figura 5. Fereastra de conFigurare a parametrilor algoritmilor

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ă sugestivă. 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 restul 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 caseta de text valoarea este zecimală, după prima cifră se pune automat virgulă. Când o casetă 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 pornirea aplicației. 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”.

Figura 6. Fereastra de generare grafic

Pentru a genera un grafic se apasă pe butonul „Graphic”, iar acest buton va deschide 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 „Next” ș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 constantelor 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 este ales niciun algoritm și se apasă butonul „Generate”, graficul nu va fi generat, iar fereastra de generare va fi închisă; butonul se va comporta la fel ca butonul „Cancel”.

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ă precizeze 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 mereu 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 eliminarea 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 afișare, se tine apăsat și se deplasează cursorul mouse-ului.

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 curent 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 dezactivat. 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 rulare. Î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 casetă 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 particulei 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. La 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 milisecunde. Această casetă poate fi modificată când algoritmul nu rulează, dar și în timpul rulării unui algoritm, durata modificându-se instantaneu.

Atunci când butonul „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 generarea 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 standard ș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 fereastră 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 renunț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”, resetează 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 punctele deschise la culoare și toate punctele asociate acelei particule vor fi colorate 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 curentă, 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 buton, 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 memoriei 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ă.

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 semnificativ de rulări pe testul din Figura 9, toți algoritmii realizează o clusterizare corectă.

Pentru a recrea acest test, se generează 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 puncte 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.

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 dificultăț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 Dunn, 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 cluster 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 simplu mod de a genera acest test este folosirea editorului de teste din aplicație.

Dacă în pasul inițial, doi dintre centroizi 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ă este 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.

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 poziț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 algoritmul 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 asociate 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 ponderi 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ățesc, viteza se va stabiliza și va fi apropiată de 0. Dacă până în acel moment nu s-a ajuns la soluția corectă, algoritmul nu va mai ajunge la o clusterizare corectă în acea rulare.

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ă, deoarece indicii de validare folosesc distanța euclidiană pentru a calcula 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 centrul modulului de afișare, la o distanță mică unul de celălalt, distanța dintre 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 algoritmului 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.

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ă calculează distanța dintre două puncte. În calculul diametrului 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 clusterului 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, algoritmii 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 cluster 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ă.

6.6. Set de date cu clustere cu forme neregulate

Figura 14. Testul 6 cu clustere cu forme neregulate

Setul de date din 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, clusterul verde poate 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ă, diametrele acestora vor fi, de asemenea, variabile, iar în procesul de clusterizare, un centroid va avea asociate 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, algoritmul 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.

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. Algoritmul PSO cu factor de comprimare este mult mai rapid decât ceilalți algoritmi pe acest test.

Pentru a reproduce acest test, se vor genera cinci clustere poziționate î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 pentru algoritmul 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, se 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 deoarece 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 multe 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.

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 cazul setului de date din Figura 16 algoritmul PSO standard ajunge mai greu la soluția corectă, deoarece 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 de teste și apoi edita puțin sau se poate genera un test gol ce va fi editat să arate asemănător cu cel din 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 pentru 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 stabilizează 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.

6.9. Rezultate obținute

Tabelul 1

Rezultatele obținute pentru testele 1-3, folosind indicele Dunn

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 convergență, 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 indicele 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 clusterizare 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

Tabelul 2

Rezultate obținute pentru testele 1-3, folosind indicele Davies Bouldin

Indicele Davies Bouldin î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 ponderi 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 clusterizarea obținută este puțin mai slabă, conform indicelui Davies Bouldin.

Testul 3 este favorabil pentru algoritmul 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. Algoritmii de inteligență a roiurilor 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

Tabelul 3

Rezultatele obținute pentru testele 4-6, folosind indicele Dunn

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 indicele 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 dificultăți în găsirea acestei soluții.

Figura 19. Grafic pentru testul 4 folosind indicele Dunn

Tabelul 4

Rezultatele obținute pentru testele 4-6, folosind indicele Davies Bouldin

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 corectă 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 viteză 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 afectează 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

Rezultatele obținute pentru testele 7-8

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 rapid 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 testul 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 clusterului 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

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 rezultate mai bune 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 corectă 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. Indicele 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 pentru 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.

Bibliografie

A. K. Jain, R. C. Dubes, „Algorithms for Clustering Data”, Prentice Hall, 1988, pag. 1-3

G. Gan, „Data Mining and Knowledge Discovery Series”, CRC Press, 2011, pag. 3-4

F. Kovács, C. Legány, A. Babos, „Cluster Validity Measurement Techniques”, http://uni-obuda.hu/conferences/mtn2005/KovacsFerenc.pdf

A.K. Jain, M.N. Murty, P.J. Flynn, „Data Clustering: A Review”, ACM Computing Surveys, Vol. 31, No. 3, September 1999, pag. 265-323

C. C. Aggarwal, C. K. Reddy, „Data Clustering Algorithms and Applications, CRC Press, 2013, pag. 100-101

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

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

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

X. S. Yang, Engineering Optimization: An Introduction with Metaheuristic Applications, John Wiley & Sons, 2010, pag. 203-205

M. A. Montes de Oca, „Particle Swarm Optimization”, IRIDIA-CoDE, Universit´e Libre de Bruxelles (U.L.B.), May 7, 2007, pag. 8-22

R. M. Chen, H. F. Shih, „Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search”, Algorithms, Vol.6, Issue 2, 2013, pag. 228-244

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. 163-173

Y. Liu, Y. Shen, „Data Clustering with Cat Swarm Optimization”, Journal of Convergence Information Technology, Volume 5, Number 8, October 2010, pag. 21-28

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

J. Wu, „Advances in K-means Clustering, A Data Mining Thinking”, Springer, 2012, 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: Problema de Clusterizare pe Date (ID: 150152)

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.

Problema de Clusterizare pe Date

Copyright Notice

Detectia Si Recunoasterea Fetelor In Imagini de Slaba Calitate

Elaborarea Si Sistemul Informational al Detinatorului Nominal

Module Software Specifice Ingineriei Electrice

Proiectarea Si Securitatea Orientata pe Servicii Web

Reglementari Juridice Privind Criminalitatea Informatica

Recunoasterea Obiectelor Folosind Procesarea Imaginilor

Copyright Notice

Similar Posts