درخت تصمیم(decision tree) چیست؟-3الگوریتم پر کاربرد آن

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

درخت تصمیم(decision tree) یکی از پرکاربردترین الگوریتم‌ها در بین الگوریتم‌های داده‌کاوی است. درخت تصمیم دقیقا مانند یک درخت است با این تفاوت که از ریشه به سمت پایین (برگ) رشد کرده است. در الگوریتم درخت تصمیم نمونه‌ها را دسته‎‌بندی می‌کنیم که در واقع دسته‌ها در انتهای گره‌های برگ قرار دارد. درخت تصمیم در مسائلی کاربرد دارد که بتوان آنها را به صورتی مطرح نمود که پاسخ واحدی به صورت نام یک دسته یا کلاس ارائه دهند.

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

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

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

روش طراحی درخت تصمیم(decision tree)

در ابتدا باید موضوع اصلی که می‌خواهید برای آن تصمیم‌گیری کنید را مشخص کنید. بعد از آن ایده‌هایتان را برای تصمیم‌گیری بر روی کاغذ بیاورید و متغیرهایی که به تصمیم شما وابسته‌اند را مشخص کنید. مثلا برای خرید لپ تاپ چه متغیرهایی برای شما اهمیت دارد؟ و سپس آنها را به ترتیب اولویت مرتب کنید.

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

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

کسانی که بازی بیست سوالی انجام داده اند به سادگی می­توانند  درخت تصمیم­ گیری را درک کنند. در این بازی یک نفر موضوع خاصی را در ذهن خود در نظر می­گیرد و شخص دیگری سعی می­کند با پرسش تعدادی سوال که جواب آنها بلی و خیر است موضوع مورد نظر شخص اول را شناسایی کند. در درخت تصمیم‌(decision tree ) نیز تعدادی پرسش وجود دارد و با مشخص شدن پاسخ هر سوال یک سوال دیگر پرسیده می­شود. اگر سوالها درست و سنجیده پرسیده شوند، تعداد کمی از پرسش­ها برای پیش بینی رکورد جدید کافی می­ باشد.

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

درخت تصمیم از تعدادی گره و شاخه تشکیل شده است که در آن نمونه­ ها را به نحوی طبقه­ بندی می­کند که از ریشه به سمت پایین رشد می­ کند و در نهایت به گره ­های برگ م ی­رسد. هر گره داخلی یا غیر برگ با یک ویژگی مشخص می­ شود. این ویژگی سوالی را در رابطه با مثال ورودی مطرح می­ کند. در هر گره داخلی به تعداد جواب ­های ممکن با این سوال شاخه وجود دارد که هریک با مقدار آن جواب مشخص می‌شوند. برگ­های این درخت با یک کلاس و یا یک طبقه از جواب­ها مشخص می‌شوند.

برخی از الگوریتم های درخت تصمیم(decision tree)

الگوریتم­های زیادی برای ساخت درخت تصمیم وجود دارند که از آن جمله می ­توان به:

ID3:Iterative Dichotomiser

C4.5: Classifier 4.5

CART: Classification And Regression Tree

ID4

ds CART: DempsterShafer  Classification And Regression Tree

ID5R

EC4.5:Efficient Classifier 4.5

CHAID: Chi square Automatic Interaction Detection

RF: Random Forest

RT: Random Tree

DS: Decision Stump

QUEST: Quick Unbiased  Efficient Statistical Tree

در ادامه به توضیح، برخی از این الگوریتم ها می ­پردازیم.

• الگوریتم ID3

این الگوریتم یکی از ساده ترین الگوریتم های درخت تصمیم(decision-tree) است. در این الگوریتم درخت تصمیم از بالا به پایین ساخته می‌شود. این الگوریتم با این سوال شروع می‌شود: کدام ویژگی باید در ریشه درخت مورد آزمایش، قرار بگیرد؟ برای یافتن جواب از معیار بهره اطلاعات  استفاده می‌شود.

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

• الگوریتم C4.5

این الگوریتم یکی از تعمیم های الگوریتم ID3 است که از معیار نسبت بهره(Gain ratio) استفاده می­ کند. الگوریتم هنگامی متوقف می‌شود که تعداد نمونه ها کمتر از مقدار مشخص شده‌ای باشد. این الگوریتم از تکنیک پس هرس استفاده می‌کند و همانند الگوریتم قبلی داده‌های عددی را نیز می­پذیرد.

از نقاطِ ضعف الگوریتم ID3  که در C4.5  رفع شده است می‌توان به موارد زیر اشاره کرد:

• الگوریتم C4.5    می‌تواند مقادیر گسسته یا پیوسته را در ویژگی‌ها درک کندو
• الگوریتم C4.5   قادر است با وجود مقادیر گمشده نیز درخت تصمیم(decision tree) خود را بسازد، در حالی که الگوریتمی مانند ID3 و بسیاری دیگر از الگوریتم‌های طبقه‌بندی نمی‌توانند با وجود مقادیر گمشده، مدلِ خود را بسازند.
• سومین موردی که باعث بهینه شدن الگوریتم  C4.5  نسبت به ID3  می‌شود، عملیاتِ هرس کردن جهت جلوگیری از بیش برازش می‌باشد. الگوریتم‌هایی مانند ID3  به خاطر اینکه سعی دارند تا حد امکان شاخه و برگ داشته باشند (تا به نتیجه مورد نظر برسند) با احتمال بالاتری دارای پیچیدگی در ساخت مدل و این پیچیدگی در بسیاری از موارد الگوریتم را دچار بیش برازش و خطای بالا می‌کند.اما باعملیات هرس کردن درخت که در الگوریتم 5  انجام می‌شود، می‌توان مدل را به یک نقطه بهینه رساند که زیاد پیچیده نباشد (و البته زیاد هم ساده نباشد) و  بیش برازش یا کم برازش(Underfitting) رخ ندهد.

• الگوریتم C4.5 این قابلیت را دارد که وزن‌های مختلف و غیر یکسانی را به برخی از ویژگی‌ها بدهد.

الگوریتم CHAID

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

نرم افزارهای مورد استفاده برای انجام الگوریتم درخت تصمیم

در حوزه داده‌کاوی، با استفاده از نرم افزارهای SPSS Modeler, SAS JMP, Clementine, MATLAB, R, Python, … می‌توانید الگوریتم درخت تصمیم را برای دسته‌بندی نمونه‌های خود استفاده کنید.

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

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

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