CN108834077A - 基于用户移动特性的跟踪区划分方法、装置及电子设备 - Google Patents

Abstract

本发明提供了基于用户移动特性的跟踪区划分方法、装置及电子设备，利用预设的提取方法在用户GPS定位点中确定的途经点和停留点，然后依此确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值，初始化当前距离权重和当前访问频率权重，再执行以下聚类过程：根据相关参数和预设的相似度计算公式，分别计算各小区与各跟踪区的区域中心的相似度，并将各小区归类到与其相似度最大的跟踪区中，得到当前聚类结果；如果当前聚类结果与上一聚类结果不相同，则返回执行聚类过程；如果当前聚类结果与上一聚类结果相同，则将当前聚类结果作为跟踪区的划分结果。采用本发明，划分的跟踪区具有较高的稳定性，可以避免频繁的位置更新，降低位置管理的开销。

Description

基于用户移动特性的跟踪区划分方法、装置及电子设备

技术领域

本发明涉及通信技术领域，特别是涉及一种基于用户移动特性的跟踪区划分方法、装置及电子设备。

背景技术

人的移动过程反映着纷繁复杂的移动特性，对诸多行业的发展有着重要意义。随着无线通信、移动定位、传感器网络和移动互联网技术的快速发展以及带有定位功能的移动终端的普及，获取长周期、大规模、高精度的个体移动轨迹成为可能，这些轨迹对应的数据为分析人类移动行为提供了充足的资源。通过统计分析和数据发掘等方法对这些收集到的真实的大规模个体移动轨迹数据进行分析，可以获取用户移动行为的特征，从而将其运用到位置管理技术中。在通信技术领域中，为了支持移动用户在整个通信网络覆盖范围内移动时，为其提供连续性的通信和业务，移动性管理实体可以通过位置管理技术实现对移动用户位置的跟踪。在位置管理技术的研究中，位置管理技术通常包括位置更新和位置查找，其中，位置更新和位置查找均以位置管理相关区域(可以称为位置区、跟踪区或寻呼区等)的划分为基础。

在4G及5G网络中，移动性管理实体在进行位置管理相关区域的划分时，通常将用户的移动轨迹划分成一系列的跟踪区(Tracking Area，TA)，每个跟踪区包含一个或多个蜂窝小区，一组TA可以组成一个跟踪区列表(TAL，Tacking Area List)。现有技术通常使用建模和聚类等理论分析的方法对跟踪区进行划分，在进行聚类时，通常采用随机选取初始聚类中心的方法，并且只从空间的角度进行聚类。

然而，发明人在实现本发明的过程中发现，现有技术至少存在如下问题：在进行聚类时，现有技术采用随机选取初始聚类中心的方法，并且只从空间的角度进行聚类，这样会导致移动用户在两个相邻的跟踪区间移动时出现频繁的位置更新的情况，并且位置管理的开销较大。

发明内容

本发明实施例的目的在于提供一种基于用户移动特性的跟踪区划分的方法、装置及电子设备，以避免移动用户在两个相邻的跟踪区间移动时出现频繁的位置更新的情况，并降低位置管理的开销。具体技术方案如下：

第一方面，提供了一种基于用户移动特性的跟踪区划分方法，所述方法包括：

利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点；

根据所述途径点和所述停留点，确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值；

初始化当前距离权重和当前访问频率权重；

执行以下聚类过程：根据所述当前距离权重、所述当前访问频率权重、所述跟踪区的总数目、所述各跟踪区的区域中心的坐标值、所述轨迹数据经过的各小区的坐标值、所述各小区的访问频率、所述各跟踪区的区域中心的访问频率和预设的相似度计算公式，分别计算所述各小区与所述各跟踪区的区域中心的相似度，并将所述各小区归类到与其相似度最大的跟踪区中，得到当前聚类结果；

如果所述当前聚类结果与上一聚类结果不相同，则根据所述当前聚类结果中各跟踪区包含的各小区的坐标值和各小区的访问频率，更新所述各跟踪区的区域中心的坐标值和所述各跟踪区的区域中心的访问频率；根据预设的距离权重计算公式和预设的访问频率权重计算公式，更新所述当前距离权重和当前访问频率权重，并返回执行所述聚类过程；

如果所述当前聚类结果与上一聚类结果相同，则将所述当前聚类结果作为跟踪区的划分结果。

可选的，所述利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点，包括：

从用户移动轨迹数据中的全球定位系统GPS定位点中的第一个GPS定位点开始，每隔预设的时间间隔，根据所述时间间隔内包含的各GPS定位点，确定一个途经点；

