随着科技的不断进步, 数据正快速地增长和累积.减少数据冗余、实现数据共享, 已成为大数据时代的首要任务.记录链接(record linkage)^[1]是指从一个或多个数据源中匹配出代表现实世界中同一实体的记录, 记录链接在金融、医疗、政府等领域具有广泛的应用前景.但是, 当记录信息涉及到个人隐私或敏感信息时, 我们必须要考虑记录信息的隐私保护问题.因此近年来, 研究隐私保护下的记录链接(PPRL).PPRL技术可以保证在记录链接的过程中, 只有最终匹配结果被各数据源间共享, 其他未匹配的记录信息均未被泄露.例如在分散的医疗体系中, 某人的医疗信息可能分布在多个医院, 找出同一个人在不同医院的诊断信息有利于更准确的分析病情, 但由于涉及到患者隐私, 各医院并不希望暴露患者的医疗信息.PPRL技术既可以找出某位患者在各医院的医疗信息, 又能够保证各医院其他患者的医疗信息不被泄露.因此, PPRL技术不仅具有理论研究价值, 而且有着重要和迫切的实际应用价值.

目前, 已有很多文献提出了PPRL的方法^[2-8], 其中大多数方法都只适用于两个数据源, 对于3个及以上的多方PPRL方法的研究还很少.这是因为想要找到一个可以合理度量多条记录相似度的方法并不容易.适用于两个数据源的相似度度量方法大多数并不适用于多数据源.然而, 现实中的很多应用进行记录链接的数据源往往不只两个.因此, 多方PPRL的研究具有重要的现实意义.随着数据量的不断增长和现实世界数据质量问题的存在(如拼写错误、顺序颠倒等), 多方PPRL方法的可扩展性和容错性成为研究的重点.目前, 大部分多方PPRL方法只适用于精确匹配^[9-11], 即:只有各记录完全一致才认为匹配成功, 并不能处理存在质量问题的数据(data with quality issues, 简称DQI), 制约了其实际应用.还有少部分非精确的近似匹配方法可以处理DQI, 但由于应用密码学保护技术导致时间代价较大, 不具有可扩展性.文献[2])提出了一种可扩展的基于“与”运算的多方PPRL近似方法(BasedAnd_PPRL, 简称BA_PPRL), 但在处理DQI类型的数据时, 该方法会丢失较多真实匹配的记录, 导致查全率过低.可见, 已有解决方法不能有效地处理DQI类型的数据.因此, 研究出一种时间代价较低又能有效处理DQI类型数据的多方PPRL近似方法, 是亟待解决的问题.

本文提出一种基于比率的结合布隆过滤(bloom filter)、动态阈值(dynamic threshold)、检查机制(check mechanism)、安全合计(secure summation)和改进的Dice相似度函数的多方近似PPRL方法(BasedRatio_PPRL, 简称BR_PPRL).BA_PPRL方法^[2]与本文方法相近, 并且具有较高的准确率和较低的时间代价, 但当处理存在质量问题的数据时, 该方法查全率过低, 导致其很难具有应用价值.本文提出的方法在保证准确率的前提下, 显著提升了查全率且时间代价较低, 更具有应用价值.

本文的贡献点是:

(1) 基于比率来标识记录间在某位置的相似度, 能够有效地提高方法的容错性;

(2) 基于动态阈值及检查机制来确定真正匹配的位置, 能够保证在提高查全率的同时, 查准率不受影响;

(3) 利用改进的Dice相似度函数, 能够有效计算带有质量问题的记录间的相似度;

(4) 通过实验证明了本文方法可以有效地处理DQI类型的数据, 即:保证查准率的同时, 具有更高的查全率和较小的时间代价.因此, 本文方法拥有更高的容错性和较好的可扩展性.

本文第1节简述与本文方法有关的相关工作.第2节说明本文方法用到的背景知识.第3节描述本文提出方法的流程及算法, 并对其隐私保护程度进行分析.第4节给出实验结果, 并对其加以分析.最后, 在第5节对本文进行总结, 并指出进一步的工作方向.

1 相关工作

