多流形LE算法在高光谱图像降维和分类上的应用

吴东洋， 马 丽

(中国地质大学(武汉)机械与电子信息学院，武汉 430074)

0 引言

流形学习方法于2000年在著名的科学杂志被首次提出，它假设数据均匀采样于一个高维欧氏空间中的低维流形。流形学习的过程就是从高维采样数据中恢复低维流形结构，并求出相应的低维数据的过程。经典的流形学习方法主要有等距特征映射[1]、拉普拉斯特征映射(Laplacian eigenmaps，LE)[2]、局部线性嵌入[3]和局部切空间对齐[4]等，这些流形学习方法都可以在图嵌入框架下进行描述[5]，不同的流形学习算法对应不同的图结构。

传统的流形学习算法均假设不同类的数据位于同一个流形上(单流形假设)，然而不同类的数据特征不同，不同类的数据位于不同流形上的假设(多流形假设)更加合理。近些年来，许多基于多流形假设的流形学习方法被提出，2011年Xiao等[6]提出了一种有监督的多流形分类方法，利用局部保持映射算法[7]计算得到每一类有标签点数据的映射矩阵，分别计算经过映射后未知标签点数据被每一类有标签点数据重构的误差，选择误差最小的类别作为未标签点的类别。2014年Huang等[8]提出了一种多层流形的概念，根据类别之间的关系建立树形结构，确定父流形和子流形，数据点之间的相似性权值取决于数据点所在流形结构之间的相似性。谱聚类算法[9]是一种基于图论的聚类方法，其求解过程是先进行LE算法的降维，然后对降维结果进行K均值聚类，由于传统的LE算法没有考虑到数据的多流形特性，在图构造过程中点间的权值度量不准确，为了解决这个问题，2011年Wang等[10]提出了一种多流形谱聚类(spectral clustering on multiple manifolds，SMMC)算法，利用有限个局部线性块去拟合整个非线性流形结构，将计算2个点之间的相似性转换成计算2个点所在线性块之间的相似性，从而得到更准确的相似性度量。

基于多流形假设，不同类地物的高光谱数据应该位于各自不同的流形结构上，因此基于单流形假设的流形学习算法并不能体现高光谱数据的多流形特征。SMMC算法主要是对LE算法中权值计算不准确问题的改进，本文将这种改进后的LE算法称为多流形LE算法,并将之应用到高光谱数据的降维上，相比于传统的LE算法，多流形LE算法更加符合高光谱数据的特点。由于高光谱数据自身的同谱异类[11]等现象，直接应用多流形LE算法会出现局部线性块不纯和块间相似性度量不准确的问题，本文分别利用高光谱遥感图像的空间信息和标签信息来解决这2个问题，并与传统的LE算法及未经改进的多流形LE算法进行对比。

1 多流形LE算法

1.1 LE算法

LE算法是一种局部流形学习方法，目的是保持降维前后数据的局部邻接关系，即高维空间中距离近的2个点在低维空间距离同样很近。设原高维数据为X=[x1,…,xN]T∈RN×M，其中，xi(i=1，2，...，N)为样本点数据；N为样本个数；M为原高维数据的维数。设降维后的数据为Y=[y1,…,yN]T∈RN×m，其中，yi(i=1，2，...，N)为xi降维后的结果；m为降维后的维数。定义邻接矩阵为W∈RN×N，W的计算主要包括近邻选择和权值计算2个步骤，即首先利用欧氏距离或光谱角距离等距离度量方式得到数据点的一个领域； 然后利用热核函数或者二值化策略计算得到数据点与其近邻点之间的权值，由热核函数计算得到。定义拉普拉斯矩阵L为

L=D-W，

(1)

(2)

(3)

式中σ为实参数。

对于降至一维的情况(m=1)，LE算法的目标函数为

(4)

式中Wij的值为xi和xj之间的权值，权值越大，说明2点越相似。如果Wij的值很大，根据式(4)的约束，yi-yj趋近于0，即和高维数据点xi和xj相对应的低维数据yi和yj也很相似，从而保持了降维前后数据的局部邻接关系。取p的值为1，通过对目标函数的化简和优化，对式(4)的求解就转换成为对式(5)的广义特征值求解。式(5)中λ是特征值，降维结果y就是最小非0特征值对应的特征向量，即

