基于正則表達式構建學習的網頁信息抽取方法

朱文琰 鄭肖雄

(復旦大學計算機科學技術學院智能信息處理重點實驗室 上海 200433)

基于正則表達式構建學習的網頁信息抽取方法

朱文琰 鄭肖雄

(復旦大學計算機科學技術學院智能信息處理重點實驗室 上海 200433)

正則表達式作為信息抽取領域中的一種常用方法已經被廣泛應用多年。然而構建高質量并且復雜度較高的正則表達式通常需要耗費大量人工成本，為此，提出一種基于正則表達式狀態轉換的算法來學習復雜正則表達式的構建過程。該算法需要給定輸入初始正則以及正反例樣本，初始正則表達式在經過析取分離與合并交叉兩大類正則表達式狀態轉換之后，得到候選正則表達式集合，利用F值評估候選項的信息抽取效果，通過貪心的啟發式策略選擇一個最優正則表達式作為輸出。在多種數據集上對算法進行測評。實驗表明，該算法性能與準確度均優于常規的機器學習方法。尤其在較小規模訓練集和跨數據集上依然有較好的效果。

正則表達式構建 狀態轉換 Web信息抽取

0 引 言

大部分的信息抽取任務可以通過精心構建的正則表達式來抽取相應的實體。例如郵箱地址、電話號碼、信用卡號碼和身份證號碼、基因和蛋白質名稱等。在標準的正則表達式構建過程中，以上提到的這些實體所代表的特征模式均能夠被很好地表現出來。構建這樣的正則表達式原型是非常簡單直接的，但事實上，考慮到方法的健壯性要求，通常就需要更加復雜的規則。盡管信息抽取領域已有許多機器學習的方法，包括最大熵馬爾科夫模型[1]、監督學習[2]、字符類模型[3]、半監督學習[4]、無監督學習[5]等。但是在實際的信息抽取任務中，人工構建的正則表達式依然被廣泛采用[6]。事實上，如何通過自動學習的方法來減少在構建正則表達式過程中的人工消耗是信息抽取領域的一個難題。本文提出了一個基于正則表達式學習的信息抽取方法，將標注過的正反例樣本以及一個初始的正則表達式作為輸入，通過一系列正則表達式的狀態變換得到一組備選正則集合，在多組備選集合上根據其在標注樣本上的信息抽取效果，選出最優正則表達式作為輸出。通過實驗可以證明，該方法能夠顯著減少在信息抽取初期構造復雜正則表達式的人工成本，在一些特定類型的信息抽取任務中具有較好的效果。尤其是在較小規模的訓練集以及跨數據集上有不錯的表現，能夠構造出高質量的正則表達式。

1 相關工作

信息抽取是自然語言處理研究中的重要部分，網頁信息抽取是指在半結構化的網頁內容中抽取結構化數據的過程。目前，信息抽取系統在實現上主要分為兩大類，分別是基于統計學習的方法和基于規則模式的匹配方法。兩者互有優劣，統計學習的方法具有可移植性和魯棒性，但是都需要大量訓練數據來完成對參數的設置以及對系統的優化。基于規則的匹配方法具有較高的效率和準確率。但是規則的生成需要較高的代價。所以規則的自動生成是信息抽取領域的重要問題。

第一個實現規則的機器學習方法的是 Cristal 信息抽取系統[7]。這個系統先從訓練樣本中生成規則集合，抽取方法是每一個實例提取出一個原始規則。然后循環從規則集合中選擇兩個相似度最高的規則進行合并，最后得到最小規則集。 Crystal 系統目前只能夠支持單槽的信息抽取，它的缺陷是無法確定目標字段的界限。WHISK[8]抽取系統通過將規則的約束條件不斷增加來得到最終的結果。此系統首先確定能夠能覆蓋所有樣例的規則最普通范式，然后通過訓練樣本對規則增加特征和限制進行拓展，滿足一定的錯誤率要求后停止訓練，得到最終的集合。AutoSlog 是基于模板詞典的規則構造器，它能夠自動地構造指定領域的詞典，這樣的模板也叫做概念節點。一個概念節點包含如下部分:概念位元、 語言規則以及觸發條件[9]。其中位元包含了一系列用于觸發的詞組，觸發條件對 生成的語言規則在語法上進行了一些約束。RAPIER[10]是基于邏輯的一種信息抽取系統，從訓練語料上歸納出所需要的抽取規則。RAPIER 采用的是自底向上的學習算法，從具體某一個樣本的規則歸納為 覆蓋全集的范式。RAPIER系統在執行規則生成的過程中運用了語義和句法的信息。SRV[11]是一種基于關聯的信息抽取系統，采用了自頂向下的歸納式算法進行信息抽取。該系統應用分類算法來完成抽取任務，具有相同大小的文本數據被選取為候選項，這些候選項將在后續作為分類器的輸入。候選短語在文本訓練數據上的覆蓋率是其在規則中出現的概率估計。

