基于自分簇自學(xué)習算法的垃圾短信識別

李 根, 王科峰, 賁衛(wèi)國, 宋 微, 劉鴻儒, 徐亦晉

(1. 中國聯(lián)通網(wǎng)絡(luò)通信集團有限公司 吉林省分公司, 長春 130021； 2. 吉林大學(xué) 計算機科學(xué)與技術(shù)學(xué)院, 長春 130012)

0 引 言

垃圾短信是指內(nèi)容違反相關(guān)規(guī)定或其內(nèi)容引起用戶反感的短信, 例如金融欺詐、 違法營銷、 詛咒威脅和反動言論等。垃圾短信發(fā)送者會在內(nèi)容上盡一切可能偽裝混淆, 常見的偽裝手段包括： 同型字替換、 同音字替換、 組合字替換、 拆解字替換、 亂序替換和暗語替換等多種方式, 使其在保持一定的可讀性的同時不被過濾系統(tǒng)識別。

常見的垃圾短信識別方法有兩種[1], 分別為基于關(guān)鍵字規(guī)則的方法和基于短信內(nèi)容的方法。基于關(guān)鍵字規(guī)則的識別方法需要人工錄入關(guān)鍵字和規(guī)則, 效率低下且識別效果差, 更無法及時應(yīng)對垃圾短信發(fā)送者的故意偽裝混淆。目前主流的識別技術(shù)是基于短信內(nèi)容的方法, 主要是指通過機器學(xué)習算法對短信內(nèi)容的特征進行分類, 典型的方法如黃文明等[2]提出的文本加權(quán)KNN(K-Nearest Neighbor)算法, 賴文輝等[3]采用的詞向量卷機神經(jīng)網(wǎng)絡(luò)方法, 以及樸素貝葉斯、 邏輯回歸、 支持向量機和隨機森林等方法[4-5], 這些方法對已知相似樣本效果較好, 但對垃圾短信的變種, 即人為故意偽裝混淆后的垃圾短信, 識別效果并不理想[6]。

導(dǎo)致這種問題的原因是傳統(tǒng)的文本分類算法將樣本預(yù)先分為幾個簇, 并訓(xùn)練形成識別模型, 當垃圾短信被人工偽裝混淆后, 如采用拼接字法、 同音相似字法等, 造成原有特征缺失, 識別模型的效果會急劇下降。雖然詞向量[7]和LSTM(Long Short-Term Memory)網(wǎng)絡(luò)[8]取得了一定的效果, 但由于垃圾短信是人工主動針對識別模型進行偽裝, 導(dǎo)致樣本特征具有復(fù)雜性和多樣性, 隨著新樣本的不斷加入, 簇特征邊界越來越模糊, 甚至與正常短信樣本有交集, 導(dǎo)致識別模型效果下降。

筆者提出一種垃圾短信自分簇和自學(xué)習方法, 采用編輯距離構(gòu)建垃圾短信關(guān)系鏈, 通過聚類算法實現(xiàn)垃圾短信的動態(tài)自分簇能力, 使簇與簇的特征邊界清晰, 提高識別準確率。尋找簇核心, 并以簇核心計算簇內(nèi)各個垃圾短信樣本的權(quán)值, 以權(quán)值樣本構(gòu)建識別模型, 每次新樣本加入后, 會重新計算簇核心及簇內(nèi)樣本權(quán)值, 更新分類器, 實現(xiàn)自學(xué)習能力。

1 垃圾短信自分簇方法

垃圾短信偽裝的方法多種多樣, 但其目的是固定的, 對短信內(nèi)容的偽裝只是在文本的展現(xiàn)形式上做出一些變化, 在確保不影響接收者閱讀的前提下躲避垃圾短信過濾系統(tǒng)的識別, 所以, 發(fā)布者通常會采用少變快變的策略。對同一個類型的垃圾短信, 可以將發(fā)布者對短信內(nèi)容的偽裝看作是垃圾短信的變種, 其特征是漸進的、 高頻率的變化, 通過收集一定時間內(nèi)的全量短信數(shù)據(jù), 就可以通過內(nèi)容對比構(gòu)建出這條垃圾短信的演化關(guān)系鏈。