Ly=λDy。

(5)

将降维过程由一维扩展至多维，LE算法的目标函数表示为式(6)，其中P为m维的常数向量，此时的降维数据Y为m个最小的非0特征值对应的特征向量。

(6)

对于高光谱遥感数据，不同类别数据点可能具有相似的光谱特征(异类同谱)，导致LE算法近邻选择不准确，即目标点的邻域中有和目标点不同类别的点，此时2个异类点之间的权值本应该为0，然而由于2点光谱相似，从而得到一个比较大的权值。因此，在近邻选择错误的情况下，如何正确度量2个异类点之间的相似性(减小异类点之间的权值)是对LE算法的一个改进方向，这也是下面多流形LE算法主要解决的问题。

1.2 多流形LE算法

多流形LE算法假设不同类别的数据位于不同的流形结构上，图邻接矩阵中权值的计算不是基于数据点之间的光谱相似性，而是基于数据点所在的局部流形结构的相似性，能够更真实地反映数据之间的关系。多流形LE算法采用数据的局部切空间表示数据的局部结构，由于位于同一个流形上的点之间的局部切空间是相似的，而位于不同流形上的点之间的局部切空间是不相似的，因此数据点的局部切空间信息可以用于度量2个点之间的相似性。相比较LE算法，多流形LE算法将度量2个点之间的相似性转变为度量2个点局部切空间信息之间的相似性。局部切空间信息的计算方法主要分为2步： ①计算得到数据点xi的一个领域，计算该邻域内数据点集的协方差矩阵； ②对该协方差矩阵进行奇异值分解，xi的局部切空间信息就是d个最大的左奇异值对应的奇异向量，d为参数，表示局部切空间维数。

由于整体的流形结构具有全局非线性、局部线性的特点，因此可以找到有限多个小的局部线性块来近似整个非线性的流形结构，数据点xi的邻域就是其所在块中所有数据点的集合。因此，找到有限多个局部线性块变得非常关键，借鉴高斯混合模型思想，即任意数据分布都可用高斯混合模型(有限多个单高斯模型)来表示。

首先，利用K均值聚类算法得到Z(Z>0)个初始聚类块(Z个初始的聚类块可以看成高斯混合模型里面的Z个单高斯模型)； 然后，分别计算每个数据点和Z个初始聚类块之间的边缘概率分布，利用期望最大化算法进行迭代寻优； 最后，得到的Z个聚类块就是可以用来近似整个流形结构的局部流形结构。

在得到Z个线性块之后 ，计算每个线性块的切空间信息，此时每个数据点的局部切空间信息就是该点所在线性块的切空间信息。式(7)中Qij为xi和xj间切空间信息的相似性，即

(7)

式中：ο为调整参数；d为特征空间大小；Θi为第i个点的局部切空间信息，即第i个点所在线性块的切空间信息；θl为2个切空间对应奇异向量之间的角度，cos(θl)的计算式为

(8)

式中ul和vl分别为2个局部切空间的主成分向量。

综上，多流形LE算法步骤为： ①计算得到有限多个局部线性流形块来近似整个非线性的流形结构，计算每个块的切空间信息； ②计算得到邻接矩阵W； ③由邻接矩阵W计算得到拉普拉斯矩阵L，利用式(6)计算得到降维结果。

2 改进的多流形LE算法

2.1 多流形LE算法存在的问题

多流形LE 算法处理高光谱数据时存在2个方面问题： ①局部线性块不纯，局部线性块基于K均值算法和最大后验概率方法得到，由于高光谱图像的异类同谱特点，同一个聚类块中可能存在不同类别的数据； ②同类点的局部切空间之间的权值计算不准确，通常同类数据点的局部切空间应该非常相似，其之间的权值也较大，而实际得到的权值很小。以上2个问题均导致数据点间权值度量不准确，最终影响图结构的准确性。

2.2 多流形LE算法改进

2.2.1 结合空间信息提高块纯度

图像中每一个像素点都有空间位置上的意义，互为空间近邻的像素点通常属于同一种类别地物，因此可以借助空间近邻点的光谱信息来弥补自身光谱不能完全反映类别信息的不足，从而增大了不同类别数据之间的光谱差异，解决局部线性块不纯的问题。一个像素点的光谱特征可以由其空间邻域的光谱信息来表示，即

