الانتقال إلى المحتوى
العودة إلى نتائج البحث

استقراء القواعد (RIPPER)

قدّمه
William W. Cohen
السنة
1995
النوع
Supervised rule learning algorithm
العائلة
Rule learning

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

استقراء القواعد، وتحديداً خوارزمية RIPPER (التشذيب التزايدي المتكرر لإنتاج تقليل الأخطاء)، هي طريقة تعلم آلي مُشرف تتعلم مجموعة مُحكمة من قواعد التصنيف بصيغة "إذا-إذن" من بيانات تدريب مُصنفة. قدمها ويليام دبليو كوهين في عام 1995، وتطبق RIPPER استراتيجية "الفصل والتغلب" (separate-and-conquer) مع تقليم الحد الأدنى لطول الوصف (MDL) لتوليد قواعد دقيقة وقابلة للتفسير، مما يجعلها خوارزمية علامة فارقة في مجال تعلم القواعد الاستقرائية.

الفكرة الحدسية وراء الطريقة

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

التاريخ

تعود جذور استقراء القواعد إلى أنظمة التعلم الآلي المبكرة مثل AQ (Michalski, 1969) و CN2 (Clark and Niblett, 1989). عالجت ورقة RIPPER لكوهين عام 1995 عدم الكفاءة الحسابية وميول الإفراط في التخصيص لأسلافها من خلال تقديم التقليم التزايدي والتحسين المعتمد على MDL. قُدمت RIPPER في مؤتمر ICML 1995 وسرعان ما أصبحت خوارزمية قياسية نظرًا لدقتها التنافسية وشفافيتها، ولا تزال مرجعًا قياسيًا في أدبيات تعلم القواعد والكتب المدرسية.

متى تُستخدم

يُعد استقراء القواعد باستخدام RIPPER مناسبًا عندما يكون تفسير النموذج مطلبًا أساسيًا، مثل دعم القرارات السريرية، أو اكتشاف الاحتيال، أو إعدادات الامتثال التنظيمي. تعمل مع الميزات الاسمية والرقمية المختلطة وتتوسع بشكل معقول لعشرات الآلاف من الحالات. تفترض RIPPER أن تسميات التدريب موثوقة بما فيه الكفاية وأن حدود القرار الأساسية يمكن تقريبها بالاقترانات المحاذية للمحاور. إنها أقل ملاءمة لمساحات الميزات المستمرة عالية الأبعاد أو المهام التي تتطلب مخرجات مُعايرة احتمالية؛ في تلك الحالات، قد يُفضل استخدام أشجار الانحدار المعززة (gradient boosted trees) أو الانحدار اللوجستي.

الحدود والاعتبارات

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

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • تنتج قواعد "إذا-إذن" قابلة للقراءة البشرية يمكن لخبراء المجال مراجعتها والتحقق منها
  • التعلم الفعال "بالفصل والتغلب" مع التقليم الموجه بـ MDL يقلل من الإفراط في التخصيص
  • تتعامل مع السمات الاسمية والرقمية دون الحاجة إلى معالجة مسبقة مكثفة
  • وقت تدريب سريع بشكل عام مقارنةً بالطرق المجمعة (ensemble methods) لأحجام مجموعات البيانات المعتدلة

التطبيقات

  • دعم القرارات السريرية واستخلاص قواعد التشخيص الطبي
  • اكتشاف الاحتيال والشذوذ في مراقبة المعاملات المالية
  • تصنيف النصوص باستخدام الميزات المعجمية والهيكلية
  • اكتشاف تسلل الشبكة باستخدام قواعد تنبيه قابلة للتفسير
  • التنبؤ بتوقف العملاء عن التعامل باستخدام قواعد عمل قابلة للتنفيذ

كيف يعمل

كيف يعمل

1

تعالج RIPPER فئة واحدة في كل مرة، مع اعتبار جميع الحالات المتبقية كمجموعة سلبية. تنمو بشكل جشع قاعدة اقترانية عن طريق إضافة الشرط الذي يزيد نسبة الحالات الإيجابية إلى إجمالي الحالات المغطاة بشكل متكرر. بمجرد نموها، يتم الالتزام بالقاعدة وإزالة جميع الحالات التي تغطيها قبل تعلم القاعدة التالية، متبعةً بذلك نموذج "الفصل والتغلب" الكلاسيكي الذي وصفه كوهين (1995).

