分支的计算差异度.ppt

08 網頁異動偵測 Source from TANET 2004 page 218 網頁異動偵測技術在網際網路新聞資訊擷取上之應用 陳奕明 李逸群 中央大學資管所 新聞網頁資訊擷取 資訊擷取的目的： 從各個異質來源的眾多文件中擷取資訊，轉換成統一的格式 將文字資料轉換成結構 化格式的資料 資訊擷取（information Extraction）技術分成兩類： 知識工程法： 運用人工手動的方式 特定的應用領域， 建構文法表示規則 這些規則可用來篩選出符合的語句，然後再擷取出來 缺點： 需要大量的人力投入 網頁變化快，此法並不切實際 自動訓練法：依其擷取的方式分為數類，如圖 1 所示 資訊擷取技術 自動訓練法－擷取程式(Extractor) 擷取程式(Extractor) ： 一組擷取路徑，加上應用這些路徑來進行擷取動作的程式碼，如圖 2 所示。 擷取程式(Extractor)的運作方式 運作方式： 擷取程式依照擷取路徑的指示，從網頁中尋找欲擷取的資訊並將資訊存入資料庫中 擷 取路徑是以 Html 網頁標籤結構為基礎的一個網頁位置表現方法 圖 2 的擷取路徑: 代表Html裡 的Body內之第一個Table中第三個tr裡的第 二個td 注意： 擷取路徑是以人工透過人機介面程式設定出來 擷取程式(Extractor) －需因應網頁改變 異動偵測(Change detection) 異動偵測(Change detection)技術 用來比 對網頁前後改變不同之處為何 應用的領域： 連續性查詢(Continual query) 資料倉儲的節省網頁空間技 術 連續性查詢(Continual query) 連續性查詢的目的： 做資料的更新監測(Update monitor) 更新監測： 主動地將資料更新的情形通知使用者 無須使用者透過手動方式不斷地檢查資料是否有更新 例如： 使 用者希望系統能夠在 Microsoft 的股價在一星期之內如果上漲了 10%的時候通知使用者 可以用下面程式來進行連續性查詢 連續性查詢(Continual query) －範例 連續性查詢概念 Pu 和 Liu 所提出 針對結構化的資料，也就是一般資料庫中的格式化資料 Web CQ 計劃 針對半結構化的網頁資料來進行連續性查詢的工作 需要一套能夠偵測網頁前後有何不同之處的技術，來作為判斷網頁的異動是否已達到使用者所設定的條件 Web CQ 使用下列模組來達到異動偵測 Object Extraction模組：用來辨認資訊在網頁中的位置 Differential Generation 模組：判斷這些內容有哪些地方改變 資料倉儲節省網頁空間的技術 資料倉儲： 需要紀綠同一網頁或資料庫在不同時間點的資料，才能對資料做進一步的分析和處 理 如果將每個時間點所有的網頁都儲存，在儲存空間和搜尋效率上都會造成浪費 使用了一套技術，可以只儲存目前的網頁和過去到現在的改變（稱為 delta），減少 儲存量，如圖 5 所示。 資料倉儲節省網頁儲存空間的運作方式 資料倉儲領域的異動偵測演算法 節省網頁空間的技術： 須先有一套方 法 處理如何找出目前網頁和過去網頁不同之處的問題 這便是異動偵測技術在資料倉儲應用的地 方 異動偵測演算法種類： Xyleme 系統： 使用一套 diff algorithm 的演算法 最大特 色： 不計算相似或差異度，而以子樹(subtree)做 為比較的單位 從網頁結構中最末端的節點，由下 往上進行配對。 異動偵測演算法種類－ CDA Change Detection Algorithm (CDA) 楊百翰大學的資料倉儲領域的異動偵測演算法 方法： 將目前和過去 的網頁依照其 Html 網頁標籤結構，轉換成分支(Branch)的型式 將每個分支加以比較 比較的方法： 給予權重，再計算分枝之間不同的節點有多少，將所有的差異加總，就是所謂的差異度 每個分支都用這種兩兩成對，計算差異度，得到表格 表格的意義： 每個舊網頁的分支最可能是對應到新網頁的哪一 個分支，差異度最小的就是最有可能的分支 CDIES 異動偵測資訊擷取系統 (Change Detection Information Extraction System, CDIES) CDIES目的： 進行資訊擷取時，依網頁改版自動更新擷取路徑 資訊擷取的動作不因網頁改版而中斷 CDIES 系統架構圖 CDIES 運作流程說明 第一 步驟： 設定樣本網頁(sample web page)的擷取路徑 透過 Extractor Guider 針對某個網站設定擷取路徑 使用者操作介面所提供的工具設定擷取範圍 系統將擷取範圍所對應