基于本地化差分隐私保护的频繁项目挖掘算法

频繁项目挖掘是数据挖掘的研究热点之一,若数据集包含敏感信息,不作处理地发布挖掘结果会有隐私泄露的风险。目前已有本地化差分隐私的频繁项目挖掘算法,但还无法满足处理大数据时的实时性和数据可用性要求。针对这些问题,该文提出了一种新的面向本地化差分隐私保护的频繁项目挖掘算法—GFIM(group-based frequent items mining)。该算法把用户随机划分为不相交且大小相等的两组用户,整个运行过程分为两个阶段。第一阶段主要根据全部用户提交的信息挖掘出频繁项目的候选集C,而在第二阶段,两组用户分别通过设置冗余项把自身修剪为O(k)发送给数据收集者,最终的top-k频繁项目将利用上述两个阶段的结果。采用分阶段的思想减少了计算时遍历数据集的次数,加快了整体的运行速度。通过理论证明了该算法满足ε-本地化差分隐私,在多个真实数据集上的实验也验证了该方法的性能。

最小支持度变化时分布式数据库中频繁项目集更新

讨论分布式数据库系统中最小支持度变化时频繁项目集如何高效更新问题,提出了一种基于最小支持度变化的局部频繁项目集的更新算法ULFS和全局频繁项目集的更新算法UGFS.该算法能够充分利用已挖掘的结果,并且产生较少数量的候选频繁项目集,在求解全局频繁项目集过程中,候选局部频繁项目集支持数的通信量为O(n).将文章提出的算法用Java加以实现,并对算法性能进行了研究.实验结果表明这些算法是可行、有效的,并且具有较快的速度.

基于位存储Tid的CPU并行化Eclat算法

Eclat算法采用垂直数据表示方式且无需复杂的数据结构,然而在挖掘频繁项目集过程中,交集计数的生成方式造成内存大量消耗和挖掘效率下降。为此,在分析Eclat算法及其现有改进算法基础上,提出一种位存储事务标识(Tid)的CPU并行化Eclat算法。该算法使用二进制位形式存储项目的 Tid,将挖掘频繁项目集的任务分配到CPU各个线程,最大限度地提高CPU的运算性能。实验结果表明,该算法能在降低内存使用的同时,提高频繁项目集的挖掘效率。