Google網頁排序能力和回覆款目品質探討:以檢索失誤率為例

蔡佳霖(Chia-Lin Tsai

輔仁大學圖書資訊所碩士班研究生

 

吳政叡(Cheng-Juei Wu

輔仁大學圖書資訊所專任教授

關鍵字:檢索失誤率,排序,資訊檢索評估,Retrieval Error RatioGooglePageRankRankingInformation Retrieval Evaluation

中文摘要

為了增進檢索品質,Google搜尋引擎採用PageRank排序技術,以類似引文分析(citation analysis)的網頁連結計算方式,來排序重要性較高的網頁。不同於一般搜尋引擎以詞彙加權(term weighting)方式,作為相關排序(relevance ranking)的依據。本文以十位檢索者進行檢索實驗,來探討Google使用PageRank技術後的整體網頁排序能力。實驗結果顯示Google利用PageRank排序計算方式,確實優先排序使用者需要的文件;但前20筆回覆款目的平均檢索失誤率仍高達19.5%~21.5%,表示Google回覆款目品質仍易誤導使用者,尚有改進空間。

壹、前言

隨著全球資訊網WWW與全文檢索技術的發達,搜尋引擎已成為獲取資訊、檢索資料的主要來源之一。然而隨著網際網路的普及,網頁的成長數量逐日劇增,導致搜尋引擎具有高回收率、低精確率的現況。於是專家學者除了一方面發展多樣化的檢索策略與技巧外,另一方面則設法改進排序演算法,將高相關或重要文件優先排列於前,供使用者挑選,增加檢索品質。

目前以創新的排序(Ranking)方式,來提昇檢索品質與精確率的搜尋引擎中,以Google [1]最具代表性。其使用的專利排序技術PageRank不同於詞彙加權(term weighting)方式,而是利用類似引文(citation)的網頁連結特性,計算網頁被連結(引用)的次數,透過演算計分決定網頁排列順序,增進檢索品質[2]

PageRank排序技術,是希望透過客觀的引文(citation)計量方式,能與人們對於文件重要性的主觀判斷有所一致[3]。對於符合使用者需求之重要網頁文件,能夠優先排序,提供使用者挑選。

因此本文將先介紹搜尋引擎相關排序技術,包括詞彙加權排序和PageRank排序。並設計一簡單實驗,對於Google利用PageRank排序技術是否能將重要性較高網頁文件優先排序,以符合使用者需求,進行初步探討。此外也將利用檢索失誤率(RER)來衡量Google回覆款目的品質。

貳、排序技術探討

資訊檢索系統中,排序是為了擷取重要及相關文件,其意義與目錄功能相同,在於協助使用者能夠正確並迅速地取得所需文件。

在搜尋引擎全文檢索環境下,系統以檢索詞彙比對出大量文件時,使用者通常先由排列較前的回覆款目進行判斷是否需要,再進一步點選閱讀原文。因此檢索系統如何將文件按相關或重要程度排序,提供使用者優先挑選,即為重要研究課題。以下將介紹常見的搜尋引擎排序技術。

一、 詞彙加權排序

以一般搜尋引擎而言,相關排序(relevance ranking)的計算方式,主要是針對檢索詞彙(search term)進行處理。文件相關程度的高低,依檢索詞彙出現位置(location)或出現頻率(frequency)具有重要影響 [4]。例如,檢索詞彙出現在網頁文件的title標籤中,將比出現於內文標題或是內文主體,具較高相關程度;而網頁文件中檢索詞彙出現的頻率越高,也代表其相關程度越高。

搜尋引擎常使用的排序計算模式以Boolean ModelVector Model為主:[5]-[6]

1.     Boolean Model:為最簡單的檢索模式,單純使用布林邏輯判斷文件中是否有檢索詞彙存在,但缺乏程度上比對。雖有Boolean Spreading ActivationMost-cited演算法加以改良,加入網頁文件彼此參考關係,和檢索詞彙出現於所連結網頁的考量。但仍無法計算詞彙出現頻率,故文件排序效果不彰。

2.     Vector Model:是利用三角函數的Cosine定理,將檢索詞彙與文件相關程度作內積相乘,找出所夾擠的面積範圍,面積越大則相關程度越高。最常見的演算法為TFxIDF,用以計算字彙頻率與文件重要性。TFTerm Frequency)為檢索詞彙於文件中出現頻率;IDFInverse Document Frequency)則是指資料庫中含有檢索詞彙的文件出現頻率越低,該文件越顯得重要。

