Decision tree গভীরে — CART, impurity, pruning আর missing value

মডিউল ৬ শেষ হয়েছিল পর্ব ৩১-এ একটি সতর্ক কথায়: অনেক categorical আর মিশ্র কলামের tabular ডেটায় SVM-এর চেয়ে boosting প্রায়ই ভালো করে। এই মডিউল সেই boosting আর forest-এর দিকে যাবে, কিন্তু সবগুলোর ইট একটিই: একটি decision tree. AI-এর ভিত্তি কোর্সের পর্ব ৬৬-এ গাছের সঙ্গে প্রথম দেখা হয়েছে: Gini দিয়ে প্রথম প্রশ্ন বাছা আর max_depth দিয়ে গাছ ছোট রাখা। এখানে ভেতরে ঢুকব: প্রতিটি সংখ্যা হাতে, তারপর নিজে লেখা গাছ, তারপর scikit-learn-এর গাছের সঙ্গে হুবহু মিল। চালানো যায় এমন চারটি ব্লক পাতাতেই চলে (ব্রাউজারের Python, scikit-learn 1.8.0); প্রথমবার scikit-learn নামতে প্রায় দশ সেকেন্ড লাগে।

১ · গাছ কীভাবে প্রশ্ন বাছে — greedy, ওপর থেকে নিচে

বাজারঘরের (একটি কাল্পনিক অনলাইন দোকান) প্রশ্ন: কোন গ্রাহক চলে যাবেন, অর্থাৎ churn করবেন? প্রতিটি গ্রাহকের চারটি সংখ্যা: শেষ অর্ডারের পর কত দিন (days), গত ছয় মাসে অর্ডার (orders), দেরিতে পৌঁছানো ডেলিভারি (late) আর গড় ঝুড়ির দাম (basket, টাকা)। সব ডেটা seed দিয়ে বানানো, কোনো আসল দোকানের নয়।

CART (Classification And Regression Trees) গাছ বানায় recursive binary splitting দিয়ে:

1. সব train সারি মূল node-এ। যদি সব এক শ্রেণির হয়, বা কোনো থামার নিয়ম পূরণ হয়, এটি পাতা.
2. না হলে প্রতিটি feature j আর প্রতিটি সম্ভাব্য threshold t-এর জন্য প্রশ্ন “x_j ≤ t?” সারিগুলোকে বাঁ আর ডান দুই দলে ভাগ করে। প্রতিটি প্রশ্নের জন্য সন্তানদের impurity-র ওজনসহ গড় হিসাব।
3. যে (j, t) সেই গড় সবচেয়ে কম দেয়, সেটিই এই node-এর প্রশ্ন।
4. বাঁ আর ডান দলে ধাপ ১ থেকে আবার, যেন প্রতিটি দল একটি নতুন ছোট ডেটাসেট।

দুটি শব্দ মনে রাখুন। Greedy: প্রতিটি ধাপে এখনকার সেরা প্রশ্ন, ভবিষ্যতের কথা না ভেবে (DSA কোর্সের greedy algorithm-এর মতো)। Top-down: মূল থেকে শুরু করে নিচে। কেন সেরা পুরো গাছ সরাসরি খোঁজা হয় না? Laurent Hyafil আর Ronald Rivest ১৯৭৬ সালে দেখান, একটি নির্দিষ্ট অর্থে সবচেয়ে ছোট নির্ভুল binary decision tree খোঁজা NP-complete. তাই বাস্তবে greedy, আর তার ভুল আংশিক সারানো হয় pruning আর ensemble দিয়ে।

নতুন গ্রাহক এলে তাঁকে মূল থেকে প্রশ্ন ধরে নিচে নামানো হয়, যতক্ষণ না কোনো পাতায় পৌঁছান। Classification-এ পাতা জানায় সেখানকার train সারিগুলোর শ্রেণি-অনুপাত (সেটিই predict_proba) আর সংখ্যাগরিষ্ঠ শ্রেণি। Prediction-এর খরচ শুধু গাছের গভীরতা, সারির সংখ্যা নয়।

২ · Impurity — Gini, entropy আর misclassification error

“সবচেয়ে পরিষ্কার ভাগ” মাপতে লাগে একটি node কতটা মেশানো তার সংখ্যা: impurity. দুই শ্রেণিতে, p হলো node-এ churn করা গ্রাহকের অনুপাত।

