基于局部多层网格的轨迹数据热点区域发现方法

摘要

本发明涉及一种基于局部多层网格的轨迹数据热点区域发现方法，本发明解决其技术问题所采用的技术方案是：步骤1）根据轨迹数据分布特点局部多层次划分轨迹运动空间，计算单元格密度；步骤2）对密度单元格在给定的阀值下筛选及扩张，计算候选热点区域；步骤3）根据候选热点区域轨迹支持数及轨迹数据在候选热点区域内的停留时间，筛选出热点区域，该方法划分网格覆盖运动平面的自适应效果比较好，只要指定单元格内样本点数量阈值，在迭代划分过程中，总能得到一个合适的网格覆盖运动空间，把样本数据做细致的划分，只要设定的密度阈值一定，初始划分参数对挖掘结果不会有太大影响，可以应用于海量数据挖掘，保证算法的效率和适应性。

说明书

技术领域

本发明涉及网络的位置服务领域，尤其是一种基于局部多层网格的轨迹数据热点区域发现方法。 

背景技术

现有的关于轨迹数据热点区域发现方法多是基于规则密度网格，需要掌握移动对象情况从而设置合理的参数，影响结果的准确性，导致方法适用性较差。 

发明内容

为了解决现有技术存在的不足，本发明提出了一种基于局部多层网格的轨迹数据热点区域发现方法，本方法能根据样本数据的分布情况局部多层次划分空间，使得单元格内样本点数趋于一致，计算单元格密度，通过扩张高密度单元格准确的定位热点区域，可以应用于海量数据挖掘，保证算法的效率和适应性 

    本发明解决其技术问题所采用的技术方案是：

步骤1）根据轨迹数据分布特点局部多层次划分轨迹运动空间，计算单元格密度；

步骤2）对密度单元格在给定的阀值下筛选及扩张，计算候选热点区域；

步骤3）根据候选热点区域轨迹支持数及轨迹数据在候选热点区域内的停留时间，筛选出热点区域。

所述步骤1）中多层次划分运动空间的步骤包括： 

步骤1.1）根据轨迹数据分布特点，初始化划分参数d；

步骤1.2）对轨迹运动空间的每一个维度进行基于参数d的等分，形成d×d个大小相等的矩形单元格；

步骤1.3）设定单元格内最小数据点个数n；

步骤1.4）将每个单元格内数据点的个数与最小数据点个数进行比较，当单元格内数据点的个数大于最小数据点个数n时，该单元格将被继续划分，否则该单元格被认为是“局部稀疏”的不再进行划分；

步骤1.5）对需要被继续划分的单元格，通过调用函数multi-Divide(G, C_i,n)进一步划分，直到所有满足划分条件的单元格划分完成，输出单元格集合G。

所述步骤1.5）中调用函数multi-Divide(G,C_i,n)对单元格进一步划分的方法包括以下步骤： 

步骤1.5.1）对C_i中的每一个单元格c_i,_j进行遍历；

步骤1.5.2）把每个单元格c_i,_j四等分；

步骤1.5.3）统计单元格c_i+1,_j中的样本点的个数；

步骤1.5.4）如果样本点的个数大于最小数据点个数n，则递归调用multi-Divide(G,Ci,n)，否则将单元格c_i+1,_j加入输出的单元格集合G中。

其中，G为输出的单元格集合，C_i表示第i层中需要进一步划分的单元格集合，n为单元格内最小数据点个数，c_i,_j表示C_i中的第j个单元格。 

所述步骤2）包括：   

步骤2.1）设定热点区域密度阀值；

步骤2.2）以该热点区域密度阀值为标准对单元格集合中的密度单元格进行初步筛选，把密度不小于热点区域密度阀值的单元格筛选到候选热点区域中并排序；

步骤2.3）将单元格集合中未处理的单元格依次分别基于密度的扩张，扩张后的单元格密度不小于热点区域密度阀值的即被候选热点区域吸收，具体步骤包括：

步骤2.3.1）判断如果该单元格与候选热点区域中任意单元格邻接且与候选热点区域中所有单元格合并后的平均密度不小于热点区域密度阀值，则候选热点区域扩张吸收该单元格；

