روش طراحی درخت تصمیم

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

 الگوریتم درخت تصمیم چگونه است؟

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

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

یکی از پرکاربردترین الگوریتم‌های داده‌کاوی، الگوریتم درخت تصمیم است. در داده‌کاوی، درخت تصمیم یک مدل پیش‌بینی کننده است به طوری که می‌تواند برای هر دو مدل رگرسیون و طبقه‌ای مورد استفاده قرار گیرد. زمانی که درخت برای کارهای طبقه‌بندی استفاده می‌شود، به عنوان درخت طبقه‌بندی (Classification Tree) شناخته می‌شود و هنگامی که برای فعالیت‌های رگرسیونی به کار می‌رود درخت رگرسیون (Regression Decision Tree) نامیده می‌شود.

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

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

 اجزای اصلی درخت تصمیم

برگ (Leaf Nodes): گره‌هایی که تقسیم‌های متوالی در آنجا پایان می‌یابد. برگ‌ها با یک کلاس مشخص می‌شوند.

ریشه (Root Node): منظور از ریشه، گره آغازین درخت است.

شاخه (Branches): در هر گره داخلی به تعداد جواب‌های ممکن شاخه ایجاد می‌شود.اجزای اصلی درخت تصمیم

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

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

سه معیار انتخاب مشخصه شناخته شده عبارتند از:

• Information gain
• Gain ratio
• Gini index

 هرس کردن درخت تصمیم

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

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

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

دو رویکرد رایج برای هرس درخت به شرح ذیل وجود دارد:

• پیش‌هرس (Pre pruning)

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

• هرس پسین (Post pruning)

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

اندازه درخت

درخت تصمیم که پیچیدگی کم‌تری داشته باشد قابل بیان و روشن است؛ بنابراین پیچیدگی درخت تأثیر مهمی بر روی صحت آن می‌گذارد.

معمولاً پیچیدگی درخت توسط یکی از معیارهای زیر اندازه‌گیری می‌شود:

• تعداد کل گره‌ها
• تعداد کل برگ‌ها
• عمق درخت و تعداد مشخصه‌های به کار رفته

پیچیدگی درخت به وسیله معیار توقف و روش‌های هرس کردن به راحتی کنترل می‌شود.