【正文】 力極為廣泛。這么多的算法雖然帶來了更多的選擇，但同時也帶來了應(yīng)用上的困難，因此有必要在一個統(tǒng)一的尺度上來衡量一些算法并對他們做出評價。根據(jù)新對象和這個標(biāo)本之間的距離，就可以將這個對象進(jìn)行分類了。根據(jù)標(biāo)準(zhǔn)統(tǒng)計方法并綜合考慮“噪聲”或異常數(shù)據(jù)，該方法可以自動確定聚類個數(shù)，從而得到魯棒性較好的聚類方法。但由于方法大大簡化，聚類結(jié)果的精確可能降低。其主要優(yōu)點是能有效地處理大規(guī)模數(shù)據(jù)集；能發(fā)現(xiàn)任意形狀的簇；能成功地處理孤立點；對于輸入的順序不敏感；不要求指定任何參數(shù)；且效率和聚類質(zhì)量都比較高。此外，它還可以處理高維數(shù)據(jù)。并且密度單元的計算復(fù)雜度大，需要建立空間索引來降低計算量，且對數(shù)據(jù)維數(shù)的伸縮性較差。具有代表性的方法是DBSCAN（Density Based Spatial Clustering of Applications withNoise），它是將密度足夠大的那部分記錄組成類，可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類，但它需要用戶主觀來選擇參數(shù)，從而影響了最終的聚類結(jié)果。絕大多數(shù)劃分算法都是基于對象之間的距離進(jìn)行聚類，這類方法只能發(fā)現(xiàn)圓形或球狀的簇，較難發(fā)現(xiàn)任意形狀的簇。在文本聚類中，最常見的是凝聚的層次聚類算法。為此，應(yīng)用最廣泛的kmeans算法有很多變種，他們可能在初始k個聚類中心的選擇、相似度的計算和計算聚類中心等策略上有所不同，最終實現(xiàn)聚類結(jié)果改進(jìn)的目標(biāo)。前者使用所有點的均值來代表簇，后者則采用類中某個數(shù)據(jù)對象來代表簇?；趧澐值木垲愃惴ǎ≒artitioning Method）是文本聚類應(yīng)用中最為普遍的算法。在聚類分析中，我們還需要衡量類與類之間的相似度，實現(xiàn)類與類之間的合并或拆分。Sim值越大表示兩個文本越相似，Sim越小則表示兩個文本區(qū)別越大。文本相似度一般定義為界于0和1之間的一個值。 VSM模型中文檔與向量空間之間的映射關(guān)系 文本相似度計算文本相似度計算是自然語言處理、Web智能檢索、文本分類和文本聚類研究中的一個基本問題。所有的這些詞構(gòu)成一個“空間”，每個詞對應(yīng)著空間中的一維。 Salton教授提出的向量空間模型簡稱VSM模型(Vector Space Model)，是信息檢索領(lǐng)域中經(jīng)典的檢索模型。在布爾模型中，一個文檔表示成文檔中出現(xiàn)的特征的集合，也可以表示成為特征空間上的一個向量，向量中每個分量權(quán)重為0或者1，這種布爾模型稱為經(jīng)典布爾模型。特征定義與篩選可以采用不同的特征選擇方法，可利用NGram、PAT樹提取特征、可利用LSI降維轉(zhuǎn)化特征、也可利用語義詞典WordNet或者HowNet定義更復(fù)雜的特征結(jié)構(gòu)。特征提取包括特征的定義和篩選，特征定義和篩選考慮以什么作為文本的特征，并不是所有的詞和字都要求或者可以成為特征。在實際的文本聚類分析研究，將實際文本內(nèi)容變成機器內(nèi)部表示結(jié)構(gòu)的方法多種多樣，可以用詞、字、短語、nGram、顯著性短語等形成向量、樹等結(jié)構(gòu)。該步驟還有一個關(guān)鍵因素就是對象距離(或者相似度)如何定義；(3)第三個步驟是算法中參數(shù)的選擇。不同的算法有不同的特性，對相同的數(shù)據(jù)輸入，不同的算法會產(chǎn)生出不同的聚類結(jié)果。下面通過簡要描述聚類分析過程來說明對結(jié)果可能造成影響的各種因素,如圖21所示:圖21 聚類流程聚類分析過程分成三個步驟，通過這三個步驟可以找到影響聚類分析效果四個方面的因素。由于算法種類眾多，文本聚類算法間缺乏一個進(jìn)行橫向比較與分析的機制，在工程實踐中對算法的選擇及參數(shù)的設(shè)定都是經(jīng)驗性的，這對進(jìn)一步開展研究以及科學(xué)地設(shè)計算法、分析算法造成了困難。文檔聚類分析算法被用于自動產(chǎn)生文檔集合的層次結(jié)構(gòu)，比如用于產(chǎn)生類似Yahoo!的網(wǎng)頁分類目錄結(jié)構(gòu)。文本聚類分析在信息檢索領(lǐng)域有相當(dāng)長的研究歷史，近年來在文本數(shù)據(jù)上的聚類分析研究和應(yīng)用越來越受到關(guān)注。在這一過程中無需指導(dǎo)，是一種典型的無需督分類，從而打破了在許多實際應(yīng)用中由于缺少形成模式類別過程的知識，或者模式類別的形成非常困難時的挖掘局限性。文本挖掘可以對大量文檔集合的內(nèi)容進(jìn)行總結(jié)，結(jié)構(gòu)分析，分類，聚類，關(guān)聯(lián)分析，分布分析以及利用文檔進(jìn)行趨勢預(yù)測等，目前已成為一項具有較大實用價值的關(guān)鍵技術(shù)，是組織和管理數(shù)據(jù)和知識的有力手段。然而Internet的深入發(fā)展和搜索引擎日趨龐大，進(jìn)一步凸現(xiàn)出海量信息和人們獲取所需信息能力的矛盾。本人授權(quán)　　 　 　大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得 及其它教育機構(gòu)的學(xué)位或?qū)W歷而使用過的材料。本文首先介紹了文本聚類的相關(guān)的技術(shù)，包括文本聚類的過程，文本表示模型，相似度計算及常見聚類算法?；谖谋镜木垲愃惴ㄑ芯空? 要聚類作為一種知識發(fā)現(xiàn)的重要方法，它廣泛地與中文信息處理技術(shù)相結(jié)合，應(yīng)用于網(wǎng)絡(luò)信息處理中以滿足用戶快捷地從互聯(lián)網(wǎng)獲得自己需要的信息資源。整個聚類過程無需指導(dǎo)，事先對數(shù)據(jù)結(jié)構(gòu)未知，是一種典型的無監(jiān)督分類。關(guān)鍵詞：文本聚類 聚類方法 KMEAN SOM II AbstractClustering 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 resources 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 large 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 that 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 clustering algorithm to split and so on. Also studied the text clustering algorithm analysis and methods of improvement.Key words：Text clustering clustering method kmean som畢業(yè)設(shè)計（論文）原創(chuàng)性聲明和使用授權(quán)說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計（論文），是我個人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。作者簽名：　　 　 　　 日　 期：　　 　 　　 學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨立進(jìn)行研究所取得的研究成果。作者簽名： 日期： 年 月 日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。搜索引擎服務(wù)應(yīng)運而生，在一定程度上滿足了用戶查找信息的需要。文本挖掘是指從大量文本數(shù)據(jù)中抽取出事先未知的，可理解的，最終可用的信息或知識的過程，它涉及Web，計算機語言，數(shù)據(jù)挖掘，信息檢索等多個領(lǐng)域，較大程度地解決了信息雜亂的現(xiàn)象，方便用戶準(zhǔn)確地定位所需的信息和信息分流。其目的是使同一類別的文本間相似度盡可能大，而不同類別的文本間的相似度盡可能的小。不同算法針對與不同規(guī)模的數(shù)據(jù)集而提出，而使用卻不僅僅限于某些特定的環(huán)境。在此類研究中，主要利用KMeans或者后綴樹聚類算法的變種來實現(xiàn)其需求。在這些應(yīng)用的推動之下，文本數(shù)據(jù)上的聚類分析算法層出不窮，各說各的好處，在我們的工程實踐中具體該采用哪種算法，如何設(shè)計文本聚類算法并對其進(jìn)行評價都是難以解決的問題。 28 第二章 文本聚類效果影響因素影響文本聚類分析效果的因素是多方面的，文本聚類分析全過程中的每個步驟都有可能對聚類結(jié)果造成影響。文本表示過程顯然需要領(lǐng)域知識參與，文本中哪些因素可以構(gòu)成特征，特征中哪些在聚類中可用以及如何使用是文本聚類第一步驟文本表示考察的內(nèi)容；(2)文本聚類分析的第二個步驟是算法。這個步驟中算法的時空效率、聚類結(jié)果質(zhì)量是研發(fā)中選擇算法的主要標(biāo)準(zhǔn)。參數(shù)的設(shè)定主觀性比較強，如何設(shè)定才是一個好的參數(shù)缺乏有效的方法，利用本文中實現(xiàn)的聚類算法包和聚類評價方法可以通過指標(biāo)的變化曲線圖尋找算法的最佳參數(shù)。表示特指特征的提取，計算指權(quán)重的定義和語義相似度的定義。文本表示本質(zhì)上是對原始文本進(jìn)行轉(zhuǎn)換，使之在機器上可形式化描述、可計算。布爾模型是基于集合論與布爾代數(shù)之上的一種簡單模型，主要應(yīng)用于信息檢索中。在經(jīng)典布爾模型基礎(chǔ)上，研究人員又提出了擴展布爾模型(Extended Boolean Approach)，重新定義了And與Or操作符成為多元操作符，使相關(guān)性可以成為[0,1]之間的數(shù)。通常情況下用向量空間模型中的向量表示文檔時，需要對文檔進(jìn)行切分(中文分詞、英文通過詞的分界符識別單詞)、停用詞處理、英文詞的詞形還原或者提取詞干(Stemming)，經(jīng)過若干個處理步驟后，基本上就可以得到一系列詞，將這些詞作為文檔的特征。 說明VSM模型中文檔與向量空間之間的映射關(guān)系。文本相似度是用來衡量文本之間相似程度大小的一個統(tǒng)計量。通常在文本向量中，最常使用的相似度計算公式就是兩個文本向量之間的“內(nèi)積”運算，其定義為：上述各公式中，Sim(di,dj)表示文本di和dj之間的相似程度，分Wki,Wkj分別表示文本di和dj的第k個特征項的權(quán)重，n為文本特征項數(shù)。(1) 當(dāng)p=1時(2) 當(dāng)p=2時這就是歐式距離，也就是向量空間中的直線距離。每種算法都有各自的優(yōu)缺點，都有其適用的領(lǐng)域，并不是每一類算法都適合于文本聚類，我們必須根據(jù)文本數(shù)據(jù)的特點對聚類算法進(jìn)行分析選擇。典型的劃分聚類方法有kmeans算法[36]和kmedoids算法，兩者的區(qū)別在于簇代表點的計算方法不同。算法容易局部收斂，且不同的初始聚類中心選取對聚類結(jié)果影響較大。前者稱為自下而上的凝聚式聚類，后者稱為自上而下的分裂式聚類。如果某一步?jīng)]有很好的選擇要凝聚或者分裂的簇，將會導(dǎo)致低質(zhì)量的聚類結(jié)果。其基本出發(fā)點是，尋找低密度區(qū)域分離的高密度區(qū)域。如果根據(jù)全局的密度參數(shù)進(jìn)行判斷，顯然是不適合的。這種方法的