1、基于文本的聚類算法研究摘 要聚類作為一種知識發現的重要方法，它廣泛地與中文信息處理技術相結合，應用于網絡信息處理中以滿足用戶快捷地從互聯網獲得自己需要的信息資源。文本聚類是聚類問題在文本挖掘中的有效應用，它根據文本數據的不同特征，按照文本間的相似性，將其分為不同的文本簇。其目的是要使同一類別的文本間的相似度盡可能大，而不同類別的文本間的相似度盡可能的小。整個聚類過程無需指導，事先對數據結構未知，是一種典型的無監督分類。本文首先介紹了文本聚類的相關的技術，包括文本聚類的過程，文本表示模型，相似度計算及常見聚類算法。本文主要研究的聚類主要方法是k-均值和SOM算法，介紹了兩種算法的基本思想和實現步

2、驟，并分析兩種算法的聚類效果。同時介紹了兩種算法的改進算法。關鍵詞：文本聚類 聚類方法 K-MEAN SOM IIAbstractClustering as an important knowledge discovery method, which extensively with Chinese information processing technology, used in network information processing to meet the users to quickly access from the Internet, the information reso

3、urces they need. Text clustering is a clustering problem in the effective application of text mining, which according to the different characteristics of text data, according to the similarity between the text, the text will be divided into different clusters. The aim is to make the same class as la

4、rge as possible the similarity between the text, and different types of text as small as possible the similarity between. The clustering process without guidance, prior to the data structure is unknown, is a typical unsupervised classification. This paper studies the effect of influencing factors th

5、at text clustering, text representation of the model such as the Boolean model, vector space model, probabilistic retrieval model and language model. Also studied the analysis of such text clustering algorithm: hierarchical clustering, agglomerative hierarchical clustering algorithm, hierarchical cl

6、ustering algorithm to split and so on. Also studied the text clustering algorithm analysis and methods of improvement.Key words：Text clustering clustering method k-mean som基于文本的聚類算法研究目 錄摘 要IVAbstractV目 錄VI第一章 緒 論11.1 課題研究的背景11.2課題研究的意義2第二章 文本聚類效果影響因素32.1文本聚類過程32.2文本表示模型42.2.1布爾模型52.2.2向量空間模型52.3 文本相

7、似度計算62.4文本聚類算法82.5本章小結11第三章 k-均值聚類算法123.1 K-均值聚類算法的思想123.1.1 K-均值聚類算法的基本思想123.1.2 K-均值聚類算法的算法流程123.1.3 K-均值算法的優缺點分析133.1.4現有的對于K-均值聚類算法的改進153.1.5現有基于初始中心點改進的K-均值聚類算法163.2 本章小結17第四章 SOM聚類算法184.1 SOM聚類算法的網絡特性與基本流程184.1.1 SOM網絡的特性184.1.2 SOM網絡聚類的基本流程194.1.3 SOM網絡聚類的優點及存在的問題194.2改進的SOM聚類方法204.2.1已有的學習策略

8、改進204.2.2等離差理論在神經元獲勝策略中的應用改進214.2.3初始化連接權值224.2.4已有的初始化連接權的方法224.2.5新的確定初始權值的方法234.3本章小結25參 考 文 獻26致 謝28基于文本的聚類算法研究第一章 緒 論1.1 課題研究的背景隨著Internet的迅猛發展，信息的爆炸式增加，信息超載問題變的越來越嚴重，信息的更新率也越來越高，用戶在信息海洋里查找信息就像大海撈針一樣。搜索引擎服務應運而生，在一定程度上滿足了用戶查找信息的需要。然而Internet的深入發展和搜索引擎日趨龐大，進一步凸現出海量信息和人們獲取所需信息能力的矛盾。那么，如何從中獲取特定內容的信

9、息和知識成為擺在人們面前的一道難題。面對互聯網時代龐雜無序的海量信息，智能高效地處理和深層次綜合利用信息離不開文本挖掘技術，國際上多個國家都抓緊投入文本挖掘技術的研究，以期能對“堆積如山”的信息進行有效的過濾，開發和利用，提取發現具有指導意義的知識。文本挖掘是指從大量文本數據中抽取出事先未知的，可理解的，最終可用的信息或知識的過程，它涉及Web，計算機語言，數據挖掘，信息檢索等多個領域，較大程度地解決了信息雜亂的現象，方便用戶準確地定位所需的信息和信息分流。文本挖掘可以對大量文檔集合的內容進行總結，結構分析，分類，聚類，關聯分析，分布分析以及利用文檔進行趨勢預測等，目前已成為一項具有較大實用價

10、值的關鍵技術，是組織和管理數據和知識的有力手段。聚類作為一種只是發現的重要方法，是數據挖掘中一項重要的研究課題，它廣泛地與中文信息處理技術相結合，應用于網絡信息處理中以滿足用戶快捷地從互聯網獲得自己需要的信息資源，文本聚類則是聚類問題在文本挖掘中的有效應用，是文本挖掘的重要內容之一。文本聚類是根據文本數據的不同特征，按照事物間的相似性，將其劃分為不同數據類的過程。其目的是使同一類別的文本間相似度盡可能大，而不同類別的文本間的相似度盡可能的小。在這一過程中無需指導，是一種典型的無需督分類，從而打破了在許多實際應用中由于缺少形成模式類別過程的知識，或者模式類別的形成非常困難時的挖掘局限性。隨著人們

