北郵郭軍web搜索chapter5

1、Web 搜索搜索郭軍郭軍北京郵電大學(xué) 第第5 5章章 信息過濾信息過濾n基本方法基本方法n模型學(xué)習(xí)模型學(xué)習(xí)n垃圾郵件及垃圾短信過濾垃圾郵件及垃圾短信過濾n話題檢測與追蹤系統(tǒng)話題檢測與追蹤系統(tǒng)引言引言n信息過濾的本質(zhì)是“流環(huán)境”下的二元分類u流環(huán)境：過濾系統(tǒng)處于信息持續(xù)新生的環(huán)境之中，新的數(shù)據(jù)源源不斷地流經(jīng)過濾系統(tǒng)u二元分類：一類是需要篩選出來的，一類是系統(tǒng)不關(guān)心的 n以模式分類模式分類為技術(shù)核心，高效高精度地處理數(shù)據(jù)流IR被檢索的文檔相對穩(wěn)定 用戶查詢需求不同 IF信息資源動態(tài)變化 用戶需求相對固定IF的研究重點n分類器的選擇u針對特定的應(yīng)用環(huán)境選擇分類器模型u目前研究較多的是樸素Bayes模

2、型、向量相似度(模板匹配)模型、SVM、k-NN等n分類器的學(xué)習(xí)及優(yōu)化u生成式算法、區(qū)分式算法u計算效率，類別模型的增量學(xué)習(xí)和自動演進(jìn)，半監(jiān)督學(xué)習(xí)、特征降維技術(shù)基本方法基本方法n信息過濾系統(tǒng)中常用的分類器uBayes分類器u向量距離分類器uk近鄰分類器uSVMn系統(tǒng)性能評價Bayes分類器分類器nBayes分類器將分類問題看作統(tǒng)計決策問題，以最小錯誤率為目標(biāo)進(jìn)行分類u前提：事先獲得各個類別的似然函數(shù)，決策時利用Bayes公式計算給定樣本特征值條件下各類別的后驗概率n設(shè)隨機(jī)變量xRd, 各類別的似然函數(shù)為P(x|ci)，對于某確定樣本t, 根據(jù)Bayes公式：( ) ()()( )iiiP c

3、PcP cPttt分類方法n計算得到各個P(ci|t)后，將樣本t分到類別ck中，其中1argmax()jj mkP c t舉例：隨機(jī)選取100封郵件，進(jìn)行人工標(biāo)注，其中有30封垃圾郵件和70封非垃圾郵件，對于詞“培訓(xùn)”，垃圾郵件中有21封含有該詞，非垃圾郵件中有28封含有該詞，假定過濾系統(tǒng)只采用該詞判別是否為垃圾郵件，問若一封新郵件含有該詞，則過濾系統(tǒng)認(rèn)為該郵件是否是垃圾郵件？對于多個詞，如何判別？似然比Rln二元分類問題可以根據(jù)似然比Rl來決定t的歸屬 對數(shù)似然比：假設(shè)x的各維數(shù)據(jù)之間相互獨立； 樸素Bayes分類器 111222(| )( ) ( |)(| )() ( |)lP cP c

4、 PcRP cP c Pctttt111221( )(|)()(|)djjldjjP cP tcRP cP tc121211lnln( )ln()ln (|)ln (|)ddljjjjRP cP cP tcP tc向量距離分類器向量距離分類器n向量距離分類器可以看作是Bayes分類器的簡化，它用各類別數(shù)據(jù)的均值向量、方差向量、協(xié)方差矩陣等參數(shù)近似描述它們的分布特性，利用向量之間的各種距離進(jìn)行分類，常用的距離尺度有:21()dgjijjDt1|dcjijjDt1()()TmiiiDtt221() /dsjijijjDtk近鄰分類器近鄰分類器n也稱k-NN分類器(k-Nearest Neighbo

5、r)n最大特點是不需要訓(xùn)練類別模型，而是按某種合理的比例從各類別中抽取樣本，用所有抽出的樣本構(gòu)成分類器的總體特征樣本n對于一個給定的樣本t，首先按照某種距離測度找出與其最接近的k個樣本，然后根據(jù)這k個樣本所屬類別進(jìn)行投票SVMnSVM是一種以結(jié)構(gòu)風(fēng)險最小化為目標(biāo)的二元分類器，在尋找最優(yōu)分類超平面時不但要求將兩類數(shù)據(jù)隔離，而且要求兩類數(shù)據(jù)距超平面的平均距離最大n設(shè)線性可分?jǐn)?shù)據(jù)集為nD維空間中線性判別函數(shù)的一般形式為n分類超平面方程為1(,)niiiyDxdRx1, 1y ( )gbxw x0bw x系統(tǒng)性能評價系統(tǒng)性能評價n評價指標(biāo)主要包括分類器的精度和速度u速度取決于分類器算法的復(fù)雜程度，在實

