目標(biāo)字符串頻率變化對WCNB分類器精度的影響

崔超， 黃德海， 崔連和， 申利民

(1.齊齊哈爾大學(xué) 應(yīng)用技術(shù)學(xué)院，黑龍江，齊齊哈爾 161006；2.燕山大學(xué) 信息學(xué)院，河北，秦皇島 066004)

?

目標(biāo)字符串頻率變化對WCNB分類器精度的影響

崔超1， 黃德海1， 崔連和1， 申利民2

(1.齊齊哈爾大學(xué) 應(yīng)用技術(shù)學(xué)院，黑龍江，齊齊哈爾 161006；2.燕山大學(xué) 信息學(xué)院，河北，秦皇島 066004)

為解決MNB分類器在測試樣本變化時分類精度誤差較大的問題，采用權(quán)重標(biāo)準(zhǔn)補(bǔ)集分類器(WCNB)代替MNB分類器，并研究WCNB分類器對不同測試樣本分類精度的變化，針對WCNB技術(shù)存在目標(biāo)字符串變化所產(chǎn)生的權(quán)重計數(shù)問題，采用目標(biāo)字符串頻率轉(zhuǎn)換技術(shù)，建立一種有誤差補(bǔ)償功能的WCNB分類器數(shù)學(xué)模型并進(jìn)行了實驗仿真. 實驗仿真結(jié)果驗證了WCNB數(shù)學(xué)模型的可行性.

文本分類；數(shù)學(xué)模型；計算機(jī)仿真

采用貝頁斯多項式數(shù)學(xué)模型的文本分類器(MNB)在實際文本處理中運(yùn)行速度快、分類效率高，在中小型郵件服務(wù)器的垃圾郵件排查中應(yīng)用廣泛. 但當(dāng)測試樣本變化時MNB分類器分類篩選的誤差比較大，同用戶對文本文件處理的要求比較，MNB分類器即使在單標(biāo)記的文本集合中，對樣本文件進(jìn)行目標(biāo)字符串匹配檢索時也存在字符串分割和統(tǒng)計上的錯誤，影響最終的分類結(jié)果，更無法對多標(biāo)記的文本集合進(jìn)行分類篩選. 為解決文本分類精度不高的問題，分析分類質(zhì)量較低的原因，在數(shù)學(xué)處理上將分類器數(shù)學(xué)模型當(dāng)成線性對象處理，利用比MNB模型更成熟的WCNB技術(shù)[1]，采用權(quán)重標(biāo)準(zhǔn)補(bǔ)集技術(shù)的WCNB分類器，增加獨立變量，改進(jìn)了同一測試樣本的分類精度. 并以頗具代表性的單標(biāo)記文本Industry Set、20Newsgroups和多標(biāo)記文本(包括macro、micro兩種)為測試樣本，通過仿真試驗研究了方案的可行性.

1 MNB文本分類器

1.1 MNB文本分類器存在的問題

在郵件服務(wù)器對垃圾郵件的甄別工作中，由于貝頁斯多項式數(shù)學(xué)模型線性度高、工作原理簡單[2]，所以采用貝頁斯多項式數(shù)學(xué)模型的文本分類器(MNB)得到了廣泛應(yīng)用. 但由于測試文本標(biāo)記數(shù)量不等和大小不同、貝頁斯模型獨立變量在不同級別分類權(quán)重錯誤等原因，使貝頁斯模型產(chǎn)生權(quán)重向量偏移，導(dǎo)致MNB分類器文本分類精度下降. 在實際應(yīng)用中，貝頁斯模型權(quán)重向量有多個級別，級別越高權(quán)重向量越大，MNB系統(tǒng)運(yùn)行時更容易選擇有較大權(quán)重向量級別的分類.

