C均值聚类

C均值聚类（共8篇）

C均值聚类 篇1

0 引言

聚类分析是数据挖掘和模式分类中的一个重要研究部分,是非监督分类的重要方法。模糊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算法无需计算样本模糊隶属度,降低了聚类算法复杂度,提高了算法的计算效率及精度,而且该方法可以推广到其他基于生物寻优的聚类算法。通过仿真实验验证了所提出算法的有效性和时效性。

关键词：模糊c均值聚类,隐隶属度,粒子群算法,目标函数,算法复杂度

C均值聚类 篇2

基才模糊C均值聚类和D-S证据理论的多传感器信息融合技术研究

D-S证据理论能很好地表达“不确定”和“未知”等信息融合中的.重要概念,在多传感器信息融合领域得到了广泛的应用.针对传感器数量较多时,D-S方法计算量很大的问题,提出了利用模糊C均值聚类来减少证据体数目.再结合D-S证据理论进行信息融合的办法.实验数据表明,该方法大大减少了计算量,保证了目标识别的准确度.

作 者：张公永 王平张佑春 ZHANG Gong-yong WANG Ping ZHANG You-chun 作者单位：西华大学电气信息学院,四川,成都,610039刊 名：国外电子元器件 ISTIC英文刊名：INTERNATIONAL ELECTRONIC ELEMENTS年，卷(期)：“”(5)分类号：V243 TP212.9关键词：模糊C均值聚类 D-S证据理论 信息融合

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

模糊聚类广泛地应用于模式识别与图像处理的过程中, 其中模糊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.

一种自适应的模糊C均值聚类算法 篇4

聚类分析[1]是数据挖掘的重要研究方向之一, 可以搜索并识别一个有限的种类集合或簇集合, 从而描述数据的特性。通过聚类可以帮助人们识别密集的和稀疏的区域, 发现数据全局的分布模式, 使同一聚类对象的相似性尽可能最大, 而不同聚类对象的相似性尽可能达到最小。也就是说, 形成聚类以后同一个聚类内的对象具有很高的相似性, 而且与不属于该聚类的对象有迥然的差异。聚类分析作为统计学的一个分支, 已经不仅仅是一个很重要的研究课题, 而且还具有非常广阔的应用背景。聚类分析在入侵分析、客户分类、空间数据处理、www文本分类、医疗图像自动识别、卫星照片分析、基因识别等领域有着相当广泛的应用, 在当前搜索引擎和信息检索急剧发展的互联网时代, 利用文本聚类分类新闻和资讯信息, 是各大搜索公司采用的主要方法。而且聚类分析自身的研究也是一个蓬勃发展的领域, 数据挖掘、机器学习、模式识别、统计学、空间数据库技术、计算智能和市场学等领域的发展也快速推动着聚类分析研究的进程, 使它成为数据分析和应用研究中的一个比较热门的话题[2]。

现在被广泛使用的聚类算法大多数都已知了数据集的类别数, 然后才对数据集进行划分, 然而在通常情况下, 我们获得的许多数据集是没有任何先验知识的, 类别数未知或不能用近似的方法得到。例如, 当一个数据集的维数很高时, 许多特征可能彼此交叉重叠, 此时利用数据的可视化去获得数据集的类别数是很困难的。在针对现实中聚类数目不可预知的问题上, 传统的类别数先验的聚类算法已然不能胜任、担当起处理、解决此类问题的主角。自动聚类算法, 即针对那种聚类数目不可预知问题的算法, 已悄然成为当今聚类领域研究的热点与前沿。由于自动聚类不需要先验的类别数, 故这类算法更具有解决现实问题的意义。而且, 自动聚类又可以与先前已存在的聚类算法相结合, 即又能继承前人所做的工作, 故自动聚类算法的研究又能很好地承接起前人的工作结晶, 便于自身的发展。鉴于以上提到的诸多因素, 本文的主要目的在于研究自动聚类问题。

2 模糊C均值聚类算法

基于目标函数聚类算法中, 模糊C均值类型的算法理论是最为完善、运用最为广泛的。模糊C均值类型算法最初是从硬聚类目标函数的优化中推导出来的。为用目标函数法来解决聚类问题, 人们构造带约束条件的非线性规划函数, 因此类内的平方误差和J1作为聚类的目标函数形式。为了要使该目标函数极小化所以采取Pikard硬C均值算法以及ISODATA算法。提出模糊划分概念以后, Dunn先将WGSS函数扩展到了诸如同类内的加权平均误差和的函数, 而后Bezdek再次引入参数m, 把其推广到了目标函数中的无限族, 并且提出了交替优化的算法, 就是我们所熟知的模糊C均值算法[3]。

2.1 数据集c的划分

设数据集, 为空间中n个一组有限观测的样本集, 是观测样本xj的特征向量或者模式向量, 对应于特征空间之中的一个点, xjk为特征向量xj的在第k维特征的赋值。对于给定的样本集X聚类分析是需要产生X的c划分。假设数据集X是c划分得到了c个子集是X1…Xc, 若它们满足 (1) 的条件, 就称其为X的硬c划分:

若用隶属函数表示样本xj与子集Xi (1≤i≤c) 之间的隶属关系, 那么硬C划分中μij为子集Xi的特征函数, 显然有μij∈ (0, 1) 所以X硬C划分同样是能通过隶属度函数来表示的, 就是构成的矩阵U=[μij]c×n用c个子集的特征函数值来表示。特征矩阵U中的第i行是第i个子集的特征函数, 然而特征矩阵U中的第j列是样本Xj相对c个子集隶属函数。那么X的硬c划分的空间为:

Ruspini运用模糊集的理论将隶属函数从{0, 1}二值推广到了[0, 1]区间, 使得硬c划分的概念扩展到模糊c划分, 从而得到了X的模糊c划分空间表示为:

