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

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

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

شاخص جینی

شاخص جینی (Gini Index) یا ضریب جینی (Gini Coefficient) یک معیار آماری از توزیع است که بدست آمارگر ایتالیایی، کورادو جینی، در سال ۱۹۱۲ ساخته شده است. از کاربردهای آن می توان در زمینه های سنج نابرابری اقتصادی، اندازه گیری توزیع درآمد یا معمولاً توزیع ثروت در میان جمعیت اشاره کرد. در زمینه یادگیری ماشین، معیار اندیس جینی در کنار بهره اطلاعات (Information Gain)، هر دو برای برگزیدن یک ویرگی برای یک گره نابرگ به کار می روند.

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

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

  • الگوریتم های ID3 و C4.5 از Information Gain کمک می گیرند.
  • الگوریتم CART از Gini Index کمک می گیرد.

نمونه مثال هایی از شاخص جینی

گمان کنید دو کلاس قرمز و آبی داریم و می خواهیم چهار توپ را با این دو رنگ برچسب گذاری کنیم. اگر تصمیم بگیرید هر چهار توپ را قرمز کنید، یعنی ۴ توپ قرمز و صفر توپ آبی، این انتخاب تصادفی شما تا چه اندازه نادرست است. خط زیر محاسبه مجموع توان دو احتمال هر یک از کلاس های قرمز و آبی را نشان می دهد. توجه کنید کل فضای نمونه ما ۴ تا توپ است که احتمال قرمز بودن 4/4 و احتمال آبی بودن برابر با 0 = 0/4 است.

در بالا اندازه شاخص جینی صفر شد، یعنی با برچسب گذاری ۴ توپ به رنگ قرمز، هرگز انتخاب نادرستی نخواهد بود. اکنون گمان کنید که تصمیم می گیریم تصادفی دو توپ را قرمز و ۳ توپ دیگر را آبی رنگ (برچسب گذاری) کنیم. اکنون بر پایه شکل زیر اندازه شاخص جینی برابر با ۰.۵ خواهد بود. اکنون شما برای برچسب گذاری ۳ تو قرمز و یک توپ آبی شاخص جینی را بدست آورید.

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