密度峰聚类算法优化及其隐私保护研究

作     者：鲍舒婷 

作者单位：安徽师范大学 

学位级别：硕士

导师姓名：孙丽萍

授予年度：2019年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 0839[工学-网络空间安全] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：密度峰聚类 共享近邻相似度 万有引力搜索 差分隐私 

摘      要：数据挖掘可以发现隐藏在大量数据中有价值的模式和知识,聚类分析是数据挖掘领域中的重要研究方法。作为一种无监督学习的数据分析方法,聚类分析通过划分簇使得簇中样本相似度高的同时簇间样本相似度低,已被广泛应用于模式识别、图像处理以及社团检测等领域。聚类分析的过程是对数据的挖掘和再利用,如果这些数据包含敏感信息,一旦被攻击者恶意挖掘,将会对用户个人财产和名誉带来巨大的影响。密度峰聚类算法是一种基于密度的聚类算法,该算法可以发现任意形状的类簇,聚类过程简洁高效,无需迭代。密度峰聚类算法也存在一些不足之处:对输入参数dc敏感;对剩余样本进行分配很容易形成类似“多米诺骨牌连带错误效应;密度峰聚类算法在计算样本局部密度和最短距离时可能泄露用户隐私。针对以上问题,本文的主要工作和研究成果如下:（1）针对密度峰聚类算法存在对全局参数dc敏感,提出了一种基于共享近邻相似度的密度峰聚类算法。首先,该算法结合欧氏距离和共享近邻相似度进行样本局部密度的定义,避免了原始密度峰聚类算法中参数dc的设置;其次,优化聚类中心的选择过程,能够自适应地进行聚类中心的选择;最后,将样本分配至距其最近并拥有较高密度的样本所在的簇中。实验结果表明,在UCI数据集和模拟数据集上,该算法能有效地提高聚类的准确性和聚类结果的质量。（2）针对密度峰聚类算法仅依赖局部密度对剩余样本进行分配同时容易形成类似“多米诺骨牌效应的缺陷,提出了一种基于万有引力搜索的密度峰聚类算法。该算法使用密度峰聚类算法进行聚类中心选择,将聚类中心作为初始的粒子群并在万有引力搜索算法框架下进行剩余样本的分配,通过寻找最优解获取最佳的聚类效果。实验结果表明,在UCI数据集和模拟数据集上,该算法能具有较优的聚类效果。（3）针对密度峰聚类算法在计算样本局部密度和最短距离时可能泄露用户隐私的缺陷,提出一种差分隐私保护的密度峰聚类算法。该算法在局部密度和最短距离的计算过程中加入Laplace噪声进行差分隐私保护,同时进行隐私安全分析证明算法满足差分隐私保护。实验结果表明,算法在隐私保护程度和聚类有效性之间取得良好的平衡。