融合密度和劃分的文本聚類算法?

劉 龍 劉 新 蔡林杰 唐 朝

（湘潭大學(xué)計(jì)算機(jī)學(xué)院·網(wǎng)絡(luò)空間安全學(xué)院 湘潭 411105）

1 引言

近幾十年來(lái)，隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，人們獲取的信息和采集的數(shù)據(jù)越來(lái)越多，但是海量的數(shù)據(jù)缺乏有效的處理，人們就很難得到有效且有用的信息?；诖朔N情況，作為數(shù)據(jù)挖掘的一種有效工具，聚類算法［1］可以幫助人們高效分析數(shù)據(jù)之間的關(guān)系。

本文研究文檔聚類［2］，文檔聚類的首要任務(wù)是文本向量化，將文檔轉(zhuǎn)換為高維向量再進(jìn)行聚類。2013 年，谷歌推出了基于神經(jīng)網(wǎng)絡(luò)訓(xùn)練的Word2vec［3］詞向量模型，極大地促進(jìn)了自然語(yǔ)言處理的發(fā)展；谷歌在2018 年再次發(fā)布了基于深度學(xué)習(xí)的BERT［4］模型，該模型刷新了自然語(yǔ)言處理領(lǐng)域中多個(gè)方向的記錄。

文檔聚類的核心任務(wù)是研究聚類算法，但是密度聚類算法［5］在高維數(shù)據(jù)集上的表現(xiàn)非常差。劃分算法中的K-均值算法［6］效果一般，主要原因是算法的初始化［7］是隨機(jī)生成的。近年來(lái)，為了克服選取中心點(diǎn)為離群點(diǎn)，李武等［8］提出一種啟發(fā)式算法來(lái)逐步選取初始類中心點(diǎn)，選取的原則是初始類中心點(diǎn)差異度高且與其他初始類中心點(diǎn)差異度高，實(shí)驗(yàn)表明該算法聚類效果正確率高，收斂速度快。賈瑞玉等［9］提出利用局部密度和決策樹來(lái)確定K-均值算法的類簇中心點(diǎn)的數(shù)量和位置，該方法可以有效地排除特殊點(diǎn)，在低維上有著不錯(cuò)的效果。王思杰等［10］提出基于距離的離群點(diǎn)檢測(cè)技術(shù)，對(duì)中心點(diǎn)進(jìn)行篩選，避免離群點(diǎn)成為中心點(diǎn)。張國(guó)峰等［11］提出逐步選取類簇中心點(diǎn)，在更新中心點(diǎn)的同時(shí)判斷簇點(diǎn)的合理性并及時(shí)做出修改，這種方法確保了不會(huì)出現(xiàn)空簇。Rodriguez等［12］在Science上提出了一種新的密度聚類算法，該算法的思想是聚類中心的密度高于其鄰近的中心且距其他高密度點(diǎn)相對(duì)較遠(yuǎn)。

本文使用BERT 模型來(lái)處理文本向量化，并且與其他方法進(jìn)行實(shí)驗(yàn)比較，BERT 模型的確具有出色的性能。本文還提出了一種結(jié)合密度和劃分的文本聚類算法，與其他幾種聚類算法相比，該算法對(duì)高維數(shù)據(jù)集具有更好的聚類效果。

2 相關(guān)工作

2.1 文本向量化表示

文本聚類一個(gè)重要過(guò)程就是文本的向量化。文本向量方法有傳統(tǒng)的向量空間模型［13］（VSM）和Word2vec 方法，兩者需要結(jié)合文本特征提取TF-IDF［14］方法來(lái)進(jìn)行文本聚類。Word2vec 方法優(yōu)點(diǎn)是簡(jiǎn)單、快捷、易懂，但也存在著比較嚴(yán)重的問(wèn)題，它非常依賴語(yǔ)料庫(kù)，需要選取質(zhì)量較高且和所處理文本相符的語(yǔ)料庫(kù)進(jìn)行訓(xùn)練。

