臺灣博碩士論文加值系統

近幾年網際網路的迅速發展，使得資料不斷地與日俱增，因此造成巨量資料(Big Data)、雲端運算(Cloud Computing)、資料探勘(Data Mining)等相關議題成為近幾年非常熱門的議題。在本篇論文中，我們運用一個在頻繁樣式探勘(Frequent pattern mining)中具代表性的經典演算法─Apriori演算法運用在巨量資料時可能產生的問題，進行深入研究與探討，因為傳統的Apriori演算法會隨著增加資料庫的資料量及支持度縮小時，計算時間將會大量增加。
本論文提出兩個演算法，”運用MapReduce框架之頻繁項目集探勘演算法”(Frequent Patterns Mining Algorithm Based on MapReduce Framework, FAMR)與”優化FAMR” (Optimization FAMR, OFAMR)演算法，我們運用Hadoop平台中MapReduce框架的特性，改進傳統Apriori演算法的執行方式，以達到更佳的運算效能。於本論文中，我們藉由對原始資料的預處理，使得Apriori演算法在MapReduce的運算中，能夠大量減少記憶體的負載量，有效地提升運算的效能。
在前人利用MapReduce框架進行Apriori演算法的平行化所提出的”One-phase”演算法中，由於運用一次性的MapReduce運算，One-phase的方法會一次產生所有的候選項目，而造成記憶體不足的狀況發生，當記憶體不足時會嚴重拖延運算時間，FAMR針對此一問題進行改進，大量降低非高頻項目的候選集，減少記憶體的使用，因此，相較於One-phase的運算時間，FAMR最少有16.2以上的加速比，同時，我們亦針對FAMR做優化並提出OFAMR演算法，與FAMR的執行速度比較，OFAMR演算法在較大量的資料狀況下可達到1.17倍的加速比。

Recently, the data is continuously increasing in every enterprise. The Big Data, Cloud Computing, Data Mining etc., become hot topics in the present day. In this thesis, we modified the tradition Apriori algorithm by improving the execution efficiency, since Aprori algorithm confronted with an issue that the computation time increases dramatically when data size increases. Therefore, we design and implement two efficient algorithms: Frequent Patterns Mining Algorithm Based on MapReduce Framework (FAMR) algorithm and Optimization FAMR (OFAMR) algorithm. We adopt Hadoop MapReduce framework’s advantage to shorten the mining execution time
Compared with “One-phase” algorithm, experimental results showed that FAMR has 16.2 speedup in the running time. Since the previous method only used one-time MapReduce operation, it will generate excessive candidates and result insufficient memory. Moreover, we implemented another Optimization FAMR (OFAMR) algorithm in the thesis; the performance of OFAMR is superior to FAMR, because the number of candidates generated by OFAMR is less than the candidates generated by FAMR.

摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
第一章 緒論 1
第二章 相關研究 4
2.1 資料探勘 4
2.2 Apriori演算法 6
2.3 AprioriTID演算法 10
2.4 Hadoop 11
2.5 HDFS 12
2.6 MapReduce 15
2.7 Apriori Algorithm on MapReduce 17
2.8 Parallel of Apriori Algorithm on MapReduce 19
2.9 MRApriori 21
第三章 研究方法 24
3.1運用MapReduce框架之頻繁項目集探勘演算法(Frequent Patterns Mining Algorithm Based on MapReduce Framework, FAMR) 24
3.2 FAMR演算法及流程圖 27
3.3優化FAMR的演算法(Optimization FAMR, OFAMR) 31
第四章 實驗與結果分析 34
4.1實驗環境設定 34
4.2 FAMR演算法、OFAMR演算法與以前方法比較 35
第五章 結論與未來展望 45
參考文獻 47

