臺灣博碩士論文加值系統

本研究根據知識發現流程(KDD) 及 Apriori 演算法提出我們的挖掘程序，同時以布林表格為資料結構。 以布林表格為基礎僅需在 Apriori 演算法之第一回合時掃描資料庫(讀取資料至布林表格)，其餘回合再以布林表格為資料來源，故可節省掃描資料庫的時間。在挖掘程序中本研究只須運用兩個功能：
(1) 產生候選項目集(Candidate Itemsets) 及依 Apriori 定理作修剪。
(2) 將產生的高頻項目集( Frequent Itemsets)由多筆轉為單筆，供產生下回合之 候選項目集(Candidte itemsets) 使用。
我們將本研究所提的方法與其它演算法進行時間及空間上的效能比較，發現本研究方法有不錯的表現。

The thesis proposed an association rules mining algorithm based on KDD (Knowledge discovery in Database) methodology and Apriority algorithm scanning the full database for every pass during its mining process. The proposed algorithm scanned transactions in database only in the first pass and converted them into Boolean Table data structure used for subsequent processing. No further scanning was needed afterwards and hence I/O time was reduced substantially. Two key processes of the proposed algorithm were:(1) Generate candidate item sets and prune them by Apriori principle.(2) Convert and combine multiple records of frequent item sets into single record o generate new candidate item sets in the next pass.
The performance of the proposed algorithm was compared to other related algorithms in terms of time and space and results were discussed in details.

中文提要 …………………………………………………………………… i
英文提要 …………………………………………………………………… ii
誌謝 …………………………………………………………………… iii
目錄 …………………………………………………………………… iv
表目錄 …………………………………………………………………… vi
圖目錄 …………………………………………………………………… vii
第一章 緒論……………………………………………………………… 1
1.1 料挖掘概述……………………………………………………… 1
1.1.1 資料挖掘(Data Mining)定義…………………………………… 2
1.1.2 資料挖掘技術…………………………………………………… 3
1.1.3 資料挖掘限制…………………………………………………… 9
1.1.4 資料挖掘未來挑戰……………………………………………… 10
1.2 研究動機與目的………………………………………………… 10
1.3 論文架構………………………………………………………… 11
第二章 文獻探討………………………………………………………… 12
2.1 關聯法則(Association Rule)探討………………………………… 12
2.1.1 關聯法則的意義………………………………………………… 12
2.1.2 關聯法則之相關名詞…………………………………………… 13
2.1.3 關聯法則之推導………………………………………………… 13
2.1.4 關聯法則之探討………………………………………………… 15
2.1.5 關聯法則之相關應用…………………………………………… 16
2.2 Apriori 演算法探討……………………………………………… 18
2.2.1 演算法…………………………………………………………… 18
2.2.2 演算法的改良: AprioriTid……………………………………… 24
2.3 DHP(Direct Hashing and Pruning) 演算法探討………………… 27
2.4 DLG演算法探討………………………………………………… 29
2.5 Boolean Algorithm 探討………………………………………… 32
2.6 網路選課資料挖掘探討………………………………………… 37
第三章 研究方法………………………………………………………… 38
3.1 研究構想………………………………………………………… 38
3.2 研究步驟及方法………………………………………………… 39
第四章 實驗及結果分析………………………………………………… 45
4.1 實驗設備及資料說明…………………………………………… 45
4.1.1 實驗設備………………………………………………………… 45
4.1.2 資料格式………………………………………………………… 45
4.2 實驗過程………………………………………………………… 50
4.3 討論……………………………………………………………… 57
第五章 結論與未來研究………………………………………………… 63
5.1 結論……………………………………………………………… 63
5.2 未來研究方向.…………………………………………………… 64
參考文獻 …………………………………………………………………… 66
附錄一 …………………………………………………………………… 73

