<jupyter_start><jupyter_text>Decision treeshttps://scikit-learn.org/stable/modules/tree.html * pruning: helps agains overfitting * decision trees within an ensemble $\rightarrow$ stability * balance data sets $\rightarrow$ else you get biased trees Initial example (from the scikit-learn website)<jupyter_code>from pylab import *
from sklearn.datasets import load_iris
from sklearn import tree
iris = load_iris()
X, y = iris.data, iris.target
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, y)

print(concatenate((X.transpose(),y.reshape((1,len(y))))).transpose())
import graphviz, pydotplus
from IPython.display import Image  

dot_data = tree.export_graphviz(clf, out_file=None, 
                      feature_names=iris.feature_names,  
                      class_names=iris.target_names,  
                      filled=True, rounded=True,  
                      special_characters=True)  

pydot_graph = pydotplus.graph_from_dot_data(dot_data)
Image(pydot_graph.create_png())
# adapted from https://stackoverflow.com/questions/20224526/how-to-extract-the-decision-rules-from-scikit-learn-decision-tree

def get_code(tree, feature_names):
    left      = tree.tree_.children_left
    right     = tree.tree_.children_right
    threshold = tree.tree_.threshold
    features  = [feature_names[i] for i in tree.tree_.feature]
    value = tree.tree_.value

    def recurse(left, right, threshold, features, node, indent=0):
        if (right[node] != -1):
            assert left[node] != -1
            print(" "*indent + "if ( " + features[node] + " <= " + str(threshold[node]) + " ) {")
            recurse (left, right, threshold, features,left[node], indent+2)
            print(" "*indent + "} else {")
            recurse (left, right, threshold, features,right[node], indent+2)
            print(" "*indent + "}")
        else:
            print(" "*(indent) + "return " + str(value[node]))

    recurse(left, right, threshold, features, 0)

get_code(clf,iris.feature_names)
from __future__ import annotations
import dataclasses
from typing import Union
import json

@dataclasses.dataclass
class LeafNode:
    class_idx: int
    probs: list[float]

@dataclasses.dataclass
class SplitNode:
    name: str
    idx: int
    threshold: float
    left: Union[SplitNode, LeafNode]
    right: Union[SplitNode, LeafNode]    
    
def get_decision_tree(tree, feature_names):
    left      = tree.tree_.children_left
    right     = tree.tree_.children_right
    threshold = tree.tree_.threshold
    features  = [feature_names[i] for i in tree.tree_.feature]
    value = tree.tree_.value

    def recurse(left, right, threshold, features, node):
        if (right[node] != -1):
            assert left[node] != -1
            return SplitNode(
                features[node],
                tree.tree_.feature[node],
                threshold[node],
                recurse (left, right, threshold, features,left[node]),
                recurse (left, right, threshold, features,right[node])
            )
        else:
            winner_idx = argmax(value[node])
            return LeafNode(
                winner_idx,
                value[node]
            )

    return recurse(left, right, threshold, features, 0)

class EnhancedJSONEncoder(json.JSONEncoder):
    # from https://stackoverflow.com/questions/51286748/make-the-python-json-encoder-support-pythons-new-dataclasses
    def default(self, o):
        if isinstance(o, np.ndarray):
            return o.tolist()        
        elif isinstance(o, np.integer):
            return int(o)
        elif isinstance(o, np.floating):
            return float(o)
        elif isinstance(o, np.floating):
            return float(o)
        elif dataclasses.is_dataclass(o):
            return dataclasses.asdict(o)
        else:
            return super().default(o)