[1] Apache, “Hadoop,” http://hadoop.apache.org/, 2006.
[2] R. Agrawal, T. Imielinski, and A. Swami, “Mining Association Rule between Sets of Items in Large Databases,” ACM SIGMOD Conf. Management of Data, pp. 207-216, May 1993.
[3] R. Agrawal, and R. Srikant, “Fast algorithms for mining association rules,” International Conference on Very Large Data Bases, pp. 487-499, 1994.
[4] R. Agrawal, and R. Srikant, “Quest Synthetic Data Generator,” IBM Almaden Research Center, San Jose, California, 2009.
[5] D. Borthakur, “The Hadoop Distributed File System: Architecture and Design,” http://hadoop.apache.org/docs/r0.18.0/hdfs_design.pdf.
[6] Data mining, http://en.wikipedia.org/wiki/Data_mining.
[7] S. Ghemawat, H. Gobioff, S.T. Leung, “The Google file system,” SOSP '03 Proceedings of the nineteenth ACM symposium on Operating systems principles, pp. 29-43, 2003.
[8] W.H. Inmon, Building the Data Warehouse. John Wiley, 1992.
[9] N. Li, L. Zeng, Q. He &; Z. Shi, “Parallel Implementation of Apriori Algorithm Based on MapReduce,” Proc. of the 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel &; Distributed Computing (SNPD’12). Kyoto, IEEE: 236 – 241, 2012.
[10] L. Li, M. Zhang, “The Strategy of Mining Association Rule Based on Cloud Computing,” Proc. of the 2011 International Conference on Business Computing and Global Informatization (BCGIN’11). Washington, DC, USA, IEEE: 475- 478, 2011.
[11] M. Lin, P. Lee, S. Hsueh, “Apriori-based Frequent Itemset Mining Algorithms on MapReduce,” Proc. of the 16th International Conference on Ubiquitous Information Management and Communication (ICUIMC ’12). New York, NY, USA, ACM: Article No. 76, 2012.
[12] Online database, http://en.wikipedia.org/wiki/Online_database.
[13] R. Sears, K. Elmeleegy, T. Condie, N. Conway, P. Alvaro, J.M. Hellerstein, “MapReduce Online,” NSDI'10 Proceedings of the 7th USENIX conference on Networked systems design and implementation, pp. 21-21, 2010.
[14] Taiwan Hadoop Forum, http://forum.hadoop.tw/.
[15] A. Weiss, “Computing in the clouds,” ACM Networker, 11(4):18-25, Dec.2007.
[16] T. White, Hadoop: The Definitive Guide. O’Reilly Media, Yahoo! Press, June 5, 2009.
[17] O. Yahya, O. Hegazy, E. Ezat, “An Efficient Implementation of Apriori Algorithm Based on Hadoop-MapReduce Model,” International Journal of Reviews in Computing (IJRIC ’12). pp. 59-67, Vol. 12, December 31 2012.
[18] X.Y. Yang, Z. Liu, Y. Fu, “MapReduce as a Programming Model for Association Rules Algorithm on Hadoop,” Proc. of the 3rd International Conference on Information Sciences and Interaction Sciences (ICIS’10). Chengdu, China, IEEE: 99 – 102, 2010.
[19] K.M. Yu, C.Y. Lin, W. Ouyang, J. Zhou, “An OpenCL Candidate Slicing Frequent Pattern Mining algorithm on graphic processing units,” In proceeding of: Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, pp. 2344-2349, 2011
[20] K.M. Yu, S.H. Wu, “An Efficient Load Balancing Multi-core Frequent Patterns Mining Algorithm,” Trust, Security and Privacy in Computing and Communications (TrustCom), pp. 1408-1412, 2011.
[21] K.M. Yu, J. Zhou, “A Weighted Load-Balancing Parallel Apriori Algorithm for Association Rule Mining,” IEEE Internation Conference on Granular Computing, pp. 756-761, 2008.
[22] K.M. Yu, J. Zhou, W.C.Hsiao, “Load Balancing Approach Parallel Algorithm for Frequent Pattern Mining,” Parallel Computing TechnologiesLecture Notes in Computer Science Vol. 4671, 2007, pp. 623-631
[23] K.M. Yu, J. Zhou, T.P. Hong et al., “A Load-Balanced Distributed Parallel Mining Algorithm,” Expert Systems with Applications, vol. 37, no. 3, pp. 2486-2494, 2009.
[24] 陸嘉恆，Hadoop 實戰技術手冊，佳魁資訊。
[25] 資料探勘，http://www.icoding.co/2012/08/data-mining-newbie-html。