一、DBSCAN算法

1. 簡介

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一個基于密度的聚類算法。算法把簇看作數(shù)據(jù)空間中由低密度區(qū)域分割開的高密度對象區(qū)域；將足夠高密度的區(qū)域劃為簇，可以在有噪音的數(shù)據(jù)集中發(fā)現(xiàn)任意形狀的聚類。

2. 基本概念

在DBSCAN 算法中有兩個重要的參數(shù)：Eps 和 MinPtS。Eps 是定義密度時的鄰域半徑，MinPts 為定義核心點時的閾值。

基于中心定義密度的方法可將點分為三類：

（1）核心點：給定用戶指定閾值MinPts，如果一個點的給定鄰域內(nèi)的點的數(shù)目超過給定閾值MinPts， 那么該點稱為核心點。

（2）邊界點：邊界點不是核心點，但它落在某個核心點的Eps鄰域內(nèi)。

（3）噪聲點：噪聲點既不是核心點，也不是邊界點。

基于密度的簇定義如下：

（1）密度直達：給定一個對象集合D，如果p是在q的鄰域內(nèi)，且q是一個核心對象，則稱p從對象q出發(fā)是直接密度直達的。

（2）密度可達：如果存在一個對象鏈 ， ，對于

是從關(guān)于Eps和MinPts直接密度可達的，則對象p是從對象q關(guān)于Eps和MinPts密度可達的。

（3）密度連接：如果對象集D中存在一個對象o，使得對象p和q是從o關(guān)于Eps和MinPts密度可達的，那么對象p和q是關(guān)于Eps和MinPts密度連接的。

（4）密度可達是密度直達的傳遞閉包，這種關(guān)系非對稱的，只有核心對象之間是相互密度直達的。

3. 算法過程

通俗的來講，算法流程如下：

（1）將所有數(shù)據(jù)對象標(biāo)記為核心對象、邊界對象或噪聲對象。

（2）刪除噪聲對象。

（3）為距離在Eps之內(nèi)的所有核心對象之間賦予一條邊。

（4）每組聯(lián)通的核心對象形成一個簇。

（5）將每個邊界對象指派到一個與之關(guān)聯(lián)的核心對象的簇中。

二、DBSCAN算法舉例

1. 案例說明和數(shù)據(jù)

給定一組二維數(shù)據(jù)（x，y）作為點，可以自己定義也可以利用下面的數(shù)據(jù)，將數(shù)據(jù)存入文本文檔中，放入相應(yīng)目錄下即可。Eps設(shè)為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

2. 代碼

//定義點類
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;
    }

    /**
     * 設(shè)置已經(jīng)分類點的標(biāo)志
     * @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;
    }

    /**
     * 讀取數(shù)據(jù)
     * @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>>();// 分類結(jié)果集
    private static int e = 2;// e半徑
    //private static int e = 2;// e半徑
     private static int minp = 3;// 密度閾值
    //private static int minp = 4;// 密度閾值

    /**
     * 打印結(jié)果
     **/
    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++;
        }
    }

    /**
     * 調(diào)用算法
     */
    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) {
                        // 為所有聚類完畢的點做標(biāo)示
                        Utility.setListClassed(tmpLst);
                        resultList.add(tmpLst);
                    }
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    /**
     * 合并結(jié)果集
     * @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;
    }

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

    }
}

3.運行結(jié)果

三、總結(jié)

DBSCAN算法可以對任意形狀的稠密數(shù)據(jù)集進行聚類，相對于K-Means、Mean Shift之類的聚類算法一般只適用于凸數(shù)據(jù)集。除此之外該算法在聚類的同時發(fā)現(xiàn)異常點，對數(shù)據(jù)集中的異常點不敏感。

DBSCAN算法也存著缺點，如果樣本集的密度不均勻、聚類間距差相差很大時，聚類質(zhì)量比較差；樣本集較大時，聚類收斂時間較長；以及對Eps和MinPts的聯(lián)合調(diào)參是比較困難的。

在日常生活中，我們可以根據(jù)數(shù)據(jù)的類型進行合理選擇該算法進行聚類分類。

參考

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

https://zhuanlan.zhihu.com/p/139926467文章來源地址http://www.zghlxwxcb.cn/news/detail-812657.html