一种分布式时空挖掘方法及系统与流程

1.本发明涉及分布式时空挖掘技术领域，尤其涉及一种分布式时空挖掘方法及系统。


背景技术：

2.目前，传统的时空数据挖掘技术主要包括几类，例如，应用于获取具有相似时空特征的时空对象的场景，包括：从时空轨迹数据库中获取第一时空数据集和第二时空数据集；其中，第一时空数据集中包含第一时空对象及其第一时间范围和第一空间属性，第二时空数据集中包含第二时空对象及其第二时间范围和第二空间属性；根据第一时间范围、第一空间属性、第二时间范围和第二空间属性对整个时间范围和空间范围进行划分，生成多个时空范围的时空分区，并对每个时空分区内来自两个时空数据集内的时空对象进行计算，得到满足时间约束的空间k最近邻。又例如，一种基于多源大数据的时空过程智能分析挖掘方法与系统，包括以下步骤：访问普通用户界面，触发注册和登录后通过安全认证和授权可访问管理员主界面；选择内置时空过程模型或上传新模型，提供模型参数配置和在线建模功能；依据多源大数据的上传、查询与分析，选择模型适用的多源数据集；根据时空过程模型和多源数据集，对时空过程分析挖掘任务进行分布式计算；时空过程产品展示。
3.但是，上述的几种时空数据挖掘技术都是单机挖掘的方式，难以针对大规模时空数据进行分布式挖掘处理，在面对大规模时空数据时，传统的单机挖掘算法存在效率很低、扩展性差的问题。


技术实现要素：

