Distributed Data Mining: Why Do More Than Aggregating Models

1 Introduction

This paper deals with the problem of mining several large and geographically distributed databases (DBi) with the goal of producing a set of classification rules that explains the various groupings found in the observed data. The result of this mining is both a predictive and descriptive meta-classifier. In other words, we aim at producing a model which is not only capable of predicting the class of new objects, but which is also able to explain the choices of its predictions. We believe that this kind of models, based on classification rules, should also be easy to understand by humans, which is also one of our objectives. Also, our application context is one where it is impossible to gather all these databases on the same site, and this, either because of downloading time, or because of the difficulty to mine the aggregated database.

In the literature, we find very few distributed data mining techniques which are both predictive and descriptive. The majority of them try to produce a meta-classifier in the form of a set of rules with disjoint cover, i.e., where an object is covered by one and only one rule. We will show in this paper that this constraint of disjoint cover is not necessary to produce a reliable meta-classifier and furthermore, introduces unnecessary complexity to the mining technique. Therefore, we propose a simpler technique where an object can be covered by several rules, and where the lifting of this constraint enables us to produce a conceptually very simple classifier with good prediction capability as will be shown below.

The performance of our meta-classifier (from a prediction point of view) is compared to C4.5 applied on the whole database DB = ∪iDBi; it is used only as a reference to assess the potential loss of accuracy of our method since, by assumption, we stated that we could not process DB because of download/processing time constraints.

This paper proceeds as follows. We present in sections 2 a survey of some well known model aggregation techniques. Then, in section 3, we present our solution for distributed data mining (DDM) by model aggregation (DDM-MA) based on a majority vote that is pondered by some confidence coefficient. Section 4 introduces a conceptual comparison between our method and those found in the literature. In section 5, we present experimental results which prove the viability of our method. We will show that it bares comparable accuracy rates while being simpler that other DDM methods. We finally present a conclusion and our future work.

2 Model aggregation existing techniques

As we present in this paper a technique developed in a distributed data mining perspective, we will ignore some non relevant techniques as the Ruler System [Fayyad et al., 1993] [Fayyad et al., 1996] that was developed for the aggregation of several decision trees build on the same data set in a centralized system, the Distributed Learning System [Sikora and Shaw, 1996] developed in a context of information management system that builds a distributed learning system, and the Fragmentation Approach [W¨uthrich, 1995] which uses probalistic rules. Also, we will ignore purely predictive techniques such as bagging [Breiman, 1996], boosting [Schapire, 1990], stacking [Tsoumakas and Vlahavas, 2002], and the arbiter and combiner methods [Chan, 1996], [Prodromidis et al., 2000].

2.1 TheMIL algorithm

The MIL algorithm (Multiple Induction Learning) was initially proposed by Williams [Williams, 1990] in order to resolve conflicts between conflictual rules in expert systems. Authors of [Hall et al., 1998a; 1998b] took again the technique of Williams [Williams, 1990] to aggregate decision trees built in parallel and transformed beforehand into rules. The process of aggregation proposed by these authors is a regrouping of rules accompanied by a process of resolution of the possible conflicts between them. It should be noted that this resolution of the conflicts treats only one pair of conflict rules at a time. Two rules are considered in conflict when their premises are consistent while they produce two different classes [Williams, 1990] (called conflict of type I) , or when the conditions of the premises overlap partially [Hall et al., 1998a] (called conflict of type II) or when the rules have the same number of predicates with different values for conditions and they classify objects into the same class [Hall et al., 1998b] (called conflict of type III).The conflict resolution consists in either specializing one or the two rules in conflict (conflicts type I and II), or in adjusting the value of the condition, i.e., the test boundary, for the conflicts of type II and III and eventually in combining the two rules in conflict (conflict of type III). In certain cases (conflicts of type I and II), new rules are added based on the training sets to recover the cover lost by the specialization process.

2.2 The DRL system (Distributed Rule Learner)

