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

徐征，劉遵雄，張賢龍

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

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

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

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

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

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

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

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

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

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

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

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

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

2 Lasso回歸及LAR算法

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

其拉格朗日表達式為

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

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

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

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

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

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

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

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

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

3 實驗和結(jié)果分析

3.1 數(shù)據(jù)準備及評價標準

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

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

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

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

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

其中：

lhm：1為當hm%=0.1時，對應(yīng)的sm%的值。因為在實際中，將一封正常郵件錯分為垃圾郵件的代價系數(shù)要比將一封垃圾錯分為正常郵件的代價系數(shù)高的多。

3.2 實驗及結(jié)果分析

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

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

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

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

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

基于Lasso回歸實驗選出的詞條，建立相應(yīng)的邏輯回歸分類模型，并進行測試，相應(yīng)評價指標值見表3。對比表2和表3，可以看出，在性能方面等方面，使用邏輯回歸的1-ROCA%確實明顯優(yōu)于Lasso回歸，而且Lasso過濾器的誤判率也高于邏輯回歸，但是邏輯回歸方法的時耗要比直接使用Lasso做分類判別的時耗高，因為前者比后者多出了邏輯回歸模型建立的時間。所以在時間效率上，邏輯回歸不如Lasso過濾算法。

圖4 過濾器的ROC學習曲線Fig.4 ROC learning curve of Filter

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

4 結(jié)論

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

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

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

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

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

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

[6]張文良,黃亞樓,倪維健.基于差分貢獻的垃圾郵件過濾特征選擇方法[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].中南大學,2008.

[9]孫燕.隨機效應(yīng)Logit計量模型的自適應(yīng)Lasso變量選擇方法研究[J].數(shù)量經(jīng)濟技術(shù)經(jīng)濟研究,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].新世紀圖書館,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

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

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

1005-0523（2014）04-0130-06