4.本发明提供了一种分布式时空挖掘方法及系统，以解决现有的单机挖掘算法的存在效率很低、扩展性差的问题。
5.为了实现上述目的，本发明通过如下的技术方案来实现：第一方面，本发明提供一种分布式时空挖掘方法，包括：s1：确定计算节点集合，利用预先计算得到的节点连接模型构建所述节点集合对应的拓扑结构；s2：设定时空数据集，利用时空数据划分模型将时空数据集中的数据元素划分到对应的计算节点上；s3：控制计算节点获取计算节点集合中除自身节点以外的其他节点发来的消息，并结合自身节点上的数据元素，执行挖掘函数，获得计算结果；s4：通过消息通信，各个计算节点将计算结果发送给拓扑结构中所连接的计算节点；s5：反复执行s3~s4，直到迭代结束，完成分布式挖掘。
6.可选地，所述节点连接模型的计算方式如下：将计算节点集合中的所有计算节点划分为领导节点和普通节点；其中一个领导节
点连接至少两个普通节点，领导节点和普通节点采用第一网络连接方式进行网络连接，领导节点之间采用第二网络连接方式进行网络连接；设定普通节点跨域发消息给另一个普通节点时，由本域的领导节点进行转发至跨域的领导节点，并由跨域的领导节点发送至跨域的普通节点。
7.可选地，所述将计算节点集合中的所有计算节点划分为领导节点和普通节点,包括：确定计算节点集合中的每个节点的计算能力，将计算能力超过阈值的视为为领导节点，将计算能力低于阈值的视为普通节点。
8.可选地，所述s2包括：利用kd树划分空间的二维，得到一系列第一子空间，在第一子空间内再利用quad树进行划分，进一步形成一系列第二子空间；交替采用kd树和quad树进行划分，直到划分粒度达到阈值；按照先x轴再y轴给划分好的子空间进行编号，得到{0,1,2,
…
m}；将子空间编号对最大标识进行取模操作，进行子空间到计算节点的分配，其中，每个节点对应一个标识；同时，将每一个计算节点的时间周期对最大标识进行取模操作，将时空数据集中的数据元素分配至对应的计算节点。
9.可选地，所述s3包括：s31：计算节点将自身节点对时空数据的挖掘结果表示为向量ll，将其他计算节点的挖掘结果表示为向量lo；s32：进行训练lo+ll映射为结果rs；反复执行步骤s31~s32，直到满足预先设定的训练次数得到训练模型；记录该训练模型为挖掘函数。
10.可选地，所述方法还包括：测试普通节点和各个领导节点的网络延时，根据网络延时就近进行领导节点的连接。
11.可选地，所述计算能力包括cpu、内存或者带宽。
12.第二方面，本技术提供一种分布式时空挖掘系统，包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现上述第一方面所述方法的步骤。
13.有益效果：本发明提供的分布式时空挖掘方法，利用预先计算得到的节点连接模型构建所述节点集合对应的拓扑结构，利用时空数据划分模型将时空数据集中的数据元素划分到对应的计算节点上实现分布式挖掘，这样，在网络拓扑上考虑了混合式结构，这种结构即满足本地快速迭代，又可以利用领导节点的性能优势进行高效的域间挖掘，大大提高了挖掘的效率。
14.在进一步的技术方案中，数据划分利用了kd树结合quad树的方法，在数据偏斜分布时同样可以划分均匀，且划分的简单性，可以提升整体的挖掘效率。
15.采用了机器学习的方法改造单机版的时空挖掘算法，使之成为分布式算法，这样，
可以在保持原算法精度的同时，提升算法的可扩展性和伸缩性。
附图说明
16.图1为本发明优选实施例的一种分布式时空挖掘方法的流程图。
具体实施方式
17.下面对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
18.除非另作定义，本发明中使用的技术术语或者科学术语应当为本发明所属领域内具有一般技能的人士所理解的通常意义。本发明中使用的“第一”、“第二”以及类似的词语并不表示任何顺序、数量或者重要性，而只是用来区分不同的组成部分。同样，“一个”或者“一”等类似词语也不表示数量限制，而是表示存在至少一个。“连接”或者“相连”等类似的词语并非限定于物理的或者机械的连接，而是可以包括电性的连接，不管是直接的还是间接的。“上”、“下”、“左”、“右”等仅用于表示相对位置关系，当被描述对象的绝对位置改变后，则该相对位置关系也相应地改变。
19.请参见图1，本技术提供的一种分布式时空挖掘方法，包括：s1：确定计算节点集合，利用预先计算得到的节点连接模型构建节点集合对应的拓扑结构；s2：设定时空数据集，利用时空数据划分模型将时空数据集中的数据元素划分到对应的计算节点上；s3：控制计算节点获取计算节点集合中除自身节点以外的其他节点发来的消息，并结合自身节点上的数据元素，执行挖掘函数，获得计算结果；s4：通过消息通信，各个计算节点将计算结果发送给拓扑结构中所连接的计算节点；s5：反复执行s3~s4，直到迭代结束，完成分布式挖掘。
20.在一示例中，计算节点集合可以是{节点1，节点2，节点3，
…
，节点n}，时空数据集是ds，其中数据元素为(x,y,t)。利用时空数据划分模型将时空数据集中的数据元素划分到对应的计算节点上时，每个计算节点负责一部分时空数据，即节点i负责空间（xa, xb）(ya, yb)，时间周期为(ta mod t, tb mod t)。其他节点发来的消息可以是指其他计算节点的挖掘结果。
21.上述的分布式时空挖掘方法，利用预先计算得到的节点连接模型构建所述节点集合对应的拓扑结构，利用时空数据划分模型将时空数据集中的数据元素划分到对应的计算节点上实现分布式挖掘，这样，在网络拓扑上考虑了混合式结构，这种结构即满足本地快速迭代，又可以利用领导节点的性能优势进行高效的域间挖掘，大大提高的挖掘的效率。
22.可选地，节点连接模型的计算方式如下：将计算节点集合中的所有计算节点划分为领导节点和普通节点；其中一个领导节点连接至少两个普通节点，领导节点和普通节点采用第一网络连接方式进行网络连接，领导节点之间采用第二网络连接方式进行网络连接；
设定普通节点跨域发消息给另一个普通节点时，由本域的领导节点进行转发至跨域的领导节点，并由跨域的领导节点发送至跨域的普通节点。
23.其中，领导节点之间存在连接关系，具体地，确定领导节点之间的连接关系的方式如下：测试普通节点和各个领导节点的网络延时，根据网络延时就近进行领导节点的连接。这样，可以快速的进行跨域消息转发。
24.在本可选的实施方式中，第一网络连接方式是本地化普通网络连接；第二网络连接方式是全连通网络，采用高速网络连接。
25.这样，将计算节点在拓扑结构上分为领导节点和普通节点得到节点连接模型，并设定各计算节点之间的连接方式和消息转发方式，可以提升时空数据的挖掘的效率。
26.可选地，将计算节点集合中的所有计算节点划分为领导节点和普通节点,包括：确定计算节点集合中的每个节点的计算能力，将计算能力超过阈值的视为为领导节点，将计算能力低于阈值的视为普通节点。
27.本实施例中，计算能力包括cpu、内存或者带宽。此处仅作示例不做限定。
28.在一具体示例中，将带宽超过阈值的计算节点视为领导节点，将带宽低于阈值的计算节点视为普通节点。
29.这样根据每个节点的计算能力确定领导节点和普通节点，可以充分发挥每个节点的计算能力，减少资源浪费。
30.可选地，s2包括：利用kd树划分空间的二维，得到一系列第一子空间，在第一子空间内再利用quad树进行划分，进一步形成一系列第二子空间；交替采用kd树和quad树进行划分，直到划分粒度达到阈值；按照先x轴再y轴给划分好的子空间进行编号，得到{0,1,2,
…
m}；将子空间编号对最大标识进行取模操作，进行子空间到计算节点的分配，其中，每个节点对应一个标识；同时，将每一个计算节点的时间周期对最大标识进行取模操作，将时空数据集中的数据元素分配至对应的计算节点。
31.需要说明的是，每个节点事先有标识，在一些可以实现的实施方式中，标识可以是数字标识。
32.在一示例中，将子空间划分给节点的方式具体为，比如子空间标号为1~7，而节点编号为1~3，将子空间编号1mod最大标识7，将子空间编号2mod7，依次类推，最终为节点1分配子空间1、4、7，节点2分配子空间2、5，节点3分配子空间3、6。
33.在本实施例中，数据划分利用了kd树（多维二叉树）结合quad树（四叉树）的方法，既考虑数据的偏斜性（即在数据偏斜分布时同样可以划分均匀），又考虑了划分的简单性，这样效率更高、效果更好。
34.可选地，s3包括：s31：计算节点将自身节点对时空数据的挖掘结果表示为向量ll，将其他计算节点的挖掘结果表示为向量lo；s32：进行训练lo+ll映射为结果rs；
反复执行步骤s31~s32，直到满足预先设定的训练次数得到训练模型；记录该训练模型为挖掘函数。
35.本实施例中，采用了机器学习的方法改造单机版的时空挖掘算法，使之成为分布式算法，这可以在保持原算法精度的同时，大大提升了算法的可扩展性和伸缩性。
36.本技术实施例还提供一种分布式时空挖掘系统，包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现上述方法的步骤。该分布式时空挖掘系统可以实现上述的方法的各个实施例，且能达到相同的有益效果，此处，不做赘述。
37.以上详细描述了本发明的较佳具体实施例。应当理解，本领域的普通技术人员无需创造性劳动就可以根据本发明的构思作出诸多修改和变化。因此，凡本技术领域中技术人员依本发明的构思在现有技术的基础上通过逻辑分析、推理或者有限的实验可以得到的技术方案，皆应在由权利要求书所确定的保护范围内。

