DM7 Classification C4DM7分类C KDnuggets.pptVIP

Machine Learning in Real World:C4.5 Outline Handling Numeric Attributes Finding Best Split(s) Dealing with Missing Values Pruning Pre-pruning, Post-pruning, Error Estimates From Trees to Rules Industrial-strength algorithms For an algorithm to be useful in a wide range of real-world applications it must: Permit numeric attributes Allow missing values Be robust in the presence of noise Be able to approximate arbitrary concept descriptions (at least in principle) Basic schemes need to be extended to fulfill these requirements C4.5 History ID3, CHAID – 1960s C4.5 innovations (Quinlan): permit numeric attributes deal sensibly with missing values pruning to deal with for noisy data C4.5 - one of best-known and most widely-used learning algorithms Last research version: C4.8, implemented in Weka as J4.8 (Java) Commercial successor: C5.0 (available from Rulequest) Numeric attributes Standard method: binary splits E.g. temp 45 Unlike nominal attributes,every attribute has many possible split points Solution is straightforward extension: Evaluate info gain (or other measure)for every possible split point of attribute Choose “best” split point Info gain for best split point is info gain for attribute Computationally more demanding Weather data – nominal values Weather data - numeric Example Split on temperature attribute: E.g. temperature ? 71.5: yes/4, no/2 temperature ? 71.5: yes/5, no/3 Info([4,2],[5,3])= 6/14 info([4,2]) + 8/14 info([5,3]) = 0.939 bits Place split points halfway between values Can evaluate all split points in one pass! Avoid repeated sorting! Sort instances by the values of the numeric attribute Time complexity for sorting: O (n log n) Q. Does this have to be repeated at each node of the tree? A: No! Sort order for children can be derived from sort order for parent Time complexity of derivation: O (n) Drawback: need to create and store an array of sorted indices for each numeric attribute More speeding up Entropy only needs to be evaluated