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

程志伟

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

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

中图分类号：TP301文献标识码：A文章编号：1009-3044（2012）33-8006-04

1概述

随着计算机软硬件技术的不断发展，新的计算模式相继涌现，IBM公司于2007年底宣布了云计算计划[1]，云计算开始被业界关注。云计算是一种全新的模式，它可以将相对集中互联的大规模资源进行整合并以服务的形式提供给用户，既方便了用户，又提高了资源的利用率。但对于硬件服务提供商来说，为了满足用户的需求，保证服务的质量，在云计算环境中应投入多少资源来应对可能出项的短暂峰值成为一个亟待解决的问题，因为从经济学的观点来看，如果需求没有较大的增长而不断加大硬件资源的投入，纯利润会降低，甚至变成负值。因此行之有效的方法是将互联的空闲硬件资源进行整合，组成更大的逻辑资源池并以租赁的方式对外提供，硬件服务商仅需支付少量的费用租赁应对短暂的峰值，实现商家和用户的利益双赢。关于云计算环境中集群资源模糊聚类划分的问题，国内处于起步阶段，出现了一些研究成果：文献[2]和文献[3]通过引进误差容忍向量和资源需求向量机制来获得逻辑资源池，文献[3]对集群中的节点进行了规范化和量化，二者均没有考虑到资源的商业特性，同时传统模糊聚类算法对噪声数据敏感，收敛速度慢。针对以上问题，该文充分考虑资源运行成本属性，改进聚类算法，放宽了规约条件同时提出了新的目标函数，并构建数据集，通过仿真实验和评价函数来验证算法的可行性。

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

2.1资源描述

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

HVi=｛CPU，Memeory，BandWidth，Cost，GeLoc｝

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

2.2聚类中心的选取

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

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

2.3数据矩阵与目标函数

2.3.1构建数据矩阵

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

2.3.2目标函数的改进

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

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

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

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

隶属度为：

2.3.3算法描述

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

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

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

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

Step4计算误差[e=i=1c||ci（k）-ci（k-1）||2]，若e<ε，则输出划分的矩阵和聚类中心ω，否则转向step2，重复执行step2～step4；

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

3实验仿真及结果分析

3.1实验数据与结果

为验证算法的有效性，故构建100台计算机且满足条件r，每台机器的属性如表1（仅列出20台机器）所示：

表中数据均为原始数据，若直接用于聚类处理，恐影响聚类结果，故需对数据进行预处理。数据的预处理分两步：一是对GeLoc进行数值化，我们可以按各地市区号的升序排，排好后从0开始赋值实现数字化。二是标准化，除GeLoc外把其余四个属性数值按下列公式[5]规划到区间[0，1]上：

数据标准化之后，应用改进的聚类算法进行分类，结果见图2所示；采用经典的C-均值算法分类见图3所示：

对比两图可发现图2中的数据点更集中，并经常有数据点与类中心重合的现象，类与类之间的界限也很明显，出现此现象主要是因为加权因子Mij，Mij-1类似于一个放大镜，它将所有的距离进行放大，但尺度不同；距离近的点放大的尺度小，而距离远的点放大的尺度要大一些，于是导致两极分化，距离近的数据点变得更近，距离远的点也就变得更远，使得聚类效果更好。

3.2评价标准

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

表2中改进聚类算法的均方误差ESSE值偏小，更好地反映出改进聚类算法在聚拢效果上的高效性和稳定性。

4结束语

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

参考文献：

[1]SimsK.IBMintroducesready-to-usecloudcomputingcollaborationservicesgetclientsstartedwithcloudcomputing.2007.http：//www-03.ibm.com/press/us/en/pressrelease/22613.wss

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

[3]那丽春.集群资源模糊聚类划分模型[J].计算机工程，2012，38（6）.

[4]JamesCBezdek.PatternRecognitionwithFuzzyObjectiveFunctionAlgorithms[M].NewYork：Plenum，1981：128-132.

[5]陈健美，宋顺林，陆虎，等.改进模糊聚类算法及其在入侵检测中的应用[J].东南大学学报，2007，37（4）.

[6]LiuYuan-chao，WangXiao-long，XuZhi-ming，etal.Asurveyofdocumentclustering[J].JournalofChineseInformationProcessing，2006.

[7]王飞，张德贤，韩金淑，等.蚁群优化与模糊聚类结合的文本聚类研究[J].计算机工程与应用，2010，46（32）.