(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210459527.5 (22)申请日 2022.04.27 (71)申请人 中山大学 地址 510275 广东省广州市海珠区新港西 路135号 (72)发明人 卢宇彤　张元胤　陈志广　 (74)专利代理 机构 深圳市创富知识产权代理有 限公司 4 4367 专利代理师 高冰 (51)Int.Cl. G06F 9/50(2006.01) G06F 9/54(2006.01) G06K 9/62(2022.01) G06V 10/762(2022.01) (54)发明名称 一种基于DBSCAN算法的大规模数据分析方 法 (57)摘要 本发明公开了一种基于DBSCAN算法的大规 模数据分析方法， 包括如下步骤： 步骤一、 通过环 形通信计算邻接表； 步骤二、 局部初步确定核心 点的临时簇号； 步骤三、 轮流广播同步核心点簇 号； 步骤四、 反向环形通信更新边界点簇号。 本发 明能很好地解决DBSCAN算法在大规模数据聚类 分析中的效率问题， 本发明巧 妙地分解DBSCAN算 法递归计算过程计算步骤依 赖问题， 使其适用于 分布式的执行模 型， 使得集群中不同结点的工作 负载尽量平衡。 极大减少分布式计算中的通信 量， 并利用非阻塞通信方式让计算和通信重叠， 减少空闲等待时间。 充分利用计算结点的内存， 使得集群上的海量数据聚类分析成为现实。 权利要求书2页 说明书5页 附图4页 CN 114706688 A 2022.07.05 CN 114706688 A 1.一种基于DBSCAN 算法的大规模数据分析 方法， 其特 征在于， 包括如下步骤： 步骤一、 通过环形通信计算邻接表； 步骤二、 局部初步确定核心点的临时簇号； 步骤三、 轮流广播同步核心点簇号； 步骤四、 反向环形通信更新 边界点簇号。 2.根据权利 要求1所述一种基于DBSCAN算法的大规模数据分析方法， 其特征在于， 所述 步骤一包括如下步骤： 步骤S1、 将数据集平均分发到集群中的计算结点后， 在每个计算结点内计算数据对象 的距离， 然后整理成一个内部数据对象的邻接表和领域对象数量表； 步骤S2、 通过环形通信的方式计算 跨结点间数据的邻接关系。 3.根据权利 要求1所述一种基于DBSCAN算法的大规模数据分析方法， 其特征在于， 所述 步骤二中局部初步确定核心 点的临时簇号， 其具体为： 任意选定一个核心点， 为这个核心 点 分配簇号为自己本身的ID， 然后根据邻接表确定它的Eps领域内的所有核心 点， 接着对 所有 核心点分配簇号； 然后对Eps邻域内的其它所有 核心点递归执行该过程。 4.根据权利 要求1所述一种基于DBSCAN算法的大规模数据分析方法， 其特征在于， 所述 步骤四包括如下步骤： 步骤S41： 建立本地的簇号等价表， 簇号等价表 具体形式为CIDs→CIDt数组， 表示 临时簇 号CIDs和CIDt在聚类算法的结果中属于同一个簇号， 而在数值上CIDs≤CIDt； 步骤S42： 包括 步骤S421和步骤S42 2， 所述步骤S421和步骤S42 2同时进行， 所述步骤S421： 以计算结点 Ni中心， 向计算结点 集合 广播自身的核心点， 然后接收方根据Ni的核心点和 邻接表确定核心点的簇号； 所述步骤S422为如果 那么将计算结点Nj 的核心点 集广播到集 合{Nt|0≤t≤i}， 由集 合中的结点计算出其簇号， 并将结果返回给Nj； 步骤S43： 采用二叉树的通信方式统一簇号 等价表； 步骤S44： 所有结点 根据接收到的簇号 等价表更新结点内核心点簇号。 5.根据权利 要求1所述一种基于DBSCAN算法的大规模数据分析方法， 其特征在于， 所述 步骤四、 反向环形通信更新边界点簇号， 其具体为每个结点根据邻接表， 计算好其它结点的 边界点的簇号， 然后将其返回给其它结点。 6.根据权利 要求4所述一种基于DBSCAN算法的大规模数据分析方法， 其特征在于， 所述 步骤S43具体为： 首先是结点N2k+1将簇号等价表发送到N2k， 采用并查集的方式整合； 然后将 N4k+2簇号表统一到N4k完成整合,如此继续下去， 最后汇 集到0号结点上， 再由0号结点将最终 簇号等价表广播到各个结点。 7.根据权利 要求4所述一种基于DBSCAN算法的大规模数据分析方法， 其特征在于， 所述 步骤S421具体为扫描接收结点中的核心点， 查看其邻接表， 如果有Ni中的核心点则开始更 新簇号： 如果该核心点的簇号CID是原来的局部临时簇号， 那么就赋予其簇号， 然后将原局 部临时簇号对应的所有本地数据对象更新簇号； 如果在更新过程中发现已经分配了其它结 点的簇号， 这种冲突表示三者共属于同一簇， 那么就将这两个簇号记录到临时的本地簇号权　利　要　求　书 1/2 页 2 CN 114706688 A 2等价表中， 记录方式是新建一个CIDs→CIDt对。权　利　要　求　书 2/2 页 3 CN 114706688 A 3