大規(guī)模短文本的不完全聚類(lèi)

彭澤映，俞曉明，許洪波,劉春陽(yáng)

(1. 中國(guó)科學(xué)院 計(jì)算技術(shù)研究所，北京 100190； 2. 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029)

1 引言

聚類(lèi)分析[1](非監(jiān)督學(xué)習(xí))是數(shù)據(jù)挖掘中的一個(gè)重要領(lǐng)域。它將大量具有相同屬性的事物按照相似度分為各個(gè)組，進(jìn)而輔助人們從這些信息中抽取摘要或者發(fā)現(xiàn)新的規(guī)律。至今，聚類(lèi)分析已成功應(yīng)用于文本摘要、生物基因識(shí)別、電子商務(wù)客戶(hù)行為分析等眾多方面、取得了很好效果。

隨著這兩年Twitter帶來(lái)的新一波內(nèi)容風(fēng)潮，越來(lái)越多關(guān)注被投放到了一種早已廣泛存在的信息形式： 短文本。稱(chēng)之為短文本是因?yàn)檫@些信息都是一些很短的文本，一般字?jǐn)?shù)都不超過(guò)100。實(shí)際上，在Twitter風(fēng)靡之前，短文本就早已深入人們的網(wǎng)絡(luò)生活中，甚至可以說(shuō)是與網(wǎng)民最貼近的信息形式。搜索引擎中與用戶(hù)最相關(guān)的部分用戶(hù)查詢(xún)就是一種典型的短文本； “網(wǎng)絡(luò)固話(huà)”即時(shí)通訊軟件中的聊天對(duì)話(huà)基本都屬于短文本。除此之外，聊天室對(duì)話(huà)、新聞標(biāo)題、論壇標(biāo)題和SNS狀態(tài)信息等也都是短文本的棲息地。另外，人們?nèi)粘Ｉ钪械牡昧涣髦侄绦牛彩嵌涛谋镜木扌驮慈?/p>

短文本在傳遞公開(kāi)信息的同時(shí)攜帶了豐富的用戶(hù)信息，從而成為一種新的具有極大價(jià)值的信息資源，對(duì)于此類(lèi)數(shù)據(jù)的聚類(lèi)需求也凸現(xiàn)出來(lái)。

應(yīng)用場(chǎng)景一： 網(wǎng)絡(luò)熱點(diǎn)信息的發(fā)現(xiàn)。通過(guò)對(duì)網(wǎng)絡(luò)上的短文本信息進(jìn)行聚類(lèi)，可以挖掘網(wǎng)絡(luò)上的熱點(diǎn)信息，幫助用戶(hù)更好地獲取和理解網(wǎng)絡(luò)信息。

應(yīng)用場(chǎng)景二： 企業(yè)信息系統(tǒng)的改善。對(duì)即時(shí)通信數(shù)據(jù)進(jìn)行分析和挖掘?qū)τ谄髽I(yè)信息系統(tǒng)的組織和優(yōu)化具有重要作用。

應(yīng)用場(chǎng)景三： 關(guān)鍵信息的提取。政府或組織采集的民意調(diào)查數(shù)據(jù)包含了民眾對(duì)社會(huì)事件的看法、觀點(diǎn)等輿情信息。情報(bào)工作者需要對(duì)大量短語(yǔ)消息進(jìn)行采集和處理，以發(fā)現(xiàn)可疑的對(duì)話(huà)和人，通過(guò)監(jiān)測(cè)公共開(kāi)放聊天室的會(huì)話(huà)，利用聚類(lèi)技術(shù)可以自動(dòng)提取與違法行為相關(guān)的對(duì)話(huà)或行為模式。

至今，已有許多聚類(lèi)算法被相繼提出，但常用的文本聚類(lèi)算法如K-means等在短文本聚類(lèi)中效果不佳[2]。主要是因?yàn)槎涛谋疽话憔哂幸韵绿卣鳎?/p>

a. 形式不規(guī)范，趨向口語(yǔ)化。很多短文本都帶有很多口語(yǔ)化內(nèi)容和網(wǎng)絡(luò)流行語(yǔ)，還有一些使用變形字，如“我”變“額”。

