فصل ۶: درخت‌های تصمیم

درخت‌های تصمیم الگوریتم‌هایی همه‌کاره در یادگیری ماشین هستند که می‌توانند مسائل طبقه‌بندی، رگرسیون و حتی مسائل چندخروجی را حل کنند. این الگوریتم‌ها توانایی برازش مجموعه‌داده‌های پیچیده را دارند. در فصل ۲ نمونه‌ای از DecisionTreeRegressor روی داده‌های مسکن کالیفرنیا آموزش داده شد که دادهٔ آموزشی را کاملاً برازش کرد؛ هرچند در واقع دچار بیش‌برازش شده بود.

درخت‌های تصمیم همچنین اجزای بنیادی جنگل‌های تصادفی هستند؛ الگوریتم‌هایی که در فصل ۷ معرفی می‌شوند و از قدرتمندترین روش‌های رایج یادگیری ماشین به شمار می‌آیند. در این فصل ابتدا آموزش، نمایش و پیش‌بینی با درخت تصمیم بررسی می‌شود، سپس الگوریتم آموزشی CART در Scikit-Learn، منظم‌سازی درخت‌ها، رگرسیون با درخت و در پایان محدودیت‌های این مدل‌ها توضیح داده خواهد شد.

آموزش و نمایش یک درخت تصمیم

برای درک بهتر، یک درخت تصمیم روی مجموعه‌دادهٔ Iris آموزش می‌دهیم:

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

iris = load_iris(as_frame=True)
X_iris = iris.data[["petal length (cm)", "petal width (cm)"]].values
y_iris = iris.target

tree_clf = DecisionTreeClassifier(max_depth=2, random_state=42)
tree_clf.fit(X_iris, y_iris)

برای نمایش درخت آموزش‌دیده ابتدا می‌توان با export_graphviz() تعریف گراف را در فایل iris_tree.dot ذخیره کرد:

from sklearn.tree import export_graphviz

export_graphviz(
    tree_clf,
    out_file="iris_tree.dot",
    feature_names=["petal length (cm)", "petal width (cm)"],
    class_names=iris.target_names,
    rounded=True,
    filled=True
)

سپس در Jupyter می‌توان فایل را با Graphviz بارگذاری و نمایش داد:

from graphviz import Source
Source.from_file("iris_tree.dot")

Graphviz نرم‌افزار متن‌باز نمایش گراف است و ابزار خط فرمان dot نیز دارد که فایل‌های .dot را به قالب‌هایی مانند PDF یا PNG تبدیل می‌کند. درخت حاصل در شکل ۶-۱ دیده می‌شود.

انجام پیش‌بینی

فرض کنید می‌خواهیم یک گل Iris را فقط با طول و عرض گلبرگ طبقه‌بندی کنیم. حرکت از گرهٔ ریشه در عمق صفر آغاز می‌شود. نخستین پرسش این است که آیا طول گلبرگ کمتر یا مساوی حدود 2.45 cm است یا نه. اگر پاسخ مثبت باشد، به فرزند سمت چپ در عمق یک می‌رویم. این گره یک برگ است و فرزند دیگری ندارد؛ بنابراین درخت مستقیماً کلاس Iris setosa را پیش‌بینی می‌کند.

اگر طول گلبرگ بزرگ‌تر از ۲٫۴۵ سانتی‌متر باشد، مسیر به گرهٔ راست ریشه می‌رود. این گره برگ نیست و پرسش دیگری مطرح می‌کند: آیا عرض گلبرگ کمتر یا مساوی حدود ۱٫۷۵ سانتی‌متر است؟ اگر بله، نمونه به احتمال زیاد Iris versicolor و در غیر این صورت Iris virginica است.

ویژگی samples در هر گره تعداد نمونه‌های آموزشی‌ای را نشان می‌دهد که به آن گره رسیده‌اند. برای مثال در شکل ۶-۱، ۱۰۰ نمونه طول گلبرگ بالاتر از ۲٫۴۵ سانتی‌متر دارند و به شاخهٔ راست ریشه می‌روند؛ از میان آن‌ها ۵۴ نمونه عرض گلبرگ کمتر از ۱٫۷۵ سانتی‌متر دارند.

