臺灣博碩士論文加值系統

由交易資料庫中發掘關聯式規則能萃取出所需的知識或感興趣的式樣，目前大部份的方法多是將項目或項目集的最小支持度門檻值設定為單一值。然而，在現實世界的應用中，不同項目的重要性可能必須要有不同條件來評斷。而在不同情形下，各項目集的最小支持度需求也應該有不同的設定。在本論文中，在項目具不同最小支持度時，我們從另一個觀點定義項目集支持度限並制發展出數個有效的探勘方法。我們採用最大支持度限制將一個項目集的最小支持度設定為該項目集所包含項目的最小支持度之最大值並提出了一個基於最大支持度限制的演算法來找出關聯規則。另外，物件項目在現實生活的應用中可能會具有階層性的關係。對於較高階層的項目我們採用最小階層支持度限制，也就是一個在較高階層項目的最小支持度設定為屬於該項目的最小支持度之最小值。我們提出了在多重最小支持下探勘多階層關聯規則以及探勘泛化型關聯規則的兩個演算法。此外，由於交易資料在現實世界中常具有數量。為了處理這類問題，我們於是運用模糊集合理論在所提出的方法上，由數值型的項目資料中來探勘具多重最小支持度的語意型關聯規則。基於所提出的最小支持度限制，我們提出了探勘模糊關聯規則與探勘多階層模糊關聯規則的兩個演算法。我們也做了一些實驗比較了所提出的演算法與一些相關的現存方法，從實驗結果顯示我們所提出的演算法之可行性。最後，我們也討論了關於應用位元字串技術來加速所提出的探勘演算法，及採用以基因演算法為基礎的模糊探勘架構來萃取出一組合適的隸屬函數以及模糊關聯規則。

Discovery of association rules from transaction databases can be used to extract desirable knowledge or interesting patterns. Most of the previous approaches set a single minimum support threshold for all items or itemsets. In real applications, however, the requirements of minimum supports for itemsets may vary under different situations. In this thesis, we develop several efficient mining algorithms from another perspective when items have different minimum supports. We introduce the maximum support constraint for setting a minimum support of the itemset as the maximum of the minimum supports of the items contained in it. We then propose an algorithm to find association rules under the proposed maximum support constraints. In addition, items in real application domains may have taxonomic relationships. We then adopt the minimum-taxonomy support constraint for the higher concept-level items. That is, the minimum support for an item at a higher concept-level is set as the minimum of the minimum supports of the items belonging to it. Two algorithms are proposed for mining multiple-level association rules and mining generalized association rules under multiple minimum supports. Besides, the transaction data sets in real-world applications usually consist of quantitative values. To deal with that, we adopt the fuzzy set theory to the proposed algorithms for mining linguistic association rules from quantitative items with multiple minimum supports. We then propose two algorithms for mining fuzzy association rules and finding fuzzy multiple-level association rules based on the proposed support constraints. Experiments are also made to present a comparison of the proposed algorithms with some related approaches, and the results show the feasibility of the proposed algorithms. At last, some discussions about applying the granular computing technique of bit strings for speeding up the proposed mining algorithm and using the GA-based fuzzy mining structure for extracting both suitable membership functions and fuzzy association rules are also given.

