基于知識圖譜的k-modes文本聚類研究

高 靜，王 鋼

(鄭州商學院 信息與機電工程學院，河南 鞏義 451200)

數(shù)據(jù)挖掘技術全面推廣，各行業(yè)領域運行及管理迎來新的發(fā)展機遇。聚類作為數(shù)據(jù)挖掘的重要技術方法，解決了非標簽的數(shù)據(jù)分類問題[1]，通過聚類，將文本數(shù)據(jù)進行有效歸類整理，提高數(shù)據(jù)的可用性。

當前網(wǎng)絡中的文本數(shù)據(jù)，由于行業(yè)差異性及文本異構性，所產(chǎn)生的文本要完成精確聚類并不簡單，常因為文本分詞不當或者語義模糊而造成錯誤聚類，若是首先能夠確定文本所處行業(yè)領域，或者能夠確定文本所包含的核心概念，將聚類的領域范圍進一步縮小，將有效提高聚類的有效性。現(xiàn)有文本聚類研究中，楊慧婷等[2]采用k-means算法進行聚類，并采用深度信念網(wǎng)絡進行聚類準確度提升，但由于深度信念網(wǎng)絡收斂需要消耗大量時間，因此該算法的聚類效率并不高;謝娟英等[3]和張志龍等[4]分別采用譜聚類算法和密度峰值聚類算法進行文本分割聚類，解決了復雜文本的聚類問題。

知識圖譜采用概念、實體和關系的三元模型，可以有效地分析文本的核心概念及關鍵內(nèi)容，得到文本的所有知識元節(jié)點。相比于文本的分詞后立即聚類，通過知識圖譜建模后對知識元節(jié)點聚類，可以獲得更高的聚類準確度。因此，本文研究旨在進一步提高聚類準確率，采用知識圖譜進行文本分析預處理，然后通過k-modes算法[5]完成聚類，經(jīng)過知識圖譜分析之后，k-modes能夠獲得更優(yōu)的聚類性能，提高了k-modes算法的聚類適用度。

1 知識圖譜

知識圖譜(Knowledge graph，KG)采用四元組表示知識，其主要包含概念(Concept)、實體(Entity)、關系(Relation)和屬性(Attribute)，以及知識圖譜的構成要素知識元,其結構如圖1所示。

圖1 知識圖譜結構

知識域d內(nèi)包含的知識元[6]為

KEd={ke1，ke2，…，kei，…，ken}

(1)

式中:kei={ci，ei，ri，ai}，KEd表示領域d內(nèi)所有知識元集合，kei表示第i個知識元，其包含概念知識ci、實體知識ei、關系知識ri和屬性知識ai。

其中領域d內(nèi)的概念、實體和關系集合分別為Cd、Ed和Rd[7]

Cd={c1，c2，…，ck，…，cnc}

(2)

Ed={e1，e2，…，ek，…，ene}

(3)

Rd={r1，r2，…，rk，…，rnr}

(4)

式中:nc、ne和nr分別代表概念、實體和關系的總數(shù)。

每個概念ci對應的屬性集合[8]

Aci={a1，a2，…，aj，…ana}

(5)

式中:na表示屬性總數(shù)。

對復雜文本首先進行知識集合分類，接著進行知識單元解析，最后提取知識單元包含的知識元及圖譜，通過逐層分析，獲得知識圖譜，其中知識的規(guī)模結構如圖2所示[9]。

圖2 知識結構組成

2 k-modes聚類

2.1 文本聚類設計

設X={x1，x2，x3，…，xn}，xi(i=1，2，…，n)，其中每個樣本點包含m個屬性。n個樣本被劃分為了k個簇z，則k-modes聚類的目標函數(shù)P(W，Z)[10]

(6)

(7)

式中:ωi，l∈{0，1}，1≤i≤n，1≤l≤k，W為n×k的二進制隸屬矩陣，Z={z1，z2，…，zk}是一個包含k個簇z的k×m簇中心矩陣。

D(xi，zl)為節(jié)點到某個簇中心的距離。k-modes算法距離計算公式[11]為

(8)

(9)

(11)

式中:nzl，j為簇zl的屬性值等于zl，j的樣本個數(shù)。

2.2 聚類流程

首先，所提KGK-modes(Knowledge graph k-modes，KGK-modes)算法將文本進行知識圖譜分析，生成包含知識圖譜四元組的樣本集合，然后進行k-modes聚類。先確定k個簇心，從樣本中隨機選擇k個簇作為聚類中心點，組成初始簇集合Z1，確定W1使得P(W1，Z1)取得最小值，設定t=1。

