A Method for Fast Feature Selection Utilizing Cross-Similarity within the Context of Fuzzy Relations

Abbreviations

1  Introduction

With the evolution of information technology, a substantial amount of information is captured in the form of data. These datasets contain a substantial quantity of redundant information. In data mining and model training, these redundant features can increase computational complexity and even result in model distortion, ultimately affecting the model’s predictive capability. Feature selection (or attribute selection, attribute reduction) is a crucial technique to minimize redundant features, aiming to identify the smallest subset of features that retain the distinguishability of the data.

Rough set theory [1] enjoys widespread application across diverse fields [2–4], with feature selection emerging as a particularly prominent research area within its scope. However, a limitation of rough set theory is its inability to handle continuous data directly. When dealing with features with continuous values, discretization is necessary, which can lead to the loss of valuable data information. To address these limitations of traditional rough set theory, Dubois et al. [5] introduced a novel concept by integrating fuzzy sets with rough sets, resulting in the emergence of a fuzzy rough set (FRS). This extension of Pawlak’s rough set model to the fuzzy domain represents a significant advancement in the field. Since then, researchers have conducted thorough investigations into fuzzy rough set theory, further refining its theoretical framework, alleviating constraints in practical applications, mitigating the impact of noisy data, and enhancing its overall robustness. Some researchers [6,7] have endeavored to generalize the fuzzy relationships among samples in fuzzy rough sets, broadening their scope and enhancing the model’s adaptability. Additionally, they have gone beyond the traditional definitions of the upper and lower approximation operators, giving the model a more comprehensive and flexible framework. These innovative extensions not only increase the model’s flexibility but also enable it to handle a wider range of practical applications with greater precision and adaptability. Despite the efforts of some researchers [8–11] to design more reasonable relationships and upper-lower approximation operations in order to mitigate the impact of noisy data and enhance the robustness of these fuzzy rough set models, they are often accompanied by increased computational complexity. Some researchers [12–16] have broadened the concept of fuzzy partition to fuzzy covering, thereby easing the constraints on the model’s application and enhancing its adaptability to diverse scenarios. This generalization not only facilitates a more flexible application of the model but also empowers it to tackle a broader spectrum of practical problems with enhanced precision and accuracy.

With the evolution of fuzzy rough set theory, numerous feature selection algorithms have emerged, built upon this theory. These algorithms aim to identify and extract salient features from datasets, aiding in their effective representation and interpretation. Jensen et al. [17] introduced the concepts of the fuzzy positive region and the fuzzy-rough dependency function, subsequently developing a feature selection model based on this dependency. Yang et al. [18] proposed a granular matrix and a granular reduction model, informed by fuzzy β-covering theory. Huang et al. [19,20] introduced a novel discernibility measure and a novel fitting model for attribute reduction, utilizing the fuzzy β-neighborhood to capture the distinguishing power of a fuzzy covering family. Huang et al. [21] devised a robust rough set model that integrates fuzzy rough sets, covering-based rough sets, and multi-granulation rough sets. Furthermore, he successfully employed this model in the realm of feature selection. Wan et al. [22] proposed a novel interactive and complementary feature selection approach, which is based on the fuzzy multi-neighborhood rough set model, specifically designed for use with fuzzy and uncertain data. Hu et al. [23] developed a fuzzy multi-objective feature selection method, incorporating a fuzzy dominance relationship and particle swarm optimization. Deng et al. [24] formulated the dual similarity by leveraging the concept of neighborhood fuzzy entropy, and subsequently utilized it for feature selection in label distribution learning. Dai et al. [25] introduced the concept of multi-fuzzy β-covering approximation spaces and subsequently proposed a forward greedy fuzzy β-covering reduction algorithm, which is based on the monotone conditional entropy in a multi-fuzzy β-covering approximation space.

Current feature selection algorithms predominantly employ forward greedy feature selection, that follows a sequential process, consisting of several distinct steps:

1)   Determine an evaluation metric.

