《模式識別原理與應(yīng)用》課件第11章

第11章文本分類11.1文本分類技術(shù)11.2垃圾郵件識別技術(shù)11.3網(wǎng)頁分類技術(shù)習(xí)題11.1文本分類技術(shù)

11.1.1文本分類流程文本分類的流程圖如圖11-1所示,它包含中文分詞、特征提取、向量表示、分類器等四大部分。首先,收集大量的包含各種信息的文本語料,形成訓(xùn)練數(shù)據(jù)集,并對其進(jìn)行人工分類;其次,對訓(xùn)練數(shù)據(jù)進(jìn)行中文分詞(對英文文本不需要分詞)、特征提取、向量表示,形成特征向量;再次,選擇合適的分類器模型,對訓(xùn)練數(shù)據(jù)的特征向量進(jìn)行訓(xùn)練,得到有效的分類器;最后,利用訓(xùn)練好的分類器對待分類的文本進(jìn)行分類。圖11-1文本分類流程11.1.2文本預(yù)處理

1.中文分詞中文文本是由字連接在一起組成的。在文本處理中,中文文本需要先分割成一個(gè)個(gè)有意義的詞,這就是中文分詞。對于英文,就是識別出空格(多個(gè)空格可以看成是一個(gè)空格),并把它作為詞的分隔符?，F(xiàn)有的分詞算法分為三大類:基于字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計(jì)的分詞方法。

(1)基于字符串匹配的分詞方法又叫做機(jī)械分詞方法,它是按照一定的策略將待分析的漢字串與一個(gè)“充分大的”機(jī)器詞典中的詞條進(jìn)行匹配,若在詞典中找到某個(gè)字符串,則匹配成功(識別出一個(gè)詞)。常用的幾種機(jī)械分詞方法有正向最大匹配、逆向最大匹配、最少切分(使每一句中切出的詞數(shù)最小)等。

(2)基于理解的分詞方法是利用漢語的語法知識和語義知識及心理學(xué)知識進(jìn)行分詞,需要建立分詞數(shù)據(jù)庫、知識庫和推理機(jī)。由于此方法需要使用大量的語言知識和信息,目前這種系統(tǒng)還處在試驗(yàn)階段。

(3)基于統(tǒng)計(jì)的分詞方法是根據(jù)字與字相鄰共現(xiàn)的頻率能夠較好地反映成詞的可信度這一點(diǎn),對語料中相鄰共現(xiàn)的各個(gè)字的組合的頻度進(jìn)行統(tǒng)計(jì),計(jì)算它們的互現(xiàn)信息。這種方法只需對語料中的字組頻度進(jìn)行統(tǒng)計(jì),不需要切分詞典,因而又叫做無詞典分詞法或統(tǒng)計(jì)取詞方法。這種方法增加了空間復(fù)雜度。衡量自動分詞技術(shù)的主要指標(biāo)是切分精度和切分速度。針對信息檢索與分類/聚類系統(tǒng)來說,分詞技術(shù)的主要問題是確定詞的顆粒度大小、對專用術(shù)語的識別、判別詞與詞之間的語義關(guān)聯(lián)、對未登錄詞的處理等?？梢韵炔捎米畲笃ヅ?、最短路徑、概率統(tǒng)計(jì)等方法,得到一個(gè)詞語粗分結(jié)果,然后再對粗分結(jié)果進(jìn)行歧義詞排除、未登錄詞識別等處理。

2.文本表示模型文本表示模型主要研究選擇計(jì)算機(jī)能夠識別的模型,用其來完整的表示文本內(nèi)容。目前,具有代表性的文本表示模型有布爾模型(BooleanModel)、向量空間模型(VectorSpaceModel,VSM)、概率模型(ProbabilisticModel)等。向量空間模型目前已被成功地應(yīng)用于著名的文本檢索系統(tǒng)SMART中。一些研究表明向量空間模型在處理大規(guī)模文本方面有很強(qiáng)的優(yōu)勢,它逐漸成為最簡便、最高效的文本表示模型之一。向量空間模型的基本概念如下:

(1)文本。本書泛指一般的文本或者文本中的段落、句群或者句子,通常指的是一篇文章。盡管文本可以是多媒體對象,但是在本書的討論中,只認(rèn)為是文本對象。

(2)特征項(xiàng)。文本的內(nèi)容由一些特征項(xiàng)來表達(dá),一般由文本所含有的基本語言單位(字、詞、詞組或短語等)來表示,即文本可以表示為D(t1,t2,…,tn),其中,tk表示各個(gè)特征項(xiàng),每個(gè)特征項(xiàng)表示文本的一個(gè)維度。

(3)特征項(xiàng)權(quán)重。在一個(gè)文本中,每個(gè)特征項(xiàng)都被賦予一個(gè)權(quán)重wk,以表示這個(gè)特征項(xiàng)在該文本中的重要程度。這樣文本就表示為(11-1)其中,特征項(xiàng)tk的權(quán)重為wk,1≤k≤n。

(4)向量空間模型。給定一個(gè)文本D=D(t1,w1;t2,w2;…;tn,wn),由于tk在文本中既可以重復(fù)出現(xiàn)又應(yīng)該有先后次序的關(guān)系,分析起來有一定的難度,為了簡化分析,可以暫不考慮tk在文本中的先后次序,但要求tk互異(即沒有重復(fù))。這時(shí)可以把t1,

t2,

…,

tn

看成一個(gè)n維的坐標(biāo)系,而w1,w2，…,wn為相應(yīng)的坐標(biāo)值,因此,一個(gè)文本就表示為n維空間的一個(gè)向量,稱D=D(w1,w2,…,wn)為文本D的向量表示或向量空間模型。

