Giới thiệu về các phương pháp phân cụm
Phân cụm (clustering) là kỹ thuật gom nhóm các đối tượng dữ liệu sao cho các đối tượng trong cùng một nhóm (cụm) có độ tương đồng cao, còn các đối tượng giữa các cụm khác nhau thì có độ khác biệt lớn. Có nhiều phương pháp phân cụm khác nhau, mỗi phương pháp phù hợp với các loại dữ liệu và bài toán cụ thể. Dưới đây là 5 phương pháp chính:
1. Phương pháp phân vùng (Partitioning Methods)
Cho một cơ sở dữ liệu gồm n đối tượng hoặc bộ dữ liệu, phương pháp phân vùng tạo ra k phân vùng của thông tin, trong đó mỗi phân vùng định nghĩa một cụm, và k < n. Phương pháp này phân chia dữ liệu thành k nhóm thỏa mãn:
- Mỗi nhóm phải chứa ít nhất một đối tượng.
- Mỗi đối tượng chỉ thuộc đúng một nhóm.
Cho trước số phân vùng k, phương pháp tạo phân vùng ban đầu, sau đó sử dụng phương pháp tái định vị lặp lại để cải thiện phân vùng bằng cách chuyển các đối tượng từ nhóm này sang nhóm khác. Tiêu chí chung của phân vùng tốt là: các đối tượng trong cùng cụm "gần" hoặc liên quan với nhau, trong khi các đối tượng của các cụm khác nhau "xa" hoặc rất khác biệt.
2. Phương pháp phân cấp (Hierarchical Methods)
Phương pháp phân cấp tạo ra một phân giải phân cấp của tập đối tượng dữ liệu cho trước. Có hai cách tiếp cận:
- Agglomerative (Bottom-up - Tự dưới lên): Bắt đầu với mỗi đối tượng tạo thành một nhóm độc lập. Kế tiếp kết hợp các đối tượng hoặc nhóm gần nhau, cho đến khi tất cả các nhóm được gộp thành một (cấp cao nhất của hệ thống phân cấp) hoặc thỏa mãn điều kiện dừng.
- Divisive (Top-down - Tự trên xuống): Bắt đầu với tất cả đối tượng trong cùng một cụm. Mỗi lần lặp, một cụm được chia thành các cụm nhỏ hơn, cho đến khi mỗi đối tượng nằm trong một cụm riêng biệt hoặc thỏa mãn điều kiện dừng.
3. Phương pháp dựa trên mật độ (Density-based Methods)
Một số phương pháp phân vùng dựa trên khoảng cách giữa các đối tượng, chỉ phát hiện được các cụm hình cầu và gặp khó khăn với các cụm hình dạng tùy ý. Các phương pháp dựa trên mật độ khắc phục nhược điểm này.
- DBSCAN: Phương pháp điển hình dựa trên mật độ, mở rộng cụm theo ngưỡng mật độ.
- OPTICS: Đánh giá thứ tự phân cụm tăng cường để phân tích cụm tự động và tương tác.
4. Phương pháp dựa trên lưới (Grid-based Methods)
Phương pháp này lượng tử hóa không gian đối tượng thành một số hữu hạn các ô tạo thành cấu trúc lưới. Các hoạt động phân cụm được thực hiện trên cấu trúc lưới này (không gian lượng tử hóa).
Ưu điểm: Thời gian xử lý nhanh, thường độc lập với số lượng đối tượng dữ liệu, chỉ phụ thuộc vào số ô trong mỗi chiều của không gian lượng tử hóa. Ví dụ: STING, CLIQUE, Wave-Cluster.
5. Phương pháp dựa trên mô hình (Model-based Methods)
Phương pháp này giả định một mô hình cho từng cụm và tìm sự phù hợp tốt nhất của các bản ghi với mô hình cho trước. Thuật toán dựa trên mô hình định vị cụm bằng cách tạo hàm mật độ phản ánh phân bố không gian của các điểm dữ liệu. Cách này cũng dẫn đến phương pháp tự động xác định số lượng cụm dựa trên thống kê tiêu chuẩn, tính đến "nhiễu" (noise) hoặc giá trị ngoại lai (outliers), từ đó tạo ra các phương pháp phân cụm mạnh mẽ (robust).