Statistical, distance-based and decision-tree classifiers, each worked on the buys_computer data.
The worked examples in this chapter use the classic buys_computer training set, which appears in many data mining textbooks. It has 14 records and four attributes, namely age, income, student and credit rating, and its class label shows whether the person buys a computer. Nine of the records are labelled "yes" and five are labelled "no". The full data set is given below, so that every count used in this chapter can be checked against it.
| RID | Age | Income | Student | Credit rating | Buys computer |
|---|---|---|---|---|---|
| 1 | youth | high | no | fair | no |
| 2 | youth | high | no | excellent | no |
| 3 | middle-aged | high | no | fair | yes |
| 4 | senior | medium | no | fair | yes |
| 5 | senior | low | yes | fair | yes |
| 6 | senior | low | yes | excellent | no |
| 7 | middle-aged | low | yes | excellent | yes |
| 8 | youth | medium | no | fair | no |
| 9 | youth | low | yes | fair | yes |
| 10 | senior | medium | yes | fair | yes |
| 11 | youth | medium | yes | excellent | yes |
| 12 | middle-aged | medium | no | excellent | yes |
| 13 | middle-aged | high | yes | fair | yes |
| 14 | senior | medium | no | excellent | no |
11.1 Statistical-based algorithms
Regression. Regression fits an equation of the form y = c0 + c1x1 + … + cnxn to the data, and then uses the equation either to predict a value or to separate classes.
ExampleFor a set of houses, the price in lakhs of rupees is found to be 10 + 0.05 × the area in square feet. A house of 1,200 square feet is therefore predicted to cost 10 + 60 = ₹70 lakh.
ExplanationRegression predicts numbers. When a cut-off is added, such as "a price above ₹50 lakh means premium", the same equation can also classify houses.
Naïve Bayes. A naïve Bayes classifier chooses the class with the highest posterior probability. It assumes that the attributes are independent of each other once the class is known, which lets the probability be calculated as the product shown below.
ExampleA new record X has age = youth, income = medium, student = yes and credit rating = fair, and it must be classified. Each conditional probability is counted from the data set above. For example, of the 9 "yes" records, 2 are youths (records 9 and 11), so P(age = youth | yes) = 2/9; of the 5 "no" records, 3 are youths (records 1, 2 and 8), so P(age = youth | no) = 3/5. The table below works through the full calculation for both classes.
| Term | Class "yes" | Class "no" |
|---|---|---|
| Prior P(C) | 9/14 = 0.643 | 5/14 = 0.357 |
| P(age = youth | C) | 2/9 = 0.222 | 3/5 = 0.600 |
| P(income = medium | C) | 4/9 = 0.444 | 2/5 = 0.400 |
| P(student = yes | C) | 6/9 = 0.667 | 1/5 = 0.200 |
| P(credit = fair | C) | 6/9 = 0.667 | 2/5 = 0.400 |
| P(X | C) | 0.044 | 0.019 |
| P(X | C) × P(C) | 0.028 | 0.007 |
The row P(X | C) is the product of the four conditional probabilities above it. For "yes", it is 0.222 × 0.444 × 0.667 × 0.667 = 0.044, and for "no", it is 0.600 × 0.400 × 0.200 × 0.400 = 0.019. Multiplying by the priors gives 0.044 × 0.643 = 0.028 for "yes" and 0.019 × 0.357 = 0.007 for "no".
ExplanationBecause 0.028 is greater than 0.007, the record X is classified as "buys computer = yes". Each conditional probability is simply a ratio of counts from the training data, which makes naïve Bayes very fast. The independence assumption is rarely exactly true, but the method still works well in practice.
11.2 Distance-based algorithms
Distance-based algorithms classify a record according to how close it is to records whose class is already known. In the simple approach, the record is assigned to the class whose centre is nearest to it. In the k-nearest neighbours (KNN) method, the k training records closest to the new record are found, and the record is given the class that most of them share.
ExampleA new customer has a normalised age of 0.40 and a normalised income of 0.60. The table below shows five past customers, their class, and the Euclidean distance from each of them to the new customer.
| Neighbour | Age | Income | Class | Distance to (0.40, 0.60) |
|---|---|---|---|---|
| A | 0.45 | 0.52 | Buys | √(0.05² + 0.08²) = √0.0089 = 0.094 |
| B | 0.30 | 0.70 | Does not buy | √(0.10² + 0.10²) = √0.0200 = 0.141 |
| C | 0.55 | 0.75 | Buys | √(0.15² + 0.15²) = √0.0450 = 0.212 |
| D | 0.10 | 0.40 | Does not buy | √(0.30² + 0.20²) = √0.1300 = 0.361 |
| E | 0.80 | 0.20 | Does not buy | √(0.40² + 0.40²) = √0.3200 = 0.566 |
ExplanationWith k = 3, the three nearest neighbours are A, B and C, and the vote is two "buys" against one "does not buy", so the new customer is classified as a buyer. With k = 5, the vote becomes two against three, so the answer changes to "does not buy". KNN builds no model in advance, which is why it is called a lazy learner, and both the choice of k and the way distances are scaled can change its answer.
11.3 Decision tree-based algorithms
A decision tree classifies a record by asking a series of questions about its attributes, starting at the root and following the branches until it reaches a leaf that gives the class.
The tree in the figure tests age first. Young people are then split by whether they are students, and older people are split by their credit rating.
ID3, one of the best-known tree algorithms, chooses the attribute at each node using entropy and information gain, which are defined by the two formulas below.
ExampleFor the whole training set of 9 "yes" and 5 "no" records, Entropy(S) = −(9/14) log₂(9/14) − (5/14) log₂(5/14) = 0.410 + 0.530 = 0.940. The table below counts the classes for each value of each attribute, finds the entropy of each group, and works out the gain.
| Attribute | Value | Yes | No | Entropy of group | Weighted entropy | Gain |
|---|---|---|---|---|---|---|
| Age | youth | 2 | 3 | 0.971 | (5/14) × 0.971 = 0.347 | |
| middle-aged | 4 | 0 | 0 | (4/14) × 0 = 0 | ||
| senior | 3 | 2 | 0.971 | (5/14) × 0.971 = 0.347 | 0.940 − 0.694 = 0.246 | |
| Income | high | 2 | 2 | 1.000 | (4/14) × 1.000 = 0.286 | |
| medium | 4 | 2 | 0.918 | (6/14) × 0.918 = 0.394 | ||
| low | 3 | 1 | 0.811 | (4/14) × 0.811 = 0.232 | 0.940 − 0.911 = 0.029 | |
| Student | yes | 6 | 1 | 0.592 | (7/14) × 0.592 = 0.296 | |
| no | 3 | 4 | 0.985 | (7/14) × 0.985 = 0.493 | 0.940 − 0.788 = 0.152 | |
| Credit rating | fair | 6 | 2 | 0.811 | (8/14) × 0.811 = 0.464 | |
| excellent | 3 | 3 | 1.000 | (6/14) × 1.000 = 0.429 | 0.940 − 0.892 = 0.048 |
For example, the youth group has 2 "yes" and 3 "no" records, so its entropy is −(2/5) log₂(2/5) − (3/5) log₂(3/5) = 0.529 + 0.442 = 0.971. The totals 0.911, 0.788 and 0.892 are found by adding the unrounded weighted entropies, so adding the rounded figures in the table can differ by 0.001. Some textbooks print 0.151 for student because they round at an earlier step; the exact value is 0.152.
ExplanationAge gives the largest information gain, 0.246, so it becomes the root of the tree. All the middle-aged records belong to the class "yes", so that branch ends immediately in a pure leaf. The algorithm then repeats the same calculation on the youth subset and on the senior subset. In the youth subset (records 1, 2, 8, 9 and 11), the three non-students all have "no" and the two students both have "yes", so splitting on student gives two pure leaves. In the senior subset (records 4, 5, 6, 10 and 14), the three records with a fair credit rating all have "yes" and the two with an excellent rating both have "no", so splitting on credit rating gives two pure leaves. Income never gives the best split at any node, so it does not appear in the tree at all.
CART uses the Gini index instead of entropy. For the whole training set, Gini(S) = 1 − (9/14)² − (5/14)² = 1 − 0.413 − 0.128 = 0.459, and CART chooses the binary split that reduces this value the most.
Several decision tree algorithms are in common use, and they differ mainly in how they measure the quality of a split. The table below compares them.
| Algorithm | Split measure | Tree shape | Notes |
|---|---|---|---|
| ID3 | Information gain | Multi-way | Handles categorical attributes only and favours attributes with many values |
| C4.5 | Gain ratio | Multi-way | Handles numeric and missing values, and prunes the tree |
| CART | Gini index | Binary | Builds both classification and regression trees |
| SLIQ and SPRINT | Gini index | Binary | Scale to data sets that are too large for memory |
Pruning. Pruning removes branches that fit noise in the training data rather than a real pattern.
ExampleOne branch of a tree reads "youth, student, credit excellent and income low leads to no", but it is supported by only one training record. Post-pruning replaces this branch with the majority class of its parent node.
ExplanationA smaller tree classifies unseen data more accurately, because it is less overfitted to the training data. Pre-pruning stops the tree from growing early by using a threshold, while post-pruning first grows the full tree and then cuts it back.
Exam points
- Naïve Bayes assumes attributes are independent given the class and picks the class with the highest P(X | C) × P(C).
- KNN is a lazy learner: it builds no model and votes among the k nearest training records.
- ID3 splits on information gain, C4.5 on gain ratio, and CART on the Gini index with binary splits.
- The attribute with the highest information gain becomes the root of the tree.
- For the buys_computer data, Entropy(S) = 0.940 and age has the highest gain (0.246).
- Pruning removes branches that fit noise, reducing overfitting.
Independent study notes for learning purposes. Not affiliated with or endorsed by any university, publisher or course provider. Product and company names are trademarks of their respective owners.