1.? 基本原理
OPTICS（Ordering Points To Identify the Clustering Structure）是一種基于密度的聚類算法，可視為DBSCAN的改進版本。它能夠識別不同密度的簇，并自動發現數據中的層次化聚類結構，適用于復雜分布的數據集。適合如下應用場景：
- 地理空間數據分析：識別不同密度的城市熱點區域。
- 生物信息學：基因表達數據的層次化聚類。
- 異常檢測：通過可達性圖識別離群點（高可達距離的點）。
- 圖像分割：處理紋理密度不均勻的圖像。
關鍵概念
DBSCAN的局限性：
-
對全局參數
eps（鄰域半徑）敏感，難以處理密度變化大的數據。 -
無法直接輸出層次化聚類結果。
OPTICS的改進：
-
通過計算可達距離（Reachability Distance），避免固定
eps的限制。 -
生成可達性圖（Reachability Plot），支持多尺度聚類分析。
| 術語 | 定義 |
|---|---|
| 核心距離 | 使點成為核心對象的最小半徑（類似DBSCAN的eps）。 |
| 可達距離 | 點p到點o的可達性，定義為max(核心距離(o), 歐氏距離(o,p))。 |
| 簇排序 | 通過可達距離生成數據點的有序列表，反映密度結構。 |
算法步驟
-
初始化：
-
設定參數
min_samples（核心點的最小鄰域點數）和max_eps（可選，限制搜索范圍）。 -
為每個點計算核心距離和可達距離。
-
-
生成有序列表：
-
從任意未訪問點開始，擴展其
eps-鄰域。 -
若鄰域內點數≥
min_samples，標記為核心點，并計算其鄰域點的可達距離。 -
按可達距離從小到大將點加入有序列表。
-
-
提取簇結構：
-
通過可達性圖識別“山谷”區域（低可達距離），每個山谷對應一個簇。
-
使用參數
xi或eps切割可達性圖，提取最終聚類。
-
OPTICS與HDBSCAN對比如下：
| 特性 | HDBSCAN | OPTICS |
|---|---|---|
| 基礎算法 | 基于DBSCAN的層次化改進 | 基于DBSCAN的密度排序擴展 |
| 核心思想 | 通過層次聚類提取穩定簇，自動選擇簇 | 生成可達性圖，通過閾值提取簇 |
| 簇提取方式 | 基于最小簇大小和最小樣本數 | 基于可達距離和ξ（xi）參數 |
| 噪聲處理 | 明確區分噪聲點（標簽=-1） | 可通過參數過濾噪聲 |
| 參數 | HDBSCAN | OPTICS |
|---|---|---|
| 關鍵參數 | min_cluster_size,?min_samples | min_samples,?xi,?eps |
| 距離度量 | 支持任意距離（如歐式、余弦） | 通常使用歐式距離 |
| 自動化程度 | 自動確定簇數 | 需手動設置ξ或eps提取簇 |
| 優點 | 自動確定簇數：無需預設簇數量。 處理變密度數據：適應不同密度的簇。 魯棒性強：對噪聲和參數選擇不敏感。 | 可視化支持：可達性圖直觀展示聚類結構。 靈活性高：通過ξ參數動態提取簇。 |
| 缺點 | 計算復雜度高：大數據集可能較慢。 需要調參： | 手動提取簇：需人工干預選擇閾值。 參數敏感： |
| 場景 | HDBSCAN | OPTICS |
|---|---|---|
| 自動聚類 | ? 最佳選擇 | ?? 需手動提取簇 |
| 變密度數據 | ? 表現優異 | ? 需調整ξ參數 |
| 噪聲數據 | ? 明確標記噪聲 | ? 需后處理過濾 |
| 可視化分析 | ?? 有限支持 | ? 可達性圖直觀 |
| 大規模數據 | ?? 較慢（可近似優化） | ?? 中等規模更適用 |
2. Python實現
from sklearn.cluster import OPTICS
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons# 生成示例數據（月牙形分布）
X, _ = make_moons(n_samples=300, noise=0.05, random_state=42)# OPTICS模型
# min_samples：核心點的最小鄰域點數
# xi：決定簇邊界陡峭度的閾值（0~1）
# min_cluster_size：最小簇大小（可選）
clustering = OPTICS(min_samples=10, xi=0.05, min_cluster_size=0.1)# 擬合并預測
clustering.fit(X)
labels = clustering.labels_# 可視化
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', s=10)
plt.title("OPTICS Clustering")
plt.show()參數說明
| 參數 | 作用 |
|---|---|
min_samples | 定義核心點的鄰域最小點數（值越小，對噪聲越敏感）。 |
xi | 控制簇邊界的陡峭度（較小值生成更多小簇）。 |
min_cluster_size | 簇的最小樣本比例（0~1）或絕對數量。 |
max_eps | 限制鄰域搜索的最大半徑（若為np.inf，則完全依賴min_samples）。 |
可達性圖解讀：
-
低可達距離的區域（“山谷”）代表高密度簇。
-
高峰值點可能是噪聲或簇邊界。
# 繪制可達性圖
space = np.arange(len(X))
reachability = clustering.reachability_[clustering.ordering_]
labels = clustering.labels_[clustering.ordering_]plt.figure(figsize=(10, 5))
plt.plot(space, reachability, 'k-', alpha=0.6)
plt.scatter(space, reachability, c=labels, cmap='viridis', s=10)
plt.ylabel('Reachability Distance')
plt.title('Reachability Plot')
plt.show()層次化簇提取
通過調整xi或手動切割可達性圖，可提取不同密度的簇：
# 使用不同xi值提取簇
clustering_xi = OPTICS(min_samples=10, xi=0.1).fit(X)
labels_xi = clustering_xi.labels_plt.scatter(X[:, 0], X[:, 1], c=labels_xi, cmap='viridis', s=10)
plt.title(f"OPTICS with xi=0.1 (Clusters: {len(np.unique(labels_xi))})")
plt.show()3. 總結
| 特性 | OPTICS | DBSCAN |
|---|---|---|
| 參數敏感性 | 僅需min_samples，對eps不敏感 | 依賴eps和min_samples |
| 輸出結果 | 可達性圖 + 層次化簇 | 單一密度閾值下的硬劃分 |
| 計算復雜度 | 較高（需維護有序列表） | 較低 |
| 適用場景 | 多密度簇、層次化分析 | 單一密度、簡單分布 |
優點
-
無需預設
eps，適應多密度數據。 -
可輸出層次化聚類結構。
-
對噪聲魯棒性強。
缺點
-
計算復雜度高于DBSCAN（近似于O(n log n)）。
-
參數
xi的選擇需要經驗或調優。自動選擇xi：基于可達性圖的梯度變化自動切割（如sklearn.cluster.cluster_optics_xi）。 -
高維數據可能表現不佳（需配合降維）。
進階技巧
-
加速計算：使用
KDTree或BallTree優化鄰域搜索（通過metric_params設置） -
處理大數據集：結合
HDBSCAN（基于OPTICS思想的擴展算法）
