UNIVERSITATEA BABEŞ-BOLYAI CLUJ-NAPOCA

FACULTATEA DE MATEMATICǍ ŞI INFORMATICǍ

SPECIALIZAREA INFORMATICĂ ROMÂNĂ

LUCRARE DE DIPLOMǍ

Modele de învățare nesupervizată

Conducător ştiinţificProf. univ. dr. Czibula Gabriela

AbsolventCodrean Florina

2012

Cuprins

Introducere...............................................................................................................................................3

1. Învățarea automată...............................................................................................................................3

1.1. Problematica învățării automate...................................................................................................3

1.2. Învățarea supervizată....................................................................................................................3

1.2.1. Rețele neuronale....................................................................................................................3

1.2.2. Arbori de decizie....................................................................................................................3

1.2.3. Învățarea Bayesiană...............................................................................................................3

1.3. Învățarea prin întărire....................................................................................................................3

1.4. Învățarea nesupervizată.................................................................................................................3

1.4.1. Clustering...............................................................................................................................3

1.4.2. Rețele cu auto-organizare (SOM)..........................................................................................3

1.4.3. Învățarea Hebbiană................................................................................................................3

2. Clustering.............................................................................................................................................3

2.1. Descriere.......................................................................................................................................3

2.2. Formalizarea problemei................................................................................................................3

2.3 Clasificarea tehnicilor de clustering..............................................................................................3

2.4. Măsuri de similaritate...................................................................................................................3

2.5. Metoda K-means...........................................................................................................................3

2.6. Metoda Fuzzy C-means................................................................................................................3

2.7. Măsuri de calitate..........................................................................................................................3

3. Aplicații ale Analizei Cluster...............................................................................................................3

3.1. Domenii de aplicații......................................................................................................................3

3.1.1. Electroenergetică...................................................................................................................3

3.1.2. Segmentarea pieței.................................................................................................................3

3.1.3. Probleme de recunoaștere de imagini....................................................................................3

3.1.4. Medicină................................................................................................................................3

3.1.5. Web mining............................................................................................................................3

3.2. Îmbunătățiri aduse tehnicilor de clustering. Hibridizare..............................................................3

3.2.1. Clustering și agenți inteligenți în web mining.......................................................................3

3.2.2. Clustering folosit în sisteme predictive.................................................................................3

3.2.3. Clustering în cadrul GIS (Geographical Information System)..............................................3

4. Prezentarea aplicației...........................................................................................................................3

4.1. Motivație.......................................................................................................................................3

Concluzii..................................................................................................................................................3

Bibliografie............................................................................................Error! Bookmark not defined.

Introducere

1. Învățarea automată

1.1. Problematica învățării automate

Învăţarea automată, unul din sub-domeniile de bază ale Inteligenţei Artificiale, se

preocupă cu dezvoltarea de algoritmi şi metode ce permit unui sistem informatic să înveţe

date, reguli, chiar algoritmi. Învăţarea automată presupune în primul rând identificarea şi

implementarea unei modalităţi cât mai eficiente de a reprezenta informaţii, în sensul facilitării

căutării, reorganizării şi modificării lor. Alegerea modului de a reprezenta aceste date ţine

atât de concepţia generală asupra modului de rezolvare a problemei, cât şi de caracteristicile

datelor cu care se lucrează. [1]

Învăţarea nu se poate face pe baza unui set foarte mare de cunoştinţe, atât din cauza

costurilor mari, presupuse de acumularea unor baze de informaţii mari cât şi din cauza

complexităţii memorării şi prelucrării unui volum mare de informaţii. În acelaşi timp însă,

învăţarea trebuie să ducă la formularea de suficiente „reguli” atât cât să permită rezolvarea

unor probleme dintr-un spaţiu mai larg decât cel pe baza căruia s-a făcut învăţarea. Adică

învăţarea trebuie să îmbunătăţească performanţa unui sistem nu doar în rezolvarea repetată a

unui acelaşi set de probleme, ci şi în rezolvarea unor probleme noi. Acest lucru presupune o

generalizare a unei metode de rezolvare pentru a acoperi un număr cât mai mare de instanţe

posibile, dar şi păstrarea unei specializări suficiente pentru a fi identificate corect instanţele

acceptate. Aceasta se poate face fie inductiv, generalizând o problemă plecând de la un set de

exemple, fie deductiv, plecând de la o bază de cunoştinţe suficiente asupra universului

problemei şi extrăgând date şi reguli esenţiale. Pentru a putea face acest lucru, un algoritm de

învăţare trebuie să fie capabil să selecteze acele elemente semnificative pentru rezolvarea

unei instanţe viitoare a problemei. Aceasta alegere se face pe baza unor criterii de selecţie

numite diagonale inductive. [2][3]

O altă componentă esenţială al unui algoritm de învăţare este metoda de verificare, o

metodă capabilă să confirme dacă generalizările făcute sau regulile deduse se apropie mai

mult de soluţia ideală decât starea anterioară a sistemului. Studiul învăţării automate a dus la

descrierea a numeroase metode, variind după scop, date de antrenament, strategia de învăţare

şi modalitatea de reprezentare a datelor.

În cadrul învățării automate se pot distinge trei mari direcții de cercetare și de tipuri

de învățare. Prima dintre ele este reprezentată de învățarea supervizată, care presupune

construirea unui model al datelor inițiale în care o parte dintre ele sunt explicative, etichetate,

iar una sau mai multe sunt neetichetate, considerate date de test. Cel de-al doilea tip de

învățare automată este învățarea prin întărire, care presupune oferirea unei recompense sau a

unei pedepse simulate, în funcție de anumite tipuri de comportamente ale sistemului, cu

ajutorul cărora sistemul învață un comportament așteptat. Ultima categorie, cea a învățării

nesupervizate, se aplică cel mai bine pe anumite probleme din viația reală, deoarece nu

necesită nicio etapă de antrenare, aplicându-se direct pe datele neetichetate. În continuare vor

fi prezentate cele trei tipuri de învățare. [4]

1.2. Învățarea supervizată

Învăţarea supervizată este un tip de învăţare inductivă ce pleacă de la un set de

exemple de instanţe ale problemei şi formează o funcţie de evaluare, denumită şablon, care să

permită clasificarea unor instanţe noi. Învăţarea este supervizată în sensul că setul de exemple

este dat împreună cu clasificarea lor corectă. Aceste instanţe rezolvate se numesc instanţe de

antrenament. Formal, setul de instanţe de antrenament este o mulţime de perechi atribut-

valoare (x,f(x)), unde x este instanţa iar f(x) clasa căreia îi aparţine instanţa respectivă.

Scopul învăţării este construirea unei funcţii de tip şablon care să clasifice corect

instanţele date ca exemplu, iar pentru un x pentru care nu se cunoaşte f(x) să propună o

aproximare cât mai corectă a valorii f(x). Astfel, învățarea supervizată este echivalentă cu

optimizarea unei funcții de eroare care măsoară diferența dintre răspunsurile care ar trebui să

le producă sistemul și cele pe care le produce efectiv. [4]

Probleme importante ale învățării nesupervizate sunt cele de clasificare,

probabilistice. Astfel, clasificarea supervizată implică gruparea datelor pe baza unor modele

prestabilite, denumite clase de antrenament. De obicei, acestea reprezintă o grupare de

referință ce corespunde realității, folosită inițial pentru antrenarea sistemului înaintea

clasificării propriu-zise a datelor. [5]

În continuare vor fi prezentate pe scurt fundamentele teoretice ale câtorva tehnici

folosite în cadrul învățării nesupervizate, precum rețele neuronale, arborii de decizie și

învățarea bayesiană.

1.2.1. Rețele neuronale

În cadrul învățării nesupervizate, rețelele neuronale ocupă o categorie aparte, fiind

des folosite la rezolvarea numeroaselor probleme. Cea mai semnificativă proprietate a

reţelelor neuronale este capacitatea de a învăţa din mediul înconjurător şi de a-şi îmbunătăţi

performanţele pe baza acestui proces de învăţare. Reţeaua neuronală învaţă pe baza unui

proces iterativ de ajustare a ponderilor sinaptice şi eventual al nivelului de activare. Dacă

procesul de învăţare decurge bine, atunci reţeaua neuronală acumulează tot mai multe

informaţii, la fiecare iteraţie.[4]

Reţelele neuronale au fost inspirate de modelul creierului biologic privit ca o reţea

