4. Information Retrieval

 一、IR的介紹 

  • Information Retrieval (資訊檢索)原先應用在圖書館的資料檢索系統
  • 隨著Internet的蓬勃發展,人們於網路上進行網站搜尋與全文檢索的需求,也與日俱增。例如GOOGLE和YAHOO的搜尋 
  • 資訊檢索是利用一定設備和方法,從某種格式上面的文獻、 資料或數據中查找所需資訊的一種過程 
  • 隨著不同資訊型態的出現,資訊檢索的技術亦逐漸多樣化,以適應各種型態的資訊。

 二、使用IR可能會遇到的問題

  • 字串不匹配(vocabulary mismatch):查詢詞與文件記載(或索引詞)不同 
    * 同義:「筆記型電腦」vs「筆記本電腦」(形似),「閣揆」vs「行政院長」 
    * 廣狹義:「攜帶型」vs「掌上型」
  • 使用者需求差異大:同樣的檢索詞,但相關的文件會因人而異
    * Known item search 
       - 已知「作者」、「人名」
    * Unknown item search 
       - 無法精確表達查詢字串:人名、地名、機構名、專有名詞、特定領域名稱 
       - 不知如何表達查詢字串:「晶圓代工的發展前景」、「電視廣告對兒童的影響」
  • 領域需求差異大:斷詞需求、查詢功能 
     - EX:「中醫工會」:「治虛寒,五香、加八角、加薑,加味米酒…」
  •  資料本身不一致、不乾淨及檔案格式差異大 
     * 民83年vs 1994、年代日期格式不同 
     * 異常標點符號、字碼、dash 、single quote 
     * 資料誤植、OCR 雜訊文字 
     * Data cleaning is required
  • 文件格式、資訊架構、作業環境 
     * 需要解各種檔案格式:HTML、XML、Office、PDF、ZIP、EMAIL、BBS … 
     * 資訊來源與權限控管:File systems、DBMS、Web、Notes … 

三、 IR的模組 

目前各家IR系統所使用之Model,最常見者為Boolean Model、Vector Model,與Probabilistic Model三種。

1.   布林模式 (Boolean Model)

  • 布林模型是一個最簡單的檢索模型,以幾何理論 (set theory) 和布林代數(Boolean algebra) 為基礎,只考慮索引字集合中的各索引字是否出現
  • 優點: 
    •  呈現的方式極為簡潔且容易明白所代表的意義 
    •  速度快、檢索者可完全控制檢索過程,並預測檢索結果 
    •  對需求明確的檢索(如明確的作者名、題名)非常有效
  • 缺點: 
    •  對於每份文件的預測不是 “相關” 就是 “不相關”,並沒有部分符合 (partial match) 查詢條件的這種結果 
    •  查詢結果沒依照符合程度排序、一般使用者較難表達複雜查詢條件

2.    向量模式 (Vector Model)

  • Salton 等人首先於1971 年提出向量模型的檢索系統。
  • 不同於布林檢索的是,它不再只是二元化的比對,而有了部分比對及相似度的觀念
  • 藉由每個索引項目不同的權重值,來計算文件與查詢之間的相似程度。
  • 轉換文件及查詢語句到向量空間後比對相似度,常用餘弦夾角(cosine)表示
  • 可允許使用者輸入任意字串,查詢時不必受資料誤植、錯字的限制
  • 可概略稱為「近似字串查詢」、「容錯查詢」、或是「模糊搜尋」(fuzzy search)、「近似自然語言查詢」或「自然語言查詢」

3.      機率模式 (Probabilistic Model)                                      

  • 典型機率模型為1976由Roberston及Sparck Jones 所提出的,這個模型後來被稱之為二元獨立檢索 (binary independence retrieval, BIR) 模型
  • 機率模型嘗試以機率的架構來解資訊檢索問題
  • 將查詢詞彙與相關文件的不確定性,以機率描述並加以運算亦可做到向量模式的查詢效果,兩者不同處在基本假設與運算模式
  • 機率模型的概念
    • 透過一組標註好的資料 (查詢及其對應的相關文件) 或稱為訓練資料 (training data)
    •  由這些標註的資料,遞迴的去計算其間的分佈關係
    • 使得查詢與對應文件的機率計算能達到最大 
    •  最後得到一個與使用者查詢相關的文件集合。

四、TF(term frequency) & IDF(inverse document frequency)

  • TF-IDF是一種統計方法,用以評估一字詞對於一個文件集或一個語料庫中的其中一份文件的重要程度。
  • 字詞的重要性隨著它在文件中出現的次數成正比增加,但同時會隨著它在語料庫中出現的頻率成反比下降。如下圖