二、 網頁連結排序

運用網頁超連結特性於排序計算方式上有WebQueryHITSPageRank[7]。其中以實際運用於Google搜尋引擎上的PageRank排序技術較具代表性。

Google所使用的PageRank排序技術是由Sergey BrinLawrence Page1998年提出[8]。其認為網頁超連結(hyperlink)的特性結構,類似於用來計算學術論文被引用次數的引文分析(citation analysis)。藉由此種連結(引用)關係,可透過公式計算網頁排名值(PageRank),來決定網頁的重要性。

PageRank的計算觀念為,網頁彼此連結的關係可分為連結(forward links)與被連結(backlinks)兩種(見圖一),連結與被連結可視為引用(citing)與被引用(cited)的關係。被連結較多的網頁如同被引用較多,代表該網頁具有較高的重要性,網頁排名值亦較高。並且若是被重要性較高的網頁所連結,則被連結網頁的重要性與排名值也相對較高。

網頁連結與排名值的關係,如(圖二)所示[9]。網頁A的排名值為100,含有兩個連結(forward links),連結出去排名值平均為50。網頁B排名值為9,含有三個連結(forward links),連結出去排名值平均為3。網頁C被網頁A與網頁B所連結(backlinks),故總排名值為53。網頁D只被網頁A所連結(backlinks),故排名值為50

PageRank的計算公式為:假設網頁AT1T2…..Tn個網頁連結(backlinks),參數d為一控制因素(值介於1-0之間-通常設0.85),CA)為網頁A的連結數量(forward links),則網頁APageRank值可由以下公式算出。[10]-[11]

PRA)=(1-d+ dPRT1/ CT1+…….+ PRTn/ CTn))

所求得的PRA)值即為網頁A的在所有網頁中的連結分布機率,代表網頁A的重要性。

因此,Google在排序網頁文件時,會先以檢索詞彙出現在網頁文件的標題(title)、連結文字(anchor)、網址(URL)或網頁文字的大小字型(html large font or small font)中,進行加權計分。最後再結合PageRank計算網頁排名值,將重要性較高的網頁文件突顯出來,加以優先排序。[12]

參、搜尋引擎的評估

一、 精確率與回收率

檢索系統評估的目的,在於了解檢索結果滿足資訊需求的程度[13],亦是了解系統回饋結果(客觀)與使用者需求滿足(主觀)的平衡程度。常用以評估檢索系統的公式理論有精確率(precision ratio)與回收率(recall ratio)。

精確率代表檢索到相關文章比例,回收率則是用以計算資料庫中相關文章被檢索出來的比例,所求得的比例愈高,表示系統效能愈好。精確率與回收率公式如下:[14]

1.         精確率公式 p

p表示精確率

a表示檢索到相關文章筆數

e表示所有檢索到文章筆數

2.         回收率公式r

r表示回收率

a表示檢索到相關文章筆數

f表示資料庫中所有相關文獻筆數

由公式中,可了解評估公式著重計算相關文件與檢索結果的筆數。現今,搜尋引擎的檢索結果筆數動輒上萬筆,過多的檢索結果筆數,使得公式的計算面臨實際執行的困難。

同時,在相關(relevance)概念的認定上,至今仍不易了解且無一致定義。單就相關定義上即有主題相關、邏輯相關、證據相關、情境相關與心理相關等不同理論[15] -[16]。一般非專業學科的檢索者,不易分辨相關概念上的差別,且影響使用者相關判斷的因素過於廣泛,仍待進一步研究實證。[17]

因此進行搜尋引擎檢索評估時,檢索結果筆數過多,以及相關概念的不易區分,使得回收率與精確率不但面臨實際評估時計算上的困難,也逐漸失去其衡量意義。

