畢業(yè)論文---基于文本的聚類算法

1、<p><b>　　摘 要</b></p><p>　　聚類作為一種知識發(fā)現(xiàn)的重要方法，它廣泛地與中文信息處理技術相結合，應用于網絡信息處理中以滿足用戶快捷地從互聯(lián)網獲得自己需要的信息資源。文本聚類是聚類問題在文本挖掘中的有效應用，它根據(jù)文本數(shù)據(jù)的不同特征，按照文本間的相似性，將其分為不同的文本簇。其目的是要使同一類別的文本間的相似度盡可能大，而不同類別的文本間的相似度盡可能

2、的小。整個聚類過程無需指導，事先對數(shù)據(jù)結構未知，是一種典型的無監(jiān)督分類。</p><p>　　本文首先介紹了文本聚類的相關的技術，包括文本聚類的過程，文本表示模型，相似度計算及常見聚類算法。本文主要研究的聚類主要方法是k-均值和SOM算法，介紹了兩種算法的基本思想和實現(xiàn)步驟，并分析兩種算法的聚類效果。同時介紹了兩種算法的改進算法。</p><p>　　關鍵詞：文本聚類 聚類方法

3、 K-MEAN SOM </p><p><b>　　Abstract</b></p><p>　　Clustering as an important knowledge discovery method, which extensively with Chinese information processing technology, used in netw

4、ork information processing to meet the users to quickly access from the Internet, the information resources they need. Text clustering is a clustering problem in the effective application of text mining, which according

5、to the different characteristics of text data, according to the similarity between the text, the text will be divided into different clusters. The </p><p>　　Key words：Text clustering clustering method k-m

6、ean som</p><p><b>　　目 錄</b></p><p><b>　　摘 要IV</b></p><p>　　AbstractV</p><p><b>　　目 錄VI</b></p><p>　　第一章 緒

7、 論1</p><p>　　1.1 課題研究的背景1</p><p>　　1.2課題研究的意義2</p><p>　　第二章 文本聚類效果影響因素3</p><p>　　2.1文本聚類過程3</p><p>　　2.2文本表示模型4</p><p>　　2.2.1布爾模型5<

8、;/p><p>　　2.2.2向量空間模型5</p><p>　　2.3 文本相似度計算6</p><p>　　2.4文本聚類算法8</p><p>　　2.5本章小結11</p><p>　　第三章 k-均值聚類算法12</p><p>　　3.1 K-均值聚類算法的思想12</

9、p><p>　　3.1.1 K-均值聚類算法的基本思想12</p><p>　　3.1.2 K-均值聚類算法的算法流程12</p><p>　　3.1.3 K-均值算法的優(yōu)缺點分析13</p><p>　　3.1.4現(xiàn)有的對于K-均值聚類算法的改進15</p><p>　　3.1.5現(xiàn)有基于初始中心點改進的K-均值

10、聚類算法16</p><p>　　3.2 本章小結17</p><p>　　第四章 SOM聚類算法18</p><p>　　4.1 SOM聚類算法的網絡特性與基本流程18</p><p>　　4.1.1 SOM網絡的特性18</p><p>　　4.1.2 SOM網絡聚類的基本流程19</p>

11、<p>　　4.1.3 SOM網絡聚類的優(yōu)點及存在的問題19</p><p>　　4.2改進的SOM聚類方法20</p><p>　　4.2.1已有的學習策略改進20</p><p>　　4.2.2等離差理論在神經元獲勝策略中的應用改進21</p><p>　　4.2.3初始化連接權值22</p><

12、p>　　4.2.4已有的初始化連接權的方法22</p><p>　　4.2.5新的確定初始權值的方法23</p><p>　　4.3本章小結25</p><p>　　參 考 文 獻26</p><p><b>　　致 謝28</b></p><p><b>　　第一

13、章 緒 論</b></p><p>　　1.1 課題研究的背景</p><p>　　隨著Internet的迅猛發(fā)展，信息的爆炸式增加，信息超載問題變的越來越嚴重，信息的更新率也越來越高，用戶在信息海洋里查找信息就像大海撈針一樣。搜索引擎服務應運而生，在一定程度上滿足了用戶查找信息的需要。然而Internet的深入發(fā)展和搜索引擎日趨龐大，進一步凸現(xiàn)出海量信息和人們獲取所需信息能

14、力的矛盾。那么，如何從中獲取特定內容的信息和知識成為擺在人們面前的一道難題。面對互聯(lián)網時代龐雜無序的海量信息，智能高效地處理和深層次綜合利用信息離不開文本挖掘技術，國際上多個國家都抓緊投入文本挖掘技術的研究，以期能對“堆積如山”的信息進行有效的過濾，開發(fā)和利用，提取發(fā)現(xiàn)具有指導意義的知識。</p><p>　　文本挖掘是指從大量文本數(shù)據(jù)中抽取出事先未知的，可理解的，最終可用的信息或知識的過程，它涉及Web，計算機

15、語言，數(shù)據(jù)挖掘，信息檢索等多個領域，較大程度地解決了信息雜亂的現(xiàn)象，方便用戶準確地定位所需的信息和信息分流。文本挖掘可以對大量文檔集合的內容進行總結，結構分析，分類，聚類，關聯(lián)分析，分布分析以及利用文檔進行趨勢預測等，目前已成為一項具有較大實用價值的關鍵技術，是組織和管理數(shù)據(jù)和知識的有力手段。</p><p>　　聚類作為一種只是發(fā)現(xiàn)的重要方法，是數(shù)據(jù)挖掘中一項重要的研究課題，它廣泛地與中文信息處理技術相結合，應

16、用于網絡信息處理中以滿足用戶快捷地從互聯(lián)網獲得自己需要的信息資源，文本聚類則是聚類問題在文本挖掘中的有效應用，是文本挖掘的重要內容之一。文本聚類是根據(jù)文本數(shù)據(jù)的不同特征，按照事物間的相似性，將其劃分為不同數(shù)據(jù)類的過程。其目的是使同一類別的文本間相似度盡可能大，而不同類別的文本間的相似度盡可能的小。在這一過程中無需指導，是一種典型的無需督分類，從而打破了在許多實際應用中由于缺少形成模式類別過程的知識，或者模式類別的形成非常困難時的挖掘局限

17、性。</p><p>　　隨著人們對聚類問題更加深入地了解和重視，國內外大量學者不斷投身到該項目研究，聚類主要工作集中在尋找針對大型數(shù)據(jù)庫的聚類方法和世界的聚類分析方法上，使得各種成果不斷涌現(xiàn)，各個領域的聚類分析算法層出不窮。通過聚類分析可以發(fā)現(xiàn)隱藏在數(shù)據(jù)集中的簇，標識出有意義的模式或分布。不同算法針對與不同規(guī)模的數(shù)據(jù)集而提出，而使用卻不僅僅限于某些特定的環(huán)境。</p><p>　　1.2