構(gòu)建垃圾短信關(guān)系鏈的關(guān)鍵方法是內(nèi)容相似度比較, 即對任意兩條短信的內(nèi)容做相似度計算, 相似度高則認為兩條短信的親緣關(guān)系近, 相似度低則認為沒有關(guān)系。因為垃圾短信的變種是通過人工少量修改短信內(nèi)容隱藏關(guān)鍵字, 所以適合采用編輯距離[9]方法對內(nèi)容進行相似度計算, 經(jīng)過對比選用Levenshtein編輯距離算法[10-12]。

編輯距離是指兩個字符串之間, 由一個轉(zhuǎn)成另一個所需的最少編輯操作次數(shù), 允許的編輯操作包括： 替換一個字符、 插入一個字符和刪除一個字符3種操作。一個字符串變成另一個字符串所需要的編輯次數(shù)越少, 則認為兩個字符串的相似度越大。

兩個字符串a(chǎn)和b的Levenshtein編輯距離計作:Llevab, 表示為

(1)

以現(xiàn)有垃圾短信樣本構(gòu)成原始樣本庫, 任意選取其中一條垃圾短信作為節(jié)點, 計算與該條短信編輯距離小于k的節(jié)點(k的取值與短信樣本的全量程度有關(guān), 初始值為5, 需根據(jù)網(wǎng)絡(luò)構(gòu)成情況調(diào)整), 并建立關(guān)聯(lián), 重復(fù)此過程對所有節(jié)點進行計算, 最終構(gòu)成垃圾短信相似度關(guān)系鏈示意圖, 如圖1a所示。

通過圖1可知, 存在多個相似度較高且集中的垃圾短信簇群, 通過聚類算法可以完成簇群的分類聚類。因為無法提前預(yù)知垃圾短信簇群的數(shù)量, 所以經(jīng)過比較選擇可自動確定分類數(shù)量的MeanShift聚類算法[12-14], MeanShift的滑窗半徑r為編輯距離, 可以控制簇群的分割程度, 即變化到一定程度則認定為是另一種類的垃圾短信, 實現(xiàn)垃圾短信的自分簇能力, 如圖1b所示。

當新的垃圾短信樣本加入時, 重新計算樣本間的編輯距離并重新聚類便可以對垃圾短信的分簇進行更新。

自分簇方法比人工分簇更加準確和高效, 可以解決簇與簇之間樣本交叉問題, 以及特征邊界模糊的問題, 也可以解決后續(xù)識別模型訓(xùn)練過程中的樣本特征不均衡問題, 通過自分簇能力使每種類型的垃圾短信的特征在訓(xùn)練過程中都能突出體現(xiàn), 進一步提高了識別模型的準確率。

圖1 垃圾短信相似度關(guān)系鏈示意圖Fig.1 Schematic diagram of the similarity relationship chain of spam messages

2 垃圾短信自學(xué)習方法

在遇到垃圾短信的未知變種時, 如果內(nèi)容特征變化較小, 通過自分簇方法仍可以維持較好的識別效果。隨著時間的增加, 內(nèi)容變化由于累積逐步變大, 識別模型的準確率開始降低, 這就需要使識別模型具有一定的自學(xué)習能力。自學(xué)習方法就是將新的垃圾短信變種樣本加入到相應(yīng)的垃圾短信簇中, 并重新訓(xùn)練識別模型, 如何準確判定一條短信是否為垃圾短信是自學(xué)習算法的關(guān)鍵。

垃圾短信的來源主要有3個： 系統(tǒng)攔截、 用戶舉報和管理員處理。系統(tǒng)攔截存在一定的不可控的錯誤率； 用戶舉報由用戶主觀決定, 同樣存在不理智行為； 管理員處理可認為可靠, 但管理員效率低下, 無法完全依賴。垃圾短信的來源是一個典型的弱可信系統(tǒng)[9], 這需要算法對所有來源的垃圾短信提供一定的容錯性, 即實現(xiàn)被錯誤判定的短信即使歸類到垃圾短信樣本庫中, 經(jīng)過訓(xùn)練也不影響識別模型的整體準確率和穩(wěn)定性, 或在一定時間內(nèi)能恢復(fù)被錯誤判定的短信對識別模型的影響。

垃圾短信發(fā)送者為達到目的, 垃圾短信是被大量發(fā)送的, 典型特征是大量和高重復(fù)性, 反之被錯誤判定的垃圾短信的特征是少量, 即錯誤樣本一定是少部分用戶因為情緒、 偏見或其他原因?qū)е碌? 多數(shù)用戶并不會有這種判定。因此, 通過垃圾短信數(shù)量特征和時效性特征, 對垃圾短信樣本進行加權(quán)處理, 可以有效解決垃圾短信來源弱可信問題, 使識別模型具有一定的容錯性[12,15-16]。

具體方法如下。

1) 簇核心選取。為使每個簇都具有一個代表性特征, 所以需要選取每個簇的簇核心c, 簇核心選取簇內(nèi)樣本最集中的樣本節(jié)點, 即與簇內(nèi)與所有樣本距離最小的樣本節(jié)點, 如下

(2)

其中si為分類中樣本節(jié)點i到其他節(jié)點的平均距離, 核心集合ci為si最小的樣本節(jié)點。如有多個核心滿足條件, 則選取與最新的樣本節(jié)點距離最短的樣本節(jié)點作為簇核心。

2) 樣本基礎(chǔ)權(quán)值。其計算方法如下

bi=alnNi

(3)

其中Ni為某個樣本出現(xiàn)的數(shù)量, 出現(xiàn)一次增加1,a為基礎(chǔ)權(quán)值調(diào)節(jié)系數(shù), 根據(jù)識別模型效果進行調(diào)整,bi為樣本節(jié)點i的基礎(chǔ)權(quán)值。

3) 樣本權(quán)值分層調(diào)整。以簇核心為中心, 根據(jù)編輯距離區(qū)間d對分類中的樣本進行分層, 取

l1:d∈[1,5],l2:d∈[5,10],l3:d∈[10,∞]

每層樣本在神經(jīng)網(wǎng)絡(luò)訓(xùn)練中的樣本權(quán)重調(diào)整系數(shù)為o1,o2,o3, 分別取1,0.75,0.25, 則調(diào)整后權(quán)值如下

wi=bioi

(4)

如上實現(xiàn)了在識別模型訓(xùn)練過程中強化新樣本的權(quán)重, 減弱舊樣本的權(quán)重。隨著新樣本的不斷加入, 整個簇的簇核心會有所移動, 移動后會逐漸圈入高頻出現(xiàn)的新樣本、 逐漸圈出低頻出現(xiàn)舊樣本, 并構(gòu)成新的不同的樣本權(quán)重, 使整個識別模型傾向于新的、 大量的被判定的樣本, 而少量的、 誤判的樣本會被漸漸排除分類, 實現(xiàn)識別模型的容錯能力, 如圖2所示。

圖2 垃圾短信自學(xué)習核心移動示例圖Fig.2 Examples of spam messages self-learning core movement

4) 樣本權(quán)值時間調(diào)整。新樣本的權(quán)重較低, 如果系統(tǒng)長期運行, 舊樣本累積權(quán)值較高, 核心很難向新樣本移動, 為解決此問題引入時間戳, 如新樣本為原有樣本則更新原有樣本時間戳, 時間戳過舊則按照比例降低樣本權(quán)值, 方法如下

ti=1/m

(5)

其中m為距離當前日期的月份數(shù),ti為節(jié)點i的時間調(diào)整系數(shù), 調(diào)整后的樣本權(quán)值為

wi=biti

(6)

通過時間調(diào)整, 可以保持識別模型對新型變種垃圾短信的靈敏度。

5) 樣本權(quán)值。最終樣本權(quán)值如下

wi=bioiti

(7)

最終對自分簇后的垃圾短信樣本簇與正常短信樣本使用CNN(Convolutional Neural Networks) 神經(jīng)網(wǎng)絡(luò)分類算法進行分類訓(xùn)練, 在訓(xùn)練中, 以樣本權(quán)值大小為采樣幾率進行樣本抽取參與訓(xùn)練, 高權(quán)值垃圾短信樣本高幾率被抽中, 低權(quán)值垃圾短信樣本低幾率被抽中, 最終形成識別模型。

