韓素青，李淑慧

(太原師范學(xué)院 計算機科學(xué)與技術(shù)系 ,晉中 030619)

0 引言

近年來，隨著機器學(xué)習(xí)的興起，類別不平衡問題逐漸成為研究的熱點.不平衡數(shù)據(jù)廣泛存在于網(wǎng)絡(luò)入侵檢測、軟件缺陷檢測、醫(yī)療診斷等領(lǐng)域[1-3].在不平衡數(shù)據(jù)中，樣本較少的類別通常是關(guān)注的焦點.例如，在網(wǎng)絡(luò)入侵檢測中，如果將被惡意攻擊的網(wǎng)絡(luò)誤判為正常網(wǎng)絡(luò)，可能產(chǎn)生信息泄露，由此引發(fā)巨大的經(jīng)濟損失.因此對少數(shù)類的正確識別至關(guān)重要.

聚類分析是一種重要的數(shù)據(jù)分析技術(shù)，是一種以無監(jiān)督學(xué)習(xí)方法探索數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，進而形成簇的過程.此方法不需要指定樣本的類標(biāo)記，但標(biāo)記由聚類學(xué)習(xí)算法自動確定.在聚類分析中，譜聚類是一種利用圖劃分思想處理數(shù)據(jù)聚類問題的方法，可以很好地處理非凸結(jié)構(gòu)的數(shù)據(jù)，并獲得令人滿意的聚類結(jié)果[4-5]，常用于解決數(shù)據(jù)不平衡的問題.然而，傳統(tǒng)的譜聚類算法需要根據(jù)數(shù)據(jù)之間的相似度來構(gòu)造矩陣，并且還需要拉普拉斯矩陣的特征分解過程.因此，僅適用于小型數(shù)據(jù)集，而難以處理大規(guī)模數(shù)據(jù).為提升譜聚類算法的可擴展性，2004年，F(xiàn)owlkes 等人在文[6]中設(shè)計了 Nystrom 方法，并將其用于譜聚類，加快了特征分解的速度.2009年，Yan等人在文[7]中提出一種快速近似譜聚類的思想，即通過選取代表點進行譜聚類，然后再根據(jù)數(shù)據(jù)點與代表點之間的關(guān)系將聚類關(guān)系擴展到整個數(shù)據(jù)集上.其中，代表點根據(jù)隨機抽樣產(chǎn)生.2011年，Chen 等人在文[8]中提出一種基于地標(biāo)點的譜聚類算法(Landmark-based Spectral Clustering， LSC)，并在文[9]中給出了相關(guān)的理論分析，結(jié)果顯示，該方法不僅適用于大規(guī)模數(shù)據(jù)集，而且性能比 Nystrom 方法要好.然而，該方法使用隨機采樣法來獲取地標(biāo)點，抽樣結(jié)果會影響聚類結(jié)果的穩(wěn)定性.這容易導(dǎo)致樣本點在某一區(qū)域的數(shù)目很多，而其余區(qū)域幾乎沒有.

本文將LSC算法用于處理不平衡數(shù)據(jù)聚類問題，提出一種改進地標(biāo)點采樣的不平衡數(shù)據(jù)聚類算法.該算法根據(jù)數(shù)據(jù)的密度分布對數(shù)據(jù)進行采樣，旨在獲得相對平衡的數(shù)據(jù)集；將在采樣數(shù)據(jù)集上進行K-means聚類獲得的聚類中心作為地標(biāo)點，可以確保算法較大程度地保留數(shù)據(jù)的主要特征.

1 相關(guān)概念

1.1 譜聚類算法原理及主要步驟

譜聚類算法[10]以譜圖理論為基礎(chǔ)，通過將樣本對應(yīng)于圖中的點，樣本間的相似度對應(yīng)于兩點間邊的權(quán)重，將數(shù)據(jù)的聚類問題轉(zhuǎn)化為圖中邊的分割問題.

