Tuesday, October 6, 2009


In their paper, "MESO: Supporting Online Decision Making in Autonomic Computing Systems", Kasten and McKinley showcase their novel approach to pattern classification. Called MESO (Multi-Element Self-Organising tree), this pattern classifier is designed to support online, incremental learning and decision making in autonomic systems.

Using supervised data MESO uses a novel approach to cluster data. It also unveils a new tree structure to organise the resulting clusters, which the authors call sensitivity spheres.

To create their sensitivity spheres, Kasten and McKinley improved on the long standing leader follower algorithm which creates small clusters of patterns. Basically, a training pattern within a specified distance is assigned to that cluster, otherwise a new cluster is created.

What is the problem with the algorithm: The distance measure which determines the size of the clusters is fixed throughout the clustering process.

In their paper the authors proposed the use of a growth function to remedy this problem.
grow_{\delta }  = \frac{(d - \delta) \frac{\delta}{d}f }{1 + ln(d - \delta + 1)^{2} }

d \rightarrow distance between the new pattern and the nearest sensitivity sphere

\frac{\delta}{d}  \rightarrow scales the result relative to the difference between the current \delta and d

Note: the denominator serves to limit the growth rate based on how far the current \delta is from d

Once the data is assigned to these clusters or sensitivity spheres, it is then organised into a novel tree structure. Kasten boasts of a tree structure which rather than focussing on putting individual patterns into large clusters close to the root of the tree, he instead places the focus on his sensitivity spheres. He then builds a MESO tree starting at the root node which is home to all the sensitivity spheres. He further explains:

The root node is then split into subsets of similar spheres which produces child nodes. Each child node is futher split into subsets until each child contains only one sphere.


Using the eight datasets in the table below MESO results shows it superiority in terms of speed and accuracy against other classifiers.

No comments:

Post a Comment