## Decision Trees

It is also known as Divide-And-Conquer method. This method constructs a rule by dividing overly general rules into a set of rules, which correspond to conjunction subsets of the examples. It then continues recursively with those rules for which the corresponding subsets contain both positive and negative examples. The final rule set consists of all specialized rules for which the corresponding sets contain positive examples only. Some examples of these systems are:

J48 (C4.5)
J48 algorithm is the Weka implementation of the C4.5 top-down decision tree learner proposed by Quinlan. The algorithm uses the greedy technique and is a variant of ID3, which determines at each step the most predictive attribute, and splits a node based on this attribute. Each node represents a decision point over the value of some attribute. J48 attempts to account for noise and missing data. It also deals with numeric attributes by determining where thresholds for decision splits should be placed. The main parameters that can be set for this algorithm are the confidence threshold, the minimum number of instances per leaf and the number of folds for reduced error pruning.

Ross Quinlan (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, San Mateo, CA.

Alternating decision trees (ADTree) algorithm is a generalization of decision trees, voted decision trees and voted decision stumps. The algorithm applied boosting procedures to decision tree algorithms to produce accurate classifiers. The classifiers are in the form of a majority vote over a number of decision trees but having a smaller and easier to understand classification rules.

DecisionStump
DecisionStump algorithm builds simple binary decision ‘stumps’ (1 level decision tress) for both numeric and nominal classification problems. It copes with mission values by extending a third branch from the stump or treating ‘missing’ as a separate attribute value. DecisionStump is usually used in conjunction with a boosting algorithm such as LogitBoost. It does regression (based on mean-squared error) or classification (based on entropy).

Witten, I.H., Frank, E., Trigg, L., Hall, M., Holmes, G., Cunningham, S.J. Weka: Practical machine learning tools and techniques with java implementations. In Proc. ICONIP/ANZIIS/ANNES’99 Int. Workshop: Emerging Knowledge Engineering and Connectionist-Based Info. Systems. (1999) 192-196

RandomTree
RandomTree is an algorithm for constructing a tree that considers K randomly chosen attributes at each node. It performs no pruning.

http://www.lsi.upc.es/~bejar/apren/docum/doc/weka/classifiers/trees/RandomTree.html

REPTree
REPTree algorithm is a fast decision tree learner. It builds a decision/regression tree using information gain/variance and prunes it using reduced-error pruning (with back-fitting). The algorithm only sorts values for numeric attributes once. Missing values are dealt with by splitting the corresponding instances into pieces (i.e. as in C4.5).

http://www.dbs.informatik.uni-muenchen.de/Lehre/KDD_Praktikum/weka/doc/weka/classifiers/trees/REPTree.html

## Rule learner (or Rule Induction)

It is also known as Separate-And-Conquer method. This method apply an iterative process consisting in first generating a rule that covers a subset of the training examples and then removing all examples covered by the rule from the training set. This process is repeated iteratively until there are no examples left to cover. The final rule set is the collection of the rules discovered at every iteration of the process [13]. Some examples of these kinds of systems are:

OneR

OneR or “One Rule” is a simple algorithm proposed by Holt. The OneR builds one rule for each attribute in the training data and then selects the rule with the smallest error rate as its ‘one rule’. To create a rule for an attribute, the most frequent class for each attribute value must be determined. The most frequent class is simply the class that appears most often for that attribute value. A rule is simply a set of attribute values bound to their majority class. OneR selects the rule with the lowest error rate. In the event that two or more rules have the same error rate, the rule is chosen at random.

Ridor

Ridor algorithm is the implementation of a RIpple-DOwn Rule learner proposed by Gaines and Compton. It generates a default rule first and then the exceptions for the default rule with the least (weighted) error rate. Then it generates the “best” exceptions for each exception and iterates until pure. Thus it performs a tree-like expansion of exceptions. The exceptions are a set of rules that predict classes other than the default. IREP is used to generate the exceptions.

PART

PART is a separate-and-conquer rule learner proposed by Eibe and Witten. The algorithm producing sets of rules called ‘decision lists’ which are ordered set of rules. A new data is compared to each rule in the list in turn, and the item is assigned the category of the first matching rule (a default is applied if no rule successfully matches). PART builds a partial C4.5 decision tree in each iteration and makes the “best” leaf into a rule. The algorithm is a combination of C4.5 and RIPPER rule learning.

JRip (RIPPER)

JRip implements a propositional rule learner, Repeated Incremental Pruning to Produce Error Reduction (RIPPER), which was proposed by William W. Cohen as an optimized version of IREP. Ripper builds a ruleset by repeatedly adding rules to an empty ruleset until all positive examples are covered. Rules are formed by greedily adding conditions to the antecedent of a rule (starting with empty antecendent) until no negative examples are covered. After a ruleset is constructed, an optimization postpass massages the ruleset so as to reduce its size and improve its fit to the training data. A combination of cross-validation and minimum-description length techniques is used to prevent overfitting.

DecisionTable

DecisionTable algorithm builds and using a simple decision table majority classifier as proposed by Kohavi. It summarizes the dataset with a ‘decision table’ which contains the same number of attributes as the original dataset. Then, a new data item is assigned a category by finding the line in the decision table that matches the non-class values of the data item. DecisionTable employs the wrapper method to find a good subset of attributes for inclusion in the table. By eliminating attributes that contribute little or nothing to a model of the dataset, the algorithm reduces the likelihood of over-fitting and creates a smaller and condensed decision table.

ConjunctiveRule

ConjuctiveRule algorithm implements a single conjunctive rule learner that can predict for numeric and nominal class labels. A rule consists of antecedents “AND”ed together and the consequent (class value) for the classification/regression. In this case, the consequent is the distribution of the available classes (or mean for a numeric value) in the dataset. If the test instance is not covered by this rule, then it’s predicted using the default class distributions/value of the data not covered by the rule in the training data. This learner selects an antecedent by computing the Information Gain of each antecedent and prunes the generated rule using Reduced Error Pruning (REP) or simple pre-pruning based on the number of antecedents. For classification, the Information of one antecedent is the weighted average of the entropies of both the data covered and not covered by the rule.

## Medical Data Mining

Data mining and knowledge discovery is the process of finding patterns, trends and regularities by sifting through large amounts of data [1]. Using data stored in databases, data mining involves the creation of prediction (or classification) models, segmentation (or clustering) records based on similarity of attributes and discovery of association rules (or patterns). Nowadays, medical (or clinical) databases have accumulated large amounts of data on patients and their medical conditions. This kind of information, stored along with that of other patients, make up an ideal place to look for new analysis and patterns, or to validate proposed hypotheses. To exploit such large volumes of medical data, numerous inductive data analysis techniques derived from Machine Learning (ML) study have been successfully applied to medical data to discover useful and new knowledge [2, 3, 4]. However, medical data mining is considered by many ML communities as the most complex and problematic domain yet to be overcome [5, 6].

The range of applications of medical data mining is very wide, with the two most popular applications being diagnosis and prognosis. Diagnosis is the process of selectively gathering information concerning a patient, and interpreting it according to previous knowledge, as evidence for or against the presence or absence of disorders [7]. In a prognostic process, a patient’s information is also gathered and interpreted, but the objective is to predict the future development of the patient’s condition. Due to the predictive nature of this process, prognostic systems are frequently used as tools to plan medical treatments [8].

In the context of the data mining tasks, diagnosis and prognosis are to discover knowledge necessary to interpret the gathered information. In some cases this knowledge is expressed as probabilistic relationships between clinical features and the proposed diagnosis or prognosis. In other cases, the system is designed as a black-box decision maker that is totally unconcerned with the interpretation of its decisions. Finally, in yet other cases, a rule-based representation is chosen so as to provide the physician with an explanation of the decision. The latest is the most convenient way for physician to express their knowledge in medical diagnosis. In particular, if learned diagnostic rules can be presented in such a form, physicians are much more likely to trust and believe the consequent diagnoses. Thus, the major challenge presented by medicine is to develop technology to provide trusted hypotheses based on measures which can be relied upon in medical research and clinical hypothesis formulation [9].