Bài tập luyện tập Gom cụm

Phiếu luyện tập chủ đề gom cụm, Clustering, trình bày các bài tập theo tám nhóm chủ đề và khép lại bằng phần chú thích công thức tham khảo. Phiếu do các giảng viên thực hành soạn thảo và duy trì, với sự đóng góp của Th.S Nguyễn Thị Thu Hằng, Th.S Nguyễn Ngọc Đức và Th.S Lê Nhựt Nam.

Tổng quan về các phương pháp gom cụm¶

Bài 1¶

Mô tả ngắn gọn và cho ví dụ minh họa cho mỗi phương pháp gom cụm sau:

• Phương pháp phân hoạch, Partitioning methods.

• Phương pháp phân cấp, Hierarchical methods.

• Phương pháp dựa trên mật độ, Density-based methods.

• Phương pháp dựa trên lưới, Grid-based methods.

• Phương pháp gom cụm hai chiều, Bi-clustering methods.

Bài 2¶

Phân biệt học có giám sát, supervised learning, và học không giám sát, unsupervised learning. Trong bối cảnh đó, gom cụm thuộc loại nào? Nêu ít nhất ba ứng dụng thực tế của gom cụm trong công nghiệp và nghiên cứu.

Bài 3¶

Nêu và giải thích bốn tiêu chí chất lượng mà một phương pháp gom cụm tốt cần đáp ứng. Với mỗi tiêu chí, hãy cho biết thuật toán nào, trong các thuật toán mà bạn biết, đáp ứng tốt và thuật toán nào còn hạn chế.

Phương pháp phân hoạch, K-Means và K-Medoids¶

Bài 4¶

Giả sử bài toán khai thác dữ liệu là gom cụm các điểm, với tọa độ dạng $(x, y)$, thành ba cụm, trong đó các điểm là:

Hàm khoảng cách là khoảng cách Euclidean. Giả sử ban đầu chọn $A_1$, $B_1$, $C_1$ là tâm của ba cụm tương ứng. Sử dụng thuật toán k-means để tìm:

• Ba tâm cụm sau vòng lặp đầu tiên.

• Ba cụm cuối cùng.

Bài 5¶

Dùng một ví dụ cụ thể để chỉ ra tại sao thuật toán k-means có thể không tìm được nghiệm tối ưu toàn cục, tức là không tối thiểu hóa được tổng phương sai trong cụm, within-cluster variation. Đề xuất một chiến lược khởi tạo để giảm thiểu vấn đề này.

Bài 6¶

Thuật toán k-means++ chọn tâm cụm ban đầu như sau: trước tiên chọn ngẫu nhiên đều một tâm từ tập dữ liệu, sau đó lặp lại, với mỗi điểm $p$ chưa được chọn, chọn nó làm tâm mới với xác suất tỉ lệ với $dist(p)^2$, trong đó $dist(p)$ là khoảng cách từ $p$ đến tâm gần nhất đã chọn, và lặp cho đến khi chọn đủ $k$ tâm.

Giải thích tại sao phương pháp này vừa giúp thuật toán k-means hội tụ nhanh hơn, vừa đảm bảo chất lượng kết quả gom cụm cuối cùng.

Bài 7¶

Viết mã giả, pseudocode, cho bước tái gán đối tượng, object reassignment, của thuật toán PAM, Partitioning Around Medoids. Giải thích tại sao PAM bền vững hơn k-means khi dữ liệu có nhiễu hoặc ngoại lệ, outliers.

Bài 8¶

Cả hai thuật toán k-means và k-medoids đều có thể thực hiện gom cụm hiệu quả.

• Minh họa điểm mạnh và điểm yếu của k-means so với k-medoids.

• Minh họa điểm mạnh và điểm yếu của cả hai so với phương pháp gom cụm phân cấp, hierarchical clustering.

Bài 9¶

Cho tập dữ liệu gồm 6 điểm trong không gian 2 chiều:

• Chạy thuật toán k-means với $k = 2$, khởi tạo tâm $m_1 = P_1$ và $m_2 = P_4$. Trình bày từng bước lặp cho đến khi hội tụ.

• Tính tổng bình phương trong cụm, Within-Cluster Sum of Squares, viết tắt WCSS, của kết quả cuối cùng.

• Nếu $k = 3$, hãy dự đoán kết quả gom cụm sẽ như thế nào? Giải thích.

Phương pháp phân cấp, Hierarchical Clustering¶

Bài 10¶

Chứng minh rằng trong công thức Lance-Williams:

• Phương pháp single-linkage tương đương với $\alpha_i = \alpha_j = 0.5$, $\beta = 0$, $\gamma = -0.5$.

• Phương pháp complete-linkage tương đương với $\alpha_i = \alpha_j = 0.5$, $\beta = 0$, $\gamma = 0.5$.

• Tiêu chuẩn Ward tương đương với $\alpha_i = \frac{n_i + n_k}{n_i + n_j + n_k}$, $\alpha_j = \frac{n_j + n_k}{n_i + n_j + n_k}$, $\beta = -\frac{n_k}{n_i + n_j + n_k}$, $\gamma = 0$.

Bài 11¶

Cho ma trận khoảng cách của 5 điểm dữ liệu như sau:

• Xây dựng dendrogram bằng phương pháp single-linkage.

• Xây dựng dendrogram bằng phương pháp complete-linkage.

• So sánh hai dendrogram và nhận xét sự khác biệt về hình dạng cụm.

Bài 12¶

Tại sao BIRCH gặp khó khăn trong việc tìm cụm có hình dạng tùy ý, arbitrary shape, trong khi OPTICS thì không? Đề xuất các sửa đổi cho BIRCH để nó có thể tìm cụm có hình dạng tùy ý.

Bài 13¶

So sánh phương pháp gom cụm phân cấp kết tụ, agglomerative, và phân chia, divisive. Với mỗi phương pháp:

• Mô tả quy trình tổng quát, tức thuật toán.

• Nêu độ phức tạp tính toán.

• Cho biết ưu và nhược điểm trong thực tế.

Phương pháp dựa trên mật độ, DBSCAN và OPTICS¶

Bài 14¶

Chứng minh rằng trong DBSCAN*, quan hệ density-connectedness là một quan hệ tương đương, equivalence relation, tức là thỏa mãn ba tính chất: phản xạ, reflexive, đối xứng, symmetric, và bắc cầu, transitive.

Bài 15¶

Chứng minh rằng trong DBSCAN*, với giá trị MinPts cố định và hai ngưỡng lân cận $\varepsilon_1 < \varepsilon_2$, một cụm $C$ xác định theo $\varepsilon_1$ và MinPts phải là tập con của một cụm $C'$ xác định theo $\varepsilon_2$ và MinPts.

Bài 16¶

Viết mã giả cho thuật toán OPTICS. Giải thích ý nghĩa của hai khái niệm core-distance và reachability-distance, đồng thời mô tả cách đọc biểu đồ reachability plot để xác định cụm.

Bài 17¶

Nêu các điều kiện mà phương pháp gom cụm dựa trên mật độ phù hợp hơn phương pháp phân hoạch và phân cấp. Cho ví dụ ứng dụng cụ thể để minh họa cho lập luận được đưa ra.

Bài 18¶

Cho tập điểm dữ liệu 2 chiều và tham số $\varepsilon = 2$, MinPts $= 3$:

• Xác định các điểm lõi, core points, điểm biên, border points, và điểm nhiễu, noise points.

• Trình bày các cụm được hình thành bởi DBSCAN.

Phương pháp dựa trên lưới, STING và CLIQUE¶

Bài 19¶

Viết mã giả cho bước tìm các ô dày đặc, dense cells, trong tất cả các không gian con, subspaces, của thuật toán CLIQUE.

Bài 20¶

