Feature Selection 2

Data science Day 10:

Sequential Backward Selection

Backward Selection is the selection method starting from the whole set and achieves the attribute set by removing the element that results in the maximum decrease of the Objective Function in each step.

Sequential Backward Selection Algorithm

1. Let Y= X.
2. x in Y where F(x) is maximized.
3. Y- {xi}, and repeat step 2.

If we run a complete SBS Algorithm, we will have Y=ø, in order to avoid this scenario, we will impose a stopping criterion in practice.

Example:

Apply feature selection on the objective function without a stopping criterion.

Nerivill / Pixabay

Solution:

1. Check the Objective function value for x1, x2, x3 and x4.

2. Check the Objective function value for Y-{x3}
If x1=0, we have F(0,1,0,1)=4
If x2=0, we have F(1,0,0,1)=4
If x4=0, we have F(1,1,0,0)=3

Since x1 and x2 produce the same value, we can pick either x1 or x2. I will pick x1 for simplicity.

3. Check the Objective function value for Y-{x3,x1}
If x2=0, we have F(0,0,0,1)=4
If x4=0, we have F(0,1,0,0)=0
Since x2=0 produce the highest value for the objective function, 4, we will remove x2 in step 3.

3. Check the Objective function value for {x4,x1,x2}∪{x3}
If x4=0, we have F(0,0,0,0)= 0
By finishing this step, we removed the whole set.

Summary:

Sequential Forward Selection is a smart choice to use when the desired cardinality of Y is small. Backward Selection is preferred if the desired cardinality is large.

Both SFS and SBS cannot compare the previous result and the current stage. We need more complicated approaches to resolve this limitation.

Thanks to Douglas Rumbaugh‘s Data Mining Class notes!

Happy studying! 😳