摘要 I
ABSTRACT III
ACKNOWLEDGEMENTS V
CONTENTS VI
LIST OF FIGURES VIII
LIST OF TABLES IX
CHAPTER 1 INTRODUCTION 1
1.1 BACKGROUND AND MOTIVATION 1
1.2 CONTRIBUTIONS 7
1.3 THESIS ORGANIZATION 8
CHAPTER 2 LITERATURE SURVEY 10
2.1 MINING ASSOCIATION RULES WITH MULTIPLE MINIMUM SUPPORTS 10
2.2 MINING AT MULTIPLE CONCEPT-LEVELS 11
2.3 MINING ALGORITHMS FOR FUZZY ASSOCIATION RULES 15
CHAPTER 3 MINING ASSOCIATION RULES UNDER MULTIPLE MINIMUM-SUPPORTS 18
3.1 THE BASICS OF THE PROPOSED ALGORITHMS 19
3.2 MINING ASSOCIATION RULES WITH MULTIPLE MINIMUM SUPPORTS USING THE MAXIMUM CONSTRAINT 23
3.2.1 The proposed algorithm 24
3.2.2 An example 26
3.2.3 Experimental results 30
CHAPTER 4 MINING ASSOCIATION RULES WITH TAXONOMIC RELATIONSHIPS UNDER MULTIPLE MINIMUM- SUPPORTS 37
4.1 THE BASICS OF THE PROPOSED ALGORITHMS 37
4.2 THE MINING ALGORITHM FOR MULTIPLE-LEVEL ASSOCIATION RULES UNDER MULTIPLE MINIMUM-SUPPORTS 39
4.2.1 The proposed algorithm 41
4.2.2 An example 44
4.2.3 The modified algorithm for level-crossing mining 54
4.3 MINING GENERALIZED ASSOCIATION RULES UNDER THE MAXIMUM SUPPORT CONSTRAINTS 70
4.3.1 The proposed algorithm 71
4.3.2 An example 76
4.3.3 Experimental results 82
CHAPTER 5 MINING FUZZY ASSOCIATION RULES WITH MULTIPLE MINIMUM-SUPPORTS 88
5.1 MINING FUZZY ASSOCIATION RULES WITH MULTIPLE MINIMUM SUPPORTS USING MAXIMUM CONSTRAINTS 89
5.1.1 The proposed algorithm 90
5.1.2 An example 93
5.2 THE MINING ALGORITHM FOR FUZZY MULTIPLE-LEVEL ASSOCIATION RULES UNDER MULTIPLE MINIMUM SUPPORTS 101
5.2.1 The proposed algorithm 102
5.2.2 An example 107
CHAPTER 6 DISCUSSION AND CONCLUSION 122
6.1 SPEEDING UP BY GRANULAR COMPUTING 122
6.2 SPECIFICATION OF MEMBERSHIP FUNCTIONS FOR MINING FUZZY ASSOCIATION RULES 124
6.3 CONCLUSION AND FUTURE WORK 126
REFERENCES 129
PUBLICATION LIST 133

