首页 / 算法 / OPTICS聚类算法原理
OPTICS聚类算法原理
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了OPTICS聚类算法原理,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2287字,纯文字阅读大概需要4分钟。
内容图文
![OPTICS聚类算法原理](/upload/InfoBanner/zyjiaocheng/632/28b04f15fca64ae9898bfbd63406098d.jpg)
OPTICS聚类算法原理
基础
OPTICS聚类算法是基于密度的聚类算法,全称是Ordering points to identify the clustering structure,目标是将空间中的数据按照密度分布进行聚类,其思想和DBSCAN非常类似,但是和DBSCAN不同的是,OPTICS算法可以获得不同密度的聚类,直接说就是经过OPTICS算法的处理,理论上可以获得任意密度的聚类。因为OPTICS算法输出的是样本的一个有序队列,从这个队列里面可以获得任意密度的聚类。
定义
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、结果队列遍历结束,则算法结束。
内容总结
以上是互联网集市为您收集整理的OPTICS聚类算法原理全部内容,希望文章能够帮你解决OPTICS聚类算法原理所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。