根据预设的时间阈值ΔT、距离阈值ΔD、预设的停留点计算公式和t_j-t_i≥ΔT，将符合所述停留点计算公式的各GPS定位点作为停留点，其中，(x_i,y_i,t_i)和(x_j,y_j,t_j)表示两个GPS定位点的经纬度和定位时间。

可选的，所述根据所述途径点和所述停留点，确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值，包括：

将所述途经点的数目与所述停留点的数目之和作为跟踪区的总数目，并将所述途经点的坐标值和所述停留点的坐标值分别作为各跟踪区的区域中心的坐标值初始值。

可选的，所述初始化当前距离权重和当前访问频率权重，包括：

将当前距离权重的初始值和当前访问频率权重的初始值分别设置为1/2。

第二方面，提供了一种基于用户移动特性的跟踪区划分装置，所述装置包括：

提取模块，用于利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点；

确定模块，用于根据所述途径点和所述停留点，确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值；

初始化模块，用于初始化当前距离权重和当前访问频率权重；

执行模块，用于执行以下聚类过程：根据所述当前距离权重、所述当前访问频率权重、所述跟踪区的总数目、所述各跟踪区的区域中心的坐标值、所述轨迹数据经过的各小区的坐标值、所述各小区的访问频率、所述各跟踪区的区域中心的访问频率和预设的相似度计算公式，分别计算所述各小区与所述各跟踪区的区域中心的相似度，并将所述各小区归类到与其相似度最大的跟踪区中，得到当前聚类结果；

更新模块，用于如果所述当前聚类结果与上一聚类结果不相同，则根据所述当前聚类结果中各跟踪区包含的各小区的坐标值和各小区的访问频率，更新所述各跟踪区的区域中心的坐标值和所述各跟踪区的区域中心的访问频率；根据预设的距离权重计算公式和预设的访问频率权重计算公式，更新所述当前距离权重和当前访问频率权重，并返回执行所述聚类过程；

确认模块，用于如果所述当前聚类结果与上一聚类结果相同，则将所述当前聚类结果作为跟踪区的划分结果。

可选的，所述提取模块具体用于：

从用户移动轨迹数据中的全球定位系统GPS定位点中的第一个GPS定位点开始，每隔预设的时间间隔，根据所述时间间隔内包含的各GPS定位点，确定一个途经点；

根据预设的时间阈值ΔT、距离阈值ΔD、预设的停留点计算公式和t_j-t_i≥ΔT，将符合所述停留点计算公式的各GPS定位点作为停留点，其中，(x_i,y_i,t_i)和(x_j,y_j,t_j)表示两个GPS定位点的经纬度和定位时间。

可选的，所述确定模块具体用于：

将所述途经点的数目与所述停留点的数目之和作为跟踪区的总数目，并将所述途经点的坐标值和所述停留点的坐标值分别作为各跟踪区的区域中心的坐标值初始值。

可选的，所述初始化模块具体用于：

将当前距离权重的初始值和当前访问频率权重的初始值分别设置为1/2。

第三方面，提供了一种电子设备，所述电子设备包括处理器、通信接口、存储器和通信总线，其中，所述处理器、所述通信接口、所述存储器通过所述通信总线完成相互间的通信；

所述存储器，用于存放计算机程序；

所述处理器，用于执行所述存储器上所存放的程序时，实现上述任一所述的基于用户移动特性的跟踪区划分方法的方法步骤。

第四方面，本发明实施例还提供了一种计算机可读存储介质，所述计算机可读存储介质中存储有指令，当其在计算机上运行时，使得计算机执行上述任一所述的基于用户移动特性的跟踪区划分方法。

第五方面，本发明实施例还提供了一种包含指令的计算机程序产品，当其在计算机上运行时，使得计算机执行上述任一所述的基于用户移动特性的跟踪区划分方法。

本发明实施例提供的一种基于用户移动特性的跟踪区划分方法、装置、电子设备、存储介质及计算机程序产品，利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点，然后根据途径点和所述停留点，确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值，然后初始化当前距离权重和当前访问频率权重，再执行以下聚类过程：根据当前距离权重、当前访问频率权重、跟踪区的总数目、各跟踪区的区域中心的坐标值、轨迹数据经过的各小区的坐标值、各小区的访问频率、各跟踪区的区域中心的访问频率和预设的相似度计算公式，分别计算各小区与各跟踪区的区域中心的相似度，并将各小区归类到与其相似度最大的跟踪区中，得到当前聚类结果；如果当前聚类结果与上一聚类结果不相同，则根据当前聚类结果中各跟踪区包含的各小区的坐标值和各小区的访问频率，更新各跟踪区的区域中心的坐标值和各跟踪区的区域中心的访问频率，再根据预设的距离权重计算公式和预设的访问频率权重计算公式，更新当前距离权重和当前访问频率权重，并返回执行所述聚类过程；如果当前聚类结果与上一聚类结果相同，则将当前聚类结果作为跟踪区的划分结果。

