السَّمْت

أساسيات تعلم الآلة1984تأسيسي10 دقيقة قراءة

أشجار التصنيف والانحدار

Classification and Regression Trees

Breiman, L. · Friedman, J. · Olshen, R. · Stone, C. — Chapman and Hall/CRC

المشكلة

قبل ظهور CART، كان بناء نموذج للتصنيف أو الانحدار يتطلّب إما افتراضات معلمية جامدة كالخطية، أو قواعد خبرة مكتوبة يدوياً. النماذج الخطية لم تكن قادرة على التقاط التفاعلات المعقدة بين السمات، وقواعد أنظمة الخبرة كانت هشّة — بمجرد تغيير المجال تبدأ من الصفر. لم توجد طريقة عامة وتلقائية تتعامل مع والانحدار معاً، وتعالج البيانات المفقودة، وتعمل مع أنواع مختلطة من السمات، وتُنتج قرارات مفهومة للبشر.

الإسهام

CART: خوارزمية موحَّدة تبني أشجار قرار ثنائية للتصنيف والانحدار معاً. في كل تبحث الخوارزمية عن أفضل ثنائي باستعراض جميع السمات وجميع العتبات بحثاً عن أعلى نقاء ممكن ( للتصنيف، وتقليل للانحدار). تنمو الشجرة بأسلوب جشع حتى تصبح نقية، ثم تُشذَّب بأسلوب مع التحقق المتقاطع لإيجاد الحجم المناسب. التقسيمات البديلة تتعامل مع البيانات المفقودة. النتيجة نموذج قابل للتفسير ولا معلمي يلتقط التفاعلات تلقائياً دون حاجة لهندسة السمات.

الأثر

CART هي البذرة التي نبتت منها منظومة كاملة. الغابة العشوائية (2001) تبني مئات من أشجار CART العشوائية وتجمع أصواتها. التعزيز التدرُّجي (1999) يُسلسل أشجار CART صغيرة واحدة تلو الأخرى، كل شجرة تُصحّح أخطاء سابقتها. XGBoost وLightGBM وCatBoost — محرِّكات البيانات الجدولية في الصناعة — كلها أحفاد CART. أثبتت CART أن شجرة قرار واحدة مصمَّمة بعناية يمكنها مضاهاة معرفة الخبراء، وأحفادها اليوم تُشغّل معظم أنظمة تعلّم الآلة الإنتاجية على البيانات المهيكلة.

تخيّل أنك طبيب طوارئ. يصل مريض وعليك أن تقرّر بسرعة: هل تُدخله المستشفى أم تصرفه؟

لن تُجري كل الفحوصات الممكنة. تبدأ بالسؤال الأكثر دلالة: «هل ضغط الدم مرتفع بشكل خطير؟» إن كان نعم انتقل يساراً — واسأل عن ألم الصدر. إن كان لا انتقل يميناً — واسأل عن الحمى. كل إجابة تُضيّق نطاق التشخيص حتى تصل إلى قرار.

هذا بالضبط ما تفعله : مخطط انسيابي من أسئلة ثنائية مُرتَّبة بحيث يأتي السؤال الأكثر فائدة أولاً. وCART هي الخوارزمية التي تبني هذا المخطط تلقائياً من البيانات — دون الحاجة لخبير بشري.

المشكلة: نماذج جامدة أو قواعد هشّة

قبل CART، كان الممارسون أمام خيار صعب:

  • النماذج الخطية (كـ) تفترض أن خطّ مستقيم. لكن البيانات الحقيقية نادراً ما تكون بهذه البساطة — فخطورة حالة مريض قد لا ترتفع إلا حين يكون ضغط الدم والكوليسترول مرتفعَين معاً، وهذا تفاعل لا يلتقطه النموذج الخطي ما لم تُصمَّم يدوياً.

  • أنظمة الخبرة تُرمّز المعرفة التخصصية كقواعد «إذا-فـ» مكتوبة يدوياً. تعمل بكفاءة في نطاقات ضيقة لكنها تنهار حين يتغيّر المجال. وصيانة آلاف القواعد مع تطوّر المعرفة كابوس هندسي.

