Adam Omielan

Sunil Vadera

ECCO: A New Evolutionary Classifier with Cost Optimisation

Keywords:

Decision tree learning algorithms and their application represent one the major successes of AI. Early research on these algorithms aimed to produce classification trees that were accurate. More recently, there has been recognition that in many applications, aiming to maximize accuracy alone is not adequate since the cost of misclassification may not be symmetric and that obtaining the data for classification may have an associated cost. This has led to significant research on the development of cost-sensitive decision tree induction algorithms. One of the seminal studies in this field has been the use of genetic algorithms to develop an algorithm known as ICET. Empirical trials have shown that ICET produces some of the best results for cost-sensitive decision tree induction. A key feature of ICET is that it uses a pool that consists of genes that represent biases and parameters. These biases and parameters are then passed to a decision tree learner known as EG2 to generate the trees. That is, it does not use a direct encoding of trees. This paper develops a new algorithm called ECCO (Evolutionary Classifier with Cost Optimization) that is based on the hypothesis that a direct representation of trees in a genetic pool leads to improvements over ICET. The paper includes an empirical evaluation of this hypothesis on four data sets and the results show that, in general, ECCO is more cost-sensitive and effective than ICET when test costs and misclassifications costs are considered.

Background

Decision tree learning algorithms have been widely studied since Quinlan first developed the ID3 algorithm [START_REF] Quinlan | Induction of Decision Trees[END_REF], with significant impetus given by developments such as C4.5 [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF], and its availability in the Weka system [START_REF] Witten | Data Mining: Practical Machine Learning Tools and Techniques[END_REF]. These decision tree learning algorithms aim to take a table of examples as input and produce a decision tree of the kind shown in Figure 1, where there are decision nodes such as Test A, Test B and Test C, and outcomes of the tests decision nodes that are labeled on the links, such as Improve, Same and Deteriorate.

Fig. 1. A decision tree

Early decision tree learning algorithms, such as CART [START_REF] Breiman | Classification and Regression Trees[END_REF], and ID3 [START_REF] Quinlan | Induction of Decision Trees[END_REF] aimed to learn such trees from a set of training data. They built decision trees in a greedy fashion, where a test is first chosen as a root.

The training examples are then divided into subsets associated with each possible value of the chosen test. The process is then applied recursively until the examples in the subsets all have the similar outcomes, resulting in leaf or decision nodes. A significant step in this greedy algorithm is the criteria for selecting the next test. Most of the early algorithms adopted information theoretic measures that selected tests on the basis of the amount of information gained towards the final classification. The primary aim of these greedy algorithms was to produce accurate decision trees, where accuracy was estimated by the proportion of cases for which the data in a testing set were correctly classified. However, several authors recognized that maximizing accuracy is not adequate for many real world applications and that costs need to be taken into account (e.g., [START_REF] Breiman | Classification and Regression Trees[END_REF][START_REF] Turney | Cost-Sensitive Classification: Empirical Evaluation of a Hybrid Genetic Decision Tree Induction Algorithm[END_REF][START_REF] Vadera | CSNL A cost-sensitive non-linear decision tree algorithm[END_REF]). There are several types of costs but the main ones include the costs of misclassifying an example and the cost of acquiring information [START_REF] Turney | Types of cost in inductive concept learning[END_REF]. For example, in a medical application misclassifying a person as healthy when they are ill can be higher than misclassifying them as ill, and the cost of carrying out an MRI scan can be higher than a blood test.

Research on development of cost-sensitive decision tree algorithms can be broadly classified into the following main categories:

