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

彭澤映，俞曉明，許洪波,劉春陽

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 背景知識

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

2.1 分割式聚類法

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

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

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

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

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

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

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

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

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

c) 算法對outliers非常敏感。

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

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

2.2 層次聚類法

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

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

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

3 大規(guī)模短文本類別的“長尾現(xiàn)象”

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

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

圖1 長尾現(xiàn)象

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

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

圖2 短文本類別柱狀圖

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

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

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

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

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

4.1 不完全聚類的主要思想

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

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

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

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

基于限制比較次數(shù)的不完全聚類算法的必然代價是它可能使一些本該聚在一起的樣本錯失聚類機(jī)會。因此，我們在算法過程中加入其他方法減少這種代價。

4.2.1 初始類別的選取

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

4.2.2 短文本的排序

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

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

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

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

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

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

4.3 算法描述

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

步驟1. 選取m個初始類別；

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

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

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

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

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

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

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

表2 完全聚類與不完全聚類的比較

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

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

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

6 結(jié)束語

本文對實(shí)際應(yīng)用中的大規(guī)模短文本聚類問題進(jìn)行了研究。通過觀察和分析發(fā)現(xiàn)大規(guī)模短文本類別所具有的“長尾現(xiàn)象”，并提出了不完全聚類思想對具有“長尾現(xiàn)象”的這類數(shù)據(jù)進(jìn)行聚類分析。實(shí)驗(yàn)結(jié)果表明，本文所提出的基于限制比較次數(shù)的不完全聚類算法能夠快速有效地得到樣本信息中的大類簇，是一種處理大規(guī)模短文本聚類應(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] 黃永光，劉挺，車萬翔，胡曉光. 面向變異短文本的快速聚類算法[J]. 中文信息學(xué)報，2007, 21(2): 63-68.

[5] 賀濤，曹先彬，譚輝. 基于免疫的中文網(wǎng)絡(luò)短文本聚類算法[J]. 自動化學(xué)報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.