OPTICS算法是从DBSCAN算法演化而来的基于层次密度的聚类算法，它可以解决DBSCAN算法中的参数敏感问题和不能很好处理数据中带有非均匀密度簇的问题，且OPTICS对参数不是十分敏感

一：OPTICS算法相关定义

（1）相关定义

由于OPTICS算法基于DBSCAN算法，所以以下定义是共用的，这里不再给出具体描述（详见：【数据聚类】第四章第一节1：基于密度算法概述、DBSCAN算法相关概念、定义和算法流程）

• Eps邻域
• 核心对象
• 直接密度可达
• 密度可达
• 密度相连

在OPTICS算法中需要额外引入以下两个定义

• 核心距离（core-distance）：对于$\forall x_p\in D$，若$x_p$为核心对象，那么核心距离可以定义为

c o r e _ d i s t a n c e ( x p ) = { 未 定 义 （ 如 果 x p 不 是 核 心 对 象 ） 使 得 x p 为 核 心 对 象 的 最 小 半 径 （ 其 他 ） core\_distance(x_p{})=

core_distance(xp​)=⎩⎨⎧​未定义（如果xp​不是核心对象）​使得xp​为核心对象的最小半径（其他）​​

• 可达距离（reachability-distance）：对于$\forall x_p,x_q\in D$，$x_q$对$x_p$的可达距离可定义为

r e a c h a b i l i t y _ d i s t a n c e ( x q , x p ) = { 未 定 义 （ 如 果 x p 不 是 核 心 对 象 ） m a x ( c o r e _ d i s t a n c e ( x p ) , d i s t a n c e ( x p , x q ) ) ) （ 其 他 ） reachability\_distance(x_q{},x_p{})=

reachability_distance(xq​,xp​)=⎩⎪⎨⎪⎧​未定义（如果xp​不是核心对象）​max(core_distance(xp​),distance(xp​,xq​)))（其他）​​

如下图，MinPts设置为5

• $x_p$是一个核心对象
• $x_p$的核心距离为core_distance($x_p$)
• 点$x_{q1}$到点$x_p$的可达距离是core_distance($x_p$)
• 点$x_{q2}$到点$x_p$的可达距离是$r_2$

（2）簇结构可视化

基于上述定义，OPTICS算法在执行过程中可以生成一个以可达距离为纵轴，以数据点输出次序为横轴的坐标图，从中可以清晰观察到各个数据点基于密度的聚簇结构

如下图所示，可以通过寻找每个陡峭下降区域和陡峭上升区域所构成的凹陷来发现各个簇的对应结果

• 例如左图数据集中×形簇对应右图第一个陡峭下降区域和陡峭上升区域所构成的凹陷处

二：算法流程

OTTICS算法和DBSCAN算法一样，仍然需要用户输入Eps和MinPts，但是它们仅仅起到辅助作用，其变化并不会对最终结果造成大的影响。算法流程如下

如下，OPTICS算法首先会进行初始化，然后进入主循环，在循环过程中

• 对于任意一个未标记的数据点$x_p$，OPTICS将其标记为已访问，然后将它输出到序列order中，清空当前的种子序列seeds，确定$x_p$的$\xi$邻域
• 如果$x_p$是一个核心对象，这时OPTICS会计算$x_p$的核心距离，并利用Update函数对种子序列及可达距离进行更新
• 接着OPTICS会依次从种子序列中拿出一个未访问的数据点$x_q$，将其标记为已访问，把它放到输出序列中，确定其$\xi$邻域，如果$x_q$为核心对象，OPTICS就会再次利用Update函数对种子序列和可达距离进行更新
• 这个过程会不断循环直到所有数据点都被访问完为止

Update函数是OPTICS中用来更新种子序列和各个数据点可达距离的函数，对于任意一个未访问数据点$x_j\in N_{\xi }(x_i)$，首先计算$x_j$到$x_i$的可达距离

• 如果$x_j$的可达距离没有定义：那么就将$x_j$到$x_i$的可达距离定义为$x_j$的可达距离，并按照可达距离的大小将$x_j$插入到种子序列中
• 如果$x_j$的可达距离已经存在且$x_j$到$x_i$的可达距离小于$x_j$的可达距离：那么将$x_j$的可达距离替换为$x_j$到$x_i$的可达距离，并按照可达距离的大小对种子序列进行升序排序