本研究以提昇循序樣本探勘效率為目標，發展了一套結合多部電腦的分散式探勘系統。首先，由於直接以支持度預測子任務工作量並不準確，我們提出新的工作量預測方法。而後，本研究提出了一套負載平衡演算法-ADLB，結合動態與靜態分配的特點，對於任務採取分段分配，以達成負載平衡並降低通訊負擔。此外，我們也引用並改進文獻[20]中有關演算法切換的概念，以取得更大幅度效能改善。為驗證系統效能，我們結合了16部電腦進行分散式探勘，實驗結果顯示，本系統在各種不同節點數目下均具有良好加速比，顯示其具有處理大型資料之潛力。

The research develop a distributed mining system coordinating multi computers to promote efficiency of sequential pattern mining. First, because of the inaccuracy of directly supporting sequential pattern mining. Then, the work propose a Advanced Dynamic Load Balance algorithm -ADLB. Different to previous works, ADLB 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, we also improve the performance with  on the basis of citing literature 20. Choose a proper mining algorithm for each database but not apply a single algorithm for all databases with different features. In addition, we combine the sixteen computers that adoptee distributed mining. In comparison with the previous works, the experimental results shows ADLB can effectively reduce the runtime and obtain a better speed-up ratio. This result demonstrates the potentials of ADLB for mining sequential pattern in Very Large Databases.

目錄
1.	緒論	1
2.	資料探勘相關演算法	5
2.1.	非平行式循序樣本探勘演算法	6
2.1.1.	PrefixSpan演算法[5]	6
2.1.2.	SPADE演算法[11]	7
2.2.	平行循序樣本探勘演算法	9
2.2.1.	以樹狀投射為基礎之平行演算法[17]	9
2.2.2.	pSPADE演算法[12]	10
3.	分散式循序樣本探勘	13
3.1.	分散式探勘環境	13
3.2.	任務工作量預測	14
3.3.	分散式循序樣本探勘演算法	18
3.3.1.	SDLB[20]	18
3.3.2.	初始任務分段	19
3.3.3.	負載平衡	20
3.3.4.	任務平衡度測試	26
3.3.5.	處理嚴重傾斜之資料庫	27
4.	節點探勘演算法選擇	30
4.1.	PrefixSpan與SPADE之比較	30
4.2.	節點演算法選擇之原則	32
4.3.	應用演算法切換概念於漸進更新之資料庫	34
5.	實驗結果	40
5.1.	ADLB效能驗證	40
5.2.	ADLB2效能驗證	42
6.	結論	45
參考文獻	47
附錄 1		50
附錄 2		51
附錄 3	資料庫生成及格式	54
3.1	資料庫生成	54
3.2	資料庫格式	55
 
表目錄
表 1.  PrefixSpan範例資料	6
表 2.  字首映射後的資料及循序樣本	7
表3.  水平資料庫範例	8
表4.  ID-list	8
表 5.  ID-List時序結合	8
表 6.  frequent 1-sequence支持度、剩餘交易量與執行時間	17
表 7.  分散式探勘演算法	23
表 8.  分散式探勘演算法-漸進試資料庫	36
表 9.  執行時間與加速比	41
表 10. 漸進式資料庫執行時間	43
表 11. 遞增式資料庫執行時間	44
 
圖目錄
圖 1.  PrefixSpan 演算法產生之樹狀結構	9
圖 2.  pSPADE產生之循序樣本	10
圖 3.  分散式探勘架構	14
圖 4.  SDLB任務分割	18
圖 5.  ADLB任務分割	20
圖 6.  不同特性之分散式演算法與負載平衡	27
圖 7.  不同特性之分散式演算法與負載平衡	28
圖 8.  不同特性之分散式演算法與負載平衡	29
圖 9.  不同的樣本分布圖	31
圖 10. 不同特性之探勘結果與演算法執行時間之相關性	31
圖 11. 樣本分佈趨勢圖	34
圖 12. 受測資料庫比較	35
圖 13. 實驗資料庫-樣本分佈趨勢圖	41
圖 14. 執行時間與加速比	42
圖 15. 遞減式資料庫樣本分佈趨勢圖	43
圖 16. 遞增式資料庫樣本分佈趨勢圖	44