The DRL technique (Distributed Rule Learner) [Provost and Hennessy, 1996] was conceived based on the advantage of the invariant-partitioning property [Provost and Hennessy, 1994]. The DRL technique begins by partitioning the training data E into nd disjoined subsets, assigns each one (Ei) to a different machine, and provides the infrastructure for the communication between different learners (named RL). When a rule r satisfies the evaluation criterion for a subset of the data (i.e., f ′ (r, Ei, nd) ≥ c ; f ′ being an evaluation function 1 of a rule and c a constant), it becomes a candidate to satisfy the global evaluation criterion; the extended invariant-partitioning property guarantees that each rule which is satisfactory on the whole data set will be acceptable at least on one subset. When a local learner discovers an acceptable rule, it sends the rule to the other machines so that they update its statistics on the remainder of the examples. If the rule meets the global evaluation criterion (f(r, E) ≥ c; f being the principal evaluation function and c a constant), it is asserted as a satisfactory rule. In the opposite case, its local statistics are replaced by the global statistics and the rule is made available to be specialized some more. The property of invariant-partitioning guarantees that each satisfactory rule on the whole data set will be found by at least one of the RLs.

2.3 Combining rule sets generated in parallel

The work presented by [Hall et al., 1999] is a mixture of the last two techniques presented above, i.e., that of [Williams, 1990], [Hall et al., 1998b] and [Provost and Hennessy, 1996]. In details, they associate to each rule a measurement of its "quality" which is based on its prediction precision as well as on the number and the type of the examples that it covers.

The technique suggested in [Hall et al., 1999] is based on the use of what [Provost and Hennessy, 1996] proposes (see §2.2), with a small difference where the deletion of the rule from the space of rules under consideration is made only when the rule classifies all the data of the various distributed bases, which is the case when its measure f(r,E) is lower than a certain threshold. It should be noted that each rule does not "travel" alone from one site to another, but is indeed accompanied by the values necessary to calculate the measure associated with each rule.

1 This rule evaluation function could be for example the Laplace precision estimator [Segal and Etzioni, 1994] [Webb, 1995].

However, in [Hall et al., 1999], the authors show that in the extreme case the property of invariant-partitioning could not be satisfied. Thus, they prove that the precision of the aggregate rule set can be very different from the precision of the rules built on the training set. Moreover, the authors show that conflicts between rules can be solved, as described by [Hall et al., 1998b] and [Williams, 1990].

In addition, [Hall et al., 1999] proposes a new type of conflict between rules: a rule whose premise contains some interval that overlaps an interval that is contained in the premise of a second rule. In this case, a more general rule is created by combining the two conflicting rules and by adjusting the border values of these intervals.

3 The proposed model aggregation technique

The proposed technique is very simple. We build in parallel over each distributed DBi a model, i.e., a set of classification rules Ri, called base classifier. Figure 1 shows an example of such rules.

IF adoption_of_the_budget_resolution = n IF physician_fee_freeze = y THEN CLASS: republican IF adoption_of_the_budget_resolution = u IF physician_fee_freeze = y THEN CLASS: democrat

Then, we compute for each rule a confidence coefficient (see below for details). Finally, in a centralized site, base classifiers are aggregated in the same set of rules (R = ∪iRi) which represents our final model, called meta-classifier. The global algorithm of our distributed data mining technique is described by Figure 2.

1. Do in parallel over each database DBi
2. (a) Apply on DBi a classification algorithm producing a set of disjoint cover rules. The produced set is

• where ni is the number of rules; (b) Compute for each rik a confidence coefficient crik (see hereafter);
• In a central site create:

where nd is the number of distributed databases.

Figure 2: Algorithm of the proposed DDM technique.

Since different rule sets are going to be merged together whereas they are issued from different data subsets, and since each rule r has its proper error rate Er and coverage n, we compute for each rule a confidence coefficient cr. This confidence coefficient is computed in straightforward manner from the lower bound of an error rate confidence interval proposed by [Langford, 2005]. We defined it as one minus the worst error rate in (1 - δ) of the time :

Since R is not a set of disjoint cover rules where an object is covered by a unique rule, we explain hereafter how we can use this meta-classifier as a predictive and descriptive model.

3.1 The use of R as a predictive model

The set R represents the aggregation of all base classifiers (R = ∪iRi). This rule set is used as a predictive model as well as a descriptive one. From a predictive point of view, the predicted class of a new object is the class predicted by a majority vote of all the rules that cover it, where the rules are weighted by their confidence coefficients 2 . It should be noted that, contrarily to what is identified in the literature (see §2), we have restricted the notion of rules in conflict to be those that cover the same object but with different classification results. If several rules cover the same object and predict the same class, we do not consider them as being in conflict.