1. Algorithms that adopt the Greedy algorithm but that adapt the information theoretic selection measures to include costs. The key difference amongst algorithms in this category is how the information gain measure is adapted to include costs and whether they take account of just the costs of the tests, or also take cost of misclassification. Algorithms that take account of just costs of attributes include CS-ID3 [START_REF] Tan | Cost-Sensitive Concept Learning Of Sensor Use in Approach and Recognition[END_REF], IDX [START_REF] Norton | Generating Better Decision Trees[END_REF], EG2 [START_REF] Núnez | The Use of Background Knowledge in Decision Tree Induction[END_REF] , CSGain [START_REF] Davis | Cost-sensitive decision tree learning for forensic classification[END_REF]. Algorithms that also adapt the information theoretic measure to include costs of misclassification include PM [START_REF] Liu | A New Cost-Sensitive Decision Tree with Missing Values[END_REF], and CS-4.5 [START_REF] Freitas | Cost-Sensitive Decision Trees applied to medical data[END_REF]. 2. Algorithms that utilise bagging and boosting methods that generate alternative trees and combine them in a way that reduces cost. For example, the MetaCost system [START_REF] Domingos | MetaCost: A general method for making classifiers cost-sensitive[END_REF] resamples the data several times and applies a base learner (such as C4.5) to each sample to generate alternative decision trees. The decisions made on each example by the alternative trees are combined to predict the class of each example that minimizes the cost and the examples relabeled. The relabeled examples are then processed by the base learner, resulting in a cost-sensitive decision tree. Other examples of systems that adopt bagging include B-PET & B-LOT [START_REF] Moret | Learning to predict channel stability using biogeomorphic features[END_REF], and examples of systems that use boosting methods include AdaCost [START_REF] Fan | AdaCost: misclassification cost-sensitive boosting[END_REF] and Lp-CSB [START_REF] Lozano | Multi-class cost-sensitive boosting with p-norm loss functions[END_REF]. 3. The use of Genetic Algorithms (GAs) to generate and evolve cost-sensitive trees.

The idea with these methods is to begin with a genetic pool, select the fittest, apply evolution operators such as mutation and crossover to generate a new pool and repeat the evolution cycles, resulting in improved pools. The main algorithm in this category is Turney's ICET [START_REF] Turney | Cost-Sensitive Classification: Empirical Evaluation of a Hybrid Genetic Decision Tree Induction Algorithm[END_REF] (Inexpensive Classification with Expensive Tests). ICET begins by dividing the training set of examples into two random but equal parts: a sub-training set and a sub-testing set. An initial population is created consisting of individuals with random values of CAi, ω, and CF, which are parameters required by C4.5 and EG2 . C4.5, with the EG2's cost function, is then used to generate a decision tree for each individual. These decision trees are then passed to a fitness function to determine fitness. This is measured by calculating the average cost of classification on the sub-testing set. The next generation is then obtained by using the roulette wheel selection scheme, which selects individuals with a probability proportional to their fitness. Mutation and crossover are used on the new generation and passed through the whole procedure again. After a fixed number of generations the best decision tree is selected.

A comprehensive survey of these algorithms that includes a framework and timeline covering over 50 algorithms can be found in Lomax and Vadera [START_REF] Lomax | A Survey of Cost-Sensitive Decision Tree Induction Algorithms[END_REF]. This paper focuses on this last category: algorithms that use genetic algorithms for generating costsensitive decision tree algorithms. By far the most widely known and cited algorithm in this category is Turney's ICET [START_REF] Turney | Cost-Sensitive Classification: Empirical Evaluation of a Hybrid Genetic Decision Tree Induction Algorithm[END_REF]. In our previous empirical evaluations, ICET produced some of the best results in comparison to algorithms from other categories [START_REF] Lomax | An Empirical Comparison of Cost-Sensitive Decision Tree Induction Algorithms[END_REF]. As mentioned above, a key feature of ICET is that the population of individuals consists of biases that are utilized when C4.5 is used to generate decision trees. That is the individuals in the population are not direct encodings of trees. This paper presents a new algorithm called ECCO that is based on the hypothesis that direct encoding of trees in a pool could improve upon the results of Turney's seminal system ICET. The next section of the paper describes how ECCO is developed using a GA and is followed by a section that presents an empirical evaluation of the hypothesis that a direct representation of trees leads to improvements over the ICET system.

