În clustering bazat pe centroid, clusterele sunt reprezentate de un vector central, care poate să nu fie neapărat membru al setului de date. Când numărul de clustere este fixat la k, clusteringul prin k-medii oferă o definiție formală ca o problemă de optimizare: găsiți k centre de cluster și atribuiți obiectele celui mai apropiat centru cluster, astfel încât distanțele pătrate de la cluster să fie minimizate.
Problema de optimizare în sine este cunoscută a fi dificilă și, prin urmare, abordarea comună este de a căuta doar soluții aproximative. O metodă de aproximare deosebit de cunoscută este algoritmul Lloyd, adesea denumit „algoritm k-medii”. Cu toate acestea, găsește doar un optim local și este de obicei rulat de mai multe ori cu diferiți inițializari aleatorii. Variațiile k-mediilor includ adesea astfel de optimizări, cum ar fi alegerea celor mai bune dintre rulările multiple, dar și restricționarea centroizilor la membrii setului de date (k-medoizi), alegerea medianelor (clustering k-mediane), alegerea centrelor inițiale mai puțin aleatoriu ( K-medii++) sau permiterea unei atribuiri de cluster neclare (c-medii fuzzy).
Majoritatea algoritmilor de tip k-medii necesită ca numărul de clustere – k – să fie specificat în prealabil, ceea ce este considerat a fi unul dintre cele mai mari dezavantaje ale acestor algoritmi. În plus, algoritmii preferă grupuri de dimensiuni aproximativ similare, deoarece vor atribui întotdeauna un obiect celui mai apropiat centroid. Acest lucru duce adesea la separarea incorectă a granițelor între grupuri (ceea ce nu este surprinzător, deoarece algoritmul a optimizat centrele clusterului, nu marginile clusterului).
K-medii are o serie de proprietăți teoretice interesante. În primul rând, partiționează spațiul de date într-o structură cunoscută sub numele de diagramă Voronoi. În al doilea rând, este aproape conceptual de clasificarea celui mai apropiat vecin și, ca atare, este popular în învățarea automată. În al treilea rând, poate fi văzut ca o variație a clasificării bazate pe model, iar algoritmul Lloyd ca o variație a algoritmului de maximizare a așteptărilor pentru acest model discutat mai jos.
Exemple de clustering k-medii:
(K- mediile separă datele în celule Voronoi, presupunând clustere de dimensiuni egale (nu este adecvată aici))
(K-mediile nu pot reprezenta clustere bazate pe densitate)
Sursa: Drew Bentley, Business Intelligence and Analytics. © 2017 Library Press, Licență CC BY-SA 4.0. Traducere și adaptare: Nicolae Sfetcu
Lasă un răspuns