(5)相似度度量。兩個(gè)文本D1和D2之間的相關(guān)程度常常用它們的相似度Sim(D1,D2)來度量。在向量空間模型下,可以借助向量之間的某種距離來表示文本間的相似度。常用的是采用向量之間的內(nèi)積來計(jì)算相似度,定義式如下:(11-2)或者采用夾角余弦計(jì)算,定義式如下:(11-3)夾角余弦公式忽略了各個(gè)向量的絕對長度,著重從形狀考慮它們之間的關(guān)系,當(dāng)兩個(gè)向量方向相近時(shí),夾角余弦值較大,反之則較小。本節(jié)所涉及的文本之間的相似度均采用向量之間的夾角余弦來計(jì)算。向量空間模型如圖11-2所示。圖11-2向量空間模型向量空間模型的最大優(yōu)點(diǎn)在于把文本內(nèi)容簡化為特征與其權(quán)重的向量表示,把對文本內(nèi)容的處理簡化成向量空間的向量運(yùn)算,使得問題的難度大大降低了。向量空間模型表達(dá)效果的優(yōu)劣,直接依賴于特征項(xiàng)的選擇和特征加權(quán)方式。選取特征項(xiàng)主要有以下兩條原則:

(1)應(yīng)當(dāng)選擇包含文本信息多的,對文本的表現(xiàn)能力較強(qiáng)的語言單位作為特征項(xiàng)。特征項(xiàng)可以是文本中基本的語言單位,例如單字、詞、詞組或者短語等多個(gè)層次,也可以是更高層次的單元,例如概念等。層次越高,包含的文本信息也越多,能更好地描述文本內(nèi)容,同時(shí)存在的問題就是它可能需要復(fù)雜的附加處理,比如,對漢語特征,如果選擇詞作為特征項(xiàng),則首先需要先進(jìn)行中文分詞處理,而中文分詞是一個(gè)比較復(fù)雜的處理過程。

(2)特征項(xiàng)的提取過程應(yīng)當(dāng)比較容易,時(shí)間和空間開銷都不應(yīng)當(dāng)大。對特征項(xiàng)的選擇問題,許多學(xué)者做了研究。在文本分類領(lǐng)域,通過對使用單詞、詞組、聚類單詞和聚類詞組作為特征項(xiàng)所做的實(shí)驗(yàn)比較分析,結(jié)果表明單詞特征項(xiàng)作為文本特征項(xiàng),不僅方法簡單,而且具有較高的分類精確度。如何用選擇的特征項(xiàng)來更好地描述文本內(nèi)容？向量空間模型中用特征的權(quán)重來表示一個(gè)文本的內(nèi)涵,或者稱為內(nèi)容,即D=D(w1,w2,…,wn),w1,w2,…,wn為相應(yīng)特征t1,t2,…,tn在n維向量空間的坐標(biāo)值。文本描述的權(quán)重計(jì)算的準(zhǔn)則是要最大限度地區(qū)分不同的文檔。目前大多數(shù)特征權(quán)重的計(jì)算方法是基于下面兩個(gè)準(zhǔn)則或者假設(shè):

(1)一個(gè)特征在文本中出現(xiàn)的范圍越廣,說明該特征區(qū)分文本之間區(qū)別的能力越低。

(2)一個(gè)特征在一個(gè)特定文本中出現(xiàn)的頻率越高,說明該特征區(qū)分這個(gè)文本之間區(qū)別的能力越強(qiáng)。特征項(xiàng)權(quán)重的計(jì)算一般分為兩種:一種是由專家或者用戶根據(jù)自己的經(jīng)驗(yàn)與所掌握的領(lǐng)域知識,人為地賦權(quán)值,這種辦法隨意性較大,很難適用于大規(guī)模真實(shí)文本的處理;另一種是運(yùn)用統(tǒng)計(jì)的方法,也就是用文本的統(tǒng)計(jì)信息(如詞頻等)來計(jì)算項(xiàng)的權(quán)重。運(yùn)用統(tǒng)計(jì)的方法有布爾頻率法和TF×IDF算法。布爾頻率法的規(guī)則是:如果特征項(xiàng)tk在文本Di中出現(xiàn),就記權(quán)值wik為1,否則,wik為0。這種方法無法體現(xiàn)特征在文本中的作用程度。

TF×IDF(TermsFrequency×InverseDocumentFrequency)算法利用詞條在文檔中出現(xiàn)的頻率TF和每個(gè)特征項(xiàng)在整個(gè)數(shù)據(jù)集文檔的反向文檔頻率IDF來計(jì)算權(quán)值。用tfik(TermFrequency)表示特征項(xiàng)tk在文本Di中的出現(xiàn)次數(shù),idfk(InverseDocumentFrequency)表示特征項(xiàng)tk的反向文檔頻數(shù),TF×IDF公式定義為(11-4)式中:tfik是一個(gè)局部統(tǒng)計(jì)量,它在不同文本中有不同的值;反向文檔頻率idfk是一個(gè)全局統(tǒng)計(jì)量,反映了一個(gè)給定的詞條在整個(gè)文檔集中的分布情況。IDF的原始定義為(11-5)其中:N表示整個(gè)集合中包括的文檔數(shù);nk是集合中出現(xiàn)特征項(xiàng)tk的文檔數(shù)。可以看出,包含給定詞條的文檔數(shù)越少,IDF的值就越大;如果文檔集中的每篇文檔都包含給定的詞條,則idf的值等于0。在實(shí)際的應(yīng)用中,為了避免0值的出現(xiàn),將式(11-5)進(jìn)行改進(jìn),即(11-6)其中,c∈(0,1)為常數(shù),目前較為常用的公式為(11-7)如果考慮到文本長度對權(quán)值的影響,還應(yīng)該對特征項(xiàng)權(quán)值公式做歸一化處理,將各權(quán)值規(guī)范到區(qū)間［0,1］,即(11-8)

TF×IDF算法是一種經(jīng)驗(yàn)公式,并沒有堅(jiān)實(shí)的理論基礎(chǔ)。但是,多年的實(shí)踐表明,式(11-8)是文本處理中的一個(gè)有效工具,在信息檢索等諸多領(lǐng)域都得到了廣泛應(yīng)用。