The ECCO algorithm

To develop a cost-sensitive decision tree algorithm that is based on the use of a genetic algorithm we need to address the following questions:

• How can the trees be represented as genes?

• What mutation and cross-over operators are appropriate?

• What sort of fitness function is appropriate?

The following subsections describe how these questions are addressed, leading to the ECCO algorithm.

Encoding the tests and Trees as Genes

The genes in GAs are represented as bit strings. To represent a tree as a bit string, we need to first code each test. Each test is given a unique identification number, from 1 to n, where n is the total number of tests. Each identifier is then converted to its binary equivalent. To code a tree as a fixed length binary string, we need to assume a fixed size tree. The maximal size of a tree is determined by the number of possible values of the tests. For example, a test such as 'It has wings' has only two outcomes, true or false. More complex tests give rise to more outcomes, e.g. A test such as 'How many eggs?' when classifying a recipe may well have '0, 1, 2, 3' eggs possible, and so four child nodes are needed. Given that we know the tests and the maximal number of possible outcomes of tests, we can compute the maximal size of a tree. This can then be used to compute the length of the bit string required to represent a tree. Figure 2 illustrates a mapping for tree of depth 3 assuming a maximal of two outcomes per test (the idea extends to n-ary trees). It's worth noting that continuous variables are handled by using the process used in systems such as C4.5 where they discretized to axis parallel binary tests (See Quinlan C4.5 [START_REF] Quinlan | C4.5: Programs for Machine Learning[END_REF] for details).

Fig. 1. An illustration of how trees are represented genes

In general, a bit string may not correspond to a fully populated tree and, so such maximal trees need interpretation. Even if we begin with fully constituted trees in the initial population, such trees may arise because of the evolution process described in the next section. The interpretation used is to assume that the highest parent node that does not correspond to a test is assumed to be a leaf node (i.e. a classification denoting an outcome).

Evolving the population

Having developed a representation of trees, the next question is: how can the populations evolve? This is done by using the standard crossover and mutation operations.

The crossover process takes two of the fittest genes of a population, and combines the first part of one, and the second part of the other to create a new gene. Figure 3 illustrates the crossover operator on two genes representing decision trees. The position of the split is at any random point in the string, but must be on a boundary between nodes. The genes that are chosen for the crossover operation include a random mix of the genes, with greater weighting given to the fittest genes.

Fig. 2. The crossover operation on representations of trees

The mutation operation changes up to 2% of the nodes. Thus if there are fifty nodes at most in a string, up to one of them will be changed into a different node. This helps prevent the tree from becoming stuck if the fittest genes become identical, and to evolve further to test other slightly different trees.

Fitness Function

The fitness function has to assess the overall cost of the tree. First the tree needs to be trained to set the classification at each leaf node. That is, a proportion of the data provided is processed through the tree, marking at each node that it has been accessed, and at the classification node the class that row of data belongs to, is appropriately marked. The class chosen at a leaf node is then selected as the one that minimizes the cost of misclassification based on the user provided costs of misclassification. Once a tree is trained, it is possible to traverse the tree with each example and compute its cost as the sum of the tests used and the cost of any misclassification. Given these results, the obvious question to explore is the behaviour of the two approaches when the costs of misclassification are smaller. Figure 5, below, presents the results when the misclassifications cost ratios are varied from 1.5 to 5 and the test costs available in the benchmark data sets are used. The Dn indicates that a tree of depth n is used and results with pruning are indicated with a Pr while results without pruning are indicated with a NPr. These results also show: (a) that ECCO converges to minima more quickly than ICET, (b) that ICET is not very sensitive to increases in misclassification costs, (c) in this range, there isn't much variation in the results whether or not ECCO uses pruning (indeed the differences are not visible in Figure 5 where the lines combine).

Conclusion

