基于用戶行為特征的多維度文本聚類

黎萬英，黃瑞章,2,3，丁志遠，陳艷平,2，徐立洋

(1.貴州大學 計算機科學與技術學院，貴陽 550025； 2.貴州省公共大數(shù)據(jù)重點實驗室(貴州大學)，貴陽 550025；3.計算機軟件新技術國家重點實驗室(南京大學)，南京 210093)(*通信作者電子郵箱rzhuang@gzu.edu.cn)

0 引言

隨著Twitter、微博等社交媒體的廣泛使用，給傳統(tǒng)文本內(nèi)容聚類方法帶來挑戰(zhàn)。由于社交媒體中存在大量短文本，導致基于文本內(nèi)容聚類中的特征稀疏問題比較嚴重。另外，除了文本內(nèi)容，社交媒體數(shù)據(jù)還包含很多用戶行為信息，如：點贊、轉發(fā)、評論、關注、引用等(也稱“用戶行為特征”)。缺少用戶行為特征的聚類方法不能對社交媒體數(shù)據(jù)的分布特征進行建模。除了Twitter、微博等“新媒體”外，有些傳統(tǒng)文本中也包含有用戶行為信息，如學術論文中的合作作者和參考文獻等。

為了在文本內(nèi)容的基礎上有效利用用戶行為特征進行聚類，本文提出了結合用戶行為特征的多維度文本聚類(Multi-dimensional Text Clustering with User Behavior Characteristics, MTCUBC)模型，該模型主要針對傳統(tǒng)多維度聚類中存在的兩個問題：1)傳統(tǒng)多維度聚類主要使用文本內(nèi)容和超鏈接等“靜態(tài)特征”，缺乏對用戶行為特征的有效利用；2)傳統(tǒng)多維度聚類只是簡單地將多個維度空間進行線性疊加，沒有考慮不同維度空間的差異性。本文提出的MTCUBC模型根據(jù)文本相似性在不同空間上應該保持一致的原則，將用戶行為特征作為約束(constrains)來輔助聚類。同時，采用度量學習(metric learning)方法來精確地調(diào)節(jié)每個屬性值，從而提高聚類的效果。

本文通過兩個數(shù)據(jù)集對模型進行驗證。實驗結果表明，該方法與單維度文本聚類方法相比有明顯的改進，與多維度聚類方法比較也有明顯的提升。

1 相關工作

在相關研究中，多維度聚類備受關注，例如：在網(wǎng)絡中，廣泛使用圖像、音頻、超鏈接、文本等不同類型的特征來進行聚類。在早期的研究中，數(shù)據(jù)的標注信息經(jīng)常被用作多維度聚類的約束。例如，文獻[1]提出了一種將有標記和未標記樣本進行合并的方法; 文獻[2]提出了一種成對約束(pair-wise)的聚類框架，使用標記數(shù)據(jù)作為約束來指導聚類過程; 文獻[3-4]均研究了帶標記和未標記樣本聚類結果的影響。這類方法的實現(xiàn)需要部分數(shù)據(jù)帶有標注信息,難以在無標注數(shù)據(jù)集中使用。

在約束聚類中，文獻[1,5]通過修改聚類目標函數(shù)實現(xiàn)多維度空間聚類，其中，文獻[1]在K-Means算法的基礎上，提出如何修改利用流行的聚類算法應用到實際問題中，文獻[5]提出半監(jiān)督聚類算法，將部分未標記的數(shù)據(jù)進行聚類，然后用已知類來預測未來樣本點的類別。文獻[6]提出了成對約束聚類方法。這類模型均使用約束來修改聚類的目標函數(shù)，但由于特征的高維稀疏性而影響聚類效果，沒有考慮能改善文本間距離測量的距離度量方法。

