Phân cụm Phân cấp trong R

Các thao tác tiền xử lý cho Phân cụm

Có một vài điều bạn nên xử lý trước khi bắt đầu.

• Chuẩn hóa tỉ lệ (Scaling)

Bạn bắt buộc phải chuẩn hóa thang đo của các giá trị đặc trưng trước khi bắt đầu quá trình phân cụm. Lý do là các giá trị đặc trưng của mỗi quan sát được biểu diễn như các tọa độ trong không gian n chiều (n là số đặc trưng) rồi khoảng cách giữa các tọa độ này được tính. Nếu các tọa độ này không được chuẩn hóa, điều đó có thể dẫn đến kết quả sai lệch.

Ví dụ, giả sử bạn có dữ liệu về chiều cao và cân nặng của ba người: A (6ft, 75kg), B (6ft, 77kg), C (8ft, 75kg). Nếu bạn biểu diễn các đặc trưng này trong hệ tọa độ hai chiều, chiều cao và cân nặng, và tính khoảng cách Euclid giữa chúng, khoảng cách giữa các cặp sau sẽ là:

A-B : 2 đơn vị

A-C : 2 đơn vị

Vâng, độ đo khoảng cách cho thấy cả hai cặp A-B và A-C là tương tự nhau, nhưng thực tế thì rõ ràng không phải vậy! Cặp A-B giống nhau hơn cặp A-C. Do đó việc chuẩn hóa các giá trị này trước rồi mới tính khoảng cách là rất quan trọng.

Có nhiều cách để chuẩn hóa các giá trị đặc trưng, bạn có thể xem xét tiêu chuẩn hóa toàn bộ thang đo của tất cả giá trị đặc trưng (x(i)) về khoảng [0,1] (được gọi là chuẩn hóa min-max) bằng cách áp dụng phép biến đổi sau:

$ x(s) = x(i) - min(x)/(max(x) - min (x)) $

Bạn có thể dùng hàm normalize() của R cho việc này hoặc tự viết hàm như sau:

standardize <- function(x){(x-min(x))/(max(x)-min(x))}

Kiểu chuẩn hóa khác có thể đạt được qua phép biến đổi sau:

$ x(s) = x(i)-mean(x) / sd(x) $

Trong đó sd(x) là độ lệch chuẩn của các giá trị đặc trưng. Cách này sẽ đảm bảo phân phối giá trị đặc trưng có trung bình 0 và độ lệch chuẩn 1. Bạn có thể thực hiện qua hàm scale() trong R.

• Bù giá trị khuyết (Missing Value imputation)

Bạn cũng cần xử lý trước các giá trị thiếu/null/inf trong tập dữ liệu. Có nhiều cách xử lý các giá trị như vậy: loại bỏ, hoặc bù bằng trung bình, trung vị, mode, hay dùng một số kỹ thuật hồi quy nâng cao. R có nhiều gói và hàm để xử lý bù giá trị khuyết như impute(), Amelia, Mice, Hmisc... Bạn có thể đọc về Amelia trong hướng dẫn này.

Thuật toán Phân cụm Phân cấp

Thao tác then chốt trong phân cụm kết tụ phân cấp là lặp lại việc kết hợp hai cụm gần nhau nhất thành một cụm lớn hơn. Có ba câu hỏi chính cần được trả lời trước:

• Đại diện một cụm có hơn một điểm như thế nào?
• Xác định mức “gần” của các cụm ra sao?
• Khi nào thì dừng việc gộp cụm?

Hy vọng đến cuối hướng dẫn này bạn sẽ có thể trả lời tất cả các câu hỏi đó. Trước khi áp dụng phân cụm phân cấp, hãy xem qua cách nó hoạt động:

1. Bắt đầu bằng việc tính khoảng cách giữa mọi cặp điểm quan sát và lưu vào một ma trận khoảng cách.
2. Sau đó đặt mỗi điểm vào một cụm riêng.
3. Tiếp theo gộp các cặp điểm gần nhau nhất dựa trên khoảng cách từ ma trận khoảng cách, và kết quả là số lượng cụm giảm đi 1.
4. Sau đó tính lại khoảng cách giữa cụm mới và các cụm cũ, rồi lưu vào một ma trận khoảng cách mới.
5. Cuối cùng lặp lại bước 2 và 3 cho đến khi tất cả cụm được gộp thành một cụm duy nhất.

Có nhiều cách đo khoảng cách giữa các cụm để quyết định quy tắc phân cụm, thường được gọi là Phương pháp Liên kết (Linkage). Một số phương pháp thường gặp:

• Liên kết hoàn chỉnh (Complete-linkage): tính khoảng cách lớn nhất giữa các cụm trước khi gộp.

