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

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.

• Bilal Alatas
• Ahmet Arslan

• Classification rule mining
• data mining
• genetic algorithms.

[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.