3.特征空間降維采用向量空間模型進(jìn)行文本描述時(shí),每一個(gè)不同的特征都作為特征空間中的一維,每一個(gè)文本都是空間中的一個(gè)向量,這種描述方法簡單而且直接,但同時(shí)也使得特征空間變得高維,致使文本分類的性能急劇下降。為了解決這個(gè)問題，必須降維,目前采用的技術(shù)主要有特征選擇和特征提取。特征提取方法主要是采用代數(shù)的方法進(jìn)行特征空間降維,主要方法有主成分分析(PrincipalComponentAnalysis)、奇異值分解(SingularValueDecomposition)等。特征選擇是構(gòu)造一個(gè)特征評估函數(shù),根據(jù)特征評估函數(shù)對各個(gè)特征進(jìn)行獨(dú)立的評估,然后按照評估值的大小排序,最后選擇評估值大于某個(gè)設(shè)定閾值的特征作為最優(yōu)特征。文本分類中,通常使用的特征評估函數(shù)有信息增益(InformationGain)、期望交叉熵(ExpectedCrossEntropy)、文檔頻率(DocumentFrequency)、文本證據(jù)權(quán)(theWeightofEvidenceforText)、開方擬合檢驗(yàn)(χ2－statistic)、優(yōu)勢率(OddRatio)、互信息(MutualInformation)等。每一種特征選擇方法對應(yīng)一種特征評估函數(shù)。用c1,c2,…,ck表示文本的k個(gè)類;t表示某個(gè)特征;P(t)表示特征t出現(xiàn)的概率;表示特征t不出現(xiàn)的概率;P(cj)表示第j類的出現(xiàn)概率;P(cj,t)表示特征t與類別cj共同出現(xiàn)的聯(lián)合概率;表示特征t不與類別cj共同出現(xiàn)的聯(lián)合概率。一般采用兩種概率估算方式,分別是布爾概率估算方式和詞頻概率估算方式。采用布爾概率估算方式,可得:

(1)P(t)是訓(xùn)練文本集合中出現(xiàn)特征t的文本個(gè)數(shù)與總的文本個(gè)數(shù)的比值;

(2)是訓(xùn)練文本集合中不出現(xiàn)特征t的文本個(gè)數(shù)與總的文本個(gè)數(shù)的比值;

(3)P(cj)是第cj類的文本總數(shù)與訓(xùn)練文本總數(shù)的比值;

(4)P(cj,t)是屬于cj類且含有特征t的文本總數(shù)與訓(xùn)練文本總數(shù)的比值;

(5)是屬于cj類且不含特征t的文本個(gè)數(shù)與訓(xùn)練文本總數(shù)的比值。采用詞頻概率估算方式,可得:

(1)P(t)是訓(xùn)練文本集合中出現(xiàn)特征t的個(gè)數(shù)與總的特征個(gè)數(shù)的比值;

(2)是訓(xùn)練文本集合出現(xiàn)的不包含特征t的個(gè)數(shù)與總的特征個(gè)數(shù)的比值;

(3)P(cj)是第cj類文本的特征總數(shù)與所有特征總數(shù)的比值;

(4)P(cj,t)是在cj類文本中出現(xiàn)特征t的個(gè)數(shù)與總的特征個(gè)數(shù)的比值;

(5)是在cj類文本出現(xiàn)的不包含特征t的特征個(gè)數(shù)與總的特征個(gè)數(shù)的比值。下面定義各種特征評估函數(shù)。

1)文檔頻率閾值法文檔頻率閾值法是利用特征的文檔頻率進(jìn)行特征選擇。特征t的文檔頻率是指包含這個(gè)特征的訓(xùn)練文本的總數(shù),定義式如下:(11-9)其中,t(cj)為cj類中包含特征t的訓(xùn)練文本的個(gè)數(shù)。運(yùn)用文檔頻率閾值法進(jìn)行特征選擇時(shí),首先計(jì)算各個(gè)特征的文檔頻率,然后將文檔頻率大于某個(gè)設(shè)定閾值的特征選為最優(yōu)特征。文檔頻率閾值法基于這樣一種假設(shè):對于一個(gè)類而言,出現(xiàn)頻率小的特征是沒有任何意義的,刪除它們對分類結(jié)果不會造成不利的影響。這種假設(shè)顯然有其局限性,在一些信息檢索的研究中,頻率小的詞可能具有很大的類別區(qū)分度。文檔頻率閾值法是最簡單的一種文本特征選擇方法,它的最大優(yōu)勢就是速度快,時(shí)間復(fù)雜度和文本數(shù)目成線性關(guān)系,所以非常適合應(yīng)用到大規(guī)模文本特征集合的特征選擇,同時(shí)它也是最有效的文本特征選擇方法之一。

2)期望交叉熵法期望交叉熵法是利用期望交叉熵進(jìn)行特征選擇。期望交叉熵考慮了特征t出現(xiàn)的概率,同時(shí)也考慮了特征t與類別之間的關(guān)系,定義式如下:(11-10)

3)信息增益法信息增益法是利用信息增益進(jìn)行特征選擇。信息增益法經(jīng)常被應(yīng)用于機(jī)器學(xué)習(xí)領(lǐng)域。信息增益法是通過一個(gè)特征t是否出現(xiàn)在文本中來推算該特征對整個(gè)分類所提供的信息量,定義為特征t在文本出現(xiàn)前后的信息熵之差,定義式如下:(11-11)它與期望交叉熵的區(qū)別是考慮了特征不出現(xiàn)在同一類別文本中對類別的影響,因?yàn)橛袝r(shí)特征不出現(xiàn)也可能對判斷文本類別有貢獻(xiàn)。

4)文本證據(jù)權(quán)法文本證據(jù)權(quán)法是利用文本證據(jù)權(quán)進(jìn)行特征選擇。文本證據(jù)權(quán)比較了類cj出現(xiàn)的概率與在給定特征t下類cj出現(xiàn)的條件概率之間的差別,定義式如下:(11-12)如果特征和類別之間為強(qiáng)相關(guān)(P(cj|t)值大),且類別出現(xiàn)的概率小,則說明此特征類別區(qū)分度大,計(jì)算出來的文本證據(jù)權(quán)值大,可選擇該特征作為最優(yōu)特征。如果特征和類別之間為弱相關(guān)(P(cj|t)值小),且類別出現(xiàn)的概率大,則說明此特征類別區(qū)分度小,計(jì)算出來的文本證據(jù)權(quán)值小,不會被選為最優(yōu)特征。

