簡彩仁1，呂書龍2

　　(1.廈門大學 嘉庚學院,福建 漳州 363150; 2.福州大學 數學與計算機科學學院,福建 福州 350108)

　　摘要：基于表示理論的子空間分割方法有著廣泛的應用。經典的子空間分割方法通過不同的正則項求解仿射矩陣，而忽略了特征屬性對子空間分割的影響。針對這些問題，通過特征權重自適應的思想對最小二乘回歸子空間分割方法進行改進，提出權自適應最小二乘回歸子空間分割方法。在6個數據集上的實驗結果表明該方法是有效的。

　　關鍵詞：聚類；最小二乘回歸；權自適應 ；子空間分割

　　中圖分類號：TP311, TP371文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.10.016

　　引用格式：簡彩仁，呂書龍.權自適應最小二乘回歸子空間分割法［J］.微型機與應用，2017,36（10）：54-57,60.

0引言

　　*基金項目：福建省中青年教師教育科研社科A類項目（JAS151395）; 福州大學第九批高等教育教學改革工程項目（52001024）

　　子空間分割方法是近年來聚類方法研究的熱點問題［17］，其目標是將數據集分割（或聚集）成幾個簇，并使每一個簇對應于一個子空間。子空間分割方法已經成功應用在機器學習和計算機視覺等相關研究中。現實中的數據近乎可以視為是混合子空間，因此子空間分割方法在圖像聚類、圖像分割、運動物體識別和基因表達數據識別等領域有著廣泛的應用［16］。

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

　　子空間分割方法是一種重要的聚類方法，在過去的二十幾年里，已經提出許多經典的子空間分割方法。根據其表示方式的不同子空間分割方法可以粗略地分為四類［3］：代數方法、迭代方法、統計方法、譜聚類方法。

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

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

1相關研究

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

　　針對理想的無噪聲數據集，最小二乘回歸子空間分割方法為:

　　minZZFs.t.X=XZ

　　然而現實數據總是存在噪聲，將該模型擴展為:

　　minZX－XZ2F+λZ2F

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

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

2權自適應最小二乘回歸子空間分割

　　最小二乘回歸子空間分割方法用X=XZ來重構樣本，然而現實數據的特征屬性總是存在噪聲，但是最小二乘回歸子空間分割方法沒有考慮特征屬性噪聲對子空間分割的影響。針對這一不足，提出權自適應最小二乘回歸子空間分割方法，該方法可以自適應地選擇特征的權重，而不改變最小二乘回歸子空間分割方法的聚集性能。

　　2.1目標函數

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

　　因此，原始數據集X可以變為新的數據集diag(w)X，對其應用最小二乘回歸子空間分割方法得到權自適應最小二乘回歸子空間分割模型：

　　其中，λ>0是給定的正則參數。式（1）的第一項是加權重構項，其中參數wi表示第i個特征的重要程度，從而可以優化特征屬性，使該方法更利于子空間分割；第二項是正則F范數，用以實現子空間分割的聚集性。

　　2.2目標優化

　　目標函數有兩個參數w和Z，采用交替優化的方法實現問題（1）的求解。

　　（1）固定Z，優化w

　　固定參數Z，并且將無關的正則項去掉，式（1）變為：

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

　　（2）固定w，優化Z

　　固定w，并令X~=diag(w)X，則式（2）變為：

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

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

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

　　關于Z求導，并令其為0：

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

　　從而得到解析解：

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

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

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

　　2.3權自適應最小二乘回歸子空間分割方法的聚集性質

　　最小二乘回歸子空間分割方法有縮小相關數據系數和聚集性質［3］。定理2證明了權自適應最小二乘回歸子空間分割方法也有這樣的性質。

　　定理2給定一個向量y∈Rm，矩陣X∈Rm×n和參數λ>0，假設X已經按列標準化，z*是如下權自適應最小二乘回歸子空間分割問題的解：

　　其中r=xTixj是樣本相關系數。

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

　　L(z*)zk=0

　　因此有：

