核化圖正則子空間分割方法

鄭毅偉 許金波 王藝恬 簡(jiǎn)彩仁

摘 要：傳統(tǒng)的線(xiàn)性子空間分割方法很難刻畫(huà)數(shù)據(jù)的非線(xiàn)性結(jié)構(gòu)。借鑒核理論提出核化圖正則子空間分割方法，在非線(xiàn)性空間中對(duì)數(shù)據(jù)進(jìn)行重構(gòu)，有利于刻畫(huà)數(shù)據(jù)的非線(xiàn)性特點(diǎn)。利用Sylvester方程可求得全局最優(yōu)解。2個(gè)圖像數(shù)據(jù)集和2個(gè)基因表達(dá)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，核化圖正則子空間分割方法優(yōu)于其他線(xiàn)性子空間分割方法。

關(guān)鍵詞：子空間分割;核理論;圖正則;聚類(lèi);Sylvester方程;非線(xiàn)性結(jié)構(gòu)

中圖分類(lèi)號(hào)：TP311;TP371 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2019）05-00-03

0 引 言

聚類(lèi)在機(jī)器學(xué)習(xí)等領(lǐng)域有著廣泛的應(yīng)用[1]。譜聚類(lèi)是一種傳統(tǒng)的聚類(lèi)方法，譜聚類(lèi)利用數(shù)據(jù)點(diǎn)之間的相似性構(gòu)造出關(guān)聯(lián)矩陣，再用關(guān)聯(lián)矩陣構(gòu)造出無(wú)向圖，最后用譜方法進(jìn)行分割。譜聚類(lèi)方法的主要問(wèn)題是求解相似矩陣。隨著表示理論的興起[2-4]，許多基于表示理論的重構(gòu)方法為譜圖矩陣的建立提供了新的途徑。基于表示理論的子空間分割方法利用表示理論得到重構(gòu)系數(shù)，再利用重構(gòu)系數(shù)構(gòu)造譜圖矩陣，最后用譜聚類(lèi)的方法實(shí)現(xiàn)聚類(lèi)。

子空間分割的目的是將數(shù)據(jù)集分割成幾個(gè)不同的類(lèi)簇，每個(gè)類(lèi)簇都對(duì)應(yīng)一個(gè)子空間，從而對(duì)樣本數(shù)據(jù)集進(jìn)行分割聚類(lèi)。近年來(lái)，基于表示理論的數(shù)據(jù)重構(gòu)方法的發(fā)展帶動(dòng)了子空間分割方法的創(chuàng)新，許多基于表示理論的子空間分割方法被提出，使得該研究方向成為聚類(lèi)問(wèn)題研究的熱點(diǎn)之一。例如，稀疏表示子空間分割方法（SSC）[5]利用L1范數(shù)的稀疏性得到具有稀疏性能的重構(gòu)系數(shù);低秩表示子空間分割方法（LRR）[6]基于低秩表示的思想旨在尋找低秩矩陣刻畫(huà)重構(gòu)系數(shù);最小二乘回歸子空間分割方法（LSR）[7]利用傳統(tǒng)的嶺回歸模型通過(guò)正則L2范數(shù)得到具有聚集功能的重構(gòu)系數(shù)。不僅如此，許多基于這些方法的拓展模型被提出[8-9]。但是這些子空間分割方法都是在高維樣本空間中基于歐氏距離度量的識(shí)別方法，不適合刻畫(huà)非線(xiàn)性數(shù)據(jù)的本質(zhì)。針對(duì)這一不足，結(jié)合圖正則子空間分割方法，利用核理論[10-11]，提出核化圖正則子空間分割方法，在高維核空間中研究非線(xiàn)性數(shù)據(jù)的聚類(lèi)問(wèn)題。

1 相關(guān)工作

本節(jié)敘述了對(duì)核化圖正則子空間分割方法提出的理論依據(jù)。

1.1 圖正則化項(xiàng)

圖正則化項(xiàng)借鑒流形學(xué)習(xí)的思想，保持原有數(shù)據(jù)集的流形結(jié)構(gòu)，在模式識(shí)別的研究中應(yīng)用廣泛[8，12]。假設(shè)原樣本空間的兩個(gè)樣本xi和xj映射為新樣本空間的兩個(gè)樣本zi和zj，定義圖正則化項(xiàng)：

式中：D是對(duì)角矩陣且;圖拉普拉斯矩陣L=D-G，G是邊權(quán)矩陣。

式中Nk（xi）是xi的k近鄰所組成的集合。

1.2 子空間分割方法

基于表示理論的子空間分割方法的關(guān)鍵在于重構(gòu)矩陣Z的求解。低秩表示子空間分割方法[6]主要保持重構(gòu)矩陣的低秩性質(zhì)，其數(shù)學(xué)模型為：

最小二乘回歸子空間分割方法[7]主要保持重構(gòu)系數(shù)的聚集性，其數(shù)學(xué)模型為：

利用圖正則化項(xiàng)提出的圖正則化子空間分割方法[8]如下：

2 核化圖正則子空間分割方法

