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

خوارزمية أبْريوري

قدّمه
Agrawal, R. & Srikant, R.
السنة
1994
النوع
Frequent itemset and association rule mining algorithm
العائلة
Machine learning

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

حجم الخط

ماذا تفعل؟

خوارزمية أبْريوري، التي قدمها أغراوال وسريكَانت عام 1994، هي الطريقة الأساسية لاكتشاف مجموعات العناصر المتكررة وقواعد الارتباط في قواعد بيانات المعاملات. تستخدم بحثًا على مستوى المستويات (level-wise) موجهًا بالخاصية المضادة للتزايد (anti-monotone) للدعم (support) لتعداد جميع تركيبات العناصر التي تتواجد معًا فوق عتبة دنيا يحددها المستخدم بكفاءة، ثم تستخلص قواعد شرطية (if-then) قابلة للتفسير من تلك الأنماط.

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

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

التاريخ

إهمال إزالة القواعد غير المفيدة (على سبيل المثال، القواعد التي تتضمن عناصر يتم شراؤها عالميًا مثل بطاقة ولاء المتجر).

متى تُستخدم

استخدم أبْريوري عندما يكون الهدف هو اكتشاف أنماط التواجد المشترك أو العلاقات الشرطية في بيانات المعاملات أو بيانات وجود العناصر الثنائية - تحليل سلة السوق، المشاركة المشتركة لعناصر الاستبيان، التواجد المشترك للتشخيصات الطبية، أو ارتباط المصطلحات النصية. إنها مناسبة لمجموعات البيانات متوسطة الحجم حيث تكون شفافية وقابلية تفسير قواعد المخرجات أولوية. لا تستخدم أبْريوري عندما تكون قاعدة بيانات المعاملات كبيرة جدًا (ملايين الصفوف مع فهارس عناصر واسعة)، حيث أن مسحها المتكرر الكامل لقاعدة البيانات يجعلها بطيئة مقارنة بـ FP-Growth؛ في تلك الحالات يُفضل FP-Growth. كما أنها غير مناسبة للبيانات الرقمية المستمرة بدون تجزئة مسبقة، ولا تقوم بنمذجة الاتجاهية أو السببية.

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

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

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

نقاط القوة

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

التطبيقات

  • قدم راكيش أغراوال وراماكريشنا سريكَانت خوارزمية أبْريوري في VLDB عام 1994، بناءً على صياغة أغراوال وآخرين لمشكلة تعدين قواعد الارتباط عام 1993. يعكس الاسم بصيصها الرئيسي: استخدام المعرفة المسبقة لمجموعات العناصر (k) المتكررة لتقليم المرشحين في المستوى k+1. أصبحت المعيار القياسي الذي تُقاس به جميع خوارزميات مجموعات العناصر المتكررة اللاحقة - بما في ذلك FP-Growth (2000) و Eclat - ولا تزال فصلًا قياسيًا في كتب تعدين البيانات والتعلم الآلي.
  • تحليل سلة السوق: اكتشاف المنتجات التي يتم شراؤها معًا بشكل متكرر لتوجيه تخطيط الأرفف والعروض الترويجية.
  • المعلوماتية الطبية: تحديد الأعراض أو التشخيصات أو وصفات الأدوية المتزامنة في سجلات المرضى.
  • تعدين استخدام الويب: العثور على الصفحات أو الميزات التي يميل المستخدمون إلى زيارتها أو تفعيلها معًا.
  • تحليل الاستبيانات والاستقصاءات: اكتشاف العناصر أو استجابات المقاييس التي يتم الموافقة عليها بشكل منهجي.
  • تمهيد أنظمة التوصية: إنشاء ارتباطات عناصر مرشحة قبل نشر الترشيح التعاوني.

كيف يعمل

كيف يعمل

1

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

2

تجري الخوارزمية مسحًا كاملاً لقاعدة بيانات المعاملات لعد عدد مرات ظهور كل عنصر فردي. يتم الاحتفاظ فقط بالعناصر التي يلبي دعمها الحد الأدنى للدعم أو يتجاوزه؛ يتم التخلص من الباقي. تشكل هذه المجموعة من العناصر الفردية المتكررة المستوى الأول من المرشحين.

الصيغة
\text{support}(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}
3

