Weka算法Clusterers-DBSCAN源代码分析

Weka算法Clusterers-DBSCAN源代码分析

大家好,又见面了,我是全栈君。

假设说世界上仅仅能存在一种基于密度的聚类算法的话。那么它必须是DBSCAN(Density-based spatial clustering of applications with noise)。DBSCAN作为基于密度聚类算法的典型,相对于Kmeans,最大长处是能够自己决定聚类数量。同一时候能够过滤一些噪点。但相对的。对传入的參数较为敏感,而且參数调优全靠经验。


一、算法

对于算法部分仅仅做一些”感性“的分析。详细算法的理论证明以及更精确的形式化描写叙述參考Wiki:http://en.wikipedia.org/wiki/DBSCAN

DBSCAN算法相对于简单,仅仅要弄清几个概念,算法本身是水到渠成的。

(1)几个变量

领域半径e,最小数目minOpt

(2)几个名词

核心对象:若一个对象其领域半径e内的对象数量大于等于minOpt,则称该对象为核心对象。

直接密度可达:若一个核心对象p,其领域半径内有若干点q,则对于每个q有q从对象p直接密度可达。

(3)算法流程

主流程:输入e,minOpt以及对象集合n

I、找到一个未标记的核心对象k,并设此对象为已标记。若找不到核心对象直接退出

II、扩展此核心对象,expand(k)

III、若全部对象均已标记,则退出,否则转I

expand流程:输入核心对象k

I、初始化一个集合S。放入k

II、遍历该集合元素。对于集合中每个核心对象,找到其全部未标记的的密度可达对象,放入集合S,并设为已标记

III、若II没有增加不论什么新对象。则退出。否则转II


在分析Weka的实现时。除了代码本身,着重关心下面几点:

(1)是否使用了特殊的数据结构来提高效率

(2)缺失值的处理

(3)噪声的处理

(4)其他实现技巧

(5)和原始DBSCAN不同之处


二、SequentialDatabase类

在分析详细的buildClusterer方法之前,先分析SequentialDatabase类,该类是DBSCAN方法用到的一个辅助类。封装一个instance并暴露一些定制的查询操作。

(1)epsilonRangeQuery,该函数用于查找离一个给定对象queryDataObject距离epsilon之内的全部对象

public List epsilonRangeQuery(double epsilon, DataObject queryDataObject) {
        ArrayList epsilonRange_List = new ArrayList();
        Iterator iterator = dataObjectIterator();
        while (iterator.hasNext()) {
            DataObject dataObject = (DataObject) iterator.next();
            double distance = queryDataObject.distance(dataObject);//默认的。距离计算器是欧式距离
            if (distance < epsilon) {
                epsilonRange_List.add(dataObject);
            }
        }

        return epsilonRange_List;
    }

能够看出该函数遍历了全部的对象。因此时间复杂度为O(n)

(2)返回一个List,当中Index0是距离近期的k个对象。index1是小于epsilon距离的对象

 public List k_nextNeighbourQuery(int k, double epsilon, DataObject dataObject) {
        Iterator iterator = dataObjectIterator();

        List return_List = new ArrayList();
        List nextNeighbours_List = new ArrayList();
        List epsilonRange_List = new ArrayList();

        PriorityQueue priorityQueue = new PriorityQueue();

        while (iterator.hasNext()) {
            DataObject next_dataObject = (DataObject) iterator.next();
            double dist = dataObject.distance(next_dataObject);

            if (dist <= epsilon) epsilonRange_List.add(new EpsilonRange_ListElement(dist, next_dataObject));

            if (priorityQueue.size() < k) {
                priorityQueue.add(dist, next_dataObject);
            } else {
                if (dist < priorityQueue.getPriority(0)) {
                    priorityQueue.next(); //把最大距离的移除,来实现一个固定长度的队列
                    priorityQueue.add(dist, next_dataObject);
                }
            }
        }

        while (priorityQueue.hasNext()) {
            nextNeighbours_List.add(0, priorityQueue.next());//将优先队列写到list中,每次都加入到index0能够看出这个List是个升序list。

} return_List.add(nextNeighbours_List); return_List.add(epsilonRange_List); return return_List; }

这个函数的设计必须吐槽:第一基于约定的编程,约定了Index0和index1的数据。而且还约定了当中的list所存储的对象。还约定了优先队列中元素升序排列,使得这个函数重用性及其之低。

第二和epsilonRangeQuery相比有部分反复的地方(但又不能调用epsilonRangeQuery,由于调用了相当于全部对象遍历两次)。

(3)coreDistance。该函数不仅返回了上面函数的list,还加入了index3为离得最远的而且小于epsilon的对象。

