隐私保护中的本地泛化和桶化技术

沙特国王大学学报用于个性化隐私保护李伯玉，何坤华中科技大学计算机科学与技术学院，武汉，中国阿提奇莱因福奥文章历史记录：2022年11月1日收到2022年11月17日修订2022年12月14日接受2022年12月28日在线提供保留字：隐私保护数据发布局部泛化局部桶化A B S T R A C T匿名化技术在隐私保护数据发布中得到了广泛的研究和应用。在大多数以前的方法中，微数据表由三类属性组成，即显式标识符，准标识符（QI）和敏感属性。一般来说，个人可能对不同属性的敏感性有不同的看法。因此，存在另一种类型的属性，其包含QI值和敏感值，称为半敏感属性。在本文中，我们提出了一种新的匿名化技术，称为本地泛化和桶化，以防止身份泄露和保护每个半敏感属性和敏感属性上的敏感值。其基本原理是使用局部泛化和局部桶化将元组划分为局部等价组，并将敏感值分别划分为局部桶。局部泛化和局部桶化保护是独立的，因此它们可以通过适当的算法实现，而不会削弱其他保护。此外，每个半敏感属性和敏感属性的局部桶化保护也是独立的。因此，局部桶化可以根据匿名化的实际需求，在不同的属性下遵循不同的原则。我们进行了大量的实验来说明所提出的方法的有效性。©2022作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍随着人类社会进入大数据时代，企业和政府收集了各种个人信息，如收入调查、医疗信息和人口普查。这些大量的个人数据，也称为微数据，用于数据挖掘和机器学习，有助于企业创造商业价值和政府制定政策。然而，微数据总是包含私人信息，如果微数据被公开而没有任何伪装，则导致个人的秘密可能被公开（Raju等人，2022; Safi等人， 2022年）。许多匿名化技术，如泛化（Sweeney，2002）和桶化（Xiao和Tao，2006），都是支持匿名化的。*通讯作者。电子邮件地址：brooklet60@hust.edu.cn（K. He）。沙特国王大学负责同行审查制作和主办：Elsevier为保护隐私的数据发布做准备。在这些方法中，微数据表中的属性被分为三类：（1）显式标识符，它可以唯一或主要标识记录所有者，必须从发布表中删除;（2）准标识符（QI），它可以用来重新识别记录所有者，当一起使用时;和（3）敏感属性，它包含个人的机密信息泛化将QI属性上的值转化为一般形式，并且广义值相同的元组构成等价群。因此，同一等价组中的记录是不可区分的。而桶化将元组划分为桶，打破了QI属性和敏感属性之间的关系。因此，每个记录对应于桶内的不同敏感值1.1. 动机以前的方法总是假设一个属性只包括QI值或敏感值。事实上，不同的人可能会将不同的数据值视为对同一属性敏感。因此，属性可以包含QI值和敏感值两者，敏感值被认为是半敏感的。例如，一家医院发布了一些病人的诊断记录，如图所示。 1（b），https://doi.org/10.1016/j.jksuci.2022.12.0081319-1578/©2022作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.comB. Li和K. 他沙特国王大学学报394Fig. 1. 一个匿名化微数据表的例子。使研究人员能够研究各种疾病的特征。在微数据表中，除了ID之外的每个属性都有一个标志，该标志标记元组是否将她/他的值视为敏感（例如，ID为1002的元组不关心她的年龄值是否已知其他人，但ID为1007的人想保密）。因此，年龄和邮政编码属性在微数据表中是半敏感的，因为它们包含QI值和敏感值。假设对手具有如图1（b）所示的背景知识，并且获得图1（b）的微数据表。知道马克以前去过医院，并通过他的性别和邮政编码值进行匹配，对手推断：（1）他的记录在微数据表中的ID为1004;以及（2）他的年龄24岁，得的是肺炎。 防止这种隐私披露的目标已经导致了许多匿名技术的发展（参见调查（Fung等人，2010年））。以前的泛化或分桶化是匿名化整个属性而不是特定值，因此只能将半敏感属性视为QI属性。图1（b）的一般化版本和分桶版本分别在图1（c）和1（d）虽然泛化有效地防止了身份泄露，但它总是遭受严重的信息丢失，如 Aggarwal （ 2005 ） ， Li and Li （ 2009 ） ， Kifer and Gehrke（2006）所提出的。几乎所有的值都是不可逆地泛化的，这阻碍了接收者对数据信息的分析。例如，图1（c）（c）阻止对手识别记录所有者，但为接收者保留了较差的信息效用。分桶表虽然保留了良好的信息效用，但它只保护敏感属性上的机密值，而不关心个性化的隐私需求。当攻击者具有足够的背景知识时，半敏感属性上的敏感值往往会暴露出来例如，攻击者仍然可以通过匹配图1中的QI值来获取Mark的ID和年龄。 1（d）.针对个性化隐私信息的保护问题，提出了一种新的局部泛化和桶化算法（LGB）。LGB防止身份和敏感值的披露，并保留重要的信息效用。它使用局部泛化和局部桶化来将元组划分为局部等价组，其中仅特定的QI值被泛化并将感兴趣的值划分为局部等价组。将敏感值分别存储到每个半敏感属性和敏感属性内的本地桶中LGB的详细形式化和分析在第2节中给出。 图图2示出了LGB对图1（b）的可能的匿名化结果。图 2，GID的属性表示本地等价组的ID，BID的标志表示对应属性内的本地桶的ID。注意，每个局部桶仅包含敏感值，并且所有QI值都通过局部泛化来泛化。例如，当对手匹配图2中Mark的QI值时，他只能推断Mark的记录ID可能是1004和1008，其属于GID 3的本地等价组，并且年龄属性包括本地等价组中的BID 1和2的本地桶。然后对手得出结论，马克的年龄可能是24岁，31岁，29岁和34岁。基于同样的原因，马克的疾病值可能是消化不良、肺炎和支气管炎。因此，攻击者无法确定目标元组的确切记录ID和敏感值1.2. 贡献这项研究扩展了个性化匿名的概念（Xiao和Tao，2006; Wang等人，2009年）。它假设个人可以随意确定其敏感值，属性可以是QI、半敏感或敏感，并且微数据表由若干QI属性、半敏感属性和敏感属性组成。我们假设对手的背景知识是：（1）由于人们必须谨慎地对陌生人保密，所以对手对半敏感属性和敏感属性没有获得任何敏感值;（2）在最坏的情况下，对手知道微数据表中所有个体的存在性和QI值。Adversary的目的是从匿名表中获取目标人的ID和敏感值。我们的贡献如下。首先，我们提出了LGB技术来保护个性化隐私信息。LGB结合局部泛化和局部桶化，为身份和敏感值提供安全保护，并尽可能减少信息丢失。局部泛化和局部桶化保护是独立的，因此它们可以通过适当的算法来实现，而不会单独削弱另一个保护。此外，每个区域中的本地桶化保护B. Li和K. 他沙特国王大学学报395SA我–6m G1/1图二. LGB的匿名表半敏感属性和敏感属性也是独立的。因此，局部桶化可以根据匿名化的实际需求，在不同的属性上遵循不同的原则其次，我们说明了LGB的有效保护身份和敏感值的基础上满足k-匿名和l-多样性原则，分别，即，对于每个元组，身份和敏感值的公开的概率分别至多为1/k和1/l。而且，由于各防护是独立的，因此任一防护等级都可以根据实际需要灵活调整，而不会单独降低另一防护等级。第三，提出了一种有效的实现LGB的算法，该算法同时具有k-匿名性和l-分集性.该算法包括局部泛化和局部桶化两个主要部分，分别将元组划分为局部等价群和将敏感值划分为局部桶。我们还提出了两种不同的算法来实现局部概化的基础上多维划分和最小化归一化确定性惩罚（NCP）分别为不同的利用目的。此外，每个局部桶的范围尽可能地缩小，以保留更多的信息效用。最后，我们进行了大量的实验，表1注释摘要符号描述TA微数据表气气属性ASAA敏感属性ASSA半敏感属性GA QI集团局部等价群t½A]属性A上元组t的值k控制k-匿名性l控制l-分集新的属性定义允许个人定制自己的隐私需求，匿名者可以根据不同属性的特点采用适当的匿名化方法来保护人们的个性化隐私信息，并保留有价值的我们对个性化隐私保护的定义如下。定义4（个性化隐私保护）。给定由多个QI属性、敏感属性和半敏感属性组成的微数据表T，个性化隐私保护旨在防止身份泄露并保护T中每个元组的所有敏感值。接下来，我们介绍QI集团的定义如下。定义5（分区和QI组）。 一个划分由T的几个子集组成，使得每个元组只属于一个子集，每个子集称为QI群。具体来说，让是m个QI群fG1;G2;·· ·;Gmg，则Sm Gi¼T，对于任何阐述了LGB的基本性质和不同的性能两个建议的局部泛化算法之间，通过1 2;i1\I2 ¼£可扩展性度量测量、NCP和聚集查询应答的结果研究了敏感值密度对半敏感属性的影响本文的其余部分组织如下。第二节给出了LGB的形式化描述和分析。第三节提出了一种实现LGB的算法。第4节给出了实验结果和分析。第5节介绍了相关的研究。第六部分对全文进行了总结，并提出了今后的研究方向2. 定义和分析2.1. 概念LGB技术的形式化需要一定的先验和新颖的概念，重要的符号总结如表1所示。我们首先根据数据值的属性重新定义属性的类别，如下所示。定义1（QI 属性）。 属性是视为合格中介机构当且仅当属性仅包含QI值时，表示为AQI的定义2（敏感属性）。当且仅当属性仅包含敏感值时，属性被认为是敏感属性，表示为定义3（半敏感属性）。 当且仅当属性包含QI值和敏感值时，属性被认为是半敏感属性，表示为ASSQI组在使用不同的匿名化方法时有不同的表现。一般来说，同一QI组中的元组具有相同的QI值。而在桶化中，每个QI组被分成两个子表，每个子表分别包含QI值和敏感值。定义6（等同性组）。给定T的一个具有m个QI群的划分，每个QI群被称为等价群，如果对于任何元组t2T，T的广义表包含以下形式的元组t[Gj½1];Gj½2];· ··;Gj½d];t½A]n;其中G j= 16j6m是包括t的唯一QI群;Gj=16i6d是Gj中的所有元组在AQI上的一般i化值，并且t1/2AS A]表示在A S A上的t的 值。定义7（桶）。给定具有m个QI组的T的划分，如果每个QI组被表示为作为形式：QITQIQI;BIDQIQIandSATQIASA;BIDQIQI;其中QI和SA分别是QI组中元组的QI值和敏感值，BID表示桶的ID。在以往的等价群中，包括QI值在内的所有整体属性我们提出了局部泛化技术的基础上的新的定义的属性划分元组到局部等价组，通过推广只是特定的QI值。16iG.B. Li和K. 他沙特国王大学学报3962½]2jjjjjjK22SMi1i2定义8（QI分区）。 对于任何元组t;QI，t表示包含t的QI值的属性QI1/2t] 1/4fAjt 1/2A]是QI值g：T的QI划分 将表划分为不相交的子集fT1;T2;·· ·;Tmg，使得对于任意16iTi1/2T i ; QI1/ 2 T i;Q I1/2Ti]。2.2. 保护分析在本节中，我们详细分析了本地泛化和本地桶化对身份和敏感值泄露的保护。在不失一般性的情况下，我们说明了本地泛化和本地桶化如何分别符合k-匿名性和l-多样性1K的定义-匿名性和L-多样性的介绍如下。1/112 1 2定义12（k-抗氧化性）。 微数据表T 满足k-定义9（局部等效组）。 给定微数据表T和具有m个子集的T的QI划分，如果QI值在对应属性中被推广为相同形式，则每个子集被称为局部等价群，使得对于任何元组t T，T的局部推广表包含以下形式的元组t匿名，如果对于任何元组t2T，身份泄露的概率小于或等于1=k。定义13（l-多样性）。如果任何敏感值被公开的概率小于或等于1=1，则微数据表T符合l-多样性。七七莎莎LEGj 1/2A1];·· ·;LEGj 1/2Ap];t 1/2A1];· ··;t 1/2Aq]其中LEG j16j6m是包含t的唯一局部等价群;A QI16i16p和A SA16i26q表示包含t的QI值和敏感值的属性 在j专家组中，LEGj/AQI]是LEGj中所有元组的AQI上的一般化值，然后，通过满足相应的条件，证明了局部广义表和局部桶化表也能满足k-匿名性和l我们首先考虑在局部广义表中防止身份泄露，并有以下引理和推论。引理1.给定一个局部广义表，对于任何元组t T，并且[t/2ASA]表示属性ASA上的t的 值。局部综合包含两个划分步骤。首先，它通过QI划分将元组划分为子集，其中所有记录都携带相同属性上的QI值。比如说，在图3（a）中，具有ID 1001和1002的元组在相同的子集中，因为它们两者都仅携带关于年龄和性别的属性的QI值。接下来，局部泛化将元组划分为每个子集内的局部等价组，并泛化它们的QI值。例如，在图3中的GID 3的子集中的元组。 3(a)被划分为图3（b）中GID 3和GID 4的局部等价群，并且图3（b）中的每个群都是局部等价群。同样，先前的分桶化保护整个敏感属性，而不是特定的敏感值。我们提出了局部桶化技术，将敏感值划分到相应属性的局部桶中。定义10（Local Bucket）。对于T中的任何半敏感属性或敏感属性，敏感值被划分到局部桶中，并且每个局部桶具有以下形式：IDT-ID;BID-ID和SAT-SA;BID-ID;身份披露的概率至多为1=LEGt，其中L2EGt为包含t的局部等价群证据根据定义9，同一局部等价群中的元组具有相同的包含QI值的属性因此，对手必须通过匹配QI值获得至少LEG t个可能的元组，则身份泄露的概率至多为1=jLEGt<$ j。H推论1.一个局部广义表满足k-匿名性，如果每个局部等价群至少包含k个元组.证据给定一个局部广义表，其中每个局部等价群至少包括k个元组，对于任何元组t2T，我们有jLEGt jPk;其中LEG t是包含t的局部等价群的大小。然后其中ID和SA分别表示本地桶中元组的ID和敏感值，BID表示本地桶的ID。1jLEGt j 61：属性中的bucket例如，在图4中，具有ID 1004和1005的元组在年龄属性内的BID 1的相同局部桶中，但是它们在疾病属性内的BID 2和3的不同局部桶因此，不同属性内的本地桶是独立的。注意，当微数据表不包含任何半敏感属性时，先前的等价组和桶可以分别被视为局部等价组和局部桶的特殊情况。基于定义9和10，我们将LGB技术定义如下。定义11（局部泛化和桶化）。给定一个微数据表T，通过局部泛化和局部桶化的划分，给出了T的局部泛化和局部桶化，并且每个元组和敏感值分别属于一个局部等价群和局部桶根据引理1，任何元组的身份公开的概率至多为1=k。因此，局部广义表满足k-匿名性. H接下来，我们讨论对本地分桶表中的敏感值的保护。假设对手知道t对手需要通过匹配QI值来在本地分桶表中找到t定义14（匹配元组）。 给定一个局部分桶表Tbuc，并且对于任何元组t T，元组mt Tbuc是t，如果t的每个QI值与mt的QI值匹配。1在本文中，我们使用频率l-分集来限制LGB，以及其他版本的LGB。L-分集（例如，熵L-分集）也可以被应用。B. Li和K. 他沙特国王大学学报39722ðÞP16;P16;P16;P16吉吉pt;sXpt;mbpsjt;mb6Xpt;mbjmbs0j：;（c）ÞjmbjjmbjLMB200升图三. 局部泛化的例子。由此可见：psjt;mbsj6jmbs0j;然后：jmbjjmbjMBH见图4。 本地分桶表。mbjmbj定义15（匹配桶）。给定局部桶化表Tbuc，并且对于任何元组t T，如果在MB.例如，当对手在图4的局部分桶表中匹配Mark时，他可以推断Mark我们将pt;s表示为t的敏感值s暴露的概率，并让p t;b表示t在桶b中的概率。然后我们有下面的引理和推论。引理2. 给定局部分桶表，对于任何元组t T，暴露t的任何敏感值s的概率如下：推论2.如果每个局部桶满足以下条件，则局部桶化表符合l-多样性原则：（1）每个敏感值在局部桶中最多出现一次;（2）每个局部桶的大小至少为l.证据 根据引理2，对于任何元组t2T，我们有ptsptmbjmbs0j. jmbj我们限制每个敏感值在本地桶中最多出现一次，因此对于任何s2T，jmbsj61：对于任何局部桶B，我们有：pjb jPl：然后又道：p t s6Xptmbjmbs0jMBpt;s6Xpt;mbjmbs0j61Xpt;mb1：其中，jmb=s0=j是匹配桶mb中出现最敏感的值s 0的数量，jmbj是mb的大小。证据为了获得敏感值s，对手必须计算t存在于每个局部桶中并且t在每个局部桶内携带敏感值s的概率。然后，对手有：pt;sXpt;bpsjt;b;B其中，p，t，b表示假定t在局部桶b中，t携带敏感值s的概率。攻击者消除不包含任何匹配元组t的本地桶，表示如下：p=0;b=0; if根据定义15，我们有：pt;sXpt;mbpsjt;mb;MB在mb中，对出现最敏感的值s0表示为：jmbsj6 jmbs0j：因此，局部分桶表通过满足条件而符合l-分集。H最后，通过满足推论1和推论2中的条件，我们证明了局部广义桶化表满足k-匿名性和l-多样性.推论3.局部广义桶化表满足k-匿名性和l-多样性的条件是：（1）每个局部等价群至少包含k个元组;(2)每个敏感值在每个局部桶内最多出现一次;以及（3）每个局部桶的大小至少为L。证据根据定义11，局部泛化和局部分桶的保护是独立的，推论1和2中的条件是不重叠的。因此，只要局部广义和桶化表满足相应的条件，它就符合k-匿名性和l-多样性。H通常，局部泛化增强了局部桶化的保护，因为局部泛化将QI值转换为增加目标元组的匹配元组的数量的相同形式。例如，ID为1006的元组位于图中疾病属性内BID 3的局部桶。 四，;MBB. Li和K. 他沙特国王大学学报398f···g而他在图2中的BID 2和BID 3中。 2，因为他的QI值在GID 2的局部等价群中被推广为相同的形式，这增加了他的匹配元组的数量。然后，他的疾病值被公开的概率降低到1= 4。3. 该方法本节提出了一个算法，以实现LGB符合k-匿名和l-多样性。此外，提出了两种算法来实现不同的利用目的的局部泛化。LGB的主要过程在算法1中给出。算法1. LGB输入：微数据表T，参数k和l输出：匿名表Tanony1：属性，包括感知值g2：Tanony¼T3：对于每个属性2属性4： ValuePairsen;s2attrandsissensitiveg5：Tanony/局部分桶化Tanony;ValuePairsen;l6：结束锻造7：Tanony;k8：返回Tanony数据结构Attrisen（第1行）将包括敏感值的属性存储在T中，即，半敏感属性和敏感属性的集合。变量Tanony（第2行）表示匿名化的结果，并且它被初始化为T。在每次迭代中（第3行到第6行），算法从属性中挑选一个属性，并选择具有敏感值的元组（第4行）。然后，该算法基于l的值将元组划分为局部桶（第5行）。在循环之后，函数local generalization根据k的值将Tanony划分为局部等价组（第7行）。最后，算法返回Tanony作为T的匿名化结果（第8行）。注意，在算法1中，QI属性不包含在Attr_sen中，并且ValuePair_sen不包括任何在attr中具有QI值的元组。因此，没有一个本地桶包含任何QI值。该过程包括两个主要部分，即局部桶化（第5行）和局部泛化（第7行）。我们将在本节的其余部分详细说明每个部分。3.1. 局部桶化本节提出了一种有效的算法来实现算法1中的函数局部桶化。该算法将ValuePairsen中的元组划分为局部桶，并尽可能缩小每个局部桶中敏感值的范围，以保持更多的算法2中示出了详细的过程。算法2. 局部桶化输入：匿名表Tanony，值对ValuePair，参数l输出：匿名表Tanony1：ValuePairg中的值数量;数值计数2：中位数1/4计算中位数1/4数值1/43：VPsmall;sjid;s2ValuePairands6mediang4：VPbig;sjid;s2ValuePairands>mediang5：如果检查VPsmall;l并且检查VPbig;l，则6：Tanony¼局部桶形化Tanony;VP小;l7：Tanony¼局部桶化Tanony;VPbig;lbig8：其他9：dividevidebuckets-匿名;ValuePair;值对10：如果11：返回Tanony该算法递归地将ValuePair划分为两个较小的集合，并且它们的敏感 值 范 围 不 重 叠 。 数 据 结 构 valuenumber 存 储 每 个 敏 感 值 和ValuePair中计数的出现次数（第1行）。算法-Rithm计 算敏 感 值的 中 值，在valuenumber （ 第2 行 ）中 ， 将ValuePair分为两个较小的集合（第3行和第4行）。函数检查检查ValuePair是否可以被划分成符合l-多样性的局部桶（第5行），使得最出现敏感值的数量与l的值的乘积不大于ValuePair的大小。如果VPsmall和VPbig 都满足条件，则算法进行递归调用的功能针对VPsmall 和 VPbig 的 局 部 桶 化 （ 第 6 行 和 第 7 行 ） 。 否 则 ， 该 算 法 将ValuePair中的元组划分为局部桶（第9行）。函数dividebuckets是由assign实现的。m-Invariance（Xiao and Tao，2007）的分割算法来满足推论2中的条件。提案1. 在局部桶化阶段后，Tanony证据函数划分桶由m-不变性的分配算法实现，其中参数l和m在数学上是等价的。在算法2的每个递归中，检查VPsmall和VPbig的两个集合以满足l-合格条件（Xiao和Tao，2007）。分配算法根据m-不变性将元组划分为m个唯一桶.则每个生成的局部桶的大小至少为l，并且每个敏感值在每个局部桶中最多出现一次因此，相应属性内的所有局部桶都满足基于l的值的推论2中的条件。在算法1中的循环（步骤3至6）之后，每个半敏感属性和敏感属性内的具有敏感值的元组被划分成l-唯一的局部桶，使得T_anony满足l-多样性原则。H3.2. 局部泛化在本节中，我们分别提出了基于多维划分和最小化NCP的两种局部泛化算法。我们在第4节中进行的实验将显示它们的不同性能。我们详细说明每个算法如下。3.2.1. 基于多维划分先前的多维划分（LeFevre等人， 2006）是将元组划分为等价组的有效且流行的方法。但是，它不适用于个性化隐私要求的发布我们结合多维划分和QI划分，根据元组的特定QI值将元组划分为局部等价组。定义16（多维QI分区）。给定具有d个属性的微数据表T和具有m个子集T1;T2; Tm的QI分区，多维QI分区将元组划分为每个子集内的非重叠多维区域。B. Li和K. 他沙特国王大学学报399J2ð½] ½]···½ ][]]¼-ðÞXX12D覆盖D1/2Ai]×D1/2 Ai]×···×D1/2Ai] × 1/2Ai]× 1/2 A i ] ×1/2Ai × 1/2 A i × 1/2 A i ×1/2A独特的区域。为了尽可能地减少信息损失，每个局部等价群的大小应被最小化以仅满足k-匿名性，使得每个区域被划分为更小的区域，直到它们中的至少一个的大小小于k。算法3详细描述了基于多维划分的局部泛化算法3. 局部泛化输入：微数据表T，参数k输出：匿名表Tanony1：Tanony¼。2：T个子集，其中T的子集被QI划分g3：对于每个T集，2个T子集4：分区集¼ fT集g5：whilepartition set6：操作集1/4拾取集1/4分区集1/47：分区集1/4分区集-操作集8：QI设置为¼QI½opperset]9：分区标志¼假等于k（第15行），算法将Sl和Sr添加到分区集合中（第16行和第17行），并将分区标志设置为真（第18行），然后中断while循环（第19行）。否则，从QI集合中删除attri（第21行）。如果在while循环之后partition flag为false，则不能使用单个属性将oper set划分为符合k-anonymity的较小该算法将操作集中的QI值一般化，并将广义集gen集添加到Tanony中（第25和26行）。最后，算法返回Tanony作为广义结果（第30行）。基于多维划分的局部概化是一种非常适合的方法，因为它均匀地将元组划分为局部等价组，从而减少了大量的信息损失。在实践中，一些微数据表是为了特定的目的而发布的，并且信息效用应该通过给定的度量来评估。接下来，我们提出了另一种算法来实现局部泛化，它尽可能地保留由特定度量评估的信息效用3.2.2. 基于最小化NCP在本节中，我们提出了一种基于效用的算法，通过使用NCP来实现局部泛化（Xu et al.， 2006）作为信息度量。 对任意元组t2T;t的值v在范畴属性A cat 上推广为v ω，则.10：当Q1设置时11：属性选择维度操作者集合;QI集合12：分割值¼cal中位数运算符集;属性NCPAcat大小vω;j一只猫j13：Sl/ftjt2opersetandt/fattri]6splitvalueg14：Srftjt2opersetandt½attri]>splitvalueg15：如果jSljPk和jSrjPk，则16：分区集1/4分区集1/417：partition set/partition set分区集其中，size=v ωn是在Acat的层次树中作为v ω的后代的叶节点的数量，并且jAcatj表示属性Acat上的不同值的数量。当tNCPA其中v ω和v ω是较低的18：分区标志¼真numrangeAnum低上19：休息20：其他21：QI集QI集属性22：如果结束第23章：结束24：如果分区标志为假，则25：生成集/一般化操作器集26：Tanony/Tanony生成集27：如果结束第28章：结束29：结束30：返回顶部数据结构T匿名和T子集分别存储匿名化结果和由QI分区划分的T的子集（线1和2）。在每次迭代中（第3行到第29行），算法挑选子集T集并将其划分为局部等价群。数据结构划分集包含未被广义化的元组的集合，并且它在开始时（第4行）包括T集合。只要分区集不为空（第5行），算法就从分区集中挑选并消除一个集（第6行和第7行）。数据结构QI集合表示操作集合中包括QI值的属性的集合（第8行），并且分区标志表示操作集合是否可以被划分（第9行）。当QI集合不为空时（第10行），该算法选择一个属性属性并计算中值（第11和12行），然后将操作集合分成两个较小的集合（第13和14行）。如果Sl和Sr的大小都大于或分别为广义值域的上界和上界，range A num是属性A num上所有值的范围。整个广义表的信息损失表示为DNCPAitt：t2T i¼1算法4描述了基于极小化NCP的满足k-匿名性的局部推广.数据结构T匿名和T子集分别存储匿名化结果和由QI分区划分的T的子集（行1和2）。在每一次迭代中（第3行到第24行），该算法挑选子集T集并将其划分为局部等价群（第3行）。数据结构QI集合表示包括T集合（线）中的QI值的属性的集合4），而分割集表示尚未被推广的元组的集合（第5行）。当分割集不为空时（第6行），算法从分割集中挑选并消除一个集合运算集（第7和8行）。如果操作集的大小小于2k（第9行），将oper集中的元组推广并添加到Tanony中（第10和11行）。否则，函数find seeds返回两个基于QI集合最大化NCP值的种子记录（第13行），并且算法根据种子元组将oper集合划分为两个较小的集合（第14行）。函数查找种子和划分表可以通过（Xu et al.， 2006年）。接下来，如果T1和T2的大小都大于小于或等于k，算法将它们添加到划分集合中（第15至17行），否则，将oper集合泛化并添加到Tanony中（第18至20行）。最后，算法返回Tanony作为广义结果（第25行）。Þ ¼B. Li和K. 他沙特国王大学学报400¼þ德国马克Jj、算法4. 局部泛化输入：微数据表T，参数k输出：匿名表Tanony1：Tanony¼。2：T个子集，其中T的子集被QI划分g3：对于每个T集，2个T子集4： QIset（QI 设 置）5：分区集¼ fT集g6：whilepartition set7：操作集1/4拾取集1/4分区集1/48：分区集1/4分区集-操作集9：如果joper设置j2k，则v<或APv或A6v或A其中v是来自D/2A的随机值。 根据（Zhang等人， 2007），相对误差率，表示为R误差，由以下等式给出：B. Li和K. 他沙特国王大学学报401ð Þð Þ表2属性的描述属性值类型灵敏度类型大小1性分类半敏感22年龄连续半敏感733关系分类齐134婚姻状况分类齐65种族分类齐96教育分类齐117每周小时数连续齐938占领分类半敏感2579工资连续敏感719图五. 可辨别性度量结果。见图6。 NCP结果。R误差：上求和-下求和=上求和;其中Sumupper和Sumlower分别是工资总和的上限和下限，Sumact是实际值。根据（Zhang et al.，2007），Sum upper和Sum lower通过组中的“点击数”计算。但是，由于每个元组都包含在不同半敏感属性的局部桶中，因此我们需要统计每个工资局部桶中满足查询条件的元组的可能数量的上界和下界设Prot A表示t与属性A上的条件匹配的概率，并且Pro t表示t满足查询条件的概率，则我们有。ProtprottumorYprottumor：对于salary中的每个局部bucket，我们计算概率之和，然后分别将概率之和向下舍入和向上舍入为元组数量的下限和上限。 接下来，我们通过帮助表统计本地bucket中工资总和的下限和上限，分别表示为Sumlowerbucket和Sum upperbucket。整个表中工资总额的下限和上限表示为。Sumlower¼XSumlowerb;B和Sumupper¼XSumupperb：B一B. Li和K. 他沙特国王大学学报402见图7。 查询应答结果。见图8。不同密度的敏感值。图7（a）和7（b）分别示出了LGB_MDP和LGB_NCP的聚合查询应答的结果。相对误差率随k或l值的增大而增大，且受k的影响大于l的影响。 因此，局部泛化比局部桶化对信息效用的影响更大。注意，当l较 小 时 ， LGB_MDP 具 有 比 LGB_NCP 更 低 的 相 对 错 误 率 ， 因 为LGB_MDP比LGB_NCP更均匀地将元组划分为局部等价组，这缩小了广义值的范围。但随着l的增长，LGB_MDP的相对错误率逐渐接近LGB_NCP，因为局部桶的范围足够大，可以覆盖查询条件，因此局部桶化具有越来越多的对信息效用的重要影响。总之，当l值较小时，LGB_MDP优于LGB_NCP其他方面，LGB_MDP和LGB_NCP的性能几乎相同.4.3. 密度效应我们检查了半敏感属性中敏感值的密度对LGB_MDP的影响。每个半敏感属性的敏感值百分比分别设置为10%、20%、30%和40%左右结果通过聚合查询应答进行评估，图8（a）、8（b）、8（c）和8（d）示出了结果。B. Li和K. 他沙特国王大学学报40