Phân tích cụm là một bài toán quan trọng trong phân tích dữ liệu. Các nhà khoa học dữ liệu dùng phân cụm để xác định máy chủ lỗi, nhóm các gen có mẫu biểu hiện tương tự, hoặc nhiều ứng dụng khác.
Tóm lược, phân cụm là nhiệm vụ nhóm các đối tượng lại với nhau sao cho các đối tượng trong cùng một cụm giống nhau hơn so với các đối tượng ở cụm khác. Độ tương đồng phản ánh mức độ mạnh yếu của mối quan hệ giữa hai đối tượng dữ liệu. Phân cụm chủ yếu được dùng cho khai phá dữ liệu khám phá. Phân cụm có rất nhiều ứng dụng trong các lĩnh vực như học máy, nhận dạng mẫu, phân tích ảnh, truy hồi thông tin, tin-sinh học, nén dữ liệu và đồ họa máy tính.
Có nhiều họ kỹ thuật phân cụm, và bạn có thể quen với kỹ thuật phổ biến nhất: K-Means (thuộc họ phân cụm dựa trên trọng tâm). Nhắc nhanh, K-Means xác định k trọng tâm trong dữ liệu và phân cụm các điểm bằng cách gán chúng cho trọng tâm gần nhất.
Mặc dù K-Means dễ hiểu và dễ triển khai trên thực tế, thuật toán không xử lý ngoại lệ, nên mọi điểm đều được gán vào một cụm ngay cả khi chúng không thuộc cụm nào. Trong miền phát hiện bất thường, điều này gây vấn đề vì các điểm bất thường sẽ bị gán cùng cụm với các điểm dữ liệu “bình thường”. Các điểm bất thường kéo trọng tâm cụm về phía chúng, khiến việc phân loại chúng là bất thường trở nên khó khăn hơn.
Hướng dẫn này sẽ đề cập đến một loại kỹ thuật phân cụm khác gọi là phân cụm dựa trên mật độ, cụ thể là DBSCAN (một kỹ thuật phân cụm dựa trên mật độ). So với phân cụm dựa trên trọng tâm như K-Means, phân cụm dựa trên mật độ hoạt động bằng cách nhận diện các cụm điểm “dày đặc”, từ đó học được các cụm có hình dạng bất kỳ và nhận diện ngoại lệ trong dữ liệu.
Nhược điểm của kỹ thuật phân cụm dựa trên trọng tâm
Trước khi bàn về nhược điểm của phân cụm dựa trên trọng tâm, hãy giới thiệu ngắn gọn về nó. Trọng tâm là một điểm dữ liệu (tưởng tượng hoặc thực) ở giữa một cụm. Trong phân cụm dựa trên trọng tâm, các cụm được biểu diễn bằng một véc-tơ trung tâm hay trọng tâm. Trọng tâm này không nhất thiết phải là một phần tử của tập dữ liệu. Phân cụm dựa trên trọng tâm là một thuật toán lặp, trong đó khái niệm về độ tương đồng được suy ra từ mức độ gần của một điểm dữ liệu đến trọng tâm của cụm.
Đôi khi một tập dữ liệu có thể chứa các giá trị cực đoan nằm ngoài phạm vi mong đợi và khác biệt với dữ liệu còn lại. Đây được gọi là ngoại lệ. Chính xác hơn, ngoại lệ là một quan sát nằm ở khoảng cách bất thường so với các giá trị khác trong một mẫu ngẫu nhiên từ quần thể.
Nền tảng chính của các kỹ thuật phân cụm dựa trên trọng tâm được dẫn dắt bởi phép đo khoảng cách giữa các điểm dữ liệu và các trọng tâm. Do đó, các kỹ thuật phân cụm dựa trên trọng tâm thường không phát hiện tốt các điểm dữ liệu lệch nhiều so với phân phối bình thường của dữ liệu. Ngay cả trước khi xây dựng các mô hình dự đoán, ngoại lệ có thể dẫn đến biểu diễn sai và kéo theo diễn giải sai về dữ liệu thu thập được. Điều này về bản chất là không mong muốn khi xây dựng các mô hình phân tích và dự đoán hiệu quả từ dữ liệu.
Bạn có thể coi hai cột cao hơn (so với các cột còn lại) sau đây là ngoại lệ trong bộ dữ liệu đó:
Giới thiệu chung về kỹ thuật phân cụm dựa trên mật độ
Trước khi bàn về phân cụm dựa trên mật độ, trước hết bạn cần đề cập đến một chủ đề: lân cận ɛ.
Ý tưởng chung đằng sau lân cận ɛ là với một điểm dữ liệu, bạn muốn có thể lập luận về các điểm dữ liệu trong không gian xung quanh nó. Một cách hình thức, với ɛ > 0 (giá trị thực) và một điểm p, lân cận ɛ của p được định nghĩa là tập các điểm cách p tối đa ɛ.
Nếu nhớ lại hình học, hình mà mọi điểm cách đều tâm là hình tròn. Trong không gian 2D, lân cận ɛ của một điểm p là tập các điểm nằm trong hình tròn bán kính ɛ, tâm p. Trong không gian 3D, lân cận ɛ là hình cầu bán kính ɛ, tâm p, và trong không gian nhiều chiều hơn, lân cận ɛ chính là N-sphere bán kính ɛ, tâm p.
Hãy xét một ví dụ để làm rõ hơn ý tưởng này. Trong hình dưới, 100 điểm dữ liệu rải trong khoảng [1,3]X[2,4]. Hãy chọn điểm (3,2) làm điểm p.
Đầu tiên, xét lân cận của p với bán kính 0,5 (ɛ = 0,5), tập các điểm cách p không quá 0,5.
Hình bầu dục xanh mờ biểu diễn lân cận của chúng ta, và có 31 điểm dữ liệu trong lân cận này. Vì có 100 điểm được rải và 31 điểm ở trong lân cận, điều này có nghĩa là xấp xỉ dưới một phần ba số điểm nằm trong lân cận của p với bán kính 0,5.
Bây giờ, hãy đổi bán kính thành 0,15 (ɛ = 0,15) và xét lân cận nhỏ hơn thu được.
Lân cận giờ đã thu nhỏ lại, nên chỉ còn 3 điểm dữ liệu nằm trong đó. Bằng cách giảm ɛ từ 0,5 xuống 0,15 (giảm 70%), số điểm trong lân cận của chúng ta giảm từ 31 xuống 3 (giảm 90%).
Giờ bạn đã hiểu khá rõ về “lân cận”, tôi sẽ giới thiệu khái niệm quan trọng tiếp theo: khái niệm “mật độ” cho một lân cận (suy cho cùng bạn đang tiến tới học “phân cụm dựa trên mật độ”).
Trong lớp khoa học phổ thông, trẻ em được dạy mật độ = khối lượng/thể tích. Hãy dùng ý tưởng khối lượng chia cho thể tích này để định nghĩa mật độ tại một điểm p. Nếu xét một điểm p và lân cận bán kính ɛ của nó, bạn có thể định nghĩa khối lượng của lân cận là số điểm dữ liệu (hoặc tỷ phần điểm dữ liệu) nằm trong lân cận, và thể tích của lân cận là thể tích của hình tạo thành bởi lân cận. Ở trường hợp 2D, lân cận là hình tròn, nên thể tích lân cận chính là diện tích hình tròn đó. Ở trường hợp 3D và cao hơn, lân cận là hình cầu hay n-sphere, nên bạn có thể tính thể tích của hình này.
Ví dụ, hãy xét lại lân cận của p = (3,2) với bán kính 0,5.
Khối lượng là số điểm dữ liệu trong lân cận, nên khối lượng = 31. Thể tích là diện tích hình tròn, nên thể tích = π0,52 = π/4. Do đó, xấp xỉ mật độ cục bộ tại * p = (3,2) được tính là mật độ = khối lượng/thể tích = 31/(π/4) = 124/π ~= 39,5.
Giá trị này tự thân thì vô nghĩa, nhưng nếu bạn tính xấp xỉ mật độ cục bộ cho mọi điểm trong tập dữ liệu, bạn có thể phân cụm các điểm bằng cách nói rằng các điểm ở gần nhau (nằm trong cùng lân cận) và có xấp xỉ mật độ cục bộ tương tự thì thuộc cùng cụm. Nếu bạn giảm giá trị ɛ, bạn có thể tạo ra các lân cận nhỏ hơn (thể tích ít hơn) và cũng chứa ít điểm dữ liệu hơn. Lý tưởng là bạn muốn nhận diện các lân cận có mật độ cao, nơi phần lớn điểm dữ liệu nằm trong các lân cận này, nhưng thể tích mỗi lân cận tương đối nhỏ.
Mặc dù đây không phải chính xác điều mà DBSCAN hay thuật toán Cây Tập Mức (một kỹ thuật phân cụm khác thuộc họ phân cụm dựa trên mật độ) thực hiện, nó tạo nên trực giác chung cho phân cụm dựa trên mật độ.
Tóm lại, bạn đã đề cập đến lân cận ɛ và cách chúng cho phép lập luận về không gian xung quanh một điểm cụ thể. Sau đó bạn học khái niệm mật độ tại một điểm cho một lân cận cụ thể. Ở phần tiếp theo, bạn sẽ tìm hiểu thuật toán DBSCAN, nơi quả cầu ɛ là công cụ nền tảng để định nghĩa các cụm.
Bên trong hoạt động của DBSCAN
DBSCAN là viết tắt của Density-Based Spatial Clustering of Applications with Noise (Phân cụm không gian dựa trên mật độ cho các ứng dụng có nhiễu) và không nghi ngờ gì là thuật toán phân cụm dựa trên mật độ nổi tiếng nhất. Nó được giới thiệu lần đầu vào năm 1996 bởi Ester và cộng sự. Do tầm quan trọng cả về lý thuyết lẫn ứng dụng, thuật toán này là một trong ba thuật toán nhận Giải thưởng Test of Time tại SIGKDD 2014.
Không giống K-Means, DBSCAN không yêu cầu số cụm làm tham số. Thay vào đó, nó suy ra số cụm dựa trên dữ liệu và có thể phát hiện các cụm có hình dạng bất kỳ (trong khi K-Means thường phát hiện các cụm dạng cầu). Như bạn đã thấy, lân cận ɛ là nền tảng của DBSCAN để xấp xỉ mật độ cục bộ, vì vậy thuật toán có hai tham số:
ɛ: Bán kính của các lân cận quanh một điểm dữ liệu p.
minPts: Số điểm dữ liệu tối thiểu bạn muốn trong một lân cận để định nghĩa một cụm.
Sử dụng hai tham số này, DBSCAN phân loại các điểm dữ liệu thành ba nhóm:
Điểm lõi (Core Points): Một điểm dữ liệu p là điểm lõi nếu Nbhd(p,ɛ) [lân cận ɛ của p] chứa ít nhất minPts; |Nbhd(p,ɛ)| >= minPts.
Điểm biên (Border Points): Một điểm dữ liệu *q là điểm biên nếu Nbhd(q, ɛ) chứa ít hơn minPts điểm, nhưng q có thể đạt tới từ một điểm lõi p nào đó.
Ngoại lệ (Outlier): Một điểm dữ liệu o là ngoại lệ nếu nó không phải điểm lõi cũng không phải điểm biên. Về bản chất, đây là lớp “khác”.
Những định nghĩa này có thể có vẻ trừu tượng, nên hãy đi sâu hơn từng khái niệm.
Điểm lõi:
Điểm lõi là nền tảng để xây dựng các cụm của chúng ta, dựa trên xấp xỉ mật độ mà tôi đã thảo luận ở phần trước. Bạn dùng cùng một ɛ để tính lân cận cho mỗi điểm, nên thể tích của mọi lân cận là như nhau. Tuy nhiên, số điểm khác trong mỗi lân cận thì khác nhau. Hãy nhớ tôi đã nói bạn có thể xem số điểm dữ liệu trong lân cận là khối lượng của nó. Thể tích mỗi lân cận là hằng số, còn khối lượng thì thay đổi, nên bằng cách đặt một ngưỡng cho lượng khối lượng tối thiểu cần có để trở thành điểm lõi, bạn thực chất đang đặt một ngưỡng mật độ tối thiểu. Do đó, điểm lõi là những điểm dữ liệu đáp ứng yêu cầu mật độ tối thiểu. Các cụm của chúng ta được xây dựng xoay quanh các điểm lõi (vì vậy mới gọi là “lõi”), nên bằng cách điều chỉnh tham số minPts, bạn có thể tinh chỉnh mức độ “dày đặc” tối thiểu của lõi cụm.
Điểm biên:
Điểm biên là các điểm trong cụm nhưng không phải điểm lõi. Trong định nghĩa ở trên về điểm biên, tôi đã dùng thuật ngữ “có thể đạt được theo mật độ” (density-reachable). Tôi chưa định nghĩa thuật ngữ này, nhưng khái niệm thì đơn giản. Để giải thích, hãy quay lại ví dụ lân cận với epsilon = 0,15. Xét điểm r (chấm đen) nằm ngoài lân cận của điểm p.
Tất cả các điểm bên trong lân cận của p được gọi là trực tiếp đạt tới từ p. Giờ, hãy khám phá lân cận của điểm q, một điểm trực tiếp đạt tới từ p. Vòng tròn vàng biểu diễn lân cận của q.
Giờ trong khi điểm mục tiêu r không nằm trong lân cận của p, nó lại nằm trong lân cận của q. Đây là ý tưởng đằng sau “có thể đạt được theo mật độ”: Nếu bạn có thể tới điểm r bằng cách “nhảy” từ lân cận này sang lân cận khác, bắt đầu từ điểm p, thì r là có thể đạt được theo mật độ từ p.
Theo phép so sánh, bạn có thể coi các điểm “có thể đạt được theo mật độ” là “bạn của bạn”. Nếu các điểm trực tiếp đạt tới từ một điểm lõi p là “bạn bè” của nó, thì các điểm có thể đạt được theo mật độ, tức các điểm trong lân cận của “bạn bè” của p, là “bạn của bạn bè”. Một điều có thể chưa rõ là tính “có thể đạt được theo mật độ” không giới hạn ở chỉ hai lần nhảy lân cận kề nhau. Miễn là bạn có thể tới điểm đó bằng các “cú nhảy lân cận”, bắt đầu từ một điểm lõi p, thì điểm đó có thể đạt được theo mật độ từ p, vì vậy “bạn của bạn của bạn … của bạn” cũng được tính.
Điều quan trọng cần nhớ là ý tưởng “có thể đạt được theo mật độ” phụ thuộc vào giá trị ɛ. Chọn ɛ lớn hơn thì nhiều điểm trở nên có thể đạt được theo mật độ hơn, còn chọn ɛ nhỏ hơn thì ít điểm có thể đạt được hơn.
Ngoại lệ:
Cuối cùng là lớp “khác”. Ngoại lệ là các điểm không phải điểm lõi và cũng không đủ gần một cụm để có thể đạt được theo mật độ từ một điểm lõi. Ngoại lệ không được gán vào bất kỳ cụm nào và, tùy ngữ cảnh, có thể được xem là các điểm bất thường.
Nghiên cứu tình huống DBSCAN trong Python:
DBSCAN đã được triển khai rất tốt trong thư viện học máy Python Scikit-Learn phổ biến, và vì bản triển khai này có khả năng mở rộng và được kiểm thử tốt, bạn sẽ sử dụng nó để xem DBSCAN hoạt động ra sao trong thực tế.
Các bước của thuật toán DBSCAN là:
Chọn ngẫu nhiên một điểm chưa được gán vào cụm nào hoặc chưa được đánh dấu là ngoại lệ. Tính lân cận của nó để xác định liệu đó có phải điểm lõi không. Nếu có, bắt đầu một cụm quanh điểm này. Nếu không, gán điểm đó là ngoại lệ.
Khi tìm được một điểm lõi và do đó một cụm, mở rộng cụm bằng cách thêm tất cả các điểm trực tiếp đạt tới vào cụm. Thực hiện các “cú nhảy lân cận” để tìm tất cả các điểm có thể đạt được theo mật độ và thêm chúng vào cụm. Nếu một ngoại lệ được thêm vào, đổi trạng thái của điểm đó từ ngoại lệ thành điểm biên.
Lặp lại hai bước này cho đến khi mọi điểm đều được gán vào một cụm hoặc được đánh dấu là ngoại lệ.
# Let's import all your dependencies firstfrom sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
Được hỗ trợ bởi
Bộ dữ liệu gồm 440 khách hàng và có 8 thuộc tính cho mỗi khách hàng. Bạn sẽ dùng thư viện Pandas để nhập tệp .csv và chuyển nó thành một đối tượng DataFrame.
Khi nhập tệp .csv của bạn vào, hãy đảm bảo cung cấp đúng đường dẫn của tệp đó.
# Import .csv file and convert it to a DataFrame object
df = pd.read_csv("C:/Users/Sayak/data/customers.csv");print(df.head())Được hỗ trợ bởi
Channel Region Fresh Milk Grocery Frozen Detergents_Paper \
02312669965675612142674123705798109568176232932236353880876842405351631313265119642216404507423226155410719839151777
Delicatessen
0133811776278443178845185Được hỗ trợ bởi
Trước khi tiếp tục áp dụng DBSCAN, điều rất quan trọng là bạn hiểu dữ liệu để biết bộ dữ liệu chứa kiểu dữ liệu nào, dữ liệu tuân theo phân phối nào, và đặc trưng nào là số hay không.
<class'pandas.core.frame.DataFrame'>RangeIndex:440 entries,0 to 439
Data columns(total 8 columns):
Channel 440 non-null int64
Region 440 non-null int64
Fresh 440 non-null int64
Milk 440 non-null int64
Grocery 440 non-null int64
Frozen 440 non-null int64
Detergents_Paper 440 non-null int64
Delicatessen 440 non-null int64
dtypes:int64(8)
memory usage:27.6KB
None
Được hỗ trợ bởi
Như bạn thấy từ kết quả trên, không có giá trị thiếu trong bộ dữ liệu và tất cả dữ liệu đều thuộc kiểu số nguyên. Điều này giảm gánh nặng tiền xử lý thêm cho dữ liệu. Hãy đào sâu thêm một chút.
Channel Region Fresh Milk Grocery \
count 440.000000440.000000440.000000440.000000440.000000
mean 1.3227272.54318212000.2977275796.2659097951.277273
std 0.4680520.77427212647.3288657380.3771759503.162829
min 1.0000001.0000003.00000055.0000003.00000025%1.0000002.0000003127.7500001533.0000002153.00000050%1.0000003.0000008504.0000003627.0000004755.50000075%2.0000003.00000016933.7500007190.25000010655.750000
max 2.0000003.000000112151.00000073498.00000092780.000000
Frozen Detergents_Paper Delicatessen
count 440.000000440.000000440.000000
mean 3071.9318182881.4931821524.870455
std 4854.6733334767.8544482820.105937
min 25.0000003.0000003.00000025%742.250000256.750000408.25000050%1526.000000816.500000965.50000075%3554.2500003922.0000001820.250000
max 60869.00000040827.00000047943.000000Được hỗ trợ bởi
Từ kết quả trên, bạn có thể suy ra tất cả các thước đo thống kê cần thiết như độ lệch chuẩn, trung bình, giá trị cực đại của từng đặc trưng trong bộ dữ liệu. Bạn có thể thấy phần lớn dữ liệu trong bộ này là liên tục ngoại trừ hai đặc trưng: Channel và Region. Để đơn giản hóa tính toán, bạn sẽ loại hai đặc trưng này:
df.drop(["Channel","Region"], axis =1, inplace =True)Được hỗ trợ bởi
# Let's get a view of the data after the dropprint(df.head())Được hỗ trợ bởi
Fresh Milk Grocery Frozen Detergents_Paper Delicatessen
012669965675612142674133817057981095681762329317762635388087684240535167844313265119642216404507178842261554107198391517775185Được hỗ trợ bởi
Để bạn có thể trực quan hóa dữ liệu, ở đây chúng ta sẽ dùng hai đặc trưng:
Groceries: Chi tiêu hằng năm của khách hàng (theo một đơn vị tiền tệ nào đó) cho sản phẩm tạp hóa.
Milk: Chi tiêu hằng năm của khách hàng (theo một đơn vị tiền tệ nào đó) cho sản phẩm sữa.
# Let's plot the data now
x = df['Grocery']
y = df['Milk']
plt.scatter(x,y)
plt.xlabel("Groceries")
plt.ylabel("Milk")
plt.show()Được hỗ trợ bởi
Hãy điểm qua nhanh các hàm bạn dùng để vẽ: plt.scatter(): Hàm này tạo biểu đồ phân tán dựa trên dữ liệu (là các tham số bạn truyền vào [x và y]). plt.xlabel(): Giúp bạn đặt nhãn dọc theo trục X. (Groceries trong trường hợp này) plt.ylabel(): Giúp bạn đặt nhãn dọc theo trục Y. (Milk trong trường hợp này) plt.show(): Sau khi biểu đồ được tạo, hàm này giúp hiển thị nó ra kết quả.
Bạn thật sự nên khám phá thế giới tuyệt vời của Matplotlib cho mọi mục đích trực quan hóa. Tài liệu của nó cực kỳ tuyệt vời.
Bạn có thể dễ dàng nhận ra các điểm dữ liệu nằm khá xa phần còn lại. Đúng chứ? Vâng, đó là các ngoại lệ.
Với DBSCAN, chúng ta muốn nhận diện cụm chính của khách hàng, nhưng cũng muốn gắn cờ những khách hàng có thói quen mua sắm hằng năm bất thường hơn là ngoại lệ.
Vì các giá trị dữ liệu ở mức hàng nghìn, bạn sẽ chuẩn hóa từng thuộc tính bằng cách đưa về trung bình 0 và phương sai đơn vị. Điều này cơ bản giúp giữ nguyên các mối quan hệ giữa các đặc trưng, sao cho một thay đổi nhỏ ở một đặc trưng sẽ phản ánh ở đặc trưng khác.
Phù hợp với trực giác, thuật toán DBSCAN đã xác định được một cụm khách hàng quanh mức chi tiêu trung bình cho tạp hóa và sữa. Ngoài ra, nó có thể gắn cờ những khách hàng có hành vi mua sắm hằng năm lệch quá nhiều so với những khách hàng khác.
Bởi vì các ngoại lệ tương ứng với khách hàng có hành vi mua sắm cực đoan hơn, nhà phân phối bán buôn có thể nhắm mục tiêu riêng các khách hàng này bằng các ưu đãi độc quyền để khuyến khích mua hàng lớn hơn.
Ứng dụng thực tế của DBSCAN
Giả sử chúng ta có một trang thương mại điện tử và muốn cải thiện doanh số bằng cách gợi ý sản phẩm phù hợp cho khách hàng. Chúng ta không biết chính xác khách hàng tìm gì nhưng dựa trên một bộ dữ liệu có thể dự đoán và gợi ý sản phẩm phù hợp cho một khách hàng cụ thể. Ta có thể áp dụng DBSCAN cho bộ dữ liệu (dựa trên cơ sở dữ liệu thương mại điện tử) và tìm các cụm dựa trên sản phẩm người dùng đã mua. Dựa vào các cụm này, ta có thể tìm điểm tương đồng giữa khách hàng; ví dụ, nếu khách hàng A đã mua một cây bút, một quyển sách và một chiếc kéo, trong khi khách hàng B đã mua một quyển sách và một chiếc kéo, thì bạn có thể gợi ý một cây bút cho khách hàng B.
Trước khi các phương pháp nâng cao dựa trên học sâu bùng nổ, các nhà nghiên cứu đã dùng DBSCAN để tách biệt các gen từ một bộ dữ liệu gen có khả năng tham gia trung gian gây ung thư.
Các nhà khoa học đã dùng DBSCAN để phát hiện các điểm dừng trong dữ liệu quỹ đạo tạo ra từ thiết bị GPS di động. Các điểm dừng đại diện cho phần có ý nghĩa và quan trọng nhất của một quỹ đạo.
Kết luận
Trong bài viết này, bạn đã biết về các nhược điểm chính của phân cụm dựa trên trọng tâm và làm quen với một họ kỹ thuật phân cụm khác, tức phân cụm dựa trên mật độ. Bạn cũng đã thấy cách chúng khắc phục các hạn chế của phân cụm dựa trên trọng tâm.
Bạn đã học cách DBSCAN hoạt động và cũng thực hiện một nghiên cứu tình huống về nó. Bên cạnh đó, bạn có cái nhìn tổng quan hợp lý về các bài toán thực tế nơi DBSCAN đã được ứng dụng để giải quyết. Để đọc thêm, tôi thực sự khuyên bạn nên tìm hiểu các phương pháp phân cụm dựa trên mật độ khác như phân cụm Cây Tập Mức và cách nó khác DBSCAN.
Martin Ester, Hans-Peter Kriegel, Jörg Sander và Xiaowei Xu. 1996. Thuật toán dựa trên mật độ để khám phá các cụm trong các cơ sở dữ liệu không gian lớn có nhiễu. Trong Kỷ yếu Hội nghị Quốc tế lần thứ hai về Khai phá Tri thức và Khai thác Dữ liệu (KDD'96), do Evangelos Simoudis, Jiawei Han và Usama Fayyad (Biên tập). AAAI Press 226-231.
%22%3E%3Cpath%20d%3D%22m-369%200h408v79h-408z%22%20fill%3D%22%237933ff%22%2F%3E%3Cpath%20d%3D%22m-148%200h306v45h-306z%22%20fill%3D%22%23974dff%22%2F%3E%3C%2Fg%3E%3C%2Fsvg%3E)
%22%2F%3E%3C%2FclipPath%3E%3Cg%20clip-path%3D%22url(%23a)%22%3E%3Cpath%20d%3D%22m76%200h484v36h-484z%22%20fill%3D%22%23974dff%22%2F%3E%3Cpath%20d%3D%22m0%200h384v24h-384z%22%20fill%3D%22%2306bdfc%22%20transform%3D%22matrix(1%200%200%20-1%200%2060)%22%2F%3E%3C%2Fg%3E%3C%2Fsvg%3E)
%22%3E%0A%20%20%20%20%20%20%20%20%3Crect%20fill%3D%22%23EFEBE4%22%20height%3D%22180%22%20width%3D%22336%22%20%2F%3E%0A%20%20%20%20%20%20%20%20%3Crect%0A%20%20%20%20%20%20%20%20%20%20fill%3D%22%23DD3400%22%0A%20%20%20%20%20%20%20%20%20%20height%3D%22106.6%22%0A%20%20%20%20%20%20%20%20%20%20transform%3D%22rotate(-30%20-208.588%20220.18)%22%0A%20%20%20%20%20%20%20%20%20%20width%3D%22456.125%22%0A%20%20%20%20%20%20%20%20%20%20x%3D%22-208.588%22%0A%20%20%20%20%20%20%20%20%20%20y%3D%22220.18%22%0A%20%20%20%20%20%20%20%20%2F%3E%0A%20%20%20%20%20%20%20%20%3Crect%0A%20%20%20%20%20%20%20%20%20%20fill%3D%22%23FFEC3C%22%0A%20%20%20%20%20%20%20%20%20%20height%3D%2235.875%22%0A%20%20%20%20%20%20%20%20%20%20transform%3D%22rotate(-30%20-208.588%20220.18)%22%0A%20%20%20%20%20%20%20%20%20%20width%3D%22347.576%22%0A%20%20%20%20%20%20%20%20%20%20x%3D%22-208.588%22%0A%20%20%20%20%20%20%20%20%20%20y%3D%22220.18%22%0A%20%20%20%20%20%20%20%20%2F%3E%0A%20%20%20%20%20%20%20%20%3Crect%0A%20%20%20%20%20%20%20%20%20%20fill%3D%22%23FF931E%22%0A%20%20%20%20%20%20%20%20%20%20height%3D%2235.875%22%0A%20%20%20%20%20%20%20%20%20%20transform%3D%22rotate(-30%20-226.525%20189.111)%22%0A%20%20%20%20%20%20%20%20%20%20width%3D%22347.576%22%0A%20%20%20%20%20%20%20%20%20%20x%3D%22-226.525%22%0A%20%20%20%20%20%20%20%20%20%20y%3D%22189.111%22%0A%20%20%20%20%20%20%20%20%2F%3E%0A%20%20%20%20%20%20%20%20%3Crect%0A%20%20%20%20%20%20%20%20%20%20fill%3D%22%23DD3400%22%0A%20%20%20%20%20%20%20%20%20%20height%3D%22106.6%22%0A%20%20%20%20%20%20%20%20%20%20transform%3D%22rotate(-30%2085.5879%20256.055)%22%0A%20%20%20%20%20%20%20%20%20%20width%3D%22456.125%22%0A%20%20%20%20%20%20%20%20%20%20x%3D%2285.5879%22%0A%20%20%20%20%20%20%20%20%20%20y%3D%22256.055%22%0A%20%20%20%20%20%20%20%20%2F%3E%0A%20%20%20%20%20%20%20%20%3Crect%0A%20%20%20%20%20%20%20%20%20%20fill%3D%22%23FFEC3C%22%0A%20%20%20%20%20%20%20%20%20%20height%3D%2235.875%22%0A%20%20%20%20%20%20%20%20%20%20transform%3D%22rotate(-30%2085.5879%20256.055)%22%0A%20%20%20%20%20%20%20%20%20%20width%3D%22184.5%22%0A%20%20%20%20%20%20%20%20%20%20x%3D%2285.5879%22%0A%20%20%20%20%20%20%20%20%20%20y%3D%22256.055%22%0A%20%20%20%20%20%20%20%20%2F%3E%0A%20%20%20%20%20%20%20%20%3Crect%0A%20%20%20%20%20%20%20%20%20%20fill%3D%22%23FF931E%22%0A%20%20%20%20%20%20%20%20%20%20height%3D%2235.875%22%0A%20%20%20%20%20%20%20%20%20%20transform%3D%22rotate(-30%20227.432%20132.736)%22%0A%20%20%20%20%20%20%20%20%20%20width%3D%22271.625%22%0A%20%20%20%20%20%20%20%20%20%20x%3D%22227.432%22%0A%20%20%20%20%20%20%20%20%20%20y%3D%22132.736%22%0A%20%20%20%20%20%20%20%20%2F%3E%0A%20%20%20%20%20%20%3C%2Fg%3E%0A%20%20%20%20%20%20%3Cdefs%3E%0A%20%20%20%20%20%20%20%20%3CclipPath%20id%3D%22clip%22%3E%0A%20%20%20%20%20%20%20%20%20%20%3Crect%20fill%3D%22white%22%20height%3D%22180%22%20width%3D%22336%22%20%2F%3E%0A%20%20%20%20%20%20%20%20%3C%2FclipPath%3E%0A%20%20%20%20%20%20%3C%2Fdefs%3E%0A%20%20%20%20%3C%2Fsvg%3E)
Matt Crabtree · 10 min
Tóm lược, phân cụm là nhiệm vụ nhóm các đối tượng lại với nhau sao cho các đối tượng trong cùng một cụm giống nhau hơn so với các đối tượng ở cụm khác. Độ tương đồng phản ánh mức độ mạnh yếu của mối quan hệ giữa hai đối tượng dữ liệu. Phân cụm chủ yếu được dùng cho khai phá dữ liệu khám phá. Phân cụm có rất nhiều ứng dụng trong các lĩnh vực như học máy, nhận dạng mẫu, phân tích ảnh, truy hồi thông tin, tin-sinh học, nén dữ liệu và đồ họa máy tính.
Có nhiều họ kỹ thuật phân cụm, và bạn có thể quen với kỹ thuật phổ biến nhất: K-Means (thuộc họ phân cụm dựa trên trọng tâm). Nhắc nhanh, K-Means xác định k trọng tâm trong dữ liệu và phân cụm các điểm bằng cách gán chúng cho trọng tâm gần nhất.
Mặc dù K-Means dễ hiểu và dễ triển khai trên thực tế, thuật toán không xử lý ngoại lệ, nên mọi điểm đều được gán vào một cụm ngay cả khi chúng không thuộc cụm nào. Trong miền phát hiện bất thường, điều này gây vấn đề vì các điểm bất thường sẽ bị gán cùng cụm với các điểm dữ liệu “bình thường”. Các điểm bất thường kéo trọng tâm cụm về phía chúng, khiến việc phân loại chúng là bất thường trở nên khó khăn hơn.
Hướng dẫn này sẽ đề cập đến một loại kỹ thuật phân cụm khác gọi là phân cụm dựa trên mật độ, cụ thể là DBSCAN (một kỹ thuật phân cụm dựa trên mật độ). So với phân cụm dựa trên trọng tâm như K-Means, phân cụm dựa trên mật độ hoạt động bằng cách nhận diện các cụm điểm “dày đặc”, từ đó học được các cụm có hình dạng bất kỳ và nhận diện ngoại lệ trong dữ liệu.
Nhược điểm của kỹ thuật phân cụm dựa trên trọng tâm
Trước khi bàn về nhược điểm của phân cụm dựa trên trọng tâm, hãy giới thiệu ngắn gọn về nó. Trọng tâm là một điểm dữ liệu (tưởng tượng hoặc thực) ở giữa một cụm. Trong phân cụm dựa trên trọng tâm, các cụm được biểu diễn bằng một véc-tơ trung tâm hay trọng tâm. Trọng tâm này không nhất thiết phải là một phần tử của tập dữ liệu. Phân cụm dựa trên trọng tâm là một thuật toán lặp, trong đó khái niệm về độ tương đồng được suy ra từ mức độ gần của một điểm dữ liệu đến trọng tâm của cụm.
Đôi khi một tập dữ liệu có thể chứa các giá trị cực đoan nằm ngoài phạm vi mong đợi và khác biệt với dữ liệu còn lại. Đây được gọi là ngoại lệ. Chính xác hơn, ngoại lệ là một quan sát nằm ở khoảng cách bất thường so với các giá trị khác trong một mẫu ngẫu nhiên từ quần thể.
Nền tảng chính của các kỹ thuật phân cụm dựa trên trọng tâm được dẫn dắt bởi phép đo khoảng cách giữa các điểm dữ liệu và các trọng tâm. Do đó, các kỹ thuật phân cụm dựa trên trọng tâm thường không phát hiện tốt các điểm dữ liệu lệch nhiều so với phân phối bình thường của dữ liệu. Ngay cả trước khi xây dựng các mô hình dự đoán, ngoại lệ có thể dẫn đến biểu diễn sai và kéo theo diễn giải sai về dữ liệu thu thập được. Điều này về bản chất là không mong muốn khi xây dựng các mô hình phân tích và dự đoán hiệu quả từ dữ liệu.
Bạn có thể coi hai cột cao hơn (so với các cột còn lại) sau đây là ngoại lệ trong bộ dữ liệu đó:
Giới thiệu chung về kỹ thuật phân cụm dựa trên mật độ
Trước khi bàn về phân cụm dựa trên mật độ, trước hết bạn cần đề cập đến một chủ đề: lân cận ɛ.
Ý tưởng chung đằng sau lân cận ɛ là với một điểm dữ liệu, bạn muốn có thể lập luận về các điểm dữ liệu trong không gian xung quanh nó. Một cách hình thức, với ɛ > 0 (giá trị thực) và một điểm p, lân cận ɛ của p được định nghĩa là tập các điểm cách p tối đa ɛ.
Nếu nhớ lại hình học, hình mà mọi điểm cách đều tâm là hình tròn. Trong không gian 2D, lân cận ɛ của một điểm p là tập các điểm nằm trong hình tròn bán kính ɛ, tâm p. Trong không gian 3D, lân cận ɛ là hình cầu bán kính ɛ, tâm p, và trong không gian nhiều chiều hơn, lân cận ɛ chính là N-sphere bán kính ɛ, tâm p.
Hãy xét một ví dụ để làm rõ hơn ý tưởng này. Trong hình dưới, 100 điểm dữ liệu rải trong khoảng [1,3]X[2,4]. Hãy chọn điểm (3,2) làm điểm p.
Đầu tiên, xét lân cận của p với bán kính 0,5 (ɛ = 0,5), tập các điểm cách p không quá 0,5.
Hình bầu dục xanh mờ biểu diễn lân cận của chúng ta, và có 31 điểm dữ liệu trong lân cận này. Vì có 100 điểm được rải và 31 điểm ở trong lân cận, điều này có nghĩa là xấp xỉ dưới một phần ba số điểm nằm trong lân cận của p với bán kính 0,5.
Bây giờ, hãy đổi bán kính thành 0,15 (ɛ = 0,15) và xét lân cận nhỏ hơn thu được.
Lân cận giờ đã thu nhỏ lại, nên chỉ còn 3 điểm dữ liệu nằm trong đó. Bằng cách giảm ɛ từ 0,5 xuống 0,15 (giảm 70%), số điểm trong lân cận của chúng ta giảm từ 31 xuống 3 (giảm 90%).
Giờ bạn đã hiểu khá rõ về “lân cận”, tôi sẽ giới thiệu khái niệm quan trọng tiếp theo: khái niệm “mật độ” cho một lân cận (suy cho cùng bạn đang tiến tới học “phân cụm dựa trên mật độ”).
Trong lớp khoa học phổ thông, trẻ em được dạy mật độ = khối lượng/thể tích. Hãy dùng ý tưởng khối lượng chia cho thể tích này để định nghĩa mật độ tại một điểm p. Nếu xét một điểm p và lân cận bán kính ɛ của nó, bạn có thể định nghĩa khối lượng của lân cận là số điểm dữ liệu (hoặc tỷ phần điểm dữ liệu) nằm trong lân cận, và thể tích của lân cận là thể tích của hình tạo thành bởi lân cận. Ở trường hợp 2D, lân cận là hình tròn, nên thể tích lân cận chính là diện tích hình tròn đó. Ở trường hợp 3D và cao hơn, lân cận là hình cầu hay n-sphere, nên bạn có thể tính thể tích của hình này.
Ví dụ, hãy xét lại lân cận của p = (3,2) với bán kính 0,5.
Khối lượng là số điểm dữ liệu trong lân cận, nên khối lượng = 31. Thể tích là diện tích hình tròn, nên thể tích = π0,52 = π/4. Do đó, xấp xỉ mật độ cục bộ tại * p = (3,2) được tính là mật độ = khối lượng/thể tích = 31/(π/4) = 124/π ~= 39,5.
Giá trị này tự thân thì vô nghĩa, nhưng nếu bạn tính xấp xỉ mật độ cục bộ cho mọi điểm trong tập dữ liệu, bạn có thể phân cụm các điểm bằng cách nói rằng các điểm ở gần nhau (nằm trong cùng lân cận) và có xấp xỉ mật độ cục bộ tương tự thì thuộc cùng cụm. Nếu bạn giảm giá trị ɛ, bạn có thể tạo ra các lân cận nhỏ hơn (thể tích ít hơn) và cũng chứa ít điểm dữ liệu hơn. Lý tưởng là bạn muốn nhận diện các lân cận có mật độ cao, nơi phần lớn điểm dữ liệu nằm trong các lân cận này, nhưng thể tích mỗi lân cận tương đối nhỏ.
Mặc dù đây không phải chính xác điều mà DBSCAN hay thuật toán Cây Tập Mức (một kỹ thuật phân cụm khác thuộc họ phân cụm dựa trên mật độ) thực hiện, nó tạo nên trực giác chung cho phân cụm dựa trên mật độ.
Tóm lại, bạn đã đề cập đến lân cận ɛ và cách chúng cho phép lập luận về không gian xung quanh một điểm cụ thể. Sau đó bạn học khái niệm mật độ tại một điểm cho một lân cận cụ thể. Ở phần tiếp theo, bạn sẽ tìm hiểu thuật toán DBSCAN, nơi quả cầu ɛ là công cụ nền tảng để định nghĩa các cụm.
Bên trong hoạt động của DBSCAN
DBSCAN là viết tắt của Density-Based Spatial Clustering of Applications with Noise (Phân cụm không gian dựa trên mật độ cho các ứng dụng có nhiễu) và không nghi ngờ gì là thuật toán phân cụm dựa trên mật độ nổi tiếng nhất. Nó được giới thiệu lần đầu vào năm 1996 bởi Ester và cộng sự. Do tầm quan trọng cả về lý thuyết lẫn ứng dụng, thuật toán này là một trong ba thuật toán nhận Giải thưởng Test of Time tại SIGKDD 2014.
Không giống K-Means, DBSCAN không yêu cầu số cụm làm tham số. Thay vào đó, nó suy ra số cụm dựa trên dữ liệu và có thể phát hiện các cụm có hình dạng bất kỳ (trong khi K-Means thường phát hiện các cụm dạng cầu). Như bạn đã thấy, lân cận ɛ là nền tảng của DBSCAN để xấp xỉ mật độ cục bộ, vì vậy thuật toán có hai tham số:
Sử dụng hai tham số này, DBSCAN phân loại các điểm dữ liệu thành ba nhóm:
Những định nghĩa này có thể có vẻ trừu tượng, nên hãy đi sâu hơn từng khái niệm.
Điểm lõi:
Điểm lõi là nền tảng để xây dựng các cụm của chúng ta, dựa trên xấp xỉ mật độ mà tôi đã thảo luận ở phần trước. Bạn dùng cùng một ɛ để tính lân cận cho mỗi điểm, nên thể tích của mọi lân cận là như nhau. Tuy nhiên, số điểm khác trong mỗi lân cận thì khác nhau. Hãy nhớ tôi đã nói bạn có thể xem số điểm dữ liệu trong lân cận là khối lượng của nó. Thể tích mỗi lân cận là hằng số, còn khối lượng thì thay đổi, nên bằng cách đặt một ngưỡng cho lượng khối lượng tối thiểu cần có để trở thành điểm lõi, bạn thực chất đang đặt một ngưỡng mật độ tối thiểu. Do đó, điểm lõi là những điểm dữ liệu đáp ứng yêu cầu mật độ tối thiểu. Các cụm của chúng ta được xây dựng xoay quanh các điểm lõi (vì vậy mới gọi là “lõi”), nên bằng cách điều chỉnh tham số minPts, bạn có thể tinh chỉnh mức độ “dày đặc” tối thiểu của lõi cụm.
Điểm biên:
Điểm biên là các điểm trong cụm nhưng không phải điểm lõi. Trong định nghĩa ở trên về điểm biên, tôi đã dùng thuật ngữ “có thể đạt được theo mật độ” (density-reachable). Tôi chưa định nghĩa thuật ngữ này, nhưng khái niệm thì đơn giản. Để giải thích, hãy quay lại ví dụ lân cận với epsilon = 0,15. Xét điểm r (chấm đen) nằm ngoài lân cận của điểm p.
Tất cả các điểm bên trong lân cận của p được gọi là trực tiếp đạt tới từ p. Giờ, hãy khám phá lân cận của điểm q, một điểm trực tiếp đạt tới từ p. Vòng tròn vàng biểu diễn lân cận của q.
Giờ trong khi điểm mục tiêu r không nằm trong lân cận của p, nó lại nằm trong lân cận của q. Đây là ý tưởng đằng sau “có thể đạt được theo mật độ”: Nếu bạn có thể tới điểm r bằng cách “nhảy” từ lân cận này sang lân cận khác, bắt đầu từ điểm p, thì r là có thể đạt được theo mật độ từ p.
Theo phép so sánh, bạn có thể coi các điểm “có thể đạt được theo mật độ” là “bạn của bạn”. Nếu các điểm trực tiếp đạt tới từ một điểm lõi p là “bạn bè” của nó, thì các điểm có thể đạt được theo mật độ, tức các điểm trong lân cận của “bạn bè” của p, là “bạn của bạn bè”. Một điều có thể chưa rõ là tính “có thể đạt được theo mật độ” không giới hạn ở chỉ hai lần nhảy lân cận kề nhau. Miễn là bạn có thể tới điểm đó bằng các “cú nhảy lân cận”, bắt đầu từ một điểm lõi p, thì điểm đó có thể đạt được theo mật độ từ p, vì vậy “bạn của bạn của bạn … của bạn” cũng được tính.
Điều quan trọng cần nhớ là ý tưởng “có thể đạt được theo mật độ” phụ thuộc vào giá trị ɛ. Chọn ɛ lớn hơn thì nhiều điểm trở nên có thể đạt được theo mật độ hơn, còn chọn ɛ nhỏ hơn thì ít điểm có thể đạt được hơn.
Ngoại lệ:
Cuối cùng là lớp “khác”. Ngoại lệ là các điểm không phải điểm lõi và cũng không đủ gần một cụm để có thể đạt được theo mật độ từ một điểm lõi. Ngoại lệ không được gán vào bất kỳ cụm nào và, tùy ngữ cảnh, có thể được xem là các điểm bất thường.
Nghiên cứu tình huống DBSCAN trong Python:
DBSCAN đã được triển khai rất tốt trong thư viện học máy Python Scikit-Learn phổ biến, và vì bản triển khai này có khả năng mở rộng và được kiểm thử tốt, bạn sẽ sử dụng nó để xem DBSCAN hoạt động ra sao trong thực tế.
Các bước của thuật toán DBSCAN là:
Cho mục đích nghiên cứu tình huống này, bạn sẽ dùng một bộ dữ liệu gồm dữ liệu khách hàng hằng năm của một nhà phân phối bán buôn.
Vậy hãy bắt đầu.
Bộ dữ liệu gồm 440 khách hàng và có 8 thuộc tính cho mỗi khách hàng. Bạn sẽ dùng thư viện Pandas để nhập tệp .csv và chuyển nó thành một đối tượng DataFrame.
Khi nhập tệp .csv của bạn vào, hãy đảm bảo cung cấp đúng đường dẫn của tệp đó.
Trước khi tiếp tục áp dụng DBSCAN, điều rất quan trọng là bạn hiểu dữ liệu để biết bộ dữ liệu chứa kiểu dữ liệu nào, dữ liệu tuân theo phân phối nào, và đặc trưng nào là số hay không.
Theo mô tả trong kho lưu trữ học máy UCI chính thức của bộ dữ liệu này, thông tin về các đặc trưng như sau:
Giờ bạn đã biết về các đặc trưng của bộ dữ liệu, hãy hiển thị một số thống kê của dữ liệu.
Như bạn thấy từ kết quả trên, không có giá trị thiếu trong bộ dữ liệu và tất cả dữ liệu đều thuộc kiểu số nguyên. Điều này giảm gánh nặng tiền xử lý thêm cho dữ liệu. Hãy đào sâu thêm một chút.
Từ kết quả trên, bạn có thể suy ra tất cả các thước đo thống kê cần thiết như độ lệch chuẩn, trung bình, giá trị cực đại của từng đặc trưng trong bộ dữ liệu. Bạn có thể thấy phần lớn dữ liệu trong bộ này là liên tục ngoại trừ hai đặc trưng: Channel và Region. Để đơn giản hóa tính toán, bạn sẽ loại hai đặc trưng này:
Để bạn có thể trực quan hóa dữ liệu, ở đây chúng ta sẽ dùng hai đặc trưng:
Hãy điểm qua nhanh các hàm bạn dùng để vẽ: plt.scatter(): Hàm này tạo biểu đồ phân tán dựa trên dữ liệu (là các tham số bạn truyền vào [x và y]). plt.xlabel(): Giúp bạn đặt nhãn dọc theo trục X. (Groceries trong trường hợp này) plt.ylabel(): Giúp bạn đặt nhãn dọc theo trục Y. (Milk trong trường hợp này) plt.show(): Sau khi biểu đồ được tạo, hàm này giúp hiển thị nó ra kết quả.
Bạn thật sự nên khám phá thế giới tuyệt vời của Matplotlib cho mọi mục đích trực quan hóa. Tài liệu của nó cực kỳ tuyệt vời.
Bạn có thể dễ dàng nhận ra các điểm dữ liệu nằm khá xa phần còn lại. Đúng chứ? Vâng, đó là các ngoại lệ.
Với DBSCAN, chúng ta muốn nhận diện cụm chính của khách hàng, nhưng cũng muốn gắn cờ những khách hàng có thói quen mua sắm hằng năm bất thường hơn là ngoại lệ.
Vì các giá trị dữ liệu ở mức hàng nghìn, bạn sẽ chuẩn hóa từng thuộc tính bằng cách đưa về trung bình 0 và phương sai đơn vị. Điều này cơ bản giúp giữ nguyên các mối quan hệ giữa các đặc trưng, sao cho một thay đổi nhỏ ở một đặc trưng sẽ phản ánh ở đặc trưng khác.
Bạn sẽ tạo một đối tượng DBSCAN yêu cầu tối thiểu 15 điểm dữ liệu trong một lân cận bán kính 0,5 để được coi là điểm lõi.
Tiếp theo, chúng ta có thể trích xuất nhãn cụm và các ngoại lệ để vẽ kết quả.
Phù hợp với trực giác, thuật toán DBSCAN đã xác định được một cụm khách hàng quanh mức chi tiêu trung bình cho tạp hóa và sữa. Ngoài ra, nó có thể gắn cờ những khách hàng có hành vi mua sắm hằng năm lệch quá nhiều so với những khách hàng khác.
Bởi vì các ngoại lệ tương ứng với khách hàng có hành vi mua sắm cực đoan hơn, nhà phân phối bán buôn có thể nhắm mục tiêu riêng các khách hàng này bằng các ưu đãi độc quyền để khuyến khích mua hàng lớn hơn.
Ứng dụng thực tế của DBSCAN
Giả sử chúng ta có một trang thương mại điện tử và muốn cải thiện doanh số bằng cách gợi ý sản phẩm phù hợp cho khách hàng. Chúng ta không biết chính xác khách hàng tìm gì nhưng dựa trên một bộ dữ liệu có thể dự đoán và gợi ý sản phẩm phù hợp cho một khách hàng cụ thể. Ta có thể áp dụng DBSCAN cho bộ dữ liệu (dựa trên cơ sở dữ liệu thương mại điện tử) và tìm các cụm dựa trên sản phẩm người dùng đã mua. Dựa vào các cụm này, ta có thể tìm điểm tương đồng giữa khách hàng; ví dụ, nếu khách hàng A đã mua một cây bút, một quyển sách và một chiếc kéo, trong khi khách hàng B đã mua một quyển sách và một chiếc kéo, thì bạn có thể gợi ý một cây bút cho khách hàng B.
Trước khi các phương pháp nâng cao dựa trên học sâu bùng nổ, các nhà nghiên cứu đã dùng DBSCAN để tách biệt các gen từ một bộ dữ liệu gen có khả năng tham gia trung gian gây ung thư.
Các nhà khoa học đã dùng DBSCAN để phát hiện các điểm dừng trong dữ liệu quỹ đạo tạo ra từ thiết bị GPS di động. Các điểm dừng đại diện cho phần có ý nghĩa và quan trọng nhất của một quỹ đạo.
Kết luận
Trong bài viết này, bạn đã biết về các nhược điểm chính của phân cụm dựa trên trọng tâm và làm quen với một họ kỹ thuật phân cụm khác, tức phân cụm dựa trên mật độ. Bạn cũng đã thấy cách chúng khắc phục các hạn chế của phân cụm dựa trên trọng tâm.
Bạn đã học cách DBSCAN hoạt động và cũng thực hiện một nghiên cứu tình huống về nó. Bên cạnh đó, bạn có cái nhìn tổng quan hợp lý về các bài toán thực tế nơi DBSCAN đã được ứng dụng để giải quyết. Để đọc thêm, tôi thực sự khuyên bạn nên tìm hiểu các phương pháp phân cụm dựa trên mật độ khác như phân cụm Cây Tập Mức và cách nó khác DBSCAN.
Nếu bạn muốn tìm hiểu thêm về phân cụm trong Python, hãy học khóa Unsupervised Learning in Python của chúng tôi.
Tài liệu tham khảo:
Martin Ester, Hans-Peter Kriegel, Jörg Sander và Xiaowei Xu. 1996. Thuật toán dựa trên mật độ để khám phá các cụm trong các cơ sở dữ liệu không gian lớn có nhiễu. Trong Kỷ yếu Hội nghị Quốc tế lần thứ hai về Khai phá Tri thức và Khai thác Dữ liệu (KDD'96), do Evangelos Simoudis, Jiawei Han và Usama Fayyad (Biên tập). AAAI Press 226-231.
https://towardsdatascience.com/how-dbscan-works-and-why-should-i-use-it-443b4a191c80
https://www.coursera.org/learn/predictive-analytics/lecture/EVHfy/dbscan