فصل ۹: درخت تصمیم
عنوان اصلی: Decision Tree
منبع: https://christophm.github.io/interpretable-ml-book/tree.html
نویسنده: Christoph Molnar
مترجم: مریم محمودی
مدلهای خطی و لجستیک در شرایطی که رابطه بین ویژگیها و خروجی غیرخطی است یا ویژگیها با یکدیگر تعامل دارند، عملکرد ضعیفی دارند. درختهای تصمیم این مشکل را به شیوهای کاملاً متفاوت حل میکنند: داده را بر اساس مقادیر آستانهای ویژگیها به زیرمجموعههایی تقسیم میکنند و در هر زیرمجموعه پیشبینی ثابتی ارائه میدهند. درختهای تصمیم هم برای رگرسیون و هم برای دستهبندی به کار میروند.
یک درخت تصمیم از گرهها (nodes) و یالها (edges) تشکیل شده است:
- گره ریشه (root node): نقطه شروع درخت؛ شامل تمام دادههای آموزشی است.
- گرههای داخلی (split nodes): هر گره داده را بر اساس یک قانون «اگر ویژگی $j$ از آستانه $c$ کمتر/بیشتر باشد» به دو شاخه تقسیم میکند.
- گرههای برگ (leaf nodes یا terminal nodes): انتهای درخت؛ پیشبینی نهایی ارائه میدهند.
برای پیشبینی یک نمونه جدید، از ریشه شروع کرده و با دنبال کردن قوانین شاخهبندی تا رسیدن به یک برگ پیش رفته، و پیشبینی آن برگ را برمیگردانیم.
الگوریتم CART
پرکاربردترین الگوریتم آموزش درخت تصمیم، CART (Classification and Regression Trees) است. مدل ریاضی آن به صورت زیر است:
$$\hat{f}(\mathbf{x}) = \sum_{m=1}^{M} c_m \cdot \mathbf{1}{\mathbf{x} \in R_m}$$
که در آن:
- $M$ تعداد گرههای برگ است.
- $R_m$ ناحیهای از فضای ویژگی است که با برگ $m$ متناظر است.
- $c_m$ مقدار پیشبینیشده در برگ $m$ است (میانگین مقادیر هدف در رگرسیون، یا دسته اکثریت در دستهبندی).
- $\mathbf{1}{\mathbf{x} \in R_m}$ تابع نشانگر است که ۱ میشود اگر نمونه $\mathbf{x}$ در ناحیه $R_m$ باشد.
هر نمونه دقیقاً در یک ناحیه $R_m$ قرار میگیرد.
برای درک بهتر (توضیح مترجم): فرض کنید میخواهیم قیمت خانه را با دو ویژگی «متراژ» و «تعداد اتاق» پیشبینی کنیم و درخت فقط دو تقسیم دارد. اگر متراژ کمتر از ۸۰ باشد، وارد برگ $R_1$ میشویم که میانگین قیمت آن ۱۵۰ میلیون تومان است ($c_1 = 150$)؛ در غیر این صورت به تقسیم بعدی میرویم و بسته به تعداد اتاق، وارد $R_2$ ($c_2 = 220$) یا $R_3$ ($c_3 = 300$) میشویم. برای خانهای با متراژ ۶۰، تابع نشانگر فقط برای $R_1$ برابر ۱ و برای بقیهٔ نواحی برابر صفر است؛ بنابراین $\hat{f}(\mathbf{x}) = c_1 = 150$. یعنی فرمول بالا صرفاً میگوید: «ببین نمونه در کدام برگ افتاده و مقدار همان برگ را برگردان.»
چگونه تقسیمبندیها انتخاب میشوند؟
CART در هر مرحله، تقسیمی را انتخاب میکند که معیار زیر را بیشینه کاهش دهد:
- رگرسیون: واریانس خروجی در هر شاخه.
- دستهبندی: ناخالصی گینی (Gini impurity) یا آنتروپی اطلاعات.
مثال مترجم برای درک بهتر خوانندگان: فرض کنید در یک گره ۱۰ نمونه داریم: ۵ تای آنها کلاس «مثبت» و ۵ تای دیگر کلاس «منفی» هستند. ناخالصی گینی این گره برابر است با $1 - (0.5^2 + 0.5^2) = 0.5$، یعنی بیشترین مقدار ممکن (کاملاً ناخالص). حالا اگر با یک تقسیم، گره را به دو زیرگره تبدیل کنیم که در یکی ۴ نمونهٔ «مثبت» و ۱ نمونهٔ «منفی» باشد و در دیگری ۱ نمونهٔ «مثبت» و ۴ نمونهٔ «منفی»، ناخالصی گینی هر زیرگره برابر $1 - (0.8^2 + 0.2^2) = 0.32$ میشود که کمتر از ۰٫۵ اولیه است. CART دقیقاً چنین تقسیمی را ترجیح میدهد، چون ناخالصی را کاهش میدهد و کلاسهای هر زیرگره را «خالصتر» میکند.
این فرایند به صورت بازگشتی ادامه مییابد تا زمانی که معیار توقف فعال شود — مثلاً وقتی تعداد نمونهها در یک گره پیش از تقسیم، یا تعداد نمونهها در یک گره برگ، به زیر حد مجاز برسد.
برای ویژگیهای دستهای، الگوریتم گروهبندیهای مختلف از دستهها را میآزماید تا بهترین تقسیم را بیابد. پس از یافتن بهترین نقطهٔ برش برای هر ویژگی، الگوریتم آن ویژگی را انتخاب میکند که بهترین تفکیک را از نظر واریانس یا ناخالصی گینی ایجاد کند و این تقسیم را به درخت اضافه میکند.
برای معرفی دقیقتر CART، کتاب «The Elements of Statistical Learning» (Hastie 2009) توصیه میشود؛ در این فصل تمرکز اصلی بر CART است، اما تفسیر برای بیشتر انواع دیگر درختهای تصمیم مشابه است.
شکل ۹.۱: ساختار یک درخت تصمیم مصنوعی. هر گره داخلی یک قانون تقسیم بر اساس یک ویژگی و آستانه دارد. برگها مقادیر پیشبینی را نگه میدارند.
تفسیر
تفسیر قاعدهمحور
برای تفسیر پیشبینی یک نمونه، کافی است مسیر آن از ریشه تا برگ را دنبال کنیم. هر گره داخلی یک شرط «اگر—آنگاه» است و تمام شرطها با AND به هم متصل میشوند:
«اگر ویژگی $x_j$ [کمتر/بیشتر] از آستانه $c$ باشد و ... آنگاه پیشبینی برابر میانگین مقادیر هدف نمونههای آن برگ است.»
این قالب تفسیر کاملاً ساده و شهودی است — هر کسی میتواند مسیر تصمیمگیری را گام به گام دنبال کند.
اهمیت ویژگیها
اهمیت هر ویژگی در درخت تصمیم با میزان کاهشی که آن ویژگی در ناخالصی (واریانس یا گینی) ایجاد کرده اندازهگیری میشود. اگر ویژگی $j$ در چند گره مختلف مورد استفاده قرار گرفته، مجموع کاهشهای ناشی از تمام آن تقسیمها جمع میشود. در نهایت این اعداد به نحوی مقیاس میشوند که مجموعشان ۱۰۰ باشد و هر عدد سهم آن ویژگی از اهمیت کلی مدل را نشان دهد.
هشدار: اهمیت گینی (Gini importance) به نفع ویژگیهای عددی و ویژگیهای دستهای با دستههای زیاد تورش دارد (Strobl et al. 2008). برای ارزیابی دقیقتر، استفاده از اهمیت ویژگی مبتنی بر جایگشت (permutation feature importance) توصیه میشود.
تجزیه پیشبینی بر اساس ویژگیها
یکی از قابلیتهای جالب درخت تصمیم این است که میتوان پیشبینی هر نمونه را به سهم هر ویژگی تجزیه کرد. گره ریشه میانگین کلی دادههای آموزشی ($\bar{y}$) را پیشبینی میکند. هر تقسیم در مسیر نمونه تا برگ، مقداری به این میانگین اضافه یا از آن کم میکند:
$$\hat{f}(\mathbf{x}) = \bar{y} + \sum_{d=1}^{D} \text{split.contrib}(d, \mathbf{x}) = \bar{y} + \sum_{j=1}^{p} \text{feat.contrib}(j, \mathbf{x})$$
که در آن:
- $D$ عمق درخت (تعداد گرههای داخلی در مسیر) است.
- $\text{split.contrib}(d, \mathbf{x})$ سهم تقسیم $d$ام در پیشبینی نمونه $\mathbf{x}$ است.
- $\text{feat.contrib}(j, \mathbf{x})$ مجموع سهم تمام تقسیمهایی است که از ویژگی $j$ استفاده کردهاند.
یک ویژگی ممکن است چندین بار در مسیر ظاهر شود؛ سهمهای آن جمع میشوند. ویژگیهایی که اصلاً در مسیر نمونه استفاده نشدهاند سهم صفر دارند. این تجزیه نوعی توضیح محلی (local explanation) برای هر پیشبینی منفرد فراهم میکند.
مثال مترجم برای درک بهتر خوانندگان: فرض کنید میانگین قیمت همهٔ خانههای دادهی آموزشی ($\bar{y}$) برابر ۲۰۰ میلیون تومان است. برای خانهای خاص، اولین تقسیم بر اساس متراژ است و چون متراژ خانه بزرگتر از آستانه است، ۳۰ میلیون تومان به پیشبینی اضافه میشود. تقسیم دوم بر اساس تعداد اتاقهاست و چون تعداد اتاق کمتر از آستانه است، ۱۰ میلیون تومان از پیشبینی کم میشود. پیشبینی نهایی برابر است با $200 + 30 - 10 = 220$ میلیون تومان. اگر متراژ در مسیر دیگری هم دوباره استفاده شده باشد، سهم آن تقسیم هم به سهم قبلی «متراژ» اضافه میشود؛ در نهایت میتوانیم بگوییم مثلاً «متراژ» ۳۵ میلیون تومان و «تعداد اتاق» منفی ۱۵ میلیون تومان در پیشبینی این خانهٔ خاص سهیم بودهاند.
مثال
از دادههای اجاره دوچرخه برای پیشبینی تعداد دوچرخههای اجارهشده در یک روز مشخص با یک درخت تصمیم استفاده میکنیم. حداکثر عمق مجاز درخت را ۲ در نظر گرفتهایم:
شکل ۹.۲: درخت تصمیم با عمق ۲ برای پیشبینی تعداد دوچرخههای اجارهشده روزانه. دو ویژگی انتخابشده عبارتند از تعداد دوچرخههای اجارهشده دو روز پیش (cnt_2d_bfr) و دما.
درخت دو ویژگی انتخاب کرده است: تعداد دوچرخههای اجارهشده دو روز پیش و دما. قاعده کلی این است: هر چه تعداد اجاره اخیر بیشتر، پیشبینی نیز بیشتر. وقتی تعداد اجاره اخیر کم باشد، دما تعیینکننده پیشبینی میشود.
برای درختهای عمیقتر، اهمیت ویژگیها به این صورت رتبهبندی میشود:
شکل ۹.۳: اهمیت ویژگیها در درخت تصمیم عمیقتر برای دادههای اجاره دوچرخه. تعداد دوچرخه دو روز قبل مهمترین ویژگی است، سپس دما، فصل، و آبوهوا.
مزایا
گرفتن تعاملات: ساختار درختی بهطور طبیعی تعاملات بین ویژگیها را نشان میدهد؛ هر تقسیم در یک گره فرزند، تنها برای زیرمجموعهای از دادهها اعمال میشود که از مسیر خاصی آمدهاند.
گروهبندی طبیعی: تقسیم داده به گروههای مجزا اغلب شهودیتر از خطالرأسهای چندبُعدی در رگرسیون خطی است.
قابلیت تجسم: درخت را میتوان بهراحتی رسم کرد و هر کسی بدون دانش آماری میتواند آن را بفهمد. برای درختهای کمعمق (یک تا سه سطح)، تفسیر بسیار آسان است.
توضیحات انسانپسند: ساختار درخت تصمیم توضیحهایی خوب، آنگونه که در فصل «توضیحات انسانپسند» تعریف شده، تولید میکند. این ساختار بهطور طبیعی ما را به فکر کردن دربارهٔ پیشبینی هر نمونه به شکل خلافواقع (counterfactual) دعوت میکند: «اگر یک ویژگی بزرگتر/کوچکتر بود، پیشبینی بهجای y2 برابر y1 میشد.» این توضیحات contrastive هستند، چون همیشه میتوان پیشبینی یک نمونه را با سناریوهای «چه میشد اگر» مرتبط (که همان برگهای دیگر درخت هستند) مقایسه کرد. اگر درخت کوتاه باشد — مثلاً یک تا سه تقسیم عمق داشته باشد — توضیحهای حاصل selective هم هستند: درختی با عمق سه، حداکثر به سه ویژگی و نقطهٔ تقسیم برای توضیح پیشبینی یک نمونه نیاز دارد. صداقت (truthfulness) پیشبینی به عملکرد پیشبینی درخت بستگی دارد. توضیحهای درختهای کوتاه بسیار ساده و کلی هستند، چون در هر تقسیم، نمونه یا به یک برگ میرود یا به برگ دیگر، و تصمیمهای دودویی بهراحتی قابلفهماند.
بینیازی به تبدیل ویژگی: در مدلهای خطی، گاهی لازم است از یک ویژگی لگاریتم گرفته شود. اما درخت تصمیم با هر تبدیل یکنوای یک ویژگی، به همان خوبی کار میکند و نیازی به نرمالسازی یا استانداردسازی نیست.
مقیاس ویژگی اهمیتی ندارد: CART و سایر الگوریتمهای درخت نسبت به مقیاس و تبدیلهای یکنوای ویژگیها ناوردا (invariant) هستند. برای مثال، تبدیل واحد یک ویژگی از کیلوگرم به گرم (ضرب در ۱۰۰۰) مقدار نقطهٔ تقسیم را تغییر میدهد، اما ساختار کلی درخت بدون تغییر باقی میماند.
تصمیمهای دودویی ساده: درختهای کمعمق (۱ تا ۳ تقسیم) فقط به تعداد کمی ویژگی نیاز دارند و بسیار آسان درک میشوند.
محدودیتها
ضعف در روابط خطی: وقتی رابطه واقعی بین ویژگی و خروجی خطی است، درخت تصمیم مجبور است آن را با یک تابع پلهای تقریب بزند. این تقریب ناکارآمد است و به تقسیمبندیهای بسیار زیادی نیاز دارد تا به دقت یک خط مستقیم برسد.
ناپیوستگی پیشبینیها (فقدان صافی): تغییرات جزئی در یک ویژگی ورودی میتواند تأثیر بزرگی روی پیشبینی داشته باشد، که معمولاً مطلوب نیست. فرض کنید درختی برای پیشبینی قیمت یک خانه، متراژ را یکی از ویژگیهای تقسیمکننده انتخاب کرده و تقسیم دقیقاً در نقطهٔ ۱۰۰٫۵ متر مربع رخ میدهد. کاربری را تصور کنید که از این درخت برای برآورد قیمت خانهاش استفاده میکند: او خانه را اندازه میگیرد، به این نتیجه میرسد که مساحت آن ۹۹ متر مربع است، آن را در ماشینحساب قیمت وارد میکند و پیشبینی ۲۰۰٬۰۰۰ یورو دریافت میکند. سپس متوجه میشود که فراموش کرده یک انباری کوچک با مساحت ۲ متر مربع را اندازه بگیرد. این انباری دیوار شیبدار دارد، بنابراین کاربر مطمئن نیست که باید کل مساحت آن را حساب کند یا فقط نیمی از آن را. پس تصمیم میگیرد هر دو حالت ۱۰۰ و ۱۰۱ متر مربع را امتحان کند. نتیجه: ماشینحساب قیمت به ترتیب ۲۰۰٬۰۰۰ و ۲۰۵٬۰۰۰ یورو خروجی میدهد، که کاملاً ضدشهودی است، چرا که از ۹۹ به ۱۰۰ متر مربع هیچ تغییری در پیشبینی رخ نداده بود.
ناپایداری: درخت تصمیم واریانس بالایی دارد. تغییرات کوچک در دادههای آموزشی میتوانند ساختار کاملاً متفاوتی از درخت ایجاد کنند، چون هر تقسیم بعدی به نتیجه تقسیمهای قبلی وابسته است. این ناپایداری یکی از دلایل اصلی محبوبیت جنگل تصادفی (Random Forest) است که با ترکیب درختهای متعدد این واریانس را کاهش میدهد.
مشکل مقیاسپذیری با عمق: تعداد گرههای برگ با عمق بهسرعت افزایش مییابد. یک درخت دودویی با عمق $d$ حداکثر $2^d$ گره برگ دارد. درخت با عمق ۱۰ میتواند تا ۱۰۲۴ برگ داشته باشد — تفسیر چنین درختی دیگر ممکن نیست.
نرمافزار
برای مثالهای این فصل از بستهٔ rpart در R استفاده شده که الگوریتم CART (Classification and Regression Trees) را پیادهسازی میکند. CART در زبانهای برنامهنویسی مختلف، از جمله Python، در دسترس است. باید توجه داشت که CART الگوریتمی نسبتاً قدیمی و تا حدی منسوخشده است و الگوریتمهای جدید و جالبی برای برازش درختها وجود دارند. برای مروری بر برخی از بستههای R مربوط به درخت تصمیم، میتوانید به صفحهٔ CRAN Task View یادگیری ماشین و یادگیری آماری زیر کلیدواژهٔ «Recursive Partitioning» مراجعه کنید. در Python، بستهٔ imodels الگوریتمهای مختلفی برای رشد درختهای تصمیم (مثلاً برازش حریصانه در برابر بهینه)، هرس درختها، و منظمسازی درختها ارائه میدهد.
درخت تصمیم انتخاب ایدهآلی است وقتی تفسیرپذیری اولویت اول است، دادهها تعاملات غیرخطی دارند، یا میخواهیم یک مدل بصری برای ارائه به ذینفعان غیرفنی داشته باشیم. برای عملکرد پیشبینی بهتر، روشهای گروهی مانند جنگل تصادفی یا گرادیان بوستینگ ترجیح دارند.