Tree Growing Algorithms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

import numpy as np
from typing import Union, List
 
def entropy(probs: Union[np.ndarray, List[float]]) -> float:
    """
    Compute entropy of a probability distribution.
    
    Parameters:
        probs: Array of probabilities (must sum to 1)
        
    Returns:
        Entropy in bits (log base 2)
    """
    probs = np.asarray(probs)
    
    # Filter out zero probabilities to avoid log(0)
    probs = probs[probs > 0]
    
    return -np.sum(probs * np.log2(probs))
 
def entropy_from_counts(counts: Union[np.ndarray, List[int]]) -> float:
    """
    Compute entropy from class counts.
    
    Parameters:
        counts: Array of counts for each class
        
    Returns:
        Entropy in bits
    """
    counts = np.asarray(counts)
    total = np.sum(counts)
    
    if total == 0:
        return 0.0
    
    probs = counts / total
    return entropy(probs)
 
# Demonstrate entropy behavior
print("Entropy Examples (Binary Classification)")
print("=" * 50)
print(f"{'Distribution':<25} | {'Entropy (bits)':<15}")
print("-" * 50)
 
distributions = [
    ([1.0, 0.0], "Certain (1.0, 0.0)"),
    ([0.9, 0.1], "Skewed (0.9, 0.1)"),
    ([0.7, 0.3], "Moderate (0.7, 0.3)"),
    ([0.5, 0.5], "Maximum (0.5, 0.5)"),
]
 
for probs, name in distributions:
    h = entropy(probs)
    print(f"{name:<25} | {h:<15.4f}")
 
