臺灣博碩士論文加值系統

雖然分析網站使用者瀏覽行為對於網站經營者有其重要性及必要性，不過實務上由於網站的建置初期往往不會考慮到是否未來有分析使用者瀏覽行為的需求，所以要在既有網站上建立一個分析系統其實是困難重重，以分析網誌為例，要如何確認網誌上面的哪些記錄是來自於同一使用者的行為就是一個非常大的挑戰，本論文提出一種方式利用ISAPI 過濾器配合cookie的技術，在實務上同時兼顧可行性與準確性來辨別個別的網站使用者，而不需要更動已開發的系統與程式碼。

　　過去在關聯性法則運用在網路探勘的相關研究大多著重於找出不同網頁彼此的關聯性藉以產生具意義的規則，本論文則是利用關聯性法則分析的結果，透過合併關聯性緊密的資料項目集同時排除內部資料關係鬆散的資料項目集，藉此產生內部資料關聯性高的資料群，分析的過程中，也同時將關聯性較低的資料排除於資料群之外，同時確保資料品質的一致性。得到資料特性也有別於傳統以距離量測為基礎的資料分群法所產生的群資料特性。

　　透過實驗結果，可以發現本論文所得到的群資料的確能夠將使用者的瀏覽相關性高的頁面集中在同一群內，與關聯性法則超圖形分割法（Association Rule Hypergraph Partition）所得到的資料相比，本論文所得到的分群結果除了比較準確，資料品質也較佳。

Analyzing and understanding user behavior in browsing a web site is an important issue in web site developments, however, this capability is seldom an integral part of the design process when building the web site. It is a challenging task to add such capability to an existing and running web server due to the engineering consideration of modifying potentially large amount of web pages.

This thesis uses ISAPI filter to inject cookies into HTTP transaction in order to identify individual user. This method can be applied to existing system with minor modifications. The main goal of data clustering is to partition data set into clusters, so that the data in each cluster share some common trait. This thesis proposes a method to cluster data items bases on the large itemsets which come from association rule analysis, instead of some commonly known distance measure.

Empirical data are collected from an existing web server and the resulting clusters are analyzed and compared with the commonly used “Association Rule Hypergraph Partitioning”. The experiment shows the method we proposed can get more pertinent results as compare to “Association Rule Hypergraph Partitioning” and also at the same time, the method can prune infrequent data items.

中文提要 I
英文提要 II
誌謝 III
目錄 V
圖目錄 VII
表目錄 IX
第一章 緒論 1
第一節 研究背景與動機 1
第二節 研究目的 2
第二章 文獻探討 4
第一節 資料探勘 4
第二節 網頁探勘 5
第三節 關聯性法則 7
第四節 超圖形分割法 11
第五節 關聯性法則超圖形分割法 16
第六節 COOKIE 17
第三章 系統設計相關實作與方法 19
第一節 系統前置工作 19
第二節 資料清理工作 24
第三節 擷取交易階段 25
第四節 整理交易資料 27
第五節 資料分析階段 29
第六節 系統實作部分 36
第四章 實驗結果與分析 38
第五章 結論 44
參考文獻 46
附錄 實驗數據 48

圖目錄
圖 1 網際網路近年來的成長趨勢 6
圖 2 利用APRIORI演算法產生頻繁項目集的過程 10
圖 3 多階層的超圖形分割法的收縮切割與合併修正過程 12
圖 4 邊收縮的收縮過程 13
圖 5 超邊收縮的收縮過程 14
圖 6 修改的超邊收縮的收縮過程 14
圖 7 IIS 基本架構圖 21
圖 8負責植入COOKIE的ISAPI 過濾器的處理流程 22
圖 9 切割交易的示意圖 26
圖 10 交易處理過程的流程圖 28
圖 11 本論文系統實作架構圖 36
圖 12 以5分鐘閒置時間切割日誌 39
圖 13 以5分鐘閒置時間切割日誌，交易長度為3至50 39
圖 14 以60分鐘閒置時間切割日誌 40
圖 15 以60分鐘閒置時間切割日誌，交易長度為3至50 40

表目錄
表 1 APRIORI演算法 取得候選項目集 9
表 2 APRIORI演算法 產生候選項目集 9
表 3 APRIORI演算法 判斷非頻繁項目集 10
表 4 網址代碼範例 27
表 5 主程式 判斷頻繁項目集是否擴展群或留待評估 33
表 6 評估頻繁項目集信賴值是否足夠 34
表 7 將頻繁項目集做排序 34
表 8 計算頻繁項目集與既有資料群相似度 34
表 9 擴展既有資料群 35
表 10 判斷頻繁項目集需要擴展或是新增資料群 35
表 11最小支持度影響的頻繁項目集數量 41

[1]Netcraft, Web Server Survey, Dec. 2004. (news.netcraft.com/archives/2004/12/01/ December_2004_web_server_survey.html)
[2]Google doubles search index (news.com.com/Google+doubles+search+index/2110-1032 _3-5448738.html)
[3]教育部社教博識網 (wise.edu.tw)
[4]W.J. Frawley, G. Piatetsky-Shapiro and C.J. Matheus, “Knowledge Discovery in Databases: an Overview,” Knowledge Discovery in Databases, Cambridge, MA:AAAI/MIT, pp. 213-228, 1991.
[5]J. Han and M. Kamber, “Data Mining: Concepts and Techniques,” Morgan Kaufmann Publishers, CA, USA, 2001.
[6]O. Etzioni, “The World Wide Web: Quagmire or Gold Mine,” Communications of the ACM, vol. 39, pp.65-68, 1996.
[7]S. Chakrabarti, “Mining the web: Analysis of Hypertext and Semi Structured Data,” Morgan Kaufmann Publishers, CA, USA, 2002.
[8]R. Agrawal and R, Srikant, “Fast Algorithms for Mining Association Rules,” Proc. 20th Very Large Databases (VLDB) Conf., pp 487-499, 1994.
[9]G. Karpis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel Hypergraph Partitioning: Application in VLSI Domain,” IEEE Trans. VLSI Syst., vol. 7, pp. 69-79, 1999.
[10]G. Karpis and V. Kumar, “Multilevel K-way Hypergraph Partitioning,” Proc. 36th ACM/IEEE Design Automation Conf., pp. 343-348, 1999.
[11]B. W. Kernighan and S. Lin., “An Efficient Heuristic Procedure for Partitioning graphs,” The Bell System Technical Journal, vol. 49, pp. 291-307, 1970.
[12]C. M. Fiduccia and R. M. Mattheyses, “A Linear Time Heuristic for Improving Network Partitions,” Proc. 19th IEEE Design Automation Conf., pp. 175-181, 1982.
[13]E. H. Han, G. Karypis, V. Kumar, and B. Mobasher, “Clustering Based On Association Rule Hypergraphs,” SIGMOD''97 Workshop on Research Issues on Data Mining and Knowledge Discovery, 1997.
[14]Persistent Client State HTTP Cookies (wp.netscape.com/newsref/std/cookie_spec.html)
[15]HTTP State Management Mechanism (www.ietf.org/rfc/rfc2965.txt)
[16]Internet Information Services (www.microsoft.com/windowsserver2003/iis)
[17]Globally Unique Identifier (en.wikipedia.org/wiki/Globally_Unique_Identifier)
[18]World Wide Web Consortium (www.w3.org)
[19]Extended Log File Format (www.w3.org/TR/WD-logfile)
[20]B. Mobasher, R. Cooley and J. Srivastava, “Automatic Personalization Based on Web Usage Mining,” Communications of the ACM, Vol. 43, Issue 8, pp. 142-151, 2000.