【導讀】聚類作為一種知識發(fā)現(xiàn)的重要方法，它廣泛地與中文信息處理技術相結合，應用于網絡信息處理中以滿足用戶快捷地從互聯(lián)網獲得自己需要的信息資源。其目的是要使同一類別的文本間的相。似度盡可能大，而不同類別的文本間的相似度盡可能的小。整個聚類過程無需指。導，事先對數據結構未知，是一種典型的無監(jiān)督分類。型，相似度計算及常見聚類算法。本文主要研究的聚類主要方法是k-均值和SOM. 算法，介紹了兩種算法的基本思想和實現(xiàn)步驟，并分析兩種算法的聚類效果。時介紹了兩種算法的改進算法。師的指導下進行的研究工作及取得的成果。而使用過的材料。究所取得的研究成果。不包含任何其他個人或集體已經發(fā)表或撰寫的成果作品。究做出重要貢獻的個人和集體，均已在文中以明確方式標明。全意識到本聲明的法律后果由本人承擔。同意學校保留并向國家有關部門或機構送交論文的復印件和電子版，允許論文被查閱和借閱。

　　

【正文】 數目，網絡通過學習過程自適應地確定聚類數目 。 ②因其采用“勝者全得”的學習策略，對噪音數據不敏感 。 ③ 具有可視化的優(yōu)點 。它采用的鄰域學習策略能使數據從高維映射到低維時保持其拓撲結構不變，輸出層神經元連接權矢量的空間分布能正確地反應輸入模式的空間概率分布 。因此， SOM 網絡不但能學習到輸入模式的類別特征，而且能夠學習到輸入模式在原始空間中的拓撲結構特征和概率分布，從而具備可視化的優(yōu)點。 (2)無導師學習現(xiàn)在發(fā)展的還不成熟，傳統(tǒng) SOM 網絡在文本聚類領域的應用還存在著許多的不足 : ①網絡輸出層結點的初始結構需要用戶預先給出 。輸出層結點的初始拓撲結構與輸入模式在在原始數據空間中的拓撲結構一致時，網絡才會達到好的學習效果。但是由于文本數據高維性的特點，人們很難預先給出與原始數據空間中相一致的網絡輸出層拓撲結構。 ②網絡訓練時，有些輸出層神經元的連接權值與輸入模式相差很大，始終不能獲勝，成為“死神經元” 。其權值得不到任何學習訓練的機會，進而影響文本 聚基于文本的聚類算法研究 20 類的粒度和識別的精度。相反有些神經元因為獲勝次數過多，出現(xiàn)神經元過度利用的問題，也會影響網絡的學習效果。 ③網絡輸出層神經元連接權的初始值影響聚類速度 。因為文本數據的高維性，網絡學習一次花費時間較多。隨機確定輸出層神經元連接權的初始值，會引起網絡達到收斂的學習次數過多，影響文本 聚類的速度。 改進的 SOM 聚類方法 已有的學習策略改進 就具體的學習策略來說，自組織特征映射神經網絡采用的是“勝者全得”的競爭學習算法，就是在競爭學習時網絡的各輸出神經元相互競爭，最后只有一個最強神經元獲勝 。只有獲勝節(jié)點才允許有輸出，且輸出為 1，其余節(jié)點輸出為 0。這種學習策略存在如下兩個問題 : (l)網絡訓練時，有些輸出層神經元的連接權值與輸入模式相差很大，始終不能獲 勝，成為“死神經元”，其權值得不到任何學習訓練的機會 。 (2)相反有些神經元因為獲勝次數過多，出現(xiàn)神經元過度利用的問題。近 年來，有些學者針對神經元欠利用和過度利用的問題，提出了許多改進的學習策略，代表性的有 SOMCV、 SOMC、 ESOM、 TASOM、 DSOM。 (1)SOMCV 該種方法把 SOM 網絡的權值都初始化為 l/m(m 是輸入向量的維 數 )，每個輸入向量 xj要經過如下修正后再輸入網絡。 (2)SOMC 即帶“良心”的競爭學習 SOM，它的基本思想是給每個競爭層結點設置一個闡值，每次使競爭獲勝的神經元的閩值增加，使經常獲勝的神經元獲勝的機會減小。 (3)ESOM 把更新獲勝結點 Z及其領域結點的權值修改。 (4)TASOM 該種 學習策略中，每個神經元都有自己的學習率和鄰域函數，并且能 根據學習時間自動地調整學習率和鄰域的大小。 (5)DSOM 該種學習策略是把內源性一氧化氮 (NO)的四維動態(tài)擴散特性和其在長時間學習過程中的增強作用應用到 SOM 中，輸入向量 X 輸入網絡后，以某種規(guī)基于文本的聚類算法研究 21 則 (評價函數 )確定競爭層中一組獲勝神經元，稱為亞興奮神經元簇。并把每一個亞興奮神經元作為 NO的擴散源。然后計算各亞興奮神經元所處位置的 NO 濃度，則 NO 濃度最高的神經元為最終獲勝單元。 以上算法對神經元的獲勝策略進行了改進，在一定程度上解決了神經元欠利用和過度利用 的問題，可以得到較好質量的聚類結果。但是聚類沒有以類內離差最小一平均類內相似度最大為基礎，很難保證可以得到使平均類內離差最小一平均類內相似度最大的聚類結果。本文借鑒學習矢量量化中等失真度的原則，針對文本聚類問題，把文本聚類追求的目標一平均類內離差最小即平均類內相似度最大考慮進去，提出了一種改進的學習策略，該算法把等離差理論引入神經網絡的學習過程中，通過調整類內離差來指導神經網絡的學習，以使得聚類結果的平均類內離差最小 :不僅解決了神經元欠利用和過度利用的問題，而且大大提高了文本聚類的結果質量。 等離 差理論在神經元獲勝策略中的應用改進 (l)文本聚類的目標函數基于劃分的聚類器的基本思想是 :一個 K階的聚類器把輸入空間分成 K個小空間 S1， S2， ? ， Sk，每個小空間 S代表一個類別，每個小空間 S 內的聚類中心用 z。來表示。 (2)等類內離差原則聚類問題的實質就是求出適當 s和 z，使總類內離差 D(s)最小。通常稱使總類內離差最小的聚類器為最優(yōu)聚類器。最優(yōu)聚類器的必要條件是指最近鄰條件和質心條件。 (3)改進算法的基本流程 根據等類內離差準則，希望所有分割區(qū)域的類內離差相等，即要求所有的D(S、 )(i， 2，? K)相等。 所以，本文把等類內離差準則引入到 SOM算法的學習策略中，在爭學習的過程中，將決定那個神經元獲勝的策略加以修改，定義新的距離測度為 :d(x1， x 2)=d(x， z)D(S)顯然當 D(s)增加時， d(x， Z)隨之增加，這就減少了神經元 ，最終結果將導致所有區(qū)域的類內離差趨于相等。這樣不僅解決了神經元欠利用問題，而且使各連接權值在表征輸入空間數據分布時得到了更有效的利用，使得量化的總類內離差接近最小，從而得到最優(yōu)的聚類結果。 EDSOM 算法的基本步驟可描述如下 : 基于文本的聚類算法研究 22 步驟 1：初始化連接權值 w，學習率。鄰 域半徑 Nb。，對于輸出層每個神經元結點的類內離差初始化為 D(s。 )=1 步驟 2: 取樣。對所有輸入樣本執(zhí)行步驟 3一步驟 6 步驟 3: 確定獲勝神經元。如果采用歐氏距離，按連接權向量與輸入樣本之間的距離值最小的神經元是獲勝神經元。 步驟 4: 更新按更新獲勝神經元及其鄰域內所有神經元的連接權值，而鄰域外的神經元的連接權值保持不變。 步驟 5: 參數調整。調整學習率和鄰域半徑，為了保證算法的收斂，學習率的取值一般在 0到 1之間，且隨著學習代數的增加而遞減 。鄰域半徑也隨著學習代數的增加而遞減，最后只有獲勝結點在學習。 步 驟 6: 更新每個輸出層神經元結點的類內離差。若輸出層神經元結點對應的輸入空間區(qū)域非空，則更新類內離差。 步驟 7: 返回步驟 2，直至算法收斂或達到最大迭代次數為為止。 初始化連接權值 初始權的設置，對于網絡的收斂狀況和收斂速度都是有影響的。不同的初始權，在其它條件相同的情況下，可能達到不同的輸出方差水平。人工神經網絡學習，如同其它優(yōu)化技術一樣，初始權設置的好壞，也會影響到收斂的程度。一般說來，初始權值設置不當，有可能造成在某一局部極小值周圍長期徘徊不出，收斂所需的時間延長，甚至收斂到局部最優(yōu)或不收斂 。 已有的初始化連接權的方法 網絡的訓練主要是通過對連接權的調整實現(xiàn)的，當連接權不再變化或者變化很少時，網絡訓練就完成了，達到了一個收斂的狀態(tài)。因此連接權的初始狀態(tài)對網絡的訓練過程影響很大。由于連接權矢量初始狀態(tài)最理想的分布是其方向與輸入模式的方向一致，因此在連接權初始化時，應該盡可能地使其初始狀態(tài)與輸入模式處于一種互相容易接近的狀態(tài)。目前有下面幾種常用的初始化方法 : (1)隨機初始化權值 :一般學習規(guī)則是將網絡的連接權賦予區(qū)間內的隨機值。一般情況下，輸入學習模式只處于整個模式空間的有限位置，如果對 連接權值隨機初始化，則在權值矢量會廣泛地分布于各個隨機方向上，一定會有大量的連接基于文本的聚類算法研究 23 權矢量與輸入模式方向差異很大，甚至方向相反。這樣在網絡訓練時，尋找輸入模式的最佳映射就非常困難，為達到網絡收練，需經過很多次的反復學習。所以在實際應用中，這種初始化方法會出現(xiàn)網絡學習時間過長，甚至無法收斂的現(xiàn)象。 (2)所有連接權矢量賦予相同權值 :將所有的連接權矢量賦予相同的初始值，這樣可以減少輸入模式在最初階段對連接權矢量的挑選余地，增加每一個權矢量被選中的機會，盡可能快地校正連接權矢量和輸入模式之間的方向偏差，加快收斂的速度 。 (3)從輸入空間中任意選取 K 個矢量對權值矢量進行初始化， K是輸出層神經元結點的個數。這種方法相對于隨機初始化連接權值來說，網絡訓練時，尋找輸入模式的最佳映射相對容易，但因為隨機選取的 K個矢量不一定與模式的類別方向一致，達到網絡收斂的學習次數波動性較大。 (4)在文本聚類領域，還存在一種特殊的初始化權值的方法，即根據專家經驗，按照某一個單詞屬于某個類別的概率確定。由于文本數據的高維性，在進行聚類之前，一般要進行特征選擇和特征抽取，以降低文本數據的維度。進行特征抽取以后，一個單詞可能映射到輸入空間的多個維上 ，使這種確定初始連接權值的方法變得非常困難。連接權值的理想分布是其方向與各個模式類別的方向一致，但在初始化時想做到這一點是不現(xiàn)實的，因為這是網絡訓練所要達到的目的，在網絡收斂時，連接權的方向與各個模式類別的方向一致。但在對連接權進行初始化時，可以試圖使連接權的初始狀態(tài)與各個模式類別的方向相似。于是，用 SOM 對數據進行聚類時，對連接權值進行初始化時，可以試圖從輸入模式空間中找出 K個有代表性的點，它們能代表各個模式類別的中心，或者與各個模式類別的方向相似，最起碼相差不能太大。選出的這 K個數據點應該屬于不同的模式 類別為好，且這 K個數據點應盡量靠近該類別的中心，這是我們初始化連接權時要達到的目標。理論表明，文檔數據點密集區(qū)可能包含模式類別的中心或離模式類別的中心較近，本文提出一種用層次聚類法探測數據密集區(qū)，用探測到的 K個數據密集區(qū)中心點隨機初始化權值，以期提高網絡收斂的速度。 新的確定初始權值的方法 用 SOM 進行聚類時，本文通過如下方法從待聚類數據中選出 K個有代表性的點， (K 是輸出層神經元的節(jié)點數目 ): 基于文本的聚類算法研究 24 步驟 1:采用平均鏈接 (UMPGA)對每個文檔的前 Nb個近鄰 (包括文檔本身 )行聚類，這樣每個文檔的鄰近區(qū)域 形成了一棵聚類樹 (如圖 所示 )，算法從這棵類層次樹上選取 score==平均相似度、文檔數量， score 最高的結點 (實際上是一個密的文檔集合 )，被加入到一個鏈表中。圖中結點 e依據 score 將被選中，它包括了 {3， 4， 5， 6， 7， 8}，這個密集的文檔集合中有可能包括模式類別的中心。 圖 1 密集區(qū)域探測 步驟 2:按照這些密集 小區(qū)域的得分 (Score)為這個鏈表進行排序。 步驟 3:為這些密集小區(qū)域生成中心點向量。中心向量是取屬于這個密集小區(qū)域的文檔向量各個維權重的平均值。 步驟 4:在每次聚類時，算法接受用戶輸入的輸出層神經元結點數目參數 K，對于這些中心點，找到一個合適的相似度閩值，使得在這個相似度闡值下，有 K個中心點它們之間的相似度小于這個閩值。至此，獲得了 K個中心。 步驟 5:用這 K個數據點對 SOM網絡的權值進行初始化，同時初始化學習率“。， 鄰域半徑 Nb。 步驟 6:取樣。對所有輸入樣本執(zhí)行步驟 7一步驟 10。 步驟 7:確定獲勝 神經元。如果采用歐氏距離，按本文計算連接權向量與輸入樣本之間的距離，選擇使本文上章上節(jié)中公式 ()值最小的神經元是獲勝神經元。 步驟 8:更新。按本文更新獲勝神經元及其鄰域內所有神經元的連接權值，而鄰域外的神經元的連接權值保持不變。 基于文本的聚類算法研究 25 步驟 9:參數調整。調整學習率和鄰域半徑，為了保證算法的收斂，學習率的取值一般在 O到 1之間，且隨著學習代數的增加而遞減 。鄰域半徑也隨著學習代數的增加而遞減，最后只有獲勝結點在學習。 步驟 10:返回步驟 6，直至算法收斂或達到最大迭代次數為為止。 本章小結 本章 詳細的介紹了 SOM 聚類算法的網絡特性和具體的步驟，以及 SOM 算法的優(yōu)點以及存在的問題。 同時也針對了 SOM 算法的改進具體步驟如下：（ 1）已有的學習策略改進（ 2）等離差理論在神經元獲勝策略中的應用改進 .基于文本的聚類算法研究 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網絡的中文歧義字段分詞方法研究 . [M]大連理工大學學報 .2020， 47（ 1）： [10]楊曉恝，蔣維，郝文寧 .基于本體和句法分析的領域分詞的實現(xiàn) . [M]計算機工程 .2020， 34（ 23）： [11]丁振國，張卓，黎靖 .基于 Hash結構的逆向最大匹配分詞算法的改進 . [M]