print("
Key insight: Maximum entropy occurs at uniform distribution")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

import numpy as np
from collections import Counter
from typing import List, Tuple
 
def information_gain(y: np.ndarray, x: np.ndarray) -> float:
    """
    Compute information gain of splitting y by attribute x.
    
    Parameters:
        y: Class labels (n_samples,)
        x: Attribute values (n_samples,)
        
    Returns:
        Information gain in bits
    """
    n = len(y)
    
    # Compute parent entropy H(Y)
    parent_counts = np.array(list(Counter(y).values()))
    parent_entropy = entropy_from_counts(parent_counts)
    
    # Compute conditional entropy H(Y|X)
    conditional_entropy = 0.0
    unique_values = np.unique(x)
    
    for value in unique_values:
        # Subset where X = value
        mask = (x == value)
        subset_y = y[mask]
        
        # Weight by proportion of instances
        weight = np.sum(mask) / n
        
        # Entropy of this subset
        subset_counts = np.array(list(Counter(subset_y).values()))
        subset_entropy = entropy_from_counts(subset_counts)
        
        conditional_entropy += weight * subset_entropy
    
    # Information gain = parent entropy - conditional entropy
    return parent_entropy - conditional_entropy
 
# Classic "Play Tennis" example from Quinlan's papers
# Attributes: Outlook, Temperature, Humidity, Wind
# Class: PlayTennis (Yes/No)
 
outlook = np.array(['Sunny', 'Sunny', 'Overcast', 'Rain', 'Rain', 'Rain', 
                    'Overcast', 'Sunny', 'Sunny', 'Rain', 'Sunny', 
                    'Overcast', 'Overcast', 'Rain'])
temperature = np.array(['Hot', 'Hot', 'Hot', 'Mild', 'Cool', 'Cool', 
                        'Cool', 'Mild', 'Cool', 'Mild', 'Mild', 
                        'Mild', 'Hot', 'Mild'])
humidity = np.array(['High', 'High', 'High', 'High', 'Normal', 'Normal',
                     'Normal', 'High', 'Normal', 'Normal', 'Normal',
                     'High', 'Normal', 'High'])
wind = np.array(['Weak', 'Strong', 'Weak', 'Weak', 'Weak', 'Strong',
                 'Strong', 'Weak', 'Weak', 'Weak', 'Strong', 'Strong',
                 'Weak', 'Strong'])
play_tennis = np.array(['No', 'No', 'Yes', 'Yes', 'Yes', 'No', 'Yes',
                        'No', 'Yes', 'Yes', 'Yes', 'Yes', 'Yes', 'No'])
 
print("Information Gain Analysis: Play Tennis Dataset")
print("=" * 55)
 
# Parent entropy
parent_counts = np.array([9, 5])  # 9 Yes, 5 No
parent_h = entropy_from_counts(parent_counts)
print(f"Parent entropy H(PlayTennis): {parent_h:.4f} bits")
print()
 
# Information gain for each attribute
attributes = {
    'Outlook': outlook,
    'Temperature': temperature,
    'Humidity': humidity,
    'Wind': wind
}
 
print(f"{'Attribute':<15} | {'Information Gain':<18} | {'Rank'}")
print("-" * 55)
 
gains = {}
for name, values in attributes.items():
    ig = information_gain(play_tennis, values)
    gains[name] = ig
 
# Sort by gain
sorted_attrs = sorted(gains.items(), key=lambda x: x[1], reverse=True)
for rank, (name, ig) in enumerate(sorted_attrs, 1):
    print(f"{name:<15} | {ig:<18.4f} | {rank}")
 
print()
print(f"Best split attribute: {sorted_attrs[0][0]}")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

"""
ID3 Algorithm: Complete Implementation
 
This implementation follows Quinlan's original specification with
detailed comments explaining each decision point.
"""
 
import numpy as np
from collections import Counter
from typing import Dict, List, Any, Optional, Union
from dataclasses import dataclass
 
@dataclass
class TreeNode:
    """Represents a node in the decision tree."""
    is_leaf: bool = False
    prediction: Optional[str] = None  # For leaf nodes
    attribute: Optional[str] = None   # For internal nodes
    children: Optional[Dict[str, 'TreeNode']] = None  # Branches
    
    def __repr__(self):
        if self.is_leaf:
            return f"Leaf({self.prediction})"
        return f"Node({self.attribute})"
 
class ID3Classifier:
    """
    ID3 Decision Tree Classifier.
    
    Implements the classic ID3 algorithm with information gain
    (entropy reduction) as the splitting criterion.
    
    Limitations (by design, matching original ID3):
    - Categorical attributes only
    - No pruning
    - No handling of missing values
    - No continuous attributes
    """
    
    def __init__(self):
        self.root: Optional[TreeNode] = None
        self.attributes: List[str] = []
        
    def _entropy(self, y: np.ndarray) -> float:
        """Compute entropy of label distribution."""
        if len(y) == 0:
            return 0.0
        counts = np.array(list(Counter(y).values()))
        probs = counts / len(y)
        probs = probs[probs > 0]
        return -np.sum(probs * np.log2(probs))
    
    def _information_gain(self, X: np.ndarray, y: np.ndarray, 
                          attribute_idx: int) -> float:
        """Compute information gain for splitting on attribute."""
        parent_entropy = self._entropy(y)
        
        # Get unique values for this attribute
        values = np.unique(X[:, attribute_idx])
        
        # Compute weighted child entropy
        child_entropy = 0.0
        for value in values:
            mask = X[:, attribute_idx] == value
            weight = np.sum(mask) / len(y)
            child_entropy += weight * self._entropy(y[mask])
        
        return parent_entropy - child_entropy
    
    def _majority_class(self, y: np.ndarray) -> str:
        """Return the most common class label."""
        counter = Counter(y)
        return counter.most_common(1)[0][0]
    
    def _build_tree(self, X: np.ndarray, y: np.ndarray,
                    available_attrs: List[int],
                    attribute_names: List[str]) -> TreeNode:
        """
        Recursively build the decision tree.
        
        Base cases:
        1. All examples have same class -> leaf node
        2. No attributes left -> leaf with majority class
        3. No examples -> leaf with parent's majority (handled in parent)
        
        Recursive case:
        Select best attribute, create branches for each value,
        recurse on subsets.
        """
        # Base case 1: All examples have same class
        unique_classes = np.unique(y)
        if len(unique_classes) == 1:
            return TreeNode(is_leaf=True, prediction=unique_classes[0])
        
        # Base case 2: No attributes remaining
        if len(available_attrs) == 0:
            return TreeNode(is_leaf=True, 
                          prediction=self._majority_class(y))
        
        # Find attribute with maximum information gain
        best_gain = -1
        best_attr_idx = None
        
        for attr_idx in available_attrs:
            gain = self._information_gain(X, y, attr_idx)
            if gain > best_gain:
                best_gain = gain
                best_attr_idx = attr_idx
        
        # Create internal node
        best_attr_name = attribute_names[best_attr_idx]
        node = TreeNode(
            is_leaf=False,
            attribute=best_attr_name,
            children={}
        )
        
        # Remove this attribute from available set
        remaining_attrs = [i for i in available_attrs if i != best_attr_idx]
        
        # Create branches for each attribute value
        unique_values = np.unique(X[:, best_attr_idx])
        majority_class = self._majority_class(y)  # Default for empty branches
        
        for value in unique_values:
            mask = X[:, best_attr_idx] == value
            subset_X = X[mask]
            subset_y = y[mask]
            
            if len(subset_y) == 0:
                # Empty subset: use parent's majority class
                node.children[value] = TreeNode(
                    is_leaf=True, 
                    prediction=majority_class
                )
            else:
                # Recurse on subset
                node.children[value] = self._build_tree(
                    subset_X, subset_y, 
                    remaining_attrs, attribute_names
                )
        
        return node
    
    def fit(self, X: np.ndarray, y: np.ndarray, 
            attribute_names: Optional[List[str]] = None):
        """
        Build the decision tree from training data.
        
        Parameters:
            X: Feature matrix (n_samples, n_attributes), categorical values
            y: Class labels (n_samples,)
            attribute_names: Optional names for attributes
        """
        n_samples, n_attrs = X.shape
        
        if attribute_names is None:
            attribute_names = [f"attr_{i}" for i in range(n_attrs)]
        
        self.attributes = attribute_names
        available_attrs = list(range(n_attrs))
        
        self.root = self._build_tree(X, y, available_attrs, attribute_names)
        
        return self
    
    def predict_one(self, x: np.ndarray, 
                    attribute_name_to_idx: Dict[str, int]) -> str:
        """Predict class for a single instance."""
        node = self.root
        
        while not node.is_leaf:
            attr_name = node.attribute
            attr_idx = attribute_name_to_idx[attr_name]
            value = x[attr_idx]
            
            if value in node.children:
                node = node.children[value]
            else:
                # Unseen value: return most common child prediction
                # (Simple handling; real systems do better)
                child_preds = [c.prediction for c in node.children.values() 
                              if c.is_leaf]
                if child_preds:
                    return Counter(child_preds).most_common(1)[0][0]
                else:
                    node = list(node.children.values())[0]
        
        return node.prediction
    
    def predict(self, X: np.ndarray) -> np.ndarray:
        """Predict classes for multiple instances."""
        attr_to_idx = {name: i for i, name in enumerate(self.attributes)}
        predictions = [self.predict_one(x, attr_to_idx) for x in X]
        return np.array(predictions)
    
    def print_tree(self, node: Optional[TreeNode] = None, 
                   indent: str = "") -> None:
        """Pretty-print the decision tree."""
        if node is None:
            node = self.root
        
        if node.is_leaf:
            print(f"{indent}→ {node.prediction}")
        else:
            print(f"{indent}[{node.attribute}]")
            for value, child in node.children.items():
                print(f"{indent}  = {value}:")
                self.print_tree(child, indent + "    ")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import numpy as np
 
# Play Tennis Dataset
data = np.array([
    ['Sunny',    'Hot',  'High',   'Weak',   'No'],
    ['Sunny',    'Hot',  'High',   'Strong', 'No'],
    ['Overcast', 'Hot',  'High',   'Weak',   'Yes'],
    ['Rain',     'Mild', 'High',   'Weak',   'Yes'],
    ['Rain',     'Cool', 'Normal', 'Weak',   'Yes'],
    ['Rain',     'Cool', 'Normal', 'Strong', 'No'],
    ['Overcast', 'Cool', 'Normal', 'Strong', 'Yes'],
    ['Sunny',    'Mild', 'High',   'Weak',   'No'],
    ['Sunny',    'Cool', 'Normal', 'Weak',   'Yes'],
    ['Rain',     'Mild', 'Normal', 'Weak',   'Yes'],
    ['Sunny',    'Mild', 'Normal', 'Strong', 'Yes'],
    ['Overcast', 'Mild', 'High',   'Strong', 'Yes'],
    ['Overcast', 'Hot',  'Normal', 'Weak',   'Yes'],
    ['Rain',     'Mild', 'High',   'Strong', 'No'],
])
 
X = data[:, :-1]
y = data[:, -1]
attribute_names = ['Outlook', 'Temperature', 'Humidity', 'Wind']
 
# Build and display the tree
clf = ID3Classifier()
clf.fit(X, y, attribute_names)
 
print("ID3 Decision Tree for Play Tennis:")
print("=" * 40)
clf.print_tree()
 
print("
" + "=" * 40)
print("Predictions on training data:")
predictions = clf.predict(X)
accuracy = np.mean(predictions == y)
print(f"Training accuracy: {accuracy:.2%}")