1.一种基于空间相似性的海量轨迹层次化并行聚类方法,其特征在于,包括:
获取轨迹数据;
根据获取的轨迹数据进行轨迹区域的网格单元划分;
基于划分的网格单元将轨迹数据转化为集合数据;
根据集合数据的集合形式,计算每条轨迹对应的MinHash签名并将所有轨迹的MinHash签名组成签名矩阵;
将得到的签名矩阵划分为若干个带,并将带中的轨迹映射到桶中;
将至少在一个带中被映射到同一个桶中的轨迹划分到同一类;
判断并输出聚类结果;
所述根据获取的轨迹数据进行轨迹区域的网格单元划分,包括对于给定的轨迹数据集,基于所有轨迹的最小和最大的x与y坐标确定其空间覆盖范围,然后选择固定网格单元大小z,将轨迹空间划分为 m × n个单元;
所述基于划分的网格单元将轨迹数据转化为集合数据,包括根据轨迹中各点的坐标确定轨迹路径穿过的网格单元,其中,任意轨迹ti被表示为它所穿过的若干网格单元,记为gi={c{x,y}},其中x∈[1, m]且y∈[1, n],对每个网格单元进行编码作为该网格的标识,其中,使用莫顿编码的编码方式将每个网格使用一个整数作为其标识符,每条轨迹对应其经过的若干网格单元的标识符组成的整数集合;
所述计算每条轨迹对应的MinHash签名并将所有轨迹的MinHash签名组成签名矩阵,包括将轨迹集合数据以矩阵的形式存储,得到TE-矩阵;使用哈希函数计算出每个网格单元标识符对应的哈希值并存储为矩阵的形式,得到HV-矩阵;基于TE-矩阵和HV-矩阵生成Sig-矩阵,将Sig-矩阵中的元素初始化为∞,其中,遍历TE-矩阵中的每一行i,检查每列的值,若值为‘0’,则不执行任何操作;若值为‘1’,则使用TE-矩阵中相同行的哈希值更新Sig-矩阵中对应列;并用HV-矩阵的行更新Sig-矩阵,最终得到签名矩阵;
所述将得到的签名矩阵划分为若干个带,并将带中的轨迹映射到桶中,包括将Sig-矩阵的行进一步划分为多个带,对于每个带,创建一个桶数组,将带中签名相同的轨迹映射到同一个桶,同一桶内的轨迹说明其签名之间具有高Jaccard相似度;
所述将至少在一个带中被映射到同一个桶中的轨迹划分到同一类,包括创建初始一个初始类C1并将其设置为第一个带中的任一桶,扫描其余带中的桶,查找与C1中的轨迹存在交集的桶,如果存在这样的桶,则将桶中的轨迹合并到C1中,完成对第二到最后一个带中每个桶的扫描后,返回到第一个带,此时若发现与C1存在交集的桶,同样将其合并,扫描完第一个带中的桶之后即可确认C1,确定C1后,依次将第一个带中未处理的桶作为新类,直到第一个带中的所有桶都处理完毕,判断最终得到的每个类之间是否存在交集,若存在,同样将存在交集的类进行合并,最终得到的互相之间不存在交集的类即为本次聚类过程的最终结果;
所述判断并输出聚类结果,包括判断每个类是否满足设定条件,若满足设定条件则输出该类作为最终聚类结果中的某一类;若不满足,以并行的方式对每个类重复聚类操作,其中在进行网格单元划分时使用更小的网格单元划分该类中轨迹的整个轨迹空间;所述的条件指在进行进一步聚类之后,该类中的轨迹并没有被分为更多的子类,具体来说,对每个类内的轨迹使用原网格单元大小的二分之一的网格单元进行网格划分,以得到更细粒度的轨迹表示,然后以并行的方式在各类内进行更细粒度的进一步聚类;如果某个类在优化过程中未被进一步分割为多个子类,则认为该类已达到足够的类内相似性,作为最终的类输出;反之则对这些子类继续递归执行更细粒度的聚类优化过程,直到无法继续分割。
2.一种基于空间相似性的海量轨迹层次化并行聚类系统,执行如权利要求1所述的方法,其特征在于,包括:数据获取模块,被配置为,获取轨迹数据;
单元划分模块,被配置为,根据获取的轨迹数据进行轨迹区域的网格单元划分;
转化模块,被配置为,基于划分的网格单元将轨迹数据转化为集合数据;
矩阵模块,被配置为,根据集合数据的集合形式,计算每条轨迹对应的MinHash签名并将所有轨迹的MinHash签名组成签名矩阵;
映射模块,被配置为,将得到的签名矩阵划分为若干个带,并将带中的轨迹映射到桶中;
划分模块,被配置为,将至少在一个带中被映射到同一个桶中的轨迹划分到同一类;
判断输出模块,被配置为,判断并输出聚类结果。
3.一种计算机可读存储介质,其中存储有多条指令,其特征在于,所述指令适于由终端设备的处理器加载并执行如权利要求1所述的方法。
4.一种终端设备,包括处理器和计算机可读存储介质,处理器用于实现各指令;计算机可读存储介质用于存储多条指令,其特征在于,所述指令适于由处理器加载并执行如权利要求1所述的方法。