ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 ２０１１，４７（３０） １０９ 面向统计应用的隐私保护发布 金华，鞠时光，兰丽辉，刘善成 ＪＩＮ Ｈｕａ，ＪＵ Ｓｈｉｇｕａｎｇ，ＬＡＮ Ｌｉｈｕｉ，ＬＩＵ Ｓｈａｎｃｈｅｎｇ 江苏大学计算机科学与通信工程学院，数据库与信息安全研究所，江苏镇江２１２０１３ Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ＆Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｄａｔａｂａｓｅ＆Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ．Ｊｉａｎｇｓｕ Ｕｎｉｖｅｒ－ ｓｉｙｔ，Ｚｈｅｎｊｉａｎｇ，Ｊｉａｎｇｓｕ ２１２０１３，Ｃｈｉｎａ ＪＩＮ Ｈｕａ，ＪＵ Ｓｈｉｇｕａｎｇ。ＬＡＮ Ｌｉｈｕｉ。ｅｔ ａ１．Ｐｒｅｓｅｒｖｉｎｇ ｐｒｉｖａｃｙ ｆｏｒ ｓｔａｔｉｓｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｄａｔａ ｐｕｂｌｉｓｈｉｎｇ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉ－ ｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ．２０１１。４７（３０）：１０９—１１２． Ａｂｓｔｒａｃｔ：Ｃｕｒｒｅｎｔ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖａｔｉｏｎ ｍｏｄｅｌｓ ａｒｅ ａｌｍｏｓｔ ｇｅｎｅｒａｌ ｄａｔａ ｐｕｂｌｉｓｈｉｎｇ ｍｅｔｈｏｄｓ．Ｅｖａｌｕａｔｉｏｎ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｌｏｓｓ Ｃａｌｌ ｎｏｔ ｒｅｆｌｅｃｔ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｐｕｂｌｉｓｈｅｄ ｄａｔａ ｗｅｌｌ ｆｏｒ ｓｏｍｅ ｓｐｅｃｉｉｆｃ ａｐｐｌｉｃａｔｉｏｎ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｓｅｑｕｅｎｃｅ ｔａｂｌｅ ｐｕｂｌｉｓｈｉｎｇ ｍｏｄｅｌ ｂａｓｅｄ ｏｎ ｕｓｅｒ ｉｎｔｅｒａｃｔｉｖｉｔｙ ｆｏｒ ｓｔａｔｉｓｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ．Ｔｈｅ ｍｏｄｅｌ ｃｏｎｓｉｄｅｒｓ ｒｅｑｕｉｒｅｍｅｎｔｓ ｏｆ ｕｓｅｒｓ ａｎｄ ｐｕｂｌｉｓｈｅｓ ｄａｔａ ｂａｓｅｄ ｏｎ ｍｉｎ—ｃｏｖｅｒｓ ｏｆ ｃｏｎｓｉｓｔｅｎｔ ｃｌａｓｓ ｗｉｔｈｏｕｔ ｓｅｐａｒａｔｉｎｇ ｑｕａｓｉ ｉｄｅｎｔｉｆｉｅｒｓ ａｎｄ ｓｅｎｓｉｔｉｖｅ ａｔｔｒｉｂｕｔｅｓ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｏｄｅｌ ｈａｓ ａ ｇｏｏｄ ｑｕｅｒｙ ａｃｃｕｒａｃｙ ｆｏｒ ｍａｓｓ ｄａｔａ ｓｅｔｓ． Ｋｅｙ ｗｏｒｄｓ：ｄａｔａ ｐｕｂｌｉｓｈｉｎｇ；ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖａｔｉｏｎ；ｓｔａｔｉｓｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ；ｕｓｅｒ ｉｎｔｅｒａｃｔｉｖｉｔｙ；ｓｅｑｕｅｎｃｅ ｔａｂｌｅ 摘要：现有的隐私保护模型多为通用发布方法，基于信息损失率的评价方法在具体应用中并不能很好地反映数据的发布质 量。面向统计应用提出了一种基于交互的序列表发布模型，结合用户查询需求基于ＱＩ相容类最小覆盖，在不割裂ＱＩ和敏感属性 的基础上进行数据发布。实验结果表明，该模型对于大数据集的隐私保护发布具有很高的查准率。 关键词：数据发布；隐私保护；统计应用；用户交互；序列表 ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２．８３３１．２０１１．３０．０３０ 文章编号：１００２—８３３１（２０１１）３０－０１０９－０４ 文献标识码：Ａ 中图分类￣：ＴＰ３１１ ｌ引言 表２中进行３种联合查询： 随着信息技术的发展和社会生活的一体化，包含个人信 查询１：年龄大于５０岁的平均收入。这一查询正好覆盖了 息数据收集的种类和数量呈指数增长。信息共享成为人们日 表中的第三个等价类，可以查询到准确的结果。其平均收入 常工作、生活和学习中日益普遍的行为。但信息共享中隐私 为￥８０ ０００。 泄露的现象也屡见不鲜。因此要在发布数据的同时进行隐私 查询２：年龄在３５岁至５５岁之间的收入总和。对于泛化 保护ｎ。 。近年来国外研究者已经提出了一些基于匿名思想的 表２存在两个极端的情况：一是等价类１和等价类３都不满足 隐私保护发布模型，如 匿名模型 ］、Ｌ 多样性模型 、ｔ－ｃｌｏｓ— 时，查询结果即为等价类２的和￥２１０ ０００；二是等价类１和等 ｎｅｓｓ框架［５１和个性化匿名模型 等。这些隐私保护模型都为通 价类３都满足时，查询结果即为￥６１５ ０００。显然查询结果误 用的数据发布方法，实现通常基于泛化或有损连接的算法 ， 差很大。 衡量发布质量都用基于信息度量的信息损失率来表示 。其 表１原始数据 度量方法通常有：最小信息缺损度量、可辨识度量、ＩＬｏｓｓ和折 Ａｇｅ Ｚｉｐｃｏｄｅ 衷度量。但是基于这些通用信息度量方法的信息损失率，在 ３５ ２７ １０１ ￥５４ ０００ 一些具体的应用中并不能很好地反映数据发布的质量，比如 ３８ ２７ １２０ ￥５５ ０００ 在一些统计分析中，往往需要进行联合查询，用户关心的是在 ４０ ２７ １３０ ￥５６ ０００ ４１ ２７ ２２９ 满足隐私保护的前提下其查询的结果需具有很高的准确率， ￥６５ ０００ ４３ ２７ ２６９ ￥７５ ０００ 只有查询结果准确了，这些发布的数据才有较高的统计应用 ４７ ２７ ２４３ ￥７００００ 价值。下面用一个例子来考察一下隐私保护的联合查询。 ５２ ２７ ６５６ ￥８Ｏ ０００ 表１是一个微数据发布的原始数据，对应的表２为该数据 ５３ ２７ ６８６ ￥７５ ０００ 采用泛化的方法经过３．匿名保护后发布的数据。比如在发布 ５８ ２７ ６３５ ￥８５ ０００ 基金项目：国家自然科学基金（ｍｅ Ｎａｔｉｏｎａｌ ＮａＲｎ＇ａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ ｕｎｄｅｒ Ｇｒａｎｔ Ｎｏ．６０７７３０４９）；江苏省自然科学基金（Ｎｏ．ＢＫ２０１０１９２）； 教育部博士点基金项目（Ｎｏ．２００９３２２７１ １０００５）。 作者简介：金华（１９７７～），男，博士生，讲师，ＣＣＦ会员，研究方向为数据库安全、数据隐私保护；鞠时光（１９５５一），男，博导，教授，博士；兰丽辉 （１９７６一），女，博士生；刘善成（１９８８一），男，硕士生。Ｅ－ｍａｉｌ：ｊｉｎｈｕａ＠ｕｊｓ．ｅｄｕ．ｃａ 收稿日期：２０１１—０７—２２；修回日期：２０１１－０９—０２ １１０ ２０１１，４７（３０） ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 表２基于泛化的３．匿名表 Ｚｉｐｃｏｄｅ Ｓｅｘ Ｓａｌａｒｙ 系。因此上述这些方法无法得到用户实际所关心的准确查询 结果。本文提出的基于交互的序列表发布隐私保护模型是在 不割裂ＱＩ和ＳＡ对应关系的前提下，实现的隐私保护，对于大 数据集具有很高的查准率。本文模型的出发点是基于统计应 ｍ一 ２ ３ ４ ６ ７ ９ 用查询的实际需求和对大量实际数据集ＱＩ属性的分析作出 的。在实际的应用查询中查询所涉及到的ＱＩ属性数目一般为 ∞ 钙钾观 一３个左右，而以往基于匿名的发布模型都是将所有ＯＩ属性捆 一” 抛 ｎｅ ｌ绑在一起进行匿名的。通过对ＵＣＩ ｍａｃｈｉｅａｒｎｉｎｇ ｒｅｐｏｓｉ． ｔｏｒｙ的人口统计数据，Ａｄｕｌｔ原始数据集（３０ １６９条记录）进行 统计发现，存在大量本身就满足匿名的数据记录，其所占比例 一Ｍ Ｍ Ｍ Ｆ Ｆ Ｍ Ｍ Ｆ Ｍ 跟ＱＩ的数目存在密切的关系。图ｌ为列举所有ＱＩ属性组合的 ２７１ ２７１ ￥５４ ０００ ￥５５ ０００ ２７１ ２７２＊ Ａ一 枷 枷枷枷枷圳枷圳 ２７２ ２７２ ２７６＊ ￥５６ ０００ ￥６５ ０００ ￥７５ ０００ ￥７０ ０００ ￥８０ ０００ ２７６＊ ２７６＊ ￥７５ ０００ ￥８５ ０００ 查询３：女性的最低收入。因为Ｓｅｘ属性为全泛化，因此查 询结果为［￥５４ ０００，￥８５ ０００］，造成了巨大的误差。 文献【９］针对上述问题提出了一种基于置换的发布方法。 其具体步骤是：首先采用泛化的方法得到匿名泛化表，然后在 泛化表的等价类中对敏感屙性ＳＡ进行置换，最后将泛化的准标 识符ＱＩ恢复原值。对表１进行置换方法发布可得到表３。该置 换方法针对上述三种联合查询，得到的结果分别为：￥８Ｏ ０００， ［￥５３０ ０００，￥５４０ ０００］，［￥５４ ０００，￥８５ ｏｏｏ］。该方法虽然在一定 程度上降低了查询的误差，但是如果查询范围跨越了等价类 的界限，由于等价类中的ＳＡ已经被置换过了，因此还会存在 较大的误差；而且该方法只适用于数值型的敏感属性，而不适 用于类别型的敏感属性。 表３基于置换的３．匿名表 Ｓａｌａｒｙ ￥５６ ０００ ￥５４ ０００ ￥５５ ０００ ￥６５ ０００ ￥７０ ０００ ￥７５ ０００ ￥７５ ０００ ￥８０ ０００ ￥８５ ０００ 本文在前人工作的基础上针对统计应用的隐私数据发布 问题进行了进一步研究。其主要贡献如下： （１）通过对大量实际数据集的分析，并结合统计应用查询 的实际需求，总结了ＱＩ属性与记录 匿名之间的影响关系。 （２）提出了一种基于交互的序列表发布隐私保护模型，通 过该模型的发布能够在保证隐私保护要求的前提下，最大程 度地满足用户统计应用查询的需求。 （３）给出了发布模型的算法描述，并基于实验，对所提出 的方法进行了验证与分析比较，测试了算法发布数据的质量， 结果表明所提出的方法能够在提供足够的隐私保护度的前提 下，具有更高的查准率，更符合实际应用的需求。 ２面向统计应用的序列表发布模型 ２．１模型思想 有损连接的方法是将ＱＩ和ＳＡ分表发布的，其ＱＩ属性和 ＳＡ之间是被割裂开的，在发布表中不存在ＱＩ和ＳＡ之间的准 确对应关系。置换方法将等价类中的ＳＡ错乱了，因此ＱＩ和 ＳＡ之间的对应关系也是错乱的。泛化方法将ＱＩ进行了泛化， 虽然没有分表发布，但本质上也割裂了ＱＩ和ＳＡ之间的对应关 平均统计数据，当ＱＩ数目为３时，即使ｋ取２０，其平均满足比例 也将近８５％，而所有ＱＩ组合满足比例只有５％，即使ｋ－＝２时，也 只有４０％。可见将所有ＱＩ属性捆绑在一起进行匿名，必然导 致大量记录的ＯＩ和ＳＡ被割裂。 ０Ｏ 祠 ９Ｏ 丑 ８０ 懈 ７０ ６Ｏ 暇 ５０ 岛 ４０ ３０ ｌ盥Ｉ ２０ １０ ０ 撰 图１ Ａｄｕｌｔ数据集满足ｋ匿名统计 基于上述分析，本文提出一种序列表的发布模型，将满足ｋ 匿名的记录按照ＱＩ屙Ｉ生数目由高到低分成一组序列表进行发 布。首先发布包含全部９个ＱＩ和ＳＡ属性表，且满足ｋ匿名的记 录。然后将剩余的记录按照８个ＱＩ和ＳＡ属性表，发布满足ｋ匿 名的记录。以此类推，直到ＱＩ的数目为３。最后将所有剩余的记 录采用泛化方法进行发布，为了缩小泛化范围，将这些剩余记录 按照３个ＱＩ和ＳＡ属性表泛化发布，从而提高泛化表的查准率。 序列表的发布过程中，在选取ＱＩ时存在较多的ＱＩ组合方 式，遍历所有ＱＩ组合会导致发布序列表数量的庞大，而且从实 际出发有相当一些组合并没有现实意义。为此本文引入交互 的发布方式，并提出ＱＩ相容类和相容类最小覆盖的概念。 定义１（ＱＩ相容类）设原 椭 个ＱＩ屙陛， ｆ］（ｆ∈［１， 棚）为表中第ｊ个ＱＩ属性，则与任一用户查询相关的所有 ［ｉ］ 集合称为一个ＱＩ相容类。记作ＣｏｎＣｌａｓｓ｛Ｑ／［ …，Ｑ， ） ，ｍ 集合中的ＯＩ属性数。 定义２（ＱＩ相容类最小覆盖）当发布，２个ＱＩ和ＳＡ属性表 时，能覆盖所有相容类的最少个｛ ［ …， ［ ｝ 组合称为ｎ 个ＱＩ的相容类最小覆盖。记作ＭｉｎＣｏｖｅｒＱＩ 。 通过与用户的简单交互，将查询分为感兴趣查询、一般查 询和不感兴趣查询三种情况。将查询映射成ＱＩ相容类，根据 用户兴趣确定相容类的优先级顺序，仅考虑前两种查询对应 的相容类，设计ＧｅｔＭｉｎＣｏｖｅｒ算法计算发布ｎ个ＱＩ序列表的最 小覆盖。模型基于ｏＩ相容类最小覆盖进行序列表发布，既考 虑了用户的查询需求，同时又大大减少了需要发布的序列表 数量。该模型发布的数据能够满足高准确率的查询，但其缺 陷在于所发布的数据存储在多种不同结构的表中，因此在发 布数据的同时应该开发一个相应的查询接口一起发布，这对 于开发人员而言是比较简单的工作。 金华，鞠时光，兰丽辉，等：面向统计应用的隐私保护发布 表４ Ａｄｕｌｔ实验数据集描述 ２．２算法描述 根据序列表发布模型的思想，本文设计了一个基于交互 （１４） （１５） （１６） ｉｆ记录的ＳＡ为类别型 将剩余记录进行泛化发布，添加到 ｅｌｓｅ 式的序列表发布算法（ＩｓＴＡ），具体算法描述如下所示： 算法１ ＧｅｔＭｉｎＣｏｖｅｒ （１７） （１８） 基于置换发布，添加到 ｅｎｄ ｉｆ 输入：原始数据表Ｔ，ＱＩ属性； ＱＩ相容类Ｊａｇｇｅｄ ＡｒｒａｙＣＣ（ＣｏｎＣｌａｓｓ［１］，…，ＣｏｎＣｌａｓｓ［ｉ］，…）； 输出：最小覆盖序Ｙ￣Ｊａｇｇｅｄ ＡｒｒａｙＭＣ（ＭｉｎＣｏｖｅｒＱＩ［３］，…， ＭｉｎＣｏｖｅｒＱＩ［ｄ一１］）。 流程：（１）ｆｏｒｅａｃｈ Ｊａｇｇｅｄ ＡｒｒａｙＣＣ （１９）ｅｎｄ ｆｏｒ （２０）ｅｎｄ ｆｏｒ （２１）ｅｎｄ ｗｈｉｌｅ ・ （２２）将所有序列表 输出； （２） ｉｔ］ＣｏｎＣｌａｓｓ［ｉ］ｌ＜３且为其他相容类的子类 （３） 将ＣｏｎＣｌａｓｓ［ｉ］从Ｊａｇｇｅｄ ＡｒｒａｙＣＣ中删除； （４） ｅｎｄ ｉｆ （５）ｅｎｄ ｆｏｒ ３实验结果及分析 本文基于ＵＣＩ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅｐｏｓｉｔｏｒｙ人口统计实际 （６）ｆｏｒ（ｊ＝ｄ一１，ｊ＞２，ｊ．．）／／ｊ表示记录的ＱＩ数目 （７）Ｔｅｍｐ ＡｒｒａｙＣＣ Ｊａｇｇｅｄ ＡｒｒａｙＣＣ 数据集进行实验分析，该数据集共有１４种属性，实验选择其中 的９种作为ＱＩ属性，Ｓａｌａｒｙ作为ｓＡ，原数据集中的Ｓａｌａｒｙ只有 大于５０ ０００和小于５０ ０００两种，对其按照６个级别进行了重 新分配。具体描述如表４所示。实验环境为Ｉｎｔｅｌ Ｐｅｎｔｉｕｍ Ｄ ３．００ ＧＨｚ ＣＰＵ，１ ＧＢ内存；ＸＰ系统；编程环境为Ｍｉｃｒｏｓｏｆｔ Ｖｉ． ｓｕａｌ Ｓｔｕｄｉｏ ２００８编译器。 （８） ｆｏｒｅａｃｈ所有ＱＩ数目为ｊ的覆盖组合 （９） 多的ＣｏｎＣｌａｓｓ （１Ｏ） （１１） （１２） ｉｆ ＭｉｎＣｏｖｅｒＱＩ［ｊ］［ｉ］可以覆盖Ｔｅｍｐ ＡｒｒａｙＣＣ中最 将ＭｉｎＣｏｖｅｒＱＩＤ］［ｉ］添加到Ｊａｇｇｅｄ ＡｒｒａｙＭＣ； 从Ｔｅｍｐ ＡｒｒａｙＣＣ中删除被覆盖的ＣｏｎＣｌａｓｓ； ｅｎｄ ｉｆ 根据实际用户查询需求，选取感兴趣查询和—般查询：［Ａｇｅ， Ｅｄｕｃａｔｉｏｎ，Ｓｅｘ］、［Ｒａｃｅ，Ｅｄｕｃａｔｉｏｎ，Ｓｅｘ］、［Ａｇｅ，Ｏｃｃｕｐａｔｉｏｎ］、［Ｏｃ— ｃｕｐａｔｉｏｎ，Ｎａｔｉｖｅ．ｃｏｕｎｔｒｙ１，将其映射为相容类，并获得最小覆 盖，如ｎ＝６时，ＭｉｎＣｏｖｅｒＱＩ ｛ １】，鲫２】，鲫３］，Ｑ／ｊ６】，鲫７］， 鲫８】｝。分别从最终用户所关心的查询准确率和算法执行效 （１３） （１４） （１５） ｉｆ Ｔｅｍｐ ＡｒｒａｙＣＣ为空 ｂｒｅａｋ； ｅｎｄ ｉｆ 率两个方面比较了基于Ｉｎｃｏｇｎｉｔｏ的全域泛化、置换和序列表 方法。 （１６）ｅｎｄ ｆｏｒ （１７）ｅｎｄ ｆｏｒ ３．１查准率比较 从最终用户需求的角度出发，在满足隐私保护要求的前 提下，查询准确率是用户最关心的性能发布指标，它反映的是 发布数据的查询结果与原始数据查询结果的完全匹配程度。 它由两部分构成：查询出的记录为原始记录（未泛化记录），这部 分记录的查准率为１００％，记作Ｐ… ；查询出的记录为泛化记录， 这部分记录的查准率通过两个结果间的距离来反映，本文采用 （１８）输出Ｊａｇｇｅｄ ＡｒｒａｙＭＣ 算法２ ＩＳＴＡ 输入：原始数据表Ｔ，匿名约束ｋ，ＱＩ屙陛，ＳＡ属性； 最小覆盖序列Ｊａｇｇｅｄ ＡｒｒａｙＭＣ； 输出：发布序列表 （Ｔｓ。， ，…， －－）。 流程：（１）ｗｈｉｌｅ Ｔ≠ （２）ｆｏｒ（ｊ＝ｌＱＩ Ｊ，Ｊ＞２，ｊ一） （３） ｆｏｒｅａｃｈ Ｊａｇｇｅｄ ＡｒｒａｙＭＣ中的ＭｉｎＣｏｖｅｒＱＩ［ｊ】 文献［１０］中的加权泛化距离来表示，记作Ｐｇｅｎ 示属性最大泛化距离。则总的查询率尸＝Ｐ ． ＃ｉ＇ｉｇｅ￣ｎＰ一 １ Ｖ１４． —茬 × ＾ 』ｍ （４） （５） （６） （７） ｆｏｒｅａｃｈ Ｔ中所有记录 ｉｆ记录的ＭｉｎＣｏｖｅｒＱＩ［ｊ］［ｉ］组合满足ｋ－匿名 将该记录的ＭｉｎＣｏｖｅｒＱＩ［ｊ］［ｉ］组合添加到 。； ｅｎｄ ｉｆ １００％，其中ＷＨＤ…ｄｅｒ表示记录的泛化距离，ＭａｘＣＷＨＤ￣）表 ： ＋ ＾ Ｊ，” （８） ｅｎｄ ｆｏｒ ，其中Ｎｕｍ为查询所涉及到的所有记录总数， （９） ｅｎｄ ｆｏｒ （１Ｏ）从Ｔ中删除被添加的记录； （１１）ｅｎｄ ｆｏｒ Ｎｕｍ ．啪为查询结果中的未泛化记录数，Ｈｕｍ 为泛化记 （１２）ｆｏｒｅａｃｈ Ｊａｇｇｅｄ ＡｒｒａｙＭＣ中的ＭｉｎＣｏｖｅｒＱＩ［３］ （１３）ｆｏｒ ｅａｃｈ Ｔ中剩余记录 录数。 图２为ｋ取值为５、１０时，泛化方法、置换方法和本文基于 交互的序列表方法查准率实验结果比较。 Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 ＋Ｇｅｎｅｒａｌｉｚａｔｉｏｎ Ｐｅｒｍｕｔａｔｉｏｎ十ＩＳＴＡ ＋Ｇｅｎｅｒａｌｉｚａｔｉｏｎ一－＊－－Ｐｅｒｍｕｔａｔｉｏｎ＋ＩＳＴＡ ∞∞鲫加∞如∞如加ｍ Ｏ 、 得 斟 ５００ ２ ０００ ５ ０００ １０ ０００ １５ ０００ ２０ ０００ ２５ ０００ ３０ ０００ ５００ ２ ０００ ５ ０００ １０ ０００ １５ ０００ ２０ ０００ ２５ ０００ ３Ｏ ０００ 选取记录数 选取的记录数 （ａ）ｋ＝５ 图２查准率比较 十２５．０Ｏ （ｂ）ｋ－１０ Ｇｅｎｅｒａｌｉｚａｔｉｏｎ Ｐｅｒｍｕｔａｔｉｏｎ—★ＩＳＴＡ —・一Ｇｅｎｅｒａｌｉｚａｔｉｏｎ Ｐｅｒｍ【ｕｔａｔｉｏｎ ★ＩＳＴＡ ２０ ００ 垦１５ ００ １０ ００ ５．０Ｏ ０．０Ｏ ５００ ２ ０００ ５ ０００ １０ ０００ １５ ０００ ２０ ０００ ２５ ０００ ３Ｏ ０００ ∞＼匠曾 ５００ ２ ０００ ５ ０００ １０ ０００ １５ ０００ ２０ ０００ ２５ ０００ ３０ ０００ 记录数 （ａ）ｋ－－５ 如 ｍ ０ ∞∞∞∞∞∞∞∞ 记录数 （ｂ）ｋ＝１０ 图３算法执行时间 可以看到，在面向大数据集发布时，序列表方法具有更高 的查询准确率，这是因为泛化或者置换方法都始终要求缸匿名 在所有的ＱＩ属性上。当ＱＩ属性个数较多时，需要泛化的记录数 直线上升，因此泛化的范围越来越大，甚至某些属性被完全泛 化，从而造成了很大的信自损失，使得查询结果只能很大的范围 描述，误差很大。但是实际上，面向统计分析的应用，其查询范 围很少是在多ＱＩ屙陧上进行查询，绝大部分是少量的几个ＱＩ属 性间的查询。序列表方法是基于大数据集本身存在大量无需泛 化就满足缸匿名保护的记录，尽可能多地发布这些原始记录，再 通过泛化发布剩余记录。因此本文提出的基于交互式的序列表 发布模型更能贴切实际的应用需求，在满足缸匿名隐私保护的 前提下，大大提高了查询准确率，具有更高的数据发布质量。 的概念，给出了模型的发布算法ＩＳＴＡ。以最终用户所关心的 查询结果准确率来反映数据发布的质量，与泛化和置换方法 进行了实验比较，结果表明，本文的模型能够满足统计应用的 发布需求，具有更高的发布质量。 参考文献： 【１】Ｆｕｎｇ Ｂ Ｃ Ｍ，Ｗａｎｇ Ｋｅ，Ｃｈｅｎ Ｒｕｉ，ｅｔ ａ１．Ｐｒｉｖａｃｙ－ｐｒｅｓｅｒｖｉｎｇ ｄａｔａ ｐｕｂｌｉｓｈｉｎｇ：ａ ｓｕｒｖｙｅ ｏｎ ｒｅｃｅｎｔ ｄｅｖｅｌｏｐｍｅｎｔｓ［Ｊ］．ＡＣＭ Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ，２０１０，４２（４）：１－５５． ［２］周水庚，李丰，陶宇飞，等．面向数据库应用的隐私保护研究综述［Ｊ］． 计算机学报，２００９，３２（５）：８４７—８６０． ［３］Ｍｅｙｅｒｓｏｎ Ａ，Ｗｉｌｌｉａｍｓ Ｒ．Ｏｎ ｔｈｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｏｐｔｉｍａｌ ｋ－ａｎｏ－ ｎｙｍｉｙ［ｔＣ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ２３ｒｄ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｐｒｉｎｃｉｐｌｅｓ ｏｆ ＤａｔａｂａＳＣ Ｓｙｓｔｅｍｓ．Ｐａｒｉｓ，Ｆｒａｎｃｅ：ＡＣＭ Ｐｒｅｓｓ，２００４：２２３．２２８． ３．２执行效率比较 实验分别汁算了ｋ－＝５、１０时，Ｇｅｎｅｒａｌｉｚａｔｉｏｎ、Ｐｅｒｍｕｔａｔｉｏｎ和 ＩＳＴＡ的算法执行时间，如图３所示。 总的来讲随记录数的增加、 的变大，三种方法的执行时间 ［４］Ｍａｃｈａｎａｖａｊｊｈａｌａ Ａ，Ｇｅｈｒｋｅ Ｊ，Ｋｉｆｅｒ Ｄ，ｅｔ ａ１．Ｌ—ｄｉｖｅｒｓｉｔｙ：ｐｒｉｖａｃｙ ｂｅｙｏｎｄ ｋ－ａｎｏｎｙｍｉｙ［ｔＣ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ２２ｎｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒ＿ ｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ．Ａｔｌａｎｔａ，Ｇｅｏｒｇｉａ，ＵＳＡ：ＩＥＥＥ Ｐｒｅｓｓ，２００６： ２４—３６ 都有所增加，但是前两种方法的增加幅度较大，而ＩＳＴＡ增加幅度 较小，而且总的执行时间要明显小于前两种方法。因为当记录 数增加时，ＩＳＴＡ方法需要泛化记录数的相对比例反而减小。大 量的记录不需要进行泛化处理，直接分表发布就可以了。而且 ［５］Ｌｉ Ｎｉｎｇｈｕｉ，Ｌｉ Ｔｉｎｃｈｅｎｇ，Ｖｅｎｋａｔａａｓｕｂｒａｍａｎｉａｎ Ｓ．Ｃｌｏｓｅｎｅｓｓ：ａ ｎｅｗ ｐｒｉｖａｃｙ ｍｅａｓｕｒｅ ｆｏｒ ｄａｔａ ｐｕｂｌｉｓｈｉｎｇ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ，２０１０，２２（７）：９４３—９５６． 它的泛化是基于相容类最小覆盖进行泛化的，无需象Ｇｅｎｅｒａｌｉｚａ． ｔｉｏｎ和Ｐｅｒｍｕｔａｔｉｏｎ方法那样将９个ＱＩ屙ｌ生绑定在一起泛化。此 外，Ｐｅｒｍｕｔａｔｉｏｎ是在Ｇｅｎｅｒａｌｉｚａｔｉｏｎ的基础上得到等价类之后再 将表中的内容恢复原值，再置换，因此庀的执行时间最长。 ［６】ＴＡＯ Ｙｕ－ｆｅｉ，ＣＨＥＮ Ｈｅ－ｋａｎｇ，ＸＩＡＯ Ｘｉａｏ－ｋｕｉ，ｅｔ ａ１．ＡＮＧＥＬ：ｅｎｈａｎｃ． ｉｎｇ ｔｈｅ ｕｔｉｌｉｔｙ ｏｆ ｇｅｎｅｒａｌｉｚａｔｉｏｎ ｆｏｒ ｐｒｉｖａｃｙ ｐｒｅｓｅｒｖｉｎｇ ｐｕｂｌｉｃａ— ｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ，２００９，２１ （７）：１０７３ １０８７． ［７］韩建民，岑婷婷，虞慧群．数据表缸匿名化的微聚集算法研究［Ｊ】．电 子学报，２００８，３６（１１）：２０２１—２０２９． ４结束语 针对现有通用隐私保护模型不能很好适合具体应用的情 况，面向统计应用数据发布进行了研究。通过对实际数据集 进行分析，从用户的实际查询需求出发，提出了基于交互的序 列表发布模型。在不割裂ＱＩ和敏感属性之间关系的前提下， ［８］兰丽辉，鞠时光，金华，等．数据发布中隐私保护研究综述［Ｊ］．计算 机应用研究，２０１０，２７（８）：２８２２．２８２７． 【９］Ｚｈａｎｇ Ｑｉｎｇ．Ｍｉｃｒｏｄａｔａ ｐｒｉｖａｃｙ ｐｒｏｔｅｃｔｉｏｎ ｔｈｒｏｕｇｈ ｐｅｒｍｕｔａｔｉｏｎ— ｂａｓｅｄ ａｐｐｒｏａｃｈｅｓ［Ｄ］．Ｎｏｒｔｈ Ｃａｒｏｌｉｎａ Ｓｔａｔｅ Ｕｎｉｖｅｒｓｉｙ，２００８．ｔ ［１Ｏ］韩建民，于娟，虞慧群，等．面向敏感值的个性化隐私保护［Ｊ］．电子 学报，２０１０，３８（７）：１７２３—１７２８． 达到隐私保护发布的目的。基于ＱＩ相容类和相容类最小覆盖