CSE255 THURSDAY JANUARY 15, 1998 ADMINISTRATION Prof. Gary Cottrell will lecture in this room, Center Hall 206, on neural networks next week. NOTES ON WRITING There are at least four separate mistakes in the sentence below. "To be sure, no large set of data can be thought of being pristine." It is very wearing to teach good writing. You should have learned this in high school. If you didn't, you must learn it now. Take a community college course. Formatting: make your entire report one document. Minimize the use of appendices. Always put a date and contact info on any report you write. You never know who will see a copy. COST MATRICES FOR THE GERMAN CREDIT DATA The published matrix is: predicted (1 = Good, 2 = Bad) 1 2 ---------------------------- 1 0 1 actual ----------------------- 2 5 0 Note these are costs, not profits. It is is not economically meaningful to have different costs in column 2. A more sensible matrix with cash flows is: predicted (1 = Good, 2 = Bad) 1 2 ---------------------------- 1 1 0 actual ----------------------- 2 -5 0 MEASURING ACCURACY: CROSS-VALIDATION We can always construct a decision tree that will replicate perfectly the classification of the training examples. So how should we measure the accuracy of a tree? To measure accuracy, we should use a "holdout" set of training data and measure accuracy on that. But the natural inclination is to use all the data possible for training. Compromise: cross-validation. Definition: The k-fold cv error rate of an algorithm on a set is computed as follows: divide the data set randomly into k equal subsets for each subset Si, let Ti be the whole dataset minus Si let ei be the error rate on Si of the concept learned from Ti the cv error rate is the average of the ei The most common value of k is 10. Sometimes k = the size of the whole dataset, so each training set is as large as possible subject to the constraint that testing must be on an independent sample. Cross-validation is widely used, but not well-understood. Theory and practice lead to two main conclusions: cv is unbiased: on average it does not under- or over-estimate error cv has high variance: it is not a precise estimator. ACCURACY ESTIMATES Accuracy estimates should be reported with error bars. MineSet will give these. Fluctuations in a learning curve should be statistically insignificant, i.e. inside the error bars. Remember the concepts behind statistical quality control. Even small improvements over the base rate can be remarkable and useful, e.g. 47% accuracy in predicting voting behavior compared to a 34% base rate. CORRELATION VERSUS CAUSATION Most algorithms detect correlations, not causal relationships. For example, one team found that number of acres of cotton planted in an Alabama county is predictive of the yield per acre in that county. General knowledge suggests that the causal relationship is from yield to acreage planted, not the other way round. It is important to think about whether you are trying to discover zero-order, first-order, second-order etc. effects. A zero-order effect is a principal influence. A first-order effect is a secondary influence that gives changes in the main effect. A second-order effect modulates a first-order effect, etc. For example the best predictor of this year's cotton yield may be last year's yield, or a historical average yield. This year's rain and sun may only predict year to year differences in yield. GENERAL COMMENTS ON THE DATA MINING PROJECT REPORTS Two teams last year used data from Germany. Both had trouble with erroneous translations from German into English. For example "Komfort" in German means the level of luxury of a hotel. Difficulty with German is similar to difficulty with specialized vocabulary. In real data mining and knowledge engineering projects, you cannot assume that words used by people in the domain automatically mean what you think they do. Data preprocessing requires careful thought. For example, in predicting whether a country is involved in a war, probably 15 different types of government should be reduced to fewer. Otherwise the learning algorithm cannot reasonably know which types are more similar to each other. DECISION TREES Let's specialize to a relatively easy but non-trivial case: each example is a finite feature vector a concept is a decision tree where nodes are features For example the features (also called attributes) might be outlook sunny, overcast, rain temperature cool, mild, hot humidity high, normal windy true, false A particular example in the training set might be : positive LEARNING DECISION TREES Question: Why bother with decision trees? Why not just use decision tables? Intuitively, there is no learning involved in creating a decision table from examples. More concretely, no generalization happens. The only lines that are filled in are those that correspond exactly to given examples. This is called "rote learning". From another, point of view, all decision tables are equally excessively large. Generalization, i.e. induction, means having a small concept that classifies many examples. THE IDEA OF THE ID3 ALGORITHM ID3 is top down and recursive. First the algorithm chooses a root feature. Then recursively it finds a decision tree for each alternative value of the feature. Let C be an arbitrary training set. If every member of C is positive (negative), return the tree which is just the leaf positive (negative). Otherwise, let T be some feature with values O1 through Ow. T generates a partition of C into subsets C1 through Cw. Clearly we can recursively call the algorithm to generate decision trees separately for C1 through Cw. The recursion will terminate provided that at least two of the subsets generated are non-empty, i.e. provided that the chosen feature T does not always have the same value. WE WANT SIMPLE TREES, I.E. *SMALL* TREES Decision trees can be small: the path from the root to a leaf may ignore many features. Occam's razor (William of Occam, 1285-?1349) suggests that a simple explanation is more likely to be true. We'll return to this question. For now, we'll accept that the objective is to find a small decision tree that correctly generalizes the training data. In fact all we can require is that the tree be correct on the training data.