簡(jiǎn)彩仁1，呂書(shū)龍2

　　(1.廈門(mén)大學(xué) 嘉庚學(xué)院,福建 漳州 363150; 2.福州大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,福建 福州 350108)

　　摘要：基于表示理論的子空間分割方法有著廣泛的應(yīng)用。經(jīng)典的子空間分割方法通過(guò)不同的正則項(xiàng)求解仿射矩陣，而忽略了特征屬性對(duì)子空間分割的影響。針對(duì)這些問(wèn)題，通過(guò)特征權(quán)重自適應(yīng)的思想對(duì)最小二乘回歸子空間分割方法進(jìn)行改進(jìn)，提出權(quán)自適應(yīng)最小二乘回歸子空間分割方法。在6個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明該方法是有效的。

　　關(guān)鍵詞：聚類(lèi)；最小二乘回歸；權(quán)自適應(yīng) ；子空間分割

　　中圖分類(lèi)號(hào)：TP311, TP371文獻(xiàn)標(biāo)識(shí)碼：ADOI： 10.19358/j.issn.1674-7720.2017.10.016

　　引用格式：簡(jiǎn)彩仁，呂書(shū)龍.權(quán)自適應(yīng)最小二乘回歸子空間分割法［J］.微型機(jī)與應(yīng)用，2017,36（10）：54-57,60.

0引言

　　*基金項(xiàng)目：福建省中青年教師教育科研社科A類(lèi)項(xiàng)目（JAS151395）; 福州大學(xué)第九批高等教育教學(xué)改革工程項(xiàng)目（52001024）

　　子空間分割方法是近年來(lái)聚類(lèi)方法研究的熱點(diǎn)問(wèn)題［17］，其目標(biāo)是將數(shù)據(jù)集分割（或聚集）成幾個(gè)簇，并使每一個(gè)簇對(duì)應(yīng)于一個(gè)子空間。子空間分割方法已經(jīng)成功應(yīng)用在機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺(jué)等相關(guān)研究中?，F(xiàn)實(shí)中的數(shù)據(jù)近乎可以視為是混合子空間，因此子空間分割方法在圖像聚類(lèi)、圖像分割、運(yùn)動(dòng)物體識(shí)別和基因表達(dá)數(shù)據(jù)識(shí)別等領(lǐng)域有著廣泛的應(yīng)用［16］。

　　子空間分割方法［3］用數(shù)學(xué)語(yǔ)言可以描述為：給定k個(gè)子空間{Si}ki=1采樣的數(shù)據(jù)向量集合X=［X1,…,Xk］=［x1,…,xn］∈Rm×n，其中Xi是從子空間Si中采樣的ni個(gè)數(shù)據(jù)向量的集合，n=∑ki=1ni。子空間分割方法根據(jù)它們采樣的基子空間分割數(shù)據(jù)。

　　子空間分割方法是一種重要的聚類(lèi)方法，在過(guò)去的二十幾年里，已經(jīng)提出許多經(jīng)典的子空間分割方法。根據(jù)其表示方式的不同子空間分割方法可以粗略地分為四類(lèi)［3］：代數(shù)方法、迭代方法、統(tǒng)計(jì)方法、譜聚類(lèi)方法。

　　基于譜聚類(lèi)的子空間分割方法在于求解仿射矩陣Z=(Zij)n×n，其中Zij用來(lái)度量?jī)蓚€(gè)樣本xi和xj的相似度。理想的仿射矩陣是塊對(duì)角的，不同類(lèi)的兩個(gè)樣本的仿射矩陣值Zij=0，這樣就便于利用譜聚類(lèi)分割仿射矩陣，從而達(dá)到子空間分割的目的。以距離為背景的度量是一種最常見(jiàn)的相似度計(jì)算方法，例如Zij=exp(－xi－xj/σ),σ>0，然而這些方法僅僅考慮了樣本兩兩之間的相似度而不能很好地刻畫(huà)數(shù)據(jù)的本質(zhì)特征。得益于樣本表示理論，基于譜聚類(lèi)的子空間分割方法得到了很好的發(fā)展，例如低秩表示子空間分割方法［2］、最小二乘回歸子空間分割方法［3］和圖正則化子空間分割方法［5］提出了一些新的計(jì)算仿射矩陣的方法，這些方法通過(guò)表示理論來(lái)得到相似系數(shù)。

