An Evolutionary Method for Associative Contrast Rule Mining from Incomplete Database

Kaoru Shimada; Takashi Hanioka

doi:10.20965/jaciii.2015.p0766

single-jc.php

JACIII Vol.19 No.6 pp. 766-777

doi: 10.20965/jaciii.2015.p0766

(2015)

Paper:

Views over last 60 days: 292

An Evolutionary Method for Associative Contrast Rule Mining from Incomplete Database

Kaoru Shimada and Takashi Hanioka

Fukuoka Dental College
2-15-1 Tamura, Sawara-ku, Fukuoka 814-0193, Japan

Received:

December 19, 2014

Accepted:

August 18, 2015

Online released:

November 20, 2015

Published:

November 20, 2015

Keywords:

association rule, data mining, evolutionary computation, incomplete database, missing value

Abstract

We propose a method for associative contrast rule mining from an incomplete database to find interesting differences between two incomplete datasets. The associative contrast rule is defined as follows: although an association rule “if X then Y” satisfies the given importance conditions within Database A, the same rule does not satisfy the same conditions within Database B. The proposed method extracts associative contrast rules directly without generating the frequent itemsets used in conventional rule mining methods. We developed our message using the basic evolutionary graph-based optimization basic structure and a new evolutionary strategy for rule accumulation mechanism. The method realizes association analysis between two classes of an incomplete database using the chi-square test. We evaluated the performance of the method for associative contrast rule mining from the incomplete database. Experimental results showed that our proposed method extracts associative contrast rules effectively. Evaluations of the mischief for rule measurements by missing values are demonstrated. Simulation results showed the difference between using the proposed method for an incomplete database and using the database as complete.

Full Text (0.6MB)

Would you consider donation?

References

[1] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” Proc. of the 20^th VLDB Conf., pp. 487-499, 1994.
[2] J. Han, J. Pei, Y. Yin and R. Mao, “Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach,” Data Mining and Knowledge Discovery, Vol.8, pp. 53-87, 2004.
[3] X. Wu, C. Zhang and S. Zhang, “Efficient Mining of Both Positive and Negative Association Rules,” ACM Trans. on Information Systems, Vol.22, No.3, pp. 381-405, 2004.
[4] A. K. H. Tung, H. Lu, J. Han and L. Feng, “Efficient Mining of Intertransaction Association Rules,” IEEE Trans. on Knowledge and Data Engineering Vol.15, No.1, pp. 43-56, 2003.
[5] K. Shimada and K. Hirasawa, “Exceptional Association Rule Mining Using Genetic Network Programming,” Proc. of the 4^th Int. Conf. on Data Mining (DMIN), pp. 277-283, 2008.
[6] K. Shimada and T. Hanioka, “An Evolutionary Associative Contrast Rule Mining Method for Incomplete Database,” Proc. of the Int. Conf. on Data Mining (DMIN), pp. 160-166, 2013.
[7] J. W. Grzymala-Busse and W. J. Grzymala-Busse, “Handling Missing Attribute Values,” Data Mining and Knowledge Discovery Handbook (2^nd ed.), O. Maimon, L. Rockach (eds.), Springer, pp. 33-51, 2010.
[8] M. Saar-Tsechansky and F. Provost, “Handling Missing Values when Applying Classification Models,” J. of Machine Learning Research, Vol.8, pp. 1625-1657, 2007.
[9] K. Shimada and K. Hirasawa, “A Method of Association Rule Analysis for Incomplete Database Using Genetic Network Programming,” Proc. of the Genetic and Evolutionary Computation Conf. (GECCO 2010), pp. 1115-1122, 2010.
[10] K. Shimada, “An Evolving Associative Classifier for Incomplete Database,” Lecture Notes in Artificial Intelligence, Vol.7377: Advances in Data Mining, Perner P.(Ed.), Springer, pp. 136-150, 2012.
[11] K. Shimada and T. Hanioka, “An Evolutionary Method for Exceptional Association Rule Set Discovery from Incomplete Database,” Proc. of Int. Conf. on Information Technology in Bio- and Medical Informatics (ITBAM), Lecture Notes in Computer Science, Vol.8649, M. Bursa et al. (Eds.), Springer, pp. 133-147, 2014.
[12] S. Mabu, C. Chen, N. Lu, K. Shimada, and K. Hirasawa, “An Intrusion-Detection Model Based on Fuzzy Class-Association-Rule Mining Using Genetic Network Programming,” IEEE Trans. on Systems, Man, and Cybernetics – Part C –, Vol.41, pp. 130-139, 2011.
[13] S. Mabu, K. Hirasawa, and J. Hu, “A Graph-Based Evolutionary Algorithm: Genetic Network Programming (GNP) and Its Extension Using Reinforcement Learning,” Evolutionary Computation, Vol.15, No.3, pp. 369-398, 2007.
[14] A. A. Freitas, “Data Mining and knowledge Discovery with Evolutionary Algorithms,” Springer, New York, 2002.
[15] A. Ghosh and L. C. Jain, “Evolutionary Computing in Data Mining,” Springer, Heidelberg, 2005.
[16] K. Shimada, K. Hirasawa and J. Hu, “Genetic Network Programming with Acquisition Mechanisms of Association Rules,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.10, No.1, pp. 102-111, 2006.
[17] S. Brin, R. Motwani, and C. Silverstein, “Beyond market baskets: generalizing association rules to correlations,” Proc. of ACM SIGMOD, pp. 265-276, 1997.

