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

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

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

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本章小結(jié)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 本章小結(jié)17</p><p>　　第四章 SOM聚類算法18</p><p>　　4.1 SOM聚類算法的網(wǎng)絡(luò)特性與基本流程18</p><p>　　4.1.1 SOM網(wǎng)絡(luò)的特性18</p><p>　　4.1.2 SOM網(wǎng)絡(luò)聚類的基本流程19</p>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、<p>　　2.3.1樣本間相似度</p><p>　　在向量空間模型中，文本相似性的度量方法很多，主要有內(nèi)積法、Dice系數(shù)法、余弦法和距離度量法等。</p><p><b>　　1.內(nèi)積法</b></p><p>　　通常在文本向量中，最常使用的相似度計算公式就是兩個文本向量之間的“內(nèi)積”運算，其定義為：</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個特征項的權(quán)重，n為文本特征項數(shù)。Sim值越大表示兩個文本越相似，Sim越小則表示兩個文本區(qū)別越大。<

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

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

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

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

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

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

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

42、　　在文本聚類中，最常見的是凝聚的層次聚類算法。使用該算法可以得到較好的聚類結(jié)果，而且該方法無需用戶輸入?yún)?shù)；但是層次聚類算法的時間復(fù)雜度比較高，達到了O(n2)，對于大規(guī)模的文本集合，有其不適用性。此外，在層次聚類算法中，一旦兩個簇在凝聚和分裂后，這個過程將不能被撤銷，簇之間也不能交換對象。如果某一步?jīng)]有很好的選擇要凝聚或者分裂的簇，將會導(dǎo)致低質(zhì)量的聚類結(jié)果。</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ù)，從而影響了最終的聚類結(jié)果。</p><p>　　基于密度的聚

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

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

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

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

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

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

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

52、;　　本章主要介紹了影響文本聚類結(jié)果的三方面主要因素：文本表示模型、相似度計算方法及聚類算法。文本聚類過程中每個步驟都有可能影響最終的聚類效果，各方面因素變化情形眾多，在實際研究和工程應(yīng)用中，聚類評價工作困難重重。為了更好地評價聚類結(jié)果，我們在下一章將詳細介紹已有的文本聚類評價方法，比較各自的優(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ù)聚類的問題，該種算法由于其算法簡便，又很早提出，因此在科學(xué)和工業(yè)領(lǐng)域的應(yīng)用中影響力極為廣泛。該算法首先隨機選取k個數(shù)據(jù)點作為n個簇的初始簇中心，集合中每個數(shù)據(jù)點被劃分到與其距離最近的簇中心所在的類簇之中，形成了k個聚類

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

55、，此時標(biāo)志著聚類準(zhǔn)則函數(shù)已經(jīng)收斂，算法結(jié)束。</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(lǐng)=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:否則，算法結(jié)束。</p><p>　　K-均值聚類算法在執(zhí)行過程中還可以加入聚類準(zhǔn)則函數(shù)來終止迭代過程，一般采用聚類誤差平方和準(zhǔn)則函數(shù)，即在上面算法流程中的step4中計算聚類誤差平方和J，然后加入判斷，若兩次的J值沒有明顯變化，則說明J值已經(jīng)收斂，結(jié)束算法，否則轉(zhuǎn)入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)，算法終止;否則，轉(zhuǎn)Step2。</p><p>　　從上面的算法思想及流程中可以看出，k個類簇的初始簇中心點的選取對聚類的最終結(jié)果至關(guān)重要，算法中，每一次迭代都把數(shù)據(jù)點劃分到與其距離最近的簇中心所在的類簇中去，然后重新計算簇中心，進而反復(fù)迭代，直到每一個數(shù)據(jù)點都不再重新劃分為止。&l

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

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

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

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

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

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

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

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

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

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

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

71、　　目前的K-均值聚類算法中，對于初始聚類中心點的選取方法主要總結(jié)如下:</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、擇聚類結(jié)果最好的一組聚類中心作為算法的初始聚類中心點。</p><p>　　(5)通過“密度法”選擇代表點作為初始聚類中心。這里所指的密度是指樣本點分布的密集情況，描述為，對于所有的樣本，、將每個樣本點假設(shè)為中心，設(shè)定一個半徑，則落入這個半徑所在圓內(nèi)的所有樣本點的數(shù)目即為該樣本點的密度值，在計算完所有樣本點的密度值后，選取最大密度值的樣本點作為第一個初始聚類中心，然后將該樣本點及其半徑所在圓內(nèi)的數(shù)據(jù)點去除后，重新

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

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

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

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

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

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

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

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

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

83、;</p><p>　?、谝蚱洳捎谩皠僬呷谩钡膶W(xué)習(xí)策略，對噪音數(shù)據(jù)不敏感;</p><p>　　③具有可視化的優(yōu)點;它采用的鄰域?qū)W習(xí)策略能使數(shù)據(jù)從高維映射到低維時保持其拓?fù)浣Y(jié)構(gòu)不變，輸出層神經(jīng)元連接權(quán)矢量的空間分布能正確地反應(yīng)輸入模式的空間概率分布;因此，SOM網(wǎng)絡(luò)不但能學(xué)習(xí)到輸入模式的類別特征，而且能夠?qū)W習(xí)到輸入模式在原始空間中的拓?fù)浣Y(jié)構(gòu)特征和概率分布，從而具備可視化的優(yōu)點。</

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

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

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

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

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

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

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

91、均類內(nèi)相似度最大為基礎(chǔ)，很難保證可以得到使平均類內(nèi)離差最小一平均類內(nèi)相似度最大的聚類結(jié)果。本文借鑒學(xué)習(xí)矢量量化中等失真度的原則，針對文本聚類問題，把文本聚類追求的目標(biāo)一平均類內(nèi)離差最小即平均類內(nèi)相似度最大考慮進去，提出了一種改進的學(xué)習(xí)策略，該算法把等離差理論引入神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)過程中，通過調(diào)整類內(nèi)離差來指導(dǎo)神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)，以使得聚類結(jié)果的平均類內(nèi)離差最小:不僅解決了神經(jīng)元欠利用和過度利用的問題，而且大大提高了文本聚類的結(jié)果質(zhì)量。</

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

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

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

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

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

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

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

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

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

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

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

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

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

105、度、文檔數(shù)量，score最高的結(jié)點(實際上是一個密的文檔集合)，被加入到一個鏈表中。圖中結(jié)點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ū)域的文檔向量各個維權(quán)重的平均值。</p><p>　　步驟4:在每次聚類時，算法接受用戶輸入的輸出層神經(jīng)元結(jié)點數(shù)目參數(shù)K，對于這些中心點，找到一個合適的相似度閩值，使得在這個相似度闡值下，有K個中心點它們之間的相似度小于這個閩值。至此，獲得了K個中心。</p><p>　　步驟5:用這K個數(shù)據(jù)點對SOM