0 引言

随着云计算技术的大面积普及与应用，集群的规模将越来越大^[1]；同时节点间频繁的迁移、备份、失效处理等高耦合性操作对集群的任务调度和资源分配造成了巨大的困难^[2-4]。一种有效的处理方案是：把集群节点按照工作状态聚类，同一聚类中的节点具有相同的负载状态，如CPU占用率、内存占用率、I/O吞吐量、磁盘空间、网络通信状态等。文献[5]运用模糊聚类技术把计算机划分成若干个能力均衡的逻辑集群；文献[6]使用改进的C均值聚类算法计算出集群节点聚类中心和分类结果。但是目前所有聚类算法都不能保证完全准确地把每一个实例划分到合理的类，如果给出节点属于各个类的概率来形成概率聚类，将有助于消除传统聚类问题中硬性而快速的判断方案引发的脆弱性^[7]。在聚类的实际应用中已经有学者使用了概率模型^[8-10]，然而使用概率模型对集群节点按工作状态聚类的应用尚未见诸文献。

对相空间理论的研究发现，传统相空间同样适用于云计算系统的分析。文献[11]首次提出云计算相空间的概念，为分析云计算集群提供了思路；文献[12]提出了多尺度量子谐振子算法(Multi-scale Quantum Harmonic Oscillator Algorithm, MQHOA)，其在收敛过程中波函数的特征对集群概率聚类具有启发作用；文献[13]基于MQHOA的高斯采样提出了一种聚类中心选取算法，证明了MQHOA用于聚类的可行性，但该算法不适用于密度分布呈多峰特性的数据集。本文在相空间的基础上利用多尺度量子谐振子算法的搜索聚焦能力，根据其收敛过程中波函数变化的概率解释，提出了基于多尺度量子谐振子算法的相空间概率聚类算法(Phase Space Probabilistic Clustering Algorithm base on Multi-scale Quantum Harmonic Oscillator Algorithm, PSPCA-MQHOA)，并通过三种模拟集群实验验证了PSPCA-MQHOA能适用于多种负载状态的集群。

1 相空间模型与多尺度量子谐振子算法 1.1 相空间投影与网格化

目前基于云计算相空间的研究已经有一定的成果^[14-16]。文献[11]给出了云计算相空间的一般定义：在云计算系统中以服务器的n个工作状态参数为坐标轴所形成的n维空间称为云计算系统的相空间。

对于只考虑两个工作状态x和y的拥有p个节点的集群，可以由相空间中的点集C表示：C={(x_i, y_i):i≤p}。某集群节点的CPU占用率和内存占用率在相空间中的投影如图 1所示，进一步将相空间划分为n×n的网格，根据每个网格在相空间中的位置附加坐标，投影到相空间的节点就必然落入某一个网格中。

将相空间如上述过程网格化后便可以运用MQHOA对节点进行聚类。如果把每一个网格当成一个点，落在网格中的节点数量当成函数值，整个相空间就可以抽象为一个离散的目标函数F(x, y)，其定义域为：1≤x≤n², 1≤y≤n²(x, y为整数)。此时网格取代连续目标函数中的点成为最小的计算单位，落入网格中的节点越多视为更优的采样位置，聚类的过程转化为优化问题，网格划分得越密计算的结果越精确。

1.2 多尺度量子谐振子算法在PSPCA-MQHOA中的应用

量子力学以其完备的理论成为现代物理学的基础支柱之一，在多种技术中得到了广泛的应用，其中量子谐振子的运动规律对优化问题有重要的启示。多尺度量子谐振子算法(MQHOA)就是一种模仿量子谐振子从高能态向基态收敛过程的函数优化算法，文献[17]详细介绍了其物理模型。MQHOA的波函数表示了目标函数在定义域上最优解出现位置的概率密度，由算法在函数优化的收敛过程中高斯函数的叠加形成。文献[12]给出了MQHOA在高维坐标分量x_i的归一化波函数公式:

$ \psi {\rm{(}}x{\rm{)}} = \sum\limits_{i = 1}^k {\frac{1}{{\sqrt {2{\rm{ \mathsf{ π} }}} \sigma k}}\exp [-\frac{{{{(x-{x_i})}^2}}}{{2{\sigma ^2}}}]} $

(1)

PSPCA-MQHOA的概率聚类过程就是寻找网格化相空间中局部包含节点最多的网格的过程，其波函数表示了网格化相空间中包含节点最多的网格出现位置的概率密度，以此波函数可以确定聚类个数, 计算各网格中节点分属于各聚类的概率。PSPCA-MQHOA过程可以视为MQHOA对一个离散目标函数的多峰优化过程。

2 PSPCA-MQHOA 2.1 PSPCA-MQHOA原理分析

根据MQHOA在相空间上的优化过程设计PSPCA-MQHOA的基本思想：将集群工作状态投影到相空间，把相空间划分为n×n个网格。在n×n个网格中随机选取k个网格作为采样网格集合K。对K中每一个采样网格k_i(1≤i≤k)按标准差为当前尺度σ_s的高斯函数N(k_i, σ_s²)生成新的网格，若新网格中的节点数大于采样网格k_i中的节点数，则用新网格替换采样网格k_i。如此对每一个k_i进行m次高斯采样，然后计算采样网格位置之间标准差变化量的最大值MAX(Δσ_k)，若MAX(Δσ_k)小于当前尺度σ_s，则把当前尺度σ_s减半，重复进行以上过程直到当前尺度σ_s小于预定义的停止尺度σ。以此形成一种类似于MQHOA多峰问题的解决办法。

如图 2为尺度收敛下采样网格的移动情况，图中网格中的数字表示被投影到该网格的节点数，被阴影覆盖的网格为当前采样网格，图 2(a)~(d)分别为尺度在12.5、6.25、3.125、1.562 5下的采样网格位置，从中可以看出随着算法尺度的收敛，采样网格朝着局部节点数最多的网格聚拢。

2.2 PSPCA-MQHOA基本流程

算法1  PSPCA-MQHOA。

输入  集群状态相空间, 采样网格个数k, 采样参数m, 算法停止尺度σ, 搜索尺度σ_s；

输出  集群节点概率聚类的结果。

步骤1  把集群状态相空间划分为n×n的网格，随机生成k个初始采样网格。

步骤2  对每一个采样网格k_i，按标准差为σ_s的高斯分布N(k_i, σ_s²)生成新的采样网格，若生成的网格包含更多节点则用新网格更新当前采样网格，每个采样网格重复此过程m次。

步骤3  若k个采样网格位置标准差变化量的最大值MAX(Δσ_k)满足MAX(Δσ_k)≥σ_s, 则返回步骤2，否则进入步骤4。

步骤4  若σ_s≥σ，搜索尺度减半σ_s=σ_s/2，返回步骤2；否则算法结束，此时的波函数图像就表示集群的概率聚类。

PSPCA-MQHOA的迭代过程由嵌套的两种收敛组成：多尺度收敛和量子谐振子收敛。其中多尺度收敛的次数在网格划分完成后是固定不变的；对于量子谐振子收敛，后续的实验表明其次数在同一尺度下通常为1。

2.3 算法结果分析

PSPCA-MQHOA的输出结果为在停止尺度σ下的波函数，由于PSPCA-MQHOA的波函数表示了包含节点最多的网格出现位置的概率分布，所以波函数图像波峰的位置就是节点数最多的网格最有可能出现的位置，即聚类的中心，波峰的数量则是聚类的数量。类似于量子谐振子处于基态时波函数由多个高斯函数叠加形成，此时的波函数由多个高斯函数在聚类中心处叠加形成。将组成波函数的若干个高斯函数分离出来单独讨论可知，每一个高斯函数都是由数个采样网格在某处聚集形成，则此处必然是一个全局或局部节点数最密集的区域，自然地在这个区域就存在着一个聚类。若将每一个高斯函数代表一个聚类，那么高斯函数的函数值就是网格中节点属于其代表聚类的概率贡献，因此每一个网格中的节点都有属于各个聚类的概率贡献，将其归一化后就得出了节点属于各个聚类的概率。综上所述，对算法输出的波函数进行如下处理后形成了集群节点的概率聚类：

假设算法停止时波函数图像有c个波峰，则该集群节点按工作状态可分为c个聚类，记为C_i。坐标为(x, y)的网格处的波函数值为c个高斯函数在(x, y)处的叠加，即：Ψ(x, y)= $ \sum\limits_{i = 1}^c {f(x, y, i)} $，其中f(x, y, i)为第i个高斯函数在网格(x, y)处提供的波函数值，则网格(x, y)中的节点分属于各类的概率为：P[C_i|(x, y)]=f(x, y, i)/Ψ(x, y)。

3 实验分析

本章在二维相空间下对PSPCA-MQHOA进行实验，对算法参数进行分析，以确定实验中使用的算法停止尺度σ、采样网格个数k和采样参数m的选取；然后对三种模拟集群的工作状态进行概率聚类实验，输出其波函数图像，并与传统聚类算法进行比较。

3.1 实验参数的分析

PSPCA-MQHOA的精确性与网格的划分有密切关系，网格划分得越密算法的结果越精确，然而计算开销越大。实际情况中需要根据集群中节点的数量动态调整网格划分的密度，因此不详细讨论网格的划分密度。为确定实验参数使用的测试数据为拥有四个聚类中心的二维数据集，其在相空间的投影如图 3所示，并假设相空间划分为n×n个网格，参数k、m、σ将以n的倍数进行取值。

