EN中文

地球信息科学学报 >

2015 , Vol. 17 >Issue 4: 391 - 400

DOI: https://doi.org/10.3724/SP.J.1047.2015.00391

匿名集序列规则与转移概率矩阵的空间预测和实验

  • 张海涛 , * ,
  • 葛国栋 ,
  • 黄慧慧 ,
  • 徐亮
展开
  • 南京邮电大学 地理与生物信息学院, 南京 210003

作者简介：张海涛（1978-）,男,博士,副教授,研究方向为移动GIS理论方法与关键技术、时空数据挖掘、LBS隐私保护。E-mail:

收稿日期: 2014-10-11

  要求修回日期: 2014-10-31

  网络出版日期: 2015-04-10

基金资助

2010年度江苏政府留学奖学金项目

国家自然科学基金项目“基于大时空范围LBS匿名集的推理攻击及隐私保护”(41201465)

江苏省自然科学基金项目“对抗基于时空关联规则推理攻击的LBS隐私保护研究”(BK2012439)

收起

A Method of Spatial Prediction Based on Transition Probability Matrix and Sequential Rules of Spatial-temporal K-anonymity Datasets

  • ZHANG Haitao , * ,
  • GE Guodong ,
  • HUANG Huihui ,
  • XU Liang
Expand
  • College of Geographic and Biologic Information, Nanjing University of Posts & Telecommunications, Nanjing 210003, China
*Corresponding author: ZHANG Haitao, E-mail:

Received date: 2014-10-11

  Request revised date: 2014-10-31

  Online published: 2015-04-10

Copyright

《地球信息科学学报》编辑部 所有
Fold

摘要

随着位置服务（Location Based Service,LBS）的广泛应用,隐私保护成为LBS进一步深入发展亟待解决的问题,时空K-匿名成为一个主流方向。LBS应用服务器存储用户执行连续查询生成的历史匿名数据集,分析大时空尺度历史的匿名数据集,空间预测可以实现LBS应用的个性化服务。本文提出了一种融合概率统计与数据挖掘2种典型技术——马尔科夫链与序列规则,对匿名数据集中包含的特定空间区域进行预测的方法。方法包括4个过程：（1）分析序列规则、马尔科夫过程进行预测的特点;（2）以匿名数据集序列规则的均一化置信度为初始转移概率,构建n步转移概率矩阵;（3）设计以n步转移概率矩阵进行概略空间预测的方法,以及改进的指定精确路径的空间预测方法;（4）实验验证方法的性能。结果证明,该方法具有模型结构建立速度快、精确空间预测概率与真实概率的近似度可灵活调节等优点,具有可用性。

关键词： 时空K-匿名; 序列规则; 马尔科夫链; 转移概率矩阵; 空间预测

本文引用格式

张海涛 , 葛国栋 , 黄慧慧 , 徐亮 . 匿名集序列规则与转移概率矩阵的空间预测和实验[J]. 地球信息科学学报, 2015 , 17(4) : 391 -400 . DOI: 10.3724/SP.J.1047.2015.00391

Abstract

Recently, spatial-temporal K-anonymity has become a prominent method among a series of techniques for user privacy protection in Location Based Services (LBS) applications, because of its easy implementation and broad applicability. Analyzing spatial prediction scenarios based on spatial-temporal K-anonymity datasets is important in improving the utilization of LBS anonymity datasets for individualized services. In this paper, we present a spatial prediction method by combining the advantages of probabilistic statistics techniques and data mining techniques. The detailed process is divided into four phases: Phase 1, the predictive characteristics based on sequential rules and Markova chain are studied, and then an algorithm is designed to compute the n-step transition probability matrices of normalized sequential rules mined from sequences of spatial-temporal K-anonymity datasets; Phase 2, directly adopting the n-step transition probability matrices of example datasets, the simple predictions are performed; however, the drawback of this method is also found: the full path of the simple predictions cannot be learned, which is very important to the analysis of behavior patterns of LBS users; therefore in Phase 3, a precise predictive algorithm is designed, which recursively discovers the detailed k step path, its transition probability from the detailed k-1 step, and the simple k step that includes the start and the stop node only; and in Phase 4, simulation experiments are conducted, while the experimental results demonstrate that the proposed approach can build the predictive model faster than traditional methods, and can also adjust the accuracy of the predictions flexibly by setting different confidence thresholds for sequential rules of datasets.