步骤2.3.2）如果该单元格与候选热点区域中任何单元格都不邻接，则候选热点区域不吸收该单元格，继续遍历单元格中的下一个单元格；

步骤2.3.3）如果候选热点区域中所有单元格合并后的平均密度小于热点区域密度阀值，则此次扩张失败，即候选热点区域不能吸收该单元格。

所述步骤2.3）中，单元格集合中未处理的单元格与候选热点区域中任意单元格是否邻接的判断方法为：从横向和纵向两个维度判断两个矩形单元格是否邻接，设定其中一个矩形单元格的宽为w1，高为h1，中心点为p1，另一个矩形单元格的宽为w2，高为h2，中心点为p2，如果（w1+w2）/2＜|p1.x-p2.x|，则矩形单元格横向分离；如果（h1+h2）/2＜|p1.y-p2.y|，则矩形单元格纵向分离，如果两个矩形单元格既不横向分离又不纵向分离，则可认定为相邻或相接。 

本发明的有益效果是：该基于局部多层网格的轨迹数据热点区域发现方法划分网格覆盖运动平面的自适应效果比较好，只要指定单元格内样本点数量阈值，在迭代划分过程中，总能得到一个合适的网格覆盖运动空间，把样本数据做细致的划分，只要设定的密度阈值一定，初始划分参数对挖掘结果不会有太大影响，可以应用于海量数据挖掘，保证算法的效率和适应性。 

附图说明

附图1为该基于局部多层网格的轨迹数据热点区域发现方法的流程图。 

附图2为轨迹数据运动空间经局部多层网格划分后的示意图。 

附图3为单元格集合中未处理的单元格与候选热点区域中任意单元格邻接方式示意图。 

具体实施方式

下面结合附图及实施例对本发明作进一步说明。 

本发明的主要构思为：对于轨迹数据高密度样本区域迭代地进行多层次网格划分，每深入一个层次的划分都使覆盖网格的精度提高一倍,最终使得覆盖高密度区域的网格单元格尺寸能取到一个合适值，因此算法中对于覆盖网格单元格尺寸的初始值选择不再重要，也不会对结果产生重大影响，对样本空间采用灵活的划分尺度并利用这些细分单元格发现热点区域能有效控制热点区域的范围，同时也能有效避免得到区域范围过大的问题，在一定程度上减弱了网格划分对样本数据点之间联系产生的割裂影响。 

局部多层次划分后，得到一个覆盖运动空间的不规则网格，计算每个单元格密度，对高密度单元格进行基于密度的扩张，得到候选热点区域，如果候选热点区域满足轨迹支持数阈值和移动对象最短停留时间阈值，则该候选区域为热点区域，逐一考察候选区域，最终得到热点区域集合。 

 参见图1和图2所示， 一种基于局部多层网格的轨迹数据热点区域发现方法，包括以下步骤： 

步骤1）根据轨迹数据分布特点局部多层次划分轨迹运动空间，计算单元格密度，移动对象的运动平面假设为一个规则矩形，样本空间的多层次划分是一个递归过程，在最初仅仅对样本空间进行简单的划分，然后对符合条件的单元格作进一步多层次划分，其步骤包括：

步骤1.1）根据轨迹数据分布特点，初始化划分参数d；

步骤1.2）把样本空间划分为d×d个相同的矩形单元格{c_0i|0≤i≤(d×d)}，每个单元格的宽度为W_0i,高度为H_0i，面积S_0i=W_0i×H_0i；

每个矩形宽为W_oi，高度为H_0i，分别表示第0层次划分的第i个单元格的宽度和高度，通过这两个参数很容易得出单元格的面积S，用于计算单元格样本密度,以上为对样本空间的简单划分；

步骤1.3）设定单元格内最小数据点个数n；

步骤1.4）统计每个单元格中点的个数count(c_i,_j)，如果单元格c_i,_j中数据点个数大于n，则把该单元格加入集合C_i中，否则把该单元格加入单元格集合G中；

其中，G为输出的单元格集合，C_i表示第i层中需要进一步划分的单元格集合，n为单元格内最小数据点个数，c_i,_j表示C_i中的第j个单元格；

