درخت و-یا

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

تعریف

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

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

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

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

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

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


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

نمودار درختی

نمودار جدولی

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

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

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

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

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

مثال

پانویس
  1. ^ and-or tree
  2. ^ decision tree
  3. ^ disjunctive
  4. ^ classification
  5. ^ AND
  6. ^ OR

منابع
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.