论文部分内容阅读
数据挖掘技术因为能够从海量数据中获得潜在的、正确的、有价值信息而成为研究热点。关联规则挖掘是数据挖掘的核心研究分支之一，而频繁模式挖掘作为关联规则挖掘的一个关键步骤，更具有研究价值。然而屡次发生的隐私泄露事件，给数据挖掘中的隐私保护带来极大的威胁，由于添加了隐私保护，挖掘效率已经成为大多数隐私保护的频繁模式挖掘算法的瓶颈。因此，提高隐私保护频繁模式挖掘算法的效率成为迫切需要解决的问题，并且数据库的少量更新都需要重新运行原算法，往往会造成之前挖掘结果极大的浪费，必须在挖掘算法中加入更新模型以提高其效率。
本文针对隐私保护的频繁模式挖掘算法的效率问题展开研究工作，通过深入分析制约隐私保护的频繁模式挖掘算法效率的因素，研究提出了改进算法，主要成果如下：
1）针对BEMASK算法在候选集数量成千上万时，位与运算和庞大的子集计数会消耗大量时间和系统内存的问题，提出了PBEK(partition and bitmap based efficient MASK)算法。该算法主要采用划分和先验约束的方法。将数据库D划分成均匀的非重叠小块，在每个小块上运行BEMASK算法，并利用先验约束的方法，缩减后续小块中局部频繁项集的数量，从而达到扫描全局bitmaps，高效产生全局频繁项集的目标。实验结果表明，改进算法PBEK比原算法BEMASK具有较高的效率。
2）针对顾城等改进的RRPH算法(GRRPH)在运行过程中需要多次数据库扫描以及计数时多次比较的不足，提出了BRRPH(bitmap based randomized response with partial hiding)算法，该算法采用bitmap技术表示数据库中的事务，实验结果表明BRRPH算法比GRRPH算法具有更高的效率；针对数据库允许的频繁或者偶尔的新增会使得一些现有的强关联规则无效或者弱规则变为强规则的问题，引入了增量更新模型，提出IBRRPH算法,实验结果表明改进之后的算法IBRRPH在处理数据库发生变化时比原算法具有较高的效率。
本文针对隐私保护的频繁模式挖掘算法的效率问题展开研究工作，通过深入分析制约隐私保护的频繁模式挖掘算法效率的因素，研究提出了改进算法，主要成果如下：
1）针对BEMASK算法在候选集数量成千上万时，位与运算和庞大的子集计数会消耗大量时间和系统内存的问题，提出了PBEK(partition and bitmap based efficient MASK)算法。该算法主要采用划分和先验约束的方法。将数据库D划分成均匀的非重叠小块，在每个小块上运行BEMASK算法，并利用先验约束的方法，缩减后续小块中局部频繁项集的数量，从而达到扫描全局bitmaps，高效产生全局频繁项集的目标。实验结果表明，改进算法PBEK比原算法BEMASK具有较高的效率。
2）针对顾城等改进的RRPH算法(GRRPH)在运行过程中需要多次数据库扫描以及计数时多次比较的不足，提出了BRRPH(bitmap based randomized response with partial hiding)算法，该算法采用bitmap技术表示数据库中的事务，实验结果表明BRRPH算法比GRRPH算法具有更高的效率；针对数据库允许的频繁或者偶尔的新增会使得一些现有的强关联规则无效或者弱规则变为强规则的问题，引入了增量更新模型，提出IBRRPH算法,实验结果表明改进之后的算法IBRRPH在处理数据库发生变化时比原算法具有较高的效率。