(9)

式中：α为实参数；Xi(i=1，2，3，...，r)为Xt的空间近邻点；r为空间近邻点数，当空间窗口取3×3时，r=8。由式(9)可知，Xt的光谱被其周围8个空间近邻点的光谱均值与原光谱的一个加权和所替代，通过对所有的数据点进行同样的处理，得到一个新的带有空间信息的数据集，新数据集的不同类间光谱有了较大的差异，对比结果如图1所示。

(a) 未添加空间信息的光谱曲线 (b) 添加了空间信息的光谱曲线

图1添加空间信息前后的光谱曲线对比

Fig.1Comparionofspectralgraphwithspatialinformationaddedbeforeandafter

图1中的数据是经过归一化后的BOT高光谱数据，图1(a)中的2条曲线是2个不同类数据点的光谱曲线，2条光谱曲线非常相似； 图1(b)中的2条曲线是对原始的高光谱数据添加空间信息后的光谱曲线，可以发现，通过添加空间信息后2条原本非常相似的不同类的光谱曲线得到了比较好的区分。对新的数据集合进行分块处理，块的纯度得到了很大提高。

2.2.2 结合标签信息改进同类点间的相似性度量

利用有限的标签信息部分解决同类点的局部切空间之间的权值计算不准确的问题。如果块中存在有标签的数据点，则为线性块赋予类别具有以下3种情况(图2)。

(a) 块类别为1类 (b) 块类别为2类 (c) 块没有类别

图2为块赋类别

Fig.2Assignclassestoblocks

当块中只有1个类别的标签点时，此时将这个类别赋给块，如图2(a)所示； 当块中有2个及2个以上类别的标签点时，则将点数多的类别赋给块，如图2(b)所示； 当块中不同类别的点数相同时，则不给块赋类别，如图2(c)所示。如果2个块的类别相同，将不考虑利用切空间计算得到的块间权值，而是人为的设置2个块之间的权值为1，如果2个块仅其中之一有类别或者2个块均没有类别，则仅仅利用2个块的切空间计算块间权值。

3 实验结果与分析

3.1 数据描述

本文实验采用3种高光谱数据，分别为采集于Okavango Delta的Botswana地区BOT数据、美国Kennedy Space Center地区的KSC数据和意大利University of Pavia地区的PU数据。BOT数据的光谱范围为357～2 576 nm，具有10 nm的光谱分辨率和30 m的空间分辨率，包括了145个波段，共获取了9类地物的1 580个类别标记数据。KSC数据的光谱范围为400～2 500 nm，具有10 nm的光谱分辨率和18 m的空间分辨率，包括了167个波段，共获取了13类地物的5 211个类别标记数据。PU数据的光谱范围为430～860 nm，具有10 nm的光谱分辨率和1.3 m的空间分辨率，包括了103个波段，共获取了9类地物的42 776个类别标记数据。

在本文实验中，将用到BOT数据全部1 580个有标签数据点，考虑到KSC数据和PU数据的数据量较大，实验中采用的是从KSC数据的每类数据中随机选取30%(共1 564个数据点)和从PU数据的每一类数据中随机选取5%(共2 138个数据点)的高光谱数据。

3.2 实验设计和结果分析

实验对比4种算法，分别是LE，多流形LE(multi-manifold LE,MLE)，MLE_Spatial和MLE_Spatial_Label算法。其中，LE算法是传统的流形学习方法，采用热核函数度量2个点之间的权值； MLE_Spatial是在MLE算法的基础上，通过添加空间信息来提高了线性块的纯净度； MLE_Spatial_Label算法是在MLE_Spatial算法的基础上，通过利用有标签信息来解决同类线性块之间的权值度量问题。