• Liên kết đơn (Single-linkage): tính khoảng cách nhỏ nhất giữa các cụm trước khi gộp. Liên kết này có thể dùng để phát hiện các giá trị cao trong tập dữ liệu vốn có thể là ngoại lệ vì chúng sẽ được gộp ở cuối cùng.

• Liên kết trung bình (Average-linkage): tính khoảng cách trung bình giữa các cụm trước khi gộp.

• Liên kết trọng tâm (Centroid-linkage): tìm trọng tâm của cụm 1 và cụm 2 rồi tính khoảng cách giữa hai trọng tâm trước khi gộp.

Việc chọn phương pháp liên kết hoàn toàn tùy thuộc vào bạn và không có phương pháp “chắc thắng” nào luôn cho kết quả tốt. Các phương pháp liên kết khác nhau dẫn đến các cụm khác nhau.

Dendrogram

Trong phân cụm phân cấp, bạn phân loại các đối tượng thành một hệ phân cấp giống như sơ đồ cây gọi là dendrogram. Khoảng cách của lần tách hay gộp (gọi là height) được hiển thị trên trục y của dendrogram bên dưới.

Trong hình trên, đầu tiên 4 và 6 được gộp thành một cụm, gọi là cụm 1, vì chúng gần nhau nhất, tiếp theo là điểm 1 và 2, gọi là cụm 2. Sau đó 5 được gộp vào cùng cụm 1 rồi đến 3 dẫn đến còn lại hai cụm. Cuối cùng hai cụm được gộp thành một và đây là lúc quá trình phân cụm dừng.

Một câu hỏi có thể làm bạn băn khoăn là làm sao quyết định khi nào dừng gộp cụm? Điều đó phụ thuộc vào hiểu biết miền của bạn về dữ liệu. Ví dụ, nếu bạn đang phân cụm các cầu thủ bóng đá trên sân dựa trên vị trí của họ (đại diện cho tọa độ để tính khoảng cách), bạn đã biết rằng bạn nên kết thúc với chỉ 2 cụm vì chỉ có hai đội chơi một trận đấu.

Nhưng đôi khi bạn cũng không có thông tin đó. Trong những trường hợp như vậy, bạn có thể tận dụng kết quả từ dendrogram để xấp xỉ số cụm. Bạn cắt cây dendrogram bằng một đường ngang tại độ cao mà đường có thể đi qua khoảng cách lớn nhất lên xuống mà không cắt qua điểm gộp. Trong trường hợp trên sẽ là giữa độ cao 1.5 và 2.5 như hình:

Nếu bạn cắt như hình, bạn sẽ thu được đúng hai cụm.

Lưu ý không bắt buộc chỉ cắt ở những vị trí như vậy; bạn có thể chọn bất kỳ điểm nào làm điểm cắt tùy vào số cụm bạn muốn. Ví dụ, cắt dưới 1.5 và trên 1 sẽ cho bạn 3 cụm.

Lưu ý đây không phải là quy tắc cứng nhắc để quyết định số cụm. Bạn cũng có thể xem các biểu đồ như Silhouette, elbow, hoặc một số thước đo số như chỉ số Dunn, gamma của Hubert, v.v. thể hiện biến thiên lỗi theo số cụm (k), và bạn chọn giá trị k nơi lỗi nhỏ nhất.

Đo lường chất lượng Cụm

Có lẽ phần quan trọng nhất trong bất kỳ tác vụ học không giám sát nào là phân tích kết quả. Sau khi bạn đã thực hiện phân cụm bằng bất kỳ thuật toán và tập tham số nào, bạn cần đảm bảo rằng mình đã làm đúng. Nhưng xác định bằng cách nào?

Có nhiều thước đo cho việc này, phổ biến nhất có lẽ là Chỉ số Dunn. Chỉ số Dunn là tỷ số giữa khoảng cách nhỏ nhất giữa các cụm và đường kính lớn nhất trong cụm. Đường kính của một cụm là khoảng cách giữa hai điểm xa nhau nhất trong cụm. Để có các cụm tách biệt tốt và gọn chặt, bạn nên hướng đến chỉ số Dunn cao hơn.

Phân cụm Phân cấp trong Thực tiễn

Giờ bạn sẽ áp dụng kiến thức đã học để giải một bài toán thực tế.

Bạn sẽ áp dụng phân cụm phân cấp trên tập dữ liệu seeds. Tập này gồm các phép đo thuộc tính hình học của nhân hạt thuộc ba giống lúa mì khác nhau: Kama, Rosa và Canadian. Nó có các biến mô tả thuộc tính của hạt như diện tích, chu vi, hệ số bất đối xứng, v.v. Mỗi giống lúa mì có 70 quan sát. Bạn có thể tìm thông tin chi tiết về tập dữ liệu tại đây.