目前, 对于多方PPRL解决方法的研究还处于起步阶段.国外有较少的相关方法被提出; 在国内, 还未见有相关方法.最早的多方PPRL方法^[9]是通过将各个数据源的记录编码, 然后传入另一方进行对比.但是, 这个方法只适用于精确匹配.2004年, 一种基于安全多方计算的精确匹配方法^[10]被提出.2008年, 文献[11]提出通过安全等价链接进行精确匹配的方法.文献[10, 11]应用的隐私保护方法时间代价较高.文献[12]提出一种基于k-匿名和博弈概念的近似匹配方法, 但只能应用于分类属性上.

文献[13]最早提出了利用Bloom Filter将记录属性值转换为0和1组成的位数组, 并对记录间做“与”运算, 如果运算结果的位数组与各记录的位数组均相同, 则匹配成功.该方法虽然时间代价较小, 但却只适用于精确匹配.为此, 文献[2]在该方法的基础上提出了与安全合计和Dice相似函数相结合的近似匹配方法.同样, 该方法时间代价较小, 且准确率较高.但当数据源中记录存在质量问题时, 该方法的查全率会降低, 导致其实际应用价值较低.本文提出的方法通过计算位数组的各对应位置bit 1所占的比率, 并利用动态阈值、检查机制和改进的Dice相似函数, 使得在处理存在质量问题的数据时, 匹配结果的查全率显著提高.

2 背景知识 2.1 布隆过滤

Bloom Filter^[14]是一种空间效率很高的随机数据结构, 它可以将集合转换为位数组.下面具体介绍Bloom Filter是如何用位数组表示集合的.初始状态时, Bloom Filter是一个包含m位的位数组, 每一位都置为0.为了表达S={x₁, x₂, …, x_n}这样n个元素的集合, Bloom Filter使用k个相互独立的哈希函数(hash function), 它们分别将集合中的每个元素映射到{1, …, m}的范围中.对任意一个元素x, 第i个哈希函数映射的位置h_i(x)就会被置为1(1≤i≤k).

2.2 多方安全Bloom Filter匹配

在判断多个位数组是否来自同一实体时, 为了保证隐私, 各个位数组应尽少暴露自身信息给其他参与方.因此在进行多方Bloom Filter匹配时, 每个位数组被均分成P(参与方个数)个部分{B₁, B₂, …, B_P}, B₁, B₂, …, B_P分别相应传到参与方P₁, P₂, …, P_P中.这样, 每个参与方只获知位数组中m/P个字符, 保证了数据的安全.

2.3 安全合计

安全合计是安全多方计算中的一种方法, 被广泛应用于各种PPRL方法中.它的基本思想是:各参与方将自己的数据加密后再进行合计, 得到合计结果后解密即为真实的合计结果.该过程各方除了获得最终的真实合计结果外, 对其他方的真实数据均一无所知.

2.4 Dice相似函数

在计算多个位数组之间相似度时, 可以利用基于集合的Dice相似度计算函数.假如计算B₁, B₂, …, B_P这P个位数组之间的相似度, 见公式(1) :

$Dice\_sim({B_1},...,{B_P}) = \frac{{P \times \left| {{B_1} \cap {B_2}... \cap {B_P}} \right|}}{{\sum\limits_{i = 1}^P {{B_i}} }}$

(1)

其中, |B_i|代表第i个位数组中1的个数.

3 多方BR_PPRL近似方法

本文提出的多方BR_PPRL近似方法由3个模块构成:数据准备及生成模块、记录近似匹配模块和相似度计算模块, 如图 1所示, 详见算法1.

算法1.多方BR_PPRL近似匹配算法.

输入:D_i:来自参与方P_i的数据源; i, j, z, 1≤i, j≤P, 1≤z≤m; T_D:动态阈值; T_A:全局阈值;

输出:匹配记录集合M.

1:  Blocking(D_i); //先对每个数据源进行分块处理

2:  B_i=genetateBloomfilters(D_i, A); //对每个数据源中的记录应用Bloom Filter

3:  divide(B_i)={B_{i, 1}, …, B_{i, j}, …, B_{i, P}}; //将每个0, 1字符串分为P个部分

4:  send B_{i, j} to P_j; //将字符串的第j部分传给参与方j

5:  R_{i, z}=generateRatios(B_{i, z}); //计算每个竖列的比率

6:  IF R_{i, z}≥T_D THEN:

7:      IF R_{i, z}=1 THEN:

8:          Y_{i, z}=R_{i, z};

