Universitatea babeş-bolyai cluj-napoca

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 , unde x_i, este o entitate neetichetată căreia îi este asignat un vector de atribute V_i 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:
   

2. 
   Fiecare grup conţine minim o entitate:
   

 ,

O altă proprietate poate fi considerată:

3. 
   O entitate apartine doar unui singur grup:
   

, ,  , , 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]