王彬宇，劉文芬，胡學(xué)先，魏江宏

1.數(shù)學(xué)工程與先進計算國家重點實驗室，鄭州 450000

2.桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點實驗室，廣西 桂林 541000

1 引言

隨著大數(shù)據(jù)時代的不斷發(fā)展，文本信息大量產(chǎn)生且富含豐富價值，如何合理利用這些文本信息成為人們面臨的機遇與挑戰(zhàn)。文本聚類作為文本數(shù)據(jù)挖掘的重要手段之一，是將大量雜亂無序的文章，通過相似度判斷進行合理的歸類，使主題、內(nèi)容相似的文章分在同一類別中，而不相似的文章被劃分到不同的類別[1]。作為一種無監(jiān)督的機器學(xué)習(xí)方法，文本聚類由于不需要訓(xùn)練過程，以及不需要預(yù)先對文本手動標(biāo)注類別，因此具有一定的靈活性和較高的自動化處理能力，已經(jīng)成為對文本信息進行有效組織、摘要和導(dǎo)航的重要手段，為越來越多的研究人員所關(guān)注[2]。

在文本聚類方法中，基于余弦相似度的K-means算法[4]由于其算法簡單、收斂速度快、能有效處理大數(shù)據(jù)集等特點，仍然是使用最廣泛的文本聚類算法,特別是它在向量空間模型中的拓展——超球K-means算法（Spherical K-Means，SKM）[5]，已被證明是非常有效的文本聚類算法。2016年，Tunali等人在SKM的基礎(chǔ)上，提出了一種更適用于文本聚類的軟劃分聚類方法——多簇超球K-means算法（Multi-Cluster Spherical K-Means，MCSKM）[6]，通過在聚類過程中將每個樣本點分配到多個簇中使聚類更快地逼近最優(yōu)解。本文在K-means算法及上述拓展算法的基礎(chǔ)上，討論如下幾個問題：

首先，K-means算法從出現(xiàn)到現(xiàn)在已有50多年，科研工作者從優(yōu)化問題[7]、K值的選取[9]、離群點檢測[10]等多方面對其進行研究改進，但其中眾多優(yōu)異的研究改進成果是建立在歐氏距離的基礎(chǔ)上，而對基于余弦相似度的K-means算法（后面簡稱為余弦K-means算法），用夾角的余弦值衡量相似度，改進算法卻不一定適用，如經(jīng)典改進算法Fuzzy ISODATA，K-means++[11]等等。同時，由于余弦相似度是衡量文本間相似度的度量標(biāo)準(zhǔn)，用角度表達距離且計算復(fù)雜，所以專門面向余弦K-means的改進算法至關(guān)重要但設(shè)計存在一定難度。為了避免重新設(shè)計改進算法，能否將基于歐氏距離的K-means算法（后面簡稱歐氏K-means算法）改進成果通過變換運用到余弦K-means中，成為值得考慮關(guān)注的問題。

其次，歐氏距離反映數(shù)據(jù)間的間隔長度，而余弦相似度反映數(shù)據(jù)間的相似程度，余弦K-means每輪迭代中的簇中心計算方法是否與歐氏K-means計算方法一致，該如何計算。文獻[12]中關(guān)注到這個問題，提出不能按照原K-means算法中通過計算簇內(nèi)所有樣本點均值的方法進行計算，作者采用符合簇內(nèi)余弦距離和最短的簇內(nèi)點作為簇中心，但簇內(nèi)點與真實簇中心還有一定差距。之后，胡洋瑞等人在此基礎(chǔ)上也提出在余弦K-means中使用歐氏距離計算簇中心造成距離度量標(biāo)準(zhǔn)不一致，并給出了簇內(nèi)中心點應(yīng)滿足的目標(biāo)函數(shù)[13]，但并未解出簇內(nèi)中心點具體的計算方式。由此，能否通過理論推導(dǎo)得到余弦K-means的簇內(nèi)中心點計算公式是亟待解決的問題。

