一种基于密度峰值的高效分布式聚类算法
2019-07-05何仝徐蔚鸿马红华曾水玲
何仝 徐蔚鸿 马红华 曾水玲
摘 要：基于密度峰值的聚类算法（DPC）是最近提出的一种高效密度聚类算法。该算法可以对非球形分布的数据聚类，有待调节参数少、聚类速度快等优点，但在计算每个数据对象的密度值和高密度最邻近距离时，需要进行距离度量，其时间复杂度为 。在大数据时代，尤其是处理海量高维数据时，该算法的效率会受到很大的影响。为了提高该算法的效率和扩展性，利用 Spark 在内存计算以及迭代计算上的优势，提出一种高效的基于E2LSH分区的聚类算法ELSDPC（an efficient distributed density peak clustering algorithm based on E2LSH partition with spark）。算法利用DPC算法的局部特性，引入局部敏感哈希算法LSH实现将邻近点集划分到一个区域。通过实验分析表明：该算法可在满足较高准确率的同时有效提高聚类算法的扩展性和时间效率。
关键词：聚类;密度峰值;大数据;局部敏感哈希;Spark
中图分类号： TP311.1 文献标识码：A
An Efficient Distributed Clustering Algorithm Based on Peak Density
HE Tong1，2？覮，XU Wei-hong1，2，MA Hong-hua2，ZENG Shui-ling3
（1. School of Computer and Communication Engineering，Changsha University of Science
and Technology，Changsha，Hunan 440114，China;
2. Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation，
Changsha University of Science and Technology，Changsha，Hunan 440114，China;
3. Zixing City Science Bureau，Chenzhou，Hunan 23400，China;）
Abstract：The density peak clustering algorithm （DPC） is a recently proposed efficient density clustering algorithm. The algorithm can cluster the data of non-spherical distribution，which needs less adjustment parameters and fast clustering speed. But when calculating the density and exclusion value of each data object，the distance measure needs to be measured，and its time complexity is . When dealing with big data，especially high-dimension data ，the efficiency of the algorithm will be greatly affected. In order to improve the efficiency and scalability of the algorithm，take the advantages of Spark in memory calculation and iterative computing，we propose an efficient clustering algorithm based on E2LSH partition-ELSDPC. Using the local characteristics of the DPC algorithm，the LSH implementation is introduced to divide the adjacent point set into a region. The experimental analysis shows that the algorithm can effectively improve the scalability and time efficiency of the clustering algorithm while satisfying the high accuracy.
Key words：clustering;density peak;big data;LSH;Spark
聚類是被称为模式识别的无监督学习方法[1]。它将数据样本分成若干个类或簇，使得同一个类或簇中样本相似度较高，不同类或簇中的样本相似度较低，从而发现数据元素间的潜在联系，挖掘感兴趣的知识。2014年Alex和Anlessandro在Science上发表了自动确定类簇数和类簇中心的聚类算法DPC（Clustering by Fast Search and Find of Density Peaks）[2]，利用数据集的密度峰值点，该算法能快速发现任意形状数据集的类簇中心，并高效进行样本点归类和离群点剔除，处理大规模数据时性能良好。相对于诸多传统聚类算法，DPC具有用户交互性、无迭代性、能识别任意形状的簇等优点，但是计算局部密度ρ和高密度最邻近距离δ需要测量数据集中任意两点之间的欧氏距离，复杂度为O（N2）。当处理海量高维数据时，算法的实现涉及到大量的高维欧氏距离计算，造成大量的计算开销，使其无法在单机环境下运行，严重影响了算法的实用性。
分布式 DPC 的挑战，在基于MapReduced的简单分布式密度中心聚类算法SDDPC[3]，SDDPC计算了两个后续MapReduce作业中的ρ和δ值。这两个工作有相似的计算程序： Map和shuffle阶段主要用于发送和准备输入数据，而Reduce阶段分别执行ρ和δ的实际计算。然而，该算法必须将每一点都洗牌到其他点，计算出所有对点的距离，产生平方次计算和通信开销。对于拥有数百万点的大型数据集来说，这样的代价将是非常高昂的，而百万千万的数据集在大数据时代，是越来越普遍了。SDPC[4]利用Spark GraphX优化了SDDPC的实现方式。MRDPC[5]采用简单的几何空间划分对数据进行分块处理，提出了独立计算单元和独立计算块的概念，在进行独立计算块中的局部密度计算的过程中，降低了通信开销，但聚类的准确率有所下降。EDDPC[3]是最近提出的并行 DPC 算法，它利用Voronoi图和数据复制/过滤模型，大量减少距离测量和shuffle成本。
本文的贡献如下：1）利用DPC算法的区域特性，提出适合DPC的分区方法;2）充分考虑分布式计算的因素，紧密结合RDD计算过程，在spark分布式平台上实现了所提出的算法.
1 相关工作
1.1 DPC
DPC是一类给定数据集S = {x1，x2，…，xn}，快速搜索密度峰值点的聚类算法。假设聚类中心对应某些具有局部极大密度估计值的样本点，这些样本点可以看作由低密度样本点所包围的“高密度峰值点”，距离其他高密度近邻样本相对较远。算法通过快速搜索和发现代表聚类中心的“高密度峰值点”，将每个非中心样本点沿着密度估计值递增的最近邻方向迭代移动到相应的聚类中心，实现数据划分。这里涉及两个基本概念：局部密度估计和高密度最近邻距离。
式中：χ（d）表示核密度估计的核函数，常见的有两种核函数形态，相应的密度估计公式如下：
1）截断核估计
2）高斯核估计
式中： d（i，j）为样本点xi、xj间的距离，采用满足三角不等式的距离度量，如欧氏距离;dc > 0是预先指定的密度估计参数，相当于核函数的窗宽。由文献[6]可知当数据量比较大时截断核计算简便且性能优于高斯核函数，当数据量较少时而高斯核估计则具有更好的鲁棒性。因此本文采用适合海量数据处理的截断核函数。
离群值δi则定义为到具有更大密度估计值的最近邻样本点的距离，即
1.2 Spark 平台
Spark[7]由美国加州大学的伯克利分校的 AMP 实验室首次提出的类HadoopMapReduce的基于内存计算的大数据并行计算框架。Spark 不同于MapReduce的是 job 的中间结果不需要再写入本地的 HDFS，而是直接在内存中完成，可以更好的适用于机器学习以及数据挖掘的多次迭代的计算。Spark 最主要的创新点是提出了弹性分布式数据集RDD[8]（Resilient Distributed Dataset）。 RDD 本质上是一种只读的分布式共享内存模型 ，它具备像MapReduce等数据流模型的容错特性，并且允许开发人员在大型集群上执行内存的计算。对于数据分区来说 Spark 支持用户自主确定分区策略，Hadoop的MapReduce在执行 Map 后一般需要花费大量的时间进行排序操作，这个主要由 shuffle 执行。Spark 虽然也有 shuffle 操作，但是 Spark 的 shuffle 不是在所有场景下都是必须的，因此可以很大程度地减轻开销。
1.3 E2LSH
LSH[9]（Locality Sensitive Hashing）算法由Gionis提出的一种针对海量高维数据的快速最近邻查找算法，它将原始数据从欧氏空间的准则下转换到Hamming空间下便于进行局部敏感哈希运算，E2LSH[10]是基于p-stable分布的LSH方法的一种实现。
对一个实数集上的分布D，如果存在P≥0，对任何n个实数r1，r2，…，rn和n个满足D分布的n个独立同分布随机变量X1，X2，…，Xn，∑i ri·Xi和（∑i |ri|p）（1/p） X）有相同的分布，其中X是服从D分布的一个随机变量，则D分布被称为一个p-stable分布[10]。对于任何p∈（0，2）存在稳定分布，当p = 2时是高斯分布，概率密度函数为：
p-stable分布具有如下性质：若两个变量都服从p-stable分布，则其线性组合也服从p-stable分布[10]。
根据稳定分布性质，随机变量a·v具有和（∑i |vi|p）（1/p） X）一样的分布，其中随机变量a中的每一维都是随机的、独立的从p-stable分布中产生的，因此可以用a·v对向量v来进行降维，并可以用它来估算‖v‖p[12]，很容易看出这个过程是可以线性组合的，也就是说a·（v1 - v2） = a·v1 - a·v2当p = 2时，两个向量v1和v2的映射距离a·v1 - a·v2和
‖v1 - v2‖p X的分布是一樣的，此时对应的距离计算方式为欧氏距离。
2 ELSDPC
在DPC算法中邻近点在计算中起着十分重要的作用。因此本文提出利用E2LSH来划分数据，将距离较近的点分配到同一个分区。
2.1 分区策略
本文并不用‖a·v‖p，来估算‖v‖p，而是使用它对每一个特征向量v赋予一个hash值。对于两个向量v1和v2，如果它们之间的距离很近（‖v1-v2‖较小），它们将以很高的概率发生碰撞（hash值相同），如果它们之间的距离很远，则冲突的概率将会很小。E2LSH中的hash数定义如下：
式中w表示窗口的大小b表示[0，w]之间的随机变量。显然通过这种分区方式能保证边界点的邻近节点会被分到同一个区域，能够更准确地估计边界区域中对象的局部密度。
LSH 的距离保持特性允许我们根据它们的哈希值对点集进行分区。如果两个点 i 和 j 被散列到同一个桶，我们可以相信i 和 j是非常接近的。因此，我们可以将它们分配到相同的分区。然而，根据公式（7）有可能发生两个距离较远的点被哈希到同一个桶，即positive false[9]。为了减少positive false，可采用k个hash函数的组合G = {h1，h2，…，hk}来作为分区id。只有两个点的k个hash值都分别有相同的值才会被分到同一个分区。产生的数据分区结果称为E2LSH 分区布局p，定义如下：
定义1 给定一个数据点集合S，一组hash函数G = {h1，h2，…，hk}，通过对每一个点pi∈S使用G映射到一组k维向量G（pi） = {h1（pi），h2（pi），…，hk（pi）}表示的分区上。集合S也因此分为多个互不相交的子集，即P（S） = S1∪S2∪…，且？坌 m≠n，Sm∩Sn = ？准。
然而，也有可能是接近的点被hash到不同的分区，特别是当k比较大时，容易导致negtive false[9].为了减少negtive false的数量，我们采用了L个G函数{G1，G2，…，GL}.假设通过采用一个hash组函数Gl，可以得到一种E2LSH分区Pl（S） = Sl1∪Sl2∪…，Slm≠Sln，？坌 m≠n，Sm∩Sn = ？准，通过使用L个G函数，就可以的得到L种分区布局。如图2所示展示了两种分区方式。
在 map 阶段，我们实现了多个 LSH 分区布局。对每一个对象pi进行L次G映射，并与pi进行组合得到L个键值对〈G1（pi），pi〉，〈G2（pi），pi〉，…，〈GM（pi），pi〉，每一个reduce（）函数都会收到一个特定E2LSH分区布局下的子集Slm。
2.2 ρ的近似估计
对于一个确定的E2LSH分区布局pi（S），它的一个子集Slm将会发送给一个reduce（）函数。reduce（）函数的第一步工作就是计算子集 中任意两点之间的距离。然后计算每一个点i的局部密度 mi =
如图1所示对象p2在布局1中位于分区S1和S2的边界，因此 12< ρ，但是在布局2中对象p2的dc领域内的对象都在同一个分区，能得到 22= ρ，因此通过多个布局，然后取每个对象的最大值，能够很大概率得到或者十分接近每个对象的局部密度。下面我们分析 li的概率Pr（ li = ρ）。
引理1 给定一个点pi和一个E2LSH函数
证明：给定一个d维的随机向量a，a的每一维都是独立的随机的从高斯分布N（0，1）（高斯分布是p取2时的稳定分布）中选取的变量，由p-stable分布的概率特性可知a·pi - a·pj 的分布和d（i，j）x的分布是一样的，x是服从标准高斯随机变量的绝对值，令yi = a·pi + b，因此对任意pj，d（i，j）≤dc有maxjyi - yj = maxja·pi - a·pj≤dc x，对任意一个位于特定槽内的yi，需要保证yi和它的dc领域内的点都位于同一个槽内，则yi需要满足yi ∈[αw + dc w，（α + 1）w - dc]，如图2所示，yi留在这个区域内概率为 = 1 - ，而服从标准高斯分布的变量的绝对值的概率密度函数为
证明完毕。
2.3 δ的近似估计
在一种特定E2LSH的分区布局的一块分区子集Slm中设计一种reduce（）函数来计算Slm中任意
两个对象之间的距离，然后用{ i|j∈Pmk}估计
li = min j|j∈ ， i > jd（i，j），i∈Pmk，对于Slm中密度最大的点i = arg max i|i∈ ， i，令 li = ∞。
虽然 i很可能完全等价于的ρi，但是由于 li的计算是在子集中进行的。如图1a所示p2的依附点与p2不在同一個分区，将本地的 li作为δi的近似时会得到错误的结果，将i的依附点定位到另外一颗密度树中。如图1b所示在另一种分区布局方式下，p2的依附点和p2在同一个分区则可以得到正确的 δ2和依附点σ2。将两者结果进行适当合并则可以得到正确的结果。
假设 i = ρi，利用p-stable分布的性质，可得到引理3，通过下面的引理得到Pr[ li = δi] 。
引理3.给定一个点pi和一个E2LSH的hash函数，d（i，σi）表示pi和它的真实依附点σi（如果存在）的距离，则
Pδi（d（i，σi），w） = Pr[h（pi） = h（pσi）]
= fp 1- dx
= 2F -1- 1-e （10）
F（）表示密度为N（0，1）高斯分布的随机变量的分布函数。
引理4.在一个拥有k个hash函数的特定E2LSH分区布局中，如果对象 的真实依附点存在，则Pr[ li = δi]=P δi（d（i，σi），w）k。
证明：对每一对象 ，在L种不同的分区布局中可以得到L个近似值（ 1i， 2i，…， Li），通过公式（2）可知越小的高密度最邻近距离越可能是真实的δi，因此令 i = minm mi，和ρ的估计类似，δi= i的条件是找到的 i就是σi，即需要对象i和其真实依赖点σi经过k次hash时，每次hash都会分到同一个区域，可得到概率Pr[ li = δi]=P δi（d（i，σi），w）k。证明完毕。
定理2.在L种E2LSH分区布局中，如果对象i的依附点存在则Pr[ i=δi]≥1-[1-P δi（d（i，σi），w）k]L。
2.4 的进一步修改
如图2和定理2所示，绝大多数点的δi，即d（i，σi）是比较小的，Pr[ i = δi]也能取得较大的值，但是当i和它的依附点的距离较大时，则容易出错。显然，能够近似估计较小的δ，对较大的 则不能够准确估计。显然，密度峰值點通常有较大的 ，通过局部敏感hash函数很难被映射到同一个桶中，本地的密度峰值点很可能被选为全局的密度峰值点，导致过多的点被选为密度峰值点，形成过多的类。
为了纠正δ，需要找到容易被错误估计的点，根据定理2的结论，我们可以设定一个精确度阈值 ？撰δ，令
Pr[ i = δi] = 1 - [1 - P δi （d（i，σi），wk]L ≥？撰δ （11）
w，L，k会在聚类前确定，因此在式（12）中 是唯一的变量，我们可以得到满足精确度阈值的d（i，σi）最小值γ。当d（i， i）≥d（i，σi）≥γ，δi的近似值很可能是错误的，需要进一步纠正。然而，精确地校正这些 i需要计算点i的到所有密度更高的点的距离。这将导致大量的计算和通信成本。相反，我们依靠粗略的矫正，考虑到δi计算只考虑到更高密度点的距离，我们对 较大的点进行采样。点的密度越高，则采样点的概率越高。在校正δi值时，只有这些采样点作为距离测量的候选点。虽然这方法简单，但实验结果表明它是足够有效的。
2.5 ELSDPC算法设计
算法1介绍了ELSDPC算法的主要流程，先使用spark入口函数读取待聚类的数据集生成初始RDD集合，并进行持久化操作，采用算法2对数据进行分区。基于positive false 的影响，重复L-1次对初始RDD对分区，然后计算各自分区布局下的 ρ值，对各种分区布局下得到的ρ值进行处理得到最接近于关于各个数据项真实ρ的 值集合。对于 的处理，与ρ类似，不过需要对 进行进一步矫正，矫正后，重新选择密度峰值点，并根据密度峰值点对对象进行分配。
算法1：ELSDPC算法
输入：待聚类数据集，布局数量L，每种布局中函数个数k
输出：（i，δi，σi）
1）指定分区数，若不指定分区数，默认为文件block数
2）sc=SparkContext（），指定spark程序的入口。
3）读入数据生成RDD集合rddini = {（1，p1），（2，p1）}，…，（n，pn）}，同时用水塘采样法对数据进行采样，计算dc。
4）通过算法2对数据进行分区，得到RDD集合rddiniky，集合元素为
5）对rddiniky集合进行规约化操作，计算两两对象间的距离d（i，j），计算出ρ值，得到集合rddly，plist，元素为
6）重复步骤（4），（5）L次，得到L个rddly，plist
7）计算ρ，对第一个rddly，plist进行处理得到rddly1，p，元素
8）计算 ，方法与计算ρ雷同。
9）画出决策图，用户依据自己的经验和专业知识选择ρpeak，δpeak，得到集合Dpeak={pi | i>ρpeak， i>δpeak }。
10）指定精确度阈值 得到满足精确度阈值的 的d（i，σi）最小值，令γ = d（i，σi）min，，采用并行计算从RDD集合rddρ，δ的分区区中过滤出 i > γ的对象，作为待纠正对象rddtocorr，同时对数据进行采样，如果 ≥ ρpeak则以 的概率进行采样，如果 < ρpeak则以β 的概率进行采样，β是给定的采样率。
11）计算需要被纠正的点到更高密度点的距离，如果找到一个更小的 i则对其进行更新。
12）重新选择密度峰值点，并根据密度峰值点对对象进行重新分配。
算法2：分区算法
输入：函数个数k，RDD集合rddini = {（1，p1），（2，p1）}，…，（n，pn）}
输出：RDD集合rddiniky，集合元素为
1）随机生成一组hash函数簇G={h1，h2，…，hk}
2）将pi分别与h1，h2，…，hk相乘，得到G（pi）={h1（pi），h2（pi），…，hk（pi）}
3）以
3 时间复杂度
3.1 shuffle成本
通过Spark的内存计算特性，适当的转化操作和持久化操作能够从分区中获益，使得shuffle成本大大减少，使得shuffle的消耗主要集中在算法1的step7中。假设数据集的维度为，则shuffle成本可以被近似定义为[3]：
Cs（w，k，L） = 2[（L - 1）·N + di·N] （12）
di表示数据的维度。类似的，SDDPC、EDDPC也采取最主要shuffle消耗进行计算，假设SDDPC每个分区可处理n个数据，SDDPC的shuffle成本可以定义为di·（N）2/n，EDDPC采用复制/过滤模型降低了shuffle成本，但十分依赖数据集的实际分布，在极端情况下shuffle成本仍旧可能接近di·（N）2/n。显然，当数据量越大，ELSDPS相较与SDDPC和EDDPC的shuffle成本的优化越明显。
3.2 计算成本
计算发生在E2LSH分区、距离计算ρ、δ的近似估计，其中距离计算是最主要的计算成本。因为在特定布局的一个分区Slm中都会计算一个距离矩阵 Dlm，Dlm中的元素表示Slm中任意两个对象的距离，大小为Nlm × Nlm（Nlm表示Slm中对象的个数）。因此本文使用距离计算的次数作为计算成本的估计，定义如下[3]：
E[Cc（w，k，L）]=E[ （Nlm）2=L· N2m （13）
其中M表示分区数。类似的，SDDPC的计算成本可以定义为N2 = （ （Nm）2），EDDPC也根据最主要的计算消耗将计算成本定义为 N2m。
3.3 参数调节-L，k，w的选取
ELSDPC算法主要是根据 对数据集进行聚类，对象 被分配到正确类簇的概率为Pr[ li = ρi]·Pr[ li = δi]，然而根据定理二可知 i的准确度十分依赖于真实的δi，不能够在实验前得到，因此通过分析 的准确度，来定义准确度阈值：
？撰（w，k，L） = ？撰ρ（w，k，L） = 1-[1-Pρ（w，dc）k]M
（14）
假定shuffle一个字节的时间和计算一对对象的距离的时间比例为μ，则优化目标可以描述为满足1-[1-Pρ（w，dc）k]M≥？撰且使得μ·2[（L-1）·N+S] + 2L·∑M m=1（Nm）2能够取得最小值的参数求解问题。
从定理1可知随着L，w的增加，k的减少都会提高准确度。而shuffle成本和计算成本则都随着 L的增加而增加。计算成本同时受到∑M m=1（Nlm）2的影响，而∑M m=1（Nlm）2也会受到w，k的影响，w变小，k变大都会导致产生更多较小的Nm，从而可能得到较小的∑M m=1（Nlm）2。因此L，w，k三个参数对准确度和时间效率的作用是相反的。
综上所述，需要在保证给定精度要求下调整L，w，k来获得最小化运行时间。由于计算成本 （主要由∑M m=1（Nlm）2决定） ，不仅仅取决于 E2LSH 参数L，w，k，还依赖数据的分布，最优化的问题不能在没有数据知识的情况下解决。通过采样数据点来调整离线参数。通过分布式水塘采樣法采样得到h
组N个对象，然后对这h组对象分别执行E2LSH分区法，得到h个E2LSH布局，即可得到 h个
∑ m=1（N′m）2，计算其均值，并通过放大 倍来估计计算成本即∑ m=1（Nlm）2≈ · 。同时，通过贪婪启发算法来寻找最优化参数集。
首先，先将L，k固定为L0，k0，通过给定的准确度？撰求得w的最小值w0，然后通过L0，k0，
∑ m（Nlm）2的预测值得到总的时间消耗T0。
接下来，令L+x=L0+x，L-x=L0-x（x表示步长，且x∈A+），同时固定k0，计算出T+x，T-x，我们选择拥有较小时间成本的L并固定，然后令k+y=k0+y，k-y=k0-y，同样选择导致时间成本较小的k。通过调节L，k不断重复上述过程直到时间成本T不在随着 L，k的变化而减少，这时候将（L，k，w）作为结果返回。
4 实验与结果分析
4.1 实验环境和数据集
实验环境为Linux操作系统，spark本地集群，包括一台master机器和4台slave机器，各节点虚拟机处理器配置为Intel Xeon CPU E5-2650 v2，内存4GB。表1中列出了我们采用的数据集[13]，包括1个小规模的2D 数据集，四个大中型高维数据集，使用2D 数据集来可视化聚类结果，大中型数据集以评估本地集群的效率和有效性。
4.2 ELSDPC算法的有效性
在 ELSDPC中，根据3.3.2节所示，将参数设置为？撰 = 0.99，L = 5，k = 3。
为了使聚类结果可视化，在小型2D 数据集s2上运行了DPC 和 ELSDPC。如图3所示DPC和ELSDPC的聚类结果几乎是相同的。差异仅存在于边界点和决定一组点是否应以更细的粒度聚集。
4.3 ELSDPC算法的效率
Facial，KDD，3Dspatia，BigCross500K四个数据集上依次分别运行SDDPC ，ELSDPC算法。ELSDPC参数设置为？撰 = 0.99，L = 5，k = 3，SDDPC每个分区处理2000个数据集。
①shuffle成本，图5b比较了SDDPC和ELSDPC在数据混洗过程中的shuffle成本，在SDDPC中需要将所有点都复制到其他分区中，而在ELSDPC中主要将ELSDPC分区计算的结果进行shuffle，避免了平方次通信的消耗。如图5b所示，相比SDDPC，ELSDPC可以达到5-87x的收益，随着数据量和增大，收益越明显。
（a）运行时间
（b）shuffle成本
（c）计算成本
②计算成本，图5c展示了两种算法中距离计算的次数，SDDPC的计算成本呈平方式增长，ELSDPC则呈线性增长趋势，如图5c所示，随着数据量的增大，ELSDPC相比SDDPC的计算成本能获得收益更加明显。
表2 BigCross500K不同算法下聚類效率表
表2中，我们可以看到，尽管相比EDDPC，ELSDPC需要更多的计算次数，但通过更少的shuffle成本，比起EDDPC仍只需要更少的运行时间;MRDPC采用立方体进行切割，并将立方体与周围的立方体内的数据，进行距离计算和shuffle，ELSDPC的计算次数和shuffle消耗明显优于MRDPC，同时MRDPC的立体几何划分方式没有考虑DPC算法中邻近点的不规则性，导致算法的准确率也远远低与ELSDPC。
4.4 参数L K的影响
本节主要研究参数L，k的影响。通过在在本地机器集群上使用运用ELSDPC算法对BigCross500K 数据集进行聚类，设置？撰 = 0.99。通过离线参数调节（第3.3.2节） 方法返回L = 5和k = 3。我们进一步变化的L和k，图6a和图7显示了参数L，k对运行时间和准确度的影响。如图6a所示，当k = 3 时，运行时间随着L的增加而增加;但是当k很大时，情况则有所不用，当k = 20，趋势实际上在逆转，这是因为当L较小而k很大时，会发生严重的工作负载倾斜，从而导致性能下降。图6b显示了参数L，k的选择对准确率的影响。当L小于5时，准确率异常低，这可能会降低群集结果的质量。另一方面，当L大于 5时，准确率十分稳定，几乎所有情况下准确率都达到了99%。考虑参数对运行效率和准确率的影响，本文建议设置L = [5，20] 和k = [3，10]。
5 结 论
提出了一种分布式聚类算法EDDPC，根据LSH对数据集进行划分，然后提出多次hash对分区后的计算结果进行修正，保证聚类的质量;同时在Spark分布式平台上，利用RDD实现了算法。文中使用UCI的数据集对改进算法进行了一系列实验，实验结果表明，使用ELSDPC聚类算法在能保证良好聚类结果的精度的同时表现出良好的数据伸缩率和可扩展性，算法具有处理海量高维数据的能力。
参考文献
[1] HAN Jia-wei，INEKAMER M. 数据挖掘：概念与技术[M]. 机械工业出版社，2007.
[2] RODRIGUEZ A，LAIO A. Clustering by fast search and find of density peaks[J]. Science，2014，344（6191）：1492.
[3] GONG S，ZHANG Y. EDDPC：an efficient distributed density peaks clustering algorithm[J]. Journal of Computer Research & Development，2016，6（53）：1400—1409.
[4] LIU R，LI X，DU L，et al. Parallel implementation of density peaks clustering algorithm based on spark[J]. Procedia Computer Science，2017，107（C）：442—447.
[5] WANG Y，PENG T，HAN J Y，et al. Density-based distributed clustering method[D]. 长春：吉林大学，2017.
[6] HOU J，LIU W. Evaluating the density parameter in density peak based clustering[C]// Seventh International Conference on Intelligent Control and Information Processing. IEEE，2017：68—72.
[7] ZAHARIA M，CHOWDHURY M，FRANKLIN M J，et al. Spark： cluster computing with working sets[C]// Usenix Conference on Hot Topics in Cloud Computing. USENIX Association，2010：10—10.
[8] ZAHARIA M，CHOWDHURY M，DAS T，et al. Resilient distributed datasets： a fault-tolerant abstraction for in-memory cluster computing[C]// Usenix Conference on Networked Systems Design and Implementation. USENIX Association，2012：2—2.
[9] INDYK P. Approximate nearest neighbors： towards removing the curse of dimensionality[C]// ACM Symposium on Theory of Computing. 1998：604—613.
[10] DATAR M，IMMORLICA N，INDYK P，et al. Locality-sensitive hashing scheme based on p-stable distributions[C]// Proc. Symposium on Computational Geometry. 2004：253—262.
[11] ESREADA R，RUIZ I.The language： scala[M]. Big Data SMACK：Apress，Berkeley，CA，2016.
[12] LAHA R G. Book review： one-dimensional stable distributions[J]. Bulletin of the American Mathematical Society，1989，20（2）：270—278.
[13] LICHMAN M. UCI machine learning repository[EB/CD]. http：//archive.ics.uci.edu/ml，2013.
[14] VINH N X，EPPS J，BAILEY J. Information theoretic measures for clusterings comparison： is a correction for chance necessary？[C]// International Conference on Machine Learning. ACM，2009：1073—1080.
[15] HE Y，TAN H，LUO W，et al. MR-DBSCAN： an efficient parallel density-Based clustering algorithm using mapreduce[C]// IEEE，International Conference on Parallel and Distributed Systems. IEEE，2012：473—480.
