DBSCAN
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法將簇看做高密度區(qū)域以從低密度區(qū)域中區(qū)分開编兄。由于這個(gè)算法的一般性驮瞧，DBSCAN建立的簇可以是任何形狀的。相對(duì)的抬纸，K-means則假設(shè)簇是凸的。核樣本的概念是DBSCAN的重要成分，核樣本是指高密度區(qū)域的樣本琐旁。一個(gè)簇是由互相靠近的核樣本的集合以及靠近核樣本的非核樣本組成的集合組成的。這個(gè)算法有兩個(gè)參數(shù)猜绣，
min_samples和 eps 灰殴，這兩個(gè)參數(shù)表示數(shù)據(jù)的稠密性。當(dāng)min_samples增加 或者 eps 減小的時(shí)候掰邢，意味著一個(gè)簇分類有更大的密度要求验懊。
若樣本在數(shù)據(jù)集中存在eps距離內(nèi)有至少min_samples擅羞，則該樣本可以成為核樣本。也用來定義邊緣樣本义图。核樣本是向量空間的高密度區(qū)域。通過找到一個(gè)核樣本召烂，找到其附近的核樣本碱工，再找到附近核樣本的附近的核樣本遞歸地建立由核樣本組成的簇。一個(gè)簇也包含鄰居是核樣本的非核樣本奏夫。
根據(jù)定義怕篷，任何核樣本是簇的一部分。任何距離核樣本至少eps距離非核樣本是異常值酗昼。
從下圖中可以看到廊谓，不同的顏色表示不同的簇。大圈圈表示算法定義的核樣本麻削，小圈圈表示仍是簇的組成部分的非核樣本蒸痹。黑色點(diǎn)表示異常值。
實(shí)現(xiàn)
這個(gè)算法是有隨機(jī)性的呛哟，雖然標(biāo)簽會(huì)變化叠荠，但是核樣本始終屬于同一個(gè)簇。非確定性主要來自非核樣本的歸屬扫责。一個(gè)非核樣本可能距離兩個(gè)簇的非核樣本都小于eps 榛鼎。根據(jù)三角不等式，這兩個(gè)核樣本之間的距離大于eps鳖孤，否則他們會(huì)屬于同一個(gè)簇者娱。非核樣本將會(huì)屬于先產(chǎn)生的簇，而簇產(chǎn)生的先后順序是隨機(jī)的苏揣。不考慮數(shù)據(jù)集的順序黄鳍，算法是確定性的，相同數(shù)據(jù)上的 結(jié)果也會(huì)相對(duì)穩(wěn)定腿准。
當(dāng)先實(shí)現(xiàn)是使用球樹和線段樹來計(jì)算點(diǎn)的鄰居际起，這避免了計(jì)算時(shí)全距離矩陣⊥麓校可以使用一般的距離度量方法街望。
內(nèi)存消耗
當(dāng)前實(shí)現(xiàn)不是一個(gè)節(jié)約內(nèi)存的算法，因?yàn)樗⒘薻d-tree和ball-tree不能使用的成對(duì)的相似矩陣弟跑≡智埃可以繞過這個(gè)的方法如下：
- 可以通過metric='precomputed'計(jì)算稀疏的半徑臨近圖，這會(huì)節(jié)省內(nèi)存使用孟辑。
- 數(shù)據(jù)可以壓縮哎甲，或者使用BIRCH去掉數(shù)據(jù)中的重復(fù)值蔫敲。然后大量的數(shù)據(jù)集將由小部分?jǐn)?shù)據(jù)代表，可以使用sample_weight來擬合算法
使用說明
class sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric='euclidean', algorithm='auto', leaf_size=30, p=None, n_jobs=1)
| 參數(shù) | 說明 |
|---|---|
| eps | float炭玫，可選 |
| min_samples | int奈嘿，可選 |
| metric | string，用于計(jì)算特征向量之間的距離 |
| algorithm | {‘a(chǎn)uto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}吞加，可選 |
| leaf_size | 傳遞給球樹裙犹，影響速度、內(nèi)存衔憨，根據(jù)情況自己選擇 |
| p | 明氏距離的冪次叶圃，用于計(jì)算距離 |
| n_jobs | CPU并行數(shù) |
| 方法 | 說明 |
|---|---|
| fit(X[, y, sample_weight]) | 從特征矩陣進(jìn)行聚類 |
| fit_predict(X[, y, sample_weight]) | 實(shí)行聚類并返回標(biāo)簽(n_samples, n_features) |
| get_params([deep]) | 取得參數(shù) |
| set_params(**params) | 設(shè)置參數(shù) |
| 屬性 | 類型 | 大小 | 說明 |
|---|---|---|---|
| core_sample_indices_ | array | [n_core_samples] | 核樣本的目錄 |
| components_ | array | [n_core_samples, n_features] | 訓(xùn)練樣本的核樣本 |
| labels_ | array | [n_samples] | 聚類標(biāo)簽。噪聲樣本標(biāo)簽為-1 |
例子
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler
##############################################################################
# Generate sample data
centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4,
random_state=0)
X = StandardScaler().fit_transform(X)
##############################################################################
# Compute DBSCAN
db = DBSCAN(eps=0.3, min_samples=10).fit(X)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_
# Number of clusters in labels, ignoring noise if present.
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
print('Estimated number of clusters: %d' % n_clusters_)
print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))
print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))
print("Adjusted Rand Index: %0.3f"
% metrics.adjusted_rand_score(labels_true, labels))
print("Adjusted Mutual Information: %0.3f"
% metrics.adjusted_mutual_info_score(labels_true, labels))
print("Silhouette Coefficient: %0.3f"
% metrics.silhouette_score(X, labels))
##############################################################################
# Plot result
import matplotlib.pyplot as plt
# Black removed and is used for noise instead.
unique_labels = set(labels)
colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))
for k, col in zip(unique_labels, colors):
if k == -1:
# Black used for noise.
col = 'k'
class_member_mask = (labels == k)
xy = X[class_member_mask & core_samples_mask]
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
markeredgecolor='k', markersize=14)
xy = X[class_member_mask & ~core_samples_mask]
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
markeredgecolor='k', markersize=6)
plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()
應(yīng)用
關(guān)鍵在于調(diào)節(jié)前面提到的兩個(gè)參數(shù)践图，需要不斷修正掺冠。如果需要測(cè)試數(shù)據(jù)，可以留言码党。
import scipy.io as sio
import numpy as np
from sklearn.cluster import DBSCAN
#from sklearn import metrics
import matplotlib.pyplot as plt
data_smile = sio.loadmat('data\smile.mat')
X = data_smile['smile'][:, :2]
labels_true = data_smile['smile'][:, 2]
db = DBSCAN(eps=0.05, min_samples=3).fit(X)
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True
labels = db.labels_
# Number of clusters in labels, ignoring noise if present.
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
# Black removed and is used for noise instead.
unique_labels = set(labels)
colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels)))
for k, col in zip(unique_labels, colors):
if k == -1:
# Black used for noise.
col = 'k'
class_member_mask = (labels == k)
xy = X[class_member_mask & core_samples_mask]
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
markeredgecolor='k', markersize=14)
xy = X[class_member_mask & ~core_samples_mask]
plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=col,
markeredgecolor='k', markersize=6)
plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()
參考
- “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise” Ester, M., H. P. Kriegel, J. Sander, and X. Xu, In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, pp. 226–231. 1996
- 概要：http://scikit-learn.org/stable/modules/clustering.html#dbscan
- 參數(shù)說明：http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN
