cart pruning marimo

import%20marimo%0A%0A__generated_with%20%3D%20%220.16.2%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20return%20(mo%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%20Classification%20and%20Regression%20Trees%20(CART)%3A%20Interactive%20Demonstration%0A%20%20%20%20%20%20%20%20%23%23%20Understanding%20Tree%20Growth%20and%20Cost-Complexity%20Pruning%0A%0A%20%20%20%20%20%20%20%20Welcome%20to%20this%20interactive%20exploration%20of%20**Classification%20and%20Regression%20Trees%20(CART)**!%20This%20notebook%20demonstrates%20how%20decision%20trees%20grow%20in%20complexity%20and%20how%20**Cost-Complexity%20Pruning**%20helps%20control%20overfitting.%0A%0A%20%20%20%20%20%20%20%20%23%23%20What%20are%20Classification%20Trees%3F%0A%0A%20%20%20%20%20%20%20%20Decision%20trees%20are%20non-parametric%20supervised%20learning%20methods%20that%20recursively%20partition%20the%20feature%20space%20into%20regions%20based%20on%20simple%20decision%20rules.%20Unlike%20linear%20models%20that%20assume%20global%20functional%20forms%2C%20trees%20construct%20piecewise%20constant%20approximations%20to%20capture%20local%20patterns.%0A%0A%20%20%20%20%20%20%20%20**%F0%9F%8E%AF%20The%20Core%20Concept%3A**%0A%0A%20%20%20%20%20%20%20%20-%20Recursively%20split%20the%20feature%20space%20based%20on%20feature%20thresholds%0A%20%20%20%20%20%20%20%20-%20Each%20split%20maximises%20information%20gain%20(minimises%20impurity)%0A%20%20%20%20%20%20%20%20-%20Terminal%20nodes%20(leaves)%20make%20class%20predictions%0A%20%20%20%20%20%20%20%20-%20Tree%20depth%20controls%20model%20complexity%0A%0A%20%20%20%20%20%20%20%20**%F0%9F%93%8A%20Mathematical%20Foundation%3A**%0A%0A%20%20%20%20%20%20%20%20**Gini%20Impurity**%20(for%20classification)%3A%0A%20%20%20%20%20%20%20%20%24%24%5Ctext%7BGini%7D(t)%20%3D%201%20-%20%5Csum_%7Bi%3D1%7D%5EC%20p_i%5E2%24%24%0A%0A%20%20%20%20%20%20%20%20where%20%24p_i%24%20is%20the%20proportion%20of%20class%20%24i%24%20in%20node%20%24t%24.%0A%0A%20%20%20%20%20%20%20%20**Cost-Complexity%20Pruning%3A**%0A%20%20%20%20%20%20%20%20%24%24R_%5Calpha(T)%20%3D%20R(T)%20%2B%20%5Calpha%20%7CT%7C%24%24%0A%0A%20%20%20%20%20%20%20%20where%3A%0A%20%20%20%20%20%20%20%20-%20%24R(T)%24%20is%20the%20misclassification%20rate%0A%20%20%20%20%20%20%20%20-%20%24%7CT%7C%24%20is%20the%20number%20of%20terminal%20nodes%20(complexity)%0A%20%20%20%20%20%20%20%20-%20%24%5Calpha%20%5Cgeq%200%24%20is%20the%20complexity%20parameter%20(pruning%20strength)%0A%0A%20%20%20%20%20%20%20%20**%F0%9F%94%A7%20Key%20Features%3A**%0A%0A%20%20%20%20%20%20%20%20-%20**Max%20Depth**%3A%20Controls%20how%20deep%20the%20tree%20can%20grow%20(complexity)%0A%20%20%20%20%20%20%20%20-%20**Pruning%20%24%5Calpha%24**%3A%20Trades%20off%20accuracy%20for%20simplicity%20by%20removing%20weak%20branches%0A%20%20%20%20%20%20%20%20-%20**Decision%20Boundary**%3A%20Non-linear%20boundaries%20that%20adapt%20to%20data%20structure%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20%23%20Import%20required%20libraries%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20plotly.graph_objects%20as%20go%0A%20%20%20%20from%20plotly.subplots%20import%20make_subplots%0A%20%20%20%20from%20sklearn.datasets%20import%20make_moons%0A%20%20%20%20from%20sklearn.tree%20import%20DecisionTreeClassifier%2C%20export_text%0A%20%20%20%20from%20sklearn.model_selection%20import%20train_test_split%0A%20%20%20%20from%20sklearn.metrics%20import%20accuracy_score%0A%20%20%20%20import%20pandas%20as%20pd%0A%0A%20%20%20%20%23%20Set%20random%20seed%20for%20reproducibility%0A%20%20%20%20np.random.seed(2025)%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20DecisionTreeClassifier%2C%0A%20%20%20%20%20%20%20%20accuracy_score%2C%0A%20%20%20%20%20%20%20%20export_text%2C%0A%20%20%20%20%20%20%20%20go%2C%0A%20%20%20%20%20%20%20%20make_moons%2C%0A%20%20%20%20%20%20%20%20np%2C%0A%20%20%20%20%20%20%20%20train_test_split%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Sample%20Dataset%20Generation%0A%0A%20%20%20%20%20%20%20%20We'll%20use%20a%20**two-moons**%20synthetic%20dataset%2C%20which%20is%20ideal%20for%20demonstrating%20non-linear%20decision%20boundaries.%20This%20dataset%20has%20two%20interleaving%20half-circles%2C%20making%20it%20a%20classic%20test%20case%20for%20non-linear%20classifiers.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(make_moons%2C%20train_test_split)%3A%0A%20%20%20%20%23%20Generate%20synthetic%20two-moons%20dataset%0A%20%20%20%20_X_full%2C%20_y_full%20%3D%20make_moons(n_samples%3D300%2C%20noise%3D0.25%2C%20random_state%3D2025)%0A%0A%20%20%20%20%23%20Split%20into%20train%20(70%25)%20and%20test%20(30%25)%20sets%0A%20%20%20%20X_train%2C%20X_test%2C%20y_train%2C%20y_test%20%3D%20train_test_split(%0A%20%20%20%20%20%20%20%20_X_full%2C%20_y_full%2C%20test_size%3D0.3%2C%20random_state%3D2025%2C%20stratify%3D_y_full%0A%20%20%20%20)%0A%20%20%20%20return%20X_test%2C%20X_train%2C%20y_test%2C%20y_train%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Interactive%20Controls%0A%0A%20%20%20%20%20%20%20%20Adjust%20the%20parameters%20below%20to%20explore%20how%20tree%20complexity%20and%20pruning%20affect%20model%20behaviour%3A%0A%0A%20%20%20%20%20%20%20%20**Max%20Depth%3A**%20Controls%20how%20deep%20the%20tree%20can%20grow.%20Deeper%20trees%20capture%20more%20complex%20patterns%20but%20risk%20overfitting.%0A%0A%20%20%20%20%20%20%20%20**Pruning%20Parameter%20(%24%5Calpha%24)%3A**%20Controls%20cost-complexity%20pruning.%20Higher%20%24%5Calpha%24%20values%20produce%20simpler%20trees%20by%20removing%20weak%20branches%20that%20don't%20sufficiently%20improve%20accuracy.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20%23%20Interactive%20control%20for%20tree%20growth%20(horizontal)%0A%20%20%20%20max_depth_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D1%2C%20stop%3D10%2C%20step%3D1%2C%20value%3D5%2C%0A%20%20%20%20%20%20%20%20label%3D%22Maximum%20Tree%20Depth%3A%22%0A%20%20%20%20)%0A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20**Tree%20Growth%20Control%3A**%0A%20%20%20%20%7Bmax_depth_slider%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%20(max_depth_slider%2C)%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Tree%20Structure%20Visualisation%0A%0A%20%20%20%20%20%20%20%20The%20diagram%20shows%20the%20current%20tree%20structure.%20When%20%CE%B1%20%3D%200%2C%20you%20see%20the%20full%20unpruned%20tree.%20As%20you%20increase%20%CE%B1%2C%20weak%20branches%20are%20removed.%0A%0A%20%20%20%20%20%20%20%20**%F0%9F%92%A1%20Controls%3A**%0A%0A%20%20%20%20%20%20%20%20-%20Use%20the%20vertical%20%CE%B1%20slider%20(left)%20to%20interactively%20prune%20the%20tree%0A%20%20%20%20%20%20%20%20-%20Use%20browser%20zoom%20(Ctrl%2FCmd%20%2B%20scroll%20or%20%2B%2F-)%20to%20zoom%20the%20diagram%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20%23%20Vertical%20slider%20for%20pruning%20control%0A%20%20%20%20ccp_alpha_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0.0%2C%20stop%3D0.1%2C%20step%3D0.005%2C%20value%3D0.0%2C%0A%20%20%20%20%20%20%20%20label%3D%22Pruning%20%CE%B1%3A%22%2C%0A%20%20%20%20%20%20%20%20orientation%3D%22vertical%22%0A%20%20%20%20)%0A%20%20%20%20return%20(ccp_alpha_slider%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20DecisionTreeClassifier%2C%0A%20%20%20%20X_train%2C%0A%20%20%20%20ccp_alpha_slider%2C%0A%20%20%20%20export_text%2C%0A%20%20%20%20max_depth_slider%2C%0A%20%20%20%20np%2C%0A%20%20%20%20y_train%2C%0A)%3A%0A%20%20%20%20%23%20Build%20the%20tree%20with%20current%20max_depth%20and%20ccp_alpha%20settings%0A%20%20%20%20current_tree%20%3D%20DecisionTreeClassifier(%0A%20%20%20%20%20%20%20%20max_depth%3Dmax_depth_slider.value%2C%0A%20%20%20%20%20%20%20%20ccp_alpha%3Dccp_alpha_slider.value%2C%0A%20%20%20%20%20%20%20%20random_state%3D2025%2C%0A%20%20%20%20%20%20%20%20criterion%3D'gini'%2C%0A%20%20%20%20%20%20%20%20min_impurity_decrease%3D0.0001%2C%20%20%23%20Prevent%20splits%20with%20negligible%20improvement%0A%20%20%20%20%20%20%20%20min_samples_split%3D5%2C%20%20%20%20%20%20%20%20%20%20%20%20%23%20Require%20at%20least%205%20samples%20to%20split%0A%20%20%20%20%20%20%20%20min_samples_leaf%3D2%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Require%20at%20least%202%20samples%20in%20each%20leaf%0A%20%20%20%20)%0A%20%20%20%20current_tree.fit(X_train%2C%20y_train)%0A%0A%20%20%20%20%23%20Tree%20to%20Mermaid%20conversion%20function%0A%20%20%20%20def%20tree_to_mermaid(tree%2C%20feature_names%3DNone)%3A%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20Convert%20sklearn%20DecisionTreeClassifier%20to%20Mermaid.js%20graph%20syntax.%0A%0A%20%20%20%20%20%20%20%20Args%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20tree%3A%20Fitted%20DecisionTreeClassifier%0A%20%20%20%20%20%20%20%20%20%20%20%20feature_names%3A%20Optional%20list%20of%20feature%20names%0A%0A%20%20%20%20%20%20%20%20Returns%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20String%20containing%20Mermaid.js%20graph%20definition%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20%20%20%20%20_tree%20%3D%20tree.tree_%0A%20%20%20%20%20%20%20%20if%20feature_names%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20feature_names%20%3D%20%5Bf%22X%5B%7B_i%7D%5D%22%20for%20_i%20in%20range(_tree.n_features)%5D%0A%0A%20%20%20%20%20%20%20%20_lines%20%3D%20%5B%22graph%20TD%3B%22%5D%0A%0A%20%20%20%20%20%20%20%20def%20_recurse(node_id%2C%20depth%3D0)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%22Recursively%20build%20Mermaid%20nodes%20and%20edges.%22%22%22%0A%20%20%20%20%20%20%20%20%20%20%20%20_indent%20%3D%20%22%20%20%20%20%22%20*%20depth%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Check%20if%20terminal%20node%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_tree.feature%5Bnode_id%5D%20%3D%3D%20-2%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%23%20Terminal%20node%20-%20show%20class%20prediction%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_class_counts%20%3D%20_tree.value%5Bnode_id%5D%5B0%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_predicted_class%20%3D%20int(np.argmax(_class_counts))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_gini%20%3D%20_tree.impurity%5Bnode_id%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_samples%20%3D%20int(_tree.n_node_samples%5Bnode_id%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_lines.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f'%7B_indent%7Dnode%7Bnode_id%7D%5B%22Class%20%7B_predicted_class%7D%3Cbr%2F%3EGini%3A%20%7B_gini%3A.3f%7D%3Cbr%2F%3ESamples%3A%20%7B_samples%7D%22%5D'%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20return%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Internal%20node%20-%20show%20split%20condition%0A%20%20%20%20%20%20%20%20%20%20%20%20_feature_idx%20%3D%20_tree.feature%5Bnode_id%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_threshold%20%3D%20_tree.threshold%5Bnode_id%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_gini%20%3D%20_tree.impurity%5Bnode_id%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_samples%20%3D%20int(_tree.n_node_samples%5Bnode_id%5D)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20_lines.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f'%7B_indent%7Dnode%7Bnode_id%7D%5B%22%7Bfeature_names%5B_feature_idx%5D%7D%20%E2%89%A4%20%7B_threshold%3A.3f%7D%3Cbr%2F%3EGini%3A%20%7B_gini%3A.3f%7D%3Cbr%2F%3ESamples%3A%20%7B_samples%7D%22%5D'%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Get%20children%0A%20%20%20%20%20%20%20%20%20%20%20%20_left_child%20%3D%20_tree.children_left%5Bnode_id%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_right_child%20%3D%20_tree.children_right%5Bnode_id%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Add%20edges%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_left_child%20!%3D%20-1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_lines.append(f'%7B_indent%7Dnode%7Bnode_id%7D%20--%3E%7CTrue%7C%20node%7B_left_child%7D')%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_recurse(_left_child%2C%20depth%20%2B%201)%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_right_child%20!%3D%20-1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_lines.append(f'%7B_indent%7Dnode%7Bnode_id%7D%20--%3E%7CFalse%7C%20node%7B_right_child%7D')%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_recurse(_right_child%2C%20depth%20%2B%201)%0A%0A%20%20%20%20%20%20%20%20_recurse(0)%0A%20%20%20%20%20%20%20%20return%20%22%5Cn%22.join(_lines)%0A%0A%20%20%20%20%23%20Generate%20Mermaid%20diagram%0A%20%20%20%20current_tree_mermaid%20%3D%20tree_to_mermaid(current_tree)%0A%0A%20%20%20%20%23%20Also%20generate%20text%20representation%20for%20WASM%20compatibility%0A%20%20%20%20current_tree_text%20%3D%20export_text(current_tree%2C%20feature_names%3D%5B%22X%5B0%5D%22%2C%20%22X%5B1%5D%22%5D)%0A%20%20%20%20return%20current_tree%2C%20current_tree_mermaid%2C%20current_tree_text%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20X_test%2C%0A%20%20%20%20X_train%2C%0A%20%20%20%20accuracy_score%2C%0A%20%20%20%20ccp_alpha_slider%2C%0A%20%20%20%20current_tree%2C%0A%20%20%20%20current_tree_mermaid%2C%0A%20%20%20%20current_tree_text%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20y_test%2C%0A%20%20%20%20y_train%2C%0A)%3A%0A%20%20%20%20import%20sys%0A%0A%20%20%20%20%23%20Calculate%20metrics%20for%20current%20tree%0A%20%20%20%20_train_acc%20%3D%20accuracy_score(y_train%2C%20current_tree.predict(X_train))%0A%20%20%20%20_test_acc%20%3D%20accuracy_score(y_test%2C%20current_tree.predict(X_test))%0A%20%20%20%20_n_nodes%20%3D%20current_tree.tree_.node_count%0A%0A%20%20%20%20%23%20Detect%20if%20running%20in%20WASM%20environment%20(Pyodide)%0A%20%20%20%20_is_wasm%20%3D%20'pyodide'%20in%20sys.modules%20or%20'emscripten'%20in%20sys.modules%0A%0A%20%20%20%20if%20_is_wasm%3A%0A%20%20%20%20%20%20%20%20%23%20Use%20text%20representation%20in%20WASM%0A%20%20%20%20%20%20%20%20_tree_viz%20%3D%20mo.md(f%22%22%22**Text-based%20Tree%20(WASM%20mode)%3A**%0A%20%20%20%20%60%60%60%0A%20%20%20%20%7Bcurrent_tree_text%7D%0A%20%20%20%20%60%60%60%22%22%22)%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%23%20Use%20Mermaid%20for%20interactive%20viewing%0A%20%20%20%20%20%20%20%20_tree_viz%20%3D%20mo.mermaid(current_tree_mermaid)%0A%0A%20%20%20%20%23%20Create%20the%20tree%20diagram%20with%20metrics%0A%20%20%20%20_tree_content%20%3D%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20_tree_viz%2C%0A%20%20%20%20%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20%20%20%20%20**Current%20Tree%20Metrics%3A**%0A%20%20%20%20%20%20%20%20Training%20Accuracy%3A%20%7B_train_acc%3A.3f%7D%20%7C%20Test%20Accuracy%3A%20%7B_test_acc%3A.3f%7D%20%7C%20Nodes%3A%20%7B_n_nodes%7D%20%7C%20%CE%B1%3A%20%7Bccp_alpha_slider.value%3A.3f%7D%20%7B'**(Unpruned)**'%20if%20ccp_alpha_slider.value%20%3D%3D%200.0%20else%20'**(Pruned)**'%7D%0A%20%20%20%20%20%20%20%20%22%22%22)%0A%20%20%20%20%5D%2C%20gap%3D0.5)%0A%0A%20%20%20%20%23%20Display%20vertical%20slider%20next%20to%20tree%20with%20minimal%20gap%0A%20%20%20%20mo.hstack(%5B%0A%20%20%20%20%20%20%20%20ccp_alpha_slider%2C%0A%20%20%20%20%20%20%20%20_tree_content%0A%20%20%20%20%5D%2C%20justify%3D%22start%22%2C%20gap%3D1)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Decision%20Boundary%20Visualisation%0A%0A%20%20%20%20%20%20%20%20The%20plot%20below%20shows%20how%20the%20pruned%20tree%20partitions%20the%202D%20feature%20space.%20Training%20points%20are%20shown%20with%20filled%20markers%2C%20whilst%20test%20points%20use%20hollow%20markers.%20The%20background%20colour%20represents%20the%20predicted%20class%20in%20each%20region.%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(X_test%2C%20X_train%2C%20current_tree%2C%20go%2C%20np%2C%20y_test%2C%20y_train)%3A%0A%20%20%20%20%23%20Create%20a%20mesh%20for%20decision%20boundary%20visualisation%0A%20%20%20%20_x_min%2C%20_x_max%20%3D%20X_train%5B%3A%2C%200%5D.min()%20-%200.5%2C%20X_train%5B%3A%2C%200%5D.max()%20%2B%200.5%0A%20%20%20%20_y_min%2C%20_y_max%20%3D%20X_train%5B%3A%2C%201%5D.min()%20-%200.5%2C%20X_train%5B%3A%2C%201%5D.max()%20%2B%200.5%0A%20%20%20%20_xx%2C%20_yy%20%3D%20np.meshgrid(%0A%20%20%20%20%20%20%20%20np.linspace(_x_min%2C%20_x_max%2C%20200)%2C%0A%20%20%20%20%20%20%20%20np.linspace(_y_min%2C%20_y_max%2C%20200)%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Predict%20on%20the%20mesh%20using%20current%20tree%0A%20%20%20%20_Z%20%3D%20current_tree.predict(np.c_%5B_xx.ravel()%2C%20_yy.ravel()%5D)%0A%20%20%20%20_Z%20%3D%20_Z.reshape(_xx.shape)%0A%0A%20%20%20%20%23%20Create%20decision%20boundary%20plot%0A%20%20%20%20decision_boundary_fig%20%3D%20go.Figure()%0A%0A%20%20%20%20%23%20Add%20decision%20boundary%20as%20contour%0A%20%20%20%20decision_boundary_fig.add_trace(go.Contour(%0A%20%20%20%20%20%20%20%20x%3Dnp.linspace(_x_min%2C%20_x_max%2C%20200)%2C%0A%20%20%20%20%20%20%20%20y%3Dnp.linspace(_y_min%2C%20_y_max%2C%20200)%2C%0A%20%20%20%20%20%20%20%20z%3D_Z%2C%0A%20%20%20%20%20%20%20%20colorscale%3D%5B%5B0%2C%20'rgba(31%2C119%2C180%2C0.3)'%5D%2C%20%5B1%2C%20'rgba(255%2C127%2C14%2C0.3)'%5D%5D%2C%0A%20%20%20%20%20%20%20%20showscale%3DFalse%2C%0A%20%20%20%20%20%20%20%20hoverinfo%3D'skip'%2C%0A%20%20%20%20%20%20%20%20contours%3Ddict(%0A%20%20%20%20%20%20%20%20%20%20%20%20coloring%3D'heatmap'%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20showlabels%3DFalse%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20))%0A%0A%20%20%20%20%23%20Add%20training%20data%0A%20%20%20%20for%20_class_idx%20in%20%5B0%2C%201%5D%3A%0A%20%20%20%20%20%20%20%20_mask%20%3D%20y_train%20%3D%3D%20_class_idx%0A%20%20%20%20%20%20%20%20decision_boundary_fig.add_trace(go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3DX_train%5B_mask%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3DX_train%5B_mask%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D'markers'%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20size%3D8%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D'blue'%20if%20_class_idx%20%3D%3D%200%20else%20'orange'%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20symbol%3D'circle'%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(width%3D1%2C%20color%3D'darkblue'%20if%20_class_idx%20%3D%3D%200%20else%20'darkorange')%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3Df'Class%20%7B_class_idx%7D%20(Train)'%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20hovertemplate%3Df'Class%20%7B_class_idx%7D%20(Train)%3Cbr%3EX1%3A%20%25%7B%7Bx%3A.2f%7D%7D%3Cbr%3EX2%3A%20%25%7B%7By%3A.2f%7D%7D%3Cextra%3E%3C%2Fextra%3E'%0A%20%20%20%20%20%20%20%20))%0A%0A%20%20%20%20%23%20Add%20test%20data%0A%20%20%20%20for%20_class_idx%20in%20%5B0%2C%201%5D%3A%0A%20%20%20%20%20%20%20%20_mask%20%3D%20y_test%20%3D%3D%20_class_idx%0A%20%20%20%20%20%20%20%20decision_boundary_fig.add_trace(go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3DX_test%5B_mask%2C%200%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3DX_test%5B_mask%2C%201%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D'markers'%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20marker%3Ddict(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20size%3D8%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D'blue'%20if%20_class_idx%20%3D%3D%200%20else%20'orange'%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20symbol%3D'circle-open'%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(width%3D2%2C%20color%3D'darkblue'%20if%20_class_idx%20%3D%3D%200%20else%20'darkorange')%0A%20%20%20%20%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3Df'Class%20%7B_class_idx%7D%20(Test)'%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20hovertemplate%3Df'Class%20%7B_class_idx%7D%20(Test)%3Cbr%3EX1%3A%20%25%7B%7Bx%3A.2f%7D%7D%3Cbr%3EX2%3A%20%25%7B%7By%3A.2f%7D%7D%3Cextra%3E%3C%2Fextra%3E'%0A%20%20%20%20%20%20%20%20))%0A%0A%20%20%20%20decision_boundary_fig.update_layout(%0A%20%20%20%20%20%20%20%20title%3D'Decision%20Boundary%20(Current%20Tree)'%2C%0A%20%20%20%20%20%20%20%20xaxis_title%3D'Feature%201'%2C%0A%20%20%20%20%20%20%20%20yaxis_title%3D'Feature%202'%2C%0A%20%20%20%20%20%20%20%20width%3D800%2C%0A%20%20%20%20%20%20%20%20height%3D600%2C%0A%20%20%20%20%20%20%20%20showlegend%3DTrue%2C%0A%20%20%20%20%20%20%20%20hovermode%3D'closest'%0A%20%20%20%20)%0A%0A%20%20%20%20decision_boundary_fig%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Understanding%20Cost-Complexity%20Pruning%0A%0A%20%20%20%20%20%20%20%20**The%20Pruning%20Trade-off%3A**%0A%0A%20%20%20%20%20%20%20%20Cost-complexity%20pruning%20(also%20called%20weakest-link%20pruning)%20removes%20branches%20that%20provide%20minimal%20improvement%20in%20classification%20accuracy%20relative%20to%20their%20added%20complexity.%0A%0A%20%20%20%20%20%20%20%20**How%20it%20works%3A**%0A%0A%20%20%20%20%20%20%20%201.%20**Grow%20a%20full%20tree**%20to%20the%20specified%20%60max_depth%60%0A%20%20%20%20%20%20%20%202.%20**Calculate%20cost-complexity**%20for%20each%20subtree%3A%20%24R_%5Calpha(T)%20%3D%20R(T)%20%2B%20%5Calpha%20%7CT%7C%24%0A%20%20%20%20%20%20%20%203.%20**Prune%20weakest%20links**%20iteratively%3A%20Remove%20subtrees%20where%20the%20complexity%20cost%20exceeds%20the%20accuracy%20benefit%0A%20%20%20%20%20%20%20%204.%20**Select%20optimal%20%24%5Calpha%24**%20via%20cross-validation%20(or%20manual%20tuning%20as%20demonstrated%20here)%0A%0A%20%20%20%20%20%20%20%20**Key%20Insights%3A**%0A%0A%20%20%20%20%20%20%20%20-%20**%24%5Calpha%20%3D%200%24**%3A%20No%20pruning%20(full%20tree%20up%20to%20max%20depth)%0A%20%20%20%20%20%20%20%20-%20**Small%20%24%5Calpha%24**%3A%20Minimal%20pruning%2C%20removes%20only%20very%20weak%20branches%0A%20%20%20%20%20%20%20%20-%20**Large%20%24%5Calpha%24**%3A%20Aggressive%20pruning%2C%20may%20reduce%20to%20a%20stump%20or%20very%20simple%20tree%0A%20%20%20%20%20%20%20%20-%20**Optimal%20%24%5Calpha%24**%3A%20Balances%20test%20accuracy%20and%20model%20simplicity%0A%0A%20%20%20%20%20%20%20%20**Practical%20Considerations%3A**%0A%0A%20%20%20%20%20%20%20%20-%20**Bias-Variance%20Trade-off**%3A%20Pruning%20increases%20bias%20slightly%20but%20can%20dramatically%20reduce%20variance%0A%20%20%20%20%20%20%20%20-%20**Generalisation**%3A%20Pruned%20trees%20often%20achieve%20better%20test%20accuracy%20despite%20lower%20training%20accuracy%0A%20%20%20%20%20%20%20%20-%20**Interpretability**%3A%20Simpler%20trees%20are%20easier%20to%20explain%20and%20visualise%0A%20%20%20%20%20%20%20%20-%20**Computational%20Efficiency**%3A%20Fewer%20nodes%20means%20faster%20predictions%0A%0A%20%20%20%20%20%20%20%20**%F0%9F%92%A1%20Experiment%3A**%20Try%20adjusting%20both%20sliders%20to%20observe%3A%0A%0A%20%20%20%20%20%20%20%20-%20How%20max%20depth%20controls%20initial%20tree%20complexity%0A%20%20%20%20%20%20%20%20-%20How%20%24%5Calpha%24%20removes%20weak%20branches%20from%20the%20grown%20tree%0A%20%20%20%20%20%20%20%20-%20The%20effect%20on%20training%20vs.%20test%20accuracy%20(watch%20for%20overfitting!)%0A%20%20%20%20%20%20%20%20-%20Changes%20in%20decision%20boundary%20smoothness%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%0A%20%20%20%20%20%20%20%20r%22%22%22%0A%20%20%20%20%20%20%20%20%23%23%20Summary%20and%20Key%20Takeaways%0A%0A%20%20%20%20%20%20%20%20**Classification%20Trees%20(CART)%3A**%0A%0A%20%20%20%20%20%20%20%20-%20Partition%20feature%20space%20recursively%20using%20simple%20threshold%20rules%0A%20%20%20%20%20%20%20%20-%20Use%20impurity%20measures%20(Gini%20index)%20to%20determine%20optimal%20splits%0A%20%20%20%20%20%20%20%20-%20Flexible%20non-linear%20decision%20boundaries%0A%0A%20%20%20%20%20%20%20%20**Tree%20Growth%20(Max%20Depth)%3A**%0A%0A%20%20%20%20%20%20%20%20-%20Controls%20model%20complexity%20directly%0A%20%20%20%20%20%20%20%20-%20Deeper%20trees%20capture%20more%20intricate%20patterns%20but%20risk%20overfitting%0A%20%20%20%20%20%20%20%20-%20Limited%20depth%20acts%20as%20a%20form%20of%20regularisation%0A%0A%20%20%20%20%20%20%20%20**Cost-Complexity%20Pruning%20(%24%5Calpha%24)%3A**%0A%0A%20%20%20%20%20%20%20%20-%20Post-hoc%20regularisation%20technique%0A%20%20%20%20%20%20%20%20-%20Removes%20branches%20with%20poor%20cost-benefit%20ratio%0A%20%20%20%20%20%20%20%20-%20Often%20improves%20generalisation%20by%20reducing%20overfitting%0A%20%20%20%20%20%20%20%20-%20Produces%20more%20interpretable%20models%0A%0A%20%20%20%20%20%20%20%20**Best%20Practices%3A**%0A%0A%20%20%20%20%20%20%20%20-%20Use%20proper%20train%2Ftest%20splits%20for%20unbiased%20evaluation%0A%20%20%20%20%20%20%20%20-%20Monitor%20both%20training%20and%20test%20accuracy%20(gap%20indicates%20overfitting)%0A%20%20%20%20%20%20%20%20-%20Consider%20computational%20cost%3A%20simpler%20trees%20predict%20faster%0A%20%20%20%20%20%20%20%20-%20Tune%20both%20max%20depth%20and%20%24%5Calpha%24%20via%20cross-validation%20for%20optimal%20performance%0A%0A%20%20%20%20%20%20%20%20**Extensions%20and%20Advanced%20Topics%3A**%0A%0A%20%20%20%20%20%20%20%20-%20**Random%20Forests**%3A%20Ensemble%20of%20trees%20with%20feature%20randomness%0A%20%20%20%20%20%20%20%20-%20**Gradient%20Boosting**%3A%20Sequential%20trees%20correcting%20previous%20errors%0A%20%20%20%20%20%20%20%20-%20**Regression%20Trees**%3A%20CART%20applied%20to%20continuous%20outcomes%0A%20%20%20%20%20%20%20%20-%20**Feature%20Importance**%3A%20Quantify%20predictive%20power%20of%20each%20feature%0A%20%20%20%20%20%20%20%20%22%22%22%0A%20%20%20%20)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A