龔 芝，馬 凌，劉 敏，何先波

(1.湖南信息學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，湖南 長沙 410151；2.西南石油大學(xué) 信息學(xué)院，四川 成都 637001；3.西華師范大學(xué) 計(jì)算機(jī)學(xué)院，四川 南充 637002)

由于文本數(shù)量、文本結(jié)構(gòu)及多語言符號諸多因素影響，文本數(shù)據(jù)挖掘難度不斷提升，而文本聚類作為文本挖掘的核心方法之一，在文本挖掘質(zhì)量提升方面優(yōu)勢明顯[1]，特別是對非標(biāo)簽數(shù)據(jù)挖掘分析貢獻(xiàn)較大。通過聚類，可以有效挖掘海量異構(gòu)多維數(shù)據(jù)之間的關(guān)系，完成離散非標(biāo)簽的數(shù)據(jù)分類，將數(shù)據(jù)進(jìn)行有效歸類整理，提高數(shù)據(jù)的可用性，為各行業(yè)的數(shù)據(jù)模型分析提供技術(shù)支持。在多類別多語言融合的復(fù)合文本聚類過程中文本的特征提取及消歧對文本聚類的準(zhǔn)確度有較大影響[2]，因此對聚類樣本的特征預(yù)處理顯得尤為重要。當(dāng)前的聚類性能提升研究，一方面是從平臺部署角度出發(fā)，通過超強(qiáng)運(yùn)算的云平臺及并行技術(shù)提高大規(guī)模聚類效率，另一方面是尋求適用度更強(qiáng)的算法來提高聚類的準(zhǔn)確度和穩(wěn)定性，本文研究主要集中在后者。

當(dāng)前，關(guān)于文本聚類挖掘方面的研究較多。張旭等[3]從新聞文本入手，詳細(xì)分析了樣本的不同特征選擇對聚類性能影響明顯，合適的特征訓(xùn)練有助于提高聚類準(zhǔn)確度。殷碩等[4]重點(diǎn)分析了語義特征提取方法，并證明了文本特征語義對聚類效果影響明顯。這兩者都闡述了文本特征有效提取對聚類性能影響較大。知識圖譜采用概念、實(shí)體和關(guān)系的三元模型，可以有效地分析文本的核心概念及關(guān)鍵內(nèi)容，得到文本的所有知識元節(jié)點(diǎn)。相比于文本分詞后立即聚類，通過知識圖譜建模后對知識元節(jié)點(diǎn)聚類，可以獲得更高的聚類準(zhǔn)確度。因此，本文借助知識圖譜技術(shù)，將待聚類的文本特征進(jìn)行有效提取、整合和評價(jià)，獲得更精準(zhǔn)有效的文本特征，然后通過近鄰傳播(Affinity propagation，AP)聚類算法實(shí)現(xiàn)文本聚類，并采用差分進(jìn)化(Differential evolution，DE)的偏向參數(shù)優(yōu)化策略對AP算法進(jìn)行聚類增強(qiáng)，提高其在文本挖掘聚類中的準(zhǔn)確度。

1 知識圖譜

知識圖譜技術(shù)結(jié)構(gòu)主要是通過知識集合分類，對知識單元抽取[5]，然后整合及評估獲得知識圖譜，其主要結(jié)構(gòu)如圖1所示。

圖1 知識圖譜技術(shù)結(jié)構(gòu)

如圖2所示，知識圖譜采用概念(Concept)、實(shí)體(Entity)、關(guān)系(Relation)和屬性(Attribute)[6]來表示知識，知識圖譜的構(gòu)成要素為知識元。

知識域d內(nèi)的知識元集合KE d可表述為[6]:K E d={ke1，ke2，…，ke i，…，ke n}，其中第i個(gè)元素kei可表述為ke i={ci，ei，r i，a i}，其中ci、ei、r i和a i分別表示概念知識、實(shí)體知識、關(guān)系知識和屬性知識。知識域d內(nèi)的概念、實(shí)體和關(guān)系集合C d、E d和R d

[7]，分別表述為:C d={c1，c2，…，c k，…，cnc}、E d={e1，e2，…，ek，…，e ne}和R d={r1，r2，…，r k，…，r nr}，概率c i根據(jù)其包含的屬性可以表述為:Aci={a1，a2，…，a j，…a na}，其中nc、ne、nr和na分別代表概念、實(shí)體、關(guān)系和屬性總數(shù)。

圖2 知識圖譜結(jié)構(gòu)

對復(fù)雜文本首先進(jìn)行知識集合分類，接著進(jìn)行知識單元解析，最后提取知識單元包含的知識元及圖譜，通過逐層分析，獲得知識圖譜。

2 文本聚類算法

2.1 AP聚類

AP聚類的數(shù)學(xué)描述如下:設(shè)2個(gè)待聚類的樣本i與j，其兩者之間相似程度S(i，j)可用以下公式表示[8]

根據(jù)式(1)求解任意兩個(gè)樣本點(diǎn)的相似度值，組成樣本相似矩陣，其中對角線元素稱為偏向參數(shù)P，P值對聚類類別數(shù)影響較大，在實(shí)際應(yīng)用時(shí)對聚類性能影響敏感度高。

