數(shù)位文字知識探勘以中文索引典之建構(gòu)及應(yīng)用為例.ppt

數(shù)位文字知識探勘 - 以中文索引典之建構(gòu)及應(yīng)用為例,文字知識探勘簡介 索引典建構(gòu)：緣由與目的 相關(guān)之研究 關(guān)鍵詞自動擷取 關(guān)聯(lián)詞自動擷取 應(yīng)用範(fàn)例 成效評估,曾元顯 .tw 資訊中心 國立臺灣師範(fàn)大學(xué),近年研究主題演進(jìn)圖,知識探勘,知識探勘（knowledge discovery, KD） 擷取隱晦、有用、未被發(fā)掘、有潛在價值的規(guī)則、資訊或知識的一種過程 實(shí)務(wù)上，運(yùn)用資訊組織與分析等探勘技術(shù)，與使用者互動，反覆探索，發(fā)現(xiàn)訊息或規(guī)律，人工解讀結(jié)果，轉(zhuǎn)換規(guī)律訊息成資訊或知識。 資料探勘（data mining, DM） 處理結(jié)構(gòu)化（structured）資料，即資料間有共同欄位 文字探勘（text mining, TM） 處理非結(jié)構(gòu)化資料，資料常為自由文字,知識探勘步驟與技術(shù),步驟： 資料蒐集 資料清理 資料轉(zhuǎn)換 探勘技術(shù)運(yùn)用 結(jié)果呈現(xiàn)與解讀,技術(shù)： 關(guān)聯(lián)分析（association） 分類（classification） 歸類（clustering） 概略化（generation） 預(yù)測（prediction） 序列分析（sequence analysis） 特徵詞彙擷取 索引與檢索 摘要（summarization）,資訊組織與主題分析,資訊組織與主題分析的技術(shù)內(nèi)容 資訊檢索 權(quán)威控制 詞彙關(guān)聯(lián) 內(nèi)容摘要 主題歸類 文件分類 圖書館學(xué)較重視標(biāo)準(zhǔn)化的作業(yè)與架構(gòu) 資訊科技較重視自動化技術(shù)的運(yùn)用,索引典自動建構(gòu)：前言,檢索失敗的主要因素之一：字彙不匹配問題 查詢詞與索引詞不相同的情況 例:筆記型電腦與筆記本電腦,行政院長與閣揆 改進(jìn)方法：查詢擴(kuò)展、權(quán)威檔、索引典 查詢擴(kuò)展(query expansion) 加入更多與查詢主題相關(guān)的詞彙，或更改查詢詞的權(quán)重 權(quán)威檔 (authority file) 記錄及解決同義異名詞的工具 索引或檢索時，將各種同義異名詞對應(yīng)起來，視為相同的詞彙處理,索引典自動建構(gòu)：前言,索引典 (thesaurus) 除同義詞外，還有紀(jì)錄廣義詞、狹義詞、反義詞、相關(guān)詞等 列舉主題詞彙，將詞彙間的語意或主題關(guān)係標(biāo)示出來的知識庫 查詢時，可互相推薦，以擴(kuò)展或縮小查詢範(fàn)圍，或提示相關(guān)概念的不同查詢用語 例攜帶型電腦：筆記型電腦、掌上型電腦 使檢索從字串比對層次，提升到語意比對層次 人工製作索引典，準(zhǔn)確度高，但召回率低、成本大、建構(gòu)速度慢、事先選用的詞彙可能與後續(xù)或其他新進(jìn)的文件無關(guān) 一般目的索引典運(yùn)用在特定領(lǐng)域的文件檢索上，無法提升檢索效能 針對每一種文獻(xiàn)領(lǐng)域製作索引典，耗時費(fèi)力,索引典自動建構(gòu)：前言,共現(xiàn)索引典(co-occurrence thesaurus) 利用詞彙的共現(xiàn)性，自動建構(gòu)詞彙關(guān)聯(lián)（term association） 或稱關(guān)聯(lián)詞庫 成本低、建構(gòu)速度快、召回率高、與館藏文件用詞一致，但準(zhǔn)確率低 詞彙關(guān)係：主題相關(guān)，不一定語意相關(guān) 例：李登輝與康乃爾、中華電訊與ADSL,關(guān)聯(lián)檢索研究成果,曾元顯, 漸進(jìn)式關(guān)聯(lián)詞庫之建構(gòu)方法, 中華民國發(fā)明專利，專利號： I 290684 . 有效期：2007/12/01-2023/05/08 透過國科會小產(chǎn)學(xué)計畫，技術(shù)移轉(zhuǎn)國內(nèi)廠商 產(chǎn)業(yè)應(yīng)用： 誠品書店（/） 政府研究資訊系統(tǒng)GRB智慧搜尋系統(tǒng)（38萬筆）,研究方法,文獻(xiàn)探討、技術(shù)瞭解、優(yōu)缺點(diǎn)分析、適用範(fàn)圍分析 歸納重點(diǎn) 提出改進(jìn)方法 實(shí)驗(yàn)測試 成效比較 不同研究之間的比較 同一研究內(nèi)，對照組之比較 提出適用情況與應(yīng)用方向 持續(xù)評估與改進(jìn),相關(guān)研究：Salton 89,Salton 曾提出建構(gòu)共現(xiàn)索引典的架構(gòu)： 算出各個詞彙間的相似度 相似度：詞彙在各文件之間，共同出現(xiàn)的情形（或主題相似度） 重要的索引詞彙，任兩詞彙皆拿來比對相似度 計算量至少 M2，M ：所有重要詞彙的個數(shù) 依此相似度將詞彙歸類成索引典類別( thesaurus classes )（或主題類別）,Tj=(d1j, d2j, , dnj), n：所有文件的個數(shù),相關(guān)研究：Salton 89,歸類方式，主要有： Complete-link: 一開始，每個詞?。ㄔ兀?，都單獨(dú)視為一類 兩個類別之間的相似度，若超過某個門檻值，就結(jié)合並歸成同一類，如此重複歸類 兩個類別之間的相似度，定義為跨類別元素之間相似度最低者 易產(chǎn)生多數(shù)個索引典類別（thesaurus class），但每類僅有少數(shù)個詞彙 Single-link: 同上述作法，但兩個類別之間的相似度，定義為跨類別元素之間相似度最高者 易產(chǎn)生少數(shù)個類別，但每類都有大量的詞彙 透過共現(xiàn)索引典的查詢擴(kuò)展，檢索成效的召回率，通?？商嵘?10% 至 20% 小結(jié)： 歸類運(yùn)算量太大，運(yùn)用在大量文件上，耗時長久,相關(guān)研究： Chen 96,相關(guān)研究： Chen (JASIS 95),定義非對稱的詞彙相似度 詞彙 Tj 在文件 i 中的權(quán)重: 詞彙 Tj 及 Tk 在文件 i 中的權(quán)重: Cluster_weight(Tj, Tk) Cluster_weight(Tk, Tj) 若Tj =Artificial Intelligence, wj =2,相關(guān)研究： Chen (JASIS 95),從 4714 文件中 (共 8 MB), 產(chǎn)生了 1,708,551 個詞對（co-occurrence pairs ） 由於關(guān)聯(lián)詞對太多，每個詞，限制其關(guān)聯(lián)詞數(shù)最多100 個，如此刪除了 60% 的詞對，剩下 709,659 個詞對（由 7829 個不同的詞組成） 產(chǎn)生上述的詞對，在 Sun Sparc 工作站上要花 9.2 CPU 小時、磁碟空間 12.3 MB 成效評估： 6個受試者，16 個預(yù)選的詞，請每個受試者先就每個詞，聯(lián)想出相關(guān)的詞??；再從系統(tǒng)提示的關(guān)聯(lián)詞，判斷哪些是相關(guān)或不相關(guān) 兩種結(jié)果比較，召回率分別為 28.60% 與 61.89% ；精確率為 77.08% 及 24.17% 小結(jié)： 人工聯(lián)想精確率高、召回率低；機(jī)器產(chǎn)生關(guān)聯(lián)詞較多、準(zhǔn)確度較低,相關(guān)研究： Sanderson and Croft (SIGIR99),概念階層的範(fàn)例：from Sanderson and Crofts paper,相關(guān)研究： Sanderson and Croft (SIGIR99),目的：從檢出的文件中自動產(chǎn)生概念階層（concept hierarchies），便利使用者瞭解檢出文件的大致內(nèi)容 第一步：詞彙選擇（決定哪些詞彙要列在概念階層中）: 來源 1: 檢索結(jié)果的前幾篇中比對程度較佳的段落裡，找出常常一起出現(xiàn)的詞彙 來源 2: 每一篇檢出文件的最相關(guān)段落裡，取符合下列條件的詞?。?(df_in_retrieved_set / df_in_collection) = 0.1 者 平均從 TREC 的每個查詢結(jié)果的前 500 篇文件中，擷取出 2430 個詞 第二步：詞彙關(guān)聯(lián)分析: 任意兩個詞都拿來做 包含 關(guān)係（subsumption relationship）比較： P(Tj | Tk) = 1 and P(Tk | Tj) = 0.8 and P(Tk | Tj) 1, if Tj 包含 Tk 平均每個查詢擷取出 200 包含對（subsumption pairs） 由這些 包含對 產(chǎn)生 概念階層，即包含者為父節(jié)點(diǎn)，被包含者為其子節(jié)點(diǎn),相關(guān)研究： Sanderson and Croft (SIGIR99),成效評估：測試包含者與被包含者的關(guān)聯(lián)程度（relatedness） 由 8 個受試者判斷，67% 包含對被判斷為相關(guān)（interesting for further exploring） 比較：51% 詞彙對（隨意配對，而非用包含關(guān)係配對者）被判斷為相關(guān) 小結(jié)： 此方法在查詢時才進(jìn)行，查詢反應(yīng)時間會受影響 提示的詞彙只限於檢索結(jié)果的前N篇，不是一個 全域索引典（global thesaurus） 隨機(jī)配對，關(guān)聯(lián)度高，顯示詞彙選擇的重要性,關(guān)聯(lián)詞分析,先前的作法 共現(xiàn)性的單位為文件 兩個詞彙在文件中距離越大，關(guān)係密切的可能性越低 需要分析的詞對個數(shù)多，許多詞對的關(guān)聯(lián)分析徒勞無功 計算量：M2n，M:所有詞彙個數(shù), n :所有文件個數(shù) 例：n=10,000, M=10,000 (M=1000), 計算量：1012 (1010) 新的作法 共現(xiàn)性的單位縮小到段落或句子 需要分析的詞對個數(shù)少 計算量：K2Sn，K:文件關(guān)鍵詞數(shù), S:文件句子數(shù), n:同上 例：n=10,000, K=30, S=20, 計算量：6x106,關(guān)聯(lián)詞分析：新的方法：Tseng 2002,主要分二個步驟： 擷取個別文件的關(guān)鍵詞 關(guān)鍵詞的關(guān)聯(lián)分析與累積 關(guān)鍵詞擷取 關(guān)鍵詞：文件內(nèi)有意義且具代表性的詞彙 關(guān)鍵詞：呈現(xiàn)文件主題意義的最小單位 各種文獻(xiàn)自動化處理的必要步驟。 關(guān)鍵詞的認(rèn)定是主觀的判斷，不利於電腦的自動處理 重複性假設(shè)： 如果文件探討某個主題，那麼應(yīng)該會提到某些特定的字串好幾次 具有客觀性、可自動處理 假設(shè)簡單，可適用於不同領(lǐng)域,關(guān)聯(lián)詞分析：新的方法：Tseng 2002,第一步：詞彙選擇： 每篇文件先用 詞庫（長詞優(yōu)先法）斷詞 再由關(guān)鍵詞擷取演算法 擷取關(guān)鍵詞（至少出現(xiàn)2次者）（包含新詞） 以 停用詞 過濾擷取出的關(guān)鍵詞，並依詞頻（term frequency）高低排序 選 詞頻最高的 N 個詞作關(guān)聯(lián)分析 第二步：詞彙關(guān)聯(lián)分析: 每篇文件選出來的詞，以 下面公式計算兩個詞彙的 權(quán)重 wgt： where NSi denotes number of all sentence in document i and NS(Tij) denotes in document i the number of sentences in which term Tj occurs. 關(guān)聯(lián)詞 的權(quán)重超過門檻值（1.0）者，才依下面公式累積其權(quán)重 關(guān)聯(lián)詞 的最後相似度定義為： 原方法：僅單純累加每對關(guān)聯(lián)詞的權(quán)重 新方法：加入 IDF (inverse document frequency ) 及 詞彙長度,關(guān)鍵詞自動擷取方法,比較： 詞庫比對法：詞庫需持續(xù)維護(hù)更新 統(tǒng)計分析法：容易遺漏統(tǒng)計特徵不足者 文法剖析法：需詞庫、詞性標(biāo)記等資源與運(yùn)算 適合作為關(guān)鍵詞的名詞片語少於 50% Arppe 1995,關(guān)鍵詞自動擷取方法 Tseng 97, 98, 99, 2001,找出最大重複出現(xiàn)字串（maximally repeated pattern）的演算法 token : 一個中文字（character）或英文字（word） n-token: 輸入文字中，任意連續(xù)的 n tokens （與 n-gram 類似） 演算法三步驟： 步驟一 : 轉(zhuǎn)換輸入文字成 2-token 串列 步驟二 : 依合併規(guī)則重複合併 n-tokens 成 (n+1)-tokens，直到無法合併 步驟三 : 依過濾規(guī)則，過濾不合法的詞彙,依過濾規(guī)則，過濾不合法的詞彙,詞頻,關(guān)鍵詞自動擷取過程範(fàn)例,輸入文字: “BACDBCDABACD”, 假設(shè) 門檻值 = 1 步驟一 : 產(chǎn)生 L = (BA:2 AC:2 CD:3 DB:1 BC:1 CD:3 DA:1 AB:1 BA:2 AC:2 CD:3) 步驟二: token 合併 : 第一次 :合併 L 成 L1= (BAC:2 ACD:2 BAC:2 ACD:2) 丟掉: (BA:2 AC:2 CD:3 DB:1 BC:1 DA:1 AB:1 BA:2 AC:2 CD:3) 留住 : (CD:3) 第二次 : 合併 L1 成 L2 = (BACD:2 BACD:2) 丟掉 : (BAC:2 ACD:2 BAC:2 ACD:2) 留住 : (CD:3) 第三次 : 合併 L2 成 L3 = ( ) 丟掉 : ( ) 留住 : (CD:3 BACD:2) 步驟三: 無須過濾,關(guān)鍵詞自動擷取範(fàn)例 Tseng 2000：英文範(fàn)例,Web Document Clustering: A Feasibility Demonstration Users of Web search engines are often forced to sift through the long ordered list of document returned by the engines. The IR community has explored document clustering as an alternative method of organizing retrieval results, but clustering has yet to be deployed on the major search engines. The paper articulates the unique requirements of Web document clustering and reports on the first evaluation of clustering methods in this domain. A key requirement is that the methods create their clusters based on the short snippets returned by Web search engines. Surprisingly, we find that clusters based on snippets are almost as good as clusters created using the full text of Web documents. To satisfy the stringent requirements of the Web domain, we introduce an incremental, linear time (in the document collection size) algorithm called Suffix Tree Clustering (STC), which creates clusters based on phrases shared between documents. We show that STC is faster than standard clustering methods in this domain, and argue that Web document clustering via STC is both feasible and potentially beneficial.?,Terms extracted before filtering 1. clusters based on : 3 2. document clustering : 3 3. of Web : 3 4. on the : 3 5. search engines : 3 6. STC is : 2 7. Web document clustering : 2 8. Web search engines : 2 9. clustering methods in this domain : 2 10. requirements of : 2 11. returned by : 2,Terms extracted after filtering 1. clusters based : 3 2. document clustering : 3 3. Web : 3 4. 5. search engines : 3 6. STC : 2 7. Web document clustering : 2 8. Web search engines : 2 9. clustering methods in this domain : 2 10. requirements : 2 11. returned : 2,關(guān)鍵詞自動擷取範(fàn)例 Tseng 2000：中文範(fàn)例,Comparison of Three Metadata Related Standards 在本文中，我們介紹了三個跟 metadata 相關(guān)的標(biāo)準(zhǔn)，它們分別是 FGDC 的 Digital Geospatial Metadata、Dublin Core、和 URC。雖然它們各有自己的設(shè)計目標(biāo)和特質(zhì)，但都是假設(shè)其操作環(huán)境為類似網(wǎng)際網(wǎng)路的環(huán)境。FGDC 的 Digital Geospatial Metadata 是設(shè)計來專門處理地理性資料，由於它有聯(lián)邦行政命令的支持，可說是已成為美國在地理方面的資料著錄國家標(biāo)準(zhǔn)。Dublin Core 則比較像是 USMARC 的網(wǎng)路節(jié)縮版，使非專業(yè)人士也能在短時間內(nèi)熟悉和使用此格式來著錄收藏資料，但在現(xiàn)階段祇針對類似傳統(tǒng)印刷品的電子文件。由 IETE 的 URI 工作小組所負(fù)責(zé)的 URC，其原始的設(shè)計目的雖是用來連結(jié) URL 和 URN，但為因應(yīng)電子圖書館時代的要求，其內(nèi)含逐漸擴(kuò)大，雖然尚在發(fā)展中，但由於有 IETE 的支持，未來成為網(wǎng)際網(wǎng)路上通用標(biāo)準(zhǔn)的可能性極大。在此文中，我們也從幾個不同角度，分析和比較這三個 metadata 格式的異同和優(yōu)缺點(diǎn)。,Terms before filtering 1. 設(shè) 計 : 3 2. 資 料 : 3 3. 網(wǎng) 路 : 3 4. 標(biāo) 準(zhǔn) : 3 5. Dublin Core : 2 6. FGDC 的 Digital Geospatial Metadata : 2 7. IETE 的 : 2 8. 三 個 : 2 9. 文 中 : 2 10. 比 較 : 2 11. 它 們 : 2 12. 由 於 : 2 13. 地 理 : 2 14. 成 為 : 2 15. 我 們 : 2 16. 的 支 持 : 2 17. 的 設(shè) 計 目 : 2 18. 格 式 : 2 19. 著 錄 : 2 20. 電 子 : 2 21. 網(wǎng) 際 網(wǎng) 路 : 2 22. 環(huán) 境 : 2 23. 雖 然 : 2 24. 類 似 : 2,Terms after filtering 1. 設(shè) 計 : 3 (design) 2. 資 料 : 3 (data) 3. 網(wǎng) 路 : 3 (network) 4. 標(biāo) 準(zhǔn) : 3 (standard) 5. Dublin Core : 2 6. FGDC 的 Digital Geospatial Metadata : 2