uriaşă în care unităţi de calcul mici transmit semnale simple prin conectori către alte unităţi

din reţea, în urma modelului format de conectori şi a semnalelor transmise rezultând

raţionamente inteligente. O reţea neuronală este formată dintr-o mulţime de noduri şi

conexiuni între noduri. Intrările într-un nod pot veni fie din exteriorul reţelei fie de la un alt

nod din reţea, iar ieşirile pot merge în afara reţelei sau pot intra în alt nod din reţea. Fiecare

conexiune are ataşat un cost ce afectează semnalul transmis prin ea. Învăţarea unei reţele se

face prin ajustarea acestor costuri.

Acest tip de rețele pot fi unistratificate cu flux unidimensional, numite perceptron,

sau multistratificate:

- Perceptronul: este un model de reţea neuronală unistratificată cu flux

unidirecţional. Semnalele de intrare sunt fie de tip excitatorfie de tip

inhibator. Perceptronii sunt capabili să înveţe doar funcţii liniar separabile,

adică funcţii în a căror reprezentare în spaţiu putem separa oricare doua clase

de valori ale funcţiei printr-un singur plan.

- Rețele neuronale multistratificate: are un strat de intrare, ce conţine noduri în

care toate intrările provin din exteriorul reţelei, un strat intern, ascuns, şi un

strat de ieşire, în care ieşirile tuturor nodurilor pleacă în exteriorul reţelei. [4]

1.2.2. Arbori de decizie

Un arbore de decizie este una din cele mai utilizate structuri de reprezentare utilizate

în învăţarea automată. Pentru o instanţă specificată de un set de proprietăţi, arborele verifică

anumite proprietăţi pentru a naviga în interiorul său şi ajunge la o frunză care va fi eticheta

acelei instanţe. Fiecare nod intern al arborelui reprezintă un test făcut asupra uneia sau mai

multor proprietăţi ale instanţei, iar ramurile descendente din acel nod sunt identificate de

posibilele rezultate ale acelui test. Astfel, un arbore de decizie construieşte pentru o instanţă o

conjuncţie logică ce se verifică pentru proprietăţile instanţei şi formează un fel de

demonstraţie a clasificării făcute pe baza acelor proprietăţi. [4]

1.2.3. Învãțarea Bayesianã

Învăţarea în modelul Bayesian presupune menţinerea unor variante posibile ale

şablonului, fiecare variantă fiind evaluată prin calcularea probabilităţii ca ea să clasifice

corect o instanţă viitoare. Această probabilitate se calculează folosind rezultatele anterioare

ale clasificărilor făcute de şablonul respectiv. La un moment dat, trebuie însă ca cel puţin o

parte din şabloanele ipotetice să fie eliminate ca fiind posibile soluţii. Acest lucru se face prin

stabilirea unui şablon ca fiind cel mai probabil şi eliminarea tuturor celorlalte, sau cel puţin a

celor cu o probabilitate considerabil mai mică. [4]

1.3. Învãțarea prin întãrire

Spre deosebire de metodele de învăţare supervizată prezentate mai sus, învăţarea

prin întărire se face fără ca algoritmul de învăţare să compare direct şablonul obţinut cu

rezultatele corecte pentru exemplele de antrenament. În schimb este implementată o

modalitate de a “răsplăti” sau “pedepsi” sistemul în funcţie de cât de mult se apropie de

rezultatul corect. Acest feedback este singura metodă a sistemului de învăţare de a se regla

pentru îmbunătăţirea rezultatelor sale. Acest lucru face învăţarea prin încurajare mai dificilă,

căci sistemul nu mai primeşte informaţii directe despre cum şi cât să se corecteze, ci doar ştie

dacă se apropie sau se depărtează de rezultatul optim. De asemenea, feedback-ul poate veni

doar uneori, nu neapărat la fiecare schimbare în şablonul ipotetic, deci sistemul trebuie să

aibă o modalitate de a direcţiona şi impulsiona singur schimbarea pentru îmbunătăţirea

şablonului. [4]

Concretizând, învățarea prin întărire se referă la o clasă exactă de probleme din

învățarea automată care admite ca un sistem să exploreze mediul, să perceapă anumite stări și

să încearce niște acțiuni. În schimbul acțiunilor efectuate, sistemul va primi o recompensă

pozitivă sau negativă. Astfel, algoritmul de învățare prin întărire va urmări să găsească o

politică de maximizare a recompensei pe parcursul execuției, în contextul problemei date.

Spre deosebire de majoritatea formelor de învăţare în care sistemului i se spune dinainte ce

acţiuni să întreprindă, în cazul învăţării prin întărire sistemul trebuie sa descopere singur care

acţiuni duc la obţinerea unei recompense mai mari. Acţiunile întreprinse pot afecta nu numai

recompensa obţinută imediat, dar şi situaţia următoare, şi în consecinţă toate recompensele

viitoare. Programarea sistemelor se face prin semnale de întărire sau slabire

(răsplată/pedeapsă) fără a fi nevoie să se precizeze modalitatea concretă de rezolvare a

sarcinii necesar a fi îndeplinită. Comportamentul adecvat se învaţă prin interacţiuni de tipul

încercărilor succesive asupra mediului înconjurător dinamic. [2]

O diferenţă majoră dintre învăţarea prin întărire şi învăţarea de tip supervizat o

reprezintă faptul că primului tip îi este necesară o fază explicită de explorare a mediului în

scopul achiziţionării de cunoştinţe. Cel de al doilea tip de învăţare, cel supervizat, presupune

acumularea cunoştinţelor pe baza unor exemple furnizate de către un expert sau supervizor

extern şi, deşi reprezintă unul din tipurile cele mai importante de instruire, nu este adecvată

învăţării din interacţiuni cu mediul. În probleme interactive este deseori imposibil şi nepractic

să se obţină exemple de comportament adecvat şi reprezentativ pentru toate situaţiile posibile

în care un sistem ar putea să se găsească. Este deci necesară capacitatea sistemului de a învăţa

din propria experienţă. [3]

În acest context intervine problema explorare versus exploatare: pentru a obţine o

recompensă însemnată un sistem instruit prin învățare prin întărire va prefera acţiuni care au

mai fost încercate în trecut şi care au dovedit că aduc un aport substanţial.

Totodată este necesar să încerce şi noi acţiuni care s-ar putea dovedi mai productive

decât cele testate până în prezent. În consecinţă, dilema explorare-exploatare se rezumă la

faptul că un sistem trebuie să exploateze cunoştinţele deja acumulate pentru a maximiza

recompensa, dar trebuie şi să exploreze noi acţiuni care s-ar putea dovedi mai bune decât cele

deja efectuate. Sistemul trebuie să încerce o varietate de acţiuni şi progresiv să le favorizeze

pe cele care par a fi mai bune. [2]

În continuare vor fi prezentate pe scurt fundamentele teoretice ale câtorva tehnici

folosite în cadrul învățării prin întărire:

- Q learning: este o metodă bazată pe valoarea acțiunilor. Sistemul poate alege

o acțiune cu o valoare estimată cât mai mare, denumită și ”acțiune lacomă”.

Această metodă exploatează cunoștințele curente în scopul maximizării

recompensei. Comportamentul sistemului poate fi îmbunătățit prin acțiuni de

tipul ε-lacome, care descriu selectarea unei mici proporții ε de date care vor

fi alese aleator, iar restul datelor alese vor fi de tipul celor cu valoarea

estimată cât mai mare. Unele strategii din Q-learning încep cu o valoare ε

mare, pentru încurajarea explorării, după care valoarea sa este treptat

diminuată.

- Metode de tip Monte Carlo: nu presupun cunoașterea completă a a modelului

mediului. Sunt necesare însă secvenţe de stări, acţiuni şi recompense desprinse din

interacţiunea actuală sau simulată cu mediul.

- Metode bazate pe programarea dinamică: sunt acele metode care se bazează

pe anumiți algoritmi care pot fi folosiți la calculul unor strategii optime,

având dat un obiect modelat cu procese de decizie de tip Markov. Aceste

metode presupun oferirea de recompense întârziate, ceea ce înseamnă că o

recompensă substanțială poate să apară doar la finalul unui șir de acțiuni care

nu aduc decât o recompensă imediată nesemnificativă. Astfel, sistemul va

trebui să învețe care dintre acțiuni sunt dezirabile astfel încât să poată obține

