在前面介绍的DBSCAN算法中，有两个初始参数E（邻域半径）和minPts(E邻域最小点数)需要用户手动设置输入，并且聚类的类簇结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果，其实这也是大多数其他需要初始化参数聚类算法的弊端。
为了克服DBSCAN算法这一缺点，提出了OPTICS算法（Ordering Points to identify the clustering structure）。OPTICS并不显示的产生结果类簇，而是为聚类分析生成一个增广的簇排序（比如，以可达距离为纵轴，样本点输出次序为横轴的坐标图），这个排序代表了各样本点基于密度的聚类结构。它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类，换句话说，从这个排序中可以得到基于任何参数E和minPts的DBSCAN算法的聚类结果。
定义
OPTICS算法的基础有两点，
- 参数（半径，最少点数）：
一个是输入的参数，包括:半径ε，和最少点数MinPts。
- 定义（核心点，核心距离，可达距离，直接密度可达）：
另一个是相关概念的定义：
核心点的定义，如果一个点的半径内包含点的数量不少于最少点数，则该点为核心点，数学描述即
Nε(P)>=MinPts
在这个基础上可以引出核心距离的定义，即对于核心点，距离其第MinPtsth近的点与之的距离
coreDist(P)={UNDIFED, MinPtsth Distance in N(P),if N(P)<=MinPtselse
可达距离，对于核心点P，O到P的可达距离定义为O到P的距离或者P的核心距离，即公式
reachDist(O,P)={UNDIFED, max(coreDist(P), dist(O,P)),if N(P)<=MinPtselse
O到P直接密度可达，即P为核心点，且P到O的距离小于半径。
算法
OPTICS算法的难点在于维护核心点的直接可达点的有序列表。算法的计算过程如下：
- 输入：数据样本D，初始化所有点的可达距离和核心距离为MAX，半径ε，和最少点数MinPts。
- 1、建立两个队列，有序队列（核心点及该核心点的直接密度可达点），结果队列（存储样本输出及处理次序）
- 2、如果D中数据全部处理完，则算法结束，否则从D中选择一个未处理且未核心对象的点，将该核心点放入结果队列，该核心点的直接密度可达点放入有序队列，直接密度可达点并按可达距离升序排列；
- 3、如果有序序列为空，则回到步骤2，否则从有序队列中取出第一个点；
- 3.1 判断该点是否为核心点，不是则回到步骤3，是的话则将该点存入结果队列，如果该点不在结果队列；
- 3.2 该点是核心点的话，找到其所有直接密度可达点，并将这些点放入有序队列，且将有序队列中的点按照可达距离重新排序，如果该点已经在有序队列中且新的可达距离较小，则更新该点的可达距离。
- 3.3 重复步骤3，直至有序队列为空。
- 4、算法结束。
输出结果
给定半径ε，和最少点数MinPts，就可以输出所有的聚类。
计算过程为：
给定结果队列
- 1、从结果队列中按顺序取出点，如果该点的可达距离不大于给定半径ε，则该点属于当前类别，否则至步骤2；
- 2、如果该点的核心距离大于给定半径ε，则该点为噪声，可以忽略，否则该点属于新的聚类，跳至步骤1；
- 3、结果队列遍历结束，则算法结束。
评论