臺灣博碩士論文加值系統

網頁是呈現線上龐大資料庫最主要的方式，內容包含許多資訊，除了本身想顯示的主要資料區域之外，還加上其他許多部份，例如：導覽連結、廣告、裝飾的圖文、著作權聲明…等等。每個部份都有各自分別的功能，把整個網頁分成很多獨立功能的小單元區塊，這些小單元區塊將可以應用在許多方面，例如：網路傳輸、儲存，PDA、手機上的瀏覽…等。

大多數使用者感興趣的部份，可能只有表達網頁真正內容的資料區域，其它部份雖然有助於使用者瀏覽更方便，但是卻對電腦程式來說卻非常難去處理，例如：網頁資訊的資訊檢索(Information Retrieval)、資訊擷取(Information Extraction)、分類(Classification)、分群(Clustering)，都會因為整個網頁內容不只有單一個主題目的，而造成這些研究上處理的困難。

本篇論文提出一個有效的方法，PSDSM演算法，可以將整個網頁分割成很多具有單一功能、獨立存在的小區塊，然後在這些區塊當中，找出表達網頁真正內容的資料區域；主要分成兩個方面，第一、網頁區塊化：利用網頁重複性的結構，將內容相近的部份歸為同一區塊；第二、資料區域擷取：藉由比較兩個網頁對應區塊的內容，決定哪一個區塊是資料區塊。

實驗結果顯示，在許多不同型態的網站，利用本篇論文的方法擷取出的資料區域，幾乎完美的接近使用者感興趣的真正內容；另外，將之應用於網頁資訊擷取系統 – IEPAD，以及網頁分類，結果顯示，擷取出的資料區域，對於這兩方面的研究都有不錯的幫助；最後，比較資料區域與整個網頁的資料量，對於某些網站，資料量減少的程度高達75%，對於網路傳輸將可以有不錯的助益。

Web Page is the major manner to present huge online data. A web page often contains many segments, including main actual content in this page (we called “data-rich section”), navigational bar, advertisements, copyright and privacy notices, and unnecessary images and extraneous links for decoration. Each segment has its useful function. Dividing web pages into many independent segments has many applications. For example, network caching, cell phone and PDA browsing.

Many people only interest in main content (data-rich section) of the page, other segment can benefit human browsing, but these “human-oriented” segments are difficult for computer programs to parse. Due to these segments contain not only one purpose, they can seriously harm web data mining.

We propose an PSDSM algorithm to segment web page into many single purpose、independent blocks and identify Data-rich Section. Our approach has two aspects. First, we use repeated structures of a web page to segment web page. Second, we identify Data-rich section by block comparison.

Experimental results show that data-rich section mining by our PSDSM algorithm almost match the actual content of user interesting. Furthermore, it also benefit in web informational extraction – IEPAD and web page classification. Data-rich section can effectively reduce size of whole web page thereby improving network issues.

第一章 緒論 1
1.1 問題定義 3
1.2 貢獻 4
1.3 論文架構 4
第二章 應用與動機 5
2.1 應用 5
2.2 IE系統 7
2.3 動機與研究方向 7
第三章 相關研究討論 8
3.1 利用標籤<Tag>的特性以及視覺線索切割網頁 9
3.2 網頁區塊化並比較網頁找出資料區域 10
3.3 直接由DOM Tree中擷取資料區域 12
3.3.1 單一網頁擷取 12
3.3.2 多網頁擷取 13
第四章 PSDSM演算法 18
4.1 Page Segmentation 19
4.1.1 重複性區域(Repeated Block) 20
4.1.2 只考慮重複性區域的問題 21
4.1.3 子樹結構編碼 23
4.1.4 重新尋找重複性區域 28
4.1.5 Page Segmentation整體演算法 29
4.2 Data-rich Section Mining 30
4.2.1 區塊在不同網頁的差異性 30
4.2.2 區塊大小的重要性 34
4.2.3 資料區域擷取—多筆資料比數網頁 34
4.2.4 資料區域擷取—單筆資料網頁 35
第五章 實驗結果 36
5.1 資料區域的正確性 36
5.2 應用方向 – IEPAD 43
5.3 應用方向 – 分類演算法(Classification) 44
5.4 網頁資料減少程度 47
第六章 結論與未來展望 48
參考文獻 50

