曹大為，賀超波，陳啟買(mǎi)，劉 海

(1.華南師范大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510631； 2.仲愷農(nóng)業(yè)工程學(xué)院 信息科學(xué)技術(shù)學(xué)院，廣州 510225)(*通信作者電子郵箱chenqimai@scnu.edu.cn)

0 引言

近年來(lái)，隨著社交網(wǎng)絡(luò)和電子商務(wù)的快速發(fā)展，涌現(xiàn)了大量短文本形式的互聯(lián)網(wǎng)內(nèi)容，例如Twitter、微博、微信和在線(xiàn)評(píng)論等。對(duì)短文本進(jìn)行聚類(lèi)有著廣泛的應(yīng)用價(jià)值，例如可以利用用戶(hù)對(duì)商品的評(píng)論推薦商品[1]，利用Twitter進(jìn)行用戶(hù)職業(yè)的推測(cè)[2]等。由于短文本過(guò)于簡(jiǎn)短，冗余度高，導(dǎo)致存在特征詞提取困難和特征稀疏的問(wèn)題[3]。大多數(shù)特征詞在短文本中只出現(xiàn)一次，使得傳統(tǒng)的基于詞頻(Term Frequency, TF)和詞頻逆向文件頻率(Term Frequency-Inverse Document Frequency, TF-IDF)的聚類(lèi)算法包括K-means、隱含狄利克雷分布(Latent Dirichlet Allocation, LDA)等對(duì)短文本難以有效處理，為此需要研究專(zhuān)門(mén)的短文本聚類(lèi)算法。目前已存在一些對(duì)于短文本聚類(lèi)算法的研究，其中具有代表性的工作包括：Banerjee等[4]利用維基百科的信息擴(kuò)充短文本的特征，F(xiàn)odeh等[5]利用本體中的語(yǔ)義知識(shí)來(lái)優(yōu)化聚類(lèi)，Efron等[6]和Tang等[7]擴(kuò)充短文本以改善信息檢索和聚類(lèi)效果，以及Hu等[8]利用WordNet對(duì)特征詞進(jìn)行豐富和擴(kuò)充等。近幾年，隨著深度學(xué)習(xí)和神經(jīng)網(wǎng)絡(luò)的發(fā)展，出現(xiàn)了一些基于神經(jīng)網(wǎng)絡(luò)的短文本聚類(lèi)算法，例如Kim[9]提出將詞向量輸入進(jìn)卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行模型訓(xùn)練，周飛燕等[10]提出利用動(dòng)態(tài)卷積神經(jīng)網(wǎng)絡(luò)對(duì)句子的語(yǔ)義進(jìn)行建模等?？偟膩?lái)說(shuō)，現(xiàn)有的短文本聚類(lèi)算法在一定程度上進(jìn)行了優(yōu)化，但由于需要外部知識(shí)的依賴(lài)或者需要建立復(fù)雜的神經(jīng)網(wǎng)絡(luò)處理模型，導(dǎo)致聚類(lèi)過(guò)程過(guò)于繁雜。為此，本文提出一種基于加權(quán)核非負(fù)矩陣分解(Weighted Kernel Nonnegative Matrix Factorization，WKNMF)的短文本聚類(lèi)算法，該算法利用核方法的映射關(guān)系將稀疏特征空間映射到高維隱性空間，從而可以直接利用文本中的隱性語(yǔ)義特征；同時(shí)可以利用非負(fù)矩陣分解(Nonnegative Matrix Factorization, NMF)具有的強(qiáng)大聚類(lèi)能力直接進(jìn)行文本聚類(lèi)。本文工作包括：1)將NMF與核方法(Kernel method)相結(jié)合，設(shè)計(jì)出一種新的短文本聚類(lèi)模型，該模型以NMF為基礎(chǔ)，利用核技巧大大簡(jiǎn)化了運(yùn)算復(fù)雜度；2)通過(guò)迭代更新規(guī)則對(duì)短文本權(quán)重進(jìn)行動(dòng)態(tài)調(diào)整，以?xún)?yōu)化不同短文本對(duì)聚類(lèi)的影響程度；3)在微博短文本數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)，結(jié)果表明WKNMF的聚類(lèi)質(zhì)量要好于現(xiàn)有的代表性算法。

