【正文】 模型、相似度計算方法及聚類算法。為了更好地評價聚類結(jié)果 ，我們在下一章將詳細介紹已有的文本聚類評價方法，比較各自的優(yōu)缺點。該算法首先隨機選取 k個數(shù)據(jù)點作為 n個 簇的初始簇中心，集合中每個數(shù)據(jù)點被劃分到與其距離最近的簇中心所在的類簇之中，形成了 k 個聚類的初始分布。這里的聚類準則函數(shù)一般采用聚類誤差平方和準則函數(shù)。 K均值聚類算法的算法流程 原始的 K均 值聚類算法 : 輸入 :數(shù)據(jù)集 x={x1， x2， ?? xn}，聚類數(shù)目 k。 [step2]計算每一個數(shù)據(jù)點與這 k個簇中心的距離 d(xi， mj， (i)), i=1， 2，?n， j=1， 2，?， k， ,如果滿足 d(xi， mj(I))=min{d(xi， mj(I))， j=1， 2，?，k}則 xi? cj. [steP3]計算 k 個新的聚類 中心 基于文本的聚類算法研究 13 [step4]判斷 :若 mj(i+1)? mj(I)， j=1， 2，?， k，則 I=i+1，返回 step2:否則，算法結(jié)束。具體流程如下 : [Stepl][初始化 l隨機指定 k 個聚類中心 (ml， m2， ?? mk)。否則，轉(zhuǎn) Step2。 K均值算法的優(yōu)缺點分析 K均值算法是一種基于劃分的聚類算法，它通過不斷的迭代過程來進行聚類，當算法收斂到一個結(jié)束條件時就終止迭代過程，輸出聚類結(jié)果。然而 Kmeans 過分依賴于初始中心點的選取，且容易受噪音點的影響。然而這些技術(shù)并沒有得到廣泛認可，在許多實際應用中還是反復利用 K均值聚類算法來解決問題。(2)重新計算簇中心，對于每一個重新分配 后的類簇，重新計算其簇中心。從 K均值聚類算法的算法流程中可以看出， K 值作為一個需要預先確定的參數(shù)，在已知的前提下才能執(zhí)行 K均值聚類算法，而在實際應用中，需要聚類的數(shù)據(jù)究竟要分成多少個類別，往往不是被用戶所知的。往往獲取 K值的代價要比 K均值聚類算法的代價大得多，因此 K 值的不確定性是 K均值聚類算 法的一個很大的不足之處。 K均值聚類算法隨機的選取 K個初始簇中心點，并針對這 K個簇中心點進行迭代運算，即重新分配數(shù)據(jù)點和重新計算簇中心的運算，直到所有的數(shù)據(jù)點位置不再變化或聚類誤差準則函數(shù)不再變化。初始簇中心點選取不當很容易造成聚類結(jié)果陷入局部最優(yōu)解甚至或?qū)е洛e誤的聚類結(jié)果。在 K均值聚類算法中，每次對于簇中心的重新計算，都是通過對每一個類簇 中所有數(shù)據(jù)點求均值，這樣，當數(shù)據(jù)集中存在噪音點數(shù)據(jù)時，均值點的計算將導致聚類中心 (即簇中心偏離數(shù)據(jù)真正密集的區(qū)域，而趨向噪音點數(shù)據(jù)歹這樣導致聚類結(jié)果的不準確。 基于文本的聚類算法研究 15 (4)K均值聚類算法無法發(fā)現(xiàn)任意形狀的簇。 (5)K均值聚類算法不適用于大數(shù)據(jù)量的聚類問題。 現(xiàn)有的對于 K均值聚類算法的改進 目前，對于 K均值聚類算法的改進主要集中在以下兩個方面 : (1)初始聚類中心的選擇 K均值聚類算法是一個迭代的求解最優(yōu)解的問題，這里的最優(yōu)解一般指的是目標函數(shù) (即聚類誤差和準則函數(shù) )的最優(yōu)解，是一個優(yōu)化問題。而 K均值聚類算法采取隨機選取初始簇 中心點，這樣，初始中心點的不同或數(shù)據(jù)輸入順序的不同都有可能導致聚類結(jié)果的不穩(wěn)定性，且無法得到全局最優(yōu)解而陷入局部最優(yōu)解。而 K均值聚類算法的聚類結(jié)果受 K值的影響， K 值不同時，聚類結(jié)果往往也隨著不同，很多方法是通過試探 K值來達到獲取 K值的目的，而在數(shù)據(jù)量較大時，這種方法并不 行得通，需要大量的時間代價，因此，為了得到確定的聚類結(jié)果， K 值的確定顯得尤為重要。 基于 K均值聚類算法的改進，國內(nèi)外的專家學者做了大量的研究工作，主要 基于文本的聚類算法研究 16 總結(jié)如下。 (2)按最大最小距離聚類法中尋找聚類中心的方法來確定 K均值聚類算法 中的初始聚類中心。 (4)采用基于數(shù)據(jù)采樣的方法。 (5)通過“密度法”選擇代表點作為初始聚類中心。 (6)聚類問題解出 k 類問題的中心。 (7)進行多次初始值的選擇、聚類、找出一組最優(yōu)的聚類結(jié)果。除了以上列出的初始中心點的選取方法以外，還有很多對 K均值聚類算法的初始中心點的改進算法，在這里由于篇幅的關(guān)系我們沒有一一列出。同時也 對 kmeans 算法的改進有兩種方法一是：現(xiàn)有的對于 K均值聚類算法的改進，二是：現(xiàn)有基于初始中心點改進的 K均值聚類算法。它是由多個細胞聚合而成的，在接受外界刺激后，它們會自動形成。生物細胞中的這種現(xiàn)象在 SOM網(wǎng)絡模型中有所反應。 SOM 網(wǎng)絡是輸入樣本通過競爭學習后，功能相同的輸入靠得比較近，不同的分得比較開，以此將一些無規(guī)則的輸入自動排開，在連接權(quán)的調(diào)整過程中，使權(quán)的分布與輸入域可逐步縮小，使區(qū)域的劃分越來越明顯。這種形式也成為數(shù)據(jù)壓縮。遺憾的是，網(wǎng)絡在高維映射到低維時會發(fā)生畸變，而且壓縮比越大，畸變越大 。樣本的概率密度分布相似。一般可以這樣說， SOM網(wǎng)絡的權(quán)矢量收斂到所代表的輸入矢量的平均值，它反映了輸入數(shù)據(jù)的統(tǒng)計特性。當隨機樣本輸入到 SOM網(wǎng)絡時，如果樣本足夠多，那么在權(quán)值分布上可近似于輸入隨機樣本的概率密度分布，在輸出神 經(jīng)元上也反映了這種分布，即概率大的樣本集中在輸出空間的某一個區(qū)域，如果輸入的樣本有幾種分布類型，則它們各自會根據(jù)其概率分布集中到輸出空間的各個不同的區(qū)域。鄰域半徑 Nbo. 步驟 2:取樣對所有輸入樣本執(zhí)行步驟 3 一步驟 6. 步驟 3:確定獲勝神經(jīng)元。 步驟 4:更新獲勝神經(jīng)元及其鄰域 內(nèi)所有神經(jīng)元的連接權(quán)值，而鄰域外的神經(jīng)元的連接權(quán)值保持不變。調(diào)整學習率和鄰域半徑，為了保證算法的收斂，學習率的取值一般在 O到 1之間，且隨著學習代數(shù)的增加而遞減 。 SOM 網(wǎng)絡聚類的優(yōu)點及存在的問題 (l) SOM神經(jīng)網(wǎng)絡在聚類方面有如下優(yōu)點 : ①無須用戶指定聚類數(shù)目，網(wǎng)絡通過學習過程自適應地確定聚類數(shù)目 。 ③ 具有可視化的優(yōu)點 。因此， SOM 網(wǎng)絡不但能學習到輸入模式的類別特征，而且能夠?qū)W習到輸入模式在原始空間中的拓撲結(jié)構(gòu)特征和概率分布，從而具備可視化的優(yōu)點。輸出層結(jié)點的初始拓撲結(jié)構(gòu)與輸入模式在在原始數(shù)據(jù)空間中的拓撲結(jié)構(gòu)一致時，網(wǎng)絡才會達到好的學習效果。 ②網(wǎng)絡訓練時，有些輸出層神經(jīng)元的連接權(quán)值與輸入模式相差很大，始終不能獲勝，成為“死神經(jīng)元” 。相反有些神經(jīng)元因為獲勝次數(shù)過多，出現(xiàn)神經(jīng)元過度利用的問題，也會影響網(wǎng)絡的學習效果。因為文本數(shù)據(jù)的高維性，網(wǎng)絡學習一次花費時間較多。 改進的 SOM 聚類方法 已有的學習策略改進 就具體的學習策略來說，自組織特征映射神經(jīng)網(wǎng)絡采用的是“勝者全得”的競爭學習算法，就是在競爭學習時網(wǎng)絡的各輸出神經(jīng)元相互競爭，最后只有一個最強神經(jīng)元獲勝 。這種學習策略存在如下兩個問題 : (l)網(wǎng)絡訓練時，有些輸出層神經(jīng)元的連接權(quán)值與輸入模式相差很大，始終不能獲 勝，成為“死神經(jīng)元”，其權(quán)值得不到任何學習訓練的機會 。近 年來，有些學者針對神經(jīng)元欠利用和過度利用的問題，提出了許多改進的學習策略，代表性的有 SOMCV、 SOMC、 ESOM、 TASOM、 DSOM。 (2)SOMC 即帶“良心”的競爭學習 SOM，它的基本思想是給每個競爭層結(jié)點設置一個闡值，每次使競爭獲勝的神經(jīng)元的閩值增加，使經(jīng)常獲勝的神經(jīng)元獲勝的機會減小。 (4)TASOM 該種 學習策略中，每個神經(jīng)元都有自己的學習率和鄰域函數(shù)，并且能 根據(jù)學習時間自動地調(diào)整學習率和鄰域的大小。并把每一個亞興奮神經(jīng)元作為 NO的擴散源。 以上算法對神經(jīng)元的獲勝策略進行了改進，在一定程度上解決了神經(jīng)元欠利用和過度利用 的問題，可以得到較好質(zhì)量的聚類結(jié)果。本文借鑒學習矢量量化中等失真度的原則，針對文本聚類問題，把文本聚類追求的目標一平均類內(nèi)離差最小即平均類內(nèi)相似度最大考慮進去，提出了一種改進的學習策略，該算法把等離差理論引入神經(jīng)網(wǎng)絡的學習過程中，通過調(diào)整類內(nèi)離差來指導神經(jīng)網(wǎng)絡的學習，以使得聚類結(jié)果的平均類內(nèi)離差最小 :不僅解決了神經(jīng)元欠利用和過度利用的問題，而且大大提高了文本聚類的結(jié)果質(zhì)量。來表示。通常稱使總類內(nèi)離差最小的聚類器為最優(yōu)聚類器。 (3)改進算法的基本流程 根據(jù)等類內(nèi)離差準則，希望所有分割區(qū)域的類內(nèi)離差相等，即要求所有的D(S、 )(i， 2，? K)相等。這樣不僅解決了神經(jīng)元欠利用問題，而且使各連接權(quán)值在表征輸入空間數(shù)據(jù)分布時得到了更有效的利用，使得量化的總類內(nèi)離差接近最小，從而得到最優(yōu)的聚類結(jié)果。鄰 域半徑 Nb。 )=1 步驟 2: 取樣。如果采用歐氏距離，按連接權(quán)向量與輸入樣本之間的距離值最小的神經(jīng)元是獲勝神經(jīng)元。 步驟 5: 參數(shù)調(diào)整。鄰域半徑也隨著學習代數(shù)的增加而遞減，最后只有獲勝結(jié)點在學習。若輸出層神經(jīng)元結(jié)點對應的輸入空間區(qū)域非空，則更新類內(nèi)離差。 初始化連接權(quán)值 初始權(quán)的設置，對于網(wǎng)絡的收斂狀況和收斂速度都是有影響的。人工神經(jīng)網(wǎng)絡學習，如同其它優(yōu)化技術(shù)一樣，初始權(quán)設置的好壞，也會影響到收斂的程度。 已有的初始化連接權(quán)的方法 網(wǎng)絡的訓練主要是通過對連接權(quán)的調(diào)整實現(xiàn)的，當連接權(quán)不再變化或者變化很少時，網(wǎng)絡訓練就完成了，達到了一個收斂的狀態(tài)。由于連接權(quán)矢量初始狀態(tài)最理想的分布是其方向與輸入模式的方向一致，因此在連接權(quán)初始化時，應該盡可能地使其初始狀態(tài)與輸入模式處于一種互相容易接近的狀態(tài)。一般情況下，輸入學習模式只處于整個模式空間的有限位置，如果對 連接權(quán)值隨機初始化，則在權(quán)值矢量會廣泛地分布于各個隨機方向上，一定會有大量的連接基于文本的聚類算法研究 23 權(quán)矢量與輸入模式方向差異很大，甚至方向相反。所以在實際應用中，這種初始化方法會出現(xiàn)網(wǎng)絡學習時間過長，甚至無法收斂的現(xiàn)象。 (3)從輸入空間中任意選取 K 個矢量對權(quán)值矢量進行初始化， K是輸出層神經(jīng)元結(jié)點的個數(shù)。 (4)在文本聚類領域，還存在一種特殊的初始化權(quán)值的方法，即根據(jù)專家經(jīng)驗，按照某一個單詞屬于某個類別的概率確定。進行特征抽取以后，一個單詞可能映射到輸入空間的多個維上 ，使這種確定初始連接權(quán)值的方法變得非常困難。但在對連接權(quán)進行初始化時，可以試圖使連接權(quán)的初始狀態(tài)與各個模式類別的方向相似。選出的這 K個數(shù)據(jù)點應該屬于不同的模式 類別為好，且這 K個數(shù)據(jù)點應盡量靠近該類別的中心，這是我們初始化連接權(quán)時要達到的目標。 新的確定初始權(quán)值的方法 用 SOM 進行聚類時，本文通過如下方法從待聚類數(shù)據(jù)中選出 K個有代表性的點， (K 是輸出層神經(jīng)元的節(jié)點數(shù)目 ): 基于文本的聚類算法研究 24 步驟 1:采用平均鏈接 (UMPGA)對每個文檔的前 Nb個近鄰 (包括文檔本身 )行聚類，這樣每個文檔的鄰近區(qū)域 形成了一棵聚類樹 (如圖 所示 )，算法從這棵類層次樹上選取 score==平均相似度、文檔數(shù)量， score 最高的結(jié)點 (實際上是一個密的文檔集合 )，被加入到一個鏈表中。 圖 1 密集區(qū)域探測 步驟 2:按照這些密集 小區(qū)域的得分 (Score)為這個鏈表進行排序。中心向量是取屬于這個密集小區(qū)域的文檔向量各個維權(quán)重的平均值。至此，獲得了 K個中心。 鄰域半徑 Nb。對所有輸入樣本執(zhí)行步驟 7一步驟 10。如果采用歐氏距離，按本文計算連接權(quán)向量與輸入樣本之間的距離，選擇使本文上章上節(jié)中公式 ()值最小的神經(jīng)元是獲勝神經(jīng)元。按本文更新獲勝神經(jīng)元及其鄰域內(nèi)所有神經(jīng)元的連接權(quán)值，而鄰域外的神經(jīng)元的連接權(quán)值保持不變。調(diào)整學習率和鄰域半徑，為了保證算法的收斂，學習率的取值一般在 O到 1之間，且隨著學習代數(shù)的增加而遞減 。 步驟 10:返回步驟 6，直至算法收斂或達到最大迭代次數(shù)為為止。 同時也針對了 SOM 算法的改進具體步驟如下：（ 1）已有的學習策略改進（ 2）等離差理論在神經(jīng)元獲勝策略中的應用改進 .基于文本的聚類算法研究 26 參 考 文 獻 [1]Dhillon documents and words using bipartite spectral graph of the 7thACM Conference on Knowledge Discovery and Data York,Acm : [2]Dhillon, Clustering in High Dimensional Text Data. papers/ [3 [4]高茂庭 .文本聚類分析若干問題研究 .天津大學博士學 位論文 .2020:1315 [5]于智航 .改進的密度聚類算法研究 .大連理工大學碩士學位論文 .2020: [6 [7]姚天順，朱靖波等 .自然語言理解 —— 一種讓機器懂得人類語言的研究 .[M]第 2版 .清華大學出版社， 2020： [8]張培穎 .運用有向圖進行中文分詞研究 . [M]計算機工程與應用 .2020， 45（ 22）： [9]張利，張立勇，張曉淼 .基于改進 BP網(wǎng)絡的中文歧義字段分詞方法研究 . [M]大連理工大學學報 .2020， 47（ 1）： [10]楊曉恝，蔣維，郝文寧 .基于本體和句法分析的領域分詞的實現(xiàn) . [M]計算機工程 .2020， 34（ 23）： [11]丁振國，張卓，黎靖 .基于 Hash結(jié)構(gòu)的逆向最大匹配分詞算法的改進 . [