基于CLSVSM的懲罰性矩陣分解及其在文本主題聚類中的應(yīng)用

牛奉高，馮世佳，黃 琛

(山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院，山西 太原 030006)

0 引 言

大數(shù)據(jù)時代下，信息量飛速增長，通過人工方式快速地在資料中查找有效信息難上加難。文本主題聚類發(fā)揮著不可忽視的作用，它是將一個文本集合劃分成若干互異的簇，從而使每個簇內(nèi)文本之間的相似性較大，而互異簇文本之間的相似性較小[1]。文檔中包含的知識相當(dāng)豐富，聚類之前首先要把無結(jié)構(gòu)的文檔知識表示為計算機(jī)可以識別的數(shù)據(jù)形式[2]。經(jīng)典的文本表示模型是由Salton[3]提出的向量空間模型(VSM)，其文本空間是由一組正交向量所構(gòu)成的向量空間[4]，但其忽視了詞與詞之間的語義關(guān)系，導(dǎo)致文本主題聚類精度不高；Wong[5]針對這一問題提出了一種廣義向量空間模型(Generalized Vector Space Model， GVSM)，挖掘了詞之間的共現(xiàn)信息，但仍未充分提取語義信息；牛奉高等[6]通過共現(xiàn)分析方法深度挖掘詞之間的潛在語義，提出了一種共現(xiàn)潛在語義向量空間模型(Co-occurrence Latent Semantic Vector Space Model， CLSVSM)，其聚類效果優(yōu)于VSM。然而，模型的維數(shù)較高，致使數(shù)據(jù)稀疏和計算復(fù)雜這一問題依舊存在。因此，對其進(jìn)行降維處理是非常必要的。

矩陣分解對數(shù)據(jù)降維非常有效，通過矩陣分解得到原數(shù)據(jù)矩陣的低秩近似，是對原始數(shù)據(jù)內(nèi)在結(jié)構(gòu)特征的刻畫[7]。常見的一種矩陣分解工具是奇異值分解，是很多經(jīng)典算法(如潛在語義分析、主成分分析)的求解方法，在文本挖掘領(lǐng)域被廣泛應(yīng)用。但是一般情況下分解后的左右奇異向量中的元素為正或為負(fù)，沒有0元素，此時結(jié)果通常是不能解釋的[8]。于是，本文將懲罰性矩陣分解應(yīng)用于文本資源，構(gòu)建語義核來實現(xiàn)降維的同時提高聚類算法的性能。

懲罰性矩陣分解(Penalized Matrix Decomposition, PMD)是在2009年由Witten等[8]提出，并將其應(yīng)用于稀疏主成分分析和典型相關(guān)性分析。此后，學(xué)者們將該方法應(yīng)用于多個領(lǐng)域。Zhang等[9]利用PMD從微陣列數(shù)據(jù)中發(fā)現(xiàn)轉(zhuǎn)錄模塊。Zheng等[10]將PMD應(yīng)用于基因表達(dá)。王娟等[11]提出了一種基于PMD的文本軟聚類算法，并用實驗證明該方法在信息檢索方面的效果。Liu等[12]提出了利用PMD稀疏方法來提取核心基因，并用實驗證明了該方法的有效性。俞仙子等[13]提出了一種基于PMD的文本核心特征詞提取方法，并證實得到的核心特征詞更易被解釋。邵作運等[14]實現(xiàn)了共詞分析中基于PMD的特征詞提取、軟聚類和可視化。隨后，Liu等[15]引入了全局散度矩陣，提出了基于類別信息的PMD。懲罰性矩陣分解，是對向量進(jìn)行稀疏化懲罰，隨后這種方法被廣泛應(yīng)用[16]。