ویژگی value تعداد نمونه‌های هر کلاس را در آن گره نشان می‌دهد. مثلاً گرهٔ پایین-راست شامل ۰ نمونه Setosa، یک نمونه Versicolor و ۴۵ نمونه Virginica است.

ویژگی gini میزان ناخالصی Gini را اندازه می‌گیرد. اگر همهٔ نمونه‌های یک گره از یک کلاس باشند، گره «خالص» است و gini=0. گرهٔ سمت چپ در عمق یک فقط Setosa دارد و بنابراین کاملاً خالص است. ناخالصی Gini گرهٔ i از رابطهٔ زیر محاسبه می‌شود:

در این رابطه، Gᵢ ناخالصی گرهٔ i و pᵢ,ₖ نسبت نمونه‌های کلاس k در همان گره است. برای نمونه، گرهٔ چپ در عمق ۲ ناخالصی تقریبی 1 − (0/54)² − (49/54)² − (5/54)² ≈ 0.168 دارد.

شکل ۶-۲ مرزهای تصمیم همین درخت را نشان می‌دهد. خط عمودی ضخیم مرز ریشه در petal length = 2.45 cm است. بخش چپ کاملاً خالص است و دیگر تقسیم نمی‌شود. بخش راست ناخالص است، بنابراین گرهٔ عمق یک آن را در petal width = 1.75 cm تقسیم می‌کند. چون max_depth=2 است، درخت در همین نقطه متوقف می‌شود. اگر عمق حداکثر ۳ بود، گره‌های عمق ۲ نیز مرزهای جدیدی اضافه می‌کردند.

ساختار کامل درخت و اطلاعات گره‌ها از طریق ویژگی tree_ در دسترس است. برای جزئیات می‌توان help(tree_clf.tree_) را بررسی کرد.

تفسیر مدل: جعبهٔ سفید در برابر جعبهٔ سیاه

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

برای مثال اگر یک شبکهٔ عصبی تشخیص دهد شخص خاصی در تصویر حضور دارد، مشخص نیست دقیقاً کدام نشانه بیشترین نقش را داشته است: چشم‌ها، دهان، بینی، کفش یا حتی مبل پشت سر فرد. در مقابل، درخت تصمیم مجموعه‌ای از قواعد روشن فراهم می‌کند که حتی در صورت نیاز می‌توان آن‌ها را دستی اجرا کرد. حوزهٔ یادگیری ماشین تفسیرپذیر به دنبال سامانه‌هایی است که بتوانند تصمیم‌های خود را به شکلی قابل فهم برای انسان توضیح دهند؛ موضوعی مهم در کاربردهایی که باید از تصمیم‌های ناعادلانه یا غیرقابل‌توضیح جلوگیری شود.

برآورد احتمال کلاس

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

فرض کنید گلبرگ نمونه‌ای طول ۵ سانتی‌متر و عرض ۱٫۵ سانتی‌متر دارد. مسیر آن به برگ چپ در عمق ۲ می‌رسد. در آن برگ نسبت کلاس‌ها ۰ از ۵۴ برای Setosa، ۴۹ از ۵۴ برای Versicolor و ۵ از ۵۴ برای Virginica است؛ یعنی تقریباً ۰٪، ۹۰٫۷٪ و ۹٫۳٪. بنابراین کلاس Versicolor انتخاب می‌شود:

>>> tree_clf.predict_proba([[5, 1.5]]).round(3)
array([[0.   , 0.907, 0.093]])
>>> tree_clf.predict([[5, 1.5]])
array([1])

نکته این است که در تمام ناحیه‌ای که به همین برگ منتهی می‌شود، احتمال‌های برآوردی دقیقاً یکسان هستند؛ حتی اگر نقطه‌ای در آن ناحیه از نظر هندسی به یک کلاس خاص نزدیک‌تر به نظر برسد.

الگوریتم آموزشی CART

Scikit-Learn برای آموزش یا «رشد» درخت تصمیم از الگوریتم Classification and Regression Tree (CART) استفاده می‌کند. الگوریتم ابتدا مجموعهٔ آموزشی را با استفاده از یک ویژگی k و یک آستانه tₖ به دو زیرمجموعه تقسیم می‌کند؛ مثلاً شرط «طول گلبرگ ≤ ۲٫۴۵».

