模糊均值算法范文-盘古文库

模糊均值算法范文

来源：火烈鸟

作者：开心麻花

2025-09-19

模糊均值算法范文（精选8篇）

模糊均值算法第1篇

伴随着模糊理论的形成、发展和深化,人们提出了许多模糊聚类算法。在实际中受到普遍欢迎的是基于目标函数的模糊聚类方法[1]也就是把聚类归结为一个带约束的非线性规划的问题,通过优化求解获得数据集的模糊划分和聚类该方法设计简单[2],解决范围广,还可以转化为优化问题而借助经典数学的非线性规划理论求解[3],并易于在计算机上实现。因此,随着计算机的应用和发展[4],基于目标函数的模糊聚类算法成为新的研究热点。

在基于目标函数的聚类算法中,模糊C均值类型算法理论最为完善、应用最为广泛,模糊C均值和LSA相结合的进行的文档聚[类方法,还可以使用模糊C均值算法对Web日志信息进行研究[5],所以本文就以这类的聚类算法为研究对象。本文首先回顾经典的模糊C均值的收敛性证明方法,在此基础上提出了针对聚类中心的迭代泛函序列,然后进行改进。

1模糊C均值的收敛性证明

简单地回顾模糊C均值收敛性的证明过程。Zangwill定理可以证明大多数的分类迭代收敛性。

Zangwill收敛性定理[6]。

设f为IRm空间的子集到到其自身的一个函数映射即:

$f : D_{f} \subset Ι R^{m} Ι R 。$

S:{x*∈Df:f(x*)<f(y)∀y∈B0(x*,r)}A:DfDf是一个迭代算法,有xk+1=A(xk),k=0,1,。

如果满足下面条件:

(1)对于{A,S},存在一个函数g是下降函数。

(2).A在Df/S上是连续的。

(3)迭代序列:

{A(xk):k=0,1,2,;x0∈Df}⊂K,被包含在一个紧集里。

则,由A产生的迭代序列{xk}收敛于一个点x*∈S,或者存在一个子序列{xkj}⊂{xk},有{xkj}x*∈S。

模糊C均值算法的迭代过程就是通过交替地迭代更新聚类中心和隶属度矩阵来最小化目标函数的过程,其目标函数Jm定义在(MfcIRcs)IR上[7]。

$J_{m} (U, v) = \sum_{k = 1}^{n} \sum_{i = 1}^{c} (u_{i k})^{m} ∥ x_{k} - v_{i} ∥^{2}$ ;1m<∞ (1)

$u_{i k}^{*} = \frac{1}{\sum_{j = 1}^{c} (\frac{d_{i k}^{*}}{d_{j k}^{*}})^{1 / (m - 1)}}$ ;1ic;1kn (2)

$v_{i}^{*} = \sum_{k = 1}^{n} (u_{i k}^{*})^{m} x_{k} / \sum_{k = 1}^{n} (u_{i k}^{*})^{m}$ ;1ic (3)

式(2)中dik=‖xk-vi‖2。

为了方便阐述把迭代函数表示为:

$(U_{n + 1}, v_{n + 1}) = Γ_{m} (U_{n}, v_{n}) (4)$

可以得到下面两个引理。

引理1:设φ:MfcIR,φ(U)=Jm(U,v),其中v∈IRcs是固定点。当且仅当通过式(2)计算出的隶属度矩阵U*=F(v)为φ的一个严格局部最小值。

引理2:设ψ:MfcIR,ψ(U)=Jm(U,v),其中U⊂Mfc是固定点。当且仅当通过式(3)计算出的聚类中心v*=G(U)为ψ的一个严格局部最小值。

于是,可以得到下面定理。

定理1:设:

S={(U*,v*):Jm(U*,v*)<Jm(U,v),∀(U,v)∈B0((U*,v*),r)},则Jm对于{Γm,S}是一个下降函数。

定理2:Γm在(MfcIRcs)上是连续的。

定理3:设[conv(X)]c为X凸壳上的c个域的笛卡尔积,设(U(0),G(U(0))为迭代Γm的起始点,其中U(0)∈Mfc,v(0)=G(U(0))。则(Γm)(k)(U(0),v(0))∈Mfc[conv(X)]c,其中k=1,2,,Mfc[conv(X)]c在MfcIRcs上是紧集。

由定理1、定理2和定理3,可得到如下结论。

定理4:设在IRs有 $X = {x_{1}, x_{2}, \dots, x_{n}} ‚ J_{m} (U, v) = \sum_{k = 1}^{n} \sum_{i = 1}^{c} (u_{i k})^{m} ∥ x_{k} - v_{i} ∥^{2}$ ;1<m<∞。

其中U满足: $u_{i k} \in [0, 1] ‚ \sum_{i = 1}^{c} u_{i k} = 1 ‚ \sum_{k = 1}^{n} u_{i k} > 0$ 其中1ic,1kn。Γm为定义在(MfcIRcs)(MfcIRcs)为Picard迭代算子,则对任意的(U(0),G(U(0))∈Mfc[conv(X)]c。

有{(Γm)(j)(U(0),v(0)}收敛于Jm的一个局部最小值点(U*,v*)[8],或者包含一个子序列{(Jm)(jk)(U(0),v(0))}(U*,v*)。

2关于聚类中心的泛函迭代序列

模糊C均值聚类算法虽然是交替优化迭代聚类中心和隶属度矩阵[9],但我们最关心的结果只是聚类中心,也就是说,如果使用不同的隶属度测量函数来替换(2),得到聚类中心同样能符合最终要求[10]。但是这样我们就需要构造新的目标函数,如在文献[11]提到的:

$\begin{array}{l} J^{'} (X, v, U) = \sum_{i = 1}^{c} \sum_{j = 1}^{n} u_{i j}^{m} ∥ x_{j} - v_{i} ∥^{2} + \\ \sum_{i = 1}^{c} η_{i} \sum_{j = 1}^{n} (1 - u_{i j})^{m} 。 \end{array}$

其中 $u_{i j} = \frac{1}{1 + (d_{s} (x, v) / η_{i})^{1 / (m - 1)}}$ 。

我们选择的隶属度测量方式是:

$u_{s} = \frac{1}{\sum_{i = 1}^{c} \frac{d_{s} (x, v)^{1 / (m - 1)} + ε}{d_{i} (x, v)^{1 / (m - 1)} + ε}} (5)$

对于任意的x,v都有us∈[0,1]。

由于隶属函数已被改写,要使用模糊C均值这种交替迭代方式,我们采用了这样的一种方式,即通过一个临时的聚类中心的隶属度,这时把隶属度当作常数来更新目标函数(如后述),这里我们只需对聚类中心迭代即可。

设在一个数据集X={x1,x2,,xn}上,迭代公式可以表示为:

$v_{i + 1} = Τ (v_{i}) (6)$

定理5:给出的关于聚类中心v的目标函数为:

$J (v) = \sum_{j = 1}^{n} \sum_{s = 1}^{c} u_{s}^{m} (x_{j}, v) d_{s} (x_{j}, v) (7)$

同时迭代T满足:

$\sum_{j = 1}^{n} u_{s}^{m} (x_{j}, v) \frac{\partial d_{s}}{\partial ξ} [x_{j}, Τ (v)] = 0 (8)$

式(8)中ξ为任意聚类中心向量。

如果v是T的一个固定点,则v也是J的极值点或鞍点。

证明:

$\begin{array}{l} \frac{\partial J}{\partial ξ} = \sum_{j = 1}^{n} \sum_{s = 1}^{c} m u_{s}^{m - 1} \frac{\partial u_{s}}{\partial ξ} + 0 = \\ \frac{m}{(m - 1)} (\sum_{j = 1}^{n} \sum_{s = 1}^{c} \sum_{i = 1}^{c} u_{s}^{m} u_{i} \frac{d_{s}}{d_{i}} \frac{\partial d_{i}}{\partial ξ} - \sum_{j = 1}^{n} \sum_{s = 1}^{c} u_{s}^{m} \frac{\partial d_{s}}{\partial ξ}) = \\ \frac{m}{(m - 1)} (\sum_{j = 1}^{n} \sum_{s = 1}^{c} \sum_{i = 1}^{c} u_{s} u_{i}^{m} \frac{\partial d_{i}}{\partial ξ} - \sum_{j = 1}^{n} \sum_{s = 1}^{c} u_{s}^{m} \frac{\partial d_{s}}{\partial ξ}) = \\ \frac{m}{(m - 1)} (\sum_{j = 1}^{n} \sum_{i = 1}^{c} u_{i}^{m} \frac{\partial d_{i}}{\partial ξ} \sum_{s = 1}^{c} u_{s} - \sum_{j = 1}^{n} \sum_{s = 1}^{c} u_{s}^{m} \frac{\partial d_{s}}{\partial ξ}) = \\ \frac{m}{(m - 1)} (\sum_{j = 1}^{n} \sum_{i = 1}^{c} u_{i}^{m} \frac{\partial d_{i}}{\partial ξ} - \sum_{j = 1}^{n} \sum_{s = 1}^{c} u_{s}^{m} \frac{\partial d_{s}}{\partial ξ}) = 0 。 \end{array}$

可以看到J的在v处的一阶导数为0,则它必定是J的一个极值点或鞍点。

定义1 设X是度量空间,T是X到X的映射,如果存在一个数α,0<α<1,使得对所有的x,y∈X,使得d(Tx,Ty)αd(x,y),则称T是压缩映射。

定理6:(压缩映射定理): 设X是完备的度量空间,T是X上的压缩映射,那么T有且只有一个不动点。

定理7:对于连续的函数J:XR和T:XX是一个连续的映射,J在T上单调,如果v*是J的一个鞍点,v*不会是T(v)序列上的固定点。

证明:设v*是J的一个鞍点,也是T(v)序列的固定点。由于T是连续的,我们可以找到一个ε>0和一个闭球集B(v*,ε),其中B中包含的向量x,满足x∈X,‖x-v*‖ε。这样一来T在这个球集上就满足了压缩映射定理,对于任意的v∈B(v*,ε),在T上都会收敛于v*。

然而,由于v*是J的一个鞍点,所以我们可以找到至少一个点v′∈B(v*,ε),使得J(v′)<J(v*)。又因为J是连续的,我们可以找到一个η>0,使得所有的 $\bar{v} \in B (v^{*}, η)$ ,满足 $J (\bar{v}) > J (v^{'})$ 。

由于通过T对聚类中心迭代使得目标函数J的值是逐渐减小的,所以T(v0)的值永远不会得到B(v*,η)里的值。也就是在使用v′进行初始化,进行迭代是不会收敛到v*的。这就出现了矛盾,假设不成立。

因此,如果v*是J的一个鞍点,v*则不会是T(v)序列上的固定点。

通过这个理论可知,如果通过迭代T得到一个固定点v*,则它就是目标函数Jm的一个极值,并且可以确定不是Jm的一个鞍点。这样以来我们的模糊C均值的聚类问题就由确定最佳聚类中心和隶属度矩阵的问题转换成了确定泛函迭代序列T(vi)的固定点的问题。

3加速泛函迭代序列T(vi)的收敛

本节我们主要研究对泛函迭代序列T(vi)收敛问题。这里采用的是最速下降法,来对关于聚类中心v的目标函数J(v)进行加速最小化。于是给出公式(9)。

$v_{k + 1} = v_{k} - α_{k} \frac{\nabla J (v_{i})}{∥ \nabla J (v_{i}) ∥} (9)$

通过化简可得迭代式(10)。

$v_{k + 1} = v_{k} - α_{k} (\nabla J (v_{i})) (10)$

式(10)中可求得:

$(\nabla J (v_{k})) = \sum_{j = 1}^{n} \sum_{i = 1}^{c} u_{i}^{m} (x_{j}, v_{k}) (\nabla d_{i}) (11)$

经过化简就有:

$v_{k + 1} = v_{k} + 2 α_{k} \sum_{j = 1}^{n} u_{s j}^{m} (x_{j} - v_{k}) (12)$

这样一来迭代过程就为:

(1) 选取初始点v0以及判别收敛的正数ε;

(2) 令k=0;

(3) 若 $∥ 2 \sum_{j = 1}^{n} u_{s j}^{m} (x_{j} - v_{k}) ∥$ 是否小于ε,则迭代停止,xk即为所求的优化点,否则进行下一步。

(4) 确定步长αk的值,使得满足:

$J (v_{k} + 2 α_{k} \sum_{j = 1}^{n} u_{s j}^{m} (x_{j} - v_{k})) = \min_{α \geq 0} J (v_{k} + 2 α \sum_{j = 1}^{n} u_{s j}^{m} (x_{j} -$

vk))。

(5)令 $v_{k + 1} = v_{k} + 2 α_{k} \sum_{j = 1}^{n} u_{s j}^{m} (x_{j} - v_{k})$ ;k=k+1,返回步骤(3)。

可以看出当步长 $α_{k} = \frac{1}{2 \sum_{j = 1}^{n} u_{s j}^{m}}$ 时,迭代式就变为模糊C均值的迭代式:

$v_{i + 1} = v_{i} + 2 α_{k} (\sum_{j = 1}^{n} u_{s j}^{m} x_{j}) - v_{i} = \frac{\sum_{j = 1}^{n} u_{s j}^{m} x_{j}}{\sum_{j = 1}^{n} u_{s j}^{m}}$ 。

由此可认为FCM迭代算法是这种迭代里的一种特例,虽然,最速下降法对一般函数而言,在远离极值点时函数下降的很快,这对我们找到极值点非常有帮助,但是,如果初始化的聚类中心离极值点很近的话,收敛过程可能会变的很慢的,这个问题将在下一节里结合相关实例来分析。

4实验结果与分析

这里我们选用的实验数据为IRIS数据,它包含了150个样本数据,分为3类:setosa,versicolor,virginica,每类有50个数据,数据有4个属性:sepal length(萼片长度),sepal width(萼片宽度),petal length(花瓣长度),petal width(花瓣宽度)。为了尽快得到聚类结果,这里我选取的初始化聚类中心,不是随机选取的,通过计算数据的平均属性而得到的,这样以来这个初始中心为:

vset=(5.006,3.418,1.464,0.244);

vver=(5.936,2.770,4.260,1.326);

vvir=(6.588,2.974,5.552,2.026)。

这里我们采用的是VC++6.0进行设计的实验程序,分别对传统FCM和改进的FCM的进行的测试。传统的FCM也就是通过对聚类中心和隶属度矩阵交替优化而来得到最终收敛结果;改进的FCM,就是基于关于聚类中心的泛函迭代数列实现的,并使用了最速下降算法来加速其收敛过程,使用的迭代式为式(12),其中步长简化为K/J(vi),这里K为常数,这里经过测试,K=4,结果比较理想。实验里收敛度是本次迭代得到的聚类中心和上次聚类中心的欧几里得距离。

具体实验结果如下:

通过表1可以发现:(1)FCM使用了经过了26次迭代后,聚类中心停止收敛,开始左右摆动,而在改进的FCM中使用了21次迭代达到这一结果;(2)在改进的FCM的收敛速度比FCM中的要快一些。通过观察我们可以发现,改进的FCM前4次迭代的收敛度要稍高于传统FCM的,这一点也证实最速下将法的特点,在远离极值点时,下降速度很快,但在接近极值点时速度会慢下来,整体上还是稍快于传统的算法,也说明了加速算法的是有效的。

5结束语

本文是在原有的以交替迭代为优化方式的传统模糊C均值算法的基础上,提出以优化聚类中心的方式来进行聚类方法,通过结合相关理论证明了这种方法的收敛性,然后结合最优化理论里的最速下降法,来尝试加快聚类中心的泛函迭代序列的收敛速度。实验也表明了,对聚类中心的迭代序列的收敛过程进行加速,是有助于加快找到目标函数的极值点。

摘要：在模糊C均值算法的基础上,通过对原有算法进行改进,以达到加快聚类速度的目的。提出了一种使用最速下降法来优化模糊C均值算法的方法。从传统的模糊C均值算法中推导出关于聚类中心的泛函迭代序列,并证明了该序列的收敛性,以及该序列收敛到的不动点是目标函数达到的极值点。而后,使用最速下降法加快该序列收敛速度。最终通过实验结果来验证了理论的可行性。在其迭代过程中,对于越偏离理论聚类中心的点,下降趋势比传统模糊C聚类算法就越明显。

关键词：聚类,模糊C均值,泛函迭代序列,最速下降法

参考文献

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

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

[3]陈松生,王蔚.改进的快速模糊C均值聚类算法.计算机工程与应用,2007;43(10):167—169

[4]王小华,楼佳.基于迭代分类的聚类结果改进的方法.计算机工程,2010;36(13):27—29

[5]闫仁武,商好值.一种基于遗传算法的模糊C均值算法.科学技术与工程,2010;10—(28):7037—7039

[6] Bezdek J C.A convergence theorem for the fuzzy ISODATA clusteringalgorithm.IE-EE Trans.PAMI,1980;1(2):1—8

[7] Sabin M J.Convergence and consistency of fuzzy c-means/ISODATAalgorithms.IEEE Trans.PAMI,1987;9(5):661—668

[8] Selim S A,Kamel M S.On the mathematical and numerical propertiesof the fuzzy c-me-an salgorithm.FSS,1992,49(2):181—191

[9]朱长江,张缨.模糊C-均值聚类算法的改进研究.河南大学学报(自然科学版),2012;42(1):92—95

[10]李鹏飞.一种改进的模糊C均值算法在入侵检测中的应用.计算机应用与软件,2012;29(2):289—300

模糊均值算法第2篇

基于模糊C-均值的原型模式选择及其在核爆地震识别中的应用

协同模式识别是一种全新的有着抗噪声、抗缺损等诸多优良特性的模式识别方法,但将其用于核爆地震和天然地震的分类时,采用现有的原型模式选择方法识别效果并不理想.本文提出了一种基于模糊C-均值的`原型模式选择方法,该方法首先对每一类训练样本采用模糊C-均值聚类的方法聚为c类,然后选取这c类的c个重心或c个聚类中心作为该类的原型模式进行核爆地震的协同模式识别.实验结果表明,同现有的原型模式选择方法相比,该方法使识别率有了较大提高.

作者：韩绍卿李夕海宋仔标刘代志 HAN Shao-qing Li Xi-hai SONG Zi-biao LIU Dai-zhi 作者单位：第二炮兵工程学院,西安,710025 刊名：核电子学与探测技术 ISTIC PKU英文刊名：NUCLEAR ELECTRONICS & DETECTION TECHNOLOGY 年，卷(期)： 27(5) 分类号：O235 关键词：协同模式识别原型模式模糊C-均值核爆天然地震

模糊均值算法第3篇

计算加速设备价格和功耗比日益下降,包含加速设备和一般计算核心的异构计算机系统已经在企业计算日益普及。但是,使用底层的加速API去编写GPGPU程序却很困难,而且对于每个厂商的各种品牌加速设备,可能都需要重新设计程序并调整代码,对于大型项目来说,很容易出现错误或出现高度依赖特定设备的代码。

目前已经出现了提供基于制导语句的API使编译器负责一些底层的编程工作。当然,要使算法能加速设备运行还是要依赖于程序员,但从这个角度来看,这种努力并没有简化加速程序的开发工作,提高了开发效率和简化了代码管理。2011年12月,OPENMP的成员包括CPAS、CRAY、NVIDIA和PGI等公司发布了OPENACC指令协议,OPENACC可以加速C/C++和FORTRAN语言中的并行部分。在这个工作中,使用高斯模糊的代码来展示基于OPENACC指令获得的效能,工作内容包含代码性能分析和工作效率的提升与评价。

2 相关工作

GPU计算触发了新编程模式的进步,目前常用GPU计算模型为CUDA和OPENCL,二者都可以通过程序员在底层将代码移植到GPU的核函数中来加速程序。但目前CUDA只能应用NVIDIA的GPU设备,而OPENCL则作为数家硬件厂商的可移植通用计算标准。但由于重复的移植和易错的编程风格,使用底层的API经常会产生一个效率低下的开发过程。目前已经有几个基于指令制导计算的编译器被开发出来,作为和OPENMP加速指令的补充,OPENACC就是一个基于指令加速被提出来的编程模型。

The Portland Group提供了PGI加速模型,这个模型为C和FORTAN语言,可以通过编译器使基于指令的计算任务加载到NVIDIA GPU上,同时带有一系列其它的功能,作为OPENACC规范的基础,CAPS公司已经建立HMPP环境提供指令来声明代码片段,即适合硬件加速的函数,intel也依赖于指令来把代码转换成MIC在加速器上运行,hiCUDA定义了一个带有核心指令的高层CU-DA抽象,数据传输条件和函数调用,但是在支持CUDA特性的同时,hiCUDA把更多的责任和任务交给了程序员,OPENMPC通过把OPENMP区域的代码翻译成CU-DA,并通过一些额外的指令来控制CUDA相关的参数,编译器也可能为程序发现一些合适的调优配置,但是它被严格限制应用于NVIDIA系列的GPU上。目前,Barcelo na超级计算中心已经开发了StarSs编程模型,该模型针对几个加速器架构提供扩展给OPENMP,它着眼于OPENMP任务在运行期分派给不同的架构设备,但依赖于程序员来分派数据的输入和输出。

3 OPENACC总述

用于C/C++和Fortran的OPENACC API和指令负责把底层的GPU任务交给编译的同时,又提供了跨系统、跨主机CPU和加速设备支持。当然,到目前为止,几个公司的OPENACC实现仅支持NVIDIA GPU设备,在这里需对OPENACC指令协议提供一个简要的概述。

OPENACC指令协议假设了一个主机执行模型,在这个模型里,主程序代码运行在主机CPU里,而计算紧密区域则分派给附加的GPU加速设备。内存模型分别为主机内存和设备内存,但这两种内存并不会自动同步,GPU设备实现的是一个弱内存模型,防止不同计算单元的相关连,但是通过显式的同步调用则可以让同一计算单元实现关连,执行和数据管理是由程序员使用指令来完成。

最重要的指令是parallel和kernel关键字,描述了同步或异步的代码区域,这两个关键字映射到一个OPENCL或CUDA的核函数,这个核函数可以在N维的工作单元内执行。为了提高性能,也可以规定gang、worker、vector_length等关键字,关键字gang和vector可以对应于OPENCL里面的工作组和工作项,而关键字worker定义了工作项的组合,或是CUDA架构的warp概念。在parallel区域里,loop关键字表明使用内核函数来对循环加速,程序员可以加入额外的条件在parallel、kernels或loop关键字里来优化或纠正默认的数据管理,例如,可以使用显式的data关键字来指示在主机和加速硬件之间的数据传输,如copyin或copy,也可以使用create关键字在硬件上创建私有数据,或通过present关键字来告诉编译器数据已经在设备上,而且用户也可以通过update关键字来同步主机和设备之间的数据。CPU的内存通常支持低延迟的本地存储,编译器可以通过它来优化程序,为了使用CPU的快速内存,开发者可以应用cache指令来存储数据。

除了指令之外,OPENACCR指令集还提供了运行时库调用和环境变量,例如,库调用可以获取关于加速设备的信息,进行初始化或收集在设备上的数据。

4 OPENACC实现图像加速

图像模糊是在图像处理中最经常使用到的操作,也是在加速设备中最常应用的计算应用。有两种比较知名的线性和非线性模糊方法,如2d高斯卷积滤波和中值滤波、均值滤波等。它们通常是一些更复杂的图像操作的组成部分,如噪声滤波和图像分割。传统的卷积模糊计算量巨大,程序效率比较低,基于滑动窗口的均值滤波是一种快速模糊方法,其结果近似于卷积模糊的结果,具有性能好、计算简单、方法简单等特点。因此,可选用它来验证OPENACC加速。

4.1基于OPENACC加速算法

相应的代码用C语言完成,算法骨架如下:

5 数据结果分析

实验平台操作系统为redhat fedora 64位Linux系统,CPU为I7-2600,主频3.4G,内存为16G,显卡为NIVI-DA TELSA C2070,所采用的编译软件为HMPP 3.2,支持OPENACC的部分指令。图像像素与CPU计算时间关系如图1所示。

从图1可以看出,随着图像像素的增大,CPU所花费的计算时间呈指数性增长,而在代码中添加OPENACC指令后,计算机所花费的计算时间则呈线性增长。与CU-DA相比,OPENACC的时间虽然要高出6倍左右,但是因为CUDA的代码是经过精心优化的,相比较而言,OPENACC只是多加入十几行代码就能取得10倍左右的加速比。而且随着OPENACC编译器的优化和硬件的发展,与CUDA等底层技术实现的差距将会越来越小。

图2.a是10241024的原图,图2.b、图2.c是经过半径为5的均值滤波模糊处理后的图像,图2.b为CPU处理,图2.c为OPENACC指令处理。由上图可以看出图2.b、图2.c两图像模糊的结果基本相同。

6 结语

使用不多的OPENACC指令就可在原有代码的基础上,得加速比良好的均值滤波模糊算法,且不用改变原来代码,大大增强了代码的可维护性和可读性。对于当前的均值滤波模糊实现来说,使用OPENACC指令优化还有很大的空间,目前已有大量的串行代码,采用OPENACC指令可以将其运行在GPU设备上,实现并行加速。

参考文献

[1] R BORDAWEKAR,U BONDHUGULA,R RAO.Can CPUs Match GPUs on performance with productivity: experiences with optimizing a FLOP-intensive application on CPUs and GPU[C].2010.

[2] C BRECHER,C GORGELS,A HARDJOSUWITO.Simulation based ToolWear Analysis in Bevel Gear Cutting[C].2010.

[3]M B¨UCKER,R BEUCKER,A RUPP.Parallel Minimum p-NormSolution of the Neuromagnetic Inverse Problem for Realistic Sig-nals Using Exact Hessian-Vector Products[J].SIAM Journal onScientific Computing,2008(6).

[4] R DOLBEAU,S BIHAN,F BODIN.Hmpp:A Hybrid Multi-core Parallel Programming Evironment[C].2007.

[5]CAPS ENTERPRISE,CRAY INC.NVIDIA,AND THE PORT-LAND GROUP.The OpenACC Application Programming Inter-face[C].2011.

模糊均值算法第4篇

关键词：协作学习,分组系统,学习者特征,FCM

协作组的实现需要建立在学习者个性特征的基础上,在计算机的协助下完成分组,保证下一步协作任务的开展。分组的过程就是使得学习者由独立的个人状态转变为有机结合的协作组状态[1]。如何进行最优化的分组,国内外为此进行了大量的研究,有的研究者从协作学习理论出发,提出了分组的基本原则,但没有具体分组方法的阐述[2]。而有的研究者的分组方式多是硬性分组,没有充分考虑学习者特征的复杂性和模糊性。文中根据学习者的个性特征的模糊性,利用模糊C均值算法进行分组,替代辅导教师根据经验分组以及硬性的随机分组或学习者自主分组,提高分组的执行效率、增强分组的可靠性。

1 协作组的分组理论

1.1 分组依据

(1) 学习风格理论。

学习风格是指学习者个体在其心理、生理特征基础上形成的,接受和加工信息过程的持久性偏好。大量的研究表明学习风格对学习者的知识建构至关重要,并且不同学习风格的学习者在一个小组内可以互相影响。文中利用现有的学习风格测试量表度量学习者的特征属性[3],采取有意失配的策略进行分组。

(2) 学习者特征理论。

学习者特征是指对学习者学习有关学科内容产生影响的心理和社会的特点,一般包括智力因素和非智力因素。依据特征因素对分组的影响程度和测量的可操作性,文中采用知识基础和认知能力作为学习者基本特征。

(3) 系统论。

系统是指由若干要素组成的具有一定新功能的有机整体。系统最为基本的特征是整体性,系统中要素之间是由于相互作用联系起来的,在这样复杂的联系之中,每一个部分都相互影响、相互制约。系统稳定性的不断增强是通过信息反馈机制的调控作用实现的,文中将协作学习的准备、过程和评价作为有机的整体,分组是整个协作学习过程的一个要素,它作用于其它要素,同理其它要素也反作用于它。所以,将协作学习的评价结果作为反馈信息作用于分组系统,能有效提高分组的准确程度。

1.2 分组原则

协作学习的基本分组原则是同质分组和异质分组。同质分组是指把个别特征、初始能力特征和学习风格上都比较接近的协作成员组成一个小组的方式,形成组间异质,组内同质的协作氛围。异质分组是指小组内各成员间形成学习风格、知识基础等方面的差异,而每个协作组之间在一定程度上相似,这样,组内成员可以彼此取长补短,小组之间可以进行平等竞争,对协作学习产生激励作用。在当前国内外的研究中,异质分组方式的积极影响效果在调查试验中已得到证实。文中将以异质分组策略为核心,提供一系列的个体差异测试,并以此为出发点实现分组,力求达到组间最大化同质、组内最大化异质的分组结果。

协作组规模是指协作组内成员的数目。协作组的人数,国外研究一般建议4~6人,计算机支持的协作学习过程中的组规模,大多研究者认为在3~5人之间。一般分组系统需预先确定小组规模,可以根据协作内容和方式的不同确定合宜的人数。

2 协作组分组系统模型

文中所提出的分组系统模型是在北京师范大学黄荣怀教授设计的“WebCL系统模型”基础上,将分组部分抽象出来,并增加一条反馈通道,使分组部分成为一个闭环系统[4]。因而,分组系统可以作为一个相对独立的子系统使用,也可以作为整个协作学习系统的一个功能模块,图1为分组系统模型。

文中将分组功能从协作学习过程子系统中分离出来,从原系统8个信息库中选取3个对分组起关键作用的信息库作为分组的数据依据。通过评价系统的信息反馈及时了解学习者特征的变化,调整分组系统的参数为下一次协作学习准备条件。

3 分组算法

学习者的分组数据是学习风格和学习者特征,可以利用相应的测试量表获得。但是,学习风格和学习者特征都具有模糊性,量表获取的数据只能对其进行量的描述,不能完全反映真实的情况。所以,文中采用模糊-C均值(FCM)算法[5],对待分组对象进行模糊聚类,然后根据分组原则按比例抽取学习者组成协作组,算法步骤描述如下:

初始化参数c与m的值,c是分组数,m是加权指数。

步骤1:用值 $\frac{1}{c}$ 初始化划分矩阵U。

步骤2:用公式 $c_{i} = \frac{\sum_{j = 1}^{n} u_{i j}^{m} x_{j}}{\sum_{j = 1}^{n} u_{i j}^{m}}$ ,计算c个聚类中心ci,i=1,…,c。

步骤3:根据公式 $J (U, c_{1}, \dots, c_{c}) = \sum_{j = 1}^{n} J_{i} = \sum_{i = 1}^{c} \sum_{i = 1}^{c} u_{i j}^{m} d_{i j}^{2}$ ,计算目标函数。如果它小于某个确定的阈值,或它相对上次目标函数值的改变量小于某个阈值,则算法停止。

步骤4:用公式 $u_{i j} = \frac{1}{\sum_{k = 1}^{c} (\frac{d_{i j}}{d_{k j}})^{2 / (m - 1)}}$ 计算新的U矩阵,返回步骤2。

步骤5:保存聚类结果,按比例抽调成员,组成协作组。

算法流程,如图2所示。

4 实验

本次实验的对象选取某高校信息科学与工程学院07年级3班和9班,其中07-9班为实验班,07-3班为对比班。两班人数均为30人,入学成绩、男女比例、年龄等基本情况较接近。实验班采用文中提供的分组系统进行分组,对比班采用学习者自主分组,通过考察实验班和对比班在对同一协作内容进行协作学习后的协作绩效,衡量两班的学习效果。协作绩效可以反映协作学习的成效,协作绩效由协作组内学习者学习成绩的平均值和协作度两个值来表征,如果协作组平均成绩越高,协作度越大,则协作组的协作绩效越好[6,7],实验结果的比较,如表1所示。

由表1可以看出,实验班的协作绩效远高于对比班的协作绩效,证明了文中所提出的基于模糊C均值算法的分组方法,可以明显的提高计算机支持的协作学习的学习效果。

5 结束语

文中在“WebCL系统模型”基础上,将分组功能从协作学习过程子系统中分离出来,考虑到学习风格和学习者特征的模糊性,提出了基于模糊C均值算法的分组方法。该方法根据学习者的相似性进行模糊划分,避免用确定的界限进行硬性划分,更能够反映出学习者真实特征,使分组更符合实际情况,实验证明能够明显提高协作学习效果。

参考文献

[1]赵建华.计算机支持的协作学习[M].上海:上海教育出版社,2006.

[2]程向荣.计算机支持的协作学习的伙伴模型[J].计算机应用,2007(7):62-65.

[3]Barbara A.Soloman.Index of Learning Styles Question-naire[EB/OL].http://www.engr.ncsu.edu/learn-ingstyles/ilsweb.html,(2006-12-12)[2009-01-09].

[4]汪长娥,赵曙光,付新林.一种模糊核聚类算法的改进[J].电子科技,2008,21(10):52-54,58.

[5]黄荣怀.基于Web的协作学习系统模型[J].中国远程教育,2001(5):42-47.

[6]石洪波.一种有效的FCM算法的实现方式[J].铁道学报,2003(2):64-68.

模糊均值算法第5篇

自从Zadeh教授1965年提出模糊集概念[1]以来,模糊集合无论在理论还是应用方面都取得了巨大的成就。Atanassov扩展了Zadeh的模糊集,给出了直觉模糊集[2]的概念和性质。直觉模糊集引入非隶属度和犹豫度,被证明更适合处理一些模糊的和不确定的问题。在过去的数十年中,很多人致力于直觉模糊集的原理和性质的研究,并且应用到各种领域,如决策分析[3,4,5]、医疗诊断、模式识别、机器学习等。由于客观事物的复杂性和不确定性,直觉模糊集中的隶属度有时很难用一个精确实数值表达,而用区间数表示会比较合适。Atanassov和Gargov对直觉模糊集进行推广,进一步细化描述,给出了区间直觉模糊集的定义[6]。

相对于直觉和区间直觉模糊集在决策分析中的大量应用,直觉模糊集和区间直觉模糊集在聚类中的应用近年来才被关注。作为数值分析的一种重要工具,模糊聚类被广泛应用到各种领域,如模式识别、信息检索、数据挖掘等。张洪美等人[7]定义了一种直觉模糊集合的关联度,并给出了基于等价关系的聚类算法,后来Xu[8]针对此算法给出了更有效的关联度,并将其推广到区间直觉模糊集合上。目前基于等价矩阵的聚类算法只能够处理数据量比较小的数据,而FCM算法比较适合处理大量数据,但它是针对普通的模糊集合,无法处理对象为直觉模糊或区间直觉模糊的集合。

针对上述问题,吴成茂[9]推导出直觉模糊数的模糊C均值聚类算法,并给出直觉模糊聚类中心的初始化方法和有效性函数。申晓勇[10]通过引入密度函数来初始化直觉模糊聚类中心,并和随机样本法的聚类结果比较,说明性能上有了较大的提高。Tamalika Chaira[11]给出直觉模糊聚类算法并应用到了医学图像处理中。

鉴于此,本文将FCM算法推广到区间直觉模糊集上,并将一种有效性函数区间直觉模糊化,用来确定最佳聚类类别数,最后通过实例进行验证。

1 区间直觉模糊集及欧氏距离

Atanassov对区间直觉模糊集的定义[2]如下:

定义1设X为一个非空集合,则称:

为区间直觉模糊集,其中:

对应的分别表示隶属度和非隶属度。的下限和上限,的下限和上限且还必须满足此外表示IVIFS的犹豫度。其中:

特别地,当,那么就退化为直觉模糊集。对于IVIFS中任意两个集合,满足以下条件:

性质1当且仅当:

性质2当且仅当

对欧氏距离,Xu[12]给出了基于权重的欧氏距离公式,定义如下:

定义2对于为区间直觉模糊集,wl为对应的属性权重,其中则欧氏距离公式为:

满足以下四个条件:

2 区间直觉模糊集的FCM算法

设为一组有效观测样本集,每个样本均有s个属性且:

为区间直觉模糊集,其中为c个聚类中心,c表示聚类类别数。每个聚类中心均有s个属性,则有为区间直觉模糊集,表示为:

划分矩阵表示第j个样本隶属于第i个聚类中心的隶属度,给出下列IVIFS聚类的数学模型:

其中m为加权指数。

聚类准则为求Jm的极小值min}。构造Lagrange函数:

并对求导,可得的表达式为:

对聚类中心珘Pi各属性对应的隶属度和非隶属度下限及上限求导,得到下列方程组:

求解以上方程组,得:

由式(15)知,珘μU珘Pi(xl)+珓vUP珘i(xl)1且0珘μL珘Pi(xl),珘μU珘Pi(xl),珓vL珘Pi(xl),珓vU珘Pi(xl)1,故珘Pi满足定义1中关于区间直觉模糊集的描述。根据式(12)和(15),给出IVIFS聚类算法的描述:

Step1初始化聚类目标数c(2cn)、阈值ε、l=1为起始迭代次数、模糊加权指数m、最大迭代次数T、属性权重矩阵w,随机产生并归一化模糊划分矩阵珟U(1),其上标表示迭代次数;

Step2根据式(15)计算聚类中心珘Pi(l+1);

Step3根据隶属度式(12)计算样本的划分矩阵珟U(l+1);

Step4如果‖珟U(l+1)-珟U(l)‖ε或者l>T则转Step5,否则l=l+1,跳转到Step2;

Step5算法结束,输出聚类中心和划分矩阵。

3 区间直觉模糊集聚类有效性函数

聚类是一种无监督的学习算法,对事先给定的数据无任何先验知识。如果确定数据集具有结构,用聚类算法确定结构时,聚类类别数的选取对结果有直接影响,类别数的选取属于聚类有效性的范畴。对于FCM算法,目前应用较广泛的聚类有效性函数有Dunn的划分系数[13]、Bezdek的划分熵[14]、Xie-Beni指标[15]等。通过研究发现Xie-Beni指标在类别数比较大并逐渐接近样本点数目时,指标值失去判断性和鲁棒性。本文通过引入惩罚项对Xie-Beni指标改进,同时把Xie-Beni指标扩展到区间直觉模糊集下,计算得到的指标最小值对应最佳聚类类别数。聚类有效性指标函数计算公式如下:

其中作为惩罚因子,物理意义为数据集中任意数据对之间的平均距离,抑制当聚类数目较大并逐渐增加到n时呈现的单调递减趋势,提高指标的鉴别力和鲁棒性。指标函数计算公式的分子表示类内紧凑度,分母表示类间分离度,可知指标值越小越好。

根据上述有效性指标,给出可以确定最佳聚类类别数的区间直觉聚类流程:首先由专家分析聚类数的大致范围[cmin,cmax];然后对于不同的c值,使用上述的聚类算法求解,并计算不同c值对应的有效性指标Vnew_xie;最后输出最小指标值对应的聚类中心和划分矩阵,算法结束。

4 实验结果与分析

实验采用的IRIS数据集[16]是国际公认的比较无监督聚类方法好坏的典型数据集之一。它包含3类,每类包含50个样本点,每个样本点有4个属性,该数据集的特点是第一类和其他类离得比较远,第二类和第三类距离较近,且有部分重叠。

IRIS为实数集,用矩阵R=(Rij)ns表示各样本的属性值,用珘F=(珘Fij)ns表示属性值区间直觉模糊化后的矩阵。基于文献[17]中直觉模糊化的思想,本文给出如下区间直觉模糊化的方法:

首先计算样本点隶属度下限珘μL珘Fij和上限珘μU珘Fij:

其中max(Rkj)=max{R1j,R2j,,Rkj,},k=1,2,,n。

然后计算αij和βij:

取非隶属度下限ν珓L珘Fij=min(αij,βij),非隶属度上限ν珓U珘Fij=max(αij,βij)。

样本区间直觉模糊化后,取聚类类别数cmin=2,cmax,=10,阈值ε=10-5,权重w=(0.25,0.25,0.25,0.25)T,加权指数m分别取1.5、2和2.5。每种情况下算法均运行10次,得到表1中的聚类有效性指标值。

从表1可看出,c=3且m分别取1.5、2和2.5时得到的指标值都是最小的,所以c=3为最佳聚类类别数,符合真实情况,说明本算法能确定最佳聚类类别数。

进一步地,令c=3,m在[1.5,2.5]变化,分别用MAT-LAB中的FCM算法和本文算法聚类,得到如表2所示的结果。

从表2可以看出,聚类的准确率提高了6.67%。

5 结论

提出基于区间直觉模糊集的c均值聚类迭代算法和一种聚类有效性指标计算方法,将有效性指标和聚类方法结合起来,给出可以确定最佳聚类数的聚类流程。实验验证算法不仅可得到最佳聚类数,而且能提高聚类的准确率。本文为处理大数据量的区间直觉模糊聚类问题提供了一种解决方法。

摘要：针对区间直觉模糊集(IVIFS)的聚类问题,提出了基于IVIFS的C均值聚类算法。算法首先应用IVIFS的欧氏距离,构造了聚类的目标函数;然后根据拉格朗日乘数法推导出聚类的迭代公式,得到IVIFS聚类算法;此外,还提出一种IVIFS聚类的有效性函数,并将此函数和聚类结合,给出可以确定最佳聚类类别数的聚类流程;最后通过实验验证了该算法不仅得到了最佳聚类类别数,同时还提高了聚类的准确率。

模糊均值算法第6篇

图像分割是把图像分成若干个具有特定性质的区域并提取感兴趣目标的技术和过程。在医学图像处理领域, 把感兴趣区域或组织器官从错综复杂的图像中准确分割出来, 是进行后续处理及分析包括目标检测 (如特定正常组织器官或者病灶的定位) 、测量分析、分类识别 (如对识别出的病灶进行良恶分类) 、辅助诊断 (如对识别出的病灶进行分析确定分级) 、可视化、手术规划和手术导航等的基础。但图像分割是图像处理过程中最具挑战性的任务之一, 特别是对于医学图像而言, 由于受成像原理和人体安全的局限, 获得的信号强度一般较弱, 加上人体组织结构复杂、个体差异及生命活动等因素, 因此, 与普通图像比较, 医学图像不可避免地具有模糊、不均匀性等特点。这些特性使得其分割工作相比成像条件可以高度控制的工业图像要困难很多。

医学成像模式中, 磁共振成像 (MRI) 具有软组织分辨率高、无电离辐射损伤、可自由选取剖面、多序列成像等方面的优势, 已在脑部及软组织等成像中得到广泛应用。MRI图像分割的最主要困难在于随机噪声、偏差场 (bias field) 和部分容积 (partial volume, PV) 效应的影响[1]。随机噪声源自磁共振过程中的热噪声和电磁噪声, 在图像中通常体现为Rician噪声[2];偏差场则由设备中磁场不均匀和信号读取线圈敏感性不均匀引起, 它使图像呈现一种全局的、低频的、连续的阴影, 又被称为灰度非均匀性 (intensity inhomogeneity) 或阴影效果 (shading effect) ;而PV效应是由于图像像素中存在不同的组织时, 像素灰度值为这些物质的平均信号值, 组织的一些解剖结构会因此在图像中失去。

对于脑部MRI图像, 由于噪声、偏差场、不同脑组织间较弱的灰度差异以及脑组织自身结构的复杂性等因素, 传统的区域分割算法和边缘检测算法难以得到满意的结果。近年来, 模糊C-均值 (fuzzy C-means, FCM) 算法和基于变形模型的方法在脑MRI图像分割中得到广泛应用。特别是由于FCM具有以下优势: (1) 适合于医学图像中混合组织的模糊性; (2) 适用于目标种类已知的组织分割; (3) 属于无监督分类, 不需要人工干预, 亦无须提供初始轮廓, 因此在医学MRI影像特别是脑MRI分割中取得了很好的效果。

1 传统的FCM聚类算法

FCM算法是由Dunn[3]提出并由Bezdek[4]改进的一种基于最小化目标函数的聚类方法, 其基本思想是通过迭代寻找聚类中心和隶属度函数使得目标函数达到最小。FCM的目标函数如下:

FCM通过交替更新隶属度函数和聚类中心来最小化目标函数。迭代结束的条件是2次迭代的目标函数之差小于某一初始阈值。

2 基于FCM的脑MRI图像分割及算法改进

2.1 FCM的空间连续性与灰度非均匀性校正

由于MRI图像中存在大量噪声, 如果仅使用传统的FCM, 分割出来的区域往往是不连续的。这是由于传统的FCM在分割时假设图像中各个像素相互独立, 没有考虑到它们之间的相关性。要解决这类问题, 通常采用在目标函数中引入空间约束的方法, 使分割结果具有空间连续性。文献[6]在FCM的目标函数中加入空间正则化项, 使每个像素的隶属度函数受其邻域像素的影响, 以保持组织的空间连续性, 对脑部MRI图像的分割实验表明其效果明显优于传统的FCM。文献[7]对文献[6]中采用的正则化项进一步简化, 减少了计算量。文献[8]则将邻域像素的隶属度作为权重, 加权到中心像素的隶属度上, 其本质依然是通过邻域像素影响中心像素。文献[9]提出了一种相异指数 (dissimilarity index) , 在用邻域对中心像素施加影响时, 区分中心像素属于组织内部还是边界, 从而在引入组织空间连续性的同时更好地保持了组织边缘。文献[10]指出上述文献只采用图像局部信息作为空间约束, 在噪声较强的条件下, 分割效果会不佳。它提出了一种结合图像局部和非局部信息 (local and non-local information) 的模糊聚类方法, 该方法在对脑部MRI图像分割中能更好抑制噪声并取得了更为准确的分割效果。

相较于噪声的去除, 灰度非均匀性校正更为复杂。灰度的非均匀性与扫描设备和扫描对象相关, 这种非均匀性会由于不同的设备、不同的对象、不同的参数甚至不同的层而发生改变[11]。文献[12]提出一种自适应的FCM框架, 灰度的非均匀性以增益场 (gain field) 形式引入到目标函数中, 再通过加入正则化项使得增益场的变化缓慢而平滑, 实现对增益场的估计和校正。文献[6]提出一种通过改变目标函数来补偿非均匀性的方法, 该方法假设MRI图像模型为组织的真实信号与增益场的乘积:

其中, Yk和Xk分别表示第k个像素灰度的观察值和真实值, Gk为第k个像素的增益场, N为MRI图像像素总数。对上式使用对数变换, 得到偏差场 (bias field) 模型:

其中, yk和xk分别表示第k个像素灰度观察值和真实值取对数后的结果, βk表示第k个像素的偏差场。以上述模型为基础改进目标函数, 同时加入空间正则化项, 既可矫正图像的灰度非均匀性, 又可抑制噪声对图像分类的影响, 但这种方法的局限性在于仅能使用图像灰度作为聚类特征。文献[9]进一步采用B样条曲面估计偏差场, 对样条曲面的参数选取使用一种两阶段法:首先使用最小均方法逐层估计曲面参数, 而后结合相邻层间信息, 修正参数。该方法在脑部MRI分割中表现出较好的鲁棒性和有效性。文献[13]同样采用了改进目标函数来补偿灰度非均匀性的方法, 但与文献[6]不同的是对偏差场使用一种均值传导的滤波算子, 该算子通过计算任意非边界像素与其四邻域像素的差值, 当差值大于一给定阈值时, 用均值代替它们的原始值, 使用该算子平滑偏差场, 此算法在与同类算法对脑部MRI分割的比较中, 结果更为准确。文献[14]利用可能性模糊C-均值算法 (possibilistic fuzzy C-means, PFCM) 具有减小噪声和异常点对聚类结果影响的优势, 并结合连续局部灰度聚类 (coherent local intensity clustering, CLIC) , 准确地估计了偏差场并实现了对不同组织的分类, 还有效克服噪声和灰度非均匀性对脑部MRI图像分割的影响。

2.2 基于核函数的FCM算法

传统FCM采用欧式距离作为度量, 对球状点云数据有较好的分类效果, 但对于其他形态的点云数据, 难以得到正确的分类[15]。随着对FCM算法的深入研究, 采用非欧式距离代替传统FCM中的欧式距离作为度量, 对于形态复杂的医学影像点云数据有更强的鲁棒性。其中基于核函数的FCM (kernelbased FCM, KFCM) 方法得到了广泛研究。核函数的基本原理是将线性不可分的样本集使用一个非线性变换映射到高维空间中, 从而实现线性可分的目的。文献[7]使用高斯径向基函数作为核函数:

其中, dm表示向量的维数, σ为尺度参数, 并由此产生了新的距离公式:

其中, xm和vn分别表示图像第m个像素的特征向量和第n类的聚类中心。在引入空间约束后, 该方法在对脑部MRI分割中体现了很好的准确性和鲁棒性。文献[16]针对传统模糊核聚类算法当数据类差别很大时, 小数据类被误分或被大数据类吞并的缺陷, 提出了一种加权模糊核聚类 (weighted kernel based FCM, WKFCM) 算法, 该方法在目标函数中对每类乘该类动态权值, 在对脑MRI图像分割中, 相比较KFCM结果, 脑室信息无遗漏, 边界更为光滑。文献[17]针对文献[7]中高斯径向基函数 (Gaussian radial basis function kernel) 中带宽σ的选取问题, 提出使用数据点距中心距离的标准差作为带宽的自适应选取参数。文献[18]提出了一种基于多核函数的FCM (multiplekernel based FCM) , 将多个核函数的线性组合作为新的核函数, 在对脑部T1序列MRI图像模型分割中, 分割结果优于文献[7]中提出的方法。文献[15]比较了不同核函数对不同数据集的分类效果, 指出基于核函数的FCM对核函数类型和核函数参数高度敏感。但这些KFCM算法存在的问题是:聚类的原始特征被引入到高维特征空间, 因此聚类结果难以像在原始特征空间那样进行直接解释。

2.3 FCM与其他算法的联合应用

近年来, 基于可变形轮廓的医学图像分割算法逐渐流行, FCM作为一种基于区域的有效分割算法, 可与这些边界算法相结合, 以达到更好的分割效果。文献[19]针对区域主动轮廓模型 (chan-vese, CV) 对初始位置敏感的问题, 使用FCM粗分割的结果作为CV模型的初始值, 消除了初始位置对分割结果的影响。文献[20]针对水平集 (level set) 分割脑部组织时存在的收敛速度慢、分割质量对迭代终止条件敏感等问题, 使用FCM的隶属度计算level set中区域压力项Vp, 减少了迭代次数, 并降低了对噪声的敏感度。文献[21]使用FCM分类结果对level set初始化, 估计参数并调整曲线演化, 该方法有效地解决了level set算法需大量人工干预的问题, 在对各种医学图像分割中, 均表现出较强的鲁棒性。

此外, FCM还可与其他算法相结合用于图像分割。文献[22]提出了一种基于蚁群算法的FCM, 弥补了传统FCM聚类个数难于确定、搜索常陷于局部极值的问题, 提高了脑部MRI图像的分割质量和收敛速度。文献[23]将分水岭算法分割后的区域进行合并, 而后再用WKFCM算法聚类处理, 较好地解决了分水岭算法的过度分割问题, 在对脑部MRI图像分割中, 得到的图像轮廓更为清晰。

3 结语

FCM已广泛应用于医学图像分割领域, 并已经成为分割脑MRI图像的常见手段。本文针对FCM用于脑MRI图像分割时面临的噪声、灰度非均匀性的影响, 对提出的改进算法进行了分析回顾, 可以看出:通过在目标函数中引入空间约束, 使组织保持空间连续性, 可达到抑制噪声的目的;针对灰度非均匀性, 近年来已提出了多种基于FCM的校正算法, 在脑部MRI图像中均取得了较好的分割效果。基于核函数FCM, 虽然已展示出潜在优势, 然而针对具体图像应选取何种核函数以及核函数参数的确定, 还需要全面系统的分析。FCM与其他方法的联合是近期的研究热点, 特别是与level set等轮廓分割算法的联合应用, 结合了基于区域与基于边缘分割的优势, 对于边缘较弱的脑MRI图像, 取得了很好的分割效果。

今后对FCM的改进主要有2个方向: (1) 改进目标函数, 如引入约束项或是采用新的距离计算方法代替欧式距离; (2) 与其他分割算法结合起来, 特别是与基于轮廓的算法相结合, 这样可以有效地利用区域分割与轮廓分割的优势, 得到更为合理的分割结果。由于FCM算法分割医学图像具有计算量较小、符合医学图像模糊性等特点, 其仍将是一种常用并且有效的医学图像分割算法。

摘要：研究了模糊C-均值 (fuzzy C-means, FCM) 算法在脑MRI图像分割中的应用, 介绍了传统FCM算法在图像分割中存在的不足, 并从空间连续性与磁场非均匀性校正、基于核函数的FCM算法以及FCM与其他算法联合分割3个方面, 阐述了对传统FCM算法的改进, 最后指出了改进目标函数和与其他分割算法相结合是今后主要的研究方向。

模糊均值算法第7篇

1 模糊C - 均值聚类算法

通过隶属度来确定每个数据对象属于某个聚类的程度的聚类算法就是模糊C - 均值聚类算法[2]。

FCM将n个向量( i = 1,2,3,…,n) 分为c个模糊的小组,通过求解每一组的聚类中心,使得目标函数在非相似度指标下达到最小值。FCM是用模糊来划分,用隶属度来确定每一个数据点属于各组的程度。因为归一化的规定,所以任何一个数据集的隶属度和等于1[3]。

则FCM目标函数的一般为

在此uij介于[0,1]间; 模糊组i的聚类中心用ci来表示,第i个聚类中心与第j个数据点间的欧几里德距离,且m ∈[1,+ ∞ ) 是一个加权指数[4]。从而得到新的目标函数,式( 3) 是式( 4) 得到最小值的必要条件

这里 λj,j∈[1,n],是式( 1) n个约束式的拉格朗日乘子。对所有输入的参数求导[5],则式( 2) 达到最优值的必要条件为

基于上述两个必要条件,模糊C - 均值聚类算法可用以下步骤来确定聚类中心和隶属矩阵ui:

步骤1 用样本值来初始化隶属矩阵U,使其满足式( 1) 中的约束条件;

步骤2 用式( 4) 计算c个聚类中心,i = 1,…,c;

步骤3 根据式( 2) 计算目标函数。若目标函数小于某个给定的阀值或者它相对上次目标函数值的改变量小于某个阀值,则算法终止;

步骤4 用式( 5) 计算新的隶属矩阵。返回步骤2,直到算法终止,得出最优值。

2 算法优化与改进

2. 1 内核方法和核函数

是一个非线性变换到一个高一维特征的模糊空间[6]。用内核来表示即k( x,y) ,径向基函数和内核多项式为

式中,d是矢量x的维数; a≥0; b的范围是[1,2]。显然,对于所有的x和上面的径向基内核有结果k( x,x) =1[7]

将式( 6) 等价代换到式( 7) ,从而产生核函数。

2. 2 优化后算法

将内核函数引入式( 8) ,从而取代欧几里德距离得到新的目标函数式( 9)

在实际的算法实现过程中,使用式( 11) 取代式( 10) ,能够进一步简化式( 11) 的计算复杂度[8]

使用内核函数替换式( 12) ,得出式( 13)

xk是样本空间中被  映射的样本数据,这样所有的样本数据能够被提前计算和存储。在式( 12) 中同时使用式( 14) 和式( 15) 进行交替迭代能够简化目标函数,方便计算[9]

式(14)和式(15)分别称为KFCM_S1算法和KF-CM_S2算法。

2. 3 实验算法步骤

步骤1计算数据样本中的形心数量C和集群数,然后选择初始类的形心,ε > 0 设置是一个微小的值;

步骤2 对于KFCM_S1 和KFCM_S2,只计算其平均值或者均值滤波的图像;

步骤3 使用式( 14) 更新矩阵的分区;

步骤4 使用式( 11) 更新形心。重复第3 步和第4 步直至满足条件。

当算法的迭代次数达到用户指定的迭代次数或相应目标函数达到极小值,迭代过程将终止,保证得到最优解或者局部最优解[10]。

3 测试与分析

3. 1 人物图像测试

3. 2 细菌图像测试

3. 3 算法速率

椒盐噪声和高斯噪声的噪声密度都为0.05,然后测试FCM、FCM_S、KFCM_S对噪声图像的分割和去噪的时间。表1为加入高斯噪声的图像处理时间,表2为加入椒盐噪声的图像处理时间。

由图5 和图6 可以看出,KFCM_S算法处理加高斯和加椒盐噪声的图像时间最短。

3. 4 峰值信噪比

峰值信噪比越高,处理后的图像与原图越接近。表3 为不同算法的峰值信噪比值,从表中可看出,只有KFCM_S算法的峰值信噪比最高,该算法对图像去噪和分割性能最好。

4 结束语

通过算法速率测试,KFCM_S算法相比较传统的FCM算法,在图像的分割和去噪的时间上减少约68% ,这体现了该算法的高效性。通过峰值信噪比测试,得出优化后的算法峰值信噪比最高,对图像分割和聚类效果更加准确,KFCM _S算法的峰值信噪比比FCM算法提高了约10% ,证明了KFCM_S算法分割图像的优越性和鲁棒性。

摘要：针对传统FCM算法处理噪声图像时存在去噪性能差、聚类时间长、分割效果不佳等问题。文中通过拟合核聚类算法和传统的FCM算法,产生一种使用内核诱导距离取代欧式距离的核函数FCM算法,并推导出利用样本特征和空间信息的核FCM聚类算法,通过大量的对比测试,得出文中算法较传统FCM算法在图像的分割和去噪时间上减少约68%,峰值信噪比相比传统FCM算法提高了约10%。证明优化后的算法具有更好的抗噪性与鲁棒性。

关键词：FCM,内核诱导距离,核聚类,鲁棒性

参考文献

[1]李云松.改进的模糊C-均值聚类对噪声图像的分割[D].兰州:兰州理工大学,2007.

[2]廖松有,张继福,刘爱琴.利用模糊熵约束的模糊C均值聚类算法[J].小型微型计算机系统,2014,35(2):379-383.

[3]陈新泉.特征加权的模糊C聚类算法[J].计算机工程与设计,2007,28(22):5329-5333.

[4]高新波,范九伦,谢维信.区间值数据模糊C-均值聚类新算法[J].西安电子科技大学学报:自然科学版,1999,26(5):604-609.

[5]唐成龙,王石刚.基于数据间内在关联性的自适应模糊聚类模型[J].自动化学报,2010,36(11):1544-1556.

[6]潘庆丰,陈国龙.基于核函数的模糊C均值聚类算法[J].集美大学学报:自然科学版,2006,11(4):369-374.

[7]周巧萍,潘晋孝,杨明.基于核函数的混合C均值聚类算法[J].模糊系统与数学,2008,22(6):148-151.

[8]程可嘉.基于核函数的模糊聚类算法研究[D].成都:电子科技大学,2009.

[9]蒋帅.K-均值聚类算法研究[D].西安:陕西师范大学,2010.

模糊均值算法第8篇

(一) 背景与目的

被测试者对于样本特征有着较大的敏感性, 为使之更好地配合如实提供特征信息, 可以建立一种随机截尾的Simmons模型, 即在随机截尾模型基础上增加一个装置产生服从均匀分布的随机变量。正是这一装置“滤去”了被测试者的敏感性, 从而可以准确地估计出特征向量 (体重, 腰围) 的估计平均值。

(二) 假设与约定

第一, x= (x1, x2) T为样本体重与腰围特征向量。x1= (x11, x21, , xn1) , Xi1为第i个女生ai体重数据;x2= (x12, x22, , xn2) T, Xi2为第i个女生ai腰围数据;X (i) = (xi1, xi2) T为ai的两特征向量, (i=1, 2, n) 。

第三, 假设样本x (1) , x (2) , , X (n) 相互独立同分布, f (x) =f (x1, x2) 为x= (x1, x2) 的概率密度, f1 (x) , f2 (x) 为相应边际密度, μ= (μ1, μ2) 为x= (x1, x2) 的数学期望。

第四, 在测试实验中的两次抽卡所显示的数字Y, Z分别为服从[c1, c1+t1], [c2, c2+t2]上的均匀分布。

第五, 已知样本容量n=20。

(三) 实验步骤

第一, 取3个空盒。

1号盒子放入红、白、黑、绿4种色小球, 放入比例为;2号放入22张卡片, 卡片上标有重数据42、43、、63;3号放入12张卡片标上腰围数据16、17、、27。将3个盒子分别摇匀。

第二, 每位被测试者有放回地先从1号盒摸取一小球, 并作答:

取到红、白、黑球分别作答1、0、, 取到绿球则转到下一步。

第三, 取到绿球者接着一次性从2号盒抽取两张卡片再放回摇匀, 将该两张卡片上的数字Yi1、Zi1与自身的特征数据Xi1作比较, 并作答:

若Xi1>max{Yi1, Zi1}, 作答1;若min{Yi1, Zi1}Xi1max{Yi1, Zi1};作答0;若Xi1

第四, 记被测试者从1号盒子摸取小球、从2号盒子抽取卡片、从3号盒子抽取卡片时的作答值分别为βi, αi1, αi2。

对X1, X2均沿用数据βi, 则最后得到的数据记为γi1, γi2, (i=1, 2, n) 。

(四) 模型的建立与分析

由上面实验结果有:

分别求解μ1, μ2的无偏估计与方差估计之表达式:

第一, μj的无偏估计表达式: (j=1, 2) :

本均值为:

μj的无偏估计:

第二, 通过γij的方差求得μj的方差估计表达式 (j=1, 2) :

于是μj的方差估计为:

(五) 数据统计与结果

从上面可以看出, Var关于p单调递增, 综合考虑取p=0.4, 则在1号盒子中放入30个小球:白球4, 红球4, 黑球4, 绿球18。

通过测试实验得到以下样本数据 (见表1) :

βi所在列为空白说明取球者αi摸取的球为绿色。

根据表1的数据及①、②、③式可求得所要考察的两特征估计值。

样本均值:

无偏估计:

方差估计:

二、基于一种模糊均值算法的识别分类

所要识别的为参加测试男生“偏胖”、“中等”与“偏瘦”。算法给出了各男生所属类别的模糊矩阵, 在此基础上构造出模糊集并进行了知识推理。

记号:第一, X={x1, x2, , xn}, xk为第k名男生ak体重, k=1, 2, , n;第二, 论域A={[z1, z2) , [z2, z3) , [z3, z4], (z4, z5]}为体重区间集合z1=48, z2=53, z3=58, z4=63, z5=69;第三, 识别类集合Ω={C1, C2, , Cm}, m为识别的模式类个数;第四, 类中心集合W={y1, y2, , ym}, yi为Ci类中心, i=1, 2, , m;第五, 模糊矩阵, U=[uij]mn第i行j列元素uij为aj属于类Ci的隶属度;第六, m=3, n=20, 分别表示模糊集偏胖、中等与偏瘦。现有测得样本数据 (见表2) :

(一) 模糊均值算法

1、算法依据

构造加权指数函数:, 使得L (U, W) 取最小。应用Lagrange乘子法可得:

定理:L (U, W) 局部取最小的充要条件 (对所有的1lm, 1kn, xk≠yl) :

2、算法步骤

第一, 对数据集X={x1, x2, , xn}, 任意给定初始模糊矩阵U (0) =[uij (0) ]mn;第二, 计算均值, s为叠代次数 (1im, s=0, 1, 2, ) ;第三, U (s) =[uij (s) ]mn替代为第四, 任意给定正数ε (0<ε<0.5) , 若则停止算法, 否则令s=s+1返回至第二步骤。

3、算法实现与分析

第一, 算法实现。

对表2中的数据, 事先任意给定初始矩阵:U (0) =[uij (0) ]mn

取t=2, ε=0.4, 算法终止于s=1, 有‖U (1) -U (0) ‖=0.38<ε且最终矩阵为:U (1) =[uij (1) ]mn为:

第二, 结果分析。

比较U (0) 与U (1) 中各元素 (隶属度) , 第14、16、20列变化较显著 (见表3) :uij (s) 为aj属于类Ci的隶属度 (s=0, 1;1m3;1j20) 。

从表3可看出:a16与a20在事先基本上将之分类于c3 (偏瘦) 或者c2 (中等) , 算法实现后a16与a20明显识别为c3 (偏瘦) ;对于a14则识别结果不同, 由原来属于类c2变成现在的c3类。

由表2中可知, a16、a20、a14所对应的x16、x20、x14分别为48.8、48.8、53.8都小于均值58.22 (千克) , 三者应该分类为c3 (偏瘦) , 识别结果是恰当的。

如果将ε= (0.4) 取到更小, 则经过这一模糊均值算法, 其结果更为准确。

摘要：文章在随机截尾模型基础上建立了一种随机截尾的Simmons模型, 讨论了有限总体下敏感性问题的抽样调查方法, 以及利用这种方法所得出的估计量, 并给出了无偏与方差估计量公式。还提出了一种模糊均值算法, 更加有效地对训练样本进行比较准确模糊分类。

关键词：Simmons模型,抽样调查,估计,模糊均值算法

参考文献