درخت تصمیم و جنگل تصادفی: پیاده‌سازی از صفر و تئوری ریاضی

در دنیای تحلیل داده و مسائل روزمره‌ی مهندسی نرم‌افزار، بیشتر داده‌هایی که با آن‌ها سروکار داریم به شکل جدول‌های رابطه‌ای و ساختاریافته هستند. با وجود هیاهوی شبکه‌های عصبی و یادگیری عمیق، در عمل مدل‌های مبتنی بر درخت مثل درخت تصمیم (Decision Tree) و جنگل تصادفی (Random Forest) همچنان پادشاه بلامنازع پردازش داده‌های جدولی به شمار می‌روند و اغلب سریع‌تر، کم‌هزینه‌تر و دقیق‌تر از معماری‌های پیچیده عمل می‌کنند.

یادگیری عمیق به حجم عظیمی از داده، تنظیمات دقیق ابرپارامترها و منابع محاسباتی سنگین نیاز دارد؛ در حالی که مدل‌های درختی حتی روی یک سیستم معمولی با پردازنده‌ی مرکزی (CPU) در عرض چند دقیقه آموزش می‌بینند و رابطه‌ی بین ویژگی‌های عددی و متنی را بدون پیش‌پردازش‌های پیچیده استخراج می‌کنند.

در این درس، ریاضیات پشت تفکیک داده‌ها مانند ناخالصی جینی (Gini Impurity)، آنتروپی و بهره‌ی اطلاعات را بررسی می‌کنیم و یک درخت تصمیم و جنگل تصادفی را بدون وابستگی به کتابخانه‌های آماده، از صفر در پایتون کدنویسی می‌کنیم تا دقیقاً ببینید در پشت صحنه‌ی این الگوریتم‌ها چه می‌گذرد.

درخت تصمیم در واقع یک فلوچارت ساده است؛ اما جنگلی از این درخت‌ها، یکی از قدرتمندترین ابزارهای یادگیری ماشین به شمار می‌رود.

اهداف یادگیری

• پیاده‌سازی محاسبات ناخالصی جینی (Gini impurity)، آنتروپی (entropy) و بهره‌ی اطلاعات (information gain) برای پیدا کردن بهترین تفکیک‌ها در درخت تصمیم
• ساخت یک دسته‌بند درخت تصمیم از صفر همراه با کنترل‌های پیش‌هرس (حداکثر عمق، حداقل تعداد نمونه)
• ساخت جنگل تصادفی (random forest) با استفاده از نمونه‌گیری بوت‌استرپ و تصادفی‌سازی ویژگی‌ها، و درک سازوکار کاهش واریانس در این روش
• مقایسه‌ی اهمیت ویژگی مبتنی بر کاهش میانگین ناخالصی (MDI) با اهمیت جایگشتی (permutation importance) و تشخیص سوگیری‌های MDI

صورت مسئله

فرض کنید داده‌های جدولی دارید: سطرها همان نمونه‌ها هستند، ستون‌ها ویژگی‌ها، و یک ستون هدف هم وجود دارد که می‌خواهید آن را پیش‌بینی کنید. شاید اولین ایده‌تان استفاده از یک شبکه عصبی باشد؛ اما روی داده‌های جدولی، مدل‌های مبتنی بر درخت (درخت‌های تصمیم، جنگل‌های تصادفی و درخت‌های ارتقای گرادیان) همیشه عملکرد بهتری نسبت به یادگیری عمیق دارند. در مسابقات کگل (Kaggle) روی داده‌های ساختاریافته، برندگان اصلی XGBoost و LightGBM هستند، نه ترنسفورمرها.

