均值模糊范文

2024-07-01

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

均值模糊第1篇

图像分割是模式识别、计算机视觉领域的经典研究课题之一, 是由图像处理到图像分析的关键技术, 在实际生活中的应用非常广泛。作为模糊聚类算法中典型的形式, 模糊C均值 (FCM) 算法已广泛地应用在图像分割领域。但是该算法存在容易收敛到局部极值、计算量大、容易受噪声影响等不足。针对传统的FCM算法对颜色相近的区域很难分割和容易受噪声干扰的缺点, 本文对FCM分割算法进行了改进。

2 模糊C均值聚类 (FCM) 算法

传统的FCM算法通过迭代使得模糊目标函数达到最小以确定最佳聚类, 该算法的实现方法是根据数据点的特征将数据点划分为要求的几个类, 使得被划分到每个类内的数据点的特征尽量相似, 而不同类之间的数据点特征尽量不同。用隶属度函数表示样本与子集的隶属关系, 子集构成的矩阵称为模糊隶属矩阵。

设表示各类的聚类中心, 目标函数定义为:

其中, U为模糊隶属矩阵, 为模糊指数;dik A为第个样本到第i类的距离, 其定义为:

xk为Rs空间中第k个样本;表示样本点xk到聚类中心vi的欧式距离;A一般取单位矩阵。

3 基于各向异性均值漂移的FCM聚类算法 (AMSFCM)

均值漂移 (Mean Shift, 简称MS) 算法是一种有效的特征空间聚类算法, 该算法的原理简单、迭代效率高, 已广泛应用在图像分割和信息跟踪等领域。它的基本原理是通过迭代搜索特征空间中样本点信息最聚集的地方, 迭代过程中搜索点沿着样本点密集的方向移动到密度函数的局部极大值点, 对于图像分割, 就是要找到不同色彩的聚类点。

基于各向异性均值漂移的模糊C均值聚类算法 (AMSFCM) 的思想是在FCM算法的基础上对样本点进行均值漂移聚类, 由于MS算法是在特征空间中搜索到局部密度极大点, 分割图像时统一考虑图像的空间信息和颜色信息, 对于彩色图像, 每个像素点的信息可用5维特征空间中的值来表示, 即。其中, 前两个参数 (x, y) 表示像素在特征空间中的坐标, 通过色彩转换将图像中的亮度、色差都一一表示出来, 颜色空间 (L, U, V) 中的参数分别表示图像的亮度和色差, 本算法中颜色之间的色距用马氏距离来定义。颜色值差异大的色距也大, 颜色值差异小的色距也小。坐标和颜色都相近的像素点, 在其对应的5维特征空间中也相近, 因此聚类过程中我们把坐标和色距都相近的点归为一类, 实现图像分割。

在AMSFCM算法中我们使用下面的核函数

其中, hs, hr分别表示像素点特征空间和颜色空间中核函数的带宽, xs, xr分别为像素点在空间位置的坐标和该像素点的 (灰度图像q=1, 彩色图像q=3) 维向量特征。

为了自适应地调整带宽, 我们可以将核密度估计表示成如下的形式

其中, 核函数kr的带宽hr是带宽矩阵Hs的函数, 为马氏距离, 在聚类过程中, 通过调节空间信息中的带宽来更新颜色信息的带宽hr, 目的是尽量缩小马氏距离, 以便对相似像素进行较优的分割。

在实际应用中, 像素点的分布在在方向上常常是不对称的。MS算法中的核函数决定算法本身的收敛性, 同时核函数是否为各向异性决定MS算法是否各向异性。因此将带宽矩阵分解为:

根据公式 (6) 更新带宽矩阵

具体执行步骤如下:

步骤一:初始化参数:指定聚类类别数c, 11) ;设置迭代计数器b=0, 设定迭代停止阈值

步骤二:用值在[0, 1]间的随机数初始化隶属矩阵U0;

步骤三:利用公式 (7) 计算c个聚类中心

步骤五:利用公式 (4) 和公式 (5) 计算核函数的带宽;

步骤六:计算MS向量,

当MS向量小于ε1时, 迭代停止;

步骤七:将空间距离和色距相近的像素点作为一类重构图像;

步骤八:循环执行步骤三到步骤七, 当迭代终止。

4 实验结果与分析

为便于比较, 实验在给定相同的初始隶属度矩阵的情况下分别采用传统的FCM算法和改进算法对图像进行分割。

实验一:对临床脑部MR图像分割, 参数初始值设置如下:聚类类别数为灰质、白质、脑脊液、背景等4类;最大迭代次数100;模糊指数;核函数的带宽分别为迭代停止阈值分别为分割结果如下图所示:

实验二:对含有密度为1%椒盐噪声的脑部MR图像分割, 参数设置如下:核函数带宽矩阵的带宽分别为;其它参数与实验一相同。分割结果如下图所示:

图2、图5分别为使用FCM算法的分割结果, 图3、图6分别为使用的AMSFCM算法的分割结果。从实验结果可以看出, 由于原始脑部MR图像中灰质部分与白质部分的色差较小, 使用基于欧式距离的FCM算法, 由于没有考虑像素的空间信息, 在分割灰质与白质区域时容易发生颜色漂移, 造成误分割, 而且分割结果对椒盐噪声也很敏感。而改进的算法采用基于各向异性的核函数, 同时考虑了像素的本身信息与空间信息, 能够克服颜色相近区域的漂移现象, 通过使用马氏距离加大相近颜色的色距, 能够对原始图像准确的分割, 同时降低了噪声对分割的干扰。

5 结论

本文针对传统FCM算法对颜色相近区域和细长区域很难分割和容易受噪声干扰的缺点, 提出了一种改进的模糊C均值聚类图像分割方法, 即MSFCM算法。该算法在图像分割过程中使用各向异性核函数通过关联每个样本点的空间信息和颜色信息反映了图像的真实结构。通过对脑部MR图像进行分割比较, 证明本文提出的算法具有较强的抗噪性, 特别是去除椒盐噪声, 在分割颜色变化不明显的区域时更体现了改进算法的优势。

参考文献

[1]J.C.Bezdek.Cluster validity with fuzzy sets[J].Journal of Cybernetics, 1974.

[2]Y.Z.Cheng.Mean shift, mode seeking, and clustering[J].IEEE Trans on pattern analysis and machine intelligence, 1995.

[3]R.T.Collins.Mean-shift blob tracking through scale space[C].Processings2003 IEEE computer society conference on computer vision and pattern recognition.Los Alamitos:IEEE computer society, 2003.

[4]李华, 张明新, 郑金龙.融合多特征的均值漂移彩色图像分割方法[J].计算机应用, 2009.

[5]伊怀锋, 黄先武.基于均值偏移的彩色图像分割算法[J].计算机应用, 2006.

[6]J.wang, B.Thiesson.Image and video segmentation by anisotropic kernel mean shift[C].Processings of European conference on computer vision.New York, 2004.

均值模糊第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-均值核爆天然地震

基于权重系数模糊C均值聚类第3篇

1 模糊C均值聚类算法

FCM算法[3]由Bezdek于1974年首次提出, 通过最优化目标函数值来获得数据样本的最优划分, 由于算法中没有考虑样本数据的领域信息, 导致分割结果易受噪声和复杂背景的干扰而出现误分割。Girolam等人对FCM算法进行了改进, 提出了核模糊聚类算法 (KFCM) [8], 将核函数的概念引入到样本数据与聚类中心的相似性度量中, 增强了算法对噪声的鲁棒性。Wang等将局部和非局部空间约束引入到FCM算法中, 对MRI脑图像进行分割并获得了较好的分割结果, 但该方法对于信噪比较低的图像分割效果不理想[9]。Yang等人将高斯核函数和支持向量机方法引入到F CM算法中, 极大地抑制了图像中存在的噪声和离群像素的干扰, 获得了较好的分类结果[10]。文献[11]提出了一种基于全局空间相似性的模糊聚类算法, 将数据空间位置信息引入到数据与聚类中心的相似性度量计算中, 增强了分割结果的空间分布连续性。

该文提出一种基于权重系数模糊C均值聚类算法, 并将其应用于图像分割中。算法通过定义权重系数矩阵并构造相应的核函数, 将数据样本中每个样本的邻域特征信息引入到数据样本与聚类中心的相似性计算中, 通过核函数将样本集合中的样本映射到高维空间中, 实现样本在特征空间的优化。由于该文算法充分考虑了样本点的邻域信息, 极大地抑制了样本空间中的噪点和离群样本点, 与传统FCM算法相比, 该文算法能够获得更加精确的图像分割结果。

模糊C均值聚类算法是一种无监督的自动分割方法, 算法首先要确定聚类中心数c并初始化聚类中心点, 通过迭代更新聚类中心和最小化目标函数值来计算样本中数据与各个聚类中心的隶属度, 根据隶属度矩阵对样本集合X= (x1, x2, …xn) ∈Rn×p中数据进行分类。FCM算法目标函数如下式所示:

式中:xi∈X为样本中第i个数据;vj∈V, V= (v1, v2, …vn) ∈Rn×p为第j个聚类中心;ij为第i个数据到第j个聚类中心的隶属度;m=2为权重指数。算法通过更新聚类中心和隶属度矩阵来最小化目标函数值, 其更新公式如公式 (2) 和公式 (3) 所示:

2 基于权重系数模糊C均值聚类

由于传统FCM算法仅对孤立数据样本点进行分类, 没有考虑其领域信息, 导致分割结果空间分布不连续, 在图像分割中常常表现为分割结果易受孤立噪点和复杂背景的干扰而出现误分割现象。该文将权重系数概念引入到节点间相似性度量中, 考虑了数据的领域相关性, 增强了分割结果的空间分布连续性, 获得的分类结果更加符合人们的实际需求。权重系数定义如下:

从目标函数定义中可以看到, 特征空间样本距离如下所示:

其中K (x, y) (28)  (x)  (y) 为线性核函数, 则基于权重系数模糊C均值聚类目标函数更新公式如下式所示:

将基于权重系数特征空间样本距离带入聚类中心和隶属度矩阵更新公式中, 可以得到改进的聚类中心和隶属度更新公式如下式所示:

基于权重系数模糊C均值聚类算法流程如下所示:

(1) 确定聚类中心个数c和最大迭代次数N;初始化隶属度矩阵和聚类中心;

(2) 设迭代次数t=1, 并以样本集合中每个数据点为中心, 计算其3×3邻域样本值与其对应权重系数的乘积和;

(3) 更新聚类中心;

(4) 更新隶属度矩阵;

(5) 如果满足终止条件, 即相邻两次迭代目标函数值之差小于给定阈值或大于最大迭代次数, 退出循环, 根据每个样本点到各个聚类中心隶属度函数值的大小对数据样本点进行分类;否则, 执行步骤 (3) , t=t+1。

3 结果与分析

为了验证该文算法的可行性, 分别对遥感图像、具有自然背景彩色图像和星云图像三类具有不同特征的图像进行仿真实验 (如图1、图2和图3所示) , 比较该文算法与FCM算法和KFC M算法分割结果的精确性。图 (a) 为原始图像, 图 (b) 为FCM算法分割结果, 图 (c) 为KFCM算法分割结果, 图 (d) 为该文算法分割结果, 从分割结果中可以看到, 传统FCM算法易受噪声和杂波的干扰导致分割结果目标空间分布离散, 无法对图像中目标进行精确分割;KFCM算法分割结果在一定程度上抑制了图像中噪声和杂波的干扰, 分割结果类内数据空间分布连续增强, 但仍无法获得令人满意的分割结果;该文算法通过定义权重矩阵, 将图像中每个像点的邻域信息引入到聚类中心和隶属度矩阵的更新计算中, 增强了算法对噪声和杂波的鲁棒性, 获得了较好的图像分割结果。

4 结语

该文提出一种基于权重系数模糊C均值聚类算法, 并将其应用于图像分割中。该文算法根据图像中每个像点及其邻域像点的空间位置关系, 定义相应的权重系数矩阵, 构造相应的核函数, 并将其引入到模糊C均值聚类中。通过核函数将样本集合中的样本映射到高维空间中, 实现样本在特征空间的优化。图像中每个像点邻域特征信息的引入增强了算法对噪声和杂波的鲁棒性, 提高了图像分割结果的精度。

摘要：传统基于模糊C均值聚类图像分割算法易受复杂纹理和噪声干扰, 无法准确分割图像。针对这一现象, 提出一种基于权重系数模糊C均值聚类算法, 并将其应用于图像分割中。算法定义权重系数矩阵, 将每个像点的邻域信息引入到像点间相似性度量中, 计算每个像点与聚类中心点的邻域相似程度, 根据权重系数矩阵确定邻域中每个像点在邻域特征计算中所占权重, 增强了算法对噪点和杂波的鲁棒性。实验结果表明, 与传统模糊C均值聚类算法相比, 该文算法获得更加精确的图像分割结果。

关键词：模糊C均值聚类,权重系数,FCM

参考文献

[1]Karasulu B, Korukoglu S.A simulated annealing-based optimal threshold determining method in edge-based segmentation of grayscale images[J].Applied Soft Computing, 2011, 11 (2) :2246-2259.

[2]Isa N A M, Salamah S A, Ngah U K.Adaptive fuzzy movingk-means clustering algorithm for image segmentation[J].IEEETransactions on Consumer Electronics, 2009, 55 (4) :2145-2153.

[3]Bezdek J C.Cluster validity with fuzzy sets[J].Cybernetics and Systems, 1974, 3 (3) :58-73.

[4]Boykov Y, Veksler O, Zabih R.Fast approximate energy minimization via graph cuts[C]//Proceedings of the 7th IEEE International Conference on Computer Vision.Los Alamitos:IEEE Computer Society Press, 1999, 1:377-384.

[5]L.Grady, Random Walks for Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, no.11, pp.17681783, 2006.

[6]Mortensen E, Morse B, Barrett W, et al.Adaptive boundary detection using'live-wire'two-dimensional dynamic programming[C]//Proceedings of Computers in Cardiology.Los Alamitos:IEEE Computer Society Press, 1992:635-638.

[7]Kass M, Witkin A, Terzopoulos D.Snakes:active contour models[J].International Journal of Computer Vision, 1987, 1 (4) :321-331.

[8]Girolami M.Mercer kernel-based clustering in feature space[J].IEEE Transactions on Neural Networks, 2002, 13 (3) :780-784.

[9]Wang J Z, Kong J, Lu Y H, et al.A modified FCM algorithm for MRI brain image segmentation using both local and non-local spatial constraints[J].Computerized Medical Imaging and Graphics, 2008, 32 (8) :685-698.

[10]Yang X W, Zhang G Q, Lu J, et al.A kernel fuzzyc-means clustering-based fuzzy support vector machine algorithm for classification problems with outliers or noises[J].IEEE Transactions on Fuzzy Systems, 2011, 19 (1) :105-115.

基于泛函序列的模糊C均值算法第4篇

伴随着模糊理论的形成、发展和深化,人们提出了许多模糊聚类算法。在实际中受到普遍欢迎的是基于目标函数的模糊聚类方法[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} \to Ι R 。$