近年來，關于通過正負樣本來學習正則語言的方法有很多[12-15]。其中大部分的工作通常假設所學習的目標表達式比較簡單。例如在DNA定序應用的模式學習中[16]，輸入序列被看作是由序列間隙隔開的多個原子事件。每一個原子事件都可以通過一個簡短的正則表達式來表示，于是問題就簡化為簡單正則表達式的學習問題。在XML DTD 推斷中[17]，通常XML文件會使用簡單的DTD來描述文件主題內容，利用DTD就可以對XML文件信息進行提取。然而，考慮到方法的魯棒性和結果的準確性，通常需要構建更加復雜的正則表達式來獲得更有效的信息抽取。

在信息抽取領域，傳統正則學習的方法大多著眼于在相對小的字符表上進行正則表達式的學習[18]。常見的情況是在詞性標注[19]、形態分析[20]、詞典匹配[21]等文本處理過程之后產生的標注詞上進行正則表達式的學習，字符表的大小就由以上分析步驟產生的標注結果所決定。另外，之前的幾乎所有工作都將問題限制在一個特定的正則類型中[22]，禁用或限制了某些正則符號和操作的使用。

2 問題描述

對于一個信息抽取任務，需要獲取實體ε，令R0表示初始輸入的正則表達式，M(R0,D)表示將R0作用于文本D上所得到的結果。令：

Mp(R0,D)= {x∈Mp(R0,D) :x是實體ε的實例}

(1)

Mn(R0,D)= {x∈Mn(R0,D) :x不是實體ε的實例}

(2)

分別表示R0的正例和反例的匹配結果。任務目標就是輸出一個比初始輸入的R0效果更好的正則表達式。

對于一個候選正則R，及其所應用的目標文檔D，如果想要判斷R是否比R0有更好的效果，那么就必須對R所匹配的結果進行正負分類。如果R所匹配的結果是所有已有結果的子集，那么就能夠進行判斷，因此有如下假定：

假定1 對于字符集Σ上的正則表達式R0，任何其他的正則表達式R是一個更優候選者當且僅當M(R,D)?M(R0,D)。

在此假定的基礎上，仍然會得到近乎無限多的候選正則表達式，為了進一步通過學習得到一個最優正則式，需要一個在不同正則表達式之間進行轉換的方法，以及評價一個正則表達式抽取信息效果的目標函數。下面給出兩者的定義：

定義1 令R表示字符集Σ上所有的正則表達式的集合，正則表達式的轉換就是一個函數F:R→2R,?R0∈F(R),L(R0)?L(R)。L(R)表示R所匹配的結果。

舉例來說，對于正則表達式(d+-)+d+來說，可以將第二個數量符號+替換為一個特定的范圍，例如{1，2}或{3，4}，于是就得到了新的表達式(d+-){1，2}d+ ，(d+-){3，4}d+。將數量符號+替換為一個具體的范圍就是正則表達式轉換的一個特例，后面會進一步說明，現階段可以將正則的轉換看作是能夠產生一系列候選正則集合的函數。下面給出本文學習問題的搜索空間的定義：

定義2 給定一個輸入正則表達式R0和一系列的轉換T，學習問題的搜索空間為T(R0)，即將轉換T重復作用在R0上所得到的所有正則表達式的集合。

選擇使用信息檢索領域的常用指標F1-Measure來比較檢索空間中不同正則表達式抽取信息的效果，使用之前提到的Mp(R,D)和Mn(R,D)分別定義一下指標：

(3)

(4)

(5)

最終的正則表達式學習任務就可以由如下最優化問題來定義：

定義3 對于給定的輸入正則表達式R0，文檔集合D，正反例樣本集合Mp(R,D)和Mn(R,D)以及一系列正則轉換T，輸出一個最優正則表達式 ：

Rf=argmaxR∈T(R0)F(R,D)

(6)

3 正則表達式轉換

3.1 現代正則引擎