دلیل این برتری چیست؟ درخت‌ها بدون نیاز به پیش‌پردازش، انواع مختلف ویژگی‌ها (عددی و دسته‌ای) را مدیریت می‌کنند؛ روابط غیرخطی را بدون مهندسی ویژگی می‌فهمند؛ و تفسیرپذیرند: کافی است به درخت نگاه کنید تا ببینید یک پیش‌بینی دقیقاً بر چه اساسی انجام شده است. علاوه بر این، جنگل‌های تصادفی با میانگین‌گیری از چندین درخت، مقاومت بسیار بالایی در برابر بیش‌برازش (overfitting) روی مجموعه‌داده‌های متوسط نشان می‌دهند.

در این درس، ابتدا درخت‌های تصمیم را با تفکیک بازگشتی از صفر می‌سازیم و سپس جنگل تصادفی را روی آن بنا می‌کنیم. فرمول‌های ریاضی معیارهای تفکیک (ناخالصی جینی، آنتروپی و بهره‌ی اطلاعات) را پیاده‌سازی خواهید کرد و متوجه می‌شوید چطور ترکیب چند یادگیرنده‌ی ضعیف، به یک مدل قدرتمند تبدیل می‌شود.

مفاهیم پایه

سازوکار درخت تصمیم

درخت تصمیم با پرسیدن یک سری سؤال بله/خیر، فضای ویژگی‌ها را به ناحیه‌های مستطیلی تقسیم می‌کند.

هر گره داخلی، یک ویژگی را در برابر یک مقدار آستانه می‌سنجد. هر گره برگ هم یک پیش‌بینی ارائه می‌دهد. برای دسته‌بندی یک داده‌ی جدید، از ریشه شروع می‌کنید و شاخه‌ها را پیش می‌گیرید تا به یک برگ برسید.

ساخت درخت از بالا به پایین انجام می‌شود؛ یعنی در هر گره، ویژگی و آستانه‌ای انتخاب می‌شود که داده‌ها را به بهترین شکل ممکن تفکیک کند. مفهوم «بهترین» را معیار تفکیک مشخص می‌کند.

معیارهای تفکیک: سنجش ناخالصی

در هر گره، مجموعه‌ای از نمونه‌ها را داریم. می‌خواهیم آن‌ها را طوری بشکنیم که گره‌های فرزندِ حاصل، تا حد ممکن «خالص» باشند؛ یعنی بیشتر نمونه‌های هر فرزند متعلق به یک کلاس باشند.

ناخالصی جینی (Gini impurity) احتمال این را می‌سنجد که اگر یک نمونه‌ی تصادفی را بر اساس توزیع کلاس‌های همان گره برچسب‌گذاری کنیم، چقدر احتمال دارد اشتباه دسته‌بندی شود.

$$\text{Gini}(S) = 1 - \sum_k p_k^2 \quad \text{where } p_k \text{ is the proportion of class } k \text{ in set } S.$$

برای یک گره کاملاً خالص (که همه‌ی نمونه‌هایش از یک کلاس باشند)، جینی برابر 0 است. برای یک تفکیک دودویی با نسبت 50/50، جینی برابر 0.5 خواهد بود. هرچه کمتر باشد بهتر است.

Example: 6 cats, 4 dogs

Gini = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48

آنتروپی (Entropy) محتوای اطلاعات (میزان بی‌نظمی) درون یک گره را می‌سنجد؛ مفهومی که در فاز 1 درس 09 بررسی شد.

$$\text{Entropy}(S) = -\sum_k p_k \log_2(p_k)$$

برای گره خالص، آنتروپی برابر 0 است و برای تفکیک دودویی 50/50، آنتروپی به 1.0 می‌رسد. هرچه کمتر باشد بهتر است.

Example: 6 cats, 4 dogs

Entropy = -(0.6 * log2(0.6) + 0.4 * log2(0.4))
        = -(0.6 * -0.737 + 0.4 * -1.322)
        = 0.442 + 0.529
        = 0.971 bits

بهره‌ی اطلاعات (Information gain) میزان کاهش ناخالصی (آنتروپی یا جینی) پس از انجام تفکیک است.

