徐征，劉遵雄，張賢龍

（華東交通大學(xué)1.電氣與電子工程學(xué)院；2.信息工程學(xué)院，江西南昌330013）

基于套索（Lasso）的中文垃圾郵件過濾

徐征1，劉遵雄2，張賢龍2

（華東交通大學(xué)1.電氣與電子工程學(xué)院；2.信息工程學(xué)院，江西南昌330013）

使用向量空間模型表示的文本郵件數(shù)據(jù)高維而稀疏，不利于郵件過濾分類模型的建立，通常需在分類器訓(xùn)練前進(jìn)行維數(shù)約減。Lasso回歸是一種基于l1正則化的多元線性模型，其在模型參數(shù)估計(jì)的同時(shí)實(shí)現(xiàn)了變量選擇。提出使用Lasso回歸進(jìn)行垃圾郵件過濾，建立Lasso回歸郵件分類模型、Lasso回歸詞條選擇結(jié)合邏輯回歸的分類模型，結(jié)合中文文本垃圾郵件數(shù)據(jù)集TREC06C進(jìn)行垃圾郵件過濾實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明Lasso回歸詞條選擇結(jié)合邏輯回歸的郵件分類模型性能更佳。

中文文本郵件；垃圾郵件；過濾；Lasso；邏輯回歸

基于內(nèi)容的垃圾郵件過濾技術(shù)逐步成為垃圾郵件過濾研究重點(diǎn)［1-2］，研究方法多為模式識(shí)別、數(shù)據(jù)挖掘等領(lǐng)域的分類或回歸技術(shù)，常用的模型算法有決策樹、支持向量機(jī)［3］、貝葉斯分類和邏輯回歸（Logistic Re?gression）［4-5］等。建立垃圾郵件過濾模型首先需要獲得一定數(shù)目的正常郵件和垃圾郵件，使用向量空間模型（vector spacemodel，VSM）表示的郵件數(shù)據(jù)特征維度高而且稀疏，基于這些數(shù)據(jù)建立分類模型時(shí)計(jì)算量龐大，分類器模型容易陷于“過學(xué)習(xí)”，其泛化能力不好。解決該問題通常的辦法是先于分類器訓(xùn)練進(jìn)行特征維數(shù)約減，以提高算法運(yùn)算效率、改善分類性能。

特征選擇是常用的維數(shù)約減方法，其采用一些統(tǒng)計(jì)和信息論方法，如文檔頻率、χ2統(tǒng)計(jì)和信息增益等［6］，選擇出對分類貢獻(xiàn)最大的特征子集。最小絕對縮減和變量選擇算子（least absolute shrinkage and selection operator，Lasso）回歸是一種回歸系數(shù)絕對值和受限制的多元線性回歸方法，也稱為“套索”回歸，其可以同時(shí)實(shí)現(xiàn)模型參數(shù)估計(jì)和變量選擇［7-9］。Lasso回歸研究發(fā)展很快，相應(yīng)的改進(jìn)模型（彈性網(wǎng)、組套索等）和算法相繼被提出，而最小角度回歸（least angle regression，LAR）算法能很好解決Lasso回歸的計(jì)算問題［10］。

提出基于套索的垃圾郵件過濾算法，使用Lasso回歸選擇特征詞條，建立邏輯回歸分類模型。結(jié)合中文垃圾郵件的數(shù)據(jù)集TREC（Text retrieval conference）［11］進(jìn)行垃圾郵件過濾模擬實(shí)驗(yàn)，并對求得的郵件過濾性能評價(jià)指標(biāo)值給以分析說明。

1 基于VSM（向量空間模型）的郵件表示

