السَّمْت

أساسيات تعلم الآلة1993تأسيسي9 دقيقة قراءة

C4.5: برامج للتعلّم الآلي

C4.5: Programs for Machine Learning

Quinlan, J. R. — Morgan Kaufmann

المشكلة

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

الإسهام

جاء C4.5 بأربع إضافات جوهرية فوق ID3: أولاً، استبدل كسب المعلومات لتفادي الانحياز نحو السمات كثيرة القيم. ثانياً، أصبح قادراً على التعامل مع السمات المستمرة بإيجاد أفضل عتبة تقسيم. ثالثاً، عالج القيم المفقودة بتوزيع كل حالة ناقصة كَسرياً على الفروع. رابعاً، أضاف تشذيباً يستند إلى تقدير الخطأ ويقصّ الفروع التي لا تُعمّم جيداً. وإلى جانب ذلك، يستطيع C4.5 تحويل الشجرة إلى مجموعة قواعد «إذا-فإنّ» أكثر إيجازاً وأسهل تفسيراً، مستعيناً بمبدأ الحد الأدنى لطول الوصف لاختيار أفضل مجموعة فرعية من القواعد.

الأثر

ظلّ C4.5 خوارزمية أشجار القرار الأوسع انتشاراً في التعلّم الآلي لأكثر من عقد، واختِير الخوارزمية الأولى في استطلاع 2008 لأبرز أساليب التنقيب في البيانات. أفكاره الأساسية — نسبة الكسب، والتشذيب بتقدير الخطأ، واستخراج القواعد — تحوّلت إلى مكوّنات معيارية في كل أسلوب شجري جاء بعده. الغابات العشوائية وأُطر تعزيز التدرّج مثل XGBoost وLightGBM كلها تعود جذورها إلى سلالة أشجار القرار التي أنضجها C4.5 وجعلها عملية.

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

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

من ID3 إلى C4.5: إصلاح أربعة نقاط ضعف

الفكرة الأساسية التي طرحتها خوارزمية ID3 بسيطة وقوية: في كل خطوة، اختر السؤال الذي يُقلّل أكبر قدر من الغموض حول الفئة المستهدفة — وهذا ما نسمّيه . لكن ID3 كانت تعاني من أربع نقاط ضعف جوهرية، وجاء C4.5 ليعالجها واحدة تلو الأخرى.

افتح في المختبر
انقر على كل قيد لترى كيف حلّه C4.5.
تستيقظ التجربة عند وصولك…

الأساس: الإنتروبيا وكسب المعلومات

قبل أن نستعرض ما أضافه C4.5، لا بد من فهم الآلية الأساسية التي يرتكز عليها. تقيس درجة «الفوضى» في مجموعة من الأمثلة. تخيّل كيساً مليئاً بكرات حمراء فقط — لا مفاجأة أبداً عند السحب، فالإنتروبيا صفر. أما كيس فيه نصف كراته حمراء ونصفها زرقاء، فأنت لا تعرف ماذا ستسحب — الإنتروبيا في أعلى مستوياتها.

كسب المعلومات يقيس كم تَقِلّ هذه الفوضى حين نطرح سؤالاً معيّناً. إذا سألنا «هل الجو مشمس؟» وانقسمت الأمثلة إلى مجموعات نقية تقريباً، فهذا سؤال ممتاز وكسبه مرتفع. يرث C4.5 هذا المبدأ من ID3، لكنه يصحّح عيباً دقيقاً في طريقة ترتيب الأسئلة.

H(S)=−∑c=1Cpclog⁡2pcH(S) = -\sum_{c=1}^{C} p_c \log_2 p_c
الإنتروبيا — مقدار المفاجأة المتبقية في المجموعة S — p_c هي نسبة الأمثلة المنتمية إلى الفئة c. إذا كانت كل الأمثلة من فئة واحدة فالإنتروبيا = 0، أي يقين تام. وكلما تساوى توزيع الفئات ارتفعت الإنتروبيا وبلغت حدّها الأقصى عند التساوي الكامل.
Gain(S,A)=H(S)−∑v∈Values(A)∣Sv∣∣S∣H(Sv)Gain(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)
كسب المعلومات — كم من الإنتروبيا تُزيله السمة A؟ — حين نُقسّم المجموعة S وفق السمة A، تحصل كل مجموعة فرعية Sᵥ على إنتروبيا خاصة بها. نحسب المتوسط الموزون لهذه الإنتروبيات ونطرحه من الإنتروبيا الأصلية. كلما ارتفع الكسب دلّ ذلك على أنّ السمة A سؤال أفضل لاختياره.
افتح في المختبر
اسحب المنزلق لتغيير نسبة الفئات وشاهد تغيّر الإنتروبيا.
تستيقظ التجربة عند وصولك…

المشكلة الأولى: نسبة الكسب تصحّح انحياز كثرة القيم

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

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

GainRatio(S,A)=Gain(S,A)SplitInfo(S,A)GainRatio(S, A) = \frac{Gain(S, A)}{SplitInfo(S, A)}
نسبة الكسب — كسب المعلومات مُقيَّساً بمعلومات التقسيم — SplitInfo(S,A) = −Σ (|Sᵥ|/|S|) log₂(|Sᵥ|/|S|) — وهي إنتروبيا التقسيم ذاته. كلما زادت معلومات التقسيم — أي كثرت الفروع الصغيرة — انخفضت نسبة الكسب الناتجة.
افتح في المختبر
قارن كيف يرتّب كسب المعلومات ونسبة الكسب السمات ذاتها.
تستيقظ التجربة عند وصولك…

المشكلة الثانية: التقسيم على السمات المستمرة

ID3 لا تعرف إلا السمات الفئوية — مثل «اللون = أحمر / أزرق / أخضر». لكن في الواقع معظم البيانات تحتوي على قياسات رقمية كدرجة الحرارة وضغط الدم والعمر. الحل في C4.5 هو تحويل أي سمة مستمرة إلى سؤال ثنائي بسيط: «هل درجة الحرارة ≤ 28.5؟»

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

افتح في المختبر
اسحب خط العتبة لإيجاد أفضل نقطة تقسيم للسمة المستمرة.
تستيقظ التجربة عند وصولك…

المشكلة الثالثة: التعامل مع القيم المفقودة

في الواقع، البيانات دائماً ناقصة. تحليل دم لم يصل بعد، أو مشارك في استبيان تخطّى سؤالاً. ID3 لم تكن تعرف ماذا تفعل في هذه الحالة — كانت تتوقف ببساطة أمام أي سجل ناقص.

C4.5 يتعامل مع القيم المفقودة بطريقة ذكية: حين تكون قيمة سمةٍ ما مفقودة، يُوزَّع المثال كَسرياً على جميع الفروع بحسب نسب الأمثلة المعروفة. مثلاً: إذا كان 60% من الأمثلة المعروفة للسمة A تذهب يساراً و40% يميناً، فإن المثال الناقص يُرسَل كنسخة بوزن 0.6 إلى اليسار ونسخة بوزن 0.4 إلى اليمين. بهذا يُساهم المثال في كلا الجانبين بدلاً من إهماله أو تخمين قيمته. الفكرة أشبه بتصويت موزون — المثال الناقص يُصوّت بما تُرجّحه البيانات المتاحة.

المشكلة الرابعة: تشذيب الأشجار المُفرطة التخصيص

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

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

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

افتح في المختبر
اضغط «شذِّب» لمشاهدة التشذيب يبسّط الشجرة خطوة بخطوة.
تستيقظ التجربة عند وصولك…

من الأشجار إلى القواعد: أكثر إيجازاً وأسهل تفسيراً

كل مسار من جذر الشجرة إلى ورقتها هو في حقيقته قاعدة «إذا-فإنّ»: «إذا كان الطقس مشمساً والرطوبة ≤ 75 → العب». ما يفعله C4.5 هو تحويل الشجرة كاملةً إلى قواعد من هذا النوع، ثم تحسينها في ثلاث مراحل:

المرحلة الأولى — تبسيط كل قاعدة. جرّب حذف الشروط واحداً تلو الآخر. إذا لم يزد حذف شرطٍ ما الخطأَ المُقدَّر، احذفه. النتيجة قاعدة أقصر وأعمّ.

المرحلة الثانية — التجميع بحسب الفئة. اجمع القواعد التي تُعطي الفئة نفسها، ثم استخدم مبدأ الحد الأدنى لطول الوصف (MDL) لاستبقاء أصغر مجموعة كافية — وتخلّص من القواعد المكرّرة.

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

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