参数n是单元格进一步划分的条件，对于每个单元格，如果其中包含样本点数超过n那么该单元格将继续被划分，否则该单元格被认为是“局部稀疏”的，不需要继续划分了，通过这个参数体现了算法对运动空间划分的“局部性”；

步骤1.5）对于C_i中的每个单元格c_i,_j调用函数multi-Divide(G,C_i,n)对单元格进一步划分包括以下步骤：

步骤1.5.1）对C_i中的每一个单元格c_i,_j进行遍历；

步骤1.5.2）把每个单元格c_i,j四等分，每次划分后使得原来的精度提高一倍；划分得到的单元格被标识为c_i+1,_j，0≤j≤3，记录下新得到的单元格的长度和宽度，用于计算单元格中样本点的平均密度；

步骤1.5.3）统计单元格c_i+1,_j中的样本点的个数；

步骤1.5.4）如果样本点的个数大于n，则递归调用multi-Divide(G, C_i,n)，否则将单元格c_i+1,_j加入输出的网格单元格集合G中。

步骤2）对密度单元格在给定的阀值下筛选及扩张，计算候选热点区域，以单元格集合G以及设定的热点区域阈值 为参数，算法结束将得到候选热点区域集合R，包括以下步骤： 

步骤2.1）设定热点区域密度阀值；

步骤2.2）计算单元格集合G中每个单元格的密度，并把这些单元格标记为未处理。对于G中的单元格，以密度为主要标准进行非升序排列并以单元格的面积为次要标准非降序排列，对单元格进行初步筛选，把密度不小于热点区域密度阈值的单元筛选到集合G_*中，并排序，把G_*中每个未处理的候选密度单元格ck看作热点区域r的初始组成单元格，如果该单元格已经处理过了，则继续考察G_*下一个单元格；

步骤2.3）从G中按照排好的顺序选择未处理单元格，将单元格集合中未处理的单元格依次分别基于密度的扩张，扩张后的单元格密度不小于热点区域密度阀值的即被候选热点区域吸收，判断如果该单元格与r中的任意单元格邻接且与r中所有单元格合并后的平均密度不小于密度阈值，则热点区域r扩张吸收该单元格；如果该单元格与r中任何单元格都不邻接，则r不能吸收该单元格，继续遍历G中的下一个单元格；如果r中所有单元格合并后的平均密度小于密度阈值，那么此次扩张失败，即r不能吸收该单元格，并且热点区域r到达边界，跳出循环考察G*中下一个未处理的单元格。

如图3所示，在进行密度单元格扩张时候需要判断两个单元格是否相邻，根据本算法划分得到的单元格不可能相交，因此主要考察单元格的邻接情况就可以了，两个矩形单元格的位置关系包括相离、相邻和相接，表示矩形相邻接的五种情况，需要一种方法能准确判断这五种相邻情况，对于单元格c1,c2，假如c1的中心点为p1，宽为w1，高为h1；c2中心点位p2，宽为w2,高位h2。通过观察可以发现，图中b，c两种情况可以看作是a的特殊情况，它们都是a中矩形在一边上运动产生的重合；而且，如果两个矩形的宽或高相等，那么b，c两种情况继续运动后产生情况d，e，如果两个矩形的宽和高度都不相等，那么矩形相邻接任然可以归属为b，c两种情况。可以从横向和纵向两个维度来判断两个矩形是否邻接，如果(w1+w2)/2 < |p1.x-p2.x|，则矩形横向分离，如果(h1+h2)/2 < |p1.y- p2.y|，则矩形纵向分离，如果两个矩形既不横向分离又不纵向分离，则可认定两个矩形相邻或相接。 

步骤3）根据区域轨迹支持数及轨迹数据在候选热点区域内的停留时间，筛选出热点区域，其步骤包括： 

以候选热点区域集合R和轨迹数据集合T为参数，同时需要设定热点区域轨迹支持度阈值S_R和轨迹在候选区域中最短停留时间阈值。对于每个候选热点区域，遍历轨迹集合，如果轨迹与该区域相交，且轨迹在该区域内停留的时间不小于阈值ts，则该轨迹为候选区域的支持轨迹统计每个区域的支持轨迹，以此计算候选区域的支持度，如果支持度大于阈值S_R，则可以判定该区域为热点区域。