【機器學(xué)習(xí)】DBSCAN算法

這篇具有很好參考價值的文章主要介紹了【機器學(xué)習(xí)】DBSCAN算法。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

參考鏈接：
https://blog.csdn.net/haveanybody/article/details/113092851
https://www.jianshu.com/p/dd6ce77bfb8a
https://blog.csdn.net/qq_38563206/article/details/120941479

1 介紹

DBSCAN(Density-Based Spatial Clustering of Applica tion with Noise)算法是于1996年提出的一種簡單的、有效的基于密度的聚類算法，該算法利用類的密度連通性快速發(fā)現(xiàn)任意形狀的類。該算法的中心思想是：對于一個類中的每一個點P(不包括邊界點)，在給定的某個Eps鄰域內(nèi)數(shù)據(jù)點的個數(shù)不少于Minpts。

DBSCAN算法不屬于圖聚類算法。圖聚類算法是一種基于圖結(jié)構(gòu)的聚類算法，它利用圖中的頂點和邊的信息來劃分聚類。DBSCAN算法不需要構(gòu)建圖結(jié)構(gòu)，它只需要計算數(shù)據(jù)點之間的距離，然后根據(jù)密度閾值和鄰域半徑來判斷數(shù)據(jù)點是否屬于某個聚類。

DBSCAN算法的主要優(yōu)點是：

它可以發(fā)現(xiàn)任意形狀的聚類，而不是像K-means算法那樣只能發(fā)現(xiàn)球形的聚類。
它可以識別噪聲點，并將它們從聚類中排除，而不是像層次聚類算法那樣將所有的數(shù)據(jù)點都分配到某個聚類中。
它不需要事先指定聚類的個數(shù)，而是根據(jù)數(shù)據(jù)的密度自動確定聚類的個數(shù)。

DBSCAN算法的主要缺點是：

它對密度閾值和鄰域半徑的選擇非常敏感，不同的參數(shù)設(shè)置可能導(dǎo)致不同的聚類結(jié)果。
它對高維數(shù)據(jù)的處理效果不佳，因為高維空間中的距離計算很難反映數(shù)據(jù)的真實相似度。
它對不同密度的聚類的劃分效果不佳，因為它使用的是全局的密度閾值，而不是針對每個聚類的局部密度閾值。

2 代碼

2.1 直接調(diào)用sklearn的接口

本小節(jié)最后會給出完整代碼，在這之前，先對代碼中出現(xiàn)的一些關(guān)鍵點做一個簡單的筆記。

2.1.0 sklearn.cluster.DBSCAN接口

sklearn.cluster.DBSCAN(
    eps=0.5,
    min_samples=5,  # 指定核心樣本的最小樣本數(shù)，鄰域內(nèi)至少需要有 min_samples 個樣本點（不包括樣本點自身）
    metric='euclidean',  # 距離度量方式，默認(rèn)是歐氏距離，具體選擇可參考KNN篇，選擇precomputed表示自己計算距離，fit時X傳入距離矩陣即可
    metric_params=None,  # metric的輔助參數(shù)，根據(jù)metric的值決定
    algorithm='auto',  # 近鄰點的查找方法，可選‘a(chǎn)uto’, ‘ball_tree’, ‘kd_tree’, ‘brute’。默認(rèn)auto會根據(jù)樣本數(shù)量自動選擇，具體可參考前面KNN的文章
    leaf_size=30,  # BallTree or cKDTree參數(shù)
    p=None,  # 閔可夫斯基距離的p，默認(rèn)None就是2，表示歐式距離
    n_jobs=None
)

詳細(xì)參考：
https://scikitlearn.com.cn/0.21.3/22/#237-dbscan
https://scikit-learn.org.cn/view/379.html

2.1.1 數(shù)據(jù)標(biāo)準(zhǔn)化方法