研究文本郵件數(shù)據(jù)，垃圾郵件過濾等效于二元文本分類問題。進(jìn)行垃圾郵件過濾，首先需使用向量空間模型VSM將郵件數(shù)據(jù)表示成易于計(jì)算機(jī)處理的形式，即使用中文分詞對郵件進(jìn)行預(yù)處理（得到郵件正文和主題的詞條），選擇一定詞條特征進(jìn)行統(tǒng)計(jì)分析，將每封郵件表示為一長度等于詞條數(shù)的向量。從而郵件數(shù)據(jù)集表示成詞條文檔矩陣Xn×m=(x1,x2,...,xm)和郵件目標(biāo)向量yn×1，其中m為詞條數(shù)，n為文檔數(shù)，y的分量取-1或1表示對應(yīng)郵件的類別（正常或垃圾郵件）。

X每行成分值為對應(yīng)詞條關(guān)于不同郵件的權(quán)值，表示詞條在郵件中的重要程度。常用的幾種權(quán)值計(jì)算方法為布爾權(quán)重，詞頻權(quán)重，tf-idf權(quán)重、tfc權(quán)重、ltc權(quán)重。在本文中選用ltc權(quán)重，使用詞頻的對數(shù)，減少詞頻差異帶來的干擾。ltc權(quán)重的計(jì)算公式如下

其中：xki表示詞條i在文檔k中的權(quán)重；fki表示詞條i在文檔k中的詞頻數(shù)；n是郵件中文檔的總數(shù)；ni表示詞條i的文檔頻數(shù)。

2 Lasso回歸及LAR算法

提出使用Lasso回歸進(jìn)行詞條特征選擇。Lasso回歸是一種回歸系數(shù)受限制的最小二乘（即懲罰最小二乘）問題，能較好地處理模型學(xué)習(xí)中的“過學(xué)習(xí)”問題，在進(jìn)行模型參數(shù)估計(jì)的同時(shí)實(shí)現(xiàn)變量選擇。Lasso回歸優(yōu)化問題為

其拉格朗日表達(dá)式為

其中：λ為懲罰參數(shù)，λ與s存在某種對應(yīng)關(guān)系。Lasso回歸求解算法很多，有射擊算法（shooting algo?rithm）、同倫（homotopy）算法和最小角度回歸（least angle regression，LAR）算法。LAR算法是對傳統(tǒng)的stagewise forward selection［8］方法加以改進(jìn)而得到的有效精確方法，并且在計(jì)算上也比stagewise方法簡單，它最多只需要通過m步（m為變量個(gè)數(shù)），就能得到擬合解。LAR與最小二乘計(jì)算復(fù)雜度相當(dāng)，能很好的解決Lasso回歸的計(jì)算問題。LAR算法如下：

首先需要對數(shù)據(jù)進(jìn)行預(yù)處理，使其去均值和標(biāo)準(zhǔn)化。

定義β?=(β1,β2...,βm)T為當(dāng)前擬合向量μ的系數(shù)

則xi跟殘差y-μ的相關(guān)系數(shù)為

逐步計(jì)算擬合值μ：剛開始時(shí)，相關(guān)系數(shù)都為0，然后找出跟殘差（此時(shí)為y）相關(guān)系數(shù)最大的變量，假設(shè)是xj1，將其加入到活動(dòng)集，這時(shí)在xj1的方向上找到一個(gè)最長的步長r?1，直到出現(xiàn)下一個(gè)變量（假設(shè)是xj2）跟殘差的相關(guān)系數(shù)跟xj1與殘差的相關(guān)系數(shù)相等，此時(shí)把xj2加入活動(dòng)集里，LAR繼續(xù)在這2個(gè)變量等角度的方向進(jìn)行擬合，找到第3個(gè)變量xj3使得該變量、活動(dòng)集中變量跟殘差的相關(guān)系數(shù)相等，隨后LAR繼續(xù)找尋下一個(gè)變量，直至使殘差減小到一定范圍內(nèi)。

LAR求解Lasso算法的步驟如下：