افتح في المختبر
شاهد شجرة قرار تتحول إلى قواعد مشذَّبة — لاحظ كيف تُحذف الشروط.
تستيقظ التجربة عند وصولك…

خوارزمية C4.5 خطوة بخطوة

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

الخوارزمية الأساسية لـ C4.5 (مبسّطة)python

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

import numpy as np
from collections import Counter

def entropy(y, weights=None):
    """الإنتروبيا الموزونة لتسميات الفئات."""
    if weights is None:
        weights = np.ones(len(y))
    total = weights.sum()
    if total == 0:
        return 0.0
    ent = 0.0
    for c in set(y):
        mask = (y == c)
        p = weights[mask].sum() / total
        if p > 0:
            ent -= p * np.log2(p)
    return ent

def gain_ratio(X, y, attr, weights):
    """نسبة الكسب في C4.5 = كسب المعلومات / معلومات التقسيم."""
    total = weights.sum()
    base_ent = entropy(y, weights)
    gain = base_ent
    split_info = 0.0

    for val in set(X[:, attr]):
        mask = (X[:, attr] == val)
        w_sub = weights[mask]
        frac = w_sub.sum() / total
        gain -= frac * entropy(y[mask], w_sub)
        if frac > 0:
            split_info -= frac * np.log2(frac)

    if split_info == 0:
        return 0.0
    return gain / split_info        # صيغة C4.5 الجوهرية

def build_tree(X, y, weights, attrs):
    """بناء شجرة C4.5 تكرارياً (نسخة مبسّطة)."""
    # الحالات الأساسية
    if len(set(y)) == 1:
        return {'leaf': y[0]}
    if len(attrs) == 0:
        return {'leaf': Counter(y).most_common(1)[0][0]}

    # اختر أفضل سمة حسب نسبة الكسب
    best = max(attrs, key=lambda a: gain_ratio(X, y, a, weights))
    tree = {'attr': best, 'children': {}}

    for val in set(X[:, best]):
        mask = (X[:, best] == val)
        remaining = [a for a in attrs if a != best]
        tree['children'][val] = build_tree(
            X[mask], y[mask], weights[mask], remaining
        )
    return tree

# بعد البناء، يشذّب C4.5 من الأسفل إلى الأعلى
# مستخدماً تقديرات خطأ تشاؤمية (الحد الأعلى لفترة الثقة).

مراحل عمل C4.5 الكاملة

افتح في المختبر
انقر على كل مرحلة لترى ما يحدث فيها.
تستيقظ التجربة عند وصولك…

لماذا غيَّر C4.5 مسار التعلّم الآلي

  1. 1986

    ID3

    خوارزمية كوينلان الأولى. تعمل على السمات الفئوية فقط، بلا تشذيب ولا معالجة للقيم المفقودة. أدخلت معيار كسب المعلومات لاختيار أفضل سمة.

  2. 1993

    C4.5

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

  3. 1998

    C5.0 / See5

    الإصدار التجاري الذي خَلَف C4.5. أسرع وأخف في استهلاك الذاكرة ويدعم التعزيز. تفاصيل الخوارزمية لم تُنشر وبقيت ملكية خاصة.

  4. 2001

    الغابات العشوائية

    دمج بريمان عدداً كبيراً من أشجار القرار باستخدام التكييس وعشوائية السمات. كل شجرة تنتمي لسلالة C4.5، لكن قوة التجميع تتفوق على التشذيب وحده في مقاومة الإفراط في التخصيص.

  5. 2016

    XGBoost / LightGBM

    أُطر تعزيز التدرّج التي تبني الأشجار بشكل متتابع، بحيث تُصحّح كل شجرة أخطاء سابقتها. سيطرت على مسابقات Kaggle والتطبيقات الصناعية.

ما فعله C4.5 يتجاوز بناء أشجار أفضل — فقد أسّس المنهجية الكاملة لبناء القابلة للتفسير وتشذيبها وتقييمها. الغابات العشوائية التي نستخدمها اليوم ما هي إلا تجميعات من أشجار، كل شجرة منها تعود في أصلها عبر C4.5 إلى ID3.

المرجعQuinlan, J. R.. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.

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