OPTICS聚类算法是基于密度的聚类算法，全称是Ordering points to identify the clustering structure。提到基于密度的聚类算法，应该很快会想到前面介绍的DBSCAN聚类算法，事实上，OPTICS也是为了优化DBSCAN而出现的。
一、原理
在DBSCAN算法中，有两个比较重要的参数：邻域半径 _eps_和核心对象的最小邻域样本数 _min_samples，_选择不同的参数会导致最终聚类的结果千差万别，而在高维数据中，两个参数的联合调参也不是一件容易的事。OPTICS算法的提出就是为了帮助DBSCAN算法选择合适的参数，降低输入参数的敏感度。实际上，OPTICS并不显式的生成数据聚类结果，只是对数据集中的对象进行排序，得到一个有序的对象列表，通过该有序列表，可以得到一个决策图，通过决策图可以选择不同的 _eps_参数进行DBSCAN聚类。在继续阅读下面的内容之前，需要先了解DBSCAN的相关内容，因为本文的部分概念来自于DBSCAN。
在DBSCAN的基础上，OPTICS定义了两个新的距离概念：
（1）核心距离
对于一个给定的核心对象X，使得X成为核心对象的最小邻域距离 r 就是X的核心距离。这句话乍一看有点绕，其实仔细读两遍就明白了，假如在DBSCAN中我们定义 eps = 1.2 和 min_samples=5，X在eps = 1.2的邻域内有8个样本点，则X是核心对象，但是我们发现距离X最近的第5个点和X的距离是0.8，那么核心对象 X 的核心距离就是 0.8，显然每个核心对象的核心距离并不都是相同的。参考图1，注意在计算 _min_samples_的时候，一般也包括样本点自身，所以只需在P点eps邻域内找到7个点，那么P点就是核心点。
（2）可达距离
如果X是核心对象，则对象 Y 到对象 X 的可达距离就是Y到X的欧氏距离和X的核心距离的最大值，如果X不是核心对象，则Y和X之间的可达距离就没有意义（不存在可达距离），显然，数据集中有多少核心对象，那么 Y 就有多少个可达距离。在下文介绍 API 的时候，我们会介绍在OPTICS中，一般默认设置 eps 为无穷大，即只要数据集的样本数不少于 _min_samples，_那么任意一个样本点都是核心对象，即都有核心距离，且任意两个对象之间都存在可达距离。
图1
1.1 算法描述
OPTICS的原理并不复杂，只不过大多数介绍资料都喜欢列举一些广义的算法流程或者伪代码，虽然满足算法介绍的严谨性，但是阅读起来不免显得晦涩难懂，没有阅读的欲望。因此，和之前的文章一样，本文也是先介绍OPTICS的标准算法流程，然后再以案例的形式介绍流程的具体执行逻辑，如果算法流程不能一下子理解的话，可以先跳过直接看后面的案例，然后再回来看标准流程。
OPTICS算法流程：
- 已知数据集 D，创建两个队列，有序队列O和结果队列R（有序队列用来存储核心对象及其该核心对象的密度直达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次序。可以把有序队列里面放的理解为待处理的数据，而结果队列里放的是已经处理完的数据）。
- 如果D中所有点都处理完毕或者不存在核心点，则算法结束。否则，选择一个未处理（即不在结果队列R中）且为核心对象的样本点 p，首先将 p 放入结果队列R中，并从D中删除 p。然后找到 D 中 p 的所有密度直达样本点 x，计算 x 到 p 的可达距离，如果 x 不在有序队列 O 中，则将 x 以及可达距离放入 O 中，若 x 在 O 中，则如果 x 新的可达距离更小，则更新 x 的可达距离，最后对 O 中数据按可达距离从小到大重新排序。
- 如果有序队列 O 为空，则回到步骤2，否则取出 O 中第一个样本点 y（即可达距离最小的样本点），放入 R 中，并从 D 和 O 中删除 y。如果 y 不是核心对象，则重复步骤 3（即找 O 中剩余数据可达距离最小的样本点）；如果 y 是核心对象，则找到 y 在 D 中的所有密度直达样本点，并计算到 y 的可达距离，然后按照步骤2将所有 y 的密度直达样本点更新到 O 中。
- 重复步骤2、3，直到算法结束。最终可以得到一个有序的输出结果，以及相应的可达距离。
已知样本数据集为：D = {[1, 2], [2, 5], [8, 7], [3, 6], [8, 8], [7, 3], [4,5]}，为了更好地标识索引，我们以表格标识数据如下：
图2
表1
索引 0 1 2 3 4 5 6 核心对象 元素
(1, 2)(2, 5)(8, 7)(3, 6)(8, 8)(7, 3)(4, 5)
核心距离
3.161.411.01.411.03.611.41
第一次可达距离inf 3.16
8.604.479.216.084.240
第二次可达距离
1.41 第四次可达距离
4.12
—
5.0
(5.10)
1.0
Original: https://blog.csdn.net/haveanybody/article/details/113782209
Author: 大白兔黑又黑
Title: 机器学习笔记（十一）聚类算法OPTICS原理和实践
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/560790/
转载文章受原作者版权保护。转载请注明原作者出处！