【文章內(nèi)容簡(jiǎn)介】 本上參數(shù)的好壞對(duì)結(jié)果的影響都比較顯著。從這三個(gè)步驟可以 看出影響文本聚類分析效果的因素包括四個(gè)方面：文本表示模型、距離度量方法、算法模型和參數(shù)優(yōu)化。參數(shù)的設(shè)定主觀性比較強(qiáng)，如何設(shè)定才是一個(gè)好的參數(shù)缺乏有效的方法，利用本文中實(shí)現(xiàn)的聚類算法包和聚類評(píng)價(jià)方法可以通過指標(biāo)的變化曲線圖尋找算法的最佳參數(shù) 。 文本表示模型 在實(shí)際的文本聚類分析研究，將實(shí)際文本內(nèi)容變成機(jī)器內(nèi)部表示結(jié)構(gòu)的方法多種多樣，可以用詞、字、短語、 nGram、 顯著性短語等形成向量、樹等結(jié)構(gòu)。在經(jīng)典的研究中通常利用特征 (Term，包括字、詞、詞組等 )的詞頻信息建立文本向量，通過文本向量與文本向量之間 的相似度來進(jìn)行聚類分析。 文本表示包括兩個(gè)問題：表示與計(jì)算。表示特指特征的提取，計(jì)算指權(quán)重的定義和語義相似度的定義。特征提取包括特征的定義和篩選，特征定義和篩選考慮以什么作為文本的特征，并不是所有的詞和字都要求或者可以成為特征。特征的權(quán)重定義及特征結(jié)構(gòu)上的相似度度量可以選取不同的模型，如向量空間模型、概率模型、語言模型等。文本表示是文本聚類的第一步，該步驟的變化很多，對(duì)最終聚類效果的影響也不盡相同。文本表示本質(zhì)上是對(duì)原始文本進(jìn)行轉(zhuǎn)換，使之在機(jī)器上可形式化描述、可計(jì)算。特征定義與篩選可以采用不同的特征選擇方法 ，可利用 NGram、 PAT 樹提取特征、可利用 LSI 降維轉(zhuǎn)化特征、也可利用語義詞典基于文本的聚類算法研究 5 WordNet 或者 HowNet 定義更復(fù)雜的特征結(jié)構(gòu)。關(guān)于特征定義與篩選可以參考自然語言處理領(lǐng)域中的相關(guān)研究，這里不詳細(xì)介紹。本節(jié)接下來主要介紹信息檢索和文本分析處理中經(jīng)常用到的幾個(gè)檢索模型，這幾個(gè)檢索模型根據(jù)不同的理論假設(shè)推導(dǎo)、定義了不同的特征權(quán)重計(jì)算方法與語義相似度計(jì)算方法，是文本表示模型的重要組成部分。 布爾模型 布爾模型是基于集合論與布爾代數(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)典布爾模型只能用于信息檢索中計(jì)算用戶查詢與文檔的相關(guān)性，而無法利用該模型計(jì)算兩個(gè)文檔更深層面的相似度，無法在更多的文本處理應(yīng)用中使用。在經(jīng)典布爾模型基礎(chǔ)上，研究人員又提出了擴(kuò)展布爾模型 (Extended Boolean Approach)，重新定義了 And與 Or 操 作符成為多元操作符，使相關(guān)性可以成為 [0,1]之間的數(shù)。 向量空間模型 Salton 教授提出的向量空間模型簡(jiǎn)稱 VSM 模型 (Vector Space Model)，是信息檢索領(lǐng)域中經(jīng)典的檢索模型 。 向量空間模型將文檔表示成一個(gè)向量，向量的每一維表示一個(gè)特征，這個(gè)特征可以是一個(gè)字、一個(gè)詞、一個(gè) ngram或某個(gè)復(fù)雜的結(jié)構(gòu)。通過對(duì)文檔 的解析處理可以得到這些特征。通常情況下用向量空間模型中的向量表示文檔時(shí)，需要對(duì)文檔進(jìn)行切分 (中文分詞、英文通過詞的分界符識(shí)別單詞 )、停用詞處理、英文詞的詞形還原或者提取詞干 (Stemming)，經(jīng)過若干個(gè)處理步驟后，基本上就可以得到一系列詞，將這些詞作為文檔的特征。所有的這些詞構(gòu)成一個(gè)“空間”，每個(gè)詞對(duì)應(yīng)著空間中的一維。每個(gè)文檔可以用文檔中的詞來表示，這些詞及其對(duì)應(yīng)的權(quán)重構(gòu)成一個(gè)向量。文檔對(duì)應(yīng)特征空間中的一個(gè)向量，對(duì)應(yīng)特征空間中的一個(gè)點(diǎn)。 表 說明 VSM 模型中文檔與向量空間之間的映射關(guān)系。 基于文本的聚類算法研究 6 表 VSM模型中文檔與向量空間之間的映射關(guān)系 文本 相似度計(jì)算 文本相似度計(jì)算是自然語言處理、 Web 智能檢索、文本分類和文本聚類研究中的一個(gè)基本問題。一個(gè)文本聚類分析過程的質(zhì)量取決于對(duì)度量標(biāo)準(zhǔn)的選擇。因此，在研究聚類算法之前，先要討論其度量標(biāo)準(zhǔn)。文本相似度是用來衡量文本之間相似程度大小的一個(gè)統(tǒng)計(jì)量。文本相似度一般定義為界于 0 和 1 之間的一個(gè)值。如果兩文本之間相似度為 1，則說明這兩個(gè)文本對(duì)象完全相同；反之，則說明兩文本沒有相似之處。 樣本間相似度 在向量空間模型中，文本相似 性的度量方法很多，主要有內(nèi)積法、 Dice 系數(shù)法、余弦法和距離度量法等。 通常在文本向量中，最常使用的相似度計(jì)算公式就是兩個(gè)文本向量之間的“內(nèi)積”運(yùn)算，其定義為： 系數(shù)法 弦法 基于文本的聚類算法研究 7 上述各公式中， Sim(di,dj)表示文本 di 和 dj 之間的相似程度，分 Wki,Wkj分別表示文本 di 和 dj 的第 k 個(gè)特征項(xiàng)的權(quán)重， n 為文本特征項(xiàng)數(shù)。 Sim值越大表示兩個(gè)文本越相似， Sim越小則表示兩個(gè)文本區(qū)別越大。 在文本相似度計(jì)算中，我們也可以用兩個(gè)文本之間的距離來度量文本之間 的相似程度。常使用的距離公式如下： 公式中， Dis(di,dj)表示文本向量 di 和 dj 在向量空間的距離， Wki,Wkj分別表示文本的第 k 個(gè)特征項(xiàng)的權(quán)重，參數(shù) p 決定了選擇的是哪種距離計(jì)算。 (1) 當(dāng) p=1 時(shí) (2) 當(dāng) p=2 時(shí) 這就是歐式距離，也就是向量空間中的直線距離。 簇間相似度 在聚類分析中，我們還需要衡量類與類之間的相似度，實(shí)現(xiàn)類與類之間的合并或拆分。為了衡量文本集合之間的相似度，常見的方法有：最小距離、最大距離、平均距離、質(zhì)心法、離差平方和等。 基于文本的聚類算法研究 8 文本聚類算法 聚類分析作為一個(gè)活躍的研究 領(lǐng)域，已經(jīng)出現(xiàn)了很多聚類算法，總體上聚類算法可分為基于劃分的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法等。每種算法都有各自的優(yōu)缺點(diǎn)，都有其適用的領(lǐng)域，并不是每一類算法都適合于文本聚類，我們必須根據(jù)文本數(shù)據(jù)的特點(diǎn)對(duì)聚類算法進(jìn)行分析選擇。 基于劃分的方法 基于劃分的聚類算法（ Partitioning Method）是文本聚類應(yīng)用中最為普遍的算法。方法將數(shù)據(jù)集合分成若干個(gè)子集，它根據(jù)設(shè)定的劃分?jǐn)?shù)目 k 選出 k 個(gè)初始聚類中心，得到一個(gè)初始劃分，然后采用迭代重定位技術(shù)，反復(fù)在 k 個(gè)簇之間重新計(jì)算每個(gè)簇的 聚類中心，并重新分配每個(gè)簇中的對(duì)象，以改進(jìn)劃分的質(zhì)量。使得到的劃分滿足“簇內(nèi)相似度高，簇間相似度小”的聚類原則。典型的劃分聚類方法有 kmeans 算法 [36]和 kmedoids 算法，兩者的區(qū)別在于簇代表點(diǎn)的計(jì)算方法不同。前者使用所有點(diǎn)的均值來代表簇，后者則采用類中某個(gè)數(shù)據(jù)對(duì)象來代表簇。為了對(duì)大規(guī)模的數(shù)據(jù)集進(jìn)行聚類，以及處理復(fù)雜形狀的聚類，各類改進(jìn)的劃分算法逐漸增多。 基于劃分方法的優(yōu)點(diǎn)是運(yùn)行速度快，但該方法必須事先確定 k 的取值。算法容易局部收斂，且不同的初始聚類中心選取對(duì)聚類結(jié)果影響較大。為此，應(yīng)用最廣泛 的 kmeans 算法有很多變種，他們可能在初始 k 個(gè)聚類中心的選擇、相似度的計(jì)算和計(jì)算聚類中心等策略上有所不同，最終實(shí)現(xiàn)聚類結(jié)果改進(jìn)的目標(biāo)。 基于層次的方法 基于層次的聚類算法（ Hierarchical Method）又叫“分級(jí)聚類算法”或“樹聚類”，它通過分解給定的數(shù)據(jù)對(duì)象集來創(chuàng)建一個(gè)層次。這種聚類方法有兩種基本的技術(shù)途徑：一是先把每個(gè)對(duì)象看作一個(gè)簇，然后逐步對(duì)簇進(jìn)行合并，直到所有對(duì)象合為一個(gè)簇，或滿足一定條件為止；二是把所有對(duì)象看成一類，根據(jù)一些規(guī)則不斷選擇一個(gè)簇進(jìn)行分解，直到滿足一些預(yù)定的條件 ，如類的數(shù)目達(dá)到了預(yù)定基于文本的聚類算法研究 9 值，或兩個(gè)最近簇的距離達(dá)到閾值等。前者稱為自下而上的凝聚式聚類，后者稱為自上而下的分裂式聚類。 在文本聚類中，最常見的是凝聚的層次聚類算法。使用該算法可以得到較好的聚類結(jié)果，而且該方法無需用戶輸入?yún)?shù)；但是層次聚類算法的時(shí)間復(fù)雜度比較高，達(dá)到了 O(n2)，對(duì)于大規(guī)模的文本集合，有其不適用性。此外，在層次聚類算法中，一旦兩個(gè)簇在凝聚和分裂后，這個(gè)過程將不能被撤銷，簇之間也不能交換對(duì)象。如果某一步?jīng)]有很好的選擇要凝聚或者分裂的簇，將會(huì)導(dǎo)致低質(zhì)量的聚類結(jié)果。 基于密度的方法 絕大多 數(shù)劃分算法都是基于對(duì)象之間的距離進(jìn)行聚類，這類方法只能發(fā)現(xiàn)圓形或球狀的簇，較難發(fā)現(xiàn)任意形狀的簇。為此，提出了基于密度的聚類算法（ DensityBased Clustering Method），其主要思想是：只要鄰近區(qū)域的對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目超過某個(gè)閾值，就繼續(xù)聚類。即對(duì)給定類中的每個(gè)數(shù)據(jù)點(diǎn)，在一個(gè)給定范圍的區(qū)域中至少包含某個(gè)數(shù)目的點(diǎn)，這樣就能很好的過濾掉“噪聲”數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。其基本出發(fā)點(diǎn)是，尋找低密度區(qū)域分離的高密度區(qū)域。具有代表性的方法是 DBSCAN（ Density Based Spatial Clustering of Applications with Noise），它是將密度足夠大的那部分記錄組成類，可以在帶有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類，但它需要用戶主觀來選擇參數(shù)，從而影響了最終的聚類結(jié)果。 基于密度的聚類算法在當(dāng)前的文獻(xiàn)中較少被用于文本聚類中。這是由于文本間的相似度不穩(wěn)定，同屬一簇的文本，有些文本間的相似度較高，所以密度高；有些相似度較低，所以密度低。如果根據(jù)全局的密度參數(shù)進(jìn)行判斷，顯然是不適合的。并且密度單元的計(jì)算復(fù)雜度大，需要建立空間索引來降低計(jì)算量，且對(duì)數(shù)據(jù)維數(shù)的伸縮性 較差。 基于網(wǎng)格的方法 基于網(wǎng)格的算法（ GridBased Clustering Method）把對(duì)象空間量化為有限數(shù)目的單元，形成了一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)。所用的聚類操作都在整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)即量化的空間基于文本的聚類算法研究 10 上進(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 算法、基于小波變換的聚類法 WAVECLUSTER 算法。 STING（ Statistical Information Grid），利用了存儲(chǔ)在網(wǎng)格中的統(tǒng)計(jì)信息，它不但能并行處理且能增量更新，因而效率很高，缺點(diǎn)是簇的質(zhì)量和精確性欠佳。 WaveCluster（ Clustering Using Wavelet Transformation）是一種多分辨率的聚類算法。其主要優(yōu)點(diǎn)是能有效地處理大規(guī)模數(shù)據(jù)集；能發(fā)現(xiàn)任意形狀的簇；能成功地處理孤立點(diǎn)；對(duì)于輸入的順序不敏感；不要求指定任何參數(shù)；且效率和聚類質(zhì)量都比較高。 CLIQUE（ Clustering in Quest）是一種將基于密度的方法與基于網(wǎng)格的方法相結(jié) 合的算法，能有效處理大型數(shù)據(jù)庫的高維數(shù)據(jù)。它對(duì)輸入順序不敏感，無需假設(shè)任何規(guī)范的數(shù)據(jù)分布。另外，它還具有良好的可伸縮性。但由于方法大大簡(jiǎn)化，聚類結(jié)果的精確可能降低。 基于模型的方法 基于模型的算法（ ModelBased Clustering Method）試圖優(yōu)化給定的數(shù)據(jù)和某些數(shù)學(xué)模型之間的適應(yīng)性。這樣的算法經(jīng)常是基于這樣的假設(shè)，數(shù)據(jù)是根據(jù)潛在的概率分布生成的。它通過為每個(gè)聚類假設(shè)一個(gè)模型來發(fā)現(xiàn)符合相應(yīng)模型的數(shù)據(jù)對(duì)象。根據(jù)標(biāo)準(zhǔn)統(tǒng)計(jì)方法并綜合考慮“噪聲”或異常數(shù)據(jù)，該方法可以自動(dòng)確定聚類個(gè)數(shù)，從 而得到魯棒性較好的聚類方法?；谀Ｐ偷乃惴ㄖ饕袃深悾謩e為統(tǒng)計(jì)學(xué)方法和神經(jīng)網(wǎng)絡(luò)方法。 大多數(shù)的概念聚類采用的是統(tǒng)計(jì)的方法，即在決定一個(gè)類時(shí)，用可能性的描述語句，典型的代表就是 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)用于文檔的聚類分析算法也種類繁多，基于文本的聚類算法研究 11 如何評(píng) 價(jià)文檔聚類分析的效果，目前還沒有一個(gè)確定的說法。在實(shí)際的應(yīng)用中一般都是實(shí)現(xiàn)幾種算法，然后用人工判斷的方法去選擇合適的算法以及算法相對(duì)應(yīng)的參數(shù)。這么多的算法雖然帶來了更多的選擇，但同時(shí)也帶來了應(yīng)用上的困難，因此有必要在一個(gè)統(tǒng)一的尺度上來衡量一些算法并對(duì)他們做出評(píng)價(jià)。 本章小結(jié) 本章主要介紹了影響文本聚類結(jié)果的三方面主要因素：文本表示模型、相似度計(jì)算方法及聚類算法。文本聚類過程中每個(gè)步驟都有可能影響最終的聚類效果，各方面因素變化情形眾多，在實(shí)際研究和工程應(yīng)用中，聚類評(píng)價(jià)工作困難重重。為了更好地評(píng)價(jià)聚類結(jié)果 ，我們?cè)谙乱徽聦⒃敿?xì)介紹已有的文本聚類評(píng)價(jià)方法，比較各自的優(yōu)缺點(diǎn)。 基于文本的聚類算法研究 12 第三章 k均值聚類算法 K均值聚類算法的思想 K均值聚類算法的基本思想 一九六七年，麥克奎因 [B. Mac Queen]提出了 K均值聚類算法，用來處理數(shù)據(jù)聚類的問題，該種算法由于其算法簡(jiǎn)便，又很早提出，因此在科學(xué)和工業(yè)領(lǐng)域的應(yīng)用中影響力極為廣泛。該算法首先隨機(jī)選取 k個(gè)數(shù)據(jù)點(diǎn)作為 n個(gè) 簇的初始簇中心，集合中每個(gè)數(shù)據(jù)點(diǎn)被劃分到與其距離最近的簇中心所在的類簇之中，形成了 k 個(gè)