改進特征權重的短文本聚類算法①

馬 存,郭銳鋒,高 岑,孫 詠

1(中國科學院大學,北京 100049)

2(中國科學院 沈陽計算技術研究所,沈陽 110168)

1 相關工作

隨著移動終端智能化的發展,紛繁多樣的短文本信息充斥著互聯網的各個角落.由于短文本信息少,口語化嚴重,網絡新詞多,使用傳統的文檔聚類會導致向量空間模型高度稀疏,缺乏語義信息,所以需要針對短文本的固有特點尋求一種有效的模型表示和聚類方法.

傳統的向量空間模型,主要通過特征詞和權重來表示短文本數據,它的缺點也很明顯,它忽略了同義詞在語義中的貢獻并且會出現特征稀疏的問題,進而造成維數災難.為了解決短文本特征稀疏的問題,一些學者研究了外部信息增強的方法,對短文本特征進行擴展,從而提高聚類效果[1–3].然而語義擴展方法并沒有解決“維數災難”的問題,還帶來了新的問題,比如聚類的效果完全依賴于知識庫的豐富程序,無法識別新興的網絡新詞,比如 2016 年流行的“老司機”,“發車了”等.另有一部分學者通過原始高維特征詞空間映射到低維的潛在語義空間或主題空間,挖掘文本潛在的語義結構[4–6].但這種模型忽略了低頻詞的貢獻,尤其是短文本中貢獻度高的低頻詞,導致上述模型應用于網絡短文本中的效果很差.

詞向量是一種基于大量未標注的語料學習而來的低維分布式實數向量,充分挖掘了同義詞之間的共現關系[7,8].基于此,本文結合短文本的特點和詞向量的優勢,提出一種改進的特征詞權重并結合松弛詞語移動距離(RWMD)的短文本聚類算法.首先,定義多因子權重規則,如文本中詞性和情感詞,對于情感詞的處理主要包括文字和表情符號,接著使用Skip-gram模型基于定義好的權重規則訓練特征詞向量,最后引入RWMD距離計算文本之間的相似度并以此聚類.實驗結果表明本文提出的方法切實可行,尤其是在網絡短文本中效果明顯.

2 改進的特征詞向量及聚類模型框架

2.1 改進策略

短文本數據,尤其是論壇帖子,商品評論以及微博和微信的聊天記錄,形式復雜多樣,包含各種表情符號,在數據預處理階段不能簡單的將表情符號當作噪聲直接去除,否則會失去一部分語義信息,即情感信息;另外由于數據包含的短文本的長度也大小不一,因此關鍵詞的位置因素也必須考慮在內;再者就是詞性對短文本的影響[9],名詞、動詞、形容詞和副詞是文本特征的重要組成部分,因此詞性的貢獻也不容忽視.基于此,本文在文獻[8]中提出的特征權重計算法進行了修改,提出一種融合表情符號、位置因素以及詞性信息的多因子加權策略的關鍵詞提取方法:

式中,Weight(w)表示詞語w在文本d中的權重,Weightsen表示單詞w在文本d中情感所占的權重,α,β,γ為加權系數,他們之和為1.Weightpos和Weightlen的計算公式參考文獻[8],Weightsen的計算公式為:

其中,tf(wi,d)表示特征Wi在文本d中的詞頻;N表示文本總數;表示所有文本集中出現第i個詞語的文本數量;senwi表示該詞的情感加權值,其具體值需要根據文獻[10]的研究內容加以定義,將表情符號歸為7個情感類別,結合實驗用數據集,分別統計每一類情感所占比例,以此比例作為senwi的加權值.定義如表1所列.

表1 情感類別系數

在預處理階段,當文本中含有表情符號時,會根據表1中的希臘字母進行替換.若一個短文本中含有多種表情符號,則根據多個表情符號的權值綜合計算其權重;若一個文本中不含有表情符號,則在特征詞權重的計算公式中,第3項將為0.即:

此時,α取經驗值0.6.本文將此模型記為EFA(Emotion Fusion Algorithm)算法.

2.2 訓練特征詞向量

本文使用Mikolov[11]提出的基于Hierarchical Softmax構造的Skip-gram模型訓練詞向量,它主要包括 3層結構:輸入層,投影層和輸出層,目標函數L如式(1)所示:

其中,V是數據詞典,Context(w)表示單詞w的上下文窗口,一般窗口值取5到10效果較好.

2.3 以特征詞表征的短文本相似度計算

文本采用RWMD距離算法來計算文本之間的語義相似度,RWMD算法是基于WMD算法放松限制條件來降低算法的復雜度[12]改進而來.RWMD算法是將一個短文本的特征詞向量全部流向另一個短文本的特征詞向量所經過的距離總和的最小值作為兩個短文本之間的語義相似度.

2.3.1 特征詞之間的語義相似度

RWMD算法在計算文本的相似度之前需要先計算特征詞之間的相似度,衡量兩個特征詞之間的相似度使用歐式距離來計算,即:

L的值越小,說明兩個詞越相近.

2.3.2 短文本之間的相似度計算

