（計算機軟件與理論專業(yè)論文）web聚類技術及其在搜索引擎中的應用.pdf

y 7 4 6 1 9 8 w e b 聚類技術及其在搜索引擎中的應用 計算機軟件與理論 研究生李戰(zhàn)勝指導教師杜亞軍 摘要 搜索引擎是當前研究的熱門技術之一 用戶通過輸入查詢詞來獲取搜索結(jié) 果 從而能夠在海量的互聯(lián)網(wǎng)資源中獲取有用信息 然而 當前搜索引擎返回 的搜索結(jié)果數(shù)目非常龐大 要從這么多的結(jié)果中找到有用信息 有時顯得很困 難 如何更好地顯示搜索結(jié)果 更好地幫助用戶找到自己感興趣的信息 是本 文所要研究和解決的問題 幸運地是 利用聚類技術對搜索結(jié)果按主題聚類 將很好地表現(xiàn)搜索結(jié)果 顯然 傳統(tǒng)的聚類技術一般都是針對數(shù)值數(shù)據(jù)進行的 而對于文本數(shù)據(jù) 尤其 是w e b 文檔類型的數(shù)據(jù) 需要新的能夠處理高維 實時的聚類算法 并在文本 特征提取和時間復雜廢方面有更高的要求 本文提出的新的聚類算法m y c l u s t e r 是基于短語和潛在語義索引基礎上的 針對搜索結(jié)果的模糊w e b 聚類算法 在m y c l u s t c r 聚類算法中采用由多個有序 詞構成的短語來建立文檔特征向量 雨不是傳統(tǒng)方法上用單個詞來建立 這樣 可以有效地避免數(shù)據(jù)噪音的干擾 而且還可以明顯地降低特征矩陣的維度 縮 減計算時間 w e b 文檔特征矩陣的建立將涉及w e b 文檔的下載和解析 關鍵短 語和非關鍵短語的識別和中文分詞等關鍵技術 w e b 聚類結(jié)果由類標簽和類內(nèi)容構成 每個類標簽都對應著許多類內(nèi)容 即搜索結(jié)果 每個類標簽代表著一個主題 顯然類標簽的可讀性 也即主題鮮 明 將直接影響用戶查找信息的命中率 當然 類內(nèi)容是用戶獲取最終信息的 入口 它與類標簽的相關性就很重要 我們采用線性代數(shù)中奇異值分解方法來 發(fā)現(xiàn)類內(nèi)容和歸納類標簽 使類內(nèi)很相似 類間不相似 而且類內(nèi)容很好地關 聯(lián)了類標簽 對形成的類標簽和類內(nèi)容 采用合并和排序策略 將很好地修正 聚類結(jié)果 為了更好地測試m y c l u s t e r 算法的聚類效果 本文給出了基于m y c i u s t c r 算法的聚類搜索b l 擎框架及聚類結(jié)果評價體系 實現(xiàn)聚類搜索引擎的過程中將 涉及多種編程語言 例如h t m l j a v a s c r i p t c g i 和 等 和數(shù)學軟件m a t l a b 并實現(xiàn)了 在脫離m a t l a b 環(huán)境情況下對m a t l a b 生成的動態(tài)鏈接庫的直接調(diào) 用 我們的聚類結(jié)果評價體系通過類標簽的可讀性 類內(nèi)容的相關性 類內(nèi)容 覆蓋率和類重疊度等指標 來綜合評價一個算法質(zhì)量的好壞 通過對比實驗 我們發(fā)現(xiàn)m y c l u s t e r 在類標簽可讀性和類內(nèi)容相關性方面 有很大地優(yōu)勢 但在類內(nèi)容覆蓋率方面有所欠缺 希望未來將能有所改進 并 在增量聚類等方面作進一步的研究 關鍵詞 聚類搜索引擎 w e b 搜索結(jié)果聚類算法 奇異值分解 m y c l u s t e r i i a b s t r a c t c u r r e n t l y t h et e c h n o l o g yo fs e a r c he n g i n ei sa h o ti ni r r e s e a r c h o n l y au s e f c a ni n p u tf lq u e r ya n dg e ts o m es e a r c hr e s u l t s s ot h a tt h e yc a nr e a l i z et h ed r e a mo f g e t t i n gt h eu s e f u li n f o r m a t i o nf r o mi n t e r a c t b u t t h et o t a ln u m o fs e a r c hr e s u l t si s v e r yl a r g e a n di ti sd i f f i c u l tf o ru s e r st of i n dt h eu s e f u li n f o r m a t i o n i nt h o s er e s u l t s h o wt oo r g a n i z et h es e a r c hr e s u l ta n dh o wt of m dt h eu s e f u li n f o r m a t i o n t h i s t h e s i sw i l la s kt h o s eq u e s t i o n s f o r t u n a t e l y c l u s t e r i n ga c c o r d i n g t ot h et h e m e so ft h es e a r c hr e s u l t sw i l lb ew e l l t oh e l pu s e rt of i n dt h ei n f o r m a t i o nt h e ya r ei n t e r e s t e d a p p a r e n t l y t h ec o n v e n t i o n a l t e c h n o l o g i e so n l y d e a lw i t ht h en u m e r i c a ld a t ar a t h e rt h a nt h et e x t u a ld a t a e s p e c i a l l y f o rd e a l i n gw i t ht h ew e bt e x t u a ld a t a w ep r o p o s ean e wc l u s t e r i n g a l g o r i t h m t h en e wc l u s t e r i n ga l g o r i t h m n a m e dm y c l u s t e r i saf u z z yw e b c l u s t e r i n g a l g o r i t h mb a s e do nt h ep h r a s ea n dl a t e n ts e m a n t i ci n d e x i n g i ti si m p o r t a n tt of o r m ae i g e nv e c t o ro fd o c u m e n t sa n dw e t r yt of o r mi tb yu s i n gp h r a s e sc o n s t i t u t e db y s o m es e q u e n c e dw o r d sr a t h e rt h a no n ew o r d t h ea l g o r i t h mw i l le f f e c t i v e l ya v o i d t h ed i s t u r bo fd a t an o i s e d e c r e a s et h ed i m e n s i o no fe i g e nm a t r i xa n ds a v et h et i m e f o rc o m p u t i n g f o rf o r m i n gt h ee i g e nm a t r i x i tw i l li n c l u d et h ek e yt e c h o n o l o g i e s s u c ha s d o w n l o a d i n ga n dp a r s i n gw e bd o c u m e n t s i d e n t i f y i n gk e yp h r a s e sa n d g e n e r a lp h r a s e s a n dc h i n e s ew o r d sd i v i d e d s y n c o p a t i o nt e c h n o l o g y e t c t h er e s u l to fm y c l u s t e ri sc o m p o s e do fc l a s sl a b e l sa n dc l a s sc o n t e n t s e a c h c l a s sl a b e l c o r r e s p o n d i n g s t os o m ec l a s sc o n t e n t s n a m e l ys e a r c h r e s u l t s c l e a r l y t h e r e a d a b i l i t y o fc l u s t e rl a b e l sw i l l d i r e c t l y e f f e c tt h er a t eo f f i n d i n g au s e f u l i n f o r m a t i o n c e r t a i n l y t h ec l a s sc o n t e n t s i sa e n t r yf o ru s e r sg e t t i n gt h ei n f o r m a t i o n a n dt h er e l a t i o nb e t w e e nt h ec l a s sc o n t e n t sa n dt h ec l a s sl a b e l si sv e r y i m p o r t a n t w e u s eam e t h o do f s i n g u l a rv a l u ed e c o m p o s i t i o nt oi n d u c ec l a s sl a b e l sa n df i n dc l a s s c o n t e n t s s ot h a tt h ec l u s t e r sh a v et h ec h a r a c t e r i s t i ct h a to b j e c t sb e l o n g i n gt ot h e s a m ec l u s t e ra r e s i m i l a r t oe a c ho t h e r w h i l e o b j c o t sf r o mt w od i f f e r e n tc l u s t e r sa r e d i s s i m i l a r l a s t l y w ci n c o r p o r a t ea n ds o r tt h ec l u s t e r s i i i f o rt e s t i n gt h eq u a l i t yo fc l u s t e r i n g w cp r o p o s eac l u s t e r i n gs e a r c he n g i n e b a s e do no u ra l g o r i t h mo fm y c l u s t e ra n das y s t e mo fe v a l u a t i o no fs e a r c hr e s u l t s c l u s t e r i n g i nt h ep r o c e s so fr e a l i z i n gt h ec l u s t e r i n gs e a r c hc n g i n e w ew i l ld e a lw i t h h t m l j a v a s c r i p t c g i c a n dm a t l a b e t c i no u r s y s t e m o fe v a l u a t i o no f s e a r c h r e s u l t s c l u s t e r i n g w e u s et h er e a d a b i l i t yo fc l a s sl a b e l s t h er e l e v a n c eo fd a s s c o n t e n t s t h ec o v e r a g eo fc l a s sc o n t e n t sa n dt h eo v e r l a po fc l a s st 0e v a l u a t et h e q u a l i t yo fa l g o r i t h m b ye x p e r i m e n t s o u rm y c l u s t e rh a ss o m ea d v a n t a g e so ft h er e a d a b i l i t yo fc l a s s l a b e l sa n dt h er e l e v a n c eo fc l a s sc o n t e n t s b u ti th a sad e f a u l to ft h ec o v e r a g eo f c l a s sc o n t e n t s w ew i l l r e m e d yi t i nf u t u r ea n df u r t h e r s t u d yi n t h ei n c r e m e n t c l u s t e r i n g k e y w o r d s c l u s t e r i n gs e a r c he n g i n e t h ec l u s t e r i n ga l g o r i t h mo fw e bs e a r c h r e s u l t s s i n g u l a r v a l u e d e c o m p o s i t i o n m y c l u s t e r i v 西華大學碩士學位論文 第1 章緒論 就像g o o g l e 的創(chuàng)始人所說的 我們?nèi)裟芨咨频厮褜べY料 實在已經(jīng)改 變世界 在互聯(lián)網(wǎng)高速發(fā)展的今天 人們發(fā)現(xiàn)查找信息變得越來越困難了 如何才能更有效地查找我們感興趣的信息 這一問題已經(jīng)成為眾多學者的 研究對象 在 s e l b e r g 9 9 1 中提到 這個問題即是從w e b 中找出與用戶給定查詢 詞相關的文檔集 為解決這個難題 涌現(xiàn)了眾多的搜索引擎 如g o o s e g o o s e 0 5 y a h o o y a h o o 0 5 百度 b a i d u 0 5 3 中搜 z h o n g s o u 0 5 等 然而這些搜索引 擎的搜索結(jié)果卻并不盡如人意 使用者輸入查詢詞 一般都會得到成千上萬的 搜索結(jié)果 然而其中大部分頁面都是不需要的無關資料 雖然有一些技巧試圖 給那些有較多關鍵詞或者罕見關鍵詞的頁面賦予更大的權重 卻仍然不能保證 與用戶意圖最相關的頁面一定被排在最前面 因此用戶別無選擇 只能把檢索 到的頁面一個個再篩選一遍 顯然 這浪費人的時間和精力 c u t t i n ge ta 1 9 2 等提出的稱為 s c a t t e r g a t h e r 的技術 試圖更合理的組 織搜索結(jié)果 這種技術對檢索到的結(jié)果頁面進行聚類操作 按照頁面彼此之間 的相似程度分為若干組 每組都有一個比較明確的主題 用戶可以迅速地掃描 每一組并選擇那些和他的目標最相關的組 這是一個很好的嘗試和開端 它將 很好地解決人們查找信息難的問題 此后 陸續(xù)出現(xiàn)了g r o u p e r g r o u p e r 9 9 c a r r o t 2 c a r r o t 2 0 3 1 v i v i s i m o v i v is i m o 0 5 3 等聚類搜索引擎 1 1 研究動態(tài) 搜索引擎 s e a r c he n g i n e 的鼻祖是1 9 9 0 年由m c g i l lu n i v e r s i t y 學生a l a n e m t a g e p e t e r d e u t s c h b i l lw h e e l a n 發(fā)明的a r c h i e 雖然當時w o r l dw i d ew e b 還未出現(xiàn) 但網(wǎng)絡中文件傳輸還是相當頻繁的 由于大量的文件散布在各個分 散的f t p 主機中 查詢起來非常不便 因此 a 1 a ne m t a g e 等想到了開發(fā)一個 可以用文件名查找文件的系統(tǒng) 于是便有了a r c h i e a r c h i e 是第一個自動索引 互聯(lián)網(wǎng)上匿名f r p 網(wǎng)站文件的程序 但它還不是真正的搜索弓l 擎 1 9 9 4 年4 月 s t a n f o r du n i v e r s i t y 的兩名博士生 美籍華人j e r r yy a n g 楊 致遠 和d a v i df i l o 共同創(chuàng)辦了y a h o o 隨著訪問量和收錄鏈接數(shù)的增長 y a h o o 目錄開始支持簡單的數(shù)據(jù)庫搜索 因為y a h o o 的數(shù)據(jù)是手工輸入的 所以不能 耍望盔堂堡主蘭垡笙壅 真正被歸為搜索引擎 事實上只是一個可搜索的目錄 y a h o o 中收錄的網(wǎng)站都 附有簡介信息 所以搜索效率明顯提高 1 9 9 4 年初 w a s h i n g t o n 大學c s 學生b r i a np i n k e r t o n 開始了他的小項目 w e b c r a w l e r w e b c r a w l e r 0 5 1 1 9 9 4 年4 月2 0 日 w e b c r a w l e r 正式亮相時僅包 含來自6 0 0 0 個服務器的內(nèi)容 w e b c r a w l e r 是互聯(lián)網(wǎng)上第一個支持搜索文件全 部文字的全文搜索引擎 在它之前 用戶只能通過u r l 和摘要搜索 摘要一般 來自人工評論或程序自動取正文的前1 0 0 個字 w e b c r a w l e r 后來發(fā)展成為元搜 索引擎 d e c 的a l t a v i s t a t a v i s t a 0 5 是一個遲到者 1 9 9 5 年1 2 月才登場亮相 但是 大量的創(chuàng)新功能使它迅速到達當時搜索引擎的頂峰 a l t a v i s t a 最突出的 優(yōu)勢是它的速度 a l t a v i s t a 是第一個支持自然語言搜索的搜索引擎 也是第一 個實現(xiàn)高級搜索語法的搜索引擎 如a n d o r n o t 等語法 1 9 9 8 年9 月2 7 日g o o g l e 的發(fā)布 再一次改寫了搜索引擎的發(fā)展史 它在 p a g e r a n k p a g e b r i ne ta 1 9 8 動態(tài)摘要 網(wǎng)頁快照 d a i l y r e f r e s h 多文檔格 式支持 地圖股票詞典尋人等集成搜索 多語言支持 用戶界面等功能上的革 新 象a l t a v i s t a 一樣 再一次永遠改變了搜索引擎的定義 給定一查詢詞來查找與之相關的文檔集 需要考慮三方面的因素 1 w e b 是一動態(tài)的文檔集合 它每時每刻都在更新 2 互聯(lián)網(wǎng)上存在海量的文檔 而搜索引擎僅返回與查詢詞相關的很少結(jié)果 3 如何將最相關的結(jié)果排在最 前面 以利于用戶的查找 為解決這些問題 現(xiàn)有的搜索引擎 如g o o g l e b r i n p a g e 9 8 都采用c r a w l e r 或s p i d e r 或b o o 等技術獲取互聯(lián)網(wǎng)上的文檔 經(jīng)過 索引 以所謂的查詢詞一結(jié)果列表方法把最相關的結(jié)果排在最前面 由于搜索引擎僅憑用戶的查詢詞來返回搜索結(jié)果 很低的查全率和查準率 會導致用戶需要翻很多搜索結(jié)果頁才能找到自己感興趣的信息 甚至根本找不 到 y a h o o 采用目錄的方式把互聯(lián)網(wǎng)上的文檔按類別進行分類 用戶可以按照 類別導航來查找資料 但是w e b 文檔更新很快 用人工方式編輯形成的分類目 錄顯然不適臺當前信息極度膨脹的互聯(lián)網(wǎng) 而利用人工智能方法 聚類將會很 好地解決這些問題 聚類 c l u s t e r i n g 是一個將數(shù)據(jù)集劃分為若干類 c l a s s 或簇 c l u s t e r 的 過程 并使得同一個組內(nèi)的數(shù)據(jù)對象具有較高的相似度 而不同組中的數(shù)據(jù)對 象是不相似的 如果把它應用到搜索結(jié)果上 將很好地把搜索結(jié)果分到相應地 2 西華大學碩士學位論文 類中 比如 查詢 計算機 將得到 計算機病毒 計算機考試 計算機 科研網(wǎng) 等類 對于普通用戶 也很容易通過先選定類 再查找對應的文檔 將大大提高查找信息的命中率 這也即聚類搜索引擎 c l u s t e r i n g s e a r c h e n g i n e 所要達到的目的 聚類搜索引擎一般是元搜索引擎 m e t as e a r c he n g i n e 與w e b 聚類技術 的整合 通過元搜索引擎獲取來自不同搜索引擎的搜索結(jié)果 然后對搜索結(jié)果 一般是文檔的一個片段即s n i p p e t 而不是整篇文章 進行聚類 形成類標簽 c l a s sl a b e l 和類內(nèi)容 c l a s sc o n t e n t 每個類標簽中均包含對應的類內(nèi)容 s c a t t e g a t h e r h e a r s ta n dp e d e r s e n 9 6 較早對搜索結(jié)果進行聚類的系統(tǒng) 它 是基于b u c k s h o t 和f r a c t i o n a t i o n 兩種聚類算法基礎上 通過對標題 t i t l e 的 評價 把相似的文檔聚合在一起 以區(qū)別不相關的文檔 a g g l o m e r a t i v eh i e r a r c h i c a lc l u s t e r i n g h c 是基于k m e a n s s i n g l e p a s s 等 基于距離的聚類算法 但精度很低 類標簽很難表示 g r o u p e r g r o u p e r 9 9 1 通過h u s k y s e a r c h 元搜索引擎獲取搜索結(jié)果并利用基 于短語 p h r a s e 的后綴樹聚類 s u f f i x t r e ec l u s t e r i n g 算法對其動態(tài)聚類成帶 有類標簽的簇集 它的特點是基于共享短語 s h a r e dp h r a s e s 而不是孤立的詞 w o r d 允許類重疊 是一種模糊聚類方法 可以增量聚類 時間為線性 c a r r o t 2 c a r r o t 2 0 3 并as e m a n t i ch i e r a r c h i c a lo n f i n ec l u s t e r i n g s h o e 0 4 兩 者都用到了后綴數(shù)組 s u f f i x a r r a y 來發(fā)現(xiàn)關鍵短語 k e y p h r a s e s 不同的是 前者使用s v d 算法來得到類標簽 再利用向量空間模型 v e c t o r s p a c em o d e l 形成簇集 而后者利用s v d 來得到類標簽和形成簇集 v i v i s i m o v i v ls i m o 0 5 p e f e ze ta 1 o o 基于的原理是 種n q 做準確描述所 有配對 c o n c i s ea l lp a i r sp r o f i l i n g 簡稱為c a p p 的方法 這種方法著眼于形 成可描述的聚類 它的基本原理是將所有的類別成對的進行比較 找出能夠?qū)?每一對類別區(qū)分開來的特征 然后對那些特征進行組織 形成最后的描述 保 證每一對至少有一個特征能夠?qū)⑺推渌麑^(qū)別出來 v l s i m o 自動聚類所依 據(jù)的是搜索引擎返回的網(wǎng)址 標題和簡單描述 而不是整個網(wǎng)頁 在導師的精心指導下 我們智能搜索引擎研究小組取得了較好的成績 從 搜索引擎的構架研究到個人w e b 搜索服務 再到聚類搜索引擎 我們積累了豐 富的經(jīng)驗 并完成了智能搜索引擎和個性化平臺的開發(fā) 在原有的個人w e b 搜 索服務研究的基礎上 我們把聚類技術應用到對搜索結(jié)果的處理上 是對搜索 3 墮蘭奎堂堡主堂垡絲苧 結(jié)果表現(xiàn)方式的一次變革 提出了一個基于短語和潛在語義檢索的w e b 搜索結(jié) 果聚類算法m y c l u s t e r 并在此基礎上構造了聚類搜索引擎和評價體系 1 2 研究的目的和范圍 本文研究的主要目的是 提出一個高效 可靠的搜索結(jié)果聚類算法 研究 工作主要包括 1 信息檢索 i n f o r m a t i o nr e t r i e v a l 的研究 及線性代數(shù)在w e b 挖掘中的 應用 2 設計搜索結(jié)果聚類算法 3 設計執(zhí)行其算法的應用框架 4 設計算法評價體系 本文涉及的問題屬于w e b 挖掘領域 是信息檢索的子領域 w e b 挖掘主要 分為 1 w e b 用法挖掘 w e b u s a g em i n i n g 用來自動發(fā)現(xiàn)用戶獲取w e b 服 務的模式 2 w e b 結(jié)構挖掘 w e bs t r u c t u r em i n i n g 用來分析w 曲的超鏈 結(jié)構 3 w e b 內(nèi)容挖掘 w e bc o n t e n tm i n i n g 研究如何從互聯(lián)網(wǎng)上獲取信 息的問題 本文屬于第3 種w e b 挖掘 1 3 論文結(jié)構 本文剩下的章節(jié)將組織如下 第二章 簡單介紹w e b 搜索 口搜索引擎 及各種類型的搜索引擎 其中 將涉及系統(tǒng)架構和搜索結(jié)果表現(xiàn) 第三章 簡單介紹w e b 聚類技術 包括中文分詞技術和針對搜索結(jié)果的多 種聚類算法 第四章 詳細介紹本文將提出的搜索結(jié)果聚類算法m y c l u s t e r 所必備的概念 和理論 包括關鍵短語和非關鍵短語的識別 奇異值分解方法等 第五章 提出我們的搜索結(jié)果聚類算法m y c l u s t e r 利用關鍵短語和非關鍵 短語來構造特征矩陣 奇異值分解方法來發(fā)現(xiàn)類內(nèi)容和歸納類標簽 類合并和 類排序完成聚類的最后過程 并給出執(zhí)行m y c l u s t e r 算法的系統(tǒng)框架 第六章 提出我們的搜索結(jié)果聚類算法評價體系 并進行對比實驗和分析 第七章 總結(jié) 4 西華大學碩士學位論文 第2 章w e b 搜索 本章將重點介紹傳統(tǒng)搜索引擎和其他各類搜索引擎 并分析它的結(jié)構包括 爬行蟲 文檔索引 文檔排序 文檔緩存 查詢處理和結(jié)果顯示界面等 同時 著重介紹了各種搜索結(jié)果表現(xiàn)方法 并進行對比分析 最后就如何獲取搜索結(jié) 果進行簡要地闡述 2 1w e b 搜索服務 w e b 搜索服務即w e b 搜索引擎 目的是幫助用戶更好地查找互聯(lián)網(wǎng)上的信 息和資源 現(xiàn)在的w e b 搜索引擎能搜索的文本類型非常廣泛 包括h t m l 網(wǎng) 頁 p d f p s m sw o r d 和m sp o w e r p o i n t 文檔等 甚至還能搜索多媒體文 件 用戶使用w e b 搜索 只需登錄搜索引擎站點 例如 g o o s e h t t p w w w g o o g l e t o m 在搜索框中輸入要查詢的字符串 即查詢詞 很快 就會返回搜索引擎提供的帶有超鏈 h y p e r l i n k 的文檔結(jié)果列表 搜索引擎往 往把跟查詢詞最相關的結(jié)果排在最前面 它們很可能就包含用戶想要的信息 帶有超鏈的文檔結(jié)果并不是源文 而是源文中的 d 片段 這主要是基于檢索 速度方面的考慮 現(xiàn)代的搜索引擎不再局限于普通文檔的搜索 范圍擴大到對 很多資源包括f r p 資源 網(wǎng)上購物商場 地圖 多媒體資源等 其代表有天網(wǎng) 螞蟻f r p 文件搜索 k e e p s oh e0 5 g o o g l eo r o u p s o o o g l eg r o u p s 0 5 f r o o g l e f r o o g l e 0 5 等 現(xiàn)代搜索引擎可以分為傳統(tǒng)搜索引擎 元搜索引擎 智 能搜索引擎 包括個性化搜索引擎 聚類搜索引擎等 等三大類 2 1 1 傳統(tǒng)搜索引擎 真正意義上的搜索引擎 通常指的是利用爬行蟲收集互聯(lián)網(wǎng)上幾千萬到幾 十億個網(wǎng)頁并對網(wǎng)頁中的文字 即關鍵詞 進行索引 建立索引數(shù)據(jù)庫的全文 搜索引擎 當用戶查找某個關鍵詞的時候 所有在頁面內(nèi)容中包含了該關鍵詞 的網(wǎng)頁都將作為搜索結(jié)果 在經(jīng)過復雜的算法排序后 這些結(jié)果將按照與搜索 關鍵詞的相關度高低 依次排列 現(xiàn)在的搜索引擎已普遍使用超鏈分析技術 除了分析索引網(wǎng)頁本身的文字 還分析索引所有指向該網(wǎng)頁的鏈接的u r l 望蘭盔堂堡主蘭壘笙苧 a n c h o r t e x t 甚至鏈接周圍的文字 傳統(tǒng)搜索引擎基本上都具備一些共同的組 件包括 爬行蟲 c r a w l e r s p i d e r r o b o t 文檔索引 文檔排序 文檔緩存 查詢處理 結(jié)果顯示界面等 傳統(tǒng)搜索引擎的一般構架如圖2 1 所示 一 器 一 1 苧 凈型 囂1 q 掣 二童 蓋 罐 一 象二 曼p 些型 1 勘 u1 目 e i g g 日醛 墾 h 樣l 錐 掣麓 圖2 1 傳統(tǒng)搜索引擎構架 2 1 1 1 爬行蟲 w e bc r a w l e r 爬行蟲是能夠從互聯(lián)網(wǎng)上自動下載網(wǎng)頁的計算機程序 一般采用并行下載 方式 它與普通下載方式不同的是它能提取爬行過的網(wǎng)頁中的u r l 并把它作 為下一個自動爬行的目標網(wǎng)頁 這樣重復爬行 直到人為地終止程序或設置出 口 爬行蟲程序很復雜 涉及到網(wǎng)頁排重 死鏈處理 動態(tài)網(wǎng)頁下載 網(wǎng)頁跳 轉(zhuǎn)等難題 還必須遵守r o b o te x c l u s i o np r o t o c o l 2 0 0 5 年4 月2 日顯示o o o g l e 抓取互聯(lián)網(wǎng)上的文檔總數(shù)為8 0 5 8 0 4 4 6 5 1 張 即便有這么多的文檔也只占互聯(lián)網(wǎng)的 d 部分 g o o g l e 爬行蟲的爬行周期從原 來的一個月縮短為現(xiàn)在的一周 使用戶得到的搜索結(jié)果有很高的新鮮度 提高 了信息的查全率和查準率 一般爬行蟲程序的偽代碼如下 c r a w l e r u r l s e t u r l s e t d o c s e td o c s e t w h i l e u r l s e t 非空 6 西華大學碩士學位論文 法 從u r l s e t 中取一u r l 下載此u r l 對應的文檔d o c 從下載的文檔d o c 中解析出u r l s 保存到n e w u r l s e t 中 將下載的d o c 添加到d o c s e t 中 把u r l 保存到i n d e x e d u r l s e t 中 f o r n e w u r l s e t 中的每個u r l u r l 通過一算法映射為一固定長度的字符串 i f i n d e x e d u r l s e t 中不存在此字符串 將u r l 加入到u r l s e t 中 爬行蟲程序一般采用寬度優(yōu)先和深度優(yōu)先算法 也有其他一些智能爬行算 2 1 1 2 文檔索引 d o c u m e n ti n d e x 文檔索引就是對爬行蟲下載的網(wǎng)頁 或文檔 建立索引結(jié)構 以提高檢索 速度 由于下載的網(wǎng)頁數(shù)量很大 及網(wǎng)頁本身包含的內(nèi)容很豐富 要對嘲頁中 的每個詞建立索弓l 數(shù)據(jù)量很大 也是不可能的 所以其中將涉及停用詞處理 英文詞根處理 中文切詞分詞 建立倒排表 y a t e s e ta 1 9 9 和數(shù)據(jù)壓縮 y a t e se t a l 9 9 等 數(shù)掘一般達到幾百g 通常以文件的形式存放在多臺服務器上 而 不是數(shù)據(jù)庫 2 1 1 3 文檔評價 d o c u m e n tr a n k i n g 文檔評價是對所有下載的網(wǎng)頁進行重要性評價 其中涉及的關鍵因素較多 有詞頻 鏈接數(shù) 是否首頁等 比較流行的評價算法有p a g e r a n k p a g e b r i n e ta 1 9 8 和h i t s c h a k r a b a r t i 9 8 其中p a g e r a n k 算法已經(jīng)獲得了很大的成功 7 墮蘭奎堂堡主蘭竺堡壅 1 p a g e r a n k 算法 假設 網(wǎng)頁a 存在網(wǎng)頁乃 霸指向它 即網(wǎng)頁a 的外鏈c i t a t i o n s 參數(shù) d 為一衰減因子介于0 到1 之間 c 似 就指網(wǎng)頁a 的外鏈數(shù) 網(wǎng)頁一的p a g e r a n k 值計算如下 p r 彳 t 1 一d d p 尺 互 c 寫 p r t c a p a g e r a n k 值是用戶瀏覽此網(wǎng)頁的一個概率分布 它們總和等于1 2 h i t s 算法 h i t s h y p e r l i n k i n d u c e dt o p i cs e a r c h 算法是利用h u b a u t h o r i t y 方法的 評價算法 其算法描述如下 將查詢孽提交給傳統(tǒng)的基于關鍵字匹配的搜索引 擎 從搜索引擎返回的網(wǎng)頁中取前h 個網(wǎng)頁作為根集 r o o ts e t 用s 表示 s 滿 足如下3 個條件 1 s 中網(wǎng)頁數(shù)量相對較小 2 s 中網(wǎng)頁大多數(shù)是與查詢q 相關的網(wǎng)頁 3 s 中網(wǎng)頁包含較多的權威網(wǎng)頁 通過向s 中加入被s 引用的網(wǎng)頁和引用5 的網(wǎng)頁將s 擴展成一個更大的集合 z 以z 中的h u b 網(wǎng)頁為頂點集乃 以權威網(wǎng)頁為頂點集比 m 中的網(wǎng)頁到圪 中的網(wǎng)頁的超鏈接為邊集e 形成一個二分有向圖陽 巧 場 司 對礙中 的任一個頂點v 用 v 表示網(wǎng)頁v 的h u b 值 對比中的頂點u 用口0 表示 網(wǎng)頁的a u t h o r i t y 值 開始時 o 口以 1 對u 執(zhí)行 操作修改它的口 對 v 執(zhí)行0 操作修改它的 然后規(guī)范化口0 矗 如此不斷的重復計算下面 的操作i 0 直到口以 收斂 i 操作 口0 一羅 v v 韶 0 操作 0 羅口 v 2 每次迭代后需要對 a 進行規(guī)范化處理 劬 呻y 撬陋臼 蜘 7 屬阽 rv 口t v 扣坼 式 1 反映了若一個網(wǎng)頁由很多好的m 6 指向 則其權威值會相應增加 即權 8 墮蘭查蘭堡主蘭垡笙奎 威值增加為所有指向它的網(wǎng)頁的現(xiàn)有h u b 值之和 式 2 反映了若一個網(wǎng)頁指 向許多好的權威頁 則h u b 值也會相應增加 即h u b 值增加為該網(wǎng)頁鏈接的所 有網(wǎng)頁的權威值之和 2 1 1 4 文檔緩存 d o c u m e n tc a c h e 文檔緩存是指源文的存儲 供檢索時實時提取網(wǎng)頁片段和做網(wǎng)頁快照使用 2 1 1 5 查詢處理 q u e r yp r o c e s s o r 查誨處理就是執(zhí)行用戶的查詢需求 與文檔索引 文檔緩存和文檔排序進 行通信 把最終的結(jié)果返回給用戶 2 1 1 6 結(jié)果顯示界面 p r e s e n t a t i o ni n t e r f a c e 結(jié)果顯示界面一般用來顯示搜索結(jié)果總數(shù) 搜索時間和搜索結(jié)果等 傳統(tǒng) 搜索引擎大都采用列表形式來顯示結(jié)果 用戶通過翻頁來完成查找 這也是與 聚類搜索引擎在搜索結(jié)果顯示方式上的最大區(qū)別 2 1 2 元搜索引擎 m e t as e a r c he n g i n e 元搜索號l 輩是一神調(diào)用其它獨立搜索引擎的引擎疥稱 搜索引擎之母 t h e m o t h e ro fs e a r c ee n g i n e s 在這里 元 m e t a 為 總的 超越 之意 元搜索引擎就是對多個獨立搜索引擎的整合 調(diào)用 控制和優(yōu)化利用 相對元 搜索引擎 可被利用的獨立搜索引擎稱為 源搜索引擎 s o u r c ee n g i n e 或 搜索資源 s e a r c i n gr e s o u r c e s 整合 調(diào)用 控制和優(yōu)化利用源搜索引擎的 技術 稱為 元搜索技術 m e t a s e a r c h i n gt e c h n i q u e 元搜索技術是元搜索引 擎的核心 元搜索引擎分為并行處理式和串行處理式兩大類 并行處理式元搜索引擎 將用戶的查詢請求同時轉(zhuǎn)送給它調(diào)用鏈接的多個獨立型搜索引擎進行查詢處 理 串行處理式元搜索引擎將用戶的查詢請求依次轉(zhuǎn)送給它調(diào)用鏈接的每一個 獨立型搜索引擎進行查詢處理 西華大學碩士學位論文 元搜索引擎是用戶同時利用多引擎進行網(wǎng)絡搜索的中介 檢索時 元搜索 引擎根據(jù)用戶提交的檢索請求 調(diào)用源搜索引擎進行搜索 對搜索結(jié)果進行匯 集 篩選 刪并等優(yōu)化處理后 以統(tǒng)一的格式在同一界面集中顯示 元搜索引 擎雖沒有網(wǎng)頁搜尋機制 亦無獨立的索引數(shù)據(jù)庫 但在檢索請求提交 檢索接 口代理和搜索結(jié)果顯示等方面 均有自己研發(fā)的特色元搜索技術支持 對搜索 結(jié)果的顯示 不同的元搜索引擎有不同的處理技術 由于元搜索引擎設定的搜 索結(jié)果排序依據(jù) 最大返回結(jié)果數(shù)量 相關度參數(shù)及優(yōu)化機制等不同 調(diào)用相 同的源搜索引擎的不同元搜索引擎顯示搜索結(jié)果的數(shù)量多少 排序先后 結(jié)果 信息描述選擇亦有較大差異 1 9 9 5 年華盛頓大學碩士生e r i c s e l b e r g 和o r e n e t z i o n i 推出第一個元搜索 引擎 m e t a c r a w l e r 以來 這一新型的網(wǎng)絡檢索工具異軍突起 發(fā)展迅速 目前 可用的元搜索引擎已近百種 盡管元搜索引擎存在著功能上的局限 但其以含 蓋較多的搜索資源 能夠在盡可能短的時間內(nèi)提供相對全面 準確的搜索結(jié)果 等諸多優(yōu)異功能受到用戶的青睞 已漸成為一種不可或缺的極具潛力的網(wǎng)絡檢 索工具 現(xiàn)在較流行的元搜索引擎有d o g p i l ef d o g p i l e 0 5 m e t a c r a w l e r m e t a c r a w l e r 0 5 見雷2 2 邪m a m m a m a m m a 0 5 m e t a c r a w t e r 等p h 等鼉?nèi)瓕W鬻j j 譬謄熬鬻i 廣e x a br a s j 童 擘旦要等望唉籬謦 j 靜i 二毫 圈2 2 m e t a c r a w l e r 元搜索引擎 2 1 3個性化搜索引擎 p e r s o n a l i z e ds e a r c he n g i n e 個性化搜索引擎是接受用戶輸入的查詢詞 來查找用戶的感興趣信息 此 系統(tǒng)在與用戶的頻繁交互中記下用戶的個人興趣愛好 并建立用戶興趣模型 當用戶使用時 向用戶提供某一方面的或全部的感興趣信息 比如 一喜歡 獵 豹 這種動物的用戶搜索 獵豹 時 將得到有關 獵豹 這一生物的信息 而不是獵豹汽車或其它 1 0 西華大學碩士學位論文 個性化搜索引擎系統(tǒng)必須滿足以下三個要求 1 1 個性化的 個性化搜索引擎系統(tǒng)必須是為特定的用戶服務的 2 高適應性的 由于用戶的興趣是在改變的 所以 系統(tǒng)必須能察覺用戶的興趣改變了 系統(tǒng)必須根據(jù)這些改變采取相應的措施 3 1 易擴展的 個性化搜索引擎系統(tǒng)應該能探測新的領域 以此來發(fā)現(xiàn)用戶潛在的興趣 總之 個性化搜索引擎系統(tǒng)應該能及時地提供與用戶的需求相匹配的信息 并在用戶興趣改變時作出相應的變化 所以 系統(tǒng)不但要了解用戶當時的需求 還應能探索不同的領域來發(fā)現(xiàn)用戶新的興趣愛好 其代表有g o o g l e p e r s o n a l i z e d g o o g l ep e r s o n a l i z e d 0 5 z h o n g s o ui p s z h o n g s o ui p s 0 5 見圖 2 3 霸7 孽 玉秘 z h o n g s o u c o m 個 臻藿 二二二 三三 二二二黜 蔓夏 一 攮墊囂艘送纛差型 圖2 3 中搜個性化搜索引擎 2 1 4 聚類搜索引擎 c l u s t e r i n g s e a r c he n g i n e 聚類搜索引擎是元搜索引擎與w e b 聚類技術的整合 它通過元搜索引擎獲 取來自不同傳統(tǒng)搜索引擎的搜索結(jié)果 然后對搜索結(jié)果 一般是文檔的一些片 段 而不是整篇文章 進行聚類 形成簇集 每個簇中均包含對應的文檔集 西華大學碩士學位論文 聚類搜索引擎與傳統(tǒng)搜索引擎的最大區(qū)別就在于 搜索結(jié)果表現(xiàn)形式的不同 傳統(tǒng)搜索引擎的搜索結(jié)果是一按相關性排序的結(jié)果列表 而聚類搜索引擎則是 將搜索結(jié)果進行再聚類 形成類標簽和對應的類內(nèi)容的過程 使用聚類搜索引 擎時 用戶首先也是輸入查詢詞 然后選擇感興趣的類標簽 得到相應的類內(nèi) 容 即搜索結(jié)果 實質(zhì)上它起到 信息導航 的作用 也是對搜索結(jié)果表現(xiàn)方 式的一次變革 將大大提高用戶瀏覽信息的命中率和效率 其代表有v i v i s i m o v i v ts i m o 0 5 1 見圖2 4 c a r r o t 2 c a r r o t 2 0 5 m o o t e r m o o t e r 0 5 等 塑旦 一 罌銎毒 i 鬟 墓簍塞黧萎黧簍暴霪簍 g 溪藤 一 巾 q 棗 尊 h t 呻鼎目镕 竹e r q 燃e t x 廠 暉蓐曩i i 囂習匹 遂鯊j 圖2 4 v i v ls i m o 聚類搜索引擎 2 2 搜索結(jié)果表現(xiàn) 搜索結(jié)果是反映一個搜索引擎質(zhì)量好壞的重要指標 也是用戶獲取自己感 興趣信息的入口 返回與查詢詞最相關的搜索結(jié)果一直是所有搜索引擎提供商 追求的目標 在搜索結(jié)果一定的情況下 如何更好地組織和表現(xiàn)搜索結(jié)果 將 直接影響用戶查找信息的效率 搜索結(jié)果表現(xiàn)形式目前主要有 1 評價列表 2 人工目錄 3 聚類 2 2 1 評價列表 r a n k e dl i s t 評價列表 見圖2 5 是目前搜索引擎采用的比較常見的方式 它按文檔與 查詢詞的相關程度來排序 把最相關的搜索結(jié)果顯示在前面 評價列表中的每 個結(jié)果通常由標題 t i t l e u r l 和來自文檔的片段等構成 用戶通過瀏覽評價 列表來確定信息所在的位置 然后點擊位置上的u r l 打開對應的文檔 即完成 用戶的一次查找過程 但它也存在著很多不足之處 g r o u p e r 9 9 w e i s s 0 1 1 用戶為了找到所需的文檔 往往得瀏覽很長的結(jié)果評價列表 甚至通過 翻頁才能找到 1 2 用戶無法知道查詢詞與文檔的相關程度 也無法知道文檔問的相關性 3 結(jié)果沒有經(jīng)過分類 用戶很難快速找到需要的文檔 玨華大學碩士學位論文 c o 昭i e 所有同站星曩妻 匾旦上監(jiān)捱 圜夏目量 研掰 一型盤邋 療搜索所有網(wǎng)站r 搜索所有中文網(wǎng)頁r 搜索簡體中文網(wǎng)頁 1 日 3 0 日 電稿報集團 藪i 麗l 假冒墨盒 硒鼓 電腦城外并奔馳的郡是敲假冒打印耗襯生意的一 曾經(jīng)有 段時間 本地的工t 螢子里有過這樣的 c o p i 曲t c z 0 0 4c p c t c 橢 電腦報版權所 有渝i c p 證b 2 2 0 0 3 0 0 0 3 號如有意見請與我們聯(lián)蓉信息部制作 c p