在垃圾郵件分類研究領(lǐng)域，由于貝頁斯模型權(quán)重向量存在級別差異，針對一個分類級別的權(quán)重向量影響研究比較少. 實際上，對于不同分類級別，可以把分類權(quán)重向量差異視作在貝頁斯模型中引入獨立變量后，對樣本數(shù)據(jù)分類的建模操作. 這與符合貝頁斯模型獨立假定原則的分類級別相比，引入獨立變量的模型對于不符合獨立假定原則分類級別的影響更突出.

1.2 測試樣本分析

實驗中有A、B兩個測試樣本文件，實驗?zāi)康氖欠謩e研究“北京”和“哈爾濱”兩個詞在對應(yīng)樣本內(nèi)權(quán)重變化規(guī)律，建立相應(yīng)的數(shù)學(xué)模型. 利用貝頁斯模型研究兩詞權(quán)重的區(qū)別，假定名詞“北京”和“哈爾濱”在相應(yīng)文件內(nèi)出現(xiàn)幾率相同，“哈”和“爾濱”在第2個樣本中單獨出現(xiàn)概率忽略，則測試樣本出現(xiàn)1次“哈爾濱”，貝頁斯模型會對本級別分類權(quán)重自動計數(shù)2次，對“哈”和“爾濱”兩個對象所對應(yīng)權(quán)重分別加1. 由于“北京”和“哈爾濱”在與其所對應(yīng)分類級別的文件內(nèi)出現(xiàn)的次數(shù)相等，所以，“哈爾濱”出現(xiàn)1次，在權(quán)重累加上是“北京”的2倍，導(dǎo)致樣本B分類級別累加權(quán)重2倍于樣本A分類級別累加權(quán)重，結(jié)果使貝頁斯模型(MNB)對分類級別判斷出現(xiàn)錯誤. 如果在測試樣本文檔A中“北京”出現(xiàn)5次，在測試樣本文檔B中“哈爾濱”出現(xiàn)3次，基于上面錯誤計數(shù)方法，貝頁斯模型(MNB)對A、B樣本的分類級別累加權(quán)重分別為5和6，系統(tǒng)從而誤選中測試樣本文檔B.

實際分類中，貝頁斯模型(MNB)總會在兩個測試樣本文檔中選擇1個. 以標(biāo)準(zhǔn)的Reuters-21578文集為例，討論包含“furious”一詞的測試樣本文檔子集，測試中一種比較準(zhǔn)確的做法是，選擇一個經(jīng)驗閾值b，數(shù)學(xué)表示為

(1)

式中b+，b-為貝頁斯多項式數(shù)學(xué)模型中的門檻值[3]，相比用單個測試樣本文檔選定的閾值，前兩者要小得多，即準(zhǔn)確率更高.

(2)

式中：P函數(shù)為概率函數(shù)；θ為αi變化時的概率變量.

得到的準(zhǔn)確率要略低于b=-94.6時所對應(yīng)的分類精度，究其原因是貝頁斯模型(MNB)中引入的獨立變量比較偏重于包含“furious”目標(biāo)字符串的測試樣本文檔類，此時由MNB確定的“邊界定義權(quán)重”Wci采用的是常用對數(shù)形式，下標(biāo)c和i分別代表分類級別和相應(yīng)指數(shù)，在由測試數(shù)據(jù)組成的不同集合中，每一個集合都對應(yīng)一個有相應(yīng)數(shù)值范圍的對數(shù)變量θci，用以標(biāo)記相應(yīng)級別的測試樣本，數(shù)學(xué)表示如下，

(3)

2 引入WCNB分類技術(shù)解決權(quán)重向量標(biāo)準(zhǔn)化參數(shù)漂移問題

2.1 利用WCNB分類技術(shù)對多個數(shù)據(jù)集合分類測試

在系統(tǒng)權(quán)重向量在標(biāo)準(zhǔn)化過程中，存在著某一文件分類相對于其他文件分類有較高獨立性的問題，為解決這類問題對系統(tǒng)精度帶來的影響，需要對式(3)的“邊界定義權(quán)重”進(jìn)行優(yōu)化，對原來對數(shù)性質(zhì)的參數(shù)估算值進(jìn)行優(yōu)化，數(shù)學(xué)表示為