2)   Model initialization: commences with an empty set as the selected feature subset and a candidate feature subset consisting of all features.

3)   Feature selection: in each iteration, incorporate one feature from the candidate feature subset to the already selected feature subset according to the evaluation metric. This process continues until the stopping criteria are satisfied.

When dealing with a dataset containing n features and m samples, the forward greedy feature selection algorithm, in the worst-case scenario, necessitates the calculation of the evaluation metric n(n−1)/2 times. Moreover, for each evaluation of the evaluation metric, the calculation of relationships between every pair of samples in the dataset is essential, which necessitates calculating m2 relationships between samples, such as distances or similarities. Consequently, the time complexity of these algorithms typically lies in the order of O(m2n2) or higher. A significant challenge faced by these feature selection algorithms is their high computational complexity, which makes it challenging for them to effectively handle large sample sizes or high-dimensional data in practical settings.

Through rigorous research and meticulous analysis, we have identified the following issues with existing uncertainty measures and their corresponding feature selection algorithms:

1)   Existing feature selection algorithms must consider the relationships between all samples when calculating uncertainty measures (based on dependency or conditional information entropy).

2)   Existing sample relationships may exhibit weak associations due to noisy data, which can result in the selection of redundant features.

3)   Existing feature selection algorithms struggle to process large sample sizes or high-dimensional datasets effectively due to their high computational complexity.

Drawing upon the insights obtained, we introduce a novel and efficient feature selection algorithm that is grounded in cross-similarity. This algorithm represents a significant advancement in addressing the above challenges associated with feature selection. The primary contributions of this paper are outlined as follows:

1)   We establish a fuzzy binary relation known as the “cross-similarity relation”, which is highly sensitive to samples and relationships that impact the uncertainty of the decision tables while ignoring samples that are already consistent in the decision table.

2)   Using the cross-similarity relation as the uncertainty measure, we propose a new feature selection algorithm. Compared to existing feature selection algorithms, our algorithm reduces the time complexity from O(m2n2) to O(mn2).

3)   To mitigate the impact of noise-induced weak relationships, we introduce a truncation parameter that effectively reduces the influence of noisy data on the feature selection algorithm.

The paper is organized as follows: Section 2 covers the basics of similar relations and fuzzy rough sets. Section 3 introduces cross-similarity relations and their significance, along with their key properties. Section 4 details our new forward greedy feature selection model using fuzzy cross-similarity for data analysis. Section 5 presents experiments proving our method’s effectiveness, stability, and efficiency. Finally, Section 6 summarizes our findings, limitations of the algorithm, and further research directions.

2  Preliminaries

In this section, we will delve into the fundamental concepts of similar relations and fuzzy rough sets.

2.1 Similar Relations

In an information table, a binary relation among samples can be constructed based on the feature set. This binary relation is generally either a similarity relation [5,20,25] or a distance relation [7,26].

Definition 1. Let U={x1,x2,…,xm} be a set of samples, A={a1,a2,…,an} be a set of conditional features, and R={r1,r2,…,rn} be a set of similar relations between samples, where ri∈R(i=1,2,⋅⋅⋅,n) is a fuzzy compatible relation derived from the corresponding feature ai∈A, signifying that ri(xj,xk)∈[0,1](xj,xk∈U) and ri fulfills the properties of reflexivity and symmetry. Then, the pair (U,R) is referred to as a fuzzy compatible relation space (FCRS).

Definition 2. Let (U;R) be an FCRS, x,y∈U,G⊆R, and SimG(x,y)=⋀ri∈Gri(x,y). Then SimG is called a multi-attribute fuzzy compatible relation concerning G.

Definition 3. A parameterized multi-attribute fuzzy compatible relation is defined as follows:

SimGλ(x,y)={0,SimGλ(x,y)<λSimGλ(x,y),SimGλ(x,y)≥λ(1)

where 0≤λ<1.

The truncation parameter λ can be used to eliminate weak similarity relationships introduced by noisy data in the dataset. SimGλ is capable of filtering out weak similarity relationships that exert influence on data uncertainty.

Proposition 4. Let (U,R) be an FCRS. It holds that, for any x,y∈U,

1)   if G1⊆G2⊆R, then SimG1λ(x,y)≥SimG2λ(x,y);

2)   if λ1≤λ2, then SimGλ1(x,y)≥SimGλ2(x,y).

Proof. 1) For any ri∈G1, G1⊆G2⟹ri∈G2, SimG1λ(x,y)=⋀ri∈G1ri(x,y)≥⋀ri∈G2ri(x,y)=SimG2λ(x,y).

2) If SimG(x,y)<λ1≤λ2, then SimGλ1(x,y)=SimGλ2(x,y)=0; if λ1≤SimG(x,y)<λ2, SimGλ1(x,y)=SimG(x,y)>SimGλ2(x,y)=0; if λ1≤λ2≤SimG(x,y), then SimGλ1(x,y)=SimGλ2(x,y)=SimG(x,y). In summary, SimGλ1(x,y)≥SimGλ2(x,y). □

2.2 Fuzzy Rough Sets

Definition 5. Let (U,R) be an FCRS, with D serving as the decision feature. Then the triple (U,R,D) is known as a fuzzy decision table (FDT).

Let U/D={D1,D2,…,Dp} denote the ensemble of equivalent classes that are categorized by D. Di∈U/D(i=1,2,…,p) can also be conceptualized as a fuzzy set, characterized by clear boundaries.

Di(x)={0,x∉Di1,x∈Di(2)

Definition 6. Let (U,R) be an FCRS, ∀A∈ℱ(U), ∀G⊆R, and ∀λ∈[0,1]. Then the lower and upper approximations of A concerning G and λ are respectively as follows:

Apr_Gλ(A)(x)=⋀y∈U{A(y)⋁(1−SimGλ(x,y))}(3)

Apr¯Gλ(A)(x)=⋁y∈U{A(y)⋀SimGλ(x,y)}(4)

Then the quadruple (U,G,A,λ) is called a fuzzy rough set model (FRSM) concerning G and λ.

Proposition 7. Let (U,G,A,λ) be an FRSM. Then the following conclusions hold:

1)   if G1⊆G2⊆G, then Apr_G1λ(A)⊆Apr_G2λ(A);

2)   if λ1≤λ2, then Apr_Gλ1(A)⊆Apr_Gλ2(A).

Proof. 1) Base on Proposition 4, for any x,y∈U, if G1⊆G2⊆G, then SimG1λ(x,y)≥SimG2λ(x,y)⇒Apr_G1λ(A)(x)=⋀y∈U{A(y)⋁(1−SimG1λ(x,y))}≤ ⋀y∈U{A(y)⋁(1−SimG2λ(x,y))}=Apr_G2λ(A)(x)⇒Apr_G1β,λ(A)⊆Apr_G2β,λ(A).

2) Base on Proposition 4, for any x,y∈U, if λ1≤λ2, then SimGλ1(x,y)≥SimGλ2(x,y)⇒Apr_Gλ1(A)(x)=⋀y∈U{A(y)⋁(1−SimGλ1(x,y))}≤ ⋀y∈U{A(y)⋁(1−SimGλ2(x,y))}=Apr_Gλ2(A)(x)⇒Apr_Gλ1(A)⊆Apr_Gλ2(A). □

Proposition 8. Let (U,G,A,λ) be an FRSM. Then the following conclusions hold:

1)   if G1⊆G2⊆G, then Apr¯G1λ(A)⊇Apr¯G2λ(A);

2)   if λ1≤λ2, then Apr¯Gλ1(A)⊇Apr¯Gλ2(A).

Proof of Proposition 8 follows a similar approach to Proposition 7.

Proposition 9. Let (U,G,A,λ) be an FRSM. Then Apr_Gλ(A)⊆A⊆Apr¯Gλ(A).