Key words： spatial-temporal K-anonymity; sequential rules; Markov chain; transition probability matrix; spatial prediction.

1 引言

移动通信和定位技术的快速发展,使得位置服务（LBS）成为通信技术、地理信息等领域一个新兴的研究方向[1]。随着LBS的深入发展与广泛应用,位置隐私泄露与非法使用等隐私安全问题,逐渐成为公众关注的焦点,隐私保护成为LBS进一步深入发展亟待解决的关键问题[2-3]。近年来,LBS位置隐私保护技术的研究,已经取得了一定的进展。2003年由Gruteser等人提出的时空K-匿名方法[4],以数据真实可用、方法实现简洁灵活,更适合LBS移动计算环境等特点,成为近年来研究的主流方法[5-6]。
时空K-匿名方法的基本思想是：要求提交给LBS应用位置服务器的查询请求不再包括精确的时空信息,而替换为由时空近邻的k个用户位置形成的粗粒度的匿名空间区域。时空K-匿名方法可用于LBS的快照查询,也可用于LBS的连续查询[7-9]。本文重点对后者进行分析：以空间网格划分的时空K-匿名方法为例,说明LBS连续查询进行位置隐私保护的过程,基本原理如图1所示。具体过程描述如下：
Fig. 1 The workflow of generating location anonymity in LBS continuous queries

图1 LBS连续查询的匿名执行过程

（1）根据LBS系统提供位置服务的空间（2维）范围及时间周期,得到离散化的时空格,如图1（a）所示。
（2）通过LBS用户运动轨迹与时空格的匹配,得到与运动轨迹相对应的空间格（图1（b）中的黄色空间格）序列,如图1（b）所示。
（3）LBS用户在运动过程中,根据需要提出连续查询。生成连续查询的时间及所在空间位置与时空格匹配,也可得到对应的空间格序列。连续查询对应的空间格序列（图1（c）中的红色空间格）,是运动轨迹对应空间格序列的子集,如图1（c）所示。
（4）在连续查询对应空间格序列的每个空间格（图1（c）中的红色空间格）,采用时空K-匿名方法生成包括1个或多个空间格的匿名空间区域：统计当前提出匿名查询用户所在空间格包含的用户数（包括提出匿名查询者）,如果用户数小于K值,则搜索并累加其他邻近空间格（图1（d）中的绿色空间格）包括的用户数,直至满足K值要求（用户也可根据系统性能的需要,限定最多可搜索的邻近空间格的数量,如果达到数量限制,仍不能满足要求,则匿名不成功）,最终生成对应连续查询的匿名空间区域数据集（以下简称匿名数据集）,如图1（d）所示。
在实际应用中,应用服务器会记录、存储匿名数据集。分析大尺度的历史匿名数据集,通过空间预测功能,可为LBS的资源优化管理、个性化服务配置等应用提供支持。为此,本文分析序列规则、马尔科夫过程进行预测的特点,提出了一种匿名数据集包含的空间区域序列规则（以下简称匿名集序列规则）与转移概率矩阵,对匿名数据集中包含的特定空间区域进行到达预测的方法。

2 空间预测方法原理

2.1 匿名集序列规则

