Introduction

An Example

The Algorithm

Constructive Induction

Related Work

Our Papers on Function Decompositon



Orange

Data sets

Spotlight

Looking for a public data mining software? Try Orange, a scriptable component based framework.

Want to use decision support tool, but your computer is just not there when you need it? Check our handheld-based decision-support schema and our PalmPilot software.

Explore what we are doing in functional genomics.

FRI > Biolab > Function Decomposition > An Example

An Example

Suppose a function y=F(x1,x2,x3) is given where x1, x2, and x3 are attributes and y is the target concept. y, x1, and x2 can take the values lo, med, hi; x3 can take the values lo, hi. The function F is partially specified with a set of examples in the following table.


There are three non-trivial partitions of the attributes: <x1>|<x2,x3>, <x2>|<x1,x3>, and <x3>|<x1,x2>, and three corresponding decompositions: y=G1(x1,H1(x2,x3)), y=G2(x2,H2(x1,x3)), and y=G3(x3,H3(x1,x2)). These decompositions are given in the following figure.


The comparison of three different decompositions above shows that:

  • Example sets in the decomposition y=G1(x1, H1(x2, x3)) are overall smaller than those for the other two decompositions.

  • The new concept c1=H1(x2, x3) uses only three values, whereas that for H2(x1, x3) uses four and that for H3(x1, x2) uses five.

  • By inspecting the example sets for H1 and G1 it is easy to see that c1 corresponds to MIN(x2, x3) and y to MAX(x1,c1). It is harder to interpret the sets of examples for G2, H2, G3, and H3.

Among the three attribute partitions it is therefore beneficial to decide for <x1>|<x2,x3> and decompose y=F(x1,x2,x3) to y=G1(x1, c1) and c1 = H1(x2, x3)).

Above illustrates how a single step decomposition can be applied to a data set, resulting in a (hierarchy) of two data sets. If we would have a more complex data set (having more than three attributes), the two resulting data set may be considered for further decomposition. In this way, the overall decomposition algorithm recursively applies single step decomposition, until some termination criterion (say, for instance, decomposition has derived data sets with only two attributes) is satisfied. The result is a concept hierarchy, with a number of tables (data sets) which provide for an extensional definition of concepts. A number of such examples of function decomposition's utility have been documented, and decomposition was tested on example sets much more complex than the one used above. For example, and to illustrate for the hierarchies that decomposition can develop, in one of our early experiments we have tested decomposition on a nursery data set and obtain a following hierarchy:

Note that the number of new concepts (besides the target one) is six. The numbers besides the names of attributes and concepts denote their cardinality (the number of values they use). Nursery data set is special, as it was itself generated from the concept hierarchy: this enabled us to check how close to original hierarchy is the one discovered. Our experiments show that function decomposition behaves rather well in this respect. Check this yourself by comparing the above hierarchy with the original one for nursery data set.