6、際應(yīng)用中與計算機(jī)的硬件性能關(guān)系很大u精度通過與人工標(biāo)注結(jié)果(ground truth)進(jìn)行比較來計算n對于二元分類問題，常用的精度指標(biāo)有u準(zhǔn)確率u召回率uF-measureubreak-even點 精度指標(biāo)標(biāo)注標(biāo)注為為L類類標(biāo)注為標(biāo)注為非非L類類判別為判別為L類類ab判別為非判別為非L類類cd分類與標(biāo)注對應(yīng)關(guān)系的頻次分類與標(biāo)注對應(yīng)關(guān)系的頻次 aPabaRaci) 準(zhǔn)確率準(zhǔn)確率(Precision)表示所有被分類器分到類L的數(shù)據(jù)中正確的所占的比例ii) 召回率召回率(Recall)表示所有實際屬于L的數(shù)據(jù)被分類器分到L中的比例iii) 平衡點平衡點BEP(Break-even Point): P

7、和R值是互相影響的: P會隨著R的升高而降低，反之亦然。因此，為了更全面地反映分類器的性能，一種做法是選取P和R相等時的值來表征系統(tǒng)性能，這個值叫BEPiv) F值值一種把準(zhǔn)確率和召回率綜合考慮的評價方法，定義如下：22(1) P RFPR12 P RFPR模型學(xué)習(xí)模型學(xué)習(xí)n生成式學(xué)習(xí)u典型應(yīng)用：利用EM算法對GMM的參數(shù)進(jìn)行估計u共同特征：每個類模型只用本類的樣本進(jìn)行估計，估計的準(zhǔn)則是使模型產(chǎn)生訓(xùn)練樣本的可能性最大(最大似然)u早期的模型學(xué)習(xí)主要采用生成式算法n區(qū)分式學(xué)習(xí)u典型應(yīng)用: SVM的學(xué)習(xí)u共同特征: 由需要相互區(qū)分的各類樣本共同構(gòu)成一個模型，通過多類樣本的“角力”形成不偏不依的分類

