Attribute reduction for multiset-valued data based on FRIC -model

1 Introduction

Rough set theory (RST), brought forward by Pawlak [21, 22], can effectively deal with the uncertainty of an information system (IS). The application of RST is mostly related to ISs [12, 36].

Attribute reduction (A-reduction) as a technology of data ming is to use the attribute evaluation function to evaluate the attributes, and filter the redundant attributes in the conditional attribute set, so as to reduce the data dimension and to improve the generalization performance and efficiency of algorithms. The core step of A-reduction is to construct the attribute evaluation function. This function can be used to select key representative attributes from high-dimensional data. So far, there have been many outstanding results. Yao et al. [33] brought up class-specific A-reduction in RST. Lang et al. [14] gave A-reduction in dynamic fuzzy covering information systems based on homomorphism. Li et al. [15] investigated A-reduction for heterogeneous data based on information entropy. Trabelsi et al. [26] put forward heuristic method for A-reduction from partially uncertain data using rough sets.

As the extension of RST, fuzzy rough sets (FR-sets) can effectively deal with the uncertainty and ambiguity in the actual scene, and has been successfully applied to A-reduction. Wang et al. [29] proposed a fitting model for A-reduction based on FR-sets. Chen et al. [4] presented a novel A-reduction algorithm based on FR-sets. Dai et al. [6] presented maximal-discernibility-pair-based approach to A-reduction based on FR-sets. Wang et al. [28] constructed A-reduction based on FR-sets using distance measures.

Usually, RST deals with MV-data in the following way. Similarity measure in an MSVDIS is introduced in the sense of the similarity between information values which is fed back to the object set. Then, the tolerance relations on the object set are constructed. But these kinds of tolerance relations have deficiencies when they are used in fuzzy rough computation.

Given an MSVDIS and a threshold λ. This paper defines the fuzzy symmetry relations on the object set based on the number of attributes about the similarity between information values which is not less than λ, where λ controls the similarity between information values. This leads to FR-sets for MV-data. Fuzzy positive regions and fuzzy dependency functions associated with the FR-sets are constructed. Thus, fuzzy rough iterative computation model (FRIC-model) for MV-data is obtained. A-reduction algorithms in an MSVDIS based on FRIC-model are given. Finally, the experimental results show that the given algorithm is more effective than some existing algorithms.

This paper is organized as follows. Section 2 recalls some notions about FR-sets, multisets and probability distribution sets. Section 3 introduces an MSVDIS. Section 4 introduces fuzzy symmetric relations in an MSVDIS. Section 5 defines some evaluation functions in an MSVDIS. Section 6 establishes FRIC-model. Section 7 presents A-reduction algorithm based on FRIC-model. Section 8 carries out numerical experiments to show the feasibility of the presented algorithm. Section 9 executes Friedman test and post-hoc test to further verify the stability of classification of the presented algorithm. Section 10 concludes this paper.

2 Preliminaries

In this section, we give an overview of FR-sets, multisets and probability distribution sets.

Throughout this paper, O signifies a finite set, 2 ^O means the family of all subsets of O and |X| denotes the cardinality of X ∈ 2 ^O . Put O = { o 1 , o 2 , ⋯ , o n } .

3 MSVDISs

Definition 3.1.Suppose that O is a finite set of objects or samples and A is a finite set of attributes. Then (O, A) is referred to as an information system (IS), if ∀ a ∈ A, a is able to decide a information function  f _a  : O → V _a , where V _a  = {f _a (o) : o ∈ O}.

