臺灣博碩士論文加值系統

我們在本篇論文中，將探討網頁使用者習性探勘中，資料前置處理的一些實務上碰到的問題以及解決的方法。
由於在網頁使用者習性探勘的過程中，若未先做好網頁結構分析，則不能確實完成資料前置處理的工作，進而嚴重影響到模式發掘的正確性。
因此，在本論文中，我們應用隨機過程時間派翠網路(Stochastic Timed Petri Nets, STPN)的可到達行為特性(reachability)以及網頁架構經過分析後產生的資料結構，來協助資料前置處理過程中的網頁內容範圍辨識以及路徑填補。

Data preprocessing is an important procedure in web usage mining. In this paper, we will discuss some major questions in data preprocessing, and then provide some methods to help to solve these problems.
In a web usage mining process, if we do not complete the web structure analysis at first, then we cannot truly complete data preprocessing, as well seriously affects the accuracy in pattern discovery.
Therefore, in the present paper, we utilize Stochastic Timed Petri Nets (STPN) and its reachability behavior characteristic, as well as the constructed web structure which produces after the web structure analysis, to help web content scope recognization and path completion procedure.

第一章 緒論 ………………………………………………………1
1.1 研究背景與動機………………………………………………1
1.2 相關研究………………………………………………………3
1.3 研究目標………………………………………………………4

第二章 背景知識 …………………………………………………5
2.1 派翠網路結構分析與其可到達行為特性……………………5
2.2 隨機過程時間派翠網路定義…………………………………7
2.3 使用STPN建構網頁結構模型…………………………………10

第三章 利用STPN協助網頁內容範圍辯識 ………………………18
3.1 網頁內容範圍辯識流程 ……………………………………19
3.2 案例一：使用紀錄無缺漏，上下網頁內容範圍無交集……26
3.3 案例二：使用紀錄部份缺漏，上下網頁內容範圍無交集…31
3.4 案例三：使用紀錄無缺漏，上下網頁內容範圍有交集……33
3.5 案例四：使用紀錄部份缺漏，上下網頁內容範圍有交集…36

第四章 利用STPN可到達行為特性協助路徑填補 ………………39
4.1 路徑填補流程…………………………………………………40
4.2 案例五：網頁內容範圍彼此互通……………………………44
4.3 案例六：Dead-End網頁內容範圍間的路徑填補……………48

第五章 結論與未來研究方向 ……………………………………54

參考文獻 ……………… …………………………………………56

附錄一 尚未經過前置處理的網頁使用者日誌…………………59
附錄二 網頁內容範圍辨識程式碼列表…………………………60
附錄三 使用MATLAB C函式庫計算STPN狀態方程式 …………70
附錄四 網頁範圍辨識程式執行結果……………………………72

[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]Federico Michele Facca and Pier Luca Lanzi “Recent Development in Web Usage Mining”, Lecture Notes in Computer Science 2727, pp.140-150, 2003.
[3]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.
[4]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.
[5]Robert Cooley, Pang-Ning Tan, Jaideep Srivastava, ”Discovery of Interesting Usage Patterns from Web Data”, Lecture Notes in Computer Science, 2000.
[6]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.
[7]Myra Spiliopoulou, Carsten Pohle, Lukas C. Faulstich, “Improving the effectiveness of a web site with web usage mining”, WEBKDD, 1999.
[8]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.
[9] Johnson P. Thomas, Mathews Thomas, and George Ghinew, “Modeling of Web Services Flow”, IEEE International Conference on E-Commerce(CEC’03), June, 2003.
[10]Rachid Hamadi and Boualem Benatallah, “A Petri Net-based Model for Web Service Composition”, In Preceedings of the Fourteenth Australasian database conference on Database technologies, 2003, p.191-200, February 01, 2003, Adelaide, Australia.
[11]Lisa Wells S. Christensen, Lars M. Kristensen, and Kjeld H. Mortensen, “Simulation Based Performance Analysis of Web Servers”, In Proceedings of 9th International Workshop on Petri Nets and Proformance Models, PNPM’01 Aachen, Sept. 11-14, pp 9-68, 2001
[12]P. David Scotts, Richard Furuma, “Petri-net-based hypertext: document structure with browsing semantics”, ACM Transactions on Information Systems, Volume 7, Issue 1, pp.3-29, January 1989.
[13]W. Reisig, “Correctness Proofs of Distributed Algorithms”, Lecture Notes in Computer Science, Vol. 938 : Theory and Practice in Distributed Systems, pp. 164-177, 1995.
[14]Tadao Murata, “Petri Nets: Properties, Analysis and Applications”, Proceedings of the IEEE, Vol. 77, No. 4, 1989.
[15]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.
[16]R. Krap, and R. Miller, “Parallel Program Schemata”, RC-2053, IBM T. J. Watson Research Center, Yorktown Heights, New York, April 1968, 54 Pages, also Journal of Computer and System Science, Vol. 3, No. 4, May 1969, page 167-195：preliminary draft, IEEE Conference Record of the 1967 Eighth Automata Symposium on Switching and Automata Theory, New York： IEEE, pages. 55-61, October 1967.
[17]S. R. Kosaraju, “decidability of reachability in vector addition systems”, om Proc. 14th Annual ACM Symp. On Theory of Computing, San Francisco, pages. 267-281, May 1982.
[18]Ernst, W. Mayr, “An algorithm for the general Petri net reachability Problem”, SIAM, J. Comput. Vol. 13, No.3, pages. 441-460, August 1984.
[19]R. J. Lipton, “The reachability problem is exponential-space-hard”, Rep. 62, Dept. Computer Science, Yale Univ., New Haven, CT, 1976
[20]陳伯榮、楊士央、何仁中，”應用隨機過程時間派翠網路來強化網頁使用者習性探勘”， 二○○四數位生活與網際網路科技研討會，國立成功大學 光復校區，2004.
[21]陳伯榮、楊士央、季振忠、陳清祥，”應用一般隨機過程派翠網路來協助網頁使用者習性探勘中的前置處理” ，二○○五數位生活與網際網路科技研討會，國立成功大學 光復校區，2005.