DBSCAN (Density-Based Spatial Clustering of Applications with Noise) la mot thuat toan phan cum kinh dien, dac biet manh me o cho: no khong can ban phai bao truoc so luong cum, va no tu dong phat hien cac diem loi (noise/outliers). Dac diet cho du lieu co hinh dang bat ky.
DBSCAN La Gi? Giai Thich De Hieu Cho Nguoi Moi
DBSCAN la mot thuat toan phan cum dua tren mat do (density-based). Thay vi phai chon truoc so luong cum nhu K-Means, DBSCAN tu dong tim ra cac cum dua tren muc do tap trung cua du lieu. No xac dinh cac vung co mat do cao la cum, va cac diem le tach ra goi la noise.
De hieu don gian: ban nghi tuong minh dang dung tren mot bai dat trong, nhin xuong va thay cac cum nguoi dung gan nhau. DBSCAN se tu dong nhan dien moi cum nguoi la mot nhom, con nhung nguoi dung mot minh o xa thi bi danh dau la outlier. Khong can ai bao truoc “bai nay co 5 nhom”.
DBSCAN Hoat Dong Nhu The Nao?
DBSCAN su dung hai tham so chinh de xac dinh cum:
1. Epsilon (eps) — ban kinh tim kiem. Day la khoang cach toi da giua hai diem de duoc xet la “lang gieng” cua nhau. Moi diem trong du lieu deu co mot vung tron ban kinh eps xung quanh no.
2. MinPts — so luong diem toi thieu can co trong vung eps de tao thanh cum. Neu mot diem co it nhat MinPts diem lang gieng (bao gom chinh no) thi no duoc goi la core point (diem khoi).
Tu hai khai niem nay, DBSCAN phan loai moi diem thanh ba loai:
Core point — diem co it nhat MinPts lang gieng trong ban kinh eps. Day la “trai tim” cua cum.
Border point — diem nam trong ban kinh eps cua mot core point nhung ban than no khong du MinPts de tro thanh core. No nam tren bien gioi cua cum.
Noise — diem khong phai core point, cung khong phai border point cua bat ky core point nao. Day la outlier, duoc DBSCAN tu dong loai bo.
Qua Trinh Chay DBSCAN Tang Dan
Thuat toan bat dau tu mot diem bat ky va kiem tra xem no co phai core point khong. Neu co, no tao mot cum moi va bat dau mo rong cum do bang cach tim tat ca core point lang gieng, roi tim tiep core point lang gieng cua cac core point do — nhu hieu ung domino.
Qua trinh mo rong nay tiep dien cho den khi khong con them duoc core point nao vao cum. Luc do, DBSCAN chuyen sang mot diem chua duoc xet va bat dau lai. Cac diem con sot lai cuoi cung chinh la noise.
Minh nghi dieu hay nhat cua cach tiep can nay la no khong can chay nhieu vong lap nhu K-Means. Chi can mot buoc duyet qua du lieu la du. Thuc te, phuc tap cua DBSCAN la O(n log n) khi dung cau truc du lieu index nhu R*-tree hoac KD-tree.
DBSCAN vs K-Means: Khac Biet Trong Suot
Nhieu nguoi hoi minh rang: da co K-Means roi thi dung DBSCAN lam gi? Cau tra loi la chung phuc vu hai muc dich hoan toan khac nhau.
K-Means yeu cau ban phai bao truoc so luong cum (k). No gia dinh rang tat ca cum deu co hinh cau (spherical) va kich thuoc tuong doi tuong dong. Neu du lieu cua ban co cac cum hinh dang bat ky — nhu hinh luoi, hinh vong tron, hay hinh quang — K-Means se chay sai hoan toan.
DBSCAN khong can ban bao so luong cum. No tu dong tim ra so luong cum phu hop voi du lieu. Va vi no dua tren mat do, DBSCAN co the phat hien cac cum co hinh dang bat ky. Them nua, DBSCAN tu dong danh dau outlier, trong khi K-Means phai ep moi diem vao mot cum nao do — ke ca khi diem do rat xa tat ca cac cum.
Tuy nhien, DBSCAN cung co yeu diem. No rat nhay cam voi tham so eps. Thay doi eps mot chut co the lam so luong cum thay doi dang ke. Va khi du lieu co cac cum voi mat do khac nhau (cum rat tap trung ben canh cum rai rac), DBSCAN kho xu ly vi mot gia tri eps khong the phu hop cho tat ca.
Cai Dat Tham So Eps Va MinPts Nhu The Nao?
Day la cau hoi pho bien nhat khi bat dau dung DBSCAN. Minh thuong dung hai quy tac sau:
MinPts — quy tac chung la dat bang so chieu du lieu nhan 2. Vi du, du lieu 2 dac trung thi MinPts = 4, du lieu 3 dac trung thi MinPts = 6. Voi dataset lon, co the tang len MinPts = 2*n hoac cao hon de giam nhieu.
Eps — minh thuong dung phuong phap k-distance graph. Tinh khoang cach tu moi diem den diem lang gieng thu k gan nhat (k = MinPts – 1), sap xep tang dan, va ve bieu do. Diem “khuuyt” (elbow) tren bieu do chinh la gia tri eps tot nhat.
Mot cach khac la thu nghiem voi nhieu gia tri eps khac nhau va danh gia bang silhouette score hoac Davies-Bouldin index. Tuy lau hon nhung ket qua dang tin cay hon.
Ung Dung Thuc Te Cua DBSCAN
DBSCAN duoc ung dung rat rong rai. Minh nhan xet mot vai case pho bien:
Phat hien vi tri mo cong ty — tu du lieu GPS cua khach hang, DBSCAN co the xac dinh cac khu vuc tap trung nguoi dung, giup mo cua hang tai vi tri co mat do khach cao nhat.
Phan tich du lieu vi vat the — trong ban do va GIS, DBSCAN phan cum cac diem vi tri thanh cum bieu dien cac khu vuc quan trong nhu cum nha hoac khu cong nghiep.
Phat hien anomaly — trong bao mat va gian lan, cac diem bi DBSCAN danh dau la noise thuong la cac giao dich bat thuong hoac hanh vi ngay mac.
Phan khuc khach hang — dua tren hanh vi mua hang, DBSCAN nhom khach hang thanh tung cum tu nhien, khong can gia dinh truoc co bao nhieu nhom.
DBSCAN Trong Python
Thuc hanh DBSCAN trong Python rat don gian nho thu vien scikit-learn:
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
X, _ = make_moons(n_samples=300, noise=0.05)
db = DBSCAN(eps=0.3, min_samples=5)
labels = db.fit_predict(X)
# labels = -1 nghia la noise
print(f"So cum: {len(set(labels)) - (1 if -1 in labels else 0)}")
print(f"So noise: {list(labels).count(-1)}")Chi voi vai dong code, ban da co the phan cum du lieu co hinh dang bat ky va tu dong phat hien outlier. Vi du make_moons o tren tao du lieu hinh hai vong trang khong — mot bai toan ma K-Means bao chay sai, nhung DBSCAN giai quyet de dang.
Ket Luan
DBSCAN la mot cong cu manh me trong bo goi phan cum, dac biet khi ban khong biet truoc so luong cum va du lieu co nhieu outlier. No bo sung hoan hao cho K-Means va Hierarchical Clustering, tao thanh bo ba phan cum ma moi data scientist can biet.
Dieu quan trong nhat khi dung DBSCAN la chon eps va MinPts phu hop. Hay bat dau voi k-distance graph de tim eps, va dat MinPts = 2 * so_chieu_du_lieu. Sau do fine-tune bang silhouette score. Khi da quen, ban se thay DBSCAN la mot thuat toan rat tu nhien va de hieu — no don gian la tim cac vung data tap trung, va bo qua nhung gi thua tha.