It is to be noted that any object can be covered by at most nd rules, knowing that nd is the number of sites.

3.2 The use of R as a descriptive model

As a classification system is often developed as support to decision-making, the different rules covering an object may be proposed to the user who could then judge, from his expertise, of their relevance, helped by a confidence coefficient. Presenting to a decision maker more than one rule may have its advantages since it may provide a larger and more complete view of the "limits" of each class. We bring to mind, that in machine learning, the limit which defines separation between various classes is generally not unique nor clear cut, and consequently, several rules producing the same class can represent the "hyper-planes" separating the various classes, providing various views on these data.

4 A conceptual comparison

4.1 TheMIL technique

The MIL technique [Hall et al., 1998a] [Hall et al., 1998b] suffers from several problems. First of all, the process of conflict resolution only specializes the rules based on the classification rules data sets. The generated rules could show poor classification ability when they are applied to new objects, especially in the case of very noisy training data. In addition, the adaptation of the technique of Williams [Williams, 1990] in order to treat distributed bases implies an increase in the volume of data exchanged between the various sites. Indeed, on the one hand, each rule travels accompanied by the index of the covered objects and, on the other hand, in the event of conflict, all the objects covered by one of the two rules in conflict must be downloaded from the training site to the site resolving the conflict.

2 However, in an unlikely tie situation, we propose to carry out a simple majority vote. In very rare cases, when the simple majority vote also leads to a tie, we choose the majority class in the different training sets.

4.2 The DRL system

The most significant disadvantage of the DRL system [Provost and Hennessy, 1996] is its execution time. Indeed, when a rule is considered to be acceptable by a given site, it must go across to all the other sites. In other words, any acceptable rule on a site must classify all the data of all the other sites. Thus, the rule must, on the one hand,"travel" through all the sites, and on the other hand, classify the data of each site. If a rule is not considered to be satisfactory on the whole data set, this rule is specialized and the process starts again if it is considered to be locally acceptable. It is clear that this process could be very time consuming.

4.3 Combining rule sets generated in parallel

As for the system of combining rule sets generated in parallel, it is identical to the previous one with a little difference: any rule generated in a given site must cross over to all the other sites. Thus, the number of rules traveling between the various sites is more significant than the number of rules of the DRL system. Consequently, it is clear that this technique is slower than the preceding one.

4.4 The proposed technique

To overcome the problems of MIL technique, the proposed one is based on a majority vote that is known to be rather a robust model against noisy data. Indeed, the prediction process gives good results especially in noisy bases (see §5 below).

In the proposed technique (see §3) rules "travel" only in one way, from the distributed database site to the central site and the amount of data is almost minimal where a rule is augmented by no more than its confidence coefficient. Thus the problem of excess communication found in the DRL system and its successor is avoided.

From an execution point of view, an asymptotic analysis was conducted in [Aounallah, 2006] and [Aounallah and Mineau, 2006] of our technique and those presented in §2 of this paper. This asymptotic analysis shows clearly that in the worst case our technique is faster than existing ones.

In the best case, we expect our technique to be at least comparable to existing ones. Since having no conflicts between different base classifiers is very rare, we believe that our technique is faster than existing ones because our technique does not conduct any conflict resolution step.

Moreover, the proposed technique is no more than a simple aggregation of base classifiers. Consequently, there is no doubt that it is conceptually by far simpler that existing comparable ones, i.e., it should be faster and simpler to implement than those found in the literature (see §2).

5 An empirical comparison

To evaluate the performance of our DDM technique, we conducted some experiments in order to assess its prediction (accuracy) rate. We compared it to a C4.5 algorithm built on the whole data set, i.e., on the aggregation of the distributed databases. This C4.5, produces a rule set R′ , which is used as a reference for its accuracy rate since we assumed in the introduction that it is impossible to gather all these bases onto a single site, and this, either because of downloading time, or because of the difficulty to learn from the aggregated base because of its size. The rule set R′ is considered to be the ideal case, where theoretically it is not possible to perform better than a model built on the whole data set.

