随着高光谱遥感技术的不断发展和成熟,高光谱遥感技术被运用到越来越多的领域,并在在军事侦查,矿产勘探侦测,农业、林业病虫害监测,渔业,畜牧业等方面都取得的很大突破,为我们的生活和工作带来了便利[1]。但是高光谱图像数据维度高、数据量大、有标签样本获取的代价高,在这种情况下很难准确估计遥感图像的地物统计分布。而分类是高光谱数据处理的重要研究内容,同时分类也是获取信息的一种手段。高光谱图像遥感图像的分类可以根据是否需要已知待分类图像的先验知识分为监督分类[2]、非监督分类、半监督分类[3]。
监督分类是指在分类之前,需要获取先验知识或者统计特征,再对样本进行分类的一种分类方法。非监督分类是指分类之前不需要获取相应的先验知识,仅仅根据待分类样本集中样本本身的相似性或者差异性进行分类。半监督分类则是介于监督分类和半监督分类之间的一种分类方法。在分类之前只需获得少量样本的先验知识,然后就能根据这些少量的统计特征对需要分类的样本进行分类。
监督分类效果好,分类精度高,但是需要获取大量的先验知识,数据处理速度慢;非监督分类不需要获取先验知识,数据处理速度快,但是分类效果不好,分类精度低;半监督分类只需要或者少量的先验知识,数据处理速度快,同时分类效果好,分类精度高。
支持向量机(SVM)[4-5]是基于统计学理论的机器学习理论,在模式分类领域应用广泛[6-8]。它以结构风险最小化为准则,遵循间隔最大化思想,构建一个分类平面。近年来支持向量机在高光谱遥感图像分类中同样得到了很大程度的应用,并且取得了很好的效果。2007年,Javadeva等[9]在标准支持向量机的基础上提出了孪生支持向量机(twin SVM,TSVM)。TSVM寻求2个非平行的最优分类超平面,使得每一个分类面靠近一类样本而远离其他类样本。邵元海等[10]在TSVM的基础上提出了孪生边界支持向量机(twin bound SVM,TBSVM),通过在目标函数的基础上增加正规化项的方式来实现结构风险最小化。其他的研究学者又提出了其他改进的TSVM[11-13],它们在鲁棒性、有效性和泛化性方面都有所提高。在TSVM的基础上,Kumar M A和Gopal M[14]在2009年提出了最小二乘孪生支持向量机(least squares twin SVM,LSTSVM)。LSTSVM在模型训练、解决不均衡问题、求解异或问题方面表现良好,已经成为机器学习领域的热点[15-16]。
聚类算法[17]是在一个数据集中,根据数据之间的相似性或者差异性进行重新划分或者重组的过程。简洁和效率高的K均值算法是聚类算法中运用最广泛的一种聚类方法。K均值算法是先选定K个初始的聚类中心,然后把剩下的像元按照距离的大小划分到距离该像元最近的聚类中心,再对每个聚类中心重新进行距离计算,直达该算法收敛,通过这个过程将数据集自动的划分成K个聚类[18]。
本文将K均值聚类算法和最小二乘孪生支持向量机相结合,先用聚类算法处理数据样本,达到缩减样本的目的,再把缩减之后的样本通过最小二乘孪生支持向量机进行分类。将二者结合之后可以充分体现各自的优势,在利用K均值算法对数据进行处理时不需要获取大量的先验知识,节省了大量的人力物力。将处理过的样本再进行分类时,在分类精度基本不变的前提下分类时间大幅度减少。
1 孪生支持向量机TSVM是是二分类器,分类原理是通过2个凸二次规划问题(quadratic programming,QP)[19-20]得到2个非平行的分类超平面,然后分别计算每个样本到2个超平面的垂直距离,最后根据样本与2个分类超平面之间垂直距离的大小决定样本的所属类别。把属于该分类面的样本定义为“+1”类,不属于该分类面的样本定义为“-1”类。图 1为TSVM的分类示意图,正方形和圆形分别代表“+1”类和“-1”类样本,2类样本对应的分类超平面分别为H1、H2。
TSVM是通过求解2个凸二次规划问题(QP)来获得2个分类超平面。
假设有n维数据集,其中“+1”类训练样本的数量为m1,“-1”类样本的数量为m2,则总的样本数量m=m1+m2。矩阵A表示“+1”类样本集,矩阵B表示“-1”类样本集。解决以下2个QP问题就可以求得TSVM分类器。具体的过程如下。
1) TSVM1分类器求解
$\begin{array}{l} \mathop {{\rm{min}}}\limits_{\mathit{\boldsymbol{\omega }}{^{(1)}},{\mathit{\boldsymbol{b}}^{(1)}}} \frac{1}{2}{\left( {\mathit{\boldsymbol{A}}{\mathit{\boldsymbol{\omega }}^{(1)}} + {\mathit{\boldsymbol{e}}_1}{\mathit{\boldsymbol{b}}^{(1)}}} \right)^{\rm{T}}}\left( {\mathit{\boldsymbol{A\omega }}{^{(1)}} + {\mathit{\boldsymbol{e}}_1}{\mathit{\boldsymbol{b}}^{(1)}}} \right) + {c_1}\mathit{\boldsymbol{e}}_2^{\rm{T}}q\\ \quad \quad {\rm{s}}.{\rm{t}}. - (\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{\omega }}^{(1)}} + {\mathit{\boldsymbol{e}}_2}{\mathit{\boldsymbol{b}}^{(1)}}) + q \ge {\mathit{\boldsymbol{e}}_2},{\rm{ }}q \ge 0 \end{array}$ | (1) |
2) TSVM2分类器求解
$\begin{array}{l} \mathop {{\rm{min}}}\limits_{{\mathit{\boldsymbol{\omega }}^{(2)}},{\mathit{\boldsymbol{b}}^{(2)}}} \frac{1}{2}{\left( {\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{\omega }}^{(2)}} + {\mathit{\boldsymbol{e}}_2}{\mathit{\boldsymbol{b}}^{(2)}}} \right)^{\rm{T}}}\left( {{\rm{ }}\mathit{\boldsymbol{B}}{\mathit{\boldsymbol{\omega }}^{(2)}} + {\mathit{\boldsymbol{e}}_2}{\mathit{\boldsymbol{b}}^{(2)}}} \right) + {\rm{ }}{c_2}e_1^{\rm{T}}q\\ \quad \quad {\rm{s}}.{\rm{t}}. - (\mathit{\boldsymbol{A}}{\mathit{\boldsymbol{\omega }}^{(2)}} + {\mathit{\boldsymbol{e}}_1}{\mathit{\boldsymbol{b}}^{(2)}}) + q \ge {\mathit{\boldsymbol{e}}_1},{\rm{ }}q \ge 0 \end{array}$ | (2) |
式中:ω(1)、ω(2)∈Rn,b∈R,e1、e2为全1列向量,e1=(1,1,…,1)T∈Rm1,e2=(1,1,…,1)T∈Rm2,c1、c2>0。
根据式(1)、(2) 可以得到2个对应的分类超平面,使得每一类样本都尽可能聚集在其对应的超平面周围。2个式子的第一项代表某一类样本点到其所对应的分类超平面的距离的平方和。因此,只要分类超平面距离某类样本尽可能的近,就可以使第一项达到最小。同时,约束条件要求此分类超平面距离另一类样本点的距离至少为1。式(1)、(2)2个目标函数的第二项表示误差变量的和应该最小。
最终得到分类超平面
$\left\{ \begin{array}{l} {\mathit{\boldsymbol{x}}^{\rm{T}}}{\mathit{\boldsymbol{\omega }}^{(1)}} + {\mathit{\boldsymbol{b}}^{(1)}} = 0\\ {\mathit{\boldsymbol{x}}^{\rm{T}}}{\mathit{\boldsymbol{\omega }}^{(2)}} + {\mathit{\boldsymbol{b}}^{(2)}} = 0 \end{array} \right.$ | (3) |
一个新样本点所对应的样本类别则取决于样本点与2个平面的距离大小(属于距离较小的样本类别):
${\mathit{\boldsymbol{x}}^{\rm{T}}}{\mathit{\boldsymbol{\omega }}^{(r)}} + \mathit{\boldsymbol{b}}{^{(1)}} = \mathop {{\rm{min}}}\limits_{l = 1,2} \left| {{\mathit{\boldsymbol{x}}^{\rm{T}}}{\mathit{\boldsymbol{\omega }}^{(l)}} + \mathit{\boldsymbol{b}}{^{(l)}}} \right|$ | (4) |
式中·是x到分类平面xTω(l)+b(1)=0, l=1, 2的垂直距离。
2 K均值聚类算法聚类算法是根据样本集内样本的自身特性,按照样本之间的相似性或者是相异性,并用数学的方法将相似性或者相异性定量的表示,然后按照相似或相异程度进行聚类划分。样本经过聚类之后可以使属于同一类的样本间的相似度最大,同样使得不属于同一类的样本间相异度达到最大。
K均值(K-means)算法是由Mac Queen在1967年提出的聚类算法的一种经典算法。K-means算法的核心思想是找出K个样本点,然后将剩下的样本点依据到选取的K个样本点距离的大小,分别归类。
下面是K均值算法的步骤(以对n个样本进行分类为例):
1) 随机找出K个样本点作为初始的聚类中心;
2) 剩下的样本点根据其到个初始聚类中心距离的大小,划分到距离最小的聚类中心,并标明所属的类别;
3) 将每一个样本根据步骤2) 的结果,移动到对应的聚类中心,并计算偏差D;
4) 若D收敛,则终止该算法并返回结果;否则返回到步骤2),直至偏差D收敛。
3 K-LSTSVM算法在TSVM的基础上运用最小二乘的方法,可以把求解2个QP的问题转化为求解一个线性方程组的问题。可以比较容易地获得2个对应的分类超平面。具体的做法是把TSVM问题中原始的2个凸二次规划问题修改为最小二乘的形式,并用等式约束来代替TSVM中的不等式约束,这就是就是最小二乘孪生支持向量机(LSTSVM)。
相对于需要求解2个较为复杂的凸二次规划问题的TSVM,LSTSVM,只需要求解2个或者3个维数较小的矩阵的逆就可以解决分类问题。不论是运算复杂度还是向量机所需的分类时间都有大幅度下降。
同时在处理数据、解决分类问题以及求解超平面的过程中,我们发现决定该样本是否属于某一分类面时,不属于此分类面的样本数量远远大于属于该分类面的样本数量,如果要对这些样本全部进行分类则需要耗费大量的时间,而且并不是所有样本对最终分类面的确定都有很大的贡献,存在样本的大量冗余现象。因此在对样本分类以及分类超平面确定的过程中对冗余样本的缩减就显得很有必要。
本文基于一对余分类器的最小二乘孪生支持向量机的基础上进行改进,对于不属于该分类超平面以及对最终分类超平面的确定贡献较小的冗余样本,提出了一种基于K均值聚类算法的样本缩减方法。
该方法是结合提出的最小二乘孪生支持向量机和K均值聚类算法对这些大量的冗余样本进行聚类,达到缩减样本的目的。即基于K均值聚类的孪生支持向量机半监督分类(K-LSTSVM)方法,能在分类精度基本不受影响的前提下大大缩短分类器的分类时间,从而有效提高LSTSVM的分类效率。假设对于一个分类面来说属于它的样本为“+1”类样本,不属于该分类面的的样本为“-1”类样本。具体的分类步骤为:
1) 从数据库中提取训练样本,并将正负样本分开,计算出各分类器对应的“-1”类样本的数量;
2) 根据样本缩减率设置K均值聚类算法中的K值,然后通过该算法进行样本缩减;
3) 把缩减之后的样本按照对应的分类器进行整理,形成新的训练样本集;
4) 把分类器原来的“+1”类训练样本集与样本缩减后的“-1”类训练样本集重新组合,形成新的样本集,再对LSTSVM分类器进行训练和分类。
4 实验结果与分析 4.1 实验数据采用印第安农林遥感数据集和帕维亚大学遥感数据集这2个数据集进行仿真。其中的印第安农林数据集是1992年6月在美国印第安纳州新北部获得的,包含20 736个像元,224个波段。普度大学提供了220个波段,因噪声和水吸收等去除20个波段。本实验共采用200个波段,数据集示意图如图 2(a)所示。另外一个数据集来自截取之后的自帕维亚数据集,包含207 400个像元、103个波段、8个地物类别。数据图示意图如图 2(b)所示。
本实验所用电脑处理器为AMD Sempron(tm) X2 Processor 2.50 GHz;安装内存(RAM)为4.00 GB;系统类型为64位Windows7操作系统;仿真软件为MABLAB2010b。
4.3 评价准则高光谱图像的分类结果精度的评价准则都是从混淆矩阵获得的,混淆矩阵的具体形式为
$\mathit{\boldsymbol{M}} = \left[ {\begin{array}{*{20}{c}} {{m_{11}}} & {{m_{12}}} & \cdots & {{m_{1N}}}\\ {{m_{21}}} & {{m_{22}}} & \cdots & {{m_{2N}}}\\ \vdots & \vdots & \, & \vdots \\ {{m_{N1}}} & {{m_{N2}}} & \cdots & {{m_{NN}}} \end{array}} \right]$ | (5) |
式中:mij(i=1, 2, …, N;j=1, 2, …, N)表示原本属于i类被错误的分类为j类的总像元个数,N为所有类别的总个数。mii(i=1, 2, …, N)为被准确划分类所属类别的像元数,mii越大则说明分类精度越高。通过混淆矩阵可以获得另外2个评价分类精度的指标:总体分类精度(overall accuracy,OA)和Kappa系数(k)。
OA的计算方法为
$A = \frac{1}{n}\sum\limits_{i = 1}^N {{m_{ii}}} $ | (6) |
式中:N为总的类别数,n为测试样本总数。A的值越大说明分类效果越好。
Kappa计算方法为
$k = \frac{{n\sum\limits_{i = 1}^N {{m_{ii}}} - \sum\limits_{i = 1}^N {{m_{i + }}{m_{ + i}}} }}{{{n^2} - \sum\limits_{i = 1}^N {{m_{i + }}{m_{ + i}}} }}$ | (7) |
式中:+表示将相应行或列的值求和,n是总的测试样本个数。Kappa系数可以定量地评价分类器的总体有效性,Kappa系数值越高则说明分类效果越好。
为了说明本文所提方法的有效性,在印第安农林和帕维亚大学这2个遥感数据集的基础上进行仿真实验。分别进行LSTSVM分类和基于K均值的LSTSVM分类。对每一个数据集的仿真实验都设置3个不同的提取率来提取训练样本。相同的训练样本主要分为2个部分,第一部分是提取几种样本的全部作为LSTSVM训练样本,在训练样本相同的基础上观察2种分类方法Kappa系数、总体分类精度(OA)、分类时间(t)的差异。实验中所涉及的核函数采用的是高斯径向基核函数,LSTSVM中的参数通过网格搜索法获得最佳结果。
4.4 AVIRIS高光谱图像数据实验对于印第安纳农林数据选取的训练样本提取率分别为5%、10%、20%,在每个提取率的基础上分别比较2种方法的分类时间、总体分类精度、Kappa系数。表 1是分类结果。
图 3~5是印第安纳农林数据在不同训练样本提取率下的3种评价准则。
从图中可以看出,随着样本提取率的增加,2种分类方法的分类时间、总体分类精度、Kappa系数都随着增加;在同一提取率下,K-LSTSVM的OA、Kappa系数都比对应的LSTSVM要低,但是OA和Kappa的下降幅度较小,OA分别下降了1.21%、1.15%、0.83%;Kappa分别下降了1.14%、1.37%、1.04%。基本不影响分类结果,但是K-LSTSVM的分类所需时间与LSTSVM相比较却大大降低,分别下降了62.50%、25.27%、61.23%。可以说明K均值聚类算法与孪生支持向量机结合的分类算法在基本不影响分类结果的情况下可以大幅度缩短分类所需时间。图 6表示2种分类方法在不同样本提取率下的真实地物分类结果。
对与帕维亚大学数据,选取的训练样本提取率分别为5%、10%、20%,在每个提取率的基础上分别比较2种方法的分类时间(time)、总体分类精度(OA)、Kappa系数。表 2是分类结果。
图 7~9是帕维亚大学数据在不同训练样本提取率下的3种评价准则。从图中可以看出,随着样本提取率的增加,2种分类方法的分类时间、总体分类精度、Kappa系数都随着增加,在同一提取率下,K-LSTSVM的OA、Kappa系数都比对应的LSTSVM要低,但是OA和Kappa的下降幅度较小,OA分别下降了9.99%、1.58%、2.86%;Kappa分别下降了8.77%、6.20%、1.48%,基本不影响分类结果。但是K-LSTSVM的分类所需时间与LSTSVM相比较却大大降低,分别下降了51.70%、51.51%、53.71%。可以说明K均值聚类算法与孪生支持向量机结合的分类算法在基本不影响分类结果的情况下可以大幅度缩短分类所需时间。图 10表示2种分类方法在不同样本提取率下的真实地物分类结果。
1) 本文提出的基于K均值聚类算法的改进算法可通过控制样本缩减率,有效减少样本数量;
2) 缩减后的样本应用于孪生支持向量机可降低计算复杂度;
3)K均值算法和孪生支持向量机结合可以在基本不改变分类精度的前提下大幅度缩短分类时间。
本文在分类的时候只结合了图像的光谱信息,在接下来的研究工作中,可以考虑充分利用空间信息,进一步的提高分类精度。
[1] | 童庆禧, 张兵, 郑兰芬. 高光谱遥感[M]. 北京: 高等教育出版社, 2006. (0) |
[2] | ZHANG D, ZHOU Z, CHEN S. Semi-supervised dimensionality reduction[C]//Proceedings of the 7th International Conference on Data Mining, Omaha:USA, 2007:629-634. (0) |
[3] | CHAPELLE O, SCHOLKOPF B. Semisupervised learning[M]. Cambridge: MIT Press, 2006. (0) |
[4] | 王立国, 张晔, 谷延锋. 支持向量机多类目标分类器的结构简化研究[J]. 中国图象图形学报:A辑, 2005, 10(5): 571-574. (0) |
[5] | CRISTIANINI N, SHAWE-TAYLOR J. 支持向量机导论[M]. 李国正, 王猛, 曾华军, 译. 北京: 电子工业出版社, 2004: 50-55. (0) |
[6] | BAYRO-CORROCHANO E J, ARANA-DANIEL N. Clifford support vector machines for classification, regression, and recurrence[J]. IEEE trans on neural networks, 2010, 21(11): 1731-1746. DOI:10.1109/TNN.2010.2060352 (0) |
[7] | ERTEKIN S, BOTTOU L, GILES C L. Nonconvex online support vector machines[J]. IEEE transactions on pattern analysis and machine intelligence, 2011, 33(2): 368-375. DOI:10.1109/TPAMI.2010.109 (0) |
[8] | ZHANG, Yunsheng, ZHANG Yongfei. Adaptive resource allocation with svm-based multi-hop video packet delay bound violation modeling[J]. Chinese journal of electronics, 2011, 20(2): 261-267. (0) |
[9] | JAYADEVA, KHEMCHANDANI R, CHANDRA S. Twin support vector machines for pattern classification[J]. IEEE trans on pattern analysis and machine intelligence, 2007, 29(5): 905-910. DOI:10.1109/TPAMI.2007.1068 (0) |
[10] | SHAO Y H, ZHANG C H, WANG X B, et al. Improvements on twin support vector machines[J]. IEEE trans neural netw, 2011, 22(6): 962-968. DOI:10.1109/TNN.2011.2130540 (0) |
[11] | QI Z, TIAN Y, SHI Y. Robust twin support vector machine for pattern classification[J]. Pattern recognition, 2013, 46(1): 305-316. DOI:10.1016/j.patcog.2012.06.019 (0) |
[12] | PENG X, XU D. Bi-density twin support vector machines for pattern recognition[J]. Neurocomputing, 2013, 99(1): 134-143. (0) |
[13] | YE Q, ZHAO C, GAO S, et al. Weighted twin support vector machines with local information and its application[J]. Neural networks the official journal of the international neural network society, 2012, 35(11): 31-39. (0) |
[14] | FUNG G, MANGASARIAN O L. Proximal support vector machine classifiers[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2001:77-86. (0) |
[15] | MANGASARIAN O L, WILD E W. Multisurface proximal support vector machine classification via generalized eigenvalues[J]. IEEE transactions on pattern analysis and machine intelligence, 2005, 28(1): 69-74. (0) |
[16] | JAYADEVA, KHEMCHANDANI R. Twin support vector machines for pattern classification[J]. IEEE transactions on pattern analysis and machine intelligence, 2007, 29(5): 905-910. DOI:10.1109/TPAMI.2007.1068 (0) |
[17] | KUMAR M A, GOPAL M. Least squares twin support vector machines for pattern classification[J]. Expert systems with applications, 2009, 36(4): 7535-7543. DOI:10.1016/j.eswa.2008.09.066 (0) |
[18] | MELESSE A M, JORDAN J D. A comparison of fuzzy vs. augmented-ISODATA classification algorithms for cloud-shadow discrimination from Landsat images[J]. Photogrammetric engineering & remote sensing, 2002, 68(9): 905-911. (0) |
[19] | WAGSTAFF K, CARDIE C, ROGERS S, et al. Constrained K-means clustering with background knowledge[C]//Eighteenth international conference on machine learning. San Francisco:Morgan Kaufmann Publishers Inc. 2001:577-584. (0) |
[20] | MANGASARIAN O L. Nonlinear programming[M]. SIAM, 1994:5-10. (0) |