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

y 7 4 6 1 9 8 w e b 聚類技術(shù)及其在搜索引擎中的應(yīng)用 計(jì)算機(jī)軟件與理論 研究生李戰(zhàn)勝指導(dǎo)教師杜亞軍 摘要 搜索引擎是當(dāng)前研究的熱門技術(shù)之一 用戶通過輸入查詢?cè)~來獲取搜索結(jié) 果 從而能夠在海量的互聯(lián)網(wǎng)資源中獲取有用信息 然而 當(dāng)前搜索引擎返回 的搜索結(jié)果數(shù)目非常龐大 要從這么多的結(jié)果中找到有用信息 有時(shí)顯得很困 難 如何更好地顯示搜索結(jié)果 更好地幫助用戶找到自己感興趣的信息 是本 文所要研究和解決的問題 幸運(yùn)地是 利用聚類技術(shù)對(duì)搜索結(jié)果按主題聚類 將很好地表現(xiàn)搜索結(jié)果 顯然 傳統(tǒng)的聚類技術(shù)一般都是針對(duì)數(shù)值數(shù)據(jù)進(jìn)行的 而對(duì)于文本數(shù)據(jù) 尤其 是w e b 文檔類型的數(shù)據(jù) 需要新的能夠處理高維 實(shí)時(shí)的聚類算法 并在文本 特征提取和時(shí)間復(fù)雜廢方面有更高的要求 本文提出的新的聚類算法m y c l u s t e r 是基于短語(yǔ)和潛在語(yǔ)義索引基礎(chǔ)上的 針對(duì)搜索結(jié)果的模糊w e b 聚類算法 在m y c l u s t c r 聚類算法中采用由多個(gè)有序 詞構(gòu)成的短語(yǔ)來建立文檔特征向量 雨不是傳統(tǒng)方法上用單個(gè)詞來建立 這樣 可以有效地避免數(shù)據(jù)噪音的干擾 而且還可以明顯地降低特征矩陣的維度 縮 減計(jì)算時(shí)間 w e b 文檔特征矩陣的建立將涉及w e b 文檔的下載和解析 關(guān)鍵短 語(yǔ)和非關(guān)鍵短語(yǔ)的識(shí)別和中文分詞等關(guān)鍵技術(shù) w e b 聚類結(jié)果由類標(biāo)簽和類內(nèi)容構(gòu)成 每個(gè)類標(biāo)簽都對(duì)應(yīng)著許多類內(nèi)容 即搜索結(jié)果 每個(gè)類標(biāo)簽代表著一個(gè)主題 顯然類標(biāo)簽的可讀性 也即主題鮮 明 將直接影響用戶查找信息的命中率 當(dāng)然 類內(nèi)容是用戶獲取最終信息的 入口 它與類標(biāo)簽的相關(guān)性就很重要 我們采用線性代數(shù)中奇異值分解方法來 發(fā)現(xiàn)類內(nèi)容和歸納類標(biāo)簽 使類內(nèi)很相似 類間不相似 而且類內(nèi)容很好地關(guān) 聯(lián)了類標(biāo)簽 對(duì)形成的類標(biāo)簽和類內(nèi)容 采用合并和排序策略 將很好地修正 聚類結(jié)果 為了更好地測(cè)試m y c l u s t e r 算法的聚類效果 本文給出了基于m y c i u s t c r 算法的聚類搜索b l 擎框架及聚類結(jié)果評(píng)價(jià)體系 實(shí)現(xiàn)聚類搜索引擎的過程中將 涉及多種編程語(yǔ)言 例如h t m l j a v a s c r i p t c g i 和 等 和數(shù)學(xué)軟件m a t l a b 并實(shí)現(xiàn)了 在脫離m a t l a b 環(huán)境情況下對(duì)m a t l a b 生成的動(dòng)態(tài)鏈接庫(kù)的直接調(diào) 用 我們的聚類結(jié)果評(píng)價(jià)體系通過類標(biāo)簽的可讀性 類內(nèi)容的相關(guān)性 類內(nèi)容 覆蓋率和類重疊度等指標(biāo) 來綜合評(píng)價(jià)一個(gè)算法質(zhì)量的好壞 通過對(duì)比實(shí)驗(yàn) 我們發(fā)現(xiàn)m y c l u s t e r 在類標(biāo)簽可讀性和類內(nèi)容相關(guān)性方面 有很大地優(yōu)勢(shì) 但在類內(nèi)容覆蓋率方面有所欠缺 希望未來將能有所改進(jìn) 并 在增量聚類等方面作進(jìn)一步的研究 關(guān)鍵詞 聚類搜索引擎 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 西華大學(xué)碩士學(xué)位論文 第1 章緒論 就像g o o g l e 的創(chuàng)始人所說的 我們?nèi)裟芨咨频厮褜べY料 實(shí)在已經(jīng)改 變世界 在互聯(lián)網(wǎng)高速發(fā)展的今天 人們發(fā)現(xiàn)查找信息變得越來越困難了 如何才能更有效地查找我們感興趣的信息 這一問題已經(jīng)成為眾多學(xué)者的 研究對(duì)象 在 s e l b e r g 9 9 1 中提到 這個(gè)問題即是從w e b 中找出與用戶給定查詢 詞相關(guān)的文檔集 為解決這個(gè)難題 涌現(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é)果卻并不盡如人意 使用者輸入查詢?cè)~ 一般都會(huì)得到成千上萬(wàn)的 搜索結(jié)果 然而其中大部分頁(yè)面都是不需要的無(wú)關(guān)資料 雖然有一些技巧試圖 給那些有較多關(guān)鍵詞或者罕見關(guān)鍵詞的頁(yè)面賦予更大的權(quán)重 卻仍然不能保證 與用戶意圖最相關(guān)的頁(yè)面一定被排在最前面 因此用戶別無(wú)選擇 只能把檢索 到的頁(yè)面一個(gè)個(gè)再篩選一遍 顯然 這浪費(fèi)人的時(shí)間和精力 c u t t i n ge ta 1 9 2 等提出的稱為 s c a t t e r g a t h e r 的技術(shù) 試圖更合理的組 織搜索結(jié)果 這種技術(shù)對(duì)檢索到的結(jié)果頁(yè)面進(jìn)行聚類操作 按照頁(yè)面彼此之間 的相似程度分為若干組 每組都有一個(gè)比較明確的主題 用戶可以迅速地掃描 每一組并選擇那些和他的目標(biāo)最相關(guān)的組 這是一個(gè)很好的嘗試和開端 它將 很好地解決人們查找信息難的問題 此后 陸續(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 研究動(dòng)態(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 學(xué)生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 雖然當(dāng)時(shí)w o r l dw i d ew e b 還未出現(xiàn) 但網(wǎng)絡(luò)中文件傳輸還是相當(dāng)頻繁的 由于大量的文件散布在各個(gè)分 散的f t p 主機(jī)中 查詢起來非常不便 因此 a 1 a ne m t a g e 等想到了開發(fā)一個(gè) 可以用文件名查找文件的系統(tǒng) 于是便有了a r c h i e a r c h i e 是第一個(gè)自動(dòng)索引 互聯(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 楊 致遠(yuǎn) 和d a v i df i l o 共同創(chuàng)辦了y a h o o 隨著訪問量和收錄鏈接數(shù)的增長(zhǎng) y a h o o 目錄開始支持簡(jiǎn)單的數(shù)據(jù)庫(kù)搜索 因?yàn)閥 a h o o 的數(shù)據(jù)是手工輸入的 所以不能 耍望盔堂堡主蘭垡笙壅 真正被歸為搜索引擎 事實(shí)上只是一個(gè)可搜索的目錄 y a h o o 中收錄的網(wǎng)站都 附有簡(jiǎn)介信息 所以搜索效率明顯提高 1 9 9 4 年初 w a s h i n g t o n 大學(xué)c s 學(xué)生b r i a np i n k e r t o n 開始了他的小項(xiàng)目 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 正式亮相時(shí)僅包 含來自6 0 0 0 個(gè)服務(wù)器的內(nèi)容 w e b c r a w l e r 是互聯(lián)網(wǎng)上第一個(gè)支持搜索文件全 部文字的全文搜索引擎 在它之前 用戶只能通過u r l 和摘要搜索 摘要一般 來自人工評(píng)論或程序自動(dòng)取正文的前1 0 0 個(gè)字 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 是一個(gè)遲到者 1 9 9 5 年1 2 月才登場(chǎng)亮相 但是 大量的創(chuàng)新功能使它迅速到達(dá)當(dāng)時(shí)搜索引擎的頂峰 a l t a v i s t a 最突出的 優(yōu)勢(shì)是它的速度 a l t a v i s t a 是第一個(gè)支持自然語(yǔ)言搜索的搜索引擎 也是第一 個(gè)實(shí)現(xiàn)高級(jí)搜索語(yǔ)法的搜索引擎 如a n d o r n o t 等語(yǔ)法 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 動(dòng)態(tài)摘要 網(wǎng)頁(yè)快照 d a i l y r e f r e s h 多文檔格 式支持 地圖股票詞典尋人等集成搜索 多語(yǔ)言支持 用戶界面等功能上的革 新 象a l t a v i s t a 一樣 再一次永遠(yuǎn)改變了搜索引擎的定義 給定一查詢?cè)~來查找與之相關(guān)的文檔集 需要考慮三方面的因素 1 w e b 是一動(dòng)態(tài)的文檔集合 它每時(shí)每刻都在更新 2 互聯(lián)網(wǎng)上存在海量的文檔 而搜索引擎僅返回與查詢?cè)~相關(guān)的很少結(jié)果 3 如何將最相關(guān)的結(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 等技術(shù)獲取互聯(lián)網(wǎng)上的文檔 經(jīng)過 索引 以所謂的查詢?cè)~一結(jié)果列表方法把最相關(guān)的結(jié)果排在最前面 由于搜索引擎僅憑用戶的查詢?cè)~來返回搜索結(jié)果 很低的查全率和查準(zhǔn)率 會(huì)導(dǎo)致用戶需要翻很多搜索結(jié)果頁(yè)才能找到自己感興趣的信息 甚至根本找不 到 y a h o o 采用目錄的方式把互聯(lián)網(wǎng)上的文檔按類別進(jìn)行分類 用戶可以按照 類別導(dǎo)航來查找資料 但是w e b 文檔更新很快 用人工方式編輯形成的分類目 錄顯然不適臺(tái)當(dāng)前信息極度膨脹的互聯(lián)網(wǎng) 而利用人工智能方法 聚類將會(huì)很 好地解決這些問題 聚類 c l u s t e r i n g 是一個(gè)將數(shù)據(jù)集劃分為若干類 c l a s s 或簇 c l u s t e r 的 過程 并使得同一個(gè)組內(nèi)的數(shù)據(jù)對(duì)象具有較高的相似度 而不同組中的數(shù)據(jù)對(duì) 象是不相似的 如果把它應(yīng)用到搜索結(jié)果上 將很好地把搜索結(jié)果分到相應(yīng)地 2 西華大學(xué)碩士學(xué)位論文 類中 比如 查詢 計(jì)算機(jī) 將得到 計(jì)算機(jī)病毒 計(jì)算機(jī)考試 計(jì)算機(jī) 科研網(wǎng) 等類 對(duì)于普通用戶 也很容易通過先選定類 再查找對(duì)應(yīng)的文檔 將大大提高查找信息的命中率 這也即聚類搜索引擎 c l u s t e r i n g s e a r c h e n g i n e 所要達(dá)到的目的 聚類搜索引擎一般是元搜索引擎 m e t as e a r c he n g i n e 與w e b 聚類技術(shù) 的整合 通過元搜索引擎獲取來自不同搜索引擎的搜索結(jié)果 然后對(duì)搜索結(jié)果 一般是文檔的一個(gè)片段即s n i p p e t 而不是整篇文章 進(jìn)行聚類 形成類標(biāo)簽 c l a s sl a b e l 和類內(nèi)容 c l a s sc o n t e n t 每個(gè)類標(biāo)簽中均包含對(duì)應(yīng)的類內(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 較早對(duì)搜索結(jié)果進(jìn)行聚類的系統(tǒng) 它 是基于b u c k s h o t 和f r a c t i o n a t i o n 兩種聚類算法基礎(chǔ)上 通過對(duì)標(biāo)題 t i t l e 的 評(píng)價(jià) 把相似的文檔聚合在一起 以區(qū)別不相關(guān)的文檔 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 等 基于距離的聚類算法 但精度很低 類標(biāo)簽很難表示 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é)果并利用基 于短語(yǔ) 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 算法對(duì)其動(dòng)態(tài)聚類成帶 有類標(biāo)簽的簇集 它的特點(diǎn)是基于共享短語(yǔ) s h a r e dp h r a s e s 而不是孤立的詞 w o r d 允許類重疊 是一種模糊聚類方法 可以增量聚類 時(shí)間為線性 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)關(guān)鍵短語(yǔ) k e y p h r a s e s 不同的是 前者使用s v d 算法來得到類標(biāo)簽 再利用向量空間模型 v e c t o r s p a c em o d e l 形成簇集 而后者利用s v d 來得到類標(biāo)簽和形成簇集 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 做準(zhǔn)確描述所 有配對(duì) c o n c i s ea l lp a i r sp r o f i l i n g 簡(jiǎn)稱為c a p p 的方法 這種方法著眼于形 成可描述的聚類 它的基本原理是將所有的類別成對(duì)的進(jìn)行比較 找出能夠?qū)?每一對(duì)類別區(qū)分開來的特征 然后對(duì)那些特征進(jìn)行組織 形成最后的描述 保 證每一對(duì)至少有一個(gè)特征能夠?qū)⑺推渌麑?duì)區(qū)別出來 v l s i m o 自動(dòng)聚類所依 據(jù)的是搜索引擎返回的網(wǎng)址 標(biāo)題和簡(jiǎn)單描述 而不是整個(gè)網(wǎng)頁(yè) 在導(dǎo)師的精心指導(dǎo)下 我們智能搜索引擎研究小組取得了較好的成績(jī) 從 搜索引擎的構(gòu)架研究到個(gè)人w e b 搜索服務(wù) 再到聚類搜索引擎 我們積累了豐 富的經(jīng)驗(yàn) 并完成了智能搜索引擎和個(gè)性化平臺(tái)的開發(fā) 在原有的個(gè)人w e b 搜 索服務(wù)研究的基礎(chǔ)上 我們把聚類技術(shù)應(yīng)用到對(duì)搜索結(jié)果的處理上 是對(duì)搜索 3 墮蘭奎堂堡主堂垡絲苧 結(jié)果表現(xiàn)方式的一次變革 提出了一個(gè)基于短語(yǔ)和潛在語(yǔ)義檢索的w e b 搜索結(jié) 果聚類算法m y c l u s t e r 并在此基礎(chǔ)上構(gòu)造了聚類搜索引擎和評(píng)價(jià)體系 1 2 研究的目的和范圍 本文研究的主要目的是 提出一個(gè)高效 可靠的搜索結(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 挖掘中的 應(yīng)用 2 設(shè)計(jì)搜索結(jié)果聚類算法 3 設(shè)計(jì)執(zhí)行其算法的應(yīng)用框架 4 設(shè)計(jì)算法評(píng)價(jià)體系 本文涉及的問題屬于w e b 挖掘領(lǐng)域 是信息檢索的子領(lǐng)域 w e b 挖掘主要 分為 1 w e b 用法挖掘 w e b u s a g em i n i n g 用來自動(dòng)發(fā)現(xiàn)用戶獲取w e b 服 務(wù)的模式 2 w e b 結(jié)構(gòu)挖掘 w e bs t r u c t u r em i n i n g 用來分析w 曲的超鏈 結(jié)構(gòu) 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é)構(gòu) 本文剩下的章節(jié)將組織如下 第二章 簡(jiǎn)單介紹w e b 搜索 口搜索引擎 及各種類型的搜索引擎 其中 將涉及系統(tǒng)架構(gòu)和搜索結(jié)果表現(xiàn) 第三章 簡(jiǎn)單介紹w e b 聚類技術(shù) 包括中文分詞技術(shù)和針對(duì)搜索結(jié)果的多 種聚類算法 第四章 詳細(xì)介紹本文將提出的搜索結(jié)果聚類算法m y c l u s t e r 所必備的概念 和理論 包括關(guān)鍵短語(yǔ)和非關(guān)鍵短語(yǔ)的識(shí)別 奇異值分解方法等 第五章 提出我們的搜索結(jié)果聚類算法m y c l u s t e r 利用關(guān)鍵短語(yǔ)和非關(guān)鍵 短語(yǔ)來構(gòu)造特征矩陣 奇異值分解方法來發(fā)現(xiàn)類內(nèi)容和歸納類標(biāo)簽 類合并和 類排序完成聚類的最后過程 并給出執(zhí)行m y c l u s t e r 算法的系統(tǒng)框架 第六章 提出我們的搜索結(jié)果聚類算法評(píng)價(jià)體系 并進(jìn)行對(duì)比實(shí)驗(yàn)和分析 第七章 總結(jié) 4 西華大學(xué)碩士學(xué)位論文 第2 章w e b 搜索 本章將重點(diǎn)介紹傳統(tǒng)搜索引擎和其他各類搜索引擎 并分析它的結(jié)構(gòu)包括 爬行蟲 文檔索引 文檔排序 文檔緩存 查詢處理和結(jié)果顯示界面等 同時(shí) 著重介紹了各種搜索結(jié)果表現(xiàn)方法 并進(jìn)行對(duì)比分析 最后就如何獲取搜索結(jié) 果進(jìn)行簡(jiǎn)要地闡述 2 1w e b 搜索服務(wù) w e b 搜索服務(wù)即w e b 搜索引擎 目的是幫助用戶更好地查找互聯(lián)網(wǎng)上的信 息和資源 現(xiàn)在的w e b 搜索引擎能搜索的文本類型非常廣泛 包括h t m l 網(wǎng) 頁(yè) p d f p s m sw o r d 和m sp o w e r p o i n t 文檔等 甚至還能搜索多媒體文 件 用戶使用w e b 搜索 只需登錄搜索引擎站點(diǎn) 例如 g o o s e h t t p w w w g o o g l e t o m 在搜索框中輸入要查詢的字符串 即查詢?cè)~ 很快 就會(huì)返回搜索引擎提供的帶有超鏈 h y p e r l i n k 的文檔結(jié)果列表 搜索引擎往 往把跟查詢?cè)~最相關(guān)的結(jié)果排在最前面 它們很可能就包含用戶想要的信息 帶有超鏈的文檔結(jié)果并不是源文 而是源文中的 d 片段 這主要是基于檢索 速度方面的考慮 現(xiàn)代的搜索引擎不再局限于普通文檔的搜索 范圍擴(kuò)大到對(duì) 很多資源包括f r p 資源 網(wǎng)上購(gòu)物商場(chǎ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)搜索引擎 元搜索引擎 智 能搜索引擎 包括個(gè)性化搜索引擎 聚類搜索引擎等 等三大類 2 1 1 傳統(tǒng)搜索引擎 真正意義上的搜索引擎 通常指的是利用爬行蟲收集互聯(lián)網(wǎng)上幾千萬(wàn)到幾 十億個(gè)網(wǎng)頁(yè)并對(duì)網(wǎng)頁(yè)中的文字 即關(guān)鍵詞 進(jìn)行索引 建立索引數(shù)據(jù)庫(kù)的全文 搜索引擎 當(dāng)用戶查找某個(gè)關(guān)鍵詞的時(shí)候 所有在頁(yè)面內(nèi)容中包含了該關(guān)鍵詞 的網(wǎng)頁(yè)都將作為搜索結(jié)果 在經(jīng)過復(fù)雜的算法排序后 這些結(jié)果將按照與搜索 關(guān)鍵詞的相關(guān)度高低 依次排列 現(xiàn)在的搜索引擎已普遍使用超鏈分析技術(shù) 除了分析索引網(wǎng)頁(yè)本身的文字 還分析索引所有指向該網(wǎng)頁(yè)的鏈接的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)搜索引擎的一般構(gòu)架如圖2 1 所示 一 器 一 1 苧 凈型 囂1 q 掣 二童 蓋 罐 一 象二 曼p 些型 1 勘 u1 目 e i g g 日醛 墾 h 樣l 錐 掣麓 圖2 1 傳統(tǒng)搜索引擎構(gòu)架 2 1 1 1 爬行蟲 w e bc r a w l e r 爬行蟲是能夠從互聯(lián)網(wǎng)上自動(dòng)下載網(wǎng)頁(yè)的計(jì)算機(jī)程序 一般采用并行下載 方式 它與普通下載方式不同的是它能提取爬行過的網(wǎng)頁(yè)中的u r l 并把它作 為下一個(gè)自動(dòng)爬行的目標(biāo)網(wǎng)頁(yè) 這樣重復(fù)爬行 直到人為地終止程序或設(shè)置出 口 爬行蟲程序很復(fù)雜 涉及到網(wǎng)頁(yè)排重 死鏈處理 動(dòng)態(tài)網(wǎng)頁(yè)下載 網(wǎng)頁(yè)跳 轉(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 爬行蟲的爬行周期從原 來的一個(gè)月縮短為現(xiàn)在的一周 使用戶得到的搜索結(jié)果有很高的新鮮度 提高 了信息的查全率和查準(zhǔn)率 一般爬行蟲程序的偽代碼如下 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 西華大學(xué)碩士學(xué)位論文 法 從u r l s e t 中取一u r l 下載此u r l 對(duì)應(yīng)的文檔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 中的每個(gè)u r l u r l 通過一算法映射為一固定長(zhǎng)度的字符串 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 文檔索引就是對(duì)爬行蟲下載的網(wǎng)頁(yè) 或文檔 建立索引結(jié)構(gòu) 以提高檢索 速度 由于下載的網(wǎng)頁(yè)數(shù)量很大 及網(wǎng)頁(yè)本身包含的內(nèi)容很豐富 要對(duì)嘲頁(yè)中 的每個(gè)詞建立索弓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ù)掘一般達(dá)到幾百g 通常以文件的形式存放在多臺(tái)服務(wù)器上 而 不是數(shù)據(jù)庫(kù) 2 1 1 3 文檔評(píng)價(jià) d o c u m e n tr a n k i n g 文檔評(píng)價(jià)是對(duì)所有下載的網(wǎng)頁(yè)進(jìn)行重要性評(píng)價(jià) 其中涉及的關(guān)鍵因素較多 有詞頻 鏈接數(shù) 是否首頁(yè)等 比較流行的評(píng)價(jià)算法有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 算法 假設(shè) 網(wǎng)頁(yè)a 存在網(wǎng)頁(yè)乃 霸指向它 即網(wǎng)頁(yè)a 的外鏈c i t a t i o n s 參數(shù) d 為一衰減因子介于0 到1 之間 c 似 就指網(wǎng)頁(yè)a 的外鏈數(shù) 網(wǎng)頁(yè)一的p a g e r a n k 值計(jì)算如下 p r 彳 t 1 一d d p 尺 互 c 寫 p r t c a p a g e r a n k 值是用戶瀏覽此網(wǎng)頁(yè)的一個(gè)概率分布 它們總和等于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 方法的 評(píng)價(jià)算法 其算法描述如下 將查詢孽提交給傳統(tǒng)的基于關(guān)鍵字匹配的搜索引 擎 從搜索引擎返回的網(wǎng)頁(yè)中取前h 個(gè)網(wǎng)頁(yè)作為根集 r o o ts e t 用s 表示 s 滿 足如下3 個(gè)條件 1 s 中網(wǎng)頁(yè)數(shù)量相對(duì)較小 2 s 中網(wǎng)頁(yè)大多數(shù)是與查詢q 相關(guān)的網(wǎng)頁(yè) 3 s 中網(wǎng)頁(yè)包含較多的權(quán)威網(wǎng)頁(yè) 通過向s 中加入被s 引用的網(wǎng)頁(yè)和引用5 的網(wǎng)頁(yè)將s 擴(kuò)展成一個(gè)更大的集合 z 以z 中的h u b 網(wǎng)頁(yè)為頂點(diǎn)集乃 以權(quán)威網(wǎng)頁(yè)為頂點(diǎn)集比 m 中的網(wǎng)頁(yè)到圪 中的網(wǎng)頁(yè)的超鏈接為邊集e 形成一個(gè)二分有向圖陽(yáng) 巧 場(chǎng) 司 對(duì)礙中 的任一個(gè)頂點(diǎn)v 用 v 表示網(wǎng)頁(yè)v 的h u b 值 對(duì)比中的頂點(diǎn)u 用口0 表示 網(wǎng)頁(yè)的a u t h o r i t y 值 開始時(shí) o 口以 1 對(duì)u 執(zhí)行 操作修改它的口 對(duì) v 執(zhí)行0 操作修改它的 然后規(guī)范化口0 矗 如此不斷的重復(fù)計(jì)算下面 的操作i 0 直到口以 收斂 i 操作 口0 一羅 v v 韶 0 操作 0 羅口 v 2 每次迭代后需要對(duì) a 進(jìn)行規(guī)范化處理 劬 呻y 撬陋臼 蜘 7 屬阽 rv 口t v 扣坼 式 1 反映了若一個(gè)網(wǎng)頁(yè)由很多好的m 6 指向 則其權(quán)威值會(huì)相應(yīng)增加 即權(quán) 8 墮蘭查蘭堡主蘭垡笙奎 威值增加為所有指向它的網(wǎng)頁(yè)的現(xiàn)有h u b 值之和 式 2 反映了若一個(gè)網(wǎng)頁(yè)指 向許多好的權(quán)威頁(yè) 則h u b 值也會(huì)相應(yīng)增加 即h u b 值增加為該網(wǎng)頁(yè)鏈接的所 有網(wǎng)頁(yè)的權(quán)威值之和 2 1 1 4 文檔緩存 d o c u m e n tc a c h e 文檔緩存是指源文的存儲(chǔ) 供檢索時(shí)實(shí)時(shí)提取網(wǎng)頁(yè)片段和做網(wǎng)頁(yè)快照使用 2 1 1 5 查詢處理 q u e r yp r o c e s s o r 查誨處理就是執(zhí)行用戶的查詢需求 與文檔索引 文檔緩存和文檔排序進(jìn) 行通信 把最終的結(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ù) 搜索時(shí)間和搜索結(jié)果等 傳統(tǒng) 搜索引擎大都采用列表形式來顯示結(jié)果 用戶通過翻頁(yè)來完成查找 這也是與 聚類搜索引擎在搜索結(jié)果顯示方式上的最大區(qū)別 2 1 2 元搜索引擎 m e t as e a r c he n g i n e 元搜索號(hào)l 輩是一神調(diào)用其它獨(dú)立搜索引擎的引擎疥稱 搜索引擎之母 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 為 總的 超越 之意 元搜索引擎就是對(duì)多個(gè)獨(dú)立搜索引擎的整合 調(diào)用 控制和優(yōu)化利用 相對(duì)元 搜索引擎 可被利用的獨(dú)立搜索引擎稱為 源搜索引擎 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)化利用源搜索引擎的 技術(shù) 稱為 元搜索技術(shù) m e t a s e a r c h i n gt e c h n i q u e 元搜索技術(shù)是元搜索引 擎的核心 元搜索引擎分為并行處理式和串行處理式兩大類 并行處理式元搜索引擎 將用戶的查詢請(qǐng)求同時(shí)轉(zhuǎn)送給它調(diào)用鏈接的多個(gè)獨(dú)立型搜索引擎進(jìn)行查詢處 理 串行處理式元搜索引擎將用戶的查詢請(qǐng)求依次轉(zhuǎn)送給它調(diào)用鏈接的每一個(gè) 獨(dú)立型搜索引擎進(jìn)行查詢處理 西華大學(xué)碩士學(xué)位論文 元搜索引擎是用戶同時(shí)利用多引擎進(jìn)行網(wǎng)絡(luò)搜索的中介 檢索時(shí) 元搜索 引擎根據(jù)用戶提交的檢索請(qǐng)求 調(diào)用源搜索引擎進(jìn)行搜索 對(duì)搜索結(jié)果進(jìn)行匯 集 篩選 刪并等優(yōu)化處理后 以統(tǒng)一的格式在同一界面集中顯示 元搜索引 擎雖沒有網(wǎng)頁(yè)搜尋機(jī)制 亦無(wú)獨(dú)立的索引數(shù)據(jù)庫(kù) 但在檢索請(qǐng)求提交 檢索接 口代理和搜索結(jié)果顯示等方面 均有自己研發(fā)的特色元搜索技術(shù)支持 對(duì)搜索 結(jié)果的顯示 不同的元搜索引擎有不同的處理技術(shù) 由于元搜索引擎設(shè)定的搜 索結(jié)果排序依據(jù) 最大返回結(jié)果數(shù)量 相關(guān)度參數(shù)及優(yōu)化機(jī)制等不同 調(diào)用相 同的源搜索引擎的不同元搜索引擎顯示搜索結(jié)果的數(shù)量多少 排序先后 結(jié)果 信息描述選擇亦有較大差異 1 9 9 5 年華盛頓大學(xué)碩士生e r i c s e l b e r g 和o r e n e t z i o n i 推出第一個(gè)元搜索 引擎 m e t a c r a w l e r 以來 這一新型的網(wǎng)絡(luò)檢索工具異軍突起 發(fā)展迅速 目前 可用的元搜索引擎已近百種 盡管元搜索引擎存在著功能上的局限 但其以含 蓋較多的搜索資源 能夠在盡可能短的時(shí)間內(nèi)提供相對(duì)全面 準(zhǔn)確的搜索結(jié)果 等諸多優(yōu)異功能受到用戶的青睞 已漸成為一種不可或缺的極具潛力的網(wǎng)絡(luò)檢 索工具 現(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(xué)鬻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個(gè)性化搜索引擎 p e r s o n a l i z e ds e a r c he n g i n e 個(gè)性化搜索引擎是接受用戶輸入的查詢?cè)~ 來查找用戶的感興趣信息 此 系統(tǒng)在與用戶的頻繁交互中記下用戶的個(gè)人興趣愛好 并建立用戶興趣模型 當(dāng)用戶使用時(shí) 向用戶提供某一方面的或全部的感興趣信息 比如 一喜歡 獵 豹 這種動(dòng)物的用戶搜索 獵豹 時(shí) 將得到有關(guān) 獵豹 這一生物的信息 而不是獵豹汽車或其它 1 0 西華大學(xué)碩士學(xué)位論文 個(gè)性化搜索引擎系統(tǒng)必須滿足以下三個(gè)要求 1 1 個(gè)性化的 個(gè)性化搜索引擎系統(tǒng)必須是為特定的用戶服務(wù)的 2 高適應(yīng)性的 由于用戶的興趣是在改變的 所以 系統(tǒng)必須能察覺用戶的興趣改變了 系統(tǒng)必須根據(jù)這些改變采取相應(yīng)的措施 3 1 易擴(kuò)展的 個(gè)性化搜索引擎系統(tǒng)應(yīng)該能探測(cè)新的領(lǐng)域 以此來發(fā)現(xiàn)用戶潛在的興趣 總之 個(gè)性化搜索引擎系統(tǒng)應(yīng)該能及時(shí)地提供與用戶的需求相匹配的信息 并在用戶興趣改變時(shí)作出相應(yīng)的變化 所以 系統(tǒng)不但要了解用戶當(dāng)時(shí)的需求 還應(yīng)能探索不同的領(lǐng)域來發(fā)現(xiàn)用戶新的興趣愛好 其代表有g(shù) 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 個(gè) 臻藿 二二二 三三 二二二黜 蔓夏 一 攮墊囂艘送纛差型 圖2 3 中搜個(gè)性化搜索引擎 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 聚類技術(shù)的整合 它通過元搜索引擎獲 取來自不同傳統(tǒng)搜索引擎的搜索結(jié)果 然后對(duì)搜索結(jié)果 一般是文檔的一些片 段 而不是整篇文章 進(jìn)行聚類 形成簇集 每個(gè)簇中均包含對(duì)應(yīng)的文檔集 西華大學(xué)碩士學(xué)位論文 聚類搜索引擎與傳統(tǒng)搜索引擎的最大區(qū)別就在于 搜索結(jié)果表現(xiàn)形式的不同 傳統(tǒng)搜索引擎的搜索結(jié)果是一按相關(guān)性排序的結(jié)果列表 而聚類搜索引擎則是 將搜索結(jié)果進(jìn)行再聚類 形成類標(biāo)簽和對(duì)應(yīng)的類內(nèi)容的過程 使用聚類搜索引 擎時(shí) 用戶首先也是輸入查詢?cè)~ 然后選擇感興趣的類標(biāo)簽 得到相應(yīng)的類內(nèi) 容 即搜索結(jié)果 實(shí)質(zhì)上它起到 信息導(dǎo)航 的作用 也是對(duì)搜索結(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 囂習(xí)匹 遂鯊j 圖2 4 v i v ls i m o 聚類搜索引擎 2 2 搜索結(jié)果表現(xiàn) 搜索結(jié)果是反映一個(gè)搜索引擎質(zhì)量好壞的重要指標(biāo) 也是用戶獲取自己感 興趣信息的入口 返回與查詢?cè)~最相關(guān)的搜索結(jié)果一直是所有搜索引擎提供商 追求的目標(biāo) 在搜索結(jié)果一定的情況下 如何更好地組織和表現(xiàn)搜索結(jié)果 將 直接影響用戶查找信息的效率 搜索結(jié)果表現(xiàn)形式目前主要有 1 評(píng)價(jià)列表 2 人工目錄 3 聚類 2 2 1 評(píng)價(jià)列表 r a n k e dl i s t 評(píng)價(jià)列表 見圖2 5 是目前搜索引擎采用的比較常見的方式 它按文檔與 查詢?cè)~的相關(guān)程度來排序 把最相關(guān)的搜索結(jié)果顯示在前面 評(píng)價(jià)列表中的每 個(gè)結(jié)果通常由標(biāo)題 t i t l e u r l 和來自文檔的片段等構(gòu)成 用戶通過瀏覽評(píng)價(jià) 列表來確定信息所在的位置 然后點(diǎn)擊位置上的u r l 打開對(duì)應(yīng)的文檔 即完成 用戶的一次查找過程 但它也存在著很多不足之處 g r o u p e r 9 9 w e i s s 0 1 1 用戶為了找到所需的文檔 往往得瀏覽很長(zhǎng)的結(jié)果評(píng)價(jià)列表 甚至通過 翻頁(yè)才能找到 1 2 用戶無(wú)法知道查詢?cè)~與文檔的相關(guān)程度 也無(wú)法知道文檔問的相關(guān)性 3 結(jié)果沒有經(jīng)過分類 用戶很難快速找到需要的文檔 玨華大學(xué)碩士學(xué)位論文 c o 昭i e 所有同站星曩妻 匾旦上監(jiān)捱 圜夏目量 研掰 一型盤邋 療搜索所有網(wǎng)站r 搜索所有中文網(wǎng)頁(yè)r 搜索簡(jiǎn)體中文網(wǎng)頁(yè) 1 日 3 0 日 電稿報(bào)集團(tuán) 藪i 麗l 假冒墨盒 硒鼓 電腦城外并奔馳的郡是敲假冒打印耗襯生意的一 曾經(jīng)有 段時(shí)間 本地的工t 螢子里有過這樣的 c o p i 曲t c z 0 0 4c p c t c 橢 電腦報(bào)版權(quán)所 有渝i c p 證b 2 2 0 0 3 0 0 0 3 號(hào)如有意見請(qǐng)與我們聯(lián)蓉信息部制作 c p