徐 山 ，杜衛(wèi)鋒

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

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

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

1 理論基礎(chǔ)

1.1 類間相似度

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

C={c1，c2，…，cm}

D={d1，d2，…，dn}

類間相似度為[1]：

1.2 訓(xùn)練集和測試集的劃分

對于有監(jiān)督學(xué)習(xí)，將語料庫分為訓(xùn)練集和測試集。訓(xùn)練集用于算法的學(xué)習(xí)，測試集用于評估算法的有效性。

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

1.3 封閉測試和開放測試

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

1.4 TFIDF

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

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

(1)詞在文本中出現(xiàn)的次數(shù)越多，則該詞對文本內(nèi)容越具代表性，其權(quán)值越大；

(2)詞所出現(xiàn)的文本數(shù)越多，則該詞區(qū)分文本類別屬性的能力越低，其權(quán)值越小。

2 不可靠語料庫的提純

2.1 相似短信的刪除

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

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

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

2.2 降低誤分類短信的影響

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

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

則聚類Di與最初的分類Cj相對應(yīng)。

經(jīng)過實驗，得到類間相似度結(jié)果如表1所示。

表1 類間相似度

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

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

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

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

封閉測試下實驗所得的查準(zhǔn)率、查全率和微平均指標(biāo)如表2所示。

開放測試下實驗所得的查準(zhǔn)率、查全率和微平均指標(biāo)如表3所示。

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

表2 封閉測試準(zhǔn)確率對比

表3 開放測試準(zhǔn)確率對比

3 改進(jìn)的IDF

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

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

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

[4]還證明了該公式的性質(zhì)：(1)IDF是關(guān)于m的嚴(yán)格單調(diào)增函數(shù)；(2)IDF是關(guān)于k的嚴(yán)格單調(diào)減函數(shù)。

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

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

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

因為 m1〉m2〉0，k≥0，N〉0，所以 f(m1)-f(m2)〉0。改進(jìn)后的IDF仍是關(guān)于m的嚴(yán)格單調(diào)增函數(shù)。

則：

因為 k1〉k2≥0，m≥0，N〉0，所以 f(k1)-f(k2)〈0。 改進(jìn)后的IDF仍是關(guān)于k的嚴(yán)格單調(diào)減函數(shù)。

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

4 結(jié)果分析與評估

用基于KNN的分類方法進(jìn)行測試，得到了對IDF進(jìn)行改進(jìn)前后的數(shù)據(jù)，計算所得的查全率和查準(zhǔn)率指標(biāo)如表4所示。

表4 對IDF改進(jìn)前后準(zhǔn)確率對比

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

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

參考文獻(xiàn)

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

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

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

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