北郵郭軍web搜索chapter5

Web搜索

郭軍

北京郵電大學(xué)

第5章信息過濾基本方法模型學(xué)習(xí)垃圾郵件及垃圾短信過濾話題檢測與追蹤系統(tǒng)引言信息過濾的本質(zhì)是“流環(huán)境”下的二元分類流環(huán)境：過濾系統(tǒng)處于信息持續(xù)新生的環(huán)境之中，新的數(shù)據(jù)源源不斷地流經(jīng)過濾系統(tǒng)二元分類：一類是需要篩選出來的，一類是系統(tǒng)不關(guān)心的以模式分類為技術(shù)核心，高效高精度地處理數(shù)據(jù)流IR被檢索的文檔相對穩(wěn)定用戶查詢需求不同IF信息資源動態(tài)變化用戶需求相對固定IF的研究重點分類器的選擇針對特定的應(yīng)用環(huán)境選擇分類器模型目前研究較多的是樸素Bayes模型、向量相似度(模板匹配)模型、SVM、k-NN等分類器的學(xué)習(xí)及優(yōu)化生成式算法、區(qū)分式算法計算效率，類別模型的增量學(xué)習(xí)和自動演進，半監(jiān)督學(xué)習(xí)、特征降維技術(shù)基本方法信息過濾系統(tǒng)中常用的分類器Bayes分類器向量距離分類器k近鄰分類器SVM系統(tǒng)性能評價Bayes分類器Bayes分類器將分類問題看作統(tǒng)計決策問題，以最小錯誤率為目標(biāo)進行分類前提：事先獲得各個類別的似然函數(shù)，決策時利用Bayes公式計算給定樣本特征值條件下各類別的后驗概率設(shè)隨機變量x∈Rd,各類別的似然函數(shù)為P(x|ci)，對于某確定樣本t,根據(jù)Bayes公式：分類方法計算得到各個P(ci|t)后，將樣本t分到類別ck中，其中舉例：隨機選取100封郵件，進行人工標(biāo)注，其中有30封垃圾郵件和70封非垃圾郵件，對于詞“培訓(xùn)”，垃圾郵件中有21封含有該詞，非垃圾郵件中有28封含有該詞，假定過濾系統(tǒng)只采用該詞判別是否為垃圾郵件，問若一封新郵件含有該詞，則過濾系統(tǒng)認為該郵件是否是垃圾郵件？對于多個詞，如何判別？似然比Rl二元分類問題可以根據(jù)似然比Rl來決定t的歸屬對數(shù)似然比：假設(shè)x的各維數(shù)據(jù)之間相互獨立；樸素Bayes分類器向量距離分類器向量距離分類器可以看作是Bayes分類器的簡化，它用各類別數(shù)據(jù)的均值向量、方差向量、協(xié)方差矩陣等參數(shù)近似描述它們的分布特性，利用向量之間的各種距離進行分類，常用的距離尺度有:k近鄰分類器也稱k-NN分類器(k-NearestNeighbor)最大特點是不需要訓(xùn)練類別模型，而是按某種合理的比例從各類別中抽取樣本，用所有抽出的樣本構(gòu)成分類器的總體特征樣本對于一個給定的樣本t，首先按照某種距離測度找出與其最接近的k個樣本，然后根據(jù)這k個樣本所屬類別進行投票SVMSVM是一種以結(jié)構(gòu)風(fēng)險最小化為目標(biāo)的二元分類器，在尋找最優(yōu)分類超平面時不但要求將兩類數(shù)據(jù)隔離，而且要求兩類數(shù)據(jù)距超平面的平均距離最大設(shè)線性可分數(shù)據(jù)集為D維空間中線性判別函數(shù)的一般形式為分類超平面方程為系統(tǒng)性能評價評價指標(biāo)主要包括分類器的精度和速度速度取決于分類器算法的復(fù)雜程度，在實際應(yīng)用中與計算機的硬件性能關(guān)系很大精度通過與人工標(biāo)注結(jié)果(groundtruth)進行比較來計算對于二元分類問題，常用的精度指標(biāo)有準(zhǔn)確率召回率F-measurebreak-even點精度指標(biāo)標(biāo)注為L類標(biāo)注為非L類判別為L類ab判別為非L類cd分類與標(biāo)注對應(yīng)關(guān)系的頻次i)準(zhǔn)確率(Precision)表示所有被分類器分到類L的數(shù)據(jù)中正確的所占的比例ii)召回率(Recall)表示所有實際屬于L的數(shù)據(jù)被分類器分到L中的比例iii)平衡點BEP(Break-evenPoint):P和R值是互相影響的:P會隨著R的升高而降低，反之亦然。因此，為了更全面地反映分類器的性能，一種做法是選取P和R相等時的值來表征系統(tǒng)性能，這個值叫BEPiv)F值一種把準(zhǔn)確率和召回率綜合考慮的評價方法，定義如下：模型學(xué)習(xí)生成式學(xué)習(xí)典型應(yīng)用：利用EM算法對GMM的參數(shù)進行估計共同特征：每個類模型只用本類的樣本進行估計，估計的準(zhǔn)則是使模型產(chǎn)生訓(xùn)練樣本的可能性最大(最大似然)早期的模型學(xué)習(xí)主要采用生成式算法區(qū)分式學(xué)習(xí)典型應(yīng)用:SVM的學(xué)習(xí)共同特征:由需要相互區(qū)分的各類樣本共同構(gòu)成一個模型，通過多類樣本的“角力”形成不偏不依的分類面降維變換需要進行學(xué)習(xí)的降維變換是指變換核（基函數(shù)）隨被處理數(shù)據(jù)集變化以獲得最佳變換效果的變換(自適應(yīng)變換)主成分分析PCA(PrincipalComponentAnalysis)獨立成分分析ICA(IndependentComponentAnalysis)線性鑒別分析LDA(LinearDiscriminativeAnalysis)希爾伯特—黃變換Hilbert-Huang自適應(yīng)變換也存在生成式和區(qū)分式之分PCA