8、面降維變換降維變換n需要進(jìn)行學(xué)習(xí)的降維變換是指變換核（基函數(shù)）隨被處理數(shù)據(jù)集變化以獲得最佳變換效果的變換(自適應(yīng)變換)u主成分分析PCA(Principal Component Analysis)u獨立成分分析ICA(Independent Component Analysis)u線性鑒別分析LDA(Linear Discriminative Analysis)u希爾伯特黃變換Hilbert-Huangu自適應(yīng)變換也存在生成式和區(qū)分式之分PCA dRxN1iixX11NxiiNx 11)NtxixixiN (x)(x 設(shè)隨機(jī)變量，存在一個樣本集，則其均值可估計如下：協(xié)方差矩陣可估計如下：xii

9、a1 ,.,dAaa()xtAyx 求解按降序排列的d個特征值和對應(yīng)的特征向量，并構(gòu)成矩陣稱為x的PCA變換(也稱K-L變換)，則式PCA的性質(zhì)的性質(zhì)yx tAAxyx1yd PCA變換后的變量y是零均值的隨機(jī)變量，其協(xié)方差矩陣為：由于A是列為的特征向量的正交矩陣，所以是對角陣且對角線元素為的特征值，即：由于y的非對角元素都是零，所以隨機(jī)變量y的各維之間是不相關(guān)的LDA nLDA的思想是找一個投影方向，使得投影后在低維空間里樣本的類間散度較大，類內(nèi)散度較小 x1x2xLDA的定義的定義(1/3)1cwiiSS()()itiiCSixxmxmdRx1()()ctbiiiinSmm mmm設(shè)Ci為

10、第i類樣本的集合，共有c類樣本，則樣本類內(nèi)散度矩陣定義為：其中，mi為第i類樣本的均值，樣本類間散度矩陣定義為：其中為樣本集的總體均值向量LDA的定義的定義(2/3)t Wyx:將d維的隨機(jī)變量x變換到c-1維11()() ()()ySSiccttwiibiiiiCinymymmm mm SW S WSW S Wttwwbb定義在變換空間中樣本的類內(nèi)和類間散度矩陣：容易證明LDA的定義的定義(3/3)定義如下的準(zhǔn)則函數(shù)：()argmaxargmaxTbbTwwJoptWWSW S WWW S WS(1,2,)biiwiic 1S wS w， -1wbS S1S S WWwb 121 ,cdia

11、g 容易證明，使J(.)最大化的變換矩陣W的列向量由下列等式中的最大特征值對應(yīng)的特征向量組成：這是一個廣義特征值問題，如果Sw是非奇異的，W的列向量就是由矩陣的特征向量組成其中LDA的奇異性的奇異性nLDA是信息過濾中數(shù)據(jù)降維的核心算法之一n在應(yīng)用中常遇到類內(nèi)分散度矩陣Sw奇異的問題u當(dāng)數(shù)據(jù)維數(shù)很高時，能夠獲得的樣本數(shù)常常相對不足，使得獨立的訓(xùn)練樣本數(shù)N小于數(shù)據(jù)維數(shù)d，而這將導(dǎo)致Sw為奇異矩陣u信息過濾所處理的文本、圖像、音頻等一般都是在高維數(shù)據(jù)空間中表達(dá)的u解決LDA奇異性問題時，常先用某種生成式算法對數(shù)據(jù)進(jìn)行降維LDA奇異性的解決奇異性的解決n 主要方法: u正則化正則化LDAuPCA+L

12、DAuPCA+NULL空間空間uLDA/QRuLDA/GSVD 正則化正則化LDA（RLDA）n一種簡單的解決Sw矩陣奇異的方法是利用正則化思想在Sw上加一個擾動量，數(shù)學(xué)表達(dá)為其中 0，I為一個單位矩陣 這種方法的主要問題在于擾動量的選取有難度。如果擾動量太小可能不足以解決奇異問題，太大又會使Sw內(nèi)包含的判決信息丟失wwSSIPCA+LDAn首先用PCA對數(shù)據(jù)降維，使Sw成為非奇異矩陣，然后再進(jìn)行LDAn將生成式變換與區(qū)分式變換結(jié)合nPCA變換使數(shù)據(jù)中的信息被 “忠實地”保留，同時數(shù)據(jù)維數(shù)得到了壓縮，以便消除使Sw奇異的條件n難點：沒有明確的理論指導(dǎo)PCA降維的維數(shù)選擇u如果PCA維數(shù)太低，會

13、丟失過多的鑒別信息u如果維數(shù)太高，相對來說訓(xùn)練樣本會仍顯不足，這樣即使能解決Sw的奇異問題，也難免會出現(xiàn)過擬合的現(xiàn)象LDA/QRn對Hb進(jìn)行QR分解，得到一個正交矩陣Q和一個上三角矩陣R，然后在Q張成的低維子空間內(nèi)進(jìn)行鑒別分析n算法分兩步完成：bd rRQbrcRR, TTbbwwSQ S QSQ S Q, bwSS第一步，對Hb進(jìn)行QR分解，Hb = QR的正交列張成了Hb的秩空間是上三角矩陣第二步，在上運用LDA然后定義:LDA/GSVD n通過廣義奇異值分解GSVD，用Hb和Hw代替Sb和Swn根據(jù)GSVD理論，正交矩陣YRc*c，ZRn*n，以及非奇異矩陣XRd*d滿足如下關(guān)系：因此有

14、, , TTbbTTwwY H X 0Z H X0IIDDOObwbwbwbw1(,)twbbrrrdiagD1(,)twbwrrrdiagD221iiTTbbww IX的列向量就是矩陣對Hb,Hw對應(yīng)的廣義奇異向量，并將其作為基于GSVD的鑒別特征子空間RDMnRDM的特點主要有兩方面u1）將LDA問題轉(zhuǎn)化為同時對角化類內(nèi)和類間散度矩陣問題u2）通過能量適應(yīng)準(zhǔn)則來近似估計 12, ,Twndiag SI0對類內(nèi)散度矩陣Sw進(jìn)行對角化，得：在對角矩陣上加上一個小的擾動量進(jìn)行正則化，即（）的選擇11*,()min( )miimnmiiJ mmE其中RDM將Sw的能量譜用作選擇的標(biāo)準(zhǔn)J(m)通過前

15、m個特征值在總能量譜中所占的比例來確定m的值半監(jiān)督學(xué)習(xí)半監(jiān)督學(xué)習(xí)n問題：樣本不足 / 標(biāo)注樣本不足u找到有效的方法，使得只需手工標(biāo)注少數(shù)數(shù)據(jù)，就能較準(zhǔn)確地對全部數(shù)據(jù)進(jìn)行自動標(biāo)注n三類算法u在聚類過程中利用已標(biāo)注的數(shù)據(jù)來引導(dǎo)聚類u在對標(biāo)注樣本進(jìn)行學(xué)習(xí)之后，首先處理那些有較高置信度的未標(biāo)注樣本，然后迭代地把這些估計加入到標(biāo)注樣本集中u將數(shù)據(jù)看作圖上的結(jié)點，將數(shù)據(jù)間的(已知的)相似性看作結(jié)點間的初始邊長(權(quán)重)，應(yīng)用圖的理論對數(shù)據(jù)進(jìn)行聚類半監(jiān)督學(xué)習(xí)的形式定義半監(jiān)督學(xué)習(xí)的形式定義1,lxx1 CiRy1,ll uxx標(biāo)注樣本集合L =標(biāo)注樣本的類別向量用yij = 1 and yiq = 0 (qj)

16、表示xi點屬于第j類，C為類別數(shù)用fi表示，fi是元素值為0或1的C維向量用Y表示已標(biāo)注樣本集的真實類別矩陣用F表示數(shù)據(jù)集的類別指示矩陣，其類別指示向量設(shè)未標(biāo)注樣本集合U = 半監(jiān)督學(xué)習(xí):在已知數(shù)據(jù)集L、U和Y的情況下估計F基于圖的算法基于圖的算法n在圖中估計樣本的類別函數(shù)f，使其滿足兩個條件：u1) 對于已標(biāo)注樣本，其真實類別和通過f得到的結(jié)果越接近越好u2) 對于整個樣本集，f 足夠平滑n這兩個條件可以通過正則化方法得到滿足，即在求解的過程中用先驗知識對求解過程加以約束，從而獲得有意義的解n類別估計函數(shù) f 一般由兩項組成，一項是損失函數(shù)，用來評價條件1的滿足度；另一項是正則化，保證條件2