[1]	 IBM. http://www.almaden.ibm.com/software/quest/Resources/index.shtml. Quest Data Mining Project, IBM Almaden Research Center, San Jose, CA 95120. 
[2]	 J. Han, J. Pei, and Y. Yin, “Mining frequent patterns without candidate generation”, In Proc. ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’00), Dallas, TX, May 2000, pp.1-12. 
[3]	 J. Pei, et al., “FreeSpan: Frequent pattern-projected sequential pattern mining”, In Proc. Int. Conf. Knowledge Discovery and Data Mining (KDD’00), Boston, MA, August 2000, pp. 355-359. 
[4]	 J. Pei, J. Han, and W. Wang, “Mining Sequential Patterns with Constraints in Large Databases”, Proc. 2002 Int. Conf. on Information and Knowledge Management (CIKM'02), Washington, D.C., Nov. 2001. 
[5]	 J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu, “PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth,” Proc. 2001 Int'l Conf. Data Eng. (ICDE '01), pp. 215-226, 2001. 
[6]	 J. Pei, J. Han, and W. Wang, Constraint-Based Sequential Pattern Mining in Large Databases Proc. 2002 Int'l Conf. Information and Knowledge Management (CIKM '02), pp. 18-25, Nov. 2002. 
[7]	 J. Pei, J. Han, B. Mortazavi-Asl, J. Wang, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu. "Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach," IEEE Transactions on Knowledge and Data Engineering, vol.16, no.11, pp.1424-1440, November 2004. 
[8]	 J. S. Park; Ming-S yan Chen and Philip S. Yu , “An Effective Hash-Based Algorithm for Mining Association Rules,” Proceedins Management of Data ,May 1995 ACM SIGMOD international conference on Management of Data , May 1995,pp.175-186.
[9]	 M. Garofalakis, R. Rastogi, and K. Shim, “Mining Sequential Patterns with Regular Expression Constrains,” IEEE Trans. on Knowledge and Data Eng., Vol. 14, No. 3, pp. 530-552, May/June 2002. 
[10]	 M. J. Zaki, “Sequence mining in categorical domains: Incorporating constraints,” In CIKM, pages 422-429,2000. 
[11]	 M. J. Zaki. “SPADE: An efficient algorithm for mining frequent sequences,” Machine Learning, 42(1/2):31-60, 2001. 
[12]	 M. J. Zaki, “Parallel Sequence Mining on Shared-Memory Machines,” Journal of Parallel and Distributed Computing 61, 401-426 (2001). 
[13]	 R. Agrawal and R. Srikant. Fast Algorithms for Mining Association Rules. In Proc. 1994 Int. Conf. Very Large Data Bases (VLDB’94), pages 487–499, Santiago, Chile, Sept. 1994. 
[14]	 R. Agrawal and R. Srikant. Mining Sequential Patterns. In Proc. 1995 Int. Conf. Data Engineering (ICDE’95), pages 3–14, Taipei, Taiwan, Mar. 1995. 
[15]	 R. Srikant and R. Agrawal. Mining sequential patterns: Generalizations and performance improvements. In 5th Intl. Conf. Extending Database Technology, March 1996. 
[16]	 S. Orlando, R. Perego, C. Silvestri: A new algorithm for gap constrained sequence mining. Symposim on Applied Computing (SAC'04), pp 540-547, 2004. 
[17]	 V. Guralnik and G. Karypis, “Parallel tree-projection-based sequence mining algorithms,” Parallel Computing 30 (2004) 443-472. 
[18]	 Y. L. Chen, S. S. Chen, and P. Y. Hsu, “Mining hybrid sequential patterns and sequential rules, Information Systems,” Vol. 27, No. 5, 2004, pp. 345-362. 
[19]	 張昭憲、周定賢，“以動態任務分配為基礎之分散式循序樣本探勘系統”，第十六屆國際資訊管理學術研討會，台北(輔仁大學)，2005年5月。
[20]	 張昭憲、黃揚智，“有效率的分散式循序樣本探勘系統”，2006年1月。