Phân cụm và ứng dụng

Phạm vi Clustering with Applications, đọc hiểu bài báo, phân tích và thực nghiệm. Đồ án do giảng viên thực hành hướng dẫn và duy trì, với sự đóng góp của Th.S Lê Nhựt Nam, thuộc Bộ môn Khoa học máy tính.

Mục tiêu đồ án¶

Phân cụm, clustering, là một trong những dạng bài toán học không giám sát cơ bản trong lĩnh vực khai thác dữ liệu. Với ứng dụng trải rộng từ phân tích hình ảnh y tế, phân tích mạng xã hội, phân khúc khách hàng, đến phát hiện bất thường trong an ninh mạng, nó giữ một vị trí quan trọng trong nhiều nghiên cứu.

Đồ án này yêu cầu mỗi nhóm chọn một bài báo khoa học từ danh sách do giảng viên cung cấp, sau đó thực hiện các yêu cầu sau:

1. Đọc hiểu và phân tích bài báo bằng chính ngôn ngữ và sự hiểu biết của sinh viên.

2. Tái hiện thực nghiệm: cài đặt lại một phần hoặc toàn bộ các kết quả thực nghiệm được báo cáo trong bài báo, đánh giá và so sánh kết quả.

Lựa chọn bài báo¶

Nguồn bài báo¶

Sinh viên chọn một bài báo từ danh sách chính thức do giảng viên cung cấp. Danh sách bao gồm các bài báo thuộc các hướng nghiên cứu phân cụm nâng cao, ví dụ:

• Phân cụm phổ, Spectral Clustering, và các biến thể

• Phân cụm dựa trên mật độ, Density-based, gồm DBSCAN, OPTICS, HDBSCAN và các mở rộng

• Phân cụm phân cấp, Hierarchical Clustering

• Phân cụm dựa trên đồ thị, Graph-based Clustering

• Phân cụm cho dữ liệu chiều cao, High-dimensional Clustering, Subspace Clustering

• Phân cụm sâu, Deep Clustering, kết hợp mạng nơ ron

• Phân cụm có ràng buộc, Constrained Clustering

• Phân cụm ứng dụng như phân đoạn ảnh, phân tích văn bản, phân tích mạng

Quy tắc lựa chọn¶

Phần A: Đọc hiểu và phân tích bài báo¶

Bối cảnh và động lực nghiên cứu¶

• Vấn đề được giải quyết: bài báo đặt ra bài toán gì? Tại sao bài toán đó quan trọng? Trình bày bằng ví dụ thực tế trực quan với lời diễn đạt của riêng mình.

• Hạn chế của các phương pháp trước: phân tích cụ thể ít nhất 2 phương pháp tiền nhiệm mà bài báo đề cập. Với mỗi phương pháp, chỉ rõ ý tưởng cốt lõi, hạn chế mà bài báo này cố gắng vượt qua, và tại sao hạn chế đó là bất cập thực tế.

• Đóng góp chính: liệt kê và diễn giải các đóng góp, contributions, của bài báo theo cách hiểu của nhóm. Phân biệt đóng góp lý thuyết, đóng góp kỹ thuật và đóng góp thực nghiệm.

Phương pháp đề xuất¶

• Ký hiệu và bài toán hình thức: định nghĩa lại toàn bộ ký hiệu toán học được sử dụng trong bài báo theo cách nhất quán. Phát biểu bài toán tối ưu hóa nếu có một cách đầy đủ.

• Kiến trúc và pipeline tổng thể: vẽ sơ đồ tổng thể của phương pháp bằng TikZ hoặc công cụ khác. Mô tả luồng dữ liệu từ đầu vào đến đầu ra.

• Các thành phần kỹ thuật: với mỗi thành phần hoặc module trong phương pháp, trả lời ba câu hỏi gồm thành phần này làm gì, tại sao cần thành phần này, và nó hoạt động như thế nào về mặt toán học. Trình bày công thức với giải thích từng biến.

• Tính chất lý thuyết: nếu bài báo có bổ đề, định lý, hoặc chứng minh, sinh viên phải trình bày lại và giải thích trực quan ý nghĩa của chúng. Không cần tái chứng minh hoàn toàn, nhưng phải hiểu được.

• Độ phức tạp: phân tích độ phức tạp thời gian và không gian của thuật toán. So sánh với các phương pháp tiền nhiệm.

