قسمت هفتم – الگوریتم FP-Growth (Frequent Pattern Growth)

الگوریتم FP-Growth (Frequent Pattern Growth) یک روش کارآمد برای استخراج الگوهای فراوان (Frequent Patterns) از پایگاه‌های داده تراکنش است. این الگوریتم یکی از جایگزین‌های الگوریتم Apriori است و مزایای قابل توجهی از جمله سرعت بالاتر و نیاز کمتر به حافظه دارد.

مقدمه

در تحلیل داده‌های تراکنش، هدف این است که مجموعه‌های کالایی که به‌طور مکرر در تراکنش‌ها با هم خریداری می‌شوند، شناسایی شوند. این فرآیند به‌عنوان “استخراج الگوهای فراوان” شناخته می‌شود. الگوریتم FP-Growth یک روش کارآمد برای پیدا کردن این مجموعه‌ها است و برخلاف الگوریتم Apriori نیازی به انجام بررسی‌های متعدد بر روی همه مجموعه‌های ممکن ندارد.

مراحل اصلی الگوریتم FP-Growth

الگوریتم FP-Growth در دو مرحله اصلی اجرا می‌شود:

1. ساخت ساختار درخت FP (Frequent Pattern Tree)

در این مرحله، تمام داده‌های ورودی (تراکنش‌ها) بررسی می‌شوند تا ساختار درختی به نام “درخت FP” ساخته شود. درخت FP یک درخت فشرده است که برای ذخیره‌سازی مجموعه‌های فرکانس بالا و تکرار در تراکنش‌ها طراحی شده است. این درخت به‌طور کارآمدی تمام تراکنش‌ها را فشرده می‌کند و به الگوریتم کمک می‌کند تا تنها الگوهای فراوان را شناسایی کند.

2. استخراج الگوهای فراوان

در این مرحله، پس از ساخت درخت FP، الگوریتم از آن برای استخراج الگوهای فراوان استفاده می‌کند. این فرآیند معمولاً به‌صورت بازگشتی انجام می‌شود، به این معنی که الگوریتم ابتدا الگوهای فراوان برای پایین‌ترین سطوح درخت را شناسایی کرده و سپس به‌تدریج الگوهای سطح بالاتر را پیدا می‌کند.

تفسیر خروجی بالا

در خروجی گراف FP-Growth بالا، هر لبه (Edge) نمایانگر یک رابطه یا هم‌ارتباط بین دو محصول است. این روابط از طریق مقادیری مانند Lift اندازه‌گیری می‌شوند. برای مثال:

• رابطه بین “Touring Tire” و “Touring Tire Tube” با عدد ۱۱.۳۹ نشان می‌دهد که این دو محصول اغلب با هم خریداری می‌شوند و ارتباط بسیار قوی‌ای دارند. عدد ۱۱.۳۹ به معنی Lift است که میزان ارتباط قوی بین این دو محصول را نشان می‌دهد. به‌طور دقیق‌تر، Lift بیشتر از ۱ به این معنا است که این دو محصول بیشتر از حد انتظار با هم خریداری می‌شوند.
• رابطه بین “Bottle” و “ML Road Tire” با عدد ۱.۵۳ نشان‌دهنده یک ارتباط نسبی و قوی است. اگرچه این دو محصول نسبت به “Touring Tire” و “Touring Tire Tube” ارتباط کمتری دارند (Lift کمتر از ۱۱.۳۹)، اما هنوز هم بیشتر از آنچه که به‌طور تصادفی انتظار می‌رود با هم خریداری می‌شوند. عدد ۱.۵۳ نشان‌دهنده این است که این دو محصول نیز به‌طور معناداری در کنار هم قرار می‌گیرند.

تفسیر مقادیر:

• Support: درصدی از تراکنش‌ها که شامل مجموعه‌ای از محصولات هستند.
• Confidence: احتمال اینکه یک محصول پس از خرید یک محصول دیگر خریداری شود.
• Lift: قدرت ارتباط بین دو محصول، که اگر مقدار Lift بیشتر از ۱ باشد، نشان‌دهنده ارتباط مثبت بین آن‌ها است. هرچه مقدار Lift بالاتر باشد، نشان‌دهنده ارتباط قوی‌تری است.

مزایای FP-Growth

1. سرعت بیشتر: در مقایسه با Apriori که نیاز به تولید مجموعه‌های مختلف کاندید دارد، FP-Growth تنها نیاز به ساخت یک درخت واحد دارد، که باعث کاهش چشمگیر زمان پردازش می‌شود.
2. صرفه‌جویی در حافظه: FP-Growth تنها نیاز به ذخیره‌سازی یک درخت فشرده دارد که فضای کمتری را نسبت به نگهداری تمامی مجموعه‌های کاندید مصرف می‌کند.
3. بدون نیاز به تولید مجموعه‌های کاندید: در FP-Growth نیازی به تولید مجموعه‌های کاندید فراوان نیست، بلکه با استفاده از درخت FP به‌طور مستقیم به‌دنبال الگوهای فراوان می‌گردد.

معایب FP-Growth

1. پیچیدگی زمانی در ساخت درخت: اگرچه ساختار درخت FP به‌طور کلی سریع است، اما در مواردی که داده‌ها بسیار پیچیده و متنوع باشند، زمان ساخت درخت ممکن است طولانی شود.
2. وابستگی به حافظه: درخت FP باید در حافظه نگهداری شود، بنابراین در مقادیر بسیار بزرگ داده، ممکن است مشکلات حافظه به وجود آید.

کاربردها

الگوریتم FP-Growth در بسیاری از زمینه‌ها از جمله:

• تحلیل بازار (Market Basket Analysis)
• شناسایی الگوهای خرید مشتریان
• توصیه سیستم‌ها
• کشف روابط بین ویژگی‌ها در داده‌های بزرگ استفاده می‌شود.

در نهایت، FP-Growth یک روش قدرتمند و کارآمد برای کشف الگوهای فراوان در داده‌های تراکنش است و به‌طور خاص در مواقعی که حجم داده‌ها زیاد است و نیاز به پردازش سریع داریم، می‌تواند بسیار مفید باشد.