MapReduce DBSCAN và khởi tạo centroid

Giới thiệu

Bài này học chạy DBSCAN song song bằng chia vùng. Bạn dùng nó cho cụm hình lạ ở dữ liệu lớn.

Kiến thức cần nhớ

Vì sao DBSCAN khó song song

• K-means mỗi điểm quyết định độc lập nên chia mảnh tùy ý.
• DBSCAN quyết định theo hàng xóm, hàng xóm có thể sang máy khác.
• Chuỗi lan truyền dài có thể bò qua nhiều vùng.
• Cắt ẩu là đứt cụm nên cần pha gộp biên riêng.

Chia vùng và chạy địa phương

• Chia không gian thành vùng có vành đệm rộng ít nhất epsilon.
• Mỗi máy chạy DBSCAN trên vùng cộng vành của mình.
• Điểm sâu trong vùng chốt ngay, điểm vành chờ gộp.
• Vành hẹp hơn epsilon thì sót cầu, rộng quá thì tính trùng nhiều.

Gộp biên và chốt nhiễu

• Thu cụm chạm vành, xây đồ thị nối qua điểm chung rồi gộp.
• Điểm nhiễu địa phương mà kề lõi vùng bên thì cứu thành biên.
• Chỉ điểm không ai nhận mới là nhiễu thật.
• Gộp cụm trước rồi mới chốt nhiễu sau.

Khởi tạo và khi nào đáng giá

• Ngẫu nhiên đơn giản nhưng dễ rơi cực tiểu xấu.
• Tâm canopy rải đều theo mật độ nên tốt nhất cho dữ liệu lớn.
• DBSCAN không có tâm nhưng canopy giúp chọn epsilon theo vùng.
• Dữ liệu vừa 1 máy thì chạy đơn cho xong, vượt nhớ mới MapReduce.

Ví dụ

• Input: cụm nằm gọn 1 vùng không chạm biên. Output: trùng chạy đơn máy, khỏi gộp.
• Giải thích: không chạm vành thì không có gì để nối sang vùng khác.
• Input: chuỗi lan truyền vắt qua biên, vành đủ epsilon. Output: nối thành 1 cụm duy nhất.
• Giải thích: vành đủ rộng giữ được cầu lan truyền qua biên.

💻 Bài tập

Ngôn ngữ: Python 3 với NumPy và multiprocessing. Dùng DBSCAN ngày 48. Nộp vào day-088/.

Bài 1: Chia vùng có vành đệm

def partition(X, n_x: int, n_y: int, eps: float) -> list[dict]:
    """Chia hộp bao dữ liệu thành lưới n_x * n_y vùng.
       Mỗi vùng trả {"core_box": (x1,y1,x2,y2), "indices": chỉ số điểm trong core_box nới thêm eps mỗi phía}."""

Mọi điểm thuộc đúng 1 core_box
Điểm cách biên core_box dưới eps xuất hiện ở nhiều vùng (vành)

Bài 2: DBSCAN song song và gộp biên

1. Chạy DBSCAN địa phương trên từng vùng song song.
2. Gộp: 2 cụm địa phương có chung ít nhất 1 điểm lõi thì là cùng cụm toàn cục. Dùng Union-Find (ngày 33) để gộp.
3. Điểm là nhiễu ở vùng này nhưng là biên ở vùng khác thì thành biên.
4. Kết quả cuối phải khớp DBSCAN tuần tự trên toàn bộ dữ liệu (so sánh sau khi đổi tên cụm, chấp nhận khác ở điểm biên nằm giữa 2 cụm).

1 cụm dài vắt ngang 4 vùng -> sau gộp còn đúng 1 cụm

Bài 3: Thí nghiệm độ rộng vành (nâng cao)

1. Chạy với vành rộng 0.5 * eps, 1 * eps, 2 * eps. Với vành hẹp, chỉ ra cụm bị xé đôi.
2. Đo tổng số điểm được xử lý (cả trùng lặp) và thời gian theo độ rộng vành.
3. $n = 2 \cdot 10^5$ điểm. So thời gian song song với 1, 4, 16 vùng và DBSCAN tuần tự có lưới (ngày 48).

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

• Test phân vùng pass.
• Kết quả gộp khớp DBSCAN tuần tự.
• Có ví dụ vành hẹp làm xé cụm.
• Bảng thời gian và số điểm trùng lặp theo độ rộng vành.

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

• Vì sao DBSCAN khó song song hơn K-means?
• Vành đệm rộng bao nhiêu là đủ?
• Điểm nhiễu địa phương được cứu thế nào?
• Khi nào MapReduce DBSCAN đáng giá?

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