34 شکاف دودویی و ناخالصی

همانطور که در قسمت آخر فصل قبل اشاره کردیم ، روند ساخت یک درخت تصمیم باینری به سه مؤلفه اصلی نیاز دارد:

مجموعه ای از تقسیمات قابل قبول را برای هر گره ایجاد کنید: تمام شکافهای باینری ممکن را محاسبه کنید.

معیار را برای یافتن تقسیم گره "بهترین" تعریف کنید: برخی از معیارهای بهینه سازی بهینه سازی شده. این به نوبه خود ، نیاز به تعیین برخی از ناهمگونی (در یک گره معین) دارد.

یک قانون را برای اعلام یک گره معین به عنوان گره داخلی یا گره برگ تعیین کنید.

در این فصل ما این مؤلفه ها را با جزئیات بیشتری بررسی خواهیم کرد.

34. 1 پارتیشن باینری

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

1. متغیرهای دودویی
2. متغیرهای نظم
3. متغیرهای اسمی
4. متغیرهای پیوسته

تعداد تقسیمات باینری ممکن برای هر نوع متغیر تقسیم بندی در زیر شرح داده شده است.

34. 1. 1 تقسیم متغیرهای باینری

از آنجا که متغیرهای باینری دارای دو مقدار هستند ، آنها فقط یک پارتیشن باینری تولید می کنند. به عنوان مثال ، می گویند ما یک جنس متغیر با دو مقدار ، زن و مرد داریم. این ویژگی فقط می تواند به یک روش ممکن تقسیم شود:

شکل 34. 1: مثال یک پارتیشن باینری برای یک متغیر باینری

34. 1. 2 تقسیم متغیرهای اسمی

یک متغیر اسمی ممکن است دسته های زیادی داشته باشد و تعداد تقسیمات باینری به تعداد دسته های مجزا برای متغیر مربوطه بستگی دارد. تعداد کل پارتیشن های باینری ممکن برای یک متغیر اسمی با دسته \ (q \) است

به عنوان مثال ، فرض کنید یک رنگ متغیر با سه دسته: آبی ، سفید و قرمز. تعداد تقسیمات باینری برای این ویژگی اسمی:

شکل 34. 2: نمونه ای از تقسیمات باینری برای یک متغیر اسمی

34. 1. 3 تقسیم متغیرهای نظم

تقسیمات باینری برای متغیرهای معمولی باید به خاصیت سفارش دسته ها احترام بگذارد ، یعنی گروه بندی دسته ها باید ترتیب را در بین مقادیر حفظ کنند. تعداد کل پارتیشن های باینری برای یک متغیر معمولی با دسته \ (q \) است

به عنوان مثال ، اندازه پوشاک ممکن است چهار دسته داشته باشد: کوچک (S) ، متوسط (M) ، بزرگ (L) و فوق العاده بزرگ (XL). در این حالت ، تعداد شکاف های باینری خواهد بود

شکل 34. 3: نمونه ای از تقسیمات باینری برای یک متغیر معمولی

34. 1. 4 متغیرهای مداوم را تقسیم می کند

