一種多策略學習算法在web信息提取中的應用

一種多策略學習算法在web信息提取中的應用

與普通文本信息不同，web信息具有動態(tài)、慢程、無結(jié)構(gòu)等特點。因此，提取web信息通常采用機器學習方法，如j.r.quila提出的foil和ciravenna提出的pioccio。對于web信息的存儲方法，將機械學習、統(tǒng)計學習和相關(guān)學習分為三種類型。機械學習和統(tǒng)計學習適用于web頁的信息提取，相關(guān)學習適用于提取web頁之間的鏈接。這種獨特的學習方法在web信息的實現(xiàn)上有一定的局限性。在此基礎上，我們提出了一種將多種機會主義學習方法結(jié)合起來的多策略學習算法。這三種代表性的機械學習方法相結(jié)合，使不同的方法相互滲透，相互互動，提高web信息提取的精度，超過傳統(tǒng)的單一機械學習方法所達到的水平。1多策略學習1.1初始聯(lián)系集的定義針對Web信息的分布特征,即WWW可以被視作是一個以網(wǎng)頁為節(jié)點、網(wǎng)頁間超鏈接為邊的有向圖,多策略學習算法使用了相關(guān)學習的方法來描述Web的圖結(jié)構(gòu),使用特征選取的機械學習和統(tǒng)計學習來描述圖結(jié)構(gòu)中的節(jié)點和邊.因此,在學習之前定義以下背景聯(lián)系集作為初始規(guī)則.a.has-word(Page):這個聯(lián)系集合指出在網(wǎng)頁Page中出現(xiàn)了單詞word.一個特定的聯(lián)系只用于一個特定的詞(如has-teacher和has-woman等).b.link-to(Hyperlink,Page,Page):這個聯(lián)系集合代表了數(shù)據(jù)集合中網(wǎng)頁間的超鏈接.對于一個給定的超鏈接,第一個參數(shù)定義了超鏈接的標識,第二個參數(shù)定義了該超鏈接所在的網(wǎng)頁,第三個參數(shù)定義了該超鏈接所指向的網(wǎng)頁.c.has-anchor-word(Hyperlink):這個聯(lián)系集合指出在每一個超鏈接的標記文本(如下劃線)中所找到的單詞word.d.not():表示對以上各個聯(lián)系集合的取反.1.2新聞特性的生成多策略學習算法先采用統(tǒng)計學習與機械學習推導出能夠表述訓練集合中大多數(shù)網(wǎng)頁特征的候選語句片斷,然后將其應用于背景聯(lián)系集合之上得出可接受的語句片斷,最后運用相關(guān)學習來完成一條完整Web信息提取規(guī)則的推導.算法的具體描述如下.步驟1初始化一條尾部為空的語句L(v1,v2,…,vk).步驟2當語句L仍覆蓋反面實例且不太復雜時,a.調(diào)用語句片斷生成算法得到新的候選語句片斷Sj(vi);b.根據(jù)背景聯(lián)系集合選擇語句片斷Sj(vi)添加到語句L的尾部;c.生成一個新的訓練集合T′,使得T′與當前L中的變量對應起來,對于T中的每一個實例t和語句片段Sj(vi)中的新變量vi,假設新實例tvi是連接t和變量vi所得并且tvi滿足Sj(vi),那么將tvi加入T′,其正反屬性與t的正反屬性一致;d.將T′代替T;e.對于每一條語句片斷Sj(vi),如果Sj(vi)被L選中,那么將其作為背景聯(lián)系保留.步驟3通過去掉無用的語句片段來修改規(guī)則定義.本算法的關(guān)鍵是在步驟2中用到的語句片斷生成算法,它在相關(guān)學習的基礎上結(jié)合統(tǒng)計學習思想,生成的語句片斷Sj(vi)是一條一元Boolean類型的斷言,用來描述語句L中的變量vi.它是通過在問題域中的常量特征集合上運用統(tǒng)計學習來推演得出的.1.3web信息提取假設問題域中的每個常量都屬于一個類型,每個類型對應一個或多個網(wǎng)頁集合且每一個給定類型的常量又對應該類型的網(wǎng)頁集合中唯一一張網(wǎng)頁,那么算法的具體描述如下:步驟1輸入尚未完全生成的語句(或規(guī)則)L(v1,v2,…,vk)和各種類型的Web頁集合;步驟2對于語句L中的每一個變量vi:對于與vi的類型相關(guān)的每一個網(wǎng)頁集合Pj,a.C1={集合Pj中表示與變量vi所綁定的常量的正面實例},b.C2={集合Pj中表示與變量vi所綁定的常量的反面實例},c.根據(jù)目標類型的公共信息來為集合C1∪C2中的每一個詞語賦一個權(quán)值,d.n=|C1∪C2|×e(其中e為有效規(guī)模參數(shù),用來控制n的有效值),e.D={權(quán)值較高的前n個詞語},f.假設D={w1,w2,…,wn},那么在特征集合D上運用貝葉斯統(tǒng)計方法,即argmaxP(vi|w1,w2,…,wn),學習得出語句片斷Sj(vi).由于Web信息提取規(guī)則需要總結(jié)的是訓練集合中大多數(shù)網(wǎng)頁的共同特征,因此在構(gòu)造特征詞語集合D時不必將訓練集合中出現(xiàn)的所有詞語作為貝葉斯的考慮對象,而是如本步驟2中c,d和e所描述的那樣先為每個詞語賦權(quán)值并按權(quán)值排序后,取前n個詞語來構(gòu)成特征集合.2實驗結(jié)果與分析MUC(MessageUnderstandingConference)會議為信息檢索和信息提取領域內(nèi)的算法性能測試制定了一系列的評估參數(shù).設總共需要提取的信息數(shù)目為N,提取正確的信息數(shù)目為Ncorrect,提取錯誤的信息數(shù)目為Nincorrect,那么信息查全率Re和提取精確度pr如下:Re=Ncorrect/N;pr=Ncorrect/(Ncorrect+Nincorrect).通常查全率和精確度需要一起考慮.例如,在網(wǎng)頁數(shù)目較少的情況下機械學習算法得出的提取精確度較高,使得它看起來似乎是較強的提取方法,然而較低的查全率表明機械學習的高精確度只是在網(wǎng)頁集合較小的情況下才得到的.因此為了使評估結(jié)果更全面、更具說服力,在比較多個提取算法的性能時通常是將精確度pr和查全率Re結(jié)合成一個綜合性的數(shù)據(jù)F,定義為如下形式:F=(β2+1.0)prRe/(β2pr+Re)?式中參數(shù)β決定了查全率與精確度的比值.實驗數(shù)據(jù)來源于網(wǎng)上收集的大約5000張包含藥品信息的醫(yī)藥廣告網(wǎng)頁,將結(jié)合前的三種機器學習算法和結(jié)合后的多策略學習算法分別應用于這個網(wǎng)頁集合之上,對集合中每張網(wǎng)頁上的藥品信息按照藥品名稱、批準文號、功能主治分別提取出來,并依據(jù)前面提到的評估策略對實驗結(jié)果進行評估,得出所提取的藥品信息的查全率Re和精確度pr并計算出F值.由于本實驗的重點評估對象是查全率Re和精確度pr共同構(gòu)成的綜合數(shù)據(jù)F,因此本實驗中假設Re和pr的比值相同,即β=1.具體實驗結(jié)果如表1所示.實驗結(jié)果表明:多策略學習算法對于每一類藥品信息提取結(jié)果的F值都明顯高于前三種學習算法,而且在保持信息提取精確度pr相對穩(wěn)定且有一定上升的情況下使得信息的查全率Re也大大增加,因此多策略學習算法性能優(yōu)于前三種單一的機器學習算法,將其應用于Web信息的提取也更加精確、有效.將機