动态均值聚类算法

2024-12-09

动态均值聚类算法（共7篇）

动态均值聚类算法篇1

引言

径向基函数神经网络 (RBFNN) 以其简单的网络结构、快速的学习方法、较好的推广能力, 已经广泛地应用于许多领域, 特别是模式识别和函数逼近等领域。然而, 如何有效地确定RBF神经网络的网络结构和参数, 至今没有系统的规律可循。在RBF神经网络中需要确定的参数包括隐含层节点数、隐含层基函数的中心值和宽度、隐含层到输出层的连接权值。目前, 隐含层节点数主要依靠经验来选取。而根据moody准则, 神经网络的设计应该在满足精度要求的情况下有最小的结构, 以保证网络的泛化能力[1]。

由于隐含层基函数中心值的选取对网络的函数逼近能力有很大的影响, 目前最常用的确定隐含层中心值的方法是K-均值聚类法。由于K-均值聚类法的聚类过程一般能够根据输入向量比较准确地确定聚类数和相应的聚类中心, 因此, 如果在已知全部输入向量时使用该方法能够比较精确地确定网络结构。但是, 它要求实现确定全部输入向量和指定聚类中心的数目, 这在实际应用中很难办到。而动态K-均值聚类方法能够根据输入来实时地确定网络的中心。因此, 本文提出动态均值聚类方法, 对一般的K-均值方法进行改进。

一、BRF神经网络的结构原理

RBF神经网络最基本的结构形式是一种三层前向网络。网络的基本构成包括输入层、隐含层和输出层, 各层的节点数目分别为P, M, L, 每一层都有着完全不同的作用。其结构如图1所示。

第一层是输入层, 由一些信号源节点 (感知单元) 组成, 它们将网络与外界环境连接起来。第二层是隐含层, 由若干个隐节点构成。隐含层只有一个隐含层单元, 采用径向基函数作为其输出特性。第三层是输出层, 由若干个线性求和单元的输出节点组成, 它对输入模式的作用产生响应。输入层节点传递输入信号到隐含层。从输入空间到隐含层空间的变换是非线性的, 而从隐含层空间到输出层空间的变换是线性的。网络输出节点计算隐节点给出基函数的线性组合。输入层到隐含层之间的权值固定为1, 只有隐含层到输出层之间的权值Wkj (k=1, 2, …, L;j=1, 2, …, M) 可调。

在图1中, 输入层由P个信号源节点组成。设N为当前训练的样本总数, 对于训练集的每个样本即为输入矢量:X= (xl, x2, …, xp) , 其中xi (i=1, …, P) 为网络的第i个输入。隐含层由M个隐节点组成。每个隐含层节点的激活函数是一个径向基函数, 它是一种局部分布的中心点径向对称衰减的非负非线性函数。由于高斯基函数具备表示形式简单、径向对称、光滑性好、易于进行理论分析等优点, 所以文中隐含层变换函数采用高斯基函数, 其表达形式如下所示:

其中, X= (x1, x2, …, xp) T为网络输入矢量。Cj为隐含层第j个高斯单元的中心矢量, 与X具有相同维数的向量, Cj= (cj1, cj2, …, cjp) , (j=l, 2, …, M) 。ðj是第j个感知的变量 (可以自由选择的参数) , 它决定了该基函数围绕中心点的宽度。M是隐节点的个数。‖X-Cj‖是向量X-Cj的Euclid范数, 表示X和Cj之间的距离。Φj (X) 为隐含层第j个节点的输出, 即为第j个隐节点的活跃值。当前活跃值矢量为。由高斯公式可知, 从输入层到隐含层之间是一种函数变换, 隐含层节点的输出范围在0~1之间, 且输入样本愈靠近节点的中心, 输出值愈大, Φj (X) 在Cj处有一个唯一的最大值。随着‖X-Cj‖的增大, Φj (X) 迅速衰减到零。输出层由L个节点组成。设N为当前训练的样本总数, 对于每个样本即为网络的实际输出矢量为:yk= (y1, y2, …, yL) , k=l, …, L, 为网络的第k个输出。RBF神经网络的输出为隐含层节点输出的线性组合, 输出形式可表示为:

其中L是输出节点个数, Φj (X) 为高斯函数。wkj为第k (k=1, 2, …, L) 个输出节点与第j (j=l, 2, …, M) 个隐节点的连接权值。

二、BRF中心调整的动态K-均值聚类算法

2.1 动态K-均值的引入

RBF网络中心学习过程分两步:一是根据输入样本确定隐含层各节点的变换函数的中心Cj和半径ρj;二是采用误差校正学习算法, 调节输出层的权W。其目的就是把输入数据分配到一定数目的有意义的类别中去, 即根据欧氏空间中的距离来对输入向量进行聚类。本文采用自适应调整聚类中心的方法——动态均值聚类法。

该方法的基本思想是:首先已知据聚类中心的数目, 然后随着向量的输入, 计算输入向量与特定聚类中心的欧氏距离。如果距离小于门限值, 则将该聚类中心所对应的输入向量的平均值作为新的聚类中心;如果距离大于门限值, 则将刚输入的向量作为新的聚类中心。再接着输入向量, 直到确定所有的聚类中心。

2.2 动态K-均值聚类算法在RBF中的应用

动态K-均值聚类算法在RBF网络中心选取中的作用是调整聚类中心, 使网络中心的选取更精确。它的计算过程可以简要的描述如下:

首先, 令类别数为0 (第一个输入会强迫创建出一个类别模式以支持该输入) 。以后, 每遇到每一个新的输入向量, 则计算它与任何一个已分配的类别模式之间的距离。如果指定第P个输入向量为X (p) 以及第j个聚类中心为Cj, 则欧氏距离d可以表示为:

其中M是输入向量的维数。

设输入向量X (p) 和所有已分配的模式类别之间的距离已知, 且和该输入矢量最近的中心为Ck, 应有d0=‖X (p) -Ck‖<‖X (p) -Cj‖, j=1, …, T, j≠k其中T是已分配类别的数目。

在确定了与输入矢量最近的中心后, k就已经确定了, 从而d0也就确定了。先把它和距离门限值ρ进行比较, 会有如下两种情况:

(1) 当d0<ρ时, 输入矢量X (p) 在允许的误差范围内, 该输入矢量属于第k个类别。也就是说, 如果用Sk表示第K个中心所对应的全部输入矢量的集合, 则X (p) ∈Sk。这时可以引入k-均值聚类方法的思想, 通过求得所有成员矢量的平均值来进行中心更新。即:

其中NSk表示第K个聚类中心所对的输入矢量的个数。

(2) 当d0>ρ时, 输入矢量X (p) 不在允许的误差范围内, 从而不能分配到该类别中去。此时, 应该以X (p) 为中心, 分配一个新的聚类中心, 算法流程图如图2所示。

上面的过程用动态聚类的方法实时的找到了网络的中心, 在确定网络中心Cj之后, 可以令相应的半径ρj等于其与属于该类的训练样本之间的平均距离, 即:

最后可以根据误差梯度下降法调节权值W以完成RBF网络学习过程。

三、仿真试验及结果分析

本实验通过RBF神经网络函数逼近的方法来比较K-均值聚类和动态K-均值聚类方法的优劣。实验环境为PC机一台, 所用工具为MATLAB。

考虑非线性函数y=2sin (πx) +2cos (0.5πx) , x∈[0, 10], 用RBF神经网络进行函数逼近。

x以0.1为间隔在[0, 10]上均匀取值, 可得到100个样本作为训练样本。RBF神经网络的中心点个数取m=20, 基函数用高斯函数。对分别采用K-均值算法和动态K-均值算法确定RBF神经网络中心进行比较:采用K-均值聚类算法, 训练时样本的最小平均相对误差为0.1014327, 图3为K-均值聚类法RBF拟合曲线。采用动态K-均值聚类算法, 训练时样本的平均相对误差为0.0731432, 图4为动态K-均值聚类法RBF拟合曲线。可见采用动态K-均值聚类算法可以获得更好的效果。

四、结论

本文在k-均值聚类算法的基础上, 将动态均值聚类方法应用到RBF神经网络。该方法有效地解决了k-均值聚类的局限性, 提高了RBF的网络学习能力。通过仿真实验验证了该方法的实用性和精确度, 可供进一步的研究和实际应用。

参考文献

[1]阎平凡, 张长水.人工神经网络与模拟进化计算[M].北京:清华大学出版社, 2003.

[2]张海朝, 黄淼.基于RBF神经网络的B样条曲面重构[J], 微电子学与计算机, 2008, 7.

[3]兰天鸽, 方勇华.构造RBF神经网络及其参数优化[J], 计算机工程, 2008, 33 (5) .

[4]Roy A, Govil S, Miranda R.A Neural Network Learning Theory and aPolynomial Time RBF Algorithm[J].IEEE Trans.on Neural Network, 1997, 8 (6) :1301-1313.

[5]潘登, 郑应平.基于RBF神经网络的网格数据聚类方法[J].计算机应用, 2007, 26 (2) .

[6]任江涛, 孙婧昊.一种用于文本聚类的改进的K均值算法[J].计算机应用, 2006, 26 (6) .

[7]Mashor M Y.Hybrid training algorithm for RBF network[J].Interna-tional Journal of the Computer, the Internet and Management, 2000, 8 (2) :48-65.

[8]Bianchini M, Frascono P, Cori M.Learning without minima radialbasis function network[J].IEEE Trans on Neural Networks, 1995, 6 (3) :749-756.

[9]Pedrycz W.Conditional fuzzy clustering in the design of radial ba-sis function neural network[J].IEEE Trans on Neural Networks, 1998, 9 (4) :601-612.

[10]Gonzalez J, Pojas I, Pomares H.A new clustering technique for function approximation[J].IEEE Trans on Neural Networks, 2002, 13 (1) :132-142.

动态均值聚类算法篇2

配电网重构是对网络拓扑结构进行优化,通过优化开关状态来调整网络的潮流分布,达到降低网损和均衡负荷等目的。其研究内容主要包括静态重构和动态重构。静态重构基于确定时间点优化,是一个非线性的组合优化问题,主要算法有启发式算法、传统数学优化方法以及智能算法;而动态重构基于时间区段进行优化,因此动态重构能够依据系统负荷随时间的变化对配网网络结构进行动态调整,更符合实际配电系统的日前优化要求。

文献[1]选择能最大限度降低网损量的开关开闭,将时间段落按配网中总负荷变动大小来分段,虽然能在一定程度上减少重构次数,但存在一定的不合理性,配网重构是依据每个节点的负荷寻找最优拓扑结构的,即使总负荷不变,各个节点负荷的变化也会导致产生不同的最优拓扑结构;文献[2]将开关操作的费用计入目标函数中,将时变问题分解为多个静态重构子问题,使用遗传算法分别求解每个静态子问题,并使用动态规划得到全局最优时变策略;文献[3] 采用混合粒子群算法对各个时间断面分别进行静态求解,选择若干优良解构成解集,引入多代理协调技术来获得动态重构解;文献[4]采用和声搜索算法对每个时间断面分别求解,选取每个断面下的若干优良解构成待选解集,利用动态规划根据待选解集得到动态重构解。文献[2-4]在考虑每个时间断面重构解的组合时,易造成解空间过大而求解困难。文献[5]将配电网络动态重构转换为以聚类中心表示负荷状态的多个静态重构问题,并采用改进的化学反应算法求解各个静态问题,重构数与聚类数有关,而一定时间内配电网动态重构的次数受一定的限制,聚类后得到的分段数可能大于动态重构允许的次数。

