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

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

الگوریتم درخت تصمیم

الگوریتم درخت تصمیم قادر است علاوه بر متغیرهای کمی، متغیرهای کیفی را نیز پیش بینی کند. این روش اولین بار توسط Breman و همکاران ارائه شد.  نتیجه پیاده سازی الگوریتم درخت تصمیم مجموعه ای از شرط های منطقی (conditions then-if )با ساختار درختی است که برای پیش بینی یک ویژگی به کار می رود. طوری که داده هایی که در برگ های انتهایی این درخت قرار می گیرند توسط یکی از مقادیر ویژگی هدف برچسب می خورند. این مدل به دلیل سهولت در تفسیر نتایج و ناپارامتری و غیر خطی بودن، نیاز به پیش فرض رابطه خطی بین متغیر های مستقل و وابسته ندارد.

بیشتر بخوانید: داده کاوی چیست؟  || علم داده  || متن کاوی چیست؟

الگوریتم درخت تصمیم به گونه ای عمل می کند که سعی دارد گوناگونی و یا تنوع (از نظر ویژگی هدف) را در گره ها به حداقل ممکن برساند. این عدم یکنواختی در گره ها با استفاده از معیارهای عدم خلوص (measure Impurity )قابل اندازه گیری است که مهمترین و پرکاربرد ترین آن شاخص جینی می باشد.
اغلب تفاوت انواع درخت های تصمیم در همین معیار اندازه گیری عدم خلوص، شیوه شاخه بندی (Splitting )و هرس کردن گره های درخت می باشد. در این مقاله 4 نوع الگوریتم درخت تصمیم CHAID، QUEST، CART و 0.C5 معرفی خواهد شد.

الگوریتم CART 

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

الگوریتم QUEST

(Tree Statically Efficient and Unbiased Quick ) الگوریتم جدید دو دویی گسترش درخت است که فقط فیلد خروجی سمبلیک را مورد استفاده قرار می دهد. در تقسیم داده ها به صورت بازگشتی به زیر گروه ها فقط دو زیر گروه را پشتیبانی می کند. یک الگوریتم سریع است که هرس نمودن آن رو به عقب است.

الگوریتم CHAID

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

الگوریتم 0.C5

الگوریتم 0.C5 یک نوع درخت تصمیم گیری تک متغیره و بهبود یافته الگوریتم 5.C4است. این الگوریتم مشابه با CART ابتدا درختی تقریبا پر ایجاد می کند ولی استراتژی هرس آن کامال متفاوت است. این الگوریتم دسته بندی را با تقسیم کردن داده ها به زیر مجموعه هایی که شامل رکورد های همگن تر از والد خود هستند انجام می دهد. در 0.C5تقسیم کردن نمونه ها براساس فیلدی که بیشترین بهره اطلاعات را دارد صورت میگیرد. این الگوریتم روشی افزایشی از هرس کردن درخت را به کار می گیرد تا خطای طبقه بندی کردن ناشی از نویز یا جزئیات خیلی زیاد را در داده های آموزشی کاهش دهد. هرس کردن با جایگزینی گره داخلی با گره برگ رخ می دهد که بدان وسیله درصد یا میزان خطا کاهش می یابد.
استفاده از الگوریتم های داده کاوی در بررسی عوامل موثر بر پیش بینی وضعیت بدو تولد نوزادان، باقری

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

کپی برداری بدون ذکر منبع، براساس قانون جرایم اینترتی و مادۀ 12 فصل سوم قانون جرایم رایانه ای غیر قانونی بوده و مجازات جزای نقدی و حبس دارد و شرعا نیز حرام است! 

افتخار آکادمی داده، همسفر بودن با شما در راه یادگیری علم داده است.