درخت و-یا

درختهای و-یا^∗ که نام دیگر آنها درختان تصمیم^∗ است، نمونه‌ها را با مرتب کردن آنها در درخت از گره ریشه به سمت گره‌های برگ دسته بندی می‌کنند.

تعریف

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

نحوه ساخت درخت و-یا

مثال: بازنمایی درخت تصمیم برای تابع A ∧ ~B

1. ریشه درخت مسئله اصلی را در بر می‌گیرد.
2. هر گره داخلی در درخت، صفتی از نمونه را آزمایش می‌کند و هر شاخه‌ای که از آن گره خارج می‌شود متناظر یک مقدار ممکن برای آن صفت می‌باشد.
3. به هر گره برگ، یک دسته بندی منتسب می‌شود. هر نمونه، با شروع از گره ریشه درخت و آزمایش صفت مشخص شده توسط این گره و حرکت در شاخهٔ متناظر با مقدار صفت داده شده در نمونه، دسته بندی می‌شود.
4. این فرآیند برای هر زیردرختی که گره جدید ریشه آن می‌باشد تکرار می‌شود.

نحوه نمایش درخت و-یا

برای نمایش درخت و-یا می‌توان از نمودار درختی یا یک جدول استفاده کرد که در زیر یک درخت و-یا در هر دو نمودار نشان داده شده است.

مثال نمایش داده شده در اصل، ترسیم گزاره منطقی زیر است:

(چشم انداز = آفتابی ∧ رطوبت = معمولی) ∨ (چشم انداز = ابری) ∨ (چشم انداز = بارانی ∧ باد = ضعیف)

در این مسئله هدف آنست که به جواب درست برسیم و مسیری که ما را به جواب «بله» می رساند را تعیین می کنیم.

نمودار درختی

نمودار جدولی

کاربرد درخت و-یا

• درخت تصمیم در مسایلی کاربرد دارد که بتوان آنها را بصورتی مطرح نمود که پاسخ واحدی بصورت نام یک دسته یا کلاس ارائه دهند.
• برای مثال می‌توان درخت تصمیمی ساخت که به این سوال پاسخ دهد: بیماری مریض بیماری کدام است؟ و یا درختی ساخت که به این سوال پاسخ دهد: آیا مریض به هپاتیت مبتلاست؟
• برای مسائلی مناسب است که مثالهای آموزشی بصورت زوج (مقدار-ویژگی) مشخص شده باشند.
• تابع هدف دارای خروجی با مقادیر گسسته باشد. مثلا هر مثال با بله و خیر تعیین شود.
• نیاز به توصیف گر فصلی^∗ باشد.

ویژگی‌های درخت و-یا

• برای تقریب توابع گسسته بکار می‌رود.^∗
• نسبت به نویز داده‌های ورودی مقاوم است.
• برای داده‌های با حجم بالا کاراست از این رو در داده کاوی استفاده می‌شود.
• می توان درخت را بصورت قوانین if-then نمایش داد که قابل فهم برای استفاده است.
• امکان ترکیب عطفی و فصلی فرضیه‌ها را می‌دهد.
• در مواردی که مثالهای آموزشی که فاقد همه ویژگیها هستند نیز قابل استفاده است.

تعمیم درختان تصمیم به گراف‌های تصمیم

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

روشی که اشیا در گراف‌های تصمیم دسته بندی می‌شوند همان روش بکار رفته در درختان تصمیم می‌باشد. هر درخت تصمیم و گراف تصمیم یک دسته بندی را تعریف می‌کنند (یک افراز از فضای شیء به دسته‌های مجزا). مجموعهٔ توابع قابل نمایش توسط گراف دقیقاً همانند مجموعه قابل نمایش توسط درخت است. هرچند مجموعه دسته‌هایی که در تعریف یک تابع تصمیم وارد می‌شوند متفاوت است.

مثال

پاورقی

1. ^ and-or tree
2. ^ decision tree
3. ^ disjunctive
4. ^ classification
5. ^ AND
6. ^ OR

منابع

• مشارکت‌کنندگان ویکی‌پدیا، «And–or tree»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲ می ۲۰۱۱).
• مشارکت‌کنندگان ویکی‌پدیا، «Decision tree»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲ می ۲۰۱۱).
• http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/mlbook/ch3.pdf
  
• http://ce.aut.ac.ir/~shiry/lecture/machine-learning/Decision%20Tree.ppt