基于Spark,框架和ASPSO,的并行划分聚类算法
时间：2023-01-16 17:50:06 来源：柠檬阅读网 本文已影响 人 
毛伊敏，甘德瑾，廖列法，陈志刚
（1.江西理工大学信息工程学院，江西 赣州 341000；
2.中南大学计算机学院，湖南 长沙 410083）
聚类算法根据数据的相似特征将数据集划分成不同的类别，同一类别下的对象具有一定的相似性，而不同类别对象之间则差异较大[1]，因其能够发现样本数据潜在的分布模式，被广泛应用于计算机科学、生物信息学、图像处理、社交网络、天文学以及许多其他的领域。在聚类算法中，基于划分的聚类算法，如K-means 算法[2]、K-中心点算法[3]和CLARANS（clustering algorithm based on randomized search）[4]，由于聚类思想简单且聚类可行性高，受到人们的广泛关注。
随着5G 时代的到来，数据规模爆炸式增长。相较于传统数据，大数据拥有数据规模大、数据种类多样化、数据价值密度低、数据增长速度快等基本特征[5-6]。然而，传统的划分聚类算法在处理大数据时，其时间复杂度以几何级数增长。因此，如何使划分聚类算法更快地处理大数据，是国内外重点关注的问题。
随着传统的数据挖掘算法在分布式计算框架的广泛应用，Spark 凭借计算速度快、简洁易用、通用性强和支持多种运行模式等优势深受广大研究人员青睐。其中，Mugdha 等[7]最早提出了K-means 与Spark 结合的近似算法，但该算法易受噪声数据影响，划分后的数据网格存在数据离散系数较大与抗干扰性差的问题。针对此问题，王海艳等[8]提出了基于Spark 与密度区域划分（SP-DAP，Spark and density-area partition）算法，提取数据集中的高密度数据区域，极大地减小了数据划分后的离散系数并增强了算法的抗干扰性。但该算法无法准确获取局部簇的簇数，从而导致对大型数据的聚类存在局部簇的簇数难以确定的问题。为了解决此问题，Wang 等[9]提出基于 Spark 与 K-means（SK-means，Spark and K-means）并行聚类算法，通过将数据划分为几个可重叠子集，并进行预处理得到簇数。徐鹏程等[10]在Spark 平台上引入Canopy算法和最大最小距离方法，通过简单的距离计算把初始数据划分为多个子集，获取局部聚类的簇数，解决了局部簇的簇数难以确定的问题。虽然这些算法对局部簇的簇数难以确定的问题进行了改进，但是并没有避免局部簇质心的随机性对聚类效果的影响。
近年来，群体智能优化算法凭借其寻优效果好、易实现等优势得到了广泛应用。因此，许多学者引入群体智能算法对数据的局部簇质心进行优化。例如，Multazam 等[11]在Spark 平台上提出遗传算法与K-means 相结合（SP-GAKMS，Spark and genetic algorithmwith K-means），通过对种群个体的多次选择、交叉以及变异的遗传操作，使种群个体逐渐优化并逐步逼近最优解，最终得到最优的初始质心集。许明杰等[12]在 Spark 环境下提出PSOK-means（particle swarm optimization and K-means）算法，利用粒子群优化（PSO，particle swarm optimization）算法来提高K-means 的全局搜索能力，得到初始质心。Gao 等[13]利用最优化问题对 PSO 算法进行改进，提出了SP-PSOK-means（Spark and PSO with K-means）算法，利用远离个体最差经验和最差群体经验提高局部搜索能力，获取全局最优初始质心。虽然这些算法成功应用了群优化算法来获取局部簇的初始质心，但存在局部搜索能力差、搜索精度不高且易陷入局部最优值等缺点，导致无法获取全局最优初始质心，因此算法的初始质心优化能力有待进一步提升。
此外，基于Spark 并行计算框架下的划分聚类算法在进行局部簇的并行化合并过程时存在算法局部簇并行化合并效率低的问题。为了解决这个问题，Agrawal 等[14]提出基于Spark 节点相似度的局部簇合并（SP-LCMNS，Spark and local cluster merging and node similarity）算法，通过合并二次划分算法与群体结构，避免了点与边集的重复计算，极大地提高了局部簇的并行化合并效率；
Lai 等[15]提出了基于Spark 局部聚合的自动迭代聚簇算法（SP-LAICA，Spark and local aggregation and iterative clustering algorithm），通过寻找局部簇数据集中连接紧密的节点集，并迭代合并局部簇，实现了对局部簇的高效率并行化合并。虽然上述算法对提升局部簇的并行化合并的效率有一定提升，但这些算法都存在一定的局限性，导致簇的并行化合并效率降低。因此，局部簇并行化合并效率低的问题仍是亟待解决的问题。
综上，如何有效减小数据离散系数、增强算法抗干扰性、确定局部聚类簇数、避免局部簇质心随机性以及提高局部簇并行化合并效率等仍然是目前亟待解决的问题。针对这些问题，本文提出了一种基于Spark 框架和粒子群优化自适应策略（ASPSO，adaptive strategy based on particle swarm optimization）下的并行划分聚类（PDC-SFASPSO，parallel division clustering based on Spark framework and ASPSO）算法。本文的主要工作如下。1)提出了基于皮尔逊相关系数和方差（PCCV，Pearson’s correlation coefficient and variance）的网格划分策略，计算数据网格的皮尔逊相关系数与相关系数阈值，通过与阈值比较，对数据网格进行划分，获取数据离散系数较小的网格单元G1，G2，G3，…，Gm，并设计离群因子对网格单元进行离群点过滤，解决了数据离散系数较大与抗干扰性差的问题。2)提出了基于势函数与高斯函数（PFGF，potential function and Gaussian function）的网格划分策略，对数据点进行局部区域的有效覆盖，并提出更新函数FU(xi，yj)，更新数据集中的样本点，形成以不同样本点为核心的区域簇，获取局部聚类的簇数，解决了局部簇的簇数难以确定的问题。3)提出了ASPSO，计算自适应参数η，通过自适应参数更新粒子的位置和速度，获取局部簇质心，解决了局部簇质心的随机性问题。4)提出了基于簇半径与邻居节点（CRNN，cluster radius and neighbor node）的局部簇合并策略，计算出邻居节点，并根据簇的相似性函数CSM(ni，nj)进行相似度判断，结合Spark 并行计算框架将相似度大的簇进行合并，避免了在并行化运算过程中对所有簇的点与边集同时展开搜索，提高了局部簇并行化合并的效率。
定义1势函数。势函数可以对数据点的作用势进行分析，度量样本空间中2个数据点随距离的变化情况[16]。设有一个样本集Si，x1和x2为数据集中的2 个样本点，则势函数γ(x1，x2)可以表示为
其中，T为常数，d2(x1，x2)为x1和x2之间的距离。
定义2高斯核函数。高斯核函数是某种沿径向对称的标量函数，可以将有限维数据映射到高维空间，并将数据集划分成多个不同子空间，从而进行局部计算[17]。设σ表示带宽，x表示样本点，x′表示核中心，则高斯核函数k(x，x′)可以表示为
定义3邻居节点。邻居节点表示簇与簇之间的交集节点，可以衡量簇与簇之间亲密程度。设有2 个簇Ci，Cj的数据点，对于任意样本点xi，如果其到质心的距离小于簇半径Ri和Rj，则此样本点称为邻居节点，其集合称为邻居节点集[18]。
定义4PSO 算法。PSO 算法是一种基于群体智能的全局随机搜索算法，可以对粒子的位置进行不断调优，求解粒子最优化问题[19]。该算法主要包括3 个阶段：粒子位置与速度的初始化、粒子速度更新、粒子位置更新。其具体步骤如下。
1)粒子位置与速度的初始化
2)粒子速度更新
其中，ω为惯性权重，表示之前的速度对当前速度的影响；
c1和c2为学习因子，rand和Rand 为0～1 的随机数。
3)粒子位置更新
2.1 算法思想
PDC-SFASPSO 算法主要包括3 个阶段：数据划分、局部聚类、局部簇合并。1)数据划分阶段提出网格划分策略PCCV，进行数据划分。2)局部聚类阶段，首先提出PFGF 策略与更新函数FU(xi，yj)获取局部聚类的簇数；
然后提出ASPSO 初始化局部簇质心；
最后结合Spark 提出并行化局部聚类策略（SPPLCS，Spark and parallel local clustering strategy）进行局部簇的并行化计算，实现局部聚类。3)局部簇合并阶段提出局部簇合并策略CRNN，合并相似度大的局部簇。
2.2 数据划分
目前大数据环境下的划分聚类算法中，在对数据划分时存在数据离散系数较大与抗干扰性差的问题。因此，本文在进行数据划分的过程中提出了网格划分策略PCCV 来解决此问题。该策略主要包括3 个步骤：数据集的粗略划分、网格的划分、离群点的过滤。
2.2.1 数据集的粗略划分
对于初始数据集，可以对数据先进行粗略划分，获取数据离散系数较小的网格。其具体过程为：首先获取划分数据集，并将其标记为Gs；
其次提出分割函数FD(xi)计算出划分阈值，分别与每个数据点比较，将大于阈值的数据放入网格Gmax中，小于阈值的数据则放入Gmin中；
最后获得2 个数据网格Gmax与Gmin。
定理1分割函数FD(xi)。已知空间数据集中第i维度的数据的方差为Si，数据之和为di，网格中数据点的个数为num，则分割函数FD(xi)为
其中，为第k维度下的数据值。
证明由于方差越大，该维度所带的信息量越多。对于不同维度下方差相同的数据，di越大表明数据越离散，di越小表明数据越集中。因此，网格的划分维度k可根据确定，并选取的最大值作为网格的划分维度。又由于均值可以反映数据的整体倾向，因此，选取该维度下数据的均值作为数据划分的网格分割函数。证毕。
2.2.2 网格的划分
在获取Gmax与Gmin这2 个数据网格之后，由于分割函数只能对数据集进行粗略划分，无法对相似度较大的数据进行网格划分，导致无法获取网格单元。因此，需要对网格Gmax与Gmin进行进一步的数据划分，获取离散系数较小的网格单元，其具体过程如下。
1)提出数据的皮尔逊相关系数阈值PCCk。计算网格中数据点的PCCk值，以PCCk值作为网格划分阈值对数据网格进行划分，通过比较数据的皮尔逊相关系数与PCCk的大小，将系数大于PCCk的数据标记为core，系数小于PCCk的数据标记为uncore。
2)将网格中2 种数据core 与uncore 分别划分为2 个更小的网格，并取消标记。
3)对网格数据点个数进行判断，如果数据点的个数大于网格单元的阈值maxNum，则返回步骤1)；
否则停止对网格进行划分。其中maxNum表示数据集的数据个数n与并行化节点Partition个数的比值。
4)将划分好的网格单元进行标记，得到网格单元G1，G2，G3，…，Gm。
定理2皮尔逊相关系数阈值PCCk。设PCCi，j为任意2 个数据点的皮尔逊相关系数值，Gnum为网格单元的数据点个数，sum 为求和函数，ω为数据点的密度权重，则PCCk为
证明PCCi，j代表数据点之间的关联程度，即PCCi，j越大，数据点之间的相似度越大。将式(11)代入式(10)可得的大小反映了数据的离散化程度，其值越大，则数据越离散；
其值越小，则数据越集中。因此的大小可以很好地对数据相似程度进行衡量，PCCk可以作为网格划分的皮尔逊相关系数阈值。证毕。
2.2.3 离群点的过滤
在获取网格单元G1，G2，G3，…，Gm后，由于网格单元存在离群点，会造成算法的抗干扰性差。因此，为了增强算法的可抗干扰性，设计离群因子GOF来过滤离群点，具体过程为：计算每个网格单元中数据的GOF值，若GOF值远大于ε（网格单元数据阈值），则将该数据点视为离群点，并对其进行删除。
定理3离群因子GOF。假设d(xi，xj)表示网格中2 个数据点的欧氏距离，表示网格单元的中心点，则离群因子GOF为
证明d表示当前网格中某一数据点与其余的m-1个数据点的欧氏距离，其大小可以表示网格的密度。d越小表明网格的密度越大，d越大表明网格的密度越小。表示当前数据点到网格中心的距离。对于离群点来说，其值会相对于其他数据点更大。如果数据点的GOF值远大于ε，则可以将此数据点过滤，因此，可以用GOF来过滤网格的离群点。证毕。
数据划分的伪代码如算法1 所示。
算法1数据划分
输入初始数据集S
输出数据网格单元G1，G2，G3，…，Gm
2.3 局部聚类
目前在大数据环境下的划分聚类算法中，对数据的局部聚类需要对网格单元的数据进行质心初始化，再结合并行化计算完成局部聚类。然而，在实现质心初始化的过程中，由于无法确定局部聚类的簇数，导致不能更好地确定初始质心集的个数，无法实现较优的初始质心。因此，为了获取局部聚类的簇数，更好地实现初始化质心，完成并行化局部聚类，提出LC 策略，其具体过程包括3 个步骤：局部聚类簇数获取、局部簇质心初始化、局部簇并行化计算。
2.3.1 局部聚类簇数获取
为了有效地实现局部聚类，需要优先获取局部聚类的簇数，因此本文提出了PFGF 策略，通过势函数与高斯核函数来完成数据的覆盖与搜索，获取局部聚类的簇数。其具体过程为：首先，对数据集中任意一对数据xi和xj通过式(1)计算其作用势γ(xi，xj)，并以xi为基准样本，将其他的样本点对xj的作用势进行累加，得到每个样本点的作用势集合为ρ={ρ1，ρ2，…，ρn}；
其次，为了对原始数据进行全局搜索，从ρ中选择最大作用势ρi放入一个空的集合M{}中，并以ρi为当前的高斯核中心，以给定的核宽σ建立相应的高斯核来对原始数据的一个局部区域有效覆盖；
最后，为了寻找新的最大势值，需要消除当前高斯核所覆盖的局部区域的样本势值，提出基于高斯核函数的更新函数FU(xi，yj)对数据集中的其他样本点进行更新。
定理4更新函数FU(xi，yj)。假设当前的高斯核中心为ρi，集合中的样本点为ρj，则其更新函数FU(xi，yj)为
其中，σk表示核宽，表示高斯内核。
证明由高斯核函数的衰减特性可知，当样本点距离高斯核中心较远时，xj对xi的影响十分小，又由于表示高斯内核，因此S中各个样本点的势值都可以有效更新。证毕。
2.3.2 局部簇质心初始化
在获取了局部聚类的簇数之后，为了解决局部簇质心随机性的问题，本文提出了策略ASPSO。该策略主要包括2 个阶段：自适应参数确定、质心初始化。自适应参数确定阶段提出AS 策略，引入柯西变异算子，设置粒子平均速度与η来作为自适应参数；
质心初始化阶段通过AS 策略与PSO 算法相结合，并根据自适应参数，对粒子的速度与位置不断更新，跳出局部最优，获取初始化质心。
1)自适应参数确定
在实现质心初始化的过程中，提出了粒子的收敛性，由此性质可知粒子最终收敛于，算法将停止运行，如果算法没有在收敛之前得到全局最优解，就会导致过早收敛，陷入局部最优解。
因此，为了实现初始质心的全局最优解，需要设计自适应参数来避免局部最优。为此，PDC-SFASPSO 算法设计了AS 策略，来确定自适应参数，其具体过程如下。
定理6粒子群体平均速度。已知粒子的个数为n，粒子的速度为vk，i，则粒子的平均速度为
证明由于在初始阶段，粒子的平均速度较大，随着粒子位置的不断更新，由可知，粒子速度不断减小，导致平均速度相对减小，群体也开始慢慢收敛，即其平均速度的变化的趋势与收敛的趋势是一致的，因此选取平均速度作为控制变异步长的自适应参数。证毕。
② 提出柯西变异算子的离散性。由此性质可知，柯西分布具有比高斯分布更加离散的取值，更有利于算法跳出局部最优。因此，AS 策略引入的变异算子为柯西变异算子，并将其与参数结合，根据式(17)对陷入局部最优的粒子进行位置更新，跳出局部最优。
证明由于f(x)与g(x)都是以x=μ对称，因此要证明f(x)＞g(x)，只需证明当x＞N时，f(x)＞g(x)即可。令显然存在N＞ 0时，使W(x)＞ 0，即，即可知f(x)＞g(x)，证毕。
③设计边界限制参数η。由于C(1)是引入的柯西算子，是由t=1 的柯西分布函数产生的随机数，并不能得到有效搜索区域，因此，在进行数据集搜索时，对搜索区域进行边界限制，只对满足边界限制参数η的数据区域进行搜索。
定理8边界限制参数。假设x0为xi的中位数，和分别表示xi左侧和右侧的尺度参数，则参数η为
对于任意的x，满足
证明由于x0为xi的中位数，即(x-x0)2的均值表示粒子位置维度的2 阶中心矩，减少了粒子的离散化程度和噪声的影响。可以有效防止参数η过大而影响算法2 的收敛。而由于x满足
2)质心初始化
在通过AS 策略进行自适应参数选取，保证不会陷入局部最优解之后，便可以进行质心的初始化。其具体过程如下。
①将每个网格单元的数据看作一群粒子S1，S2，…，Sm，并通过式(3)～式(5)对其进行初始化。
③计算参数η的值，获取有效搜索区域，根据更新的适应值，结合式(6)与式(7)在有效搜索区域中对粒子的速度与粒子的位置进行更新。
局部聚类的伪代码如算法2 所示。
算法2局部聚类
输入初始数据集S，粒子的初始位置x和始速度v，簇数K，自适应参数
输出质心数据集
2.3.3 局部簇并行化计算
在对网格单元的数据质心初始化之后，便需要对网格单元进行并行化合并，获取局部簇，实现局部并行化聚类。因此，本文提出并行化局部聚类策略SPPLCS，实现对局部簇的并行化计算来完成整个局部聚类的过程。其基本步骤如下。
1)将各个网格单元G1，G2，G3，…，Gm分配到Partition。
2.4 局部簇合并
为了解决局部簇并行化合并效率低的问题，本文提出了局部簇合并策略CRNN，该策略结合Spark计算框架将相似度大的簇进行合并，提高了局部簇并行化合并效率。其主要步骤如下。
2)对于簇Ci，Cj，通过邻居节点集疏密程度判断2 个簇之间的亲密程度，并分别计算出2 个簇的样本点数ni，nj，提出簇的相似性函数CSM(ni，nj)，计算出簇与簇之间的相似度。
定理9簇的相似性函数。设nei和nej分别为Ci和Cj之间的邻居节点和非邻居节点的个数，ni和nj分别为簇和簇的样本点的个数，则簇的相似性函数表示为
局部簇合并的伪代码如算法3 所示。
算法3局部簇并行化合并
输入局部簇
输出局部簇的并行化合并
2.5 算法时间复杂度分析
PDC-SFASPSO 算法的时间复杂度主要由网格单元的获取、局部簇的形成以及局部簇的并行化合并三部分构成，时间复杂度分别如下。
1)网格单元的获取阶段的时间复杂度主要取决于数据集的粗略划分、网格划分、网格单元的离群点过滤。设数据集的样本点数为n，维度数为m，网格单元个数为p，Partition 数为r，则网格单元的获取阶段的时间复杂度为
2)局部簇的形成阶段的时间复杂度主要取决于簇数的获取、质心初始化、局部并行化聚类。设有q个局部区域覆盖，g个全局最优值，w个有效搜索区域，即粒子的自适应平均速度只需迭代w次，对于参数η便只需更新lgw次，令最大迭代次数为Iter，则局部簇的形成阶段的时间复杂度为
3)局部簇的并行化合并阶段的时间复杂度主要取决于计算簇半径与邻居节点，通过相似度进行簇的并行化合并。假设簇数为k，分布式节点数为d，则其时间复杂度为
综上可知，PDC-SFASPSO 算法的时间复杂度为
其中，w≪n，因此nw≪n2。由于g≪n，r≪n，d≪n，k≪n，因此最终的时间复杂度近似为
SP-DAP 算法对划分后的数据进行并行化聚类阶段的时间复杂度为。由于该算法并没有计算出局部聚类簇数，导致没有较优的初始化质心，因此并行化聚类的迭代次数要远大于 PDC-SFASPSO 算法。因此，而O(n2lgn)≫，因此，PDC-SFASPSO 算法的时间复杂度要低于SP-DAP 算法。
对于SP-GAKMS 算法，由于该算法在使用群智能算法初始化质心时，会导致陷入局部最优，并不能获取较优的初始质心。因此，其算法的迭代次数也远大于PDC-SFASPSO 算法，导致并行化聚类阶段的时间复杂度。所以，PDC-SFASPSO算法的时间复杂度低于SP-GAKMS 算法。
对于SP-LCMNS算法，设对边的迭代次数为e，则该算法的数据划分的时间复杂度为(2)O n e，在对数据集进行并行化聚类时，仅仅使用了二次划分算法进行优化，并未在并行化聚类之前对数据集进行簇的生成，导致了并行化聚类的迭代次数增多。因此该阶段的时间复杂度为
其中，Iter′≫Iter，u≫q，故PDC-SFASPSO 算法的时间复杂度要低于SP-GAKMS 算法。
综上可知，相较于SP-DAP 算法、SP-GAKMS算法与SP-LAICA 算法，PDC-SFASPSO 算法有更理想的时间复杂度。
3.1 实验环境
为了验证PDC-SFASPSO 算法的性能，本文设计了相关实验。在硬件方面，实验包括4 个计算节点，即一个master 节点和3 个worker 节点，并修改主机名分别为master、salve_1、salve_2、salve_3。所有节点的CPU 均为Inter Core i5，2.50 GHz 四核CPU，16 GB 内存，512 GB 存储磁盘。实验环境中的4 个节点处于同一个局域网中，所有的计算节点通过1 Gbit/s 以太网相连。在软件方面，使用CentOS6.0系统安装Hadoop 2.7.7，从而配置Hadoop集群，对每个节点都安装JDK1.8.0 并完成节点的集群配置。安装Hive1.1.2 与Spark2.2.0，使用Hive将HDFS中的数据进行分析和管理。在Spark 并行计算框架的基础上，使用Scala 编程语言对数据进行处理，并将处理好的数据导入集群。最后使用Superset 对集群中处理好的数据进行可视化处理。各个节点的具体配置如表1 所示。
表1 实验中节点的配置
3.2 实验数据
本节实验采用4 个真实的数据集，分别是Online Retail、N_BaloT、Health News 及Bag words[20]。其中，Online Retail 数据集包含非商店在线零售的所有交易；
N_BaloT 是从9 台商业物联网设备收集的真实数据；
Health News 包含来自超过15 个主要健康新闻机构的健康新闻；
Bag words 包含5 个文本集合。这些数据集的详细信息如表2 所示。
表2 实验数据集
3.3 评价指标
3.3.1 加速比
加速比是通过并行计算来降低总体运行时间而获得的性能提升的数值化表示形式，其定义为
其中，T1表示算法在单节点上的运行时间；
Tp表示并行计算的运行时间；
Sp越大，表示算法的并行化效率越高。
3.3.2 NMI
标准互信息（NMI，normalized mutual information）通过对信息进行量化度量，并根据2 个概率分布的信息熵的差值进行聚类的效果评估，其定义为
其中，X和Y为N维向量，I(X，Y)表示X和Y之间的互信息，H(X)和H(Y)分别表示X和Y的熵；
NMI 值越大，聚类效果越好。
3.3.3 ARI
调整兰德指数（ARI，adjusted Rand index）是通过将模型的超分布假设为随机模型从而用于聚类模型的性能评估，该评价指标具有更高的区分度，其定义为
3.4 PSO 算法的优越性分析
文献[21]中MSPSO 算法通过保留粒子历史最优位置，重新初始化其他粒子，提高了粒子多样性，扩大了搜索空间，从而获取全局最优解。因此，为验证ASPSO 算法的优越性，本文选取MSPSO 算法、PSO算法、ASPSO 算法在4 个不同基准函数（Sphere、Schwefel、Ackely、Griewank）进行仿真实验，函数的具体信息如表3 所示。算法参数设置如下：采用线性下降惯性权重，并且w在[0.35，0.95]内取值随迭代数增加而线性递减。学习因子c1和c2均为1.5，种群规模为40，函数维度为30，收敛阈值ε设置为10-5，边界值vmax为0.5Range，并设置ASPSO 算法的尺度参数为[-100，100]。为对算法进行统计算分析，将每个函数独立运行50 次，其结果如表4 所示。
表3 基准测试函数
表4 ASPSO 算法与PSO 算法的性能对比
从表4 可以看出，ASPSO 算法的平均值与标准差始终低于PSO 算法与MSPSO 算法，ASPSO算法在收敛精度和应用在不同类型函数的稳定性方面明显优于PSO 算法与MSPSO 算法。尤其是在高维多峰函数f3与f4上，PSO 算法的标准差分别为6.332 与3.289，很显然，未优化的PSO 算法所在的搜索区域有多个极值点，且快速收敛陷入了局部最优解，相较于标准差仍保持理论较优的ASPSO 算法，其全局搜索能力与稳定性明显远低于ASPSO 算法。这是因为ASPSO 算法采用了AS策略，设计了控制变异步长参数与边界限制参数，对粒子位置进行更新，
帮助粒子跳出局部最优，获取全局最优解。从函数f1与f2可以看出，ASPSO 算法的标准差接近理论最优值0，具有较高的收敛精度，极大地体现了ASPSO 算法较强的跳出局部极值能力和较好的全局搜索能力。实验表明，在全局寻优能力和算法稳定程度方面，ASPSO 算法明显比传统PSO 算法具有更好的优越性。
3.5 聚类过程性分析
由于Bag words 数据集具有样本数量多、属性多的特点。因此，选取Bag words 数据集对算法进行聚类过程性分析。算法首先采用PCCV 策略对数据集进行划分，获取网格单元。由于数据集包含多维特征属性，聚类效果不易观测，因此将数据网格单元投影到二维空间进行演示。其中图1 展示了部分网格单元数据点的分布。然后，通过ASPSO算法获取各个数据网格单元的质心点集，通过SPPLCS 策略将质心点与其他网格单元中心距离最近的2 个数据网格单元进行并行化合并，获取局部簇，图2 展示了部分局部簇数据点的分布。最后，采用CRNN策略计算出各个簇之间的邻居节点数，依据邻居节点数，并结合CSM(ni，nj)函数对簇的相似性进行判断，将相似度大的局部簇进行合并，从而完成并行化聚类。图3 显示了第一轮2 个簇合并的数据点。
图1 网格单元数据集分布
图2 局部数据点的分布
图3 第一轮2 个簇合并的数据点
3.6 算法可行性分析与并行化效率比较
为了验证PDC-SFASPSO 算法的可行性并比较各个算法之间的并行化效率，使用算法的加速比来进行衡量。并对每一个数据集都运行20 次，取其均值作为实验结果，如图4 所示。
图4 各算法处理各数据集的加速比
从图4 可以看出，PDC-SFASPSO 在节点数达到4 时，加速比最大，并且在各个数据集上PDCSFASPSO 的加速比随着节点数的增多而不断增大，尤其是在Online Retail 数据集上，PDC-SFASPSO 的加速比的增长趋势更加明显，很好地体现了PDC-SFASPSO 的并行化可行性。其中，当节点数达到4 时，在Online Retail 数据集上，PDC-SFASPSO的加速比相较于SP-DAP 算法、SP-GAKMS 算法和SP-LAICA 算法分别增加了0.3、0.28、0.4；
在N_BaloT数据集上，PDC-SFASPSO 的加速比相较于SP-DAP算法、SP-GAKMS 算法和SP-LAICA 算法分别增加了 0.3、0.26、0.4；
在 Bag words 数据集上，PDC-SFASPSO 的加速比相较于SP-DAP 算法、SP-GAKMS 算法和SP-LAICA 算法分别增加了0.03、0.02、0.1。产生这些结果的原因如下：一方面，PDC-SFASPSO 采用了PCCV 策略，解决了数据间离散系数较大与算法抗干扰性差的问题，间接地提高了聚类的并行化效率；
另一方面，算法在并行化合并阶段设计了相似性函数CSM(ni，nj)进行相似度判断，极大地提高了局部簇并行化合并的效率。因此，在4 种数据集中，PDC-SFASPSO 相较于其他3 种算法具有最佳的并行化效率且具有可行性。
3.7 聚类效果与算法性能比较分析
在目前基于Spark 计算框架的并行聚类算法中，SP-DAP 算法[7]、SP-GAKMS[10]算法和SP-LAICA算法[15]在对数据集进行并行化聚类时，分别在数据集划分阶段、局部聚类阶段与局部簇并行化合并阶段进行了算法的优化，解决了数据离散系数较大、局部簇质心随机性以及局部簇并行化合并效率低等问题，从而极大地提高了算法的聚类效果，相较于大多数基于Spark 的并行聚类算法有着更优的聚类效果、并行效率和时间效率等性能，因此本文选择这3 种算法与提出的PDC-SFASPSO 算法进行聚类效果、并行效率与时间效率等比较与分析。
3.7.1 聚类效果比较分析
1)NMI 值比较
使用NMI 作为衡量指标评价算法的聚类效果，分别比较各个算法在不同数据集上的NMI 值，从而对各个算法的聚类效果进行分析。因此，为了验证PDC-SFASPSO 算法的聚类效果，将4 种算法在上述4 种数据集上进行比较，通过比较NMI 值来体现算法的聚类效果，并分别运行10 次得出聚类结果，取其聚类结果均值并结合一定的误差范围作为实验结果。实验结果如表5 所示。
表5中的数据表明，在聚类效果方面，各算法的NMI 值随着数据集的特征属性增多而不断减小，PDC-SFASPSO 算法在4 种数据集上始终表现得最好。其中，在Online Retail 数据集中，PDC-SFASPSO 算法的NMI 值相比于SP-DAP、SP-GAKMS和SP-LAICA算法分别高出了3.2%、4.9%和2.9%；
在N_BaloT 数据集上，分别高出了7.3%、8.4%和9.3%。产生这种结果的主要原因是PDC-SFASPSO 采用PCCV 策略解决了数据离散系数较大与算法抗干扰性差的问题，并且在对局部簇质心进行初始化时，提出了策略ASPSO，获取了全局最优初始质心，解决了局部簇质心随机性的问题，极大地提高了聚类效果。
表5 各算法处理数据集的NMI 值
2)ARI 值比较
为了进一步验证PDC-SFASPSO 算法的聚类效果，使用ARI 作为衡量指标评价算法的聚类效果，将4 种算法分别在上述4 种数据集上进行处理，并分别运行10 次得出聚类结果，取其聚类结果均值作为实验结果，如图5 所示。
从图5 可以看出，在对各数据集进行处理时，PDC-SFASPSO 算法的ARI 值始终保持最高，并且随着数据集的特征属性增多，PDC-SFASPSO 的ARI值与其他3 种算法的ARI 值相比较，PDC-SFASPSO算法的优势更加明显。尤其是在Bag words 数据集上，PDC-SFASPSO 凭借着设计了PFGF 策略，其ARI 值远高于SP-LAICA。在Online Retail 数据集上PDC-SFASPSO 算法的ARI 值相比于SP-DAP 算法、SP-GAKMS 算法和SP-LAICA 算法分别高0.02、0.03和0.04，在Bag words 数据集上分别高0.06、0.10和0.12。产生这些结果的主要原因是PDC-SFASPSO算法设计了ASPSO 策略获取局部簇质心，解决了局部簇质心的随机性问题。并且PDC-SFASPSO 算法在初始化质心之前，设计了PFGF 策略来获取局部聚类的簇数，解决了算法局部簇簇数难以确定的问题，从而提高了算法的聚类效果。因此，通过对比算法在 4 种数据集上的 ARI 值可以看出，PDC-SFASPSO 算法具有最佳的聚类效果。
3.7.2 性能比较分析
1)抗干扰性比较
为了验证PDC-SFASPSO 与其他3 种算法在大数据集下并行化聚类的抗干扰性，通过利用Sklearn中的函数生成一种具有缺失值的噪声数据集，将其分成多份，分别依次加入上述4 种数据集中。将ARI 值作为评价指标，对加入含有缺失值噪声数据的算法的聚类效果进行比较。通过比较算法的聚类效果来对算法的可抗干扰性进行分析，算法聚类效果越好，则算法受噪声数据的影响越小，即算法的可抗干扰性越好[14]。实验结果如图6 所示。
从图6 可以看出，随着噪声数据的不断增加，各算法的ARI 值逐渐减小，PDC-SFASPSO 在4 种数据集中的ARI 值始终保持最高，具有更好的聚类效果，并且噪声数据越多，PDC-SFASPSO 算法的抗干扰能力相较于其他3种算法优势越加明显。其中，当噪声数据达到50%时，在Online Retail 数据集上，PDC-SFASPSO的ARI值相较于SP-DAP、SP-GAKMS和SP-LAICA 算法分别高21%、27%、33.3%；
在Bag words 数据集上，PDC-SFASPSO 的ARI 值分别高32.3%、49.1%、40.9%。产生这些结果的主要原因是由于最开始没有加入噪声数据，ARI 值达到最大，当加入噪声数据后，算法的ARI 值会因为噪声数据的突然加入，呈现快速下降的趋势，因此在噪声数据为20%～40%时，算法的ARI 值下降最快。而PDC-SFASPSO 算法由于设计了PCCV 策略，提高了算法的聚类效果，并通过设计离群因子GOF来对离群点过滤，减小了噪声数据对算法聚类效果的影响，极大地增强了算法的抗干扰能力。同时，通过对比图6(b)～图6(d)可以看出，随着噪声数据的不断增加，PDC-SFASPSO 算法的ARI 值一直保持最优，这也证明了PDC-SFASPSO 算法具有最佳的抗干扰性。
图6 算法处理各数据集的ARI
2)算法运行时间比较
将PDC-SFASPSO、SP-DAP、SP-GAKMS 与SP-LAICA 算法分别在Online Retail、N_BaloT、Health News 及Bag words 数据集上进行对比实验，分析各个算法的运行时间，实验结果如图7 所示。
图7 算法在各个数据集上的运行时间
从图7 可以看出，随着数据集的属性与数据量的增多，算法运行的时间开销也逐渐增大。并且PDC-SFASPSO 算法在4 种数据集上的运行时间始终最低。其中，在Health News 数据集上，相较于Online Retail 数据集算法的时间开销产生了明显的增长，分别增加了38.2%、73.5%、79.6%、85.9%，然而对于PDC-SFASPSO 算法，其时间消耗增加的始终较为平缓。产生此结果的主要原因是PDC-SFASPSO 算法使用了网格划分策略PCCV 解决了数据间离散系数较大的问题与算法抗干扰性差的问题，从而提高了算法的聚类效果，间接地提高了并行化合并效率；
此外，在并行化阶段，PDC-SFASPSO 算法设计了CRNN 策略，极大地减小了聚簇时间消耗，解决了局部簇并行化合并效率低的问题。因此，PDC-SFASPSO 算法在各个数据集上相对于其他3 种算法时间消耗始终处于最低。
针对传统的划分聚类算法在大数据环境下的不足，本文提出了一种基于Spark 框架和ASPSO 策略下的并行划分聚类算法PDC-SFASPSO。该算法在数据划分阶段提出了网格划分策略，保证了划分后的数据网格单元数据离散系数较小，并设计了离群因子过滤网格单元数据，增强了数据的抗干扰性；
使用基于PFGF 的搜索策略对数据进行核覆盖搜索获取局部簇簇数，并提出ASPSO 优化算法，通过自适应参数避免算法陷入局部最优解从而获取全局最优质心；
提出了局部簇并行化合并策略CRNN，通过避免对所有簇的点与边集同时展开搜索而提高算法局部簇的并行化合并效率。为了验证PDC-SFASPSO算法的性能，本文设计了相关实验，在Online Retail、N_BaloT、Health News和Bag words 数据集上将PDC-SFASPSO 算法分别与SP-DAP、SP-GAKMS和SP-LAICA 算法进行比较。实验结果显示，与其他算法相比，PDC-SFASPSO 算法在处理大数据时具有相对较好的性能表现。但是，该算法仍有一些需要改进及完善的地方，如数据的特征约简与负载平衡等问题，这些都是下一步重点研究的问题。
