Pruning is carried out from the leaves to the root. Instead of E/N, C4.5 determines the upper limit of the binomial probability when E events have been observed in N trials, using a user-specified confidence whose default value is 0.25. The pruning algorithm is based on a pessimistic estimate of the error rate associated with a set of N cases, E of which do not belong to the most frequent class. The initial tree is then pruned to avoid overfitting. An attribute A with discrete values has by default one outcome for each value, but an option allows the values to be grouped into two or more subsets with one outcome for each subset. C4.5 uses two heuristic criteria to rank possible tests: information gain, which minimizes the total entropy of the subsets where the threshold h is found by sorting S on the values of A and choosing the split between successive values that maximizes the criterion above. There are usually many tests that could be chosen in this last step. according to the outcome for each case, and apply the same procedure recursively to each subset. Make this test the root of the tree with one branch for each outcome of the test, partition S into corresponding subsets S 1, S 2. Otherwise, choose a test based on a single attribute with two or more outcomes.If all the cases in S belong to the same class or S is small, the tree is a leaf labeled with the most frequent class in S.Given a set S of cases, C4.5 first grows an initial tree using the divide-and-conquer algorithm as follows: We will outline the algorithms employed in C4.5, highlight some changes in its successor See5/C5.0, and conclude with a couple of open research issues. Like CLS and ID3, C4.5 generates classifiers expressed as decision trees, but it can also construct classifiers in more comprehensible ruleset form. Such systems take as input a collection of cases, each belonging to one of a small number of classes and described by its values for a fixed set of attributes, and output a classifier that can accurately predict the class to which a new case belongs. Systems that construct classifiers are one of the commonly used tools in data mining. We also advised that each nominated algorithm should have been widely cited and used by other researchers in the field, and the nominations from each nominator as a group should have a reasonable representation of the different areas in data mining. We asked each nomination to provide the following information: (a) the algorithm name, (b) a brief justification, and (c) a representative publication reference.
All except one in this distinguished set of award winners responded to our invitation. In an effort to identify some of the most influential algorithms that have been widely used in the data mining community, the IEEE International Conference on Data Mining (ICDM, ) identified the top 10 algorithms in data mining for presentation at ICDM '06 in Hong Kong.Īs the first step in the identification process, in September 2006 we invited the ACM KDD Innovation Award and IEEE ICDM Research Contributions Award winners to each nominate up to 10 best-known algorithms in data mining.
0 kommentar(er)