TF(term frequency)

  • 指的是某一個關鍵字在該文件中出現的次數。這個數字通常會被正規化,以防止它偏向長的文件。
  • 譬如說某篇文章裡面,「電腦」這個詞出現很多次,或是「使用者需求」這個詞出現很多次,那麼這些詞句的出現頻率,就會很高。
  • 一篇文章中出現很多次的詞句,必定有其重要性。

 TF公式為: "每個字串的出現次數"除以"所有字串的出現次數的總和"。字串即是term。

  •   tf(i,j) = n(i,j) / ( n(1,j)+n(2,j) + ... n(k,j) )

IDF(inverse document frequency)在了解 IDF 之前,需先了解 DF 是甚麼。

  • DF 就是Document Frequency:在固定 N 篇文章,某個關鍵字的 Document Frequency (DF),就是說這個關鍵字在 N 篇文章裡面出現了幾次。
  • Inverse Document Frequency (IDF) 則是把 DF 取倒數,即一個數字乘以 IDF,就等於是除以 DF 的意思。
  • 如果搜尋一串字,所有網頁都有這串字,而且這串字在每個網頁都出現很多次,是不是表示這個字串沒什麼重要性?
  • IDF的表示,是以某一字串出現在越多的地方則代表越不重要愈不重要

IDF公式為:

  • idf = LOG ( 所有的網頁數/ 字串出現的網頁數)
  • idf(i) =LOG( | D | / | { d: d 中有字串 t(i)} | ) 

        以上| D | 表示所有的網頁數, | { d: d 中有字串 t(i)} | 表示 字串出現的網頁數。

  • 用LOG的好處是將除法換成減法,因而:

tidf(i) =LOG( | D | ) - LOG( | { d: d 中有字串 t(i)} | )

 有了 TF IDF 以後,我們就可以計算其結果,對每一個關鍵字都算出一個分數 。這個分數的高低,就代表了這個關鍵字在某篇文章中的重要程度。為甚麼我們說這樣子可以找出重要的字,而不是常出現的字呢?因為 TF 會把某篇文章中,出現最多次的排在第一位,其次的排在第二位,以此類推。然而乘上 IDF 以後,那些常常出現的字,像是英文中的 “the”、”a”、”it”,因 IDF 小,所以乘上 TF 以後,重要性就變低了,電腦程式就不會把這些常出現的字,誤認為是重要的字了!

TF-IDF(term frequency, inverse document frequency)表示式:

  -->  tfidf(i,j) = tf(i,j) * idf (i)

五、Precision and recall 查準率及查全率 

在資訊檢索或資料探勘的領域中,一個最基本的問題就是到底回傳回來的結果,是不是使用者想要的?回傳的效率有多好?我們可用下面兩個評估檢索結果的方法,叫做【查準率(Precision)】和【查全率(Recall)】 。

  • Precision = Relevant Documents Retrieved / Total Retrieved Documents

         --> (抓回來的相關文章數量)  / (抓回文章的總數)

  • Recall = Relevant Documents Retrieved  / Total Relevant Docue  

        -->  (抓回來的相關文章數量) / (相關文章的總數)

  

從上面的公式可以看出來,Precision和Recall的分子都是Relevant Document Retrieved(抓回來的相關文章數量),差別的地方在於Precision的分母是【抓回文章的總數】;而Recall的分母則是【相關文章的總數】。

 EX:假設現在資料庫中有10000筆資料,和美食有關的文章有500篇。使用者在輸入美食的關鍵字後,回傳的文章有4000篇,其中有400篇是和美食有關的。

Precision = 400 / 4000 = 10%
Recall = 400 / 500 = 80%
其結果為:這個搜尋引擎的查準率是10%、查全率是80%。

我們可以將以上的兩個比率畫分成下面的四個象限:

 


tp : 代表文章和此query有相關,而且系統判斷正確回傳。
fp :
代表文章和此query沒有相關,但是系統判斷錯誤卻被搜尋引擎回傳。
fn :
代表文章和此query有相關,但是系統判斷錯誤沒有回傳。
tn :
代表文章和此query沒有相關,而且系統判斷正確沒有回傳。
所以我們得出:
Precision = tp / tp+fp

Recall = tp / tp+fn

檢全率和檢準率間存在一種反比關係。也就是說,在檢索中,如果要提高檢全率,必定會降低檢準率,反之亦然。如下圖

 

Reference:

1. Precision and Recall - Information Retrieval

http://kevingo75.blogspot.com/2008/11/precision-and-recall-information.html

2.Information Retrieval Techniques for Spoken Language Processing

 Lee-Feng Chien (簡立峰) Institute of Information Science  Institute of Information Science Academia  Academia Sinica Sinica, Taiwan

3. 資訊檢索與知識探勘 - 曾元顯-輔仁大學圖書資訊學系

 

----以下來自木瓜的共筆