本文使用BERT 模型來(lái)處理文本的向量化，BERT 模型作為Word2vec 的替代者，它的網(wǎng)絡(luò)架構(gòu)使 用 了 多 層 帶 有Attention［15］的Transformer［16］結(jié)構(gòu)。本文使用的是BERT-Base 中文模型，模型有12 層Transformer 編碼器，隱藏層的維度是768，自注意頭的個(gè)數(shù)為12，其中BERT 模型中一個(gè)Transformer編碼器的計(jì)算過(guò)程如下：

1）文本向量：通過(guò)詞向量化將單詞變成向量x1、x2…xm，文本向量X的維度是m×768，m為句子的最大分詞數(shù)；

2）計(jì)算Q、K、V：這里我們通過(guò)模型的參數(shù)WO、WK、WV結(jié)合輸入向量X來(lái)計(jì)算出來(lái)向量Q、K、V：

3）單頭自注意力層的輸出矩陣Z：這里首先計(jì)算詞在上下文中的意義以及詞之間的影響QK，得到之后進(jìn)行歸一化處理，最后加權(quán)平均得到單頭注意力層輸出矩陣Z：

4）融合所有注意力頭信息的矩陣Zsum：BERT模型使用了12個(gè)注意力頭，經(jīng)過(guò)步驟3）后，我們可以得到12 個(gè)不同的Z 矩陣，乘上附加的權(quán)重矩陣WO可得到Zsum，Zsum的維度為m×768，最后經(jīng)過(guò)殘差連接和求和歸一化即為下一層下面Transformer 編碼器的輸入。公式中concat（Zi）表示為12 個(gè)注意力頭輸出矩陣的拼接：

2.2 文本距離計(jì)算

文本聚類過(guò)程中需要計(jì)算文本間的差異，本文使用歐氏距離來(lái)計(jì)算文本距離，歐氏距離可以有效防止過(guò)擬合，還可以讓距離優(yōu)化求解快速和穩(wěn)定。文本距離計(jì)算公式如下：

注：D（X，Y）表示文本X與文本Y的歐氏距離。該值越小代表著兩個(gè)文本屬于同一類別的可能性越高。反之，該值越大則說(shuō)明文本相似度越小。xi與yi分別表示文本X、Y的某一向量維度值。

3 文本聚類算法

3.1 K-means算法

K-means算法屬于劃分聚類算法，該算法是將數(shù)據(jù)集n個(gè)數(shù)據(jù)對(duì)象劃分成K類，其具體步驟是：

1）任意選擇K 個(gè)樣本點(diǎn)當(dāng)做初始類中心點(diǎn)，每個(gè)初始類中心點(diǎn)作為一個(gè)聚類中心；

2）對(duì)于數(shù)據(jù)集中的所有樣本點(diǎn)，計(jì)算其與每個(gè)聚類中心的距離，將其歸為距離最近的聚類中心類簇；

3）將各個(gè)類簇樣本點(diǎn)的均值作為該類簇新的聚類中心，得到新的K個(gè)聚類中心；

4）重復(fù)步驟2）～3），并在每次迭代后計(jì)算是否滿足停止條件，若達(dá)到條件之一，則輸出結(jié)果。

K-means算法的停止條件一般為以下三種：聚類中心與前一次聚類中心相差極??；重新劃分給其他類簇的樣本點(diǎn)極少；目標(biāo)函數(shù)極小，即數(shù)據(jù)集的誤差平方和（SSE）局部最小。誤差平方和計(jì)算如式（7）至式（8）所示：

注：SSE 參數(shù)計(jì)算表示當(dāng)前的聚類情況的所有樣本點(diǎn)到各自劃分類的聚類中心的距離總和，這個(gè)值越小表示當(dāng)前的聚類效果越好。K表示聚類類別。Ci表示單個(gè)類簇，共K 個(gè)類簇。p 表示樣本點(diǎn)向量。mi表示類中心點(diǎn)向量，是類Ci的均值向量，也稱質(zhì)心。x表示類簇Ci中的向量。

