发布时间: 2017-02-25
摘要点击次数:
全文下载次数:
DOI: 10.11834/jig.20170206
2017 | Volumn 22 | Number 2

图像分析和识别

核空间广义均衡模糊C-均值聚类算法

杜朵朵, 吴成茂

西安邮电大学电子工程学院, 西安 710121

收稿日期: 2016-06-02; 修回日期: 2016-10-09

基金项目: 国家自然科学基金重点项目(61136002)；陕西省教育厅科学研究计划资助项目(2015JK1654)；陕西省自然科学基金项目(2014JM8331，2014JQ5138，2014JM8307)；研究生创新基金项目(CXL2015-03)

第一作者简介: 杜朵朵(1992-),女,西安邮电大学电子通信工程专业硕士研究生,主要研究方向为图像分割。E-mail:568931247@qq.com

中图法分类号: TP391.41

文献标识码: A

文章编号: 1006-8961(2017)02-0188-09

摘要

目的针对现有广义均衡模糊C-均值聚类不收敛问题，提出一种改进广义均衡模糊聚类新算法，并将其推广至再生希尔伯特核空间以便提高该类算法的普适性。方法在现有广义均衡模糊C-均值聚类目标函数的基础上，利用Schweizer T范数极限表达式的性质构造了新的广义均衡模糊C-均值聚类最优化目标函数，然后采用拉格朗日乘子法获取其迭代求解所对应的隶属度和聚类中心表达式，同时对其聚类中心迭代表达式进行修改并得到一类聚类性能显著改善的修正聚类算法；最后利用非线性函数将数据样本映射至高维特征空间获得核空间广义均衡模糊聚类算法。结果对Iris标准文本数据聚类和灰度图像分割测试表明，提出的改进广义均衡模模糊聚类新算法及其修正算法具有良好的分类性能，核空间广义均衡模糊聚类算法对比现有融入类间距离的改进模糊C-均值聚类(FCS)算法和改进再生核空间的模糊局部C-均值聚类(KFLICM)算法能将图像分割的误分率降低10%30%。结论本文算法克服了现有广义均衡模糊C-均值聚类算法的缺陷，同时改善了聚类性能，适合复杂数据聚类分析的需要。

关键词

广义均衡模糊C-均值聚类; 核空间; Schweizer T范数; 图像分割; 误分率; 聚类性能

Improvement of general equalization fuzzy C-means clustering and its kernel spaces algorithm

Du Duoduo, Wu Chengmao

School of Electronic Engineering, Xi'an University of Posts and Telecommunication University, Xi'an 710121, China

Supported by: The State Key Program of National China(61136002);Natural Science Foundation of Shaanxi Province,China(2014JM8331,2014JQ5138,2014JM8307)

Abstract

Objective A new general equalization fuzzy C-means clustering algorithm that targets the shortcomings of existing, non-convergent types is proposed and applied in image segmentation. The proposed general equalization fuzzy clustering algorithm is also extended into the Hilbert reproduced kernel space. This approach can improve the universality of this algorithm class. Method The limit expression properties of the Schweizer T-norm are applied to construct the objective function of the new general equalization fuzzy C-means clustering based on the objective function of existing types. The Lagrange multiplier method is then adopted to obtain iterated formulae of the fuzzy membership and clustering center for the modified general equalization fuzzy C-means clustering. The iterative expression of the clustering center is modified to further improve the performance of the clustering algorithm. The modified clustering algorithm significantly improves a clustering performance class. Finally, a nonlinear function is adopted to map data samples from the Euclidean space to the high-dimensional feature space of Hilbert. The kernel space general equalization fuzzy C-means clustering algorithm is thus obtained. The kernel spaces general equalization fuzzy C-means clustering algorithms can improve the error classification rate of image segmentation by 10% to 30% compared with existing fuzzy compactness and separation (FCS)and fuzzy C-means clustering with local information and kernel metric (KFLICM)algorithms. Resuls Experimental results of the clustering analysis of Iris data and gray image segmentation indicate that the proposed general equalization fuzzy C-means clustering algorithm is efficient. Its modified algorithm can obtain more satisfactory clustering quality and segmentation effects than existing fuzzy c-means clustering algorithms. Conclusion The proposed algorithm overcomes the shortcomings of existing general equalization fuzzy C-means clustering algorithms and improves the clustering performance, which is suitable for complex data analysis.

Key words

general equalization fuzzy C-means clustering; kernel spaces; Schweizer T-norm; image segmentation; error classification rate; clustering performance

0 引言