18、課題研究的意義</p><p>　　文本聚類分析在信息檢索領域有相當長的研究歷史，近年來在文本數(shù)據(jù)上的聚類分析研究和應用越來越受到關注。關于文本數(shù)據(jù)上的聚類分析研究，較早的綜合性介紹可以追溯到C.J.van Rijsbergen在IR領域的經典書籍《InformationRetrieval》中提到的利用文本聚類分析技術來提高信息檢索系統(tǒng)的準確率，但近年來此類研究已不多見。上個世紀90年代以來，文本的聚類分析技術研

19、究更多地集中在對大規(guī)模的文檔集合的瀏覽上在對用戶提出的查詢重新組織搜索引擎的查詢結果的研究中利用聚類技術重新組織文檔集合，用于文檔集合的瀏覽，這是近年來文本聚類中一個廣受關注的研究點，2004年SIGIR上MSRA推出的Search Result Clustering技術代表了此類應用研究目前最新的進展。在此類研究中，主要利用K-Means或者后綴樹聚類算法的變種來實現(xiàn)其需求。文檔聚類分析算法被用于自動產生文檔集合的層次結構，比如用于產

20、生類似Yahoo!的網頁分類目錄結構。近年來，文檔聚類算法還在文檔分析處理領域中一個新的應用方向話題檢測與跟蹤中得到了進一步研究與應用。話題檢測中利用文檔聚類算法從大量的文檔中自動</p><p>　　第二章 文本聚類效果影響因素</p><p><b>　　2.1文本聚類過程</b></p><p>　　影響文本聚類分析效果的因素是多方面的

21、，文本聚類分析全過程中的每個步驟都有可能對聚類結果造成影響。下面通過簡要描述聚類分析過程來說明對結果可能造成影響的各種因素,如圖2-1所示:</p><p><b>　　圖2-1 聚類流程</b></p><p>　　聚類分析過程分成三個步驟，通過這三個步驟可以找到影響聚類分析效果四個方面的因素。聚類流程三個步驟的實際處理內容為：</p><p&g

22、t;　　(1)文本聚類分析首先將文本表示成機器可計算的形式。不論是抽取文本特征形成一個向量還是抽取文本特征形成一個特殊的結構，對文本的這種機器表示過程簡稱為文本表示。文本表示過程顯然需要領域知識參與，文本中哪些因素可以構成特征，特征中哪些在聚類中可用以及如何使用是文本聚類第一步驟文本表示考察的內容；</p><p>　　(2)文本聚類分析的第二個步驟是算法。不同的算法有不同的特性，對相同的數(shù)據(jù)輸入，不同的算法會產

23、生出不同的聚類結果。聚類分析算法可以從不同的角度進行比較，比如是否產生層次聚類結構、是否需要參數(shù)、是否能夠產生模糊聚類、能否識別出不規(guī)則形狀的簇等等。目前在文獻中出現(xiàn)的聚類分析算法數(shù)目眾多，但在文本數(shù)據(jù)上效果孰優(yōu)孰劣仍沒有得到有效的研究。這個步驟中算法的時空效率、聚類結果質量是研發(fā)中選擇算法的主要標準。該步驟還有一個關鍵因素就是對象距離(或者相似度)如何定義；</p><p>　　(3)第三個步驟是算法中參數(shù)的選

24、擇。不同的算法對參數(shù)的敏感性不同，但是基本上參數(shù)的好壞對結果的影響都比較顯著。從這三個步驟可以看出影響文本聚類分析效果的因素包括四個方面：文本表示模型、距離度量方法、算法模型和參數(shù)優(yōu)化。參數(shù)的設定主觀性比較強，如何設定才是一個好的參數(shù)缺乏有效的方法，利用本文中實現(xiàn)的聚類算法包和聚類評價方法可以通過指標的變化曲線圖尋找算法的最佳參數(shù)。</p><p><b>　　2.2文本表示模型</b>&l

25、t;/p><p>　　在實際的文本聚類分析研究，將實際文本內容變成機器內部表示結構的方法多種多樣，可以用詞、字、短語、n-Gram、顯著性短語等形成向量、樹等結構。在經典的研究中通常利用特征(Term，包括字、詞、詞組等)的詞頻信息建立文本向量，通過文本向量與文本向量之間的相似度來進行聚類分析。</p><p>　　文本表示包括兩個問題：表示與計算。表示特指特征的提取，計算指權重的定義和語義相

26、似度的定義。特征提取包括特征的定義和篩選，特征定義和篩選考慮以什么作為文本的特征，并不是所有的詞和字都要求或者可以成為特征。特征的權重定義及特征結構上的相似度度量可以選取不同的模型，如向量空間模型、概率模型、語言模型等。文本表示是文本聚類的第一步，該步驟的變化很多，對最終聚類效果的影響也不盡相同。文本表示本質上是對原始文本進行轉換，使之在機器上可形式化描述、可計算。特征定義與篩選可以采用不同的特征選擇方法，可利用N-Gram、PAT樹提

27、取特征、可利用LSI降維轉化特征、也可利用語義詞典WordNet或者HowNet定義更復雜的特征結構。關于特征定義與篩選可以參考自然語言處理領域中的相關研究，這里不詳細介紹。本節(jié)接下來主要介紹信息檢索和文本分析處理中經常用到的幾個檢索模型，這幾個檢索模型根據(jù)不同的理論假設推導、定義了不同的特征權重計算方法與語義相似度計算方法，是文本表示模型的重要組成部分。</p><p><b>　　2.2.1布爾模型

28、</b></p><p>　　布爾模型是基于集合論與布爾代數(shù)之上的一種簡單模型，主要應用于信息檢索中。在布爾模型中，一個文檔表示成文檔中出現(xiàn)的特征的集合，也可以表示成為特征空間上的一個向量，向量中每個分量權重為0或者1，這種布爾模型稱為經典布爾模型。經典布爾模型中查詢與文檔的相關性只能是0或者1，滿足查詢query中的所有邏輯表達式的文檔被判定相關，不滿足的被判定為不相關。經典布爾模型只能用于信息檢索

29、中計算用戶查詢與文檔的相關性，而無法利用該模型計算兩個文檔更深層面的相似度，無法在更多的文本處理應用中使用。在經典布爾模型基礎上，研究人員又提出了擴展布爾模型(Extended Boolean Approach)，重新定義了And與Or操作符成為多元操作符，使相關性可以成為[0,1]之間的數(shù)。</p><p>　　2.2.2向量空間模型</p><p>　　Salton教授提出的向量空間模

30、型簡稱VSM模型(Vector Space Model)，是信息檢索領域中經典的檢索模型。向量空間模型將文檔表示成一個向量，向量的每一維表示一個特征，這個特征可以是一個字、一個詞、一個n-gram或某個復雜的結構。通過對文檔的解析處理可以得到這些特征。通常情況下用向量空間模型中的向量表示文檔時，需要對文檔進行切分(中文分詞、英文通過詞的分界符識別單詞)、停用詞處理、英文詞的詞形還原或者提取詞干(Stemming)，經過若干個處理步驟后，

