大数据数据挖掘培训讲义7-回归和knn算法.ppt

Classification Algorithms – Continued Outline Rules Linear Models (Regression) Instance-based (Nearest-neighbor) Generating Rules Decision tree can be converted into a rule set Straightforward conversion: each path to the leaf becomes a rule – makes an overly complex rule set More effective conversions are not trivial (e.g. C4.8 tests each node in root-leaf path to see if it can be eliminated without loss in accuracy) Covering algorithms Strategy for generating a rule set directly: for each class in turn find rule set that covers all instances in it (excluding instances not in the class) This approach is called a covering approach because at each stage a rule is identified that covers some of the instances Example: generating a rule Example: generating a rule, II Example: generating a rule, III Example: generating a rule, IV Possible rule set for class “b”: More rules could be added for “perfect” rule set Rules vs. trees Corresponding decision tree: (produces exactly the same predictions) But: rule sets can be more clear when decision trees suffer from replicated subtrees Also: in multi-class situations, covering algorithm concentrates on one class at a time whereas decision tree learner takes all classes into account A simple covering algorithm Generates a rule by adding tests that maximize rule’s accuracy Similar to situation in decision trees: problem of selecting an attribute to split on But: decision tree inducer maximizes overall purity Each new test reduces rule’s coverage: Selecting a test Goal: maximize accuracy t total number of instances covered by rule p positive examples of the class covered by rule t – p number of errors made by rule Select test that maximizes the ratio p/t We are finished when p/t = 1 or the set of instances can’t be split any further Example: contact lens data, 1 Rule we seek: Possible tests: Example: contact lens data, 2 Rule we seek: Possible tests: Modified rule and resulting data Rule with best test added: Instances