　　－2xTidiag(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已經按列標準化，xi－xj2=2(1－r)，其中r=xTixj是樣本相關系數。由于z*是式（7）的最優解，有：

　　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）蘊含著：

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

　　定理2證明的權自適應最小二乘回歸子空間分割方法的聚集能力表明模型的最優解是相關依賴的。假如xi和xj是高度相關的，即r=1，定理2表明xi和xj對應的表示系數zi和zj的不同程度為0，這樣xi和xj就會聚成相同的簇。

　　2.4權自適應最小二乘回歸子空間分割算法

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

　　算法：權自適應最小二乘回歸子空間分割算法（ALSR）

　　Input：數據矩陣X，正則參數λ，類數k

　　Output：k個類簇

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

　　①固定Z，利用式（4）優化w；

　　②固定w，利用式（6）優化Z；

　　直到收斂；

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

　　(3)應用標準分割方法將數據分成k個子空間。

3實驗

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

　　對一個給定的樣本，令ri和si分別為聚類算法得到的類標簽和樣本自帶的類標簽，那么準確率的計算公式為：

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

　　3.1數據集

　　本文選用6個來自UCI數據庫的常用于模式識別研究的公開數據集breast、german、liver、pima、vote和wpbc為研究對象，表1簡要給出了它們的相關信息，更多的數據集描述可以參考UCI數據庫的說明。

　　3.2實驗結果與分析

　　本文的實驗環境為Windows 7系統，內存2 GB，所有

　　方法都用MATLAB 2011b編程實現。實驗結果用聚類準確率進行比較。實驗中子空間分割方法ALSR、LSR、GRSS和LRR的正則參數設置為0.000 1，0.001，0.01，0.1，1，2，3，4，5，10。實驗過程中遍歷這些參數，實驗結果選取平均聚類準確率最高的參數。GRSS的近鄰數量固定為5。

　　為避免隨機性，每種方法運行10次取聚類準確率的平均值。表2以聚類準確率的均值±標準差(P值)的形式給出實驗結果。

　　由實驗結果得出以下結論：

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

　　（2）與經典的最小二乘回歸子空間分割方法（LSR）對比，ALSR的聚類準確率顯著高于LSR。這一結果說明考慮特征權重對于改進LSR是有效的。此外，與其他經典的子空間分割方法GRSS和LRR對比，ALSR方法也有較理想的聚類準確率。因此，ALSR是一種有效的子空間分割方法。

　　（3）與傳統的K均值聚類方法（Kmeans）相比，ALSR在所有測試數據集上都可以取得更好的聚類準確率。盡管Kmeans聚類方法在某些數據集上有突出的聚類準確率，比如在vote數據集上可以達到86.90%的準確率，但是在其他數據集上聚類結果一般。因此，ALSR的聚類準確率比Kmeans聚類方法更突出。

　　3.3參數選擇

　　與LSR對比，ALSR通過自適應加權并沒有增加新的參數，和LSR一樣，ALSR只有一個參數：正則系數λ。圖1的結果反映了正則參數λ對聚類準確率的影響。

　　從整體來看，聚類準確率對不同的正則參數λ較為敏感。但是從局部來看，ALSR的聚類準確率對不同的正則參數λ是相對穩定的，除了在vote數據集上，較小的正則參數λ具有較高的聚類準確率，這和文獻［3］的研究結論是一致的。

4結論

　　本文用權自適應的思想對最小二乘回歸子空間分割方法進行改進，提出權自適應最小二乘回歸子空間分割方法。在6個數據集上的實驗結果表明權自適應最小二乘回歸子空間分割方法通過考慮不同特征權重對數據集的影響，可以得到較為理想的聚類準確率。如何降低正則參數λ對聚類準確率的影響將是對ALSR進行進一步研究的一個方向。

　　參考文獻

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

　　［2］ 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.

　　［3］ 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.

　　［4］ 簡彩仁, 陳曉云. 基于投影最小二乘回歸子空間分割的基因表達數據聚類［J］. 模式識別與人工智能, 2015,28(8):728-734.