31、基本上就可以得到一系列詞，將這些詞作為文檔的特征。所有的這些詞構成一個“空間”，每個詞對應著空間中的一維。每個文檔可以用文檔中的詞來表示，這些詞及其對應的權重構成一個向量。文檔對應特征空間中的一個向量，對應特征空間中的一個點。表2.1 說明VSM模型中文檔與向量空間之間的映射關系。</p><p>　　表2.1 VSM模型中文檔與向量空間之間的映射關系</p><p>　　2.3 文本相似

32、度計算</p><p>　　文本相似度計算是自然語言處理、Web智能檢索、文本分類和文本聚類研究中的一個基本問題。一個文本聚類分析過程的質量取決于對度量標準的選擇。因此，在研究聚類算法之前，先要討論其度量標準。文本相似度是用來衡量文本之間相似程度大小的一個統(tǒng)計量。文本相似度一般定義為界于0和1之間的一個值。如果兩文本之間相似度為1，則說明這兩個文本對象完全相同；反之，則說明兩文本沒有相似之處。</p>

33、<p>　　2.3.1樣本間相似度</p><p>　　在向量空間模型中，文本相似性的度量方法很多，主要有內積法、Dice系數(shù)法、余弦法和距離度量法等。</p><p><b>　　1.內積法</b></p><p>　　通常在文本向量中，最常使用的相似度計算公式就是兩個文本向量之間的“內積”運算，其定義為：</p>

34、<p><b>　　2.Dice系數(shù)法</b></p><p><b>　　3.余弦法</b></p><p>　　上述各公式中，Sim(di,dj)表示文本di和dj之間的相似程度，分Wki,Wkj分別表示文本di和dj的第k個特征項的權重，n為文本特征項數(shù)。Sim值越大表示兩個文本越相似，Sim越小則表示兩個文本區(qū)別越大。<

35、/p><p><b>　　4.距離度量法</b></p><p>　　在文本相似度計算中，我們也可以用兩個文本之間的距離來度量文本之間的相似程度。常使用的距離公式如下：</p><p>　　公式中，Dis(di,dj)表示文本向量di和dj在向量空間的距離，Wki,Wkj分別表示文本的第k個特征項的權重，參數(shù)p決定了選擇的是哪種距離計算。</

36、p><p><b>　　當p=1時</b></p><p><b>　　當p=2時</b></p><p>　　這就是歐式距離，也就是向量空間中的直線距離。</p><p>　　2.3.2簇間相似度</p><p>　　在聚類分析中，我們還需要衡量類與類之間的相似度，實現(xiàn)類與類之

37、間的合并或拆分。為了衡量文本集合之間的相似度，常見的方法有：最小距離、最大距離、平均距離、質心法、離差平方和等。</p><p><b>　　2.4文本聚類算法</b></p><p>　　聚類分析作為一個活躍的研究領域，已經出現(xiàn)了很多聚類算法，總體上聚類算法可分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網格的方法等。每種算法都有各自的優(yōu)缺點，都有其適用的

38、領域，并不是每一類算法都適合于文本聚類，我們必須根據(jù)文本數(shù)據(jù)的特點對聚類算法進行分析選擇。</p><p>　　2.4.1基于劃分的方法</p><p>　　基于劃分的聚類算法（Partitioning Method）是文本聚類應用中最為普遍的算法。方法將數(shù)據(jù)集合分成若干個子集，它根據(jù)設定的劃分數(shù)目k選出k個初始聚類中心，得到一個初始劃分，然后采用迭代重定位技術，反復在k個簇之間重新計算每

39、個簇的聚類中心，并重新分配每個簇中的對象，以改進劃分的質量。使得到的劃分滿足“簇內相似度高，簇間相似度小”的聚類原則。典型的劃分聚類方法有k-means算法[36]和k-medoids算法，兩者的區(qū)別在于簇代表點的計算方法不同。前者使用所有點的均值來代表簇，后者則采用類中某個數(shù)據(jù)對象來代表簇。為了對大規(guī)模的數(shù)據(jù)集進行聚類，以及處理復雜形狀的聚類，各類改進的劃分算法逐漸增多。</p><p>　　基于劃分方法的優(yōu)點

40、是運行速度快，但該方法必須事先確定k的取值。算法容易局部收斂，且不同的初始聚類中心選取對聚類結果影響較大。為此，應用最廣泛的k-means算法有很多變種，他們可能在初始k個聚類中心的選擇、相似度的計算和計算聚類中心等策略上有所不同，最終實現(xiàn)聚類結果改進的目標。</p><p>　　2.4.2基于層次的方法</p><p>　　基于層次的聚類算法（Hierarchical Method）又叫

41、“分級聚類算法”或“樹聚類”，它通過分解給定的數(shù)據(jù)對象集來創(chuàng)建一個層次。這種聚類方法有兩種基本的技術途徑：一是先把每個對象看作一個簇，然后逐步對簇進行合并，直到所有對象合為一個簇，或滿足一定條件為止；二是把所有對象看成一類，根據(jù)一些規(guī)則不斷選擇一個簇進行分解，直到滿足一些預定的條件，如類的數(shù)目達到了預定值，或兩個最近簇的距離達到閾值等。前者稱為自下而上的凝聚式聚類，后者稱為自上而下的分裂式聚類。</p><p>

42、　　在文本聚類中，最常見的是凝聚的層次聚類算法。使用該算法可以得到較好的聚類結果，而且該方法無需用戶輸入參數(shù)；但是層次聚類算法的時間復雜度比較高，達到了O(n2)，對于大規(guī)模的文本集合，有其不適用性。此外，在層次聚類算法中，一旦兩個簇在凝聚和分裂后，這個過程將不能被撤銷，簇之間也不能交換對象。如果某一步沒有很好的選擇要凝聚或者分裂的簇，將會導致低質量的聚類結果。</p><p>　　2.4.3基于密度的方法<

43、;/p><p>　　絕大多數(shù)劃分算法都是基于對象之間的距離進行聚類，這類方法只能發(fā)現(xiàn)圓形或球狀的簇，較難發(fā)現(xiàn)任意形狀的簇。為此，提出了基于密度的聚類算法（Density-Based Clustering Method），其主要思想是：只要鄰近區(qū)域的對象或數(shù)據(jù)點的數(shù)目超過某個閾值，就繼續(xù)聚類。即對給定類中的每個數(shù)據(jù)點，在一個給定范圍的區(qū)域中至少包含某個數(shù)目的點，這樣就能很好的過濾掉“噪聲”數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。其基本

44、出發(fā)點是，尋找低密度區(qū)域分離的高密度區(qū)域。具有代表性的方法是DBSCAN（Density Based Spatial Clustering of Applications with</p><p>　　Noise），它是將密度足夠大的那部分記錄組成類，可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類，但它需要用戶主觀來選擇參數(shù)，從而影響了最終的聚類結果。</p><p>　　基于密度的聚