Phân tích phê bình bài báo¶

• Điểm mạnh: phân tích ít nhất 3 điểm mạnh thực sự của phương pháp, có dẫn chứng từ thực nghiệm hoặc lý thuyết.

• Hạn chế và điểm yếu: phân tích ít nhất 2 hạn chế mà bài báo chưa giải quyết hoặc chưa thảo luận đầy đủ. Sinh viên có thể nêu quan sát của riêng mình dựa trên hiểu biết về lĩnh vực.

• Giả định tiềm ẩn: phương pháp có những giả định nào về dữ liệu đầu vào? Các giả định đó có hợp lý trong thực tế không?

• Hướng phát triển tiếp theo: đề xuất ít nhất 2 hướng nghiên cứu mở rộng tiềm năng mà nhóm nhận thấy sau khi đọc bài báo.

Phần B: Tái hiện thực nghiệm¶

Phạm vi tái hiện¶

Sinh viên được phép chọn một trong hai phạm vi sau, tùy thuộc vào độ phức tạp của bài báo:

• Phạm vi đầy đủ: tái hiện toàn bộ các thực nghiệm chính, main experiments, được báo cáo trong bài báo trên các tập dữ liệu tương tự hoặc giống hệt.

• Phạm vi cốt lõi: tái hiện ít nhất 2 thực nghiệm quan trọng nhất của bài báo, trong đó có thực nghiệm so sánh hiệu năng chính dạng bảng hoặc hình. Phần còn lại được thay bằng phân tích ablation study hoặc thực nghiệm bổ sung tự thiết kế.

Yêu cầu cài đặt¶

Nội dung thực nghiệm bắt buộc¶

• Tái hiện kết quả chính: chạy lại các thực nghiệm trong phạm vi đã chọn. Tổng hợp kết quả vào bảng so sánh giữa số liệu được báo cáo trong bài báo và số liệu từ cài đặt của nhóm. Tính độ lệch tương đối cho từng chỉ số.

• Phân tích sai lệch: nếu kết quả tái hiện khác với bài báo, phân tích và giải thích các nguyên nhân khả dĩ gồm siêu tham số chưa được nêu rõ, phiên bản thư viện, khởi tạo ngẫu nhiên. Đây là phần thể hiện hiểu biết sâu về thuật toán. Nếu bài báo có mã nguồn công khai, so sánh kết quả của nhóm với kết quả từ mã gốc và phân tích điểm khác biệt.

• Ablation study tự thiết kế: thiết kế ít nhất một thực nghiệm ablation không có trong bài báo gốc để kiểm chứng tầm quan trọng của một thành phần kỹ thuật cụ thể. Ví dụ bỏ một module, thay thế bằng phương án đơn giản hơn, hoặc thay đổi một siêu tham số quan trọng.

• Đánh giá trên tập dữ liệu mới: áp dụng phương pháp đã cài đặt lên ít nhất một tập dữ liệu không có trong bài báo gốc. Phân tích kết quả và nhận xét liệu phương pháp có hoạt động tốt ngoài phạm vi tác giả đã thử nghiệm không.

Độ đo đánh giá phân cụm¶

Sinh viên phải báo cáo kết quả bằng ít nhất 3 độ đo sau đây, phù hợp với loại dữ liệu và điều kiện có nhãn hay không:

Yêu cầu báo cáo¶

Ngoài mã nguồn, nhóm phải nộp một báo cáo hoàn chỉnh dạng IEEE conference format, từ 10 đến 15 trang theo mẫu được cung cấp tại https://www.ieee.org/conferences/publishing/templates, không kể tài liệu tham khảo và phụ lục. Báo cáo file Report.pdf đặt ở thư mục root của repository, ngang cấp với README. Cấu trúc báo cáo như sau:

1. Tóm tắt, Abstract, một nửa trang: tóm tắt bài báo, phương pháp cài đặt và kết quả chính.

2. Chương 1 Giới thiệu: nội dung Phần A về bối cảnh và động lực.

3. Chương 2 Phương pháp: nội dung Phần A về phương pháp đề xuất.

4. Chương 3 Phân tích phê bình: nội dung Phần A về phân tích phê bình.

5. Chương 4 Tái hiện thực nghiệm: nội dung Phần B đầy đủ.