b. 短文本特征信息很少，只有少量的字可以被分析使用。

c. 數(shù)量巨大，通常至少是百萬(wàn)級(jí)的。

d. 實(shí)時(shí)性要求較高，因?yàn)槎涛谋臼遣粩嗟漠a(chǎn)生的，而且信息更新很快，如Twitter上的信息，基本上每個(gè)小時(shí)都有熱點(diǎn)話(huà)題產(chǎn)生。

近幾年來(lái)也有一些專(zhuān)門(mén)針對(duì)短文本的聚類(lèi)算法被提出，代表性工作有： Wang等針對(duì)即時(shí)通信消息的聚類(lèi)提出了WR-Kmeans算法[2]，He等提出了一種基于中文塊的中文短文本聚類(lèi)方法[3]，黃永光等提出一種采用檢索思想的短文本聚類(lèi)算法[4]，賀濤等提出一種基于免疫的中文網(wǎng)絡(luò)短文本聚類(lèi)算法[5]，這些工作主要是針對(duì)上面提到的短文本的a、b特征進(jìn)行的研究，在一定程度上提高了短文本聚類(lèi)的效果，但并沒(méi)有在聚類(lèi)性能上做太大改進(jìn)。

而實(shí)際應(yīng)用中的短文本信息往往具有很大的數(shù)量，這些信息在短時(shí)間內(nèi)都可以達(dá)到上千萬(wàn)甚至過(guò)億的量級(jí)。以Twitter為例，Twitter每天產(chǎn)生的信息量可以達(dá)到6 500萬(wàn)條，且這個(gè)數(shù)量仍在不斷增加[6]。已有的針對(duì)短文本的聚類(lèi)方法在大規(guī)模數(shù)據(jù)上的處理性能往往達(dá)不到實(shí)際應(yīng)用的要求。

本文通過(guò)對(duì)實(shí)際應(yīng)用中的短文本信息進(jìn)行深入觀察和實(shí)驗(yàn)分析，發(fā)現(xiàn)這些大規(guī)模短文本的類(lèi)別具有“長(zhǎng)尾現(xiàn)象”，并據(jù)此提出一種新的不完全聚類(lèi)的思想，可以很大程度上解決聚類(lèi)的性能問(wèn)題。

2 背景知識(shí)

聚類(lèi)分析指將物理或抽象對(duì)象的集合分組成為由類(lèi)似的對(duì)象組成的多個(gè)類(lèi)的分析過(guò)程。常用的文本聚類(lèi)分析方法主要包括分割式聚類(lèi)法、層次聚類(lèi)法。本節(jié)對(duì)這兩種常用的聚類(lèi)算法加以介紹，并對(duì)它們?cè)诙涛谋揪垲?lèi)中的應(yīng)用進(jìn)行相關(guān)分析。

2.1 分割式聚類(lèi)法

分割式聚類(lèi)法的中心思想是： 通過(guò)不同的重分配策略不斷優(yōu)化已存在的類(lèi)別。分割式聚類(lèi)算法一般是迭代算法，在迭代的每一步對(duì)類(lèi)別進(jìn)行優(yōu)化。最典型的分割式算法是K-Means算法。

K-Means算法[7]是目前在科學(xué)和工業(yè)領(lǐng)域應(yīng)用最多最廣泛的聚類(lèi)算法，它的算法流程如下：

步驟1. 從所有數(shù)據(jù)對(duì)象中選取K個(gè)數(shù)據(jù)對(duì)象作為初始聚類(lèi)中心；

步驟2. 對(duì)其他數(shù)據(jù)對(duì)象，根據(jù)其與聚類(lèi)中心的距離，分配給各個(gè)類(lèi)別；

步驟3. 根據(jù)分配結(jié)果，取每個(gè)類(lèi)別所有數(shù)據(jù)的平均值，作為新的聚類(lèi)中心；

步驟4. 迭代運(yùn)行步驟2和步驟3，直到所有的聚類(lèi)中心不再發(fā)生變化。

K-Means算法具有流程簡(jiǎn)單直觀、復(fù)雜度低，效率高、算法易于并行等優(yōu)點(diǎn)。但同時(shí)該算法也存在以下一些固有缺陷：