# 生成包含750個樣本的聚類數(shù)據(jù)集，其中每個樣本屬于上述三個中心之一，cluster_std 控制聚類的標(biāo)準(zhǔn)差
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0)
X = StandardScaler().fit_transform(X)  # 對樣本數(shù)據(jù)進行標(biāo)準(zhǔn)化處理，確保每個特征的均值為0，標(biāo)準(zhǔn)差為1
# X = MinMaxScaler().fit_transform(X)  # 對數(shù)據(jù)進行歸一化處理

數(shù)據(jù)預(yù)處理方法有很多，像常用的標(biāo)準(zhǔn)化、歸一化、特征工程之類，這里主要介紹一下標(biāo)準(zhǔn)化和歸一化。

標(biāo)準(zhǔn)化處理通常是為了確保不同特征的尺度一致，使得模型更容易收斂并提高算法的性能。雖然標(biāo)準(zhǔn)化處理在大多數(shù)情況下是有益的，但對于不規(guī)則數(shù)據(jù)（如存在極端離群值或不符合正態(tài)分布的數(shù)據(jù)），有時候可能需要謹(jǐn)慎處理。
對于不規(guī)則數(shù)據(jù)，可以考慮使用其他數(shù)據(jù)預(yù)處理方法，例如：

歸一化（Normalization）： 將數(shù)據(jù)縮放到一個固定的范圍，例如 [0, 1]。這對于受極端值影響較大的情況可能更合適。

RobustScaler： 該方法對數(shù)據(jù)中的離群值具有魯棒性，因此在存在離群值的情況下可能更適用。

特征工程： 根據(jù)數(shù)據(jù)的特點進行定制的特征變換，以滿足特定的數(shù)據(jù)分布。

最終選擇哪種預(yù)處理方法取決于數(shù)據(jù)的性質(zhì)和模型的需求。在處理不規(guī)則數(shù)據(jù)時，建議進行實驗比較不同的方法，以找到最適合特定數(shù)據(jù)集的預(yù)處理策略。
歸一化（Normalization）和標(biāo)準(zhǔn)化（Standardization）是兩種不同的數(shù)據(jù)縮放方法，盡管它們的目標(biāo)都是使得特征在數(shù)值上更一致，但采用的處理方式略有不同。

歸一化： 歸一化的目標(biāo)是將數(shù)據(jù)縮放到一個固定的范圍，通常是 [0, 1]。最常見的歸一化方法是使用最小-最大縮放，公式為：

$X_{\text{normalized}} = \frac{X - X_{\text{min}}}{X_{\text{max}} - X_{\text{min}}}$

這確保了所有特征的值都在 0 到 1 之間。
標(biāo)準(zhǔn)化： 標(biāo)準(zhǔn)化的目標(biāo)是使得數(shù)據(jù)的分布具有標(biāo)準(zhǔn)正態(tài)分布的特性，即均值為 0，標(biāo)準(zhǔn)差為 1。最常見的標(biāo)準(zhǔn)化方法是使用 Z 分?jǐn)?shù)標(biāo)準(zhǔn)化，公式為：

$X_{\text{standardized}} = \frac{X - \mu}{\sigma}$

其中 (\mu) 是均值，(\sigma) 是標(biāo)準(zhǔn)差。標(biāo)準(zhǔn)化處理后的數(shù)據(jù)集具有均值為 0，標(biāo)準(zhǔn)差為 1 的性質(zhì)。

雖然這兩種方法有不同的數(shù)學(xué)表達(dá)式，但它們的目的都是為了處理不同尺度的特征，使得模型更容易學(xué)習(xí)和收斂。選擇使用歸一化還是標(biāo)準(zhǔn)化通常取決于具體的任務(wù)和數(shù)據(jù)集的特點。

需要注意的是，在本文的示例代碼中，直接將X = StandardScaler().fit_transform(X)換成X = MinMaxScaler().fit_transform(X)最后計算輪廓系數(shù)的時候會報錯：ValueError: Number of labels is 1. Valid values are 2 to n_samples - 1 (inclusive)，為啥我目前也還不知道，有知道的好兄弟記得評論區(qū)踢我。

