Search

Matroid theory is a useful tool for the combinatorial optimization issue in data mining, machine learning and knowledge discovery. Recently, combining matroid theory with rough sets is becoming interesting. In this paper, rough set approaches are used to investigate an important class of matroids, transversal matroids. We first extend the concept of upper approximation number functions in rough set theory and propose the notion of generalized upper approximation number functions on a set system. By means of the new notion, we give some necessary and sufficient conditions for a subset to be a partial transversal of a set system. Furthermore, we obtain a new description of a transversal matroid by the generalized upper approximation number function. We show that a transversal matroid can be induced by the generalized upper approximation number function which can be decomposed into the sum of some elementary generalized upper approximation number functions. Conversely, we also prove that a generalized upper approximation number function can induce a transversal matroid. Finally, we apply the generalized upper approximation number function to study the relationship among transversal matroids. [ABSTRACT FROM AUTHOR]

Uncertainty measures are an important tool for analyzing data. There is the uncertainty of a rough set caused by its boundary region in rough set models. Thus the uncertainty measurement issue is also an important topic for rough set theory. Shannon entropy has been introduced into rough set theory. However, there are relatively few studies on the uncertainty measure in generalized rough set models. We know that the boundary region of a rough set is closely related to the upper and lower approximations in rough set models. In this paper, from the viewpoint of the upper and lower approximations, we propose new uncertainty measures, the upper rough entropy and the lower rough entropy, in generalized rough set models. Then we focus on the investigations of the upper rough entropy, and give the concepts of the upper joint entropy, the upper conditional entropy and the mutual information with respect to a general binary relation. Some important properties of these measures are obtained. The connections among these measures are given. Furthermore, comparing with the existing uncertainty measures, the upper rough entropy has high distinguishing degree. Theoretical analysis and experimental results show that the proposed entropy is better effective than some existing measures. [ABSTRACT FROM AUTHOR]

Rough set theory is an important technique in knowledge discovery in databases. In covering-based rough sets, seven types of rough set models were established in recent years. This paper defines the concept of maximal description of an element, and further explores the properties and structures of several types by means of the concepts of maximal description and minimal description. Finally, we study the relationship between covering-based rough sets and the generalized rough sets based on binary relation. [ABSTRACT FROM AUTHOR]