1 相關(guān)工作

1.1 非負(fù)矩陣分解

NMF是一種低秩近似分解模型[11]，該模型主要在矩陣分解的基礎(chǔ)上增加一個(gè)非負(fù)的限定。假設(shè)矩陣X為矩陣，NMF可以通過(guò)兩個(gè)非負(fù)矩陣W和H的乘積來(lái)近似表示X:

X=WH

(1)

(2)

由于F范數(shù)計(jì)算方便，可解釋性強(qiáng)，通常使用F范數(shù)作目標(biāo)函數(shù)。而目標(biāo)函數(shù)對(duì)于W和H是非凸的，一般很難求得全局最優(yōu)解，但可以使用梯度下降、最小二乘和乘性更新等優(yōu)化方法進(jìn)行求解。

NMF具有數(shù)據(jù)降維的功能，而且具有良好的可解釋性，使得它具有廣泛的應(yīng)用。例如，利用NMF進(jìn)行音頻中噪聲數(shù)據(jù)的去除[12]、文本流主題層次的檢測(cè)和跟蹤[13]，利用NMF對(duì)彩色圖像的聚類(lèi)評(píng)價(jià)[14]和復(fù)雜網(wǎng)絡(luò)重構(gòu)[15]等。此外，NMF被證明與K-means算法具有緊密關(guān)系，且具有強(qiáng)大的聚類(lèi)能力，可以應(yīng)用于文本聚類(lèi)。例如最早提出的基于NMF的文本聚類(lèi)[16]，以及后續(xù)基于NMF改進(jìn)的相關(guān)文本聚類(lèi)算法[17-18]，都取得了不錯(cuò)的效果。但現(xiàn)有基于NMF的文本聚類(lèi)算法大多面向長(zhǎng)文本，很少應(yīng)用于短文本。

1.2 核函數(shù)與核技巧

核函數(shù)是從低維空間到高維空間的一種映射函數(shù)。設(shè)X是輸入空間(歐氏空間Rn的子集或離散集合)，又設(shè)B為特征空間(希爾伯特空間)，如果存在從原始空間到更高維空間的映射，即從R到B的映射：

φ(X):R→B

(3)

則稱(chēng)該映射過(guò)程稱(chēng)為核方法。對(duì)任意的x,y∈X，函數(shù)k(x,y)滿(mǎn)足條件：

k(x,y)=(φ(x))Tφ(y)

(4)

即稱(chēng)k(x,y)為核函數(shù)。

核技巧的核心是繞過(guò)運(yùn)算映射函數(shù)φ，通過(guò)定義低維度運(yùn)算的核函數(shù)k(x,y)來(lái)表示高維度φ(x)和φ(y)的內(nèi)積，從而完美地解決了φ(x)難于計(jì)算的問(wèn)題。通常滿(mǎn)足Mercer定理[19]，即定義任何半正定的函數(shù)都可以作為核函數(shù)。常用的核函數(shù)有線(xiàn)性核、多項(xiàng)式核、高斯核以及Sigmoid核等，分別定義如下：

k(x,y)=xTy

(5)

k(x,y)=(1+xTy)d

(6)

(7)

k(x,y)=tanh(αxty+c)

(8)

矩陣形式的核函數(shù)如式(9)所示:

(9)

2 基于WKNMF的短文本聚類(lèi)

2.1 短文本聚類(lèi)模型

(10)

實(shí)際上，短文本聚類(lèi)不僅僅需要利用文本中出現(xiàn)的顯式的詞項(xiàng)特征(如TF、TF-IDF值)進(jìn)行聚類(lèi)，同時(shí)也不能忽略短文本中潛在的語(yǔ)義特征，但一般隱性的語(yǔ)義特征和短文本中的詞項(xiàng)是非線(xiàn)性的關(guān)系。雖然NMF能通過(guò)處理顯性的詞項(xiàng)特征進(jìn)行文本聚類(lèi)，但是忽略了短文本中的隱性語(yǔ)義特征。為此，可以利用核函數(shù)高維映射的特點(diǎn)來(lái)表示非線(xiàn)性的特征，從而可以利用短文本的隱性語(yǔ)義特征進(jìn)行短文本聚類(lèi)。