CART زوج (k,tₖ) را به‌گونه‌ای انتخاب می‌کند که دو زیرمجموعهٔ حاصل، با درنظرگرفتن اندازهٔ آن‌ها، بیشترین خلوص را داشته باشند. تابع هزینهٔ طبقه‌بندی چنین است:

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

بازگشت زمانی متوقف می‌شود که عمق حداکثر تعیین‌شده با max_depth حاصل شود، یا دیگر تقسیمی پیدا نشود که ناخالصی را کاهش دهد. فراپارامترهایی مانند min_samples_split، min_samples_leaf، min_weight_fraction_leaf و max_leaf_nodes نیز شرایط توقف بیشتری ایجاد می‌کنند.

پیچیدگی محاسباتی

برای پیش‌بینی کافی است مسیر از ریشه تا یک برگ طی شود. درخت‌ها معمولاً تقریباً متعادل هستند و طول این مسیر حدود O(log₂(m)) گره است. چون در هر گره فقط مقدار یک ویژگی بررسی می‌شود، پیچیدگی پیش‌بینی تقریباً O(log₂(m)) و مستقل از تعداد ویژگی‌ها است؛ در نتیجه پیش‌بینی حتی روی مجموعه‌های آموزشی بزرگ بسیار سریع است.

در آموزش، در هر گره ویژگی‌ها روی نمونه‌ها بررسی می‌شوند. اگر همهٔ n ویژگی روی همهٔ m نمونه بررسی شوند، پیچیدگی تقریبی آموزش O(n × m log₂(m)) خواهد بود.

ناخالصی Gini یا Entropy؟

DecisionTreeClassifier به‌طور پیش‌فرض از ناخالصی Gini استفاده می‌کند، اما با قرار دادن criterion="entropy" می‌توان Entropy را انتخاب کرد. مفهوم Entropy ابتدا در ترمودینامیک برای سنجش بی‌نظمی مولکولی مطرح شد و بعد در نظریهٔ اطلاعات Shannon به سنجش متوسط محتوای اطلاعاتی یک پیام گسترش یافت. وقتی همهٔ پیام‌ها یکسان باشند Entropy صفر است. در یادگیری ماشین نیز اگر یک گره فقط نمونه‌های یک کلاس را داشته باشد، Entropy آن صفر خواهد بود.

برای نمونه، Entropy گرهٔ چپ در عمق ۲ در شکل ۶-۱ تقریباً برابر −(49/54)log₂(49/54) − (5/54)log₂(5/54) ≈ 0.445 است.

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

فراپارامترهای منظم‌سازی

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

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

برای کنترل بیش‌برازش باید آزادی درخت در زمان آموزش محدود شود. ساده‌ترین ابزار، محدودکردن عمق با max_depth است. مقدار پیش‌فرض None به معنی نبود محدودیت است. کاهش عمق مدل را منظم‌تر می‌کند.

به‌طور کلی افزایش فراپارامترهای min_* یا کاهش فراپارامترهای max_* باعث منظم‌تر شدن درخت می‌شود.

نمونهٔ عملی منظم‌سازی

روی مجموعهٔ moons دو درخت آموزش می‌دهیم: یکی بدون منظم‌سازی و دیگری با min_samples_leaf=5:

from sklearn.datasets import make_moons

X_moons, y_moons = make_moons(
    n_samples=150, noise=0.2, random_state=42
)

tree_clf1 = DecisionTreeClassifier(random_state=42)
tree_clf2 = DecisionTreeClassifier(min_samples_leaf=5, random_state=42)

tree_clf1.fit(X_moons, y_moons)
tree_clf2.fit(X_moons, y_moons)

درخت بدون محدودیت در سمت چپ آشکارا بیش‌برازش دارد، در حالی که مرز تصمیم مدل منظم‌شده در سمت راست نرم‌تر و احتمالاً قابل‌تعمیم‌تر است. این موضوع با مجموعهٔ آزمونی که Seed متفاوتی دارد نیز تأیید می‌شود:

>>> X_moons_test, y_moons_test = make_moons(
...     n_samples=1000, noise=0.2, random_state=43)
...
>>> tree_clf1.score(X_moons_test, y_moons_test)
0.898
>>> tree_clf2.score(X_moons_test, y_moons_test)
0.92

مدل دوم روی مجموعهٔ آزمون دقت بالاتری دارد.