درخت تصمیم قسمت 4

درخت تصمیم چیست؟

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

درخت تصمیم یک مدل خودتوصیف است یعنی به‌تنهایی و بدون حضور یک فرد متخصص در آن حوزه، نحوه دسته‌بندی را به صورت گرافیکی نشان می‌دهد و به دلیل همین سادگی و قابل‌فهم بودن، روش محبوبی در داده‌کاوی محسوب می‌شود. البته به خاطر داشته باشید در مواردی که تعداد گره‌های درخت زیاد باشد، نمایش گرافیکی و تفسیر آن می‌تواند کمی پیچیده باشد.
برای روشن شدن مطالب، به مثال زیر توجه کنیدکه در آن قصد داریم به کمک ساخت یک درخت تصمیم، بازی‌کردن کریکت را برای یک دانش‌آموز، پیش‌بینی کنیم:
فرض کنید نمونه‌ای شامل ۳۰ دانش‌آموز با سه متغیر جنسیت (پسر/ دختر)، کلاس (X / IX) و قد (۵ تا ۶ فوت) داریم. ۱۵ نفر از ۳۰ نفر در اوقات فراغت خود کریکت بازی می‌کنند. حال می‌خواهیم با بررسی خصوصیات این پانزده نفر، پیش‌بینی کنیم چه کسانی در اوقات فراغت خود کریکت بازی می‌کنند.برای این کار ابتدا باید براساس خصوصیات ۱۵ نفری که کریکت بازی می‌کنند، یک الگو برای دسته‌بندی به دست آوریم. از آنجا که درخت تصمیم یک ساختار سلسله مراتبی شرطی دارد (شکل فوق) و در هر مرحله باید بر اساس مقدار یک خصوصیت تصمیم بگیریم، مهم‌ترین کاری که در ساخت این درخت تصمیم باید انجام دهیم، این است که تعیین کنیم کدام خصوصیت داده‌ها، تفکیک‌کنندگی بیشتری دارد. سپس این خصوصیت‌ها را اولویت‌بندی کرده و نهایتاً با لحاظ این اولویت‌ها از ریشه به پایین در اتخاذ تصمیم، ساختاری درخت‌مانند برای دسته‌بندی داده‌ها بنا کنیم. الگوریتم‌های مختلف ساخت درخت تصمیم، مهم-‌ترین تفاوتی که با هم دارند، در انتخاب این اولویت و روشی است که برای انتخاب اولویت خصوصیت‌ها در نظر می‌گیرند.
برای سنجش میزان تفکیک‌کنندگی یک خصوصیت، ساده‌ترین روش این است که دانش‌آموزان را براساس همهٔ مقادیر هر سه متغیر تفکیک کنیم. یعنی مثلاً ابتدا بر اساس جنسیت، داده‌ها را جدا کنیم و سپس مشخص کنیم چند نفر از دختران و چندنفر از پسران، کریکت بازی می‌کنند. سپس همین کار را برای قد و کلاس تکرار کنیم. با این کار، می‌توانیم درصد بازیکنان هر مقدار از یک خصوصیت (درصد بازیکنان دختر از کل دختر‌ها و درصد بازیکنان پسر از کل پسر‌ها) را محاسبه کنیم. هر خصوصیتی که درصد بیشتری را تولید کرد، نشانگر تفکیک‌کنندگی بیشتر آن خصوصیت (و البته آن مقدار خاص) است.
جور دیگری هم به این موضوع می‌توان نگاه کرد: این متغیر، بهترین مجموعه همگن از دانش‌آموزان از لحاظ عضویت در گروه بازی‌کنان را ایجاد می‌کند یعنی در گروه بازیکنان، بیشترین خصوصیتی که بین همه مشترک است، پسر بودن است. میزان همگنی و یکنواختی ایجاد شده توسط هر خصوصیت هم، شکل دیگر میزان تفکیک‌کنندگی آن خواهد بود.
در تصویر زیر شما می‌توانید مشاهده کنید که متغیر جنسیت در مقایسه با دو متغیر دیگر، قادر به شناسایی بهترین مجموعهٔ همگن هست چون میزان مشارکت دانش‌آموزان پسر دربازی کریکت ۶۵ درصد است که از تمام متغیرهای دیگر بیشتر است:

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

درخت تصمیم چگونه کار می‌کند؟

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