5)開方擬合檢驗(yàn)法開方擬合檢驗(yàn)法是利用開方擬合檢驗(yàn)進(jìn)行特征選擇。開方擬合檢驗(yàn)是衡量類cj和特征t之間的獨(dú)立性的缺乏程度,或者稱為統(tǒng)計(jì)相關(guān)性。開方擬合檢驗(yàn)值越大,說明類cj和特征t之間的獨(dú)立性越小,相關(guān)性越大,特征t攜帶的類cj的信息也就越多。特殊的情況,當(dāng)特征t與類cj之間獨(dú)立時(shí),開方擬合檢驗(yàn)值為0,此時(shí)特征t不包含任何與類別cj有關(guān)的信息,定義式如下:(11-13)其中,A、B、C、D表示文本的個(gè)數(shù),如表11-1所示。式(11-13)計(jì)算的是類cj和特征t的開方擬合檢驗(yàn)值,特征t對于整個(gè)訓(xùn)練文本的開方擬合檢驗(yàn)值是其相對于所有類的開方擬合檢驗(yàn)值的綜合,定義式如下:(11-14)表11-1開方擬合檢驗(yàn)法中A、B、C、D的含義

類cj的文本個(gè)數(shù)非cj的文本個(gè)數(shù)特征t出現(xiàn)AB特征t不出現(xiàn)CD

6)互信息法互信息法是利用互信息進(jìn)行特征選擇。特征t對類別cj的互信息為二者的互信息量,定義式如下:(11-15)互信息衡量特征t和類cj之間獨(dú)立的統(tǒng)計(jì)關(guān)系,MI的值越大,說明特征t和類cj共同出現(xiàn)的程度越大。(11-16)

7)優(yōu)勢率法優(yōu)勢率法是利用優(yōu)勢率進(jìn)行特征選擇,它只能用于二分類問題,定義式如下:(11-17)11.1.3分類器文本分類器的任務(wù)是在給定的分類體系前提下,根據(jù)文本的內(nèi)容自動確定文本關(guān)聯(lián)的類別。文本分類是一個(gè)映射的過程,它將未標(biāo)明類別的文本映射到已有的類別中。該映射可以是一對一映射,也可以是一對多的映射。文本分類的映射規(guī)則是系統(tǒng)根據(jù)已經(jīng)掌握的若干分類技術(shù),總結(jié)出分類的規(guī)律性而建立的類別公式和判別規(guī)則。這樣,用戶不但能夠方便地瀏覽文檔,而且可以通過限制搜索范圍來使文檔的查找更為容易。利用文本分類技術(shù)可以對大量文檔進(jìn)行快速、有效的自動分類。

1.K-近鄰分類器

KNN算法的思想很簡單:給定一篇待分類的文檔,系統(tǒng)在訓(xùn)練集中找到與之距離最近的文檔,這K個(gè)文檔中的大多數(shù)文檔所在的類別就是待分類文檔的類別。假設(shè)有一個(gè)任意的輸入文檔,系統(tǒng)在訓(xùn)練文檔中對它最近鄰居排序,并采用排列在最前面的K個(gè)文檔來預(yù)測輸入文檔的類。鄰居文檔與待分類的新文檔間的相似值被當(dāng)作類的權(quán)重,K個(gè)最近鄰居的類權(quán)重之和被用于類的排序。

2.

SVM分類器文本學(xué)習(xí)以文檔或文本字段為學(xué)習(xí)對象,通過大量文檔集的訓(xùn)練,系統(tǒng)掌握文檔的類別特征,獲得識別新文檔的規(guī)則和模型,從而為分類器提供分類的知識。文本學(xué)習(xí)是學(xué)習(xí)分類器內(nèi)含的一種機(jī)制。分類器被輸入一組文檔,學(xué)習(xí)機(jī)制根據(jù)文檔信息內(nèi)容來進(jìn)行監(jiān)督,學(xué)習(xí)形成的分類器就可用于識別新文檔。最典型的方法就是SVM分類器。

3.貝葉斯分類器

超文本的結(jié)構(gòu)是半自動化的,且多數(shù)頁面文本內(nèi)容短小,如果用平常的文本分類器去分類,則效果明顯不好。目前對超文本的分類,主要涉及頁面的純文本分類、超文本結(jié)構(gòu)信息分類和協(xié)調(diào)分類等。純文本分類方法沒有用超文本頁面中的任何結(jié)構(gòu)信息,只是將此頁面當(dāng)作一個(gè)普通文本看待,用一般的文本分類方法進(jìn)行分類。超文本頁面中含有大量有用的結(jié)構(gòu)信息,這些信息可能包括該頁面標(biāo)題、重要的子標(biāo)題等重要內(nèi)容。如果將這些結(jié)構(gòu)信息用于分類,一方面可以提高分類精度,另一方面可以減少計(jì)算量。最典型的綜合協(xié)調(diào)法就是樸素貝葉斯分類器法。貝葉斯分類器的原理是計(jì)算文本d屬于某個(gè)類別cj的條件概率P(cj|d),進(jìn)而將文本d分到概率最大的類別中去。計(jì)算P(cj|d)時(shí),利用貝葉斯公式:(11-18)其中:P(cj)是類的先驗(yàn)概率;P(d|cj)是類的條件概率。對同一篇文本,P(d)是一定的,在分類的過程中可以忽略。如果設(shè)文本d可以表示為特征集合(t1,t2,…,tn),n為特征個(gè)數(shù),貝葉斯分類器中假定各特征項(xiàng)之間是相互獨(dú)立,則有(11-19)式中,P(cj)和P(ti|cj)都利用訓(xùn)練集加以估計(jì)。假定Nj表示訓(xùn)練樣本集中屬于第cj類的文本總數(shù),N表示訓(xùn)練樣本集的文本總數(shù),則先驗(yàn)概率P(cj)為(j=1,2,…,k)(11-20)(i=1,2,…,n;j=1,2,…,k)(11-21)最大后驗(yàn)概率準(zhǔn)則如下:如果則d屬于cj類。11.2垃圾郵件識別技術(shù)電子郵件由于其快捷、方便、高效的特點(diǎn),已經(jīng)成為現(xiàn)代通信方式的重要組成部分。然而隨著人們?nèi)找鎻V泛地使用電子郵件,令人厭煩的不請自來的垃圾郵件日益泛濫。2006年1月，CCNNIC(中國互聯(lián)網(wǎng)絡(luò)信息中心)發(fā)布的《第十六次中國互聯(lián)網(wǎng)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》顯示,中國網(wǎng)民平均每周收到郵件16.8封,其中六成以上是垃圾郵件。什么是垃圾郵件？至今沒有一個(gè)統(tǒng)一定義,中國互聯(lián)網(wǎng)協(xié)會定義的垃圾郵件是指包括下述屬性的電子郵件:

(1)收件人事先沒有提出要求或者不同意接收的廣告、電子刊物以及各種形式的宣傳郵件;

(2)收件人無法拒收的電子郵件;

(3)隱藏發(fā)件人身份、地址、標(biāo)題等信息的電子郵件;

(4)含有虛假的信息源、發(fā)件人、路由等信息的電子郵件。垃圾郵件的存在干擾了人們正常的生活,浪費(fèi)了用戶的時(shí)間和金錢。通常人們判斷一封垃圾郵件所需要時(shí)間大約為10s,用戶每天都需要花費(fèi)一段時(shí)間來處理垃圾郵件,對于全球用戶來講被浪費(fèi)的時(shí)間是不可估計(jì)的,同時(shí)有調(diào)查表明下載垃圾郵件所需要的上網(wǎng)費(fèi)和電話費(fèi),每年大約被浪費(fèi)掉100億美元以上。垃圾郵件占用了大量傳輸、存儲和運(yùn)算資源,影響了網(wǎng)絡(luò)的正常運(yùn)行,給相關(guān)企業(yè)帶來了巨大的經(jīng)濟(jì)損失。業(yè)內(nèi)人事分析:一旦垃圾郵件占到了網(wǎng)絡(luò)總數(shù)據(jù)流量的1/3以上,將會造成巨大的存儲需求,甚至對信息安全系統(tǒng)的有效性造成威脅。AOL、雅虎、Hotmail等Internet服務(wù)提供商(ISP)所處理的郵件,垃圾郵件已超過50%,僅僅考慮和處理這些垃圾郵件就會花費(fèi)大量的人力物力。據(jù)估計(jì),全世界企業(yè)大約用80到100億美元來處理垃圾郵件。此外,垃圾郵件的存在給社會帶來了不穩(wěn)定因素。有些人利用電子郵件方便快捷、價(jià)格低廉以及開放無國界性的特點(diǎn)傳播反動、黃色、病毒等不良信息,給網(wǎng)絡(luò)安全以及社會的發(fā)展和穩(wěn)定帶來很大的危害。要解決垃圾郵件泛濫問題必須綜合法律、技術(shù)等多種手段。許多國家和地區(qū)都制定了反垃圾郵件的法律和法規(guī),例如我國制定的《網(wǎng)絡(luò)安全法》、《電子商務(wù)法》等法律,這些法律法規(guī)都對減少垃圾郵件的數(shù)量起到了一定的作用。但是Internet是一個(gè)開放的全球范圍的網(wǎng)絡(luò),法律法規(guī)的作用受到諸多不確定因素的影響，因此,目前大多采用技術(shù)手段來防治垃圾郵件,統(tǒng)稱為反垃圾郵件技術(shù)。垃圾郵件過濾技術(shù)是其主流技術(shù),下面將詳細(xì)介紹該技術(shù)的相關(guān)內(nèi)容。11.2.1服務(wù)器與客戶端過濾電子郵件的協(xié)議和內(nèi)容格式由RFC(RequestforComments)的幾個(gè)文檔規(guī)定。RFC821規(guī)定了SMTP(簡單傳輸協(xié)議),定義了發(fā)送郵件協(xié)議。RFC822規(guī)定了郵件文本從主機(jī)傳送到主機(jī)的格式化定義。RFC1725規(guī)定了POP3(郵局協(xié)議版本3),定義了從POP3服務(wù)器收取郵件的機(jī)制。MIME(多用途互聯(lián)網(wǎng)郵件擴(kuò)展協(xié)議)是RFC822的擴(kuò)展,支持多種非文本文件的傳送,目前幾乎所有的電子郵件系統(tǒng)都支持此標(biāo)準(zhǔn)。Internet電子郵件系統(tǒng)概念模型如圖11-3所示。圖11-3

Internet電子郵件系統(tǒng)概念模型下面解釋圖11-3中的幾個(gè)概念。

MUA(MailUserAgent):郵件用戶代理,為客戶端程序。MUA是用戶用來發(fā)送和接收電子郵件的客戶端程序,負(fù)責(zé)為用戶提供處理電子郵件的界面,例如Outlook。MUA將郵件系統(tǒng)的復(fù)雜性與用戶隔離開。

MTA(MailTransferAgent):郵件傳輸代理,為服務(wù)器端程序。MTA負(fù)責(zé)從客戶端或者另一個(gè)MTA接收電子郵件,并判斷電子郵件的目的地是本地地址還是非本地地址。如果為本地地址,則將電子郵件交給本地MDA,由本地MDA負(fù)責(zé)將電子郵件傳遞到郵箱。如果為非本地地址,則將電子郵件傳給遠(yuǎn)程的MDA,由遠(yuǎn)程MDA將郵件傳給下一個(gè)MTA。MDA(MailDeliveryAgent):郵件投遞代理。MDA是MTA的附帶服務(wù)器程序,用于將電子郵件投遞到目的郵箱或者投遞給遠(yuǎn)程MTA。

MRA(MailRetrievalAgent):郵件獲取代理,為服務(wù)器端程序,用于MUA從郵件服務(wù)器上獲取電子郵件。根據(jù)圖11-3,給出電子郵件的傳遞過程如下:

(1)電子郵件發(fā)送方利用MUA編輯電子郵件。

(2)通過與MTA進(jìn)行SMTP會話,將電子郵件交給MTA。

(3)MTA根據(jù)電子郵件地址判斷電子郵件的目的地是否為本地。如果目的地是本地郵箱,則調(diào)用本地MDA,將電子郵件發(fā)送到本地郵箱;如果不是本地郵箱,則調(diào)用遠(yuǎn)程MDA，通過SMTP會話,將電子郵件傳遞給下一個(gè)MTA。

(4)接收到新電子郵件的MTA重復(fù)(3),直至電子郵件投遞到目的郵箱中。

