核方法聚类范文

核方法聚类范文（精选7篇）

核方法聚类 第1篇

彩色图像分割方法可归纳为：直方图阈值法、特征空间聚类、基于区域的方法、边缘检测方法、模糊方法、神经元网络方法等。模糊c均值(FCM)聚类[1]用于彩色图像分割具有简单直观、易于实现的特点，但存在聚类性能受中心点初始化影响且计算量大等问题，限制了其在彩色图像分割的使用。而且目前已有的聚类算法只能对一些典型分布的样本奏效，比较经典的聚类方法如传统的kmeans方法和模糊C-均值聚类方法等都没有对样本的特征进行优化，而是直接利用样本的特征进行聚类。Girolam[2]等引入核方法输入空间的数据非线性映射到高维特征空间，增加了数据点的线性可分概率，即扩大数据类之间的差异，在高维特征空间达到线性可聚的目的，从而提高聚类的质量。近年来对核聚类的积极研究，涌现了许多基于核的聚类算法，诸如支持向量聚类，基于核的模糊聚类算法[3]，而谢维信等人提出了模糊核聚类算法(KFCM)[4]。小波变换的多分辨率特性也被应用到纹理分割和图像分割中[5]。

本文将核方法与密度函数结合的核密度函数聚类方法用于彩色图像分割聚类的数目数目上限的确定和模糊核聚类聚类中心的初始化，用模糊核聚类进行图像分割，并利用小波变换的多分辨率特性，实现多分辨率的彩色图像分割以减少计算量。

2 基于核的聚类

2.1 减法聚类

减法聚类[1]算法是把所有的数据点作为聚类中心的候选点，它是一种快速而独立的近似聚类方法，计算量与数据点的数目成简单的线性关系，而且与考虑问题的维数无关。

令是样本点，n是样本的个数，由于每个数据点都是聚类中心的候选点，因此数据点xi的密度指标定义为

参数γa是一个正数。如果一个数据点有多个邻近的数据点，则该数据具有高密度值。γa表示邻域半径，邻域以外的数据对密度指标的贡献很小。

在计算每个数据点的密度指标后，选择具有最高密度指标的数据点作为第一个聚类中心，令xc1为选中的点，Dc1其密度指标，则每个数据点的密度指标修改为

γb是一个正数。接近第一个聚类中心的数据点的密度指标显著减小，γb定义了一个密度指标函数显著减小邻域。

修正了所有数据点的密度指标后，选定下一个密度最高点作为下一个聚类中心，再次修正数据点所有的密度指标，不断重复此过程直到产生足够的聚类中心。

2.2 基于密度函数的聚类方法

但是上述方法是以指数运算为基础的，对于大样本的情况包括图像分割的情况会影响计算速度，裴继红[6]等提出了一种基于密度函数的聚类方法。

定义样本点在xi的密度函数如下：

其中

其中rd可以取上公式1、2，是邻域密度有效半径。由公式3，在xi周围样本点越密集，则Di值越大，故可以用来表示在样本空间中样本点的密集程度。与减法聚类算法相似，令D1*=max{Di,i=1,n}，对应的x1*取为第1个初始聚类中心，求后续初始聚类中心的密度调整关系式为

其中Dk*=max{Di,i=1,n}，对应得样本点xk*取为第k个初始聚类中心位置。由上式确定决定的中心初始化方法，其原理与减法聚类方法相似，但是运算量却小很多。

裴继红等人给出了γa、γb一种确定的方法，即取

其中n为数据集合的样本数目，max{}、min{}是集合求大求小函数。γf表示处于样本集合最中间的样本到距离它最远的样本的距离的二分之一，γm表示的是n个样本的均方根距离的二分之一。

但是可以看到减法聚类和密度函数算法是以样本之间的距离为基础构造的，故比较适合于对样本空间中呈团状分布的集合进行初始化，对诸如线状和椭球壳状等的数据样本集要做进一步的修改。由于基于密度函数聚类方法是一种非迭代优化算法，因此计算量比模糊C均值算法小，运算时间也较FCM算法少。

2.3 基于核方法的密度函数聚类

核方法利用Mercer核把输入空间样本映射到特征空间，使得映射后的样本具有更好的聚类形式。本文将核方法引入到密度函数聚类，形成了基于核方法的密度函数聚类。

假设输入空间的样本，被某种非线性映射Φ映射到某一特征空间H得到Φ(x1)，Φ(x2)，，Φ(xl)，那么输入空间的点积形式在特征空间就是可以用Mercer核来表示为

引入核方法后得到样本的非线性映射为Φ:xΦ(x)，样本点在xi的密度函数如下：

‖Φ(xi)-Φ(xj)‖2为Φ(xi)与Φ(xj)之间的距离。因而Di表示特征空间中xi与xj的相似程度。特征空间下其距离计算公式为

后续初始聚类中心的密度关系式调整为

其实现过程如下：

Step1:首先对样本集合X中的每一个点xi计算出其核密度指标选取密度指标最高Dc1=max{Di,i=1,,n}的数据点xc1作为第一个聚类中心。

Step2：假定xck为第k次选出的聚类中心，相应密度指标为Dck，对于每个数据点指标按公式

进行修正，选出密度指标最高的数据点xck+1作为新的聚类中心。

Step3：判断Dck+1-Dck<δ是否成立。若不成立，则转step2;否则退出。其中δ<1是事先给出的参数，此参数决定了最终产生的初始化聚类中心数目，δ越小，则产生的聚类数越多。

3 基于核的密度函数多分辨率彩色图像分割

首先进行小波变换，获得图像不同分辨率下的表示，在最小分辨率的图像上进行基于核的密度函数的聚类，并结合核化的聚类有效性指标确定聚类数目，同时得到图像分割的初始结果，然后进行扩展，在下一分辨率上进行图像分割，重复直到原始尺寸的图像，从而获得最终的分割结果。

1)小波变换与特征提取：对原始图像进行Le级离散小波变换，获得各个分辨率下的子带。采用9/7提升小波变换和特征提取方法。

2)聚类初始化及聚类数目的确定：将基于核的密度函数的聚类算法和聚类有效性指标相结合实现图像的自适应分割，利用基于核的密度函数聚类结果初始化模糊核聚类的聚类中心，然后运行模糊核聚类直到收敛，并依据聚类有效性指标获得最佳的聚类数目，具体实现步骤如下：

Step1：设置最大聚类数目Cmax和最小聚类数目Cmin，阙值δ，并设置初始聚类数目k=Cmin。

Step2：利用核密度函数聚类算法计算出Cmax个聚类中心或者条件Dck+1-Dck<δ满足，确定聚类数目的上限，修改Cmax的值，最终确定模糊核聚类的初始聚类中心。

Step3：选取Step2获得前k个聚类中心，并进行模糊核聚类算法，直至收敛。

Step4：计算聚类数目为k的聚类有效性的核化指标。如果超出聚类数目的上限转到Step5;否则转到k=k+1，转到Step3。

Step5：依据Step4计算所得的聚类有效性得到最佳聚类数目。

其流程图如图1所示：

3)多分辨率聚类分割：将上一尺度分割所得的标号图像l(x,y)进行标准的线性插值扩展，利用分割结果和当前尺度下特征向量M(x,y)计算当前尺度的聚类中心，设Gq表示扩展l(x,y)同一类的坐标集合，Nq为Gq中元素的数目，则聚类中心的特征矢量为，

得到cL个聚类中心，然后进行模糊核聚类分割，并将其分割结果用于下一尺度图像。继续重复进行此过程直至小波分解的最小尺度，获得各点的隶属度函数μij和聚类{CF}(F=1,2,cL)。

4)最终分割：对原始图像利用上一步分割结果和最小距离分类器进行分割。对于最大隶属度(max(μij)i=1,2,,cL)大于某阙值的点直接划分到该类;否则利用最小分类器进行分割聚类，得到最终的分割结果。距离计算公式不是传统的欧式距离而是采用引入核方法距离公式来获得和模糊核函数对应的最终分割结果。