[1] Zhi-Hua Zhou,"Three perspectives of data mining (book review)", Artificial Intelligence,143(1),pp. 139–146, January 2003.
[2] Chris Clifton and Bhavani Thuraisingham,"Emerging Standards for Data Mining", Computer Standards and Interfaces ,23(3), pp. 187–193, July 2001.
[3] D.M. Amidon, "Blueprint for 21st century innovation management", Journal of Knowledge Management ,2(1), pp. 23–31 ,1998.
[4] H. Holtz, Databased Marketing — Every Manager’s Guide to the Super Marketing Tool of the 21st Century, Wiley, New York, 1992.
[5] M.C. Rumizen, "Report on the second comparative study of knowledge creation conference", Journal of Knowledge Management ,2(1), pp.77–82, September 1998.
[6] J.R. Quinlan, C4.5: Programs for Machine Learning, Morgan Kaufmann, San Mateo, CA, 1993.
[7] L. Breiman, et al. , Classification and Regression Trees, Chapman &. Hall (Wadsworth, Inc.), New York, 1984.
[8] Michael J. A. Berry, and G. Linoff, Data Mining Techniques: For Marketing,Sales, and Customer Support , John Wiley & Sons, Inc., New York, 1997.
[9] Hosking,et al. ,"A statistical perspective on data mining", Future Generation Computer Systems, 13(2-3), pp. 117-134, November 1997.
[10] M. C. Lovell,"Data Mining" , The Review of Economics and Statistics , LXV(1), pp. 1–12, February 1983.
[11] M. Holsheimer, and A.P.J.M. Siebes, Data Mining: the search for knowledge in databases, CWI (Centre for Mathematics and Computer Science), Amsterdam, 1994.
[12] U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy (Eds.), Advances in Knowledge Discovery and Data Mining, MIT Press, Menlo Park, CA, 1996.
[13] J. Han and M. Kamber, Data Mining : Concepts and Techniques,Morgan Kaufmann Pub,San Francisco,2000.
[14] D. Hand, H. Mannila, and P. Smyth, Principles of Data Mining ,MIT Press, Cambridge, CA, 2001.
[15] I.H. Witten, and E. Frank, Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann, San Francisco, CA, 2000.
[16] H. A. Edelstein, Introduction to data mining and knowledge discovery (3rd ed) , Two Crows Corp.,Potomac, MD,1999.
[17] http://www.moneydj.com/z/glossary/glexp_4670.asp.htm
[18] http://www.uniminer.com/center01.htm
[19] M. J. Shaw, C. Subramaniam, G. W. Tan, and M. E. Welge, "Knowledge Management and Data Mining for Marketing", Decision Support Systems, 31(1), pp.127-137, May 2001.
[20] J.R. Quilan, "Induction of decision trees", Machine Learning, 1,pp. 81-106, November 1986.
[21] K. Alsabti, S. Ranka, and V. Singh, "An Efficient K-Means Clustering Algorithm", PPS/SPDP Workshop on High performance Data Mining, pp. 34-39,March 1998.
[22] L. Kaufman and P. J. Rousseuw, Finding Groups in Data: an Introduction to Cluster Analysis , John Wiley & Sons, NY, 1990.
[23] R. T. Ng and J. Han, "Efficient and Effective Clustering Methods for Spatial Data Mining", Proc. of the 20th Int’l Conf. on Very Large Databases, pp. 144-155, Santiago, Chile, 1994.
[24] W.S. McCulloch and W. Pitts, "Artificial Neural Network",Bull. Math. Biophys ,5, pp.115-133. 1943.
[25] D. Hebb, The Organization of Behavior, John Wiley, New York,1949.
[26] P. J. Werbos, "Backpropagation and neurocontrol:A review and prospectus" IJCNN,1,pp. 209-216, March 1989.
[27] RP. Li, ZO. Wang, "Mining classification rules using rough sets and neural networks", EUROPEAN JOURNAL OF OPERATIONAL RESEARCH ,157 (2), pp.439-448,September 2004.
[28] H. Lu, R. Setiono, H. Liu,"Effective data mining using neural networks", IEEE Transactions on Knowledge and Data Engineering ,8(6),pp. 957–961, December 1996.
[29] M. Craven, J. Shavlik, "Using neural networks for data mining", Future Generation Computer Systems ,13(2-3),pp. 211–229, October 1997.
[30] J. H Holland, "Outline for A Logical Theory of Adaptive Systems", Journal of the Association for Computing Machinery, 9(3),pp. 297-314, July 1962.
[31] D. A. Koonce, and S.-C. Tsai, "Using Data Mining to Find Patterns in Genetic Algorithm Solutions to a Job Shop Schedule",Computers & Industrial Engineering, 38, pp.361-374,2000.
[32] K.F. Man,K.S. Tang,and S. Kwong,"Genetic Algorithms:Concepts and Applications",IEEE Transactions on Industrial Electronic,43(5),pp.519-533, 1996.
[33] P.D. Scott, and E. Wilkins, "Evaluating data mining procedures: Techniques for generating artificial data sets", Information and Software Technology , 41,pp.579-587, 1999.
[34] W.Seifert Jeffrey, "Data Mining and the Search for Security:Challenges for Conneting the Dots and Databases", Government Information Quarterly, 21( 4), pp.461‐480,2004.
[35] J. M. Donato, J. C. Schryver, Gregory C. Hinkel, Richard L. Schmoyer, Jr., Micheal R. Leuze, and Nancy W. Grandy, "Mining multi-dimensional data for decision support", Future Generation Computer Systems, 15(3),pp. 433-441, 1999.
[36] A.J. Feelders, H.A.M. Daniels and M. Holsheimer," Methodological and practical aspects of data mining", Information & Management ,37(5), pp. 271-281, 2000.
[37] Wai-Ho Au, and Keith C.C. Chan, "Mining changes in association rules: a fuzzy approach", Fuzzy Sets and Systems ,149(1), pp. 87-104,January 2005.
[38] F. Crespo, R. Weber," A methodology for dynamic data mining based on fuzzy clustering", Fuzzy Sets and Systems ,150(2), pp.267-284,2005.
[39] F. Masseglia, P. Poncelet, and M. Teisseire," Incremental Mining of Sequential Patterns in Large Databases", Data and Knowledge Eng., 46(1), pp. 97-121, July 2003.
[40] U. Fayyad, D. Madigan, G. Piatetsky-Shapiro,and P. Smyth, "From data mining to knowledge discovery in databases", AI Magazine ,17(3), pp. 37-54 ,1996.
[41] E. Yilmaz, E. Triantaphyllou, J. Chen, and TW Liao, "Heuristic for Mining Association Rules In Polynomial Time" ,Computer and Mathematical Modelling,37,pp. 219-233,2003.
[42] Ji-Han Jiang, Chin-Chen Chang, and Tung-Shou Chen, "A Compact Sparse Matrix Representation Using Random Hash Functions", Data & Knowledge Engineering, 32, pp. 29-49, 2000.
[43] T. Calders, and J. Paredaens, "Axiomatization of frequent sets", In Proceedings of the 8th International Conference on Database Theory , pp. 204-218 , London, UK, January 2001.
[44] Mitsunori Ogihara,"Data Mining for Studying Large Databases", Xerox, Webster, NY, February 12, 2004.
[45] A. Kitada, T. Murai and Y. Sato, "A Data Structure for Dynamic Data Mining", Third International Conference. on. Knowledge-Based Intelligent Information Engineeing Systems, pp. 530 -533, Adelaide, Australia ,September 1999.
[46]呂永和，賴瓊惠，劉佳灝，吳素英，「以布林演算基礎的多階層序列型樣探勘技術」，第七屆人工智慧與應用研討會(TAAI2002)，p279，朝陽科技大學，臺灣，民國91年11月15日。
[47]李建億，潘冠良，吳政道，「運用矩陣運算策略來提昇關聯法則探勘效能之研究」，2001中華民國第九屆模糊理論及其應用會議，國立中央大學，臺灣，民國90年11月23-24日。
[48]何俊輝，蔡崇煒，楊竹星，莊嘉育，「應用資料採礦及演化式計算概念於數位學習路徑分析」，第三屆數位典藏技術研討會，中央研究院資訊科學研究所，臺灣，民國93年8月5-6日。
[49]陳銘宗，「組合式關聯法則應用於缺值問題之研究」，朝陽科技大學，碩士論文，民國92年。
[50]馬南超，「一種三向度時間序列資料處理模型」，私立中原大學，碩士論文，民國92年。
[51]陳垂呈，「應用布林運算快速分群化交易項目」，台灣區域網際網路研討會,嘉義中正大學，民國90年10月24-26日。
[52]蔡旻璇，「序列樣式分析應用於課程規劃支援系統」，靜宜大學，碩士論文，民國91年。
[53]顏博文，「應用資料探勘技術分析學生選課特性與學業表現」，中原大學，碩士論文，民國92年。
[54]謝育勳，「員工知識管理資訊系統之設計與發展—資料採擷技術之應用」，國立中央大學，碩士論文，民國89年。
[55]楊淦淼，「設計建立在多層式服務架構上的資料挖掘系統—以學生課程管理為例」，逢甲大學，碩士論文，民國91年。
[56]楊琇媛，「利用資料倉儲與資料探勘技術於招生筞略與學生特質分析之研究」，中原大學，碩士論文，民國91年。
[57]邱永祥，「運用類神經網路與資料探勘技術於網路教學課程推薦之研究」，朝陽科技大學，碩士論文，民國92年。
[58]何達明，「排序對關聯演算法速度的影響」，中原大學，碩士論文，民國9１年。
[59]沈明賢，「差異性顯示對關聯法則使用之評估」，元智大學，碩士論文，民國90年。
[60]陸津華，「挖掘高獲利性關聯規則之研究」，東海大學，碩士論文，民國92年。
[61]武家慶，「適用於挖掘多層次聯結規則的架構」，逢甲大學，碩士論文，民國90年。
[62]楊文昇，「有效率的挖掘關聯法則之高頻物項集合演算法」，逢甲大學碩士論文，民國90年。
[63]許振華，「從限定項目個數及交易長度的資料中有效地找出關聯規則之研究」，逢甲大學，碩士論文，民國91年。
[64]陳銘宗，「組合式關聯法則應用於缺值問題之研究」，朝陽科技大學，碩士論文，民國92年。
[65]李文傑，「企業知識發掘架構透過資料庫關聯規則探勘」，朝陽科技大學，碩士論文，民國92年。
[66]楊昇宏，「資料挖掘應用於找尋瀏覽網頁之型樣」，逢甲大學，碩士論文，民國89年。
[67] R. Agrawal, T. Imielinski and A. Swami, "Mining Association Rules between Sets of Items in Large Database", Proc. of the ACM SIGMOD Int''l Conf. on Management of Data, pp. 207-216, New York, May 1993.
[68] R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association Rules in Large Databases", Proc. of the 20th International Conference on Very Large Database, pp. 487-499, Santiago, Chile, September 1994.
[69] Jong Soo Park, Ming-Syan Chen, and Philip S. Yu, "Using a Hash-Based Method with Transaction Trimming and Database Scan Reduction for Mining Association Rules", IEEE Trans. On Knowledge and Data Engineering, 95, pp. 813-825, October 1997.
[70] S.J. Yen and Arbee L.P. Chen, "An Efficient Approach to Discovering Knowledge from Large Databases", In Proc. of 4th Int. Conf. on Parallel and Distributed Information Systems, pp. 8-18, Miami Beach, Florida, USA, December 1996.
[71] S.Y. Wur and Y. Leu, "An Effective Boolean Algorithm for Mining Association Rules in Large Databases", Proc. of the 6th Int. Conf. on Database Systems for Advanced Applications, pp. 179-186, Hsinchu, Taiwan,April 1999.
[72] Weiyang Lin, "Association Rule Mining for Collaborative Recommender Systems", WORCESTER POLYTECHNIC INSTITUTE, Thesis of Master, May 2000。
[73] A. Savasere, E. Omiecinski and S. Navathe. "An Efficient Algorithm for Mining Association Rules in Large Databases", Proceedings of the 21st International Conference on Very Large Databases, pp. 432-444, Zurich, Switzerland , September 1995.
[74] B. Lent, A. Swami and J. Widom. "Clustering Association Rules", Proceedings of the 13th International Conference on Data Engineering. pp. 220-231, Birmingham, UK ,April 1997.
[75] J.S. Park, M.S. Chen, and P.S. Yu. "An Effective Hash Based Algorithm for Mining Association Rules ", Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, pp. 175-186, San Jose, California, May 1995.
[76] Jun-Lin Lin and Margaret H. Dunham. "Mining Association Rules: Anti-Skew Algorithms",Proc. of 1998 Int''l Conf. on Data Engineering, pp. 486-493, Orlando, Florida, USA, February 1998.
[77] M.J. Zaki, "Scalable algorithms for association mining,", IEEE Transactions on Knowledge and Data Engineering, 12(3),pp. 372 -390 , May-June 2000.
[78] A.B. Tickle, R. Andrews, M. Golea, and J. Diederich, "The truth will come to light: Directions and challenges in extracting the knowledge embedded within trained artificial neural networks", IEEE Trans. Neural Networks ,9 (6),pp.1057–1068, 1998.
[79] I. Geist,"A Framework for Data Mining and KDD" ,In: The 2002 ACM SIGAPP Symposium on Applied Computing (SAC), pp. 508 – 513,Madrid, Spain, March 2002.
[80] U. Fayyad, G. Piatetsky-Shapiro, P. Smyth ,"The KDD process for extracting useful knowledge from volumes of data", Commun ACM , 39(11), pp.27–41, November 1996.
[81] C. Glymour, D. Madigan, D. Pregibon, and P. Smyth, "Statistical themes and lessons for data mining", Data Mining and Knowledge Discovery ,1(1), pp. 11-28, 1997.
[82] M. Holsheimer, A. Siebes, "Data Mining: The Search for Knowledge in Databases, Technical Report", CS-R9406, CWI, 1994.
[83] W . Frawley, G . Piatetsky-Shapiro, and C. Matheus," Knowledge discovery in databases: an overview", AAAI/MIT Press, pp.1-30, Menlo Park, CA, 1991.