2.2 硬C均值聚类算法

硬C均值算法作为数据集X实现硬C划分典型的算法, 更是最受提倡的算法。它可以将数据集X划分为c个超椭球结构的聚类。硬C均值算法将典型的聚类问题归纳到以下非线性的数学划分问题:

其中U=[μij]c×n为硬C划分矩阵, V= (v1, v2, …, vc) 是c个聚类的中心, ‖·‖表示欧氏距离。

硬C均值算法其具体的流程为:

初始化:设定聚类的类别数c, 其中2≤c≤n, n为数据的个数, 迭代的停止阈值ε的设定, 初始化聚类的中心V0, 设定迭代的计数器b=0;

步骤一:依据公式 (5) 来计算或者更新划分的矩阵Ub=[μij];

步骤二:根据公式 (6) 来更新聚类的中心Vb+1:

步骤三:如果那么算法停止算法并且输出划分的矩阵U以及聚类中心V;否则, 令b=b+l, 跳到执行步骤一。

2.3 模糊C均值聚类算法及其存在的问题

Dunn曾依照Ruspini定义模糊划分的概念, 将HCM算法扩展到模糊的形式。为能实现这一扩展, Dunn把每一个样本和每一个聚类中心的距离使用隶属度平方加权, 使得类内误差平方和目标函数扩展到了类内加权误差的平方和的函数:

Bezdek又把Dunn的目标函数扩展成更加普遍化的形式, 提出基于目标函数模糊聚类普遍描述:

其中m∈[1, ∞) 称为加权指数, 别名平滑参数。即使从数学的角度看, m是不自然的。但是若不对隶属度进行加权, 那么硬C均值算法到模糊C均值算法的扩展会是没有效的。

模糊C均值算法具体的流程为:

初始化:规定聚类的类别数c, 2≤c≤n, n为数据个数, 迭代停止阈值ε设定, 初始化聚类中心V0, 设定迭代计数器b=0;

步骤一:根据公式 (9) 计算或者更新划分矩阵

步骤二:根据公式 (10) 计算或者更新聚类中心:

步骤三:如果, 那么算法停止, 并且输出划分矩阵U以及聚类中心V;若不然, 则令b=b+l, 跳到执行步骤一。

FCM算法是当今较为流行的模糊聚类算法, 研究其原因有以下几个方面:首先模糊C均值的泛函Jm依然是传统的硬C均值泛函J1推广得到的, 我们知道, 硬C均值泛函J1的聚类准则其应用特别广泛的, 对于其研究理论已经非常完备, 这就为Jm的研究奠定了良好的基础。从数学角度上看Jm和RS的希尔伯特空间结构密切相关, 所以比其它泛函数学基础更为深厚。

在大量模糊聚类算法中, 模糊C均值类型的算法理论是最完善的, 它不但数学基础深厚, 而且成功运用到许多领域, 是当今最为实用也是最受欢迎的算法。即使这样, 该算法依然不是无懈可击的, 存在着许多遗留问题, 其中尤为突出的是由于模糊聚类目标函数是非凸的, 而FCM类型算法是通过迭代法来实现的, 所以这个算法对初始化十分敏感, 那么就特别容易陷入局部极小值, 就无法得到全局最优解。模糊C均值聚类算法要求有预先确定的聚类数目, 对于不同的数据集, 给定相同的聚类数c, 所产生的聚类效果不同;而对于相同的数据集, 给定不同的聚类数c, 所产生的聚类效果也会有很大的差异。

虽然模糊聚类作为一种无监督分类, 可是当前的FCM类型的算法是要求聚类类别数的先验知识, 不然算法就会产生错误, 那么它就会破坏算法的自适应性以及无监督性。FCM类型的聚类算法属于划分式的方法, 对于给定的样本集, 无论数据中是否存在聚类结构, 无论分类结果是否有效, 它总会将数据划分成c个子类。换言之, 现有的聚类趋势与聚类分析以及有效性分析是分离的、隔断的。

3 自适应的模糊C均值聚类算法

自适应的模糊C均值聚类算法是模糊C均值聚类算法的改进版本。在模糊聚类算法的基础上, 通过运用有效性函数来自动获取聚类数目, 然后进行模糊聚类, 从而实现了聚类结果一体化。同时, 因为自适应的模糊C均值聚类算法不需要输入聚类数目, 解决了模糊C均值聚类算法对初始值敏感的问题, 改进的模糊C均值聚类算法不会陷入局部最优解, 并且对于相同的数据集, 自适应的模糊C均值聚类算法所求得的结果是一致的, 具有很好的稳定性。

3.1 有效性函数

评估聚类结果的问题被人们称之为聚类的有效性问题。概括来说, 寻找最优划分或最佳聚类数C以及聚类结果的有效性的验证都称为聚类有效性问题[4]。为了解决聚类有效性问题, 其中有一个构造聚类有效性函数有效方法, 探索合理的聚类的有效性指标并且利用这些指标来评价聚类有效性。对于聚类的分析来说, 有效性指标的问题还能转化为确定最优分类数C的问题, 因此这是基于目标函数聚类。通过聚类的有效性指标, 进行一种迭代的过程来把数据集最优聚类结果及其分类数目确定。通过运用不一样的参数c运行指定的聚类算法在已知的数据集上, 进行多种的划分。计算每一种划分指标值, 最后, 通过比较分析每一个指标值的大小及变化情况, 确定符合预定条件的指标值所对应的参数c被认为是最佳的聚类数[5]。

聚类的有效性函数Vw具体定义[6,7]:

Com (Uc, Vc) 是紧致性度量, 定义如下:

Sep (c, Uc) 是分离性度量, 定义如下:

因为紧致性, 度量函数和分离性度量函数通常不在同一个数量级, 因此通过最大值的方法将它们进行标准化:

定义是紧致性度量与分离性度量的比较值。紧致性度量的值越小就表示同一类中数据的差异就越小, 即分散的程度就越小, 分离性度量的值越大就表示不同类之间的数据差异就越大, 即类间的分离程度就越大。因此, Vw的最小值就应该对应最佳的模糊C聚类数c。

3.2 自适应的模糊C均值聚类算法模型

设, 它的模糊C划分可以使用模糊矩阵U=[μij]∈RCN表示, 矩阵U的元素μij用来表示第j (j=1, 2, …, n) 个数据点是属于第i (i=1, 2, …, c) 类的隶属度, μij应该满足下面的条件;当今广泛使用取类内加权误差平方和的极小值的聚类准则, 即:, 式中V是聚类中心, m是加权指数[8]:

自适应的FCM聚类算法的具体过程如下:

步骤一:初始化FCM算法和Vw函数的参数:

步骤二:对于已知的数据集以c作为分类数应用FCM算法, 求出相应的聚类中心VC和模糊矩阵UC;

步骤三:利用步骤二中的结果, 计算并储存紧致性度量Com (Uc, Vc) 和分离性度量Sep (c, Uc) , c=2, 3, …, cmax;

步骤四:如果c<cmax, 令c=c+1, 转到步骤二, 否则转到步骤五;

步骤五:对和, c=2, 3, …, cmax进行标准化, 并根据, U, 计算出其有效性函数的值;

步骤六:找出最小值, 并记录与之对应的聚类数目;

步骤七:把作为最优聚类数目, 进行FCM算法聚类, 得到相应的聚类结果, 即最优的聚类结果。

4 仿真结果与分析

4.1 较为清晰数据集的自动聚类仿真实验

为了验证自适应的模糊C均值算法的可行性和有效性, 选择2个较为清晰的数据集进行实验测试。数据集分别为数据集1:较为清晰的可分为4类的三维数据点;数据集2:较为清晰的可分为5类的三维数据点。

数据集原图如图1所示, 数据集自动聚类结果图如图2所示。

4.2 较为模糊数据集的自动聚类仿真实验

为了验证自适应的模糊C均值算法的可行性和有效性, 选择2个较为模糊的数据集进行实验测试。数据集分别为数据集3:较为模糊的可分为5类的三维数据点;数据集4:较为模糊的可分为3类的三维数据点。

数据集原图如图3所示, 数据集自动聚类结果图如图4所示。

4.3 实验结果分析与评价

根据上述实验结果进行比较可以分析出, 自适应的模糊C均值算法对于较为清晰的数据集, 可很好实现自动聚类的功能;而对于较为模糊的数据集, 同样可以实现自动聚类的功能。

自适应的模糊C均值聚类算法不依赖任何初试条件, 通过利用有效性函数自动获取最优的聚类数目, 实现了聚类全过程无须人为干预的目的, 并且具有良好的可行性和有效性, 实现了自动判定类别数的功能。

5 结束语

传统的模糊C均值聚类算法因为要求输入聚类数目的先验知识, 所以对初始值敏感, 给定不同的聚类数目, 所产生的聚类效果会有很大的差异。针对传统算法的不足, 本文结合有效性函数提出了自适应的模糊C均值聚类算法, 该算法运用有效性函数来自动获取聚类数目, 然后进行模糊聚类, 实现聚类结果的一体化。在仿真实验中, 利用改进算法分别处理较为清晰和较为模糊的数据集, 通过分析仿真结果发现, 自适应的模糊C均值聚类算法不依赖任何初始条件, 无需人为干预就能很好的得出最优解, 不仅保证了聚类结果的正确性, 同时实现了自动判定类别数的功能, 具有良好的可行性和有效性。

参考文献

[1]李雷, 罗红旗, 丁亚丽.一种改进的模糊C均值聚类算法[J].计算机技术与发展, 2009, 19 (2) :71-73.

[2]张雷, 李人厚.基于免疫原理的一种动态数据聚类算法[J].控制与决策, 2007, 22 (4) :469-472.

[3]高新波.FCM聚类算法中模糊加权指数m的优选方法[J].模糊系统与数学, 2005, 19 (1) :143-148.

[4]唐明会, 杨燕.模糊聚类有效性的研究进展[J].计算机工程与科学, 2009, 31 (09) :122-124.

[5]Weina Wang, Yunjie Zhang.On Fuzzy Cluster Validity Indices[J].Fuzzy Sets and Systems, 2007, 158 (19) :2095-2117.

[6]Yunjie Zhang, Weina Wang, et al.Cluster Validity Index for Fuzzy Clustering[J].Information Sciences, 2008.178:1205-1218.

[7]董云影, 张运杰, 畅春玲.改进的遗传模糊聚类算法[J].模糊系统与数学, 2005, 19 (2) :128-133.

C均值聚类 篇5

聚类分析是按照个体之间的相似性对个体进行的类别划分,同类间个体相似性较大,不同类个体相似性较小。C-均值聚类算法是聚类算法的一种。现代雷达告警系统的任务是在威胁系统可能发射武器之前向驾驶员发出可靠报警。雷达告警系统对信号分选要求快速、准确,传统分选方法速度较慢。因此本文中采用改进的C-均值聚类算法,完成对信号的正确分选。

1 改进的C-均值聚类算法概述

1.1 C-均值聚类算法概述

C-均值算法是一种基于样本间相似度的聚类方法,属于非监督学习方法。此方法是随机选取几个样本X中的元素xi(i=1,2,…,N),按照某种方法根据元素间的相似程度划分成C类,使得同一类中元素相似程度较高,不同类元素之间相似程度较低,将同类所有元素平均值作为相似程度的度量标准,称为类中心。当新增一个元素xj(j=1,2,…,N)需要划分到类中,将它划分到距离类中心最近的类中,同时修正该类的中心值,重复这个过程,直到样本X所有元素都划分到类中。