Bắt đầu bằng cách nhập tập dữ liệu vào một dataframe với hàm read.csv().

Lưu ý tệp không có header và được phân tách bằng tab. Để đảm bảo khả năng tái lập kết quả bạn cần dùng hàm set.seed().

set.seed(786)
file_loc <- 'seeds.txt'
seeds_df <- read.csv(file_loc,sep = '\t',header = FALSE)Được hỗ trợ bởi

Vì tập dữ liệu không có tên cột nên bạn sẽ tự đặt tên cột dựa trên mô tả dữ liệu.

feature_name <- c('area','perimeter','compactness','length.of.kernel','width.of.kernal','asymmetry.coefficient','length.of.kernel.groove','type.of.seed')
colnames(seeds_df) <- feature_nameĐược hỗ trợ bởi

Nên thu thập một số thông tin cơ bản hữu ích về tập dữ liệu như kích thước, kiểu dữ liệu và phân phối, số lượng NA, v.v. Bạn sẽ thực hiện bằng các hàm str(), summary() và is.na() trong R.

str(seeds_df)
summary(seeds_df)
any(is.na(seeds_df))Được hỗ trợ bởi

Lưu ý rằng tập dữ liệu này có tất cả các cột là giá trị số. Không có giá trị thiếu cần làm sạch trước khi phân cụm. Tuy nhiên thang đo của các đặc trưng khác nhau và bạn cần chuẩn hóa. Ngoài ra, dữ liệu có nhãn và bạn đã có thông tin quan sát nào thuộc giống lúa mì nào.

Bây giờ bạn sẽ lưu nhãn vào một biến riêng và loại bỏ cột type.of.seed khỏi tập dữ liệu để thực hiện phân cụm. Sau đó bạn sẽ dùng nhãn thật để kiểm tra chất lượng phân cụm của mình.

seeds_label <- seeds_df$type.of.seed
seeds_df$type.of.seed <- NULL
str(seeds_df)Được hỗ trợ bởi

Bạn sẽ thấy mình đã bỏ cột nhãn thật khỏi tập dữ liệu.

Giờ bạn sẽ dùng hàm scale() của R để chuẩn hóa tất cả giá trị cột.

seeds_df_sc <- as.data.frame(scale(seeds_df))
summary(seeds_df_sc)Được hỗ trợ bởi

Lưu ý trung bình của tất cả các cột là 0 và độ lệch chuẩn là 1. Giờ khi đã tiền xử lý dữ liệu, đã đến lúc xây dựng ma trận khoảng cách. Vì tất cả giá trị ở đây là số liên tục, bạn sẽ dùng phương pháp khoảng cách euclidean.

dist_mat <- dist(seeds_df_sc, method = 'euclidean')Được hỗ trợ bởi

Ở bước này bạn nên quyết định dùng phương pháp liên kết nào và tiến hành phân cụm phân cấp. Bạn có thể thử mọi loại liên kết rồi sau đó quyết định loại nào hiệu quả hơn. Ở đây bạn sẽ tiếp tục với phương pháp liên kết average.

Bạn sẽ dựng dendrogram bằng cách vẽ đối tượng phân cụm phân cấp được xây dựng với hclust(). Bạn có thể chỉ định phương pháp liên kết qua tham số method.

hclust_avg <- hclust(dist_mat, method = 'average')
plot(hclust_avg)Được hỗ trợ bởi

Lưu ý cách dendrogram được dựng và mọi điểm dữ liệu cuối cùng gộp thành một cụm với height (khoảng cách) hiển thị trên trục y.

Tiếp theo, bạn có thể cắt dendrogram để tạo số cụm mong muốn. Vì trong trường hợp này bạn đã biết chỉ có ba loại lúa mì nên bạn sẽ chọn số cụm là k = 3, hoặc như bạn thấy trong dendrogram h = 3 bạn sẽ được ba cụm. Bạn sẽ dùng hàm cutree() của R để cắt cây với hclust_avg là một tham số và tham số còn lại là h = 3 hoặc k = 3.

cut_avg <- cutree(hclust_avg, k = 3)Được hỗ trợ bởi

Nếu bạn muốn xem trực quan các cụm trên dendrogram, bạn có thể dùng hàm abline() của R để vẽ đường cắt và chồng các khoang hình chữ nhật cho mỗi cụm trên cây bằng hàm rect.hclust() như trong đoạn mã sau:

plot(hclust_avg)
rect.hclust(hclust_avg , k = 3, border = 2:6)
abline(h = 3, col = 'red')Được hỗ trợ bởi

Bây giờ bạn có thể thấy ba cụm được bao trong ba hộp màu khác nhau. Bạn cũng có thể dùng hàm color_branches() từ thư viện dendextend để trực quan hóa cây với các nhánh màu khác nhau.

Nhớ rằng bạn có thể cài đặt gói trong R bằng lệnh install.packages('package_name', dependencies = TRUE).

suppressPackageStartupMessages(library(dendextend))
avg_dend_obj <- as.dendrogram(hclust_avg)
avg_col_dend <- color_branches(avg_dend_obj, h = 3)
plot(avg_col_dend)Được hỗ trợ bởi

Giờ bạn sẽ gắn kết quả phân cụm thu được trở lại dataframe gốc dưới tên cột cluster với mutate() từ gói dplyr và đếm có bao nhiêu quan sát được gán vào mỗi cụm bằng hàm count().

suppressPackageStartupMessages(library(dplyr))
seeds_df_cl <- mutate(seeds_df, cluster = cut_avg)
count(seeds_df_cl,cluster)Được hỗ trợ bởi

Bạn sẽ thấy có bao nhiêu quan sát được gán vào mỗi cụm. Lưu ý rằng trong thực tế, từ dữ liệu có nhãn, bạn có 70 quan sát cho mỗi giống lúa mì.

Thông thường, người ta đánh giá xu hướng giữa hai đặc trưng dựa trên kết quả phân cụm để rút ra thêm insight hữu ích theo từng cụm. Như một bài tập, bạn có thể phân tích xu hướng giữa perimeter và area của lúa mì theo từng cụm với gói ggplot2.

suppressPackageStartupMessages(library(ggplot2))
ggplot(seeds_df_cl, aes(x=area, y = perimeter, color = factor(cluster))) + geom_point()Được hỗ trợ bởi

Lưu ý rằng với tất cả các giống lúa mì, có vẻ tồn tại mối quan hệ tuyến tính giữa chu vi và diện tích của chúng.

Vì bạn đã có nhãn thật cho tập dữ liệu này, bạn cũng có thể đối chiếu lại kết quả phân cụm bằng hàm table().

table(seeds_df_cl$cluster,seeds_label)Được hỗ trợ bởi

Nếu bạn xem bảng được tạo, bạn sẽ thấy rõ ba nhóm với 55 phần tử trở lên. Tổng thể, bạn có thể nói rằng các cụm đủ tốt để đại diện cho các loại hạt khác nhau vì ban đầu bạn có 70 quan sát cho mỗi giống lúa mì. Các nhóm lớn hơn thể hiện sự tương ứng giữa các cụm và các loại thực tế.

Lưu ý rằng trong nhiều trường hợp bạn không có nhãn thật. Khi đó, như đã đề cập, bạn có thể dùng các thước đo khác như tối đa hóa chỉ số Dunn. Bạn có thể tính chỉ số dunn bằng hàm dunn() từ thư viện clValid. Ngoài ra, bạn có thể cân nhắc kiểm định chéo kết quả bằng cách tạo tập huấn luyện và kiểm tra như trong các thuật toán máy học khác, rồi thực hiện phân cụm khi bạn có nhãn thật.

So sánh với Thuật toán Phân cụm K-Means

Có thể bạn đã nghe về thuật toán phân cụm k-means; nếu chưa, hãy xem hướng dẫn này. Có nhiều khác biệt căn bản giữa hai thuật toán, dù trong các trường hợp khác nhau, mỗi thuật toán có thể hoạt động tốt hơn thuật toán kia. Một vài khác biệt:

• Khoảng cách sử dụng: Phân cụm phân cấp hầu như có thể xử lý mọi độ đo khoảng cách, trong khi k-means dựa vào khoảng cách Euclid.
• Tính ổn định của kết quả: k-means cần một bước ngẫu nhiên khi khởi tạo, có thể cho kết quả khác nếu chạy lại. Điều này không xảy ra với phân cụm phân cấp.
• Số lượng cụm: Trong k-means, bạn có thể dùng biểu đồ elbow, Silhouette, v.v. để tìm số cụm phù hợp; phân cấp cũng có thể dùng tất cả các cách đó và còn có lợi thế tận dụng dendrogram cho cùng mục đích.
• Độ phức tạp tính toán: K-means ít tốn kém tính toán hơn phân cụm phân cấp và có thể chạy trên tập dữ liệu lớn trong thời gian hợp lý; đây là lý do chính khiến k-means phổ biến hơn.

Kết luận

Chúc mừng! Bạn đã đi đến cuối hướng dẫn này. Bạn đã học cách tiền xử lý dữ liệu, những điều cơ bản về phân cụm phân cấp cùng các độ đo khoảng cách và phương pháp liên kết mà nó sử dụng trong R. Bạn cũng biết phân cụm phân cấp khác gì so với thuật toán k-means. Làm tốt lắm! Nhưng luôn còn nhiều điều để học. Tôi gợi ý bạn xem khóa học Unsupervised Learning in R của chúng tôi.