1964年，Ajzerman等[17]探究勢函數(shù)時，在機(jī)器學(xué)習(xí)中引進(jìn)核函數(shù)，它的引入在一定程度上促進(jìn)了支持向量機(jī)(SVM)的進(jìn)步。此后，許多學(xué)者將核函數(shù)方法與聚類算法相結(jié)合[18]。核方法將數(shù)據(jù)對象映射到更高維的空間，然后利用它們變換之后向量之間的相互信息(如內(nèi)積)來構(gòu)建分類、回歸和聚類。因此，用核函數(shù)方法應(yīng)對高維的問題是有顯著成效的。

計算文本之間的相似度時，增添語義聯(lián)系，可以明顯地提高聚類性能。因而，各個領(lǐng)域探究時將文本語義的核函數(shù)視為重點。2000年Siolas等[19]提出了語義核(Semantic Kernel)的觀點，并將其作為支持向量機(jī)中的基礎(chǔ)核。2002年，Cristianini等[20]基于LSA的思想，提出了潛在語義核。2005年，Mavroeidis等[21]給出了語義核函數(shù)的正式定義，并基于共現(xiàn)分析的理論構(gòu)建了廣義向量空間核。2010年，張玉峰等[22]又提出了基于WordNet的語義核函數(shù)。2013年，Nasir等[23]提出了語義平滑VSM，并實現(xiàn)了語義核的創(chuàng)建。2014年，Kim等[24]提出了一種語言獨立語義(LIS)核，它能夠在不使用語法標(biāo)簽和詞匯數(shù)據(jù)庫的情況下有效地計算短文本文檔之間的相似度。2017年，Wang等[25]提出了語義擴(kuò)散核，不僅考慮了共現(xiàn)知識，還利用了文檔的類知識。2019年，徐炎等[26]結(jié)合HowNet通過本體庫和內(nèi)部統(tǒng)計特征構(gòu)造語義核。

本文受以上PMD及語義核函數(shù)的啟發(fā)，基于CLSVSM研究懲罰性矩陣分解，其有助于挖掘文本數(shù)據(jù)的本征結(jié)構(gòu)，增強可解釋性，提高了文本表示模型的聚類效果?；赑MD構(gòu)建語義核函數(shù)，具體是依據(jù)CLSVSM得到的篇詞矩陣應(yīng)用PMD方法對特征向量進(jìn)行稀疏約束，由此得到的詞與詞之間的共現(xiàn)矩陣是稀疏的且體現(xiàn)了核心特征詞的語義信息。最后通過共現(xiàn)分析理論構(gòu)建語義核，進(jìn)一步挖掘了數(shù)字文本資源之間的語義關(guān)聯(lián)，降低了計算復(fù)雜度。將本文提出的方法應(yīng)用于數(shù)字文本資源的主題聚類研究，實驗結(jié)果表明，該方法在降低矩陣維數(shù)的同時，減少了計算復(fù)雜度，提高了文本資源主題聚類的精度。

1 相關(guān)知識概述1.1 共現(xiàn)潛在語義向量空間模型

CLSVSM主要應(yīng)用每個特征詞之間的最大共現(xiàn)強度，對傳統(tǒng)形式下高維稀疏0和1權(quán)重的文本表示模型進(jìn)行語義補充。CLSVSM[6]構(gòu)建過程如下：

首先，設(shè)有n篇不同文獻(xiàn)組成的文獻(xiàn)集，這些文獻(xiàn)共有m個互異的特征詞，組成特征詞集，建立“篇-詞”矩陣A=(aij)n×m。A中的元素取值采用布爾權(quán)重的方法。

其次，特征詞之間的共現(xiàn)矩陣表示為C=AT·A，相應(yīng)的共現(xiàn)強度矩陣計算公式如下：

(1)

最后，引進(jìn)指標(biāo)集Ii1={j|aij=1}，即所有aij=1的特征詞j的集合。據(jù)此構(gòu)建CLSVSM，其表達(dá)式為：

φ:diφ(di)=(qi1,qi2,qi3,…,qim)T∈Rm

(2)

其中，