具體地，給定m維的數(shù)據(jù)集X={x1,x2,…,xn}，首先根據(jù)數(shù)據(jù)點構(gòu)造相似度圖，將求解樣本數(shù)據(jù)集的聚類結(jié)果的問題轉(zhuǎn)換為求解圖的最小割問題；然后依據(jù)圖劃分準(zhǔn)則和譜映射原理，將相似度矩陣變換為Laplacian矩陣.在此基礎(chǔ)上，對Laplacian矩陣進行特征分解，也就是將數(shù)據(jù)轉(zhuǎn)換到一個維數(shù)相對較低的特征子空間中；最后在這個子空間中，使用簡單的聚類方法對數(shù)據(jù)進行聚類.

通常，譜聚類算法概括為以下步驟:

Step1 構(gòu)建數(shù)據(jù)之間的相似度矩陣Z；

Step2 通過對相似度矩陣進行特征分解，構(gòu)建特征子空間；

Step3 利用K-means算法或其它有效的聚類算法在特征子空間中對數(shù)據(jù)進行聚類.

對于任意形狀的樣本空間，譜聚類算法都能獲得良好的聚類效果.但是，處理大規(guī)模數(shù)據(jù)所需的計算量非常大，因此，通過抽樣方法獲取有價值的數(shù)據(jù)點來替代原始數(shù)據(jù)集的方法可減低數(shù)據(jù)規(guī)模，值得進一步探究.

1.2 抽樣方法

在處理不平衡數(shù)據(jù)問題時，重采樣是一種常用的采樣方法，通過改變訓(xùn)練樣本的分布來消除或減小不平衡數(shù)據(jù)的潛在影響.重抽樣通常有兩種方法：過采樣和欠采樣.

過采樣通過增加少數(shù)類中的樣本數(shù)來提高模型識別的性能.Ling等人在文[11]中指出，僅通過隨機復(fù)制少數(shù)類樣本并不能使樣本的識別率提升.Chawla等人在文[12]中提出了SMOTE(Synthetic MinorityOversampling Technique)算法，該算法通過線性插值法在相鄰樣本之間構(gòu)造新少數(shù)類樣本.Han等人則從誤分類樣本的角度進行分析，認為誤分樣本一般位于簇類的邊界上.因此，只對邊界上的少數(shù)類樣本進行隨機復(fù)制[13]，但這類方法容易過擬合.

欠采樣通過從多數(shù)類中刪除一些樣本來提升模型識別的性能，但是，隨機去掉多數(shù)類中的某些樣本容易導(dǎo)致有用信息被刪除的情況發(fā)生[14].Jorma在文[15]中提出一種基于最近鄰規(guī)則的欠采樣方法，由于刪除了類別邊界的多數(shù)類樣本，因此降低了邊界附近數(shù)據(jù)樣本類別的識別效果.Yu等人在文[16]中給出了ACOsampling方法，該方法通過蟻群算法尋找多數(shù)類樣本中包含最多信息的樣本子集，然后將該子集與少數(shù)類樣本組合成用于訓(xùn)練的新數(shù)據(jù)集.這類方法的主要缺陷在于有可能丟失包含重要信息的樣本子集.Hido等人在文[17]中提出的EBBag算法結(jié)合欠抽樣和bagging算法設(shè)計，對于每次迭代，訓(xùn)練集包括所有少數(shù)類樣本和從多數(shù)類樣本中隨機抽取的子集，但是，由于抽取的樣本是在不考慮數(shù)據(jù)分布特征的情況下隨機選擇的，因此很容易丟失有用信息.

目前，大多抽樣方法的研究主要基于有標(biāo)簽樣本進行，但實際上有許多數(shù)據(jù)集是無法預(yù)先賦予標(biāo)簽的，因此，一些學(xué)者也對無類標(biāo)簽的數(shù)據(jù)的抽樣做了一些研究.

Yen和Lee在文[18]中提出一種基于聚類的欠采樣方法，該方法是基于預(yù)聚類的采樣，通過計算樣本之間的不平衡度來確定需要保留在聚類中的樣本數(shù)量，并且根據(jù)要保留的樣本數(shù)隨機刪除多數(shù)類.龐天杰在文[19]中設(shè)計的算法采用了先抽取部分樣本作為公共樣本，然后從剩余樣本中多次抽取固定規(guī)模的樣本，并與公共樣本一起形成新的訓(xùn)練樣本的策略，聚類結(jié)果由多個訓(xùn)練樣本集上的譜聚類結(jié)果集成.由該策略獲得的不同的訓(xùn)樣本集，既有一定的差異度，又有一定的相同性.

