Evolutionary process that helped me to win $1000

As the recent successful winner of the RapidMiner farming on Mars competition, I thought I would post the evolutionary process that helped lead me to the best solution.

I've tidied it up a bit and in fact there are 4 processes. The main one calls the others using "Execute Process" which ensures that common processing is placed in one location to avoid making errors.

The four processes are.

1. EvoExample.rmp
2. ReadAllData.rmp
3. FilterHourAndSelectAttributes.rmp
4. ImportData.rmp

When saving these, ensure the names are as above and they are all saved in the same repository. It's also important to point the processes at the locations of the training and test files. Download the training data from here and the test data from here. Unzip in the normal way and enter the locations into the "ReadAllData" process by changing the macros associated with the "ExecuteProcess" operator that runs the "ImportData" process.

When all the dust has settled, run the "EvoExample" process and observe the log output that writes a row each time a test has been performed with the specific settings of hour and misclassification cost.

These two parameters are contained in the depths of the process and the evolutionary process chooses values for these parameters and determines how they affect performance. 

The process has a couple of interesting features. Firstly, the performance is extracted from a calculation to match the scoring used in the competition. The operator "Extract Performance" is used to do this. Secondly, the process shows a way of varying the value of a macro inside the evolutionary operator. This is a bit of a hack and involves using the varying parameter of the evolutionary operator to control the execution of the example set made by a "Generate Data" operator and then using other operators to extract the details of this dummy example set to place into a macro. Maybe there's an easier way; I couldn't find one.

The contest did reveal an issue with the way nominal values are read and assigned which show up when running in Windows and in Linux environments. I hope this will lead to an enhancement to allow more control to be exerted. In the meantime, the process tries to get round these by sorting and being explicit in assigning positive and negative labels. Despite this, there is a chance that different environments will yield different results. The interested reader is referred to this process.

Have fun!...

Using Genetic Algorithms to find global extremes in arbitrary functions

Genetic algorithms offer the possibility to find global maxima and minima in arbitrary functions as the inputs to the functions are varied. RapidMiner has a number of evolutionary operators and one in particular is "Optimize Parameters (Evolutionary)" that, on the face of it, allows the parameters of operators contained within it to be varied as a performance vector is calculated based on how the varied parameters cause the inner operators to behave. There is a slight difficulty because not all parameters can be exposed for control by the Optimize operator so a work-around is needed. We'll come back to that shortly.

Firstly, let's choose a function to optimize. A good candidate is the Rastrigin function that, in two dimensions, has the following form.

f(i1, i2) = 20 + i1*i1 + i2*i2 - 10*(cos(2*pi*i1) + cos(2*pi*i2))

Within the range -5.12 to 5.12 for both i1 and i2, the function has many local minima which makes finding the lowest a challenging problem for some techniques. The following graph shows the function.

By inspection and exploration we can find that the global minimum is 0 when i1 and i2 are both 0. The process to generate this data is here.

Now let's see if we can find this minimum using a RapidMiner process. The process is here.

The first part of the process shown above uses a "Generate Data by User Specification" operator to generate a small example set that needs a label and a regular attribute in order for the "Optimize Parameters (Evolutionary)" operator to work.

The inner operators inside the Optimize operator are shown below.

The two operators labelled i1 and i2 are there purely to allow parameters to be passed from the control part of the Optimize operator. This is the work around I mentioned earlier. Basically, operators i1 and i2 expose parameters that can be seen from the Optimize operator and can be varied. The parameter settings for the Optimize operator are shown in the following.

This shows that the i1.constant value is allowed to vary between -5.12 and 5.12; the Optimize operator chooses the values as it proceeds.

Returning to the inner operators, the values of the parameters are accessed using a "Generate Attributes" operator. The first two attributes show how to get the values from the i1 and i2 operators. The third attribute calculates the Rastrigin value and the fourth attribute copies this into a result attribute (not strictly necessary - this process used to have other functions which I deleted to make the cut down process for this blog post).

