王賢明，潘佳玲，胡智文

(1.溫州理工學院數(shù)據(jù)科學與人工智能學院,溫州 325035;2.浙江工商大學計算機與信息工程學院,杭州 310018)

1 引言

在文本挖掘領域，文本聚類是一類常見而又重要的數(shù)據(jù)挖掘手段，同時也是很多其他挖掘操作的前置工作。顧名思義，聚類即按照某些特征和規(guī)則將整個數(shù)據(jù)集分成若干組的過程，各個組內元素在某些特征方面具有較高的相似性，而組間元素則在這些特征方面具有較大的差異性，所得到的各個組即為一個聚類，也常稱之為“簇”。聚類作為一種無監(jiān)督的機器學習方法，無需人工對數(shù)據(jù)進行標注和訓練，自動化程度高。目前已被廣泛應用于計算機科學、情報學、社會學、生物學等多個領域。隨著互聯(lián)網的高速發(fā)展，文本聚類在Web數(shù)據(jù)處理相關方面應用尤其廣泛，例如推薦系統(tǒng)、網絡輿情[1-2]、各類文本挖掘及相關應用[3-5]。

在諸多Web相關研究領域中，網絡輿情研究近年來發(fā)展很快，是一個兼具實用價值和學術價值的綜合性研究領域，被學術界和政府管理部門重視，吸引了計算機科學、情報學、社會學、新聞學、統(tǒng)計學等多個學科研究人員投入到相關研究中。在網絡輿情研究中，其中一個重要的研究方向即網絡輿情熱點的發(fā)現(xiàn)。由于網絡數(shù)據(jù)的海量性，導致網絡熱點的發(fā)現(xiàn)對聚類算法的實時性要求較高，計算資源消耗也大。不過正是由于網絡數(shù)據(jù)的海量性，一旦某個熱點產生后，圍繞該熱點的大量媒體數(shù)據(jù)將迅速發(fā)布并傳播開來，也就是說，由于相關熱點數(shù)據(jù)非常多，無需獲取其全部相關數(shù)據(jù)，而只需要獲取其中一部分數(shù)據(jù)，且保證這部分數(shù)據(jù)足夠“純”,即足夠分析出相關熱點，這是一種典型的準確率重要性遠大于召回率的情況。然而目前鮮有專門針對這種情況的聚類算法。

2 相關研究及問題

2.1 聚類方法

文本聚類的研究歷史悠久，取得了豐碩的成果，相關聚類方法層出不窮。目前，較為知名的文本聚類方法如劃分聚類、層次聚類、基于密度的聚類[6-7]等。近年來，基于語義的聚類[8-11]和深度學習的聚類[12-13]逐漸受到關注，尤其以后者更為明顯。同時也有不少混合型方法或集成聚類方法[14-17]。此外，也有一些適用于特殊場合的聚類方法，例如目前針對短文本的聚類[18-20]也獲得了不少關注。

在上述方法中，基本都需要特征項或詞支撐，并且不同的特征或特征組合效果是不同的[21-22]，因而決定了特征選擇[23-24]或降維[25-26]對聚類是一項重要的前置研究內容。對中文而言，往往離不開分詞的支持[27]，相應的分詞準確性問題也隨之而來，最終也將影響聚類的速度、準確率和召回率。

N-Gram是一種經典的統(tǒng)計語言模型，目前已被廣泛使用于各種各樣的文本應用場合[28-30]及非文本應用場合[31]。由于N-Gram的特點，因此可以應用于文本相似度的計算[32-33]。文獻[34]提出了一種基于N-Gram相似度算法的文本聚類方法，該方法無需分詞支持，對語言也無要求，速度和準確率可以方便地調控。其適用場景是：對準確率和速度要求較高，但對召回率要求次之。典型的應用如網絡輿情實時熱點發(fā)現(xiàn)。在輿情熱點發(fā)現(xiàn)過程中，對準確率和速度要求是必然的；熱點分析要求有一定量的相關主題文檔即可進行，并不要求識別得足夠全面，也就意味著對該聚類的召回率并無太高要求。不過該方法在聚類閾值相對較小時，初始聚類結果較為“粗糙”，且準確性也相對稍低，可能存在著將毫不相干的內容聚到同一個類中的弊端。

