國立政治大學 資訊科學研究所 知識系統實驗室 研究生： 鄭雍瑋 指導教授： 劉吉軒 博士 中華民國九十五年六月三十日

Presentation on theme: "國立政治大學 資訊科學研究所 知識系統實驗室 研究生： 鄭雍瑋 指導教授： 劉吉軒 博士 中華民國九十五年六月三十日"— Presentation transcript:

1 國立政治大學 資訊科學研究所 知識系統實驗室 研究生： 鄭雍瑋 指導教授： 劉吉軒 博士 中華民國九十五年六月三十日
中文資訊擷取結果之錯誤偵測 Error Detection on Chinese Information Extraction Results 國立政治大學 資訊科學研究所 知識系統實驗室 研究生： 鄭雍瑋 指導教授： 劉吉軒 博士 中華民國九十五年六月三十日 各位口試委員、教授和同學午安 我叫鄭雍瑋，感謝各位參與我的口試

2 報告大綱 研究背景與目標 相關研究 錯誤偵測方法 實驗結果與分析 相關技術之比較分析 結論與未來方向

3 研究背景 資訊擷取 (Information Extraction) 技術提供收集大量資訊與進一步的資訊加值處理。
企業或組織單位也開始善加利用這些龐大的資料，來進行商業決策或研究用途。 而資料的正確性、完整性和一致性正是影響決策品質以及各種行動的執行成果。(Redman,1996) 資料清理技術，可做為改善品質的工作，進行處理錯誤、不一致的資料以及遺漏值等問題。 (Rahm,2000) 眾所皆知，隨著資訊科技的進展，電子文件不斷地增加

4 研究目標 最新的資訊擷取技術所擷取出的資訊，仍然還是含有錯誤資料。若以人力方式進行錯誤偵測及更正，這將是耗費大量人力及時間的工作。 研究目標
發展較通用的錯誤偵測方法，不需定義領域知識。 發展一套針對中文資料偵測機制。 改善資料品質，以及提昇資訊擷取的效用。

5 相關研究：資訊擷取 資訊擷取的定義 資訊擷取的方法 (Applet and Iseral, 1997 )
針對特定領域的資料轉換成相對於原文件核心資訊的技術。(Jim and Wendy,1996 ) 資訊擷取的方法 (Applet and Iseral, 1997 ) Knowledge Engineering Approach Automatically Trainable System 擷取規則由人工建立 自動建立擷取規則 建立規則的人必須對領域 有一定程度的瞭解 從標註完成的訓練文件 來學習擷取規則 需要大量的人工介入 與使用者互動來建立擷取規則 Knowledge Engineering Approach 效果會比較好

6 相關研究：資料品質 資料品質的定義 資料品質的構面 (Ballou et al.,1987)
資料品質的最佳定義為適用性(fitness for use) (Tayi and Ballou,1998) 資料品質的構面 (Ballou et al.,1987) 正確性 即時性 完整性 一致性 因此，最近幾年大多數的學者都認同資料品質的定義為資料對資料消費者適用的程度，本研究亦採用此觀念作為本研究對資料品質的定義。 正確性（Accuracy）：當紀錄（record）的值與實際的值相同時即稱為正確性。 即時性（Timeliness）：紀錄的內容並非過時的即稱為即時性。 完整性（Completeness）：所有的值都儲存在一個確定數量的紀錄中即稱為完整性。 一致性（Consistency）：在所有的個案中，同一個資料所呈現的值都是相同的。

7 相關研究：資料清理 資料清理的定義 資料清理方法
是一種針對資料集合中進行識別、移除錯誤與不一致情況的技術，進而改善資料品質的問題 (Rahm,2000) 資料清理方法 屬性遺失值 (Missing Value) 雜訊資料 (Noisy Data) 資料完整性 資料一致性

8 相關研究：資料清理(續) 異常偵測技術 (Distance-based Outlier Detection Technique) 演算法 (Knorr et al.,1998) 假設資料庫有 p 個欄位屬性值， i、 j 分別為資料庫中任意兩筆值組。則兩筆值組距離公式如下： f 欄位為文字或二元型態資料時：當 X i f = X j f 則 f 欄位為數值型態資料時：

