臺灣博碩士論文加值系統

網頁使用習性探勘的研究，藉由分析使用者瀏覽記錄（Web Usage Log）及相關數據資料，可以提供客戶的行為模式分析或網頁架構調整等應用。本論文說明如何分析網站的網頁靜態架構，建立隨機時間派翠網路（STPN）模型，利用其可到達行為特性，來協助使用者辨識（User Identification）、區段辨識（Session Identification）等分析作業。
關於網頁使用習性探勘的方法研究，一般都是分析使用者瀏覽記錄，但因忽略了網頁架構的分析，而影響模式發掘的正確性。而網頁架構是以超連結( Hyper-Link ) 的方式組成，一個複雜的網頁架構內容，並無法以簡單的樹結構 ( Tree ) 或其他圖形資料結構來描述。本研究說明如何分析網頁內容架構，以隨機時間過程派翠網路作為網頁架構的學理模型，於分析網頁內容的過程中，建立隨機過程時間派翠網路。

The research on web usage mining provides the applications, such as behavior scheme analysis and web structure adjustment by analyzing the Web Usage Log and related data. This paper describes how to parse the static structure of a web, establish the Stochastic Timed Petri Nets model and apply its accessible-behavior feature to assist the web usage mining procedures like User Identification, Session Identification, Usage Pattern Discovery, etc.

目錄
表目錄　　　　　　　　　　　　　　　　　iv
圖目錄　　　　　　　　　　　　　　　　　v
網頁架構圖　　　　　　　　　　　　　　　vii
1.　　緒論　　　　　　　　　　　　　　　1
1.1.　　研究背景　　　　　　　　　　　　1
1.2.　　研究動機　　　　　　　　　　　　1
1.3.　　研究目的　　　　　　　　　　　　1
1.4.　　論文架構　　　　　　　　　　　　2
2.　　背景知識　　　　　　　　　　　　　3
2.1.　　網頁連結　　　　　　　　　　　　3
2.1.1.　　Anchor頁面連結　　　　　　　　3
2.1.2.　　Frameset頁框集　　　　　　　　5
2.1.3.　　Frame 頁框連結　　　　　　　　7
2.1.4.　　Inline Frame內嵌式頁框連結　　11
2.1.5.　　Form表單連結　　　　　　　　　13
2.2. 　網頁架構圖　　　　　　　　　　　14
2.3. 　隨機時間過程時間派翠網路STPN　　16
2.3.1.　　隨機過程時間派翠網路的定義　　16
2.3.2.　　STPN的運作規則　　　　　　　　18
3.　　研究方法　　　　　　　　　　　　　21
3.1.　　網頁連結分析　　　　　　　　　　22
3.1.1.　　網頁架構圖與STPN對照　　　　　22
3.2.　　HTML語法與STPN對照　　　　　　　22
3.2.1.　　頁面連結轉換　　　　　　　　　22
3.2.2.　　頁面轉換為頁框集　　　　　　　23
3.2.3.　　頁框集轉換為頁面　　　　　　　24
3.2.4.　　頁框集間的轉換　　　　　　　　25
3.2.5.　　頁面轉換為內嵌頁框連結　　　　28
3.2.6.　　表單連結轉換　　　　　　　　　28
3.2.7.　　網頁內容展開分析　　　　　　　29
3.3.　　讀取網頁內容及儲存資料　　　　　31
3.3.1.　　讀取網頁內容　　　　　　　　　31
3.3.2.　　儲存網頁內容資料　　　　　　　32
3.3.3.　　site_spider 演算法　　　　　　34
3.4.　　建立STPN關連矩陣　　　　　　　　36
3.4.1.　　關連矩陣值的計算　　　　　　　36
3.4.2.　　build_place_tran演算法　　　　36
4.　　實作與分析　　　　　　　　　　　　39
4.1.　　資料名稱定義　　　　　　　　　　39
4.1.1.　　資料型別定義　　　　　　　　　45
4.1.2.　　系統全域變數　　　　　　　　　47
4.2.　　程式清單　　　　　　　　　　　　47
4.2.1.　　系統流程圖　　　　　　　　　　48
4.2.2.　　演算法 site_spider　　　　　　53
4.2.3.　　演算法 read_web_page　　　　　54
4.2.4.　　演算法 build_place_tran 　　　56
4.2.5.　　演算法 navigate_page　　　　　57
4.2.6.　　演算法 navigate_frame 　　　　58
4.2.7.　　演算法 build_web_struct 　　　60
4.3.　　資料庫設計　　　　　　　　　　　62
4.3.1.　　Table Schema　　　　　　　　　62
4.4.　　實例說明 -簡單網頁　　　　　　　65
4.5.　　實例複雜網頁　　　　　　　　　　68
4.5.1.　　複雜網頁的範例資料　　　　　　74
5.　　結論與未來研究方向　　　　　　　　77
參考文獻　　　　　　　　　　　　　　　　78