本研究采用改进最优模糊C均值聚类技术(opti-mal fuzzy C-means clustering,OFCMC)对所研究时间区间进行时段划分,将动态重构问题转化为以负荷聚类中心为代表的多个静态重构问题。本研究在文献 [6]的基础上,结合启发式规则,对和声搜索算法(har-mony search algorithm,HSA)做进一步的改进,并将其应用于求解以聚类中心为代表的静态重构问题上。

1基于改进OFCMC的重构时段划分

针对配电网动态重构中的开关操作次数约束难以处理的问题,本研究采用改进OFCMC对所研究时间区间进行时段划分,从而限制重构次数。

1.1基于OFCMC的配电网负荷聚类

模糊聚类分析是根据客观事物之间的特征、亲疏程度以及相似性,通过建立模糊相似关系对客观事物进行聚类的分析方法。文献[7]中提出的OFCMC采用遗传-迭代自组织算法,能够较好地解决有关事物聚类方面的问题,得出所研究事物的最优聚类数及最优聚类中心。

本研究采用OFCMC对未来一天的预测负荷数据进行聚类,将未来一天等时间间隔地划分为T个时段,假定各节点负荷在各个时段内保持不变,则t时段 (t = 1,2,…,T) 的负荷状态可表示为Xt =[xt1,xt2,…xtn] , 其中:n —网络的节点数,xti— t时段节点i(i = 1,2,…,n) 的复功率。研究时间区间内所有的负荷状态为X ={X1,X2,…XT} ,经聚类可将X分为C(C ∈[2,T - 1]) 类;可得对应的聚类中心为V ={V1,V2,…VC} ,第m个聚类中心为Vm,Vm=[vm1,vm2,…vmn] ,其中:vmi—第m个聚类中心节点i的复功率;可得对应的隶属度矩阵为U =(μmt)CXT ,其中:μmt—第t个数据Xt隶属于第m类Vm的程度。详细求解方法可参见文献[7]。

1.2基于改进OFCMC的时段划分

将OFCMC直接应用于动态重构时段划分时,应基于以下两点进行改进:1OFCMC仅将负荷特性相近的时段归为一类,但没有考虑负荷的时序特性,因此需要对聚类结果按时间顺序进行排序来确定分段数及各分段的起止时刻;2在一天内配电网动态重构次数是有限的,而通过时序排列按类分段所形成的分段数可能大于一天内最大重构允许次数,因此需要通过一定的方法对初始分段进行融合。基于以上讨论,本研究将分2步对时段进行划分:首先用OFCMC对负荷数据进行聚类,并通过时序排列按类分段从而完成一次划分;在此基础上,利用枚举法对时段进行二次划分。

1.2.1时段的一次划分

(1)基于日前负荷预测值,获得未来一天24各个时段的负荷功率。

(2)为了减少最小数据和最大数据对聚类影响过大,对样本数据进行标准化,将聚类数据压缩在[0,1] 闭空间。标准化公式如下:

式中:xti— t时段节点i对应的负荷值,x′ti— t时段节点i对应的标准化负荷值。

(3)根据文献[7]可计算得到最佳模糊隶属度矩阵U 、聚类中心V以及最佳聚类数C ,将所有数据按最大隶属度归类获得各时段负荷所属聚类。

(4)记录各时段负荷的聚类编号,按照时间顺序排列,将隶属于同一聚类且相邻的时段汇集成一段, 形成段C1。

1.2.2时段的二次划分

在时段的初步划分结果中,整个研究区间被分成了C1段,且相邻的时段必隶属于不同的聚类。若初始分段数C1> Cmax(Cmax—最大重构允许次数),则需进行时段的二次划分,具体步骤如下所示:

(1)设定目标函数,如下式所示:

式中:Cfinal—最终分段数, ΔPj—第j个分段的网损功率, Δtj—第j个分段的时长。需满足的约束条件有单时间断面的静态约束,包括潮流约束、节点电压约束、支路容量约束及网络拓扑约束;此外,还应满足重构次数约束。

(2)引入一个以二进制编码的染色体F ,设定其基因位的长度为时段一次划分后的分段数C1,将其首位固定设置为“1”;第i(i = 2,…,C1) 位的设置方法为:若将其设置为“1”则表示该分段与上一分段隶属同一聚类,则可将这两分段合并;若为“0”则表示与上一分段隶属不同聚类,则不能合并。假设时段一次划分后共有8个分段,则初始染色体可表示为F0={1,0,0,0,0,0,0,0}。

(3)保持染色体首位不变,采用枚举法选择其他任意 (C1- Cmax) 个基因位,修改其0-1状态(若该位原始状态为“0”,被选中后则修改为“1”),按步骤2中的规则进行融合,并根据下式计算新类的聚类中心。共

C1- Cmax有( CC1)种选择方案,选择使目标函数值达到最小的方案作为最终时段二次划分的方案。目标函数的求解方法详见下文第3节。

式中:e,f,…(e,f... ∈[2,C]) —合并段中包含的各时间段负荷状态隶属聚类的编号;h —OFCMC中的一个收敛因子(h >1时收敛)。

本研究提出的基于改进OFCMC的时段划分法能将重构次数严格限制在约束范围内,且算法可行。因为,经时段一次划分后得到的分段数必小于24,一般规定一天最大重构允许次数为4,则时段二次划分中最大的方案数C2233- 4为8 855种;而一天中某些相邻时段的负荷特征非常相似,因此经时段一次划分后得到的分段数必大大小于24,方案数必将大大小于8 855。大量计算表明,典型日经时段一次划分后得到的分段数一般为8~10分段,则时段二次划分对应的最大方案数为70~210,均在可计算范围内,说明该算法的可行性。

