共現索引典之自動建構、評估與應用 前言 相關之研究 關鍵詞自動擷取 關聯詞自動擷取 應用範例 成效評估 結語 曾元顯 輔仁大學圖書資訊學系

Presentation on theme: "共現索引典之自動建構、評估與應用 前言 相關之研究 關鍵詞自動擷取 關聯詞自動擷取 應用範例 成效評估 結語 曾元顯 輔仁大學圖書資訊學系"— Presentation transcript:

1 共現索引典之自動建構、評估與應用 前言 相關之研究 關鍵詞自動擷取 關聯詞自動擷取 應用範例 成效評估 結語 曾元顯 輔仁大學圖書資訊學系
2001/11/16 前言 相關之研究 關鍵詞自動擷取 關聯詞自動擷取 應用範例 成效評估 結語

2 前言 檢索失敗的主要因素之一：「字彙不匹配問題」 「查詢擴展」(query expansion)
「查詢詞」與「索引詞」不相同的情況 例:「筆記型電腦」與「筆記本電腦」,「行政院長」與「閣揆」 改進方法：「查詢擴展」、「權威檔」、「索引典」 「查詢擴展」(query expansion) 加入更多與查詢主題相關的詞彙，或更改查詢詞的權重 「權威檔」 (authority file) 記錄及解決同義異名詞的工具 索引或檢索時，將各種同義異名詞對應起來，視為相同的詞彙處理

3 前言 「索引典」 (thesaurus) 除同義詞外，還有紀錄廣義詞、狹義詞、反義詞、、相關詞等
列舉主題詞彙，將詞彙間的語意或主題關係標示出來的知識庫 查詢時，可互相推薦，以擴展或縮小查詢範圍，或提示相關概念的不同查詢用語 例「攜帶型電腦」：「筆記型電腦」、「掌上型電腦」 使檢索從「字串比對層次」，提升到「語意比對層次」 人工製作索引典，準確度高，但召回率低、成本大、建構速度慢、事先選用的詞彙可能與後續或其他新進的文件無關 一般目的索引典運用在特定領域的文件檢索上，無法提升檢索效能 針對每一種文獻領域製作索引典，耗時費力

4 前言 「共現索引典」(co-occurrence thesaurus)
利用詞彙的「共現性」，自動建構「詞彙關聯」（term association） 或稱「關聯詞庫」 成本低、建構速度快、召回率高、與館藏文件用詞一致，但準確率低 詞彙關係：主題相關，不一定語意相關 例：「李登輝」與「康乃爾」、「中華電訊」與「ADSL」

5 相關研究：Salton ’89 Salton 曾提出建構共現索引典的架構： 算出各個詞彙間的相似度
「相似度」：詞彙在各文件之間，共同出現的情形（或主題相似度） 重要的索引詞彙，任兩詞彙皆拿來比對相似度 計算量至少 M2，M ：所有重要詞彙的個數 依此相似度將詞彙歸類成「索引典類別」( thesaurus classes )（或「主題類別」） Tj=(d1j, d2j, … , dnj), n：所有文件的個數

6 相關研究：Salton ’89 歸類方式，主要有： Complete-link: Single-link:
一開始，每個詞彙（元素），都單獨視為一類 兩個類別之間的相似度，若超過某個門檻值，就結合並歸成同一類，如此重複歸類 兩個類別之間的相似度，定義為跨類別元素之間相似度最低者 易產生多數個索引典類別（thesaurus class），但每類僅有少數個詞彙 Single-link: 同上述作法，但兩個類別之間的相似度，定義為跨類別元素之間相似度最高者 易產生少數個類別，但每類都有大量的詞彙 透過共現索引典的查詢擴展，檢索成效的召回率，通常可提升 10% 至 20% 小結： 歸類運算量太大，運用在大量文件上，耗時長久

7 相關研究： Crouch et al (SIGIR’90)
文件先以 complete-link 方法作歸類前處理 結果可視為一棵樹 樹葉（最末端節點）：文件本身 分枝部分：類別相似度 根據使用者給定的參數，進行文件歸類 類別相似度門檻值（設為 時，有 2 個類別 (A,B) 與 (C,D,E) ）） 每類文件篇數（設為 2 時，有2 個類別 (A,B) 與 (D,E) ） 詞頻門檻（threshold for low document frequency) 同一類中每篇文件都出現的低頻詞（低於詞頻門檻），才被歸成同一類 A B D E C 0.089 0.149 0.029 0.077

8 相關研究： Crouch et al (SIGIR’90)
文件與查詢詞彙，皆用此共現索引典加以擴展，進行檢索 檢索成效： ADI文件集（全部只有82篇文件）成效提升 10.6% 類別門檻值: 0.075, 每類文件篇數: 5, 詞頻門檻: 20 Medlars 文件集（全部有1033篇文件）成效提升 15.8% 類別門檻值: 0.12, 每類文件篇數: 3, 詞頻門檻 : 50 小結： 運算量大，只運用在文件數少的情況 參數多，且需就個別 文件集 作不同調整