其中：u為當(dāng)前最小角度方向，即角平分線方向；μ為當(dāng)前擬合的y值；c為殘差與變量的相關(guān)系數(shù)；r?,r?為當(dāng)前的最長步長；A為變量集合；XA為搜索矩陣；WA，aA，GA為中間變量。

使用LAR算法，求出Lasso回歸的解向量β，而對應(yīng)β系數(shù)不為0的變量，即為選出的關(guān)鍵詞條。然后基于這些詞條建立邏輯回歸分類模型。

圖1 LAR選擇示意圖Fig.1 The schematic diagram of LAR selection

3 實(shí)驗(yàn)和結(jié)果分析

3.1 數(shù)據(jù)準(zhǔn)備及評價(jià)標(biāo)準(zhǔn)

本文使用的中文垃圾郵件數(shù)據(jù)集TREC06c是TREC（text retrieval conference）2006年給出的中文垃圾郵件評測公共數(shù)據(jù)，數(shù)據(jù)及選擇概況見表1。

表1 中文垃圾郵件數(shù)據(jù)集Tab.1 Dataset of Chinese spam封

選取3萬封原始郵件進(jìn)行預(yù)處理，從郵件數(shù)據(jù)中提取出郵件的內(nèi)容，并用VSM模型將郵件數(shù)據(jù)表示成文檔詞條矩陣。預(yù)處理過程用C++語言實(shí)現(xiàn)，提取郵件主題、正文等重要信息，包括郵件內(nèi)容的解碼、中文的文本分詞、構(gòu)建郵件內(nèi)容詞語的詞庫和ltc權(quán)重計(jì)算等步驟?？紤]到郵件主題可能包含更多郵件信息，將出現(xiàn)在郵件主題中的詞條權(quán)重進(jìn)行加倍。

使用中科院的分詞組件ICTCLAS進(jìn)行中文分詞，對分詞后的郵件數(shù)據(jù)進(jìn)行統(tǒng)計(jì)得到49 452個(gè)詞條，考慮到郵件中許多詞條的出現(xiàn)頻數(shù)很少，去除文檔頻率小于0.2%的詞條，以及空格、特殊的標(biāo)點(diǎn)符號等干擾字符，最終得到8 879個(gè)詞條。實(shí)驗(yàn)中發(fā)現(xiàn)，有一些郵件數(shù)據(jù)沒有正文，從而生成全0數(shù)據(jù)，刪除這樣的數(shù)據(jù)。考慮到在實(shí)際生活中，垃圾郵件的數(shù)目往往比正常郵件數(shù)據(jù)多，實(shí)驗(yàn)中以垃圾郵件跟正常郵件2∶1的比例隨機(jī)抽取了5 000封垃圾郵件，2 500封正常郵件構(gòu)成訓(xùn)練樣本，在其余數(shù)據(jù)中隨機(jī)抽取4 000封垃圾郵件，2 000封正常郵件作為測試數(shù)據(jù)。建立Lasso回歸郵件分類模型（簡稱“Lasso方法”），再者基于Lasso回歸選取的特征詞條建立邏輯回歸分類模型（簡稱“邏輯回歸方法”）進(jìn)行垃圾郵件過濾實(shí)驗(yàn)，使用如下指標(biāo)進(jìn)行性能評價(jià)：

lHm%表示正常郵件的誤判率；lsm%表示垃圾郵件的誤判率；l1-ROCA%［10］：ROC曲線上方的部分，曲線下面部分的面積反映了分類器閾值在取得；所有可能值上，分類器效率（effectiveness）的一個(gè)累計(jì)度量，從而避免用單一的hm%；或sm%進(jìn)行衡量的局限性。1-ROCA%是眾多指標(biāo)中最重要的一項(xiàng)；llam%：平均誤分率對數(shù)。定義如下

其中：

lhm：1為當(dāng)hm%=0.1時(shí)，對應(yīng)的sm%的值。因?yàn)樵趯?shí)際中，將一封正常郵件錯(cuò)分為垃圾郵件的代價(jià)系數(shù)要比將一封垃圾錯(cuò)分為正常郵件的代價(jià)系數(shù)高的多。