(5)郵箱用戶可以通過駐留在服務(wù)器上的MUA查看郵箱接收的電子郵件,也可以使用遠(yuǎn)程計(jì)算機(jī)上的MUA通過POP協(xié)議或者IMAP協(xié)議獲取查看電子郵件。根據(jù)上述電子郵件傳遞過程,垃圾郵件過濾可以在三個(gè)不同位置進(jìn)行:

(1)用戶端過濾——MUA過濾,在客戶端過濾。

(2)郵件上傳階段過濾——MTA過濾,即在MUA與MTA會話過程中對郵件進(jìn)行檢測,判斷是否為垃圾郵件，并進(jìn)行過濾。

(3)郵件遞送階段過濾——MDA從MTA中接收郵件,在本地或者遠(yuǎn)程投遞時(shí)進(jìn)行檢查,判斷是否為垃圾郵件，并進(jìn)行過濾。垃圾郵件過濾技術(shù)一般都同時(shí)適用于客戶端和服務(wù)器端的垃圾郵件過濾,技術(shù)的應(yīng)用研究在推進(jìn)和發(fā)展階段主要集中于三個(gè)方面:

(1)利用IP或域名的“黑白名單”進(jìn)行的郵件限制或過濾,例如利用黑名單過濾、用戶自定義郵件白通道等。

(2)基于垃圾郵件的特征分析、規(guī)則提取的規(guī)則匹配過濾方法,例如關(guān)鍵詞過濾技術(shù)、信頭分析、群發(fā)過濾等。(3)利用文本分類和統(tǒng)計(jì)算法進(jìn)行垃圾郵件的檢測。比較有代表的是貝葉斯過濾器,它是貝葉斯文本分類方法應(yīng)用于垃圾郵件過濾中的結(jié)果,過濾器通過對郵件文本內(nèi)容的學(xué)習(xí)來實(shí)現(xiàn)垃圾郵件的自動過濾。11.2.2黑白名單過濾技術(shù)

利用“黑白名單”過濾技術(shù)進(jìn)行郵件限制或過濾,是一種最傳統(tǒng)的方式。通過黑名單技術(shù)對垃圾郵件進(jìn)行屏蔽,通過白名單技術(shù)對允許的郵件進(jìn)行放行。黑白名單內(nèi)容可以是電子郵件地址、IP地址或域名等。網(wǎng)站、運(yùn)營商、企業(yè)和個(gè)人都可以參與制定和維護(hù)名單,攔截已知垃圾郵件發(fā)送者的所有郵件。黑名單一般由比較權(quán)威的組織所提供,例如中國反垃圾郵件網(wǎng)站(http://)建立了自己的黑名單,為大眾提供服務(wù)。黑白名單技術(shù)的優(yōu)點(diǎn)是過濾簡單、速度快。該技術(shù)的缺點(diǎn)首先是無法區(qū)分垃圾郵件和合法郵件,只是機(jī)械地進(jìn)行過濾,過濾效果差。例如,如果垃圾郵件發(fā)送者改變了地址,黑名單又沒有跟上,就可能使垃圾郵件“漏網(wǎng)”;如果自己的朋友改變了郵箱地址,而自己沒有將其加入白名單中,那就可能收不到他的信,阻止掉了合法郵件是用戶不能忍受的。其次,Internet是一個(gè)跨國家、無邊界的網(wǎng)絡(luò),對于黑名單技術(shù)而言要想起到好的效果,需要各個(gè)國家之間的合作,才能確保垃圾郵件制造者無處隱匿。11.2.3規(guī)則匹配過濾技術(shù)規(guī)則匹配過濾技術(shù)是根據(jù)垃圾郵件的某些特征,首先人工設(shè)定一些規(guī)則,通過這些規(guī)則來描述垃圾郵件,當(dāng)郵件符合這些規(guī)則中的一條或幾條時(shí),則判定其為垃圾郵件。下面主要介紹規(guī)則匹配過濾技術(shù)中的群發(fā)過濾和關(guān)鍵詞過濾。

1.群發(fā)過濾

垃圾郵件發(fā)送者為了降低發(fā)送垃圾郵件的成本,大多使用群發(fā)功能,使得郵件服務(wù)器在一段較短時(shí)間內(nèi)收到來自同一個(gè)地址的大量郵件,或者在一段較短時(shí)間內(nèi)收到不同地址發(fā)送過來的大量內(nèi)容相同的郵件,這些郵件都被認(rèn)為是垃圾郵件而進(jìn)行過濾。缺點(diǎn)是當(dāng)一個(gè)用戶大批量發(fā)送正常郵件時(shí),正常郵件很可能被誤判為垃圾郵件。

2.關(guān)鍵詞過濾通常的做法是創(chuàng)建一些簡單或復(fù)雜的,能夠反映垃圾郵件特征的單詞表來識別和處理垃圾郵件。比如某些關(guān)鍵詞大量出現(xiàn)在垃圾郵件中,如一些病毒的郵件標(biāo)題(如test)、一些商業(yè)廣告的標(biāo)題(如“free”、“贈送”、“免費(fèi)”等)。它的基礎(chǔ)是必須創(chuàng)建一個(gè)龐大的過濾關(guān)鍵詞列表。這種技術(shù)缺陷很明顯,過濾的能力同關(guān)鍵詞有明顯聯(lián)系。當(dāng)然,系統(tǒng)采用這種技術(shù)來處理郵件時(shí)消耗的系統(tǒng)資源會比較多,并且,一般躲避關(guān)鍵詞的技術(shù)(如拆詞、組詞)就很容易繞過過濾,例如,我們知道帶有標(biāo)題“Free”的信件是垃圾郵件,但是這種技術(shù)可能會因?yàn)樽帜钢g有空格而放過它,所以誤判率較高。11.2.4垃圾郵件內(nèi)容過濾技術(shù)

由于郵件中很大一部分信息集中于郵件的文本中,因此可以通過對文本的分析來識別郵件是否為垃圾郵件,目前采用的識別技術(shù)主要是將文本分類技術(shù)引入到垃圾郵件過濾中,將郵件自動分類為垃圾郵件和合法郵件。垃圾郵件內(nèi)容過濾的實(shí)質(zhì)是二分類問題,主要包括訓(xùn)練過程和過濾過程,其基本框圖如圖11-4所示。圖11-4垃圾郵件內(nèi)容過濾的基本框圖