17、得到滿足基于隨機(jī)場的半監(jiān)督學(xué)習(xí)基于隨機(jī)場的半監(jiān)督學(xué)習(xí) n首先在圖上定義一個連續(xù)的隨機(jī)場，然后根據(jù)能量函數(shù)最小化時調(diào)和函數(shù)的特性獲得聚類結(jié)果 2,1( ) ( )( )2iji jEwijfff()1( )EpeZffexp( )llZEdffYf基于相似點應(yīng)屬于相同類別，得到二次能量函數(shù)：式中W=wij是圖的權(quán)值矩陣，代表結(jié)點間的相似性通過已標(biāo)注數(shù)據(jù)，可以獲得部分f(i)的取值即，如果xiL ，則f(i)由yi確定另，利用Gauss隨機(jī)場賦予f一個概率分布其中為常數(shù)，Z為配分函數(shù)Diiijjw DW2,1( ) ( )( )2Tiji jEwijfffff1( )TpeZfff令D為一個對角矩

18、陣,，表示點i的度, 則定義由此，能量函數(shù)可以改寫為：Gauss隨機(jī)場可以改寫為：的定義:組合Laplace矩陣基于基于Gauss隨機(jī)場的學(xué)習(xí)隨機(jī)場的學(xué)習(xí)(1/2) 1( )( ) Dijj iiiiwjffllluuluuWWWWW111()()uuuuuulluuulluuull fDWW ffIPP f上式中的含義與圖中的平滑概念是一致的 (f(i)取周圍點的均值)將權(quán)重矩陣W寫成分4塊的分塊矩陣調(diào)和函數(shù)的解是在滿足fl = yl的條件下使 f = 0其中P為圖的轉(zhuǎn)移概率矩陣，P=D-1W在能量函數(shù)達(dá)到最小的條件下，未標(biāo)注樣本點滿足基于基于Gauss隨機(jī)場的學(xué)習(xí)隨機(jī)場的學(xué)習(xí)(2/2) 基

