978-1-4799-5150-5/14/$31.00 ©2014 IEEE 480
2014 10th International Conference on Natural Computation
Dynamic Reducts Computation Analysis Based on Rough Sets
Carine Pierrette Mukamakuza
School of Information Science and Engineering
Central South University
Changsha, China
E-mail: kuzacari808@gmail.com
Jiayang Wang
School of Information Science and Engineering
Central South University
Changsha, China
E-mail: csuwjy@mail.csu.edu.cn
Li Li
Shenzhen Graduate School
Harbin Institute of Technology
Shenzhen, China
Abstract—In this paper analysis of reduction and dynamic
reducts of an information data is presented. The method of
reduction in information system is explained first, the
information was assumed to be in a two-dimension or in a
matrix form. A discernibility matrix of the data was
constructed, and then all reducts from that matrix were found.
The best (optimum) reduct was selected from all reducts; that
was achieved by considering the one with the highest level of
frequency by using Java programming and Weka tool. Three
methods of dynamic reducts computation are introduced
namely: The new type of Reduct in the object-oriented rough
set model which is called dynamic reduct , the method of
dynamic reduct calculation based on calculating of reduct
traces and the generation F-dynamic reduct using cascading
Hashes. The analysis of those three methods led to their
improvement through adding one step in each algorithm which
was the method of getting the optimum reducts from all
reducts calculated in first steps of each algorithm. As result,
the dynamic reducts were generated from optimum reducts
and not from all reducts. Thus by generating an improved
dynamic reducts, improvement of those three methods for
calculation of dynamic reducts is achieved.
Keywords-component: Information system; Optimum reduct;
Dynamic reduct ; knowlegde discovery
I. INTRODUCTION
The last few years have seen a remarkable growth in the
use of rough set theory and applications for solving various
problems in engineering fields. This is mainly because
optimum reduct and dynamic reduct algorithms have seen
tremendous improvements in the last few years, allowing
larger problem instances to be solved in different
applications domains such as computer intelligence,
mechanical, electrical, electronics, medical. Rough set theory
deals with reasoning and approximation about data. In
approximation aspect, the lower approximation and the
upper approximation are the basic concepts by
indiscernibility relations which illustrate set-theoretic
approximations of any given subset of data. The essential
part of an information system is the reduct, from which all
objects discernible are discerned in the original information
system. Another important part is the core which is a
common part of all reducts. The discernibility matrix is used
to compute the core and reducts.
The purpose of this work is to introduce three methods
of dynamic reducts computation namely: a dynamic reduct in
the object–oriented rough set models; dynamic reducts based
on calculating reduct traces; and the generation (F,ε)-
dynamic reduct using cascading Hashes. Method of
calculating the optimum reducts which improves the three
methods above is also proposed.
Rough set theory is the foundation of rough system
theory and applications. Rough set theory, introduced by
Professor Z.Pawlak in the early 1980s [1], is a new
mathematical tool to deal with imprecise, uncertain, and
vague information [2]. It has been widely applied in many
fields such as machine learning, data mining, artificial
intelligence, etc. Even though the research of knowledge
reduct in rough set is mostly based on complete information
system, it is meaningful to extend rough set theory into
incomplete information system and design an efficient
knowledge reduct algorithm.
II. P
RELIMINARY CONCEPTS OF ROUGH SET THEORY
A. Definitions
1) Information System
Rough Set approach can be presented to incomplete
information systems, i.e. to systems in which attribute values
for objects may be unknown (missing, null) and this theory’s
main concern can be devoted to finding rules from such
systems. A theory of Rough Set (RS) introduced by Z.
Pawlak defines formally an information system as a system
The project supported by National Natural Science Foundation of China,Grant No. 61173052.
The project supported by Hunan Provincial Natural Science Foundation of China,Grant No. 14JJ4007.
——————————————————————————————————————————————————————————————————————————————