基于支持向量機的短文本分類方法

趙延平,王 芳,夏 楊

(北京交通大學信息中心,北京 100044)

0 引 言

隨著互聯(lián)網(wǎng)的興起，越來越多的商家關心用戶對其產(chǎn)品的咨詢和評論，從而進行用戶滿意度分析、傾向性分析和用戶關聯(lián)性分析，以便給商家提供更良好的決策支持。分析用戶的咨詢針對的是哪類產(chǎn)品或哪方面問題，是一種文本分類方法。在電信領域中，用戶的咨詢都在160字以內，稱為短文本。本文針對這些短文本進行主題分類，對子串和子序列特征進行度量，利用SVM分類器實現(xiàn)分類。

1 相關工作

常見短文本分類有2種方法。一是利用搜索引擎擴展短文本[1]，這種分類方法僅僅擴展了文本，但對無效信息和噪聲處理不佳，且消耗時間長，并且分類效果對搜索引擎依賴較大。二是在短文本特征的基礎上，利用知識庫，發(fā)現(xiàn)詞之間的語義關系[2]，如維基百科，利用語義特征進行分類；還有一種分類方式是利用短文本隱藏的主題作為額外特征集，與原始特征一并用于訓練和分類[3]。這2種方式都是在人工干預的情況下擴展特征，然后進行相似度計算，雖然也可以取得不錯的效果，但獲取有效特征比較困難。本文擺脫這種外部依賴，針對特定領域，提出利用Web模式序列挖掘PLWAP算法[4-5]得到頻繁子串和子序列特征從而進行分類，經(jīng)實驗，得到了良好的效果。

2 Web模式序列挖掘算法PLWAP

WAP算法對項目的前綴樹進行挖掘，PLWAP算法基于WAP算法[5]，對某個項目的后綴樹進行挖掘。PLWAP-Tree算法描述如下：

算法：PLWAP-Tree

輸入：Web訪問序列數(shù)據(jù)庫WASD；

支持度閾值λ(0<λ≤1)；

頻繁事件集L。

輸出：PLWAP-Tree

方法：

1)掃描原始數(shù)據(jù)，得到頻繁項目FE集合

2)再次掃描FE中每個event

If current tree node has children

if event is one of the child:

the count of current node=count +1

else:

insert into tree as a new node

the count of new node =1

position code=rightmost child node position code +′0′

endif

else:

insert into tree as a new node;

the count of new node=1

position code=parent node position code +′1′

endif

之后對PLWAP-tree進行挖掘，輸出所有滿足最小支持度閾值的頻繁模式。

本文采用這種方法得到所有頻繁子串和子序列。

3 咨詢短文本分類方法

3.1 研究背景及意義

本文數(shù)據(jù)集來源于某移動公司客服平臺的真實數(shù)據(jù)，該平臺每天實時接收用戶通過手機/Web對運營商所提供的各種業(yè)務的實時咨詢，并對問題進行自動回復。本文收集了4個月的數(shù)據(jù)，有百萬條級別的文本。把所有文本分為4類，分別是介紹、開通、使用、取消。介紹類是用戶對業(yè)務的了解；開通類是用戶針對如何開通或開通過程中的咨詢；使用類是指用戶開通后，在使用過程中的咨詢，另外，優(yōu)惠類咨詢和比較類咨詢本文都統(tǒng)一歸為使用類；取消類是針對如何取消或取消過程中的咨詢。以下以彩鈴業(yè)務咨詢語句為例，其中的實驗數(shù)據(jù)集描述如表1所示。

表1 實驗數(shù)據(jù)集描述

本文的目標是分析每一條無結構化的用戶咨詢文本，得到結構化信息用于支持企業(yè)進一步地對不同業(yè)務的統(tǒng)計分析。它分為4子任務：1)識別用戶發(fā)送信息的情緒傾向；2)分析表達情緒所針對的業(yè)務[6]；3)分析信息的主題；4)對用戶發(fā)送信息形成摘要。例如對于表1中的第一條咨詢語句，系統(tǒng)所抽取的信息如下：

情緒傾向：“非負情緒”

相關業(yè)務：“彩鈴”

相關主題：“介紹”

文本摘要：“彩鈴如何收費”

本文主要完成第三個子任務。

3.2 分類特征

通過觀察每類特征，發(fā)現(xiàn)每種類別經(jīng)常會出現(xiàn)一些詞或串，如開通類經(jīng)常會出現(xiàn)“開通”“如何開通”“怎樣開通”，取消類經(jīng)常會出現(xiàn)“取消”“如何取消”“怎么取消”，使用類經(jīng)常會出現(xiàn)“怎么用不了”“怎么不能下載”“為什么……卻……不”等，類似地，其他主題也會有相應的模式。這種模式分別是文本的字串和子序列，直觀上這2種特征是很有用的分類特征。