图像分割^[1-2]是图像处理到图像分析的关键步骤，长期以来备受相关学者高度重视。迄今，已涌现出大量图像分割理论^[3-4]和模型，其中模糊C-均值聚类^[5-6]是一种采用迭代法实现样本归类的快速且存储空间消耗较少的聚类算法，已成为解决图像分割问题最为实用的分割技术。但模糊C-均值聚类算法在进行图像分割时未考虑像素与其邻域像素之间的关系，不利于像素空间分布较为复杂的遥感和医学图像的分割。于是学者们提出结合空间邻域信息的模糊C-均值聚类算法^[7-11]，以及将像素点灰度与其邻域像素的均值、中值相结合的2维和3维直方图的模糊C-均值聚类算法^[12-13]，这类算法具有一定的抗噪性，但是对于目标和背景所占比例相差较为悬殊的图像不能获得满意的分割效果。文献[14]同时考虑样本类内紧致性和类间分散性，提出类内距离与类间聚类相结合的改进模糊C-均值聚类算法(FCS)，但其对背景较暗的图像无法获得满意的分割效果。希腊学者Krinidis等人^[15]提出了将像素与其邻域像素的灰度信息和空间信息相融合的自适应模糊局部C-均值聚类分割算法，该算法具有较强的鲁棒性，但无法收敛于局部极小值点^[16]。公茂果等人^[17]将文献[15]算法推广至再生希尔伯特空间并引入新的加权模糊因子，提出具有较强鲁棒性的核空间模糊局部C-均值聚类分割法(KFLICM)，该类算法^[18]对于复杂遥感和医学等图像能获得满意的分割效果，其存在的缺点是算法时间复杂性高，无法满足大幅面图像实时分割的需要。文献[19]将样本容量因素引入到FCM目标函数中，提出广义均衡模糊C-均值聚类(GEFCM)算法，该算法在模糊指数m>1时对类样本数量分布不均匀的数据集可有效聚类。文献[20]在文献[19]的基础上将模糊指数扩展为m=1提出均衡模糊C-均值聚类算法，并引入粒子群算法对模糊隶属度进行编码，克服了m>1的限制。

本文考虑到广义均衡模糊C-均值算法的有效性和稳健性，将其用于灰度图像分割，发现GEFCM算法产生的迭代序列并不收敛。在现有广义均衡模糊C-均值聚类目标函数的基础上，本文利用Schweizer T范数完整族^[21]极限表达式的性质构造了新的广义均衡模糊C-均值聚类目标函数获得广义均衡模糊聚类新算法及其修正算法，并对其欧氏空间距离推广至再生希尔伯特核空间，得到核空间广义均衡模糊C-均值聚类算法及其修正算法。大量图像分割实验表明，本文所建议的改进广义均衡模糊聚类新算法及其核空间算法是有效的，相比现有算法可获得更加良好的聚类效果。

1 广义均衡模糊C-均值聚类算法

模糊C-均值聚类算法只考虑样本与聚类中心的距离，距离越小隶属程度越高。未考虑各类样本容量差异，而实际问题中样本的分类受类样本容量大小影响，当各类样本容量差异较大时，聚类判决向小样本类倾斜，由此导致FCM的误判。文献[19]提出广义均衡模糊C均值聚类，在FCM目标函数式中引入样本容量信息，得到广义均衡模糊C-均值的目标函数为

$\min {{J}_{m}}(U,V)=\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{\frac{u_{ij}^{m}}{\sum\limits_{s=1}^{n}{u_{sj}^{m}}}}}d_{ij}^{2}$

(1)

满足约束条件

1) $\sum\limits_{j=1}^{c}{{{u}_{ij}}}=1,\forall i\in \{1,\cdots ,n\}$；

2) $\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{{{u}_{ij}}=\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{c}{{{u}_{ij}}=n}}}}$；

式中，n是总的样本数，c是聚类数目，m为模糊指数，且m>1，u_ij表示第i个样本属于第j类的隶属度，d_ij²为样本x_i与聚类中心v_j之间的欧氏距离平方；$\sum\limits_{s=1}^{n}{u_{is}^{m}}$表示第i类的样本容量，在目标函数中除以$\sum\limits_{s=1}^{n}{u_{is}^{m}}$以抵消各类内样本容量差异对分类判决的影响。

针对目标函数表达式(1) ，文献[19]采用拉格朗日乘数法得其隶属度u_ij和聚类中心v_j表达式为

${{u}_{ij}}=\frac{{{\left[ \frac{{{(\sum\limits_{s=1}^{n}{u_{sj}^{m}})}^{2}}}{(\sum\limits_{s=1}^{n}{u_{sj}^{m}-u_{ij}^{m}})||{{x}_{i}}-{{v}_{j}}|{{|}^{2}}} \right]}^{\frac{1}{m-1}}}}{\sum\limits_{r=1}^{c}{{{\left[ \frac{{{(\sum\limits_{s=1}^{n}{u_{sr}^{m}})}^{2}}}{(\sum\limits_{s=1}^{n}{u_{sr}^{m}}-u_{ir}^{m})||{{x}_{i}}-{{v}_{r}}|{{|}^{2}}} \right]}^{\frac{1}{m-1}}}}}$

(2)

${{v}_{j}}=\frac{\sum\limits_{i=1}^{n}{{{u}_{ij}}{{x}_{i}}}}{\sum\limits_{i=1}^{n}{{{u}_{ij}}}}$

(3)

2 改进广义均衡模糊聚类新算法及其修正算法

上述广义均衡模糊C-均值聚类算法利用拉格朗日乘子法得到模糊隶属度迭代式(2) ，正如文献[22]所述，由于式(2) 两边均含参量u_ij，使该算法收敛性受到影响，虽可获得良好的聚类分割结果，但无法收敛到全局最优解。故采用迭代算法迭代给定次数便终止算法执行，所获得的样本隶属度实现样本分类。

