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

تعدين مجموعات العناصر المتكررة ECLAT

قدّمه
Mohammed J. Zaki
السنة
2000
النوع
Frequent-itemset mining algorithm (vertical format)
العائلة
Pattern mining

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

حجم الخط

ماذا تفعل؟

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

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

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

التاريخ

قدم محمد زكي خوارزمية ECLAT ونموذج التعدين الرأسي في عمل توج إلى ورقته البحثية في IEEE TKDE عام 2000 حول التعدين القابل للتوسع للارتباط، ثم قام بتحسينها لاحقاً باستخدام مجموعات الفروق (dECLAT). انضمت إلى Apriori (1994، توليد المرشحين الأفقي) و FP-Growth (2000، قائم على الشجرة) كواحدة من العائلات الثلاث القياسية لخوارزميات مجموعات العناصر المتكررة، حيث تتنافس كل منها في المسح والذاكرة وكثافة البيانات بشكل مختلف. لا تزال ECLAT خياراً قياسياً في أدوات تعدين البيانات.

متى تُستخدم

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

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

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

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

نقاط القوة

  • الدعم المحسوب عن طريق تقاطعات مجموعات المعرفات السريعة - لا توجد عمليات مسح متكررة لقاعدة البيانات.
  • البحث العميق مع فئات التكافؤ البادئة يعيد استخدام العمل ويحدد الذاكرة محلياً.
  • فعالة جداً في مجموعات البيانات الكثيفة، وتنافسية مع FP-Growth.
  • تحسين مجموعات الفروق يقلل بشكل أكبر من تكلفة الذاكرة والتقاطع.

التطبيقات

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

كيف يعمل

كيف يعمل

1

يتم تحويل قاعدة البيانات مرة واحدة إلى تنسيق رأسي: كل عنصر يقابل مجموعة معرفات المعاملات الخاصة به، وهي مجموعة المعاملات التي يظهر فيها. هذه هي بنية البيانات الرئيسية - كل العمل اللاحق هو عمليات مجموعات على مجموعات المعرفات، وليس مروراً عبر المعاملات الأصلية.

الصيغة
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}
2

دعم مجموعة العناصر هو عدد عناصر تقاطع مجموعات معرفات المعاملات الخاصة بعناصرها - عدد المعاملات التي تحتوي عليها جميعاً. يصبح العد تقاطعاً، وهو أمر سريع، وتكون العناصر الفردية المتكررة (تلك التي تكون مجموعة معرفاتها كبيرة بما يكفي) هي بذرة البحث.

الصيغة
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |
3

يتم توسيع مجموعات العناصر عن طريق تقاطع مجموعات المعرفات: مجموعة معرفات X ∪ {y} هي تقاطع مجموعات معرفات X و {y}. تستكشف خوارزمية ECLAT شبكة مجموعات العناصر بعمق أول ضمن فئات التكافؤ (مجموعات العناصر التي تشترك في بادئة)، لذلك يتم إعادة استخدام التقاطعات ويظل البحث محلياً.

الصيغة
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}
4

يتم الاحتفاظ بالتوسيع فقط إذا كانت مجموعة معرفاته (وبالتالي دعمه) تلبي الحد الأدنى لدعم الدعم؛ وإلا يتم تقليم هذا الفرع (مضاد للرتابة: لا يمكن أن يكون أي مجموعة فائقة متكررة). مجموعات الفروق - التي تخزن فقط الاختلافات بين مجموعات المعرفات - هي تحسين شائع يقلل بشكل أكبر من تكلفة الذاكرة والتقاطع.

الصيغة
\text{keep extensions with } \text{support} \ge \text{minsup}

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

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

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

كيف تختلف خوارزمية ECLAT عن Apriori و FP-Growth؟

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

ما هي مجموعة المعرفات (tidset)؟

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

ما هي مجموعات الفروق (diffsets)؟

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

طرق ذات صلة

المصادر

  1. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.

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