2.2 聚類的評估

文本聚類的評估較為困難，方法多樣。例如采用專家人工評估、熵（Entropy）評估、準確率、召回率、F-score等，其中尤以準確率、召回率最為普遍，它們評估的是每個單獨的聚類，且一般都盡量在這兩者間取得平衡。

由于在輿情熱點分析類似的應用過程中，往往會同時得到多個聚類，并且在該評估過程中，準確率的重要性遠高于召回率。本文基于實際需要和便利性，擬從當前的聚類評價指標構建綜合性的評估指標。

本文方法優(yōu)勢及創(chuàng)新點如下：

（1）相較于常規(guī)聚類方法，本文方法由于是基于NGram，避免了很多聚類方法中的分詞、特征提取等操作，同時具備語言無關性，而且也可以輕松地通過調整閾值實現(xiàn)對聚類速度、聚類精細程度等的調控。

（2）本文方法所得初始聚類的“內聚性”強，相應的，各個初始聚類的準確率高。因而最終聚類往往準確率也較高。

（3）定義了適合本文聚類方法的綜合評估指標。

3 方法及原理

3.1 應用于網絡輿情熱點發(fā)現(xiàn)的文本聚類方法

設原始文檔集個數(shù)為k，每個文檔集對應一個主題，文檔集分別記為D1={d11,d21,…,dn11}，D2=。實驗文檔集為上述文檔集的并集，在不必區(qū)分或者無法區(qū)分文檔的歸屬時，可將文檔集記為：D'={d'1,d'2,…,d'n}，其中，為文檔集中的文檔數(shù)。聚類過程中，文檔相似度采用文獻[32]中方法計算，相似度閾值為T,即若文檔相似度值不低于該值，則將這些文檔歸屬到一個類中。聚類中文檔數(shù)閾值為C，即若某個初始聚類中的文檔數(shù)不低于該值，則認定該初始聚類為一個有效聚類，否則舍棄。

聚類的主要流程如下圖1所示。

圖1 聚類過程

其中，上述flag變量既可以用于記錄初始聚類完畢時所得的聚類數(shù)，也可以用作各聚類的序號。S=Sim(di,dj)是文檔di和dj的相似度值，范圍為[0,100]。聚類完畢，根據(jù)flag值即可知所獲得的初始聚類個數(shù)，且每個初始聚類中最少元素個數(shù)為C。此處的初始聚類是指經過上述方法聚類后的直接聚類結果，以便和最終的聚類區(qū)分開。

經由上述方法聚類后，所得初始聚類結果可以直接用于類似網絡熱點識別之類的應用場景。倘若需將其聚類應用到其他更為廣泛的聚類場合，則需要對上述初始聚類結果執(zhí)行合并處理。所謂合并處理，即對各個初始聚類進行二次聚類。二次聚類可以通過兩種方式進行。第一種是準確性更好的方式，即將各個初始聚類視為一個整體來對待，例如計算各個初始聚類中文檔集的頻繁項集，該頻繁項集對應于該初始聚類，然后利用頻繁項集的方法[35]即可完成初始聚類的合并，亦即完成最終聚類。第二種是一種快捷的方式，即以各個初始聚類中的最長文檔作為該聚類的代表文檔，并對各個代表文檔進行聚類計算。若代表文檔聚為一類，則意味著其對應的初始聚類可以合并為一個大的聚類。一般情況下，采用第二種方式也可以取得較為滿意的結果。由于聚類的合并可以采用多種常規(guī)的聚類方法，因此不再贅述。

3.2 聚類覆蓋率

4 實驗及結果分析

4.1 實驗方案

為了便于比較，本文采用與文獻[34]相同的實驗數(shù)據(jù)、相似度計算參數(shù)和實驗方案，其中文獻[34]中方法記為DRGrams，本文方法記為AR-Grams。