C-均值算法是一种较典型的逐点修改迭代的动态聚类算法,下面介绍其基本原理。

设样本xi(i=1,2,…,N)为样本X中的元素,Cj为样本X中元素组成的第j类聚类,Kj为Cj中的元素个数,lj是第j类所有元素的均值,那么有

lj即为聚类Cj的中心,是衡量相似度的计算标准。将Cj中的各元素x与均值li的误差平方和对所有类相加后为

显然,Wr是误差平方和,Wr度量的是r个元素集C1,C2,…,Cr和相应的r个聚类中心l1,l2,…,lr所产生误差的平方和,所以它是元素数据集和类别数的函数。对于不同的聚类而言Wr是不同的,所以最小均方误差准则下的最优分类必然是使Jc极小的聚类。

C-均值聚类的要点和核心是:以误差平方和Wr为准则函数,算法把n个向量xi(i=1,2,…,n)分为r个组Cj(j=1,2,…,r),并求每组Cj的聚类中心lj(j=1,2,…,c),逐点修正类中心,使得Wr达到最小。要达到最小均方误差准则下的最优分类,对样本的划分尤为重要,一般是选择一些代表点作为聚类中心,然后按照某种准则将其余的点分到各类中。而且初始代表点的选择直接影响到聚类结果的优化程度。

1.2 改进的C-均值聚类算法

经典的C-均值聚类算法存在两个方面的问题:一是算法对初始聚类中心的选取直接影响聚类迭代的效果和速度;二是需要预知实际的聚类数目。这就局限了算法的应用领域和效果。

针对C-均值聚类算法存在的弊端,采用文献[1]提出的改进C-均值算法,直接用样本的初始值进行初始分类,用点到聚类中心的距离是否在误差范围内作判断标准进行分类,而不需要计算点到每个中心的距离。

2 改进C-均值聚类算法的雷达告警系统信号分选

雷达告警系统是对PDW流作处理,找出满足条件的PDW流信息。每一个脉冲描述子(PDW)包含信号的脉宽(PW)、载频(RF)、脉冲到达方向(DOA)和脉冲到达时间(TOA)等信息。告警系统流程可分为3部分:第一步分对各频段接收到的在频段内的信号进行灵敏度判断,满足灵敏度条件的PDW流进行脉冲参数的测量;第二步是测量后的PDW流的粗分选;第三步是将分选得到的PDW脉冲类与雷达告警库的告警参数比较,对满足告警条件的脉冲输出其告警参数信息,其中雷达告警库告警参数包括PW、PRI、RF、同一辐射源连续脉冲个数。

在雷达告警系统中必须同时满足雷达告警库的PW、PRI、RF和同一辐射源连续脉冲个数这4个参数条件的脉冲流,才能进行威胁告警指示,所以考虑在雷达告警系统中,把经过测量后的雷达脉冲串(PDW),首先,按照DOA、PW和RF进行分选,因为属于同一DOA、PW和RF范围的脉冲流很可能属于同一辐射源;其次,再对每一类进行PRI分选,这样使得PRI分选和后续工作更容易。脉冲告警系统分选的流程如图1所示,分选的目的是将属于同一辐射源且满足告警条件的信号筛选出来进行威胁告警指示。

由于雷达的空间位置不会在短时间内发生明显变化,故可以先按到达方向(DOA)进行初步分选,由于PDW流中RF,PW参数相对固定性,故在DOA分选后可对RF PW进行联合分选最后进行PRI分选。本文只讨论利用文献[2]提出的改进的C-均值聚类算法对PDW流进行的DOA分选和RF PW联合分选,不做PRI聚类,因为PRI种类多、变化快,不适合聚类处理。具体处理流程如图1所示[3,4,5]。

文献[1]的分选流程,DOA的分选的步骤如下:

(1)读入经过测量可信的PDW流作为待分选的PDW流,此PDW流的第一个脉冲的DOA参数作为第一个DOA聚类的类中心。

(2)取PDW流的下一个脉冲的PDW描述字信息,将其DOA参数与第一个DOA聚类的类中心进行比较,若比较结果值小于设定的容差范围,则将该脉冲所有参数信息分配到该聚类中,同时需重新计算该DOA聚类的平均值,即类中心,并读取PDW流下一个脉冲的PDW描述字信息,继续进行比较。相反,若比较结果值大于设定的容差范围,直接跳转到下一步

(3)比较结果值大于设定的容差范围,认定为匹配不成功,此时需判断是否己经与所有聚类的类中心进行了比较,若没有,则仍需与下一个聚类类中心进行比较。相反,如果和全部的聚类类中心都进行了比较但没有匹配上,则应增加一类聚类类别,将该脉冲DOA参数作为新聚类的类中心。然后读取下一个脉冲继续进行比较,重复步骤(2)和步骤(3)的操作过程。

(4)如果最后一个脉冲已归到某个聚类中,剔除脉冲数少于5个的聚类,因为这些脉冲已无法进行PRI分选,DOA分选结束。

RF、PW联合分选步骤和DOA的分选类似,所不同的是:

(1)读入脉冲流是经过DOA分选的PDW流。

(2)每个聚类都是以RF和PW参数同时满足在各自分选容差范围内作为判断条件的。

由于此次聚类算法仅将在各参数设置范围内具有相似性的脉冲归类,归类完后实际情况中有可能存在几类都属于同一部雷达的情况,还需要根据实际掌握的信息和情况进行合并。

3 算法仿真

为了验证算法的有效性,模拟了3组不同辐射源夹杂干扰噪声的脉冲信号,按照脉冲到达时间顺序进行混合。每个辐射源PDW流包括PW、RF、DOA等参数。参数取值情况与抖动如表1所示,同时由于测量误差的原因,脉宽、载频、到达角有一定偏差。

