So sánh Phương Pháp Phân Cụm: Hierarchical vs K-means | Kinh tế vĩ mô | Trường Đại học kinh tế Thành Phố Hồ Chí Minh

1. Hierarchical Clustering (Phân cụm phân cấp)
Nguyên lý hoạt động
Hierarchical Clustering xây dựng một cấu trúc phân cấp dựa trên ma trận khoảng cách
hoặc độ tương đồng giữa các đối tượng. Phương pháp này có thể thực hiện theo hai chiến lược chính: 
Bottom-Up (Agglomerative): Còn được gọi là AGNES, phương pháp này bắt
đầu từ từng đối tượng đơn lẻ và kết hợp các đối tượng gần nhau thành từng
cụm nhỏ cho đến khi tất cả các đối tượng thuộc cùng một cụm lớn. Mỗi bước
kết hợp hai cụm gần nhất dựa trên khoảng cách nhỏ nhất hoặc trung bình giữa
các đối tượng của hai cụm. 
Top-Down (Divisive): Được gọi là DIANA, bắt đầu từ một cụm duy nhất chứa
tất cả các đối tượng, sau đó chia dần các cụm này thành các cụm con cho đến
khi mỗi đối tượng trở thành một cụm riêng. Cách làm này đòi hỏi việc tách
cụm sao cho độ tương đồng trong cụm vẫn cao và khoảng cách giữa các cụm vẫn lớn.
Các đặc điểm chính 
Cấu trúc phân cấp: Kết quả của Hierarchical Clustering là một cây phân cấp
(dendrogram), giúp dễ dàng quan sát mối quan hệ giữa các đối tượng ở nhiều cấp độ khác nhau. 
Khoảng cách và độ đo: Khoảng cách giữa các cụm có thể được tính bằng
nhiều phương pháp, bao gồm: o
Single-Linkage: Khoảng cách giữa hai cụm là khoảng cách giữa hai
điểm gần nhất của mỗi cụm. o
Complete-Linkage: Khoảng cách giữa hai cụm là khoảng cách lớn nhất
giữa các điểm của mỗi cụm. o
Average-Linkage: Sử dụng trung bình của tất cả các khoảng cách giữa các điểm trong hai cụm. Ưu điểm 
Không cần xác định số cụm trước: Đây là một lợi thế khi số cụm không được
biết trước, bởi vì phân cụm có thể được xem xét ở nhiều cấp độ khác nhau. 
Hiển thị trực quan: Cấu trúc phân cấp của dendrogram giúp ta có cái nhìn rõ
ràng về mối quan hệ giữa các đối tượng và sự phân chia của chúng. 
Hiệu quả với dữ liệu nhỏ và dạng cụm tự nhiên: Thích hợp với dữ liệu nhỏ,
giúp nhóm dữ liệu có đặc điểm nổi bật và dễ quan sát. Nhược điểm 
Không thể quay lui: Khi một đối tượng đã được phân vào một cụm cụ thể,
thuật toán không thể quay lại để thay đổi quyết định này. Điều này có thể dẫn
đến phân cụm không tối ưu. 
Không hiệu quả với dữ liệu lớn: Với dữ liệu có kích thước lớn, tốc độ xử lý
của phương pháp này chậm và tiêu tốn tài nguyên, do đó khó áp dụng trên dữ liệu lớn. 
Nhạy cảm với nhiễu và dữ liệu không đầy đủ: Hierarchical Clustering có thể
bị ảnh hưởng lớn nếu dữ liệu chứa nhiều nhiễu hoặc các điểm ngoại biên. Ứng dụng
Hierarchical Clustering thường được sử dụng cho các bài toán phân cụm nhỏ, như
phân tích phân cấp trong dữ liệu phân loại sinh học, phân loại văn bản, hoặc để tạo ra
các hệ thống phân cấp cho mục đích tổ chức dữ liệu.
2. K-means (Phân cụm K trung tâm)
Nguyên lý hoạt động
K-means là một thuật toán phân cụm dựa trên phân hoạch, trong đó cần xác định trước
số lượng cụm kkk. Quy trình cơ bản của K-means gồm các bước sau:
1. Khởi tạo trung tâm cụm: Chọn ngẫu nhiên kkk điểm trong không gian dữ liệu
làm trung tâm ban đầu cho kkk cụm.
2. Phân bổ các đối tượng vào cụm: Phân bổ mỗi điểm dữ liệu vào cụm có trung
tâm gần nó nhất, thường dựa trên khoảng cách Euclid.
3. Cập nhật trung tâm cụm: Sau khi phân bổ lại, cập nhật trung tâm của mỗi
cụm bằng cách tính trung bình của tất cả các điểm dữ liệu trong cụm.
4. Lặp lại quá trình: Quá trình này tiếp tục cho đến khi các cụm ổn định, nghĩa
là không có sự thay đổi trong phân bổ cụm hoặc đạt đến số lần lặp tối đa. Ưu điểm 
Đơn giản và nhanh chóng: Thuật toán K-means có độ phức tạp tính toán thấp,
do đó có thể xử lý nhanh các tập dữ liệu lớn. 
Hiệu quả cho các cụm có dạng hình cầu: K-means hoạt động tốt trên dữ liệu
có các cụm dạng hình cầu và đồng nhất. 
Dễ triển khai và mở rộng: Dễ dàng thực hiện trên nhiều loại dữ liệu khác
nhau và có thể mở rộng cho các bài toán lớn. Nhược điểm 
Phải biết trước số cụm kkk: Số cụm cần được xác định trước, điều này có thể
không khả thi nếu không có thông tin ban đầu về số cụm. 
Nhạy cảm với điểm ngoại biên: K-means có thể bị ảnh hưởng bởi các điểm
ngoại biên hoặc nhiễu, điều này có thể làm sai lệch trung tâm của cụm. 
Phụ thuộc vào cách khởi tạo trung tâm: Kết quả của K-means phụ thuộc vào
các điểm khởi tạo ban đầu. Có thể dẫn đến tối ưu cục bộ thay vì tối ưu toàn cục. 
Không phù hợp với cụm không lồi (non-convex): Với dữ liệu mà các cụm
không có dạng lồi, K-means không thể tạo ra phân cụm chính xác. Ứng dụng
K-means rất phổ biến trong nhiều lĩnh vực, bao gồm phân tích thị trường, phân tích
khách hàng, phát hiện xu hướng, và phân đoạn hình ảnh trong thị giác máy tính. So sánh tổng quan Đặc điểm Hierarchical Clustering K-means Chiến lược Bottom-Up hoặc Top-Down
Phân hoạch dựa trên số cụm kkk Số cụm
Không cần xác định trước Cần xác định trước Cấu trúc phân cấp Cụm với trung tâm cụm Kết quả (dendrogram) (centroid) Tốc độ Chậm với dữ liệu lớn
Nhanh, hiệu quả với dữ liệu lớn Nhạy cảm với Cao Cao nhiễu
Dạng cụm phù hợp Mọi dạng cụm nhỏ
Cụm lồi, dạng hình cầu
Khả năng quay lui Không thể quay lui
Có thể thay đổi trung tâm cụm