2.1.2 算法評估指標(biāo)

當(dāng)對聚類結(jié)果進行評估時，這些指標(biāo)提供了關(guān)于聚類性能的不同方面的信息：

同質(zhì)性（Homogeneity）： 衡量每個聚類中的成員是否都屬于同一類別。同質(zhì)性得分越高，表示聚類結(jié)果越好。
完整性（Completeness）： 度量是否找到了每個真實類別的所有成員。完整性得分越高，表示聚類結(jié)果越完整。
V-measure： 同質(zhì)性和完整性的調(diào)和平均，提供了對聚類結(jié)果的整體評估。
調(diào)整蘭德指數(shù)（Adjusted Rand Index）： 用于度量聚類結(jié)果與真實標(biāo)簽之間的相似性，接近 1 表示較高的相似性。
調(diào)整互信息（Adjusted Mutual Information）： 度量聚類結(jié)果與真實標(biāo)簽之間的信息一致性。
輪廓系數(shù)（Silhouette Coefficient）： 用于度量聚類結(jié)果的緊密性和分離性，值越接近 1 表示聚類結(jié)果越好。

DBSCAN是一種無監(jiān)督聚類算法，它不要求輸入數(shù)據(jù)包含真實標(biāo)簽。在正常的使用情況下，DBSCAN 是無需真實標(biāo)簽的。然而，在示例代碼中，labels_true 是提供的真實標(biāo)簽，主要是用于驗證聚類算法的性能，以評估聚類結(jié)果與真實標(biāo)簽之間的相似性。

通常情況下，對于無監(jiān)督聚類算法，我們在實際應(yīng)用中不知道數(shù)據(jù)的真實標(biāo)簽，因此評估聚類算法的性能時使用的是無監(jiān)督的內(nèi)部評估指標(biāo)，如輪廓系數(shù)、Calinski-Harabasz指數(shù)、DB指數(shù)等，它們不依賴于真實標(biāo)簽。這些指標(biāo)可以在沒有真實標(biāo)簽的情況下，通過對聚類結(jié)果自身進行評估，提供一些關(guān)于聚類質(zhì)量的信息。

Calinski-Harabasz指數(shù)
Calinski-Harabasz指數(shù)（也稱為方差比標(biāo)準(zhǔn)）是一種用于評估聚類結(jié)果的有效性的指標(biāo)。它通過計算簇內(nèi)的離散度與簇間的分離度之間的比率來度量聚類的緊密度和分離度。指數(shù)值越高，表示聚類效果越好。

具體計算方式為：

$\text{Calinski-Harabasz指數(shù)} = \frac{\text{簇間離散度}}{\text{簇內(nèi)離散度}} \times \frac{\text{樣本數(shù)量} - \text{簇數(shù)量}}{\text{簇數(shù)量} - 1}$

其中，簇內(nèi)離散度是各個簇內(nèi)樣本與其簇內(nèi)均值的距離的總和，簇間離散度是所有簇中心與數(shù)據(jù)整體均值的距離的總和。

Calinski-Harabasz指數(shù)越高，表示簇間的分離度較高，簇內(nèi)的離散度較低，聚類效果越好。

在 scikit-learn 中,可以使用 metrics.calinski_harabasz_score 函數(shù)來計算Calinski-Harabasz指數(shù)。例如：

from sklearn import metrics
calinski_harabasz_score = metrics.calinski_harabasz_score(X, labels)
print("Calinski-Harabasz指數(shù)：%0.3f" % calinski_harabasz_score)

DB指數(shù)
對于密度聚類算法（如DBSCAN），DB指數(shù)（Davies-Bouldin指數(shù)）是一種用于評估聚類結(jié)果的指標(biāo)。DB指數(shù)考慮了簇的緊密度和分離度，越小的值表示聚類結(jié)果越好。

DB指數(shù)的計算方式是對每個簇，計算該簇內(nèi)每個點與簇內(nèi)其他點的平均距離（緊密度），然后找到與該簇最近的其他簇，計算兩個簇中心的距離（分離度）。DB指數(shù)是緊密度與分離度的加權(quán)平均值，公式如下：

