MapReduce cho K-means và canopy clustering

Giới thiệu

Bài này học chạy K-means song song và canopy dọn đường. Bạn dùng nó để gom cụm dữ liệu terabyte.

Kiến thức cần nhớ

K-means song song

• Bước gán mỗi điểm độc lập nên chia trăm máy cùng làm.
• Map tính tâm gần nhất cho từng điểm rồi nhả cặp tâm điểm.
• Shuffle gom cùng tâm về 1 reduce, reduce tính trung bình ra tâm mới.
• Lặp tới khi tâm ổn định, mỗi vòng là 1 job.

Canopy tiền xử lý

• Phủ nhanh các tán bao điểm bằng 2 ngưỡng lỏng T1 và chặt T2.
• Lấy điểm chưa phủ làm tâm, điểm trong T1 vào tán, trong T2 bị xóa chờ.
• Điểm vành giữa 2 ngưỡng thuộc tán nhưng vẫn chờ làm tâm khác.
• Ví dụ đời thường: như khoanh vùng tìm kiếm trước khi soi kỹ từng nhà.

Canopy giúp K-means

• Chỉ so điểm với tâm có tán chứa nó, đỡ so với mọi tâm.
• Số tán sinh ra gợi ý số cụm k khỏi đoán mò.
• Lấy tâm tán làm centroid khởi đầu hội tụ nhanh hơn ngẫu nhiên.
• Tán lỏng quá thì khổng lồ vô dụng, chặt quá thì vụn như không phủ.

Giá của nhiều job

• Mỗi vòng đọc dữ liệu và tâm cũ từ đĩa rồi ghi tâm mới ra.
• Lặp chục vòng thì đọc ghi thành gánh nặng chính.
• MapReduce mở rộng tốt nhưng không cứu được độ trễ lặp.
• Spark lấp chỗ này bằng giữ dữ liệu trong nhớ qua các vòng.

Ví dụ

• Input: 1 vòng K-means tay với 8 điểm và 2 tâm. Output: tâm mới bằng trung bình từng nhóm.
• Giải thích: reduce chỉ tính trung bình nhóm map đã gán.
• Input: canopy với T1 bằng T2. Output: các tán rời nhau không giao.
• Giải thích: không có vành giữa nên không có điểm thuộc 2 tán.

💻 Bài tập

Ngôn ngữ: Python 3 với NumPy và multiprocessing. Dùng khung MapReduce ngày 50. Nộp vào day-087/.

Bài 1: K-means dạng MapReduce

Cùng dữ liệu và cùng tâm khởi đầu -> kmeans_mr cho kết quả giống kmeans ngày 47

Đo thời gian với $n = 10^6$ điểm 10 chiều, n_workers = 1, 2, 4, 8.

Bài 2: Canopy clustering

def canopy(X, T1: float, T2: float, seed=0) -> list[tuple[np.ndarray, list[int]]]:
    """T1 > T2. Chọn ngẫu nhiên 1 điểm còn trong danh sách làm tâm.
       Điểm cách tâm < T1 vào tán. Điểm cách tâm < T2 bị xóa khỏi danh sách chờ."""

1. Dùng khoảng cách rẻ (Manhattan) cho canopy.
2. In số tán với 3 cặp (T1, T2). Chọn cặp cho số tán gần số cụm thật.
3. Dùng tâm tán làm tâm khởi đầu K-means. So số vòng lặp và inertia với khởi tạo ngẫu nhiên và k-means++.

Bài 3: Chi phí đọc ghi mỗi vòng (nâng cao)

1. Mô phỏng Hadoop: mỗi vòng đọc dữ liệu từ file .npy trên đĩa và ghi tâm ra file. Đo thời gian đọc ghi so với thời gian tính.
2. Bản "Spark": giữ dữ liệu trong bộ nhớ của worker giữa các vòng (dùng Pool với initializer nạp dữ liệu 1 lần).
3. Vẽ biểu đồ thời gian theo số vòng cho 2 bản.

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

• kmeans_mr khớp K-means tuần tự.
• Bảng canopy + K-means so với 2 cách khởi tạo khác có số thật.
• Biểu đồ Bài 3 cho thấy chi phí đọc ghi mỗi vòng.
• Giải thích được vì sao combiner trong mapper giảm dữ liệu shuffle.

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

• 1 vòng K-means MapReduce gồm những bước nào?
• Canopy dùng 2 ngưỡng T1 T2 thế nào?
• Vì sao canopy giúp khởi tạo tốt hơn ngẫu nhiên?
• Ranh giới lớn nhất của MapReduce lặp là gì?

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