一種SOFM網(wǎng)絡(luò)的二階段聚類算法

丁天一,張 旻

(電子工程學(xué)院,合肥 230037)

1 引 言

聚類是數(shù)據(jù)挖掘、模式識別等研究方向的重要研究內(nèi)容之一,在識別數(shù)據(jù)的內(nèi)在結(jié)構(gòu)方面具有極其重要的作用.作為一種有效的數(shù)據(jù)分析方法,聚類已經(jīng)廣泛地用于語音識別、圖像處理、信息檢索和統(tǒng)計科學(xué)等領(lǐng)域[1,2].隨著人類獲取數(shù)據(jù)的手段越來越多,數(shù)據(jù)正以前所未有的速度增長和累積,人們對于聚類的要求也越來越高.一般的聚類算法,如k-means算法[3]、k-medoids算法[4]等,需要預(yù)先指定一個聚類數(shù)目,然而在實際應(yīng)用過程中聚類數(shù)目往往是未知的,因此尋求一種有效的在聚類數(shù)目未知情況下完成聚類的算法成為了一個亟待解決的問題[5].

目前為止有不少學(xué)者針對聚類數(shù)目未知情況下的聚類問題進行研究,并提出了一些算法與聚類有效性評價指標以確定最佳聚類數(shù)目.文獻[6]提出了一種基于層次劃分的最佳聚類數(shù)確定方法COPS,用于自動確定大型、復(fù)雜數(shù)據(jù)集的最佳聚類數(shù)目,但是控制計算精度參數(shù)的取值可能會對計算結(jié)果產(chǎn)生影響;文獻[7]提出了一種基于人工免疫的自適應(yīng)譜聚類算法,通過模擬抗體的克隆選擇機制和免疫系統(tǒng)的初次免疫應(yīng)答、二次免疫應(yīng)答機制,實現(xiàn)數(shù)據(jù)樣本聚類分組數(shù)的自動調(diào)整,但是算法中的閾值參數(shù)需要多次實驗確定,閾值不同實驗結(jié)果也有較大差異;文獻[8]提出了一種k-means算法的最佳聚類數(shù)確定算法,通過樣本數(shù)據(jù)分層得到聚類數(shù)搜索范圍的上界,并設(shè)計了一種聚類有效性指標評價聚類后類內(nèi)與類間相似性程度以獲取最佳聚類數(shù),但是聚類有效性指標不能保證對于每種數(shù)據(jù)集都能得到一個正確的聚類數(shù)目.文獻[9]提出了一種基于局部密度下降搜索的自適應(yīng)聚類算法,但需要人為設(shè)置多種參數(shù),迭代搜索過程使聚類耗時較大.文獻[10]提出了一種譜聚類最佳聚類數(shù)的確定方法,結(jié)合了Silhouette評價指標與局部尺度的概念,但實驗中的參數(shù)設(shè)置較為復(fù)雜,算法復(fù)雜度較高.自組織特征映射網(wǎng)絡(luò)是一種無監(jiān)督聚類算法,由于無需指定聚類數(shù)目,具有自組織學(xué)習(xí)特性,適用于高維數(shù)據(jù)聚類等優(yōu)點,而廣泛應(yīng)用于聚類問題中[11-13].但SOFM網(wǎng)絡(luò)訓(xùn)練結(jié)束后存在大量的獲勝神經(jīng)元,遠多于實際樣本類別數(shù).因此,如何有效地利用SOFM網(wǎng)絡(luò)的學(xué)習(xí)結(jié)果并確定樣本最佳聚類數(shù),對解決未知聚類數(shù)目情況下的聚類問題具有重要的意義[14].

鑒于此,本文提出了一種SOFM網(wǎng)絡(luò)的二階段聚類算法,實現(xiàn)在聚類數(shù)目未知的情況下對數(shù)據(jù)的聚類.該算法包含兩個階段:首先通過SOFM網(wǎng)絡(luò)的無監(jiān)督自組織學(xué)習(xí)過程將數(shù)據(jù)集劃分成若干個子類,每一個子類用獲勝神經(jīng)元代表該類內(nèi)的所有樣本;然后采用凝聚層次聚類的方法對獲勝神經(jīng)元進行聚類,并以樹狀圖的形式表示聚類結(jié)果;最后,綜合兩次聚類結(jié)果,將獲勝神經(jīng)元的聚類結(jié)果映射到原始數(shù)據(jù)集,得到最終聚類結(jié)果.該算法無需任何先驗知識,解決了SOFM網(wǎng)絡(luò)學(xué)習(xí)結(jié)束后獲勝神經(jīng)元較多的問題的同時,充分利用了SOFM網(wǎng)絡(luò)的自組織學(xué)習(xí)特性,結(jié)合了層次聚類算法的優(yōu)點,適合于聚類數(shù)目未知情況下數(shù)據(jù)的聚類,提高了聚類準確率和穩(wěn)定性.

