Dependency Analysis and Attribute Reduction in the Probabilistic Approach to Rough Sets - Feature Selection for Data and Pattern Recognition - page 103

Algorithm 1 — Reduction :

Step 1 :Let Initial Dependency

ʻ

ₐ ʻ( | )

X C ;

Step 2 : Arrange condition attributes a ∈ C in descending order based on the

degree of ;

Step 3 : Starting with the attribute with the lowest

ʻ — dependency measure ʻ( X |{ a } )

— dependency degree and
proceeding in ascending order, perform the following two steps for all condition
attributes:
Step 3.1 : Test the condition Initial Dependency

ʻ

= ʻ( X | C −{ a } ) ;

Step 3.2 :If Initial Dependency = ʻ( X | C −{ a } ) then eliminate the attribute a

from the set of condition attributes C ;
Step 4 : The remaining set of condition attributes at the end of the process is a

ʻ — reduct of the initial collection of condition attributes.

In the above algorithm, the condition attributes with the weakest connection with
the target classification are eliminated first. Although this technique does not guar-
antee finding the shortest reduct, it appears to be a reasonable heuristic to find best
attributes in the reduct. It should also be noted that the — reduct , in general, does not

preserve the approximation regions of a target set X . This means that after computing
the

ʻ

— reduct of a condition attributes, the approximation regions of a probabilistic
decision table have to be re-computed again.
If the preservation of the approximation regions of a probabilistic decision table
is of interest, the reduction of condition attributes can be conducted using γ —
dependencies measure (Eq. 6.19 ), which is also monotonic. In this case, any reduct,
referred to as γ — reduct , of condition attributes preserving the functional dependency
between the condition attributes and the attribute Region indicating the approxima-
tion region of each elementary set, can be computed. A single γ — reduct can be
identified using a variant of

ʻ

— Reduction algorithm, referred to as γ — Reduction

ʻ

algorithm:

Algorithm 2 γ — Reduction :
Step 1 Let Initial Dependency

1;
Step 2 Arrange condition attributes a

ₐ

∈ C in descending order based on the

degree of ;

Step 3 Starting with the attribute with the lowest

ʻ — dependency measure ʻ( X |{ a } )

— dependency degree and
proceeding in ascending order, perform the following two steps for all condition
attributes:
Step 3.1 Test the condition Initial Dependency

ʻ

= γ (

Region | C −{ a } ) ;

= γ (

Step 3.2 If Initial Dependency Region | C −{ a } ) then eliminate the attribute

a from the set of condition attributes C ;
Step 4 The remaining set of condition attributes at the end of the process equals to
a γ — reduct of the initial collection of condition attributes of a probabilistic decision
table.