From this point, the "Optimize" operator needs a performance vector to work on. The simplest thing to use is the "Extract Performance" operator to extract a specific value from the example set containing the Rastrigin result. This is shown below and the optimization direction is set to minimize since we are looking for a minimum.

The final "Log" operator records what happens.

If we run this process the Log result is shown in the following plot.

This shows the performance tending to 0, the global minimum, as the process proceeds and this corresponds to i1 and i2 both being 0. Plotting the log result as a scatter plot shows clusters of blue points which show how the genetic algorithm successfully keeps to areas where there are minima.

Genetic algorithms are not guaranteed to find the global minimum and in fact, even the process in this blog occasionally does not find it. If you set the parameter "specify population size" in "Optimize Parameters (Evolutionary)" to a small number like 5, you should observe this because fewer individuals are used to test the solution space and so the chance of being near the global minimum is low. Note that a little known feature of the "Process" operator is that setting "random seed" to -1 causes a new random seed to be selected for each run thereby ensuring that each run produces different results.

Of course, there is no way to detect when the global extreme is not found in the more normal case when the answer is not known beforehand. As usual, be sceptical and alive to the possibility that the result is not the best and try different parameter settings to see how results change. As mentioned, the population size affects this as do the "crossover prob" and "tournament fraction" parameters. There is no free lunch of course and an exhaustive search will always take longer.

In summary, we can see that RapidMiner can, with a bit of a work around, be used to optimize arbitrary functions. My experiments show that it seems to do a good job in most cases. A future post will show the same thing using R.

Unit testing RapidMiner processes using R

I've used R a lot over the last few years. Partly in my day to day activity, but also as part of my efforts as co-editor with Dr. Markus Hofmann for our recent new book "Text Mining and Visualization: Case Studies Using Open-Source Tools", available at all good bookstores ;)

I have also made some R packages and these even contain unit tests implemented with the splendid testthat package. Any minute now, I might even become an R expert.

Unit tests are vital to the health and sanity of the creator of any solution. Once something gets big and is subject to a lot of change, it is extremely important to know whether changes haven't accidentally broken something. RapidMiner processes are no different and it struck me that it would be worth implementing some basic unit testing for these. It could be done using RapidMiner itself but, for fun, I thought I would use R.

Here is a small example process that illustrates this. It starts by estimating the performance of a classifier on the Iris data set. The estimated performance is converted to an example set using the "Performance to Data" operator and is then passed to the "Execute R" operator.

This is the performance vector.

The R script confirms that all the parts of the performance vector are as expected. It uses a base R function called "all.equal()" to do this (I decided not to use testthat to avoid having to install the library so others can get going more quickly).

Here is the R script.

As you can see, the script checks that all the parts of the example set are as expected. For example, this line

confirms that the values for accuracy and kappa are 0.94 and 0.91 respectively with a tolerance of 0.01. The R script then outputs a data frame with the results. When all is well the result looks like this.

By changing the parameters of the earlier operators, the results will change. This can be picked up by examination of the result. Here is an example when the number of cross validations is set to 3.

In other words, the performance has changed and this gets detected automatically. Obviously, this is a simple example but you can see how it could be extended.

As I mentioned above, you could do this in pure RapidMiner but it would need quite a number of operators to realise it. The R integration in RapidMiner is relatively easy to use and so it deserves the time of day when considering how to tackle problems.

R also has a tremendous range of packages and a future post will touch cautiously on how to access a database directly.

A "feature" of the Performance (Regression) operator

I noticed a feature of the Performance (Regression) operator whereby it never reports a value for correlation less than 0. This would happen if a label and prediction are negatively correlated with one another. Furthermore, the squared correlation is also reported as zero in this case.

This example process shows this.