在保证其良好性能的前提下，提出改进广义均衡聚类新算法，其具体推导如下：

文献[21]中介绍T范数完整族的极限公式为

$\mathop {\lim }\limits_{\alpha \to 0} {(1 + {a^\alpha } - {b^\alpha })^{\frac{1}{\alpha }}} = \frac{a}{b}$

(4)

式中，α∈R且0<a<1,0<b<1,a<b。

结合原广义均衡模糊C-均值聚类的目标函数式(1) 中$\frac{u_{ij}^{m}}{\sum\limits_{s=1}^{n}{u_{sj}^{m}}}$有u_ij^m<1，为保证$\sum\limits_{s=1}^{n}{u_{sj}^{m}}$也小于1，分子分母同除n，即$\frac{u_{ij}^{m}}{\sum\limits_{s=1}^{n}{u_{sj}^{m}}}=\frac{u_{sj}^{m}/n}{\sum\limits_{s=1}^{n}{u_{sj}^{m}/n}}$。则利用上述极限式(4) ，构造参数型广义均衡模糊聚类目标函数为

$\begin{align} & {{J}_{\alpha }}(U,V)= \\ & {{\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{c}{\left( 1+{{\left( \frac{1}{n}u_{ij}^{m} \right)}^{\alpha }}-{{\left( \frac{1}{n}\sum\limits_{s=1}^{n}{u_{sj}^{m}} \right)}^{\alpha }} \right)}}}^{\frac{1}{\alpha }}}||{{x}_{i}}-{{v}_{j}}|{{|}^{2}} \\ \end{align}$

(5)

式(5) 中若α→0，为原广义均衡模糊C-均值聚类的目标函数式(1) ，若α=1，一种新的广义均衡模糊C-均值聚类的目标函数为

$\begin{align} & {{J}_{m}}(U,V)=\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{(1+\frac{1}{n}u_{ij}^{m}-\frac{1}{n}\sum\limits_{s=1}^{n}{u_{sj}^{m}})d_{ij}^{2}}}\text{=} \\ & \sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{d_{ij}^{2}}}+\frac{1}{n}\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{u_{ij}^{m}d_{ij}^{2}}}-\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{u_{sj}^{m}}}d_{ij}^{2} \\ \end{align}$

(6)

式中，$\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{d_{ij}^{2}}}\approx {{c}^{{{m}_{1}}}}\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}d_{ij}^{2}}}$，参数${m_1} \gg 10$，于是可得一种新的改进广义均衡模糊C-均值聚类的最优化问题描述为

$\begin{align} & \min {{J}_{m}}(T,U,V)\text{=} \\ & {{c}^{{{m}_{1}}}}\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{t_{ij}^{{{m}_{1}}}d_{ij}^{2}}}+\frac{1}{n}\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}d_{ij}^{2}}}-\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}d_{ij}^{2}}} \\ \end{align}$

(7)

满足约束条件

1) $\sum\limits_{j=1}^{c}{{{u}_{ij}}}=1,\sum\limits_{j=1}^{c}{{{t}_{ij}}}=1,\forall i\in \{1,\cdots ,n\}$；

2) 0≤u_ij≤1,0≤t_ij≤1,1≤i≤n,1≤j≤c；

3) $0\le \sum\limits_{i=1}^{n}{{{u}_{ij}}\le n}$,$0\le \sum\limits_{i=1}^{n}{{{u}_{ij}}}\le n$,1≤j≤c;

式中，m₁和m₂均为模糊指数，m₂同FCM取值范围常选取为[1.5,2.5]，但m₁应取较大值，具体可依靠大量实验反复验证或依据经验取值。t_ij同u_ij一样，仍为模糊隶属度。

针对最优化聚类问题式(7) ，采用拉格朗日乘数法构造无约束优化问题函数为

$\begin{align} & \min L(T,U,V)={{c}^{{{m}_{1}}}}\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{t_{ij}^{{{m}_{1}}}d_{ij}^{2}}}+\frac{1}{n}\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}d_{ij}^{2}}}- \\ & \sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}d_{ij}^{2}}}+\sum\limits_{i=1}^{n}{{{\lambda }_{i}}}(1-\sum\limits_{j=1}^{c}{{{u}_{ij}}})+\sum\limits_{i=1}^{n}{{{\zeta }_{i}}(1-{{t}_{ij}})} \\ \end{align}$

(8)

令$\frac{\partial L(T,U,V)}{\partial {{t}_{ij}}}=0$，$\frac{\partial L(T,U,V)}{\partial {{u}_{ij}}}=0$，$\frac{\partial T(T,U,V)}{\partial {{v}_{j}}}=0$和$\frac{\partial L(T,U,V)}{\partial {{v}_{j}}}=0$，于是获得其模糊隶属度t_ij,u_ij和聚类中心v_j为

${{t}_{ij}}=\frac{1}{\sum\limits_{j=1}^{c}{{{\left( \frac{{{d}^{2}}({{x}_{i}},{{v}_{j}})}{{{d}^{2}}({{x}_{i}},{{v}_{j}})} \right)}^{\frac{1}{{{m}_{1}}-1}}}}}$