This paper has introduced a new cost-sensitive decision tree learner, ECCO, that is based on the use genetic algorithms to evolve trees. The algorithm utilizes a more direct coding of trees as genes than the widely cited ICET algorithm that uses biases as genes and utilizes C4.5 and EG2 to generate the trees from the biases. Empirical trials were conducted on four benchmark data sets and the results show that ECCO is more cost-sensitive than ICET to increases in the ratio of costs of misclassification and ECCO produces trees that enable more cost-effective decision making than ICET. As future work, the performance of ECCO needs to be evaluated on a wider range of benchmark data and against a wider range of cost-sensitive algorithms such as those mentioned in [START_REF] Vadera | CSNL A cost-sensitive non-linear decision tree algorithm[END_REF][START_REF] Lomax | A Survey of Cost-Sensitive Decision Tree Induction Algorithms[END_REF][START_REF] Lomax | An Empirical Comparison of Cost-Sensitive Decision Tree Induction Algorithms[END_REF].

Fig. 4 .

 4 Fig. 4. Results with misclassification costs in the range 1.5 to 5

Te st A PRI CE YES YES NO Te st B Imp rove Deter iorate Low High Te st C YES Bad Go od Same NO

  The average cost over the examples in the training set is then the fitness function.

	3	E mpirical co omparison	with ICET T
	This sect tion presents a an empirical e evaluation of	ECCO. The	primary idea	being ex-
	plored is	that utilizing		a direct encod ding of decisio on trees for a	GA instead o of utilizing
	an interm mediate decisio on tree genera ator will result t in better per rformance. T The ECCO
	algorithm m was implem mented by util lizing the GE ENSIS [20] g genetic algorit thm and a
	version o of ICET imple	mented as par rt of previous	work [6] was	utilized.
	The ex xperiments we ere designed	to test the pe rformance of f ECCO under r a variety
	of condit tions, and to m make compari isons to the p performance o of ICET. To u understand
	how the a algorithms ar	e affected, ex xperiments we ere first condu ucted where th he cost of
	misclassi fication of on ne class over a another were	set to: 10, 50	, 100, 500, 10 000, 5000,
	10000. A All the experi iments were p performed wi ith ten iteratio ons using rand domly se-
	lected tra aining sets con nsisting of tw wo-thirds of th e data and the e remaining th hirds used
	as testing g data to comp pute the averag ges. The dept th of trees for r ECCO was a also varied
	from 5 to o 11.
	The m maximum dept th was chose n as the deep pest depth tha at would give e a binary
	"101 001 010 011 101 011 010" string tha at was smaller r than 50,000 b bits in length,	parent gene with a minim mum depth of 5 5. This bit
	"001 111 010 000 100 010 011" length wa as chosen for r performance reasons; the needed fo or the Geneti c Algorithm's s operations, b larger the str ring the longe er the time parent gene but a smaller string leads to a more
	restrictive e maximum d depth. This va alue as an upp per limit prov vided a satisfa actory bal-
	ance.
	The ex xperiments we ere performed d on the widel ly used liver,	heart, hepatit	is, and di-
	"101 001 010 011 101 010 011" abetes be enchmark data a sets availabl le from the UC CI machine le new gene earning reposi itory [21].
	A range	of experimen nts were carr ried out, inclu uding when m misclassificati ions costs
	alone are e considered,		and when bot th test and m misclassificatio on costs are co onsidered.
	The resu ults had a com mmon pattern n for all the d data sets and	occurs irresp pective of
	whether o or not test cos sts were includ ded. This com mmon pattern n is illustrated	by Figure
	4, which	shows the per rformance of	ICET and EC CCO (with a d depth of 5, wit th pruning
	and inclu uding both test t costs) on the e Hepatitis dat ta set. As thi is illustrates, a as the cost
	of miscla assification in ncreases, ECC CO is more	sensitive and d performs b better than
	ICET. Th he scale of imp provement is	similar on the e other data se ts.
			F Fig. 3. Averag e cost as miscl assification co sts increase for r hepatitis dat	a