الصيغة
\text{For each class } c \in \mathcal{C} \text{, grow a rule } R: \text{cond} \Rightarrow c \text{ maximizing } \frac{p}{p+n}
2

يتم تقليم كل قاعدة مرشحة على قسم تحقق (validation partition) باستخدام المقياس (p - n) / (p + n)، حيث يمثل p و n عدد الحالات المغطاة بشكل صحيح وغير صحيح على التوالي. يتم حذف الشروط من ذيل القاعدة إلى الداخل طالما أن التقليم يزيد هذه القيمة، مما يحمي من الإفراط في التخصيص (overfitting) الناتج عن الاقترانات المحددة للغاية التي تتناسب مع مجموعة التدريب.

الصيغة
\text{Prune rule } R \text{ by removing conditions to maximize } v(R, \text{prune set}) = \frac{p - n}{p + n}
3

بعد تعلم جميع القواعد لكل فئة على حدة، تجري RIPPER مرحلة تحسين اختيارية موجهة بمبدأ الحد الأدنى لطول الوصف (MDL). لكل قاعدة في المجموعة النهائية، تنظر الخوارزمية في استبدالها أو مراجعتها وتقبل التغيير فقط إذا قلل من طول الوصف المشترك لمجموعة القواعد والبيانات المصنفة بشكل خاطئ المتبقية، مما يوازن بين الدقة وتعقيد النموذج.

الصيغة
\text{Minimize description length: } DL(\text{ruleset}) + DL(\text{data} \mid \text{ruleset})
4

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

الصيغة
\hat{y} = c_k \text{ where } R_k \text{ is the first rule in the ordered list that fires on instance } \mathbf{x}

الأخطاء الشائعة

  • تطبيق RIPPER على مجموعات بيانات صغيرة بدون بيانات تقليم كافية يؤدي إلى قواعد مُقلمة بشكل مفرط ومنخفضة التغطية
  • تجاهل عدم توازن الفئات يتسبب في امتصاص الفئة الافتراضية للفئة الأقلية، مما يخفي ضعف استدعاء الفئة الأقلية
  • معاملة ترتيب القواعد المتعلمة كسببية بدلاً من تنبؤية يؤدي إلى سوء تفسير في التحليلات الاستكشافية
  • تخطي مرحلة تحسين MDL (المتوفر في بعض التطبيقات) قد يترك قواعد زائدة أو متعارضة في المجموعة النهائية

الأسئلة الشائعة

كيف تختلف RIPPER عن شجرة القرار؟

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

هل يمكن لـ RIPPER التعامل مع مشاكل متعددة الفئات؟

نعم. تمتد RIPPER إلى الإعدادات متعددة الفئات عن طريق تعلم قواعد لكل فئة بالتناوب، مرتبة من الفئة الأندر إلى الأكثر تكرارًا. يتم إزالة الحالات التي تغطيها قواعد الفئات المبكرة قبل تعلم قواعد الفئات اللاحقة. قاعدة افتراضية تعين الفئة الأغلبية لأي حالة لا تغطيها القواعد الصريحة.

ما هو دور مبدأ الحد الأدنى لطول الوصف (MDL) في RIPPER؟

يوفر MDL معيارًا رسميًا لموازنة تعقيد القاعدة مع ملاءمة البيانات. في مرحلة التحسين، تفضل RIPPER مجموعات القواعد التي يكون طول وصفها الإجمالي - الذي يشمل ترميز القواعد والحالات المصنفة بشكل خاطئ - أقصر. هذا يمنع الخوارزمية من الاحتفاظ بقواعد محددة للغاية تحفظ الضوضاء بدلاً من التقاط الأنماط الحقيقية في البيانات.

طرق ذات صلة

المصادر

  1. Cohen, W. W. (1995). Fast effective rule induction. Proceedings of the 12th International Conference on Machine Learning, 115–123.

    افتح مرجع DOI
    تم النسخ.