差分隐私下的频繁模式挖掘算法研究

作     者：卢国庆 

作者单位：中国科学院大学 

学位级别：硕士

导师姓名：丁丽萍

授予年度：2015年

学科分类：0839[工学-网络空间安全] 08[工学] 

主      题：网络安全 频繁模式挖掘算法 差分隐私技术 数据挖掘 机器学习 

摘      要：当今我们生活在数据时代。通过数据挖掘和机器学习能够从数据中获得大量有价值的知识。与此同时，数据亦是危险的“潘多拉之盒，一旦泄漏用户的隐私将被侵犯。如何保护隐私数据成为当前面临的重大挑战。 差分隐私作为一种新的隐私保护技术，定义了一个相当严格的攻击模型，通过添加噪音使数据失真达到隐私保护的目的，能够防止攻击者拥有任意背景知识下的攻击。实施差分隐私主要考虑两个方面的问题:(1)如何保证设计的算法满足差分隐私，以确保不泄露隐私;(2)如何减少数据失真带来的误差，以提高数据可用性。 目前差分隐私的应用研究主要集中在两个方向:数据发布和数据分析。频繁模式挖掘是一项重要的数据挖掘任务，是数据分析的基础。然而，频繁模式本身和相应计数信息都有可能泄露用户的隐私。差分隐私下的频繁模式挖掘算法研究，主要考虑在保护频繁模式本身和相应计数信息不被披露即满足差分隐私的同时，如何提高数据的可用性。 本论文主要取得了以下两个方面的成果: 1.分析了差分隐私下的频繁模式挖掘算法研究。根据模式类型的不同，从频繁项集挖掘、频繁序列挖掘和频繁子图挖掘三个方面对现有的差分隐私下的频繁模式挖掘算法研究进行了分类整理，理清了研究现状，同时指出了有待解决的问题，为后续研究奠定了基础。 2.提出了一种满足差分隐私的频繁序列模式挖掘算法。序列数据内在序列性和高维度的特点，给差分隐私应用于频繁序列挖掘带来了挑战。对此提出了一种基于交互式差分隐私保护框架的频繁序列模式挖掘算法Diff-FSPM。该算法利用指数机制获取最优序列长度，并采用一种维规约策略获得原始序列数据集的规约表示，有效降低序列高维度的影响;应用前缀树压缩频繁序列模式，利用拉普拉斯机制产生的噪音扰动频繁模式的真实支持度计数，同时采用闭频繁序列模式和马尔可夫假设，有效分配隐私预算，并利用一致性约束后置处理，增强输出模式的可用性。理论角度证明算法满足ε-差分隐私，实验结果验证算法具有较好的可用性。