(3)

1.2 懲罰性矩陣分解

Witten等[8]詳細(xì)給出了懲罰性矩陣分解的計算規(guī)則，對矩陣Xn×p進(jìn)行SVD，公式如下：

X=UDVT

(4)

其中，U和V這2個向量是正交的，D是奇異值矩陣。

PMD的方法是在U或V上進(jìn)行約束，其目標(biāo)函數(shù)為[8]：

(5)

其中，u是U的一列；v是V的一列；d是D的對角線元素；‖‖是Frobenius范數(shù)；P1和P2是凸懲罰函數(shù)，它們可以使用多種形式[8]。

單因子PMD的目標(biāo)函數(shù)為：

(6)

1.3 語義核

2005年Mavroeidis等給出了語義核的正式定義，對于文本表示模型，在構(gòu)建語義核函數(shù)時，可以先對其進(jìn)行簡單的線性映射φ:φ(di)=Sdi,i=1,…,n,其中S稱為相似性矩陣，表示文檔中特征詞的信息，S可以選擇任何恰當(dāng)形式的矩陣，得到語義核函數(shù)[21]，公式如下：

(7)

其中，矩陣P是對稱的，Pij表示特征詞i與j間的語義關(guān)系[21]。因此，特征詞空間的語義關(guān)系也可以通過語義核函數(shù)來度量，不同的矩陣S構(gòu)造的語義核函數(shù)也是不同的。

2 基于CLSVSM的懲罰性矩陣分解

2.1 利用PMD的理論分析

本文利用PMD的目的：1)對特征詞樣本施加懲罰，提取核心特征詞，進(jìn)而計算篇詞矩陣的K-秩近似，重建原始文本數(shù)據(jù)；2)基于該分解方法構(gòu)建語義核函數(shù)，進(jìn)一步挖掘核心特征詞之間的語義信息，降低文本表示模型的維數(shù)，減少計算復(fù)雜度。由于PMD基于稀疏約束，經(jīng)過約束的大多數(shù)系數(shù)都會變成0，從而凸顯出特征詞樣本的最主要部分，使高維矩陣更加容易識別和解釋[27]。

對于CLSVSM中的n×p維的篇詞矩陣X，用PMD將其分解成2個基本的矩陣U和V，即X～UV,它們分別是左奇異矩陣和右奇異矩陣，左奇異向量{uk}是矩陣U的一列，代表了相應(yīng)特征詞樣本的表達(dá)模式，右奇異向量{vk}是V的一列，代表了特征詞樣本，如圖1所示[12]。

圖1 基于PMD的文本數(shù)據(jù)分解模型

通常，文本數(shù)據(jù)的特征樣本定義為原始樣本的線性組合，特征樣本應(yīng)包含數(shù)據(jù)的本征結(jié)構(gòu)。換句話說，每篇文檔都可以看成特征樣本的線性組合，因此可以在稀疏過程中找到能夠表達(dá)所有文本的核心特征詞，代表了所研究領(lǐng)域的熱點及方向[14]。因此，本文通過計算原始文本數(shù)據(jù)的K-秩近似，提取數(shù)據(jù)的本征結(jié)構(gòu)，使文本表示模型更合理、恰當(dāng)，將其應(yīng)用于文本主題聚類中，檢驗其聚類效果。

根據(jù)圖1，矩陣X的第j行元素Sj，即p維的向量，是特征詞樣本{vk}的線性組合，計算公式如下：

(8)

然而為了重建原始數(shù)據(jù)，需要特征詞樣本，即p維向量。如上所述，X的第j行元素構(gòu)成p維向量Sj。因此，樣本Sj可以由特征詞樣本{vk}來表示。也就是說，在文本表示模型中，可以使用特征詞集，即核心特征詞，來代表文本。

2.2 基于PMD構(gòu)建語義核函數(shù)