$$\begin{aligned} & IG(S, \text{feature}, \text{threshold}) = \text{Impurity}(S) - \text{weighted\_avg}(\text{Impurity}(S_{\text{left}}), \text{Impurity}(S_{\text{right}})) \\[4pt] & \text{where the weights are the proportions of samples in each child.} \end{aligned}$$

الگوریتم حریصانه (greedy) در هر گره به این ترتیب کار می‌کند: تمام ویژگی‌ها و همه‌ی آستانه‌های ممکن را امتحان کن، و زوج (ویژگی، آستانه)ای را بردار که بهره‌ی اطلاعات را به حداکثر می‌رساند.

فرایند تفکیک داده‌ها

در گره فعلی، به ازای مجموعه‌داده‌ای با $n$ ویژگی و $m$ نمونه:

1. به ازای هر ویژگی $j$ (از $j = 1$ تا $n$):
   • نمونه‌ها را بر اساس ویژگی $j$ مرتب کنید
   • میانگین هر دو مقدار متوالی و متمایز را به عنوان آستانه امتحان کنید
   • به ازای هر آستانه، بهره‌ی اطلاعات را محاسبه کنید
2. ویژگی و آستانه‌ای را انتخاب کنید که بیشترین بهره‌ی اطلاعات را دارد
3. داده‌ها را به دو شاخه‌ی چپ (ویژگی <= آستانه) و راست (ویژگی > آستانه) تقسیم کنید
4. همین فرایند را به صورت بازگشتی روی هر دو فرزند تکرار کنید

این روش حریصانه تضمین نمی‌کند که درخت بهینه‌ی سراسری به دست آید، چون پیدا کردن درخت بهینه‌ی سراسری یک مسئله‌ی NP-hard است. با این حال، تفکیک حریصانه در عمل عملکرد بسیار خوبی دارد.

شرط‌های توقف

بدون شرط‌های توقف، درخت آن‌قدر رشد می‌کند تا همه‌ی برگ‌ها خالص شوند یا هیچ تفکیکی نتواند نمونه‌ها را جدا کند؛ وضعیتی که اغلب به یک نمونه در هر برگ ختم می‌شود. در این حالت، درخت داده‌های آموزشی را کامل حفظ می‌کند و قدرت تعمیم افتضاحی خواهد داشت.

پیش‌هرس (Pre-pruning) رشد درخت را پیش از رسیدن به حد نهایی متوقف می‌کند:

• حداکثر عمق (max depth): توقف تقسیم‌بندی وقتی درخت به عمق مشخصی می‌رسد
• حداقل نمونه در هر برگ (min samples per leaf): توقف تقسیم در صورتی که یک گره کمتر از $k$ نمونه داشته باشد
• حداقل بهره‌ی اطلاعات (min information gain): توقف تقسیم در صورتی که بهترین تفکیک، ناخالصی را کمتر از یک حد آستانه بهبود دهد
• حداکثر تعداد گره‌های برگ (max leaf nodes): محدود کردن تعداد کل برگ‌ها

پس‌هرس (Post-pruning) ابتدا اجازه می‌دهد درخت کامل رشد کند، سپس آن را هرس می‌کند:

• هرس پیچیدگی-هزینه (Cost-complexity pruning که در scikit-learn استفاده می‌شود): جریمه‌ای متناسب با تعداد برگ‌ها اضافه می‌کند. با افزایش جریمه، درخت‌های کوچک‌تری به دست می‌آورید
• هرس کاهش خطا (Reduced error pruning): اگر حذف یک زیردرخت خطای اعتبارسنجی را افزایش ندهد، آن زیردرخت را حذف می‌کند

پیش‌هرس ساده‌تر و سریع‌تر است. پس‌هرس اغلب درخت‌های بهتری می‌سازد، چون جلوی تفکیک‌هایی را که شاید بعداً به شاخه‌های مفیدی ختم شوند، زودتر از موعد نمی‌گیرد.

درخت‌های تصمیم برای رگرسیون

در مسائل رگرسیون، پیش‌بینی هر برگ برابر با میانگین مقادیر هدفِ موجود در همان برگ است. معیار تفکیک هم تغییر می‌کند:

کاهش واریانس (Variance reduction) جایگزین بهره‌ی اطلاعات می‌شود:

$$VR(S, \text{feature}, \text{threshold}) = \text{Var}(S) - \text{weighted\_avg}(\text{Var}(S_{\text{left}}), \text{Var}(S_{\text{right}}))$$

تفکیکی را انتخاب کنید که بیشترین کاهش واریانس را به همراه داشته باشد. درخت، فضای ورودی را به چند ناحیه تقسیم می‌کند و در هر ناحیه یک مقدار ثابت (میانگین) را پیش‌بینی می‌کند.

جنگل‌های تصادفی: قدرت مدل‌های گروهی

یک تک‌درخت تصمیم، واریانس بالایی دارد؛ یعنی تغییرات جزئی در داده‌ها می‌تواند درخت‌های کاملاً متفاوتی بسازد. جنگل تصادفی با میانگین گرفتن از تعداد زیادی درخت، این مشکل را حل می‌کند.

دو منبع تصادفی‌سازی، تنوع درخت‌ها را رقم می‌زنند:

بگینگ (Bagging / bootstrap aggregating): هر درخت روی یک نمونه‌ی بوت‌استرپ آموزش می‌بیند؛ یعنی نمونه‌گیری تصادفی با جایگذاری از روی داده‌های آموزشی. حدود 63% از نمونه‌های اولیه در هر بوت‌استرپ قرار می‌گیرند (بقیه نمونه‌های خارج از کیسه یا out-of-bag هستند که می‌توان برای اعتبارسنجی از آن‌ها استفاده کرد).

تصادفی‌سازی ویژگی‌ها (Feature randomization): در هر تفکیک، فقط زیرمجموعه‌ی تصادفی از ویژگی‌ها بررسی می‌شود. مقدار پیش‌فرض برای دسته‌بندی $\sqrt{n_{\text{features}}}$ و برای رگرسیون $n_{\text{features}}/3$ است. این کار مانع از آن می‌شود که همه‌ی درخت‌ها روی یک ویژگی غالب و مشترک تقسیم شوند.

نکته‌ی کلیدی: میانگین‌گیری از چندین درختِ ناهمبسته، بدون افزایش بایاس، واریانس را کاهش می‌دهد. شاید تک‌تک درخت‌ها چنگی به دل نزنند، اما مدل گروهی نهایی بسیار قدرتمند است.

اهمیت ویژگی‌ها

جنگل‌های تصادفی ذاتاً امتیاز اهمیت ویژگی‌ها را در اختیارتان می‌گذارند. رایج‌ترین روش:

کاهش میانگین ناخالصی (MDI): برای هر ویژگی، کل میزان کاهش ناخالصی را در تمام درخت‌ها و همه‌ی گره‌هایی که از آن ویژگی استفاده کرده‌اند، با هم جمع کنید. ویژگی‌هایی که در تفکیک‌های اولیه‌تر باعث کاهش بیشتر ناخالصی می‌شوند، اهمیت بالاتری دارند.

$$\text{importance}(\text{feature}_j) = \sum_{\text{nodes where feature}_j \text{ is used}} \frac{n_{\text{samples at node}}}{n_{\text{total samples}}} \cdot \text{impurity\_decrease}$$

این روش سریع است (چون هنگام آموزش حساب می‌شود)، ولی نسبت به ویژگی‌هایی با کاردینالیتی بالا (تعداد مقادیر یکتای زیاد) و ویژگی‌هایی با نقاط تفکیک پرتعداد، سوگیری دارد.

اهمیت جایگشتی (Permutation importance) روش جایگزین است: مقادیر یک ویژگی را تصادفی به هم می‌ریزید و افت دقت مدل را اندازه می‌گیرید. این روش مطمئن‌تر است، اما محاسبات کندتری دارد.

چه زمانی درخت‌ها شبکه‌های عصبی را شکست می‌دهند؟

