Implementare manualmente il KMEANS

Per iniziare ad usare matlab e usare praticamente il K-mean si è preso ispirazione dall'esercizio senza soluzione [ex7.pdf] dal corso Machine Learning da coursera.org [link] , in cui si chiede di impletentare il K-mean per comprimere un immagine.

1) Inizialmente si carica in una matrice 128x128x3 le informazioni dei di ogni singolo px, in base a rosso|verde|blu


                    %  Load an image 

                    A = double(imread('bird_small.png'));

2) Si dividono per 255 i valori dei px per avere un range che va da 0 ad 1


                    % Divide by 255 so that all values are in the range 0 - 1 

                    A = A / 255;

3) Si trasforma la matrice 128x128x3 in una 16384x3, ogni riga contiene un px. In colonna sono rappresentati il rosso, verde e blu.


                    % Size of the image [128x128x3] 

                    img_size = size(A); 

                    X = reshape(A, img_size(1) * img_size(2), 3);

4) Si settano gli iperparametri per il K-Means: K ed il numero di iterazioni


                    K = 3;              

                    max_iters = 10;

5) Si inizializzano in modo random i k centroidi.


                    initial_centroids = kMeansInitCentroids(X, K);

6) Si fa partire il K-Means


                    [centroids, idx] = runkMeans(X, initial_centroids, max_iters,true);

Algoritmo K-Means

a) Inizializzo i valori


                    % Mi salvo la grandezza della matrice, m =16384 ed n=3 

                    [m n] = size(X);


                    % Mi riprendo il valori di K (il numero delle righe della matrice "initial_centroids")  

                    K = size(initial_centroids, 1);


                    % Copio la variabile initial_centroids in centroids, inizializzo la variabile previous_centroids per poter visualizzare lo spostamento 

                    centroids = initial_centroids;      

                    previous_centroids = centroids;


                    % Creo la matrice idx [16384x1] e la inizializzo tutta a 0 

                    idx = zeros(m, 1);

b) Computo il K-means

Per ogni passo del ciclo

Trovo il più vicino valore del px al centroide nella funzione findClosestCentroids()
Sposto il centroide con la funzione centroids()


                    for i=1:max_iters                                                           

                          % For each example in X, assign it to the closest centroid 

                         idx = findClosestCentroids(X, centroids);                                   


                          % Given the memberships, compute new centroids 

                         centroids = computeCentroids(X, idx, K);                                    

                    end

findClosestCentroids()