4.2 實驗結果與分析

（1）聚類閾值與初始聚類數(shù)的關系

初始聚類數(shù)是利用AR-Grams進行聚類后的直接聚類結果，亦即未進行聚類合并之前的聚類情況。相關實驗結果如下圖2所示。

圖2 初始聚類數(shù)與閾值的關系

從圖2可見，當閾值較小時，獲得的初始聚類較少，隨著閾值的增大，所得初始聚類逐漸增多，當閾值增大到一定范圍時（對本例是[11,15]），聚類數(shù)呈現(xiàn)基本穩(wěn)定的狀態(tài)，但當閾值增到足夠大時，聚類數(shù)開始逐漸下降。

呈現(xiàn)上述現(xiàn)象的原因在于：當閾值較小時，閾值對不同聚類元素的辨識度有限，且相對較容易受到因采用隨機n-Grams相似度計算中的隨機性影響，因而更容易將本不該隸屬于一個類中的文檔聚到一起，從而最終獲得的聚類較少，容易推斷，此時的準確率也應該相對較低。當閾值逐漸增大時，閾值的辨識度逐漸增大，各文檔更容易被歸屬到其應該的聚類中，因而聚類相對更為準確，聚類數(shù)也就更多，這正是聚類數(shù)增多的原因。當閾值增大到一定范圍時，此時可以較為準確地劃分各個文檔的類別歸屬，并且由于此時聚到同類中的文檔確實是存在相當程度的重復，因而在閾值不是足夠大時，一定程度的閾值變化是不會有太大影響的。這正是聚類數(shù)存在一段相對穩(wěn)定區(qū)間的原因。并且，此階段各個聚類的大小相對更大，同時各個聚類的準確率基本維持在100%，該階段正是適合于用作類似于網絡熱點分析相關研究或應用的時機。隨著閾值的繼續(xù)增大，只有幾乎完全相同的文檔才會被聚到一個類當中，不過完全相同的文檔數(shù)畢竟有限，因而此時獲得的聚類數(shù)將開始逐漸降低。需要交代的是，此時得到的初始聚類其實較多，不過只是有些聚類太小，即元素數(shù)在閾值C之下，因而被過濾掉了，留下的有效初始聚類數(shù)在減少。

另外，對比AR-Grams和DR-Grams，可以發(fā)現(xiàn)兩者隨著閾值的變化趨勢相同，但在不同的閾值階段上，具體聚類數(shù)有所差異。在低閾值時，AR-Grams獲得的聚類相對更多，最為重要原因就在于AR-Grams在低閾值下聚類更為精細，不像DR-Grams聚類結果那么粗糙，因而獲得的聚類數(shù)更多，相應的，整體上各聚類更小。但隨著閾值的增大，閾值已能夠準確地進行聚類而不至出錯，因而兩種聚類方法在高閾值時的表現(xiàn)基本相同。

此外，當初始聚類數(shù)趨于穩(wěn)定時，意味著此時所對應的閾值T為較好的選擇。根據(jù)這一特征，可以實現(xiàn)聚類過程中聚類閾值T的自動化確定。

（2）聚類閾值與準確率、召回率及F-score的關系

準確率是經典的聚類評估指標，AR-Grams聚類準確率結果如下圖3所示。

圖3 聚類閾值與準確率的關系

與DR-Grams聚類一樣，閾值越小，各文檔歸屬出錯的可能性越大；閾值越大，各文檔歸屬出錯的可能性越小，聚類閾值對聚類結果起著決定性作用。對比AR-Grams和DRGrams結果可見，兩種方法所得結果的變化趨勢相同，即準確率隨著聚類閾值的增大而增大，直至為100%。并且在閾值T=11時，準確率已經接近100%，當閾值T≥15時，準確率幾乎已為100%。故從聚類準確率來看，聚類閾值在AR-Grams和DR-Grams下具備同樣的作用。在AR-Grams聚類下，相似度閾值范圍可初步確定在區(qū)間[11,17]。