So sánh hai thuật toán STING và CLIQUE theo các tiêu chí: cấu trúc lưới sử dụng, cách xác định cụm, khả năng xử lý không gian cao chiều, và độ phức tạp tính toán. Phương pháp nào phù hợp hơn với dữ liệu có chiều cao? Giải thích.

Đánh giá chất lượng gom cụm¶

Bài 21¶

Trình bày ba nhiệm vụ chính trong đánh giá gom cụm:

• Đánh giá xu hướng gom cụm, clustering tendency. Thống kê Hopkins được sử dụng như thế nào cho nhiệm vụ này?

• Xác định số lượng cụm, number of clusters. Mô tả phương pháp Elbow và chỉ số Calinski-Harabasz.

• Đo lường chất lượng gom cụm, clustering quality. Phân biệt phương pháp nội tại, intrinsic, và ngoại tại, extrinsic.

Bài 22¶

Thảo luận mức độ phương pháp purity, entropy, và phương pháp dùng hệ số Jaccard thỏa mãn bốn yêu cầu cần thiết của phương pháp đánh giá gom cụm ngoại tại, extrinsic, bao gồm: tính thuần nhất của cụm, cluster homogeneity, tính đầy đủ của cụm, cluster completeness, ràng buộc túi, rag bag, và bảo toàn cụm nhỏ, small cluster preservation.

Bài 23¶

Cho kết quả gom cụm sau với nhãn thực, ground truth, đã biết:

• Tính purity tổng thể của kết quả gom cụm.

• Tính entropy cho từng cụm và entropy trung bình có trọng số.

• Tính chỉ số Rand, Rand Index, và hệ số Jaccard. So sánh và nhận xét.

Bài 24¶

Hệ số Silhouette của một điểm dữ liệu $i$ được định nghĩa là:

trong đó $a(i)$ là khoảng cách trung bình từ $i$ đến các điểm trong cùng cụm, $b(i)$ là khoảng cách trung bình nhỏ nhất từ $i$ đến các điểm trong cụm khác.

• Giải thích ý nghĩa của $s(i)$ khi $s(i) \approx 1$, $s(i) \approx 0$ và $s(i) < 0$.

• Tính hệ số Silhouette cho từng điểm trong Bài 4, giả sử kết quả gom cụm k-means đã hội tụ.

• Làm thế nào để sử dụng Silhouette trung bình để chọn số cụm $k$ tối ưu?

Bài 25¶

Chỉ số Dunn được định nghĩa là:

trong đó $dist(C_i, C_j)$ là khoảng cách giữa hai cụm và $diam(C_m)$ là đường kính của cụm $m$.

• Giải thích tại sao chỉ số Dunn lớn hơn thể hiện chất lượng gom cụm tốt hơn.

• Chỉ ra một hạn chế thực tế của chỉ số Dunn và đề xuất cách khắc phục.

Tích hợp và ứng dụng phương pháp gom cụm¶

Bài 26¶

Cho một ví dụ về cách tích hợp hai phương pháp gom cụm cụ thể, trong đó một thuật toán được sử dụng như bước tiền xử lý cho thuật toán kia. Ngoài ra, giải thích tại sao sự tích hợp này đôi khi dẫn đến cải thiện cả chất lượng lẫn hiệu quả gom cụm.

Bài 27¶

Gom cụm được công nhận là một nhiệm vụ khai thác dữ liệu quan trọng với nhiều ứng dụng rộng rãi. Cho một ví dụ ứng dụng cho mỗi trường hợp sau:

• Ứng dụng sử dụng gom cụm là chức năng khai thác dữ liệu chính.

• Ứng dụng sử dụng gom cụm như công cụ tiền xử lý dữ liệu cho các nhiệm vụ khai thác dữ liệu khác.

Bài 28¶

Các khối dữ liệu, data cubes, và cơ sở dữ liệu đa chiều chứa dữ liệu danh nghĩa, thứ tự và số trong dạng phân cấp hoặc tổng hợp. Dựa trên kiến thức của bạn về các phương pháp gom cụm, hãy thiết kế một phương pháp gom cụm tìm kiếm cụm trong các khối dữ liệu lớn một cách hiệu quả và chính xác.