3.2 K-means++算法

K-means++算法［17］主要解決K-means 算法受初始化影響大的問(wèn)題，在選擇初始類中心點(diǎn)方面做了改進(jìn)，保證初始點(diǎn)足夠離散。算法初始化類中心點(diǎn)的具體步驟如下：

1）任選某一樣本點(diǎn)當(dāng)做初始類中心點(diǎn)；

2）計(jì)算其余樣本點(diǎn)與最近初始類中心點(diǎn)的距離，用D（x）表示；

3）通過(guò)樣本點(diǎn)的D（x）來(lái)表示其成為初始類中心點(diǎn)的概率P；

4）最后輪盤法選擇出下一個(gè)初始類中心點(diǎn)；

5）重復(fù)步驟2）～4）直至得到K 個(gè)初始類中心點(diǎn)。

關(guān)于K-means++算法的初始化過(guò)程中參數(shù)D（x）和P，D（x）為文本向量的歐氏距離，具體計(jì)算見(jiàn)式（6），概率P計(jì)算如式（9）所示：

K-means++算法的初始化有效地改善了隨機(jī)初始化的不穩(wěn)定性，選取下一個(gè)聚類中心點(diǎn)的概率與距離掛鉤，使得初始類中心點(diǎn)離散。

3.3 最大距離法

2014 年，翟海東等［18］提出使用最大距離法來(lái)選取初始類中心點(diǎn)。采用最遠(yuǎn)距離的逐步選取類中心點(diǎn)，最大距離法選取類中心點(diǎn)流程如下：

1）計(jì)算n 個(gè)樣本點(diǎn)兩兩之間的距離，找到滿足D（c1，c2）≥D（ci，cj）（i，j=1，2，…，n）的兩個(gè)樣本點(diǎn)c1和c2，并將它們作為兩個(gè)初始類中心點(diǎn)；

2）在剩余的（n-2）個(gè)樣本點(diǎn)中，選取滿足D（c1，c3）×D（c2，c3）≥D（c1，ci）×D（c2，ci）的樣本點(diǎn)c3，將c3 作為第三個(gè)初始簇中心，ci 是除c3 外的任一樣本點(diǎn)；

3）依此類推，直至選取K個(gè)中心點(diǎn)。

最大距離法屬于K-means++算法的優(yōu)化，聚類的初始化簇中心點(diǎn)確實(shí)有效地囊括所有數(shù)據(jù)，促使所選中心點(diǎn)的分布離散且合理。但是該方法極易選中離群點(diǎn)，導(dǎo)致聚類效果不理想。關(guān)于此類方法，還有基于子空間的K-means++優(yōu)化算法［19］和K-meansⅡ算法［20］。

3.4 融合密度和劃分的聚類算法

本文提出了一種結(jié)合密度和劃分的文本聚類算法（CDP 算法）。首先通過(guò)距離計(jì)算來(lái)定義樣本點(diǎn)的密度，然后通過(guò)密度來(lái)選擇適合作為中心點(diǎn)的樣本，然后通過(guò)最遠(yuǎn)距離方法逐漸選擇初始聚類中心點(diǎn)，最后根據(jù)距離對(duì)整個(gè)數(shù)據(jù)集進(jìn)行劃分。算法具體步驟如下：

1）使用文檔距離計(jì)算模型計(jì)算n 個(gè)樣本集兩兩之間的距離dij；并計(jì)算所有樣本之間的平均距離dc，給出dc計(jì)算如式（10）所示：

2）根據(jù)樣本之間距離與樣本平均距離大小計(jì)算出每個(gè)樣本的密度?i，并計(jì)算所有樣本的密度ρi，給出ρi和ρc計(jì)算如式（11）～（13）所示：

