基于核函數(shù)的高維離散數(shù)據(jù)聚類算法研究與應(yīng)用

葉福蘭

(福州外語外貿(mào)學(xué)院理工學(xué)院，福州 350202)

0 前言

伴隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，我們迎來了大數(shù)據(jù)時(shí)代，生活的各個(gè)領(lǐng)域積累了大量有價(jià)值的數(shù)據(jù)信息，這些數(shù)據(jù)的規(guī)模越來越大，維度越來越高，復(fù)雜度也越來越強(qiáng)。如何對(duì)這些高維數(shù)據(jù)進(jìn)行高效分析，挖掘潛在的、有價(jià)值的信息是值得研究的一個(gè)重要課題。聚類分析作為一種無監(jiān)督的機(jī)器學(xué)習(xí)方法，是目前最為常用的挖掘數(shù)據(jù)信息的方法之一，旨在從大量的數(shù)據(jù)中獲取潛在的、有價(jià)值的、未知的信息。傳統(tǒng)的聚類算法常用于連續(xù)型數(shù)據(jù)的研究，對(duì)樣本未進(jìn)行優(yōu)化，無法達(dá)到高精度的聚類效果。作為一種主流的統(tǒng)計(jì)學(xué)習(xí)方法，核學(xué)習(xí)是解決許多統(tǒng)計(jì)學(xué)習(xí)問題的有力工具，核函數(shù)的引入可以將非線性問題轉(zhuǎn)化為線性問題，從而得到準(zhǔn)確挖掘。

1 聚類分析[1]

聚類分析是將數(shù)據(jù)樣本按照其特征分成不同的簇(類)，使得相同簇之間的對(duì)象具有較大的相似性，而不同簇之間的對(duì)象具有較大的差異性。主要的聚類分析方法有：基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法及基于模型的方法。主要的基于劃分的方法有k-Means算法和k-Medoids算法；基于層次的聚類方法有凝聚法和分裂法；具有代表性的基于密度的算法有DBSCAN算法和OPTICS算法；基于網(wǎng)格的方法將空間對(duì)象轉(zhuǎn)化成有限的單元，形成網(wǎng)格結(jié)構(gòu)，如STING算法、WaveCluster算法以及CLIQUE算法等；基于模型的方法試圖找到數(shù)據(jù)樣本與某統(tǒng)計(jì)模型的最優(yōu)擬合，如：COBWEB算法、EM算法等。

聚類分析方法通常通過計(jì)算距離來衡量數(shù)據(jù)之間的相似度，距離值越小表示兩個(gè)數(shù)據(jù)對(duì)象相似性越大，反之差異越大，常用的距離計(jì)算方法有(設(shè)有兩個(gè)n維向量x(x1，x2，…，xn)，y(y1，y2，…，yn))：

(1)

(2)

(3)

還有曼哈頓距離、馬氏距離等。

2 高維數(shù)據(jù)聚類分析

高維數(shù)據(jù)存在稀疏性的特點(diǎn)，隨著數(shù)據(jù)維度的增加，使用傳統(tǒng)的聚類算法進(jìn)行分析后得到的結(jié)果誤差越來越大，影響聚類效果。為了解決維度災(zāi)難所帶來的問題，目前針對(duì)高維數(shù)據(jù)的聚類方法主要有基于聯(lián)合的聚類、基于超圖的聚類、基于子空間的聚類、基于降維的聚類，而基于子空間和基于降維的聚類居多?；谧涌臻g的聚類是從樣本數(shù)據(jù)中選取多個(gè)不同的子集，分別針對(duì)子集對(duì)應(yīng)的子空間進(jìn)行聚類，將聚類局部化在相關(guān)維中進(jìn)行，可以分為硬子空間算法(如PROCLUS算法)和軟子空間算法(如WFCM算法)?；诮稻S的聚類是處理高維數(shù)據(jù)的一個(gè)重要手段，通過將原始高維數(shù)據(jù)轉(zhuǎn)換為低維空間，對(duì)低維空間數(shù)據(jù)進(jìn)行聚類，再將聚類結(jié)果擴(kuò)展到原高維空間中，分為線性降維和非線性降維。線性降維要求數(shù)據(jù)集的特征屬性是線性的，對(duì)于非線性結(jié)構(gòu)數(shù)據(jù)集要求采用非線性降維方法解決問題。非線性降維典型算法有：KPCA算法，MDS算法，Isomap算法等。