(O, C, d) is named as a decision information system (DIS), if (O, C ∪ {d} is an IS, where C and d are a set of conditional attributes and a decision attribute.

Suppose that * means a missing value. If ∃ a ∈ C, * ∈ V _a , but * ∉ V _d  = {f _d (o) : o ∈ O}, then a DIS (O, C, d) is an incomplete decision information system (IDIS).

Let (O, C, d) be an IDIS. ∀ a ∈ C, indicate V a * = V a - { f a ( o ) : f a ( o ) = * } .

Example 3.2.Suppose that a₁, a₂, a₃ and d express “Headache", “Muscle pain", “Temperature" and “Symptom", respectively. Put O = {o₁, o₂, ⋯ , o₉}, C = {a₁, a₂, a₃}. Let d be a decision attribute. Then, Table 1 is an IDIS (O, C, d).

Example 3.3.(Continued from Example 3.2) V a 1 * = { Sick ( S ) , Middle ( M ) , No ( N ) } , V a 2 * = { Yes ( Y ) , No ( N ) } , V a 3 * = { High ( H ) , Low ( L ) , Normal ( N ) } , V a 4 * = V a 4 = { Flu , Rhinitis , Health } .

Definition 3.4. Let (O, C, d) be an DIS with O = {o₁, o₂, ⋯ , o _n }. Then the pair (O, C, d) is said to be a multiset-valued decision information system (MSVDIS), if for each a ∈ C, f _a (o₁), f _a (o₂), ⋯ f _a (o _n ) are multisets drawn from the same set.

If P ⊆ C, then (O, P, d) is known as a subsystem of (O, C, d).

Definition 3.5. Let (O, C, d) be an IDIS with O = {o₁, o₂, ⋯ , o _n }. Given a ∈ C. Denote V a * = { x 1 , x 2 , ⋯ , x s } . Then V a * is an ordinary set.

Let M _a  = {f _a (o₁) , f _a (o₂) , ⋯ , f _a (o _n )} - {*} be a multiset (i.e., if f _a (o₁) = f _a (o₃), then it is allowed).

Suppose that ∀ i, m _i expresses the number of occurrences of x _i in M _a . Then M a = { m 1 / x 1 , m 2 / x 2 , ⋯ , m s / x s } .

If f _a (o) =*, then f _a (o) is replaced by {m₁/x₁, m₂/x₂, ⋯ , m _s /x _s }; if f _a (o) = x _j , then f _a (o) is replaced by { 0 / x 1 , ⋯ , 0 / x j - 1 , 1 / x j , 0 / x j + 1 , ⋯ , 0 / x s } .

After this treatment, (O, C, d) is an MSVDIS. We call it the MSVDIS induced by the IDIS (O, C, d).

The following example shows that an IIS induces an MSVDIS. Thus, an MSVDIS can be teated like an IIS.

Example 3.6. (Continued from Example 3.2) The following MSVDIS is induced by an IDIS (O, C, d) given in Table 1.

Definition 4.1.Let (O, C, d) be an MSVDIS. Given P ⊆ C and λ ∈ [0, 1]. Then the fuzzy relation on O can be defined as R P λ ( o , o ′ ) = 1 θ | { a ∈ P : HD ( P f a ( o ) , P f a ( o ′ ) ) ≤ λ } | , where θ ∈ [|P|, + ∞) is a constant, for instance, θ = |C|.

For convenience, denote P oo ′ λ = { a ∈ P : HD ( P f a ( o ) , P f a ( o ′ ) ) ≤ λ } . Then R P λ ( o , o ′ ) = 1 θ | P oo ′ λ | .

Clearly, R P λ is a fuzzy symmetric relation on O (i.e, ∀ o , o ′ ∈ O , R P λ ( o , o ′ ) = R P λ ( o ′ , o ) ), which is called the fuzzy symmetric relation induced by the subsystem (O, P, d).

If θ = |P|, then R P λ is a fuzzy tolerance relation on O (i.e, ∀ o ∈ O , R P λ ( o , o ) = 1 , and ∀ o , o ′ ∈ O , R P λ ( o , o ′ ) = R P λ ( o ′ , o ) ).

Proposition 4.2.Let (O, C, d) be an MSVDIS.

(1) If P₁ ⊆ P₂ ⊆ C, then ∀ λ ∈ [0, 1], R P 1 λ ⊆ R P 2 λ .

(2) If 0 ≤ λ₁ < λ₂ ≤ 1, then ∀ P ⊆ C, R P λ 2 ⊆ R P λ 1 .

Proof. (1) By Definition 4.1, R P 1 λ ( o , o ′ ) = 1 θ | ( P 1 ) oo ′ λ | , R P 2 λ ( o , o ′ ) = 1 θ | ( P 2 ) oo ′ λ | .

Since P₁ ⊆ P₂, we have ∀ o, o′ ∈ O, ( P 1 ) oo ′ λ ⊆ ( P 2 ) oo ′ λ .

So ∀ o, o′ ∈ O, R P 1 λ ( o , o ′ ) ≤ R P 2 λ ( o , o ′ ) .

Thus, R P 1 λ ⊆ R P 2 λ .

(2) By Definition 4.1, R P λ 1 ( o , o ′ ) = 1 θ | P oo ′ λ 1 | , R P λ 2 ( o , o ′ ) = 1 θ | P oo ′ λ 2 | .

Since 0 ≤ λ₁ < λ₂ ≤ 1, we have ∀ o, o′ ∈ O, P oo ′ λ 2 ⊆ P oo ′ λ 1 .

So ∀ o, o′ ∈ O, R P λ 2 ( o , o ′ ) ≤ R P λ 1 ( o , o ′ ) .

Thus, R P λ 2 ⊆ R P λ 1 . □

Proposition 4.2 illustrates that R P λ monotonically increases and decreases with respect to P and λ, respectively. The monotonicity of R P λ makes it easy for us to deal with R P λ .

5 Some evaluation functions in an MSVDIS

This part presents some evaluation functions in an MSVDIS.

Definition 5.1.Let (O, C, d) be an MSVDIS. Given P ⊆ C and λ ∈ [0, 1]. Define R P λ _ ( X ) ( o ) = ⋀ o ′ ∉ X , ∀ o ∈ O ; R P λ ¯ ( X ) ( o ) = ⋁ o ′ ∈ X R P λ ( o , o ′ ) , ∀ o ∈ O . Then R P λ _ ( X ) and R P λ ¯ ( X ) are called the lower and upper fuzzy approximations of X ∈ 2 ^O , respectively.

Proposition 5.2.Let (O, C, d) be an MSVDIS. Then the following properties hold. (1) ∀ P ⊆ C, ∀ λ ∈ [0, 1], ∀ X ∈ 2 ^O , R P λ _ ( X ) ⊆ X ⊆ R P λ ¯ ( X ) , where X ( o ) = { 1 , o ∈ X ; 0 , u ∉ X . (2) If P₁ ⊆ P₂ ⊆ C, then ∀ λ ∈ [0, 1], ∀ X ∈ 2 ^O , R P 1 λ _ ( X ) ⊆ R P 2 λ _ ( X ) , R P 2 λ ¯ ( X ) ⊆ R P 1 λ ¯ ( X ) .

(3) If 0 ≤ λ₁ < λ₂ ≤ 1, then ∀ P ⊆ C, ∀ X ∈ 2 ^O , R P λ 1 _ ( X ) ⊆ R P λ 2 _ ( X ) , R P λ 1 ¯ ( X ) ⊆ R P λ 2 ¯ ( X ) .

Proof. (1) (i) Given P ⊆ C, λ ∈ [0, 1], X ∈ 2 ^O . Then by Definition 4.1, we can obtain that ∀ o , o ′ ∈ O , 0 ≤ R P λ ( o , o ′ ) ≤ 1 .

Then 0 ≤ ⋀ o ′ ∉ X [ 1 - R P λ ( o , o ′ ) ] ≤ 1 .

So ∀ o ∈ O, 0 ≤ R P λ _ ( X ) ( o ) ≤ 1 .

Thus ∀ o ∈ X, R P λ _ ( X ) ( o ) ≤ 1 = X ( o ) .

Note that ∀ u ∉ X, R P λ _ ( X ) ( o ) = 1 - R P λ ( u , u ) = 0 . Then ∀ u ∉ X, R P λ _ ( X ) ( o ) = 0 ≤ 0 = X ( o ) .

This implies that ∀ o ∈ O, R P λ _ ( X ) ( o ) ≤ X ( o ) .

Thus R P λ _ ( X ) ⊆ X .

(ii) Obviously, ∀ o ∈ O , 0 ≤ R P λ ¯ ( X ) ( o ) ≤ 1 .

Then ∀ u ∉ X, X ( o ) = 0 ≤ R P λ ¯ ( X ) ( o ) .

Note that ∀ o ∈ X, R P λ ¯ ( X ) ( o ) = R P λ ( u , u ) = 1 . Then ∀ o ∈ X, R P λ ¯ ( X ) ( o ) = 1 ≤ 1 = X ( o ) .

This implies that ∀ o ∈ O, X ( o ) ≤ R P λ ¯ ( X ) ( o ) .

Thus X ⊆ R P λ ¯ ( X ) .

From the above, R P λ _ ( X ) ⊆ X ⊆ R P λ ¯ ( X ) .

(2) (i) Since P₁ ⊆ P₂ ⊆ C, by Proposition 4.2, we have R P 1 λ ⊆ R P 2 λ .

Then ∀ o ∈ O, o′ ∉ X, R P 1 λ ( o , o ′ ) ≤ R P 2 λ ( o , o ′ ) .

This implies that ∀ o ∈ O, ⋀ o ′ ∉ X [ 1 - R P 2 λ ( o , o ′ ) ] ≤ ⋀ o ′ ∉ X [ 1 - R P 1 λ ( o , o ′ ) ] .

Thus ∀ o ∈ O, R P 2 λ _ ( X ) ( o ) ≤ R P 1 λ _ ( X ) ( o ) .

Therefore, R P 2 λ _ ( X ) ⊆ R P 1 λ _ ( X ) .

(ii) Since P₁ ⊆ P₂ ⊆ C, by Proposition 4.2, we have R P 1 λ ⊆ R P 2 λ .

Then ∀ o ∈ O, o′ ∈ X, R P 1 λ ( o , o ′ ) ≤ R P 2 λ ( o , o ′ ) .

So ⋁ o ′ ∈ X R P 1 λ ( o , o ′ ) ≤ ⋁ o ′ ∈ X R P 2 λ ( o , o ′ ) .

Thus R P 1 λ ¯ ( X ) ( o ) ≤ R P 2 λ ¯ ( X ) ( o ) .

Therefore, R P 1 λ ¯ ( X ) ⊆ R P 2 λ ¯ ( X ) .

(3) (i) Since 0 ≤ λ₁ < λ₂ ≤ 1, by Proposition 4.2, we have R P λ 1 ⊆ R P λ 2 .

Then ∀ o ∈ O, o′ ∉ X, R P λ 1 ( o , o ′ ) ≤ R P λ 2 ( o , o ′ ) .

This implies that ∀ o ∈ O, ⋀ o ′ ∉ X [ 1 - R P λ 2 ( o , o ′ ) ] ≤ ⋀ o ′ ∉ X [ 1 - R P λ 1 ( o , o ′ ) ] .

Thus ∀ o ∈ O, R P λ 2 _ ( X ) ( o ) ≤ R P λ 1 _ ( X ) ( o ) .

Therefore, R P λ 2 _ ( X ) ⊆ R P λ 1 _ ( X ) .

(ii) Since P₁ ⊆ P₂ ⊆ C, by Proposition 4.2, we have R P λ 1 ⊆ R P λ 2 .

Then ∀ o ∈ O, o′ ∈ X, R P λ 1 ( o , o ′ ) ≤ R P λ 2 ( o , o ′ ) .

So ⋁ o ′ ∈ X R P λ 1 ( o , o ′ ) ≤ ⋁ o ′ ∈ X R P λ 2 ( o , o ′ ) .

Thus R P λ 1 ¯ ( X ) ( o ) ≤ R P λ 2 ¯ ( X ) ( o ) .

Therefore, R P λ 1 ¯ ( X ) ⊆ R P λ 2 ¯ ( X ) . □

Definition 5.3.Let (O, C, d) be an MSVDIS. Suppose P ⊆ C and λ ∈ [0, 1]. The fuzzy positive region of decision d relative to P can be defined as POS P λ ( d ) = ⋃ D ∈ O / d R P λ _ ( D ) = ⋃ i = 1 r R P λ _ ( D i ) .

Proposition 5.4.Let (O, C, d) be an MSVDIS.

(1) If P₁ ⊆ P₂ ⊆ C, then ∀ λ ∈ [0, 1], POS P 2 λ ( d ) ⊆ POS P 1 λ ( d ) .

(2) If 0 ≤ λ₁ < λ₂ ≤ 1, then ∀ P ⊆ C, POS P λ 1 ( d ) ⊆ POS P λ 2 ( d ) .

Proof. It follows from Proposition 5.2. □

Definition 5.5.Let (O, C, d) be an MSVDIS. Suppose P ⊆ C and λ ∈ [0, 1]. Then λ-degree of dependence of d relative to P can be defined as Γ P λ ( d ) = | POS P λ ( d ) | n .

Proposition 5.6.Let (O, C, d) be an MSVDIS.

(1) If P₁ ⊆ P₂ ⊆ C, then ∀ λ ∈ [0, 1], Γ P 2 λ ( d ) ⊆ Γ P 1 λ ( d ) .

(2) If 0 ≤ λ₁ < λ₂ ≤ 1, then ∀ P ⊆ C, Γ P λ 1 ( d ) ⊆ Γ P λ 2 ( d ) .

Proof. It follows from Proposition 5.4. □

Definition 5.7.Let (O, C, d) be an MSVDIS. Suppose P ⊆ C, λ ∈ [0, 1] and a ∈ C - P. Then λ-significance of a relative to P about d can be defined as sig λ ( a , P , d ) = Γ P λ ( d ) - Γ P ∪ { a } λ ( d ) .

6 FRIC-model in an MSVDIS

This section gives FRIC-model in an MSVDIS.

Let (O, C, d) be an MSVDIS. Given P ⊆ C and λ ∈ [0, 1]. Suppose |P| ≤ θ₁ < θ₂ < ⋯ ≤ |C|. Then ∀ i, denote ( R P λ ) i ( o , o ′ ) = 1 θ i | P oo ′ λ | ( o , o ′ ∈ O ) ; R P λ _ ( D ) i ( o ) = ⋀ o ′ ∉ D [ 1 - ( R P λ ) i ( o , o ′ ) ] ( D ∈ O / d , o ∈ O ) ; R P λ ¯ ( D ) i ( o ) = ⋁ o ′ ∈ D ( R P λ ) i ( o , o ′ ) ( D ∈ O / d , o ∈ O ) ; POS P λ ( d ) i = ⋃ D ∈ O / d R P λ _ ( D ) i ; Γ P λ ( d ) i = | POS P λ ( d ) i | n ; sig λ ( a , P , d ) ) i = Γ P λ ( d ) i - Γ P ∪ { a } λ ( d ) i ( P ⊆ C , a ∈ C - P ) .

Theorem 6.1.Let (O, C, d) be an MSVDIS. Given P ⊆ C and λ ∈ [0, 1]. Then ∀ D ∈ O/d, ∀ o ∈ O, ∀ i, R P λ _ ( D ) i + 1 ( o ) = θ i + 1 - θ i θ i + 1 + θ i θ i + 1 R P λ _ ( D ) i ( o ) .

Proof. R P λ _ ( D ) i ( o ) = ⋀ o ′ ∉ D ( 1 - 1 θ i | P oo ′ λ | ) = 1 - ⋁ o ′ ∉ D 1 θ i | P oo ′ λ | = 1 - 1 θ i ⋁ o ′ ∉ D | P oo ′ λ | .

Similarly, R P λ _ ( D ) i + 1 ( o ) = 1 - 1 θ i + 1 ⋁ o ′ ∉ D | P oo ′ λ | .

Then, θ i + 1 - θ i θ i + 1 + θ i θ i + 1 R P λ _ ( D ) i ( o ) = θ i + 1 - θ i θ i + 1 + θ i θ i + 1 ( 1 - 1 θ i ⋁ o ′ ∉ D | P oo ′ λ | ) = 1 - 1 θ i + 1 ⋁ o ′ ∉ D | P oo ′ λ | .

Thus R P λ _ ( D ) i + 1 ( o ) = θ i + 1 - θ i θ i + 1 + θ i θ i + 1 R P λ _ ( D ) i ( o ) . □

Corollary 6.2.Let (O, C, d) be an MSVDIS. Given P ⊆ C and λ ∈ [0, 1]. Then ∀ D ∈ O/d, ∀ o ∈ O, ∀ i ∈ [|P|, |C|-1], R P λ _ ( D ) i + 1 ( o ) = 1 i + 1 + i i + 1 R P λ _ ( D ) i ( o ) .

Theorem 6.3.Let (O, C, d) be an MSVDIS. Given P ⊆ C and D ∈ O/d. Then ∀ i, R P λ ¯ ( D ) i + 1 = θ i θ i + 1 R P λ ¯ ( D ) i .

Proof. Obviously. □

Corollary 6.4.Let (O, C, d) be an MSVDIS. Given P ⊆ C and D ∈ O/d. Then ∀ i ∈ [|P|, |C|-1], R P λ ¯ ( D ) i + 1 = i i + 1 R P λ ¯ ( D ) i .

Theorem 6.5.Let (O, C, d) be an MSVDIS. Given P ⊆ C and λ ∈ [0, 1]. Then ∀ o ∈ O, ∀ i, POS P λ ( d ) i + 1 ( o ) = θ i + 1 - θ i θ i + 1 + θ i θ i + 1 POS P λ ( d ) i ( o ) .

Proof. By Theorem 6.1, we can obtain that ∀ o ∈ O, ∀ i, POS P λ ( d ) i + 1 ( o ) = ⋁ D ∈ O / d R P λ _ ( i + 1 ) ( D ) ( o ) = ⋁ D ∈ O / d ( θ i + 1 - θ i θ i + 1 + θ i θ i + 1 R P λ _ ( i ) ( D ) ( o ) ) = θ i + 1 - θ i θ i + 1 + ⋁ D ∈ O / d θ i θ i + 1 R P λ _ ( i ) ( D ) ( o ) = θ i + 1 - θ i θ i + 1 + θ i θ i + 1 ⋁ D ∈ O / d R P λ _ ( i ) ( D ) ( o ) .

Thus POS P λ ( d ) i + 1 ( o ) = θ i + 1 - θ i θ i + 1 + θ i θ i + 1 POS P λ ( d ) i ( o ) . □

Corollary 6.6.Let (O, C, d) be an MSVDIS. Given P ⊆ C and λ ∈ [0, 1]. Then ∀ o ∈ O, ∀ i ∈ [|P|, |C|-1], POS P λ ( d ) i + 1 ( o ) = 1 i + 1 + i i + 1 POS P λ ( d ) i ( o ) .

Theorem 6.7.Let (O, C, d) be an MSVDIS. Given P ⊆ C and λ ∈ [0, 1]. Then ∀ i, Γ P λ ( d ) i + 1 = θ i + 1 - θ i θ i + 1 + θ i θ i + 1 Γ P λ ( d ) i .

Proof. By Theorem 6.5, | POS P λ ( d ) i + 1 | = ∑ j = 1 n POS P λ ( d ) i + 1 ( o j ) = ∑ j = 1 n ( θ i + 1 - θ i θ i + 1 + θ i θ i + 1 POS P λ ( d ) i ( o j ) ) = θ i + 1 - θ i θ i + 1 n + θ i θ i + 1 ∑ j = 1 n POS P λ ( d ) i ( o j ) = θ i + 1 - θ i θ i + 1 n + θ i θ i + 1 | POS P λ ( d ) i | .

Then | POS P λ ( d ) i + 1 | n = θ i + 1 - θ i θ i + 1 + θ i θ i + 1 | POS P λ ( d ) i | n .

Thus Γ P λ ( d ) i + 1 = θ i + 1 - θ i θ i + 1 + θ i θ i + 1 Γ P λ ( d ) i . □

Corollary 6.8.Let (O, C, d) be an MSVDIS. Given P ⊆ C and λ ∈ [0, 1]. Then ∀ i ∈ [|P|, |C|-1], Γ P λ ( d ) i + 1 = 1 i + 1 + i i + 1 Γ P λ ( d ) i .

Theorem 6.9.Let (O, C, d) be an MSVDIS. Suppose P ⊆ C, a ∈ C - P. Then ∀ i,  sig λ ( a , P , d ) i + 1 = θ i θ i + 1 sig λ ( a , P , d ) i .

Proof. By Theorem 6.7, sig ^λ(a, P, d) _i+1 = Γ P λ ( d ) i + 1 - Γ P ∪ { a } ( i + 1 ) ( d ) = ( θ i + 1 - θ i θ i + 1 + θ i θ i + 1 Γ P λ ( d ) i ) - ( θ i + 1 - θ i θ i + 1 + θ i θ i + 1 Γ P ∪ { a } λ ( d ) i ) = θ i θ i + 1 Γ P λ ( d ) i - θ i θ i + 1 Γ P ∪ { a } λ ( d ) i = θ i θ i + 1 ( Γ P λ ( d ) i - Γ P ∪ { a } λ ( d ) i ) .

Thus sig λ ( a , P , d ) i + 1 = θ i θ i + 1 sig λ ( a , P , d ) i . □

Corollary 6.10.Let (O, C, d) be an MSVDIS. Suppose P ⊆ C, a ∈ C - P. Then ∀ i ∈ [|P|, |C|-1], sig λ ( a , P , d ) i + 1 = i i + 1 sig λ ( a , P , d ) i .

7 A-reduction in an MSVDIS

This part studies A-reduction in an MSVDIS and proposes the corresponding algorithm.

Algorithm 1 Computing R P λ

REQUIRE (O, C, d), P ⊆ C and λ ∈ [0, 1].

ENSURE R P λ .

1: foro, o′ ∈ O

2: fora ∈ C

3: Calculate HD(P_{f a (o)}, P_{f a (o′)});

4: ifHD(P_{f a (o)}, P_{f a (o′)}) ≤ λ

5: a ∈ P oo ′ λ ;

6: end if

7: end for

8: Obtain P oo ′ λ ;

9: Calculate R P λ ( o , o ′ ) = | P oo ′ λ | ;

10: end for

11: return R P λ = ( R P λ ( o , o ′ ) ) n × n ;

It can be seen that Algorithm 1 has two cycles, and the time complexity is mainly determined by the scale of O and C. Therefore, the time complexity of the overall algorithm is O(|C| * |O|²). Based on the above FRIC-model, we propose Algorithm 2 for a reduct. This algorithm uses FRIC-model to solve the MV-data problem, so we call this algorithm MFRIC.

Algorithm 2 Obtain a reduct in an MSVDIS (FRIC)

REQUIRE (O, C, d), D ∈ O/d, R P λ , δ ∈ [0, 1].

ENSURE A reduct P.

1: let P =∅;

2: while true do

3: θ = |P|;

4: fora ∈ C - P

5: Compute R P ⋃ { a } λ _ ( D ) = min { 1 - 1 | θ | + 1 R P ⋃ { a } λ ( D ) };

Γ P ⋃ { a } λ ( d ) = ∑ D ∈ O / d R P ⋃ { a } λ _ ( D ) | O | ;

6: end for

7: Find a^* ∈ C - P such that Γ P ⋃ { a * } λ ( d ) = max { Γ P ⋃ { a } λ ( d ) : a ∈ C - P } ;

Then compute sig ( a * , P , d ) = θ θ + 1 ( Γ P λ ( d ) - Γ P ⋃ { a * } λ ( d ) ) ;

8: ifsig(a^*, P, d) > δ

9: P = P ∪ {a^*

10: else

11: break;

12: end if

13: end while

14: return P.

By Algorithm 2 (MFRIC), we obtain a reduct about data. It adds a parameter δ in step 10, which is a threshold and usually take (0.05, 0.3). The δ is mainly used to control the significance. When δ takes different values, different reducts can be obtained. The time complexity of Algorithm 2 is polynomial. The time complexity from step(4) to step(7) is O(|C - P| * |O|²). The time complexity from step(8) is O(|C - P|). There are no loops in the remaining steps, and the time complexity is O(1). From step 2 to step 15, attribute reduction is realized, and the number of attributes is reduced from |C| to |P|. The time complexity is O ( ( | C | + | P | ) 2 * ( | C | - | P | + 1 ) * | O | 2 ) = O ( | C | 2 + | C | - | P | 2 + | P | 2 * | O | 2 ) . Its space complexity is O(|C| * |O|²).

8 Experiments

In order to verify the effectiveness of the proposed algorithm, we will introduce the results of numerical experiments in this section. All numerical experiments were completed on Lenovo computer with Intel Core i7-4790cup @ 3.60GHZ and 16G memory. Eight classified data were selected from UCI [27] machine learning repository for experiment. Since there is no MV-data in UCI, we choose incomplete data to replace MV-data. These eight data sets are detailed in Table 3.

In order to facilitate operation and observe the impact of deletion rate on the algorithm, 5%, 10% and 20% of the information are deleted randomly in the all data set. Our goal is to reduce data attributes while keeping the classification accuracy of data unchanged. The subset with the largest classification accuracy is recorded while reducing the data set, and the subset with the largest classification accuracy is taken as the optimal subset. Therefore, MFRIC algorithm is programmed with MATLAB to find the best reduction set. Because the proposed algorithm has a key parameter λ, the selection of λ will directly affect the reduced subset. Parameter λ is selected from 0.5 to 0.9 in steps of 0.05.

The attribute subset with the highest classification accuracy is selected as the final result. The number of reduced subsets and the value of parameter λ are shown in Table 4. At the same time, in order to verify the advantages and disadvantages of the proposed algorithm, we looked for the other three algorithms to compare with it. Because there are few literatures on multiset-valued information systems, algorithms KGIRA-M [35], FSRS [24] and FSNTDJE [25] were selected for comparison. KGIRA-M and FSNTDJE discuss incomplete information systems, and FSRS studies set-valued information systems. The average reduction subsets of the other three algorithms under the three deletion rates are shown together in Table 4.

It can be seen from Table 4 that the average number of reduced attributes of algorithm MFRIC in the case of data loss of 5%, 10% and 20% is 6.38, 7.75 and 9.50 respectively, and the overall average number is 7.86. The reduction effect of this algorithm is equivalent to that of the other three algorithms, and can be considered to be effective.

Next, we will discuss the classification accuracy of the reduced subsets of the four algorithms under the same classifier. Two classifiers Classification And Regression Trees (CART) and Support Vector Machines (SVM) are selected to calculate the classification accuracy of reduced subsets. 5-fold cross validation is used to test the stability of the four algorithms. Tables 5 and 6 show the accuracy comparison of the four algorithms after reduction under the two classifiers. For comparison, the classification accuracy of all sets is calculated and the results are placed in column 2. Black bold font indicates the best result for this line. From the tables, it can be seen that MFRIC calculates slightly more quantities with higher accuracy than the other three algorithms. The accuracy of CART classifier is significantly higher than that of SVM. Further, it can be found that when the deletion rate increases gradually, the classification accuracy decreases, which is consistent with the intuitive understanding. However, does this mean that the proposed algorithm must be better than other algorithms? Statistical analysis is discussed in the next section. Through statistical analysis, we can judge whether the performance of the algorithm is significant.

In the proposed algorithm, the parameter λ affects the change of classification accuracy. The relationship between λ and classification accuracy under different data sets is observed by drawing. Figure 1 shows the relationship between parameter λ and classification accuracy. It can be seen from the figure that the curve drawn by CART is slightly higher than SVM under the same deletion rate, which also shows that CART is slightly better than SVM in classification effect. The curve in the figure has no obvious change law, which shows that the value of parameter λ will affect the classification accuracy, but which value will have a greater impact depends on the data set and deletion rate.

OPEN IN VIEWER

Fig. 1

Classification accuracy of reduced subset of algorithm MFRIC under classifier CART and SVM.

In order to compare the classification accuracy of the four algorithms, the classification accuracy of all the best reduced subsets is found, and the corresponding receiver operation characteristic curves(ROC) were drawn. The deletion rate of 5% was used for all experimental data. The ROC curves obtained by using CART classifier for the reduced subsets of the four algorithms are shown in Figure 2. The Area Under Curve (AUC) is calculated separately and displayed on the legend of each subgraph. The horizontal axis of Figure 2 is false positive rate and the vertical axis is true positive rate. It can be seen from Figure 2 that most of the areas are greater than 0.5, indicating that the classification effect is very nice. In most cases, the AUC of MFRIC algorithm is slightly larger than that of other algorithms, which shows that it not only has higher classification accuracy, but also has good classification balance. In order to confirm the effect of cart classifier, we also selected four data sets to verify whether the ROC curve and AUC under SVM classifier are as obvious as each other. As can be seen from Figure 3, the effect of classifier SVM is slightly worse than CART, but the AUC still exceeds 0.5. This shows that although the classification effect of SVM is not as good as CART, it also meets the requirements of classification.

OPEN IN VIEWER

Fig. 2

ROC curve and AUC value under CART classifier.

OPEN IN VIEWER

Fig. 3

ROC curve and AUC value under SVM classifier.

Friedman test is an nonparametric hypothesis test which is applied to compare the performance of classification algorithms statistically [5]. If Friedman test result is significant, then the null hypothesis “all algorithms have the same performance” will be rejected. Thus a post-hoc test such as Nemenyi test should be carried out to further test which algorithms perform better.

For T data sets and G algorithms, C _i is the average rank of the i-th algorithm with i = 1, 2, ⋯ , G. The original Friedman statistic is defined as χ F 2 = T G ( G + 1 ) ( 12 ∑ i = 1 G C i 2 - 3 G ( G + 1 ) 2 ) .

Since the original Friedman test result is generally not significant when the value of G is too small, a different Friedman test with a test statistic F _F is usually used. The statistic F _F follows the F-distribution with G - 1 and (G - 1)(T - 1) degrees of freedom and it is defined as F F = ( T - 1 ) χ F 2 T ( G - 1 ) - χ F 2 .

Nemenyi test can be used to test whether there is difference between the performance of two algorithms. The critical value of Nemenyi test is defined as CD α = q α G ( G + 1 ) 6 T , where α is significance level, and q _α is the critical value of the Tukey distribution with parameters 1 - α and G. The difference between the average ranks of each pair of algorithms is compared with the critical value CD _α. When the average rank difference is larger than the critical value, it indicates the pair of algorithms perform significantly different.

The ranks of the proposed algorithms with different classifiers can be calculated by their classification accuracies from Tables 5 and 6. They are showed in Tables 7 and 8.

The Friedman tests results with CART and SVM in Table 8. F _F  > F_0.05(3, 69), p - value< α. The results of statistical analysis point out that the null hypothesis of “there is no significant difference between the classification accuracies of the four algorithms" is rejected both with CART and with SVM. This means that two Nemenyi tests are needed. The results of the Nemenyi tests in Figures 4 and 5 are illustrated as follows:

(1) Under the CART classifier

a) The algorithm MFRIC had a higher classification accuracy than that of KGIRA-M, FSRS, and FSNTDJE;

b) There was no significant difference in classification accuracy among algorithms KGIRA-M, FSRS, FSNTDJE.

