试论基于模糊聚类算法的资源整合

【摘 要】为解决云计算环境中硬件资源整合问题，分析了云中互联资源的属性，提出一种改进模糊聚类算法。该算法放宽规约条件，考虑到矩阵中数据点的关系无法比较，定义加权因子并构建新的目标函数，先随机选取硬件作为初始聚类中心，然后不断计算隶属度确定聚类中心，重复迭代改进目标函数优化数据集的划分，最后获取属性相似的逻辑资源池。实验结果表明改进算法收敛速度较快，得到的聚类结果较好，适合云环境中具有相似属性的资源整合。

【关键词】资源属性；加权因子；目标函数；模糊聚类；评价函数

0.引言

随着计算机软硬件技术的不断发展，新的计算模式相继涌现，IBM公司于2007年底宣布了云计算计划[1]，云计算开始被业界关注。云计算是一种全新的模式，它可以将相对集中互联的大规模资源进行整合并以服务的形式提供给用户，既方便了用户，又提高了资源的利用率。但对于硬件服务提供商来说，为了满足用户的需求，保证服务的质量，在云计算环境中应投入多少资源来应对可能出项的短暂峰值成为一个亟待解决的问题，因为从经济学的观点来看，如果需求没有较大的增长而不断加大硬件资源的投入，纯利润会降低，甚至变成负值。因此行之有效的方法是将互联的空闲硬件资源进行整合，组成更大的逻辑资源池并以租赁的方式对外提供，硬件服务商仅需支付少量的费用租赁应对短暂的峰值，实现商家和用户的利益双赢。

1.基于改进模糊聚类算法的硬件资源整合

1.1资源描述

云环境中硬件资源有多重属性，本文仅从以下五方面来考虑，任一资源HVi的资源属性可描述为：

HVi={CPU，Memeory，BandWidth，Cost，GeLoc}

其中，CPU表示运行速度，用Ghz来衡量；Memeory表示内存大小，用容量来衡量；BandWidth表示网络带宽，用Mbps.s-1来度量；Cost表示每秒运行资源的成本，用￥.s-1；GeLoc表示资源所在的地理位置，我们可以采用地区号来表示。

1.2聚类中心的选取

资源有其固有的地理位置，硬件服务商如需租赁资源，考虑到运行成本、速度等因素，应选择本地区或周围地区的逻辑资源池。在此引入变量r，若GeLoc值相同，则r=0，认定是本地区的逻辑资源池；若0

本研究的聚类个数c由租赁者指定，任选本地区或周围地区的c个硬件资源构成的初始聚类中心为{ω1，ω2…，ωc}。

1.3数据矩阵与目标函数

1.3.1构建数据矩阵

设互联的硬件资源数目为n，集合X= {X1，X2，…，Xn}表示，其中每个资源Xi有m个属性，用向量Xi=（xi1，xi2，…，xim）表示，则得到的数据空间为：

X={Xi|Xi=（xi1，xi2，…，xim），1≤i≤n}

1.3.2目标函数的改进

模糊C-均值聚类算法的目标函数J及其约束条件如下：

J（U，c1，…，cc）=■Ji=■■u■■d■■ （1）

■uij=1，？坌j=1，…，n （2）

在公式（1）中，uij为隶属度，表示数据点与类中心的关系；公式（2）为约束条件，要求每个数据点xj与c个聚类中心的总和为1。正式由于这个条件的限制，使得聚类中心不能独立，对噪声数据比较敏感，因此对隶属度函数的约束条件（2）修改为：

■uij>0，？坌j=1，…，n （3）

数据与聚类中心的关系由uij表示，但相对于同一聚类中心，不同数据点的关系无法描述。

图中A，B，C为三个数据点，x，y，z为聚类中心。点C对三个聚类中心的隶属度分别为0.2，0.5，0.3，经比较可知点C属于类中心y的可能性较大。但对于类中心y来说，数据点A，B，C的关系无法比较，因此，提出一个加权因子。

定义1 加权因子Mij，表示相对于同一聚类中心ci各数据点的归属程度，其公式如下：

Mij=uij*（Mi）-1 （4）

其中，Mi=■uij>0，？坌j=1，…，n （5）

改进的新目标函数为：

J（U，ω1，…，ωc）=■Ji=■■u■■M■■*（xj-ωi）■ （6）

应用Lagrange乘数法求解出聚类中心为：

ci=■，？坌i=1，…，n （7）

隶属度为：

uij=■■■ （8）

1.3.3算法描述

集合X = { X1，X2，…，Xn}为需要整合的硬件资源，输入聚类个数c和最大迭代次数k，误差ε，参数m=2，执行下列步骤：

Step1 确定初始聚类中心{ω1，ω2…，ωc}，并令k=1；

Step2 根据公式（8）计算隶属度；

Step3 根据公式（7）更新聚类中心；

Step4 计算误差e=■ci（k）-ci（k-1）■，若e

基于加权因子的模糊聚类算法，不仅考虑了数据点对各聚类中心的距离，还考虑了相对同一类中心各数据点的关系，有效地克服了基于欧式距离的算法特点。

2.实验仿真及结果分析

2.1实验数据与结果

为验证算法的有效性，故构建100台计算机且满足条件r，需对数据进行预处理。数据的预处理分两步：一是对GeLoc进行数值化，我们可以按各地市区号的升序排，排好后从0开始赋值实现数字化。二是标准化，除GeLoc外把其余四个属性数值按下列公式规划到区间[0，1]上：

x'ik=■（i=1，2，…，n；k=1，2，…，m） （9）

其中：

■=■■xik，sk=■ （10）

数据标准化之后，分别应用改进的聚类算法进行分类，以及采用经典的C-均值算法分类。对比发现前者数据点更集中，并经常有数据点与类中心重合的现象，类与类之间的界限也很明显，出现此现象主要是因为加权因子Mij，Mij-1类似于一个放大镜，它将所有的距离进行放大，但尺度不同；距离近的点放大的尺度小，而距离远的点放大的尺度要大一些，于是导致两极分化，距离近的数据点变得更近，距离远的点也就变得更远，使得聚类效果更好。

2.2评价标准

从图中我们可以直观地看出改进聚类算法的效果，但聚类算法还须通过评价函数进一步来验证。聚类结果的评价一般采用两种方式，内部评价和外部评价，本文采用内部评价函数ESSE来作为评价标准，见公式（11）。

ESSE=■■（d（xi，cj））2 （11）

其中，nj表示第j个聚类中的元素数；d（xi，cj）为数据xi与聚类中心cj的距离；ESSE值越小，表示聚类效果越好。

测试时，聚类数目c分别等于2，3，4，迭代10次，取平均值为最终结果。改进聚类算法的均方误差ESSE值偏小，更好地反映出改进聚类算法在聚拢效果上的高效性和稳定性。

3.结束语

云环境下的资源种类繁多、功能各异，通过本文提出的基于加权因子的改进模糊聚类算法可以获得若干个逻辑池，而每个逻辑池中的资源属性特征相近，适合运行同一类计算任务，使用成本为资源池中每个资源的Cost总和，提高了资源的利用率。实验结果表明，改进算法加快了收敛速度，降低了算法的时间复杂度，得到较好的聚类划分。但算法中参数m只能根据经验给出，聚类数目c只能通过反复试验得出，缺乏理论支持，需进一步研究改进。

【参考文献】

[1]Sims K.IBM introduces ready-to-use cloud computing collaboration services get clients started with cloud computing.2007.http：///press/us/en/pressrelease/22613.wss.

[2]刘伯成，陈庆奎.云计算中的集群资源模糊聚类划分模型[J].计算机科学，2011，38（s1）.