設(shè)隨機變量，存在一個樣本集，則其均值可估計如下：協(xié)方差矩陣可估計如下：求解按降序排列的d個特征值和對應(yīng)的特征向量，并構(gòu)成矩陣稱為x的PCA變換(也稱K-L變換)，則式PCA的性質(zhì)PCA變換后的變量y是零均值的隨機變量，其協(xié)方差矩陣為：由于A是列為的特征向量的正交矩陣，所以是對角陣且對角線元素為的特征值，即：由于的非對角元素都是零，所以隨機變量y的各維之間是不相關(guān)的LDA

LDA的思想是找一個投影方向，使得投影后在低維空間里樣本的類間散度較大，類內(nèi)散度較小x1x2x’LDA的定義(1/3)設(shè)Ci為第i類樣本的集合，共有c類樣本，則樣本類內(nèi)散度矩陣定義為：其中，mi為第i類樣本的均值，樣本類間散度矩陣定義為：其中為樣本集的總體均值向量LDA的定義(2/3):將d維的隨機變量x變換到c-1維定義在變換空間中樣本的類內(nèi)和類間散度矩陣：容易證明LDA的定義(3/3)定義如下的準(zhǔn)則函數(shù)：容易證明，使J(.)最大化的變換矩陣W的列向量由下列等式中的最大特征值對應(yīng)的特征向量組成：這是一個廣義特征值問題，如果Sw是非奇異的，W的列向量就是由矩陣的特征向量組成其中LDA的奇異性LDA是信息過濾中數(shù)據(jù)降維的核心算法之一在應(yīng)用中常遇到類內(nèi)分散度矩陣Sw奇異的問題當(dāng)數(shù)據(jù)維數(shù)很高時，能夠獲得的樣本數(shù)常常相對不足，使得獨立的訓(xùn)練樣本數(shù)N小于數(shù)據(jù)維數(shù)d，而這將導(dǎo)致Sw為奇異矩陣信息過濾所處理的文本、圖像、音頻等一般都是在高維數(shù)據(jù)空間中表達的解決LDA奇異性問題時，常先用某種生成式算法對數(shù)據(jù)進行降維LDA奇異性的解決

主要方法:正則化LDAPCA+LDAPCA+NULL空間LDA/QRLDA/GSVD

正則化LDA（RLDA）一種簡單的解決Sw矩陣奇異的方法是利用正則化思想在Sw上加一個擾動量，數(shù)學(xué)表達為 其中

0，I為一個單位矩陣這種方法的主要問題在于擾動量的選取有難度。如果擾動量太小可能不足以解決奇異問題，太大又會使Sw內(nèi)包含的判決信息丟失PCA+LDA首先用PCA對數(shù)據(jù)降維，使Sw成為非奇異矩陣，然后再進行LDA將生成式變換與區(qū)分式變換結(jié)合PCA變換使數(shù)據(jù)中的信息被“忠實地”保留，同時數(shù)據(jù)維數(shù)得到了壓縮，以便消除使Sw奇異的條件難點：沒有明確的理論指導(dǎo)PCA降維的維數(shù)選擇如果PCA維數(shù)太低，會丟失過多的鑒別信息如果維數(shù)太高，相對來說訓(xùn)練樣本會仍顯不足，這樣即使能解決Sw的奇異問題，也難免會出現(xiàn)過擬合的現(xiàn)象LDA/QR對Hb進行QR分解，得到一個正交矩陣Q和一個上三角矩陣R，然后在Q張成的低維子空間內(nèi)進行鑒別分析算法分兩步完成：第一步，對Hb進行QR分解，Hb=QR的正交列張成了Hb的秩空間是上三角矩陣第二步，在上運用LDA然后定義:LDA/GSVD

通過廣義奇異值分解GSVD，用Hb和Hw代替Sb和Sw根據(jù)GSVD理論，正交矩陣Y∈Rc*c，Z∈Rn*n，以及非奇異矩陣X∈Rd*d滿足如下關(guān)系：因此有X的列向量就是矩陣對[Hb,Hw]對應(yīng)的廣義奇異向量，并將其作為基于GSVD的鑒別特征子空間RDMRDM的特點主要有兩方面1）將LDA問題轉(zhuǎn)化為同時對角化類內(nèi)和類間散度矩陣問題2）通過能量適應(yīng)準(zhǔn)則來近似估計對類內(nèi)散度矩陣Sw進行對角化，得：在對角矩陣上加上一個小的擾動量進行正則化，即（）σ的選擇RDM將Sw的能量譜用作選擇σ的標(biāo)準(zhǔn)J(m)通過前m個特征值在總能量譜中所占的比例來確定m的值半監(jiān)督學(xué)習(xí)問題：樣本不足/標(biāo)注樣本不足找到有效的方法，使得只需手工標(biāo)注少數(shù)數(shù)據(jù)，就能較準(zhǔn)確地對全部數(shù)據(jù)進行自動標(biāo)注三類算法在聚類過程中利用已標(biāo)注的數(shù)據(jù)來引導(dǎo)聚類在對標(biāo)注樣本進行學(xué)習(xí)之后，首先處理那些有較高置信度的未標(biāo)注樣本，然后迭代地把這些估計加入到標(biāo)注樣本集中將數(shù)據(jù)看作圖上的結(jié)點，將數(shù)據(jù)間的(已知的)相似性看作結(jié)點間的初始邊長(權(quán)重)，應(yīng)用圖的理論對數(shù)據(jù)進行聚類半監(jiān)督學(xué)習(xí)的形式定義標(biāo)注樣本集合L=標(biāo)注樣本的類別向量用yij=1andyiq=0(qj)表示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基于圖的算法在圖中估計樣本的類別函數(shù)f，使其滿足兩個條件：1)對于已標(biāo)注樣本，其真實類別和通過f得到的結(jié)果越接近越好2)對于整個樣本集，f足夠平滑這兩個條件可以通過正則化方法得到滿足，即在求解的過程中用先驗知識對求解過程加以約束，從而獲得有意義的解類別估計函數(shù)f一般由兩項組成，一項是損失函數(shù)，用來評價條件1的滿足度；另一項是正則化，保證條件2得到滿足基于隨機場的半監(jiān)督學(xué)習(xí)首先在圖上定義一個連續(xù)的隨機場，然后根據(jù)能量函數(shù)最小化時調(diào)和函數(shù)的特性獲得聚類結(jié)果基于相似點應(yīng)屬于相同類別，得到二次能量函數(shù)：式中W={wij}是圖的權(quán)值矩陣，代表結(jié)點間的相似性通過已標(biāo)注數(shù)據(jù)，可以獲得部分f(i)的取值即，如果xi∈L

