اولین چالش که درخت تصمیم گیری با آن مواجه است، این است که مشخص شود شکسته شدن بر اساس کدام ویژگی انجام شود. الگوریتم C5.0 از آنتروپی به عنوان یک معیار استفاده می کند، مفهومی که از تئوری اطلاعات (Information Theory) گرفته شده است که مقدار تصادفی یا اختلال (Disorder) را در مجموعه ای از مقادیر کلاس محاسبه می کند.

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

در این نوشته می خواهیم درباره دو مفهوم آنتروپی و بهره اطلاعات سخن بگوییم که دو میعار پایه برای الگوریتم های درخت تصمیم هستند. این نوشته به ویژه درباره الگوریتم ID3 گفتگو می کنیم که از معیار IG یا بهره اطلاعات (Information Gain) کمک می گیرد. بهره اطلاعات معیاری برای برگزیدن بهترین ویژگی برای انشعاب است و برای بدست آوردن IG نیاز به داشتن معیار دیگری به نام آنتروپی داریم.

بهترین ویژگی کدام است

تا بدین جا باید فهمیده باشید که در ساخت درخت تصمیم، برجسته ترین نکته آن است که از میان ویژگی ها، کدام ویژگی، برای جای گرفتن در ریشه و سپس لایه های، بهترین دیگر است. در شکل زیر گمان کنید که دو کلاس (منفی و مثبت یا Yes و No یا Play و No Play) و همچنین تنها دو تا از همه ویژگی ها به نام A1 و A2 را داریم و می خواهیم بدانیم کدام ویژگی باید برای ریشه برگزیده شود. توجه کنید هم اکنون همه داده ها در ریشه هستند.

شکل بالا نشان می دهد که در ریشه می خواهیم از میان دو ویژگی A1 و A2 یکی را برای ریشه برگزینم. در آغاز همه ۶۴ نمونه (۳۵ + ۲۹ نمونه) در ریشه هستند. از این ۶۴ نمونه، ۲۹ تای آن در کلاس مثبت (Yes) و ۳۵ تای آن در کلاس منفی (No) و همچنین مقدار و.یژگی ها  به گونه بولی و دارای مقدارهای t و f هستند. اگر A1 را برگزنیم، پس با توجه به مقدار آنها، اگر مقدار t باشد، پس ۲۱ نمونه در کلاس مثبت و ۵ نمونه در کلاس منفی هستند. اگر مقدار ویژگی A1 برابر با f باشد، پس ۸ نمونه در کلاس مثبت و ۳۰ نمونه در کلاس منفی هستند. همین را می توان برای A2 نیز گفت.

آنتروپی چیست

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

آنتروپی صفر است، اگر همه نمونه های یک گره متعلق به یک کلاس باشند و  آنتروپی بیشینه (Maximum) است، اگر توزیع کلاس یکسان (Uniform Class Ditribution) داشته باشیم. به عبارت دیگر، آنتروپی یک گره که شامل تک کلاس است، برابر با عدد صفر است زیرا احتمال ۱ می شود و log (1) = 0 است. آنتروپی به حداکثر مقدار می رسد زمانی که همه کلاس ها در گره احتمالا یکسان هستند.

اگر تنها دو کلاس (طبقه – Class) وجود داشته باشد، پس مقدار آنتروپی صفر تا یک خواهد بود ولی اگر n کلاس وجود داشته باشد، پس مقدار آنتروپی میان صفر تا (log(n است. در هر مورد، مقدار کیمنه (Minmum Value) نشان دهنده این است که نمونه (Sample) کاملا همگن (Homogeneous) است.

گمان کنید مجموعه داده ای به نام S دارید که در آن چندین نمونه (Sample) هست که تنها به دو کلاس C1 و C2 تعلق دارند. برای نمونه اگر ۱۰ نمونه داشته باشیم و اگر هر ۱۰ نمونه به کلاس C1 تعلق داشته باشند (و از این رو صفر نمونه به کلاس C2تعلق داشته باشد)، در این گونه آنتروپی E برای این مجموعه برابر صفر است، زیرا همه ۱۰ نمونه متعلق به یکی از کلاس و آن هم کلاس C1 هستند. حال اگر ۵ نمونه در کلاس C1 و ۵ نمونه در کلاس C2 باشند، پس آنتروپی برابر با یک است. به طور کلی هر چه آشفتگی کمتر باشد، آنتروپی نیز کمتر هست. همچنین اگر دو کلاس داشته باشیم، پس آنتروپی شماره ای میان صفر تا یک خواهد بود.

نمونه آنتروپی

شکل زیر ۱۴ نمونه از نمونه های روزهایی که می توان (کلاس Yes) یا نمی توان (کلاس No) تنیس بازی کرد را نشان می دهد. همچنین از میان این ۱۴ نمونه ۹ تای آن کلاس کلاس Yes هستند و از این رو شانس (احتمال) بروز کلاس Yes برابر با ۹/۱۴ است. بنابراین ۵ نمونه دیگر در کلاس No و شانس (احتمال) آن برابر با ۵/۱۴ است. بر پایه فرمول آنتروپی (شکل نخست بالا)، و با توجه به دو شانس گفته شده، آنتروپی برابر با ۰.۹۴۰ خواهد بود.

بنابراین نخستین گام در الگوریتم های درخت تصمیم (ID3) بدست آوردن اندازه آنتروپی است. آنتروپی شماره ای است که اندازه همگنی و پراکندگی نمونه های یک مجموعه داده را نشان می دهد. آنتروپی تنها یکی از معیارهای ساخت درخت تصمیم است. Information Gain یا بهره اطلاعات یکی دیگر از معیارهای ID3 (و C4.5) است.

بهره اطلاعات

پس از آنکه داده ها بر پایه یک ویژگی، به زیر شاخه هایی شکسته شوند، انتظار داریم تا آنتروپی کاهش پیدا کند، از این رو بهره اطلاعات (Information Gain) برابر است با مقدار کاهش آنتروپی، پس از شکسته شدن داده ها بر پایه یکی از ویژگی ها. شکل زیر فرمول بدست آوردن مقدار بهره اطلاعات را نشان می دهد که در آن (Entropy(S مقدار آنتروپی پیش از انشعاب و (values(S، مجموعه همه مقدارهای ویژگی A هستند. Sv زیر مجموعه ای از مجموعه S است که برای آن، ویژگی A دارای مقدار V است.

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

گام های برگزیدن ویژگی برای انشعاب

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

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