Web搜索

郭軍

北京郵電大學

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

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

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

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

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

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

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

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

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

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

基于局部一致和全局平滑的學習用一個加權圖來描述數據集，在滿足與標注信息一致的條件下使樣本集的類別平滑變化定義圖G={V,W}，wij的計算方法如下根據相似度越大類別越可能一致的原則，定義目標函數η是數據集中每個點與其近鄰點間的差異度，越小越好優化目標函數聚類結果必須滿足已標注的真實類別信息將這些信息表示為等式：A為C×n的系數矩陣，yi為已標注樣本i的真實類別向量(行向量)F為n×C的類別指示矩陣b是C×C的對角矩陣，bjj等于標注樣本中屬于第j類的樣本個數最優的類別估計結果就是當xi∈L時，fi=yi因此，半監督學習問題就轉化為了如下的最優化問題優化問題的求解令矩陣，上述優化問題可轉化為將F取0/1值的條件進行松弛，使其取實數值將優化問題變為標準的二次規劃問題，定義Lagrange函數令可求得類別指示向量F的最優實數解為其中演進式學習演進式學習—分類模型隨著信息環境的變化而自動演進隨機過程(而不是隨機變量)動態描述數據分布，使分類模型隨著分布的變化而自動演進分類模型永遠是動態的，系統通過應用環境中的樣本對模型不斷進行修正不再試圖估計靜態的“總體分布”，而只考慮當前時刻隨機變量的分布如何從上一時刻的分布演進出來演進學習通過小樣本完成，因而可以提高學習效率演進式學習的流程不斷地從應用環境中獲取新樣本進行模型的演進增加自動采集新樣本、接收識別(分類)模塊的樣本反饋、以及演進式模型學習和更新分類模型等過程類別標注樣本庫中存放從應用環境中自動采集的數據樣本和分類器識別后反饋的樣本，作為模型演進的數據源模型的演進方法假設S(ti)是隨機過程{X(t)}在ti時刻的一個學習樣本集相鄰時刻學習樣本集的關系是:S(ti)=S(ti-1)\E(ti)∪A(ti)

即，S(ti)可以通過從S(ti-1)

中剔除樣本集E(ti)后添加樣本集A(ti)的方法獲得模型演進的關鍵問題：獲得A(ti)和E(ti)的方法利用A(ti)和E(ti)對ti-1時刻的模型進行演進，獲得ti時刻的模型|A(ti)|和|E(ti)|的變化規律在t0時刻用N0個樣本初始化，演進初期|A(ti)|>>|E(ti)|隨著系統的成熟，|A(ti)|和|E(t)|逐步接近tc是系統性能達到設計要求進入常態的時刻，交換的訓練樣本數為dd的大小與演進周期(ti-ti-1)成正比在演進周期(ti-ti-1)比較短的情況下，|A(ti)|和|E(ti)|都遠小于|S(ti-1)|。性能指標影響因素：系統進入常態的時刻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)|物理意義是通過更換邊緣樣本來移動學習樣本集的類中心。模型演進對于生成式模型，采用ML準則下的增量式EM算法對于區分式模型；可采用基于自適應特征分布變化的adaboost算法需要注意的是，由于自動采集和識別反饋的樣本的類別標注是有錯誤率的，因此在沒有人工校對的情況下S(ti)是含噪的垃圾郵件及垃圾短信過濾

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