第二講：文本處理(4章)

1、1第二講：文本處理第二講：文本處理 . 重復(fù)文檔與噪聲重復(fù)文檔與噪聲 (3章,3.7-3.8) . 文本處理文本處理 (4章 )主講人：朱征宇朱征宇聯(lián)系電話mail：zhu_課程名稱：智能信息檢索課程名稱：智能信息檢索23.7 重復(fù)文檔的檢測重復(fù)文檔的檢測v文文 檔重檔重 復(fù)現(xiàn)復(fù)現(xiàn) 象象互聯(lián)網(wǎng)上重復(fù)和近似重復(fù)的文檔非常普遍(除重復(fù)源外，抄襲、廣告等垃圾信息)URL地址指向同一網(wǎng)頁，以及鏡像站點(爬蟲重復(fù)爬取頁面)一個大型信息采集系統(tǒng)，通常有30%是重復(fù)信息v重復(fù)信息的影響重復(fù)信息的影響大量非常相似文檔的存在，使信息采集、索引、搜索過程，消耗大量資源，卻提供少量有用信息

2、v重復(fù)文檔檢測重復(fù)文檔檢測完全重復(fù)檢測：檢驗和檢驗和(checksumming)技術(shù)(更復(fù)雜的有：*循環(huán)冗余校驗循環(huán)冗余校驗cyclic redundancy check，CRC) 并參考 http:/ 基于詞詞(及權(quán)重)表達文檔，并計算相似性(發(fā)現(xiàn)與給定文檔的相似性)2) 基于指紋表達文檔，并計算相似性(在集合中找所有相似文檔對) （相似性判定：對兩文檔的指紋，計算所包含的相同指紋數(shù)量）如何檢查重如何檢查重復(fù)文檔？復(fù)文檔？重復(fù)文檔帶重復(fù)文檔帶來的弊端？來的弊端？蜘蛛網(wǎng)上收蜘蛛網(wǎng)上收集的文檔重集的文檔重復(fù)量大嗎？復(fù)量大嗎？3循環(huán)冗余校驗循環(huán)冗余校驗CRC（即生成的（即生成的r=n-k位碼校驗碼

3、）位碼校驗碼）（通過左移（通過左移r位操作位操作-成為成為n位碼）位碼）（即生成的（即生成的n位位CRC碼）碼）4文檔指紋生成過程文檔指紋生成過程例子例子5例子：文檔指紋的生成例子：文檔指紋的生成參考參考-更好的方法：更好的方法：simhash指紋技術(shù)指紋技術(shù)這這16個串的指紋個串的指紋n=3共有共有16個個n-gram串串（采用逗號分隔）（采用逗號分隔）p=4通過模通過模4為為0選擇的選擇的4個指紋個指紋4個指紋個指紋大規(guī)模的應(yīng)用中，大規(guī)模的應(yīng)用中，如網(wǎng)上查找近似重如網(wǎng)上查找近似重復(fù)文檔，復(fù)文檔，n-gram常包含常包含5-10個單詞個單詞,散列值則為散列值則為64位！位！6simhash指

4、紋技術(shù)指紋技術(shù)*例子：圖例子：圖3-157例子：例子：simhash指紋的計算指紋的計算*第第2位散列值計算：位散列值計算：+2-2 +1-1-1-1-1+1-1-1-1-1+1=-5用b=8位二進制來表示的指紋：出現(xiàn)13個詞：第第1位散列值計算：位散列值計算：-2+2+1-1-1+1-1+1+1-1+1-1+1=+1(根據(jù)13個詞的權(quán)重和該位是0/1 -1/+1確定的值)(正數(shù)對應(yīng)1負數(shù)對應(yīng)0)實際應(yīng)用中，實際應(yīng)用中，b取很大的值！取很大的值！如文獻如文獻Henzinger(2006)中，中，指紋長指紋長b=384位，當當兩網(wǎng)位，當當兩網(wǎng)頁的指紋中有多于頁的指紋中有多于372為是相為是相同的

5、同的,這兩網(wǎng)頁近似重復(fù)這兩網(wǎng)頁近似重復(fù)!83.8 文檔噪聲處理文檔噪聲處理v文檔噪聲文檔噪聲一些網(wǎng)頁中含有文本、鏈接、圖片等，但未必與主要內(nèi)容相關(guān)例如，廣告、徽標logo、熱鏈接等，（如圖3-16）v去除文檔噪聲的理由去除文檔噪聲的理由搜索引擎中使用的頁面內(nèi)容表示組件主要是基于詞統(tǒng)計的無關(guān)文本（廣告文本，熱鏈接的錨文本）會干擾頁面內(nèi)容表示無關(guān)文本、鏈接、圖片等，會大量增加處理和空間消耗v去除文檔噪聲的技術(shù)去除文檔噪聲的技術(shù)(對網(wǎng)頁中內(nèi)容塊進行檢測的噪聲判定技術(shù))法1：Finn(2001)-基于HTML標簽分析提出的判定方法法2* ：還有Pinto(2002)-對上方法的改進，基本思路是：“使用

6、一個文本窗口對文檔斜率曲線中低斜率部分進行搜索”法3：Gupta(2003)-利用網(wǎng)頁的結(jié)構(gòu)來識別頁面的內(nèi)容塊#什么是文檔噪聲?為何要去除為何要去除文檔噪聲？文檔噪聲？如何去除文檔噪聲?9Finn(2001)噪聲判定方法噪聲判定方法v核心思想核心思想網(wǎng)頁中，主要內(nèi)容文本會比附加內(nèi)容文本含有更少量的HTML標簽例如，圖3-6中頁面的詞素-標簽統(tǒng)計圖3-17，網(wǎng)頁主要正文位于”平坦區(qū)域”v平坦區(qū)域的檢測方法平坦區(qū)域的檢測方法用(長為N)二進制位序列表示網(wǎng)頁(設(shè)網(wǎng)頁中詞素總數(shù)為N)若第n個詞素是一個標簽，則bn=1；否則(即其它所有詞素) ，bn=0；注意：這里忽略 “字體、標題、表格”等標簽， (