最后，隨機選取初始點極易導(dǎo)致聚類結(jié)果陷入局部最優(yōu)解、聚類迭代次數(shù)增加以及聚類結(jié)果不穩(wěn)定等問題，而良好的初始點選取方法可減少上述問題，并使聚類精度及效率得到提高。初始點選取一直是K-means算法研究的熱點問題，但大量改進算法都是建立在歐氏距離的基礎(chǔ)上，而對余弦K-means算法卻并不適用。為了減少隨機初始點對余弦K-means聚類結(jié)果的影響，許多研究者采用多次實驗結(jié)果取均值的方式來減少算法的不穩(wěn)定性[14]；徐森等人提出使用集成學(xué)習(xí)的方式對多次實驗結(jié)果進行有機結(jié)合，以期望更大程度地減少隨機初始點的影響[15]。但這些算法因需要重復(fù)多次試驗而極大地降低了聚類效率，且并未直接解決余弦K-means的初始點選擇問題。2015年，Duwairi等人采用對區(qū)域進行1/k均等劃分的方式，進行初始點選取[16]，但該選取方法并未結(jié)合目標(biāo)數(shù)據(jù)集的點分布特性，僅適用于點均勻分布的數(shù)據(jù)集，而對于大部分?jǐn)?shù)據(jù)集效果差強人意。2016年，翟東海等人通過定義余弦距離利用最大距離法來進行初始點選取，但文章未給出余弦距離的合理解釋且算法對孤立點較敏感[12]。因此，在余弦K-means中進行初始點選取一直是困擾文本聚類的難點問題。

本文針對上述三個問題，提出了相對應(yīng)的解決方案。首先，針對于部分歐氏K-means改進成果不適用于余弦K-means的問題，為了避免在余弦K-means上完全重新設(shè)計改進算法，本文探討了余弦相似度與歐氏距離的關(guān)系，得到標(biāo)準(zhǔn)向量前提下二者的轉(zhuǎn)化公式，并在此基礎(chǔ)上定義了一種與歐氏距離意義相近關(guān)系緊密的余弦距離，通過余弦距離的性質(zhì)，使原有歐氏K-means改進算法可通過余弦距離遷移到余弦K-means算法中。然后，利用余弦相似度與歐氏距離的轉(zhuǎn)化公式，解出余弦K-means簇內(nèi)中心點的目標(biāo)函數(shù)，證明余弦K-means算法中簇中心計算方法與原歐氏K-means的計算方法一致。最后，針對MCSKM隨機初始點選取的問題，通過余弦距離以及本文第三節(jié)結(jié)論，將歐氏K-means的初始點改進算法K-means++思想遷移到余弦K-means算法中，得到適用于余弦K-means的初始點選取方法，結(jié)合軟劃分文本聚類算法形成新的文本聚類算法MCSKM++。通過實驗驗證，該算法具有迭代次數(shù)少，運行時間短，聚類精度高等優(yōu)點。

2 背景知識

2.1 文本的向量表示

文本是復(fù)雜的非結(jié)構(gòu)化數(shù)據(jù)，而傳統(tǒng)的聚類算法所處理的對象都是數(shù)值型數(shù)據(jù)。為了對文本進行聚類，首先需要將非結(jié)構(gòu)化的文本數(shù)據(jù)轉(zhuǎn)化為易于處理的數(shù)值向量。向量空間模型（Vector Space Model，VSM）[17]是將文本數(shù)據(jù)進行向量化表示的經(jīng)典方法，可以將文檔集合D中的每篇文檔di轉(zhuǎn)化成為一個n維向量xi=(xi1,xi2,…,xin)，其中n表示整個文檔集合的所有文檔中不同的詞語的數(shù)量，xij表示詞語wj在文檔di中的權(quán)值。

為了確定一個單詞在某個文檔中的取值，最常用的計算方法是采用詞頻逆文檔頻率（TF-IDF）[18]。對于詞語wj，利用TF-IDF方法計算它在文檔di中的權(quán)值xij的公式為：

其中，fij表示詞語wj在文檔di中出現(xiàn)的頻數(shù)，lb(1+N/fj)表示詞語wj的逆文檔詞頻，N是整個文檔集合中的文檔數(shù)量，fj為整個文檔集合中包含詞語wj的文檔數(shù)量。

通過文本的向量表示，非結(jié)構(gòu)化的文檔集合D={d1,d2,…,dn}轉(zhuǎn)化成為傳統(tǒng)聚類算法可處理的向量集合X={x1,x1,…,xn}。然而這些文本向量具有高維、稀疏、維度間有相關(guān)性等特點[19]，導(dǎo)致需要對聚類算法做相應(yīng)的改進以適用于文本聚類。

2.2 相似性度量

對于歐氏空間中的任意兩個向量x=(x1,x2,…,xn)和y=(y1,y2,…,yn)，其歐氏距離定義為：

而它們的余弦相似度（Cosine）定義為兩個向量夾角的余弦：