The conducted experiments have been tested on nine data sets: chess end-game (King+Rook versus King+Pawn), Crx, house-votes-84, ionosphere, mushroom, pima-indiansdiabetes, tic-tac-toe, Wisconsin Breast Cancer (BCW)[Mangasarian and Wolberg, 1990] and Wisconsin Diagnostic Breast Cancer (WDBC), taken from the UCI repository [Blake and Merz, 1998]. The size of these data sets varies from 351 objects to 5936 objects (Objects with missing values have been deleted). Furthermore, in order to get more realistic data sets, we introduced noise in the nine aforementioned databases, and this by reversing the class attribute 3 of successively 10%, 20%, 25% and 30% of objects. Hence, since for each data set we have, in addition to the original set, 4 other noisy sets, giving a total number of databases of 45.

In order to simulate a distributed environment, the data sets have been divided as follows. We divided each database into a test set with proportion of 1/4. This data subset was used as a test set for our meta-classifier and for R′ , our reference classifier. The remaining data subset (of proportion 3/4), was divided randomly into 2, 3, 4 or 5 data subsets in order to simulate distributed databases. The size of these bases was chosen to be disparate and in such a way so there was a significant difference between the smallest and the biggest data subset. As an example of such subdivision see Figure 3.

For the construction of the base classifiers we used C4.5 release 8 [Quinlan, 1996] [Quinlan, downloaded in 2004]

3 Please note that all data sets have a binary class attribute.

which produces a decision tree that is then directly transformed into a set of rules. The confidence coefficient of each rule was computed using the program offered by Langford [Langford, downloaded in 2006] with a basis of 95% confidence interval (i.e., δ = 0.05).

In order to assess the prediction capability of our technique we compared its prediction rate to the one of R′ over the 45 aforementioned data sets. Table 1 to 5 detail the results obtained. The third and the forth columns of these tables contain respectively the lower and the upper bound of R′ error rate confidence interval computed at 95% confidence. The last column contains:

• "+" if our technique outperformsR′ ,
• "-" if R′ outperforms our meta-classier and
• a blank if the two techniques are statistically comparable.

From these tables, we can see that our meta-classier performance is very comparable to the one of R′ since in 35 cases over 45 its error rate is statistically comparable and only in 3 cases it is worst than R′ . Moreover, surprisingly, our metaclassifier could outperformR′ in 7 cases; this is especially the case when noise in distributed data sets is important. In these cases, we could easily see the advantage of using a noise robust model as the weighted majority vote in a non disjoint cover rule set, instead of using a single model with disjoint cover rule set.

These results, prove also the viability of the confidence coefficient proposed in this paper.

6 Conclusion

The objective of this paper is to present a very simple distributed data mining technique (DDM) by model aggregation (MA). With this intention, we presented, on the one hand, a rapid survey of existing model aggregation techniques which are most comparable to ours. And on the other hand, we presented a description of our DDM-MA technique.

Throughout this paper, we have shown that the proposed DDM technique is conceptually by far simpler that existing comparable techniques. Indeed, it consists of a simple aggregation of distributed models (base classifiers).

Experiments demonstrate that our technique, from a prediction point of view, performs as well as or even better, than a classifier built over the whole data set, R′ , the theoretically ideal case since it is built over the whole data. Our metaclassifier R could outperform R′ due to the weighted majority vote pondered by a confidence coefficient associated to each rule. This confidence coefficient is based on the lower bound of an error rate confidence interval proposed by [Langford, 2005]. In other words, such a mojority vote over imperfect rules gives very good predictive results because the confidence coefficient used in the process uses these rules with a weight that reflects their individual prediction power.

Moreover, since the granularity of the majority vote is at rule level (instead of classifier level), the meta-classifier R can be used as a descriptive model, where the predictive class of an object is described by the rules covering it.

Due to these good results, we can imagine that our technique could be applied on very large centralized databases that could be divided into smaller ones before applying our technique, rather than applying a data mining tool over the centralized database; this is what we propose to explore in a near future.

Furthermore, we propose, on the one hand, to test the proposed technique on n-ary databases and, on the other hand, to compare it experimently to exiting techniques.