一种基于密度的大型空间数据聚类算法K‑DBSCAN

摘要

本发明具体涉及一种基于密度的大型空间数据聚类算法K‑DBSCAN，通过预设基于密度聚类参数：预设半径R、最小近邻数量Min_N、预划分数量K、划分迭代次数T；之后将数据集按照空间分布进行划分为K

说明书

技术领域

本发明涉及数据挖掘和大数据分析领域，具体涉及一种基于密度的大型空间数据聚类算法K-DBSCAN。

背景技术

空间数据聚类被广泛的使用于许多信息技术领域，例如数据挖掘、模式识别、机器学习、人工智能、可视分析、地理信息系统等。尤其在大数据时代中，它可用来探索有意义但尚未知晓的潜在的模式及现象，可应用于许多学科领域，例如社会网络分析、经济网络分析、交通网络分析、气象分析、智慧城市发展等。传统的基于距离计算的空间数据聚类方法主要有三种：1)、基于划分的聚类；2)、基于密度的聚类；3)、层次聚类。

基于密度的聚类可以有效的处理噪声点以及识别任意形状，主要算法包括：DBSCAN(Density-Based Spatial Clustering of Applications with Noise)、OPTICS(Ordering points to identify the clustering structure)、DENCLUE(DENsity bastedCLUstEring)等。其中，DBSCAN是最著名的基于密度的空间聚类算法。其计算复杂度为O(N²)，即当数据量增长100倍时，其计算时间将增加约10000倍。尽管已有许多基于计算并行化的方法来大幅降低计算所需时间，但仍受限于计算平台中CPU或GPU的数量。例如，要在相同的计算时间内进行100倍数据量的DBSCAN聚类，则需要约10000倍的CPU或GPU数量。因此在面临海量数据时，DBSCAN无法被广泛应用。

发明内容

本发明要解决的是现有技术中针对大量数据需要进行聚类时DBSCAN无法适用的技术问题。

为了解决上述技术问题，本发明提供如下技术方案：

一种基于密度的大型空间数据聚类算法K-DBSCAN，包括：

将数据集划分为K₁个数据子集，其中K₁为大于1的自然数；

获取每一数据子集的可达子集，并形成与该数据子集对应的可达子集索引；

根据所述可达子集索引对各数据子集数据进行基于密度的空间聚类。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述将数据集划分为K₁个数据子集，其中为K₁大于1的自然数，具体包括：

获取所述数据集的实际空间范围值D_len；

根据所述数据集的实际空间范围值D_len对所述数据集中的数据点进行预划分得到K个预分类，其中K为大于1的自然数；

预分类步骤，获取每个预分类的中心点所在位置，并将所述数据集中的每一数据点分配至与之距离最近的中心点所在的预分类中，若某一预分类中的数据点数量小于预设最小近邻数量Min_N，则删除该预分类；

重复所述预分类步骤T次，得到K₁个数据子集，其中T为预设的划分迭代次数。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述获取所述数据集的实际空间范围值D_len，具体包括：

获取所述数据集的最大空间范围值D_max和最小空间范围值D_min，其中D_max＝LN_max+LA_max，D_min＝LN_min+LA_min，LN_max为所述数据集中所有数据点的经度最大值，LA_min为所述数据集中所有数据点的经度最小值，LN_min为所述数据集中所有数据点的纬度最小值，LA_max为所述数据集中所有数据点的纬度最大值；

获取所述数据集的实际空间范围值D_len＝D_max－D_min。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述根据所述数据集的实际空间范围值D_len对所述数据集中的数据点进行预划分得到K个预分类，其中K为大于1的自然数，具体包括：

对于所述数据集中的任意一个数据点a，按照以下计算方法获得其所属的预分类：其中LNa为数据点a的经度值，LAa为数据点a的纬度值。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述获取每一数据子集的可达子集，并形成与该数据子集对应的可达子集索引，具体包括：

根据所述数据子集中所有数据点的经度值和纬度值，确定所述数据子集的最大经度值LO_max、最小经度值LQ_min、最小纬度值LO_min、最大纬度值LQ_max；

获取每一所述数据子集的可达空间覆盖范围：LO_right＝LO_max+d，LO_left＝LO_min–d，LQ_up＝LQ_max+d，LQ_down＝LQ_min-d,其中d为预设可达距离，LQ_up、LO_right、LQ_down、LO_left分别为所述数据子集的可达空间覆盖范围的上边界、右边界、下边界和左边界；

为每个所述数据子集计算其可达子集列表，计算方法为：对于任意的数据子集P_a和数据子集P_b，若数据子集P_a的可达空间覆盖范围与数据子集P_b的可达空间覆盖范围存在交集，则确定数据子集P_a和数据子集P_b互相可达，且每一数据子集都是自身的可达子集，记为RPL_a＝{a,b…}和RPL_b＝{a,b…}；每一数据子集的所有可达子集构成该数据子集的可达子集列表，