a) 需要預(yù)先給定聚類(lèi)數(shù)目K，K的設(shè)定對(duì)算法結(jié)果影響較大；

b) 初始K個(gè)中心點(diǎn)的選擇對(duì)算法準(zhǔn)確度有較大影響；

c) 算法對(duì)outliers非常敏感。

對(duì)于短文本聚類(lèi)，短文本類(lèi)別數(shù)量巨大，類(lèi)簇的個(gè)數(shù)K難以預(yù)先給定，更不用說(shuō)K個(gè)初始中心點(diǎn)的選擇。另外，雖然K-Means聚類(lèi)算法相比于其他聚類(lèi)算法具有較高的效率，但對(duì)于巨大數(shù)量的短文本，K-Means迭代過(guò)程所需要的運(yùn)行時(shí)間通常也是難以接受的。

另一種常見(jiàn)的分割式聚類(lèi)法是K-Medoids算法。基本思路和K-Means是一樣的，不同的只是中心點(diǎn)的選擇策略，K-Medoids不是取所有點(diǎn)的平均值為中心點(diǎn)，而是取到類(lèi)別所有點(diǎn)距離和最小的樣本點(diǎn)作為中心點(diǎn)，這樣K-Medoids就可以用于處理K-Means無(wú)法適用的Category類(lèi)型數(shù)據(jù)。K-Medoids復(fù)雜度比K-Means還高，對(duì)于處理短文本性能同樣無(wú)法接受。

2.2 層次聚類(lèi)法

層次聚類(lèi)法[8]可以分為從上至下(分治)和從下至上(聚合)兩種方式。從上至下算法起初把所有點(diǎn)看成一個(gè)類(lèi)別，然后根據(jù)一定的標(biāo)準(zhǔn)分割類(lèi)別，直到滿(mǎn)足停止條件。從下至上則與此相反，算法起初把所有點(diǎn)分別看成一個(gè)類(lèi)別，之后根據(jù)一定標(biāo)準(zhǔn)把若干個(gè)類(lèi)別合并為一個(gè)類(lèi)別，直到滿(mǎn)足停止條件。層次聚類(lèi)法的優(yōu)點(diǎn)在于聚類(lèi)結(jié)果可以用樹(shù)狀圖直觀表示，非常適用于本身具有分層結(jié)構(gòu)的數(shù)據(jù)集。它的缺點(diǎn)主要是需要人為給定停止條件，并且它的時(shí)間與空間復(fù)雜度均為O(n2)。

層次聚類(lèi)法的代表算法有： BIRCH算法、CURE算法、CHAMELEON算法等，它們之間的區(qū)別基本就在于對(duì)不同的連接標(biāo)準(zhǔn)(linkage metric)的選擇。連接標(biāo)準(zhǔn)就是拆分類(lèi)或合并類(lèi)時(shí)的標(biāo)準(zhǔn)。最常用的三類(lèi)連接標(biāo)準(zhǔn)是： Single link(兩個(gè)類(lèi)別之間點(diǎn)的最小距離)、Complete link(兩個(gè)類(lèi)別之間點(diǎn)的最大距離)、和Average link(兩個(gè)類(lèi)別之間點(diǎn)的平均距離)。

層次聚類(lèi)算法較高的時(shí)間與空間復(fù)雜度使其無(wú)法應(yīng)對(duì)實(shí)際應(yīng)用中大規(guī)模的短文本聚類(lèi)需求。

3 大規(guī)模短文本類(lèi)別的“長(zhǎng)尾現(xiàn)象”

