type
status
password
date
slug
summary
category
URL
tags
icon
我们知道kmeans聚类算法只能处理球形的簇，也就是一个聚成实心的团（这是因为算法本身计算平均距离的局限）。但往往现实中还会有各种形状，比如下面两张图，环形和不规则形，这个时候，那些传统的聚类算法显然就悲剧了。于是我们提出密度聚类方法，密度聚类方法的指导思想是，只要样本点的密度大于某阈值，则将该样本添加到最近的簇中。
这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。但计算密度单元的计算复杂度大，需要建立空间索引来降低计算量。
DBSCAN算法
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的空间聚类算法。 该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。
重要参数说明
- eps：相当于圈的半径，越大越小都不好，自己合适调节
- min_samples：相当于一个圈中最少的样本数，不到的话，就被划分为离散点
- metric：最近邻距离度量参数。可以使用的距离度量较多 ， 一般来说 DBSCAN 使用认的欧式距离(即 p=2 的闵可夫斯基距离)就可以满足我们的需求。 可以使用的距度度量参数有
类别 | 名称 | 公式 |
欧式距离 | Euclidean | |
曼哈顿距离 | manhattan | |
切比雪夫距离 | chebyshev | |
闵可夹断基距离 | minkowski | 为曼哈顿距离， 为欧式距离 |
带权闵可夫斯基距离 | wminkowski | 其中 为特征权重 |
标准化欧式距离 | seuclidean | 即对于各特征维度做了归一化以后的欧式距离。 此时各样本特征维度的均值为 0 |
马氏距离 | mahalanobis | 其中， 为样本协方差矩阵的逆矩阵。当样本分布独立时 为单位矩阵，此时马氏距离等同于欧式距离。 |
DBSCAN流程
DBSCAN案例
参数 | 类型 | 解释 |
eps | float, default=0.5 | 邻域的距离阈值 |
min_samples | int, default=5 | 样本点要成为核心对象所需要的邻域的样本数阈值 |
metric | str, or callable, default=‘euclidean’ | 度量方式，默认为欧式距离，可以使用的距离度量参数有
’euclidean’/‘manhattan’/‘chebyshev’/‘minkowski’/‘wminkowski’/‘seuclidean’/‘mahalanobis’ |
metric_params | dict, default=None | 度量函数的其他关键字参数 |
algorithm | {‘auto’, ‘ball_tree’, ‘kd_tree’, ‘brute’}, default=‘auto’ | 近邻算法求解方式。单纯的索引并不能优化。 |
leaf_size | int, default=30 | 使用’ball_tree’或’kd_tree’时停止建子树的叶子节点数量的阈值 |
p | float, default=None | 只用于闵可夫斯基距离和带权重闵可夫斯基距离中p值的选择，p=1为曼哈顿距离，p=2为欧式距离。 |
n_jobs | int, default=None | CPU并行数，值为-1时使用所有CPU运算 |
DBSCAN
KMeans
DBSCAN自定义距离
运行速度
DBSCAN的优缺点
- 优点：DBSCAN 与其他聚类算法相比有很多优点。首先，它根本不需要固定数量的簇。它也会将异常值识别为噪声，而不像均值漂移，即使数据点非常不同，也会简单地将它们分入簇中。另外，它能够很好地找到任意大小和任意形状的簇。
- 缺点：DBSCAN 的主要缺点是当簇的密度不同时，它的表现不如其他聚类算法。这是因为当密度变化时，用于识别邻域点的距离阈值 和 minPoints 的设置将会随着簇而变化。这个缺点也会在非常高维度的数据中出现，因为距离阈值 再次变得难以估计。
ST-DBSCAN
ST-DBSCAN（Spatial Temporal-DBSCAN）算法由DeryaBirant等人[2]在2007年提出用于海洋环境研究。ST-DBSCAN是在DBSCAN基础上发展而来，相比DBSCAN多了一个维度上的聚类。需要注意的是，多的一个维度上的约束条件不一定得是时间距离，可以是与二维空间其它无相关性的维度，例如高程、颜色、温度、质量等。
OPTICS算法
引言
OPTICS(Ordering points to identify the clustering structure)是一基于密度的聚类算法，OPTICS算法是DBSCAN的改进版本。在DBCSAN算法中需要输入两个参数： 和 MinPts ，选择不同的参数会导致最终聚类的结果千差万别，因此DBCSAN对于输入参数过于敏感。OPTICS算法的提出就是为了帮助DBSCAN算法选择合适的参数，降低输入参数的敏感度。
OPTICS和DBSCNA的输入参数一样（ 和 MinPts ），虽然OPTICS算法中也需要两个输入参数，但该算法对 输入不敏感（一般将 固定为无穷大），同时该算法中并不显式的生成数据聚类，只是对数据集合中的对象进行排序，得到一个有序的对象列表，通过该有序列表，可以得到一个决策图，通过决策图可以不同 参数的数据集中检测簇集，即：先通过固定的 MinPts 和无穷大的 得到有序列表，然后得到决策图，通过决策图可以知道当 取特定值时（比如 ）数据的聚类情况。
相关定义
由于OPTICS算法是DBSCAN算法的一种改进，因此有些概念是共用的，比如： -邻域，核心对象，密度直达，密度可达，密度相连等，下面是与OPTICS相关的定义（假设我的样本集是 ：
DBSCAN相关定义
- -邻域：对于 ，其 -邻域包含样本集 中与 的距离不大于 的子样本集。即 , 这个子样本集的个数记为 。 -邻域是一个集合
- 核心对象：对于任一样本 ，如果其 -邻域对应的 至少包含 MinPts 个样本，即如果 ，则 是核心对象。
- 密度直达：如果 位于 的 -邻域中，且 是核心对象，则称 由 密度直达。反之不一定成立，即此时不能说 由 密度直达，除非 也是核心对象，即密度直达不满足对称性。
- 密度可达：对于 和 ，如果存在样本序列 ，满足 ，且 由 密度直达，则称 由 密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本 均为核心对象，因为只有核心对象才能使其他样本密度直达。密度可达也不满足对称性，这个可以由密度直达的不对称性得出。
- 密度相连：对于 和 ，如果存在核心对象样本 ， 和 均由 密度可达，则称 和 密度相连。密度相连关系满足对称性。
OPTICS相关定义
在上述DBSCAN定义的基础上，OPTICS在引入了两个算法需要的定义：
- 核心距离（core-distance）：样本 ，对于给定的 和 MinPts ，使得 成为核心对象的最小邻域半径称为 的核心距离，其数学表达如下， 代表集合 中与节点 第 近邻的节点，如 表示 中与 最近的节点
- 可达距离（reachability-distance）：设 ,对于给定的 和 ， 关于 的可达距离定义为：
特别的，当 为核心点时（相应的参数为 和 MinPts ），可按照下式来理解
即 表示 使得“ 成为核心点”，“ 可以从 直接密度可达” 同时成立的最小邻域半径。可达距离这里可能不太好理解，先记住一点，每一个点都有两个新属性：`可达距离，核心距离`
算法思想
假设我们的数据集为，OPTICS算法的目标是输出一个有序排列，以及每个元素的两个属性值：核心距离，可达距离。为此引入如下的数据结构：
- 待处理队列：临时队列
- 结果队列
- ：OPTICS算法的输出有序列表，例如 表示：在集合 中的数据，第10号节点首先被处理，然后第100号节点被处理，然后第4号节点被处理（即节点被处理的顺序列表）
- ：第 号节点的核心距离，例如 表示：在集合X中的数据，第10号节点的核心距离为1.2，第100号节点的核心距离为1.4，第4号节点的核心距离为4.5
- ：第 号节点的可达距离，例如 表示：在集合中的数据，第10号节点的可达距离为3.4，第100号节点的可达距离为3.1，第4号节点的可达距离为4.5
算法流程
- 初始化核心对象集合
- 遍历 的元素，如果是核心对象，则将其加入到核心对象集合 中
- 如果核心对象集合 中元素都已经被处理，则算法结束，否则转入步骤4.
- 在核心对象集合 中，随机选择一个未处理的核心对象 ，首先将 标记为已处理，同时将 压入到结果列表中 (包括有序列表、核心距离列表、可达距离列表)，最后将 的 -邻域中未访问的点，根据可达距离的大小（计算未访问的邻居点到 点的可达距离）依次存放到待处理集合 中。
- 如果种子集合 ，跳转到3，否则，从待处理集合 seeds 中挑选可达距离最近的节点 seed ，首先将其标记为已访问，将 seed 标记为已处理，同时将 seed 压入到有序列表 p 中，然后判断 seed 是否为核心对象，如果是将 seed 中未访问的邻居点加入到种子集合中，重新计算可达距离。（计算种子集合中距离 seed 点的可达距离。如果可达距离更小，则更新可达距离）跳转到5.
说明：第一点，第一个被处理的对象是不存在可达距离的 （因为没有被计算过），只有进入过 seeds 的点才能计算可达距离。
算法伪代码
- OPTICS算法伪代码
- update算法伪代码
簇的定义
我们最后得到的结果列表包括有序列表（实际上相当于节点的索引）、可达距离列表、核心距离列表。我们使用这些结果列表对样本进行聚类
从结果队列中按照顺序取出样本点，直到结果队列为空
- 如果该点的可达距离小于等于人工设定的半径R，则该点属于当前聚类簇；
- 如果该点的可达距离大于人工设定的半径R，则
- 如果该点的核心距离大于给定的半径R，则为噪声点；
- 如果该点的核心距离小于等于给定的半径R，则为新的聚类簇；
算法案例（用示例展示算法）
假设，min_samples=2，则数据集D在OPTICS算法上的执行步骤如下：
索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 核心对象 |
元素 | (1,2) | (2,5) | (8,7) | (3,6) | (8,8) | (7,3) | (4,5) | ㅤ |
核心距离 | 3.16 | 1.41 | 1 | 1.41 | 1 | 3.61 | 1.41 | ㅤ |
第一次可达距离 | inf | 3.16 | 8.6 | 4.47 | 9.21 | 6.08 | 4.24 | 0 |
第二次可达距离 | — | — | 6.32 | 1.41 | 6.70 | 5.38 | 2.0 | 1 |
第三次可达距离 | — | — | 5.09 | — | 5.39 | 5.0 | 1.41 | 3 |
第四次可达距离 | — | — | 4.47 | — | 5.0 | 3.61 | — | 6 |
第五次可达距离 | — | — | 4.12 | — | 5.0(5.1) | — | — | 5 |
第六次可达距离 | — | — | — | — | 1 | — | — | 2 |
输出顺序 | 0 | 1 | 5 | 2 | 6 | 4 | 3 | ㅤ |
可达距离 | inf | 3.16 | 4.12 | 1.41 | 1 | 3.61 | 1.41 | ㅤ |
- 计算所有的核心对象和核心距离，因为 eps 为无穷大，则显然每个样本点都是核心对象。因为 min_samples=2，则每个核心对象的核心距离就是离自己最近样本点到自己的距离（样本点自身也是邻域元素之一），具体如上表所示。
- 随机在 D 中选择一个核心对象，假设选择 0 号元素，将 0 号元素放入有序列表p中，并从 D 中删除。因为 eps = inf，则其他所有样本点都是 0 号元素的密度直达对象，计算其他所有元素到 0 号元素的可达距离（实际就是计算所有元素到 0 号元素的欧氏距离，如表1第一次可达距离），并按可达距离排序，添加到序列seeds中。
- 此时 O 中可达距离最小的元素是 1 号元素，取出 1 号元素放入有序列表p，并从 D 和seeds中删除，因为 1 号元素是核心对象，找到 1 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新seeds（如表1第二次可达距离）。
- 此时seeds中可达距离最小的元素是 3 号元素，取出 3 号元素放入有序列表p，并从 D 和seeds中删除，因为 3 号元素是核心对象，找到 3 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新seeds（如表1第三次可达距离）。
- 此时seeds中可达距离最小的元素是 6 号元素，取出 6 号元素放入有序列表p，并从 D 和seeds中删除，因为 6 号元素是核心对象，找到 6 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新seeds（如表1第四次可达距离）。
- 此时seeds中可达距离最小的元素是 5 号元素，取出 5 号元素放入有序列表p，并从 D 和seeds中删除，因为 5 号元素是核心对象，找到 5 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新seeds（如表1第五次可达距离）。注意本次计算的4号元素到5号元素的可达距离是5.10，大于5.0，因此不更新4号元素的可达距离。
- 此时seeds中可达距离最小的元素是 2 号元素，取出 2 号元素放入有序列表p，并从 D 和seeds中删除，因为 2 号元素是核心对象，找到 2 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新seeds（如表1第六次可达距离）。
- 此时seeds中可达距离最小的元素是 4 号元素，取出 4 号元素放入有序列表p，并从 D 和seeds中删除，因为 D 已空，seeds也已空，程序结束。根据表1，最终的有序列表p的元素索引输出顺序为：0、1、3、6、5、2、4，可达距离如表1最后一行所示。
我们按照最终的输出顺序绘制可达距离图（注意，因为第一个元素没有可达距离，或者说可达距离是无穷大，故图中没有标出 0 号元素的可达距离）：
可以发现，可达距离呈现两个波谷，也即表现为两个簇，波谷越深，表示簇越紧密，只需要在两个波谷之间取一个合适的 eps 分隔值（图中蓝色的直线，例如两个可达距离的平均值），使用 DBSCAN 算法就会聚类为两个簇。即第一个簇的元素为：0、1、3、6、5；第二个簇的元素为：2、4。
算法实现
使用sklearn实现OPTICS算法
使用numpy实现OPTICS算法
- 结果列表决策图（横坐标是处理顺序，纵坐标是该点的可达距离），举个例子，横坐标为： [1,2,3] ，纵坐标为： [5.5,3.6,8.4] 。说明：第一个被处理的点的可达距离为5.5，第二个被处理的点的可达距离为3.6，第三个被处理的点的可达距离为8.4。同时在该图中可以看出，当eps取3时，原数据集可以被分为3个类别（决策图有一个凹槽）。
- 聚类结果可视化图（棕色是离群点）