public List coreDistance(int minPoints, double epsilon, DataObject dataObject) {
        List list = k_nextNeighbourQuery(minPoints, epsilon, dataObject);

        if (((List) list.get(1)).size() < minPoints) {
            list.add(new Double(DataObject.UNDEFINED));
            return list;
        } else {
            List nextNeighbours_List = (List) list.get(0);
            PriorityQueueElement priorityQueueElement =
                    (PriorityQueueElement) nextNeighbours_List.get(nextNeighbours_List.size() - 1);
            if (priorityQueueElement.getPriority() <= epsilon) {
                list.add(new Double(priorityQueueElement.getPriority()));
                return list;
            } else {
                list.add(new Double(DataObject.UNDEFINED));
                return list;
            }
        }
    }

三、buildClusterer

接着从buildClusterer说起,该函数是全部聚类器的入口。用于使用已知样本训练一个聚类器。

函数本身是比較简单的。

  public void buildClusterer(Instances instances) throws Exception {
        // 先測一下这个Instance是否能用dbscan进行聚类。dbscan差点儿可处理全部的类型(枚举、日期、数值、missingValue)
        getCapabilities().testWithFail(instances);

        long time_1 = System.currentTimeMillis();

        processed_InstanceID = 0;
        numberOfGeneratedClusters = 0;
        clusterID = 0;

        replaceMissingValues_Filter = new ReplaceMissingValues();
        replaceMissingValues_Filter.setInputFormat(instances);
        Instances filteredInstances = Filter.useFilter(instances, replaceMissingValues_Filter);

        database = databaseForName(getDatabase_Type(), filteredInstances);
        for (int i = 0; i < database.getInstances().numInstances(); i++) {
            DataObject dataObject = dataObjectForName(getDatabase_distanceType(),
                    database.getInstances().instance(i),
                    Integer.toString(i),
                    database);
            database.insert(dataObject);//插入到数据库
        }
        database.setMinMaxValues();

        Iterator iterator = database.dataObjectIterator();
        while (iterator.hasNext()) {//对于全部节点进行迭代并非最高效的,假设使用一个变量记录当前unclassfied的数量,当为0的时候直接退出更为高效一些,尽管时间复杂度没有变化。

DataObject dataObject = (DataObject) iterator.next(); if (dataObject.getClusterLabel() == DataObject.UNCLASSIFIED) { if (expandCluster(dataObject)) {//假设某个点未标记,则尝试进行扩展 clusterID++; numberOfGeneratedClusters++; } } } long time_2 = System.currentTimeMillis(); elapsedTime = (double) (time_2 - time_1) / 1000.0;//非常奇怪,weka的实现具有不同的编程风格,起码以往的聚类器或者分类器。并没有直接在训练函数中来计算所用时间。

}


四、expandCluster

扩展核心节点为一个簇的主函数,若成功扩展返回true,否则返回false,例如以下:

private boolean expandCluster(DataObject dataObject) {
        List seedList = database.epsilonRangeQuery(getEpsilon(), dataObject);//该函数寻找给定对象距离epsilon以内的对象
        if (seedList.size() < getMinPoints()) {
            dataObject.setClusterLabel(DataObject.NOISE);//假设是非核心对象。临时设置为noise,之后假设不能被核心对象聚类到就一直是noise了。
            return false;
        }

        //走到这里都是核心对象
        for (int i = 0; i < seedList.size(); i++) {
            DataObject seedListDataObject = (DataObject) seedList.get(i);
            seedListDataObject.setClusterLabel(clusterID);//全部seedList里的对象都从属于clusterID,这个clusterID是一个自增量
            if (seedListDataObject.equals(dataObject)) {
                seedList.remove(i);//注意epsilonRangeQueryList会把參数对象本身也放进去。所以这里要移除
                i--;
            }
        }

        for (int j = 0; j < seedList.size(); j++) {
            DataObject seedListDataObject = (DataObject) seedList.get(j);
            List seedListDataObject_Neighbourhood = database.epsilonRangeQuery(getEpsilon(), seedListDataObject);
           //对于seedList中每个元素都寻找其领域内的元素
            if (seedListDataObject_Neighbourhood.size() >= getMinPoints()) {
                for (int i = 0; i < seedListDataObject_Neighbourhood.size(); i++) {//走到这个循环内说明是核心对象
                    DataObject p = (DataObject) seedListDataObject_Neighbourhood.get(i);
                    if (p.getClusterLabel() == DataObject.UNCLASSIFIED || p.getClusterLabel() == DataObject.NOISE) {<span style="white-space:pre">		</span>
                        if (p.getClusterLabel() == DataObject.UNCLASSIFIED) {
                            seedList.add(p);//假设是未分类的,就加到seedList中。这里使用了unclassified来保证不会加入反复,并且nosie不加入是由于noise肯定不是核心对象(本函数开头逻辑保证)这也算是一个trick。使用了一个list加下标起到了set的效果,假设让我来实现预计我会直接用set吧
                        }
                        p.setClusterLabel(clusterID);//设置成对应的聚类
                    }
                }
            }
            seedList.remove(j);//不是非常明确这里为啥要remove。按理说遍历之后不会再訪问不是必需删除了。也许为了节省内存。也也许是作者强迫症(这段代码的作者貌似不喜欢用迭代器,并且多次使用基于下标的删除,在java中这并非一个非常优雅的编程方式,尽管我也常常这么用)
            j--;
        }

        return true;
    }


五、时间复杂度分析

buildClusterer函数主循环为n,expandCluster函数对list中每一个元素调用eplisonRangeQuery。因此是n^2,总结来看是整个算法是n^3,并非非常高效。

优化点:

buildClusterer并不能产生优于O(n)的优化,但能够使用计数器记录未标记的数量来提高一些效率,expandCluster也没什么优化点。但eplisonRangeQuery起码有两个地方能够优化,第一个是使用KDTree(就像Xmean算法一样,參见之前的博客)来更有效寻找离给定点距离近期的距离,其次是使用Cache来缓存一些给定点对的距离。由于考虑到同样的点在程序中事实上是被计算了多次的。


六、clusterInstance

这个函数接收一个instance作为參数,理应返回该instance从属的cluster。但DBSCAN貌似并没有这么做。

    public int clusterInstance(Instance instance) throws Exception {
        if (processed_InstanceID >= database.size()) processed_InstanceID = 0;
        int cnum = (database.getDataObject(Integer.toString(processed_InstanceID++))).getClusterLabel();
        if (cnum == DataObject.NOISE)
            throw new Exception();
        else
            return cnum;
    }

依次返回的是id为0,1,2的用例的下标,不知道这么做的用意何在。

并且假设是个noise直接抛出异常,并且根本就不说明为啥抛这个异常。

整个函数意义不明。


七、总结

假设非要写个总结的话,那么我个人对于这段代码是比較失望的,不管是一些函数抽象的设计,数据结构的设计,Java代码风格,都有一种浓浓的”业余“的味道,和之前分类器整洁的代码相比全然是判若两人(好吧本来也不是一个人写的)。

除此之外最后的clusterInstance的行为和凝视全然不符,不知道是个bug还是feature还是其他什么原因导致的。



版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115705.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • java中byte的用法_澄清池的工作原理

    java中byte的用法_澄清池的工作原理缓冲区在计算机世界中随处可见,内存中的多级缓冲区,io设备的缓冲区等等,还有我们经常用的内存队列,分布式队列等等。缓冲区,平衡了数据产生方和数据消费方的处理效率差异,提高了数据处理性能。JDK为了解决网络通信中的数据缓冲问题,提供了ByteBuffer(heap或者直接内存缓存)来解决缓存问题,通过缓冲区来平衡网络io和CPU之间的速度差异,等待缓冲区积累到一定量的数据再统一交给CPU去处理,从而…

  • iterator的用法_名词所有格的用法整理初一

    iterator的用法_名词所有格的用法整理初一@Overrideprotectedvoidreduce(Textkey,Iterable<IntWritable>values,Contextcontext)throwsIOException,InterruptedException{intcount=0;Iterator<IntWritable>iterator=values.iterator();//<1,1,1>

    2022年10月24日
  • 关系数据库理论之最小函数依赖集「建议收藏」

    关系数据库理论之最小函数依赖集「建议收藏」前言在本文中,会介绍为什么要引入最小函数依赖集,最小函数依赖集是什么,以及如何求最小函数依赖集。为什么需要最小函数依赖集在关系数据模型中,一个关系通常由R(U,F)构成,U为属性的全集,F为函数依赖集。在实际生活中,我们可以根据语义来定义关系中属性的依赖关系,例如学号可以唯一确定一位学生的姓名、性别等等。但是,有时候给出的函数依赖集并不是最简的,这有时会拖累我们对关系的后续处理,例如关系的分…

  • plsql 注册码「建议收藏」

    plsql 注册码「建议收藏」plsql下载地址https://www.allroundautomations.com/bodyplsqldevreg.html12.0.3.182164bit:注册码:ProductCode(产品编号):jtrexa75fat2mgcetfhx767laqrbtssqrkserialNumber(序列号):335566password:xs374ca12.0…

  • java基本数据类型有哪些_java中有八种基本数据类型

    java基本数据类型有哪些_java中有八种基本数据类型在java中有八种基本数据类型对应每种基本类型又有八种包装类型:基本类型:boolean,char,int,byte,short,long,float,double包装器类型:Boolean,Character,Integer,Byte,Short,Long,Float,Double从上面我们可以看到除了char和int其它的包装类型名称和对应的基本类型一样只是首字母大写了。既然有了基本…

  • pycharm安装教程-pycharm安装详细步骤(Mac版)

    pycharm安装教程-pycharm安装详细步骤(Mac版)上期跟大家讲了怎么安装Python,这期跟大家介绍个很好用的编程工具–pycharm。PyCharm是一种PythonIDE,带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具,比如调试、语法高亮、Project管理、代码跳转、智能提示、自动完成、单元测试、版本控制。Pycharm分为专业版(Professional)和社区版(Community),专业版功能非常全,需要购买,可以试用,对比之下社区版功能有限,可以免费使用,并且开源。如果大家只是不需要做特别复杂的项目,下载社区版就足够

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号