基于K-means 方法的MapReduce 模型社交网络隐私保护研究

张娱嘉,张景璐

(1.智己汽车科技有限公司,上海 201210;2.北京电子科技职业学院,北京 100176)

0 引言

使用各种软件工具和算法对大量数据进行抓取和处理是现代常见的获取信息途径。 其中聚类分析是一门重要技术,把相似的对象通过静态分类的方法分成多种组别和子集,每种子集具有相似的特征和属性,作为一种非监督性学习,聚类分析可以有效处理数据挖掘、模式识别,图像分析、网络入侵检测、大规模定位和市场细分等领域的问题。

针对内容的聚类分析和数据挖掘等技术的应用中,存在两个问题,首先是信息的收集与处理需要考虑到隐私保护问题,包括个人的重要身份信息,利用这些信息可能直接或者间接追溯到具体的个人,另外数据挖掘提供有价值信息的同时还可能泄露团体的行为等敏感信息,要在发布信息时确切保护好用户个人权益,就需要用差分隐私保护。

其次是庞大数据量带来的效率问题,对海量混杂的大数据进行相关性查找和模式分析时,单个计算机难以保证时间和效率,可以用并行的分布式计算。

聚类分析将未标记的数据集划分为簇,最广为使用的算法即是Lloyd’s algorithm,也称为K-means,Kmeans 需要选择的参数较少,只需要选择的参数是K,也就是所需要的簇数和速度,使用分布式计算的MapReduce 框架来实现K-means[1]。 本文提出一种基于MapReduce 的K-means 差分隐私保护法,应对多种背景下的恶意分析。

1 差分隐私保护

定义相邻两个数据集,若存在两个数据库名为D和D’,在两个数据库中,有n条数据,状态为1 或者0(ai= 1 或者0),这些数据形成一个集合{a1,a2,a3,...,an},这两个集合就是相邻集合。 定义一个随机算法A,对同样的输入,该算法的输出不是固定值,而是服从某一个分布,这个算法分别作用于上述两个相邻数据集,得到的两个输出分布会变得难以区分,所以差分隐私形式化的定义为:

Pr{A(D)=O} ≤eℓPr{A(D＇)=O}

当算法A 作用相邻数据集后,最终得到输出O 的概率相差较小时,可以认为这个算法能达到差分隐私的效果,这样观察者仅仅通过观察数据处理结果,很难找出具体某条数据的变化,从而保护数据集的隐私问题。

从两个数据集的拉普拉斯随机分布图看,在lamda为0.5,数据集A 值为-5,5,数据集B 为-4,5 的情况下,两个laplace 分布呈现如图1 所示的结果,保护隐私的目的需要使两个分布尽可能接近。

图1 数据集的Laplace 分布

Pr{A(D)=O}≤eℓ·Pr{A(D＇)=O}+δ,δ是一个较小的常数,使用高斯噪声(Gaussian noise)就可以。新的常数加入,最终结果不可避免会不准确,在数据量较大时噪声的影响比较小,否则就会导致结果偏离准确值,需要将δ设置成较小数值。 目标是在更少的隐私预算下得到相同的噪声尺度。

2 MapReduce 框架下的DP K-means 算法

K-means 每次迭代分为两个阶段,第一是去计算最接近均值μi的点的集合Si,第二是将这些新均值作为这些集合的质心,这两个阶段分别是MapReduce 算法的Map 和Reduce 阶段。 Map 阶段对数据集中的每个点x 进行操作。 最小化这个给定的x 的距离,计算x和每个平均值之间的平方距离,找到最后的平均值μi,发出一个键值对,索引i 作为键,值是(x, 1)。 函数是:

如图2 所示,假如相邻数据A 与数据集B 的数据差分是数据n,对两个数据集完成一系列查询操作后,获得结果1 和结果2,那么比对相邻数据集A 和B 的差分和两个结果1 和2 之间的差分,就可以明确得知研究对象n的具体数据,如果有外部观察者试图破解结果,只能知道数据集B 与数据集A 相差n 条记录,收集结果进行分析后,分析者也无法得到单个记录的信息。 所以MapReduce 框架下的K-means 算法,可以有效防止攻击者因为简单的查询操作而获得新的信息[4]。

图2 差分隐私算法应对的攻击模式

3 算法设计

4 可用性实验

为了验证新的Map-Reduce 模型进行保护差分隐私的有效性,选择“Blood”和“Gramma”数据库来进行验证,关注的两个标准是召回率和精确率。 F-measure可以整合召回率和精确率,用F-measure 来证明集群可用性。 F-measure 越大,两个聚类结果的相似性越强,添加噪声的算法对聚类的影响很小[8]。 将f 方法和标准数据集之间的相似性写为 F1,去对比方法和作为F2之间的相似性[9]。 运行过程中,增加的噪声服从拉普拉斯随机分布,结果具有随机性。

5 结语

本文利用基于MapReduce 的K-means 方法来实现差分隐私保护,在MapReduce 的框架下,并行计算聚类,最终利用Laplace 的机制实现差分隐私保护,同时提高了这个算法的效率和隐私性。