Gini-র একটি সুন্দর অর্থ আছে: node থেকে এলোমেলোভাবে একটি গ্রাহক নিয়ে তাঁকে node-এর অনুপাত অনুযায়ী এলোমেলো label দিলে ভুল হওয়ার সম্ভাবনা। Entropy আর তার কমা, অর্থাৎ information gain, AI-এর ভিত্তি কোর্সের পর্ব ৩৮-এ বিস্তারিত দেখেছেন; এখানে শুধু ব্যবহার। একটি split-এর মান:

I_split = (n_L/n) · I(L) + (n_R/n) · I(R)

এখানে n_L, n_R হলো বাঁ আর ডান সন্তানের সারি, I যেকোনো একটি impurity. লক্ষ্য I_split সবচেয়ে কম করা, অর্থাৎ decrease = I(parent) − I_split সবচেয়ে বেশি করা। Entropy দিয়ে এই decrease-এর নামই information gain.

কেন misclassification error দিয়ে গাছ বাড়ানো হয় না? দুই শ্রেণির ৮০০ গ্রাহক, ৪০০ আর ৪০০. Split A দেয় (৩০০ থাকবেন, ১০০ churn) আর (১০০, ৩০০); Split B দেয় (২০০, ৪০০) আর (২০০, ০). দুটিতেই ২০০টি ভুল, error ০.২৫. কিন্তু B একটি পুরো খাঁটি দল বানিয়েছে, যা পরের ধাপে আর ভাগ করতে হবে না। Gini সেটি ধরে: A-তে ০.৩৭৫, B-তে ০.৩৩৩. কারণটি জ্যামিতিক: Gini আর entropy p-এর কঠোরভাবে বাঁকা (strictly concave) ফাংশন, তাই সন্তানদের p যতই বাবার p থেকে দূরে সরে, ওজনসহ গড় ততই কমে। Error রেখাটি টুকরো টুকরো সোজা; সন্তান দুজন একই দিকে সংখ্যাগরিষ্ঠ থাকলে error একটুও কমে না, যদিও ভাগটি কাজের। Breiman ও সহলেখকেরা CART বইয়ে এই যুক্তিই দিয়েছিলেন। Error তবু কাজে লাগে: pruning-এর পুরোনো রূপে আর শেষ মূল্যায়নে।

নিচের ব্লক তিনটি মাপ নিজে লেখে, দশজনের টেবিলে সব নয়টি সম্ভাব্য threshold চেষ্টা করে, A আর B split তুলনা করে, আর তিনটি রেখা আঁকে।

import numpy as np
import matplotlib.pyplot as plt

def gini(y):    p = np.mean(y); return 1 - p**2 - (1 - p)**2
def entropy(y):
    p = np.mean(y)
    return 0.0 if p in (0, 1) else -(p*np.log2(p) + (1-p)*np.log2(1-p))
def miscls(y):  p = np.mean(y); return min(p, 1 - p)

days  = np.array([3, 8, 12, 17, 25, 29, 34, 47, 60, 78])
churn = np.array([0, 0, 0, 1, 0, 0, 0, 1, 1, 1])
print(f"root: gini {gini(churn):.4f}  entropy {entropy(churn):.4f}  error {miscls(churn):.2f}")
print(" threshold  left  right  w-gini  w-entropy  w-error")
for t in (days[:-1] + days[1:]) / 2:            # পাশাপাশি দুই মানের মাঝখান
    L, R = churn[days <= t], churn[days > t]
    w = lambda f: (len(L)*f(L) + len(R)*f(R)) / len(churn)
    print(f"{t:9.1f}  {len(L):4d}  {len(R):5d}  {w(gini):.4f}  {w(entropy):9.4f}  {w(miscls):7.2f}")

# দুই split, misclassification error একই, Gini আলাদা
for name, (a, b) in {"A": ((300, 100), (100, 300)), "B": ((200, 400), (200, 0))}.items():
    ys = [np.r_[np.zeros(s[0]), np.ones(s[1])] for s in (a, b)]
    g = sum(len(y)*gini(y) for y in ys) / 800
    e = sum(len(y)*miscls(y) for y in ys) / 800
    print(f"split {name}: weighted gini {g:.4f}  weighted error {e:.4f}")

