由於網際網路迅速的發展與上網人口不斷的增加，網路上的商機潛力無窮。特別是隨著電子商務之蓬勃發展，一個成功的網站必須要能夠瞭解並符合使用者的真正需求，才得以在激烈的競爭中生存，然而在網路的匿名使用習慣下，這並不是一件容易的事。因此，只能透過觀察到的使用者瀏覽行為，推測出其背後可能隱含的訊息，作為建構或改善網站之依據。根據上述之網路模式，本論文進行快取策略之分析與研究，透過建立有效的快取置換策略，可以加快瀏覽之速度與減少等待網頁傳輸之時間。
本篇論文之主要目的就是要利用隱藏馬可夫模型(Hidden Markov Models, HMMs)的統計機率特性，進行網路上快取策略之分析與研究。透過快取策略之隱藏馬可夫模型的建立，可以得出觀察輸出機率與狀態轉移機率矩陣。且根據觀察到使用者瀏覽網頁之特性，本研究可以找出最能表達這些網頁的相關網頁集合，做為代理伺服器中，快取進行置換網頁物件時的置放策略。最後，基於參數初始值的不準確性，可以透過相關之演算法進行模型參數之重估計與訓練，得到最佳之模型參數。設計出具有預測性且效能高的快取置放策略。

Owing to the fast development of Internet and increasing population surfing on the World Wide Web, there are more noticeable research activities worthy to investigate. Especially in the realm of E-Commerce, researchers get closely involved in the studies associated with its topics. As far as the web business is concerned, the critical problem is the browsing speed and time that the user must wait for his request response. The goal of this paper is to design an effective caching policy for web site management, a policy being used to increase cache hits and hopefully take off the load from the web server. Consequently, we can provide a better and timely service to the customers. Also in this paper, we introduce a novel approach of caching policy using Hidden Markov Models (HMMs) that is a statistical technique. According to the users’ browsing patterns from our observation, we can generate corresponding observable symbol probability and state transition probability. At the end, we will specify how to use HMMs in the aforementioned caching policy.

誌謝 i
摘要 ii
Abstract iii
目 錄 iv
表目錄 vi
圖目錄 vii
1. 緒 論 1
1. 1 動機與目的 1
1. 2 相關研究 3
1. 2. 1 隱藏馬可夫模型(Hidden Markov Model) 3
1. 2. 2 網路瀏覽行為分析 3
1. 2. 3 代理伺服器 (Proxy Server) 6
1. 2. 4 置換策略 (Replacement Policy) 9
1.2.4.1 基礎置換策略 10
1.2.4.2 複合置換策略 12
1. 3 論文架構 13
2. 隱藏馬可夫模型 14
2. 1 馬可夫模型的基本理論 14
2. 2 隱藏馬可夫模型的理論 15
2. 3 典型問題的處理方法 17
3. 問題及方法描述 27
3. 1 問題描述 27
3. 2 方法描述 27
3. 2. 1 置換機制 27
3. 2. 2 置換策略 31
4. 使用隱藏馬可夫模型與快取策略之制訂 34
4. 1 建立快取策略的隱藏馬可夫模型 34
4. 2 參數估計 39
5. 結論與未來展望 43
參考文獻及書目 45

[1] 蔡芳升，「以隱藏馬可夫模型模擬衛星通訊通道傳播特性」，國立臺北科技大學，碩士論文，1999。
[2] 李彥緯，「隱藏馬可夫模型之參數估計與模型選擇」，國立中央大學，碩士論文，1998。
[3] 許毅嘉，「關連法則應用於代理伺服器上之快取置換機制」，國立中興大學，碩士論文，2001。
[4] Christopher, D. M. and H. Schutze, Foundations of Statistical Natural Language Processing, Massachusetts London: The MIT Press Cambridge, 1999.
[5] Baum, L. E. and T. Petrie, “Statistical inference for probabilistic functions of finite state Markov chains”, Annals of the Institute of Statistical Mathematics, 37, pp.1554-1563, 1966.
[6] Berry, J. A. and Gordon, Linoff, Data Mining Techniques for Marketing , Sales and Customer Support, New York: John Wiley and Sons, 1997.
[7] Churchill, G. A., “Stochastic models for heterogeneous DNA sequences”, Bull. Math. Biol., 51, pp.79-94, 1989.
[8] Elliott, R. J., L. Aggoun and J. B. Moore, Hidden Markov Models: Estimation and control, New York: Springer, 1995.
[9] Korgh, A., M. Brown, I. S. Mian, k. Sjolander and D. Haussler, “Hidden Markov models in computational biology: applications to protein modeling”, J. Mol. Biol., 235, pp.1501-1513, 1994.
[10] Rabiner, L. R., “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”, Proceedings of the IEEE, Vol.77, No.22, pp.257-286, 1989.
[11] Rabiner, L. R. and B. H. Juang, “An Introduction to Hidden Markov Model,” IEEE ASSP Magazine, vol.3, no.1, pp.4-16, 1986.
[12] Aas, K., L. Eikvil and R. B. Huseby, “Applications of hidden Markov chains in image analysis”, The Journal of Pattern Recognition Society, 32, pp.703-713, 1999.
[13] Rizzo, L. and L. Vicisano, “Replacement Policies for a Proxy Cache,” IEEE/ACM Transactions on Networking, Vol.8, No.2, pp.158-170, 2000.
[14] Cooley, R., et al. “Web Mining: Information and Pattern Discovery on the World Wide Web”, Proceedings of the IEEE International Conference on Tools with Artificial Intelligence, November 1997.
[15] Agrawal, R., et al. “Mining Association Rules between Sets of Items in Large Database.” Proc. ACM SIGMOD, pp. 207-216, May 1993.
[16] Squid Proxy Server, http://squid.nlanr.net/