現代正則引擎主要可以分為基本不同的兩大類[18]：一種是DFA(確定型有窮自動機)，另一種是NFA(不確定型有窮自動機)。使用DFA的工具主要有egrep、awk、lex和flex。而使用NFA的工具包括.NET、PHP、Ruby、Perl、Python、GNUEmacs、ed、sec、vi、grep的多數版本，甚至還有某些版本的egrep和awk。也有一些系統采用了混合引擎，它們會根據任務的不同選擇合適的引擎，甚至對同一表達式中的不同部分采用不同的引擎，以求得功能與速度之間的平衡。NFA和DFA都發展了很多年了，產生了許多不必要的變體，以致現在的情況比較復雜。POSIX標準的出臺，就是為了規范這種現象，POSIX標準清楚地規定了引擎中應該支持的元字符和特性。

3.2 正則表達式轉換定義

下面介紹如何利用現代正則引擎的句法規則實現正則表達式的轉換，首先考慮這樣一個信息抽取任務：從一段文本中找出所有的軟件名稱，一個簡單的模式是R= ([A-Z]w*s*)+[Vv]?(d+.?)+，即為以一個或多個大些字母開頭的單詞，后面跟一個數字版本號。將R應用于實際數據中會發現，一方面R確實能夠提取出正確的結果，如Office2010,Python2.7,AdobeGoLive5,DeelexInstallerv1.0，另一方面，一些非軟件名稱的結果也會被提取到，例如Building17,Chapter3.2,ENGLISH202。針對以上出現的非軟件名稱結果，大體可以從兩個角度來改進：

1) 對于像ENGLISH202 這樣的全大寫單詞的課程代碼，可以將R的前半部分單詞的表達式改為R1= ([A-Z][a-z]*s*)+，即變為以一個大寫字母開頭的單詞，這樣就能夠過濾掉之前匹配到的錯誤結果。

2) 另一個改進的方法是利用現代正則引擎中的前向否定符”?!”來顯式地去除掉Building,Chapter,ENGLISH之類的單詞，前向否定就是除了正常的搜索匹配之外繼續查找，檢查是否出現某些特定內容以達到在正常匹配到內容的基礎上，過濾掉某種不想要的內容。舉例來說：(?!Ra)Rb返回的是匹配Rb并且不匹配Ra的內容。回到上面的例子一個改進的方法是將前半部分表達式改為 (?!Building|Chapter|ENGLISH)[A-Z]w*s*。

以上兩個角度給出了正則表達式轉換的基本原則，通過抽取出一個正則表達式的一部分并對其進行一定的修改以獲得原正則匹配結果的真子集。這樣的修改分為析取分離與合并交叉兩類。析取分離主要作用在由一系列析取項組成的子表達式上，通過分離掉一個或多個析取項從而進行正則的轉換。合并交叉則是將某一限定的子表達式與其他表達式進行合并，從而得到轉換后的表達式。具體定義如下：

定義4 令R是屬于RΣ中的一個正則表達式，且有R=Raλ(X)Rb,λ(X)表示正則集合X={R1,R2,…,Rn}上的析取R1|R2|…|Rn，對于某一Y?X，Y作用于R的析取分離轉換后的正則為DD(R,X,Y)=Raλ(Y)Rb。

定義5 令R是屬于RΣ中的一個正則表達式，且有R=RaXRb,對于某一RΣ中的Y，合并交叉轉換后的正則為II(R,X,Y)=Ra(X∩Y)Rb。

3.3 正則表達式轉換實現

下面介紹具體如何運用不同的句法規則來實現析取分離和合并交叉的正則表達式轉換，包含以下部分：

1) 字符類限制約束

字符類通常表示一系列字符析取結果的縮寫，例如元字符d表示(0|1|…|9)，w表示(a|…|z|A|…|Z|0|1…|9|_)。字符類可以用層級結構來表示，其中每一層的節點所包含的字符范圍都比他的父親節點更少。在正則中對某一字符類用其后代節點對其代替就是析取分離轉換的一種實現形式。

2) 數量符約束

數量符用來定義一段重復序列出現的次數范圍，例如x{a,b}表示的是序列x出現至少a次，至多b次。由于數量符也可以被看成是其范圍中每一項的析取，如a{1,3}相當于a|aa|aaa，所以如定義4所描述，將某一正則表達式R{m,n}替換為R{m′,n′}(m≤m′≤n′≤n)也是一種析取分離轉換的形式。需要注意的是，在進行這樣的析取分離轉換之前，需要對a+和a*這樣的通配符限制在一個實現設置好的范圍max中，轉變為a{1,max}和a{0,max}。

