一種改進(jìn)地標(biāo)點(diǎn)采樣的不平衡數(shù)據(jù)聚類算法

韓素青，李淑慧

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

0 引言

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

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

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

1 相關(guān)概念

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

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

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

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

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

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

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

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

1.2 抽樣方法

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

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

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

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

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

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

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

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

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

Z=P∑Q

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

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

2.1 SRK抽樣法

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

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

β的選擇方法如下：

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

2)計(jì)算每對(duì)樣本點(diǎn)之間的歐式距離；

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

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

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

2.2 LSC-SRK算法

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

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

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

輸出：k個(gè)簇；

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

Step2 在每個(gè)簇中按定義2.1計(jì)算類抽樣比例SR，并按比例對(duì)Ci進(jìn)行簡(jiǎn)單隨機(jī)抽樣；

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

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

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

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

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

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

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

3.1 有效性評(píng)價(jià)指標(biāo)

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

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

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

accuracy的表達(dá)式如下：

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

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

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

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

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

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

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

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

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

3.3 實(shí)驗(yàn)情況

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

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

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

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

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

4 結(jié)束語

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