هدف از الگوریتم‌های درخت تصمیم هم انتخاب درست این سؤالات است به گونه‌ای که یک دنباله کوتاه از سؤالات برای پیش‌بینی دستهٔ رکورد جدید تولید کنند.

هر گره داخلی متناظر با یک متغیر و هر یال، نمایانگر یک مقدار ممکن برای آن متغیر است. یک گره برگ، مقدار پیش‌بینی‌شدهٔ متغیر هدف (متغیری که قصد پیش‌بینی آنرا داریم)، را نشان می‌دهد یعنی برگ‌ها نشان‌دهندهٔ دسته‌بندی نهایی بوده و مسیر پیموده شده تا آن برگ، روند رسیدن به آن گره را نشان می‌دهند.

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

انواع متغیر‌ها در درخت تصمیم

در مسائل مرتبط با درخت‌های تصمیم با دو نوع کلی از متغیر‌ها مواجه هستیم:

• متغیرهای عددی یا پیوسته: مانند سن، قد، وزن و… که مقدار خود را از مجموعهٔ اعداد حقیقی می‌گیرند.
• متغیرهای رده‌ای یا گسسته : مانند نوع، جنس، کیفیت و… که به‌صورت دو یا چند مقدار گسسته هستند. در مواردی مانند آیا این شخص دانش‌آموز است؟ که دو جواب بله و خیر داریم، این متغیر از نوع طبقه‌ای خواهد بود.

از طرفی می‌توانیم متغیر‌ها را به دون گروه کلی، متغیرهای مستقل و متغیرهای وابسته تقسیم کنیم. متغیرهای مستقل، متغیرهایی هستند که مقدار آن‌ها، مبنای تصمیم گیری ما خواهند بود و متغیر وابسته، متغیری است که بر اساس مقدار متغیرهای مستقل، باید مقدار آنرا پیش‌بینی کنیم. متغیرهای مستقل با گره‌های میانی نشان داده می‌شوند و متغیرهای وابسته، با برگ نشان داده می‌شوند. حال هر یک از این دو نوع متغیر مستقل و وابسته، می‌تواند گسسته یا پیوسته باشد.
چنانچه متغیری وابستهٔ عددی باشد دسته بندی ما یک مسالهٔ رگرسیون و چنانچه طبقه‌ای باشد، دسته بندی از نوع، رده‌بندی (Classification) است. به عبارتی دیگر، هنگامی‌که خروجی یک درخت، یک مجموعه گسسته از مجموعه مقادیر ممکن است؛ به آن درخت دسته‌بندی می‌گوییم (مثلاً مؤنث یا مذکر، برنده یا بازنده). این درخت‌ها تابع X→C را بازنمایی می‌کنند که در آن C مقادیر گسسته می‌پذیرد. هنگامی‌که بتوان خروجی درخت را یک عدد حقیقی در نظر گرفت آن را، درخت رگرسیون می‌نامیم (مثلاً قیمت خانه یا طول مدت اقامت یک بیمار در یک بیمارستان). این درختان اعداد را در گره‌های برگ پیش‌بینی می‌کنند و می‌توانند از مدل رگرسیون خطی یا ثابت (یعنی میانگین) یا مدل‌های دیگر استفاده کنند. وظیفهٔ یادگیری در درختان رگرسیون، شامل پیش‌بینی اعداد حقیقی بجای مقادیر دسته‌ای گسسته است که این عمل را با داشتن مقادیر حقیقی در گره‌های برگ خود نشان می‌دهند. بدین‌صورت که میانگین مقادیر هدف نمونه‌های آموزشی را در این گره برگ به دست می‌آورند. این نوع از درختان، تفسیر آسان داشته و می‌توانند توابع ثابت تکه‌ای را تقریب بزنند.
درخت CART (Classification And Regression Tree) نامی است که به هر دو روال بالا اطلاق می‌شود. نام CART سرنام کلمات درخت رگرسیون و دسته‌بندی است. البته نوع دیگری از درخت‌های تصمیم هم داریم که برای خوشه‌بندی (clustering) داده‌ها به کار می‌روند و به دلیل کاربرد محدود، در این مجموعه مقالات به آن‌ها نخواهیم پرداخت (بیشتر تحقیقات در یادگیری ماشین روی درختان دسته‌بندی متمرکز است).

