基于數(shù)據(jù)流聚類的手機短信監(jiān)管系統(tǒng)

綦 科， 謝冬青

(廣州大學(xué)計算機科學(xué)與教育軟件學(xué)院，廣東廣州510065)

0 引 言

手機短信的泛濫不僅對網(wǎng)絡(luò)產(chǎn)生沖擊，更造成嚴重不良社會影響。加強短信，特別是垃圾短信的監(jiān)管是維護短信市場的正常秩序，保障信息安全的關(guān)鍵[1]。短信監(jiān)管的基礎(chǔ)是短信的內(nèi)容識別問題。目前短信監(jiān)管過濾功能的技術(shù)實現(xiàn)絕大部分是基于內(nèi)容關(guān)鍵字過濾技術(shù)和號碼黑白名單過濾技術(shù)[2-3]。這二類過濾技術(shù)存在嚴重不足：①過濾規(guī)則需要事先定制，缺乏及時性和動態(tài)性，用戶操作麻煩；②無法滿足用戶個性化定制需求；③基于文本匹配的方法處理效率較低，無法滿足大規(guī)模短信實時過濾監(jiān)管的要求；④容易發(fā)生錯誤過濾，識別精度不高。

與正常短信比較，需要監(jiān)管的短信具有如下特點[4]：①短信的內(nèi)容都很近似，某段時間內(nèi)不會做修改或者做很小的修改；②發(fā)送頻率比較高，發(fā)送數(shù)量大；③相同內(nèi)容的短信發(fā)送給不同的接收者；④發(fā)送沒有時間特征，即任何等長時間段發(fā)送短信的數(shù)目相同，因此，考慮到短信的接收發(fā)送都必須經(jīng)過短信中心的轉(zhuǎn)發(fā)，結(jié)合以上需要監(jiān)管短信的特點，短信的監(jiān)管大多在短信中心實施。但這種監(jiān)管方式存在的不足在于：某些短信，對于不同的人有著不同的作用，它可能是垃圾短信，也可能正是接受者所需要的短信，因此監(jiān)管需要有個性化的選擇，而這在短信中心是比較難實現(xiàn)的。因此，針對現(xiàn)有短信監(jiān)管方法的不足，本文基于文本數(shù)據(jù)流聚類算法和Bayes分類算法，利用短信中心可以集中監(jiān)控發(fā)送者的優(yōu)勢，設(shè)計短信接收者和短信中心端互動的二層監(jiān)管模型的技術(shù)手段，實現(xiàn)高效的手機短信監(jiān)管系統(tǒng)，有效的發(fā)現(xiàn)短信的發(fā)送者，使之成為個性化手機短信監(jiān)管過濾和源頭跟蹤的有效解決方案。

1 短信監(jiān)管系統(tǒng)的設(shè)計

1.1 系統(tǒng)框架

系統(tǒng)采用數(shù)據(jù)流聚類算法，利用短信中心可以集中監(jiān)控發(fā)送者的優(yōu)勢，設(shè)計短信接收者和短信中心端互動的二層監(jiān)管模型的技術(shù)手段，實現(xiàn)高效的手機短信個性化監(jiān)管系統(tǒng)。系統(tǒng)服務(wù)器端應(yīng)用在Windows平臺上，以O(shè)racle8i為數(shù)據(jù)庫，實現(xiàn)提出的基于數(shù)據(jù)流聚類的短信監(jiān)管系統(tǒng)；客戶端支持以Windows Mobile為操作系統(tǒng)的智能手機終端。系統(tǒng)體系結(jié)構(gòu)如圖1所示。

圖1 系統(tǒng)架構(gòu)

1.2 功能設(shè)計

系統(tǒng)結(jié)構(gòu)分為中心服務(wù)器和客戶端代理引擎二部分：系統(tǒng)將核心分類算法放置在短信中心服務(wù)器端，將客戶端引擎作為客戶端代理放置在客戶終端。短信中心從終端上收集用戶反饋的信息，然后對它們進行機器學(xué)習(xí)。機器學(xué)習(xí)后更新特征庫，客戶終端從中心下載這些更新特征。