首先定義從傳統(tǒng)特征空間到更高維特征空間的映射：

φ:D∈R→φ(D)∈H

(11)

其中φ(D)={φ(d1),φ(d2), …,φ(dM)}?？紤]到不同的短文本對(duì)聚類(lèi)影響的差異，為短文本增加一個(gè)權(quán)重μ={μ1,μ2,…,μm}，得到Dμ={μ1d1,μ2d2,…,μmdm}，以區(qū)分不同的短文本對(duì)聚類(lèi)的影響，即：

φ(Dμ)={φ(μ1d1),φ(μ2d2),…,φ(μmdm)}

在理論基礎(chǔ)研究方面，段金菊等人在《學(xué)習(xí)科學(xué)視域下的e-learning深度學(xué)習(xí)研究》一文中以深度學(xué)習(xí)的內(nèi)涵與特征、高水平思維是深度學(xué)習(xí)的核心等理念為依據(jù)，構(gòu)建了e-learning環(huán)境下深度學(xué)習(xí)分析模型，強(qiáng)調(diào)基于學(xué)習(xí)科學(xué)視角的情境認(rèn)知理論、分布式認(rèn)知理論、建構(gòu)主義學(xué)習(xí)理論、聯(lián)通主義學(xué)習(xí)理論及元認(rèn)知理論為深度學(xué)習(xí)提供了理論支持[5]。

(12)

利用NMF找到k個(gè)向量Uφ和系數(shù)矩陣H來(lái)表示高維映射空間φ(Dμ)，即

φ(Dμ)≈UφH

(13)

其中Uφ表示分解矩陣中的核基矩陣，公式如下：

Uφ={φ(u1),φ(u2),…,φ(uk)}

(14)

因而可以得WKNMF短文本聚類(lèi)模型：

(15)

2.2 模型求解與聚類(lèi)算法

通過(guò)利用核技巧，使用梯度下降對(duì)式(15)進(jìn)行優(yōu)化求解。本文采用的核函數(shù)為高斯核函數(shù)。

(16)

(17)

(18)

(19)

其中max函數(shù)可以保證更新矩陣U的非負(fù)性，而其中αt=βs，即β的s次方，s為滿(mǎn)足式(20)的最小正整數(shù)：

(20)

(21)

Lφ(φ(Dμ),UφHt+1)-Lφ(φ(Dμ),UφHt)≤

(22)

在第t+1次更新Ut+1、Ht+1后，對(duì)權(quán)重向量μ進(jìn)行更新：

(23)

每次迭代更新U和H后進(jìn)行全局的收斂判斷：

(24)

其中ε為超參數(shù)，如果設(shè)置過(guò)小，可能無(wú)法滿(mǎn)足式(24)的條件，這就需要設(shè)置迭代次數(shù)上限進(jìn)行控制；如果設(shè)置過(guò)大，準(zhǔn)確率則會(huì)下降。因此迭代過(guò)程中滿(mǎn)足式(24)或者達(dá)到迭代次數(shù)上限，即可停止迭代。通常迭代上限一般設(shè)置為500。根據(jù)以上設(shè)計(jì)思路，本文設(shè)計(jì)了基于WKNMF的短文本聚類(lèi)算法：

算法 基于WKNMF的短文本聚類(lèi)算法。

輸入D,U,H,μ,β,σ,ε,k,t;

輸出c={c1,c2,…,ck}。

1)

2)

設(shè)置損失函數(shù)(15)

3)

While 不滿(mǎn)足式(24) or 迭代次數(shù)不超過(guò)tdo

4)

根據(jù)式(19)更新U

5)

根據(jù)式(21)更新H

6)

根據(jù)式(23)更新

7)

End While

8)

i=1

9)

Whilei

10)

j=arg max(hi)

//判斷短文本di所屬聚類(lèi)

11)

cj=cj∪{di}

12)

i++

13)

End While

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

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

本文利用爬蟲(chóng)系統(tǒng)爬取了新浪微博在2014年04月30日至2014年05月12日關(guān)于12個(gè)主題的微博信息作為實(shí)驗(yàn)數(shù)據(jù)集，共有84 413條，每個(gè)類(lèi)別微博的數(shù)量如表1所示。