(4)

將式(4)稱為基于貝頁斯模型的權(quán)重標(biāo)準(zhǔn)補(bǔ)集(WCNB)模型，分別采用貝頁斯多項式數(shù)學(xué)模型分類器和WCNB分類器，表1為基于4個著名數(shù)據(jù)集合的分類計算結(jié)果[4-5]. 數(shù)據(jù)集合包括Industry sector、20 Newsgroup、Reuters(micro)和Reuters(macro)等，前2個集合是單標(biāo)記性質(zhì)的集合，即對每個集合中的測試樣本文檔只分配一個分類標(biāo)記(級別)，對于每個二進(jìn)制對象，采用標(biāo)準(zhǔn)“1對多冗余”的處理手段，在表中同單分類級別相對應(yīng)的兩組數(shù)據(jù)是采用MNB分類器和WCNB分類器的分類精度值；Reuters數(shù)據(jù)集是多分類標(biāo)記的數(shù)據(jù)集，每個文檔可以包含多個標(biāo)記，一個測試樣本文檔可分配多個分類級別，與前兩個數(shù)據(jù)集相比，對多標(biāo)記數(shù)據(jù)集的分類操作更復(fù)雜，采用標(biāo)準(zhǔn)“多對多冗余”的處理手段，每次計算生成大量數(shù)據(jù). 后兩個數(shù)據(jù)分別對應(yīng)Reuters數(shù)據(jù)集合在全局和局部精度重調(diào)臨界點的概率分布值，由表中數(shù)據(jù)可以看出，對于單/多標(biāo)記文集，MNB分類器分類精度總要低于WCNB分類器. 對于單標(biāo)記性質(zhì)數(shù)據(jù)集合，集中表現(xiàn)在WCNB比MNB有更高的準(zhǔn)確率；對于多標(biāo)記數(shù)據(jù)集，WCNB比MNB有更高的召回率，郵件接收者在客戶端的郵件統(tǒng)計也證明WCNB分類效果更好.

表1 基于4個典型數(shù)據(jù)集的MNB和WCNB的文本分類精度實驗數(shù)據(jù)對比

Tab.1 Text classification precision experiments by MNB and WCNB in 4 data sets

數(shù)據(jù)集文本分類精度MNBWCNBIndustrysector0589089220Newsgroup08510867Reuters(micro)08390882Reuters(macro)02900589

由表1可以看到，對MNB分類器的應(yīng)用可以進(jìn)一步優(yōu)化到基于貝頁斯模型的權(quán)重標(biāo)準(zhǔn)補(bǔ)集分類器(WCNB)的應(yīng)用，從兩種分類器對于4種不同數(shù)據(jù)集的分類精度可以看出，對目標(biāo)文本確定未標(biāo)記字符串，使用WCNB分類器取代MNB分類器，可以提高測試樣本文檔分類質(zhì)量.

2.2 WCNB分類器工作原理

為解決系統(tǒng)參數(shù)評估結(jié)果的精度受目標(biāo)字符串頻率變化影響的問題，WCNB分類器首先對系統(tǒng)輸入的字符串的出現(xiàn)頻率進(jìn)行調(diào)低處理. 在WCNB分類器中非目標(biāo)字符串對文檔分類級別影響很小，但字符串的隨機(jī)變化會造成一種兩者有關(guān)聯(lián)的偽表象，對系統(tǒng)參數(shù)評估帶來干擾，進(jìn)而影響目標(biāo)文檔分類權(quán)重. 由于眾多的非目標(biāo)字符串出現(xiàn)頻率高，即使它們對不同級別的權(quán)重差異比較小，也會對目標(biāo)文檔分類邊界的確定帶來干擾，為解決該問題，WCNB分類器首先利用下面的數(shù)學(xué)模型來降低字符串頻率變化所帶來的影響，