對于高維的數(shù)值型數(shù)據(jù)，文獻[20]證明歐氏距離作為K-means的相似性度量具有更好的適應(yīng)性，因此K-means算法普遍采用歐氏距離。而對于文本向量，文獻[21]提出余弦相似度相比于歐氏距離具有更好的效果。因為歐氏距離用向量間間隔長度的大小衡量距離，注重維度數(shù)值上差異的絕對值，而余弦相似度利用夾角的余弦值即方向來刻畫相似度，更注重維度間相對層面的差異。在文本的相似度判斷中，單詞是否同時出現(xiàn)即相同維度上是否同時非零是判斷其相似度的重要指標(biāo)，而對于單詞出現(xiàn)的次數(shù)即相同維度上數(shù)值的差異，其重要程度相對減少。因此，向量夾角的余弦值更能刻畫文本向量間的相似程度，文本聚類通常采用余弦相似度作為相似度度量。并且，正因為余弦相似度的特性，得到下面適于文本聚類的超球K-means聚類算法。

2.3 超球K-means聚類算法

超球K-means聚類算法（Spherical K-means，SKM）算法[5]是專門針對于文本聚類的K-means改進算法。其基本思想是在聚類前對文本向量進行標(biāo)準(zhǔn)化，再對標(biāo)準(zhǔn)化后的向量做K-means聚類。這樣做的原因是長文本相比于短文本擁有更多的特征詞，標(biāo)準(zhǔn)化后可減少長文本的貢獻率，使相似度更側(cè)重于方向上的傾斜，而非數(shù)值上的變化[6]。并且，對于歐氏空間中的任意兩個向量x=(x1,x2,…,xn)和 y=(y1,y2,…,yn)及標(biāo)準(zhǔn)化向量=即歐氏空間中的任意兩個向量，標(biāo)準(zhǔn)化前后的余弦相似度不變。公式（4）是SKM算法可行的關(guān)鍵因素，但歐氏距離不具有上述性質(zhì)。另外，通過該算法，每個文本向量的長度為1且分布在半徑為1的超球面上，在計算向量間余弦相似度時，公式（3）可簡化為計算效率。

2.4 MCSKM算法

由于文本數(shù)據(jù)內(nèi)容復(fù)雜，一篇文檔可能與多個類別相關(guān)。針對SKM算法進行硬聚類劃分的缺點，2016年，Tunali等人提出了一種基于軟劃分的SKM改進算法——多簇超球K-means算法（Multi-Cluster Spherical K-means，MCSKM）。MCSKM算法是通過在SKM算法每輪迭代中，文檔向量在滿足限制條件時同時分配給多個簇，使聚類結(jié)果更快地向全局最優(yōu)解逼近。首先，作者給出了兩個限制條件：

（1）根據(jù)數(shù)據(jù)集設(shè)定參數(shù)——最大可分配簇（Max Assignable Clusters，MAC），使每個樣本點同時分配給的簇的數(shù)量不大于MAC。MAC建議值為≤MAC≤，K表示簇的個數(shù)。

（2）根據(jù)數(shù)據(jù)集設(shè)定參數(shù)——相似度比值界限（Similarity Ratio Limit，SRL），對向量 xi，當(dāng)某個簇中的簇中心）時，則xi允許被分配到簇oj中。SRL的建議值為0.1≤SRL≤0.2。

通過這兩個限制條件對文本向量進行軟劃分。具體算法如下：

算法1 MCSKM[6]

輸入：文檔向量集合X，簇個數(shù)K，最大可分配簇MAC，相似度比值界限SRL

輸出：聚類結(jié)果

步驟1從X中任意選擇K個文檔向量作為初始聚類中心。

步驟2對于X中每個文檔向量xi。

（1）計算xi和K個聚類中心之間的余弦相似度。

（2）將余弦相似度值從最高到最低排序。

（3）將文檔xi分配給具有最高相似度的簇obest。

（4）在滿足限制條件MAC和SRL的情況下，將xi按順序分配給相似度高的合格簇。

步驟3根據(jù)分配給各簇的文檔重新計算K個簇中心。

步驟4重復(fù)步驟2和3，直到算法收斂。

3 歐氏距離、余弦相似度與余弦距離

為了使基于歐氏距離的改進算法思想可以遷移到基于余弦K-means算法中，本章將首先探索余弦相似度與歐氏距離的關(guān)系，在此基礎(chǔ)上給出一種余弦距離，通過余弦距離的優(yōu)良性質(zhì)，使改進算法思想得以運用到余弦K-means算法中。因SKM算法中先將向量標(biāo)準(zhǔn)化后聚類，且不影響聚類結(jié)果，因此下面的討論在標(biāo)準(zhǔn)化向量的前提下進行。表1中列出了本文中用到的重要變量及符號定義。

表1 變量及符號定義

