随着移动设备、无线网络和定位技术的发展和广泛应用，可以获得越来越多的位置信息，基于位置服务^{[1, 2, 3]}逐渐成为研究热点.位置预测是基于位置服务的重要组成部分.Markov模型由于符合移动对象移动规律，被广泛用于位置建模和预测^{[4, 5, 6]}.然而，在实际应用中，GPS设备采集的轨迹数据由于采集点丢失或面向新用户等原因往往具有稀疏性，使得依据单个用户的历史轨迹构建状态转移矩阵的Markov位置预测方法准确率不高.针对这种情况，本文提出一种基于用户移动行为相似性聚类的Markov位置预测方法，通过建立用户转移概率矩阵和区域向量进行用户移动行为相似性计算，并在此基础上进行聚类，发现行为相似的用户，用行为相似的一类用户的历史轨迹进行位置预测，从而提高Markov模型的预测准确性.

在位置预测之前，进行数据预处理，将原始GPS轨迹转化为区域轨迹.首先，采用文献[7]中的方法提取具有一定规模和访问频繁程度的十字路口作为关键交通枢纽，在此基础上，将关键交通枢纽这样具有物理意义的位置作为顶点，基于Voronoi 图^[8]进行地图区域划分，将地图划分为以关键交通枢纽为中心的若干区域，并将原始GPS轨迹数据转化为区域轨迹.

给定用户已经走过的区域轨迹S₁,S₂,…,S_l，位置预测即在现有轨迹条件下，计算到达下一个区域S_next的概率p(S_next|S₁,S₂,…,S_l)，并求得使该概率最大的区域S_next.

本文采用一阶Markov模型进行位置预测，因此，预测结果S_pre可表示为

定义1 (用户转移矩阵)设地图划分的区域总数为N，用户i的转移矩阵M_i是一个N×N矩阵，其中第r行、第c列(1≤r≤N，1≤c≤N)的元素M_i(r,c)是用户i的历史轨迹中从区域r转移到区域c的轨迹数目.

定义2 (区域向量)用户i的区域向量V_i是一个N维向量，其第r个元素V_i(r)表示用户i的历史轨迹中从区域r出发向所有区域转移的计数总和.

定义3 (用户转移概率矩阵)用户i的转移概率矩阵P_i是一个N×N矩阵，其中第r行、第c列的元素P_i(r,c)为用户i在当前位置为区域r的条件下转移到区域c的概率.

用户转移矩阵和区域向量可从用户历史轨迹数据统计得出，用户转移概率可通过用户转移矩阵和区域向量计算得到，如式(2)所示，从而建立用户转移概率矩阵:

给定用户i、用户j的用户转移概率矩阵P_i，P_j，以及它们的区域向量V_i， V_j.用户i相对于用户j的移动行为的差异性可表示为式(3)：

其中:括号中的量是基于相对熵的思想，利用用户转移概率矩阵计算的用户i与用户j同处于区域r时转移特性的概率分布差异；括号前的量是基于区域向量计算的用户i对区域r的偏好(区域特性).

同理，用户j相对于用户i移动行为的差异性，可计算如式(4):

综合式(3)与式(4)，用户i和用户j的移动行为差异性D_ij定义为

用户i和用户j的移动行为相似度sim_ij为差异性D_ij的倒数，即sim_ij=1/D_ij.

基于2.2节计算的用户移动行为相似性，本文借鉴文献[9]中的方法，通过最大化类的内聚程度进行聚类.

定义4 (用户相似矩阵)设K为参加聚类的用户总数，用户相似矩阵A是一个K×K矩阵，元素A_ij为用户i和用户j间的移动行为相似度(K≥i,j≥1).为了方便，将对角线上元素置为0.

定义5 (聚类概率向量)聚类概率向量z是一个K维向量.其元素z_i为用户i出现在聚类z的概率(K≥i≥1).

好的聚类应保证同一类中的用户具有好的内聚性，体现在用户相似矩阵中，这些用户应该具有较大的移动行为相似度.式(6)可表示与向量z相对应的类的内聚程度^[9]：

g(z)越大则用户之间的关系越紧密，则越有可能成为一类，这样就把用户聚类的问题转化为寻找合适的向量z,使得类的内聚程度g(z)达到最大值，如式(7)所示:

具体聚类过程如算法1所示.

算法1 基于移动行为相似性的用户聚类算法

输入：用户转移概率矩阵集MPSet[]、区域向量集MVSet[]、用户转移矩阵集MSet[]

输出：聚类集合Cluster[]，用户类的转移概率矩阵集D[]

1)计算用户相似矩阵A;

2)c=1;i=0;

3)while用户集U非空do

4) 对式(7)进行求解，得到向量z;

5) 向量z中非零的元素对应的用户放入聚类Cluster[c-1];

6) 删掉用户集U、向量z和矩阵A中已聚类用户的信息，得到新的用户集U、向量z和矩阵A;

7) c=c+1;

8)while i<c do

9) 将Cluster[i]中所有用户的转移矩阵和区域向量加和保存到CSet[i]和CVSet[i]中;

10) 由CSet[i]和CVSet[i]利用式(2)计算用户类i的转移概率矩阵D[i];

11) i++;

12)return Cluster，D

经过2.3节的聚类算法得到多个用户聚类，在基于聚类的位置预测中，首先基于贝叶斯的思想为用户确定所属聚类，即计算用户当前轨迹为S₁,S₂,…,S_l时属于类别C_k的概率，如式(8)所示，选择概率最大者作为用户所属类别.

式(8)中分母对于所有类别都是相同的，因此只需要比较分子的大小.其中:p(C=C_k)表示类别为C_k的先验概率，可由该聚类中用户的数量和总用户数量求出；p(S₁,S₂,…,S_l|C=C_k)是类别为C_k的聚类中轨迹S₁,S₂,…,S_l出现的概率，可通过聚类C_k的转移概率矩阵D_Ck求出.

上述过程可得出当前用户所属的聚类，基于此，Markov位置预测可基于一类用户的转移概率矩阵进行.设用户聚类C_k的转移概率矩阵D_Ck如式(9)所示:

设用户当前所在的位置是区域S_i(1≤i≤N),则S_i所在行概率最大者所对应的列就是用户最可能前往的下一个位置.

本文实验环境为Intel(R) Core(TM2) Duo E8500 CPU，4 GB内存，500 GB硬盘，操作系统为Windows XP.所用的数据集是北京市10 357辆出租车的GPS轨迹真实数据集^[10].

图 1对比了本文基于Voronoi图的区域划分方法与通常的网格区域划分方法对于位置预测准确率的影响.

图 1(Figure 1)

Fig. 1

图 1 区域划分的有效性 Fig. 1 The effectiveness of region partitioning

从图 1可以看出，在二环以外，基于Voronoi图进行区域划分的位置预测准确率高于网格区域划分，而在二环以内，出现相反的情况.原因在于，在二环以内，重要交通枢纽非常多，导致基于Voronoi图所划分的区域粒度过细，所预测的区域即使离实际区域非常近，但是可能分属于两个不同的区域，被划为了预测错误的情况.

图 2对比了不带用户聚类(without clustering,WITHOUTC)、基于密度的聚类(density-based spatial clustering of applications with noise,DBSACN)以及本文基于移动行为相似性的用户聚类(user clustering based on mobile behavior similarity,UCMBS)在预测结果上的准确率.整体来看，对用户进行聚类比不带有用户聚类的位置预测准确率更高.轨迹长度较小时，基于UCMBS的位置预测准确率低于基于DBSCAN的位置预测准确率;但是，随着轨迹长度的增加，基于UCMBS的预测准确率增长迅速，超过了DBSCAN.这是因为轨迹长度越长，当前用户的轨迹信息越充分，得出用户所属的聚类也就越准确，从而预测准确性越高.

图 2(Figure 2)

Fig. 2

图 2 用户聚类对于位置预测准确性的影响 Fig. 2 The effect of clustering on location prediction accuracy

由于采集点丢失或出现新用户等原因，GPS数据往往具有稀疏性，以往基于单个用户轨迹进行位置预测的准确率较低.针对这种情况，本文提出了基于用户移动行为相似性聚类的Markov位置预测方法，并提出了同时考虑用户转移特性和区域特性的移动行为相似性测度.真实数据上的实验表明了本文所提出的位置预测方法相比于不进行用户聚类和基于其他聚类方法的位置预测具有更高的准确率.