劉麗華

(內(nèi)蒙古財經(jīng)大學(xué) 檔案館，呼和浩特 010010)

海量檔案文本數(shù)據(jù)急劇增長，也伴隨著文本數(shù)據(jù)描述的多樣化[1]。例如，一則新聞消息可以通過不同的語言進行表達和傳播；一個文本可以利用不同的特征描述(Word2Vec、TF-IDF等)進行分析。這樣的數(shù)據(jù)稱為多模態(tài)數(shù)據(jù)，不同領(lǐng)域或不同描述形式可以代表一種模態(tài)。通常，不同模態(tài)之間可以為語義相同的數(shù)據(jù)對象相互補充信息，結(jié)合多個模態(tài)的數(shù)據(jù)信息對一個物體進行描述相比于單模態(tài)可以更加全面地了解該物體的特征并且精準對該物體進行辨別。另外，隨著檔案文本不斷增長，給檔案管理帶來了一定困難，有效對檔案數(shù)據(jù)進行聚類、劃分，能夠按主題對檔案文本進行分類管理，便于后期查閱、處理。

近年來多模態(tài)文本數(shù)據(jù)聚類或分類算法的研究備受關(guān)注[2]。例如，Amini等[3]將不同語言的文檔看作是原始文檔的不同模態(tài)，成功設(shè)計了多視圖多數(shù)投票和多視圖共分類[4]等方法對文檔進行學(xué)習(xí)；Bickel等[5]研究了眾多多模態(tài)數(shù)據(jù)形式下的聚類方法，例如k-means、k-medoids和EM(expectation-maximization)等。挖掘不同模態(tài)結(jié)合過程中潛在的數(shù)據(jù)信息是研究者們共同的目標，由此可見，研究多模態(tài)數(shù)據(jù)融合的有效方法已成為文本大數(shù)據(jù)分析中的重要方向。文中針對海量檔案文本數(shù)據(jù)的多模態(tài)特點，研究有效的增量多模態(tài)文本聚類方法。

非負矩陣分解[6](NMF, nonnegative matrix factorization)是一種經(jīng)典的矩陣分解技術(shù)，它可以將每個觀測對象解釋為非負基向量的線性組合相加后得到的結(jié)果[7]，這恰好符合了人們在大腦和心理上所習(xí)慣的“局部構(gòu)成整體”的思想[8-9]。近幾年內(nèi)，NMF已經(jīng)被廣泛運用于數(shù)據(jù)聚類中，它與許多先進的無監(jiān)督聚類算法相比，其性能極具競爭力[10]。例如，Xu等[11]將NMF應(yīng)用于文本聚類，取得了較好的結(jié)果；Brunet等[12]在生物數(shù)據(jù)聚類方面也獲得了類似的成功。這些基于NMF的單模態(tài)聚類算法都取得了不錯的成果。如果將NMF技術(shù)應(yīng)用于多模態(tài)檔案文本數(shù)據(jù)將取得令人期待的結(jié)果。NMF本身具有屬性降維的功能，可以很好地解決多模態(tài)檔案文本大數(shù)據(jù)存在的維數(shù)災(zāi)難問題。然而，基于NMF的多模態(tài)文本數(shù)據(jù)聚類方法也將面臨以下問題：多模態(tài)文本數(shù)據(jù)存在異構(gòu)性，如何充分結(jié)合多個模態(tài)的數(shù)據(jù)信息是首要的挑戰(zhàn)；當(dāng)多模態(tài)的文本數(shù)據(jù)出現(xiàn)爆炸式增長的時候，傳統(tǒng)的學(xué)習(xí)方法需要損耗大量的空間和時間成本。

針對以上問題，文中將研究基于NMF的增量多模態(tài)文本聚類方法。與傳統(tǒng)的非負矩陣分解方法使用得到的系數(shù)矩陣進行數(shù)據(jù)分析不同，文中提出的方法將直接用融合后的共享特征矩陣進行聚類分析，檢測融合數(shù)據(jù)的效果。該方法是基于語義的，在考慮每種模態(tài)的實際意義的情況下求得所有模態(tài)的共享特征，并且在多模態(tài)數(shù)據(jù)語義融合的基礎(chǔ)上引入圖規(guī)則化的思想，保證各模態(tài)數(shù)據(jù)與共享特征的幾何結(jié)構(gòu)相似性，力求能夠獲得更好的特征學(xué)習(xí)與聚類分析效果。然而，當(dāng)大規(guī)模檔案文本數(shù)據(jù)遇到實時性的需求時，傳統(tǒng)的多模態(tài)數(shù)據(jù)融合算法無法滿足在短時間對大量數(shù)據(jù)進行處理的任務(wù)，因此實現(xiàn)2種增量自適應(yīng)文本數(shù)據(jù)特征學(xué)習(xí)方案，并求解對應(yīng)的增量優(yōu)化規(guī)則，可以節(jié)約數(shù)據(jù)處理的時間成本，同時學(xué)習(xí)的增量方法在一定程度上也更加節(jié)省數(shù)據(jù)占據(jù)的存儲空間。2個實際文本數(shù)據(jù)集上的實驗結(jié)果表明：文中提出方法優(yōu)于現(xiàn)有的一些增量和非增量學(xué)習(xí)方法，能夠?qū)Χ嗄B(tài)文本數(shù)據(jù)進行有效劃分。

1 相關(guān)技術(shù)

1.1 非負矩陣分解

給定一個M×N大小的非負矩陣X(矩陣中的元素均為負)，每個列向量代表一個數(shù)據(jù)實例，數(shù)據(jù)實例大小為N，每個行向量代表一種特征屬性，共有M維特征屬性。這個矩陣被近似分解為一個M×d的基矩陣U和一個N×d的編碼矩陣V，其原理如圖1所示[6]。

圖1 非負矩陣分解原理原理Fig.1 The principle of non-negative matrix factorization

通常，設(shè)定d的數(shù)值遠遠小于N，假設(shè)d為數(shù)據(jù)聚類的類數(shù)。非負矩陣分解可以形式化表示為

X≈UVT(U≥0，V≥0 )。

(1)

為了求得矩陣X的近似表示，可以將目標函數(shù)最小化：

(2)

(3)

(4)

按照式(3)和式(4)依次對U、V進行交替迭代直到函數(shù)收斂，求得最后的U、V矩陣。

非負矩陣分解將一個原始矩陣分解成一個基矩陣和一個編碼矩陣相乘的形式，要求得到的基矩陣和編碼矩陣非負，因此原矩陣中的某一行數(shù)據(jù)可以看作編碼矩陣中所有列向量的加權(quán)和，具體的系數(shù)對應(yīng)編碼矩陣中列向量的元素。該分解過程可以理解為一種特征提取的行為，編碼矩陣則為原始矩陣的潛在特征表示。

1.2 多模態(tài)非負矩陣分解

(5)

通過共享矩陣V的耦合，聯(lián)合迭代更新各變量，得到優(yōu)化后的多模態(tài)共享特征。

2 增量多模態(tài)文本聚類方法

文中提出的增量多模態(tài)算法考慮每個模態(tài)的語義信息，使用NMF抽取出多模態(tài)數(shù)據(jù)的共享特征子空間。為提升其學(xué)習(xí)特征的有效性，算法還嵌入圖拉普拉斯正則化項，保證高維數(shù)據(jù)在降維過程中盡量維持其原始的數(shù)據(jù)結(jié)構(gòu)，進一步提升共享特征學(xué)習(xí)的準確性。最后，為每個模態(tài)設(shè)立模態(tài)權(quán)值，通過權(quán)值的自適應(yīng)更新，合理控制每個模態(tài)對于特征子空間的貢獻。在實際應(yīng)用中，數(shù)據(jù)往往是分批到來的，這導(dǎo)致了非增量算法時間開銷巨大。因此，在上述基礎(chǔ)算法的基礎(chǔ)上，進行算法的2種增量改進來大幅度減少時間消耗。第一種增量改進算法基于數(shù)據(jù)相對獨立這一假設(shè)[13]：當(dāng)新數(shù)據(jù)到來時，它僅通過計算新數(shù)據(jù)的特征子空間從而減少時間開銷。第二種增量改進算法結(jié)合了緩沖區(qū)的思想[14]，為數(shù)據(jù)開創(chuàng)時間緩沖區(qū)，通過緩沖區(qū)來減少時間開銷。

2.1 基于圖規(guī)則化的多模態(tài)NMF

拉普拉斯特征映射是一種基于圖的降維方法，它可以使圖中原本相近的2個點在降維后依然盡量地靠近。因此，拉普拉斯矩陣使數(shù)據(jù)中具有相似性的實例在降維后的空間內(nèi)依舊保持高度相似，以達到后續(xù)更好的特征學(xué)習(xí)效果[15]。

根據(jù)數(shù)據(jù)間的歐氏距離，采用p-最近鄰算法構(gòu)造出一個鄰接矩陣W，Wij表示數(shù)據(jù)實例i和數(shù)據(jù)實例j的相似度，要求在降維后的子空間內(nèi)原本靠近的數(shù)據(jù)仍舊相近，即在共享特征子空間V中，原始空間相近的行向量vi與行向量vj(Wij較大)的距離要盡可能的小。故得到目標函數(shù)：

Tr(VDVT)-Tr(VWVT) =Tr(VLVT)，

(6)

式中：L是圖的拉普拉斯矩陣，L=D-W；W是鄰接矩陣；D是度矩陣，它是一個對角矩陣，其每一行的對角元素是W矩陣中對應(yīng)每一行或列之和。

根據(jù)上述方法計算得到每一個模態(tài)數(shù)據(jù)的拉普拉斯矩陣L(v)后，便可得到基于圖規(guī)則化的多模態(tài)NMF的目標函數(shù)：

s.t.V≥0，U(v)≥0，v=1,2,3,…,nv。

(7)

式中，λ為圖正則化項的控制參數(shù)。

2.2 增量自適應(yīng)圖規(guī)則化多模態(tài)NMF

基于2.1節(jié)的圖規(guī)則化的多模態(tài)NMF，文中提出增量自適應(yīng)圖非負矩陣分解模型(IAGNMF, incremental adaptive graph regularized multi-modal NMF)。模型中假設(shè)新數(shù)據(jù)與原有數(shù)據(jù)是相對獨立的，因此對于新到來的數(shù)據(jù)，在保持原有數(shù)據(jù)共享特征子空間不變的基礎(chǔ)上為新數(shù)據(jù)開辟新的特征子空間。對于圖的增量計算則是對每個模態(tài)新數(shù)據(jù)在全局數(shù)據(jù)集合空間上的分布特點進行擬合，保證新數(shù)據(jù)對應(yīng)特征子空間分布與各個模態(tài)所有數(shù)據(jù)分布相似。最后為每個模態(tài)設(shè)立一個模態(tài)權(quán)值，通過權(quán)值自適應(yīng)更新來控制各模態(tài)對于新數(shù)據(jù)特征子空間學(xué)習(xí)的貢獻，具體細節(jié)如下：

(8)

(9)

(10)

最后，在式(10)的基礎(chǔ)上為模態(tài)添加自適應(yīng)權(quán)重因子(α(v))γ，其中，α(v)為第v個模態(tài)的權(quán)重因子，γ為控制權(quán)重分散程度的參數(shù)。自動更新自身模態(tài)權(quán)重，約束不同模態(tài)對特征子空間的影響。這樣得到了目標函數(shù)：

(11)

(12)

(13)

(14)

(15)

(16)

(17)

利用拉格朗日優(yōu)化函數(shù)對式(17)進行優(yōu)化表示得到：

(18)

其中：?為限定條件Vl≥0的拉格朗日乘子，用式(18)對Vl求偏導(dǎo)得到：

(19)

通過KKT(Karush-Kuhn-Tucher)條件(?)ij(Vl)ij=0，得到Vl的更新規(guī)則為：

(20)

(21)

利用拉格朗日優(yōu)化公式對式(21)進行優(yōu)化表示得到

(22)

利用式(22)對α(v)求導(dǎo)，使導(dǎo)數(shù)為0，得到：

(23)

(24)

2.3 在線自適應(yīng)圖規(guī)則化多模態(tài)NMF

與IAGNMF不同，在線自適應(yīng)圖非負矩陣分解(OAGNMF, online adaptive graph regularized multi-modal NMF)假設(shè)新數(shù)據(jù)總是與它到達時間相近的數(shù)據(jù)關(guān)聯(lián)性更強，而與到達時間較遠的數(shù)據(jù)關(guān)聯(lián)更弱。因此，模型中設(shè)立一個固定大小的緩沖區(qū)，總是存放s個最近到來的數(shù)據(jù)，將其他較早到來的數(shù)據(jù)丟棄。運用緩存區(qū)的數(shù)據(jù)進行特征子空間學(xué)習(xí)。

因此，在構(gòu)造圖正則化項時，僅需要計算緩沖區(qū)實例的p-最近鄰圖即可。頂點對應(yīng)緩存區(qū)的實例，同樣采用余弦距離來衡量文本實例的相似度：

(25)

(26)

類似的，目標函數(shù)(26)是非凸的，采取同樣的策略尋找局部最優(yōu)解：

(27)

(28)

同理，對目標函數(shù)(26)進行拉格朗日優(yōu)化表示后對Vs求導(dǎo)，通過KKT條件使導(dǎo)數(shù)為0得到Vl的更新規(guī)則：

(29)

(30)

2.4 復(fù)雜度分析

設(shè)多模態(tài)數(shù)據(jù)平均模態(tài)維度為M，算法IAGNMF的空間復(fù)雜度為O(V(Mk+Ml+MMc+3(k+l)2+1)+Mc(k+l)+2)(V(Mk+Ml+MMc+3(k+l)2+1)+Mc(k+l)+2)≈O((k+l)2)。假設(shè)迭代更新平均收斂次數(shù)是tt，多模態(tài)數(shù)據(jù)平均模態(tài)維度為M，算法IAGNMF一次增量過程的時間復(fù)雜度為O(Vt(2MMc(k+l)+Ml(k+l))+VMvl(k+l))≈O(k)O(Vt(2MMc(k+l)+Ml(k+l))+VMvl(k+l))O(Vt(2MMc(k+l)+Ml(k+l))+VMvl(k+l))。

設(shè)多模態(tài)數(shù)據(jù)平均模態(tài)維度為M，算法OAGNMF的空間復(fù)雜度為O(V(Ms+MMc+3s2+1)+Mcs+2)≈O(1)O(V(Ms+MMc+3s2+1)+Mcs+2)O(V(Ms+MMc+3s2+1)+Mcs+2)。假設(shè)迭代更新平均收斂次數(shù)是tt，多模態(tài)數(shù)據(jù)平均模態(tài)維度為M，那么算法OAGNMF一次增量過程的時間復(fù)雜度為O(Vt(2MMcs+Ms2)+VMvs2)≈O(1)O(Vt(2MMcs+Ms2)+VMvs2)O(Vt(2MMcs+Ms2)+VMvs2)。

3 實驗分析

為驗證文中提出算法的有效性，設(shè)計了一系列算法對比實驗，并在多模態(tài)文本數(shù)據(jù)集LegalText和Webkb上驗證算法IAGNMF和OAGNMF和現(xiàn)有的一些相關(guān)算法：ConcatNMF(concatenation NMF)[6]，INMF (incremental NMF)[13]，MultiINMF (multi-view Incremental NMF)[10]和MultiGNMF(multi-view graph NMF)[15]的性能。一是比較共享特征學(xué)習(xí)效果，將算法提取出來的低維特征進行k-means聚類分析，分析聚類的準確度(ACC, accuracy)和純度(PUR, purity)。二是比較運行算法的時間開銷。

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

3.1.1 數(shù)據(jù)集LegalText

LegalText數(shù)據(jù)集是具有7個大類6 300個法律案例的文本數(shù)據(jù)，分別是瀆職，妨害社會管理秩序，破壞社會主義市場經(jīng)濟秩序，侵犯財產(chǎn)，侵犯公民人身權(quán)利、民主權(quán)利，貪污受賄，危害公共安全。通過預(yù)處理得到150維word2vec特征和500維tfidf特征2個模態(tài)。

3.1.2 數(shù)據(jù)集Webkb

Webkb數(shù)據(jù)集[16]源自于康奈爾大學(xué)計算機科學(xué)系的網(wǎng)頁文本內(nèi)容，該數(shù)據(jù)集包含屬于4個類別的8 282個數(shù)據(jù)樣例，共有2 500維網(wǎng)頁中的文本特征屬性和1 380維網(wǎng)頁中超鏈接的錨文本特征屬性2種模態(tài)信息。

3.2 算法比較

文中基于NMF提出2種增量多模態(tài)聚類算法，實驗中，將提出的2種算法與現(xiàn)有的一些基于NMF的增量和非增量方法進行比較，驗證提出算法的性能。具體比較算法包括：①ConcatNMF：將多模態(tài)數(shù)據(jù)的所有模態(tài)屬性進行直接拼接后進行非負矩陣分解[6]；②INMF[13]：為單模態(tài)增量非負矩陣分解方法，實驗中對數(shù)據(jù)集中多有模態(tài)數(shù)據(jù)進行單模態(tài)增量學(xué)習(xí)，并采用最好模態(tài)結(jié)果；③MultiINMF：為多模態(tài)非負矩陣分解MultiNMF的增量算法[10]，其增量實現(xiàn)與INMF相同；④MultiGNMF為基于圖規(guī)則化的多模態(tài)數(shù)據(jù)融合算法，其實現(xiàn)拓展了圖正則化NMF[15]到多模態(tài)數(shù)據(jù)。

3.3 實驗設(shè)置

實驗當(dāng)中，比較算法ConcatNMF、INMF、MultiINMF和MultiGNMF的參數(shù)選擇與其原始文獻中相同。文中提出的IAGNMF圖正則化參數(shù)λ=15，權(quán)重分散程度參數(shù)γ=1.3；OAGNMF圖正則化參數(shù)λ=15，權(quán)重分散程度參數(shù)γ=1.3，緩沖區(qū)大小設(shè)置為40%數(shù)據(jù)集大小。每次實驗非重復(fù)地取1/10數(shù)據(jù)集的實例作為新到來的實例運行算法學(xué)習(xí)其低維共享特征，運行10次之后完成對整個數(shù)據(jù)集的特征學(xué)習(xí)。對于增量算法，每次學(xué)習(xí)新實例的低維共享特征后，記錄學(xué)習(xí)時間，與已經(jīng)完成特征學(xué)習(xí)的實例的低維共享特征一起進行聚類分析驗證學(xué)習(xí)效果；對于非增量算法，新實例和已完成特征學(xué)習(xí)的實例一起進行特征學(xué)習(xí)，記錄學(xué)習(xí)時間，將學(xué)習(xí)到的所有實例的低維共享特征進行聚類分析驗證學(xué)習(xí)效果。對于每次模型運行，都能得到其時間開銷，聚類精度和純度。每個實驗重復(fù)運行15次，并取其均值輸出比較結(jié)果。

實驗環(huán)境為Windows10操作系統(tǒng)，Matlab R2018a軟件平臺，硬件環(huán)境為Intel?CoreTMi5-7300HQ CPU @ 2.50GHz處理器，8G內(nèi)存。

3.4 結(jié)果分析

LegalText和Webkb 2個文本數(shù)據(jù)集上的各算法聚類有效性比較結(jié)果如圖2和圖3所示。

圖2 LegalText數(shù)據(jù)集上的聚類結(jié)果比較Fig.2 Comparison of clustering results on LegalText dataset

從圖2和圖3可以看出，相比于ConcatNMF、INMF、MultiINMF和MultiGNMF，文中提出的2種增量多模態(tài)文本聚類方法具有一定的優(yōu)勢。例如，在LegalText數(shù)據(jù)集上IAGNMF在ACC和PUR 2種聚類指標上一直優(yōu)于所有比較算法，這是因為IAGNMF實現(xiàn)了增量的圖規(guī)則化機制保證了融合空間特征與原始數(shù)據(jù)具有一致的幾何相似結(jié)構(gòu)，此外IAGNMF實現(xiàn)了模態(tài)權(quán)重的自適應(yīng)調(diào)整，保證了各模態(tài)的有效信息。同樣OAGNMF和MultiGNMF也是用了圖規(guī)則化項，也得到了較好的結(jié)果。OAGNMF采用數(shù)據(jù)緩存機制，假設(shè)一段時間內(nèi)數(shù)據(jù)具有相似性，而在實際的數(shù)據(jù)集LegalText中這個假設(shè)很難保證，但在標準數(shù)據(jù)集Webkb中便能得到較好的效果(如圖4)。MultiGNMF實現(xiàn)沒有考慮各模態(tài)的權(quán)重，所以相比于文中提出的算法其性能略有下降。

圖3 Webkb數(shù)據(jù)集上的聚類結(jié)果比較Fig.3 Comparison of clustering results on Webkb dataset

圖4 2個數(shù)據(jù)集上的時間開銷比較Fig.4 Comparison of time consumption on two datasets

圖4給出了幾種比較算法的時間性能。從圖中可以看出，基于圖規(guī)則化的MultiGNMF比ConcatNMF、INMF和MultiINMF需要消耗更多的時間。IAGNMF和OAGNMF同樣使用圖規(guī)則化提升算法的性能，但其增量實現(xiàn)能夠有效減少算法的時間開銷。

綜上，相比于比較算法文中提出的2種算法在聚類性能和時間消耗上均具有一定的優(yōu)勢，適合海量多模態(tài)文本數(shù)據(jù)的增量融合學(xué)習(xí)與聚類分析。當(dāng)數(shù)據(jù)集中數(shù)據(jù)樣本隨采集時間有一定的前后依賴時，采用數(shù)據(jù)緩存機制的OAGNMF算法能夠得到較好的性能；而當(dāng)數(shù)據(jù)間沒有時間依賴時，采用增量圖相似結(jié)構(gòu)度量的IAGNMF算法具有更加的聚類性能。

4 結(jié)束語

文中提出2種增量多模態(tài)文本聚類算法，基于NMF構(gòu)建多模態(tài)文本數(shù)據(jù)特征學(xué)習(xí)基本模型，利用局部相似圖規(guī)則化保證學(xué)習(xí)特征空間的結(jié)合結(jié)構(gòu)與原始數(shù)據(jù)空間的一致性，提升多模態(tài)融合特征學(xué)習(xí)的準確性。設(shè)計了2種增量多模態(tài)數(shù)據(jù)特征學(xué)習(xí)機制，并對各模態(tài)權(quán)重進行自適應(yīng)調(diào)整，實現(xiàn)海量多模態(tài)文本數(shù)據(jù)的快速、有效融合學(xué)習(xí)。通過2個實際文本數(shù)據(jù)集上的實驗結(jié)果表明，文中提出的2種算法具有一定的優(yōu)越性。