隨著新樣本的不斷加入, 通過對樣本庫整體重復(fù)進行自分簇和自學(xué)習過程, 可以實現(xiàn)識別模型的自學(xué)習能力。

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

自分類算法的實驗部分, 數(shù)據(jù)集選自真實短信網(wǎng)關(guān)數(shù)據(jù), 對發(fā)送號碼和接收號碼做脫敏處理后構(gòu)成訓(xùn)練數(shù)據(jù)集, 通過人工進行篩選, 共整理84 557條短信, 其中垃圾短信52 169條, 包括被投訴短信或明顯違反規(guī)定的短信, 其余為正常短信。訓(xùn)練采用6 ∶2 ∶2的方式劃分為訓(xùn)練集, 驗證集和測試集。

測試方法為無預(yù)分簇(垃圾短信、 正常短信兩類)、 人工分簇(正常短信8類、 垃圾短信17類)、 筆者自分簇方法。

筆者算法主要集中在樣本的分簇處理與樣本的權(quán)值處理, 是一種樣本預(yù)處理方法, 可以與多種分類算法相結(jié)合, 實驗部分選用CNN神經(jīng)網(wǎng)絡(luò)[3]和RNN神經(jīng)網(wǎng)絡(luò)[8]算法進行訓(xùn)練對比。結(jié)果選取訓(xùn)練過程30 min內(nèi)的最高準確率情況下最低loss率的模型, 在測試集進行準確率測試, 進行10次, 結(jié)果分別如圖3、 圖4、 表1、 表2所示。

圖3 CNN神經(jīng)網(wǎng)絡(luò)分類訓(xùn)練結(jié)果 圖4 RNN神經(jīng)網(wǎng)絡(luò)分類訓(xùn)練結(jié)果圖 Fig.3 CNN neural network classification Fig.4 RNN neural network classification training result diagram training result diagram

表1 CNN神經(jīng)網(wǎng)絡(luò)分類訓(xùn)練

表2 RNN神經(jīng)網(wǎng)絡(luò)分類訓(xùn)練

由實驗結(jié)果可知, 筆者自分簇算法相對于無預(yù)分類、 人工分類準確率提高2.51%～5.14%, 且模型的準確率穩(wěn)定, 證明自分簇算法可以有效提高模型識別效果。

自學(xué)習算法的實驗部分, 數(shù)據(jù)集采用所在地區(qū)一年內(nèi)真實網(wǎng)關(guān)數(shù)據(jù)歷史記錄, 進行脫密處理后以月為單位生成樣本集, 通過隨機抽取方式使每周的樣本集的大小在80 000條左右, 共產(chǎn)生12個樣本集, 模型采用自分類算法, CNN神經(jīng)網(wǎng)絡(luò)分類模型, 分別采用開啟自學(xué)習方式和不開啟自學(xué)習方式, 按照月份順序通過模型進行判斷, 準確率如圖5、 圖6、 表3、 表4所示。

圖5 第1次測試結(jié)果圖 圖6 第2次測試結(jié)果圖 Fig.5 Graph of the first test result Fig.6 Graph of the second test result

表3 第1次測試

表4 第2次測試

由實驗數(shù)據(jù)可知, 在開啟自學(xué)習功能的情況下, 經(jīng)歷過12個月時長的樣本后, 模型依然保持著穩(wěn)定的準確率, 而未開啟自學(xué)習功能的方式, 經(jīng)歷過12個月時長的樣本后, 準確率有較明顯的下降, 證明筆者算法對垃圾短信的變種樣本具有自學(xué)習能力。

4 結(jié) 語

筆者針對垃圾短信變種的特征, 提出了基于距離特征的垃圾短信自分簇算法和自學(xué)習算法, 使垃圾短信識別模型能根據(jù)新的垃圾短信樣本特征進行自學(xué)習, 并自我更新, 使識別模型具有持續(xù)識別新型垃圾短信變種的能力。

筆者主要工作是垃圾短信的樣本分類和處理, 是一種樣本預(yù)處理優(yōu)化方法, 將文中方法與其他更復(fù)雜的機器學(xué)習算法相結(jié)合, 可以進一步提高模型的識別準確率。