二、 檢索失誤率

基於上述問題,新的衡量方式-檢索失誤率(Retrieval Error Ratio[18],以使用者實際檢索筆數為計算基準,避免搜尋引擎檢索結果筆數過多問題;對於相關文件的判斷,以使用者主觀判斷是否需要為主,與一般相關文件(relevant document)認定並不相同。

檢索失誤率評估上著重於檢索系統所提供之回覆款目的品質。對於影響使用者判斷需要因素並不深入分析,單純以使用者主觀因素進行檢索與判斷文件需要與否。

評估方式則是將檢索所得回覆款目,先讓使用者判斷需要與否,再進一步點選閱讀原始文件,進行確認是否為需要文件,並分別記錄其結果後再加以比較。檢索失誤率計算公式為:

檢索失誤率=

檢索失誤分為第一型失誤與第二型失誤,第一型失誤為使用者由檢索系統提供款目資訊,判斷需要原文,點選閱讀後卻發現是非需要文件;第二型失誤代表使用者由檢索系統提供款目資訊,判斷非需要文件,點選原文後發現為需要文件。檢索失誤率判斷表如下:[19]

 

肆、實驗動機與設計

一、 實驗動機

為了解Google搜尋引擎利用PageRank排序技術,是否能將使用者需要的重要網頁文件優先排序,以及回覆款目資訊,是否協助使用者正確挑選所需網頁原始文件。因此進行下面的實驗探討。

二、 檢索者背景

由於本次實驗僅為初步探討性質,也限於時間與人力上的安排,檢索使用者以對資訊檢索較為了解的五位參考館員與五位圖資系學生為主,協助進行檢索實驗。

三、 實驗設計

為求符合實際檢索者行為,本實驗以標準資訊檢索流程(見圖三)為基礎,進行實驗設計。

1.     操作型名詞定義

排序能力:指Google搜尋引擎利用PageRank排序技術,將使用者需要之重要網頁排列於前的能力。

回覆款目:指Google回覆檢索結果中,有關原始文件之摘要資訊。包括標題Title、檢索詞彙的前後文和URL網址等。

2.     檢索過程與判斷

十位檢索者分別於Google搜尋引擎上進行檢索實驗[20]。檢索者以本身資訊需求(information need)概念所形成的檢索詞彙(search term)進行檢索。檢索過程中,網頁文件的需要與否,由檢索者本身主觀判斷,以求選擇檢索詞彙與判斷文件需要與否的一致性,避免詞彙意義上認定問題。

3.     檢索詞彙模式的選擇

為了符合檢索者實際網頁檢索行為(web search behavior),實驗中檢索詞彙分為單一詞彙與回饋修正詞 彙,分別產生兩種檢索結果。

單一詞彙指的是,檢索者選定一檢索詞彙代表資訊需求概念,進行檢索後,直接進行挑選閱讀文件。

回饋修正詞彙則是指,較熟悉檢索搜尋引擎的使用者,會初步掃瞄(scan)檢索結果,確認檢索結果是否符合資訊需求概念。若滿意檢索結果,則進行挑選閱讀原始文件;反之則利用布林邏輯檢索功能,回饋修正檢索詞彙,直到檢索結果滿意才進行挑選閱讀原始文件[21]。使用者最後所選定的檢索詞彙即為回饋修正詞彙。

4.     檢索筆數的設定

據指出,只有7% 的搜尋引擎檢索者會瀏覽超過前三頁(30筆)的檢索結果[22]。因此本實驗針對搜尋引擎所回覆的檢索結果(120筆)及(201220筆)分別進行判斷與勾選。透過區隔筆數的檢索實驗,進行了解系統是否有效地排序重要文件。

5.     實驗步驟

依前面說明,實驗步驟設計如下。

(1)    檢索者由自身概念產生的檢索  詞彙進行檢索,由單一詞彙與回饋修正詞彙分別進行一次。

(2)    由(120筆)及(201220筆)的回覆款目資訊,判斷是否需要,並記錄勾選。

(3)    點選(120筆)與(201220筆)的網頁原始文件,確認是否符合需要,並記錄勾選。

(4)    計算十位檢索者勾選的(120筆)、(201220筆)原文需要平均數及檢索失誤率。

(5)    彙整實驗結果並製成表格,表格分為單一詞彙以及回饋修正詞彙兩類,其中分列館員、學生實驗 結果與總平均表(附表1~6)。

   

伍、實驗結果與分析

本次實驗中,十位檢索者共進行二十次檢索實驗,所產生的表格數據可分為三類,茲分述如下。

一、 單一詞彙實驗結果(附表1~2

120筆)數據:

1.     原文需要的平均筆數,館員平均有7.8筆,學生平均為10.4筆。

2.     檢索失誤的平均筆數,館員平均有1.8筆,學生平均為6筆。

201220筆)數據:

1.     原文需要的平均筆數,館員平均為1.6筆,學生平均為2.6筆。

2.     檢索失誤的平均筆數,館員平均有2.8筆,學生平均為4筆。

二、 回饋修正詞彙實驗結果(附表3~4

120筆)數據:

1.     原文需要的平均筆數,館員平均有8.2筆,學生平均為8.8筆。

2.     檢索失誤的平均筆數,館員平均有4.6筆,學生平均為4筆。

201220筆)數據:

1.     原文需要的平均筆數,館員平均為2筆,學生平均為1筆。

2.     檢索失誤的平均筆數,館員平均有3.2筆,學生平均為3.6筆。

三、 實驗結果總平均(附表5~6

120筆)數據:

1.     單一詞彙實驗,原文確認平均筆數需要為9.1筆,檢索失誤為3.9筆。

2.     回饋修正詞彙實驗,原文確認需要為8.5筆,檢索失誤為4.3筆。

201220筆)數據:

1.     單一詞彙實驗,原文確認平均筆數需要為2.1筆,檢索失誤為3.4筆。

2.     回饋修正詞彙實驗,原文確認需要為1.5筆,檢索失誤為3.4筆。

四、實驗分析

由實驗結果數據分析如下:

(一) Google於檢索結果中,(120筆)的檢索者需要文件的平均筆數遠高於(201220筆),約6筆 以上。並不受檢索者身份(館員或學生)和檢索詞彙模式(單一詞彙與回饋修正詞彙)的影響。

(二) Google120筆)檢索總失誤平均在3.9~4.3筆之間,檢索失誤率仍達19.5%~21.5%。符合先前針對國內外七個著名搜尋引擎的實驗數據,平均檢索失誤率為20.7%[23]

因此由實驗分析(一)可初步推論,Google所回覆的前20筆檢索結果,符合使用者需求文件平均筆數較高,顯示出Google使用PageRank排序技術,確實增進了整體排序能力。不過,根據上面實驗分析(二)的數據顯示,Google20筆的檢索失誤率仍達19.5%~21.5%,表示其回覆款目提供的資訊品質欠佳或不足,故造成使用者錯誤點選與錯失資料的機率仍偏高。

陸、結語

全球資訊網的普及盛行,使得搜尋引擎成為協助使用者進行獲取網頁資料的重要角色,因此提昇搜尋引擎的檢索品質,一直是資訊檢索領域的專家學者所努力的目標。

本文中的實驗結果,初步證實了Google搜尋引擎利用PageRank排序技術,確實能將重要網頁優先排列於前面20筆檢索結果,增加檢索品質。數據顯示出Google搜尋引擎(120筆)檢索結果中,檢索者需要文件的平均筆數,高於(201220筆)檢索結果達6筆以上(請參考附表56中之點選原文確認需要項目)。

另一方面,Google120筆)檢索結果中(單一詞彙與回饋修正詞彙實驗),平均檢索失誤率仍達19.5%~21.5%,與一般搜尋引擎的平均檢索失誤率20.7%相同[24]。顯示出搜尋引擎的共同問題在於回覆款目所能提供資訊有限,僅以標題、檢索詞彙前後幾行文字與URL網址,提供使用者判斷挑選,使用者仍容易檢索失誤,導致耗費時間成本與漏失所需資料。