　　低秩表示子空間分割方法旨在通過(guò)秩最小化來(lái)構(gòu)建相似矩陣，最小二乘回歸子空間分割方法通過(guò)F范數(shù)正則化達(dá)到內(nèi)聚度，圖正則化子空間分割方法通過(guò)拉普拉斯圖正則化保持相似度。但是現(xiàn)實(shí)數(shù)據(jù)存在各類(lèi)噪聲，因此樣本重構(gòu)時(shí)，很容易受到噪聲的影響，然而這些方法都忽略了樣本重構(gòu)時(shí)特征屬性噪聲對(duì)子空間分割的影響。為了彌補(bǔ)這一不足，利用特征屬性加權(quán)的方法改進(jìn)最小二乘回歸子空間分割方法，并通過(guò)對(duì)特征權(quán)重進(jìn)行非負(fù)限制達(dá)到自適應(yīng)選擇特征權(quán)重的目的。該方法可以實(shí)現(xiàn)自適應(yīng)選擇特征權(quán)重，并保持最小二乘回歸子空間分割方法的聚集性。

1相關(guān)研究

　　基于表示理論的子空間分割方法是近年來(lái)的研究熱點(diǎn)，最小二乘回歸子空間分割方法將經(jīng)典的嶺回歸模型應(yīng)用到子空間分割方法，文獻(xiàn)［3］證明了該方法有很好的內(nèi)聚性能。最小二乘回歸子空間分割方法將每個(gè)樣本點(diǎn)xi表示為其他樣本點(diǎn)的線性組合x(chóng)i=∑j≠iZijxj，并通過(guò)正則Z的F范數(shù)達(dá)到樣本聚集的效果，最后用(Zij+Zji)/2表示xi和xj之間的相似度。

　　針對(duì)理想的無(wú)噪聲數(shù)據(jù)集，最小二乘回歸子空間分割方法為:

　　minZZFs.t.X=XZ

　　然而現(xiàn)實(shí)數(shù)據(jù)總是存在噪聲，將該模型擴(kuò)展為:

　　minZX－XZ2F+λZ2F

　　這是經(jīng)典的嶺回歸模型，其解析解為Z*=(XTX+λI)－1XTX，其中，λ>0是正則參數(shù)，I是單位矩陣。

　　最小二乘回歸子空間分割方法有很好的聚集性能，并且該方法有解析解，可以快速得到表示系數(shù)，然而它忽略了特征屬性噪聲對(duì)子空間分割的影響。

2權(quán)自適應(yīng)最小二乘回歸子空間分割

　　最小二乘回歸子空間分割方法用X=XZ來(lái)重構(gòu)樣本，然而現(xiàn)實(shí)數(shù)據(jù)的特征屬性總是存在噪聲，但是最小二乘回歸子空間分割方法沒(méi)有考慮特征屬性噪聲對(duì)子空間分割的影響。針對(duì)這一不足，提出權(quán)自適應(yīng)最小二乘回歸子空間分割方法，該方法可以自適應(yīng)地選擇特征的權(quán)重，而不改變最小二乘回歸子空間分割方法的聚集性能。

　　2.1目標(biāo)函數(shù)

　　給定一個(gè)樣本x=［x1,x2,…,xm］Τ∈Rm，由于現(xiàn)實(shí)數(shù)據(jù)在采樣過(guò)程中存在噪聲的影響，每個(gè)特征對(duì)模式識(shí)別方法的影響程度是不一樣的，因此每個(gè)特征屬性有不一樣的權(quán)重，通過(guò)非負(fù)特征權(quán)重w=［w1,w2,…,wm］Τ∈Rm+的作用得到新的樣本x~=［w1x1,w2x2,…,wmxm］Τ=diag(w)x，其中，diag(w)是一個(gè)m×m的以w為主對(duì)角線元素的對(duì)角矩陣，為達(dá)到特征權(quán)自適應(yīng)的目的,限制∑mi=1wi=1,wi≥0,i=1,2,…,m。