(1)客戶端代理引擎--分類引擎

客戶端代理運行在終端上，以后臺服務(wù)的方式運行，短信分類引擎將用到存儲在終端并與短信中心實現(xiàn)同步更新的數(shù)據(jù)：個性化短信特征庫。分類引擎具有以下功能：

1)當(dāng)短信到達時，根據(jù)分類特征庫，調(diào)用分詞模塊和貝葉斯分類模塊，判別接收的短信是否屬于垃圾短信。

2)由用戶根據(jù)自己的喜好自行決定短信是否屬于垃圾短信。

3)通過網(wǎng)絡(luò)向短信中心反饋接收到的短信是否屬于垃圾短信，信息發(fā)送者號碼，發(fā)送時間，接收者號碼等信息。

4)通過網(wǎng)絡(luò)定期從短信中心下載更新的個性化特征庫，在下一條短信到達終端時，采用更新后的特征庫進行分類判別。

(2)中心服務(wù)器--短信處理中心

短信處理中心實現(xiàn)的是一種分布式的短信分類學(xué)習(xí)系統(tǒng)，同時采用數(shù)據(jù)流聚類算法對短信源頭進行跟蹤。其具體功能點如下：

1)黑白名單庫和個性化特征庫的維護更新。以二種途徑進行特征庫的更新：一是接收客戶終端反饋的短信分類信息，進行增量學(xué)習(xí)，每隔一段時間形成增量更新。服務(wù)器端在收到用戶反饋的短信后自動觸發(fā)Bayes機器訓(xùn)練算法，進行機器學(xué)習(xí)，更新個性化特征庫；經(jīng)過Bayes機器學(xué)習(xí)后的增量更新包括：新增的特征項及其在垃圾短信和正常短信中出現(xiàn)的條件概率；客戶端反饋的刪除的特征項；重新計算后的特征項及其在垃圾短信和正常短信中出現(xiàn)的條件概率。二是在短信中心維護黑白名單庫，由人工更新。

2)短信內(nèi)容處理模塊。包括分詞處理模塊、特征提取模塊。分詞處理模塊對短信進行高效率分詞；特征提取模塊則提取短信長度特征、頻率特征、規(guī)則特征、文本特征等信息。

3)數(shù)據(jù)流聚類模塊。通過數(shù)據(jù)流聚類算法找出潛在的監(jiān)管短信，再根據(jù)這些短信找到潛在短信的短信發(fā)送者。

1.3 工作流程

如圖1所示，系統(tǒng)對短信的分類流程如下：

(1)短信中心收到短信后，將短信文本送入黑白名單庫，依據(jù)黑白名單庫對短信進行第一層過濾。未通過第一層過濾的垃圾短信被屏蔽；通過第一層過濾的短信送入數(shù)據(jù)流聚類模塊。

(2)通過第一層過濾的短信送入數(shù)據(jù)流聚類模塊后，應(yīng)用數(shù)據(jù)流聚類算法進行垃圾短信源頭的識別，并將識別結(jié)果存入黑白名單庫，封鎖該號碼。

(3)沒有被封鎖的短信，由短信中心轉(zhuǎn)發(fā)短信給接收者。

(4)用戶接收到經(jīng)過短信后，根據(jù)終端上的分類引擎和分類特征庫，調(diào)用分詞模塊和貝葉斯分類模塊，將短信正確分類(垃圾或非垃圾短信)。

(5)由用戶根據(jù)自己的需求自行決定短信分類類別。

(6)通過網(wǎng)絡(luò)向短信中心反饋短信的分類類別，信息發(fā)送者號碼，發(fā)送時間，發(fā)送者號碼等信息。

(8)短信接收者通過網(wǎng)絡(luò)定期從短信中心下載更新的個性化特征庫，在下一條短信到達終端時，采用更新后的特征庫進行分類判別。

2 關(guān)鍵技術(shù)實現(xiàn)

(1)服務(wù)器端和客戶終端的短信文本分詞