3.2 實(shí)驗(yàn)及結(jié)果分析

使用獲得的數(shù)據(jù)進(jìn)行垃圾郵件過濾實(shí)驗(yàn)，訓(xùn)練樣本是一個(gè)維度為7 500×8 879的文檔詞條矩陣和對應(yīng)樣本的類別目標(biāo)值向量。首先進(jìn)行Lasso回歸模型訓(xùn)練，使用LAR算法求解Lasso問題的解β，其中對應(yīng)系數(shù)不為0的詞條就是選中的詞條。式（3）中的λ控制著回歸系數(shù)l1范數(shù)的懲罰，使用不同的λ值進(jìn)行垃圾郵件過濾實(shí)驗(yàn)，λ的值分別取12、10、8和7，分別求解得出不同數(shù)目的詞條，分別為467、672、1 106和1 481。實(shí)驗(yàn)中將使用不同λ值訓(xùn)練獲得的Lasso回歸模型，并將其用于6 000封測試郵件的分類，計(jì)算相應(yīng)評價(jià)指標(biāo)值見表2，對應(yīng)的ROC曲線見圖2。根據(jù)表2，隨著詞條特征維度的增加，郵件過濾的各項(xiàng)指標(biāo)大體上有所提高，但是正常郵件誤判率（hm%）有所增大。

圖2 邏輯回歸分類ROC曲線圖Fig.2 ROC curve of ogistic regression and classification

圖3 Lasso分類ROC曲線圖Fig.3 ROC curve of Lasso Classification

表2 用Lasso回歸實(shí)驗(yàn)結(jié)果Tab.2 Experimental results of the Lasso regression

表3 Lasso詞條選擇結(jié)合邏輯回歸的實(shí)驗(yàn)結(jié)果Tab.3 The experimental results with the logistic regression and Lasso lexical selection

基于Lasso回歸實(shí)驗(yàn)選出的詞條，建立相應(yīng)的邏輯回歸分類模型，并進(jìn)行測試，相應(yīng)評價(jià)指標(biāo)值見表3。對比表2和表3，可以看出，在性能方面等方面，使用邏輯回歸的1-ROCA%確實(shí)明顯優(yōu)于Lasso回歸，而且Lasso過濾器的誤判率也高于邏輯回歸，但是邏輯回歸方法的時(shí)耗要比直接使用Lasso做分類判別的時(shí)耗高，因?yàn)榍罢弑群笳叨喑隽诉壿嫽貧w模型建立的時(shí)間。所以在時(shí)間效率上，邏輯回歸不如Lasso過濾算法。

圖4 過濾器的ROC學(xué)習(xí)曲線Fig.4 ROC learning curve of Filter

圖4是兩種方法的ROC學(xué)習(xí)曲線，可看出，當(dāng)訓(xùn)練樣本數(shù)目很少的情況下，Lasso的效果比較好，隨著訓(xùn)練樣本數(shù)目的增加，雖然兩種過濾算法對于垃圾郵件的預(yù)測性能都有所提高，但是，當(dāng)訓(xùn)練樣本達(dá)到一定數(shù)目時(shí)，使用Lasso過濾算法的1-ROCA%值基本趨于穩(wěn)定了，而邏輯回歸方法的性能有比較顯著的提升。當(dāng)訓(xùn)練樣本足夠多的時(shí)候，選用邏輯回歸分類器的效果會(huì)更好。

4 結(jié)論

Lasso回歸是一種基于回歸系數(shù)l1正則化的統(tǒng)計(jì)建模技術(shù)，已被廣泛用于社會(huì)、經(jīng)濟(jì)和科學(xué)等領(lǐng)域的數(shù)據(jù)分析與判別決策上。利用Lasso回歸對中文垃圾郵件數(shù)據(jù)進(jìn)行建模分析，建立Lasso回歸分類模型，基于Lasso回歸選取的特征詞條建立邏輯回歸分類模型，結(jié)合中文垃圾郵件數(shù)據(jù)進(jìn)行模擬，實(shí)驗(yàn)表明基于Lasso回歸詞條選擇的邏輯回歸分類模型以時(shí)間效率損失為代價(jià)獲得了較好的分類性能。

