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

استقراء أشجار القرار

Induction of Decision Trees

Quinlan, J. R. — Machine Learning

المشكلة

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

الإسهام

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

الأثر

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

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

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

ما هي شجرة القرار؟

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

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

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

افتح في المختبر

اضغط «خطوة بناء» لتشاهد ID3 وهي تنمّي الشجرة عقدةً تلو الأخرى، مختارةً في كل مرة السمة ذات أعلى كسب معلومات.

تستيقظ التجربة عند وصولك…

الإنتروبيا: قياس الغموض

قبل أن نختار السمة «الأفضل»، نحتاج أداة تقيس مقدار الفوضى في مجموعة الأمثلة — أي مدى اختلاط الفئات فيها. هنا يستعين ID3 بمفهوم من .

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

H(S) = -\sum_{i=1}^{c} p_i \log_2 p_i

إنتروبيا شانون لمجموعة S — p_i = نسبة الأمثلة في الفئة i · c = عدد الفئات · H = 0 حين تنتمي كل الأمثلة لفئة واحدة (نقاء تام) · H = 1 بت لفئتين متساويتين (أقصى غموض)

يمكنك التفكير في الإنتروبيا كـمقياس للمفاجأة. حين تعرف النتيجة سلفاً، لا مفاجأة — القيمة صفر. وحين تتساوى كل الاحتمالات، تبلغ المفاجأة ذروتها. ما تحاول ID3 فعله عند كل عقدة هو طرح السؤال الذي يُنزل هذه المفاجأة أقرب ما يمكن إلى الصفر.

افتح في المختبر

اسحب المنزلق لتغيير نسبة الفئات وراقب الإنتروبيا ترتفع وتنخفض.

تستيقظ التجربة عند وصولك…

كسب المعلومات: اختيار أفضل تقسيم

الآن صار لدينا طريقة لقياس الفوضى. السؤال التالي: أيّ سمة تُقلّل هذه الفوضى أكثر من غيرها؟ هنا يأتي دور : وهو ببساطة الفرق بين الإنتروبيا قبل التقسيم وبعده.

لنأخذ مثالاً عملياً: 14 عيّنة لمباريات تنس — 9 منها «العب» و5 «لا تلعب». الإنتروبيا الكلية نحو 0.94 بت. لو قسّمنا على سمة «الطقس» (مشمس / غائم / ممطر)، يصبح المتوسط الموزون لإنتروبيا المجموعات الثلاث 0.69 بت تقريباً. الفرق 0.94 − 0.69 = 0.25 بت هو كسب المعلومات لهذه السمة. تحسب ID3 هذا الكسب لكل سمة وتختار صاحبة الكسب الأعلى.

Gain(S, A) = H(S) - \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)

كسب المعلومات للسمة A على المجموعة S — H(S) = الإنتروبيا قبل التقسيم · S_v = المجموعة الجزئية حيث قيمة السمة A تساوي v · المجموع الموزون يراعي أحجام المجموعات الجزئية · كسب أعلى = سمة أكثر فائدة

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

افتح في المختبر

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

تستيقظ التجربة عند وصولك…

خوارزمية ID3 خطوة بخطوة

الخوارزمية نفسها أنيقة في بساطتها، وتعمل بشكل تعاودي:

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

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

افتح في المختبر

تابع خوارزمية ID3 الكاملة خطوة بخطوة: احسب الأكساب، واختر أفضل سمة، وقسّم، وكرّر.

تستيقظ التجربة عند وصولك…

تقنية النافذة: التوسّع لمجموعات البيانات الكبيرة

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

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

التعامل مع الواقع: الضوضاء والقيم المفقودة

في الواقع، البيانات نادراً ما تكون نظيفة. مشكلتان رئيسيتان تواجهان أشجار القرار:

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

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

افتح في المختبر

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

تستيقظ التجربة عند وصولك…

نقطة ضعف: الانحياز نحو السمات كثيرة القيم

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

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

GainRatio(S, A) = \frac{Gain(S, A)}{SplitInfo(S, A)}