4 实验结果及分析

图像分割结果如图1所示，运行时间比较如表1所示。表2为基于核的密度函数聚类算法的数值分析表。小波变换采用提升小波算法及其特征提取方法，特征的窗口大小，高斯核函数σ为50。图1 a)为hand、ball、woman、tower原始图像，b)FCM算法结果，c)为本文算法基于核的密度函数聚类的多分辨率彩色图像的分割结果。

从表1可以看出，该方法比传统的模糊C均值聚类算法大大降低了计算的时间，是快速有效的。传统FCM必须设定聚类数目，本方法能够自动确定最佳聚类数目。小波变换的多分辨率特性应用到彩色图像分割，把最佳聚类数目确定和聚类的初始化等能在高分辨率上进行，降低了计算量。从图像的分割结果上看，本文算法要优于传统的FCM算法。从表2可以看到基于核的密度聚类算法随着迭代次数的增加，密度指标差值及Dck+1-Dck逐步下降，直至趋近于0，由此可以得到聚类算法的上限，这样就缩减了聚类有效性指标的搜索范围，降低了模糊聚类算法的计算时间。

5 结论

本文实现了一种基于核密度函数聚类的彩色图像分割方法，并结合小波变换实现了快速彩色图像分割。对裴继红等人的密度函数聚类进行改进用于模糊核聚类的聚类初始化，加快了模糊核聚类的收敛速度以降低计算量。实验结果表明，基于核密度函数的聚类方法对聚类的最佳数目的确定和聚类初始化是快速有效的，其余小波变换结合的彩色图像分割方法大大降低了图像分割的时间。更好聚类有效性指标和彩色图像的特称提取是下一步的研究方向。

参考文献

[1]Chiu S L.Fuzzy model identification based on cluster estimation[J].Intelligent and Fuzzy System,1994(2):267-278.

[2]Girolami M.Mercer Kernel Based Clustering in Feature Space[J].IEEE Trans on NeuralNetworks,2002,13(3):780-784.

[3]蔡卫菊,张颖超.基于核的模糊聚类算法[J].计算机工程与应用,2006,42(18):173-175.

[4]伍忠东,高新波,谢维信.基于核方法的模糊聚类算法[J].西安电子科技大学学报:自然科学版,2004,31(4):533-537.