定理1對于歐氏空間中的任意兩個標(biāo)準(zhǔn)化向量x=(x1,x2,…,xn)和 y=(y1,y2,…,yn)，對歐氏距離d(x,y)和余弦相似度cos(x,y)，有

證明 由標(biāo)準(zhǔn)化向量定義，有

結(jié)合公式（3）可得

由公式（2）知

結(jié)合式（6）可推出cos(x,y)=1-d2(x,y)。 證畢。

定理1使我們對余弦相似度有了更清晰的認(rèn)識。在標(biāo)準(zhǔn)向量的前提下，余弦相似度與歐氏距離并非兩種完全不同的距離度量，反而具有直接函數(shù)關(guān)系。這樣的關(guān)系，使余弦相似度從夾角的余弦值即方向來刻畫相似度，轉(zhuǎn)變?yōu)榭梢杂孟蛄块g間隔長度大小的平方進行度量，從注重維度間相對層面的差異轉(zhuǎn)變?yōu)樽⒅鼐S度數(shù)值上的差異。同時，這樣的轉(zhuǎn)變也使原來困擾余弦K-means的部分問題得到解決，如本文第四章對簇內(nèi)中心點進行計算。為使基于歐氏距離的改進算法可以遷移到余弦K-means算法中，給出一種基于余弦相似度的距離定義方式。

定義1對于歐氏空間中的任意兩個向量x=(x1,x2,…,xn)和 y=(y1,y2,…,yn)，其余弦距離 dc(x,y)定義為：

經(jīng)驗證，定義的余弦距離符合距離的非負性，對稱性，三角不等式的三個距離基本條件，且該距離與兩點間相似度呈負相關(guān)，因此可作為衡量距離的指標(biāo)。另外，由于文本向量各維度都取值為0到1，則dc(x,y)取值范圍為[0，1]。

定義1給出的余弦距離，是完全在余弦相似度的基礎(chǔ)上定義的距離概念，其最大程度地表達了余弦相似度提供的信息，在聚類過程中，其效果與余弦相似度是完全一致的。由定理1與定義1可知：

推論1歐氏距離d(x,y)，余弦相似度cos(x,y)，余弦距離dc(x,y)三者的關(guān)系為：

三者的轉(zhuǎn)化關(guān)系成為將改進算法遷移的重要公式。余弦相似度與歐氏距離有直接的函數(shù)關(guān)系，使兩者之間有了緊密聯(lián)系，其次，余弦距離的提出，彌補了余弦K-means中缺少距離的缺點，也作為橋梁，使之前基于歐氏距離的K-means改進方法，可通過余弦距離遷移到基于余弦相似度的K-means算法中。因為余弦距離是完全由余弦相似度決定的距離指標(biāo)，與余弦相似度在聚類過程中效果一致，其次通過公式（11），得知余弦距離與歐氏距離一樣，也是用向量間間隔長度的大小來刻畫距離，并且是歐氏距離的函數(shù)，與歐氏距離正相關(guān)，因此余弦距離可表達與歐氏距離幾乎一致的距離意義?；诖丝梢詫⒒跉W氏距離的改進方案遷移到余弦K-means算法中，第五章初始點的選取即是對此理論的運用。

4 中心點計算

通過上章對余弦距離與余弦相似度的深入分析，本章利用定理1推導(dǎo)出簇中心的計算方式。K-means每輪迭代中，簇中心需重新計算以期望簇內(nèi)距離和F(oj)=小。在歐氏距離下，第 j簇cj的簇中心為：

|cj|表示簇cj中樣本點的個數(shù)。易證明，樣本點oj是使簇內(nèi)距離達到最小的點。而對于基于余弦相似度的K-means算法，利用余弦相似度刻畫樣本點間相似度，簇內(nèi)中心點該如何計算，與上式是否保持一致，本章將進行簇中心的推導(dǎo)。

做目標(biāo)函數(shù)F(oj)等于簇內(nèi)余弦相似度和，其極大值點oj即為中心點。

但此式是非線性函數(shù)，對此式的極大值求解是比較困難的，所以之前問題卡在這里無法解決。但應(yīng)用上一章提出的余弦相似度轉(zhuǎn)化，問題可迎刃而解。由定理1目標(biāo)函數(shù)轉(zhuǎn)化為：

求上式的極大值點，簡化為求下面式子的極小值點：

依次令原式對oj1,oj2,oj3,…,ojn求偏導(dǎo)，可得

令上式等于0，則

則極值點為：