روی داده‌های جدولی، درخت‌ها و جنگل‌ها دست بالا را نسبت به شبکه‌های عصبی دارند. به چند دلیل:

شبکه‌های عصبی زمانی برنده می‌شوند که داده‌ها ساختار مکانی یا ترتیبی داشته باشند (تصویر، متن، صدا). برای جدول‌های مسطح داده، درخت‌ها گزینه‌ی پیش‌فرض هستند.

پیاده‌سازی از صفر

مرحله‌ی 1: ناخالصی جینی و آنتروپی

هر دو معیار تفکیک را از صفر بسازید و بررسی کنید که آیا در تشخیص تفکیک‌های مناسب با هم هم‌نظر هستند یا خیر.

import math

def gini_impurity(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return 1.0 - sum((c / n) ** 2 for c in counts.values())

def entropy(labels):
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {}
    for label in labels:
        counts[label] = counts.get(label, 0) + 1
    return -sum(
        (c / n) * math.log2(c / n) for c in counts.values() if c > 0
    )

مرحله‌ی 2: پیدا کردن بهترین تفکیک

تمام ویژگی‌ها و همه‌ی آستانه‌ها را امتحان کنید و حالتی را که بیشترین بهره‌ی اطلاعات را دارد برگردانید.

def information_gain(parent_labels, left_labels, right_labels, criterion="gini"):
    measure = gini_impurity if criterion == "gini" else entropy
    n = len(parent_labels)
    n_left = len(left_labels)
    n_right = len(right_labels)
    if n_left == 0 or n_right == 0:
        return 0.0
    parent_impurity = measure(parent_labels)
    child_impurity = (
        (n_left / n) * measure(left_labels) +
        (n_right / n) * measure(right_labels)
    )
    return parent_impurity - child_impurity

مرحله‌ی 3: ساخت کلاس DecisionTree

تفکیک بازگشتی، پیش‌بینی و ردیابی اهمیت ویژگی‌ها. متد _build قلب تپنده‌ی درخت است: وقتی گره کاملاً خالص شود یا به محدودیت پیش‌هرس برسد متوقف می‌شود؛ در غیر این صورت، بهترین تفکیک را انجام می‌دهد و فرایند را روی هر دو فرزند به صورت بازگشتی اجرا می‌کند.

import random

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2,
                 min_samples_leaf=1, criterion="gini",
                 max_features=None):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.min_samples_leaf = min_samples_leaf
        self.criterion = criterion
        self.max_features = max_features
        self.tree = None
        self.feature_importances_ = None

    def fit(self, X, y):
        self.n_features = len(X[0])
        self.feature_importances_ = [0.0] * self.n_features
        self.n_samples = len(X)
        self.tree = self._build(X, y, depth=0)
        total = sum(self.feature_importances_)
        if total > 0:
            self.feature_importances_ = [
                fi / total for fi in self.feature_importances_
            ]

    def predict(self, X):
        return [self._predict_one(x, self.tree) for x in X]

    def _build(self, X, y, depth):
        if len(set(y)) == 1:
            return {"leaf": True, "value": y[0]}

        if self.max_depth is not None and depth >= self.max_depth:
            return self._make_leaf(y)

        if len(y) < self.min_samples_split:
            return self._make_leaf(y)

        best_feature, best_threshold, best_gain = self._best_split(X, y)

        if best_feature is None or best_gain <= 0:
            return self._make_leaf(y)

        left_X, left_y, right_X, right_y = self._split_data(
            X, y, best_feature, best_threshold
        )

        if len(left_y) < self.min_samples_leaf or len(right_y) < self.min_samples_leaf:
            return self._make_leaf(y)

        weight = len(y) / self.n_samples
        self.feature_importances_[best_feature] += weight * best_gain

        return {
            "leaf": False,
            "feature": best_feature,
            "threshold": best_threshold,
            "left": self._build(left_X, left_y, depth + 1),
            "right": self._build(right_X, right_y, depth + 1),
        }

    def _make_leaf(self, y):
        counts = {}
        for label in y:
            counts[label] = counts.get(label, 0) + 1
        return {"leaf": True, "value": max(counts, key=counts.get)}

    def _best_split(self, X, y):
        best_feature = None
        best_threshold = None
        best_gain = -1.0

        if self.max_features == "sqrt":
            k = max(1, int(math.sqrt(self.n_features)))
            feature_indices = random.sample(range(self.n_features), k)
        elif isinstance(self.max_features, int):
            if self.max_features < 1:
                raise ValueError("max_features must be at least 1 when given as an integer")
            k = min(self.max_features, self.n_features)
            feature_indices = random.sample(range(self.n_features), k)
        else:
            feature_indices = list(range(self.n_features))

        for feature_idx in feature_indices:
            values = sorted(set(X[i][feature_idx] for i in range(len(X))))
            if len(values) <= 1:
                continue

            for i in range(len(values) - 1):
                threshold = (values[i] + values[i + 1]) / 2.0
                left_y = [y[j] for j in range(len(X)) if X[j][feature_idx] <= threshold]
                right_y = [y[j] for j in range(len(X)) if X[j][feature_idx] > threshold]

                if len(left_y) < self.min_samples_leaf or len(right_y) < self.min_samples_leaf:
                    continue

                gain = information_gain(y, left_y, right_y, self.criterion)
                if gain > best_gain:
                    best_gain = gain
                    best_feature = feature_idx
                    best_threshold = threshold

        return best_feature, best_threshold, best_gain

    def _split_data(self, X, y, feature, threshold):
        left_X, left_y, right_X, right_y = [], [], [], []
        for i in range(len(X)):
            if X[i][feature] <= threshold:
                left_X.append(X[i])
                left_y.append(y[i])
            else:
                right_X.append(X[i])
                right_y.append(y[i])
        return left_X, left_y, right_X, right_y

    def _predict_one(self, x, node):
        if node["leaf"]:
            return node["value"]
        if x[node["feature"]] <= node["threshold"]:
            return self._predict_one(x, node["left"])
        return self._predict_one(x, node["right"])