得到每个所述数据子集的可达子集列表后，将所有K₁个数据子集的可达子集列表按照数据子集顺序进行排列，得到可达子集索引。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，当数据子集P_a的可达空间覆盖范围与数据子集P_b的可达空间覆盖范围存在如下任意一种关系时，可确定数据子集P_a的可达空间覆盖范围与数据子集P_b的可达空间覆盖范围存在交集：

关系一：(LO_{left_a}<LO_{left_b}<LO_{right_a})且(LQ_{down_a}<LQ_{up_b}<LQ_{up_a})；

关系二：(LO_{left_a}<LO_{left_b}<LO_{right_a})且(LA_{down_a}<LQ_{down_b}<LQ_{up_a})；

关系三：(LO_{left_a}<LO_{right_b}<LO_{right_a})且(LQ_{down_a}<LQ_{up_b}<LQ_{up_a})；

关系四：(LO_{left_a}<LO_{right_b}<LO_{right_a})且(LA_{down_a}<LA_{down_b}<LA_{up_a})；

关系五：(LO_{left_a}<LO_{left_b}<LO_{right_a})且(LQ_{down_a}>LQ_{down_b}&LQ_{up_a}<LQ_{up_b})；

关系六：(LO_{left_a}<LO_{right_b}<LO_{right_a})且(LQ_{down_a}>LQ_{down_b}&LQ_{up_a}<LQ_{up_b})；

关系七：(LO_{left_a}>LO_{left_b}且LO_{right_a}<LO_{right_b})且(LQ_{down_a}<LQ_{up_b}<LQ_{up_a})；

关系八：(LO_{left_a}>LO_{left_b}且LO_{right_a}<LO_{right_b})且(LQ_{down_a}<LQ_{down_b}<LQ_{up_a})；

关系九：(LO_{left_a}>LO_{left_b})且(LO_{right_a}<LO_{right_b})且(LQ_{up_a}<LQ_{up_b})且(LQ_{down_a}>LQ_{down_b})；

其中，LQ_{up_a}、LO_{right_a}、LQ_{down_a}、LO_{left_a}分别为数据子集P_a的可达空间覆盖范围的上边界、右边界、下边界和左边界；LQ_{up_b}、LO_{right_b}、LQ_{down_b}、LO_{left_b}分别为数据子集P_b的可达空间覆盖范围的上边界、右边界、下边界和左边界。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述根据所述可达子集索引对各数据子集数据进行基于密度的空间聚类，具体包括：

根据所述可达子集索引计算每一数据子集的核心点；

分别对每个数据子集中的核心点进行聚类。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述根据所述可达子集索引计算每一数据子集的核心点，具体包括：

步骤11：按顺序从K₁个数据子集中选取数据子集a，从数据子集a中按顺序选取数据点P_i，设数据点P_i的近邻点数量N_i的初始值为0，分类标签CF为1；

步骤12：从数据子集a的可达子集列表中按顺序选取数据子集b；

步骤13：从数据子集b中按顺序选取数据点P_j；

步骤14：计算数据点P_i与数据点P_j之间的距离D_i,j，若距离D_i,j小于预设半径R，则确定数据点P_j是数据点P_i的近邻点，数据点P_i的近邻点数量N_i＝N_i+1；

步骤15：按照步骤13和14所述的方法，遍历数据子集b中的所有数据点，按照步骤14的方法计算得到数据点P_i的近邻点数量N_i；

步骤16：按照步骤12所述的方法，遍历数据子集a的可达子集列表中的所有可达数据子集，按照步骤15所述方法计算得到数据点P_i的近邻点数量N_i；

步骤17：每次计算得到数据点P_i的近邻点数量N_i后，均判断数据点P_i的近邻点数量N_i是否大于最小近邻数量Min_N，若是则数据点P_i为核心点，为数据点P_i加上分类标签CF_i＝CF，并为该步计算中最后一个近邻点P_k加上分类标签MF_a，且针对数据点P_i的核心点计算结束，令CF＝CF+1，并按照步骤11中的方法，选取下一个数据点P_i+1进行核心点计算；

步骤18：按照步骤11至步骤17所述的方法，按顺序遍历数据子集a中的每一个数据点，完成数据子集a中所有数据点的核心点计算；

步骤19：按照步骤11至步骤18所述的方法，按顺序遍历K₁个数据子集中的每一个数据子集，完成所有数据子集中所有数据点的核心点计算。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述计算每一数据子集的核心点，具体包括：

步骤21：按顺序从K₁个数据子集中选取数据子集a，从数据子集a中按顺序选取数据点P_i，设数据点P_i的近邻点数量N_i的初始值为0，分类标签CF为1；

步骤22：从数据子集a中按顺序选取数据点P_j；