[5]Jian-Li Ding,Yuan-Xiang Li,Ling-Ling Wang.A wavelet-based color multiresolution image segmentation[C].In:Proceedings of interna-tional Conference on Neural Networks and Brain(ICNN&B'05).Beijing,2005(2):1107-1111.

聚类分析方法在教学评价中的应用 第2篇

【关键词】聚类分析 教学评价

【中图分类号】G642 【文献标识码】A 【文章编号】1006－9682（2009）04－0014－02

【Abstract】This paper lists the 10 teaching evaluation indicators, The cluster analysis of indicators and appropriate classification is based on the principle of cluster analysis to the public 75 computer teachers teaching situation Through the classification and sorting, the teachers come to the indicators of differences in which aspects of teachers for the future of efforts to provide a certain reference value.

【Key words】Cluster Analysis Teaching Evaluation

教学评价既包括对教的评价，也包括对学的评价。当然，评价方法也是多种多样的，但大多数都以定性评价为主，本文旨在采取定量与定性相结合，来探讨聚类分析法在教学评价中的应用。

一、基本概念

俗话说：“物以类聚，人以群分。”分类是人们认识世界的基础。在社会、经济及自然现象的研究中，存在着大量分类研究的问题。尽管传统的分类方法起源很早，但利用数学和计算机手段对复杂对象进行定量分类的方法还只有几十年的历史。

聚类分析的基本思想是根据对象间的相关程度进行类别的聚合。在进行聚类分析之前，这些类别是隐蔽的，能分为多少种类别事先也是不知道的。聚类分析的原则是同一类中的个体有较大的相似性，不同类中的个差异很大。聚类分析又分为样品聚类和变量聚类，本文主要探讨变量聚类。［1］

1．聚类分析的一般步骤［2］

（1）数据变换处理。在聚类分析过程中，需要对各个原始数据进行一些相互比较运算，而各个原始数据往往由于计量单位不同而影响这种比较和运算。因此，需要对原始数据进行必要的变换处理，以消除不同计量单位对数据值大小的影响。

（2）计算聚类统计量。聚类统计量是根据变换以后的数据计算得到的一个新数据。它用于表明各样品或变量间的关系密切程度。常用的统计量有距离和相似系数两大类。

（3）选择聚类方法。根据聚类统计量，运用一定的聚类方法，将关系密切的样品或变量聚为一类，将关系不密切的样品或变量加以区分。选择聚类方法是聚类分析最终的、也是最重要的一步。

2．数据变换

为了克服原始数据由于计量单位的不同对聚类分析结果产生不合理的影响。在聚类分析过程中，首先应对原始数据进行数据变换处理。数据变换的方法很多，本文主要采用Z分数变换，

即： 。

其中：x'ij表示标准化数据， 表示变量j的均值，sj表示变

量的标准差，即： 。

3．聚类统计量

研究样品或变量疏密程度的数量指标有两大类，一类是距离，另一类是相似系数。这两大类指标就是用于反映各样品或各变量间差别大小的统计量。变量的测量尺度不同，所采用的统计

量也就不同。本文采用的欧氏距离，即： 。

4．聚类方法

聚类方法有很多，比如最小距离法，最长距离法，组间聚类法，组内聚类法，本文主要介绍最小距离法，即：首先合并最近的或最相似的两类，用两类间最近点间的距离代表两类间的距离。［3］

二、应用实例

我校教师教学质量评价共有10项指标，如图1所示：

本次教学质量评价是每位学生对该班计算机任课老师的各项指标进行的网上评价，每项指标分为非常满意（3分）、满意（2分）、不满意（1分）三种情况，原始数据略。本文主要是用SPSS软件［4］对75位老师的10项指标的得分情况进行聚类分析，也就是变量聚类，而不是样本聚类。聚类图如图2所示。

根据聚类图中的归类情况，参照各样本的指标数据，我们将26位教师分为四类。分别是：第一类：1、3、4、7；第二类：5、6、8；第三类：9、10；第四类：2。根据聚类结果再对数据进行定性分析发现第一类和第三类的六项指标达到的满意率较高，而第四类的一项指标次之，学生最不满意的是第二类的5、6、8三项指标。

由此可见，教师在授课过程中还应该多介绍该学科最新发展动态、最新研究成果和启发学生思维、创造良好课堂气氛。教师尤其要尽职尽责，积极批改作业和辅导学生。计算机是操作性很强的学科，如果学生的问题得不到及时解决，必然影响教学质量。

三、结 论

本文通过聚类分析对教学评价的10项指标进行分类，反映出不同的教师各项指标存在的差异，通过分类和排序，得出不同的教师在教学上不同的努力方向。同时，又根据聚类分析大量的算法而得出聚类结果，最后采用定量与定性相结合，对我校计算机公共课的教师的各项指标进行分析，明确了教师在以后教学过程中的改进方向，对教学质量的提高具有积极的作用。

参考文献

1 李旭荣.聚类分析在教学评价中的应用.长江大学学报（自科版），2007

2 黄水平.聚类分析法在教师课堂教学中的应用.山西医科大学学报，2005

3 刘明星.聚类分析法在教师考核中的运用.教学与管理，2004

4 魏连昌.试用统计软件进行教学质量分析.软件研制，2006

绘画作品流派分析核聚类算法 第3篇

绘画是艺术门类中的重要组成之一。绘画艺术从作品材质划分, 西方有油画、漆画等, 中国有水墨画、水彩画等;从风格上划分, 则更加细分到诸多流派, 单譬如油画, 就有印象主义、浪漫主义、写实主义, 抽象主义、后现代主义等等数十种之多, 对于一般的艺术欣赏者而言, 难以分辨。因此, 亟需提出一种基于机器识别的分类算法。

分类算法需根据艺术流派分析的传统经验进行算法设计, 同时可以参考基于内容的视频检索的部分核心思想进行实现。就核心概念而言, 视频是帧的封装, 流派是目标作品绘画的封装, 在实现上具有类比的可行性。在基于内容的视频检索领域, 许多研究方法都是利用并提取关键帧从而简化视频相似度对比的运算量, 但需满足帧数相等的先决条件。在绘画目标作品分类算法中, 显然不适用。为了更好的满足本文特定的分类需求, 算法需解决两个不同绘画样本数量 (矩阵不同维) 的聚类及其相似度计算问题。本文主要思想正是以此为出发点, 提出相似度核来计算不同维矩阵相似度的算法, 再结合聚类算法解决流派分类问题。

1 特征提取

颜色、纹理和形状是绘画作品图像中最重要的代表特征, 也是最为底层的视觉特征, 我们在特征向量的提取工作中, 着重从此着手。

颜色特征是固有的一种视觉特性, 颜色特征对图像质量的变化、噪声等都有很好的鲁棒性, 目前基于图像颜色提取特征向量的算法日臻成熟, 如颜色直方图、颜色矩、累计直方图、Color Coherence Vector等。

纹理特征与物体的表面有强相关性, 表现物体的某种局部性质, 是像素在局部区域中分布关系的度量, 但其本质是像素灰度空间的分布规律。基于图像纹理提取特征向量的算法有重要的研究意义, 也取得了很大的发展, 主要有Tamura纹理特征、灰度共生矩阵、小波变换和自回归纹理模型等。

形状特征基于图像中物体与区域的划分, 在目前的技术水平下, 无法保证准确性和鲁棒性, 只应用于特殊情况中。

对此, 提出了综合特征提取方法, 采用颜色特征与纹理特征相结合的方法构造特征矩阵。

1.1 颜色特征向量提取

选取分量间相互独立且具有视觉一致性的HSV颜色空间, 如图1所示。

为72级的一维直方图, 即该图像的颜色特征。

1.2 纹理特征向量提取

采用灰度共生矩阵来表示纹理特征, 其本质是图像二阶组合条件概率密度函数。具有计算量小, 算法复杂度低, 容易实现, 特征提取速度快的特点。

取d=1, θ分别为0°、45°、90°、135°的公式如下:

RGB转化为灰度图像, 灰度级256, 如式 (7) :

其中Y为灰度值, R为红色分量的灰度值, G为绿色分量的灰度值, B为蓝色分量的灰度值。

在保证检索特征的前提下, 采用16级灰度量化能大大提高提取速度, 按照公式 (3) (4) (5) (6) 构造共生矩阵, 分别计算出其惯性矩CON、熵ENT、能量ASM、相关COR后做归一化处理, 得公式 (8) :

其中Fi为N维特征向量, fij为上特征分量。

1.3 综合特征向量提取

在获得颜色特征和纹理特征之后, 根据公式 (1) 和公式 (8) 可构造综合特征向量为:

1.4 特征矩阵构造

2 相似度计算

2.1 相似度核

根据上文1.2章节构造特征矩阵的定义, 利用公式 (11) 对待分类的绘画目标作品建立特征矩阵, 即:

其中, nj为所选流派图像库中所包含的作品图像的数量。

公式 (14) 得出的相似度核, 可以量化解决绘画目标作品与绘画流派图像库之间 (即不同维度矩阵) 的相似度计算问题。为了进一步提高机器分类的精度, 我们结合艺术作品传统识别方法中最为关键的特征进引入权重系数, 即对绘画作品的纹理和颜色特征进行加权。在公式 (11) 中加入权重系数ω, 则公式 (11) 的改进形式为:

根据公式 (12) 与公式 (13) 定义, 代入公式 (15) 中得到加权相似度核为:

权重系数采用加权向量进行设置:

其中, ωcm是颜色特征加权值, ωtm是纹理特征加权值, 可根据具体情况进行优化调整。

2.2 聚类算法

综合分析目前的主流聚类算法并根据本文研究的实际情况, 采用层次聚类中的凝聚算法, 可以得到较好的聚类精度与较好的聚类时间, 应用在本文算法中流程如下:

流程一:输入待分类的数字化绘画作品图像, 提取颜色特征向量和纹理特征向量并构造综合特征向量, 进而构造特征矩阵;

流程二:输入流派图像库全部图像, 提取颜色特征向量和纹理特征向量并构造综合特征向量, 进而构造特征矩阵;

流程三:根据公式 (16) 计算相似度, 进行凝聚聚类后标记、合并高于相似度阀值的类别, 并更新聚类特征矩阵;

流程四:若聚类符合要求, 则选择相似度最高的流派图像库, 作为匹配结果, 并按相似度排序列举备选流派图像库。若聚类不符合要求, 则转流程三。

4 结束语

本文提出一种相似度核聚类算法, 主要解决了绘画作品相似度的量化及机器分类的问题。首先定义了目标作品绘画与流派图像库的特征向量与特征矩阵;其次, 基于矩阵运算方法及核函数提出一种相似度核聚类算法, 能有效完成绘画作品的流派分析和聚类。但是, 本文所设计的算法在特征向量的提取上, 还不够全面有效, 造成了对作品流派的进一步细分, 例如印象派中的新印象派、后印象派等, 就无法做到较好的识别与相似度区分, 此类问题更加复杂, 将是下一步研究的重点。

参考文献

[1]李梁凯, 徐庆, 罗小小.结合Tsallis熵与Jensen距离的视频关键帧抽取方法[J].计算机工程, 2015.04.10 16:39.

[2]王松, 韩永国, 吴亚东, 张赛楠.基于图像主色彩的视频关键帧提取方法[J].计算机应用, 2013, 9.

[3]孙吉贵, 刘杰, 赵连宇.聚类算法研究[J].软件学报, 2008, 19 (1) .

核方法聚类 第4篇

核方法是支持向量机 (Support Vector Machine, SVM) 的基础[1]。支持向量机广泛应用于分类、回归、新知识检测等领域以及聚类分析[2,3,4,5]。Tax将支持向量机方法用于数据域描述 (即一类分类) 中, 提出了基于高斯核的SVDD (Support Vector Domain Description ) 算法[6], Ben-Hur等将该算法进一步发展为一种新的无监督非参数型的聚类算法-支持向量聚类 (Support Vector Clustering, SVC) [7]。

高斯径向基函数 (Radial Basis Function, RBF) 相对于线性核函数和多项式核函数具有更好的性能[6], 因而广泛应用于支持向量聚类。然而当样本空间分布不均匀时, 单宽度的高斯核函数存在局部泛化风险, 是典型的局部核, 影响了支持向量聚类的效果。鉴于此, 本文提出加权多宽度高斯核函数应用于支持向量聚类, 通过加权多宽度高斯核函数的多参数调节以期提高泛化能力、改善聚类的效果。

1 核方法

核方法的基本思想就是通过非线性变换把输入样本空间映射到一个高维特征空间, 然后在高维特征空间中设计线性学习算法。如果算法中各个模式矢量间的相互作用仅限于内积运算, 则不需要知道非线性变换的具体形式, 只要用满足Mercer条件的核函数代替线性算法中的内积, 就能得到原输入空间中对应的非线性算法, 从而避免了高维Hilbert空间中进行大量内积计算的“维数灾难”。高斯核是支持向量聚类中普遍采用的核函数。

1.1 高斯核

高斯核函数形式如下[1]:

${\rm K}(\mathit{x},\mathit{y})=\exp (-\parallel \mathit{x}-\mathit{y}\parallel {}^2/2\sigma {}^2)(1)$

式中:x, y为输入样本空间。高斯核函数的宽度参数σ2定义了该函数的泛化规模, 直接影响SVM 的泛化能力, 由于高斯核可调参数的惟一性和数据样本空间分布的不均匀性, 单宽度的高斯核在样本的稠密区域会产生过学习现象, 而在样本的稀疏区域则产生欠学习现象, 也就是存在局部风险, 可能造成对样本的错误聚类。

1.2 加权多宽度高斯核

加权多宽度高斯核函数 (Weighted Gaussian Kernel with Multiple Widths, WGKMW) [8]形式如式 (2) 所示:

$\begin{array}{l}{\rm K}(\mathit{x}‚\mathit{y})=[\exp (-\parallel \mathit{x}-\mathit{y}\parallel {}^2/2\sigma {}^2)+R]{}^m\\ \forall R\ge 0‚m\ge 0‚m\in {\rm N}(2)\end{array}$

通过二项式定理 (Binomial Theorem) 将式 (2) 展开如下:

$\begin{array}{l}{\rm K}(\mathit{x}‚\mathit{y})={\displaystyle \sum _{s=0}^m\left[\begin{array}{l}m\\ s\end{array}\right]}R{}^{m-s}\exp \left(-\frac{s\parallel \mathit{x}-\mathit{y}\parallel {}^2}{2\sigma {}^2}\right)\\ =R{}^m+{\displaystyle \sum _{s=1}^{m}R}{}^{m-s}\exp (-\frac{\parallel \mathit{x}-\mathit{y}\parallel {}^2}{2\sigma {}^2/s})(3)\end{array}$

由式 (3) 可以看出, m个不同宽度的高斯核线性组合成加权多宽度高斯核。Rm-s是分别分配在m个不同宽度高斯核上的权重系数, 控制不同高斯核的相对权重;m个高斯核由统一的宽度σ2变为可调宽度σ2/s;常量因子Rm使数据点之间距离的线性平移放大, 在其特征空间扩大了样本点之间的差异, 从而可以更好地实现对差别微弱的样本类之间的聚类。

2 基于加权多宽度高斯核的支持向量聚类 (SVC)

该聚类算法的基本思想是:通过加权多宽度高斯核的非线性变换, 把输入的数据集映射到高维特征空间, 然后在高维特征空间中寻找包围样本点映像的超球体, 并通过最小化该超球体的体积, 使得目标样本点尽可能的被包围在超球体内部, 而非目标样本点尽可能的在超球体外部。最后将超球描述的数据映射回输入空间, 超球体转化为一系列封闭的轮廓, 每一个轮廓就是一个聚类集合。其过程主要分为2部分:聚类描述 (SVDD) 和聚类标识。聚类描述部分包括:加权多宽度高斯核宽度系数的优化、Hilbert空间最小包络超球体半径的计算、Lagrange乘子的计算以及有界支持向量 (Bounded Support Vectors, BSVs) 与支持向量 (Support Vectors, SVs) 的选取;聚类标识部分:首先生成聚类标识邻接矩阵, 再通过DFS (Depth First Search) 算法[9]根据邻接矩阵进行聚类分配。

2.1 聚类边界

设数据空间X⊆Rm, 数据集{xi}⊆X包含N个数据点, 通过WGKMW定义的非线性映射Φ:XH;xΦ (x) , 将样本从输入空间映射到高维特征空间中, 在特征空间构造包含全部或大部分数据点的超球, 最小包络超球体半径r通过下面的优化问题[7]实现:

$\{\begin{array}{l}\min L=r{}^2+C{\displaystyle \sum _{i=1}^{{\rm N}}\xi }{}_i\\ \text{s}.\text{t}.\parallel \Phi (\mathit{x}{}_i)-\mathit{a}\parallel {}^{2}r{}^2+\xi {}_i\end{array}(4)$

式中:‖‖是欧几里德模量;a是超球球心;ξi是允许部分数据在球外引入的松弛变量, ξi≥0。

将式 (4) 写为Lagrangian形式:

$\begin{array}{l}L(r‚\mathit{a}‚\mathit{\xi })=r{}^2+C{\displaystyle \sum _{i=1}^{{\rm N}}\xi }{}_i-{\displaystyle \sum _{i=1}^{{\rm N}}[}r{}^2+\xi {}_i-\\ \parallel \Phi (\mathit{x}{}_i)-\mathit{a}\parallel {}^2]\cdot \beta {}_i-{\displaystyle \sum _{i=1}^{{\rm N}}\xi }{}_i\mu {}_i(5)\end{array}$

式中:βi≥0和μi≥0均为Lagrangian乘子;惩罚系数C (0<C<1) 用来在最小包络球的大小和可能落在球体外的样本数量之间进行平衡。

由式 (5) 求min L即:

$\frac{\partial L(r‚\mathit{a}‚\mathit{\xi })}{\partial r}=0‚\frac{\partial L(r‚\mathit{a}‚\mathit{\xi })}{\partial \mathit{a}}=0‚\frac{\partial L(r‚\mathit{a}‚\mathit{\xi })}{\partial \mathit{\xi }}=0$

可得:

$\{\begin{array}{l}{\displaystyle \sum _{i=1}^{{\rm N}}\beta }{}_i=1\\ \mathit{a}={\displaystyle \sum _{i=1}^{{\rm N}}\beta }{}_i\Phi (\mathit{x}{}_i)\\ \beta {}_i=C-\mu {}_i\end{array}(6)$

由KKT互补条件[10]可得:

$\{\begin{array}{l}\xi {}_i\mu {}_i=0\\ (r{}^2+\xi {}_i-\parallel \Phi (\mathit{x}{}_i)-\mathit{a}\parallel {}^2)\beta {}_i=0\end{array}(7)$

分析KKT条件可知, 若一个样本点对应的松弛变量ξi> 0, 并且βi> 0, 表示该样本点落在特征空间中的最小包络超球的外面。由式 (7) 可知, 这种点对应的μi=0, βi= C, 这种点称有界支持向量。当某个样本点对应的βi满足0 <βi< C 时, 可知ξi= 0, 代入式 (7) 有 (r2-‖Φ (xi) -a‖2) =0, 表示该样本点位于特征空间超球的表面上 (因为它们到球中心的距离等于球半径) , 这样的点就称为支持向量。而剩下的那些对应βi= 0 的点, 则落在超球内部。由${\displaystyle \sum _{i=1}^{{\rm N}}\beta }{}_i=1$可知, 当C≥1时, 不存在有界支持向量。

将式 (6) 代入式 (5) , 并消去r, a和μi得到Lagrangian的Wolf对偶形式:

$\{\begin{array}{l}\max W(\beta )={\displaystyle \sum _{i=1}^{{\rm N}}(}\Phi (\mathit{x}{}_i)){}^2\beta {}_i-{\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\beta }}{}_i\beta {}_j\Phi (\mathit{x}{}_i)\cdot \Phi (\mathit{x}{}_j)\\ \text{s}.\text{t}.{\displaystyle \sum _{i=1}^{{\rm N}}\beta }{}_i=1\end{array}(8)$

式中:i=1, 2, , N;0βiC。

根据Mercer定理, 用Mercer核来替代式 (8) 中的点积形式, 即K (xi, xj) =Φ (xi) Φ (xj) , 并将式 (2) 的加权多宽度高斯核代入式 (8) 得:

$\{\begin{array}{l}\max W(\beta )={\displaystyle \sum _{i=1}^{{\rm N}}{\rm K}}(\mathit{x}{}_i‚\mathit{x}{}_i)\beta {}_i-{\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\beta }}{}_i\beta {}_j{\rm K}(\mathit{x}{}_i‚\mathit{x}{}_j)\\ \text{s}.\text{t}.{\displaystyle \sum _{i=1}^{{\rm N}}\beta }{}_i=1\end{array}(9)$

式中:i=1, 2, , N;0βiC。

使用加权多宽度高斯核时SVC的模型参数包括m, σ, R和惩罚系数C。样本点x在特征空间中的像到球心的距离为:

$\begin{array}{l}d{}^2(\mathit{x})=\parallel \Phi (\mathit{x})-\mathit{a}\parallel {}^2={\rm K}(\mathit{x}‚\mathit{x})-2{\displaystyle \sum _{i=1}^{{\rm N}}\beta }{}_i{\rm K}(\mathit{x}{}_i‚\mathit{x})+\\ {\displaystyle \sum _{i=1}^{{\rm N}}{\displaystyle \sum _{j=1}^{{\rm N}}\beta }}{}_i\beta {}_j{\rm K}(\mathit{x}{}_i‚\mathit{x}{}_j)(10)\end{array}$

超球体的半径r可以用任一支持向量到球心的距离表示:

$r=d(\mathit{x}{}_i)(11)$

式中:xi为支持向量。

支持向量聚类的边界为:数据空间中满足{x|d (x) =r}条件的样本点即支持向量形成聚类的边界, 有界支持向量在边界外, 其他数据点在聚类范围内。

2.2 聚类标识

由于聚类描述算法 (SVDD) 对样本点所属的类不做区分, 为了在输入空间形成不同的类, 利用特征空间中的距离d (y) 来划分:如果2个样本点属于不同的类, 则它们在输入空间中的任何连线必将穿过数据概率密度极低的区域 (Valley) , 这样的路径连线在特征空间中将穿出超球体, 因此穿出超球部分的连线上必然存在点y且有d (y) >r。由此可以定义一个由数据点对决定的nn邻接矩阵A, 对于给定的一对数据点xi和xj, 邻接矩阵中的元素Aij得出如下: 如果xi和xj之间路径连线上的所有y都有d (y) r, 则Aij=1;否则, Aij=0。

这里邻接矩阵A诱导出一个曲线图, 曲线图中的连通量定义为类。根据邻接矩阵A, 由DFS (Depth-first Search) 算法进行聚类分配。

3 仿真实验与分析

对3组数据集分别采用单宽度高斯核和加权多宽度高斯核进行支持向量聚类实验。3组数据集均为线性不可分。

实验1 二维空间的数据集pentagon, 取自捷克技术大学Vojtech Franc和Vaclav Hlavac编写的stprtool工具包, 由99个样本组成[11], 分别隶属于5个不同的类别。选取单宽度高斯核参数σ=0.25, 惩罚系数C=0.35。加权多宽度高斯核参数m=2, σ=0.25, R=6.4, 惩罚系数C=0.35。聚类实验结果如图1所示。

由实验结果可见, 图1 (a) 中单宽度高斯核聚类有2个有界支持向量点 (BSVs) , 图1 (b) 中加权多宽度高斯核没有有界支持向量点。

实验2 实验数据采用美国GUI的Iris实际数据, 数据由四维空间中的150个样本组成, 分别隶属于3个不同的类别, 每类50个样本。这里仅抽取其两维空间即有两类属性的120个样本[12], 分别隶属于2个不同的类别。选择单宽度高斯核参数σ=0.8, 惩罚系数C=0.3。选择加权多宽度高斯核参数m=2, σ=0.8, R=0.3, 惩罚系数C=0.3。聚类实验结果见图2。

由实验结果可见, 图2 (a) 中单宽度高斯核聚类有4个有界支持向量点 (BSVs) , 图2 (b) 中加权多宽度高斯核有1个有界支持向量点。

实验3 实验数据采用匈牙利维斯普雷姆大学Janos和Balazs Feil编写的模糊核聚类工具箱中的数据Data3[13], 该数据集由163个样本组成, 分别隶属于3个不同的类别。选取单宽度高斯核参数σ=2, 惩罚系数C=0.3, 加权多宽度高斯核参数σ=2, R=2, m=2惩罚系数C=0.3。聚类实验结果见图3。由实验结果可见, 图3 (a) 中单宽度高斯核聚类有3个有界支持向量点 (BSVs) , 图3 (b) 中加权多宽度高斯核有2个有界支持向量点。

有界支持向量 (BSVs) 属不能正确聚类的样本点。通过计算有界支持向量所占样本总数的比例, 即聚类误差率, 来评价单宽度高斯核和加权多宽度高斯核的聚类效果。

聚类误差率:

$\text{e}\text{r}\text{r}\text{o}\text{r}=(\text{B}\text{S}\text{V}\text{s}/l)100\%$

式中:l为数据样本总数。

应用2种核函数的聚类性能比较见表1。

从以上3组实验可见, 选择加权多宽度高斯核参数σ以及惩罚系数C与单宽度高斯核相同, 通过调节加权多宽度高斯核增加的2个参数R, m, 所得的聚类结果误差率要低于单宽度高斯核的聚类。加权多宽度高斯核的参数空间覆盖了单宽度高斯核的参数空间, 通过引入适当核函数的调节参数能够增加聚类的泛化能力, 提高聚类效果。

4 结 语

本文提出将加权多宽度高斯核函数应用到支持向量聚类, 弥补了单宽度高斯核函数可调参数单一、泛化能力弱的不足。实验结果表明, 在加权多宽度高斯核参数σ以及惩罚系数C与单宽度高斯核相同时, 通过调节R, m可以降低聚错率。

加权多宽度高斯核参数的选取对聚类效果具有较大的影响, 如何优化核函数的参数, 以达到更好的聚类效果, 仍有待进一步研究。

参考文献

[1]CRISTIANINI N, SCHOLKOPF B.Support vector ma-chines and kernel methods:the new generation of learningmachines[J].AI Magazine, 2002, 23 (3) :31-41.

[2]MULLER K R, MIKA S, RATSCH G, et al.An introduc-tion to kernel based learning algorithms[J].IEEE Transac-tions on Neural Networks, 2001, 12 (2) :181-201.

[3]BURGES C J.A tutorial on support vector machines forpattern recognition[J].Data Mining and Knowledge Dis-covery, 1998, 2 (2) :121-167.

[4]SCHOLKOPF B, WILLIAMSON R, SMOLA A, et al.Sup-port vector method for novelty detection[J].Advances inNeural Information Processing Systems, 2000, 12:582-588.

[5]HUR A B, HORN D, SIEGELMANN H T, et al.A supportvector clustering met hod[C]//Proceedings of 2000 15thInternational Conference on Pattern Recognition.Barcelona:ICPR, 2000, 2:724-727.

[6]TAX D M J, DUIN R P W.Support vector domain descrip-tion[J].Pattern Recognition Letters, 1999, 20 (11-13) :1191-1199.

[7]HUR A B, HORN D, SIEGELMANN H T, et al.Supportvector clustering[J].Journal of Machine Learning Re-search, 2001 (2) :125-137.

[8]田径, 赵犁丰, 赵宇倩.一种基于WGKMW的网络结构核函数框架[J].中国海洋大学学报:自然科学版, 2009 (S1) :86-88.

[9]FLETCHER R.Practical methods of optimization[M].Chichester:Wiley-Interscience, 1987.

[10]FRANC Vojtech, HLAVAC Vaclav.Statistical patternrecognition toolbox for matlab[M].[S.l.]:[s.n.], 2008.

[11]HUR A B, HORN D, SIEGELMANN H T, et al.Supportvector clustering toolbox[DB/OL].[2001-11-05].http://www.scholarpedia.org/article/Support_vector_clustering.

核方法聚类 第5篇

传统的FCM算法虽然快速简单, 但并没有考虑目标物体的形状等先验知识, 没有对样本特征进行优化, 而是基于样本特征间的欧氏距离进行聚类。对噪声和异常点缺乏足够的鲁棒性, 分割时间依赖于图像的大小, 因此图像越大, 分割时间越长。在过去几十年中, 随着对模糊C-均值聚类算法的深入研究, 针对其不足, 国内外学者提出了许多改进的FCM算法, 并融合其他技术以提高图像分割性能。Ahmed等[2]结合空间邻域信息, 提出FCM_S算法, 取得了好的分割效果;陈和张等[3]人又在此基础上提出了其变体算法FCM_S1和FCM_S2, 减少了运算量。Wang X等[4]提出运用权重思想确定像素点隶属度, 抑制了噪声的干扰。结合空间信息的FCM增强算法已有效地用于图像降噪及图像分割[5]。后来很多学者提出了基于核函数的模糊C-均值聚类算法 (KF-CM) , 通过引入核函数将传统的FCM推广到了核空间, 对图像的特征具有较好的适应性, 同时核函数对噪声具有很好的抑制能力。因此, 学者们在FCM算法中引入核函数。Zhang和Chen等用非线性函数对图像像素进行空间变换, 将FCM_S算法、FCM_S1算法和FCM_S2算法扩展到相应的核版本, 以此来增强FCM_S算法、FCM_S1算法和FCM_S2算法的抗噪性能, 在新的特征空间按照FCM算法对图像各点进行聚类。

本文结合空间邻域和灰度信息, 引入核函数, 针对RF-CM[6]算法未考虑噪声和邻域之间关系, 无法有效避免噪声影响的缺点, 提出基于空间信息的核均值聚类分割算法。实验表明, 提出算法分割结果保留了图像更多细节和边缘信息, 同时具有较强的抗噪声能力。

1 RFCM算法

FCM算法最早由Dunn提出, 而后由Bezdek[1]进行完善。传统的FCM算法是一种迭代算法, 将图像中所有的像素点当作孤立的数据进行聚类, 是一种无监督分类方法。由于原始的FCM算法未考虑图像的空间信息, 这使得算法在运行过程中对噪声十分敏感。FCM算法通过将图像I={f (i, j) , 0≤i≤M, 0≤j≤N}分成c类, 实现图像的分割, 其中f (i, j) 为特征数据。

RFCM算法是广义模糊C均值聚类算法的改进算法[11]是FCM的一个改进算法。通过在隶属度函数中引入一个单一数据点的量, 使得分配更清晰。

RFCM的目标函数如下:

使用拉格朗日数乘法最小化式 (1) , 新的聚类中心vi和隶属度函数uij更新方程如下:

为满足uij, 0≤uij≤1, α (0≤α≤1) , aj=α·min{‖xj-vs‖2|s∈{1, 2, …, c}}参数控制收敛速度, 当α=0时, RFCM算法等价于FCM。

在参数α选取适当的情况下, RFCM不仅可以更快速地聚类, 还具有良好的聚类性能。但是, RFCM算法中噪声被视为正常图像的一部分, 未考虑噪声和邻域之间的关系, 故无法有效避免噪声的影响。

2 改进的基于空间信息的核聚类算法

2.1 核表示和核函数

文献[3]提出了基于核函数的FCM算法KFCM。Φ:x∈XRd|→Φ (x) ∈RH (d<<H) 是由一个非线性映射到一个高维特征空间F的变换, 在F中, 欧氏距离‖x-y‖2被‖Φ (x) -Φ (y) ‖2取代, 定义为:

每一个线性算法仅利用内积就可以很容易地扩展到非线性, 只要通过满足Mercer条件的核函数[15]。因为高斯核函数对应的特征空间是无穷维的, 有限的样本在该特征空间肯定是线性可分的, 所以较常用。本文中采用高斯核函数。这里, 核函数K (x, y) 被用来计算F的内积。定义核函数如下:

将式 (4) 带入 (5) 式得到:

样本方差来估计σ2被定义为:

2.2 KSNRFCM算法

本算法引入核函数并提出结合局部空间和灰度信息的一个新的模糊C均值聚类图像分割算法 (KSNRFCM) 。通过内核替代 (即方程 (6) ) , 所述核广义模糊C-均值聚类目标函数如下:

利用拉格朗日乘子法得到隶属度函数和聚类中心:

NKRFCM算法的基本步骤如下:

步骤1:确定聚类数c, 模糊加权指数 (此处直接定义为2) , 迭代停止阈值ε, 令初始迭代次数为n=0。

步骤2:初始聚类中心vi (0) 。

步骤3:根据式 (9) 计算新的隶属度uij。

步骤4:根据式 (10) 计算新的聚类中心vi。

步骤5:停止条件|Unew-Uold|<ε, 算法终止, 否则, 令n=n+1, 转至步骤3。 (U=[u1, u2, …, uc]是聚类原型向量)

步骤6:按照最大隶属度原则对图像进行分割。

3 实验结果与讨论

为验证本文算法有效性, 实验中将算法用于lena图像进行分割实验, 并与FCM、RFCM、NRFCM以及KGFCM分割方法进行了比较。为验证算法可行性, 在Visual C++6.0环境下进行实验, 在实验中选取λ=0.02。所有算法在Microsoft windows XP计算机上进行。

3.1 含噪图像实验结果分析

为验证试验结果有效性, 对图1 (a) 原始图像加入高斯噪声和椒盐噪声, 分别运用RFCM、NRFCM算法与本文所提出算法进行比较, 设置分类数c=2。

图1 (b) 为加入均值为0, 局部方差为0.01的高斯噪声后的图像, 图1 (c) 为RFCM算法分割结果, 图1 (e) 为NRF-CM算法分割结果, 图1 (f) 为本文算法分割结果。

可以看出, 利用本文所提出算法进行图像分割, 噪声抑制效果比RFCM算法和NRFCM算法更好。分割后, 方形零件周界清晰。

3.2 图像分割细节实验结果分析

将本文算法应用于lena图像进行分割实验, 并与FCM、RFCM、NRFCM以及KGFCM分割方法进行了比较。

如图2, (b) 是FCM算法分割结果; (c) 为KGFCM算法分割结果; (d) 为RFCM算法分割结果; (e) 是NRFCM算法分割结果; (f) 本文提出算法分割结果。

对比图2, 结合图3本文算法分割lena图对比明显区域描述看出:对于图中的脸部、嘴巴和帽子流苏部分的细节与边缘部分 (红框区域) , 本文所提算法分割效果更好, 细节显示更充分。结合图像的分割性能指标 (表1) , 本文所提出算法在分割过程中保留了更多图像的细节信息。

3.3 分割性能指标分析

为了对算法进行客观、定量的评价, 本文采用常用的图像分割评价标准最大香农熵Hmax[6]对上述分割结果进行评价, 定义如下:

其中, P0, P1分别表示分割图像的二值输出为1和0的概率。对大多数图像而言, 香农熵代表图像的信息量, 如果分割后的图像香农熵越大, 分割图像从原始图像中得到的信息量越大。分割图像细节越丰富, 总体分割效果越好。这里分别对lena图像、flower图像以及脑出血放射图像进行仿真验证。

得到分割性能指标如下表所示:

4 结束语

本文提出结合空间邻域和灰度信息的新的模糊C-均值聚类图像分割算法 (SNRFCM) , 然后在新的目标函数中采用内核感应距离代替欧氏距离, 同时通过引入核函数, 提出了一种基于空间信息的核聚类图像分割算法 (SKNRFCM) 。通过使用一个惩罚因子, 有效地减少噪声对聚类结果的负面影响。通过使用聚类权重, 有效避免部分噪声影响。实验结果表明, 通过与FCM、RFCM、NRFCM和KGFCM算法进行比较, 本文所提出算法具有良好的分割性能, 尤其在图像分割细节和边缘方面, 同时具有较好的抗噪声能力。

摘要：RFCM是对传统的模糊C均值聚类算法的一个改进算法。但未考虑噪声和邻域间的关系, 故无法有效避免噪声影响。为克服以上缺点, 提出结合空间邻域和灰度信息的核模糊C均值聚类图像分割算法。通过使用一个距离惩罚项, 有效地减少噪声对聚类结果的负面影响;通过使用聚类权重有效避免块噪声;引入空间约束项、采用内核感应距离, 使分割结果更好地保留了图像细节, 分割更加准确。实验结果表明, 与FCM、RFCM、NRFCM和KGFCM比较, 该算法保留更多图像细节和边缘信息, 同时具有较强的抗噪声能力。

关键词：RFCM,图像分割,模糊C均值聚类,核函数

参考文献

[1]BEZDEK JC.Cluster Validity with Fuzzy Sets[J].Cybernetics and Systems, 1974, 3 (3) :56-75.

[2]AHMED MN, YAMANY SM, MOHAMED N, et al.A Modified Fuzzy C-means Algorithm for Bias Field Estimation and Segmentation of MRI data[J].IEEE Trans Med Imag, 2002, 21:193-199.

[3]Zhang DQ, Chen SC.A Novel Kernelized Fuzzy C-Means Algorithm with Application in Medical Image[J].Artificial Intelligence in Medicine, 2004, 32 (1) .

[4]Wang X, Wang Y, Wang L.Improving fuzzy c-means clustering based on feature-weight learning[J].Pattern Recognition Letters, 2004, 25:1123-1132.

[5]WU M, SCHOLKOPF B.A local learning approach for clustering[J].Adv.Neural Inf.Process Syst, 2007, 19:1529-1536.

核方法聚类 第6篇

高光谱遥感图像包含了丰富的空间和光谱信息,具有很高的分辨力,已应用到科学研究的各个领域,特别是国防等涉及国家安全方面[1]。然而,面对高光谱的海量数据,如何将高光谱图像的各种特征结合,研究快速、高效的目标识别算法是目前和未来一段时间内的一个重点。

聚类分析是数据挖掘及机器学习领域内的重点问题之一,在数据挖掘、模式识别、决策支持、机器学习及图像分割等领域有广泛的应用。聚类是一个将数据分类到不同的类或者簇的过程,属于同一个簇的样本或者数据的特性具有很大的相似性,属于不同簇的样本数据有较大的不同点,聚类的这一特性可在高光谱图像处理中发挥重要的作用[2]。

在聚类领域中,传统的方法分为无监督聚类和监督聚类两种。前者不需要有标记的数据,但限制了算法性能的提高;监督聚类需要大量的有标签样本的数据作为训练集,而有标记数据的获取却是比较困难且昂贵的。由于监督聚类和非监督聚类的局限性,半监督聚类成为一个新兴的研究热点。半监督聚类结合了非监督聚类和监督聚类的优点,充分利用数据的类别信息和内部结构信息,能够得到比较好的结果[3]。冷明伟[4]提出一种基于极少量标签数据的半监督K-均值聚类算法,它首先利用标签数据集选取初始点,对给定的数据集进行聚类,然后基于影响因子和约束进行聚类结果的合并,该方法在标记样本较少时仍能实现较高的聚类精度。陈小冬等[5]提出一种基于判别分析的聚类算法,迭代执行降维和聚类,其不仅能很好地处理高维数据,还有效地提高了聚类性能。

Camps-Valls[6]等提出一种基于图的半监督聚类算法(Semi-Supervised Graph-Based Clustering, SSGC),将流形学习算法应用于图结构的设计中,能很好的挖掘高光谱遥感数据的非线性特性[7],取得了较好的分类效果。SSGC算法相对于支持向量机(Support Vector Machine, SVM)算法表现出较好的鲁棒性和稳定性,且当标记样本数较少时,优势更加明显,这说明该方法在不适定情况下分类的有效性。通过将该方法在高光谱数据上运行,发现此算法能产生较高的分类正确率,但仍有提升空间;然而其耗时巨大,虽然原作者使用Nyström方法[8]以提升计算速度,但这种方法又引进了两个需要调节的参数——用于计算核矩阵近似分解的样本数和最大本征值的数量。

鉴于SSGC算法的不足,本文在此算法上进行一定的改进,首先通过引入半监督学习方法对RBF核函数进行了改进,更好地利用了样本的先验信息和背景知识;同时又融合光谱角核函数,最终提出一种半监督复合核图聚类算法(Semi-Supervised Graph Clustering with Composite Kernel, SSGCK ),可以提高聚类正确率,而且有效提升运算速度。

1 相关工作

1.1 半监督聚类

聚类是将不同的样本数据按照其本身的特性划分到各个不同的类或者簇的过程,它能够很好地反映样本的分布特点,揭示数据结构特征,并表现出一定的优势。较为经典和著名的聚类算法有:K-均值(K-means)算法[9,10],一种将样本以隶属度为1 或0 的方式划分至某一类中的硬划分聚类算法,已被广泛使用;模糊C-均值(Fuzzy C-Means,FCM)算法[11,12],Bezdek将模糊因子引入了K-均值算法,提出了FCM算法。

半监督聚类[13]利用少部分标记的数据辅助非监督的学习。目前,半监督的聚类方法大致分为以下两类:

1) 基于限制的方法。该类算法在聚类过程中,利用标签的数据来引导聚类过程,最终得到一个恰当的分割结果。通过分析给定的标记信息和其它相关的约束条件,得到更多控制聚类过程的信息,减少聚类搜索的次数或者盲目性,在得到更好聚类效果的同时能适当减少聚类的时间。

2) 基于距离测度函数学习的方法。聚类算法必须基于某一距离测度函数进行聚类,在该方法中所使用的距离测度函数是通过对标签数据学习得到的。

1.2 SSGC算法

SSGC算法是一种基于图的半监督聚类算法。基于图的半监督聚类算法核心思想在于:构造一个图模型G(V,E),图中数据点作为顶点,数据的相似性作为边权值。其中数据节点包含了少量有标记的数据和大量无标记的数据,边权值反映了数据点之间的相似程度,权值越大表示数据点越相似,反之越不相似。SSGC算法的具体实现为:

假设存在n个N维数据空间的数据x组成的数据集Xn={x1, x2, …, xl, xl+1, …, xn}RN以及其对应的标签集 Γ={1, 2, 3, …, c},其中前l个数据点被标记为yi∈Γ,其余数据为未标记数据,目标算法就是找到这n-l个数据点所属的类别。定义一个n ×c的矩阵F,若数据中第i个点xi被标记为yi=j∈Γ,则Fij=1,否则Fij=0;在计算F之前,首先引入标记样本信息,即仿照定义F的方式定义一个n×c的矩阵Y,将数据集中已知类别的标记信息代入Y中。

SSGC算法的重点是构造近邻矩阵W,其使用的是RBF核函数:

式中令Wij=0 以避免自相似。

2 半监督复合核图聚类算法

SSGC算法在构造近邻矩阵时,必须求出每个点相对于其他所有点的权重值,这是一个繁琐而又冗余的操作,而且SSGC算法在此过程没有应用标记样本信息;另外,SSGC算法采用单个核函数构成的核机器并不能应对诸如数据异构或不规则、样本规模巨大、样本不平坦分布等实际问题。

本文提出的SSGCK算法在构造权重矩阵时,先对RBF核函数进行一定的改进,精简算法步骤,减少计算量,同时加入标记信息,增加同类点权重,构造出第一个权重矩阵W;然后又利用光谱角信息,构造了一个基于光谱角核函数的权重矩阵A,最后将两个权重矩阵融合,构造复合核函数权重矩阵M。最后研究基于此复合核权重矩阵的聚类,得到了很好地实验效果。

复合核函数的本质就是将K个核函数组合起来,事实上任一函数只要满足Mercer条件[14,15],就可以看作是一种核函数。假设一组基核函数{Km}Mm=1,则总函数定义如下:

其中αm为子核函数的权值,满足:

多核函数利用不同类型的核函数之间的优势互补,可以达到更好的效果。本文构造复合核权重矩阵的过程可分为以下流程:

1) RBF核函数改造

本文继续选用经典而常用的RBF核函数,不仅考虑到其良好的非线性映射性能,可以处理非线性可分情况,还因为该核函数也是欧氏距离的一种表示,体现了样本在特征空间里光谱亮度差异。

本文在RBF核函数的基础上进行一定的改进,得到了一种组合核函数。其具体实现为:

① 采用K近邻法构建有标记样本和无标记样本的近邻关系图G。若xi与xj为近邻,则在近邻关系矩阵G中有边连接,否则无边连接;

② 设置近邻关系矩阵G中边的权值矩阵W=[Wij]N×N,表达式如下:

2) 构造光谱角核函数权重矩阵