$\frac{1}{k} \sum_{i=1}^{k} \max_{j \neq i} \left( \frac{S_i + S_j}{d(C_i, C_j)} \right)$

其中：

(k) 是簇的數(shù)量。
(S_i) 是簇內(nèi)點到簇中心的平均距離。
(d(C_i, C_j)) 是簇中心之間的距離。

DB指數(shù)的優(yōu)點是越小越好，表示簇內(nèi)緊密度越高，簇間分離度越好。但請注意，DB指數(shù)的計算也涉及到對距離的定義，這在密度聚類中可能涉及到一些具體的選擇。

在 scikit-learn 中，可以使用 metrics.davies_bouldin_score 函數(shù)來計算DB指數(shù)。例如：

from sklearn import metrics

db_score = metrics.davies_bouldin_score(X, labels)
print("DB指數(shù)：%0.3f" % db_score)

DB指數(shù)是一種適用于密度聚類算法的評估指標(biāo)，對于不同形狀和大小的簇都比較穩(wěn)健。

在計算DB指數(shù)時，涉及到對距離的定義，特別是在密度聚類中，選擇距離的度量方式可能會影響DB指數(shù)的計算結(jié)果。通常來說，DB指數(shù)的計算可以使用不同的距離度量方法，其中 Euclidean 距離是最常見的選擇。

在 scikit-learn 中，默認(rèn)的距離度量方式通常是 Euclidean 距離，因為 Euclidean 距離在許多情況下都是一種合理的選擇。然而，對于一些特定的密度聚類場景，也可以考慮使用其他距離度量方法，例如 Mahalanobis 距離，特別是當(dāng)數(shù)據(jù)具有不同的方差和協(xié)方差結(jié)構(gòu)時。

在使用 metrics.davies_bouldin_score 函數(shù)計算DB指數(shù)時，你可以通過傳遞 metric 參數(shù)來指定距離度量方式。例如，使用 Mahalanobis 距離：

from sklearn import metrics
from scipy.spatial.distance import mahalanobis

# 自定義 Mahalanobis 距離的度量方式
def mahalanobis_distance(X, Y):
    # 在這里實現(xiàn) Mahalanobis 距離的計算方式
    # ...

# 計算DB指數(shù)，使用 Mahalanobis 距離
db_score = metrics.davies_bouldin_score(X, labels, metric=mahalanobis_distance)
print("DB指數(shù)：%0.3f" % db_score)

需要注意的是，Mahalanobis 距離的計算需要對每個簇內(nèi)的協(xié)方差矩陣進行估計，這可能會增加計算的復(fù)雜性。選擇合適的距離度量方式應(yīng)該根據(jù)具體的數(shù)據(jù)特點和任務(wù)需求來進行。

輪廓系數(shù)
輪廓系數(shù)（Silhouette Coefficient）是一種用于評估聚類結(jié)果好壞的指標(biāo)，它結(jié)合了簇內(nèi)的緊密度和簇間的分離度。輪廓系數(shù)的取值范圍在 [-1, 1] 之間，具體定義如下：

對于每個樣本：

計算該樣本與同簇內(nèi)其他樣本的平均距離，記為 (a)（簇內(nèi)緊密度）。
計算該樣本與最近的其他簇中所有樣本的平均距離，記為 (b)（簇間分離度）。
輪廓系數(shù) (s) 的計算方式為 $\max(a, b)$ 。

對于整個數(shù)據(jù)集，輪廓系數(shù)是所有樣本輪廓系數(shù)的平均值。

輪廓系數(shù)的解釋：

輪廓系數(shù)接近1表示簇內(nèi)樣本距離緊密，簇間樣本距離相對較遠(yuǎn)，聚類效果較好。
輪廓系數(shù)接近0表示簇內(nèi)樣本距離和簇間樣本距離相近，表明聚類結(jié)果不清晰。
輪廓系數(shù)接近-1表示簇內(nèi)樣本距離松散，簇間樣本距離較近，聚類效果差。