Proof. Based on Definitions 2.2 and 2.7, for any x∈U, SimGλ(x,x)=1, Apr_Gλ(A)(x)=⋀y∈U{A(y)⋁(1−SimGλ(x,y))}≤A(x)⋁(1−SimGλ(x,x))=A(x) and Apr¯Gλ(A)(x)=⋁y∈U{A(y)⋀SimGλ(x,y)}≥A(x)⋀SimGλ(x,x)=A(x), Apr_Gλ(A)(x)≤A(x)≤Apr¯Gλ(A)(x), so we have Apr_Gλ(A)⊆A⊆Apr¯Gλ(A). □

Definition 10. Let (U,R,D) be an FDT, ∀G⊆R and ∀λ∈[0,1). If Apr_Gλ(Di)(x)=Apr¯Gλ(Di)(x) (∀Di∈U/D), x is referred to as a consistent sample regarding G and λ. If all samples of U demonstrate consistency, the FDT is considered a consistent one.

Proposition 11. Let (U,R,D) be an FDT, ∀A∈ℱ(U), ∀G⊆R, and ∀λ∈[0,1]. Then the following conclusions are true:

1)   if SimGλ(x,y)>0(∀y∈U)⇒Di(x)=Di(y)(i=1,2,…,p), then the sample x is a consistent sample;

2)   if SimGλ(x,y)>0(∀y∈U)⇒∃Di∈U/D such that Di(x)≠Di(y), then the sample x is an inconsistent sample.

Proof. 1) For Di(x)=1, Apr_Gλ(Di)(x)=⋀y∈U{Di(y)∨(1−SimGλ(x,y))}={⋀y∈Di{Di(y)⋁(1−SimGλ(x,y))}}∧{⋀y∈U−Di{Di(y)⋁(1−SimGλ(x,y))}}. For ∈Di⇒Di(y)=1⇒⋀y∈Di{Di(y)⋁(1−SimGλ(x,y))}=1; for y∉Di⇒SimGλ(x,y)=0⇒⋀y∈U−Di{Di(y)⋁(1−SimGλ(x,y))}=1. Apr_Gλ(Di)(x)=1 holds. Apr¯Gλ(Di)(x)=⋁y∈U{Di(y)⋀SimGλ(x,y)}≥Di(x)⋀SimGλ(x,x)=1, and Apr¯Gλ(Di)(x)∈[0,1], so ∀y∈U,Apr¯Gλ(Di)(x)=1=Apr_Gλ(Di)(x).

For Di(x)=0, Apr_Gλ(Di)(x)=⋀y∈U{Di(y)⋁(1−SimGλ(x,y))}≤Di(x)⋁(1−SimGλ(x,x))=0, and Apr_Gλ(Di)(x)≥0, so Apr_Gλ(Di)(x)=0; Apr¯Gλ(Di)(x)=⋁y∈U{Di(y)⋀SimGλ(x,y)}={⋁y∈Di{Di(y)⋀SimGλ(x,y)}}∨{⋁y∈U−Di{Di(y)⋀SimGλ(x,y)}}. For y∈Di⇒SimGλ(x,y)=0⇒⋁y∈Di{Di(y)⋀SimGλ(x,y)}=0; and for y∉Di⇒Di(y)=0⇒⋁y∈U−Di{Di(y)⋀SimGλ(x,y)}=0. Apr¯Gλ(Di)(x)=0 holds. Apr_Gλ(Di)(x)=0=Apr¯Gλ(Di)(x).

Hence, the sample x is a consistent sample.

2) For Di(x)=1, Di(y)=0 and SimGλ(x,y)>0, Apr_Gλ(Di)(x)=⋀y∈U{Di(y)⋁(1−SimGλ(x,y))}≤Di(y)⋁(1−SimGλ(x,y))<1; Apr¯Gλ(Di)(x)=⋁y∈U{Di(y)⋀SimGλ(x,y)}≥Di(x)⋀SimGλ(x,x)=1 and Apr¯Gλ(Di)(x)∈[0,1], Apr¯Gλ(Di)(x)=1>Apr_Gλ(Di)(x).