更新簇點Zt，確定Zt+1使得P(Wt，Zt+1)取最小值，若滿足P(Wt，Zt+1)=P(Wt+1，Zt+1)則停止，否則繼續(xù)更新Wt+1使得P(Wt+1，Zt+1)最小化，若P(Wt，Zt+1)=P(Wt+1，Zt+1)則停止，否則更新簇點[13]。具體流程如圖3所示。

圖3 KGK-modes文本聚類流程

3 實例仿真

為了驗證KGK-modes在文本聚類中的性能，進行性能仿真。實驗仿真的硬件環(huán)境為64位Windows 10操作系統(tǒng)的臺式電腦，CPU為Intel 7，8G內(nèi)存，顯卡為GTX3060;實驗仿真的軟件為MATLAB R2018b。首先驗證知識圖譜對k-modes聚類的性能影響;其次采用常用文本聚類算法和本文算法分別進行文本聚類性能仿真，驗證不同的算法的仿真性能。聚類評價指標主要為純度(Purity，P)、標準互信息(Normalized mutual information，NMI)和F值(F-Value，F(xiàn))。仿真數(shù)據(jù)分別來自于公開的UCI數(shù)據(jù)集和Sogo實驗室的搜狐新聞數(shù)據(jù)集，其具體仿真數(shù)據(jù)如表1和表2所示。

表1 UCI仿真集

表2 新聞文本集

3.1 知識圖譜對k-modes的聚類性能影響

為了驗證知識圖譜對k-modes的聚類影響，分別采用k-modes和KGK-modes算法對表1中的數(shù)據(jù)集進行性能仿真。

3.1.1 UCI數(shù)據(jù)集仿真性能

從表3可以看出，在4種不同數(shù)據(jù)集的聚類過程中，經(jīng)過了知識圖譜的k-modes算法表現(xiàn)出更優(yōu)的性能。橫向?qū)Ρ劝l(fā)現(xiàn)，k-modes算法在seeds數(shù)據(jù)集的聚類純度最高為0.806 1，在Flowers數(shù)據(jù)集的聚類純度最低為0.766 2;而KGK-modes算法在seeds數(shù)據(jù)集的聚類純度最高為0.904 6，在Flowers數(shù)據(jù)集的聚類純度最低為0.882 4，因此2種算法均在seeds數(shù)據(jù)集中聚類性能最優(yōu)，在Flowers數(shù)據(jù)集聚類最差。對比NMI和F性能，經(jīng)過了知識圖譜分析之后，k-modes算法表現(xiàn)出了更優(yōu)的聚類性能，這主要是經(jīng)過知識圖譜分析后，對文本概念、實體和關系的準確劃分在一定程度上確定了樣本類別，降低了后期的k-modes聚類難度，提高了聚類的性能。

表3 2種算法的聚類性能(UCI集)

KGK-modes在UCI的4類數(shù)據(jù)集聚類中，P、NMI和F值方面均表現(xiàn)出良好的性能。為了分析聚類純度的穩(wěn)定性，對2種算法的聚類純度RMSE性能進行仿真，從表1的4個樣本集中隨機抽取1 000個樣本進行聚類仿真，結果如圖4所示。

圖4 2種算法的聚類純度RMSE

從圖4得，隨著聚類迭代次數(shù)增加，2種算法的聚類純度RMSE逐漸下降，對比發(fā)現(xiàn)，KGK-modes對于UCI數(shù)據(jù)集的聚類純度RMSE下降速度更快，最后收斂于0.5左右，而k-modes約收斂于0.75。

為了進一步分析k-modes算法和KGK-modes算法的聚類性能，對2種算法在4個數(shù)據(jù)集上的聚類時間性能進行仿真，統(tǒng)計結果如表4所示。

表4 2種算法的聚類時間(UCI集)

從表4得，2種算法在UCI 4個數(shù)據(jù)集的聚類時間與樣本量關系密切，樣本量最多的iris數(shù)據(jù)集聚類時間最長，樣本量最少的Wine數(shù)據(jù)集聚類時間最短。對比發(fā)現(xiàn)，知識圖譜分析需要消耗一定的時間，因此KGK-modes聚類時間比k-modes聚類時間更長，但兩者相差的時間并不大。

3.1.2 新聞數(shù)據(jù)集仿真