(9)

${{u}_{ij}}=\frac{1}{\sum\limits_{j=1}^{c}{{{\left( \frac{{{d}^{2}}({{x}_{i}},{{v}_{j}})}{{{d}^{2}}({{x}_{i}},{{v}_{j}})} \right)}^{\frac{1}{{{m}_{2}}-1}}}}}$

(10)

${{v}_{j}}=\frac{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{t_{ij}^{{{m}_{1}}}{{x}_{i}}-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}{{x}_{i}}}}}{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{t_{ij}^{{{m}_{1}}}-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}}}}$

(11)

式(9) 中当${m_1} \gg 10$，则有${{t}_{ij}}\approx \frac{1}{c}$成立，故式(6) (7) 成立，因此m₁取值较大。

该算法可收敛到目标函数的最优解，且继承了原广义均衡聚类的良好性能。

在仿真实验测试中发现，若将聚类中心做些许调整，便可得到更好的聚类结果。将聚类中心修正为

${{v}_{j}}=\frac{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{1}}}{{x}_{i}}-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}{{x}_{i}}}}}{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{1}}}-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}}}}$

(12)

隶属度t_ij、u_ij的迭代更新公式保持不变，得到改进广义均衡模糊聚类修正算法。

原广义均衡模糊C-均值聚类的不收敛性证明，和本文改进广义均衡的收敛性证明由于篇幅有限省略。本文仅用图像分割的测试结果简要分析。

3 核空间广义均衡模糊C-均值聚类及其修正算法

考虑到基于核方法的聚类通过核函数把原始空间的点映射到高维特征空间中，在高维特征空间直接或间接地进行算法设计、分析与计算。经过核函数的映射，能使原来呈非凸数据变得更具有可分性，更好地实现样本分类。故本文将核函数引入改进广义均衡模糊聚类新算法，得到核空间广义均衡模糊C-均值聚类(KGEFCM)算法。假设输入空间的样本向量x_i∈R^P,i=1,2，…，n被某一非线性映射φ映射到某一特征空间R^P，从而得到φ(x₁),φ(x₂),…φ(x_n)。故将核广义均衡模糊C-均值聚类的最优化问题描述为

$\begin{align} & \min {{J}_{m}}(T,U,V)\text{=}{{c}^{{{m}_{1}}}}\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{t_{ij}^{{{m}_{1}}}||\phi ({{x}_{i}})-\phi ({{v}_{j}})|{{|}^{2}}}}\text{+} \\ & (\frac{1}{n}-1)\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}||\phi ({{x}_{i}})-\phi ({{v}_{j}})|{{|}^{2}}}} \\ \end{align}$

(13)

利用核函数性质‖φ(x)－φ(y)‖=K(x,x)-2K(x,y)+K(y,y)，以及核函数选取良好局部逼近能力的高斯函数K(x,y)=exp(－‖x－y²‖/σ²)，将最优化问题式(13) 转化为

$\begin{align} & \min {{J}_{m}}(T,U,V)\text{=}{{c}^{{{m}_{1}}}}\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{t_{ij}^{{{m}_{1}}}||1-K({{x}_{i}},{{v}_{j}})|{{|}^{2}}}}\text{+} \\ & (\frac{1}{n}-1)\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}||1-K({{x}_{i}},{{v}_{j}})|{{|}^{2}}}} \\ \end{align}$

(14)

式中，m为加权指数且m∈[1,∞]，m取得越大，所得的分类矩阵模糊程度越大，通常取值为[1.5,2.5]。

针对最优化聚类问题式(13) ，采用拉格朗日乘子法构造无约束优化问题函数为

$\begin{align} & \min L(T,U,V)={{c}^{{{m}_{1}}}}\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{t_{ij}^{{{m}_{1}}}||1-K({{x}_{i}},{{v}_{j}})|{{|}^{2}}+}} \\ & (\frac{1}{n}-1)\sum\limits_{j=1}^{c}{\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}||1-K({{x}_{i}},{{v}_{j}})|{{|}^{2}}}}\text{+} \\ & \sum\limits_{i=1}^{n}{{{\lambda }_{i}}(1-\sum\limits_{j=1}^{c}{{{u}_{ij}}})+\sum\limits_{i=1}^{n}{{{\zeta }_{i}}(1-\sum\limits_{j=1}^{c}{{{t}_{ij}}})}} \\ \end{align}$

(15)

令$\frac{\partial L(T,U,V)}{\partial {{t}_{ij}}}=0$,$\frac{\partial L(T,U,V)}{\partial {{u}_{ij}}}=0$,$\frac{\partial T(T,U,V)}{\partial {{v}_{j}}}=0$和$\frac{\partial L(T,U,V)}{\partial {{v}_{j}}}=0$，于是获得其模糊隶属度t_ij，u_ij和聚类中心v_j为

${{t}_{ij}}=\frac{1}{\sum\limits_{j=1}^{c}{{{\left( \frac{1-K({{x}_{i}},{{v}_{j}})}{1-K({{x}_{i}},{{v}_{j}})} \right)}^{\frac{1}{{{m}_{1}}-1}}}}}$