p = np.linspace(0.001, 0.999, 200)
H = -(p*np.log2(p) + (1-p)*np.log2(1-p))
fig, ax = plt.subplots(figsize=(6, 3.6))
ax.plot(p, 1 - p**2 - (1-p)**2, label="Gini 1 - p^2 - (1-p)^2")
ax.plot(p, H / 2, label="entropy / 2 (bits)")
ax.plot(p, np.minimum(p, 1 - p), label="misclassification error")
ax.set(xlabel="p = share of churners in a node", ylabel="impurity",
       title="Three impurity measures (two classes)")
ax.legend(fontsize=8); fig.subplots_adjust(bottom=0.15)

root: gini 0.4800  entropy 0.9710  error 0.40
 threshold  left  right  w-gini  w-entropy  w-error
      5.5     1      9  0.4444     0.8920     0.40
     10.0     2      8  0.4000     0.8000     0.40
     14.5     3      7  0.3429     0.6897     0.30
     21.0     4      6  0.4500     0.9245     0.40
     27.0     5      5  0.4000     0.8464     0.30
     31.5     6      4  0.3167     0.7145     0.20
     40.5     7      3  0.1714     0.4142     0.10
     53.5     8      2  0.3000     0.6490     0.20
     69.0     9      1  0.4000     0.8265     0.30
split A: weighted gini 0.3750  weighted error 0.2500
split B: weighted gini 0.3333  weighted error 0.2500

৩ · সংখ্যার feature-এ সেরা threshold — সাজানো, মাঝখান আর খরচ

একটি সংখ্যার feature-এ অসীম সংখ্যক threshold সম্ভব, কিন্তু ভাগ বদলায় শুধু তখন, যখন threshold কোনো train মান পার হয়। তাই মানগুলো সাজিয়ে নিয়ে পাশাপাশি দুটি আলাদা মানের মাঝখানে কাটলেই সব আলাদা ভাগ পাওয়া যায়: n টি আলাদা মানে n − ১টি প্রার্থী। মাঝখান কেন, কিনারা নয়? দুটি মানের মাঝে যেকোনো জায়গায় কাটলে train-এ একই ফল, আর মাঝখান নতুন ডেটার জন্য দুই দিকে সমান জায়গা রাখে। scikit-learn-ও মাঝখান নেয়, আর ভেতরে X-কে float32 করে নেয়।

খরচ। প্রতিটি threshold-এ গোড়া থেকে Gini হিসাব করলে একটি feature-এ n² কাজ। চালাক উপায়: সাজানো ক্রমে একটি করে সারি বাঁ দিকে সরান আর শ্রেণির গোনা হালনাগাদ করুন; প্রতিটি নতুন threshold-এ Gini তখন O(1). ফলে একটি node-এ একটি feature-এর খরচ সাজানোর O(n log n) আর স্ক্যানের O(n); p টি feature-এ O(p · n log n). গাছ মোটামুটি ভারসাম্যপূর্ণ হলে প্রতিটি স্তরে সব node মিলে n টি সারি, স্তর প্রায় log n টি, তাই পুরো গাছ প্রায় O(p · n log² n); খুব একপেশে গাছে স্তর n-এর কাছাকাছি হতে পারে, আর খরচও বাড়ে। scikit-learn-এর docs সবচেয়ে খারাপ ক্ষেত্রের সীমা আরও বড় লেখে। Big-O-এর ভাষা DSA কোর্সের Big-O পর্বে আছে।

মেপে দেখা যাক। ডেস্কটপে সত্যিকারের run (একটি সাধারণ ল্যাপটপ, Python 3.14.4, scikit-learn 1.8.0; একটি run, সাধারণ ফল নয়)। একই ডেটা-নিয়মে চারটি feature, n প্রতিবার দ্বিগুণ; সমান মান ভাঙতে সামান্য noise যোগ করা:

~/bazarghar-ml$ python tree_time.py
Python 3.14.4, scikit-learn 1.8.0
        n   depth-8 fit (s)   full-tree fit (s)  leaves
   50,000           0.11               0.16     4,843
  100,000           0.24               0.37     9,557
  200,000           0.54               0.88    19,257
  400,000           1.17               2.11    37,831
  800,000           2.93               5.65    75,768

