賈瑞玉，陳勝發(fā)

(安徽大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，合肥230601)

1 引 言

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

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

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

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

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

2 CFFIC 算法

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

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

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

2.1 頻繁詞集挖掘

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

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

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

2.2 文本表示模型

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

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

2.3 RCF 算法

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

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

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

2.3.1 約束傳播

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

Step 1.通過定義 k-NN 圖的權(quán)重矩陣 W={wij}N×N，構(gòu)造一個k-NN 圖，wij的定義如下:

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

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

Step 6.通過利用F*和原始權(quán)重矩陣W 構(gòu)造一個新的權(quán)重矩陣

通過上述方法，可以收集更多關(guān)于數(shù)據(jù)集的約束信息.利用對偶連接約束信息重構(gòu)權(quán)值矩陣.也就是說，如果一對數(shù)據(jù)點(diǎn)屬于同一個類，那么連接它們的邊的相應(yīng)權(quán)值就會被賦一個大得多的值，否則權(quán)值就會被賦一個小得多的值.

2.3.2 RCF 的目標(biāo)函數(shù)

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

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

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

2.3.3 更新 RCF 規(guī)則

公式(6)中的目標(biāo)函數(shù)可以重寫為:

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

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

公式(14)中，關(guān)于U 和V 的偏導(dǎo)為:

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

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

3 實驗及結(jié)果分析

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

3.1 評價標(biāo)準(zhǔn)

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

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

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

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

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

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

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

表1 Sohu 短文本數(shù)據(jù)集Table 1 Dataset of Sohu essay

3.3 相關(guān)算法的參數(shù)設(shè)置

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

表2 Weibo 短文本數(shù)據(jù)集Table 2 Dataset of short articles on Weibo

3.4 聚類性能比較

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

圖2 Sohu 的運(yùn)行時間Fig.2 Running time of Sohu

圖3 Weibo 的運(yùn)行時間Fig.3 Running time of Weibo

3.4.1 聚類質(zhì)量

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

表3 Sohu 數(shù)據(jù)集的AC 和NMITable 3 AC and NMI of Sohu dataset

表4 Weibo 數(shù)據(jù)集的AC 和NMITable 4 AC and NMI of Weibo dataset

3.4.2 運(yùn)行時間

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

4 結(jié) 論

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