流形降維最小二乘回歸子空間分割

林智鵬，黃増裕，簡彩仁

(廈門大學(xué)嘉庚學(xué)院，福建 漳州 363105)

0　引言

模式識別研究的核心問題是識別，主要包括數(shù)據(jù)的分類與聚類。本文借鑒子空間分割方法對高維小樣本數(shù)據(jù)進(jìn)行聚類，其主要思路是將數(shù)據(jù)分割成不同的子空間進(jìn)而實現(xiàn)聚類。子空間分割方法可以粗略地分為迭代法、代數(shù)法、譜聚類法和統(tǒng)計法[1]。作為一種重要的聚類工具，子空間分割方法應(yīng)用于運動對象的分割、人臉識別及圖像分割等。常見的子空間分割方法包括稀疏表示子空間分割、最小二乘回歸子空間分割、低秩表示子空間分割以及它們的擴(kuò)展模型[1-4]。上述方法都是基于表示理論構(gòu)造樣本相似矩陣，然后應(yīng)用譜聚類方法對數(shù)據(jù)進(jìn)行聚類。

直接對高維數(shù)據(jù)進(jìn)行研究不僅使得傳統(tǒng)的模式識別方法難以適應(yīng)，還會造成內(nèi)存開銷問題，因此研究數(shù)據(jù)降維具有重要的意義。降維手段主要包括特征選擇和特征提取。特征選擇的主要思路是：從特征中選出對識別有利的特征；而特征提取是對原始數(shù)據(jù)通過數(shù)學(xué)方法將其變換到不同的空間，是特征重構(gòu)的一種方法。降維方法一直是模式識別的熱點問題，本文研究特征提取的降維技術(shù)，特征提取的降維方法主要分為非線性降維方法和線性降維方法，主成分分析是線性降維算法的典型代表，非線性降維算法的優(yōu)秀代表是流形降維，它是一種全局的降維算法，其代表有局部保持投影[5]等。

現(xiàn)有的子空間分割方法對高維小樣本數(shù)據(jù)進(jìn)行聚類時，會受到樣本非線性、高維數(shù)等特點的影響，難以達(dá)到理想效果。本文提出流形學(xué)習(xí)降維子空間分割方法對最小二乘回歸子空間分割方法進(jìn)行研究以提高聚類準(zhǔn)確率。該方法利用局部保持投影降維方法將樣本數(shù)據(jù)變換到新的低維空間后再實行最小二乘回歸子空間分割實現(xiàn)聚類。

1　子空間分割方法概述

基于最小二乘回歸子空間分割方法最小化Z的F-范數(shù):

最小二乘回歸子空間分割方法具有較強(qiáng)的魯棒性和良好的聚類性能，可以得到解析解，因此可以快速得到表示系數(shù)：

Z=(XTX+λI)-1XTX

由上式可以計算得到仿射矩陣：

最后利用標(biāo)準(zhǔn)化分割方法[6]即可完成數(shù)據(jù)的聚類。

2　流形降維最小二乘回歸子空間分割法

由于基因表達(dá)數(shù)據(jù)和圖像數(shù)據(jù)等高維小樣本數(shù)據(jù)具有高維數(shù)、多噪聲和非線性等特點，在原有的高維空間對這類數(shù)據(jù)進(jìn)行識別研究，基于線性理論的子空間分割方法難以適應(yīng)，因此有必要對原始高維樣本空間做變換得到低維的樣本數(shù)據(jù)。本文提出利用局部保持投影降維方法將樣本數(shù)據(jù)變換到新的低維空間后再實行最小二乘回歸子空間分割實現(xiàn)聚類。

2.1　局部保持投影降維

局部保持投影[5]是一種非線性的降維方法，該方法在原有數(shù)據(jù)結(jié)構(gòu)空間中保持局部流形結(jié)構(gòu)，是一種基于譜圖理論的學(xué)習(xí)方法。局部保持投影利用k近鄰關(guān)系構(gòu)造樣本的權(quán)圖。對數(shù)據(jù)集X∈Rm×n，有n個樣本和m個特征，其相似矩陣W定義為：