文獻[7]提出學習距離矩陣的方法；文獻[8]給出成對約束的聚類框架，并提出一種主動選擇成對約束的方法來改進聚類效果；文獻[9]將社會行為信息的相似性嵌入到視覺空間中; 為了提高多維度聚類的結果，文獻[10]使用相似的文章來學習距離矩陣；文獻[11]提出使用相似的文章作為約束，為每個類學習出一個距離矩陣的聚類方法；文獻[12]提出一種可以同時進行多維度聚類和特征選擇的方法，該方法主要是針對高維數(shù)據(jù)稀疏問題；文獻[13]提出基于隱馬爾可夫條件隨機場的多維度聚類框架；文獻[14]提出一種多維度K-Means聚類算法，該算法為每個維度指定一個權重，使其與聚類結果相關聯(lián)，其中維度用給定的內(nèi)核矩陣表示，并且內(nèi)核的加權組合與簇并行學習；文獻[15]提出一種多類型的網(wǎng)絡文本聚類(Multi-type Features based Web Document Clustering, MFRC)，為每一個特征空間設置一個權重值。

在成對約束聚類中，文獻[10]結合梯度下降和迭代過程來學習馬氏矩陣(Mahalanobis metric)；文獻[16]提出冗余成分分析算法，它只用必連約束來學習馬氏距離，但是這些矩陣學習方法都只訓練出一個距離矩陣。

與前面的模型相比，本文提出的MTCUBC模型允許度量學習方法利用成對約束和無標簽數(shù)據(jù)來學習出多個距離矩陣，使實驗結果有很大提升。

2 模型的提出

2.1 社會特征的學習

本文將社會維度中的用戶行為特征嵌入到詞維度聚類中，因此，如何將復雜、無結構的用戶行為特征加入到有結構的詞維度空間是本文首先要解決的問題。用論文中作者和參考文獻間的關系來舉例說明，xi={a1,a2, …,an}表示社會維度中第i篇論文中出現(xiàn)的作者和論文引用參考文獻中的作者的表示，其中作者出現(xiàn)為1，不出現(xiàn)為0，并且當前論文中的作者及參考文獻中的作者只取前三位。社會維度中，作者間的相似性對于詞維度的聚類有幫助，為了證明這一點，本文收集了兩個數(shù)據(jù)，以Aminer論文集[17]為例進行說明，該數(shù)據(jù)集收集了3 000篇論文，統(tǒng)計有8 812個詞和22 373個作者。對于每篇論文中的作者，若他們引用的文章都有較高的相似性、較低的差異性，則這些文章中的作者有相同的愛好領域。本文抽象出社會維度中的作者特征和詞維度中的詞特征向量來計算它們之間的相似度，假如要給作者推薦參考文獻，除了從文章的內(nèi)容以外，社會相似度也是一個可靠、可以考慮的指標。

2.2 基于約束的聚類算法

由于有標簽的樣本比較少，文獻[16]考慮到使用約束方法比提供有標簽的數(shù)據(jù)更現(xiàn)實，因此使用相似文章對來學習距離，雖然類標簽可能未知，但用戶仍然可以指定對應樣本是否屬于同一個簇，所以約束的方法也比類標簽更通用。

針對傳統(tǒng)聚類方法不能直接利用約束的問題，基于約束的聚類算法是使用標注數(shù)據(jù)作為約束來輔助聚類，但本文中沒有標注好的樣本，是通過在社會維度(social)聚類后，挑選具有較高相似度的文章對作為約束來輔助詞(word)維度聚類，此時挑選的文章對類別是確定的。利用約束將目標函數(shù)和約束條件結合起來可以解決這一問題。

設M表示是一組必須關聯(lián)的文章，其中(xi,xj)∈M表示xi和xj應該被聚到同一個類中。讓W={ωij}作為M中違反約束的懲罰因子，所以目標是最小化下面的目標函數(shù)：

(1)

其中:I為指示函數(shù)，I[true]=1和I[false]=0。li和lj在社會維度中有較高的相似度，在詞向量維度聚類中應該被聚到同一個類中，否則將會受到相應懲罰。

2.3 基于度量學習聚類

為調(diào)節(jié)向量中每個屬性的貢獻度，本模型不是統(tǒng)一地給定某個權重參數(shù)，而是通過一個度量學習矩陣來給每個屬性一個權重，這樣更能滿足每個屬性間的差異性。