9 相關研究：資料清理(續) 唯一性偵測 (Uniqueness Detection) 技術。(李念秋,2002)
自動偵測出目標欄位之值組是否為唯一性。若此欄位為唯一性的話，則欄位內有重複值組則屬於錯誤資料，反之亦然。 學者共提出七個欄位屬性特徵。從訓練資料中擷取出這七個屬性特徵後，再透過C4.5歸納演算法訓練出決策樹，便可透過此決策樹判定該欄位是否為唯一性。

10 相關研究：分類分析法 ID3 決策樹歸納法 C4.5決策樹歸納法 支持向量機 (Support Vector Machine)
以資訊獲利(Information Gain)為根據，選擇最佳的屬性當成決策樹的節點。 可能並不具決策價值、無法處理連續性數值屬性分類的問題。 C4.5決策樹歸納法 獲利比 (Gain Ratio) 、連續性數值分割方法。 支持向量機 (Support Vector Machine) 統計、向量。 但是以資訊獲利為選擇分類屬性的準則偏向選擇屬性質較多的屬性。倘若資料集合依據屬性C 的可能值進行分類，而每個屬性 C可能值的分支僅存在單一筆資料時，則該屬性C 將具有最大的資訊獲利；但在實際決策上，屬性C 並不具決策價值。為了改進資訊獲利的缺失，Quinlan 提出資訊獲利比率(Gain-Ratio Measure)的方法作為選擇適當決策屬性的根據。

11 研究方法：需求分析 資訊擷取的異常資料 遺失值 (Missing values)：資訊擷取技術若無法去識別目標文件中相關的屬性資料，此屬性值在資料庫中將會被填入空值。 遺失個體 (Missing entities)：資訊擷取技術若無法從目標文件中去辨認出主題個體，會造成該主題個體的資料被忽略。 重複值組 (Duplicates)：描述同一主題實體的多筆資料，稱為重複值組。重複值組的發生通常並不是資訊擷取的錯誤，而是由於在文件中會重複描述同一主題實體。 不合格值組 (Invalid values)：資訊擷取對文件進行萃取屬性值時發生錯誤，造成此屬性值在語義上是異常、不合格的值組。 在這四種資料異常情況中，Duplicates較易被關鍵屬性資訊偵測出來。Missing values若要被偵測，得依靠綱目正確性限制，如果已知某一屬性為必填欄位，就容易指出Missing values問題。否則若沒有任何已知資訊存在，勢必很難判斷此屬性值的缺少是否為Missing values。同樣的道理，Missing entities也不容易被偵測得知。 因此，我們把資料偵測的目標擺在Invalid values。給定由資訊擷取成果所彙整的資料庫，對於每一筆資料中的每一屬性值，我們將透過語義及語法規則，去分析、偵測出Invalid values，甚至可移除異常資料與更正為正確資料。這些技術將能提升資訊擷取之加值服務品質。

12 研究方法：方法架構圖 訓練 資料庫 目標 字串圖形結構 偵測方法 字串特徵值 分類正確與 錯誤值組

13 字串圖形結構方法架構圖 訓練 資料庫 目標 偵測錯誤資料規則模型 資料推論器 分類正確與 錯誤值組 建構字串圖形 結構器

14 建構字串圖形結構器 節點(Node)：一個字元 (Character) 代表
邊 (Edge)：代表兩個字有關聯關係，也就是字詞在文句中前後的關係。 字串：ABC A B C

15 建構字串圖形結構器：建構演算法 Step1. 將訓練資料庫中第 i 筆字串內容取出。
Step2. 將 Step1 所取出的字串，根據其字元建出各節點，並且包含 root 與 end 節點。若字元與原有的字串圖形結構中節點重複，則不需再次建構。 Step3. 根據字串內容，將每個字元間的關聯建立出有方向性的連接關係。若字元間的關聯與原有的字串圖形結構中連接重複，則不需再次建構。 Step4. 取出訓練資料庫中的下一筆字串，即 i = i +1。重回Step1處理，直到處理完訓練資料庫為止。

