Prediction Workflow

• Data Acquisition: Retrieve the text dataset sourced from the UCI repository.
• Data Preparation: Parse the tab-delimited records.
• Data Analysis: Validate the parsed data and visualize the resulting decision model.
• Model Training: Construct the tree structure using the build_tree method.
• Model Evaluation: Test the classifier with validation instances.
• Deployment: Serialize the tree structure to disk to bypass retraining.

Core ID3 Implementation

import math
import pickle
import operator

def compute_entropy(dataset):
    total = len(dataset)
    freq = {}
    for row in dataset:
        label = row[-1]
        freq[label] = freq.get(label, 0) + 1
    entropy = 0.0
    for count in freq.values():
        p = count / total
        entropy -= p * math.log2(p)
    return entropy

def partition_data(dataset, col_idx, target_val):
    subset = []
    for row in dataset:
        if row[col_idx] == target_val:
            trimmed = row[:col_idx] + row[col_idx+1:]
            subset.append(trimmed)
    return subset

def find_optimal_split(dataset):
    num_cols = len(dataset[0]) - 1
    base_ent = compute_entropy(dataset)
    max_gain = 0.0
    best_col = -1
    for i in range(num_cols):
        vals = set(row[i] for row in dataset)
        subset_ent = 0.0
        for v in vals:
            subset = partition_data(dataset, i, v)
            prob = len(subset) / float(len(dataset))
            subset_ent += prob * compute_entropy(subset)
        gain = base_ent - subset_ent
        if gain > max_gain:
            max_gain = gain
            best_col = i
    return best_col

def get_dominant_class(labels):
    tally = {}
    for l in labels:
        tally[l] = tally.get(l, 0) + 1
    sorted_tally = sorted(tally.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_tally[0][0]

def build_tree(dataset, feature_names):
    outcomes = [row[-1] for row in dataset]
    if outcomes.count(outcomes[0]) == len(outcomes):
        return outcomes[0]
    if len(dataset[0]) == 1:
        return get_dominant_class(outcomes)
    best_idx = find_optimal_split(dataset)
    best_name = feature_names[best_idx]
    tree = {best_name: {}}
    del feature_names[best_idx]
    unique_vals = set(row[best_idx] for row in dataset)
    for v in unique_vals:
        sub_names = feature_names[:]
        tree[best_name][v] = build_tree(partition_data(dataset, best_idx, v), sub_names)
    return tree

def predict(node, header, sample):
    root_key = list(node.keys())[0]
    sub_node = node[root_key]
    feat_idx = header.index(root_key)
    for key in sub_node.keys():
        if sample[feat_idx] == key:
            if isinstance(sub_node[key], dict):
                return predict(sub_node[key], header, sample)
            else:
                return sub_node[key]

def serialize_model(tree, filepath):
    with open(filepath, 'wb') as f:
        pickle.dump(tree, f)

def deserialize_model(filepath):
    with open(filepath, 'rb') as f:
        return pickle.load(f)

Decision Tree Visualization

import matplotlib.pyplot as plt

branch_style = dict(boxstyle="sawtooth", fc="0.8")
leaf_style = dict(boxstyle="round4", fc="0.8")
arrow_cfg = dict(arrowstyle="<-")

def draw_node(ax, txt, center, parent, style):
    ax.annotate(txt, xy=parent, xycoords='axes fraction',
                xytext=center, textcoords='axes fraction',
                va="center", ha="center", bbox=style, arrowprops=arrow_cfg)

def count_leaves(tree):
    count = 0
    root = list(tree.keys())[0]
    branches = tree[root]
    for key in branches.keys():
        if isinstance(branches[key], dict):
            count += count_leaves(branches[key])
        else:
            count += 1
    return count

def measure_depth(tree):
    depth = 0
    root = list(tree.keys())[0]
    branches = tree[root]
    for key in branches.keys():
        if isinstance(branches[key], dict):
            curr = 1 + measure_depth(branches[key])
        else:
            curr = 1
        if curr > depth:
            depth = curr
    return depth

def render_branches(ax, tree, parent_pos, txt):
    leaves = count_leaves(tree)
    depth = measure_depth(tree)
    root = list(tree.keys())[0]
    center = (render_branches.x_offset + (1.0 + float(leaves)) / 2.0 / render_branches.width, render_branches.y_offset)
    draw_mid_text(ax, center, parent_pos, txt)
    draw_node(ax, root, center, parent_pos, branch_style)
    branches = tree[root]
    render_branches.y_offset -= 1.0 / render_branches.max_depth
    for key in branches.keys():
        if isinstance(branches[key], dict):
            render_branches(ax, branches[key], center, str(key))
        else:
            render_branches.x_offset += 1.0 / render_branches.width
            draw_node(ax, branches[key], (render_branches.x_offset, render_branches.y_offset), center, leaf_style)
            draw_mid_text(ax, (render_branches.x_offset, render_branches.y_offset), center, str(key))
    render_branches.y_offset += 1.0 / render_branches.max_depth

def draw_mid_text(ax, center, parent, txt):
    x = (parent[0] - center[0]) / 2.0 + center[0]
    y = (parent[1] - center[1]) / 2.0 + center[1]
    ax.text(x, y, txt)

def render_tree(tree):
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    ax_props = dict(xticks=[], yticks=[])
    ax = plt.subplot(111, frameon=False, **ax_props)
    render_branches.width = float(count_leaves(tree))
    render_branches.max_depth = float(measure_depth(tree))
    render_branches.x_offset = -0.5 / render_branches.width
    render_branches.y_offset = 1.0
    render_branches(ax, tree, (0.5, 1.0), '')
    plt.show()

Execution and Overfitting Considerations

>>> import id3_core
>>> import tree_viz
>>> with open('lenses.txt') as f:
...     records = [line.strip().split('\t') for line in f]
>>> attrs = ['age', 'prescript', 'astigmatic', 'tearRate']
>>> lens_model = id3_core.build_tree(records, attrs)
>>> lens_model
{'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic': {'yes': {'prescript': {'hyper': {'age': {'pre': 'no lenses', 'presbyopic': 'no lenses', 'young': 'hard'}}, 'myope': 'hard'}}, 'no': {'age': {'pre': 'soft', 'presbyopic': {'prescript': {'hyper': 'soft', 'myope': 'no lenses'}}, 'young': 'soft'}}}}}}
>>> tree_viz.render_tree(lens_model)

An unpruned tree often captures noise in the training data, resulting in overfitting. To mitigate this, pruning techniques can be applied to remove leaf nodes that contribute minimal information, merging them into parent branches.