文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【数据挖掘】基于密度的聚类方法 - OPTICS 方法 ( 算法流程 | 算法示例 )

【数据挖掘】基于密度的聚类方法 - OPTICS 方法 ( 算法流程 | 算法示例 )

作者头像
韩曙亮
发布于 2023-03-27 20:02:15
发布于 2023-03-27 20:02:15
1.7K0
举报
文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

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

被当做噪音处理了 ;

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-05-06，如有侵权请联系 cloudcommunity@tencent.com 删除
数据挖掘
队列
对象
数据
算法

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数据挖掘
队列
对象
数据
算法
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 文章目录
    • OPTICS 算法 两个阶段
    • OPTICS 算法 第一阶段 生成族序
    • 待处理队列样本的 核心距离 与 可达距离
    • OPTICS 算法 第二阶段 数据准备
    • OPTICS 算法 第二阶段 工作流程
    • OPTICS 算法 示例 题目
    • OPTICS 算法 示例 人为判断
    • OPTICS 算法 示例 第一次迭代
    • OPTICS 算法 示例 第二次迭代
    • OPTICS 算法 示例 第三次迭代
    • OPTICS 算法 示例 第四次迭代
    • OPTICS 算法 示例 第五次迭代
    • OPTICS 算法 示例 第十六次迭代
    • OPTICS 算法 示例 第二阶段聚类分析
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2025 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论