基于聚类结构编码的差分隐私异构数据发布.pdf

第 卷第 期计算机应用与软件 年 月 基于聚类结构编码的差分隐私异构数据发布高海燕高晋阳郑志华（晋中职业技术学院电子信息学院山西 晋中 ）（中北大学仪器与电子学院山西 太原 ）收稿日期：。国家自然科学基金项目（）；年山西省高等学校大学生创新创业训练计划项目（）。高海燕，讲师，主研领域：计算机应用。高晋阳，副教授。郑志华，讲师。摘要针对异构数据发布的隐私保护以及数据挖掘泛化性问题，提出一种用于聚类分析的异构数据差分隐私发布方案。为了解决处理隐私信息后缺乏正确引导的问题，将原始数据分组为集群，并利用集群标签对数据的集群结构进行编码，还为异构数据定制了一个同时考虑关系属性和集值属性的距离度量集群。在保留集群结构的同时迭代地概括原始数据。进一步在原始数据中加入噪声从而满足 差分隐私的要求。在满足差分隐私原则的前提下，提出一种同时处理关系数据和集值数据的不确定性算法，不同类型的数据以类似的方式进行匿名化。通过实验验证了该方法能够有效解决异构数据发布问题。关键词数据发布异构数据差分隐私聚类分析中图分类号 文献标志码 ：（，）（，），引言大数据时代下，信息已经成为了一种极为重要的战略资源，尤其在医疗、科研、军事等领域 。如何在发布数据的同时有效地保护隐私信息，同时尽可能多地保留受干扰数据的效用以进行后续数据分析成为了研究的重点 。异构数据通常由关系数据和集值数据组成，因此异构数据的隐私保护一般分为关系数据匿名化与集值数据匿名化 。对于关系数据匿名化问题，文献 隐藏识别属性和敏感属性之间的相关性，并生成 匿名相似性数据以显示身份和属性。等 通过在泛化过程中添加不确定性，可以有效发布差分隐第 期高海燕，等：基于聚类结构编码的差分隐私异构数据发布 私数据。对于集值数据匿名化问题，文献 提出一种数据分区技术，用于断开标识属性之间的关联，并在最终查询结果中添加噪声。文献 提出 匿名模型，通过区分集值属性中的敏感项和非敏感项，满足多样性相关性来防止属性泄漏。虽然上述方法取得了一定的效果，但是许多方法均是单独处理关系数据或集值数据，对于异构数据来说是否有效还需进一步研究。针对异构数据匿名化，也有一系列研究，文献 提出一个差分隐私回归分析模型，将目标函数转化为多项式形式，并对多项式表示的系数加入噪声。文献 将差分隐私与决策树相结合，提供分类器的隐私保护，还使用小批量梯度下降算法来保护训练数据的隐私。虽然这些工作针对某些特定数据考虑了异构数据的聚类性能，但是缺乏泛化性能，即上述匿名化过程不考虑一般性的聚类分析任务，因此用户在使用时缺乏灵活性与实用性。针对上述问题，提出了一种用于聚类分析的异构数据差分隐私发布方案。利用聚类标签对聚类结构进行编码，并结合泛化技术和输出扰动来掩盖原始数据。通过实验验证了该方法能够有效解决异构数据发布问题。差分隐私代表一个有限的数据域，代表一条具有 属性的记录。数据集 是 一组从数据域 中采样出来的 个记录。数据集 和 是两个相邻数据集，当且仅当 或 ，其中 表示该数据集，是通过在 数据集中添加 记录而生成的结果，差分隐私的定义如下所示。定义 （差分隐私）对于任何一对数据集 和，或者对于任何一组可能被消除的输出，它的随机机制 是差分隐私的。即：（）（）（）（）参数 被称为隐私预算，它是通过随机机制 来控制隐私保证的程度。越小意味着隐私保护程度越高。默认为一个正数并且它的数值通常比较小，例如：、和 。附加噪声的量不仅取决于隐私预算 还取决于随机机制的全局敏感度。全局敏感度反映了两个相邻数据集上函数输出的最大差分。定义 （全局敏感度）给定一个随机函数 ：，对于任意一对相邻数据集 和，的全局敏感度是：（）（）（）定义 （拉普拉斯机制）给定一个数据集 ，隐私预算 和一个随机函数 ：，其全局敏感度是 ，算法（）（）（）满足 差分隐私。定义 （指数机制）给定一个数据集 ，输出的范围 ，隐私预算 ，和一个效用的函数 ：（，），机制 以与 （，）()成正比的概率选择输出 来满足 差分隐私。差分隐私有两个重要的属性。它们在判断一种机制是否满足差分隐私中起着重要的作用。属性 （顺序组合），是一组隐私机制。如果每个 都提供一个 差分隐私并且 在数据集上顺序执行，则 将提供()差分隐私。顺序组合表明当许多差分隐私被应用于相同的数据集时隐私预算和噪声会线性增加。属性（平行组合），是一组隐私机制。如果每个 在不相交的数据集子集上提供 差分隐私，则 将提供（，）差分隐私。平行组合表明当应用于不同数据集子集中的一组差分隐私，其隐私保护程度取决于 的最大值。问题描述假设数据所有者希望通过将特定于个人的数据发布给数据接受方来进行聚类分析。这些原始数据可以被定义为一组记录 ，每个记录（）代表一种具有 属性 ，的个人信息。假定每一种属性（）可以是分类的，数值的或集合值的，并且为每个分类或集合值的属性给出了分类树。在发布之前，应删除明确的标识符，例如名称和驾驶执照编号。聚类分析的任务是将对象分成若干组，使相似的对象在组中，不同的对象在不同的组中，聚类的结果可以用聚类结构来表示。定义 （聚类结构）设 是聚类的个数，数据集 ，的聚类结构被定义为一个矩阵 ，矩阵的每个元素 ，（，）代表了记录 到第 个聚类的聚类分配，也就是说，当，等于时记录 属于第 个簇，而当 ，等于时 不属于第 个簇。基于上述假设，有如下定义：定义 （聚类分析差分隐私异构数据）给定一个数据集 ，和隐私预算 ，对异构数据进 计算机应用与软件 年行聚类分析的匿名化问题是使数据集 使不同类型的属性上匿名化。例如：满足 差分隐私并且尽可能与 的聚类结构保持相似的匿名数据集 ，。异构数据发布方法 差分隐私的泛化算法首先，数据所有者在原始数据集 上使用一种聚类算法来确定初始的聚类结构，同一聚类中的记录有相同的聚类标签。与数据集 相比，标记的数据集具有 个属性 ，其中 表示类标签；即除了 中的原始属性 ，中的每条记录 也有一个类标签。因此，保存 的聚类结构意味着在匿名化过程中保留识别这些类标签的能力，然后通过在 上执行所提出的差分隐私算法来获取匿名数据集 。如果 不够令人满意，则数据所有者可以返回到第一步并且调整算法因子，即分类树、聚类算法的选择和聚类的数量。重复上述步骤直到得到效能满意的 。第四步，数据所有者将数据集 释放给数据接收者。为异构数据提出了一种称为 的差分隐私的泛化算法，该算法基于自上而下的专业化技术 。专业化从最一般的状态开始，然后通过将某些值替换为更具体的值来迭代下降，直到达到预定义的专业化数量。专业化过程就是根据相应的分类树，由表示将父值 （）替换为其直接连接的子值 （）。例如，图 中 （，），（），和 （），交替使用术语“子节点”和“子值”。在下文中，还将可以替换为其直接关联的子值的父值称为“”。图 为数据专业化过程。首先，将每个值都概括为图 所示对应的分类树上的最上面的值，并且初始值 为 ，。假设将 剪切以向下切割，然后由于 ，和当前 被更新为 ，。图 分类树示意图确保专业化过程满足 差分隐私的关键是确定匿名化的每一步都是差分隐私的。其关键步骤包括切割选择和划分记录。选择用指数机制来选择割集是因为该机制是为离散备选方案设计的。根据定义 可知，这个过程是需要效用函数的。另外采用属性与类标签之间的信息增益作为效用函数。这是因为切割上的每个专业化的过程中都倾向于通过生成特定的属性值来增加信息，并且信息增益能够基于这些值使类标签“更可预测化”。计算数据集 中属性值 的熵的方法为：（）（）（）式中：（）数据集 中的 属性域，是 中的一组数据记录，其中 的属性值可以一般化为 ，是包含类标签的数据集 的一组数据记录，是数据集的大小。一般化为其子值的属性值 的效用函数定义为：（）（）（）（）（）式中：（）是 的子值，并且 （）。（）的全局敏感度是 （），其 中（）是 属性域的大小。因为（）的取值范围是 （），（）（）的取值范围是（）。因此，无论是添加还是删除任何记录，（）的变化都不大于 （）。在每一次的专业化过程中，首先通过式（）完成每个割集候选的效用分数，然后根据指数机制有效地选择一个割以向下划分。使用上述分类树中的数据，根据式（）中 效用分数计算为：（）()（）()（）()（）（）（）（）与上述计算类似，（，），（），根据指数机制，、被选择为切割的可能性分别是 、和 。选择剪切后，原始记录分为不同的组。因为它们具有预定义的分类树，所以分类属性的划分策略是固定的。因此分类属性的分区函数的全局敏感性为 。根据当前选择的分类切割和相应的分类树，记录分区第 期高海燕，等：基于聚类结构编码的差分隐私异构数据发布 的步骤应满足差分隐私。与分类属性相比，集值属性专门化的区别在于子节点组合的存在。假设选择一个设定值 ，在它对应的分类树上有 个子节点。在 上的一般化将产生总共（）个子集。为了提高 的效率，应尽早地剪掉子集。由于差分性隐私需要不确定性，因此通过验证其噪声大小是否大于阈值，将其视为“非空”。也就是说，如果子分区的噪声大小大于阈值，则保留该子分区。否则，将其视为“空”，应该修剪。阈值可以由数据所有者控制。如文献 中所述，无须为数字属性提供分类树。如果选择了数字分割以向下分割，则在搜索分割的分割值时将动态生成或扩展其相应的分类树。不应为分割随机选择分割值，因为从不包含该值的数据集中选择相同值的可能性为 。这意味着对数值属性的分割值的选择是概率性的。再次使用指数机制，计算数字切割中每个属性值的效用得分，并使用指数机制选择属性值作为数字切割的分割值。选择属性值 作为数字割点 的分割值的概率定义为：（()）（）（()）（）式中：是隐私预算，是式（）的全局敏感度，（）（或 （）是 （或）的效用分数，（）是剪切 的属性值的集合。如果选择 ，）进行分割，我们将计算每个属性值在 到 范围内的效用得分，并且概率地选择一个值作为 ，）的分割值。考虑 类属性。然后，根据式（），（）计算如下：（）()，（）()，（）()（）（），（），（）在计算完所有的 （）后，式（）用于计算每个值被选作实际拆分值的概率。首先，为 数值属性初始化分割值，其中 是数值属性的数量。然后，针对每一轮专业化，概率性地选择切割。如果切割是设置值的，则应验证其非空子节点，以确定它们是否真的是“非空”；如果切割为数字，则为其选择分割值。请注意，这两种情况是互斥的。每个叶分区节点中的确切记录数不能直接发布，因为对于不同的数据，该数目可能不同。可以通过在每个节点中的记录数量上增加噪声来掩盖这种差分。隐私分析定理 满足 差分隐私。证明：通过指数机制为 个数字属性中的每一个初始化分割值。每一个指数机制的隐私预算成本为 ，因此根据顺序组成属性保证 差分隐私。使用指数机制选择要切割的切口，这一步就可以满足 差分隐私。通过拉普拉斯机制使用 隐私预算来对值进行割集产生“非空”分区节点。并使用指数机制来为新数值削减所产生的分割值。因此，如果削减是分类的，定值的或数字的，则一项专业化所需的隐私预算成本将分别为 或 。该算法最后通过拉普拉斯机制返回每组并记录模糊数量。这些步骤可保证 差分隐私。的每个不确定步骤都具有差分化隐私，并且总隐私预算不大于 。另外，由于具有顺序组成属性，因此可以满足 差分隐私。定理 时间复杂度为 （）。证明：为数值属性选择一个时间复杂度为 （）的分割值，其中 是输入的大小数据集。数值属性确定拆分值，其时间复杂度为 （）。通过遍历具有 属性，其时间复杂度为 （）的输入数据集，然后 无须遍历所有数据记录，而是根据为 中候选数据保留的某些信息来计算效用分数，因此相应的时间复杂度仅要求是（）。根据定义，从指数机制选择切割时，它的成本与离散切割的数量成正比。因此，基于概率选择算法的成本为（），其中 是 的大小，数值属性选择的时间复杂度为 （）的分隔值。通常 比 小得多。因此，循环迭代效能满意算法成本为 （）。其他计算均可以在恒定的时间 （）内被完成。因此，的总运行时间为 （）。实验与分析 实验设置与数据集所有的实验都是在一台 的 为英特尔酷睿 ，内存大小为 ，操作系统为 （位）的个人电脑上进行的。下面所给出的每个结果都是运行了 次以上的平均值。实验使用了两个公开的数据集，即 和 计算机应用与软件 年 。数据集包含人口普查记录，文献表明，该数据集已广泛用于测试匿名方法。在实验中，删除了类标签，并将此数据集用于聚类分析。为了综合一个异构数据集，假设一个人可以有多个职业，然后将具有相同属性值的记录组合到一条记录中，从而使职业属性为集值。为了综合处理，放弃了三个数值属性（即 、资本收益和资本损失），因为它们可能产生更少的异构记录。因此，保留了 条记录，这些记录具有 个分类属性、个数字属性和 个集值属性。为简化问题，将合成数据集称为 。第二个数据集 是医疗研究的重要公共资源。它由一些临床注释表组成，包括护理记录和出院摘要。具体来说，根据共享的 列将三个表连接在一起。然后，将相同 的多个 代码合并为一行。检索了 条记录，并选择了 个分类属性，即性别、婚姻状况、宗教、种族、入学类型，保险方式和入学来源和一个集值属性 代码。选择 均值和平分 均值仅包含一个算法参数，即聚类数 ，而不是考虑聚类参数的不同组合 。任何聚类算法都需要某种方法来测量对象之间的距离或相似性。因此介绍两个异构记录的语义距离度量。如果让、表示来自同一域的两个属性值，则 和 之间的距离计算如下：（，）（，）（）式中：（，）是 和 之间最短路径的长度，是相应分类法树的高度。归一化定义的优势在于，分类树的所有叶节点可以具有不同的深度。两个异构记录之间的距离，即 和，定义为：（，）（，）（）式中：是属性的数量，而（）是第 个灵活性属性的权重。在实验中，将所有（，）设置为相等。的目标是在保护可观数据实用性的同时保护原始数据集的私人信息。通过匿名前后的聚类结构的相似性来确定数据实用性。也就是说，匿名化前后的聚类结构越相似，匿名化数据集的效用就越高。在实验中，应用两个指标 和 评估两个聚类结构的相似性。考虑两个聚类结构 和 ，并将 中的每个聚类 视为“真实聚类”，并将 中的每个聚类 视为“预测聚类”。令 表示同时包含在 和 中的记录数，并且 表示聚类中对象的数量。和 的 、和 计算如下：（，）（）（，）（）（，）（，）（，）（，）（，）（）它测量聚类 预测的准确性，该预测基于 和 描述了真实的聚类。真实聚类 的成功预测是通过 的“最佳”预测聚类 来衡量的，即 的最大化 （，）。因此，加权最大 的总和用于评估 的质量，并且 的整体 计算为：（）（，）（）式中：是原始数据集 中的记录数。（）的范围是到。（）的值越大，比较的两个聚类结构越相似。如果两个保留在同一个聚类 中的记录在 中一起保存，并且 中不同聚类的两个记录被分在 中不同的聚类里则说明两个聚类结构 和 相同。对于每个聚类结构，都将生成一个方矩阵 （）来表示每对记录之间的关系。也就是说，如果第 个记录和第 个记录在同一聚类中，则 （）中的第（，）个元素等于 ；否则等于 。然后，定义 来表示 （）和 （）中出现的相同值的百分比：（），（），（）如果 （）和 （）中第（，）个元素的值相同，则 等于 ；否则，等于 ，并且 是原始数据集 中的记录数。的范围是到。的值越大，比较的两个聚类结构越相似。结果分析 数据实用性和隐私在该实验中，改变了隐私预算 ，专业化数目 和聚类数 ，以观察 和 。图 图 显示了 的结果。其中，图 （）显示了当 且 时，最小 为 。图 （）还显示当 且 最大 为 。从图 图 可以看出，与 相比，不同于 和 值的 值的跨度较小，大约在 范围内。有一个明显的趋势表明随着较高的 导致较少的干扰和较少的噪声，值随 的增加而增加。另外，和 也随着 的增加而增加，因为更详细的信息保留在用第 期高海燕，等：基于聚类结构编码的差分隐私异构数据发布 于聚类的匿名数据集中。但是，从一定的 开始，随着 的进一步增加，和 保持相同或减少。这是因为 的值越高，表示分区树中的叶子节点越多，并且叶子节点的数量越多，作用于这些叶子中的记录数的拉普拉斯机制产生的噪声越多节点。图 图 显示了 的 和 值的相似趋势，只有在获得最佳性能的情况下和 的值不同。这些结果表明，即使对于不同的匿名性要求，也可以在匿名化后保持原始数据集的相似聚类结构。（）效用（）效用图 均值 数据的效用（）效用（）效用图 均值 数据的效用（）效用（）效用图 均值匿名 的数据效用（）效用（）效用图 均值匿名 的数据效用 不同匿名化算法上的数据实用程序为了验证提出的聚类算法聚类质量是否比没有这倾向的一般差分隐私的聚类质量更好，在 工具中将本文的算法与（，）差分隐私进行了比较。（，）差分隐私是 差分隐私的松弛版本，因为前者允许以 为边界的错误概率。因为只有关系数据可以输入到 ，所以首先将异构的 和 转换为关系数据。具体来说，将为值属性集合的每个值创建一个二进制属性。例如，如果属性是值集合的并且具有 个值，即 和，则记录的模式将为“”“”或“计算机应用与软件 年”。此类转换仅对 执行，对 不执行。之所以为（，）差分隐私设置 和 ，是因为对于该工具，这两个值分别是最大和最小可接受值。将 的 固定为 。结果如图 所示。这些数字表明，在每个隐私预算上，的 值明显优于（，）差分隐私。例如，在图 中，即使 ，的 为 ，而 的 为 ，而当 时 和 的（，）差分隐私的 分别仅为 和 但是，值之间的差分较小。这是因为匿名前后位于不同聚类中的两个记录的情况也对 的值起了积极的意义。（）效用（）效用图 数据不同的 均值匿名算法（）效用（）效用图 对等分 均值的 匿名算法当 评估 工具中 相对于（，）的 改进时，还对 成对测试用例进行了一系列单尾 检验，证明 的改善在 时具有显著的统计学意义。从这些结果可以推出，提出的方法在聚类质量方面胜过了一般的匿名化方法。不同聚类算法上的数据实用程序在本实验中，研究了在数据接收者应用与数据所有者使用的聚类算法不同的聚类算法的情况下的数据实用程序。以两种不同的顺序应用了 均值和等分 均值，分别表示为等分 均值 均值以及 均值等分 均值。图、图 分别显示了匿名的 和 的数据实用程序。除了图 中 和 的情况外，所有 值均高于 。具体表现在，对于 和 ，最大的 值是 和 。的所有值均高于 ，和 的平均 值分别为 和 。（）均值聚类算法（）等类 均值聚类算法图 数据的不同聚类算法（）均值聚类算法第 期高海燕，等：基于聚类结构编码的差分隐私异构数据发布（）等类 均值聚类算法图 的不同聚类算法这些结果表明 即使使用不同的聚类算法，也具有良好的数据实用性。在这些不同实体聚类算法中使用的记录之间的距离度量应保持相同或相似。否则，由不同聚类算法产生的聚类结构可能完全不同。与 节中的实验结果相比，不同聚类算法上的数据效用可能不是很稳定。例如，在图 （）中，时 的平均值仅为 ，比 和 时的平均值小。该算法可能与其他聚类算法产生的结构不同，因为它们的搜索条件不同。可扩展性在可扩展性方面，将 与 中的（，）差分隐私进行了比较。与第 节中的实验相似，我们为（，）差分隐私设置 和 ，为 设置 。我们还固定了 并进行了 均值聚类。通过随机复制他们的记录，生成了多个版本的 和 。为了比较，图 显示了具有 至 条数据记录的 和 在 和 上的结果。可以看出，在运行时方面，比 更有效，因为 不考虑数据分析任务。在搜索数值属性的分割值时，将计算当前值范围内所有可能数值的效用分数。在拆分集值属性时，根据分类树考虑当前父节点的子节点的组合。通过维护和更新信息，而不是重复扫描所有数据记录，进一步提高了 的运行速度。而在 上花费的时间比在 上花费的时间更长。这是因为中有成千上万个代码，并且相应的分类树比 中的职业属性树大得多，这意味着选择代码属性进行拆分时需要更多的计算时间。图 两个数据集的可扩展性 的适应性。虽然在文中只使用了 均值和等分 均值来评估 的性能，但是其他的聚类算法，例如 ，可以集成到我们的方法中。提出的方法提供了一个灵活的框架，在这个框架中，聚类算法可以被视为“插件”组件。利用将聚类结果对原始数据进行匿名化处理，而并非一种聚类算法。然而，数据匿名化前后用于聚类的距离度量应该保持不变，或者至少相似，以获得更好的数据效用。否则，不同聚类策略所生成的聚类结构将会完全不同。同时，的关注点是在数据发布的前后保持聚类结构的相似性。如果原始数据不适用于聚类分析或者某些聚类算法无法产生好的聚类结果，那么 就无法帮助数据或其匿名版本生成更好的数据。结语本文介绍了一种用于聚类分析的异构数据发布方法。该方法利用聚类标签对聚类结构进行编码，并结合泛化技术和输出扰动来掩盖原始数据。通过分析实验结果可得如下结论：（）提出的方法即使对于不同的匿名性要求，也可以在匿名化后保持原始数据集的相似聚类结构。（）引入了差分隐私方法的聚类质量比未引入差分隐私的匿名化方法更高，说明差分隐私有助于聚类性能的提高。（）提出的方法提供了一个适应性较强的框架，可以结合不同的聚类算法，且都能够具有良好的数据实用。在这些不同实体聚类算法中使用的记录之间的距离度量应保持相同或相似。否则，由不同聚类算法产生的聚类结构可能完全不同。本文虽然分析了提出方法的有效性，但是缺乏与其他隐私数据发布方法的对比研究，对于该方法的实际应用也缺乏可行性分析，这些都是实验室下一步研究的重点。参考文献杜恒，杨俊成 基于拉普拉斯回归主动学习的大数据流分类算法 计算机应用与软件，（）：巫红霞，谢强 基于加权社区检测与增强人工蚁群算法的高维数据特征选择 计算机应用与软件，（）：王婷婷，龙士工，丁红发 大型社交网络的差分隐私保护算法 计算机工程与设计，（）：郑小乐 大数据环境下的数据安全研究 电子世界，（）：（下转第 页）计算机应用与软件 年 ：，：，：，：，：，：，：陆震寰，孔芳，周国栋 面向多语料库的通用事件指代消解 中文信息学报，（）：宦敏，程昊熠，李培峰 基于结构化表示的中文事件同指消解方法 中文信息学报，（）：中 国 民 用 航 空 局 民 用 航 空 安 全 信 息 管 理 规 定：北京：中华人民共和国交通运输部，中国民用航空安全信息系统 ：祝寒 基于事理图谱的航空安全事故因果关系研究 天津：中国民航大学，：，：，：，：，：，：，（）：，：，：（上接第 页），（）：，（）：，（）：，：，（）：郭庆，朱一凡，谢莹莹，等 面向大规模网络流量数据的实时汇聚查询关键技术研究 小型微型计算机系统，（）：王智远，陈榕，任崇广 基于集成学习的云平台异常点检测 计算机工程与设计，（）：霍东雪，刘辉，尚振宏，等 一种异构集成学习的儿科疾病诊断方法研究 计算机应用与软件，（）：，（）：，（）：王锟朋，高兴宇 基于附加间隔 特征的人脸聚类算法 计算机应用与软件，（）：王韫烨，孔珊 基于检测器集层次聚类的否定选择算法 计算机工程，（）：赵仁和，王军锋 自适应尺度的局部强度聚类图像分割模型 计算机工程与科学，（）：陈怡君，曹逻炜，杜玉倩 基于自步数据重构正则化的模糊 均值聚类算法改进 计算机与现代化，（）：