聚类算法--DBSCAN算法

这篇具有很好参考价值的文章主要介绍了聚类算法--DBSCAN算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、DBSCAN算法

  1. 简介

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个基于密度的聚类算法。算法把簇看作数据空间中由低密度区域分割开的高密度对象区域;将足够高密度的区域划为簇,可以在有噪音的数据集中发现任意形状的聚类。
  1. 基本概念

在DBSCAN 算法中有两个重要的参数:Eps 和 MinPtS。Eps 是定义密度时的邻域半径,MinPts 为定义核心点时的阈值。

基于中心定义密度的方法可将点分为三类:

(1)核心点:给定用户指定阈值MinPts,如果一个点的给定邻域内的点的数目超过给定阈值MinPts, 那么该点称为核心点。

(2)边界点:边界点不是核心点,但它落在某个核心点的Eps邻域内。

(3)噪声点:噪声点既不是核心点,也不是边界点。

基于密度的簇定义如下:

(1)密度直达:给定一个对象集合D,如果p是在q的邻域内,且q是一个核心对象,则称p从对象q出发是直接密度直达的。

(2)密度可达:如果存在一个对象链 , dbscan聚类算法,算法,聚类,数据挖掘,机器学习,Powered by 金山文档 ,对于

dbscan聚类算法,算法,聚类,数据挖掘,机器学习,Powered by 金山文档是从dbscan聚类算法,算法,聚类,数据挖掘,机器学习,Powered by 金山文档关于Eps和MinPts直接密度可达的,则对象p是从对象q关于Eps和MinPts密度可达的。

(3)密度连接:如果对象集D中存在一个对象o,使得对象p和q是从o关于Eps和MinPts密度可达的,那么对象p和q是关于Eps和MinPts密度连接的。

(4)密度可达是密度直达的传递闭包,这种关系非对称的,只有核心对象之间是相互密度直达的。

  1. 算法过程

dbscan聚类算法,算法,聚类,数据挖掘,机器学习,Powered by 金山文档

通俗的来讲,算法流程如下:

(1)将所有数据对象标记为核心对象、边界对象或噪声对象。

(2)删除噪声对象。

(3)为距离在Eps之内的所有核心对象之间赋予一条边。

(4)每组联通的核心对象形成一个簇。

(5)将每个边界对象指派到一个与之关联的核心对象的簇中。

二、DBSCAN算法举例

  1. 案例说明和数据

给定一组二维数据(x,y)作为点,可以自己定义也可以利用下面的数据,将数据存入文本文档中,放入相应目录下即可。Eps设为2,MinPts为3。使用DBSCAN算法进行分类操作。

0,0
0,1
0,2
0,3
0,4
0,5
12,1
12,2
12,3
12,4
12,5
12,6
0,6
0,7
12,7
0,8
0,9
1,1
6,8
8,7
6,7
3,5
  1. 代码

//定义点类
public class Point {
    private int x;
    private int y;
    private boolean isKey;
    private boolean isClassed;
    public boolean isKey() {
        return isKey;
    }
    public void setKey(boolean isKey) {

        this.isKey = isKey;
        this.isClassed = true;
    }
    public boolean isClassed() {
        return isClassed;
    }
    public void setClassed(boolean isClassed) {

        this.isClassed = isClassed;
    }
    public int getX() {
        return x;
    }
    public void setX(int x) {
        this.x = x;
    }
    public int getY() {
        return y;
    }
    public void setY(int y) {
        this.y = y;
    }
    public Point() {
        x = 0;
        y = 0;
    }
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public Point(String str) {
        String[] p = str.split(",");
        this.x = Integer.parseInt(p[0]);
        this.y = Integer.parseInt(p[1]);
    }
    public String print() {
        return "(" + this.x + "," + this.y + ")";
    }
}
//对点进行操作
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
public class Utility {


    /**
       * 测试两个点之间的距离
       * @param p 点
       * @param q 点
       * @return 返回两个点之间的距离
       */
    public static double getDistance(Point p,Point q){

        int dx=p.getX()-q.getX();
        int dy=p.getY()-q.getY();
        double distance=Math.sqrt(dx*dx+dy*dy);
        return distance;
    }

    /**
       * 检查给定点是不是核心点
       * @param lst 存放点的链表
       * @param p 待测试的点
        * @param e e半径
       * @param minp 密度阈值
       * @return
       */
    public static List<Point> isKeyPoint(List<Point> lst,Point p,int e,int minp){

        int count=0;
        List<Point> tmpLst=new ArrayList<Point>();
        for (Point q : lst) {
            if (getDistance(p, q) <= e) {
                ++count;
                if (!tmpLst.contains(q)) {
                    tmpLst.add(q);
                }
            }
        }
        if(count>=minp){
            p.setKey(true);
            return tmpLst;
        }
        return null;
    }

    /**
     * 设置已经分类点的标志
     * @param lst
     */
    public static void setListClassed(List<Point> lst){

        for (Point p : lst) {
            if (!p.isClassed()) {
                p.setClassed(true);
            }
        }
    }

    /**
     * 如果b中含有a中包含的元素,则把两个集合合并
     * @param a
     * @param b
     * @return a
     */
    public static boolean mergeList(List<Point> a,List<Point> b){
        boolean merge=false;
        for (Point value : b) {
            if (a.contains(value)) {
                merge = true;
                break;
            }
        }
        if(merge){
            for (Point point : b) {
                if (!a.contains(point)) {
                    a.add(point);
                }
            }
        }
        return merge;
    }

    /**
     * 读取数据
     * @return 返回文本中点的集合
     */
    public static List<Point> getPointsList() throws IOException{
        List<Point> lst=new ArrayList<Point>();
        //String txtPath="D:"+File.separatorChar+"Points.txt";
        String txtPath="E:\\myfile\\Points.txt";
        BufferedReader br=new BufferedReader(new FileReader(txtPath));

        String str="";
        while((str = br.readLine()) != null && !str.equals("")){
            lst.add(new Point(str));
        }
        br.close();
        return lst;
    }
}
//主要算法

import java.io.*;
import java.util.*;

public class DBScan {
    private static List<Point> pointsList = new ArrayList<Point>();// 初始点列表
    private static List<List<Point>> resultList = new ArrayList<List<Point>>();// 分类结果集
    private static int e = 2;// e半径
    //private static int e = 2;// e半径
     private static int minp = 3;// 密度阈值
    //private static int minp = 4;// 密度阈值

    /**
     * 打印结果
     **/
    private static void display() {
        int index = 1;
        for (List<Point> lst : resultList) {
            if (lst.isEmpty()) {
                continue;
            }
            System.out.println("*****第" + index + "个分类*****");
            for (Point p : lst) {
                System.out.print(p.print());

            }
            System.out.print("\n");
            index++;
        }
    }

    /**
     * 调用算法
     */
    private static void applyDbscan() {
        try {
            pointsList = Utility.getPointsList();
            for (Point p : pointsList) {
                if (!p.isClassed()) {
                    List<Point> tmpLst = new ArrayList<Point>();
                    if ((tmpLst = Utility.isKeyPoint(pointsList, p, e, minp)) != null) {
                        // 为所有聚类完毕的点做标示
                        Utility.setListClassed(tmpLst);
                        resultList.add(tmpLst);
                    }
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 合并结果集
     * @return
     */
    private static List<List<Point>> getResult() {
        applyDbscan();// 找到所有直达的聚类
        int length = resultList.size();
        for (int i = 0; i < length; ++i) {
            for (int j = i + 1; j < length; ++j) {
                if (Utility.mergeList(resultList.get(i), resultList.get(j))) {
                    resultList.get(j).clear();
                }
            }
        }
        return resultList;
    }

    /**
     * 程序主函数
     * @param args
     */
    public static void main(String[] args) {
        getResult();
        display();

    }
}

3.运行结果

dbscan聚类算法,算法,聚类,数据挖掘,机器学习,Powered by 金山文档

三、总结

DBSCAN算法可以对任意形状的稠密数据集进行聚类,相对于K-Means、Mean Shift之类的聚类算法一般只适用于凸数据集。除此之外该算法在聚类的同时发现异常点,对数据集中的异常点不敏感。

DBSCAN算法也存着缺点,如果样本集的密度不均匀、聚类间距差相差很大时,聚类质量比较差;样本集较大时,聚类收敛时间较长;以及对Eps和MinPts的联合调参是比较困难的。

在日常生活中,我们可以根据数据的类型进行合理选择该算法进行聚类分类。

参考

https://blog.csdn.net/qq_42735631/article/details/120983729

https://zhuanlan.zhihu.com/p/139926467文章来源地址https://www.toymoban.com/news/detail-812657.html

到了这里,关于聚类算法--DBSCAN算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • DBSCAN聚类算法

    DBSCAN (density-based spatial clustering of applications with noise),即“具有噪声的基于密度的空间聚类应用”。它的原理是识别特征空间的“拥挤”区域中的点,在这些区域中许多点靠在一起,这些区域称为特征空间中的 密集 区域。密集区域最终将有相对较空的区域分隔开。 在密集区

    2024年02月06日
    浏览(48)
  • DBSCAN聚类算法——MATLAB实现

        声明:本文修改自《 数学建模清风 》老师的代码    DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的区域划分为簇,并可在噪

    2024年02月11日
    浏览(44)
  • 密度聚类算法(DBSCAN)实验案例

    DBSCAN是一种强大的基于密度的聚类算法,从直观效果上看,DBSCAN算法可以找到样本点的全部密集区域,并把这些密集区域当做一个一个的聚类簇。DBSCAN的一个巨大优势是可以对任意形状的数据集进行聚类。 本任务的主要内容: 1、 环形数据集聚类 2、 新月形数据集聚类 3、

    2024年02月08日
    浏览(46)
  • 基于密度的聚类算法(1)——DBSCAN详解

    基于密度的聚类算法(1)——DBSCAN详解 基于密度的聚类算法(2)——OPTICS详解 基于密度的聚类算法(3)——DPC详解 1. DBSCAN简介 DBSCAN(Density-Based Spatial Clustering of Applications with Noise, 具有噪声的基于密度的聚类方法 )是一种典型的基于密度的空间聚类算法。和K-Means,BIR

    2024年01月24日
    浏览(47)
  • 毫米波雷达点云 DBSCAN聚类算法

    聚类的目的是将一组数据点划分为具有相似特征或属性的组或簇。通过聚类分析,我们可以识别出数据中的内在模式、结构和关联关系,从而获得对数据的更深入理解。 具体来说,聚类的目的可以分为以下三部分: 发现数据的内在结构: 聚类可以将数据分成簇,这些簇可能

    2024年02月06日
    浏览(46)
  • 深度解读DBSCAN聚类算法:技术与实战全解析

    探索DBSCAN算法的内涵与应用,本文详述其理论基础、关键参数、实战案例及最佳实践,揭示如何有效利用DBSCAN处理复杂数据集,突破传统聚类限制。 关注TechLead,分享AI全维度知识。作者拥有10+年互联网服务架构、AI产品研发经验、团队管理经验,同济本复旦硕,复旦机器人智

    2024年02月05日
    浏览(47)
  • C# | DBSCAN聚类算法实现 —— 对直角坐标系中临近点的点进行聚类

    聚类算法是一种常见的数据分析技术,用于将相似的数据对象归类到同一组或簇中。其中,DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法,能够有效地识别出不同形状和大小的簇,同时还能标识出噪声数据。本篇博客将介绍聚类算法的概念

    2024年02月09日
    浏览(39)
  • 数据挖掘18大算法实现以及其他相关经典DM算法:决策分类,聚类,链接挖掘,关联挖掘,模式挖掘、图算法,搜索算法等

    【机器学习入门与实践】入门必看系列,含数据挖掘项目实战:模型融合、特征优化、特征降维、探索性分析等,实战带你掌握机器学习数据挖掘 专栏详细介绍:【机器学习入门与实践】合集入门必看系列,含数据挖掘项目实战:数据融合、特征优化、特征降维、探索性分析

    2024年02月09日
    浏览(48)
  • 【机器学习】DBSCAN算法

    参考链接: https://blog.csdn.net/haveanybody/article/details/113092851 https://www.jianshu.com/p/dd6ce77bfb8a https://blog.csdn.net/qq_38563206/article/details/120941479 DBSCAN(Density-Based Spatial Clustering of Applica tion with Noise)算法是于1996年提出的一种简单的、有效的基于密度的聚类算法,该算法利用类的密度连通性

    2024年01月19日
    浏览(42)
  • 大数据的常用算法(分类、回归分析、聚类、关联规则、神经网络方法、web数据挖掘)

    在大数据时代,数据挖掘是最关键的工作。大数据的挖掘是从海量、不完全的、有噪声的、模糊的、随机的大型数据库中发现隐含在其中有价值的、潜在有用的信息和知识的过程,也是一种决策支持过程。其主要基于人工智能,机器学习,模式学习,统计学等。通过对大数据

    2024年02月09日
    浏览(63)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包