Skip to content
بازگشت به نتایج جست‌وجو

FP-Growth (رشد الگوی پرتکرار)

معرفی‌شده توسط
Jiawei Han, Jian Pei & Yiwen Yin
سال
2000
نوع
Frequent-itemset mining algorithm
خانواده
Pattern mining

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

FP-Growth که توسط جیاوی هان، جیان پی و یی‌ون یین در سال ۲۰۰۰ معرفی شد، مجموعه‌های قلم (itemsets) پرتکرار را از داده‌های تراکنشی استخراج می‌کند، بدون اینکه مجموعه‌های کاندید را تولید کند؛ این مرحله پرهزینه‌ای است که الگوریتم کلاسیک Apriori را کند می‌کند. این روش پایگاه داده را در دو پیمایش فشرده کرده و به یک درخت الگوی پرتکرار (FP-tree) تبدیل می‌کند، سپس الگوهای پرتکرار را به صورت بازگشتی از آن ساختار رشد می‌دهد، که این امر آن را به طور چشمگیری سریع‌تر از Apriori بر روی مجموعه داده‌های بزرگ و متراکم می‌سازد.

شهود پشت روش

Apriori مجموعه‌های قلم پرتکرار را با تولید و آزمون مکرر ترکیبات کاندید پیدا می‌کند — این یک فرآیند پرهزینه و نیازمند پیمایش زیاد است که در داده‌های متراکم منفجر می‌شود. FP-Growth مسیری متفاوت را در پیش می‌گیرد: کل پایگاه داده تراکنش‌ها را به یک درخت فشرده می‌فشارد که در آن پیشوند‌های مشترک یک بار ذخیره می‌شوند، بنابراین الگوهای مشترک همپوشانی و فشرده می‌شوند. سپس، به جای تولید کاندیدها، الگوهای پرتکرار را مستقیماً از درخت با دنبال کردن مسیرهایی که به هر قلم منجر می‌شوند و استخراج بازگشتی درخت‌های «شرطی» کوچک‌تر، می‌خواند. دو پیمایش بر روی داده‌ها و یک ساختار داده هوشمندانه، به جای پیمایش‌های متعدد و انفجار ترکیبی کاندید در Apriori، جایگزین می‌شوند.

تاریخ

هان، پی و یین FP-Growth را در SIGMOD 2000 به عنوان جایگزینی بدون تولید کاندید برای Apriori معرفی کردند، با پرداختی گسترده‌تر در مقاله Data Mining and Knowledge Discovery سال ۲۰۰۴ خود. ایده درخت الگوی پرتکرار — فشرده‌سازی تراکنش‌ها در یک ساختار پیشوند مشترک و استخراج بازگشتی آن — در کنار Apriori (مبتنی بر کاندید) و ECLAT (قالب عمودی)، به یک تکنیک بنیادی در استخراج الگو تبدیل شد. این روش همچنان یک استخراج‌کننده مجموعه قلم استاندارد و با کارایی بالا در کتابخانه‌های داده‌کاوی باقی مانده است.

چه زمانی استفاده شود

از FP-Growth برای استخراج مجموعه‌های قلم پرتکرار (و به طور پایین‌دستی، قوانین وابستگی) از داده‌های تراکنشی استفاده کنید — تحلیل سبد خرید، استخراج استفاده از وب و جریان کلیک، توصیه‌گری، و هم‌وقوعی در بیوانفورماتیک — به ویژه بر روی مجموعه داده‌های بزرگ یا متراکم که در آن‌ها تولید کاندید Apriori خیلی کند است. این روش تنها به دو پیمایش پایگاه داده نیاز دارد و معمولاً به طور قابل توجهی بهتر از Apriori عمل می‌کند. هزینه‌های آن: درخت FP باید در حافظه جا شود (محدودیتی برای مجموعه داده‌های بسیار بزرگ یا فوق‌العاده پراکنده، که در آن‌ها درخت ضعیف فشرده می‌شود)، پیاده‌سازی بازگشت می‌تواند پیچیده باشد، و مانند تمام استخراج مبتنی بر پشتیبانی، به آستانه حداقل پشتیبانی حساس است (خیلی پایین خروجی را منفجر می‌کند، خیلی بالا الگوها را از دست می‌دهد). ECLAT (تقاطع مجموعه داده عمودی) یک جایگزین است؛ برای خود قوانین، با تولید قوانین وابستگی جفت کنید.

