{'fraction_non_alphanumeric': 0.03148069579974544, 'fraction_numerical': 0.013237165888841747, 'mean_word_length': 4.931555108203321, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An improved approach to attribute reduction with covering rough sets

Attribute reduction is viewed as an important preprocessing step for pattern recognition and data mining. Most of researches are focused on attribute reduction by using rough sets. Recently, Tsang et al. discussed attribute reduction with covering rough sets in the paper [E. C.C. Tsang, D. Chen, Daniel S. Yeung, Approximations and reducts with covering generalized rough sets, Computers and Mathematics with Applications 56 (2008) 279-289], where an approach based on discernibility matrix was presented to compute all attribute reducts. In this paper, we provide an improved approach by constructing simpler discernibility matrix with covering rough sets, and then proceed to improve some characterizations of attribute reduction provided by Tsang et al. It is proved that the improved discernible matrix is equivalent to the old one, but the computational complexity of discernible matrix is greatly reduced.


Introduction
Attribute reduction and feature selection have become one of the important steps for pattern recognition and machine learning tasks. Classical rough set theory [19] is a mathematical tool for handling data sets with imprecision and uncertainty. It can be employed to study attribute reduction and feature selection in information systems.
Equivalence relations are the mathematical basis for the rough set theory. Based on equivalence relations, objects of a universe can be partitioned into exclusive equivalence classes, which form the basic information granules to approximate arbitrary subset of the 2 universe. The main idea of rough sets is to remove redundant information in data and to make correct decision or classification. Rough set theory has attracted wide attention on the research areas in both of the theory and its applications.
Many types of attribute reductions have been proposed based on classical rough sets such as possible reduct, approximate reduct, α-reduct, μ-decision reduct and so on [9,17,24]. Kryszkiewicz [9] reviewed and compared these five types of attribute reducts in inconsistent systems. In fact, only two of them, possible reduct and μ-decision reduct, are essential because the others are just equivalent to one of them, respectively. In addition, some other reduction methods based on classical rough sets were also proposed in [13,14,22,23,31].
However, equivalence relation in classical rough set theory is still restrictive for many applications, as it is only suitable for handling discrete variables and cannot directly deal with continuous or real-value data. There are large amount of continuous data in real-life applications. For example, a lot of numerical data are faced with on performance analysis and equipment condition monitoring and diagnosis in power systems [20]. When dealing with such numerical attributes by using classical rough sets, they are often discretized firstly into symbol-type attributes as a pretreatment [18]. This type of conversion will bring a major drawback of information loss, thus affecting the accuracy of extracted rules [8]. In order to solve this problem, scholars have proposed a series of extensions of the rough set model [1][2][3][4][5][6][7][8][10][11][12]15,16,[26][27][28][29][30][32][33][34][35]. On the basis of the concept of cover on a universe, Pomykala et al [21] introduced the concepts of lower and upper covering approximation operators in the universe. Afterward many authors conducted detailed study of properties of covering approximation operators [1,15,21,28,[32][33][34][35]. However, few people employ covering rough sets to make research on attribute reduction. Zhu [33] et al investigated reduction of covering elements based on covering rough sets. The reduction of covering elements is referred as to a means to get rid of excessive covering elements in a cover under the condition that keeps the upper and lower approximation of an arbitrary subset invariant. So what they meant about reduction is not the strict sense of attribute reduction. In [28] a pioneering work related to attribute reduction with covering rough sets was conducted, where the authors constructed discernible matrix and analyzed its some important properties. In view of the discernible matrix, an approach to compute 3 all the reducts was developed. However, the formula for computing discernible matrix is very complicated, and so should be difficultly applied in practice.
In this paper, we revisit the discernible-matrix approach to attribute reduction with covering rough sets. More concretely, we reconstruct discernible matrix of attribute reduction. Compared with the approach in [28], the computational complexity of improved approach is lower. In addition, we improve the theorems in [28] that describe the properties of discernible matrix and attribute reduction with covering rough sets. The theory improved here is helpful in establishing a basic foundation of covering rough sets and broadening its applications.
The remainder of this paper is structured as follows. In Section 2, we recall and define some basic notions related to covering rough sets. In Section 3, we reconstruct discernible matrix of attribute reduction based on covering rough sets and improve some characterizations of the structure and properties of attribute reduction. In Section 4, we conclude the paper with a summary.

Some notions related to covering rough sets
Attribute reduction is an important application field of rough set theory. However, in real world there are lots of data sets that cannot be handled well by classical rough sets.
In light of this, similarity relation rough sets [26], dominance rough sets [3,4], and even neighborhood rough sets [6,10] were developed one by one. All these models induce covers of a universe, instead of partitions, and thus can be categorized into covering rough sets, which are more general than classical rough sets and can handle more complex tasks.
Granulating information in data sets is the basis of rough set theory. The granulated information forms elementary information granules to approximately describe arbitrary concepts in approximation spaces. Covering rough set theory employs the notion of covers to granulate information in data sets.
The relationships between information granules have the following properties.
(1) Reflexivity: xU (3) Transitivity: ,, In classification and regression learning, we are usually confronted with the task of approximating some concepts with provided knowledge. With information granules in covering approximation spaces, any concepts can be approximated.

Definition 2.3 [28] Let ( , )
UC be a covering approximation space. XU  is an arbitrary subset of the universe. The covering lower and upper approximations of X are defined as ( ) Definition 2.4 [28] Suppose U is a finite universe and is also a cover of U , we call it the induced cover of Δ .
Clearly,   . The relationships between information granules in ) (Δ Cov also have such properties as reflexivity, anti-symmetry and transitivity.
Definition 2.5 Let U be a universe and is called a covering information system; Δ is called a conditional covering (attribute) set.
be a covering information system and Δ Definitions 2.5 and 2.6 are natural extensions of the corresponding concepts in classical rough set theory by substituting equivalence relations with covers. It can be seen from the two definitions that the purpose for reducing conditional covering set is to find a minimal covering subset that keeps original information granularity invariant.

Attribute reduction based on discernbility matrix
In this section, we first develop some theorems to describe discernbility between objects. Then, we reconstruct the discernible matrix of attribute reduction based on covering rough sets and improve some characterizations of basic properties of attribute reduction.
Proof. Straightforward. □ The above theorem implies that an indispensable cover can be characterized by the discernibility between objects. That is to say, i C is an indispensable cover if and only if y not belonging to the neighborhood of x with respect to Δ implies y belonging to the neighborhood of x with respect to . This implies that i C is a sole cover that can distinguish the two objects.

Proof. Straightforward. □
This theorem shows that if two objects can be distinguished under the granularity level of () x  , then there is at least a cover Δ i C  such that the two objects are also distinguished under the granularity level of () i Cx, and vice versa. This means that if two objects are not in the same original information granule, i.e. one object is not in the neighborhood of another object with respect to Δ , we can find at least an attribute (cover) to distinguish them.
. Clearly, we have ii c  for any i xU  . As an attribute and its induced cover are uniquely determined by each other, the discernibility matrix gives the description of all the attribute subsets that can distinguish any two objects. If two objects don't belong to one information granule at original level of granularity, then they must be distinguished by some attributes. This idea is consistent with the viewpoint in classical rough sets. Besides, covering and classical rough sets bear some formal resemblance between discernibility matrices. Thus the proposed approach is a generalization of classical rough sets.
In [28] the reduction method based on discernibility matrix was also proposed to compute all the reducts. For the sake of comparison, let us review the definition of discernibility matrix introduced there. x we denote a n n  matrix () ij w , called the discernibility matrix of In fact, the two types of discernbility matrices are equivalent. Next, we present the proof of their equivalence. ( From the first case and the fact , there must exist another cover where n and m are the numbers of samples and attributes, respectively. This justifies that our proposed method is simpler than the method in [28]. From theoretical viewpoint, Our study on this topic plays the same important role as the researches [25,30] in traditional and generalized rough sets.
The following theorem is used to study the properties of the discernibility matrix.
be the discernibility matrix of ( , ) Δ U and 12 { , , } Δ n C C C   . Then the following statements hold:   In [28], Proposition 4.5 says that the core of attribute reduction is computed by Here we improve it based on the discernible matrix in Definition 3.1 as follows.
. By Proposition 3.1 and The following theorem is an improved version of Proposition 4.6 in [28] . represents the disjunction operation among elements in ij c . By using the function, we can compute all the reducts of covering information systems. The following example is employed to compare our idea with that in [28].
Example 3.1. Let consider an example of house evaluation problem provided in [28].

Conclusion
Covering rough sets are an important extension of classical rough sets. In this paper, we have redeveloped a relatively simple formula for computing discernible matrix. Although the proposed discernible matrix is equivalent to the one introduced in [28] and the results may be the same in computing attribute reducts, the computational complexity of our discernible matrix is lower. In addition, we have improved some characterizations of attribute reduction with covering rough sets. Compared with the results in [28], the improved ones are more concise, more profound to see through the nature of attribute reduction. These results obtained in the paper accord to the corresponding ones in classical rough sets and may help us develop more efficient approaches to attribute reductions, and so deal with more complex data sets.