本发明涉及数据隐私保护技术领域，具体涉及一种轨迹数据发布中针对个人偏好位置的隐私保护方法。
背景技术：
随着基于位置的服务的快速发展，出现了许多移动定位设备，如汽车导航、嵌入全球定位系统的手机、平板电脑、位置传感器等，导致了各种基于位置服务应用的出现。这些应用允许用户将位置以及查询内容发送给位置服务器，位置服务器将对应的查询结果返回给用户。这些应用被划分为两类：一类是基于用户提供实时位置在线应用；另一类是由位置服务提供商收集和分析移动数据或将轨迹数据发送给第三方的离线应用。这些应用为人们的生活带来了极大的便利，然而轨迹数据中往往包含了关系到用户个人偏好的隐私数据。
对于离线应用，轨迹数据发布之后，主要是用来进行数据挖掘与分析，可以用来优化交通网络与交通管理策略，分析用户的行为来支持商业决策等。在离线应用中，如果这类数据不经任何处理直接发布出来，攻击者能够根据用户部分位置的时空关联推测出用户的其他位置信息，导致用户隐私的泄露。因此，数据发布者发布数据时，一方面要确保发布的匿名数据不泄露个人的隐私信息；另一方面要保证发布的匿名数据具有高可用性，使得研究者仍然能够根据发布的匿名数据进行较准确的数据分析。所以，如何在满足用户隐私需求的同时提高匿名数据的可用性成为亟待解决的问题。
目前，在离线轨迹数据发布场景中，很多方法被提出来用于进行隐私保护。现有的轨迹数据发布的隐私保护方法有三类：1.基于聚类的方法，在关系数据库中使用k-匿名概念进行匿名。2.准标识符的方法，是假设攻击者知道一条轨迹的部分背景知识，来识别轨迹上剩余的移动点或敏感属性。3.差分隐私的方法，保证移动对象在差分隐私定义下被保护。然而，现有的这些方法大多考虑的是对整条轨迹数据进行保护，但是由于轨迹上包含的所有位置数据并不一定都涉及用户的个人偏好信息，因此不需要对整条轨迹上的位置都进行隐私保护处理，而只需要对涉及个人偏好信息的位置进行相应的隐私保护处理。对整条轨迹数据进行隐私保护的方法不仅会影响轨迹数据的可用性，而且存在算法效率低下的问题。
技术实现要素：
本发明所要解决的是现有离线轨迹数据发布场景中所使用的隐私保护方法会影响轨迹数据的可用性和效率低下的问题，提供一种轨迹数据发布中针对个人偏好位置的隐私保护方法。
本发明是通过以下技术方案实现的：
轨迹数据发布中针对个人偏好位置的隐私保护方法，其具体包括步骤如下：
步骤1、对原始轨迹数据集中的所有轨迹，分别计算每两条轨迹的综合距离；
r(ti，tj)＝(1-α)×dist(ti，tj) α×[1-rel(ti，tj)]
其中，r(ti，tj)表示轨迹ti和tj的综合距离；dist(ti，tj)表示轨迹ti和tj的距离，disto(ti，tj)表示轨迹ti和tj的方向距离，dists(ti，tj)表示轨迹ti和tj的速度距离，distl(ti，tj)表示轨迹ti和tj的位置距离，
步骤2、基于原始轨迹数据集中每两条轨迹的综合距离，并利用k均值聚类算法对原始轨迹数据集中所有轨迹进行聚类，得到若干个轨迹簇；其中k为设定值；
步骤3、对于尚未自己定义个人偏好位置的用户即目标用户，先基于步骤2的聚类结果确定该目标用户所对应的轨迹所在的轨迹簇，再从该轨迹簇中找出与该目标用户所对应的轨迹综合距离最接近的n条轨迹，后将这n条轨迹所对应的用户的个人偏好位置作为拟推荐给目标用户的个人偏好位置；其中n为设定值；
步骤4、对步骤3所得到拟推荐给目标用户的个人偏好位置进行隐私保护后，推送给目标用户。
上述步骤1中，轨迹ti和tj的方向距离disto(ti，tj)为：
其中，pt表示轨迹ti和tj的公共时间戳，ol(ti，tj)表示轨迹ti和tj的公共时间戳的数目，stij表示轨迹ti和tj的公共时间段的开始时间，eij表示轨迹ti和tj的公共时间段的结束时间，
上述步骤1中，轨迹ti和tj的速度距离dists(ti，tj)为：
其中，pt表示轨迹ti和tj的公共时间戳，ol(ti，tj)表示轨迹ti和tj的公共时间戳的数目，stij表示轨迹ti和tj的公共时间段的开始时间，eij表示轨迹ti和tj的公共时间段的结束时间，
上述步骤1中，轨迹ti和tj的位置距离distl(ti，tj)为：
其中，pt表示轨迹ti和tj的公共时间戳，ol(ti，tj)表示轨迹ti和tj的公共时间戳的数目，stij表示轨迹ti和tj的公共时间段的开始时间，eij表示轨迹ti和tj的公共时间段的结束时间，δr表示轨迹ti和tj上的所有相同的两相邻时间戳位置组成的两个三角形面积的总和。
上述步骤2中，轨迹簇的个数为
上述步骤4的具体过程如下：
步骤4.1、根据攻击者掌控的关于原始轨迹数据集的位置记录计算攻击者拥有的知识集；
步骤4.2、对于知识集中的每一条知识q，在找出原始轨迹数据集中含有当前知识q的轨迹并放入轨迹列表中，并将该轨迹列表中所有轨迹所对应用户的个人偏好位置放入原始位置列表中；
步骤4.3、对于原始位置列表中的每一个个人偏好位置iocj，计算攻击者由知识q推测出当前个人偏好位置locj的概率p(q→locj)：
其中，n(locj，q，t)表示轨迹列表中包含当前个人偏好位置locj的轨迹的数目，|n(q，t)|表示轨迹列表中所有轨迹的数目；
步骤4.4、比较攻击者由知识q推测出当前个人偏好位置locj的概率p(q→locj)与用户认为的能够忍受的隐私被泄露的概率pr：如果p(q→locj)小于等于pr，则对当前个人偏好位置locj不做处理；如果p(q→locj)大于pr，则将当前个人偏好位置locj放入到不安全位置列表中；
步骤4.5、对于不安全位置列表中的每一个个人偏好位置locj′，如果轨迹列表中包含当前个人偏好位置locj′的轨迹只有一条的时候，则从该条轨迹上删除当前个人偏好位置locj′，否则，从轨迹列表中随机选择n(t，q→locj′)条包含当前个人偏好位置locj′的轨迹，并从这些轨迹上删除当前个人偏好位置locj′；其中n(t，q→locj)为设定值。
上述步骤4.5中，随机选择轨迹的条数n(t，q→locj′)为：
n(t，q→locj′)＝s(q∪locj′，t)-s(q，t)*pr
其中，s(q∪locj′，t)表示原始轨迹数据集中同时包含当前知识q和当前个人偏好位置locj′的轨迹的数目，s(q，t)表示原始轨迹数据集中包含当前知识q的轨迹的数目，pr表示用户认为的能够忍受的隐私被泄露的概率。
与现有技术相比，针对轨迹数据上的个人偏好位置能够泄露用户的一些隐私信息的问题，本发明面向离线轨迹数据发布中的隐私保护策略，先对原始轨迹数据集中的每条轨迹，找出轨迹上涉及用户个人偏好的位置，再对这些位置进行相应的隐私保护处理，最后再发布轨迹数据。本发明既能进一步提高发布的轨迹数据的可用性，又能保证用户的隐私信息不被泄露。
附图说明
图1为轨迹数据发布中针对个人偏好位置的隐私保护方法的流程图。
图2为轨迹相似性聚类的结构示意图。
图3为个人偏好位置的隐私保护的流程图。
具体实施方式
为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实例，对本发明进一步详细说明。
本发明先对原始轨迹数据集中的所有轨迹，根据轨迹之间的距离和pt值以及对应的用户之间的好友关系程度，对轨迹进行聚类处理。再根据轨迹聚类的结果，找出尚未自己定义个人偏好位置的用户(目标用户)所在的簇，找出与目标用户最相似的前n个用户，将他们的个人偏好位置推荐给目标用户。最后对轨迹数据集中的所有个人偏好位置进行隐私保护处理。
一种轨迹数据发布中针对个人偏好位置的隐私保护方法，如图1所示，其具体包括步骤如下：
步骤1：将所有用户的轨迹形成原始轨迹数据集t，在原始数据集中，每个轨迹对应一个用户。对原始轨迹数据集t中的所有用户对应的轨迹，分别计算每2个用户所对应轨迹的综合距离。
由于轨迹之间的相关性能够反应用户之间的社交关系，而两个用户如果是好友，好友的偏好会影响用户偏好的选择，因此本发明在对轨迹数据进行聚类的时候，我们不仅考虑了轨迹之间的距离，也考虑了轨迹对应的用户之间的好友关系程度，并允许用户自定义他们的个人偏好位置类型。
步骤1.1：轨迹之间距离计算
计算轨迹之间的距离时，我们考虑了轨迹间的方向距离、速度距离、位置距离。对于原始轨迹数据集中的每一对轨迹都需要计算他们之间的距离，以及其轨迹对应的用户之间的好友关系程度。
①计算两轨迹之间的方向距离disto(ti，tj)：
其中，
②计算两轨迹之间的速度距离dists(ti，tj)：
其中，
③计算两轨迹之间的位置距离distl(ti，tj)：
其中，δr表示2条轨迹上每2个相同的相邻时间戳所组成的两个三角形面积的总和。如轨迹ti的2个相邻时间戳ti-5和ti-6，与轨迹tj的2个连续时间戳tj-5和tj-6这4个时间戳，其所组成的三角形为δti-5ti-6tj-5和δtj-5tj-6ti-6。
④计算两轨迹之间的距离dist(ti，tj)：
其中
步骤1.2：用户间好友关系程度计算
在计算每对轨迹之间的距离时，计算其对应的用户之间的好友关系程度rel(ti，tj)：
其中，f(tn)表示轨迹tn的用户的好友集合。
步骤1.3：基于用户友好关系的轨迹综合距离计算
两轨迹之间的综合距离r(ti，tj)：
r(ti，tj)＝(1-α)×dist(ti，tj) α×[1-rel(ti，tj)]
其中，α表示两用户成为好友关系程度所占的权重。
步骤2：基于轨迹之间距离和用户间好友关系程度计算原始轨迹数据集中每两条轨迹的综合距离，并利用k均值聚类算法(k-means)对原始轨迹数据集的轨迹进行聚类，得到
步骤3：对于尚未自己定义个人偏好位置的用户即目标用户，先基于步骤2的聚类结果确定该目标用户所对应的轨迹所在的轨迹簇，再从该轨迹簇中找出与该目标用户所对应的轨迹综合距离最接近的n条轨迹，后将这n条轨迹所对应的用户的个人偏好位置作为拟推荐给目标用户的个人偏好位置。如图2所示。
步骤3.1：对于没有定义个人偏好位置的用户即目标用户，根据上一步骤的轨迹聚类结果，找出该目标用户的轨迹ts′所在的轨迹簇。
步骤3.2：利用综合距离计算公式计算ts′与它所在的轨迹簇中的其他所有轨迹之间的综合距离；
步骤3.3：对步骤3.2所得的综合距离进行升序排序，选出n个综合距离最小值所对应的轨迹。由于n条最小距离轨迹对应n个用户，因此将这n个用户存放入一个列表。
步骤3.4：根据步骤3.3，找出列表中所有用户定义的个人偏好位置类型，并存入一个列表，再将该列表推荐给该目标用户。
步骤4：对步骤3所得到拟推荐给目标用户的个人偏好位置进行隐私保护后，推送给目标用户。
由于轨迹数据中往往包含了涉及用户个人偏好的隐私数据，如果数据发布者对数据不做任何处理直接发布，会造成用户个人偏好信息的泄露。攻击者可能掌握用户局部的轨迹信息，如果仅是删除或隐藏原始轨迹集中的身份信息，攻击者仍然能够以一定的概率推断出用户的其他涉及个人偏好的位置信息。
表1
根据表1发布的轨迹数据集，如果一个攻击者知道marry的部分轨迹数据{a1，a2}，根据发布的轨迹数据集，攻击者能够知道marry的轨迹是t1，t2，t3，t4中的一条，所以攻击者能够推测涉及marry的个人偏好位置b1的概率是
隐私保护的目标是：即使在攻击者知道部分真实位置记录的情况下，也无法以高于pr的概率推测出攻击者尚未掌握的轨迹上的其他个人偏好位置信息，使最终发布的轨迹数据具有较高的数据利用率，同时能够保护用户个人的隐私信息不被泄露。其中pr为用户认为的能够忍受的隐私被泄露的概率。
隐私保护的原理是：首先，生成攻击者拥有的知识集q，q∈q。接着，把q→locj(攻击者拥有的知识→个人偏好位置记录)记为l，根据l的概率进行分类，如果p(l)＜pr，则l是安全的；否则l是不安全的(对应的q也是不安全的)。最后，对不安全的l进行相应的匿名处理。如图3所示。
假设攻击者v掌控的关于t的位置记录为av＝{a1，a2，a3}，根据攻击者拥有的知识的定义，我们可以为t中的每条轨迹生成相应的知识q，如表2。
表2
1)轨迹的定义：
ti＝{i，(t1，x1，y1)，(t2，x2，y2)，...，(tm，xm，ym)}，其中i表示轨迹的唯一标识，(ti，xi，yi)表示在时间ti时所在的位置。
2)轨迹记录的定义：
轨迹记录是由n个位置信息按照时间顺序组成的长度为n的一条记录，ti＝{i，(x1，y1)，(x2，y2)，...，(xm，ym)}表示一条轨迹记录。
3)攻击者拥有的知识的定义：
对于一条轨迹记录ti＝{i，(x1，y1)，(x2，y2)，...，(xm，ym)}的知识为t′i＝{i，(x1，y1)，(x2，y2)，...，(xm，ym)}，k＜＝m，
隐私保护详细的实现步骤如下：
步骤4.1、对轨迹数据集t中的所有轨迹ti，根据av计算出攻击者拥有的知识集q，其中
步骤4.2、对知识集q中的每一个q，在t中找出包含q的轨迹并放入列表n(q，t)中，并将n(q，t)中所有轨迹的个人偏好位置放入location列表中。对location中的每一个位置locj，在n(q，t)中找出包含该位置的轨迹的数目n(locj，q，t)。
步骤4.3、对每一个locj，根据公式计算出攻击者由q推测出个人偏好位置locj的概率p(q→locj)：
其中，n(locj，q，t)表示轨迹列表中包含当前个人偏好位置locj的轨迹的数目，|n(q，t)|表示轨迹列表中所有轨迹的数目。
步骤4.4、比较p(q→locj)与pr的大小：如果p(q→locj)大于pr，那么称由q推测locj是不安全的，将locj放入列表location′，并转至步骤4.5；否则，由q推测locj是安全的，对个人偏好位置locj不做处理。
步骤4.5、对location′中每一个位置locj′，如果n(q，t)中包含locj的轨迹数只有一条的时候，则直接从该轨迹上删除locj′；否则，我们需要根据公式计算需要删除的不安全的locj′的轨迹数n(t，q→locj′)，从包含locj′的轨迹集中随机选择轨迹，对其上的locj′进行删除，使得攻击者由q推测出locj′的概率降低到pr。需要删除的locj的轨迹数目n(t，q→locj′)：
n(t，q→locj′)＝s(q∪locj′，t)-s(q，t)*pr
其中，s(q∪locj′，t)表示原始轨迹数据集中同时包含当前知识q和当前个人偏好位置locj′的轨迹的数目，s(q，t)表示原始轨迹数据集中包含当前知识q的轨迹的数目，pr表示用户认为的能够忍受的隐私被泄露的概率。
需要说明的是，尽管以上本发明所述的实施例是说明性的，但这并非是对本发明的限制，因此本发明并不局限于上述具体实施方式中。在不脱离本发明原理的情况下，凡是本领域技术人员在本发明的启示下获得的其它实施方式，均视为在本发明的保护之内。
1.轨迹数据发布中针对个人偏好位置的隐私保护方法，其特征是，其具体包括步骤如下：
步骤1、对原始轨迹数据集中的所有轨迹，分别计算每两条轨迹的综合距离；
r(ti，tj)＝(1-α)×dist(ti，tj) α×[1-rel(ti，tj)]
其中，r(ti，tj)表示轨迹ti和tj的综合距离；dist(ti，tj)表示轨迹ti和tj的距离，disto(ti，tj)表示轨迹ti和tj的方向距离，dists(ti，tj)表示轨迹ti和tj的速度距离，distl(ti，tj)表示轨迹ti和tj的位置距离，
步骤2、基于原始轨迹数据集中每两条轨迹的综合距离，并利用k均值聚类算法对原始轨迹数据集中所有轨迹进行聚类，得到若干个轨迹簇；其中k为设定值；
步骤3、对于尚未自己定义个人偏好位置的用户即目标用户，先基于步骤2的聚类结果确定该目标用户所对应的轨迹所在的轨迹簇，再从该轨迹簇中找出与该目标用户所对应的轨迹综合距离最接近的n条轨迹，后将这n条轨迹所对应的用户的个人偏好位置作为拟推荐给目标用户的个人偏好位置；其中n为设定值；
步骤4、对步骤3所得到拟推荐给目标用户的个人偏好位置进行隐私保护后，推送给目标用户。
2.根据权利要求1所述的轨迹数据发布中针对个人偏好位置的隐私保护方法，其特征是，步骤1中，轨迹ti和tj的方向距离disto(ti，tj)为：
其中，pt表示轨迹ti和tj的公共时间戳，ol(ti，tj)表示轨迹ti和tj的公共时间戳的数目，stij表示轨迹ti和tj的公共时间段的开始时间，eij表示轨迹ti和tj的公共时间段的结束时间，
3.根据权利要求1所述的轨迹数据发布中针对个人偏好位置的隐私保护方法，步骤1中，轨迹ti和tj的速度距离dists(ti，tj)为：
其中，pt表示轨迹ti和tj的公共时间戳，ol(ti，tj)表示轨迹ti和tj的公共时间戳的数目，stij表示轨迹ti和tj的公共时间段的开始时间，eij表示轨迹ti和tj的公共时间段的结束时间，
4.根据权利要求1所述的轨迹数据发布中针对个人偏好位置的隐私保护方法，步骤1中，轨迹ti和tj的位置距离distl(ti，tj)为：
其中，pt表示轨迹ti和tj的公共时间戳，ol(ti，tj)表示轨迹ti和tj的公共时间戳的数目，stij表示轨迹ti和tj的公共时间段的开始时间，eij表示轨迹ti和tj的公共时间段的结束时间，δr表示轨迹ti和tj上的所有相同的两相邻时间戳位置组成的两个三角形面积的总和。
5.根据权利要求1所述的轨迹数据发布中针对个人偏好位置的隐私保护方法，步骤2中，轨迹簇的个数为
6.根据权利要求1所述的轨迹数据发布中针对个人偏好位置的隐私保护方法，步骤4的具体过程如下：
步骤4.1、根据攻击者掌控的关于原始轨迹数据集的位置记录计算攻击者拥有的知识集；
步骤4.2、对于知识集中的每一条知识q，在找出原始轨迹数据集中含有当前知识q的轨迹并放入轨迹列表中，并将该轨迹列表中所有轨迹所对应用户的个人偏好位置放入原始位置列表中；
步骤4.3、对于原始位置列表中的每一个个人偏好位置locj，计算攻击者由知识q推测出当前个人偏好位置locj的概率p(q→locj)：
其中，n(locj，q，t)表示轨迹列表中包含当前个人偏好位置locj的轨迹的数目，|n(q，t)|表示轨迹列表中所有轨迹的数目；
步骤4.4、比较攻击者由知识q推测出当前个人偏好位置locj的概率p(q→locj)与用户认为的能够忍受的隐私被泄露的概率pr：如果p(q→locj)小于等于pr，则对当前个人偏好位置locj不做处理；如果p(q→locj)大于pr，则将当前个人偏好位置locj放入到不安全位置列表中；
步骤4.5、对于不安全位置列表中的每一个个人偏好位置locj′，如果轨迹列表中包含当前个人偏好位置locj′的轨迹只有一条的时候，则从该条轨迹上删除当前个人偏好位置locj′，否则，从轨迹列表中随机选择n(t，q→locj′)条包含当前个人偏好位置locj′的轨迹，并从这些轨迹上删除当前个人偏好位置locj′；其中n(t，q→locj)为设定值。
7.根据权利要求6所述的轨迹数据发布中针对个人偏好位置的隐私保护方法，步骤4.5中，随机选择轨迹的条数n(t，q→locj′)为：
n(t，q→locj′)＝s(q∪locj′，t)-s(q，t)*pr
其中，s(q∪locj′，t)表示原始轨迹数据集中同时包含当前知识q和当前个人偏好位置locj′的轨迹的数目，s(q，t)表示原始轨迹数据集中包含当前知识q的轨迹的数目，pr表示用户认为的能够忍受的隐私被泄露的概率。
技术总结