6. Chương 5 Kết luận: tổng kết những gì học được, khó khăn gặp phải và hướng phát triển.

7. Tài liệu tham khảo: bao gồm bài báo gốc và ít nhất 5 tài liệu liên quan khác.

Tổ chức đồ án và nộp bài¶

Nhóm nộp duy nhất một link trên Moodle: link trỏ đến public GitHub repository của nhóm. Repository là nơi duy nhất lưu trữ mã nguồn, notebook thực nghiệm, báo cáo và PDF bài báo gốc, đồng thời là nơi gắn các link công khai vào README:

• Molab: nền tảng notebook hosted của marimo, truy cập tại https://molab.marimo.io. Mỗi notebook được xuất bản lên Molab, link xem công khai đặt trong bảng ánh xạ trên README để grader xem code không cần cài marimo.

• Weights & Biases: nền tảng theo dõi thực nghiệm học máy, truy cập tại https://wandb.ai. Toàn bộ thực nghiệm được track trên một project công khai, link công khai đặt trong README để grader kiểm chứng kết quả trong báo cáo.

• README đóng vai trò chỉ mục của repo: liệt kê tên và MSSV thành viên, bảng phân công công việc của từng thành viên, hướng dẫn cài đặt và chạy, bảng ánh xạ từng notebook với link Molab tương ứng và link experiment trên W&B tương ứng, cùng tổng link project W&B của nhóm.

• Bài báo gốc: đính kèm PDF bài báo trong thư mục paper/.

• Dữ liệu lớn: host trên Hugging Face hoặc Kaggle, link đính kèm trong README. Mã chuẩn bị dữ liệu nằm trong marimo notebook, viết trực tiếp hoặc import từ file phụ trợ như src/data.py. Khi chuẩn bị thực nghiệm, ưu tiên dùng các bộ dữ liệu đã có sẵn công khai trên hai nền tảng này thay vì tự host dữ liệu mới, giúp nhóm giảm nhẹ phần công việc chuẩn bị.

• Đồ án này nằm trong phạm vi phần thi vấn đáp cuối kỳ, trong đó nhóm trình bày và trả lời câu hỏi về các đồ án đã thực hiện trong học kỳ.

Cấu trúc thư mục tham khảo:

Group_ID/
├── README.md                     # chi muc: thanh vien, phan cong, huong dan chay,
│                                 # bang anh xa notebook - Molab - W&B
├── Report.pdf                    # bao cao dat ngang cap voi README, quy cach o phan
│                                 # Yeu cau bao cao
├── requirements.txt
├── paper/
│   └── paper.pdf                 # ban PDF bai bao goc
├── notebooks/
│   ├── 01_main_experiments.py    # marimo notebook
│   ├── 02_ablation_study.py      # marimo notebook
│   └── 03_new_dataset.py         # marimo notebook
├── src/
│   ├── model.py                  # cai dat chinh cua thuat toan
│   ├── utils.py
│   └── metrics.py                # cac do do danh gia
└── data/                         # du lieu, ban lon host tren Hugging Face hoac Kaggle

Tiêu chí chấm điểm¶

Tổng điểm bằng phần A cộng phần B cộng phần chất lượng kết quả thực nghiệm và trình bày, tối đa 100%.

Rubric chi tiết Phần A:

• Xuất sắc: diễn đạt bằng ngôn ngữ riêng, hiểu đúng mọi công thức, phê bình sâu sắc và có căn cứ.

• Tốt: hiểu đúng phương pháp nhưng phê bình còn sơ sài hoặc bề mặt.

• Đạt: mô tả đúng ý chính nhưng thiếu chiều sâu hoặc có sai sót nhỏ về ký hiệu.

• Chưa đạt: sao chép gần như nguyên văn bài báo, hoặc hiểu sai phương pháp.

Rubric chi tiết Phần B:

• Xuất sắc: kết quả tái hiện sát với bài báo, phân tích sai lệch thuyết phục, ablation study có insight rõ ràng, tập dữ liệu mới được phân tích sâu.

• Tốt: tái hiện được kết quả chính, phân tích đầy đủ nhưng ablation còn đơn giản.

• Đạt: cài đặt chạy được, kết quả có sai lệch nhưng có giải thích hợp lý.

• Chưa đạt: mã nguồn không chạy, hoặc kết quả lệch nghiêm trọng mà không giải thích được.