2 SOFM網(wǎng)絡(luò)模型

SOFM網(wǎng)絡(luò)是由輸入層和輸出層(競爭層)組成的兩層神經(jīng)網(wǎng)絡(luò).輸入層是一維的神經(jīng)元,有n個節(jié)點,節(jié)點數(shù)n與輸入樣本向量的維數(shù)相同.輸出層是二維神經(jīng)元,按二維形式排列成節(jié)點矩陣,有m=p×q個節(jié)點.SOFM網(wǎng)絡(luò)中有兩種連接權(quán)值,即輸入神經(jīng)元與輸出神經(jīng)元之間的連接權(quán)值以及輸出神經(jīng)元的側(cè)向連接權(quán)值[15].SOFM網(wǎng)絡(luò)的二維平面陣列模型如圖1所示.

圖1 SOFM網(wǎng)絡(luò)模型Fig.1 SOFM model

SOFM網(wǎng)絡(luò)是一種無監(jiān)督聚類法,其能將任意輸入模式在輸出層映射成一維或二維離散圖形,并保持其拓撲結(jié)構(gòu)不變,即通過對輸入樣本的自組織學(xué)習(xí),在輸出層將分類結(jié)果表示出來.此外,網(wǎng)絡(luò)通過對輸入模式的反復(fù)學(xué)習(xí),可以使連接權(quán)值空間分布密度與輸入模式的概率分布趨于一致,即連接權(quán)向量空間分布能反映輸入模式的統(tǒng)計特征.

在輸入樣本類數(shù)未知的情況下,構(gòu)造SOFM網(wǎng)絡(luò)時要求輸出層神經(jīng)元的數(shù)量足夠多,造成了訓(xùn)練結(jié)束后網(wǎng)絡(luò)的輸出層存在大量的獲勝神經(jīng)元,而實際中樣本的類數(shù)遠遠小于獲勝神經(jīng)元的數(shù)目.很多獲勝神經(jīng)元權(quán)值十分接近,這些神經(jīng)元所代表的是同一個類別的樣本,將權(quán)值相近的神經(jīng)元所代表的樣本合并可以獲得更優(yōu)的聚類結(jié)果.

3 SOFM網(wǎng)絡(luò)的二階段聚類算法

SOFM網(wǎng)絡(luò)的二階段聚類算法主要分為SOFM網(wǎng)絡(luò)對數(shù)據(jù)集的粗聚類過程和層次聚類對獲勝神經(jīng)元的細聚類過程兩部分.在對輸入樣本進行數(shù)據(jù)預(yù)處理之后,通過SOFM網(wǎng)絡(luò)的自組織學(xué)習(xí)過程將樣本分為若干個簇,以獲勝神經(jīng)元代表每一個簇內(nèi)的所有樣本.下一步,通過層次聚類的方法,對獲勝神經(jīng)元進行聚類,將同一類別神經(jīng)元對應(yīng)的所有樣本合并,得到最終的聚類結(jié)果.

3.1 數(shù)據(jù)預(yù)處理

在數(shù)據(jù)集輸入到SOFM網(wǎng)絡(luò)的輸入層之前,需要對數(shù)據(jù)進行規(guī)范化處理以適用于SOFM網(wǎng)絡(luò)的學(xué)習(xí)過程,本文采用如下的歸一化(最小-最大規(guī)范化)處理方式:

(1)

3.2 基于SOFM網(wǎng)絡(luò)的粗聚類

SOFM網(wǎng)絡(luò)采用Kohonen學(xué)習(xí)規(guī)則,總結(jié)起來主要分為兩步:第一,尋找最優(yōu)匹配神經(jīng)元,即競爭學(xué)習(xí)過程;第二,更新權(quán)值的自適應(yīng)調(diào)整過程,即輸出層神經(jīng)元的側(cè)反饋過程.具體步驟如下:

Step1.網(wǎng)絡(luò)初始化.初始化權(quán)值wij(0),(i=1,2,…,n;j=1,2,…,m),賦予wij(0)一個[0,1]區(qū)間內(nèi)的隨機值.初始化設(shè)置各輸出神經(jīng)元j的鄰域初始值NEj(0).確定學(xué)習(xí)速率的初始值γ(0)(0<γ(0)<1)和總的學(xué)習(xí)次數(shù)K.

Step2.尋找樣本向量的最優(yōu)匹配神經(jīng)元.提供一個新的樣本向量作為網(wǎng)絡(luò)的輸入,計算輸入向量與所有輸出層神經(jīng)元之間的歐氏距離dj,并求出dj*滿足式(2)條件下的輸出層神經(jīng)元j*(j*∈[1,m]).

(2)

Step3.調(diào)整連接權(quán)值.修正輸出神經(jīng)元j*與其鄰域內(nèi)其他神經(jīng)元與輸入層神經(jīng)元之間的連接權(quán)值:

wij(k+1)=wij(k)+γ(k)(xj-wij(k))

(3)

式(3)中,j∈NEj*(k),i∈[1,n],γ(k)為第k次學(xué)習(xí)時的學(xué)習(xí)速率.

返回Step 2,直至輸入向量全部提供給網(wǎng)絡(luò).

Step4.更新學(xué)習(xí)速率γ(k)及鄰域NEj(k):

(4)

(5)

式(4)和式(5)中,γ(0)為學(xué)習(xí)速率的初始值,NEj(0)為鄰域NEj(k)的初始值,INT(x)為取整符號,k為學(xué)習(xí)次數(shù),K為總的學(xué)習(xí)次數(shù).

令k=k+1,返回Step 2,直至k=K迭代結(jié)束.

假設(shè)M為輸入樣本向量的數(shù)量,即數(shù)據(jù)集的樣本個數(shù)為M,通過上述的學(xué)習(xí)過程,最終學(xué)習(xí)后的網(wǎng)絡(luò)將樣本數(shù)據(jù)劃分成C類,即:

(6)

式(6)中,C表示獲勝神經(jīng)元的數(shù)目,D1,D2,…,DC表示樣本數(shù)據(jù)的粗聚類結(jié)果.

3.3 基于凝聚層次聚類的細聚類

SOFM網(wǎng)絡(luò)對樣本向量自組織學(xué)習(xí),得到了樣本數(shù)據(jù)的粗聚類結(jié)果,輸出層的網(wǎng)格中以獲勝神經(jīng)元權(quán)值分布的形式保存了輸入樣本的分布與拓撲信息.通過對學(xué)習(xí)后的神經(jīng)元權(quán)值進行聚類,可得到進一步的細聚類結(jié)果.學(xué)習(xí)結(jié)束后神經(jīng)元權(quán)值分布往往是不規(guī)則的,本文采用凝聚層次聚類方法對神經(jīng)元權(quán)值進行聚類.凝聚層次聚類是一種采用自底而上聚合策略的層次聚類算法,以單個數(shù)據(jù)對象為初始簇,最近簇相聚和的方法融合,直至得到期望的聚類數(shù)為止[16].

假定有N個對象要被聚類,構(gòu)造N×N的相似矩陣D=d(i,j),聚類結(jié)果用序號0,1,…,n-1表示,L(m)表示第m次聚類的層次.簇的序號用m表示,簇r和簇s的相似系數(shù)(即相似矩陣中的值)用d(r,s)表示.

層次聚類在構(gòu)造相似度矩陣的過程中有很多種距離的度量方法,本文選取了Ward′s method(離差平方和)的距離度量方法,將簇間的距離d(r,s)定義為兩個簇合并時產(chǎn)生的誤差平方和:

(7)

基于最小距離的凝聚層次聚類算法描述如下:

Step1.L(0)=0,m=0.

Step2.從當前所有簇對中,根據(jù)d(r,s)=mind(i,j)找到距離最近的兩個簇r,s.

Step3.簇的序列號加1,即m=m+1,將簇r和簇s合并,令聚類的層次L(m)=[d(r,s)].

