Classification systems based on rough sets under the belief function framework.

*(English)*Zbl 1242.68340Summary: In this paper, we present two classification approaches based on rough sets (RS) that are able to learn decision rules from uncertain data. We assume that the uncertainty exists only in the decision attribute values of the decision table (DT) and is represented by the belief functions. The first technique, named belief rough set classifier (BRSC), is based only on the basic concepts of the rough sets. The second, called belief rough set classifier, is more sophisticated. It is based on generalization distribution table (BRSC-GDT), which is a hybridization of the generalization distribution table and the rough sets (GDT-RS). The two classifiers aim at simplifying the uncertain decision table (UDT) in order to generate significant decision rules for classification process. Furthermore, to improve the time complexity of the construction procedure of the two classifiers, we apply a heuristic method of attribute selection based on rough sets. To evaluate the performance of each classification approach, we carry experiments on a number of standard real-world databases by artificially introducing uncertainty in the decision attribute values. In addition, we test our classifiers on a naturally uncertain web usage database. We compare our belief rough set classifiers with traditional classification methods only for the certain case. Besides, we compare the results relative to the uncertain case with those given by another similar classifier, called the belief decision tree (BDT), which also deals with uncertain decision attribute values.

##### MSC:

68T37 | Reasoning under uncertainty in the context of artificial intelligence |

##### Keywords:

rough sets; generalization distribution table; belief functions; uncertainty and classification##### Software:

C4.5
PDF
BibTeX
Cite

\textit{S. Trabelsi} et al., Int. J. Approx. Reasoning 52, No. 9, 1409--1432 (2011; Zbl 1242.68340)

Full Text:
DOI

##### References:

[1] | An, A.; Chan, C.; Shan, N.; Cercone, N.; Ziarko, W., Applying knowledge discovery to predict water-supply consumption, IEEE expert, 12, 4, 72-78, (1997) |

[2] | Bauer, M., Approximations algorithm and decision making in the dempster – shafer theory of evidence – an empirical study, Ijar, 17, 2-3, 217-237, (1997) · Zbl 0939.68109 |

[3] | S. Ben Hariz, Z. Elouedi, K. Mellouli, Clustering approach using belief function theory, in: 12th International Conference, AIMSA 2006, Varna, Bulgaria, September 12-15, LNAI 4183, 2006, pp. 162-171. · Zbl 1158.68441 |

[4] | Bosse, E.; Jousseleme, A.L.; Grenier, D., A new distance between two bodies of evidence, Information fusion, 2, 91-101, (2001) |

[5] | Dasarathy, B.V., Nearest neighbour (NN) norms: NN pattern classification techniques, (1991), IEEE Computer Society Press Los Alamitos, CA |

[6] | Denoeux, T., A k-nearest neighbor classification rule based on dempster – shafer theory, IEEE transactions on systems, man and cybernetics, 25, 5, 804-813, (1995) |

[7] | T. Denoeux, M. Skarstien-Bajanger, Induction of decision trees form partially classified data using belief functions, in: IEEE International Conference on Systems, Nashville, USA, vol. 4, 2000, pp. 2923-2928. |

[8] | Denoeux, T., A neural network classifier based on dempster – shafer theory, IEEE transactions on systems, man and cybernetics, part A, 30, 2, 131-150, (2000) |

[9] | Dong, J.Z.; Zhong, N.; Ohsuga, S., Probabilistic rough induction: the GDS-RS methodology and algorithms, (), 621-629 |

[10] | Dubois, D., Putting rough sets and fuzzy sets together, (), 203-232 |

[11] | Elouedi, Z.; Mellouli, K.; Smets, P., Belief decision trees: theoretical foundations, International journal of approximate reasoning, 28, 2-3, 91-124, (2001) · Zbl 0991.68088 |

[12] | Z. Elouedi, K. Mellouli, P. Smets, A pre-pruning method in belief decision trees, in: The Ninth International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU), Annecy, France, vol. 1, 2002, pp. 579-586. |

[13] | Elouedi, Z.; Mellouli, K.; Smets, P., Assessing sensor reliability for multisensor data fusion within the transferable belief model, IEEE transactions on systems, man and cybernetics, 34, 1, 782-787, (2004) |

[14] | Fan, T.F.; Liau, C.J.; Liu, D.R., Dominance-based fuzzy rough set analysis of uncertain and possibilistic data tables, International journal of approximate reasoning, 52, 9, 1283-1297, (2011) · Zbl 1242.68325 |

[15] | Fixen, D.; Mahler, R.P.S., The modified dempster – shafer approach to classification, IEEE transactions on systems, man and cybernetics A, 27, 1, 96-104, (1997) |

[16] | Friedman, N.; Geiger, D.; Goldszmidt, M., Bayesian network classifiers, Machine learning, 29, 131-163, (1997) · Zbl 0892.68077 |

[17] | J.W. Grzymala-Busse, Rough set strategies to data with missing attribute values, in: Workshop Notes, Foundations and New Directions of Data Mining, The 3rd International Conference on Data Mining, Melbourne, FL, 2003, pp. 56-63. |