　　因此，原始數(shù)據(jù)集X可以變?yōu)樾碌臄?shù)據(jù)集diag(w)X，對(duì)其應(yīng)用最小二乘回歸子空間分割方法得到權(quán)自適應(yīng)最小二乘回歸子空間分割模型：

　　其中，λ>0是給定的正則參數(shù)。式（1）的第一項(xiàng)是加權(quán)重構(gòu)項(xiàng)，其中參數(shù)wi表示第i個(gè)特征的重要程度，從而可以優(yōu)化特征屬性，使該方法更利于子空間分割；第二項(xiàng)是正則F范數(shù)，用以實(shí)現(xiàn)子空間分割的聚集性。

　　2.2目標(biāo)優(yōu)化

　　目標(biāo)函數(shù)有兩個(gè)參數(shù)w和Z，采用交替優(yōu)化的方法實(shí)現(xiàn)問(wèn)題（1）的求解。

　?。?）固定Z，優(yōu)化w

　　固定參數(shù)Z，并且將無(wú)關(guān)的正則項(xiàng)去掉，式（1）變?yōu)椋?/p>

　　下面的定理給出了求解方法。

　　（2）固定w，優(yōu)化Z

　　固定w，并令X~=diag(w)X，則式（2）變?yōu)椋?/p>

　　minZX~－X~Z2F+λZ2F（5）

　　令L(Z)=X~－X~Z2F+λZ2F，并將其展開(kāi)：

　　L(Z)=Tr(X~TX~)+Tr(ZTX~TX~Z)－Tr(X~TX~Z)－Tr(ZTX~TX~)+λTr(ZTZ)

　　關(guān)于Z求導(dǎo)，并令其為0：

　　2X~TX~Z－2X~TX~+2λZ=0

　　從而得到解析解：

　　Z*=X~TX~+λI－1X~TX~（6）

　　其中，X~=diag(w)X，λ>0是正則參數(shù)，I是單位矩陣。

　　上述兩個(gè)步驟都可以得到極小值，因此算法的收斂性可以得到保證，通過(guò)上述兩個(gè)步驟的交替迭代過(guò)程可以得到式（2）的解。

　　2.3權(quán)自適應(yīng)最小二乘回歸子空間分割方法的聚集性質(zhì)

　　最小二乘回歸子空間分割方法有縮小相關(guān)數(shù)據(jù)系數(shù)和聚集性質(zhì)［3］。定理2證明了權(quán)自適應(yīng)最小二乘回歸子空間分割方法也有這樣的性質(zhì)。

　　定理2給定一個(gè)向量y∈Rm，矩陣X∈Rm×n和參數(shù)λ>0，假設(shè)X已經(jīng)按列標(biāo)準(zhǔn)化，z*是如下權(quán)自適應(yīng)最小二乘回歸子空間分割問(wèn)題的解：

　　其中r=xTixj是樣本相關(guān)系數(shù)。

　　證明：令L(z)=diag(w)y－diag(w)Xz22+λz22，由于z*是式（7）的解，必然有：

　　L(z*)z(mì)k=0

　　因此有：

　?。?xTidiag(w)(y－Xz*)+2λz*i=0

　　－2xTjdiag(w)(y－Xz*)+2λz*j=0

　　以上兩式相減有：

　　z*i－z*j=1λ(xTi－xTj)diag(w)(y－Xz*)

　　X已經(jīng)按列標(biāo)準(zhǔn)化，xi－xj2=2(1－r)，其中r=xTixj是樣本相關(guān)系數(shù)。由于z*是式（7）的最優(yōu)解，有：

　　diag(w)y－diag(w)Xz*22+λz*22=L(z*)≤L(0)=diag(w)y22（8）

　　因此diag(w)y－diag(w)Xz*2≤diag(w)y2，那么式（8）蘊(yùn)含著：

　　z*i－z*j2y2≤1λ2(1－r)