設(shè)r(i，j)和a(i，j)分別表示樣本i與j的吸引度函數(shù)和隸屬度函數(shù)，點(diǎn)i和j的相似程度與r(i，j)＋a(i，j)的值呈正比，求解任意2個(gè)樣本點(diǎn)的吸引度和隸屬度，將其組成矩陣R=[r(i，j)]N×N和A=[a(i，j)]N×N。

關(guān)于r(i，j)和a(i，j)的求解方法為[9]

r(j，j)為節(jié)點(diǎn)j的自吸引度，j′表示除了j的其他樣本點(diǎn)，i′表示除了i和j的其他樣本點(diǎn)。

當(dāng)i=j時(shí)，式(3)變?yōu)閇10]

對式(2)兩邊都加上a(i，j)，則有

設(shè)E=[e(i，j)]N×N=[r(i，j)＋a(i，j)]N×N，E=R＋A稱為決策陣，設(shè)Γ=[τ(i，j)]N×N=[s(i，j)＋a(i，j)]N×N，Γ=S＋A為潛力陣，則式(5)變?yōu)?/p>

求解e(i，j)最大值，獲得樣本點(diǎn)之間的最大相似程度，樣本點(diǎn)與某簇中心相似程度越高，則表示這個(gè)節(jié)點(diǎn)屬于這個(gè)簇，逐一求解各節(jié)點(diǎn)至各簇中心點(diǎn)的e(i，j)最大值，便能獲得所有點(diǎn)的聚類類別。

2.2 DE算法

設(shè)種群規(guī)模為N，屬性維度為D，差分縮放因子為F，交叉速率CR，每個(gè)個(gè)體的取值為[Umin，Umax]，則第i個(gè)個(gè)體 的j維屬性可表示為[11]

式中:i=1，2，…，N；j=1，2，…，D；rand為(0，1)隨機(jī)數(shù)。

設(shè)第G代的個(gè)體(i=1，2，…，N)的變異操作得到的G＋1代個(gè)體為[12]

式中:i≠r1≠r2≠r3，r1、r2和r3為第G代中除了編號為i的個(gè)體之外的隨機(jī)3個(gè)個(gè)體；F常見取值[0，2]。

個(gè)體交叉方法為[13]

式中:f表示適應(yīng)度函數(shù)。當(dāng)達(dá)到最大代數(shù)Gmax時(shí)，DE算法停止。

2.3 DE-AP聚類流程

首先，對文本進(jìn)行知識圖譜分析，生成包含知識圖譜四元組的樣本集合，然后進(jìn)行DE-AP聚類。根據(jù)樣本集合構(gòu)建相似度矩陣，初始化偏向參數(shù)，接著通過DE算法進(jìn)行偏向參數(shù)優(yōu)化，以簇內(nèi)各節(jié)點(diǎn)的相似度之和作為適應(yīng)度函數(shù)，求解DE的適應(yīng)度最優(yōu)個(gè)體即為最優(yōu)偏向參數(shù)，最后通過最優(yōu)偏向參數(shù)求解AP聚類結(jié)果。具體流程如圖3所示。

圖3 基于知識圖譜的DE-AP聚類流程

3 實(shí)例仿真

為了驗(yàn)證DE-AP算法的數(shù)據(jù)聚類挖掘性能，進(jìn)行實(shí)例仿真。仿真數(shù)據(jù)來源為某大型新聞門戶平臺，首先驗(yàn)證知識圖譜對大規(guī)模多樣化樣本的聚類影響，對聚類結(jié)果進(jìn)行可視化展示；然后分別采用AP算法和DE-AP算法進(jìn)行聚類性能仿真，對比2種算法的準(zhǔn)確率和均方根誤差(Root mean squared error，RMSE)性能；最后將常用聚類算法和本文算法進(jìn)行聚類性能對比仿真。

在進(jìn)行聚類訓(xùn)練時(shí)，4種樣本集的訓(xùn)練和測試個(gè)數(shù)比為3∶1。DE算法的主要參數(shù)取值C R=0.1，F(xiàn)=0.1。

3.1 知識圖譜對DE-AP的聚類性能影響

為了驗(yàn)證知識圖譜對DE-AP的聚類影響，分別采用DE-AP和知識圖譜DE-AP算法對表1中的數(shù)據(jù)集進(jìn)行性能仿真，并對聚類結(jié)果進(jìn)行可視化，考慮到篇幅原因，在此僅選擇體育和歷史樣本集的可視化結(jié)果進(jìn)行展示，如圖4-7所示。

表1 仿真文本集

圖4 DE-AP聚類可視化(體育樣本集)

圖5 知識圖譜＋DE-AP聚類可視化(體育樣本集)

圖6 DE-AP聚類可視化(歷史樣本集)

圖7 知識圖譜＋DE-AP聚類可視化(歷史樣本集)

