在前面介绍的DBSCAN算法中，有两个初始参数Eps（邻域半径）和MinPts（E邻域最小点数）需要用户手动设置输入，并且聚类的类簇结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果，其实这也是大多数其他需要初始化参数聚类算法的弊端。

为了克服DBSCAN算法这一缺点，提出了OPTICS算法（Ordering Points to identify the clustering structure）。OPTICS并不显示的产生结果类簇，而是为聚类分析生成一个增广的簇排序（比如，以可达距离为纵轴，样本点输出次序为横轴的坐标图），这个排序代表了各样本点基于密度的聚类结构。它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类，换句话说，从这个排序中可以得到基于任何参数Eps和MinPts的DBSCAN算法的聚类结果。

5.4.2.1　相关定义

（1）核心距离：对象a的核心距离实质是a成为核心对象的最小Eps。如果a不是核心对象，那么a的核心距离没有任何意义。

（2）可达距离：对象b到对象a的可达距离是指a的核心距离和a与b之间距离之间的较大值。如果a不是核心对象，a和b之间的可达距离没有意义。

例如：假设邻域半径为Eps＝1，Minpts＝3，则存在点A（2，3），B（2，4），C（1，4），D（1，3），E（2，2），F（3，2）。

点A为核心对象，在A的邻域中有点｛A，B，C，D，E，F｝，其中A的核心距离为Eps＝1，因为在点A的Eps邻域中有点A，B，D，E，点的个数＞3；

点F到核心对象点A的可达距离为因为A到F的距离大于点A的核心距离Eps＝1。

如图5.5所示。

图5.5　点F到核心对象点A的可达距离示意图

5.4.2.2　算法描述

OPTICS算法额外存储了每个对象的核心距离和可达距离。基于OPTICS产生的排序信息来提取类簇。(www.daowen.com)

算法描述如下：

算法：OPTICS

输入：样本集S，邻域半径Eps，给定点在Eps邻域内成为核心对象的最小邻域点数MinPts

输出：具有可达距离信息的样本点输出排序

步骤：

（1）创建两个队列，有序队列和结果队列。（有序队列用来存储核心对象及其该核心对象的直接可达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次序）

（2）如果所有样本集S中所有点都处理完毕，则跳至步骤（4），算法结束。否则，选择一个未处理（即不在结果队列中）且为核心对象的样本点，找到其所有直接密度可达样本点，如过该样本点不存在于结果队列中，则将其放入有序队列中，并按可达距离排序。

（3）如果有序队列为空，则跳至步骤（2），否则，从有序队列中取出一个样本点（即可达距离最小的样本点）进行拓展，并将取出的样本点保存至结果队列中（如果它不存在结果队列）。

①判断该拓展点是否是核心对象，如果不是，回到步骤（3），否则找到该拓展点所有的直接密度可达点。

②判断该直接密度可达样本点是否已经存在结果队列，是则不处理，否则下一步。

③如果有序队列中已经存在该直接密度可达点，并且此时新的可达距离小于旧的可达距离，则用新可达距离取代旧可达距离，有序队列重新排序。

（4）算法结束，输出结果队列中的有序样本点。

筛选出数据集中的核心对象，然后计算每个核心对象的核心距离。进而执行算法，输出结果。