首先基于CLSVSM進(jìn)行文檔表示，其對應(yīng)的“篇-詞”矩陣表示為：

(9)

建立語義核函數(shù)的重要步驟是尋找相似性矩陣S。本文對“篇-詞”矩陣X進(jìn)行懲罰性矩陣分解，由前述可知，奇異矩陣V就反映出了篇詞矩陣中相應(yīng)的特征詞中的信息。取前k個特征值對應(yīng)的特征向量vk，使得抽取的信息能最大程度地解釋特征詞的信息[28]。

針對特征詞向量非稀疏性導(dǎo)致解釋性差的問題，本文基于PMD準(zhǔn)則，在v上實施懲罰：P2(v)=‖v‖1≤c2，不對u進(jìn)行約束，其目標(biāo)函數(shù)為[8]：

(10)

k(di,dj)=φT(di)VkVkTφ(dj)

(11)

簡稱其為PMD_K，得到的核矩陣為：

K=XVkVkTXT

(12)

矩陣(12)也反映了兩篇文本之間語義關(guān)系的相似性?；赑MD的語義核構(gòu)建不僅對核心特征詞間的語義信息進(jìn)行合并，而且共現(xiàn)矩陣具有稀疏性，使得運算簡便，避免了高維空間的復(fù)雜運算。

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

3.1 實驗數(shù)據(jù)

文獻(xiàn)數(shù)據(jù)向量表達(dá)相對比較準(zhǔn)確，因此本實驗在中、英文3類文獻(xiàn)數(shù)據(jù)上進(jìn)行。

中文數(shù)據(jù)均來自CNKI，第一類收集于信息科學(xué)下的3個學(xué)科，分別為“出版”“圖書情報與數(shù)字圖書館”和“檔案及博物館”，簡略處理，最終獲得文獻(xiàn)896篇，其中包括“出版”299篇、“圖書情報與數(shù)字圖書館”298篇、“檔案及博物館”299篇，同時共獲得2024個關(guān)鍵詞。第二類是多類別不均衡數(shù)據(jù)，采集于5個類別，簡略處理，最終獲得文獻(xiàn)共1650篇，其中“出版”360篇、“檔案及博物館”330篇、“圖書情報與數(shù)字圖書館”380篇、“科學(xué)研究管理”300篇和“宏觀經(jīng)濟(jì)管理與可持續(xù)發(fā)展”280篇，共包含關(guān)鍵詞4256個。

英文數(shù)據(jù)收集信息來源于Web of Science，類別分別是“computer science information system”、“management”、“computer science interdisciplinary application”這3種，一共獲得411篇文獻(xiàn)，1889個文獻(xiàn)關(guān)鍵詞。

3.2 評價指標(biāo)

對數(shù)據(jù)使用聚類算法聚類后，對結(jié)果進(jìn)行優(yōu)劣判斷，本實驗選擇的評價指標(biāo)是純度(purity)、熵值(entropy)、F值(F-measure)。

本文將實驗的文獻(xiàn)分為k個類別，將其標(biāo)記為Lj(1≤j≤k),使用聚類算法對文獻(xiàn)集進(jìn)行聚類后獲得k個簇，將其標(biāo)記為Cr(1≤r≤k)。假如實驗的文檔有n篇，類Lj中共有nj篇文檔，簇Cr中共有nr篇文獻(xiàn)，其中無差異的文獻(xiàn)有nrj篇。評價指標(biāo)純度、熵值的計算公式如下[6]：

(13)

(14)

定義每篇文獻(xiàn)i的準(zhǔn)確率和召回率，計算公式如下[6]：

Pr=nrj/nr,Rj=nrj/nj

(15)

采用每篇文獻(xiàn)的準(zhǔn)確率和召回率的平均值表示聚類結(jié)果總的準(zhǔn)確率和召回率，分別簡記為P和R，計算公式如下[6]：

(16)