11、對聚類問題更加深入地了解和重視，國內外大量學者不斷投身到該項目研究，聚類主要工作集中在尋找針對大型數據庫的聚類方法和世界的聚類分析方法上，使得各種成果不斷涌現，各個領域的聚類分析算法層出不窮。通過聚類分析可以發現隱藏在數據集中的簇，標識出有意義的模式或分布。不同算法針對與不同規模的數據集而提出，而使用卻不僅僅限于某些特定的環境。1.2課題研究的意義文本聚類分析在信息檢索領域有相當長的研究歷史，近年來在文本數據上的聚類分析研究和應用越來越受到關注。關于文本數據上的聚類分析研究，較早的綜合性介紹可以追溯到C.J.van Rijsbergen在IR領域的經典書籍InformationRetrieva

12、l中提到的利用文本聚類分析技術來提高信息檢索系統的準確率，但近年來此類研究已不多見。上個世紀90年代以來，文本的聚類分析技術研究更多地集中在對大規模的文檔集合的瀏覽上在對用戶提出的查詢重新組織搜索引擎的查詢結果的研究中利用聚類技術重新組織文檔集合，用于文檔集合的瀏覽，這是近年來文本聚類中一個廣受關注的研究點，2004年SIGIR上MSRA推出的Search Result Clustering技術代表了此類應用研究目前最新的進展。在此類研究中，主要利用K-Means或者后綴樹聚類算法的變種來實現其需求。文檔聚類分析算法被用于自動產生文檔集合的層次結構，比如用于產生類似Yahoo!的網頁分類目錄結

13、構。近年來，文檔聚類算法還在文檔分析處理領域中一個新的應用方向話題檢測與跟蹤中得到了進一步研究與應用。話題檢測中利用文檔聚類算法從大量的文檔中自動地抽取話題，應用于個性化信息服務或者情報分析。在這些應用的推動之下，文本數據上的聚類分析算法層出不窮，各說各的好處，在我們的工程實踐中具體該采用哪種算法，如何設計文本聚類算法并對其進行評價都是難以解決的問題。由于算法種類眾多，文本聚類算法間缺乏一個進行橫向比較與分析的機制，在工程實踐中對算法的選擇及參數的設定都是經驗性的，這對進一步開展研究以及科學地設計算法、分析算法造成了困難。因此，需要對文本聚類分析結果的質量進行評價，利用這種評價機制來指導算法設

14、計、算法選擇、算法效能分析、參數優化等。有了文本聚類分析的科學評價機制，我們未來的工作就有據可依，可以更科學地選擇算法，分析、設計算法。- 28 -第二章 文本聚類效果影響因素2.1文本聚類過程影響文本聚類分析效果的因素是多方面的，文本聚類分析全過程中的每個步驟都有可能對聚類結果造成影響。下面通過簡要描述聚類分析過程來說明對結果可能造成影響的各種因素,如圖2-1所示:圖2-1 聚類流程聚類分析過程分成三個步驟，通過這三個步驟可以找到影響聚類分析效果四個方面的因素。聚類流程三個步驟的實際處理內容為：(1)文本聚類分析首先將文本表示成機器可計算的形式。不論是抽取文本特征形成一個向量還是抽取文本特征

15、形成一個特殊的結構，對文本的這種機器表示過程簡稱為文本表示。文本表示過程顯然需要領域知識參與，文本中哪些因素可以構成特征，特征中哪些在聚類中可用以及如何使用是文本聚類第一步驟文本表示考察的內容；(2)文本聚類分析的第二個步驟是算法。不同的算法有不同的特性，對相同的數據輸入，不同的算法會產生出不同的聚類結果。聚類分析算法可以從不同的角度進行比較，比如是否產生層次聚類結構、是否需要參數、是否能夠產生模糊聚類、能否識別出不規則形狀的簇等等。目前在文獻中出現的聚類分析算法數目眾多，但在文本數據上效果孰優孰劣仍沒有得到有效的研究。這個步驟中算法的時空效率、聚類結果質量是研發中選擇算法的主要標準。該步驟還

16、有一個關鍵因素就是對象距離(或者相似度)如何定義；(3)第三個步驟是算法中參數的選擇。不同的算法對參數的敏感性不同，但是基本上參數的好壞對結果的影響都比較顯著。從這三個步驟可以看出影響文本聚類分析效果的因素包括四個方面：文本表示模型、距離度量方法、算法模型和參數優化。參數的設定主觀性比較強，如何設定才是一個好的參數缺乏有效的方法，利用本文中實現的聚類算法包和聚類評價方法可以通過指標的變化曲線圖尋找算法的最佳參數。2.2文本表示模型在實際的文本聚類分析研究，將實際文本內容變成機器內部表示結構的方法多種多樣，可以用詞、字、短語、n-Gram、顯著性短語等形成向量、樹等結構。在經典的研究中通常利用特

17、征(Term，包括字、詞、詞組等)的詞頻信息建立文本向量，通過文本向量與文本向量之間的相似度來進行聚類分析。文本表示包括兩個問題：表示與計算。表示特指特征的提取，計算指權重的定義和語義相似度的定義。特征提取包括特征的定義和篩選，特征定義和篩選考慮以什么作為文本的特征，并不是所有的詞和字都要求或者可以成為特征。特征的權重定義及特征結構上的相似度度量可以選取不同的模型，如向量空間模型、概率模型、語言模型等。文本表示是文本聚類的第一步，該步驟的變化很多，對最終聚類效果的影響也不盡相同。文本表示本質上是對原始文本進行轉換，使之在機器上可形式化描述、可計算。特征定義與篩選可以采用不同的特征選擇方法，可利

