不可靠語料庫的提純及詞權度量指標IDF的改進*

徐 山 ，杜衛鋒

(1.南京城市職業學院 教務處，江蘇 南京210038；2.嘉興學院 數理與信息工程學院，浙江 嘉興314001)

隨著我國移動通信業務的發展，短信業務因價格便宜、方便快捷，贏得了廣大用戶的青睞，短信開始被人們稱為繼報紙、廣播、電視、互聯網之后的“第五媒體”。然而伴隨“拇指經濟”爆發性增長的同時，無孔不入的不良短信騷擾讓人不堪忍受。不良短信的泛濫，不僅影響我國的正常通信秩序，而且毒化社會風氣，不利于社會發展進步。

扼制不良短信的傳播，既需要監管部門制定相應的法律法規，也需要采取一定的技術對不良短信進行識別和過濾。本文研究了文本分類中的兩個問題，可應用于不良短信過濾，分別是不可靠語料集的提純和關于TFIDF詞權度量指標的一點改進。

1 理論基礎

1.1 類間相似度

設兩類為 C、D，分別有 m、n個樣本，即：

C={c1，c2，…，cm}

D={d1，d2，…，dn}

類間相似度為[1]：

1.2 訓練集和測試集的劃分

對于有監督學習，將語料庫分為訓練集和測試集。訓練集用于算法的學習，測試集用于評估算法的有效性。

對于訓練集和測試集的劃分，目前主要有兩種方法[2]：保持（Holdout）方法和 k折交叉驗證（K-fold Cross Validation）方法。保持方法將已知數據隨機劃分為訓練數據和測試數據兩部分，一般訓練數據占2/3，測試數據占1/3。使用訓練數據導出分類模型，它在測試數據上的分類精度作為最終的分類精度。k折交叉驗證則將已知數據隨機劃分為 k個大致相等的數據子集 S1、S2、…、Sk，訓練和測試重復進行k次。在第i次過程中，Si作為測試數據，其余的子集則作為訓練數據。最終分類器的分類精度取k次測試分類精度的平均值。這種方法適用于原始數據量較小的情況，這時不適合直接應用保持方法。

1.3 封閉測試和開放測試

用分類器對測試集進行分類，得到測試集的分類結果，從而可以對測試集的性能做出評價。測試有封閉測試和開放測試之分。封閉測試時，測試集是訓練集的一部分，或者就是訓練集本身；開放測試時，測試集是與訓練集獨立同分布的兩個數據集[3]。一般來說，封閉測試的結果意義不大，分類中主要應用開放測試。

1.4 TFIDF

度量詞權的加權體系中用某一權重值取代表示該詞是否出現的布爾表示，通常具有更高的準確性。為了處理同樣是高頻詞的專業詞和通用詞，挖掘領域一般采用詞頻反轉文檔頻率TFIDF(Term Frequency Inverse Document Frequency)這一指標衡量某個詞的權重，公式如下：

其中TF表示詞條在文本中的權重，N表示訓練集總文本數，n表示包含詞條的文本數。對式(3)，有如下直觀的解釋：

(1)詞在文本中出現的次數越多，則該詞對文本內容越具代表性，其權值越大；

(2)詞所出現的文本數越多，則該詞區分文本類別屬性的能力越低，其權值越小。

2 不可靠語料庫的提純

2.1 相似短信的刪除

從網上搜集的語料來自不同的網站，其中有大量短信是相同或相似的，這些相似短信并不會給分類器增加信息，反而會干擾分類器的學習，增加分類器的空間和時間復雜度。本文提出了一種刪除相似短信的方法。

如果采用文件比較的方法，只能比對出完全相同的短信。而通過對語料庫的分析，發現其中有很多短信只是在措辭方面略有不同，而表述的內容幾乎一致。

采用向量空間模型將短信向量化，應用式(2)給出的夾角余弦計算兩個向量之間的相似度，設定某個閾值，如果相似度超過該閾值，則刪除其中一個向量對應的短信。通過實驗，發現閾值設置為0.95比較合適，可以基本刪除相似短信，而不會造成誤刪。經過該步驟，總共刪除了330條相似短信。

2.2 降低誤分類短信的影響

另一種情況是短信分類錯誤。例如，有些短信明明是正常短信，卻被錯誤地劃分到了黃色短信的類中。但是，要對語料庫中的所有短信逐一閱讀，人工確定其類別，又是一項耗時耗力的工作。

如何對不純的語料庫進行提純，本文提出了一種方法。假設最初語料庫分為 n類 C1、C2、…、Cn，應用聚類方法，將語料庫聚合為n類。但是，聚類方法產生的類并沒有類別標簽，為找到聚類產生的類與原先分類之間的對應關系，假設聚類產生的類為 D1、D2、…、Dn，應用類間相似度確定聚類Di與最初的哪個分類相對應，如式(4)所示：

則聚類Di與最初的分類Cj相對應。