(16)

${{u}_{ij}}=\frac{1}{\sum\limits_{j=1}^{c}{{{\left( \frac{1-K({{x}_{i}},{{v}_{j}})}{1-K({{x}_{i}},{{v}_{j}})} \right)}^{\frac{1}{{{m}_{2}}-1}}}}}$

(17)

${{v}_{j}}=\frac{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{t_{ij}^{{{m}_{1}}}K({{x}_{i}},{{v}_{j}}){{x}_{i}}-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}K({{x}_{i}},{{v}_{j}}){{x}_{i}}}}}{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{t_{ij}^{{{m}_{1}}}K({{x}_{i}},{{v}_{j}})-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}K({{x}_{i}},{{v}_{j}})}}}$

(18)

同改进算法的修正算法类似，仅将其核空间广义均衡模糊C-均值聚类算法的聚类中心修正为

${{v}_{j}}=\frac{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{1}}}K({{x}_{i}},{{v}_{j}}){{x}_{i}}-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}K({{x}_{i}},{{v}_{j}}){{x}_{i}}}}}{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{1}}}K({{x}_{i}},{{v}_{j}})-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{u_{ij}^{{{m}_{2}}}K({{x}_{i}},{{v}_{j}})}}}$

(19)

便得到核空间广义均衡模糊聚类修正算法。

利用式(16)-(18) ,可设计最优化问题式(13) 的核空间广义均衡模糊C-均值迭代求解算法如下：

1) 设置迭代误差ε=0.001，分类数c，初始化聚类中心v_j⁽⁰⁾(j=1,2,…,c)；

2) 高斯核函数参数σ²的选取

${{\sigma }^{2}}=k\cdot \frac{1}{n-1}\sum\limits_{i=1}^{n}{{{(||{{x}_{i}}-\bar{x}|{{|}^{2}}-\bar{d})}^{2}}}$

(20)

式中,$\bar{x}=\frac{1}{n}\sum\limits_{i=1}^{n}{{{x}_{i}}}$，$\bar{d}=\frac{1}{n}\sum\limits_{i=1}^{n}{||{{x}_{i}}-\bar{x}|{{|}^{2}}}$，k为微量调节因子；

3) 利用式(16) (17) 计算隶属度t_ij和u_ij的迭代表达式为

$t_{ij}^{(t)}=\frac{1}{\sum\limits_{l=1}^{c}{{{\left( \frac{1-K({{x}_{i}},v_{j}^{(t)})}{1-K({{x}_{i}},v_{l}^{(t)})} \right)}^{\frac{1}{{{m}_{1}}-1}}}}}$

(21)

$u_{ij}^{(t)}=\frac{1}{\sum\limits_{j=1}^{c}{{{\left( \frac{1-K({{x}_{i}},v_{j}^{(t)})}{1-K({{x}_{i}},v_{j}^{(t)})} \right)}^{\frac{1}{{{m}_{2}}-1}}}}}$

(22)

4) 利用式(18) 计算聚类中心的迭代表达式为

$\begin{align} & v_{j}^{(t+1)}= \\ & \frac{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{{{(t_{ij}^{(t)})}^{{{m}_{1}}}}K({{x}_{i}},{{v}_{j}}){{x}_{i}}-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{{{(u_{ij}^{(t)})}^{{{m}_{2}}}}K({{x}_{i}},{{v}_{j}}){{x}_{i}}}}}{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{{{(t_{ij}^{(t)})}^{{{m}_{1}}}}K({{x}_{i}},{{v}_{j}})-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{{{(u_{ij}^{(t)})}^{{{m}_{2}}}}K({{x}_{i}},{{v}_{j}})}}} \\ \end{align}$

(23)

5) 迭代次数增1，t=t+1；

6) 若‖v_j^(t)－v_j^(t+1)‖<ε，则算法终止。

核空间广义均衡模糊聚类修正迭代算法步骤同上述KGEFCM算法步骤一致，仅将步骤4) 中聚类中心的迭代表达式(23) 替换为

$\begin{align} & v_{j}^{(t+1)}= \\ & \frac{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{{{(u_{ij}^{(t)})}^{{{m}_{1}}}}K({{x}_{i}},{{v}_{j}}){{x}_{i}}-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{{{(u_{ij}^{(t)})}^{{{m}_{2}}}}K({{x}_{i}},{{v}_{j}}){{x}_{i}}}}}{{{c}^{{{m}_{1}}}}\sum\limits_{i=1}^{n}{{{(u_{ij}^{(t)})}^{{{m}_{1}}}}K({{x}_{i}},{{v}_{j}})-(1-\frac{1}{n})\sum\limits_{i=1}^{n}{{{(u_{ij}^{(t)})}^{{{m}_{2}}}}K({{x}_{i}},{{v}_{j}})}}} \\ \end{align}$

(24)

4 实验测试