光谱角(SAM)是以运算影像像元的光谱与样本参考光谱之间的夹角来区分类别。其原理是把像元的光谱(多个波段的像素值)作为矢量投影到N维空间上,各光谱曲线被看作有方向且有长度的矢量,而光谱之间形成的夹角叫光谱角,光谱角分类法是依据光谱角的大小来进行分类的,而没有考虑光谱矢量的长度( 影像的亮度)。光谱角的数学表达式为

其中:θij为影像像元光谱与参考光谱之间的夹角,xi为影像像元光谱曲线矢量,xj为参考光谱曲线矢量。光谱角以很小的弧度角 θij来表示,它代表了光谱曲线之间大部分的光谱相似性。

本文构造光谱角核函数权重矩阵的方法为

①计算两两样本点之间的光谱角θij,具体方法参照式(7),得到一个光谱角信息的矩阵;

②设置近邻关系矩阵G中边的权值矩阵A=[Aij]N×N,表达式如下:

3) 构造复合核权重矩阵

至此,已得出本算法所用的两个基核分别构造的近邻矩阵:RBF核近邻矩阵W和光谱角核近邻矩阵A,将W和A加权构造复合核近邻矩阵M,在此复合权重矩阵的基础上进行聚类:

其中α 为子核函数的权值。可以发现,本文在构造基核时,只有当xj为xi的K近邻点时,才将其影响计入权重矩阵W或A中,即只考虑一个点的K近邻点对于该点的影响,K近邻之外的点忽略不计(对于矩阵W,K近邻通过排序欧式距离选取;对于矩阵A,K近邻通过排序光谱角值选取),即在计算权重矩阵时只对某点的K个近邻点构造近邻矩阵,而不是所有点,因此降低了计算量,提高了分类速度。此外,对于有标记的点,若xj与xi为同一类,则将Wij赋予一个较大的值1,xj与xi为异类时将Wij置零,这样做实际上是在构造核函数时进一步应用了数据的半监督信息,将有价值信息最大化。