從計算結(jié)果可知，余弦K-means及其拓展算法的簇內(nèi)中心點仍是簇內(nèi)各坐標(biāo)的和的均值，與歐氏K-means的簇內(nèi)中心點的計算方法相同。此處使余弦相似度的K-means算法的簇中心計算方式得到證明，可利用此公式計算簇內(nèi)中心點。

5 MCSKM++

MCSKM[6]算法利用軟劃分的方式提高了文本聚類的效果，更符合文本的多樣特性。但其算法的初始點采用隨機選取方式，極有可能導(dǎo)致結(jié)果陷入局部最優(yōu)解，增加迭代次數(shù)等問題。為了減少隨機初始點對算法的影響，原作者采用10次實驗取均值的方式來減少算法的不穩(wěn)定性，但這樣導(dǎo)致算法需消耗10倍的計算時間。而對于MCSKM的初始點有效選取問題，由于算法中兩點間距離采用余弦相似度，導(dǎo)致現(xiàn)有眾多優(yōu)異的初始點選取方法無法適用，本章運用第三章提出的余弦距離得到適合MCSKM的初始點選取方法。

初始點選取一直是K-means算法研究的熱點問題，其本質(zhì)是在第一輪選點時提前對類別進行初步預(yù)測，使選點更接近于最終結(jié)果，繼而大量減少聚類中的迭代與計算成本。許多初始點選取方案基于以下事實：距離大的樣本點分到同一個簇的可能性??；相反，距離小的樣本點分到同一個簇的可能性大[12]。因此，選取K個相互之間距離較遠的點作為初始簇中心能取得較好效果。而對于文本聚類所需的基于余弦相似度的K-means算法，缺少距離的概念，余弦相似度表達方向的差異，如何利用方向?qū)Τ跏键c進行選擇成為新的問題。即使借用相似度小的點作為初始點的思路，選擇余弦值最小的兩點xa,xb作為初始點的前兩個點，但不易選取離xa,xb盡可能都遠的第三個中心點xc。因為對于歐氏距離，第三點xc普遍采用分別到xa,xb的距離和或積的最大值點，但余弦值的和或積卻沒有意義，不能表達其相距前兩點較遠。所以，基于余弦相似度的K-means算法初始中心點較難選取，而余弦距離的引入可將歐氏K-means中良好的初始點選取方法進行遷移運用。

余弦距離的提出，使余弦K-means算法擁有距離的度量，且余弦距離與歐氏距離一樣，利用兩點間間隔長度刻畫距離，是向量數(shù)值上的差異，而不再是方向，所以可以將歐氏距離的距離遠即可當(dāng)初始點的思想遷移應(yīng)用于余弦K-means算法，即依次尋找余弦距離相隔最遠的K個點。而為了避免孤立點對選取方法的影響，采用K-means++中利用概率的方式進行選取，需要將原有算法中的歐氏距離d(xi,obest)替換為余弦距離dc(xi,obest)=點xi被選為下一個距離中心的概率為離最近的簇中心點。上式中分子表示該點到最近簇中心的余弦距離的平方，而分母表示屬于該簇的所有點到聚類中心的余弦距離的平方和。通過此概率可利用輪盤法依次選出K個初始點。初始點選取完畢后，在滿足限制條件MAC和SRL的情況下對樣本點進行軟劃分，得到最終的文本聚類結(jié)果，算法具體流程如算法2所示：

算法2 MCSKM++

輸入：文檔向量集合X，簇個數(shù)K，最大可分配簇MAC，相似度比值界限SRL

輸出：聚類結(jié)果

步驟1從文檔向量集合X中隨機選取一個樣本點作為第一個初始聚類中心。

步驟2計算每個樣本點xi與當(dāng)前已有聚類中心之間的最短距離，即與最近的一個聚類中心obest的余弦距離dc(xi,obest)。

步驟3計算各樣本點xi被選為下一個聚類中心的概率依據(jù)此概率用輪盤法選出下一個初始聚類中心。

步驟4重復(fù)步驟2和3，直到選擇出共K個初始聚類中心。

步驟5對于X中每個文檔向量xi。

（1）計算xi和K個聚類中心之間的余弦相似度。

（2）將余弦相似度值從最高到最低排序。

（3）將文檔xi分配給具有最高相似度的簇obest。

（4）在滿足限制條件MAC和SRL的情況下，將xi按順序分配給相似度高的合格簇。

步驟6根據(jù)分配給各簇的文檔重新計算K個簇中心。

步驟7重復(fù)步驟5和6，直到算法收斂。