درمان متغیرهای مداوم به تعداد مقادیر مختلفی که متغیر در نظر می گیرد بستگی دارد. فرض کنید یک متغیر مداوم با مقادیر مختلف \ (q \). اگر در نظر بگیریم که \ (q \) به نوعی "کافی" است ، می توانیم متغیر مداوم را مانند یک متغیر معمولی درمان کنیم. اگر \ (q \) را بزرگ بدانیم ، ممکن است مقادیر آن را گروه بندی کنیم و تعداد آنها را در \ (q^*\) کاهش دهیم (\ (q^*

\ [Q-1 \ Quad \ Text \ Quad Q^*-1 \]

به عنوان مثال ، سن متغیر مداوم (اندازه گیری شده در سالها) را با پنج مقدار 5 ، 7 ، 8 ، 9 و 10 تصور کنید

شکل 34. 4: نمونه ای از تقسیمات باینری برای یک متغیر مداوم

جدول زیر تعداد تقسیمات باینری را بسته به نوع مقیاس برای یک ویژگی خاص نشان می دهد.

34. 2 اقدامات ناخالصی

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

برای اهداف توضیحی، اجازه دهید روی یک گره با اشیاء \(n = 14\) تمرکز کنیم که به کلاس‌های \(2\) تقسیم می‌شوند. یک کلاس با \(\bigcirc\) و دیگری با \(\Delta\) مشخص می شود. هر دو کلاس دارای اشیاء \(7\) هستند. فرض کنید این گره به صورت زیر تقسیم می شود:

شکل 34. 5: تقسیم فرضی یک گره

ما احساس شهودی داریم که گره والد ناهمگونی بیشتری نسبت به گره های فرزند خود دارد. در واقع، این یک نتیجه کلی است: یک تقسیم نمی تواند منجر به گره های فرزند با ناهمگونی بیشتر از گره والد شود. با بیان متفاوت، شما هرگز نمی توانید بدتر از گره والد انجام دهید.

در گره والد شکل قبلی، نسبت \(\bigcirc\) برابر با نسبت \(\Delta\) است. به عبارت دیگر، احتمال یک \(\bigcirc\) بودن برابر با یک \(\Delta\) وجود دارد. با این حال، در گره سمت چپ، شانس بیشتری برای \(\bigcirc\) بودن نسبت به \(\Delta\) وجود دارد (در مورد گره سمت راست برعکس است).

بیشتر معیارهای ناهمگنی (و در نتیجه همگنی) به نسبت طبقات در یک گره والد مربوط می شود. بیایید چند ایده در مورد نحوه انجام این کار را با هم مرور کنیم:

\(\mathrm(\bigcirc) - \mathrm(\Delta)\) ;در این مورد باید نوعی تفسیر به مقدار \(0\) اختصاص دهید.

آنتروپی (اطلاعات، همانطور که از دیدگاه علم کامپیوتر مشاهده می شود). همچنین می تواند به این به عنوان معیاری از "بی نظمی" در یک گره اشاره کند.

ناخالصی (چقدر مختلط، متنوع)

34. 2. 1 آنتروپی

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

بیایید با یک مثال (انتزاعی) اسباب بازی شروع کنیم: می گوییم یک جعبه حاوی 12 شی داریم که همه از یک کلاس هستند (مثلاً \(\bigcirc\)).

شکل 34. 6: مجموعه ای از 12 شی از همان نوع

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

حال، فرض کنید سه مورد از آن \(\bigcirc\) با \(\square\) جایگزین شده است.

شکل 34. 7: مجموعه ای با دو نوع شی مختلف

اگر بخواهیم به طور تصادفی یک شی را از این کادر ترسیم کنیم، مقداری عدم قطعیت در مورد کلاس آن وجود خواهد داشت. یعنی مقداری آنتروپی وجود دارد. از نظر احتمال، احتمال 9/12 وجود دارد که شی انتخاب شده \(\bigcirc\) باشد و احتمال 3/12 وجود دارد که شی ترسیم شده \(\square\) باشد.

در نهایت، در شدیدترین حالت، فرض کنید که 12 شی داریم، همه از کلاس های مختلف، مانند نمودار زیر:

شکل 34. 8: مجموعه ای با 12 نوع شی مختلف

ما در مورد طبقات اشیاء ترسیم شده از این کادر کاملاً نامطمئن هستیم. یعنی حداکثر آنتروپی را داریم.

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

شکل 34. 9: مجموعه ای با 12 نوع شی مختلف

حال، بیایید ببینیم چگونه می‌توانیم ایده آنتروپی خود را با ایده احتمال مرتبط کنیم. از مثال های بالا، می توانیم رابطه زیر را هنگام انتخاب تصادفی یک شی از کادر مشاهده کنیم:

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

عملکردهای زیادی وجود دارد که این رفتار را نشان می دهد. موردی که ما استفاده خواهیم کرد لگاریتم هر پایه \(b\) است. توجه داشته باشید که

\[ \log_b(P) : [0، 1] \به (-\infty، 0] \]

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

34. 2. 2 ریاضی پشت آنتروپی

اگر اجازه دهیم \(H(\text)\) آنتروپی یک گره خاص را نشان دهد، از تعریف زیر استفاده می کنیم:

جایی که \(p_k\) نشان دهنده احتمال انتخاب تصادفی یک شی است که از کلاس \(k\) آمده است. به علامت منفی در فرمول بالا توجه کنید. دلیل این علامت منفی داشتن مقادیر مثبت از لگاریتم احتمالات است. طبق قرارداد، ما از گزارشی از پایه 2 استفاده می کنیم. منطق پشت انتخاب \(2\) از نظریه اطلاعات ناشی می شود، زیرا گزارش های پایه 2 را می توان بر حسب بیت تفسیر کرد. علاوه بر این، اگر \(p_j = 0\) برای برخی کلاس \(j \in \\) , \(p_j \log_b(p_j) = 0\) را تنظیم می کنیم زیرا \[ \lim_ \left[ p_j \log_b(p_j)

ight] = 0 \] به این ترتیب، هرگز مجبور نیستیم به طور مستقیم \(\log_b(0)\) را ارزیابی کنیم.

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

\[\شروع H(\text) &= - p_1 \cdot log_2 (p_1) \\ &= -(1) \cdot \log_2(1) \\ &= -1 \cdot 0 = 0 \end\]

اکنون، برای مثال دوم در بالا، کلاس های \(K = 2\) با \(p_1 = 9/12\) و \(p_2 = 3/12\) داریم، به طوری که

\[\begin H(\text) &= - p_1 \log_2 (p1) - p_2 \log_2 (p_2) \\ &= - \frac \log_2\left( \frac

ight) - \frac \log_2\left(\frac

ight) \تقریباً 0. 8112 \end\]

در گره ای که یک تقسیم 50-50 وجود دارد، داریم

\[\begin H(\text) &= - p_1 \log_2 (p1) - p_2 \log_2 (p_2) \\ &= - \frac \log_2\left( \frac

ight) - \frac \log_2\left(\frac

ight) = 1 \end\]

شکل زیر چندین نمونه از مجموعه ها و مقادیر آنتروپی آنها را نشان می دهد.

شکل 34. 10: مجموعه های مختلف با مقادیر آنتروپی آنها

34. 2. 3 ناخالصی جینی

• نوع دوم اندازه گیری ناهمگنی (یا ناخالصی) که توضیح خواهیم داد ناخالصی جینی است که به آن شاخص جینی نیز می گویند.
• اجازه دهید به مثال جعبه دوم از بخش قبل برگردیم. 9 \(\bigcirc\) و 3 \(\square\) وجود دارد.
• شکل 34. 11: مجموعه ای با دو نوع شی مختلف
• فرض کنید من به طور تصادفی یک توپ را انتخاب می کنم و توجه می کنم که به چه کلاسی تعلق دارد. سپس از شما می خواهم (بدون اینکه هیچ اطلاعاتی در مورد جعبه به شما بدهم، به جز این واقعیت که \(\bigcirc\) و \(\square\) وجود دارد)، حدس بزنید که شی انتخاب شده من متعلق به چه کلاسی است.

4 نتیجه ممکن برای این وضعیت وجود دارد:

• اجازه دهید به مثال جعبه دوم از بخش قبل برگردیم. 9 \(\bigcirc\) و 3 \(\square\) وجود دارد.
• شکل 34. 11: مجموعه ای با دو نوع شی مختلف

من \(\square\) را انتخاب می کنم، حدس می زنید \(\bigcirc\) .

من \(\square\) را انتخاب می کنم، حدس می زنید \(\square\) .

شاخص جینی به طبقه بندی های اشتباه توجه می کند. یعنی موقعیت هایی که حدس شما اشتباه بوده است. به عنوان مثال، در مثال بالا، در مجموع 2 طبقه بندی اشتباه وجود دارد:

من \(\bigcirc\) را انتخاب می کنم، حدس می زنید \(\square\) .

من \(\square\) را انتخاب می کنم، حدس می زنید \(\bigcirc\) .

شاخص جینی شامل احتمال نادرست طبقه بندی یک شیء به طور تصادفی از جعبه است. به شرح زیر محاسبه می شود:

برای یک گره معین حاوی اشیاء کلاسهای \ (k \) ، ناخالصی جینی توسط:

با انجام کمی جبر ، می توان فرمول های جایگزین برای ناخالصی جینی پیدا کرد:

چند نمونه

برای اهداف تصویرگری ، اجازه دهید ناخالصی جینی یک گره حاوی 12 شیء را محاسبه کنیم ، همه در یک کلاس:

شکل 34. 12: مجموعه ای از 12 شی از همان نوع

\ [\ شروع gini (\ text) & = \ sum_^ p_k (1 - p_k) \\ & = \ سمت چپ (\ frac \ راست) \ سمت چپ (\ frac \ راست) = 0 \ end \]

اکنون یک گره متعادل را با اشیاء دو کلاس در نظر بگیرید

شکل 34. 13: مجموعه متعادل دو طبقه

ناخالصی جینی در این مورد:

\ [\ شروع gini (\ text) & = \ sum_^ p_k (1 - p_k) \\ & = \ سمت چپ (\ frac \ راست) \ سمت چپ (\ frac \ راست) + \ سمت چپ (\ frac \ راست) \سمت چپ (\ frac \ راست) = 0. 5 \ پایان \]

شکل زیر نمونه های مختلفی از مجموعه ها و ناخالصی های جینی آنها را نشان می دهد.

شکل 34. 14: مجموعه های مختلف با ناخالصی های جینی آنها

34. 2. 4 ناخالصی مبتنی بر واریانس

تاکنون وقتی یک پاسخ طبقه بندی می کنیم ، اقدامات ناخالصی را در نظر گرفته ایم. اما در مورد یک پاسخ کمی چیست؟در این مورد از چه معیار ناخالصی می توانیم استفاده کنیم؟

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

به عنوان مثال ، یک گره والدین را در نظر بگیرید که توسط \ (n \) مشخص شده است. مجموع انحرافات مربع از میانگین توسط:<\mathcal>جایی که \ (\ bar \) میانگین پاسخ برای افراد در گره \ (n \) است.<\mathcal>حال فرض کنید ما به دنبال بهترین تقسیم باینری در میان مجموعه ای از ویژگی های \ (x_1 ، \ dots ، x_m \) هستیم.

می گویند ما پیش بینی کننده \ (x_j \) را می گیریم ، و ما در حال ارزیابی یک شرط تقسیم شده توسط مقدار برش \ (s \) هستیم. این بدان معنی است که \ (s \) فضای ویژگی را در دو منطقه \ (\ mathcal \) و \ (\ mathcal \) تقسیم می کند: