خوارزمية C4.5

C4.5 هي خوارزمية تُستخدم لإنشاء شجرة قرار ، وقد طوّرها روس كوينلان . ^{[ 1 ]} تُعدّ C4.5 امتدادًا لخوارزمية ID3 السابقة لكوينلان . يمكن استخدام أشجار القرار التي تُنشئها C4.5 في التصنيف، ولهذا السبب، يُشار إلى C4.5 غالبًا باسم المصنّف الإحصائي .

في عام 2011، وصف مطورو برنامج Weka للتعلم الآلي خوارزمية C4.5 بأنها "برنامج رائد في مجال أشجار القرار، وربما تكون الأداة الأساسية في التعلم الآلي الأكثر استخدامًا على نطاق واسع في التطبيقات العملية حتى الآن". ^{[ 2 ]} وقد اكتسبت هذه الخوارزمية شهرة واسعة بعد أن احتلت المرتبة الأولى في قائمة أفضل 10 خوارزميات في مجال استخراج البيانات، وهي ورقة بحثية بارزة نشرتها Springer ضمن سلسلة محاضرات علوم الحاسوب (LNCS) عام 2008. ^{[ 3 ]}

يبني C4.5 أشجار القرار من مجموعة بيانات تدريبية بنفس طريقة ID3 ، باستخدام مفهوم إنتروبيا المعلومات . بيانات التدريب عبارة عن مجموعة${\displaystyle S={s_{1},s_{2},...}}$من العينات المصنفة مسبقًا. كل عينة${\displaystyle s_{i}}$يتكون من متجه ذي أبعاد p${\displaystyle (x_{1,i},x_{2,i},...,x_{p,i})}$، حيث${\displaystyle x_{j}}$تمثل قيم السمات أو خصائص العينة، بالإضافة إلى الفئة التي تنتمي إليها${\displaystyle s_{i}}$الشلالات.

في كل عقدة من الشجرة، يختار خوارزمية C4.5 السمة التي تُقسّم مجموعة العينات إلى مجموعات فرعية غنية بفئة معينة. معيار التقسيم هو كسب المعلومات المُعَيَّر (الفرق في الإنتروبيا). تُختار السمة ذات أعلى كسب معلومات مُعَيَّر لاتخاذ القرار. ثم تُكرر خوارزمية C4.5 العملية على القوائم الفرعية المُقسَّمة .

تحتوي هذه الخوارزمية على عدد قليل من الحالات الأساسية .

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

أدخلت C4.5 عدداً من التحسينات على ID3. بعض هذه التحسينات هي:

• معالجة السمات المتصلة والمنفصلة: لمعالجة السمات المتصلة، يقوم C4.5 بإنشاء عتبة ثم يقسم القائمة إلى تلك التي تكون قيمة سماتها أعلى من العتبة وتلك التي تكون قيمتها أقل من أو تساويها. ^{[ 5 ]}
• معالجة بيانات التدريب ذات القيم المفقودة للسمات: يسمح C4.5 بتحديد قيم السمات على أنها مفقودة. ببساطة، لا تُستخدم قيم السمات المفقودة في حسابات الربح والإنتروبيا.
• التعامل مع السمات ذات التكاليف المختلفة.
• تقليم الأشجار بعد إنشائها: يعود C4.5 إلى الشجرة بمجرد إنشائها ويحاول إزالة الفروع التي لا تساعد عن طريق استبدالها بعقد الأوراق.

قام كوينلان بتطوير برنامجي C5.0 وSee5 (C5.0 لأنظمة يونكس/لينكس، وSee5 لأنظمة ويندوز) اللذين يسوّقهما تجاريًا. يقدم C5.0 عددًا من التحسينات على C4.5، منها: ^{[ 6 ] [ 7 ]}

• السرعة - C5.0 أسرع بكثير من C4.5 (بمقدار عدة مراتب)
• استخدام الذاكرة - يتميز الإصدار C5.0 بكفاءة أعلى في استخدام الذاكرة مقارنةً بالإصدار C4.5
• أشجار القرار الأصغر - يحقق الإصدار C5.0 نتائج مماثلة للإصدار C4.5 مع أشجار قرار أصغر بكثير.
• دعم التعزيز - يعمل التعزيز على تحسين الأشجار ومنحها دقة أكبر.
• الترجيح - يسمح لك الإصدار C5.0 بترجيح الحالات المختلفة وأنواع التصنيف الخاطئ.
• التصفية - خيار C5.0 يقوم تلقائيًا بتصفية السمات لإزالة تلك التي قد تكون غير مفيدة.

يتوفر مصدر إصدار أحادي الخيوط من C5.0 لنظام Linux بموجب رخصة جنو العمومية العامة (GPL).

• خوارزمية ID3
• تعديل C4.5 لتوليد قواعد زمنية وسببية

• النسخة الأصلية موجودة على الصفحة الرئيسية لروس كوينلان: http://www.rulequest.com/Personal/
• See5 و C5.0