4.5 Algoritmus K-Means

Algoritmus k-priemeru

K-priemer je nezvyčajný názov pre algoritmus. Čítajte ďalej a dozviete sa, čo stojí za touto voľbou.

Aby sme vám uľahčili sledovanie príbehu algoritmu x-mean, použijeme súbor údajov zobrazený na obrázku nižšie. Skladá sa zo 100 párov bodov, predstavte si, že ide o hodnoty nejakých dvoch číselných atribútov.

Táto sekcia je spárovaná s Jupyter Notebook 10-k-means.ipynb. Ak chcete obsah ďalej sledovať, kliknite na odkaz a potom kliknutím  na tlačidlo otvorte obsah v prostredí Google Colab. Ak si poznámkové bloky prezeráte v lokálnom počítači, vyhľadajte poznámkový blok s rovnakým názvom v obsahu a spustite ho.

 Algoritmus k-priemeru by mal nájsť k zhlukov v množine údajov. Zhluky, ktoré tento algoritmus hľadá, sú určené ťažiskom , inštanciou, ktorá predstavuje stred zhluku.

 Počiatočným krokom algoritmu je inicializačný krok. V ňom musíme náhodne vybrať x ťažísk. Potom musíme zopakovať nasledujúce kroky:

Pre každú inštanciu musíme vypočítať euklidovskú vzdialenosť ku každému z ťažísk x a potom priradiť inštanciu k hviezdokope, ktorej ťažisko je najbližšie. Po usporiadaní všetkých inštancií prejdeme k ďalšiemu kroku.

Pre každý zo zhlukov x musíme vybrať nové ťažisko. Robíme to tak, že vypočítame priemer inštancií, ktoré sú v každom zo zhlukov, a túto hodnotu deklarujeme ako nový ťažisko. Potom sa opäť vrátime ku kroku 1.

Algoritmus zhlukovania sa skončí, keď sa hodnoty ťažísk klastra stabilizujú. To by znamenalo, že v dvoch po sebe nasledujúcich iteráciách dostaneme ťažidlá, ktoré sa líšia veľmi málo, menej ako nejaká vopred určená presnosť.

Samotný algoritmus k-priemeru nie je nepríjemný na programovanie, takže to urobíme spoločne. Predtým zvážme niektoré technické podrobnosti:

Jedným z príkladov súboru údajov je dvojica čísel, povedzme (2, -3). To znamená, že ťažisko bude mať tiež dvojicu čísel a bude mať dva cooridnáty;

Ak sú (10, 2) a (4, -4) dve inštancie súboru údajov, vypočítame inštanciu predstavujúcu ich priemer ako (10 + 42, 2 − 42) = (7, -1);

Ak sú (0, 0) a (3, 4) dve inštancie súboru údajov, vypočítame euklidovskú vzdialenosť medzi nimi ako (3 − 0)2 + (4 − 0)2.

V datasete budeme hľadať štyri klastre. Prečo sme si vybrali túto problematiku, zvážime o niečo neskôr. Teraz sa pripravme na naprogramovanie algoritmu.

Premenná k označuje počet zhlukov. K = 4.

Ťažiská zhluku označíme premennou ťažiska. Keďže máme k zhluku, bude to pole dĺžky k . Jeden ťažisko je, ako sme povedali, jedna dvojica čísel, takže prvky tohto poľa budú dvojice čísel.

V procese klastrovania musíme sledovať, ktorý klaster spájame s ktorou inštanciou. Preto použijeme označenia na označovanie klastrov, podobne ako pri úlohách klasifikácie. Môžu to byť hodnoty 0, 1, 2 a 3. Vo všeobecnosti niektoré hodnoty 0, 1, 2, ..., k-1. Všetky štítky ponecháme v sérii labele_klastera.

Teraz si predstavíme funkciu generisi_centroide(X, k), ktorá generuje počiatočné ťažisko. Jej argumentmi sú množina inštancií X a počet zhlukov k a samotná funkcia náhodne vyberie k čísel z intervalu od 0 do 100 a vráti inštancie, ktoré sú na týchto pozíciách.

def generisi_centroide(X, k):
N = X.shape[0]
indices = np.random.randint(low = 0, high = N, size = k)
return X[indices]

Na obrázku nižšie sú znázornené vygenerované ťažiská. Každý z nich je vo farbe zhluku, ktorý predstavuje.