步骤23：计算数据点P_i与数据点P_j之间的距离D_i,j，若距离D_i,j小于预设半径R，则确定数据点P_j是数据点P_i的近邻点，数据点P_i的近邻点数量N_i＝N_i+1；

步骤24：按照步骤22所述的方法，遍历数据子集a中的所有数据点，按照步骤23所述的方法，计算数据点P_i的近邻点数量N_i；

步骤25：每次计算得到数据点P_i的近邻点数量N_i后，均判断数据点P_i的近邻点数量N_i是否大于最小近邻数量Min_N，若是则数据点P_i为核心点，为数据点P_i加上分类标签CF_i＝CF，并为该步计算中最后一个近邻点P_k加上分类标签MF_a，且针对数据点P_i的核心点计算结束，令CF＝CF+1，并按照步骤21中的方法，选取下一个数据点P_i+1进行核心点计算；

步骤26：按照步骤21至步骤25所述的方法，遍历数据子集a中的每一个数据点，完成数据子集a中所有数据点的核心点计算；

步骤27：按照步骤21至步骤26所述的方法，遍历K₁个数据子集中的每一个数据子集，完成所有数据子集中所有数据点的核心点计算。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，根据所述的可达子集索引，分别对每个数据子集中的核心点进行聚类，具体包括：

步骤31：对每个数据子集中的所有核心点的MF值进行聚合，对于任意数据点P_i，如果其MF值存在，则令CF_i＝MF_i；

步骤32：按顺序从K₁个数据子集中选取数据子集a，从数据子集a中按顺序选取数据点P_i；

步骤33：从数据子集a的可达子集列表中按顺序选取数据子集b；

步骤34：从数据子集b中按顺序选取数据点P_j；

步骤35：若数据点P_i与数据点P_j的分类标签CF_i与CF_j相等，则执行步骤37；否则计算数据点P_i与数据点P_j的距离D_i,j，若距离D_i,j小于所述预设半径R，则执行步骤36，否则执行步骤37；

步骤36：判断分类标签CF_i与CF_j之间的大小关系：当CF_i<CF_j时,则令CF_j＝CF_i，当CF_i>CF_j时，则令CF_i＝CF_j；

步骤37：按照步骤34至步骤36所述的方法，遍历数据子集b中的每一个数据点；

步骤38：按照步骤33至步骤37所述的方法，遍历数据子集a的可达子集列表中的每一个可达子集中的每一个数据点，完成数据子集a中核心点P_i的聚类计算；

步骤39：按照步骤32至步骤38所述的方法，遍历数据子集a中的每一个数据点，完成数据子集a中的所有核心点的聚类计算；

步骤310：按照步骤31至步骤39所述的方法，按顺序遍历K₁个数据子集中的每一个数据子集，完成每一个数据子集中的每一个核心点的聚类计算。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述分别对每个数据子集中的核心点进行聚类，具体包括：

步骤41：对每个数据子集中的所有核心点的MF值进行聚合，对于任意数据点P_i，如果其MF值存在，则令CF_i＝MF_i；

步骤42：按顺序从K₁个数据子集中选取数据子集a，从数据子集a中按顺序选取数据点P_i和数据点P_j；

步骤43：判断数据点P_i与数据点P_j的分类标签CF_i与CF_j是否相等；若相等则执行步骤45，若不相等则计算数据点P_i与数据点P_j的距离D_i,j，若距离D_i,j小于所述预设半径R，则执行步骤44，否则执行步骤45；

步骤44：判断数据点P_i与数据点P_j的分类标签CF_i与CF_j的大小关系：当CF_i<CF_j时,则令CF_j＝CF_i，当CF_i>CF_j时，则令CF_i＝CF_j；

步骤45：按照步骤41至步骤44所述的方法，遍历数据子集a中的每一个数据点，完成数据子集a中所有核心点的聚类计算；

步骤46：按照步骤46至步骤45所述的方法，按顺序遍历K1个数据子集中的每一个数据子集，完成每一个数据子集中的每一个核心点的聚类计算。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，还包括如下步骤：

分别计算得到每个数据子集中的近邻点并对每个数据子集中的近邻点进行聚类。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述分别计算得到每个数据子集中的近邻点并对每个数据子集中的近邻点进行聚类，具体包括：

步骤51：按顺序从K1个数据子集中选取数据子集a，将数据子集a中的核心点作为一个子集，记为CG_a，非核心点作为一个子集NCG_a；

步骤52：按照步骤51所述的方法，遍历K1个数据子集，为所有数据子集划分核心点子集CG与非核心点NCG；

步骤53：按顺序从K1个数据子集中选取数据子集a，按顺序从数据子集a的非核心点子集NCG_a中选取非核心点NCP_i；

步骤54：按顺序从数据子集a的可达子集列表中选取数据子集b；

步骤55：按顺序从数据子集b的核心点子集CG_b中选取核心点CP_j；