在大部分的聚類(lèi)算法中，孤立點(diǎn)都是一個(gè)不容忽視的因素，有些算法對(duì)孤立點(diǎn)很敏感，如K-Means算法。現(xiàn)在已有很多學(xué)者針對(duì)孤立點(diǎn)的檢測(cè)和減少孤立點(diǎn)對(duì)聚類(lèi)算法的影響開(kāi)展研究。但是這些研究可能都基于一個(gè)假設(shè)： 孤立點(diǎn)相對(duì)于正常點(diǎn)是少量的。這個(gè)假設(shè)對(duì)于大多數(shù)聚類(lèi)問(wèn)題是成立的，但對(duì)于手機(jī)短信息、Twitter信息、聊天信息等大規(guī)模短文本的這些應(yīng)用場(chǎng)景來(lái)說(shuō)，不一定成立。有很多情況下，孤立點(diǎn)的數(shù)量往往大于正常點(diǎn)。這里所說(shuō)的孤立點(diǎn)不僅指單個(gè)的點(diǎn)，也包括數(shù)量極小的類(lèi)別，我們根據(jù)這個(gè)特征發(fā)現(xiàn)這些應(yīng)用中的短文本的類(lèi)別往往具有“長(zhǎng)尾現(xiàn)象”。

“長(zhǎng)尾現(xiàn)象”是統(tǒng)計(jì)學(xué)中Power Laws[9]和帕累托(Pareto)分布特征的一個(gè)口語(yǔ)化表達(dá)。長(zhǎng)尾現(xiàn)象的示意圖如圖1所示。舉例來(lái)說(shuō)，我們常用的漢字實(shí)際上并不多，但因出現(xiàn)頻次高，所以這些為數(shù)不多的漢字占據(jù)了圖1廣大的灰色區(qū)域；絕大部分的漢字難得一用，它們就屬于黑色區(qū)域的長(zhǎng)尾。雖然長(zhǎng)尾部分使用頻率低，但是由于長(zhǎng)尾的“長(zhǎng)”，長(zhǎng)尾部分的面積甚至?xí)笥诨疑珔^(qū)域的面積。

圖1 長(zhǎng)尾現(xiàn)象

大規(guī)模短文本類(lèi)別的“長(zhǎng)尾現(xiàn)象”是指在很多短文本實(shí)際應(yīng)用環(huán)境中，有相當(dāng)部分的短文本類(lèi)別包含的短文本數(shù)量很小，屬于孤立點(diǎn)，不太具有聚類(lèi)的效果和意義，但是它們?cè)诙涛谋究倲?shù)量中卻占據(jù)很大比例。僅有少量的類(lèi)別屬于大類(lèi)別，這些大類(lèi)別所包含的短文本數(shù)很大，是我們通常意義上的“熱點(diǎn)”，這些熱點(diǎn)才是我們?cè)诙涛谋揪垲?lèi)應(yīng)用中所真正關(guān)注的。以Twitter信息為例，Twitter上的大部分信息屬于個(gè)人信息，如自己的想法，遇到的事等等，這些信息極少有類(lèi)別的概念，因此也就缺乏聚類(lèi)的意義，而當(dāng)網(wǎng)絡(luò)出現(xiàn)一些熱點(diǎn)事件時(shí)，會(huì)有很多圍繞這些熱點(diǎn)的Twitter信息出現(xiàn)，這些信息構(gòu)成的大類(lèi)別才是短文本聚類(lèi)希望得到的結(jié)果。

我們通過(guò)一個(gè)實(shí)驗(yàn)對(duì)短文本類(lèi)別的長(zhǎng)尾現(xiàn)象進(jìn)行了驗(yàn)證。我們從Twitter一段時(shí)間的數(shù)據(jù)中收集了98 122條短文本信息。對(duì)該數(shù)據(jù)利用傳統(tǒng)K-Medoids算法進(jìn)行聚類(lèi)分析，觀察聚類(lèi)結(jié)果。試驗(yàn)中類(lèi)別個(gè)數(shù)K設(shè)為10 000，聚類(lèi)結(jié)果如圖2所示。圖中，橫坐標(biāo)為聚類(lèi)類(lèi)別編號(hào)，縱坐標(biāo)表示該類(lèi)別中所含的樣本個(gè)數(shù)。從圖2可以看出， 該數(shù)據(jù)中部分樣本構(gòu)成了較大的類(lèi)簇，這些類(lèi)簇所體現(xiàn)的信息是我們對(duì)短文本進(jìn)行聚類(lèi)分析想要得到的熱點(diǎn)信息。同時(shí)，還有相當(dāng)一部分文本信息形成了孤立點(diǎn)，也就是長(zhǎng)尾現(xiàn)象中的“尾部”。

