王 茜，张鲲鹏

(重庆大学计算机学院，重庆 400044)

近年来随着数据挖掘技术的发展，数据隐私保护逐渐引起人们普遍的关注［1－2］。Rizvi S J等［3］于 2002年提出了基于随机扰动的 MASK(mining associations with secrecy konstraints)算法。该方法很好地解决了在保持高度隐私的同时获得较为准确的挖掘结果的问题，但该算法运行的时间效率较低。武振华等［4］在此基础上改进了MASK算法。称之为XMASK算法［4］，该算法利用分治策略简化求解逆矩阵的过程，从而提高了算法的运行效率。本文提出一种基于XMASK算法的改进算法。复杂度分析和实验结果都表明本文提出的算法在保证隐私度和准确度不变的同时明显提高了运行的时间效率。

1 MASK算法和XMASK算法

MASK算法由Rizvi提出。假定数据集为超市购物数据篮，所挖掘的数据集可以看作由0和1组成的二维稀疏布尔矩阵，1表示购买某件商品，0表示没有购买。为了保护输入数据集的隐私性，MASK算法采用概率歪曲的方法对原始数据集进行扰乱操作。一个0－1数据库元组可以看成一个随机向量X={Xi}，Xi=0或者1。对Xi进行歪曲操作得到 Yi=XiXOR，其中是 ri的补，ri是满足贝努利分布的随机变量，分布律p(ri=1)=p，p(ri=0)=1－p。由异或计算的特点可知随机向量X经过歪曲操作后，第i个分量Xi保持原值的概率为p，取其相反值的概率为1－p。

MASK算法所挖掘的数据集是真实数据集经过概率变换形成的，所以需要重构项集的真实支持度。设真实数据集对应的矩阵为T，T经过歪曲变换后得到的矩阵为D，歪曲概率为p。T的第i列中1的个数记为，0的个数为，D中第 i列中1的个数为，0的个数为。……