18、用N-Gram、PAT樹提取特征、可利用LSI降維轉化特征、也可利用語義詞典WordNet或者HowNet定義更復雜的特征結構。關于特征定義與篩選可以參考自然語言處理領域中的相關研究，這里不詳細介紹。本節接下來主要介紹信息檢索和文本分析處理中經常用到的幾個檢索模型，這幾個檢索模型根據不同的理論假設推導、定義了不同的特征權重計算方法與語義相似度計算方法，是文本表示模型的重要組成部分。2.2.1布爾模型布爾模型是基于集合論與布爾代數之上的一種簡單模型，主要應用于信息檢索中。在布爾模型中，一個文檔表示成文檔中出現的特征的集合，也可以表示成為特征空間上的一個向量，向量中每個分量權重為0或者1，這種布爾

19、模型稱為經典布爾模型。經典布爾模型中查詢與文檔的相關性只能是0或者1，滿足查詢query中的所有邏輯表達式的文檔被判定相關，不滿足的被判定為不相關。經典布爾模型只能用于信息檢索中計算用戶查詢與文檔的相關性，而無法利用該模型計算兩個文檔更深層面的相似度，無法在更多的文本處理應用中使用。在經典布爾模型基礎上，研究人員又提出了擴展布爾模型(Extended Boolean Approach)，重新定義了And與Or操作符成為多元操作符，使相關性可以成為0,1之間的數。2.2.2向量空間模型 Salton教授提出的向量空間模型簡稱VSM模型(Vector Space Model)，是信息檢索領域中經典

20、的檢索模型。向量空間模型將文檔表示成一個向量，向量的每一維表示一個特征，這個特征可以是一個字、一個詞、一個n-gram或某個復雜的結構。通過對文檔的解析處理可以得到這些特征。通常情況下用向量空間模型中的向量表示文檔時，需要對文檔進行切分(中文分詞、英文通過詞的分界符識別單詞)、停用詞處理、英文詞的詞形還原或者提取詞干(Stemming)，經過若干個處理步驟后，基本上就可以得到一系列詞，將這些詞作為文檔的特征。所有的這些詞構成一個“空間”，每個詞對應著空間中的一維。每個文檔可以用文檔中的詞來表示，這些詞及其對應的權重構成一個向量。文檔對應特征空間中的一個向量，對應特征空間中的一個點。表2.1 說

21、明VSM模型中文檔與向量空間之間的映射關系。表2.1 VSM模型中文檔與向量空間之間的映射關系2.3 文本相似度計算文本相似度計算是自然語言處理、Web智能檢索、文本分類和文本聚類研究中的一個基本問題。一個文本聚類分析過程的質量取決于對度量標準的選擇。因此，在研究聚類算法之前，先要討論其度量標準。文本相似度是用來衡量文本之間相似程度大小的一個統計量。文本相似度一般定義為界于0和1之間的一個值。如果兩文本之間相似度為1，則說明這兩個文本對象完全相同；反之，則說明兩文本沒有相似之處。2.3.1樣本間相似度在向量空間模型中，文本相似性的度量方法很多，主要有內積法、Dice系數法、余弦法和距離度量法等

22、。1.內積法通常在文本向量中，最常使用的相似度計算公式就是兩個文本向量之間的“內積”運算，其定義為：2.Dice系數法3.余弦法上述各公式中，Sim(di,dj)表示文本di和dj之間的相似程度，分Wki,Wkj分別表示文本di和dj的第k個特征項的權重，n為文本特征項數。Sim值越大表示兩個文本越相似，Sim越小則表示兩個文本區別越大。4.距離度量法在文本相似度計算中，我們也可以用兩個文本之間的距離來度量文本之間的相似程度。常使用的距離公式如下：公式中，Dis(di,dj)表示文本向量di和dj在向量空間的距離，Wki,Wkj分別表示文本的第k個特征項的權重，參數p決定了選擇的是哪種距離計算

23、。(1) 當p=1時(2) 當p=2時這就是歐式距離，也就是向量空間中的直線距離。2.3.2簇間相似度在聚類分析中，我們還需要衡量類與類之間的相似度，實現類與類之間的合并或拆分。為了衡量文本集合之間的相似度，常見的方法有：最小距離、最大距離、平均距離、質心法、離差平方和等。2.4文本聚類算法聚類分析作為一個活躍的研究領域，已經出現了很多聚類算法，總體上聚類算法可分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網格的方法等。每種算法都有各自的優缺點，都有其適用的領域，并不是每一類算法都適合于文本聚類，我們必須根據文本數據的特點對聚類算法進行分析選擇。2.4.1基于劃分的方法基于劃分的聚類

24、算法（Partitioning Method）是文本聚類應用中最為普遍的算法。方法將數據集合分成若干個子集，它根據設定的劃分數目k選出k個初始聚類中心，得到一個初始劃分，然后采用迭代重定位技術，反復在k個簇之間重新計算每個簇的聚類中心，并重新分配每個簇中的對象，以改進劃分的質量。使得到的劃分滿足“簇內相似度高，簇間相似度小”的聚類原則。典型的劃分聚類方法有k-means算法36和k-medoids算法，兩者的區別在于簇代表點的計算方法不同。前者使用所有點的均值來代表簇，后者則采用類中某個數據對象來代表簇。為了對大規模的數據集進行聚類，以及處理復雜形狀的聚類，各類改進的劃分算法逐漸增多?；趧澐?/p>

