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

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

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

8、;/p><p>　　2.2.2向量空間模型5</p><p>　　2.3 文本相似度計(jì)算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)缺點(diǎn)分析13</p><p>　　3.1.4現(xiàn)有的對(duì)于K-均值聚類算法的改進(jìn)15</p><p>　　3.1.5現(xiàn)有基于初始中心點(diǎn)改進(jì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)點(diǎn)及存在的問(wèn)題19</p><p>　　4.2改進(jìn)的SOM聚類方法20</p><p>　　4.2.1已有的學(xué)習(xí)策略改進(jìn)20</p><p>　　4.2.2等離差理論在神經(jīng)元獲勝策略中的應(yīng)用改進(jìn)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>　　參 考 文 獻(xiàn)26</p><p><b>　　致 謝28</b></p><p><b>　　第一

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

48、的順序不敏感；不要求指定任何參數(shù)；且效率和聚類質(zhì)量都比較高。</p><p>　　CLIQUE（Clustering in Quest）是一種將基于密度的方法與基于網(wǎng)格的方法相結(jié)合的算法，能有效處理大型數(shù)據(jù)庫(kù)的高維數(shù)據(jù)。它對(duì)輸入順序不敏感，無(wú)需假設(shè)任何規(guī)范的數(shù)據(jù)分布。另外，它還具有良好的可伸縮性。但由于方法大大簡(jiǎn)化，聚類結(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ù)潛在的概率分布生成的。它通過(guò)為每個(gè)聚類假設(shè)一個(gè)模型來(lái)發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對(duì)象。根據(jù)標(biāo)準(zhǔn)統(tǒng)計(jì)方法并綜合考慮“噪聲”或異常數(shù)據(jù)，該方法可以自動(dòng)確定聚類個(gè)數(shù)，從而得到魯棒性較好的聚類方法。基于模型的算法主要有兩類，分別為統(tǒng)計(jì)學(xué)方法和神經(jīng)網(wǎng)

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

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

52、;　　本章主要介紹了影響文本聚類結(jié)果的三方面主要因素：文本表示模型、相似度計(jì)算方法及聚類算法。文本聚類過(guò)程中每個(gè)步驟都有可能影響最終的聚類效果，各方面因素變化情形眾多，在實(shí)際研究和工程應(yīng)用中，聚類評(píng)價(jià)工作困難重重。為了更好地評(píng)價(jià)聚類結(jié)果，我們?cè)谙乱徽聦⒃敿?xì)介紹已有的文本聚類評(píng)價(jià)方法，比較各自的優(yōu)缺點(diǎn)。</p><p>　　第三章 k-均值聚類算法</p><p>　　3.1 K-均值聚類算

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

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

55、，此時(shí)標(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個(gè)類簇cj，j=1，2，……，k</p><p>　　[ste

56、pl]令I(lǐng)=1，隨機(jī)選取k個(gè)數(shù)據(jù)點(diǎn)作為k個(gè)類簇的初始簇中心，mj(I) j=1，2，…，k;</p><p>　　[step2]計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)與這k個(gè)簇中心的距離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]計(jì)算k個(gè)新的聚類中心&l

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

76、思想及算法流程，并且詳細(xì)的提出了該算法的優(yōu)點(diǎn)以及存在的問(wèn)題。同時(shí)也對(duì)k-means算法的改進(jìn)有兩種方法一是：現(xiàn)有的對(duì)于K-均值聚類算法的改進(jìn)，二是：現(xiàn)有基于初始中心點(diǎn)改進(jì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)細(xì)胞模型中還存在著一種細(xì)胞聚類的功能柱。它是由多個(gè)細(xì)胞聚合而成的，在接受外界刺激后，它們會(huì)自動(dòng)形成。一個(gè)功能柱中的細(xì)胞完成同一種功能。生物細(xì)胞中的這種現(xiàn)象在SOM網(wǎng)絡(luò)模型中有所反應(yīng)。當(dāng)外界輸入不同的樣本到SOM網(wǎng)絡(luò)中，一開(kāi)始輸入樣本引起輸出興奮的位置各不相同，但通過(guò)網(wǎng)絡(luò)自組織后會(huì)形成一些輸出群，它們分別代表了輸入樣本的分布，反映了輸入樣本的圖形分布特征，所以SOM網(wǎng)絡(luò)常常被稱為特性圖。</p>

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

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

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

81、<p>　　步驟3:確定獲勝神經(jīng)元。如果采用歐氏距離，計(jì)算連接權(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é)點(diǎn)在學(xué)習(xí)</p><p>　　步驟6:返回步驟2，直至算法收斂或達(dá)到最大迭代次數(shù)為為止。</p><p>　　4.1.3 SOM網(wǎng)絡(luò)聚類的優(yōu)點(diǎn)及存在的問(wèn)題</p><p>　　(l) SOM神經(jīng)網(wǎng)絡(luò)在聚類方面有如下優(yōu)點(diǎn):</p><p>　　①無(wú)須用戶指定聚類數(shù)目，網(wǎng)絡(luò)通過(guò)學(xué)習(xí)過(guò)程自適應(yīng)地確定聚類數(shù)目

83、;</p><p>　?、谝蚱洳捎谩皠僬呷谩钡膶W(xué)習(xí)策略，對(duì)噪音數(shù)據(jù)不敏感;</p><p>　　③具有可視化的優(yōu)點(diǎn);它采用的鄰域?qū)W習(xí)策略能使數(shù)據(jù)從高維映射到低維時(shí)保持其拓?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)點(diǎn)。</

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

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

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

87、這種學(xué)習(xí)策略存在如下兩個(gè)問(wèn)題:</p><p>　　(l)網(wǎng)絡(luò)訓(xùn)練時(shí)，有些輸出層神經(jīng)元的連接權(quán)值與輸入模式相差很大，始終不能獲</p><p>　　勝，成為“死神經(jīng)元”，其權(quán)值得不到任何學(xué)習(xí)訓(xùn)練的機(jī)會(huì);</p><p>　　(2)相反有些神經(jīng)元因?yàn)楂@勝次數(shù)過(guò)多，出現(xiàn)神經(jīng)元過(guò)度利用的問(wèn)題。近年來(lái)，有些學(xué)者針對(duì)神經(jīng)元欠利用和過(guò)度利用的問(wèn)題，提出了許多改進(jìn)的學(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ù))，每個(gè)輸入向量xj要經(jīng)過(guò)如下修正后再輸入網(wǎng)絡(luò)。</p><p>　　(2)SOM-C即帶“良心”的競(jìng)爭(zhēng)學(xué)習(xí)SOM，它的基本思想是給每個(gè)競(jìng)爭(zhēng)層結(jié)點(diǎn)設(shè)置一個(gè)闡值，每次使競(jìng)爭(zhēng)獲勝的神經(jīng)

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

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

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

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

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

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

95、權(quán)值w，學(xué)習(xí)率。鄰域半徑Nb。，對(duì)于輸出層每個(gè)神經(jīng)元結(jié)點(diǎn)的類內(nèi)離差初始化為D(s。)=1</p><p>　　步驟2: 取樣。對(duì)所有輸入樣本執(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é)點(diǎn)在學(xué)習(xí)。</p><p>　　步驟6: 更新每個(gè)輸出層神經(jīng)元結(jié)點(diǎn)的類內(nèi)離差。若輸出層神經(jīng)元結(jié)點(diǎn)對(duì)應(yīng)的輸入空間區(qū)域非空，則更新類內(nèi)離差。</p>&l

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

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

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

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

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

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

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

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

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

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