داتا ماينينج · CSC213

الـ Decision Trees: الـ Gini Index والـ Information Gain وإزاي بنختار الـ Splits

داتا ماينينج شروحات ومراجعات

الـ decision tree بيصنف الـ records بسلسلة اختبارات على الـ attributes. في كل node خوارزمية greedy بتختار الاختبار اللي بيقلل الـ impurity أكتر، بالـ Gini index أو الـ entropy.

الـ decision tree فيه root وinternal nodes فيها test condition على attribute وleaves عليها class labels. في الإطار العام لبناء الـ classification model بنستخدم الـ training records لبناء model بعدين نطبقه على الـ test set. بناء الشجرة greedy: في كل node بيختار أحسن split محلي من غير ما يبص قدام، وده سريع بس مش مضمون يطلع الأمثل.

مقاييس الـ impurity: لـ node t بنسب classes p(i): الـ Gini = 1 - مجموع p(i) تربيع، والـ entropy = - مجموع p(i) log2 p(i). لو كل records الـ node t من class واحد الـ Gini = 0 (نقي). في مسألة بـ class-2 باحتمالات p و1 - p الـ Gini أكبر ما يمكن 0.5 لما p = 0.5 ويبقى 0 لما p = 0 أو 1. والـ gain بتاع split = impurity الأب - المتوسط الموزون لـ impurity الأبناء؛ نختار الـ split اللي أعلى gain.

الـ test conditions بتعتمد على نوع الـ attribute. Nominal: multiway split (فرع لكل قيمة) أو binary split بتجميع القيم. Ordinal: تجميعات بتحافظ على الترتيب (متدمجش Small مع Large وتسيب Medium). Continuous: binary split بـ threshold (A < v) أو discretization لفترات.

أهم النقاط

  • Gini = 1 - مجموع p(i)^2؛ الـ node النقي Gini = 0؛ أقصى قيمة في class-2 هي 0.5.
  • Gain = impurity الأب - impurity الأبناء الموزون.
  • Greedy: أحسن split محلي في كل node.
  • الـ ordinal splits لازم تحافظ على الترتيب.
  • الـ continuous بيستخدم thresholds أو discretization.

مثال محلول

node فيه 6 records من class A و4 من B: Gini = 1 - 0.36 - 0.16 = 0.48. split بيدي يسار (4 A و0 B) بـ Gini 0 ويمين (2 A و4 B) بـ Gini = 1 - 1/9 - 4/9 = 0.444. الموزون = 0.6 × 0.444 = 0.267 فالـ gain = 0.48 - 0.267 = 0.213.

أسئلة شائعة

كام الـ Gini لـ node نقي؟

صفر لأن كل الـ records من class واحد.

ليه الـ decision trees بتتسمى greedy؟

لأنها بتختار أحسن split في كل خطوة من غير ما تعتبر الخطوات اللي بعدها.

أسئلة تدريب على الموضوع ده

جرّبها بنفسك، وبعدين افتح التطبيق وشوف الإجابة والشرح.

  1. When designing a test condition for an ordinal attribute (e.g., Shirt Size: Small, Medium, Large, Extra Large), which group split violates the order property?
    • A. {Small, Medium} and {Large, Extra Large}
    • B. Multi-way split using all distinct values
    • C. {Small} and {Medium, Large, Extra Large}
    • D. {Small, Large} and {Medium, Extra Large}
  2. How is the Gain calculated when choosing an attribute test condition to find the best split?
    • A. Gain = M - P
    • B. Gain = P + M
    • C. Gain = P * M
    • D. Gain = P - M (P is impurity before, M is weighted child impurity)
  3. What are the primary ways of handling splitting based on continuous attributes in decision trees?
    • A. Using only multi-way splits with equal frequency bucketing
    • B. Converting continuous attributes directly into class labels
    • C. Discretization (static/dynamic) and Binary Decisions (A < v or A ≥ v)
    • D. Bagging and Boosting only
  4. In the general framework for building a classification model, what is the correct technical distinction between the two core phases?
    • A. Induction is used on the test set to map attribute sets, while Deduction builds the model using the training set.
    • B. Induction evaluates node impurity, whereas Deduction optimizes the Gini gain.
    • C. Induction learns a model from the training set, whereas Deduction applies the learned model to classify records in the test set.
    • D. Induction calculates the class probability distribution, while Deduction discretizes continuous variables.
  5. How can nominal attributes be split when constructing test conditions for decision trees?
    • A. Only through dynamic discretization ranges.
    • B. Strictly through binary splits that preserve strict numeric ordering.
    • C. Either via multi-way splits (using as many partitions as distinct values) or binary splits (dividing values into two subsets).
    • D. Only via multi-way splits based on the exact count of unique records.
  6. What is the defining characteristic of a greedy approach when determining the best split in decision tree induction?
    • A. It evaluates all future tree branches globally before making the first split.
    • B. It selects the split that produces nodes with purer class distributions at the current step without looking ahead.
    • C. It avoids calculating impurity measures to speed up training.
    • D. It prioritizes multi-way splits over binary splits to minimize tree depth.