采用本发明实施例提供的技术方案，在实现跟踪区划分的聚类过程中，综合考虑了用户移动轨迹在时间和空间上的特性，可以根据各用户移动轨迹数据划分对应的跟踪区，在划分跟踪区时，跟踪区数目和初始的跟踪区中心(即跟踪区的第一中心)根据途经点和停留点确定，这样划分的跟踪区具有较高的稳定性，可以避免移动用户在两个相邻的跟踪区间移动时出现频繁的位置更新的情况，并且有效地降低了位置管理的开销。当然，实施本发明的任一产品或方法必不一定需要同时达到以上所述的所有优点。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍。

图1为本发明实施例提供的一种基于用户移动特性的跟踪区划分方法的流程图；

图2为本发明实施例提供的一种提取途径点和停留点的示意图；

图3为本发明实施例提供的一种提取某用户一整天的GPS定位点得到的途径点和停留的示意图；

图4为采用本发明实施例提供的基于用户移动特性的跟踪区划分方法得到的跟踪区的示意图；

图5为本发明实施例提供的一种基于用户移动特性的跟踪区划分装置的结构示意图；

图6为本发明实施例提供的电子设备的结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行描述。

本发明实施例提供的一种基于用户移动特性的跟踪区划分方法、装置及电子设备，在实现跟踪区划分的聚类过程中，综合考虑了用户移动轨迹在时间和空间上的特性，可以根据各用户移动轨迹数据划分对应的跟踪区，在划分跟踪区时，跟踪区数目和初始的跟踪区中心(即跟踪区的第一中心)根据途经点和停留点确定，这样划分的跟踪区具有较高的稳定性，可以避免移动用户在两个相邻的跟踪区间移动时出现频繁的位置更新的情况，并且有效地降低了位置管理的开销。本发明实施例的执行主体可以是移动性管理实体。

下面首先对本发明实施例提供的基于用户移动特性的跟踪区划分方法进行介绍。

如图1所示，本发明实施例提供的基于用户移动特性的跟踪区划分方法可以包括以下步骤：

S110：利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点。

在本发明实施例中，技术人员可以预先将用户的移动轨迹数据存储到移动性管理实体中，移动轨迹数据由用户的GPS(Global Positioning System，全球定位系统)定位点组成。移动性管理实体可以获取用户移动轨迹数据，然后利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点。

可选的，作为本发明实施例的一种实施方式，可以按照以下方式确定途经点和停留点：从用户移动轨迹数据中的全球定位系统GPS定位点中的第一个GPS定位点开始，每隔预设的时间间隔，根据时间间隔内包含的各GPS定位点，确定一个途经点；根据预设的时间阈值ΔT、距离阈值ΔD、预设的停留点计算公式和t_j-t_i≥ΔT，将符合所述停留点计算公式的各GPS定位点作为停留点，其中，(x_i,y_i,t_i)和(x_j,y_j,t_j)表示两个GPS定位点的经纬度和定位时间。

在本发明实施例中，一个GPS定位点即为一条GPS数据记录，表示用户所处的位置及产生这条记录的时间，GPS定位点可形式化表示为：

p_i＝(x_i,y_i,t_i)

其中，x_i,y_i代表该点的经纬度，t_i代表该点定位时间。

移动轨迹是按照时间顺序依次排列的各GPS定位点组成，其可形式化表示为：

Traj＝p₁,p₂,…,p_n

其中，Traj代表移动轨迹，p_n代表第n个GPS定位点。

移动性管理实体可以从用户移动轨迹数据中的GPS定位点中的第一个GPS定位点开始，每隔预设的时间间隔，根据该时间间隔内包含的各GPS定位点，确定一个途经点。例如，预设的时间间隔为10分钟，每隔10分钟取这10分钟内的所有GPS定位点的坐标值的平均值作为一个途经点的坐标值，以此方式确定途经点。

如果用户在某个区域的停留时间超过了某一时间阈值，且该区域的半径小于一个距离阈值，可以将这个区域作为一个停留点。在本文中，将停留点定义为一系列相邻的GPS定位点的集合抽象出的一个虚拟的点，并用该区域内所有GPS定位点的坐标值的平均值来代表这个停留点的坐标值。时间阈值可以预设为ΔT，距离阈值可以预设为ΔD，如果该区域内的任意两点满足下面的公式(1)和公式(2)，则可以将该区域作为一个停留点。

t_j-t_i≥ΔT (2)

其中，(x_i,y_i,t_i)和(x_j,y_j,t_j)表示该区域中的任意两个GPS定位点。

例如，结合人们平时移动的规律，通常认为当一个用户花费超过30分钟的时间在不超过200米的范围内活动，则该区域可以作为一个停留点，即ΔD＝200m，ΔT＝30min，当两定位点p_i和p_j满足公式(1)和公式(2)时，则可以认为由p_i到p_j(包括p_i和p_j)之间所有的定位点共同抽象出一个停留点。停留点的坐标值可以由p_i到p_j之间的各定位点的坐标值的平均值来表示，计算方式如下：

其中，s.x和s.y代表停留点的经纬度，即停留点的坐标值。

本发明实施例提供的方案中，利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的GPS定位点中，确定途径点和停留点，这样得到的途径点和停留点能够准确的反应用户移动的特性，提高跟踪区划分的稳定性。

S120：根据途径点和停留点，确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值。

在本发明实施例中，移动性管理实体可以将途径点和停留点的总数目作为跟踪区的总数目，或者，将途径点和停留点的总数目与预设阈值的差值作为跟踪区的总数目。另外，移动性管理实体可以将途经点和停留点均作为跟踪区的区域中心，或者，将部分途经点和停留点作为跟踪区的区域中心。

可选的，作为本发明实施例的一种实施方式，将途经点的数目与停留点的数目之和作为跟踪区的总数目，并将途经点的坐标值和停留点的坐标值分别作为各跟踪区的区域中心的坐标值初始值。

在本发明实施例中，将途经点的数目与停留点的数目之和作为跟踪区的总数目，并将途经点和停留点均作为各跟踪区的区域中心(也可以称为初始聚类中心)。并将途经点的坐标值和停留点的坐标值分别作为各跟踪区的区域中心的坐标值初始值。这样可以在保证聚类结果稳定性的同时，减少了寻找最优聚类结果时需要计算的次数，从而减少了算法运行的时间，提高算法的效率。

S130：初始化当前距离权重和当前访问频率权重。

在本发明实施例中，移动性管理实体可以初始化当前距离权重和当前访问频率权重，即给当前距离权重和当前访问频率权重设置具体的数值。

可选的，作为本发明实施例的一种实施方式，将当前距离权重的初始值和当前访问频率权重的初始值分别设置为1/2。当计算公式(8)的相似度使用N个参数的权重时，通常将各参数的权重的初始值设置为1/N。

在本发明实施例中，将当前距离权重和当前访问频率权重设置成相等的值，这样可以均衡这两个参数对跟踪区划分的影响程度，提高跟踪区划分的稳定性。当前距离权重可以用W_Dis表示，当前访问频率权重可以用W_Freq表示，如公式(5)所示。

S140：执行以下聚类过程：根据当前距离权重、当前访问频率权重、跟踪区的总数目、各跟踪区的区域中心的坐标值、轨迹数据经过的各小区的坐标值、各小区的访问频率、各跟踪区的区域中心的访问频率和预设的相似度计算公式，分别计算各小区与各跟踪区的区域中心的相似度，并将各小区归类到与其相似度最大的跟踪区中，得到当前聚类结果。

在本发明实施例中，小区是指用户移动轨迹经过的小区，小区的划分方式可以采用目前常用的蜂窝移动通信系统中小区的划分方式，一个小区通常代表一个基站的覆盖范围，小区的坐标可以用基站的坐标表示，或者用基站覆盖范围的中心点坐标表示。在计算各小区与各跟踪区的区域中的相似度时，主要包括以下3个步骤：

第一步，计算各小区与各跟踪区的区域中心的欧式距离：

其中，表示小区C_i(i＝1,2,…,N)到跟踪区的区域中心(即聚类中心)的欧氏距离，和表示第i个小区的坐标，和表示k个聚类中心的坐标。

第二步，计算各小区的访问频率和各聚类中心的访问频率的差值：

其中，表示第i个小区的访问频率与第k个聚类中心的访问频率的差值，表示第i个小区的访问频率，即用户经过第i个小区的次数，表示第k个聚类中心的访问频率。

第三步，计算各小区与各聚类中心的相似度：

其中，表示第i个小区与第k个聚类中心的相似度。

在计算得到小区与各聚类中心的相似度之后，将该小区归类到其相似度最大的跟踪区中，即将小区归类到通过公式(8)得到的最大值的跟踪区中。假如出现一个小区与多个聚类中心的相似度相同，可以随机选取一个聚类中心，并将该小区归类到该聚类中心对应的跟踪区中。

S150：如果当前聚类结果与上一聚类结果不相同，则根据当前聚类结果中各跟踪区包含的各小区的坐标值和各小区的访问频率，更新各跟踪区的区域中心的坐标值和各跟踪区的区域中心的访问频率；根据预设的距离权重计算公式和预设的访问频率权重计算公式，更新当前距离权重和当前访问频率权重，并返回执行聚类过程S140。

在本发明实施例中，在得到聚类结果之后，需要判断当前聚类结果与上一聚类结果不相同，聚类结果是指当前的各跟踪区的区域中心的坐标值和各跟踪区的区域中心的访问频率，其中，当前的各跟踪区的区域中心的坐标值是指各跟踪区归类的各小区的坐标值的平均值，各跟踪区的区域中心的访问频率是指各跟踪区归类的各小区的访问频率的平均值。如果当前聚类结果与上一聚类结果不相同，需要更新各跟踪区的区域中心的坐标值、各跟踪区的区域中心的访问频率、当前距离权重和当前访问频率权重，并返回执行步骤S140。

更新当前距离权重和当前访问频率权重主要包括以下5个步骤：

第一步，根据当前聚类结果，计算所有K个聚类在访问频率这一维度上类间距离之和，如公式(9)所示。其中，表示所有小区C_i,i＝1,2,…,N访问频率的平均值，表示第k个聚类中所有小区访问频率的平均值。

第二步，计算所有K个聚类在访问频率这一维度上类内距离之和，如公式(10)所示。其中，k＝1,2,…K,j＝1,2,…J_k表示第k个聚类中所有小区访问频率的平均值，表示第k个聚类中第j(j＝1,2,…,J_k)个小区访问频率的值。

第三步，计算访问频率这一维度上的类间距离和类内距离的比值。

第四部，根据公式(9)至(11)的思想，进一步计算距离这一维度的类间距离和类内距离的比值，如公式(12)所示。

第五步，更新当前距离权重和当前访问频率的权重。

S160：如果当前聚类结果与上一聚类结果相同，则将当前聚类结果作为跟踪区的划分结果。

在本发明实施例中，如果聚类结果不再变化，即当前聚类结果对应的各跟踪区的区域中心的坐标值和各跟踪区的区域中心的访问频率与上一次的聚类结果相同，则将当前的聚类结果作为跟踪区的划分结果，即完成跟踪区的划分。

本发明实施例提供的基于用户移动特性的跟踪区划分方法，在实现跟踪区划分的聚类过程中，综合考虑了用户移动轨迹在时间和空间上的特性，可以根据各用户移动轨迹数据划分对应的跟踪区，在划分跟踪区时，跟踪区数目和初始的跟踪区中心(即跟踪区的第一中心)根据途经点和停留点确定，这样划分的跟踪区具有较高的稳定性，可以避免移动用户在两个相邻的跟踪区间移动时出现频繁的位置更新的情况，并且有效地降低了位置管理的开销。

如图2所示，为本发明实施例提供的利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法提取途经点和停留点的示意图。图2上部的p1至p16表示16个GPS点位点，图2下部表示采用本发明实施例提供的提取方法得到的途经点和停留点。

如图3所示，为某用户的一整天的GPS点位点转化为途经点和停留点的示意图，图中的黑色圆点表示途径点，五角星表示停留点，图中的横坐标和纵坐标表示经纬度。

如图4所示，为图3对应的用户移动轨迹被划分成跟踪区的示意图，图4中的每个虚线圆圈表示一个跟踪区，虚线圆圈中的每个圆点表示一个小区。

基于相同的技术构思，相应于图1所述的方法实施例，本发明还提供了一种基于用户移动特性的跟踪区划分装置，如图5所示，该装置包括：

提取模块501，用于利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点；

确定模块502，用于根据所述途径点和所述停留点，确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值；

初始化模块503，用于初始化当前距离权重和当前访问频率权重；

执行模块504，用于执行以下聚类过程：根据所述当前距离权重、所述当前访问频率权重、所述跟踪区的总数目、所述各跟踪区的区域中心的坐标值、所述轨迹数据经过的各小区的坐标值、所述各小区的访问频率、所述各跟踪区的区域中心的访问频率和预设的相似度计算公式，分别计算所述各小区与所述各跟踪区的区域中心的相似度，并将所述各小区归类到与其相似度最大的跟踪区中，得到当前聚类结果；

更新模块505，用于如果所述当前聚类结果与上一聚类结果不相同，则根据所述当前聚类结果中各跟踪区包含的各小区的坐标值和各小区的访问频率，更新所述各跟踪区的区域中心的坐标值和所述各跟踪区的区域中心的访问频率；根据预设的距离权重计算公式和预设的访问频率权重计算公式，更新所述当前距离权重和当前访问频率权重，并返回执行所述聚类过程；

确认模块506，用于如果所述当前聚类结果与上一聚类结果相同，则将所述当前聚类结果作为跟踪区的划分结果。

本发明实施例提供的基于用户移动特性的跟踪区划分装置，在实现跟踪区划分的聚类过程中，综合考虑了用户移动轨迹在时间和空间上的特性，可以根据各用户移动轨迹数据划分对应的跟踪区，在划分跟踪区时，跟踪区数目和初始的跟踪区中心(即跟踪区的第一中心)根据途经点和停留点确定，这样划分的跟踪区具有较高的稳定性，可以避免移动用户在两个相邻的跟踪区间移动时出现频繁的位置更新的情况，并且有效地降低了位置管理的开销。

可选的，所述提取模块501具体用于：

从用户移动轨迹数据中的全球定位系统GPS定位点中的第一个GPS定位点开始，每隔预设的时间间隔，根据所述时间间隔内包含的各GPS定位点，确定一个途经点；

根据预设的时间阈值ΔT、距离阈值ΔD、预设的停留点计算公式和t_j-t_i≥ΔT，将符合所述停留点计算公式的各GPS定位点作为停留点，其中，(x_i,y_i,t_i)和(x_j,y_j,t_j)表示两个GPS定位点的经纬度和定位时间。

本发明实施例提供的方案中，利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的GPS定位点中，确定途径点和停留点，这样得到的途径点和停留点能够准确的反应用户移动的特性，提高跟踪区划分的稳定性。

可选的，所述确定模块502具体用于：

将所述途经点的数目与所述停留点的数目之和作为跟踪区的总数目，并将所述途经点的坐标值和所述停留点的坐标值分别作为各跟踪区的区域中心的坐标值初始值。

在本发明实施例中，将途经点的数目与停留点的数目之和作为跟踪区的总数目，并将途经点和停留点均作为各跟踪区的区域中心(也可以称为初始聚类中心)。这样可以在保证聚类结果稳定性的同时，减少了寻找最优聚类结果时需要计算的次数，从而减少了算法运行的时间，提高算法的效率。

可选的，所述初始化模503块具体用于：

将当前距离权重的初始值和当前访问频率权重的初始值分别设置为1/2。

在本发明实施例中，将当前距离权重和当前访问频率权重设置成相等的值，这样可以均衡这两个参数对跟踪区划分的影响程度，提高跟踪区划分的稳定性。

本发明实施例还提供了一种电子设备，如图6所示，包括处理器601、通信接口602、存储器603和通信总线604，其中，处理器601、通信接口602、存储器603通过通信总线604完成相互间的通信；

存储器603，用于存放计算机程序；

处理器601，用于执行存储器603上所存放的程序时，实现如下步骤：

利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点；

根据所述途径点和所述停留点，确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值；

初始化当前距离权重和当前访问频率权重；

执行以下聚类过程：根据所述当前距离权重、所述当前访问频率权重、所述跟踪区的总数目、所述各跟踪区的区域中心的坐标值、所述轨迹数据经过的各小区的坐标值、所述各小区的访问频率、所述各跟踪区的区域中心的访问频率和预设的相似度计算公式，分别计算所述各小区与所述各跟踪区的区域中心的相似度，并将所述各小区归类到与其相似度最大的跟踪区中，得到当前聚类结果；

如果所述当前聚类结果与上一聚类结果不相同，则根据所述当前聚类结果中各跟踪区包含的各小区的坐标值和各小区的访问频率，更新所述各跟踪区的区域中心的坐标值和所述各跟踪区的区域中心的访问频率；根据预设的距离权重计算公式和预设的访问频率权重计算公式，更新所述当前距离权重和当前访问频率权重，并返回执行所述聚类过程；

如果所述当前聚类结果与上一聚类结果相同，则将所述当前聚类结果作为跟踪区的划分结果。

本发明实施例提供的电子设备，在实现跟踪区划分的聚类过程中，综合考虑了用户移动轨迹在时间和空间上的特性，可以根据各用户移动轨迹数据划分对应的跟踪区，在划分跟踪区时，跟踪区数目和初始的跟踪区中心(即跟踪区的第一中心)根据途经点和停留点确定，这样划分的跟踪区具有较高的稳定性，可以避免移动用户在两个相邻的跟踪区间移动时出现频繁的位置更新的情况，并且有效地降低了位置管理的开销。

上述电子设备提到的通信总线可以是外设部件互连标准(Peripheral ComponentInterconnect，简称PCI)总线或扩展工业标准结构(Extended Industry StandardArchitecture，简称EISA)总线等。该通信总线可以分为地址总线、数据总线、控制总线等。为便于表示，图中仅用一条粗线表示，但并不表示仅有一根总线或一种类型的总线。通信接口用于上述电子设备与其他设备之间的通信。

存储器可以包括随机存取存储器(Random Access Memory，简称RAM)，也可以包括非易失性存储器(non-volatile memory)，例如至少一个磁盘存储器。可选的，存储器还可以是至少一个位于远离前述处理器的存储装置。上述的处理器可以是通用处理器，包括中央处理器(Central Processing Unit，简称CPU)、网络处理器(Network Processor，简称NP)等；还可以是数字信号处理器(Digital Signal Processing，简称DSP)、专用集成电路(Application Specific Integrated Circuit，简称ASIC)、现场可编程门阵列(Field－Programmable Gate Array，简称FPGA)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件。

在本发明提供的又一实施例中，还提供了一种计算机可读存储介质，该计算机可读存储介质中存储有指令，当其在计算机上运行时，使得计算机执行上述实施例中任一所述的基于用户移动特性的跟踪区划分方法。

在本发明提供的又一实施例中，还提供了一种包含指令的计算机程序产品，当其在计算机上运行时，使得计算机执行上述实施例中任一所述的基于用户移动特性的跟踪区划分方法。

本发明实施例提供的存储介质和计算机程序产品，在实现跟踪区划分的聚类过程中，综合考虑了用户移动轨迹在时间和空间上的特性，可以根据各用户移动轨迹数据划分对应的跟踪区，在划分跟踪区时，跟踪区数目和初始的跟踪区中心(即跟踪区的第一中心)根据途经点和停留点确定，这样划分的跟踪区具有较高的稳定性，可以避免移动用户在两个相邻的跟踪区间移动时出现频繁的位置更新的情况，并且有效地降低了位置管理的开销。

在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件实现时，可以全部或部分地以计算机程序产品的形式实现。所述计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行所述计算机程序指令时，全部或部分地产生按照本发明实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或数据中心通过有线(例如同轴电缆、光纤、数字用户线(DSL))或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质，(例如，软盘、硬盘、磁带)、光介质(例如，DVD)、或者半导体介质(例如固态硬盘Solid State Disk(SSD))等。

需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者设备中还存在另外的相同要素。

本说明书中的各个实施例均采用相关的方式描述，各个实施例之间相同相似的部分互相参见即可，每个实施例重点说明的都是与其他实施例的不同之处。尤其，对于装置、电子设备、可读存储介质和计算机程序产品实施例而言，由于其基本相似于方法实施例，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。以上所述仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内所作的任何修改、等同替换、改进等，均包含在本发明的保护范围内。

Claims (9)

1.一种基于用户移动特性的跟踪区划分方法，其特征在于，所述方法包括：

利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点；

根据所述途径点和所述停留点，确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值；

初始化当前距离权重和当前访问频率权重；

执行以下聚类过程：根据所述当前距离权重、所述当前访问频率权重、所述跟踪区的总数目、所述各跟踪区的区域中心的坐标值、所述轨迹数据经过的各小区的坐标值、所述各小区的访问频率、所述各跟踪区的区域中心的访问频率和预设的相似度计算公式，分别计算所述各小区与所述各跟踪区的区域中心的相似度，并将所述各小区归类到与其相似度最大的跟踪区中，得到当前聚类结果；

如果所述当前聚类结果与上一聚类结果不相同，则根据所述当前聚类结果中各跟踪区包含的各小区的坐标值和各小区的访问频率，更新所述各跟踪区的区域中心的坐标值和所述各跟踪区的区域中心的访问频率；根据预设的距离权重计算公式和预设的访问频率权重计算公式，更新所述当前距离权重和当前访问频率权重，并返回执行所述聚类过程；

如果所述当前聚类结果与上一聚类结果相同，则将所述当前聚类结果作为跟踪区的划分结果。

2.根据权利要求1所述的方法，其特征在于，所述利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点，包括：

从用户移动轨迹数据中的全球定位系统GPS定位点中的第一个GPS定位点开始，每隔预设的时间间隔，根据所述时间间隔内包含的各GPS定位点，确定一个途经点；

根据预设的时间阈值ΔT、距离阈值ΔD、预设的停留点计算公式和t_j-t_i≥ΔT，将符合所述停留点计算公式的各GPS定位点作为停留点，其中，(x_i，y_i，t_i)和(x_j，y_j，t_j)表示两个GPS定位点的经纬度和定位时间。

3.根据权利要求1所述的方法，其特征在于，所述根据所述途径点和所述停留点，确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值，包括：

将所述途经点的数目与所述停留点的数目之和作为跟踪区的总数目，并将所述途经点的坐标值和所述停留点的坐标值分别作为各跟踪区的区域中心的坐标值初始值。

4.根据权利要求1所述的方法，其特征在于，所述初始化当前距离权重和当前访问频率权重，包括：

将当前距离权重的初始值和当前访问频率权重的初始值分别设置为1/2。

5.一种基于用户移动特性的跟踪区划分装置，其特征在于，所述装置包括：

提取模块，用于利用预设的基于时间的途径点提取方法和预设的基于阈值的停留点提取方法，在用户移动轨迹数据的全球定位系统GPS定位点中，确定途径点和停留点；

确定模块，用于根据所述途径点和所述停留点，确定跟踪区的总数目和各跟踪区的区域中心的坐标值初始值；

初始化模块，用于初始化当前距离权重和当前访问频率权重；

执行模块，用于执行以下聚类过程：根据所述当前距离权重、所述当前访问频率权重、所述跟踪区的总数目、所述各跟踪区的区域中心的坐标值、所述轨迹数据经过的各小区的坐标值、所述各小区的访问频率、所述各跟踪区的区域中心的访问频率和预设的相似度计算公式，分别计算所述各小区与所述各跟踪区的区域中心的相似度，并将所述各小区归类到与其相似度最大的跟踪区中，得到当前聚类结果；

更新模块，用于如果所述当前聚类结果与上一聚类结果不相同，则根据所述当前聚类结果中各跟踪区包含的各小区的坐标值和各小区的访问频率，更新所述各跟踪区的区域中心的坐标值和所述各跟踪区的区域中心的访问频率；根据预设的距离权重计算公式和预设的访问频率权重计算公式，更新所述当前距离权重和当前访问频率权重，并返回执行所述聚类过程；

确认模块，用于如果所述当前聚类结果与上一聚类结果相同，则将所述当前聚类结果作为跟踪区的划分结果。

6.根据权利要求5所述的装置，其特征在于，所述提取模块具体用于：

从用户移动轨迹数据中的全球定位系统GPS定位点中的第一个GPS定位点开始，每隔预设的时间间隔，根据所述时间间隔内包含的各GPS定位点，确定一个途经点；

根据预设的时间阈值ΔT、距离阈值ΔD、预设的停留点计算公式和t_j-t_i≥ΔT，将符合所述停留点计算公式的各GPS定位点作为停留点，其中，(x_i，y_i，t_i)和(x_j，y_j，t_j)表示两个GPS定位点的经纬度和定位时间。

7.根据权利要求5所述的装置，其特征在于，所述确定模块具体用于：

将所述途经点的数目与所述停留点的数目之和作为跟踪区的总数目，并将所述途经点的坐标值和所述停留点的坐标值分别作为各跟踪区的区域中心的坐标值初始值。

8.根据权利要求5所述的装置，其特征在于，所述初始化模块具体用于：

将当前距离权重的初始值和当前访问频率权重的初始值分别设置为1/2。

9.一种电子设备，其特征在于，所述电子设备包括处理器、通信接口、存储器和通信总线，其中，所述处理器、所述通信接口、所述存储器通过所述通信总线完成相互间的通信；

所述存储器，用于存放计算机程序；所述处理器，用于执行所述存储器上所存放的程序时，实现权利要求1-4任一所述的方法步骤。