Series: Machine Learning Fundamentals – Bài 29
Ở bài trước, chúng ta đã tìm hiểu K-Means Clustering – thuật toán gom nhóm dựa trên khoảng cách đến tâm cụm. Mặc dù K-Means rất nhanh và đơn giản, nó lại gặp hạn chế lớn khi dữ liệu có hình dạng bất kỳ (hình vành nhẫn, hình xoắn ốc) hoặc chứa nhiều nhiễu (Outliers).
Để khắc phục hoàn toàn nhược điểm đó, thuật toán DBSCAN ra đời như một giải pháp phân nhóm dựa trên mật độ cực kỳ hiệu quả.
DBSCAN là gì?
DBSCAN là viết tắt của:
Density-Based Spatial Clustering of Applications with Noise.
Đây là một thuật toán học không giám sát (Unsupervised Learning) dựa trên triết lý: Một cụm dữ liệu là một vùng không gian có mật độ điểm cao, được phân tách với các cụm khác bởi những vùng có mật độ điểm thấp.
K-Means (Chia theo tâm) DBSCAN (Chia theo mật độ)
o o o x x x o o o o o
o o o x x x o o
(Chỉ gom nhóm hình cầu) (Gom được hình vành nhẫn, uốn lượn)
Tài liệu chính thức mô tả DBSCAN có khả năng tự động phát hiện số lượng cụm dựa trên mật độ thực tế mà người dùng không cần khai báo trước số cụm $K$. Xem thêm tại Scikit-Learn DBSCAN Documentation.
Các tham số quan trọng trong DBSCAN
DBSCAN hoạt động dựa trên 2 tham số cốt lõi:
-
eps($\epsilon$ – Epsilon): Bán kính vùng lân cận xung quanh một điểm dữ liệu. -
minPts(min_samples): Số lượng điểm tối thiểu cần có trong bán kínheps(bao gồm chính điểm đó) để tạo thành một vùng có mật độ cao.
Phân loại 3 dạng điểm trong DBSCAN
Dựa trên hai tham số eps và minPts, DBSCAN chia mọi điểm dữ liệu thành 3 loại:
(O) Border Point * Noise (Biệt lập)
|
v
(●) Core Point (Chứa >= minPts trong bán kính eps)
-
Core Point (Điểm lõi): Điểm có ít nhất
minPtsđiểm khác nằm trong bán kínheps. -
Border Point (Điểm biên): Điểm không phải Core Point, nhưng nằm trong bán kính
epscủa một Core Point. -
Noise / Outlier (Điểm nhiễu): Điểm không phải Core Point và cũng không nằm trong bán kính
epscủa bất kỳ Core Point nào.
Cách DBSCAN hoạt động
Quy trình phân nhóm của DBSCAN diễn ra theo các bước:
-
Chọn một điểm ngẫu nhiên chưa được truy vấn trong Dataset.
-
Kiểm tra vùng lân cận bán kính
epscủa điểm đó:-
Nếu có đủ $\ge$
minPts, điểm đó trở thành Core Point và một cụm mới được khởi tạo. -
Nếu không đủ
minPts, điểm đó tạm thời đánh dấu là Noise.
-
-
Mở rộng cụm: Thêm tất cả các điểm nằm trong vùng lân cận
epscủa Core Point vào cụm. Nếu trong nhóm mới có các Core Point khác, tiếp tục hợp nhập vùng lân cận của chúng (Density-reachable). -
Lặp lại quá trình cho đến khi tất cả các điểm đều được phân loại vào một cụm hoặc gán là Noise.
So sánh K-Means và DBSCAN
| Tiêu chí | K-Means Clustering | DBSCAN |
| Số lượng cụm $K$ | Bắt buộc khai báo trước | Tự động phát hiện |
| Hình dạng cụm | Chỉ gom dạng hình cầu (Spherical) | Phân nhóm hình dạng bất kỳ |
| Xử lý Outliers | Nhạy cảm, Outlier kéo lệch tâm | Tự động phát hiện và loại bỏ Noise |
| Độ phức tạp | $O(n)$ – Rất nhanh | $O(n \log n)$ – Chậm hơn trên dữ liệu lớn |
| Mật độ không đều | Hoạt động bình thường | Kém hiệu quả nếu các cụm có mật độ khác xa nhau |
Dữ liệu có cần Feature Scaling không?
CỰC KỲ BẮT BUỘC.
Vì DBSCAN sử dụng bán kính eps dựa trên khoảng cách Euclidean để xác định vùng lân cận, nếu các Feature có vạch quy mô khác nhau, bán kính eps sẽ bị biến dạng. Việc chuẩn hóa bằng StandardScaler trước khi huấn luyện DBSCAN là yêu cầu bắt buộc.
Ưu điểm và Nhược điểm của DBSCAN
Ưu điểm
-
Không cần chọn trước số lượng cụm $K$.
-
Phát hiện cụm có hình dạng phức tạp và không đều.
-
Tự động lọc bỏ nhiễu (Noise) và Outliers hiệu quả.
Nhược điểm
-
Khó chọn cặp tham số
epsvàminPtstối ưu nếu không hiểu rõ dữ liệu. -
Hoạt động kém nếu các cụm trong Dataset có mật độ chênh lệch quá lớn.
-
Bị ảnh hưởng bởi “Lời nguyền số chiều” (Curse of Dimensionality) khi số Features quá nhiều.
Khi nào nên dùng DBSCAN?
-
Dữ liệu có nhiều Outliers hoặc nhiễu.
-
Dữ liệu hình dạng phi tuyến tính (dạng vành khăn, đường uốn lượn, bản đồ không gian địa lý).
-
Phân tích không gian địa lý (GIS Data) để tìm các điểm nóng ô nhiễm, phân vùng mật độ dân cư.
Tóm tắt
-
DBSCAN gom nhóm dựa trên mật độ và bán kính khoảng cách.
-
Tự động xác định số cụm và tự động tách biệt điểm Noise.
-
Hai tham số cốt lõi là
epsvàminPts. -
Luôn luôn Feature Scaling dữ liệu trước khi chạy DBSCAN.
Tài liệu tham khảo
-
Scikit-Learn Documentation: DBSCAN in Scikit-Learn
-
Ester et al. (1996): A density-based algorithm for discovering clusters in large spatial databases with noise – Bài báo gốc về DBSCAN.
Khóa học tại MCNA Technology School
Nếu bạn muốn thực hành Machine Learning, Python và xây dựng các mô hình trên dữ liệu thực tế, có thể tham khảo:
-
🤖 Combo 5 khóa AI & Power BI: Xem khóa học AI & Power BI
-
🐍 Combo Python: Xem Combo Python
Tác giả: Bùi Đình Tuyển – Data Analyst tại MCNA Technology School
📞 Hotline: 0939.866.825 (Mr. Minh Khang)
🌐 Website: MCNA Technology School
📍 Hà Nội: 30 Trung Liệt, Đống Đa | Liền kề 44B TT2 Văn Quán, Hà Đông
📍 TP.HCM: 50B Phan Tây Hồ, Cầu Kiệu