[1]趙俊生,蘇依拉,馬志強(qiáng).基于內(nèi)容過濾的反垃圾郵件系統(tǒng)模型研究[J].內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2013,34(3):163-167.

[2]陳俊,劉遵雄.基于非負(fù)矩陣分解特征提取的垃圾郵件過濾[J].華東交通大學(xué)學(xué)報(bào),2010,27(6):75-80.

[3]沈躍伍.基于在線學(xué)習(xí)的垃圾郵件過濾技術(shù)研究[D].哈爾濱理工大學(xué),2012.

[4]WEI DENGPING.A logistic regressionmodel for semantic web servicematchmaking[J].Science China(Information Sciences), 2012,07:1715-1720.

[5]張恒,秦賓,許金鳳.上市公司財(cái)務(wù)預(yù)警的正則化邏輯回歸模型[J].華東交通大學(xué)學(xué)報(bào).2011,28(6):42-47.

[6]張文良,黃亞樓,倪維健.基于差分貢獻(xiàn)的垃圾郵件過濾特征選擇方法[J].計(jì)算機(jī)工程,2007(8):80-82.

[7]TIBSHIRANI R.Regression shrinkage and selection via the Lasso[J].Journal of the Royal Statistical Society,1994,58(B):267-288.

[8]龔建朝.Lasso及其相關(guān)方法在廣義線性模型模型選擇中的應(yīng)用[D].中南大學(xué),2008.

[9]孫燕.隨機(jī)效應(yīng)Logit計(jì)量模型的自適應(yīng)Lasso變量選擇方法研究[J].數(shù)量經(jīng)濟(jì)技術(shù)經(jīng)濟(jì)研究,2012(12):147-157.

[10]EFRON B,HASTIE T,JOHNSTONE L,et al.Least angle regression[J].Annals of Statistics.2004,32:407-451.

[11]方慧.TREC發(fā)展歷程及現(xiàn)狀分析[J].新世紀(jì)圖書館,2010(1):57-62.

Spam Filtering of Chinese Text Email Via Lasso

Xu Zheng1,Liu Zunxiong2,Zhang Xianlong2
(1.School of Electrical and Electronic Engineering,East China Jiaotong University,Nanchang 330013,China;2.School of Information Engineering,East China Jiaotong University,Nanchang 330013,China)

Text email data depicted with vector spacemodel are of high dimensionality and sparsity,which are not suitable for establishing email filtering classificationmodel.Generally,such data should be reduced before classifi?er training.Lasso regression is amultivariate linearmodel based on l1 regularization,which can estimatemodel pa?rameters while selecting the variables simultaneously.In this paper,the approaches to email classification based on Lasso are proposed.Also,the Lasso classificationmodel and the logisticalmodel with the selected term are es?tablished.Besides,simulation experiments with TREC06C are carried out,and the results show that logistic regres?sionmodel plus the term selected with Lasso achieves better performances.

Chinese text email;spam;filtering;Lasso;logistic regression

TP391

A

2014-05-10

國家自然科學(xué)基金項(xiàng)目（71361009，61065003）；教育部人文社會(huì)科學(xué)研究項(xiàng)目（13YJC630192）；華東交通大學(xué)校立科研課題（09DQ04）

徐征（1978—），女，講師，主要研究方向?yàn)閿?shù)理統(tǒng)計(jì)、機(jī)器學(xué)習(xí)、非線性系統(tǒng)分析與建模及其在網(wǎng)絡(luò)行為分析中的應(yīng)用。

1005-0523（2014）04-0130-06