7、即也用0表示)這樣，(平坦區(qū)域P)主要內(nèi)容塊的檢測主要內(nèi)容塊的檢測是一個優(yōu)化問題：找到i，j兩值，使目標函數(shù)最大化：P前標簽數(shù)+P中其它詞素數(shù)目+P后標簽數(shù) 使用限制：主要適合于非內(nèi)容塊滿足“文本詞素比例小于標簽的比例的情形” （否則對內(nèi)容模塊平臺區(qū)域的識別將較為困難?。?10文檔噪聲的例子：文檔噪聲的例子：標簽統(tǒng)計相對平坦區(qū)域相對平坦區(qū)域Finn 方法方法可否擴展到識別可否擴展到識別多個內(nèi)容區(qū)域？多個內(nèi)容區(qū)域？法2-Pinto(2002)11Gupta(2003)噪聲判定方法噪聲判定方法v文檔對象模型文檔對象模型DOM瀏覽器顯示網(wǎng)頁時，HTML解析器使用標簽解釋頁面指定結(jié)構(gòu)(DOM)DOM類

8、似一個樹結(jié)構(gòu)，用于識別網(wǎng)頁中主要的部分例如：圖3-16中頁面的DOM樹如圖3-18vGupta噪聲判別方法噪聲判別方法(思路思路)通過遍歷DOM樹，采用不同過濾技術(shù)，來刪除DOM樹中的節(jié)點(如圖片，腳本、廣告、鏈接列表、無內(nèi)容的表格，等元素) ，只留下內(nèi)容部分該方法非常適合于識別只包含單一單一內(nèi)容塊的網(wǎng)頁v*如何識別多內(nèi)容塊頁面？如何識別多內(nèi)容塊頁面？辦法是：側(cè)重于視覺頁面布局和外觀（如定義顯示信息的：塊的位置，字體大小，背景顏色，分隔符，等）結(jié)合DOM樹和視覺分析，可以處理含有多個多個內(nèi)容塊的頁面#12圖圖3-18： 圖圖3-16頁面的頁面的DOM樹樹含有新聞文本的部分通過注釋cnnArti

9、cleContent給出13一、文本處理簡介一、文本處理簡介v文本處理文本處理(爬蟲)獲得文本后，需決定是否修改或重構(gòu)這些文本，以簡化搜索這個過程被稱為文本轉(zhuǎn)換/文本處理處理目的：將詞語可能出現(xiàn)的多種形式轉(zhuǎn)化為更加一致的索引項索引項（可用它表示文本內(nèi)容）-建立索引庫的重要基礎(chǔ)建立索引庫的重要基礎(chǔ)！v精確搜索精確搜索 (文本處理的基本服務(wù)對象)最簡單的文本處理是什么都不做，如文字處理器的“查找”：當鍵入查找詞后，掃描文檔，并精確匹配到鍵入詞位置這種搜索叫“精確搜索”，這種功能非常有用局限性：甚至未考慮大小寫敏感問題（computer不能匹配Computer）還好，大多數(shù)的字處理軟件有忽略大小寫的

10、選項大多數(shù)的搜索引擎不區(qū)分大小寫v其它處理事項其它處理事項（看似簡單，但對搜索結(jié)果影響大）忽略標點符號，詞素切分，詞串(成語，短語)切分去除停用詞(頻繁詞,無意義詞)，詞干提取(允許run與running匹配)格式改變(字體，大小)，結(jié)構(gòu)處理（標題，章節(jié)），鏈接處理信息抽取（識別：新詞、人名、組織名、地址），分類，多語言問題#第第4 4章章- - -“我一直在嘗試理解這些詞的意思我一直在嘗試理解這些詞的意思”什么是精確什么是精確搜索？搜索？文本處理還文本處理還需做什么？需做什么？文本處理目文本處理目的和任務(wù)？的和任務(wù)？14二、文本統(tǒng)計二、文本統(tǒng)計v文本統(tǒng)計的作用文本統(tǒng)計的作用雖然語言豐富和多變

11、，但仍然是可以預(yù)見的!Luhn于1958指出：一個詞的重要性取決于它在文檔中出現(xiàn)的頻率表示詞語出現(xiàn)規(guī)律的統(tǒng)計模型，對于信息檢索非常重要：被應(yīng)用于搜索引擎的關(guān)鍵部件(排序算法、查詢轉(zhuǎn)換、索引技術(shù))v詞語統(tǒng)計的特點詞語統(tǒng)計的特點最明顯的特征之一是“詞語頻率的分布非常傾斜”：v一些詞的出現(xiàn)頻率非常高，很多詞的出現(xiàn)次數(shù)非常少v而且，詞頻分布滿足齊普夫法則（Zipfs low）“預(yù)測詞的比例”的計算公式（用齊普夫法則，根據(jù)詞頻推出）v下面討論文本統(tǒng)計中的兩個基本問題詞表增長規(guī)律 & 數(shù)據(jù)集規(guī)模估計#為何需要文為何需要文本統(tǒng)計？本統(tǒng)計？詞語分布有詞語分布有規(guī)律嗎？規(guī)律嗎？15詞語頻率的分布詞語頻率

