مفهوم “اسپم” متنوع است ، از آن برای تبلیغات محصولات / وب سایتها استفاده می شود و یا اینکه از آن برای شناسایی محتوای پورونو یا برای دسته بندی ایمیل ها استفاده می شود. به طور کل، تشخيص اسم، فلتر کردن آن داده های تازه وارد شده بر پایه یک مدل از پیش ساخته شده به دو یا چندین دسته (طبقه Class) است.

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

به طور معمول، ساختن درخت همانطور که در نوشته های پیشین توضیح داده شد، بر پایه دنبال کردن یک سری if .. then است و این تا زمانی ادامه خواهد داشت که تمام برگ ها بدست آمده باشند که این روند منجر به مدل هایی می شود که بسیار پیچیده و کاملاً مطابق با داده های آموزش هستند.

وجود برگ های خالص و ناب (Pure) به معنی صد در صد دقیق بودن مدل ساخته شده از روی مجموعه آموزشی است. هر نقطه از داده های مجموعه آموزشی که در برگ است، دارای کلاس اکثریت صحیح است. در شکل زیر نخست نموداری از هر نقطه از داده های مجموعه داده آموزشی به شمار ۱۰۰ تا در رنگ های آبی (۵۰ تا) و قرمز (۵۰ تا) نشان داده شده است.

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

در نخستین قاعده، X[1] <= 0.0596 که بررسی می کند مقدار ویژگی (متغیر مستقل X1) کوچکتر از شماره 0.0596 باشد، داده ها به دو بخش طبقه بندی می شوند تا اینکه در دسته بالا ۱۸ تا آبی با ۴۸ قرمز و دردسته پایینی ۲ تا قرمز و ۳۲ آبی جای می گیرد (مجموع همگی ۱۰۰ تا). انگیزه آن است که روند ساخت مدل به گونه ای باشد که هر رنگ در دسته خودش جای بگیرد.

از نمودار دوم می بینید که برخی داده های قرمز در ناحیه آبی و برخی از آبی ها در مرز قرمز هستند که این نشان دهنده Overfitting در مدل است. در نوشته مفاهیم Generalization و Overfitting و Underfitting در یادگیری ماشین گفته شده زمانی Overfitting رخ می دهد که مدل بسیار متکی به داده های یادگیری باشد و در برابر آن، Underfitting زمانی است که مدل به خوبی از داده های آموزشی یاد نگرفته باشد. در درخت تصمیم دو رویکرد به نام های Pre-Pruning (پیش از هَرَس) و Post-Pruning (پس از هرس) برای پوشش این دو پدیده نامطلوب هست.

یكی از مشكلات پیش آمده، استفاده بیش از حد قوانین (Rules) برای آموزش داده ها است که در واقع باعث افزایش عمق درخت نیز می شود. با بودن این شمار زیاد از قواعدها، بسیاری از آنها برای داده های هنوز دیده نشده (داده های تازه) ارزش پیش بینی کمی دارند. بنابراین پدیده Overfitting در طبقه بندی درخت تصمیم می تواند به که قوانین بسیار یا قوانینی با دقت پایین پیش بینی برای داده های تازه و هنوز دیده نشده (Unseen Data) منجر شود. در برابر این شمار کمتری از قوانین فراگیر (عمومی) شاید دقت بیشتری روی داده های هنوز دیده نشده داشته باشند.

هرس کردن (Pruning) تکنیکی در یادگیری ماشین و الگوریتم جستجو است که با حذف بخش هایی از درخت که اطلاعات کمی را برای طبقه بندی فراهم می کند، تلاش در کاهش اندازه درخت تصمیم دارد. با تکنیک هرس کردن، پیچیدگی طبقه بند پایانی کاهش پیدا می کند و از این رو با کاهش پدیده Overfitting، دقت پیش بینی بهبود می یابد.

پیش از هرس یا Pre-Pruning

Pre-Pruning روشی برای کاهش پدیده Overfitting در مدل های درخت تصمیم است. پیش از هرس یا Pre-Pruning به زبان ساده، توقف زودهنگام ساخت درخت تصمیم است. به گفته دیگر در این شیوه پیش از آنکه مجموعه داده آموزشی را کاملا طبقه بندی کند از رشد درخت پیش گیری می شود.

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

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

در شیوه پیش از هرس (Pre-Pruning) از ساخته شدن شاخه های بی معنا پیش گیری می شود. در این شیوه، یک درخت تصمیم، شامل استفاده از یک شرط خاتمه (Termination Condition) است، تا تصمیم گرفته شود چه زمانی مناسب برای خاتمه دادن برخی از شاخه ها زودرس ساخته شده است.