利用k最近邻(k nearest neighbor，kNN)算法衡量以上4种对比算法的性能，设置kNN分类器中的k值为1，分别选取每个类别的10%，30%和50%这3种比例的数据依次作为训练数据，剩下的为测试数据，计算在不同比例训练数据下4种算法的效果。由于4种对比算法都涉及到图的构造问题，遍历图构造中的领域值K为5，10，15和20这4个值。对于LE算法，遍历热核函数中参数σ的值为0.1，0.4，0.7和1这4个值。MLE，MLE_Spatial和MLE_Spatial_Label算法均涉及分块问题，通过分析前期的实验结果，分别为不同的数据遍历了不同的块数。MLE_Spatial和MLE_Spatial_Label算法均有空间信息的添加，通过分析前期的实验结果，取BOT数据的空间窗口为3×3，α为20，KSC数据的空间窗口为5×5，α为12，PU数据的空间窗口为5×5，α为20。为减少偶然性，在同一组参数下进行10次重复试验，通过计算10次重复试验的总体分类精度的平均值来最终说明在这组参数下算法的效果。

表1—3为4类对比算法分别在BOT数据、KSC数据和PU数据上通过以上参数遍历寻优后得到的实验结果。

表1 不同算法在BOT数据上的最优总体分类精度Tab.1 Optimal accuracy of different algorithmson BOT data

表2 不同算法在KSC数据上的最优总体分类精度Tab.2 Optimal accuracy of different algorithmson KSC data

表3 不同算法在PU数据上的最优总体分类精度Tab.3 Optimal accuracy of different algorithmson PU data

从表1—3中可知，MLE的效果普遍优于LE，这说明相比于传统的图结构中权值的构造方法，基于多流形分块思想计算权值的方法更加合理； MLE_Spatial全部优于MLE并且分类精度高出很多，说明添加空间信息提高块纯净度的作用非常明显； MLE_Spatial_Label全部优于MLE_Spatial并且分类精度提高更加明显，说明通过对标签信息的添加，在一定程度上解决了同类块之间权值度量不准确的问题。

图3是4种算法在不同数据不同类上的正确率对比，可以发现LE，MLE，MLE_Spatial和MLE_Spatial_Label的正确率在BOT数据的每一类别上均逐步提升； 而在KSC和PU数据上，虽然总体上也能反映出上面的规律，但在某些类别上并不符合，这和不同类别本身的数据特征有关系。这表明BOT数据的各类别间的区分性较好，而PU和KSC数据有些类之间的区分性并不好。对于区分性不好的PU和KSC数据，MLE最后的分类准确率并不比LE高，而MLE_Spatial和MLE_Spatial_Label在添加空间信息时，由于空间窗口选择都是5×5，虽然提高了块的纯度，但是容易把异类点的光谱考虑进来，从而影响最后的分类精度。

(a) BOT数据 (b)KSC数据 (c) PU数据

图3不同数据各类的分类精度

Fig.3Classificationaccuracyoffourkindsofalgorithmsindifferentkindsofdata

3.3 参数分析

为了定量地描述空间信息对提高块纯度的作用，定义度量块纯净度的策略： 如果一个块中所有点的类别都是相同的，那么这个块称为纯净块，否则为不纯净块，以所有纯净块中的数据点数量(纯净点数)来度量局部线性块的效果。表4—6为BOT，KSC和PU这3种数据不添加空间信息和添加了空间信息时不同块数下的纯净点数，可以发现，相比于未添加空间信息时的纯净点数，添加空间信息后的纯净点数明显提高。

表4 BOT数据(1 580个点)不同块数对应的纯净点数Tab.4 Pure points of different number of blocks on BOT data (个)

表5 KSC数据(1 870个点)不同块数对应的纯净点数Tab.5 Pure points of different number of blockson KSC data (个)

表6 PU数据(2 138个点)不同块数对应的纯净点数Tab.6 Pure points of different number of blockson PU data (个)

当块数较少时，块中含有异类点的概率增加，从而影响了图构造的准确性，最终影响到分类准确率。然而并不是块数越多分类效果就越好，块数越多，平均每个块中的点数就越少，较少的点数将无法有效地表示块的流形结构，同样不利于分类，因此总体分类精度会随着块数的增加呈现先增加后下降的趋势。如图4所示，其中邻域值K为5，比例为10%。从图4中发现，添加空间信息后的分类精度曲线变化更加剧烈，这是因为当数据添加空间信息后，类内聚合程度增大。以KSC数据为例，其中圆形数据点是菱形数据在添加了空间信息的基础上整体向右平移得到的，如图5所示。分块过程对类内聚合度高的数据更加敏感，分类精度曲线的变化更加剧烈。另外，MLE_Spatial和MLE_Spatial_Label算法涉及到空间窗口和原始光谱权重θ这2个参数，空间窗口设置的原则是越小越好，因为随着空间窗口的增大，异类点被选择的概率会增大，从而影响到光谱的准确性。当空间窗口为3×3时BOT数据的效果已经很好，因此本文没有尝试更大的窗口，对于KSC数据和PU数据，空间窗口为3×3时的实验效果并不理想，因此选择5×5的空间窗口。α的选取是通过大量前期的试验结果得到的。