n দ্বিগুণ হলে সময় প্রায় ২.১ থেকে ২.৭ গুণ: দ্বিগুণের সামান্য বেশি, n log n-এর সঙ্গে মানানসই, পর্ব ৩১-এর SVC-এর প্রায় চার গুণের সঙ্গে তুলনা করুন। আট লাখ সারিতে পুরো গাছ ছয় সেকেন্ডের কম। কিন্তু শেষ কলামটি দেখুন: কোনো সীমা না দিলে গাছ প্রায় প্রতি দশ-এগারোটি সারিতে একটি পাতা বানিয়েছে, ৭৫,৭৬৮টি পাতা। এটি শেখা নয়, মুখস্থ। সেই সমস্যায় অংশ ৬-এ ফিরব।

৪ · Regression tree — squared error আর variance কমানো

লক্ষ্য যদি সংখ্যা হয়, যেমন বাজারঘরের ডেলিভারিতে কত ঘণ্টা লাগবে, তাহলে “মেশানো” মাপার বদলে মাপি “ছড়ানো”। একটি পাতার অনুমান সেখানকার y-গুলোর গড় ȳ, আর node-এর ভুল হলো squared error-এর যোগফল SSE = ∑(y_i − ȳ)²; এটি n × variance-এর সমান। সেরা split সন্তানদের SSE-এর যোগ সবচেয়ে কম করে, অর্থাৎ variance reduction সবচেয়ে বেশি করে। Squared error-এ গড়ই সেরা ধ্রুবক অনুমান, তাই পাতায় গড় (পর্ব ০২-এর loss আর তার সেরা ধ্রুবক)।

ছয়টি কাল্পনিক অর্ডার, গুদাম থেকে দূরত্ব (km) আর ডেলিভারির সময় (ঘণ্টা): (২, ১০), (৪, ১২), (৫, ১১), (৯, ৩০), (১২, ৩৪), (১৫, ৩২). মূলের গড় ২১.৫, SSE ৬৭১.৫.

৭ km-এ ভাগ করলে SSE ৬৭১.৫ থেকে ১০-এ নামে: কাছের তিনটি অর্ডার গড়ে ১১ ঘণ্টা, দূরের তিনটি ৩২ ঘণ্টা। DecisionTreeRegressor-এর ডিফল্ট criterion="squared_error" ঠিক এটিই করে; "absolute_error" পাতায় median নেয় (outlier-এ শক্ত, কিন্তু অনেক ধীর), "poisson" গণনার লক্ষ্যের জন্য (পর্ব ২০), আর "friedman_mse" একটি সংশোধিত রূপ যা পর্ব ৩৫-এর gradient boosting-এ কাজে লাগে। একটি সীমা মনে রাখুন: regression tree-এর অনুমান ধাপের মতো, আর train-এ দেখা y-এর পরিসরের বাইরে কখনো যায় না। ২০ km-এর অর্ডারেও উত্তর ৩২ ঘণ্টা। এই extrapolation-এর অক্ষমতা পর্ব ৩৩ (Bagging আর random forest) একটি ছবিতে দেখাবে।

৫ · নিজে CART লেখা — আর scikit-learn-এর সঙ্গে হুবহু মেলানো

এবার পুরো বাজারঘর ডেটা: ৩০০ জন গ্রাহক, চারটি feature. Churn-এর সম্ভাবনা বাড়ে দিন আর দেরির ডেলিভারির সঙ্গে, কমে অর্ডারের সঙ্গে; ঝুড়ির দামের কোনো ভূমিকা নেই (একটি অকাজের feature রাখা হয়েছে ইচ্ছা করে)। প্রায় ৪৩–৪৭% গ্রাহক churn করেন।

# bazar_churn.py — বাজারঘরের কাল্পনিক গ্রাহক, কে চলে যাবে (seed দিয়ে বানানো)
import numpy as np
import pandas as pd

def make_churn(n=400, seed=32):
    rng = np.random.default_rng(seed)
    days = rng.integers(1, 91, n)                  # শেষ অর্ডারের পর কত দিন
    orders = rng.poisson(4, n)                     # গত ৬ মাসে অর্ডার
    late = rng.binomial(orders, 0.25)              # দেরিতে পৌঁছানো ডেলিভারি
    basket = rng.gamma(4, 300, n).round()          # গড় ঝুড়ি (টাকা)
    score = 0.05 * (days - 45) - 0.5 * (orders - 4) + 0.9 * late - 1.0
    p = 1 / (1 + np.exp(-3 * score))
    churn = (rng.random(n) < p).astype(int)
    return pd.DataFrame({"days": days, "orders": orders, "late": late,
                         "basket": basket, "churn": churn})