محدودیت‌ها و ملاحظات

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

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • بدون تولید کاندید — بسیار سریع‌تر از Apriori بر روی داده‌های بزرگ/متراکم.
  • فقط دو پیمایش پایگاه داده، صرف نظر از طول الگو.
  • درخت FP ساختار مشترک را فشرده می‌کند، حافظه و زمان را در داده‌های متراکم ذخیره می‌کند.
  • به الگوهای پرتکرار طولانی که روش‌های مبتنی بر کاندید را تحت‌الشعاع قرار می‌دهند، مقیاس‌پذیر است.

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

اولین پیمایش پایگاه داده، پشتیبانی (support) هر قلم را شمارش کرده و آن‌هایی را که زیر آستانه حداقل پشتیبانی هستند، دور می‌ریزد. قلم‌های پرتکرار باقی‌مانده بر اساس فراوانی نزولی مرتب می‌شوند — این ترتیب به تراکنش‌ها اجازه می‌دهد پیشوندهای درخت را به اشتراک بگذارند و درخت FP را فشرده نگه می‌دارد.

فرمول
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

دومین پیمایش، هر تراکنش (قلم‌های پرتکرار آن، به ترتیب مرتب شده) را در درخت FP درج می‌کند، شمارش‌ها را در طول مسیرهای پیشوند مشترک افزایش می‌دهد و در صورت نیاز شاخه‌های جدیدی اضافه می‌کند. یک جدول سربرگ (header table) تمام وقوع هر قلم را به هم پیوند می‌دهد، بنابراین درخت به طور فشرده ساختار پرتکرار کل مجموعه داده را نشان می‌دهد.

فرمول
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

برای هر قلم پرتکرار (با کمترین فراوانی اول پردازش می‌شود)، الگوریتم پایگاه الگوی شرطی (conditional pattern base) آن را جمع‌آوری می‌کند — مجموعه‌ای از مسیرهای پیشوند در درخت که با آن قلم هم‌وقوع هستند، هر کدام وزن‌دهی شده با شمارش آن. این، زمینه (context)‌ای را که قلم در آن به طور پرتکرار ظاهر می‌شود، ثبت می‌کند.

فرمول
\text{for each item: collect its conditional pattern base (prefix paths)}
4

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

فرمول
\text{build conditional FP-trees recursively to grow frequent patterns}

دام‌های رایج

  • تنظیم حداقل پشتیبانی خیلی پایین، که منجر به انفجار مجموعه‌های قلم می‌شود.
  • فرض اینکه همیشه بهتر از Apriori عمل می‌کند — در داده‌های کوچک یا پراکنده، سود ناچیز است.
  • فراموش کردن اینکه مجموعه‌های قلم پرتکرار، قوانین نیستند؛ تولید قانون یک مرحله جداگانه است.
  • نادیده گرفتن محدودیت‌های حافظه زمانی که درخت FP نمی‌تواند در RAM نگهداری شود.

پرسش‌های متداول

چگونه FP-Growth سریع‌تر از Apriori است؟

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

درخت FP چیست؟

یک درخت پیشوند فشرده از قلم‌های پرتکرار پایگاه داده. تراکنش‌هایی که یک پیشوند را به اشتراک می‌گذارند، یک مسیر را به اشتراک می‌گذارند، با شمارش گره‌ها که پشتیبانی را ثبت می‌کنند، و یک جدول سربرگ وقوع هر قلم را به هم پیوند می‌دهد. این ساختار پرتکرار مجموعه داده را به طور فشرده ذخیره می‌کند تا الگوها بدون پیمایش مجدد داده‌ها قابل خواندن باشند.

FP-Growth چگونه به ECLAT و قوانین وابستگی مرتبط است؟

FP-Growth، ECLAT و Apriori همگی مجموعه‌های قلم پرتکرار را پیدا می‌کنند؛ ECLAT به جای درخت، از رویکرد تقاطع مجموعه داده عمودی استفاده می‌کند. یافتن مجموعه‌های قلم پرتکرار تنها مرحله اول است — قوانین وابستگی (با اطمینان/بالابری) از آن مجموعه‌های قلم در یک مرحله جداگانه تولید می‌شوند.

روش‌های مرتبط

منابع

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    باز کردن مرجع DOI
    کپی شد.
  2. 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
    کپی شد.