本发明公开了一种基于近似语义查询的K支配隐私保护方法，首先，给定数据并从中获得包含真实位置的矩形区域中的位置数据集，通过MCA算法获取数据集中的聚类中心点，采用基于最大最小距离的多中心数据处理算法，结合由MCA算法聚类生成的数据点集，选择保证它们之间的距离最远的位置点并生成了一组经过处理的候选集。其次，通过计算不同名称的位置信息之间的距离，获得候选集中任意两个位置之间的语义相似度，并结合哑元的方法选择语义相似度最小的k‑1位置作为虚拟结果集。实验结果表明，该方法可以保证位置的物理分散性和语义多样性，并提高虚拟生成的效率。同时，实现了隐私保护安全与查询服务质量之间的平衡。
1.一种基于近似语义查询的K支配隐私保护方法，其特征在于包括以下步骤：步骤一、获取包含真实位置的矩形区域中的位置数据集，采用MCA算法计算正方形区域中位置地理坐标的聚类中心，得到若干个聚类中心，这些聚类中心被选为虚拟候选集，首先将样本对象作为第一聚类中心，然后选择离第一聚类中心最远的样本作为第二聚类中心，然后确定其他的聚类中心，直到没有新的聚类中心，确定所有聚类中心后，将包含m个样本的聚类样本集作为虚拟位置候选集，根据算法1，选择l1作为第一聚类中心,后选择l5作为第二聚类中心，再确定第三聚类中心l9，经过聚类计算，得到三个聚类中心，生成虚拟位置候选集；
1)给定γ的数值同时保证γ的取值范围处在0＜γ＜1区间范围内；
4)对于Sn中剩余对象的每个li，其到Z1和Z2的距离是Di1和Di2；假设D12是Z1和Z2之间的距离，若Di＝max{min(Di1,Di2)}且其中的i∈(1...n)且Di>γ·D12，则取li为第三个聚类中心Z3；
5)以此类推，得到所有符合条件的v个聚类中心，当最大最小距离小于γ·D12时,寻找聚类中心的计算结束；
6)假设v代表计算得到的聚类中心个数，判断符合下面哪种情况:(1)如果v≥m，则算法结束；
(2)如果v＜m,则重新选择γ的值,然后重新执行步骤1；
通过最大最小距离的多中心聚类方法，选择若干位置后，再经过哑元方法处理后产生一个候选的数据集，其中哑元方法处理的具体过程如下：步骤1：提出了一种考虑位置地名的语义信息特征的哑元选择方法，平衡了隐私保护和查询质量之间的矛盾；
步骤2：采用基于最大最小距离法的多中心聚类算法生成哑元数据集，保证了哑元的物理分散性；
步骤3：计算地理地名信息之间的语义相似度，选择语义相似度最小的位置地名作为哑元，保证了哑元的语义多样性；
所提出的哑元生成方法通过以下两种算法来实现:首先，通过算法1进行聚类计算生成哑元数据集S1；其次，通过算法2，计算候选集S1中位置的语义相似度来产生虚拟集S2；
步骤二、计算地理位置信息之间的距离后，计算得到候选集合中任意两个位置之间的语义相似度，选择k‑1个语义相似度最小的地理位置作为虚拟位置，其中语义相似度的计算和获取虚拟位置结果集的具体步骤如下：
1)依次匹配地名信息的每个字符，忽略匹配值相同的前缀字符，然后，得到两个新的字符串A和B；
2)假设字符串A包含i个字符，它表示为A＝a1a2a3Lai；字符串B包含j个字符，表示为B＝b1b2b3Lbi；
3)构造一个i+1列j+1行的动态规划矩阵，从D[i,j]得到的最后一个元素是ed(A,B)；
4)如果j＝0，返回i，然后退出；如果i＝0，返回j，然后退出；
5)第一行初始化为(0,1,l,i)；第一列初始化为(0,1,l,j)；
如果ai＝bi，则D[i,j]＝D[i‑1,j‑1]；
若ai≠bi，则D[i,j]＝1+min{D[i‑1,j‑1],D[i‑1,j],D[i,j‑1]}；
7)重复步骤6，直到获得矩阵中的所有值，最终保证距离为D[i,j]；
8)通过D[i,j]计算相似度匹配指数S(A,B)，即语义相似度；
9)选择语义相似度最小的k‑1个位置，生成虚拟结果集S2。
2.根据权利要求1所述的一种基于近似语义查询的K支配隐私保护方法，其特征在于：提出了一种对数据进行处理的MCA方法，来实现获取聚类中心点集的目的。
3.根据权利要求1所述的一种基于近似语义查询的K支配隐私保护方法，其特征在于：采用基于最大最小距离法的多中心聚类算法生成候选虚拟模型集，保证虚拟模型的物理分散性。
4.根据权利要求1所述的一种基于近似语义查询的K支配隐私保护方法，其特征在于：所述语义相似度的处理上，选择语义相似度最小的地理位置作为虚拟地名，保证了虚拟地名的语义多样性。
5.根据权利要求4所述的一种基于近似语义查询的K支配隐私保护方法，其特征在于：所述近似语义查询过程中候选集的处理选择上提出了一种哑元的处理方法，能够很好的削减候选集的选择上的平均执行时间。
一种基于近似语义查询的K支配隐私保护方法
技术领域
[0001] 本发明涉及数据的查询上的隐私保护处理的领域，具体是一种基于近似语义查询的K支配隐私保护方法。
背景技术
[0002] 主要创新点研究的背景意义
[0003] 随着移动定位技术和无线通信技术的发展，市场上大量的移动设备具备了GPS精确定位的能力，使得基于位置的服务(LBS)发展迅速。然而，当LBS为社会提供便利和巨大利益的同时，其敏感信息泄露问题也越来越受到人们的关注。因为用户的位置在不同的位置服务提供商之间共享，不可信的第三方可以通过分析和比较这些位置信息轻易地窃取用户的隐私。例如，通过捕捉最近用户的踪迹，对手可以分析一些信息，如家庭住址、工作场所和健康状况等。
[0004] 因此，有必要保证用户位置隐私的安全目前，为了防止隐私信息的泄露，现有提出的许多不同的方法主要包括有模糊方法、加密方法和基于策略的方法。空间匿名方法通常需要完全可信的第三方的帮助(TTP)。当需要位置查询服务时，移动用户首先向TTP发送查询请求，TTP生成包含用户位置的K支配区域，然后发送给LBS服务器进行查询。在这种方法中，如果K支配区域的面积过大，不仅会消耗更多的时间，而且会降低查询结果的准确性。同时，TTP容易成为系统的瓶颈。然而，在基于虚拟位置的隐私保护中，不需要TTP和匿名区域，虚拟位置由移动客户端生成。因此，它可以很好地弥补空间匿名方法的上述缺点。
发明内容
[0005] 针对现有技术的不足，本发明的目的是提供一种基于近似语义查询的K支配隐私保护方法，在传统的计算中结合K支配的技术和语义相似性的相关技术提高对查询的隐私保护程度，此外该算法还能够进一步的提高查询的效率。
[0006] 本发明解决其技术问题所采用的技术方案是：一种基于近似语义查询的K支配隐私保护方法，该方法主要包含如下的步骤：
[0007] 1.首先，给定数据并从中获得包含真实位置的矩形区域中的位置数据集，通过MCA中心聚类的方法计算并产生多个聚类中心，从而构成候选数据集，接着采用基于最大最小距离的多中心数据处理方法来选择了一些位置,保证它们之间的距离最远，并生成了一组经过处理的假的数据点；
[0008] 2.其次，通过计算不同名称的位置信息之间的距离，获得候选集中任意两个位置之间的语义相似度，并选择语义相似度最小的k‑1位置作为虚拟数据点。
[0009] 进一步，采用MCA算法，能够实现在移动客户端生成多个聚类中心。因为这些位置彼此相距最远，假的数据点可以从它们中产生数据集。
[0010] 进一步，所述语义相似度的计算，通过对候选集合的位置信息进行语义相似度的计算，并选择具有最小语义相似度的k‑1个位置作为虚拟位置并将k‑1个虚拟点信息和真实位置发送到LBS服务器进行查询，同时结合提出的哑元生成方法来生成虚拟集合，其中哑元数据集通过算法1中的聚类计算来生成。
[0011] 本发明的有益效果是：本发明通过采用K支配结合语义相似度的算法实现对用户位置信息查询的进一步保护,这样既减少查询时的时间开销问题，还能够进一步的保障用户的查询隐私问题。
附图说明
[0012] 图1是本发明一种基于近似语义查询的K支配隐私保护方法的摘要附图。
[0013] 图2是本发明给出的三种方法随着K值增加的时间开销对比图。
[0014] 图3是本发明给出的一种MCA算法的例证图。
[0015] 图4是本发明给出的本发明和MaxMinDistDS的运行效率的对比图。
[0016] 图5是本发明给出的本发明和SimpMaxMinDistDS的运行效率的对比图。
具体实施方式
[0017] 下面将结合本发明中的附图，对本发明实施例中的技术方案进行清除、完整地描述，显然，所描述的实例仅仅是本发明的一部分实施例子，而不是全部的实施例。此外应理解，在阅读本发明之后，本领域技术人员可以对本发明进行各种修改或改动，这些等价形式同样落在申请所附权利要求书所限定的范围。
[0018] 本发明公开了一种基于近似语义查询的K支配隐私保护方法，具体操作过程包括：
[0019] 步骤①：使用MCA算法计算正方形区域中位置地理坐标的聚类中心，得到若干个聚类中心，这些聚类中心被选为虚拟候选集。MCA算法是一种基于启发式的聚类算法，它根据欧氏距离将尽可能远的对象作为聚类中心。首先将样本对象作为第一聚类中心，然后选择离第一聚类中心最远的样本作为第二聚类中心。然后确定其他的聚类中心，直到没有新的聚类中心。确定所有聚类中心后，将包含个样本的m个聚类样本集作为虚拟位置候选集。结果如图3所示的位置。根据算法1，选择l1作为第一聚类中心,后选择l5作为第二聚类中心，再确定第三聚类中心l9。经过聚类计算，得到三个聚类中心，生成虚拟位置候选集。
[0020] 当确定聚类中心时，实际位置被用作初始聚类中心1，如果选择它作为第六个聚类中心，则必须满足这些条件:
[0021] (1)Di＞γ·D12其中i∈(1,...,n)；
[0022] (2)Di＝max{min(Di1,Di2)}且i∈(1,...,n),D12＝|Z2‑Z1|；
[0023] (3)γ是算法中的测试参数,其取值范围为：0.5＜γ＜1。
[0024] MCA步骤算法如下：
[0025] 算法1:MCA计算并产生多个聚类中心，并生成候选集。
[0026] 输入:位置数据集Sn和需求参数m。
[0027] 输出:生成虚拟位置数据集S1。
[0028] 1.给定γ的数值同时保证的取值范围处在0＜γ＜1区间范围内。
[0029] 2.将真实位置lre作为第一聚类中心Z1。
[0030] 3.找到离Z1最远的位置，作为第二聚类中心Z2。
[0031] 4.对于Sn中剩余对象的每个li，其到Z1和Z2的距离是Di1和Di2。假设D12是Z1和Z2之间的距离，若Di＝max{min(Di1,Di2)}且其中的i∈(1...n)且Di>γ·D12，则取为第三个聚类中心Z3。
[0032] 5.以此类推，得到所有符合条件的v个聚类中心。当最大最小距离小于γ·D12时,寻找聚类中心的计算结束。
[0033] 6.假设v代表计算得到的聚类中心个数，判断符合下面哪种情况:
[0034] (1)如果v≥m，则算法结束；
[0035] (2)如果v＜m,则重新选择的值,然后重新执行步骤1。
[0036] 7.生成候选集合S1。
[0037] 步骤②：计算伪候选集的位置信息的语义相似度。首先，根据位置信息的特点，剔除掉信息中的相同前缀。然后，通过计算距离计算剩余字符串中的语义相似度，提高了计算的效率和准确性。比如“哈尔滨第二中学”“哈尔滨第一中学”就是两串中文地名。“哈尔滨”对两个地名串的语义相似度计算没有任何意义，也影响了计算结果的准确性。因此，“哈尔滨”在计算中不再作为前缀。
[0038] D[i,j]是动态规划距离矩阵，每次编辑操作的代价在0和1之间。并且可以根据需要设置不同的值。在本文中，该值设置为0或1。如果ai＝bi，替换成本为0。否则，所有开销设置为1。在下面的矩阵中，D是动态规划矩阵，它表示字符串A＝“第二中学”和字符串B＝“第一中学”之间的距离。
[0039]
[0040] 两个字符串之间的距离通过计算获得，即D[i,j]＝D[4,4]＝2。利用下面的公式计算字符串之间的相似匹配指数，即语义相似度，语义相似度是0.5。
[0041] 其中|A|和|B|分别表示两个字符串的长度，字符串S的最大长度用于计算语义相似度。最后，根据公式Arg min(S(li,lj))，获得包括真实位置的具有最小语义相似度的k个位置。
[0042] 语义相似性算法如下：
[0043] 算法2:计算语义相似度,获取虚拟位置结果集。
[0044] 相关输入步骤描述:
[0045] 输入:位置候选集S1和语义多样性的参数阈值l。
[0046] 输出:位置结果集S2。
[0047] 1.依次匹配地名信息的每个字符，忽略匹配值相同的前缀字符。然后，得到两个新的字符串A和B。
[0048] 2.假设字符串A包含i个字符，它表示为A＝a1a2a3Lai；字符串B包含j个字符，表示为B＝b1b2b3Lbi。
[0049] 3.构造一个i+1列j+1行的动态规划矩阵。从D[i,j]得到的最后一个元素是ed(A,B)。
[0050] 4.如果j＝0，返回i，然后退出；如果i＝0，返回j，然后退出。
[0051] 5.第一行初始化为(0,1,l,i)；第一列初始化为(0,1,l,j)。
[0052] 6.给矩阵中的每个元素赋值:
[0053] 如果ai＝bi，则D[i,j]＝D[i‑1,j‑1]；
[0054] 若ai≠bi，则D[i,j]＝1+min{D[i‑1,j‑1],D[i‑1,j],D[i,j‑1]}。
[0055] 7.重复步骤6，直到获得矩阵中的所有值，最终保证距离为D[i,j]。
[0056] 8.通过D[i,j]计算相似度匹配指数S(A,B)，即语义相似度。
[0057] 9.选择语义相似度最小的k‑1个位置，生成虚拟结果集S2。
[0058] 最后，通过实验验证了该方法的有效性。在考虑语义相似性的哑元位置选择方法中，分别比较了MaxMinDistDS、SimpMaxMinDistDS和提出的方法的哑元位置平均执行时间。三种方法的虚拟位置的平均执行时间如图2所示。在图4中，在图5中，分别比较了MaxMinDistDS、SimpMaxMinDistDS和所提出的方法生成虚拟对象的效率对比。如图2所示，随着k的增加，MaxMinDistDS算法比所提出的方法花费更多的时间。如图5所示，当k<5时，SimpMaxMinDistDS算法的平均执行时间略大于提出的方法，当k≥5时，SimpMaxMinDistDS算法的平均执行时间远大于提出的方法。从图5可以看出，随着k的增加，所提出的方法的效率越来越优于其他两种算法。
[0059] 理论和实验结果表明，我们的算法能够保证位置的物理分散性和语义多样性，有效地保护用户的位置隐私，并减少了生成哑元的时间,有效的提高了查询的效率。
[0060] 尽管本发明的实施方案已公开如上,但其并不仅仅限于说明书和实施方式中所列运用,它完全可以被适用于各种适合本发明的领域,对于熟悉本领域的人员而言,可容易地实现另外的修改,因此在不背离权利要求及等同范围所限定的一般概念下,本发明并不限于特定的细节和这里示出与描述的图例。