نسبة الكسب — تصحيح C4.5 لكسب المعلومات — معلومات التقسيم تقيس إنتروبيا السمة ذاتها (مدى توزّع الأمثلة بالتساوي بين قيمها). القسمة عليها تُعاقب التقسيمات كثيرة الفروع.

الفكرة ذاتها في شيفرة برمجية

نواة ID3 — الإنتروبيا وكسب المعلومات وبناء الشجرة التكراريpython

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

import math
from collections import Counter

def entropy(labels):
    """H(S): إنتروبيا شانون لقائمة من تصنيفات الفئات."""
    n = len(labels)
    counts = Counter(labels)
    return -sum((c/n) * math.log2(c/n) for c in counts.values())

def info_gain(data, attr_index, label_index):
    """Gain(S, A): مقدار انخفاض الإنتروبيا عند التقسيم على السمة A."""
    total = len(data)
    h_before = entropy([row[label_index] for row in data])

    # تجميع الصفوف حسب قيمة السمة
    splits = {}
    for row in data:
        splits.setdefault(row[attr_index], []).append(row)

    # الإنتروبيا الموزونة بعد التقسيم
    h_after = sum(
        (len(subset) / total) * entropy([r[label_index] for r in subset])
        for subset in splits.values()
    )
    return h_before - h_after

def id3(data, attrs, label_index):
    """بناء شجرة قرار بشكل تكراري."""
    labels = [row[label_index] for row in data]

    # كل الأمثلة من فئة واحدة؟ ← ورقة
    if len(set(labels)) == 1:
        return labels[0]

    # لم تتبقَّ سمات؟ ← فئة الأغلبية
    if not attrs:
        return Counter(labels).most_common(1)[0][0]

    # اختيار السمة ذات أعلى كسب معلومات
    gains = {a: info_gain(data, a, label_index) for a in attrs}
    best = max(gains, key=gains.get)

    tree = {best: {}}
    remaining = [a for a in attrs if a != best]

    for val in set(row[best] for row in data):
        subset = [row for row in data if row[best] == val]
        tree[best][val] = id3(subset, remaining, label_index)

    return tree

# هذا كل ما في ID3. الباقي هو اختيار بيانات جيدة.

لماذا كان هذا مهمّاً

1966
CLS (نظام تعلّم المفاهيم)
قدّم هَنت نظام CLS لبناء الأشجار من الجذر نزولاً انطلاقاً من أمثلة تدريبية، مع اختيار السمات وفق معيار الكلفة. يُعدّ السلف المباشر لـ ID3.
1979
ID3 المبكّر
طبّق كوينلان النسخة الأولى من ID3 على تصنيف نهايات الشطرنج، مُثبتاً أن التقسيم القائم على نظرية المعلومات قادر على اكتشاف قواعد معقدة تلقائياً.
1986
الورقة البحثية — استقراء أشجار القرار
نشر كوينلان الوصف النهائي لـ ID3 مع توسعات للتعامل مع الضوضاء والبيانات الناقصة، في العدد الأول من مجلة Machine Learning.
1984
CART (أشجار التصنيف والانحدار)
طوّر بريمان وزملاؤه CART بشكل مستقل، باستخدام معيار جيني بدلاً من الإنتروبيا، وأضافوا آلية التقليم بموازنة الكلفة والتعقيد. مسار تطوّر موازٍ لـ ID3.
1993
C4.5
خليفة ID3 من كوينلان — يتعامل مع السمات المتصلة، ويستخدم نسبة الكسب، ويُضيف التقليم البَعدي. أصبح من أكثر الخوارزميات استشهاداً في التعلّم الآلي.
2001
الغابات العشوائية
جمع بريمان عدداً كبيراً من أشجار القرار في نموذج تجميعي واحد، كل شجرة تُدرَّب على عيّنة عشوائية من السمات والبيانات. أشجار القرار تحوّلت إلى لبنات لبناء نماذج أقوى.
2016
XGBoost يهيمن على Kaggle
أشجار تعزيز التدرّج، المتحدّرة من سلالة ID3، أصبحت الخوارزمية الفائزة في غالبية مسابقات البيانات الجدولية، مؤكّدةً القوة المستمرة لأشجار القرار.

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

المرجعQuinlan, J. R.. Induction of Decision Trees. Machine Learning, 1986.

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