步骤56：计算非核心点NCP_i与核心点CP_j之间的距离D_i,j，如果距离D_i,j小于所述预设半径R，则非核心点NCP_i是核心点CP_j的近邻点，并进行聚类：令CF_i＝CF_j；

步骤57：按照步骤55至步骤56中所述的方法，遍历数据子集b中的每一个核心点；

步骤58：按照步骤54至56中所述的方法，遍历数据子集a的可达子集列表中的每一个可达子集，完成非核心点NCP_i的聚类计算；

步骤59：按照步骤53至步骤58中所述的方法，按顺序遍历数据子集a中的每一个非核心点，完成数据子集a中所有非核心点的聚类计算；

步骤510：按照步骤53至步骤59中所述的方法，按顺序遍历K₁个数据子集中的每一个数据子集，完成每个数据子集中所有非核心点的聚类计算。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述分别计算得到每个数据子集中的近邻点并对每个数据子集中的近邻点进行聚类，具体包括：

步骤61：将K₁个数据子集中每一个数据子集中的核心点作为一个子集，记为CG，非核心点作为一个子集，记为NCG；

步骤62：按照步骤61所述的方法，遍历K₁个数据子集，为所有的数据子集划分核心点CG与非核心点NCG；

步骤63：按顺序从K₁个数据子集中选取数据子集a，从数据子集a中的非核心点子集NCG_a中按顺序选取非核心点NCP_i；从数据子集a中的核心点子集CG_a中按顺序选取核心点CP_j；

步骤64：计算点NCP_i与点CP_j之间的距离D_i,j，如果D_i,j小于预设半径R，则点NCP_i是点CP_j的近邻点，并进行聚类：令CF_j＝CF_i；

步骤65：按照步骤63至步骤64中所述的方法，按顺序遍历数据子集a中的每一个非核心点，完成数据子集a中的所有非核心点的聚类计算；

步骤66：按照步骤63至步骤65所述的方法，按顺序遍历K₁个数据子集中的每一个数据子集，完成每个数据子集中所有非核心点的聚类计算。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述预分类的数量K通过以下方式得到：

其中N是所述数据集中数据点的总数量，Min_N是预设最小近邻点数量，k为常数。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述预设的划分迭代次数T满足：1≤T≤10。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述预设可达距离d满足：设R≤d≤R×2，其中R为预设半径R。

可选地，上述的基于密度的大型空间数据聚类算法K-DBSCAN中，所述预设半径R替换为R′：R≤R′≤R×2。

本发明还提供一种执行基于密度的大型空间数据聚类算法K-DBSCAN的电子设备，其特征在于，包括：

至少一个处理器；以及

与所述至少一个处理器通信连接的存储器；其中，

所述存储器存储有可被所述一个处理器执行的指令，所述指令被所述至少一个处理器执行，以使所述至少一个处理器能够：

将数据集划分为K₁个数据子集，其中K₁为大于1的自然数；

获取每一数据子集的可达子集，并形成与该数据子集对应的可达子集索引；

根据所述可达子集索引对各数据子集数据进行基于密度的空间聚类。

本发明提供的上述技术方案，与现有技术相比，至少具有以下有益效果：本发明提出了一种基于密度的大型空间数据聚类算法K-DBSCAN，该算法首先利用一种简化的并行化k-means算法进行数据划分，其次利用一种可达子集索引来引导聚类，最后利用一种改进的分布式并行化聚类算法来进行空间聚类。该算法极大的降低了基于密度的空间数据聚类的计算复杂度，使得该算法可广泛应用于海量数据聚类。

附图说明

为了更清楚地说明本发明具体实施方式或现有技术中的技术方案，下面将对具体实施方式或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施方式，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明一个实施例所述基于密度的大型空间数据聚类算法K-DBSCAN的方法流程图；

图2为本发明一个实施例所述步骤采用改进的k-means聚类算法对数据集进行空间划分聚类的方法流程图；

图3为本发明一个实施例所述步骤S102的实现方法流程图；

图4为本发明一个实施例所述数据子集的空间覆盖范围示意图；

图5为本发明一个实施例所述不同数据子集互达的示意图；

图6为本发明一个实施例根据所述可达子集索引计算每一数据子集的核心点的实现方法流程图；

图7为本发明一个实施例所述根据可达子集索引对每个数据子集中的核心点进行聚类的实现方法流程图的实现方法流程图；

图8为本发明一个实施例所述计算得到每个数据子集中的近邻点并对每个数据子集中的近邻点进行聚类的实现方法流程图；

图9为本发明一个实施例所述执行基于密度的大型空间数据聚类算法K-DBSCAN的方法的电子设备的硬件结构连接示意图。

具体实施方式

实施例1

本实施例提供一种基于密度的大型空间数据聚类算法K-DBSCAN，如图1所示，包括：

S101：将数据集划分为K₁个数据子集，其中K₁为大于1的自然数。

