本文介绍一种可以按照点的密度进行聚类的算法。该算法的名称为DBSCAN。其英文全称为（Density-based spatial clustering of applications with noise）。该算法根据空间点的密度进行聚类：给定某空间里的一个点集合，这算法能把附近的点分成一组（有很多相邻点的点），并标记出位于低密度区域的局外点（最接近它的点也十分远），也就是一些与聚集的点比较远的点能够自动被当做离群点去掉。DBSCAN是一种比较常用的聚类分析算法，在论文中也经常被引用。
下面给出几张图片展示该算法的效果：
通过图形，来介绍这个算法的特点，你可能更容易理解，该算法有如下几个特点：
DBSCAN不需要预先声明聚类数量;DBSCAN可以找出任何形状的聚类，甚至能找出一个聚类，它包围但不连接另一个聚类;DBSCAN能分辨噪音（局外点）;
这里列出的为该算法一些比较直观的特点，以上的这些特点让DBSCAN非常适合对空间数据点进行聚类，它能够有效分辨异常点，并且不需要我们预先指定聚类数量，对空间中点的聚集情况能够很好的进行处理。
对算法的用处有个大致了解后，就可以试着去理解它的原理了，下面这段文字和图片解释了DBSCAN算法的原理：
考虑在某空间里将被聚类的点集合，为了进行 DBSCAN 聚类，所有的点被分为核心点，可达点及局外点，详请如下：如果一个点 p 在距离 ε 范围内有至少 minPts 个点(不包括自己)，则这个点被称为核心点，那些 ε 范围内的则被称为由 p 直接可达的，根据此定义，没有任何点是由非核心点直接可达的。如果存在一条道路 p1, …, pn ，有 p1 = p和pn = q， 且每个 pi+1 都是由 pi 直接可达的(道路上除了 q 以外所有点都一定是核心点)，则称 q 是由 p 可达的。所有不由任何点可达的点都被称为局外点。如果 p 是核心点，则它与所有由它可达的点(包括核心点和非核心点)形成一个聚类，每个聚类拥有最少一个核心点，非核心点也可以是聚类的一部分，但它是在聚类的“边缘”位置，因为它不能达至更多的点。
在这幅图里，minPts = 4（一个聚类中至少有4个点），点 A 和其他红色点是核心点，因为它们的 ε-邻域（图中红色圆圈）里包含最少 4 个点（包括自己），由于它们之间相互相可达，它们形成了一个聚类。点 B 和点 C 不是核心点，但它们可由 A 经其他核心点可达，所以也属于同一个聚类。点 N 是局外点，它既不是核心点，又不由其他点可达。
“可达性”不是一个对称关系，因为根据定义，没有点是由非核心点可达的，但非核心点可以是由其他点可达。所以为了正式地界定 DBSCAN 找出的聚类，进一步定义两点之间的“连结性”：如果存在一个点 o 使得点 p 和点 q 都是由 o 可达的，则点 p 和点 q 被称为(密度)连结的，而连结性是一个对称关系。定义了连结性之后，每个聚类都符合两个性质：
一个聚类里的每两个点都是互相连结的；
如果一个点 p 是由一个在聚类里的点 q 可达的，那么 p 也在 q 所属的聚类里。
说完了原理，我们再来看一下怎么去实现，在scikit-learn的官方网站，给出了一个DBSCAN算法的示例代码，这段演示了在Python中，我们将怎样使用DBSCAN来实现聚类。
请在电脑端打开阅读代码，或者访问官方文档：
http://scikit-learn.org/stable/auto_examples/cluster/plot_dbscan.html#sphx-glr-auto-examples-cluster-plot-dbscan-py
print(__doc__)
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_] = Truelabels = 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(each) for each in np.linspace(0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):
if k == -1:
# Black used for noise. col = [0, 0, 0, 1] class_member_mask = (labels == k) xy = X[class_member_mask & core_samples_mask] plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col), markeredgecolor='k', markersize=14) xy = X[class_member_mask & ~core_samples_mask] plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col), markeredgecolor='k', markersize=6) plt.title('Estimated number of clusters: %d' % n_clusters_) plt.show
这段代码的运行结果如下图所示，也就是上面我引用过得一幅图形：
据我的研究，在R语言，RapidMiner等数据挖掘工具中，也提供了类似的算法，你可以选择自己熟悉的工具去使用该算法，不同的工具官方一般都会提供相应的文档，可按照文档的提示进行使用即可。