1.一种基于基站标号轨迹的运动模式挖掘方法,其特征在于:包括如下步骤:
(1)历史基站标号轨迹数据集构建:首先对用户智能手机当前所连接基站的标号进行连续采集,然后对采集到的数据进行轨迹分割得到若干基站标号轨迹数据以形成历史基站标号轨迹数据集;
(2)基站间相似度计算:基于历史基站标号轨迹数据集分析基站间的切换模式,在此基础上估计基站间的相似度;
(3)运动模式挖掘:将基站间相似度融入基于前缀扩展的序列模式挖掘算法,从历史基站标号轨迹数据集中挖掘运动模式,步骤如下:(3-1)算法准备:算法准备包括如下步骤:
(3-1-1)建立基站切换有向图G:图的结点代表基站,结点c1到c2的边代表在历史基站标号轨迹中出现过c1直接切换到c2的情况,即发生切换时c1和c2在轨迹中是相邻的,则G(c)代表基站c可以直接切换到的基站的集合;
(3-1-2)建立基站相似度邻接链表T:表头向量中每个头结点代表一个基站,头结点c指向的单链表包含了所有与基站c相似度大于指定阈值的基站,该单链表的表结点按照相似度从大到小排列,则T(c)[i]代表与基站c相似度第i大的基站,其中基站间相似度由步骤(2)计算得到;
(3-1-3)初始化算法:算法初始化工作包括:设置前缀集all_prefixes为空;设置当前前缀cur_prefix为空字符串;设置当前投影序列集PS为历史基站标号轨迹数据集,并设置每个投影序列P的置信度P.conf为1;
(3-2)生成频繁基站集:若cur_prefix为空字符串,则从所有基站中寻找频繁基站;反之,则从G(lc)中寻找频繁基站,其中lc为cur_prefix最后一个字符所代表的标号对应的基站;
从一个基站集CS中寻找频繁基站的方法为:对CS中每一个基站c,首先计算当前投影序列集中每一条投影序列对其的支持度,然后求和;最后,支持度总和大于指定阈值的基站即为频繁基站;
投影序列P对基站c的支持度support(c,P)的计算公式如下:
其中,P.conf代表P的置信度;
(3-3)生成投影序列集:对频繁基站集中的每个基站c,过程如下:
(3-3-1)更新当前前缀cur_prefix,并将更新的cur_prefix加入前缀集all_prefixes;
(3-3-2)设置新投影序列集NPS为空;
(3-3-3)对当前投影序列集中的每个投影序列P,基于c和P生成一个新的投影序列NP,若NP不为空则加入NPS;
(3-4)迭代算法:若新投影序列集NPS不为空,则将NPS作为当前投影序列集,转向步骤(3-2);
(3-5)生成运动模式:对all_prefixes中的每一个前缀,将其代表的字符串转化为对应的基站序列,该基站序列即为一个运动模式。
2.如权利要求1所述的一种基于基站标号轨迹的运动模式挖掘方法,其特征在于:所述步骤(2)中,采用回归算法估计基站间的相似度,步骤如下:(2-1)构造训练数据集:给定一个历史基站标号轨迹数据集,首先通过特定的网络服务接口查询其中包含的所有基站的实际位置;然后,基于基站实际位置计算每对基站间的实际物理距离;最后,基于基站间实际物理距离计算每对基站间的相似度真实值;基站c1和c2的相似度真实值ts(c1,c2)的计算公式如下:其中,d(c1,c2)为基站c1和c2的实际物理距离,单位:千米;
(2-2)抽取基站间切换模式特征:对于训练数据集中包含的任意一对基站,基于其在训练数据集中表现出的切换模式,抽取切换模式特征,切换模式特征包括本地切换模式特征和K近邻切换模式特征两大类;
本地切换模式特征包括三类:同现率、振荡次数均值和最大值以及加权切换次数均值和最大值;
K近邻切换模式特征包括三类:K近邻同现率、K近邻振荡次数均值和K近邻加权切换次数均值;
(2-3)训练回归器:基于训练数据集中包含的所有基站对的切换模式特征和相似度真实值,采用回归算法训练一个回归器;
(2-4)计算位置信息未知的基站间的相似度:给定一对实际位置未知的基站c1和c2,首先抽取c1和c2在历史基站标号轨迹数据集中的切换模式特征,然后采用训练好的回归器得到c1和c2的相似度估计值s(c1,c2)。
3.如权利要求2所述的一种基于基站标号轨迹的运动模式挖掘方法,其特征在于:所述步骤(2-2)中,对于一对基站c1和c2,同现率指c1和c2同时出现的轨迹数量与c1和c2至少有一个出现的轨迹数量的比例;
c1和c2的一次振荡指在一条轨迹中由c1切换到c2再切换回c1或由c2切换到c1再切换回c2,振荡次数均值指c1和c2在所有c1和c2同时出现的轨迹中振荡次数的平均值,振荡次数最大值指c1和c2在所有c1和c2同时出现的轨迹中振荡次数的最大值;
c1和c2在基站标号轨迹Q中的加权切换次数wsc(c1,c2,Q)的计算公式如下:其中,n为c1和c2在Q中发生切换的次数,intervali为c1和c2发生第i次切换时间隔的基站数量,加权切换次数均值指c1和c2在所有c1和c2同时出现的轨迹中加权切换次数的平均值,加权切换次数最大值指c1和c2在所有c1和c2同时出现的轨迹中加权切换次数的最大值;
对于一对基站c1和c2,K近邻切换模式特征的计算方法为:给定本地切换模式特征F,首先找出除c2外与c1的F值最大的K个基站KNN1,以及除c1外与c2的F值最大的K个基站KNN2;然后,求c2与KNN1中每个基站的F值,以及c1与KNN2中每个基站的F值;最后,计算这些值的平均值。
4.如权利要求1~3之一所述的一种基于基站标号轨迹的运动模式挖掘方法,其特征在于:所述(3-3-1)中,基于基站c更新当前前缀cur_prefix的方法为:将c的标号作为一个字符附加到cur_prefix代表的字符串的末尾。
5.如权利要求1~3之一所述的一种基于基站标号轨迹的运动模式挖掘方法,其特征在于:所述(3-3-3)中,基于基站c和投影序列P生成一个新的投影序列NP的方法为:若c在P中出现,则NP为c在P中第一次出现的位置到P的末尾构成的子序列,并设置NP.conf为P.conf;
若T(c)[i]在P中出现,则NP为T(c)[i]在P中第一次出现的位置到P的末尾构成的子序列,并设置NP.conf为s(c,T(c)[i])×P.conf,否则,NP为空。