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

簡彩仁，呂書龍

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

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

簡彩仁1，呂書龍2

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

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

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

0 引言

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

2.1 目標函數(shù)

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

(1)

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

2.2 目標優(yōu)化

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

(1)固定Z，優(yōu)化w

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

(2)

其中，Y=X-XZ。式(2)可以轉(zhuǎn)化為：

(3)

(4)

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

于是，得到如下不等式：

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

(5)

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

從而得到解析解：

(6)

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

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

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

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

(7)

那么

因此有：

以上兩式相減有：

(8)

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

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

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

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

Output：k個類簇

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

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

②固定w，利用式(6)優(yōu)化Z；

直到收斂；

(3)應(yīng)用標準分割方法將數(shù)據(jù)分成k個子空間。

3 實驗

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

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

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

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

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

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

本文的實驗環(huán)境為Windows 7系統(tǒng)，內(nèi)存2 GB，所有方法都用MATLAB 2011b編程實現(xiàn)。實驗結(jié)果用聚類準確率進行比較。實驗中子空間分割方法ALSR、LSR、GRSS和LRR的正則參數(shù)設(shè)置為0.000 1，0.001，0.01，0.1，1，2，3，4，5，10。實驗過程中遍歷這些參數(shù)，實驗結(jié)果選取平均聚類準確率最高的參數(shù)。GRSS的近鄰數(shù)量固定為5。

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

圖1 不同參數(shù)下的聚類結(jié)果

[5] Chen Xiaoyun,Jian Cairen.Gene expression data clustering based on graph regularized subspace segmentation[J].Neurocomputing,2014,143(16):44-50.

[6] 林莉媛,陳曉云,簡彩仁.融入距離信息的最小二乘回歸子空間分割[J].微型機與應(yīng)用,2016,35(6):63-65.

[7] VIDAL R.A tutorial on subspace clustering[J].IEEE Signal Processing Magazine,2010,28(2):52-68.

[8] Shi Jianbo,MALIK J.Normalized cuts and image segmenta-tion[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.

[9] Cai Deng,He Xiaofei,Wu Xiaoyun,et al.Non-negative matrix factorization on manifold[C].Proceedings of the 8th IEEE International Conference on Data Mining,Pisa,Italy,2008:63-72.

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

表2 聚類準確率對比

由實驗結(jié)果得出以下結(jié)論：

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

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

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

3.3 參數(shù)選擇

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

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

4 結(jié)論

本文用權(quán)自適應(yīng)的思想對最小二乘回歸子空間分割方法進行改進，提出權(quán)自適應(yīng)最小二乘回歸子空間分割方法。在6個數(shù)據(jù)集上的實驗結(jié)果表明權(quán)自適應(yīng)最小二乘回歸子空間分割方法通過考慮不同特征權(quán)重對數(shù)據(jù)集的影響，可以得到較為理想的聚類準確率。如何降低正則參數(shù)λ對聚類準確率的影響將是對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] 簡彩仁,陳曉云.基于投影最小二乘回歸子空間分割的基因表達數(shù)據(jù)聚類[J].模式識別與人工智能,2015,28(8):728-734.

Adaptive weight least square regression subspace segmentation

Jian Cairen1,Lv Shulong2

(1.Tan Kah Kee Colleage,Xiamen University,Zhangzhou 363105,China;2.College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China)

The subspace segmentation method based on the representation theory is widely used.The classical subspace segmentation methods are based on the different regularization terms to obtain the affine matrix.However,they neglect the influence of feature attributes on the subspace segmentation method.To solve these problems,the method based on adaptive weight least square regression subspace segmentation is improved.The experimental results on six data sets show that the proposed method is effective.

clustering; least square regression; adaptive weight; subspace segmentation

福建省中青年教師教育科研社科A類項目(JAS151395); 福州大學(xué)第九批高等教育教學(xué)改革工程項目(52001024)

TP311,TP371

A

10.19358/j.issn.1674- 7720.2017.10.016

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

2016-11-18)

簡彩仁(1988-),男,碩士,主要研究方向：數(shù)據(jù)挖掘、模式識別等。

呂書龍(1977-),男,碩士，副教授,主要研究方向：數(shù)據(jù)挖掘,統(tǒng)計計算,應(yīng)用統(tǒng)計分析等。