該算法的前4步利用概率的方式進行初始點選取，其本質(zhì)是提前對數(shù)據(jù)集的類簇進行初步預(yù)測，使其在每個類簇中各選取一個點作為初始聚類中心。該初步預(yù)測的合理性體現(xiàn)在如下兩方面。一是大概率選取到密集區(qū)域內(nèi)的點，減少孤立點對初始點選取的影響。該方法并非直接選取余弦距離相距最遠的點，而是采用點間距離所占全部距離和的概率選取，這樣在初始點選取過程中，雖然孤立點距離遠被選取概率大，但該區(qū)域內(nèi)點的數(shù)量少，而密集區(qū)域內(nèi)，雖單個點的選中概率不及孤立點高，但由于該區(qū)域點數(shù)量眾多，由此選中該區(qū)域的概率為區(qū)域內(nèi)點的概率和，其值遠高于孤立點，所以可以保證選中的點大概率是密集區(qū)域的點，而密集區(qū)域其實就是類簇的雛形。二是選取的點相互之間距離遠，不在相同類簇中。因為利用兩點間余弦距離確定概率，導(dǎo)致相距越遠的類簇其概率和越高，則選取距離相隔較遠的類簇內(nèi)的點的概率更高，避免了選取的多個初始點在同一類簇內(nèi)。基于上述兩點，該方法既能約束選取密集區(qū)域內(nèi)的點，又可要求選取的點之間相距較遠，則得到的初始點較大程度地反映了類簇的分布情況。該初始點選取方法的優(yōu)勢在于通過概率的方式選取初始點，使得到的初始點分布在相距較遠的密集區(qū)域中，即在每個類簇中各選取一個初始聚類中心，避免算法陷入局部最優(yōu)解，同時節(jié)省了后面迭代過程中的計算與時間成本。相比于隨機選取[6]、區(qū)域均等劃分[16]等選取方式，該方法根據(jù)數(shù)據(jù)集的本身特點選取初始點；相比于傳統(tǒng)的基于最大距離的選取方法[12]，避免了孤立點對初始點的選??；而相比于利用密度的初始點方法[22]，該方法無需單獨確定密度界限參數(shù)，自動根據(jù)數(shù)據(jù)集特點選取初始點。該算法的后三步利用軟聚類的方式將點進行多重劃分，可進一步減少迭代次數(shù)，且更適用于文本的多屬性特性。

6 實驗設(shè)計與結(jié)果

6.1 數(shù)據(jù)集

本文采用文本挖掘領(lǐng)域經(jīng)典的公開數(shù)據(jù)集20newsgroup（20NG）新聞組數(shù)據(jù)集[23]。該數(shù)據(jù)集共包含18 846篇文章，20個新聞組，每組大約有1 000篇文章，其中每篇文章的平均長度為137.85個單詞。

6.2 軟硬件平臺

實驗采用的硬件環(huán)境配置為Intel core i7處理器，16 GB內(nèi)存，64位Ubuntu 16.04 LTS操作系統(tǒng)。軟件采用python軟件進行編程，利用numpy工具包進行科學(xué)計算，sklearn工具包做部分?jǐn)?shù)據(jù)處理工作。

6.3 評價指標(biāo)

6.3.1 標(biāo)準(zhǔn)化互信息

標(biāo)準(zhǔn)化互信息（Normalized Mutual Information，NMI）[24]是衡量聚類結(jié)果的有效度量方式，用來衡量兩個數(shù)據(jù)分布的吻合程度，NMI的值越大即表示聚類結(jié)果與原類別標(biāo)簽的相似度越高。對實驗預(yù)測結(jié)果A與真實數(shù)據(jù)分布B，其計算公式為：

其中，p(a)、p(b)分別表示A、B的概率分布，p(a,b)表示 A和B的聯(lián)合概率分布，H(A)，H(B)為 A、B的熵，其計算公式為：

6.3.2 蘭德系數(shù)

蘭德系數(shù)（Rand Index，RI）利用實驗預(yù)測結(jié)果A與真實數(shù)據(jù)分布B中元素對數(shù)的分布情況進行評價，其計算公式如下：

其中x表示在A與B中都是同類別的元素對數(shù)，y表示在A與B中都是不同類別的元素對數(shù)，z表示數(shù)據(jù)集中可以組成的總元素對數(shù)。RI取值范圍為[0，1]，值越大則聚類結(jié)果與真實情況越吻合。

6.4 實驗設(shè)計及結(jié)果分析

為驗證改進算法的有效性，對原始算法MCSKM，改進算法MCSKM++及文獻[12]算法進行編程實現(xiàn)，作用于20NG數(shù)據(jù)集向量表示后不同維度的數(shù)據(jù)集合，從NMI、RI、迭代次數(shù)、時間四個方面對三種算法的實驗結(jié)果進行比較分析。

