綦 科, 謝冬青
(廣州大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院,廣東廣州510065)
手機(jī)短信的泛濫不僅對(duì)網(wǎng)絡(luò)產(chǎn)生沖擊,更造成嚴(yán)重不良社會(huì)影響。加強(qiáng)短信,特別是垃圾短信的監(jiān)管是維護(hù)短信市場(chǎng)的正常秩序,保障信息安全的關(guān)鍵[1]。短信監(jiān)管的基礎(chǔ)是短信的內(nèi)容識(shí)別問(wèn)題。目前短信監(jiān)管過(guò)濾功能的技術(shù)實(shí)現(xiàn)絕大部分是基于內(nèi)容關(guān)鍵字過(guò)濾技術(shù)和號(hào)碼黑白名單過(guò)濾技術(shù)[2-3]。這二類(lèi)過(guò)濾技術(shù)存在嚴(yán)重不足:①過(guò)濾規(guī)則需要事先定制,缺乏及時(shí)性和動(dòng)態(tài)性,用戶(hù)操作麻煩;②無(wú)法滿(mǎn)足用戶(hù)個(gè)性化定制需求;③基于文本匹配的方法處理效率較低,無(wú)法滿(mǎn)足大規(guī)模短信實(shí)時(shí)過(guò)濾監(jiān)管的要求;④容易發(fā)生錯(cuò)誤過(guò)濾,識(shí)別精度不高。
與正常短信比較,需要監(jiān)管的短信具有如下特點(diǎn)[4]:①短信的內(nèi)容都很近似,某段時(shí)間內(nèi)不會(huì)做修改或者做很小的修改;②發(fā)送頻率比較高,發(fā)送數(shù)量大;③相同內(nèi)容的短信發(fā)送給不同的接收者;④發(fā)送沒(méi)有時(shí)間特征,即任何等長(zhǎng)時(shí)間段發(fā)送短信的數(shù)目相同,因此,考慮到短信的接收發(fā)送都必須經(jīng)過(guò)短信中心的轉(zhuǎn)發(fā),結(jié)合以上需要監(jiān)管短信的特點(diǎn),短信的監(jiān)管大多在短信中心實(shí)施。但這種監(jiān)管方式存在的不足在于:某些短信,對(duì)于不同的人有著不同的作用,它可能是垃圾短信,也可能正是接受者所需要的短信,因此監(jiān)管需要有個(gè)性化的選擇,而這在短信中心是比較難實(shí)現(xiàn)的。因此,針對(duì)現(xiàn)有短信監(jiān)管方法的不足,本文基于文本數(shù)據(jù)流聚類(lèi)算法和Bayes分類(lèi)算法,利用短信中心可以集中監(jiān)控發(fā)送者的優(yōu)勢(shì),設(shè)計(jì)短信接收者和短信中心端互動(dòng)的二層監(jiān)管模型的技術(shù)手段,實(shí)現(xiàn)高效的手機(jī)短信監(jiān)管系統(tǒng),有效的發(fā)現(xiàn)短信的發(fā)送者,使之成為個(gè)性化手機(jī)短信監(jiān)管過(guò)濾和源頭跟蹤的有效解決方案。
系統(tǒng)采用數(shù)據(jù)流聚類(lèi)算法,利用短信中心可以集中監(jiān)控發(fā)送者的優(yōu)勢(shì),設(shè)計(jì)短信接收者和短信中心端互動(dòng)的二層監(jiān)管模型的技術(shù)手段,實(shí)現(xiàn)高效的手機(jī)短信個(gè)性化監(jiān)管系統(tǒng)。系統(tǒng)服務(wù)器端應(yīng)用在Windows平臺(tái)上,以O(shè)racle8i為數(shù)據(jù)庫(kù),實(shí)現(xiàn)提出的基于數(shù)據(jù)流聚類(lèi)的短信監(jiān)管系統(tǒng);客戶(hù)端支持以Windows Mobile為操作系統(tǒng)的智能手機(jī)終端。系統(tǒng)體系結(jié)構(gòu)如圖1所示。
圖1 系統(tǒng)架構(gòu)
系統(tǒng)結(jié)構(gòu)分為中心服務(wù)器和客戶(hù)端代理引擎二部分:系統(tǒng)將核心分類(lèi)算法放置在短信中心服務(wù)器端,將客戶(hù)端引擎作為客戶(hù)端代理放置在客戶(hù)終端。短信中心從終端上收集用戶(hù)反饋的信息,然后對(duì)它們進(jìn)行機(jī)器學(xué)習(xí)。機(jī)器學(xué)習(xí)后更新特征庫(kù),客戶(hù)終端從中心下載這些更新特征。
(1)客戶(hù)端代理引擎--分類(lèi)引擎
客戶(hù)端代理運(yùn)行在終端上,以后臺(tái)服務(wù)的方式運(yùn)行,短信分類(lèi)引擎將用到存儲(chǔ)在終端并與短信中心實(shí)現(xiàn)同步更新的數(shù)據(jù):個(gè)性化短信特征庫(kù)。分類(lèi)引擎具有以下功能:
1)當(dāng)短信到達(dá)時(shí),根據(jù)分類(lèi)特征庫(kù),調(diào)用分詞模塊和貝葉斯分類(lèi)模塊,判別接收的短信是否屬于垃圾短信。
2)由用戶(hù)根據(jù)自己的喜好自行決定短信是否屬于垃圾短信。
3)通過(guò)網(wǎng)絡(luò)向短信中心反饋接收到的短信是否屬于垃圾短信,信息發(fā)送者號(hào)碼,發(fā)送時(shí)間,接收者號(hào)碼等信息。
4)通過(guò)網(wǎng)絡(luò)定期從短信中心下載更新的個(gè)性化特征庫(kù),在下一條短信到達(dá)終端時(shí),采用更新后的特征庫(kù)進(jìn)行分類(lèi)判別。
(2)中心服務(wù)器--短信處理中心
短信處理中心實(shí)現(xiàn)的是一種分布式的短信分類(lèi)學(xué)習(xí)系統(tǒng),同時(shí)采用數(shù)據(jù)流聚類(lèi)算法對(duì)短信源頭進(jìn)行跟蹤。其具體功能點(diǎn)如下:
1)黑白名單庫(kù)和個(gè)性化特征庫(kù)的維護(hù)更新。以二種途徑進(jìn)行特征庫(kù)的更新:一是接收客戶(hù)終端反饋的短信分類(lèi)信息,進(jìn)行增量學(xué)習(xí),每隔一段時(shí)間形成增量更新。服務(wù)器端在收到用戶(hù)反饋的短信后自動(dòng)觸發(fā)Bayes機(jī)器訓(xùn)練算法,進(jìn)行機(jī)器學(xué)習(xí),更新個(gè)性化特征庫(kù);經(jīng)過(guò)Bayes機(jī)器學(xué)習(xí)后的增量更新包括:新增的特征項(xiàng)及其在垃圾短信和正常短信中出現(xiàn)的條件概率;客戶(hù)端反饋的刪除的特征項(xiàng);重新計(jì)算后的特征項(xiàng)及其在垃圾短信和正常短信中出現(xiàn)的條件概率。二是在短信中心維護(hù)黑白名單庫(kù),由人工更新。
2)短信內(nèi)容處理模塊。包括分詞處理模塊、特征提取模塊。分詞處理模塊對(duì)短信進(jìn)行高效率分詞;特征提取模塊則提取短信長(zhǎng)度特征、頻率特征、規(guī)則特征、文本特征等信息。
3)數(shù)據(jù)流聚類(lèi)模塊。通過(guò)數(shù)據(jù)流聚類(lèi)算法找出潛在的監(jiān)管短信,再根據(jù)這些短信找到潛在短信的短信發(fā)送者。
如圖1所示,系統(tǒng)對(duì)短信的分類(lèi)流程如下:
(1)短信中心收到短信后,將短信文本送入黑白名單庫(kù),依據(jù)黑白名單庫(kù)對(duì)短信進(jìn)行第一層過(guò)濾。未通過(guò)第一層過(guò)濾的垃圾短信被屏蔽;通過(guò)第一層過(guò)濾的短信送入數(shù)據(jù)流聚類(lèi)模塊。
(2)通過(guò)第一層過(guò)濾的短信送入數(shù)據(jù)流聚類(lèi)模塊后,應(yīng)用數(shù)據(jù)流聚類(lèi)算法進(jìn)行垃圾短信源頭的識(shí)別,并將識(shí)別結(jié)果存入黑白名單庫(kù),封鎖該號(hào)碼。
(3)沒(méi)有被封鎖的短信,由短信中心轉(zhuǎn)發(fā)短信給接收者。
(4)用戶(hù)接收到經(jīng)過(guò)短信后,根據(jù)終端上的分類(lèi)引擎和分類(lèi)特征庫(kù),調(diào)用分詞模塊和貝葉斯分類(lèi)模塊,將短信正確分類(lèi)(垃圾或非垃圾短信)。
(5)由用戶(hù)根據(jù)自己的需求自行決定短信分類(lèi)類(lèi)別。
(6)通過(guò)網(wǎng)絡(luò)向短信中心反饋短信的分類(lèi)類(lèi)別,信息發(fā)送者號(hào)碼,發(fā)送時(shí)間,發(fā)送者號(hào)碼等信息。
(8)短信接收者通過(guò)網(wǎng)絡(luò)定期從短信中心下載更新的個(gè)性化特征庫(kù),在下一條短信到達(dá)終端時(shí),采用更新后的特征庫(kù)進(jìn)行分類(lèi)判別。
(1)服務(wù)器端和客戶(hù)終端的短信文本分詞
要實(shí)現(xiàn)短信的監(jiān)管,首先必須理解短信的內(nèi)容。對(duì)于短信中文文本而言,要理解短信內(nèi)容,必須對(duì)中文文本進(jìn)行分詞[5]。分詞是將短信分割成一個(gè)個(gè)有意義的單詞。與英文等以詞為最小語(yǔ)言單位不同,中文的最小語(yǔ)言元素是字,字再構(gòu)成詞,而且詞之間沒(méi)有分隔標(biāo)記(比如空格),所以中文的分詞相對(duì)來(lái)說(shuō)復(fù)雜很多。
針對(duì)短信文本,在對(duì)其進(jìn)行分詞之前,首先進(jìn)行文本預(yù)處理,去除對(duì)分類(lèi)沒(méi)有用處的詞,主要是分詞后形成的單個(gè)的字,以及代詞、嘆詞、語(yǔ)氣助詞等。預(yù)處理可以通過(guò)查表(助詞表、代詞表)方式進(jìn)行。
系統(tǒng)分別在服務(wù)器端和客戶(hù)端進(jìn)行分詞?,F(xiàn)在的分詞算法[6-7]主要包括二類(lèi):一類(lèi)是機(jī)械式分詞法,一般以分詞詞典為依據(jù),通過(guò)文檔中的漢字串和詞表中的詞逐一匹配來(lái)完成詞的切分,另一類(lèi)是理解式分詞法,即利用漢語(yǔ)的語(yǔ)法知識(shí)和語(yǔ)義知識(shí)進(jìn)行分詞,需要建立分詞數(shù)據(jù)庫(kù)、知識(shí)庫(kù)和推理庫(kù)。由于理解式分詞法在語(yǔ)義分析和語(yǔ)法分析等方面遠(yuǎn)未成熟,因此現(xiàn)有分詞系統(tǒng)多采用機(jī)械式分詞法。
本系統(tǒng)采用中科院FreeICTCLAS分詞系統(tǒng)[8],該分詞系統(tǒng)為機(jī)械式分詞系統(tǒng),具有較高的分詞準(zhǔn)確度和分詞速度,且具有較高的靈活性,可以依據(jù)需要裁減分詞詞典??紤]到短信文本中所用的詞匯一般都為常用詞,且服務(wù)器端對(duì)短信處理實(shí)時(shí)性的要求,以及手機(jī)終端存儲(chǔ)和處理能力的限制,我們對(duì)分詞詞典進(jìn)行了精簡(jiǎn)和壓縮,減少了詞典規(guī)模,最終分詞詞典包含約4萬(wàn)條左右的詞條,占用存儲(chǔ)空間為2.5M左右,完全滿(mǎn)足服務(wù)器端和客戶(hù)終端的分詞需求。
(2)黑白名單庫(kù)和特征項(xiàng)條件概率表的維護(hù)更新
小流域是山區(qū)水源涵養(yǎng)和集水的基本單元。只有把小流域保護(hù)好、治理好,大流域的河道、水庫(kù)水質(zhì)、水量和生態(tài)才有基本保障。建設(shè)生態(tài)清潔小流域的最終目標(biāo),是促進(jìn)生態(tài)系統(tǒng)良性循環(huán),人與自然和諧相處,實(shí)現(xiàn)流域人口、資源、環(huán)境協(xié)調(diào)發(fā)展。
系統(tǒng)在服務(wù)器端維護(hù)黑白名單庫(kù),設(shè)置黑白名單過(guò)濾特征庫(kù)和關(guān)鍵詞庫(kù),由人工隨時(shí)更新。同時(shí),系統(tǒng)在數(shù)據(jù)流聚類(lèi)模塊,應(yīng)用數(shù)據(jù)流聚類(lèi)算法進(jìn)行垃圾短信源頭的識(shí)別,并將識(shí)別結(jié)果經(jīng)人工確認(rèn)后更新黑白名單庫(kù)。
再者,系統(tǒng)維護(hù)一個(gè)最多包含200項(xiàng)特征項(xiàng)的條件概率表。客戶(hù)終端通過(guò)Internet或3G無(wú)線(xiàn)網(wǎng)絡(luò)向服務(wù)器端傳輸反饋的個(gè)性化短信分類(lèi)信息,包括短信分類(lèi)類(lèi)別(垃圾或非垃圾短信)、信息發(fā)送者號(hào)碼、發(fā)送時(shí)間、接收者號(hào)碼等信息。服務(wù)器接收客戶(hù)終端反饋的短信分類(lèi)信息,應(yīng)用Bayes算法進(jìn)行增量學(xué)習(xí),收到用戶(hù)反饋的短信后自動(dòng)觸發(fā)機(jī)器訓(xùn)練算法,進(jìn)行機(jī)器學(xué)習(xí),更新或新增特征項(xiàng)及相應(yīng)的條件概率。
(3)貝葉斯分類(lèi)
貝葉斯分類(lèi)[9]是基于貝葉斯定理進(jìn)行的分類(lèi),該算法可以預(yù)測(cè)樣本屬于每類(lèi)成員的可能性,最后將樣本分到可能性最大的那個(gè)類(lèi)別中去。
貝葉斯分類(lèi)過(guò)程如下:
1)讀入訓(xùn)練樣本短信,并統(tǒng)計(jì)各類(lèi)短信數(shù)目;
2)讀入分詞詞典,對(duì)訓(xùn)練樣本短信進(jìn)行分詞處理,得到各詞條及對(duì)應(yīng)的文檔頻率(document frequency,DF)值。
3)根據(jù)特征向量選取方法,按DF值從大到小,各類(lèi)選前200個(gè)特征詞形成特征向量;
4)讀入訓(xùn)練樣本短信,對(duì)貝葉斯分類(lèi)器進(jìn)行訓(xùn)練;
5)讀入待分類(lèi)短信,用訓(xùn)練后的貝葉斯分類(lèi)器進(jìn)行識(shí)別,并給出分類(lèi)結(jié)果。
系統(tǒng)在短信中心端設(shè)置了二個(gè)貝葉斯分類(lèi)器:一個(gè)用于短信的實(shí)時(shí)分類(lèi),當(dāng)用戶(hù)短信到達(dá)短信中心,由服務(wù)器調(diào)用,對(duì)短信進(jìn)行分類(lèi)判斷;另外一個(gè)作為后臺(tái)服務(wù)程序,定期輪詢(xún)每個(gè)用戶(hù),根據(jù)用戶(hù)反饋的信息進(jìn)行訓(xùn)練學(xué)習(xí),并更新每個(gè)用戶(hù)的個(gè)性化特征庫(kù)。
系統(tǒng)在用戶(hù)終端上同樣啟用了貝葉斯分類(lèi)器,對(duì)到達(dá)用戶(hù)終端的短信進(jìn)行分類(lèi)判斷,然后提示用戶(hù)作出選擇判斷。
(4)基于數(shù)據(jù)流聚類(lèi)的短信源頭跟蹤
服務(wù)器端的數(shù)據(jù)流聚類(lèi)模塊根據(jù)客戶(hù)端反饋的信息和監(jiān)管短信發(fā)送者的特點(diǎn),識(shí)別出真正的短信發(fā)送者,該模塊的核心算法就是數(shù)據(jù)流聚類(lèi)算法。數(shù)據(jù)流聚類(lèi)是對(duì)元素集進(jìn)行分組,使得組內(nèi)元素盡量相似,組間元素盡量相異的數(shù)據(jù)處理方法。數(shù)據(jù)流聚類(lèi)研究的方向很多,如:針對(duì)基于劃分的k-中心聚類(lèi)問(wèn)題,Guha[10]在2000年首先提出基于k中心聚類(lèi)的smallspace算法,該算法使用一個(gè)迭代過(guò)程實(shí)現(xiàn)了在數(shù)據(jù)流環(huán)境下的 k-中心聚類(lèi);將傳統(tǒng)數(shù)據(jù)聚類(lèi)思想應(yīng)用到數(shù)據(jù)流聚類(lèi)中,Cao[11]等人提出了Denstream算法,用基于密度的方法進(jìn)行數(shù)據(jù)流聚類(lèi);針對(duì)多數(shù)據(jù)流的聚類(lèi)問(wèn)題,Beringer[12]等人提出了基于K-means的多數(shù)據(jù)流聚類(lèi)方法,能夠快速近似地計(jì)算數(shù)據(jù)流間的相似度,使數(shù)據(jù)流聚類(lèi)算法在各個(gè)領(lǐng)域得到廣泛應(yīng)用。
數(shù)據(jù)流聚類(lèi)算法可分為基于劃分[13],基于密度[14]和基于網(wǎng)格[15]等幾類(lèi),其中以基于劃分的居多。但這些方法都只適合處理數(shù)值型數(shù)據(jù),不適用于文本聚類(lèi),而短信一般表現(xiàn)為文本,因此必須采用適用于文本的數(shù)據(jù)流聚類(lèi)算法用于文本的聚類(lèi)。本系統(tǒng)應(yīng)用Guha提出的k-中心聚類(lèi)算法,找出潛在的被監(jiān)管短信,再根據(jù)這些短信找出潛在的短信發(fā)送者,實(shí)現(xiàn)短信源頭跟蹤。
系統(tǒng)在數(shù)據(jù)流聚類(lèi)模塊,應(yīng)用如上數(shù)據(jù)流聚類(lèi)算法進(jìn)行垃圾短信源頭的識(shí)別,并將識(shí)別結(jié)果經(jīng)人工確認(rèn)后更新黑白名單庫(kù)。
測(cè)試數(shù)據(jù)由某電信研究院提供,共20000條短信。經(jīng)人工標(biāo)注,垃圾短信共計(jì)1400條(色情類(lèi)205條、詐騙類(lèi)45條、廣告類(lèi)940條、謠言類(lèi)80條、公共安全類(lèi)130條),占所有用戶(hù)短信的7%;正常短信18600條,占所有用戶(hù)短信的93%。系統(tǒng)的軟硬件測(cè)試環(huán)境為:服務(wù)器為Intel Pentium4 CPU,3GHz主頻,4GB內(nèi)存,500GB硬盤(pán),Windows Server 2003操作系統(tǒng);用戶(hù)終端為dopodA8188型號(hào)手機(jī),該型號(hào)運(yùn)行Windows Mobile操作系統(tǒng),CPU為600MHz的AMD微處理器,帶有512M內(nèi)存。
表1 測(cè)試結(jié)果
實(shí)驗(yàn)中從客戶(hù)端收集到反饋的垃圾短信號(hào)碼匯報(bào)個(gè)數(shù)共計(jì)64個(gè),經(jīng)系統(tǒng)的數(shù)據(jù)流聚類(lèi)模塊自動(dòng)識(shí)別屬于垃圾短信發(fā)送者的號(hào)碼有53個(gè),經(jīng)人工確認(rèn)垃圾短信發(fā)送者號(hào)碼59個(gè),源頭跟蹤準(zhǔn)確率達(dá)到89.8%,這說(shuō)明數(shù)據(jù)流聚類(lèi)算法對(duì)識(shí)別垃圾發(fā)送者有較大幫助。
實(shí)驗(yàn)還對(duì)客戶(hù)端性能進(jìn)行了測(cè)試。表2給出了客戶(hù)端性能測(cè)試結(jié)果。從測(cè)試結(jié)果看,貝葉斯分類(lèi)時(shí)間很短,影響處理速度的是短信分詞算法。但整體來(lái)看,客戶(hù)端處理時(shí)間不超過(guò)2s,而且相對(duì)于當(dāng)前智能手機(jī)的內(nèi)存配置,客戶(hù)端所占用的內(nèi)存不超過(guò)10M,一般智能手機(jī)的運(yùn)算速度和內(nèi)存完全可以滿(mǎn)足性能要求。
表2 客戶(hù)端性能測(cè)試結(jié)果
本文描述了基于數(shù)據(jù)流聚類(lèi)的短信監(jiān)管系統(tǒng)的功能設(shè)計(jì)和關(guān)鍵技術(shù)分析,利用基于文本內(nèi)容的數(shù)據(jù)流聚類(lèi)算法,設(shè)計(jì)短信接收者和短信中心端互動(dòng)的二層監(jiān)管模型,實(shí)現(xiàn)短信的個(gè)性化監(jiān)管和源頭跟蹤。系統(tǒng)經(jīng)過(guò)實(shí)驗(yàn)測(cè)試,已經(jīng)在某通信部門(mén)進(jìn)行中小范圍的試用,取得了良好的效果。提高系統(tǒng)的性能以支持更多的并發(fā)短信用戶(hù),以及綜合考慮垃圾短信的特點(diǎn)以提高數(shù)據(jù)流聚類(lèi)精度和源頭跟蹤精度將是本文的后續(xù)研究工作。
[1]黃文良,陳純,羅云彬.一種高效垃圾短信過(guò)濾系統(tǒng)的實(shí)現(xiàn)[J].電信科學(xué),2008,24(5):61-67.
[2]易陽(yáng)峰.垃圾短信的監(jiān)控與原理實(shí)現(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].情報(bào)探索,2008(11):86-91.
[7]文庭孝.漢語(yǔ)自動(dòng)分詞研究進(jìn)展[J].圖書(shū)與情報(bào),2005(5):54-63.
[8]張華平.計(jì)算所漢語(yǔ)詞法分析系統(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ù)流的任意形狀聚類(lèi)算法[J].軟件學(xué)報(bào),2006,17(3):379-388.