臺灣博碩士論文加值系統

過往我們可以透過經驗歸納出一些事物的潛在規則，而在有了電腦的運算輔助後，我們更可以將資料當中潛藏的資訊挖掘出來加以利用，但也因為儲存技術飛速發展，過往自動和半自動的分析方式已經漸漸無法適用，巨量資料的隨處可見，讓過去的資料探勘方法迎來了一次考驗，所以為了突破這個瓶頸，巨型資料探勘的題目也更為被看重。在巨型資料探勘的研究當中，依照不同的方向可大略分為六種方式，在本研究中我們深度探討了過往的探勘關聯式規則與資料分類之方法，並且經過分析與研究後，最終提出可實際使用在對應場景的數個方法，並且以資料產生器和現實資料進行雙重測試，以此證明我們的方法可以有效的處理各種類型的資料，並且在速度上能夠比起過去方法更有效率。
首先，平行化的資料探勘已經成為一個重要的研究領域。為了提高效率，因此我們提出了一個基於FP-Growth的算法，這個算法能夠在平行化計算環境中提供快速和可擴展的FP演算，以及提供簡化的數據結構來存儲項目和計數，以此盡可能地減少網絡傳輸上的資料量。為了驗證我們方法的有效性和效率，因此我們使用了DistEclat和BigFIM進行實驗比較，從實驗中可證明，該方法在處理巨量資料時具有優越的高效能，並且在各種實驗條件中仍然擁有良好的效能。
而在挖掘決策樹時，處理時間和I/O成本受到大量數據的影響，為了改善查找資料時的成本問題，本文提出在多個Client端之間分配數據，讓大量數據計算可以平均分配。然後在由Server端合併計算結果，並生成探勘結果。實驗結果證明了我們所提的演算法之優越性，也間接證明了該算法可處理更大量的數據並產生正確的結果。

Humans relied on experience to deduce the underlying rules of many things in the past. Nowadays, with the help of computers, information hidden in data can be more easily discovered and utilized. Yet, with the rapid development of storage technology, automatic and semi-automatic analysis methods have gradually become inapplicable. The ubiquity of big data has brought a challenge to the past data mining methods. To break this bottleneck, big data mining is becoming an increasingly valued subject. Big data mining can be roughly divided into six categories; in this study, we will have an in-depth discussion on past mining association rules and data classification methods. With analysis and research, we put forward several possible methods that can be used in corresponding scenarios. Then, we double-tested said methods with data generators and real data to prove that our methods can effectively handle various types of data, and are faster and more efficient than past methods.
First, data mining on distributed environments has emerged as an important research area. To improve the performance, we propose a set of algorithms based on FP growth that discover FPs that are capable of providing fast and scalable service in distributed computing environments and a brief data structure to store items and counts to minimize the data for transmission on the network. To ensure completeness and execution capability, DistEclat and BigFIM we re considered for the experiment comparison. Experiments show that the proposed method has superior cost-effectiveness for processing massive datasets and good capabilities under various experiment conditions.
During mining practical decision tree, the processing time and I/O cost are affected by the large amount of data. With the aim of improving the resource cost problem of exploration, this paper proposes to distribute data among multiple clients and distribute the large amount of data computation equally. The main server then consolidates the computation results and generates the survey results. Experiment results demonstrate the superiority of the proposed algorithm, thus allowing a larger amount of data to be processed and producing high-quality results.

中文摘要 I
Abstract III
誌謝 V
Table of Contents VII
List of Figures IX
List of Tables XI
Chapter 1 Introduction 1
1.1 Background 1
1.2 Motivation 4
1.3 Overview of the Dissertation 8
1.4 Organization of the Dissertation 9
Chapter 2 Related Work 10
2.1 FP-Tree and FP-Growth Association Rules Mining Algorithm 10
2.2 C4.5 Classification Algorithm 14
2.3 Research on Frequent Pattern Mining for Big Data 18
2.4 Database Projection Algorithm 23
2.5 BigFIM Algorithm 25
2.6 Research on Classification of Big Data 28
2.7 MR-C4.5 Algorithm 29
Chapter 3 A Fast Method for Mining Frequent Patterns from Big Data in Distributed Computing Environments 34
3.1 Introduction 34
3.2 Experimental evaluation and performance study 43
3.3 Summary 61
Chapter 4 A fast and distributed C4.5 algorithm for urban big data 63
4.1 Introduction 63
4.2 Experimental Evaluation and Performance Study 73
4.3 Summary 92
Chapter 5 Conclusions 94
References 95

[1]Chan, K., A. Wong, G. Piatesky–Shapiro and W. Frawley, 1991, Knowledge Discovery in Databases, AAAI/MIT Press Menlo Park, CA:/Cambridge, MA.
[2]Chakrabarti, S., M. Ester, U. Fayyad, J. Gehrke, J. Han, S. Morishita, G. Piatetsky-Shapiro and W. Wang, 2006, "Data mining curriculum: A proposal (Version 1.0)", Intensive working group of ACM SIGKDD curriculum committee, vol. 140, pp. 1-10.
[3]Bramer, M ,2007, Principles of data mining (Vol. 180), Springer.
[4]Madden, S., 2012, "From databases to big data", IEEE Internet Computing, vol. 16, no. 3, pp. 4-6.
[5]Fayyad, U., G. Piatetsky-Shapiro and P. Smyth, 1996, "From data mining to knowledge discovery in databases", AI magazine, vol. 17, no. 3, pp. 37-37.
[6]Agrawal, R., T. Imieliński and A. Swami, 1993, "Mining association rules between sets of items in large databases", Proceedings of the 1993 ACM SIGMOD international conference on Management of data, pp. 207-216, June.
[7]Han, J., J. Pei and Y. Yin, 2000, "Mining frequent patterns without candidate generation", ACM sigmod record, vol. 29, no. 2, pp. 1-12.
[8]Kass, G. V., 1980, "An exploratory technique for investigating large quantities of categorical data", Journal of the Royal Statistical Society: Series C, vol. 29, no. 2, pp. 119-127.
[9]Breiman, L., J. H. Friedman, R. A. Olshen and C. J. Stone, 2017, Classification and regression trees, Routledge.
[10]Quinlan, J. R., 1986, "Induction of decision trees", Machine learning, vol. 1, no. 1, pp. 81-106.
[11]Loh, W.-Y. and Y.-S. Shih, 1997, "Split selection methods for classification trees", Statistica sinica, pp. 815-840.
[12]Quinlan, J. R., 2014, C4.5: programs for machine learning, Elsevier.
[13]Schlegel, B., R. Gemulla and W. Lehner, 2011, "Memory-efficient frequent-itemset mining", Proceedings of the 14th international conference on extending database technology, pp. 461-472, ACM New York, NY, USA.
[14]Lucchese, C., S. Orlando and R. Perego, 2005, "Fast and memory efficient mining of frequent closed itemsets", IEEE Transactions on Knowledge Data Engineering, vol. 18, no. 1, pp. 21-36.
[15]Javed, A. and A. Khokhar, 2004, "Frequent pattern mining on message passing multiprocessor systems", Distributed Parallel Databases, vol. 16, no. 3, pp. 321-334, ACM New York, NY, USA ©2000
[16]Vu, L. and G. Alaghband, 2013, "Novel parallel method for mining frequent patterns on multi-core shared memory systems", Proceedings of the 2013 International Workshop on Data-Intensive Scalable Computing Systems, pp. 49-54, ACM New York, NY, USA.
[17]Zhou, J. and K.-M. Yu, 2008, "Balanced Tidset-based parallel FP-tree algorithm for the frequent pattern mining on grid system", 2008 Fourth International Conference on Semantics, Knowledge and Grid, pp. 103-108, IEEE.
[18]Lin, K. W. and Y.-C. Lo, 2013, "Efficient algorithms for frequent pattern mining in many-task computing environments", Knowledge-Based Systems, vol. 49, pp. 10-21.
[19]Cameron, J. J., A. Cuzzocrea and C. K. Leung, 2013, "Stream mining of frequent sets with limited memory", Proceedings of the 28th Annual ACM Symposium on Applied Computing, pp. 173-175, ACM New York, NY, USA.
[20]Adnan, M. and R. Alhajj, 2009, "DRFP-tree: disk-resident frequent pattern tree", Applied Intelligence, vol. 30, no. 2, pp. 84-97.
[21]Han, J., J. Pei, Y. Yin and R. Mao, 2004, "Mining frequent patterns without candidate generation: A frequent-pattern tree approach", Data mining knowledge discovery, vol. 8, no. 1, pp. 53-87.
[22]Grahne, G., J. Zhu, 2004, "Mining Frequent Itemsets from Secondary Memory", International Conference on Data Mining, pp. 91-98, November.
[23]"Apache Hadoop" [Online]. Available: https://hadoop.apache.org/
[24]"Spark" [Online]. Available:http://spark.apache.org/
[25]Wu, X., V. Kumar, J. Ross Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan, A. Ng, B. Liu and P. S. Yu, 2008, "Top 10 algorithms in data mining", Knowledge information systems, vol. 14, no. 1, pp. 1-37.
[26]Qiu, Y., Y. J. Lan and Q. S. Xie, 2004, "An improved algorithm of mining from FP- tree", Proceedings of the Third International Conference on Machine Learning and Cybernetics, pp. 26-29.
[27]Zhou, J. and K.-M. Yu, 2008, "Tidset-based parallel FP-tree algorithm for the frequent pattern mining problem on PC clusters", International Conference on Grid and Pervasive Computing, pp. 18-28, Springer.
[28]Li, H., Y. Wang, D. Zhang, M. Zhang and E. Y. Chang, 2008, "Pfp: parallel fp-growth for query recommendation", Proceedings of the 2008 ACM conference on Recommender systems, pp. 107-114.
[29]Wei, X., Y. Ma, F. Zhang, M. Liu and W. Shen, 2014, "Incremental FP-Growth mining strategy for dynamic threshold value and database based on MapReduce", Proceedings of the 2014 IEEE 18th International Conference on Computer Supported Cooperative Work in Design (CSCWD), pp. 271-276, IEEE, Hsinchu.
[30]Makanju, A., Z. Farzanyar, A. An, N. Cercone, Z. Z. Hu and Y. Hu, 2016, "Deep parallelization of parallel FP-growth using parent-child MapReduce", 2016 IEEE International Conference on Big Data (Big Data), pp. 1422-1431, IEEE, Washington, DC.
[31]Xia, D., X. Lu, H. Li, W. Wang, Y. Li and Z. Zhang, 2018, "A MapReduce-based parallel frequent pattern growth algorithm for spatiotemporal association analysis of mobile trajectory big data", Complexity, vol. 2018.
[32]Chang, H.-Y., Y.-J. Tzang, J.-C. Lin, Z.-H. Hong, T.-Y. Chi and C.-Y. Huang, 2015, "A Hybrid Algorithm for Frequent Pattern Mining Using MapReduce Framework", 2015 First International Conference on Computational Intelligence Theory, Systems and Applications (CCITSA), pp. 19-22, Yilan, doi: 10.1109/CCITSA.2015.40.
[33]Wang, C.-S. and J.-Y. Chang, 2019, "MISFP-growth: hadoop-based frequent pattern mining with multiple item support", Applied Sciences, vol. 9, no. 10, pp. 2075.
[34]Moens, S., E. Aksehirli and B. Goethals, 2013, "Frequent Itemset Mining for Big Data", Big Data, 2013 IEEE International Conference on, pp. 111-118.
[35]Bin, Z. and X. Wensheng, 2015,"An Improved Algorithm for High Speed Train's Maintenance Data Mining Based on MapReduce", 2015 International Conference on Cloud Computing and Big Data (CCBD), pp. 59-66, Shanghai
[36]He, B., J. Pei and H. Zhang, 2017, "The mining algorithm of frequent itemsets based on mapreduce and FP-tree", 2017 International Conference on Computer Network, Electronic and Automation (ICCNEA), pp. 108-111, IEEE.
[37]Ragaventhiran, J. and M. Kavithadevi, 2020, "Map-optimize-reduce: CAN tree assisted FP-growth algorithm for clusters based FP mining on Hadoop", Future Generation Computer Systems, vol. 103, pp.111-122.
[38]Corporation I., "IBM Platform Computing", http://www03.ibm.com/systems/platformcomputing/products/symphony/, accessed: 2016-02-04.
[39]dite Gassama, A. D., F. Camara and S. Ndiaye, 2017,"S-FPG: A parallel version of FP-Growth algorithm under Apache Spark™", in 2017 IEEE 2nd International Conference on Cloud Computing and Big Data Analysis (ICCCBDA), pp. 98-101, IEEE.
[40]Cai, Z., X. Zhu, Y. Zheng, D. Liu and L. Xu, 2018, "A Caching-Based Parallel FP-Growth in Apache Spark", in International Conference on Algorithms and Architectures for Parallel Processing, pp. 519-533, Springer.
[41]Miao, Y., J. Lin and N. Xu, 2019, "An improved parallel FP-growth algorithm based on Spark and its application", in 2019 Chinese Control Conference (CCC), pp. 3793-3797, IEEE.
[42]Zhang, Y. and L. Wang, 2020, "A optimization algorithm for association rule based on spark platform", in 2020 International Conference on Computer Network, Electronic and Automation (ICCNEA), pp. 82-86, IEEE.
[43]Zaki, M. J., S. Parthasarathy, M. Ogihara and W. Li, 1997, "Parallel algorithms for discovery of association rules", Data mining and knowledge discovery, vol. 1, no. 4, pp. 343-373.
[44]Agrawal, R. and R. Srikant, 1994, "Fast algorithms for mining association rules", in Proc. 20th int. conf. very large data bases, VLDB, vol. 1215, pp. 487-499, Citeseer.
[45]Dai, W. and W. Ji, 2014, "A mapreduce implementation of C4.5 decision tree algorithm", International journal of database theory application, vol. 7, no. 1, pp. 49-60.
[46]Mu, Y., X. Liu, Z. Yang and X. Liu, 2017, "A parallel C4. 5 decision tree algorithm based on MapReduce", Concurrency and Computation: Practice and Experience, vol. 29, no. 8, pp. e4015.
[47]Koli, A. and S. Shinde, 2017, "Parallel decision tree with map reduce model for big data analytics", in 2017 International Conference on Trends in Electronics and Informatics (ICEI), pp. 735-739, IEEE.
[48]Wu, G., H. Li, X. Hu, Y. Bi, J. Zhang, and X. Wu, 2009, "MReC4. 5: C4. 5 ensemble classification with MapReduce", in 2009 fourth ChinaGrid annual conference, pp. 249-255, IEEE.
[49]Huang, P.-Y., W.-S. Cheng, J.-C. Chen, W.-Y. Chung, Y.-L. Chen and K. W. J. I. A. Lin, 2021, "A distributed method for fast mining frequent patterns from big data", IEEE Access, vol. 9, pp. 135144-135159.
[50]陳永霖，2016，於分散式環境下探勘巨大資料庫之高效性頻繁樣式演算法, 國立高雄科技大學，碩士論文。
[51]Zaki, M. J., 2016, “IBM Generator: IBM Synthetic Data Generator for Itemsets and Sequences,” Github, Oct, https://github.com/zakimjz/IBMGenerator (accessed Jul. 21, 2021).
[52]Goethals, B., 2019, “Frequent Itemset Mining Dataset Repository,” FIMI Workshop Committee, Jan. http://fimi.uantwerpen.be/data/ (accessed Jul. 21, 2021)
[53]黃正宇，2021，高效性分散式C4.5決策樹演算法之研究，國立高雄科技大學，碩士論文。
[54]"Scikit-learn, Machine learning in Python " [Online]. Available: https://scikit-learn.org/stable/