改進(jìn)的最小二乘孿生支持向量機(jī)聚類

劉玉菲，陳素根

（安慶師范大學(xué) 數(shù)理學(xué)院，安徽 安慶 246133）

聚類是一種重要的機(jī)器學(xué)習(xí)方法，如基于劃分的聚類K-means 算法、基于密度的聚類DBSCAN 算法、基于層次的聚類AGNES算法等[1]。近年來，基于平面的聚類引起學(xué)者們的關(guān)注，P.S Bradley等提出的k平面聚類（KPC）[2]算法，其主要思想是通過平面更新代替聚類中心更新，但是KPC忽視了每一類之間的影響。為了克服類與類之間對聚類效果的影響，Wang等提出了孿生支持向量機(jī)聚類（TWSVC），其主要思想是在尋找簇中心平面時要求本簇樣本盡可能近，而非本簇樣本與該平面有一定距離[3]。隨后，許多學(xué)者在TWSVC的基礎(chǔ)上提出了改進(jìn)的算法，如Wang等提出的基于Ramp損失的孿生支持向量機(jī)聚類算法（Ramp TWSVC）[4]，Sanaz Moezzi 等提出的改進(jìn)的孿生支持向量機(jī)聚類算法（TWSVC+）[5]等。TWSVC算法作為一種新型的聚類算法，表現(xiàn)出了較好的聚類性能，但它依然有一些不足，如TWSVC需要求解一系列二次規(guī)劃問題，計算相對復(fù)雜。為了提高算法的求解效率，Reshma Khemchandani 等人2016 年提出了最小二乘孿生支持向量機(jī)聚類（LSTWSVC），該算法在目標(biāo)函數(shù)中引入了一個正則項以實現(xiàn)結(jié)構(gòu)風(fēng)險最小化，并用等式約束代替TWSVC中不等式約束，優(yōu)化問題只需要求解一系列的線性方程組，而不是像TWSVC那樣求解一系列的二次規(guī)劃問題，減少了計算復(fù)雜性[6]。然而，LSTWSVC對每一類樣本都給予相同的懲罰，使得該算法性能受離群點的影響較大。基于上述分析，為了減少離群點對LSTWSVC性能的影響，我們構(gòu)造了一種新的權(quán)重函數(shù)，并在此基礎(chǔ)上提出了一種改進(jìn)的最小二乘孿生支持向量機(jī)聚類算法，簡記為ILSTWSVC。

1 相關(guān)工作

給定m個n維的數(shù)據(jù)樣本{x1,x2,x3,…,xm}，記為X=(x1,x2,x3,…,xm)T，為方便起見，將第i類數(shù)據(jù)樣本全體記為Xi，其余類數(shù)據(jù)樣本記為，其中i=1,2,3,…,k。

1.1 KPC

對于聚類問題，KPC希望將數(shù)據(jù)集X聚成k類，使數(shù)據(jù)樣本點在k類中心平面的附近中心平面為

其中，wi∈Rn和bi∈R，KPC嘗試解決以下問題：

其中，Xi包含X中屬于第i個類的行，e表示分量全為1的適當(dāng)維數(shù)向量。

求解優(yōu)化問題（2），可得到wi,bi，再按照以下規(guī)則進(jìn)行聚類：

對于非線性情形，我們引入核函數(shù)K(x,X)，利用核技巧就可以直接將線性KPC模型推廣到非線性KPC模型，具體算法見參考文獻(xiàn)[2]。

1.2 TWSVC

對于孿生支持向量機(jī)聚類問題，TWSVC尋找k類中心平面為

對于每一類，使得這一類的數(shù)據(jù)點盡可能離這一類中心平面近，其余樣本點盡可能遠(yuǎn)離這一類，建立優(yōu)化問題如下：

其中，c表示懲罰參數(shù)，ξi是松弛向量，e表示分量全為1的適當(dāng)維數(shù)向量。

其中，T(·)表示一階泰勒展開，j表示第j個子問題。

引入拉格朗日函數(shù)，利用Karush-Kuhn-Tucker(K.K.T)條件，得到對偶問題：

對于非線性情形，引入核函數(shù)K(x,X)，利用核技巧將線性TWSVC模型推廣到非線性TWSVC模型，具體算法見參考文獻(xiàn)[3]。

1.3 LSTWSVC

LSTWSVC用等式約束代替TWSVC中的不等式約束，并在目標(biāo)函數(shù)中加入正則化項，以實現(xiàn)結(jié)構(gòu)風(fēng)險最小化原則。對于第i類(i=1,2,3,…,k)聚類中心平面，建立優(yōu)化問題：

其中，c,v是參數(shù)，qi是松弛向量，e表示分量全為1的適當(dāng)維數(shù)向量。

