CN115658809B 一种基于局部方向中心性的数据分布式聚类方法及装置 （武汉大学）

一种基于局部方向中心性的数据分布式聚本发明公开了一种基于局部方向中心性的建优先搜索K_means树全局索引，并共享索引变处理优化两个角度对CDC聚类算法进行分布式优2S5：分布式集群的主节点根据局部类簇的最大可达距离进行分区间局部类簇的合并，对局部类簇中每个内部点的可达距离进行排序，得到最大根据最大可达距离以及两个类簇之间的距离不大于两簇可达距离之和的连接规则进行分区间类簇合并，即D(C.Gn)≤RtRh，并更新类簇ID，生成完整的类簇，其中，为C、CP中取得最大可达距离的内部点之间的距离。3S2.7：通过分布式集群的主节点将优先搜索K_means树全局索引变量分发至各工作节S4.1：基于优先搜索K_means树的全局索引结构对各分区内待聚类数据进行k近邻搜;离，d(p,p)为内部点p;与内部点pj之间的距离；全局索引构建模块，用于基于读取的待聚类的完整数据构建优先搜索K_means树全局数据分区模块，用于结合数据采样和Hilbert曲线分区方法对待聚类的完整数据进行4全局合并模块，用于通过分布式集群的主节点根据局部类簇的最对局部类簇中每个内部点的可达距离进行排序，得到最大根据最大可达距离以及两个类簇之间的距离不大于两簇可达距离之和的连接规则进行分区间类簇合并，即D(C。,CP)≤Ra+RP，并更新类簇ID，生成完整的类簇，其中，为C、CP中取得最大可达距离的内部点之间的距离。9.一种计算机设备，包括存储器、处理器及5和边界点。据此，局部方向中心性聚类算法CDC通过建立局部方向中心性量度(DirectionCentralityMetric,DCM)衡量数据点K最近邻(K_NearestNeighbor,KNN)分布的方向均匀[0003]并行化已成为目前聚类算法性能优化的热点。常用分布式计算框架包括Hadoop、上提高了大数据聚类的效率；然而Spark默认分区策略因忽视了类簇的空间邻近性容易导解决或者至少部分解决现有技术中存在的计算效率不高和分区效果不佳6对应的分区ID，通过分布式集群的主节点将分区ID对应的分区数据发送至对应的工作节值之间的关系划分内部点和边界点，再基于内部点到边界点的可达距离进行内部点的合[0024]S2.7：通过分布式集群的主节点将优先搜索K_7[0036]S4.3：合并分区所有数据点imm)为内部点pi与边界点qm之间j的可达距[0041]对局部类簇Cα中每个内部点的可达距离进行排序，得到最大可达距离Rα=max[0042]根据最大可达距离以及两个类簇之间的距离不大于两簇可达距离之和的连接规[0046]全局索引构建模块，用于基于读取的待聚类的完整数据构建优先搜索K_means树[0047]数据分区模块，用于结合数据采样和Hilbert曲线分区方法对待聚类的完整数据8心性聚类算法实现了在分布式集群环境下的数据聚类，该方法基于优先搜索K_means树索引提高局部聚类中近邻搜索的效率，并且基于数据采样和Hilbert曲线分区方法优化并行样和Hilbert曲线的分区方法同时顾及了分区效率和数据分布的空间邻近性，不仅通过数据采样减少分区计算的数据量来提高分区速度，并且结合具有较好空间聚集特征的9[0070]本发明要解决的技术问题在于针对CDC聚类算法处理海量数据时计算效率低及Spark默认分区策略的数据倾斜问题，如何加快算法流程中的近邻搜索实现更高效的数据点划分，并设计快速均衡的数据分区方法来提高并行分布式系统的整体性能及CDC聚类算优先搜索K_means树索引加速最近邻搜索，降低算法计算复杂度；并结合数据采样和对应的分区ID，通过分布式集群的主节点将分区ID对应的分区数据发送至对应的工作节值之间的关系划分内部点和边界点，再基于内部点到边界点的可达距离进行内部点的合据场景下CDC聚类算法的可计算性问题和ApacheSpark原生数据分区方案的数据倾斜问[0098]S2.7：通过分布式集群的主节点将优先搜索K_[0110]S4.3：合并分区所有数据点imm)为内部点pi与边界点qm之间j的可达距[0116]对局部类簇Cα中每个内部点的可达距离进行排序，得到最大可达距离Rα=max[0117]根据最大可达距离以及两个类簇之间的距离不大于两簇可达距离之和的连接规[0121]本发明公开了一种基于优先搜索K_means树近邻搜索和基于数据采样和Hilbert曲线数据分区的局部方向中心性聚类算法(ClusteringbyLocalDirection骤，即首先基于全局索引分别对各分区内待聚类数据执行K最近邻搜索并对每个数据点计类结果输出到分布式文件系统中。针对数据海量数据场景下CDC聚类算法面临的可计算性[0122]为了更清楚地说明本发明公开的技术方案的有益效果，具体实施例中选取6个不同数据分布的二维人造数据集(如图1所示)开展[0124]图2和图3也从真实数据集上的聚类精度与执行时间视角将原有单机算法与本申[0125]下面将以ApacheSpark为例对实施过程进行说明，测试单机配置为4核8线程[0126]本发明通过局部方向中心性聚类算法分布式优化与加速方法提升算法对大规模[0129]在主节点上对待聚类数据构建基于优先搜索K_means树全[0132]在主节点上根据局部类簇的最大可达距离进行分区间类簇合并如图9所示，同时[0139]局部聚类模块4，用于通过分布式集群的各个工作节点并行执行CDC局部聚类算[0140]全局合并模块5，用于通过分布式集群的主节点根据局部类簇的最大可达距离进[0142]由于本发明实施例二所介绍的装置为实施本发明实施例一中基于局部方向中心实施例一中方法所采用的装置都属于本发明所欲[0145]由于本发明实施例三所介绍的计算机可读存储介质为实施本发明实施例一中基[0149]由于本发明实施例四所介绍的计算机设备为实施本发明实施例一中基于局部方本发明实施例一中方法所采用的计算机设备都属于本发明所欲保护现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定