表目錄
表2-1 複雜網頁內容表 　　　　　　　　　　16
表3-1 HTML-STPN網頁連結轉換　　　　　　　23
表3-2 HTML-STPN頁面轉換為頁框集　　　　　24
表3-3 HTML-STPN 頁框集轉換為頁面 　　　　25
表3-4 HTML-STPN 頁框集轉換為頁框集 　　　26
表3-5 HTML-STPN 頁框集轉換為頁框集(2)　　27
表3-6 HTML-STPN 網頁連結轉換為內嵌頁框 　28
表3-7 HTML-STPN 表單連結轉換 　　　　　　29
表3-8 網頁內容讀取方式比較表 　　　　　　32
表3-9 HTML連結屬性名稱 　　　　　　　　　33
表3-10 HTML連結屬性清單　　　　　　　　　34
表4-1 簡單網頁的派翠網路系統狀態值 　　　67
表4-2 簡單網頁的位置轉換表 　　　　　　　68
表4-3 複雜網頁內容表 　　　　　　　　　　68
表4-4 複雜網頁的派翠網路系統狀態值 　　　72
表4-5 複雜網頁的位置轉換表　　　　　 　　72
表4-6 網頁內容範圍資料表（複雜網頁） 　　73
表4-7 網頁內容範圍展開（複雜網頁） 　　　73

圖目錄
圖2-1　簡單網頁架構圖(DIRECTED GRAPH)　　15
圖2-2　複雜網頁架構圖　　　　　　　　　　16
圖2-3　STPN PLACE的表示圖　　　　　　　　17
圖2-4　STPN TRANSITION的表示圖 　　　　　17
圖2-5　STPN PLACE-TRANSITION表示圖 　　　18
圖3-1　COOLEY的網頁探勘處理程序圖　　　　21
圖3-2　HTML頁面連結轉換　　　　　　　　　22
圖3-3　HTML頁面轉換為頁框集　　　　　　　23
圖3-4　HTML頁框集轉換為頁面　　　　　　　24
圖3-5　HTML頁框集轉換　　　　　　　　　　25
圖3-6　HTML頁框集轉換 (2)　　　　　　　　26
圖3-7　STPN PLACE ALIAS　　　　　　　　　27
圖3-8　HTML頁面轉換為內嵌頁框　　　　　　28
圖3-9　HTML表單連結轉換　　　　　　　　　29
圖3-10 視窗名稱與網頁內容辨識　　　　　　30
圖3-11 無限深度的網頁內容範圍　　　　　　31
圖3-12 SITE SPIDER 流程圖　　　　　　　　35
圖3-13 建立STPN關連矩陣的流程圖　　　　　37
圖4-1　UML物件關連圖 　　　　　　　　　　45
圖4-2　系統方塊圖　　　　　　　　　　　　48
圖4-3　流程圖 SITE_SPIDER　　　　　　　　48
圖4-4　流程圖 READ_WEB_PAGE　　　　　　　49
圖4-5　流程圖 PARSING_HTML 　　　　　　　49
圖4-6　流程圖 INSERT_LINK　　　　　　　　50
圖4-7　流程圖 BUILD_PLACE_TRAN　 　　　　50
圖4-8　流程圖 BUILD_WEB_STRUCT 　　　　　51
圖4-9　流程圖 NAVIGATE_PAGE　　　　　　　51
圖4-10 流程圖 NAVIGATE_FRAME 　　　　　　52
圖4-11 資料庫關連圖　　　　　　　　　　　62
圖4-12 簡單網頁架構圖(DIRECTED GRAPH)　　65
圖4-13 簡單網頁架構圖(STPN)　　　　　　　66
圖4-14 複雜網頁架構圖 (PAGEVIEW) 　　　　69
圖4-15 複雜網頁架構圖(STPN)　　　　　　　70