[1]R. Agrawal, T. Imielinksi and A. Swami, “Mining association rules between sets of items in large database,“ The ACM SIGMOD Conference, Washington DC, USA, 1993, pp. 207-216.
[2]R. Agrawal, T. Imielinksi and A. Swami, “Database mining: a performance perspective,” IEEE Transactions on Knowledge and Data Engineering, Vol. 5, No. 6, 1993, pp. 914-925.
[3]R. Agrawal and R. Srikant, “Fast algorithm for mining association rules,” The International Conference on Very Large Data Bases, 1994, pp. 487-499.
[4]R. Agrawal and R. Srikant, “Mining sequential patterns,” The Eleventh IEEE International Conference on Data Engineering, 1995, pp. 3-14.
[5]R. Agrawal, R. Srikant and Q. Vu, “Mining association rules with item constraints,” The Third International Conference on Knowledge Discovery in Databases and Data Mining, Newport Beach, California, 1997, pp. 67-73.
[6]A. F. Blishun, “Fuzzy learning models in expert systems,” Fuzzy Sets and Systems, Vol. 22, No. 1, 1987, pp. 57-70.
[7]L. M. de Campos and S. Moral, “Learning rules for a fuzzy inference model,” Fuzzy Sets and Systems, Vol. 59, 1993, pp. 247-257.
[8]C. C. Chan, and W.H. Au, “Mining fuzzy association rules,” Conference on Information and Knowledge Management, Las Vegas, 1997, pp. 209-215.
[9]R. L. P. Chang and T. Pavliddis, “Fuzzy decision tree algorithms,” IEEE Transactions on Systems, Man and Cybernetics, Vol. 7, 1977, pp. 28-35.
[10]C. Clair, C. Liu and N. Pissinou, “Attribute weighting: a method of applying domain knowledge in the decision tree process,” The Seventh International Conference on Information and Knowledge Management, 1998, pp. 259-266.
[11]P. Clark and T. Niblett, “The CN2 induction algorithm,” Machine Learning, Vol. 3, 1989, pp. 261-283.
[12]O. Cordón, F. Herrera, F. Hoffmann and L. Magdalena, “Evolutionary tuning and learning of fuzzy knowledge bases,” Genetic Fuzzy Systems, World Scientific, 2001.
[13]M. Delgado and A. Gonzalez, “An inductive learning procedure to identify fuzzy systems,” Fuzzy Sets and Systems, Vol. 55, 1993, pp. 121-132.
[14]W. J. Frawley, G, Piatetsky-Shapiro and C. J. Matheus, “Knowledge discovery in databases: an overview,” The AAAI Workshop on Knowledge Discovery in Databases, 1991, pp. 1-27.
[15]T. Fukuda, Y. Morimoto, S. Morishita and T. Tokuyama, “Mining optimized association rules for numeric attributes,” The ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1996, pp. 182-191.
[16]A.Gonzalez, “A learning methodology in uncertain and imprecise environments,” International Journal of Intelligent Systems, Vol. 10, 1995, pp. 57-371.
[17]I. Graham and P. L. Jones, Expert Systems-Knowledge, Uncertainty and Decision, Chapman and Computing, Boston, 1988, pp.117-158.
[18]J. Han and Y. Fu, “Discovery of multiple-level association rules from large database,” The Twenty-first International Conference on Very Large Data Bases, Zurich, Switzerland, 1995, pp. 420-431.
[19]T. P. Hong and C. Y. Lee, “Induction of fuzzy rules and membership functions from training examples,” Fuzzy Sets and Systems, Vol. 84, 1996, pp. 33-47.
[20]T. P. Hong, C. S. Kuo and S. C. Chi, “A data mining algorithm for transaction data with quantitative values,” The Eighth International Fuzzy Systems Association World Congress, 1999, pp. 874-878.
[21]T. P. Hong, C. S. Kuo and S. C. Chi, “Mining association rules from quantitative data”, Intelligent Data Analysis, Vol. 3, No. 5, 1999, pp. 363-376.
[22]T. P. Hong, C. S. Kuo and S. C. Chi, “Trade-off between computation time and number of rules for fuzzy mining from quantitative data,” International Journal of Uncertainty, Fuzziness and Knowledge-based Systems, Vol. 9, No. 5, 2001, pp. 587-604.
[23]T. P. Hong, M. J. Chiang and S. L. Wang, “Mining from quantitative data with linguistic minimum supports and confidences”, The Eleventh IEEE International Conference on Fuzzy Systems, 2002, pp. 494-499.
[24]T. P. Hong, K. Y. Lin and B. C. Chien, “Mining fuzzy multiple-level association rules from quantitative data,” Applied Intelligence, Vol. 18, No. 1, 2003, pp. 79-90.
[25]T. P. Hong, K. Y. Lin and S. L. Wang, “Fuzzy data mining for interesting generalized association rules,” Fuzzy Sets and Systems, Vol. 138, No. 2, 2003, pp. 255-269.
[26]T. P. Hong, C. H. Chen, Y. L. Wu and Y. C. Lee, “A GA-based fuzzy mining approach to achieve a trade-off between number of rules and suitability of membership functions”, Soft Computing, Vol. 10, No. 11, 2006, pp. 1091-1101.
[27]A. Kandel, Fuzzy Expert Systems, CRC Press, Boca Raton, 1992, pp. 8-19.
[28]M. Kaya, and R. Alhajj, “A clustering algorithm with genetically optimized membership functions for fuzzy association rules mining,” The IEEE International Conference on Fuzzy Systems, 2003, pp. 881 -886.
[29]M. Kaya and R. Alhajj, “Mining multi-cross-level fuzzy weighted association rules”, IEEE International Conference Intelligent Systems, Varna, Bulgaria, 2004, pp. 225-230.
[30]C. Kuok, A. Fu, and M. Wong, “Mining fuzzy association rules in databases,” SIGMOD Record, 1998, 27(1):41-46.
[31]T.Y. Lin, “Data mining: granular computing approach,” The Third Pacific-Asia Conference on Knowledge Discovery and Data Mining, Beijing, 1999, pp. 24-33.
[32]T.Y. Lin, “Data mining and machine oriented modeling: a granular computing approach,” Journal of Applied Intelligence, Vol. 13, No 2, 2000, pp. 113-124.
[33]T.Y. Lin and E. Louie, “Finding association rules by granular computing: fast algorithms for finding association rules,” in Data Mining, Rough Sets and Granular Computing, Physica-Verlag, 2002, pp. 23-42.
[34]B. Liu, W. Hsu, and Y. Ma, “Mining association rules with multiple minimum supports,” The 1999 International Conference on Knowledge Discovery and Data Mining, 1999, pp. 337-341.
[35]E. Louie and T.Y. Lin, “Finding association rules using fast bit computation: machine-oriented modeling,” Foundations of Intelligent Systems, Lecture Notes in Artificial Intelligence, Vol. 1932, Springer-Verlag, 2000, pp. 486-494.
[36]C. L. Lui and F. L. Chung, “Discovery of generalized association rules with multiple minimum supports,” in Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, Lecture Notes in Artificial Intelligence, Vol. 1910, 2000, pp. 510-515.
[37]E. H. Mamdani, “Applications of fuzzy algorithms for control of simple dynamic plants, “ IEEE Proceedings, 1974, pp. 1585-1588.
[38]H. Mannila, H. Toivonen, and A.I. Verkamo, “Efficient algorithm for discovering association rules,” The AAAI Workshop on Knowledge Discovery in Databases, 1994, pp. 181-192.
[39]J.S. Park, M.S. Chen, P.S. Yu, “Using a hash-based method with transaction trimming for mining association rules,” IEEE Transactions on Knowledge and Data Engineering, Vol. 9, No. 5, 1997, pp. 812-825.
[40]J. R. Quinlan, “Decision tree as probabilistic classifier,” The Fourth International Machine Learning Workshop, Morgan Kaufmann, San Mateo, CA, 1987, pp. 31-37.
[41]J. Rives, “FID3: fuzzy induction decision tree,” The First International symposium on Uncertainty, Modeling and Analysis, 1990, pp. 457-462.
[42]M. Setnes, H. Roubos, “GA-fuzzy modeling and classification: Complexity and performance,” IEEE Transaction on Fuzzy System, Vol. 8, No. 5, 2000, pp. 509-522.
[43]H. Shen, S. Wang and J.Yang, “Fuzzy taxonomic, quantitative database and mining generalized association rules,” Proceedings of 4th International Conference on Rough Sets and Current Trends in Computing, RSCTC 2004, Uppsala, Sweden, 2004, pp.610-617.
[44]R. Srikant and R. Agrawal, “Mining generalized association rules,” The Twenty-first International Conference on Very Large Data Bases, Zurich, Switzerland, 1995, pp. 407-419.
[45]R. Srikant and R. Agrawal, “Mining quantitative association rules in large relational tables,” The 1996 ACM SIGMOD International Conference on Management of Data, Monreal, Canada, June 1996, pp. 1-12.
[46]M. C. Tzeng and W. Y. Lin, “Mining generalized association rules with multiple minimum supports,” DaWaK 2001, Lecture Notes in Computer Science, Vol. 2114, 2001, pp. 11-20.
[47]C. H. Wang, T. P. Hong and S. S. Tseng, “Inductive learning from fuzzy examples,” The Fifth IEEE International Conference on Fuzzy Systems, New Orleans, 1996, pp. 13-18.
[48]C. H. Wang, T. P. Hong and S. S. Tseng, “Integrating fuzzy knowledge by genetic algorithms,” IEEE Transactions on Evolutionary Computation, Vol. 2, No.4, 1998, pp. 138-149.
[49]W. Wang and S. M. Bridges, “Genetic algorithm optimization of membership functions for mining fuzzy association rules,” The International Joint Conference on Information Systems, Fuzzy Theory and Technology, 2000, pp. 131-134.
[50]K. Wang, Y. H and J. Han, “Mining frequent itemsets using support constraints,” in Proceedings of the 26th International Conference on Very Large Data Bases, 2000, pp. 43-52.
[51]Q. Wei and G. Chen, “Mining generalized association rules with fuzzy taxonomic structures,” 18th International Conference of the North American Fuzzy Information Processing Society, NAFIPS, NY, USA, 1999, pp. 477-481.
[52]S. Yue, E. Tsand, D. Yeung, and D. Shi, “Mining fuzzy association rules with weighted items,” The IEEE International Conference on System, Man and Cybernetics, 2000, pp. 1906-1911.
[53]L. A. Zadeh, “Fuzzy sets,” Information and Control, Vol. 8, No. 3, 1965, pp. 338-353.
[54]L. A. Zadeh, “Fuzzy logic,” IEEE Computer, 1988, pp. 83-93.
[55]Z. Zheng, R. Kohavi and L. Mason, “Real world performance of association rules algorithms,” Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001, pp. 401-406.