使用RWMD距離計算短文本d中所有特征詞流向短文本d′中所有特征詞距離和的最小值作為短文本d和短文本d′之間的相似度.假設允許短文本d中的每個特征詞可以流向d′中的任意一個特征詞,矩陣T ∈ Rn×n是轉移矩陣,其中Tij≥0,表示詞語i有多少轉移到了詞語j,C(i,j)表示詞語i和詞語j之間的語義相似度,目標函數為:

約束條件為:

2.4 K-means聚類算法流程

輸入:實驗所用的短文本數據集.通過數據預處理,并加權計算融合情感詞權重的特征詞集合,并由Softmax模型訓練而成的特征詞向量.輸出:具有K類的短文本集合.Step 1.指定聚類數目K,以及K個初始聚類中心.Step 2.指定 RWMD 算法為距離函數.Step 3.計算每個文本向量d與K個初始聚類中心的RWMD距離,將每個文本向量d分配給距離最小的聚類中心.Step 4.重新計算新的K個聚類中心.Step 5.重復 Step 3 及 Step 4,直到聚類中心小于閾值.

3 實驗與結果分析

3.1 實驗數據

本文采用了3種類型數據集:微博數據、文本分類通用數據和QQ群聊天數據.其中文本分類通用數據集從中選取5個類別的標題;聊天記錄數據人工標注出若干個聊天片段.具體描述如表2所示.

3.2 評價指標

為了使結果更有對比性,本文采用了文本聚類常用的準確率、召回率、和宏平均作為實驗結果的評價指標:

其中,Pij、Rij和Fij表示類別i在類簇j中的準確率、召回率和F1值,Ci表示正確類別i中的文本數,Cj表示結果中類簇j中的文本數,Cij表示結果中類簇j中原本屬于類別i的文本數,對于類簇j取各個類別中Fij最高的作為類別i的F1值,Fmacro表示宏平均的結果,m表示原始類別的個數.

3.3 實驗結果與分析

本文使用VSM,LDA和BTM這3中模型對文本進行表示來驗證模型的可行性和有效性,分別將結果記為KM-VSM、KM-LDA、KM-BTM,本文提出的模型結果記作KM-EFA.其中VSM中使用TF-IDF作為特征權重,LDA模型和BTM模型中主題數設為15,超參數 α和β 取經驗值50/K,β=0.01,迭代次數為2000.

3.3.1 對比實驗

在上文中介紹的3個數據集上分別使用上述4 種方法進行實驗,使用平均F值作為評價指標,結果如表3所示.從表中可以看出,基于主題模型的聚類評測結果一般要好于基于VSM模型的聚類結果,說明無法發現同義詞之間語義關系的模型會受到短文本數據特征稀疏的影響;基于BTM模型的聚類評測效果優于基于LDA模型的聚類效果,說明在短文本特征比較少的時候基于主題概率的統計方法統計出的數據意義不大.其中模型KM-EFA1是不考慮情感因素只考慮詞性和位置因素的評測結果,而KM-EFA2是考慮了所有因素的評測結果.對比發現,本文提出的方法評測結果要優于對比方法,在3個數據集的試驗中,性能比次優的結果平均提高了13.62%,從而驗證了本模型使用情感加權更能挖掘出詞之間的語義相似性,從而提高聚類效果.

表3 模型在數據集上的評測結果

3.3.2 特征值參數與權重系數分析

為了校驗特征詞選擇過程的參數K以及情感權重加權系數 γ對聚類的影響,本文在3個數據集上分別取γ等于 0.1、0.25 和 0.45,同時對參數K在[5,100]范圍以步長為5,進行遍歷,結果如圖1所示.

從圖中可以看出,當情感權重系數不同時,隨著K的變化,F值也變得有所不同.綜合來說,當特征K在[40,50]之間時,F值表現最好,這是因為K太小時,特征個數不足以表達完整的語義,當K太大時,句子的主題信息不明顯,會造成“富者越富”的現象,影響聚類效果.另外,當數據集中表現情感的詞比較多時,情感權重的大小會直接影響聚類的好壞.如微博和聊天數據含有大量情感詞,聚類的效果完全由情感權重決定,但在普通的分類文本中情感權重越大聚類效果則越差.

圖1 特征個數與權重參數分析

4 結束語

本文融合情感加權的方法有效的提高了短文本的聚類效果,尤其在微博微信等即時聊天的短文本數據中,效果更好,這是因為在這類文本中人們使用表情符號的頻率相對普通文本較高,此方法能充分挖掘符號下的語義信息.但隨著深入的研究,這類文本中也充斥著大量的不規范用語,如“狗帶”,“一顆賽艇”等,這些不規范用語對聚類結果產生一定的影響,尤其是一些拆分字沒有辦法對其準確的表示,比如“古月哥欠”,表達的是胡歌,但經過分詞之后,這幾個字會變得毫無意義,雖然這類詞語出現頻次較低,但往往這類詞語是短文本的核心語義,同時用戶故意使用這類詞語一般均會涉及不正當言論,是網絡監督和輿情管理的重要分析方向.因此,對這種現象的研究,具有重要的現實意義.