گفتیم که درخت تصمیم (Decision Tree) در دسته الگوریتم های یادگیری با نظارت جای دارد ولی می توانیم از یک دید دیگر، الگوریتم درخت تصمیم را در دسته الگوریتم های یادگیری استقرایی جای دهیم. درخت تصمیم گیری با ترتیب کردن نمونه ها از ریشه به سوی برگ های درخت، نمونه ها را دسته بندی می کند. گفتیم که هر گره نا برگ، یکی از ویژگی های مجموعه داده است که تصمیم گیری بر پایه مقدارهای آن انجام می شود و هر یال بیرون آمده از گره ها، یکی از مقدارهای برای آن ویژگی است. در هر شاخه از درخت، گره برگ، نمایانگر یک پاسخ است که برابر با یکی از کلاس ها یا برچسب ها هستند.

شکل زیر یک مجموعه داده را نشان می دهد که در برگیرنده داده هایی برای روزهایی است که با توجه به مقدار چهار ویژگی آن، می توانیم پیش بینی کنیم که آیا می توان در یک روز تنیس بازی کرد (کلاس Yes) یا بازی نکرد (کلاس No). انگیزه آن هست که مدلی را بر پایه درخت تصمیم و از روی مجموعه داده یادگیری بسازیم تا بتوانیم بر پایه یک نمونه تازه همانند زیر، پیش بینی کنیم که آیا یک روز دلخواه دیگر، برای بازی تنیس پسندیده هست یا نه؟

شکل زیر درخت تصمیم بازی کردن تنیس را نشان می دهد. برای نمونه، مسیر زیر در مجموعه داده ها، یک نمونه منفی است زیر را در این مسئله، این نمونه دارای برچسب یا کلاس No است. بر پایه دومین کد زیر، درخت ها تصمیم ترکیبی از روابط ترکیب عطفی (AND با نماد ) و ترکیب فصلی (OR با نماد ) است

تفسیر منطق زیر با توجه به یال ها در درخت تصمیم بدین گونه است که اگر ویژگی Outlook برابر با Sunny و ویژگی Humidity برابر با Normal باشد، پس می توان تنیس بازی کرد یا اگر ویژگی outlook برابر با overcast باشد، پس می توان تنیس بازی کرد یا اگر outlook برابر با Rain و wind برابر با weak بود، پس می توان تنیس بازی کرد.

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

بیشتر الگوریتم هایی که برای یادگیری درختی (Tree Learning) ساخته شده اند، نسخه های گوناگونی از یک الگوریتم پایه هستند که این الگوریتم از جسـتجوی حریصـانه (Greedy) بالا به پایین برای جستجوی فضای درخت ها تصمیم گیری ممکن، کمک می گیرد. ایـن روش، الگـوریتم ID3 نـام دارد و تکامل یافته ID3 الگوریتم دیگری است که الگوریتم 5.C4 نامیده می شود. در این نوشته می خواهیم درباره این دو الگوریتم بگوییم.

گسسته سازی و انشعاب گره

در آمار و یادگیری ماشین، گسسته سازی (Discretisation) به فرآیند تبدیل یا تقسیم مداوم  ویژگی ها (Features) یا متغیرها برای مشخص کردن ویژگی های Nominal در فواصلی (Interval) اشاره دارد. انگیزه آن است که داده های شماره ای (عددی) که پیوسته هستند را به بازه های تبدیل کنیم. به طور معمول داده ها به پارتیشن هایی با طول/عرض مساوی K (فواصل برابر) یا K٪ از کل داده ها (فرکانس های برابر) تفکیک می شوند.

گسسته سازی فرایند تبدیل متغیرهای پیوسته (Continuous) به متغیرهای گسسته (Discrete) از طریق ایجاد مجموعه ای از فواصل متناقض است که دامنه مقادیر متغیر را در بر می گیرد. گسسته سازی در درخت تصمیم گیری شامل استفاده از یک درخت تصمیم گیری برای شناسایی نقاط تقسیم بهینه است.

