基于數據流聚類的手機短信監管系統

綦 科， 謝冬青

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

0 引 言

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

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

1 短信監管系統的設計

1.1 系統框架

系統采用數據流聚類算法，利用短信中心可以集中監控發送者的優勢，設計短信接收者和短信中心端互動的二層監管模型的技術手段，實現高效的手機短信個性化監管系統。系統服務器端應用在Windows平臺上，以Oracle8i為數據庫，實現提出的基于數據流聚類的短信監管系統；客戶端支持以Windows Mobile為操作系統的智能手機終端。系統體系結構如圖1所示。

圖1 系統架構

1.2 功能設計

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

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

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

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

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

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

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

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

短信處理中心實現的是一種分布式的短信分類學習系統，同時采用數據流聚類算法對短信源頭進行跟蹤。其具體功能點如下：

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

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

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

1.3 工作流程

如圖1所示，系統對短信的分類流程如下：

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

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

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

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

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

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

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

2 關鍵技術實現

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

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

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

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

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

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

小流域是山區水源涵養和集水的基本單元。只有把小流域保護好、治理好，大流域的河道、水庫水質、水量和生態才有基本保障。建設生態清潔小流域的最終目標，是促進生態系統良性循環，人與自然和諧相處，實現流域人口、資源、環境協調發展。

系統在服務器端維護黑白名單庫，設置黑白名單過濾特征庫和關鍵詞庫，由人工隨時更新。同時，系統在數據流聚類模塊，應用數據流聚類算法進行垃圾短信源頭的識別，并將識別結果經人工確認后更新黑白名單庫。

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

(3)貝葉斯分類

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

貝葉斯分類過程如下：

1)讀入訓練樣本短信，并統計各類短信數目；

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

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

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

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

系統在短信中心端設置了二個貝葉斯分類器：一個用于短信的實時分類，當用戶短信到達短信中心，由服務器調用，對短信進行分類判斷；另外一個作為后臺服務程序，定期輪詢每個用戶，根據用戶反饋的信息進行訓練學習，并更新每個用戶的個性化特征庫。

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

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

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

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

系統在數據流聚類模塊，應用如上數據流聚類算法進行垃圾短信源頭的識別，并將識別結果經人工確認后更新黑白名單庫。

3 實驗結果及分析

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

表1 測試結果

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

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

表2 客戶端性能測試結果

4 結束語

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

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

[2]易陽峰.垃圾短信的監控與原理實現[J].中興通訊技術,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]鄧維維.數據流挖掘算法的研究及應用[D].廣州:華南理工大學博士學位論文,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]張華平.計算所漢語詞法分析系統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]朱蔚恒,印鑒,謝益煌.基于數據流的任意形狀聚類算法[J].軟件學報,2006,17(3):379-388.