Silberschatz Korth Sudarshan: Database System Concepts, Fourth Edition in Software

Drawer USS Code 128 in Software Silberschatz Korth Sudarshan: Database System Concepts, Fourth Edition

The McGraw Hill Companies, 2001

22

respectively As an optimization, since the class for the range 25,000 to 50,000 and the range 50,000 to 75,000 is the same under the node degree = masters, the two ranges have been merged into a single range 25,000 to 75,000 Best Splits Intuitively, by choosing a sequence of partitioning attributes, we start with the set of all training instances, which is impure in the sense that it contains instances from many classes, and end up with leaves which are pure in the sense that at each leaf all training instances belong to only one class We shall see shortly how to measure purity quantitatively To judge the bene t of picking a particular attribute and condition for partitioning of the data at a node, we measure the purity of the data at the children resulting from partitioning by that attribute The attribute and condition that result in the maximum purity are chosen The purity of a set S of training instances can be measured quantitatively in several ways Suppose there are k classes, and of the instances in S the fraction of instances in class i is pi One measure of purity, the Gini measure is de ned as

Gini(S) = 1

When all instances are in a single class, the Gini value is 0, while it reaches its maximum (of 1 1/k) if each class has the same number of instances Another measure of purity is the entropy measure, which is de ned as

Entropy(S) =

The entropy value is 0 if all instances are in a single class, and reaches its maximum when each class has the same number of instances The entropy measure derives from information theory When a set S is split into multiple sets Si , i = 1, 2, , r, we can measure the purity of the resultant set of sets as:

Purity(S1 , S2 , , Sr ) =

That is, the purity is the weighted average of the purity of the sets Si The above formula can be used with both the Gini measure and the entropy measure of purity The information gain due to a particular split of S into Si , i = 1, 2, , r is then Information-gain(S, {S1 , S2 , , Sr }) = purity(S) purity(S1 , S2 , , Sr ) Splits into fewer sets are preferable to splits into many sets, since they lead to simpler and more meaningful decision trees The number of elements in each of the sets Si may also be taken into account; otherwise, whether a set Si has 0 elements or 1 element would make a big difference in the number of sets, although the split is the same for almost all the elements The information content of a particular split can be

The McGraw Hill Companies, 2001

Information-content(S, {S1 , S2 , , Sr })) =

All of this leads to a de nition: The best split for an attribute is the one that gives the maximum information gain ratio, de ned as Information-gain(S, {S1 , S2 , , Sr }) Information-content(S, {S1 , S2 , , Sr }) Finding Best Splits How do we nd the best split for an attribute How to split an attribute depends on the type of the attribute Attributes can be either continuous valued, that is, the values can be ordered in a fashion meaningful to classi cation, such as age or income, or can be categorical, that is, they have no meaningful order, such as department names or country names We do not expect the sort order of department names or country names to have any signi cance to classi cation Usually attributes that are numbers (integers/reals) are treated as continuous valued while character string attributes are treated as categorical, but this may be controlled by the user of the system In our example, we have treated the attribute degree as categorical, and the attribute income as continuous valued We rst consider how to nd best splits for continuous-valued attributes For simplicity, we shall only consider binary splits of continuous-valued attributes, that is, splits that result in two children The case of multiway splits is more complicated; see the bibliographical notes for references on the subject To nd the best binary split of a continuous-valued attribute, we rst sort the attribute values in the training instances We then compute the information gain obtained by splitting at each value For example, if the training instances have values 1, 10, 15, and 25 for an attribute, the split points considered are 1, 10, and 15; in each case values less than or equal to the split point form one partition and the rest of the values form the other partition The best binary split for the attribute is the split that gives the maximum information gain For a categorical attribute, we can have a multiway split, with a child for each value of the attribute This works ne for categorical attributes with only a few distinct values, such as degree or gender However, if the attribute has many distinct values, such as department names in a large company, creating a child for each value is not a good idea In such cases, we would try to combine multiple values into each child, to create a smaller number of children See the bibliographical notes for references on how to do so Decision-Tree Construction Algorithm The main idea of decision tree construction is to evaluate different attributes and different partitioning conditions, and pick the attribute and partitioning condition that results in the maximum information gain ratio The same procedure works recur-