خوارزمية نمو الأنماط المتكررة (FP-Growth)
- قدّمه
- Jiawei Han, Jian Pei & Yiwen Yin
- السنة
- 2000
- النوع
- Frequent-itemset mining algorithm
- العائلة
- Pattern mining
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
تُعد خوارزمية FP-Growth، التي قدمها جياوي هان وجيان بيي ويي وين ين في عام 2000، أداة لاستخراج مجموعات العناصر المتكررة من بيانات المعاملات دون الحاجة إلى توليد مجموعات مرشحة، وهي الخطوة المكلفة التي تبطئ خوارزمية Apriori الكلاسيكية. تقوم هذه الخوارزمية بضغط قاعدة البيانات في شجرة الأنماط المتكررة (FP-tree) في مسحين، ثم تنمي الأنماط المتكررة بشكل تكراري من هذا الهيكل، مما يجعلها أسرع بكثير من Apriori على مجموعات البيانات الكبيرة والكثيفة.
الفكرة الحدسية وراء الطريقة
تجد خوارزمية Apriori مجموعات العناصر المتكررة عن طريق توليد واختبار مجموعات مرشحة بشكل متكرر - وهي عملية مكلفة وتعتمد على المسح المتكرر وتنفجر مع البيانات الكثيفة. تسلك خوارزمية FP-Growth مسارًا مختلفًا: فهي تضغط قاعدة بيانات المعاملات بأكملها في شجرة مدمجة حيث يتم تخزين البادئات المشتركة مرة واحدة، بحيث تتداخل الأنماط الشائعة وتُضغط. بعد ذلك، بدلاً من توليد المرشحين، تقرأ الأنماط المتكررة مباشرة من الشجرة عن طريق تتبع المسارات التي تؤدي إلى كل عنصر وتعدين الأشجار 'الشرطية' الأصغر بشكل تكراري. مسحان للبيانات وهيكل بيانات ذكي يحلان محل مسحات Apriori المتعددة وانفجار المرشحين التوافقي.
التاريخ
قدم هان وبيي وين خوارزمية FP-Growth في مؤتمر SIGMOD 2000 كبديل خالٍ من توليد المرشحين لخوارزمية Apriori، مع معالجة موسعة في مقالهم عام 2004 في Data Mining and Knowledge Discovery. أصبحت فكرة شجرة الأنماط المتكررة - ضغط المعاملات في هيكل بادئة مشترك وتعدينها بشكل تكراري - تقنية أساسية في تعدين الأنماط، جنبًا إلى جنب مع Apriori (المعتمدة على المرشحين) و ECLAT (بالتنسيق الرأسي). لا تزال أداة قياسية عالية الأداء لاستخراج مجموعات العناصر في مكتبات تعدين البيانات.
متى تُستخدم
استخدم خوارزمية FP-Growth لاستخراج مجموعات العناصر المتكررة (وبشكل لاحق، قواعد الارتباط) من بيانات المعاملات - تحليل سلة السوق، واستخراج استخدام الويب وسجل النقرات، والتوصية، والتعايش الحيوي المعلوماتي - خاصة على مجموعات البيانات الكبيرة أو الكثيفة حيث يكون توليد المرشحين في Apriori بطيئًا للغاية. تحتاج فقط إلى مسحين لقاعدة البيانات وعادة ما تتفوق على Apriori بشكل كبير. تكاليفها: يجب أن تتسع شجرة FP-tree في الذاكرة (وهو قيد لمجموعات البيانات الكبيرة جدًا أو المتفرقة للغاية، حيث تضغط الشجرة بشكل ضعيف)، يمكن أن تكون التكرارية معقدة في التنفيذ، ومثل جميع عمليات التعدين المستندة إلى الدعم، فهي حساسة للحد الأدنى من عتبة الدعم (إذا كانت منخفضة جدًا تؤدي إلى انفجار المخرجات، وإذا كانت مرتفعة جدًا تفوت الأنماط). خوارزمية ECLAT (تقاطع مجموعات معرفات المعاملات الرأسية) هي بديل؛ بالنسبة للقواعد نفسها، اقترنها بتوليد قواعد الارتباط.
الحدود والاعتبارات
- يجب أن تتسع شجرة FP-tree في الذاكرة؛ قد لا تكون مجموعات البيانات الكبيرة جدًا كذلك.
- على البيانات المتفرقة، تضغط الشجرة بشكل ضعيف، مما يقلل من الميزة.
- بناء الشجرة الشرطية التكراري معقد نسبيًا في التنفيذ.
- حساس للحد الأدنى من عتبة الدعم، مثل جميع عمليات تعدين مجموعات العناصر المتكررة.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- لا يوجد توليد مرشحين - أسرع بكثير من Apriori على البيانات الكبيرة/الكثيفة.
- مسحان فقط لقاعدة البيانات، بغض النظر عن طول النمط.
- تضغط شجرة FP-tree الهيكل المشترك، مما يوفر الذاكرة والوقت على البيانات الكثيفة.
- تتوسع لتشمل الأنماط المتكررة الطويلة التي تطغى على الطرق المعتمدة على المرشحين.
التطبيقات
- تحليل سلة السوق وتعدين الارتباط في البيع بالتجزئة.
- تعدين أنماط استخدام الويب وسجل النقرات.
- التوصية عبر العناصر المتكررة التعايش.
- التعايش الحيوي المعلوماتي واكتشاف الأنماط.
- أي مهمة واسعة النطاق لمجموعات العناصر المتكررة حيث تكون Apriori بطيئة جدًا.
كيف يعمل
كيف يعمل
يقوم المسح الأول لقاعدة البيانات بحساب دعم كل عنصر واستبعاد تلك التي تقل عن الحد الأدنى لدعم. يتم فرز العناصر المتكررة المتبقية بترتيب تنازلي حسب التكرار - وهذا الترتيب يسمح للمعاملات بمشاركة بادئات الشجرة ويحافظ على شجرة FP-tree مدمجة.
الصيغة
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}يقوم المسح الثاني بإدراج كل معاملة (عناصرها المتكررة، بالترتيب المُفرز) في شجرة FP-tree، مع زيادة العد على طول مسارات البادئات المشتركة وإضافة فروع جديدة حسب الحاجة. تربط طاولة رأسية جميع تكرارات كل عنصر، بحيث تمثل الشجرة بشكل مدمج الهيكل المتكرر لمجموعة البيانات بأكملها.
الصيغة
\text{second scan: insert each transaction's frequent items into the FP-tree}لكل عنصر متكرر (يتم معالجته من الأقل تكرارًا أولاً)، تجمع الخوارزمية قاعدة الأنماط الشرطية الخاصة به - وهي مجموعة مسارات البادئات في الشجرة التي تتواجد مع هذا العنصر، وكل منها مُرجح بعدده. هذا يلتقط السياق الذي يظهر فيه العنصر بشكل متكرر.
الصيغة
\text{for each item: collect its conditional pattern base (prefix paths)}من كل قاعدة أنماط شرطية، يتم بناء شجرة FP-tree شرطية أصغر وتعدينها بشكل تكراري، مما ينمي مجموعات عناصر أطول عن طريق إلحاق العنصر بالأنماط الموجودة في شجرته الشرطية. تتوقف التكرارية عند الأشجار ذات المسار الواحد، والتي يتم تعداد مجموعات عناصرها مباشرة - مما ينتج عنه جميع مجموعات العناصر المتكررة دون توليد مرشحين.
الصيغة
\text{build conditional FP-trees recursively to grow frequent patterns}الأخطاء الشائعة
- تعيين الحد الأدنى للدعم منخفضًا جدًا، مما ينتج عنه انفجار في مجموعات العناصر.
- افتراض أنها تتفوق دائمًا على Apriori - على البيانات الصغيرة أو المتفرقة يكون المكسب متواضعًا.
- نسيان أن مجموعات العناصر المتكررة ليست قواعد؛ توليد القواعد هو خطوة منفصلة.
- تجاهل حدود الذاكرة عندما لا يمكن الاحتفاظ بشجرة FP-tree في ذاكرة الوصول العشوائي.
الأسئلة الشائعة
كيف تكون FP-Growth أسرع من Apriori؟
تقوم Apriori بتوليد واختبار مجموعات العناصر المرشحة بشكل متكرر، وتقوم بمسح قاعدة البيانات عدة مرات. تتجنب FP-Growth توليد المرشحين تمامًا: فهي تضغط البيانات في شجرة FP-tree في مسحين وتستخرج الأنماط بشكل تكراري منها. هذا يزيل انفجار المرشحين التوافقي، مما يوفر تسريعًا كبيرًا على البيانات الكثيفة.
ما هي شجرة FP-tree؟
شجرة بادئة مضغوطة لعناصر البيانات المتكررة. تشترك المعاملات التي تشترك في بادئة في مسار، مع تسجيل عدد العقد للدعم، وتربط طاولة رأسية تكرارات كل عنصر. إنها تخزن الهيكل المتكرر لمجموعة البيانات بشكل مدمج بحيث يمكن قراءة الأنماط دون إعادة مسح البيانات.
كيف ترتبط FP-Growth بـ ECLAT وقواعد الارتباط؟
تجد FP-Growth و ECLAT و Apriori جميعها مجموعات العناصر المتكررة؛ تستخدم ECLAT نهج تقاطع مجموعات معرفات المعاملات الرأسية بدلاً من الشجرة. العثور على مجموعات العناصر المتكررة هو فقط المرحلة الأولى - يتم إنشاء قواعد الارتباط (مع الثقة/الرفع) من تلك المجموعات في خطوة منفصلة.
طرق ذات صلة
المصادر
Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.
افتح مرجع DOIتم النسخ.Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.
افتح مرجع DOIتم النسخ.