الگوریتم FP-Growth (Frequent Pattern Growth) یک روش کارآمد و تأثیرگذار در حوزه دادهکاوی (Data Mining) است که برای کشف مجموعههای اقلام مکرر (Frequent Itemsets) در پایگاههای داده تراکنشی (Transactional Databases) به کار میرود. این الگوریتم توسط جیاوئی هان (Jiawei Han) و همکارانش در سال ۲۰۰۰ معرفی شد و به عنوان یک جایگزین قدرتمند برای الگوریتم Apriori شناخته میشود. هدف اصلی FP-Growth، یافتن الگوهای پنهان در دادهها است که نشاندهنده همرخدادی اقلام مختلف (مانند محصولات خریداری شده در یک سبد خرید) هستند.
مفهوم مجموعههای اقلام مکرر
در دادهکاوی، یک “مجموعه اقلام مکرر” به گروهی از اقلام اطلاق میشود که به طور مکرر و با یک حداقل آستانه مشخص (Minimum Support) در تراکنشها ظاهر میشوند. به عنوان مثال، در یک سوپرمارکت، اگر مشتریان اغلب شیر و نان را با هم خریداری کنند، “شیر و نان” یک مجموعه اقلام مکرر محسوب میشود. کشف این الگوها اساس تحلیل سبد خرید (Market Basket Analysis) و تولید قوانین انجمنی (Association Rules) است.
چرا FP-Growth توسعه یافت؟ (مقایسه با Apriori)
پیش از FP-Growth، الگوریتم Apriori روش استاندارد برای کشف الگوهای مکرر بود. Apriori از یک رویکرد کاندیدا-تولید-آزمون (Candidate Generation and Test) استفاده میکند که در آن ابتدا مجموعههای اقلام کاندیدای مکرر ایجاد شده و سپس پشتیبانی (Support) آنها در کل پایگاه داده محاسبه میشود. این فرآیند بهویژه برای پایگاههای داده بزرگ با اقلام زیاد، بسیار زمانبر و نیازمند اسکنهای مکرر پایگاه داده است.
FP-Growth برای غلبه بر این محدودیتها طراحی شد. ویژگیهای کلیدی آن عبارتند از:
- عدم تولید کاندیدا: FP-Growth نیازی به تولید مجموعههای اقلام کاندیدا ندارد، که باعث کاهش قابل توجهی در زمان پردازش و حافظه مصرفی میشود.
- اسکن کمتر پایگاه داده: این الگوریتم تنها دو بار پایگاه داده را اسکن میکند.
- ساختار داده فشرده: استفاده از ساختار دادهای به نام FP-Tree.
نحوه کار الگوریتم FP-Growth
FP-Growth بر پایه یک ساختار داده درختی به نام “درخت الگوهای مکرر” یا “FP-Tree” عمل میکند. مراحل اصلی این الگوریتم به شرح زیر است:
1. اولین اسکن پایگاه داده:
- الگوریتم یک بار پایگاه داده تراکنشی را اسکن میکند تا فراوانی (Frequency) هر قلم را محاسبه کند.
- اقلامی که فراوانی آنها کمتر از “حداقل پشتیبانی” (Minimum Support) است، فیلتر میشوند.
- اقلام باقیمانده بر اساس فراوانی نزولی مرتب میشوند (به این ترتیب که اقلام مکررتر در ابتدای لیست قرار میگیرند).
2. ساخت FP-Tree:
- پایگاه داده برای بار دوم اسکن میشود.
- برای هر تراکنش، اقلام موجود در آن (که قبلاً فیلتر و مرتب شدهاند) به ترتیب فراوانی نزولی وارد درخت FP-Tree میشوند.
- اگر مسیر مشابهی در درخت از قبل وجود داشته باشد، شمارنده (Count) گرههای موجود در آن مسیر افزایش مییابد. در غیر این صورت، گرههای جدیدی ایجاد میشوند.
- در نهایت، یک درخت فشرده و متراکم از الگوهای مکرر ایجاد میشود که تمام اطلاعات مربوط به فراوانی اقلام را در خود جای داده است.
3. استخراج مجموعههای اقلام مکرر از FP-Tree:
- الگوریتم با شروع از پایینترین سطح درخت (اقلام با کمترین فراوانی) به سمت ریشه، اقدام به استخراج مجموعههای اقلام مکرر میکند.
- برای هر قلم، یک “پایگاه داده شرطی” (Conditional Pattern Base) و سپس یک “درخت FP شرطی” (Conditional FP-Tree) ساخته میشود.
- این فرآیند بهصورت بازگشتی (Recursive) ادامه مییابد تا زمانی که تمام مجموعههای اقلام مکرر با حداقل پشتیبانی مشخص، شناسایی شوند.
مزایای کلیدی FP-Growth
- کارایی بالا: به دلیل عدم نیاز به تولید کاندیداها و تعداد کم اسکنهای پایگاه داده، FP-Growth در مقایسه با Apriori بسیار سریعتر عمل میکند، بهویژه برای دادههای بزرگ و متراکم.
- کاهش مصرف حافظه: ساختار FP-Tree یک نمایش فشرده از پایگاه داده است که به کاهش نیاز حافظه کمک میکند.
- مناسب برای دادههای بزرگ: این الگوریتم برای تحلیل دادههای حجیم و با ابعاد بالا بسیار مناسب است.
کاربردهای FP-Growth
الگوریتم FP-Growth کاربردهای فراوانی در زمینههای مختلف دارد، از جمله:
- تحلیل سبد خرید (Market Basket Analysis): شناسایی اقلامی که مشتریان اغلب با هم خریداری میکنند.
- توصیهگرها (Recommendation Systems): پیشنهاد محصولات یا خدمات مرتبط به کاربران.
- تحلیل تراکنشهای مالی: کشف الگوهای مشکوک در تراکنشها برای شناسایی کلاهبرداری.
- تحلیل وبلاگها: شناسایی مسیرهای پربازدید کاربران در وبسایتها.
- تشخیص بیماری: یافتن همرخدادی علائم یا فاکتورها در تشخیص بیماریها.
FP-Growth یک ابزار قدرتمند و انعطافپذیر است که به محققان و تحلیلگران داده اجازه میدهد تا الگوهای ارزشمند را به طور کارآمد از حجم عظیمی از دادهها استخراج کنند.
کلیدواژه ها : FP-Growth-الگوریتم FP-Growth-کشف الگوهای مکرر-Frequent Itemsets-دادهکاوی-Data Mining-تحلیل سبد خرید-Market Basket Analysis-FP-Tree-الگوریتم Apriori-قوانین انجمنی-Association Rules-Weka FP-Growth-
