Bỏ qua đến nội dung chính
Mục lục

DBSCAN: phân cụm theo mật độ và điểm nhiễu

AIDev Team · duyệt: Nguyễn Việt Chung

Bài 4/7 · Chương 8

Học không giám sát

  • 8 phút
  • Trung cấp
  • Python 3.14
  • Cập nhật

DBSCAN phân cụm dữ liệu theo mật độ: một điểm là điểm lõi nếu trong bán kính eps quanh nó có ít nhất min_samples điểm, kể cả chính nó. Các điểm lõi nằm trong bán kính của nhau nối thành một cụm, điểm không lõi nhưng nằm trong bán kính của một điểm lõi là điểm biên, còn lại là điểm nhiễu với nhãn −1. Thuật toán DBSCAN không cần chọn số cụm trước và tìm được cụm có hình dạng bất kỳ.

Cần biết trước: K-means, bộ dữ liệu có sẵn của scikit-learn và value_counts.

Điểm lõi, điểm biên, điểm nhiễu

Clustering là gì, nói gọn: xếp các dòng vào nhóm để dòng cùng nhóm giống nhau hơn dòng khác nhóm. K-means định nghĩa "giống" bằng khoảng cách tới tâm; DBSCAN định nghĩa bằng vùng lân cận dày đặc:

Nϵ(p)={q:d(p,q)≤ϵ}N_{\epsilon}(p) = \{ q : d(p, q) \le \epsilon \}

Trong đó:

  • p: điểm đang xét; q: một điểm bất kỳ của bảng, kể cả p.

  • d(p, q): khoảng cách Euclid giữa hai điểm.

  • ε (eps): bán kính lân cận.

  • N_ε(p): tập các điểm nằm trong bán kính ε quanh p; p là điểm lõi khi tập này có ít nhất min_samples điểm.

Tám khách, mỗi khách một số: số đơn 12 tháng là 1, 2, 3, 4, 10, 11, 12, 20. Với ε = 1,5 và min_samples = 3:

Điểm

Lân cận trong 1,5

Số điểm

Loại

1

1, 2

2

biên (gần lõi 2)

2

1, 2, 3

3

lõi

3

2, 3, 4

3

lõi

4

3, 4

2

biên (gần lõi 3)

10

10, 11

2

biên (gần lõi 11)

11

10, 11, 12

3

lõi

12

11, 12

2

biên (gần lõi 11)

20

20

1

nhiễu

Lõi 2 và lõi 3 cách nhau 1, nằm trong bán kính của nhau nên chung một cụm cùng các điểm biên 1 và 4. Lõi 11 tạo cụm thứ hai. Khách 20 đơn không gần lõi nào nên là nhiễu. DBSCAN của scikit-learn cho cùng kết quả:

python
import numpy as np
from sklearn.cluster import DBSCAN

x = np.array([[1], [2], [3], [4], [10], [11], [12], [20]])
m = DBSCAN(eps=1.5, min_samples=3).fit(x)
print("labels_:", m.labels_)
print("điểm lõi:", x[m.core_sample_indices_].ravel())

KẾT QUẢ

labels_: [ 0  0  0  0  1  1  1 -1]
điểm lõi: [ 2  3 11]

Đổi min_samples=3 thành min_samples=2 rồi chạy lại: bảy khách thành lõi, nhưng cách chia giữ nguyên và dòng đầu vẫn in [ 0 0 0 0 1 1 1 -1].

Cụm hình dạng bất kỳ

K-means gán mỗi điểm cho tâm gần nhất, nên ranh giới giữa hai cụm luôn là một đường thẳng nằm giữa hai tâm. Hai đám điểm hình trăng khuyết lồng vào nhau từ make_moons cho thấy điều đó:

python
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons

X, _ = make_moons(n_samples=300, noise=0.06, random_state=0)
km = KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(X)
db = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
fig, axs = plt.subplots(1, 2, figsize=(8, 3.2),
                        layout="constrained")
for ax, nhan, ten in [(axs[0], km, "K-means, K = 2"),
                      (axs[1], db, "DBSCAN, eps = 0.2")]:
    ax.scatter(X[:, 0], X[:, 1], c=nhan, s=10, cmap="coolwarm")
    ax.set_title(ten)
plt.show()
Hai biểu đồ phân tán của hai dải hình trăng khuyết lồng nhau: bên trái K-means cắt mỗi dải bằng một đường chéo nên mỗi màu lấy nửa của cả hai dải; bên phải DBSCAN tô mỗi dải trọn một màu.

K-means cắt đôi mỗi trăng khuyết bằng một đường chéo. DBSCAN đi theo các điểm lõi liền nhau dọc theo mỗi dải, nên tìm đúng hai hình trăng khuyết.

DBSCAN trên bảng khách hàng

Bảng chi_tieu_khach_hang.csv (số giả lập của AIDev, 1.500 khách của chuỗi Sóc Nhanh) có sáu cột số. Như với K-means, log các cột lệch phải và scale mọi cột trước, vì eps là một khoảng cách đo chung cho mọi cột:

python
import numpy as np
import pandas as pd
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler

goc = pd.read_csv("chi_tieu_khach_hang.csv").drop(columns="ma_kh")
kh = goc.copy()
kh[kh.columns[:4]] = np.log1p(kh[kh.columns[:4]])
Z = StandardScaler().fit_transform(kh)
nhan = DBSCAN(eps=1.0, min_samples=10).fit_predict(Z)
print(pd.Series(nhan).value_counts().sort_index())
cot = ["so_don_12_thang", "tong_chi_12_thang_nghin"]
print(goc.groupby(nhan)[cot].median())

KẾT QUẢ