9:      ELSE IF checkMecharism($S_{i,z}^'$)=Ture

10:          V_Rz=R_{i, z};

11:      ELSE Y_{i, z}=0;

12:  ELSE Y_{i, z}=0;

13:  R_a=secureSummation(Y_{i, z}, V_Rz);

14:  $Dice\_sim = \frac{{P \times {R_a}}}{{\sum\limits_{i = 1}^P {\sum\limits_{z = 1}^m {\left| {{B_{i,m}}} \right|} } }}$;

15:  IF Dice_sim≥T_A

16:      M={B₁, B₂, …, B_P} as a Match;

17:      RETURN M;

18:  ELSE

19:      {B₁, B₂, …, B_P} as a Non-match;

数据准备及生成模块的主要功能是统一各数据源之间参数、分块, 并利用Bloom Filter将数据源中各记录的公共属性值转换为由0, 1组成的位数组.转换得到的位数组在一定程度上代表了记录并保护了记录的隐私, 位数组将代表各记录在后续模块中进行匹配.

记录近似匹配模块的主要功能是判断来自各数据源的位数组间匹配成功的位置.首先, 计算位数组间各对应位置bit 1所占的比率; 然后, 利用动态阈值选出候选匹配成功位置; 最后, 通过检查机制得到真正匹配成功的位置.

相似度计算模块的主要功能是计算来自各数据源的位数组间的相似度, 进而判断这些位数组是否来自于同一实体.若相似度不小于全局阈值, 则匹配成功; 反之, 匹配失败.

3.1 数据准备及生成

在算法开始前, 需要先确定输入参数并保证各参与方参数一致, 表 1说明了本文方法用到的参数及其意义; 然后, 对各数据源D_i应用相同的分块方法, 减少候选匹配对的数量, 从而减少时间代价; 接着, 将各数据源D_i中的N_i条记录的属性A的值变为q-gram; 最后, Bloom Filter应用k个哈希函数将其映射成N_i个m长度的位数组(第1行、第2行).

为了保证位数组的安全, 利用多方安全Bloom Filter匹配技术, 将长度为m的位数组均分成P个片段(m/p), 并将第j个片段传给P_j(1≤j≤P), 参与方P_j收到P-1个来自其他参与方的第j个片段(第3行、第4行).

3.2 记录近似匹配

本文提出的多方BR_PPRL近似方法对位数组间对应的位置进行比率计算, 得到bit 1所占的比率, 然后, 利用动态阈值和检查机制判断匹配成功的位置.比率计算、动态阈值和检查机制均为该算法的关键环节, 由于相似度结果是依据匹配成功位置得出的, 因此, 全面而准确地找出匹配成功的位置, 对方法的性能具有关键性影响.尤其当数据存在质量问题时, 该方法的性能更优于已有方法.

3.2.1 比率计算

BA_PPRL^[2]是目前最优的多方近似方法, 在该方法中, 为了得到匹配成功的位置, 各位数组将对应位置字符做“与”运算, B_{1, z}∩ B_{2, z}∩ …∩ B_{P, z}表示P个位数组在位置z做“与”运算(1≤z≤m).只有各对应位置字符均为1时, “与”运算结果才为1, 代表该位置匹配成功S_z.然而, 当其中某条记录存在质量问题时, 可能使得一些原本为1的位置变为0, 进而导致一些真实应该匹配成功的位置被丢失, 最终造成真实匹配结果的丢失, 导致查全率过低.

为支持存在质量问题的数据的多方近似匹配, 本文的BR_PPRL方法通过计算各位数组对应位置bit 1所占比率R_z代替“与”运算(第5行), 即B_{1, z}, B_{2, z}, …, B_{P, z}代表P个位数组在位置z的值(1≤z≤m), O_{i, z}代表P个位数组在位置z值为1的个数(1≤i≤P), 因此, ${R_z} = \frac{{{O_{i,z}}}}{P}$比率可以更准确地代表各位数组在某个位置的相似度, 因此, 通过比率而不是“与”运算结果判断某位置是否匹配成功, 可以提高方法的容错率, 减少真实匹配结果的丢失, 提高查全率.

3.2.2 动态阈值

为了利用比率判断某位置是否匹配成功, 本文提出动态阈值T_D的概念, T_D用来筛选候选匹配位置.如果某位置比率为1, 则直接作为匹配成功位置S_z; 否则, 若大于等于T_D, 则作为候选匹配位置$S_z^＇$(第6行~第12行).在给出T_D前, 先计算当参与方个数为P、容错率为X时, 即, 允许每条记录发生错误的概率为X, 每竖列对应位置中a个位置出现错误的概率P_e, P_e见公式(2).

${P_e} = C_P^a{X^a}{(1 - X)^{P - a}}$

(2)

由二项分布定理得知:当a=PX时, P_e最大.a取整a'=[PX].由于每个竖列出现a'个错误的概率最大, 那么每个竖列最多允许a'个错误发生.所以, 动态阈值T_D见公式(3) 所示.

${T_D} = \frac{{P - a'}}{P}$

(3)

动态阈值由P和X决定, 当P一定时, X越大, T_D越小, 允许发生错误的位置越多; 反之, X越小, T_D越大, 允许发生错误的位置越少.当X=0时, T_D=1, 不允许任何错误发生, 等同于BA_PPRL方法.

3.2.3 检查机制

候选匹配位置$S_z^＇$代表该位置有可能是真实匹配, 但又存在质量问题的位置.为了保证准确率不受影响, 需要对候选匹配位置做进一步判断.本文提出一种检测机制, 可以测出某条记录是否是存在质量问题但又匹配成功的记录, 详见算法2.

算法2.检查机制算法.

输入:来自于P个参与方的位数组B₁, B₂, …, B_P; 候选匹配位置$S_z^＇$;

输出:True or False.

1:    $\sigma = \sqrt {PX(1 - X)} $; //计算σ

2:    $F' = getlocation0(S_z^＇)$; //找出候选位置中存在质量问题的记录

3:    $F = \left| {F'} \right|$; //集合F'的个数即存在质量问题记录的个数

4:    IF F < a'+3σ THEN:

5:        ${B_a} = getBF0(S_z^＇)$; //找出存在质量问题的记录

6:        B_b=getclosedBF1(F'); //找出与其最近的正常记录

7:        $Dice\_sim({B_a},{B_b}) = \frac{{2 \times \left| {{B_a} \cap {B_b}} \right|}}{{\left| {{B_a}} \right| + \left| {{B_b}} \right|}}$;

8:        IF Dice_sim > T_A THEN:

9:            RETURN True;

10:        ELSE

11:        RETURN False;

12:    ELSE

13:        RETURN False;

检查机制的总体思想:

1.利用切比雪夫定理判断存在质量问题的记录数是否在合理范围内(第1行~第4行), 即, 找出所有候选位置中存在质量问题的记录即位置为0所对应的记录:若存在质量问题记录的个数F < a'+3σ, 则继续检查; 否则, 检查不通过.其中, σ为公式(2) 的标准差, 见公式(4).

$\sigma = \sqrt {PX(1 - X)} $

(4)

由切比雪夫定理得到公式(5) :

$F < a' + 3\sigma $

(5)

由于$F < a' + 3\sigma $的概率为89%, 所以当存在质量问题记录的个数$F > a' + 3\sigma $时, 直接判断记录间不匹配;

2.通过上述检查的候选匹配位置继续判断存在质量问题的记录与距其最近的正常记录是否匹配成功(第5行~第11行).将位置为0的位数组与距离最近的位置为1的位数组传入一个绝对安全的第P+1方, 同样利用Dice相似度函数计算两者相似度, 若大于全局阈值则检测通过, S_Rz代表真实匹配但又存在质量问题的位置; 否则不通过.

3.3 相似度计算

传统的Dice相似度函数见公式(1).本文方法提出改进的Dice相似度函数, 见公式(6).

$Imp\_Dice\_sim({B_1}, \ldots ,{B_P}) = \frac{{P \times (\left| {{S_z}} \right| + {V_{{R_z}}})}}{{\sum\limits_{i = 1}^P {\left| {{B_i}} \right|} }}$

(6)

其中, B₁, B₂, …, B_P代表来自于P个参与方的P个位数组, |B_i|代表B_i中bit 1的个数, |S_z|代表比率为1的位置个数, ${{V_{{R_z}}}}$代表位置${{S_{{R_z}}}}$的比率值.

由此, 可以推导出公式(7) :

$Imp\_Dice\_sim = Dice\_sim + \frac{{P \times {V_{{R_z}}}}}{{\sum\limits_{i = 1}^P {\left| {{B_i}} \right|} }}$

(7)

● 当不存在位置${{S_{{R_z}}}}$时, Imp_Dice_sim=Dice_sim;

● 当存在位置${{S_{{R_z}}}}$时, Imp_Dice_sim在Dice_sim上加入了存在质量问题的真实匹配位置.

因此, 本文提出的方法对于存在质量问题但又真实匹配的记录依然可以计算出较高相似度, 显著减少了真实匹配记录的丢失.所以, 本文方法在处理带有质量问题的数据时, 显著提高了查全率.

应用多方Bloom Filter安全匹配技术的改进的Dice相似度函数见公式(8).

$Dice\_sim = \frac{{P \times \left( {\sum\limits_{j = 1}^P {\left| {{S_{j,z}}} \right|} + \sum\limits_{j = 1}^P {{V_{j,{R_z}}}} } \right)}}{{\sum\limits_{i = 1}^P {\sum\limits_{j = 1}^P {\left| {{B_{i,j}}} \right|} } }}$

(8)

其中, 加和运算均利用安全合计保证数据安全, 若相似度不小于阈值, 则匹配成功; 否则, 匹配失败(第13行~第19行).|B_{i, j}|代表第i个位数组片段j中bit 1的个数.

3.4 多方BR_PPRL近似算法示例

下面举个例子来说明上述过程.如图 2所示, 有五方参与本文方法.

首先, 从5个数据源中各提取出一条记录, 并用Bloom Filter将记录中属性A的值转换为5个位数组{B₁, B₂, B₃, B₄, B₅}; 接下来, 将5个位数组均分为5个片段, 并把相应片段传到对应参与方中, 然后计算各对应位置中bit 1所占的比率.当P=5, X=1/5时, 动态阈值为T_D=4/5.因此, 1作为匹配成功位置继续保留下来, 4/5不小于动态阈值, 作为候选匹配位置进入检查机制进行判断:首先找出带有质量问题的记录B₁, 个数小于a'+3σ.继续检查.由于B₁与距其最近且为1的B₂相似度为0.89, 大于全局阈值0.8, 所以4/5作为带有质量问题的匹配成功位置.3/5小于动态阈值则未匹配成功变为0.由公式(8) 可得, Dice相似度结果为0.89, 大于全局阈值T_A, 所以这5条记录匹配成功, 均来自同一实体.方法BA_PPRL计算得到的相似结果为0.74, 小于全局阈值T_A, 导致真实匹配记录的丢失.

$Dice\_sim = \frac{{P \times \left( {\sum\limits_{j = 1}^P {\left| {{S_{j,z}}} \right|} + \sum\limits_{j = 1}^P {{V_{j,{R_z}}}} } \right)}}{{\sum\limits_{i = 1}^P {\sum\limits_{j = 1}^P {\left| {{B_{i,j}}} \right|} } }} = \frac{{5 \times (1 + 1 + 1 + 1 + 4/5)}}{{4 + 5 + 6 + 6 + 6}} = 0.89.$

3.5 隐私保护分析

我们假设所有参与方都遵循Honest-But-Curious攻击方法, 即:参与方都尽力通过已获得的信息推测其他方的信息, 但不会串通、恶意攻击等.本文方法应用安全多方Bloom Filter匹配技术, 使得每个参与方只能看见其他方m/P bits的片段.因此, P越大, 则安全性越高.

在检查机制中由于在绝对安全的第P+1方进行匹配, 所以过程中并没有信息泄露.

4 实验与分析 4.1 准备工作

本文用Python(2.7.11版本)实现文中提出的方法.处理器:Intel(R)Core(TM) i5-4590;主频:3.3GHz, 8核; 内存: 8GB; 操作系统:Windows 7, 64位.

本文实验采用的数据集为北卡罗来纳州选民登记名单(North Carolina voter registration list, 简称NCVR), 该数据集中的记录都是公共可获得的真实个人信息.数据集可以从ftp://alt.ncsbe.gov/data/上下载.

对本文方法, 我们从运行时间(runtime)、查准率(precision)、查全率(recall)和F指数这4个方面进行评估^[15].运行时间用来评估本文方法的可扩展性, 查准率、查全率和F指数用来评估本文方法的匹配质量.查准率代表本文方法找出匹配成功的记录中, 真实匹配记录所占的比率, 查准率越高, 代表方法的结果越准确.查全率是指本文方法找出的真实匹配的记录占所有真实匹配记录的比率, 查全率越高, 代表方法找到的真实匹配记录越全. F指数则用来综合评估方法的结果.

本文分别以数据源大小、参与方个数、容错率和扰乱比例为自变量, 评估以上4个指标的变化情况.参与方个数的变化范围为^{[3, 5, 7, 10]}; 数据源大小是从NCVR中分别提取5 000, 10 000, 50 000, 100 000, 500 000和1 000 000条记录分给每个参与方, 并保证不同大小的数据源中均有一半的记录是各参与方共有的; 容错率变化范围为[1/5, 2/5, 3/5, 4/5, 1];扰乱比例(disturbed ratio, 简称DR)变化范围为[1/4, 1/2, 3/4, 1], 扰乱比例为占各数据源共有记录的比例.

本文方法的优势在于:处理存在质量问题的现实数据时, 比之前方法具有更高的查全率且; 在检查机制的保护下, 查准率也不会受到太大影响.因此, 为了评估不同程度质量问题对本文方法匹配结果的影响, 利用文献[16]中的工具, 可以生成不同程度质量问题的数据集.本文生成3个扰乱数据集, 扰乱程度分别为每条记录至多一个拼写错误(Mod-1)、两个拼写错误(Mod-2) 和3个拼写错误(Mod-3).拼写错误包括增加、删除和替换字符.

本文实验的参数设置设定m=1000, k=30, q=2, T_A=0.8.本文应用基于语音分块的探测法^[17]来提高方法的可扩展性.

4.2 实验结果与分析 4.2.1 可扩展性评估

首先评估本文方法的运行时间随数据源大小增加的变化情况.其中, 参与方个数P=5, 容错率X=1/5, 扰乱比例占共有记录中的1/2.图 3表示本文方法比BA_PPRL方法运行时间稍长, 但仍具有较好的可扩展性.这是因为本文提出的比率计算和检查机制导致运行时间变长.

下面评估本文方法运行时间随着参与方个数增加的变化情况.数据集大小均为|D_i|=1rjxb-28-9-2281, 容错率X=1/5, 扰乱比例占共有记录中的1/2.图 4表示随着参与方个数的增加, 运行时间变短.这是因为随着P的增加, l/P变小, 即, 分到每个参与方的片段变短, 所以运行时间变短.

4.2.2 方法性能评估

本节分别从查全率、查准率和F指数这3方面对方法BR_PPRL的性能进行评估, 并与方法BA_PPRL进行对比.数据集分别选取3个不同程度扰乱数据集Mod-1, Mod-2和Mod-3.

首先评估在Mod-1数据集中, 两种方法的3个评价指标随参与方个数增加的变化情况.其中, |D_i|=5000, 容错率X=1/5, 扰乱比例占共有记录中的1/2.如图 5所示, 两种方法的查全率均随P的增加而减小.这是因为当数据存在质量问题时, P越大, 丢失的真实匹配记录越多.BA_PPRL方法在处理存在质量问题的数据时, 查全率下降很快.当P=3时, 查全率最高, Recall=0.5;当P=10时, 查全率几乎为0;本文提出方法的查全率始终较高, 当P=10时, 查全率依然在0.5以上.两种方法的查准率均随P的增加而减小, 且两者的查准率较为相近.通过观察F指数的变化可以看出:在处理扰乱数据集时, 本文方法的性能明显优于方法BR_PPRL.

接下来评估在不同程度扰乱数据集上, 本文提出方法的3个评价指标随参与方个数增加的变化情况.其中, |D_i|=5000, 容错率X=1/5, 扰乱比例为共有记录中的1/2.如图 6所示:随着扰乱程度的增加, 本文方法的查全率、查准率和F指数都在下降.这是由于扰乱程度增加后, 一些真实匹配的记录会更容易被丢失.

然后评估在Mod-1数据集中, 两种方法的3个评价指标随容错率增加的变化情况.其中, P=5, |D_i|=5000, 扰乱比例为共有记录中的1/2.如图 7所示:在方法BA_PPRL中, 3个评估指标并不受容错率变化的影响, 因此一直保持恒定值, 查全率为0.2, 查准率为0.9, F指数为0.33.本文方法随着容错率的增大, 查全率不断增大, 查准率不断下降.这是因为容错率越大, 动态阈值越小, 找到的匹配对数越多, 但相应的准确率会下降.在检查机制的保护下, 容错率为1时, 查准率依然在0.4以上.通过F指数的变化可以看出, 本文方法能够更好地处理存在质量问题的数据集.

接下来评估在不同程度扰乱数据集上, 本文提出方法的3个评价指标随容错率增加的变化情况.其中, P=5, |D_i|=5000, 扰乱比例为共有记录中的1/2.如图 8所示:随着扰乱程度的增加, 本文方法的查全率、查准率和F指数都在下降.同样是由于扰乱程度增加后, 一些真实匹配的记录会更容易被丢失.

接下来评估在精确数据集上, 两种方法的查准率随容错率增加的变化情况.其中, P=5, |D_i|=5000, DR=0.如图 9所示, 方法BA_PPRL的查准率并不会随容错率的变化而变化.本文方法的查准率随容错率的增大而变小, 但当X=1时, 本文方法的查准率依然在0.7以上.由于数据集为精确的, 所以方法BA_PPRL能准确地找全各参与方间的共有记录.随着容错率的增加, 本文方法在找全各参与方间共有记录的同时还会误找一些记录认为匹配成功.因此, 通过对比方法BA_PPRL与本文方法在精确数据集中查准率随容错率的变化情况, 可以推断出本文方法的失误率.

继续评估在Mod-1数据集中, 两种方法的3个评价指标随扰乱比例增加的变化情况.其中P=5, |D_i|=5000, X=1/5.如图 10所示, 3个评估指标均随扰乱比例的增加而下降.方法BA_PPRL的查全率大幅度下降, 当DR≥3/4, 其查全率几乎为0.本文方法的查全率即使在DR=1时, 仍然在0.4以上.F指数可以说明本文方法在处理存在质量问题数据集时的有效性.

接下来评估在不同程度扰乱数据集上, 本文提出方法的3个评价指标随扰乱比例增加的变化情况.其中, P=5, |D_i|=5000, X=1/5.如图 11所示:随着扰乱比例的增加, 本文方法的查全率、查准率和F指数都在下降.但Mod-3的F指数依然保持较好效果.

接下来评估在不同程度扰乱数据集上, 本文提出方法的3个评价指标随扰乱比例增加的变化情况.其中, P=5, |D_i|=5000, X=1/5.如图 11所示:随着扰乱比例的增加, 本文方法的查全率、查准率和F指数都在下降.但Mod-3的F指数依然保持较好效果.

4.2.3 实验总结

通过实验可以得知:本文提出的方法在处理带有质量问题的数据时具有较高的查全率; 且在有效的检查机制的保护下, 查准率并未受到太大影响.在运行时间上, 本文方法比BA_PPRL方法要长, 但对比一些应用密码学保护技术的方法, 时间代价仍然较低, 具有较好的可扩展性.因此, 本文提出的方法虽然牺牲了少部分时间代价, 但在保证准确率的前提下, 显著提高了查全率.

5 结束语

多方PPRL方法的研究是实现大数据共享的必然要求, 具有广泛的应用价值.但目前的方法在处理带有质量问题的现实数据时, 存在查全率低和时间代价大的特点.因此, 本文提出了一种结合布隆过滤、安全合计、动态阈值、检查机制和改进的Dice相似度函数的多方近似PPRL方法.动态阈值和检查机制可以有效地选出存在质量问题的真实匹配的位置, 并利用改进的Dice相似度函数计算相似度.本文方法可以有效减少由于数据质量问题带来的真实匹配记录的丢失, 进而提高查全率.检查机制则可以保证查准率依然较高.本文方法具有良好的扩展性, 并且在保证准确率的前提下显著提高了查全率, 具有广泛而深远的现实意义.在未来的工作中, 将进一步研究更优的多方隐私分块方法来提高本文方法的可扩展性.

致谢 在此, 我们向对本文的工作给予支持和建议的同行, 尤其是对东北大学计算机科学技术系申德荣教授、聂铁铮副教授及各位给予帮助的同学表示感谢.