，則f(i)由yi確定另，利用Gauss隨機場賦予f一個概率分布其中β為常數(shù)，Z為配分函數(shù)令D為一個對角矩陣,，表示點i的度,則定義由此，能量函數(shù)可以改寫為：Gauss隨機場可以改寫為：的定義:組合Laplace矩陣基于Gauss隨機場的學(xué)習(xí)(1/2)

上式中的含義與圖中的平滑概念是一致的(f(i)取周圍點的均值)將權(quán)重矩陣W寫成分4塊的分塊矩陣調(diào)和函數(shù)的解是在滿足fl=yl的條件下使Δf

=0其中P為圖的轉(zhuǎn)移概率矩陣，P=D-1W在能量函數(shù)達到最小的條件下，未標(biāo)注樣本點滿足基于Gauss隨機場的學(xué)習(xí)(2/2)

基于局部一致和全局平滑的學(xué)習(xí)用一個加權(quán)圖來描述數(shù)據(jù)集，在滿足與標(biāo)注信息一致的條件下使樣本集的類別平滑變化定義圖G={V,W}，wij的計算方法如下根據(jù)相似度越大類別越可能一致的原則，定義目標(biāo)函數(shù)η是數(shù)據(jù)集中每個點與其近鄰點間的差異度，越小越好優(yōu)化目標(biāo)函數(shù)聚類結(jié)果必須滿足已標(biāo)注的真實類別信息將這些信息表示為等式：A為C×n的系數(shù)矩陣，yi為已標(biāo)注樣本i的真實類別向量(行向量)F為n×C的類別指示矩陣b是C×C的對角矩陣，bjj等于標(biāo)注樣本中屬于第j類的樣本個數(shù)最優(yōu)的類別估計結(jié)果就是當(dāng)xi∈L時，fi=yi因此，半監(jiān)督學(xué)習(xí)問題就轉(zhuǎn)化為了如下的最優(yōu)化問題優(yōu)化問題的求解令矩陣，上述優(yōu)化問題可轉(zhuǎn)化為將F取0/1值的條件進行松弛，使其取實數(shù)值將優(yōu)化問題變?yōu)闃?biāo)準(zhǔn)的二次規(guī)劃問題，定義Lagrange函數(shù)令可求得類別指示向量F的最優(yōu)實數(shù)解為其中演進式學(xué)習(xí)演進式學(xué)習(xí)—分類模型隨著信息環(huán)境的變化而自動演進隨機過程(而不是隨機變量)動態(tài)描述數(shù)據(jù)分布，使分類模型隨著分布的變化而自動演進分類模型永遠是動態(tài)的，系統(tǒng)通過應(yīng)用環(huán)境中的樣本對模型不斷進行修正不再試圖估計靜態(tài)的“總體分布”，而只考慮當(dāng)前時刻隨機變量的分布如何從上一時刻的分布演進出來演進學(xué)習(xí)通過小樣本完成，因而可以提高學(xué)習(xí)效率演進式學(xué)習(xí)的流程不斷地從應(yīng)用環(huán)境中獲取新樣本進行模型的演進增加自動采集新樣本、接收識別(分類)模塊的樣本反饋、以及演進式模型學(xué)習(xí)和更新分類模型等過程類別標(biāo)注樣本庫中存放從應(yīng)用環(huán)境中自動采集的數(shù)據(jù)樣本和分類器識別后反饋的樣本，作為模型演進的數(shù)據(jù)源模型的演進方法假設(shè)S(ti)是隨機過程{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)的方法獲得模型演進的關(guān)鍵問題：獲得A(ti)和E(ti)的方法利用A(ti)和E(ti)對ti-1時刻的模型進行演進，獲得ti時刻的模型|A(ti)|和|E(ti)|的變化規(guī)律在t0時刻用N0個樣本初始化，演進初期|A(ti)|>>|E(ti)|隨著系統(tǒng)的成熟，|A(ti)|和|E(t)|逐步接近tc是系統(tǒng)性能達到設(shè)計要求進入常態(tài)的時刻，交換的訓(xùn)練樣本數(shù)為dd的大小與演進周期(ti-ti-1)成正比在演進周期(ti-ti-1)比較短的情況下，|A(ti)|和|E(ti)|都遠小于|S(ti-1)|。性能指標(biāo)影響因素：系統(tǒng)進入常態(tài)的時刻dA(ti)和E(ti)的獲得ti時刻以隨機的方式從采集的樣本和反饋的識別樣本中選出一個集合N(ti)，從中選出|A(ti)|個識別得分最低的樣本組成A(ti)，在S(ti-1)中選出|E(ti)|個識別得分最低的樣本組成E(ti)|S(ti)|=|S(ti-1)|+|A(ti)|-|E(ti)|物理意義是通過更換邊緣樣本來移動學(xué)習(xí)樣本集的類中心。模型演進對于生成式模型，采用ML準(zhǔn)則下的增量式EM算法對于區(qū)分式模型；可采用基于自適應(yīng)特征分布變化的adaboost算法需要注意的是，由于自動采集和識別反饋的樣本的類別標(biāo)注是有錯誤率的，因此在沒有人工校對的情況下S(ti)是含噪的垃圾郵件及垃圾短信過濾

