結合新概念分解和頻繁詞集的短文本聚類

賈瑞玉，陳勝發(fā)

(安徽大學計算機科學與技術學院，合肥230601)

1 引 言

文本聚類作為高效組織、導航、檢索和總結大型文本集合的重要工具，受到了廣泛的關注.因此，對短文本進行聚類有很大的應用價值，例如:可以挖掘用戶評論中的觀點［1］，檢測社交媒體中的話題［2］和情感分析［3］等.由于短文本表達靈活多樣，文字簡短且增長迅速，所以特征稀疏、特征難提取和噪音數據多等特點，傳統(tǒng)的適合長文本以及小數據量的聚類算法是難于處理，因此有效的短文本聚類算法需要被研究出來.近年來，基于矩陣因子的文本聚類方法已經得到了廣泛的應用.特別是非負矩陣因子分解(Nonnegative Matrix Factorization，NMF)［4］和概念因子分解(Concept Factorization，CF)［5］.

一般來說，NMF 的目標是找到兩個非負矩陣因子，它們的乘積與原始數據矩陣近似.NMF 中的非負約束產生了基于部件的文本文檔表示，因為它們只允許加法組合，而不允許減法組合［6］.NMF 的主要限制是它只能在數據點的原始特征空間中執(zhí)行.為了解決這一局限性，Xu 和 Gong 提出了CF 方法［7］，CF 保留了NMF 的所有優(yōu)點，也可以在任何數據表示空間［8］中執(zhí)行.在文檔聚類中使用CF 方法時，每個文檔都由聚類中心的線性組合表示，每個聚類中心由數據點的線性組合表示.由于線性系數具有明確的語義意義，因此可以很容易地從這些系數中得到每個文檔的標簽.

最近的研究表明，在機器學習中使用額外的監(jiān)控信息可以提高學習性能［9，10］.為此，通過使用監(jiān)控信息來指導學習過程的方法提出了許多關于CF 的擴展.監(jiān)控信息要么合并到基本CF 模型中，要么合并到圖結構中.在這些CF 的擴展中，約束概念分解(Constrained Concept Factorization，CCF)［11］使用確切的標簽信息作為額外的硬約束.這個模型確保在新的表示空間中將具有相同類標簽的數據點嚴格地映射表示.CCF 的局限性在于它忽略了數據集的局部幾何結構信息.為了解決這個問題，局部正則化約束概念分解(Local Regularization Cons-trained Concept Factorization，LRCCF)［12］將局部幾何結構信息和標簽信息合并到CF 模型中.約束鄰域保留概念分解(Constrained Neighborhood Pre-serving Concept Factorization，CNPCF)［13］使用含有必要連接約束形式的監(jiān)控信息來修改圖.然而，當監(jiān)控信息是有限的時候，這些信息無法有效的保持數據集的幾何結構.因此，有必要提出一種新的CF 框架，它可以利用無約束數據點并且同時保持數據集的局部幾何結構.

對于傳統(tǒng)文本表示的語義缺失和高維問題，基于頻繁詞集的文本聚類可以很好的解決.在文本集中有很多文本都出現某些詞，這些詞的集合被稱為頻繁詞集，并且這些詞的集合可以對一些關于主題的語義起到很好的表示作用.文獻［14］對文本表示是使用挖掘出的頻繁詞集，并且對于文本之間的相似度也是使用共有的頻繁詞集的數量來表示的，然后進行文本聚類.文獻［15］提出了一種基于頻繁詞集的文本聚類方法(frequent itemsets based document clustering method，FIC).該方法首先對預處理過的文本集進行頻繁詞集的挖掘，然后采用挖掘出來的頻繁詞集來構建文本表示模型，接著將每個文本看作節(jié)點，文本間的相似性看作節(jié)點之間的邊，來構建成文本網絡，最后使用社區(qū)劃分的算法進行文本聚類.

為了解決傳統(tǒng)文本表示的高維和語義缺失，本文利用文獻［15］的優(yōu)點，提出了一種結合新概念分解和頻繁詞集的短文本聚類(Combining new con-cept factorization with frequent itemsets for short text clustering，CFFIC).該方法首先挖掘出頻繁詞集，運用頻繁詞集來構建文本表示模型.然后利用無約束數據點，提出了正則化概念分解(Regularized concept factorization，RCF)進行聚類.該算法不僅能對處理后的文文本的維度起到很好的降低作用，還可以很好的關聯(lián)短文本集中文本，并且提出的新正則化概念分解算法(Regularized concept factorization，RCF)很好解決了CF 算法在監(jiān)控信息不足的情況下的缺陷，使得聚類效果得到了有效提升.

