Nguyễn Hoài Phương –CH0403014- Email: phuongnh@dsp.com.vn
THUẬT TOÁN DBSCAN
(Nguồn: A Density-Based Algorithm for Discovering Clusters
in Large Spatial Databases with Noise
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu
Institute for Computer Science, University of Munich
Oettingenstr. 67, D-80538 München, Germany
{ester | kriegel | sander | xwxu}@informatik.uni-muenchen.de)
Thuật toán DBSCAN ((Density Based Spatial Clustering of Applications with Noise)
do Martin Ester và các tác giả khác đề xuất là thuật toán gom tụm dựa trên mật độ, hiệu
quả với cơ sở dữ liệu lớn, có khả năng xử lý nhiễu.
Ý tưởng chính của thuật toán là vùng lân cận mỗi đối tượng trong một cụm có số đối
tượng lớn hơn ngưỡng tối thiểu. Hình dạng vùng lân cận phụ thuộc vào hàm khoảng cách
giữa các đối tượng (nếu sử dụng khoảng cách Manhattan trong không gian 2 chiều thì
vùng lân cận có hình chữ nhật, nếu sử dụng khoảng cách Eucler trong không gian 2 chiều
thì vùng lân cận có hình tròn).
Các đối tượng trong mỗi cụm được phân làm 2 loại: đối tượng bên trong cụm (core
point: đối tượng lõi) và đối tượng nằm trên đường biên của cụm (border point: đối tượng
biên).
Hình 1. Đối tượng biên và đối tuợng lõi
I. Định nghĩa
Định nghĩa 1
Vùng lân cận Eps của đối tượng p, ký hiệu NEps(p) là tập hợp các đối tượng q
sao cho khoảng cách giữa p và q dist(p,q) nhỏ hơn Eps.
NEps(p) = {q∈D | dist(p,q) ≤ Eps}.
Tính chất:
- Nói chung vùng lân cận của đối tượng biên có số đối tượng ít hơn đáng kể
so hơn đối tượng biên
Định nghĩa 2
Đối tượng p tới được trực tiếp theo mật độ (directly density-reachable) thỏa
Eps, MinPts từ đối tượng q nếu p∈NEps(q) và |NEps(q)| ≥ MinPts.
Data Minning –DBSCAN Trang 1/7
Nguyễn Hoài Phương –CH0403014- Email: phuongnh@dsp.com.vn
Tính chất:
- Nếu p, q đều là core point quan hệ directly density-reachable là đối xứng
nghĩa là p tới được trực tiếp theo mật độ từ q và ngược lại.
- Nếu trong p, q có một đối tượng lõi (core point), một đối tượng biên như
hình dưới thì chỉ đối tượng biên có tới được trực tiếp theo mật độ từ đối
tượng lõi mà không có chiều ngược lại (bất đối xứng).
Hình 2. Quan hệ tới được trực tiếp theo mật độ
Định nghĩa 3
Đối tượng p tới được theo mật độ (density-reachable) thỏa Eps, MinPts từ đối
tượng q nếu tồn tại một dãy p1, p2, ..., pn (p1 =q, pn= p) sao cho pi+1 tới được theo mật
độ trực tiếp từ pi.
Tính chất:
- Quan hệ density-reachable là sự mở rộng của directly density-reachable.
- Quan hệ density-reachable có tính bắt cầu
- Nếu p, q đều là đối tượng lõi (core point) thì quan hệ density-reachable là
đối xứng nghĩa là p tới được theo mật độ từ q và ngược lại.
- Nếu p, q đều là đối tượng biên (border point) thì p không tới được theo
mật độ từ q và ngược lại.
- Nếu trong p, q có một đối tượng lõi (core point), một đối tượng biên như
hình dưới thì chỉ đối tượng biên có tới được theo mật độ từ đối tượng lõi
mà không có chiều ngược lại (bất đối xứng).
Hình 3 Quan hệ tới được theo mật độ
Data Minning –DBSCAN Trang 2/7
Nguyễn Hoài Phương –CH0403014- Email: phuongnh@dsp.com.vn
Định nghĩa 4
Đối tượng p kết nối theo mật độ (density-connected) thỏa Eps, MinPts với đối
tượng q tồn tại đối tượng o sao cho cả p và q đều tới được theo mật độ từ o.
Tính chất:
- Đối với các đối tượng tới được theo mật độ với đối tượng khác, quan hệ
density-connected có tính phản xạ
- Quan hệ density-connected có tính đối xứng.
Hình 4 Quan hệ kết nối theo mật độ
Định nghĩa 5
Cho cơ sở dữ liệu D, cụm C thỏa Eps và MinPts là tập con khác rỗng của D
thỏa 2 điều kiện sau:
1) ∀p,q: nếu p ∈C và q liên hệ theo mật độ từ p thỏa Eps và MinPts thì q∈C.
2) ∀p,q∈C: p kết nối theo mật độ với p thỏa Eps và MinPts.
Cụm C thỏa định nghĩa trên sẽ có ít nhất MinPts đối tượng vì lý do sau: C
phải có ít nhất một đối tượng p (C khác rỗng), p phải liên hệ mật độ với bản thân nó
thông qua một đối tượng o (điều kiện 2 của định nghĩa 5). Vì vậy, o là đối tượng lõi
và vùng lân cận Eps của o có ít nhất MinPts đối tượng (do p có liên hệ mật độ từ o).
Định nghĩa 6
Cho các cụm C1 ,. . ., Ck của cơ sở dữ liệu D với các tham số Epsi and
MinPtsi, (i = 1, . . ., k). Tập nhiễu là tập các đối tượng thuộc D nhưng không thuộc
bất kỳ cụm Ci nào.
noise = {p∈D | ∀i: p ∉ Ci}.
II. Bổ đề
Bổ đề 1
Cho p là một đối tượng trong D và |NEps(p)| ≥ MinPts. Tập O = {o | o∈D và o
tới được theo mật độ từ p thỏa Eps and MinPts} là một cụm thỏa Eps and MinPts.
Bổ đề 2
Gọi C là một cụm thỏa Eps và MinPts, p là một đối tượng thuộc C sao cho |
NEps(p)| ≥ MinPts. Khi đó tập C tương đương với tập O = {o | o tới được theo mật độ
từ p thỏa Eps and MinPts}.
Data Minning –DBSCAN Trang 3/7
Nguyễn Hoài Phương –CH0403014- Email: phuongnh@dsp.com.vn
III. Thuật toán
Thuật toán DBSCAN (Density Based Spatial Clustering of Applications with
Noise) là thuật toán gom tụm các đối tượng trong cơ sở dữ liệu không gian thỏa mãn
định nghĩa 5 và 6.
Ứng với thông số Eps, MinPts cho trước, DBSCAN xác định một cụm thông qua
2 bước: 1) chọn đối tượng bất kỳ thỏa mãn điều kiện đối tượng lõi làm đối tuợng hạt
giống; 2) tìm các đối tượng tới đuợc theo mật độ từ đối tượng hạt giống. Trong
trường hợp lý tưởng thì ứng với mỗi cụm, cần phải xác định được thông số Eps,
MinPts ít nhất một đối tượng thuộc cụm; sau đó, tìm tất cả các đối tượng cho từng
cụm. Tuy nhiên, không dễ gì xác định được các thông tin trên nhanh chóng và chính
xác nên DBSCAN sử dụng thông số Eps, MinPts của cụm có mật độ ít dày đặc nhất
làm thông số chung cho tất cả các cụm. Các thông số này được xác định thông qua
thuật toán heuristic (xem phần IV).
Để tìm một cụm, thuật toán DBSCAN bắt đầu từ một đối tượng bất kỳ và sau đó
tìm tất cả các đối tượng tới được theo mật độ thỏa Eps and MinPts từ đối tượng p.
Nếu p là đối tượng lõi, bước trên sinh ra một cụm thỏa Eps and MinPts (xem bổ đề 2).
Nếu p là đối tượng biên thì không tìm được đối tượng tới được theo mật độ từ p,
DBSCAN duyệt đối tượng tiếp theo trong cơ sở dữ liệu. Vì sử dụng chung thông số
Eps và MinPts cho tất cả các cụm nên DBSCAN có thể kết hợp 2 cụm thỏa định
nghĩa 5 thành một cụm nếu hai cụm gần nhau. Khoảng cách giữa 2 tập đối tượng S1
và S2, ký hiệu dist (S1, S2) là giá trị khoảng cách nhỏ nhất của 2 đối tượng p, q thuộc
S1, S2: dist (S1, S2) = min{dist(p,q) | p∈S1, q∈S2}. Hai tập đối tượng trong cùng một
cụm có thể tách nhau nếu khoảng cách giữa chúng lớn hớn Eps (Then, two sets of
points having at least the density of the thinnest cluster will be separated from each
other only if the distance between the two sets is larger than Eps). Vì vậy, thuật toán
DBSCAN có thể cần phải được gọi đệ qui để loại trừ cụm có số đối tượng lớn. Vấn
đề này không khó giải quyết vì DBSCAN cung cấp thuật toán cở bản rất hiệu quả.
•Mã giã của thuật toán DBSCAN
DBSCAN (SetOfPoints, Eps, MinPts)
// SetOfPoints is UNCLASSIFIED (UNCLASSIFIED :chưa phân lớp)
ClusterId := nextId(NOISE);
FOR i FROM 1 TO SetOfPoints.size DO
Point := SetOfPoints.get(i);
IF Point.ClId = UNCLASSIFIED THEN
IF ExpandCluster(SetOfPoints, Point,ClusterId, Eps, MinPts) THEN
ClusterId := nextId(ClusterId)
END IF
END IF
END FOR
END; // DBSCAN
SetOfPoints là toàn bộ các đối tượng trong cơ sở dữ liệu hoặc một cụm được
khám phá ở bước trước. Eps và MinPts là thông số được xác định bằng tay hoặc
thông qua thuật toán heuristics (xem mục IV). Hàm SetOfPoints.get(i) trả về thành
phần thứ i của SetOfPoints, hàm ExpandCluster để tạo một cụm từ đối tượng lõi.
Data Minning –DBSCAN Trang 4/7
Nguyễn Hoài Phương –CH0403014- Email: phuongnh@dsp.com.vn
•Mã giả của hàm ExpandCluster
ExpandCluster(SetOfPoints, Point, ClId, Eps,MinPts) : Boolean;
seeds:=SetOfPoints.regionQuery(Point,Eps);
IF seeds.size<MinPts THEN // không phải là đối tượng bên trong cụm (no
core point)
SetOfPoint.changeClId(Point,NOISE);
RETURN False;
ELSE // all points in seeds are density- reachable from Point
SetOfPoints.changeClIds(seeds,ClId);
seeds.delete(Point);
WHILE seeds <> Empty DO
currentP := seeds.first();
result := SetOfPoints.regionQuery(currentP,Eps);
IF result.size >= MinPts THEN
FOR i FROM 1 TO result.size DO
resultP := result.get(i);
IF resultP.ClId IN {UNCLASSIFIED, NOISE} THEN
IF resultP.ClId = UNCLASSIFIED THEN
seeds.append(resultP);
END IF;
SetOfPoints.changeClId(resultP,ClId);
END IF; // UNCLASSIFIED or NOISE
END FOR;
END IF; // result.size >= MinPts
seeds.delete(currentP);
END WHILE; // seeds <> Empty
RETURN True;
END IF
END; // ExpandCluster
Hàm SetOfPoints.regionQuery(Point,Eps) trả về vùng lân cận Eps của đối tượng
Point trong tập SetOfPoints. Có thể sử dụng cấu trúc cây R* để thực hiện hiệu quả
phép toán này.
Giá trị ClId (clusterId) của đối tượng có trị là NOISE (nhiễu) có thể thay đổi khi
đối tượng có tới được theo mật độ từ đối tượng khác. Các đối tượng này được không
thêm vào danh sách các đối tượng hạt giống (đối tượng đại diện cho một cụm) vì các
đối tượng này không phải là đối tượng lõi (core point).
Nếu 2 cụm C1 và C2 gần nhau, có thể có một số đối tượng p nằm trong cả 2 cụm
C1 và C2. Khi đó, p là đối tượng nằm ở biên của cụm vì nếu không C1 và C2 trùng
nhau do DBSCAN sử dụng cùng thông số Eps và MinPts cho tất cả các cụm. Trong
trường hợp này, đối tượng p thuộc về cụm được phát hiện ra trước. Ngoại trừ các tình
huống hiếm xảy ra này, kết quả của DBSCAN độc lập với thứ tự các đối tượng được
duyệt do bổ đề 2.
Data Minning –DBSCAN Trang 5/7