為驗(yàn)證該數(shù)據(jù)集的顯式詞項(xiàng)特征的稀疏性，對(duì)短文本去除停用詞后進(jìn)行特征詞的TF計(jì)算，其分布結(jié)果如表2所示。經(jīng)統(tǒng)計(jì)，文本的詞頻只出現(xiàn)1次的占91.3%，因而需要利用短文本的潛在語(yǔ)義特征進(jìn)行聚類(lèi)。

表1 微博數(shù)據(jù)集

表2 微博數(shù)據(jù)集的TF值分布

3.2 算法比較與評(píng)價(jià)準(zhǔn)則

采用K-means[25]、LDA[26]、NMF和自組織神經(jīng)網(wǎng)絡(luò)(Self-Organization Map, SOM)[27]四種聚類(lèi)算法與WKNMF短文本聚類(lèi)算法進(jìn)行比較，其中K-means、LDA、NMF和WKNMF設(shè)置相同的k值進(jìn)行比較。SOM算法將高維數(shù)據(jù)集在保持原始分布特征的基礎(chǔ)上映射到低維的拓?fù)浣Y(jié)構(gòu)中，能形成低維的特征拓?fù)渚W(wǎng)絡(luò)。低維拓?fù)渚W(wǎng)絡(luò)包括正方形網(wǎng)格和正六邊形網(wǎng)格的平面結(jié)構(gòu)，比如利用10×10的正方形網(wǎng)格構(gòu)成的二維拓?fù)渚W(wǎng)絡(luò)。由于拓?fù)浣Y(jié)構(gòu)的差異會(huì)影響短文本的聚類(lèi)效果，對(duì)此，實(shí)驗(yàn)分別采用20×20、15×15和10×10的正六邊形網(wǎng)格和正方形網(wǎng)格分別對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)，最后和WKNMF聚類(lèi)的最優(yōu)值進(jìn)行比較。

采用準(zhǔn)確率(Accuracy, AC)和NMI(Normalized Mutual Information, NMI)兩種評(píng)價(jià)準(zhǔn)則[16]。假設(shè)文檔di的聚類(lèi)標(biāo)簽和文本標(biāo)簽分別為ci和pi，則AC定義為：

(25)

其中：n代表測(cè)試文檔的總數(shù)；δ(a,b)函數(shù)當(dāng)a=b時(shí)為1，否則為0；map(pi)是一個(gè)映射函數(shù)，表示將pi映射到相應(yīng)的文本標(biāo)簽上，一般映射方法采用KM(Kuhn-Munkres)算法[28]。

假設(shè)短文本聚類(lèi)結(jié)果以及已知的聚類(lèi)結(jié)果集合分別為c和p,可以構(gòu)建混淆矩陣N=[nij]|c|×|p|，其中表示c中第i個(gè)聚類(lèi)與p中第j個(gè)聚類(lèi)的重疊數(shù)量，則NMI的定義為：

(26)

其中：n*j和ni*分別表示矩陣N的第j列和第i行的和。AC和NMI的值越大，表示短文本聚類(lèi)的質(zhì)量越高。

3.3 參數(shù)設(shè)置

算法中存在一些超參數(shù)，如β和ε，它們的取值對(duì)算法的效率和結(jié)果有很大的影響。如較大的β值會(huì)使算法迭代次數(shù)變少，但精確度下降；而較小的β值雖然減小了步長(zhǎng)，但過(guò)小的取值會(huì)使步長(zhǎng)變得太小，反而增加了迭代次數(shù)。ε取值過(guò)小會(huì)導(dǎo)致很大的迭代次數(shù)，而取值接近1又可能導(dǎo)致迭代過(guò)早結(jié)束等。所以這些參數(shù)都需要?jiǎng)討B(tài)確定，先在一個(gè)較小的數(shù)據(jù)集(原始數(shù)據(jù)集中隨機(jī)抽取的子集)中動(dòng)態(tài)優(yōu)化這些參數(shù)，使結(jié)果盡量接近最優(yōu)。實(shí)驗(yàn)隨機(jī)選取數(shù)據(jù)集中不同主題的微博各100篇共計(jì)1 200篇，選取β和ε這兩個(gè)重要參數(shù)進(jìn)行測(cè)試和調(diào)整，β取值為0到1，ε值為0到0.01，以Accuracy和NMI為結(jié)果進(jìn)行關(guān)聯(lián)性測(cè)試。圖1和圖2以三維折線(xiàn)圖的形式展示了參數(shù)β和ε同時(shí)對(duì)實(shí)驗(yàn)結(jié)果的影響。

