算法短记 — DBSCAN聚类

DBSCAN算法全称“Density-Based Spatial Clustering of Applications with Noise”，是典型的密度聚类方法。

关于DBSCAN算法的详细介绍，请参考《机器学习（周志华）》9.5密度聚类。

sklearn中已经实现了DBSCAN。关于sklearn中DBSCAN的详细介绍，请查看：
http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html

调用sklearn中的DBSCAN算法，主要有两个参数需要调整：eps和min_samples。eps参数的意思是ϵ-邻域中两个样本之间的最大距离，min_samples参数的意思是核心对象ϵ-邻域中的最小样本数量。

假定数据集为D={x_1,x_2,⋯,x_m }，DBSCAN算法首先定义了以下几个概念：

DBSCAN基本概念（from 《机器学习（周志华）》9.5密度聚类）

DBSCAN将“由密度可达关系导出的最大密度相连样本集合”定义为“簇”。

DBSCAN算法伪码（from 《机器学习（周志华）》9.5密度聚类）

使用DBSCAN进行聚类的案例如下：

import pandas as pd
import numpy as np
from sklearn.cluster import DBSCAN

# step 1. 输入数据

data = [1457330154,
 1457330161,
 1457334366,
 1457333746,
 1457333752,
 1457334359,
 1457334357,
 1457334498,
 1457334501,
 1457334369,
 1457334504,
 1457334371,
 1457334513,
 1457334511,
 1457335570,
 1457335580,
 1457336210,
 1457336201]

# step 2. 调用sklearn中的DBSCAN算法对bus_ic进行聚类
dbscan = DBSCAN(eps=10, min_samples=1, n_jobs=-1)
cluster = dbscan.fit_predict(np.array(data).reshape(-1, 1))

# step 3. 整理聚类结果
clustered = pd.DataFrame(list(zip(data, cluster)),
                                columns=['time', 'cluster'])
clustered.sort_values('cluster', inplace=True)
print(clustered)

          time  cluster
0   1457330154        0
1   1457330161        0
2   1457334366        1
5   1457334359        1
6   1457334357        1
9   1457334369        1
11  1457334371        1
3   1457333746        2
4   1457333752        2
13  1457334511        3
12  1457334513        3
8   1457334501        3
7   1457334498        3
10  1457334504        3
14  1457335570        4
15  1457335580        4
16  1457336210        5
17  1457336201        5