سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
در جلسه گذشته دیدیم که یکی از معیارها برای چیدن درخت و انتخاب ریشه آنتروپی هست که در واقع پایه Information Gain است.
فرض کنید نماد Hs(Y) برای این بکار برده میشه: آنتروپی روی متغیر تصادفی Y با استفاده از مجموعه سمپل‌های S. یعنی در مجموعه سمپل‌های S ببینیم چند درصد داده‌ها برچسبشون مثبته، چند درصد برچسبشون منفیه.
حالا این معیار چی داره میگه؟ میگه اگه مجموعه سمپل S رو داری و ویژگی A، میزان خوب بودن ویژگی A یا به عبارتی دیگه میزان شکسته شدن داده‌ها بر اساس ویژگی A رو به صورت زیر در نظر بگیر:
اول ببین داده‌ها تو همون مجموعه سمپلی که داریم بررسی می‌کنیم برچسبشون چه میزان آنتروپی داره. بعد با استفاده از ویژگی A داده‌هارو تقسیم کن. بعد از دیدن ویژگی دوباره بیا میزان آنتروپی رو محاسبه کن.
هرچی یک ویژگی باعث بشه که مقدار بیشتری از میزان آنتروپی کم بشه، به این معنی هست که اون ویژگی خیلی موثرتر بوده. یعنی انگار داده‌ها به صورتی شکسته شدن که در هر ناحیه هم برچسب هستن.
فقط معیار آنتروپی رو برای استفاده نداریم و معیارهای دیگه‌ای هم هست که استفاده میشه که به کمکش نشون بدن چه مقدار عدم یکنواختی در برچسب‌ها وجود داره.
جلسه قبلی یک مثالی رو دیدیم که کامل حلش نکردیم و در مورد بازی تنیس بود. 14 تا سمپل بود که 9 تاش مثبت بودن به این معنی که بازی تنیس برگزار میشه و 5 تاش منفی که یعنی بازی تنیس برگزار نمیشه. حالا دو تا ویژگی داریم، می‌خوایم ببینیم بر اساس کدوم ویژگی داده‌هارو بشکنیم.
اول مقدار IG رو باید در ریشه برای ویژگی Humidity حساب کنیم. بعد جمع وزن‌دار آنتروپی در فرزندان رو ازش کم کنیم. حاصلش رو باید با محاسبات مشابه در ویژگی دوم مقایسه کنیم. کدوم رو انتخاب کنیم؟ اونی که میزان gain بیشتری داره رو انتخاب می‌کنیم که اگر محاسبات رو انجام بدیم میشه درخت سمت چپ.
این معیار بین دو متغیر تصادفی تعریف میشود. فرمولش پایین اومده. به معنی کاهش مقدار آنتروپی Y بعد از دیدن مقدار X است. به عبارتی دیگه یعنی چقدر مقدار آنتروپی Y بعد از دیدن مقدار X کاهش پیدا کرده. مقدار لگاریتم زمانی که 1 شود جواب برابر با صفر میشود. 1 شدن لگاریتم برابر است با برابر شدن صورت و مخرج. صورت و مخرج در صورتی باهم برابر می‌شوند که دو متغیر X و Y از هم مستقل باشند. اگر ویژگی‌ای رو در نظر بگیریم که MI زیادی با برچسب داره، یعنی از برچسب مستقل نیست، یعنی اگر داده‌هارو برحسب اون بشکنیم، انگار برحسب برچسب شکستیم.
حالا طبق این معیار کدوم ویژگی‌ها برامون باارزش‌ترن؟ اون ویژگی‌هایی که از برچسب مستقل هستن برامون ارزشی ندارن.
اگه آنتروپی رو به صورت شرطی بنویسیم به فرمول زیر می‌رسیم:
اینجا هم ازش یک مثال آورده شده:
حالا ببینیم تا اینجا در مورد معیارهای مختلف چی گفتیم. اول اینکه از بین همه ویژگی‌ها دنبال اون ویژگی گشتیم که برای مجموعه نمونه‌های S منجر به بیشینه شدن Gain بشه. مقدار Gain رو هم به صورت زیر تعریف کردیم.
ادامه مثالی که بالاتر دیدیم اینجا آورده شده. اولین ویژگی رو به کمک همین معیار Information Gain ست کرده بعنوان ریشه. بعد بین ویژگی‌های باقی‌مونده مجددا معیار حساب کرده و تصمیم گرفته.
این الگوریتم رو در جلسه گذشته دیدیم که یه جورایی به صورت بازگشتی عمل می‌کرد.
اگر داده مجموعه آموزش سازگار داشته باشیم، سازگار به این معنی که اگه دو تا سمپل داریم که همه ویژگی‌هاشون عین همه دیگه‌س برچسبشون هم عین هم باشه و نتونه متفاوت باشه، حالا تو این حالت مقدار خطای آموزش الگوریتم درخت تصمیم چقدر میشه؟ مقدار خطای آموزش همیشه صفر میشه.
حالا انتخاب ویژگی به صورت حریصانه انجام میشد و باید حداکثر Information Gain رو داشته باشه. این کار باعث میشه که سایز درخت تا حد خوبی کوچیک بشه. چرا؟ چون امیدواریم که تو یک سری نودها زودتر به یکنواختی برسیم و دیگه گسترش پیدا نکنن. پس امیدواریم که سایز درختمون کوچیک‌تر بشه.
حالا هرچقدر سایز درخت کوچیک‌تر باشه کمک میکنه کنه خطای تعمیم‌پذیری کمتر بشه. چرا؟ انگار به درخت‌ها با سایز کوچیک‌تر اولویت بیشتری میدیم که باعث میشه واریانس کمتر بشه. البته درسته که امیدواریم سایز درختمون کوچیک بشه، اما از طرفی دیگه ما داده‌ها رو تا زمانی می‌شکنیم که کاملا از هم جدا بشن و ممکنه به حالتی برسیم که مجبور بشیم بخاطر یک داده یک نود رو مجددا ادامه بدیم و همین باعث پیچیده‌تر شدن درختمون میشه.
چون شرط پایان الگوریتم چیز خیلی خوبی نیست، باعث میشه که overfitting رخ بده.
فرض کنید برای سادگی متغیرهارو یک سری بولین در نظر گرفتیم. هر مسیر از ریشه تا برگ با یک سری AND نشون داده میشه. OR ها هم داره برگ‌های مختلف مثبت رو نشون میده.
پس درخت تصمیم داره یه‌جورایی تمام توابع بولین رو پوشش میده.
از نظر هندسی جواب به صورت زیر در میاد. چون داریم بر اساس مقدار متغیر تصمیم می‌گیریم، اون ویژگی یا تو قانونی که داشتیم ظاهر شده یا ظاهر نشده. اگه شرطی اعمال نکرده باشیم انگار یه مکعب مستطیل داریم که کشیده شده، اگر شرطی اعمال کرده باشیم، اون مکعب مستطیل رو محدود و محدودتر می‌کنیم. ناحیه مثبت هم در فضا از اجتماع یک‌سری ابر مکعب مستطیل تشکیل شده.
تصویر زیر هم گریدی بودن الگوریتم رو نشون میده که فقط از یک مسیر میریم جلو و بقیه مسیر‌هارو چک نمی‌کنیم و به عقب هم برنمی‌گردیم.
یکی از مشکلات اساسی این الگوریتم overfitting هست که اگه حواسمون نباشه خیلی زود رخ میده. یه مثال ازش ببینیم.
همون مثال تنیس رو در نظر بگیرید. فرض کنید یک نمونه منفی به داده‌هامون اضافه شده. تو اون قسمت قرمز رنگ بخاطر اون یک نمونه و جدا کردنش از نمونه‌های مثبت مجبور شده دوباره اون نود درخت رو بشکنه به دو نود دیگه که همین باعث overfitting میشه.
نمودار زیر هم داره میزان دقت رو به ازای تعداد نودها نشون میده. هرچقدر تعداد نودها بیشتر شده دقت روی داده‌های آموزش بیشتر شده ولی همزمان دقت روی داده‌های جدید کمتر شده که همون نشون دهنده overfitting هست.
حالا اصلا به چه صورت می‌تونیم جلوی overfitting رو بگیریم؟
دو راه کلی وجود داره:
برای یک زیر درخت چند حالت مختلف داریم:
حالا وقتی که می‌خوایم هرس کردن رو انجام بدیم از خطای cross validation استفاده می‌کنیم. به این صورت که به هر زیر درختی که می‌رسیم یک بار بعنوان زیر درخت مقدار CV را روی آن محاسبه می‌کنیم و یک بار در حالتی که آن را به یک نود تبدیل کرده‌ایم. این کار را روی همه زیر درخت‌های موجود انجام داده و نهایتا آن زیر درختی که در اثر هرس شدن باعث شود خطای CV از همه کمتر شود را انتخاب می‌کنیم.
یک extension از الگوریتم ID3 هست. درخت تصمیم رو به صورت یک‌سری مجموعه قواعد در میاره که یکم بالاتر اشاره‌ای بهش کردیم. هرس کردن رو بر اساس نودها انجام نمیده، بر اساس حذف اون عبارات انجام میده. حذف کردن این قوانین باعث میشه که یک ویژگی خاص از کل زیر درخت حذف نشه و فقط از بخشی از اون هرس بشه ولی در روش قبلی اگر ویژگی بالاتری رو حذف می‌کردیم انگار از کل زیر درخت حذف شده بود.
همه چیزهایی که تا اینجا بررسی کردیم ویژگی‌های گسسته داشتن، حالا اگه ویژگی پیوسته بود چیکار کنیم؟ می‌تونیم یک حدی تعیین کنیم بگیم اگر بیشتر از اون حد بود مثلا برچسبش + باشه و اگه کمتر بود برچسبش - شه. حالا حد رو چطور تعیین کنیم؟ فرض کنید سه حد مختلف در نظر می‌گیریم چجوری بفهمیم کدوم رو باید انتخاب کنیم؟ باید به ازای هر threshold مانند قبل یک دور information gain را محاسبه کنیم و در نهایت هر حدی که باعث شد information gain بهتری داشته باشیم با توجه به ویژگی‌ها، آن را مد نظر قرار دهیم.
معیار Mutual Information سعی بر این داره که اول ویژگی‌هایی رو انتخاب کنه که تعداد مقادیر بیشتری دارند. یعنی یک ویژگی با 10 مقدار رو بعنوان ریشه در نظر می‌گیره به‌جای انتخاب ویژگی با 2 مقدار. این باعث میشه که دسته‌بندی‌مون خیلی خوب نباشه و سایز درخت رو زیاد میکنه.
اسلاید زیر داره انواع مختلف درخت‌های تصمیم رو نشون میده که بر اساس مقالات مختلف به دست اومده.
به صورت کلی درخت تصمیم یکی از ساده‌ترین دسته‌بندهای موجود هست و در عین سادگی تا حد خوبی می‌تونه عملکرد خوبی داشته باشه. چندین معیار مختلف رو برای دسته‌بندی در موردش بررسی کردیم و به صورت کلی دو الگوریتم مختلف رو هم دیدیم. یکی از معایبش اینه که خیلی زود دچار overfitting میشه و با دو راهکار مختلف متوقف کردن زودهنگام و هرس کردن درخت جلوش رو گرفت.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
