مجموعات العناصر المتكررة القصوى

Abstract

التنقيب عن قواعد الإرتباط واحدة من أشهر عمليات التنقيب في البيانات، والتي تستخدم في البحث عن العلاقات غير الظاهرة أو المخفية بين العناصر داخل قواعد المعاملات. ونتيجة لذلك فإن تطبيقاتها اليوم تشمل العديد من المجالات المختلفة، أبرزها المجال التجاري حيث تتواجد قواعد الإرتباط في كل عمليات تحليل سلة التسوق، عمليات تجميع المنتجات وترتيبها في المراكز والمحلات التجارية إضافة إلى عمليات تصميم دليل السلع والمنتجات... . لكن المشكلة الرئيسية في التنقيب عن قواعد الإرتباط تكمن في البحث عن مجموعات العناصر المتكررة التي تساهم في إنشاء هذه القواعد. لذلك أقتُرِحت خلال العقدين الماضيين العديدُ من الخوارزميات لحلّ هذه المشكلة، أبرزها خوارزمية Aprioriالتي تعتمد المقاربة بالمستويات، خوارزميةEclat والتيتستخدم المُقاربة العمودية وأيضا خوارزمية المقاربة بالإسقاط FRGrowth. حققت مختلف هذه الخوارزميات نجاحًا باهرا على مدى سنوات، لكنها بقيت تُعاني من كونها "مكلفة للغاية" من حيث الزمن المستغرق والمساحة التخزينية للذاكرة عند التنفيذ. في هذا العمل سيتم دراسة التمثيلات المتراصة لمجموعات العناصر المتكررة المقترحة في بداية الألفية الجديدة، وبشكل خاص تمثيلات مجموعات العناصر المتكررة القصوى، من حيث مفاهيمها الأساسية وإستعراض لبعض الخوارزميات الموجودة حاليا للبحث عن مجموعات العناصر المتكررة القصوى في قواعد المعاملات، ليتم بعدها القيام بمقارنة لإثنتين من هذه الخوارزميات هما FPMaxو Charm-MFI والموجودتين في منصة SPMF مفتوحة المصدر بإستعمال قواعد معاملات مختلفة الأنواع والأحجام. حيث أظهرت النتائج التجريبية تفوق خوارزمية FPMax على خوارزمية Charm-MFIمن حيث الإستهلاك الأقل للمساحة التخزينية للذاكرة، أمّا بالنسبة للزمن المستغرق للتنفيذ فإنّ خوارزمية Charm-MFIتفوقت في قواعد المعاملات المتناثرة بالمقابل رجح كفة خوارزمية FPMax في قواعد المعاملات المكثّفة.