45、類算法在當前的文獻中較少被用于文本聚類中。這是由于文本間的相似度不穩(wěn)定，同屬一簇的文本，有些文本間的相似度較高，所以密度高；有些相似度較低，所以密度低。如果根據(jù)全局的密度參數(shù)進行判斷，顯然是不適合的。并且密度單元的計算復雜度大，需要建立空間索引來降低計算量，且對數(shù)據(jù)維數(shù)的伸縮性較差。</p><p>　　2.4.4基于網格的方法</p><p>　　基于網格的算法（Grid-Based C

46、lustering Method）把對象空間量化為有限數(shù)目的單元，形成了一個網絡結構。所用的聚類操作都在整個網絡結構即量化的空間上進行。這種方法的一個突出的優(yōu)點就是處理速度很快，其處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與量化空間中的每一維的單元數(shù)目有關。此外，它還可以處理高維數(shù)據(jù)。代表算法有統(tǒng)計信息網格法STING算法、聚類高維空間法CLIQUE算法、基于小波變換的聚類法WAVE-CLUSTER算法。</p><p>

47、　　STING（Statistical Information Grid），利用了存儲在網格中的統(tǒng)計信息，它不但能并行處理且能增量更新，因而效率很高，缺點是簇的質量和精確性欠佳。</p><p>　　WaveCluster（Clustering Using Wavelet Transformation）是一種多分辨率的聚類算法。其主要優(yōu)點是能有效地處理大規(guī)模數(shù)據(jù)集；能發(fā)現(xiàn)任意形狀的簇；能成功地處理孤立點；對于輸入

48、的順序不敏感；不要求指定任何參數(shù)；且效率和聚類質量都比較高。</p><p>　　CLIQUE（Clustering in Quest）是一種將基于密度的方法與基于網格的方法相結合的算法，能有效處理大型數(shù)據(jù)庫的高維數(shù)據(jù)。它對輸入順序不敏感，無需假設任何規(guī)范的數(shù)據(jù)分布。另外，它還具有良好的可伸縮性。但由于方法大大簡化，聚類結果的精確可能降低。</p><p>　　2.4.5基于模型的方法&l

49、t;/p><p>　　基于模型的算法（Model-Based Clustering Method）試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學模型之間的適應性。這樣的算法經常是基于這樣的假設，數(shù)據(jù)是根據(jù)潛在的概率分布生成的。它通過為每個聚類假設一個模型來發(fā)現(xiàn)符合相應模型的數(shù)據(jù)對象。根據(jù)標準統(tǒng)計方法并綜合考慮“噪聲”或異常數(shù)據(jù)，該方法可以自動確定聚類個數(shù)，從而得到魯棒性較好的聚類方法。基于模型的算法主要有兩類，分別為統(tǒng)計學方法和神經網

50、絡方法。</p><p>　　大多數(shù)的概念聚類采用的是統(tǒng)計的方法，即在決定一個類時，用可能性的描述語句，典型的代表就是COBWEB，它是一個通用且簡單的聚類方法?；谏窠浘W絡的聚類方法是將每一個類看作一個標本，它是這個類型的“典型”，但不需要和某個具體的對象或例子相對應。根據(jù)新對象和這個標本之間的距離，就可以將這個對象進行分類了。如基于SOM的文檔聚類方法在數(shù)字圖書館等領域得到了較好的應用。聚類分析算法眾多，應用

51、于文檔的聚類分析算法也種類繁多，如何評價文檔聚類分析的效果，目前還沒有一個確定的說法。在實際的應用中一般都是實現(xiàn)幾種算法，然后用人工判斷的方法去選擇合適的算法以及算法相對應的參數(shù)。這么多的算法雖然帶來了更多的選擇，但同時也帶來了應用上的困難，因此有必要在一個統(tǒng)一的尺度上來衡量一些算法并對他們做出評價。</p><p><b>　　2.5本章小結</b></p><p>

52、;　　本章主要介紹了影響文本聚類結果的三方面主要因素：文本表示模型、相似度計算方法及聚類算法。文本聚類過程中每個步驟都有可能影響最終的聚類效果，各方面因素變化情形眾多，在實際研究和工程應用中，聚類評價工作困難重重。為了更好地評價聚類結果，我們在下一章將詳細介紹已有的文本聚類評價方法，比較各自的優(yōu)缺點。</p><p>　　第三章 k-均值聚類算法</p><p>　　3.1 K-均值聚類算

53、法的思想</p><p>　　3.1.1 K-均值聚類算法的基本思想</p><p>　　一九六七年，麥克奎因[B. Mac Queen]提出了K-均值聚類算法，用來處理數(shù)據(jù)聚類的問題，該種算法由于其算法簡便，又很早提出，因此在科學和工業(yè)領域的應用中影響力極為廣泛。該算法首先隨機選取k個數(shù)據(jù)點作為n個簇的初始簇中心，集合中每個數(shù)據(jù)點被劃分到與其距離最近的簇中心所在的類簇之中，形成了k個聚類

54、的初始分布。對分配完的每一個類簇計算新的簇中心，然后繼續(xù)進行數(shù)據(jù)分配過程，這樣迭代若干次后，若簇中心不再發(fā)生變化，則說明數(shù)據(jù)對象全部分配到自己所在的類簇中，聚類準則函數(shù)收斂，否則繼續(xù)進行迭代過程，直至收斂。這里的聚類準則函數(shù)一般采用聚類誤差平方和準則函數(shù)。本算法的一個特點就是在每一次的迭代過程中都要對全體數(shù)據(jù)點的分配進行調整，然后重新計算簇中心，進入下一次的迭代過程，若在某一次迭代過程中，所有數(shù)據(jù)點的位置沒有變化，相應的簇中心也沒有變化