25、方法的優點是運行速度快，但該方法必須事先確定k的取值。算法容易局部收斂，且不同的初始聚類中心選取對聚類結果影響較大。為此，應用最廣泛的k-means算法有很多變種，他們可能在初始k個聚類中心的選擇、相似度的計算和計算聚類中心等策略上有所不同，最終實現聚類結果改進的目標。2.4.2基于層次的方法基于層次的聚類算法（Hierarchical Method）又叫“分級聚類算法”或“樹聚類”，它通過分解給定的數據對象集來創建一個層次。這種聚類方法有兩種基本的技術途徑：一是先把每個對象看作一個簇，然后逐步對簇進行合并，直到所有對象合為一個簇，或滿足一定條件為止；二是把所有對象看成一類，根據一些規則不斷選

26、擇一個簇進行分解，直到滿足一些預定的條件，如類的數目達到了預定值，或兩個最近簇的距離達到閾值等。前者稱為自下而上的凝聚式聚類，后者稱為自上而下的分裂式聚類。在文本聚類中，最常見的是凝聚的層次聚類算法。使用該算法可以得到較好的聚類結果，而且該方法無需用戶輸入參數；但是層次聚類算法的時間復雜度比較高，達到了O(n2)，對于大規模的文本集合，有其不適用性。此外，在層次聚類算法中，一旦兩個簇在凝聚和分裂后，這個過程將不能被撤銷，簇之間也不能交換對象。如果某一步沒有很好的選擇要凝聚或者分裂的簇，將會導致低質量的聚類結果。2.4.3基于密度的方法絕大多數劃分算法都是基于對象之間的距離進行聚類，這類方法只能

27、發現圓形或球狀的簇，較難發現任意形狀的簇。為此，提出了基于密度的聚類算法（Density-Based Clustering Method），其主要思想是：只要鄰近區域的對象或數據點的數目超過某個閾值，就繼續聚類。即對給定類中的每個數據點，在一個給定范圍的區域中至少包含某個數目的點，這樣就能很好的過濾掉“噪聲”數據，發現任意形狀的簇。其基本出發點是，尋找低密度區域分離的高密度區域。具有代表性的方法是DBSCAN（Density Based Spatial Clustering of Applications withNoise），它是將密度足夠大的那部分記錄組成類，可以在帶有“噪聲”的空間數據庫

28、中發現任意形狀的聚類，但它需要用戶主觀來選擇參數，從而影響了最終的聚類結果。基于密度的聚類算法在當前的文獻中較少被用于文本聚類中。這是由于文本間的相似度不穩定，同屬一簇的文本，有些文本間的相似度較高，所以密度高；有些相似度較低，所以密度低。如果根據全局的密度參數進行判斷，顯然是不適合的。并且密度單元的計算復雜度大，需要建立空間索引來降低計算量，且對數據維數的伸縮性較差。2.4.4基于網格的方法基于網格的算法（Grid-Based Clustering Method）把對象空間量化為有限數目的單元，形成了一個網絡結構。所用的聚類操作都在整個網絡結構即量化的空間上進行。這種方法的一個突出的優點就是

29、處理速度很快，其處理時間獨立于數據對象的數目，只與量化空間中的每一維的單元數目有關。此外，它還可以處理高維數據。代表算法有統計信息網格法STING算法、聚類高維空間法CLIQUE算法、基于小波變換的聚類法WAVE-CLUSTER算法。STING（Statistical Information Grid），利用了存儲在網格中的統計信息，它不但能并行處理且能增量更新，因而效率很高，缺點是簇的質量和精確性欠佳。WaveCluster（Clustering Using Wavelet Transformation）是一種多分辨率的聚類算法。其主要優點是能有效地處理大規模數據集；能發現任意形狀的簇；能成

30、功地處理孤立點；對于輸入的順序不敏感；不要求指定任何參數；且效率和聚類質量都比較高。CLIQUE（Clustering in Quest）是一種將基于密度的方法與基于網格的方法相結合的算法，能有效處理大型數據庫的高維數據。它對輸入順序不敏感，無需假設任何規范的數據分布。另外，它還具有良好的可伸縮性。但由于方法大大簡化，聚類結果的精確可能降低。2.4.5基于模型的方法基于模型的算法（Model-Based Clustering Method）試圖優化給定的數據和某些數學模型之間的適應性。這樣的算法經常是基于這樣的假設，數據是根據潛在的概率分布生成的。它通過為每個聚類假設一個模型來發現符合相應模型

31、的數據對象。根據標準統計方法并綜合考慮“噪聲”或異常數據，該方法可以自動確定聚類個數，從而得到魯棒性較好的聚類方法。基于模型的算法主要有兩類，分別為統計學方法和神經網絡方法。大多數的概念聚類采用的是統計的方法，即在決定一個類時，用可能性的描述語句，典型的代表就是COBWEB，它是一個通用且簡單的聚類方法?；谏窠浘W絡的聚類方法是將每一個類看作一個標本，它是這個類型的“典型”，但不需要和某個具體的對象或例子相對應。根據新對象和這個標本之間的距離，就可以將這個對象進行分類了。如基于SOM的文檔聚類方法在數字圖書館等領域得到了較好的應用。聚類分析算法眾多，應用于文檔的聚類分析算法也種類繁多，如何評價