3 实验与分析

3.1 实验设置

在实验中,选用两个高光谱遥感数据集,即Indian Pine和Botswana数据集,每类地物中分别随机标记5,10,... 50,55 个点,每次实验重复运行10 次,最终取分类精度的平均值。为尽可能减小环境因素对实验结果的影响,每次实验均将多种方法在同一数据集选取的相同样本点上依次进行。实验中对比的算法有K-means算法,FCM算法,SSGC算法(其参数设置为:式(1)中的RBF核宽度σ置为0.01,式(3)中用到的 β 置为0.99)。最后,本文提出的SSGCK算法参数设置为:近邻点数K设置为5。

由于本方法中用到了两个权重矩阵,两者的权重分配可能会影响分类正确率。本文通过调整子核函数权值α ,得到α 与分类正确率的关系图,如图1 所示。

由图1 可以看出,改变系数α 会对实验结果产生一定的影响,且α 为0.8∼0.9 时,分类效果最为理想。本文所用算法中将α 值设定为0.85。

3.2 Indian Pine数据集

为了验证本文算法的有效性,在仿真数据中首先采用目前国内外广泛采用的印第安纳(Indian Pine)高光谱遥感数据集进行测试实验,其假彩色图像如图2所示。该数据集的大小为145×145,共有220个波段以及17类已知地物类别。去除水汽吸收明显和低信噪比波段后,剩余200个波段用于实验,并从数据点较多的地物类别中随机选择6类进行实验。