Step4.更新相似矩陣D,刪除簇r,s相應(yīng)的行和列,并在矩陣中加上新生成的簇相應(yīng)的行和列.相似矩陣中新生成的簇(r,s)和原來的簇k的相似度由下式定義:

d(k,(r,s))=min(d(k,r),d(k,s))

(8)

Step5.重復(fù)Step 2～Step 4,直到所有對象都被合并到一個簇為止.

凝聚層次聚類算法一直執(zhí)行到所有樣本出現(xiàn)在同一個簇中,以“樹狀圖”的形式表示聚類結(jié)果,其中每層鏈接一組聚類簇.在樹狀圖的特定層次上進行分割,可得到相應(yīng)的簇劃分結(jié)果.

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

為了驗證SOFM網(wǎng)絡(luò)的二階段聚類算法的性能,本文設(shè)計了兩個實驗.實驗1通過模擬一組分布雜亂的人工數(shù)據(jù)集來驗證SOFM網(wǎng)絡(luò)的二階段聚類算法過程的可行性,實驗2從UCI數(shù)據(jù)集中選取3種典型的數(shù)據(jù)集,分別用k-means算法、層次聚類算法、基于U-Matrix可視化分析的SOFM網(wǎng)絡(luò)聚類算法和SOFM網(wǎng)絡(luò)的二階段聚類算法對數(shù)據(jù)集進行聚類實驗,通過比較四種聚類算法的正確率驗證本文算法的有效性.

4.1 人工數(shù)據(jù)集仿真實驗

為了驗證SOFM網(wǎng)絡(luò)的二階段聚類算法過程的可行性,實驗參照文獻[7]的方法隨機生成一組服從正態(tài)分布的二維模擬數(shù)據(jù),共包含140個樣本,生成人工數(shù)據(jù)集的參數(shù)如表1所示.其中,μx、μy為用于生成正態(tài)分布數(shù)據(jù)的均值,σ為標準差.

首先,采用k-means算法對人工數(shù)據(jù)集進行聚類實驗,選取聚類數(shù)目k=5時得到的4次聚類結(jié)果如圖2所示.

由圖2可以看出,當數(shù)據(jù)集的分布較為接近時,即便是在指定聚類數(shù)目k的情況下,由于k-means算法聚類初始中心的不確定性,也會造成重復(fù)實驗過程中聚類結(jié)果的多樣性,且不同聚類結(jié)果差別較大.

表1 人工數(shù)據(jù)集的參數(shù)值
Table 1 Parameter value of artificial datasets

參數(shù)第1類第2類第3類第4類第5類μx37745μy24865σ0．50．50．50．30．3樣本數(shù)3030302030

下一步,采用本文的算法對人工數(shù)據(jù)集進行聚類實驗.在建立SOFM網(wǎng)絡(luò)時,輸出層二維映射神經(jīng)元的節(jié)點矩陣采用10×10的排列形式,拓撲結(jié)構(gòu)采用六邊形結(jié)構(gòu),學(xué)習(xí)次數(shù)設(shè)置為500.將歸一化處理后的人工數(shù)據(jù)集輸入到SOFM網(wǎng)絡(luò)的輸入層,學(xué)習(xí)結(jié)束后得到的輸出層結(jié)果如圖3所示.

圖2 k-means算法聚類結(jié)果Fig.2 Clustering results of k-means algorithm

圖3 學(xué)習(xí)結(jié)束后的輸出層結(jié)果Fig.3 Result of the output layer after learning

通過SOFM網(wǎng)絡(luò)對樣本的學(xué)習(xí),網(wǎng)格中保存了輸入樣本的分布與拓撲信息.在輸出層的100個神經(jīng)元中,有71個獲勝神經(jīng)元,每一個網(wǎng)格中的數(shù)字表示獲勝神經(jīng)元所代表的樣本數(shù)目.實驗中SOFM網(wǎng)絡(luò)將輸入樣本分為71類,每一類只代表少量的樣本,此時SOFM網(wǎng)絡(luò)的學(xué)習(xí)結(jié)果作為人工數(shù)據(jù)集的粗聚類結(jié)果.

