درخت تصمیم در یادگیری ماشین

درخت تصمیم یا Decision Tree یکی از کلیدی‌ترین مباحث در یادگیری ماشین است. در این پست، گام به گام مبحث درخت تصمیم در یادگیری ماشین را به شما آموزش می‌دهم. با من و هوسم جان همراه باشید…

درخت و یادگیری ماشین

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

• ریشه
• تنه
• شاخه‌ها
• برگ‌ها

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

حالا که با درخت آشنا شدید، می‌توانیم بحث ساختمان داده درختی را شروع کنیم. آشنا شدید! انگار نمی‌دونستید درخت چیه! 😅

ساختمان داده درختی (Tree Data Structure)

ساختمان داده یکی از پایه‌ای‌ترین مباحث حوزه علوم کامپیوتر هست. نیازی نیست که عمیقا وارد این مبحث شویم. به همین اندازه بسنده کنیم که:

ساختمان داده، شامل روش‌ها و ساختارهایی برای ذخیره‌سازی و مدیریت داده‌ها به شکل کارآمد و بهینه است.

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

• در ساختار درختی، نگاه از بالا به پایین داریم. برخلاف درخت واقعی که از پایین به بالا نگاه می‌کردیم.
• سه نوع گره یا Node در ساختار درختی داریم.
• گره قرمز: گره ریشه یا Root Node نام دارد. همه چیز از این گره شروع می‌شود و گره والد هم نام دارد.
• گره آبی: گره داخلی یا Inner Node نام دارد. این گره هم والد هست و هم فرزند!
• گره سبز: برگ یا Leaf Node نام دارد. این گره والد نیست و فقط فرزند هست!
• فقط یک گره ریشه داریم، اما ممکن هست بیش از یک گره داخلی و برگ داشته باشیم.
• شاخه یا یال یا Branch: متصل‌کننده گره‌ها.
• زیردرخت یا Sub Tree: یک تکه از درخت را زیردرخت یا Sub Tree می‌نامیم. مستطیل سبز!
• عمق یا Depth: تعداد یال‌های بین گره ریشه تا یک گره مشخص. مثلا، عمق درخت از بالا تا پایین، سه هست. یال‌های بنفش!
• بسه دیگه! 😀

خُب خُب، دیگر می‌توانیم وارد بحث اصلی یعنی درخت تصمیم در یادگیری ماشین شویم.

درخت تصمیم یا Decision Tree

تمامی توضیحاتم تا اینجا برای این بود که کلمه درخت در درخت تصمیم را درک کنید. پس آنچه که تا اینجا ما می‌دانیم این هست که:

درخت تصمیم یک الگوریتم یادگیری ماشین مبتنی بر ساختار داده درختی با نمایش سلسله مراتبی است.

با تعریف بالا کلمه تصمیم یا Decision در درخت تصمیم هم معنا پیدا می‌کند؛ یک الگوریتم یادگیری ماشین که می‌تواند در تسک‌های رگرسیون و طبقه بندی استفاده شود. یعنی، تصمیم‌گیری می‌کند! اما می‌خواهم به کلمه تصمیم از یک زاویه دیگر هم نگاه کنید؛ در شکل زیر، یک درخت تصمیم را مشاهده می‌کنید. این نمایش برای شما آشناست. همان گره ها و یال ها که در ساختار داده درختی دیدیم. سه نوع گره داشتیم: گره ریشه، گره داخلی و برگ. نکته مهم این هست که گره داخلی با نام گره تصمیم یا Decision Node شناخته می‌شود. چرا؟ چون واقعا در این نوع گره، تصمیم گیری انجام می‌شود. مثلا به گره بنفش x₁<=1 نگاه کنید. مشخص است که این گره فیچر x₁ از دیتاست را بررسی می‌کند:

• اگر مقدار x₁ از 1 کمتر باشد، به شاخه چپ می‌رویم.
• درغیراینصورت، به شاخه راست می‌رویم.

در ادامه، می‌خواهم درباره نحوه تفسیر درخت تصمیم بالا را تشریح کنم.

تفسیر درخت تصمیم در یادگیری ماشین