يتم ضم مجموعات العناصر المتكررة الموجودة في المستوى k زوجيًا لتشكيل مجموعات عناصر مرشحة بحجم k+1. يتم ضم الأزواج التي تشترك في نفس العناصر k-1 الأولى فقط، وهي قاعدة تحافظ على مجموعة المرشحين مدمجة. يقوم مسح جديد لقاعدة البيانات بعد دعم كل مرشح.

4

قبل العد، يتم فحص كل مرشح بحجم k+1 مقابل جميع مجموعاته الفرعية بحجم (k). إذا لم تكن أي مجموعة فرعية متكررة في المستوى السابق، يتم تقليم المرشح فورًا دون قراءة البيانات، مستغلًا الخاصية المضادة للتزايد لتقليل الحساب. الناجون من خطوة التقليم هذه يشكلون المستوى التالي من مجموعات العناصر المتكررة.

5

من كل مجموعة عناصر متكررة بحجم اثنين أو أكثر، يتم إنشاء جميع القواعد الشرطية الممكنة عن طريق تقسيم العناصر إلى مقدم (antecedent) وتالي (consequent). يتم تقييم كل قاعدة بناءً على الثقة - نسبة المعاملات التي تحتوي على المقدم والتي تحتوي أيضًا على التالي. يتم التخلص من القواعد التي تقل عن الحد الأدنى للثقة.

الصيغة
\text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)}
6

يتم ترتيب القواعد الناجية حسب الرفع (lift)، الذي يقارن الثقة المرصودة مع التردد الأساسي للتالي. يشير الرفع الذي يزيد عن 1 إلى أن المقدم والتالي يتواجدان معًا أكثر من المصادفة؛ الرفع القريب من 1 يشير إلى الاستقلال؛ الرفع الأقل من 1 يشير إلى ارتباط سلبي. القواعد ذات الرفع الأعلى هي الاكتشافات الأكثر قابلية للتنفيذ.

الصيغة
\text{lift}(X \Rightarrow Y) = \frac{\text{confidence}(X \Rightarrow Y)}{\text{support}(Y)}

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

  • تشغيل أبْريوري مباشرة في MethodMind - تحميل مجموعة بيانات المعاملات الخاصة بك، وتعيين عتبات الدعم والثقة، وتلقي قواعد الارتباط المصنفة مع الدعم والثقة والرفع، بالإضافة إلى تصور شبكي لأقوى اتصالات العناصر.
  • تحديد الحد الأدنى للدعم منخفضًا جدًا والغرق في آلاف القواعد منخفضة الجودة دون تصفية بالرفع.
  • تفسير الثقة العالية على أنها سببية بدلاً من تواجد مشترك - قاعدة ذات ثقة عالية ولكن رفع قريب من 1 تكون تافهة.
  • تطبيق أبْريوري على الميزات المستمرة دون تجزئتها أولاً، مما يؤدي إلى تضخيم مساحة العناصر وتدهور النتائج.
  • الإبلاغ عن القواعد دون التحقق مما إذا كانت أحجام عينات مجموعات العناصر كبيرة بما يكفي للوثوق بتقديرات الدعم.

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

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

ما هو الفرق بين الدعم والثقة والرفع؟

الدعم هو نسبة جميع المعاملات التي تحتوي على مجموعة العناصر - يقيس الانتشار. الثقة هي الاحتمال الشرطي لظهور التالي بالنظر إلى المقدم - تقيس موثوقية القاعدة. الرفع هو نسبة الثقة المرصودة إلى التردد الأساسي للتالي؛ الرفع الذي يزيد عن 1 يظهر ارتباطًا إيجابيًا حقيقيًا بدلاً من مصادفة مدفوعة بشعبية العنصر.

متى يجب أن أختار FP-Growth بدلاً من أبْريوري؟

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

كيف أختار الحد الأدنى للدعم والثقة؟

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

هل يمكن لأبْريوري التعامل مع البيانات الرقمية أو المستمرة؟

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

هل أبْريوري يعني السببية بين العناصر؟

طرق ذات صلة

المصادر

  1. Agrawal, R. & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th International Conference on Very Large Data Bases (VLDB), 487–499.

    افتح مرجع المنشور
    تم النسخ.
  2. Apriori algorithm. Wikipedia.

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