سؤال مصاحبه

محاسبه‌ی امتیاز گره درخت با جینی و آنتروپی

Score a tree node with Gini and with entropy

  • سطح ۲: میانی
  • تخمین
  • ۸ دقیقه

گرهی در یک درخت تصمیم (Decision tree) دسته‌بندی، شامل 6 گربه و 4 سگ است. ناخالصی جینی (Gini impurity) و آنتروپی (Entropy) آن را برحسب بیت به دست آورید و توضیح دهید درخت چگونه از این دو عدد برای انتخاب یک انشعاب (Split) استفاده می‌کند.

اول خودتان جواب بدهید، بعد پاسخ را باز کنید.

پاسخ کوتاه

سهم هر کلاس 0.6 و 0.4 است. جینی برابر است با 1 منهای مجموع توان دوم سهم‌ها؛ یعنی 1 منهای 0.36 منهای 0.16، که حاصل 0.48 می‌شود. آنتروپی برابر است با منفیِ مجموع حاصل‌ضرب سهم در لگاریتم مبنای 2 سهم، که به 0.971 بیت می‌رسد. درخت تک‌تک ویژگی‌ها و آستانه‌ها (Thresholds) را بررسی می‌کند و انشعابی را نگه می‌دارد که بیشترین کاهش را از ناخالصی والد به ناخالصی وزن‌دار دو فرزند داشته باشد.

پاسخ کامل

دو معیار عددی

Gini    = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 0.48
Entropy = -(0.6 * log2(0.6) + 0.4 * log2(0.4))
        = -(0.6 * -0.737 + 0.4 * -1.322)
        = 0.442 + 0.529 = 0.971 bits

جینی احتمال این است که اگر برچسب یک نمونه‌ی تصادفی در گره را بر اساس توزیع کلاس‌های همان گره تعیین کنید، آن برچسب اشتباه از آب درآید. آنتروپی، میانگین میزان غافلگیری (Surprise) برچسب‌ها در گره است. هر دو معیار برای یک گره خالص برابر با 0 هستند. برای گرهی با دو کلاس و سهم‌های برابر، جینی 0.5 و آنتروپی 1.0 بیت است.

نحوه‌ی استفاده‌ی درخت از این معیارها

بهره‌ی اطلاعات (Information gain) یک انشعاب برابر است با ناخالصی والد منهای میانگین وزن‌دار ناخالصی فرزندان، که در آن وزن هر فرزند برابر با سهمش از کل نمونه‌هاست. این الگوریتم حریصانه (Greedy) عمل می‌کند: در هر گره مقادیر هر ویژگی را مرتب می‌کند، نقطه‌ی میانی میان هر دو مقدار متمایز را به‌عنوان آستانه می‌آزماید و جفتی را که بیشترین بهره را دارد نگه می‌دارد. سپس همین روند را به‌صورت بازگشتی برای هر دو فرزند تکرار می‌کند. تقسیم حریصانه بهترین درخت ممکن را پیدا نمی‌کند، چون این مسئله NP-hard است، اما در عمل بسیار خوب جواب می‌دهد.

جینی یا آنتروپی

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

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 2: بهره‌ی انشعابی که همه‌ی گربه‌ها را در یک طرف و همه‌ی سگ‌ها را در طرف دیگر قرار می‌دهد چقدر است؟ پاسخ مورد انتظار: فرزندان خالص هستند، پس ناخالصی آن‌ها 0 است و بهره برابر با ناخالصی والد می‌شود؛ یعنی 0.48 برای جینی.
  • سطح 2: چرا ناخالصی فرزندان را بر اساس سهم نمونه‌هایشان وزن‌دهی می‌کنیم؟ پاسخ مورد انتظار: یک فرزند خالص که تنها 1 نمونه دارد نباید ارزشی برابر با یک فرزند ناخالص داشته باشد که باقی داده‌ها را در خود جای داده است.
  • سطح 3: درخت چگونه یک ویژگی پیوسته را به آستانه‌های کاندید تبدیل می‌کند؟ پاسخ مورد انتظار: مقادیر را مرتب می‌کند و نقطه‌ی میانی بین هر جفت همسایه‌ی متمایز را می‌آزماید.
  • سطح 3: چه چیزی مانع ادامه‌ی بازگشت، پیش از رسیدن به وضعیتی می‌شود که هر برگ فقط 1 نمونه داشته باشد؟ پاسخ مورد انتظار: محدودیت‌های پیش‌هرس (Pre-pruning) مانند حداکثر عمق، حداقل تعداد نمونه در هر برگ، یا حداقل بهره؛ یا پس‌هرس (Post-pruning) بعد از رشد کامل درخت.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «جینی برابر است با 0.6 ضرب در 0.4.» این حاصل‌ضرب نصفِ جینی در حالت دوکلاسه است. فرمول اصلی 1 منهای مجموع توان دوم سهم‌هاست که اینجا 0.48 می‌شود.
  • «آنتروپی گرهی با نسبت 6 به 4 برابر با 1 بیت است چون دو کلاس داریم.» 1 بیت حداکثر مقدار ممکن است و فقط وقتی به دست می‌آید که سهم کلاس‌ها برابر باشد. سهم‌های نابرابر مقدار کمتری می‌دهند که در این مثال 0.971 بیت است.
  • «انشعابی را انتخاب کنید که کمترین ناخالصی فرزند را دارد، ناخالصی والد اهمیتی ندارد.» ناخالصی والد برای تمام انشعاب‌های کاندید در آن گره یکسان است، بنابراین رتبه‌بندی (Rank) یکسان خواهد بود؛ اما بهره همان مقداری است که درخت ذخیره می‌کند و به‌عنوان اهمیت ویژگی (Feature importance) گزارش می‌دهد.

کجای دوره آموزش داده می‌شود

در درس درخت‌های تصمیم هر دو معیار برای این گره محاسبه می‌شوند، و در درس نظریه‌ی اطلاعات مفاهیم آنتروپی و آنتروپی شرطی تعریف شده‌اند.