2改进的配电网重构和声搜索算法

HSA是一种启发式全局优化算法,是对乐师们在音乐演奏中凭借各自的记忆,通过反复调整乐队中各乐器的音乐,最终达到一个美妙和声状态过程的模拟[8]。

HSA算法的寻优过程包括和声记忆库考虑、基因调整以及随机变异操作。在寻优过程中如何合理地设置基音调整策略,一直是学者们研究的热点和难点之一[9]。若该策略设置不合理,将会导致HSA盲目地随机搜索,降低算法的收敛性,影响算法的寻优能力。本研究针对这一问题,并结合配电网重构的特点,提出了一种基于启发式规则的基音调整策略,下文将进行详细论述。

2.1可行解的编码方法

配电网重构要求重构后的网络呈辐射状、无孤岛运行。本研究采用文献[10]的基本环与基本环矩阵来确定重构解各维决策变量的可行取值范围,并且其可行解规定为任意两个基本环所包含的公共分段开关最多只能断开一个,从而确定可行重构解。

在辐射状配电网中,闭合一个联络开关后其与若干分段开关组成的单连支回路称为基本环。形成一个基本环后,则必须打开环中的另一开关以恢复网络辐射状。本研究将重构解向量HV设置为各基本环中断开支路的组合,采用整数编码的方式,以断开支路的编号为决策变量,联络开关的个数为解向量的维数,编码格式如下式所示:

式中:xi—第i个重构环中断开支路的编号;M —重构环的个数。

2.2基于启发式规则的基音调整策略

2.2.1基音调整策略

支路交换法的基本思想[11]为:首先合上一个联络开关,在配电网中形成一个环网;其次选择环网中的一个分段开关将其打开,使配电网恢复为辐射状。上述过程称为一次拓扑调整。对于绝大多数配电网来说,沿线电压相角变化极小[12],因此一次拓扑调整引起的有功线损变化量 ΔP可简化表示为:

式中:Ik—断开支路k的支路电流;Vm,Vn—联络开关两端的电压;Rloop—联络开关闭合后形成的单连支回路中所有支路电阻之和。

Mesut E.Baran等人在文献[11]的基础上做了改进,利用网损变化的估算公式(5)为一元二次函数的特点,将其求极值的方法用于寻找断开开关。该函数在其顶点处有最小值,设其顶点坐标为 (Iopt,ΔPopt) ,其数学表达式如下式所示;当Ik∈(0,2Iopt) ,ΔP为负,且Ik越接近Iopt,系统网损减小越多。

根据以上所论述的启发式规则,定义基于启发式规则的基音调整策略为:选择能保持网络辐射状无孤岛运行且支路电流值在0~2Iopt之间最接近Iopt的支路作为决策变量基音调整选择的支路。

2.2.2基于启发式规则的基音调整策略实现步骤

该策略的具体实现步骤如下所示:

(1)确定需要进行基音调整的决策变量。 HV =[x1,x2,…,xM] 由HSA的记忆库考虑和随机变异操作确定,生成随机数组R = rand(1,M) ,若R(m)<PAR(基音调整概率),则说明需要对xm进行基音调整。

(2)计算初始状态下辐射状网络的潮流。该状态下网络中断开的支路编号分别为x1,x2,…,xM。

(3)进行独立拓扑调整。若合上一个联络开关形成的基本环与其他基本环不存在公共支路,则这两种对应的拓扑调整互不影响,即为独立拓扑调整, 反之为非独立拓扑调整[13]。对步骤1中确定的决策变量,只考虑当前网络拓扑下的所有独立拓扑结构, 根据2.2.1中介绍的方法确定各相应基本环中能够降低网损的支路集合,又根据基本环矩阵来确定各相应决策变量的可行取值范围,求得两者的交集,若交集不为空,则从中选择支路电流值在0~2Iopt之间且最接近Iopt的支路作为基因调整选择的支路,否则保持不变。

(4)判断是否对所有需要进行基音调整的决策变量进行操作。若是,则结束该操作;否则根据步骤3的结果修改网络拓扑并计算新的潮流分布,重复步骤3。

2.3改进HSA的实现步骤

本研究的重构算法主要包括构建基本环矩阵、利用启发式规则制定基音调整策略及利用和声策略全局寻优这几部分。具体实现步骤如下:

(1)算法参数的初始化。改进HSA的参数包括解向量的维数M 、和声记忆库的大小HMS、和声记忆库考虑概率HMCR、基音调整概率PAR、最大迭代次数Nmax和终止条件。

(2)初始化和声记忆库。初始状态下联络开关全部断开,分段开关全部闭合,本研究采用文献[10]的基本环矩阵自动生成算法生成基本环矩阵,利用该矩阵及可行解规定随机生成HMS个初始和声存入和声记忆库中,计算各初始解的目标函数值。

(3)生成新和声HVnew=[x′1,x′2,...,x′M] :

1生成新的基本环矩阵:根据上一个解所确定的开关状态,将断开的开关视为联络开关,根据基本环矩阵自动生成算法生成新的基本环矩阵。

2生成一个随机数组R1= rand(1,M) ,对各维决策变量都进行以下操作:根据基本环矩阵及可行解规定确定x′m(m = 1,2,...,M) 的可行取值范围B1m;判断R1(m) 是否小于HMCR,若是则将HM中第m列元素构成一集合B2m,取B1m和B2m的交集,x′m从该交集中随机选取;否则x′m从B1m中随机选取。

3对步骤2中生成和声HVnew进行基音调整,具体步骤详见2.2.2节。

(4)更新和声记忆库:计算新和声的目标函数值, 若其优于和声记忆库中最差和声,则用新和声替代最差和声存入和声记忆库中。

(5)判断算法是否满足终止条件:若满足则停止迭代,否则转至步骤3。

3配电网动态重构

本研究采用改进OFCMC将研究时间区间进行时段划分,并求得各分段的负荷聚类中心。聚类中心是同一类数据的中心,具有表征类中数据的能力;并且, 负荷分布状态相近的时段所对应的最佳网络拓扑结构一般也相同或相近。因此,本研究将配电网络动态重构问题转化为多个静态重构子问题,对每一分段进行静态重构,以该分段的聚类中心作为代表负荷进行潮流计算,并采用第2节给出的改进HSA进行求解。动态重构问题的目标函数见式(2),静态重构子问题的目标函数如下式所示:

式中:ΔPj—第j个分段的网损功率,Δtj—第j个分段的时长。需满足的约束条件包括潮流约束、节点电压约束、支路容量约束及网络拓扑约束。

4实验及结果分析

IEEE-33节点配电系统[14]作为测试系统进行相关的研究如图1所示。在图1中,虚线为联络线路,各条支路上均装有开关。各节点编号和各虚线线路编号如图所示,实现线路编号为该线路右端节点编号。

4.1改进HS算法性能验证

本研究改进HSA的参数设置如下:HMS=10;HM-CR=0.85;PAR=0.5;Nmax=300。

文献[15]已表明HSA在求解配电网重构问题时相比于遗传、禁忌搜索算法等具有较好的性能。根据基本环矩阵和本研究的编码方式,利用HSA(称之为算法一)、有关文献的改进HSA(称之为算法二)以及本研究的改进HSA(称之为算法三)对33节点网络进行静态重构。为比较这3种算法的全局收敛性,本研究分别利用这3种不同的算法对测试系统循环计算200次,给出各算法在这200次计算中得到的最优解(网损/k W)、最差解(网损/k W)、标准差以及求得全局最优解的次数和求得全局最优解时重构一次所需的平均时间(次/s),IEEE-33节点系统结果比较如表1所示。从表1中可以看出,3种算法均能求得文献[16]所述的公认的已知全局最优解,但算法三求得全局最优解的次数(97次)比算法一和算法二(分别为51次和72次)多,本研究算法求得的网损标准差比其他两种算法小,且耗时比其他两种算法略短。以上说明本研究算法具有较好的全局收敛性和寻优速度。原因是本研究算法采用了基于启发式规则的基音调整策略,将启发式规则和智能算法相结合,一方面利用HSA的全局搜索能力能够克服支路交换法比对初始解依赖性较大的缺点;另一方面利用启发式规则能够大大缩小算法的搜索范围,减少需要考虑的开关组合,使得算法朝着目标更优的方向搜索。

4.2配电网动态重构实例分析

本研究构建IEEE-33节点未来一天的预测负荷数据(参见文献[17])并对该系统进行动态重构。将未来一天分为24个时段,第1个时段为0∶00~1∶00,其他依次类推,假定每个时段内负荷恒定。设定一天内最大重构允许次数为4。

经OFCMC聚类后得到的各时段负荷的最优聚类结果如图2所示。从图2中可以看出,若不对初始分段做进一步的融合处理,则将一天划分成了8段,分段数大于最大重构允许次数。有关文献采取将孤立类的时间段做平滑处理使负荷种类的变化更具连续性的方法,则将分段数减为6,时段划分结果为:分段I为第1~6时段,分段II为第7~8时段,分段III为第9~1时段,分段IV为第15~21时段,分段V为第22~23时段,分段VI为第24时段;本研究采用改进OFCMC对时段进行划分,则将分段次数减至4,时段划分结果为:分段I为第1~8时段;分段II为第9~14时段;分段III为第15~21时段,分段IV为第22~24时段。

本研究采取3种方案来验证将动态重构问题转化为基于OFCMC时段划分结果和以负荷聚类中心为代表负荷的多个静态重构问题的合理性和有效性。

方案一:以各时段的实际数据分别进行重构;方案二:基于有关文献时段划分的结果并以聚类中心作为代表负荷进行重构;方案三:基于本研究改进OFC MC时段划分的结果并以聚类中心作为代表负荷进行重构,结果如表2所示。

方案一得到的系统总网损为15 21 k W·h,开关操作的调度次数为11次,闭合/打开总次数为34次;方案二得到的系统总网损为1 525.7 k W·h,开关操作的调度次数为5次,开关闭合/打开总次数为18次;方案三得到的系统总网损为1 527.2 k W·h,开关操作的调度次数为3次,开关闭合/打开总次数为14次。

注:开关操作均在时段的起始时刻点进行

从表2中分析可知,方案二和方案三的代表负荷所得重构方案能满足同时段数据中绝大多数最优,而少量不满足最优的也与最优非常接近,方案三不满足最优的重构方案比方案二多,因为方案三相比于方案二融合了更多的时段。

方案二和方案三的系统总网损比方案一略大,但开关操作的调度次数和开关闭合/打开总次数大大减少;方案三的系统总网损比方案二略大,但开关操作的调度次数和开关闭合/打开总次数分别减少了2次和4次。以上分析均说明了本研究将动态重构问题转化为基于改进OFCMC时段划分结果和以负荷聚类中心为代表负荷的多个静态重构问题的合理性;另外, 本研究改进OFCMC能将重构次数严格控制在约束范围内,而文献[5]中的方法不一定能满足约束条件,突出本研究算法的有效性。

5结束语

本研究采用改进OFCMC将研究时间区间进行时段划分,求得各分段的聚类中心作为代表负荷用作潮流计算,采用改进HSA对每一分段进行静态重构求解,算例验证了本研究算法的可行性和合理性。

该算法具有如下特点:1采用改进OFCMC进行时段划分后能将重构次数严格限制的约束范围内;2采用改进HSA解决静态重构问题,具有良好的收敛性和寻优效率。

摘要：针对配电网络动态重构中的开关操作次数约束难以处理与和声搜索算法寻优效率低的问题,分别提出了改进的最优模糊C均值聚类法和改进的和声搜索算法,利用前者对研究时间区间的负荷进行聚类从而将配电网动态重构转为以聚类中心代表各分段负荷的多个静态重构子问题,利用后者对各静态重构问题进行求解。每个时间点的优化网络结构由相应的聚类中心的重构结果决定,由此得到配电网络重构的操作时间点和操作开关。在IEEE 33节点配电系统负荷数据的基础上构建1天的负荷数据并对该系统进行动态重构。研究结果表明,该方法能够控制开关操作次数,提高静态重构算法的寻优效率。

动态均值聚类算法篇3

聚类分析[1]是模式识别和数据压缩领域中一种重要的非监督学习过程,其目的是将若干特征相似的特征模式划分到一个集合,每个集合的特征模式之间按照某种度量来衡量相似程度,使得同一个集合内的数据对象具有较高的相似度,而不同集合中的数据对象间的相似度尽可能小,数据对象间特性差异的大小通常是借助于某一距离空间中的距离概念来刻划的。在现有的聚类算法中,K-均值算法以其简单和高效占有重要地位[2]。但因K-均值算法在寻找聚类中心的过程中采用了启发式方法,使得该算法对初始聚类中心的选择较为敏感,易于陷入局部最优解。尤其在大矢量空间中,这种算法的性能会变得更差[3,4]。美国Holland教授于1975年提出了一种全局优化自适应概率搜索算法—遗传算法(GA)[5,6]。该算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法,具有较强的鲁棒性和全局寻优的能力,但基于遗传的K均值算法(GA-K均值算法)存在前期过早收敛而后期收敛慢的缺点[7]。本文借助免疫机制的优点[8],将免疫原理的选择操作机制引入遗传算法中,提出基于改进遗传算法的K-均值聚类算法。该算法结合K-均值算法的高效性和局部搜索能力,以及改进遗传算法的全局优化能力,达到了较好的聚类效果。

1 基于改进遗传算法的K-均值聚类算法

遗传算法在解决实际问题时,目标函数和约束条件作为抗原输入,随机产生初始抗体群,并通过一系列遗传操作及个体浓度的计算,在保持抗体多样性的情况下找出针对该抗原的抗体。本研究借助免疫机制来调整选择概率,以优化初始聚类中心,同时,在种群进化过程中,自适应动态调节交叉概率和变异概率,避免了早熟现象的发生。具体步骤如下:

1.1 染色体编码及种群初始化

染色体编码有很多方式,聚类分析中常用的是基于聚类中心的浮点数编码和基于聚类划分的整数编码。根据聚类样本的高维性和数量大的特点,本文采用浮点数编码。初始种群的产生采用随机生成,方法为:假设随机从样本空间中选K个样本作为聚类中心,其它样本随机分到这K个聚类中,并计算各个聚类的聚类中心作为初始个体的染色体编码,最后增加一位该个体所对应的适应度,即1条染色体可以用长度为(K+1)个基因位组成的浮点码串S=Z1Z2…Zkf表示,重复进行psize次(psize为种群大小),得到初始种群。

1.2 染色体适应度的选取

根据染色体的构成,采用的适应度函数为

$f = \frac{1}{k} \times \frac{E_{1}}{E_{k}} \times D_{k}$

上式中:k为聚类类别数;是簇内距离;是簇间距离。,计算公式分别为

$E_{k} = \sum_{j = 1}^{k} \sum_{x_{i} \in Ι_{j}} ∥ x_{i} - c_{j} ∥^{2}$

上式中:xi表示类簇Ij中的样本;cj表示类簇j的中心。这样定义考虑了簇内聚类最小的原则。

$D_{k} = {m a x}_{i ‚ j = 1}^{k} ∥ c_{i} - c_{j} ∥$

上式中:ci,cj分别为簇i,j的中心。这样定义考虑了簇间距离最大的原则。

适应度函数受3个因素影响,即1/k,E1/Ek及。第一个因素减少的时候,另外两个因素随着k的增加而增加,所以这个适应度函数表达的内涵是在所分类别数尽可能小的情况下提高聚类的紧凑度和分离程度。

1.3 选择操作

针对基于遗传算法的聚类算法在算法开始前期收敛速度快,而后期由于各条染色体的个体差异变小使收敛速度变得很慢,本研究采用一种基于免疫原理[6]的选择操作和比例适应度分配方法相结合的混合选择算子计算个体被选中的概率以克服上述缺点。

定义1 个体浓度:

$d = \frac{群体中相同个体的数目 (m)}{群体大小 (p_{s i z e})}$

找出群体中个体浓度最大的m个个体,设为1,2,…,m,则这m个个体的个体浓度概率为 $p_{d} = \frac{(1 - d)}{p_{s i z e}}$ ,其余的个体浓度概率为,所有个体的浓度概率之和为1。

设某一个个体的适应度为fi,该个体被选中的概率为pfi,则

$p_{f_{i}} = \frac{f_{i}}{p_{d} \times \sum_{j = 1}^{p_{s i z e}} f_{i}}$

式中:i=1,2,…,psize。

此种选择策略有两个优点:一是个体适应度越大,则选中的概率越大,加速了算法的收敛;二是个体浓度越大则被选择的概率越小,起到抑制作用,保证了进化群体中个体的多样性,避免过早收敛。

1.4 交叉操作

标准遗传算法由于在进化过程中采用固定的交叉概率和变异概率,已经被证明无法收敛到问题的全局最优解,容易出现早熟现象,后期还会因为个体差异的减小出现收敛速度缓慢的现象。鉴于此,本研究按照一定的交叉概率采用最邻近法则进行交叉操作。首先对交叉概率和变异概率做出如下约定:当群体适应度比较集中时,使得交叉概率Pc和变异概率Pm增大;当群体适应度比较分散时,使得交叉概率Pc和变异概率Pm适当减小。这样约定能使算法在迭代过程中根据个体的适应度来改变其交叉概率Pc和变异概率Pm,从而在能保护最优个体的同时加速较差个体的淘汰速度,增强了算法的全局搜索能力。其数学模型为:

$Ρ_{c} = {\begin{cases} Κ_{1} \times \frac{f_{m a x} - f^{'}}{f_{m a x} - f_{a v g}} f^{'} \geq f_{a v g} \\ Ρ_{c} = Κ_{2} f^{'} ＜ f_{a v g} \end{cases}$

$Ρ_{m} = {\begin{cases} Κ_{3} \times \frac{f_{m a x} - f}{f_{m a x} - f_{a v g}} f \geq f_{a v g} \\ Ρ_{m} = Κ_{4} f ＜ f_{a v g} \end{cases}$

式中:K1,K2,K3,K4是小于0的常数;fmax为群体的最大适应度;favg为群体的平均适应度;f′为交叉产生的2个新个体中适应度较大的那个个体的适应度;f为变异个体的适应度值。

采用最邻近法则的基因匹配交叉操作:设待交叉的2条染色体为S1=Z $_{1}^{(1)}$ Z $_{2}^{(1)}$ …Z $_{k}^{(1)}$ 和S2=Z $_{1}^{(2)}$ Z $_{2}^{(2)}$ …Z $_{k}^{(2)}$ 。对染色体S1的每个基因Z $_{i}^{(1)}$

,选择S2中与Z $_{i}^{(1)}$ 距离最近的基因Z $_{j}^{(1)}$ 配对,已经配对的基因不再参加后续的基因配对。再将S2按基因配对的顺序重新排列,得到S*2。最后随机选择交叉点进行单点交叉得到下一代个体S′1和S′2。

1.5 变异操作

变异操作是一种局部随机搜索,与选择、交叉算子结合可以保证算法的有效性。本研究中采用按基因位(一个基因即为一个聚类中心)的维向量来进行,每个基因位的每维向量(一个浮点数)按变异概率Pm来发生随机变异。在整个算法开始之前,先求出每维向量的最大值和最小值,分别保存在向量 $v e c Μ a x [p]$ 与 $v e c Μ i n [p]$ (p为样本数据维数)中,可知所有最优聚类中心的第i(0〈i≤P)维向量的值一定介于 $v e c Μ i n [i]$ 与 $v e c Μ a x [i]$ 之间。同时约定随机变异的值应在 $v e c Μ i n [i]$ 与 $v e c Μ a x [i]$ 之间。这样既保证了群体的多样性,又可以避免盲目搜索,大大提高了搜索的速度和效率。

1.6 算法终止条件

只要满足以下2个条件中的任意一个条件则算法终止:

(1)算法迭代次数超过设定一个最大的迭代次数maxGen;

(2)运行过程中得到相同的最优结果次数连续超过某一阀值。

本文采用第2个条件作为结束条件。

2 算法描述

给定样本数据集合 $D = {d_{1} ‚ d_{2} ‚ \dots ‚ d_{i} ‚ \dots ‚ d_{n}}$ ,基于改进遗传算法的K-均值聚类算法具体过程描述为

(1)确定要生成的类簇数目k、种群规模为psize个个体及算法结束条件。

(2)先随机选择k个初始聚类中心组成一个个体 $C = {c_{1} ‚ c_{2} ‚ \dots ‚ c_{i} ‚ \dots ‚ c_{k}}$ ,对个体进行染色体编码,总共进行psize次,得到群体为psize个个体,设置初始迭代次数t=0。

(3)对数据集中的每一个样本数据di,依次计算它与各个聚类中心的相似度;将样本数据di合并到与其具有最大相似度的类簇中。

(4)按照相似度公式计算新的类簇的中心,组成一个个体,并计算新个体的适应度;

(5)对所有的个体实施遗传算子,得到下一代的群体;

(6)得到优化后的个体。如果所有聚类中心均达到稳定,则结束;否则,t=t+1,转(3)。

3 试验结果及分析

分别采用 k-均值算法、遗传K-均值算法(GA-K均值算法)和本文算法在VC++和MatlAB环境下进行仿真实验。遗传算法的交叉概率和变异概率初始值分别取为0.75,0.09,群体规模为100,迭代次数为100次,当运行过程中得到最优结果次数连续10次以上时算法结束。实验采用数据是Fisher的Iris 3种植物150样本个数据[9]进行10次试验,每个样本均为四维向量,代表植物的4种属性。三种算法分别单独运行10次,计算出簇内距离Ek与簇间距离Dk的最大值,最小值及平均值。实验结果见表1。

注:以上数据为单个算法运行10次的平均值。

聚类算法的理想结果是同时获得最小的簇内距离和最大的簇间距离。从表1中的数据可以看出,标准的K-均值算法由于对初始中心选取敏感性很大,在初始中心选择不当的情况下易陷入局部最优,出现过早收敛;GA-K均值算法由于个体的多样性不足而常出现早熟现象;本研究提出的算法在全局搜索能力方面优于K-均值和GA-K均值算法,所获得的聚类结果具有更强的稳定性,对于随机分布的数据聚类有明显的优越性;同时从达到最优解迭代次数看,本文提出的算法达到最优解的平均迭代次数要远少于K-均值和GA-K均值算法,所以本文提出的算法收敛速度更快。

4 结束语

本文对遗传算法和K-均值聚类算法进行了研究,针对K-均值聚类效果易受初始聚类中心影响的不足,为克服遗传算法引入K-均值算法所带来的易出现局部早熟的缺点,将免疫机制的选择操作引入遗传算法,使个体浓度和适应度同时对个体的选择操作产生作用,改变以往单纯以适应度来作为个体选择的依据,对算法进行改进,然后将改进的遗传算法引入K-均值算法中以优化聚类中心,提出一种基于改进遗传算法的K-均值聚类算法。试验结果表明,本研究的算法与传统的K-均值算法和GA-K均值算法比较,在全局搜索能力方面优于K-均值和GA-K均值算法,所获得的聚类结果具有更强的稳定性,能够有效改善聚类质量。

参考文献

[1]Jiawei Han,Micheline Kamber.数据挖掘概念与技术[M].北京:机械工业出版社,2005:185-218

[2]Bandyopadhyay S,Maulik U.An evolutionary technique based on k-means algorithm for optional clustering in rn[J].Information Sciences,2002,(146):221-237

[3]Ahmadyfard Alireza,Modares Hamidreza.Combining PSO and k-means to enhance data clustering[A].IST2008International Symposium[C].Tehran:IEEE Press,2008.

[4]Hai-xiang Guo,Ke-jun Zhu,Si-wei Gao,et al.Animproved genetic k-means algorithm for optimal clustering[A].Sixth IEEE International Conference[C].Leipzig:IEEE Press,2006.

[5]李茂军,罗安.单亲遗传算法的机理分析[J].长沙理工大学学报(自然科学版),2004,1(1):76-79

[6]贺志民,方美娥.基于遗传算法的特征值问题求解[J].长沙电力学院学报(自然科学版),2003,18(1)12-14

[7]赖玉霞,刘建平,杨国兴.基于遗传算法的K-均值聚类分析[J].计算机工程2008,34(20):200-202

[8]王磊,潘进,焦李成.免疫算法[J].电子学报2000,28(7):74-78

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

聚类分析是数据挖掘和模式分类中的一个重要研究部分,是非监督分类的重要方法。模糊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-均值聚类算法篇5

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} + Λ + (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-均值聚类算法篇6

模糊聚类广泛地应用于模式识别与图像处理的过程中, 其中模糊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 < \sum_{k = 1}^{Ν} u_{i k} < Ν, 1 \leq k \leq Ν, 1 \leq i \leq c$ , 记vi表示第i类的聚类中心。则X的一个模糊C-均值聚类的就是求如下目标函数的最小值:

$J (U, V) = \sum_{k = 1}^{Ν} \sum_{i = 1}^{c} (u_{i k})^{m} (d_{i k})^{2} (1)$

其中 $d_{i k} = | 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)} = \sum_{k = 1}^{Ν} (u_{i k}^{(l)})^{m} x_{k} / \sum_{k = 1}^{Ν} (u_{i k}^{(l)})^{m} (i = 1, 2, \dots, c), (l < m) (2)$

(3) 修正U:

$u_{i k}^{(l + 1)} = 1 / \sum_{j = 1}^{c} (\frac{d_{i k}}{d_{j k}})^{\frac{2}{m - 1}} \forall i, \forall k (3)$

(4) 对给定的ε>0, 实际计算时应对取定的初始值进行迭代计算直至 $\max {| u_{i k}^{t} - u_{i k}^{t - 1} |} < ε$ , 则算法终止, 否则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{cases} \max {x_{i j}} 当 x_{i j} 为效益型指标 \\ \min {x_{i j}} 当 x_{i j} 为成本型指标 \end{cases} (5)$

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

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

$\min J (U, V, c) = \sum_{k = 1}^{Ν} \sum_{i = 1}^{c} (u_{i k})^{m} (d^{'}_{i k})^{2} (6)$

$s \cdot t {\begin{cases} 0 \leq u_{i k} \leq 1 1 \leq i \leq c, 1 \leq k \leq Ν \\ \sum_{i = 1}^{c} u_{i k} = 1 1 \leq k \leq Ν \\ 0 ＜ \sum_{k = 1}^{Ν} u_{i k} ＜ Ν 1 \leq i \leq c \\ 1 \leq m ＜ \infty \end{cases}$

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

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

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

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

第一类:上海、北京;

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

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

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

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

3.1 Friedman检验的思想

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

$R_{i \cdot} = \frac{1}{Ν} (R_{i 1} + R_{i 2} + \dots + R_{i Ν}) i = 1, 2, \dots, s (7)$

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

$\begin{array}{l} R_{\cdot \cdot} = \frac{1}{s Ν} [(R_{11} + R_{21} + \dots + R_{s 1}) + \dots + (R_{1 Ν} + R_{2 Ν} + \dots + R_{s Ν})] \\ = \frac{1}{s Ν} [Ν (1 + 2 + \dots + s)] = \frac{s + 1}{2} \end{array}$

的周围, 而统计量:

$Q = \frac{12 Ν}{s (s + 1)} \sum_{i = 1}^{s} (R_{i \cdot} - \frac{s + 1}{2})^{2} ~ χ^{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.

动态均值聚类算法篇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.

【动态均值聚类算法】推荐阅读：

动态K-均值聚类算法09-03

C均值聚类算法08-17

均值聚类08-02

C均值聚类06-27

K均值聚类08-22

K均值聚类法06-30

模糊均值算法09-25

动态阈值算法08-20