o recompensă în viitorul apropiat. Acest tip de metode sunt importanți din

punct de vedere teoretic din cauza necesității existenței unui model perfect.

[2]

1.4. Învãțarea nesupervizatã

Învăţarea nesupervizată elimină complet necesitatea unor instanţe de antrenament,

deci şi problemele legate de acestea. Scopul învăţării nesupervizate nu este definit anterior ca

un concept ţintă, algoritmul fiind lăsat singur să identifice concepte posibile.

În general, învăţarea nesupervizată presupune existenţa unor instanţe neclasificate,

un set de reguli euristice pentru crearea de noi instanţe şi evaluarea unor concepte deduse,

eventual un model general al spaţiului de cunoştinţe în care se găsesc aceste instanţe. Un

algoritm de învăţare nesupervizată construieşte concepte pentru a clasifica instanţele, le

evaluează şi le dezvoltă pe cele considerate “interesante” de regulile euristice. În general,

concepte interesante sunt considerate cele care acoperă o parte din instanţe, dar nu pe toate.

[2]

Învăţarea nesupervizată permite identificarea unor concepte complet noi plecând de la

date cunoscute. Încercări de a aplica acest tip de învăţare în cercetarea ştiinţifică au dus la

rezultate semnificative. Totuși, principalul factor ce limitează numărul şi relevanţa

conceptelor învăţate de acest gen de algoritmi este faptul că ele nu pot învăţa noi metode de a

crea şi evalua concepte. Pentru a obţine rezultate mai relevante, ar trebui întâi descris un set

mult mai complex de operaţii pentru crearea de noi concepte, precum şi nişte reguli euristice

mai flexibile pentru evalua aceste concepte.[3]

1.4.1. Clustering

Domeniul în care învăţarea nesupervizată s-a dovedit însă mai utilă este cel al

identificării automate de clase în mulţimi neclasificate de instanţe. Această problemă

presupune existenţa unei mulţimi de obiecte negrupate şi a unor mijloace de a găsi şi măsura

similarităţi între aceste obiecte. Scopul unui algoritm de identificare a unor clase de obiecte

este de a grupa obiectele într-o ierarhie de clase după criterii cum ar fi maximizarea

similarităţii obiectelor din aceeaşi clasă. Ierarhia de clase este reprezentată de obicei ca un

arbore, fii unui nod reprezentând categorii distincte dar incluse în categoria părinte. [6]

În cadrul clasificării nesupervizate, un grup de probleme importante sunt cele de

clustering, denumite și probleme de clasificare nesupervizată. Acestea propun o partiționare

optimală a spațiului datelor de intrare din punctul de vedere al unui anumit criteriu

matematic, fără a folosi informații cunoscute dinainte. Avantajul acestor metode este acela că

sunt complet automate, fără a fi nevoie de intervenția utilizatorului și pot fi folosite pentru

clasarea datelor despre care nu cunoaștem informații referitoare la conținutul lor. Pe de altă

parte, fiind un proces automat, relevanța grupurilor determinate tinde să fie mai scăzută decât

în cazul clasificării supervizate, aceasta depinzând mult de metoda folosită și de puterea de

discriminare a spațiului de caracteristici folosit. [5] Modelarea datelor pune clustering-ul într-

o perspectivă istorică înrădăcinată în matematică, statistici, şi analiză numerică. Din

perspectiva unei maşini de învăţare clusterii corespund tiparelor ascunse (hidden patterns),

căutarea clusterilor este învăţarea nesupervizată, şi sistemul rezultat reprezintă un concept de

date. Prin urmare, clustering este nesupervizat de un concept de date ascunse. Datele se referă

la baze de date mari care impun grupare şi analiză suplimentară a cerinţelor de calcul.

Dintr-o perspectivă practică, clustering-ul joacă un rol de seamă în aplicaţii de data

mining, cum ar fi explorarea ştiinţifică a datelor, extragerea de informaţii şi text mining,

aplicaţii de baze de date spaţiale, analiza web, CRM, marketing, diagnosticarea medicală,

biologie computaţională, şi multe altele. Clustering-ul este obiectul cercetării active în mai

multe domenii cum ar fi statistici, recunoaşterea formelor, şi maşini de învăţare. Acest studiu

se concentrează pe clustering în data mining. Data mining adaugă la clustering complicaţiile

unor seturi de date foarte mari cu foarte multe atribute de diferite tipuri. Ele impun cerinţe de

calcul unice pe algoritmi de clustering relevanţi.

Metodele de clustering pot fi clasificate după modelele pe care sunt bazate, fiecare

dintre acestea putând genera diferite rezultate. În general, aceștia sunt împărțiți în două mari

categorii: tehnici bazate pe metode partiționale și tehnici bazate pe metode ierarhice. Totuși,

s-a ajuns în a se determina șapte clase principale în care pot fi clasificate problemele de

clustering, acesea fiind:

1) Metode ierarhice: care pot fi aglomerative sau divizive.

2) Metode partiționale: algoritmi de relocare, clustering probabilistic, metoda

K-means, metoda K-medoids, algoritmi bazați pe densități.

3) Metode bazate pe grid.

4) Clustering bazat pe constrângeri.

5) Metode evolutive de clustering: folosind algoritmi genetici.

6) Algoritmi scalabili de clustering.

7) Algoritmi bazați pe rețele neuronale.

1.4.2. Rețele cu auto-organizare (SOM)

Rețelele cu autoorganizare, cunoscute și sub denumirea de Self-Organizing Maps

(SOM) sunt rețele care învață să formeze propriile lor clasificări ale datelor de intrare, fără

ajutor extern. Acestea sunt rețele neuronale particulare pentru care neuronii constituenți devin

sensibili la anumiți vectori de intrare prin intermediul unui proces de învățare nesupervizat.

Pentru a face acest lucru, apartenența la o anumită clasă este definită de anumiți

vectori de intrare care împărtășesc aceleași caracteristici, iar rețeaua trebuie să identifice

caracteristicile date în sfera vectorilor respectivi. Neuronii vor tinde să se ordoneze ca și cum

rețeaua neuronală ar ar reprezenta un sistem de coordonate pentru vectorii de intrare. Astfel,

este construită o hartă topografică artificială care învață prin auto-organizare într-o manieră

inspirată din neurobiologie. Obiectivul principal al unui SOM este de a transforma un model

de semnal de intrare de dimensiune arbitrară în una sau două hărţi dimensionale discrete.

Astfel, în cursul învățării, neuronii constituenți vor alege anumite modele sau clase de vectori

de intrare, iar locațiile lor vor deveni sisteme de coordonate pentru caracteristicile de intrare.

[2]

Rețelele cu auto-organizare oferă o modalitate elegantă de a reprezenta date

multidimensionale în spații dimensionale reduse, de 1-2 dimensiuni prin cuantificarea

vectorilor. Astfel, rețelele vor memor informația astfel încât orice relație topologică din setul

de învățare va fi reținută.

1.4.3. Învățarea Hebbiană

O altă tehnică folosită în învățarea nesupervizată este bazată pe legea lui Hebb,

formulată în 1949. Aceasta presupune tot existența unei rețele neuronale artificiale

nesupervizate, care însă este descrisă prin două condiții care privesc modul de declanșare a

neuronilor în cadrul realizării calculelor. Prima condiție se referă la faptul că dacă doi neuroni

sunt activați în același timp de către un stimul conținut în vectorul datelor de intrare atunci

poderea conexiunii dintre ei crește, iar ce-a de-a două condiție afirmă că dacă doi neuroni

sunt activați în contratimp, atunci ponderea conexiunii dintre ei scade. [2]

2. Clustering

2.1. Descriere

Sarcinile de a cataloga seturi mari de date și de a le împărți în grupuri de elemente

care au caracteristici comune se regăsesc deseori în numeroase domenii. Pentru experții

umani poate fi extrem de dificil și de obicei imposibil să realizeze o clasificare pe grupuri de

obiecte cu proprietăți comune a unor date abstracte nestructurate, așa cum deseori este nevoie

să se facă. Acest tip de probleme intră în categoria problemelor de clustering din invățarea

nesupervizată.

Învățarea nesupervizată constă în aplicarea unor algoritmi de grupare pentru un set

de date, în mod direct, fără a menționa criteriul de grupare și fără a utiliza o etapă de

antrenare, eliminând necesitatea folosirii unor date suplimentare de antrenament. Ideea de

