《布爾檢索模型》PPT課件

《《布爾檢索模型》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、布爾檢索模型XXXX布爾檢索模型概述布爾檢索法是指利用布爾運(yùn)算符連接各個(gè)檢索詞，然后由計(jì)算機(jī)進(jìn)行邏輯運(yùn)算，找出所需信息的一種檢索方法。設(shè)文本集D中某一文本i,則該文本可表示為:其中為標(biāo)引詞用來反映文本i的內(nèi)容設(shè)另一用戶檢索表達(dá)式為對(duì)于該檢索式，系統(tǒng)響應(yīng)并輸出的一組文本應(yīng)為:它們都含有標(biāo)引詞和或者含有標(biāo)引詞和。布爾運(yùn)算符AND（或*）：邏輯與表示所連接兩個(gè)檢索詞的交集部分。例如檢索同時(shí)含有關(guān)鍵詞A和B的集合C：AANDBOR（或+）:邏輯或表示查找含有檢索詞A和B之一，或同時(shí)包含檢索詞A和B的信息:AORBNOT（或-）:

2、邏輯非表示含有檢索詞A并且不含有檢索詞B的信息：ANOTB布爾運(yùn)算符運(yùn)算符之間的優(yōu)先級(jí)：NOT>AND>OR，如檢索表達(dá)式：雪花NOT啤酒AND歌曲OR小說，搜索結(jié)果為：名字叫《雪花》的歌曲或者小說。利用小括號(hào)（）可以設(shè)置出個(gè)性化的檢索方程。例如檢索出不包含日本在內(nèi)的有關(guān)教育或法律方面的信息：（universityORcollege）AND（educationORLaw）NOTJapan布爾模型在網(wǎng)頁查重中的應(yīng)用網(wǎng)頁中的重復(fù)現(xiàn)象微軟曾作過一個(gè)試驗(yàn)，從網(wǎng)絡(luò)中下載了150000000個(gè)網(wǎng)頁，發(fā)現(xiàn)這些網(wǎng)頁中有29．2％是相似網(wǎng)

3、頁，而且這些相似網(wǎng)頁中還有22．2％是完全重復(fù)的(一字不差)；另外相似網(wǎng)頁十分穩(wěn)定地存在，一對(duì)相似的網(wǎng)頁在1O個(gè)星期以后極有可能還是相似的網(wǎng)頁。網(wǎng)頁重復(fù)的弊端重復(fù)的網(wǎng)頁降低了網(wǎng)頁采集器的工作效率，浪費(fèi)了數(shù)據(jù)挖掘工具的資源，使用戶的工作效率下降，如何能夠盡可能準(zhǔn)確地去除這些重復(fù)的網(wǎng)頁就是我們所面臨的問題。布爾模型在網(wǎng)頁查重中的應(yīng)用※關(guān)于重復(fù)的定義一直以來，對(duì)于重復(fù)的定義都非常模糊，沒有一個(gè)清晰的定義。一字不差可以理解為重復(fù)，字面上意義相近也可以理解為重復(fù)。對(duì)于重復(fù)各人都有自己的定義?！鵆onrad對(duì)于重復(fù)的定義是：如果兩篇

4、文章之間有超過80％的用詞相同，而且長度相差不超過正負(fù)20％，則這兩篇文章就是重復(fù)的。※Pugh(workforGoogle)對(duì)于重復(fù)的定義就要簡單得多：如果兩篇文章之間有超過r個(gè)特征相同，則它們就是相似的。布爾模型在網(wǎng)頁查重中的應(yīng)用在利用布爾模型的查重算法中，對(duì)于重復(fù)的定義就是使用Pugh對(duì)重復(fù)的定義。該算法是利用布爾模型進(jìn)行查重，將每篇文章表示為一個(gè)二進(jìn)制數(shù)，若是符合比較條件的兩篇文章，則將兩個(gè)二進(jìn)制數(shù)異或，結(jié)果中為1的特征則是兩篇文章不同的特征，計(jì)算出兩篇文章中的不同特征個(gè)數(shù)后，再判斷是否需要它們比較。當(dāng)語料集合較

5、大時(shí)，文檔之間兩兩比較的次數(shù)就相當(dāng)巨大，這是所有網(wǎng)頁查重算法的瓶頸。在使用布爾模型的網(wǎng)頁查重算法中，兩篇文檔之間是否需要比較取決于它們的相同特征個(gè)數(shù)而不是文檔長度，當(dāng)特征的總個(gè)數(shù)差別在閾值d之內(nèi)的時(shí)候，就異或其二進(jìn)制碼；否則不需要比較，直接判定它們不同。在得到二進(jìn)制碼異或的結(jié)果（0或1）之后，在讀取文檔的過程中建立一個(gè)索引。(表1)網(wǎng)頁重復(fù)的判定過程:布爾模型在網(wǎng)頁查重中的應(yīng)用▲其中id代表特征的唯一表示，Doic表示出現(xiàn)了該特征的文檔的唯一標(biāo)識(shí)符。當(dāng)兩篇文檔相互比較而相異結(jié)果為1時(shí)，就將它們分別插入它們之間不同的特征鏈

6、表中；否則，插入相同特征鏈表中。▲當(dāng)再有新的文檔需要比較時(shí)，根據(jù)該文檔中出現(xiàn)的特征，選擇應(yīng)該與它相同的集合，以減少比較次數(shù)。布爾模型在網(wǎng)頁查重中的應(yīng)用id1Doic1Doic2Doic4Doic6…id2Doic2Doic5Doic7Doic9…id3Doic1Doic4Doic5Doic6…id4Doic5Doic6Doic7Doic8…………………表一索引數(shù)據(jù)結(jié)構(gòu)使用這種算法的優(yōu)點(diǎn)：由于一些詞在所有文檔中都大量出現(xiàn)，這些詞將不會(huì)作為文檔的特征值，可以忽略大量常用停用詞的影響，如in，and，the等，這樣讀取文檔時(shí)就

7、不需要特別過濾常用詞，節(jié)約了處理文檔和提取特征的時(shí)間。特征值的比較結(jié)果只有1和0兩種狀態(tài)，節(jié)約資源，易于實(shí)現(xiàn)。布爾模型在網(wǎng)頁查重中的應(yīng)用當(dāng)兩篇文檔需要比較時(shí)，最好的情況就是所有的特征均不同，結(jié)果為0，此時(shí)的相異度就為1。當(dāng)有k（比如設(shè)k為0.2）以上特征不同時(shí)，則判定兩篇文檔為非相似文檔；如有0.2以下的特征不同，則需要計(jì)算這些不同特征總的頻度(Tf)。表2為文檔D1和D2相異度的計(jì)算實(shí)例。相異度的計(jì)算:布爾模型在網(wǎng)頁查重中的應(yīng)用?T表示文檔中出現(xiàn)的特征，D表示特征t是否在文檔Doic中出現(xiàn)過(0表示沒有出現(xiàn)，1表示出現(xiàn)

8、了，這就是布爾模型)，Tf表示特征t在文檔中的出現(xiàn)頻率，Result表示兩篇文檔之間D的異或結(jié)果：Result=D1D2。D1D2Tf1Tf2resultT101021T211130T310201T411570T511620表二D1和D2相異度的計(jì)算對(duì)于兩篇文檔i和j，假設(shè)它們符合比較的條件，則它們的相異度計(jì)算公式為