خوارزمية النمو FP-Growth في عملية التنقيب في البيانات

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

ما هي خوارزمية FP-Growth

تُعد خوارزمية النمو (FP-Growth) طريقة بديلة للعثور على مجموعات عناصر متكررة دون استخدام الأجيال المرشحة وبالتالي تحسين الأداء، وبالنسبة للكثير تستخدم استراتيجية “فرق تسد”، ويتمثل جوهر هذه الطريقة في استخدام بنية بيانات خاصة تسمى شجرة الأنماط المتكررة (شجرة FP) والتي تحتفظ بمعلومات اقتران مجموعة العناصر.

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

وتنقيب قواعد الرابطة (ARM) هو أسلوب للتنقيب عن البيانات لاكتشاف ارتباطات مثيرة للاهتمام بين مجموعات البيانات وإنّ نمو النمط المتسلسل (نمو FP) هو خوارزمية (ARM) فعالة لضغط المعلومات في بنية الشجرة، ومع ذلك فإنّها تميل إلى المعاناة من فجوة الأداء عند معالجة قواعد البيانات الكبيرة بسبب إجراءات التنقيب الخاصة بها.

مبدأ عمل خوارزمية FP-Growth

• يقوم بضغط قاعدة بيانات الإدخال لإنشاء مثيل شجرة (FP) لتمثيل العناصر المتكررة.

• بعد هذه الخطوة الأولى تقوم بتقسيم قاعدة البيانات المضغوطة إلى مجموعة من قواعد البيانات الشرطية وكل منها مرتبط بنمط واحد متكرر.

• يتم تنقيب كل قاعدة بيانات بشكل منفصل.

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

ما هي شجرة خوارزمية FP-Growth

شجرة الأنماط المتسلسلة (FP-tree) هي بنية بيانات مضغوطة تخزن المعلومات الكمية حول الأنماط المتكررة في قاعدة البيانات وتتم قراءة كل معاملة ثم تعيينها على مسار في شجرة (FP)، كما يتم ذلك حتى تتم قراءة جميع المعاملات وتسمح المعاملات المختلفة ذات المجموعات الفرعية المشتركة للشجرة بالبقاء مضغوطة لأن مساراتها تتداخل.

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

ويتم الحفاظ على ارتباطات العقد مع العقد السفلية أي العناصر التي يتم تعيينها مع مجموعات العناصر الأخرى وأثناء تكوين الشجرة، ويتم تسمية جذر واحد بأنه “فارغ” مع مجموعة من الأشجار الفرعية لبادئة العنصر كأفرع وجدول متكرر لرأس العناصر وتتكون كل عقدة في الشجرة الفرعية لبادئة العنصر من ثلاثة حقول:

• اسم العنصر: يسجل العنصر الذي تمثله العقدة.

• العدد: عدد المعاملات التي يمثلها جزء المسار الذي يصل إلى العقدة.

• رابط العقدة: روابط للعقدة التالية في شجرة (FP) تحمل نفس اسم العنصر أو خالية إذا لم يكن هناك أي شيء.

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

يحدث السيناريو الأسوأ عندما يكون لكل معاملة مجموعة عناصر فريدة، لذا فإنّ المساحة اللازمة لتخزين الشجرة أكبر من المساحة المستخدمة لتخزين مجموعة البيانات الأصلية؛ لأنّ شجرة (FP) تتطلب مساحة إضافية لتخزين المؤشرات بين العقد والعدادات لكل عنصر.

مزايا خوارزمية FP-Growth

• تحتاج هذه الخوارزمية إلى مسح قاعدة البيانات مرتين عند مقارنتها بـ (Apriori) الذي يقوم بمسح المعاملات لكل تكرار.

• لا يتم إقران العناصر في هذه الخوارزمية ممّا يجعلها أسرع.

• يتم تخزين قاعدة البيانات في نسخة مضغوطة في الذاكرة.

• إنّها فعالة وقابلة للتطوير للتنقيب بالأنماط المتسلسلة الطويلة والقصيرة.

عيوب خوارزمية FP-Growth

• شجرة (FP) أكثر تعقيدًا وصعوبة في البناء من (Apriori).

• قد تكون باهظة الثمن.

• قد لا تتناسب الخوارزمية مع الذاكرة المشتركة عندما تكون قاعدة البيانات كبيرة.

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