Khái niệm
Phân cụm dựa trên ràng buộc (constraint-based clustering) tìm cụm thỏa mãn sở thích/ràng buộc do người dùng nêu ra. Dựa trên bản chất ràng buộc, có thể áp dụng các cách tiếp cận khác nhau. Có 5 loại ràng buộc chính:
1. Ràng buộc trên từng đối tượng (Constraints on individual objects)
Định nghĩa ràng buộc trên đối tượng được phân cụm. Ví dụ: ứng dụng bất động sản, chỉ phân cụm không gian các biệt thự sang trọng trị giá >1 triệu USD. Ràng buộc này thu hẹp tập đối tượng cần phân cụm. Xử lý đơn giản bằng tiền xử lý (ví dụ: SELECT qua SQL), bài toán giảm thành unconstrained clustering.
2. Ràng buộc trên tham số phân cụm (Constraints on clustering parameters)
Người dùng muốn đặt giá trị mong muốn cho tham số phân cụm. Tham số phụ thuộc thuật toán cụ thể. Ví dụ: k (số cụm mong muốn) trong k-means; ε (bán kính) và MinPts (số điểm tối thiểu) trong DBSCAN. Dù tham số ảnh hưởng mạnh kết quả, chúng gắn liền thuật toán → thường không coi là constraint-based clustering chính thống.
3. Ràng buộc trên hàm khoảng cách/tương đồng (Constraints on distance/similarity functions)
Định nghĩa hàm khoảng cách/tương đồng khác nhau cho thuộc tính cụ thể của đối tượng, hoặc thước độ khác nhau cho cặp đối tượng cụ thể. Ví dụ: phân cụm vận động viên, dùng trọng số khác cho chiều cao, cân nặng, tuổi, trình độ.
4. Ràng buộc do người dùng chỉ định trên thuộc tính cụm riêng lẻ (User-specified constraints on individual cluster properties)
Người dùng chỉ định đặc điểm mong muốn của cụm kết quả, ảnh hưởng mạnh quá trình phân cụm.
Ví dụ thực tế: Công ty giao hàng muốn chọn vị trí k trạm dịch vụ trong thành phố. CSDL khách hàng: tên, vị trí, thời gian sử dụng dịch vụ, chi phí trung bình/tháng.
- Cách cơ bản: phân cụm không ràng buộc dùng hàm khoảng cách vị trí khách hàng.
- Cách thông minh hơn: chia khách hàng thành 2 lớp - khách hàng giá trị cao (cần dịch vụ thường xuyên, đều đặn) và khách hàng thường (cần dịch vụ thỉnh thoảng). Thêm ràng buộc:
- Mỗi trạm phải phục vụ ≥ 100 khách hàng giá trị cao.
- Mỗi trạm phải phục vụ ≥ 5.000 khách hàng thường.
5. Phân cụm bán giám sát dựa trên "giám sát một phần" (Semi-supervised clustering based on partial supervision)
Chất lượng unsupervised clustering cải thiện đáng kể bằng giám sát yếu. Dạng: ràng buộc cặp (cặp đối tượng gán nhãn cùng cụm hoặc khác cụm). Quy trình phân cụm có ràng buộc này gọi là semi-supervised clustering.