16 建構字串圖形結構器：範例 字串圖形結構訓練資料庫： 偵測錯誤資料規則模型 ： A C D A D E B C F 訓練 資料庫 root A
end 偵測錯誤資料規則模型 ：

17 建構字串圖形結構器：特性 呈現訓練資料中所有出現的字元及關聯。 圖形結構內節點之鄰點多寡反映字元關係變化度。
若某節點的右鄰點數量較多時，則代表該字元是常見的前置詞 若某節點的左鄰點數量較多時，則是較常見的後置詞。 鄰點數越多也說明了該文件的文字關係變化較大，鄰點數越少則反映了文件內容較為單純。

18 資料推論器 目標資料的字元及關聯完全出現在字串圖形結構。 目標資料的字元及關聯不完全出現在字串圖形結構。 推論該資料為正確的資訊結果值
圖形結構內節點之鄰點多寡反映字元關係變化度。 M 1 2 3 9 錯誤：M0 右鄰點較多的規則模型 若設定右鄰點數門檻值：5 正確：M0

19 資料推論器(續) 字串資料 String 之節點可用 表示， i = {0,1, 2, …,N,N+1} 定義一： 為合格關聯
為 root 節點 為 end 節點 各個關聯 節點之左鄰點數為 節點之右鄰點數為 定義一： 為合格關聯 出現在規則模型上。 沒有出現在規則模型上， 或 超過門檻值

20 資料推論器(續) 字串是具有位置與順序的特性 定義二： 為合格節點 出現在規則模型上。 定義三： 為合格節點
Ex.市政府會計室、會計室市政府。 增加相對應位置比對方式。 定義二： 為合格節點 出現在規則模型上。 沒有出現在規則模型上， 或 超過門檻值 定義三： 為合格節點 出現在相對應位置規則模型上。 沒有出現在相對應位置規則模型上， 或 超過門檻值

21 資料推論器(續) 越高，代表性越高 節點重要度 定義四： 為 所指向的節點之被指向節點數，用 表示，反映出與 同位置節點數。
該節點位置的字元內容較易掌握，反映出該位置的字元較具代表性。以下圖為例，A、Z節點較為重要。 1 2 3 5 A 4 Z 定義四： 為 所指向的節點之被指向節點數，用 表示，反映出與 同位置節點數。 該類型節點之代表性程度： 越高，代表性越高

22 資料推論器(續) 目標資料符合訓練字串圖形結構之節點群組，以 , 表示之。字串群組之代表性程度為
目標資料符合訓練字串圖形結構之節點群組，以 , 表示之。字串群組之代表性程度為 推論公式： (m為合格節點數、n為合格關聯數、 權重) 數值越高代表此字串正確的機率越高

23 (Classification Analysis)
字串特徵值方法架構圖 訓練 資料庫 擷取字串 特徵器 字串特徵 轉換器 目標 C4.5演算法 偵測錯誤資料規則模型 資料推論器 分類正確與錯誤值組 訓練資料 特徵轉換數值 目標資料 特徵值 分類分析 (Classification Analysis) SVM演算法

24 擷取字串特徵器 字串特徵值是描述字串外表特徵，而不考慮其文字意義。共定義六個字串特徵值。
String Cardinality (以下簡稱Sc)：字串長度。 String Prefix (以下簡稱Sp)：字串前k個字元，k是可設定的參數。 String Suffix (以下簡稱Ss)：字串後k個字元，k是可設定的參數。 String Entity (以下簡稱Se)：完整字串內容。 String Numeral (以下簡稱Sn)：字串內容是否包含數字，輸出結果為 true/false。 String Format (以下簡稱Sf)：字串內容所屬的資料型態。

25 = (Sc(vi), Sp(vi), Ss(vi), Se(vi), Sn(vi), Sf(vi))
擷取字串特徵器(續) 六個特徵值種類用 SF 作為代表 針對資料庫中每個 vi 值，可用下列公式表達： 處理範例： = (Sc(vi), Sp(vi), Ss(vi), Se(vi), Sn(vi), Sf(vi))

26 字串特徵轉換器 第一種轉換方式：先計算每一特徵值出現的百分比，再根據其百分比分佈來進行適當的數值分配。
特徵數值 第二種轉換方式：先計算每一特徵值出現的百分比，再將百分比由小到大排列。接著根據排序過後的百分比分佈，累加其百分比值。

27 字串特徵轉換器(續) 各長度特徵分布比率 長度特徵比率與特徵轉換數值： 累加長度特徵比率與特徵轉換數值：

28 C4.5演算法 訓練資料範例： 規則模型：

29 SVM演算法 支持向量機，將目標資料分為正確與錯誤兩類別。
本研究所使用的SVM軟體及參數設定係參考國立台灣大學 LIBSVM 網站相關文獻。

30 實驗資料 政府人事任免公報，從民國三十七年起，周期性出刊，記載政府各部門人事異動情形。
型態辨識技術擷取資訊，已經處理到目前為止共20年份的資料，共萃取出超過10萬筆人事異動資料，並皆彙整而成資料庫。(翁家緯,2003) ‧‧‧ 任命鄒擅銘為國史館臺灣文獻館簡任第十職等組長。 任命吳文慎為交通部臺灣區國道新建工程局人事室簡任第十職等主任，林渭鵬為經濟部水利處人事室簡任第十職等主任。 任命鍾萬梅為行政院客家委員會簡任第十二職等處長，黃崇烈為簡任第十一職等副處長。 行政院國家科學委員會科學工業園區管理科長曹常通另有任用，應予免職。

31 實驗評估方法 以字串特徵作為錯誤偵測的基礎，每一個字串特徵值皆可視為簡單的二元分類器，因此我們可以建立二元分類器指出合格與異常資料。
ROC 圖形，用來觀察該分類器 TP-rate 與 FP-rate 的損益平衡情形。

32 實驗設計 字串圖形結構方法實驗架構 訓練及目標資料年份數 合併年份 單一年份 字串圖形方法參數 關聯門檻值 字元門檻值 訓練資料筆數
圖形結構節點比對方式 對應位置比對方式 原始比對方式

33 節點比對方式之實驗結果 對應位置比對的偵測效果優於原始比對。 「職等」、「總統」與「年份」欄位，可完美偵測。
Ex.「單位」欄位錯誤資料為「為外交部」，兩種比對方式所計算出的 Score 數值會有明顯差異。 姓名欄位實驗結果 單位欄位實驗結果

34 訓練資料筆數之實驗結果 「職等」、「總統」與「年份」欄位的資料內容非常單純，因此實驗結果不隨資料訓練筆數而改變，即可完美偵測。
「單位」與「職稱」欄位隨資料訓練筆數增加而增進偵測效果。 「姓名」則是效果差距不大 姓名欄位實驗結果 單位欄位實驗結果

35 目標資料年份數之實驗結果 合併年份優於單一年份 合併年份所提供的資料較為全面，促使學習出的圖形結構較為完整。 姓名欄位實驗結果
單位欄位實驗結果

36 字串圖形方法參數 考慮字元門檻值及關聯門檻值。
「姓名」、「單位」與「職稱」欄位透過門檻值的設定，可達到提昇偵測效果的目的。「職等」、「總統」與「年份」欄位不考慮門檻值時，就能訓練出完整的圖形結構。 姓名欄位實驗結果 單位欄位實驗結果

37 字串圖形結構之實驗小結 當欄位的字串內容變化度較大，效果較為不理想，反之亦然。
「職等」、「總統」與「年份」欄位，可以完美分類正確與錯誤資料；「姓名」、「單位」與「職稱」等欄位則是有誤判情況發生。 錯誤原因： 正確資料被偵測為錯誤資料：訓練資料未包含全部正確資料值 錯誤資料被偵測為正確資料：錯誤資料可能與正確資料的字元或關聯非常相似。

38 實驗設計(續) 字串特徵值方法實驗架構 累加特徵比率 特徵比率 字串特徵轉換器 訓練及目標資料年份數 合併年份 單一年份 字串特徵方法參數
正反案例比1:1 w 參數 訓練資料筆數 正反案例比N:1