32、文檔聚類分析的效果，目前還沒有一個確定的說法。在實際的應用中一般都是實現幾種算法，然后用人工判斷的方法去選擇合適的算法以及算法相對應的參數。這么多的算法雖然帶來了更多的選擇，但同時也帶來了應用上的困難，因此有必要在一個統一的尺度上來衡量一些算法并對他們做出評價。2.5本章小結本章主要介紹了影響文本聚類結果的三方面主要因素：文本表示模型、相似度計算方法及聚類算法。文本聚類過程中每個步驟都有可能影響最終的聚類效果，各方面因素變化情形眾多，在實際研究和工程應用中，聚類評價工作困難重重。為了更好地評價聚類結果，我們在下一章將詳細介紹已有的文本聚類評價方法，比較各自的優缺點。第三章 k-均值聚類算法3.

33、1 K-均值聚類算法的思想3.1.1 K-均值聚類算法的基本思想一九六七年，麥克奎因B. Mac Queen提出了K-均值聚類算法，用來處理數據聚類的問題，該種算法由于其算法簡便，又很早提出，因此在科學和工業領域的應用中影響力極為廣泛。該算法首先隨機選取k個數據點作為n個簇的初始簇中心，集合中每個數據點被劃分到與其距離最近的簇中心所在的類簇之中，形成了k個聚類的初始分布。對分配完的每一個類簇計算新的簇中心，然后繼續進行數據分配過程，這樣迭代若干次后，若簇中心不再發生變化，則說明數據對象全部分配到自己所在的類簇中，聚類準則函數收斂，否則繼續進行迭代過程，直至收斂。這里的聚類準則函數一般采用聚類誤