與TWSVC 類似，上式可以通過凹凸過程求解，把它分解為一系列(j=0,1,2,…)的初始二次規(guī)劃子問題，（10）式即可轉(zhuǎn)化為以下的優(yōu)化模型：

其中T(·)表示一階泰勒展開，j表示第j個子問題。

將式（11）中的約束條件代入優(yōu)化問題的目標(biāo)函數(shù)中，得到無約束優(yōu)化問題：

求解優(yōu)化問題式（12）轉(zhuǎn)化為求解線性方程組問題。對目標(biāo)函數(shù)關(guān)于求導(dǎo)并整理化簡得到以下線性方程組：

于是，求解式（13）可得

對于非線性部分，引入核函數(shù)K(x,X)，利用核技巧將線性LSTWSVC模型推廣到非線性LSTWSVC模型，具體算法見文獻(xiàn)[6]。

2 改進(jìn)的最小二乘孿生支持向量機(jī)聚類

為克服離群點對LSTWSVC聚類性能的影響，本文提出了一種改進(jìn)的孿生支持向量機(jī)聚類算法，簡稱為ILSTWSVC，下面詳細(xì)介紹ILSTWSVC算法。

2.1 線性ILSTWSVC

考慮離群點對聚類效果的影響，在LSTWSVC基礎(chǔ)上，引入加權(quán)矩陣D對其余類樣本給予不同權(quán)重的懲罰，對于第i類(i=1,2,3,…,k)聚類中心平面，構(gòu)建優(yōu)化問題：

其中，c,v是參數(shù)，ξi是松弛向量，e表示分量全為1的適當(dāng)維數(shù)向量，D是以di為元素的對角矩陣。

根據(jù)樣本分布對聚類效果的影響，對不同的樣本賦予不同的權(quán)重di：

對于優(yōu)化問題（16）的目標(biāo)函數(shù)，第1項是樣本點到聚類中心平面的距離平方和，第2項是正則項，第3項是損失項。最小化第1項使得第i類樣本更加聚集在第i類聚類中心平面周圍，最小化第2項以實現(xiàn)結(jié)構(gòu)風(fēng)險避免過擬合，最小化第3項使得其他類樣本盡可能與第i類聚類中心平面保持一定距離。

為了求解優(yōu)化問題（16），先將其約束條件一階泰勒展開，再用CCCP求解，對于第i類(i=1,2,3,…,k)聚類中心平面，通過給定一系列(j=0,1,2,…)的初始，優(yōu)化問題（14）可轉(zhuǎn)化為

當(dāng)所有的wi,bi(i=1,2,3,…,k)求解出來之后，再按照以下規(guī)則進(jìn)行聚類：

綜上所述，給出線性ILSTWSVC算法如下：

算法1.線性ILSTWSVC

2.2 非線性ILSTWSVC

現(xiàn)將上述的線性模型拓展為非線性模型。選擇合適的核函數(shù)K將數(shù)據(jù)映射到高維特征空間中，類似于線性情形，建立非線性ILSTWSVC模型的優(yōu)化問題：

類似線性情況，可轉(zhuǎn)化為

其中，c,v是參數(shù),是松弛向量，e表示分量全為1的適當(dāng)維數(shù)向量，D是對角矩陣。

求解（27）式能得

求解式（28），可得

對于非線性算法，可類似于線性算法步驟，不同之處在于先選擇合適的核函數(shù)K將數(shù)據(jù)映射到高維空間，此處不再贅述。

2.3 算法描述

一般情況下，基于平面的聚類算法中的初始標(biāo)簽是隨機(jī)生成的，這樣選擇的實驗結(jié)果往往不穩(wěn)定，聚類效果對初始標(biāo)簽有較強(qiáng)的依賴性。因此，采取文獻(xiàn)[7]中的初始化方法得到每一類的樣本點Xi(i=1,2,3…,k)，然后求解特征值問題：

其中，I是一個單位矩陣，此處是最小特征值λ對應(yīng)的特征向量，并且

3 實驗結(jié)果及分析

為驗證ILSTWSVC 的性能，選取2 個人工數(shù)據(jù)集和5 個UCI 數(shù)據(jù)集進(jìn)行實驗。具體實驗環(huán)境是MATLAB R2014a，硬件配置為Window10 操作系統(tǒng)，12 GB 內(nèi)存，3.5 GHz 主頻CPU 的計算機(jī)。選取KPC、TWSVC 和LSTWSVC 作為對比實驗，與ILSTWSVC 實驗進(jìn)行比較，非線性情形下選擇核函數(shù)，其中δ為核參數(shù)。實驗均采用網(wǎng)格尋優(yōu)為各算法選擇最優(yōu)參數(shù)，在TWSVC、LSTWSVC和ILSTWSVC中，c和v的網(wǎng)格搜索范圍均設(shè)置為{ 2i|i=-5,-4,-3,…,5 }，在所有非線性實驗中，核函數(shù)參數(shù)δ搜索范圍設(shè)置為{ 2i|i=-5,-3,-1,…,5 }。初始化的近鄰數(shù)p從{ 1,3,5 }中選擇。

