大数据数据挖掘培训讲义5：分类算法基础.ppt

witten eibe Algorithms for Classification: The Basic Methods Outline Simplicity first: 1R Na?ve Bayes Classification Task: Given a set of pre-classified examples, build a model or classifier to classify new cases. Supervised learning: classes are known for the examples used to build the classifier. A classifier can be a set of rules, a decision tree, a neural network, etc. Typical applications: credit approval, direct marketing, fraud detection, medical diagnosis, ….. Simplicity first Simple algorithms often work very well! There are many kinds of simple structure, eg: One attribute does all the work All attributes contribute equally independently A weighted linear combination might do Instance-based: use a few prototypes Use simple logical rules Success of method depends on the domain Inferring rudimentary rules 1R: learns a 1-level decision tree I.e., rules that all test one particular attribute Basic version One branch for each value Each branch assigns most frequent class Error rate: proportion of instances that don’t belong to the majority class of their corresponding branch Choose attribute with lowest error rate (assumes nominal attributes) Pseudo-code for 1R Note: “missing” is treated as a separate attribute value Evaluating the weather attributes * indicates a tie Dealing withnumeric attributes Discretize numeric attributes Divide each attribute’s range into intervals Sort instances according to attribute’s values Place breakpoints where the class changes(the majority class) This minimizes the total error Example: temperature from weather data The problem of overfitting This procedure is very sensitive to noise One instance with an incorrect class label will probably produce a separate interval Also: time stamp attribute will have zero errors Simple solution:enforce minimum number of instances in majority class per interval Discretization example Example (with min = 3): Final result for temperature attribute With overfitting avoidance Resulti