3 核函數(shù)[2]

核函數(shù)是一種測(cè)量數(shù)據(jù)樣本相似度的重要方法，將核函數(shù)引入到聚類分析中，使得原有的高維線性非線性可分的空間映射到線性可分的假設(shè)特征空間中，在低維空間計(jì)算表現(xiàn)高維空間的分類效果，在輸入空間與特征空間中建立起了一座橋梁，有效解決非線性和維度災(zāi)難問題。核函數(shù)定義如下：

對(duì)任意的xi∈Rn(Rn為輸入空間，i=1，2，…，n)，φ函數(shù)是從Rn到高維特征空間H的映射，若存在函數(shù)k(xi，xj)=φ(xi)φ(xj)(φ(xi)φ(xj)為xi，xj映射到特征空間上的內(nèi)積)，則稱k(xi，xj)為核函數(shù)。常見的核函數(shù)有：線性核函數(shù)、多項(xiàng)式核函數(shù)、徑向基核函數(shù)RBF、Sigmoid核函數(shù)、傅里葉核函數(shù)等。

1)線性核：k(xi，xj)=(xi，xj)，

(4)

2)多項(xiàng)式核：k(xi，xj)= ((xi?xj)+1)d，

(5)

(6)

4)感知器核：k(xi，xj)=tanh(k(xi，xj)+ν)，

(7)

0

(8)

4 基于多核的降維聚類算法分析

4.1 KPCA算法

4.1.1 PCA算法

面對(duì)高維數(shù)據(jù)維度災(zāi)難問題，我們需要對(duì)數(shù)據(jù)樣本進(jìn)行降維，通過降維技術(shù)過濾數(shù)據(jù)樣本中的冗余信息。PCA方法通過將原始數(shù)據(jù)通過線性變換映射到新的特征空間中，用盡可能少的特征組合表示原始數(shù)據(jù)。PCA算法首先對(duì)原始樣本數(shù)據(jù)構(gòu)成的n維矩陣去均值化，即求出每列的平均值，將該列所有數(shù)減去該平均值，使得每個(gè)特征的均值為零；接著求其協(xié)方差矩陣，根據(jù)協(xié)方差矩陣求出特征值及特征向量，將特征值從大到小進(jìn)行排序，選擇其中最大的k個(gè)，然后將對(duì)應(yīng)的k個(gè)特征向量分別作為列向量組成特征向量矩陣；最后將樣本點(diǎn)投影到選取的特征向量中。以上實(shí)現(xiàn)了將一組n維數(shù)據(jù)降為k維，其目標(biāo)實(shí)現(xiàn)了將原始數(shù)據(jù)變換到k個(gè)正交基，使得各字段間的協(xié)方差為0，而字段的方差則盡可能大。

4.1.2 KPCA算法

KPCA是基于PCA算法的基礎(chǔ)上引入核函數(shù)后的一種非線性分析方法，首先把核函數(shù)隱式地將輸入空間轉(zhuǎn)換到一個(gè)非線性特征空間中，接著在該非線性特征空間中進(jìn)行PCA線性變換。對(duì)非線性特種空間中的樣本數(shù)據(jù)集進(jìn)行線性分析時(shí)，通過核函數(shù)進(jìn)行隱式定義，無需進(jìn)行直接計(jì)算，只需通過計(jì)算核函數(shù)的內(nèi)積即可。針對(duì)離散數(shù)據(jù)集的對(duì)象，只能通過KPCA進(jìn)行處理。例如：對(duì)于人臉圖像，不同人之間的數(shù)據(jù)，存在著非線性關(guān)系，通過KPCA進(jìn)行非線性分析，所得到的識(shí)別率遠(yuǎn)高于PCA算法。

4.2 多核函數(shù)構(gòu)造[3-4]

