পাঠ ২০ · ৪৫-এর মধ্যে · মডিউল ৩
Home / AI Courses / Machine Learning / CART

CART অ্যালগরিদম

CART — Classification & Regression Trees
৭ মিনিট পড়া মাঝারি · Intermediate NumPy + sklearn

এই পাঠে যা শিখবেন

  • CART-এর binary-only কাঠামো — ID3/C4.5-এর সাথে পার্থক্য
  • Regression tree — variance reduction-এ split বাছা
  • Cost-complexity pruning — $\alpha$ hyperparameter ও CV
  • Surrogate splits — missing values handle
  • sklearn-এর ccp_alpha — practical pruning

১ · CART কেন আলাদা

Decision tree-এর অনেক variant আছে — ID3 (১৯৮৬), C4.5 (১৯৯৩), CARTCARTClassification And Regression Trees — Breiman, Friedman, Olshen, Stone (১৯৮৪)। Binary split, cost-complexity pruning, surrogate splits — তিন signature feature। sklearn-এর default tree algorithm। (১৯৮৪)। CART কয়েকটি কারণে dominant:

  • Binary only: "yes/no" branches। Multi-way split (ID3 categorical-এ যেটা করত) নেই।
  • Both tasks: classification ও regression — একই framework।
  • Numerical & categorical: দু'রকম feature handle।
  • Missing data: surrogate splits — drop করতে হয় না।
  • Cost-complexity pruning: theoretically grounded post-pruning।
কেন binary?

Multi-way splits-এ "category-এর সংখ্যা যত বেশি, gain তত বেশি" — biased। Binary split — feature-কে সঠিক ব্যবহার করতে বাধ্য। Numerical features-এর জন্য — threshold-এ split natural। Categorical-এ — best subset খুঁজে binary split। সব data type-এ একই treatment।

২ · Classification CART — রিভিশন

Gini impurity দিয়ে split বাছাই — পূর্ববর্তী পাঠে। Recursive binary partitioning। প্রতিটি split-এ:

$$\Delta i(s, t) = i(t) - p_L \cdot i(t_L) - p_R \cdot i(t_R)$$

$i(t)$ — Gini, $p_L, p_R$ — left/right child fraction। সর্বোচ্চ $\Delta i$-এর split।

৩ · Regression CART — variance কমানো

Target continuous (যেমন বাড়ির দাম)। Impurity-র জায়গায় varianceVarianceRegression-এ impurity-র analog। একটি node-এ targets-এর spread। Split-এর পর variance কমানো → Information Gain-এর regression analog।:

$$V(t) = \frac{1}{|t|} \sum_{i \in t} (y_i - \bar{y}_t)^2$$

প্রতিটি leaf-এ prediction = সেই leaf-এর mean target। Split-এ variance reduction maximize।

Equivalently: MSE minimize। কারণ leaf prediction = mean → squared error = variance × |t|।

৪ · Cost-Complexity Pruning

Pre-pruning (depth limit) coarse। Better — full tree বানিয়ে subtrees prune। কিন্তু কোনগুলো? CART-এর elegant solution:

$$R_\alpha(T) = R(T) + \alpha \cdot |T|$$

  • $R(T)$ — tree-এর misclassification (বা MSE)।
  • $|T|$ — leaf-এর সংখ্যা (complexity)।
  • $\alpha \ge 0$ — penalty parameter।

$\alpha = 0$ → full tree। $\alpha$ বাড়ালে — ছোট tree। প্রতিটি $\alpha$-এ optimal subtree আছে — Breiman দেখিয়েছেন এটি unique ও nested।

৫ · Pruning algorithm

  1. Full tree $T_{\max}$ বানান।
  2. প্রতিটি internal node-এ "weakest link" calculate — কোন subtree-কে prune করলে $R/|T|$ ratio সবচেয়ে কম বাড়ে।
  3. সেই subtree-কে leaf-এ replace।
  4. ২-৩ পুনরাবৃত্তি — root-এ পৌঁছানো পর্যন্ত।
  5. প্রতি step-এ একটি $\alpha$ ও subtree রেকর্ড — sequence $T_0 \supset T_1 \supset \ldots \supset T_K$।
  6. Cross-validation-এ best $\alpha$ বাছুন।

