开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
OPTICS(Ordering points to identify the clustering structure)是一基于密度的聚类算法，OPTICS算法是DBSCAN的改进版本，因此OPTICS算法也是一种基于密度的聚类算法。在DBCSAN算法中需要输入两个参数： 和 MinPts，选择不同的参数会导致最终聚类的结果千差万别，因此DBCSAN对于输入参数过于敏感。OPTICS算法的提出就是为了帮助DBSCAN算法选择合适的参数，降低输入参数的敏感度。OPTICS主要针对输入参数过敏感做的改进，OPTICS虽然和DBSCNA的输入参数一样，但该算法对 输入不敏感（一般将 固定为无穷大），同时该算法中并不显式的生成数据聚类，只是对数据集合中的对象进行排序，得到一个有序的对象列表，通过该有序列表，可以得到一个决策图，通过决策图可以不同 参数的数据集中检测簇集，即：先通过固定的MinPts无穷大的 得到有序列表，然后得到决策图，通过决策图可以知道当 取特定值时数据的聚类情况。
由于OPTICS算法是DBSCAN算法的一种改进，因此有些概念是共用的，比如： -邻域，核心对象，密度直达，密度可达，密度相连等，这些概念可直接查看往期的DBSCAN算法讲解，这里不再赘述。下面仅介绍与OPTICS相关的定义
假设样本集是 ，在DBSCAN定义的基础上，OPTICS在引入了两个算法需要的定义：
核心距离（core-distance）：样本 ，对于给定的和MinPts，使得成为核心点的最小邻域半径称为的核心距离，其数学表达如下：代表集合 中与节点第i近邻的节点（也就是距离第i小的），如表示 中与 最近的节点。核心距离表达式为：
举个例子说明一下， 假设有5个样本点如下：
以及初始化半径R和最小MinPts为3，即在半径R内，如果有3个或者3个以上的点，即为核心点。
选择第一个点p，如下图黑色的点，并以它为圆心作一个半径为R的圆，如下图（左图）：
在该圆内，共有4个点，所以该黑点为核心点。该核心点有三个邻居点，如上右图的淡红色的点。接着以该核心点为圆心，找到一个最小半径（这个最小半径一般小于前面给出的R）的圆，使得该圆内至少包含3个点，则该半径则为该核心点的核心距离。
换种说法就是：当前核心点 的邻域中，与核心点距离升序排第位的样本点，与 的距离作为的核心距离（-1是因为邻域包含了p本身），这种定义可以在后续编程中有用。OPTICS一开始会设定，所以所有点都是核心点，所以的计算也不需要区分条件，除非你数据集的总样本量 <（但这有点扯淡了）。
可达距离（reachability-distance）：设 ,对于给定的和 ， y 关于x的可达距离定义为：
实际上式中隐含了可达距离有两个前提条件：一是x是核心点，二是y可以从x直接密度可达。rd的含义是比较核心距离和y到x的距离谁大，就将其作为可达距离。
核心距离和可达距离这里可能会不太好理解，可参考下图，
假设为6mm，MinPts为5，则p为核心点不难判定，核心距离就是刚好让p成为满足有5个点的核心点的最小半径，显然，当半径不断增大，直到3时，正好框进去5个点使p成为了核心点，因此核心距离就是3；r到p的可达距离，是比较p核心距离3和r到p的距离（图中表示的是小于3的）大小，取大者，即3。而q到p的可达距离同样为比较p核心距离3和q到p的距离（图中表示的是7）大小，取大者即7。这样讲应该可以理解了吧。
有了上述定义后，可根据可达距离对样本点进行排序，这也是OPTICS算法中Ordering Points的由来。具体过程如下
\1. 定义两个队列，有序队列和结果队列，有序队列用于存储核心点及其密度直达点集合, 并按照可达距离升序排列；结果队列用于存储样本点的输出次序；有序队列中的点为待处理样本，结果队列中的点为处理之后的样本；
\2. 选取一个未处理的核心点, 将其放入结果队列，同时计算邻域内样本点的可达距离，按照可达距离升序将样本点依次放入有序队列；
\3. 从有序队列中提取第一个样本，如果为core point, 则计算可达距离，将可达距离最小的点放入结果队列，如果不是core point, 则跳过该点，选取新的core point, 重复步骤2；
\4. 不断迭代第二步和第三步，直到所有样本点都处理完毕，然后输出结果队列中的样本点及其可达距离。
处理完毕之后，根据样本的输出顺序和可达距离，可以绘制如下所示的柱状图，其中不同的峰谷对应不同的类别， 红色表示噪声点。
由于这里理解有点困难，加个小实例说明一下。
假设样本数据集为：D = {[1, 2], [2, 5], [8, 7], [3, 6], [8, 8], [7, 3], [4,5]}，为了更好地标识索引，我们以图形显示数据如下：
假设，则数据集D具体绘图步骤如下：
（1）计算所有的核心对象和核心距离，因为刚开始为inf无穷大，则显然每个样本点都是核心对象。因为 MinPts=2，则每个核心对象的核心距离就是离自己最近样本点到自己的距离（样本点自身也是邻域元素之一），具体如下表所示。
随机在 D 中选择一个核心对象，假设选择 0 号元素，将 0 号元素放入结果序列R中，并从 D 中删除。因为 eps = inf，则其他所有样本点都是 0 号元素的密度直达对象，计算其他所有元素到 0 号元素的可达距离（实际就是计算所有元素到 0 号元素的欧氏距离，如表1第一次可达距离），并按可达距离排序，添加到有序序列 O 中。
此时 O 中可达距离最小的元素是 1 号元素，取出 1 号元素放入 R ，并从 D 和 O 中删除，因为 1 号元素是核心对象，找到 1 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新 O（如表第二次可达距离）。
此时 O 中可达距离最小的元素是 3 号元素，取出 3 号元素放入 R ，并从 D 和 O 中删除，因为 3 号元素是核心对象，找到 3 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新 O（如表第三次可达距离）。
此时 O 中可达距离最小的元素是 6 号元素，取出 6 号元素放入 R ，并从 D 和 O 中删除，因为 6 号元素是核心对象，找到 6 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新 O（如表第四次可达距离）。
此时 O 中可达距离最小的元素是 5 号元素，取出 5 号元素放入 R ，并从 D 和 O 中删除，因为 5 号元素是核心对象，找到 5 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新 O（如表第五次可达距离）。注意本次计算的4号元素到5号元素的可达距离是5.10，大于5.0，因此不更新4号元素的可达距离。
此时 O 中可达距离最小的元素是 2 号元素，取出 2 号元素放入 R ，并从 D 和 O 中删除，因为 2 号元素是核心对象，找到 2 号元素在 D 中的所有密度直达对象（剩余的所有样本点），并计算可达距离，同时更新 O（如表第六次可达距离）。
此时 O 中可达距离最小的元素是 4 号元素，取出 4 号元素放入 R ，并从 D 和 O 中删除，因为 D 已空，O 也已空，程序结束。根据表1，最终的结果序列 R 的元素索引输出顺序为：0、1、3、6、5、2、4，可达距离如表最后一行所示。
我们按照最终的输出顺序绘制可达距离图（注意，因为第一个元素没有可达距离，或者说可达距离是无穷大，故图中没有标出 0 号元素的可达距离）：
可以发现，可达距离呈现两个波谷，也即表现为两个簇，波谷越深，表示簇越紧密，只需要在两个波谷之间取一个合适的 eps 分隔值（图中蓝色的直线，例如两个可达距离的平均值），其实使用 DBSCAN 算法就会聚类为两个簇。即第一个簇的元素为：0、1、3、6、5；第二个簇的元素为：2、4。
输入：样本集，MinPts参数
待求：类别，邻域参数eps
步骤：
（1）创建两个队列，有序队列和结果队列。
1）有序队列用于存储core points及其密度直达points, 并按可达距离升序排列。有序队列中的points为待处理样本；
2）结果队列用于存储样本点的输出次序。结果队列中的points为处理之后的样本；
（2）选取一个未处理的core point, 将其放入结果队列，同时计算邻域内样本点的可达距离，按照可达距离升序将样本点依次放入有序队列。
（3） 若有序队列为空，则回到步骤2（重新选取处理数据）。否则，从有序队列中提取第一个样本，如果为core point, 则计算可达距离，将可达距离最小的点放入结果队列。如果不是core point, 则重复步骤2；
1）如果有序队列中已经存在直接密度可达点，如果此时新的可达距离小于旧的可达距离，则用新可达距离取代旧可达距离，有序队列重新排序(因为一个对象可能有多个核心对象可达)；
2）如果有序队列中不存在该直接密度可达样本点，则插入该点，并对有序队列重新排序；
（4）迭代2，3，直到数据集中所有点都处理完成，则算法结束，输出结果队列中有序样本点。
已知条件 :
① 数据集 :将如下含有 16 个样本的数据集 , 进行聚类分析 ;
② 数据样本的属性 :该数据样本是 二维数据 , 有两个属性值 , 可以在一个平面进行模拟 , 一个是 x 轴数据 , 一个是 y轴数据 ;
③ 聚类参数 :-邻域 半径是44 ,MinPts = 3;
首先由人进行的判断分析肉眼判断 , 应该分成两层分组：内层分组 ，如下图 绿色的 圈代表的聚类 ；外层分组 ：如下图红色的圈代表的聚类。
选择样本 A开始分析 :样本 A 的核心距离就是 ε ; 将样本 A 拿出来 , 放入族序与可达距离构成的坐标系 : x 轴是族序 , y 轴是可达距离 ;
其中 A 由于是第一个处理的样本 , 其只有核心距离 , 没有可达距离 , 因此 A 的可达距离设置成 正无穷大 ;
判定 样本 A 是否是核心对象 : 判定 ε -邻域 中分布的样本数量是否大于等于MinPts = 3阈值个数 , 也就是除 A 外 , 应该还有另外 2 个样本 , 这里假设发现其 ε -邻域 中还有样本 B 和样本I , 因此样本 A 是核心对象 ;
样本 A 是核心对象 :执行下面一系列流程 ;
① 提取样本 :提取所有 从A 样本触发 , 密度可达的 数据样本对象 , 即 B , I 两个样本;
② 计算核心距离 :计算 样本 A 的核心距离 , 结果是 40 ;
③ 计算 可达距离 :计算提取的B , I 两个样本对象的可达距离 , 都是 40 ;
④ 待处理队列 :将计算好核心距离、可达距离的样本放入待处理队列 Q 中 ;
B 表示样本B, 40表示样本A到样本B的可达距离是40 ;
I 表示 样本 I, 40表示样本A 到 样本的可达距离是 40。
选择样本 B 分析 :从Q待处理队列 中 , 选择一个 可达距离 最小的样本 B 继续进行进一步的扩展 , 这两个样本可达距离都是 40, 任意选一个即可 , 选择 B;
此时将 B从待处理队列Q中移出 , 只剩下 I 样本 , 此时的待处理队列是 :
将样本 B拿出来 , 放入以下族序 -可达距离坐标系中 , 其中样本 B可达距离是 40, 其对应的 y轴可达距离是 40 , x 轴族序是 2;
判定样本 B是否是核心对象 :判定ε-邻域 中分布的样本数量是否大于等于MinPts = 3阈值 个数 , 也就是除 B外 , 应该还有另外 2个样本 , 假设通过距离计算发现其 ε -邻域 中还有 样本 A 和样本C , 则样本B 是核心对象;
样本 B B B 是核心对象 : 执行下面一系列流程 ;
① 提取样本 :提取所有 从 B样本触发 , 密度可达的数据样本对象 , 即 C , A 两个样本 ; 但是样本 A 已经处理过了 , 就不再处理样本A , 只处理样本 C ;
② 计算核心距离 :计算样本 B的核心距离 , 从 B 到 C的距离 , 结果是40 ;
**③ 计算可达距离 :**计算提取的 C 样本对象的可达距离 , 是40 ;
④ 待处理队列 :将计算好 核心距离 可达距离 的样本放入待处理队列 Q中 ;
C 表示样本C , 40 表示 样本 C到 样本 B 的可达距离是40 ;
(I,40) 中的 I 表示 样本 I , 40 表示 样本 A 到 样本I 的 可达距离是40 ;
选择样本 I分析 :从Q待处理队列中 , 选择一个 可达距离 最小的样本 I 继续进行 进一步的 扩展 , 这两个样本可达距离都是40 , 任意选一个即可 , 选择I;
此时将I从待处理队列Q中移出 , 只剩下 C 样本 , 此时的待处理队列是 :
将样本I拿出来 , 放入族序 - 可达距离坐标系，样本I可达距离是40 , 其对应的 y轴可达距离是40 , x 轴族序是 3 ;
判定样本I是否是核心对象 :判定数据样本I是否是核心对象 , 通过判定其 ε-邻域 中分布的样本数量是否大于等于MinPts=3 阈值 个数 , 也就是除I外 , 应该还有另外2 个样本 , 这里发现其 ε-邻域 中还有样本 A , J , K , L , M , R, 因此 样本I是核心对象 ;
样本I是核心对象 :执行下面一系列流程 ;
① 提取样本 :提取所有从I样本出发 , 密度可达的数据样本对象 , 即 A , J , K , L , M , R 样本 ; 但是样本 A已经处理过了 , 就不再处理样本 A, 只处理样本 J , K , L , M , R;
② 计算核心距离 :计算样本I的核心距离 ;
③ 计算 可达距离 :计算提取的 J , K , L , M , R 样本对象的可达距离 , 分别是 20 , 20 , 31 , 40 , 43;
④ 待处理队列 :将计算好 核心距离 可达距离 的样本放入 待处理队列 Q中 ;
(J,20) 中的 J 表示 样本 J , 20 表示 样本I到 样本 J 的 可达距离是 20 ;
选择样本 J分析 :从Q待处理队列中 , 选择一个 可达距离 最小的样本 J继续进行 进一步的 扩展 , 这个样本可达距离是 20 20 20 , 在待处理队列中最小 , 选择 样本 J ;
此时将 J 从待处理队列Q中移出 , 剩下 K , L , C , M , R样本 , 此时的待处理队列是 :
将 样本 J拿出来 , 放入族序 - 可达距离 坐标系,其中样本J 可达距离是20 , 其对应的 y轴可达距离是20 , x 轴族序是 4 ;
判定样本 J是否是核心对象 :判定数据样本 J 是否是核心对象 , 通过判定其 ε-邻域 中分布的样本数量是否大于等于MinPts=3 阈值 个数 , 也就是除J 外 , 应该还有另外 2 个样本 , 这里发现其 ε-邻域 中还有 样本 I , L , K , R , M , P , 因此 样本 J 是核心对象 ;
样本 J是核心对象 :*执行下面一系列流程 ;
① 提取样本 :提取所有 从 J样本出发 , 密度可达的 数据样本对象 , 即 I , L , K , R , M , P 样本 ; 但是样本I已经处理过了 , 就不再处理样本I, 只处理样本 L , K , R , M , P;
② 计算核心距离 :计算 样本 J的核心距离 ;
③ 计算 可达距离 :计算 提取的 L , K , R , M , P样本对象的 可达距离 , 分别是 19 , 20 , 21 , 30 , 31 ;
④ 待处理队列 :将计算好 核心距离 可达距离 的样本放入 待处理队列 Q 中 ;
( L , 19 ) 中的 L表示 样本L , 19 表示 样本 J到 样本L 的 可达距离是19 ;
选择样本 L 分析 :从Q待处理队列中 , 选择一个 可达距离 最小的样本 L 继续进行 进一步的 扩展 , 这个样本可达距离是19 , 在待处理队列中最小 , 选择 样本 L ;
此时将 L 从待处理队列Q中移出 , 剩下 K , R , M , P , C样本 , 此时的待处理队列是 :
将 样本 L 拿出来 , 放入族序 - 可达距离坐标系,其中样本 L可达距离是19 , 其对应的 y轴可达距离是19 , x 轴族序是 5 ;
判定 样本 L 是否是核心对象 :判定数据样本 L 是否是核心对象 , 通过判定其 ε-邻域 中分布的样本数量是否大于等于MinPts=3 阈值 个数 , 也就是除 L 外 , 应该还有另外2 个样本 , 这里发现其 ε-邻域 中还有 样本 I , J , M , K , R , P , N , 因此 样本 L 是核心对象 ;
样本 L 是核心对象 :执行下面一系列流程 ;
① 提取样本 :提取所有 从 L 样本出发 , 密度可达的 数据样本对象 , 即 I , J , M , K , R , P , N 样本 ; 但是样本 I , J 已经处理过了 , 就不再处理样本 I , J , 只处理样本 M , K , R , P , N ;
② 计算核心距离 :计算 样本 L 的核心距离 ;
③ 计算 可达距离 :计算 提取的 M , K , R , P , N样本*对象的 可达距离 , 分别是 18 , 18 , 20 , 21 , 35 ;
④ 待处理队列 :将计算好 核心距离 可达距离 的样本放入 待处理队列 Q 中 ;
(M,18) 中的 M 表示 样本 M , 18表示 样本 L 到 样本M 的 可达距离是18 ;
......
第 16 次迭代之后 ,Q待处理队列清空 , 所有的样本都放到了族序 - 可达距离坐标系中，如下图所示;
此时已经将每个样本的 族序 , 以及其可达距离表示在了坐标系中 ，可以开始进行聚类了 。
**（1）ε 太小无意义聚类分析 **
选择如下图所绘制的 红色线代表的 ε值进行聚类 , 没有任何意义 , 距离太小了 , 没有出现波谷，以至于所有的样本都不能密度可达 ; 所有的样本都被标记成噪音了 。
（2） 两个聚类分组的情况 :
下图中 , 绘制的红色线的 y轴值代表的 ε, 此时按照此 ε进行聚类 , 凹形波谷的分在一组聚类中 , 如
聚类分组 1 :{ J , L , M , K , N , R , P } ;
聚类分组 2 :{ D , F , G , E } ;
其它的 A , B , I , C , H样本 都被 标记成噪音处理了 ;
（3） 一个聚类分组的情况 :
聚类分析 :下图中 , 绘制的红色线的 y轴值代表的 ε, 此时按照此 ε = 44进行聚类 , **只有一个凹形波谷，所有样本分在一组聚类中 , 如
聚类分组 1:{ B , I , J , L , M , K , N , R , P , C , D , F , G , E , H } ；