ClassBasic数据挖掘.ppt

Example of the Over-fitting Problem in Decision Tree Construction 11 “Yes” and 9 “No” samples;prediction = “Yes” 8 “Yes” and 9 “No” samples;prediction = “No” 3 “Yes” and 0 “No” samples;prediction = “Yes” Ai=0 Ai=1 Example of Post-Pruning Class = Yes 20 Class = No 10 Error = 10/30 Training Error (Before splitting) = 10/30 Pessimistic error = (10 + 0.5)/30 = 10.5/30 Training Error (After splitting) = 9/30 Pessimistic error (After splitting) = (9 + 4 ? 0.5)/30 = 11/30 PRUNE! Class = Yes 8 Class = No 4 Class = Yes 3 Class = No 4 Class = Yes 4 Class = No 1 Class = Yes 5 Class = No 1 * the upper bound of the confidence interval of the error rate Since the pessimistic error rate increases with the split, we do not want to keep the children. This practice is called “tree pruning”. * Enhancements to Basic Decision Tree Induction Allow for continuous-valued attributes Dynamically define new discrete-valued attributes that partition the continuous attribute value into a discrete set of intervals Handle missing attribute values Assign the most common value of the attribute Assign probability to each of the possible values Attribute construction Create new attributes based on existing ones that are sparsely represented This reduces fragmentation, repetition, and replication Road Map * Basic concepts Decision tree induction Evaluation of classifiers Rule induction Classification using association rules Na?ve Bayesian classification Na?ve Bayes for text classification Support vector machines K-nearest neighbor Ensemble methods: Bagging and Boosting Summary Evaluating classification methods Predictive accuracy Efficiency time to construct the model time to use the model Robustness: handling noise and missing values Scalability: efficiency in disk-resident databases Interpretability: understandable and insight provided by the model Compactness of the model: size of the tree, or the number of rules. * Evaluation methods * Holdout set: The available data set D is divided