এর সুবিধা — শুধু $K$টি candidate tree (exponential possibilities নয়)। Computationally feasible।

৬ · Surrogate Splits — missing data

বাস্তব dataset-এ missing values সাধারণ। অনেক algorithm — drop করে বা impute। CART-এর elegance:

  • প্রতিটি split-এ — primary feature (best split) ছাড়াও surrogate splitsSurrogate SplitPrimary split-এর "imitator" — অন্য feature যা একই partitioning করে। Primary feature missing হলে — best surrogate ব্যবহার। CART-এর missing-data robustness-এর source। খোঁজা হয়।
  • Surrogate = অন্য একটি feature যা primary split-এর সাথে highly agreeing।
  • Test-এ primary value missing → surrogate ব্যবহার।
  • সব surrogate missing → majority direction।

Note: sklearn 1.4+-এ missing_values handling আছে; classical CART surrogate fully implement scikit-learn-এ নেই (R-এর rpart-এ আছে)। Concept তবু important।

CART — grow then prune ১. Full Tree (T_max) α = 0 — overfit |T| = 7 leaves R(T) = 0.02 train CV error 0.18 ২. Pruning sequence α grows → tree shrinks α=0.00 → |T|=7 α=0.02 → |T|=5 α=0.05 → |T|=3 ★ α=0.10 → |T|=2 α=0.20 → |T|=1 Cross-validation CV picks α=0.05 CV error 0.10 ৩. Pruned Tree balanced — generalizes |T| = 3 leaves R(T) = 0.08 train CV error 0.10
CART পদ্ধতি — full tree → cost-complexity sequence → CV-নির্বাচিত pruned tree। Generalization ও interpretability দু'টোই better।

৭ · NumPy দিয়ে — Regression CART

Variance-based regression tree — ছোট, কিন্তু সম্পূর্ণ working।

Python · NumPy 
import numpy as np

def variance(y):
    return np.var(y) if len(y) > 0 else 0

def best_reg_split(X, y):
    n, d = X.shape
    best_red, best_feat, best_thr = 0, None, None
    parent_v = variance(y)
    for f in range(d):
        for t in np.unique(X[:, f]):
            mask = X[:, f] <= t
            yL, yR = y[mask], y[~mask]
            if len(yL) == 0 or len(yR) == 0:
                continue
            v = (len(yL)*variance(yL) + len(yR)*variance(yR)) / n
            red = parent_v - v
            if red > best_red:
                best_red, best_feat, best_thr = red, f, t
    return best_feat, best_thr, best_red

class RegNode:
    def __init__(self, val=None, feat=None, thr=None, L=None, R=None):
        self.val, self.feat, self.thr, self.L, self.R = val, feat, thr, L, R

def build_reg_tree(X, y, depth=0, max_depth=4, min_n=5):
    if depth >= max_depth or len(y) < min_n:
        return RegNode(val=y.mean())
    f, t, r = best_reg_split(X, y)
    if f is None or r < 1e-6:
        return RegNode(val=y.mean())
    m = X[:, f] <= t
    return RegNode(feat=f, thr=t,
                   L=build_reg_tree(X[m],  y[m],  depth+1, max_depth, min_n),
                   R=build_reg_tree(X[~m], y[~m], depth+1, max_depth, min_n))

def predict_reg(node, x):
    if node.val is not None:
        return node.val
    return predict_reg(node.L if x[node.feat] <= node.thr else node.R, x)

# Test on synthetic regression data
np.random.seed(0)
X = np.random.rand(200, 1) * 10
y = np.sin(X[:, 0]) + 0.1 * np.random.randn(200)

tree = build_reg_tree(X, y, max_depth=4)
preds = np.array([predict_reg(tree, x) for x in X])
mse = np.mean((preds - y)**2)
print(f"Train MSE: {mse:.4f}")

    


    

      Tree sin(x) curve-কে step-function-এ approximate। depth বাড়ালে fit improve, কিন্তু overfitting risk-ও বাড়ে।
    


    
৮ · sklearn — cost-complexity pruning


    

      

        
        Python · scikit-learn
      

      
from sklearn.datasets import load_breast_cancer
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

X, y = load_breast_cancer(return_X_y=True)
Xt, Xv, yt, yv = train_test_split(X, y, test_size=0.3, random_state=0)