匿名集序列规则涉及以下基本概念：SD={S,I}表示一个序列数据库,其中,S={s1,s2,…,sm}表示所有序列的集合,I={i1,i2,…,in}表示 S中所有序列包含数据项的集合（简称项集）。对于任一序列su={X1,X2,…,Xv},项集X1,X2,…,Xv具有时间先后关系,且X1,X2,…,Xv均包含于I,即 X 1 , X 2 , ... , X n ⊆ I 。
对应于图1执行过程中,一次连续查询生成的匿名数据集,形成一个以空间格为数据项的匿名集序列,例如,s1={(1,12),(42,43,44),(57,67,77),(80,90,99,100)}。
A→B(SeqSup,SeqConf)表示从众多匿名集序列中挖掘得到一个匿名集序列规则。其中,A,B表示由匿名空间区域（图1(d)中的红色、绿色空间格）构成的项集(为简化问题的描述,本文只考虑匿名集序列规则的前项集、后项集均包括一个空间格的情况。),A称为前项集,B称为后项集,A,B⊆I,且A,B中的项不分先后顺序,即可同时发生;A→B表示：如果项集A出现在一个匿名集序列的项集中,则项集B也将出现在该序列的后续项集中,即项集A和B均出现在同一匿名集序列的项集中,且项集A发生的时间早于项集B。例如,对于上述匿名集序列s1,可以对(1)→(42),(12)→(42),(57)→(80),(42)→(100)等形式的匿名集序列规则提供支持。
SeqSup与SeqConf分别表示度量匿名集序列规则有效性的2个指标：支持度与置信度,其计算公式为：
SeqSup (A→B)=Sup(A⋂B)/|S|（1）
Se q Conf ( A → B ) = Sup ( A ⋂ B ) / Sup ( A ) （2）
式中,|S|表示匿名集序列数据库中所有序列的个数;Sup(A⋂B)表示在匿名集序列数据库中先后包含项集A和项集B的序列个数;Sup(A)表示在匿名集序列数据库中包含项集A的序列个数。由于任意的A⊆I,|S|≥Sup(A)均成立,对于任意的匿名集序列规则r,均有 Se q Conf ( r ) ≥ Se q Sup ( r ) 。
依据上述概念,在对匿名集序列数据进行预处理后,可采用Fournier-Viger等人提出的序列规则挖掘算法[10-13],进行匿名集序列规则的挖掘。表1是一组匿名集序列规则的示例数据。
Tab. 1 Sample datasets of anonymity sequential rules

表1 匿名集序列规则的示例数据

序号 序列规则 置信度
1 A→B 0.2
2 A→C 0.5
3 A→D 0.2
4 B→C 0.7
5 B→E 0.3
6 C→D 0.1
7 C→F 0.6
8 D→F 0.9
9 E→F 0.8

2.2 n步转移概率矩阵

n步转移概率矩阵涉及以下基本定义[14]和定理：
（1）定义1：{Xn,n∈T}表示一个马尔科夫过程,其中,参数T是离散的时间集合,即T={0,1,2,∙∙∙},其相应随机变量Xn,所有可能取值的集合I={i0,i1,i2∙∙∙}称为“状态空间”。
（2）定义2：若一个马尔科夫过程{Xn,n∈T}满足以下条件：
P X n + 1 = x X 1 = x 1 , X 2 = x 2 , ... , X n = x n = P X n + 1 = x X n = x n ，
也即Xn+1相对于过去状态的条件概率分布,仅是Xn的一个函数,则称{Xn,n∈T}为马尔科夫链。
（3）定义3：条件概率pij (n)=P(Xn+1=j,Xn=i),表示马尔科夫链{Xn,n∈T}在时刻n处于状态 i 的条件下,时刻n+1处于状态 j 的概率。
pij (n)也称为马尔科夫链{Xn,n∈T},在时刻n的1步转移概率。如果pij (n)取值与n无关,则 X n , n ∈ T 为齐次马尔科夫链,简记pij (n)为pij。
（4）定义4：若P(1)为马尔科夫链{Xn,n∈T}的所有1步转移概率pij组成的矩阵,且具有性质：① pij≥0,i,j∈I;② ,则称P(1)为1步转移概率矩阵。
（5）定义5：n步转移概率矩阵的定义可以通过类比得出：若P(n)为马尔科夫链{Xn,n∈T}的所有n步转移概率 组成的矩阵,且具有性质：① ;② ,则称P(n)为n步转移概率矩阵。
（6）定理1：对于齐次马尔科夫链{Xn,n∈T},其n步转移概率矩阵P(n)的取值为其n个1步转移概率矩阵P的乘积,即 （结束n步转移概率矩阵计算的条件是：转移概率矩阵包含的所有元素值（即概率值）都低于设定的阈值精度）。
LBS用户在连续匿名查询过程中,依照匿名集序列规则中包含空间区域的运动过程,可看做具有随机特性的一个马尔科夫过程。
匿名集序列规则 A → B ( Se q S up , Se q Conf ) 中,后项集B发生的概率只与前项集A有关,即LBS用户在某一空间区域发生匿名查询的概率,只取决于其前一次匿名查询时所处的空间区域。因此,该马尔科夫过程为马尔科夫链。同时,由于A→B只表示项集A、项集B发生的先后顺序,也即LBS用户在项A集、项集B包含空间区域,提出匿名请求的先后关系,与具体的匿名请求发生时间无关。因此,该马尔科夫链为齐次马尔科夫链。
根据匿名集序列规则置信度的定义可知,其与齐次马尔科夫链的条件概率具有完全一致的统计意义。基于匿名集序列规则数据,可直接得到对应齐次马尔科夫链的1步转移概率。表1数据所对应1步转移概率的图形表达如图2所示。
Fig. 2 State diagram of one-step transition probability from original sequential rules

图2 原始序列规则数据的1步转移概率

但是,由于不满足 的性质,匿名集序列规则数据得到的1步转移概率,并不能直接生成齐次马尔科夫链的1步转移矩阵。例如,图2中从A出发的1步转移概率之和就不为1： = pAB+pAC+pAD=0.9。为此,必须进行归一化操作,处理过程如式（3）所示。
对图2中所有状态进行归一化处理后,得到的1步转移概率的图形表达,如图3所示。
Fig. 3 State diagram of one-step transition probability matrix from normalized sequential rules

图3 归一化序列规则数据的1步转移概率

从1步转移概率得到1步转移概率矩阵P(1),按照定理1计算得到2-4步转移概率矩阵P(2)-P(4),如式（4）所示。
P 1 = A B C D E F A 0 0.2222 0.5556 0.2222 0 0 B 0 0 0.7 0 0.3 0 C 0 0 0 0.1429 0 0.8571 D 0 0 0 0 0 1 E 0 0 0 0 0 1 F 0 0 0 0 0 0 P 2 = A B C D E F A 0 0 0.1555 0.0794 0.0667 0.6984 B 0 0 0 0.1000 0 0.9000 C 0 0 0 0 0 0.1429 D 0 0 0 0 0 0 E 0 0 0 0 0 0 F 0 0 0 0 0 0 P 3 = A B C D E F A 0 0 0 0.0222 0 0.2794 B 0 0 0 0 0 0.1000 C 0 0 0 0 0 0 D 0 0 0 0 0 0 E 0 0 0 0 0 0 F 0 0 0 0 0 0 P 4 = A B C D E F A 0 0 0 0 0 0.0222 B 0 0 0 0 0 0 C 0 0 0 0 0 0 D 0 0 0 0 0 0 E 0 0 0 0 0 0 F 0 0 0 0 0 0 （4）

3 基于n步转移概率矩阵的空间预测

在实际的应用中,可根据LBS用户的需要,以及相关地理背景知识,指定匿名集序列规则中包含某一空间的区域,为空间预测的目标区域（Target Area）。在对匿名集序列规则数据进行均一化处理后,目标区域对应齐次马尔科夫链中的目标状态（Target State）,通过对目标状态的分析,对所有LBS用户到达目标区域的概率进行空间预测。

3.1 概略预测

根据用户设定目标区域所对应的目标状态,n步转移概率矩阵可直接对所有LBS用户到达目标区域的概率进行概略预测。例如,设定图3中的状态 F 为目标状态,依据 P 1 - P 4 ,可得到从某一状态对应的空间区域,分别经过1-4步状态转移到达目标状态 F 对应目标区域的转移路径和概率,如表2所示。
Tab. 2 Simple predictions to arrive at target area F

表2 到达目标区域F的概略预测

类型 目标区域 步数 概略路径 概率
到达 F 1 C→F 0.2222
D→F 0.5556
E→F 0.2222
2 A→F 0.6984
B→F 0.89997
C→F 0.1429
3 A→F 0.2794
B→F 0.10003
4 A→F 0.0222
表2中1步转移路径只包括起点、终点,预测表达比较清晰。例如,C→F:0.2222,表示LBS用户如果在状态C对应空间区域提出匿名查询,将具有0.2222的概率在状态F对应空间区域的再次提出匿名查询。但是,对于步数n≥2时,转移路径就不能精确获知用户在匿名空间区域的具体转移过程。例如,A→F:0.2794,只能表示如果用户在状态A对应空间区域提出匿名查询,将具有0.2794的概率,经过3步状态转移到达状态F对应空间区域并提出匿名查询。但是,并不清楚具体经过哪2个状态及对应的空间区域,而这对于分析用户的行为模式,以提供个性化服务至关重要[15-17]。

3.2 精确预测

针对概略预测的缺点,本文提出精确预测的方法。其实现的基本原理是：由n步到达目标状态的概略路径的起点与n-1到达目标状态的精确路径的起点得到组合路径,并通过与1步转移概率矩阵的联合计算,最终得到所有n步到达目标状态的精确路径及预测概率。图4是实现精确预测n步到达目标状态对应空间区域的基本流程。基于图4中的流程,以式（4）的1-4步转移概率矩阵P(1)-P(4)为输入数据,对到达目标状态F的精确路径进行预测：
Fig. 4 Flowchart of the precise prediction to arrive at the target area

图4 精确预测到达目标状态的算法实现流程

（1）从 P 1 得到1步到达目标状态F的精确路径列表 P Exac_in 1 ,也即1步到达目标状态 F 的精确路径列表 P simp_in 1 ,而且 P Exac_in 1 = P simp_in 1 =([C→F],[D→F],[E→F])。
（2）从P(2)得到2步到达目标状态F的概略路径列表 P simp_in 2 =([A→F],[B→F],[C→F])。
（3）逐个将 P Exac_in 1 路径的起点与 P simp_in 2 路径的起点合并,得到相应组合路径。例如,路径[C→F]的起点与[A→F]路径的起点合并后得到组合路径[A→C],类别可以得到组合路径[A→C]、[A→D]、[A→E]、[B→C]、[B→D]、[B→E]、[C→C]、[C→D]、[C→E]。
（4）在 P 1 中检查存在的组合路径得到：[A→C]、[A→D]、[B→C]、[B→E]、[C→D]。
（5）将组合路径[A→C]的概率（0.5556）分别和 P Exac_in 1 中精确路径[C→F]的概率（0.8571）相乘,得到精确路径[A→C→F]的概率为0.4762,分别可以得到[A→D→F]的概率为0.2222、[B→C→F]的概率为0.59997、[B→E→F]的概率为0.3、[C→D→F]的概率为0.1429。因此, P Exac_in 2 =([A→C→F], [A→D→F], [B→E→F], [C→D→F])。
（6）以 P Exac_in 2 和从P(3)得到3步到达目标状态 F 的概略路径列表 P simp_in 3 =([A→F], [B→F])为参数,进行迭代运算得到, P Exac_in 3 =([A→B→C→F]),再以 P Exac_in 3 和 P simp_in 4 =([A→F])为参数,得到 P Exac_in 4 =[A→B→C→D→F]。
（7）得到精确预测2-4步到达目标状态 F 对应空间区域路径及概率信息如表3所示。鉴此结果,可更为准确了解LBS用户执行连续匿名查询的过程。例如,表3中A→B→C→F：0.1333,表示某一LBS用户如果参与了发生在状态 A 对应空间区域的匿名查询,将具有0.1333的概率沿着路径A→B→C→F到达状态F对应的空间区域,并提出匿名查询。
Tab. 3 Precise predictions to arrive at target area F