[1]A. Z. Border, S. C. Glassman, and M. S. Manasse. Syntactic clustering of the web. In Proceedings of the 6th International World Wide Web Conference(WWW6), pp. 1157-1166, 1997.

[2]A. Arasu and H. Garcia-Molina. Extracting structured data from web pages. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 337-348, San Diego, California, USA, June 9-12, 2003.

[3]B. Liu, R. Grossman, and Y. Zhai. Mining data records in web pages. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD-2003), pp. 601-606, Washington, DC, USA, August 24 - 27, 2003.

[4]C.-H. Chang and S.-C. Lui. IEPAD：Information extraction based on pattern discovery. In Proceedings of the 10th International Conference on World Wide Web, pp. 681-688, Hong Kong, May 2-6, 2001.

[5]C.-H. Chang and S.-C. Kuo. OLERA：A semi-supervised approach for web data extraction with visual support. IEEE Intelligent Systems, 2003.

[6]Document Object Model(DOM) – W3C Recommendation.
http://www.w3c.org/DOM/

[7]J. Wang and F. H. Lochovsky. Data-rich section extraction from HTML pages. In Proceedings of IEEE Computer Society 2002. 3rd International Conference on Web Information Systems Engineering (WISE 2002), pp. 313-322, Singapore, December 12-14, 2002.

[8]J. Wang and F. H. Lochovsky. Data extraction and label assignment for web databases. In Proceedings of the Twelfth International World Wide Web Conference, WWW2003, pp. 187-196, Budapest, Hungary, May 20-24, 2003

[9]J. M. Kleinberg. Authoritative sources in a hyperlinked environment. In Proceeding of 9th ACM-SIAM Symposium on Discrete Algorithms, 1998 and IBM Research Report RJ 10076, May 1997. Extended version in Journal of the ACM 46(1999), pp. 604-632。

[10]L. Ramaswamy, A. lyengar, L. Liu, and F. Douglis. Automatic detection of fragments in dynamically generated web pages. In Proceedings of the Thirteenth International World Wide Web Conference, WWW2004, New York, USA, May 17-22, 2004.

[11]L. Yi, B. Liu, and X. Li. Eliminating noisy information in web pages for data mining. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD-2003), pp. 296-305, Washington, DC, USA, August 24 - 27, 2003.

[12]S.-H. Lin and J.-M. Ho. Discovering informative content blocks from web documents. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 588-593, Edmonton Alberta, Canada, July 23-26, 2002.

[13]S. Yu, D. Cai, J.-R. Wen, and W.-Y. Ma. Improving pseudo-relevance feedback in web information retrieval using web page segmentation. In Proceedings of the Twelfth International World Wide Web Conference, WWW2003, pp. 11-18, Budapest, Hungary, May 20-24, 2003.

[14]S. Gupta, G. Kaiser, D. Neistadt, and P. Grimm. DOM-based content extraction of HTML documents. In Proceedings of the Twelfth International World Wide Web Conference, WWW2003, pp. 207-214, Budapest, Hungary, May 20-24, 2003.

[15]T. Munzner, F. Guimbretiere, S. Tasiran, L. Zhang, and Y. Zhou. TreeJuxtaposer：Scalable tree comparison using Focus+Context with guaranteed visibility. In Proceeding of ACM SIGGRAPH 2003. pp. 453-462, July 2003.

[16]V. Crescenzi, G. Mecca, and P. Merialdo. ROADRUNNER：Towards automatic data extraction from large web sites. In Proceedings of 27th International Conference on Very Large Data Bases, pp. 109-118, Roma, Italy, September 11-14, 2001.

[17]Y. Chen, W.-Y. Ma, and H.-J. Zhang. Detecting web pages structure for adpative viewing on small form factor devices. In Proceedings of the Twelfth International World Wide Web Conference, WWW2003, pp. 225-266, Budapest, Hungary, May 20-24, 2003.

[18]Z. Bar-Yossef and S. Rajagopalan. Template detection via data mining and its applications. In Proceedings of the Eleventh International World Wide Web Conference, WWW2002, pp. 580-591, Honolulu, Hawaii, USA, May 7-11, 2002.