(5)

式中δij為一個邏輯變量，如果字符(串)i在文檔j中出現(xiàn)時，δij值為1、否則為0，其累加和是對所有目標(biāo)文檔相應(yīng)字符串邏輯變量計數(shù)結(jié)果的求和.

WCNB解決系統(tǒng)參數(shù)評估結(jié)果的精度受目標(biāo)字符串所在目標(biāo)文檔長度變化影響的問題，任何一個目標(biāo)文檔具有很強(qiáng)的字符串獨立性，一個特定的字符串如果在文檔A中某位置首次出現(xiàn)，則在該位置后的剩余篇幅出現(xiàn)的概率非常大，MNB分類器對這種現(xiàn)象會產(chǎn)生很大的誤差. 為解決問題，WCNB分類器對字符串計數(shù)進(jìn)行規(guī)范化處理來提高分類精度. 與普通信息檢索轉(zhuǎn)換相似，WCNB通過對特定目標(biāo)字符串的頻率轉(zhuǎn)換為每個文檔生成一個長度為1的目標(biāo)字符串頻率向量，以降低文檔長度不同的影響，數(shù)學(xué)模型為

(6)

式中：k為文檔數(shù)量；i為目標(biāo)字符串. 這種轉(zhuǎn)換在普通信息檢索中是常用的，因為對在一個數(shù)學(xué)模型內(nèi)生成多個文檔的概率要進(jìn)行跨文檔比較操作，如要避免小文檔字符串?dāng)?shù)量少的干擾，上面分類過程則只需跨級別而不跨文檔[6].

上述兩方面轉(zhuǎn)換使WCNB分類器在系統(tǒng)參數(shù)評估中降低了任一個文檔有過高的權(quán)重.

通過對采用貝頁斯模型權(quán)重標(biāo)準(zhǔn)補(bǔ)集分類器(WCNB)和貝頁斯多項式數(shù)學(xué)模型分類器(MNB)所得到的分類結(jié)果數(shù)據(jù)的比較，可以看出WCNB的改進(jìn)效果還是比較明顯的，對Reuters和Industry sector兩類樣本文件集的分類結(jié)果進(jìn)行分析，在不同數(shù)據(jù)集內(nèi)測試數(shù)據(jù)數(shù)量發(fā)生變化的情況下，WCNB的性能改進(jìn)是顯著的. 表中Reuters(macro)局部精度重調(diào)臨界點概率值(召回率)有成倍的提高，利用WCNB可以實現(xiàn)只用較少的測試樣本，全面優(yōu)化多分類標(biāo)記數(shù)據(jù)集多級別分類質(zhì)量的目標(biāo). 對于20Newsgroup數(shù)據(jù)集，WCNB還顯示出具備對跨數(shù)據(jù)集測試樣本處理的能力，這點對建立跨數(shù)據(jù)集合的分類模型意義重大. 借助于交叉驗證手段，當(dāng)對貝頁斯多項式分類器進(jìn)行平滑參數(shù)優(yōu)化時[4]，所得到的結(jié)果是相似的，這一結(jié)論又提高了WCNB的性能. 實驗證明，使用MNB時，不同的特征變量選擇、分值評判機(jī)制及預(yù)處理系統(tǒng)，都會對分類計算結(jié)果精度有影響.

3 利用樣本字符串頻率轉(zhuǎn)換優(yōu)化文本建模