3）將所有滿足ρi>ρc的樣本點(diǎn)歸入適合作為初始類中心點(diǎn)集合M，核心點(diǎn)集M 的個(gè)數(shù)m 必須滿足n>m>K；

4）在M 集合中隨機(jī)選取一點(diǎn)c1 作為初始類中心點(diǎn)；

5）在（m-1）個(gè)點(diǎn)中，選擇滿足D（c1，c2）≥D（c1，ci）的樣本點(diǎn)c2，ci是M集合中除c2的任一點(diǎn)；

6）在（m-2）個(gè)點(diǎn)中，選擇滿足D（c1，c3）×D（c2，c3）≥D（c1，ci）×D（c2，ci）的樣本點(diǎn)c3，ci 是M 集合中c3的任一點(diǎn)；

7）依此類推，直至得到K個(gè)初始類中心點(diǎn)；

8）根據(jù)距離計(jì)算將所有樣本點(diǎn)分配至與其相距最小類簇里；

9）重新計(jì)算中心點(diǎn)，類簇中全部樣本的均值就是新中心點(diǎn)；

10）重復(fù)步驟8）～9），直至數(shù)據(jù)集的SSE目標(biāo)函數(shù)不變或者變化極小。注：dc表示截?cái)嗑嚯x，即文檔數(shù)據(jù)集的樣本平均距離，計(jì)算數(shù)值是每一個(gè)文檔與其他文檔之間的文本距離總和平均化后得到的數(shù)值，當(dāng)數(shù)據(jù)集確定后，該值為常數(shù)。ρi表示為單個(gè)文檔Xi的密度，若兩個(gè)文本的文本距離若小于樣本平均距離dc，說(shuō)明兩個(gè)文本距離較近，即文本相似度較高，文檔Xj在文檔Xi的密度領(lǐng)域內(nèi)，該值越大說(shuō)明文檔Xi的附近點(diǎn)越多。ρc表示截?cái)嗝芏?，?jì)算數(shù)值是所有文檔的密度平均值，當(dāng)文本集確定后，該值也為常數(shù)。

4 實(shí)驗(yàn)

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

本文實(shí)驗(yàn)使用的數(shù)據(jù)集來(lái)自清華大學(xué)的的THUCNews 新聞文本分類數(shù)據(jù)集，THUCNews 數(shù)據(jù)集是根據(jù)新浪新聞2005～2011 年間的歷史數(shù)據(jù)篩選過(guò)濾生成，包含74 萬(wàn)篇新聞文檔，均為UTF-8 純文本格式。此數(shù)據(jù)集在原始新浪新聞分類體系的基礎(chǔ)上，重新整合劃分出14 個(gè)候選分類類別：財(cái)經(jīng)、彩票、房產(chǎn)、股票、家居、教育、科技、社會(huì)、時(shí)尚、時(shí)政、體育、星座、游戲、娛樂(lè)。該數(shù)據(jù)集的每篇文檔所包含的字?jǐn)?shù)在300～5000之間。

4.2 評(píng)估標(biāo)準(zhǔn)

此次實(shí)驗(yàn)使用的評(píng)判標(biāo)準(zhǔn)主要是F1 值，其次還有文本聚類耗時(shí)T。F1 值由精確率P（precision）和召回率R（recall）的計(jì)算得到，精確率P 值為所有“正類判定為正類”占所有“檢測(cè)是正類”的比例，召回率R值是所有“正類判定為正類”占所有“樣本是正類”的比例。P、R、F1 值的計(jì)算如式（14）～式（16），其中，TP表示“正類判定為正類”，F(xiàn)P表示“負(fù)類判定為正類”，F(xiàn)N表示為“正類判定為負(fù)類”。

4.3 實(shí)驗(yàn)對(duì)比

4.3.1 文本向量化實(shí)驗(yàn)