盡管核函數(shù)在聚類分析中得到了有效且廣泛的應(yīng)用，但單個(gè)核函數(shù)均是基于單個(gè)特征空間，單核函數(shù)無法滿足異構(gòu)、不規(guī)則樣本的分析。不同的核函數(shù)有著不同的特征屬性，適用于不同的應(yīng)用場(chǎng)合，通過組合多個(gè)核函數(shù)，對(duì)每個(gè)核函數(shù)賦予不同權(quán)重值，根據(jù)樣本數(shù)據(jù)的特征屬性區(qū)別映射到不同的特征空間中，構(gòu)造組合成新的核函數(shù)，使數(shù)據(jù)樣本在新的特征空間中得到更好的表現(xiàn)，能大大提高聚類分析的效果。但如何對(duì)單核函數(shù)進(jìn)行組合，以及在組合過程中各核函數(shù)的權(quán)重是多大，是多核函數(shù)需要考慮的重點(diǎn)問題。根據(jù)核函數(shù)的性質(zhì)，如果對(duì)多個(gè)單核函數(shù)加權(quán)后得到的核滿足Mercer條件，則該核為核函數(shù)。

在構(gòu)造組合核函數(shù)前，先了解核對(duì)齊。核對(duì)齊不僅可以衡量核函數(shù)參數(shù)選擇的優(yōu)劣，同樣還可以表示核函數(shù)與目標(biāo)函數(shù)或者核函數(shù)與另一個(gè)核函數(shù)之間的相似性度量，作為構(gòu)造最優(yōu)組合核函數(shù)的依據(jù)。設(shè)K1，K2分別為核函數(shù)k1，k2的核矩陣，則核函數(shù)對(duì)齊定義為：

(9)

若理想核函數(shù)為yy′，則核函數(shù)k與理想核函數(shù)yy′的核對(duì)齊為：

(10)

(11)

應(yīng)用內(nèi)點(diǎn)法對(duì)以上半定規(guī)劃模型求解權(quán)重βi，從而得出最優(yōu)組合核函數(shù)。

4.3 降維多核聚類算法實(shí)現(xiàn)

4.3.1 降維多核聚類算法實(shí)現(xiàn)[3]

面對(duì)高維數(shù)據(jù)，采用傳統(tǒng)的核函數(shù)進(jìn)行聚類，效果不佳。首先，考慮先將高維數(shù)據(jù)采用PCA降維技術(shù)進(jìn)行降維處理；再次，結(jié)合聚類算法的基本思路，將最優(yōu)組合多核函數(shù)替代單核函數(shù)，對(duì)降維后的數(shù)據(jù)進(jìn)行聚類分析處理。得到降維多核聚類算法描述如下：

輸出：各類簇的樣本；

Step1：首先利用PCA降維技術(shù)實(shí)現(xiàn)對(duì)所輸入的原始數(shù)據(jù)集D進(jìn)行降維處理，得到降維后的數(shù)據(jù)集D′；

Step2：將得到的數(shù)據(jù)集D′映射到構(gòu)造的多核函數(shù)核空間中，根據(jù)聚類算法，隨機(jī)選擇m個(gè)樣本作為初始簇中心點(diǎn)；

Step3：計(jì)算其余樣本對(duì)象到簇中心的距離，并歸類到最相似的簇中；

Step4：計(jì)算簇的新均值，重新選擇簇中心；

Step5：計(jì)算目標(biāo)函數(shù)；

Step6：重復(fù)Step2至Step5，直到目標(biāo)函數(shù)收斂或中心點(diǎn)不再變化，結(jié)束算法。

4.3.2 降維多核聚類算法實(shí)驗(yàn)[5]

為了驗(yàn)證算法的實(shí)驗(yàn)效果，將基于多核的降維算法應(yīng)用于機(jī)器故障診斷中，圖1給出故障識(shí)別的精確率對(duì)比情況，從圖可以看出新的組合核函數(shù)性能要高于單核函數(shù)，能夠獲得更好的聚類效果。

圖1 故障精確率對(duì)比圖

5 結(jié)語

不同的核函數(shù)有著各自不同的特性，聚類過程中會(huì)產(chǎn)生不同的分類效果，所以最優(yōu)組合核函數(shù)中權(quán)重的選擇至關(guān)重要。本文首先分析了聚類的幾種主要算法以及相似性度量的幾種常見方法，接著分析了高維數(shù)據(jù)的聚類分析方法以及對(duì)核函數(shù)進(jìn)行了介紹，針對(duì)傳統(tǒng)單核函數(shù)的弊端，提出基于多核函數(shù)的高維離散數(shù)據(jù)聚類算法研究。