S102：获取每一数据子集的可达子集，并形成与该数据子集对应的可达子集索引。

S103：根据所述可达子集索引对各数据子集数据进行基于密度的空间聚类。

上述方案中，首先将数据集进行数据划分，得到多个数据子集，其次利用一种可达子集索引来引导聚类，最后针对划分后的每一数据子集采用聚类算法来进行空间聚类。该算法极大的降低了基于密度的空间数据聚类的计算复杂度，使得该算法可广泛应用于海量数据聚类。

实施例2

上述步骤S101中，可以采用多种方式对数据集进行划分，具体地需要保证每一划分后得到的数据子集具有特定的空间和数据点。本实施例中提供一种实现方式，采用一种改进的k-means聚类算法对数据集进行空间划分聚类，包括：

具体地，如图2所示，包括如下步骤：

S201：分别计算出所述数据集中所有数据点的经度最大值LN_max、经度最小值LN_min和纬度最大值LA_max、纬度最小值LA_min；得到所述数据集的最大空间范围值D_max＝LN_max+LA_max和最小空间范围值D_min＝LN_min+LA_min，然后计算出所述数据集的实际空间范围值D_len＝D_max－D_min。

S202：根据所述实际空间范围值D_len对所述数据集中的数据点进行初始划分，具体算法为：对于任意数据点a，其所属预分类的计算公式为：其中LNa为数据点a的经度值，LAa为数据点a的纬度值。而K值可通过公式自动计算得到：N是数据集中数据点的总数量，Min_N是最小近邻点数量，k是任意常数。

S203：对于任意分类C_a，如果其成员数量小于预设最小近邻数量Min_N，则删除该预分类；

S204：分别计算每个预分类的中心点；

S205：然后计算每个数据点到每个所述中心点的距离，并将所述数据点分配到与之最近的所述中心点所在的预分类；

S206：重复执行步骤S203、S204、S205，迭代次数为T次，其中T可以选择为任意自然数，优选地T可以为：1≤T≤10；

S207：所述数据集中的数据点被划分到K₁个预分类中，每一个预分类即可作为一个数据子集，因此得到了K₁个数据子集。

上述步骤S102中，如图3所示，可通过如下方式实现：

S301：为每个所述数据子集P计算可达空间覆盖范围，计算方法为：对比数据子集P中所有数据点的经度值和纬度值，找出所有数据点中的最大经度值LO_max、最小经度值LQ_min、最小纬度值LO_min、最大纬度值LQ_max；再加上预设可达空间距离d，得到数据子集P的可达空间覆盖范围：LO_right＝LO_max+d，LO_left＝LO_min–d，LQ_up＝LQ_max+d，LQ_down＝LQ_min-d,其中，LQ_up、LO_right、LQ_down、LO_left分别为所述数据子集的可达空间覆盖范围的上边界、右边界、下边界和左边界。

如图4所示，矩形框内的数据点代表一个数据子集(也可以叫做一个预分类)，矩形内框代表了该数据子集的空间覆盖范围，矩形外框代表了该数据子集的可达空间覆盖范围。从图中可以看出，内框和外框之间的相差为预设可达空间距离d。作为一种可选的实现方式，所述可达空间距离d值可为任意数值，通常设R≤d≤R×2，R是预设半径。

S302：为每个所述数据子集P计算其可达子集列表RPL，计算方法为：对于任意的所述数据子集P_a和P_b，如果存在数据子集P_a的可达空间覆盖范围R_a，以及数据子集P_b的可达空间覆盖范围R_b，且范围R_a与范围R_b相交，则定义P_a与P_b互相可达，记为RPLa＝{a,b…}、RPLb＝{a,b…}，显然每个数据子集都是自己的可达子集。如图5所示，对于数据子集P₁，其可达空间覆盖范围R₁只与数据子集P₂、P₃、P₄的可达空间覆盖范围R₂、R₃、R₄相交，则P₁与P₂互相可达，P₁与P₃互相可达，P₁与P₄互相可达。上述步骤中，判断数据子集P_a和数据子集P_b是否相交可以通过判断其中的一个数据子集的边界是否落入另一个数据子集的边界内，具体地可概括为9种情况，可通过以下公式进行计算：

(1)(LO_{left_a}<LO_{left_b}<LO_{right_a})&(LQ_{down_a}<LQ_{up_b}<LQ_{up_a})

(2)(LO_{left_a}<LO_{left_b}<LO_{right_a})&(LQ_{down_a}<LQ_{down_b}<LQ_{up_a})

(3)(LO_{left_a}<LO_{right_b}<LO_{right_a})&(LQ_{down_a}<LQ_{up_b}<LQ_{up_a})

(4)(LO_{left_a}<LO_{right_b}<LO_{right_a})&(LQ_{down_a}<LQ_{down_b}<LQ_{up_a})

