(3.238.96.184) 您好!臺灣時間:2021/05/08 21:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:周定賢
研究生(外文):Ting-Hsien Chou
論文名稱:以動態任務分配為基礎之分散式循序樣本探勘系統
論文名稱(外文):A Distributed Sequential Pattern Mining System based on Dynamic Task Partition
指導教授:張昭憲張昭憲引用關係
學位類別:碩士
校院名稱:淡江大學
系所名稱:資訊管理學系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2005
畢業學年度:93
語文別:中文
論文頁數:41
中文關鍵詞:循序樣本探勘分散式架構關聯規則資料探勘
外文關鍵詞:sequential pattern miningdistributed architectureassociation rulesdata mining
相關次數:
  • 被引用被引用:0
  • 點閱點閱:90
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
循序樣本探勘(sequential pattern mining)可從資料庫找出經常出現的樣本,而且指出樣本中各項目出現的時序,其複雜度遠高於關聯規則式的菜籃分析(Market Basket Analysis)。針對循序樣本探勘目前已有許多方法被提出[1,10-16],然而,面對日益膨脹的資料庫,這些方法的效能再次受到挑戰。為有效改善大型資料庫的探勘效率,利用網路結合多部電腦的分散式探勘(distributed mining)便開始受到重視[2][4]。
為加速大型資料庫的循序樣本探勘,本研究以分散式架構為基礎研製有效的探勘演算法,並據以發展實用的探勘系統。首先,本研究提出任務佇列(task queue)的概念,有效結合靜態與動態任務分配之優點,不但可減輕靜態分配的任務歪斜問題,亦能降低動態分配頻繁的通訊負擔。其次,為使探勘完成後之結果彙整更有效率,本研究也充分利用閒置節點來進行探勘結果整合。此外,我們特別採用PrefixSpan[1]做為基礎演算法,以便有效控制任務間的獨立性。為評估系統效能,我們分別使用2、4、8、16及32部電腦進行分散式探勘實驗,數據顯示本系統不但能有效降低探勘時間,同時具有良好的加速比(speedup ratio)。此結果驗證了提出方法之有效性,也顯示本系統處理大型資料庫之潛能。
Sequential pattern mining can discover frequent patterns in database and point out the sequence of items in patterns. It is more complex than traditional association rule mining. In the past few years, there are many efficient sequential pattern mining methods have been proposed. However, their efficiency are being challenged because the size of real-life database is drastically increased. In order to alleviate the problem of mining large database, the researchers begin paying attention to perform mining under a distributed architecture.
In this thesis, a distributed sequential pattern mining system are developed to speed up the mining process. The proposed system is based on a novel concept of “task queue”, which effectively abates task askew of static task partition and communication overhead of dynamic task partition. For the purpose of collecting the mining result efficiently, the first idle node is assigned to collect the resultant patterns. Besides, to maintain the independency of dispatched tasks, we adopt PrefixSpan as the outline algorithm. Finally , we performed a serious of experiments on 1, 2, 4, 8, 16 and 32 processors respectively. A fine speedup ratio is obtained according to the experimental results. It clearly demonstrate that the system has potential to deal with large database .
目錄
第一章 緒論 1
第二章 循序樣本探勘方法簡介 6
2.1 PREFIXSPAN演算法 7
2.2 分散式資料探勘演算法 10
2.3 演算法評析 12
第三章 分散式資料探勘系統 14
3.1系統架構 14
3.2系統運作模式 15
3.3探勘過程之任務分配方式 17
第四章 實驗結果 27
4.1實驗環境 27
4.2實驗結果 27
4.3實驗結果比較 31
第五章 結論 34
參考文獻 35
附錄 37
附錄1 37
附錄2 39

表目錄
表 一 範例交易資料庫 8
表 二 一階頻繁項目之投影資料庫 9
表 三 表一中的範例資料庫產生的循序樣本 9
表 四 探勘任務執行時間 28
表 五 產生一階頻繁項目集與二階頻繁項目集之比較 31
表 六 動態任務分配資料庫特性 32
表 七 動態任務分配加速比 33

圖目錄
圖 一 系統運作模式 15
圖 二 樣本收集步驟 17
圖 三 靜態任務分配 18
圖 四 動態任務分配 19
圖 五 Z字型靜態任務分配 25
圖 六 五萬筆資料加速比趨勢圖 29
圖 七 七萬五千筆資料加速比趨勢圖 29
圖 八 十萬筆資料加速比趨勢圖 30
[1]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”,In Proc. Int. Conf. Data Engineering (ICDE ’01), Heidelberg, Germany, April 2001, pp.215-224.
[2]Valerie Gualnik , George Karypis ,“ Paralel tree-projection-based sequence mining algorithms ”,Parallel Computing ,30 (2004) 443-472 . (ELSEVIER)
[3]Agrawal R, Srikant R.“Fast algorithm for mining association rules”.In: Proceedings of the 20th International Conference on VLDB. Santiago, 1994. 487~499.
[4]Cheung, D.W. , Ng , V.T; Fu , A.W. , Yongjian Fu , “Efficient Mining of Association Rule in Distributed Databases ” , IEEE Transaction on Knowledge and Data Emgomeeromg , Vp; 8 ,No.6 .Dec 1996
[5]T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, McGraw-Hill,New York, NY, 1990.
[6]A. Grama, A. Gupta, G. Karypis, V. Kumar, “Introduction to Parallel Computing: Design and Analysis of Algorithms, 2nd ed.”, Addison Wesley Publishing Company, Redwood City, CA, 2003.
[7]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.
[8]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.
[9]J. Pei, J. Han, B. Mortazavi-Asl, H. Zhu, “Mining access pattern efficiently from web logs”, in proceedings of Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2000, pp. 396-407.
[10]R. Srikant and R. Agrawal. Mining sequential patterns. In 11th Int. Conf. Data Engineering, 1995.
[11]R. Agrawal and R. Srikant. “Mining sequential patterns: Generalizations and per- formance improvements”. Proc. of the Fifth Int''l Conference on Extending Database Technology, 1995.
[12]M. J. Zaki, “SPADE: An efficient algorithm for mining frequent sequences”, Machine Learning, vol. 1, no. 1~2, 2001, pp. 31-60.
[13]http://www-sal.cs.uiuc.edu/~hanj/
[14]J. Pei, J. Han and W. Wang, “Mining Sequential Patterns with Constraints in Large Databases,” CIKM’02, Nov. 4-9, 2002, McLean, Virginia, USA.
[15]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.
[16]D. E. Brown, and R. B. Oxford, “Data Mining Time Series with Applications to Crime Analysis,” Proceeding of the 2001 IEEE conference, pp. 1453-1458.
[17]P. Bertone and M. Gerstein, “Integrative Data Mining: The New Direction in Bioinformatics,” IEEE Engineering in Medicine and Biology, July/August 2001, pp. 33-40.
[18]R.Agrawal and J.C. Shafer, “Parallel mining of association rules”, IEEE Transactions on Knowledge and Data Engineering, 8(6), pp962-969, 1996.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