基于多語義復(fù)合表示模型的去離群點文本聚類

顧永春,武 嬌,金世舉,顧興全,尹雪婷,劉雅萱

(1.中國計量大學(xué) 理學(xué)院,浙江 杭州 310018;2.中國計量大學(xué) 標準化學(xué)院,浙江 杭州 310018)

隨著互聯(lián)網(wǎng)的發(fā)展,以文本為代表的非結(jié)構(gòu)化數(shù)據(jù)增長迅速,但文本數(shù)據(jù)無法直接被計算機識別。因此,文本數(shù)據(jù)挖掘的首要問題是對文本進行結(jié)構(gòu)化表示[1]。

文本(句子或文檔)表示[2]是指以詞向量為基礎(chǔ),對詞向量進行組合得到可以表示文本的向量。向量空間模型[3](Vector space model,VSM)是常用的文本表示方法,可以看作是對One-Hot詞語表示的加權(quán)平均,權(quán)重可以是詞語的詞頻[4](Term frequency,TF)和詞頻逆文本頻(Term frequency-inverse document frequency,TF-IDF)[5]等。VSM具有可解釋性強、操作簡單、耗時少等優(yōu)點。但VSM表示的維度由文本語料控制,若文本語料較大,則文本向量稀疏且高維;此外,VSM表示無法完整融合詞語的上下文位置信息,導(dǎo)致文本向量的語義信息缺失。

以Word2vec為代表的詞嵌入(Word embedding)[6]可以將詞語表示為緊湊低維的實值向量,并且能夠捕捉詞語的語義和句法屬性。但對于文本聚類等文本級別的任務(wù),需要將詞嵌入擴展到整個文本。Le[7]等人提出的Doc2vec模型就是Word2vec從詞語到文本層級的擴展。也有學(xué)者利用遞歸神經(jīng)網(wǎng)絡(luò)[8]、卷積神經(jīng)網(wǎng)絡(luò)[9-10]等神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練文本向量。這些直接訓(xùn)練得到文本向量的方法[11]可以有效解決文本向量語義缺失的問題[12]。但也存在可解釋性差,訓(xùn)練時間冗長等不足[13]。

詞嵌入組合[14]是另一種常用的文本表示方法,這種表示方法通過對詞嵌入加權(quán)平均形成文本向量。常見的加權(quán)方式有均值加權(quán)、平滑逆詞頻(Smooth inverse frequency,SIF)[15]加權(quán)和互信息(Mutual information,MI)[16]加權(quán)等。對詞嵌入進行組合得到低維緊湊的文本向量不僅可以融合文本語義,還具有可解釋性強、耗時少等優(yōu)點。然而,相同詞語在不同文本中可能會有不同語義。例如,“蘋果”一詞可以表示一種水果也可以表示蘋果公司。但由詞嵌入組合得到的文本向量無法體現(xiàn)這種語義上的差異。

Nikolentzos[17]等采用多元高斯分布對詞嵌入和文本向量進行建模,并應(yīng)用于文本分類。但是,單個高斯分布并不能解決一詞多義的問題。為此,Mekala[18]等人提出了稀疏復(fù)合文本向量SCDV(Sparse composite document vectors)表示模型。SCDV首先利用軟聚類方法將詞語劃分為多個詞簇,形成語義空間,并得到詞語屬于不同語義空間的概率,作為詞語不同語義的權(quán)重;然后將多個語義權(quán)重作用在詞嵌入上得到多個語義向量,并將之連接成詞語的多語義向量;接著將文本中所有多語義詞向量的均值作為文本向量;最后,通過將較小的元素置零,對文本向量進行“稀疏化”。SCDV模型的優(yōu)點是,文本中具有不同語義的同一個詞語可以同時被劃分到多個不同的語義空間,使得不同語義被包含于文本向量的不同部分,從而加強了文本向量的語義結(jié)構(gòu)。然而,傳統(tǒng)的SCDV模型仍存在著一些不足。例如,對任意的語義空間,軟聚類方法為每個詞語都會相應(yīng)地賦予非零語義權(quán)重。但是,若詞語對應(yīng)于某個語義空間的語義權(quán)重較小,在構(gòu)造文本語義向量時將會引入冗余信息和“噪聲”。SCDV使用“稀疏化”方法通過設(shè)置閾值過濾冗余信息,但不恰當(dāng)?shù)拈撝禃⑽谋鞠蛄康乃性囟贾脼榱?從而導(dǎo)致“過稀疏”并產(chǎn)生無意義的文本表示。針對上述問題,本文設(shè)計一種截斷概率來優(yōu)化詞語的語義權(quán)重,并將其作為詞嵌入的權(quán)重用于文本多語義向量構(gòu)建,提出多語義復(fù)合文本向量(Multi-semantic composite document vectors,MSCDV)模型。

文本聚類是文本挖掘的常見任務(wù),目標是將結(jié)構(gòu)化表示后的文本數(shù)據(jù)集劃分為若干個簇類,使得同一簇內(nèi)的文本盡可能相似,不同簇類間的文本盡可能相異。K-means算法是應(yīng)用最廣泛的聚類算法之一,其具有原理簡單、易于實現(xiàn)等優(yōu)點[19]。但是,傳統(tǒng)的K-means算法對離群點敏感,離群點的存在會導(dǎo)致聚類中心偏移,從而導(dǎo)致聚類性能下降。為此,本文利用MSCDV的結(jié)構(gòu)特征識別離群點,在此基礎(chǔ)上提出一種去除離群點的K-means(K-means based on removing outliers,KMRO)算法。本文提出的MSCDV模型與KMRO聚類算法具有以下優(yōu)點。

1)利用截斷概率優(yōu)化詞語的語義權(quán)重,過濾冗余語義空間,使得MSCDV的語義結(jié)構(gòu)特征更加明顯。

2)使用概率閾值僅過濾掉詞語的小概率語義空間,大概率語義空間仍被保留,因此,MSCDV模型能有效避免文本向量的元素“過稀疏”的問題。

3)KMRO算法借助文本向量的結(jié)構(gòu)特征,通過統(tǒng)計語義空間包含的文本數(shù)量來確定離群點,并采用去除離群點的優(yōu)化方法能夠顯著地提高K-means算法的聚類性能。

1 多語義復(fù)合文本向量

本節(jié)主要介紹多語義復(fù)合文本向量的構(gòu)建流程。假設(shè)語料庫Ω中共有N個文本。首先對語料庫中所有的文本進行分詞和訓(xùn)練詞嵌入等預(yù)處理,每個文本d∈Ω都可以被切分為多個不同的詞語,每個詞語w都有與之唯一對應(yīng)的詞嵌入vw,其維度為M。

1.1 語義空間構(gòu)建

高斯混合模型(Gaussian mixture model,GMM)可以看作是多個高斯分布函數(shù)的線性組合,通常用于描述同一集合中包含多個不同數(shù)據(jù)分布的情況。

本文使用GMM來刻畫語料庫中詞語的語義空間分布及其語義概率,每個高斯分布代表一個語義空間。假設(shè)語料庫Ω包含K個的語義空間c1,c2,…,cK,將詞語w∈Ω的概率分布定義為如下形式:

(1)

其中,p(w|ck)=N(μk,Σk)表示w的詞嵌入vw在第k個語義空間中服從均值為μk,協(xié)方差矩陣為Σk的Gaussian分布;參數(shù)p(ck)=πk被稱為GMM的混合系數(shù),可看作是選擇第k個語義空間的先驗概率,滿足

(2)

使用期望最大化(Expectation-maximum,EM)算法求解GMM,可得到詞語w屬于第k個語義空間的后驗概率

(3)

本文將p(ck|w)稱為詞語w對ck的語義概率,k=1,2,…,K。

由于p(ck|w),k∈{1,2,…,K}不全為零,表明詞語w以不同的概率歸屬于不同的語義空間,從而對任意的ci和cj,i≠j,有ci∪cj≠?。

如前所述,當(dāng)詞語w屬于某個語義空間的語義概率較小時,會將冗余信息和“噪聲”引入文本表示。為此,定義如下的截斷語義概率

(4)

其中,ε為閾值參數(shù)。通過將過小的語義概率置零,可過濾詞語在小概率語義空間中的分布,從而達到優(yōu)化語義空間的目的。

1.2 文本的MSCDV表示

對語料Ω中的某個文本d,首先,以各語義空間中詞語的截斷語義概率為權(quán)重,通過對d中所有詞語的詞嵌入加權(quán)平均得到相應(yīng)語義空間的語義向量。

(5)

其中,wi是d中的詞語;|d|是文本d中詞語的數(shù)量;vwi是d中第i個詞語wi的詞嵌入,P(ck|wi)是wi對ck更新后的截斷語義概率。

然后,將K個語義向量x1,x2,…,xK連接形成文本d的MSCDV表示

(6)

其中,x是一個K×M維向量。

2 去離群點K-means算法

在得到多語義復(fù)合文本向量表示后。首先,借助文本向量的語義結(jié)構(gòu)將文檔劃分到不同的文本空間sk,k=1,2,…,K,文本空間與語義空間的在數(shù)量上相等;然后,統(tǒng)計文本空間中的文檔數(shù)目確定冗余文本空間和離群點;最后,提出去離群點聚類算法提高聚類性能。

2.1 離群點判定

首先,將所有文本向量按如下規(guī)則劃分到K個文本空間中。對任意的文本向量x,如果其第k個語義向量xk滿足

(7)

則稱x屬于文本空間sk,記作x∈sk。其中,xk,m表示xk的第m個元素。

由于文本向量由多個語義向量復(fù)合形成,同一文本可以同時被劃分到不同文本空間,從而對任意的si和sj,i≠j,有si∪sj≠?。

然后,判別sk是否為冗余文本空間。對第k個文本空間sk,若其中包含的文本向量數(shù)量sk≤δ·N,則稱sk為冗余文本空間,sk中的文本向量即為離群點。將所有離群點構(gòu)成的集合記為O,有

(8)

那么,由正常的文本向量構(gòu)成的集合即為Hc,Hc=Ω-H。

2.2 去離群點聚類算法

將語料庫Ω中N個文檔對應(yīng)的文本向量用矩陣X=(xd1,xd2,…,xdN)T表示,其中xdn是n個文本向量。設(shè)L為文本的聚類簇數(shù),Z=(z1,z2,…,zL)T是由L個聚類中心組成的矩陣,zl∈Z是第l簇的聚類中心。對每個文本向量xdn,使用二值變量un,l∈{0,1}(l=1,…,L)表示其所屬的類別,若xdn屬于第l個簇類,有un,l=1,且?k≠l,un,k=0。將這些二值變量用矩陣U=(un,l)N×L表示。那么,K-means聚類的目標函數(shù)具有如下形式:

(9)

考慮到文本向量中包含的離群點,本文分別使用二值變量un,l∈{0,1}和vm,l∈{0,1}(l=1,…,L)來標記正常點和離群點所屬的類別,將(9)式改寫為如下形式:

(10)

其中,U=(un,l)|Hc|×L,V=(vm,l)|H|×L。可以看到,目標函數(shù)被分為兩個部分:第一部分(“+”前)反映正常文本向量的簇類劃分對聚類性能的影響;第二部分(“+”后)反映離群點的簇類劃分對聚類性能的影響。與K-means算法的思想一樣,本文將通過對正常點和離群點的簇類劃分與聚類中心的交替優(yōu)化來最小化Q(U,V,Z)。但不同之處在于,更新聚類中心時,本文剔除了離群點,僅使用正常的文本向量,從而達到弱化離群點的影響、提高聚類性能的目的。

本文提出的KMRO算法使用迭代方法最小化(11)式,每次迭代對U,V,Z交替更新:

1)固定Z,更新U和V

第s次迭代中,估計U和V的子問題為

(11)

最優(yōu)解可以通過將數(shù)據(jù)點劃分到與其最近的聚類中所屬的類別得到。對任意的xdn∈Hc,un,l的更新公式為

(12)

對任意xdn∈H,vm,l的更新公式為

(13)

2)固定U和V,更新Z

第s次迭代中,估計Z的子問題為

(14)

目標函數(shù)是zl的二次函數(shù),令其關(guān)于zl的導(dǎo)數(shù)為零,可以容易得到zl的更新公式

(15)

從初始的聚類中心開始,KMRO算法按上述公式對正常點與離群點的簇類劃分和聚類中心交替更新,直到簇類劃分不再改變,或者迭代次數(shù)達到某個最值。KMRO算法流程如算法1所示。

算法1.KMRO算法輸入:X,smax,ε1,L輸出:U,V1.利用(8)式將X劃分為H和Hc2.從Hc隨機選擇L個點構(gòu)成Z(0)3.根據(jù)Z(0)計算U(0)和V(0)4.令s=0,Δ=1005.Whiles

2.3 算法收斂性分析

(16)

3 實 驗

在本節(jié)中,通過2個文本數(shù)據(jù)集的實驗來驗證基于MSCDV的KMRO聚類算法(PSCDV-KMRO)在文本聚類任務(wù)上的有效性和優(yōu)越性。實驗討論了不同截斷語義概率、語義空間數(shù)目和冗余文本空間數(shù)目參數(shù)對PSCDV-KMRO算法性能的影響,并與基于平均詞嵌入表示(Meanvec-KM)模型、TF加權(quán)平均詞嵌入表示(TFvec-KM)模型、TF-IDF加權(quán)平均詞嵌入表示(TFIDFvec-KM)模型和SCDV文本表示(SCDV-KM)模型的K-means算法性能進行對比。實驗中所有程序代碼使用Spyder(Python3.7)編譯,并在CPU為i5-4210M,內(nèi)存8GB的計算機上運行。

實驗數(shù)據(jù)集從20Newsgroups[21]中選取。其中,數(shù)據(jù)集DS1:從10個類別中選取200個文本;數(shù)據(jù)集DS2:從20個類別選取400個文本。

在MSCDV中使用的詞嵌入由20Newsgroups所有語料生成,對語料的文本作詞根提取等預(yù)處理后,利用Python3.7的gensim工具包訓(xùn)練基于Word2vec模型的詞嵌入,除了詞嵌入的維度M=150,其他參數(shù)均為默認值。設(shè)K-means和KMRO算法的聚類簇目等于文本類別數(shù)目;最大迭代次數(shù)smax=1 000;最小迭代誤差ε1=10-5。MSCDV-KMRO的最優(yōu)參數(shù)組合利用控制變量法依次確定,具體數(shù)值在3.1中詳細敘述。SCDV模型的參數(shù)均為默認值。

實驗以精確率(Precision,P)、召回率(Recall,R)和F值(F-measure,F)作為聚類性能的評價指標。

3.1 參數(shù)實驗

數(shù)據(jù)集進行聚類實驗,利用控制變量法分別研究MSCDV-KMRO中截斷語義概率閾值參數(shù)ε、語義空間數(shù)目K和冗余空間參數(shù)δ對聚類性能的影響。

實驗1)和2)都設(shè)置δ=0,即所有數(shù)據(jù)點都為正常點的情況下做的聚類,也就是MSCDV-KMRO算法即為MSCDV-K-means。

1)ε對MSCDV-KMRO聚類性能的影響

設(shè)置K=2,ε為變量。圖1分別展示了ε的變化對兩個數(shù)據(jù)集聚類效果的影響。其中,圖1(a)說明在給定的上述條件下,當(dāng)ε=1-10-8時,對數(shù)據(jù)集DS1的聚類效果最好;圖1(b)說明,相同條件下,當(dāng)ε=1-10-2時,對數(shù)據(jù)集DS2的聚類效果最好。

2)K對MSCDV-KMRO聚類性能的影響

在DS1和DS2中分別令ε=1-10-8和ε=1-10-2,K為變量。表1分別顯示了當(dāng)K的取值為15到20之間的整數(shù)時,在兩個數(shù)據(jù)集上聚類性能的變化情況。實驗結(jié)果表明,在給定上述ε值和δ值的條件下,當(dāng)K=17時,在本文提出的MSCDV模型下,K-means算法的性能最佳。

3)δ對MSCDV-KMRO聚類性能的影響

將ε和K設(shè)置為常量,在兩個數(shù)據(jù)集上分別討論參數(shù)δ對聚類性能的影響。在DS1上設(shè)置ε=1-10-8,K=17;在DS2上設(shè)置ε=1-10-2,K=17。δ從0到0.7變化,實驗結(jié)果如表2所示。可以看到,當(dāng)δ=0.6時,MSCDV-KMRO在兩個數(shù)據(jù)集上都獲得了最優(yōu)的聚類性能。如前所述,δ=0對應(yīng)于未考慮離群點的MSCDV-KM算法,這表明通過去除離群點確立能夠有效地提高算法的聚類性能。

通過上述參數(shù)實驗,得到MSCDV-KMRO算法對數(shù)據(jù)集DS1和DS2的最優(yōu)參數(shù)設(shè)置,見表3。

圖1 參數(shù)ε對聚類性能的影響Figure 1 Cluster performance comparison with different values of ε

表1 參數(shù)K對聚類性能的影響

表2 參數(shù)δ對聚類性能的影響

表3 MSCDV-KMRO算法參數(shù)設(shè)置

表4 聚類性能比較

3.2 對比實驗

表4給出MSCDV-KMRO與Meanvec-KM、TFvec-KM、TFIDFvec-KM、SCDV-KM和MSCDV-KM等5種算法聚類性能的比較。對于數(shù)據(jù)集DS1,MSCDV-KMRO和SCDV-KM算法的聚類性顯著優(yōu)于其他算法,說明多語義復(fù)合表示更適合文本聚類任務(wù);相比于SCDV-KM,MSCDV-KMRO的三個聚類性能指標都有14%以上的提高,說明在多語義復(fù)合表示下,去除離群點的策略對聚類性能的進一步提升起到了重要作用。對于數(shù)據(jù)集DS2,由于SCDV模型的文本向量過于稀疏,從而無法有效地進行文本聚類,但MSCDV模型能夠避免“過稀疏”問題。總的來說,與其他4種算法相比,MSCDV-KMRO算法在聚類性能上的提高能達到3.57%～44.88%。

4 結(jié) 論

本文針對文本聚類任務(wù),通過復(fù)合詞語的多種語義信息提出MSCDV文本向量表示模型,并基于文本向量的結(jié)構(gòu)特征構(gòu)建KMRO聚類算法。參數(shù)和對比實驗的結(jié)果表明:1)文本的多語義復(fù)合表示更適合文本聚類任務(wù);2)過濾冗余語義空間和去除離群點能夠有效提升算法的聚類性能;3)在適當(dāng)?shù)膮?shù)設(shè)置下,KMRO算法顯著優(yōu)于傳統(tǒng)K-means算法。

基于MSCDV模型的KMRO算法對文本聚類性能的提升表明,在文本表示中以適當(dāng)?shù)姆椒ㄈ谌氩煌恼Z義信息能夠使文本表示更加完善。因此,在文本表示模型構(gòu)建中探究如何選擇和提取有效語義信息,構(gòu)造語義和結(jié)構(gòu)特征并存的表示模型,并將其應(yīng)用于其他文本任務(wù)需要做進一步的研究。