S:{x*∈Df:f(x*)<f(y)∀y∈B0(x*,r)}A:Df→Df是一个迭代算法,有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定义在(Mfc×IRcs)→IR上[7]。

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

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

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

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

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

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

可以得到下面两个引理。

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

引理2:设ψ:Mfc→IR,ψ(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在(Mfc×IRcs)上是连续的。

定理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在Mfc×IRcs上是紧集。

由定理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$ 其中1≤i≤c,1≤k≤n。Γm为定义在(Mfc×IRcs)→(Mfc×IRcs)为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:X→R和T:X→X是一个连续的映射,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

均值模糊第5篇

计算加速设备价格和功耗比日益下降,包含加速设备和一般计算核心的异构计算机系统已经在企业计算日益普及。但是,使用底层的加速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是1024×1024的原图,图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.

均值模糊第6篇

关键词：协作学习,分组系统,学习者特征,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.

均值模糊第7篇

聚类是将一组给定的未知类标号的样本分成内在的多个类别, 使得同一类中的样本具有较高的相似度, 而不同类中的样本差别大。聚类分析的目的是揭示和刻画数据的内在结构, 其内容涉及统计学、生物学、以及机器学习等研究领域, 并在模式识别、数据分析和挖掘、图像处理等领域获得了广泛的应用[1]。模糊C均值 (Fuzzy C-Means, FCM) 算法是一种基于划分的聚类算法, 它的思想就是使得被划分到同一类的对象之间相似度最大, 而不同类之间的相似度最小。模糊C均值算法是普通C均值算法的改进, 普通C均值算法对于数据的划分是硬性的, 而FCM则是一种柔性的模糊划分。

目前大多数针对模式识别的软件都是基于Matlab, 模糊C均值就已经集成在Matlab语言中。Matlab是集数值分析、矩阵运算、信号处理和图形显示于一体的高性能数学软件, 但Matlab也存在其自身的局限性:一般基于Matlab的应用程序不能脱离Matlab集成环境工作, 而且编写界面的功能相对较弱, Matlab本身是一种解释性的语言, 运行速度非常慢, 大大降低了程序的效率。因此, 将Matlab与VB有效地集成在一起, 实现应用系统的无缝集成, 对于有效缩短开发周期, 优化系统性能是十分有意义的。介绍用VB与MatrixVB的混编来实现模糊C均值聚类方法。

1 关于MatrixVB 的简介

MatrixVB[2] 是Mathworks 公司针对VB 提供的一个Matlab 组件库 (Component Object Model Library) , 它提供了600 多个函数, 包括基本的数学运算和功能强大的信号处理、线性代数、串运算及图形图像处理功能等, 用来弥补VB 内建函数的不足, 主要是针对数学函数而言, 它具有Matlab绘图的强大功能, 让VB 能很轻易地画出一些数学函数图形, 为VB 提供了强大的功能扩展, 让程序员更容易地去开发计算应用方面的程序代码。在VB中使用该数学工具包可以避免重复性劳动, 可以减少开发人员实现算法和界面设计方面的困难。

2 模糊C均值原理及其实现

模糊C均值 (FCM) , 是用隶属度确定每个数据点属于某个聚类的程度的一种聚类算法。由Bezdek[3]提出了该算法, 作为早期硬C均值聚类 (HCM) 方法的一种改进。

FCM把n个向量xi (i=1, 2, …, n) 分为c个模糊组, 并求每组的聚类中心, 使得非相似性指标的价值函数达到最小。FCM与HCM的主要区别在于FCM用模糊划分, 使得每个给定数据点用值在[0, 1]间的隶属度来确定其属于各个组的程度。与引入模糊划分相适应, 隶属矩阵U允许有取值在[0, 1]间的元素。不过, 加上归一化规定, 一个数据集的隶属度和总等于1:

$\sum_{i = 1}^{c} u_{i j} = 1, \forall j = 1, 2, \dots, n (1)$

则FCM的价值函数 (或目标函数) 就是一般化形式:

$J (U, c_{1}, c_{2}, \dots, c_{c}) = \sum_{i = 1}^{c} J_{i} = \sum_{i = 1}^{c} \sum_{j}^{n} u_{i j}^{m} d_{i j}^{2} (2)$

式中, ci为模糊组i的聚类中心;dij=||ci-xj||为第i个聚类中心与第j个数据点间的欧几里德距离;且m是一个加权指数。构造如下新的目标函数, 可求得使式 (2) 达到最小值的必要条件:

$\begin{array}{l} \bar{J} (U, c_{1}, c_{2}, \dots, c_{c}, λ_{1}, λ_{2}, \dots, λ_{n}) = \\ J (U, c_{1}, c_{2}, \dots, c_{c}) + \sum_{j = 1}^{n} λ_{j} (\sum_{i = 1}^{c} u_{i j} - 1) = \\ \sum_{i = 1}^{c} \sum_{j}^{n} u_{i j}^{m} d_{i j}^{2} + \sum_{j = 1}^{n} (\sum_{i = 1}^{c} u_{i j} - 1) (3) \end{array}$

式中, λj, j=1, 2, …, n是式 (1) 的n个约束式拉格朗日乘子。对所有输入参量求导, 使式 (2) 达到最小的必要条件为:

$c_{i} = \sum_{j = 1}^{n} u_{i j}^{m} x_{j} / \sum_{j = 1}^{n} u_{i j}^{m} (4)$

和:

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

根据上述两个必要条件, 模糊C均值聚类算法是一个简单的迭代过程。在批处理方式运行时, FCM用下列步骤确定聚类中心ci和隶属矩阵U :

步骤1 用值在0, 1间的随机数初始化隶属矩阵U, 使其满足式 (1) 中的约束条件。

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

步骤3 用式 (2) 计算价值函数。如果它小于某个确定的阈值, 或它相对上次价值函数值的改变量小于某个阈值, 则算法停止。

步骤4 用式 (5) 计算新的U矩阵。返回步骤2。

通过上面的讨论, 不难看出FCM算法需要两个参数, 一个是聚类数目C;另一个是参数m。以下利用VB和MatrixVB实现上述算法。首先读入待分类的数据, 数据分布如图1所示, 是200组二维数据。设置参数:将数据分为3类, 初始化隶属度矩阵U, m=2。程序如下所示:

算法的输出是C个聚类中心点向量和大小为C×N的一个模糊划分矩阵, 这个矩阵表示的是每个样本点属于每个类的隶属度。根据这个划分矩阵, 按照模糊集合中的最大隶属原则就能够确定每个样本点归为哪个类。聚类中心表示的是每个类的平均特征, 可以认为是这个类的代表点。以下是迭代求取聚类中心和隶属度矩阵的程序:

图2是对未知类别的待分类数据进行模糊C均值聚类的最终结果, 不同的图形表示不同的类别。

3 结语

在此介绍VB与MatrixVB混合编程的模糊C均值方法实现, 程序在 Windows XP Professional 版上用MatrixVB4.5和Visual Basic6.0中文版实现, 具有效率高, 占用系统资源少等优点。文中给出了部分基本代码, 可以根据自己的需要进行扩充, 并应用于分类处理。这种编程方式既节省了时间, 又提高了软件的性能, 对于优化系统, 缩短软件开发周期很有意义。

摘要：针对Visual Basic数值计算能力和图像处理能力的不足, 不利于系统开发, 介绍了模糊C均值法的原理及其基于VB和MatrixVB的实现;该方法将Matlab的强大计算功能与VB的Windows用户界面开发方面优势结合起来, 充分发挥各自优势, 缩短了软件的开发周期。软件测试结果表明, 该计算方法正确, 软件界面友好, 计算速度快, 系统资源消耗少, 操作简便易行, 能满足数据分类的要求。

关键词：Visual Basic,MatrixVB,模糊C均值,模式识别

参考文献

[1]边肇祺, 张学工.模式识别[M].2版.北京:清华大学出版社, 2000.

[2]MathWorks.Inc.MatrixVB User′s Guide[Z].2000.

[3]Bezdek J C.Pattern Recognition with Objective Function Al-gorithms[M].New York:Plenum Press, 1981.

[4]王跃强, 王纪龙, 王云才.VB程序中实现调用Matlab的方法[J].计算机应用, 2002, 2 (21) :95-96.

[5]何强, 何英.Matlab扩展编程[M].北京:清华大学出版社, 2002.

[6]刘炳文.精通Visual Basic6.0中文版[M].北京:电子工业出版社, 1999.

[7]黄锡泉.VB与Matlab无缝接口编程[J].微计算机应用, 2005, 26 (2) :238-239.

均值模糊第8篇

图像分割是指把图像分成具有不同特性的区域并提出感兴趣的目标,它是图像处理到图像分析的关键步骤。近年来,模糊C均值(FCM)算法[1,2]作为一种无监督聚类算法已成功应用在医疗诊断、目标识别和图像分割等领域,其主要目的在于将向量空间的样本点按照某种距离度量划分成一定数量的子空间。

基于图像片的图像处理思想[3,4]是近年来刚刚兴起的用于去除图像噪声的一种方法,其基本原理是将原先图像处理中的点用局部图像片来替代,增加了单个像素点的计算信息,在图像去噪领域得到了很好的应用。本文将这种以片代点的思想应用于基于模糊聚类方法的图像分割,通过实验证明本文的方法很好地克服了基于FCM图像分割所存在的问题,同时该方法也为聚类分割提供了一种全新的思路。

2. 模糊C均值聚类

2.1 传统模糊C均值算法(FCM)

模糊聚类由Dunn[1]首先提出,并由Bezdek[2]推广为一般的模糊C均值聚类算法。该算法通过最小化一个二次目标函数,将数据集(图像)划分为若干类。

FCM算法中目标函数定义如下:

其中,U={uik}∈Rn×c为隶属度矩阵,V={v1,v2,…,vc}∈Rc×p为c个聚类中心的集合,m∈[1,∞]为加权指数,通过大量研究表明,m的最佳选择范围为[1.5,2.5],通常取m=2较为理想。dik=|xk-vi|A表示第k个样本到第i类中心vi的距离,|誗|A表示A范数,一般定义为欧氏距离。

FCM的目标函数可以通过迭代更新隶属度矩阵U和聚类中心集合V达到最优解:

不断更新上述两式直到聚类中心集合V的变化值小于设定值ε(ε>0)。

传统的FCM算法在图像处理过程中主要存在两方面的缺陷:一是对于图像噪声的敏感,这主要是因为传统的FCM算法仅仅考虑了图像各个像素点灰度值之间的差别而没有将图像的其它信息考虑进去,例如空间信息等;另一个就是隶属度函数非单峰值的现象[4]。一般认为,当某一点属于某一类时,该点所对应隶属度的值应该趋向于1,该点其它类对应隶属度的值趋向于0,这就是本文所说的单峰值,如图1(a)所示。但是通过(2)式计算所得的FCM隶属度uik并无法满足单峰值特性。图1(b)中,u1(x),u2(x),u3(x)是FCM的隶属度分布情况,聚类中心为v1=1,v2=3,v3=8。u1(x)在5附近达到局部最大值,因此u1(x)并非单峰值。这种非单峰值的现象在一定程度会影响分类结果。图1(c)为本文方法的隶属度分布。

2.2 FCM的改进算法

为了克服FCM对于图像噪声的敏感性,自FCM被提出之后,人们对其抗噪性进行了大量的研究。因此在传统FCM算法中加入空间约束成为研究的热点。

Ahmed等人[5]于2002年提出了BCFCM,将像素点的局部区域均值引入到传统的FCM目标函数中,以达到抗噪效果,其目标函数如下:

其中xr表示以k点为中心的邻域Nk中像素点的灰度值,nk为集合Nk的势,即Nk中的像素个数。参数用来控制该局部项对于全局的影响。在此基础上,Chen等人[6]提出了BCFCM的快速算法,FCM_S1和FCM_S2,通过提前计算出各个像素点的局部均值来提高算法速度。

随后,Szil觃gyi等人[7]将BCFCM算法流程重组,提出了EnFCM。他们首先对图像进行均值滤波,如下:

其中,ζk表示各个像素点滤波后的灰度值。其目标函数为:

式中,hl表示图像中灰度级为l,l∈{1,2,…L}总像素点个数,L为图像的灰度级个数,对于一般的灰度图像而言,L=256。相应的更新函数为:

无论是经典的BCFCM还是改进的MFGFCM都不可避免地需要通过一些控制参数来控制局部区域约束项,而这些参数的设定往往都要根据具体实验而定,无法提出一个统一的标准方法,在实现及使用过程中,参数的设定较为繁琐。针对此问题,本文提出了一种全新的聚类方法。使用图像片来代替单个像素点的计算,不仅拉大了像素点与聚类中心之间的距离,使得聚类精度更高,同时消除了目标函数中的局部区域控制项,与传统FCM相比,在参数设置方面仅仅增加了一个片窗口大小的设置,就能够达到更好的抗噪性能。另一方面,本文还有效地消除了由于FCM所导致的隶属度函数的非单峰值现象,与理想的隶属度函数分布十分相近,以达到提高分割精度的目的。

3. 基于图像片的模糊C均值聚类的图像分割方法

3.1 图像片的思想

图像片的思想来源于图像去噪领域中的一种非局部平均的图像去噪方法[3,4],其基本思想是利用图像的局部相似信息来代替单个像素点的相似信息。这里所谓的局部相似信息即图像片。图像片包含更多的图像信息,能够比单个像素点更好描述图像的特征,因此基于图像片的图像去噪方法能够更好地保持纹理等具有重复结构的特征。本文正是在借鉴这种方法的基础上,将图像片的思想用于聚类分割算法中,以图像片代替单个像素点,通过计算图像片与聚类中心的相似性,增加像素点与聚类中心的距离,虽然在一定程度上拉大了像素点与其所对应聚类中心的距离,但同时也大大增加了该点与其它聚类中心的距离,这样从整体看来,该方法可以使分类更加精确。另一方面,以片代点的思想,可以很好地克服单个像素点灰度值对于分类的绝对影响,即克服噪声的影响,从而达到抗噪目的。本文正是使用图像片来代替单个像素点,通过计算图像片与聚类中心之间的欧氏距离,来计算该片中心点的隶属度,达到对该点进行分类的目的。

3.2 本文算法

本文将图像片代替像素点的思想用于聚类分割,提出了基于图像片的模糊C均值聚类(IPFCM)方法。

令I:Ω→Rn为定义在连续域Ω奂R2上的二维图像,当n=1时,表示灰度图像;当n=3时,表示彩色图像。本文以灰度图像为例进行介绍。

令片PI(x,y)为定义在图像I中的点(x,y)∈Ω上的以(x,y)为中心的q×q邻域中所有像素灰度值的集合。其中邻域窗口长度q=2r+1为奇数,r∈N*为邻域窗口半径。将片PI(x,y)排列成q2维的向量

即图像中的每一个像素点都对应一个q2维的向量。这对应的目标函数为:

其中,U={uik}∈RN×c为隶属度矩阵,V=(v1,v2,…,vc)为c个聚类中心的集合,N为图像中总像素数,m∈[1,∞]为加权指数,取值与FCM相同。d∧ik=|PkI-vi|A表示第k个图像片到第i类中心vi的距离,由于片PkI为一个向量,可以采用两种方式来计算该距离,一是用向量均值,二是用向量总和,为了提高计算速度,本文采用向量均值来计算该距离:

函数具有单峰值性,其中。

现只考虑单个图像片PkI,令uij,i∈{1,…,c},k∈{1,…,N}为当前图像片所属类对应的隶属度。推导过程中使用m=2,根据Lagrange乘子寻优算法有:

进一步可得到:

通过式(16)可以看出,本文方法可以很好的控制隶属度函数的单峰值性,如图1(c)所示,从中发现本文的隶属度函数分布与理想分布十分接近,这就很好的克服了FCM方法中非单峰值的特点,进而保证了聚类的精确性。聚类中心集合V的更新如下:

均值。

3.3 算法流程

本文算法具体流程如下:

步骤一:初始化参数,设置m=2,ε=0.01,c初始化聚类中心集合V。一般而言,对于灰度图像,在0到255的范围内随机生成c个整数,作为V的初始值,并通过更新达到最佳聚类中心值;

步骤二:设置图像片邻域窗口半径r,并根据公式(9)将图像中每一个像素点扩展为q2维的向量,其中q=2r+1;

步骤三:根据公式(16)更新隶属度矩阵U;

步骤四:根据公式(17)更新聚类中心V;

步骤五:比较更新前后的聚类中心,如果|Vnew-Vold|<ε,则停止迭代输出结果图像;否则回到步骤三继续更新迭代。

4. 实验结果

首先讨论图像片半径的选取,再对人工合成灰度图像不同方法的实验结果进行定量比较;最后对医学图像进行实验。

4.1 图像片大小的选择

与FCM相比,本文唯一的额外参数为图像片半径r的设置。r越大,聚类分割的抗噪性越强,但在增加算法时间复杂度的同时容易造成图像边缘点的误分类;r越小,虽然提高了图像的分割精度,减小了算法的时间复杂度,却是以牺牲抗噪性为代价的。如图2所示,第一行为噪声较小的不同图像片半径的分割结果;第二行为噪声较大的不同图像片半径的分割结果。图2中,对于噪声较小的图像而言,r=1的图像片克服图像中噪声影响的同时,很好的保持了图像边缘,在区域的交界处误分类点数很少,随着的增大,区域交界处愈加的不平滑,r=3时图像区域交界处甚至出现了“过渡区域”。当图像噪声较大时,r=1的图像片的抗噪效果明显不如r=3的图像片,但是r=3时图像区域交界处出现“过渡区域”,这将导致分割精度的大幅度降低。对于实际图像而言,虽然噪声是不可避免的,但其强度相对较低,同时结构比较复杂,图像各个区域交界处较多,因此一般采用r=1的图像片来进行处理。

图3显示了本文方法不同图像片大小的图像分割结果。图像来源于BrainWeb1,原图为加噪9%的MR脑图像。对比实验显示出,随着图像片半径的增大,分割结果变得更为平滑,灰质与白质的边缘部分细节丢失更为严重。

本文对MR图像的分割精度进行了定量分析。目前,已有很多种图像分割精度的评判标准,本文采用较常用的两种方法:JS(Jaccard similarity)方法[8]和DC(Dice coefficient)方法[8],其度量公式依次为:

(18)、(19)式中,S1,S2表示需要比较的两幅分割结果,这里使用分类分割后的结果与BrainWeb中的人工分割结果进行比较。|誗|表示相应区域中的像素点个数。这里采用公式(18)对图3的分割结果进行精度计算,如表1所示。通过表1的定量分析证明了上述现象。尽管很好的克服了噪声的影响,但是图像分割精度过差,r越大分割精度也就越低,无法满足实际需要。当r=0时,此时的IPFCM方法退化为FCM方法,分割图像的细节能够得到较好的保持,但对于噪声的敏感性是无法避免的,这也是FCM本身无法克服的缺陷。从实验结果可以看出,r=1的图像片处理结果无论在分割精度、细节保持还是克服噪声方面,都具有很好的效果。

实验过程中,基本参数设定为:m=2,ε=0.01,所有聚类方法均使用半径r=1的窗口,人工合成图像中c=3,医学图像中c=4,聚类中心则根据c的大小随机生成相应的聚类中心集。

4.2 合成图像

图4为各个聚类方法的分割结果比较。该图像来自IBSR,选用256*256大小的带噪图像对FCM、BCFCM、EnFCM、FGFCM、MFGFCM、IPFCM这六种方法进行方法比较。其中,只有FCM与IPFCM不需要额外的参数设定,BCFCM、EnFCM、FGFCM、MFGFCM均需要一个或几个控制参数,这些参数的设定并非本文重点,这里不一一列举。图4中,FCM方法对于噪声的敏感显而易见,BCFCM不仅无法达到满意的抗噪结果,其效率也十分低下,运行开销较大;EnFCM与FGFCM方法虽然比较地好提高了运行速度,但是分割结果还是可以看到该方法无法消除的部分噪声;从结果来看,MFGFCM与IPFCM的抗噪性最好,细节上本文方法要优于MFGFCM。

对于合成图像的分割精度计算,采用如下公式:

计算结果如表2所示。通过表2的对比,在相同噪声的情况下,IPFCM的分割精度最高。这些噪声图像都是在图4(a)的原图基础上增加不同的噪声,其中,Gaussian1、Gaussian2、Gaussian3都是均值为0,方差依次为0.01、0.03、0.05的高斯白噪声;Impluse为椒盐噪声;Mixed1、Mixed2分别为方差为0.04、0.08的混合噪声。

由于噪声强度问题,以上分析只能体现出MFGFCM与IPFCM拥有较好的抗噪性,但两者之间的比较不够突出,图5使用了另外一幅合成图像,从中明显可以看出IPFCM的抗噪性明显优于MFGFCM。

4.3 MR脑图像

本文对核磁共振(MR)图像使用EnFCM、MFGFCM、IPFCM三种方法在不同噪声水平下的分割结果进行比较。由于本文是针对聚类方法提出的新思想,而不是针对脑图像应用,没有加入MR脑图像去偏移场的计算,因此本文选用T1模态1mm切片厚度无偏移场的不同噪声水平下的脑图片,图6第一列的三幅图像分别为加噪0%、3%、9%的第96针脑图像,其分割结果如图6第二至第四列图像所示。

通过EnFCM、MFGFCM、IPFCM三种方法的比较,还是可以看出IPFCM在抗噪方面是最好的。

表3列出了图6中各种方法分割后灰质、白质的分割精度。通过定量分析得出在克服噪声影响的同时IPFCM在同类方法中的分割精度较高,且无需过多参数设定,具有较强的可靠性。

以上多组不同类型的实验,对IPFCM进行了全面的分析,不仅表明了IPFCM的有效性和精确性,同时还对图像片半径的选择进行了讨论。一般情况下,建议设置半径为r=1。4.1中的实验表明图像片窗口越大,IPFCM的抗噪性就越强,但是边缘模糊现象就越明显。4.2和4.3中的实验显示,当图像片半径为时,无论合成图像还是MR脑图像,IPFCM都可以得到较高的分割精度,因此图像片半径为具有很强的适用性。

5. 结论

本文提出一种全新的基于图像片进行模糊C均值聚类的图像分割理念与IPFCM方法,通过实验对比发现,IPFCM很好地克服了FCM分割方法对于噪声的敏感以及隶属度函数的非单峰值的缺陷,具有很好的抗噪性和较高的分割精度,图像的隶属度函数与理想隶属度函数十分接近。与同类方法相比,IPFCM不需要过多的参数设定,具有很好的鲁棒性和较强的可靠性。同时,本文将聚类中心的每一个成员扩展为一个向量,并给出了向量聚类中心的更新公式,为日后将多种图像特征加入FCM对图像进行分割提供了充分的理论基础。需要指出的是,本文采用正方形图像片,并未将图像像素点的方向信息考虑进去,使得图像细节部分容易被起周边像素影响而丢失信息。另一方面,当使用半径较大的图像片时,将会不可避免的降低分割精度,可以对分割后的图像进行二次聚类以提高分割精度。如何在图像片中加入方向信息,以及引入哪些图像特征将是未来研究工作的重点。

参考文献

[1]J C Dunn.A fuzzy relative of the ISODATA process and its use in detecting compact well separated cluster[J].Journal of Cybemet,3:32～57,1974.

[2]J C Bezdek.Pattern recognition with fuzzy objective function algorithms[M].Norwell,MA,USA:Kluwer Academic Publishers,1981.

[3]A.Buades,B.Coll,and J.-M.Morel.A non-local algorithm for image denoising[J],Proc.IEEE Conf.Computer Vision and Pattern Recognition,vol.2,pp.60-65,Jun.2005.

[4]F.Hoppner,F.Klawonn.Improved fuzzy partitions for fuzzy regression models[J],Int.J.Approx.Reason.32(2)85-102,2003.

[5]MN Ahmed,SM Yamany,N Mohamed,AA Farag,Moriarty T.A modified fuzzy c-means algorithm for bias field estimation and segmentation of MRI data[J].IEEE Trans Med Imag21,193-199,2002.

[6]S Chen,DQ Zhang.Robust image segmentation using FCM with spatial constraints based on new kernel-induced distance measure[J].IEEE Trans Syst Man Cybern Part B34,1907-1916,2004.

[7]L Szilágyi,Z Benyó,SM Szilágyi,HS Adam.MR brain image segmentation using an enhanced fuzzy c-means algorithm[J].Proc25th Ann Int Conf IEEE EMBS,2003:724-726.

本文来自 99学术网(www.99xueshu.com)，转载请保留网址和出处

【均值模糊】相关文章：

基于一种动态颜色模型的模糊C-均值图像分割05-30

均值方差模型05-29

均值不等式06-24

K均值算法06-25

均值聚类分割07-03

年日均值合并成EIS2000文件格式程序11-25