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

التنقيب عن قواعد الارتباط (Apriori)

قدّمه
Rakesh Agrawal & Ramakrishnan Srikant
السنة
1994
النوع
Unsupervised pattern discovery algorithm
العائلة
Pattern mining

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

حجم الخط

ماذا تفعل؟

التنقيب عن قواعد الارتباط هو تقنية تنقيب بيانات غير خاضعة للإشراف تكتشف أنماط التواجد المشترك بين العناصر في مجموعات بيانات المعاملات. تم تقديمه رسميًا بواسطة أغراوال، إميليانسكي، وسوامي في عام 1993، وتم تحسينه بخوارزمية Apriori الرائدة بواسطة أغراوال وسريكاند في عام 1994، وهو يحدد قواعد على شكل X ⇒ Y — مما يعني أن المعاملات التي تحتوي على مجموعة العناصر X تميل أيضًا إلى احتواء مجموعة العناصر Y — ويتم قياسها بالدعم والثقة والرفع.

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

تخيل سجل إيصالات سوبر ماركت: إذا كان الآلاف من العملاء الذين يشترون الخبز والزبدة يشترون أيضًا الحليب، فإن هذا النمط يستحق الاهتمام. تعمل تقنية التنقيب عن قواعد الارتباط مثل أمين مكتبة دقيق يمشط كل إيصال، ويحسب عدد مرات ظهور مجموعات العناصر معًا، ويكشف عن المجموعات التي تتجاوز الحد الأدنى للتكرار. بمجرد العثور على المجموعات المتكررة، تسأل الخوارزمية: بالنظر إلى أن لديك بالفعل هذه العناصر، ما مدى موثوقية ذلك في التنبؤ بالعنصر التالي؟ هذا المنطق المكون من مرحلتين (التكرار ثم الثقة) هو جوهر Apriori.

التاريخ

حددت الورقة الأساسية لأغراوال، إميليانسكي، وسوامي (1993) مشكلة قواعد الارتباط في سياق بيانات معاملات السوبر ماركت. قدمت ورقة أغراوال وسريكاند لعام 1994 في VLDB خوارزمية Apriori واستراتيجية التقليم الفعالة الخاصة بها، مما جعل التنقيب على نطاق واسع عمليًا. أنتجت الأعمال اللاحقة FP-Growth (هان وآخرون، 2000)، التي تتجنب توليد المرشحين تمامًا، و ECLAT، التي تنقب في تنسيق بيانات عمودي — مما أسس عائلة خوارزمية غنية أصبحت الآن مركزية لمناهج تنقيب البيانات.

متى تُستخدم

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

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

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

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

نقاط القوة

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

التطبيقات

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

كيف يعمل

كيف يعمل

1

تقوم الخوارزمية بفحص قاعدة بيانات المعاملات D لحساب عدد مرات ظهور كل مجموعة عناصر X. يتم الإعلان عن مجموعة عناصر بأنها متكررة — ووضعها في L_k — فقط عندما يلبي دعمها (نسبة المعاملات التي تحتوي عليها) الحد الأدنى لدعم σ_min المحدد من قبل المستخدم أو يتجاوزه. تبدأ العملية بالعناصر الفردية (k=1) وتبني مجموعات مرشحة أكبر بشكل تكراري.

الصيغة
L_k = \{ X \subseteq I \mid |X| = k,\; \text{support}(X) = \frac{|\{t \in D : X \subseteq t\}|}{|D|} \geq \sigma_{\min} \}
2

تنص خاصية عدم التزايد للدعم على أن أي مجموعة فرعية من مجموعة عناصر متكررة يجب أن تكون متكررة بحد ذاتها. تستغل Apriori ذلك عن طريق تقليم كل مجموعة مرشحة k-عنصر إذا لم تكن جميع مجموعاتها الفرعية (k-1) موجودة في المجموعة المتكررة L_{k-1} التي تم التحقق منها. هذا يقلل بشكل كبير من مساحة البحث، ويتجنب عمليات مسح مكلفة لقاعدة البيانات لمجموعات العناصر التي لا يمكن أن تكون متكررة.

الصيغة
\forall X \in C_k,\; \forall Y \subset X,\; |Y| = k-1 : Y \notin L_{k-1} \Rightarrow X \notin L_k
3

من كل مجموعة عناصر متكررة X ∪ Y، تقوم الخوارزمية بإنشاء قواعد X ⇒ Y حيث X و Y مجموعتان فرعيتان منفصلتان. يتم الاحتفاظ بالقاعدة فقط عندما يلبي دعمها — الاحتمال الشرطي لـ Y بالنظر إلى X، محسوبًا على أنه دعم(X ∪ Y) / دعم(X) — الحد الأدنى لثقة γ_min أو يتجاوزه. هذه الخطوة تحول التواجد المشترك الخام إلى عبارات تنبؤية اتجاهية.

الصيغة
X \Rightarrow Y \text{ where } X \cap Y = \emptyset,\quad \text{confidence}(X \Rightarrow Y) = \frac{\text{support}(X \cup Y)}{\text{support}(X)} \geq \gamma_{\min}
4

يتم ترتيب القواعد المحتفظ بها وتصفيتها حسب الرفع، والذي يقيس مدى احتمالية ظهور Y مع X أكثر من الصدفة. يشير الرفع > 1 إلى ارتباط إيجابي يتجاوز الاستقلال؛ يشير الرفع = 1 إلى الاستقلال؛ يشير الرفع < 1 إلى ارتباط سلبي. يمكن لمقاييس الاهتمام الإضافية مثل الإدانة والرافعة أن تزيد من تحسين مجموعة القواعد للنشر العملي.

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

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

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

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

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

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

كيف تقلل خوارزمية Apriori من التكلفة الحسابية؟

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

متى يجب أن أستخدم FP-Growth بدلاً من Apriori؟

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

طرق ذات صلة

المصادر

  1. Agrawal, R., Imieliński, T., & Swami, A. (1993). Mining association rules between sets of items in large databases. ACM SIGMOD, 207–216.

    افتح مرجع DOI
    تم النسخ.
  2. Agrawal, R., & Srikant, R. (1994). Fast algorithms for mining association rules. Proceedings of the 20th VLDB Conference, 487–499.

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