Universitatea babeş-bolyai cluj-napoca

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 = (x₁, x₂, ..., x_n) și Y = (y₁, y₂, ..., y_n), 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 x_i reprezintă măsura în care vectorul X posedă cea de-a i-a caracteristică, așadar x_i 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, va fi atribuită unui grup C_j, cu centroidul K_j care este cel mai apropiat de acest vector, iar K_j este actualizat după fiecare atribuire, folosind formula: , unde nr_j reprezintă numărul de entități care aparţin grupului C_j (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.