Classification is an important topic in data mining research. Given a set of data records, each of which belongs to one of a number of predefined classes, the classification problem is concerned with the discovery of classification rules that can allow records with unknown class membership to be correctly classified. Many algorithms have been developed to mine large data sets for classification models and they have been shown to be very effective. However, when it comes to determining the likelihood of each classification made, many of them are not designed with such purpose in mind. For this, they are not readily applicable to such problem as churn prediction. For such an application, the goal is not only to predict whether or not a subscriber would switch from one carrier to another, it is also important that the likelihood of the subscriber's doing so be predicted. The reason for this is that a carrier can then choose to provide special personalized offer and services to those subscribers who are predicted with higher likelihood to churn. Given its importance, we propose a new data mining algorithm, called DMEL, to handle classification problems of which the accuracy of each predictions made has to be estimated. In performing its tasks, DMEL searches through the possible rule space using an evolutionary approach that has the following characteristics: (i) the evolutionary process begins with the generation of an initial set of first-order rules (i.e., rules with one conjunct/condition) using a probabilistic induction technique and based on these rules, rules of higher order (two or more conjuncts) are obtained iteratively; (ii) when identifying interesting rules, an objective interestingness measure is used; (iii) the fitness of a chromosome is defined in terms of the probability that the attribute values of a record can be correctly determined using the rules it encodes; and (iv) the likelihood of predictions (or classifications) made are estimated so that subscribers can be ranked according to their likelihood to churn. Experiments with different data sets showed that DMEL is able to effectively discover interesting classification rules. In 2 particular, it is able to predict churn accurately under different churn rates when applied to real telecom subscriber data. Index Terms: data mining, predictive modeling, evolutionary computation, genetic algorithms, rule interestingness measures, churn prediction, customer retention, customer relationship management. Classification is an important topic in data mining research. Given a set of data records, each of which belongs to one of a number of predefined classes, the classification problem is concerned with the discovery of classification rules that can allow records with unknown class membership to be correctly classified. Many algorithms have been developed to mine large data sets for classification models and they have been shown to be very effective [3, 16-17, 30, 36-38]. However, when it comes to determining the likelihood of each classification made, many of them are not designed with such purpose in mind. Existing data mining algorithms such as decision tree based algorithms (e.g. possible that some leaves in a decision tree have similar class probabilities. Unlike decision tree based algorithms, other classification techniques such as logit regression and neural networks [3] can determine a probability for a prediction with its likelihood. However, comparing with decision tree based algorithms, these algorithms do not explicitly express the uncovered patterns in a symbolic, easily understandable form (e.g., if-then rules). Owing to the limitations of these existing techniques, we propose a new algorithm, called DMEL (Data Mining by Evolutionary Learning), to mine classification rules in databases. The DMEL algorithm has the following characteristics. First, instead of random generation, the initial population, which consists of a set of first-order rules 1 , is generated non-randomly using a probabilistic induction technique. Based on these rules, rules of higher orders are then obtained iteratively with the initial population at the start of 1 In this paper, the order of the rule is related to the number of conditions in the antecedent of a rule. A onecondition rule is therefore a first-order rule. If a rule's antecedent contains two conditions, it is a second-order rule. If there are three conditions in the antecedent of a rule, it is a third-order rule, and so on. 3 each iteration obtained based on the lower order rules discovered in the previous iteration. Second, when identifying interesting rules, DMEL uses an objective interestingness measure that does not require subjective input from the users. Third, in evaluating the fitness of a chromosome, DMEL uses a function, which is defined in terms of the probability that the attribute values of a tuple can be correctly determined using the rules it encodes. Fourth, the likelihood of predictions (or classifications) made is estimated. Fifth, DMEL is able to handle missing values in an effective manner. Using the discovered rules, DMEL can be used to classifying records with unknown class membership. In particular, DMEL is able to predict churn, which is concerned with the loss of subscribers who switch from one carrier to another. Since competition in the telecommunications industry is very fierce, many carriers consider reducing churn as an important business venture to maintain profitability. Churn costs carriers a large amount of money annually in North America and Europe [28] . A small reduction in annual churn rate can result in a substantial increase in the valuation and the shareholder value of a carrier [28] . Consequently, analyzing and controlling churn is critical for carriers to improve their revenues. To reduce churn rate, a carrier gives us a database of 100,000 subscribers. Among these subscribers, some of them had already switched to another carrier. The task assigned to us is to mine the database to uncover patterns that relate the demographics and behaviors of subscribers with churning so that further loss of subscribers can be prevented as much as possible. Efforts are then made to retain subscribers that are identified to have a high probability of switching to other carriers. Since the customer services centers of the carrier only have a fixed number of staff available to contact a small fraction of all subscribers, it is important for it to distinguish subscribers with high probability of churning from those with low probability so that, given the limited resources, the high probability churners can be contacted first. For such an application, the goal is not only to predict whether or not a subscriber would switch from one carrier to another, it is also important that the likelihood of the subscriber's doing so be predicted. It can be difficult for the carrier to take advantage of the discovery because the carrier does not have enough resources to contact all or a large fraction of the subscribers. On the other hand, logit regression and neural networks, which can determine a probability for a prediction with its likelihood, do not explicitly express the uncovered patterns in a symbolic, easily understandable form. It is for this reason that the carrier did not consider these approaches as the best for their task concerned as they could not verify and interpret the uncovered churning patterns. Unlike existing techniques, DMEL is able to mine rules representing the churning patterns and to predict whether a subscriber is likely to churn in the near future. Experimental results show that it is able to discover the regularities hidden in the database and to predict the probability that a subscriber churns under different churn rates. In addition, since some attributes in the subscriber database contains significant amount of missing values, the ability of DMEL to handle missing values effectively is important to the success of DMEL in churn prediction. In the following section, we review related work in data mining and evolutionary computation literature for building predictive models. In particular, we explain how they can be used in churn prediction. In Section 3, we provide the details of DMEL and explain how it can be used to discover interesting rules hidden in databases. To evaluate the performance of DMEL, we applied it to several real-world databases. The experimental results are given in Section 4. The details of the subscriber database provided by a carrier in Malaysia and the experimental results using this database to test if DMEL is effective for churn prediction are then given in Section 5. Finally, in Section 6, we give a summary of the paper. Among the different approaches for building predictive models in data mining, decision-tree based algorithms are the most popular (e.g., [16-17, 30, 36-38] Assume that the records in a database are characterized by n attributes, A 1 , …, A i , …, A n and that A i is the attribute whose values are to be predicted. In the tree-building phase, a decision tree is constructed by recursively partitioning the training set according to the values of A j , j = 1, …, n, j ≠ i. This partitioning process continues until all, or the majority, of the records in each partition have the same attribute values, Since the resulting decision tree may contain branches that are created due to noises in the data, some of the branches may need to be removed. The tree-pruning phase, therefore, consists of selecting and removing the sub-trees that have the largest estimated error rate. Tree pruning has been shown to increase the prediction accuracy of a decision tree on one hand and reduce the complexity of the tree on the other. Of the many decision tree based algorithms that have been used in data mining, C4.5 is by far the most popular [36] . Other than the use of decision tree based algorithms, techniques based on genetic algorithms (GAs) have also been proposed for predictive modeling. There are currently two different GA-based approaches for rule discovery: the Michigan approach and the Pittsburgh approach. The Michigan approach, exemplified by Holland's classifier system [21] , represents a rule set by the entire population whereas the Pittsburgh approach, exemplified by Smith's LS-1 system [39] , represents a rule set by an individual chromosome. Although the Michigan approach is able to deal with multi-class problems, one of the major difficulties in using it is the problem in credit assignment, which gives the activated classifiers a reward if the classification they produced is correct and gives them a punishment, otherwise. Specifically, it is extremely hard to come up with a good credit assignment scheme that works. The algorithms based on the Pittsburgh approach (e.g., [10, 23, 39] ) represent an entire rule set as a chromosome, maintain a population of candidate rule sets, and use selection and genetic operators to produce new generation of chromosomes and, hence, new rule sets. Each chromosome competes with one another in terms of classification accuracy on the application domain. Individuals are selected for reproduction using roulette wheel selection and a whole new population is generated based on crossover and mutation. The selected chromosomes produce offspring using an extended version of the standard two-point crossover operator such that the crossover points can occur either both on rule boundaries or within rules [10, 39] . That is, if one parent is being cut on a rule boundary, then the other parent must be cut on a rule boundary as well; similarly, if one parent is being cut at a point, say, 5 bits to the right of a rule boundary, then the other parent must be cut in a similar spot [10, 39] . The mutation operator is identical to the classical one, which performs bit-level mutations. The fitness of each individual rule set is computed by testing the rule set on the current set of training examples [10, 39] . The Pittsburgh approach was originally designed for single-class learning problems and hence only the antecedent of a rule was encoded into an allele of a chromosome [10, 23, 39 ]. An instance that matches one or more rules is classified as a positive example of the concept (class) and an instance that fails to match any rule is classified as a negative example [10, 23, 39] . To tackle multi-class problems, they could be extended by introducing multiple populations so that a specific population is dedicated to learn each concept. It is possible that an instance is matched by more than one rule of different concepts on one hand and it is also possible that an instance is matched by none of any rule of any concept on the other. Unfortunately, this problem has not been addressed in many of the systems based on the Pittsburgh approach (e.g., [10, 23, 39] ). Recently, the use of GAs for rule discovery in the application of data mining has been studied in [9, 12, 15, 26] . These algorithms are based on the Michigan approach in a way that each rule is encoded in a chromosome and the rule set is represented by the entire population. Unlike classifier systems (e.g., [19, 21, 29] It is important to note that these algorithms [9, 12, 15] were developed to discover rules for a single class only. When they are used to deal with multi-class problems, the GAs are run once for each class. Specifically, they would search rules predicting the first class in the first run; they would search rules predicting the second class in the second run and so on. Similar to the Pittsburgh approach, it is possible that an instance is matched by more than one rule predicting different classes on one hand and it is also possible that an instance is matched by none of any rule predicting any class on the other. This problem has not been addressed by these algorithms. Although GA-based rule discovery approaches can produce accurate predictive models, they cannot determine the likelihood associated with their predictions. This prevents these techniques from being applicable to the task of predicting churn, which requires the ranking of subscribers according to their likelihood to churn. A related work on churn prediction in a database of 46,744 subscribers has been presented in [32] . The performances of logit regression, C5.0 (a commercial software product based on C4.5), and nonlinear neural networks with a single hidden layer and weight decay [3] are evaluated empirically. The experimental results in [32] showed that neural networks outperformed logit regression and C5.0 for churn prediction. An empirical comparison of DMEL with neural networks and C4.5 on the subscriber database provided by the carrier in Malaysia will be given in Section 5. To perform search more effectively in a huge rule set space, we propose to use an evolutionary algorithm called DMEL. Using an evolutionary learning approach, DMEL is capable of mining rules in large 7 databases without any need for user-defined thresholds or mapping of quantitative into binary attributes. However, DMEL requires quantitative attributes to be transformed to categorical attributes through the use of a discretization algorithm, as will be seen later. In this paper, the order of the rule is related to the number of conditions in the antecedent of a rule. A one-condition rule is therefore a first-order rule. If a rule's antecedent contains two conditions, it is a second-order rule. If there are three conditions in the antecedent of a rule, it is a third-order rule, and so on. DMEL discovers rules by an iterative process. It begins with the generation of a set of first-order rules using a probabilistic induction technique. Based on these rules, it then discovers a set of secondorder rules in the next iteration and based on the second-order rules, it discovers third-order rules, etc. In other words, if we refer to the initial set of first-order rules as R 1 , the rules in R 1 are then used to generate a set of second-order rules, R 2 . R 2 is then used to generate a set of third-order rules, R 3 , and so on for 4th and higher order rules. In general, at the (l -1)-th iteration, DMEL begins an evolutionary learning process by generating an initial population of individuals (each represents a set of l-th order rules) by randomly combining the rules in R l -1 to form a set of rules of order l. Once started, the iterative learning process goes on uninterrupted until no more interesting rules in the current population can be identified. The DMEL algorithm is given in Fig. 1 below. The decode function in Fig. 1 is to extract all the interesting rules encoded in a chromosome and store them in R l . If an allele in the chromosome is found interesting based on the objective measure defined in Section 3.2, the decode function will extract the rule it encodes. The rule set returned by the decode function therefore contains interesting rules only. When none of the rules encoded in the individual is found interesting, the decode function will return a null set and hence R l will become a null set. For the evolutionary process, DMEL encodes a complete set of rules in a single chromosome in such a way that each gene encodes a single rule. Specifically, given the following l-th order rule, for example: where ŵ , given by Equation (14) later, is an uncertainty measure associated with it, this rule is encoded in DMEL by the allele given in Fig. 2 It should be noted that the consequent and the uncertainty measure are not encoded. This is because the consequent is not, and in fact, should not be determined by chance. In DMEL, both the consequent and the uncertainty measure are determined when the fitness of a chromosome is computed. Given this representation scheme, the number of genes in the chromosome is, therefore, the same as the number of rules in the rule set. 9 DMEL begins the evolutionary process by the generation of a set of first-order rules. When compared to randomly generated initial population, it has been shown that heuristically-generated initial populations can improve convergence speed and find better solutions [20, 22, 24, 41] . Based on these findings, DMEL first discovers a set of first-order rules and places it in the initial population. Furthermore, the initial first-order rules are generated very rapidly. The time it takes to generate the initial population that contains the first-order rules is negligible when compared to the time it takes for the best set of rules to be evolved. The generation of first-order rules can be accomplished by using the interestingness measure given by Equation (5) and the weight of evidence measure given by (14) Instead of using the chi-square test, we propose to use the residual analysis [6] [7] to determine whether a ip is dependent on a jq . We consider the association between a ip and a jq interesting if the probability of finding a ip in a tuple given that a jq is in the same tuple is significantly different from the probability of finding a ip in the tuple alone. In other words, therefore, there exists an interesting association between a ip and a jq if  To decide if the difference is significant, the adjusted residual [6] [7] The measure defined by (5) , whenever a jq is found, the probability that a ip is also found in the same tuple is expected to be significantly lower than when a jq is not found. In such a case, we say that a jq is negatively associated with Given that a ip and a jq are positively or negatively associated, a measure of the strength of the association can be defined. In [6] [7] , such a measure is proposed and it is called the weight of evidence measure. This measure is defined in terms of an information theoretic concept known as mutual information. Mutual information measures the change of uncertainty about the presence of a ip in a tuple given that it has a jq . It is defined as follows: Based on the mutual information measure, the weight of evidence measure is defined as [6] [7] When the number of tuples characterized by both a jq and a ip is sufficiently large, we can simply use the sample posterior probability of a ip given a jq , Pr(A i = a ip | A j = a jq ), as the population posterior probability. However, under skewed class distributions, the number of tuples having a jq and a ip can be very small and this can prohibit the use of the sample posterior probability as the population posterior probability. To obtain the population posterior probability, we propose to use an empirical Bayes method, which takes both the sample posterior and the sample prior probabilities into consideration [4] . The empirical Bayes estimation of the posterior probability of a ip given a jq is defined as: where B is the shrinkage factor, which weighs the importance of the posterior and the prior probabilities. Assuming the probability distribution of the records having a jq and a ip and the probability distribution of the estimated posterior probability are both Gaussian, the shrinkage factor is defined as: The weight of evidence defined in Equation (9) can then be modified as: By the use of the interestingness measure given by Equation (5) and the weight of evidence measure given by (14), a set of interesting first-order rules can be discovered. Once these rules are discovered, DMEL will begin an iterative process of initialization of population, evaluation of fitness of individuals, selection, reproduction, and termination, etc., so as to discover higher order rules. Since a good initial population may improve the speed of the evolutionary process and make it easier for an optimal solution to be found, DMEL does not generate its initial populations completely randomly. Instead, it makes use of a heuristic in which the association between a jq ∧ a ks and a ip is more likely to be interesting if the association between a jq and a ip and the association between a ks and a ip are interesting. The initialize function takes as argument, R l -1 . The chrom i .allele j in Fig. 3 denotes the j-th allele of the ith chromosome. The rand l (R) function returns an l-th order allele constructed by randomly combining l elements in R. For our experiments, popsize was set to 30 and the number of alleles in each chromosome was set to nalleles = |R l -1 | where |R l -1 | denotes the number of rules in R l -1 . We set nalleles = |R l -1 | because each allele represents the antecedent of a rule and the chromosome is used to encode R l -1 . The genetic operators used by DMEL are implemented in the reproduce function shown in Fig. 4 The crossover(chrom 1 , chrom 2 ) function uses the two-point crossover operator because it allows the combination of schemata, which is not possible with the classical, one-point crossover [31] . DMEL uses two different strategies in choosing the crossover points, namely, crossover-1 and crossover-2. The crossover-1 operator allows the crossover points to occur between two rules only whereas the crossover-2 operator allows the crossover points to occur within one rule only. An example of the crossover-1 operator and that of the crossover-2 operator are graphically depicted in Fig. 5 and Fig. 6 , respectively. In DMEL, the crossover probability for the crossover-1 operator and that for the crossover-2 operator are denoted as p 1 and p 2 , respectively. For our experimentation, four different setups are used and they are summarized in Table 1 . The first three setups, DMEL-1, DMEL-2, and DMEL-3, use constant values of p 1 and p 2 whereas the last
Wai-Ho Au et al. REF proposed a novel evolutionary algorithm data mining by evolutionary learning (DMEL) that not only predicts whether the customer will churn but also the likelihood of doing so.
A Novel Evolutionary Data Mining Algorithm With Applications to Churn Prediction
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION
Computer Science