مرحله‌ی 4: ساخت کلاس RandomForest

نمونه‌گیری بوت‌استرپ، تصادفی‌سازی ویژگی‌ها و رأی‌گیری اکثریتی.

class RandomForest:
    def __init__(self, n_trees=100, max_depth=None,
                 min_samples_split=2, max_features="sqrt",
                 criterion="gini"):
        self.n_trees = n_trees
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.max_features = max_features
        self.criterion = criterion
        self.trees = []

    def fit(self, X, y):
        n = len(X)
        for _ in range(self.n_trees):
            indices = [random.randint(0, n - 1) for _ in range(n)]
            X_boot = [X[i] for i in indices]
            y_boot = [y[i] for i in indices]
            tree = DecisionTree(
                max_depth=self.max_depth,
                min_samples_split=self.min_samples_split,
                max_features=self.max_features,
                criterion=self.criterion,
            )
            tree.fit(X_boot, y_boot)
            self.trees.append(tree)

    def predict(self, X):
        all_preds = [tree.predict(X) for tree in self.trees]
        predictions = []
        for i in range(len(X)):
            votes = {}
            for preds in all_preds:
                v = preds[i]
                votes[v] = votes.get(v, 0) + 1
            predictions.append(max(votes, key=votes.get))
        return predictions

برای دیدن پیاده‌سازی کامل به همراه همه‌ی متدهای کمکی، به فایل code/trees.py مراجعه کنید.

استفاده از ابزارهای واقعی

با scikit-learn، آموزش یک جنگل تصادفی در سه خط خلاصه می‌شود:

from sklearn.ensemble import RandomForestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

X, y = load_iris(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)
print(f"Accuracy: {rf.score(X_test, y_test):.4f}")
print(f"Feature importances: {rf.feature_importances_}")

