Analiza convergentei algoritmului de clasificare K-means
by Mihaela Irimia, Date: 2026-11-15
Obiectivul studiului:
Evaluarea stabilității structurale și a vitezei de convergență a algoritmului K-Means (K = 3) prin monitorizarea iterativă a reducerii varianței intra-cluster pe parcursul mai multor inițializări aleatorii distincte, în scopul identificării optimului global.
Descrierea setului de date
Prezentarea setului de date analizat
Descrierea variabilelor din setul de date analizat
Short description
Setul de date analizat este format din trei variabile numerice: PIB - ul pe cap de locuitor, rata de urbanizare si emisiile de carbon.
Variabilele analizate au fost transformate pentru a diminua asimetria si influenta valorilor extreme, respectiv standardizate (toate variabilele au media zero si varianta 1) pentru a putea compara rezultatele.
Simulam individual cele 150 de rulari ale algoritmului K-meanss (pentru k = 3)
In tabel este prezentat dispersia interna inregistrata la nivelul fiecarui cluster la fiecare pas.
tot.withinSS - este suma coloanelor SS_Cluster_1, SS_Cluster_2 si SS_Cluster_3 si este criteriul pe care algoritmul K-means cauta sa-l minimizeze la fiecare iteratie.
Scadere_WSS - ne arata cu cat s-a imbunatatit gruparea observatiilor de la o ieteratie la alta (fata de iteratia precedenta). In momentul in care Scadere_WSS = 0, media centroizilor nu se mai modifica, iar algoritmul se opreste.
Analiza convergentei modelului K-means
Reprezentarea grafica a convergentei modelelor K-means rulate. Putem observa modul in care variaza dispersia totala din interiorul clusterelor fiecarui model in functie de numarul de rulari/iteratii. Observam o scadere accentuata a valorilor dispersiei totale cu numarul de iteratii pana in punctul in care aceasta nu se mai modifica.
Am utilizat functia set.seed() - care fixeaza generatorul de puncte aleatoare - care permite mentinerea acelorasi puncte aleatorii (aceleasi tari alese ca centroizi) si implocit obtinerea acelorasi rezultate - adica asigura reproductibilitatea stiintifica a rezultatelor. La fiecare rulare a algoritmului, acesta porneste din aceleasi puncte aleatorii (tarile alese ca centroizi initiali), iar numarul de iteratii si valoarea WSS la fiecare iteratie vor fi aceleasi de fiecare data.
Pentru a urmari pas cu pas modul in care algoritmul atinge convergenta, adica fiecare iteratie interna a algoritmului K-mean pana al convergenta. Pentru a vedea evolutia pas cu pas (cum se modifică WSS la iteratia 1, iteratia 2, iteratia 3 etc. pana cand WSS nu mai scade), rulam algoritmul iteratie cu iteratie (iter.max = 1), pastrand centroizii de la pasul anterior ca punct de plecare pentru pasul urmator.Folosim algoritmul Lloyd - algoritmul clasic K-Means in 2 pasi: atribuire si recalculare centroizi.
Etapele algoritmului K-means sunt:
Initializarea pozitiilor centroizilor
Atribuire etichetelor
Recalcularea pozitie centroizilor
Repetarea pasilor 2 si 3 pana la atingerea convergenta
Extragem varianta optima finala a modelului (cel care prezinta cea mai mica valoare a variantei din interiorul custerelor in momentul in care atringe convergenta - centroizi sau media culsterelor nu se mai modifica).
Identificam modelul optim
Evolutia variantei din interiorul clusterelor (TWSS) a celor 150 de modele
Banda de variatie — diferenta dinte varianta maxima
si minima. La prima iteratie, datorita alegerii aleatoare a
centroizilor, diferentele sunt mari, insa pe masura ce numarul de
iteratii creste, banda se ingusteaza pana cand toate traictoriile
converg spre minimul global (116).
Prin urmare, numarul rularilor scade pe masura ce creste numarul iteratiilor - deoarece rularile care ponesc din puncte favorabile converg mai rapid, in timp ce cele care ponesc din puncte nefavorabile au nevoie de mai multe iteratii pentru a tinge convergenta.
Factori care ar putea afecta solutia …