图3 显示了不同方法在印第安纳数据集上分类结果,其中图3(a)为几种方法分类正确率与标记点数的关系,为了对比单核算法与复合核算法的效果,实验中也加入了SSGCK(α =0)与SSGCK(α =1)两种单核算法;图3(b)是几种方法运行时间对比。

由图3(a)可以看出,增加标记点数,SSGC和SSGCK方法分类正确率都稳步提升,且SSGCK方法正确率一直高于SSGC方法。同时复合核的SSGCK算法正确率优于单纯的RBF核算法(对应于图3 中SSGCK( α =1))和光谱角核算法(对应图3 中SSGCK( α =0))。较之于传统的FCM聚类算法、K-means算法,SSGCK算法正确率有大幅提升。

由图3(b)中数据可以看出,本文提出的SSGCK算法在运行时间上处于中等水平,相对于传统方法没有优势,但相对于原来的SSGC方法,时间大大缩短,改善效果显著。

图3不同方法在印第安纳数据集上分类结果(a)不同方法的整体分类精度;(b)不同方法的运行时间Fig.3 Indian Pine hyperspectral data classification results by different methods(a)The overall classification accuracy of different algorithms;(b)Running time of different algorithms.

图4 是使用四种方法对印第安纳影像进行分类的结果。

以上实验结果显示,K-means,FCM算法分类结果较差,较多地物被误分,主要原因是这两种算法忽略了数据的全局结构,损失了较多信息。基于RBF核的SSGC算法在精度上优于K-means和FCM算法。而本文提出的半监督复合核图聚类算法将RBF核与光谱角核融合,取得的效果明显优于基于单一RBF核聚类方法,这是多核相对于单核的优势,单个核函数构成的核机器并不能应对诸如数据异构或不规则、样本规模巨大、样本不平坦分布等实际问题,而多核分类却能应对自如。