3) 否定詞典

對于一個給定的正則表達式，交叉合并轉換可以作用在其每一個有效子表達式上，對于一個正則表達式R=RaXRb和它的子表達式X，交叉合并轉換需要另一個表達式Y來得到轉換后的表達式Ra(X∩Y)Rb。由于在轉換后所得到的表達式會比原來的表達式有更好的效果，那么可以通過構建所有R的反例匹配，找出其中與X所對應的匹配字串，然后通過啟發式規則找出其中的一部分構成否定詞典Y′。于是利用前向否定符構造的正則表達式Ra(?!Y′)XRb就是利用交叉合并Ra(X∩Y′)Rb后的結果。

4) 否定詞典的啟發式構造策略

交叉合并轉換過程需要建立在否定詞典合理構造的基礎上，S(X)表示正則表達式R的反例匹配中對應子表達式X的所有字符串集合，理論上說，所有S(X)的子集都有可能構成一個否定詞典，這樣就會有指數級數量的轉換可能。為了減少轉換的數量，使用一種貪心的啟發式策略，對于每一個元素，如果能夠單獨提高F值，那么就將其加入否定詞典。

4 基于正則表達式學習的信息抽取算法

4.1 算法流程

算法1描述了對于定義3的正則表達式學習問題的算法流程。總體來說，該算法是一個不斷迭代的過程，通過對初始輸入的正則表達式進行不同形式的轉換，在每一輪迭代過程中，得到一組候選正則表達式的集合，并從中貪心地選擇在訓練集上具有最高F值的正則表達式R。為了避免過擬合的情況，當出現以下兩種情況中的任一種時，算法就會終止。(1) 當R在訓練集上的效果沒有提升；(2) 當R在測試集上的效果下降。

算法1 正則表達式構建學習算法

Input:

Mtrain: set of labeled matches used as training data

//訓練集數據

Mtest: set of labeled matches used as test data

//測試集數據

R0: user-provided regular expression

//用戶輸入初始正則表達式

T : set of regular expression transformation

//正則轉換集合

Output : one regular expression with highest F-measure

//輸出結果

Procedure RegexLearning(Mtrain, Mtest, R0,T)

0. Rnew= R0

1. while(true)

2. for each transformation ti∈T

//遍歷正則轉換集合

3. Candidatei= Transformation(Rnew, ti)

4. Candidates = ∪iCandidatei

5. R′= argmaxR∈CandidatesF(R,Mtrain)

//選擇最優結果

6. if (F(R′,Mtrain) <= F(Rnew,Mtrain)) return Rnew

7. if (F(R′,Mtest) < F(Rnew,Mtest)) return Rnew

8. Rnew= R′

9. end while

End procedure

4.2 復雜度分析

下面討論算法1的時間復雜度，根據之前提到的兩個算法終止條件，在算法的每一輪迭代中選出的具有最高F值得正則表達式R′都是嚴格優于Rnew的，由假定1可知，R′所得到的匹配結果是Rnew匹配結果的子集，所以R′所匹配的反例結果嚴格小于Rnew所匹配的反例結果，因此，總的迭代次數至多為|Mn(R0,Mtrain)|。

對于一個正則表達式R，令ncc(R)和nq(R)分別表示R中字符類和數量符的個數，R中子表達式的個數至多為|R|2,令MaxQ(R)表示自定義的R中單個數量符所限定的數量范圍，Fcc表示字符類層級樹中的最大分支數，令Ri表示在i輪迭代開始時的輸入正則，經過正則表達式轉換后的候選正則數量為：

NumREG(Ri,Mtrain)≤ncc(Ri)×Fcc+nq(Ri)×

MaxQ(Ri)+|Ri|2

令TRE(D)表示將正則表達式作用于文檔D上的平均時間。對于字符類替換和數量符限制的析取分離轉換時間是與候選正則數量成正比的，而對于通過構造否定詞典的交叉合并轉換，由于否定詞典的貪心式啟發式規則，所需要的時間也與子表達式以及反例匹配數量相關。總的構造候選正則表達式集合的時間為：

TCandidate(Ri,Mtrain)≤c×(ncc(Ri)×Fcc+nq(Ri)×

MaxQ(Ri)+|Ri|2×Mn(Ri,Mtrain)×TRE(Mtrain))

最后，從候選正則表達式集合中選出最優正則表達式，包括將候選集中的每一個正則作用于訓練集以及測試集上的時間：

