密度聚类 OPTICS：通过点排序识别聚类结构

OPTICS：通过点排序识别聚类结构

 

OPTICS聚类算法原理

基础

OPTICS聚类算法是基于密度的聚类算法，全称是Ordering points to identify the clustering structure，目标是将空间中的数据按照密度分布进行聚类，其思想和DBSCAN非常类似，但是和DBSCAN不同的是，OPTICS算法可以获得不同密度的聚类，直接说就是经过OPTICS算法的处理，理论上可以获得任意密度的聚类。因为OPTICS算法输出的是样本的一个有序队列，从这个队列里面可以获得任意密度的聚类。

定义

OPTICS算法的基础有两点，

参数（半径，最少点数）：
一个是输入的参数，包括:半径εε，和最少点数MinPtsMinPts。

定义（核心点，核心距离，可达距离，直接密度可达）：
另一个是相关概念的定义： 

算法

OPTICS算法的难点在于维护核心点的直接可达点的有序列表。算法的计算过程如下：

输入：数据样本D，初始化所有点的可达距离和核心距离为MAX，半径εε，和最少点数MinPtsMinPts。

1、建立两个队列，有序队列（核心点及该核心点的直接密度可达点），结果队列（存储样本输出及处理次序）

2、如果D中数据全部处理完，则算法结束，否则从D中选择一个未处理且未核心对象的点，将该核心点放入结果队列，该核心点的直接密度可达点放入有序队列，直接密度可达点并按可达距离升序排列；
3、如果有序序列为空，则回到步骤2，否则从有序队列中取出第一个点；
3.1 判断该点是否为核心点，不是则回到步骤3，是的话则将该点存入结果队列，如果该点不在结果队列；
3.2 该点是核心点的话，找到其所有直接密度可达点，并将这些点放入有序队列，且将有序队列中的点按照可达距离重新排序，如果该点已经在有序队列中且新的可达距离较小，则更新该点的可达距离。
3.3 重复步骤3，直至有序队列为空。
4、算法结束。

输出结果

给定半径εε，和最少点数MinPtsMinPts，就可以输出所有的聚类。

计算过程为：

给定结果队列

1、从结果队列中按顺序取出点，如果该点的可达距离不大于给定半径εε，则该点属于当前类别，否则至步骤2；
2、如果该点的核心距离大于给定半径εε，则该点为噪声，可以忽略，否则该点属于新的聚类，跳至步骤1；
3、结果队列遍历结束，则算法结束。
 

 

OPTICS的核心思想无外乎这两句话 
1、较稠密簇中的对象在簇排序中相互靠近； 
2、一个对象的最小可达距离给出了一个对象连接到一个稠密簇的最短路径。 
这两句话，可能一时半会儿体会不到它的意义。

那我们先来看看具体咋做

算法：OPTICS 
输入：样本集D, 邻域半径E, 给定点在E领域内成为核心对象的最小领域点数MinPts 
输出：具有可达距离信息的样本点输出排序 
方法： 
1、创建两个队列，有序队列和结果队列。（有序队列用来存储核心对象及其该核心对象的直接可达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次序。你可以把有序队列里面放的理解为待处理的数据，而结果队列里放的是已经处理完的数据）； 
2、如果所有样本集D中所有点都处理完毕，则算法结束。否则，选择一个未处理（即不在结果队列中）且为核心对象的样本点，找到其所有直接密度可达样本点，如过该样本点不存在于结果队列中，则将其放入有序队列中，并按可达距离排序； 
3、如果有序队列为空，则跳至步骤2（重新选取处理数据）。否则，从有序队列中取出第一个样本点（即可达距离最小的样本点）进行拓展，并将取出的样本点保存至结果队列中(如果它不存在结果队列当中的话)。然后进行下面的处理。 
3.1.判断该拓展点是否是核心对象，如果不是，回到步骤3（因为它不是核心对象，所以无法进行扩展了。那么就回到步骤3里面，取最小的。这里要注意，第二次取不是取第二小的，因为第一小的已经放到了结果队列中了，所以第二小的就变成第一小的了。）。如果该点是核心对象，则找到该拓展点所有的直接密度可达点； 
3.2.判断该直接密度可达样本点是否已经存在结果队列，是则不处理，否则下一步； 
3.3.如果有序队列中已经存在该直接密度可达点，如果此时新的可达距离小于旧的可达距离，则用新可达距离取代旧可达距离，有序队列重新排序(因为一个对象可能直接由多个核心对象可达，因此，可达距离近的肯定是更好的选择)； 
3.4.如果有序队列中不存在该直接密度可达样本点，则插入该点，并对有序队列重新排序； 
4、迭代2，3。 
5、算法结束，输出结果队列中的有序样本点。

认真学了了DBSCAN算法，肯定会对OPTICS算法感到熟悉。因为这两个算法的推进过程基本上是完全一样的。

OK，对照算法，再回想一下我说的那两句话。

1、较稠密簇中的对象在簇排序中相互靠近； 
2、一个对象的最小可达距离给出了一个对象连接到一个稠密簇的最短路径。

是不是体会更深刻了一些？ 
OPTICS全称是Ordering points to identify the clustering structure 。翻译过来就是，对点排序以此来确定簇结构。实际上，我觉得这个名字就点出了这个算法很多东西了。 
最后，参考Wiki上的图，来具体感受下OPTICS最后跑出来的结果。 

多的不说，直说下面几点 
1、X轴代表OPTICS算法处理点的顺序，y轴代表可达距离。 
2、簇在坐标轴中表述为凹陷（山谷？？Valley），并且凹陷越深，簇越紧密 
3、黄色代表的是噪声，它们不形成任何凹陷。

在最开始就已经说了，OPTICS是用的广泛的参数。 
当你需要提取聚集的时候，参考Y轴和图像，自己设定一个阀值就可以提取聚集了。这里将阀值设为0.1就挺合适的。

再来一张凹陷明显的 

 

 

 

 

 

n对于真实的，高维的数据集合而言，参数的设置通常是依靠经验，难以确定。 n绝大多数算法对参数值是非常敏感的：设置的细微不同可能导致差别很大的聚类结果。 nOPTICS算法通过对象排序识别聚类结构。 nOPTICS没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇排序。 n这个次序代表了数据的基于密度的聚类结构。较稠密中的对象在簇排序中相互靠近。