英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
算法1 寻找一个有缺失值记录的k –NNs：
4.1.2. 计算k –NNs的值
我们为每条有缺失值记录的k –NNs生成一个权重向量。权重向量中的每个元素都是根据给定记录和与其对应的k –NNs之间的比较权重来分配的。给定一个数据集R上的记录，它的k-NNs Ku = {rk1, rk2，hellip;rkk}在R中对应的权重向量wu计算如下:
wu = [Wrho; (rho; (ru , rk1 )), Wrho; (rho; (ru , rk2 )), . . . ,
Wrho; (rho; (ru , rkk ))] (19)
Wrho; (rho;(·, ·)) 是 用例18中的算法计算的比较权重值。而且，权重向量被规范化为单位向量：
其中 是wu的二次方，计算如下：
4.1.3 处理记录对中的缺失值
为了将一对记录分类为m匹配或非m匹配，分类器需要作为对这对的输入一个相似向量。相似向量中的每个元素表示记录中两个对应的标识字段值之间的相似性度量。然而，当其中任何一个值丢失时，我们使用记录的k –NNs与缺失值进行相似性度量。相似度测度Fi(ri, si)对记录r和s的第i个识别域的相似性度量，当其中任一种识别字段有缺失值时，计算如下:
其中表示给出的输入的相似值测度ri有一个缺失值，它的计算如下：
其中 是在记录r的k –NNs中的ith识别字段，而是k –NNs的相关权重向量。
相似地，表示给出的相似值测度si有一个缺失值，计算如下：
其中，是i的定义域中k –NNs记录S的k值，是k –NNs的相关权重向量。
为了说明这一点，假设我们需要计算记录r和s的ith识别字段ri和si(如ri = SMITH和si = SMYTH)之间的相似性度量。我们可以使用适当的相似性度量来度量记录中第i个字段之间的相似性。为了便于说明，我们使用二元语法和Dice系数的组合。使用二元语法和Dice系数的组合可以达到较高的准确率，并可以对其他字符串相似度测量进行分析。使用二元语法,ri和si被分为一组两个相邻的字母,先用空格填充两边的二元字符串的第一个和最后一个，(也就是：ri和si被填充为 {_S, SM, MI, IT, TH, H_} 和 {_S, SM, MY, YT, TH, H_}，很有代表性 )。在ri和si二元式中，有6个值，其中4个是相同的。ri与si之间的Dice系数为:
Dice系数取值范围在0到1之间，较高的数值表示具有较高的相似度。我们仍然假设，ri = SMITH，但是si的值丢失了。在这个例子中，我们有三个SMY的值和两个SMYTH的值，它们是在记录s的3-NNs中识别字段的对应值，以及它们相应的权重向量。首先，我们需要为三个不同的值（，以及）生成三个相应的二元组合。我们可以分别看出，在SMITH和SMY的二元集合中有6个和4个成员，其中2个相同。然后，利用相同的相似度指标(即Dice系数)，我们可以将ri与si之间的相似度分别用SMY，两个SMYTH，以及相应的权重进行计算，结果如下:
可以看出，使用公式(25)和(26)计算的相似度值之间的差值是相当小的，这表明了提出的估算相似性度量的方法是可信的。
4.2有缺失值的隐私保护记录链接
隐私保护记录链接(PPRL)要求两个数据集中的个人信息的字段必须由其相应的所有者加密:首先，两个所有者在密码或传递短语上进行约定，并且同意，以达到加密的目的；然后使用加密软件对这些字段进行加密；最后，加密的字段用作记录链接的加密标识字段。
4.2.1 在有缺失值的情况下保护隐私
为了解决隐私保护记录链中缺失值的问题，我们建议采用Bloom filter方法来构建在[16]中提出的PPRL。我们之所以在存在缺失值的情况下采用这种方法来保护隐私记录链接而不是其他方法，有这些原因：第一，Bloom filter方法允许将两个记录中对应的标识字段的两个值之间的相似性度量值在两个值被加密后进行计算，这在概率记录链接中是必需的。第二，它提高了其他隐私保护协议[16]的质量，比如瑞士匿名链接代码[41]，该代码基于一些标识字段的语音代码实现标识符。第三，它表现出健壮，发展良好，适合大规模的记录链接的特性。最后，也是最重要的，Bloom filter方法可以很容易地应用于有缺失值的k-NNs记录和k-NNs的权向量。
PPRL[16]的Bloom filter方法使用一个三方协议，其中链接由一个(受信任的)第三方(即连接单元)在一个HBC模型中完成[2]。这两个数据集所有者加密他们的数据记录，并将加密数据安全地传输到连接单元。HBC模型假定三方都正确地遵循了协议，同时对他们是否能够从任何接收到的数据中找到尽可能多的信息感到好奇[3]。Bloom filter方法[16]可以阻止任何字典攻击，只要第三方链接单元不与任何一个数据集所有者串通。尽管仍有一些其他类型的潜在攻击(例如，频率攻击)，但最初的Bloom filter方法中增加了它的安全性[42]。对于每个有缺失值的记录，我们需要对记录中k-NNs中对应的标识字段的值以及它们的权重向量进行加密。我们提出了一种方法，将这些值加密到一个Bloom filter，以及相应的NN的权重。为了实现这一点，而不是简单地在Bloom filter中设置这个值，该值对应于该值的双字母组合的散列输出，它被设置为对应的NN的权重。当多个双克集合的散列输出被映射到Bloom filter中的相同位时，位被设置为所有相应权重的总和。
在之前的例子中，我们在记录r中有ri = SMITH，而si的值在记录中丢失。我们也有三个值SMY和两个相应的值的史密斯第i个3-NNs标识字段的记录,连同他们的权向量wmacr;=(0.35,0.33,0.32)。我们现在需要将这三个值的双克映射到两个不同的Bloom filer:一个用于SMITH，另一个用于SMY和两个SMYTH。然后，我们可以计算两个Bloom filers之间的Dice系数，它将ri = SMITH和si之间的相似性度量归为缺失值。因为我们现在有真实的数字，而不是在Bloom filers用于SMY和两个SMYTH的二进制数，在公式（15）中原始的Dice系数公式需要被变形如下：
其中，两个Bloom filer被当做向量对待，bull;表示点积，和(bull;)对应向量中每个值的和。可以看出，对于两个具有二元值的Bloom filter，原始的Dice系数公式(如Eq.(15))是一个特殊情况，适用于调整的Dice系数公式(如Eq.(27))。
在Bloom filer长度l设置为与之前完全相同时，表2中的二元语法, ri = SMITH和si之间的Dice系数的计算与缺失值处理是在隐私保护方式下完成的，如下:
其中，Bloom filter B(sim;)计算SMY, SMYTHs,连同相应3-NNs的权向量wmacr;,如最后一列的表2所示。再一次，我们分析了在公式(17)和(28)中使用Dice系数计算的相似性度量。我们可以看出，这两种方法之间的差别也相当小。这表明，提出的处理缺失值的方法可以在使用Bloom filter协议的隐私预服务记录链接的上下文中，这种方法是有效的。
4.2.2 计算复杂度
在这一节中，我们分析了在存在缺失值的情况下，我们提出的隐私保护记录链接的不同阶段的计算复杂性，而我们的方法从每一个数据集R和S中的内部阻塞过程开始。假设R和S中的记录数为nR和nS，其缺失值对应的数量为mR和mS。在下一个阶段中，我们的方法搜索每个记录的k-NNs，并在同一块中寻找缺失值。两个数据集,R和S,这个搜索过程的计算复杂度是O((mR mS) times; nkA times; t ),其中，nkA表示每个块中记录的平均数量，而t是记录向量的维数。对于下一个归算过程，相应的计算复杂度将是O((mR mS) times; k times; l)，其中k对应k- nn, l是Bloom filter的长度。对于下面的阻塞过程，它需要一个复杂度为O((nR nS) times; qB times; p)哈希操作，一个通信的复杂度为O((nR nS) times; l)，一位比较的复杂度为O(nR times; nS times; l2 )。其中qB是每个记录字段中n-gram的平均数量，而p是用于将n-gram映 射成一个Bloom filter的哈希函数的计数。对于最后的匹配阶段，将会有另一个复杂度为O(nB times; (nRL nSL) times; qL times; p)散列操作，通信花费复杂度为O(nB times; (nRL nSL) times; l)，位比较复杂度为O(nB times; nRM times; nSM times; l2 )，其中nB是指阻塞后的块数，nRL和nSL表示从R和S中每个区块的平均记录数，qL是每个记录字段中n-gram的平均数，用于连接，而nRM和nSM分别对应于R和S各区块的最大记录数。
5.实验评估
在这一节中，我们介绍了我们提出的方法的实验结果。我们已经用5个现有的算法在不存在(即PRL和BF)和存在(即FRIL-0, FRIL-100和FLE)的情况下分析我们的方法：标准概率记录链接(PRL)方法[6]，Bloom Filter (BF)方法[15,16]，在细粒度记录集成和链接(FRIL)工具FRIL-0和FRIL-100[43]中可用的两种方法，以及在[8]中提出的全链接扩展(FLE)技术。我们用MATLAB R2014b对一台有3.6 ghz Intel Core i7 CPU和16 gb DDR3 RAM运行Windows 7操作系统的机器进行了所有的实验。我们评估的目的是表明我们的方法优于现有的三种技术(即FRIL-0, FRIL-100，和FLE)，以在缺失值的情况下记录链接，而另外两个现有的方法(PRL和BF)被用作标准记录链接和隐私保护记录链接的基线，而没有缺失值。
5.1数据集
对于算法PRL和BF，在数据集中都没有缺失值进行评估。对于其他三种算法，FRIL-0、FRIL-100和FLE，以及我们提出的方法，在数据集中有一定百分比的缺失值。我们已经生成并使用了基于GeCo[44,45]的一系列合成数据集。从选择合成数据集到真正的数据集有几个好处: 首先，可以通过计算成本估算来设置数据集大小。其次，我们可以在数据集中定义记录字段。例如，对于我们的实验评估，我们选择了六个字段(也就是，名字，姓氏，邮编，电话，总机，和城市)的链接。这些在实际的数据集中经常可用。记录连锁结果的基本事实是已知的，为基准测试提供质量评估。最后，数据集中缺失值的百分比可以被控制，这样的基准测试可以在不同的层次进行。每对合成数据集由两个单独的数据集组成，R和S，以及两个对应的数据集R和S有一定比例的缺失值。表3显示了数据集R和S的特征，包括大小。（也就是记录的数量），前六个字段用作标识字段，用于六个标识字段的相似性度量，使用的阻塞和内部阻塞方案。在数据集里还有一个额外的第7个ID字段，用于标记匹配的记录。为了简洁起见，前六个字段的名称由它们的第一个字母缩写。在数据集R和S中，有20%的记录是相同的(即在两个数据集中有相同id的记录)。为了模拟记录中各种类型的错误(例如印刷错误)，以反映典型关联数据集的质量。每一对数据集R和S都是从相同的数据集R和S中生成的，它们分别在R和S中有一定百分比的记录，在前六个字段中有一个缺失值。为了概括合成数据集的特点，生成了3对合成数据集R和S，以及3对R和S的缺失值，它们有10%、20%和25%的缺失值记录。我们使用了两个相似的度量方法(即Dice系数 (DC)和字符串等式(SE))来计算每个前六个字段对应的值之间的相似性度量，如表3所示。两个相似度指标都可以有效地计算[1]。例如，在表3中，DC(GN)表示在字段名中使用了Dice系数，而DC(P, C)表示在字段Postcode和City的连接上使用了Dice系数。PRL和BF分别是标准记录链接和隐私保护记录链接的两种算法。我们分别在3对数据集R和S上运行它们，以对标准记录链接的执行标准和每对数据集上的隐私保护记录链接执行标准。FRIL-0和FRIL-100是现有的两种算法，用于记录与缺失值的链接: FRIL-0假设每个缺失值与另一个数据集匹配记录中对应字段的值完全不同(也就是说，相似向量中相关字段的相似性度量为0)。相比之下，FRIL-100假设每个缺失值与另一个数据集匹配记录中的对应字段的值相同(即相似向量中对应字段的相似性度量为1)。这是在[8]中提出的三种算法中的一种，用于记录与缺失值之间的记录链接，该算法实现了三种算法的最佳性能。对于有缺失值的记录，第一次将与缺失值相关的字段重新分配给其他字段，而没有缺失值，其中权重的重新分配是基于其余字段的相对比例; 然后，它将零权重赋给那些缺少值的字段。我们已经运行了FRIL-0、FRIL-100以及与每一对数据集R和S中缺失值的记录链接，以确定与缺失值的记录链接的性能。他们的性能已经与我们的算法s的性能进行了对比，以保证隐私保护记录与缺失值之间的联系。
5.3评估
对于PRL, FRIL-0, FRIL-100和FLE算法，数据集中没有任何
全文共8157字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[11109]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
