An interval set model for learning rules from incomplete information table. (English) Zbl 1242.68235

Li, Huaxiong; Wang, Minhong; Zhou, Xianzhong; Zhao, Jiabao

Int. J. Approx. Reasoning 53, No. 1, 24-37 (2012).

Summary: A novel interval set approach is proposed in this paper to induce classification rules from incomplete information table, in which an interval-set-based model to represent the uncertain concepts is presented. The extensions of the concepts in incomplete information table are represented by interval sets, which regulate the upper and lower bounds of the uncertain concepts. Interval set operations are discussed, and the connectives of concepts are represented by the operations on interval sets. Certain inclusion, possible inclusion, and weak inclusion relations between interval sets are presented, which are introduced to induce strong rules and weak rules from incomplete information table. The related properties of the inclusion relations are proved. It is concluded that the strong rules are always true whatever the missing values may be, while the weak rules may be true when missing values are replaced by some certain known values. Moreover, a confidence function is defined to evaluate the weak rule. The proposed approach presents a new view on rule induction from incomplete data based on interval set.

MSC:

68T05	Learning and adaptive systems in artificial intelligence
68T37	Reasoning under uncertainty in the context of artificial intelligence

Keywords:

interval set; interval extension; incomplete information table; rule induction

Software:

C4.5

References:

[1]	Bazan, J. G.; Latkowski, R.; Szczuka, M. S., Missing template decomposition method and its implementation in rough set exploration system, (Greco, S.; Hata, Y.; Hirano, S.; Inuiguchi, M.; Miyamoto, S.; Nguyen, H. S.; Slowinski, R., Proceedings of the 5th International Conference on Rough Sets and Current Trends in Computing. Proceedings of the 5th International Conference on Rough Sets and Current Trends in Computing, LNAI, vol. 4259 (2006), Springer: Springer Berlin), 254-263 · Zbl 1162.68684
[2]	Bustince, H., Indicator of inclusion grade for intervalvalued fuzzy sets application to approximate reasoning based on interval-valued fuzzy sets, International Journal of Approximate Reasoning, 23, 137-209 (2000) · Zbl 1046.68646
[3]	Cendrowska, J., PRISM: an algorithm for inducing modular rules, International Journal of Man-Machine Studies, 27, 4, 349-370 (1987) · Zbl 0638.68110
[4]	Clark, P.; Niblett, T., The CN2 induction algorithm, Machine Learning, 3, 4, 261-283 (1989)
[5]	Cornelis, C.; Deschrijver, G.; Kerre, E. E., Implication in intuitionistic fuzzy and interval-valued fuzzy set theory: construction, classification, application, International Journal of Approximate Reasoning, 35, 1, 55-95 (2004) · Zbl 1075.68089
[6]	Cui, W.; Blockley, D. I., Interval probability theory for evidential support, International Journal of Intelligent Systems, 5, 2, 183-192 (1990) · Zbl 0706.68092
[7]	Denoeux, T.; Younes, Z.; Abdallah, F., Representing uncertainty on set-valued variables using belief functions, Artificial Intelligence, 174, 7-8, 479-499 (2010) · Zbl 1209.68542
[9]	Gediga, G.; Düntsch, I., Maximum consistency of incomplete data via non-invasive imputation, Artificial Intelligence Review, 19, 4, 93-107 (2003)
[10]	Ghahramani, Z.; Jordan, M. I., Supervised learning from incomplete data via an EM approach, (Cowan, J. D.; Tesauro, G.; Alspector, J., Advances in Neural Information Processing Systems, vol. 6 (1994), Morgan Kaufman: Morgan Kaufman San Mateo, CA), 120-127
[12]	Grzymala-Busse, J. W., On the unknown attribute values in learning from examples, (Ras, Z.; Zemankova, M., Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems. Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems, LNAI, vol. 542 (1991), Springer: Springer Berlin), 368-377
[13]	Grzymala-Busse, J. W.; Hu, M., A comparison of several approches to missing attribute values in data mining, (Ziarko, W.; Yao, Y., Proceedings of the 2nd International Conference on Rough Sets and Current Trends in Computing. Proceedings of the 2nd International Conference on Rough Sets and Current Trends in Computing, LNAI, vol. 2005 (2000), Springer: Springer Berlin), 378-385 · Zbl 1014.68558
[14]	Grzymala-Busse, J. W.; Grzymala-Busse, W. J., An experimental comparison of three rough set approaches to missing attribute values, (Peters, J.; Skowron, A.; Duntsch, I.; Grzymala-Busse, J.; Orlowska, E.; Polkowski, L., LNCS Transactions on Rough Sets VI. LNCS Transactions on Rough Sets VI, LNCS, vol. 4374 (2007), Springer: Springer Berlin), 31-50 · Zbl 1058.68659
[15]	Grzymala-Busse, J. W., Data with missing attribute values: generalization of indiscernibility relation and rule induction, (Peters, J.; Skowron, A.; Grzymala-Busse, J.; Kostek, B.; Swiniarski, R.; Szczuka, M., LNCS Transactions on Rough Sets I. LNCS Transactions on Rough Sets I, LNCS, vol. 3100 (2004), Springer: Springer Berlin), 78-95 · Zbl 1104.68759
[16]	Hall, J. W.; Blockley, D. I.; Davis, J. P., Uncertain inference using interval probability theory, International Journal of Approximate Reasoning, 19, 3, 247-264 (1998) · Zbl 0944.68174
[17]	Kryszkiewicz, M., Rough set approach to incomplete information systems, Information Sciences, 112, 39-49 (1998) · Zbl 0951.68548
[18]	Kryszkiewicz, M., Rules in incomplete information systems, Information Sciences, 113, 271-292 (1999) · Zbl 0948.68214
[19]	Laurikkala, J.; Kentala, E.; Juhola, M.; Pyykkö, I.; Lammi, S., Usefulness of imputation for the analysis of incomplete otoneurologic data, International Journal of Medical Informatics, 58-59, 235-242 (2000)
[20]	Leung, Y.; Fischer, M. M.; Wu, W. Z.; Mi, J. S., A rough set approach for the discovery of classification rules in interval-valued information systems, International Journal of Approximate Reasoning, 47, 2, 233-246 (2008) · Zbl 1184.68409
[21]	Li, H. X.; Yao, Y. Y.; Zhou, X. Z.; Huang, B., A two-phase model for learning rules from incomplete data, Fundamenta Informaticae, 94, 2, 219-232 (2009) · Zbl 1192.68527
[22]	Li, H. X.; Yao, Y. Y.; Zhou, X. Z.; Huang, B., Two-phase rule induction from incomplete data, (Wang, G.; Li, T.; Grzymala-Busse, J.; Miao, D.; Skowron, A.; Yao, Y., Proceedings of the 3rd International Conference on Rough Sets and Knowledge Technology. Proceedings of the 3rd International Conference on Rough Sets and Knowledge Technology, LNAI, vol. 5009 (2008), Springer: Springer Berlin), 47-54
[23]	Li, H. X.; Zhou, X. Z.; Yao, Y. Y., Missing values imputation hypothesis: An experimental evaluation, (Baciu, G.; Wang, Y.; Yao, Y.; Kinsner, W.; Chan, K.; Zadeh, L., Proceedings of the 8th International Conference on Cognitive Informatics (2009), IEEE CS Press: IEEE CS Press Los Alamitos), 275-280
[24]	Mitchell, T. M., Generalization as search, Artificial Intelligence, 18, 203-226 (1982)
[25]	Mitchell, T. M., Machine Learning (1997), McGraw-Hill: McGraw-Hill New York · Zbl 0913.68167
[26]	Moore, R. E., Interval Analysis (1966), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0176.13301
[27]	Pawlak, Z., Rough Sets: Theoretical Aspects of Reasoning about Data (1991), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, The Netherlands · Zbl 0758.68054
[28]	Polkowski, L.; Artiemjew, P., Granular classifiers and missing values, (Zhang, D.; Wang, Y.; Kinsner, W., Proceedings of the 6th International Conference on Cognitive Informatics (2007), IEEE CS Press: IEEE CS Press New York), 186-194
[29]	Qian, Y. H.; Dang, C. Y.; Liang, J. Y.; Zhang, H. Y.; Ma, J. M., On the evaluation of the decision performance of an incomplete decision table, Data and Knowledge Engineering, 65, 3, 373-400 (2008)
[30]	Qian, Y. H.; Liang, J. Y., Combination entropy and combination granulation in incomplete information systems, Lecture Notes in Artificial Intelligence, 4062, 184-190 (2006) · Zbl 1196.68269
[31]	Quinlan, J. R., C4.5: Programs for Machine Learning (1993), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[32]	Stefanowski, J.; Tsoukiàs, A., On the extension of rough sets under incomplete information, International Journal of Intelligent System, 16, 29-38 (1999)
[33]	Wang, G. Y., Extension of rough set under incomplete information systems, Journal of Computer Research and Development, 39, 10, 1238-1243 (2002), (in Chinese)
[34]	Wong, S. K.M.; Wang, L. S.; Yao, Y. Y., On modeling uncertainty with interval structures, Computational Intelligence, 11, 2, 406-426 (1995)
[35]	Yager, R. R.; Kreinovich, V., Decision making under interval probabilities, International Journal of Approximate Reasoning, 22, 3, 195-215 (1999) · Zbl 1041.91500
[36]	Yao, J. T.; Yao, Y. Y., Induction of classification rules by granular computing, (Alpigini, J.; Peters, J.; Skowron, A.; Zhong, N., Proceedings of the 3rd International Conference on Rough Sets and Current Trends in Computing. Proceedings of the 3rd International Conference on Rough Sets and Current Trends in Computing, LNAI, vol. 2475 (2002), Springer: Springer Berlin), 331-338 · Zbl 1013.68514
[37]	Yao, Y. Y., Concept formation and learning: a cognitive informatics perspective, (Chan, C.; Kinsner, W.; Wang, Y.; Miller, D., Proceedings of the 3rd IEEE International Conference on Cognitive Informatics (2004), IEEE CS Press: IEEE CS Press New York), 42-51
[40]	Yao, Y. Y.; Zhong, N., An analysis of quantitative measures associated with rules, (Wu, X.; Ramamohanarao, K.; Korb, K., Proceedings of the 2nd Pacific-Asia Conference on Knowledge Discovery and Data Mining. Proceedings of the 2nd Pacific-Asia Conference on Knowledge Discovery and Data Mining, LNAI, vol. 1974 (1999), Springer: Springer Berlin), 479-488
[41]	Zhang, H. Y.; Zhang, W. X.; Wu, W. Z., On characterization of generalized interval-valued fuzzy rough sets on two universes of discourse, International Journal of Approximate Reasoning, 51, 1, 56-70 (2009) · Zbl 1209.68552
[42]	Zhang, S. C.; Qin, Z. X.; Ling, C. X.; Sheng, S. L., Missing is useful: missing values in cost-sensitive decision trees, IEEE Transactions on Knowledge and Data Engineering, 17, 1689-1693 (2005)
[43]	Zadeh, L. A., The concept of a linguistic variable and its application to approximate reasoning (Part I), Information Science, 8, 3, 199-249 (1975) · Zbl 0397.68071
[44]	Zadeh, L. A., The concept of a linguistic variable and its application to approximate reasoning (Part II), Information Science, 8, 4, 301-357 (1975) · Zbl 0404.68074
[45]	Zeng, W. Y.; Li, H. X., Relationship between similarity measure and entropy of interval valued fuzzy sets, Fuzzy Sets and Systems, 157, 11, 1477-1484 (2006) · Zbl 1093.94038