在这里对以上数据作出解释,由于本雷达告警系统测向范围在(0°～360°)取3个典型值;同时告警系统将频率划分为6～8GHz、8～12GHz、12～18GHz这3个频段,故频率取各频段一典型值,由于不作频率测量只是简单划分故其偏差较小;脉宽测量时计数器频率高偏差较小。在仿真中为了模拟PW,RF,DOA测量值,给PW,RF和DOA加上各自随机偏差。在以上3组数据的基础上加入均匀分布干扰数据。

加入干扰数据之后,所形成的原始数据如图2和图3所示。

首先经过DOA聚类分选处理之后,得到具体的聚类结果如图4和图5所示。

其次再经过PW RF聚类分选处理之后,得到具体的聚类结果如图6所示。

从图4可以看到,噪声到达角度被进一步剔除掉。从图5和图6可以看到噪声频率、脉宽被进一步剔除掉。同时属于同一雷达辐射源的PDW脉冲流被归类到同一类别中以利于后续的分选和告警识别

该算法能自动确定分类数并且能对噪声点进行剔除,同时起到稀释脉冲流和分类具有相似性脉冲的作用,从而避免了噪声对后续分选工作产生的影响,同时使后续分选变得简单。

4 结束语

本文介绍了改进的均值聚类算法在雷达告警系统信号分选中的应用,并通过仿真进行了验证。从仿真结果看,该方法利用聚类算法的对相似个体进行分类性质进行分选,同时利用文献[1]提出的改进C-均值聚类算法无需预知设定的聚类数目,克服了传统分选方法速度慢且数据量大时易失效的缺点,对雷达告警系统雷达信号的快速准确分选和后续处理有积极的促进作用

参考文献

[1]李峰.复杂环境下雷达辐射源信号分选算法研究[D].西安:西安电子科技大学,2009.

[2]李雷,罗红旗,丁亚丽.一种改进的模糊C均值聚类算法[J].计算机技术与发展,2009,12(19):71-73.

[3]赵国庆.雷达对抗原理[M].西安:西安电子科技大学出版社,1999.

[4]祝正威.雷达信号的聚类分选方法[J].电子对抗,2004(6):6-10.

C均值聚类 篇6

1 经典的模糊C均值聚类分割算法

由Bezdek提出的模糊C均值聚类算法,其实质是根据图像分解后像素样本与每个聚类中心的加权相似性测度,通过对目标函数进行非线性迭代优化方法,然后确定最优聚类,它给出每个样本隶属于某个聚类的隶属度,即使对于很难明显分类的变量,FCM也能得到较为满意的效果。FCM通过将图像I = { f( x,y) ,0 ≤ x < m,0 ≤ y

式中: Q = [qik( x,u) ]为模糊分类矩阵; P = [p1,p2,…,pc]为聚类中心集合; m ∈[1,∞ ) 是控制聚类结果的权指数,一般赋值为2; Dx( x,y) 为f( x,y) 到聚类中心pk的距离,表示为

图像FCM分割就是通过多次迭代确定隶属度函数和聚类中心,使目标函数获得最小值。利用拉格朗日乘数法来求解使得J( Q,P) 达到最小值的满足下列等式

Bezdek利用梯度下降方法,通过对模糊分类矩阵Q与聚类中心矩阵V不断进行迭代算法,以修正聚类中心值以及各样本的隶属度,最终寻找出样本数据所含有的分类特性,使各样本划分到其隶属度最大的一类中。该算法对初始聚类中心或隶属度矩阵有较为敏感,参数初值选取决定着聚类结果的优劣和稳定性; 当初始聚类中心偏离全局最佳聚类中心比较大时,FCM很有可能陷入局部最小值。

2 近似模糊C均值聚类的中心初始化

2. 1 数据约简

聚类分析作为统计模式识别中有监督模式分类的一个重要组成部分,在无监督模式分类任务中,由于聚类标签较少而无法使用近邻一致性准则。本文利用曲福恒的研究结果,对数据进行最近邻一致性准则精简,不仅大幅降低数据量,还尽量保持约简数据后所包含的聚类结构信息,得到与模糊C均值接近的聚类中心。

设原始数据集合M中含有i个不同的样本M = { m1,m2,…,mn} Rs。分析聚类问题就是将{ m1,m2,…,mi}区分为M中的c( 2 ≤c < i) 个子集,相似的样本应要求尽量在同一子集( 聚类) 内,c为聚类数目。约简后数据集合为N = { n1,n2,…,ni} Rs。D( m,S) 表示数据m与数据集合S间的距离。则数据约简算法的步骤如下:

1) 初始化阈值,其中 γ,l = 1,nl= m1,j = 2 。

2) 对聚类样本数据mj,计算整数值r ,使其满足

3) 如果D( mj,nr) > γ,l = l + 1,nl= mj; 否则,令nr=nr∪mj,j=j+1。

4) 如果j < i ,则转到步骤2) ; 否则,将nk更新为其自身数据集合的平均值。

2. 2 加入特征空间中的模糊核聚类算法

在线性空间中难以划分的问题利用核映射处理来处理,将数据从线性空间映射到高维的非线性空间解决。

先通过一个非线性映射 Φ: X→F( X∈Rp→Φ( x) ∈Rq,q > p) 将输入空间X变换至高维特征空间F ; 然后在特征空间F中进行聚类。

对在FCM目标函数中使用核映射,则得到目标函数

其中

由核代入技巧知,上述内积定义了F中的一个核函数K( x,y) ,满足K( x,y) = ( fk( x,y) - pk)T( fk( x,y) -pk) 。Dx( x,y) 为特征空间中的欧氏距离,由于核的代入,在原输入空间中诱导出了一类核依赖的新的距离度量,由此将FCM在欧氏距离下的执行推广到了同一空间中不同距离度量的新的聚类。