輪廓系數(shù)可以用于選擇合適的聚類數(shù)目，因為它在聚類數(shù)目選擇上的峰值通常對應(yīng)于較好的聚類結(jié)果。在使用輪廓系數(shù)時，需要注意對于某些不適合聚類的數(shù)據(jù)集，輪廓系數(shù)可能并不是一個有效的指標(biāo)。

2.1.3 繪圖顏色

colors = [plt.cm.Spectral(each) for each in np.linspace(0, 1, len(unique_labels))]

這行代碼用于生成一組顏色，以便在可視化中為不同的聚類標(biāo)簽選擇不同的顏色。

np.linspace(0, 1, len(unique_labels)): 生成一個從 0 到 1 的等差數(shù)列，數(shù)列的長度與聚類標(biāo)簽的數(shù)量相同。這個數(shù)列將用于確定顏色映射的位置，確保每個聚類標(biāo)簽都有一個對應(yīng)的顏色。
plt.cm.Spectral(each): 使用 Spectral 顏色映射，根據(jù)上面生成的等差數(shù)列中的每個值，獲取相應(yīng)位置的顏色。這樣就得到了一組不同的顏色，每個顏色對應(yīng)一個聚類標(biāo)簽。

這種方式確保了在可視化中使用了一組視覺上區(qū)分度較高的顏色，以區(qū)分不同的聚類。每個聚類標(biāo)簽都被分配一種顏色，使得在可視化中可以清晰地區(qū)分不同的簇。

2.1.4 完整代碼

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler, MinMaxScaler

# 生成三個聚類中心的樣本數(shù)據(jù)
centers = [[1, 1], [-1, -1], [1, -1], [-1,1]]

# 生成包含750個樣本的聚類數(shù)據(jù)集，其中每個樣本屬于上述三個中心之一，cluster_std 控制聚類的標(biāo)準(zhǔn)差
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4, random_state=0)
X = StandardScaler().fit_transform(X)  # 對樣本數(shù)據(jù)進行標(biāo)準(zhǔn)化處理，確保每個特征的均值為0，標(biāo)準(zhǔn)差為1
# X = MinMaxScaler().fit_transform(X)  # 對數(shù)據(jù)進行歸一化處理

# 使用 DBSCAN 算法進行聚類
# eps 控制鄰域的半徑，min_samples 指定一個核心點所需的最小樣本數(shù)
db = DBSCAN(eps=0.3, min_samples=20).fit(X)

# 創(chuàng)建一個布爾掩碼，標(biāo)記核心樣本點
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)   # 創(chuàng)建一個與 db.labels_ 具有相同形狀的全零數(shù)組，數(shù)據(jù)類型為布爾型
core_samples_mask[db.core_sample_indices_] = True   # 將核心樣本的位置標(biāo)記為True

# 獲取每個樣本點的聚類標(biāo)簽
labels = db.labels_  # labels_ 屬性可以返回聚類結(jié)果，-1表示是離群點。
# print(labels)

# 統(tǒng)計聚類結(jié)果的一些信息
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)  # 計算聚類的數(shù)量，忽略噪聲點（標(biāo)簽為-1的點）
n_noise_ = list(labels).count(-1)  # 統(tǒng)計噪聲點的數(shù)量