Bài 29¶

Mô tả từng thuật toán gom cụm sau theo ba tiêu chí: hình dạng cụm có thể xác định, các tham số đầu vào cần chỉ định, và hạn chế:

• k-means

• k-medoids

• BIRCH

• DBSCAN

Bài 30¶

Mắt người rất nhanh và hiệu quả trong việc đánh giá chất lượng gom cụm cho dữ liệu 2 chiều. Hãy thiết kế một phương pháp trực quan hóa dữ liệu có thể giúp người dùng hình dung các cụm dữ liệu và đánh giá chất lượng gom cụm cho dữ liệu 3 chiều. Từ đó, cho phương pháp được đưa ra có thể mở rộng cho dữ liệu có số chiều cao hơn không?

Bài tập tổng hợp¶

Bài 31¶

Một công ty thương mại điện tử có dữ liệu 1000 khách hàng với hai thuộc tính: tổng chi tiêu trong năm, tính bằng triệu đồng, và số lần mua hàng. Sau khi chạy k-means với $k = 3$, ta thu được ba cụm:

• Tính tổng WCSS. Nếu chạy lại với $k = 4$, ta nên kỳ vọng WCSS thay đổi như thế nào? Giải thích bằng phương pháp Elbow.

• Diễn giải ý nghĩa kinh doanh của ba cụm khách hàng này.

• Thuộc tính nào nên được chuẩn hóa trước khi gom cụm? Tại sao?

Bài 32¶

Trong bài toán phân tích ảnh vệ tinh, dữ liệu gồm 10.000 pixel với 3 kênh màu R, G, B. Ta muốn phân đoạn ảnh thành các vùng địa lý khác nhau như rừng, nước, đô thị, đất trống.

• So sánh hiệu quả của k-means, DBSCAN và phân cấp agglomerative cho bài toán này. Phương pháp nào nên được chọn và tại sao?

• Làm thế nào để xác định số cụm $k$ phù hợp? Trình bày ít nhất hai phương pháp.

• Sau khi gom cụm, làm thế nào để đánh giá chất lượng kết quả nếu không có nhãn thực, ground truth?

Bài 33¶

Một bệnh viện muốn nhóm bệnh nhân dựa trên hồ sơ sức khỏe gồm: tuổi, huyết áp, đường huyết, BMI và kết quả xét nghiệm, tức 5 thuộc tính số. Dữ liệu có 2000 bệnh nhân, trong đó 5% có giá trị bất thường, tức ngoại lệ.

• Tại sao k-means không phải là lựa chọn tốt nhất cho bài toán này?

• Đề xuất pipeline gom cụm hoàn chỉnh, từ tiền xử lý đến đánh giá kết quả, giải thích lý do chọn từng bước.

• Kết quả gom cụm có thể hỗ trợ bệnh viện như thế nào trong việc cá nhân hóa phác đồ điều trị?

Chú thích và Công thức tham khảo¶

Ký hiệu và công thức quan trọng:

• Khoảng cách Euclidean: $d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}$

• Tổng bình phương trong cụm, WCSS: $WCSS = \sum_{j=1}^{k} \sum_{x \in C_j} \|x - \mu_j\|^2$

• Purity: $Purity = \frac{1}{N}\sum_{j=1}^{k} \max_i |C_j \cap L_i|$

• Entropy trung bình có trọng số: $H = -\sum_{j=1}^{k} \frac{|C_j|}{N}\sum_i \frac{|C_j \cap L_i|}{|C_j|}\log\frac{|C_j \cap L_i|}{|C_j|}$

• Silhouette: $s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}}$ với $s(i) \in [-1, 1]$

• Rand Index: $RI = \frac{TP + TN}{TP + TN + FP + FN}$

• Hệ số Jaccard: $J = \frac{TP}{TP + FP + FN}$

• Chỉ số Dunn: $D = \frac{\min_{i \ne j} dist(C_i, C_j)}{\max_m diam(C_m)}$