WIXLIB

ID3ID3 (Iterative Dichotomiser 3)Most basic decision tree algorithm, by Ross Quinlan (1986)Begin with the original set S as the root nodeOn each iteration of the algorithm, iterate through every unused attribute of the set S andcalculate a measure for that attribute, e.g. Entropy H(S) and Information Gain IG(A,S)Select the best attributeSplit S on the selected attribute to produce subsetContinue to recurse on each subset, considering only attributes not selected before (for thisparticular branch of the tree)Recursion stops when every element in a subset belongs to the same class label, or there are nomore attributes to be selected, or there are no instances left in the subset33

ID334

ID335

ID336

Impurity measuresWhich measure?Based on impurity Minimal impurity Also minimal impurity Maximal impurity37

Impurity measuresIntuitively, it's easy to see that: Is better than: But what about: We need a measure38

EntropyEntropy is a measure of the amount of uncertainty in a data set (informationtheory)H(S) x X p(x)log2 (p(x)) with S the data (sub)set, X the classes(e,g, {yes, no}), p(x) the proportion of elements with class x over S When H(S) 0, the set is completely pure (alle elements belong to the same class)39

EntropyFor the original data set, we get:#yes #no x yes x no Entropy95-0.41-0.530.9440

Information gain We can calculate the entropy of the original set and all the subsets, but how tomeasure the improvement?Information gain: measure of the difference in impurity before and after the splitHow much uncertainty was reduced by a particular split?IG(A, S) H(S) t T p(t)H(t) with T the set of subsets obtainedby splitting the original set S on attribute A and p(t) t / S 41

Information gainOriginal set S:#yes #no x yes x no Entropy95-0.41-0.530.94Calculate the entropy for all subsets created by all candidate splitting bset #yes #no x yes x no -0.40.59Strong33-0.50-0.501Weak62-0.31-0.50.81042

Information gainIG(A, S) H(S) t T p(t)H(t)545IG(outlook, S) 0.94 - ( 140.97 140.00 140.97) 0.94 - 0.69 0.25 highest IGIG(temperature, S) 0.03IG(humidity, S) 0.15IG(wind, S) 0.05#yes #no x yes x no HumidityWindSubset #yes #no x yes x no -0.40.59Strong33-0.50-0.501Weak62-0.31-0.50.81043

ID3: after one split44

ID3: continueRecursion stops when every element in a subset belongs to the same class label,or there are no more attributes to be selected, or there are no instances left in thesubset45

ID3: final treeAssign labels to the leaf nodes: easy -- just pick the most common class46

Impurity measuresEntropy (Shannon index) is not the only measure ofimpurity that can be usedEntropy: H(S) x X p(x)log2 (p(x))Gini diversity index: Gini(S) 1 x X p(x)2Gini gain similar as information gain with Entropy (use Gini(S) instead ofH(S))Not very different: Gini works a bit better for continuous variables (see after) and is a little fasterMost implementations default to this approachClassification error: ClassErr(S) 1 maxx X p(x)Something to think about: why not use accuracy directly? Or another metric ofinterest such as AUC or precision, F1, .?47

Summary so farUsing the tree to predict new labels is just as easy as using a regression formula: just follow thequestions in the tree and look at the outcomeEasy to understand, easy (for a computer) to constructCan be easily expressed as simple IF.THEN rules as well, can hence be easily implemented inexisting programs (even as a SQL procedure)Fun as background research: algorithms exist which directly try to introduce prediction modelsin the form of a rule base, with RIPPER (Repeated Incremental Pruning to Produce ErrorReduction) being the most well known. It's just as old and leads to very similar models, but hassome interesting differences and is (nowadays) not widely implemented or known anymore48

/rules.html49

Problems still to solveID3 is greedy: it never backtracks (i.e.retraces on previous steps) during theconstruction of the tree, it only movesforwardThis means that global optimality of the tree is notguaranteedAlgorithms exist which overcome this (see e.g.evtree package for R), though they're often slowand do not give much better results (greedy is goodenough)A bigger problem however is the fact that wedo not have a way to tackle continuousvariables, such as temperature 21, 24, 26,27, 30, .Another big problem is that the "grow for aslong as you can" strategy leads to trees whichwill be horribly overfitting!50

Spotting overfittingNote that this is a good motivating case to illustrate the difference between"supervised methods for predictive analytics" or "for descriptive analytics"51

C4.5Also by Ross QuinlanExtension of ID3Main contribution: dealing with continuous variablesCan also deal with missing variables. The original paper describes that you just ignore themwhen calculating the impurity measure and information gain, though most implementations donot implement this!Also allows to set importance weights on attributes (biasing the information gain, basically)Describes methods to prune trees52

C4.5: continuous variablesSay we want to split on temperature 21, 24, 26, 27, 30, .Obviously, using the values as-is would not be a good ideaWould lead to a lot of subsets, many of which potentially having only a few instancesWhen applying the tree on new data: the chance of encountering a value which was unseenduring training is much higher than for categoricals, e.g. what if temperature is 22?Instead, enforce binary splits by:Splitting on temperature 21 -- two subsets (yes, no) -- and calculate the information gainSplitting on temperature 24 -- two subsets (yes, no) -- and calculate the information gainSplitting on temperature 26 -- two subsets (yes, no) -- and calculate the information gainSplitting on temperature 27 -- two subsets (yes, no) -- and calculate the information gainAnd so on.Important: only the distinct set of values seen in the training set are considered, though somepapers propose changes to make this a little more stable53