總結來說,搜尋引擎在增加檢索品質方面,除了改善搜尋引擎排序能力之外,回覆款目品質好壞亦同樣重要。因此搜尋引擎結合電子式目錄-元資料(metadata)來改良回覆款目品質,利用簡單易學的都柏林核心集(Dublin Core)來推行網頁作者著錄,改善回覆款目品質,大幅降低檢索失誤率[25],將是全球資訊網發展必要的下一步。

柒、誌謝

        本實驗承國家圖書館參考組莊建國先生、袁明嶸先生、胡錦華小姐、王嫥嫥小姐、蔡幸芳小姐;輔仁大學圖資系陳香文同學、潘翠蘭同學、李佳玲同學、王淑君同學、張毓真同學的參與協助,在此表達感謝之意。


【註釋】

[1] <http:\\www.google.com>

[2] Sergey Brin and Lawrence Page,”The Anatomy of a Large-Scale Hypertextual Web Search Engine,”Computer Networks and ISDN Systems 30(1998):107-117.

[3] 同註2,頁109-110

[4] Danny Sullivan,”How Search Engines Rank Web Pages,” <http://searchenginewatch.com/webmasters/rank.html>(26 June, 2001)

[5] Ricardo Baeze-Yates and Berthier Ribeiro-Neto, Modern Information Retrieval (ACM Press, 1999), 380.

[6] Budi Yuwono and Dik Lun Lee, “Search and Ranking Algorithms for Locating Resources on the World Wide Web,” International Conference on the Data Engineering (1996):164-171.

[7] 同註5,頁380-381

[8] Lawrence Page, et al, “The PageRank Citation RankingBringing Order to the Web,” Stanford Digital Library Technologies, Working Paper 1999-0120 (1998):1-17..

[9] 同註8,頁3-4

[10] 同註8,頁4

[11] 有關PageRank技術,於此僅說明排序計算概念,詳細演算規則可參考註8,頁4-7

[12] 同註2,頁115

[13] 黃慕萱,資訊檢索中「相關」概念之研究相關(台北市:學生書局,民85)108

[14] 黃慕萱,資訊檢索(台北市:學生書局,民85),頁270-271

[15] 同註13,頁62-70

[16] Stefano Mizzaro, “How many relevance in information retrieval?” Interacting with Computer 101998):303-320.

[17] 同註13,頁71-78

[18] 吳政叡,機讀編目格式在都柏林核心集的應用探討(台北市:學生書局,民85),頁209

[19] 吳政叡,”Retrieval Error Ratio--A New Evaluation Measure for Information Retrieval Systems” (民87),未出版。<http://dimes.lins.fju.edu.tw>.

[20] 本實驗以Google所提供基本欄位檢索功能為主,未使用進階檢索功能選項。

[21] Christoph Holscher and Gerhard Strube,”Web Search Behavior of Internet Experts and Newbies,”Proceedings of the Ninth International World Wide Web Conference(2000),<http://www9.org>.

[22] Danny Sullian,”Counting clicks and looking at links.” <http://searchenginewatch.com/serport/98/08-clicks.html>(4 Aug.1998).

[23] 吳政叡,「都柏林核心集對減低檢索失誤率的實務探討」,圖書館學與資訊科學241(874),頁62-63

[24] 同註23,頁62

[25] 以都柏林核心集著錄網頁文件的實驗中,平均檢索失誤率只為2.9%。詳細實驗內容請參見註23


附表1:單一詞彙實驗結果-館員

檢索詞彙

社區圖書館

二二八事件

六書

老莊哲學

邏輯

平均數

筆數

1 – 20筆(單位:筆數)

回覆款目

判斷需要

10

12

12

6

4

8.6

點選原文

確認需要

7

14

11

3

4

7.8

第一型失誤

315%

00%

15%

315%

00%

1.47%

第二型失誤

00%

210%

00%

00%

00%

0.42%

檢索總失誤

315%

210%

15%

315%

00%

