均值聚类

均值聚类（共8篇）

均值聚类 篇1

link

appraisement

industry

point

实行学分制使得因材施教成为可能, 为学生的个性化发展提供了基础, 同时, 也给学校的学生日常管理工作带来了巨大的挑战。为了更好地管理学生, 文中使用K均值对学生进行聚类, 给出了具体的聚类方法和实行过程, 在实验中采用三种不同的距离计算方法对学生进行聚类, 表明了该方法是有效的。

随着高等教育教学改革的不断深化, 各地高校为适应高等教育大众化、阶段多样化的要求, 都积极探索并实施学分制的管理模式。实行学分制给学生的个性培养和教学的因材施教提供了良好的发展空间, 但从学校方面来说, 学分制下的学生管理突破了原有的学生管理体制, 对学生管理提出了严峻的考验。

在学分制下, 虽然每一个学生的自由度加大, 但是整个学校里所有的学生在长期会有一些相同或相似的情况, 即所谓的“物以类聚, 人以群分”, 如果能根据长期以来的学生的表现对学生进行聚类, 使得同一类的学生有更多的共同点, 不同类的学生有较大的不同, 然后可以针对不同类型的学生采用不同的方法进行管理, 不仅可以提高管理的针对性, 而且可以更好的研究不同类型的学生的具体情况, 为以后的学生选课、就业等方面提供一些有益的建议。

聚类是将数据分类到不同的类或者簇这样的一个过程, 所以同一个簇中的对象有很大的相似性, 而不同簇间的对象有很大的相异性。K均值聚类算法是一种有效的聚类技术, 具有对大型数据集进行高效分类的特点, 因此, 本文采用该方法对学生进行聚类。

K均值聚类

k均值聚类是最著名的划分聚类算法, 由于简洁和高效使得其成为所有聚类算法中最广泛使用的。具体的计算过程如图1所示。

基于K均值的学生聚类

聚类不仅可以降低学生管理的难度, 而且使得学生管理具有针对性和高效性的优点;K均值是一种有效的聚类算法, 因此本文其应用于学生管理。由于学生的身高、性别、年龄等这些因素对于学生管理的意义不大, 而性格虽然重要, 但是数据很难收集, 而学生在学校的首要根本任务是学习, 而且学完课程都会有一个考试来检验学习的效果, 因此, 成绩数据不仅数据量大, 而且可以指导学生此后的选课及教学计划的制定, 因此, 文中使用学习成绩对学生进行聚类。具体的流程如图2所示。

(1) 数据预处理

由于描述成绩的数据可能是数值或者是等级这样的模糊值, 为了计算的方便, 需要对模糊数据进行数值化, 在本文中, 根据图3的对应关系进行数值化。

(2) 缺失值的处理

由于在收集数据的过程中各种因素导致的数据缺失是不可避免的, 因此, 需要对项目中存在的缺失值进行处理。常用的缺失值处理方法有删除存在缺失值的个案和缺失值插补。删除法是对缺失值进行处理的最原始方法, 它将存在缺失值的个案删除。由于成绩数据缺失的情况现有发生, 因此, 本文使用该方法对缺失值进行处理。

(3) K均值聚类

对成绩进行处理以后就可以聚类了, 首先确定将成绩聚为几类, 并确定相应的聚类中心;然后分别使用欧氏距离、余弦距离和相关度三种方法计算每一个同学的成绩与各个聚类中心的距离进行聚类;最后, 根据聚类结果重新计算聚类中心, 重复该过程直到收敛。

实验

本文以某校计算机专业的一个班一年的成绩为例进行实验, 使用前文的模糊数值和缺失值的处理方法进行数据预处理, 然后使用matlab对其进行聚类, 三种距离计算方法的聚类结果如图4, 5, 6所示。

结束语

本文探讨了在学分制下的学生管理工作, 并采用K均值方法对学生进行聚类, 并给出将K均值聚类算法应用于学生聚类的步骤和具体实施过程, 表明了该方法的有效性。

均值聚类 篇2

摘要：基于93个土壤表层样品重金属Cu、Zn、Cr、Cd、Pb和Hg全量浓度分析数据,应用模糊分类方法结合地统计学手段,对南京市边缘带梅山钢铁厂附近总面积约14 km2样区内的土壤重金属污染状况进行了空间预测.结果显示,样区北部及东北角区域的土壤遭受重金属元素Cu、Zn、Cr、Cd的轻微污染,样区西侧沿长江呈带状分布的土壤由于其重金属环境容量较低,存在潜在污染风险,样区其它区域的`土壤未发现由上述重金属元素导致的污染现象.样区东北角土壤Pb、Hg污染严重,并与Cu、Zn、Cr、Cd污染在空间上重叠,是土壤重金属污染控制与土壤修复的重点区域.样区的东部和东北部区域土壤受Pb、Hg中度污染,在梅山集团的北部土壤轻微污染.研究表明,与直接对重金属浓度分析数据实施插值分析的常规克里格方法相比,模糊c-均值聚类结合地统计学方法获得的空间预测结果蕴含信息更加丰富,而模糊集理论及其相关算法在土壤学诸多领域中也具有极大的应用潜力.作 者：檀满枝 陈杰 郑海龙 张学雷 TAN Manzhi CHEN Jie ZHENG Hailong ZHANG Xuelei 作者单位：檀满枝,TAN Manzhi(中国科学院南京土壤研究所土壤与农业可持续发展国家重点实验室,南京,210008;中国科学院研究生院,北京,100039)

陈杰,张学雷,CHEN Jie,ZHANG Xuelei(中国科学院南京土壤研究所土壤与农业可持续发展国家重点实验室,南京,210008)

郑海龙,ZHENG Hailong(香港中文大学地理与资源管理系)

隐隶属度模糊c均值聚类算法 篇3

聚类分析是数据挖掘和模式分类中的一个重要研究部分,是非监督分类的重要方法。模糊C均值聚类FCM[1,2]是聚类分析领域的一种典型算法,它将聚类问题采用数学形式表达、并以非线性规划优化理论作支撑、求解过程依靠计算机实现、并具有良好的聚类性能,因此成为聚类分析领域的研究热点及主流。FCM算法及改进算法[3,4,5]被广泛应用于图像处理[6,7,8]、模式识别、故障检测等领域。

FCM算法也存在一些不足,如容易陷入局部最优解; 对类别K值的选择没有准则可依循; 对初始赋值及异常数据较为敏感等。为获得全局最优解,研究者主要依靠并行生物优化算法对FCM算法进行求解,目的在于克服FCM梯度爬山法局部极小点的缺陷。文献[4]在FCM算法中引入生物遗传算法( GA)求解,以期提高FCM算法全局寻优性能,类似的方法还包括文献[5],文献[5]引入粒子群算法( PSO) 实现对FCM算法的求解; Zhang等人[6]利用PSO和PCM实现基于马氏距离的图像分割方法; 文献[7]提出不确定c均值聚类算法VCM( Vague Cmeans Clustering algorithm) ,引入真实聚类隶属度和虚假聚类隶属度,并利用QPSO进行算法求解; 文献[8]提出基于PSO的动态加权FCM算法,以达到提高雷达跟踪目标精度的目的; 文献[9]将FCM及fuzzy PSO算法结合起来,从而有效提高聚类算法的性能。基于生物寻优算法求解的模糊聚类算法,一般首先针对聚类中心进行编码,然后基于目标函数及梯度法得到模糊隶属度迭代公式,聚类算法在AO交替迭代的过程中,需要分别计算模糊隶属度和聚类目标函数,而二者存在重复计算的内容,从而降低了算法的计算效率。提出隐隶属度模糊c均值聚类HMFCM,首先将FCM模糊隶属度公式带入FCM目标函数,从而得到无模糊隶属度的HMFCM目标函数,使得HMFCM目标函数仅包含聚类中心,然后利用PSO算法对聚类中心进行编码求解,最后利用样本与聚类中心间距离进行类别估计。HMFCM仅需利用PSO算法对聚类中心进行编码及计算聚类目标函数,而省略了对模糊隶属度的计算,从而提高了算法的计算效率,理论分析了算法的相关性质,通过仿真实验验证了算法的有效性和时效性。

1 隐隶属度模糊C均值聚类( HMFCM)

1. 1 模糊c均值聚类( FCM) 及粒子群算法( PSO)

FCM用值在0 到1 之间的隶属度确定每个样本属于各个组的程度,FCM最优化准则为:

利用梯度法得到FCM的模糊隶属度及聚类中心迭代公式,如式(2)、式(3)所示:

粒子群优化算法(PSO)是Eberhart等人在1995年提出的群智能自适应进化搜索算法,已成功应用于大量非线性、不可微和多峰值复杂问题的优化[10,12]。基本PSO算法中每个粒子都是优化问题的一个可行解,结合粒子位置和飞行速度决定其下一代粒子位置,经过逐代搜索最后找到最优解。在每一代迭代中,每个粒子根据自身最优pbest和全局最优gbest来修正自身飞行速度。

粒子的速度及位置更新公式分别为:

其中c1、c2为加速因子,取为正的常数; r1、r2为[0,1]之间的随机数,w称为惯性因子。

1. 2 HMFCM目标函数

HMFCM算法构造思路: 对于给定的聚类中心,将FCM模糊隶属度公式带入FCM目标函数中,则将目标函数转换为与模糊隶属度无关的函数,从而在目标函数中隐藏了模糊隶属度并降低了目标函数复杂度。

对于给定的聚类中心,首先将FCM模糊隶属度式( 3) 进行整理,得到:

从而有:

即有:

将式(7)两边乘以uij并对i求和,则有:

将式(8)两边对j求和,从而将FCM目标函数转换为HMF-CM目标函数:

式(9)即为HMFCM算法的目标函数,且在式(9)中模糊隶属度信息被隐藏了,即HMFCM算法仅与聚类中心有关。

1. 3 HMFCM聚类中心求解

由于HMFCM目标函数隐藏了模糊隶属度,所以无法类似FCM利用梯度法及AO交替迭代法对聚类中心及模糊隶属度进行估计,考虑采用粒子群算法( PSO) 在聚类中心解空间中搜寻最优解。

PSO算法以实数形式对聚类中心进行编码,每个粒子由c个聚类中心的d维分量组成,粒子除了位置值之外,还有速度和适应度函数,每个粒子位置和速度都是c × d维变量[12]。

定义HMFCM适应度函数为:

1. 4 HMPCM迭代流程

HMPCM算法采用下列步骤确定聚类中心及类别判决,迭代步骤为:

步骤1

初始化多个c × d维粒子的位置Xi( 0) 和速度Vi( 0) 。

步骤2

将粒子位置Xi( t) 的每d维分量构成一组对应为一聚类中心ck,从而实现聚类中心矩阵P的初始化。

步骤3

用式( 10) 计算多个粒子的适应度函数值。如果迭代次数超过某个限值,或群体最优解适应度相对上次群体最优解适应度的改变量小于某个阈值,则算法停止。

步骤4

记录及更新个体最优解Pi( t) 和群体最优解Pg( t) ,进而更新粒子速度Vi( t + 1) 及位置Xi( t + 1) ,返回步骤2。

由于HMFCM算法不存在模糊隶属度,而在目标函数计算中得到了样本与聚类中心距离,在模糊聚类算法中,样本与聚类中心距离是与模糊隶属度成反比例关系的,考虑采用样本与聚类中心距离决定样本的类别归属。聚类算法的核心思想在于距离越小类别归属度越大,当确定聚类中心后即可确定样本与聚类中心距离,最大隶属度类属确定原则等价于最小距离类属确定原则。从而HMFCM对样本xj的聚类类别判定为:

2 HMFCM性质分析

2. 1 HMFCM算法复杂性比较

模糊聚类算法的复杂度由每次迭代时参量的计算复杂度及迭代次数所决定。由于HMFCM采用粒子群算法对聚类中心寻优,所以可以将HMFCM算法与基于PSO聚类中心寻优的FCM算法( PSO-FCM) 进行比较。

在单次迭代中,HMFCM算法的复杂度直接由目标函数的复杂度决定,由式( 9) 可知,HMFCM目标函数的乘法计算复杂度为O( ncd) ,其中n为样本个数,c为类别数,d为样本维数。

当FCM算法基于PSO进行聚类中心寻优时,需要根据式( 2) 模糊隶属度及根据式( 1) 计算目标函数,则在一次迭代中,PSO-FCM的乘法复杂度由计算模糊隶属度及目标函数的复杂度所决定。在单次迭代中,由式( 2) 可知,模糊隶属度的复杂度为O( cd) ,因此结合式( 1) 可知,PSO-FCM目标函数的复杂度为O( nc2d) 。

因此HMFCM算法复杂度低于PSO-FCM的算法复杂度,从而降低了计算量、提高了运算效率,同时由于计算量的减少,有助于算法计算精度的提高,进而改进算法的聚类效果。

2. 2 HMFCM算法收敛性分析

HMFCM算法依赖PSO算法对聚类中心进行寻优及估计,因此HMFCM算法的收敛性取决于PSO算法的收敛性,粒子群算法的迭代寻优收敛性证明已经有大量研究工作和研究成果[13,14]。HMFCM算法采用基本PSO算法进行参数估计及目标函数求解,并在PSO算法收敛参数范围内取值,PSO算法迭代收敛性保证了EFCM算法迭代过程的收敛性。

3 仿真实验

为了验证HMFCM算法的有效性和计算效率,将HMFCM算法与FCM、PSO-FCM算法进行对比测试。

3. 1 公共测试数据集

基于UCI机器学习数据库中的公共数据集进行算法比对测试,所选数据集包括Iris、Wine两个数据集,两个数据集的信息如表1 所示。

3. 2 实验参数设置

粒子群优化算法采用实数编码,一个编码对应于一个可行解,每个粒子的维数为c × d维,其中c为类别数,d为样本维数,c × d维表示了c个聚类中心的总维数,针对Iris数据集的测试时,c = 3,d = 4 ; 针对Wine数据集的测试时,c = 3,d = 13 ; 粒子群适应度函数定义如式( 10) 所示,式( 10) 以倒数形式将模糊聚类目标函数最小化转化为PSO适应度函数最大化。粒子数取为20,迭代次数100 次,粒子位置的每维参数取值范围取为[0,100]。利用FCM、PSO-FCM及HMFCM算法做算法比对测试,共进行10 次试验,计算各类聚类平均精度。

3. 3 实验结果及分析

实验结果包括两个部分,一是各算法的聚类精度,另外一个是考察PSO-FCM及HMFCM算法测试时实验耗时的比对。由于FCM算法采用梯度法求解参量,迭代次数较少,用时较短,因此没有比对FCM算法迭代耗时的需要,而PSO-FCM与HMFCM利用PSO算法迭代寻优。

实验结果如表2、表3 所示。

同时基于Iris数据集,记录PSO-FCM算法在m = 2 及m =3 时的平均运行时间为: 30. 431. 秒; 记录HMFCM算法在m = 2及m = 3 时的平均运行时间为: 30. 195 秒。

基于Wine数据集,记录PSO-FCM算法在m = 2 及m = 3 时的平均运行时间为: 31. 102 秒; 记录HMFCM算法在m = 2 及m = 3 时的平均运行时间为: 31. 073 秒。

在聚类精度方面,当对Iris数据集测试时,HMFCM算法表现更优,当对Wine数据集测试时,PSO-FCM与HMFCM算法相差不多,没有明显的差异,且都略低于FCM算法。这说明不同的聚类算法适用于特定不同的数据集,需要针对数据集特性研究分析适用的聚类算法。在运算效率方面,FCM算法由于是梯度法,迭代速度是最快的,迭代的次数也是最少的。而基于PSO的聚类算法一般要求按迭代次数迭代,HMFCM算法不需计算模糊隶属度,可以直接计算聚类目标函数及PSO适应度函数,相较于PSO—FCM算法,在算法运算时间上略微占优,但并不非常明显。

4 结语

模糊聚类[15]广泛的应用于模式分类及数据挖掘领域。隐隶属度模糊c均值聚类算法( HMFCM) 将FCM模糊隶属度代入FCM目标函数中进行约简,从而得到无模糊隶属度的简化目标函数。并采用PSO算法对聚类中心进行估计,同时利用样本与聚类中心距离进行类别判决。理论性质分析表明新算法降低了原有算法的复杂度,仿真实验验证了所提出算法的有效性及时效性。这种隐隶属度方法有助于降低算法复杂度,进而提高算法精度和效率,可以进一步满足实际问题对聚类算法实效性的要求。下一步工作将把此方法推广到其他聚类算法中去。

摘要：针对基于粒子群的模糊聚类算法运算效率较低的问题,提出隐隶属度模糊c均值聚类算法HMFCM(hidden-membership fuzzy c-means clustering)。HMFCM算法将FCM模糊隶属度迭代公式代入FCM目标函数中约简,得到无模糊隶属度的HMFCM目标函数,并利用PSO算法对聚类中心进行编码寻优,最后利用样本与聚类中心距离进行类别判决。HMFCM算法无需计算样本模糊隶属度,降低了聚类算法复杂度,提高了算法的计算效率及精度,而且该方法可以推广到其他基于生物寻优的聚类算法。通过仿真实验验证了所提出算法的有效性和时效性。

一种改进的k-均值聚类算法 篇4

k-均值算法属于聚类技术中一种基本的划分方法,具有简单、快速的优点。其基本思想[1]是选取k个数据对象作为初始聚类中心,通过迭代把数据对象划分到不同的簇中,使簇内部对象之间的相似度很大,而簇之间对象的相似度很小。算法中参数k的值是事先给定的,并在数据对象集中随机选取k个数据对象作为初始聚类中心。一些研究[2,3,4,5]指出,如果初始聚类中心选取不当,k-均值算法的聚类结果可能会陷入局部最优解,从而得不到较好的聚类效果,本文的实验也证实了这一点。怎样从这些局部最优中找到一个较好的聚类结果是一个值得研究的问题。

本文对k-均值算法的初始聚类中心选择方法进行了改进,提出了一种从数据对象分布出发动态寻找并确定初始聚类中心的思路以及基于这种思路的改进算法。实验表明,与传统随机选取初始聚类中心的方法相比,改进后的方法有效改善了它的分类性能,并取得了较高的分类准确率。

1 k-均值算法

算法1 k-均值算法

输入:聚类个数k,以及包含n个数据对象的数据样本集;

输出:满足方差最小标准的k个聚类;

步骤:

(1) 从n个数据对象中任意选择k个对象作为初始聚类中心;

(2) 循环执行(3)到(4),直到每个聚类不再发生变化为止;

(3) 根据每个聚类中所有对象的均值(中心对象),计算样本集中每个对象与这些中心对象的距离,并根据最小距离重新对相应对象进行划分;

(4) 重新计算每个(有变化)聚类的均值(中心对象)。

由以上算法可知,k-均值算法的初始聚类中心是随机选定的,其聚类结果受初始聚类中心的选择影响较大。

2 k-均值改进算法的思想

在k-均值算法中,选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率,本文研究的目的就是如何找到与数据在空间分布上尽可能相一致的初始聚类中心。对数据进行划分,最根本的目的是使得一个聚类中的对象是相似的,而不同聚类中的对象是不相似的。如果用距离表示对象之间的相似性程度,相似对象之间的距离比不相似对象之间的距离要小。如果能够寻找到k个初始中心,它们分别代表了相似程度较大的数据集合,那么就找到了与数据在空间分布上相一致的初始聚类中心。

为了找到与数据在空间分布上相一致且相似程度较大的数据集合,采取下列步骤:

(1) 计算数据对象两两之间的距离;

(2) 找出距离最近的两个数据对象,形成一个数据对象集合A1,并将它们从总的数据集合U中删除;

(3) 计算A1中每一个数据对象与数据对象集合U中每一个样本的距离,找出在U中与A1中最近的数据对象,将它并入集合A1并从U中删除,直到A1中的数据对象个数到达一定阈值;

(4) 再从U中找到样本两两间距离最近的两个数据对象构成A2,重复上面的过程,直到形成k个对象集合;

(5) 最后对k个对象集合分别进行算术平均,形成k个初始聚类中心。

假设有一个2维数据集,包含有12个对象,其分布如图1所示。

假设要把它们划分为2类,按照上面的思想寻找初始聚类中心。a、b之间的距离最近,那么选择a、b构成一个数据对象集合A1,并将它们从总的集合U中删除。U中与A1相邻最近的对象是c,这样便将c加入A1集合并将它从U中删除。如果规定每个数据集合中所包含对象最大个数为4,则A1中将会再添加对象d。然后在U中再找出相互之间距离最近的两个对象g、h构成A2并将它们从U中删除。U中与A2相邻最近的对象是i,这样便将i加入A2并将它从U中删除,同样j也会并入A2。最后,将这两个对象集合分别进行算术平均,形成两个初始聚类中心。这样得到的初始聚类中心与实际样本的分布更加相符,从而可以得到更好的聚类效果。

3 基本概念

为便于说明问题,给出如下定义:

定义1 数据对象x=(x1,x2,…,xp)和y=(y1,y2,…,yp)之间的距离为:

$d(x,y)=\sqrt{(x{}_1-y{}_2){}^2+(x{}_2-y{}_2){}^2+\Lambda +(x{}_p-y{}_p){}^2}$

定义2 一个数据对象x与一个数据对象集合V之间的距离,定义为这个数据对象与这个数据对象集合中所有数据对象当中最近的距离:

d(x,V)=min(d(x,y),y∈V)

定义3 两个对象集合S和V之间的距离,定义为两个集合S和V中最近的两个数据对象x和y之间的距离:

d(S,V)=min(d(x,y),x∈S,y∈V)

4 改进的初始聚类中心选择算法算法2 初始聚类中心选择算法

假设数据对象集合U有n个数据对象,要将其聚为k类,m的初值为1。算法描述如下:

输入:聚类个数k,包含n个数据对象的数据样本集;

输出:满足方差最小标准的k个聚类;

步骤:

(1) 计算任意两个数据对象间的距离d(x,y),找到集合U中距离最近的两个数据对象,形成集合Am(1≤m≤k),并从集合U中删除这两个对象;

(2) 在U中找到距离集合Am最近的数据对象,将其加入集合Am,并从集合U中删除该对象;

(3) 重复(2)直到集合中的数据对象个数大于等于 a*n/k ( 0<a≤1);

(4) 如果m<k,则m←m+1,再从集合U中找到距离最近的两个数据对象,形成新的集合Am,(1≤m≤k),并从集合U中删除这两个数据对象,返回(2)执行;

(5) 将最终形成的k个集合中的数据对象分别进行算术平均,从而形成k个初始聚类中心。

从这k个初始聚类中心出发,应用k-均值聚类算法形成最终聚类。

5 实验分析

实验环境:P4 CPU,512MB内存,80GB硬盘,Windows 2000操作系统,VC++6.0编程语言。

实验数据:选自UCI数据库中的Iris数据集、Wine数据集和我们自己收集的Web用户数据集HWU1和HWU2。

实验方法:首先采用算法2寻找并确定初始聚类中心;在此基础上再应用算法1形成最终聚类结果。

实验结果:改进算法与随机选取初始聚类中心方法的比较如表1所示。

从表1可以看出:

(1) 随机选取初始聚类中心的方法从不同的初始中心出发会得到不同的聚类结果,聚类准确率有很大的差别,很不稳定,难以确定其是否可用。例如,对Iris数据集,多次随机选择聚类中心,最高准确率可以达到89.33%,最低仅为52.00%;对于HWU2数据集,多次随机选择聚类中心,最高准确率可以达到60.78%,最低仅为50.98%。产生这样结果的原因就是随机选择聚类中心的方法没有考虑到数据的分布情况,而只是给出了一个算法可以运行的必要条件(有初始聚类中心)。

(2) 改进后的算法能够得到较高且稳定的准确率。针对数据集Wine、HWU1可以得到最高准确率的聚类结果,针对数据集Iris、HWU2可以得到接近最高准确率的聚类结果。产生这样结果的原因就是改进后的算法首先根据启发式算法来寻找数据,因而产生的初始聚类中心比较符合数据实际分布,也就更适用于对实际数据的聚类。

6 结束语

本文首先给出了k-均值算法的一般过程,并分析了该算法随机选取初始聚类中心对聚类结果的影响,然后提出了一种从数据对象分布出发寻找初始聚类中心的思想以及基于这种思想的算法过程,并通过实验分析得出改进后的算法能够得到较高且稳定的准确率,更适用于对实际数据的聚类。

参考文献

[1]朱明.数据挖掘[M].合肥:中国科学技术大学出版社,2002.

[2]Kurniawan A,Benech N,Tao Yufei.Towards High-dimensional Cluste-ring[J].COMP,November 1999:1-2.

[3]MacQueen J.Some Methods for Classification and Analysis of Multivari-ate Observations[J].In:Proceedings of 5th Berkeley Symp.Math.Statist,Prob.,1967,1:281-297.

[4]Jolla L.Alternatives to the k-means algorithm that find better clustering[J].In:Proceeding of ACMSIGMOD,1992:192-195.

一种改进的模糊C-均值聚类算法 篇5

模糊聚类广泛地应用于模式识别与图像处理的过程中, 其中模糊C-均值聚类 (FCM) 首先由Bezdek 1981年提出, 以后很多学者针对模糊聚类中选择不同的距离函数得到不同的聚类结果, 并且探索最佳分类的问题。文献[1]利用迭代自组织分析技术 (ISODATA) 遗传算法 (GA) 嵌套构成遗传-迭代自组织分析技术共同执行FCM算法的优化计算。该方法给出了最佳聚类数的一个判别准则, 但是在确定了最佳聚类数目以后仍然存在另一个问题:怎样的分类结果最合适?本文通过对原始数据的预处理将经典的模糊C-均值聚类中的欧氏距离推广到广义欧氏距离, 得到了加权模糊C-均值聚类的迭代公式, 实证分析表明加权模糊C-均值聚类的结果与遗传-迭代自组织分析技术 (ISODATA-GA) 分类的结果基本一致, 但是通过非参数的Friedman检验分类效果优于遗传算法所得结果。

1.1 模糊C-均值聚类的迭代公式

设X={X1, X2, …, XN}⊂Rp, Rp表示p维实数向量空间, 令 uik表示第k个样本属于第i类的隶属度, 0≤uik≤1,

, $0<{\displaystyle \sum _{k=1}^{{\rm N}}u}{}_{ik}<{\rm N},1\le k\le {\rm N},1\le i\le c$, 记vi表示第i类的聚类中心。则X的一个模糊C-均值聚类的就是求如下目标函数的最小值:

$J(U,V)={\displaystyle \sum _{k=1}^{{\rm N}}{\displaystyle \sum _{i=1}^c(}}u{}_{ik}){}^m(d{}_{ik}){}^2(1)$

其中$d{}_{ik}=|x{}_k-v{}_i|$为第k个序列到第i类中心的欧氏距离。

聚类准则取为求J (U, V) 的极小值: (min) {J (U, V) }。模糊c均值聚类的具体步骤如下:

(1) 取定c, m和初始隶属度矩阵U 0, 迭代步数I = 0;

(2) 计算聚类中心V为:

$v{}_i^{(l)}={\displaystyle \sum _{k=1}^{{\rm N}}(}u{}_{ik}^{(l)}){}^{m}x{}_k/{\displaystyle \sum _{k=1}^{{\rm N}}(}u{}_{ik}^{(l)}){}^m(i=1,2,\cdots ,c),(l<m)(2)$

(3) 修正U:

$u{}_{ik}^{(l+1)}=1/{\displaystyle \sum _{j=1}^c\left(\frac{d{}_{ik}}{d{}_{jk}}\right)}{}^{\frac{2}{m-1}}\forall i,\forall k(3)$

(4) 对给定的ε>0, 实际计算时应对取定的初始值进行迭代计算直至$\max \{|u{}_{ik}^t-u{}_{ik}^{t-1}|\}<\epsilon$, 则算法终止, 否则l=l+1, 转向 (2) 。

若 ujk=max{uik}, 则xk∈第j类

1.2 加权模糊C-均值聚类的迭代公式

首先将原始数据矩阵统一趋势化, 得到无量纲矩阵

R= (rij) p×N

其中

rij = |xij-u${}_i^0$|/iqr (xij) (4)

$u{}_i^0=\{\begin{array}{l}\max \left\{x{}_{ij}\right\}\text{当}x{}_{ij}\text{为}\text{效}\text{益}\text{型}\text{指}\text{标}\\ \min \left\{x{}_{ij}\right\}\text{当}x{}_{ij}\text{为}\text{成}\text{本}\text{型}\text{指}\text{标}\end{array}(5)$

iqr (xij) 表示四分位极差。

于是加权模糊C-均值聚类可以表示为如下的规划问题:

$\min J(U,V,c)={\displaystyle \sum _{k=1}^{{\rm N}}{\displaystyle \sum _{i=1}^c(}}u{}_{ik}){}^m(d^{\prime }{}_{ik}){}^2(6)$

$s\cdot t\{\begin{array}{l}0\le u{}_{ik}\le 11\le i\le c,1\le k\le {\rm N}\\ {\displaystyle \sum _{i=1}^{c}u}{}_{ik}=11\le k\le {\rm N}\\ 0＜{\displaystyle \sum _{k=1}^{{\rm N}}u}{}_{ik}＜{\rm N}1\le i\le c\\ 1\le m＜\infty \end{array}$

其中d′ik是无量纲矩阵R中第k个序列到第i类中心的欧氏距离。

2 各地区生产力水平的聚类分析

为了表明加权模糊C-均值聚类公式的优越性, 本文选取文献[3]中的例子进行实证分析。

利用加权模糊C-均值聚类的方法, 可以将各地区生产力水平分为4类, 所得到的结果如下:

第一类:上海、北京;

第二类:天津、江苏、浙江、广东;

第三类:黑龙江、山东、新疆、湖北、海南、吉林、河北、内蒙古、辽宁、福建、河南;

第四类:江西、青海、湖南、宁夏、西藏、重庆、安徽、陕西、四川、广西、云南、山西、甘肃、贵州。

3 加权模糊C-均值聚类的非参数检验

3.1 Friedman检验的思想

设被划分为第i类的N个个体的秩的平均值为Ri·, 即

$R{}_{i\cdot }=\frac{1}{{\rm N}}(R{}_{i1}+R{}_{i2}+\cdots +R{}_{i{\rm N}})i=1,2,\cdots ,s(7)$

若各类别之间有显著差异, 则隶属于某些类别的N个个体的秩将普遍偏大, 而属于其他类别的N个个体的秩相对较小, 因而各Ri·间的差异比较大。若H0为真, 则各Ri·集中在秩的总平均值:

$\begin{array}{l}R{}_{\cdot \cdot }=\frac{1}{s{\rm N}}[(R{}_{11}+R{}_{21}+\cdots +R{}_{s1})+\cdots +(R{}_{1{\rm N}}+R{}_{2{\rm N}}+\cdots +R{}_{s{\rm N}})]\\ =\frac{1}{s{\rm N}}[{\rm N}(1+2+\cdots +s)]=\frac{s+1}{2}\end{array}$

的周围, 而统计量:

$Q=\frac{12{\rm N}}{s(s+1)}{\displaystyle \sum _{i=1}^s(}R{}_{i\cdot }-\frac{s+1}{2}){}^2~\chi {}^2(s-1)(8)$

反映了Ri·在R··附近的分散程度, 若H0不真, 则Q有偏大的趋势, 因此拒绝域为Q≥c, 其中临界值c由PH0{Q≥c}=α确定, 此检验称为Friedman检验。

3.2 聚类效果分析

利用Matlab软件对聚类的结果进行Friedman检验, 检验水平为0.05分别对传统模糊C均值聚类、本文方法进行检验, 结果如表1所示。

显然, 模糊加权聚类方法全部接受原假设, 即认为各类之间没有显著差异, 但是传统的模糊C-均值聚类只有第四类通过检验, 由此可以看出改进的加权模糊C-均值聚类的结果优于传统的方法。

摘要：模糊C-均值聚类是一种经典的聚类方法。针对模糊C-均值算法对初始值敏感、收敛结果易陷入局部极小的问题, 通过对原始数据的预处理, 将欧氏距离推广到广义欧氏距离, 得到了加权模糊C-均值聚类的迭代公式, 实证分析表明改进后的方法得到的分类结果与嵌入遗传算法的分类基本一致, 而且通过非参数检验证实分类效果良好。

关键词：模糊C-均值聚类,遗传算法,非参数检验

参考文献

[1]陈守煜.工程模糊集理论与应用[M].北京:国防工业出版社, 1998:80-87.

[2]Bezdek J.Pattern Recognition with Fuzzy Objective Function Algo-rithms[M].Plenum Press, New York, 1981.

[3]诸克军, 苏顺华, 黎金玲.模糊C-均值中的最优聚类与最佳聚类数[J].系统工程理论与实践, 2005 (3) :52-61.

[4]范金城, 梅长林.数据分析[M].北京:科学出版社, 2002.

[5]雷英杰, 张善文, 李续武, 等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社, 2005.

一种并行的加速k-均值聚类方法 篇6

聚类作为一种典型的数据挖掘方法,目前已在图像识别、股票分析等领域得到成功应用[3,4]。其任务是从大规模数据集中发现相似的类别,将样本划分为多个不重合的子集。在聚类结果中,相同类内样本应具有较大相似性,不同类间样本具有较大相异性。目前,常见的聚类模型包括:划分聚类[5]、层次聚类[6]、密度聚类[7]、网格聚类[8]、概率聚类[9]和谱聚类[10]等。

在这些聚类方法中,k-均值聚类是一种最为经典使用最为广泛的划分聚类方法[11,12]。k-均值聚类方法以各类样本的质量中心代表该类进行迭代,从而通过不断地动态调整各类中心进行聚类。但是,k-均值聚类算法复杂度高,对大规模数据无法进行有效聚类。因此,如何采用k-均值聚类方法解决大规模数据的聚类问题一直是聚类分析领域的一个研究热点。

随着数据挖掘领域处理样本规模的日趋增大,要求研究人员能够提出高效的挖掘算法来处理海量数据问题。并行计算作为一种定量、精细、高效的方法在海量数据挖掘中得到了成功的应用[13]。狭义上的并行计算是指在并行/分布式计算机上所做的计算,从广义上讲,将多个问题同时求解的过程都可以看做是并行计算的过程。尽管目前已经有学者提出了一些基于并行计算的聚类技术以改进传统的聚类方法[14,15],但是,这些技术效率还不足够高,对于大规模数据的聚类问题的处理能力依然有限。因此,如何结合并行计算技术进一步提高k-均值聚类方法处理海量数据的能力依然是一个值得探讨的问题。

针对传统k-均值聚类方法不能有效处理海量数据聚类的问题,该文提出一种基于并行计算的加速k-均值聚类方法。该方法首先将聚类样本随机划分为多个独立同分布的聚类工作集,并在每个工作集上并行进行传统k-均值聚类,对聚类后的每个类计算其中心和半径,通过衡量不同工作集聚成的子类的中心和半径,对不同工作集的子类进行快速合并,并对子类中的少数特殊数据进行二次归并以校正聚类结果,从而有效处理海量数据的聚类问题。

1 基于并行计算的加速k-均值聚类算法

1.1 k-均值聚类方法

设数据集X={x1,∙∙∙,xi,∙∙∙xn}且xi∈Rd,其中n为样本个数,d为样本维度,k为聚类之前指定的聚类个数。传统k-均值聚类算法首先随机选择k个样本作为初始聚类中心C={c1,∙∙∙,cj,∙∙∙,ck},然后计算每个样本xi∈X到聚类中心cj∈C的距离d(xi,cj),根据每个样本到聚类中心的距离将样本划分到与之最近类中,并计算更新后每个类的中心C,如此循环迭代直到更新后的类中心与更新前一致时停止。

由于传统k-均值聚类方法由于在每次迭代聚类时都需要衡量所有样本到每个类中心的距离,因此算法复杂度为O(nkq),其中,q为聚类迭代次数。当数据规模较大时,算法往往需要很多次迭代才能结束,运行效率较低,不能够有效处理海量数据的聚类。

1.2 并行的加速k-均值聚类方法

针对传统k-均值聚类方法不能有效处理大规模数据聚类的问题,该文结合并行计算思想,提出一种基于并行计算的加速k-均值聚类方法(Pk-means)。该方法首先将聚类样本集X随机划分为多个独立同分布的聚类工作集,即X→{X1,∙∙∙,Xj,∙∙∙,Xm},并在每个工作集Xj上并行进行传统k-均值聚类,得到聚类结果Xj→{Xj1,∙∙∙,Xjp,∙∙∙,Xjk}。然后,对于每个聚类后得到的类Xjp(共mk个),求解其类中心cjp和类半径rjp,然后通过衡量不同工作集中类中心之间的相似度,将相似度最高的合并为一个类,类中心(两个不同样本)相似度的求法如下:

与第i个工作集中第p个类合并的第j个工作集中类别确定方法为:

将每个工作集的聚类结果均按照上述规则进行合并,最后得到一个划分,即X→{X1,∙∙∙,Xt,∙∙∙,Xk},并计算其新的中心C={c1,∙∙∙,ct,∙∙∙,ck}及半径R={r1,∙∙∙,rt,∙∙∙,rk}。然后判断聚类结果是否需要更新,若rt<=range,则不更新,否则对子集Xt中符合条件(3)的样本按照式(4)进行更新。

基于并行计算思想的k-均值方法由于将样本划分为n k的大小,且并行执行传统k-均值聚类方法,所以初始复杂度为O(nq'),其中q'为每个工作集进行传统k-均值聚类的最大迭代次数,且易得到q'<

基于并行计算的k-均值方法具体如下:

初始化:设数据集为X={x1,∙∙∙,xi,∙∙∙xn}(其中xi∈Rd),随机划分工作子集参数为m,工作子集聚类参数为k,聚类结果更新参数为range。

Step1:将样本集X随机划分为m个工作子集,即得到划分模式X→{X1,∙∙∙,Xj,∙∙∙,Xm}。

Step2:对每个工作子集Xj进行k-均值聚类,得到每个工作子集的聚类模式Xj→{Xj1,∙∙∙,Xjp,∙∙∙,Xjk}。具体方法如下:

Step2.1:在每个工作子集Xj随机选择k个样本作为初始聚类中心;

Step1.2:根据式(5)计算每个样本xjq与所有不同类Classjp之间的相似度,并将xjq归为与其最相似的类中心所属的类;

Step1.3:根据式(6)计算样本重新分配后的第每个类的中心Cj={cjp}kp=1

Step1.4:若类中心有更新,则返回Step1.2继续聚类,直到类中心不发生更新时迭代停止,得到每个工作子集Xj的聚类结果Xj→{Xj1,∙∙∙,Xjp,∙∙∙,Xjk}。

Step3:根据式(1)计算不同工作子集中的类之间的相似度,并根据式(2)合并工作子集的聚类结果,从而生成对整个数据集X实现k类的划分,即X→{X1,∙∙∙,Xi,∙∙∙,Xk}。

Step4:根据式(3)和式(4)对聚类结果进行更新调整,从而得到更为优秀的聚类结果X→{X1opt,∙∙∙,Xiopt,∙∙∙,Xkopt}。

算法结束。

2 实验结果及分析

为验证基于并行计算的k-均值方法聚类方法处理大规模数据聚类的有效性,该文在一个人工构造的模拟的社会网络社团结构数据集上进行了实验,并将聚类结果与经典k-均值聚类方法所得到的结果进行了比较。实验在1台PC机(2.66Ghz CPU,1G内存)上进行,实验平台是Matlab2008。

为充分反应本文提出的并行加速k-均值聚类方法的有效性,实验构造了两组数据集。第一组数据集中,人工模拟的网络社团机构数据集包含100个顶点,它们被划分成相同大小的4个社团结构,每个社团结构包含25个顶点,且所有顶点的度均符合如下条件:

其中zin为每个顶点随机指向落在相同社团中顶点的有向边数目,zout为每个顶点随机指向落在不同社团中顶点的有向边数目。网络中100个顶点在zin=12,zout=3时被划分成4个社团结构时的示意图如图1所示,第二组实验数据与第一组构造方法一致,但数据规模扩大了20倍。

本文从两个方面衡量了算法的性能,即聚类结果的抱团性和聚类时间。。聚类抱团性的定义如下:

为充分反应本文提出的基于并行计算的加速k-均值聚类方法的性能,实验中与传统k-均值聚类方法进行了对比。两组实验中子集划分参数m分别取5和10,聚类个数参数均为4,聚类结果更新参数为range取当前类的1.2倍数值,所得实验结果见表1。

从以上实验结果可以看出,在构造的网络社团结构数据集上,当样本规模为100时,该文提出的基于并行计算的k-均值聚类方法的J值较高,样本的抱团性较差,聚类时间与传统k-均值聚类方法有一些提高;但是,当样本规模增加到2000时,该文提出的基于并行计算的k-均值聚类方法的J值接近于传统k-均值聚类方法的J值,而聚类的时间则只有传统k-均值聚类方法的25%左右。

综上可看出,由于本文提出的Pk_means聚类方法采用了并行计算的模式,并且采用了独立同分布的样本初始工作集划分方法,因此能够以较高的训练效率处理大规模数据的聚类问题,同时保证了聚类结果的抱团性能。

3 结论

均值聚类 篇7

关键词：聚类分析,差分进化,K-均值聚类算法,Laplace分布,Logistic混沌搜索

K-均值算法是由Mac Queen[1]提出的一种经典的聚类分析算法,它具有算法简单且收敛速度快的优点,但是算法的聚类结果易受初始聚类中心影响,且容易陷入局部最优。近年来许多学者利用各种常用智能优化算法(如遗传算法[2,3]、微粒群优化[4]等)对K-均值算法进行改进,并取得了不错的效果。

由Storn和Price提出的差分进化(Differential Evolution,DE)算法[5]是一种基于群体进化的启发式算法。该算法从原始种群开始,通过变异(Mutation)、交叉(Crossover)和选择(Selection)操作来生成新种群,通过计算每个个体的适应度值,来确定个体的保留或淘汰,然后通过不断迭代运算,引导搜索过程向最优解逼近。文献[6-7]利用差分进化对K-均值算法进行改进,结果表明,与基于传统遗传、微粒群优化等常用进化算法的K-均值改进算法比较,基于差分进化的K-均值改进算法能获得更好性能。但是,传统差分进化算法也存在算法收敛速度与全局寻优能力之间的矛盾,进化后期易出现早熟、停滞现象,通过改变控制参数虽然可以提高算法收敛速度,但是也会造成其全局寻优能力的下降,从而使得基于传统差分进化的K-均值改进算法的性能受到一定影响。

针对上述问题,该文提出一种基于改进差分进化的K-均值聚类算法,基本思想是:在差分进化算法中通过引入Laplace变异算子来提高算法收敛速度和全局寻优能力,同时通过引入Logistic变尺度混沌搜索,以克服传统差分进化算法进化后期可能出现的早熟、进化停滞现象;然后将其用来改进K-均值算法。实验结果证明,该算法具有较好的全局寻优能力,且收敛速度较快。

1 聚类的基本数学模型

设样本集合为X={X1,X2,⋯,Xn},其中Xi={xi1,xi2,⋯,xid}为d维特征向量,聚类问题的目的就是要找到一个划分C={C1,C2,⋯,CK},使得最终的聚类结果满足:

且使得聚类准则函数JC取得极小值,JC为各样本到对应聚类中心距离的总和:

其中Zj为第j个聚类中心,d(Xi,Zj)为样本到对应聚类中心点的欧式空间距离。

2 改进差分进化算法

2.1 传统差分进化算法

传统差分进化算法通过种群内个体间的合作与竞争,保存优良个体,淘汰劣质个体,以实现对全局最优解的搜索,其演化过程包括变异、交叉和选择三种基本操作。

假设初始种群为PG={Xi,G|i=1⋯NP},其中Xi,G={xji,G|j=1⋯D}为第G代种群中的第i个个体,D为优化问题的维数,NP为种群规模。

1)变异操作

随机从种群中选择一个个体作为父代基向量,选择另外不同的个体作为父代差分向量,生成变异个体Vi,G,即

其中a≠b≠c≠i∈[1,NP],NP为种群规模,G为当前种群的代数,F为缩放因子。

2)交叉操作

利用式(4)对种群中第i个个体Xi,G和其对应的变异个体Vi,G实施交叉操作,生成新个体Xi,G。

其中Xi,G为均匀分布概率,CR为交叉概率,Xi,G为随机选取的整数。

3)选择操作

将原种群的个体Xi,G和新个体Ui,G代入式(5)进行选择,适应度更优的个体进入下一代。

其中Xi,G+1为下一代的第i个个体,f为适应度函数。

2.2 Laplace变异算子

由文献[8]可知,基于柯西分布的变异算子能使算法的寻优能力得到很好地提高,而基于高斯分布的变异算子又能够较好地加快算法的收敛速度。

三种分布的密度函数曲线如图1所示,其中Laplace分布的密度函数同高斯分布相似,区别在于高斯分布概率密度用相对于均值的平方差表示,而Laplace分布概率密度用相对于均值的差的绝对值表示,其密度函数如下:

图中Laplace分布的尾部平滑度介于高斯和柯西变异算子之间,故可知Laplace变异算子既可以较好地保持种群的多样性,又可以使算法的收敛速度得到提高。

2.3 Logistic变尺度混沌搜索

为了克服DE算法在进化后期可能出现的早熟、进化停滞问题,使算法更好地收敛到全局最优解,该文在进化过程中引入了Logistic变尺度混沌搜索。

首先采用Logistic方程产生混沌序列,并按以下方式进行[0,1]中混沌序列和解空间中点列变换:

1)在[0,1]空间上随机产生一个N维变量z1=(z11,z12,⋯,z1N),其中

z1i≠0.25,0.5,0.75;i=1,2,⋯N,然后根据Logistic映射产生M个混沌序列zk,k=1,2,⋯,M

2)使用如下公式,将zk映射到解空间上M个点列xk=(xk1,xk2,⋯,xk N):

3)同理,根据下式将解空间的某个解xk映射到[0,1]区间进行混沌变换:

为使算法初期可以尽可能扩大搜索范围,而后期又可以尽量进行局部细搜索,改进算法采用了变尺度的混沌搜索。则式(7)变换为:

其中σ为尺度系数,G为当前迭代次数,Gmax为最大迭代次数。

3 基于改进差分进化的K-均值聚类算法

3.1 个体编码

改进算法个体采用基于聚类中心的实数编码方式,假设要求把数据分成k类,数据维数为d,每个个体是有k个聚类中心组成的向量,且每个聚类中心是d维的向量,所以每个个体是k×d维向量

Xi(c11,c12,⋯,c1d,c21,c22,⋯,c2d,⋯,ck1,ck2,⋯,ckd)

其中i=1,2,…,N,N为个体的数量;cj表示第j个聚类中心,cjl是代表第j个聚类中心的第l维的值。

3.2 早熟判断

在差分进化算法中,适应度函数用于判断种群进化过程中个体所在位置的好坏。衡量聚类效果的好坏,取决于Jc的结果,Jc越小聚类效果越好。所以,该文定义适应度函数如下:f(Xi)=Jc,同时引入早熟判断规则如公式(11)所示。

其中fi为当前个体适应度,fworst为当前最差个体适应度,fbest为当前最好个体适应度,pi随着迭代的进行将逐渐减小。该文设定一阈值,如果低于该阈值且不满足终止条件时,则认为该个体处于停滞状态。

3.3 算法步骤

步骤1:设定个体数N,最大迭代次数Gmax。

步骤2:种群的初始化:随机选取样本作为聚类中心,并计算当前位置适应度值。

步骤3:对于个体Xi,G按3.2描述产生变异算子F。

步骤4:分别根据式(3)执行变异操作,根据式(4)执行交叉操作,生成试验向量Uki,G,根据式(5)执行选择操作。

步骤5:根据个体的聚类中心编码,按照最近邻法则重新划分样本的归属类别。

步骤6:重新计算新的聚类中心,以替代原值。

步骤7:由式(11)判断是否陷入局部最优,若是,则对该个体变尺度混沌搜索,以利于跳出局部最优,转到步骤3。

步骤8:如不满足所设的终止条件,则转到步骤3,同时G的值自增1;否则输出最好个体值Xbest及最好适应度值f(Xbest),算法结束。

4 实验及效果评价

实验分别采用Iris、Wine和Zoo这3个知名数据集作为测试样本集,参数设置如下:种群规模为数据集维数的10倍,最大迭代次数Gmax为50次。其中DE-kmeans算法[6,7]中缩放因子F为0.5,交叉概率CR为0.1;本文算法中缩放因子F为Laplace随机数,交叉概率CR为0.1,阈值σ为0.8。对三种算法单独运行50次,根据适应度函数分别计算出最小值、最大值、平均值以及收敛到最优值所需要的时间。运行结果如表1所示。

从表1可以看出,K-均值算法虽然收敛速度最快,但因初始聚类中心的不同产生的最小适应度值和最大适应度值的差距较大且寻优精度最差;DE-kmeans的适应度相对稳定,但其收敛所消耗的时间较长;而本文所提算法的结果更加稳定,寻优精度更好,且收敛速度也较快。

5 结束语

本文首先在传统差分进化算法中引入Laplace变异算子和Logistic变尺度混沌搜索以提高其性能,然后将改进的差分进化算法应用于K-均值算法。实验结果表明:该文算法较好地克服了传统K-均值算法的缺点,具有较强的全局搜索能力,且收敛速度较快。

参考文献

[1]MacQueen J.Some methods for classification and analysis of multi-variate observations[C]//Proc.of the 5th Berkeley Symposium onMathematics Statistic Problem,1967,1:281-297.

[2]王家耀,张雪萍,周海燕.一个用于空间聚类分析的遗传K-均值算法[J].计算机工程,2006,32(3):188-190.

[3]Michael Laszlo,Sumitra Mukherjee.A genetic algorithm that exchanges neighboring centers for k-means clustering[J].Pattern Recogni tion Letters,2007,28(16):2359-2366.

[4]Omran M G H,Engelbrecht A P,Salman A.Dynamic clustering using particle swarm optimization with application in unsupervisedimage classification[J].Proceedings of World Academy of Science,Engineering and Technology,2005,9(11):199-204.

[5]Storn R,Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Journal ofGlobal Optimization,1997,11(4):341-359.

[6]Paterlini S,Krink T.High performance clustering with differential evolution[C]//Proc.of Congress on Evolutionary Computation,2004,2:2004-2011.

[7]Sudhakar G.Effective image clustering with differential evolution technique[J].International Journal of Computer and CommunicationTechnology,2010,2(1):11-19.

[8]Kuo-Tong Lan,Chun-Hsiung Lan.Notes on the distinction of Gaussian and Cauchy mutations[C]//Proc.of Eighth International Con ference on Intelligent Systems Design and Applications,2008:272-277.

[9]刘兴阳,毛力.基于Laplace分布变异的改进差分进化算法[J].计算机应用,2011,29(10):2719-2722.

[10]沈明明,毛力.融合K-调和均值的混沌粒子群聚类算法[J].计算机工程与应用,2011,47(27):144-146.

[11]张济强,高玉良.遗传模拟退火算法在k-means聚类中的应用[J].电脑知识与技术,2012,8(7):1611-1613.

均值聚类 篇8

调度是指为了实现某一目的而对共同使用的资源实行时间分配[1]。作为调度问题的一个子集,车间调度问题实际上也是一个资源分配问题。问题的求解目标主要是找到一组资源并安排到设备上去,以使作业可被“最优”完成的方案。

舰载机在航母上的调度问题是制约舰载机出动和回收的重要因素。在整个飞行任务实施过程中,舰载机的调运是一个主要的阶段,在航空母舰这样特殊的环境下,如何快速高效地将舰载机从机库转运到飞行甲板,在很大程度上影响着舰载机的起降,从而决定了航母战斗力的形成和提高。以往研究主要集中在飞行甲板调度方面,运筹学领域的图与网络分析法、排队论[2]等研究方法能够很好地解决这些问题。随着以粒子群为代表的群智能算法的研究应用不断深入,群智能优化算法在资源分配及生产调度问题[3]的求解方面较其他算法优势明显,而且能较好地提高问题解的精度。有学者将舰载机舰面布放调度问题转换为带有约束条件的多目标函数求最小解问题,并基于智能粒子群(PSO)算法对戴高乐航母舰载机舰面布放调度问题的解决方法进行了研究[4];也有学者应用柔性流水车间调度理论对空间约束条件下的舰载机出库调度问题进行建模,并基于粒子群算法对问题进行求解[5]。针对基本粒子群算法易陷入局部极值、寻优结果不稳定等缺陷,本文基于K-Means聚类算法原理,提出KMCPSO(K-Means Cluster Particle Swarm Optimization)优化算法,并利用该算法求解舰载机的出库调度问题。

2 KMCPSO算法

基本的粒子群算法通过种群间粒子的相互学习,逐渐向最优解位置收敛。种群间相互学习的基础是种群的拓扑结构,拓扑结构的不同会导致粒子的学习样本也不同。如果种群的拓扑结构固定不变(静态),则在迭代过程中,每个粒子的学习样本都是固定的,如果该粒子陷入局部最优解,粒子将会向已陷入局部最优解的学习样本学习,导致种群陷入局部最优解的概率增加[6]。根据“物以类聚”的自然选择法则,我们可以设法把算法运行中单一的种群分为多个种群,这样即使某个种群出现了早熟收敛,其他的种群还是有机会继续向全局最优位置收敛。基于此,本文提出基于K-Means聚类原理的KMCPSO算法。

2.1 K-Means聚类原理

K-Means算法属于划分式聚类算法,是一个寻找目标函数最小化的过程,目标函数的准则是使得聚簇内部尽可能紧凑,各个聚簇之间尽可能分开,通常采用方差函数。假设数据集X ={x1,x2,…xn},{X1}k是K-Means算法给出的一个K划分,则C ={c1,c2,…-ck}表示1 =K1个划分的中心,式(1)为K-Means算法的目标函数:

首先随机选取K个点作为初始的聚类中心,然后计算各个点到聚类中心的距离,把数据点划入到离它最近的聚类中心所在的聚簇中,划分完毕后,对每一个聚簇计算新的聚类中心,然后继续进行数据点划入过程,直到聚类中心不发生变化,此时目标函数也收敛到最小。

2.2 KMCPSO算法原理

在传统的粒子群算法中,由于每个子群的成员都是采用随机法确定的,这种的种群构建策略会使得算法搜索过程带有一定的盲目性。粒子的聚合往往通过某种规则以极值粒子为中心飞向极值粒子所在位置,而当群体多样性丧失时,群体将陷入局部极值点。基于此,我们利用K -均值聚类算法进行子群的构建(K- means Cluster Particle Swarm Optimization,KMCPSO),以解决上述存在的问题。

动态多种群策略是将种群分成若干个子群,每个子群的成员在搜索过程中不是固定的,而是动态变化的。对每个子群重新构建的规则是每间隔t代(重组间隔代数),将整个种群重新划分为若干个子群,这种策略使得每个子群的信息能够有效的交流,提升粒子跳出局部最优解的能力。

利用K -均值聚类算法进行子群动态构建的步骤如下所示:

Step 1设TS0=(t1,t2,…,tN) 表示由N个粒子ti=(ti1,ti2,…,tid)(i = 1,2,…,N) 构成的初始种群,tij(i = 1,2,…,d) 表示第i个粒子的第j维;

Step 2 从TS0中随机地选取n(n < N) 个粒,tij(i = 1,2,⋯,d)作为k个均值聚Ui(i = 1,2,⋯k) 的初始点,每个聚类Ui(i = 1,2,⋯k) 的中心为si=(ti1,ti2,…,tid), i = 1,2,…k;j = 1,2,…d ;

Step3对∀ti∈ TSt,计算两点间的欧氏距离d(ti,sh)= ‖ti- sh‖, (h = 1,2,…N) 如果满足条件:d(ti,sh)={min d(ti,sh)|h = 1,2,⋯N} , 那么将ti属于第Ui类, 按此方法将TSt中所有粒子分配完。

Step 4重新计算聚类中心;ni表示Ui中的粒子数.

Step 5 如果Ui′= Ui,i = 1,2,⋯k输出k个聚类( k个子群) Ui(i = 1,2,⋯k) ; 否则令Ui= Ui′,转入Step 3

KMCPSO算法流程如图1所示:

3 舰载机出库调度模型

3.1流程分析

本文以俄罗斯“库兹涅佐夫”号航母舰载机出库任务为例[7],研究分析舰载机作业时序优化。“库兹涅佐夫”号航母的舰载机出库调运设施主要有牵引车、调向转盘、升降机和系留设施(系留座及系留索具)。俄“库兹涅佐夫”号航母舰载机出库过程中,要涉及机库内轨道牵引、调向转盘调向、飞机升降机操作、飞行甲板牵引等过程。每个转向盘和一个升降机组成一个配套设备,分别记为一号设备和二号设备。图2为航母出库调度时序。

3.2 条件假设

本文提出的调度模型有如下假设:整个调度过程中不出现故障;舰载机的系留、转向、解系留的时间相同,本文将这部分时间忽略;牵引车负载作业和空驶作业速度一定且相等;所有升降机的升降时间均相等且固定;所有舰载机的调度工序均相同;所有舰载机停机位已知且固定;在同一时刻,一台设备只能保障一架舰载机;在同一时刻,一架舰载机只能接受一个阶段一台设备的保障。

3.3模型建立

假设航母机库内共有x (i,j = 1,2,⋯x) 架舰载机需安排调度,机库内有h(k = 1,2,⋯h) 个升降机、b1辆牵引车,c个转向盘;飞行甲板共有b2辆牵引车,d(m = 1,2,⋯d) 个飞行甲板停机位。本文调度模型的所有参数说明如下:

F为目标函数,表示舰载机总调度完工时间最短的方案;

Tp(i) 为第P套方案位于第i停机位舰载机的调度完工时间;

Ts(i,j,k) 为机库内第i停机位舰载机处于第j顺序到达第k号升降机的时间;

Tj(i,j,k) 为机库第i停机位舰载机以第j顺序到达第k号升降机的开始转运时间;

C(i,j + 1,k) 为机库第i停机位舰载机以第j + 1 顺序到达第k号升降机的转运时间;

B(m,j,k) 为以第j顺序升起后的舰载机由第k号升降机到第m个飞行甲板停机位的转运时间;

A[i,k]、B[m,k]、C[i,k] 均为常数矩阵,其中:

A[i,k] 表示机库内牵引车由第i停机位行驶到第k号升降机的需用时间;

B[m,k] 表示飞行甲板上牵引车由第k号升降机行驶到第m停机位的需用时间;

C[i,k] 表示机库内第i停机位舰载机到第k号升降机的转运所需时间;

a(i,j.,k) 表示机库内第i停机位处于第j顺序到达第k号升降机的舰载机标号;

Tt为升降机单程升降所需时间。

综上所述,舰载机的出库调度模型为:

式(2)表示目标为求取舰载机总调度完工时间最短的方案;式(3)表示处于第i停机位的舰载机转运过程不中断,保持运转连续性;式(4)表示不同舰载机的初始停机位不同且已知;式(5)表示基于空间约束条件下,第i停机位舰载机到第k号升降机的转运所需时间已确定;式(6)表示舰载机保障转运属于串行工序;式(7)表示考虑串行工序的等待时间,将串行工序的等待时间计算到转运时间内;式(8)表示同一设备不能保障多架舰载机。

4 基于KMCPSO的舰载机出库调度算法

假设某航母机库内有2辆牵引车,2个转向盘,2台升降机,飞行甲板有2 辆牵引车。先需将机库内的20 架舰载机调度到飞行甲板执行任务。

4.1 粒子的编码和解码

本文采用二维粒子进行编码,第一维20 个向量表示20 架舰载机的转运作业次序,在1到20之间取随机数,数值越小的,作业次数越靠前;第二维20 个向量表示用于分配20 架舰载机的转向转盘,在取值为1或2。表1给出了粒子的编码形式(随机产生)。

根据粒子的编码,可以将舰载机进行资源分配和作业调度(即解码过程):一号设备5→15→13→7→1→20→3→12→19→11;二号设备2→10→6→16→4→18→14→17→2→9。

4.2 实验结果与分析

本文以20 架舰载机的出库调度为例,数据由文献[5]提供。表2给出了舰载机在机库内转运、飞行甲板转运的时间和牵引车在机库内空驶的时间等部分数据,其中,机库内转运表示舰载机从停机位分别转运到两套转向盘所需时间参数,飞行甲板转运表示舰载机从升降机处转运至指定飞行甲板停机位所需时间参数,库内空驶表示牵引车从升降机返程会舰载机停机位所需时间参数(表2 中的数据仅供参考,以实际转运时间为准)。

(单位:秒)

参数设置位为:迭代次数Gmax= 500 ;种群规模m = 20 ,学习因子c1= c2= 2 ,惯性权重 ω 最大值0.9,最小值0.4,分群间隔代数为100。

利用KMCPSO算法可以求解得到调度总用时最短的转运方案为:一号设备2→13→4→5→3→11→15→14→11→12;二号设备20→18→6→10→8→9→7→17→16→19。

20 架舰载机出库最短用时2926s(48.7min,仅供参考),比初始随机方案调度(3600s,随机分配)节省时间近700s,占总用时23.9%,因此调度优化具有较大应用价值。最优方案对应的甘特图如图3所示:

分别基于KMCPSO算法和原始粒子群算法(PSO)[8]对舰载机调度模型进行求解,每种算法各运行10~50 次。表3 给出了最优运转方案的结果比较。

由表3 可以看出,基于KMCPSO的调度算法总用时均比PSO用少,且每次运行结果均较稳定,表明了本文提出的算法较好的克服了易陷入局部极值、寻优结果不稳定等缺陷,具有较好的实用性和应用价值。

5 结论

为减小舰载机从机库转运到飞行甲板的调度时间,实现作战资源的高效分配,本文利用KMCPSO算法建立了KMCPSO舰载机调度模型,并运用实例进行了仿真实验。仿真结果证明,采用KMCPSO算法能较好地解决PSO算法易陷入局部极值、寻优结果不稳定等缺陷,具有较好的实用性和应用价值。现代战争对航空母舰的战斗力提出了更高要求,如何快速有效地解决舰载机的调度问题,使得航空母舰能够更好地适应未来高科技战争需求,是下一步值得深入研究的工作。

参考文献

[1]夏蔚军,吴智铭,张伟,等.微粒群优化在Job-shop调度中的应用[J].上海交通大学学报,2005,39(3):381-385.

[2]《运筹学》教材编写组.运筹学[M].北京:清华大学出版社,2008:251-25.

[3]王万良,吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007:114-121.

[4]司维超,韩维,史玮韦.基于PSO算法的舰载机舰面布放调度方法研究[J].航空学报,2012,36(11):45-47.

[5]王云翔,毕玉泉,杨茂胜,等.基于空间约束的舰载机出库调度[J].指挥控制与仿真,2015,37(1):83-85.

[6]Hong~li Xu,Xu Qian,liang Zhang.Study of ACO AlgorithmOptimization Algorithm Based on Improved Tent Chaotic Map-ping Journal of Information&Computational Science.EI 9:6(2012):1653-1660.

[7]杨炳恒,王海东,韩峰,等.舰载机调运作业流程优化研究[J].科学技术与工程,2010,10(22):53-55.