12、的分布AP89統(tǒng)計分析（表統(tǒng)計分析（表4-2） ，驗證了齊普夫法則的有效性；，驗證了齊普夫法則的有效性；并有圖并有圖4-2 AP89中所有詞的中所有詞的r* Pr值的值的log-log圖。圖。但該法則對排名靠前和靠后的詞不一定準確（表但該法則對排名靠前和靠后的詞不一定準確（表4-23） PrfPr =f/TT16詞出現(xiàn)的次數(shù)排名與概率對比詞出現(xiàn)的次數(shù)排名與概率對比反比例曲線 Pr=c/r 17表表4-2 AP89統(tǒng)計分析與齊普夫法則統(tǒng)計分析與齊普夫法則r * Pr 非常接近常數(shù)非常接近常數(shù)0.1接近接近10%接近接近20%18齊普夫法則對排名靠后的齊普夫法則對排名靠后的(低頻低頻)詞不一定準確

13、詞不一定準確r * Pr 與常數(shù)與常數(shù)0.1有較大差異有較大差異19“預(yù)測詞的比例預(yù)測詞的比例”的公式的公式即n+1令n=1，有1/n(n+1)=1/2令n=1兩者相除r*f=k，r=k/f，這里設(shè)詞頻f為n，故r=k/n注：設(shè)詞頻率相同的詞，排名也相同(排在一起)20表表4-4 詞頻排名例子詞頻排名例子21表表4-5 預(yù)測公式與真實數(shù)據(jù)比較預(yù)測公式與真實數(shù)據(jù)比較22AP89中詞的中詞的r * Pr值的值的log-log圖圖因：Pr=c/rlogPr= log(c/r) =logc-logrr和Pr都取對數(shù)記為r和Pr,則Pr=logc- rPrrr和和Pr都取對數(shù)所畫圖都取對數(shù)所畫圖log2

14、32.1 詞表增長的預(yù)測詞表增長的預(yù)測(Heaps法則法則)v詞表增長詞表增長隨著語料規(guī)模的增大，新詞會不斷出現(xiàn)新詞來源：新造詞（新藥名，新公司名），人名，產(chǎn)品號碼，等基于齊普夫法則，可以預(yù)測(定性)：隨著語料規(guī)模增大，一定規(guī)模一定規(guī)模新文本中含有新詞的數(shù)目會減少vHeaps法則法則Heaps（1978）觀察發(fā)現(xiàn)：語料規(guī)模v與詞表大小n的關(guān)系為 v=k*n參數(shù)k和將隨不同語料而變化，一般10k 100和 0.5 (即對n開方)vHeapsHeaps法則的預(yù)測效果法則的預(yù)測效果語料規(guī)模小時新詞增長很快:語料規(guī)模變大時增長速度變慢圖4-3預(yù)測與AP89中詞匯增長對比(取k =62.95，0.455

15、)，很準很準！例，分析完AP89前10,879,522詞之后，Heaps法則預(yù)測詞表長度100,151，而真實值為100,024v大規(guī)模語料的新詞表預(yù)測大規(guī)模語料的新詞表預(yù)測AP89含4000萬詞，而TREC網(wǎng)絡(luò)語料GOV2含200億詞當規(guī)模達到GOV2時，似乎新詞增長將接近零，heaps法則將不再適用？圖4-4，預(yù)測與GOV2的詞表增長對比(取k =7.34，0.648) ，仍很準仍很準！什么是詞表增長？詞表增長規(guī)律詞表增長規(guī)律可以量化嗎？可以量化嗎？Heaps法則的法則的預(yù)測效果如何預(yù)測效果如何?Heaps法則適法則適用于大規(guī)模語用于大規(guī)模語料庫嗎料庫嗎?24AP89AP89中詞匯增長與中

16、詞匯增長與HeapsHeaps法則預(yù)測的對比法則預(yù)測的對比25GOV2GOV2的詞表增長與的詞表增長與HeapsHeaps法則預(yù)測的對比法則預(yù)測的對比262.2 估計結(jié)果集大小估計結(jié)果集大小v搜索結(jié)果集搜索結(jié)果集(心中有數(shù))搜索引擎在用戶輸入查詢后，一般都涉及到結(jié)果集數(shù)量的估計這里的“結(jié)果”，一般是指包含所有查詢詞的任何文檔(網(wǎng)頁)(雖然有的還允許包含部分查詢詞的文檔，但沒必要，因網(wǎng)絡(luò)規(guī)模巨大)v結(jié)果集大小的估計結(jié)果集大小的估計假設(shè)：詞在文檔中出現(xiàn)的概率是彼此獨立的，則：一文檔包括所有查詢詞的概率等于文檔包含各個詞的概率的乘積例：如查詢包含3個詞a,b,c，它們在文檔中出現(xiàn)概率分別為P(a),

17、P(b),P(c)，則聯(lián)合概率：P(abc)=P(a)*P(b)*P(c)，查詢結(jié)果集大小：fabc=N*P(a)*P(b)*P(c)v詞詞出現(xiàn)概率出現(xiàn)概率的估計的估計因搜索引擎(建索引時)容易估計到一個出現(xiàn)過該詞的文檔的數(shù)目(fa,fb,fc)和和整個文檔集的規(guī)模N，可估算這些詞的出現(xiàn)概率：P(a)=fa/N，P(a)=fb/N，P(a)=fc/N從而： fabc = (fa*fb*fc) /N2v估計效果的檢驗：估計效果的檢驗：表4-6給出了在GOV2上的部分實驗分析v1)改進的估計方式改進的估計方式：考慮詞語共現(xiàn)，并利用概率論知識來估計v2)更簡單的估計方式更簡單的估計方式： 根據(jù)已排序