55、，此時標志著聚類準則函數(shù)已經收斂，算法結束。</p><p>　　3.1.2 K-均值聚類算法的算法流程</p><p>　　原始的K-均值聚類算法:</p><p>　　輸入:數(shù)據(jù)集x={x1，x2，……xn}，聚類數(shù)目k;</p><p>　　輸出: k個類簇cj，j=1，2，……，k</p><p>　　[ste

56、pl]令I=1，隨機選取k個數(shù)據(jù)點作為k個類簇的初始簇中心，mj(I) j=1，2，…，k;</p><p>　　[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.</p><p>　　[steP3]計算k個新的聚類中心&l

57、t;/p><p>　　[step4]判斷:若mj(i+1) mj(I)，j=1，2，…，k，則I=i+1，返回step2:否則，算法結束。</p><p>　　K-均值聚類算法在執(zhí)行過程中還可以加入聚類準則函數(shù)來終止迭代過程，一般采用聚類誤差平方和準則函數(shù)，即在上面算法流程中的step4中計算聚類誤差平方和J，然后加入判斷，若兩次的J值沒有明顯變化，則說明J值已經收斂，結束算法，否則轉入ste

58、p2繼續(xù)執(zhí)行。具體流程如下:</p><p>　　[Stepl][初始化l隨機指定k個聚類中心(ml，m2，……mk);</p><p>　　[Step2][分配xi]對每一個樣本xi，，找到離它最近的聚類中心，并將其分配到該類:</p><p>　　[Step3][修正簇中心]重新計算各簇中心</p><p>　　[Step4][計算偏差]

59、 </p><p>　　[Step5][收斂判斷]如果J值收斂，則return(m1， m2，……，mk)，算法終止;否則，轉Step2。</p><p>　　從上面的算法思想及流程中可以看出，k個類簇的初始簇中心點的選取對聚類的最終結果至關重要，算法中，每一次迭代都把數(shù)據(jù)點劃分到與其距離最近的簇中心所在的類簇中去，然后重新計算簇中心，進而反復迭代，直到每一個數(shù)據(jù)點都不再重新劃分為止。&l

60、t;/p><p>　　3.1.3 K-均值算法的優(yōu)缺點分析</p><p>　　K-均值算法是一種基于劃分的聚類算法，它通過不斷的迭代過程來進行聚類，當算法收斂到一個結束條件時就終止迭代過程，輸出聚類結果。由于其算法思想簡便，又容易實現(xiàn)，因此K-均值算法己成為一種目前最常用的聚類算法之一。然而K-means過分依賴于初始中心點的選取，且容易受噪音點的影響。為解決這一問題，出現(xiàn)了各種基于全局最優(yōu)

61、化思想的K-均值聚類方法，比如模擬退火算法、遺傳算法等。然而這些技術并沒有得到廣泛認可，在許多實際應用中還是反復利用K-均值聚類算法來解決問題。</p><p>　　K-均值聚類算法采用迭代式的過程對樣本點進行分配來尋求最終的聚類結果，其終止條件是所有樣本的位置不再變化，其迭代過程可以概括如下:(l)分配樣本點，即對每個樣本點，將其分配到與其距離最近的簇中心所在的類簇中;(2)重新計算簇中心，對于每一個重新分配后

62、的類簇，重新計算其簇中心。和大多數(shù)的聚類算法一樣，K-均值聚類算法也有其自身的局限，主要局限如下:</p><p>　　(1)K-均值聚類算法中的聚類數(shù)目即K值需要由用戶預先給出。從K-均值聚類算法的算法流程中可以看出，K值作為一個需要預先確定的參數(shù)，在已知的前提下才能執(zhí)行K-均值聚類算法，而在實際應用中，需要聚類的數(shù)據(jù)究竟要分成多少個類別，往往不是被用戶所知的。當聚類數(shù)目不被人所知的情況下，人們往往需要結合其它

63、算法來獲取聚類數(shù)目，即K值。往往獲取K值的代價要比K-均值聚類算法的代價大得多，因此K值的不確定性是K-均值聚類算法的一個很大的不足之處。</p><p>　　(2)K-均值聚類算法嚴重依賴于初始簇中心點的選取。K-均值聚類算法隨機的選取K個初始簇中心點，并針對這K個簇中心點進行迭代運算，即重新分配數(shù)據(jù)點和重新計算簇中心的運算，直到所有的數(shù)據(jù)點位置不再變化或聚類誤差準則函數(shù)不再變化。這樣就導致了K-均值聚類算法對

64、初始簇中心點的嚴重依賴性。初始簇中心點選取不當很容易造成聚類結果陷入局部最優(yōu)解甚至或導致錯誤的聚類結果。</p><p>　　(3)K-均值聚類算法的聚類結果容易受噪音點數(shù)據(jù)的影響。在K-均值聚類算法中，每次對于簇中心的重新計算，都是通過對每一個類簇中所有數(shù)據(jù)點求均值，這樣，當數(shù)據(jù)集中存在噪音點數(shù)據(jù)時，均值點的計算將導致聚類中心(即簇中心偏離數(shù)據(jù)真正密集的區(qū)域，而趨向噪音點數(shù)據(jù)歹這樣導致聚類結果的不準確。因此，當

65、數(shù)據(jù)集中存在遠離所有數(shù)據(jù)點的噪音點時，聚類結果將很大程度上受這些噪音點的影響，導致聚類結果的錯誤，所以K-均值聚類算法對噪聲點和孤立點非常敏感。</p><p>　　(4)K-均值聚類算法無法發(fā)現(xiàn)任意形狀的簇。K-均值聚類算法采用距離函數(shù)作為度量數(shù)據(jù)點間相似度的方法，這里的距離函數(shù)多采用歐氏距離，同時采用聚類誤差平方和準則函數(shù)作為聚類準則函數(shù)，對于基于歐式距離的聚類算法而言，其只能發(fā)現(xiàn)數(shù)據(jù)點分布較均勻的類球狀簇，

66、對于聚類誤差平方和準則函數(shù)而言，當類簇大小差別較大，形狀較不規(guī)則時，容易造成對較大的類簇進行分割來達到目標函數(shù)取極小值的目的，因此容易造成錯誤的聚類結果。</p><p>　　(5)K-均值聚類算法不適用于大數(shù)據(jù)量的聚類問題。K-均值聚類算法每次迭代過程都要調整簇中心及重新分配數(shù)據(jù)點，因此，當數(shù)據(jù)量比較大的時候，這些迭代過程的計算量是相當大的，算法的時間開銷也是巨大的，因此，由于需要大量的計算時間，因此K-均值聚

67、類算法在待聚類數(shù)據(jù)量較大的時候并不適用。</p><p>　　3.1.4現(xiàn)有的對于K-均值聚類算法的改進</p><p>　　目前，對于K-均值聚類算法的改進主要集中在以下兩個方面:</p><p>　　(1)初始聚類中心的選擇K-均值聚類算法是一個迭代的求解最優(yōu)解的問題，這里的最優(yōu)解一般指的是目標函數(shù)(即聚類誤差和準則函數(shù))的最優(yōu)解，是一個優(yōu)化問題。然而，作為聚類

68、誤差和準則函數(shù)，通常存在一些局部最小點，目標函數(shù)的搜索方向總是沿著聚類誤差和準則函數(shù)的遞減方向進行，當初始簇中心不同時，搜索路徑也會不同，而目標函數(shù)具有很多局部最優(yōu)解，這樣就存在著，當初始簇中心選取不當時，目標函數(shù)容易陷入局部最優(yōu)解。而K-均值聚類算法采取隨機選取初始簇中心點，這樣，初始中心點的不同或數(shù)據(jù)輸入順序的不同都有可能導致聚類結果的不穩(wěn)定性，且無法得到全局最優(yōu)解而陷入局部最優(yōu)解。</p><p>　　(2

69、)K值的確定問題K-均值聚類算法中，K值是由用戶預先確定的，而在實際應用中，這個K值很難直接確定，尤其是當數(shù)據(jù)量較大時，K值的確定問題將成為K一均值聚類算法的一個很大的困難，因為在多數(shù)情況下人們并不能提前預知數(shù)據(jù)的分布情況及分類情況。而K-均值聚類算法的聚類結果受K值的影響，K值不同時，聚類結果往往也隨著不同，很多方法是通過試探K值來達到獲取K值的目的，而在數(shù)據(jù)量較大時，這種方法并不行得通，需要大量的時間代價，因此，為了得到確定的聚類結

70、果，K值的確定顯得尤為重要。因此，在無監(jiān)督情況下，通過某種學習方法得到合適的K值是很有必要的。</p><p>　　基于K-均值聚類算法的改進，國內外的專家學者做了大量的研究工作，主要</p><p><b>　　總結如下。</b></p><p>　　3.1.5現(xiàn)有基于初始中心點改進的K-均值聚類算法</p><p>

71、　　目前的K-均值聚類算法中，對于初始聚類中心點的選取方法主要總結如下:</p><p>　　(1)隨機選取k個樣本作為初始聚類中心，由于是最早提出的這種選擇初始聚類中心點的方法，因此在后來的很多文獻中把這種隨機選擇初始聚類中心的方法稱為FA(ForgyAPProach)。</p><p>　　(2)按最大最小距離聚類法中尋找聚類中心的方法來確定K-均值聚類算法</p>&l

72、t;p><b>　　中的初始聚類中心。</b></p><p>　　(3)將全部樣本以某種規(guī)則直觀的分成k類，分別計算每一類的均值點作為</p><p>　　K-均值聚類算法的初始聚類中心。</p><p>　　(4)采用基于數(shù)據(jù)采樣的方法。分別選取K組采樣數(shù)據(jù)分別執(zhí)行K-均值聚</p><p>　　類算法，然后選

73、擇聚類結果最好的一組聚類中心作為算法的初始聚類中心點。</p><p>　　(5)通過“密度法”選擇代表點作為初始聚類中心。這里所指的密度是指樣本點分布的密集情況，描述為，對于所有的樣本，、將每個樣本點假設為中心，設定一個半徑，則落入這個半徑所在圓內的所有樣本點的數(shù)目即為該樣本點的密度值，在計算完所有樣本點的密度值后，選取最大密度值的樣本點作為第一個初始聚類中心，然后將該樣本點及其半徑所在圓內的數(shù)據(jù)點去除后，重新

74、設定半徑選取下一個初始中心點，以此類推，直到得到K個初始中心點。</p><p>　　(6)聚類問題解出k類問題的中心。算法思路如下:先將全部樣本點看成是一個類簇的聚類問題，執(zhí)行K-均值聚類算法后得到的簇中心即為一個類簇的聚類問題的最佳解，然后選取與現(xiàn)有簇中心距離最遠的點作為下一個類簇的初始簇中心，以此類推，確定出K個類簇的初始聚類中心。</p><p>　　(7)進行多次初始值的選擇、聚

75、類、找出一組最優(yōu)的聚類結果。</p><p>　　(8)采用遺傳算法或者免疫規(guī)劃方法lv1進行混合聚類。除了以上列出的初始中心點的選取方法以外，還有很多對K-均值聚類算法的初始中心點的改進算法，在這里由于篇幅的關系我們沒有一一列出。</p><p><b>　　3.2 本章小結</b></p><p>　　本章詳細的闡述了k-均值聚類算法的算法

76、思想及算法流程，并且詳細的提出了該算法的優(yōu)點以及存在的問題。同時也對k-means算法的改進有兩種方法一是：現(xiàn)有的對于K-均值聚類算法的改進，二是：現(xiàn)有基于初始中心點改進的K-均值聚類算法。</p><p>　　第四章 SOM聚類算法</p><p>　　4.1 SOM聚類算法的網絡特性與基本流程</p><p>　　4.1.1 SOM網絡的特性</p>

77、<p>　　神經細胞模型中還存在著一種細胞聚類的功能柱。它是由多個細胞聚合而成的，在接受外界刺激后，它們會自動形成。一個功能柱中的細胞完成同一種功能。生物細胞中的這種現(xiàn)象在SOM網絡模型中有所反應。當外界輸入不同的樣本到SOM網絡中，一開始輸入樣本引起輸出興奮的位置各不相同，但通過網絡自組織后會形成一些輸出群，它們分別代表了輸入樣本的分布，反映了輸入樣本的圖形分布特征，所以SOM網絡常常被稱為特性圖。</p>

78、<p>　　SOM網絡是輸入樣本通過競爭學習后，功能相同的輸入靠得比較近，不同的分得比較開，以此將一些無規(guī)則的輸入自動排開，在連接權的調整過程中，使權的分布與輸入域可逐步縮小，使區(qū)域的劃分越來越明顯。在這種情況下，不論輸入樣本是多少維的，都可投影到低維的數(shù)據(jù)空間的某個區(qū)域上。這種形式也成為數(shù)據(jù)壓縮。同時，如果高維空間比較相近的樣本，則在低維空間中的投影也比較接近，這樣就可以從中取出樣本空間中較多的信息。遺憾的是，網絡在高維映

79、射到低維時會發(fā)生畸變，而且壓縮比越大，畸變越大;另外網絡要求的輸入神經元數(shù)很大，因而SOM網絡比其他人工神經網絡(比如BP網絡)的規(guī)模要大。樣本的概率密度分布相似。所以SOM網絡可以作為一種樣本特征檢測器，在樣本排序、樣本分類以及樣本檢測方面有廣泛的應用。一般可以這樣說，SOM網絡的權矢量收斂到所代表的輸入矢量的平均值，它反映了輸入數(shù)據(jù)的統(tǒng)計特性。再擴大一點，如果說一般的競爭學習網絡能夠訓練識別出輸入矢量的點特征，那么SOM網絡能夠表現(xiàn)

80、輸入矢量在線上或平面上的分布特征。當隨機樣本輸入到SOM網絡時，如果樣本足夠多，那么在權值分布上可近似于輸入隨機樣本的概率密度分布，在輸出神經元</p><p>　　4.1.2 SOM網絡聚類的基本流程</p><p>　　步驟1:初始化連接權值，學習率a。，鄰域半徑Nbo.</p><p>　　步驟2:取樣對所有輸入樣本執(zhí)行步驟3一步驟6.</p>

81、<p>　　步驟3:確定獲勝神經元。如果采用歐氏距離，計算連接權向量與輸入樣本之間的距離，選擇值最小的神經元是獲勝神經元。</p><p>　　步驟4:更新獲勝神經元及其鄰域內所有神經元的連接權值，而鄰域外的神經元的連接權值保持不變。</p><p>　　步驟5:參數(shù)調整。調整學習率和鄰域半徑，為了保證算法的收斂，學習率的取值一般在O到1之間，且隨著學習代數(shù)的增加而遞減;鄰域半徑

82、也隨著學習代數(shù)的增加而遞減，最后只有獲勝結點在學習</p><p>　　步驟6:返回步驟2，直至算法收斂或達到最大迭代次數(shù)為為止。</p><p>　　4.1.3 SOM網絡聚類的優(yōu)點及存在的問題</p><p>　　(l) SOM神經網絡在聚類方面有如下優(yōu)點:</p><p>　　①無須用戶指定聚類數(shù)目，網絡通過學習過程自適應地確定聚類數(shù)目

83、;</p><p>　　②因其采用“勝者全得”的學習策略，對噪音數(shù)據(jù)不敏感;</p><p>　?、劬哂锌梢暬膬?yōu)點;它采用的鄰域學習策略能使數(shù)據(jù)從高維映射到低維時保持其拓撲結構不變，輸出層神經元連接權矢量的空間分布能正確地反應輸入模式的空間概率分布;因此，SOM網絡不但能學習到輸入模式的類別特征，而且能夠學習到輸入模式在原始空間中的拓撲結構特征和概率分布，從而具備可視化的優(yōu)點。</

84、p><p>　　(2)無導師學習現(xiàn)在發(fā)展的還不成熟，傳統(tǒng)SOM網絡在文本聚類領域的應用還存在著許多的不足:</p><p>　　①網絡輸出層結點的初始結構需要用戶預先給出;輸出層結點的初始拓撲結構與輸入模式在在原始數(shù)據(jù)空間中的拓撲結構一致時，網絡才會達到好的學習效果。但是由于文本數(shù)據(jù)高維性的特點，人們很難預先給出與原始數(shù)據(jù)空間中相一致的網絡輸出層拓撲結構。</p><p&g

85、t;　　②網絡訓練時，有些輸出層神經元的連接權值與輸入模式相差很大，始終不能獲勝，成為“死神經元”;其權值得不到任何學習訓練的機會，進而影響文本聚類的粒度和識別的精度。相反有些神經元因為獲勝次數(shù)過多，出現(xiàn)神經元過度利用的問題，也會影響網絡的學習效果。</p><p>　　③網絡輸出層神經元連接權的初始值影響聚類速度;因為文本數(shù)據(jù)的高維性，網絡學習一次花費時間較多。隨機確定輸出層神經元連接權的初始值，會引起網絡達到

86、收斂的學習次數(shù)過多，影響文本聚類的速度。</p><p>　　4.2改進的SOM聚類方法</p><p>　　4.2.1已有的學習策略改進</p><p>　　就具體的學習策略來說，自組織特征映射神經網絡采用的是“勝者全得”的競爭學習算法，就是在競爭學習時網絡的各輸出神經元相互競爭，最后只有一個最強神經元獲勝;只有獲勝節(jié)點才允許有輸出，且輸出為1，其余節(jié)點輸出為0。

87、這種學習策略存在如下兩個問題:</p><p>　　(l)網絡訓練時，有些輸出層神經元的連接權值與輸入模式相差很大，始終不能獲</p><p>　　勝，成為“死神經元”，其權值得不到任何學習訓練的機會;</p><p>　　(2)相反有些神經元因為獲勝次數(shù)過多，出現(xiàn)神經元過度利用的問題。近年來，有些學者針對神經元欠利用和過度利用的問題，提出了許多改進的學習策略，代表

88、性的有SOM-CV、SOM-C、ESOM、TASOM、DSOM。</p><p>　　(1)SOM-CV該種方法把SOM網絡的權值都初始化為l/m(m是輸入向量的維</p><p>　　數(shù))，每個輸入向量xj要經過如下修正后再輸入網絡。</p><p>　　(2)SOM-C即帶“良心”的競爭學習SOM，它的基本思想是給每個競爭層結點設置一個闡值，每次使競爭獲勝的神經

89、元的閩值增加，使經常獲勝的神經元獲勝的機會減小。</p><p>　　(3)ESOM把更新獲勝結點Z及其領域結點的權值修改。</p><p>　　(4)TASOM該種學習策略中，每個神經元都有自己的學習率和鄰域函數(shù)，并且能 根據(jù)學習時間自動地調整學習率和鄰域的大小。</p><p>　　(5)DSOM該種學習策略是把內源性一氧化氮(NO)的四維動態(tài)擴散特性和其在長時

90、間學習過程中的增強作用應用到SOM中，輸入向量X輸入網絡后，以某種規(guī)則(評價函數(shù))確定競爭層中一組獲勝神經元，稱為亞興奮神經元簇。并把每一個亞興奮神經元作為NO的擴散源。然后計算各亞興奮神經元所處位置的NO濃度，則NO濃度最高的神經元為最終獲勝單元。</p><p>　　以上算法對神經元的獲勝策略進行了改進，在一定程度上解決了神經元欠利用和過度利用的問題，可以得到較好質量的聚類結果。但是聚類沒有以類內離差最小一平

91、均類內相似度最大為基礎，很難保證可以得到使平均類內離差最小一平均類內相似度最大的聚類結果。本文借鑒學習矢量量化中等失真度的原則，針對文本聚類問題，把文本聚類追求的目標一平均類內離差最小即平均類內相似度最大考慮進去，提出了一種改進的學習策略，該算法把等離差理論引入神經網絡的學習過程中，通過調整類內離差來指導神經網絡的學習，以使得聚類結果的平均類內離差最小:不僅解決了神經元欠利用和過度利用的問題，而且大大提高了文本聚類的結果質量。</

92、p><p>　　4.2.2等離差理論在神經元獲勝策略中的應用改進</p><p>　　(l)文本聚類的目標函數(shù)基于劃分的聚類器的基本思想是:一個K階的聚類器把輸入空間分成K個小空間S1，S2，…，Sk，每個小空間S代表一個類別，每個小空間S內的聚類中心用z。來表示。</p><p>　　(2)等類內離差原則聚類問題的實質就是求出適當s和z，使總類內離差D(s)最小。通常

93、稱使總類內離差最小的聚類器為最優(yōu)聚類器。最優(yōu)聚類器的必要條件是指最近鄰條件和質心條件。</p><p>　　(3)改進算法的基本流程</p><p>　　根據(jù)等類內離差準則，希望所有分割區(qū)域的類內離差相等，即要求所有的D(S、)(i，2，…K)相等。所以，本文把等類內離差準則引入到SOM算法的學習策略中，在爭學習的過程中，將決定那個神經元獲勝的策略加以修改，定義新的距離測度為:d(x1，x

94、 2)=d(x，z)D(S)顯然當D(s)增加時，d(x，Z)隨之增加，這就減少了神經元2.獲勝的可能性，最終結果將導致所有區(qū)域的類內離差趨于相等。這樣不僅解決了神經元欠利用問題，而且使各連接權值在表征輸入空間數(shù)據(jù)分布時得到了更有效的利用，使得量化的總類內離差接近最小，從而得到最優(yōu)的聚類結果。</p><p>　　EDSOM算法的基本步驟可描述如下:</p><p>　　步驟1：初始化連接

95、權值w，學習率。鄰域半徑Nb。，對于輸出層每個神經元結點的類內離差初始化為D(s。)=1</p><p>　　步驟2: 取樣。對所有輸入樣本執(zhí)行步驟3一步驟6</p><p>　　步驟3: 確定獲勝神經元。如果采用歐氏距離，按連接權向量與輸入樣本之間的距離值最小的神經元是獲勝神經元。</p><p>　　步驟4: 更新按更新獲勝神經元及其鄰域內所有神經元的連接權值，

96、而鄰域外的神經元的連接權值保持不變。</p><p>　　步驟5: 參數(shù)調整。調整學習率和鄰域半徑，為了保證算法的收斂，學習率的取值一般在0到1之間，且隨著學習代數(shù)的增加而遞減;鄰域半徑也隨著學習代數(shù)的增加而遞減，最后只有獲勝結點在學習。</p><p>　　步驟6: 更新每個輸出層神經元結點的類內離差。若輸出層神經元結點對應的輸入空間區(qū)域非空，則更新類內離差。</p>&l

97、t;p>　　步驟7: 返回步驟2，直至算法收斂或達到最大迭代次數(shù)為為止。</p><p>　　4.2.3初始化連接權值</p><p>　　初始權的設置，對于網絡的收斂狀況和收斂速度都是有影響的。不同的初始權，在其它條件相同的情況下，可能達到不同的輸出方差水平。人工神經網絡學習，如同其它優(yōu)化技術一樣，初始權設置的好壞，也會影響到收斂的程度。一般說來，初始權值設置不當，有可能造成在某一

98、局部極小值周圍長期徘徊不出，收斂所需的時間延長，甚至收斂到局部最優(yōu)或不收斂。</p><p>　　4.2.4已有的初始化連接權的方法</p><p>　　網絡的訓練主要是通過對連接權的調整實現(xiàn)的，當連接權不再變化或者變化很少時，網絡訓練就完成了，達到了一個收斂的狀態(tài)。因此連接權的初始狀態(tài)對網絡的訓練過程影響很大。由于連接權矢量初始狀態(tài)最理想的分布是其方向與輸入模式的方向一致，因此在連接權初

99、始化時，應該盡可能地使其初始狀態(tài)與輸入模式處于一種互相容易接近的狀態(tài)。目前有下面幾種常用的初始化方法:</p><p>　　(1)隨機初始化權值:一般學習規(guī)則是將網絡的連接權賦予區(qū)間內的隨機值。一般情況下，輸入學習模式只處于整個模式空間的有限位置，如果對連接權值隨機初始化，則在權值矢量會廣泛地分布于各個隨機方向上，一定會有大量的連接權矢量與輸入模式方向差異很大，甚至方向相反。這樣在網絡訓練時，尋找輸入模式的最佳映

100、射就非常困難，為達到網絡收練，需經過很多次的反復學習。所以在實際應用中，這種初始化方法會出現(xiàn)網絡學習時間過長，甚至無法收斂的現(xiàn)象。</p><p>　　(2)所有連接權矢量賦予相同權值:將所有的連接權矢量賦予相同的初始值，這樣可以減少輸入模式在最初階段對連接權矢量的挑選余地，增加每一個權矢量被選中的機會，盡可能快地校正連接權矢量和輸入模式之間的方向偏差，加快收斂的速度。</p><p>　

101、　(3)從輸入空間中任意選取K個矢量對權值矢量進行初始化，K是輸出層神經元結點的個數(shù)。這種方法相對于隨機初始化連接權值來說，網絡訓練時，尋找輸入模式的最佳映射相對容易，但因為隨機選取的K個矢量不一定與模式的類別方向一致，達到網絡收斂的學習次數(shù)波動性較大。</p><p>　　(4)在文本聚類領域，還存在一種特殊的初始化權值的方法，即根據(jù)專家經驗，按照某一個單詞屬于某個類別的概率確定。由于文本數(shù)據(jù)的高維性，在進行聚

102、類之前，一般要進行特征選擇和特征抽取，以降低文本數(shù)據(jù)的維度。進行特征抽取以后，一個單詞可能映射到輸入空間的多個維上，使這種確定初始連接權值的方法變得非常困難。連接權值的理想分布是其方向與各個模式類別的方向一致，但在初始化時想做到這一點是不現(xiàn)實的，因為這是網絡訓練所要達到的目的，在網絡收斂時，連接權的方向與各個模式類別的方向一致。但在對連接權進行初始化時，可以試圖使連接權的初始狀態(tài)與各個模式類別的方向相似。于是，用SOM對數(shù)據(jù)進行聚類時，

103、對連接權值進行初始化時，可以試圖從輸入模式空間中找出K個有代表性的點，它們能代表各個模式類別的中心，或者與各個模式類別的方向相似，最起碼相差不能太大。選出的這K個數(shù)據(jù)點應該屬于不同的模式類別為好，且這K個數(shù)據(jù)點應盡量靠近該類別的中心，這是我們初始化連接權時要達到的目標。理論表明，文檔數(shù)據(jù)點密集區(qū)可能包含模式類別的中心或離模式類別的中心較近，本文提出一種用層次聚類法探測數(shù)據(jù)密集區(qū)，用探測到的K個數(shù)據(jù)密集區(qū)中心點隨機初始</p>

104、<p>　　4.2.5新的確定初始權值的方法</p><p>　　用SOM進行聚類時，本文通過如下方法從待聚類數(shù)據(jù)中選出K個有代表性的點，(K是輸出層神經元的節(jié)點數(shù)目):</p><p>　　步驟1:采用平均鏈接(UMPGA)對每個文檔的前Nb個近鄰(包括文檔本身)行聚類，這樣每個文檔的鄰近區(qū)域形成了一棵聚類樹(如圖3.1所示)，算法從這棵類層次樹上選取score==平均相似

105、度、文檔數(shù)量，score最高的結點(實際上是一個密的文檔集合)，被加入到一個鏈表中。圖中結點e依據(jù)score將被選中，它包括了{3，4，5，6，7，8}，這個密集的文檔集合中有可能包括模式類別的中心。</p><p><b>　　圖1 密集區(qū)域探測</b></p><p>　　步驟2:按照這些密集小區(qū)域的得分(Score)為這個鏈表進行排序。</p>&

106、lt;p>　　步驟3:為這些密集小區(qū)域生成中心點向量。中心向量是取屬于這個密集小區(qū)域的文檔向量各個維權重的平均值。</p><p>　　步驟4:在每次聚類時，算法接受用戶輸入的輸出層神經元結點數(shù)目參數(shù)K，對于這些中心點，找到一個合適的相似度閩值，使得在這個相似度闡值下，有K個中心點它們之間的相似度小于這個閩值。至此，獲得了K個中心。</p><p>　　步驟5:用這K個數(shù)據(jù)點對SOM