1.3 SVD方法(奇異值分解方法)

本文設(shè)計的改進地標(biāo)點采樣的不平衡數(shù)據(jù)聚類算法，利用奇異值分解(Singular Value Decomposition，SVD)對相似度矩陣進行特征值分解.

SVD是一種常用的矩陣分解(Matrix Decomposition)方法.該方法能夠有效獲得相似度矩陣的一個低秩近似，降低采樣過程的時間復(fù)雜度.相關(guān)概念介紹如下.

定義1.3.1 設(shè)Z∈Cp×n，若ZTZ=ZZT=E,則稱Z為酉矩陣.

Z=P∑Q

2 一種改進地標(biāo)點采樣的不平衡數(shù)據(jù)聚類算法(LSC-SRK算法)

對于地標(biāo)點的選取，可以采用隨機抽樣選取地標(biāo)點或以K-means選取聚類中心為地標(biāo)點的方法[22].但兩種抽樣方法處理不平衡數(shù)據(jù)時存在偏差，少數(shù)類樣本可能被忽略.因此本文提出先根據(jù)樣本分布進行抽樣然后再進行K-means聚類的SRK(Sample Ratio K-means)方法.

2.1 SRK抽樣法

定義2.1 記SampleRatio為簇C的抽樣比例，抽樣比例計算如下[23]：

其中，R表示簇C的實際半徑，EX表示簇C中的各個對象到簇中心的距離的平均值，DX表示簇C內(nèi)各個對象到簇中心距離的標(biāo)準(zhǔn)差，β為分離不同密度簇的參數(shù).

β的選擇方法如下：

1)在簇C內(nèi)隨機抽樣產(chǎn)生若干樣本點；

2)計算每對樣本點之間的歐式距離；

3)計算上述所有距離的平均值μ和方差σ；

4)β取[μ-σ,μ]之間的值.

由于抽樣比例函數(shù)根據(jù)簇的分布特征確定，因此不同分布特征的簇抽樣比例不一樣.一般來說，簇的密度越大，抽樣比例越小，這樣能夠獲得相對平衡的數(shù)據(jù)集.大量實驗表明，β在0.7-1 之間取值能將密度大的簇與密度小的簇較好地分離開.

2.2 LSC-SRK算法

LSC-SRK 算法首先經(jīng)過預(yù)聚類獲得數(shù)據(jù)的初始類標(biāo)簽，其次通過定義2.1的抽樣方法獲取相對平衡的數(shù)據(jù)集；數(shù)據(jù)的相似度矩陣由數(shù)據(jù)點與地標(biāo)點之間的相似度矩陣的乘積近似，低維特征空間利用SVD算法獲得，聚類在低維特征空間上進行.

LSC-SRK算法流程描述如下：

輸入：n個m維數(shù)據(jù)點形成的數(shù)據(jù)矩陣X∈Rn×m，簇個數(shù)k，地標(biāo)點個數(shù)p；

輸出：k個簇；

Step1 對不平衡數(shù)據(jù)進行K-means預(yù)聚類，得到p個簇C(p)={C1,C2,…,Cp}；

Step2 在每個簇中按定義2.1計算類抽樣比例SR，并按比例對Ci進行簡單隨機抽樣；

Step3 將每個簇Ci中按比例抽樣形成的數(shù)據(jù)集組合成新的數(shù)據(jù)子集；

Step4 在新的數(shù)據(jù)子集上進行二次K-means聚類，并將聚類中心作為地標(biāo)點，并將p個地標(biāo)點記為la1,…,lap；

Step5 在地標(biāo)點和數(shù)據(jù)點間構(gòu)造相似度矩陣Z∈Rp×n， 使得

其中，Kh(·)是帶寬為h的核函數(shù)；

Step7 視矩陣Q的每行為一個數(shù)據(jù)點并對其進行K-means聚類，得到聚類結(jié)果.

