一個以賽局理論為基礎的網頁主題區塊擷取演算法

Abstract

隨著資訊與網路科技的快速蓬勃發展，網際網路已成為目前最龐大的資料體，由於科技的進步以及使用者人數爆增，每天有數以萬計的網頁產生。而網際網路也成為使用者最大的資訊來源。資訊爆炸的現代，要在這麼龐大的資料當中找尋特定主題的相關資料，變成是一件相當重要的研究課題。 因此，本論文提出一個以賽局理論為基礎的網頁主題區塊擷取演算法(a Game-theoRy-based Algorithm for extracting theme-Block from a web page, GRAB)，能夠自動地將使用者有興趣的主題區塊自動地辨識出來，並轉換成易於儲存、檢索與分析的結構化資料，提供不同平台(e.g.手機、PDA)應用的方便性。 本論文針對提出的GRAB演算法設計一雛型系統，並設計了兩個實驗，以實際網頁資料測試驗證演算法的效能。實驗一的結果證明GRAB演算法在10種主題的HTML網頁具有70%到90%的效能，對於新聞網頁的效果特別好。實驗二從實驗一挑選效能最好的3種主題做為資料集，並與現有三種網頁區塊擷取法比較。實驗結果證明GRAB的整體效能優於三種現有方法，其中處理結構化網頁的效能雖與現有方法差不多，但對於新聞網頁的效能仍優於現有方法；在處理非結構化網頁則具有87%到95%的效能，都優於現有的三種網頁區塊擷取方法。

Because of the rapid development of Information and network technology, Internet has become the largest body of information. The progress of technology and the explosion in the number of users, so there are produced tens of thousands pages every day. Internet has become the largest source of information. In the information explosion times, searching specific topic data in such a huge data is becoming an important topic. For this reason, this paper presents a Game-theoRy-based Algorithm for extracting theme-Block from a web page(GRAB). It can automatically identify user interested topic blocks, and then converted to easy storage, retrieval and analysis of structured data for providing different platforms (eg. mobile phone, PDA) to facilitate the application. This paper provides a prototype system based on GRAB algorithm. I design two experiments, and verify the effectiveness of algorithms through the actual web page data. The first experiment results prove that GRAB algorithm in ten topics of HTML web page can achieve 70% to 90% accuracy rate, especially in news web page. The second experiment selects the best three topics from the first experiment results for data sets, and compare with three existing web blocks retrieving methods. The results prove GRAB overall performance is better than three existing methods. Although processing structured web performance is similar to existing methods, but news web performance is better than existing methods. Processing unstructured web performance is can achieve 87% to 95% accuracy rate, and all is better than three existing web blocks retrieving methods