單獨使用準(zhǔn)確率或者召回率時，不能夠全面衡量聚類效果的優(yōu)劣。為了平等地看待準(zhǔn)確率和召回率的影響，采取準(zhǔn)確率和召回率的調(diào)和平均，記為F，計算公式如下[6]：

(17)

3.3 實驗過程

本文利用各種方法進(jìn)行文本主題聚類的主要實驗步驟如下：

Step1將采集到的數(shù)據(jù)通過VSM、CLSVSM進(jìn)行文檔表示得到篇詞矩陣，作為實驗的基礎(chǔ)矩陣。

Step2通過對基礎(chǔ)矩陣進(jìn)行SVD分解，求得矩陣的秩值，3類數(shù)據(jù)的秩分別為890、1642和405。

Step3基于CLSVSM構(gòu)建核函數(shù)，詳細(xì)構(gòu)造方法見文獻(xiàn)[28],使數(shù)據(jù)中的前K個特征值的和與所有特征值和的占比達(dá)到95%，將之簡稱為95%CLSVSM_K。

Step4基于CLSVSM的懲罰性矩陣分解研究，實現(xiàn)原始文本數(shù)據(jù)的重建，詳見第2.1節(jié)。

Step5參考第2.2節(jié)，基于PMD構(gòu)建語義核函數(shù)，得到核矩陣。

Step6通過以上步驟進(jìn)行計算求得矩陣后，使用gCLUTO工具包中的Repeated Bisection(重復(fù)二分法聚類)、Direct(直接聚類)、Agglomerative(凝聚聚類)和Graph(圖形聚類)這4種聚類算法進(jìn)行聚類[29]。

實驗過程如圖2所示。

圖2 實驗流程圖

3.4 實驗結(jié)果

為了檢驗本文方法具有廣泛適用性和有效性，本文將PMD(·,L1)和PMD_K這2種方法與經(jīng)典的文本表示的降維方法PCA、95%CLSVSM_K進(jìn)行實驗比較。在VSM、CLSVSM這2個模型上用4種聚類算法對中、英文數(shù)據(jù)集分別進(jìn)行30次實驗，通過多次實驗求得3個指標(biāo)的均值來對聚類結(jié)果進(jìn)行評價。熵值越靠近0，純度和F值越接近1，表明聚類效果越好[6]。在第一個中文數(shù)據(jù)集上，分析對比結(jié)果如表1所示。表1中將實驗的最優(yōu)結(jié)果用※符號標(biāo)記。

表1 第一個數(shù)據(jù)集在不同聚類方案上的聚類結(jié)果比較

從表1可以看出，對于2種不同的文本表示模型，不管用哪種聚類算法進(jìn)行實驗，本文提出的基于模型的PMD方法和構(gòu)建的語義核，明顯比原始的方法聚類效果更優(yōu)。橫向觀察，除了圖形聚類算法，基于CLSVSM上不同方法的各評價指標(biāo)的結(jié)果均優(yōu)于VSM。

利用重復(fù)二分法進(jìn)行聚類，基于CLSVSM的懲罰性矩陣分解方法，即PMD(·,L1)實驗比CLSVSM、95%PCA實驗，純度和F值各自增長率分別為2.2%、1.8%和1.5%、1.4%。在VSM模型上，構(gòu)建語義核方法(PMD_K)與VSM、95%PCA、PMD(·,L1)方法比較，純度達(dá)到0.679，分別提高了9.7%、20.6%和6.9%。同理，可以看出，在凝聚聚類和圖形聚類算法上，本文提出的2種方法的優(yōu)勢。其中，直接聚類算法的結(jié)果表現(xiàn)最好。

由圖3可知，基于CLSVSM，PMD_K在30次實驗中的純度明顯高于95%CLSVSM_K曲線，同時也較其他曲線穩(wěn)定，并處于最高位置，且與95%CLSVSM_K相比，F(xiàn)值提高21.9%?；贑LSVSM的懲罰性矩陣分解曲線在一定范圍內(nèi)處于較高位置，相較于CLSVSM、95%PCA曲線波動幅度較小。

圖3 直接聚類下基于CLSVSM各個方法的純度折線圖

由圖4可知，在VSM上，基于PMD構(gòu)建語義核和基于VSM的懲罰性矩陣分解曲線明顯高于其他曲線，且相較VSM，結(jié)果相對穩(wěn)定。充分說明了本文方法的聚類性能更強。

圖4 直接聚類下基于VSM各個方法的純度折線圖

表2 在第二個多類別數(shù)據(jù)集上的聚類結(jié)果比較

表2是在以上實驗中表現(xiàn)較好的CLSVSM上，利用直接聚類算法進(jìn)行實驗的聚類結(jié)果比較?？梢钥闯觯诰垲愋Ч?，各種方法在該多類別不均衡數(shù)據(jù)集上與第一個數(shù)據(jù)集上的表現(xiàn)基本一致。其中，基于CLSVSM的PMD實驗的純度和F值分別較CLSVSM提高了12.1%和13.9%，而熵值降低了15.0%。

之后，又在英文數(shù)據(jù)集上進(jìn)行了多組實驗，進(jìn)一步檢驗方法的適應(yīng)性和穩(wěn)定性。采用以上實驗中聚類結(jié)果較好的直接聚類算法，結(jié)果如表3所示。

表3 在英文數(shù)據(jù)集上不同方法的聚類結(jié)果比較

從表3可以發(fā)現(xiàn)，本文方法的聚類效果依舊比較明顯。在CLSVSM模型上，PMD_K方法求得的F值比95%CLSVSM_K求得的F值提高21.9%。且在各個評價指標(biāo)下，數(shù)據(jù)實驗的聚合效果均好于比較實驗。

通過以上分析，使用PMD方法后的聚類效果明顯較優(yōu)，尤其是基于PMD構(gòu)建語義核的聚類結(jié)果更優(yōu)，原因在于進(jìn)一步挖掘了詞間的語義信息，并將其合并，降低了矩陣的維數(shù)，減少了計算復(fù)雜度?；贑LSVSM的懲罰性矩陣分解研究，通過提取核心特征詞來重建文本數(shù)據(jù)，新的篇詞矩陣代表了原始數(shù)據(jù)的本征結(jié)構(gòu)，提高了文本表示模型的可解釋性。在文本主題聚類應(yīng)用中的結(jié)果顯示，可以有效提高聚類性能。因此，可以把其推廣應(yīng)用到信息檢索等領(lǐng)域，實現(xiàn)數(shù)字文獻(xiàn)資源的高維聚合。

4 結(jié)束語

針對現(xiàn)有的文本表示模型稀疏和高維的問題，本文將懲罰性矩陣分解方法應(yīng)用于CLSVSM，對特征詞樣本進(jìn)行稀疏約束，計算矩陣的最優(yōu)K-秩近似，挖掘數(shù)據(jù)的本征結(jié)構(gòu)。通過共現(xiàn)分析理論，基于PMD構(gòu)建的語義核函數(shù)(PMD_K)，深度提取核心特征詞之間的語義信息，實現(xiàn)同義詞的合并，在引入共現(xiàn)信息的同時又降低了文本表示的維數(shù)，減少了計算復(fù)雜度。實驗結(jié)果表明，該方法與原始方法相比增強了文本主題聚類的效果，可以應(yīng)用于文本資源的檢索、文本分類和知識發(fā)現(xiàn)等領(lǐng)域。

今后，筆者將繼續(xù)深入研究懲罰性矩陣分解方法，探索不同的懲罰函數(shù)的最優(yōu)解，并比較其應(yīng)用于不同數(shù)據(jù)集上的泛化性，以便用更合適的方法對數(shù)據(jù)矩陣進(jìn)行降維，實現(xiàn)文本的有效聚類。