[[alternative]]使用隨機派翠網路之線上網頁推薦系統

博士[[abstract]]網頁推薦系統為網頁使用習性探勘典型的應用，而網頁推薦系統在結構上可分成離線(off-line)與線上(online)兩個元件，離線元件主要根據分析過去歷史使用者習性資料(usage profile)來建立知識，並提供給線上元件使用。由於一般網頁推薦系統大多使用離線之資料前置處理，而執行資料探勘時也沒有時間限制，故此方法並不適合即時的動態環境，因此，我們需要高效能之線上網站使用習性探勘技術來解決這些問題。 我們在本文中提出以隨機過程時間派翠網路為基礎之線上網頁推薦系統，網頁推薦處理程序可分為資料準備、模式發掘和推薦三個階段。在資料準備階段，我們利用隨機過程時間派翠網路作為分析網站網頁架構的模型，並加入衡量網站基準分析網頁結構特性來增進網頁資訊的擷取。而分析網站架構後所得到的關聯矩陣與派翠網路模型之可到達行為特性可協助進行資料前置處理中的網頁內容範圍辨識和路徑填補。在模式發掘階段，我們應用流覽圖(navigational graph)和可到達圖(reachability graph)來作為使用者習性資料的模型。我們利用資料串流探勘技術維護在滑動視窗(sliding-window)上的流覽圖，並應用關聯矩陣與派翠網路模型之可到達行為特性進行可到達圖的建立。在推薦階段，我們使用馬可夫移轉機率和穩定狀態機率來協助預測使用者網頁瀏覽的行為，推薦引擎可藉由模式發掘階段所產生之流覽圖和可到達圖來協助完成動態網頁的推薦。而我們結合以代理人為基礎和事件驅動非同步通知的架構來達到線上即時的資料準備、模式發掘和推薦三個階段。[[abstract]]Web recommendation systems are typical applications of Web usage mining. The Web recommendation system is structured according to an online and an off-line component. The off-line component is aimed at building the knowledge base by analyzing past usage profiles that is then used in the online component. The general Web recommendation system mainly uses offline data preprocessing and the mining process is not time-limited. However, this approach is not suitable in real-time dynamic environments. Therefore, we need high-performance online Web usage mining techniques to provide solutions to these problems. In this paper, we propose an online Web recommendation system using STPN. The Web recommendation process consists of the data preparation phase, pattern discovery phase, and recommendation phase. In data preparation phase, we use STPN to model the Web structure, and also apply the Web metrics of Web graph properties to analyze the Web structure in improving the Web access. We simultaneously employ the Web structure analysis information in the incidence matrix and the reachability properties, obtained from the STPN model, to help proceed with pageview identification and path completion at the data preprocessing. In pattern discovery phase, the navigational graph and reachability graph are employed to model the usage profiles. We use the data stream mining technique to incrementally maintain the navigational graph over a sliding-window. The STPN’s reachability behavior characteristic and incidence matrix are applied to construct the reachability graph. In recommendation phase, we use the transition probability and steady-state probability in Markov model to predict the user’s navigational behavior. The navigational graph and reachability graph are used by the Web recommendation engine to generate the online dynamic Web recommendation. We combine the features of both the agent-based architecture and event-driven asynchronous notification architecture to achieve the online data preparation, pattern discovery, and recommendation.[[tableofcontents]]Contents Chapter 1 Introduction 1 Chapter 2 Background and Related Works 6 2.1 Stochastic Timed Petri Nets (STPN) 6 2.1.1 STPN Reachability Behavior Characteristic 7 2.2 Markov Chains 9 2.3 Web Graph 10 2.3.1 Centrality 11 2.3.2 Global Metrics 12 2.3.3 Local Metrics 14 2.4 WS-Notification 15 2.5 Related Works 17 Chapter 3 System Overview 19 3.1 System Architecture 19 3.2 Component Description 21 Chapter 4 Online Change Detection and processing 24 4.1 Web Server Log File 24 4.2 File Monitoring Agent 26 4.2.1 Data cleaning 30 4.3 Notification broker 31 Chapter 5 Using STPN to Model and Analysis the Web Structure 34 5.1 Modeling a Website Structure with STPN 34 5.2 Web Structure Metrics 39 5.2.1 Centrality 42 5.2.2 Global Metrics 48 5.2.3 Local Metrics 50 5.3 Incremental Web Structure Adapting 51 5.3.1 Adding a Link 51 5.3.2 Adding a Webpage 53 5.3.3 Deleting a link 56 5.3.4 Deleting a Webpage 58 Chapter 6 Using STPN to Enhance Web Usage Data Preprocessing 62 6.1 User Identification 66 6.2 Session Identification 67 6.3 Pageview Identification 68 6.4 Path Completion 74 6.5 Data Transformation 78 Chapter 7 Online Web Recommendation 80 7.1 User Profiles 80 7.1.1 Navigational Graph 81 7.1.2 Reachability Graph 82 7.2 Probabilistic Model 83 7.3 Incremental Maintaining Navigational Graph and Reachability Graph 89 7.4 Web Recommendation 103 Chapter 8 Conclusions and Future Research 108 Reference 111 List of Figures Figure 1: The Web usage mining process 1 Figure 2: General architecture of a typical Web recommendation system 2 Figure 3: The compactness of global metrics 13 Figure 4: The stratum of global metrics 14 Figure 5: A typical WS-Notification interaction 16 Figure 6: A typical brokered WS-Notification interaction 16 Figure 7: Sample topic space 16 Figure 8: Sample WS-topic topic space definition 17 Figure 9: The system architecture and major components 20 Figure 10: Example Web log file in the common log format 25 Figure 11: The file monitoring agent component 26 Figure 12: Example of the event message for Web program 27 Figure 13: Example of the event message for Web log 28 Figure 14: The file monitoring agent algorithm 29 Figure 15: The data cleaning algorithm 31 Figure 16: The notification broker component 32 Figure 17: The interaction diagram of the message exchange 33 Figure 18: The Web structure of Table 1 37 Figure 19: The Stochastic Timed Petri Nets corresponding to the Web structure of Table 2 38 Figure 20: The flow chart of calculating Web metrics algorithm 40 Figure 21: Convert the Incidence matrix to the converted distance matrix algorithm 41 Figure 22: The Web centrality metrics algorithm 43 Figure 23: The Web structure of Table 3 45 Figure 24: The cross-linked tree structure after adjusting 48 Figure 25: The cross-linked tree structure and depth vector, child vector after adjusting 50 Figure 26: The adding a link algorithm 53 Figure 27: The adding a Webpage algorithm 55 Figure 28: The deleting a link algorithm 57 Figure 29: The deleting a Webpage algorithm 60 Figure 30: The Web usage data preprocessing process 63 Figure 31: The component diagram of pageview identification and path completion 64 Figure 32: The Web usage data preprocessing using STPN algorithm 65 Figure 33: The data schema of the User, Session, and Pageviews 66 Figure 34: The user identification algorithm 67 Figure 35: The session identification algorithm 68 Figure 36: Web structure and STPN structure 70 Figure 37: The STPN pageview identification algorithm 71 Figure 38: The STPN path completion algorithm 76 Figure 39: The state equation of path complete 78 Figure 40: The navigational graph 82 Figure 41: The reachability graph 83 Figure 42: The calculate stead-state probability matrix algorithm 87 Figure 43: The flow chart of adding session algorithm 89 Figure 44: The adding session algorithm 90 Figure 45: The add child node algorithm 92 Figure 46: The navigational graph over a sliding-window (size=6) 94 Figure 47: The remove session algorithm 96 Figure 48: The navigational graph over a sliding-window (size=6) after adding the new session S7 98 Figure 49: The adding session to reachability graph algorithm 100 Figure 50: The reachability graph after adding the session S7 101 Figure 51: The remove Web page algorithm 103 Figure 52: The flow chart of Web recommendation algorithm 104 Figure 53: The Web recommendation algorithm 105 Figure 54: The Web recommendation of the active session: b 106 Figure 55: The Web recommendation of the active session: b->f 107 List of Tables Table 1: The hyperlink content of a Web structure 36 Table 2: The incidence matrix represents a Web structure shown in Figure 15 37 Table 3: The Web structure example 44 Table 4: The places and the corresponding Web pages 45 Table 5: The transitions and the corresponding hyperlinks’ labels 45 Table 6: Incidence matrix [Aij]7x8 which denotes the Web structure 46 Table 7: The initial matrix [Cij]7x7 which denotes the Web structure 46 Table 8: The converted distance matrix [Cij]7x7 & the value of COD, CID, ROC, RIC 46 Table 9: The incidence matrix [Aij]7x9 after adding g link to e 47 Table 10: The converted distance matrix [Cij]7x7 & the value of COD, CID, ROC, RIC after adjusting 48 Table 11: The converted distance matrix [Dij]7x7 & stratum related metrics after adjusting 49 Table 12: The transitions and the corresponding hyperlinks’ labels after adding the link: g to e 53 Table 13: The incidence matrix after adding a new page h 53 Table 14: The places and the corresponding Web pages after adding a new page h 55 Table 15: The transitions and the corresponding hyperlinks’ labels after adding the link: h to e 55 Table 16: The incidence matrix after adding Web page h and the link: h to e 55 Table 17: The transitions and the corresponding hyperlinks’ labels after deleting the link: e to a 58 Table 18: The incidence matrix after deleting the link: e to a 58 Table 19: The places and the corresponding Web pages 60 Table 20: The transitions and the corresponding hyperlinks’ labels 61 Table 21: The associated matrix after deleting the link: e to d and the link: d to a 61 Table 22: A user session before pageview identification 73 Table 23: A user session after pageview identification 73 Table 24: The activity of Web usage metrics 79 Table 25: The 6 pieces of user’s session data 82 Table 26: The co-occurrence matrix of the two Web pages 85 Table 27: The initial transition probability matrix 85 Table 28: The steady-state probability matrix 88 Table 29: The co-occurrence matrix of the navigational graph 94 Table 30: The initial transition probability matrix of the navigational graph 95 Table 31: The steady-state probability matrix of the navigational graph 95 Table 32: The standardized steady-state probability matrix of the navigational graph 95 Table 33: The co-occurrence matrix after deleting session S1 and adding the new session S7 98 Table 34: The initial transition probability matrix after deleting session S1 and adding the new session S7 99 Table 35: The standardized steady-state probability matrix after deleting session S1 and adding the new session S7 99 Table 36: The co-occurrence matrix of the reachability graph 101 Table 37: The initial transition probability matrix of the reachability graph 102 Table 38: The standardized steady-state probability matrix of the reachability graph 102[[note]]學號: 894190320, 學年度: 9