采用凝聚層次聚類對SOFM網(wǎng)絡(luò)學(xué)習(xí)后的神經(jīng)元權(quán)值進行聚類,通過對層次聚類樹狀圖的觀察分析以確定一個合適的聚類數(shù),實驗結(jié)果如圖4所示,從樹狀圖中可以得到簇與簇之間的連接關(guān)系與相似度.

圖4 獲勝神經(jīng)元的聚類樹狀圖Fig.4 Clustertree of the winning neuron

通過圖4可以看出,當聚類數(shù)目k=5時,聚類所得到的簇與簇之間的距離較大,此時神經(jīng)元權(quán)值能得到最佳的聚類結(jié)果.選取聚類數(shù)目k=5時,綜合二階段過程的聚類結(jié)果,得到人工數(shù)據(jù)集的聚類結(jié)果如圖5所示.

圖5 人工數(shù)據(jù)集聚類結(jié)果Fig.5 Clustering result of artificial datasets

從圖5可以看出,在人工數(shù)據(jù)集仿真實驗中,SOFM網(wǎng)絡(luò)的二階段聚類算法可以提供一個合適的聚類數(shù)目,并且能夠準確地劃分數(shù)據(jù).

4.2 UCI數(shù)據(jù)集仿真實驗

為了驗證SOFM網(wǎng)絡(luò)的二階段聚類算法對于復(fù)雜分布數(shù)據(jù)的有效性,實驗選取了UCI數(shù)據(jù)集中的Iris、Wine和Pima Indians Diabetes作為實驗的數(shù)據(jù)集,數(shù)據(jù)集屬性特征如表2所示.

表2 UCI數(shù)據(jù)集屬性特征
Table 2 Attribute feature of UCI dataset

數(shù)據(jù)集IrisWinePID樣本個數(shù)150178768維數(shù)4138類別數(shù)332

實驗中分別用k-means算法、Single-linkage層次聚類算法、基于U-Matrix可視化分析的SOFM網(wǎng)絡(luò)聚類算法和本文算法對以上數(shù)據(jù)集進行聚類實驗,通過數(shù)據(jù)集聚類結(jié)果的正確率指標來比較四種算法的性能,聚類正確率定義為:

(9)

由于SOFM網(wǎng)絡(luò)的自組織學(xué)習(xí)特性以及k-means算法初始中心點選取的隨機性,實驗中對每種算法在每個UCI數(shù)據(jù)集上分別進行50次實驗,實驗得到的四種聚類算法求解UCI數(shù)據(jù)集的聚類正確率的平均值如表3所示.

表3 四種算法在求解UCI數(shù)據(jù)集時的性能比較
Table 3 Performance comparison of four algorithms in solving the UCI datasets

數(shù)據(jù)集平均聚類正確率本文算法k?meansSingle?linkageU?MatrixSOFMIris0．87480．80530．66670．6667Wine0．94580．66780．69660．6685PID0．65750．61750．64840．5833

由表3的統(tǒng)計結(jié)果可以看出,本文提出的算法在對三組UCI數(shù)據(jù)集進行的聚類實驗過程中取得了較好的聚類結(jié)果,聚類結(jié)果的正確率均高于其他算法.因此,本文提出的算法對于復(fù)雜分布數(shù)據(jù)的聚類是有效的.

5 結(jié)束語

本文通過對SOFM網(wǎng)絡(luò)自組織學(xué)習(xí)特性的分析,結(jié)合層次聚類算法,提出了一種SOFM網(wǎng)絡(luò)的二階段聚類算法.在粗聚類階段,通過SOFM網(wǎng)絡(luò)的自組織學(xué)習(xí)過程,得到以獲勝神經(jīng)元為代表的若干個簇;在細聚類階段,通過凝聚層次聚類的方法,對獲勝神經(jīng)元進行再聚類;最后綜合兩階段的聚類結(jié)果,得到數(shù)據(jù)集最終的聚類結(jié)果.通過人工數(shù)據(jù)集和UCI數(shù)據(jù)集驗證了本文算法的可行性與有效性,實驗結(jié)果表明,SOFM網(wǎng)絡(luò)的二階段聚類算法具有較高的準確率,可以在聚類數(shù)目未知的情況下較好地完成數(shù)據(jù)的聚類.

[1] Han Jia-wei,Kamber Micheline,Pei Jian.Data mining:concepts and techniques[M].Beijing:China Machine Press,2012.

