Attribute Reduction in Incomplete Information System based on Rough Set Theory Using Fuzzy Imperialist Competitive Algorithm

Document Type : Research Paper


1 MSc. Student in IT Engineering, University of Birjand, Iran

2 Assistant Prof., Faculty of Engineering, Dep. of Computer, Bozorgmehr University of Qaenat, Qaen, Iran


In recent years, rough set theory has been considered as a strong solution to solve artificial intelligence problem such as data mining. But, the classic rough set theory is not effective in the case of attribute reduction in incomplete information systems. Since there are null values for some of attributes in a data set, an incomplete information system is created. In this paper, a novel method proposed to solve attribute reduction in incomplete information system based on rough set theory by combining and modifying imperialist competitive algorithm with fuzzy logic. Utilizing the fuzzy logic to control the parameters of the algorithm was useful and generated better solutions compared to its classic draft. In this research, no changes imposed on incomplete data, and it was just considered as a complete systems. The fuzzy imperialist competitive algorithm acted intelligently to reduce the number of attribute in incomplete information system, providing appropriate results that is worthy of attention.


Main Subjects

صفوی، ع. ا.؛ پورجعفریان، ن.؛ صفوی، ع. (1393)، بهینهسازی بر پایۀ الگوریتمهای فراابتکاری، تهران: موسسۀ انتشاراتی پژوهشگران نشر دانشگاهی.
صنیعی آباده، م.؛ جبل عامیلیان، ز. (1392).  الگوریتم های تکاملی و محاسبات زیستی، تهران: نیاز دانش.
Atashpaz-Gargari, E. & Lucas, C. (2007, September). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. Evolutionary Computation (pp. 4661-4667). Singapore: IEEE.
Chmielewski, M., Grzymala-Busse, J., Peterson, N. & Than, S. (1993). The rule induction system LERS – a version for personal computer. Foundations of Computing and Decision Science, 18(3), 181-212.
Dash, M. & Liu, H. (2003). Consistency-based search in feature selection. Artificial Intelligence, 151(1), 155-176.
Guyon, I. & Elisseeff, A. (2003). An introduction to variable and feature selection. The Journal of Machine Learning Research, 3(1), 1157-1182.
Hajihassani, M., Armaghani, D. J. & Marto, A. (2015). Ground vibration prediction in quarry blasting through an artificial neural network optimized by imperialist competitive algorithm. Bulletin of Engineering Geology and the Environment, 74(3), 873-886.
Han, J. & Kamber, M. (2006). Data Mining: Concepts and Techniques. San Francisco: Diane Cerra.
Hu, Q., Xie, Z. & Yu, D. (2007). Hybrid attribute reduction based on a novel fuzzy-rough model and information granulation. Pattern Recognition, 40(12), 3509–3521.
Hu, Q., Yu, D. & Xie, Z. (2006). Information-preserving hybrid data reduction based on fuzzy-rough techniques. Pattern Recognition Letters, 27(5), 414–423.
Hu, X. & Cercone, N. (1995). Learning in relational databases: a rough set approach. Computational Intelligence, 11(2), 323–338.
Ke, L., Zuren, F. & Zhigang, R. (2008). An efficient ant colony optimization approach to attribute reduction in rough set theory. Pattern Recognition Letters, 29(9), 1351-1357.
Kira, K. & Rendell, L. (1992). The feature selection problem: traditional methods and a new algorithm. AAAI, 2(1), 129–134.
Kohavi, R. & John, G. (1997). Wrappers for feature subset selection. Artificial Intelligence, 97(2), 273-324.
Kryszkiewicz, M. (1998). Rough setapproach to incomplete information systems. Information Sciences, 112(1), 39-49.
Lee, C. & Lee, G. (2006). Information gain and divergence-based feature selection for machine learning-based text categorization. Information Processing and Management, 42(1), 155-165.
Li, D., Zhang, B. & Leung, Y. (2004). On knowledge reduction in inconsistent decision information systems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 12(5), 651-672.
Liang, J. & Xu, Z. (2002). The algorithm on knowledge reduction in incomplete information systems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 10(1), 95-103.
Liang, J., Chin, K., Dang, C. & YamRichid, C. (2002). A new method for measuring uncertainty and fuzziness in rough set theory. International Journal of General Systems, 31(4), 331-342.
Liang, J., Shi, Z., Li, D. & Wierman, M. (2006). Information entropy, rough entropy and knowledge granulation in incomplete information systems. International Journal of General Systems, 35(6), 641-654.
Lotfizadeh, L. A. (1992). Fuzzy logic, neural networks and soft computing. Communications of the ACM, 37(3), 77-84.
Meng, Z. & Shi, Z. (2009). A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets. Information Sciences, 179(16), 2774–2793.
Mi, J., Wu, W. & Zhang, W. (2003). Comparative studies of knowledge reductions in inconsistent systems. Fuzzy systems and mathematics, 17(3), 54-60.
Modrzejewski, M. (1993, April). Feature selection using rough set theory. Machine Learning (pp. 213–226). Berlin Heidelberg: Springer.
Orlowska, E. & Pawlak, Z. (1984). Representation of nondeterministic information. Theoretical Computer Science, 29(1), 27-39.
Pawlak, Z. (1998). Rough set theory and its applications to data analysis. Cybernetics and Systems, 29(7), 662-668.
Pawlak, Z. & Skowron, A. (2007). Rudiments of rough sets. Information Sciences, 177(1), 3-27.
Qian, Y. & Liang, J. (2008). Combination entropy and combination granulation in rough set theory. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 16(2), 179-193.
Qian, Y., Liang, J. & Dang, C. (2008). Consistency measure, inclusion degree and fuzzy measure in decision tables. Fuzzy Sets and Systems, 159(18), 2353–2377.
Qian, Y., Liang, J. & Dang, C. (2008). Interval ordered information systems. Computers & Mathematics with Applications, 56(8), 1994–2009.
Qian, Y., Liang, J. & Wang, F. (2009). A new method for measuring the uncertainty in incomplete information systems. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 17(6), 855–880.
Qian, Y., Liang, J., Pedrycz, W. & Dang, C. (2011). An efficient accelerator for attribute reduction from incomplete data in rough set framework. Pattern Recognition, 44(8), 1658–1670.
Qiana, Y., Zhangb, H., Sangb, Y. & Lianga, J. (2014). Multigranulation decision-theoretic rough sets. International Journal of Approximate Reasoning, 55(1), 225-237.
Quinlan, J. (1986). Induction of decision trees. Machine Learning, 1(1), 81-106.
Safavi, A., Pourjafarian, N. & Safavi, A. (2014). Optimization Based On Meta Hueristic Algorithms. Shiraz: Researchers academic publishing. (in Persian)
Sanei Abadeh, M., & Jebel, Z. (2013). Evolutionary Algorithms and Biological Computing. Tehran: Niaz Danesh. (in Persian)
Shao, M. & Zhang, W. (2005). Dominance relation and rules in an incomplete ordered information system. International journal of intelligent systems, 20(1), 13-27.
Skowron, A. (1995). Extracting laws from decision tables: a rough setapproach. Computational Intelligence, 11(2), 371-388.
Slezak, D. (2002). Approximate entropy reducts. Fundamenta informaticae, 53(3), 365–390.
UCI. (2016). Retrieved from
Wang, G., Yu, H. & Yang, D. (2002). Decision table reduction based on conditional information entropy. Chinese Journal of Computer, 25(7), 759–766.
Wang, G., Zhao, J. & An, J. (2005). Acomparative study of algebra viewpoint and nattribute reduction. Foundamenta Informaticae, 68(3), 289–301.
Wu, S., Li, M., Huang, W., & Liu, S. (2004). An Improved Heuristic Algorithm of Attribute Reduction in Rough Set. Journal of Systems Science & Information, 2(3), 557-562.
Wu, W., Zhang, M., Li, H. & Mi, J. (2005). Knowledge reduction in random information systems via Dempster–Shafer theory of evidence. Information Sciences, 174(3), 143–164.
Yang, C. & Shu, L. (2006). Attribute reduction algorithm of incomplete decision table based on tolerance relation. Computer Technology and Development, 16(9).
Yu, J. (2005). General C-means clustering model. Pattern Analysis and Machine Intelligence, IEEE Transactions, 27(8), 1197-1211.