首先從sklearn工具包內(nèi)調(diào)用20 NG數(shù)據(jù)集，并對數(shù)據(jù)集進行預(yù)處理操作，包括分詞、去特殊符號、去停用詞、詞根化等，因為文本屬于非結(jié)構(gòu)化數(shù)據(jù)且內(nèi)容復(fù)雜，預(yù)處理對文本聚類至關(guān)重要。然后進行文本建模，將文本用向量空間模型進行向量表示，單詞權(quán)重采用TF-IDF，原數(shù)據(jù)集轉(zhuǎn)化為為向量集合X。在文本建模過程中，采用全部特征時，向量維度約18萬維，利用詞語的文檔頻數(shù)進行特征提取，頻數(shù)的界限取值分別為200～1 000次、150～1 000次、100～1 000次、50～1 000次，形成4個數(shù)據(jù)集合X1,X2,X3,X4，其對應(yīng)的特征提取數(shù)為1 507，2 058，3 150，5 758。這樣做的原因是利用不同的特征提取數(shù)，得到向量維度不同的數(shù)據(jù)集，相當(dāng)于對多個不同的數(shù)據(jù)集進行聚類，可以更好地檢驗改進算法性能。

其次，在python環(huán)境下實現(xiàn)MCSKM算法、CMCSKM++算法、文獻[12]算法，其中MCSKM中的參數(shù)設(shè)置，采用原文[5]針對20NG數(shù)據(jù)集的推薦設(shè)置MAC=7，SRL=0.1。為了保證實驗的公平性，文獻[12]的初始點選取方法也建立在MCSKM算法的基礎(chǔ)上進行實驗。利用以上三個算法分別對集合X1,X2,X3,X4進行聚類。最后，記錄實驗結(jié)果，并從NMI、RI、迭代次數(shù)、時間四個方面對三種方法的聚類效果進行分析比較，結(jié)果由表2所列。

根據(jù)表2的實驗結(jié)果，畫出四種指標(biāo)的對比折線圖，如圖1所示。

通過表2可以看出，針對四種不同維度的數(shù)據(jù)集X1,X2,X3,X4，本文的改進算法MCSKM++相比于原始算法MCSKM以及文獻[12]算法，在計算總時間減少約20%的情況下，聚類效果不僅沒有降低，反而提高7%左右。根據(jù)圖1的折線對比圖對實驗結(jié)果進行縱向比較可以清晰地看出，面對不同維度的向量，本文改進算法的NMI、RI值均高于其他兩個算法（NMI與RI指標(biāo)反映算法的聚類精度），而迭代次數(shù)、時間兩個指標(biāo)都低于同類算法（時間與迭代次數(shù)顯示算法效率），則該算法在精度與效率兩方面都得到較大提升。出現(xiàn)該實驗結(jié)果是因為原始算法MCSKM采用隨機選取初始點的方法，導(dǎo)致算法需花費大量迭代次數(shù)逐漸向最優(yōu)解逼近，且因此可能使結(jié)果陷入局部最優(yōu)解，影響聚類效果。而本文改進算法的初始點選取方法是在選點時利用概率的方式提前對類別進行了初步預(yù)測，使選點更接近于最終聚類結(jié)果，繼而大量減少聚類的迭代與計算成本。雖然在選點階段相較于隨機選取會多花費一定時間，但由于高維數(shù)據(jù)每輪迭代所需計算量大，則減少迭代次數(shù)可大量減少聚類計算時間，從實驗結(jié)果可看出該算法用時更短。且初始點的有效選取使算法更大程度地避免陷入局部最優(yōu)解的情況，也使聚類的精度得到提高。文獻[12]算法提出的初始點選取方案雖具有一定效果，但由于其選取距離相距最遠的數(shù)據(jù)點，導(dǎo)致算法對孤立點較為敏感，影響聚類效果，且存在距離未給出合理解釋等問題，效果不如本文算法。

表2 三種算法聚類結(jié)果比較

圖1 四種評價指標(biāo)折線對比圖

7 結(jié)束語