নিচের grow ফাংশনটিই পুরো CART: প্রতিটি feature সাজায়, প্রতিটি বৈধ জায়গায় কাটে, সবচেয়ে কম ওজনসহ Gini রাখে, তারপর নিজেকেই দুই দলে ডাকে (recursion, DSA কোর্সের recursion পর্ব)। থামার নিয়ম scikit-learn-এর মতো: গভীরতা ৩, প্রতিটি পাতায় অন্তত ৫টি সারি (min_samples_leaf), অথবা node খাঁটি। পড়ার সুবিধার জন্য Gini গোড়া থেকে হিসাব হয়, তাই কোডটি O(n²); গতি নয়, স্বচ্ছতা লক্ষ্য। শেষে গাছ sk.tree_ থেকে প্রতিটি split পড়ে দুটি গাছ মেলানো হয়।

import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text
from bazar_churn import make_churn

def gini(y): p = y.mean(); return 2 * p * (1 - p)
def grow(X, y, depth=0, max_depth=3, leaf=5):
    best = (np.inf, None, None)                    # (weighted gini, feature, threshold)
    for j in range(X.shape[1]):
        o = np.argsort(X[:, j], kind="stable"); xs, ys = X[o, j], y[o]
        for i in range(leaf, len(y) - leaf + 1):   # বাঁয়ে i টি সারি
            if xs[i - 1] == xs[i]: continue        # সমান মানের মাঝে কাটা যায় না
            w = (i * gini(ys[:i]) + (len(y) - i) * gini(ys[i:])) / len(y)
            if w < best[0]: best = (w, j, (xs[i - 1] + xs[i]) / 2)
    w, j, t = best
    if depth == max_depth or gini(y) == 0 or j is None:
        return {"p": y.mean()}                     # পাতা: churn-এর অনুপাত
    m = X[:, j] <= t
    return {"j": j, "t": t, "L": grow(X[m], y[m], depth + 1),
            "R": grow(X[~m], y[~m], depth + 1)}
def predict(node, x):
    while "j" in node: node = node["L"] if x[node["j"]] <= node["t"] else node["R"]
    return int(node["p"] > 0.5)
def splits(node):
    return [] if "j" not in node else [(node["j"], node["t"])] + splits(node["L"]) + splits(node["R"])

df = make_churn(300); cols = ["days", "orders", "late", "basket"]
X, y = df[cols].to_numpy(float), df["churn"].to_numpy()
mine = grow(X, y)
sk = DecisionTreeClassifier(max_depth=3, min_samples_leaf=5, random_state=0).fit(X, y)
tr = sk.tree_; sk_splits = [(f, t) for f, t in zip(tr.feature, tr.threshold) if f >= 0]
print("root  mine:", cols[mine["j"]], "<=", mine["t"], "  sklearn:", cols[tr.feature[0]], "<=", tr.threshold[0])
print("all splits equal:", splits(mine) == sk_splits, " internal nodes:", len(sk_splits))
print("same predictions:", all(predict(mine, x) == p for x, p in zip(X, sk.predict(X))))
print(export_text(sk, feature_names=cols, show_weights=True))

root  mine: days <= 45.5   sklearn: days <= 45.5
all splits equal: True  internal nodes: 7
same predictions: True
|--- days <= 45.50
|   |--- late <= 1.50
|   |   |--- orders <= 2.50
|   |   |   |--- weights: [26.00, 9.00] class: 0
|   |   |--- orders >  2.50
|   |   |   |--- weights: [79.00, 3.00] class: 0
|   |--- late >  1.50
|   |   |--- days <= 28.00
|   |   |   |--- weights: [22.00, 4.00] class: 0
|   |   |--- days >  28.00
|   |   |   |--- weights: [3.00, 10.00] class: 1
|--- days >  45.50
|   |--- orders <= 6.50
|   |   |--- days <= 51.50
|   |   |   |--- weights: [9.00, 10.00] class: 1
|   |   |--- days >  51.50
|   |   |   |--- weights: [8.00, 91.00] class: 1
|   |--- orders >  6.50
|   |   |--- late <= 2.50
|   |   |   |--- weights: [12.00, 5.00] class: 0
|   |   |--- late >  2.50
|   |   |   |--- weights: [0.00, 9.00] class: 1

