Mining of Interesting Prediction Rules with Uniform Two-Level Genetic Algorithm

Authors: Bilal Alatas, Ahmet Arslan

Abstract:

The main goal of data mining is to extract accurate, comprehensible and interesting knowledge from databases that may be considered as large search spaces. In this paper, a new, efficient type of Genetic Algorithm (GA) called uniform two-level GA is proposed as a search strategy to discover truly interesting, high-level prediction rules, a difficult problem and relatively little researched, rather than discovering classification knowledge as usual in the literatures. The proposed method uses the advantage of uniform population method and addresses the task of generalized rule induction that can be regarded as a generalization of the task of classification. Although the task of generalized rule induction requires a lot of computations, which is usually not satisfied with the normal algorithms, it was demonstrated that this method increased the performance of GAs and rapidly found interesting rules.

Keywords: Classification rule mining, data mining, genetic algorithms.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1070347

References:

[1] B. Padmanabhan and A. A. Tuzhilin, "Belief-driven method for discovering unexpected patterns", in Proc. KDD98 4th International Conference on Knowledge Discovery and Data Mining, AAAI Press, 1998.
[2] M. Klemettinen, H. Mannila, P. Ronkainen, H. Toivonen, and A. I. Verkamo, "Finding interesting rules from large sets of discovered association rules", in N. R. Adam, B. K. Bhargava and Y. Yesha (eds), Proc. 3rd International Conference on Information and Knowledge Management, ACM Press, pp. 401-407, 1994.
[3] A. Silbershatz and A. Tuzhilin, "What makes patterns interesting in knowledge discovery systems", IEEE Transactions on Knowledge and Data Engineering, 8(6), pp. 970-974, 1996.
[4] A. Silbershatz and A. Tuzhilin, "On subjective measures of interestingness in knowledge discovery", in U. M. Fayyad and R. Uthurusamy (eds), KDD95: Proc. 1rst International Conference on Knowledge Discovery and Data Mining, AAAI Press, pp. 275-281, 1995.
[5] B. Liu, W. Hsu, and S. Chen, "Using general impressions to analyse discovered classification rules", in Proc. KDD97 3rd International Conference on Knowledge Discovery and Data Mining, AAAI Press, pp. 31- 36, 1997.
[6] B. Padmanabhan and A. Tuzhilin, "A belief-driven method for discovering unexpected patterns", in Proc. KDD98 4th International Conference on Knowledge Discovery and Data Mining, AAAI Press, 1998.
[7] C. J. G. Piatetsky-hapiro and D. McNeill, "Selecting and reporting what is interesting", in U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth and R. Uthurusamy (eds), Advances in Knowledge Discovery and Data Mining, AAAI Press, pp. 465-515, 1996.
[8] E. Noda, A.A. Freitas, and H. S. Lopes, "Discovering interesting prediction rules with a genetic algorithm", in Proc. Congress on Evolutionary Computation (CEC-99), 1322-1329, Washington D.C., USA, 1999.
[9] E. Suzuki and Y. Kodratoff, "Discovery of surprising exception rules based on intensity of implication", in Proc. 2nd European Symposium on Principles of Data Mining and Knowledge Discovery (PKDD-98), Lecture Notes in Artificial Intelligence, 1510, pp. 10-18, 1998.
[10] A. A. Freitas, "On objective measures of rule surprisingness", in Proc. 2nd European Symposium on Principles of Data Mining and Knowledge Discovery (PKDD-98), Lecture Notes in Artificial Intelligence, 1510, pp.1-9, 1998.
[11] A. Karcı and A. Çınar, "Comparison of uniform distributed initial population method and random initial population method in genetic search", in Proc. 15th International Symposium on Computer and Information Sciences, pp. 159-166, Istanbul / Turkey, 2000.
[12] A. Karc─▒ and A. Arslan, "Uniform population in genetic algorithms", Journal of Electrical and Electronics, Istanbul Unv, pp. 495-504, vol:2, no:2. 2002.
[13] J. Han and M. Kamber, "Data mining: concepts and techniques", Morgan Kaufmann Publishers, 2001.
[14] K. K. Gündoğan, B. Alataş, A. Karci, Y. Tatar, "Comprehensible classification rule mining with two-level genetic algorithm", in Proc. 2nd FAE International Symposium, pp. 373-377, Cyprus, 2002.
[15] A. A. Freitas, "A genetic algorithm for generalized rule induction", In: R. Roy et al. Advances in Soft Computing - Engineering Design and Manufacturing, 340-353, (Proc. WSC3, 3rd On-Line World Conference on Soft Computing, hosted on the Internet) Springer-Verlag, 1999.
[16] M. Bohanec, V. Rajkovic, "Expert system for decision making", Sistemica 1(1), pp. 145-157, 1990.