[2] Sun Ji-gui,Liu Jie,Zhao Lian-yu.Clustering algorithms research[J].Journal of Software,2008,19(1):48-61.

[3] Hartigan J A,Wong M A.A k-means clustering algorithm[J].Applied Statistics,1979,28(1):100-108.

[4] Park H S,Jun C H.A simple and fast algorithm for k-medoids clustering[J].Expert Systems with Applications,2009,36(2):3336-3341.

[5] Wang Jun,Wang Shi-tong,Deng Zhao-hong.Survey on challenges in clustering analysis research[J].Control and Decision,2012,27(3):321-328.

[6] Chen Li-fei,Jiang Qing-shan,Wang Sheng-rui.A hierarchical method for determining the number of clusters[J].Journal of Software,2008,19(1):62-72.

[7] Guo Kai,Li Hai-fang,Wang Hui-qing.An adaptive spectral clustering algorithm based on artificial immune[J].Journal of Chinese Computer Systems,2013,34(4):856-859.

[8] Wang Yong,Tang Jing,Rao Qin-fei,et al.High efficient k-means algorithm for determining optimal number of clusters[J].Journal of Computer Applications,2014,34(5):1331-1335.

[9] Xu Zheng-guo,Zheng Hui,He Liang,et al.Self-adaptive clustering based on local density by descending search[J].Journal of Computer Research and Development,2016,53(8):1719-1728.

[10] Mur A,Dormido R,Duro N,et al.Determination of the optimal number of clusters using a spectral clustering optimization[J].Expert Systems with Applications,2016,65(23):304-314.

[11] Stephanakis I M,Anastassopoulos G C,Iliadis L.A self-organizing feature map(SOFM)model based on aggregate-ordering of local color vectors according to block similarity measures[J].Neuro Computing,2013,107(4):97-107.

[12] Huang C H,Lin C H.Multiple harmonic-source classification using a self-organization feature map network with voltage-current wavelet transformation patterns[J].Applied Mathematical Modelling,2015,39(19):5849-5861.

[13] Li N,Cheng X,Zhang S,et al.Realistic human action recognition by fast HOG3D and self-organization feature map[J].Machine Vision and Applications,2014,25(7):1793-1812.

[14] Brugger D,Bogdan M,Rosenstiel W.Automatic cluster detection in Kohonen′s SOM[J].IEEE Transactions on Neural Networks,2008,19(3):442-459.

[15] Wu S,Chow T W S.Clustering of the self-organizing map using a clustering validity index based on inter-cluster and intra-cluster density[J].Pattern Recognition,2004,37(2):175-188.

[16] Zhou Chen-xi,Liang Xun,Qi Jin-shan.A semi-supervised agglomerative hierarchical clustering method based on dynamically updating constraints[J].Acta Automatica Sinica,2015,41(7):1253-1263.

附中文參考文獻：

[1] Han Jia-wei,Kamber Micheline,Pei Jian.數(shù)據(jù)挖掘:概念與技術(shù)[M].北京:機械工業(yè)出版社,2012.

[2] 孫吉貴,劉 杰,趙連宇.聚類算法研究[J].軟件學(xué)報,2008,19(1):48-61.

[5] 王 駿,王士同,鄧趙紅.聚類分析研究中的若干問題[J].控制與決策,2012,27(3):321-328.

[6] 陳黎飛,姜青山,王聲瑞.基于層次劃分的最佳聚類數(shù)確定方法[J].軟件學(xué)報,2008,19(1):62-72.

[7] 郭 凱,李海芳,王會青.一種人工免疫的自適應(yīng)譜聚類算法[J].小型微型計算機系統(tǒng),2013,34(4):856-859.

[8] 王 勇,唐 靖,饒勤菲,等.高效率的K-means最佳聚類數(shù)確定算法[J].計算機應(yīng)用,2014,34(5):1331-1335.

[9] 徐正國,鄭 輝,賀 亮,等.基于局部密度下降搜索的自適應(yīng)聚類方法[J].計算機研究與發(fā)展,2016,53(8):1719-1728.

[16] 周晨曦,梁 循,齊金山.基于約束動態(tài)更新的半監(jiān)督層次聚類算法[J].自動化學(xué)報,2015,41(7):1253-1263.