Decision Trees

Ad_ID  CTR   Quality  Relevance  Domain_Age  HTTPS  Violations  Category      Target
1      0.08  9        0.92       2000        1      0           Tech           1 (Approved)
2      0.02  3        0.45       100         0      2           Pharmaceut.    0 (Rejected)
3      0.04  7        0.78       1500        1      0           Finance        1 (Approved)
4      0.01  2        0.30       200         0      1           Gambling       0 (Rejected)
...    ...   ...      ...        ...         ...    ...         ...            ...

function BuildTree(samples, depth):
    if stopping_criteria_met(samples, depth):
        return Leaf(majority_class(samples))

    best_split = None
    best_gain = -∞

    for feature in all_features:
        for threshold in candidate_thresholds(feature, samples):
            left, right = split(samples, feature, threshold)
            gain = information_gain(samples, left, right)

            if gain > best_gain:
                best_gain = gain
                best_split = (feature, threshold)

    left, right = split(samples, best_split)
    node.left = BuildTree(left, depth+1)
    node.right = BuildTree(right, depth+1)
    return node

import numpy as np
import pandas as pd
from collections import Counter


class Node:
    """Represents a node in the decision tree."""

    def __init__(self, feature=None, threshold=None, left=None,
                 right=None, value=None):
        self.feature = feature        # Index of feature to split on
        self.threshold = threshold      # Threshold for the split
        self.left = left              # Left subtree (≤ threshold)
        self.right = right            # Right subtree (> threshold)
        self.value = value            # Class prediction if leaf
        self.samples = 0              # Number of samples at this node
        self.impurity = 0             # Gini/Entropy at this node

    def is_leaf(self):
        return self.value is not None

class DecisionTreeClassifier:
    """Decision Tree Classifier using Gini Impurity or Entropy."""

    def __init__(self, max_depth=None, min_samples_split=2,
                 min_samples_leaf=1, criterion="gini", random_state=None):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.criterion = criterion
        self.random_state = random_state
        self.root = None
        self.feature_importances_ = None

    def fit(self, X, y):
        """Build decision tree classifier."""
        if isinstance(X, pd.DataFrame):
            self.feature_names_ = X.columns.tolist()
            X = X.values
        else:
            self.feature_names_ = [f"f{i}" for i in range(X.shape[1])]

        self.root = self._build_tree(X, y)
        self._compute_feature_importance(X.shape[1])
        return self

    def _build_tree(self, X, y, depth=0):
        """Recursively build the tree."""
        n_samples, n_features = X.shape
        n_classes = len(np.unique(y))

        # Create leaf node
        node = Node()
        node.samples = n_samples
        node.value = Counter(y).most_common(1)[0][0]

        # Stopping criteria
        if (depth >= self.max_depth if self.max_depth else False):
            return node
        if n_samples < self.min_samples_split:
            return node
        if n_classes == 1:  # Pure node
            return node

        # Find best split
        best_split = self._best_split(X, y)
        if best_split is None:
            return node

        feature, threshold, left_idx, right_idx = best_split

        # Convert to internal node
        node.feature = feature
        node.threshold = threshold
        node.value = None
        node.impurity = self._impurity(y)

        # Recursively build subtrees
        node.left = self._build_tree(X[left_idx], y[left_idx], depth+1)
        node.right = self._build_tree(X[right_idx], y[right_idx], depth+1)

        return node

    def _best_split(self, X, y):
        """Find the best split for a node."""
        best_gain = -np.inf
        best_split = None

        for feature_idx in range(X.shape[1]):
            feature_values = X[:, feature_idx]

            # Try each unique value as threshold
            for threshold in np.unique(feature_values):
                left_idx = feature_values <= threshold
                right_idx = ~left_idx

                # Check min_samples_leaf constraint
                if (left_idx.sum() < self.min_samples_leaf or
                    right_idx.sum() < self.min_samples_leaf):
                    continue

                # Calculate information gain
                gain = self._information_gain(y, y[left_idx], y[right_idx])

                if gain > best_gain:
                    best_gain = gain
                    best_split = (feature_idx, threshold, left_idx, right_idx)

        return best_split

    def _impurity(self, y):
        """Calculate Gini or Entropy."""
        counts = np.bincount(y)
        probabilities = counts / len(y)

        if self.criterion == "gini":
            return 1 - np.sum(probabilities ** 2)
        else:  # entropy
            return -np.sum(probabilities * np.log2(probabilities + 1e-10))

    def _information_gain(self, parent, left, right):
        """Calculate information gain from a split."""
        n_left, n_right = len(left), len(right)
        n_total = n_left + n_right

        if n_left == 0 or n_right == 0:
            return 0

        parent_impurity = self._impurity(parent)
        left_impurity = self._impurity(left)
        right_impurity = self._impurity(right)

        child_impurity = (n_left / n_total) * left_impurity + \
                        (n_right / n_total) * right_impurity

        return parent_impurity - child_impurity

    def predict(self, X):
        """Predict class for X."""
        if isinstance(X, pd.DataFrame):
            X = X.values
        return np.array([self._traverse_tree(self.root, x)
                          for x in X])

    def _traverse_tree(self, node, x):
        """Traverse tree to get prediction for single sample."""
        if node.is_leaf():
            return node.value

        if x[node.feature] <= node.threshold:
            return self._traverse_tree(node.left, x)
        else:
            return self._traverse_tree(node.right, x)

    def _compute_feature_importance(self, n_features):
        """Compute feature importance from tree structure."""
        importances = np.zeros(n_features)

        def _add_importance(self, node):
            if node.is_leaf():
                return

            gain = node.samples * node.impurity
            importances[node.feature] += gain

            _add_importance(self, node.left)
            _add_importance(self, node.right)

        _add_importance(self, self.root)
        self.feature_importances_ = importances / importances.sum()

    def score(self, X, y):
        """Accuracy score."""
        return np.mean(self.predict(X) == y)