(5)(LO_{left_a}<LO_{left_b}<LO_{right_a})&(LQ_{down_a}>LQ_{down_b}&LQ_{up_a}<LQ_{up_b})

(6)(LO_{left_a}<LO_{right_b}<LO_{right_a})&(LQ_{down_a}>LQ_{down_b}&LQ_{up_a}<LQ_{up_b})

(7)(LO_{left_a}>LO_{left_b}&LO_{right_a}<LO_{right_b})&(LQ_{down_a}<LQ_{up_b}<LQ_{up_a})

(8)(LO_{left_a}>LO_{left_b}&LO_{right_a}<LO_{right_b})&(LQ_{down_a}<LQ_{down_b}<LQ_{up_a})

(9)(LO_{left_a}>LO_{left_b})&(LO_{right_a}<LO_{right_b})&(LQ_{up_a}<LQ_{up_b})&(LQ_{down_a}>LQ_{down_b})。

其中，&表示逻辑与，下角标中，right表示右边界，left表示左边界，up表示上边界，down表示下边界，a表示数据子集P_a，b表示数据子集P_b，因此对于每一符号所表示的含义，可根据下角标直接得到。

S303：通过步骤S302中所述公式分别为K₁个数据子集相对于其他各个数据子集进行计算，得到每个数据子集的所述可达子集列表RPL，并将所有K₁个数据子集的可达子集列表RPL按照子集顺序进行排列，得到一个可达子集索引RPI，记为RPI＝{RPL₁,...,RPL_K1}。

优选地，上述步骤S103可包括如下步骤：根据所述可达子集索引计算每一数据子集的核心点；分别对每个数据子集中的核心点进行聚类；分别计算得到每个数据子集中的近邻点并对每个数据子集中的近邻点进行聚类。

其中计算每一数据子集的核心点时，可以根据可达子集索引计算，也可以只在该数据子集自身的数据点范围内进行计算。只对每一数据子集中的核心点进行聚类，可以有效提高聚类速度，但是精度会受到一定程度的影响。

为此，可采用如图6所示的方案根据所述可达子集索引计算每一数据子集的核心点，包括如下步骤：

步骤11：按顺序从K₁个数据子集中选取数据子集a，从数据子集a中按顺序选取数据点P_i，设数据点P_i的近邻点数量N_i的初始值为0，分类标签CF为1；

步骤12：从数据子集a的可达子集列表中按顺序选取数据子集b；

步骤13：从数据子集b中按顺序选取数据点P_j；

步骤14：计算数据点P_i与数据点P_j之间的距离D_i,j，若距离D_i,j小于预设半径R，则确定数据点P_j是数据点P_i的近邻点，数据点P_i的近邻点数量N_i＝N_i+1；

步骤15：按照步骤13和14所述的方法，遍历数据子集b中的所有数据点，按照步骤14的方法计算得到数据点P_i的近邻点数量N_i；

步骤16：按照步骤12所述的方法，遍历数据子集a的可达子集列表中的所有可达数据子集，按照步骤15所述方法计算得到数据点P_i的近邻点数量N_i；

步骤17：每次计算得到数据点P_i的近邻点数量N_i后，均判断数据点P_i的近邻点数量N_i是否大于最小近邻数量Min_N，若是则数据点P_i为核心点，为数据点P_i加上分类标签CF_i＝CF，并为该步计算中最后一个近邻点P_k加上分类标签MF_a，且针对数据点P_i的核心点计算结束，令CF＝CF+1，并按照步骤11中的方法，选取下一个数据点P_i+1进行核心点计算；

步骤18：按照步骤11至步骤17所述的方法，按顺序遍历数据子集a中的每一个数据点，完成数据子集a中所有数据点的核心点计算；

步骤19：按照步骤11至步骤18所述的方法，按顺序遍历K₁个数据子集中的每一个数据子集，完成所有数据子集中所有数据点的核心点计算。

即针数据子集a的每一个数据点，按照顺序遍历每一个可达子集中的每一个数据点之后，再遍历数据子集a之外的其他数据子集，直到所有K₁个数据子集完成遍历。

需要说明的是，本发明实施例中所提供参数的下角标，可采用自然数来区分，其实质上并不对该参数做任何限定，例如一个数据子集中共有100个数据点时，P_i表示一个数据点，i可以从1取到100。

如图7所示，可不通过所述可达子集索引RPI来为每个子集计算核心点，以提高海量数据聚类的计算速度，但会损失一些聚类结果的精准度。具体计算方法可简化为：

步骤21：按顺序从K₁个数据子集中选取数据子集a，从数据子集a中按顺序选取数据点P_i，设数据点P_i的近邻点数量N_i的初始值为0，分类标签CF为1；

步骤22：从数据子集a中按顺序选取数据点P_j；