圖2 短文本類(lèi)別柱狀圖

另一方面，我們對(duì)相同的數(shù)據(jù)采用Single-Pass完全比較聚類(lèi)算法進(jìn)行聚類(lèi)分析，即每個(gè)短文本與所有已有類(lèi)別進(jìn)行相似度比較，相似度大于一定閾值即將此短文本歸于這個(gè)類(lèi)別，如與所有類(lèi)別均不匹配，則將此短文本新建為一個(gè)類(lèi)別。聚類(lèi)后對(duì)結(jié)果進(jìn)行統(tǒng)計(jì)，得到表1所示結(jié)果。

表1 短文本聚類(lèi)結(jié)果分析

其中，大類(lèi)別指樣本個(gè)數(shù)超過(guò)10的類(lèi)別，小類(lèi)別指樣本個(gè)數(shù)小于3的類(lèi)別，孤立點(diǎn)指樣本個(gè)數(shù)為1的類(lèi)別。從表1可以看出，在98 122條短文本樣本中，有62 960條樣本屬于孤立點(diǎn)，超過(guò)了總樣本數(shù)的60%，而大類(lèi)別數(shù)僅有570個(gè)，包含的短文本樣本數(shù)占總樣本個(gè)數(shù)的比例不到30%。

4 大規(guī)模短文本不完全聚類(lèi)

傳統(tǒng)的基本聚類(lèi)算法進(jìn)行聚類(lèi)時(shí)，大都會(huì)對(duì)所有數(shù)據(jù)進(jìn)行完全聚類(lèi)，即每個(gè)數(shù)據(jù)最后都會(huì)歸于一個(gè)或多個(gè)類(lèi)別中，我們把這類(lèi)聚類(lèi)算法統(tǒng)稱(chēng)為完全聚類(lèi)。然而，根據(jù)第3節(jié)的分析，諸如Twitter等具有“長(zhǎng)尾現(xiàn)象”的大規(guī)模短文本信息中往往存在大量的孤立點(diǎn)文本。這些文本的存在，一方面使得如K-Means等對(duì)于孤立點(diǎn)敏感的聚類(lèi)算法難以適應(yīng)于這類(lèi)文本信息的聚類(lèi)分析。另一方面，這些大量的孤立信息往往并非我們?cè)诰垲?lèi)分析中關(guān)注的重點(diǎn)。將完全聚類(lèi)算法應(yīng)用于這類(lèi)聚類(lèi)問(wèn)題，算法會(huì)將大量運(yùn)行時(shí)間浪費(fèi)在在缺乏意義的孤立點(diǎn)的聚類(lèi)上，導(dǎo)致了算法的低效。為此，我們提出了一種新的聚類(lèi)思想——不完全聚類(lèi)。

4.1 不完全聚類(lèi)的主要思想

不完全聚類(lèi)的主要思想在于在聚類(lèi)過(guò)程中集中資源處理重要的大類(lèi)別短文本，減少資源在孤立點(diǎn)聚類(lèi)上的浪費(fèi)，盡量減少小類(lèi)別短文本的聚類(lèi)時(shí)間，增加大類(lèi)別短文本聚類(lèi)的機(jī)會(huì)。

依據(jù)不完全聚類(lèi)的思想，可以有多種具體實(shí)現(xiàn)方式，本文提出一種基于限制比較次數(shù)的不完全聚類(lèi)算法，此算法主要針對(duì)短文本有時(shí)間順序的應(yīng)用，而大部分實(shí)際短文本聚類(lèi)應(yīng)用具有此類(lèi)屬性。

4.2 基于限制比較次數(shù)的不完全聚類(lèi)算法