由于針對漢語的依存語法分析準確率和時間效率尚不高，所以本文未對句子進行依存語法的分析，因而，本文主要使用第一種特征，即句法特征。它可以分為2類：子串(在語句中連續(xù)出現(xiàn))和子序列(在語句中按順序出現(xiàn))：

1)子串：在一個字符串中連續(xù)出現(xiàn)的元素形成的串稱為子串。針對語句有不分詞和分詞2種情形：

①N-gram：一個N-gram(N=1, 2, 3)是一條語句中連續(xù)出現(xiàn)的N個字形成的字串。

②公共頻繁詞語串(frequent common word substring)：將語句進行分詞，頻繁出現(xiàn)的一個或連續(xù)多個詞語形成的串。例如語句“我的手機7610,請問網(wǎng)絡怎樣才能使用？怎樣才能開通網(wǎng)絡？”，若其子串“怎樣才能開通”在其他語句也經(jīng)常出現(xiàn)，則稱該子串為公共頻繁詞語串。

2)公共頻繁子序列(frequent common subsequence)：對語句分詞后，頻繁出現(xiàn)的且保持順序的一個或多詞語構成的子序列。對語句分詞是為了在得到意義明確的頻繁子序列時，避免生成單字組成的子序列。例如語句“開通移動網(wǎng)絡收費嗎？”，經(jīng)過分詞處理：“開通 移動 網(wǎng)絡 收費 嗎？”，可能計算得到的頻繁子序列是：“開通……收費……”。

3.3 特征抽取

如何確定支持度閾值是個關鍵問題，當給定支持度閾值較小時，可能會帶來大量的冗余特征的問題，當給定支持度閾值較大時，得到的特征對分類沒有幫助，因而，本文要進行特征選擇。最常用的特征度量方法有信息增益(Information Gain， IG)、卡方統(tǒng)計量(CHI)、互信息(Mutual Information， MI)、詞頻(Document Frequency， DF)等。文獻[7]選取高指示性特征用于分類。文獻[8-11]利用互信息進行特征選擇，然后獲取主題詞，再把這些詞擴充到短文本的特征中進行分類。文獻[12-14]建立規(guī)則庫作為特征進行分類。文獻[15-17]針對中文文本分類中的特征方法進行了對比。在實際應用中，本文采用了信息增益、互信息、卡方統(tǒng)計這3種特征選擇方法并進行對比。但限于篇幅，本文僅介紹信息增益的定義：

假設文本D有m種類別C1,C2,…,Cm，P(Ci)表示未給定任何特征時類別Ci出現(xiàn)的概率，P(Ci|f)表示給定特征f時類別Ci出現(xiàn)的概率，則一個特征f的信息增益是在給定特征f下文本的熵與未給定任何特征時文本的熵的增益，形式化如下：

Gain(f)=Entropy(D)-Entropy(D|f)

然而，眾所周知，有些度量(比如CHI)對于低頻詞的度量不夠準確。另外，筆者發(fā)現(xiàn)在給定領域下，用戶咨詢中頻繁出現(xiàn)的子序列或子串具有較強的語義，并體現(xiàn)一定的情感。為了抽取這些特征，提出使用基于半監(jiān)督的方法進行特征選擇(見圖1)，可以分為如下2個步驟：

圖1 基于半監(jiān)督的特征選擇

1)通過頻繁挖掘算法獲取頻繁子串和子序列，形成候選特征集。

2)在有標記的文本上計算IG/MI/CHI，選擇其取值高的特征，得到有效的特征集。

一些典型的特征如表2所示。

表2 典型特征舉例

這種特征選擇方法有效地使用了大量未標記文本中的信息，避免訓練語料不足導致的被忽略的低頻度特征，保證選擇滿足一定頻度的特征。

3.4 部分冗余特征的處理

使用頻繁子串特征和頻繁子序列特征帶來的一個問題就是可能會帶來冗余，因為對于任意頻繁子序列f1，其任意子序列仍是頻繁的；同理，對于任意特征頻繁子串f2，其任意子串仍是頻繁子串。盡管使用特征選擇算法已經(jīng)挑選了對文本分類區(qū)分能力強的特征，可能已經(jīng)消除了一些冗余。對此，本文通過使用極大匹配來分析該部分冗余特征的作用：

極大匹配是指從文本轉化為向量表示時，只使用極大的特征，形式化如下：

句子s可用k個特征f1,f2,…,fk表示，則?i,j≤k,i≠j,fi不是fj的子串或子序列。

例如句子“八月份的優(yōu)惠是充三百送一百五的未贈送也未發(fā)短信，告知我什么時候送？”在文本匹配特征時，如果已經(jīng)匹配到一個特征“未贈送”，之后又匹配到一個子序列特征“充…送…未贈送”，則只匹配當前極大特征，即“充…送…未贈送”。即文本轉換為特征向量時，所有特征是極大的，它們之間沒有包含關系。

4 實 驗

4.1 實驗結果

