Approximations and uncertainty measures in incomplete information systems. (English) Zbl 1248.68487

Dai, Jianhua; Xu, Qing

Inf. Sci. 198, 62-80 (2012).

Summary: There are mainly two methodologies dealing with uncertainty measurement issue in rough set theory: pure rough set approach and information theory approach. Pure rough set approach is based on the concepts of accuracy, roughness and approximation accuracy proposed by Pawlak. Information theory approach is based on Shannon’s entropy or its variants. Several authors have extended the information theory approach into incomplete information systems. However, there are few studies on extending the pure rough set approach to incomplete information systems. This paper focuses on constructing uncertainty measures in incomplete information systems by pure rough set approach. Three types of definitions of lower and upper approximations and corresponding uncertainty measurement concepts including accuracy, roughness and approximation accuracy are investigated. Theoretical analysis indicates that two of the three types can be used to evaluate the uncertainty in incomplete information systems. Experiments on incomplete real-life data sets have been conducted to test the two selected types (the first type and the third type) of uncertainty measures. Results show that the two types of uncertainty measures are effective.

MSC:

68T37	Reasoning under uncertainty in the context of artificial intelligence
94A17	Measures of information, entropy

Keywords:

rough set theory; incomplete information systems; uncertainty measures; approximations; accuracy measure

Software:

UCI-ml; LERS

References:

[1]	Abo-Tabl, E. A., A comparison of two kinds of definitions of rough approximations based on a similarity relation, Information Sciences, 181, 2587-2596 (2011) · Zbl 1216.68289
[2]	Abu-Donia, H., Multi knowledge based rough approximations and applications, Knowledge-Based Systems, 26, 20-29 (2012)
[3]	Abu-Donia, H. M., Comparison between different kinds of approximations by using a family of binary relations, Knowledge-Based Systems, 21, 911-919 (2008)
[4]	Beaubouef, T.; Petry, F. E.; Arora, G., Information-theoretic measures of uncertainty for rough sets and rough relational databases, Information Sciences, 109, 185-195 (1998)
[5]	Bianucci, D.; Cattaneo, G., Information entropy and granulation co-entropy of partitions and coverings: a summary, Transactions on Rough Sets, 10, 15-66 (2009) · Zbl 1248.94038
[6]	Bianucci, D.; Cattaneo, G.; Ciucci, D., Entropies and cocentropies of coverings with application to incomplete information systems, Fundamenta Informaticae, 75, 77-105 (2007) · Zbl 1108.68112
[7]	Blaszczynski, J.; Slowinski, R.; Szelag, M., Sequential covering rule induction algorithm for variable consistency roughset approaches, Information Sciences, 181, 987-1002 (2011)
[8]	Cattaneo, G.; Ciucci, D., Investigation about time monotonicity of similarity and preclusive rough approximations in incomplete information systems, Lecture Notes on Artificial Intelligence, 3066, 38-48 (2004) · Zbl 1103.68835
[9]	Cattaneo, G.; Ciucci, D.; Bianucci, D., Entropy and co-entropy of partitions and coverings with applications to roughness theory, Studies in Fuzziness and Soft Computing, 224, 55-77 (2008) · Zbl 1145.68539
[10]	Ciucci, D., Classification of dynamics in rough sets, Lecture Notes on Artificial Intelligence, 6086, 257-266 (2010)
[11]	Dai, J. H., Rough 3-valued algebras, Information Sciences, 178, 1986-1996 (2008) · Zbl 1134.06008
[12]	Dai, J. H.; Wang, W.; Xu, Q.; Tian, H., Uncertainty measurement for interval-valued decision systems based on extended conditional entropy, Knowledge-Based Systems, 27, 443-450 (2012)
[13]	Derrac, J.; Cornelis, C.; Garcia, S.; Herrera, F., Enhancing evolutionary instance selection algorithms by means of fuzzy rough set based feature selection, Information Sciences, 181, 73-92 (2012)
[14]	Duentsch, I.; Gediga, G., Uncertainty measures of rough set prediction, Artificial Intelligence, 106, 109-137 (1998) · Zbl 0909.68040
[15]	Feng, L.; Li, T.; Ruan, D.; Gou, S., A vague-rough set approach for uncertain knowledge acquisition, Knowledge-Based Systems, 24, 837-843 (2011)
[16]	Formica, A., Semantic web search based on rough sets and fuzzy formal concept analysis, Knowledge-Based Systems, 26, 40-47 (2012)
[18]	Greco, S.; Matarazzo, B.; Slowinski, R., Handling missing values in rough set analysis of multi-attribute and multi-criteria decision problems, Lecture Notes in Artificial Intelligence, 1711, 146-157 (1999) · Zbl 1037.91510
[19]	Grzymala-Busse, J., A new version of the rule induction system LERS, Fundamenta Informaticae, 31, 27-39 (1997) · Zbl 0882.68122
[20]	Grzymala-Busse, J.; Rzasa, W., Local and global approximations for incomplete data, Lecture Notes in Computer Science, 4259, 244-253 (2006) · Zbl 1162.68690
[21]	Herawan, T.; Deris, M. M.; Abawajy, J. H., A rough set approach for selecting clustering attribute, Knowledge-Based Systems, 23, 220-231 (2010)
[22]	Hu, Q.; An, S.; Yu, D., Soft fuzzy rough sets for robust feature evaluation and selection, Information Sciences, 180, 4384-4400 (2010)
[23]	Jelonek, J.; Krawiec, K.; Slowiski, R., Rough set reduction of attributes and their domains for neural networks, Computational Intelligence, 11, 339-347 (1995)
[25]	Kim, D.; Bang, S., A handwritten numeral character classification using tolerant rough set, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 923-937 (2002)
[26]	Kryszkiewicz, M., Rough set approach to incomplete information systems, Information Sciences, 112, 39-49 (1998) · Zbl 0951.68548
[27]	Kryszkiewicz, M., Rules in incomplete information systems, Information Sciences, 113, 271-292 (1999) · Zbl 0948.68214
[28]	Li, Y. L.; Tang, J. F.; Chin, K. S.; Han, Y.; Luo, X. G., A roughset approach for estimating correlation measures in quality function deployment, Information Sciences, 189, 126-142 (2012)
[29]	Liang, J.; Chin, K. S.; Dang, C.; Yam, R. C.M., A new method for measuring uncertainty and fuzziness in rough set theory, International Journal of General Systems, 31, 331-342 (2002) · Zbl 1010.94004
[30]	Liang, J.; Shi, Z.; Li, D.; Wierman, M. J., Information entropy, rough entropy and knowledge granulation in incomplete information systems, International Journal of General Systems, 35, 641-654 (2006) · Zbl 1115.68130
[31]	Lin, T. Y., Granular computing on binary relations II: rough set representations and belief functions, Rough Sets in Knowledge Discovery, 121-140 (1998) · Zbl 0927.68090
[32]	Mac Parthalain, N.; Shen, Q., Exploring the boundary region of tolerance rough sets for feature selection, Pattern Recognition, 42, 655-667 (2009) · Zbl 1162.68625
[33]	Meng, Z.; Shi, Z., A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets, Information Sciences, 179, 2774-2793 (2009) · Zbl 1191.68667
[34]	Mi, J. S.; Leung, Y.; Wu, W. Z., An uncertainty measure in partition-based fuzzy rough sets, International Journal of General Systems, 34, 77-90 (2005) · Zbl 1125.03309
[35]	Mi, J. S.; Wu, W. Z.; Zhang, W. X., Approaches to knowledge reduction based on variable precision rough set model, Information sciences, 159, 255-272 (2004) · Zbl 1076.68089
[36]	Min, F.; He, H.; Qian, Y.; Zhu, W., Test-cost-sensitive attribute reduction, Information Sciences, 181, 4928-4942 (2011)
[37]	Pawlak, Z., Rough Sets: Theoretical Aspects of Reasoning about Data (1991), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0758.68054
[38]	Pawlak, Z., Vagueness and uncertainty: a rough set perspective, Computational Intelligence, 11, 227-232 (1995)
[39]	Pawlak, Z., Rough set approach to knowledge-based decision support, European Journal of Operational Research, 99, 48-57 (1997) · Zbl 0923.90004
[40]	Pawlak, Z., Rough set theory and its applications to data analysis, Cybernetics and Systems: An International Journal, 29, 661-688 (1998) · Zbl 1008.03526
[41]	Pawlak, Z.; Skowron, A., Rudiments of rough sets, Information Sciences, 177, 3-27 (2007) · Zbl 1142.68549
[42]	Polkowski, L., Rough Sets: Mathematical Foundations (2002), Springer · Zbl 1040.68114
[43]	Qian, Y.; Liang, J., Combination entropy and combination granulation in incomplete information system, Lecture Notes in Computer Science, 4062, 184-190 (2006) · Zbl 1196.68269
[44]	Qian, Y.; Liang, J.; Li, D.; Wang, F.; Ma, N., Approximation reduction in inconsistent incomplete decision tables, Knowledge-Based Systems, 23, 427-433 (2010)
[45]	Qian, Y.; Liang, J.; Pedrycz, W.; Dang, C., Positive approximation: an accelerator for attribute reduction in rough set theory, Artificial Intelligence, 174, 597-618 (2010) · Zbl 1205.68310
[46]	Qian, Y.; Liang, J.; Wang, F., A new method for measuring the uncertainty in incomplete information systems, International Journal of Uncertainty Fuzziness and Knowledge-Based Systems, 17, 855-880 (2009) · Zbl 1185.68715
[47]	Samanta, P.; Chakraborty, M. K., Covering based approaches to rough sets and implication lattices, Lecture Notes on Artificial Intelligence, 5908, 127-134 (2009)
[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]	Shyng, J. Y.; Shieh, H. M.; Tzeng, G. H., An integration method combining rough set theory with formal concept analysis for personal investment portfolios, Knowledge-Based Systems, 23, 586-597 (2010)
[50]	Skowron, A.; Stepaniuk, J.; Swiniarski, R., Modeling rough granular computing based on approximation spaces, Information Sciences, 184, 20-43 (2012)
[51]	Stefanowski, J.; Tsoukias, A., Incomplete information tables and rough classification, Computational Intelligence, 17, 545-566 (2001)
[52]	Su, J. H.; Wang, B. W.; Hsiao, C. Y.; Tseng, V. S., Personalized rough-set-based recommendation by integrating multiple contents and collaborative information, Information Sciences, 180, 113-131 (2010)
[53]	Swiniarski, R.; Skowron, A., Rough set methods in feature selection and recognition, Pattern recognition letters, 24, 833-849 (2003) · Zbl 1053.68093
[54]	Tsumoto, S., Automated extraction of medical expert system rules from clinical databases based on rough set theory, Information Sciences, 112, 67-84 (1998)
[55]	Wang, H.; Wang, S., Discovering patterns of missing data in survey databases: an application of rough sets, Expert Systems with Applications, 36, 6256-6260 (2009)
[56]	Wierman, M. J., Measuring uncertainty in rough set theory, International Journal of General Systems, 28, 283-297 (1999) · Zbl 0938.93034
[57]	Wu, W.; Zhang, W.; Li, H., Knowledge acquisition in incomplete fuzzy information systems via the rough set approach, Expert Systems, 20, 280-286 (2003)
[58]	Wu, W. Z.; Leung, Y., Theory and applications of granular labelled partitions in multi-scale decision tables, Information Sciences, 181, 3878-3897 (2011) · Zbl 1242.68258
[59]	Xu, W.; Li, Y.; Liao, X., Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems, Knowledge-Based Systems, 27, 78-91 (2012)
[60]	Yao, J.; Herbert, J., Financial time-series analysis with rough sets, Applied Soft Computing, 9, 1000-1007 (2009)
[61]	Yao, Y. Y., Relational interpretations of neighborhood operators and rough set approximation operators, Information Sciences, 111, 239-259 (1998) · Zbl 0949.68144
[62]	Yao, Y. Y., Information granulation and rough set approximation, International Journal of Intelligent Systems, 16, 87-104 (2001) · Zbl 0969.68079
[63]	Yao, Y. Y., Notes on rough set approximations and associated measures, Journal of Zhejiang Ocean University (Natural Science), 29, 399-410 (2010)
[64]	Yao, Y. Y., Three-way decisions with probabilistic rough sets, Information Sciences, 180, 341-353 (2010)
[65]	Yao, Y. Y., The superiority of three-way decisions in probabilistic rough set models, Information Sciences, 181, 1080-1096 (2011) · Zbl 1211.68442
[66]	Zadeh, L., Fuzzy sets and information granularity, Advances in Fuzzy Set Theory and Applications, 11, 3-18 (1979)