步骤23：计算数据点P_i与数据点P_j之间的距离D_i,j，若距离D_i,j小于预设半径R，则确定数据点P_j是数据点P_i的近邻点，数据点P_i的近邻点数量N_i＝N_i+1；

步骤24：按照步骤22所述的方法，遍历数据子集a中的所有数据点，按照步骤23所述的方法，计算数据点P_i的近邻点数量N_i；

步骤25：每次计算得到数据点P_i的近邻点数量N_i后，均判断数据点P_i的近邻点数量N_i是否大于最小近邻数量Min_N，若是则数据点P_i为核心点，为数据点P_i加上分类标签CF_i＝CF，并为该步计算中最后一个近邻点P_k加上分类标签MFa，且针对数据点P_i的核心点计算结束，令CF＝CF+1，并按照步骤21中的方法，选取下一个数据点P_i+1进行核心点计算；

步骤26：按照步骤21至步骤25所述的方法，遍历数据子集a中的每一个数据点，完成数据子集a中所有数据点的核心点计算；

步骤27：按照步骤21至步骤26所述的方法，遍历K₁个数据子集中的每一个数据子集，完成所有数据子集中所有数据点的核心点计算。

即针对数据子集a中的每一个数据点，无需遍历可达子集中的数据点，而是与数据子集a自身内的其他数据点进行遍历，完成之后再对数据子集a之外的其他数据子集进行遍历，直到K₁个数据子集全部遍历完成。

类似地，对每个数据子集中的核心点进行聚类，也可以分为两种方法，一种是根据可达子集索引对每个数据子集中的核心点进行聚类，另一种方式是无需可达子集即可完成。其中：

方式一：根据所述的可达子集索引，分别对每个数据子集中的核心点进行聚类，具体包括：

步骤31：对每个数据子集中的所有核心点的MF值进行聚合，对于任意数据点P_i，如果其MF值存在，则令CF_i＝MF_i；

步骤32：按顺序从K₁个数据子集中选取数据子集a，从数据子集a中按顺序选取数据点P_i；

步骤33：从数据子集a的可达子集列表中按顺序选取数据子集b；

步骤34：从数据子集b中按顺序选取数据点P_j；

步骤35：若数据点P_i与数据点P_j的分类标签CF_i与CF_j相等，则执行步骤37；否则计算数据点P_i与数据点P_j的距离D_i,j，若距离D_i,j小于所述预设半径R，则执行步骤36，否则执行步骤37；

步骤36：判断分类标签CF_i与CF_j之间的大小关系：当CF_i<CF_j时,则令CF_j＝CF_i，当CF_i>CF_j时，则令CF_i＝CF_j；

步骤37：按照步骤34至步骤36所述的方法，遍历数据子集b中的每一个数据点；

步骤38：按照步骤33至步骤37所述的方法，遍历数据子集a的可达子集列表中的每一个可达子集中的每一个数据点，完成数据子集a中核心点P_i的聚类计算；

步骤39：按照步骤32至步骤38所述的方法，遍历数据子集a中的每一个数据点，完成数据子集a中的所有核心点的聚类计算；

步骤310：按照步骤31至步骤39所述的方法，按顺序遍历K1个数据子集中的每一个数据子集，完成每一个数据子集中的每一个核心点的聚类计算。

方式二：不通过所述可达子集索引RPI来为每个子集中的核心点进行聚类，以提高海量数据聚类的计算速度，但会损失聚类结果的精准度。具体计算方法可简化为：

步骤41：对每个数据子集中的所有核心点的MF值进行聚合，对于任意数据点P_i，如果其MF值存在，则令CF_i＝MF_i；

步骤42：按顺序从K₁个数据子集中选取数据子集a，从数据子集a中按顺序选取数据点P_i和数据点P_j；

步骤43：判断数据点P_i与数据点P_j的分类标签CF_i与CF_j是否相等；若相等则执行步骤45，若不相等则计算数据点P_i与数据点P_j的距离D_i,j，若距离D_i,j小于所述预设半径R，则执行步骤44，否则执行步骤45；

步骤44：判断数据点P_i与数据点P_j的分类标签CF_i与CF_j的大小关系：当CF_i<CF_j时,则令CF_j＝CF_i，当CF_i>CF_j时，则令CF_i＝CF_j；

步骤45：按照步骤41至步骤44所述的方法，遍历数据子集a中的每一个数据点，完成数据子集a中所有核心点的聚类计算；

步骤46：按照步骤46至步骤45所述的方法，按顺序遍历K₁个数据子集中的每一个数据子集，完成每一个数据子集中的每一个核心点的聚类计算。

相似地，计算得到每个数据子集中的近邻点并对每个数据子集中的近邻点进行聚类的步骤，也可以通过两种方式实现。

方式一：根据所述可达子集索引RPI，分别为每个子集计算近邻点并聚类。计算方法为：