(a) BOT数据 (b) KSC数据 (c) PU数据

图4不同块数下的分类精度

Fig.4Accuracyunderdifferentblocks

(a) KSC第5类数据 (b) KSC第2类数据

图5同一类数据在添加空间信息前后2个波段的数据分布

Fig.5Distributionofsamekindofdataintwobandsbeforeandafterspatialinformationadded

图6分别是3种数据在10%的训练数据下不同的K值对应的总体分类精度。从图中可以发现，随着K值的增大，MLE和LE算法的分类精度呈现下降的趋势，而MLE_Spatial和MLE_Spatial_Label算法的分类精度呈现上升的趋势。随着K值的增大，领域范围在逐渐变大，邻域中包含异类点的概率也增大，由于LE和MLE算法并不能很好地度量异类点之间的权值，因此效果将会变差，而改进后的多流形LE算法可以较好地度量异类点之间的权值，在一定的范围内，K值越大，领域中的点数就越多，从而可以更好地表示局部流形结构，效果也随之提高。

(a) BOT数据 (b) KSC数据 (c) PU数据

图6不同邻域大小的最优分类精度

Fig.6Accuracyofclassificationwithdifferentvaluesoftheneighborhood

4 结论

1)借鉴SMMC算法中的多流形思想并将多流形LE算法应用到高光谱数据的降维中，实验结果表明多流形LE算法比传统的LE算法有更好的效果，说明了多流形假设更加符合高光谱数据的数据特征。

2)针对高光谱数据自身的特点，利用空间信息和标签信息对多流形LE算法进一步改进，实验结果表明改进后的多流形LE算法相比于原多流形LE算法有了明显的提高，说明本文基于高光谱数据特点的多流形LE算法的改进具有实际意义。

本文的不足之处是在处理同类块间权值度量不准确的问题时方法比较僵硬，如何更加灵活高效地解决这个问题是下一步需要继续研究的课题。

参考文献(References)：

[1] Tenenbaum J B,De Silva V,Langford J C.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2923.

[2] Belkin M,Niyogi P.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation,2003,15(6):1373-1396.

[3] Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.

[4] Zhang Z Y,Zha H Y.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J].Journal of Shanghai University (English Edition),2004,8(4):406-424.

[5] Yan S C,Xu D,Zhang B Y,et al.Graph embedding and extensions:A general framework for dimensionality reduction[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(1):40-51.

[6] Xiao R,Zhao Q J,Zhang D,et al.Facial expression recognition on multiple manifolds[J].Pattern Recognition,2011,44(1):107-116.

[7] He X F,Niyogi P.Locality preserving projections[C]//Advances in Neural Information Processing Systems.2003:186-197.

[8] Huang H B,Huo H,Fang T.Hierarchical manifold learning with applications to supervised classification for high-resolution remotely sensed images[J].IEEE Transactions on Geoscience and Remote Sensing,2014,52(3):1677-1692.

[9] 高 琰,谷士文,唐 琎,等.机器学习中谱聚类方法的研究[J].计算机科学,2007,34(2):201-203.

Gao Y,Gu S W,Tang J,et al.Research on spectral clustering in machine learning[J].Computer Science,2007,34(2):201-203.

[10] Wang Y,Jiang Y,Wu Y,et al.Spectral clustering on multiple manifolds[J].IEEE Transactions on Neural Networks,2011,22(7):1149-1161.

[11] 戴竹红,塔西甫拉提·特依拜.遥感影像中同谱异类问题的研究[J].中国科技信息,2006(20):278-280.

Dai Z H,Tashpolat·Tiyip.Research on same spectrum with different objects in remote sensing image[J].China Science and Technology Information,2006(20):278-280.