For Di(x)=0, Di(y)=1 and SimGλ(x,y)>0, Apr_Gλ(Di)(x)=⋀y∈U{Di(y)⋁(1−SimGλ(x,y))}≤Di(x)⋁(1−SimGλ(x,x))=0; Apr¯Gλ(Di)(x)=⋁y∈U{Di(y)⋀SimGλ(x,y)}≥Di(y)⋀SimGλ(x,y)=SimGλ(x,y)>0,soApr¯Gλ(Di)(x)>Apr_Gλ(Di)(x).

Hence, the sample x is an inconsistent sample. □

3  Cross-Similarity

According to Proposition 11, the non-zero similarity of samples that are inconsistent originates from distinct classes. Hence, the focus should be exclusively on the similarity relationships that exist between samples belonging to different classes. Now, it’s time to delve into the intriguing concept of cross-similarity.

Definition 12. Let (U,R,D) be an FDT, G⊆R, x∈U, y∈U, and 0≤λ≤1. The cross-similarity between x and y is defined as follows:

CSG,Dλ(x,y)={0,D(x)=D(y)SimGλ(x,y),D(x)≠D(y).(5)

One can consider the FDT as a graph.

•   The samples in U are visualized as nodes in the graph.

•   The parameterized multi-attribute similarity relations, designated as SimGλ, are conceptually understood as undirected weighted edges connecting nodes within the graph. If SimGλ=0, then there is no edge connecting node x and node y in the graph.

•   The equivalence relations derived from D can be visualized as distinct enclosed areas within the graph.

By Definition 12, we narrow our focus to the similarity relations among samples belonging to distinct target partitions. The term “cross” denotes the intersection of the edge connecting samples of different target partitions and the boundary of enclosed areas, from a graphical perspective.

Definition 13. Let (U,R,D) be an FDT, G⊆R, x∈U, and 0≤λ≤1. The fuzzy set with respect to x is defined as follows:

CSG,Dλ(x)=CSG,Dλ(x)(x1)x1+CSG,Dλ(x)(x2)x2+⋯+CSG,Dλ(x)(xm)xm(6)

The fuzzy set can be conceptualized as the fuzzy information granule of x, with its cardinality represented as follows:

|CSG,Dλ(x)|=∑i∈[1,m]CSG,Dλ(x)(xi)(7)

Let

CSG,Dλ(U)=[CSG,Dλ(x1,x1)CSG,Dλ(x1,x2)⋯CSG,Dλ(x1,xm)0CSG,Dλ(x1,x2)⋯CSG,Dλ(x1,xm)⋮⋱⋮00⋯CSG,Dλ(xm,xm)]

and

|CSG,Dλ(U)|=∑i∈[1,m],j∈[i,m]CSG,Dλ(xi)(xj)(8)

|CSG,Dλ(U)| represents the cross-similarity level of U.

Proposition 14. Let (U,R,D) be an FDT, x∈U, y∈U, 0≤λ≤1 and G⊆R. The following conclusions are true:

1)   CSG,Dλ(x,y)=0;

2)   CSG,Dλ(x,y)=CSG,Dλ(y,x);

3)   |CSG,Dλ(U)|=12∑i∈[1,m]|CSG,Dλ(xi)|;

4)   0≤|CSG,Dλ(x)|≤m−1;

5)   0≤|CSG,Dλ(U)|≤m(m−1)2.

Proof. 1) By Definition 12, it is evident that CSG,Dλ(x,y)=0;

2) Under Definitions 2.2–2.4 and Definition 12, it is evident that this conclusion holds true;

3) According to 1), 2), and Eq. (8), it is evident that this conclusion holds true;

4) Since SimGλ(x,y)∈[0,1] and SimGλ(x,x)=0, this conclusion is true;