34、差平方和準則函數。本算法的一個特點就是在每一次的迭代過程中都要對全體數據點的分配進行調整，然后重新計算簇中心，進入下一次的迭代過程，若在某一次迭代過程中，所有數據點的位置沒有變化，相應的簇中心也沒有變化，此時標志著聚類準則函數已經收斂，算法結束。3.1.2 K-均值聚類算法的算法流程原始的K-均值聚類算法:輸入:數據集x=x1，x2，xn，聚類數目k;輸出: k個類簇cj，j=1，2，kstepl令I=1，隨機選取k個數據點作為k個類簇的初始簇中心，mj(I) j=1，2，k;step2計算每一個數據點與這k個簇中心的距離d(xi，mj，(i), i=1，2，n，j=1，2，k，,如果滿足d(

35、xi，mj(I)=mind(xi， mj(I)，j=1，2，k則xi cj.steP3計算k個新的聚類中心step4判斷:若mj(i+1) mj(I)，j=1，2，k，則I=i+1，返回step2:否則，算法結束。K-均值聚類算法在執行過程中還可以加入聚類準則函數來終止迭代過程，一般采用聚類誤差平方和準則函數，即在上面算法流程中的step4中計算聚類誤差平方和J，然后加入判斷，若兩次的J值沒有明顯變化，則說明J值已經收斂，結束算法，否則轉入step2繼續執行。具體流程如下:Stepl初始化l隨機指定k個聚類中心(ml，m2，mk);Step2分配xi對每一個樣本xi，找到離它最近的聚類中心，并

36、將其分配到該類: Step3修正簇中心重新計算各簇中心Step4計算偏差 Step5收斂判斷如果J值收斂，則return(m1， m2，mk)，算法終止;否則，轉Step2。從上面的算法思想及流程中可以看出，k個類簇的初始簇中心點的選取對聚類的最終結果至關重要，算法中，每一次迭代都把數據點劃分到與其距離最近的簇中心所在的類簇中去，然后重新計算簇中心，進而反復迭代，直到每一個數據點都不再重新劃分為止。3.1.3 K-均值算法的優缺點分析K-均值算法是一種基于劃分的聚類算法，它通過不斷的迭代過程來進行聚類，當算法收斂到一個結束條件時就終止迭代過程，輸出聚類結果。由于其算法思想簡便，又容易實現，因此

37、K-均值算法己成為一種目前最常用的聚類算法之一。然而K-means過分依賴于初始中心點的選取，且容易受噪音點的影響。為解決這一問題，出現了各種基于全局最優化思想的K-均值聚類方法，比如模擬退火算法、遺傳算法等。然而這些技術并沒有得到廣泛認可，在許多實際應用中還是反復利用K-均值聚類算法來解決問題。K-均值聚類算法采用迭代式的過程對樣本點進行分配來尋求最終的聚類結果，其終止條件是所有樣本的位置不再變化，其迭代過程可以概括如下:(l)分配樣本點，即對每個樣本點，將其分配到與其距離最近的簇中心所在的類簇中;(2)重新計算簇中心，對于每一個重新分配后的類簇，重新計算其簇中心。和大多數的聚類算法一樣，K

38、-均值聚類算法也有其自身的局限，主要局限如下:(1)K-均值聚類算法中的聚類數目即K值需要由用戶預先給出。從K-均值聚類算法的算法流程中可以看出，K值作為一個需要預先確定的參數，在已知的前提下才能執行K-均值聚類算法，而在實際應用中，需要聚類的數據究竟要分成多少個類別，往往不是被用戶所知的。當聚類數目不被人所知的情況下，人們往往需要結合其它算法來獲取聚類數目，即K值。往往獲取K值的代價要比K-均值聚類算法的代價大得多，因此K值的不確定性是K-均值聚類算法的一個很大的不足之處。(2)K-均值聚類算法嚴重依賴于初始簇中心點的選取。K-均值聚類算法隨機的選取K個初始簇中心點，并針對這K個簇中心點進行

39、迭代運算，即重新分配數據點和重新計算簇中心的運算，直到所有的數據點位置不再變化或聚類誤差準則函數不再變化。這樣就導致了K-均值聚類算法對初始簇中心點的嚴重依賴性。初始簇中心點選取不當很容易造成聚類結果陷入局部最優解甚至或導致錯誤的聚類結果。(3)K-均值聚類算法的聚類結果容易受噪音點數據的影響。在K-均值聚類算法中，每次對于簇中心的重新計算，都是通過對每一個類簇中所有數據點求均值，這樣，當數據集中存在噪音點數據時，均值點的計算將導致聚類中心(即簇中心偏離數據真正密集的區域，而趨向噪音點數據歹這樣導致聚類結果的不準確。因此，當數據集中存在遠離所有數據點的噪音點時，聚類結果將很大程度上受這些噪音點

40、的影響，導致聚類結果的錯誤，所以K-均值聚類算法對噪聲點和孤立點非常敏感。(4)K-均值聚類算法無法發現任意形狀的簇。K-均值聚類算法采用距離函數作為度量數據點間相似度的方法，這里的距離函數多采用歐氏距離，同時采用聚類誤差平方和準則函數作為聚類準則函數，對于基于歐式距離的聚類算法而言，其只能發現數據點分布較均勻的類球狀簇，對于聚類誤差平方和準則函數而言，當類簇大小差別較大，形狀較不規則時，容易造成對較大的類簇進行分割來達到目標函數取極小值的目的，因此容易造成錯誤的聚類結果。(5)K-均值聚類算法不適用于大數據量的聚類問題。K-均值聚類算法每次迭代過程都要調整簇中心及重新分配數據點，因此，當數據

41、量比較大的時候，這些迭代過程的計算量是相當大的，算法的時間開銷也是巨大的，因此，由于需要大量的計算時間，因此K-均值聚類算法在待聚類數據量較大的時候并不適用。3.1.4現有的對于K-均值聚類算法的改進目前，對于K-均值聚類算法的改進主要集中在以下兩個方面:(1)初始聚類中心的選擇K-均值聚類算法是一個迭代的求解最優解的問題，這里的最優解一般指的是目標函數(即聚類誤差和準則函數)的最優解，是一個優化問題。然而，作為聚類誤差和準則函數，通常存在一些局部最小點，目標函數的搜索方向總是沿著聚類誤差和準則函數的遞減方向進行，當初始簇中心不同時，搜索路徑也會不同，而目標函數具有很多局部最優解，這樣就存在著

42、，當初始簇中心選取不當時，目標函數容易陷入局部最優解。而K-均值聚類算法采取隨機選取初始簇中心點，這樣，初始中心點的不同或數據輸入順序的不同都有可能導致聚類結果的不穩定性，且無法得到全局最優解而陷入局部最優解。(2)K值的確定問題K-均值聚類算法中，K值是由用戶預先確定的，而在實際應用中，這個K值很難直接確定，尤其是當數據量較大時，K值的確定問題將成為K一均值聚類算法的一個很大的困難，因為在多數情況下人們并不能提前預知數據的分布情況及分類情況。而K-均值聚類算法的聚類結果受K值的影響，K值不同時，聚類結果往往也隨著不同，很多方法是通過試探K值來達到獲取K值的目的，而在數據量較大時，這種方法并不

43、行得通，需要大量的時間代價，因此，為了得到確定的聚類結果，K值的確定顯得尤為重要。因此，在無監督情況下，通過某種學習方法得到合適的K值是很有必要的。基于K-均值聚類算法的改進，國內外的專家學者做了大量的研究工作，主要總結如下。3.1.5現有基于初始中心點改進的K-均值聚類算法目前的K-均值聚類算法中，對于初始聚類中心點的選取方法主要總結如下:(1)隨機選取k個樣本作為初始聚類中心，由于是最早提出的這種選擇初始聚類中心點的方法，因此在后來的很多文獻中把這種隨機選擇初始聚類中心的方法稱為FA(ForgyAPProach)。(2)按最大最小距離聚類法中尋找聚類中心的方法來確定K-均值聚類算法中的初始

44、聚類中心。(3)將全部樣本以某種規則直觀的分成k類，分別計算每一類的均值點作為K-均值聚類算法的初始聚類中心。(4)采用基于數據采樣的方法。分別選取K組采樣數據分別執行K-均值聚類算法，然后選擇聚類結果最好的一組聚類中心作為算法的初始聚類中心點。 (5)通過“密度法”選擇代表點作為初始聚類中心。這里所指的密度是指樣本點分布的密集情況，描述為，對于所有的樣本，、將每個樣本點假設為中心，設定一個半徑，則落入這個半徑所在圓內的所有樣本點的數目即為該樣本點的密度值，在計算完所有樣本點的密度值后，選取最大密度值的樣本點作為第一個初始聚類中心，然后將該樣本點及其半徑所在圓內的數據點去除后，重新設定半徑選取

45、下一個初始中心點，以此類推，直到得到K個初始中心點。(6)聚類問題解出k類問題的中心。算法思路如下:先將全部樣本點看成是一個類簇的聚類問題，執行K-均值聚類算法后得到的簇中心即為一個類簇的聚類問題的最佳解，然后選取與現有簇中心距離最遠的點作為下一個類簇的初始簇中心，以此類推，確定出K個類簇的初始聚類中心。(7)進行多次初始值的選擇、聚類、找出一組最優的聚類結果。(8)采用遺傳算法或者免疫規劃方法lv1進行混合聚類。除了以上列出的初始中心點的選取方法以外，還有很多對K-均值聚類算法的初始中心點的改進算法，在這里由于篇幅的關系我們沒有一一列出。3.2 本章小結本章詳細的闡述了k-均值聚類算法的算法

46、思想及算法流程，并且詳細的提出了該算法的優點以及存在的問題。同時也對k-means算法的改進有兩種方法一是：現有的對于K-均值聚類算法的改進，二是：現有基于初始中心點改進的K-均值聚類算法。第四章 SOM聚類算法4.1 SOM聚類算法的網絡特性與基本流程4.1.1 SOM網絡的特性神經細胞模型中還存在著一種細胞聚類的功能柱。它是由多個細胞聚合而成的，在接受外界刺激后，它們會自動形成。一個功能柱中的細胞完成同一種功能。生物細胞中的這種現象在SOM網絡模型中有所反應。當外界輸入不同的樣本到SOM網絡中，一開始輸入樣本引起輸出興奮的位置各不相同，但通過網絡自組織后會形成一些輸出群，它們分別代表了輸入

47、樣本的分布，反映了輸入樣本的圖形分布特征，所以SOM網絡常常被稱為特性圖。SOM網絡是輸入樣本通過競爭學習后，功能相同的輸入靠得比較近，不同的分得比較開，以此將一些無規則的輸入自動排開，在連接權的調整過程中，使權的分布與輸入域可逐步縮小，使區域的劃分越來越明顯。在這種情況下，不論輸入樣本是多少維的，都可投影到低維的數據空間的某個區域上。這種形式也成為數據壓縮。同時，如果高維空間比較相近的樣本，則在低維空間中的投影也比較接近，這樣就可以從中取出樣本空間中較多的信息。遺憾的是，網絡在高維映射到低維時會發生畸變，而且壓縮比越大，畸變越大;另外網絡要求的輸入神經元數很大，因而SOM網絡比其他人工神經網

48、絡(比如BP網絡)的規模要大。樣本的概率密度分布相似。所以SOM網絡可以作為一種樣本特征檢測器，在樣本排序、樣本分類以及樣本檢測方面有廣泛的應用。一般可以這樣說，SOM網絡的權矢量收斂到所代表的輸入矢量的平均值，它反映了輸入數據的統計特性。再擴大一點，如果說一般的競爭學習網絡能夠訓練識別出輸入矢量的點特征，那么SOM網絡能夠表現輸入矢量在線上或平面上的分布特征。當隨機樣本輸入到SOM網絡時，如果樣本足夠多，那么在權值分布上可近似于輸入隨機樣本的概率密度分布，在輸出神經元上也反映了這種分布，即概率大的樣本集中在輸出空間的某一個區域，如果輸入的樣本有幾種分布類型，則它們各自會根據其概率分布集中到輸

49、出空間的各個不同的區域。每一個區域代表同一類的樣本.4.1.2 SOM網絡聚類的基本流程步驟1:初始化連接權值，學習率a。，鄰域半徑Nbo.步驟2:取樣對所有輸入樣本執行步驟3一步驟6.步驟3:確定獲勝神經元。如果采用歐氏距離，計算連接權向量與輸入樣本之間的距離，選擇值最小的神經元是獲勝神經元。步驟4:更新獲勝神經元及其鄰域內所有神經元的連接權值，而鄰域外的神經元的連接權值保持不變。步驟5:參數調整。調整學習率和鄰域半徑，為了保證算法的收斂，學習率的取值一般在O到1之間，且隨著學習代數的增加而遞減;鄰域半徑也隨著學習代數的增加而遞減，最后只有獲勝結點在學習步驟6:返回步驟2，直至算法收斂或達到

50、最大迭代次數為為止。4.1.3 SOM網絡聚類的優點及存在的問題(l) SOM神經網絡在聚類方面有如下優點:無須用戶指定聚類數目，網絡通過學習過程自適應地確定聚類數目;因其采用“勝者全得”的學習策略，對噪音數據不敏感;具有可視化的優點;它采用的鄰域學習策略能使數據從高維映射到低維時保持其拓撲結構不變，輸出層神經元連接權矢量的空間分布能正確地反應輸入模式的空間概率分布;因此，SOM網絡不但能學習到輸入模式的類別特征，而且能夠學習到輸入模式在原始空間中的拓撲結構特征和概率分布，從而具備可視化的優點。(2)無導師學習現在發展的還不成熟，傳統SOM網絡在文本聚類領域的應用還存在著許多的不足:網絡輸出層

51、結點的初始結構需要用戶預先給出;輸出層結點的初始拓撲結構與輸入模式在在原始數據空間中的拓撲結構一致時，網絡才會達到好的學習效果。但是由于文本數據高維性的特點，人們很難預先給出與原始數據空間中相一致的網絡輸出層拓撲結構。網絡訓練時，有些輸出層神經元的連接權值與輸入模式相差很大，始終不能獲勝，成為“死神經元”;其權值得不到任何學習訓練的機會，進而影響文本聚類的粒度和識別的精度。相反有些神經元因為獲勝次數過多，出現神經元過度利用的問題，也會影響網絡的學習效果。網絡輸出層神經元連接權的初始值影響聚類速度;因為文本數據的高維性，網絡學習一次花費時間較多。隨機確定輸出層神經元連接權的初始值，會引起網絡達到

52、收斂的學習次數過多，影響文本聚類的速度。4.2改進的SOM聚類方法4.2.1已有的學習策略改進就具體的學習策略來說，自組織特征映射神經網絡采用的是“勝者全得”的競爭學習算法，就是在競爭學習時網絡的各輸出神經元相互競爭，最后只有一個最強神經元獲勝;只有獲勝節點才允許有輸出，且輸出為1，其余節點輸出為0。這種學習策略存在如下兩個問題:(l)網絡訓練時，有些輸出層神經元的連接權值與輸入模式相差很大，始終不能獲勝，成為“死神經元”，其權值得不到任何學習訓練的機會;(2)相反有些神經元因為獲勝次數過多，出現神經元過度利用的問題。近年來，有些學者針對神經元欠利用和過度利用的問題，提出了許多改進的學習策略，

53、代表性的有SOM-CV、SOM-C、ESOM、TASOM、DSOM。(1)SOM-CV該種方法把SOM網絡的權值都初始化為l/m(m是輸入向量的維數)，每個輸入向量xj要經過如下修正后再輸入網絡。(2)SOM-C即帶“良心”的競爭學習SOM，它的基本思想是給每個競爭層結點設置一個闡值，每次使競爭獲勝的神經元的閩值增加，使經常獲勝的神經元獲勝的機會減小。(3)ESOM把更新獲勝結點Z及其領域結點的權值修改。(4)TASOM該種學習策略中，每個神經元都有自己的學習率和鄰域函數，并且能 根據學習時間自動地調整學習率和鄰域的大小。(5)DSOM該種學習策略是把內源性一氧化氮(NO)的四維動態擴散特性和

54、其在長時間學習過程中的增強作用應用到SOM中，輸入向量X輸入網絡后，以某種規則(評價函數)確定競爭層中一組獲勝神經元，稱為亞興奮神經元簇。并把每一個亞興奮神經元作為NO的擴散源。然后計算各亞興奮神經元所處位置的NO濃度，則NO濃度最高的神經元為最終獲勝單元。以上算法對神經元的獲勝策略進行了改進，在一定程度上解決了神經元欠利用和過度利用的問題，可以得到較好質量的聚類結果。但是聚類沒有以類內離差最小一平均類內相似度最大為基礎，很難保證可以得到使平均類內離差最小一平均類內相似度最大的聚類結果。本文借鑒學習矢量量化中等失真度的原則，針對文本聚類問題，把文本聚類追求的目標一平均類內離差最小即平均類內相似

55、度最大考慮進去，提出了一種改進的學習策略，該算法把等離差理論引入神經網絡的學習過程中，通過調整類內離差來指導神經網絡的學習，以使得聚類結果的平均類內離差最小:不僅解決了神經元欠利用和過度利用的問題，而且大大提高了文本聚類的結果質量。4.2.2等離差理論在神經元獲勝策略中的應用改進(l)文本聚類的目標函數基于劃分的聚類器的基本思想是:一個K階的聚類器把輸入空間分成K個小空間S1，S2，Sk，每個小空間S代表一個類別，每個小空間S內的聚類中心用z。來表示。(2)等類內離差原則聚類問題的實質就是求出適當s和z，使總類內離差D(s)最小。通常稱使總類內離差最小的聚類器為最優聚類器。最優聚類器的必要條件

56、是指最近鄰條件和質心條件。(3)改進算法的基本流程根據等類內離差準則，希望所有分割區域的類內離差相等，即要求所有的D(S、)(i，2，K)相等。所以，本文把等類內離差準則引入到SOM算法的學習策略中，在爭學習的過程中，將決定那個神經元獲勝的策略加以修改，定義新的距離測度為:d(x1，x 2)=d(x，z)D(S)顯然當D(s)增加時，d(x，Z)隨之增加，這就減少了神經元2.獲勝的可能性，最終結果將導致所有區域的類內離差趨于相等。這樣不僅解決了神經元欠利用問題，而且使各連接權值在表征輸入空間數據分布時得到了更有效的利用，使得量化的總類內離差接近最小，從而得到最優的聚類結果。EDSOM算法的基本

57、步驟可描述如下:步驟1：初始化連接權值w，學習率。鄰域半徑Nb。，對于輸出層每個神經元結點的類內離差初始化為D(s。)=1步驟2: 取樣。對所有輸入樣本執行步驟3一步驟6步驟3: 確定獲勝神經元。如果采用歐氏距離，按連接權向量與輸入樣本之間的距離值最小的神經元是獲勝神經元。步驟4: 更新按更新獲勝神經元及其鄰域內所有神經元的連接權值，而鄰域外的神經元的連接權值保持不變。步驟5: 參數調整。調整學習率和鄰域半徑，為了保證算法的收斂，學習率的取值一般在0到1之間，且隨著學習代數的增加而遞減;鄰域半徑也隨著學習代數的增加而遞減，最后只有獲勝結點在學習。步驟6: 更新每個輸出層神經元結點的類內離差。若輸出層神經元結點對應的輸入空間區域非空，則更新類內離差。步驟7: 返回步驟2，直至算法收斂或達到最大迭代次數為為止。4.2.3初始化連接權值初始權的設置，對于網絡的收斂狀況和收斂速度都是有影響的。不同的初始權，在其它條件相同的情況下，可能達到不同的輸出方差水平。人工神經網絡學習，如同其它優化技術一樣，初始權設置的好壞，也會影響到收斂的程度。一般說來，初始權值設置不當，有可能造成在某一局部極小值