৬ · থামার নিয়ম বনাম cost-complexity pruning

সীমা ছাড়া গাছ প্রতিটি পাতা খাঁটি না হওয়া পর্যন্ত ভাগ করে; train accuracy ১০০%, কিন্তু নতুন ডেটায় খারাপ, অর্থাৎ overfitting (AI-এর ভিত্তি কোর্সের পর্ব ৬১). থামানোর দুই পথ।

গাছ T-এর দাম:

R_α(T) = R(T) + α · |T|

R(T) হলো পাতাগুলোর ভুল (CART বইয়ে misclassification rate; scikit-learn-এ প্রতিটি পাতার impurity গুণ সেই পাতার সারির অনুপাত, সবার যোগ), |T| পাতার সংখ্যা, আর α ≥ ০ প্রতিটি পাতার জরিমানা। α = ০ হলে পুরো গাছ সেরা; α বিশাল হলে শুধু মূল। একটি ভেতরের node t-কে পাতা বানালে R বাড়ে, কিন্তু পাতা কমে। দুটি সমান হয় যে α-তে:

α_eff(t) = (R(t) − R(T_t)) / (|T_t| − ১)

এখানে R(t) হলো t একা পাতা হলে তার ভুল, T_t হলো t-এর নিচের উপগাছ। যার α_eff সবচেয়ে ছোট, সে-ই weakest link: প্রতিটি বাড়তি পাতা দিয়ে সবচেয়ে কম লাভ আনে। তাকে কাটুন, আবার হিসাব করুন। এভাবে বাড়তে থাকা α-এর একটি ধারা আর ক্রমশ ছোট গাছের একটি শিকল পাওয়া যায়; Breiman ও সহলেখকেরা দেখান, প্রতিটি α-র সেরা ছাঁটা গাছ এই শিকলেরই কোনো একটি।

কোন α? এটি একটি hyperparameter, তাই train ডেটার ভেতরে cross-validation দিয়ে (AI-এর ভিত্তি কোর্সের পর্ব ৬৬). cost_complexity_pruning_path পুরো গাছের সব α_eff এক ডাকে দেয়; সেগুলোই প্রার্থী। নিচের ব্লক ৪০০ জনকে ৭০/৩০ ভাগ করে, তিনটি গাছ তুলনা করে: সীমাহীন, ৫-fold CV-তে বাছা max_depth, আর CV-তে বাছা ccp_alpha. Test ভাগ শুধু শেষ মাপে।

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split, GridSearchCV, StratifiedKFold
from bazar_churn import make_churn

df = make_churn(400); cols = ["days", "orders", "late", "basket"]
X_tr, X_te, y_tr, y_te = train_test_split(df[cols], df["churn"], test_size=0.3,
                                          stratify=df["churn"], random_state=0)
path = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(X_tr, y_tr)
alphas = path.ccp_alphas[:-1]                      # শেষটি শুধু মূল (একটি পাতা)
print(f"{len(alphas)} candidate alphas, from {alphas[0]:.4f} to {alphas[-1]:.4f}")

cv = StratifiedKFold(5, shuffle=True, random_state=0)
grids = {"full tree": {"ccp_alpha": [0.0]},
         "max_depth (CV)": {"max_depth": list(range(1, 11))},
         "ccp_alpha (CV)": {"ccp_alpha": list(alphas)}}
for name, grid in grids.items():
    gs = GridSearchCV(DecisionTreeClassifier(random_state=0), grid, cv=cv).fit(X_tr, y_tr)
    m, bp = gs.best_estimator_, {k: float(round(v, 4)) if isinstance(v, float) else v
                                  for k, v in gs.best_params_.items()}
    print(f"{name:15s} {bp}  leaves {m.get_n_leaves():3d}  "
          f"train {m.score(X_tr, y_tr):.3f}  test {m.score(X_te, y_te):.3f}")

tr, te, lv = [], [], []
for a in alphas:
    m = DecisionTreeClassifier(random_state=0, ccp_alpha=a).fit(X_tr, y_tr)
    tr.append(m.score(X_tr, y_tr)); te.append(m.score(X_te, y_te)); lv.append(m.get_n_leaves())