為了驗證知識圖譜對k-modes算法在Sogo新聞文本中的聚類影響，分別采用k-modes和KGK-modes算法對表2中的數(shù)據(jù)集進行性能仿真，如表5所示。

表5 2種算法的聚類性能(新聞集)

從表5可以看出，相比于k-modes算法，經(jīng)過了知識圖譜的k-modes算法在4個新聞樣本集聚類過程中表現(xiàn)出了更優(yōu)的性能。k-modes算法在數(shù)據(jù)集4的聚類純度最高為0.894 6，在數(shù)據(jù)集1的聚類純度最低為0.864 6;而KGK-modes算法在數(shù)據(jù)集4的聚類純度最高為0.952 6，在數(shù)據(jù)集1的聚類純度最低為0.927 5，這表明對于同一類型的樣本集，樣本量越大，聚類純度越高。和UCI數(shù)據(jù)集一樣，經(jīng)過了知識圖譜分析之后，k-modes算法表現(xiàn)出了更優(yōu)的NMI和F性能。對比表3和表5得，2種算法的新聞樣本集聚類性能明顯優(yōu)于UCI 4個樣本集。

對新聞集聚類純度的穩(wěn)定性進行仿真，采用2種算法對表2的數(shù)據(jù)集4聚類純度RMSE性能進行仿真，結果如圖5所示。

圖5 2種算法的聚類純度RMSE

從圖5得，隨著聚類迭代次數(shù)增加，2種算法的聚類純度RMSE下降明顯。KGK-modes的聚類純度RMSE下降速度快于k-modes算法，最后收斂于0.3左右，而k-modes約收斂于0.5。

對k-modes算法和KGK-modes算法聚類時間性能對比仿真，對2種算法在4個數(shù)據(jù)集上的聚類時間性能進行統(tǒng)計，結果如表6所示。

表6 2種算法的聚類時間(新聞集)

從表6得，對于同容量的新聞集，KGK-modes聚類時間比k-modes聚類時間略長，但差距不大。根據(jù)上述結果可以看出，KGK-modes算法在新聞數(shù)據(jù)集上表現(xiàn)出的性能高于UCI數(shù)據(jù)集，主要原因是新聞數(shù)據(jù)集的特征維度明顯少于UCI數(shù)據(jù)集，因此數(shù)據(jù)聚類效果更顯著。

3.2 不同算法的文本聚類性能

為了進一步驗證KGK-modes算法在文本聚類中的性能，分別采用常用文本聚類算法K-means[14]、K-medoid[15]、卷積神經(jīng)網(wǎng)絡(Convolutional neural networks，CNN)[16]和知識圖譜+k-mode算法對表1和2中的數(shù)據(jù)集進行聚類準確率性能仿真。分別從表1中的UCI的4個數(shù)據(jù)集中隨機抽取1 000個樣本進行性能仿真，表2中的數(shù)據(jù)集4參與仿真，結果分別如圖6和7所示。

從圖6得，在UCI的1 000個樣本聚類中，KGK-modes算法聚類準確率最高約為0.9，CNN算法次之，K-means算法聚類準確率最低約為0.78。從收斂性方面看，K-means算法在55 s左右達到穩(wěn)定，而KGK-modes和K-medoids算法兩者聚類穩(wěn)定的時間約為65 s，CNN算法聚類穩(wěn)定時約消耗了70 s。

從圖7得，KGK-modes算法的新聞集聚類準確率最高約為0.94，CNN算法次之，K-means算法最差約為0.81;在聚類時間方面，K-means和K-medoids算法聚類時間最優(yōu)，約在60 s左右達到穩(wěn)定，而KGK-modes算法和CNN算法聚類穩(wěn)定的時間分別為65 s和70 s。

圖7 4種算法的聚類準確率(新聞集)

綜合對比，KGK-modes算法的聚類準確率最高，K-means算法的聚類時間最優(yōu)，本文算法在聚類效率方面還需進一步改進。

4 結束語

采用KGK-modes算法進行本文聚類，獲得了較高的聚類性能，相比于常用文本聚類算法，表現(xiàn)出了較高的聚類純度、NMI和F值性能。后續(xù)研究將在聚類的效率方面進行展開，一方面考慮引用Spark并行聚類平臺，將知識圖譜分析和k-modes聚類并行進行，以降低文本聚類時間，另一方面，優(yōu)化k-modes聚類目標函數(shù)優(yōu)化時間，以提高聚類算法效率，增強KGK-modes在大規(guī)模文本聚類中的適用度。