【正文】 本章小結(jié) 本章 詳細(xì)的介紹了 SOM 聚類算法的網(wǎng)絡(luò)特性和具體的步驟，以及 SOM 算法的優(yōu)點以及存在的問題。鄰域半徑也隨著學(xué)習(xí)代數(shù)的增加而遞減，最后只有獲勝結(jié)點在學(xué)習(xí)。 基于文本的聚類算法研究 25 步驟 9:參數(shù)調(diào)整。 步驟 8:更新。 步驟 7:確定獲勝 神經(jīng)元。 步驟 6:取樣。 步驟 5:用這 K個數(shù)據(jù)點對 SOM網(wǎng)絡(luò)的權(quán)值進(jìn)行初始化，同時初始化學(xué)習(xí)率“。 步驟 4:在每次聚類時，算法接受用戶輸入的輸出層神經(jīng)元結(jié)點數(shù)目參數(shù) K，對于這些中心點，找到一個合適的相似度閩值，使得在這個相似度闡值下，有 K個中心點它們之間的相似度小于這個閩值。 步驟 3:為這些密集小區(qū)域生成中心點向量。圖中結(jié)點 e依據(jù) score 將被選中，它包括了 {3， 4， 5， 6， 7， 8}，這個密集的文檔集合中有可能包括模式類別的中心。理論表明，文檔數(shù)據(jù)點密集區(qū)可能包含模式類別的中心或離模式類別的中心較近，本文提出一種用層次聚類法探測數(shù)據(jù)密集區(qū)，用探測到的 K個數(shù)據(jù)密集區(qū)中心點隨機(jī)初始化權(quán)值，以期提高網(wǎng)絡(luò)收斂的速度。于是，用 SOM 對數(shù)據(jù)進(jìn)行聚類時，對連接權(quán)值進(jìn)行初始化時，可以試圖從輸入模式空間中找出 K個有代表性的點，它們能代表各個模式類別的中心，或者與各個模式類別的方向相似，最起碼相差不能太大。連接權(quán)值的理想分布是其方向與各個模式類別的方向一致，但在初始化時想做到這一點是不現(xiàn)實的，因為這是網(wǎng)絡(luò)訓(xùn)練所要達(dá)到的目的，在網(wǎng)絡(luò)收斂時，連接權(quán)的方向與各個模式類別的方向一致。由于文本數(shù)據(jù)的高維性，在進(jìn)行聚類之前，一般要進(jìn)行特征選擇和特征抽取，以降低文本數(shù)據(jù)的維度。這種方法相對于隨機(jī)初始化連接權(quán)值來說，網(wǎng)絡(luò)訓(xùn)練時，尋找輸入模式的最佳映射相對容易，但因為隨機(jī)選取的 K個矢量不一定與模式的類別方向一致，達(dá)到網(wǎng)絡(luò)收斂的學(xué)習(xí)次數(shù)波動性較大。 (2)所有連接權(quán)矢量賦予相同權(quán)值 :將所有的連接權(quán)矢量賦予相同的初始值，這樣可以減少輸入模式在最初階段對連接權(quán)矢量的挑選余地，增加每一個權(quán)矢量被選中的機(jī)會，盡可能快地校正連接權(quán)矢量和輸入模式之間的方向偏差，加快收斂的速度 。這樣在網(wǎng)絡(luò)訓(xùn)練時，尋找輸入模式的最佳映射就非常困難，為達(dá)到網(wǎng)絡(luò)收練，需經(jīng)過很多次的反復(fù)學(xué)習(xí)。目前有下面幾種常用的初始化方法 : (1)隨機(jī)初始化權(quán)值 :一般學(xué)習(xí)規(guī)則是將網(wǎng)絡(luò)的連接權(quán)賦予區(qū)間內(nèi)的隨機(jī)值。因此連接權(quán)的初始狀態(tài)對網(wǎng)絡(luò)的訓(xùn)練過程影響很大。一般說來，初始權(quán)值設(shè)置不當(dāng)，有可能造成在某一局部極小值周圍長期徘徊不出，收斂所需的時間延長，甚至收斂到局部最優(yōu)或不收斂 。不同的初始權(quán)，在其它條件相同的情況下，可能達(dá)到不同的輸出方差水平。 步驟 7: 返回步驟 2，直至算法收斂或達(dá)到最大迭代次數(shù)為為止。 步 驟 6: 更新每個輸出層神經(jīng)元結(jié)點的類內(nèi)離差。調(diào)整學(xué)習(xí)率和鄰域半徑，為了保證算法的收斂，學(xué)習(xí)率的取值一般在 0到 1之間，且隨著學(xué)習(xí)代數(shù)的增加而遞減 。 步驟 4: 更新按更新獲勝神經(jīng)元及其鄰域內(nèi)所有神經(jīng)元的連接權(quán)值，而鄰域外的神經(jīng)元的連接權(quán)值保持不變。對所有輸入樣本執(zhí)行步驟 3一步驟 6 步驟 3: 確定獲勝神經(jīng)元。對于輸出層每個神經(jīng)元結(jié)點的類內(nèi)離差初始化為 D(s。 EDSOM 算法的基本步驟可描述如下 : 基于文本的聚類算法研究 22 步驟 1：初始化連接權(quán)值 w，學(xué)習(xí)率。 所以，本文把等類內(nèi)離差準(zhǔn)則引入到 SOM算法的學(xué)習(xí)策略中，在爭學(xué)習(xí)的過程中，將決定那個神經(jīng)元獲勝的策略加以修改，定義新的距離測度為 :d(x1， x 2)=d(x， z)D(S)顯然當(dāng) D(s)增加時， d(x， Z)隨之增加，這就減少了神經(jīng)元 ，最終結(jié)果將導(dǎo)致所有區(qū)域的類內(nèi)離差趨于相等。最優(yōu)聚類器的必要條件是指最近鄰條件和質(zhì)心條件。 (2)等類內(nèi)離差原則聚類問題的實質(zhì)就是求出適當(dāng) s和 z，使總類內(nèi)離差 D(s)最小。 等離 差理論在神經(jīng)元獲勝策略中的應(yīng)用改進(jìn) (l)文本聚類的目標(biāo)函數(shù)基于劃分的聚類器的基本思想是 :一個 K階的聚類器把輸入空間分成 K個小空間 S1， S2， ? ， Sk，每個小空間 S代表一個類別，每個小空間 S 內(nèi)的聚類中心用 z。但是聚類沒有以類內(nèi)離差最小一平均類內(nèi)相似度最大為基礎(chǔ)，很難保證可以得到使平均類內(nèi)離差最小一平均類內(nèi)相似度最大的聚類結(jié)果。然后計算各亞興奮神經(jīng)元所處位置的 NO 濃度，則 NO 濃度最高的神經(jīng)元為最終獲勝單元。 (5)DSOM 該種學(xué)習(xí)策略是把內(nèi)源性一氧化氮 (NO)的四維動態(tài)擴(kuò)散特性和其在長時間學(xué)習(xí)過程中的增強作用應(yīng)用到 SOM 中，輸入向量 X 輸入網(wǎng)絡(luò)后，以某種規(guī)基于文本的聚類算法研究 21 則 (評價函數(shù) )確定競爭層中一組獲勝神經(jīng)元，稱為亞興奮神經(jīng)元簇。 (3)ESOM 把更新獲勝結(jié)點 Z及其領(lǐng)域結(jié)點的權(quán)值修改。 (1)SOMCV 該種方法把 SOM 網(wǎng)絡(luò)的權(quán)值都初始化為 l/m(m 是輸入向量的維 數(shù) )，每個輸入向量 xj要經(jīng)過如下修正后再輸入網(wǎng)絡(luò)。 (2)相反有些神經(jīng)元因為獲勝次數(shù)過多，出現(xiàn)神經(jīng)元過度利用的問題。只有獲勝節(jié)點才允許有輸出，且輸出為 1，其余節(jié)點輸出為 0。隨機(jī)確定輸出層神經(jīng)元連接權(quán)的初始值，會引起網(wǎng)絡(luò)達(dá)到收斂的學(xué)習(xí)次數(shù)過多，影響文本 聚類的速度。 ③網(wǎng)絡(luò)輸出層神經(jīng)元連接權(quán)的初始值影響聚類速度 。其權(quán)值得不到任何學(xué)習(xí)訓(xùn)練的機(jī)會，進(jìn)而影響文本 聚基于文本的聚類算法研究 20 類的粒度和識別的精度。但是由于文本數(shù)據(jù)高維性的特點，人們很難預(yù)先給出與原始數(shù)據(jù)空間中相一致的網(wǎng)絡(luò)輸出層拓?fù)浣Y(jié)構(gòu)。 (2)無導(dǎo)師學(xué)習(xí)現(xiàn)在發(fā)展的還不成熟，傳統(tǒng) SOM 網(wǎng)絡(luò)在文本聚類領(lǐng)域的應(yīng)用還存在著許多的不足 : ①網(wǎng)絡(luò)輸出層結(jié)點的初始結(jié)構(gòu)需要用戶預(yù)先給出 。它采用的鄰域?qū)W習(xí)策略能使數(shù)據(jù)從高維映射到低維時保持其拓?fù)浣Y(jié)構(gòu)不變，輸出層神經(jīng)元連接權(quán)矢量的空間分布能正確地反應(yīng)輸入模式的空間概率分布 。 ②因其采用“勝者全得”的學(xué)習(xí)策略，對噪音數(shù)據(jù)不敏感 。鄰域半徑也隨著學(xué)習(xí)代數(shù)的增加而遞減，最后只有獲勝結(jié)點在學(xué)習(xí) 步驟 6:返回步驟 2，直至算法收斂或達(dá)到最大迭代次數(shù)為為止。 步驟 5:參數(shù)調(diào)整。如果采用歐氏距離，計算連接權(quán)向量與輸入樣本之間的距離，選擇值最小的神經(jīng)元是獲勝神經(jīng)元。每一個區(qū)域代表同一類的樣本 . 基于文本的聚類算法研究 19 SOM 網(wǎng)絡(luò)聚類的基本流程 步驟 1:初始化連接權(quán)值 ? ，學(xué)習(xí)率 a。再擴(kuò)大一點，如果說一般的競爭學(xué)習(xí)網(wǎng)絡(luò)能夠訓(xùn)練識別出輸入矢量的點特征，那么 SOM網(wǎng)絡(luò)能夠表現(xiàn)輸入矢量在線上或平面上的分布特征。所以 SOM 網(wǎng)絡(luò)可以作為一種樣本特征檢測器，在樣本排序、樣本分類以及樣本檢測方面有廣泛的應(yīng)用。另外網(wǎng)絡(luò)要求的輸入神 經(jīng)元數(shù)很大，因而 SOM 網(wǎng)絡(luò)比其他人工神經(jīng)網(wǎng)絡(luò) (比如 BP 網(wǎng)絡(luò) )的規(guī)模要大。同時，如果高維空間比較相近的樣本，則在低維空間中的投影也比較接近，這樣就可以從中取出樣本空間中較多的信息。在這種情況下，不論輸入樣本是多少維的，都可投影到低維的數(shù)據(jù)空間的某個區(qū)域上。當(dāng)外界輸入不同的樣本到 SOM網(wǎng)絡(luò)中，一開始輸入樣本引起輸出興奮的位置各不相同，但通過網(wǎng)絡(luò)自組織后會形成一些輸出群，它們分別代表了輸入樣本的分布，反映了輸入樣本的圖形分布特征，所以 SOM 網(wǎng)絡(luò)常常被稱為特性圖。一個功能柱中的細(xì)胞完成同一種功能。 基于文本的聚類算法研究 18 第四章 SOM 聚類算法 SOM 聚類算法的網(wǎng)絡(luò)特性與基本流程 SOM 網(wǎng)絡(luò)的特性 神經(jīng)細(xì)胞模型中還存在著一種細(xì)胞聚類的功能柱。 基于文本的聚類算法研究 17 本章小結(jié) 本章詳細(xì)的闡述了 k均值聚類算法的算法思想及算法流程，并且詳細(xì)的提出了該算法的優(yōu)點以及存在的問題。 (8)采用遺傳算法或者免疫規(guī)劃方法 lv1 進(jìn)行混合聚類。算法思路如下 :先將全部樣本點看成是一個類簇的聚類問題，執(zhí)行 K均值聚類算法后得到的簇中心即為一個類簇的聚類問題的最佳解，然后選取與現(xiàn)有簇中心距離最遠(yuǎn)的點作為下一個類簇的初始簇中心，以此類推，確定出 K個類簇的初始聚類中心。這里所指的密度是指樣本點分布的密集情況，描述為，對于所有的樣本，、將每個樣本點假設(shè)為中心，設(shè)定一個半徑， 則落入這個半徑所在圓內(nèi)的所有樣本點的數(shù)目即為該樣本點的密度值，在計算完所有樣本點的密度值后，選取最大密度值的樣本點作為第一個初始聚類中心，然后將該樣本點及其半徑所在圓內(nèi)的數(shù)據(jù)點去除后，重新設(shè)定半徑選取下一個初始中心點，以此類推，直到得到 K 個初始中心點。分別選取 K組采樣數(shù)據(jù)分別執(zhí)行 K均值聚 類算法，然后選擇聚類結(jié)果最好的一組聚類中心作為算法的初始聚類中心點。 (3)將全部樣本以某種規(guī)則直觀的分成 k類，分別計算每一類的均值點作為 K均值聚類算法的初始聚類中心。 現(xiàn)有基于初始中心點改進(jìn)的 K均值聚類算法 目前的 K均值聚類算法中，對于初始聚類中心點的選取方法主要總結(jié)如下 : (1)隨機(jī)選取 k 個樣本作為初始聚類中心，由于是最早提出的這種選擇初始聚類中心點的方法，因此在后來的很多文獻(xiàn)中把這種隨機(jī)選擇初始聚類中心的方法稱為 FA(FyAPProach)。因此，在無監(jiān)督情況下，通過某種學(xué)習(xí)方法得到合適的 K值是很有必要的。 (2)K 值的確定問題 K均值聚類算法中， K值是由用戶預(yù)先確定的，而在實際應(yīng)用中，這個 K值很難直接確定，尤其是當(dāng)數(shù)據(jù)量較大時， K值的確定問題將成為 K 一均值聚類算法的一個很大的困難，因為在多數(shù)情況下人們并不能提前預(yù)知數(shù)據(jù)的分布情況及分類情況。然而，作為聚類誤差和準(zhǔn)則函數(shù)，通常存在一些局部最小點，目標(biāo)函數(shù)的搜索方向總是沿著聚類誤差和準(zhǔn)則函數(shù)的遞減方向進(jìn)行，當(dāng)初始簇中心不同時，搜索路徑也會不同，而目標(biāo)函數(shù)具有很多局部最優(yōu)解，這樣就存在著，當(dāng)初始簇中心選取不當(dāng)時，目標(biāo)函數(shù)容易陷入局部最優(yōu)解。 K均值聚類算法每次迭代過程都要調(diào)整簇中心及重新分配數(shù)據(jù)點，因此，當(dāng)數(shù)據(jù)量比較大的時候，這些迭代過程的計算量是相當(dāng)大的，算法的時間開銷也是巨大的，因此，由于需要大量的計算時間，因此 K均值聚類算法在待聚類數(shù)據(jù)量較大的時候并不適用。 K均值聚類算法采用距離函數(shù)作為度量數(shù)據(jù)點間相似度的方法，這里的距離函數(shù)多采用歐氏距離，同時采用聚類誤差平方和準(zhǔn)則函數(shù)作為聚類準(zhǔn)則函數(shù)，對于基于歐式距離的聚 類算法而言，其只能發(fā)現(xiàn)數(shù)據(jù)點分布較均勻的類球狀簇，對于聚類誤差平方和準(zhǔn)則函數(shù)而言，當(dāng)類簇大小差別較大，形狀較不規(guī)則時，容易造成對較大的類簇進(jìn)行分割來達(dá)到目標(biāo)函數(shù)取極小值的目的，因此容易造成錯誤的聚類結(jié)果。因此，當(dāng)數(shù)據(jù)集中存在遠(yuǎn)離所有數(shù)據(jù)點的噪音點時，聚類結(jié)果將很大程度上受這些噪音點的影響，導(dǎo)致聚類結(jié)果的錯誤，所以 K均值聚類算法對噪聲點和孤立點非常敏感。 (3)K均值聚類算法的聚類結(jié)果容易受噪音點數(shù)據(jù)的影響。這樣就導(dǎo)致了 K均值聚類算法對初始簇中心點的嚴(yán)重依賴性。 (2)K均值聚類算法嚴(yán)重依賴于初始簇中心點的選取。當(dāng)聚類數(shù)目不被人所知的情況下，人們往往需要結(jié)合其它算法來獲取聚類數(shù)目，即 K值。和大多數(shù)的聚類算法一樣， K均值聚類算法也有其自身的局限，主要局限如下 : (1)K均值聚類算法中的聚類數(shù)目即 K值需要由用戶預(yù)先給出。 K均值聚類算法采用迭代式的過程對樣本點進(jìn)行分配來尋求最終的聚類結(jié)果，其終止條件是所有樣本的位置不再變化，其迭代過程可以概括如下 :(l)分配樣本點，即對每個樣本點，將其分配到與其距離最近的簇中心所在的類簇中 。為解決這一問題，出現(xiàn)了各種基于全局最優(yōu)化思想的 K均值聚類方法，比如模擬退火算法、遺傳算法等。由于其算法思想基于文本的聚類算法研究 14 簡便，又容易實現(xiàn)，因此 K均值算法己成為一種目前最常用的聚 類算法之一。 從上面的算法思想及流程中可以看出， k個類簇的初始簇中心點的選取對聚類的最終結(jié)果至關(guān)重要，算法中，每一次迭代都把數(shù)據(jù)點劃分到與其距離最近的簇中心所在的類簇中去，然后重新計算簇中心，進(jìn)而反復(fù)迭代，直到每一個數(shù)據(jù)點都不再重新劃分為止。 [Step2][分配 xi]對每一個樣本 xi，找到離它最近的聚類中心，并將其分配到該類 : [Step3][修正簇中心 ]重新計算各簇中心 [Step4][計算偏差 ] [Step5][收斂判斷 ]如果 J值收斂，則 return(m1， m2， ? ? ， mk)，算法終止 。 K均值聚類算法在執(zhí)行過程中還可以加入聚類準(zhǔn)則函數(shù)來終止迭代過程，一般采用聚類誤差平方和準(zhǔn)則函數(shù)，即在上面算法流程中的 step4 中計算聚類誤差平方和 J，然后加入判斷，若兩次的 J 值沒有明顯變化，則說明 J值已經(jīng)收斂，結(jié)束算法，否則轉(zhuǎn)入 step2 繼續(xù)執(zhí)行。 輸出 : k個類簇 cj， j=1， 2， ?? ， k [stepl]令 I=1，隨機(jī)選取 k個數(shù)據(jù)點作為 k 個類簇的初始簇中心， mj(I) j=1，2，?， k。本算法的一個特點就是在每一次的迭代過程中都要對全體數(shù)據(jù)點的分配進(jìn)行調(diào)整，然后重新計算簇中心，進(jìn)入下一次的迭代過程，若在某一次迭代過程中，所有數(shù)據(jù)