3.3 Botswana数据集

Botswana高光谱遥感影像数据集于2001 年5 月31 日由美国宇航局通过EO-1 卫星上高光谱传感器获得,该影像由1 476×256 个像素组成,包括波长为400 nm~2 500 nm共有242 个波段,空间分辨力达到30 m,光谱分辨力达到10 nm,覆盖了博茨瓦纳奥卡万戈三角洲地区长7.7 km的带状地带,去除受大气吸收和噪声影响的波段,将剩下的145 个(10~55,82~97,102~119,134~164,187~220)波段用于实验研究。图5 为Botswana高光谱遥感影像的假彩色图及其真实地物分布情况。

图6(a)显示实验中所用4 种方法在Botswana数据集上分类正确率与标记点数的关系,图6(b)显示在此数据集上不同方法运算时间对比。

由图6(a)可见,增加标记点数,半监督算法的准确率均逐步提升,显示了半监督方法对于先验知识的利用效果。同时SSGC算法与SSGCK算法准确率遥遥领先于传统算法,因为二者都用到了RBF核函数,RBF核能够进行非线性变换,将样本在一个维度更高的特征子空间中处理,足以应对复杂数据。而本文提出的SSGCK算法正确率一直优于SSGC算法,可提升1%∼4%,能更好地应对数据异构等问题。

图6(b)中,SSGCK算法相对于SSGC算法,实验运行时间大大缩短。原因是本文对RBF核函数进行了改造,删除了不必要的计算环节,而这些环节也是非常耗时的。

图6不同方法在Botswana遥感影像上分类结果(a)不同算法的整体分类精度;(b)不同方法的运行时间Fig.6 Botswana hyperspectral data classification results by different methods(a)The overall classification accuracy of different algorithms;(b)Running time of different algorithms

4 结语

本文提出了一种半监督复合核图聚类算法,该方法在构造近邻矩阵时,使用本文构造的组合核函数,取代原有的RBF核函数,实现对先验信息的高效利用;同时为突破单核函数的局限,本文又结合光谱角核函数,构造出复合核权重矩阵;最后又将K近邻方法引入近邻矩阵的构造过程,在没有引入Nyström方法的情况下大大提升了运算速度。实验结果验证了本文算法的有效性:在Indian Pine和Botswana数据集上分类结果显示,相对于传统K-means,FCM算法,准确率提升10%∼20%,相对于SSGC算法,可以提升1%∼4%;且相对于SSGC算法,分类时间下降显著。

核方法聚类 第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 内核方法和核函数

式中,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.