本次實(shí)驗(yàn)?zāi)康氖菧y(cè)試不同的方法處理文檔向量化的效果。實(shí)驗(yàn)數(shù)據(jù)集是5 類文檔集，每一類文檔集有300 篇文檔。實(shí)驗(yàn)首先使用不同方法將文檔轉(zhuǎn)為向量，然后使用傳統(tǒng)的K-means算法對(duì)文檔向量集進(jìn)行聚類，將聚類的結(jié)果作為評(píng)判標(biāo)準(zhǔn)，實(shí)驗(yàn)僅文檔向量化處理過(guò)程不一樣，其他均一致。實(shí)驗(yàn)的兩種文檔向量化處理方法分別是BERT 模型、Word2vec。實(shí)驗(yàn)結(jié)果如圖1所示。

圖1 Word2vec與BERT關(guān)于文本向量化處理對(duì)比圖

從實(shí)驗(yàn)結(jié)果可以看到在P、R、F1 值上，BERT均領(lǐng)先Word2vec，在F1 值上提高超過(guò)10%。在文檔向量化處理效果上，BERT 模型要優(yōu)于Word2vec方法。

4.3.2 文檔關(guān)于類別數(shù)量變化實(shí)驗(yàn)

本次實(shí)驗(yàn)?zāi)康氖菧y(cè)試聚類效果關(guān)于文檔類別數(shù)量的變化。對(duì)比實(shí)驗(yàn)分成兩類：K-means 算法、本文提出的CDP算法。每一類分成七組試驗(yàn)：第一組實(shí)驗(yàn)的數(shù)據(jù)集包含3 類，每一類100 篇共300 篇文檔；第二組實(shí)驗(yàn)的數(shù)據(jù)集包含4類，每一類100篇共400篇文檔；以此類推，第七組實(shí)驗(yàn)的數(shù)據(jù)集是9類共900篇文檔。每一組實(shí)驗(yàn)均采用BERT模型處理文檔向量化，每組實(shí)驗(yàn)過(guò)程一致，僅實(shí)驗(yàn)數(shù)據(jù)集不一樣。聚類指標(biāo)隨類別數(shù)量變化如圖2所示。

圖2 聚類指標(biāo)隨類別數(shù)量變化圖

實(shí)驗(yàn)結(jié)果中，紅色線數(shù)據(jù)為K-means 算法，采用隨機(jī)化初始化，藍(lán)色線數(shù)據(jù)為CDP算法。從實(shí)驗(yàn)結(jié)果可以知道文檔聚類的F1 值會(huì)隨著文本類別的增加而降低，當(dāng)K值較小時(shí)，F(xiàn)1值很高，當(dāng)K值增加時(shí)，F(xiàn)1 值逐漸降低。使用CDP 算法后，聚類效果更好且穩(wěn)定，在聚類類別小于10時(shí)，文檔聚類的F1值一直超80個(gè)百分點(diǎn)。

4.3.3 文檔關(guān)于文檔集數(shù)量變化實(shí)驗(yàn)

實(shí)驗(yàn)三：本次實(shí)驗(yàn)?zāi)康氖菧y(cè)試聚類效果關(guān)于文檔數(shù)據(jù)集數(shù)量的變化。對(duì)比實(shí)驗(yàn)分成兩類：K-means 算法、CDP 算法。每一類分成六組對(duì)比實(shí)驗(yàn)，每組實(shí)驗(yàn)都是5 類文檔，只有文檔數(shù)量不一致，實(shí)驗(yàn)分別對(duì)每組進(jìn)行聚類取平均值：第一組實(shí)驗(yàn)包含5 類，每一類100 篇共500 篇；第二組實(shí)驗(yàn)包含5類，每一類200 篇共1000 篇；以此類推，第六組是5類共3000 篇文檔。每一組實(shí)驗(yàn)均使用BERT 模型處理文檔向量化，實(shí)驗(yàn)過(guò)程一致，僅實(shí)驗(yàn)數(shù)據(jù)集不一樣。聚類指標(biāo)隨文檔數(shù)量變化如圖3所示。