ما كان ينقص هو أسلوب يكتشف القواعد تلقائياً من البيانات، ويلتقط التفاعلات اللاخطية، ويصلح لـالتصنيف و معاً، ويُنتج مخرجات مفهومة وموثوقة للبشر.

الفكرة: اطرح أفضل سؤال، ثم كرِّر

تبني CART الشجرة من الأعلى إلى الأسفل باستخدام . الفكرة بسيطة: في كل عُقدة، ادرس كل الطرق الممكنة لتقسيم البيانات إلى مجموعتين، واختر التقسيم الذي يجعل المجموعتين أنقى ما يمكن، ثم كرّر العملية على كل مجموعة حتى تحتوي كل على فئة واحدة فقط (أو قيمة تنبؤية واحدة في حالة الانحدار).

تصوّر الأمر كلعبة «عشرين سؤالاً» صمّمها إحصائي: كل سؤال يُختار ليُزيل أكبر قدر من الغموض، وتتفرع الشجرة حتى يقود كل مسار إلى إجابة واثقة.

ثلاثة قرارات محورية تُحدّد سلوك الخوارزمية:

  • كيف نقيس النقاء — ما الذي يجعل تقسيماً أفضل من آخر؟
  • متى نتوقف عن التقسيم — إلى أيّ حدّ ينبغي أن تنمو الشجرة؟
  • كيف نُشذّب — كيف نُقلّم شجرة مُفرطة النمو دون خسارة الدقة؟
افتح في المختبر
شاهد CART وهي تبني الشجرة خطوة بخطوة. انقر «التقسيم التالي» لترى كيف تختار الخوارزمية أفضل سؤال في كل عقدة.
تستيقظ التجربة عند وصولك…

قياس النقاء: شائبة جيني

تخيّل أنك تسحب عنصرين عشوائياً من مجموعة. إن كانت المجموعة نقية (فئة واحدة فقط) فستسحب دائماً عنصرين متماثلين. وإن كانت مختلطة لأقصى حدّ فستسحب غالباً عنصرين مختلفين. شائبة جيني تقيس هذا بالضبط: احتمال أن تُخطئ في تصنيف عنصر مختار عشوائياً لو صنّفته وفق توزيع الفئات في المجموعة.

قيمة جيني = 0 تعني أن العُقدة نقية تماماً — كل العناصر من فئة واحدة. وقيمة 0.5 (لفئتين) تعني أقصى اختلاط — مزيج نصف ونصف. هدف CART عند كل تقسيم هو إيجاد والعتبة اللتين تُقلّلان شائبة جيني أكثر ما يمكن.

لماذا جيني وليس ؟ كلاهما يعمل جيداً في التطبيق، لكن جيني تتجنّب حساب اللوغاريتم فتكون أسرع قليلاً. اختار Breiman جيني كمقياس افتراضي لأنها تُنتج أشجاراً شبه مطابقة لأشجار الإنتروبيا لكن بحسابات أقل.

Gini(t)=1−∑k=1Kpk2Gini(t) = 1 - \sum_{k=1}^{K} p_k^2
شائبة جيني في العقدة t — p_k = نسبة العناصر من الفئة k في هذه العقدة · K = عدد الفئات · حين تهيمن فئة واحدة يكون أحد حدود p_k² كبيراً والباقي صغيراً، فتقترب 1 − Σp_k² من 0 (نقاء). وحين تتوزّع الفئات بالتساوي تكون كل الحدود صغيرة، فترتفع قيمة 1 − Σp_k² (اختلاط).

في أشجار الانحدار يختلف مقياس النقاء. بدل نسب الفئات، تُقلّل CART التباين () داخل كل عُقدة. والقيمة المتوقَّعة في كل ورقة هي ببساطة متوسط جميع عينات التي وصلت إليها.