TPick(Ri,Mtrain,Mtest)=NumREG×(TRE(Mtrain)+

TRE(Mtest))

Ti(Ri,Mtrain,Mtest)=TCandidate(Ri,Mtrain)+

TPick(Ri,Mtrain,Mtest)

Ttotal(Ri,Mtrain,Mtest)=∑Ti(Ri,Mtrain,Mtest)

≤|Mn(R0,Mtrain)|×t0

所以每一輪迭代的總時間為：

Ti(Ri,Mtrain,Mtest)=TCandidate(Ri,Mtrain)+

TPick(Ri,Mtrain,Mtest)

由于每一輪迭代的總時間是單調遞減的，所以最終算法的時間復雜度為(t0是第一輪迭代所需要的時間)：

Ttotal(Ri,Mtrain,Mtest)=∑Ti(Ri,Mtrain,Mtest)

≤|Mn(R0,Mtrain)|×t0

5 實驗分析

在本節中，將通過四種不同的信息抽取任務來評估本文中的算法在復雜正則表達式學習問題上的效果，并與常規的機器學習方法進行了比較。實驗中用到了數據集有三個，分別為從yahoofinance選取的2000多個上市公司網頁進行爬取所得內容，以及從密歇根大學網站[23]上爬取的5000個頁面數據和3000個的電子郵件內容信息。后兩者均為互聯網上的公開數據。實驗的四個信息抽取任務分別為電話號碼、課程代碼、超鏈接、公司名稱的信息抽取。實驗結果通過F值來評估，每個數據集被分為10個大小相同的子數據集，分別使用10%、30%、70%的數據作為訓練集，剩下的作為測試集。實驗結果如圖1-圖4所示。

圖1 電話號碼任務抽取效果

圖2 課程代碼任務抽取效果

圖3 超鏈接任務抽取效果

圖4 公司名稱任務抽取效果

分析實驗結果可見：

如果使用10%的數據作為訓練數據，對于公司名稱、課程代碼以及電話號碼三個信息抽取任務，本文的算法比傳統的條件隨機場方法F值會有顯著提高。

隨著訓練數據的增加，兩種方法的抽取效果均有提升，兩者之間的差別也隨之減小。在使用較大的訓練集時，本文的方法在公司名稱以及電話號碼兩個信息抽取任務上效果較好，而傳統機器學習方法則在另外兩個任務上有更優的表現。

以上實驗結果說明在有限的訓練數據上，本文的算法比傳統的機器學習算法有一定的提升。通常情況下，由于獲取標注數據通常需要花費大量的時間，所以如何能夠在有限的訓練集上獲得高質量的信息抽取效果是非常重要的。也正因為如此，理想中的情況是在一個訓練集上訓練出的抽取器能夠在其他的數據集上也有較好的效果，表1展示了兩種方法在跨數據集上的信息抽取效果。可以看出，在不同規模的數據集上，本文的算法均有較好的效果，相比于同數據集上的實驗結果，傳統的條件隨機場方法在跨數據集上的表現有顯著下降。

表1 跨數據集測試(F值)

6 結 語

在信息抽取領域，基于正則表達式的實體抽取一直是一種實際應用中廣泛使用的有效方法。本文提出了一種基于正則表達式學習的信息抽取方法，在給定輸入初始正則的前提下，通過機器學習的方法找到最優結果。介紹了正則表達式狀態轉換的概念及其實現方法，并且給出了選取最優正則表達式的算法，通過實驗驗證了該方法在一些特定類型的信息抽取任務中具有較好的效果。尤其是在較小規模的訓練集以及跨數據集上有不錯的表現。本文的方法仍有許多不足之處，例如在某些信息抽取任務中無法保持較高的準確率與召回率，可能的原因是在選擇最優正則表達式使用貪心的啟發式策略，但這也是與時間復雜度的一個權衡。

[1] McCallum A,Freitag D,Pereira F C N.Maximum entropy Markov models for information extraction and segmentation[C]//Proceedings of the Seventeenth International Conference on Machine Learning,2000:591-598.

[2] Soderland S.Learning information extraction rules for semi-structured and free text[J].Machine Learning,1999,34(1):233-272.

[3] Klein D,Smarr J,Nguyen H,et al.Named entity recognition with character-level models[C]//Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003.Association for Computational Linguistics,2003:180-183.

[4] Carlson A,Betteridge J,Wang R C,et al.Coupled semi-supervised learning for information extraction[C]//Proceedings of the Third ACM International Conference on Web Search and Data Mining.ACM,2010:101-110.