本文将式( 6) 中高斯核函数代入式( 5) 中,得到目标函数为

使用拉格朗日数乘法,首先对qk( x,y)m求偏导数,得到隶属度迭代式

由约束条件, 可得

求出 λ 代入式( 9)

利用高斯核函数,代入高斯核函数,则目标函数变为

可以解得聚类中心迭代表达式

2. 3 加入空间约束信息

对图像进行非线性高维聚类划分后,通过表征空间邻域像素对初始聚类中心作用的先验概率来修正各像素样本的聚类划分,形成最终修正的分割效果。利用Chuang Keh - Shih的研究成果,对已完成高维非线性空间核聚类划分后并进行数据约简的图像进行空间邻域隶属度约束处理。划分后的邻域信息为

式中: NB( fj( x,y) ) 表示像素fj( x,y) 的领域大小; qim( x,y) 表示像素fm( x,y) 属于i类的隶属度值。Hik的值是除了当前空间像素领域区域内其他像素属于i类的隶属度和。经过邻域隶属度约束修正后的隶属度的迭代表达式为

式中: p ,q是正则化参数,用于控制最终隶属度值的控制参数。式( 14) 表示邻域空间中某一类的像素和其空间邻域中像素同属于一个类时Hik的值就越大,对原始隶属度的修正就越大,反之则像素隶属度值就减小。最终本文的分割算法过程步骤如下:

1) 选择聚类有效性指标计算方法,设置模糊系数m ,设定聚类个数的最小值cmin、最大值cmax。

2) 采用本文2. 1 节的方法得到约简后的数据集合Nc={n1,n2,…nic}Rs。

3) 采用核估计方法实现聚类中心的估计,确定初始聚类中心。

4) 再根据式( 12) 与式( 10) 分别计算或更新初始聚类中心和划分矩阵。

5) 利用式( 14) 修正隶属度原型模式。

6) 判断迭代次数达到事先设定的最大次数,达到迭代次数则停止,否则继续迭代。

3 实验结果分析

为验证本文所提算法的有效性,对正常大脑磁共振图像进行实验。初始参数设置: 矩阵指数m = 2,单步最小变化为0. 000 5,最大迭代次数为100,聚类类别数为8,核参数均为150。参与比较的算法为原始的模糊C均值聚类算法、PSOFCM算法、KFCM算法、DWKFCM和本文算法,所有算法收敛精度相同且为 ε ,其他参数按原有文献设定,运行20 次取平均值。

为了验证几种分割算法的量化比较,采用合成图像的分割精度和运行时间均值作为分割评价指标,定义合成图像的分割精度为

图1 为FCM算法、PSO _ FCM算法、KFCM算法、DWKFCM算法及本文算法分割后图像与本文算法的比较结果。

图1a为是一幅181 ×181 像素的大脑磁共振图像,图1b为原始FCM算法,图像分割效果有些模糊,一些细节还没有分割出来,图1c分割效果对比FCM算法稍好,但在中间部位的信息有一定的丢失。可以看出,本算法分割效果不错,不但误分割很少,且分割的脑灰质和脑白质边缘也很光滑,在传统模糊核聚类算法与动态加权模糊核聚类算法的分割结果里,都有较多的脑白质被误分为脑灰质和脑脊液,同时分割的目标边缘也毛糙; 减小了过度分割的现象,又保留了图像的细节部分,图像中的主要目标较为准确、清晰地分割出来。

图2 是FCM、KFCM、DWKFCM和本文算法四种算法对图1a进行分割时的算法收敛次数对比图。从图2 可以看出,本文算法收敛次数很少,在很短时间内就能找到目标函数的最小值,具有明显的速度优势。

表1 为FCM、PSOFCM、KFCM、DWKFCM和本文算法的性能比较结果。

从表1 可以看出,在同一迭代次数处,本文算法从图像分割精度和运行时间上都大大高于其他几种算法,实验表明本算法具有较好的适应性和鲁棒性。

4 结束语

C均值聚类 篇7

图像分割就是指把感兴趣的目标与背景分离出来, 并按照不同的含义把目标分割开来, 也就是提取目标。图像分割在图像处理中占了非常重要的位置, 是图像处理中从图像预处理到图像分析处理最为关键的一步骤。一方面它对特征测量、特征提取及度量有重要的影响作用, 是目标表达的基础;另一方面, 对图像分析和理解在图像分割后更加容易[1]。

图像分割是图像中阳性细胞的提取、定量分析的重点。好的图像分割法能对阳性细胞进行计量分析, 并且能进行形态分析等, 图像分割问题的解决对临床病理医生的定量分析、百分比计量具有重要的作用。在临床诊断研究、医学科研研究、病理诊断分析、医学影像信息处理、计算机辅助疾病诊断等方面, 图像分割的应用范围十分广泛。在这些图像处理应用中, 图像分割是不可缺少的一步, 且也是最关键一步。

2 C-均值聚类算法

目前, 图像分割有很多方法, 归根到底, 主要有三种不同的途径。图像分割没有通用的、标准的、唯一的方法。分割方法主要包括:灰度阈值分割法、边缘检测法、区域分割法和聚类法等[2]。

C-均值聚类分割算法最早是由J.Mac Queen提出的, 是在误差平方和准则上把图像分成C类区域[3]。在C-均值聚类分割算法中先要一个准则函数, 依据样本和聚类中心之间的距离, 选择初始聚类中心C个, 划分类别, 然后每一个类的聚类的中心再重新计算。反复不断地对这个过程进行操作, 算出准则函数的值是最小为止, 一般来说都应该选择样本以及其聚类中心的平方误差的总和为准则函数[4]。C-均值聚类算法可以做动态聚类是其最为突出的优点且也是一种不许需要任何方法监督的学习算法。显微细胞彩色图像含有三基色数据, C-均值聚类算法直接运用在显微细胞彩色图像的分割中将难以进行。因此在运用C-均值聚类算法分割前必须要对显微细胞彩色图像进行处理, 将分割样本的数据量减少, 使C-均值聚类算法运行时间缩短。C-均值聚类算法运行如下[5]:

2.1从初始化聚类中心的所有数据点中任取c个初始类均值。

2.2进行迭代, 在第K次时就将数据x归为类Cj (其中j=mini{ (x-mi) }) ;那么均值离Cj最近的类即为数据x。

2.3将类均值更新

2.4假如i符合mik+1=mik, 则算法结束;否则返回 (2) 重新运行。

C-均值聚类算法最主要是要依赖于聚类中心的初始的位置来进行迭代, 在进行运算的过程中并不能保证其结果都是收敛于最优解。所以, 为了使运算结果能够更加的接近正确值, C-均值聚类算法在选择初始聚类中心的方法上要进行比较。C-均值聚类算法在选择初始聚类中心的方法有很多种, 有的在开始就应用已经确定好的n个初始聚类中心, 然后再反复地运算;还有的是先确定一个任意隶属矩阵, 然后再来运算;C-均值聚类算法也可以通过时间平均, 以在线的方式运行, 导出聚类中心。

在上述的算法中确定好n个初始聚类中心的这种C-均值聚类算法最具有代表性。

3 Ki-67彩色图像分割方法

在本文中以Ki-67彩色图像在HSI空间的特点为例, 提出Ki-67彩色图像分割方法:基于色度学准则先建立一个Ki-67彩色图像的色度学准则, 将Ki-67彩色图像粗分割成只有阳性图像;然后在此基础上用C-均值聚类算法对粗分割后的图像分割, 提取阳性细胞;最后对分割后的阳性细胞图像进行修正, 从而计算出阳性细胞的个数和面积。

3.1进行图像增强处理, 将图像中绿色区域背景颜色值加强,

3.2利用Matlab工具箱对图像进行预处理。

3.3运用色度学准则分割增强后的图像, 分割出包含有阳性细胞图及其它颜色的色彩区的图。

3.4根据此图的特征确定初始聚类中心, 按以下方式确定初始聚类中心:m1=min (X) , m2= (m1+m2) /2, m3=max (X) , X是分割出具有阳性细胞图中的每个像素的R分量值, 将已经确定的聚类数3平分为3类, 使其类间距最大化。

3.5运用C-均值聚类分割法分割该图像, 图像中的每个像素与聚类中心的距离计算出并归集到距离最近的类别中, 每个类别像素值的平均值又再一次计算, 并且其作为下一次迭代的聚类中心, 重复几次, 直到聚类中心值前后两次相等, 那么算法完成。

3.6分割出阳性细胞并提取出来, 对彩色图像进行二值化处理, 然后运用定量分析法对阳性细胞进行定量分析[5]。计算出阳性细胞数量并算出所占百分比数, 可以用于对Ki-67图像定量分析, 对肿瘤进展及预后有较强的数据依据。

4结语

因此, C-均值聚类是最基本的聚类分割方法在显微彩色图像分割中是简单直观、且较易操作, 在图像的彩色数据中聚类方法可以将其看作完整的个体来进行处理并且分割, 可以得到较好的效果。C-均值聚类是最基本的聚类分割方法, 也是最常用的方法。

参考文献

[1]张伟, 王军锋, 王涛, 等.一种基于改进算子的形态学边缘检测算法[J].计算机技术与发展, 2013, 23 (6) :23-26.

[2]侯青, 李伟, 任娜娜, 等.一种改进的中草药显微图像边缘提取算法[J].计算机技术与发展, 2014, 24 (8) :243-245.

[3]刘志文, 安兴, 李衡, 等.显微细胞图像分析方法的研究进展[J].北京理工大学学报, 2014, 34 (5) :441-453.

C均值聚类 篇8

由于电气设备故障原因和故障现象的复杂性、模糊性和不确定性,传统故障诊断方法所诊断的结果准确率并不高,传统诊断方法(IEC三比值法、改良三比值法等)属于单故障、渐发性故障的简单诊断技术。近年来,人们借助模糊理论[1]、神经网络理论、灰色系统理论等人工智能方法探索变压器故障诊断的方法,并取得了一定的成就。

在最为常用的三比值判断法则中,比值编码区间具有明确的边界,这种处理使得三比值法简单明了、便于推广,但同时也使得三比值法在比值区间的边界处易造成误判断,有些比值找不到对应规则的缺陷。变压器故障诊断在本质上属于模式识别范畴问题,FCM算法是基于模糊划分的思想,利用迭代方法,在泛函极值意义下,不断修正聚类中心的局部优化算法,国内一些学者利用该方法对变压器绝缘故障进行诊断效果不很理想。主要原因是FCM算法具有将数据集合进行相等划分的趋势,而在变压器绝缘故障中,不同故障类型产生的主要特征气体及气体组分含量存在很大差异,以油中溶解气体体积数为特征量构成的样本,典型程度不一样,应区别对待。因此,本文提出加权模糊C均值聚类算法实现权值计算和优化,完成故障聚类与诊断。

1 FCM算法

设X={x1,x2,…xn}是待聚类分析的数据集,其中xj={xj1,xj2,…xjs}表示第j个样本的s个特征值,聚类中心矩阵为V={v1,v2,…vc},c为聚类类别数,vi={vi1,vi2,…,vis}表示第i类的聚类中心,其模糊矩阵U={uij|i=1,2,3…,c,j=1,2,3,…,n},元素uij表示第j个数据点属于第i类的隶属度,满足如下约束条件:

FCM算法的目标函数:

式中:m为权重指数,m∈[1,+∞],在实际应用中m的的最佳取值范围[2]为[1.5,2.5],本文中m取为2;J(U,V)是误差平方和目标函数;dij为样本到中心矢量的距离,dij=‖xj-vi‖。

模糊聚类准则是求得适当的模糊划分矩阵U={uij}与聚类中心vi使目标函数J(U,V)达到极小值,应用拉格朗日乘数法可得:

2 WFCM算法

2.1 WFCM算法权值的选取[3]

对于一个数据集,一般不能确切地给出每个样本的典型程度。但如果样本点周围有其它样本点时,则该点处的样本分布密度就大,那么该样本点对于分类的影响也就大。

根据上述分析,对于每个样本点,其点密度函数的表达式有如下定义:

式中:Dij表示两个样本点xi与xj之间的欧氏距离;如果样本点周围的样本点xi越多,则zi的值越大,反之zi的值越小;其中α是一个参数,α≥1。

对zi进行样本归一化可得加权矩阵wi:

2.2 WFCM算法

把上述的加权矩阵引入FCM算法,得到WFCM算法,该算法的目标函数:

为求得适当U={uij}与vi使J(U,V,W)达到最小值,应用拉格朗日乘数法可得:

由式(2)、(3)、(8)、(9)可以看到,WFCM算法和FCM算法的模糊划分矩阵uij相同,聚类中心vi不同,因此,WFCM算法主要在于对聚类中心位置进行调整,使其更接近实际的聚类中心,达到正确分类的目的。

根据以上各式,WFCM算法描述如下[4]:

步骤1:输入聚类数据集X={x1,x2,…,xn},给定聚类类别数c,设定一个任意小的迭代截止误差值ε>0,算法的最大迭代次数Tmax,权重指数m=2。

步骤2:根据式(4)、(5)、(6),计算加权矩阵wi。

步骤3:初始化模糊隶属矩阵U,使其满足约束条件。

步骤4:根据式(9)计算c个聚类中心vi(i=1,2,…,c)。

步骤5:根据式(7)计算目标函数。如果它小于某个确定的阈值,或它与上次目标函数值的改变量小于某个阈值,则算法停止。

步骤6:根据式(8)计算新的模糊划分矩阵U。返回步骤4。

上述算法也可以先初始化聚类中心,然后再执行迭代过程,FCM算法已被证明有良好的收敛性[5]。

3 基于加权模糊C均值聚类算法的变压器故障诊断

3.1 特征气体的选取及规格化

本文选用油中溶解气体H2、CH4、C2H6、C2H4和C2H2为故障特征气体[6,7,8]。由于电压等级和变压器容量不同,变压器油中各溶解气体组成含量差别很大,因此把样本做规格化处理使其每个值都限定在[0,1]之内。处理如下:

式中:xi是原始样本数据,即气体组分含量数值;x'ij是原始数据规格化后的值,并且有x'ij=1;i是样本序号;j是属性序号,用1～5依次表示上述5种特征气体。

3.2 故障诊断实例

变压器常见的故障类型有:低温过热T1(t<300℃)、中温过热T2(300℃

本文收集了上述各种类型故障样本1 80个,v1、v2、v3、v4、v5和v6分别表示T1、T2、T3、PD、D1和D2的聚类中心。WFCM算法参数的选取如下:m=2,迭代截止误差ε=10-4,最大迭代次数Tmax=200,α=8,聚类类别数c=6。运用WFCM算法得到6种故障类型中心如下:

FCM与WFCM特征气体聚类法都是以上述5种特征气体的组分含量为特征量,表1为这两种方法诊断结果对比,从表1中可以看出WFCM算法正确率明显高于FCM算法。

表2列举了变压器5组诊断实例,由表2可以看出,当改良三比值法和FCM算法诊断错误时,本文提出的WFCM算法对5组实例均得出了正确的结果。

4 结论

在变压器绝缘故障中,不同故障类型产生的主要特征气体及气体组分含量存在很大差异。以油中溶解气体组分含量为特征量构成的样本,典型程度不一样,应区别对待。本文提出一种加权模糊C均值聚类算法,该算法可实现故障聚类,求出故障聚类中心。通过实例分析,该算法明显提高了故障诊断的正确率。

摘要：模糊C均值聚类(FCM)算法具有将数据集合进行相等划分的趋势,每一个样本对数据集分类的影响相同。在变压器绝缘故障中,不同故障类型产生的主要特征气体及气体组分含量存在很大差异。因此,为了区别各类数据对故障划分的影响程度,可考虑对各类数据施加一个权。文中提出了一种加权模糊C均值聚类(WFCM)算法,该算法可实现故障聚类。与FCM算法相比,WFCM算法明显提高了故障划分的正确性和鲁棒性。

关键词：变压器,故障诊断,加权,模糊C均值聚类

参考文献

[1]高新波.模糊聚类分析及其应用[M].西安:西安电子科技大学出版社,2004.

[2]高新波,裴继红,谢维信.模糊C-均值聚类算法中加权指数m的研究[J].电子学报,2000,28(4):80-83.

[3]宋宇辰,张玉英,孟海东.一种基于加权欧氏距离聚类方法的研究[J].计算机工程与应用,2007,43(4):179-180.

[4]宋斌,于萍,廖冬梅,等.变压器故障诊断中溶解气体的模糊聚类分析[J].高电压技术,2001,27(3):69-71.

[5]J C BEZDEK.A Convergence Theorem for the Fuzzy ISODATA Clustering Algorithms[J].IEEE Trans on Pattern Anal Mach Intel,1980,2(1):1-8.

[6]姜晓飞,王鹏.基于油中溶解气体分析的变压器故障在线监测技术[J].陕西电力,2008,36(12):73-76.

[7]苑津莎,鲁伟,李忠.基于人工免疫算法的变压器故障诊断方法[J].电子设计工程,2009,17(1):46-48.