print('估計的聚類數(shù)量：%d' % n_clusters_)
print('估計的噪聲點數(shù)量：%d' % n_noise_)
# 同質(zhì)性和完整性的得分越高越好
print("同質(zhì)性：%0.3f" % metrics.homogeneity_score(labels_true, labels))  # 同質(zhì)性，衡量每個群集中的成員是否都屬于同一類別
print("完整性：%0.3f" % metrics.completeness_score(labels_true, labels))  # 完整性，度量是否找到了每個真實類別的所有成員
print("V-measure：%0.3f" % metrics.v_measure_score(labels_true, labels))  # V-measure，同質(zhì)性和完整性的調(diào)和平均
# 調(diào)整蘭德指數(shù)越接近1，說明聚類結(jié)果與真實標(biāo)簽之間具有越高的相似度
print("調(diào)整蘭德指數(shù)：%0.3f" % metrics.adjusted_rand_score(labels_true, labels))  # 調(diào)整蘭德指數(shù)，用于度量聚類結(jié)果與真實標(biāo)簽之間的相似性
print("調(diào)整互信息：%0.3f" % metrics.adjusted_mutual_info_score(labels_true, labels))  # 調(diào)整互信息，度量聚類結(jié)果與真實標(biāo)簽之間的信息一致性
print("輪廓系數(shù)：%0.3f" % metrics.silhouette_score(X, labels))  # 輪廓系數(shù)，度量聚類結(jié)果的緊密性和分離性，接近1表示聚類結(jié)果越好
print("DB指數(shù)：%0.3f" % metrics.davies_bouldin_score(X, labels))  # DB指數(shù)，衡量簇內(nèi)緊密度和簇間分離度的指標(biāo)，越小越好

# 畫圖
# 移除黑色（表示噪聲），用于標(biāo)識噪聲點
unique_labels = set(labels)  # 聚類得到的標(biāo)簽，即聚類得到的簇，標(biāo)記為{0,1,2,-1}，其中-1為噪聲點
colors = [plt.cm.Spectral(each) for each in
          np.linspace(0, 1, len(unique_labels))]  # 生成一組顏色，以便在可視化中為不同的聚類標(biāo)簽選擇不同的顏色，color.shape=(4,4)
# 遍歷每個聚類標(biāo)簽，為每個簇選擇顏色進行可視化
for k, col in zip(unique_labels, colors):
    if k == -1:
        # 對于標(biāo)簽為-1的噪聲點，使用黑色
        col = (0, 0, 0, 1)

    # 獲取屬于當(dāng)前聚類的樣本點
    class_member_mask = (labels == k)

    # 繪制核心樣本點（大圓點）
    xy1 = X[class_member_mask & core_samples_mask]
    plt.plot(xy1[:, 0], xy1[:, 1], 'o', markerfacecolor=tuple(col),
             markeredgecolor='k', markersize=8)

    # 繪制非核心樣本點（小圓點）
    xy2 = X[class_member_mask & ~core_samples_mask]
    plt.plot(xy2[:, 0], xy2[:, 1], 'o', markerfacecolor=tuple(col),
             markeredgecolor='k', markersize=6)

plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()

2.2 不使用sklearn接口

從別處copy過來的代碼，加上了一些必要的注釋，代碼比較簡單就不寫詳細(xì)說明了哇。文章來源地址http://www.zghlxwxcb.cn/news/detail-802962.html

# -*- coding: utf-8 -*-
import math
import random
import matplotlib.pyplot as plt


