OPTICS 算法 两个阶段

---

第一阶段 生成族序 :

主要工作 : 计算 每个 数据集样本 对象 的 核心距离 与 可达距离 , 目的是生成 族序 ;

族序 : 处理 数据集样本 时 , 样本对外扩展的顺序 ;

核心距离 : 是使得 $O$ 能成为 核心对象 的 最小距离 , 取其半径范围内 恰好 有 MinPts个 样本 的 半径值 $\varepsilon$ 作为其核心距离 ;

可达距离 : 样本 $O$ 与样本 $p$ 之间的可达距离是 , 核心距离 与 欧几里得距离 的 较大的值 ;

第二阶段 聚类分组 :

① 使用族序信息 : 使用第一阶段 生成的 数据集样本的 族序信息 ;

② 聚类分组 : 主要是选择一个核心样本 , 然后向外扩展 , 划分聚类分组 ;

OPTICS 算法 第一阶段 生成族序

---

1 . 输入算法参数 : 算法开始时 , 需要输入两个参数 ;

① 参数一 : $\varepsilon$ 参数 , 是 $\varepsilon$-邻域 的 半径 ;

② 参数二 : MinPts 参数 , 是 $\varepsilon$-邻域中要求的含有的最低样本个数 , 即阈值 ;

2 . 选择样本 : 随机选择一个数据样本 $p$ ;

3 . 判定核心对象 : 判定数据样本 $p$ 是否是核心对象 , 通过判定其 $\varepsilon$-邻域 中分布的样本数量是否大于等于 MinPts 阈值 个数 , 也就是其中的样本分布达到一定的密度 ;

4 . 如果 $p$ 是核心对象 :

① 提取样本 : 提取所有 从 $p$ 样本触发 , 密度可达的 数据样本对象 ;

② 计算 核心距离 与 可达距离 : 计算 提取的所有的样本对象的 核心距离 与 可达距离 ;

③ 待处理队列 : 将计算好 核心距离 可达距离 的样本放入 待处理队列 $Q$ 中 ;

5 . 如果 $p$ 是边界对象 ( 非核心对象 ) : 不进行任何处理 ;

6 . 选择样本 : 从 $Q$ 待处理队列中 , 选择一个 可达距离 最小的样本 $q$ 继续进行 进一步的 扩展 , 进行 $3.4.5.6$ 步骤的循环迭代 , 遇到符合要求的 核心对象 , 放入 $Q$ 待处理队列 , 遇到不符合要求的边界对象 , 不做任何处理 ;

7 . 迭代要求及算法终止条件 : 所有的样本全部被处理过 , 都在待处理队列 $Q$ 清空时 , 终止迭代 ;

待处理队列样本的 核心距离 与 可达距离

---

1 . 样本的两个距离 : 在上面的待处理队列 $Q$ 中 , 每个样本对象 都有一个 核心距离 和 可达距离 ;

2 . 样本 的 核心距离 : 这个距离是固定不变的 , 只要数据集是同一个 , 那么每个 样本点 的核心距离 是固定的 ;

3 . 样本 的 可达距离 ( 实时更新 ) : 每次提取样本时 , 都基于一个样本 $p$ 计算与另外 所有的 密度可达 的样本的 可达距离 , 基本每次都要重新计算 , 这个可达距离每次迭代 , 都要修改一次 ;

OPTICS 算法 第二阶段 数据准备

---

1 . 第一阶段生成的数据 :

① 族序 : 处理 数据集样本 时 , 样本对外扩展的顺序 ;

② 特定 $\varepsilon_i$ ( 可达距离 ) : 该 $\varepsilon_i$ 取值范围是 $[0 , \, \varepsilon]$ 闭区间 ; 这是预先设定的一个半径值 ;

2 . 处理过程 : 根据 族序 处理每个样本对象 ; 每个样本对象都有 族序 , 核心距离 , 可达距离 属性 ;

OPTICS 算法 第二阶段 工作流程

---

1 . 取出样本 : 取出任意 样本对象 $p$ ;

2 . 判定 可达距离 : 判定 $p$ 的可达距离 是否大于 $\varepsilon_i$ 半径 ;

( 1 ) 非聚类判定 : 如果 $p$ 可达距离 大于 $\varepsilon_i$ 半径值 , 那么说明 $p$ 之前的 族序 的样本对象 , 没有一个是到 $p$ 密度可达的 ;

只要进入这个分支 , 说明 $p$ 不是当前的聚类分组样本 , 要么是新的聚类 , 要么是噪音 ; 这个需要根据其核心距离进行判定 ;