　　定理2證明的權(quán)自適應(yīng)最小二乘回歸子空間分割方法的聚集能力表明模型的最優(yōu)解是相關(guān)依賴的。假如xi和xj是高度相關(guān)的，即r=1，定理2表明xi和xj對(duì)應(yīng)的表示系數(shù)zi和zj的不同程度為0，這樣xi和xj就會(huì)聚成相同的簇。

　　2.4權(quán)自適應(yīng)最小二乘回歸子空間分割算法

　　類(lèi)似于經(jīng)典的基于表示理論的子空間分割方法，權(quán)自適應(yīng)最小二乘回歸子空間分割法（Adaptive Weight Least Square Regression Subspace Segmentation，ALSR）也是一種基于譜聚類(lèi)的子空間分割方法，首先通過(guò)2.2節(jié)的方法解決式（2），得到該問(wèn)題的解Z*，接著應(yīng)用標(biāo)準(zhǔn)分割方法（Normalized Cuts）［8］對(duì)仿射矩陣(Z*+(Z*)T)/2進(jìn)行分割。ALSR的計(jì)算步驟如下:

　　算法：權(quán)自適應(yīng)最小二乘回歸子空間分割算法（ALSR）

　　Input：數(shù)據(jù)矩陣X，正則參數(shù)λ，類(lèi)數(shù)k

　　Output：k個(gè)類(lèi)簇

　　(1)利用2.2小節(jié)的方法解決式（2），求得Z*：

　　①固定Z，利用式（4）優(yōu)化w；

　?、诠潭╳，利用式（6）優(yōu)化Z；

　　直到收斂；

　　(2)計(jì)算矩陣 (Z*+(Z*)T)/2；

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

3實(shí)驗(yàn)

　　為驗(yàn)證權(quán)自適應(yīng)最小二乘回歸子空間分割方法（ALSR）的有效性，與經(jīng)典的子空間分割方法最小二乘回歸子空間分割方法（LSR）［3］、圖正則化子空間分割方法（GRSS）［5］、低秩表示子空間分割方法（LRR）［2］以及傳統(tǒng)的聚類(lèi)方法K均值（Kmeans）從聚類(lèi)的準(zhǔn)確率的角度進(jìn)行比較。聚類(lèi)準(zhǔn)確率的計(jì)算公式［9］如下：

　　對(duì)一個(gè)給定的樣本，令ri和si分別為聚類(lèi)算法得到的類(lèi)標(biāo)簽和樣本自帶的類(lèi)標(biāo)簽，那么準(zhǔn)確率的計(jì)算公式為：

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

　　3.1數(shù)據(jù)集

　　本文選用6個(gè)來(lái)自UCI數(shù)據(jù)庫(kù)的常用于模式識(shí)別研究的公開(kāi)數(shù)據(jù)集breast、german、liver、pima、vote和wpbc為研究對(duì)象，表1簡(jiǎn)要給出了它們的相關(guān)信息，更多的數(shù)據(jù)集描述可以參考UCI數(shù)據(jù)庫(kù)的說(shuō)明。

　　3.2實(shí)驗(yàn)結(jié)果與分析

　　本文的實(shí)驗(yàn)環(huán)境為Windows 7系統(tǒng)，內(nèi)存2 GB，所有

　　方法都用MATLAB 2011b編程實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果用聚類(lèi)準(zhǔn)確率進(jìn)行比較。實(shí)驗(yàn)中子空間分割方法ALSR、LSR、GRSS和LRR的正則參數(shù)設(shè)置為0.000 1，0.001，0.01，0.1，1，2，3，4，5，10。實(shí)驗(yàn)過(guò)程中遍歷這些參數(shù)，實(shí)驗(yàn)結(jié)果選取平均聚類(lèi)準(zhǔn)確率最高的參數(shù)。GRSS的近鄰數(shù)量固定為5。

　　為避免隨機(jī)性，每種方法運(yùn)行10次取聚類(lèi)準(zhǔn)確率的平均值。表2以聚類(lèi)準(zhǔn)確率的均值±標(biāo)準(zhǔn)差(P值)的形式給出實(shí)驗(yàn)結(jié)果。

　　由實(shí)驗(yàn)結(jié)果得出以下結(jié)論：

