北京大學(xué)學(xué)士論文第 1 頁 論 文 評(píng) 定 意見評(píng)語 : “面向主題的搜索引擎”，是我們“天網(wǎng)”搜索引擎下一步發(fā)展的重要方向之一。龔筆宏同學(xué)的畢業(yè)論文，是這一新方向的良好開端。 論文所涉及的工作包含了對(duì)搜索引擎技術(shù)的一般認(rèn)識(shí)，通用搜索引擎和面向主題搜索引擎的對(duì)比，面向主題搜索引擎的基本工作方式，以及在各個(gè)環(huán)節(jié)中所涉及的有關(guān)算法對(duì)比與分析；而且，將上述知識(shí)和認(rèn)識(shí)有效地應(yīng)用到了程序設(shè)計(jì)實(shí)踐中，高質(zhì)量地完成了一個(gè)面向影視主題的搜索引擎系統(tǒng)，搜集了幾十多萬影視信息，在影視信息方面提供 著比“天網(wǎng)”通用搜索引擎更有效的服務(wù)；論文內(nèi)容豐富，所涉及的工作量大，且有較強(qiáng)的系統(tǒng)性，是一篇優(yōu)秀的本科畢業(yè)論文。 在畢業(yè)設(shè)計(jì)工作的過程中，龔筆宏同學(xué)態(tài)度端正，積極努力，精力集中，獨(dú)立思考，表現(xiàn)出很強(qiáng)的進(jìn)取精神和踏實(shí)的工作作風(fēng)，為“天網(wǎng)”的發(fā)展做出了貢獻(xiàn)。 老師簽名 :_李曉明 _ 北京大學(xué)學(xué)士論文第 2 頁 摘 要 天網(wǎng) 中英文搜索引擎是具有中文特色的搜索引擎 ,但是隨著當(dāng)前網(wǎng)絡(luò)的不斷增長 ,以及用戶應(yīng)用的不停變化 ,通用的搜索引擎已經(jīng)不能應(yīng)付各種不同的檢索請(qǐng)求 . 面向主題 的搜集系統(tǒng)是針對(duì)一個(gè)主題，一類網(wǎng)頁的搜集系統(tǒng) ,也就是說只搜集整個(gè)網(wǎng)絡(luò)的一個(gè)特定子集 . 所謂主題 ,可以用一系列例子頁面來確定 ,也可以用一系列的特征詞來確定 . 搜集的目標(biāo)就是 與例子頁面在內(nèi)容上類似的頁面 . 我們對(duì)目前所采用的各種面向主題的搜集 算法進(jìn)行了研究 ,同時(shí)進(jìn)行了初步的評(píng)估 確定了一套搜集算法 . 這套算法是基于原有的天網(wǎng)搜索引擎 ,而實(shí)現(xiàn)的 準(zhǔn)確的進(jìn)行同主題搜集 .,根據(jù)實(shí)現(xiàn)的結(jié)果說明面向主題搜集的優(yōu)勢(shì)所在 ,以及其發(fā)展的可能性 . 本文的大綱如下 : 本文首先說明了什么是通用的搜索引擎 , 什么是面向主題的搜集系統(tǒng) ,以及此二者的區(qū)別 . 接著提出了幾種搜集策略 , 總的來說 ,把面向主題的搜集系統(tǒng)分為三個(gè)部分 : 搜集例子 , 特征提取 ,根據(jù)特征進(jìn)行搜集 . 對(duì)這三部分 各分析了幾種策略 ,同時(shí)進(jìn)行了分析 ,評(píng)估 . 然后介紹了目前我們所實(shí)現(xiàn)的策略 . 我們主要采用的是基于向量空間模型 , 結(jié)合天網(wǎng)的特點(diǎn) 的特征提取 . 搜集方面我們主要加入了對(duì)連接關(guān)系的考慮 ,對(duì)出度入度的考慮 , 接著對(duì)我們的工作進(jìn)行了總結(jié) ,評(píng)價(jià)了所實(shí)現(xiàn)的系統(tǒng) ,說明面向主題比通用搜索引擎的區(qū)別 ,以及其優(yōu)勢(shì) . 最后是對(duì)未來工作的展望 , 現(xiàn)有系統(tǒng)的不足以及改進(jìn) 關(guān)鍵詞：搜索引擎 ,主題 ,文本分類 ,特征提取 ,連接關(guān)系 ,信息挖掘 北京大學(xué)學(xué)士論文第 3 頁 目 錄 論文載要 . .目錄 . .一章 面向主題的搜索引擎 4 索引擎的介紹 . . 4 1. 搜索引擎的使用 2. 搜索引擎的分類 3. 搜索引擎的未來 向主題的搜索引擎 . 6 者的區(qū)別比較 8 第二章 天網(wǎng)搜索引擎的介紹 . 網(wǎng)系統(tǒng)簡(jiǎn)介 網(wǎng)總體結(jié)構(gòu) . 第三章 搜集策略的研究和比較 . 12 述 . .定目標(biāo)樣本 . 13 征提取部分的幾種策略 . 13 集部分的策略 . 結(jié) .四章 我們的實(shí)現(xiàn) 21 統(tǒng)結(jié)構(gòu) 21 征提取部分的實(shí)現(xiàn) 22 集部分的實(shí)現(xiàn) 24 作結(jié)果及對(duì)結(jié)果的評(píng)價(jià) 27 第五章 總結(jié) . 28 參考文獻(xiàn) 29 北京大學(xué)學(xué)士論文第 4 頁 第一章 面向主題的搜索引擎 索引擎的介紹 1 1993 年， 出現(xiàn)了最早的 覽器 年 出了 覽器的發(fā)展促使 到迅速推廣 推動(dòng)著搜索引擎的發(fā)展 . 1994 年初， 出現(xiàn)了包括 內(nèi)的第一批 索引擎，同年還成立了 后者成為了近年來最成功的商業(yè)目錄。 搜索引擎能夠幫助網(wǎng)民在浩瀚網(wǎng) 海中 ,找到自己所需要的內(nèi)容 一定的策略在互聯(lián)網(wǎng)中搜集、發(fā)現(xiàn)信息，對(duì)信息進(jìn)行理解、提取、組織和處理，并為用戶提供檢索服務(wù)，從而起到信息導(dǎo)航的目的。搜索引擎提供的導(dǎo)航服務(wù)已經(jīng)成為互聯(lián)網(wǎng)上非常重要的網(wǎng)絡(luò)服務(wù) . 按 止 2000 年 6 月 30 日的調(diào)查表明，按 1690 萬網(wǎng)民計(jì)算，目前使用過搜索引擎網(wǎng)民共有 1570 萬左右。 搜 索引擎，在網(wǎng)民上網(wǎng)經(jīng)常參與的活動(dòng)中列第三位，有六成左右的網(wǎng)民將其列為經(jīng)常使用的網(wǎng)絡(luò)服務(wù)，僅次于電子郵件與瀏覽新聞，超過了網(wǎng)上聊天或網(wǎng)上下載或上傳軟件等活動(dòng) . 2. 搜索引擎的分類 按照信息搜集方法和服務(wù)提供方式的不同，搜索引擎系統(tǒng)可以分為三大類： 基于 搜索引擎 這種搜索引擎的特點(diǎn)是利用一個(gè)稱為 叫做 程序自動(dòng)訪問 點(diǎn)， 搜集 站點(diǎn)上的網(wǎng)頁，并根據(jù)網(wǎng)頁中的鏈接進(jìn)一步 搜集 其它網(wǎng)頁，或轉(zhuǎn)移到其它站點(diǎn)上。 集的網(wǎng)頁 經(jīng)過分析處理后 ,建立索引 ,加入數(shù)據(jù)庫中。 用戶查詢時(shí) ,檢索數(shù)據(jù)庫 ,返回結(jié)果 . 最早出現(xiàn)的搜索引擎就是利用 建立數(shù)據(jù)庫， 搜索引擎 這個(gè)詞的原義也只是指這種狹義上的基于 搜索引擎。 它的缺點(diǎn)： 并不能真正反映出網(wǎng)頁的質(zhì)量 , 返回信息過多，有很多無關(guān)信息 它的優(yōu)點(diǎn) : 信 息量大、更新及時(shí)、毋需人工干預(yù) 例子 : 如 天網(wǎng) 基于 目錄（ 叫做 搜索引擎 以人工方式或半自動(dòng)方式搜集信息，由編輯員查看信息之后，人工形成信息摘要，并將 站點(diǎn) 置于事先確定的分類框架中。 當(dāng)用戶查詢某個(gè)關(guān)鍵詞時(shí)，搜索軟件只在這些描述中進(jìn)行搜索。目錄 一般都是依靠一群專職編輯來建立和維護(hù)的 . 出名的商業(yè)目錄用了大約一兩百名編輯 來維護(hù)目錄 北京大學(xué)學(xué)士論文第 5 頁 它的缺點(diǎn) : 需要人工介入、維護(hù)量大、信息量少、信息更新不及時(shí) 它的優(yōu)點(diǎn) : 信息準(zhǔn)確、導(dǎo)航質(zhì)量高， 例子 :如 目前 提供了目錄式服務(wù) 索引擎 (也叫 “元搜索引擎 ”) 索引擎也叫做 的特點(diǎn)是本身并沒有存放網(wǎng)頁信息的數(shù)據(jù)庫，當(dāng)用戶查詢一個(gè)關(guān)鍵詞時(shí)，它把用戶的查詢請(qǐng)求轉(zhuǎn)換成其它搜索引擎能夠接受的命令格式，并行地訪問數(shù)個(gè)搜索引擎來查詢這個(gè)關(guān)鍵詞，并把這些搜索引擎返回的結(jié)果經(jīng)過處理后再返回給用戶。 它的缺點(diǎn) : 不能夠充分使用所使用搜索引擎的功能 , 擎的高級(jí)搜索功 能 它的優(yōu)點(diǎn) : 實(shí)現(xiàn)起來比較簡(jiǎn)單 , 返回結(jié)果的信息量更大、更全 例子 : 經(jīng)過了多年的發(fā)展之后，現(xiàn)在的搜索引擎功能越來越強(qiáng)大，提供的服務(wù)也越來越全面，它們的目標(biāo)是把自己發(fā)展成為用戶首選的 口站點(diǎn)，而不僅僅是提供單純的查詢功能。 搜索引擎未來的發(fā)展面臨著兩大難題： 1)發(fā)展速度， 近幾年來 速擴(kuò)張，其上的站點(diǎn)和網(wǎng)頁越來越多 ,再大型的搜索引擎也不可能做到真正的 一網(wǎng)打盡 2) 當(dāng)搜索引擎的數(shù)據(jù)庫越來越大時(shí)，用戶查詢同一個(gè)關(guān)鍵詞所得到的結(jié)果也就越來越多， 然而成千上萬的結(jié)果對(duì)用戶并沒有什么實(shí)際意義，用戶關(guān)心的是能否迅速在開頭幾十個(gè)結(jié)果中找到自己需要的信息 面對(duì)著這兩個(gè)難題，目前很多搜索引擎都在發(fā)生一些變化，這些變化中包含著搜索引擎未來的發(fā)展趨勢(shì)。 個(gè)性化服務(wù) 使用自動(dòng)獲得的領(lǐng)域模型 ,用戶模型 (如用戶背景 ,興趣 ,行為 ,風(fēng)格 )等進(jìn)行信息采集 ,索引 ,過濾 (包括興趣過濾和不良信息過濾 )對(duì)用戶有用的信息提交給用戶 . 目錄占據(jù)主導(dǎo)地位 北京大學(xué)學(xué)士論文第 6 頁 目錄與基于 搜索引擎相比更具優(yōu)越性，這一點(diǎn)已為大多數(shù)人所接受， 在今后的發(fā)展中，目錄將會(huì)占據(jù)主導(dǎo)地位，而基于 搜索引擎將更多地以輔助工具的面貌出現(xiàn)。 采用分布式體系結(jié)構(gòu)提高系統(tǒng)規(guī)模和性能 當(dāng)系統(tǒng)規(guī)模越來越大的時(shí)候 ,必然要采用某種分布式的方法 ,以提高系統(tǒng)性能 ,都可以進(jìn)行分布式 :如 :以在多臺(tái)機(jī)器上相互合作 ,相互分工的進(jìn)行信息發(fā)現(xiàn) . 特殊搜索引擎越來越多 搜索引擎的另外一個(gè)發(fā)展趨勢(shì)是特殊搜索引擎越來越多，這些特殊搜索引擎只收集了某個(gè)方面的網(wǎng)站或網(wǎng)頁，例如文學(xué)、醫(yī)學(xué)、體育、音樂、件等等，其中的內(nèi)容一般都要 比通用搜索引擎更好更精，因此很受用戶的歡迎。建立特殊搜索引擎的成本要遠(yuǎn)小于通用搜索引擎，這也促進(jìn)了它的發(fā)展。 也就是本文所要介紹的 面向主題的搜索引擎 . 向主題的搜索引擎 面向主題 ” 目前 ,通用的搜索引擎確實(shí)有了很多的發(fā)展 ,從技術(shù)以及硬件條件上 ,都有了很大的變化 ,但是事實(shí)上 ,即使最大的搜索引擎目前也僅能覆蓋 30%網(wǎng)絡(luò) 一般需要幾個(gè)星期 ,甚至幾個(gè)月 這主要是因?yàn)橥ㄓ玫乃阉饕娴囊粋€(gè)主要指導(dǎo)思想是 ”一網(wǎng)打盡 ”他們?cè)噲D迎合每一種可能出現(xiàn)的查詢請(qǐng)求 ,雖然這種講究高覆蓋率的搜索引擎是有其不可估量的價(jià)值 ,但是卻往往導(dǎo)致了 其搜集的網(wǎng)頁 ,在內(nèi)容上過于分散 往往導(dǎo)致查詢時(shí) ,有很多并不相關(guān)的網(wǎng)頁 . 因此隨著網(wǎng)絡(luò)的發(fā)展 ,我們需要一種新形式的搜集系統(tǒng) . 很容易的我們想到 ,用 相關(guān)度 以及 網(wǎng)頁質(zhì)量 來過濾搜集的網(wǎng)頁 對(duì)于一個(gè)個(gè)人來說 ,他所關(guān)心的始終只是一小部分 收藏起來 ,然后他所關(guān)心的也就是與這些例子類似的網(wǎng)頁 . 因此通用的搜索引擎是不 適合這種目的的 基于關(guān)鍵字(查詢是很難達(dá)到這種目的 : 將網(wǎng)頁正確的與某個(gè)主題聯(lián)系起來 我想查 唱 歌手 李小龍 , 如果用通用的搜索引擎的話 ,他很可能把拍武打片的李小龍 , 甚至是 263 的李小龍全都返回 結(jié)果會(huì)好一點(diǎn) 讓用戶很沮喪 . 北京大學(xué)學(xué)士論文第 7 頁 正是因?yàn)橛性S多是通用的搜索引擎所無法實(shí)現(xiàn) ,或?qū)崿F(xiàn)的不好的 ,因此我們就需要有一種小巧 ,精致的搜索系統(tǒng) 面向主題 ” 面向主題 就是只針 對(duì)一類主題 ,一類網(wǎng)頁 , 例如文學(xué)、醫(yī)學(xué)、體育、音樂、件等等 ,進(jìn)行搜集 . 也就是說只搜集網(wǎng)絡(luò)的一個(gè)子集 主題 : 也就是用戶所要搜集的類型定義 也可以由一系列描述類型特征的特征詞來確定 . 相對(duì)與通用的搜集系統(tǒng)而言 ,它更為小巧 但是 其中的內(nèi)容一般都要比 通用的 搜索引擎更好更精，因此很受用戶的歡迎。建立 面向主題的搜集系統(tǒng) 的成本要遠(yuǎn)小于 通用的 搜索引擎，這也促進(jìn)了它的發(fā)展 . 它所涉及的主要技術(shù) 有 :信息挖掘 ,文本分類 ,文本提取 ,網(wǎng)絡(luò)搜集 ,入度出度 等等 先有用戶確定一系列的樣本網(wǎng)頁 ,來確定所搜集的主題 , 然后進(jìn)行特征提取 , 分析樣本網(wǎng)頁 ,提取特征信息 ,之后再搜集過程中 ,根據(jù)這些特征信息 ,對(duì)每一個(gè)搜集的網(wǎng)頁 ,都賦予一定的相關(guān)度 就說明 與主題越相似 . 目前國內(nèi)的面向主題的搜集系統(tǒng)還出于起步階段 ,尚沒有很成熟的系統(tǒng) 也就是分類的搜索 ) 一般都是采用人工分類的形式 只要面向主題的搜集 算法足夠好 ,在很大程度上可以代替這種人工分類的 方法 . 好的 ”面向主題搜集系統(tǒng) 這也就涉及到面向主題的 評(píng)價(jià)指標(biāo)的問題 速度快 所謂速度快 ,不是指一臺(tái)機(jī)器每天能搜集多少網(wǎng)頁 ,而是說能夠在盡可能快的時(shí)間能覆蓋大面積的網(wǎng)絡(luò) 如果說通用的搜索引擎需要 10 天來覆蓋 30%的網(wǎng)絡(luò) ,那么 面向主題只需要 3 天就能夠覆蓋 30%的網(wǎng)絡(luò) . 聚集度高 也就是搜集到的網(wǎng)頁 ,必須是高度相關(guān)的 , 不允許將主題外的搜集進(jìn)來 , 覆蓋完全 也就是說覆蓋盡可能大的網(wǎng)絡(luò) ,保證每一個(gè)屬于主題內(nèi)的網(wǎng)頁被搜集也就是 (完全性 ),而第二點(diǎn) 是保證 , 每一個(gè)被搜集的 都是主題內(nèi) 北京大學(xué)學(xué)士論文第 8 頁 者的區(qū)別比較 對(duì)于通用的搜索引擎和面向主題的搜索引擎 ,二者之間是有差別的 ,面向的需求不同 ,各有千秋 ,或是有了通用的就不要面向主題了 . 面向主題的搜索引擎 (下簡(jiǎn)稱為 主題 ) 與通用的搜索引擎 (下簡(jiǎn)稱為 通用 )有一下幾點(diǎn)區(qū)別 : 目的不同 通用 : 搜集盡可能多的網(wǎng)頁 , 一網(wǎng)打盡 主題 : 搜集某一領(lǐng)域內(nèi)的網(wǎng)頁 . 兵貴在精 面對(duì)需求不同 通用 : 各種 各樣的檢索請(qǐng)求 主題 領(lǐng)域內(nèi)部的檢索請(qǐng)求 策略不同 通用 : 面對(duì)各種不同的網(wǎng)頁 ,一視同仁 ,同樣處理 主題 :對(duì)于各種不同類的網(wǎng)頁 ,區(qū)分對(duì)待 表 1二者的區(qū)別 通用的搜索引擎 面向主題的搜索引擎 數(shù)據(jù)量大 : 這是因?yàn)樗鸭械木W(wǎng)頁 數(shù)據(jù)量小 : 這是因?yàn)樗凰鸭糠志W(wǎng)頁 ,其余的都拋棄了 更新慢 : 因?yàn)槠鋽?shù)據(jù)量太大 ,更新一次往往要數(shù)周 ,甚至上月 更新快 : 因?yàn)閿?shù)據(jù)量小 ,能夠迅速更新 ,周期只要數(shù)天即可 . 博而不精 : 數(shù)據(jù)量大 ,但是太過 分散 ,沒有重點(diǎn) 精而不博 : 數(shù)據(jù)量小 , 集中 ,但是只限于本領(lǐng)域 數(shù)據(jù)不完全 : 這里指的是相對(duì)與它的搜集目標(biāo)而言 ,最多覆蓋網(wǎng)絡(luò)的 30數(shù)據(jù)較完全 : 相對(duì)與它的搜集目標(biāo) ,因?yàn)楸緛碓擃I(lǐng)域范圍內(nèi)的網(wǎng)頁就少 ,就可能搜集的較完全 硬件需求高 : 通用的往往需要上 G 的內(nèi)存 ,上百臺(tái)的機(jī)器才能使得搜集成一定規(guī)模 硬件需求低 : 目前我們的搜索引擎僅用了一臺(tái)機(jī)器進(jìn)行搜集 . 北京大學(xué)學(xué)士論文第 9 頁 問題 : 如我們搜 游泳 方面的信息 游泳 , 和用面向主題的搜集 系統(tǒng)搜集 游泳 領(lǐng)域 , 結(jié)果有區(qū)別馬 ? 答案 : 當(dāng)然有區(qū)別 , 1) 用面向主題 , 我們可能搜集出 網(wǎng)頁中不出現(xiàn) 游泳 ,但是確實(shí)與游泳的相關(guān)的網(wǎng)頁 , 如講述泳鏡之類的網(wǎng)頁 2)只要例子網(wǎng)頁選擇的好 , 面向主題所搜集的大部分都是與游泳相關(guān)度高的 ,而通用搜索引擎就做不到這一點(diǎn) 3) 也就是面向主題的搜集系統(tǒng)所搜集的相關(guān)網(wǎng)頁必然多于 通用所檢索得到 . 因此 ,我們可以看出 ,在網(wǎng)絡(luò)蓬勃發(fā)展的今天 ,發(fā)展面向主題的搜索引擎是很有必要的 . 北京大學(xué)學(xué)士論文第 10 頁 第二章 天網(wǎng)搜索引擎的介紹 網(wǎng)系統(tǒng)簡(jiǎn)介 因?yàn)槲覀兯鶎?shí)現(xiàn)的面向主題的搜索引擎 ,是基于天網(wǎng)搜索引擎之上完成 天網(wǎng)中英文搜索引擎是主要針對(duì)中國 豐富的信息資源而開發(fā)的具有中文特色的搜索引擎。天網(wǎng)屬于基于 搜索引擎范疇，主要采取了基于服務(wù)器模式具有導(dǎo)向功能的搜索和提供文本摘要的方式。在實(shí)現(xiàn)中，天網(wǎng)使用了中文自動(dòng)識(shí)別和中文編碼自動(dòng)轉(zhuǎn)換技術(shù)、根據(jù)中文的語言特點(diǎn)和表達(dá)習(xí)慣對(duì)中文信息進(jìn)行詞語切分和詞類標(biāo)注技術(shù)以及基于詞 的大型、高效的信息索引數(shù)據(jù)庫和快速準(zhǔn)確的檢索技術(shù)等先進(jìn)的中文信息處理和索引技術(shù)，從而大大提高了中文信息的理解程度和發(fā)現(xiàn)、檢索效率，同時(shí)也提高了漢語的查準(zhǔn)率。 目前 天網(wǎng)由若干 主控 (導(dǎo)向控制下，使用具有高度智能性和適應(yīng)性的信息發(fā)現(xiàn)算法搜索網(wǎng)頁，提取關(guān)鍵詞及摘要，形成原始數(shù)據(jù)庫，然后在此基礎(chǔ)上建立索引數(shù)據(jù)庫。 來自前端的用戶信息，傳給檢索服務(wù)器，經(jīng)過查詢優(yōu)化，產(chǎn)生結(jié)果回送用戶。 天網(wǎng)搜索引擎的檢索是基于詞匯的，克服了中文分詞的困難，同時(shí)具有中英文詞匯自動(dòng)學(xué)習(xí) 的能力。 它側(cè)重于中文信息的發(fā)現(xiàn)，向全世界的中文用戶提供準(zhǔn)確、有效的網(wǎng)絡(luò)中文信息。 天網(wǎng)搜索引擎具有以下技術(shù)特征： 信息收集符合 相關(guān)協(xié)議和標(biāo)準(zhǔn)。 實(shí)用、高效的信息分析方法 高度智能性和適應(yīng)性的信息發(fā)現(xiàn)方法 中文信息處理技術(shù) 可伸縮的分布式結(jié)構(gòu) 基于詞的大型、高效的信息索引數(shù)據(jù)庫和快速、準(zhǔn)確的檢索方法 智能化、多功能的用戶檢索接口 天網(wǎng)搜索引擎目前訪問量以及搜集網(wǎng)頁數(shù)已經(jīng)達(dá)到了千萬 天網(wǎng) 由于采用了可伸縮的分布式結(jié)構(gòu)、查詢 引數(shù)據(jù)庫和檢 索數(shù)據(jù)庫分開等先進(jìn)、有效的技術(shù)，使得系統(tǒng)占用資源少、信息收集速度快、用戶查詢響應(yīng)時(shí)間快（系統(tǒng)對(duì) 上的查詢可在 1 秒鐘之內(nèi)作出響應(yīng)）、查準(zhǔn)率和查全率較高，基本達(dá)到了實(shí)用化程度。 北京大學(xué)學(xué)士論文第 11 頁 網(wǎng)的總體結(jié)構(gòu) 本系統(tǒng)主要由 息存取和分析子系統(tǒng) ( 息搜集控制子系統(tǒng) (資源索引數(shù)據(jù)庫 (信息檢索子系統(tǒng) (管理和監(jiān)控子系統(tǒng) (幾個(gè)部分組成 系統(tǒng)的結(jié)構(gòu)圖如下 : 檔 存取分析子系統(tǒng) 搜集控制子系統(tǒng) 信息檢索子系統(tǒng) 務(wù)器 資源索引數(shù)據(jù)庫 覽器 覽器 2網(wǎng)的總體結(jié)構(gòu) 理和監(jiān)控子系統(tǒng) 存取分析子系統(tǒng) 北京大學(xué)學(xué)士論文第 12 頁 第三章 搜集策略的介紹和比較 述 主題搜索的實(shí)現(xiàn)多種多樣 ,但是如果把它們的框架去出來 ,都是大同小異 a) 確立例子網(wǎng)頁 也就是由用戶選擇例子網(wǎng)頁 ( 來確定系統(tǒng)所要搜集的主題 與主題相關(guān)性越強(qiáng) ,最后搜集的效果越好 . 因?yàn)槲覀兊恼麄€(gè)系統(tǒng)的目標(biāo)就是搜集 盡可能多的與例子網(wǎng)頁盡可能相似的網(wǎng)頁 若各自在內(nèi)容上相關(guān)性不強(qiáng) ,將會(huì)導(dǎo)致所提取的特征信息不具有代表性 ,是的搜集失敗 . 因此用戶應(yīng)該慎重選擇 例子網(wǎng)頁 . b) 提取特征信息 其實(shí)是一個(gè)文本提取的過程 ,也就是 (有些系統(tǒng)如 (實(shí)現(xiàn)的系統(tǒng) ,)把這一部分稱為 它的目的 :根據(jù) 例子網(wǎng)頁 ,用一系列的特征詞 ,以及特征詞權(quán)值來描述該主題 根據(jù)特征詞 ,特征詞權(quán)值而展開 . 特征詞 :就是一個(gè)關(guān)鍵詞 他能夠標(biāo)志主題的特征 標(biāo)志了該特征詞于該主題的相關(guān)程度 . 權(quán)值越高 ,說明該特征促于主題越相關(guān) ,越 能夠代表該主題的特征 . 因此特征詞 ,以及其權(quán)值的選擇 決定了系統(tǒng)搜集 的好壞 . c) 信息采集 其實(shí)是一個(gè)文本分類的過程 對(duì)網(wǎng)絡(luò)中的網(wǎng)頁進(jìn)行篩選 系統(tǒng)運(yùn)行前的準(zhǔn)備工作 它的目的是根據(jù)前一步所確定的特征信息 ,搜集網(wǎng)頁 盡可能于例子網(wǎng)頁相關(guān)度高的網(wǎng)頁 . 性能指標(biāo) :我們可以用以下兩個(gè)性能指標(biāo)來衡量搜集系統(tǒng)的好壞 : 北京大學(xué)學(xué)士論文第 13 頁 召回率 (檢索出的相關(guān)文檔數(shù)和文檔庫中所有的相關(guān)文檔數(shù)的比率，衡量的是檢索系統(tǒng)（搜索引擎）的查全率； 精度 (檢索出的相關(guān)文檔數(shù)與檢索出的文檔總數(shù)的比率，衡量的是檢索系統(tǒng)（搜索引擎）的查準(zhǔn)率。 對(duì)于一個(gè)檢索系統(tǒng)來講，召回率和精度不可能兩全其美：召回率高時(shí)，精度低，精度高時(shí)，召回率低。 下面我們將分別對(duì)這三步驟中的策略進(jìn)行詳細(xì)介紹 . 定例子網(wǎng)頁 確定例子網(wǎng)頁 ,由用戶確定幾個(gè)主題典型的 用來配置系統(tǒng) 1. 幾個(gè) 應(yīng)該是同一個(gè)站點(diǎn)的 , 2. 幾個(gè) 容應(yīng)該于主題密切相關(guān) 3. 幾個(gè) 好文字較多 ,這樣文本提取的效果會(huì)較好 . 4. 幾個(gè) 該是該主題中典型的網(wǎng)頁 . 用戶應(yīng)該認(rèn)真選擇 征提取部分的幾種策略 目的 : 根據(jù) 例子網(wǎng)頁 ,用一系列的特征詞 ,以及特征詞權(quán)值來描述該主題 集應(yīng)該 : 能體現(xiàn)例子網(wǎng)頁所包含的內(nèi)容 (完全性 ) 這是容易做到的 有了這一點(diǎn)我們就可以確定那些網(wǎng)頁與目標(biāo)相關(guān) 能體現(xiàn)例子網(wǎng)頁所不包含的內(nèi)容 (區(qū)分性 ) 這是難于實(shí)現(xiàn)的 但是因?yàn)槟壳安] 有一個(gè)很好的算法能夠?qū)崿F(xiàn)這一點(diǎn) ,因此我們只能確定這個(gè)網(wǎng)頁相關(guān) ,并不能確定這個(gè)網(wǎng)頁于主題不相關(guān) 下面將介紹兩種用于特征提取的算法 : 1) 基于統(tǒng)計(jì)的算法 2) 支持向量機(jī) ( 北京大學(xué)學(xué)士論文第 14 頁 于統(tǒng)計(jì)的算法 每個(gè)網(wǎng)頁 ,都會(huì)有一個(gè) ,甚至不只一個(gè)主題 網(wǎng)頁有的就只有 詞 因此我們的算法就是把想辦法把主題和這些詞聯(lián)系起來 . 顧名思義 ,基于統(tǒng)計(jì)的算法也就是 計(jì)其中出現(xiàn)過的關(guān)鍵詞，建立關(guān)鍵詞詞典 ,根據(jù)每個(gè)詞在網(wǎng)頁中的出現(xiàn)次數(shù) ,出現(xiàn)位置來計(jì) 算它的權(quán)值 ,最后 ,由這些信息 , 綜合多個(gè)網(wǎng)頁 , 來確定該主題的特征詞 ,以及特征詞的權(quán)值 . 答案 : 當(dāng)然不是 . 類比與圖象壓縮處理中所提到的 ,經(jīng)常出現(xiàn)的 ,所包含的信息量就越少 在網(wǎng)頁中越常出現(xiàn)的 , 所包含的信息量就越少 ,比如基本上每個(gè)網(wǎng)頁都會(huì)有 聯(lián)系我們 這樣的字眼 , 但是這種字眼對(duì)描述主題是沒有任何作用的 . 這也就說明了 詞頻高的未必代表主題 . 也就是說 ,一個(gè)特征在文檔中出現(xiàn)的次數(shù)越多 , 權(quán) 值越高 , 越多文檔都出現(xiàn)了這個(gè)特征 ,則這個(gè)特征反而信息量小 ,權(quán)值越低 . 因此我們可以構(gòu)造 權(quán)值評(píng)價(jià)函數(shù) 問題 : 將詞頻高的作為特征 詞 ? 特征詞的權(quán)值應(yīng)該 : 正比 于 在文檔內(nèi)出現(xiàn)的頻率 反比 于 出現(xiàn)了該特征的文檔數(shù) 北京大學(xué)學(xué)士論文第 15 頁 nk 01.0(lo g*)()g (其中 特征項(xiàng) i 中的出項(xiàng)頻數(shù) ,N 表示全部文檔的總數(shù) ,征項(xiàng)的文檔數(shù) . 基于統(tǒng)計(jì)的算法 ,實(shí)現(xiàn)起來簡(jiǎn)單 ,思想直接 ,易懂 ,但是它存在很大毛病 ,就是對(duì)高頻詞的處理 ,詞頻太高 ,有可能是忽略詞 ,或是無意義的詞 ,詞頻太低 ,也就不具有代表性 這里的一個(gè)權(quán)衡就是很關(guān)鍵的 . 持向量機(jī) (支持向量機(jī) (一種機(jī)器學(xué)習(xí)的方法 通過訓(xùn)練文本 ,以自動(dòng)尋找出那些對(duì)分類有較好區(qū)分能力的支持向量 ,由此構(gòu)造出的分類器可以最大化類與類的間隔 假設(shè)訓(xùn)練文本為 ),(ii . 其中 , 也就是是一個(gè) m 維的向量 . 1. 其中 表示 ,否則就是一個(gè)反面例子 . 法先執(zhí)行了一個(gè)映射 , 從 m 維到 n 維空間的映射 ,通常 ,n 大大于 m.,這樣 訓(xùn)練向量就被映射到一個(gè) 更高緯度的空間中 )( 這個(gè)超平面經(jīng)過優(yōu)化之后 ,保證 正面例子 和反面例子之間的 距離最大 .系數(shù) W 可以寫成 )(x 的線性組合 . W= 而這些i可以用一下的 二次方程解得 : 基于統(tǒng)計(jì)算法的評(píng)估 北京大學(xué)學(xué)士論文第 16 頁 ( )= 1)()(21 而對(duì)于這些i還必須滿足一下的約定 01Ni 同時(shí) i 0 由此可以確定了 超平面 ,確定了 分類器 一種很復(fù)雜的算法 ,具體情況情參見參考文獻(xiàn) 11 有較好的推廣新能和較高的分類準(zhǔn)確率 經(jīng)被用于孤立的手寫體識(shí)別 ,語音識(shí)別 ,人臉識(shí)別 其算法復(fù)雜 ,對(duì)于網(wǎng)頁分類這種大規(guī)模的數(shù)據(jù)集而言 ,訓(xùn)練例子往往要很多 ,才能夠找一個(gè)好的分類器 要的訓(xùn)練時(shí)間也太長 ,計(jì)算也太復(fù)雜 . 集 部分的策略 目的 :在運(yùn)行中利用前一步得到的特征值信息 ,進(jìn)行網(wǎng)頁的搜集 . 搜集到盡可能于例子網(wǎng)頁相似的網(wǎng)頁 , 盡可能于例子網(wǎng)頁相關(guān)度高的網(wǎng)頁 下面我們將介紹兩個(gè)搜集時(shí)的策略 1) 向量空間模型 2) 接關(guān)系的考慮 量空間模型 目標(biāo)表示是指以一定的特征項(xiàng) (即關(guān)鍵詞 ,特征詞 )來表示目標(biāo)網(wǎng)頁信息 ,目標(biāo)表示的模型有很多種 ,常用的有 布爾邏輯型 ,向量空間型 ,概率型等 . 在 ,將例子網(wǎng)頁經(jīng)過特征提取之后 , 看作是由一組特征項(xiàng) ( ., 構(gòu)成 ,對(duì)于每一個(gè)特征項(xiàng) ,根據(jù)其在網(wǎng)頁中的重要程度 賦以一定的權(quán)值 所以例子網(wǎng)頁可以寫成用 (,(, ., 法 的評(píng)估 北京大學(xué)學(xué)士論文第 17 頁 (n), 來表示 . 而所有待分類的網(wǎng)頁都可以寫成 ( ,其中 . 這樣我們就構(gòu)造一個(gè) n 維坐標(biāo)系 ,以特征項(xiàng)為其坐標(biāo)軸 ,(w1, 其對(duì)應(yīng)的坐標(biāo)值 D(t1,t2, , 假設(shè) 例子網(wǎng)頁的特征向量為 W,那么檢驗(yàn)網(wǎng)頁 D 和例子的相關(guān)程度 ,就裝化為向量空間中 兩個(gè)向量的夾角來度量 相似程度越高 相似度 (D,W)=,W)=其實(shí)就是計(jì)算兩個(gè)向量之間夾角的余弦 ,這個(gè)值越大 ,角度越小 ,相似程度越高 , 還有些算法 ,也構(gòu)架向量空間模型 ,但是并不采用上面的公式 ,而是采用一個(gè)函數(shù) ,來對(duì)這兩個(gè)向量進(jìn)行計(jì)算 , 通過計(jì)算結(jié)果來判斷相關(guān)程度 . 如 :最簡(jiǎn)單的線性函數(shù) F(X)= D*W = jj 結(jié)果高的就認(rèn)為相關(guān)程度高 . 據(jù)我所知 , 向量空間模型是比較形象的一種建模方式 ,實(shí)現(xiàn)起來也比較容易 . 但是有一個(gè)很大的缺陷 就是向量空間模型最初的提出主要是針對(duì)文本分類 于普通的文本 相比 ,檔中有著很明顯的標(biāo)志符 ,結(jié)構(gòu)信息更加的明顯 ,對(duì)象的屬性更加的豐富 將會(huì)遺漏了很多 有用的信息 . 向量空間模型的評(píng)估 北京大學(xué)學(xué)士論文第 18 頁 接關(guān)系的考慮 (s 就是超鏈接文本 ,網(wǎng)絡(luò)上的信息就是有許多的連接而組合在一起的 . 因此 ,我們?cè)谘芯?檔之間的關(guān)系時(shí) ,這些連接就是一個(gè)很好的信息源 ,能夠提供給我們?cè)S多有效的信息 . 所有對(duì)這些連接關(guān)系的研究都是基于一下兩個(gè)假設(shè)的 : 兩個(gè) 間存在連接 這兩個(gè) 含相關(guān)的內(nèi)容 許多網(wǎng)頁都指向同一個(gè)網(wǎng)頁 這個(gè)網(wǎng)頁是很重要的 用圖來表示 ,如下圖 .(其中 A B 表示有一個(gè)從 A 到 B 的連接 ) 圖 3說明假設(shè) 1 圖 3明假設(shè) 2 但是 ,我們可以很容易的看出這個(gè)假設(shè)其實(shí)并不是完全正確 兩個(gè)網(wǎng)頁之間 存在連接 ,并不一定表示二者之間存在相關(guān)性 是 ,門戶網(wǎng)站與各種各樣的網(wǎng)頁之間都存在連接 ,但是并不表示他們之間在內(nèi)容上又相關(guān)性 下面介紹一種利用鏈接關(guān)系的算法 s 和 權(quán)威程度 ( 一個(gè)具有高權(quán)威程度的網(wǎng)頁 ,就很有可能具有相關(guān)的內(nèi)容 一個(gè)具有高中心程度的網(wǎng)頁 ,就很有可能擁有指向相關(guān)頁的連接 . 檔 A 檔 B A 于 B 相關(guān) 檔 檔 C C 是一個(gè)重要的頁面 北京大學(xué)學(xué)士論文第 19 頁 換句話說 ,也就是 , 一個(gè)網(wǎng)頁擁有 許多指向其他相關(guān)頁的連接 ,它的 高 . 而一個(gè)網(wǎng)頁被許多 相關(guān)頁所指向 , 它的 越高 . 更進(jìn)一步說 ,一個(gè)網(wǎng)頁如果擁有許多指向那些 的網(wǎng)頁的連接 ,那么他的 當(dāng)然就越高 一個(gè) 果被許多 指向 ,他的也就越高 . 在具體實(shí)現(xiàn)中 ,我們要注意幾個(gè)問題 , 1. 在同一個(gè)主機(jī)中的網(wǎng)頁 ,往往有一些互相之間的連接 ,比如什么 回到主頁 之類的連接 , 但是這 種連接 是作者自己加入的 ,并不能又什么導(dǎo)航性 值的時(shí)候 ,這種連接應(yīng)該不加以考慮 . 2. 在計(jì)算 ,時(shí)候 ,往往能以完全計(jì)算 ,算 ,只是一個(gè)出度 .而 涉及到入度 ,網(wǎng)海茫茫 ,入度 是無法完全計(jì)算的 如果入度已經(jīng)達(dá)到了上限 ,就不再計(jì)算了 . 因此我們可以知道在具體實(shí)現(xiàn)的過程 ,我們只需要統(tǒng)計(jì)網(wǎng)頁的入度 ,出度 , 根據(jù)入度出度統(tǒng)計(jì)網(wǎng)頁的 ,以及 不斷 被修改的 . 出度高的 , 往往 比較高 ,入度高的往往 高 . 這種算法充分考慮了超文本的特征 ,能夠充分挖掘了鏈接所包含的信息 ,對(duì)發(fā)掘相關(guān)性有很大的幫助 . 但是 ,這種算法也有很大的弊病 . 1) 因?yàn)橥粋€(gè)主機(jī)上的一系列網(wǎng)頁往往是同一個(gè)作者 ,那么他往往可能使得這一系列網(wǎng)頁都指向一個(gè)他認(rèn)為重要的頁面 ,這樣會(huì)大幅度 提高 該頁面的 相關(guān)頁 相關(guān)頁 相關(guān)頁 相關(guān)頁 . . . . 關(guān)頁 相關(guān)頁 相關(guān)頁 相關(guān)頁 . . . . s 評(píng)估 北京大學(xué)學(xué)士論文第 20 頁 2) 這種算法會(huì)導(dǎo)致 , 網(wǎng)頁的 循環(huán)增大 . 比如說 , 網(wǎng)頁 A 有一 個(gè)連接指向 網(wǎng)頁 B 那么 B 的 增大 A 的 增大 而 A 的 增大 又會(huì)導(dǎo)致 B 的 增大 這樣循環(huán)增大 ,將是導(dǎo)致算法一無是處 必須采用一定的策略來避免這一點(diǎn) . 3) 不相關(guān)的節(jié)點(diǎn) :這就是前面所提到過的假設(shè)其實(shí)并不完全成立 . 有些網(wǎng)頁上往往會(huì)有一些連接是指向不相關(guān)的頁面 ,這樣的計(jì)算將會(huì)導(dǎo)致偏差 結(jié) 這一章我 們主要是介紹了 用于面向主題搜索的各種算法 1. 確定例子網(wǎng)頁 2. 進(jìn)行特征提取 3. 信息采集 在特征提取部分我介紹了兩種算法 : 基于統(tǒng)計(jì)的算法 :也就是統(tǒng)計(jì)詞頻 ,經(jīng)過一定的公式計(jì)算 其權(quán)值 ,取出 特定的作為特征項(xiàng) . 支持向量機(jī)的算法 . 通過學(xué)習(xí)算法 ,自動(dòng)尋找對(duì)分