9 相關研究： Chen ’96

10 相關研究： Chen (JASIS ’95) 定義非對稱的詞彙相似度 詞彙 Tj 在文件 i 中的權重:
詞彙 Tj 及 Tk 在文件 i 中的權重: Cluster_weight(Tj, Tk) Cluster_weight(Tk, Tj) 若Tj =「Artificial Intelligence」, wj =2

11 相關研究： Chen (JASIS ’95) 從 4714 文件中 (共 8 MB), 產生了 1,708,551 個詞對（co-occurrence pairs ） 由於關聯詞對太多，每個詞，限制其關聯詞數最多100 個，如此刪除了 60% 的詞對，剩下 709,659 個詞對（由 7829 個不同的詞組成） 產生上述的詞對，在 Sun Sparc 工作站上要花 9.2 CPU 小時、磁碟空間 12.3 MB 成效評估： 6個受試者，16 個預選的詞，請每個受試者先就每個詞，聯想出相關的詞彙；再從系統提示的關聯詞，判斷哪些是相關或不相關 兩種結果比較，召回率分別為 28.60% 與 61.89% ；精確率為 77.08% 及 24.17% 小結： 人工聯想精確率高、召回率低；機器產生關聯詞較多、準確度較低

12 相關研究： Sanderson and Croft (SIGIR’99)
概念階層的範例：[from Sanderson and Crofts’ paper]

13 相關研究： Sanderson and Croft (SIGIR’99)
目的：從檢出的文件中自動產生概念階層（concept hierarchies），便利使用者瞭解檢出文件的大致內容 第一步：詞彙選擇（決定哪些詞彙要列在概念階層中）: 來源 1: 檢索結果的前幾篇中比對程度較佳的段落裡，找出常常一起出現的詞彙 來源 2: 每一篇檢出文件的最相關段落裡，取符合下列條件的詞彙： (df_in_retrieved_set / df_in_collection) >= 0.1 者 平均從 TREC 的每個查詢結果的前 500 篇文件中，擷取出 2430 個詞 第二步：詞彙關聯分析: 任意兩個詞都拿來做 包含 關係（subsumption relationship）比較： P(Tj | Tk) = 1 and P(Tk | Tj) < 1, if Tj (較廣義的詞) 包含 Tk (較特定的詞) 由於上述條件太嚴苛，放寬成： P(Tj | Tk) >= 0.8 and P(Tk | Tj) < 1, if Tj 包含 Tk 平均每個查詢擷取出 200 包含對（subsumption pairs） 由這些 包含對 產生 概念階層，即包含者為父節點，被包含者為其子節點

14 相關研究： Sanderson and Croft (SIGIR’99)
成效評估：測試包含者與被包含者的關聯程度（relatedness） 由 8 個受試者判斷，67% 包含對被判斷為相關（interesting for further exploring） 比較：51% 詞彙對（隨意配對，而非用包含關係配對者）被判斷為相關 小結： 此方法在查詢時才進行，查詢反應時間會受影響 提示的詞彙只限於檢索結果的前N篇，不是一個 全域索引典（global thesaurus） 隨機配對，關聯度高，顯示詞彙選擇的重要性

15 本文的方法：Tseng ’00-’01 主要分二個步驟： 關鍵詞擷取 擷取個別文件的關鍵詞 關聯詞的分析與累積
關鍵詞：文件內有意義且具代表性的詞彙 關鍵詞：呈現文件主題意義的最小單位 各種文獻自動化處理的必要步驟。 關鍵詞的認定是主觀的判斷，不利於電腦的自動處理 「重複性」假設： 如果文件探討某個主題，那麼應該會提到某些特定的字串好幾次 具有客觀性、可自動處理 假設簡單，可適用於不同領域

16 關鍵詞擷取成效評估 評估資料： 結果： 100篇台灣新聞（抓自2000年6月3日中國時報網站） 平均每篇文件有 33 個關鍵詞
平均每篇文件有 11 (33%) 個關鍵詞不在詞庫中（含 123, 226 個詞 ） 相異的關鍵詞總共 2197 個 其中有 954 個詞（954/2197 = 43%）不在詞庫中 954 個詞中有 79 個是錯誤不合法的詞（人工檢視結果），錯誤率 8.3% 整體錯誤率則為 3.6% (=79/2197)