根據(jù)前述使用貝頁斯分類器在文本分類時所帶來的誤差問題，基于貝頁斯分類器的多項式數(shù)學(xué)模型對目標(biāo)文本建模，系統(tǒng)偏差量較大，效果不佳，采用WCNB過濾技術(shù)使誤差問題得到緩解. 為進(jìn)一步提高測試樣本準(zhǔn)確率，提出優(yōu)化目標(biāo)字符串頻率參數(shù)的解決方案，分析不同目標(biāo)字符串頻率分布的多個作業(yè)，在與權(quán)重標(biāo)準(zhǔn)補(bǔ)集分類器(WCNB)測試值相比后，調(diào)整目標(biāo)字符串頻率參數(shù)，由轉(zhuǎn)換頻率分布曲線顯示的解決方案有更高數(shù)量級的概率，經(jīng)過這種轉(zhuǎn)換，使目標(biāo)數(shù)據(jù)更好地匹配于權(quán)重標(biāo)準(zhǔn)補(bǔ)集分類器(WCNB)，系統(tǒng)分類性能比沒有執(zhí)行調(diào)整目標(biāo)字符串頻率參數(shù)解決方案的MNB顯著提高.

3.1 目標(biāo)字符串頻率轉(zhuǎn)換

為測試權(quán)重標(biāo)準(zhǔn)補(bǔ)集分類器(WCNB)能否按設(shè)計要求完成文本分類，參考測試文本目標(biāo)字符串頻率分布的缺省值，發(fā)現(xiàn)目標(biāo)字符串頻率的轉(zhuǎn)換能呈現(xiàn)出比MNB分類器更高數(shù)量級的概率曲線，代替已有的冪率形狀的分布曲線. 經(jīng)過簡單變換，可以使多條冪率形狀分布曲線的多項性更強(qiáng). 為測量多項式的模型曲線同測試文本目標(biāo)字符串(頻率)分布曲線的吻合度，將目標(biāo)字符串頻率分布的缺省值與擬采用的多項式分布最大可能值相比較.

為使測試方案更具有操作性，采用一個由多個詞語所組成的集合A，集合中每個詞語有大致相同出現(xiàn)概率，并以一組有相似長度的文檔所組成的集合B為作用域，在集合B中創(chuàng)建集合A詞語的目標(biāo)字符串頻率，設(shè)定上述目標(biāo)字符串頻率和由最佳匹配的多項式模型(WCNB)所預(yù)示的頻率用橫軸表示、并設(shè)定長度1為記錄單位，如圖1所示.

由圖1可以發(fā)現(xiàn)，目標(biāo)字符串頻率分布的缺省值同權(quán)重標(biāo)準(zhǔn)補(bǔ)集分類器可能提供的預(yù)期值不同，前者的缺省值有更高數(shù)量級的概率，表示目標(biāo)詞語在當(dāng)前多項式中發(fā)生的概率要遠(yuǎn)大于由最佳匹配的多項式模型所預(yù)示的概率. 例如，在一個文檔中檢測到一個指定詞語平均出現(xiàn)q次，概率的數(shù)學(xué)表達(dá)式為

(7)

可見該事件發(fā)生的概率非常小，但當(dāng)目標(biāo)文檔數(shù)量級增加到4時，事件發(fā)生概率在現(xiàn)實中就成為實際，將這類行為發(fā)生在概率上的差異稱為突發(fā)性，概率的數(shù)學(xué)表達(dá)式為

(8)

測試證明，即使目標(biāo)字符串頻率分布曲線有更高數(shù)量級的概率，目標(biāo)字符串頻率冪律[6]分布也能很好地實現(xiàn)目標(biāo)文本建模，完成WCNB模型特征向量建立.

3.2 測試數(shù)據(jù)曲線的驗證

(9)

4 結(jié) 論

