×

A novel method for constrained class association rule mining. (English) Zbl 1390.68549

Summary: To create a classifier using an associative classification algorithm, a complete set of class association rules (CARs) is obtained from the training dataset. Most generated rules, however, are either redundant or insignificant. They not only confuse end users during decision-making but also decrease the performance of the classification process. Thus, it is necessary to eliminate redundant or unimportant rules as much as possible before they are used. A related problem is the discovery of interesting or useful rules. In existing classification systems, the set of such rules may not be discovered easily. However, in real world applications, end users often consider the rules with consequences that contain one of particular classes. For example, in cancer screening applications, researchers are very interested in rules that classify genes into the “cancer” class. This paper proposes a novel approach for mining relevant CARs that considers constraints on the rule consequent. A tree structure for storing frequent itemsets from the dataset is designed. Then, some theorems for pruning tree nodes that cannot generate rules satisfying the class constraints are provided and proved. Finally, an efficient algorithm for mining constrained CARs is presented. Experiments show that the proposed method is faster than existing methods.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
62H30 Classification and discrimination; cluster analysis (statistical aspects)

Software:

CMAR; CAR-Miner
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Abdelhamid, Neda; Ayesh, Aladdin; Thabtah, Fadi; Ahmadi, Samad; Hadi, Wael, MAC: a multiclass associative classification algorithm, J. Inf. Knowl. Manage., 11, 02, 1-10, (2012)
[2] Abdelhamid, Neda; Thabtah, Fadi; Ayesh, Aladdin, Associative classification approaches: review and comparison, J. Inf. Knowl. Manage., 13, 3, 1-30, (2014)
[3] Rakesh Agrawal, Tomasz Imieliński, Arun Swami, Mining association rules between sets of items in large databases, in: Paper Presented at the ACM SIGMOD Record, 1993.
[4] Rakesh Agrawal, Ramakrishnan Srikant, Fast algorithms for mining association rules in large databases, in: Paper Presented at the 20th International Conference on Very Large Data Bases, 1994.
[5] Baralis, Elena; Cagliero, Luca; Cerquitelli, Tania; Garza, Paolo, Generalized association rule mining with constraints, Inf. Sci., 194, 68-84, (2012)
[6] Cagliero, Luca; Garza, Paolo, Improving classification models with taxonomy information, Data Knowl. Eng., 86, 85-101, (2013) · Zbl 1355.68225
[7] Cagliero, Luca; Garza, Paolo, Itemset generalization with cardinality-based constraints, Inf. Sci., 224, 161-174, (2013) · Zbl 1355.68225
[8] Cai, Ruichu; Tung, Anthony; Zhang, Zhenjie; Hao, Zhifeng, What is unequal among the equals? ranking equivalent rules from gene expression data, IEEE Trans. Knowl. Data Eng., 23, 11, 1735-1747, (2011)
[9] Chen, Chun-Hao; Chiang, Rui-Dong; Lee, Cho-Ming; Chen, Chih-Yang, Improving the performance of association classifiers by rule prioritization, Knowl.-Based Syst., 36, 59-67, (2012)
[10] Chen, Fuzan; Wang, Yanlan; Li, Minqiang; Wu, Harris; Tian, Jin, Principal association mining: an efficient classification approach, Knowl.-Based Syst., 67, 16-25, (2014)
[11] Deng, Houtao; Runger, George; Tuv, Eugene; Bannister, Wade, CBC: an associative classifier with a small number of rules, Dec. Supp. Syst., 59, 163-170, (2014)
[12] Dong, Jie; Han, Min, Bittablefi: an efficient mining frequent itemsets algorithm, Knowl.-Based Syst., 20, 4, 329-335, (2007)
[13] Duong, Hai; Truong, Tin; Le, Bac, An efficient algorithm for mining frequent itemsets with single constraint advanced computational methods for knowledge engineering, (2013), Springer, pp. 367-378
[14] Jiawei Han, Jian Pei, Yiwen Yin, Mining frequent patterns without candidate generation, in: Paper Presented at the ACM SIGMOD Record, 2000.
[15] Hernández-León, Raudel; Hernández-Palancar, José; Carrasco-Ochoa, J. A.; Martínez-Trinidad, José Fco, Studying netconf in hybrid rule ordering strategies for associative classification pattern recognition, (2014), Springer, pp. 51-60
[16] Hong, Tzung-Pei; Wang, Ching-Yao, An efficient and effective association-rule maintenance algorithm for record modification, Exp. Syst. Appl., 37, 1, 618-626, (2010)
[17] Hong, Tzung-Pei; Wang, Ching-Yao; Tseng, Shian-Shyong, An incremental mining algorithm for maintaining sequential patterns using pre-large sequences, Exp. Syst. Appl., 38, 6, 7051-7058, (2011)
[18] Leung, Carson Kai-Sang; Lakshmanan, Laks V. S.; Ng, Raymond T, Exploiting succinct constraints using FP-trees, ACM SIGKDD Explor. Newslett., 4, 1, 40-49, (2002)
[19] Jiye Li, Nick Cercone, Discovering and ranking important rules, in: Paper presented at the IEEE International Conference on Granular Computing, 2005.
[20] Wei Li, Longbing Cao, Dazhe Zhao, Xia Cui, Jinzhu Yang, CRNN: integrating classification rules into neural network, in: Paper Presented at the International Joint Conference on Neural Networks (IJCNN 2013), 2013.
[21] Wenmin Li, Jiawei Han, Jian Pei, CMAR: accurate and efficient classification based on multiple class-association rules, in: Paper Presented at the IEEE International Conference on Data Mining (ICDM 2001), 2001.
[22] Lin, Wen-Yang; Huang, Ko-Wei; Wu, Chin-Ang, Mcfptree: an FP-tree-based algorithm for multi-constraint patterns discovery, Int. J. Bus. Intell. Data Min., 5, 3, 231-246, (2010)
[23] Bing Liu, Wynne Hsu, Yiming Ma, Integrating classification and association rule mining, in: Paper presented at the 4th International Conference on Knowledge Discovery and Data Mining (KDD 1998), 1998.
[24] Liu, Huawen; Liu, Lei; Zhang, Huijie, A fast pruning redundant rule method using Galois connection, Appl. Soft Comput., 11, 1, 130-137, (2011)
[25] Nan Lu, Chun-Guang Zhou, Jing-Zhou Zhou, Research on association rules mining algorithm with item constraints, in: Paper Presented at the International Conference on Cyberworlds, 2005.
[26] Moath Najeeb, A.E. Sheikh, Mohammed Nababteh, A new rule ranking model for associative classification using a hybrid artificial intelligence technique, in: Paper presented at the 3rd International Conference on Communication Software and Networks (ICCSN 2011), 2011.
[27] Raymond T. Ng, Laks V.S. Lakshmanan, Jiawei Han, Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, in: Paper Presented at the ACM SIGMOD International Conference on Management of Data, 1998.
[28] Nguyen, Dang; Vo, Bay; Le, Bac, Efficient strategies for parallel mining class association rules, Exp. Syst. Appl., 41, 10, 4716-4729, (2014)
[29] Nguyen, Loan T. T.; Vo, Bay; Hong, Tzung-Pei; Thanh, Hoang Chi, Classification based on association rules: a lattice-based approach, Exp. Syst. Appl., 39, 13, 11357-11366, (2012)
[30] Nguyen, Loan T. T.; Vo, Bay; Hong, Tzung-Pei; Thanh, Hoang Chi, CAR-miner: an efficient algorithm for mining class-association rules, Exp. Syst. Appl., 40, 6, 2305-2311, (2013)
[31] Jian Pei, Jiawei Han, Laks V.S. Lakshmanan, Mining frequent itemsets with convertible constraints, in: Paper presented at the 17th International Conference on Data Engineering, 2001.
[32] Song, Wei; Yang, Bingru; Xu, Zhangyan, Index-bittablefi: an improved algorithm for mining frequent itemsets, Knowl.-Based Syst., 21, 6, 507-513, (2008)
[33] Ramakrishnan Srikant, Quoc Vu, Rakesh Agrawal, Mining association rules with item constraints, in: Paper presented at the 3rd International Conference on Knowledge Discovery and Data Mining (KDD 1997), 1997.
[34] Fadi Thabtah, Peter Cowling, Yonghong Peng, MMAC: a new multi-class, multi-label associative classification approach, in: Paper presented at the 4th IEEE International Conference on Data Mining (ICDM 2004), 2004.
[35] Risi Thonangi, Vikram Pudi, ACME: an associative classifier based on maximum entropy principle, in: Paper Presented at the 16th International Conference on Algorithmic Learning Theory, 2005. · Zbl 1168.68496
[36] Hannu Toivonen, Mika Klemettinen, Pirjo Ronkainen, Kimmo, Hätönen, Heikki Mannila, Pruning and grouping discovered association rules, in: Paper Presented at the ECML-95 Workshop on SMLKD, 1995.
[37] Anh Tran, Hai Duong, Tin Truong, Bac Le, Efficient algorithms for mining frequent itemsets with constraint, in: Paper presented at the 3rd International Conference on Knowledge and Systems Engineering (KSE 2011), 2011.
[38] Vo, Bay; Hong, Tzung-Pei; Le, Bac, DBV-miner: a dynamic bit-vector approach for fast mining frequent closed itemsets, Exp. Syst. Appl., 39, 8, 7196-7206, (2012)
[39] Vo, Bay; Le, Bac, A Novel Classification Algorithm Based on Association Rules Mining Knowledge Acquisition: Approaches, Algorithms and Applications, vol. 5465, (2009), Springer
[40] Vo, Bay; Le, Tuong; Hong, Tzung-Pei; Le, Bac, An effective approach for maintenance of pre-large-based frequent-itemset lattice in incremental mining, Appl. Intell., 41, 3, 759-775, (2014)
[41] Xiaoxin Yin, Jiawei Han, CPAR: classification based on predictive association rules, in: Paper Presented at the 3rd SIAM International Conference on Data Mining (SDM 2003), 2003.
[42] Zaki, Mohammed; Hsiao, C.-J., Efficient algorithms for mining closed itemsets and their lattice structure, IEEE Trans. Knowl. Data Eng., 17, 4, 462-478, (2005)
[43] Mohammed Zaki, Srinivasan Parthasarathy, Mitsunori Ogihara, Wei Li, New algorithms for fast discovery of association rules, in: Paper presented at the 3rd International Conference on Knowledge Discovery and Data Mining, 1997.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.