3.1.1 算法停止尺度σ的分析与选取

算法停止尺度σ的取值直接关系着波函数的形态，σ取值过大则算法过早停止，波函数在聚类位置叠加次数不足，如图 4(a)所示为σ=n/2时波函数的俯视图；σ取值过小则算法收敛过度，波函数在聚类中心处过度叠加，如图 4(b)所示为σ=n/30时波函数的正视图。实验的σ取值为n/2与n/30之间的一个合适的中间值σ=n/10，其波函数图像俯视图如图 4(c)所示。

3.1.2 采样网格个数k、采样参数m的分析与选取

PSPCA-MQHOA参数k、m的选取会影响算法得到的聚类个数和聚类的位置。通过使用召回率(Recall)和精确率(Precision)来衡量k、m取值不同时算法测试结果的好坏。其中：召回率R侧重于考查算法的查全率，计算方式如式(2) 所示；精确率P侧重于考查算法的查准率，计算方式如式(3) 所示。

$ R = {\rm{算法得出的与测试数据吻合的聚类数/测试数据的聚类数}} $

(2)

$ P = {\rm{算法得出的与测试数据吻合的聚类数/算法得出的所有聚类数}} $

(3)

以相空间网格密度n的不同倍数对参数k、m进行取值，组成若干个不同的k、m参数组合，对测试数据进行聚类实验，记录10次实验的平均召回率和精确率，如表 1所示。从表 1可以看出，参数k、m共同影响算法的召回率和精确率。当k较小时，算法的召回率较低，这是因为采样网格数过少，无法全面覆盖所有局部节点最多的网格；当m较小时，算法的精准率较低，这是因为算法以高斯采样寻找更优网格的次数过少，采样网格没有完全聚集到局部节点最多的网格。随着参数k、m取值的增大，算法的召回率和精确率趋近于1。理论上参数k、m越大算法越稳定，计算开销也越大。同时考虑到算法的稳定性与效率，实验参数k、m的取值为：k=n×1.5, m=n×2.0。

3.2 概率聚类实验

实验使用的数据为三种不同负载状态下的模拟集群Cluster1、Cluster2、Cluster3。其中：Cluster1处于低负荷状态；Cluster2处于负载不均衡状态；Cluster3中有两组节点负荷相似。它们在网格化的相空间投影如图 5所示。

下面使用PSPCA-MQHOA对上述三种集群按工作状态进行概率聚类，网格密度n为20，实验参数为σ=n/10，k=n×1.5，m=n×2.0。算法输出的波函数如图 6所示。图 6(a)为三种集群状态波函数的正视图，图 6(b)为三种集群状态波函数的俯视图。从图 6可以看出，PSPCA-MQHOA的波函数图像正好对应了集群节点的聚类情况，算法不仅可以应用在节点数量少、负载状态单一的集群，对节点数量多、负载不均衡的集群也同样适用，同时能区分集群中负载状态十分相似的节点。

在算法的两种收敛中，量子谐振子收敛的次数由采样网格移动情况与当前搜索尺度的关系决定，上述实验中这种关系如图 7所示。从图 7中可以看出，采样网格位置标准差变化量的最大值均小于当前搜索尺度，即每次量子谐振子收敛过程中，只需进行一次高斯采样便可生成满足条件的采样网格，当前尺度下量子谐振子收敛次数为1。这是由于网格化的相空间是一个定义域取值范围很小的离散目标函数，每次采样后网格位置的变化都非常小。因此，PSPCA-MQHOA的性能只与网格划分、集群工作状态数量和参数k、m有关，与相空间的投影情况(即集群负载情况)无关。

使用2.3节所述的方法将集群节点进行聚类，并将聚类结果与经典聚类算法K-means和DBSCAN(Density-Based Spatial Clustering of Applications with Noise)进行比较，如表 2所示，其中K-means算法在数据集Cluster1、Cluster2、Cluster3中K取值分别为1、3、2。

从表 2可以看出：对于Cluster1，由于聚类只有一个，各算法的效果相当；对于Cluster2和Cluster3，K-means算法的效果最好，但K-means算法比较依赖K的设定。在不需要提前设定聚类个数的算法中，PSPCA-MQHOA的效果略好于DBSCAN算法。

4 结语

PSPCA-MQHOA将相空间离散化后作为MQHOA的目标函数，将普通的聚类问题转化为MQHOA的多峰优化问题，并用波函数表示集群的概率聚类。通过对三种模拟集群的聚类实验，验证了PSPCA-MQHOA能适用于多种负载状态的集群，并且算法具有迭代次数少、结果直观明确等优点。使用波函数对集群节点进行概率聚类也给云计算系统分析、云计算监控、负载均衡调度等工作提供了新思路。