本文針對部分歐氏K-means改進成果不適用于余弦K-means算法的問題，通過探討余弦相似度與歐氏距離的關(guān)系，得到標(biāo)準(zhǔn)向量前提下二者的轉(zhuǎn)化公式，并由此定義一種余弦距離，使原有歐氏K-means改進算法可由余弦距離遷移到余弦K-means算法中。利用轉(zhuǎn)化公式證明類內(nèi)中心點的計算方法后，通過遷移得到余弦K-means算法的初始點選取方法，并結(jié)合文本軟聚類算法MCSKM得到新的文本聚類算法MCSKM++算法，新算法具有迭代次數(shù)少、聚類時間短、聚類精度高等優(yōu)點。在未來的工作中，將繼續(xù)研究余弦相似度下聚類算法的變化，提出更多適用于文本聚類的余弦K-means改進算法，包括研究更有效的初始點選取方案、對高維數(shù)據(jù)的有效降維方案等，使文本聚類精度和效率得到進一步的提高。

：

[1]Aggarwal C C，Zhai C X.A survey of text clustering algorithms[M]//Mining text data.US：Springer，2012：77-128.

[2]Yin J，Wang J.A text clustering algorithm using an online clustering scheme for initialization[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2016：1995-2004.

[3]Xu J，Xu B，Wang P，et al.Self-taught convolutional neural networks for short text clustering[J].Neural Networks，2017：22-31.

[4]Jain A K.Data clustering：50 years beyond K-means[J].Pattern Recognition Letters，2010，31（8）：651-666.

[5]Dhillon I S，Modha D S.Concept decompositions for large sparse text data using clustering[J].Machine Learning，2001，42（1）：143-175.

[6]Tunali V，Bilgin T，Camurcu A.An improved clustering algorithm for text mining：multi-cluster spherical K-means[J].International Arab Journal of Information Technology（IAJIT），2016，13（1）.

[7]Carvalho V O.Combining K-Means and K-Harmonic with fish school search algorithm for data clustering task on graphics processing units[J].Applied Soft Computing，2016，41（C）：290-304.

[8]Makarychev K，Makarychev Y，Sviridenko M，et al.A bicriteria approximation algorithm for k-means[J].Computer Science，2015.

[9]白樹仁，陳龍.自適應(yīng)K值的粒子群聚類算法[J].計算機工程與應(yīng)用，2017，53（16）：116-120.

[10]韓崇，袁穎珊，梅燾，等.基于K-means的數(shù)據(jù)流離群點檢測算法[J].計算機工程與應(yīng)用，2017，53（3）：58-63.

[11]Arthur D，Vassilvitskii S.K-means++：the advantages of careful seeding[C]//Eighteenth ACM-Siam Symposium on Discrete Algorithms.Society for Industrial and Applied Mathematics，2007：1027-1035.

[12]翟東海，魚江，高飛,等.最大距離法選取初始簇中心的K-means文本聚類算法的研究[J].計算機應(yīng)用研究，2014，31（3）：713-715.

[13]胡洋瑞，陳興蜀，王俊峰,等.基于流量行為特征的異常流量檢測[J].信息網(wǎng)絡(luò)安全，2016（11）：45-51.

[14]謝娟英，王艷娥.最小方差優(yōu)化初始聚類中心的K-means算法[J].計算機工程，2014，40（8）：205-211.

[15]徐森，盧志茂，顧國昌.使用譜聚類算法解決文本聚類集成問題[J].通信學(xué)報，2010，31（6）：58-66.

[16]Duwairi R，Abu-rahmeh M.A novel approach for initializing the spherical K-means clustering algorithm[J].Simulation Modelling Practice&Theory，2015，54：49-63.

[17]Salton G，Wong A，Yang C S.A vector space model for automatic indexing[J].Communications of the ACM，1975，18（11）：613-620.

[18]Salton G，Buckley C.Term-weighting approaches in automatic text retrieval[J].Information Processing& Management，1988，24（5）：513-523.

[19]王駿，王士同，鄧趙紅.特征加權(quán)距離與軟子空間學(xué)習(xí)相結(jié)合的文本聚類新方法[J].計算機學(xué)報，2012，35（8）：1655-1665.

[20]Kanungo T，Mount D M，Netanyahu N S，et al.An efficient k-means clustering algorithm：analysis and implementation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24（7）：881-892.

[21]孫吉貴，劉杰，趙連宇.聚類算法研究[J].軟件學(xué)報，2008（1）：48-61.

[22]Celebi M E，Kingravi H A，Vela P A.A comparative study of efficient initialization methods for the k-means clustering algorithm[J].Expert Systems with Applications，2013，40（1）：200-210.

[23]20NG，20 News Groups Dataset，U.C.I.Machine Learning Repository[DB/OL].[2017-09-10].http：//archive.ics.uci.edu/ml/databases/20newsgroups/.

[24]Strehl A，Ghosh J.Cluster ensembles：a knowledge reuse framework for combining partitionings[J].Journal of Machine Learning Research，2003，3（3）：583-617.