表3 到达目标区域F的精确预测

类型 目标区域 步数 精确路径 概率
到达 F 2 A→C→F 0.4762
A→D→F 0.2222
B→C→F 0.59997
B→E→F 0.3
C→D→F 0.1429
3 A→B→C→F 0.1333
A→B→E→F 0.0666
A→C→D→F 0.0794
B→C→D→F 0.10003
4 A→B→C→D→F 0.0222
精确预测n步到达目标状态对应空间区域算法实现的伪代码如下：
算法1：R:PreArriTS(L,TS)
输入：存储1-n步转移概率矩阵的链表L;目标状态TS。
输出：存储1-n步到达目标状态TS的精确转移过程链表R。
{ P 1 = L ∙ Get 1 ;
P simp_in 1 = P 1 ∙ GetArrive ( TS ) ;
P Exac_in 1 = P simp_in 1 ;
R ∙ add P Exac_in 1
PreArriTSRe L , TS , P Exac_in 1 , 1 , R ;
Return R;
}
算法2：
输入：存储1-n步转移概率矩阵的链表L;目标状态TS;当前精确路径列表 P Exac_in ;当前精确路径的步数s;存储1-n步到达目标状态TS的精确转移过程链表R。
输出：存储1-n步到达目标状态TS的精确转移过程链表R。
P ( s + 1 ) = L ∙ Get ( s + 1 ) ;
P simp_in ( s + 1 ) = P ( s + 1 ) ∙ GetArrive ( TS ) ;
For ( i = 1 ; i < = P simp_in ( s + 1 ) ∙ count ; i + + )
{ Or i 1 = P simp_in ( s + 1 ) ∙ Get ( i ) ∙ Origin ;
For ( j = 1 ; j < = P exac_in ∙ cou nt ; j + + )
{ Pro b 1 = P Exac_in ∙ Get ( j ) ∙ ProbV alue ;
Or i 2 = P Exac_in ∙ Get ( j ) ∙ Origin ;
If ( P 1 ∙ Exist ( Or i 1 , Or i 2 ) )
{ Pro b 2 = P 1 ∙ ProbValue ( Or i 1 , Or i 2 ) ;
P Exac_in ( s + 1 ) ∙ addProb Pro b 1 × Pro b 2 ;
Subs = P Exac_in ∙ Get ( j ) ∙ Sub ;
P Exac_in ( s + 1 ) ∙ addP a th Or i 1 , Subs ;
}
}
}
P Exac_in = P Exac_in ( s + 1 ) ;
R ∙ add P Exac_in ;
s + +;
If ( s < L ∙ count )
PreArriTSRe L , TS , P Exac_in , s , R ;
}
其中,算法1为程序实现的入口,第1-4行是初始化操作：从1步转移概率矩阵P(1)中获取1步到达目标状态的精确路径列表及概率。第5行调用执行递归运算的子程序PreArriTSRe,该程序在算法2中实现,其中,参数 R （存储1-n步到达目标状态 TS 的精确转移过程链表）以传地址指针的方式,在子程序PreArriTSRe中进行运算,最后运算的结果通过第6行返回。
算法2中的第1行从 L （存储1-n步转移概率矩阵的链表）中获取步数增加（s+1）的转移概率矩阵（P(s+1)）,第2行从P(s+1)中获取s+1步到达目标状态的概略路径列表及概率（ P simp_in ( s + 1 ) ）。第3-15行完成 P simp_in ( s + 1 ) 中路径与 P Exac_in （传递的参数）中路径的组合、在1步转移概率矩阵P(1)中的检查（第8行）,以及概率计算（第10行）等。第16-17行进行递归调用参数 P Exac_in 的赋值操作,第18-19行增加步数并进行检验其是否大于链表 L 中转移概率矩阵的个数,如果满足条件则在第20行回归调用程序 PreArriTSRe 。

4 实验设计与结果分析