为了验证本文核空间广义均衡模糊聚类算法及其修正算法的可行性和有效性。选取测试平台为Dell Optiplex 360(Intel Core ，内存4 GB)Windows XP 系统，Matlable 7.0 编程环境。采用传统模糊C-均值聚类(FCM)，核空间模糊C-均值聚类(KFCM)，改进广义均衡模糊C-均值聚类，核空间广义均衡模糊C-均值聚类(KGEFCM)及其修正算法对灰度图像和标准Iris文本数据集进行聚类测试。模糊指数m₁、m₂取值范围分别为[10,100],[1.5,2.5]，迭代误差ε=0.000 1。

4.1 灰度图像分割测试

大量灰度图像分割测试表明本文建议的算法是有效可行的。限于篇幅有限仅给出部分图像的分割测试结果。

4.1.1 改进广义均衡模糊聚类及其修正算法的图像分割测试

针对改进广义均衡模糊聚类及其修正算法，本部分选取图 1所示的经典灰度图分2类进行分割测试，测试结果如图 2所示。

图 1 原图

Fig. 1 Original images ((a)watch; (b)block;(c)electric pile)

图 2 不同分割算法分2类分割结果

Fig. 2 Segmentation result of different segmentation methods ((a)FCM algorithm; (b)GEFCM algorithm; (c)improved algorithm; (d)modified algorithm)

图 2所示分割结果中，图 2 (b)(c)相比图 2 (a)均可有效提取目标，且分类准确，说明改进算法可获得与原GEFCM相仿的分割结果，且分割性能均优于传统FCM算法。但原GEFCM算法聚类中心振荡，需设置迭代次数t=30强制其停止迭代，而改进算法稳定收敛，无需设置迭代次数t便可得到有效停止迭代；修正算法对图像的分割性能最佳，如图 2 (d)可清晰地将目标从背景中分割出来，且图像区域一致性和边缘准确性较好。

为了进一步说明改进算法的有效性，选取图 3所示的灰度图像分3类进行分割测试，测试结果如图 4所示。

图 3 原图

Fig. 3 Original images ((a) printed circuit; (b) Lena; (c) little ship)

图 4 不同分割算法分3类分割结果

Fig. 4 Segmentation result of different segmentation methods ((a)FCM algorithm; (b)GEFCM algorithm; (c)improved algorithm; (d)modified algorithm)

图 4所示分割结果中，原GEFCM算法需设置迭代次数t=30强制使其停止迭代，且由于聚类中心振荡，无法将图像分成3类如图 4(b)所示，进一步说明原广义均衡模糊C-均值聚类算法不收敛；改进算法可将灰度图像分为3类如图 4(c)所示，分割效果较为满意，但无法提取复杂图像的小目标信息，如小船图像的分割；修正算法得到的分割结果最为满意，接近理想分割。故对改进算法进行修正是必要且可行的。

4.1.2 核空间广义均衡模糊聚类及其修正算法的图像分割测试

为了全面准确地评价本文核空间广义均衡模糊C-均值聚类算法的有效可行性，本部分测试首先选取图 5所示的经典灰度图像分2类进行分割测试，测试结果如图 6所示；其次选取图 7所示的复杂遥感图像分2类进行分割测试，测试结果如图 8所示；最后选取图 9所示的医学图像分3类进行分割测试，测试结果如图 10所示。

图 5 原图

Fig. 5 Original images ((a)coins; (b)woman; (c)anmail)

图 6 不同分割算法分割结果

Fig. 6 Segmentation result of different segmentation methods ((a)KFCM algoritnm; (b)improved algorithm of kernel spaces; (c)correction algorithm of kernenl spaces)

图 7 原图

Fig. 7 Original images ((a) CT slices 1; (b) sculpture; (c) CT slices 2)

图 8 不同分割算法分割结果

Fig. 8 Segmentation result of different segmentation methods ((a)KFCM algoritnm; (b)improved algorithm of kernel spaces; (c)correction algorithm of kernenl spaces)

图 9 原图

Fig. 9 Original images((a)remote 1; (b)remote 2; (c)remote 3)

图 10 不同分割算法分割结果

Fig. 10 Segmentation result of different segmentation methods ((a)KFCM algoritnm; (b)improved algorithm of kernel spaces; (c)correction algorithm of kernenl spaces)

对比图 6和图 8所示3种算法对经典图像的分割结果，3种算法均可有效准确分割图像，但本文核空间广义均衡模糊C-均值聚类算法及其修正算法，如图 6和图 8中的子图(b)(c)对比子图(a)却保留更图像细节信息；由于核空间修正算法因迭代步骤与KGEFCM算法基本一致，但分割结果更接近理想分割，故可作为KGEFCM的补充算法。

图 10中对复杂遥感图像的分割结果表明，本文核空间广义均衡模糊C-均值聚类及其修正算法，能提取遥感图像中的河流、城市交通轨道等小目标，如图 10(b)(c)所示；KFCM算法仅适合类样本相差不悬殊情形，对小目标图像无法获取真实目标，如图 10(a)所示，不利于战场飞机、导弹、舰船等小目标跟踪识别需要。

4.2 标准Iris文本数据测试

