`
fufeng
  • 浏览: 75690 次
社区版块
存档分类
最新评论

聚类分析(六)基于密度的聚类算法 — OPTICS

阅读更多

什么是 OPTICS 算法

在前面介绍的 DBSCAN 算法中,有两个初始参数 E (邻域半径)和 minPts(E 邻域最小点数 ) 需要用户手动设置输入,并且聚类的类簇结果对这两个参数的取值非常敏感,不同的取值将产生不同的聚类结果,其实这也是大多数其他需要初始化参数聚类算法的弊端。

为了克服 DBSCAN 算法这一缺点,提出了 OPTICS 算法( Ordering Points to identify the clustering structure )。 OPTICS 并 不显示的产生结果类簇,而是为聚类分析生成一个增广的簇排序(比如,以可达距离为纵轴,样本点输出次序为横轴的坐标图),这个排序代表了各样本点基于密度 的聚类结构。它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类,换句话说,从这个排序中可以得到基于任何参数 E minPts DBSCAN 算法的聚类结果。      

2  OPTICS 两个概念

核心距离

对象 p 的核心距离是指是 p 成为核心对象的最小 E’ 。如果 p 不是核心对象,那么 p 的核心距离没有任何意义。

可达距离

对象 q 到对象 p 的可达距离是指 p 的核心距离和 p q 之间欧几里得距离之间的较大值。如果 p 不是核心对象, p q 之间的可达距离没有意义。

例如:假设邻域半径 E=2, minPts=3 ,存在点 A(2,3),B(2,4),C(1,4),D(1,3),E(2,2),F(3,2)

A 为核心对象,在 A E 领域中有点 {A,B,C,D,E,F} ,其中 A 的核心距离为 E’=1 ,因为在点 A E’ 邻域中有点 {A,B,D,E}>3;

F 到核心对象点 A 的可达距离为 聚类分析(六)基于密度的聚类算法 <wbr>鈥 <wbr>OPTICS ,因为 A F 的欧几里得距离 聚类分析(六)基于密度的聚类算法 <wbr>鈥 <wbr>OPTICS ,大于点 A 的核心距离 1.

3 算法描述

OPTICS 算法额外存储了每个对象的核心距离和可达距离。基于 OPTICS 产生的排序信息来提取类簇。

算法描述如下:

算法: OPTICS

输入:样本集 D, 邻域 半径 E, 给定点在 E 领域内成为核心对象的最小领域点数 MinPts

输出:具有可达距离信息的样本点输出排序

方法: 1 创建两个队列,有序队列和结果队列。(有序队列用来存储核心对象及其该核心对

         象的直接可达对象,并按可达距离升序排列;结果队列用来存储样本点的输出次

         序);

        2 如果所有样本集 D 中所有点都处理完毕,则算法结束。否则,选择一个未处理(即

不在结果队列中)且为核心对象的样本点,找到其所有直接密度可达样本点,如

过该样本点不存在于结果队列中,则将其放入有序队列中,并按可达距离排序;

      3 如果有序队列为空,则跳至步骤 2 ,否则,从有序队列中取出第一个样本点(即可

达距离最小的样本点)进行拓展,并将取出的样本点保存至结果队列中,如果它不

存在结果队列当中的话。

  3.1 判断该拓展点是否是核心对象,如果不是,回到步骤 3 ,否则找到该拓展点所

有的直接密度可达点;

3.2 判断该直接密度可达样本点是否已经存在结果队列,是则不处理,否则下一

步;

3.2 如果有序队列中已经存在该直接密度可达点,如果此时新的可达距离小于旧

的可达距离,则用新可达距离取代旧可达距离,有序队列重新排序;

3.3 如果有序队列中不存在该直接密度可达样本点,则插入该点,并对有序队列

   重新排序;

        4 算法结束,输出结果队列中的有序样本点。

大家或许会很疑惑,这里不也有输入参数 E MinPts 吗?其实这里的 E MinPts 只是起到算法辅助作用,也就是说 E MinPts 的细微变化并不会影响到样本点的相对输出顺序,这对我们分析聚类结果是没有任何影响。

我们采用与先前 DBSCAN 相同的样本点集合,

对于样本点

a={2,3};b={2,4};c={1,4};d={1,3};e={2,2};f={3,2};

g={8,7};h={8,6};i={7,7};j={7,6};k={8,5};

l={100,2}; // 孤立点

m={8,20};n={8,19};o={7,18};p={7,17};q={8,21};

并且使用相同的 E=2 MinPts =4时,输出序列为

1->a:1.0

2->e:1.0

3->b:1.0

4->d:1.0

5->c:1.4142135623730951

6->f:1.4142135623730951

------

7->g:1.4142135623730951

8->j:1.4142135623730951

9->k:1.4142135623730951

10->i:1.4142135623730951

11->h:1.4142135623730951

------

12->n:2.0

13->q:2.0

14->o:2.0

15->m:2.0

聚类分析(六)基于密度的聚类算法 <wbr>鈥 <wbr>OPTICS

如图,按照算法,分三个阶段输出了三波值

{a,e,b,d,c,f} ,{g,j,k,I,h},{n,q,o,m}

这和 DBSCAN 的类簇结果是一样的。不仅如此,我们通过 分析 有序图还能直接得到当参数 E=1.5,minPts=4 DBSCAN 的类簇结果,只要在坐标图中找到 Y 值小于 1.5 的样本点即可,只有两类 {a,e,b,d,c,f} ,{g,j,k,I,h}, 其他点被认为是孤立点,和 DBSCAN 聚类算法取 E=1.5,minPts=4 时的结果一致。

所以说,这个 OPTICS 聚类算法所得的簇排序信息等价于一个广泛的参数设置所获得的基于密度的聚类结果。

具体实现算法如下:

package com.optics;

public class DataPoint {

 

   private String name; // 样本点名
    private double dimensioin[]; // 样本点的维度
    private double coreDistance; //核心距离,如果该点不是核心对象,则距离为-1
    private double reachableDistance; //可达距离

    public DataPoint(){
    }

    public DataPoint(DataPoint e){
        this.name=e.name;
        this.dimensioin=e.dimensioin;
        this.coreDistance=e.coreDistance;
        this.reachableDistance=e.reachableDistance;
    }

    public DataPoint(double dimensioin[],String name){
        this.name=name;
        this.dimensioin=dimensioin;
        this.coreDistance=-1;
        this.reachableDistance=-1;
    }

    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public double[] getDimensioin() {
        return dimensioin;
    }
    public void setDimensioin(double[] dimensioin) {
        this.dimensioin = dimensioin;
    }
    public double getCoreDistance() {
        return coreDistance;
    }
    public void setCoreDistance(double coreDistance) {
        this.coreDistance = coreDistance;
    }
    public double getReachableDistance() {
        return reachableDistance;
    }
    public void setReachableDistance(double reachableDistance) {
        this.reachableDistance = reachableDistance;
    }
}
package com.optics;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ClusterAnalysis {
    class ComparatorDp implements Comparator<DataPoint>{
        public int compare(DataPoint arg0, DataPoint arg1) {
            double temp=arg0.getReachableDistance()-arg1.getReachableDistance();
            int a = 0;
            if (temp < 0) {
                a = -1;
            } else {
                a = 1;
            }
            return a;
        }
    }

   
    public List<DataPoint> startAnalysis(List<DataPoint> dataPoints,
            double radius, int ObjectNum) {
        List<DataPoint> dpList = new ArrayList<DataPoint>();
        List<DataPoint> dpQue = new ArrayList<DataPoint>();

        int total = 0;
        while (total < dataPoints.size()) {
            if (isContainedInList(dataPoints.get(total), dpList) == -1 ) {
                List<DataPoint> tmpDpList = isKeyAndReturnObjects(dataPoints.get(total),
                        dataPoints, radius, ObjectNum);
                if(tmpDpList != null && tmpDpList.size() > 0){
                    DataPoint newDataPoint=new DataPoint(dataPoints.get(total));
                   dpQue.add(newDataPoint);
                }
            }
            while (!dpQue.isEmpty()) {
                DataPoint tempDpfromQ = dpQue.remove(0);
                DataPoint newDataPoint=new DataPoint(tempDpfromQ);
                dpList.add(newDataPoint);
                List<DataPoint> tempDpList = isKeyAndReturnObjects(tempDpfromQ,
                        dataPoints, radius, ObjectNum);
                System.out.println(newDataPoint.getName()+":"+newDataPoint.getReachableDistance());
                if (tempDpList != null && tempDpList.size() > 0) {
                    for (int i = 0; i < tempDpList.size(); i++) {
                        DataPoint tempDpfromList = tempDpList.get(i);
                        int indexInList = isContainedInList(tempDpfromList,
                                dpList);
                        int indexInQ = isContainedInList(tempDpfromList, dpQue);
                        if (indexInList == -1) {
                            if (indexInQ > -1) {
                                int index = -1;
                                for (DataPoint dataPoint : dpQue) {
                                    index++;
                                    if (index == indexInQ) {
                                        if (dataPoint.getReachableDistance() > tempDpfromList
                                                .getReachableDistance()) {
                                            dataPoint
                                                    .setReachableDistance(tempDpfromList
                                                            .getReachableDistance());
                                        }
                                    }
                                }
                            } else {
                                dpQue.add(new DataPoint(tempDpfromList));
                            }
                        }
                    }

                    // TODO:对Q进行重新排序
                    Collections.sort(dpQue, new ComparatorDp());
                }
            }
            System.out.println("------");
            total++;

        }

        return dpList;
    }

   
    public void displayDataPoints(List<DataPoint> dps){
        for(DataPoint dp: dps){
            System.out.println(dp.getName()+":"+dp.getReachableDistance());
        }
    }

   
    private int isContainedInList(DataPoint dp, List<DataPoint> dpList) {
        int index = -1;
        for (DataPoint dataPoint : dpList) {
            index++;
            if (dataPoint.getName().equals(dp.getName())) {
                return index;
            }
        }
        return -1;
    }

   
   private List<DataPoint> isKeyAndReturnObjects(DataPoint dataPoint,List<DataPoint> dataPoints,double radius,int ObjectNum){
       List<DataPoint> arrivableObjects=new ArrayList<DataPoint>(); //用来存储所有直接密度可达对象
       List<Double> distances=new ArrayList<Double>(); //欧几里得距离
       double coreDistance; //核心距离

        for (int i = 0; i < dataPoints.size(); i++) {
            DataPoint dp = dataPoints.get(i);
            double distance = getDistance(dataPoint, dp);
            if (distance <= radius) {
                distances.add(distance);
                arrivableObjects.add(dp);
            }
        }

       if(arrivableObjects.size()>=ObjectNum){
           List<Double> newDistances=new ArrayList<Double>(distances);
           Collections.sort(distances);
           coreDistance=distances.get(ObjectNum-1);
           for(int j=0;j<arrivableObjects.size();j++){
                if (coreDistance > newDistances.get(j)) {
                    if(newDistances.get(j)==0){
                        dataPoint.setReachableDistance(coreDistance);
                    }
                    arrivableObjects.get(j).setReachableDistance(coreDistance);
                }else{
                    arrivableObjects.get(j).setReachableDistance(newDistances.get(j));
                }
           }
           return arrivableObjects;
       }

       return null;
   }

   
    private double getDistance(DataPoint dp1,DataPoint dp2){
        double distance=0.0;
        double[] dim1=dp1.getDimensioin();
        double[] dim2=dp2.getDimensioin();
        if(dim1.length==dim2.length){
            for(int i=0;i<dim1.length;i++){
                double temp=Math.pow((dim1[i]-dim2[i]), 2);
                distance=distance+temp;
            }
            distance=Math.pow(distance, 0.5);
            return distance;
        }
        return distance;
    }

    public static void main(String[] args){
         ArrayList<DataPoint> dpoints = new ArrayList<DataPoint>();
        
         double[] a={2,3};
         double[] b={2,4};
         double[] c={1,4};
         double[] d={1,3};
         double[] e={2,2};
         double[] f={3,2};

         double[] g={8,7};
         double[] h={8,6};
         double[] i={7,7};
         double[] j={7,6};
         double[] k={8,5};

         double[] l={100,2};//孤立点


         double[] m={8,20};
         double[] n={8,19};
         double[] o={7,18};
         double[] p={7,17};
         double[] q={8,21};

         dpoints.add(new DataPoint(a,"a"));
         dpoints.add(new DataPoint(b,"b"));
         dpoints.add(new DataPoint(c,"c"));
         dpoints.add(new DataPoint(d,"d"));
         dpoints.add(new DataPoint(e,"e"));
         dpoints.add(new DataPoint(f,"f"));

         dpoints.add(new DataPoint(g,"g"));
         dpoints.add(new DataPoint(h,"h"));
         dpoints.add(new DataPoint(i,"i"));
         dpoints.add(new DataPoint(j,"j"));
         dpoints.add(new DataPoint(k,"k"));

         dpoints.add(new DataPoint(l,"l"));

         dpoints.add(new DataPoint(m,"m"));
         dpoints.add(new DataPoint(n,"n"));
         dpoints.add(new DataPoint(o,"o"));
         dpoints.add(new DataPoint(p,"p"));
         dpoints.add(new DataPoint(q,"q"));

         ClusterAnalysis ca=new ClusterAnalysis();
         List<DataPoint> dps=ca.startAnalysis(dpoints, 2, 4);
         ca.displayDataPoints(dps);
    }

}

分享到:
评论

相关推荐

    基于密度的聚类算法optics(matlab程序)。

    基于密度的聚类算法optics(matlab程序)。官方程序,亲测好用,欢迎下载。

    聚类分析OPTICS算法python实现

    在众多聚类算法中,DBSCAN(Density-Based Spatial Clustering of Applications with Noise)因其对噪声和不规则形状簇的良好处理能力而受到广泛欢迎。而OPTICS(Ordering Points To Identify the Clustering ...

    基于密度聚类optics算法参数估计

    **基于密度聚类的OPTICS(Ordering Points To Identify the Clustering Structure)算法是一种用于无监督学习的聚类方法,其主要目标是发现数据集中的各种形状和大小的聚类结构,不受聚类数量的限制。MATLAB作为一款...

    基于密度的聚类算法.rar_DBSCAN_dbscan密度_dbscan聚类分析_密度聚类算法_聚类算法

    **基于密度的聚类算法——DBSCAN** DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一种非监督学习的聚类算法,它以其独特的密度连接概念,在数据挖掘领域有着广泛的应用。DBSCAN能够...

    基于密度的聚类课件DBSAN、OPTICS、DENSECLUE

    本篇文章将深入探讨三种基于密度的聚类算法:DBSCAN、OPTICS和DENCLUE。 首先,我们回顾一下聚类的基本概念。聚类是一种无监督学习方法,不依赖预先标注的类别信息,而是通过寻找数据内部的自然结构来组织数据。...

    使用numpy实现的聚类算法(包括时空聚类算法)

    MYOPTICS:基于密度的聚类OPTICS(Ordering points to identify the clustering structure)算法的底层实现 MYKMeans:基于划分的聚类KMeans算法的底层实现 MYCFSFDP:基于划分和密度的聚类CFSFDP(Clustering by ...

    聚类算法分析综述.

    从相似度度量角度分析聚类方法,聚类算法可以分为基于距离的聚类、基于密度的聚类、基于余弦度量的聚类等多种类型。基于距离的聚类方法依赖于数据点之间的距离测量,包括欧几里得距离、曼哈顿距离、闵可夫距离等。...

    cluster.zip_clustering_k-means密度_聚类算法_谱密度_谱聚类

    2. **密度聚类**:密度聚类算法如DBSCAN(Density-Based Spatial Clustering of Applications with Noise)和 OPTICS(Ordering Points To Identify the Clustering Structure),更适用于发现任意形状的簇。...

    optics聚类算法

    **光学(OPTICS)聚类算法** OPTICS,即Ordering Points To Identify the Clustering Structure,是一种用于发现数据集中的聚类结构的无参数密度敏感的聚类算法。该算法由Anja Becker、Jörg Sander和Peter Eades于...

    几种聚类分析的计算方法

    常见的基于密度的方法算法有 DBSCAN 算法、OPTICS 算法、DENCLUE 算法等。 4. 基于网格的方法 基于网格的方法是将数据空间划分成有限个单元(cell)的网格结构,然后对每个单元进行处理。常见的基于网格的方法算法...

    数据挖掘中聚类算法的综述.pptx

    常见的基于密度的聚类算法有DBSCAN、OPTICS等。 五、聚类算法的应用 聚类算法在各个领域都有着广泛的应用。在商业领域,聚类算法可以用于客户细分、市场分析等,帮助企业更好地了解客户需求和市场趋势;在教育领域...

    java 实现的 Optics 算法

    该算法基于密度连接度,定义了一个点的密度可达性和密度排斥性。密度可达性意味着一个点可以通过一系列连续的高密度邻域到达另一个点。而密度排斥性则是指在某个点的邻域内存在另一个点,其邻域内的点数量超过了预设...

    MATLAB 聚类算法

    ### MATLAB中的聚类算法 #### 一、引言 在数据挖掘与机器学习领域中,聚类算法是一种非常重要的无监督学习技术,主要用于发现数据集中的结构或模式。本篇文章将详细介绍MATLAB环境下两种常见的聚类算法:层次聚类...

    各种聚类算法的比较.doc

    基于密度的聚类算法的代表有DBSCAN、DENCLUE、OPTICS、DBCLASD、CURD等。DBSCAN算法的特点是不断生长足够高密度的区域。基于网格的聚类算法的代表有STING、STING+、CLIQUE、WaveCluster等。STING算法的特点是基于...

    实验二 聚类算法,聚类分析的算法,matlab源码.zip

    聚类算法有多种类型,包括层次聚类(凝聚型和分裂型)、划分聚类(如K-Means)以及基于密度和网格的聚类(如DBSCAN和OPTICS)。这些算法都有各自的优缺点,适用于不同的数据分布和应用场景。例如,K-Means算法简单...

    OPTICS.rar_8CLZ_earndht_fightingmkz_optics算法_optics聚类

    标题中的"8CLZ_earndht_fightingmkz"可能是指不同的项目或任务名称,而"optics算法"和"optics聚类"是关键词,表示这个压缩包文件包含与OPTICS聚类算法相关的代码、数据或结果。描述中的"主程序、副程序和数据"暗示了...

    聚类算法综述.docx

    3. 基于密度的聚类算法:基于密度的聚类算法是一种无参数的聚类算法,通过计算数据点之间的距离和密度来确定聚类。其代表算法有 DBSCAN、OPTICS 等。 4. 基于网格的聚类算法:基于网格的聚类算法是一种基于网格的...

Global site tag (gtag.js) - Google Analytics