C4.5: preventing overfittingEarly stopping: stop based on a stop criterionE.g. when number of instances in subset goes below a thresholdOr when depth gets too highOr: set aside a validation set during training and stop when performance on this set starts todecrease (if you have enough training data to begin with)54

C4.5: preventing overfittingPruning: grow the full tree, but then reduce itMerge back leaf nodes if they add little power to the classification accuracy"Inside every big tree is a small, perfect tree waiting to come out." --Dan SteinbergMany forms exist: weakest-link pruning, cost-complexity pruning (common), etc Oftentimes governed by a "complexity" parameter in most implementations55

C5 (See5)Also by Ross QuinlanCommercial offeringFaster, memory efficient, smaller trees, weighting of cases and supplying misclassification costsNot widely adopted only recently made open source, better open source implementationsavailableSupport for boosting (see next course)56

A few final insightsBinary splitsRemember the continuous splits: binary split (x split yes / no)Couldn't we do the same for categorical values?E.g. humity high yes/no?We can, and most (good) implementations indeed do so (Weka is a weird exception). This infact also prevents a bias issue in the information gain measure: by default, it is biased to prefersplits leading to more subsetsThis can make the tree deeper, but this is not a big issueNote that we can now encounter the same attribute multiple times in the "path" through a treetowards a leaf nodeConditional inference trees provide another method to avoid this bias by using a significancetest procedure in order to select variables instead of selecting the variable that maximizes aninformation measureSome implementations have proposed three-way splits (yes / no / NA) but not manyThis means that you will have to treat missing valuesHowever, trees are surprisingly robust to other issues, such as outliers57

A few final insightsRemember to prevent overfitting treesBut a deep tree does not necessarily mean that you have a problemAnd a short tree does not necessarily mean that it's not overfittingHowever, note that it is now very likely that your leaf nodes will not becompletely pure (i.e. not containing 100% yes cases or no cases)How to assign an outcome?Easy, take the majority classWe can even provide a notion of probability, e.g. if we saw "yes" 8 times in a leaf node, and"no" 2 times, then p(yes x leading to that leaf node) 80%However, this is not a well-calibrated probability like logistic regression would provideThis doesn't matter in most cases (e.g. if you're only planning to rank instances), but in some, itdoes58

A few final insightsDecision trees are also "sensitive to changes the training data"Meaning that small changes in the training data can cause your tree to look different (order offeatures, splits used)Related the how the splitting is done and information gain calculatedBut this is not that big of an issueTogether with logistic regression, decision trees are in the top-3 of predictivetechniques on tabular data. They're simple to understand and present, andrequire very little data preparation, and can learn non-linear relationshipsIn fact, many ways exist to take your favority implementation and extending itE.g. when domain experts have their favorite set of features, you can easily constrain the tree toonly consider a subset of the features in the first n levelsYou might even consider playing with more candidates to generate binary split rules, e.g."feature X between A and B?", "euclidean dist(X, Y) t", .59

Regression treesAs made popular by CART: Classification AndRegression Trees“Tree structured regression offers an interestingalternative for looking at regression type problems. Ithas sometimes given clues to data structure notapparent from a linear regression analysis”Instead of calculating the #yes’s vs. #no’s to get thepredicted class label, take the mean of the continuouslabel and use that as the outcomeBut how to select the splitting criterion?Squared residuals minimization algorithm which implies that expected sum of variances for tworesulting nodes should be minimizedBased on sum of squared errors (again): find the split that produces the greatest separation inSSE in each subset (ANOVA analysis)Find nodes with minimal within variance and therefore greatest between variance (a little bitlike k-means, a clustering technique we'll visit later)Important: comments regarding pruning still apply60

Decision trees versus logistic regressionDecision boundary of decision trees: squares orthogonal to a dimension61

Decision trees versus logistic regressionDecision trees can struggle to capture linear relationshipsE.g. the best it can do is a step function approximation of a linear relationshipThis is strictly related to how decision trees work: it splits the input features in several“orthogonal” regions and assigns a prediction value to each regionHere, a deeper tree would be necessary to approximate the linear relationshipOr apply a transformation first (e.g. PCA)62

K-nearest neighbors63

K-nearest neighbors (K-NN)A non-parametric method used for classification and regression"The data is the model"Trivially easy64

K-nearest neighbors (K-NN)Has some appealing properties: easy to understandFun to tweak with custom distances, different values for k, dynamic k-values -- even arecommender system can be built using this approachProvides surprisingly good results, given enough dataRegression: e.g. use a weighted average of the k nearest neighbors, weighted by the inverse oftheir distanceThe main disadvantage of k-NN is that it is a lazy learner: it does not learn anything from thetraining data and simply uses the training data itself as a modelThis means you don't get a formula, or a tree as a summarizing modelAnd that you need to keep training data aroundRelatively slowNot as stable for noisy data, might be hard to generalize, unstable with regards to k setting65

K-nearest neighbors 8f0dea66

Wrap upLinear regression, logistic regression and decision trees still amongst most widely usedtechniquesK-NN less widely used but can provide a quick baselineWhite box, statistical rigor, easy to construct and interpretDecision between regression and (which) classification not always a clear cut choice!Neither is the decision between unsupervised and supervisedIteration, domain expert involvement required67

Advanced Analytics in Business [D0S07a] Big Data Platforms & Technologies [D0S06a] Supervised Learning. Overview Regression Logistic regression K-NN Decision and regression trees 2. . Predict the future based on patterns learnt from past data Classification (categorical) versus regression (continuous) You have a labelled data set at your disposal