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.