經過實驗，得到類間相似度結果如表1所示。

表1 類間相似度

其中，C1、C2、C3分別代表正常短信、黃色短信、反動短信。由表 1可以得出，聚類D1、D2、D3分別對應原先的分類 C1、C2、C3。因此，實際上對語料庫進行了兩次劃分，分別是：π1={C1，C2，C3}，π2={D1，D2，D3}。 如圖 1 所示。 其中，細線表示劃分π1，粗線表示劃分π2。

圖1 網站粗分類、聚類對語料庫的兩次劃分及其交集

本文提純方法如下，如果某條短信在原先分類中被歸為一類，在聚類中還歸為該類，則保留該文檔，否則棄用。如圖1所示，灰色區域對應的就是語料庫中保留的部分，它們是分類和相應的聚類的交集 Ci∩Di(i=1，2，3)。

為驗證此提純方法的效果，對提純前后的語料庫分別進行了封閉測試和開放測試。由于提純后語料庫中只剩下不足2 000條短信，數據量較少，所以在測試時應用了10折交叉驗證。

封閉測試下實驗所得的查準率、查全率和微平均指標如表2所示。

開放測試下實驗所得的查準率、查全率和微平均指標如表3所示。

由表2、表3可見，本文方法對不可靠數據的提純效果還是比較明顯的。

表2 封閉測試準確率對比

表3 開放測試準確率對比

3 改進的IDF

IDF的主要思想是：如果包含某詞條的文本越多，即n越大，IDF越小，則說明該詞條的類別區分能力越低。如果某一類C中包含該詞條的文本數為m，而其他類包含該詞條的文本總數為k，顯然所有包含該詞條的文本數 n=m+k，當 m大時，n也大，由式(3)得到的 IDF的值會小，說明該詞條類別區分能力不強。但實際上，如果一個詞條在一個類的文本中頻繁出現，則說明該詞條能夠很好地代表這個類的文本特征，這樣的詞條應該賦予較高的權重，并選來作為該類文本的特征詞以區別于其他類文檔。這就是IDF的不足之處。

針對 IDF的不足，參考文獻[4]提出了改進意見，設總文本數為N，包含某詞條的文本數為n，其中某一類C中包含該詞條的文本數為m，則該詞條在C類中的IDF表示如下：

如果除C類外，包含該詞條的文本數為k，則式(5)可變形為：

[4]還證明了該公式的性質：(1)IDF是關于m的嚴格單調增函數；(2)IDF是關于k的嚴格單調減函數。

上述性質實際上表達了如下含義，如果在某一類中包含某詞條的文本數量大，而在其他類中包含該詞條的文本數量小，則該詞條能夠代表C類的文本特征，具有很好的類別區分能力。

但是在某些情況下，某詞條只在一個類中出現，即k=0，則：

則不管在該類中包含該詞條的文本數m為多少，值均為lgN，這與事實相違背，應該是該類中包含的文本數m越大，該值就越重要。因此本文對參考文獻[4]的公式作了如下改進：

因為 m1〉m2〉0，k≥0，N〉0，所以 f(m1)-f(m2)〉0。改進后的IDF仍是關于m的嚴格單調增函數。

則：

因為 k1〉k2≥0，m≥0，N〉0，所以 f(k1)-f(k2)〈0。 改進后的IDF仍是關于k的嚴格單調減函數。

因此改進后的IDF仍能保持原來的兩條性質，則該詞條能夠代表C類的文本特征，具有很好的類別區分能力。

4 結果分析與評估

用基于KNN的分類方法進行測試，得到了對IDF進行改進前后的數據，計算所得的查全率和查準率指標如表4所示。

表4 對IDF改進前后準確率對比

從表4可以看出，對IDF進行改進后，在查準率、查全率和微平均等指標上有了微小的提高。經過分析，在特征詞限定為1 000個時，滿足上面條件k=0的特征詞只有8個，占所有特征詞的比例很小，因此效果不是太顯著。

鑒于不良短信的泛濫和造成的重大危害，本文探討了能應用于不良短信識別和過濾的文本分類中的兩個技術問題。結合聚類分析方法，實現了對不可靠語料庫的提純，實驗結果表明該方法是相當有效的。另外，對信息檢索領域應用十分廣泛的詞權度量指標TFIDF的IDF提出了一點合理的改進，如果僅在一類中出現的特征詞的比例稍大，該改進將會有一定的效果。

參考文獻

[1]李弼程，邵美珍，黃潔.模式識別原理與應用[M].西安：西安電子科技大學出版社，2008.

[2]HAN J，KAMBER M.Data Mining：Concepts and Techniques[M].北京：高等教育出版社，2001.

[3]李家兵.交叉覆蓋算法下文本分類的研究[D].合肥：安徽大學，2007.

[4]張玉芳，彭時名，呂佳.基于文本分類 TFIDF方法的改進與應用[J].計算機工程，2006，32(19)：76-78.