基于限制比較次數(shù)的不完全聚類(lèi)算法通過(guò)限制樣本與類(lèi)別之間的比較次數(shù)來(lái)實(shí)現(xiàn)不完全聚類(lèi)。假設(shè)在聚類(lèi)過(guò)程中已經(jīng)存在n個(gè)類(lèi)別，對(duì)于待處理的每一條樣本，僅將該樣本與根據(jù)一定方法選取的m個(gè)已有類(lèi)別進(jìn)行比較，若與其中某一類(lèi)別相似度大于一定閾值，則將該樣本歸屬于這一類(lèi)別，否則將該樣本作為聚類(lèi)中心構(gòu)成一新類(lèi)別。待比較的m個(gè)類(lèi)別的選取方法可以有多種，這里我們采用的是選取最新生成的m個(gè)類(lèi)別。采用這種選取方法的原因是在實(shí)際應(yīng)用中短文本的出現(xiàn)具有一定的時(shí)間內(nèi)聚性，即在相同一段時(shí)間內(nèi)產(chǎn)生的短文本更有可能屬于同一類(lèi)別，這是因?yàn)橐粋€(gè)熱點(diǎn)事件發(fā)生后，通常會(huì)在短時(shí)間內(nèi)產(chǎn)生大量與此事件相關(guān)的短文本，而隨著時(shí)間推移，這類(lèi)短文本會(huì)越來(lái)越少。

基于限制比較次數(shù)的不完全聚類(lèi)算法的必然代價(jià)是它可能使一些本該聚在一起的樣本錯(cuò)失聚類(lèi)機(jī)會(huì)。因此，我們?cè)谒惴ㄟ^(guò)程中加入其他方法減少這種代價(jià)。

4.2.1 初始類(lèi)別的選取

根據(jù)上面提到的短文本的時(shí)間內(nèi)聚性，我們選取上一個(gè)單位時(shí)間段的大類(lèi)別作為當(dāng)前時(shí)間段聚類(lèi)的初始類(lèi)別。例如，如果聚類(lèi)過(guò)程是以小時(shí)為單位時(shí)間來(lái)進(jìn)行的，那么可以選取上一個(gè)小時(shí)聚類(lèi)過(guò)程得到的大類(lèi)別來(lái)作為這一個(gè)小時(shí)的初始類(lèi)別。當(dāng)然，在整個(gè)聚類(lèi)過(guò)程最初運(yùn)行時(shí)，初始類(lèi)別就由短文本聚類(lèi)先后次序決定了。

4.2.2 短文本的排序

為了進(jìn)一步減小聚類(lèi)時(shí)短文本與已有類(lèi)別的比較次數(shù)，同時(shí)讓每個(gè)短文本盡可能在有限的m次與已有類(lèi)別的比較中找到屬于自己的類(lèi)別，可以采用對(duì)短文本排序的方法來(lái)增加短文本之間的空間內(nèi)聚性，即讓更相似的短文本在聚類(lèi)的先后次序上也更接近。因?yàn)樵诰垲?lèi)時(shí)，每個(gè)短文本是與最新生成的m個(gè)類(lèi)別進(jìn)行相似度比較，假設(shè)某一個(gè)短文本沒(méi)有找到歸屬類(lèi)別而成為一個(gè)新類(lèi)別，那么與這條短文本相似度更高的短文本如果在聚類(lèi)的次序上離它更近的話(huà)，那這些短文本也就能更快地找到歸屬的類(lèi)別，這樣既能提高算法的性能，同時(shí)也能提高算法的效果。

我們采用的排序方法是，先生成一個(gè)固定的短文本模型，讓每個(gè)短文本與這個(gè)模型進(jìn)行相似度計(jì)算，再結(jié)合這個(gè)相似度值及每個(gè)短文本的hash值對(duì)短文本進(jìn)行排序。

4.2.3 m值的自適應(yīng)選取

對(duì)于m值的選取，除了可以使用固定值外，也可以采用更為靈活的自適應(yīng)選取方法，綜合考慮現(xiàn)有類(lèi)別數(shù)，每條短文本屬于孤立點(diǎn)的概率等因素來(lái)針對(duì)每條短文本采用不同的m值。其中，短文本屬于孤立點(diǎn)的概率可以根據(jù)短文本長(zhǎng)度、每個(gè)字的df值等內(nèi)部屬性，或者短文本來(lái)源等外部屬性，利用機(jī)器學(xué)習(xí)方法獲取。若能通過(guò)機(jī)器學(xué)習(xí)方法獲得一個(gè)模型來(lái)評(píng)估每條短文本屬于孤立點(diǎn)的概率，會(huì)對(duì)整個(gè)算法的性能和效果有很大的改進(jìn)。

