第 1 章 绪论
1.1 研究背景及意义
随着大数据时代的到来，尤其是 5G 技术的飞速发展，全球每天都在产生大量的数据，这些数据记录背后隐藏着大量有价值的信息，众多机构和企业利用这些数据，可以获取海量潜藏的具有关键价值的信息。为了能够对这些数据进行分析，数据挖掘技术应运而生。聚类[1]是一种常用的数据挖掘技术，作为海量数据智能处理的一种基本方法，在数据挖掘、模式识别[2]、生物科学[3]、web 分析[4]等领域都占有重要地位。
聚类已成为国内外关注的热点，目前为止，产生了许多种聚类算法，主要包括基于划分的聚类（如 K-means[5]和 K-medoids[6]），基于层次的聚类（如 BIRCH[7]），基于密度的聚类（如 DBSCAN[8]）以及基于网格的聚类（如 STING 算法[9]）等。这些算法针对不同的应用场景各有优势，如 DBSCAN 能够很好的适应任意形状的数据，但是对高维数据的处理较为困难。K-means 算法思想简单，实现简单，收敛速度快，但是算法本身需要用户事先给定簇的个数，且算法本身迭代的过程并不能确保一定会得到全局最优解。
2007 年，Frey 和 Dueck 提出了一种基于范例的聚类算法——近邻传播聚类（Affinity propagation clustering，简称 AP）[10]，该算法将数据中的所有样本都看作潜在的簇中心点，通过对每个点的吸引度值与归属度值进行若干次的迭代更新，直到收敛。这种算法可以简单而准确的对数据进行聚类，而不需要用户事先指定簇的数量，因此在图像分割[11]、图像特征提取[12]和多目标跟踪[13]中得到了广泛的应用。
然而，聚类的对象数据通常包含了许多用户的个人隐私信息，比如社保账号，用药记录，个人收入等。一旦这些恶意数据被恶意的攻击者挖掘分析，将会对个人隐私造成极大的威胁。由于近邻传播聚类在运行过程中会不断地在数据点之间传递互信息来进行迭代。因此，如果敌手能够截获中间值信息并加以分析，那么就可以很容易的得到指定用户的隐私数据，从而造成严重的后果。
..........................
1.2 研究现状及分析
由于针对不同聚类算法的差分隐私模型研究仍处于起步阶段，因此本节将根据不同类型的聚类算法分别介绍其相关的差分隐私保护方法的研究现状。
1.2.1 基于划分的聚类差分隐私保护方法
在众多聚类算法中，基于划分的聚类算法是应用非常广泛的一类聚类算法，其代表性的聚类算法主要有 K-means 和 K-medoids，这类算法通常是首先让用户确定需要将数据聚成几类并挑选初始中心点，然后通过不断地迭代来使得类内的数据点距离都足够的近，类间的数据点距离都足够的远。针对这类聚类算法，已经有许多基于差分隐私的保护方案相继提出，例如 Blum[21]等人在 SuLQ 平台上提出了差分隐私 K-means 算法，但其查询函数的敏感性较高，算法没有指定如何设置隐私预算，此算法的聚类结果对添加噪声的鲁棒性也不强，降低了聚类结果的可用性。2011 年，虽然 Dwork 在文献[22]中提出了一定的改进，但是仅仅是对隐私预算的分配进行了优化。针对文献[21]中的其他问题依旧没有进行很好的解决，这主要是因为算法对初始中心点的选择很敏感，并且在对中心点添加噪声后往往会和真实中心点有所偏离，进一步导致可用性下降。因此，李杨等人[23]通过将数据集平均划分为几个子集，在扰动后计算每个子集的中心，以此改进初始聚类中心点的选择来提升聚类的精度。但是，这样的方法仍然存在一定的缺陷，因为他们没有考虑离群值对聚类结果的负面影响以及等分划分数据集是否合理，所谓离群值就是与其他对象显著不同的数据对象，这类值会严重影响聚类结果的稳定性。Yu 等人[24]提出了一种剔除异常值的差分隐私K-means 方法，该方法根据数据集的分布密度进行划分后选择初始中心点，并在数据集上添加拉普拉斯噪声来保护隐私，可以抵消一部分离群值对结果的干扰，提升聚类精度。Gao和 Zhang[25]结合粒子群算法和杜鹃搜索对 K-means 聚类中心选择算法进行了改进，该算法实现了差分隐私保护，并在 Apache Spark 引擎上实现了并行化。对于 K-medoids 算法，在2017 年，高瑜等人[26]提出了一种基于差分隐私保护的 DP-Kmedoids 算法，其通过对中心点进行扰动之后再进行发布，一定程度上保护了用户的隐私不受侵害，然而同 K-means 算法一样，K-medoids 算法对初始中心点敏感，添加噪声后会进一步影响聚类结果的精度，尤其对于动态数据而言更为严重。因此，马银方等人[27]通过结合 KD 树来选出 k 个聚类中心，再结合增量数据更新 KD-树，同时采用近邻搜索策略来将增量数据分配至簇中来解决动态数据下的聚类隐私保护，提出了 KDCK-medoids 算法，提升了算法的应用面以及效用性。
..............................
第 2 章 隐私保护模型以及近邻传播聚类算法概述
2.1 隐私保护模型
在互联网以及大容量存储技术的迅猛发展之下，数据的采集、发布、共享变得越来越简单方便。但是，直接发布相关数据的分析结果容易对用户的隐私造成威胁。因此，数据发布者在数据发布之前需要对数据进行一定的处理，确保攻击者无法从发布结果中推测用户的个人隐私。
2.1.1 基于分组的隐私保护模型
对于一个数据集而言，其记录类型可以分成敏感属性、非敏感属性、标识符以及准标识符。敏感属性就是泛指一切用户不希望别人知道的信息，如年龄和疾病等等。非敏感属性就是可以公开的属性。标识符就是能够唯一的标识用户身份的属性，比如表 2.1 中的 ID和姓名，都属于标识符。准标识符就是介于标识符和非敏感属性之间的属性，通过结合别处获得的信息，能够大概率的推测出目标所对应的记录，如表 2.1 中的性别，年龄，邮编等都可以看作准标识符。
软件工程硕士论文怎么写
2.2 近邻传播聚类算法
在本小节中，将详细介绍近邻传播聚类算法[10]（以下简称 AP）的具体过程和实现原理。作为一种基于范例的聚类方法，它将网络中的每个数据点作为一个节点，并将所有数据点看作潜在的簇中心点（即范例），然后在这些节点之间交换实值消息，直到聚类产生。因此，AP 可以在不指定簇的数量的情况下探索簇中心点，并且花费更低的平方误差来对数据进行聚类，算法的具体思想如下。
对于一个待聚类数据集 X，AP 算法首先将待聚类数据集中的所有数据点都用一个相似=Ss x x x x ∈X 进行表示， ( ,)i ks x x 为相似度矩阵 s 的查询函数。当i kx ≠x 时，用来表示数据集 X 中点ix 和点kx 的相似度，一般使用欧氏距离来进行度量。当i kx =x 时，( ,)k ks x x 则表示点kx 的偏好值，所有数据点的偏好值构成一个偏好向量 p 。这个值的含义为，当一个点的偏好值越大，那么这个点就越有可能被选为一个簇中心点。函数 S 的计算公式具体表示如下：
软件工程硕士论文参考.
第 3 章 近邻传播聚类算法的差分隐私保护方法 ................................ 14
3.1 隐私问题描述 ........................................ 14
3.2 算法 DP-AP 总框架 ............................................ 16
3.3 子算法描述 ........................................ 17
第 4 章 基于 MapReduce 的近邻传播聚类差分隐私保护方法 .............................. 27
4.1 隐私问题描述 ........................... 27
4.2 算法描述 ..................................... 28
4.3 算法的隐私安全性与时间复杂性分析 ........................... 30
第 5 章 总结与展望 ......................................... 39
5.1 总结 ...................................... 39
5.2 展望 ................................................ 40
第 4 章 基于 MapReduce 的近邻传播聚类差分隐私保护方法
4.1 隐私问题描述
由本文 2.3 节可知，DisAP 主要有三个部分组成：数据稀疏化，高质量簇中心点生成以及簇分配。由于前两个部分仍然是基于传统的 AP 聚类算法，因此也存在着如本文 3.1节所描述的隐私问题。在 Mapreduce 框架中，数据处于一个开放性的分布式环境之中，这种环境为数据的分布式处理提供了灵活的处理方式。DisAP 算法主要包含以下几个部分，如图 4.1 所示，第一部分 Map 函数将数据块划分成了 K 个大小近似相等的不相关子集，在被划分成若干个子集后，数据会被输出成<key,value>的键值对的形式。第二部分的 Reduce函数对第一部分产生的<key,value>的键值对进行 AP 聚类操作。假设数据被划分成了 K 个子集，分配至 K 个计算节点进行 Reduce 操作，如果攻击者通过渗透攻击等手段攻克了其中部分计算节点，攻击者就能获得一定的背景知识。攻击者如果想要知道某个数据点的具体信息，即使该数据点所在的节点并没有被攻击者攻克，但是在进行分布式 AP 聚类的过程当中，通过节点计算的吸引度和归属度值，结合之前获得的背景知识，中间结果会有极大地可能会泄露用户的敏感数据。
在算法的第三个阶段，对应算法的 Mapper3 和 Reducer3 过程，即将除筛选出的高质量簇中心点之外的所有点与筛选出的高质量簇中心点进行欧式距离计算，从而将每个点分配至距离其最近的簇中心点所在的簇的过程中。由于算法处于分布式的环境之中，假设攻击者想知道点 k 的具体值，其知道数据点 k 处于某个节点中，并且除 k 以外的所有数据所在的节点都被攻击者攻克了。在计算欧氏距离的时候，如果攻击者能够知道 k 与高质量簇中心点集 E 中的具体距离值，那么攻击者就有可能知道 k 的具体信息，造成用户的隐私泄露。此外，由于数据的处理处于分布式环境之下，因此数据的传输和分析过程更容易遭到恶意的攻击导致用户的隐私泄露，因此分布式环境下的近邻传播聚类同样存在严重的隐私泄露问题。
软件工程硕士论文参考
第 5 章 总结与展望
5.1 总结
近年来，随着互联网和移动设备的飞速发展，网络的覆盖比率也越来越高，每一个网络用户每天都在产生着大量的数据。对这些数据加以利用分析，能够挖掘出相当有价值的信息，众多机构和企业利用这些信息能够更好地为客户服务，并开发出更优秀的互联网应用。近邻传播聚类 AP 作为一个新型的数据分析聚类算法在各个领域得到了广泛的应用，如人脸识别，生物信息学，社交网络分析等等。然而，利用近邻传播聚类算法直接对原始数据进行挖掘分析，很容易产生隐私泄露的问题，这会大大损害用户的隐私安全。本文基于近邻传播聚类算法提出了一种基于差分隐私的近邻传播聚类保护算法 DP-AP，既能在满足隐私要求的前提下尽量保证数据的可用性，又能尽量的提高算法的运行效率。本文的主体工作如下：
（1）本文首先介绍了近年来各类基于差分隐私的聚类保护算法的研究现状，并对近邻传播聚类算法，基于 MapReduce 的分布式近邻传播聚类算法以及差分隐私框架进行了详细的描述。
（2）对于近邻传播聚类算法存在的隐私泄露问题，本文指出近邻传播聚类算法在信息传递过程中可能面临的隐私风险，并且针对性的提出了一个基于差分隐私的近邻传播聚类保护方案 DP-AP。此方案主要由基于邻域密度值的偏好值自适应机制与吸引度矩阵扰动机制两个方面组成，本文对这两个机制进行了详细的介绍，并对算法的安全性和时间复杂性进行了严格的分析。同时本文还将所提出的算法与其他若干种基于差分隐私的聚类保护方案进行了对比，证明了所提出的方案能够满足严格的差分隐私框架并且在可控的时间复杂度下能够保证一定的数据可用性。
（3）由于目前许多应用场景都需要使用并行框架对大数据进行分析，但是 DP-AP 方案在大型数据集上运行效率不佳且结果精度较差。因此本文提出了一种结合 MapReduce的近邻传播聚类差分隐私保护算法 DP-DisAP，通过将数据集划分成若干个不相关的子数据集进行并行 DP-AP 聚类，减少了算法的运行时间且提升了聚类结果的可用性。同时分析了算法的隐私安全性和时间复杂度，证明算法能够对数据提供隐私保护，最后还将DP-DisAP 算法与原始的 DisAP 算法以及 DP-AP 算法进行比较，证明了 DP-DisAP 算法拥有良好的性能以及聚类精度。
参考文献（略）