Step8 將聚類結(jié)果采用最近鄰法擴展到整個數(shù)據(jù)集上.

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

3.1 有效性評價指標(biāo)

本文選取accuracy和CUN兩種指標(biāo)評價LSC-SRK 算法的聚類性能.

假設(shè)一個數(shù)據(jù)集含有n個樣本，每個樣本具有m個屬性，分別為a1,a2,…,am,經(jīng)過LSC-SRK 算法得到的聚類結(jié)果為C(k)={C1,C2,…,Ck}.

(A)accuracy[22]是一種外部評價指標(biāo)，需要數(shù)據(jù)的真實劃分結(jié)果，它用來衡量聚類結(jié)果與真實標(biāo)簽之間的吻合程度.

accuracy的表達式如下：

accuracy=∑i=1,…，k(|Ci|/n)

其中，|Ci|是簇Ci中的樣本數(shù)，k是類數(shù)，n是數(shù)據(jù)集中樣本總數(shù).

accuracy的值越高，說明該算法的聚類結(jié)果越接近真實劃分.

(B)CUN[19]是一種內(nèi)部評價指標(biāo)，用來衡量簇內(nèi)數(shù)據(jù)點間的緊湊程度.CUN的表達式如下：

3.2 實驗數(shù)據(jù)及實驗環(huán)境

為了驗證有效性，本文從UCI數(shù)據(jù)集中選取了german,Haberman,balance,abalone,page-blocks 5個不同規(guī)模的不平衡數(shù)據(jù)集進行實驗，數(shù)據(jù)集分布如表1所示.

表1 不平衡數(shù)據(jù)集

本節(jié)基于accuracy和CUN兩種評價指標(biāo)，將本文提出的LSC-SRK算法分別與隨機抽樣法選取地標(biāo)點的譜聚類算法LSC-R和以K-means選取聚類中心為地標(biāo)點的譜聚類算法LSC-K進行了比較和分析.

實驗環(huán)境為：處理器Intel XeonE5-2680v22 1.8GHz，內(nèi)存128G，操作系統(tǒng)Windows 7，編程環(huán)境MATLAB 2014a.

3.3 實驗情況

大量不平衡數(shù)據(jù)實驗[23]表明取β=0.7時能較好地分離密度不同的簇，因此本文實驗取參數(shù)β=0.7，三種算法各執(zhí)行5次，并計算其平均accuracy值和CUN值.在不同數(shù)據(jù)集上的實驗結(jié)果如表2所示，另外，就數(shù)據(jù)集的不平衡度對準(zhǔn)確性的影響也進行了分析，二者之間的關(guān)系如圖1所示.

表2 不同抽樣方法在聚類算法中的實驗結(jié)果

圖1 準(zhǔn)確度與不平衡度的關(guān)系圖

從圖1可以看出，不平衡度相對較小時，三者算法的準(zhǔn)確度差別不大，隨著不平衡度的增大，本文提出的LSC-SRK算法與LSC-K、LSC-R相比，準(zhǔn)確度明顯上升.

從表1，表2可以看出，當(dāng)數(shù)據(jù)規(guī)模相對較小的時候，LSC-SRK算法的CUN值介于LSC-K與LSC-R之間，數(shù)據(jù)規(guī)模較大時，LSC-SRK的CUN值顯著增大，而LSC-K、LSC-R則表現(xiàn)一般.這表明LSC-SRK在大規(guī)模數(shù)據(jù)中能夠更有效地區(qū)分多數(shù)類與少數(shù)類，并保證簇內(nèi)的緊湊程度.由此可以得出，LSC-SRK 算法在實際中更具有意義.

4 結(jié)束語

針對不平衡聚類問題中隨機抽樣選取地標(biāo)點導(dǎo)致聚類結(jié)果不穩(wěn)定，以及直接將K-means聚類中心作為地標(biāo)點可能丟失有價值數(shù)據(jù)等問題，本文改進了地標(biāo)點采樣算法.通過根據(jù)數(shù)據(jù)的密度分布進行采樣，以及利用SVD算法快速降維，在算法性能提升的同時，有效節(jié)約了譜聚類算法的運算成本.