fig, (a1, a2) = plt.subplots(1, 2, figsize=(9, 3.6))
a1.step(alphas, tr, where="post", label="train"); a1.step(alphas, te, where="post", label="test")
a1.set(xlabel="ccp_alpha", ylabel="accuracy", title="Pruning: accuracy")
a1.legend(fontsize=8)
a2.step(alphas, lv, where="post"); a2.set(xlabel="ccp_alpha", ylabel="leaves", title="Pruning: tree size")
fig.subplots_adjust(bottom=0.16, wspace=0.3)

26 candidate alphas, from 0.0000 to 0.0248
full tree       {'ccp_alpha': 0.0}  leaves  49  train 1.000  test 0.775
max_depth (CV)  {'max_depth': 3}  leaves   8  train 0.864  test 0.808
ccp_alpha (CV)  {'ccp_alpha': 0.0116}  leaves   8  train 0.879  test 0.825

৭ · গাছ কেন অস্থির — bootstrap, সিঁড়ির সীমা আর missing value

এটি greedy আর hierarchical গঠনের ফল: ওপরের একটি ছোট পরিবর্তন নিচে ছড়িয়ে পড়ে। মাপতে পর্ব ২১-এর bootstrap: একই ৪০০ জন থেকে ফেরত রেখে ৪০০ জন টেনে নতুন গাছ, ছয়বার। ছবির জন্য শুধু দুটি feature, days আর orders. ব্লকের শেষ অংশ ১৫% গ্রাহকের days মুছে দিয়ে দেখে, গাছ NaN নিজে সামলায় কি না।

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier
from bazar_churn import make_churn

df = make_churn(400); cols = ["days", "orders"]       # শুধু দুটি feature, ছবির জন্য
X, y = df[cols].to_numpy(float), df["churn"].to_numpy()
rng = np.random.default_rng(0)
gx, gy = np.meshgrid(np.linspace(0, 92, 200), np.linspace(-0.5, 13.5, 200))
grid = np.c_[gx.ravel(), gy.ravel()]
fig, axes = plt.subplots(1, 3, figsize=(10, 3.4), sharey=True)
preds = []
for b in range(6):
    idx = rng.integers(0, len(y), len(y))             # bootstrap: ফেরত রেখে টানা
    t = DecisionTreeClassifier(max_depth=4, random_state=0).fit(X[idx], y[idx])
    f, th = t.tree_.feature, t.tree_.threshold
    print(f"sample {b}: root {cols[f[0]]} <= {th[0]:5.1f}  left child: "
          f"{cols[f[1]]} <= {th[1]:4.1f}, right child: {cols[f[t.tree_.children_right[0]]]}")
    preds.append(t.predict(grid))
    if b < 3:
        ax = axes[b]; ax.contourf(gx, gy, preds[-1].reshape(gx.shape), alpha=0.3, cmap="coolwarm")
        ax.scatter(X[:, 0], X[:, 1], c=y, s=6, cmap="coolwarm")
        ax.set(title=f"bootstrap tree {b}", xlabel="days since last order")
axes[0].set_ylabel("orders in 6 months"); fig.subplots_adjust(bottom=0.17)
P = np.array(preds)
print(f"grid points where the 6 trees disagree: {np.mean(P.min(0) != P.max(0)):.0%}")

# missing value: 15% 'days' খালি, scikit-learn-এর tree নিজেই সামলায়
Xm = X.copy(); Xm[rng.random(len(y)) < 0.15, 0] = np.nan
tm = DecisionTreeClassifier(max_depth=3, random_state=0).fit(Xm, y)
go_left = tm.tree_.missing_go_to_left[0]
print(f"NaN in days: {np.isnan(Xm[:, 0]).sum()} rows; root {cols[tm.tree_.feature[0]]} <= "
      f"{tm.tree_.threshold[0]:.1f}, NaN rows go {'left' if go_left else 'right'}")
print("prediction for [NaN, 2]:", tm.predict([[np.nan, 2.0]]))

sample 0: root days <=  37.5  left child: days <= 17.5, right child: orders
sample 1: root days <=  55.5  left child: days <= 40.5, right child: days
sample 2: root days <=  63.5  left child: days <= 29.5, right child: orders
sample 3: root days <=  33.5  left child: days <= 19.5, right child: orders
sample 4: root days <=  53.5  left child: days <= 33.5, right child: orders
sample 5: root days <=  63.5  left child: days <= 24.5, right child: orders
grid points where the 6 trees disagree: 35%
NaN in days: 68 rows; root days <= 37.5, NaN rows go left
prediction for [NaN, 2]: [0]