-1      35
 0    1205
 1     260
Name: count, dtype: int64
    so_don_12_thang  tong_chi_12_thang_nghin
-1             75.0                 160927.0
 0              5.0                   1362.0
 1             26.0                  16229.0

Ba mươi lăm khách bị đánh dấu nhiễu, với trung vị 75 đơn và hơn 160 triệu đồng: đó là nhóm khách mua sỉ, thưa và nằm xa phần còn lại. Cụm 1 gồm khách mua thường xuyên, chi nhiều; cụm 0 gộp mọi khách còn lại, vì mật độ giữa nhóm săn khuyến mãi, nhóm thỉnh thoảng và nhóm ngủ đông liền nhau không có khoảng trống. Khác với cách tìm ngoại lai bằng IQR xét từng cột một, DBSCAN xét sáu cột cùng lúc.

Đổi eps=1.0 thành eps=0.8 rồi chạy lại: cụm 0 tách thành hai, nhưng dòng nhãn −1 in 104 vì nhiều khách ở rìa không còn đủ hàng xóm. Một eps cho mọi vùng là điểm yếu của DBSCAN khi các nhóm có mật độ khác nhau.

Kiểm tra nhanh

  1. Với tám khách 1, 2, 3, 4, 10, 11, 12, 20 đơn, eps = 1,5 và min_samples = 4, có bao nhiêu điểm lõi?

    • 0
    • 2
    • 3
    • 5
  2. Điểm biên khác điểm nhiễu ở đâu?

    • Điểm biên có đủ min_samples hàng xóm, điểm nhiễu thì không
    • Điểm biên không đủ hàng xóm để làm lõi nhưng nằm trong bán kính eps của một điểm lõi; điểm nhiễu thì không gần lõi nào
    • Điểm biên nằm ở rìa hình vẽ, điểm nhiễu nằm giữa
  3. Những câu nào đúng về DBSCAN trên bảng khách đã log và scale với eps = 1.0, min_samples = 10?

    • Khách mua sỉ rơi vào nhãn −1 vì thưa và nằm xa phần còn lại
    • Số cụm do dữ liệu và hai tham số quyết định, không đặt trước
    • Mọi khách đều thuộc một cụm nào đó
    • Kết quả không đổi khi bỏ bước scale
  4. Vì sao K-means không tách được hai hình trăng khuyết?

    • Vì n_init=10 quá ít
    • Vì mỗi điểm về tâm gần nhất, nên ranh giới giữa hai cụm là một đường thẳng
    • Vì dữ liệu chưa scale
Đúng hết lần đầu +15 XP

Bài tập

Đếm cụm và điểm nhiễu

X là mảng NumPy hai chiều, mỗi dòng một điểm; eps và min_samples là hai tham số của DBSCAN. Viết thân hàm dem_cum_va_nhieu(X, eps, min_samples): chạy DBSCAN(eps=eps, min_samples=min_samples) trên X, rồi đếm số cụm (không tính nhãn −1) và số điểm nhiễu. Hàm không sửa mảng X của nơi gọi.

Trả về: (số cụm, số điểm nhiễu), một tuple gồm hai int.

Ví dụ: với tám khách 1, 2, 3, 4, 10, 11, 12, 20 đơn (mỗi khách một dòng), eps = 1.5, min_samples = 3 cho (2, 1).

python
import numpy as np
from sklearn.cluster import DBSCAN

def dem_cum_va_nhieu(X, eps, min_samples):
    pass  # Viết thân hàm thay cho dòng này

Tóm tắt

  • DBSCAN gọi một điểm là lõi khi bán kính eps quanh nó có ít nhất min_samples điểm, kể cả chính nó.

  • Các lõi nằm trong bán kính của nhau nối thành một cụm; điểm biên vào cụm của lõi gần nó; điểm nhiễu mang nhãn −1.

  • Không cần chọn K, và cụm đi theo hình dạng của vùng dày đặc, kể cả hình trăng khuyết.

  • eps là một khoảng cách, nên phải log và scale các cột trước, như với K-means.

  • Một eps cho mọi vùng: nhóm thưa thành nhiễu, nhóm dày liền nhau gộp thành một cụm.

Câu hỏi thường gặp

Chọn eps và min_samples thế nào?

Một cách hay dùng: đặt min_samples khoảng gấp đôi số cột, rồi với mỗi điểm tính khoảng cách tới hàng xóm thứ min_samples, sắp tăng dần và vẽ. Chỗ đường cong bắt đầu dựng đứng là một eps hợp lý. Sau đó thử vài giá trị quanh đó và đọc trung vị các cột của từng cụm như ở bài này.

Có nên bỏ hết điểm nhiễu của DBSCAN?

Không nên bỏ ngay. Ở bảng khách, điểm nhiễu chính là khách mua sỉ, một nhóm nhỏ nhưng chi nhiều nhất. Hãy đọc điểm nhiễu như một danh sách cần xem riêng: có thể là lỗi nhập liệu, có thể là nhóm khách quan trọng.

DBSCAN có predict cho khách mới không?

Không có predict. Có thể xếp khách mới vào cụm của điểm lõi gần nhất nếu khoảng cách không quá eps, ngược lại coi là nhiễu; hoặc chạy lại DBSCAN trên bảng đã thêm khách mới.

Chủ đề

dbscan

Dữ liệu của bài

Bài này có hữu ích?

Hỏi đáp

Đang tải câu hỏi…

Tham vấn chuyên môn

Nguyễn Việt Chung

Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE

  • Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
  • Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
  • Xây hệ thống AI cho doanh nghiệp tại VietPlatform.
Biên soạn: AIDev Team · Rà soát · Quy trình biên tập