19、于局部一致和全局平滑的學(xué)習(xí)基于局部一致和全局平滑的學(xué)習(xí)222 ()()0 ijikjjkiijeifNNwotherwisexxxxxx2,11ijiji jiijjwffDD用一個加權(quán)圖來描述數(shù)據(jù)集，在滿足與標(biāo)注信息一致的條件下使樣本集的類別平滑變化定義圖G = V,W，wij的計算方法如下根據(jù)相似度越大類別越可能一致的原則，定義目標(biāo)函數(shù)是數(shù)據(jù)集中每個點與其近鄰點間的差異度，越小越好優(yōu)化目標(biāo)函數(shù)優(yōu)化目標(biāo)函數(shù)A Fb1,TTTTlA00yy11,TTTTTllnfFfff2,11min. .ijiji jiijjwstYDDA Fbff聚類結(jié)果必須滿足已標(biāo)注的真實類別信息將這些信息表示為等式：

20、A為Cn的系數(shù)矩陣，yi為已標(biāo)注樣本i的真實類別向量(行向量)F為nC的類別指示矩陣b是CC的對角矩陣，bjj等于標(biāo)注樣本中屬于第j類的樣本個數(shù)最優(yōu)的類別估計結(jié)果就是當(dāng)xiL時，fi =yi因此，半監(jiān)督學(xué)習(xí)問題就轉(zhuǎn)化為了如下的最優(yōu)化問題優(yōu)化問題的求解優(yōu)化問題的求解1122CID WDmin. .TtracestYF CFAFb令矩陣，上述優(yōu)化問題可轉(zhuǎn)化為(, )()TLtraceFF CFAFb(, )0(, )0TLL FFCFAFAFb將F取0/1值的條件進(jìn)行松弛，使其取實數(shù)值將優(yōu)化問題變?yōu)闃?biāo)準(zhǔn)的二次規(guī)劃問題，定義Lagrange函數(shù)令可求得類別指示向量F的最優(yōu)實數(shù)解為TFR b111()

21、TRACAAC其中演進(jìn)式學(xué)習(xí)演進(jìn)式學(xué)習(xí)n演進(jìn)式學(xué)習(xí)演進(jìn)式學(xué)習(xí)分類模型隨著信息環(huán)境的變化而自動演進(jìn)u隨機(jī)過程(而不是隨機(jī)變量)動態(tài)描述數(shù)據(jù)分布，使分類模型隨著分布的變化而自動演進(jìn)u分類模型永遠(yuǎn)是動態(tài)的，系統(tǒng)通過應(yīng)用環(huán)境中的樣本對模型不斷進(jìn)行修正u不再試圖估計靜態(tài)的“總體分布”，而只考慮當(dāng)前時刻隨機(jī)變量的分布如何從上一時刻的分布演進(jìn)出來u演進(jìn)學(xué)習(xí)通過小樣本完成，因而可以提高學(xué)習(xí)效率演進(jìn)式學(xué)習(xí)的流程演進(jìn)式學(xué)習(xí)的流程n不斷地從應(yīng)用環(huán)境中獲取新樣本進(jìn)行模型的演進(jìn)u增加自動采集新樣本、接收識別(分類)模塊的樣本反饋、以及演進(jìn)式模型學(xué)習(xí)和更新分類模型等過程n類別標(biāo)注樣本庫中存放從應(yīng)用環(huán)境中自動采集的數(shù)據(jù)樣本

22、和分類器識別后反饋的樣本，作為模型演進(jìn)的數(shù)據(jù)源模型的演進(jìn)方法模型的演進(jìn)方法u假設(shè)S(ti)是隨機(jī)過程X(t)在ti時刻的一個學(xué)習(xí)樣本集相鄰時刻學(xué)習(xí)樣本集的關(guān)系是: S(ti) = S(ti-1) E(ti) A(ti)即，S(ti)可以通過從S(ti-1) 中剔除樣本集E(ti)后添加樣本集A(ti)的方法獲得u模型演進(jìn)的關(guān)鍵問題：u獲得A(ti)和E(ti)的方法u利用A(ti)和E(ti)對ti-1時刻的模型進(jìn)行演進(jìn)，獲得ti時刻的模型|A(ti)|和|E(ti)|的變化規(guī)律n在t0時刻用N0個樣本初始化，演進(jìn)初期|A(ti)| |E(ti)|n隨著系統(tǒng)的成熟，|A(ti)|和| E(t)

