Big Data Analytics - K-Means Clustering

Il clustering k-means mira a suddividere n osservazioni in k cluster in cui ciascuna osservazione appartiene al cluster con la media più vicina, fungendo da prototipo del cluster. Ciò si traduce in una partizione dello spazio dati nelle celle Voronoi.

Dato un insieme di osservazioni (x ₁ , x ₂ , ..., x _n ) , dove ogni osservazione è un vettore reale d-dimensionale, il clustering k-means mira a suddividere le n osservazioni in k gruppi G = {G ₁ , G ₂ ,…, G _k } in modo da minimizzare la somma dei quadrati all'interno del cluster (WCSS) definita come segue -

$$ argmin \: \ sum_ {i = 1} ^ {k} \ sum_ {x \ in S_ {i}} \ parallel x - \ mu_ {i} \ parallel ^ 2 $$

L'ultima formula mostra la funzione obiettivo che è ridotta al minimo per trovare i prototipi ottimali nel clustering k-means. L'intuizione della formula è che vorremmo trovare gruppi diversi tra loro e ogni membro di ogni gruppo dovrebbe essere simile agli altri membri di ciascun cluster.

L'esempio seguente mostra come eseguire l'algoritmo di clustering k-means in R.

library(ggplot2)
# Prepare Data 
data = mtcars  

# We need to scale the data to have zero mean and unit variance 
data <- scale(data)  

# Determine number of clusters 
wss <- (nrow(data)-1)*sum(apply(data,2,var)) 
for (i in 2:dim(data)[2]) { 
   wss[i] <- sum(kmeans(data, centers = i)$withinss) 
}  

# Plot the clusters 
plot(1:dim(data)[2], wss, type = "b", xlab = "Number of Clusters", 
   ylab = "Within groups sum of squares")

Per trovare un buon valore per K, possiamo tracciare la somma dei quadrati all'interno dei gruppi per diversi valori di K. Questa metrica normalmente diminuisce quando vengono aggiunti più gruppi, vorremmo trovare un punto in cui la diminuzione nella somma dei gruppi interni dei quadrati inizia a diminuire lentamente. Nel grafico, questo valore è rappresentato al meglio da K = 6.

Ora che il valore di K è stato definito, è necessario eseguire l'algoritmo con quel valore.

# K-Means Cluster Analysis
fit <- kmeans(data, 5) # 5 cluster solution 

# get cluster means  
aggregate(data,by = list(fit$cluster),FUN = mean) 

# append cluster assignment 
data <- data.frame(data, fit$cluster)