圖3 聚類指標(biāo)隨文檔數(shù)量變化圖

實(shí)驗(yàn)結(jié)果中，紅色線數(shù)據(jù)為K-means 算法，采用隨機(jī)化初始化，藍(lán)色線數(shù)據(jù)為CDP算法。實(shí)驗(yàn)表明在文本類別不變的情況下，文檔的數(shù)量增加也會(huì)導(dǎo)致聚類的F1 值下降。數(shù)據(jù)顯示在K 值不變的情況下，兩類對(duì)比實(shí)驗(yàn)的召回率R 值都在90%左右變動(dòng)，精確率P 隨著文檔數(shù)量的增加而逐漸下降，從而導(dǎo)致F1 值的下降。說(shuō)明文檔聚類會(huì)隨著文檔集數(shù)量增加而降低，兩類對(duì)比實(shí)驗(yàn)的F1 值下降程度都較為穩(wěn)定。

4.3.4 綜合對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)四：本實(shí)驗(yàn)選擇兩組數(shù)據(jù)，第一組為5 個(gè)類別，每個(gè)類別100 篇共500 篇文章；第二類是5 個(gè)類別，每個(gè)類別有400篇共2000篇文章。測(cè)試算法有5種組合：算法1是一種傳統(tǒng)的K-means算法，使用Word2vec 做向量化處理；算法2 是K-means 加BERT 來(lái)處理文本向量化；算法3 是K-means++算法加BERT 來(lái)處理文本到向量的算法；算法4 是最大距離法（MDM）加BERT 處理向量化；算法5 是本文提出的CDP 算法，并結(jié)合BERT 處理文本向量化。每組實(shí)驗(yàn)數(shù)據(jù)集均一致，采用5 種算法，最后多次實(shí)驗(yàn)取均值作為實(shí)驗(yàn)結(jié)果。第一組實(shí)驗(yàn)結(jié)果如表1，第二組結(jié)果如表2。

表1 綜合實(shí)驗(yàn)一

表2 綜合實(shí)驗(yàn)二

根據(jù)表1 和表2 的數(shù)據(jù)，比較算法2、3、4 和算法5，可以判斷CDP 算法在準(zhǔn)確率P 和召回率R 方面均有提升，其F1 值高于其他三種算法；但是該算法耗時(shí)較多，原因是需要計(jì)算文檔數(shù)據(jù)集的密度。由算法1、2 可知，BERT 模型在處理文本轉(zhuǎn)向量方面更加優(yōu)秀。算法1 和算法5 的比較表明，與傳統(tǒng)的K均值文本聚類相比，本文提出的CDP聚類算法有很大的進(jìn)步。

4.4 實(shí)驗(yàn)結(jié)論

結(jié)合以上實(shí)驗(yàn)，在文檔數(shù)據(jù)集上，使用BERT模型對(duì)文本進(jìn)行向量化轉(zhuǎn)換，極大地提高了文本聚類效果。在此基礎(chǔ)上，本文提出的融合密度和劃分的聚類算法進(jìn)一步提升了文本聚類效果。實(shí)驗(yàn)表明，本文提出的融合密度和劃分的文本聚類算法與傳統(tǒng)的K 均值文本聚類算法相比，將F1 值提高超10%，效果顯著且穩(wěn)定。

5 結(jié)語(yǔ)

本文使用BERT 中文模型處理文檔向量化，并使用新提出的融合密度和劃分的聚類算法進(jìn)行文本聚類。與傳統(tǒng)的文本向量化處理相比，BERT 模型在處理文檔向量化方面更為出色；提出融合密度和劃分的文本聚類算法在文檔聚類問(wèn)題上有著優(yōu)秀的表現(xiàn)；但該算法也有一些缺點(diǎn)，聚類類別的增加或文檔數(shù)量的增加將導(dǎo)致文本聚類的效果略有下降，并且文本聚類將花費(fèi)較多時(shí)間。