17 單篇文件關鍵詞擷取範例 1 : 音樂 (7) 2 : 數位音樂 (5) 3 : 下載 (4) 4 : 計畫 (4) 5 : BMG (3)
BMG Entertainment與Sony Music計畫在Internet 上銷售數位音樂。（美國矽谷/陳美滿） 根據San Jose Mercury News報導指出，BMG Entertainment計畫在6月上旬或中旬開始在Internet 上銷售數位音樂。消費者將可直接將音樂下載至PC，而無需購買CD或錄音帶。該公司為執行上述計畫已與多家高科技廠商合作，包括IBM、Liquid Audio與Microsoft。BMG隸屬於Bertelsmann公司。 另外，Sony Music也將於下週一宣佈該公司計畫於本月底開 始提供數位音樂下載。消費者將可在手提裝置上聆聽下載來的數位音樂。此項數位音樂下載將是市場上首項具有防止盜錄功能的產品。網路音樂市場在過去幾年已顯現市場潛力，主要拜MP3規格之賜。 1 : 音樂 (7) 2 : 數位音樂 (5) 3 : 下載 (4) 4 : 計畫 (4) 5 : BMG (3) 6 : Music (2) 7 : Sony Music (2) 8 : Entertainment (2) 9 : BMG Entertainment (2)

18 關聯詞分析 先前的作法 本文的作法 「共現性的單位」為「文件」 兩個詞彙在文件中距離越大，關係密切的可能性越低
需要分析的詞對個數多，許多詞對的關聯分析徒勞無功 計算量：M2n，M:所有詞彙個數, n :所有文件個數 例：n=10,000, M=10,000 (M=1000), 計算量：1012 (1010) 本文的作法 「共現性的單位」縮小到「段落」或「句子」 需要分析的詞對個數少 計算量：K2Sn，K:文件關鍵詞數, S:文件句子數, n:同上 例：n=10,000, K=30, S=20, 計算量：6x106

19 關聯詞擷取效率比較 Chen ’95 ’96 的方法： 本文的方法：
4714 文件, 8 MB, 費時9.2小時取出 1,708,551 個關聯詞對 限制每個詞的關聯詞數最多100 個，共刪除了 60% 的詞對 2GB文件，費時 24.5 CPU小時，產生4,000,000個關聯詞對 本文的方法： 336,067 新聞文件, 323 MB 費時約 5.5 小時，擷取出11,490,822 個關鍵詞 全部關聯詞數: 248,613, 平均每個詞有9個關聯詞

20 關聯詞應用範例（1/2）

21 關聯詞應用範例（2/2）

22 關聯詞排序 關聯詞可按三種方式排序 關聯詞提示的順序不同，使用者感覺的關聯度不同 強度： 詞頻： 時間： 即關聯詞共現性的強度
按關聯詞出現的文件篇數（df）排序，df 越高者，排在越前面 時間： 按關聯詞出現在最近文件的次序排序 目的：讓最近才出現的關聯詞不必累積到足夠大的強度，即可排序在前面 如：「李登輝」的關聯詞中，出現「康乃爾」，因為李登輝最近又重訪康乃爾 對具有時間事件的文件集可能很重要 關聯詞提示的順序不同，使用者感覺的關聯度不同

23 關聯詞排序 查詢詞「古蹟」的關聯詞，依「詞頻」,「時間」,「強度」排序

24 關聯詞成效評估 目的 以兩種方式評估： 評估方式： 瞭解查詢詞與其提示的關聯詞之間的關聯(relatedness)情況
優點：簡單，可回溯比較 缺點：不能細微區分排序的差異 以精確率與召回率評估哪一種排序方式較好 計算平均精確率的程式為 TREC及NTCIR用的 trec_eval 程式 評估方式： 邀請5位研究所同學，就30個查詢詞（每人6個），從系統提示出來的前50個關聯詞中，判斷是否跟查詢詞相關

25 關聯詞成效評估 結果： 結論： 比較： 排序 詞頻 時間 強度 關聯比例 48% 59% 69%
排序 詞頻 時間 強度 關聯比例 48% 59% 69% 平均精確率 「詞頻」最差，因為高頻詞，代表的主題較範圍較大，以致於跟任何查詢詞的關係都不大 結論： 依「強度」排序的效果最好 比較： (Sanderson & Croft SIGIR99) 關聯比例：67 %

26 結論 共現索引典（關聯詞庫）的優點 共現索引典（關聯詞庫）的缺點 快速呈現館藏文獻內容，具備主題摘要效果 提供館藏內容的有效瀏覽
即時反應館藏文件索引、查詢用詞，降低「字彙不匹配」問題 共現索引典（關聯詞庫）的缺點 館藏文獻沒記載、或統計不足的關聯詞無法擷取 如：「紅樓夢」與「石頭記」 關聯屬性沒有標示

27 未來方向 進一步提升關聯程度（目前只用到文獻詞彙的「共現性」） 辨識詞彙關聯的屬性 「查詢文件的共現性」： 文獻主題集中化
使用者不同的查詢詞所點選的相同文件，可視為「共現性」的另一種來源，依此做出不同查詢詞的關聯 文獻主題集中化 新聞：67%；基因文件資料庫，也許會更高 結合人工判斷與領域知識 人工索引典：準確度高，召回率低、建構速度慢、成本高 自動化索引典：成本低、召回率高、即時反應館藏文件用詞，準確率低 兩種方法恰可互補不足、相輔相成 辨識詞彙關聯的屬性 提供更準確、有用的查詢 例：查詢與「手機」相關的「廠商」