由于目標(biāo)字符串頻率分布的經(jīng)驗值曲線同貝頁斯多項式分類器概率曲線相似，為使WCNB測試系統(tǒng)的實際分布概率更加緊密地趨近測試文本的概率分布. 首先,合理選擇參數(shù)d值以滿足WCNB數(shù)學(xué)表達(dá)式，使目標(biāo)字符串頻率分布經(jīng)驗值曲線緊貼冪率分布曲線，確保經(jīng)驗值曲線的概率同同冪律分布對應(yīng)級別成比例的發(fā)生變化，其次，在系統(tǒng)工作時，調(diào)整當(dāng)d>1時對目標(biāo)字符串計數(shù)的統(tǒng)計，雖然當(dāng)d=1時的數(shù)據(jù)不如d值取最優(yōu)時的數(shù)據(jù)，但與MNB分布曲線相比，不論對于單標(biāo)記性質(zhì)數(shù)據(jù)和多標(biāo)記數(shù)據(jù)集集合，WCNB比MNB有更高的準(zhǔn)確率，利用WCNB優(yōu)點的基礎(chǔ)上對文本做現(xiàn)實可行的處理. 實驗證明同MNB相比，WCNB分類效果更好.

[1] Kush E N. Learning to remove internet advertisements[C]∥Proceedings of the 3rd International Conference on Autonomous Agents Seattle. Washington D.C.: [s.n.]，1999:175-181.

[2] Hall R J. How to avoid unwanted e-mail[J]. Communication of ACM， 1998，41(3):88-95.

[3] Cohen W W. Learning rule that classify E-mail[C]∥Proceedings of the AAAI Spring Symposium on Machine Learning in Information Access.Stanford， California: [s.n.]，1996：78-84.

[4] 崔超，吳雙，張憲忠，等.基于貝葉斯概率理論的防火墻技術(shù)研究[J].北京理工大學(xué)學(xué)報，2012，32(8):801-804.

Cui Chao， Wu Shuang， Zhang Xianzhong， et al. Firewall technology based on Bayesian probability theory[J]. Transactions of Beijing Institute of Technology， 2012，32(8):801-804.(in Chinese)

[5] 崔超，張憲忠，吳雙.測試樣本空間變化對貝頁斯常規(guī)及補(bǔ)集規(guī)則權(quán)重評估影響的分析[J].北京理工大學(xué)學(xué)報，2014，34(10)：1040-1043.

Cui Chao, Zhang Xianzhong, Wu Shuang. Impact of the change of training sample space on Bayesian regular and complement class rules weight estimate[J]. Transactions of Beijing Institute of Technology, 2014,34(10):1040-1043. (in Chinese)

[6] 崔超，楊威，張憲忠，等.貝葉斯網(wǎng)絡(luò)在垃圾郵件算法中的應(yīng)用研究[J].哈爾濱工業(yè)大學(xué)學(xué)報，2011，43(11):145-148.

Cui Chao， Yang Wei， Zhang Xianzhong， et al. Bayesian application study on arithmetic for filtering junk e-mail[J]. Journal of Harbin Institute of Technology， 2011，43(11):145-148.(in Chinese)

(責(zé)任編輯：劉雨)

Effect of String Frequency Changing on the Accuracy of WCNB Classifier

CUI Chao1， HUANG De-hai1， CUI Lian-he1， SHEN Li-min2

(1.School of Applied Science and Technology， Qiqihar University， Qiqihar， Heilongjiang 161006，China;2.School of Information， Yanshan University, Qinhuangdao， Hebei 066004， China)

In order to solve the problems of classification accuracy that produced in text variety testing with MNB classifier， a WCNB classifier was presented to replace MNB classifier. The classification precision changes of the WCNB classifier were studied for different test samples. Due to the weight counting mistakes arisen from target strings changing in the WCNB classification， a target strings frequency conversion technology was adopted to develop a WCNB classifier mathematic model with error compensation function. The simulation result verifies the feasibility of the WCNB mathematic model.

text classification; mathematical model; computer simulation

2015-10-28

國家自然科學(xué)基金資助項目(61272125)

崔超(1961—)，男，教授，博士生導(dǎo)師，E-mail:cv63@163.com.

TP 393

A

1001-0645(2016)04-0382-05

10.15918/j.tbit1001-0645.2016.04.009