论文部分内容阅读
在数据流上进行频繁模式挖掘是数据挖掘领域的一个研究热点,然而很多方法研究的是单数据流,其中每条事务是独立的,不考虑某些事务由相同个体产生。在现实生活中,许多应用涉及到多数据流,每个用户对应于一条数据流,令人感兴趣的对象往往是最近发生并且出现在许多数据流中,如新兴主题发现、网上购物分析、Web使用模式挖掘和基于位置的服务等。对多数据流进行研究与共享可以极大的推动社会的发展,因为这些数据通常包含了当前的热点数据,政府可以利用这些统计结果进行民生调控与经济规划,或者用于科学研究,商业公司可以用这些统计数据进行商业推广与商业开发。但是这些数据往往也包含个人信息,如果未经任何处理就直接发布统计数据便会造成个人隐私泄露。差分隐私是一种有效的隐私保护技术,它具有严格的数学定义,且不需要假定攻击者的背景知识,已广泛应用于各种数据发布场景。基于差分隐私的频繁模式挖掘是数据挖掘和数据安全领域交叉的研究热点,然而已有的频繁模式差分隐私方法主要针对静态数据集,并且存在的数据流差分隐私方法主要针对数值或分类值数据,尚未有研究考虑多数据流上共生模式挖掘造成的隐私泄露问题。本文分析多数据流中单一窗口和连续窗口发布闭合共生模式带来的隐私泄露问题。为了解决这些问题,提出多数据流闭合共生模式挖掘的差分隐私保护方法。本文的主要研究工作如下:1)对数据流频繁模式挖掘、静态数据差分隐私频繁模式挖掘和数据流上差分隐私数据发布方法进行了综述和分析,讨论现有的工作不能直接应用于多数据流闭合共生模式的挖掘,并指出本文方法与现有方法的不同。2)讨论多数据流闭合共生模式挖掘方法在单个窗口和连续窗口发布top-k闭合共生模式存在的隐私泄露问题,指出连续时间戳发布闭合共生模式增强了攻击者的推理能力,仅需少量的背景知识就能推测出用户的隐私,因此连续窗口发布更容易泄露用户的隐私。3)提出多数据流top-k闭合共生模式挖掘的差分隐私保护方法DP-TCPM(Differentially Privacy Top-k Closed Co-Occurrence Patterns Mining Algorithm),该方法包含差异计算阶段和差分隐私挖掘阶段。差异计算阶段将上一次已加噪的闭合共生模式与当前待发布的真实统计数据进行对比,根据对比结果判断是否进入差分隐私挖掘阶段。差分隐私挖掘阶段包括通过事务分割调整共生模式图、利用指数机制扰动共生模式图、top-k闭合共生模式挖掘和对挖掘出的模式支持度进行加噪四个部分。同时对算法的时间复杂度进行分析,并证明算法满足差分隐私。4)在三个真实数据集(OnlineRetail、BMSWebView2和Foodmart)上进行大量的测试。由于缺乏直接对比的方法,本文提出一种完全扰动共生模式图的差分隐私保护方法FPCG(Differential Privacy Method Based on Fully Perturbation for Edges in CP-Graph)。选择F-score、平均相对误差和运行时间三个指标对提出的算法进行评估,实验结果表明本文的方法具有较好的效用性和有效性。