[1] [1] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” Proc. of the 20^th VLDB Conf., pp. 487-499, 1994.

[2] [2] J. Han, J. Pei, Y. Yin and R. Mao, “Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach,” Data Mining and Knowledge Discovery, Vol.8, pp. 53-87, 2004.

[3] [3] X. Wu, C. Zhang and S. Zhang, “Efficient Mining of Both Positive and Negative Association Rules,” ACM Trans. on Information Systems, Vol.22, No.3, pp. 381-405, 2004.

[4] [4] A. K. H. Tung, H. Lu, J. Han and L. Feng, “Efficient Mining of Intertransaction Association Rules,” IEEE Trans. on Knowledge and Data Engineering Vol.15, No.1, pp. 43-56, 2003.

[5] [5] K. Shimada and K. Hirasawa, “Exceptional Association Rule Mining Using Genetic Network Programming,” Proc. of the 4^th Int. Conf. on Data Mining (DMIN), pp. 277-283, 2008.

[6] [6] K. Shimada and T. Hanioka, “An Evolutionary Associative Contrast Rule Mining Method for Incomplete Database,” Proc. of the Int. Conf. on Data Mining (DMIN), pp. 160-166, 2013.

[7] [7] J. W. Grzymala-Busse and W. J. Grzymala-Busse, “Handling Missing Attribute Values,” Data Mining and Knowledge Discovery Handbook (2^nd ed.), O. Maimon, L. Rockach (eds.), Springer, pp. 33-51, 2010.

[8] [8] M. Saar-Tsechansky and F. Provost, “Handling Missing Values when Applying Classification Models,” J. of Machine Learning Research, Vol.8, pp. 1625-1657, 2007.

[9] [9] K. Shimada and K. Hirasawa, “A Method of Association Rule Analysis for Incomplete Database Using Genetic Network Programming,” Proc. of the Genetic and Evolutionary Computation Conf. (GECCO 2010), pp. 1115-1122, 2010.

[10] [10] K. Shimada, “An Evolving Associative Classifier for Incomplete Database,” Lecture Notes in Artificial Intelligence, Vol.7377: Advances in Data Mining, Perner P.(Ed.), Springer, pp. 136-150, 2012.

[11] [11] K. Shimada and T. Hanioka, “An Evolutionary Method for Exceptional Association Rule Set Discovery from Incomplete Database,” Proc. of Int. Conf. on Information Technology in Bio- and Medical Informatics (ITBAM), Lecture Notes in Computer Science, Vol.8649, M. Bursa et al. (Eds.), Springer, pp. 133-147, 2014.

[12] [12] S. Mabu, C. Chen, N. Lu, K. Shimada, and K. Hirasawa, “An Intrusion-Detection Model Based on Fuzzy Class-Association-Rule Mining Using Genetic Network Programming,” IEEE Trans. on Systems, Man, and Cybernetics – Part C –, Vol.41, pp. 130-139, 2011.

[13] [13] S. Mabu, K. Hirasawa, and J. Hu, “A Graph-Based Evolutionary Algorithm: Genetic Network Programming (GNP) and Its Extension Using Reinforcement Learning,” Evolutionary Computation, Vol.15, No.3, pp. 369-398, 2007.

[14] [14] A. A. Freitas, “Data Mining and knowledge Discovery with Evolutionary Algorithms,” Springer, New York, 2002.

[15] [15] A. Ghosh and L. C. Jain, “Evolutionary Computing in Data Mining,” Springer, Heidelberg, 2005.

[16] [16] K. Shimada, K. Hirasawa and J. Hu, “Genetic Network Programming with Acquisition Mechanisms of Association Rules,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.10, No.1, pp. 102-111, 2006.

[17] [17] S. Brin, R. Motwani, and C. Silverstein, “Beyond market baskets: generalizing association rules to correlations,” Proc. of ACM SIGMOD, pp. 265-276, 1997.