2 CFFIC 算法

CFFIC 算法流程圖如圖1 所示.該算法使用頻繁詞集構建的文本表示模型可以很好解決數據稀疏和維度的問題.

圖1 CFFIC 算法框架Fig.1 CFFIC algorithm framework

圖1 表示本文算法的主要過程，分別為預處理、頻繁詞集挖掘、文本表示、新概念分解、獲得結果.首先預處理就是對文本集進行分詞和去停用詞;然后挖掘出頻繁詞集，使用這些頻繁詞集構建文本表示模型;最后使用RCF 算法進行文本聚類以獲得結果.算法中的關鍵步驟的具體介紹如下.

2.1 頻繁詞集挖掘

本文采用文獻［16］中的算法進行頻繁詞集的挖掘.該算法的最小支持度是通過文本的數量來獲得，然后挖掘出頻繁詞集(特征選擇之后).相關定義如下:

定義1.(文本數據庫)就是進行過分詞和去停用詞的文本組成的，定義為 A={A1，A2，…，An}.

定義2.(頻繁詞集)通過最小支持度，得到頻繁詞集集合，定義為 O={O1，O2，…，Om}，其中 Oi表示一個頻繁詞集，Oi={w1，w2，…，wt}，其中 wi表示一個詞.

2.2 文本表示模型

本文算法是使用頻繁詞集構建文本表示模型.也就是構建文本-頻繁詞矩陣M，矩陣M 為0-1 矩陣，定義如下:

其中，M［i］［j］表示矩陣 M 中文本 Ai是否存在頻繁詞集 Oj，若文本 Ai中有頻繁詞集 Oj，則 M［i］［j］=1，否則M［i］［j］=0.使用頻繁詞集來代替文本中的特征單詞的方法可以很好的解決維度和文本稀疏的問題.頻繁詞集本身是可以反映出文本的主題，例如:{window}表示裝飾類，{apple}表示水果類，若{apple，window}同時出現可以表示出計算機類，而{apple，window}就是一種頻繁詞集.因此，文本間相似度用頻繁詞集來計算，可以很好的避免不同文本產生過大的相似度而影響聚類效果.

2.3 RCF 算法

正如我們前面提到的，在有空監(jiān)控信息的情況下，傳統(tǒng)的CF 算法的很難利用任何監(jiān)控信息.下面詳細介紹一種充分利用監(jiān)控信息的新型正則化CF 方法.

關于監(jiān)控信息，明確的標簽信息可能難以收集.在實踐中，我們發(fā)現了另一種相對容易獲取監(jiān)控信息的方式.我們稱之為對偶連通約束信息.具體地說，一對具有相同標簽的數據點表示為必要連接約束，否則表示為不能連接約束.然而，相反的過程可能是不正確的.換句話說，一般情況下僅從對偶連通約束中直接導出數據點的顯式標簽是很難的.這表明，對偶連通約束提供了一種監(jiān)控信息，這種信息本質上是較弱的，因此比數據點的實際標簽更通用.所以在下面的RCF 方法中，雙連通約束作為先驗信息.

一般情況下，約束信息的獲取是非常困難的，因為在這個過程中需要投入大量的人力和物質.但CF 方法在有限的約束信息的情況下，其性能是無法得到很大的提高.為了克服這一局限性，我們將這些約束映射到無約束數據點上，來獲得整個數據集的約束信息.然后將獲取的約束信息添加到CF 目標函數中，構建RCF 模型.

2.3.1 約束傳播

傳播過程可以看作是一個兩類分類問題［17］.一對約束數據點之間的關系可以編碼為+1 或－1.傳播過程決定了兩個無約束數據點之間的約束關系.這個過程完全等價于對標記為+1 的類或標記為－1 的類之間的關系進行分類.

Step 1.通過定義 k-NN 圖的權重矩陣 W={wij}N×N，構造一個k-NN 圖，wij的定義如下:

Step 2.計算歸一化圖的拉普拉斯矩陣 L=I－D－1/2WD－1/2，其中是一個對角矩陣，dii=∑jWij.

Step 5.F*=是傳播的對偶連接約束的最終表示，其中是 {Fh( t )}的極限.

Step 6.通過利用F*和原始權重矩陣W 構造一個新的權重矩陣