实验硬件：Intel-2430M CPU,主频2.4 GH,内存2G的联想笔记本电脑。
实验数据：采用文献[18]-[19]开发的软件系统,从GPS轨迹数据模拟生成500个LBS用户连续查询的匿名集序列数据。
实验1：对比匿名集序列规则与贝叶斯网络模型构建的处理时间。
匿名集序列规则挖掘方法采用SPMF（http://www.philippe-fournier-viger.com/spmf/index.php）开源框架中Rule Growth算法。置信度阈值设置为：0.24。序列规则挖掘时间为99 ms,均一化处理时间为163 ms,n步转移概率矩阵的计算时间为5 ms,共计267 ms。匿名集序列规则及归一化前后的置信度数据,在地理背景图上显示（图5）。使用BN软件包中的BN Power Constructor模块（http://webdocs.cs.ualberta.ca/~jcheng/download.htm）构建匿名集序列数据的贝叶斯网络模型[20],其处理时间包括结构学习与参数学习2个过程,共计159 s(159 000 ms)。试验结果可看出：匿名集序列规则挖掘、均一化处理,以及n步转移概率矩阵构建的时间总和（267 ms）,远小于贝叶斯网络模型的处理时间（159 000 ms）。其原因：贝叶斯网络模型需要从高维稀疏矩阵数据训练建立模型[21],而序列规则挖掘方法直接分析匿名集序列数据,并采用Aprior特性进行剪枝运算的性能优化处理[10-13]。
Fig. 5 Map of anonymity sequential rules

图5 匿名集序列规则的地图表示

实验2：对比精确预测的概率与直接统计的真实概率,分析预测的精度。
结合相关的地理背景知识,本文设定 I 为目标区域。利用精确预测方法得到2步到达目标区域 I 的转移路径与概率为：A→E→I:1,B→E→I:1,C→E→I:1,D→E→I:0.333,F→E→I:0.5,H→E→I:0.5。预测结果如图6所示。精确预测的概率值与真实概率的对比如图7所示。
Fig. 6 Map of the precise prediction path to arrive at target area I

图6 精确预测到达目标区域I路径的地图表示

Fig. 7 Comparison between the real probability and the predicted probability

图7 精确预测概率与真实概率的对比

对比试验结果可以看出：精确预测概率与真实概率的整体分布基本接近,但存在突变点,即某些转移路径的预测概率与真实概率相差过大,例如,转移路径A→E→I,B→E→I,C→E→I。分析问题原因：表3中转移路径A→E→I,B→E→I,C→E→I涉及的匿名集序列规则A→E,B→E,C→E,E→I在归一化处理前后,其置信度数据存在较大波动。据此分析,造成突变点的原因可能为匿名集序列规则的归一化处理所致。
我们进一步通过实验验证：分别设定置信度阈值为0.2,0.22,0.24,0.26和0.28,挖掘匿名集序列规则、归一化置信度数据,最后将匿名集序列规则的精确预测概率与真实概率进行对比,如图8所示。对比试验结果可看出：随着置信度阈值的降低,精确预测概率更接近于真实概率。据此我们得出结论：通过设定匿名集序列规则挖掘时的置信度阈值,可对精确空间预测的精度,也即预测概率与真实概率的接近程度,进行灵活调整。
Fig. 8 Comparison between several predicted probability with different confidence thresholds and the real probability

图8 不同置信度阈值的精确预测概率与真实概率的对比

5 结论

时空K-匿名方法是近年来LBS隐私保护研究的一个主流方法,其在实现LBS位置隐私保护的同时,也为匿名查询请求数据的进一步分析利用提出了挑战。采用数据挖掘技术对匿名查询请求数据的分析,并以分析结果进行空间预测,是实现匿名查询请求数据可用性的一个重要方式。本文分析LBS连续查询中,采用空间网格划分的时空K-匿名方法生成的历史匿名集数据,提出了匿名集序列规则与转移概率矩阵,对匿名数据集中包含的特定空间区域进行概略到达预测、精确到达预测的方法。结果表明,该方法具有模型构建速度快,精确空间预测的精度也即预测概率与真实概率的接近程度,可通过设定匿名集序列规则挖掘时的置信度阈值进行灵活调整等优点。研究成果对于丰富时空数据挖掘,以及空间预测方法的研究具有一定价值。