(2) Under the SVM classifier

a) The algorithm MFRIC had a higher classification accuracy than that of FSRS and FSNTDJE;

b) The algorithm KGIRA-M had a higher classification accuracy than that of FSRS and FSNTDJE;

c) There was no significant difference in classification accuracy between algorithms MFRIC and KGIRA-M;

d) There was no significant difference in classification accuracy between algorithms FSRS and FSNTDJE.

OPEN IN VIEWER

Fig. 4

The result of Nemenyi test with CART.

OPEN IN VIEWER

Fig. 5

The result of Nemenyi test with SVM.

In this paper, the fuzzy symmetry relations on object set of an MSVDIS have been established based on the similarity between information values which is fed back to the attribute set, and FR-sets have been proposed. FR-sets use the fuzzy symmetry relations to define fuzzy rough approximations, fuzzy positive region and fuzzy dependency and then overcome the deficiency of classical rough sets. In the fuzzy symmetry relation, there is a parameter that controls the similarity between two objects. FRIC-model in an MSVDIS has been presented based on the iteration of fuzzy positive region and fuzzy dependency. A-reduction algorithm based on FRIC-model has been given. Experiments on eight datasets from UCI have been carried out. The experimental results and statistical analysis show that the given algorithm is fast and occupies few memory. The advantage of the given algorithm is to define an iterative formula for A-reduction algorithm in an MSVDIS. In the near future, we will develop FRIC-model for other type of data.