فعلا کاری به این نداریم که درخت تصمیم بالا چگونه ساخته شده است. الان تمرکزمان روی درک نحوه کار کردن درخت تصمیم هست. درخت بالا مربوط به یک دیتاست طبقه بندی با دو کلاس هست که هر نمونه شامل دو ویژگی عددی x₁ و x₂ است. بیایید برای یک نمونه داده با مقادیر x=[x₁, x₂]=[0.3, 0.5] ببینیم چه اتفاقی می‌افتد:

• از گره ریشه شروع می‌کنیم. گره ریشه روی x₁ تعریف شده است.
• اگر مقدار x₁ در نمونه ما کمتر از 0.95- باشد، داده به کلاس قرمز تعلق دارد.
• اما اینطور نیست و باید از شاخه راست وارد یک گره تصمیم شویم.
• این گره تصمیم بازهم روی x₁ تعریف شده است. با توجه به مقدار x₁، شاخه چپ لطفا!
• گره تصمیم جدید روی x₂ تعریف شده است. با توجه به مقدار x₂ شاخه چپ انتخاب می‌شود.
• بنـــــابــــراین، نمونه داده ما به کلاس آبی تعلق دارد. 😊

تمرین: برای داده x=[x₁, x₂]=[-0.95, 0.4] و x=[x₁, x₂]=[0.1.5, -0.5] همین روند بالا را طی کنید. جواب را کامنت کنید.

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

انواع درخت تصمیم در یادگیری ماشین

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

• ID3
• C4.5
• CART 🔥

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

درخت تصمیم ID3

الگوریتم ID3 (Iterative Dichotomiser 3) یکی از نخستین و بنیادی‌ترین روش‌های ساخت درخت تصمیم در یادگیری ماشین است که توسط Ross Quinlan در سال ۱۹۸۶ معرفی شد. امروزه، این الگوریتم کمتر استفاده می‌شود؛ اما، سادگی آن باعث شده که بسیاری از منابع، آموزشِ مبحث درخت تصمیم را با این الگوریتم شروع کنند.

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

درادامه، می‌خواهم به‌صورت مختصر توضیح دهم که الگوریتم درخت تصمیم ID3 چگونه کار می‌کند. بهتر است کار با یک دیتاست نمونه پیش ببریم. با الگوگیری از منابع آموزشی مختلفريال من دیتاست برگزاری بازی گلف را برای اینجا انتخاب کرده‌ام. تصور کنید، دیتاست ما شامل 4 ویژگی چشم‌انداز، رطوبت، دما و باد است. این دیتاست مربوط به برگزاری بازی گلف با دو کلاس است. برگزارمی‌شود/برگزارنمی‌شود.

الگوریتم درخت تصمیم ID3 در یادگیری ماشین

درادامه، به‌صورت مرحله‌به‌مرحله الگوریتم درخت تصمیم ID3 را توضیح می‌دهم. پیشنهاد می‌کنم توضیحات مراحل را با نگاه کردن دیتاست بالا به انیمیشن زیر دنبال کنید:

1. با گره ریشه شروع می‌کنیم؛ گره ریشه، ارزشمندترین گره درخت تصمیم ماست. ما می‌خواهیم ویژگی‌ای را در این گره قرار دهیم که بیشترین ارزش را داشته باشد. به نظر شما باارزش‌ترین ویژگی یعنی چه؟ یعنی، بهترین تفکیک‌سازی بین کلاس 0 و 1. چگونه تعیین می‌شود؟ نیاز به یک معیار ارزیابی داریم. در درخت‌های تصمیم مختلف، معیارهای ارزیابی متفاوت است. اینجا، از معیار ارزیابی بهره اطلاعاتی (IG) استفاده می‌شود. فعلا مهم نیست که بدانید فرمولش چیست و چگونه کار می‌کند. فعلا تمرکزمان روی این هست که کلیات نحوه تشکیل درخت تصمیم را یاد بگیرید. به هرصورت معیاری به‌نام بهره اطلاعاتی (IG) داریم که بین این 4 ویژگی، ویژگی باارزش‌تر را انتخاب می‌کند.
2. طبق معیار بهره اطلاعاتی (IG) ویژگی با ارزش انتخاب‌شده چشم‌انداز است.
3. در دیتاست، ویژگی چشم‌انداز سه حالت آفتابی، ابری و بارانی دارد. ما هم برای هر حالت در این ویژگی یک شاخه رسم می‌کنیم. در ID3 تعداد شاخه‌ها برابر با تعداد حالات در ویژگی است. اما در درخت تصمیم CART، همواره دو شاخه از گره خواهیم داشت. به همین خاطر به CART درخت تصمیم باینری گفته می‌شود. 
4. وارد شاخه آفتابی می‌شویم؛ در شاخه آفتابی، باید گره تصمیم‌گیری قرار دهیم یا گره برگ؟ گره برگ زمانی قرار می‌گیرد که این حالت (چشم‌انداز: آفتابی) ما را کامل به کلاس 0 یا 1 برساند. اما با توجه به دیتاستی که داریم، این اتفاق رخ نمی‌دهد. بنابراین، باید گره تصمیم‌گیری قرار دهیم. بسیارخب، حالا کدام ویژگی را انتخاب کنیم؟ ما سه ویژگی رطوبت، دما و باد را برای انتخاب داریم. چرا چشم‌انداز را نداریم؟ چون طبق قاعده ID3 این ویژگی بالاتر انتخاب شده است و دیگر نمی‌تواند انتخاب شود. در سناریویی مشابه، بین این سه ویژگی، آن ویژگی‌ای انتخاب می‌شود که بیشترین بهره اطلاعاتی (IG) را دارد.
5. طبق معیار بهره اطلاعاتی (IG) ویژگی رطوبت انتخاب می‌شود.
6. رطوبت دو حالت نرمال و زیاد دارد. پس دو شاخه رسم می‌کنیم.
7. با بررسی دیتاست مشخص می‌شود که خوشبختانه هردو حالت ما را به یک کلاس 0 یا 1 می‌رسانند. کار شاخه آفتابی تمام شده. حالا وقت چیست؟
8. باید شاخه ابری را تعیین تکلیف کنیم؛ با بررسی دیتاست، متوجه می‌شویم که چشم‌انداز ابری مستقیما ما را به کلاس 1 می‌رساند! عالی است. پس یک گره برگ می‌گذاریم و این شاخه را هم کامل می‌کنیم. حالا می‌توانید راحت‌تر ارزش ویژگی چشم‌انداز به‌عنوان گره ریشه درک کنید. یک شاخه ما را مستقیم به گره برگ رساند. هرچه درخت ما کوچکتر و سبک‌تر باشد، برای ما ارزش بالاتری دارد. بنابراین، ما ویژگی‌هایی را دوست داریم که ما را زودتر به گره‌های برگ می‌رسانند.
9. برویم سراغ شاخه چشم‌انداز بارانی؛ این حالت ما را به کلاس 0 یا 1 نمی‌رساند. بنابراین، باید گره تصمیم‌گیری قرار دهیم.
10. باارزش‌ترین ویژگی بین سه ویژگی رطوبت، دما و باد را باید انتخاب کنیم. ممکن است بپرسید، چرا رطوبت؟ مگر نگفتی یک ویژگی وقتی یک بار انتخاب شده دیگر جز انتخاب‌های بعدی نیست؟ جوابش این هست که ویژگی رطوبت در یک مسیر کاملا متفاوت (شاخه آفتابی) است. بنابراین، معنی ندارد که در شاخه بارانی، رطوبت را از دایره انتخاب خارج کنیم. بین این سه ویژگی، ویژگی باد بیشترین بهره اطلاعات (IG) را دارد.
11. ویژگی باد دو حالت قوی و ضعیف دارد. بنابراین، دو شاخه برای این گره درنظر می‌گیریم.
12. خوشبختانه، دو حالت ضعیف و قوی به‌ترتیب ما را به دو کلاس 1 و صفر می‌رسانند. بنابراین، برای هر دو حالت گره برگ می‌گذاریم.
13. تمام!

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

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