The authors have declared that no competing interests exist.

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
[1]
Baldauf M, Dustdar S, Rosenberg F.A survey on context-aware systems[C]. In Proceedings of IJAHUC, 2007:263-277.

[2]
王璐,孟小峰.位置大数据隐私保护研究综述[J].软件学报,2014,25(4):693-712.

[3]
Duckham M, Kulik F.Location Privacy and Location-Aware Computing in Dynamic & Mobile GIS: Investigating Change in Space and Time[M]. Boca Raton: CRC Press, 2006:1-16.

[4]
Gruteser M, Grunwald D.Anonymous usage of location-based services through spatial and temporal cloaking[C]. In Proceedings of MobiSys, 2003.

[5]
Krumm J.A survey of computational location privacy[C]. In Proceedings of Personal and Ubiquitous Computing, 2009:391-399.

[6]
张海涛,黄慧慧,徐亮,等.隐私保护数据挖掘研究进展[J].计算机应用研究,2013,12(12):3529-3535.

[7]
Hu H, Xu J, Lee D L.PAM: An efficient and privacy-aware monitoring framework for continuously moving objects[C]. In Proceedings of IEEE Transaction on Knowledge and Data Engineering, 2010:404-419.

[8]
Chen J, Cheng R, Mokbel M F, et al.Scalable processing of snapshot and continuous nearest-neighbor queries over one-dimensional uncertain data[C]. In Proceedings of VLDB J, 2009:1219-1240.

[9]
Pan X, Meng X, Xu J.Distortion-based anonymity for continuous queries in location-based mobile services[C]. In Proceedings of GIS, 2009:256-265.

[10]
Fournier-Viger P, Nkambou R, Tseng V S.RuleGrowth: Mining sequential rules common to several sequences by pattern-growth[C]. In Proceedings of SAC, 2011:956-961.

[11]
Fournier-Viger P, Tseng V S.Mining top-K sequential rules[C]. In Proceedings of Hf-Based High-k Dielectrics, 2011:180-194.

[12]
Fournier-Viger P, Faghihi U, Nkambou R, et al.CMRules: Mining sequential rules common to several sequences[J]. Knowledge-based Systems, Elsevier, 2012,25(1):63-76.

[13]
Fournier-Viger P, Tseng V S.TNS: Mining top-K non-redundant sequential rules[C]. In Proceedings of 28th Symposium on Applied Computing, 2013:164-166.

[14]
刘次华. 随机过程(第四版)[M].武汉:华中科技大学出版社,2008:42-49.

[15]
陆锋,刘康,陈洁.大数据时代的人类移动性研究[J].地球信息科学学报,2014,16(5):665-672.

[16]
Kim W.Behavior-based mobility prediction for seamless handoffs in mobile wireless networks[C]. In Proceedings of Wireless Networks, 2011:645-658.

[17]
Giannotti F, Nanni M, Pedreschi D, et al.Mining mobility behavior from trajectory data[C]. In Proceedings of CSE(4), 2009:948-951.

[18]
张海涛,高莎莎,徐亮.空时K-匿名数据的关联规则挖掘研究[J].地理与地理信息科学,2012,11(6):13-16.

[19]
Gao S S.Research on association rules and sequential patterns mining of spatial-temporal K-anonymity dataset[D]. Nanjing: Nanjing University of Posts & Telecommunications, 2013.

[20]
Cheng J, Greiner R.Learning Bayesian belief network classifiers: Algorithms and system[C]. In Proceedings of Canadian Conference on AI, 2001:141-151.

[21]
张连文,郭海鹏.贝叶斯网引论[M].北京:科学出版社,2006:81-82.

Options
文章导航

/

〈 〉