5) In accordance with 3) and 4), |CSG,Dλ(U)|=12∑i∈[1,m]|CSG,Dλ(xi)|≥1/2×m×0=0 and |CSG,Dλ(U)|=12∑i∈[1,m]|CSG,Dλ(xi)|≤12×m×(m−1)≤m(m−1)2. □

Theorem 15. Let (U,R,D) be an FDT, x∈U, y∈U, λ∈[0,1] and G⊆R. The following conclusions hold true:

1)   if G1⊆G2⊆R, then CSG1,Dλ(x,y)≥CSG2,Dλ(x,y);

2)   if 0≤λ1≤λ2≤1, then CSG,Dλ1(x)(y)≥CSG,Dλ2(x)(y).

Proof. 1) In accordance with Definition 12 and Proposition 4, it is evident that this conclusion holds true.

2) According to Definition 12 and Proposition 4, it is straightforward. □

Theorem 16. Let (U,R,D) be an FDT, x∈U, λ∈[0,1] and G⊆R. The following conclusions hold true:

1)   if G1⊆G2⊆R, then |CSG1,Dλ(x)|≥|CSG2,Dλ(x)|;

2)   if 0≤λ1≤λ2≤1, then |CSG,Dλ1(x)|≥|CSG,Dλ2(x)|.

Proof. According to Theorem 15 and Eq. (7), it is straightforward to demonstrate the validity of these conclusions. □

Theorem 17. Let (U,R,D) be an FDT, x∈U, λ∈[0,1] and G⊆R. The following conclusions are true:

1)   if G1⊆G2⊆R, then |CSG1,Dλ(U)|≥|CSG2,Dλ(U)|;

2)   if 0≤λ1≤λ2≤1, then |CSG,Dλ1(U)|≥|CSG,Dλ2(U)|.

Proof. According to Theorem 16 Proposition 14, and Eq. (8), it is straightforward to demonstrate the validity of these conclusions. □

Example 1. Let (U,R,D) be an FDT, where U={x1,x2,x3,x4,x5,x6,x7} and U/D={D1={x2,x3},D2={x1,x7},D3={x4,x5,x6}}. SimGλ is shown in Table 1, where G⊆R and 0≤λ<1.

Target partition D1 can be represented as a fuzzy set D1=0x1+1x2+1x3+0x4+0x5+0x6+0x7. The lower and upper approximations of D1 under FCRS (U,G) and parament λ are:

Apr_Gλ(D1)=0x1+0.5x2+0.3x3+0x4+0x5+0x6+0x7, Apr¯Gλ(D1)=0.5x1+1x2+1x3+0.6x4+0x5+0x6+0.7x7.

Obviously, Apr_Gλ(D1)⊂Apr¯Gλ(D1), there is uncertainty in the FCRS (U,G) for Target partition D1. For a decision table, if there is an approximate inequality between the upper and lower parts of a decision partition, it is claimed that the decision table has uncertainty.

By Definition 13, the fuzzy set associated with each sample point is computed as follows:

CSG,Dλ(x1)=0x1+0.5x2+0x3+0x4+0x5+0x6+0x7,|CSG,Dλ(x1)|=0.5;

CSG,Dλ(x2)=0.5x1+0x2+0x3+0x4+0x5+0x6+0x7,|CSG,Dλ(x2)|=0.5;

CSG,Dλ(x3)=0x1+0x2+0x3+0.6x4+0x5+0x6+0.7x7,|CSG,Dλ(x3)|=1.3;

CSG,Dλ(x4)=0x1+0x2+0.6x3+0x4+0x5+0x6+0x7,|CSG,Dλ(x4)|=0.6;

CSG,Dλ(x5)=0x1+0x2+0x3+0x4+0x5+0x6+0x7,|CSG,Dλ(x5)|=0;

CSG,Dλ(x6)=0x1+0x2+0x3+0x4+0x5+0x6+0.4x7,|CSG,Dλ(x6)|=0.4;

CSG,Dλ(x7)=0x1+0x2+0.7x3+0x4+0x5+0.4x6+0x7,|CSG,Dλ(x7)|=1.1.