I'm using the Correlation Matrix operator as a way of checking the answer I get. If the sign of the calculation is changed in the Generate Attributes operator you will find that in the negative case the correlation should be -0.763 whilst in the positive it should be 0.706.

The output from the Performance (Regression) operator is 0 for correlation and squared correlation in the negative case. How odd since there are other criteria that can take negative values such as Kendall Tau and Spearman Rho.

I can't work out if this is a deliberate feature or some other thing ;)

No matter, at least I know.

Ignoring many attributes

The "set role" operator has a nice feature that lets you set the role of an attribute to free text.

By setting the role to something like "ignore" subsequent modelling operators will not process the attribute.

Here's an example that creates some fake data with 4 attributes and then sets three of them to be ignored. This causes the clustering operator to perform more poorly because it ignores some of the attributes.

Note that the roles have to be different so in this case they are "ignore01", "ignore02" and "ignore03". If you set them all to "ignore", an error happens.

Note too that the "set additional roles" dialog is a bit fiddly as it loses focus after each character is typed but it does work.

Counting clusters: part IV

Here's an example process that uses the operator "Map Clustering on Labels" to match labels to clusters. If the data already has labels, the operator allows the output from a clustering algorithm to be assessed. It compares labels and clusters and determines the best match. From this, the output is a prediction and this can be passed to a performance operator to allow a confusion matrix to be created.

This allows a clustering algorithm to be used for prediction if training examples are available.

How regression performance varies with noise

Here's a table showing how the various performance measures from the regression performance operator change as more and more noise is added for a regression problem (it's the process referenced in another post).

This is not a feature of RapidMiner as such, it's simply a quick reference to show the limits of these performance measures under noise free and noisy conditions so that when they are seen for a real problem, the table might help orientate how good the model is.

What does X-Validation do?

The model from X-Validation applied to all the test data will not match the performance estimate given by the same operator.

This is correct behaviour but can be confusing.

Following on from this thread on the RapidMiner forum my explanation of this is as follows.

A 10 fold cross validation on the Iris data set using Decision Trees produces a performance estimate of 93.33% +/- 5.16%. If you use the model produced by this operator on the whole dataset you get a performance of 94.67% (note: in fact, this model is the same as one produced by using the whole dataset).

Which performance number should be believed and why is there a difference?

Imagine someone were to produce a new Iris data set. If we use the complete model to predict the new data, what performance would we get? Would 94.67% or 93.33% be more realistic? There is no right answer but the 93.33% figure is probably more likely to be realistic because this is what the performance estimate is providing. The whole point of the X-Validation operator is to do this; namely estimate what the performance would be on unseen data; outputting a model is not its main aim.

It works by splitting the data into 10 (this is the default) partitions each containing 90% of the original data. It then builds a model on each 90% and applies it to the 10% to get a performance. It does this for all 10 partitions to get an average.

To illustrate with an example, the following 10 performance values are produced inside the operator (I'm using accuracy from the Performance Classification operator and the random number seed for the whole process is 2001).


0.867
0.933
0.933
1.0
0.933
1.0
0.933
1.0
0.867
0.867

The arithmetic mean of these is 0.933 and this matches the performance output by the X-Validation operator; namely 93.33%. The stdevp of these values is 0.051511; this matches the 5.16% error output by the operator. This means the X-Validation operator averages the performance for all the iterations inside the operator (note: if the performance result shows an error estimate then you know that some averaging has been done).

Each of the 10 models may be different. This is inevitable because the data in each partition is different. For example, manual inspection of the models produced inside the operator leads to differences as shown below.

The final model happens to be the same as the first of these but there is no reason to suppose that it would be in general. In practice, the models are likely to be the same in all cases, but it is worth bearing in mind that they might not be.

Nonetheless, the end result is likely to represent the performance of a model built using known data and applied to unknown data. Simply building a model on all data and then applying it to this data may result in a performance that is higher because of overfitting. Using this latter prediction is not as good because no unseen data has been used to make any models.