《Spark框架下保护数据差分隐私的遗传聚类算法》-工学论文，计算机论文-论文范文参考-科学狗论文网

标题

Spark框架下保护数据差分隐私的遗传聚类算法

范文

张玉婷

摘要：针对分布式计算框架下海量数据聚类分析过程中的数据隐私泄露问题，提出了一种Spark下支持差分隐私保护的遗传k-means聚类算法。首先利用遗传算法实现对k-means聚类方案的全局寻优，提高算法的准确率；并采用种群迁移策略将遗传k-means算法部署于Spark框架中，实现基于内存读写的分布式聚类；然后利用差分隐私保护的Laplace机制在Spark每轮迭代的mapvalues算子中，对各聚簇中记录数量num和聚簇中各记录之和sum上添加随机噪声。根据差分隐私保护的性质，通过理论分析证明了算法达到ε-差分隐私保护要求。最后实验分析表明了算法在Spark框架下的时效性高于MapReduce框架，其运行时间主要受迭代次数的影响，并且得出了使算法隐私性和准确性达到平衡的最优隐私保护预算取值。

关键词：数据分析；k-means聚类；Spark框架；差分隐私；遗传算法

中图分类号：TP309.7 文献标识码：A 文章编号：1009-3044（2019）04-0198-03

1 引言

在大数据时代，数据挖掘技术得到了广泛的应用，聚类分析作为一种常用的无监督数据挖掘技术，可以将相近的数据划分到同一个类簇中，在网络入侵检测、目标识别等领域应用十分广泛。k-means算法由于运算速度较快，实现原理简单，所以成为应用领域最广泛的聚类分析算法之一[1]。

本文提出一种Spark框架下满足差分隐私保护的遗传k-means算法（IGKM，Improved Genetic K-Means），利用遗传算法解决k-means算法容易陷入局部最优的问题，利用基于内存计算的Spark分布式框架，利用Laplace机制实现差分隐私保护，为应对任意背景知识恶意分析的高效聚类分析提供了一种解决方案。

2 差分隐私保护基础

差分隐私方法能够解决任意背景知识下非法分析的问题[2]。

3 Spark框架下的DP-IGKM算法

Spark下的DP-IGKM算法实现目的是在Spark分布式框架下，当数据中的某一条记录改变时，聚簇的中心点和记录总数的变化情况不会暴露数据隐私。

3.1 IGKM算法设计

Step1：种群初始化：用聚簇中心的特征取值对染色体编码。具体方法如图1。

NK为聚簇数量，vki为第k个聚簇中心点的第i个特征取值（k[∈][1， NK]）。随机选择样本集中的样本作为聚簇中心，重复M次，使用于进化的种群规模达到M。

Step2：k-means聚类

k-means聚类具体分为两个步骤：①计算各条记录与聚簇中心点间的距离关系，将各记录分配到具体它最近的中心点所在的聚簇中；②对于新形成的聚簇，计算聚簇中各记录中各维特征的平均值，形成新的聚簇中心。

Step3：遗传操作

遗传操作包括选择操作、杂交操作和变异操作。

Step4：循环终止准则设定

当算法当前的循环次数为预先设定的最高次数时，循环终止。否则，重复Step1～Step3。

3.2 Spark框架下的IGKM算法设计

采用基于内存的分布式计算框架Spark。在基于Spark的IGKM算法中，本质是利用RDD中的各Partition存储子种群，然后在子种群内进行染色体的更新。

Spark框架下的IGKM算法流程如图2所示。

图2中各算子所实现的具体操作如下。

（1）textFile算子：从分布式存储框架HDFS中读取编码后的染色体数据文件，每个染色体代表一个聚类方案。

（2）partitionBy算子：将RDD中的数据重新分区成QS个新的Partition，每个Partition存放一个子种群中的染色体数据。

（3）mapValues算子：对各Partition中的染色体数据逐条进行操作。

（4）groupBy算子：用key作为染色体所属于的子种群标识，形成P个新的Partition。

（5）mapPartitions算子：完成选择、杂交和变异等遗传操作。

（6）cache算子：将数据缓存到内存，供迭代运算使用。

（7）reduceByKeyLocally算子：选出适应度最高的染色体。

3.3 Spark框架下的DP-IGKM算法设计

Spark中的mapValues算子的操作如下：

（1）在第一轮迭代中，在染色体内部进行聚类中心初始化。

将NR条记录u1，…，uNR平均分成NK个子集G1，…，GNK，集合Gk中的记录数|Gk|≤ceil（NR/NK），ceil（）为向上取整函数。计算Gk中记录的数量num0k和Gk中各记录的特征向量之和sum0k，分别对num0k和sum0k加入随机噪声得到num0k' 和sum0k'，计算v0k'=sum0k' / num0k'，v0k'即为初始聚类中心点。

（2）在后续的迭代中，通过均值聚类完成聚类中心的更新。

3.4 算法隐私性分析

5 结语

本文在Spark分布式平台上设计了满足差分隐私保护的遗传k-means算法，利用染色体表示一种聚类方案，将多条染色体划分到Spark框架下的各个分布式资源中分别进行进化，并利用种群迁移策略实现遗传聚类的全局优化，最后通过随机噪声添加使算法满足差分隐私保護。

参考文献：

[1] 唐成华，刘鹏程，汤申生，等.基于特征选择的模糊聚类异常入侵行为检测[J].计算机研究与发展，2015，52（3）：718-728.

[2] Sarat K C，Bhogeswar B.On analysis of time-series data with preserved privacy[J].Innovations in Systems and Software Engineering，2015，11（3）：155-165.

[3] 邓诗卓，姚继涛，王波涛，等.PCPIR-V：基于Spark的并行隐私保护近邻查询算法[J].网络与信息安全学报，2016，2（5）：64-76.

[4] 宋健，许国艳，夭荣朋.基于差分隐私的数据匿名化隐私保护方法[J].计算机应用，2016，36（10）：2753-2757.

[5] 何贤芒，王晓阳，陈华辉，等.差分隐私保护参数ε的选取研究[J].通信学报，2015，36（12）：124-130.

【通联编辑：代影】

随便看

科学优质学术资源、百科知识分享平台，免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。