[[alternative]]An efficient distributed system for mining sequential patterns

碩士[[abstract]]本研究以提昇循序樣本探勘(sequential pattern mining)之效率為目標，發展以多部電腦為基礎的分散式探勘系統。分散式探勘首重節點間的負載平衡，同時需降低節點間通訊負擔。負載平衡與通訊負擔的降低均有賴於準確的任務工作量預測，此外，也應避免透過繁複的任務重分配來解決負載失衡的狀況。 針對上述重點，本研究首先針對相關文獻中常利用之工作量預測方法進行分析，發現以序列(sequence)支持度(support)為基礎之預測方式與實際狀況差異甚大，將嚴重影響負載平衡。此外，我們也發現不同特性之資料庫可能適用於不同之探勘演算法，此發現可導致全新的分散式演算法設計。根據上述結果，我們發展了一套新的分散式探勘演算法，Segmented Dynamic Load Balance algorithm (SDLB)。演算法中對於任務工作分配採取分段實施，並依狀況進行靜態與動態分配，期能在負載平衡與降低通訊負擔間取得協調。此外，本研究亦導入全新的演算法切換概念，能讓各節點依照分配任務之特性，選用合適之探勘演算法，以進一步提升總體效率。由實驗結果顯示，與前人研究相較，本系統能有效縮短執行時間，並取得更良好之加速比，此結果也顯示本系統具有處理超大型資料庫之潛力。[[abstract]]In this thesis, an effective distributed mining system is developed to increase the efficiency of sequential pattern mining. Two important concerns for distributed mining, load balance and communication overhead reduction, are carefully examined in our works. To achieve a good load balance, accurate predictions on work load of subtasks are indispensable. In addition, the independency of subtask should be effectively controlled to decrease the communication overhead among nodes. According to above objectives, the work load prediction methods used in the previous works are analyzed at first. We finds that the commonly-used prediction method does not show a well metrics for work load. Eventually, a skew presented in task partition occurs frequently due to the inaccurate prediction. Besides, we also found that, the efficiency of performing a sequence mining algorithm on a transaction database is strongly related to the distribution of sequential patterns in this database. To increase the mining efficiency, we should choose a proper mining algorithm for each database but not apply a single algorithm for all databases with different features. Base on the above observations, a novel distributed data mining algorithm, Segmented Dynamic Load Balance algorithm (SDLB), is developed. Different previous works, SDLB divides subtask dispatches into several stages. According to different situations, the static and dynamic load balance method are applied adeptly to prevent the task partition from skew and reduce the communication overhead simultaneously. Furthermore, SDLB inducts a brand-new concept that the nodes may adopt different basic mining algorithm for subtasks with different characteristics to promote the mining efficiency. In comparison with the previous works, the experimental results shows SDLB can effectively reduce the runtime and obtain a better speed-up ratio. This result demonstrates the potentials of SDLB for mining sequential pattern in Very Large Data Bases (VLDBs).[[tableofcontents]]目錄 1. 緒論 1 2. 循序樣本探勘簡介 7 2.1. 循序樣本探勘演算法 8 2.2. 循序樣本探勘之平行演算法 10 3. 子任務工作量預測 15 3.1. 支持度與工作量 15 3.2. 資料庫特性與演算法之關係 17 3.2.1. 資料庫特性與樣本分佈 17 3.2.2. 演算法特性與工作量 19 4. 分散式探勘演算法 21 4.1. 分散式探勘環境 21 4.2. 分散式探勘演算法 22 4.2.1. 任務分配架構 22 4.2.2. 分散式循序樣本探勘演算法 23 4.2.3. 任務分配法之平衡度比較 26 4.3. 節點探勘演算法切換 28 4.3.1. 切換架構 28 4.3.2. 演算法資料結構之探討 30 4.3.3. 演算法之執行時間相較 31 5. 實驗結果 32 5.1. 模擬資料庫 32 5.2. 分散式探勘演算法執行時間 33 5.2.1. 鞍型結構測試 34 5.2.2. 瀑布型結構測試 36 5.3. 各階層探勘時間 38 6. 結論 39 參考文獻 40 附錄一： 42 附錄二： 47 附錄三： 51 附錄四： 53 表目錄 表 2.1水平資料庫範例 8 表 2.2垂直資料庫範例 8 表 2.3 ID-list時序結合(Temporal Join) 9 表 2.4 PrefixSpan範例資料 10 表 2.5 字首映射後的資料及sequential patterns 10 表 3.1 Large 1-sequence支持度與總時間 17 表 4.1分散式探勘演算法 25 表 4.2演算法切換邏輯 29 表 4.3不同節點之探勘時間 31 表 5.1實驗用資料庫及其參數 32 表 5.2鞍型結構執行時間與加速比(單位：秒) 34 表 5.3一般及微偏結構執行時間與加速比(單位：秒) 36 圖目錄 圖 2.1 pSPADE產生之循序樣本 11 圖 2.2 PrefixSpan演算法產生之樹狀結構 14 圖 3.1資料庫參數對於循序樣本特性之影響 18 圖 3.2不同特性之探勘結果與演算法執行時間之相關性 20 圖 4.1分散式探勘之執行環境 21 圖 4.2任務分配架構圖 22 圖 4.3不同特性之分散式演算法與負載平衡 27 圖 4.4新舊架構之加速比 28 圖 4.5分散式演算法切換架構 29 圖 5.1實驗資料庫及其循序樣本特性 33 圖 5.2鞍型結構執行時間與加速比 35 圖 5.3一般及微偏結構執行時間與加速比 37 圖 5.4演算法與其各階層探勘時間加總 38[[note]]學號: 692520132, 學年度: 9