垃圾郵件(spam)過濾系統(tǒng)TRECSpam評測的技術(shù)是基于內(nèi)容識別的，這不同于目前在市場上普遍應(yīng)用的技術(shù)，如黑白名單過濾、基于地址分析及跟蹤的啟發(fā)式過濾等文本分類器是TRECSpam技術(shù)的核心，統(tǒng)計學(xué)習(xí)算法是研究的重點過濾器的性能兩個指標(biāo)：Ham錯分百分比hm%：被錯分到Spam目錄中的ham占ham總數(shù)的百分比Spam錯分百分比sm%：被錯分到Ham目錄中的spam占spam總數(shù)的百分比系統(tǒng)根據(jù)郵件為spam的可能性進行過濾若可能性大于閾值t，則將其投入spam目錄，否則投入ham目錄提高t有利于降低hm%，但會升高sm%；反之，降低t有利于降低sm%，但會升高hm%給出每封郵件的score，可以通過改變t值獲得sm%相對hm%的函數(shù)關(guān)系，這種函數(shù)關(guān)系的圖形表示就是著名的ROC(ReceiverOperatingCharacteristic)曲線Spam過濾器最常見的是SVM和樸素Bayes[Brat05]創(chuàng)新性地將動態(tài)數(shù)據(jù)壓縮中的局部匹配預(yù)測PPM(PredictionbyPartialMatching)用于Spam過濾PPM是一種自適應(yīng)概率編碼壓縮技術(shù)每處理被壓縮數(shù)據(jù)的一個符號，PPM的概率模型—P(x|context)都會隨之更新每處理完一個符號，都會得到一個新的P(x|context)系統(tǒng)根據(jù)P(x|context)獲得一個熵編碼方案編碼方案隨著context的演變而自適應(yīng)調(diào)整PPM通過訓(xùn)練數(shù)據(jù)獲得PPM的兩個概率模型P(x|context-spam)和P(x|context-ham)與常見的方法的差別：PPM假設(shè)信源產(chǎn)生符號的過程符合k階Markov過程PPM模型會隨著處理的進行而自動演進，這恰好應(yīng)對了Spam特征的演進性在PPM中，通常約定用-1階模式指出系統(tǒng)的字符集A，并且假定所有字符以相同的概率1/|A|出現(xiàn)未出現(xiàn)過的轉(zhuǎn)移模式用Esc表示例:“abracadabra”的2階PPM模型垃圾短信的過濾短信的基本特點：長度短，最長不能超過140個ASCII字符或70個漢字不完整(省略、指代、簡化等)、不規(guī)范(用詞另類、語法隨意等)短信分類不統(tǒng)一運營商：訂閱（由SP提供的）/手寫（由手機用戶手工輸入的）用戶：私人/廣告安全部門：合法/非法發(fā)送形式：SPMU/UU/UMU發(fā)送內(nèi)容：普通短信/垃圾短信/異常短信細分類：聊天短信、問候短信、祝福短信、娛樂短信、新聞短信、理財短信基于正則表達式的分類正則表達式(RegularExpression)由數(shù)學(xué)家StephenKleene于1956年提出在許多腳本語言中得到支持，如Perl、PHP、JavaScript，已經(jīng)被國際組織ISO和OpenGroup標(biāo)準(zhǔn)化正則表達式由模式修正符、元字符、子模式、量詞和斷言等元素組成，通過一系列模式對字符串進行匹配快速地分析大量的文本以找到特定的字符模式，提取、編輯、替換或刪除字符串基于統(tǒng)計的分類特征抽取——主要采用VSM和n-gram模型構(gòu)造一個詞的集合來很好覆蓋短信中出現(xiàn)的詞匯分詞詞集合的選擇是短信特征抽取的關(guān)鍵簡便的方法是以字為單位進行處理基于單字特征的Bayes分類器TDT系統(tǒng)Topic:特指在特定時間特定地點發(fā)生的事件，而非一般意義的事件類例：“汶川地震”VS“地震”一個話題或事件，會有多個相關(guān)的報道(story)TDT的任務(wù)報道分割將一個連續(xù)的文本流劃分為一個個報道事件檢測回顧式檢測/在線式檢測事件跟蹤將新產(chǎn)生的報道與系統(tǒng)已知的事件聯(lián)系起來給定目標(biāo)事件的條件下判斷每個后續(xù)報道是否在討論這個目標(biāo)事件報道分割算法的評價一方面是直接評價其對報道邊界定位的準(zhǔn)確性另一方面是間接評價其對事件追蹤的支持能力基于HMM進行報道分割基于話題轉(zhuǎn)換的概率進行分割基于局部語境分析LCA進行報道分割將句子轉(zhuǎn)換為LCA詞，對其索引后判斷報道邊界將視頻分割應(yīng)用于報道分割基于LCA方法的關(guān)鍵要素基于內(nèi)容的特征:一對語言模型，用于幫助判斷話題是否大幅改變在線自適應(yīng)語言模型VS離線靜態(tài)語言模型表示局部語境的語言學(xué)和結(jié)構(gòu)特征的詞匯特征使用各個詞的位置偏移量對詞的特征進行編碼以更精細的粒度對與分割邊界相關(guān)的詞進行判斷增量式地選擇最佳的詞匯特征的學(xué)習(xí)算法，并將詞匯特征與語言模型相結(jié)合形成統(tǒng)一的統(tǒng)計模型增量式地構(gòu)建一個越來越詳細的模型，對分割邊界設(shè)置的正確性進行概率估計事件檢測在新聞流中標(biāo)識出新的或是以前沒有標(biāo)識的事件本質(zhì)：無監(jiān)督的學(xué)習(xí)任務(wù)模式：回顧式/在線式回顧式的輸入是整個文本集，輸出是對文本集一簇簇的劃分在線式的輸入是按時間順序的實時報道流，系