　　（1）權(quán)自適應(yīng)最小二乘回歸子空間分割方法（ALSR）的聚類(lèi)效果是理想的，除了在liver數(shù)據(jù)集上都取得最好的聚類(lèi)準(zhǔn)確率。其中，在liver數(shù)據(jù)集上聚類(lèi)準(zhǔn)確率不如圖正則化子空間分割方法（GRSS），但是P值大于0.05，顯示兩者的聚類(lèi)準(zhǔn)確率相差不大。

　?。?）與經(jīng)典的最小二乘回歸子空間分割方法（LSR）對(duì)比，ALSR的聚類(lèi)準(zhǔn)確率顯著高于LSR。這一結(jié)果說(shuō)明考慮特征權(quán)重對(duì)于改進(jìn)LSR是有效的。此外，與其他經(jīng)典的子空間分割方法GRSS和LRR對(duì)比，ALSR方法也有較理想的聚類(lèi)準(zhǔn)確率。因此，ALSR是一種有效的子空間分割方法。

　?。?）與傳統(tǒng)的K均值聚類(lèi)方法（Kmeans）相比，ALSR在所有測(cè)試數(shù)據(jù)集上都可以取得更好的聚類(lèi)準(zhǔn)確率。盡管Kmeans聚類(lèi)方法在某些數(shù)據(jù)集上有突出的聚類(lèi)準(zhǔn)確率，比如在vote數(shù)據(jù)集上可以達(dá)到86.90%的準(zhǔn)確率，但是在其他數(shù)據(jù)集上聚類(lèi)結(jié)果一般。因此，ALSR的聚類(lèi)準(zhǔn)確率比Kmeans聚類(lèi)方法更突出。

　　3.3參數(shù)選擇

　　與LSR對(duì)比，ALSR通過(guò)自適應(yīng)加權(quán)并沒(méi)有增加新的參數(shù)，和LSR一樣，ALSR只有一個(gè)參數(shù)：正則系數(shù)λ。圖1的結(jié)果反映了正則參數(shù)λ對(duì)聚類(lèi)準(zhǔn)確率的影響。

　　從整體來(lái)看，聚類(lèi)準(zhǔn)確率對(duì)不同的正則參數(shù)λ較為敏感。但是從局部來(lái)看，ALSR的聚類(lèi)準(zhǔn)確率對(duì)不同的正則參數(shù)λ是相對(duì)穩(wěn)定的，除了在vote數(shù)據(jù)集上，較小的正則參數(shù)λ具有較高的聚類(lèi)準(zhǔn)確率，這和文獻(xiàn)［3］的研究結(jié)論是一致的。

4結(jié)論

　　本文用權(quán)自適應(yīng)的思想對(duì)最小二乘回歸子空間分割方法進(jìn)行改進(jìn)，提出權(quán)自適應(yīng)最小二乘回歸子空間分割方法。在6個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明權(quán)自適應(yīng)最小二乘回歸子空間分割方法通過(guò)考慮不同特征權(quán)重對(duì)數(shù)據(jù)集的影響，可以得到較為理想的聚類(lèi)準(zhǔn)確率。如何降低正則參數(shù)λ對(duì)聚類(lèi)準(zhǔn)確率的影響將是對(duì)ALSR進(jìn)行進(jìn)一步研究的一個(gè)方向。

　　參考文獻(xiàn)

　?。?］ ELHAMIFAR E, VIDAL R. Sparse subspace clustering［C］.Proceedings of 23rd IEEE Conference on Computer Vision and Pattern Recognition. Bonn, Germany, 2009: 2790-2797.

　?。?］ Liu Guangcan, Lin Zhouchen, Yu Yong. Robust subspace segmentation by low

　　rank representation［C］.Proceedings of the 27th International Conference on Machine Learning, Haifa, Israel, 2010: 663-670.

　?。?］ Lu Canyi, Min Hai, Zhao Zhongqiu, 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.

　?。?］ 簡(jiǎn)彩仁, 陳曉云. 基于投影最小二乘回歸子空間分割的基因表達(dá)數(shù)據(jù)聚類(lèi)［J］. 模式識(shí)別與人工智能, 2015,28(8):728-734.