4.5 Algoritam k-sredina

K -sredina je neobično ime za jedan algoritam. Čitaj dalje da bi otkrio šta se krije iza ovog izbora!

Da bi lakše ispratili priču o algoritmu k-sredina, koristićemo skup podataka koji je prikazan na donjoj slici. On se sastoji od 100 parova tačaka, zamisli da su to vrednosti neka dva numerička atributa.

 Ova sekcija je uparena sa Jupyter sveskom  12-k-means.ipynb. Da bi mogao da pratiš sadržaj dalje, klikni na link, a potom i na dugme   da bi se sadržaj otvorio u okruženju Google Colab  . Ukoliko sveske pregledaš na lokalnoj mašini, među sadržajima pronađi svesku sa istim imenom i pokreni je. Za detaljnije instrukcije pogledaj sekciju Hands-on zona i lekciju Jupyter sveske za vežbu  .

U pratećem materijalu možeš da generišeš sve slike i animacije sam.

 Algoritamk-sredina (eng. k -means ) treba da pronađe k klastera u skupu podataka. Klasteri koje traži ovaj algoritam su određeni centroidom  , instancom koja predstavlja centar klastera.

 Početni korak algoritma je korak inicijalizacije. U njemu treba da odaberemo nasumično k centroida. Zatim treba da ponavljamo sledeće korake:

1.  Za svaku instancu treba da izračunamo euklidsko rastojanje do svake od k centroida, a zatim da instancu pridružimo onom klasteru čijoj centroidi je najbliža. Kada rasporedimo sve instance, prelazimo na naredni korak.
2.  Za svaki od k klastera treba da odaberemo nove centroide. To radimo tako što za svaki od klastera izračunamo prosek instanci koje se u njemu nalaze i baš tu vrednost proglasimo novom centroidom. Nakon toga se vraćamo ponovo na korak 1.

Algoritam klasterovanja se završava kada se vrednosti centroida klastera stabilizuju. To bi značilo da u dvema uzastopnim iteracijama dobijamo centroide koje se veoma malo razlikuju, manje od neke unapred zadate tačnosti.

Sam algoritam k-sredina nije neugodno isprogramirati pa ćemo to zajednički i uraditi. Pre toga, razmotrimo nekoliko tehničkih detalja:

• Jedna instanca skupa podataka je par brojeva, recimo (2, -3). To znači da će i centroida biti par brojeva i da će imati dve kooridnate;
• Ako su (10, 2) i (4, -4) dve instance skupa podataka, instancu koja predstavlja njihov prosek ćemo računati kao (10 + 42, 2 − 42) = (7, -1);
• Ako su (0, 0) i (3, 4) dve instance skupa podataka, euklidsko rastojanje između njih ćemo računati kao (3 − 0)2 +(4 − 0)2.

U skupu podataka ćemo tražiti četiri klastera. Zašto smo baš odabrali ovaj broj ćemo razmotriti nešto malo kasnije. Pripremimo se sada za programiranje algoritma.

• Promenljivom k označavaćemo broj klastera. Zbog prethodnog dogovora važi k = 4.
• Centroide klastera ćemo označavati promenljivom centroide. Kako imamo k klastera, ovo će biti niz dužine k  . Jedna centroida je, rekli smo, jedan par brojeva pa će elementi ovog niza biti parovi brojeva.
• U toku klasterovanja treba da pratimo kom klasteru pridružujemo koju instancu. Zato ćemo za obeležavanje klastera koristiti labele, slično kao u zadacima klasifikacije. To mogu da budu vrednosti 0, 1, 2 i 3. U opštem slučaju neke vrednosti 0, 1, 2, …, k-1. Sve labele klastera čuvaćemo u nizu labele_klastera.

Uvedimo sada funkciju generisi_centroide(X, k) koja generiše početne centroide. Njeni argumenti su skup instanci X i broj klastera k, a sama funkcija nasumično bira k brojeva iz intervala od 0 do 100 i vraća instance koje se nalaze na tim pozicijama.

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

Na donjoj slici su prikazane generisane centroide. Svaka od njih je u boji klastera koji predstavlja.

Početne vrednosti centroida

Napišimo sada funkciju podeli_podatke(X, centroide, k) kojom vršimo podelu skupa instanci u klastere. Ova funkcija kao argumente ima skup instanci X, trenutne centroide centroide i broj klastera k. Za svaku instancu ćemo izračunati vrednost rastojanja do svakog centroida, zatim ćemo odabrati onu centroidu koja je najbliža i zaključiti da instanca pripada klasteru koji ona određuje.

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 donjoj slici možeš da vidiš prvu iteraciju podele instanci u klastere.

Napišimo sada funkciju izracunaj_nove_centroide(X, labele_klastera, k) koja na osnovu tekuće podele instanci u klastere može da izračuna vrednosti novih centroida. Njeni argumenti su skup instanci X, tekuća obeležja instanci labele_klastera i broj klastera k. Za svaki od klastera, ova funkcija treba da izdvoji instance koje mu pripadaju i zatim da izračuna njihov prosek.

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)

Nove centroide su sada prikazane na donjoj slici. Primetićeš da su se centroide žutog i ljubičastog klastera ”razdvojile”.

Ostaje još da objedinimo zadatke pojedinačnih koraka u funkciju koja će ih ponoviti dovoljan broj puta. To će biti funkcija izvrsi_klasterovanje(X, k, epsilon = 1e-4, broj_iteracija = 300) u kojoj X predstavlja skup instanci, k broj klastera, epsilon bliskost koju treba da zadovolje centroide klastera kako bi se algoritam zaustavio. Tu je i maksimalni broj iteracija max_broj_iteracija kojim dodatno obezbeđujemo zaustavni kriterijum.

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

Izvršavanje ove funkcije nas dovodi i do finalne podele skupa instanci na klastere koja je prikazana na donjoj slici.

U pratećoj svesci sa kodom možeš da pogledaš i animaciju koja prati ovu podelu. Neki koraci se naslanjaju na nasumične odluke (na primer, ako je instanca podjednako blizu većem broju centroida) tako da nemoj da te zbuni ako se neke vrednosti malo razlikuju.