اصطلاحات مهم مربوط به درخت تصمیم

در این بخش به معرفی اصطلاحات مهم در حوزهٔ کار با درخت تصمیم می‌پردازیم.
گره ریشه: این گره حاوی تمام نمونه‌های موجود هست و سطح بعدی اولین تقسیم مجموعهٔ اصلی به دو مجموعهٔ همگن‌تر است. در مثال قبل، گره ریشه دارای ۳۰ نمونه است.
گره تصمیم: زمانی که یک گره به زیرگره‌های بعدی تقسیم می‌شود، آن را یک گره تصمیم می‌نامیم.
برگ / گره پایانه: گره‌هایی که تقسیم نمی‌شوند یا به عبارتی تقسیم پیاپی از طریق آن‌ها پایان می‌یابد، برگ یا گره پایانه نام دارند.
در تصویر زیر، گره ریشه (Root Node) با رنگ آبی، شاخه، انشعاب (Branch) یا به عبارتی زیر درخت (Sub-Tree) با رنگ گل‌بهی، تقسیم (Splitting) و هرس (Pruning) نمایش داده‌شده‌اند. برگ‌ها هم به رنگ سبز در انتهای شاخه‌های مختلف درخت، قرار گرفته‌اند.

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

مزایا و معایب درخت تصمیم

مزایای درختان تصمیم نسبت به روش‌های دیگر داده‌کاوی
۱) قوانین تولیدشده و به‌کاررفته شده قابل‌استخراج و قابل‌فهم می‌باشند.
۲) درخت تصمیم، توانایی کار با داده‌های پیوسته و گسسته را دارد. (روش‌های دیگر فقط توان کار با یک نوع رادارند. مثلاً شبکه‌های عصبی فقط توان کار با داده‌های پیوسته را دارد و قوانین رابطه‌ای با داده‌های گسسته کار می‌کنند)
۳) مقایسه‌های غیرضروری در این ساختار حذف می‌شود.
۴) از ویژگی‌های متفاوت برای نمونه‌های مختلف استفاده می‌شود.
۵) احتیاجی به تخمین تابع توزیع نیست.
۶) آماده‌سازی داده‌ها برای یک درخت تصمیم، ساده یا غیرضروری است. (روش‌های دیگر اغلب نیاز به نرمال‌سازی داده یا حذف مقادیر خالی یا ایجاد متغیرهای پوچ دارند)
۷) درخت تصمیم یک مدل جعبه سفید است. توصیف شرایط در درختان تصمیم به‌آسانی با منطق بولی امکان‌پذیر است درحالی‌که شبکه‌های عصبی به دلیل پیچیدگی در توصیف نتایج آن‌ها یک جعبه سیاه می‌باشند.
۸) تائید یک مدل در درخت‌های تصمیم با استفاده از آزمون‌های آماری امکان‌پذیر است. (قابلیت اطمینان مدل را می‌توان نشان داد)
۹) ساختارهای درخت تصمیم برای تحلیل داده‌های بزرگ در زمان کوتاه قدرتمند می‌باشند.
۱۰) روابط غیرمنتظره یا نامعلوم را می‌یابند.
۱۱) درخت‌های تصمیم قادر به شناسایی تفاوت‌های زیرگروه‌ها می‌باشند.
۱۲) درخت‌های تصمیم قادر به سازگاری با داده‌های فاقد مقدار می‌باشند.
۱۳) درخت تصمیم یک روش غیرپارامتریک است و نیاز به تنظیم خاصی برای افزایش دقت الگوریتم ندارد.

معایب درختان تصمیم

۱) در مواردی که هدف از یادگیری، تخمین تابعی با مقادیر پیوسته است مناسب نیستند.
۲) در موارد با تعداد دسته‌های زیاد و نمونه آموزشی کم، احتمال خطا بالاست.
۳) تولید درخت تصمیم‌گیری، هزینه محاسباتی بالا دارد.
۴) هرس کردن درخت هزینه بالایی دارد.
۵) در مسائلی که دسته‌ها شفاف نباشند و همپوشانی داشته باشند، خوب عمل نمی‌کنند.
۶) در صورت همپوشانی گره‌ها تعداد گره‌های پایانی زیاد می‌شود.
۷) درصورتی‌که درخت بزرگ باشد امکان است خطا‌ها از سطحی به سطحی دیگر جمع می‌شوند (انباشته شدن خطای لایه‌ها و تاثیر بر روی یکدیگر).
۸) طراحی درخت تصمیم‌گیری بهینه، دشوار است و کارایی یک درخت دسته‌بندی کننده به چگونگی طراحی خوب آن بستگی دارد.
۹) احتمال تولید روابط نادرست وجود دارد.
۱۰) وقتی تعداد دسته‌ها زیاد است، می‌تواند باعث شود که تعداد گره‌های پایانی بیشتر از تعداد دسته‌های واقعی بوده و بنابراین زمان جستجو و فضای حافظه را افزایش می‌دهد.

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

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