t = get_decision_tree(clf,iris.feature_names)
print(json.dumps(t, cls=EnhancedJSONEncoder, indent=2))<jupyter_output>{
  "name": "petal width (cm)",
  "idx": 3,
  "threshold": 0.800000011920929,
  "left": {
    "class_idx": 0,
    "probs": [
      [
        50.0,
        0.0,
        0.0
      ]
    ]
  },
  "right": {
    "name": "petal width (cm)",
    "idx": 3,
    "threshold": 1.75,
    "left": {
      "name": "petal length (cm)",
      "idx": 2,
      "threshold": 4.950000047683716,
      "left": {
        "name": "petal width (cm)",
        "idx": 3,
        "threshold": 1.6500000357627869,
        "left": {
          "class_idx": 1,
          "probs": [
            [
              0.0,
              47.0,
              0.0
            ]
          ]
        },
        "right": {
          "class_idx": 2,
          "probs": [
            [
              0.0,
              0.0,
              1.0
            ]
          ]
        }
      },
      "right": {
        "name": "petal width (cm)",
        "idx": 3,
        "threshold": 1.550000011920929,
        "left": {
          "class_idx": 2,
    [...]<jupyter_text>Simple example problemsDefine some problem sets:<jupyter_code>%matplotlib inline
from pylab import *

def make_dataframe(**kwargs):
    from pandas import DataFrame
    return DataFrame(kwargs)

def my_plot_2D_data(D,T=None):
    if T is None:
        dataframe=D
    else:
        dataframe = make_dataframe( x=D[:,0], y=D[:,1], target=T )
    for target, data in dataframe.groupby("target"):
        plot(data.x, data.y, 'o', label=f"target={target}")
        
from sklearn.datasets import make_blobs, make_moons, make_circles

def my_make_blobs(n=2,a=3, xscale=1, yscale=1, xshift=0,nb_classes=2,n_samples=100):
    centers = [[0,0],[a,a],[a*2,0],[a,-a],
               [a,2*a]]
    D,T = make_blobs(
        n_samples=n_samples,
        centers=centers[0:n],
        cluster_std=1,
        n_features=2, 
        random_state=0
    )
    T = T%nb_classes
    return make_dataframe( x=D[:,0]*xscale+xshift, y=D[:,1]*yscale, target=T )

def my_circles():
    D,T = make_circles(
        n_samples=50,
        shuffle=True,
        noise=0.1,
        random_state=0, 
        factor=0.5
    )
    D2,T2 = make_circles(
        n_samples=100,
        shuffle=True,
        noise=0.05,
        random_state=0, 
        factor=0.5
    )
    D = concatenate((D,4*D2[T2==1,:]), axis=0)
    T = concatenate((T,T2[T2==1]), axis=0)
    return make_dataframe( x=D[:,0], y=D[:,1], target=T )

def my_make_moons():
    D,T = make_moons(
        n_samples=300, 
        shuffle=True,
        noise=0.2, 
        random_state=0
    )
    T = T%2
    return make_dataframe( x=D[:,0], y=D[:,1], target=T )

def make_challenge(level):
    if level==0: return my_make_blobs(2)
    elif level==1: return my_make_blobs(3)
    elif level==2: return my_make_blobs(4)
    elif level==3: return my_circles()
    elif level==4: return my_make_moons()
    raise Exception(f"unknown level f{level}")<jupyter_output><empty_output><jupyter_text>Show some challenges<jupyter_code>figure(figsize=[15,3])
N=5
idx=0
for n in range(N):
    idx += 1
    subplot(1,N,idx)
    dataframe = make_challenge(n)
    x = dataframe[["x"]].values.flatten()
    y = dataframe[["y"]].values.flatten()
    label = dataframe[["target"]].values.flatten()*2-1
    plot( x[label==+1], y[label==+1], 'go' )
    plot( x[label==-1], y[label==-1], 'ro' )<jupyter_output><empty_output><jupyter_text>Train and display classifier:<jupyter_code>from sklearn.datasets import load_iris
from sklearn import tree

def train_and_show(model, dataframe):
    x = dataframe[["x"]].values.flatten()
    y = dataframe[["y"]].values.flatten()
    label = dataframe[["target"]].values.flatten()*2-1

    X_train = dataframe[["x","y"]].values
    y_train = dataframe[["target"]].values*2-1
    y_train = y_train.reshape(( len(y_train), ))
    model = model.fit(X_train, y_train)    
    
    N=100
    X,Y = meshgrid( linspace(min(x),max(x),N), linspace(min(y),max(y),N) )
    D = stack((X.flatten(), Y.flatten())).transpose()
    T = model.predict(D)
    #print(T.shape)

    T=T.flatten().reshape(X.shape)
    contourf(X,Y,sign(T),colors=['#FFAAAA','#AAFFAA'], extend=True)

    plot( x[label==+1], y[label==+1], 'go' )
    plot( x[label==-1], y[label==-1], 'ro' )
    
    
model = tree.DecisionTreeClassifier()
train_and_show(model, my_make_blobs(2));<jupyter_output><empty_output><jupyter_text>Example classification (simple decision tree)<jupyter_code>figure(figsize=[15,5])
N=5
idx=0
for n in range(N):
    idx += 1
    subplot(1,N,idx)
    model = tree.DecisionTreeClassifier(random_state=0)
    train_and_show(model, make_challenge(n))<jupyter_output><empty_output><jupyter_text>Random forests<jupyter_code>from sklearn.ensemble import RandomForestClassifier
N=5
idx=0
params=[1,10,100,300]
M=len(params)

figure(figsize=[15,5*M])
for m in range(M):   
    for n in range(N):
        if n==1:
            ylabel(f"num estims.={params[m]}")
        idx += 1
        subplot(M,N,idx)
        model = RandomForestClassifier(random_state=0, n_estimators=params[m])
        train_and_show(model, make_challenge(n))<jupyter_output><empty_output><jupyter_text>Pruning<jupyter_code>from sklearn.ensemble import RandomForestClassifier
N=5
idx=0
params=[0, 0.05, 0.1, 0.2]
M=len(params)

figure(figsize=[15,5*M])
for m in range(M):   
    for n in range(N):
        if n==1:
            ylabel(f"ccp_alpha={params[m]}")
        idx += 1
        subplot(M,N,idx)
        model = RandomForestClassifier(random_state=0, n_estimators=100, ccp_alpha=params[m])
        train_and_show(model, make_challenge(n))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14443161540883803, 'fraction_numerical': 0.02750078723627585, 'mean_word_length': 2.7335423197492164, 'pattern_counts': {'":': 30, '<': 29, '<?xml version=': 0, '>': 28, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '644104', 'license': 'MIT', 'n_tokens_mistral': 3508, 'n_tokens_neox': 3363, 'n_words': 628, 'path': 'woodland_book/decision_trees.ipynb', 'repo_name': 'goto40/woodland', 'size': '9527'}