網頁架構圖
網頁架構圖 1 　　　　　　　　　　　　　　6
網頁架構圖 2 　　　　　　　　　　　　　　6
網頁架構圖 3 　　　　　　　　　　　　　　7
網頁架構圖 4 　　　　　　　　　　　　　　8
網頁架構圖 5 　　　　　　　　　　　　　　9
網頁架構圖 6 　　　　　　　　　　　　　　9
網頁架構圖 7 　　　　　　　　　　　　　　9
網頁架構圖 8 　　　　　　　　　　　　　　10
網頁架構圖 9 　　　　　　　　　　　　　　10
網頁架構圖 10　　　　　　　　　　　　　　11
網頁架構圖 11　　　　　　　　　　　　　　12
網頁架構圖 12　　　　　　　　　　　　　　12
網頁架構圖 13　　　　　　　　　　　　　　13
網頁架構圖 14　　　　　　　　　　　　　　14
網頁架構圖 15　　　　　　　　　　　　　　14

[1] Jaideep Srivastava, Robert Cooley, Mukund Deshpande, and Pan-Ning Tan, “Web Usage Mining: Discovery and Applications of Usage Patterns from Web Data”, SIGKDD Explorations, Vol.1, Issue 2, pp12-23, Jan. 2000.
[2] Configuration File of W3C http, 1995 http://www.w3c.org/Daemon/User/Config/.
[3] A. Buchner, M. Mulvenna, “Discovering Internet Marketing Intelligence through Online Analytical Web Usage Mining”, SIGMOD Record, Vol.27, No.4, pp.54-61, Dec.1998.
[4] Robert Cooley, Pang-Ning Tan, Jaideep Srivastava, ”Discovery of Interesting Usage Patterns from Web Data”, Lecture Notes in Computer Science, 2000.
[5] Peter Pirolli, James Pitkow, Ramana Rao , “Silk from a Sow’s Ear:Extracting Usable Structures from the Web”, Conference on Human Factors in Computing Systems, CHI-96, 1996.
[6] Myra Spiliopoulou, Carsten Pohle, Lukas C. Faulstich, “Improving the effectiveness of a web site with web usage mining”, WEBKDD, 1999.
[7] Jeffrey Heer, Ed H. Chi, “Identification of Web User Traffic Composition using Multi-Modal Clustering and Information “, In Proceedings of the 1st SIAM International Conference on Data Mining Workshop on Web Mining, pp.51-58, 2001.
[8] W3C 1999 HTML 4.01 SPEC http://www.w3.org
[9] Robert Cooley “The Use of Web Structure and Content to Identify Subjectively Interesting Web Usage Patterns”, ACM Transactions on Internet Technoloey, Vol.3, No.2, ppP.93-116, May 2003.
[10] W. Reisig, “Correctness Proofs of Distributed Algorithms,” Lecture Notes in Computer Science, Vol. 938：Theory and Practice in Distributed Systems, pp.164-177, 1995.
[11] Tadao Murata, “Petri Nets: Properties, Analysis and Applications,” Proceedingsof the IEEE, Vol. 77, No. 4, 1989.
[12] M. Ajmone Marsan, “Stochastic Petri Nets: An Elementary Introduction,” Lecture Notes in Computer Science, Vol. 424：Advances in Petri Nets 1989, pp. 1-29, 1990.
[13] S. R. Kosaraju, “Decidability of reachability in vector addition systems,” in Proc. 14th Annual ACM Symp.on Theory of Computing, San Francisco, pages. 267-281,May 1982.
[14] Ernst W. Mayr, “An algorithm for the general Petri net reachability Problem,” SIAM, J. Comput. Vol. 13, No. 3, pages. 441-460, August 1984.
[15] Site Spider / Web Robot http://www.robotstxt.org/wc/faq.html
[16] Sun Micro Java Developer Kit http://java.sun.com
[17] MySQL Database http://www.mysql.com
[18] HTML Parser http://sourceforge.net/htmlparser