Optimize Selection (RapidMiner Studio Core)

Description

Feature selection i.e. the question for the most relevant features for classification or regression problems, is one of the main data mining tasks. A wide range of search methods have been integrated into RapidMiner including evolutionary algorithms. For all search methods we need a performance measurement which indicates how well a search point (a feature subset) will probably perform on the given data set.

A deterministic algorithm is an algorithm which, in informal terms, behaves predictably. Given a particular input, it will always produce the same output, and the underlying machine will always pass through the same sequence of states.

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. On some problems, a greedy strategy may not produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution.

This operator realizes the two deterministic greedy feature selection algorithms 'forward selection' and 'backward elimination'. However, we have added some enhancements to the standard algorithms which are described below:

Forward Selection

Create an initial population with n individuals where n is the number of attributes in the input ExampleSet. Each individual will use exactly one of the features. Evaluate the attribute sets and select only the best k. For each of the k attribute sets do: If there are j unused attributes, make j copies of the attribute set and add exactly one of the previously unused attributes to the attribute set. As long as the performance improved in the last p iterations go to step 2

Backward Elimination

Start with an attribute set which uses all features. Evaluate all attribute sets and select the best k. For each of the k attribute sets do: If there are j attributes used, make j copies of the attribute set and remove exactly one of the previously used attributes from the attribute set. As long as the performance improved in the last p iterations go to step 2

The parameter k can be specified by the keep best parameter, the parameter p can be specified by the generations without improval parameter. These parameters have default values 1 which means that the standard selection algorithms are used. Using other values increases the runtime but might help to avoid local extrema in the search for the global optimum.

Another unusual parameter is the maximum number of generations parameter. This parameter bounds the number of iterations to this maximum of feature selections / de-selections. In combination with the generations without improval parameter, this allows several different selection schemes (which are described for forward selection, backward elimination works analogous):

maximum number of generations = m and generations without improval = p:

Selects maximal m features. The selection stops if no performance improvement was measured in the last p generations.

maximum number of generations = -1 and generations without improval = p:

Tries to selects new features until no performance improvement was measured in the last p generations.

maximum number of generations = m and generations without improval = -1:

Selects maximal m features. The selection stops is not stopped until all combinations with maximal m were tried. However, the result might contain fewer features than these.

maximum number of generations = -1 and generations without improval = -1:

Test all combinations of attributes (brute force, this might take a very long time and should only be applied to small attribute sets).