4.2.4 類(lèi)別的清理與調(diào)整

隨著聚類(lèi)過(guò)程的進(jìn)行，在聚類(lèi)中產(chǎn)生的類(lèi)別會(huì)越來(lái)越多，為了減小孤立點(diǎn)對(duì)聚類(lèi)的干擾，也為了減少聚類(lèi)過(guò)程中內(nèi)存的占用，我們可以定時(shí)對(duì)類(lèi)別進(jìn)行清理，原則是將陳舊或者數(shù)量很小并且沒(méi)有形成大類(lèi)別潛力的類(lèi)別清除。清除后還可以調(diào)整特別“熱”的事件類(lèi)別的位置，使后續(xù)的短文本更多的與這些“熱”事件類(lèi)別進(jìn)行比較。

4.3 算法描述

基于限制比較次數(shù)的不完全聚類(lèi)算法的具體流程如下：

步驟1. 選取m個(gè)初始類(lèi)別；

步驟2. 將需要聚類(lèi)的短文本進(jìn)行排序；

步驟3. 對(duì)每一條短文本，將其與最新生成的m個(gè)類(lèi)別進(jìn)行相似度比較，如與某一類(lèi)別相似度大于一定閾值，則將該短文本歸于該類(lèi)別，并更新該類(lèi)別信息，否則根據(jù)該短文本新建一類(lèi)別，并以該文本作為該類(lèi)別聚類(lèi)中心；

步驟4. 對(duì)短文本類(lèi)別進(jìn)行清理和調(diào)整；

步驟5. 如果m不是固定值，則對(duì)m進(jìn)行自適應(yīng)選取。

在實(shí)際的在線短文本聚類(lèi)分析應(yīng)用中，將實(shí)時(shí)采集的單位時(shí)間段內(nèi)的短文本依據(jù)上述步驟進(jìn)行處理即可。

5 實(shí)驗(yàn)分析

使用第三節(jié)實(shí)驗(yàn)中的98 122條短文本數(shù)據(jù)，對(duì)完全聚類(lèi)和基于限制比較次數(shù)的不完全聚類(lèi)的性能和效果進(jìn)行比較。完全聚類(lèi)使用的算法流程與基于限制比較次數(shù)的不完全聚類(lèi)相同，但在進(jìn)行比較時(shí)沒(méi)有比較次數(shù)m的限制。實(shí)驗(yàn)結(jié)果列于表1中。其中，總比較次數(shù)指聚類(lèi)過(guò)程中短文本與類(lèi)別的總比較次數(shù)之和，總類(lèi)別數(shù)是指聚類(lèi)最終得到的類(lèi)別個(gè)數(shù)，大類(lèi)別數(shù)指聚類(lèi)結(jié)果中樣本數(shù)大于10的類(lèi)別個(gè)數(shù)，小類(lèi)別數(shù)指樣本數(shù)小于3的類(lèi)別個(gè)數(shù)，孤立點(diǎn)數(shù)指樣本數(shù)為1的類(lèi)別個(gè)數(shù)。

表2 完全聚類(lèi)與不完全聚類(lèi)的比較

從表2可以看出，當(dāng)取m=10 000進(jìn)行不完全聚類(lèi)時(shí)，聚類(lèi)所得到的大類(lèi)別數(shù)為569，僅比完全聚類(lèi)所得到的大類(lèi)別數(shù)少了1個(gè)。也就是說(shuō)，m=10 000時(shí)的不完全聚類(lèi)，幾乎能夠獲得完全聚類(lèi)所得到的全部大類(lèi)別。而算法的運(yùn)行時(shí)間與總比較次數(shù)均較完全聚類(lèi)有顯著減少。當(dāng)m取1 000進(jìn)行不完全聚類(lèi)時(shí)，算法僅需完全聚類(lèi)7%(31/432)的時(shí)間代價(jià)即可得到完全聚類(lèi)80%以上(459/570)的大類(lèi)別。由此可見(jiàn)，對(duì)于具有長(zhǎng)尾現(xiàn)象的短文本進(jìn)行聚類(lèi)分析時(shí)，采用不完全聚類(lèi)法能夠有效地縮減小類(lèi)別和孤立點(diǎn)所耗費(fèi)的聚類(lèi)時(shí)間，從而在不喪失聚類(lèi)效果的前提下大幅度提升聚類(lèi)算法的效率。