其中，Nk(xi)是xi的k個近鄰樣本構(gòu)成的集合。通過簡單的代數(shù)運算可以得到局部保持投影的目標(biāo)函數(shù)：

s.t.VTXDXTV=1

2.2　流形降維最小二乘回歸子空間分割算法

流形降維最小二乘回歸子空間分割方法利用局部保持投影降維方法將樣本數(shù)據(jù)變換到新的低維空間后再實行最小二乘回歸子空間分割。首先利用局部保持投影降維方法，將原始樣本X變換到新的低維空間得到低維樣本Xnew，接著對低維樣本Xnew實行最小二乘回歸子空間分割得到表示系數(shù)Z*，從而得到仿射矩陣(|Z*|+|Z*T|)/2，最后應(yīng)用標(biāo)準(zhǔn)分割方法將數(shù)據(jù)分成k個子空間。算法描述如下：

算法：流形降維最小二乘回歸子空間分割算法(LPP-LSR)

輸入：數(shù)據(jù)矩陣X，類數(shù)k，正則參數(shù)λ

輸出：k個類簇

(1)通過局部保持投影對數(shù)據(jù)X降維得到新的數(shù)據(jù)集Xnew；

(2)利用對Xnew實行最小二乘回歸子空間分割方法求表示系數(shù)Z；

(3)計算仿射矩陣 (|Z*|+|Z*T|)/2；

(4)應(yīng)用標(biāo)準(zhǔn)分割方法將數(shù)據(jù)分成k個子空間。

3　實驗分析

本節(jié)通過實驗驗證流形降維最小二乘回歸子空間分割法(LPP-LSR)的有效性，對比方法有最小二乘回歸子空間分割法(LSR)、主成分分析降維與最小二乘回歸子空間分割法結(jié)合的方法(PCA-LSR)、局部保持投影與K均值聚類結(jié)合的方法(LPP-Kmeans)，從多個角度分析本文提出方法的有效性。實驗環(huán)境為Windows 7系統(tǒng)，內(nèi)存為2 GB，所有的方法都是用MATLAB R2011b編程實現(xiàn)。

3.1　數(shù)據(jù)描述

選用6個公開的常用生物數(shù)據(jù)集ALLAML、Carcinom、GLIOMA、nci9、Lung_discrete、Prostate_GE和2個人臉圖像數(shù)據(jù)集ORL、Orlraws10P作為實驗研究對象，數(shù)據(jù)來源于http://featureselection.asu.edu/datasets.php，其主要信息如表1所示。

表1　數(shù)據(jù)集描述

所有數(shù)據(jù)集都標(biāo)準(zhǔn)化為具有單位L2范數(shù)，即用以下公式標(biāo)準(zhǔn)化:

其中，x表示一個樣本。

3.2　實驗結(jié)果與分析

采用聚類準(zhǔn)確率(ACC)來評價實驗結(jié)果。對于原有數(shù)據(jù)集，使用ri和si分別代表聚類算法得到的類標(biāo)簽和本身自帶的類標(biāo)簽，則該準(zhǔn)確率的計算公式[7]為：

其中，n為樣本總數(shù)；δ(x,y)是一個函數(shù)，當(dāng)x=y時，值為1，否則為0；map(ri)是一個置換函數(shù)，其將每一個類標(biāo)簽ri映射成與樣本自帶的類標(biāo)簽等價的類標(biāo)簽。

實驗的主要參數(shù)設(shè)置為主成分分析(PCA)保留比率90%，子空間分割方法的正則參數(shù)λ設(shè)為0.01，降維維數(shù)設(shè)為{20,40,60,80,100,120}。

