In this paper, we discuss the integration of complex aggregates in the construction of logical decision trees. We review the use of complex aggregates in TILDE, which is based on an exhaustive search in the complex aggregate space. As opposed to such a combinatorial search, we introduce a hill-climbing approach to build complex aggregates incrementally.
Relational data mining deals with data represented by several tables. We focus on the typical setting where one table, the primary table, contains the target column, i.e. the attribute whose value is to be predicted, and has a one-to-many relationship with a secondary table. A possible way of handling such relationships is to use complex aggregates, i.e. to aggregate the objects of the secondary table which meet a given condition, using an aggregate function on the objects themselves (count function) or on a numerical attribute of the objects (e.g. max, average functions). For instance, we may want to classify molecules. Molecules have atoms. They can be represented as a table of molecules and a table of atoms, with a foreign key in the table of atoms indicating the molecule it belongs to. Then, the class of a molecule may depend on the comparison between the average of the charge of the carbon atoms of the molecule and some threshold value. This example also shows what a complex aggregate relies on: an aggregate function (here the average), a condition to select the objects to aggregate (here we select only the carbon atoms), the attribute to aggregate on (here the charge of the atoms), an operator and a threshold to make a comparison with the result of the aggregation.
Previous work showed that the expressivity of complex aggregates can be
useful to solve problems such as urban blocks classi cation. [
The rest of this paper is organized as follows. In Sect. 2, we review the use of complex aggregates in TILDE. In Sect. 3, we describe our heuristic to explore the complex aggregate space. Finally, in Sect. 4, we detail future work. 2
TILDE [
Then, TILDE has been extended [
However, the implementation does not allow more than two conjuncts in the aggregate query "due to memory problems" [6, p. 32], which limits the search space. Numerical attributes are handled by a comparison to a threshold in problems such as geographical ones. It is possible to discretize numerical attributes beforehand and to de ne predicates to make those comparisons between the values of the attributes and the thresholds given by the discretization. Nevertheless, enumerating all the combinations of thresholds over all the numerical attributes takes space in memory, and hence the approach is not tractable. To summarize, this combinatorial approach which handles complex aggregates in TILDE has limitations. We intend to overcome these limitations by not trying to explore the search space exhaustively, but by nding a heuristic to explore the search space and to build complex aggregates incrementally. 3
Incremental Construction of Complex Aggregates with Hill-Climbing Our goal is to build a logical decision tree, like TILDE, which uses complex aggregates to deal with secondary tables. To explore the re nement cube of complex aggregates, we choose to use a hill-climbing method. This section details the method. We use the general notation "f unction(condition)foperatorgthreshold" to refer to a complex aggregate. 3.1
When testing an aggregate, we make a re nement to nd the best aggregate, and a hill-climbing is performed from a starting aggregate. In this paper, we limit ourselves to the count function to aggregate secondary tables. The starting conditions are detailed below. We then try to re ne it with hill-climbing, allowing a non-strict climbing: if there is no strictly improving re nement, we allow picking a re nement with the same score as in the previous step, if it has not been visited before. To achieve that, we store all previous re nements chosen in the hill-climbing path. From the current aggregate, there are several ways to modify it: { Firstly, given the examples, we compute the possible results of the aggregate function, which will serve as possible thresholds. To these values, we add one threshold depending on the operator: strictly lower than the other values if the operator is (so that the complex aggregate is true for none of the examples) and strictly higher if the operator is . Such thresholds are chosen to be respectively MAX DOUBLE and its opposite. The current threshold is then set to the closest possible threshold if it is lower than the minimum or higher than the maximum of the possible thresholds. For instance, if the current re nement to try is "the count of atoms in the molecule is less than or equal to M AX DOU BLE" and, in the training set, there are between 13 and 42 atoms in a molecule, the threshold will be immediately set to 42. { Then, we can re ne the aggregate by increasing or decreasing the threshold (among the possible thresholds). { Other possibilities are to remove a literal from the aggregate condition, or to add one.
The Starting Conditions Given this, if we refer to the maximum threshold as max, 2 starting conditions will be count(true) max and count(true) M AX DOU BLE. From the point of view of the examples considered, they are opposite: if one succeeds for an example, the other will fail. The former is the most general (i.e. it succeds for every example), the latter the most speci c. We then observe that re nements for one will have the same e ect on information gain for the other (the nal branch of the examples will be inverted between both), so on the training set, they are equivalent, and will be re ned equivalently. In the end, we get two conditions count(condition) someT hreshold and count(condition) nextT hreshold which are opposite. To conclude on this point, considering both starting conditions is not necessary, since they will be re ned following similar paths and will yield the same information gain after the hill-climbing process. Of course, the same reasoning applies for starting conditions count(true) M AX DOU BLE and count(true) min, this is the reason why we consider only two starting conditions, arbitrarily with the operator .
Moving in the Complex Aggregate Space We now discuss our method for re nement of the aggregate. If we add a literal to the aggregate condition, it will yield a specialization and less objects will be selected. The threshold range discussed above will not be the same, and the current threshold, associated to the previous, more general condition, will not be relevant since it may be too high. Hence, the re nement will yield a poor gain ratio and will not be chosen. For instance, in the training set, there are between 13 and 42 atoms in a molecule, but only between 5 and 20 carbon atoms. If the current aggregate states that "the count of atoms is less than or equal to 30", and we try to re ne it to "the count of carbon atoms is less than or equal to 30", this last aggregate will be true for every example, yielding zero gain, and hence will not be chosen. Of course, the problem will be similar if we consider the other way, i.e. if we drop a literal from the aggregate condition, yielding a generalization.
To avoid modifying the aggregate condition without modifying the threshold, we do as follows. When modifying the aggregate condition, we consider the number of possible thresholds n1 given by the current aggregate condition, and the number of thresholds n2 given by the next (after modi cation) aggregate condition. We sort those two sets those thresholds in increasing order, such that the current threshold is in position c1 with indices going from 0 to n1 1, the next threshold chosen, in position c2 between 0 and n2 1 will be picked such that n2c2 1 is closest to n1c1 1 . Mathematically: c2 = round( c1 n(n12 1 1) ). Since we add a threshold to a list which already contains at least one element, there are always at least two possible thresholds and hence the case n1 = 1 is not an issue. 3.2
We nally discuss a problem that will occur with aggregate functions other than
count : the computation of a value for empty sets. Indeed, an aggregate condition
might select no object, and aggregation over a numerical attribute is not possible
in this case. For instance, how can the mean of the charge of the oxygen atoms
in a molecule be computed when the molecule does not have any oxygen atom?
Only the count function can deal in a natural way with empty sets, while another
solution has to be chosen for numerical aggregate functions. Some possibilities
to deal with this issue have been discussed in [
In our opinion, the two rst options are not easy to apply for every function. Indeed, for functions min or max, one can choose values as low or as high as possible so that the aggregate always succeeds or fails if the function cannot be applied directly. But for the average function, using a xed value such as 0 is not relevant if the attribute can take both positive and negative values, neither is choosing positive or negative in nity. Moreover, the fact that the set to aggregate is empty can be meaningful, and by assigning a result to the aggregate function we lose this signi cance. The third option also gives to the empty set a meaning we do not necessarily want it to have: the failure of the aggregate should mean the inequality between the result of the aggregation and the threshold is wrong. However, this is not the meaning of the empty set. Actually, it is implied by the failure of the existential quanti er for the aggregate condition, i.e. count(condition) 1 fails.
Then we see two ways to address the issue of empty sets: rstly to consider them as a third branch in our decision trees, since they do not correspond to a success or a failure of the inequality, they are a third possibility. However, this option breaks the binary structure of the tree, which is not necessarily a problem. Nevertheless, we present another option to preserve the binary tree structure: the principle is to create a node with the count(condition) 1 aggregate before adding a node with an aggregate with a function which may not be applicable. In the left branch, we can then add the aggregate f unction(condition) threshold without the empty set problem, since we know from the parent node that condition will select at least one object. This adapts the three-branch idea to preserve the binary tree structure, using two nodes instead of one. An example is shown in Fig. 1, where the aggregate "the average charge of the carbon atoms in the molecule is greater than or equal to 0.542" is "protected" by the existential quanti er which tests the presence of at least one carbon atom in the molecule, i.e. the aggregate "the count of carbon atoms in the molecule is greater than or equal to 1". If the latter succeeds, then the former can be evaluated because it is meaningful to compute the average value of a non-empty set. If the existential quanti er fails, then the average is not computed because it would be meaningless. 4
The method described in Sect. 3 is implemented and will be evaluated. The next
step in this work is to consider other aggregate functions, on numerical attributes
of the secondary objects, and to allow the change of the aggregate function in
the re ning process of the aggregates, by taking advantage of their ordering as
in [
true count(B, (atom(A,B), atom type(B,carbon)), Res1), Res1 1 true false . . . . . .
false . . . be formed both ways with such relationships, which can possibly lead to loops in the recursivity discussed above.