表3 不完全聚類(lèi)中使用類(lèi)別清理的結(jié)果

在上面實(shí)驗(yàn)的基礎(chǔ)上，我們對(duì)不完全聚類(lèi)中是否進(jìn)行類(lèi)別清理的結(jié)果作了比較。類(lèi)別清理的策略為： 設(shè)置最大類(lèi)別數(shù)MAX_CLUSTER_NUM和基類(lèi)別數(shù)BASE_CLUSTER_NUM，當(dāng)聚類(lèi)過(guò)程中類(lèi)別數(shù)達(dá)到MAX_CLUSTER_NUM時(shí)，就將類(lèi)別按照類(lèi)別大小排序，取類(lèi)別大小最大的前BASE_CLUSTER_NUM個(gè)類(lèi)別做后續(xù)聚類(lèi)，其余的類(lèi)別直接清除。實(shí)驗(yàn)中m取10 000，MAX_CLUSTER_NUM取10 000，BASE_CLUSTER_NUM取1 000。實(shí)驗(yàn)結(jié)果如表2所示。從表3可以看出，使用類(lèi)別清理后，算法僅需40%(87/212)的時(shí)間代價(jià)即可得到95%(545/569)的大類(lèi)別數(shù)。由此可見(jiàn)，使用類(lèi)別清理策略可以對(duì)不完全聚類(lèi)算法的效率有很大的提升。

6 結(jié)束語(yǔ)

本文對(duì)實(shí)際應(yīng)用中的大規(guī)模短文本聚類(lèi)問(wèn)題進(jìn)行了研究。通過(guò)觀察和分析發(fā)現(xiàn)大規(guī)模短文本類(lèi)別所具有的“長(zhǎng)尾現(xiàn)象”，并提出了不完全聚類(lèi)思想對(duì)具有“長(zhǎng)尾現(xiàn)象”的這類(lèi)數(shù)據(jù)進(jìn)行聚類(lèi)分析。實(shí)驗(yàn)結(jié)果表明，本文所提出的基于限制比較次數(shù)的不完全聚類(lèi)算法能夠快速有效地得到樣本信息中的大類(lèi)簇，是一種處理大規(guī)模短文本聚類(lèi)應(yīng)用的有效方式。

[1] A.K. JAIN, M.N. MURTY, P.J. FLYNN. Data Clustering: A Review[J]. ACM Computing Surveys, September 1999, 31(3).

[2] Wang L, Jia Y, Han W H. Instance message clustering based on extended vector space model[EB/OL]. Proceedings of 2ndIternational Symposium on Intelligence Computation and Applications. Wuhan, China: Springer, 2007: 435-443.

[3] He H, Chen B, Xu W R, Guo J. Short text feature extraction and clustering for web topic mining[EB/OL]. Proceeding of the 3rdInternational Conference on Semantics, Knowledge and Grid. Washington D. C., USA: IEEE, 2007: 382-385.

[4] 黃永光，劉挺，車(chē)萬(wàn)翔，胡曉光. 面向變異短文本的快速聚類(lèi)算法[J]. 中文信息學(xué)報(bào)，2007, 21(2): 63-68.

[5] 賀濤，曹先彬，譚輝. 基于免疫的中文網(wǎng)絡(luò)短文本聚類(lèi)算法[J]. 自動(dòng)化學(xué)報(bào)2009, 35(7).

[6] http://tech.ifeng.com/internet/detail_2010_06/09/1600761_0.shtml[DB/OL].

[7] HARTIGAN, J. and WONG, M. Algorithm AS136: A k-means clustering algorithm[J]. Applied Statistics, 1979，28: 100-108.

[8] Horatiu Mocian. Survey of Distributed Clustering Techniques[EB/OL]. 1stterm ISO report, 2009.

[9] M. E. J. Newman. Power laws, Pareto distributions and Zipf’s law[J]. Contemporary Physics, 2005，46(5)：323-351.