CART algorithm (Geron Ch 5, morie.fn hmcart) — morie_geron_cart

Greedy binary splits minimising J(k, t) = (m_L/m) G_L + (m_R/m) G_R. The split COST is delegated to morie_geron_cart_split_cost exactly as the Python module delegates to grcart, so the impurity arithmetic is never re-derived here. feature indices in the returned tree are 0-based, matching Python.

Usage

morie_geron_cart_algorithm(
  X,
  y,
  criterion = "gini",
  max_depth = NULL,
  min_samples_split = 2,
  min_samples_leaf = 1,
  min_impurity_decrease = 0
)

Arguments

X: Feature matrix.
y: Labels or targets.
criterion: "gini", "entropy" or "mse".
max_depth: Optional depth cap.
min_samples_split: Minimum node size to consider a split.
min_samples_leaf: Minimum leaf size.
min_impurity_decrease: Minimum gain to accept a split.

Value

List with tree, predictions, n_leaves, depth, n_splits, criterion, feature_importances, train_accuracy or train_mse, estimate, n.

Details

This one function serves the whole tree family: hmcdt (morie_geron_classification_tree) is the only wrapper ported here, but hmdtr, hmdthv, hmdtst, hmext, hmgbrt, hmrdt and hmrfc all route their growth through this same core in Python.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
morie_geron_cart_algorithm(V, V)
#> $tree
#> $tree$leaf
#> [1] FALSE
#> 
#> $tree$feature
#> [1] 0
#> 
#> $tree$threshold
#> [1] 1.5
#> 
#> $tree$impurity
#> [1] 0.875
#> 
#> $tree$impurity_decrease
#> [1] 0.125
#> 
#> $tree$n
#> [1] 8
#> 
#> $tree$depth
#> [1] 0
#> 
#> $tree$left
#> $tree$left$leaf
#> [1] TRUE
#> 
#> $tree$left$value
#> [1] 1
#> 
#> $tree$left$proba
#> $tree$left$proba$`1`
#> [1] 1
#> 
#> 
#> $tree$left$n
#> [1] 1
#> 
#> $tree$left$impurity
#> [1] 0
#> 
#> $tree$left$depth
#> [1] 1
#> 
#> 
#> $tree$right
#> $tree$right$leaf
#> [1] FALSE
#> 
#> $tree$right$feature
#> [1] 0
#> 
#> $tree$right$threshold
#> [1] 2.5
#> 
#> $tree$right$impurity
#> [1] 0.8571429
#> 
#> $tree$right$impurity_decrease
#> [1] 0.1428571
#> 
#> $tree$right$n
#> [1] 7
#> 
#> $tree$right$depth
#> [1] 1
#> 
#> $tree$right$left
#> $tree$right$left$leaf
#> [1] TRUE
#> 
#> $tree$right$left$value
#> [1] 2
#> 
#> $tree$right$left$proba
#> $tree$right$left$proba$`2`
#> [1] 1
#> 
#> 
#> $tree$right$left$n
#> [1] 1
#> 
#> $tree$right$left$impurity
#> [1] 0
#> 
#> $tree$right$left$depth
#> [1] 2
#> 
#> 
#> $tree$right$right
#> $tree$right$right$leaf
#> [1] FALSE
#> 
#> $tree$right$right$feature
#> [1] 0
#> 
#> $tree$right$right$threshold
#> [1] 3.5
#> 
#> $tree$right$right$impurity
#> [1] 0.8333333
#> 
#> $tree$right$right$impurity_decrease
#> [1] 0.1666667
#> 
#> $tree$right$right$n
#> [1] 6
#> 
#> $tree$right$right$depth
#> [1] 2
#> 
#> $tree$right$right$left
#> $tree$right$right$left$leaf
#> [1] TRUE
#> 
#> $tree$right$right$left$value
#> [1] 3
#> 
#> $tree$right$right$left$proba
#> $tree$right$right$left$proba$`3`
#> [1] 1
#> 
#> 
#> $tree$right$right$left$n
#> [1] 1
#> 
#> $tree$right$right$left$impurity
#> [1] 0
#> 
#> $tree$right$right$left$depth
#> [1] 3
#> 
#> 
#> $tree$right$right$right
#> $tree$right$right$right$leaf
#> [1] FALSE
#> 
#> $tree$right$right$right$feature
#> [1] 0
#> 
#> $tree$right$right$right$threshold
#> [1] 4.5
#> 
#> $tree$right$right$right$impurity
#> [1] 0.8
#> 
#> $tree$right$right$right$impurity_decrease
#> [1] 0.2
#> 
#> $tree$right$right$right$n
#> [1] 5
#> 
#> $tree$right$right$right$depth
#> [1] 3
#> 
#> $tree$right$right$right$left
#> $tree$right$right$right$left$leaf
#> [1] TRUE
#> 
#> $tree$right$right$right$left$value
#> [1] 4
#> 
#> $tree$right$right$right$left$proba
#> $tree$right$right$right$left$proba$`4`
#> [1] 1
#> 
#> 
#> $tree$right$right$right$left$n
#> [1] 1
#> 
#> $tree$right$right$right$left$impurity
#> [1] 0
#> 
#> $tree$right$right$right$left$depth
#> [1] 4
#> 
#> 
#> $tree$right$right$right$right
#> $tree$right$right$right$right$leaf
#> [1] FALSE
#> 
#> $tree$right$right$right$right$feature
#> [1] 0
#> 
#> $tree$right$right$right$right$threshold
#> [1] 5.5
#> 
#> $tree$right$right$right$right$impurity
#> [1] 0.75
#> 
#> $tree$right$right$right$right$impurity_decrease
#> [1] 0.25
#> 
#> $tree$right$right$right$right$n
#> [1] 4
#> 
#> $tree$right$right$right$right$depth
#> [1] 4
#> 
#> $tree$right$right$right$right$left
#> $tree$right$right$right$right$left$leaf
#> [1] TRUE
#> 
#> $tree$right$right$right$right$left$value
#> [1] 5
#> 
#> $tree$right$right$right$right$left$proba
#> $tree$right$right$right$right$left$proba$`5`
#> [1] 1
#> 
#> 
#> $tree$right$right$right$right$left$n
#> [1] 1
#> 
#> $tree$right$right$right$right$left$impurity
#> [1] 0
#> 
#> $tree$right$right$right$right$left$depth
#> [1] 5
#> 
#> 
#> $tree$right$right$right$right$right
#> $tree$right$right$right$right$right$leaf
#> [1] FALSE
#> 
#> $tree$right$right$right$right$right$feature
#> [1] 0
#> 
#> $tree$right$right$right$right$right$threshold
#> [1] 6.5
#> 
#> $tree$right$right$right$right$right$impurity
#> [1] 0.6666667
#> 
#> $tree$right$right$right$right$right$impurity_decrease
#> [1] 0.3333333
#> 
#> $tree$right$right$right$right$right$n
#> [1] 3
#> 
#> $tree$right$right$right$right$right$depth
#> [1] 5
#> 
#> $tree$right$right$right$right$right$left
#> $tree$right$right$right$right$right$left$leaf
#> [1] TRUE
#> 
#> $tree$right$right$right$right$right$left$value
#> [1] 6
#> 
#> $tree$right$right$right$right$right$left$proba
#> $tree$right$right$right$right$right$left$proba$`6`
#> [1] 1
#> 
#> 
#> $tree$right$right$right$right$right$left$n
#> [1] 1
#> 
#> $tree$right$right$right$right$right$left$impurity
#> [1] 0
#> 
#> $tree$right$right$right$right$right$left$depth
#> [1] 6
#> 
#> 
#> $tree$right$right$right$right$right$right
#> $tree$right$right$right$right$right$right$leaf
#> [1] FALSE
#> 
#> $tree$right$right$right$right$right$right$feature
#> [1] 0
#> 
#> $tree$right$right$right$right$right$right$threshold
#> [1] 7.5
#> 
#> $tree$right$right$right$right$right$right$impurity
#> [1] 0.5
#> 
#> $tree$right$right$right$right$right$right$impurity_decrease
#> [1] 0.5
#> 
#> $tree$right$right$right$right$right$right$n
#> [1] 2
#> 
#> $tree$right$right$right$right$right$right$depth
#> [1] 6
#> 
#> $tree$right$right$right$right$right$right$left
#> $tree$right$right$right$right$right$right$left$leaf
#> [1] TRUE
#> 
#> $tree$right$right$right$right$right$right$left$value
#> [1] 7
#> 
#> $tree$right$right$right$right$right$right$left$proba
#> $tree$right$right$right$right$right$right$left$proba$`7`
#> [1] 1
#> 
#> 
#> $tree$right$right$right$right$right$right$left$n
#> [1] 1
#> 
#> $tree$right$right$right$right$right$right$left$impurity
#> [1] 0
#> 
#> $tree$right$right$right$right$right$right$left$depth
#> [1] 7
#> 
#> 
#> $tree$right$right$right$right$right$right$right
#> $tree$right$right$right$right$right$right$right$leaf
#> [1] TRUE
#> 
#> $tree$right$right$right$right$right$right$right$value
#> [1] 8
#> 
#> $tree$right$right$right$right$right$right$right$proba
#> $tree$right$right$right$right$right$right$right$proba$`8`
#> [1] 1
#> 
#> 
#> $tree$right$right$right$right$right$right$right$n
#> [1] 1
#> 
#> $tree$right$right$right$right$right$right$right$impurity
#> [1] 0
#> 
#> $tree$right$right$right$right$right$right$right$depth
#> [1] 7
#> 
#> 
#> 
#> 
#> 
#> 
#> 
#> 
#> 
#> $predictions
#> [1] 1 2 3 4 5 6 7 8
#> 
#> $n_leaves
#> [1] 8
#> 
#> $depth
#> [1] 7
#> 
#> $n_splits
#> [1] 7
#> 
#> $criterion
#> [1] "gini"
#> 
#> $feature_importances
#> [1] 1
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "greedy CART; split cost delegated to grcart"
#> 
#> $train_accuracy
#> [1] 1
#> 
#> $estimate
#> [1] 1
#>