要實現(xiàn)短信的監(jiān)管，首先必須理解短信的內(nèi)容。對于短信中文文本而言，要理解短信內(nèi)容，必須對中文文本進行分詞[5]。分詞是將短信分割成一個個有意義的單詞。與英文等以詞為最小語言單位不同，中文的最小語言元素是字，字再構(gòu)成詞，而且詞之間沒有分隔標記(比如空格)，所以中文的分詞相對來說復(fù)雜很多。

針對短信文本，在對其進行分詞之前，首先進行文本預(yù)處理，去除對分類沒有用處的詞，主要是分詞后形成的單個的字，以及代詞、嘆詞、語氣助詞等。預(yù)處理可以通過查表(助詞表、代詞表)方式進行。

系統(tǒng)分別在服務(wù)器端和客戶端進行分詞。現(xiàn)在的分詞算法[6-7]主要包括二類：一類是機械式分詞法，一般以分詞詞典為依據(jù)，通過文檔中的漢字串和詞表中的詞逐一匹配來完成詞的切分，另一類是理解式分詞法，即利用漢語的語法知識和語義知識進行分詞，需要建立分詞數(shù)據(jù)庫、知識庫和推理庫。由于理解式分詞法在語義分析和語法分析等方面遠未成熟，因此現(xiàn)有分詞系統(tǒng)多采用機械式分詞法。

本系統(tǒng)采用中科院FreeICTCLAS分詞系統(tǒng)[8]，該分詞系統(tǒng)為機械式分詞系統(tǒng)，具有較高的分詞準確度和分詞速度，且具有較高的靈活性，可以依據(jù)需要裁減分詞詞典?？紤]到短信文本中所用的詞匯一般都為常用詞，且服務(wù)器端對短信處理實時性的要求，以及手機終端存儲和處理能力的限制，我們對分詞詞典進行了精簡和壓縮，減少了詞典規(guī)模，最終分詞詞典包含約4萬條左右的詞條，占用存儲空間為2.5M左右，完全滿足服務(wù)器端和客戶終端的分詞需求。

(2)黑白名單庫和特征項條件概率表的維護更新

小流域是山區(qū)水源涵養(yǎng)和集水的基本單元。只有把小流域保護好、治理好，大流域的河道、水庫水質(zhì)、水量和生態(tài)才有基本保障。建設(shè)生態(tài)清潔小流域的最終目標，是促進生態(tài)系統(tǒng)良性循環(huán)，人與自然和諧相處，實現(xiàn)流域人口、資源、環(huán)境協(xié)調(diào)發(fā)展。

系統(tǒng)在服務(wù)器端維護黑白名單庫，設(shè)置黑白名單過濾特征庫和關(guān)鍵詞庫，由人工隨時更新。同時，系統(tǒng)在數(shù)據(jù)流聚類模塊，應(yīng)用數(shù)據(jù)流聚類算法進行垃圾短信源頭的識別，并將識別結(jié)果經(jīng)人工確認后更新黑白名單庫。

再者，系統(tǒng)維護一個最多包含200項特征項的條件概率表?？蛻艚K端通過Internet或3G無線網(wǎng)絡(luò)向服務(wù)器端傳輸反饋的個性化短信分類信息，包括短信分類類別(垃圾或非垃圾短信)、信息發(fā)送者號碼、發(fā)送時間、接收者號碼等信息。服務(wù)器接收客戶終端反饋的短信分類信息，應(yīng)用Bayes算法進行增量學(xué)習(xí)，收到用戶反饋的短信后自動觸發(fā)機器訓(xùn)練算法，進行機器學(xué)習(xí)，更新或新增特征項及相應(yīng)的條件概率。

(3)貝葉斯分類

貝葉斯分類[9]是基于貝葉斯定理進行的分類，該算法可以預(yù)測樣本屬于每類成員的可能性，最后將樣本分到可能性最大的那個類別中去。

貝葉斯分類過程如下：

1)讀入訓(xùn)練樣本短信，并統(tǒng)計各類短信數(shù)目；

2)讀入分詞詞典，對訓(xùn)練樣本短信進行分詞處理，得到各詞條及對應(yīng)的文檔頻率(document frequency，DF)值。