در عمل، درخت‌های ارتقای گرادیان (XGBoost، LightGBM و CatBoost) معمولاً از جنگل‌های تصادفی قوی‌ترند؛ چون درخت‌ها را پشت سر هم می‌سازند و هر درخت جدید، خطاهای درختان قبلی را اصلاح می‌کند. با این حال، تنظیم اشتباه جنگل‌های تصادفی بسیار بعید است و عملاً به هیچ تنظیم ابرپارامتری نیاز ندارند.

تحویل نهایی

حاصل این درس فایل outputs/prompt-tree-interpreter.md است؛ پرامپتی که تفکیک‌های درخت تصمیم را برای ذی‌نفعان کسب‌وکار تفسیر می‌کند. ساختار درخت آموزش‌دیده (عمق، ویژگی‌ها، آستانه‌های تفکیک، دقت) را به آن بدهید تا مدل را به قوانینی با زبان ساده ترجمه کند، رتبه‌ی اهمیت ویژگی‌ها را بسنجد، بیش‌برازش یا نشت داده (data leakage) را پرچم‌گذاری کند و گام‌های بعدی را پیشنهاد دهد. هر زمان که نیاز داشتید یک مدل مبتنی بر درخت را برای کسی که اهل کدنویسی نیست توضیح دهید، از این پرامپت استفاده کنید.

تمرین‌ها

1. یک درخت تصمیم را روی مجموعه‌داده‌ای 2D با 3 کلاس آموزش دهید. تفکیک‌ها را به صورت دستی دنبال کنید و مرزهای تصمیم‌گیری مستطیلی را رسم کنید. مرزها را در دو حالت max_depth=2 و max_depth=10 با هم مقایسه کنید.

2. تفکیک با کاهش واریانس را برای درخت‌های رگرسیون پیاده‌سازی کنید. برای 200 نقطه رابطه‌ی $y = \sin(x) + \text{noise}$ را تولید کرده و درخت رگرسیون خود را روی آن برازش دهید. پیش‌بینی‌های قطعه‌قطعه ثابت درخت را در کنار منحنی واقعی رسم کنید.

3. یک جنگل تصادفی با 1، 5، 10، 50 و 200 درخت بسازید. نمودار دقت آموزش و دقت تست را بر حسب تعداد درخت‌ها رسم کنید. مشاهده کنید که دقت داده‌های تست تثبیت می‌شود اما افت نمی‌کند (مقاومت جنگل در برابر بیش‌برازش).

4. ناخالصی جینی و آنتروپی را به عنوان معیارهای تفکیک روی 5 مجموعه‌داده‌ی مختلف مقایسه کنید. دقت و عمق درخت را اندازه بگیرید. در بیشتر موارد، نتایج تقریباً یکسانی به دست می‌دهند؛ دلیل آن را توضیح دهید.

5. اهمیت جایگشتی را پیاده‌سازی کنید. آن را با معیار MDI روی مجموعه‌داده‌ای مقایسه کنید که یکی از ویژگی‌هایش نویز تصادفی است ولی کاردینالیتی بالایی دارد. MDI این ویژگی نویزی را در رتبه‌ی بالایی قرار می‌دهد؛ بررسی کنید که آیا در اهمیت جایگشتی هم همین اتفاق می‌افتد یا خیر.

اصطلاحات کلیدی

برای مطالعه‌ی بیشتر

• Breiman: Random Forests (2001) - مقاله‌ی اصلی معرفی جنگل‌های تصادفی
• Grinsztajn et al.: Why do tree-based models still outperform deep learning on tabular data? (2022) - مقایسه‌ی دقیق درخت‌ها با شبکه‌های عصبی روی مسائل داده‌های جدولی
• مستندات Decision Trees در scikit-learn - راهنمای عملی همراه با ابزارهای بصری‌سازی
• XGBoost: A Scalable Tree Boosting System (Chen & Guestrin, 2016) - مقاله‌ی اصلی روش گرادیان بوستینگ که در مسابقات کگل پیشتاز است