針對各個單一數(shù)據(jù)集而言，在圖中，“饅頭”的準確率明顯低于其他數(shù)據(jù)集，原因在于文檔集D中的最小可聚類文檔來自于“饅頭”數(shù)據(jù)集，在AR-Grams聚類下，該文檔將首先成為聚類標志文檔，并將獲得最多的與其他文檔進行相似度計算的機會，因而也將納入更多的文檔到該類中，這就是“饅頭”的最低準確率的根本性原因。這一點，是ARGrams和DR-Grams的共同特性，即較先的可聚類標志文檔所在的聚類往往具備較低的準確率。不過隨著閾值的增大，該情況逐漸被改善。

與DR-Grams相比，AR-Grams聚類在低閾值（T≤9）時準確率提高了11.9%，在整體上則提高了4.5%。由此可見，AR-Grams在低閾值下的改進效果明顯。原因正如前文所述，低閾值下的DR-Grams聚類結果較為粗糙，而ARGrams結果則較為精細，精細的聚類結果其準確率必然高得多。實驗結果顯示AR-Grams下的聚類準確性整體高于DR-Grams，高閾值下的結果相當，因而可以認為AR-Grams優(yōu)于DR-Grams。

聚類評價的另外一個重要指標為召回率，AR-Grams聚類閾值與召回率關系的結果如下圖4所示。

圖4 聚類閾值與召回率的關系

對比兩種方法的召回率曲線可知，兩種方法下聚類閾值和召回率存在相同的關系，即隨著聚類閾值的增大，召回率呈現(xiàn)先增后降的態(tài)勢，并且最佳聚類閾值范圍為[9,11]。

和DR-Grams一樣，在聚類閾值較小時（T≤9），閾值作用歸結為“類間糾錯”，即閾值的增大，將逐漸減少文檔被歸屬錯誤的可能性。但當T逐漸增大時（T＞11），文檔的歸屬已基本完全正確，正如圖3中所示，T=11時的準確率已基本為100%，因而此后的閾值作用將主要體現(xiàn)為把各個聚類劃分為更為精細的、且準確率依然保持為100%的更多小聚類，亦即“類內細分”的作用。類內的細分一方面將會獲得更多稍小的聚類，同時又將使得較多過小的聚類被閾值C過濾或者一些單一的文件不被歸屬到任意聚類中，這正是召回率曲線下降的原因。

與DR-Grams相比，AR-Grams在低閾值下的召回率提高了9.1%，在整體上則提高了2.9%?？梢姳疚姆椒ㄔ诘烷撝禃r的改進作用明顯。

綜合性的評價指標F-score曲線如下圖5所示。

圖5 聚類閾值與F-score的關系

由圖5可見，在整體上，F(xiàn)-score曲線的升降趨勢與召回率一致，即先升后降。這一點與DR-Grams聚類一樣。但具體值方面，本文方法的F-scoce在低閾值時提高了10.2%，在整體上則提高了3.5%。這主要歸功于AR-Grams的精細特性，在造就更多精細聚類的同時，提高了聚類效果。

（3）聚類閾值和覆蓋率的關系

整體覆蓋率Ca和正確覆蓋率Cr實驗結果如圖6所示。

圖6 聚類閾值與覆蓋率的關系