[18] | J.W. Grzymala-Busse, S. Siddhaye, Rough set approaches to rule induction from incomplete data, in: Proceedings of the IPMU’2004, Perugia, Italy, July 4-9, vol. 2, 2004, pp. 923-930. |

[19] | T.P. Hong, L.H. Tseng, B.C. Chien, Learning fuzzy rules from incomplete quantitative data by rough sets, IEEE, 2002, pp. 1438-1442. |

[20] | Maji, P.; Paul, S., Rough set based maximum relevance-maximum significance criterion and gene selection from microarray data, International journal of approximate reasoning, 52, 3, 408-426, (2011) |

[21] | Murphy, C.K., Combining belief functions when evidence conflicts, Decision support systems, 29, 1-9, (2000) |

[22] | Lingras, P.; West, C., Interval set clustering of web users with rough k-means, Journal of intelligent information systems, 23, 1, 5-16, (2004) · Zbl 1074.68586 |

[23] | Pawlak, Z., Rough sets, International journal of computer and information sciences, 11, 5, 341-356, (1982) · Zbl 0501.68053 |

[24] | Pawlak, Z., Rough sets: theoretical aspects of reasoning about data, (1991), Kluwer Academic Publishing Dordrecht · Zbl 0758.68054 |

[25] | Quinlan, J.R., C4.5: programs for machine learning, (1993), Morgan Kaufman San Mateo, CA |

[26] | Shafer, G., A mathematical theory of evidence, (1976), Princeton University Press Princeton, NJ · Zbl 0359.62002 |

[27] | Skowron, A.; Rauszer, C., The discernibility matrices and functions in information systems, (), 331-362 |

[28] | A. Skowron, J.W. Grzymala-Busse, From rough set theory to evidence theory, in: Advances in the Dempster-Shafer Theory of Evidence, New York, 1994, pp. 193-236. |

[29] | Smets, P.; Kennes, R., The transferable belief model, Artificial intelligence, 66, 2, 191-234, (1994) · Zbl 0807.68087 |

[30] | Smets, P., The transferable belief model for quantified belief representation, (), 207-301 · Zbl 0939.68112 |

[31] | Smets, P., Application of belief transferable belief model to diagnostic problems, International journal of intelligent systems, 13, 2-3, 127-157, (1998) · Zbl 0900.68393 |

[32] | Tian, D.; Zeng, X.J.; Keane, J., Core-generating approximate minimum entropy discretization for rough set feature selection in pattern classification, International journal of approximate reasoning, 52, 6, 863-880, (2011) |

[33] | Trabelsi, S.; Elouedi, Z.; Mellouli, K., Pruning belief decision tree methods in averaging and conjunctive approaches, International journal of approximate reasoning, 46, 91-124, (2007) · Zbl 1185.68718 |

[34] | S. Trabelsi, Z. Elouedi, Learning decision rules from uncertain data using rough sets, in: The 8th International FLINS Conference on Computational Intelligence in Decision and Control, Madrid, Spain, September 21-24, World Scientific, 2008, pp. 114-119. |

[35] | S. Trabelsi, Z. Elouedi, P. Lingras, Belief rough set classifier, Canadian AI 2009, LNAI 5549, 2009, pp. 257-261. |

[36] | S. Trabelsi, Z. Elouedi, P. Lingras, Rule discovery process based on rough sets under the belief function framework, IPMU 2010, LNAI 6178, 2010, pp. 726-736. |

[37] | Trabelsi, S.; Elouedi, Z., Heuristic method for attribute selection from partially uncertain data using rough sets, International journal of general systems, 39, 3, 271-290, (2010) · Zbl 1190.68063 |

[38] | S. Trabelsi, Z. Elouedi, P. Lingras, Belief rough set classification for web mining based on dynamic core, in: The Tenth International Conference on Intelligent Systems Design and Applications (ISDA), Cairo, Egypt, November 29, December 1, 2010, pp. 403-408. |

[39] | Vannoorenberghe, P., On aggregating belief decision trees, Information fusion, 5, 2, 179-188, (2004) |

[40] | Zhong, N.; Dong, J.Z.; Ohsuga, S., Using rough sets with heuristics for feature selection, Journal of intelligent information systems, 16, 3, 199-214, (2001) · Zbl 0994.68149 |

[41] | Zhong, N.; Dong, J.Z.; Ohsuga, S., Data mining: a probabilistic rough set approach, Rough sets in knowledge discovery, 2, 127-146, (1998) |

[42] | N. Zhong, J.Z. Dong, S. Ohsuga, Using generalization distribution tables as a hypotheses search space for generalization, in: Proceedings of Fourth International Workshop on Rough Sets, Fuzzy Sets, and Machine Discovery (RSFD-96), 1996, pp. 396-403. |

[43] | Zouhal, L.M.; Denoeux, T., An evidence-theory k-NN rule with parameter optimization, IEEE transactions on systems, man and cybernetics C, 28, 2, 263-271, (1998) |

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.