判定核心距离 : $p$ 可达距离 大于 $\varepsilon_i$ 半径值 基础上 , 进一步判定 $p$ 的核心距离 ;

① 新聚类分组 : 如果 $p$ 样本的 核心距离 , 小于 $\varepsilon_i$ , 说明 $p$ 是核心对象 , 此时创建一个新的聚类分组 ;

② 噪音标记 : 如果 $p$ 样本的 核心距离 , 大于 $\varepsilon_i$ , 将 $p$ 标记为噪音 , 异常点 ;

( 2 ) 聚类判定 : 如果 $p$ 可达距离 小于等于 $\varepsilon_i$ 半径值 , 将 $p$ 标记为当前的聚类分组 ;

OPTICS 算法 示例 题目

---

已知条件 :

① 数据集 : 将如下 含有 16 个样本的 数据集 , 进行聚类分析 ;

② 数据样本的属性 : 该数据样本是 二维数据 , 有两个属性值 , 可以在一个平面进行模拟 , 一个是 $x$ 轴数据 , 一个是 $y$ 轴数据 ;

③ 聚类参数 : $\varepsilon$-邻域 半径是 $\varepsilon = 44$ , $\varepsilon$-邻域样本最小阈值 为 $MinPts = 3$ ;

OPTICS 算法 示例 人为判断

---

首先由人进行的判断分析 ( 仅做参考 ) : 人先进行判断 , 这不是最后结果 ;

该样本数据集 , 使用肉眼判断 , 应该分成 两层 分组 ;

内层分组 : 如下图 绿色的 圈代表的聚类 ;

外层分组 : 如下图 红色的 圈代表的聚类 ;

OPTICS 算法 示例 第一次迭代

---

选择 样本 $A$ 开始分析 : 样本 $A$ 的核心距离是 $\varepsilon$ ; 将样本 $A$ 拿出来 , 放入

族序 - 可达距离 坐标系 : $x$ 轴是族序 , $y$ 轴是可达距离 ;

其中 $A$ 由于是第一个处理的样本 , 其只有核心距离 , 没有可达距离 , 因此 $A$ 的可达距离设置成 正无穷大 ;

判定 样本 $A$ 是否是核心对象 : 判定数据样本 $A$ 是否是核心对象 , 通过判定其 $\varepsilon$-邻域 中分布的样本数量是否大于等于 $MinPts = 3$ 阈值 个数 , 也就是除 $A$ 外 , 应该还有另外 $2$ 个样本 , 这里发现其 $\varepsilon$-邻域 中还有 样本 $B$ 和样本 $I$ , 因此 样本 $A$ 是核心对象 ;

样本 $A$ 是核心对象 : 执行下面一系列流程 ;

① 提取样本 : 提取所有 从 $A$ 样本触发 , 密度可达的 数据样本对象 , 即 $B$ , $I$ 两个样本 ;

② 计算核心距离 : 计算 样本 $A$ 的核心距离 , 结果是 $40$ ;

③ 计算 可达距离 : 计算 提取的 $B$ , $I$ 两个样本 对象的 可达距离 , 都是 $40$ ;

④ 待处理队列 : 将计算好 核心距离 可达距离 的样本放入 待处理队列 $Q$ 中 ;

$\{ \quad ( B , 40 ) \quad ( I , 40 ) \quad \}$

$( B , 40 )$ 中的 $B$ 表示 样本 $B$ , $40$ 表示 样本 $A$ 到 样本 $B$ 的 可达距离 是 $40$ ;

$( I , 40 )$ 中的 $I$ 表示 样本 $I$ , $40$ 表示 样本 $A$ 到 样本 $I$ 的 可达距离 是 $40$ ;

OPTICS 算法 示例 第二次迭代

---

选择样本 $B$ 分析 : 从 $Q$ 待处理队列 $\{ \quad ( B , 40 ) \quad ( I , 40 ) \quad \}$ 中 , 选择一个 可达距离 最小的样本 $B$ 继续进行 进一步的 扩展 , 这两个样本可达距离都是 $40$ , 任意选一个即可 , 选择 $B$ ;

此时将 $B$ 从待处理队列 $Q$ 中移出 , 只剩下 $I$ 样本 , 此时的待处理队列是 :

$\{ \quad ( I , 40 ) \quad \}$

将 样本 $B$ 拿出来 , 放入以下坐标系中 , 坐标系是

族序 - 可达距离 坐标系 : $x$ 轴是族序 , $y$ 轴是可达距离 ;

其中 样本 $B$ 可达距离是 $40$ , 其对应的 $y$ 轴可达距离是 $40$ , $x$ 轴族序是 $2$ ;