23、|逐步接近ntc是系統(tǒng)性能達(dá)到設(shè)計要求進(jìn)入常態(tài)的時刻，交換的訓(xùn)練樣本數(shù)為dnd的大小與演進(jìn)周期(ti - ti-1)成正比n在演進(jìn)周期(ti - ti-1)比較短的情況下，|A(ti)|和|E(ti)|都遠(yuǎn)小于|S(ti-1)|。q性能指標(biāo)影響因素：q系統(tǒng)進(jìn)入常態(tài)的時刻qdA(ti)和E(ti)的獲得nti時刻以隨機(jī)的方式從采集的樣本和反饋的識別樣本中選出一個集合N(ti)，從中選出|A(ti)|個識別得分最低的樣本組成A(ti)，在S(ti-1)中選出|E(ti)|個識別得分最低的樣本組成E(ti)n|S(ti)| = | S(ti-1)| + |A(ti)| - |E(ti)|n物理意義是

24、通過更換邊緣樣本來移動學(xué)習(xí)樣本集的類中心。 模型演進(jìn)模型演進(jìn) n對于生成式模型，采用ML準(zhǔn)則下的增量式EM算法n對于區(qū)分式模型；可采用基于自適應(yīng)特征分布變化的adaboost算法n需要注意的是，由于自動采集和識別反饋的樣本的類別標(biāo)注是有錯誤率的，因此在沒有人工校對的情況下S(ti)是含噪的垃圾郵件及垃圾短信過濾垃圾郵件及垃圾短信過濾n 垃圾郵件垃圾郵件(spam)過濾系統(tǒng)過濾系統(tǒng)uTREC Spam評測的技術(shù)是基于內(nèi)容識別的，這不同于目前在市場上普遍應(yīng)用的技術(shù)，如黑白名單過濾、基于地址分析及跟蹤的啟發(fā)式過濾等u文本分類器是TREC Spam技術(shù)的核心，統(tǒng)計學(xué)習(xí)算法是研究的重點過濾器的性能過濾器

25、的性能n兩個指標(biāo)：uHam錯分百分比錯分百分比hm%：被錯分到Spam目錄中的ham占ham總數(shù)的百分比uSpam錯分百分比錯分百分比sm%：被錯分到Ham目錄中的spam占spam總數(shù)的百分比n系統(tǒng)根據(jù)郵件為spam的可能性進(jìn)行過濾u若可能性大于閾值t，則將其投入spam目錄，否則投入ham目錄u提高t有利于降低hm%，但會升高sm%；反之，降低t有利于降低sm%，但會升高h(yuǎn)m%u給出每封郵件的score，可以通過改變t值獲得sm%相對hm%的函數(shù)關(guān)系，這種函數(shù)關(guān)系的圖形表示就是著名的ROC(Receiver Operating Characteristic)曲線Spam過濾器過濾器n最常見

26、的是SVM和樸素BayesnBrat 05創(chuàng)新性地將動態(tài)數(shù)據(jù)壓縮中的局部匹配預(yù)測PPM(Prediction by Partial Matching)用于Spam過濾nPPM是一種自適應(yīng)概率編碼壓縮技術(shù)u每處理被壓縮數(shù)據(jù)的一個符號，PPM的概率模型P(x|context)都會隨之更新u每處理完一個符號，都會得到一個新的P(x|context)u系統(tǒng)根據(jù)P(x|context)獲得一個熵編碼方案u編碼方案隨著context的演變而自適應(yīng)調(diào)整PPMn通過訓(xùn)練數(shù)據(jù)獲得PPM的兩個概率模型P(x|context-spam)和P(x|context-ham)n與常見的方法的差別：uPPM假設(shè)信源產(chǎn)生符號

