KmeanClustering

Kmeans clustering là lớp các thuật toán học không giám sát (unsupervised learning) dựa trên việc lặp lại quá trình cập nhật lõi và nhãn của các data points một cách liên tục. Quá trình này có thể tóm tắt một cách đơn giản như sau:

Căn cứ vào số lượng lớp được phân chia mà thuật toán sẽ lựa chọn ngẫu nhiên K điểm data point làm trung tâm của K lớp gọi là centroids.
Quá trình assigment: Với mỗi một điểm bất kì sẽ tính khoảng cách của nó đến K centroids. Nhãn của điểm đó sẽ được cập nhật theo centroids có khoảng cách nhỏ nhất (tức điểm trung tâm gần nó nhất). Tức là ứng với mỗi điểm \(X_{i}\) tìm k sao cho:

\[||X_{i}-\mu_{k}||^2_{2} \rightarrow \min\]

Với \(k = \overline {1,K}\)

Quá trình update: Sau khi gán labels cho các điểm. Thuật toán sẽ update lại tọa độ các centroids sao cho giá trị từng chiều của nó bằng với trung bình cộng các điểm cùng labels. Mục đích update lại centroids là để tìm ra một lõi mới cho các nhóm mới.
Tiếp tục lặp lại quá trình assignment và update cho tới khi thuật toán đạt được sự hội tụ ở các centroids. Khi đó giá trị các centroids có thể coi là không đổi sau các vòng lặp và ta sẽ thu được kết quả cuối cùng.

Quá trình update của Kmean Clustering cũng giống như quá trình tự điều chỉnh để đạt được sự chính xác cao hơn (labels liên tục được update lại) cho tới khi đạt một ngưỡng tối ưu thì các centroids sẽ không còn thay đổi được nữa (centroids hội tụ).

Bên dưới là ứng dụng của thuật toán Kmean clustering được xây dựng dựa trên quá trình update trên:

library(ggplot2)
library(tidyverse)
library(dplyr)
library(MASS)

cov <- matrix(c(1,0,0,1), ncol = 2)
mean_1 <- c(1,2)
mean_2 <- c(8,4)
mean_3 <- c(3,6)

#Khởi tạo 3 cluster X, Y, Z có trung bình là các mean_1,2,3 và matrix covariance bằng nhau

X <- mvrnorm(n = 500, mu = mean_1, Sigma = cov)
Y <- mvrnorm(n = 500, mu = mean_2, Sigma = cov)
Z <- mvrnorm(n = 500, mu = mean_3, Sigma = cov)

data <- data.frame(X) %>% mutate(label = 1) %>% 
  bind_rows(data.frame(Y) %>% mutate(label = 2)) %>% 
  bind_rows(data.frame(Z) %>% mutate(label = 3)) %>% 
  mutate(label = as.character(label))

f_visual <- function(data){
  data %>% ggplot() +
    geom_point(aes(X1, X2, color = label, shape = label))
}

f_visual(data)

Tạo các hàm số:

f_init_cent: Tương ứng với bước 1: Khởi tạo centroids.

f_dist: Tính khoảng cách giữa các centroids với data point.

f_assign_labels: Tương ứng với bước 2: Assign lại labels dựa trên centroids.

f_update_centroids: Tương ứng với bước 3: Update centroids dựa trên labels mới được assign.

f_converged: Tương ứng với bước 4: Kiểm tra điều kiện hội tụ.

f_kmean_cluster: Hàm số chính chạy thuật toán kmean clustering với k lớp.

#Lựa chọn ngẫu nhiên k centroid
f_init_cent <- function(data, k){
  round(runif(k,1,nrow(data)), 0)
}

f_dist <- function(x,y){
  m <- matrix(c(x,y), byrow = TRUE, ncol = 2)
  dist(m)
}


f_assign_labels <- function (data, centroids){
  c_lab <- numeric(nrow(data))
  for(i in 1:nrow(data)) {
    c_dist <- apply(centroids, 1, f_dist, y = data[i,1:2]) 
    c_lab[i] <- match(min(c_dist), c_dist)
  }
  c_lab
}

labels

## function (object, ...) 
## UseMethod("labels")
## <bytecode: 0x000000001cbd81e8>
## <environment: namespace:base>

f_update_centroids <- function(data, labels, k){
  centroids <- data.frame()
  for (i in 1:k){
    centroid_i <- data[which(labels == i),1:2] %>% summarise_all(mean)
    centroids <- rbind(centroids, centroid_i)
  }
  centroids
}

f_converged <- function(centroids, new_centroids){
  identical(centroids, new_centroids)
}


f_kmean_cluster <- function(data, k){
  #Khởi tạo centroids
  centroids <- data[f_init_cent(data,k), 1:2]
  mx_labels <- matrix(ncol = 1500, byrow = TRUE)
  #Assign labels
  mx_labels[1,] <- f_assign_labels(data, centroids)
  i = 1
  while(TRUE){
    i = i + 1
    #Update centroids
    new_centroids <- f_update_centroids(data, mx_labels[i-1,], k)
    #Assign label
    mx_labels <- rbind(mx_labels,f_assign_labels(data, new_centroids))
    if(f_converged(new_centroids, centroids)){
      break
    }
    centroids <- new_centroids
  }
  list(new_centroids, new_labels = mx_labels[i,], i = i)
}


(result <- f_kmean_cluster(data, k = 3))

## [[1]]
##          X1       X2
## 1 7.9528710 3.978038
## 2 3.0129347 5.952306
## 3 0.9642184 1.995808
## 
## $new_labels
##    [1] 3 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##   [35] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##   [69] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [103] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 2 3 3 3 3 3 3 3 3
##  [137] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3
##  [171] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [205] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [239] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [273] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [307] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [341] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [375] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [409] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [443] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
##  [477] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1
##  [511] 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [545] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [579] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [613] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [647] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [681] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [715] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [749] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [783] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [817] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [851] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [885] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1
##  [919] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [953] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [987] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1021] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1055] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1089] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1123] 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1157] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1191] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1225] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2
## [1259] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1293] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1327] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1361] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2
## [1395] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1429] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2
## [1463] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
## [1497] 2 2 2 2
## 
## $i
## [1] 6

f_visual(data %>% mutate(label = as.character(result$new_labels)))

Ta nhận thấy thuật toán Kmean Clustering đưa ra kết quả phân nhóm khá chuẩn xác so với các nhóm ở đồ thị gốc. Một phần nguyên nhân có kết quả phân nhóm tốt là do các nhóm ban đầu khá tách biệt và có phân phối theo dạng hình cầu. Trên thực tế thì với những dữ liệu mà biên giới giữa các nhóm không rõ ràng và có những nhóm dữ liệu lồng trong 1 nhóm dữ liệu khác thì kết quả phân chia có thể bị nhiễu. Ngoài ra tốc độ hội tụ của thuật toán cũng phụ thuộc vào việc lựa chọn centroids khởi tạo lúc đầu. Trong một số trường hợp tốc độ này rất chậm và thậm chí là hội tụ bị dừng ở điểm cực trị địa phương.

Một số link tham khảo:

Kmean clustering wiki

Data camp

Machine Learning Cơ Bản

KmeanClustering

Pham Dinh Khanh

May 30, 2018