39 字串特徵轉換器之實驗結果 「累加特徵比率」整體效果會比「特徵比率」方法好。根據兩種轉換方法的差異，前者將特徵值所劃分群組數目較多，提供了機器分類法學習出更加嚴謹的規則。

40 訓練及目標資料年份數之實驗結果 合併年份優於單一年份 合併年份所提供的資料較為全面，促使學習出的規則模型較為完整。

41 字串特徵方法參數之實驗結果 改變 w 參數 SVM C4.5
另外，以「姓名」欄位來說，w參數較大時表現較好，這是由於該欄位的字串值數量很多，造成每筆資料的字串特徵數值皆差異頗大，因此w參數提高，造成分群數目也變多，使得資料規則模型能夠做出更精確的分類。而「單位」欄位的資料變化程度遠比「姓名」欄位小，但是其Distinct Value 仍然為數不少，可以從實驗數據發現w參數除了100以外，隨著w參數遞減，TP-rate與FP-rate也同步遞減。以整體ROC操作點位置來看，距離差距不大。 SVM C4.5

42 訓練資料筆數之實驗結果 正反案例比 1:1 正反案例比 N:1 同個欄位的 ROC 操作點位置皆相距不遠。 「姓名」欄位效果差距不大。
「單位」、「職稱」欄位正確資料越高，表現越好。 「職等」、「總統」與「年份」變化程度較小的欄位，ROC 操作 點位置則是維持不變。

43 字串特徵值之實驗小結 C4.5做為機器學習分類法優於SVM。 字串特徵值概念隱含了領域知識。
單位資料規則模型 String Cardinality (Sc) String Suffix (Ss)

44 字串特徵值之實驗小結(續) 錯誤原因： 正確資料被偵測為錯誤資料：訓練資料未包含全部正確資料值或是正確字串特徵未被掌握。
錯誤資料被偵測為正確資料：該錯誤資料可能與正確資料的特徵非常相似。

45 總體實驗結果 字串圖形結構與字串特徵值，兩種方法在「職等」、「總統」與「年份」欄位時，皆能完美分類資料。
偵測「姓名」、「單位」與「職稱」欄位時，以字串特徵值表現較為傑出。 「姓名」欄位TP-rate約85%、FP-rate約27% (Distinct value: 99368) 「單位」欄位TP-rate約87%、FP-rate約4% (Distinct value: 1832) 「職稱」欄位TP-rate約91%、FP-rate約3%。(Distinct value: 213) 方法限制：錯誤資料仍屬於該欄位的合法值組 ，會造成本偵測方法誤判為正確資料的情況。

46 相關技術之比較分析 四種資料清理技術 (Maletic,2000) 實做 k-means
Statistical Outlier Detection Clustering Pattern-based detection Association Rules 實做 k-means 距離公式為 Edit Distance 應屬同一群的資料，距離差距仍大 ex. 「教育部」和「交通部高速鐵路工程局」 證明本研究方法較適合處理字串資料

47 系統應用 立法院新聞知識管理系統 機讀編目格式 (MAching Readable Cataloguing format, MARC)
|b平裝|d NT$350 tw|b d k y0chiy09 e chi|c eng cw a z 000ay 達文西密碼|f 丹.布朗(Dan Brown)著|g尤傳莉譯 初版 臺北市|c時報文化|d 2004[民93] 面|c圖|d23公分 藍小說| v 84 | |a藍小說|v 84 | |a The Da Vince code |d |e0761-I 布朗|c (Brown, Dan)|4 著 尤|b傳莉|4譯 Brown|bDan cw|b CCU|c |g CCR CCU|f c41

48 結論 本論文提出字串圖結構和字串特徵值錯誤偵測方法。 有效偵測出錯誤資訊擷取成果。 能針對中文資料進行處理。
確保高品質的資訊擷取成果產出，促成資訊擷取技術更廣泛的實際應用。

49 未來研究方向 全自動偵測技術 提昇偵測準確率 增加系統對語言瞭解的能力，判斷該欄位資料內容屬性進而自動調整合適的參數。
同時採用兩種偵測方式去處理 加強圖形結構比對演算法 增加字串特徵值種類

50 問題與討論 謝謝