MSE(t)=1∣t∣∑i∈t(yi−yˉt)2\text{MSE}(t) = \frac{1}{|t|} \sum_{i \in t} (y_i - \bar{y}_t)^2
معيار تقسيم الانحدار — التباين في العقدة t — y_i = القيمة الفعلية للعينة i · ȳ_t = متوسط كل العينات في العقدة t · التقسيم الذي يُنشئ عقدتين فرعيتين بأقل متوسط مربع خطأ مُجمَّع هو الفائز.
افتح في المختبر
اسحب شريط نسبة الفئات لترى كيف تتغير شائبة جيني والإنتروبيا. لاحظ أنهما يتفقان على التقسيم الأفضل — لكن جيني أسرع حسابياً.
تستيقظ التجربة عند وصولك…

البحث الجشع: إيجاد أفضل تقسيم

في كل عُقدة تُجري CART بحثاً شاملاً: لكل سِمة ترتّب القيم، ثم تفحص كل نقطة وسطى بين قيمتين متتاليتين كعتبة محتملة، وتحسب كسب جيني (أو تقليل التباين) لكل منها. التقسيم ذو الكسب الأعلى يفوز.

هذه : تختار أفضل تقسيم محلي في كل خطوة دون استشراف المستقبل. إيجاد الشجرة المثلى عالمياً مسألة NP-صعبة، لذا فالتقسيم الجشع هو الحلّ العملي. ورغم ذلك تعمل أشجار CART بشكل ممتاز لأن البنية التكرارية تسمح للتقسيمات اللاحقة بتصحيح ما فات.

لعُقدة تحتوي nn عيّنة و pp سمة، تبلغ التكلفة O(n⋅p⋅log⁡n)O(n \cdot p \cdot \log n) — الجزء الأكبر يذهب لترتيب كل سمة مرة واحدة ثم مسح القائمة المرتّبة بحثاً عن أفضل عتبة.

ΔGini(s,t)=Gini(t)−∣tL∣∣t∣Gini(tL)−∣tR∣∣t∣Gini(tR)\Delta Gini(s, t) = Gini(t) - \frac{|t_L|}{|t|} Gini(t_L) - \frac{|t_R|}{|t|} Gini(t_R)
كسب جيني — مقدار التحسّن من التقسيم s في العقدة t — t_L و t_R = العقدتان الفرعيتان اليسرى واليمنى بعد التقسيم · |t_L|/|t| = نسبة العينات الذاهبة يساراً · التقسيم الذي يُعظّم ΔGini هو المختار.

التشذيب: أنبت ثم قلِّم

الشجرة المكتملة النمو تحفظ بيانات التدريب حرفياً — كل ورقة نقية لكن الشجرة تعاني من . بعبارة أخرى، تعلّمت الضوضاء بدل الإشارة الحقيقية. تخيّل شجرة مفصّلة لدرجة أنها تخصّص فرعاً مستقلاً لكل مريض في مستشفى: ستتنبأ بنتائجهم بدقة تامة لكنها ستفشل كلياً مع أي مريض جديد.

الحلّ الأنيق في CART هو تشذيب التعقيد-التكلفة. الفكرة: ابنِ أولاً أكبر شجرة ممكنة T0T_0، ثم أوجد سلسلة متداخلة من أشجار أصغر بقصّ أضعف الفروع تدريجياً. كل شجرة مشذَّبة تُضحّي بقليل من دقة التدريب مقابل كثير من البساطة. ثم يختار حجم الشجرة الذي يُعمّم بأفضل شكل على بيانات لم يرها النموذج من قبل.

معيار التعقيد-التكلفة يُوازن بين ملاءمة النموذج وتعقيده بمعامل واحد α\alpha:

Rα(T)=R(T)+α⋅∣T~∣R_\alpha(T) = R(T) + \alpha \cdot |\widetilde{T}|
معيار التعقيد-التكلفة — R(T) = خطأ التدريب للشجرة T · |T̃| = عدد العقد الورقية · α = عقوبة التعقيد. α صغير → شجرة كبيرة (انحياز منخفض، تباين مرتفع). α كبير → شجرة صغيرة (انحياز مرتفع، تباين منخفض). التحقق المتقاطع يجد النقطة المثلى.
افتح في المختبر
اسحب شريط α لتشذيب الشجرة. لاحظ كيف تنخفض دقة التدريب قليلاً بينما تبلغ دقة الاختبار ذروتها عند الحجم المناسب.
تستيقظ التجربة عند وصولك…

التقسيمات البديلة: التعامل مع البيانات المفقودة

البيانات في الواقع فوضوية — مرضى يتغيّبون عن مواعيدهم، ومستشعرات تتعطّل، وحقول تُترك فارغة. أغلب نماذج تلك الحقبة كانت تحذف الصفوف التي تحتوي ببساطة، فتُهدر معلومات ثمينة.

قدّمت CART حلاً بارعاً: . لكل تقسيم رئيسي تبحث CART عن سمات احتياطية تُحاكي نمط التقسيم الرئيسي بدقة. حين تصل عيّنة إلى عُقدة وتكون قيمة السمة الرئيسية مفقودة، تستخدم CART أفضل سمة بديلة — كأن يكون لديك سؤال احتياطي جاهز حين يتعذّر الإجابة عن السؤال الأول.

وهذا الأسلوب يكشف أيضاً ارتباطات خفية: إن كان «الدخل» هو التقسيم الرئيسي و«المستوى التعليمي» أفضل بديل له، فالشجرة تُخبرك أن هاتين السمتين تتحرّكان معاً.

أهمية المتغيرات: أيّ السمات لها تأثير؟

من أبرز الفوائد العملية لـCART مفهوم . لكل سِمة تجمع CART إجمالي كسب جيني (أو تقليل التباين) عبر كل عُقدة استُخدمت فيها تلك السمة كمعيار تقسيم. السمات التي تظهر في المستويات العليا من الشجرة وتُحقّق تحسّناً كبيراً في النقاء تحتلّ أعلى المراتب.

يمنح هذا الممارسين ترتيباً تلقائياً للسمات دون حاجة لخطوة منفصلة. فالطبيب الذي يبني شجرة تشخيصية يرى فوراً أيّ القيم المخبرية أكثر تأثيراً. هذه هي السبب في بقاء CART وأحفادها مهيمنة في الطب والمال وكل مجال يتطلّب تبرير القرارات.

الفكرة ذاتها بالكود

CART: شجرة تصنيف بمقياس جيني، كاملةpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import numpy as np

def gini(y):
    """شائبة جيني: احتمال تصنيف عيّنة عشوائية بشكل خاطئ."""
    classes, counts = np.unique(y, return_counts=True)
    probs = counts / len(y)
    return 1 - np.sum(probs ** 2)

def best_split(X, y):
    """إيجاد السمة والعتبة اللتين تُعظّمان كسب جيني."""
    best_gain, best_feat, best_thresh = -1, None, None
    parent_gini = gini(y)

    for feat in range(X.shape[1]):
        thresholds = np.unique(X[:, feat])
        for t in thresholds:
            left = y[X[:, feat] <= t]
            right = y[X[:, feat] > t]
            if len(left) == 0 or len(right) == 0:
                continue
            # شائبة الأبناء الموزونة
            w_l = len(left) / len(y)
            gain = parent_gini - w_l * gini(left) - (1-w_l) * gini(right)
            if gain > best_gain:
                best_gain, best_feat, best_thresh = gain, feat, t

    return best_feat, best_thresh, best_gain