18、結(jié)果集統(tǒng)計信息估計 #估計效果還可改進嗎？設(shè)：N-文檔集的規(guī)模數(shù)何時需要估計何時需要估計結(jié)果集的大小結(jié)果集的大小?如何估計結(jié)如何估計結(jié)果集大小果集大小?但如何估計但如何估計詞出現(xiàn)概率詞出現(xiàn)概率?27魚缸,水族館 kweri:m飼養(yǎng)表表4-6 結(jié)果大小估計方法的效果分析結(jié)果大小估計方法的效果分析281）考慮詞語共現(xiàn)的改進估計方法）考慮詞語共現(xiàn)的改進估計方法v改進思路改進思路?取消“獨立性假設(shè)”利用：搜索引擎含有(2個)詞語共現(xiàn)詞語共現(xiàn)統(tǒng)計信息(fab), 和概率知識概率知識v具體改進方法具體改進方法?當查詢包含2個詞時，直接給出存儲的真實值；當查詢包含3個詞時(或更長)，也可按照如下估算來提高估

19、計精度：由概率公式有:P(abc)=P(ab)*P(c|(ab) 進而，設(shè)可用P(c|a) 與P(c|b)中較大的值來估計P(c|(ab)；在由條件概率公式P(A|B)= P(AB)/P(B) ： 則有 P(abc) = P(ab)*P(c|a) = P(ab)*P(ca)/P(a) 或 P(abc) = P(ab)*P(c|b) = P(ab)*P(cb)/P(b)；從而 N*P(abc) = N*P(ab) * NP(ca) / NP(a) 或 N*P(abc) = N*P(ab) * NP(cb) / NP(b)；若搜索引擎的文檔集大小為N，利用搜索引擎含有的詞語共現(xiàn)信息，可得到表4-6

20、中的查詢“tropical fish aquarium”和”tropical fish breeding”獲得結(jié)果集合的估計數(shù)量： ftropicalfishaquarium= ftropicalfaquarium * ffishaquarium / faquarium ftropicalfishbreeding = ftropicalbreeding * ffishbreeding / fbreedingv改進效果分析：改進效果分析： fabctropicalfishaquarium = 1921*9722/26480 = 705， fabctropicalfishbreeding = 55

21、10*36427/81885 = 2451 #(比較表4-6，好很多)真實真實1529,原來估計6真實真實3629 ,原來估計18因為: P(b)=f(b)/N292）根據(jù)）根據(jù)已排序結(jié)果集統(tǒng)計信息已排序結(jié)果集統(tǒng)計信息的估計方法的估計方法v估計方法的基本思路？估計方法的基本思路？無需存儲無需存儲更多信息(如三元組出現(xiàn)次數(shù)) ，僅使用僅使用詞頻和和當前結(jié)果集統(tǒng)計信息注：引入這類估計方法是因為，許多搜索引擎：(輸出給用戶時)“不對不對所有包含查詢詞的文檔所有包含查詢詞的文檔O進行排序，進行排序，僅對僅對其中最相關(guān)的很小一部分文檔其中最相關(guān)的很小一部分文檔(集集a)進行排序進行排序”v具體的處理技術(shù)

22、？具體的處理技術(shù)？如果知道：如果知道：集a在所有文檔N中所占比例s，以及a中包含所有查詢詞的文檔數(shù)量C； 并假設(shè)并假設(shè)：包含所有查詢詞的文檔(在所有文檔N中)是均勻分布的； 則：則：結(jié)果集O的大小可估計為：C/s；實際估算中，對被處理文檔所占的比例s的估計，可由：包含包含查詢中最低頻詞查詢中最低頻詞的文檔被處理的的文檔被處理的比例比例來衡量來衡量（因所有結(jié)果必須包含該詞）v估計效果分析估計效果分析(采用Galago搜索引擎)：1）用查詢“tropical fish aquarium”對GOV2進行排序。 GOV2中共有26480個文檔包含aquarium;當處理其中3000 個文檔(即s=30

23、00/26480)時, 有C=258 個包含所有的查詢詞，故查詢結(jié)果集的數(shù)量估計為：258/s=2277；而處理20%的文檔時，估計為：1778(真實值為1529) ，非常接近非常接近！2）對查詢“tropical fish breeding”，處理完含有breeding的文檔中10%和20%后，結(jié)果估計分別為4076和3762(真實值為3629) ，非常準確非常準確！#NOaC因C/a=O/N均勻分布故O=C/(a/N)=C/s302.3 估計搜索引擎的文檔集大小估計搜索引擎的文檔集大小v文檔總數(shù)的意義文檔總數(shù)的意義估計搜索引擎存儲的文檔總數(shù)N(網(wǎng)絡(luò)有多大) ，對學術(shù)界和企業(yè)界(哪個搜索引擎

24、覆蓋面更大)都十分重要有非常多的有關(guān)研究論文v估計方法估計方法一種簡單實用的估計方法是：基于詞語相互獨立的概念從前面分析知，若a和b是相互獨立出現(xiàn)的兩個詞，則有： fab /N = fa/N * fb/N 因P(ab)=P(a)*P(b)故： N = (fa * fb)/ fab為了得到更合理的估計值N，這兩個詞a和b應(yīng)該相互獨立但實際做法：只需小心選擇a和b，盡量保證是詞義上無關(guān)聯(lián)v估計效果分析估計效果分析GOV2中，選擇tropical和lincoln兩詞，則估計文檔集大小為：(120990*771326) / 3018=30992045，而實際值是25205179 # ftropical

25、 flincoln ftropicallincoln文檔總數(shù)如文檔總數(shù)如何估計何估計?為何要估計為何要估計索引文檔的索引文檔的總數(shù)總數(shù)?估計效果到估計效果到底如何底如何?31三、文檔解析三、文檔解析3.1 目的和任務(wù)目的和任務(wù)v文檔解析的目的識別文檔的內(nèi)容和結(jié)構(gòu)并分析和抽取各種文檔特征（為文檔索引和信息檢索服務(wù)）v文檔解析的任務(wù)通過詞素切分、詞法分析和語法分析，識別詞語、元數(shù)據(jù)（發(fā)布日期、作者）、圖、表等特征（形象比喻動物解剖）通過標記語法分析(識別文檔中的標簽和元數(shù)據(jù))，解析文檔結(jié)構(gòu)解析結(jié)果：文檔的結(jié)構(gòu)和文檔的內(nèi)容表示(用于建索引)v文檔解析關(guān)注的內(nèi)容不僅包括：構(gòu)成文檔內(nèi)容的詞素、詞、短語而

26、且包括：與文檔結(jié)構(gòu)相關(guān)的重要話題、標記、標題、鏈接等 #文檔解析的目標？文檔解析關(guān)注的內(nèi)容？文檔解析的文檔解析的具體任務(wù)具體任務(wù)?323.2 詞素切分詞素切分v詞素切分詞素切分(智能性智能性)指從文檔中的字符序列中獲取詞的過程對于英文相對簡單(仍有短語,地名等識別問題)，對于中文就非常困難同時，還需做一些簡單處理（大寫換小寫，忽略無意義字符）例子：Bigcorps 2007 bi-annual report showed profits rose 10%.得到： bgcorp 2007 annual report showed profits rose注意：這種簡單處理有時是不合理的(P.53

27、:大寫,-,數(shù)字,有意義)v詞素切分的基本思路詞素切分的基本思路雖然詞素切分考慮的因素復(fù)雜，但一種基本思路是：二次掃描！第一遍，先識別文檔標記/標簽(利用特定解析器，如HTML解析器)第二遍，對文檔結(jié)構(gòu)中合適的部分(所需內(nèi)容)進行詞素切分注意：注意：考慮到幾乎所有內(nèi)容可能對查詢都有意義，詞素切分規(guī)則必須將大部分內(nèi)容(包括大寫,標點符號,-,等)轉(zhuǎn)化為可搜索標記#什么是詞素切分？如何進行詞如何進行詞素切分素切分?333.3 停用詞去除停用詞去除v停用詞停用詞文檔內(nèi)容中包含很多功能詞，它們沒有太多實際含義:如，冠詞(the，that，a),介詞(over，above，under),Hai,be，等