從上述4圖可知，經(jīng)過了知識圖譜處理之后，對于體育和歷史樣本集，聚類類別數(shù)更趨近于實(shí)際值，而未經(jīng)過知識圖譜分析之前，體育和歷史的聚類類別數(shù)分別為6和6，遠(yuǎn)小于實(shí)際類別10和11，聚類誤差較大，這表明聚類文本通過知識圖譜的分析之后，DE-AP算法的聚類準(zhǔn)確度得到明顯提升。

3.2 DE的優(yōu)化性能

為了驗(yàn)證DE算法在AP文本數(shù)據(jù)聚類挖掘中的性能，分別采用基于知識圖譜的AP算法和DE-AP算法對表1中的文本進(jìn)行聚類，聚類準(zhǔn)確率結(jié)果如圖8所示。

圖8 AP和DE-AP的聚類準(zhǔn)確率

由圖8對比得出，在5個(gè)數(shù)據(jù)集的聚類挖掘中，基于知識圖譜的DE-AP聚類性能明顯由于AP算法性能，DE-AP算法的5個(gè)數(shù)據(jù)集的聚類準(zhǔn)確率均高于0.9，而AP算法在歷史類數(shù)據(jù)集上聚類準(zhǔn)確率僅為0.7，其他4類保持在0.8左右，這表明DE算法對偏向參數(shù)的優(yōu)化，有效地提高了AP算法的文本聚類準(zhǔn)確率；從聚類時(shí)間方面來看，引入了DE的偏向參數(shù)優(yōu)化，增加了耗時(shí)，但相比于整個(gè)聚類時(shí)間來看，DE優(yōu)化的時(shí)間較少，AP和DE-AP算法達(dá)到穩(wěn)定的時(shí)間相差較小。

下面將繼續(xù)對AP和DE-AP的算法穩(wěn)定性進(jìn)行仿真，分別驗(yàn)證2種算法的聚類準(zhǔn)確率RMSE性能，具體統(tǒng)計(jì)結(jié)果如表2所示。

從表2可知，在5類數(shù)據(jù)集中，DE-AP算法的RMSE值比AP算法更小，表明DE-AP算法的聚類準(zhǔn)確率更穩(wěn)定，經(jīng)過了DE的偏向參數(shù)優(yōu)化，DE-AP算法的文本聚類更穩(wěn)定，這主要是因?yàn)榻?jīng)過偏向參數(shù)優(yōu)化，降低了AP算法聚類的震蕩程度，不再因?yàn)槠騾?shù)的變化而造成聚類性能大幅震蕩。

表2 AP和DE-AP的聚類準(zhǔn)確率RMSE

3.3 不同算法的聚類性能

分別采用常用文本聚類算法K-means[14]、K-modes[15]、卷積神經(jīng)網(wǎng)絡(luò)(Convolutional neural network，CNN)[16]和基于知識圖譜的DE-AP對表1中的數(shù)據(jù)進(jìn)行仿真，統(tǒng)計(jì)其平均聚類準(zhǔn)確率和RMSE。

從表3可以看出，在4種樣本集的聚類準(zhǔn)確率方面，DE-AP算法最優(yōu)，聚類準(zhǔn)確率均在0.9以上，CNN算法次之，而K-means和K-modes算法較差，均在0.8以下。而從數(shù)據(jù)集橫向?qū)Ρ?，其?種算法在IT集的文本聚類準(zhǔn)確率最高，而歷史樣本集聚類準(zhǔn)確率最差，這可能與樣本集所包含的屬性個(gè)數(shù)有關(guān)系，當(dāng)屬性越多，數(shù)據(jù)聚類的難度隨之攀升，準(zhǔn)確率也相應(yīng)下降，歷史樣本集的屬性數(shù)明顯高于IT樣本集。

表3 4種算法的聚類準(zhǔn)確率

從表4可以看出，在4類數(shù)據(jù)集的聚類準(zhǔn)確率RMSE性能方面，DE-AP的RMSE值最小，CNN次之，K-modes最差，這說明DE-AP的聚類準(zhǔn)確率的穩(wěn)定性最高，而且對比Max、Min和Mean，DE-AP算法3者的值更聚合，表明這個(gè)算法在這4類樣本集的文本聚類中穩(wěn)定性高，相比于其他3種算法，聚類穩(wěn)定性優(yōu)勢明顯。

表4 4種算法的聚類準(zhǔn)確率RMSE

4 結(jié)束語

將基于知識圖譜的DE-AP聚類算法應(yīng)用于文本聚類，能夠獲得較高的聚類準(zhǔn)確率。通過合理設(shè)置DE算法的差分縮放因子和交叉速率，求解AP算法的偏向參數(shù)；通過DE算法求解的最優(yōu)偏向參數(shù)進(jìn)行AP文本聚類。與常用聚類算法對比，基于知識圖譜的DE-AP聚類算法能夠獲得更高的聚類準(zhǔn)確率。后續(xù)研究將在聚類的效率方面進(jìn)行展開，考慮引用Hadoop云平臺，將知識圖譜分析和DE-AP聚類分布式進(jìn)行，以提高聚類效率。