判定 样本 $B$ 是否是核心对象 : 判定数据样本 $B$ 是否是核心对象 , 通过判定其 $\varepsilon$-邻域 中分布的样本数量是否大于等于 $MinPts = 3$ 阈值 个数 , 也就是除 $B$ 外 , 应该还有另外 $2$ 个样本 , 这里发现其 $\varepsilon$-邻域 中还有 样本 $A$ 和样本 $C$ , 因此 样本 $B$ 是核心对象 ;

样本 $B$ 是核心对象 : 执行下面一系列流程 ;

① 提取样本 : 提取所有 从 $B$ 样本触发 , 密度可达的 数据样本对象 , 即 $C$ , $A$ 两个样本 ; 但是样本 $A$ 已经处理过了 , 就不再处理样本 $A$ , 只处理样本 $C$ ;

② 计算核心距离 : 计算 样本 $B$ 的核心距离 , 从 $B$ 到 $C$ 的距离 , 结果是 $40$ ;

③ 计算 可达距离 : 计算 提取的 $C$ 样本 对象的 可达距离 , 是 $40$ ;

④ 待处理队列 : 将计算好 核心距离 可达距离 的样本放入 待处理队列 $Q$ 中 ;

$\{ \quad ( I , 40 ) \quad ( C , 40 ) \quad \}$

$( C , 40 )$ 中的 $C$ 表示 样本 $C$ , $40$ 表示 样本 $C$ 到 样本 $B$ 的 可达距离 是 $40$ ;

$( I , 40 )$ 中的 $I$ 表示 样本 $I$ , $40$ 表示 样本 $A$ 到 样本 $I$ 的 可达距离 是 $40$ ;

OPTICS 算法 示例 第三次迭代

---

选择样本 $I$ 分析 : 从 $Q$ 待处理队列 $\{ \quad ( I , 40 ) \quad ( C , 40 ) \quad \}$ 中 , 选择一个 可达距离 最小的样本 $I$ 继续进行 进一步的 扩展 , 这两个样本可达距离都是 $40$ , 任意选一个即可 , 选择 $I$ ;

此时将 $I$ 从待处理队列 $Q$ 中移出 , 只剩下 $C$ 样本 , 此时的待处理队列是 :

$\{ \quad ( C , 40 ) \quad \}$

将 样本 $I$ 拿出来 , 放入以下坐标系中 , 坐标系是

族序 - 可达距离 坐标系 : $x$ 轴是族序 , $y$ 轴是可达距离 ;

其中 样本 $I$ 可达距离是 $40$ , 其对应的 $y$ 轴可达距离是 $40$ , $x$ 轴族序是 $3$ ;

判定 样本 $I$ 是否是核心对象 : 判定数据样本 $I$ 是否是核心对象 , 通过判定其 $\varepsilon$-邻域 中分布的样本数量是否大于等于 $MinPts = 3$ 阈值 个数 , 也就是除 $I$ 外 , 应该还有另外 $2$ 个样本 , 这里发现其 $\varepsilon$-邻域 中还有 样本 $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$ 中 ;

$\{ \quad ( J , 20 ) \quad ( K , 20 ) \quad ( L , 31 ) \quad ( C , 40 ) \quad ( M , 40 ) \quad ( R , 43 ) \quad \}$

$( J , 20 )$ 中的 $J$ 表示 样本 $J$ , $20$ 表示 样本 $I$ 到 样本 $J$ 的 可达距离 是 $20$ ;

OPTICS 算法 示例 第四次迭代

---

选择样本 $J$ 分析 : 从 $Q$ 待处理队列 $\{ \quad ( J , 20 ) \quad ( K , 20 ) \quad ( L , 31 ) \quad ( C , 40 ) \quad ( M , 40 ) \quad ( R , 43 ) \quad \}$ 中 , 选择一个 可达距离 最小的样本 $J$ 继续进行 进一步的 扩展 , 这个样本可达距离是 $20$ , 在待处理队列中最小 , 选择 样本 $J$ ;

此时将 $J$ 从待处理队列 $Q$ 中移出 , 剩下 $K,L,C,M,R$ 样本 , 此时的待处理队列是 :

$\{ \quad ( K , 20 ) \quad ( L , 31 ) \quad ( C , 40 ) \quad ( M , 40 ) \quad ( R , 43 ) \quad \}$

将 样本 $J$ 拿出来 , 放入以下坐标系中 , 坐标系是

族序 - 可达距离 坐标系 : $x$ 轴是族序 , $y$ 轴是可达距离 ;

其中 样本 $J$ 可达距离是 $20$ , 其对应的 $y$ 轴可达距离是 $20$ , $x$ 轴族序是 $4$ ;

