垃圾短信分類
1 垃圾短信分類問題介紹
1.1 垃圾短信
隨著移動互聯科技的高速發展,信息技術在不斷改變著我們的生活,讓我們的生活更方便,其中移動通信技術己經在我們生活起到至關重要的作用,與我們每個人人息息相關。短信作為移動通信的一個基礎業務,由于簡單方便而且廉價,在很久以前就己成為人們交流溝通的一種方式,得到人們的認同,成為人們生活中不可缺少的一部分,以短信拜年為例,2015 年春節期間,全國短信發送量達到 203.9 億條,2016 年春節期間,全國短信發送量達到 139.6 億條。從上述數據我們可以看出,隨著科技的發展,短信可能會被其它社交方式代替,如微信、QQ 等,但是我們發現它們之間區別并不大,所以研究垃圾短信的分類問題對研究其它社交方式垃圾信息自動識別具有同樣意義。
垃圾短信是指未經用戶同意向用戶發送的用戶不愿意收到的短信息,或用戶不能根據自己的意愿拒絕接收的短信息,主要包含以下屬性:(一)未經用戶同意向用戶發送的商業類、廣告類等短信息;(二)其他違反行業自律性規范的短信息。
信息技術改變著我們的生活,我們享受著它帶給我們的方便快捷,與此同時我們也常遭受它帶給我們的各種困擾,在現在這個信息安全缺乏保障的時代,我們時常會收到一些我們所謂的垃圾短信,不少不法分子利用短信進行勒索、詐騙、傳播不實消息和黃色信息,手機用戶需要花費大量精力去對這樣的垃圾短信進行處理,對于那些詐騙短信一些辨識能力差的人群可能很容易上當受騙,遭受不必要的財產損失,對社會危害不小。垃圾短信危害手機用戶權利的同時也會給移動通信帶來負面的影響,運營商需要消耗資源對其過濾,垃圾短信己經成為社會的公害。
1.2 垃圾短信分類
如何將垃圾短信和正常短信區分開來,減少垃圾短信的危害,提高正常短信的利用率,實現短信的自動分類具有十分重要的意義。對于垃圾短信的過濾不僅有利于維護手機用戶的權益,同時也為移動通信的發展提供一個健康有序的環境。目前短信自動分類技術大都是基于短信文本,也可以說短信分類是一種文本挖掘。根據文本挖掘的原理,將文本挖掘的原理運用到垃圾短信的分類過濾,可以實現短信的自動分類,從而對垃圾短信進行識別過濾,減少垃圾短信給人們生活帶來的各種困擾,讓短信更好的方便人們的生活。
國外的文本分類研究開始于 20 世紀 50 年代末,早期文本分類需要人為的來定義分類規則,這種方法實現起來比較麻煩,同時有太多的人為主觀因素在里面,分類效果并不是太好。后來,H.P.Luhn 提出了詞頻統計的想法,為現有文本分類技術奠定了基礎。同時期,人們提出不少分類效果比較好文本分類模型,如 1960 年馬龍和庫恩提出了概率引索模型,還有索爾頓提出的向量空間模型,這些模型在現在做文本分類還時常被用到。
九十年代,隨著各種文本的出現和機器學習的快速發展,人們將文本分為已知類別的訓練文本和未知類別的待測文本。首先,使用已知類別的文本對分類模型進行訓練,建立判別規則或分類器,最后對那些未知類別的待測文本進行分類預測,在大量實踐中它的分類效果很好,這使它在文 ^ 分類中得到廣泛應用。如 1992 年,劉易斯在論文《信息檢索中的陳述與學習》比較統的詳細的介紹了文本分類系統實現的方法。后來,人們又在提高分類預測的效果方面做了很多工作,包括特征選擇、特征降維和分類技術的選擇等。如楊益民對特征選擇進行了比較,討論選擇文檔頻率、信息增益和互信息等的分類效果比較,1995 年,Corinna Cortes 和 Vapnik 等人于提出了機器學習中經典的分類方法——支持向量機,再后來人們使用非線性的支持向量機來對文本進行分類,后來人們又提出了一些組合方法,并且取得較好的分類效果。
國外常用的文本分類算法有 Logistic、支持向量機、樸素貝葉斯、決策樹、免近鄰、組合方法等方法。與國外相比,我們國內對文本分類研究起步較晚,國內最先提出文本分類研究的是侯漢清教授,1981 年,他對國外的文本分類研究的現狀、使用的分類技術和取得的成果做了詳細的介紹,后來越來越多人們開始接觸研究,并取得了不錯的成績。如 1995 年,吳軍等人率先研制出關于漢語語料的自動分類系統;19978 年,張月杰、姚天順等人研制出了第一個關于中文新聞文本分類的自動分類系統;1999 年,鄒濤、王繼成等開發的中文技術文本分類系統。除此之外在國內還有很多人為致力于解決中文文本分類中的各種問題默默的進行著研究,他們希望通過對不同問題的研究找到合適的方法使得文本分類的效果達到最好。如針對于不同語種的文本分類模型,隱含語義在中文文本中的處理技術,最大熵模型等。
1.3 本文主要工作
本文主要工作是首先對數據數據預處理方法、Logistic 回歸的原理進行簡單的闡述。然后,對短信的文本信息進行數據預處理并使用基于邏輯回歸的文本分類技術,建立相應的分類器,以實現對短信自動分類,將正常短信和垃圾短信準確的區分開,以實現垃圾短信的過濾。其中本文使用的短信文本是 lintcode 中垃圾短信分類訓練集的英文文本,主要包括垃圾短信和正常短信兩大類。
2 數據預處理
要對短信文本進行文本挖掘,我們首先要對數據進行清洗,即對獲取到的文本數據進行預處理,因本次主要針對英文文本進行研究,所以我們以英文文本為例,在本次大致將文本處理流程分三個步驟:Normalization 和 Stemming,即標準化和詞干提取。
2.1 標準化(Normalization)
得到純文本后,第一步通常要做就是 Normalization。在英文中,所有句子第一個單詞的首字母一般是大寫,有的單詞也會全部字母都大寫用于表示強調和區分風格,這樣更易于人類理解表達的意思,但是從計算機的角度來說是沒法區別“Car”、“car”、“CAR”是否是一個意思的,因此我們一般把文本中所有字母都轉換為小寫或大寫(通常意義上是小寫),每個詞用一個唯一的詞來表示。
例如在下面的代碼中,字符串文本調用 lower()函數就可以將所有字母轉換為小寫形式。
pre_str = 'I Love My Family'after_str = pre_str.lower()print(after_str)
輸出結果為:
i love my family
經過大小寫統一化之后,我們還需要做的是清除文本中的句號、問號、感嘆號等特殊字符,并且保留字母表中的字母和數字。文檔分類和聚類等應用中若要將所有文本文檔作為一個整體,那么正則表達式這個方法特別有效。用正則匹配小寫“a”到“z”以及大寫“A”到“Z”以及數字“0”到“9”的范圍之外的所有字符并用空格代替。這個方法無需指定所有標點符號。當然,也可以采用其他正則表達式。
例如在下面的代碼中,使用 re 模塊的 sub 正則匹配所有非 a-z,A-Z,0-9 的字母,并將其替換為空格。
import retext = 'the first time you see the second renaissance it may look boring.look at it at least and definitely watch part 2.it will??'text = re.sub(r'[^a-zA-Z0-9]', " ", text)print(text)
輸出結果:
the first time you see the second renaissance it may look boring look at it at least and definitely watchpart 2 it will
2.2 詞干提取(Stemming)
在語言形態學和信息檢索里,詞干提取是去除詞綴得到詞根的過程 ─—得到單詞最一般的寫法。對于一個詞的形態詞根,詞干并不需要完全相同;相關的詞映射到同一個詞干一般能得到滿意的結果,即使該詞干不是詞的有效根。從 1968 年開始在計算機科學領域出現了詞干提取的相應算法。很多搜索引擎在處理詞匯時,對同義詞采用相同的詞干作為查詢拓展,該過程叫做歸并。
一個面向英語的詞干提取器,例如,要識別字符串“cats”、“catlike”和“catty”是基于詞根“cat”;“stemmer”、“stemming”和“stemmed”是基于詞根“stem”。 很多詞干提取是基于 Porter 詞干提取算法寫出來的。Martin Porter 在 2000 年發布了一個基于該算法的官方版本的免費應用軟件。他在自己的工作上進行延伸,建立了一個 Snowball 算法,是編寫詞干提取算法的框架,并實現了一個改良的英文詞干提取器可以同時提取一些其他語言,本文所應用的就是 Snowball 算法。
例如,本文主要研究的是英語文本,則可以用如下代碼:
import nltk.stem>>> s = nltk.stem.SnowballStemmer('english')>>> s.stem('imaging')u'imag'>>>
2.3 TF-IDF 特征向量轉換
TF-IDF(termfrequency–inverse document frequency)是一種用于資訊檢索與資訊探勘的常用加權技術。TF-IDF 是一種統計方法,用以評估一字詞對于一個文件集或一個語料庫中的其中一份文件的重要程度。字詞的重要性隨著它在文件中出現的次數成正比增加,但同時會隨著它在語料庫中出現的頻率成反比下降。TF-IDF 加權的各種形式常被搜尋引擎應用,作為文件與用戶查詢之間相關程度的度量或評級。除了 TF-IDF 以外,因特網上的搜尋引擎還會使用基于連結分析的評級方法,以確定文件在搜尋結果中出現的順序。
一般情況下,將文本分詞并向量化后,就可以得到詞匯表中每個詞在文本中形成的詞向量,以下面的 5 個短文本為例做了詞頻統計:
不考慮停用詞,處理之后得到的詞向量如下:
如果直接將統計詞頻后的 13 維特征做為文本分類的輸入,會發現有一些問題。比如第五個文本,我們發現"come","American"和“Travel”各出現 1 次,而“to“出現了兩次。似乎看起來這個文本與”to“這個特征更關系緊密。但是實際上”to“是一個非常普遍的詞,幾乎所有的文本都會用到,因此雖然它的詞頻為 2,但是重要性卻比詞頻為 1 的"China"和“Travel”要低的多。如果向量化特征僅僅用詞頻表示就無法反應這一點,TF-IDF 可以反映這一點。下面給出 TF 與 IDF 的定義:
在一份給定的文件里,詞頻(term frequency, TF)指的是某一個給定的詞語在該文件中出現的次數。這個數字通常會被歸一化(分子一般小于分母區別于 IDF),以防止它偏向長的文件。(同一個詞語在長文件里可能會比短文件有更高的詞頻,而不管該詞語重要與否。)
逆向文件頻率 (inverse document frequency, IDF) 是一個詞語普遍重要性的度量。某一特定詞語的 IDF,可以由總文件數目除以包含該詞語之文件的數目,再將得到的商取對數得到。某一特定文件內的高詞語頻率,以及該詞語在整個文件集合中的低文件頻率,可以產生出高權重的 TF-IDF。因此,TF-IDF 傾向于過濾掉常見的詞語,保留重要的詞語。
而 TF-IDF 的主要思想是如果某個詞或短語在一篇文章中出現的頻率 TF 高,并且在其他文章中很少出現,則認為此詞或者短語具有很好的類別區分能力,適合用來分類。TF-IDF 實際上是:TF * IDF,TF 詞頻(Term Frequency),IDF 反文檔頻率。TF 表示詞條在文檔 d 中出現的頻率。上面是從定性上說明的 IDF 的作用,那么如何對一個詞的 IDF 進行定量分析呢?這里直接給出一個詞 x 的 IDF 的基本公式如下:
其中,N 代表語料庫中文本的總數,而 N(x)代表語料庫中包含詞 x 的文本總數。在一些特殊的情況下上面的公式會有一些小的問題,比如某一個生僻詞在語料庫中沒有,則分母變為 0,IDF 就沒有意義了,所以常用的 IDF 需要做一些平滑,使得語料庫中沒有出現的詞也可以得到一個合適的 IDF 值,平滑的方法有很多種,最常見的 IDF 平滑公式之一是:
進而可以推導計算某一個詞的 TF-IDF 值:
其中 TF(x)是指詞 x 在當前文本的詞頻。這個數字是對詞數的歸一化,以防止它偏向長的文件,(同一個詞語在長文件里可能會比短文件有更高的詞數,而不管該詞語重要與否)。對于某一特定文件里的詞語 x 來說,它的重要性可表示為:
以上式子中分子為 x 詞在第 j 個文件中出現的次數,而分母是在第 j 個文件中所有字詞的出現詞數之和。
在此思想下,我們通過詞干提取,得到了分詞后的文檔序列后,即可使用 HashingTF 的 transform()方法把句子轉化為成特征向量。可以看到,分詞序列被變換成一個稀疏特征向量,其中每個單詞都被散列成了一個不同的索引值,特征向量在某一維度上的值即該詞匯在文檔中出現的次數。最后,使用 IDF 來對單純的詞頻特征向量進行修正,使其更能體現不同詞匯對文本的區別能力,IDF 是一個 Estimator,調用 fit()方法并將詞頻向量傳入,即產生一個 IDFModel。很顯然,IDFModel 是一個 Transformer,調用它的 transform()方法,即可得到每一個單詞對應的 TF-IDF 度量值。最后可以發現,特征向量將被其在語料庫中出現的總次數進行了修正,通過 TF-IDF 得到的特征向量,在接下來可以被應用到相關的機器學習方法中。
3 建模方法
3.1 logistics 回歸
logistics 回歸是應用非常廣泛的一個分類機器學習算法,它將數據擬合到一個 logit 函數(或者叫做 logistic 函數)中,從而能夠完成對事件發生的概率進行預測。在垃圾短信分類中,我們將 logistics 回歸用作對垃圾短信的分類,因為 logistics 回歸的特點說明了此種方法對二分類問題的分類效果很好。
3.1.1 logistics 回歸的由來
我們都學過線性回歸,這是一種對多維空間中存在的樣本點,用特征的線性組合去擬合空間中點的分布和軌跡的方法。如下圖:
線性回歸雖然可以對連續值結果進行預測,但是現實生活中更常見的問題是分類問題。最簡單的情況是:是與否的二分類問題。比如說醫生需要判斷病人是否生病,銀行要判斷一個人的信用程度是否達到可以給他發信用卡的程度等等。
遇到這類問題的時候我們最直接的想法是,既然能夠用線性回歸預測出連續值結果,那根據結果設定一個閾值限定一下是不是就可以對這類問題進行求解呢?對于數據非常標準的時候也可以解決,但是現實中我們需要用來學習的數據并不都是那么精準的。
如上圖所示,右圖閾值作用下可以很好地預測數據,但是左圖中在閾值作用下還是有數據不能被回歸模型描述出來,那么這個閾值就是失效的。這只是一個很簡單的例子,現實中得到的數據會比這個復雜許多倍,因此線性回歸模型就不能用了,實現不了我們想要的分類效果。當線性回歸的結果輸出是一個連續值,而值的范圍是無法限定的,人們尋求把這個結果值映射為可以幫助我們判斷的結果,因此邏輯回歸就誕生了。為了能更好的做回歸,人們假設輸出結果是 (0,1) 的一個概率值,這個問題就很清楚了。于是找到了數學上的一個簡單函數了, sigmoid 函數,這個函數的特性表示如下:
sigmoid 函數的圖如下:
從函數圖上可以看出,函數 y=g(z)在 z=0 的時候取值為 1/2,而隨著 z 逐漸變小,函數值趨于 0,z 逐漸變大的同時函數值逐漸趨于 1,而這正是一個概率的范圍。
3.1.2 logistics 回歸模型
針對二分類問題(
),當所選的判別函數
,即可認為
,
,即可認為
。考慮正態分布的判別函數在
的情況。取后驗概率作為判別函數
:
針對二分類問題,只有
和
兩類,且有
,假設
,可以得到以下簡化的判別函數
:
取 d 維多元正態分布密度函數作為概率密度函數:
經過計算可以得到:
其中:
于是有:
再使用最大似然估計的想法對問題進行簡化,可以得到樣本的概率密度函數的參數
的似然函數,為了方便問題的分析以及利用梯度上升算法進行參數的求解,使用似然函數的對數函數(Log Likelihood,LL),即目標函數
:
其中:
,從而得到
。目標函數
稱為 logistics 回歸的損失函數,也就是說 logistics 回歸就是要求
,使得
最大。
3.1.3 梯度上升法求解 Logistic 回歸
經過前面的討論我們已經得到了 logistics 回歸的損失函數
,接下來就是如何找到合適的向量
來使損失函數
最大。我們首先通過求解
的一階導數和二階導數來判斷其性質。求導過程如下所示:
一階導數為:
二階導數:
其中:
從而可以發現
(半正定),因此 logistics 回歸的損失函數
是連續、可微、二次可微的凹曲線(開口向下)。根據梯度上升的思路,我們只要計算
的梯度,再根據下面的遞推公式進行梯度上升就可以得到
的最優解:
梯度上升公式為:
其中
為學習率,在垃圾短信分類中
是會隨著每次迭代從而減小,這樣可以減小隨機梯度上升的回歸系數波動問題,同時也同時比普通梯度上升收斂更快,加入常數項避免 alpha 變成 0。
3.2 隨機梯度上升算法
如果使用傳統的梯度上升算法,每次更新權值都會遍歷整個數據集,如果處理 100 個左右的數據集的耗時尚可,但是在本次實驗中,數據量稍大,所以使用的是隨機梯度上升算法。
隨機梯度上升算法即一次只用一個樣本點來更新回歸系數,由于可以在新樣本到來時隊分類器進行增量式的更新,因而隨機梯度上升算法是一個在線學習算法。與“在線學習”相對應,一次處理所有數據被稱為“批處理”。
對應的,隨機梯度上升算法可以寫成偽代碼形式:
所有回歸系數初始化為 1;隨機選擇樣本計算梯度;使用 alpha×gradient 更新回歸系數;刪除已計算的樣本向量返回回歸系數值;
可以看到,隨機梯度上升算法和原始梯度上升算法之間其實是十分相似的。但是隨機梯度上升法中處理的都是數值,沒有矩陣之間的計算,減少了計算機的工作量。此外,因為隨機梯度上升法在迭代過程中會出現局部波動現象,所以對隨機梯度上升方法又進行了一些改進。將其中學習步長
改為下式所示,其中 i 表示樣本點所處位置的下標,j 表示迭代的次數。可以看到,學習步長并不是嚴格單調下降的。并且用于更新權值的向量的選擇方法也改為隨機選擇。
4 仿真實驗
4.1 實驗策略
根據第二章所述的用來處理垃圾短信的數據預處理方法以及第三章所述的建模方法,我們可以得出如下圖所示的解決垃圾短信分類問題的一個有效的方案。
首先讀入 lintcode 網站所提供的訓練集數據,按照 2.1 節所示將所有英文單詞標準化,然后按照 2.2 節內容進行詞干提取工作,再將清洗后的數據按 2.3 節方法轉換成向量形式便于建模。在得到了數值向量形式的訓練集之后,就可建立 logistics 回歸模型,并對測試集作出預測。
4.2 程序實現
根據4.1節所述的方案,我們利用python實現了這個過程,下面列舉了一些關鍵的程序實現方法。
類 stocGradAscent1 實現了隨機選取向量更新權值策略以及步長非嚴格遞減策略,理論上可以使邏輯回歸算法迅速收斂。在隨機選擇向量過程中,從第 98 行可以看出,利用了 random 工具隨機選擇一個向量進行計算并更新權值,最后在第 102 行從數據集中刪掉了這一個向量。值得注意的是,python3 必須將 dataindex 轉換成 list 類型之后才能進行 del 操作。而在 Python2 中就不用。第 96 行說明學習步長存在一個常數項,雖然步長會不斷減小,但是最終不會減小到 0,同時也保證了學習步長更新時的非嚴格單調遞減性,和第三章中所敘述的方法相同,能夠有效地解決了數據波動問題。
類 read_data,作用為讀取 lintcode 垃圾短信分類實驗中 train_data.csv 中包含的數據,由于其中含有一系列字符串,在用 pandas 中方法時老是無法讀取所有數據,所以這里采用了比較繁瑣的按行讀取,并且將標簽“ham”、“spam”分別表示成了 0 和 1,便于分類。
類 cleandata 的作用是將訓練集中的所有單詞變成小寫,之后按照常用的英語表達習慣將縮寫還原成單獨的單詞。這是因為在之后的詞干提取以及 TF-IDF 向量轉換中,如果為單詞為縮寫形式則無法對其做判斷。
在定義完讀取數據的類 read_data 和類 cleandata 之后,可以按照如下的步驟對訓練集進行處理。首先調用類 read_data 讀取訓練集、測試集中的數據,之后進行數據清洗,這樣 train_data_content 和 test_data_content 中就僅僅保留了利用 snowballStemmer 方法所保留的詞干。之后直接調用 TfidfVectorizer 函數進行 TF-IDF 特征轉換,轉換后的訓練集和測試集分別放在 train_x、test_y 中。到這里,將自然語言轉化為機器學習算法可以識別的向量的工作就完成了,之后的工作就和普通的對率回歸基本一致,即計算出各變量的權值,然后輸入 sigmoid 函數進行分類,以及輸出最后的結果。
最終結果顯示最好的得分為 0.85,排在所有隊伍的第 52 名,得分還不是很好,我想對率回歸可以看做一個單層神經網絡,如果用 BP 神經網絡進行實驗的話,可能效果會更好。
5 總結
本次實驗完成了lintcode網站AI題中的垃圾短信分類題目,首先在將所有單詞標準化之后,利用snowball方法進行詞干的提取,然后利用TF-IDF特征向量轉換方法將自然語言轉換為數值向量,最后用logistics回歸方法進行建模預測。整個方案都是我們小組討論所得出,大家一起合作完成了程序以及報告。雖然最后參數調了很久,但是成績還是第一次的參數最好,而且成績排名也算靠前,但是我們也都對自然語言處理這個陌生的方向有了一定的認識,加深了對模式識別課程中內容的記憶。