通過上述方法，可以收集更多關于數據集的約束信息.利用對偶連接約束信息重構權值矩陣.也就是說，如果一對數據點屬于同一個類，那么連接它們的邊的相應權值就會被賦一個大得多的值，否則權值就會被賦一個小得多的值.

2.3.2 RCF 的目標函數

在本小節(jié)中，我們通過將權重矩陣嵌入CF 目標函數，詳細介紹了 RCF 的構造.以下術語用于保存數據集的監(jiān)控信息:

當xi和xj具有相同的類號時，xi應該和xj一起出現在原始幾何空間中，并且會被賦一個較大的正值.根據的定義的值也會很大.最小化 φ( V )，vi和 vj應該有一個較小的歐式距離，這樣在低維表示空間中vi和vj也應該彼此靠近的.相反，當xi和xj具有不同的類號時，xi和xj應該在幾何空間中彼此遠離，并且會被賦一個較大的負值，從而的值會較小.因此，當vi和vj屬于一個類時，vi和vj的結果會有很大的不同.根據上面的分析，我們發(fā)現在低維表示空間中φ( V )可以產生一起出現的具有相同標簽的點和彼此之間距離非常遠且屬于不同類的點.這與原始空間中點的內在幾何關系是一致的.通過最小化(5)，利用有限的對偶連通約束信息可以有效地保持數據集的原始幾何形狀.如果選擇歐氏距離來度量近似的質量，則RCF 的目標函數為:

在公式(6)中，第一部分可以看作是重構項，這一項可以保證近似的效果.第二部分可以看作是一個約束項，這一項的目的是保持數據空間原有的幾何結構.在RCF 目標函數中，正則化參數λ≥0 控制這兩個部分的比例.

2.3.3 更新 RCF 規(guī)則

公式(6)中的目標函數可以重寫為:

其中tr(·)為矩陣的軌跡，D～ 表示對角矩陣，其項是 ～W 的列和.

對于uij＞0 和vij＞0，我們分別分配兩個拉格朗日乘數ψ=［ψij］和 φ=［φij］.ψij和 φij是包含拉格朗日乘數的矩陣.然后，目標函數可以重寫為:

公式(14)中，關于U 和V 的偏導為:

使用 Karush-Kuhn-Tucker(KKT)(條件為 ψijuij=0 和φijvij=0)，我們會有以下關于uij和vij的方程.

上述最小化目標函數O 的方法并不是唯一的.如果U 和V 是 O 的解，UQ 和 VQ－1也會形成任意正對角矩陣 Q 的解，這是很容檢驗的.因此，我們進一步規(guī)范化解決方案，使其惟一.設uc為U 的列向量，在和 UVT不變的條件下，對U 和V 進行歸一化更新:

3 實驗及結果分析

為了說明本文算法如何提高短文本聚類的性能，我們將CFFIC 算法與3 種具有代表性的短文本聚類算法進行比較，分別是 FIC、CNPCF 和 RNMF.RNMF 則采用 l2，1范數設計目標函數.并且這3 種算法與CFFIC 算法都使用TF 作特征度量.

3.1 評價標準

通過將每個文檔的聚類標簽與數據集提供的原始標簽進行比較，評價聚類結果.采用準確度(AC)和歸一化互信息度量(NMI)兩種標準度量來度量聚類性能.該準確度用于計算正確預測標簽的百分比，定義為:

采用歸一化互信息矩陣來表示兩個簇的相似性.給定兩個簇C 和C'，對應的互信息矩陣計算為:

其中p(ci)和p(cj')分別表示隨機選取的數據點屬于類簇C和C'的概率，p(ci，cj')表示所選點同時屬于兩個簇的概率.

在實驗中，使用標準化度量 NMI(C，C')∈(0，1)，定義如下:

其中H(C)和H(C')表示C 和C'的熵.當選取的兩個樣本相同時，NMI 取 1，當兩個樣本完全獨立時，NMI 取 0.NMI 值越大，表明聚類性能越好.

3.2 實驗數據

本文算法的實驗是使用搜狐新聞數據集和新浪微博數據集.實驗隨機選取了搜狐新聞數據集中10 個類別的數據作為Sohu 短文本數據集，各類別名稱及短文本數量如表1 所示.實驗對新浪微博數據集是按預先設置的10 個區(qū)分度最高的主題詞分別抽取相關數據作為Weibo 短文本數據集.各類別名稱及短文本數量如表2 所示.

表1 Sohu 短文本數據集Table 1 Dataset of Sohu essay

3.3 相關算法的參數設置

由于 CFFIC 算法、FIC 算法、CNPCF 算法和 RNMF 算法都要指定k 值大小，所以將這四種算法的 k 值大小設置為Sohu 短文本數據集和 Weibo 短文本數據集的類別數目.CNPCF 和CFFIC 都需要使用監(jiān)控信息，并且為了說明在監(jiān)控信息非常有限的情況下，本文算法的有效性，監(jiān)控信息量設置為t=2%.而且通過多次實驗得到能保證每個文本以至少5個頻繁詞集來表示的最小支持度最好.

表2 Weibo 短文本數據集Table 2 Dataset of short articles on Weibo

3.4 聚類性能比較

由于 Sohu 和Weibo 數據集中的每一條短文本都具有分類標簽，因此聚類質量(NMI 和AC)和運行時間是評價各個短文本聚類算法的非常好的標準.對比實驗中，每個算法都以數據集的前1 萬條數據，并以1 萬的數量進行增加的方式進行多次短文本聚類實驗.表3 和表4 分別為各種算法在兩個數據集不同短文本數量情況下的 AC 和 NMI 的實驗結果，圖2 和圖3 則為相應的運行時間對比情況.

圖2 Sohu 的運行時間Fig.2 Running time of Sohu

圖3 Weibo 的運行時間Fig.3 Running time of Weibo

3.4.1 聚類質量

首先就是聚類質量對比，從表3 和表4 可以看出，在兩個數據集的各個不同短文本數量下CNPCF 和CFFIC 的AC 和NMI 均優(yōu)于RNMF，這是因為CF 繼承了NMF 的所有優(yōu)點，作為擴展的CF 也是優(yōu)于NMF 的擴展.此外，可以發(fā)現雖然在 Sohu 數據集上 CNPCF、CFFIC 以及 FIC 的 AC 和 NMI 的數值較為接近，但在Weibo 數據集上CFFIC、FIC 要明顯優(yōu)于CNPCF，其中FIC 的 AC 和 NMI 的平均值分別比 CNPCF 提高了 39.2% 和 23.7% ，而 CFFIC 的 AC 和 NMI 的平均值分別比CNPCF 提高了40.5% 和24.7%.原因在于書寫微博內容比較隨意但書寫新聞標題是需要嚴謹規(guī)范的，因此Weibo數據集的噪音數據的數量比 Sohu 數據集多，而采用頻繁詞集進行特征選擇的具有更好的魯棒性，可以降低噪聲數據對于聚類質量的影響.

表3 Sohu 數據集的AC 和NMITable 3 AC and NMI of Sohu dataset

表4 Weibo 數據集的AC 和NMITable 4 AC and NMI of Weibo dataset

3.4.2 運行時間

其次在運行時間對比方面，從圖2 和圖3 可以看出，在兩個數據集上 CFFIC 均要明顯優(yōu)于CNPCF、FIC 和RNMF，并且隨著短文本數量變得越大的時候，運行時間的差距就越大.例如，在 Weibo 數據集中，當短文本數量達到最大時，CFFIC僅需要123s，而 CNPCF、FIC 和 RNMF 分別需要 305s、154s和 337s.CFFIC 比 CNPCF 和 RNMF 的運行時間少很多，是因為CFFIC 采用頻繁詞集代替詞來構建文本表示模型，這樣就大大的降低了數據的維數，計算復雜度也大大的降低了.但是同樣都是使用頻繁詞集來構建文本表示模型的，CFFIC 比FIC 的運行時間快，這是因為FIC 需要計算每個文本對象之間的相似度，而CFFIC 則不需要這樣計算，所以CFFIC 在運行時間上快于FIC.

4 結 論

本文提出了一種新的正則化概念分解方法，通過傳播有限約束信息來獲取更多的約束信息，并利用這些約束信息來保持數據空間的幾何結構，提高了聚類的性能.使用頻繁詞集來構建文本表示模型，解決了數據稀疏和高維的問題.由于考慮了多個文本間的關系，聚類性能再一次得到了一定程度的提升.通過2 個短文本數據集的實驗，表明了 CFFIC 具有較好的聚類質量和較小的時間開銷.至今文本聚類一直是一個值得深入研究的課題，其面臨著數據集規(guī)模海量增長的問題.因此，在下一步工作中，將重點研究基于Spark 的CFFIC 的實現方法，目的在于讓其可以處理更大規(guī)模的短文本聚類問題.