基于差分隐私的高效用项目集挖掘算法.pdf

书书书第 卷第 期太原科技大学学报 年 月 文章编号：（）收稿日期：基金项目：国家自然科学青年科学基金（）；山西省自然科学基金（）；太原科技大学博士科研启动基金（）作者简介：马煜（），男，硕士研究生，主要研究方向为大数据分析技术；通信作者：荀亚玲副教授，：基于差分隐私的高效用项目集挖掘算法马煜，荀亚玲（太原科技大学 计算机科学与技术学院，太原 ）摘要：在大数据时代，互联网安全事件频繁发生，用户数据安全性已成为大数据分析的热门话题。通过有效挖掘高效用项集获得的知识可能包含重要信息，如果被恶意滥用，可能威胁到数据拥有者的隐私或利益。为了防止数据信息泄露，提出了基于隐私保护的高效用项目集挖掘算法 （）首先在构建树的过程中，使用指数机制来混淆项头表的顺序，将拉普拉斯噪声添加到每个节点，从而得到差分隐私的树结构 最终进行高效用项目集挖掘。该方法以牺牲部分完整性为代价，大大提高了用户数据的安全性。实验结果表明，该方法的完整性损失在误差可接受的范围内，安全性能大大提升。关键词：高效用项目集挖掘；隐私保护；差分隐私；拉普拉斯机制；指数机制中图分类号：文献标识码：随着社会各领域数据的快速增长，用户面临着如何从数据海洋中挖掘出有价值信息的挑战。关联规则是数据分析知识的重要结构 ，通过在数据对象之间建立连接和关联来获取重要知识。传统的关联规则挖掘（）倾向于关注该商品是否出现在用户的购买历史中，以及同时出现在该商品购买历史中的其他商品，这样商家更容易链接到利润。因此，高效用项目集挖掘（）被提出，它不仅考虑要求信息的项目数量，还考虑效用价值，因此与传统 相比更具有决策价值。同时，一些不法分子可以从中提取出一些与利益相关的竞争信息，从而损害数据所有者的利益。因此，隐私保护效用挖掘（）已成为高效用项目集挖掘中的一个重要研究课题。传统的隐私保护方式有同态加密过程 、和 它们都可以在一定程度上保护数据不被泄露。但是在同态加密中，其加密和解密的过程需要消耗大量的计算资源，同时该方案受到每个密文都有噪声的限制，甚至使得密文变得十分困难；可以防止身份信息泄露，却不能防止属性泄露；当用户在元数据中有多个记录时 隐私原则无法防止隐私泄漏，敏感属性的性质决定了即使保证了一定概率的 也容易泄露隐私。而差分隐私 通过使用拉普拉斯机制和指数机制添加噪声，可减少个人信息泄露的风险，数据的可用性得到了很大的保证，在隐私和可用性之间取得了平衡。且差分隐私保护所添加的噪声量与数据集的大小无关，因此，在大规模数据集的情况下，即使只添加少量的噪声，也可以实现较好的隐私保护。本文结合差分隐私保护提出一种高效用项目集挖掘算法，主要贡献如下：给出一个树结构 （）来维护事务交易 项目及其效用信息，并提出了一种基于差分隐私的高效用项集挖掘算法 （）当数据为数值型时，采用拉普拉斯机制；当数据为序列型时，采用指数机制。实验结果表明，基于差分隐私的高效用项集方法可以有效保护高效用性项集的发布。相关工作 基于高效用模式集挖掘传统关联规则的挖掘方法只考虑项目集中项目出现的次数，而项目集的利润可能不同，等提出了一种依赖于紧凑的数据结构 ，采用了一种存储 项集之间关系的估计效用共现策略来提高计算速度。由于找到合适的最小效用阈值对用户比较困难，等提出了挖掘 高效用项集的高效算法 和 ，通过不设置最小效用阈值，能够有效地生成候选项集，从而获得所有高效用项目集。等提出 ，使用效用模式的树结构，用”模式增长”的方式挖掘。同时为了减少候选模式集的数量，该算法提出几种剪枝策略，以达到提高算法性能的目的。王晨等人提出了基于效用模式树的两阶段效用模式挖掘 算法 ，通过删除全局的非候选模式集和降低全局的各个节点的效用值，生成全局的条件效用模式树，进而生成高效用项集。等提出了 算法 ，是一种关于垂直结构的算法，其引入了两个新的剪枝策略，被称为划分效用剪枝和前向效用剪枝。黄坤等人提出一个新的基于差集的高效用项集挖掘方法 算法 ，其引入数据结构项集列表，项集列表只需要存储事务和效用信息。基于隐私保护的高效用模式集挖掘关于隐私保护效用挖掘（）的问题，引出了两种新的算法 和 来隐藏敏感项集，使其他用户不能从修改后的数据库中挖掘项目集。高效用项目集挖掘（）考虑数量和利润因素来衡量一个项目或项目集是否有利可图。隐私保护效用挖掘（）已经成为 的一个关键问题。对于隐藏敏感的高效用项集的问题，提出了一种新的算法，目的是减少挖掘过程中产生的副作用。隐私政策是为阻止数据所有者共享挖掘数据。文献为解决敏感效用的隐藏以及频繁项集的问题，提出了 和 两种关于数据清理的算法 ，其把敏感效用和频繁项集隐藏在修改后的数据库中。该算法不仅能隐藏敏感项集，也能清理数据库。提出了一种基于遗传算法的隐私保护效用挖掘方法 ，其目的是找到合适的事务插入到数据库中，从而隐藏敏感的高效用项目集。如何以更小的副作用隐藏高效用挖掘结果中的敏感高效用项集，保证用户在发布和共享数据时不会造成私密信息泄露。对此提出了基于竞争项分析的保护敏感项集算法 ，根据用户指定保护项来分析出敏感项集。在隐私保护的差分隐私背景下，挖掘结果的有效性已成为我们目前关注的一个重要问题。文献 以频繁挖掘模式（对象集、序列和子图）考察了三个最重要的对象，深入的探讨了满足差分隐私的频繁挖掘问题。文献 提出了一个有效的（，）隐私原则，通过此原则隐私得到了有效地保护。在这个原则的基础上，改进之前的隐私算法并且提出了一个可以满足这类型隐私原则的算法。综合上述分析，本文提出基于差分隐私的高效用项目集挖掘算法 （），数据拥有者使用差分隐私技术在数据发布的过程前对数据进行隐私保护，数据分析者在基于差分隐私上的树结构进行高效用项目集挖掘，使得数据可以抵御任意形式的攻击。差分隐私的高效用模式树 相关描述给定一组有限的项 ，每个项目 （）有一个单位利润 （）项集 是 个不一致项 ，的组成的，其中 ，是 的长度 长度为 的项集称为 项集。一个事务数据库 ，中包含一组事务，其中每个事务 （）都有唯一的标识符，叫做 交易 中的每个项目 都和一个数量 （，）相互关联，即在 中 为购买的数量。太原科技大学学报 年差分隐私常用的两种机制是：拉普拉斯机制和指数机制。一个数据集的实例如表 所示。表 表示了每一项对应的外部权重即利润。表 示例数据库 商品交易列表（，）、（，）、（，）（，）、（，）、（，）、（，）（，）、（，）、（，）（，）、（，）、（，）（，）、（，）、（，）、（，）（，）、（，）、（，）、（，）表 利润表 项目利润定义 （项目效用）在事务 中，交易中一个项目的效用表示为 （，），定义为：（，）（）（，）（）例如，表 中 （，）定义 （项目集 的效用）事务 中项目集的效用表示为 （，），定义为：（，）（，）（）例如，表 中 （，）定义 （事务效用）事务 的事务效用表示为 （），定义为：（）（，）（）例如，表 中 （）定义 （数据库总效用）事务数据库 的总效用就是所有事务效用的总和，定义为：（）（）例如，表 中 定义 （事务加权利用率）一个项目集的事务加权利用率表示为 （），定义为：（）（）（）例如，表 中 定义 （剩余效用）数据库的总效用表示为时间单位，定义为：（，）（）例如，表 中 （）定义 （最小项目效用表）事务 中的事务最小效用值记作 ，以维护所有全局有希望项目的最小项目效用，定义为：（）（）（）例如，表 中 （）（，）定义（最小效用阈值）设 表示由用户设定的百分值，那么最小效用阈值表示为 ，定义为 例如，用户设定的 为 ，那么 定义 （高效用项集）给定项集 及用户指定最小效用阈值 ，若 （），则称项集 为高效用项集 如果若 （），则称项集 为低效用项集，那么它的超集不可能是高效用项集。定义 （机制）给定数据集 ，通过在查询结果添加关于拉普拉斯的噪声，那么随机算法（）（）提供 差分隐私保护，其中 （）服从尺度参数为 的 分布，公式如下：（）（）（）定义 （指数机制）设随机算法 的输入为数据集 ，输出的查询函数范围为 ，（，）为可用性函数，函数 （，）的敏感度是 ，若函数以正比于 （，）的概率从 中选择输出 ，那么算法提供 差分隐私保护，公式如下：（，()）（）算法描述及实例分析 （）该方法的框架由三部分组成：（）构造 （）结构，使用指数机制混淆项头 表顺序，建立树的过程为每个节点添加拉普拉斯噪声；（）通过算法 从生成的树结构 获得候选高效用模式集；（）从候选高效用模式集中识别真正的高效用模式。基于差分隐私的高效用项目集挖掘方法步骤如下：第一步：首先对数据库进行第一次扫描，根据定义 、和 计算事务效用 、事务加权利用率第 卷第 期马煜，等：基于差分隐私的高效用项目集挖掘算法 和最小效用表 如果一个项的 小于最小效用阈值，那它的超集不可能是高效用项集，丢弃且更新 表 项目及其 项目 假设事务数据库最小效用阈值为 ，从表 可以得到，项目 的 为 ，根据定义可知 （），那么它的超集不可能是高效用项集。这个项目被称为没有希望的项目。由于 是没有希望的项目，则从事务 中删除没有希望的项 并且在 、的 消除了 效用。事务中剩余的有希望的项 、和 按 的降序排序，如表 表 数据库，及新 ，商品交易列表 （，）、（，）、（，）（，）、（，）、（，）、（，）（，）、（，）（，）（，）、（，）（，）、（，）、（，）、（，）（，）、（，）、（，）、（，）表 项目及其 项目 第二步：使用指数机制对项头表（）顺序进行混淆。伪代码如下：算法 混淆顺序，并创建项头表输入：交易加权利用率 ，最小效用阈值 输出：混淆项头表：（）：，：第三步：建立 ，建立树的过程为每个节点添加拉普拉斯噪声（）伪代码如下：算法 添加拉普拉斯噪声输入：节点值输出：噪声节点：（，）：（）：（）：考虑表中重组的事务 当 （，）（，）（，）被插入到 时，第一个节点 被创建。的增加是通过 的 减去 中 项后面的剩余项的效用，即 （）（，）（，）第二个节点 是 子节点。计数 和 （）（，）（）（，）同理，第三个节点 由 创建。当 （，）（，）（，）（，）插入到树中的时候，增加（）（，和 的计数增加到 然后，在带有 的节点 下创建一个新节点 计数 和 同样，在节点 下创建一个新节点 的计数 和 在插入所有重组的事务之后，被完全构建。如图 所示树结构。$&%#(%(%$&#%(5 86 图 结构 第四步：从树中挖掘潜在高效用模式，构造当前节点的条件模式基，并对其进行分析。如考虑 的条件模式基。太原科技大学学报 年表 显示了 中的本地项目及其路径效用。在表 中，标识了一个本地不太可能的项目 在对 进行第二次扫描时，本地不太可能的项目 将分别从路径 ，中删除。的效用为 ，的效用为 如果 （，），则项 在 中称为局部希望项；否则，被称为本地没希望的项目。表 路径 路径支持度路径效用值 ，第五步：根据重构后的事务数据库的事务项集，从候选高效用模式集中选择真正的高效用模式。表 重构后的事务数据库 商品交易列表（，）、（，）、（，）（，）、（，）、（，）、（，）（，）、（，）、（，）（，）、（，）（，）、（，）、（，）、（，）（，）、（，）、（，）、（，）从 生成高效用模式集，得到一组高效用项集，即：、实验结果及分析 实验环境及数据集为检验 算法的性能，将其与将经典的挖掘算法 和现有算法 进行比较。实验平台：实验所使用的系统是 位的 ，为英特尔 处理器，内存 实验数据集：实验中使用了 个标准的数据集 、，数据密度分别为 ，这个数据集的数据特性如表所示，其中包括：交易总数；同项目的数量；平均交易长度；最大交易长度。实验中 个数据集都没有提供对应的数量和单位利润 在这里，以产生随机数据的方式生成项在事务中的数量和单位利润数据。表 数据集的特征 数据集交易总数同项目的数量平均交易长度最大交易长度 实验结果的分析 算法的运行时间实验本实验主要测试在不同最小效用阈值时算法运行时间的对比，在数据集 和 进行实验。在相同的最小效用阈值下的运行时间。N J O V U M T6 1 (S P X S I%)6*%1 6 1 (S P X S I图 数据集 6 1 (S P X S I%)6*%1 6 1 (S P X S IN J O V U M T图 数据集 在如图 和图 中可清楚看到，随着最小效用阈值逐渐降低，候选高效用项集的个数逐渐增多，因此，组算法的运行时间均增长，算法和 算法运行时间相差不大，但优于 因为 算法和 都是以项的 值降序进行排列，这种排列能够减少搜索空间的范围，从而加快算法速度。数据发布的运行时间实验发布时间是数据所有者完成数据加密并交付给数据分析者的执行时间。本组实验通过改变数据集的大小来对比发布时间的变化。第 卷第 期马煜，等：基于差分隐私的高效用项目集挖掘算法实验过程中随机选择数据集 和 交易总数，如 ，和 条，在相同的最小效用阈值时，通过数据交易总数的变化进行算法发布时间分析。根据图 和图 可以看出：随着发布数据集总数越来越多，各算法运行时间也逐渐增加。算法和 算法运行时间相差不大，但是优于 因为发布的数据集总数越多，运行时间越长。数据集的密度越小，三个算法运行时间就越相近。6 1 (S P X S I%)6*%1 6 1 (S P X S I T图 数据集 6 1 (S P X S I%)6*%1 6 1 (S P X S I T图 数据集 挖掘结果的准确性实验在数据集 和 进行实验，以对比 和 两种算法的数据完整性。以 算法挖掘出高效模式集为原始数据，即其数据完整性为 其中，是以 算法挖掘出高效模式集，是其他算法挖掘出的高效模式集。从图 和图 可以看出：在两个数%B U B *O U F H S J U Z%)6*%1 6 1 (S P X S IN J O V U M 图 数据集%B U B *O U F H S J U Z%)6*%1 6 1 (S P X S IN J O V U M 图 数据集 据集的完整性分别维持在 和 左右。由于完整性在可接受范围内，算法有效增加了用户数据的安全性，有利于对数据的保护。因为在数据集 的数据密度和平均长度都高于 ，数据更为集中。总结与展望本文提出了一种基于差分隐私的高效用项目集挖掘方法，该方法安全性能大大提高，均衡了准确性和效率。实验结果表明，本文提出的差分隐私 发布方法在效率方面与没有差分隐私相差无几，完整性在误差可接受范围，对原始数据集起到很好的保护作用，防止被不法分子直接利用。由于数据是不断发生变化的，可以从动态数据集中提取最新的有价值的信息。另一方面，由于数据量爆炸式的增长，现阶段的单机计算资源需求已经不能满足用户要求。因此，分布式计算与增量挖掘技术和高效用模式集挖掘的结合得到了人们的广泛关注。太原科技大学学报 年参考文献：，（）：，（）：程帅，姚寒冰 基于同态加密的密文全文检索技术的研究 计算机科学，（）：，（）：，（）：，：，（）：，（）：，（）：，：，王晨，杜义华，卢景秀，等 基于效用模式树的高效用频繁模式挖掘算法 计算机应用，（）：，（）：黄坤，吴玉佳，李晶 基于差集的高效用项集挖掘方法 电子学报，（）：，：，（）：，（）：，（）：林果 高效用隐私保护数据挖掘的研究 哈尔滨：哈尔滨工业大学，许胜之 满足差分隐私保护的频繁模式挖掘关键技术研究 北京：北京邮电大学，：（，），（，）（下转第 页）第 卷第 期马煜，等：基于差分隐私的高效用项目集挖掘算法 石炜，张袁祥 轴承缺陷图像二值化处理及形态学边缘检测 舰船电子工程，（）：胡天赐，罗潇远，王思博，等 遥感图像的分割与提取 中国科技信息，（）：石海杰 基于 与 的时频分析方法 硅谷，（）：（），：胡旭超，谭贤四，曲智国，等 基于 信号的风轮机叶片回波模型与分析 计算机仿真，（）：吴贞宇，夏厚培 基于 的混叠多分量 信号时域参数测量 电子科技，（）：朱晓坡，徐仕源，张卓，等 一种多目标水下定位系统信号处理算法 国外电子测量技术，（）：，（，）：，：，檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲檲 （上接第 页）：，（），：，第 卷第 期 张亚斌，等：基于 的二值化融合分析方法研究