partiționare a diferitelor obiecte în grupuri, pe baza similarității lor, a apărut pentru prima

dată în secolul IV î.H. la Aristotel și Teophrastos.[7] Termenul de analiză cluster (Cluster

Analysis) și metodologia specifică procesului de clustering se crede că a apărut prima dată în

[8].

Prin clustering, termen provenit de la cuvantul din limba engleza cluster, care în

traducere înseamnă îngrămădire, sau fascicul, se înțelege metoda de a segmenta un set de date

(care pot fi înregistrări, vectori, instanțe) în mai multe grupuri (clusteri), pe baza unei anumite

similarități.[7] Tehnicile de clustering pot fi privite ca forme de învățare nesupervizată în care

datele de test sunt compuse dintr-un set de vectori de intrare cărora inițial nu le corespund

niciun set de vectori de ieșire [9]. Astfel, algoritmul primește doar date neetichetate, iar

sarcina acestuia este aceea de a găsi o reprezentare adecvată a distribuției datelor, urmând a fi

grupate în clusteri relevanți. Deosebirea dintre clustering și clasificare este aceea că aceasta

din urmă partiționează setul de date în grupuri care au fost definite anterior.

Clusteringul mai este denumit și clasificare nesupervizată. Clasificarea este procesul

prin care mai multe obiecte sau entități sunt grupate în clase care reprezintă anumite categorii

naturale. Astfel, putem considera clusteringul ca fiind o problemă centrală a clasificării, mai

precis aceea de a determina care sunt grupările naturale dintr-o mulțime de date. Aceste

grupuri se referă la structuri omogene și bine separate de obiecte din mulțimea dată.

Obiectivul clasificării automate este dat de gruparea obiectelor în așa fel încât gradul de

similitudine să fie mare între membrii aceluiași grup și mic între entități care aparține de

grupuri diferite.[10][11]

De asemenea, se poate afirma că tehnicile de clustering reprezintă tehnici speciale de

aranjare a datelor de intrare pe baza dispunerii spațiale a vectorilor corespunzători acestora.

În cadrul unui astfel de proces, vectorii de intrare sunt grupați în funcție de distanța care

separă punctele reprezentative. În urma procesului de clustering rezultă unul sau mai multe

grupuri care reprezintă poziționarea spațială a caracteristicilor datelor. În interiorul unui

cluster, punctele sunt mai apropiate între ele în raport cu un centru comun decât în raport cu

centrele altor clustere. Exemplu grafic:

Figura 1. Reprezenarea grafică a unor clusteri și evidențierea centroizilor[12]

2.2. Formalizarea problemei

Problema referită în acest articol este o problemă clasică de clustering aplicată pe

diferite seturi de date. Considerând un set de date format din mai multe entități, problema

formalizată va fi următoarea:

Se dă un set de date X={x1 , x2 ,. . . , xn}, unde xi, i=1 , n este o entitate neetichetată

căreia îi este asignat un vector de atribute Vi m-dimensional (cu m caracteristici). Se cere să

se găsească k partiții cât mai naturale ale mulțimii X: , cu , astfel încât

entitățile care aparțin aceleiași clase să fie cât mai apropiate, iar cele care aparțin la clase

diferite să fie cât mai depărtate posibil.

Algoritmii generali de clustering prezintă următoarele două caracteristici:

1) Fiecare entitate aparţine minim unui grup:

¿i=1

kC i= X

2) Fiecare grup conţine minim o entitate:

C i≠¿ ¿ , i=1 , kO altă proprietate poate fi considerată:

3) O entitate apartine doar unui singur grup:

C i∩C j=, i≠ j , C i≠¿ ¿ , i , j=1 , k , fixat

Această condiție nu este valabilă pentru algoritmii de clustering fuzzy, în

cadrul cărora o entitate aparține fiecărui cluster, cu un anumit grad. [6]

Etapele unui proces de clustering se referă la rezolvarea următoarelor probleme:

1) Stabilirea elementelor supuse operației de clustering: este o etapă principală

care mai poate include și stabilirea numărului de clusteri. Pregătirea datelor

presupune colectarea și aranjarea lor înaintea procesului de clustering. De

asemenea, datorită numărului mare de cracteristici pe care le pot deține unele

seturi de date, apare nevoia selectării celor mai importante, astfel încât

cantitatea informațiilor pierdute să fie minimală, iar rezultatele obținute în

urma procesului de clasificare să fie relevant. La extragerea caracteristicilor

se pot folosi anumite tehnici statistice.

2) Definirea unei distanțe între elementele mulțimii: necesită selectarea unei

metrici de determinare a distanței dintre două entități, aceasta putând fi

folosită pentru a caracteriza similitudinea conceptuală dintre două sau mai

multe elemente. Totodată, utilizarea cunoștințelor disponibile referitoare la

domeniul dat, pot ajuta la pregătirea datelor și la alegerea măsurii de

similaritate.

3) Realizarea procesului de clustering propriu-zis: se produce prin utilizarea

unui algoritm specific de clustering pe mulțimea de date care se dorește a fi

clasificată.

4) Extragerea rezultatelor: are loc prin obținerea acestora într-o formă cât mai

simplă și mai reprezentativă. În acest caz, simplitatea poate fi privită fie din

perspectiva analizei automate, fie din perspectiva umană, astfel încât să fie

cât mai ușor de înțeles de către experți umani.

5) Evaluarea rezultatelor: această etapă se poate realiza prin aprecierea

robusteții și validității modelului obținut repetând procesul sau folosind

anumite măsuri de calitate pentru rezultatele generate. Repetarea procesului

se poate face: folosind și alte măsuri de similaritate corespunzătoare

contextului, utilizând și alte tehnici de clustering sau rulând algoritmul de

mai multe ori, dar ignorând unul sau mai multe obiecte la fiecare iterație. În

urma repetării procesului se analizează rezultatele obținute.[7]

2.3 Clasificarea tehnicilor de clustering

Există numeroase tipuri de clustering, bazate pe diferite metode, fiecare dintre acestea

putând genera ca și rezultat diferite moduri de a grupa datele. O posibilă clasificare este aceea

de a împărți algoritmii de clustering în două mari categorii: tehnici de clustering bazate pe

partiționarea datelor și tehnici de clustering bazate pe metode ierarhice. De asemenea, există

și algoritmi mai noi care se pot grupa în algoritmi bazați pe densitate, bazați pe grid sau

bazați pe modele. Clasificarea algoritmilor de clustering nu este simplă, deseori se ajunge la

concluzia că unele categorii de algoritmi se suprapun. Pe lângă tehnicile enumerate mai sus,

se pot aminti: algoritmi de clustering bazați pe constrângeri, bazați pe grafe, algoritmi

scalabili, algoritmi speciali pentru date cu multe dimensiuni. În cadrul învățării automate, au

apărut și metode evloutive de clustering și unele care folosesc rețele neuronale. [6]

Algoritmii partiționali consideră că setul de date trebuie grupat in k clusteri

partiționându-l, iar numărul k se pretinde a fi cunoscut de la început. În cadrul acestei metode

se mai poate folosi și tehnica relocării iterative prin care se încearcă îmbunătățirea

partiționării prin mutarea obiectelor dintr-un grup în altul. Cele mai cunoscute metode

partiționale sunt: K-Means – care presupune calcularea centrului de greutate al unui cluster si

asignarea unei entități acelui cluster în funcție de o anumită metrică, K-Medoids – presupune

alegerea unui element reprezentativ (medoid) pentru fiecare cluster, la fiecare iterație, PAM

(Partitioning Around Medoids), CLARA (Clustering Large Applications), CLARANS

(Clustering Large Applications based upon RANdomized Search). [13] În timp ce algoritmii

ierarhici construiesc clustere treptat, algoritmii de partiţionare învaţă clustere direct. În acest

sens, ei încearcă să descopere clusteri fie prin relocalizarea iterativă a punctelor între

subseturi, sau încercă să identifice clusterii ca şi zone foarte populate cu date.

Algoritmii ierarhici structurează setul de obiecte creând o ierarhie. Există două tipuri

de abordări: aglomerativă și divizivă. În cadrul abordării aglomerative, sau “bottom-up”,

fiecare obiect este asignat unui cluster, iar apoi clusterii se unesc pe baza unor măsuri de

similaritate până când o anumită condiție este îndeplinită și s-au găsit un anumit număr de

clusteri. Abordarea divizivă este una de tipul “top-down”, unde la început se consider că toate