使用準(zhǔn)確率（Accuracy）來衡量聚類性能，給定聚類標(biāo)號yi∈N,i=1,2,3,…,m，計算相應(yīng)的相似矩陣M∈Rm×m，其中

設(shè)數(shù)據(jù)集的真實聚類標(biāo)簽計算的相似度矩陣為Mt，預(yù)測標(biāo)簽計算的相似矩陣為Mp。定義聚類方法的準(zhǔn)確率為蘭德統(tǒng)計量（Rand statistic）。

其中，n00是Mp和Mt中0的個數(shù)，n11是Mp和Mt中1的個數(shù)。

對于人工數(shù)據(jù)集，我們選擇了Aggregation和Jain 這2 個數(shù)據(jù)集。算法結(jié)果中最好的指標(biāo)用粗體表示。表1和表2分別給出了線性情形和非線性情形下ILSTWSVC、KPC、TWSVC、LSTWSVC在2個人工數(shù)據(jù)集上的聚類結(jié)果。

表1 線性ILSTWSVC與幾種算法在人工數(shù)據(jù)集上的準(zhǔn)確率比較

表2 非線性ILSTWSVC與幾種算法在人工數(shù)據(jù)集上的準(zhǔn)確率比較

從表1和表2可以看出，我們的方法在人工數(shù)據(jù)集Aggregation和Jain上均取得了較好的結(jié)果，在線性情形下，與其他算法相比，準(zhǔn)確率更好。圖1給出了線性情形下各算法在Jain數(shù)據(jù)集上的聚類效果圖，可以看出，我們所提出的ILSTWSVC算法具有較好的聚類效果。

圖1 線性情形下各算法在Jain數(shù)據(jù)集的聚類效果圖。（a）原始數(shù)據(jù)圖；（b）TWSVC；（c）LSTWSVC；（d）ILSTWSVC

為了進(jìn)一步驗證所提算法的有效性，在UCI數(shù)據(jù)集上進(jìn)行實驗，選擇了Iris，Hamberman，Ecoil，Zoo和Glass這5個數(shù)據(jù)集進(jìn)行驗證。表3和表4分別給出了線性情形下和非線性情形下ILSTWSVC、KPC、TWSVC、LSTWSVC 在5 個UCI 數(shù)據(jù)集上的聚類準(zhǔn)確率。由表3 可以看到，在UCI 數(shù)據(jù)集Iris，Hamberman，Zoo和Glass上，本文的線性ILSTWSVC具有較高的準(zhǔn)確率。由表4可以看出，本文中所提出的非線性ILSTWSVC在大多數(shù)數(shù)據(jù)集上也取得了較好的結(jié)果。

表3 線性ILSTWSVC與KPC、TWSVC、LSTWSVC在UCI數(shù)據(jù)集上的聚類準(zhǔn)確率比較

表4 非線性ILSTWSVC與KPC、TWSVC、LSTWSVC在UCI數(shù)據(jù)集上的聚類準(zhǔn)確率比較

4 結(jié)論

綜上所述，針對孿生支持向量機(jī)聚類算法沒有考慮數(shù)據(jù)分布對聚類性能影響的問題，本文構(gòu)造了一種新的權(quán)重函數(shù)以降低離群點對聚類性能的影響，從而提出了一種改進(jìn)的最小二乘孿生支持向量機(jī)聚類算法（ILSTWSVC）。本算法給予樣本點不同的懲罰，構(gòu)造了一種新的權(quán)重函數(shù)，在人工數(shù)據(jù)集和UCI數(shù)據(jù)集上驗證了ILSTWSVC 的有效性，與其他算法相比，我們的線性部分在人工數(shù)據(jù)集Aggregation，Jain和UCI數(shù)據(jù)集Iris，Hamberman，Zoo和Glass上都有較高的準(zhǔn)確率，非線性部分在人工數(shù)據(jù)集Jain和UCI 數(shù)據(jù)集Iris，Hamberman，Ecoil，Zoo，Glass 上也都有較高的準(zhǔn)確率。本文算法的不足之處是存在多個參數(shù)選擇，如何選擇最優(yōu)參數(shù)以提高聚類算法性能值得進(jìn)一步研究。