# Create synthetic ad quality dataset
np.random.seed(42)
n_samples = 500

X = pd.DataFrame({
    'CTR': np.random.uniform(0.01, 0.15, n_samples),
    'Quality_Score': np.random.randint(1, 11, n_samples),
    'Domain_Age_Years': np.random.randint(1, 20, n_samples),
    'Has_HTTPS': np.random.randint(0, 2, n_samples),
    'Prior_Violations': np.random.randint(0, 5, n_samples)
})

# Create target: Approved (1) if conditions met
y = ((X['CTR'] > 0.04) & (X['Quality_Score'] > 6) |
     (X['Domain_Age_Years'] > 10)).astype(int)

# Split data
split_idx = int(0.8 * n_samples)
X_train, X_test = X[:split_idx], X[split_idx:]
y_train, y_test = y[:split_idx], y[split_idx:]

# Train tree
tree = DecisionTreeClassifier(max_depth=5, min_samples_split=10,
                              criterion="gini")
tree.fit(X_train, y_train)

# Evaluate
print(f"Train Accuracy: {tree.score(X_train, y_train):.3f}")
print(f"Test Accuracy: {tree.score(X_test, y_test):.3f}")

# Feature importance
for feature, importance in zip(X.columns, tree.feature_importances_):
    print(f"{feature}: {importance:.3f}")

# Make predictions
new_ad = pd.DataFrame({
    'CTR': [0.06],
    'Quality_Score': [8],
    'Domain_Age_Years': [12],
    'Has_HTTPS': [1],
    'Prior_Violations': [0]
})
prediction = tree.predict(new_ad)
print(f"Ad Status: {'Approved' if prediction[0] == 1 else 'Rejected'}")

Train Accuracy: 0.896
Test Accuracy: 0.876

CTR: 0.341
Quality_Score: 0.298
Domain_Age_Years: 0.205
Has_HTTPS: 0.089
Prior_Violations: 0.067

Ad Status: Approved