اغلب داده ها به صورت مقادیر پیوسته داده می شوند. اگر تعداد آنها بسیار زیاد باشد ، ساختن مدل برای چنین داده هایی می تواند سخت باشد. علاوه بر این ، بسیاری از الگوریتم های داده کاوی تنها در جستجوی گسسته یا فضای متغیر فعالیت می کنند. به عنوان مثال ، درختان تصمیم گیری به طور معمول مقادیر یک متغیر را با توجه به مقدار آستانه مناسب به دو قسمت تقسیم می کنند. انگیزه از گسسته سازی، كاهش شمار مقدارهای يك متغير پيوسته با گروه بندی آنها به فاصله ها (Intervals) است.

الگوریتم ID3 برای طبقه بندی

لگوریتم اساسی ما، یا همان ID3 ،درخت تصمیم گیری متناسب را با جستجویی بالا به پایین پیدا می کند. توجه کنید که به دنبال بهینه ترین درخت از میان همه درخت های تصمیم هستیم که کوچکترین درخت است. کوچکترین درخت تصمیم، درختی با کمترین ارتفاع است. اگر مجموعه داده ای دارای m ویژگی باشد، پس در بیشینه، ارتفاع آن m است که خود گره ریشه یکی از این m ویژگی است.

  • گام  ۱: ساخت درخت تصمیم ID3 از روی همه نمونه های درون مجموعه داده. همچنین ورودی دیگر فهرستی از نام ویزگی ها و برچسب ها است. گفتیم که الگوریتم درخت تصمیم از گونه الگوریتم های طبقه بندی و از این رو در دسته الگوریتم های نظارت شده است . در الگوریتم های نظارت شده، مجموعه داده به ازای هر نمونه، دارای یک برچسب یا پاسخی است که کلاس آن نمونه را نشان می دهد.
  • گام ۱-۱: ساخت یک گره ریشه برای درخت تصمیم
  • گام ۲-۱: اگر همه نمونه ها دارای یک برچسب (کلاس) متعلق به کلاس C هستند:
  • گام ۱-۲-۱: پس یک درخت تک گره ریشه داریم که برچسب آن کلاس C است.
  • گام ۳-۱: اگر ویژگی ها تهی (Empty) باشند:
  • گام ۱-۳-۱: پس یک درخت تک گره ریشه که برچسب آن از میان بیشترین برچسب ها است
  • گام ۴-۱: وگرنه (در غیر اینصورت):
  • گام ۱-۴-۱: A یک ویژگی (Attribute) از میان ویژگی ها است که بهترین گونه نمونه ها را طبقه بندی می کند.
  • گام ۲-۴-۱: برچسب A برای ویژگی گره تصمیم ریشه برگزیده می شود.
  • گام ۳-۴-۱: برای هر مقدار در ویژگی A:
  • گام ۱-۳-۴-۱: یک انشعاب از گره ریشه بیرون می آید. گفتیم از هر گره به ازای هر مقدار آن یک انشعاب بیرون می آید. برای نمونه اگر همه مقدارهای یک ویژگی یکی از سه مقدار V1, V2 و V3 باشند، پس سه انشعاب بیرون می آید.
  • گام ۲-۳-۴-۱: گمان کنید نمونه های Vi زیر مجموعه ای از نمونه هایی با مقدار Vi برای ویژگی A باشند.
  • گام ۳-۳-۴-۱: اگر نمونه Vi تهی باشد:
  • گام ۱-۳-۳-۴-۱: همین انشعاب دنبال شود، یک گره برگ تازه ساخته شود که برچسب آن از میان بیشترین برچسب ها در نمونه ها است. گفتیم که گره برگ، همان پاسخ یا کلاس است.
  • گام ۲-۳-۳-۴-۱: وگرنه همین انشعاب را دنبال شود و یک زیر درخت به گونه بازگشتی و رفتن به گام آغازین (گام ۱) ساخته شود. در اینجا نیز سه ورودی داریم که در برگیرنده همه داده های زیر مجموعه Vi (و نه همه داده های آغازین)، برچسب ها و همه ویژگی ها منهای ویژگی A هستند.