步骤51：按顺序从K₁个数据子集中选取数据子集a，将数据子集a中的核心点作为一个子集，记为CG_a，非核心点作为一个子集NCG_a；

步骤52：按照步骤51所述的方法，遍历K1个数据子集，为所有数据子集划分核心点子集CG与非核心点NCG；

步骤53：按顺序从K1个数据子集中选取数据子集a，按顺序从数据子集a的非核心点子集NCG_a中选取非核心点NCP_i；

步骤54：按顺序从数据子集a的可达子集列表中选取数据子集b；

步骤55：按顺序从数据子集b的核心点子集CG_b中选取核心点CP_j；

步骤56：计算非核心点NCP_i与核心点CP_j之间的距离D_i,j，如果距离D_i,j小于所述预设半径R，则非核心点NCP_i是核心点CP_j的近邻点，并进行聚类：令CF_i＝CF_j；

步骤57：按照步骤55至步骤56中所述的方法，遍历数据子集b中的每一个核心点；

步骤58：按照步骤54至56中所述的方法，遍历数据子集a的可达子集列表中的每一个可达子集，完成非核心点NCP_i的聚类计算；

步骤59：按照步骤53至步骤58中所述的方法，按顺序遍历数据子集a中的每一个非核心点，完成数据子集a中所有非核心点的聚类计算；

步骤510：按照步骤53至步骤59中所述的方法，按顺序遍历K₁个数据子集中的每一个数据子集，完成每个数据子集中所有非核心点的聚类计算。

方式二：不通过所述可达子集索引RPI来为每个子集计算近邻点，以提高海量数据聚类的计算速度，但会损失聚类结果的精准度。具体计算方法可简化为：

步骤61：将K₁个数据子集中每一个数据子集中的核心点作为一个子集，记为CG，非核心点作为一个子集，记为NCG；

步骤62：按照步骤61所述的方法，遍历K₁个数据子集，为所有的数据子集划分核心点CG与非核心点NCG；

步骤63：按顺序从K₁个数据子集中选取数据子集a，从数据子集a中的非核心点子集NCG_a中按顺序选取非核心点NCP_i；从数据子集a中的核心点子集CG_a中按顺序选取核心点CP_j；

步骤64：计算点NCP_i与点CP_j之间的距离D_i,j，如果D_i,j小于预设半径R，则点NCP_i是点CP_j的近邻点，并进行聚类：令CF_j＝CF_i；

步骤65：按照步骤63至步骤64中所述的方法，按顺序遍历数据子集a中的每一个非核心点，完成数据子集a中的所有非核心点的聚类计算；

步骤66：按照步骤63至步骤65所述的方法，按顺序遍历K₁个数据子集中的每一个数据子集，完成每个数据子集中所有非核心点的聚类计算。

以上方案中，所述预设半径R可以替换为R′：R≤R′≤R×2。本实施例提供的以上技术方案，可对大型空间数据集进行基于密度的无监督及半监督聚类，并实现高效、快速的并行聚类计算。

实施例3

图9是本实施例提供的执行基于密度的大型空间数据聚类算法K-DBSCAN的电子设备的硬件结构示意图，如图9所示，该设备包括：

一个或多个处理器701以及存储器702，图9中以一个处理器701为例。

执行基于密度的大型空间数据聚类算法K-DBSCAN的设备还可以包括：输入装置703和输出装置704。

处理器701、存储器702、输入装置703和输出装置704可以通过总线或者其他方式连接，图9中以通过总线连接为例。

存储器702作为一种非易失性计算机可读存储介质，可用于存储非易失性软件程序、非易失性计算机可执行程序以及模块，如本申请实施例中的基于密度的大型空间数据聚类算法K-DBSCAN对应的程序指令/模块。处理器701通过运行存储在存储器702中的非易失性软件程序、指令以及模块，从而执行服务器的各种功能应用以及数据处理，即实现上述方法实施例的基于密度的大型空间数据聚类算法K-DBSCAN。

存储器702可以包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需要的应用程序；存储数据区可存储根据执行基于密度的大型空间数据聚类算法K-DBSCAN的装置的使用所创建的数据等。此外，存储器702可以包括高速随机存取存储器，还可以包括非易失性存储器，例如至少一个磁盘存储器件、闪存器件、或其他非易失性固态存储器件。在一些实施例中，存储器702可选包括相对于处理器701远程设置的存储器，这些远程存储器可以通过网络连接至执行基于密度的大型空间数据聚类算法K-DBSCAN装置。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。

输入装置703可接收输入的数字或字符信息，以及产生与执行基于密度的大型空间数据聚类算法K-DBSCAN装置的用户设置以及功能控制有关的键信号输入。输出装置704可包括显示屏等显示设备。

所述一个或者多个模块存储在所述存储器702中，当被所述一个或者多个处理器701执行时，执行上述任意方法实施例中的基于密度的大型空间数据聚类算法K-DBSCAN。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。