【正文】 取聚類數(shù)目，即K值。和大多數(shù)的聚類算法一樣，K均值聚類算法也有其自身的局限，主要局限如下:(1)K均值聚類算法中的聚類數(shù)目即K值需要由用戶預先給出。K均值聚類算法采用迭代式的過程對樣本點進行分配來尋求最終的聚類結果，其終止條件是所有樣本的位置不再變化，其迭代過程可以概括如下:(l)分配樣本點，即對每個樣本點，將其分配到與其距離最近的簇中心所在的類簇中。為解決這一問題，出現(xiàn)了各種基于全局最優(yōu)化思想的K均值聚類方法，比如模擬退火算法、遺傳算法等。由于其算法思想簡便，又容易實現(xiàn)，因此K均值算法己成為一種目前最常用的聚類算法之一。從上面的算法思想及流程中可以看出，k個類簇的初始簇中心點的選取對聚類的最終結果至關重要，算法中，每一次迭代都把數(shù)據(jù)點劃分到與其距離最近的簇中心所在的類簇中去，然后重新計算簇中心，進而反復迭代，直到每一個數(shù)據(jù)點都不再重新劃分為止。[Step2][分配xi]對每一個樣本xi，找到離它最近的聚類中心，并將其分配到該類: [Step3][修正簇中心]重新計算各簇中心[Step4][計算偏差] [Step5][收斂判斷]如果J值收斂，則return(m1， m2，……，mk)，算法終止。K均值聚類算法在執(zhí)行過程中還可以加入聚類準則函數(shù)來終止迭代過程，一般采用聚類誤差平方和準則函數(shù)，即在上面算法流程中的step4中計算聚類誤差平方和J，然后加入判斷，若兩次的J值沒有明顯變化，則說明J值已經(jīng)收斂，結束算法，否則轉(zhuǎn)入step2繼續(xù)執(zhí)行。輸出: k個類簇cj，j=1，2，……，k[stepl]令I=1，隨機選取k個數(shù)據(jù)點作為k個類簇的初始簇中心，mj(I) j=1，2，…，k。本算法的一個特點就是在每一次的迭代過程中都要對全體數(shù)據(jù)點的分配進行調(diào)整，然后重新計算簇中心，進入下一次的迭代過程，若在某一次迭代過程中，所有數(shù)據(jù)點的位置沒有變化，相應的簇中心也沒有變化，此時標志著聚類準則函數(shù)已經(jīng)收斂，算法結束。對分配完的每一個類簇計算新的簇中心，然后繼續(xù)進行數(shù)據(jù)分配過程，這樣迭代若干次后，若簇中心不再發(fā)生變化，則說明數(shù)據(jù)對象全部分配到自己所在的類簇中，聚類準則函數(shù)收斂，否則繼續(xù)進行迭代過程，直至收斂。第三章 k均值聚類算法 K均值聚類算法的思想 K均值聚類算法的基本思想一九六七年，麥克奎因[B. Mac Queen]提出了K均值聚類算法，用來處理數(shù)據(jù)聚類的問題，該種算法由于其算法簡便，又很早提出，因此在科學和工業(yè)領域的應用中影響力極為廣泛。文本聚類過程中每個步驟都有可能影響最終的聚類效果，各方面因素變化情形眾多，在實際研究和工程應用中，聚類評價工作困難重重。這么多的算法雖然帶來了更多的選擇，但同時也帶來了應用上的困難，因此有必要在一個統(tǒng)一的尺度上來衡量一些算法并對他們做出評價。聚類分析算法眾多，應用于文檔的聚類分析算法也種類繁多，如何評價文檔聚類分析的效果，目前還沒有一個確定的說法。根據(jù)新對象和這個標本之間的距離，就可以將這個對象進行分類了。大多數(shù)的概念聚類采用的是統(tǒng)計的方法，即在決定一個類時，用可能性的描述語句，典型的代表就是COBWEB，它是一個通用且簡單的聚類方法。根據(jù)標準統(tǒng)計方法并綜合考慮“噪聲”或異常數(shù)據(jù)，該方法可以自動確定聚類個數(shù)，從而得到魯棒性較好的聚類方法。這樣的算法經(jīng)常是基于這樣的假設，數(shù)據(jù)是根據(jù)潛在的概率分布生成的。但由于方法大大簡化，聚類結果的精確可能降低。它對輸入順序不敏感，無需假設任何規(guī)范的數(shù)據(jù)分布。其主要優(yōu)點是能有效地處理大規(guī)模數(shù)據(jù)集；能發(fā)現(xiàn)任意形狀的簇；能成功地處理孤立點；對于輸入的順序不敏感；不要求指定任何參數(shù)；且效率和聚類質(zhì)量都比較高。STING（Statistical Information Grid），利用了存儲在網(wǎng)格中的統(tǒng)計信息，它不但能并行處理且能增量更新，因而效率很高，缺點是簇的質(zhì)量和精確性欠佳。此外，它還可以處理高維數(shù)據(jù)。所用的聚類操作都在整個網(wǎng)絡結構即量化的空間上進行。并且密度單元的計算復雜度大，需要建立空間索引來降低計算量，且對數(shù)據(jù)維數(shù)的伸縮性較差。這是由于文本間的相似度不穩(wěn)定，同屬一簇的文本，有些文本間的相似度較高，所以密度高；有些相似度較低，所以密度低。具有代表性的方法是DBSCAN（Density Based Spatial Clustering of Applications withNoise），它是將密度足夠大的那部分記錄組成類，可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類，但它需要用戶主觀來選擇參數(shù)，從而影響了最終的聚類結果。即對給定類中的每個數(shù)據(jù)點，在一個給定范圍的區(qū)域中至少包含某個數(shù)目的點，這樣就能很好的過濾掉“噪聲”數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。絕大多數(shù)劃分算法都是基于對象之間的距離進行聚類，這類方法只能發(fā)現(xiàn)圓形或球狀的簇，較難發(fā)現(xiàn)任意形狀的簇。此外，在層次聚類算法中，一旦兩個簇在凝聚和分裂后，這個過程將不能被撤銷，簇之間也不能交換對象。在文本聚類中，最常見的是凝聚的層次聚類算法。這種聚類方法有兩種基本的技術途徑：一是先把每個對象看作一個簇，然后逐步對簇進行合并，直到所有對象合為一個簇，或滿足一定條件為止；二是把所有對象看成一類，根據(jù)一些規(guī)則不斷選擇一個簇進行分解，直到滿足一些預定的條件，如類的數(shù)目達到了預定值，或兩個最近簇的距離達到閾值等。為此，應用最廣泛的kmeans算法有很多變種，他們可能在初始k個聚類中心的選擇、相似度的計算和計算聚類中心等策略上有所不同，最終實現(xiàn)聚類結果改進的目標?；趧澐址椒ǖ膬?yōu)點是運行速度快，但該方法必須事先確定k的取值。前者使用所有點的均值來代表簇，后者則采用類中某個數(shù)據(jù)對象來代表簇。使得到的劃分滿足“簇內(nèi)相似度高，簇間相似度小”的聚類原則。基于劃分的聚類算法（Partitioning Method）是文本聚類應用中最為普遍的算法。聚類分析作為一個活躍的研究領域，已經(jīng)出現(xiàn)了很多聚類算法，總體上聚類算法可分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法等。在聚類分析中，我們還需要衡量類與類之間的相似度，實現(xiàn)類與類之間的合并或拆分。常使用的距離公式如下：公式中，Dis(di,dj)表示文本向量di和dj在向量空間的距離，Wki,Wkj分別表示文本的第k個特征項的權重，參數(shù)p決定了選擇的是哪種距離計算。Sim值越大表示兩個文本越相似，Sim越小則表示兩個文本區(qū)別越大。在向量空間模型中，文本相似性的度量方法很多，主要有內(nèi)積法、Dice系數(shù)法、余弦法和距離度量法等。文本相似度一般定義為界于0和1之間的一個值。因此，在研究聚類算法之前，先要討論其度量標準。 VSM模型中文檔與向量空間之間的映射關系 文本相似度計算文本相似度計算是自然語言處理、Web智能檢索、文本分類和文本聚類研究中的一個基本問題。文檔對應特征空間中的一個向量，對應特征空間中的一個點。所有的這些詞構成一個“空間”，每個詞對應著空間中的一維。通過對文檔的解析處理可以得到這些特征。 Salton教授提出的向量空間模型簡稱VSM模型(Vector Space Model)，是信息檢索領域中經(jīng)典的檢索模型。經(jīng)典布爾模型只能用于信息檢索中計算用戶查詢與文檔的相關性，而無法利用該模型計算兩個文檔更深層面的相似度，無法在更多的文本處理應用中使用。在布爾模型中，一個文檔表示成文檔中出現(xiàn)的特征的集合，也可以表示成為特征空間上的一個向量，向量中每個分量權重為0或者1，這種布爾模型稱為經(jīng)典布爾模型。本節(jié)接下來主要介紹信息檢索和文本分析處理中經(jīng)常用到的幾個檢索模型，這幾個檢索模型根據(jù)不同的理論假設推導、定義了不同的特征權重計算方法與語義相似度計算方法，是文本表示模型的重要組成部分。特征定義與篩選可以采用不同的特征選擇方法，可利用NGram、PAT樹提取特征、可利用LSI降維轉(zhuǎn)化特征、也可利用語義詞典WordNet或者HowNet定義更復雜的特征結構。文本表示是文本聚類的第一步，該步驟的變化很多，對最終聚類效果的影響也不盡相同。特征提取包括特征的定義和篩選，特征定義和篩選考慮以什么作為文本的特征，并不是所有的詞和字都要求或者可以成為特征。文本表示包括兩個問題：表示與計算。在實際的文本聚類分析研究，將實際文本內(nèi)容變成機器內(nèi)部表示結構的方法多種多樣，可以用詞、字、短語、nGram、顯著性短語等形成向量、樹等結構。從這三個步驟可以看出影響文本聚類分析效果的因素包括四個方面：文本表示模型、距離度量方法、算法模型和參數(shù)優(yōu)化。該步驟還有一個關鍵因素就是對象距離(或者相似度)如何定義；(3)第三個步驟是算法中參數(shù)的選擇。目前在文獻中出現(xiàn)的聚類分析算法數(shù)目眾多，但在文本數(shù)據(jù)上效果孰優(yōu)孰劣仍沒有得到有效的研究。不同的算法有不同的特性，對相同的數(shù)據(jù)輸入，不同的算法會產(chǎn)生出不同的聚類結果。不論是抽取文本特征形成一個向量還是抽取文本特征形成一個特殊的結構，對文本的這種機器表示過程簡稱為文本表示。下面通過簡要描述聚類分析過程來說明對結果可能造成影響的各種因素,如圖21所示:圖21 聚類流程聚類分析過程分成三個步驟，通過這三個步驟可以找到影響聚類分析效果四個方面的因素。有了文本聚類分析的科學評價機制，我們未來的工作就有據(jù)可依，可以更科學地選擇算法，分析、設計算法。由于算法種類眾多，文本聚類算法間缺乏一個進行橫向比較與分析的機制，在工程實踐中對算法的選擇及參數(shù)的設定都是經(jīng)驗性的，這對進一步開展研究以及科學地設計算法、分析算法造成了困難。話題檢測中利用文檔聚類算法從大量的文檔中自動地抽取話題，應用于個性化信息服務或者情報分析。文檔聚類分析算法被用于自動產(chǎn)生文檔集合的層次結構，比如用于產(chǎn)生類似Yahoo!的網(wǎng)頁分類目錄結構。上個世紀90年代以來，文本的聚類分析技術研究更多地集中在對大規(guī)模的文檔集合的瀏覽上在對用戶提出的查詢重新組織搜索引擎的查詢結果的研究中利用聚類技術重新組織文檔集合，用于文檔集合的瀏覽，這是近年來文本聚類中一個廣受關注的研究點，2004年SIGIR上MSRA推出的Search Result Clustering技術代表了此類應用研究目前最新的進展。文本聚類分析在信息檢索領域有相當長的研究歷史，近年來在文本數(shù)據(jù)上的聚類分析研究和應用越來越受到關注。通過聚類分析可以發(fā)現(xiàn)隱藏在數(shù)據(jù)集中的簇，標識出有意義的模式或分布。在這一過程中無需指導，是一種典型的無需督分類，從而打破了在許多實際應用中由于缺少形成模式類別過程的知識，或者模式類別的形成非常困難時的挖掘局限性。文本聚類是根據(jù)文本數(shù)據(jù)的不同特征，按照事物間的相似性，將其劃分為不同數(shù)據(jù)類的過程。文本挖掘可以對大量文檔集合的內(nèi)容進行總結，結構分析，分類，聚類，關聯(lián)分析，分布分析以及利用文檔進行趨勢預測等，目前已成為一項具有較大實用價值的關鍵技術，是組織和管理數(shù)據(jù)和知識的有力手段。面對互聯(lián)網(wǎng)時代龐雜無序的海量信息，智能高效地處理和深層次綜合利用信息離不開文本挖掘技術，國際上多個國家都抓緊投入文本挖掘技術的研究，以期能對“堆積如山”的信息進行有效的過濾，開發(fā)和利用，提取發(fā)現(xiàn)具有指導意義的知識。然而Internet的深入發(fā)展和搜索引擎日趨龐大，進一步凸現(xiàn)出海量信息和人們獲取所需信息能力的矛盾。作者簽名： 日期： 年 月 日導師簽名： 日期： 年 月 日指導教師評閱書指導教師評價：一、撰寫（設計）過程學生在論文（設計）過程中的治學態(tài)度、工作精神□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格學生掌握專業(yè)知識、技能的扎實程度□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格學生綜合運用所學知識和專業(yè)技能分析和解決問題的能力□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格研究方法的科學性；技術線路的可行性；設計方案的合理性□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格完成畢業(yè)論文（設計）期間的出勤情況□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格二、論文（設計）質(zhì)量論文（設計）的整體結構是否符合撰寫規(guī)范？□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格是否完成指定的論文（設計）任務（包括裝訂及附件）？□ 優(yōu) □