def build_tree(X, y, depth=0, max_depth=5):
    """بناء شجرة تصنيف CART بشكل تكراري."""
    # ورقة: عقدة نقية أو وصلنا لأقصى عمق
    if len(np.unique(y)) == 1 or depth >= max_depth:
        classes, counts = np.unique(y, return_counts=True)
        return {"leaf": True, "class": classes[np.argmax(counts)]}

    feat, thresh, gain = best_split(X, y)
    if feat is None:
        classes, counts = np.unique(y, return_counts=True)
        return {"leaf": True, "class": classes[np.argmax(counts)]}

    left_mask = X[:, feat] <= thresh
    return {
        "leaf": False,
        "feature": feat,
        "threshold": thresh,
        "left": build_tree(X[left_mask], y[left_mask], depth+1, max_depth),
        "right": build_tree(X[~left_mask], y[~left_mask], depth+1, max_depth),
    }

# هذا جوهر CART.
# التشذيب = ابنِ شجرة كاملة، ثم قلّم الفروع التي يُحسّن حذفها
# دقة التحقق المتقاطع. الشجرة التي تنشرها هي المشذَّبة —
# مضغوطة وقابلة للتفسير وقادرة على التعميم.

لماذا كانت CART مهمة

  1. 1984

    CART — البداية

    نشر Breiman وFriedman وOlshen وStone كتاب أشجار التصنيف والانحدار. أول إطار موحَّد لأشجار القرار الثنائية يجمع بين شائبة جيني وتشذيب التعقيد-التكلفة والتقسيمات البديلة.

  2. 1986

    من ID3 إلى C4.5 (كوينلان)

    طوّر كوينلان C4.5 انطلاقاً من ID3 بإضافة نسبة الكسب والتقسيمات المتعددة ومعالجة السمات المستمرة. تطوّر موازٍ لـCART ساهم في نشر التقسيم القائم على الإنتروبيا.

  3. 1996

    التجميع بالعيّنات (Breiman)

    قدّم Breiman تقنية التجميع بالعيّنات — درّب عدة أشجار على عيّنات فرعية عشوائية من البيانات ثم اجمع تنبؤاتها بالمتوسط. قلّصت التباين بشكل ملحوظ.

  4. 1999

    التعزيز التدرُّجي (Friedman)

    سلسل Friedman أشجار CART صغيرة بشكل متتالٍ، كل شجرة تُلائم الأخطاء المتبقية من سابقتها. أصبح التعزيز التدرُّجي المعيار الذهبي للبيانات الجدولية.

  5. 2001

    الغابة العشوائية (Breiman)

    جمع Breiman بين التجميع بالعيّنات والانتقاء العشوائي للسمات عند كل تقسيم. أصبحت الغابة العشوائية خوارزمية «الخيار الأول» — يصعب التفوق عليها ويستحيل كسرها وضبطها بسيط.

  6. 2016

    XGBoost يسيطر على Kaggle

    أضاف Chen وGuestrin في XGBoost التنظيم وتحسينات على مستوى النظام إلى التعزيز التدرُّجي. فاز بأغلب مسابقات البيانات المهيكلة في Kaggle، وتبعه LightGBM وCatBoost.

  7. 2026

    الأشجار في كل مكان

    لا تزال النماذج التجميعية القائمة على الأشجار هي الخيار الأول للبيانات الجدولية في الصناعة. التشخيص الطبي، والتقييم الائتماني، وكشف الاحتيال، وأنظمة التوصية — حيثما جاءت البيانات في صفوف وأعمدة فإن أحفاد CART هي أول أداة يلجأ إليها الممارسون.

لم يبنِ Breiman مجرّد مصنِّف. بل ابتكر لغة لطرح الأسئلة على البيانات — لغة بديهية لدرجة أن الغابة العشوائية والتعزيز التدرُّجي ليسا سوى لهجتين منها. في كل مرة تتعامل مع محرك توصيات أو تقييم مخاطر طبية أو تنبيه احتيال، فالأرجح أن غابة من أشجار CART تعمل خلف الكواليس.

المرجعBreiman, Friedman, Olshen, Stone. Classification and Regression Trees. Chapman and Hall/CRC, 1984.

مصطلحات هذه الورقة