3)根據(jù)特征向量選取方法，按DF值從大到小，各類選前200個特征詞形成特征向量；

4)讀入訓(xùn)練樣本短信，對貝葉斯分類器進行訓(xùn)練；

5)讀入待分類短信，用訓(xùn)練后的貝葉斯分類器進行識別，并給出分類結(jié)果。

系統(tǒng)在短信中心端設(shè)置了二個貝葉斯分類器：一個用于短信的實時分類，當(dāng)用戶短信到達短信中心，由服務(wù)器調(diào)用，對短信進行分類判斷；另外一個作為后臺服務(wù)程序，定期輪詢每個用戶，根據(jù)用戶反饋的信息進行訓(xùn)練學(xué)習(xí)，并更新每個用戶的個性化特征庫。

系統(tǒng)在用戶終端上同樣啟用了貝葉斯分類器，對到達用戶終端的短信進行分類判斷，然后提示用戶作出選擇判斷。

(4)基于數(shù)據(jù)流聚類的短信源頭跟蹤

服務(wù)器端的數(shù)據(jù)流聚類模塊根據(jù)客戶端反饋的信息和監(jiān)管短信發(fā)送者的特點，識別出真正的短信發(fā)送者，該模塊的核心算法就是數(shù)據(jù)流聚類算法。數(shù)據(jù)流聚類是對元素集進行分組，使得組內(nèi)元素盡量相似，組間元素盡量相異的數(shù)據(jù)處理方法。數(shù)據(jù)流聚類研究的方向很多，如：針對基于劃分的k-中心聚類問題，Guha[10]在2000年首先提出基于k中心聚類的smallspace算法，該算法使用一個迭代過程實現(xiàn)了在數(shù)據(jù)流環(huán)境下的 k-中心聚類；將傳統(tǒng)數(shù)據(jù)聚類思想應(yīng)用到數(shù)據(jù)流聚類中，Cao[11]等人提出了Denstream算法，用基于密度的方法進行數(shù)據(jù)流聚類；針對多數(shù)據(jù)流的聚類問題，Beringer[12]等人提出了基于K-means的多數(shù)據(jù)流聚類方法，能夠快速近似地計算數(shù)據(jù)流間的相似度，使數(shù)據(jù)流聚類算法在各個領(lǐng)域得到廣泛應(yīng)用。

數(shù)據(jù)流聚類算法可分為基于劃分[13]，基于密度[14]和基于網(wǎng)格[15]等幾類，其中以基于劃分的居多。但這些方法都只適合處理數(shù)值型數(shù)據(jù)，不適用于文本聚類，而短信一般表現(xiàn)為文本，因此必須采用適用于文本的數(shù)據(jù)流聚類算法用于文本的聚類。本系統(tǒng)應(yīng)用Guha提出的k-中心聚類算法，找出潛在的被監(jiān)管短信，再根據(jù)這些短信找出潛在的短信發(fā)送者，實現(xiàn)短信源頭跟蹤。

系統(tǒng)在數(shù)據(jù)流聚類模塊，應(yīng)用如上數(shù)據(jù)流聚類算法進行垃圾短信源頭的識別，并將識別結(jié)果經(jīng)人工確認后更新黑白名單庫。

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

測試數(shù)據(jù)由某電信研究院提供，共20000條短信。經(jīng)人工標注，垃圾短信共計1400條(色情類205條、詐騙類45條、廣告類940條、謠言類80條、公共安全類130條)，占所有用戶短信的7%；正常短信18600條，占所有用戶短信的93%。系統(tǒng)的軟硬件測試環(huán)境為：服務(wù)器為Intel Pentium4 CPU，3GHz主頻，4GB內(nèi)存，500GB硬盤，Windows Server 2003操作系統(tǒng)；用戶終端為dopodA8188型號手機，該型號運行Windows Mobile操作系統(tǒng)，CPU為600MHz的AMD微處理器，帶有512M內(nèi)存。

表1 測試結(jié)果