در هنگام ساختن درخت می توان از برخی اقدامات مهم برای ارزیابی خوب و مناسب بودن شکسته شدن درخت (شاخه تازه) استفاده کرد. اگر شکسته شدن در یک گره، از حد یک آستانه (Threshold) پایین تر باشد، پس این شاخه متوقف شده وگرنه گسترش پیدا می کند. آستانه بالا (High Threshold) منجر به درختان بزرگتر می شود، در حالی که آستانه پایین (Low Threshold) منجر به ساده سازی بسیار کمی می شود. روشهای مختلفی برای شیوه پیش از هرس (Pre Pruning) وجود دارد.

Post Pruning

شوه پس از هرس (Post Pruning) را شیوه هرس کردن عقب گرد (Backward Pruning) نیز می گویند. در این شیوه، نخست درخت تصمیم ساخته می شود و سپس شاخه های بی معنا حذف می شوند. بنابراین این در برابر شیوه پیش از هرس است که در آن، پیش از ساخته شدن درخت، بررسی می شود که آیا این شاخه تازه مناسب است یا نه؟

شیوه پس از هرس در درخت تصمیم به این معنی است که ما با تولید درخت (کامل) شروع می کنیم و سپس آن را با هدف بهبود دقت طبقه بندی (Classification) برخی از شاخه ها حذف می شوند. توجه کنید در هر دو روش ما به دنبال ساخت درختی هستیم که مدلی را بیان می کند و می خواهیم با بهترین دقت، پاسخ یا پیش بینی هایی را برای داده های دیده نشده (به گفته ای در زمان توسعه و آزمایش، همان داده های آزمایش یا Test Data) را برآورد کند. در هر دو شیوه پیش از یا پس از ساخت درخت، برای این بهبود و رفع Overfitting، شاخه هایی بر طبق معیارهایی حذف می شوند.

چکیده

  • اگر جه درخت های تصمیم ساخته شده با ID3 یا C4.5 با دقت و کارا هستند ولی برای اینکه آنها معمولا درخت هایی با اندازه بزرگ را می سازند.
  • در چنین زمانی که درخت بیش اندازه بزرگ می شود، مدل ساخته شده بسیار متکی به داده های یادگیری شده و از این رو نویزهای درون مجموعه داده تاثیر مخرب خودشان را می گذارند.
  • بزرگ شدن درخت و تکیه بر داده های یادگیری، پدیده Overfitting را پدید می آورد که برآیند آن مدلی ناکارآمد برای پیش بینی داده هایی است که هنوز دیده نشده اند.
  • برای پوشش دادن چیزهایی که در بالا گفته شد، هرس کردن نیاز است که برآیند آن کوتاه شدن اندازه درخت است.
  • هرس درخت تصمیم یک گام اساسی در بهینه سازی بهره وری محاسباتی و همچنین دقت طبقه بندی است.
  • هرس معمولاً منجر به کاهش اندازه درخت می شود و از پیچیدگی غیرضروری جلوگیری می شود و از این رو، از Overfitting در هنگام یادگیری مدل جلوگیری می کند.
  • Overfitting می تواند منجر به ساخت شمار زیادی قاعده (Rule) شود که بسیاری از آنها ارزش پیش بینی درستی برای داده های هنوز دیده شده نخواهند داشت.
  • شوه های گوناگونی برای پیش از هرس مانند Minimum no of object pruning یا Chi-square pruning و برای شیوه پس از هرس مانند Reduced Error Pruning و Minimum Error pruning هست که نوشته ای جداگانه را نیاز دارد.

الگوریتم CART

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

  • گره های میانی نماینده یک ویژگی
  • گره های برگ نماینده پاسخ – کلاس – برچسب
  • برای شکسته شدن، از معیار gini index کمک گرفته می شود.
  • این الگوریتم برای مسئله های رگرسیون و طبقه بندی استفاده می شود.
  • در الگوریتم CART، داده ها به دو شاخه به دو زیر مجموعه تبدیل می شوند به طوری که داده های درون هر یک از زیر مجموعه ها، داده ها همگن تر (Homogeneous) هستند.
  • این فرایند شکستن و زیر مجموعه مجموعه شدن، بازگشتی است و تا زمانی ادامه پیدا می کند که به یک سطح از همگنی برسم.