هر دو نوع درخت تصمیم و رگرسیون تقریباً مشابه هستند. در زیر به برخی شباهت‌ها و تفاوت‌های بین این دو می‌پردازیم:

ویژگی‌های درخت رگرسیون و درخت دسته‌بندی:

• زمانی که متغیر هدف ما پیوسته و عددی باشد، از درخت رگرسیون و زمانی که متغیر هدف ما گسسته یا غیرعددی باشد، از درختان تصمیم استفاده می‌کنیم.
• معیار تقسیم و شاخه زدن در درختان رگرسیون بر اساس معیار خطای عددی است.
• گره‌های برگ در درختان رگرسیون حاوی مقادیر عددی هستند که هر عدد، میانگین مقادیر دسته‌ای است که داده جاری، بیشترین شباهت را با آن‌ها داشته است اما در درختان تصمیم، مقدار برگ، متناظر با دسته‌ایست که بیشترین تکرار را با شرایط مشابه با داده داده شده، داشته است.
ن هر دو درخت، رویکرد حریصانهٔ بالا به پایین را، تحت عنوان تقسیم باینری بازگشتی دنبال می‌کنند. این روش از بالای درخت، جایی که همهٔ مشاهدات در یک بخش واحد در دسترس هستند شروع می‌شود و سپس تقسیم به دوشاخه انجام‌شده و این روال به‌صورت پی‌درپی تا پایین درخت ادامه دارد، به همین دلیل این روش را بالا به پایین می‌خوانیم. همچنین به این دلیل این روش را حریصانه می‌خوانیم که تلاش اصلی ما در یافتن بهترین متغیر در دسترس برای تقسیم فعلی است و در مورد انشعابات بعدی که به یک درخت بهتر منتهی شود، توجهی نداریم. (به عبارتی همواره بهترین انتخاب در لحظه، بهترین انتخاب در سراسر برنامه نیست و اثرات این تقسیم در تقسیم‌های آینده را در نظر نمی‌گیرد). به یاد دارید که درروش حریصانه و در مورد کوله‌پشتی نیز مورد مشابه را دیده‌ایم. در شیوه حریصانه در هر مرحله عنصری که بر مبنای معیاری معین ((بهترین)) به نظر می‌رسد، بدون توجه به انتخاب‌های آینده، انتخاب می‌شود.
• در هر دو نوع درخت، در فرآیند تقسیم این عمل تا رسیدن به معیار تعریف‌شدهٔ کاربر برای توقف عملیات، ادامه دارد. برای مثال، ما می‌توانیم به الگوریتم بگوییم که زمانی که تعداد مشاهدات در هر گره کمتر از ۵۰ شود، عملیات متوقف گردد.
• در هر دو درخت، نتایج فرآیند تقسیم، تا رسیدن به معیارهای توقف، باعث رشد درخت می‌شود. اما درخت کاملاً رشد یافته به‌احتمال‌زیاد باعث بیش‌برازش داده‌ها (over fit) خواهد شد که در این صورت، شاهدکاهش صحت و دقت بر روی ‌داده‌های آینده که قصد دسته‌بندی آن‌ها را داریم، خواهیم بود. در این زمان هرس‌کردن را بکار می‌بریم. هرس کردن، روشی برای مقابله با بیش-برازش داده‌هاست که در بخش بعد بیشتر به آن خواهیم پرداخت.

نحوهٔ تقسیم یک درخت تصمیم

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

انتخاب الگوریتم، به نوع متغیرهای هدف نیز بستگی دارد.

منبع

درخت تصمیم قسمت 1
درخت تصمیم قسمت 2
درخت تصمیم قسمت 3
درخت تصمیم قسمت 4