本文以150000條短信作為實驗語料，其中每條短信都包含詞性標注信息和業(yè)務分類信息。人工選取10000條作為訓練語料，5000條作為封閉測試語料，其他為開放測試語料。本文使用了2種已有的開源算法：分詞算法使用中科院計算所的分詞軟件ICTCLAS；頻繁子序列挖掘算法使用由C.I. Ezeife等提出的基于WAP樹的序列挖掘算法。

本文使用了廣泛應用于文本分類的SVM分類器[18-19](C.-J. Lin開發(fā)的libsvm[20])。實驗步驟如下：

1)預處理：去除停用詞(例如“我”“和”“與”等)，將每條用戶文本分割為句子。

2)對于已標記文本，生成1-gram、2-gram、3-gram。

3)根據(jù)未標記文本及已標記文本進行分詞，之后計算頻繁子序列和頻繁子串，其中最小支持度閾值設為20/10000。

4)對于步驟2和步驟3得到的所有特征，計算IG，進行特征選擇。

5)將語句轉化為特征的向量表示：向量中的每一維對應一個特征，當語句具有一個特征時，向量對應的值為1，否則為0。

6)訓練SVM分類器。

上述實驗中，頻繁子序列和頻繁子串的支持度閾值可以通過十字交叉驗證來確定。本文在同一組訓練語料上進行了3組對比實驗：使用十折交叉驗證進行極大匹配和非極大匹配時的性能對比(表3)；僅使用子串特征與增加子序列特征后的性能對比(表4)；使用IG、MI、CHI這3種度量時分類器的性能對比(表5)。由于實驗中每個類別所占比例不同，實驗中各主題類別的召回率和總體準確率(召回率)。性能指標定義如下：

表3 十折交叉上2種匹配模式召回率和正確率/%

表4 子串特征及增加子序列特征后召回率和正確率/%

表5 3種度量開放測試召回率和正確率/%

4.2 結果分析

從表3可以看出，極大匹配和非極大匹配的性能幾乎相當，可見使用子序列特征所造成的部分冗余特征對分類器性能的影響可以忽略。表4顯示了僅使用子串特征和引入子序列特征后的性能情況，可以看出僅使用子串特征可以達到較高的性能，引入頻繁子序列后性能略有提高。文獻[8]中對文本分類中的各種度量特征的方法進行了對比，他們的實驗表明IG和CHI的性能最高。表5顯示了本文使用3種度量訓練的分類器的分類結果，可以看出三者性能差異較小，其中使用IG的性能略高。

從實驗結果可以看出，分類器整體的分類能力比較好，開通、取消類特征較明顯，所以召回率比較高。但介紹、使用類有相互混淆的特征，所以二者召回率相對較低。另外，IG值高的頻繁子序列或頻繁子串，表示它們在某一個類別中頻繁出現(xiàn)，同時可以發(fā)現(xiàn)其體現(xiàn)很強的語義，它可以進一步支持構造業(yè)務本體以及用戶問題的摘要提取，一些實例如表6所示。

表6 高IG的特征及蘊含的語義

4.3 討論

本文總結了一些分類錯誤的句子，難于分類的主要有如下幾類：

1)短文本：導致文本的“特征稀疏”，因而分類器很容易錯誤分類。例如：

①“開GPRS”(特征“開”，正確分類：開通，實驗結果：介紹)

②“查密碼”(特征“無”，正確分類：使用，實驗結果：其他)

2)對比：句子通過對比來陳述事實，但因特征不明顯，歸類錯誤。

例如下面2條咨詢正確分類為使用，實驗結果為其他：

①“剛才我撥打一個電話，講了55秒的時間，為何變成1.08分鐘？”

②“您好？我的手機扣了四十塊錢的月租，我三月份開通的新號碼，月租本來是十九塊錢嗎！”

3)其它原因，比如文本中包含錯別字、表述不清楚、缺乏標點符號等。

另外，還有一些可以進一步改進的問題，對不同子句中的特征建立一種條件或順序上的關聯(lián)模型，從而研究文本中幾個子句的關系，才能更準確地判斷分類，也可以更容易生成文本的摘要。

例如“本來有開通電腦飛信，今天用不了，說未開通此項業(yè)務，這種情況不是第一次”。關聯(lián)一些特征“用不了”“未開通”以及“不是第一次”才能判斷出其類別。

5 結束語

本文嘗試對短文本進行分類，使用了子序列和子串2種句法特征，并通過半監(jiān)督的思想進行頻繁子序列/子串的特征選擇，有效地利用了未標記文本的信息。同時，討論了頻繁子串/子序列帶來的特征冗余問題，實驗表明使用這些特征可以達到較好的分類效果。

然而，在短文本分類過程中，還有如下問題需要進一步研究：如何抽取更有效的句法特征[21-22]；對于不同類別數(shù)據(jù)的不平衡性，研究針對非平衡數(shù)據(jù)的分類問題；如何利用句子中評價語的依賴關系以及引入語義資源來提高分類的準確性。