[5] Wang J,Lochovsky F H.Wrapper induction based on nested pattern discovery:HKUST-CS-27-02[R].Technical Report of Hong Kong University of Science and Technology,2002.

[6] Chiticariu L,Li Y,Reiss F R.Rule-based information extraction is dead! Long live rule-based information extraction systems![C]//Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing,2013:827-832.

[7] Sekine S.On-demand information extraction[C]//Proceedings of the COLING/ACL on Main Conference Poster Sessions.Association for Computational Linguistics,2006:731-738.

[8] Kluegl P,Toepfer M,Beck P D,et al.UIMA Ruta:rapid development of rule-based information extraction applications[J].Natural Language Engineering,2016,22(1):1-40.

[9] Fagin R,Kimelfeld B,Reiss F,et al.Spanners:a formal framework for information extraction[C]//Proceedings of the 32nd Symposium on Principles of Database Systems.ACM,2013:37-48.

[10] 鄭家恒,王興義,李飛.信息抽取模式自動生成方法的研究[J].中文信息學報,2004,18(1):48-54.

[11] Fagin R,Kimelfeld B,Reiss F,et al.Document spanners:a formal approach to information extraction[J].Journal of the ACM (JACM),2015,62(2):1-51.

[12] 楊博,蔡東風,楊華.開放式信息抽取研究進展[J].中文信息學報,2014,28(4):1-11,36.

[13] Denis F.Learning regular languages from simple positive examples[J].Machine Learning,2001,44(1):37-66.

[14] Denis F,Lemay A,Terlutte A.Learning regular languages using RFSAs[J].Theoretical Computer Science,2004,313(2):267-294.

[15] Fernau H.Algorithms for learning regular expressions[C]//16th International Conference on Algorithmic Learning Theory.Springer,2005:297-311.

[16] Garofalakis M,Gionis A,Rastogi R,et al.XTRACT:a system for extracting document type descriptors from XML documents[N].ACM SIGMOD Record,2000,29(2):165-176.

[17] Galassi U,Giordana A.Learning regular expressions from noisy sequences[C]//6th International Symposium on Abstraction,Reformulation and Approximation.Springer,2005:92-106.

[18] Bex G J,Neven F,Schwentick T,et al.Inference of concise DTDs from XML data[C]//Proceedings of the 32nd International Conference on Very Large Data Bases.VLDB Endowment,2006:115-126.

[19] Wu T,Pottenger W M.A semi-supervised active learning algorithm for information extraction from textual data:research articles[J].Journal of the American Society for Information Science and Technology,2005,56(3):258-271.

[20] Minkov E,Wang R C,Cohen W W.Extracting personal names from email:applying named entity recognition to informal text[C]//Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing.Association for Computational Linguistics,2005:443-450.

[21] Chen H,Chiang R H L,Storey V C.Business intelligence and analytics:from big data to big impact[J].MIS Quarterly,2012,36(4):1165-1188.

[22] Cohen W,McCallum A.Information extraction from the world wide web[C]//Tutorial Note at the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2003),2003.

[23] Intranet Transactional Search[OL].http://www.eecs.umich.edu/db/transactionalSearch/.

A WEBPAGE INFORMATION EXTRACTION METHOD BASED ON REGEX CONSTRUCTION LEARNING

Zhu Wenyan Zheng Xiaoxiong

(ShanghaiKeyLabofIntelligentInformationProcessing,SchoolofComputerScience,FudanUniversity,Shanghai200433,China)

As one of the main methods in the field of information extraction, the method based on regular expression has been widely used for many years. However, the construction of regular expressions is with high quality and high complexity, it is usually required to spend a lot of manual efforts. Therefore, a method based on regular expression state transition is proposed to learn the construction of complex regular expressions. The method takes in a given initial input RegEx and both positive and negative labeled samples, a collection of candidate RegEx is got after applying two main kind of regular expressions transformation on the input RegEx, based on F value assessment of the candidate RegEx on the information extraction task, the algorithm selects an optimal regular expressions as output by greedy heuristic strategy. The performance of this algorithm is evaluated on multiple datasets. Experiments show that the performance and accuracy of the proposed method outperforms those of the standard machine learning methods. And it still has a good effect on condition of small scale training set and cross domain data set.

RegEx construction State transition Web information extraction

2016-01-22。朱文琰，碩士，主研領域：金融信息處理。鄭肖雄，碩士。

TP3

A

10.3969/j.issn.1000-386x.2017.02.003