實驗中從客戶端收集到反饋的垃圾短信號碼匯報個數(shù)共計64個，經(jīng)系統(tǒng)的數(shù)據(jù)流聚類模塊自動識別屬于垃圾短信發(fā)送者的號碼有53個，經(jīng)人工確認垃圾短信發(fā)送者號碼59個，源頭跟蹤準確率達到89.8%，這說明數(shù)據(jù)流聚類算法對識別垃圾發(fā)送者有較大幫助。

實驗還對客戶端性能進行了測試。表2給出了客戶端性能測試結(jié)果。從測試結(jié)果看，貝葉斯分類時間很短，影響處理速度的是短信分詞算法。但整體來看，客戶端處理時間不超過2s，而且相對于當(dāng)前智能手機的內(nèi)存配置，客戶端所占用的內(nèi)存不超過10M，一般智能手機的運算速度和內(nèi)存完全可以滿足性能要求。

表2 客戶端性能測試結(jié)果

4 結(jié)束語

本文描述了基于數(shù)據(jù)流聚類的短信監(jiān)管系統(tǒng)的功能設(shè)計和關(guān)鍵技術(shù)分析，利用基于文本內(nèi)容的數(shù)據(jù)流聚類算法，設(shè)計短信接收者和短信中心端互動的二層監(jiān)管模型，實現(xiàn)短信的個性化監(jiān)管和源頭跟蹤。系統(tǒng)經(jīng)過實驗測試，已經(jīng)在某通信部門進行中小范圍的試用，取得了良好的效果。提高系統(tǒng)的性能以支持更多的并發(fā)短信用戶，以及綜合考慮垃圾短信的特點以提高數(shù)據(jù)流聚類精度和源頭跟蹤精度將是本文的后續(xù)研究工作。

[1]黃文良,陳純,羅云彬.一種高效垃圾短信過濾系統(tǒng)的實現(xiàn)[J].電信科學(xué),2008,24(5):61-67.

[2]易陽峰.垃圾短信的監(jiān)控與原理實現(xiàn)[J].中興通訊技術(shù),2005,11(6):49-54.

[3]Zhang ya,Fu jianming.Identifying and tracebacking short message spam[J].Application Research of Computers,2006,23(3):245-247.

[4]鄧維維.數(shù)據(jù)流挖掘算法的研究及應(yīng)用[D].廣州:華南理工大學(xué)博士學(xué)位論文,2007:73-74.

[5]He Guobin,Zhao Jinglu.Search on algorithm of Chinese word automatic segmentation[J].Computer Engineering and Applications,2010,46(3):125-127.

[6]張啟宇,朱玲,張雅萍.中文分詞算法研究綜述[J].情報探索,2008(11):86-91.

[7]文庭孝.漢語自動分詞研究進展[J].圖書與情報,2005(5):54-63.

[8]張華平.計算所漢語詞法分析系統(tǒng)ICTCLAS[EB/OL].http://sewm.pku.edu.cn/QA/reference/ICTCLAS/FreeICTCLAS/,2009-12-01.

[9]Du Huifeng,Liu Qiongsun.Bayesian classifier using copula[J].Computer Engineering and Applications,2010,46(10):111-113.

[10]Guha S,Mishra N,Motwani R.Clustering data streams[C].IEEE Symposium on Foundations of Computer Science,2000:359-366.

[11]Cao F,Martin E,Qian W N,et al.Density-based clustering over an evolving data stream with noise[C].Proceedings of the Sixth SIAM International Conference on Data Mining,2006:328-339

[12]Beringer J,Hullermeier E.Online clustering of parallel data streams[J].Data and Knowledge Engineering,2006,58(2):180-204.

[13]Aggarwa C C,Han J,Wang J,et al.Frame work for clustering evolving data stream[C].VLDB Conference,2003:81-92.

[14]Cao F,Martin E,Qian W N,et al.Density-based clustering over an evolving data stream with noise[C].Proceedings of the Sixth SIAM International Conference on Data Mining,2006:328-339.

[15]朱蔚恒,印鑒,謝益煌.基于數(shù)據(jù)流的任意形狀聚類算法[J].軟件學(xué)報,2006,17(3):379-388.