৮ · Missing value, categorical feature আর ID3 থেকে CART

scikit-learn-এ missing value. scikit-learn-এর docs অনুযায়ী DecisionTreeClassifier আর DecisionTreeRegressor splitter="best"-এ NaN সরাসরি সামলায় (এই সুবিধা এসেছে 1.3 সংস্করণে, পরে random splitter আর forest-এও; নিজের version-এর docs মিলিয়ে নিন)। পদ্ধতি সরল: প্রতিটি সম্ভাব্য split-এ NaN সারিগুলো একবার বাঁয়ে আর একবার ডানে রেখে impurity দেখা, যেটি ভালো সেটি রাখা; সেই দিক tree_.missing_go_to_left-এ জমা থাকে। Train-এ কোনো feature-এ NaN না থাকলে prediction-এর সময় সেই feature-এ NaN এলে সারিটি যে সন্তানে বেশি সারি, সেখানে যায়। Criterion হতে হবে "gini", "entropy", "log_loss" (classification) বা "squared_error", "friedman_mse", "poisson" (regression-এর ক্ষেত্রে)।

আরেকটি বড় সুবিধা: “খালি” নিজেই তথ্য হতে পারে। যে গ্রাহক কখনো ঠিকানা দেননি, তিনি হয়তো কম আগ্রহী। গড় দিয়ে ভরাট (imputation) করলে সেই সংকেত হারায়; গাছ NaN-কে নিজের দিকে পাঠিয়ে তা রাখতে পারে। তবে imputation করলে তা pipeline-এর ভেতরে, শুধু train-এ শিখে (AI-এর ভিত্তি কোর্সের পর্ব ৫৬-এর leakage-এর সতর্কতা)।

পুরোনো সমাধান। CART বই NaN-এর জন্য surrogate split প্রস্তাব করে: মূল প্রশ্নের feature না থাকলে অন্য একটি feature-এর প্রশ্ন, যা মূল ভাগকে সবচেয়ে ভালো নকল করে। R-এর rpart এটি করে; scikit-learn করে না। Quinlan-এর C4.5 অজানা মানের সারিকে ভগ্নাংশ ওজনে সব শাখায় পাঠায়।

Categorical feature. scikit-learn-এর docs সোজাসুজি বলে, তাদের গাছ এখনো categorical কলাম সরাসরি নেয় না; সংখ্যায় রূপান্তর করে দিতে হয়। বিকল্পগুলোর দাম আলাদা:

৯ · AI-এর যুগে — গাছের কোড আর ব্যাখ্যা যাচাই

AI assistant-কে “churn-এর জন্য decision tree বানিয়ে দাও” বললে সাধারণত চলে এমন কোড আসে। ভুল থাকে সূক্ষ্ম জায়গায়, আর গাছ “পড়া যায়” বলে ভুল ব্যাখ্যাও সহজে বিশ্বাসযোগ্য মনে হয়। পরিচিত ভুলগুলো:

AI-এর দেওয়া গাছের কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• ছোট একটি টেবিলে মূল split-এর Gini নিজে হিসাব করে tree_.impurity আর tree_.threshold-এর সঙ্গে মিলিয়েছি
• পাতার সংখ্যা আর গভীরতা দেখেছি; train আর CV accuracy-র ফারাক লিখে রেখেছি
• ccp_alpha বা max_depth শুধু train-এর ভেতরে CV দিয়ে বাছা, test একবারই ব্যবহার
• কয়েকটি seed বা bootstrap-এ গাছ বানিয়ে দেখেছি মূল আর ফল কতটা নড়ে
• Categorical encoding আর NaN-এর ব্যবস্থা pipeline-এর ভেতরে, নিজের version-এর docs মিলিয়ে
• একটি সরল baseline (logistic regression বা সবচেয়ে সাধারণ শ্রেণি) একই fold-এ তুলনা করেছি
• গাছের নিয়মকে কারণ বলে দাবি করিনি, আর কোনো আসল গ্রাহকের ডেটা AI-তে পেস্ট করিনি