28、它們的特點？它們的特點？v都是高頻/無意義詞，影響處理，不能用于表達文檔的相關(guān)度v在信息檢索中，稱這些功能詞為停用詞stopword(將被扔掉)v停用詞處理停用詞處理一般可采用停用詞表但包含何詞需斟酌，否則影響查詢體驗(可能查to be or not to be)可采用集合中前n(如50)個高頻詞，或使用標準停用詞表v更奇特的處理方式更奇特的處理方式如果存儲空間允許，最好索引文檔中所有詞(包括停用詞)如果需要處理停用詞，可以僅去除查詢輸入中的停用詞#什么是停用詞，影響？如何處理停如何處理停用詞用詞?還有其它的還有其它的處理思路處理思路?343.4 詞干提取詞干提取v詞干提取詞干提取自然語言的表

29、達能力在于，可以不同方式表達同一觀點但，對基于匹配的檢索，成為一個問題故，很多技術(shù)允許搜索引擎按照語義(而非機械)匹配相關(guān)文檔詞干提取(stemming) ：獲得一個詞不同變形之間關(guān)系的過程！如：swam，swimming，swim等歸結(jié)為詞干swimv詞干提取方法詞干提取方法(智能化智能化)法一：規(guī)則演算方法v最簡單的(英文)僅處理后綴”s”，復(fù)雜一點的處理后綴ing和ed等v20世紀70s的經(jīng)典方法：Porter stemmer(分多步,每步處理不同后綴,P.56)法二：基于詞典方法v采用一個詞典來存儲相關(guān)詞的列表 (如同義詞表，適合中文)（人工創(chuàng)建，甚至相關(guān)詞可不相似，如：is，was，

30、be）法三：規(guī)則與詞典結(jié)合方式v經(jīng)典方法(1993)：Krovetz stemmer (英文詞典+手動生成例外列表)：先確定詞是否在詞典中；不在時使用一個通用的變形和派生后綴列表，逐個檢查這個詞；如果找到匹配后綴，那么從這個詞刪除后綴后，再次檢查這個詞是否在詞典中 (可反復(fù)這個過程) #這些方法的處理效果如何？ 圖4-6什么是詞干什么是詞干提取，重要提取，重要嗎嗎?如何提取如何提取詞干詞干?35圖圖4-6：Krovetz等方法的處理效果例示等方法的處理效果例示 P.58 處理更合理！處理更合理！363.5 短語和短語和n元串元串v短語的重要性短語的重要性許多提交給搜索引擎的查詢都是兩、三個詞的

31、短語，如black sea一般地，包含短語的文檔比僅包含短語中詞的文檔更相關(guān)短語比單個詞更準確，歧義也更少v短語使用中的問題短語使用中的問題難點：短語對檢索的影響非常復(fù)雜:文檔應(yīng)該確切地包含整個短語(如fishing supplies),還是在同一段落/文檔中包含其中的詞干(如fish,fishing,supplies )?v如何識別短語如何識別短語(智能化智能化)一般地，采用句子語法結(jié)構(gòu)來識別使用最頻繁的是名詞短語，可用詞性標識器來分析： 通過上下文識別的方法，或基于統(tǒng)計或規(guī)則的方法(從人工標注樣本訓練) 注：一般的詞性標記有：NN-單數(shù)名詞,NNS-復(fù)數(shù)名詞,VB-動詞,CC-連詞, 等

32、(圖4-7)其它方式：其它方式：不是為短語建索引，僅在索引中存儲詞位置，處理查詢時才利用位置信息識別短語(可不局限于緊鄰的詞語，判斷在一個特定窗口中)表4-9給出一些高頻的簡單名詞短語(來自TRTC網(wǎng)和PTO美國專利部)vn元串元串(廣義短語) #為何要考慮短語？檢索中如何對待短語？如何識別如何識別短語短語?37圖圖4-7：詞性標識器的分析結(jié)果例示：詞性標識器的分析結(jié)果例示 P.6038圖圖4-9：一些高頻的簡單名詞短語：一些高頻的簡單名詞短語 P.5939n元串元串(廣義短語廣義短語)vn元串及用途在處理大規(guī)模數(shù)據(jù)集的應(yīng)用(如搜索引擎)中，在查詢階段測試詞是否近鄰可能太慢解決辦法：需要在文本

33、處理階段采用廣義短語廣義短語概念”任何n個詞的序列” - n元串(n-gram)，如；二元串，三元串vn元串的分布特征一個n元串出現(xiàn)越頻繁，越可能是一個有意義的短語所有長度的n元串，滿足齊普夫分布齊普夫分布一些常見短語(如and the，there is)出現(xiàn)非常頻繁，而大量短語只出現(xiàn)一次。(可以采用類似停用詞表技術(shù)來處理噪音，但需謹慎設(shè)計)雖然n元串規(guī)模巨大,耗費空間 (如1000個詞構(gòu)成的文檔包含長度2n 5的元串3990個) 但很多搜索引擎仍對其索引。(因能提供排序中快速融合短語的方法)上表4-10 (P.61)，給出了部分Google-n元串樣例統(tǒng)計信息 #n元串的分布特征有用嗎？n元

34、串應(yīng)用價值？什么是什么是n元元串，用途串，用途?40四、文檔結(jié)構(gòu)和標記四、文檔結(jié)構(gòu)和標記v文檔結(jié)構(gòu)的作用文檔結(jié)構(gòu)的作用在數(shù)據(jù)庫應(yīng)用中，數(shù)據(jù)記錄的屬性是搜索的關(guān)鍵部分在郵件/文獻檢索中，作者、時間、標題等域有相似作用在網(wǎng)絡(luò)搜索中，查詢通常與文檔結(jié)構(gòu)或域無關(guān)v文檔標記的用途舉例文檔標記的用途舉例HTML標記的網(wǎng)頁結(jié)構(gòu)是排序用到的重要特征!(P.62)圖4-8的網(wǎng)頁中出現(xiàn)Tropical fish標題： 短語出現(xiàn)在標題標簽標題標簽中(源代碼圖4-9) ，且用黑體標簽強調(diào)短語的重要性； 鏈接標記鏈接標記是PageRank分析網(wǎng)頁重要性依據(jù)；錨文本間接反映網(wǎng)頁內(nèi)容；vXML標記及用途標記及用途HTML定

35、義的元素類型對所有文檔是一致的但XML文檔可以用schema來描述結(jié)構(gòu)，且允許自定義元素含義XML元素比HTML標記與數(shù)內(nèi)容的語義更緊密可設(shè)計 使用XML結(jié)構(gòu)抽取信息 的文檔語義標注技術(shù) (4.6節(jié)討論)vXQurey與搜索引擎XQuery允許查詢時指定結(jié)構(gòu)和內(nèi)容限制，類似數(shù)據(jù)庫上的SQL語言能力當XML數(shù)據(jù)中文本占大部分時，還是需要使用搜索引擎(且更快捷)文檔有結(jié)構(gòu)嗎,有用嗎?文檔標記在檢索中有用？XML標記在檢索中有用?XQuery可替代搜索引擎?41五、鏈接分析五、鏈接分析v鏈接的價值鏈接的價值網(wǎng)頁鏈接將不同網(wǎng)頁聯(lián)系起來的，是互聯(lián)網(wǎng)的一個核心組成部分鏈接存在的本身，就說明了目標網(wǎng)頁的某種

36、重要性外在看：用戶瀏覽網(wǎng)頁時，鏈接提供強大的導航作用內(nèi)在看：幫助搜索引擎理解網(wǎng)頁之間的關(guān)系 (暗示網(wǎng)頁的重要性)v錨文本的價值錨文本的價值錨文本(anchor text)的兩個特性對網(wǎng)頁排序非常有用v第一，很短(兩、三詞)，簡潔地描述鏈出網(wǎng)頁的主題有助于排序算法的設(shè)計(如搜索數(shù)據(jù)庫中的所有鏈接，查找與查詢完全匹配的錨文本，匹配1次網(wǎng)頁權(quán)重就增加1)v第二，寫錨文本的人一般不是目標網(wǎng)頁的作者 因此，錨文本從另一角度來描述目標網(wǎng)頁，或強調(diào)該網(wǎng)頁對某群體的重要性TREC網(wǎng)的評測結(jié)果顯示，在一些網(wǎng)頁搜索中，它是網(wǎng)頁表示中最重要的部分（特別是在希望搜索一個特殊話題/人/機構(gòu)的主頁時）vPagerank技

37、術(shù)技術(shù)v鏈接質(zhì)量分析鏈接質(zhì)量分析 為何要分為何要分析鏈接析鏈接?錨文本重錨文本重要嗎要嗎?如何利用如何利用鏈接信息鏈接信息?42Pagerank技術(shù)技術(shù)v網(wǎng)頁規(guī)模帶來的問題網(wǎng)頁規(guī)模帶來的問題網(wǎng)頁數(shù)量達數(shù)百億，但大多數(shù)并不是很有趣 (或僅對少數(shù)人有趣)網(wǎng)頁的巨大規(guī)模給搜索引擎帶來麻煩假如要訪問易趣網(wǎng)，在百度中輸入“eBay”，返回結(jié)果上千萬個結(jié)果(出現(xiàn)在內(nèi)容或錨文本中，包括指向eBay的錨文本)，如何排序顯示？v排序原則排序原則重要的網(wǎng)頁排在前面！但什么網(wǎng)頁更重要？v鏈接的排序價值鏈接的排序價值網(wǎng)頁鏈接分析：是網(wǎng)頁重要度的一種有效衡量方法它依據(jù)網(wǎng)頁的入鏈數(shù)(指向該頁) 及每個網(wǎng)頁的重要度來估算P

38、ageRank方法：是經(jīng)常提到的經(jīng)典代表vPageRank排序技術(shù)排序技術(shù)基本原理：在網(wǎng)絡(luò)中隨機沖浪！(如同文章間的引用分析)例示：用戶Alice隨機瀏覽網(wǎng)頁Pagerank值的計算方法 #鏈接對網(wǎng)頁鏈接對網(wǎng)頁排序有用排序有用?如何通過鏈如何通過鏈接分析網(wǎng)頁接分析網(wǎng)頁的重要性的重要性?43例示：例示：Alice隨機瀏覽網(wǎng)頁隨機瀏覽網(wǎng)頁 P.64-65vAlice瀏覽方式瀏覽方式用戶Alice無聊地不斷隨機瀏覽網(wǎng)頁進入一網(wǎng)頁(有許多鏈接)時，Alice多數(shù)時候會隨意點一個鏈接Alice少數(shù)時候也會點瀏覽器上方的”surprise me”按鈕，隨機地跳到一網(wǎng)頁vAlice瀏覽特點瀏覽特點通常， A

39、lice會更多地看到受歡迎的網(wǎng)頁（因為Alice受鏈接的引導，而鏈接傾向于指向受歡迎的網(wǎng)頁）因此，期望Alice訪問大學站點次數(shù)要多于訪問個人站點，但少于CNN站點故CNN中的一個故事中的指向一個教授網(wǎng)頁的鏈接指向一個教授網(wǎng)頁的鏈接有更多可能被Alice訪問vPageRank值值若Alice瀏覽時，你去看她屏幕上的網(wǎng)頁，碰到她看CNN網(wǎng)頁的概率有多大?這個概率是是CNN的的PageRank值值(每一網(wǎng)頁都有一個PageRank )Pagerank值由網(wǎng)頁間鏈接結(jié)構(gòu)唯一決定！(用于區(qū)分受歡迎的程度)PageRank值可幫搜索引擎從包含eBay的上千萬網(wǎng)頁中找到eBay主頁！#44PageRank

40、值的計算方法值的計算方法v假設(shè)有三個相互鏈接的網(wǎng)頁(如圖4-10)v基本思路：基本思路：頁面C的PageRank(Alice瀏覽C的概率)值PR(C)-依賴于A和B的PR值每個頁面的PR(點擊可能性/概率)應(yīng)平均分配給所有的外向鏈接v若暫時忽略surprise me，PR(C)=PR(A)/2+PR(B)/1 推廣到一般情形v考慮surprise me，按按鈕概率為且進入任何網(wǎng)頁概率為1/3，從而 PR(C)=/3+(1-)(PR(A)/2+PR(B)/1) 可推廣到一般情形v計算PageRank值的算法(p.67，圖4-11)vPageRank值的特點及重要性值的特點及重要性網(wǎng)頁的PR值與具

41、體的查詢無關(guān)！搜索引擎優(yōu)先選擇PR值高的網(wǎng)頁！網(wǎng)頁搜索中，PR并沒有傳統(tǒng)方法重要，它只是排序中使用的很多特征之一之一。ABC圖4-10 僅含3個網(wǎng)頁的互聯(lián)網(wǎng)鏈接分析鏈接分析,查詢相關(guān)度查詢相關(guān)度,用戶興趣用戶興趣,點擊率點擊率,時新性時新性,甚至商業(yè)利益甚至商業(yè)利益(廣告廣告,付費付費)！PageRank值如何計算值如何計算?哪些因素會哪些因素會影響排序影響排序?45推廣到一般情形推廣到一般情形46計算計算PageRank的算法的算法初始化計算第1項Surprise me的概率循環(huán)計算（第2項）點擊鏈接的貢獻概率輸出迭代更新開始迭代1-是點擊鏈接的概率,因網(wǎng)頁p有Q個鏈接，故該項是(p中)隨機

42、選擇其中一個鏈接(到q)的概率1-是點擊鏈接的概率,因網(wǎng)頁p無鏈接，故該項是隨機跳動到一個網(wǎng)頁(全部網(wǎng)頁P個)的概率輔助材料：計算過程樣例答：效果同，角度不同 !原考慮：p有哪些鏈入q,將q分配權(quán)值求和得PR(p)現(xiàn)考慮：p有哪些鏈出q，將PR(p)分配到q注注:此處是按照前面公式此處是按照前面公式實現(xiàn)實現(xiàn)? (原右方為不同原右方為不同Lv,這里卻是統(tǒng)一的這里卻是統(tǒng)一的|Q|)應(yīng)是qq是網(wǎng)頁p 中的一個鏈接, 共Q個個到達即p的當前PR值從新計算P對每個Q的影響47v一個事實：眾所周知，PageRank和錨文本抽取技術(shù)已在商業(yè)搜索引擎中使用v一種現(xiàn)象：肆無忌憚的網(wǎng)頁設(shè)計者試圖創(chuàng)建無用鏈接(垃圾

43、鏈接link spam，如指向某重要網(wǎng)站的首頁) ，以提高其網(wǎng)頁在搜索結(jié)果中的排序位置，v另一現(xiàn)象：狡猾的作者，利用評論中添加“反向引用鏈接trackback” ，增加自己網(wǎng)站的影響力例子：通過在知名博客B的評論帖中添加反向引用 (通知博客B有一回復(fù)發(fā)布在博客A上) ，引導閱讀自己的博客A機理分析：在許多知名博客的評論部分添加反向鏈接，按照PageRank計算，因知名博客網(wǎng)頁PR大，這些博客引用的網(wǎng)頁PR也大，應(yīng)是重要網(wǎng)頁！v問題解決途徑：搜索引擎公司自動地發(fā)現(xiàn)這些評價，在索引時忽略其中的鏈接搜索引擎公司也可要求網(wǎng)站擁有者，標記不重要的鏈接目前，大多數(shù)博客軟件被設(shè)計成：讓評論中評論中鏈接包含r

44、el=nofollow屬性，比如自動地將帖子： Come vist myweb page轉(zhuǎn)變成: Come vist myweb page (讓鏈接在博客中顯示，但搜索引擎會忽略所有有該標記的鏈接)鏈接質(zhì)量分析鏈接質(zhì)量分析這種現(xiàn)象可這種現(xiàn)象可以避免以避免?48六、國際化六、國際化*v國際化國際化網(wǎng)頁多樣：全世界都在使用互聯(lián)網(wǎng)，英語網(wǎng)頁比例(70%)，在不斷下降用戶多樣：超過一半的網(wǎng)絡(luò)使用者，在搜索網(wǎng)頁時不使用英語語言多樣：桌面/企業(yè)搜索，可能每天都在很多語言中使用v單語言搜索引擎單語言搜索引擎是一個針對特定語言設(shè)計的搜索引擎本書討論以英文為主，但很多技術(shù)對任何語言都適用語言對搜索引擎設(shè)計的影響

45、，主要在文本處理過程(抽取索引項)v其它語言搜索引擎開發(fā)難點其它語言搜索引擎開發(fā)難點字符編碼是搜索引擎處理非英語時的核心問題(主流標準Unicode)每種語言需要不同的詞干提取器詞素切分對很多語言至關(guān)重要，中日韓CJK家族核心問題是分詞（如有充足的訓練數(shù)據(jù)，隱馬爾可夫模型統(tǒng)計分詞法的效果較好）有了上述工具，建立任何一種語言上的搜索引擎不在困難例外：網(wǎng)絡(luò)中“低密度”語言，因在線資源少，建立有效的搜索引擎是挑戰(zhàn)國際化是指國際化是指什么什么?不同語言上不同語言上搜索引擎開搜索引擎開發(fā)的不同發(fā)的不同?大致存在那大致存在那些難點些難點?思考：翻譯思考：翻譯自動在國際自動在國際化中作用化中作用?49課外練

46、習：課外練習： 4.3,4.54.3,4.5( (必做題必做題1 1，需提交，需提交) )：網(wǎng)頁特征網(wǎng)頁特征( (正文正文/ /信息信息/ /文本文本/ /內(nèi)容內(nèi)容) )抽取技術(shù)概述抽取技術(shù)概述 要求：至少查閱和分析至少查閱和分析3 3篇以上相關(guān)文獻篇以上相關(guān)文獻謝謝！謝謝！50*七、信息抽取七、信息抽取v信息抽取的用途信息抽取的用途信息抽取是一種從文檔中抽取結(jié)構(gòu)化信息的語言處理技術(shù)應(yīng)用非常廣泛，尤其是文本數(shù)據(jù)挖掘、自然語言處理等領(lǐng)域搜索應(yīng)用中，主要用途是識別搜索引擎用于提高排序效果的特征v信息抽取的任務(wù)信息抽取的任務(wù)包括：前面提到過的文本處理，如識別名詞短語、標題、粗體等以及：XML等標記識別，從而容易識別一些結(jié)構(gòu)特征(標題等)各種更復(fù)雜文本(各類文檔，郵件系統(tǒng))的特征抽取問題v信息抽取面臨的困難信息抽取面臨的困難文檔類型多，文本的結(jié)構(gòu)性差，語言的結(jié)構(gòu)識別困難，語義識別短語識別、新詞(新機構(gòu)/產(chǎn)品)識別、中文詞切分、掃描文本識別多媒體信息識別 (語義特征，如圖片中的人、動物、草坪、海、太陽)v信息抽取的基本技術(shù)信息抽取的基本技術(shù)語義標注技術(shù)，建立命名實體識別器的兩種基本方法(基于規(guī)則基于規(guī)