針對(duì)傳統(tǒng)子空間分割方法在線(xiàn)性空間中對(duì)原樣本數(shù)據(jù)集進(jìn)行重構(gòu)不能很好刻畫(huà)數(shù)據(jù)集的非線(xiàn)性特點(diǎn)的不足，提出核化圖正則子空間分割方法。定義非線(xiàn)性特征空間映射Φ：Rm→M，其中Rm表示原樣本空間，M表示低維流形空間。由該非線(xiàn)性映射Φ得到X的低維流形表示Φ（X），利于刻畫(huà)數(shù)據(jù)集的非線(xiàn)性特點(diǎn)。對(duì)低維流形表示Φ（X）進(jìn)行子空間分割研究給出核化圖正則子空間分割方法的目標(biāo)函數(shù)：

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

為驗(yàn)證核化圖正則化子空間分割方法（KGRSS）的有效性，將使用KGRSS和不同的子空間分割方法，即圖正則化子空間分割方法（GRSS）[8]，最小二乘回歸子空間分割方法（LSR）[7]，低秩表示子空間分割法（LRR）[6]，以及兩種傳統(tǒng)聚類(lèi)算法，即K均值聚類(lèi)法（K-means）和層次聚類(lèi)法（HC）進(jìn)行聚類(lèi)準(zhǔn)確率的比較，聚類(lèi)準(zhǔn)確率的計(jì)算公式參考文獻(xiàn)[12]。

3.1 實(shí)驗(yàn)數(shù)據(jù)

本研究實(shí)驗(yàn)選用4個(gè)應(yīng)用于模式識(shí)別的數(shù)據(jù)集作為研究，分別為圖像數(shù)據(jù)集ORL，pixraw10P和基因表達(dá)數(shù)據(jù)集TOX_171，nci9，它們的簡(jiǎn)要信息見(jiàn)表1所列。

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

為避免聚類(lèi)的隨機(jī)性，實(shí)驗(yàn)過(guò)程中將每種方法運(yùn)行50次，聚類(lèi)準(zhǔn)確率的均值見(jiàn)表2所列。

觀察聚類(lèi)準(zhǔn)確率，對(duì)比實(shí)驗(yàn)結(jié)果可知，相比GRSS方法，KGRSS方法可以取得更加理想的聚類(lèi)準(zhǔn)確率，這一結(jié)果表明，基于核理論的核化圖正則子空間分割方法在數(shù)據(jù)的聚類(lèi)研究中更加實(shí)用。對(duì)比經(jīng)典的線(xiàn)性子空間分割方法LSR和LRR，KGRSS方法也可以得到更優(yōu)的聚類(lèi)準(zhǔn)確率。因此，KGRSS可以更好地反映出數(shù)據(jù)的非線(xiàn)性特點(diǎn)，取得更好的聚類(lèi)準(zhǔn)確率。KGRSS方法得到的聚類(lèi)準(zhǔn)確率相較于傳統(tǒng)的聚類(lèi)方法K-means和HC得到的聚類(lèi)準(zhǔn)確率有明顯提升，原因是傳統(tǒng)聚類(lèi)方法以歐式距離為度量，不適合具有非線(xiàn)性特點(diǎn)的數(shù)據(jù)識(shí)別研究。由上述實(shí)驗(yàn)結(jié)果可知，KGRSS方法相較于其他各類(lèi)方法大部分都能更好地適應(yīng)數(shù)據(jù)的聚類(lèi)，因此可以表明KGRSS是一種適合數(shù)據(jù)聚類(lèi)的方法。

3.3 參數(shù)分析

圖1顯示了正則參數(shù)λ和近鄰參數(shù)K的變化對(duì)聚類(lèi)準(zhǔn)確率的影響。當(dāng)近鄰參數(shù)K不變時(shí)，較大的正則參數(shù)λ能夠得到較高的聚類(lèi)準(zhǔn)確率;當(dāng)正則參數(shù)λ不變時(shí)，近鄰參數(shù)K在不同的數(shù)據(jù)中出現(xiàn)了不同的變化情況，2～7范圍中的近鄰參數(shù)K可以取得較高的聚類(lèi)準(zhǔn)確率。通過(guò)對(duì)圖1實(shí)驗(yàn)結(jié)果的觀察，范圍2～7的近鄰參數(shù)K以及較大的正則參數(shù)λ是一組較為理想的參數(shù)選擇，表明了KGRSS方法較強(qiáng)的實(shí)用性與相對(duì)較好的應(yīng)用價(jià)值。

4 結(jié) 語(yǔ)

利用核方法改進(jìn)圖正則子空間分割方法，提出了核化圖正則子空間分割方法（KGRSS），并成功實(shí)現(xiàn)了數(shù)據(jù)的聚類(lèi)。KGRSS方法用高斯核函數(shù)對(duì)數(shù)據(jù)樣本進(jìn)行處理，引入光滑函數(shù)保持樣本的幾何結(jié)構(gòu)，并且對(duì)Sylvester方程進(jìn)行求解得到全局最優(yōu)解。實(shí)驗(yàn)結(jié)果表明，KGRSS方法可以很好地適應(yīng)數(shù)據(jù)的非線(xiàn)性特點(diǎn)，并且聚類(lèi)效果比其他子空間分割方法和傳統(tǒng)聚類(lèi)方法更好。因此，運(yùn)用KGRSS方法能夠更好地實(shí)現(xiàn)數(shù)據(jù)聚類(lèi)。