OPTICS và phân cụm phân cấp

Giới thiệu

Bài này học OPTICS cho dữ liệu nhiều mật độ. Bạn dùng nó khi DBSCAN 1 ngưỡng thất bại.

Kiến thức cần nhớ

Vì sao cần OPTICS

• Epsilon nhỏ giữ cụm dày nhưng xé cụm thưa thành nhiễu.
• Epsilon lớn giữ cụm thưa nhưng gộp cụm dày với nhiễu.
• Thực tế có cả trung tâm đông và ngoại ô thưa cùng lúc.
• OPTICS thay ngưỡng cứng bằng thứ tự sắp xếp.

Hai khoảng cách

• Khoảng cách lõi: bán kính nhỏ nhất để điểm thành lõi.
• Điểm vùng dày thì lõi nhỏ, vùng thưa thì lõi lớn.
• Lan truyền từ p tới q bằng max giữa lõi p và khoảng cách thật.
• Ví dụ đời thường: qua cầu hẹp hay rộng thì giá vé theo chỗ hẹp nhất.

Đồ thị lan truyền

• Duy trì hàng đợi ưu tiên theo lan truyền nhỏ nhất.
• Mỗi bước rút điểm rẻ nhất, ghi thứ tự và khoảng cách của nó.
• Vẽ thứ tự ngang và lan truyền đứng được đồ thị thung lũng.
• Thung lũng sâu là cụm dày, nông là cụm thưa, đỉnh cao là biên.

Trích cụm và phân cấp

• Cắt đồ thị ở 1 ngưỡng: đoạn liên tục dưới ngưỡng là 1 cụm.
• Hạ ngưỡng được cụm con dày, nâng ngưỡng gộp thành cụm cha.
• Agglomerative: mỗi điểm 1 cụm rồi gộp cặp gần nhất dần.
• Cắt cây dendrogram cao thấp khác nhau cho số cụm khác nhau.

Ví dụ

• Input: dữ liệu 1 cụm đều duy nhất. Output: đồ thị 1 thung lũng đơn.
• Giải thích: mọi điểm lan truyền rẻ như nhau nên nằm chung 1 hõm.
• Input: 2 cụm tách xa. Output: 2 thung lũng cách nhau bởi đỉnh cao.
• Giải thích: cầu nối giữa 2 cụm rất đắt nên thành đỉnh ngăn.

💻 Bài tập

Ngôn ngữ: Python 3 với NumPy. Không dùng sklearn.cluster.OPTICS trừ khi đối chiếu. Nộp vào day-083/.

Bài 1: OPTICS

def optics(X, min_pts: int, max_eps: float = np.inf) -> tuple[np.ndarray, np.ndarray, np.ndarray]:
    """Trả (ordering, reachability, core_distance).
       core_distance(p) = khoảng cách tới hàng xóm thứ min_pts (tính cả p), inf nếu không đủ.
       reachability(o từ p) = max(core_distance(p), dist(p, o)).
       Dùng heap theo reachability nhỏ nhất, cập nhật bằng lazy deletion."""

Dữ liệu 3 cụm Gauss mật độ khác nhau + 20 điểm nhiễu
-> reachability plot có 3 thung lũng, nhiễu nằm ở các đỉnh
Điểm đầu tiên trong ordering có reachability = inf

Vẽ reachability plot: trục x là thứ tự, trục y là reachability.

Bài 2: Tách cụm từ reachability plot

1. extract_dbscan(ordering, reachability, core_distance, eps): cắt ngang tại eps. Kết quả phải khớp DBSCAN ngày 48 với cùng eps (trừ khác biệt ở điểm biên).
2. Dữ liệu có 1 cụm dày nằm cạnh 1 cụm thưa. Chỉ ra không có eps nào của DBSCAN tách đúng cả hai, nhưng reachability plot thấy rõ cả hai.

Bài 3: Phân cụm phân cấp (nâng cao)

1. Tự cài agglomerative clustering với 3 cách nối: single, complete, average. $O(n^3)$ đơn giản là được với $n \le 300$.
2. Vẽ dendrogram bằng scipy.cluster.hierarchy.dendrogram từ ma trận linkage bạn tự tạo (đúng định dạng scipy).
3. Chạy 3 cách nối trên dữ liệu trăng lưỡi liềm. Cách nào tách đúng? Giải thích hiện tượng "chaining" của single link.

✅ Tiêu chí hoàn thành

• Reachability khớp sklearn.cluster.OPTICS (sai số 1e-9, cùng tham số).
• Có reachability plot và hình tách cụm.
• Có ví dụ DBSCAN thất bại mà OPTICS thấy được.
• Dendrogram 3 cách nối và giải thích chaining.

❓ Câu hỏi ôn tập

• Khoảng cách lõi là gì?
• Khoảng cách lan truyền tính thế nào?
• Đồ thị lan truyền đọc ra sao?
• Khi nào dùng OPTICS thay vì DBSCAN?

🌕 Bạn đã hoàn thành ngày 83. Làm hết bài tập phía trên rồi sang ngày tiếp theo.