为了进一步说明本文核空间广义均衡模糊C-均值聚类算法及其修正算法的有效性，选取标准Iris文本数据采用传统FCM、KFCM算法和本文算法进行聚类测试，高斯核函数取值相同。列出各算法的误分率如表 1所示。

表 1 不同算法对Iris数据集的误分率
Table 1 Misclassification rate of different segmentation methods

下载CSV

FCM算法	改进GEFCM算法	修正算法	KFCM算法	KGEFCM算法	KGEFCM修正算法
10%	8%	3%	6%	6%	3%

从不同分割算法对Iris数据集的误分率开看，本文KGEFCM修正方法作为KGEFCM的补充方法具有良好的聚类性能，故对KGEFCM算法的修正是必要且可行的。

4.3 不同分割方法性能评价

为了用更直观的数值指标将聚类算法的分割效果表示出来，本部分引入误分率这一性能评价指标进行定量化分析。误分率即错误分割的像素个数占整幅理想图像所有像素个数的百分比。其表达式为

$r=\frac{1}{2}\frac{\sum\limits_{q=1}^{c}{|{{m}_{q}}-{{n}_{q}}|}}{\sum\limits_{q=1}^{c}{|{{n}_{q}}|}}$

(25)

式中，n_q为理想分割图像中属于标号q区域的像素个数，q=1,2,…,c，共有c个类别；m_q为分割结果中属于标号q区域的像素个数。

若图像的分割误分率低，表明图像的区域一致性和边缘准确性也很好，分割结果与理想分割结果越接近即分割效果越好。反之，误分率越高，则分割结果与理想分割结果差异越大，同时图像区域一致性和边缘准确率较低即分割效果越差。原图及分割结果如图 11、图 12所示。

图 11 原图

Fig. 11 Original images ((a) remote 4; (b) cells; (c) gear)

图 12 不同分割算法分割结果

Fig. 12 Segmentation result of different segmentation methods ((a)FCS algorithm ^[14]; (b)KFLICM algorithm^[17]; (c)improved algorithm of kernel spaces)

图 12的分割结果表明，本文和空间广义均衡模糊C-均值聚类算法对比其他两种算法分割效果最佳。另外，表 2所示不同分割方法的误分率来看，本文核空间广义均衡模糊C-均值聚类算法的误分率远低于其他两种算法。因此本文核空间广义均衡模糊C-均值聚类算法对比文献[14]、文献[17]算法具有更好的分类性能，有利于复杂场景目标提取。

表 2 不同分割算法的误分率评价
Table 2 Misclassification rate of different segmentation methods

下载CSV

/%
图像	FCS算法	KFLICM算法	核空间改进法
遥感图 4	43.51	41.22	8.12
细胞图	15.43	17.56	5.14
齿轮图	37.32	41.17	7.33

5 结论

在现有广义均衡模糊C-均值聚类算法目标函数的基础上，利用Schweizer T范数极限表达式的性质构造了新的广义均衡模糊C-均值聚类目标函数得到改进广义均衡模糊聚类新算法及其修正算法，并将其推广至再生希尔伯特核空间，得到核空间广义均衡模糊聚类算法及其修正算法。灰度图像分割和Iris文本数据集聚类测试结果均表明本文建议算法是有效可行的。该改进广义均衡模糊聚类新算法相比传统模糊C-均值聚类算法和广义均衡模糊聚类算法具有更好的聚类性能，特别适合不同类样本数不均衡的多类团状数据聚类需要，相应的核空间广义均衡模糊聚类算法及其修正算法相比核空间模糊C-均值聚类算法更适合非凸多类且类样本数相差很悬殊的数据集聚类需要，其具体表现为图像中小目标聚类采用本文建议算法更有效。另外，本文改进广义均衡模糊聚类算法，以及核空间相应算法对噪声干扰数据的聚类缺乏鲁棒性，后续将借鉴现有鲁棒模糊聚类算法的研究成果，开展鲁棒改进广义均衡模糊聚类系列算法研究，以便对噪声干扰图像的目标提取具有良好的分割性能。

参考文献

[1] Thakur E P, Madaan E N. A survey of image segmentation techniques[J]. International Journal of Research in Computer Application and Robotics , 2014, 2 (4) : 158–165.

[2] Kandwal R, Kumar A, Bhargava S. Review:existing image segmentation techniques[J]. International Journal of Advanced Research in Computer Science and Software Engineering , 2014, 4 (4) : 153–156.

[3] Aqil Burney S M, Tariq H. K-means cluster analysis for image segmentation[J]. International Journal of Computer Applications , 2014, 96 (4) : 1–8. DOI:10.5120/16779-6360

[4] Khan A M, Ravi S. Image segmentation Methods:a comparative study[J]. International Journal of Soft Computing and Engineering , 2013, 3 (4) : 84–92.

[5] Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. New York: Plenum Press, 1981 : 95-107.

[6] Huang K Y. Applications of an enhanced cluster validity index method based on the Fuzzy C-means and rough set theories to partition and classification[J]. Expert Systems with Applications , 2010, 12 (37) : 8757–8769. DOI:10.1016/j.eswa.2010.06.032