27、的過程符合k階Markov過程uPPM模型會隨著處理的進(jìn)行而自動演進(jìn)，這恰好應(yīng)對了Spam特征的演進(jìn)性n在PPM中，通常約定用-1階模式指出系統(tǒng)的字符集A，并且假定所有字符以相同的概率1/|A|出現(xiàn)n未出現(xiàn)過的轉(zhuǎn)移模式用Esc表示例例:“abracadabra”的的2階階PPM模型模型 垃圾短信的過濾垃圾短信的過濾n短信的基本特點：u長度短，最長不能超過140個ASCII字符或70個漢字u不完整(省略、指代、簡化等)、不規(guī)范(用詞另類、語法隨意等) n短信分類不統(tǒng)一u運營商：訂閱（由SP提供的）/ 手寫（由手機(jī)用戶手工輸入的）u用戶：私人 / 廣告u安全部門：合法 / 非法 u發(fā)送形式：SPM

28、U / U U / U MUu發(fā)送內(nèi)容：普通短信 / 垃圾短信 / 異常短信 u細(xì)分類：聊天短信、問候短信、祝福短信、娛樂短信、新聞短信、理財短信 基于正則表達(dá)式的分類基于正則表達(dá)式的分類n正則表達(dá)式(Regular Expression) u由數(shù)學(xué)家Stephen Kleene于1956年提出 u在許多腳本語言中得到支持，如Perl、PHP、JavaScript， 已經(jīng)被國際組織ISO和Open Group標(biāo)準(zhǔn)化u正則表達(dá)式由模式修正符、元字符、子模式、量詞和斷言等元素組成，通過一系列模式對字符串進(jìn)行匹配u快速地分析大量的文本以找到特定的字符模式，提取、編輯、替換或刪除字符串基于統(tǒng)計的分類基

29、于統(tǒng)計的分類n特征抽取主要采用VSM和n-gram模型u構(gòu)造一個詞的集合來很好覆蓋短信中出現(xiàn)的詞匯u分詞u詞集合的選擇是短信特征抽取的關(guān)鍵u簡便的方法是以字為單位進(jìn)行處理n基于單字特征的Bayes分類器1212argmax(|,.,)argmax() (,.,|)MAPini Linii LHP Cw wwP C P w wwCargmax()(|)NBikii LkHP CP wCTDT系統(tǒng)系統(tǒng)nTopic: 特指在特定時間特定地點發(fā)生的事件，而非一般意義的事件類u例：“汶川地震”VS“地震”n一個話題或事件，會有多個相關(guān)的報道(story)nTDT的任務(wù)u報道分割t將一個連續(xù)的文本流劃分為

30、一個個報道u事件檢測t回顧式檢測 / 在線式檢測u事件跟蹤t將新產(chǎn)生的報道與系統(tǒng)已知的事件聯(lián)系起來t給定目標(biāo)事件的條件下判斷每個后續(xù)報道是否在討論這個目標(biāo)事件報道分割報道分割n算法的評價u一方面是直接評價其對報道邊界定位的準(zhǔn)確性u另一方面是間接評價其對事件追蹤的支持能力n基于HMM進(jìn)行報道分割u基于話題轉(zhuǎn)換的概率進(jìn)行分割n基于局部語境分析LCA進(jìn)行報道分割u將句子轉(zhuǎn)換為LCA詞，對其索引后判斷報道邊界 n將視頻分割應(yīng)用于報道分割 基于LCA方法的關(guān)鍵要素n基于內(nèi)容的特征: 一對語言模型，用于幫助判斷話題是否大幅改變u在線自適應(yīng)語言模型 VS 離線靜態(tài)語言模型n表示局部語境的語言學(xué)和結(jié)構(gòu)特征的詞匯特征u使用各個詞的位置偏移量對詞的特征進(jìn)行編碼u以更精細(xì)的粒度對與分割邊界相關(guān)的詞進(jìn)行判斷 n增量式地選擇最佳的詞匯特征的學(xué)習(xí)算法，并將詞匯特征與語言模型相結(jié)合形成統(tǒng)一的統(tǒng)計模型u增量式地構(gòu)建一個越來越詳細(xì)的模型，對分割邊界設(shè)置的正確性進(jìn)行概率估計事件檢測事件檢測n在新聞流中標(biāo)識出新的或是以前沒有標(biāo)識的事件n本質(zhì)：無監(jiān)督的學(xué)習(xí)任務(wù)n模式：回顧式/