本发明公开了基于混合高斯模型的移动对象连续k近邻查询方法及系统，构建面向全局移动对象的网格索引，基于所建立的网格索引，为查询点计算初始查询区域；构造混合高斯模型，用于模拟移动对象的位置分布，并根据移动对象位置变化对混合高斯模型进行实时更新；当查询点移动时，基于所述混合高斯模型，确定包含移动后查询点k近邻的最终查询区域；基于最终查询区域，计算移动后查询点的k近邻。本发明所提出的基于混合高斯模型的移动对象连续k近邻查询方法，在查询点和被查询对象连续移动情形下，基于已有查询结果快速计算查询点移动后的查询范围，实现对最新查询结果的实时更新，查询效率显著提高。
1.基于混合高斯模型的移动对象连续k近邻查询方法，其特征是，应用在智能交通、电子商务、社交网络领域中，包括：构建面向全局移动对象的网格索引，基于所建立的网格索引，计算初始查询区域；
构造混合高斯模型，用于模拟移动对象的位置分布，并根据移动对象位置变化对混合高斯模型进行实时更新；
当查询点移动时，基于所述混合高斯模型，确定查询点移动后包含k近邻的最终查询区域；
所述混合高斯模型，实现对移动对象位置信息的实时更新，能高效处理移动对象持续变化的位置信息，得到全局移动对象位置分布的高斯概率密度函数，有效模拟移动对象的实际分布；
在查询点连续移动情形下，基于已有查询结果快速计算查询点移动后的查询范围，实现对查询结果的实时更新。
2.如权利要求1所述的基于混合高斯模型的移动对象连续k近邻查询方法，其特征是，所述网格索引结构构建方式为：对全局移动对象建立网格索引结构，将整个二维平面区域划分成大小相同的正方形网格，每个网格单元由唯一标识符gi表示。
3.如权利要求2所述的基于混合高斯模型的移动对象连续k近邻查询方法，其特征是，所述每个网格单元gi具有一个移动对象列表Li，记录位于网格单元gi中每个移动对象的位置坐标；
当移动对象pi由网格单元gi移动至网格单元gi+1时，将移动对象pi从网格单元gi的移动对象列表gi+1中删除，并在gi+1的移动对象列表Li+1添加pi的当前位置。
4.如权利要求1所述的基于混合高斯模型的移动对象连续k近邻查询方法，其特征是，所述构造混合高斯模型的具体步骤如下：对网格索引中的所有移动对象进行初始聚类分析；
计算初始聚类分析后每个聚类的协方差矩阵，并计算各个聚类权值；
更新移动对象的参数，包括更新均值、更新协方差矩阵、更新权值，直到新的均值、协方差矩阵、权值收敛；
利用更新后的权值和各个聚类的高斯概率密度函数，计算得到与整个区域内移动对象分布相匹配的混合高斯模型的高斯概率密度函数。
5.如权利要求4所述的基于混合高斯模型的移动对象连续k近邻查询方法，其特征是，对所有移动对象进行初始聚类分析，步骤如下：从全局移动对象中任意选取M个移动对象作为初始的聚类中心；
根据每个聚类的聚类中心即聚类的均值，计算每个移动对象与所述聚类中心的距离；
如果移动对象距离某个聚类中心最近，则该移动对象属于该聚类；如果移动对象到多个聚类中心的距离相等，则可划分到与之距离相等的任意一个聚类中；
按移动对象到聚类中心的距离对所有移动对象聚类划分后，重新计算每个聚类的均值；当重新计算的每个聚类的均值收敛，初始聚类分析完成。
6.如权利要求4所述的基于混合高斯模型的移动对象连续k近邻查询方法，其特征是，更新各个聚类的参数时，首先根据每个聚类当前的参数计算后验概率，之后基于该后验概率更新均值、更新协方差矩阵、更新权值，直到新的均值、协方差矩阵、权值收敛。
7.如权利要求1所述的基于混合高斯模型的移动对象连续k近邻查询方法，其特征是，所述基于所建立的网格索引，计算查询q的初始查询区域，具体步骤为：首先确定查询点q所在的网格索引单元gq，判断网格索引单元gq内移动对象的数目是否满足k个；
若网格单元gq内移动对象数量大于等于k，则gq为候选查询区域；否则，向外扩展一层网格单元作为搜索区域，判断该搜索区域的移动对象数量是否大于等于k；
当搜索区域中移动对象数量大于等于k，将该区域记为候选查询区域；
计算候选查询区域内移动对象与q的距离，得到距离q第k近的移动对象pk，然后计算得到一个以q为圆心，以q与pk距离为半径的圆cq，cq一定包含查询qj的k近邻，记作q的初始查询区域FR，FR的半径为r。
8.如权利要求7所述的基于混合高斯模型的移动对象连续k近邻查询方法，其特征是，当查询点移动时，基于所述混合高斯模型，确定查询点移动后包含k近邻的最终查询区域，具体步骤为：查询点q移动后记为q'，查询点q'的初始查询区域变为以q'为中心，且与FR大小相等的区域CR'，CR'的半径即为r；
计算查询点q'的初始查询区域CR'内移动对象数目占所有移动对象数目的比例为ρ，从而得到q'的初始查询区域CR'内移动对象的数目ρ×n，n为全局移动对象的总数；
当q'的初始查询区域CR'内移动对象的数目满足k＜ρ×n≤2k时，CR即为q'的最终查询区域FR'；否则，将CR'作为q'的候选查询区域，调整CR'的大小，使CR'内移动对象的数量大于k且小于2k，此时CR'即为的q'的最终查询区域FR'。
9.如权利要求8所述的基于混合高斯模型的移动对象连续k近邻查询方法，其特征是，所述基于q'的最终查询区域，计算移动后查询点q'的k近邻：计算最终查询区域FR'中移动对象与q'的距离，从而得到距离q'最近的k个移动对象。
10.基于混合高斯模型的移动对象连续k近邻查询系统，其特征是，应用在智能交通、电子商务、社交网络领域中，包括：初始查询区域计算模块：构建面向大规模移动对象的网格索引，基于所建立的网格索引，计算初始查询区域；
混合高斯模型构建模块：构造混合高斯模型，用于模拟移动对象的位置分布，并根据移动对象位置变化对混合高斯模型进行实时更新；
最终查询区域确定模块：当查询点移动时，基于所述混合高斯模型，确定包含移动后查询点k近邻的最终查询区域；
移动后查询点的k近邻计算模块：基于最终查询区域，计算移动后查询点的k近邻；
所述混合高斯模型，实现对移动对象位置信息的实时更新，能高效处理移动对象持续变化的位置信息，得到全局移动对象位置分布的高斯概率密度函数，有效模拟移动对象的实际分布；
在查询点连续移动情形下，基于已有查询结果快速计算查询点移动后的查询范围，实现对查询结果的实时更新。
基于混合高斯模型的移动对象连续k近邻查询方法及系统
技术领域
[0001] 本发明涉及计算机应用技术领域，特别是涉及基于混合高斯模型的移动对象连续k近邻查询方法及系统。
背景技术
[0002] 近年来，随着移动终端的广泛应用和移动互联网的迅猛发展，移动对象k近邻查询问题已成为智能交通、电子商务、社交网络等领域的共性问题。在当前大数据背景下，移动对象规模急剧增加，如何快速、高效、精准地处理移动对象连续k近邻查询问题成为国内外相关领域的一个研究热点。
[0003] 移动对象连续k近邻查询问题，是指给定二维空间内一个移动对象的集合和一个查询点q，实时计算得到距离q最近的k个移动对象；如果查询点q的位置发生变化，则实时更新q的k近邻。移动对象连续k近邻查询问题已被国内外学者广泛研究，但是已有工作在解决该问题时某些方面有待改善。具体表现如下：
[0004] (1)现有的移动对象连续k近邻查询方法通常假定查询点是固定的，仅移动对象的位置发生变化，然后基于该假设设计移动对象连续k近邻增量查询算法。一旦查询点的位置发生变化，则需要重新计算查询结果，增量查询失去意义。
[0005] (2)现有连续k近邻查询方法通常基于区域划分索引结构(如网格索引、R-tree索引)确定候选查询范围，该过程通常涉及多次迭代计算，产生较大代价。
[0006] 综上所述，现有技术中对于如何快速准确的实现移动对象连续k近邻查询的问题，尚缺乏有效的解决方案。
发明内容
[0007] 为了解决现有技术的不足，本发明提供了基于混合高斯模型的移动对象连续k近邻查询方法，采用混合高斯模型模拟大规模移动对象的分布和运动，移动对象k近邻查询点的位置一旦发生变化，本发明能够为移动的查询点快速确定包含其k近邻的有效查询范围，从而得到其最新的k近邻。
[0008] 基于混合高斯模型的移动对象连续k近邻查询方法，包括：
[0009] 构建面向全局移动对象的网格索引，基于所建立的网格索引，计算初始查询区域；
[0010] 构造混合高斯模型，用于模拟移动对象的位置分布，并根据移动对象位置变化对混合高斯模型进行实时更新；
[0011] 当查询点移动时，基于所述混合高斯模型，确定查询点移动后包含k近邻的最终查询区域；
[0012] 基于最终查询区域，计算查询点移动后的k近邻。
[0013] 进一步的，所述网格索引结构构建方式为：对全局移动对象建立网格索引结构，将整个二维平面区域划分成大小相同的正方形网格，每个网格单元由唯一标识符gi表示。
[0014] 更进一步的，所述每个网格单元gi具有一个移动对象列表Li，记录位于网格单元gi中每个移动对象的位置坐标；
[0015] 当移动对象pi由网格单元gi移动至网格单元gi+1时，将移动对象pi从网格单元gi的移动对象列表Li中删除，并在gi+1的移动对象列表Li+1添加pi的当前位置。
[0016] 进一步的，所述构造混合高斯模型的具体步骤如下：
[0017] 对网格索引中的所有移动对象进行初始聚类分析；
[0018] 计算初始聚类分析后每个聚类的协方差矩阵，并计算各个聚类权值；
[0019] 更新各个聚类的参数，包括更新均值、更新协方差矩阵、更新权值，直到新的均值、协方差矩阵、权值收敛；
[0020] 计算各个聚类的高斯概率密度函数；
[0021] 利用更新后的权值和各个聚类的高斯概率密度函数，计算得到与整个区域内移动对象分布相匹配的混合高斯模型的高斯概率密度函数。
[0022] 进一步的，对所有移动对象进行初始聚类分析，步骤如下：
[0023] 从全局移动对象中任意选取M个移动对象作为初始的聚类中心；
[0024] 根据每个聚类的聚类中心即聚类的均值，计算每个移动对象与各个聚类中心的距离；
[0025] 如果移动对象距离某个聚类中心最近，则该移动对象属于该聚类；如果移动对象到多个聚类中心的距离相等，则可划分到与之距离相等的任意一个聚类中；
[0026] 按移动对象到聚类中心的距离对所有移动对象聚类划分后，重新计算每个聚类的均值；
[0027] 当重新计算所得的每个聚类的均值收敛，初始聚类分析完成。
[0028] 进一步的，更新各个聚类的参数时，首先根据每个聚类当前的参数计算后验概率，之后基于该后验概率更新均值、更新协方差矩阵、更新权值，直到新的均值、协方差矩阵、权值收敛。
[0029] 进一步的，所述基于所建立的网格索引，计算初始查询区域，具体步骤为：
[0030] 首先确定查询点q所在的网格索引单元gq，判断网格索引单元gq是否包含k个移动对象；
[0031] 若网格索引单元gq内移动对象数目大于等于k，则gq为候选查询区域；否则，向外扩展一层网格索引单元作为搜索区域，判断该搜索区域的移动对象数量是否大于等于k；
[0032] 当搜索区域中移动对象数量大于等于k，将该区域记为候选查询区域；
[0033] 计算候选查询区域内移动对象与q的距离，得到距离q第k近的移动对象pk，然后计算得到一个以q为圆心，以q与pk距离为半径的圆cq，cq一定包含查询q的k近邻，记作q的初始查询区域FR，FR的半径即为r。
[0034] 进一步的，当查询点移动时，基于所述混合高斯模型，确定包含查询点移动后k近邻的最终查询区域，具体步骤为：
[0035] 查询点q移动后记为q′，查询点q′的初始查询区域变为以q′为中心，且与FR大小相等的区域CR，CR的半径为r；
[0036] 计算查询点q′的初始查询区域CR内移动对象数目占全局移动对象数目的比例ρ，从而得到q′的初始查询区域CR内移动对象的数目ρ×n，n为全局移动对象的总数；
[0037] 当q′的初始查询区域CR内移动对象的数量满足k＜ρ×n≤2k时，CR即为q′的最终查询区域FR′；否则，调整CR的大小，直至CR内移动对象的数量满足k＜ρ×n≤2k，此时CR即为q′的最终查询区域FR'。
[0038] 进一步的，所述基于最终查询区域，计算查询点移动后的k近邻：计算最终查询区域FR'中移动对象与q′的距离，从而得到距离q′最近的k个移动对象。
[0039] 进一步的，计算查询点q′的初始查询区域CR内移动对象数目占所有移动对象数目的比例ρ时，r为区域CR的半径，k近邻查询点q的坐标为(x,y)，具体步骤如下：
[0040] 选取q′的初始查询区域CR上的四个点：o1(x+r,y)、o2(x,y+r)、o3(x-r,y)和o4(x,y-r)，并计算这四个点的分布概率 其中μ'm、σ'm和 分别为各个聚类更新后的均值、协方差矩阵和权值；
[0041] 查询点q′的初始查询区域CR内移动对象数目占所有移动对象数目的比例为[0042]
[0043] 基于混合高斯模型的移动对象连续k近邻查询系统，包括：
[0044] 初始查询区域计算模块：构建面向大规模移动对象的网格索引，基于所建立的网格索引，计算初始查询区域；
[0045] 混合高斯模型构建模块：构造混合高斯模型，用于模拟移动对象的位置分布，并根据移动对象位置变化对混合高斯模型进行实时更新；
[0046] 最终查询区域确定模块：当查询点移动时，基于所述混合高斯模型，确定查询点移动后包含k近邻的最终查询区域；
[0047] 移动后查询点的k近邻计算模块：基于最终查询区域，计算移动后查询点的k近邻。
[0048] 与现有技术相比，本发明的有益效果是：
[0049] (1)本发明采用混合高斯模型能够很好地模拟移动对象的分布和运动状态，从而为快速计算某区域内移动对象数目提供了很好的数学模型和计算方法。
[0050] (2)本发明所采用的混合高斯模型，实现对移动对象位置信息的实时更新，能高效处理移动对象持续变化的位置信息，得到全局移动对象位置分布的高斯概率密度函数，有效模拟移动对象的实际分布，能很好地支持连续k近邻查询方法算法。
[0051] (3)本发明所提出的基于混合高斯模型的移动对象连续k近邻查询方法，在查询点连续移动情形下，基于已有查询结果快速计算查询点移动后的查询范围，实现对查询结果的实时更新，查询效率显著提高。
附图说明
[0052] 构成本申请的一部分的说明书附图用来提供对本申请的进一步理解，本申请的示意性实施例及其说明用于解释本申请，并不构成对本申请的不当限定。
[0053] 图1为网格索引示意图，该图中，网格单元g1中包含移动对象p1，因此，g1的移动对象列表L1＝{p1}。
具体实施方式
[0054] 应该指出，以下详细说明都是例示性的，旨在对本申请提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本申请所属技术领域的普通技术人员通常理解的相同含义。
[0055] 需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本申请的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。
[0056] 本申请的一种典型的实施方式中，基于混合高斯模型的移动对象连续k近邻查询方法，包括：
[0057] 步骤(1)构建全局移动对象的网格索引Grid-Index；
[0058] 步骤(2)构造混合高斯模型，模拟移动对象的分布情况，并根据移动对象位置变化对混合高斯模型进行实时更新；
[0059] 步骤(3)：基于所建立的网格索引Grid-Index，采用YPK-CNN算法计算包含查询点的k近邻的初始查询区域；
[0060] 步骤(4)：当查询点移动时，基于混合高斯模型，确定包含移动后查询点的k近邻的最终查询区域；
[0061] 步骤(5)：基于最终查询区域，计算移动后查询点的k近邻。
[0062] 所述步骤(1)采用的网格索引结构Grid-Index，如图1所示，具有以下属性：
[0063] 对全局移动对象建立网格索引结构Grid-Index，将整个二维平面区域划分成大小相同的正方形网格，每个网格索引单元由唯一标识符gi表示，网格索引单元的边长为α。
[0064] 每个网格索引单元gi具有一个移动对象列表Li，记录位于gi中每个移动对象的位置坐标。pi(xi，yi)表示移动对象pi的位置坐标为(xi，yi)。
[0065] 当移动对象pi由网格索引单元gi移动至网格索引单元gi+1，将pi从gi的移动对象列表Li中删除，并在gi+1的移动对象列表Li+1添加pi的当前位置。
[0066] 步骤(2)构造混合高斯模型的具体步骤如下：
[0067] 步骤(2.1)：用K-Means算法对全局移动对象进行初始聚类分析；
[0068] 步骤(2.1.1)：从全局移动对象中任意选取M个对象作为初始的聚类中心；
[0069] 步骤(2.1.2)：根据每个聚类的聚类中心(即聚类的均值)，计算每个移动对象与这些聚类中心的距离；
[0070] 步骤(2.1.3)：如果移动对象距离某个聚类中心最近，则该移动对象属于该聚类；如果移动对象到多个聚类中心的距离相等，则可划分到与之距离相等的任意一个聚类中；
[0071] 步骤(2.1.4)：按距离对所有移动对象聚类划分后，重新计算每个聚类的均值μm(0≤m≤M)；
[0072] 步骤(2.1.5)：重复步骤(2.1.2)、(2.1.3)、(2.1.4)直到新的均值收敛，K-Means算法结束，完成初始聚类分析；
[0073] 步骤(2.2)：计算聚类划分结束后每个聚类的协方差矩阵σm(0≤m≤M)，并计算各个聚类权值
[0074] 步骤(2.3)：采用EM极大似然估计算法更新参数；
[0075] 步骤 (2 .3 .1) 根据每个聚类当前的μm、σm、 计算后验概 率其中pi是来自第m个聚类的任意移动对象；
[0076] 步骤(2.3.2)：更新均值：
[0077] 步骤(2.3.3)：更新协方差矩阵：
[0078] 步骤(2.3.4)：更新权值： n为全局移动对象的数量；
[0079] 步骤(2.3.5)；重复步骤(2.3.1)、(2.3.2)、(2.3.3.)(2.3.4)直到新的均值、协方差矩阵、权值收敛，EM极大似然估计算法结束；
[0080] 步骤(2.4)：计算各个聚类的高斯概率密度函数其中|σ'm|表示σ'm的行列式，
表示σ'm的逆矩阵；
[0081] 步骤(2.5)：利用更新后的权值 和N'(pi；μ'm,σ'm)，计算得到的即为与整个区域内移动对象分布相匹配的混合高斯模型的高斯概率密度函数。
[0082] 所述步骤(3)中采用YPK-CNN算法计算k近邻查询q的初步查询区域FR；
[0083] 步骤(3.1)YPK-CNN首先确定查询q所在的网格索引单元gq，判断网格索引单元gq内移动对象的数目是否满足k个；
[0084] 步骤(3.2)若gq内移动对象数目大于等于k，则gq为候选查询区域；否则，向外扩展一层网格单元作为搜索区域，判断该搜索区域的移动对象数量是否大于等于k。
[0085] 步骤(3.3)重复步骤(3.2)直至找到一个搜索区域中移动对象数量是否大于等于k，将该区域记为候选查询区域。
[0086] 步骤(3.3)计算候选查询区域内移动对象与q的距离，得到距离q第k近的移动对象pk，然后计算得到一个以q为圆心，以q与pk距离为半径的圆cq，cq一定包含查询qj的k近邻，记作q的初始查询区域FR，FR的半径为r。
[0087] 步骤(4)查询q移动后记为q′，查询点q′的初始查询区域变为以q′为中心，且与FR大小相等的区域CR'，CR'的半径即为r，本发明基于YPK-CNN计算的初始查询区域，利用混合高斯模型，快速确定包含q′的k近邻的最终查询区域FR'。具体步骤如下：
[0088] 步骤(4.1)：根据Get-Integration算法计算区域CR'内移动对象数目占所有移动对象数目的比例为ρ，从而得到区域CR'内移动对象的数目ρ×n，n为移动对象的总数。
[0089] 步骤(4.2)：当区域CR'内移动对象的数目ρ×n≤k时，扩大区域CR'的半径[0090] 步骤(4.3)：当区域CR'内移动对象的数目ρ×n>2k时，缩小区域CR'的半径[0091] 步骤(4.4)：重复步骤(4.3)或(4.4)，直至满足k＜ρ×n≤2k，此时，区域CR'即为q′的最终查询区域FR'。
[0092] 步骤(4.5)：计算FR'中移动对象与q′的距离，从而得到距离q′最近的k个移动对象。
[0093] 本申请的步骤(4.1)：中，本发明所述Get-Integration算法根据混合高斯模型的高斯概率密度函数，采取求近似积分的方法计算区域CR'内移动对象数目占所有移动对象数目的比例，r为区域CR的半径，k近邻查询q′的坐标为(x,y)，具体步骤如下：
[0094] 步骤(4.1-1)：选取CR'上的四个点：o1(x+r,y)、o2(x,y+r)、o3(x-r,y)和o4(x,y-r),并计算这四个点的分布概率
[0095] 步骤(4.1-2)：区域CR'内移动对象数目占所有移动对象数目的比例为[0096]
[0097] 本发明的另一种实施例子公开了基于混合高斯模型的移动对象连续k近邻查询系统，包括：
[0098] 初始查询区域计算模块：构建面向大规模移动对象的网格索引，基于所建立的网格索引，计算初始查询区域；
[0099] 混合高斯模型构建模块：构造混合高斯模型，用于模拟移动对象的位置分布，并根据移动对象位置变化对混合高斯模型进行实时更新；
[0100] 最终查询区域确定模块：当初始查询区域内的查询点移动时，基于所述混合高斯模型，确定包含移动后查询点k近邻的最终查询区域；
[0101] 移动后查询点的k近邻计算模块：基于最终查询区域，计算移动后查询点的k近邻。
[0102] 上述基于混合高斯模型的移动对象连续k近邻查询系统中的各个模块的具体算法与基于混合高斯模型的移动对象连续k近邻查询方法中的算法相同，此处就不再具体描述。
[0103] 以上所述仅为本申请的优选实施例而已，并不用于限制本申请，对于本领域的技术人员来说，本申请可以有各种更改和变化。凡在本申请的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。