圖1 參數(shù)β和ε對(duì)Accuracy的影響

圖2 參數(shù)β和ε對(duì)NMI的影響

由圖1和圖2可知，參數(shù)對(duì)實(shí)驗(yàn)結(jié)果有很大影響，而且當(dāng)β在0.5、ε在0.005左右時(shí)Accuracy和NMI達(dá)到峰值。此后即可將β=0.5和ε=0.005應(yīng)用到原始數(shù)據(jù)集中去，以有效地減少計(jì)算量。

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

對(duì)K-means、LDA、NMF和WKNMF設(shè)置相同的k值進(jìn)行比較，而SOM算法由于無(wú)需設(shè)置k值，可以單獨(dú)與WKNMF進(jìn)行比較。圖4和圖5分別為K-means、LDA、NMF和WKNMF在不同k值時(shí)的Accuracy和NMI的對(duì)比情況，可以看出：在k值接近數(shù)據(jù)集原有類(lèi)別時(shí)，WKNMF均具有最好的Accuracy和NMI，而傳統(tǒng)的K-means算法表現(xiàn)最差。因?yàn)樵紨?shù)據(jù)是12類(lèi)，所以當(dāng)k在12左右時(shí)各算法的Accuracy和NMI都達(dá)到最大。

圖3 各算法的Accuracy對(duì)比

圖4 各算法的NMI對(duì)比

SOM算法不需要手動(dòng)設(shè)置k值，可以設(shè)置不同的拓?fù)浣Y(jié)構(gòu)進(jìn)行對(duì)比。實(shí)驗(yàn)分別采用20×20、15×15和10×10的正六邊形和正方形二維拓?fù)浣Y(jié)構(gòu)分別對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)。表3是SOM中不同拓?fù)浣Y(jié)構(gòu)和WKNMF中效果最好情況的對(duì)比結(jié)果。從表3可以明顯地看出，以Accuracy和NMI為評(píng)價(jià)指標(biāo)，WKNMF的聚類(lèi)質(zhì)量要明顯好于各種拓?fù)浣Y(jié)構(gòu)的SOM算法，而拓?fù)浣Y(jié)構(gòu)為10×10正方形的聚類(lèi)質(zhì)量最差。

表3 SOM與WKNMF的對(duì)比

4 結(jié)語(yǔ)

對(duì)互聯(lián)網(wǎng)產(chǎn)生的大量短文本進(jìn)行聚類(lèi)分析具有重要的應(yīng)用價(jià)值，本文為此提出了一種基于加權(quán)核非負(fù)矩陣分解的短文本聚類(lèi)算法WKNMF。通過(guò)使用新浪微博數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果表明相比典型的聚類(lèi)算法K-means、LDA、NMF和SOM，WKNMF具有更好的短文本聚類(lèi)質(zhì)量。由于實(shí)驗(yàn)僅選取了高斯核函數(shù)進(jìn)行計(jì)算和推導(dǎo)，而沒(méi)有分析其他核函數(shù)，所以在下一步工作中將進(jìn)一步驗(yàn)證WKNMF使用其他核函數(shù)在短文本上的聚類(lèi)質(zhì)量。此外，由于WKNMF本質(zhì)上屬于基于內(nèi)存計(jì)算的算法，它涉及的矩陣迭代更新計(jì)算也適合采用Spark分布式內(nèi)存計(jì)算框架實(shí)現(xiàn)，因此會(huì)進(jìn)一步研究基于Spark的WKNMF的實(shí)現(xiàn)方法，以通過(guò)進(jìn)一步提高算法的運(yùn)算效率來(lái)處理更大規(guī)模的短文本聚類(lèi)問(wèn)題。