(1)輸入/輸出。訓(xùn)練過程輸入為由專家分好類別的垃圾郵件訓(xùn)練語料庫,輸出為構(gòu)造的垃圾郵件過濾器。過濾過程輸入為待過濾的垃圾郵件,輸出為待過濾郵件的類別(合法郵件類或垃圾郵件類)。

(2)預(yù)處理。預(yù)處理主要通過對垃圾郵件訓(xùn)練語料庫文本進(jìn)行掃描,從而采集到郵件原始特征集合,為郵件文本表示做好準(zhǔn)備,使郵件文本信息能夠表示成計(jì)算機(jī)可以處理的結(jié)構(gòu)化模型。

(3)特征提取。特征提取主要是采用特征空間降維技術(shù)來選取最優(yōu)特征集合(即能夠盡量完整描述文本信息的盡可能少的特征集合),然后對最優(yōu)特征集合中的每個(gè)特征進(jìn)行適當(dāng)?shù)募訖?quán),利用處理好的最優(yōu)特征將郵件文本表示成計(jì)算機(jī)可以處理的結(jié)構(gòu)化模型,特征提取是垃圾郵件過濾中重要的一步,是正確過濾的基礎(chǔ)。

(4)訓(xùn)練與過濾。訓(xùn)練主要是各種垃圾郵件過濾方法的實(shí)現(xiàn)。過濾主要是利用加權(quán)后的最優(yōu)特征形成待過濾郵件文本向量,然后應(yīng)用訓(xùn)練結(jié)果和相應(yīng)的過濾方法,對待過濾郵件進(jìn)行過濾。此外,構(gòu)建實(shí)際垃圾郵件過濾系統(tǒng)時(shí)還應(yīng)包括反饋學(xué)習(xí)過程。因?yàn)槔]件的內(nèi)容、形式以及用戶需求在不斷變化。垃圾郵件過濾系統(tǒng)需要通過反饋學(xué)習(xí)來自動更新垃圾郵件過濾器。在垃圾郵件過濾領(lǐng)域中,有人研究了英文郵件文本特征項(xiàng)的選擇,對單詞、詞組等特征進(jìn)行測試,結(jié)果顯示使用單詞和詞組作為特征項(xiàng)下的垃圾郵件過濾效果相差不大。由于單詞特征項(xiàng)的提取只需要根據(jù)英文單詞之間的空格或符號進(jìn)行,比詞組的提取更容易,一般直接采用單詞作為郵件文本的特征項(xiàng)。在垃圾郵件過濾中,特征選擇大都采用信息增益法。垃圾郵件內(nèi)容過濾技術(shù)不像規(guī)則匹配技術(shù),不需要預(yù)先設(shè)定規(guī)則,不需要分析郵件句法或內(nèi)容的含義,而是采用某種文本分類算法對已知的垃圾郵件樣本進(jìn)行學(xué)習(xí),提取垃圾郵件的特征,構(gòu)造過濾器,然后運(yùn)用此過濾器,對待過濾的新的郵件,機(jī)器自動判斷過濾垃圾郵件。目前,垃圾郵件內(nèi)容過濾技術(shù)的研究主要集中在將已有的文本分類方法應(yīng)用于垃圾郵件過濾中。應(yīng)用于垃圾郵件過濾中的文本分類方法(又稱垃圾郵件過濾方法)主要有判別分析中的K近鄰判別法(KNN方法)、貝葉斯判別法、支持向量機(jī)分類法等。從實(shí)際應(yīng)用來看,基于貝葉斯分類方法的垃圾郵件過濾技術(shù)已被263、Yahoo等多家郵件服務(wù)商采用。此外,市場上還出現(xiàn)了一些郵件客戶端工具,幫助用戶定義和訓(xùn)練個(gè)性化的垃圾郵件過濾器,例如,國內(nèi)最著名的Internet電子郵件客戶端軟件Foxmail5.0,其反垃圾郵件功能中就采用了該技術(shù)。11.3網(wǎng)頁分類技術(shù)11.3.1網(wǎng)頁分類流程網(wǎng)頁分類是先將網(wǎng)頁轉(zhuǎn)化為文檔形式,去除網(wǎng)頁中的相關(guān)噪聲,提取其中的純文本信息;再利用文本分類技術(shù)對純文本信息進(jìn)行分類,從而實(shí)現(xiàn)網(wǎng)頁的分類。網(wǎng)頁分類的流程框圖如圖11-5所示,其中,在文本分類流程框圖(圖11-1)中添加了“網(wǎng)頁文本內(nèi)容提取”。圖11-5網(wǎng)頁分類流程在瀏覽Internet的網(wǎng)頁時(shí),會發(fā)現(xiàn)它們通常包含兩部分內(nèi)容:一部分內(nèi)容體現(xiàn)的是網(wǎng)頁的主題信息,比如一張新聞網(wǎng)頁中的新聞部分,將這部分內(nèi)容稱為“主題”內(nèi)容;另一部分則是與主題內(nèi)容無關(guān)的導(dǎo)航條、廣告信息、版權(quán)信息以及調(diào)查問卷等內(nèi)容,稱之為“噪聲”內(nèi)容。根據(jù)噪聲數(shù)據(jù)的粒度,一般將其分為兩大類:

(1)全局噪聲(GlobalNoise):這種噪聲具有極大的粒度,通常不小于一個(gè)網(wǎng)頁,一般包括數(shù)據(jù)鏡像站點(diǎn)、合法/不合法的冗余網(wǎng)頁等。

(2)局部噪聲(LocalNoise):指網(wǎng)頁內(nèi)的噪聲,這些數(shù)據(jù)通常伴隨著網(wǎng)頁的主要內(nèi)容,例如廣告、導(dǎo)航信息等。在網(wǎng)頁分類中,一般所獲得的網(wǎng)頁要首先經(jīng)過全局噪聲的去除,也就是對網(wǎng)頁數(shù)據(jù)進(jìn)行去空和去重處理;然后再進(jìn)行局部噪聲的去除。而通常網(wǎng)頁文本內(nèi)容提取所關(guān)心的是局部噪聲的有效去除和文本內(nèi)容的提取,因此下面主要分析局部噪聲的去除。噪聲內(nèi)容通常分布在主題內(nèi)容周圍,有時(shí)也夾雜在主題內(nèi)容中間,但它們并無內(nèi)容相關(guān)性。從圖11-6可以看出一個(gè)新聞網(wǎng)頁一般由下面幾個(gè)部分組成:①最上方的導(dǎo)航鏈接,例如“首頁”、“娛樂”;②“無處不在”的廣告鏈接;③檢索界面;④版權(quán)信息;⑤頁面主題區(qū)。圖11-6頁面的信息示意圖需要特別注意的一個(gè)現(xiàn)象是:現(xiàn)在許多站點(diǎn)的收入都來自于廣告,而且隨著因特網(wǎng)的普及,這個(gè)現(xiàn)象會越來越明顯。設(shè)計(jì)者在設(shè)計(jì)廣告時(shí)考慮的首要問題是如何吸引用戶的“眼球”。因?yàn)閳D像相比文字具有更強(qiáng)的表現(xiàn)力,所以通常網(wǎng)頁中的廣告都是以圖像的形式嵌入到網(wǎng)頁中。如果用戶對廣告感興趣,則點(diǎn)擊圖片就可以進(jìn)入廣告站點(diǎn)。實(shí)際上,人們對廣告信息不感興趣,而且圖像占據(jù)了網(wǎng)頁下載的大多數(shù)時(shí)間。網(wǎng)頁文本內(nèi)容提取,也就是對網(wǎng)頁中的文本內(nèi)容進(jìn)行提取,主要的面向?qū)ο笫切侣勑再|(zhì)的網(wǎng)頁。這部分工作主要包括對網(wǎng)頁的書寫和構(gòu)造方式進(jìn)行分析,研究網(wǎng)頁標(biāo)記語言的寫法、網(wǎng)頁的組織結(jié)構(gòu)及特點(diǎn),去除網(wǎng)頁中含有的大量噪聲,如廣告、版權(quán)、導(dǎo)航鏈接等相關(guān)內(nèi)容,將網(wǎng)頁中的新聞主題和內(nèi)容以txt的格式進(jìn)行存儲。在這部分的處理過程中,由于當(dāng)前網(wǎng)頁構(gòu)造語言的多樣性,如XML、HTML、VRML以及WML等多種語言書寫的網(wǎng)頁,其風(fēng)格各不相同;另外,還有很多個(gè)人風(fēng)格的網(wǎng)頁書寫,其風(fēng)格可謂各式各樣,這些多風(fēng)格的網(wǎng)頁書寫格式對網(wǎng)頁內(nèi)容的提取造成了一定的困難。這里介紹一種基于向量空間模型的網(wǎng)頁噪聲凈化方法。11.3.2基于向量空間模型的網(wǎng)頁噪聲凈化

在視覺上,一張網(wǎng)頁的頁面可以劃分為若干個(gè)區(qū)域,一個(gè)區(qū)域稱為一個(gè)內(nèi)容塊。這些內(nèi)容塊中,有的包含主題內(nèi)容,而有的則包含噪聲內(nèi)容。通常,一個(gè)內(nèi)容塊中的內(nèi)容是緊密相關(guān)的,這就意味著我們可以以內(nèi)容塊為單位對網(wǎng)頁中的內(nèi)容進(jìn)行取舍。基于這樣的分析,網(wǎng)頁噪聲凈化過程就是保留網(wǎng)頁中包含主題內(nèi)容的內(nèi)容塊而去掉包含噪聲內(nèi)容的內(nèi)容塊。因此,網(wǎng)頁凈化的過程可以分為兩個(gè)步驟:網(wǎng)頁內(nèi)容結(jié)構(gòu)的表示和網(wǎng)頁內(nèi)容塊的取舍?；谙蛄靠臻g模型的網(wǎng)頁噪聲凈化的基本思想如下:

(1)將一篇HTML網(wǎng)頁解析為文檔樹(DocumentObjectModel,DOM)結(jié)構(gòu),并根據(jù)〈table〉與〈/table〉標(biāo)簽為最小單位將網(wǎng)頁內(nèi)容劃分為不同的內(nèi)容塊。

(2)根據(jù)規(guī)則挑選出網(wǎng)頁的主題內(nèi)容塊并利用向量空間模型來表示。

(3)根據(jù)內(nèi)容相似性比較技術(shù)，判斷其余內(nèi)容塊是否為噪聲內(nèi)容塊。

1.文檔樹

根據(jù)網(wǎng)頁的結(jié)構(gòu)分析可以看出,網(wǎng)頁是用標(biāo)識語言來書寫的,其中定義了一套標(biāo)簽來刻畫網(wǎng)頁顯示時(shí)的界面。因此,對于HTML網(wǎng)頁最常用的結(jié)構(gòu)表示方法就是構(gòu)造網(wǎng)頁相對應(yīng)的標(biāo)簽樹。現(xiàn)有標(biāo)簽樹的構(gòu)造方法有很多,文檔樹就是一個(gè)常用標(biāo)簽樹構(gòu)造工具,它可以將網(wǎng)頁中的標(biāo)簽按照嵌套關(guān)系整理成一棵樹狀結(jié)構(gòu)。針對網(wǎng)頁凈化的特殊需求,我們首先對HTML規(guī)范中的標(biāo)簽按照功能進(jìn)行分類,進(jìn)而提出更加適合網(wǎng)頁凈化的標(biāo)簽樹的構(gòu)造方法。依據(jù)標(biāo)簽的作用可以將HTML的標(biāo)簽分為兩類:規(guī)劃網(wǎng)頁布局的標(biāo)簽和描述顯示特點(diǎn)的標(biāo)簽。規(guī)劃網(wǎng)頁布局的標(biāo)簽:如上所述,在視覺上,網(wǎng)頁是由若干內(nèi)容塊組成的,而內(nèi)容塊是由特定的標(biāo)簽規(guī)劃出的(稱之為容器標(biāo)簽),常用的容器標(biāo)簽有〈table〉、〈tr〉、