Positive approximation: an accelerator for attribute reduction in rough set theory. (English) Zbl 1205.68310

Qian, Yuhua; Liang, Jiye; Pedrycz, Witold; Dang, Chuangyin

Artif. Intell. 174, No. 9-10, 597-618 (2010).

Summary: Feature selection is a challenging problem in areas such as pattern recognition, machine learning and data mining. Considering a consistency measure introduced in rough set theory, the problem of feature selection, also called attribute reduction, aims to retain the discriminatory power of original features. Many heuristic attribute reduction algorithms have been proposed however, quite often, these methods are computationally time-consuming. To overcome this shortcoming, we introduce a theoretic framework based on rough set theory, called positive approximation, which can be used to accelerate a heuristic process of attribute reduction. Based on the proposed accelerator, a general attribute reduction algorithm is designed. Through the use of the accelerator, several representative heuristic attribute reduction algorithms in rough set theory have been enhanced. Note that each of the modified algorithms can choose the same attribute reduct as its original version, and hence possesses the same classification accuracy. Experiments show that these modified algorithms outperform their original counterparts. It is worth noting that the performance of the modified algorithms becomes more visible when dealing with larger data sets.

MSC:

68T05	Learning and adaptive systems in artificial intelligence
68T20	Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
94A17	Measures of information, entropy

Keywords:

rough set theory; attribute reduction; decision table; positive approximation; granular computing

Software:

LERS

References:

[1]	Bazan, J. G., A comparison of dynamic and non-dynamic rough set methods for extracting laws from decision tables, (Polkowski, L.; Skowron, A., Rough Sets in Knowledge Discovery 1: Methodology and Applications. Rough Sets in Knowledge Discovery 1: Methodology and Applications, Studies in Fuzziness and Soft Computing (1998), Physica-Verlag: Physica-Verlag Heidelberg, Germany), 321-365 · Zbl 1067.68711
[2]	Bazan, J. G.; Nguyen, H. S.; Nguyen, S. H.; Synak, P.; Wróblewski, J., Rough set algorithms in classification problems, (Polkowski, L.; Tsumoto, S.; Lin, T. Y., Rough Set Methods and Applications: New Developments in Knowledge Discovery in Information Systems (2000), Springer-Verlag: Springer-Verlag Heidelberg, Germany), 49-88 · Zbl 0992.68197
[3]	Bhatt, R. B.; Gopal, M., On fuzzy-rough sets approach to feature selection, Pattern Recognition Letters, 26, 965-975 (2005)
[4]	Bhatt, R. B.; Gopal, M., On the compact computational domain of fuzzy-rough sets, Pattern Recognition Letters, 26, 1632-1640 (2005)
[5]	Chmielewski, M. R.; Grzymala Busse, J. W., Global discretization of continuous attributes as preprocessing for machine learning, International Journal of Approximate Reasoning, 15, 4, 319-331 (1996) · Zbl 0949.68560
[6]	Dash, M.; Liu, H., Consistency-based search in feature selection, Artificial Intelligence, 151, 155-176 (2003) · Zbl 1082.68791
[7]	Düntsch, I.; Gediga, G., Uncertainty measures of rough set prediction, Artificial Intelligence, 106, 109-137 (1998) · Zbl 0909.68040
[8]	Gediga, G.; Düntsch, I., Rough approximation quality revisited, Artificial Intelligence, 132, 219-234 (2001) · Zbl 0983.68194
[9]	Grzymala-Busse, J. W., An algorithm for computing a single covering, (Grzymala-Busse, J. W., Managing Uncertainty in Expert Systems (1991), Kluwer Academic Publishers), 66
[10]	Grzymala-Busse, J. W., LERS—a system for learning from examples based on rough sets, (Slowinski, R., Intelligent Decision Support: Handbook of Applications and Advances of the Rough Set Theory (1992), Kluwer Academic Publishers), 3-18
[11]	Guan, J. W.; Bell, D. A., Rough computational methods for information systems, Artificial Intelligence, 105, 77-103 (1998) · Zbl 0909.68047
[12]	Guyon, I.; Elisseeff, A., An introduction to variable feature selection, Journal of Machine Learning Research, 3, 1157-1182 (2003) · Zbl 1102.68556
[13]	Jensen, R.; Shen, Q., Semantics-preserving dimensionality reduction: rough and fuzzy-rough-based approaches, IEEE Transactions on Knowledge and Data Engineering, 16, 12, 1457-1471 (2004)
[14]	Jensen, R.; Shen, Q., Computational Intelligence and Feature Selection: Rough and Fuzzy Approaches (2008), IEEE Press/Wiley & Sons
[15]	Kira, K.; Rendell, L. A., The feature selection problem: traditional methods and a new algorithm, Proc. AAAI, 92, 129-134 (1992)
[16]	Kohavi, R.; John, G. H., Wrappers for feature subset selection, Artificial Intelligence, 97, 1-2, 273-324 (1997) · Zbl 0904.68143
[17]	Kryszkiewicz, M.; Lasek, P., FUN: fast discovery of minimal sets of attributes functionally determining a decision attribute, Transactions on Rough Sets, 9, 76-95 (2008)
[18]	Kryszkiewicz, M., Comparative study of alternative type of knowledge reduction in inconsistent systems, International Journal of Intelligent Systems, 16, 105-120 (2001) · Zbl 0969.68146
[19]	Hu, X. H.; Cercone, N., Learning in relational databases: a rough set approach, International Journal of Computational Intelligence, 11, 2, 323-338 (1995)
[20]	Hu, Q. H.; Xie, Z. X.; Yu, D. R., Hybrid attribute reduction based on a novel fuzzy-rough model and information granulation, Pattern Recognition, 40, 3509-3521 (2007) · Zbl 1129.68073
[21]	Hu, Q. H.; Yu, D. R.; Xie, Z. X.; Liu, J. F., Fuzzy probabilistic approximation spaces and their information measures, IEEE Transactions on Fuzzy Systems, 14, 2, 191-201 (2006)
[22]	Hu, Q. H.; Yu, D. R.; Xie, Z. X., Information-preserving hybrid data reduction based on fuzzy-rough techniques, Pattern Recognition Letters, 27, 5, 414-423 (2006)
[23]	Lee, C. K.; Lee, G. G., Information gain and divergence-based feature selection for machine learning-based text categorization, Information Processing and Management, 42, 155-165 (2006)
[24]	Li, D. Y.; Zhang, B.; Leung, Y., On knowledge reduction in inconsistent decision information systems, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 12, 5, 651-672 (2004) · Zbl 1082.68113
[25]	Liang, J. Y.; Chin, K. S.; Dang, C. Y.; Yam Richid, C. M., A new method for measuring uncertainty and fuzziness in rough set theory, International Journal of General Systems, 31, 4, 331-342 (2002) · Zbl 1010.94004
[26]	Liang, J. Y.; Xu, Z. B., The algorithm on knowledge reduction in incomplete information systems, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10, 1, 95-103 (2002) · Zbl 1085.68696
[27]	Liang, J. Y.; Qian, Y. H.; Chu, C. Y.; Li, D. Y.; Wang, J. H., Rough set approximation based on dynamic granulation, Lecture Notes in Computer Science, 3641, 701-708 (2005) · Zbl 1134.68542
[28]	Liu, H.; Setiono, R., Feature selection via discretization, IEEE Transactions on Knowledge and Data Engineering, 9, 4, 642-645 (1997)
[29]	Mi, J. S.; Wu, W. Z.; Zhang, W. X., Comparative studies of knowledge reductions in inconsistent systems, Fuzzy Systems and Mathematics, 17, 3, 54-60 (2003) · Zbl 1332.68221
[31]	Nguyen, H. S., Approximate Boolean reasoning: Foundations and applications in data mining, Lecture Notes in Computer Science, 3100, 334-506 (2006) · Zbl 1136.68497
[32]	Pavlenko, T., On feature selection, curse-of-dimensionality and error probability in discriminant analysis, Journal of Statistical Planning and Inference, 115, 565-584 (2003) · Zbl 1015.62066
[33]	Pawlak, Z., Rough Sets: Theoretical Aspects of Reasoning about Data (1991), Kluwer Academic Publishers: Kluwer Academic Publishers Boston · Zbl 0758.68054
[34]	Pawlak, Z.; Skowron, A., Rudiments of rough sets, Information Sciences, 177, 1, 3-27 (2007) · Zbl 1142.68549
[35]	Pawlak, Z.; Skowron, A., Rough sets: some extensions, Information Sciences, 177, 28-40 (2007) · Zbl 1142.68550
[36]	Pawlak, Z.; Skowron, A., Rough sets and boolean reasoning, Information Sciences, 177, 1, 41-73 (2007) · Zbl 1142.68551
[37]	Pedrycz, W.; Vukovich, G., Feature analysis through information granulation and fuzzy sets, Pattern Recognition, 35, 825-834 (2002) · Zbl 0997.68114
[38]	Polkowski, L., On convergence of rough sets, (Slowinski, R., Intelligent Decision Support: Handbook of Applications and Advances of Rough Set Theory, vol. 11 (1992), Kluwer: Kluwer Dordrecht), 305-311
[39]	Qian, Y. H.; Liang, J. Y., Combination entropy and combination granulation in rough set theory, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 16, 2, 179-193 (2008) · Zbl 1154.68520
[40]	Qian, Y. H.; Liang, J. Y.; Dang, C. Y., Converse approximation and rule extraction from decision tables in rough set theory, Computer and Mathematics with Applications, 55, 1754-1765 (2008) · Zbl 1147.68736
[41]	Qian, Y. H.; Liang, J. Y.; Dang, C. Y., Consistency measure, inclusion degree and fuzzy measure in decision tables, Fuzzy Sets and Systems, 159, 2353-2377 (2008) · Zbl 1187.68614
[42]	Qian, Y. H.; Liang, J. Y.; Dang, C. Y., Interval ordered information systems, Computer and Mathematics with Applications, 56, 1994-2009 (2008) · Zbl 1165.68513
[43]	Qian, Y. H.; Liang, J. Y.; Dang, C. Y.; Tang, D. W., Set-valued ordered information systems, Information Sciences, 179, 2809-2832 (2009) · Zbl 1192.68805
[44]	Qian, Y. H.; Liang, J. Y.; Li, D. Y.; Zhang, H. Y.; Dang, C. Y., Measures for evaluating the decision performance of a decision table in rough set theory, Information Sciences, 178, 181-202 (2008) · Zbl 1128.68102
[45]	Qian, Y. H.; Liang, J. Y.; Dang, C. Y., Incomplete multi-granulations rough set, IEEE Transactions on Systems, Man and Cybernetics: Part A, 40, 2, 420-431 (2010)
[46]	Quinlan, R., Induction of decision rules, Machine Learning, 1, 1, 81-106 (1986)
[47]	Shao, M. W.; Zhang, W. X., Dominance relation and rules in an incomplete ordered information system, International Journal of Intelligent Systems, 20, 13-27 (2005) · Zbl 1089.68128
[48]	Shen, Q.; Jensen, R., Selecting informative features with fuzzy-rough sets and its application for complex systems monitoring, Pattern Recognition, 37, 1351-1363 (2004) · Zbl 1070.68600
[49]	Skowron, A., Extracting laws from decision tables: a rough set approach, Computational Intelligence, 11, 371-388 (1995)
[52]	Slezak, D., Approximate entropy reducts, Fundamenta Informaticae, 53, 3-4, 365-390 (2002) · Zbl 1092.68676
[53]	Swiniarski, R. W.; Skowron, A., Rough set methods in feature selection and recognition, Pattern Recognition Letters, 24, 833-849 (2003) · Zbl 1053.68093
[54]	Wang, G. Y.; Yu, H.; Yang, D. C., Decision table reduction based on conditional information entropy, Chinese Journal of Computer, 25, 7, 759-766 (2002)
[55]	Wang, G. Y.; Zhao, J.; An, J. J., A comparative study of algebra viewpoint and information viewpoint in attribute reduction, Fundamenta Informaticae, 68, 3, 289-301 (2005) · Zbl 1098.68134
[56]	Wu, S. X.; Li, M. Q.; Huang, W. T.; Liu, S. F., An improved heuristic algorithm of attribute reduction in rough set, Journal of System Sciences and Information, 2, 3, 557-562 (2004)
[57]	Wu, W. Z.; Zhang, M.; Li, H. Z.; Mi, J. S., Knowledge reduction in random information systems via Dempster-Shafer theory of evidence, Information Sciences, 174, 143-164 (2005) · Zbl 1088.68169
[58]	Xu, Z. Y.; Liu, Z. P.; Yang, B. R.; Song, W., A quick attribute reduction algorithm with complexity of \(\max(O(| C | | U |), O(| C |^2 | U / C |))\), Chinese Journal of Computer, 29, 3, 391-398 (2006)
[59]	Yao, Y. Y., Information granulation and rough set approximation, International Journal of Intelligent Systems, 16, 1, 87-104 (2001) · Zbl 0969.68079
[60]	Ziarko, W., Variable precision rough set model, Journal of Computer and System Sciences, 46, 39-59 (1993) · Zbl 0764.68162