# 1) Full tree, pruning path
clf = DecisionTreeClassifier(random_state=0).fit(Xt, yt)
path = clf.cost_complexity_pruning_path(Xt, yt)
alphas = path.ccp_alphas

# 2) Try each alpha
scores = []
for a in alphas:
    m = DecisionTreeClassifier(ccp_alpha=a, random_state=0).fit(Xt, yt)
    scores.append((a, m.tree_.node_count, m.score(Xv, yv)))

# 3) Best alpha
best = max(scores, key=lambda r: r[2])
print(f"Best α={best[0]:.4f}, nodes={best[1]}, val acc={best[2]:.4f}")

      

        
        
      

      

    


    

      ccp_alpha CART-এর cost-complexity parameter। সাধারণত validation accuracy maximize করার $\alpha$ বাছেন। Tree size বহু কমে — interpretability জাগে।
    


    
৯ · CART vs C4.5 — সংক্ষেপে


    
    
      
  • Splits: CART binary; C4.5 multi-way (categorical)।
    • 
      
  • Criterion: CART Gini/MSE; C4.5 gain ratio (entropy-based)।
    • 
      
  • Pruning: CART cost-complexity; C4.5 error-based।
    • 
      
  • Missing: CART surrogate; C4.5 distribute-fractional।
    • 
      
  • Tasks: CART both; C4.5 শুধু classification।
    • 
      
  • Adoption: CART → sklearn, R rpart; C4.5 → academic, J48 (Weka)।
    • 
    


    

      sklearn-এ "DecisionTreeClassifier" CART-এর variant — কিন্তু classical CART-এর সব feature নেই (যেমন pure surrogate split)। Practical research / production-এ এই পার্থক্য নগণ্য — কারণ ensemble-এ tree blend হয়।
    


  


  

    
    
  


  

    
 ভাবনার প্রশ্ন

    
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।


    

      
        প্র ০১
        Cost-complexity pruning গাণিতিকভাবে কেন "elegant" — অন্য pruning পদ্ধতির চেয়ে ভাল কেন?
      
      

        

          Breiman-এর insight (১৯৮৪) — pruning-কে regularized objective হিসেবে formulate করা।
        

        

          Cost-complexity formulation:
        

        

          $$R_\alpha(T) = R(T) + \alpha |T|$$
        

        
    
          
  • Lasso-এর সাথে সাদৃশ্য — penalty + fit।
    • 
          
  • $\alpha$ continuous knob — full search avoided।
    • 
          
  • $\alpha = 0$ — no penalty; $\alpha \to \infty$ — root only।
    • 
        

        

          Theorem (Breiman):
        

        
    
          
  • প্রতিটি $\alpha$-এ — unique smallest optimal subtree $T(\alpha)$।
    • 
          
  • $\alpha$ বাড়ালে — $T(\alpha)$ nested decreasing।
    • 
          
  • মাত্র $K$ distinct subtree (full tree-র leaves-এর সংখ্যার সমান)।
    • 
          
  • Cross-validation simple এই $K$-এ search।
    • 
        

        

          অন্য pruning approach:
        

        

          (১) Reduced Error Pruning (Quinlan):
        

        
    
          
  • Validation set-এ subtree replace করে test।
    • 
          
  • Improvement হলে keep, না হলে revert।
    • 
          
  • Greedy — global optimal nয়।
    • 
          
  • Validation set প্রয়োজন।
    • 
        

        

          (২) Pessimistic Pruning (C4.5):
        

        
    
          
  • Training error-এ statistical correction।
    • 
          
  • Confidence interval upper bound prune-এর criterion।
    • 
          
  • No validation set, কিন্তু heuristic।
    • 
        

        

          (৩) Minimum Description Length (MDL):
        

        
    
          
  • Information-theoretic — tree encoding cost + error encoding cost।
    • 
          
  • Theoretically appealing।
    • 
          
  • Practical impact moderate।
    • 
        

        

          CART-এর সুবিধা:
        

        
    
          
  • Computational: $K$ candidates মাত্র — full search avoided।
    • 
          
  • Theoretical: nested sequence — monotonic complexity।
    • 
          
  • Practical: CV সরাসরি apply।
    • 
          
  • Generalizable: classification ও regression — same framework।
    • 
        

        

          Connection to modern regularization:
        

        
    
          
  • $\alpha |T|$ — L0 penalty (count of leaves)।
    • 
          
  • Lasso-এর $\lambda \|w\|_1$ analog।
    • 
          
  • Modern XGBoost: $\gamma T + \frac{\lambda}{2} \|w\|^2$ — extension।
    • 
          
  • Regularization continuum।
    • 
        

        

          Limitations:
        

        
    
          
  • Greedy growing — global optimal tree NP-hard।
    • 
          
  • $\alpha$-tuning expensive (CV)।
    • 
          
  • Single tree still high variance।
    • 
          
  • Modern ensemble (RF, XGB) এই সব সমস্যা bypass।
    • 
        

        

          মূল উপলব্ধি: Cost-complexity Breiman-এর genius — bridging classical statistics ও modern ML। আজকের sklearn ccp_alpha direct legacy।
        

      

    


    

      
        প্র ০২
        Regression tree — predicted value piecewise constant। Smooth function (যেমন বাড়ির দাম এলাকা-অনুযায়ী) কীভাবে এটা handle করে? Linear regression vs tree — কখন কোনটি better?
      
      

        

          Regression tree — tabular data world-এ unsung hero। Linear model-এর সাথে তুলনা করলে characteristics স্পষ্ট হয়।
        

        

          Tree-এর piecewise constant nature:
        

        
    
          
  • প্রতিটি leaf — একটি constant prediction (mean target)।
    • 
          
  • Feature space rectangular regions-এ partition।
    • 
          
  • Within region — সব points-এ same prediction।
    • 
        

        

          Smooth function approximation:
        

        
    
          
  • Step function ladder দিয়ে।
    • 
          
  • সঠিক চাইলে — অনেক leaves।
    • 
          
  • Approximation error decay rate $O(1/\sqrt{n})$।
    • 
          
  • Exact match achievable (depth → infinity)।
    • 
        

        

          উদাহরণ — sin(x):
        

        
    
          
  • depth=2 — ৪টি step, crude।
    • 
          
  • depth=5 — ৩২টি step, recognizable।
    • 
          
  • depth=10 — smooth-এর কাছাকাছি।
    • 
          
  • কিন্তু overfit risk।
    • 
        

        

          Tree-এর সুবিধা:
        

        
    
          
  • Non-linearity: automatic — feature engineering লাগে না।
    • 
          
  • Interaction: nested splits প্রাকৃতিকভাবে capture।
    • 
          
  • Mixed types: numerical + categorical সহজে।
    • 
          
  • Outlier robust: median-influenced (কিছুটা)।
    • 
          
  • Scale invariant: normalization লাগে না।
    • 
        

        

          Tree-এর সমস্যা:
        

        
    
          
  • Extrapolation দুর্বল: training range-এর বাইরে fixed prediction।
    • 
          
  • Smooth gradients নয়: derivative discontinuous।
    • 
          
  • Overfit prone: small data-এ memorization।
    • 
          
  • Interpolation rough: physics application-এ inadequate।
    • 
        

        

          Linear Regression-এর সুবিধা:
        

        
    
          
  • Smooth: derivative everywhere defined।
    • 
          
  • Extrapolate: outside training range reasonable।
    • 
          
  • Few parameters: overfit-এর সম্ভাবনা কম।
    • 
          
  • Interpretable: coefficients = effect size।
    • 
          
  • Statistical theory: confidence intervals, hypothesis test।
    • 
        

        

          Linear-এর সমস্যা:
        

        
    
          
  • Non-linearity assumption fails — quadratic/exponential miss।
    • 
          
  • Feature interaction manual।
    • 
          
  • Outlier sensitive।
    • 
          
  • Scale matter।
    • 
        

        

          কখন tree better:
        

        
    
          
  • Tabular data (real estate, finance, healthcare records)।
    • 
          
  • Strong interactions।
    • 
          
  • Mixed feature types।
    • 
          
  • Non-linear relationships।
    • 
          
  • Sufficient data (১,০০০+ samples)।
    • 
        

        

          কখন linear better:
        

        
    
          
  • Small data (<১০০ samples)।
    • 
          
  • Linear underlying truth (physics, economics)।
    • 
          
  • Extrapolation দরকার।
    • 
          
  • Hypothesis testing দরকার।
    • 
          
  • Smooth derivative critical।
    • 
        

        

          Real-world: বাড়ির দাম:
        

        
    
          
  • Linear: "প্রতি sqft ৫০০০ টাকা" — interpretable, কিন্তু area-specific premium miss।
    • 
          
  • Tree: "ধানমন্ডি AND new building → ৩০ক/sqft" — interaction captured।
    • 
          
  • Production: XGBoost (tree ensemble) + linear interaction features।
    • 
        

        

          Hybrid approach:
        

        
    
          
  • Tree predict residual after linear fit।
    • 
          
  • Linear smooth, tree non-linear correction।
    • 
          
  • GBM (gradient boosting) — sequential application।
    • 
        

        

          মূল উপলব্ধি: Choice — data structure-নির্ভর। "Better" universal নয়। Tabular real-world data-এ tree ensembles dominate (Kaggle evidence)।
        

      

    


    

      
        প্র ০৩
        Surrogate splits — missing data হ্যান্ডলিং elegant। কিন্তু সমস্যা আছে। কখন surrogate misleading? Modern alternatives কী?
      
      

        

          Missing data — production ML-এর recurring challenge। Surrogate split sound, কিন্তু silver bullet নয়।
        

        

          Surrogate কীভাবে কাজ করে:
        

        
    
          
  • Primary split: income > 50K।
    • 
          
  • Surrogate-1: profession in {high-paying} — যা একই partitioning করে।
    • 
          
  • Surrogate-2: education = master+।
    • 
          
  • Test-এ income missing → surrogate-1 try → missing → surrogate-2 → ...
    • 
          
  • Final fallback — majority direction।
    • 
        

        

          কখন surrogate misleading:
        

        

          (১) Missing not at random (MNAR):
        

        
    
          
  • Income missing — খুব কম বা খুব বেশি income-দের।
    • 
          
  • Surrogate এই pattern capture করে না।
    • 
          
  • Bias amplified।
    • 
        

        

          (২) Surrogate quality variable:
        

        
    
          
  • Best surrogate primary-এর ৭০% agreement (typical)।
    • 
          
  • ৩০% mismatched — accuracy drop।
    • 
          
  • Multiple surrogate fallback — error compound।
    • 
        

        

          (৩) Distributional shift:
        

        
    
          
  • Training-এ surrogate well-suited।
    • 
          
  • Production-এ correlation breakdown।
    • 
          
  • Surrogate degrade silently।
    • 
        

        

          (৪) Critical features missing:
        

        
    
          
  • Surrogate "approximate" only।
    • 
          
  • Decision-critical feature missing → unrecoverable।
    • 
        

        

          Modern alternatives:
        

        

          (১) Missing as separate category:
        

        
    
          
  • NaN-কে own value হিসেবে treat।
    • 
          
  • XGBoost-এর default approach।
    • 
          
  • Tree learn — missing-এর pattern।
    • 
          
  • সবচেয়ে practical।
    • 
        

        

          (২) Multiple Imputation:
        

        
    
          
  • Statistical multiple imputation (Rubin)।
    • 
          
  • Per-variable model fit করে predict।
    • 
          
  • Uncertainty propagation।
    • 
          
  • Computationally expensive।
    • 
        

        

          (৩) Mean/Median/Mode imputation:
        

        
    
          
  • Simple, fast।
    • 
          
  • Variance underestimate।
    • 
          
  • Bias introduce।
    • 
          
  • Baseline।
    • 
        

        

          (৪) KNN imputation:
        

        
    
          
  • Similar samples-এর mean।
    • 
          
  • Better বের, slower।
    • 
          
  • Curse of dimensionality।
    • 
        

        

          (৫) Iterative imputation (MICE):
        

        
    
          
  • প্রতি missing variable অন্য variables দিয়ে predict।
    • 
          
  • Iterate convergence-এ।
    • 
          
  • Statistically principled।
    • 
        

        

          (৬) Deep learning imputation:
        

        
    
          
  • VAE-based, GAIN।
    • 
          
  • Complex pattern learn।
    • 
          
  • Big data দরকার।
    • 
        

        

          XGBoost approach (modern dominant):
        

        
    
          
  • প্রতি split-এ — missing samples best direction shিখে।
    • 
          
  • "Default direction" — গাছ memorize।
    • 
          
  • No imputation, no surrogate, automatic।
    • 
          
  • Practical এবং accurate।
    • 
        

        

          Best practice:
        

        
    
          
  • EDA first: missing pattern বুঝুন।
    • 
          
  • Domain knowledge: missing-এর meaning কী?
    • 
          
  • Missing indicator: additional binary feature।
    • 
          
  • Model choice: XGBoost / LightGBM — native handling।
    • 
          
  • Sensitivity analysis: different strategies-এ result কতটা stable?
    • 
        

        

          Bangladesh context:
        

        
    
          
  • Survey data — incomes underreport।
    • 
          
  • Health data — sparse rural।
    • 
          
  • Mobile data — pattern in missing।
    • 
          
  • Domain expert input critical।
    • 
        

        

          মূল উপলব্ধি: Surrogate split historic gem, modern alternative often better। Missing data — algorithm choice নয়, data understanding-এর প্রশ্ন।
        

      

    


    

      
        প্র ০৪
        আপনি এক হাসপাতালের জন্য রোগ-নির্ণয় tool বানাচ্ছেন। CART কেন এখানে appropriate? Risk কী এবং mitigation strategy কী?
      
      

        

          Healthcare ML — high stakes domain। Algorithm choice কেবল accuracy নয়।
        

        

          CART কেন appropriate:
        

        

          (১) Interpretability:
        

        
    
          
  • "যদি বয়স > ৬০ AND BP > ১৪০ AND chest pain → high risk"।
    • 
          
  • চিকিৎসক বুঝতে পারে — verify করতে পারে।
    • 
          
  • Black-box NN — regulatory ও ethical issue।
    • 
          
  • FDA-এর "explainable AI" guideline-এ সঙ্গতিপূর্ণ।
    • 
        

        

          (২) Mixed feature support:
        

        
    
          
  • Age (numerical), gender (categorical), symptoms (binary), lab results (continuous)।
    • 
          
  • One model — সব handle।
    • 
          
  • Pre-processing minimal।
    • 
        

        

          (৩) Missing data robustness:
        

        
    
          
  • হাসপাতালে অনেক test-এর result missing — patient সব test করেনি।
    • 
          
  • Surrogate split / native missing handling।
    • 
          
  • Robustness real-world data-এ critical।
    • 
        

        

          (৪) Domain knowledge integration:
        

        
    
          
  • চিকিৎসকের decision tree-র সাথে natural mapping।
    • 
          
  • Existing clinical guidelines tree-form।
    • 
          
  • "Diagnostic algorithm" — tree-এর inherent।
    • 
        

        

          (৫) Speed:
        

        
    
          
  • Real-time prediction — emergency room।
    • 
          
  • Tree traversal O(depth) — milliseconds।
    • 
          
  • Mobile/IoT deployment সহজ।
    • 
        

        

          Risk:
        

        

          (১) Overfitting → false confidence:
        

        
    
          
  • Small dataset → memorized tree।
    • 
          
  • Patient মুখস্থ — generalize ব্যর্থ।
    • 
          
  • Wrong diagnosis → patient harm।
    • 
          
  • Mitigation: aggressive pruning, ensemble।
    • 
        

        

          (২) Demographic bias:
        

        
    
          
  • Training data — affluent urban patients বেশি।
    • 
          
  • Rural / poor demographic underrepresented।
    • 
          
  • Disease pattern ভিন্ন — model fail।
    • 
          
  • Mitigation: stratified sampling, fairness audit।
    • 
        

        

          (৩) Spurious correlations:
        

        
    
          
  • "Hospital ID" predict — kala-azar (specific hospital pattern)।
    • 
          
  • Causal নয় — confounded।
    • 
          
  • Deployment-এ ভেঙে পড়ে।
    • 
          
  • Mitigation: feature selection, causal analysis।
    • 
        

        

          (৪) Continuous threshold instability:
        

        
    
          
  • "BP > ১৪০" — ১৪০ vs ১৪১ huge difference।
    • 
          
  • Physiologically dubious।
    • 
          
  • Mitigation: calibration, soft boundaries।
    • 
        

        

          (৫) Data drift:
        

        
    
          
  • Disease pattern বদলায় (COVID-এর age distribution)।
    • 
          
  • Tree fixed — adapt করে না।
    • 
          
  • Mitigation: monitoring, retraining schedule।
    • 
        

        

          (৬) Class imbalance:
        

        
    
          
  • Rare disease — ১% prevalence।
    • 
          
  • Tree majority class predict (no disease)।
    • 
          
  • Sensitivity drops।
    • 
          
  • Mitigation: class weights, SMOTE, threshold tuning।
    • 
        

        

          Mitigation strategies (comprehensive):
        

        

          (১) Validation rigor:
        

        
    
          
  • Multi-site validation।
    • 
          
  • Temporal split (past/future)।
    • 
          
  • Subgroup performance check।
    • 
          
  • External cohort validation।
    • 
        

        

          (২) Ensemble + interpretation:
        

        
    
          
  • Random Forest / XGBoost — accuracy।
    • 
          
  • SHAP — per-patient explanation।
    • 
          
  • "Best of both worlds"।
    • 
        

        

          (৩) Human-in-the-loop:
        

        
    
          
  • Tool — assistant, replacement নয়।
    • 
          
  • Doctor final decision।
    • 
          
  • "AI suggests, human verifies"।
    • 
        

        

          (৪) Calibration:
        

        
    
          
  • Probability calibration (Platt, isotonic)।
    • 
          
  • Confidence interval reporting।
    • 
          
  • "৮০% confidence" — meaningful।
    • 
        

        

          (৫) Continuous monitoring:
        

        
    
          
  • Prediction distribution track।
    • 
          
  • Performance metrics dashboard।
    • 
          
  • Drift detection automatic।
    • 
        

        

          (৬) Ethical framework:
        

        
    
          
  • Patient consent।
    • 
          
  • Algorithm transparency।
    • 
          
  • Bias audit process।
    • 
          
  • Liability clarity।
    • 
        

        

          Bangladesh-specific:
        

        
    
          
  • Diverse rural-urban — single model insufficient।
    • 
          
  • Limited expert annotators — semi-supervised।
    • 
          
  • Multilingual notes — additional NLP।
    • 
          
  • Resource-constrained deployment — efficient model।
    • 
        

        

          মূল উপলব্ধি: Healthcare ML — algorithm 30%, deployment process 70%। CART good starting, কিন্তু responsible deployment cross-disciplinary effort।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        হিসাব করুন: Regression — একটি node-এ targets {2, 4, 6, 8, 10}। Variance কত? একটি split — left {2, 4}, right {6, 8, 10}। Variance reduction কত?
        
    
          
          
    
            
      
              
    • Mean = ৬। Variance = $((4+4+0+4+16)/5) = 5.6$।
      • 
              
    • Left mean = ৩, var = ১।
      • 
              
    • Right mean = ৮, var = $(4+0+4)/3 \approx 2.67$।
      • 
              
    • Weighted = $(2/5)(1) + (3/5)(2.67) = 0.4 + 1.6 = 2.0$।
      • 
              
    • Reduction = $5.6 - 2.0 = 3.6$।
      • 
            
    
          
    
        
    
      
    2. 

      
  2. 
        sklearn: Boston/California housing-এ DecisionTreeRegressor — different ccp_alpha-এ MSE deplot করুন।
        
    
          
          
    
            
    from sklearn.datasets import fetch_california_housing
from sklearn.tree import DecisionTreeRegressor
X, y = fetch_california_housing(return_X_y=True)
clf = DecisionTreeRegressor(random_state=0).fit(X, y)
path = clf.cost_complexity_pruning_path(X, y)
# loop over path.ccp_alphas, fit models, plot.
    
          
    
        
    
      
    3. 

      
  3. 
        চিন্তা: CART vs ID3/C4.5 — কেন আজ CART dominant? তিনটি কারণ লিখুন।
        
    
          
          
    
            
    (১) Both classification + regression — single framework. (২) Cost-complexity pruning — theoretically grounded, CV-friendly. (৩) sklearn / R rpart — production-ready ecosystem। ID3/C4.5 academic legacy দিয়ে।
    
          
    
        
    
      
    4. 
    

  


  

    
 আরও পড়ুন

    

    

      কোড রানার কাজ না করলে? Google Colab ব্যবহার করুন।
    

  







  
   ভুল পেলে জানান





  
    
 পূর্ববর্তী পাঠ

    
পাঠ ১৯ · Decision Tree