圖1給出不同的對比方法在8個數(shù)據(jù)集上的聚類準(zhǔn)確率，可以看出，本文提出的流形降維最小二乘回歸子空間分割法(LPP-LSR)可以有效地改進(jìn)最小二乘回歸子空間分割方法的聚類準(zhǔn)確率。從圖1中各種不同方法在不同的降維維數(shù)下聚類準(zhǔn)確率的變化關(guān)系，可以發(fā)現(xiàn)除了在Carcinom和Prostate_GE數(shù)據(jù)集上，流形降維最小二乘回歸子空間分割法(LPP-LSR)具有明顯的優(yōu)勢。

圖1　不同方法的聚類準(zhǔn)確率

為更準(zhǔn)確地反映本文方法的有效性，表2給出了各種不同方法的平均聚類準(zhǔn)確率。從表2 不難看出，除了在Carcinom和Prostate_GE數(shù)據(jù)集上，都反映出流形降維子空間分割方法大幅度地提高了最小二乘回歸子空間分割方法的聚類準(zhǔn)確率。通過與最小二乘回歸子空間分割方法(LSR)對比(表2的第一列和第二列)，可以發(fā)現(xiàn)利用局部保持投影降維可以有效去除噪聲，提高聚類準(zhǔn)確率。通過與主成分分析降維與最小二乘回歸子空間分割法結(jié)合的方法(PCA-LSR)對比(表2的第一列和第三列)，反映出流形降維方法比傳統(tǒng)的線性降維更適合高維小樣本數(shù)據(jù)的聚類。通過與局部保持投影與K均值聚類結(jié)合的方法(LPP-Kmeans)對比(表2的第一列和最后一列)，發(fā)現(xiàn)最小二

乘回歸子空間分割方法比傳統(tǒng)的K均值聚類方法具有明顯的優(yōu)勢。從不同的角度進(jìn)行對比分析，發(fā)現(xiàn)流形降維子空間分割方法(LPP-LSR)可以得到較好的聚類準(zhǔn)確率。

表2　平均聚類準(zhǔn)確率　(%)

4　結(jié)論

流形降維最小二乘回歸子空間分割方法主要是結(jié)合流形降維方法中的局部保持投影和最小二乘回歸子空間分割法，此措施不僅改進(jìn)了傳統(tǒng)方法不利于高維數(shù)、小樣本、多噪聲、干擾大的非線性數(shù)據(jù)降維的缺點，還能在數(shù)據(jù)的分割聚類上取得更加突出的準(zhǔn)確性，反映出該方法的有效性。但是該方法存在時間開銷大等不足，這是今后研究的方向。

[1] LU C Y, MIN H, ZHAO Z Q, et al. Robust and efficient subspace segmentation via least squares regression[C]. Proceedings of the 12th European Conference on Computer Vision, Firenze, Italy, 2012: 347-360.

[2] ELAMIFAR E, VIDAL R. Sparse subspace clustering [C]. Proceedings of 23rd IEEE Conference on Computer Vision and Pattern Recognition, Bonn, Germany, 2009: 2790-2797.

[3] LIU G, LIN Z, YU Y. Robust subspace segmentation by low-rank representation[C]. Proceedings of the 27th International Conference on Machine Learning, Haifa, Israel, 2010: 663-670.

[4] 簡彩仁,呂書龍. 權(quán)自適應(yīng)最小二乘回歸子空間分割法[J]. 微型機(jī)與應(yīng)用, 2017, 36(10):54-57.

[5] HE X,NIYOGI P.Locality Preserving Projections (LPP)[J].Advances in Neural Information Processing Systems,2002,16(1):186-197.

[6] SHI J, MALIK J. Normalized cuts and image segmentation [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.

[7] CAI D, HE X, WU X, et al. Non-negative matrix factorization on manifold[C]. Proceedings of the 8th IEEE International Conference on Data Mining, Pisa, Italy, 2008: 63-72.