在調(diào)整矩陣聚類相關工作中，文獻[10, 17]調(diào)整矩陣權重同時滿足最小化必連(must-linked)樣本間的距離和最大化必不連(cannot-kinked)樣本間的距離,而且存在基本的限制：對于所有的類都只能用同一個矩陣, 允許每個簇h有單獨的一個權重矩陣Ah，可以證明，在這種廣義K-means模型下，完整的數(shù)據(jù)最大對數(shù)似然函數(shù)等價于最小化目標函數(shù)：

(2)

其中:第二項是第li個高斯與協(xié)方差矩陣Ali-1的正態(tài)常數(shù)。

2.4 MTCUBC模型

結合式(1)和(2)，即結合約束與度量學習方法。在較少約束違反的情況下，最小化在學習矩陣下的聚類分散度，可以得到目標函數(shù)：

(3)

如果統(tǒng)一約束開銷ωij,所有約束違背都平等對待; 然而，在必連(must-link)集合中，對那些違背約束且離得遠的點的懲罰應該大于那些違背約束且離得相對較近的點。直觀地說：如果兩個必連點根據(jù)當前的距離度量方法相距很遠，則度量是非常不充分的，并且需要對它進行嚴格的修改。由于兩個簇中參與了同一個必連的違背行為，相應的懲罰應該影響到兩個簇的度量, 這可以通過對式(3)的第二部分乘以一個懲罰值來實現(xiàn),該懲罰值表示為：

(4)

加入懲罰值后的目標函數(shù)如下：

(5)

懲罰僅針對那些違背約束的樣本。M是社會維度中滿足一定相似度的樣本。忽略不相連(cannot-link)的樣本，因為在社會維度中不同作者的兩篇文章，在詞向量維度中其內(nèi)容可能相似。從式(5)可以看出，公式由兩部分組成，其中懲罰因子wij為每個約束提供一個權重，同時該約束也體現(xiàn)公式中兩部分之間的相對重要性。

3 算法求解

步驟2 重復下面的過程直到收斂：

③t=t+1。

EM算法和復雜度分析如下。

算法主要分兩個步驟：一是從社會維度中挑選相似對，二是計算詞維度中特征間的距離。在第一步中，要計算兩兩向量間的距離，時間復雜的在O(m2I)級別上，其中I為迭代次數(shù)，m表示論文的數(shù)量。第二步中，時間復雜度O(Ikm)，其中I為迭代的次數(shù)，k為類的個數(shù)，m為論文數(shù)量。

K-Means算法對初始化和類的個數(shù)比較敏感，好的初始中心點對K-Means聚類算法很重要。首先介紹初始化方法，本實驗采用的方法是先在必連集合中隨機挑選一個點作為初始化中心點，在必連以外的集合中挑選第二個中心點且離第一個中心點的距離最遠，同理，第三個中心點是所有樣本點中距離前兩個中心點距離最遠的點。這樣做可以加快數(shù)據(jù)的聚類收斂速度, 由于K-Means對初始點比較敏感，該方法也能一定程度上促進聚類。

期望最大(Expectation Maximization, EM)算法是在概率模型中尋找參數(shù)最大似然估計的算法。求解式(5)中的矩陣A，同時要找到聚類的最優(yōu)效果，不斷迭代優(yōu)化聚類結果，該過程就是一個EM算法過程。下面具體介紹EM的實現(xiàn)過程。

E步 在文獻[14,18]中，通過使用能夠代表當前類的樣本點用于更新數(shù)據(jù)點的分布。在簡單的K-Means中，聚類過程中是沒有交互的，本文的方法是在E步和M步中不斷交替：E步是將每個樣本點分配到每個類中，M步將重新估計中心點和度量學習距離矩陣，在本文模型作用下使所有樣本點到各自的類中心點距離之和最小。

值得注意的是，這個分配步驟是依賴于順序的，因為M的子集和每個類有關，可能會改變樣本點的分配。做了隨機分配的實驗：每個點會分配到離它最近的類中去，同時也會涉及到最少數(shù)量的約束對。實驗表明，分配的順序不會導致聚類質(zhì)量的顯著差異，所以在評估中使用隨機分配的策略。

在E步驟中，樣本點的分配遵循的原則是保持目標函數(shù)Jmtcubc最小，因此，當所有的點都被重新分配時，目標函數(shù)Jmtcubc相比上一次將會減少或是保持不變。簡而言之，結合成對約束和度量學習來指導聚類過程使聚類達到更好的效果。

M步 用每個類中的所有點xh重新估計當前的類中心μh，因此，每個簇中的分布對于目標函數(shù)Jmtcubc來說都是最小的。因為約束違背值依賴于類的分配，而成對約束不參與中心點的重新估計步驟，所以這些在M步都不會發(fā)生，因此，只有Jmtcubc的第一個距離分量最小化，重新估計樣本中心點的步驟實際上與K-Means算法類似。

(6)

其中Mh是必連約束的子集，包含當前分配給第h個簇的點。

(7)

因為每個Ah是式(7)中的協(xié)方差矩陣之和的逆，其和不能為奇異值，如果其中任何一個元素為奇異值時，可以通過添加單位矩陣乘以矩陣A-1的跡(trace)的一部分來加以限制：Ah-1=Ah-1+εtr(Ah-1)I。從直觀上看，距離學習修改了聚類變形算法使得相似的點離得更近。

4 實驗及分析

本文在兩個數(shù)據(jù)集上驗證MTCUBC模型的有效性, 實驗結合了用戶行為特征和文本詞向量空間的特征，使用社會特征輔助詞向量空間的聚類。

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

用向量空間模型表示文本特征時，很難對稀疏高維數(shù)據(jù)集進行聚類, 因為聚類算法容易遇到局部最優(yōu)而停止迭代，從而導致聚類質(zhì)量差。在以往的研究中，文獻[19]在文本集上用SP-K-means(SParse K-means)算法，其文本集大小比單詞空間的維數(shù)小，可以看出，在大多數(shù)初始化過程中，集群之間的文檔遷移很少，這導致算法收斂后的聚類質(zhì)量較差。這種現(xiàn)象在許多實際應用中出現(xiàn)，例如，當將搜索結果聚類到網(wǎng)絡搜索引擎中時，通常聚類中的網(wǎng)頁數(shù)量是數(shù)以百萬計的，然而，特征空間的維度，對應于所有網(wǎng)頁中的單詞的數(shù)量是成千上萬的，而且因為它只包含少量的所有可能的單詞，所有每個網(wǎng)頁都是稀疏的，在這種情況下，度量學習結合成對約束方法就可以凸顯它的優(yōu)勢，并且可以顯著提高聚類的質(zhì)量。為了證明MTCUBC模型中度量學習文本聚類的有效性，本文使用了具有稀疏性、高維特征的Aminer論文數(shù)據(jù)集[17]和NIPS Papers數(shù)據(jù)集[20]。

Aminer論文數(shù)據(jù)集和NIPS Papers論文數(shù)據(jù)集，收集了大量關于計算機科學的學術論文信息, 兩個數(shù)據(jù)集都包含論文信息、論文引用、作者信息和合作者信息等, 每篇文章都包含paperID、authorID、摘要和參考文獻等屬性。在數(shù)據(jù)預處理中，本文只考慮每篇論文的前三個作者, 同樣，參考文獻的作者也是只取前三個。在兩個數(shù)據(jù)集中，將詞向量維度和社會維度分別用view1、view2表示。實驗數(shù)據(jù)集的統(tǒng)計信息如表 1 所示。

表1 Aminer 和NIPS Paper數(shù)據(jù)集信息

4.2 聚類評估

本文主要采用NMI(Normalized Mutual Information)作為聚類算法的度量標準。NMI的定義如下:

(8)

算法聚類后的簇集合表示為C={c1,c2,…,ck}，標準的聚類標簽表示為：L={l1,l2,…,lj}。其中I(X;Y)=H(X)-H(X|Y)表示隨機變量間的互信息，H(X)為X的熵，H(X|Y)為在給定Y時X的條件熵。NMI取值范圍為0～1，值越大說明聚類效果越好。

4.3 實驗結果與分析

實驗表明，在兩個數(shù)據(jù)集中，社會維度特征的加入對MTCUBC算法的實驗結果有一定的影響, 從而證明結合社會維度約束的度量學習方法的NMI值比單獨的社會維度或詞維度的聚類結果好; 同時MTCUBC模型的結果也比基于特征選擇的加權多視角聚類(Weighted Multi-view Clustering with Feature Selection, WMCFS)模型[12]、多視角聚類(Multi-view Clustering)[21]中的多視角EM算法(Multi-View EM, MVEM)的結果好, 其中WMCFS算法出自文獻[12]，它提出一種可以同時進行多維度聚類和特征選擇的方法, 該方法主要是針對高維數(shù)據(jù)稀疏提出的解決辦法。

由表2可以看出: MTCUBC模型與相對應的單維度(social-single和word-single)聚類結果相比有明顯的提升，提升效果達到10個百分點到14個百分點; 與其他兩個多維度算法(WMCFS和WMCFS)聚類結果相比提升7個百分點。

表2 MTCUBC模型在兩個數(shù)據(jù)集上與單維度和多維度方法的對比實驗

圖1表示MTCUBC模型在兩個數(shù)據(jù)集中，幾個多維度聚類模型的聚類效果與加入約束對數(shù)量間的關系?？梢钥闯觯跊]有約束的情況下：WMCFS模型變成傳統(tǒng)的K-means算法，MVEM模型變成單維度的文本聚類，MTCUBC模型的結果優(yōu)于WMCFS模型，因為從式(5)可以看出，MTCUBC模型由兩部分組成，第二部分的約束不起作用，度量學習矩陣的結果取決于第一部分，其結果優(yōu)于WMCFS模型。此時，單維度的MVEM模型優(yōu)于MTCUBC模型，MVEM聚類算法是一個基于概率的算法，準確度高于MTCUBC模型。

在加入約束后，每個方法的聚類效果都有所提升，在加入2 000個左右約束對時，聚類的提升效果不明顯，分析原因是加入的這些約束對中，很大比例的約束對相似度比較高，能被分到同一個類中，或是不能被分到同一個簇中但受到的懲罰比較小，沒能改變其最初的聚類結果。

在約束對超過2 000時，聚類效果提升比較明顯，在約束對數(shù)量達到10 000對左右時算法處于收斂狀態(tài)。在沒有約束時，MVEM算法效果比本文MTCUBC模型好，但隨著約束對數(shù)量的增加，本文模型MTCUBC的聚類效果超越了WMCFS算法。整個過程中MTCUBC算法都比WMCFS算法的效果好，WMCFS算法是使用一個合適的參數(shù)，把多個維度線性疊加，而本文模型使用度量學習方法將多個維度結合，度量矩陣能影響到每個向量中的元素，而非簡單的維度之間的疊加關系。

圖1 MTCUBC模型與幾個多維度算法在兩個數(shù)據(jù)集上NMI對比

5 結語

為提高聚類效果，除利用文本自身內(nèi)容外，還充分利用和文本內(nèi)容相關的用戶行為信息，帶約束的聚類方法結合度量學習方法來改善傳統(tǒng)多維度聚類中不同維度線性結合問題，使得用戶行為信息在聚類過程中充分發(fā)揮作用; 同時，每個簇中都會學習出一個度量矩陣，改善多個類共用一個度量矩陣的情況。本文中對懲罰的開銷值ωij有待細化，深究每一維數(shù)據(jù)的權重值。

在未來的工作中，為得到更準確的聚類結果和充分利用社會信息，擬研究如何利用更多空間聚類結果來互相輔助提升聚類效果。例如，可以將社會維度，詞維度、主題維度等特征綜合利用，并使用雙向輔助作用來提高聚類結果。