Počiatočné hodnoty ťažísk

Teraz napíšme funkciu podeli_podatke(X, centroidy, k) na rozdelenie množiny inštancií do zhlukov. Táto funkcia má ako argumenty množinu inštancií X, aktuálne ťažiská ťažiska a počet zhlukov k. Pre každú inštanciu vypočítame hodnotu vzdialenosti ku každému ťažisku, potom vyberieme ťažisko, ktoré je najbližšie, a dospejeme k záveru, že inštancia patrí do klastra, ktorý špecifikuje.

def divide_data(X, centroids, k):

  # initialize the list of cluster labels
  cluster_labels = []

  # iterate through the dataset instance by instance
  for x in X:

    # initialize the list of distances to centroids
    distances_to_centroids = []

    # then for each centroid ...
    for centroid in centroids:
      # ... calculate the distance between the instance and the centroid
      d = calculate_distance(x, centroid)

      # ... and add it to the list of distances
      distances_to_centroids.append(d)

    # when we have visited all centroids,
    # choose the centroid closest to the instance x
    label = np.argmin(distances_to_centroids)

    # conclude that the instance belongs to the cluster
    # determined by that centroid
    cluster_labels.append(label)

  # the result of the function is an array of cluster labels
  return np.array(cluster_labels)

Na obrázku nižšie môžete vidieť prvú iteráciu rozdelenia inštancií do klastrov.

Teraz napíšme calculate_new_centroids(X, cluster_labels, k), ktorá dokáže vypočítať hodnoty nových ťažísk na základe aktuálneho rozdelenia inštancií do zhlukov. Jeho argumentmi sú množina inštancií X, aktuálne inštancie cluster_labels a počet zhlukov k. Pre každý zo zhlukov by táto funkcia mala extrahovať inštancie, ktoré k nej patria, a potom vypočítať ich priemer.

def calculate_new_centroids(X, cluster_labels, k):
  # initialize the list of new centroids
  new_centroids = []
  # for each cluster
  for i in range(0, k):
    # ... extract the instances that belong to it
    instance_indices = cluster_labels == i
    instances_in_cluster = X[instance_indices]
    # then calculate the new centroid value
    # by averaging all instances in the cluster
    new_centroid = np.average(instances_in_cluster, axis=0)
    # add the calculated new centroid to the list of all centroids
    new_centroids.append(new_centroid)
  # the result of the function is an array of new centroids
  return np.array(new_centroids)

Nové ťažiská sú teraz zobrazené na obrázku nižšie. Všimnete si, že ťažiská žltých a fialových zhlukov sa "oddelili".

Zostáva zlúčiť úlohy jednotlivých krokov do funkcie, ktorá ich bude opakovať dostatočný počet krát. Bude to funkcia execute_clustering(X, k, epsilon=1e-4, max_iterations=300), v ktorej X predstavuje množinu inštancií, k počet zhlukov, blízkosť epsilonu, ktorú musia uspokojiť ťažiská zhluku, aby sa algoritmus zastavil. Existuje tiež maximálny počet iterácií, max_iterations ktorých navyše poskytujeme kritérium stop.

def execute_clustering(X, k, epsilon=1e-4, max_iterations=300):

  # step of initializing centroids
  centroids = generate_centroids(X, k)

  # in each iteration of the loop
  for i in range(0, max_iterations):

    # step 1: dividing instances into clusters
    cluster_labels = divide_data(X, centroids, k)

    # step 2: calculating new centroids
    new_centroids = calculate_new_centroids(X, cluster_labels, k)

    # checking stopping criteria
    # if they are met, we stop the algorithm
    if np.linalg.norm(new_centroids - centroids) < epsilon:
      break
    # otherwise, we move to the next iteration
    centroids = new_centroids.copy()

  # the result of the function is the final cluster labels and centroid values
  return cluster_labels, new_centroids

Vykonaním tejto funkcie sa dostávame aj ku konečnému rozdeleniu množiny inštancií do klastrov, čo je znázornené na obrázku nižšie.

V sprievodnej knihe kódov môžete vidieť aj animáciu, ktorá sleduje toto rozdelenie. Niektoré kroky sa spoliehajú na náhodné rozhodnutia (napríklad ak je inštancia rovnako blízko k viacerým ťažiskám), takže sa nenechajte zmiasť, ak sa niektoré hodnoty mierne líšia.