技术特征：
1.一种分布式时空挖掘方法，其特征在于，包括：s1：确定计算节点集合，利用预先计算得到的节点连接模型构建所述节点集合对应的拓扑结构；s2：设定时空数据集，利用时空数据划分模型将时空数据集中的数据元素划分到对应的计算节点上；s3：控制计算节点获取计算节点集合中除自身节点以外的其他节点发来的消息，并结合自身节点上的数据元素，执行挖掘函数，获得计算结果；s4：通过消息通信，各个计算节点将计算结果发送给拓扑结构中所连接的计算节点；s5：反复执行s3~s4，直到迭代结束，完成分布式挖掘。2.根据权利要求1所述的分布式时空挖掘方法，其特征在于，所述节点连接模型的计算方式如下：将计算节点集合中的所有计算节点划分为领导节点和普通节点；其中一个领导节点连接至少两个普通节点，领导节点和普通节点采用第一网络连接方式进行网络连接，领导节点之间采用第二网络连接方式进行网络连接；设定普通节点跨域发消息给另一个普通节点时，由本域的领导节点进行转发至跨域的领导节点，并由跨域的领导节点发送至跨域的普通节点。3.根据权利要求2所述的分布式时空挖掘方法，其特征在于，所述将计算节点集合中的所有计算节点划分为领导节点和普通节点,包括：确定计算节点集合中的每个节点的计算能力，将计算能力超过阈值的视为为领导节点，将计算能力低于阈值的视为普通节点。4.根据权利要求1所述的分布式时空挖掘方法，其特征在于，所述s2包括：利用kd树划分空间的二维，得到一系列第一子空间，在第一子空间内再利用quad树进行划分，进一步形成一系列第二子空间；交替采用kd树和quad树进行划分，直到划分粒度达到阈值；按照先x轴再y轴给划分好的子空间进行编号，得到{0,1,2,
…
m}；将子空间编号对最大标识进行取模操作，进行子空间到计算节点的分配，其中，每个节点对应一个标识；同时，将每一个计算节点的时间周期对最大标识进行取模操作，将时空数据集中的数据元素分配至对应的计算节点。5.根据权利要求1所述的分布式时空挖掘方法，其特征在于，所述s3包括：s31：计算节点将自身节点对时空数据的挖掘结果表示为向量ll，将其他计算节点的挖掘结果表示为向量lo；s32：进行训练lo+ll映射为结果rs；反复执行步骤s31~s32，直到满足预先设定的训练次数得到训练模型；记录该训练模型为挖掘函数。6.根据权利要求2所述的分布式时空挖掘方法，其特征在于，所述方法还包括：测试普通节点和各个领导节点的网络延时，根据网络延时就近进行领导节点的连接。7.根据权利要求3所述的分布式时空挖掘方法，其特征在于，所述计算能力包括cpu、内存或者带宽。
8.一种分布式时空挖掘系统，包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时实现上述权利要求1至7中任一所述方法的步骤。

技术总结
本发明涉及分布式时空挖掘技术领域，公开了一种分布式时空挖掘方法及系统，该方法利用预先计算得到的节点连接模型构建所述节点集合对应的拓扑结构，利用时空数据划分模型将时空数据集中的数据元素划分到对应的计算节点上实现分布式挖掘，这样，在网络拓扑上考虑了混合式结构，这种结构即满足本地快速迭代，又可以利用领导节点的性能优势进行高效的域间挖掘，大大提高了挖掘的效率。大大提高了挖掘的效率。大大提高了挖掘的效率。


技术研发人员：夏东
受保护的技术使用者：湖南视觉伟业智能科技有限公司
技术研发日：2023.09.07
技术公布日：2023/10/15