判定 样本 $J$ 是否是核心对象 : 判定数据样本 $J$ 是否是核心对象 , 通过判定其 $\varepsilon$-邻域 中分布的样本数量是否大于等于 $MinPts = 3$ 阈值 个数 , 也就是除 $J$ 外 , 应该还有另外 $2$ 个样本 , 这里发现其 $\varepsilon$-邻域 中还有 样本 $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$ 中 ;

$\{ \quad ( L , 19) \quad ( K , 20 ) \quad ( R , 21 ) \quad ( M , 30 ) \quad ( P , 31 ) \quad ( C , 40 ) \quad \}$

$( L , 19 )$ 中的 $L$ 表示 样本 $L$ , $19$ 表示 样本 $J$ 到 样本 $L$ 的 可达距离 是 $19$ ;

OPTICS 算法 示例 第五次迭代

---

选择样本 $L$ 分析 : 从 $Q$ 待处理队列 $\{ \quad ( L , 19) \quad ( K , 20 ) \quad ( R , 21 ) \quad ( M , 30 ) \quad ( P , 31 ) \quad ( C , 40 ) \quad \}$ 中 , 选择一个 可达距离 最小的样本 $L$ 继续进行 进一步的 扩展 , 这个样本可达距离是 $19$ , 在待处理队列中最小 , 选择 样本 $L$ ;

此时将 $L$ 从待处理队列 $Q$ 中移出 , 剩下 $K,R, M, P,C$ 样本 , 此时的待处理队列是 :

$\{ \quad ( K , 20 ) \quad ( R , 21 ) \quad ( M , 30 ) \quad ( P , 31 ) \quad ( C , 40 ) \quad \}$

将 样本 $L$ 拿出来 , 放入以下坐标系中 , 坐标系是

族序 - 可达距离 坐标系 : $x$ 轴是族序 , $y$ 轴是可达距离 ;

其中 样本 $L$ 可达距离是 $19$ , 其对应的 $y$ 轴可达距离是 $19$ , $x$ 轴族序是 $5$ ;

判定 样本 $L$ 是否是核心对象 : 判定数据样本 $L$ 是否是核心对象 , 通过判定其 $\varepsilon$-邻域 中分布的样本数量是否大于等于 $MinPts = 3$ 阈值 个数 , 也就是除 $L$ 外 , 应该还有另外 $2$ 个样本 , 这里发现其 $\varepsilon$-邻域 中还有 样本 $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$ 中 ;

$\{ \quad ( M , 18) \quad ( K , 18 ) \quad ( R , 20 ) \quad ( P , 21 ) \quad ( N , 35 ) \quad ( C , 40 ) \quad \}$

$( M , 18 )$ 中的 $M$ 表示 样本 $M$ , $18$ 表示 样本 $L$ 到 样本 $M$ 的 可达距离 是 $18$ ;

OPTICS 算法 示例 第十六次迭代

---

第 $16$ 次迭代之后 , $Q$ 待处理队列 清空 , 所有的样本都放到了 族序 - 可达距离 坐标系 中 ;

族序 - 可达距离 坐标系 : $x$ 轴是族序 , $y$ 轴是可达距离 ;

此时已经将每个样本的 族序 , 以及其可达距离表示在了坐标系中 ;

此时可以开始进行聚类了 ;

OPTICS 算法 示例 第二阶段聚类分析

---

$\varepsilon$ 太小无意义聚类分析 : 选择如下图所绘制的 红色线代表的 $\varepsilon$ 值进行聚类 , 没有任何意义 , 距离太小了 , 以至于所有的样本都不能密度可达 ; 所有的样本都被标记成噪音了 ;

2 . 两个聚类分组的情况 :

下图中 , 绘制的红色线的 $y$ 轴值代表的 $\varepsilon$ , 此时按照此 $\varepsilon$ 进行聚类 , 凹形的分在一组 聚类中 , 如

聚类分组 $1$ : $\{ J , L,M,K,N,R,P \}$ ;

聚类分组 $2$ : $\{ D,F,G,E \}$ ;

其它的 $A,B,I,C,H$ 样本 都被 标记成噪音 处理了 ;

3 . 一个聚类分组的情况 :

聚类分析 : 下图中 , 绘制的红色线的 $y$ 轴值代表的 $\varepsilon$ , 此时按照此 $\varepsilon = 44$ 进行聚类 , 凹形的分在一组 聚类中 , 如

聚类分组 $1$ : $\{ B, I ,J , L,M,K,N,R,P, C , D,F,G,E , H \}$ ;

噪音 : 样本 $A$ 被当做噪音处理了 ;