entitățile aparțin unui singur cluster, iar la fiecare iterație care urmează, fiecare cluster se

divide în clusteri mai mici până când o condiție e satisfăcută.

Metoda de divizare ierarhică descoperă clustere succesive, utilizând clusterii deja

formați, construind o ierarhie și producând o diagramă sub formă de arbore, numită

dendogramă, și nu doar o simplă partiție a obiectelor.[7] Astfel, clusterii noi sunt formați prin

realocarea apartenențelor unui punct, la fiecare pas, pe baza unei măsuri de similaritate, prin

urmare se generează o ierarhie de clusteri imbricați. Aceste tehnici au ca avantaj simplitatea

lor conceptuală și computațională, însă ele par potrivite mai ales atunci când datele privite ca

structuri sunt regulate. [10]

Pentru acest caz nu este necesară cunoașterea de dinainte a numărului de clustere,

dar se poate alege o anumită condiție de terminare.

Cele trei tipuri de clustering ierarhic sunt:

a) Aglomerativ: în care perechi de obiecte/clustere sunt conectate succesiv,

producând clustere mai mari.

Metoda constă în:

i. Plasarea fiecărui obiect în propriul său cluster.

ii. La fiecare pas se unesc cele mai asemănătoare două clustere până

când se obține unul singur sau o anumită condiție de terminare este

îndeplinită.

b) Diviziv: toate obiectele sunt plasate inițial într-un singur cluster, apoi

succesiv sunt împărțite în grupuri separate.

Metoda constă în:

i. Toate obiectele sunt considerate ca făcând parte din același unic

cluster.

ii. La fiecare pas se divide clusterul cel mai distinctiv în clustere mai

mici, procedându-se astfel până când se obține un anumit număr de

clustere sau o anumită condiție de terminare este îndeplinită.

c) Conceptual: inițial se consideră un nod rădăcină gol, obiectele fiind

adăugate unul câte unul, utilizând clase (grupuri) deja existente, creând noi

clase sau combinând și divizând clase existente. [7]

Algoritmii bazați pe densitatea datelor se leagă de conectivitatea care poate exista

între entități și densitatea acestora dintr-o anumită regiune. În acest caz este folosită o funcție

de densitate care încearcă modelarea legii de distribuție a datelor. Această metodă are ca

avantaj modelarea unor clusteri de orice formă. Metoda de formare a clusterilor bazată pe

grid nu este chiar una nouă, aceasta se poate modifica astfel încât să se rezume la un algoritm

de clustering ierarhic, partițional sau bazat pe densitate. Ea presupune segmentarea spațiului

în care se află datele în zone regulate, obiectele plasându-se pe un grid multi-dimensional.

Clusteringul bazat pe grafe în care mulțimea inițială de entități care urmează a fi

împărțită în clusteri este privită ca o mulțime de noduri, cu ponderile muchiilor obținute pe

baza aplicării unor măsuri de similaritate între perechile de noduri. Astfel, clasificarea se va

face pe baza unei măsuri de conectivitate între anumite grupuri de noduri, iar strategia de

clasificare se poate reduce la determinarea unui arbore minimal de acoperire și eliminarea

unor muchii pentru obținerea de subgrafe. La final, partițiile rezultate vor fi reprezentate de

subgrafele determinate. [10]

După tipul de apartenență a datelor la un anumit cluster, putem distinge: clustering de

tip exact (Hard Clustering), în cadrul căruia fiecărei entități i se asociază o anumită etichetă

ce reprezintă clusterul din care face parte, și clustering de tip Fuzzy, unde fiecărei entități i se

asociază un grad sau o probabilitate de a face parte dintr-un anumit grup. În acest ultim caz, o

entitate poate aparține mai multor clusteri.

2.4. Măsuri de similaritate

În contextul metodologiei de clustering, măsura de similaritate indică cât de

asemănătoare sunt două entități. De mai multe ori însă, în loc de similaritate se utilizează

noțiunea de disimilaritate, care este mai adecvată, în ideea măsurării unei distanțe. De obicei,

unei asemenea măsuri i se cere să aibă anumite proprietăți, aceasta depinzând și de problema

concretă la care se aplică. Indiferent de dimensiunea reală a spațiului, modelele de clasificare

sunt de obicei interpretate geometric. Astfel, mulțimea de entități poate conține o combinație

de forme, dimensiuni și geometrii, iar clusteri compacți, bine delimitați și cu număr egal de

entități apartenente se regăsesc rar în datele reale. Acesta este motivul pentru care se folosesc

metrici de similaritate apreciate ca distanță. [6]

O măsură de similaritate este o funcție , aplicată pe o mulțime de

obiecte D și având anumite proprietăți specifice. Conceptual, se poate spune că

și din această cauză terminologia proprie ar fi măsura de

disimilaritate, privită ca distanța dintre două obiecte. Cu toate acestea, termenul consacrat

este cel de măsură de similaritate.

Privită ca și distanță, o asemenea măsură ar trebui să posede proprietățile de bază ale

unei metrici, și anume:

- Ne-negativitatea și identitatea: , iar dacă .

- Simetria: .

- Inegalitatea triunghiului: .

Pentru a determina similaritatea dintre două obiecte se pot utiliza diferite tipuri de

măsuri de similaritate, alese în funcție de natura datelor și de scopul propus. [7]

Considerând două entități X și Y, fiecare dintre acestea fiind reprezentate ca vectori

cu n caracteristici: X = (x1, x2, ..., xn) și Y = (y1, y2, ..., yn), dorim să calculăm distanța dintre

cele două entități, folosind cele mai cunoscute metrici pentru calculul similiarității.

1. Măsura Minkowski (ex: Manhattan, Euclidiana, Chebyshev):

Pentru p=1 se obține distanța Manhattan (taxi cab sau city block):

Distanța Manhattan pentru vectori binari devine Distanța Hamming, cu alte

cuvinte distanța Hamming pentru coduri este numărul de simboluri diferite.

Pentru p=2 se obține distanța Euclidiană:

Pentru se obține distanța Chebychev:

2. Măsura cosinus (Cosine): este relativă la cosinusul unghiului dintre cei doi

vectori:

3. Măsura Tanimoto:

4. Măsura Mahalanobis:

, unde B reprezintă o matrice simetrică.

5. Măsuri Fuzzy: sunt utilizate pentru compararea unor vectori sau matrice ale

căror elemente iau valori din intervalul [0,1]. Astfel, considerând exemplul

anterior, valorile lui xi reprezintă măsura în care vectorul X posedă cea de-a

i-a caracteristică, așadar xi denotă gradul în care elementul i aparține lui X.

Cantitatea utilizată în definirea măsurilor de similaritate fuzzy este dată de

formula:

unde p și q sunt două entități.

De exemplu, măsurile fuzzy Minkowski și fuzzy Hamming sunt date de

formulele:

Fiind dată o mulțime de instanțe, fiecare dintre ele fiind caracterizată de un set de

atribute și având la dispoziție o măsură de similaritate, se pune problema de a le împărți în

grupuri astfel încât: obiectele care aparțin aceluiași cluster sunt asemănătoare între ele, iar

obiectele care aparțin unor clusteri diferiți sunt mai puțin asemănătoare. [6]

Pe lângă aspectul măsurării distanței (similarității) dintre obiectele care trebuie

clasificate, mai există și problema maximizării distanței inter-clustere, astfel avem nevoie de

definirea unei distanțe între două clustere. Pentru a rezolva această problemă se pot folosi

următoarele metode:

- Legătura unică (single linkage – nearest neighbor): distanța între două

clustere reprezintă minimul distanței între oricare două obiecte din acele

clustere;

- Legătura medie (average linkage – unweighted pair-group average): distanța

dintre două clustere e dată de media distanțelor dintre obiectele celor două

clustere luate perechi;

- Legătura completă (complete linkage – furthest neighbor): dată de maximul

distanței dintre oricare două obiecte care aparțin celor două clustere.

- Centroid method (unweighted pair-group centroid): distanța dintre clustere

este dată de distanța dintre centroizii lor (centrele lor de greutate).

- Ward’s method: distanța este evaluată prin analiza dispersiilor.

2.5. Metoda K-means

Tehnica celor K-medii, cunoscută și sub denumirea K-means este unul dintre cei mai

simpli algoritmi de învățare nesupervizată care rezolva bine problemele de clustering.

Procedeul urmează o cale simplă și ușoară pentru a clasifica setul datelor de intrare într-un

număr de K grupuri (clustere). Varianta clasică a acestui algoritm presupune ca numărul K de

clusteri să fie cunoscut dinainte. Ideea de bază este aceea de a defini K centre de greutate,

numite centroizi, câte unul pentru fiecare cluster. Aceste centre de greutate trebuie fixate

rațional, deoarece locații diferite pot conduce la rezultate diferite. Alegerea cea mai bună este

să le fixăm cât mai depărtate unele de altele. Următorul pas este luarea pe rând a fiecărui

element din setul de date de intrare și asocierea acestuia celui mai apropiat centroid. Prima

etapă a grupării se termină atunci când nu mai există elemente negrupate. În acest moment e

necesar să fie calculate noii K centroizi pentru clusterii determinați în pasul anterior. Procesul

continuă până în momentul în care pozițiile noilor centroizi nu se mai modifică semnificativ.

[6]

K-means este unul dintre cei mai simpli algoritmi din învățarea nesupervizată, cu

rezultate bune obținute în urma rezolvării unor binecunoscute probleme de clustering. În

procedura clasică, setul de date se dorește a fi împărțit în K grupuri fixate dinainte. Ideea

principală este aceea de a defini K centroizi, câte unul pentru fiecare cluster. În acest caz,

modul de plasare a centroizilor în spațiul de căutare este crucial, deoarece plasarea lor în

diferite locații poate genera rezultate diferite.[7] Privind setul de date inițial ca un grup de

entități, vom avea entitățile, împreună cu vectorii de caracteristici corespunzători care se vor

clasifica în cele k grupuri diferite. O entitate i, i=1 , n va fi atribuită unui grup Cj, j=1 , k cu

centroidul Kj care este cel mai apropiat de acest vector, iar K j este actualizat după fiecare

atribuire, folosind formula: K j =K j +

1nr j

( zi−K j ), unde nrj reprezintă numărul de entități

care aparţin grupului Cj (dimensiunea clusterului). În problema clasică în care se folosește

K-means cei k centroizi se inițializează fie cu valori generate aleator, din domeniul de

definiție al problemei, fi cu k dintre entitățile setului de date, alese tot în mod aleator.

Algoritmul poate fi considerat:

AlegeCentroiziiInițiali(Z,k);

Câttimp (mai există diferențe între centroizii curenți și cei anteriori)

Asigneaza entitățile la clusteri;

Recalculează centroizii;

Sf-câttimp

Scopul acestui algoritm este minimizarea funcției obiectiv, o funcție de eroare

pătratică. Funcția obiectiv este dată de expresia:

unde este distanța măsurată între punctul și centroidul K al clusterului .

Algoritmul prezintă unele dezavantaje, dintre care cele mai importante sunt:

- Modul în care se face inițializarea celor K centroizi nu este specificat.

O metodă simplă de inițializare este alegerea în mod aleator a K puncte

din spațiul multidimensional de care aparțin datele de intrare, dar din

cauza acestui fapt, între aplicări succesive ale algoritmului se pot obține

rezultate foarte diferite.

- Numărul de clusteri trebuie cunoscut dinainte, fapt care în aplicarea

practică este puțin probabil. Pentru evitarea acestei probleme se pot

folosi anumite euristici care aproximează numărul de clusteri pe baza

unor caracteristici ale setului de date de intrare.

- Rezultatul final depinde de pozițiile inițiale ale celor K centroizi și se

poate întâmpla ca din această cauză rezultatele generate să nu fie cele

optime. O soluție clasică pentru eliminarea acestui dezavantaj o

reprezintă alegerea repetată a mai multor variante de poziționare a

centroizilor inițiali.

- Căutarea tinde să rămână în jurul optimului local, găsirea optimului

global fiind o problemă NP-completă.

- Se poate întâmpla ca în cadrul unui cluster, elementele să fie foarte

apropiate de centroid, iar poziția acestuia să nu mai poată fi modificată.

- Rezultatul final depinde foarte mult de metrica folosită la măsurarea

distanței. Acest fapt se poate elimina prin încercarea de a normaliza

fiecare variabilă, însă acesta nu reprezintă întotdeauna un lucru

oportun.

- Rezultatul final depinde de numărul K de clusteri

Cele mai semnificative avantaje pe care le prezintă sunt:

- Algoritmul K-means este simplu de înțeles și ușor de utilizat.

- Minimizarea funcției obiectiv de eroare pătratică are o eficiență sporită.

- K-means este folosit adeseori cu rezultate bune, mai ales atunci când

setul de date de intrare este reprezentat de entități separabile și relativ

îndepărtate.

- Datorită simplității algoritmului, acesta este convenabil pentru seturi de

date mari, cu sute de mii de înregistrări.

2.6. Metoda Fuzzy C-means

Tehnica fuzzy a celor c medii (Fuzzy C-means) este o tehnică de clustering care

permite unui element din setul de date să aparțină cu un anumit grad de apartenență, la una

sau mai multe grupe. În analiza non-fuzzy, sau hard clustering, informația este divizată în

clustere crisp, unde fiecare entitate aparține unui singur cluster.[6] Asocierea unui obiect cu

un cluster se face cu ajutorul gradelor de apartenență:

Pentru hard clustering:

Pentru fuzzy clustering:

Metoda fuzzy este folosită frecvent în recunoașterea modelelor și se bazează pe

minimizarea următoarei funcții obiectiv:

unde: X={x1 , x2 ,. . . , xn}este mulțimea entităților, fiecare având câte m caracteristici;

K={K1 , K2 , . .. , K k}este mulțimea centroizilor, unde k este numărul de clusteri; orice metrică

folosită pentru calculul distanței dintre un element și centroidul unui cluster se notează cu

; m – gradul de fuzzyficare, cu o valoare cuprinsă în intervalul , folosit

pentru a controla diferențele dintre gradele de apartenență. Nu există nici o bază teoretică

pentru alegerea optimă a valorii lui m, dar de obicei se alege valoarea

reprezintă matricea gradelor de apartenență; uij este gradul de apartenență al elementului xi la

clusterul j, care trebuie să satisfacă următoarele condiții:

Etapele algoritmului Fuzzy C-means:

1) Inițializarea centroizilor K;

2) Calculul elementelor matricei gradelor de apartenență U, care să satisfacă

cele două condiții de mai sus, folosind următoarea formulă:

unde

3) Calcularea centroizilor Kj folosind formula:

4) Repetarea pașilor 2) și 3) până când se ajunge la minimul valorii lui J.

Gruparea fuzzy se face printr-un proces iterativ de optimizare, în care se urmărește

minimizarea funcției obiectiv, cu actualizarea gradului de apartenență uij a elementului la

clusterul j. Procesul de grupare se va sfârși când va fi îndeplinită condiția:

unde este criteriul de oprire, iar v – numărul iterațiilor procedeului de optimizare.

Algoritmul poate fi considerat:

AlegeCentroiziiInițiali(K,k);

Câttimp (nu s-a ajuns la valoarea minimă a funcției obiectiv J)

CalculeazăMatriceaGradelorDeApartenență;

Recalculează centroizii;

RecalculeazăFuncțiaObiectiv;

Sf-câttimp

Astfel, entitățile din setul de date de intrare sunt atașate unui cluster prin intermediul

valorii medii corespunzătoare funcției de apartenență. Din această cauză se folosește matricea

U, a cărei elemente sunt numere între 0 și 1, care reprezintă gradul de apartenență dintre o

entitate și un anumit centroid. [6]

2.7. Mãsuri de calitate

O etapă importantă o reprezintă evaluarea algoritmilor de clustering. Așadar, fiecare

algoritm de clustering aplicat pe același set de date va grupa datele în funcție de metrica

folosită, ceea ce face ca analiza eficienței algoritmilor să fie foarte dificilă. În general, rata

eficienţei algoritmilor de clustering este calculată în funcţie de omogenitatea clusterilor

rezultaţi şi gradul de diferenţiere dintre aceştia, determinând diferite distanțe între entități și

clusteri. Astfel, se pot aplica două măsuri de calitate sau de validare: externe și interne. [13]

Măsurile externe de calitate permit analiza rezultatelor algoritmilor, însă necesită

existența unor seturi de date etichetate încă dinaintea fazei de testare. Acestea pot fi: precizia

de a plasa o entitate în grupul corespunzător, acuratețea cu care entitățile sunt grupate corect

în cadrul clusterilor sau entropia care indică omogenitatea unui cluster. În practică, măsurile

externe sunt greu de determinat deoarece acestea necesită existența unor date etichetate

dinainte și compararea rezultatelor clusteringului cu informațiile cunoscute.

Câteva măsuri externe de calitate sunt:

- Acuratețea: reprezintă procentajul de entități grupate corect în clusteri.

- Entropia: indică omogenitatea unui cluster. O entropie scăzută îndică o

omogenitate mare, ceea ce este de dorit, și invers. Această măsură poate lua

valori din intervalul [0,1]. Astfel, un cluster cu un singur element va avea

valoarea entropiei egală cu 0. Valoarea entropiei unui cluster va fi 1 dacă el

conține un număr egal de elemente din fiecare cluster al soluției reale.

Formula pentru calculul entropiei în cadrul unui cluster este:

unde prij reprezintă raportul dintre numărul de elemente din clusterul j

conținute în clusterul i.

Calculul entropiei pentru soluția de clustering a unui set de date cu k grupuri

este dat de formula:

unde nri este numărul de elemente determinate pentru clusterul Ci, iar nr –

numărul real de elemente din acel cluster.

- Precizia: este probabilitatea ca o entitate să fie plasată în clusterul

corespunzător. [13]

Măsurile interne de calitate nu necesită cunoașterea dinainte a clusterilor de care ar

aparține entitățile grupate. Dintre acestea amintim: distanța intra-cluster (compactitatea),

distanța inter-cluster (separabilitatea), echilibrul dintre clusterii formați (din puctul de vedere

al numărului de entități asignate). Deoarece acestea uneori pot fi relativ greu de determinat, și

în special pot duce la rezultate neconcludente, s-a introdus utilizarea diferitelor tipuri de

indecși, dintre care cei mai cunoscuți sunt: indexul Davies-Bouldin[4] (caută echilibrul între

compactitate și separabilitate, astfel încât gradul de împrăștiere a datelor în cadrul spațiului de

căutare să fie mic), indexul Dunn (încearcă să maximizeze distanța inter-cluster și să o

minimizeze pe cea intra-cluster) care însă în anumite cazuri pot ignora tendințele majoritare

de grupare a entităților în clusteri, descoperind doar entități izolate care pot schimba uneori

radical măsura de calitate generală.[m01 de la radu]

Câteva măsuri interne de calitate sunt:

- Compactitatea: măsoară cât de compacte sunt entitățile din cadrul unui

cluster:

unde C este clusterul curent, nrC reprezintă numărul de entități din cluster, K

este centroidul lui C și xi o entitate. Astfel, această măsură exprimă gradul de

similaritate dintre elementelor unui cluster. Compactitatea se mai numește și

distanță intra-cluster și poate lua valori din intervalul , cu cât valoarea

sa e mai mică, cu atât rezultatul este mai bun.

- Separabilitatea: măsoară disimilaritatea dintre clusterii creați și mai este

cunoscută și sub numele de distanță inter-cluster:

unde se măsoară dinstanța dintre centroizi. Astfel, pentru fiecare cluster se

determină clusterul cel mai apropiat. Pe baza acestei metrici se caută clusterii

care vor maximiza această valoare, așadar se vor căuta clusterii cei mai

distanțați.

- Echilibrul: măsoară cât de echilibrați sunt clusterii formați din puctul de

vedere al numărului de entități componente. Formula folosită este:

cu domeniul de valori , iar valoarea maximă 1 se obține atunci când toți

clusterii au același număr de elemente, iar o valoare scăzută, apropiată de 0

se poate obține atunci când numărul de entități ale clusterilor diferă foarte

mult. Chiar dacă această metrică este considerată o măsură a calității, pe date

reale este puțin probabil ca aceasta să fie relevantă, dat fiind faptul că poate

fi un fapt normal ca numărul de elemente dintr-un cluster să difere mult.

- Indexul Davies-Bouldin: este o măsură care combină primele două metrici.

Considerăm dispersia:

Indexul Davies-Bouldin va fi:

unde este distanța dintre cei doi clusteri, care poate fi considerată

la alegere, de exemplu .

Acest index caută echilibrul între compactitate și separabilitate, astfel încât

gradul de împrăștiere a datelor în cadrul spațiului de căutare să fie mic,

căutându-se minimizarea lui.

- Indexul Dunn: se bazează pe ideea de a identifica seturi de clusteri, care sunt

compacte şi bine separate. Scopul principal al măsurii este de a maximiza

distantele inter-cluster şi a minimiza distantele intra-cluster:

Valoarea acestui index poate aparține intervalului și cu cât este mai

mare, cu atât calitatea rezultatului este mai bună.

Chiar dacă aceste tipuri de măsuri interne ale calității se folosesc destul de mult,

acest domeniu de cercetare este încă la început, datorită faptului că rezultatele pot varia destul

de mult. În anumite cazuri, aceste metrici pot ignora tendințele majoritare de grupare a

entităților în clusteri, descoperind doar entități izolate care pot schimba uneori radical măsura

de calitate generală. [6][13]

3. Aplicații ale Analizei Cluster

3.1. Domenii de aplicații

Analiza cluster este folosită în numeroase domenii academice, precum bilogia (în

cadrul grupării speciilor de animale), lingvistica (gruparea dialectelor), medicină,

neuroștiințe, segmentarea pieței, marketing, sisteme de recomandare sau cercetare

educațională.

3.1.1. Electroenergetică

3.1.2. Segmentarea pieței

Segmentarea pieței reprezintă cea mai importantă aplicație a analizei cluster.

Răspunsul diverșilor stimuli de marketing, precum prețul, campaniile promoționale, atributele

produselor sau poziționarea acestora, de către anumite tipuri de grupuri este o problemă

principală pentru analiști. Abordarea acesteia începe cu realizarea unui set de variabile care

sunt relevante pentru produsele în cauză, cum ar fi: diverse beneficii, preferințe pentru mărci,

iar apoi extragerea unui eșantion reprezentativ de consumatori. În cazul în care numărul de

variabile este ridicat, pot fi aplicate tehnici de analiză factorială în vederea reducerii lor. În

urma analizei se pot obține grupuri care pot fi comparate cu variabile care descriu

consumatorii sau cu alte variabile folosite la grupare, putând oferi analiștilor de marketing

anumite modele pentru a ajunge la piețele țintă. [14]

3.1.3. Probleme de recunoaștere de imagini

Recunoaşterea şi regăsirea anumitor tipuri de imagini poate fi crucială în anumite

domenii. De exemplu, în medicină, cu ajutorul radiografiilor, a unor capturi de imagini din

tomografii sau din ecografii, care se află în fişele personale ale pacienţilor unui spital trebuie

uneori selectaţi toţi aceia care suferă de o anumită boală care poate fi determinată în urma

analizei imaginii respective.

De asemenea, în domeniul militar şi cel al siguranţei în aeroporturi recunoaşterea

imaginilor poate fi extrem de importantă pentru supravegherea şi regăsirea în baza de date a

unor persoane, echipamente, arme, etc.

În ultimii ani, programele de clustering au fost folosite intensiv în astronomie. Astfel,

dupa ce imaginile au fost preluate cu ajutorul unor telescoape performante, în funcţie de

anumite caracteristici, corpurile cereşti au putut fi clasificate cu acurateţe mărită.

Robotica este unul dintre domeniile în care aceste sisteme sunt foarte des folosite.

Spre exemplu, un robot care asamblează piese trebuie să le poată identifica. Toate aceasta se

pot realiza cu ajutorul programelor specializate, care practic indexează bazele de date cu

conţinut multimedia.

3.1.4. Medicină

3.1.5. Web mining

3.2. Îmbunătățiri aduse tehnicilor de clustering. Hibridizare.Problemele de clustering apar în tot mai multe domenii și de aceea se încearcă

eficientizarea acestora prin diferite metode. Căteva direcții noi de cercetare sunt următoarele:

combinarea agenților inteligenți cu tehnici de clustering, hibridizarea tehnicilor de clustering,

3.2.1. Clustering și agenți inteligenți în web mining

În probleme de data mining s-au încercat combinarea unor algoritmi cunoscuți de

clustering cu agenți inteligenți. La sistemele de analiză Web s-a observat faptul că din cauza

analizei în timp real, analizatorul web nu reușește performanțe deosebite în cazul în care