Therefore, based on Definition 12, the FDT (U,R,D) under G and λ can be represented in Fig. 1. Each sample is represented as a node, a similarity relationship greater than 0 corresponds to an edge, and a target partition is depicted as an area enclosed by a dashed line in the graph. Cross-similarity relationships within similar relationships are highlighted in bold red.

Figure 1: Graphical representation of the FDT

The cross-similarity matrix CSG,Dλ(U) of the FDT is shown as follows:

CSG,Dλ(U)=[00.50000000000000000.6000.7000000000000000000000.40000000]

Therefore, the cross-similarity level of U is:

|CSG,Dλ(U)|=1/2∑x∈U|CSG,Dλ(x)|=2.2

Theorem 18. Let (U,R,D) be an FDT, λ∈[0,1] and G⊆R. If |CSG,Dλ(U)|=0, the FDT is consistent:

Proof. |CSG,Dλ(U)|=0⟺∀x,y∈U, CSG,Dλ(x,y)=0⟺ifSimGλ(x,y)>0⇒D(x)=D(y). Therefore, the FDT is consistent according to Proposition 11 1). □

Theorem 19. Let (U,R,D) be an FDT, λ∈[0,1] and G⊆R. If |CSG,Dλ(U)|>0, the FDT is inconsistent.

Proof. |CSG,Dλ(U)|>0⇒∃x,y∈U, CSG,Dλ(x,y)>0⇒∃Dl∈U/D, Dl(x)≠Dl(y) and SimGλ(x,y)>0. Therefore, the FDT is inconsistent according to Proposition 11 2). □

4  Feature Selection Based on Cross-Similarity

As |CSG,Dλ(U)| decreases, the similarity between samples belonging to different classes diminishes. In other words, a low |CSG,Dλ(U)| suggests that G exhibits strong discriminatory capabilities. Consequently, |CSG,Dλ(U)| serves as an effective tool for measuring the uncertainty associated with the FDT. The framework diagram of feature selection based on cross-similarity is shown in Fig. 2.

Figure 2: A framework diagram of feature selection

Definition 20. Let (U,R,D) be an FDT, λ∈[0,1] and red⊆R. The red is referred to as a reduction of R, if

1)   |CSred,Dλ(U)|=|CSR,Dλ(U)|;

2)   |CSred−{r},Dλ(U)|>|CSred,Dλ(U)|,∀r∈red.

Definition 21. Let (U,R,D) be an FDT, λ∈[0,1], red⊆R and r∈R−red. The significance of r with respect to red is defined as follows:

DCλ(r,red,D)=|CSred,Dλ(U)|−|CSred⋃{r},Dλ(U)|(9)

The larger DCλ(r,red,D) is, the smaller |CSred⋃{r},Dλ(U)| becomes, making the r more signicant.

Algorithm 1, a cross-similarity based feature selection (CSFS) algorithm, is a forward greedy feature selection algorithm.

Considering that as more features are chosen, the number of relationships to be considered when calculating cross-similarity progressively diminishes, and only the relationships between samples located in different categories are considered, the number of samples gradually decreases. It can be assumed that the number of samples decreases in geometric progression with a common ratio of k(0<k<1). Then m+km+k2m+⋅⋅⋅+ktm=[(1−kt+1)/(1−k)]m=cm. Therefore, the time complexity of Algorithm 1 is improved to O(mn2). In contrast, the time complexity of the feature selection algorithm based on positive domain, dependency, and conditional entropy is O(m2n2).

Example 2. A decision information table is shown in Table 2, where U={x1,x2,x3,x4,x5,x5,x7}, A={a1,a2,a3,a4} and D={p,n}. Let U∗=U and R∗=R.

In this paper, the value of ri is determined through the utilization of the following equation:

rai(x,y)=max{min{ai(x)−ai(y)+σaiσai,ai(y)−ai(x)+σaiσai},0}(10)