開放性連結機制協定OPENURL

         

 整合檢索協定

過去靜態連結之缺點:以一對一方式,使用者在檢索後無法獲得更多額外資訊。

動態連結:開放性的連結機制 => OpenURL,建立聯合目錄 => OAI
 

OpenURL

特性:可將網路資源以包裹詮釋資料或網路辨識碼的網路資料傳輸語法,可以解決一些傳統靜態連結的問題。傳統資源大都是只能連結某一個特定的資源(如 資料庫代理商),若多個資料庫代理商皆可提供某一篇文獻,傳統連結無法讓使用者取得最適當的連結,開放連結則可以解決這樣的問題。OpenURL屬於一種在Web間傳遞訊息的機制。

定義:應用於Web上超連結的一種標準陳述語法,藉由已經定義好的標籤(tag),增進Web超連結能力。

目的:

         1. 定義一個標準Internet資料連結的陳述語法。
         2. 讓服務提供者(target)可以輕易解析資料提供者(source)所傳送的要求。
         3. 資料提供者能夠輕易地對服務提供者送出深度連結服務要求。

協定內容:基本語法是與一般Internet上CGI程式所用的HTTP GET與HTTP POST類似。OpenURL的語法將透過metadata(如ISSN)嵌入URL當中。

其語法有兩部分

  1. BASE-URL:就是用來接收OpenURL資料的啟始位置,如 http://www.sfx.co.il/sfxmenu
  2. DESCRIPTION:這部分就是要送給服務提供者的metadata物件細節。每個metadata物件間以&符號區隔。

OAI(Open Archives Initiative)

特性:OAI-PMH運用Internet及詮釋資料(metadata)兩種技術,在增強整合檢索功能及簡化系統開發難度上,達成了極佳的平衡。

目的:

  1. 是提供一具備應用程式獨立,且可互相運作。
  2. 提升Web上多種從事於文件內容出版發行的社群應用框架。

主要目標:

  1. 簡化文件內容有效的傳播。
  2. 提升電子化文件的存取。
  3. 擴展存取數位化資料種類的範圍。

協定內容:OAI元件主要分為OAI Service Provider與Data Provider。以OAI協定為基礎的聯合目錄架構,主要是由OAI的service provider (服務系統)定期向data provider (各典藏單位之資料庫系統)抓取metadata資料,建立集中式之聯合目錄。

規範:

  1. 定義資料提供者透過HTTP的協定發佈metadata的機制。
  2. 定義一個能夠從儲存器獲取含有metadata資料錄的機制。

整合檢索:由於OAI是架構在HTTP上的應用協定,因此其命令集即是透過HTTP所使用前端與後端傳輸之變數名稱與其內容,觸發後端對應之伺服器程式,依據變數內容處理後傳回之結果,並須遵照OAI協定XML Schema所規範的XML格式傳送資料。

OpenURL與OAI之比較:

    兩種機制的主要目的都在提供整合性的資訊查尋與連結服務。

    不同運作方式:

   1. OpenURL是一種相當簡單的語法,主要目的在即時、分散的連結資源,但OAI主要目的則在擷取各典藏系統的metadata,並將這些 metadata整合在OAI的service provider,讓使用者直接在此進行整合查尋,它所建立的是一個集中式的聯合目錄。
   2. 對使用者而言,OpenURL因屬即時、分散連結,若同時連到好幾個target,速度會較慢;而OAI 則為集中式的目錄,所以查尋速度較快。
   3. 無論對OpenURL或對OAI而言,如果要取得數位資料,除非是免費的數位資源,否則都需先取得授權。
   4. OpenURL與OAI都是非常簡單的機制,技術上並不困難,困難的是整個服務環境的配合建置,包括需有數位資源的命名系統(如DOI)、出版單位需支持此命名系統,成立命名註冊機制(如CrossRef)、以及有中介的服務機構(如SFX)。


資料參考來源

  1. 數位數位資源整合檢索協訂講義,臺灣師範大學圖書資訊學研究所陳昭珍教授 http://proj1.sinica.edu.tw/~ndaplib/channels/dlm_paper/std.-4%2092.pdf
  2. 數位典藏異質系統互通機制 : 以 OAI 建立聯合目錄之理論與實作(上),臺灣師範大學圖書資訊學研究所陳昭珍教授 http://www2.ndap.org.tw/newsletter06/news/read_news.php?nid=737
  3. 數位典藏國家型科技計畫-聯合目錄系統建置計畫成果報告 http://nccur.lib.nccu.edu.tw/bitstream/140.119/4800/1/922422H004012.pdf
  4. 資訊組織與檢索相關課程之整合研究 http://research.dils.tku.edu.tw/course/project3/%E7%AC%AC%E4%B8%89%E5%B9...