[7] Ahmed M N, Yamany S M, Mohamed N, et al. A modified fuzzy C-means algorithm for bias field estimation and segmentation of MRI data[J]. IEEE Transactions on Medical Imaging , 2002, 21 (3) : 193–199. DOI:10.1109/42.996338

[8] Li Y L, Shen Y. Fuzzy c-means clustering based on spatial neighborhood information for image segmentation[J]. Journal of Systems Engineering and Electronics , 2010, 21 (2) : 323–328. DOI:10.3969/j.issn.1004-4132.2010.02.024

[9] Beevi S Z, Sathik M M, Senthamaraikannan K, et al. A Robust fuzzy clustering technique with spatial neighborhood information for effective medical image segmentation:An efficient variants of fuzzy clustering technique with spatial information for effective noisy medical image segmentation[C]//Proceedings of 2010 International Conference on Computing Communication and Networking Technologies. Karur:IEEE, 2010:1-8.DOI:10.1109/ICCCNT.2010.5591787

[10] Wang Z M, Song Q, Soh Y C, et al. An adaptive spatial information-theoretic fuzzy clustering algorithm for image segmentation[J]. Computer Vision and Image Understanding , 2013, 117 (10) : 1412–1420. DOI:10.1016/j.cviu.2013.05.001

[11] Zhong Y F, Ma A L, Zhang L P. An adaptive memetic fuzzy clustering algorithm with spatial information for remote sensing imagery[J]. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing , 2014, 7 (4) : 1235–1248. DOI:10.1109/JSTARS.2014.2303634

[12] Liu J Z. A fuzzy clustering method for image segmentation based on two-dimensional histogram[J]. Acta Electronica Sinica , 1992, 20 (9) : 40–46. [ 刘健庄. 基于二维直方图的图象模糊聚类分割方法[J]. 电子学报 , 1992, 20 (9) : 40–46. ]

[13] Zhou X C, Shen Q T, Liu L M. New two-dimensional fuzzy C-means clustering algorithm for image segmentation[J]. Journal of Central South University of Technology , 2008, 15 (6) : 882–887. DOI:10.1007/s11771-008-0161-1

[14] Wu K L, Yu J, Yang M S. A novel fuzzy clustering algorithm based on a fuzzy scatter matrix with optimality tests[J]. Pattern Recognition Letters , 2005, 26 (5) : 639–652. DOI:10.1016/j.patrec.2004.09.016

[15] Krinidis S, Chatzis V. A robust fuzzy local information C-means clustering algorithm[J]. IEEE Transactions on Image Processing , 2010, 19 (5) : 1328–1337. DOI:10.1109/TIP.2010.2040763

[16] Celik T, Lee H K. Comments on "a robust fuzzy local information c-means clustering algorithm"[J]. IEEE Transactions on Image Processing , 2013, 22 (3) : 1258–1261. DOI:10.1109/TIP.2012.2226048

[17] Gong M G, Liang Y, Shi J, et al. Fuzzy C-means clustering with local information and kernel metric for image segmentation[J]. IEEE Transactions on Image Processing , 2013, 22 (2) : 573–584. DOI:10.1109/TIP.2012.2219547

[18] Xiang D L, Tang T, Hu C B, et al. A kernel clustering algorithm with fuzzy factor:application to SAR image segmentation[J]. IEEE Geoscience and Remote Sensing Letters , 2014, 11 (7) : 1290–1294. DOI:10.1109/LGRS.2013.2292820

[19] Wen C J, Zhan Y Z, Ke J. General equalization fuzzy C-means clustering algorithm[J]. Systems Engineering-Theory & Practice , 2012, 32 (12) : 2751–2755. [ 文传军, 詹永照, 柯佳. 广义均衡模糊C均值聚类算法[J]. 系统工程理论与实践 , 2012, 32 (12) : 2751–2755. DOI:10.3969/j.issn.1000-6788.2012.12.022 ]

[20] Wen C J, Wang Q M, Zhan Y Z. Equalization fuzzy C-means clustering algorithm[J]. Computer Science , 2014, 41 (8) : 250–253. [ 文传军, 汪庆淼, 詹永照. 均衡模糊C均值聚类算法[J]. 计算机科学 , 2014, 41 (8) : 250–253. DOI:10.11896/j.issn.1002-137X.2014.08.053 ]

[21] Gu M Q, Li H X, Wang J L. Fuzzy controllers based on the solutions of fuzzy relation equations[J]. Journal of Beijing Normal University:Natural Science , 2007, 43 (2) : 132–139. [ 谷敏强, 李洪兴, 王杰亮. 基于模糊关系方程组的解构造的模糊控制器[J]. 北京师范大学学报:自然科学版 , 2007, 43 (2) : 132–139. DOI:10.3321/j.issn:0476-0301.2007.02.005 ]

[22] Wang Q M. Research of new fuzzy clustering algorithms based on objective function and its applications[D]. Zhenjiang:Jiangsu University, 2014. [汪庆淼. 基于目标函数的模糊聚类新算法及其应用研究[D]. 镇江:江苏大学, 2014.] http://cn.bing.com/academic/profile?id=5780b2692e49fdaf5712b8579f8c4d96&encoded=0&v=paper_preview&mkt=zh-cn

摘要

关键词