جستجو با طرح این پرسش آغاز می شود که: “چه ویژگی هایی باید در ریشه درخت تصمیم بررسی شوند؟“. برای پاسخ دادن به این پرسش، همه ویژگی ها در همه نمونه ها توسط یک بررسی آماری بررسی می شوند تا معلوم گردد که کدام ویژگی به تنهایی تأثیر بیشتری بر دسته بندی (طبقه بندی) نمونه ها دارد. سپس بهترین ویژگی انتخاب می شود و به عنوان گره ریشه درخت، قرار می گیرد. برای هر مقدار این ویژگی انتخابی در ریشه درخت نمونه های آموزشی ترتیب می شوند و با توجه به این گره، مسئله به مسئله های کوچکتر تبدیل می شود.

بنابراین در آغاز، همه داده ها در گره ریشه هستند و سپس از این رو باید بهترین ویژگی برای گره برگزیده شود تا از این پس انشعاب ها بر پایه مقدارهای هر ویژگی انجام شود. نخستین ویژگی که باید برگزیده شود، برای گره ریشه است. همچنین پس از گزینش هر ویژگی، به شمار مقدارهای آن، از گره زیر شاخه بیرون می آید که سر دیگرش یا یک گره تصمیم (نابرگ) تازه است که خودش دوباره یک ویژگی دیگر از میان همه ویژگی های مجموعه داده است و یا اینکه، گره یک برگ است که یکی از برچسب ها یا کلاس های درون مسئله است.

الگوریتم C4.5 برای طبقه بندی

الگوریتم C 4.5 که توسط Ross Quinlan ایجاد شده است و الگوریتمی است که برای ایجاد درخت تصمیم و در مسئله های طبقه بندی استفاده می شود. C 4.5 توسعه داده شده الگوریتم دیگری به نام ID3 hs است. همانطور که گفتیم درخت تصمیم را می توانیم هم برای مسئله های رگرسیون (پیش بینی مقدارهای پیوسته و عددی – مانند پیش بینی قیمت) و هم برای مسئله های طبقه بندی (پیش بینی یا تعیین کلاس گونه گیاهی، اسپم بودن یا نبودن پیامک ها) استفاده کنیم.  الگوریتم C 4.5، به طور ویژه در مسئله های طبقه بندی استفاده می شود.

همانطور که گفتیم گره ریشه شامل تمامی مجموعه داده (Dataset) می شود، سپس بر اساس قوانینی که بروی هر نمونه (Sample) از مجموعه داده اعمال می شود، زیر درخت هایی ایجاد می شوند. بنابراین با توجه به اینکه بر اساس قوانینی تمامی مجموعه داده در گره ریشه به زیر درخت هایی شکسته می شود، هر زیر درخت دارای نمونه هایی هستند که دارای ویژگی ها مشابه هستند. این فرایند برای زیرشاخه ها آنقدر اجرا می شود تا بالاخره هر نمونه درست دسته بندی شود، در هر تکرار همیشه ویژگی انتخابی برای گره، ویژگی است که مهمترین اثر را در دسته بندی دارد.

یکی از محدودیت های ID3 این است که بیش از اندازه به ویژگی های با شمار زیادی از مقدارها حساس است. از این دسته داده ها می تانیم به داده های شبکه های اجتماعی اشاره کنیم. در نوشته پسین (بعدی) درباره دو مفهوم Entropy و Information Gain خواهیم گفت. این دو، دو مفهوم پایه ای در درخت تصمیم هستند.

در الگوریتم های درخت تصمیم همانند ID3, C4.5 و CART انگیزه آن است که بهترین ویژگی برای انشعاب برگزیده شود. در ID3 از معیاری به نام بهره اطلاعات (Information Gain) کمک گرفته می شود به گونه ای که این معیار برای تک تک ویزگی ها بدست آمده و سپس آن ویژگی برای گره تصمیم برگزیده می شود که IG آن بیشتر از دیگران باشد. برای بدست آوردن IG نیاز به یک معیار دیگر به نام آنتروپی است. در الگوریتم C4.5 که بهینه شده ID3 است، معیار دیگری به نام شاخص جینی (Gini Index) برای برگزیدن بهترین ویژگی به کار می رود.