由圖6可見：整體文檔覆蓋率隨著聚類閾值的增加呈現(xiàn)單調遞減趨勢，正確文檔覆蓋率則呈現(xiàn)先升后降的趨勢。顯然，隨著聚類閾值的增大，文檔將更難以聚到一起，或者難以聚成較大的類。由于各個聚類對納入該類文檔的限制更為嚴格，這將導致越來越多的文檔成為獨立于任何聚類的個體文檔，或者由于所含文檔過少而無法被認定為有效聚類，在宏觀上即呈現(xiàn)為整體文檔覆蓋率的持續(xù)下降。對正確文檔覆蓋率而言，則與上述情形有所不同。在閾值較小時，雖然絕大多數(shù)的文檔都被歸屬到相關聚類中，但是正如前文所述，低閾值時的歸屬錯誤率極高，這一問題隨著閾值的增大將逐漸緩解（即低閾值時閾值呈現(xiàn)為“類間糾錯”功能），這正是正確文檔覆蓋率在開始階段呈現(xiàn)增長趨勢的原因。在閾值較大時，由于閾值的“類內細分”作用，諸多大類被分割為多個細小的聚類甚至一些獨立的文檔，在該過程中，越來越多的獨立文檔和極其細小的聚類被排除在有效聚類之外，宏觀上即呈現(xiàn)為正確文檔覆蓋率的緩慢下降。這在另一個側面再次印證了前文所論述的閾值的兩種典型作用。當閾值增大到一定程度時，閾值已具備充分的辨識能力，可確保被歸屬到同一個類中的文檔在實際上也的確是同類文檔，此即當閾值較大時，兩條曲線基本重合的原因。

和DR-Grams相比，本文方法的正確覆蓋率提高了9.2%，在整體上則提高了3.0%，可見本文方法的主要效果表現(xiàn)在低閾值時對正確覆蓋率的提升上，主要原因與前文的聚類準確率相同，不再贅述。

（4）AR-Grams聚類特性及應用場景解釋

AR-Grams聚類方法的特性可總結為：高準確率、低召回率、聚類精度和速度易于調控。該方法可通過調整相似度計算中N-Gram的數(shù)目及各項閾值來實現(xiàn)聚類精度和速度的調控，故決定了其可用于實時性較高的場合也可用于精度要求較高的場合，但并不能用于召回率較高的場合。另外由于該方法可以獲取多個準確率高的聚類，通過其中的較大聚類即可完成類似網絡熱點發(fā)現(xiàn)之類的應用需求。這主要是由于在實際情況下，網絡熱點一旦產生，雖然圍繞著一個熱點話題的數(shù)據(jù)往往涉及多個方面，但其中往往存在著大量由于轉載或其他原因而導致有較大重復率的文檔。只要能把這些重復率較高的文檔識別出來，就足以分析出相關熱點，而并不需要識別出該熱點所有相關數(shù)據(jù)，這正是本文聚類方法具有實用價值的客觀支撐條件。本文聚類方法并不適用于類似于文獻[36]中的藝術類數(shù)據(jù)聚類（包含音樂、舞蹈、書畫等數(shù)據(jù)）。從本實驗的初步聚類結果來看(即在不進行聚類合并條件下的聚類結果)，雖然聚類數(shù)較多，但其中較大的聚類卻并不多，在實際進行網絡熱點分析時，只需利用其中的幾個較大聚類即可實現(xiàn)。另外，由于實現(xiàn)海量網絡數(shù)據(jù)中熱點的識別只需要能夠取得其中一個較大的且準確率高的聚類即可，至于該類中元素是多一些還是少一些，都不會影響熱點分析結果，這就決定了雖然本文方法仍然是基于閾值進行聚類的，但是卻對閾值要求卻很低，只需要閾值較大，例如在0.5以上，但不要高于0.9即可。

另外，雖然采用本文方法時，取較小的閾值能夠獲得較少的聚類，不過由于此時各聚類中包含了一定數(shù)量的歸屬錯誤的文檔，這些對熱點分析不利，故低閾值并不適合于進行熱點分析。

5 結束語

本文提出的AR-Grams的文本聚類方法，具有語言無關性、高準確率、低召回率、聚類精度和速度易于調控等特點，相較于常規(guī)聚類方法，省卻了繁瑣的特征提取等操作，同時也避免了DR-Grams聚類可能導致的將毫不相干的文檔聚到一個類中的缺陷，從而提高了低閾值下的準確率，因而也提高了F-score，相應的也提高了聚類的正確覆蓋率。這使得AR-Grams能在更廣的閾值范圍內應用于網絡話題檢測或者網絡熱點識別等場合。不過，在極低閾值時的聚類效果仍有待進行更為深入的研究。