1.89%

筆數

201 – 220 筆(單位:筆數)

 

回覆款目

判斷需要

3

1

8

3

1

3.2

點選原文

確認需要

1

2

3

1

1

1.6

第一型失誤

210%

00%

630%

210%

15%

2.211%

第二型失誤

00%

15%

15%

00%

15%

0.63%

檢索總失誤

210%

15%

735%

210%

210%

2.814%

 附表2:單一詞彙實驗-學生

檢索詞彙

兒童閱

讀運動

自願就

學方案

八國聯軍

著作權法

企業再造

平均數

筆數

1 – 20筆(單位:筆數)

回覆款目

判斷需要

16

12

12

16

19

15

點選原文

確認需要

12

9

8

11

12

10.4

第一型失誤

420%

315%

630%

630%

735%

5.226%

第二型失誤

00%

00%

210%

210%

00%

0.84%

檢索總失誤

420%

315%

840%

840%

735%

630%

筆數

201 – 220 筆(單位:筆數)

 

回覆款目

判斷需要

4

4

3

7

11

5.8

點選原文

確認需要

2

3

1

4

3

2.6

第一型失誤

210%

15%

210%

525%

840%

3.618%

第二型失誤

00%

00%

00%

210%

00%

0.42%

檢索總失誤

210%

15%

210%

735%

840%

420%

附表3:回饋修正詞彙實驗-館員

檢索詞彙

Papermaking

history

Taiwan

History

Industrial revolution

Air

engine

Education

Revolution

Elementary

School

Taiwan

Library

Computer

Furniture

平均數

筆數

1 – 20筆(單位:筆數)

回覆款目

判斷需要

12

14

9

9

14

11.6

點選原文

確認需要

8

10

6

4

13

8.2

第一型失誤

420%

420%

420%

630%

210%

420%

第二型失誤

00%

00%

15%

15%

15%

0.63%

檢索總失誤

420%

420%

525%

735%

315%

4.623%

筆數

201 – 220筆(單位:筆數)

 

回覆款目

判斷需要

5

5

4

2

7

4.6

點選原文

確認需要

1

4

2

0

3

2

第一型失誤

420%

210%

315%

210%

420%

315%

第二型失誤

00%

15%

00%

00%

00%

0.21%

檢索總失誤

420%

315%

315%

210%

420%

3.216%

附表4:回饋修正詞彙實驗-學生

檢索詞彙

知識管理

人力

圖書館

公共圖書館

利用教育

慈禧太后

八國聯軍

圖書館

學習性組織

植物

學名

介紹

平均數

筆數

1 – 20筆(單位:筆數)

回覆款目

判斷需要

10

12

10

8

12

10.4

點選原文

確認需要

6

9

8

8

13

8.8

第一型失誤

420%

315%

315%

15%

315%

2.814%

第二型失誤

00%

00%

15%

15%

420%

1.26%

檢索總失誤

420%

315%

420%

210%

735%

420%

筆數

201 – 220筆(單位:筆數)

 

回覆款目

判斷需要

0

3

5

2

11

4.2

點選原文

確認需要

0

1

2

1

1

1

第一型失誤

00%

210%

315%

210%

1050%

3.417%

第二型失誤

00%

00%

00%

15%

00%

0.21%

檢索總失誤

00%

210%

315%

315%

1050%

3.618%

  附表5:單一詞彙實驗總平均(單位:筆數)

 

1 – 20筆總平均

201 – 220筆總平均

回覆款目

判斷需要

11.8

4.5

點選原文

確認需要

9.1

2.1

第一型失誤

3.316.5%

2.914.5%

第二型失誤

0.63%

0.52.5%

檢索總失誤

3.919.5%

3.417%

附表6:回饋修正詞彙實驗總平均(單位:筆數)  

 

1 – 20筆總平均

201 – 220筆總平均

回覆款目

判斷需要

11

4.4

點選原文

確認需要

8.5

1.5

第一型失誤

3.417%

3.216%

第二型失誤

0.94.5%

0.21%

檢索總失誤

4.321.5%

3.417%