12/11 論文報告─FivaTech

這一次閱讀的論文是以前Lab中博班學長與老師所發表的，論文題目是FivaTech：Page-Level Web Data Extraction from Template Pages。目前Lab中的研究還有使用到以本篇論文技術為基礎的系統，但是仍然有些問題需要解決。如果這個系統能夠維護好並擴展改進的話，對未來網頁資料擷取的許多應用相信將很有幫助。

由於往相關領域閱讀論文，因此理所當然的要先了解自己Lab有在使用的系統。另一方面，也正好給大家介紹本篇論文所採用的技術。我第一次看這篇論文時，看的是只有6頁的版本，幾乎很多地方都不能了解。在看了以前學長在相關領域方面的一些研究論文之後，加上老師給了我另一個34頁比較詳盡的版本，多看幾次才總算比較清處的了解整篇論文在講什麼。

最早Web IE採用的是supervised的方式，必須依靠人工標註才能產生擷取資料的規則。後來Dynamic Web的研究往Template-based的推論方向發展，產生了一些unsupervised方式的論文。FivaTech就是其中之一，它可以透過多個擁有相同Template的頁面來推論出其結構，也因此把這樣的方法歸類為Page-Level。

FivaTech以多個網頁作輸入，最後產生共同的Template、Schema及個別的擷取資料。Template及Schema是以樹狀表示，與網頁的DOM Tree形成較一致的表現，其核心過程主要分成兩個較大的部份：Tree Merging以及Schema Detection。Tree Merging部份又可細分出四個小部份：Peer Node Recognition、Multiple String Alignment、Tandem Repeat Mining及Optional Merging，經過這四個步驟後會形成所謂的Pattern Tree，接著利用它來作下一階段的Schema Detection。

Peer Node Recognition主要是用來決定輸入的Tree中第1層(假設root為第0層)Node間的相似程度，相似程度大於某個門檻值以上則給定相同的代表符號(比如用英文字母a、b、c...等)，相同代表符號的node則屬於peer node。peer node辯識的準確性可以說是最為關鑑，在同一個DOM Tree中，peer node代表了資料樣式的重覆，可能是data rich區域；在不同DOM Tree中，peer node的意義可以用來推斷Page間共同的Template。不過在論文中並沒有提到門檻值應該設多少，而這個門檻值怎樣設可以產生最好的結果？是否可以適用在所有情況？是我感到比較疑問的地方。因為peer node的判斷直接就影響了後面的所有步驟，只要稍有不同，產生的結果可能就差很多。

決定出peer node後，下一步就是Peer Matrix Alignment。這個階段的工作就是把不同Tree的第1層node依序並排，然後取出每一行(同一個Tree)中兩個相同符號的node(peer node)間距離最大的值，裡面的最大值定義為span。接著對於span值大於0的符號node，盡量將其每一行的距離調整成span的值(最大可能循環長度)；剩下部份則盡量把相同的符號在每一列間對齊，node往下移動調整過程中空出的位置可以看成是missing data。要補充說明的部份是，對齊除了可以是相同符號(空出的部份不算)，也可以是不同的文字node。

在對齊步驟過後，可以得到一個Node List用來代表不同Page間的共同樣式(Pattern)。接下來就可以對此List作Pattern Mining的運算，將重覆的pattern壓縮起來。最後再根據不同的node在所有DOM Tree中的occurrence vector概念，由vector不一致(值不全為1)的node決定出哪些node是optional(不一定會有的資料)，這個過程稱為Optional Node Merging。

以上四個步驟從root往下一層層的作下去，最後將會形成一棵fixed/variant Pattern Tree。由此再將tree中的每個node分類並決定其order，則可以得出最終的Schema格式。至於Template的產生部份，先以規則決定出參考點(用來當作template間的分界)，再依此劃分出各個小範圍的Template，最後產生出與Schema相對應的一整組Template的表示法。這部份規則就不再說明，有興趣的話請參考投影片。

最後是本次報告論文的投影片：