class DBSCAN(object):
    STATUS_UNVISITED = 'unvisited'  # 數(shù)據(jù)點的訪問狀態(tài)
    STATUS_VISITED = 'visited'

    STATUS_GROUP = 1  # 數(shù)據(jù)點是否被分類到聚類簇
    STATUS_NOGROUP = 0

    data = dict()  # 類屬性，用于存儲數(shù)據(jù)點的信息

    def __init__(self, e, minPts):
        """
        e: 最小距離
        minPts: 最少樣本數(shù)量
        """
        self.e = e
        self.minPts = minPts

    def nearby(self, id):
        """
        返回與給定樣本點 id 在最小距離內(nèi)的鄰近樣本點列表
        """
        nearby_points = list()
        for link_id in self.scores[id]:  # self.score是距離矩陣，用字典或者二維列表表示
            if self.scores[id][link_id] <= self.e:  # 如果當(dāng)前樣本點id到link_id的距離小于鄰域半徑，則加入nearby_points列表
                nearby_points.append(link_id)

        return nearby_points

    def visit_nearby_points(self, points, group):
        """
        遞歸訪問與給定樣本點列表 points 在最小距離內(nèi)的鄰近樣本點，并將其加入 group 中
        """
        for id in points:
            if self.data[id]['is_visited'] == self.STATUS_VISITED \
                    and self.data[id]['is_group'] == self.STATUS_GROUP:
                continue
            self.data[id]['is_visited'] = self.STATUS_VISITED

            if self.data[id]['is_group'] == self.STATUS_NOGROUP:
                group.append(id)
                self.data[id]['is_group'] = self.STATUS_GROUP

            nearby_points = self.nearby(id)
            if len(nearby_points) >= self.minPts:
                self.visit_nearby_points(nearby_points, group)

    def fit(self, data_set, scores):
        """
        運行 DBSCAN 算法，返回聚類結(jié)果
        data_set: 輸入數(shù)據(jù)集
        scores: 樣本之間的距離矩陣或字典
        """
        self.scores = scores
        groups = list()

        # 初始化數(shù)據(jù)狀態(tài)
        for index, item in enumerate(data_set):
            self.data[index] = {'id': index,
                                'is_visited': self.STATUS_UNVISITED,
                                'is_group': self.STATUS_NOGROUP
                                }

        # 遍歷每個樣本點
        for id in self.data:  # self.data是一個字典，id是key
            if self.data[id]['is_visited'] == self.STATUS_VISITED:
                continue

            # 標(biāo)記樣本點為已訪問
            self.data[id]['is_visited'] = self.STATUS_VISITED
            nearby_points = self.nearby(id)

            # 如果鄰近樣本點數(shù)量大于等于最小樣本數(shù)量，則形成一個新的簇
            if len(nearby_points) >= self.minPts:
                group = list()
                group.append(id)
                self.data[id]['is_group'] = self.STATUS_GROUP
                self.visit_nearby_points(nearby_points, group)
                groups.append(group)

        # 處理未被歸為任何簇的樣本點
        for id in self.data:
            if self.data[id]['is_group'] == self.STATUS_NOGROUP:
                groups.append([id])
        # print(self.data)    # {0: {'id': 0, 'is_visited': 'visited', 'is_group': 1},...}
        return groups


def init_data(num, min, max):
    # 生成隨機數(shù)據(jù)，data.shape=(num,2)，即
    data = []
    for i in range(num):
        data.append([random.randint(min, max), random.randint(min, max)])

    return data


def mat_score(data_set):
    """
    計算輸入數(shù)據(jù)集中每兩個樣本點之間的歐式距離，并返回一個距離字典
    data_set: 輸入數(shù)據(jù)集，每個樣本點表示為 [x, y] 形式的坐標(biāo)
    """
    # 初始化距離字典
    score = dict()
    for i in range(len(data_set)):
        score[i] = dict()

    # 計算每兩個樣本點之間的歐式距離
    for i in range(len(data_set) - 1):
        j = i + 1
        while j < len(data_set):
            # 計算歐式距離
            distance = math.sqrt(abs(data_set[i][0] - data_set[j][0]) ** 2 + abs(data_set[i][1] - data_set[j][1]) ** 2)

            # 將距離保存到距離字典中
            score[i][j] = distance
            score[j][i] = distance
            j += 1

    return score


def show_cluster(data_set, groups):
    plt.title(u'DBSCAN')
    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    for index, group in enumerate(groups):
        for i in group:
            plt.plot(data_set[i][0], data_set[i][1], mark[index])

    plt.xlim(0.0, 100)
    plt.ylim(0.0, 100)
    plt.show()


if __name__ == '__main__':
    data_set1 = init_data(20, 0, 30)
    data_set2 = init_data(20, 40, 60)
    data_set3 = init_data(20, 70, 100)
    data_set = data_set1 + data_set2 + data_set3

    score_mat = mat_score(data_set)

    groups = DBSCAN(20, 5).fit(data_set, score_mat)
    show_cluster(data_set, groups)