acesta trebuie atât să realizeze analiza conținutului folosind clustering, cât și să analizeze

continuu rezultatele obținute. Din acest motiv un agent inteligent a fost însărcinat să grupeze

conținutul analizat cu ajutorul unui algoritm de clustering. În acest caz, sistemul realizat este

unul multi-agent, compus din doi agenți agenți, unul care realizează clustering propriu-zis și

altul care evaluează performanțele algoritmului de clustering aplicat. Agenții pot schimba

informații despre clusteri între ei, iar întregul sistem pote determina numărul de clusteri

existenți. Algoritmul de clustering folosit este K-Means, însă sunt folosite și rețele Kohonen

– hărți cu auto-organizare (Self Organizing Maps - SOM) și Principal Component Analysis

(PCA). Pentru a testa această aplicație s-au folosit setul de date Iris din UCI Repository [15],

și s-au aplicat pe rând PCA, SOM și apoi K-Means, ajungându-se la o performanță în

recunoașterea clusterilor de 99.48%. [16]

3.2.2. Clustering folosit în sisteme predictive

Pentru a elimina limitările anumitor tehnici de clustering, cum ar fi Fuzzy C-Means, s-a

încercat dezvoltarea unor algoritmi hibrizi. Astfel, s-a combinat Fuzzy C-Means, care e un

algoritm rapid, însă e sensibil la datele de inițializare, la fel ca si K-Means, cu Rețele

Neuronale multistrat și cu Algoritmi Genetici. Modelul rezultat, Genetic Fuzzy Neural

Network (GFNN) a fost folosit pentru crearea unui model utilizat la predicția falimentului

unor instituții și investitori, pe baza analizelor financiare. Rata de predicție corectă a

sistemului bazat pe algoritmul hibrid fiind de 98.33%.[17]

3.2.3. Clustering în cadrul GIS (Geographical Information System)

Sistemul GIS (Geographical Information System) a fost introdus în anul 1960 și este

utilizat la studiul căilor de comunicație, planificarea dezvoltării managementului localităților,

managementul datelor spațiale, a rețelelor publice de apă, canalizare, electricitate, dar putând

fi folosit și la localizarea și monitorizarea vehiculelor publice. Conceptual, GIS reprezintă o

stivă de hărți, în cadrul căreia fiecare strat este corelat cu celelalte. Acest tip de sisteme dețin

baze de date hibride, unde informațiile sunt atât atribute de diverse tipuri, cât și informații

spațiale.

Bazele de date folosite în cadrul GIS sunt complexe și foarte mari din perspectiva

numărului de obiecte existente, atribute sau caracteristici spațiale. Un astfel de sistem este

conceput în așa fel încât să poată accesa o bază de date sub formă de hărți, care pot fi

suprapuse, combinate sau analizate, fiind caracterizate de obiecte geometrice. Legăturile

dintre obiectele care sunt situate în același strat sau în straturi diferite pot fi extrem de

complexe mai ales datorită atributelor care implică proprietăți geometrice, topologice sau

semantice. Este imposibil ca un utilizator să poată identifica anumite informații greu de

descoperit în interiorul unei astfel de baze de date din cauza complexității acesteia, iar acesta

este motivul pentru care au fost introduse metode de clustering pentru identificarea unor

atribute necunoscute anterior, în scopul generalizării acestora. Acest tip de abordare este

relativ nou, introdus mai întâi de Jiang în lucrarea [18].

Jiang a utilizat tehnici de clustering pentru identificarea caracteristicilor cartografice

necesare întocmirii unui sistem GIS. Atributele elementelor inițiale au fost coordonatele

geometrice x și y, astfel încât procesul de generalizarea a implicat doar proprietățile

geometrice ale elementelor. Baza de date a cuprins 179 de obiecte, iar pentru determinarea

caracteristicilor necesare pentru procesul de generalizare s-au folosit două tehnici de

clustering: K-means și clustering ierarhic. În urma aplicării metodei K-means au fost obținute

100 de grupuri, iar modelele rezultate în urma procesului de determinare de caracteristici

generale au respectat poziționarea spațială a obiectelor din baza de date. În urma aplicării

clusteringului ierarhic, pentru baza de date inițială s-a observat că cea mai bună metodă

metodă a fost cea a distanței medii (average linkage), iar cea mai bună măsura pentru a

reflecta dinstanța dintre obiecte a fost distanța Euclidiană. [11]

Prin exemplele prezentate s-a demonstrat că tehnicile de clustering pot constitui un

suport important în diferite procese.

4. Prezentarea aplicației

4.1. Motivație

Aplicația este concepută cu scopul de a realiza o analiză comparativă între diferite

tipuri de clustering, în vederea observării de diferențe între rezultatele și performanțele

generale obținute de fiecare algoritm în parte. Aceasta dorește să surprindă motivațiile care

stau la baza apariției noilor tendințe din Inteligența Artificială în general și la unii algoritmi

de clustering în particular.

În cadrul 2-ClustSystem au fost implementați doi algoritmi cunoscuți din clustering,

Fuzzy C-means și K-means, precum și diferite măsuri de performanță a rezultatelor obținute

în urma aplicării de algoritmi de clustering, precum: distanța inter-cluster, distanța intra-

cluster, indexul Dunn, indexul Davies-Bouldin. Totodată, aplicația oferă facilitatea de a

observa modul aproximativ de dispoziție a datelor în clusteri prin intermediul unui grafic de

dispersie.

Concluzii

Bibliografie

1. Mitchell, Tom. Machine Learning. Boston : McGraw-Hill Science/Engineering/Math, 1997.

2. MacKay, David J. C. Information Theory, Inference and Learning Algorithms. Cambridge : Cambridge University Press, 2003.

3. Nilsson, Nils J. Introduction to Machine Learning: an early draft of a proposed textbook. Stanford : s.n., 1998.

4. Russel, Stuart J. și Norvig, Peter. Artificiall Inteligence A Modern Approach. New Jersey : Alan Apt, 1995.

5. Analyzing Animated Movie Contents for Automatic Video Indexing. Ionescu, B., și alții. 2011, Machine Learning Techniques for Adaptive Multimedia Retrieval: Technologies Applications and Perspectives.

6. Gan, G., Ma, C. și Wu, J. Data Clustering: Theory, Algorithms and Applications. Philadelphia : SIAM, 2007.

7. Petrescu, Mary. Clustering Ierarhic. Craiova : Else, 2010.

8. Tryon, R. C. Cluster Analysis. Ann Arbor : MI: Edwards Brothers, 1939.

9. Hapgood, Adrian A. Intelligent Systems for Engineers and Scientists. Boca Raton, Florida : CRC Press LLC, 2000.

10. Pop, Horia F. Sisteme inteligente în probleme de clasificare. Cluj-Napoca : Mediamira, 2004.

11. Cârțină, Gheorghe, Grigoraș, Gheorghe și Bobric, Elena-Crenguța. Tehnici de clustering în modelarea fuzzy. Aplicații în Electroenergetică. Iași : Venus, 2005.

12. SciKits. 4.2. Clustering - scikits.learn v0.8 documentation. scikit-leanr: machine learning in Python. [Interactiv] 1 January 2011. [Citat: 23 May 2012.] http://scikit-learn.org/0.8/modules/clustering.html.

13. Ongoing Research in Document Classification at the "Lucian Blaga" University of Sibiu. Crețulescu, R. G. Delft : s.n., 2011. the 5th International Symposium on Intelligent Distributed Computing IDC2011.

14. Muntean, C. Spss Analiza Cluster. Scribd.com. [Interactiv] 27 January 2011. http://ro.scribd.com/doc/47654684/Spss-Analiza-Cluster#outer_page_4.

15. Frank, A și Asuncion, A. UCI Machine Learning Repository: Iris Data Set. UCI Machine Learning Repository. [Interactiv] 2010. http://archive.ics.uci.edu/ml.

16. Park, Jung-Eun și Oh, Kyung-Whan. Multi-Agent Systems for Intelligent Clustering. s.l. : World Academy of Science, Engineering and Technology, 2005.

17. Martin, A., și alții. A hybrid model for bankruptcy prediction using Genetic Algorithm, Fuzzy C-Means and MARS. International Journal on Soft Computing ( IJSC ). Bhangalore : s.n., 2011.

18. Jiang, B. Spatial Clustering forMining Knowledge in Support of Generalization Processes in GIS. Leicester : ICA, 2004.