以前在開發 Chrome 擴充 NimoTab 時，有 1 個功能需要將相似/相同的網頁標題分群在一起，例如下圖：
當時用的是土炮的方法（但其實類似 DBSCAN），不過後來跟從事機器學習的同事討教有沒有更好的做法時，才知道有 1 個稱為 DBSCAN 的演算法可以使用。
本文將介紹 DBSCAN 這個實用的分群演算法，並以實際範例展示如何做到將相似的資料分群在一起，藉此讓大家對 DBSCAN 有更深入的理解。
本文環境
- Python 3
群 (cluster) / 雜訊 (noise)
在理解 DBSCAN 演算法之前，需要先理解 2 個機器學習的重要概念：
- 群 (cluster)
- 雜訊 (noise)
分群(Clustering)是機器學習中的一個重要主題，其目標是將一組資料中的相似資料歸納到同一群組。如果資料集中存在多種相似資料，則可以將其分成多個群組。由於分群屬於非監督式學習技術，它可以應用於沒有標準答案的情況。
p.s. 如果每一筆資料都有正確答案或者標籤(label)的情況，通常會使用另一種稱為分類(classification)的技術
例如下圖可以明顯感覺到資料能夠分成 2 群，而剩下的 1 個黑色點無法被歸類，這就是雜訊(noise)。
雜訊(Noise)在機器學習中指的是那些不符合任何已知群組特徵或模式的資料。這些資料可能是因為異常值、錯誤而產生，通常無法被機器學習模型很好地解釋，甚至可能干擾模型的訓練和預測過程，因此通常需要特別處理或排除。
在分群的應用情境下，雜訊通常指那些無法歸屬於任何一個群組的資料。
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 簡介
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 是一種基於密度的分群演算法，針對集中形狀不規則的資料進行分群，例如以下是 sklearn 針對多種分群演算法所做的比較圖：
其中關於 DBSCAN 的分群結果，可以看到 DBSCAN 對於集中形狀不規則資料分群效果頗好的：
DBSCAN 的主要特點是可以自動處理資料中的雜訊(noise)以及不需要預先指定群數。
DBSCAN 通過分析資料點的鄰近密度來判斷哪些點屬於相同的群，並將密度不足的資料點標為雜訊，這使得 DBSCAN 適合用於含有雜訊的資料集(dataset)。
圖解 DBSCAN 核心概念
DBSCAN 有 3 個重要核心概念：
- Core points
- Reachable points
- Outliers
在使用 DBSCAN 時，我們需要定義：
- 1 個半徑(radius) ε
- 1 個群所需要的最少鄰居數 minPoints
如果有 1 個點 p 周圍半徑 ε 滿足 1 個群所需要的最少鄰居數 minPoints（包含 p 點），那點 p 就是 Core points，例如下圖：
然後 DBSCAN 會從 Core points p 點的鄰近點開始，查看每一個鄰近點是否有周圍半徑 ε 滿足 1 個群所需要的最少鄰居數 minPoints 的情況。如果有的話，這個鄰近點也屬於 Core points；如果沒有的話就屬於 Reachable points。
例如下圖 P, Q, R, S 都符合 Core points 的條件，而 T 點則無法滿足 Core points 的條件，因為 T 點的周圍半徑只有 Q 點，但是 T 點仍落在 Q 點的周圍半徑範圍內，所以 T 屬於 Reachable points，而 P, Q, R, S, T 屬於同 1 個群：
如果有 1 個點無法滿足 Core points 與 Reachable points 的條件，就屬於 Outliers (或稱雜訊)，例如下圖的 U 點：
也因為 DBSCAN 會以群內的每個點為中心尋找周圍是否仍有符合 Core points 條件的點，並藉此擴展群的範圍，所以它具有針對集中形狀不規則的資料進行分群的能力，它的運作過程如下，可以看到群的擴展過程：
p.s. 可以在 Visualizing DBSCAN Clustering 玩看看 DBSCAN
DBSCAN 演算法
DBSCAN 的演算法虛擬碼(pseudocode)如下所示：
上述虛擬碼的註解其實已經將 DBSCAN 解釋得很清楚，在此不多加贅述。
上圖可以看到 DBSCAN 參數中有距離函式 distFunc (distance function)，這代表 DBSCAN 可以使用任意距離函數來衡量資料跟資料之間的距離，最簡單的距離函數可以使用歐幾里德距離；參數 eps 就是我們所定義的半徑(radius) ε；參數 minPts 則是 1 個群所需要的最少鄰居數 minPoints。
而上圖的 RangeQuery() 虛擬碼如下，它做的事情很單純，即是找出參數 Q 點的周圍半徑 eps 內有多少筆鄰近的資料：
以 Python 實作 DBSCAN
以 Python 程式碼實作 DBSCAN 的程式碼如下：
def dbscan(data, distance_func, eps, min_points):
"""
Performs DBSCAN clustering on the given data.
Args:
data: A list of data points.
distance_func: The distance function to use.
eps: The radius around each point.
min_points: The minimum number of points required to form a dense region.
Returns:
A list of cluster assignments for each data point.
"""
labels = [None] * len(data) # Initialize labels as None (undefined)
cluster_id = 0
for i in range(len(data)):
if labels[i] is not None: # Already assigned to a cluster or noise
continue
neighbors = range_query(data, distance_func, i, eps)
if len(neighbors) < min_points:
labels[i] = -1 # Mark as noise
else:
cluster_id += 1
labels[i] = cluster_id
# Expand cluster
seeds = neighbors.copy()
for j in seeds:
if labels[j] == -1:
labels[j] = cluster_id
if labels[j] is not None:
continue
labels[j] = cluster_id
new_neighbors = range_query(data, distance_func, j, eps)
if len(new_neighbors) >= min_points:
for k in new_neighbors:
if k not in seeds:
seeds.append(k)
return labels
前述程式碼的 dbscan() 會回傳 1 個長度與參數 data 相同的 list，其中每個元素對應的是參數 data 的群，如果值為 -1 則代表為雜訊，1 以上的值(含 1)則代表群的編號。
前述程式碼的 range_query() 實作如下，其作用是找出特定點的周圍半徑 eps 內的資料的索引值：
def range_query(data, distance_func, point_index, eps):
"""Finds the neighbors of a point within a given radius (eps)."""
neighbors = []
for i in range(len(data)):
if distance_func(data[point_index], data[i]) <= eps:
neighbors.append(i)
return neighbors
如此就實作完 DBSCAN 了！
DBSCAN 實際應用
假設我們有一大堆新聞文章標題，如果我們想有效率地對文章標題進行整理，因為我們通常不知道要將文章分成幾類，此時就可以使用 DBSCAN 將相似的文章整理在一起。
而衡量文章標題相似度的距離函數可以使用 Jaccard Index，至於斷詞(tokenize)方式我們可以使用 bigram，這樣做的好處是實作很簡單之外，也可以處理中英文混雜的情況（當然，如果有好的斷詞器也可以使用）。
p.s. bigram 是指將字串斷詞長度為 2 的多個子字串，例如 我愛演算法 可以斷詞成 我愛 , 愛演 , 演算 , 算法，除了以字元為單位之外，bigram 也可以用詞做為單位，例如 (我, 愛) , (愛, 演算法) 也算是 bigram。
以字元為單位的 bigram 程式碼如下：
def bigram_tokenize(text):
"""Tokenizes a text string into bigrams."""
tokens = []
for i in range(len(text) - 1):
tokens.append(text[i:i+2])
return tokens
計算相似度的 Jaccard Index 程式碼如下：
def jaccard_distance(tokens1, tokens2):
"""Calculates the distance between two token lists using Jaccard distance."""
set1 = set(tokens1)
set2 = set(tokens2)
intersection = len(set1.intersection(set2))
union = len(set1.union(set2))
if union == 0:
return 0
return 1 - (intersection / union)
實際用 1 個例子作為示範，讓各位知道使用 DBSCAN 分群的大致過程。
假設，以下是我們想分群的文章標題（為方便僅顯示五筆）：
data = [
'AI technology transforming industries',
'AI 技術如何改變行業',
'Introduction to Machine Learning',
'機器學習入門',
'Top 10 Python libraries for data science',
]
接著，我們對每一個文章標題進行 bigram 斷詞：
tokenized_data = [bigram_tokenize(text) for text in data]
再來，交給 DBSCAN 演算法進行分群，使用的距離函數為 Jaccard Index，我們把半徑設定為 0.6，以及群的最少資料數為 3（各位可以自行調整設定）：
eps = 0.6 # Adjust the radius as needed
min_points = 3 # Adjust the minimum points as needed
labels = dbscan(tokenized_data, jaccard_distance, eps, min_points)
最後，我們把分群結果與原始資料合併顯示：
from collections import defaultdict
from pprint import pprint
d = defaultdict(list)
# Print the cluster assignments
for i in range(len(data)):
cluster_id = labels[i]
if cluster_id == -1:
#print(f"{data[i]} - Noise")
pass
else:
d[cluster_id].append(data[i])
for k, v in d.items():
print(f"Cluster {k}:")
pprint(v)
print('--'*5)
分群結果如下，從結果也可以看到一些相似的標題都被分在同 1 群中的狀況：
Cluster 1:
['Introduction to Machine Learning',
'Introduction to Reinforcement Learning',
'Introduction to cloud computing',
'Introduction to AI ethics']
----------
Cluster 2:
['人工智慧在醫療中的應用',
'人工智慧在網路安全中的應用',
'人工智慧在自動駕駛中的應用',
'人工智慧在個人化醫療中的應用',
'人工智慧在自然災害預測中的應用',
'人工智慧在零售行業中的應用',
'機器學習在異常偵測中的應用',
'人工智慧在電子商務中的應用',
'機器學習在醫療中的應用',
'人工智慧在預測性維護中的應用',
'人工智慧在環境可持續性中的應用',
'人工智慧在法律科技中的應用',
'人工智慧在個人化客戶體驗中的應用',
'人工智慧在公共政策中的應用',
'人工智慧在風險管理中的應用',
'人工智慧在創意產業中的應用',
'人工智慧在遊戲中的應用',
'人工智慧在災難應對中的應用']
----------
Cluster 3:
['Automated machine learning tools',
'How to train a machine learning model',
'How to deploy machine learning models',
'How to learn deep learning',
'Top machine learning algorithms',
'AI and machine learning in manufacturing']
----------
Cluster 4:
['人工智慧驅動的聊天機器人',
'人工智慧驅動的行銷策略',
'人工智慧驅動的推薦系統',
'人工智慧驅動的供應鏈管理',
'人工智慧驅動的虛擬助理',
'人工智慧驅動的商業智慧']
----------
Cluster 5:
['深度學習在電腦視覺中的應用',
'深度學習在機器人學中的應用',
'深度學習在語音辨識中的應用']
是否很有趣呢！
p.s. 完整程式碼在此
如何調整 DBSCAN 分群結果
調整 DBSCAN 分群結果的方法有幾個：
- 調整 eps，也就是半徑大小，如果分群結果雜訊比較多，可以試著增加 eps 以減少雜訊的數量。
- 調整 minPoints，如果希望成群的條件變嚴苛，則可以調整 minPoints 參數，不過增加 minPoints 會讓成群的條件變嚴苛，也可能導致某些小群組變成雜訊。
- 調整距離函數，使用合適的距離函式，也能夠改善 DBSCAN 分群的能力。
總結
本文所介紹的 DBSCAN 演算法是相當實用的分群演算法，其優點在於：
- 不需事先設定群的數量（例如 K-means 需要事先設定群的數量）
- 可以處理雜訊(noise)
- 對集中形狀不規則的資料有較佳的處理能力
本文實際用 Python 程式碼進行實作並展示實際應用的範例，以期讓初學者能夠有足夠的認識基礎，不過各大機器學習相關的框架都有實作 DBSCAN（例如 sklearn），如果對 DBSCAN 已有足夠理解的話，可以直接使用各大框架所實作的 DBSCAN 即可。
以上！
Enjoy!
References
DBSCAN, Explained in 5 Minutes
不要再用 K-means！ 超實用分群法 DBSCAN 詳解
