دیتاماینینگ یار

درخت های FP و الگوریتم FP-Growth در بیگ دیتا

کاوش قوانین انجمنی

کاوش قوانین انجمنی در راستای کشف ارتباطات جالب  و با اهمیت بین اقلام اطلاعاتی در پایگاه داده ها ی بزرگ و انبار های تراکنش می باشد. داده­ کاوی انجمنی و استخراج قوانین انجمنی از مجموعه داده­ ها اولین بار توسط آگراوال برای کشف دانش و الگوهای خرید کاربران یک فروشگاه ارائه گردید. در طرح پیشنهادی آگراوال، سبد خرید کل کاربران در یک مدت زمانی خاص بررسی می­گشت و سپس قوانین انجمنی از آن استخراج می­شد؛ عادات و رفتار خرید مشتریان مورد تحلیل قرار می گرفت و الگوهای موجود در اقلام خریداری شده کشف می شد. به­ عنوان مثال مشخص می شد مشتریانی که برای خرید نان به فروشگاه می­ آمدند اغلب شیر نیز خریداری می کردند و البته معیارهای مختلف برای اعتبار و قابلبت تعمیم این الگوها در نظر گرفته می­شد. از آن زمان تاکنون کارهای بسیاری چه در زمینه بهبود کارایی الگوریتم های استخراج قوانین انجمنی و چه از نظر گسترش کاربردهای قوانین انجمنی انجام شده است. پیدا کردن چنین قوانینی می­تواند در حوزه­ های مختلف مورد توجّه بوده و کاربردهای متفاوتی داشته باشد. به ­عنوان مثال: کشف روابط انجمنی بین حجم عظیم تراکنش های کسب و کار می­تواند درتشخیص تقلّب ، در حوزه پزشکی و همچنین داده­ کاوی در مورد اطلاعات روش بکارگیری وب توسط کاربران مورد استفاده قرار گیرد یا در طراحی کاتالوگ، بازاریابی و دیگر مراحل فرآیند تصمیم ­گیری کسب و کار مؤثّر باشد. الگوریتم های استخراج این قوانین در شکل زیر خلاصه شده اند.

الگوریتم Fp-Growth

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

در اوّلین اسکن پایگاه  ­داده همانند اپریوری مجموعه آیتم ­های یک­ عضوی و پشتیبانی آنها مشخص می­شود. مجموعه اقلام پرتکرار به ترتیب نزولی پشتیبانی­شان مرتّب می­شوند.

سپس یک درخت به این صورت ساخته می­شود که: اوّل ریشه درخت با برچسبnull ساخته می­شود. بعد از آن پایگاه ­داده برای بار دوم اسکن می­شود. اقلام هر تراکنش به ­ترتیب L پردازش می­شوند و یک شاخه برای هر تراکنش ایجاد می­شود.به­ منظور تسهیل پیمایش درخت، یک جدول ساخته می­شود که هر قلم درآن به محلّ­ خودش در درخت ­اشاره می­کند. درخت پس از اسکن همه تراکنش ها کامل می­شود.

  • کاوش الگوهای متناوب

در این بخش از نوشتار، در ارتباط با هریک از مسائل مهمی که در حوزه کاوش الگوهای متناوب مطرح می‌شوند، یک تعریف رسمی ارائه می‌کنیم.

 

  • کاوش مجموعه آیتم‌های متناوب

 مساله کاوش مجموعه آیتم‌های متناوب برای اولین بار توسط Agarwal در ۱۹۹۳ به صورت کاوش قوانین تداعی در میان مجموعه‌های آیتم ها ارائه شد. مجموعه  را به عنوان مجموعه‌ای از آیتم ها در نظر بگیرید. مجموعه آیتم یک زیرمجموعه از آیتم هاست که پس از این در این نوشتار آن را برای سادگی به صورت  می‌نویسیم. مجموعه آیتمی را که دارای l آیتم باشد، مجموعه آیتم l-تایی می‌نامند.

یک تراکنش  یک چندگانه است که در آن  شماره مشخصه تراکنش و X یک مجموعه آیتم است. گفته می‌شود که تراکنش  شامل مجموعه آیتم Y است اگر  باشد.

پایگاه تراکنش TDB مجموعه‌ای از تراکنش‌هاست. آستانه زیربری یک مجموعه آیتم X در پایگاه تراکنشTDB ، که به صورت  یا  نوشته می‌شود، تعداد تراکنش‌هایی از TDB است که شامل X باشد. یعنی:  

با در نظرگرفتن یک مقدار آستانه زیربری مانند min-sup، که توسط کاربر داده می‌شود، اگر  باشد، مجموعه آیتم  Xرا یک مجموعه آیتم متناوب یا یک الگوی متناوب می‌نامند. در یک مساله کاوش مجموعه آیتم‌های متناوب به دنبال یافتن مجموعه کامل همه آیتم های متناوبی از TDB هستیم که حد آستانه‌ای min-sup را ارضا نمایند.

قوانین تداعی، قابل حصول از مجموعه آیتم‌های متناوب هستند. یک قانون تداعی یک قانون به فرم  است که در آن X و Y دو مجموعه آیتم هستند و داریم: . قانون  در پایگاه تراکنش TDB  دارای میزان پشتیبانی s است اگر داشته باشیم: . قانون در پایگاه تراکنش TDB با میزان اطمینان c برقرار است که در آن c از رابطه  به دست می‌آید.

مساله کاوش قوانین تداعی با داشتن یک پایگاه تراکنش مانند TDB و حدآستانه پشتیبانی min-sup و میزان اطمینان min-conf، به یافتن مجموعه کامل همه قوانین تداعی می‌پردازد که میزان پشتیبانی آنها از min-sup و میزان اطمینان آنها از min-conf کمتر نباشد.

کاوش قوانین تداعی را می‌توان به دو فاز تقسیم بندی نمود. در فاز اول مجموعه آیتم‌های متناوبی که حد آستانه‌ای min-sup را ارضا نمایند کاوش می‌شوند و در فاز دوم بر اساس میزان اطمینان min-conf قوانین تداعی ساخته می‌شوند. براساس مطالعات انجام شده، فاز کاوش مجموعه آیتم‌های متناوب از نظر زمانی به مراتب هزینه برتر از فاز تولید قوانین است.

  • کاوش الگوهای توالی

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

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

تعریف رسمی این مساله به صورت زر است:

فرض کنید که مجموعه‌ای از آیتم‌ها باشد.­ هر زیر مجموعه‌ای از مجموعه I یک مجموعه آیتم است. یک توالی یک لیست مرتب از آیتم‌ها است که به صورت  نشان داده می‌شود و درآن هر  یک مجموعه آیتم است (یعنی ). در برخی مراجع  را یک رویداد از توالی نیز می‌نامند و  آن را به صورت  نشان می‌دهند که در آن  یک آیتم است (یعنی ). اگر رویدادی تنها یک آیتم داشته باشد می‌توانیم در نمایش آن پرانتزها را حذف نماییم. بنابراین رویداد (x) به صورت x نمایش داده می‌شود.

با توجه به مجموعه بودن یک رویداد، هر آیتم حداکثر یکبار می‌تواند در یک رویداد از توالی ظاهر شود و امکان تکرار چند باره یک آیتم در یک توالی (در رویدادهای مختلف توالی) وجود دارد. تعداد آیتم‌های موجود در یک توالی را طول توالی می‌نامند. توالی  یک زیرتوالی از توالی خوانده می‌شود و به صورت  نشان داده می‌شود اگر اعداد صحیح  وجود داشته باشند به طوریکه ، ، … و .

پایگاه توالی SDB مجموعه‌ای از چندگانه‌های  است که در آن sid مشخصه یک توالی و s یک توالی است. گفته می‌شود که رکورد  مشتمل بر توالی  است اگر  یک زیرتوالی از s باشد یعنی داشته باشیم .

آستانه زیربری توالی  در پایگاه توالی SDB که با  نشان داده می‌شود تعداد رکوردهایی از پایگاه توالی را نشان می‌دهد که شامل  باشند. یعنی .

به ازای یک مقدار min-sup که توسط کاربر به عنوان آستانه پشتیبانی داده می‌شود، توالی  را یک الگوی توالی در پایگاه توالی SDB می‌نامند اگر حداقل به تعداد min-sup رکورد از SDB شامل  باشند (یعنی داشته باشیم ).

بر اساس یک پایگاه توالی مفروض مانند SDB و یک حد آستانه داده شده مانند min-sup، مساله کاوش الگوهای توالی به معنی یافتن مجموعه همه الگوهای توالی موجود در SDB است.

  • کاوش الگوهای توالی بسته

از آنجا که تعداد زیرتوالی‌های یک توالی دارای مرتبه‌ای نمایی از طول آن توالی است، کاوش الگوهای توالی منجر به ساخت تعداد تعداد فوق العده زیادی زیرتوالی متناوب برای یک الگوی متوالی طولانی خواهد شد. روش ارائه شده برای غلبه بر این مشکل، کاوش الگوهای توالی بسته است. بر اساس تعریف، الگوی توالی بسته به یک الگوی توالی گفته می‌شود که هیچ ابرتوالی از آن موجود نباشد که با آن تعداد تکرار یکسانی (در پایگاه توالی) داشته باشد.

فرض کنید FS مجموعه همه الگوهای توالی و CS مجموعه الگوهای توالی بسته باشد. در این صورت داریم:

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

شکل (۲) مثالی از یک پایگاه توالی را نشان می‌دهد.

این پایگاه دارای سه توالی و ۵ آیتم مجزا است.­ اگر حد آستانه‌ای را ۲ در نظر بگیریم، مجموعه CS شامل ۴ زیرتوالی به صورت  است.

  • الگوریتم‌های سریال برای مساله کاوش الگوهای متناوب در این بخش به توصیف و بررسی

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

  • الگوریتم‌های سریال برای کاوش مجموعه آیتم‌های متناوب

به ازای d آیتم موجود در یک مجموعه داده،  مجموعه آیتم کاندید ممکن وجود خواهد داشت. یک روش سردستی برای یافتن مجموعه آیتم‌های متناوب از میان این  مجموعه آیتم این است که هر یک از این مجموعه آیتم‌ها را با تک تک تراکنش‌های موجود در پایگاه تراکنش مقایسه کنیم و تعداد تراکنش‌هایی را که بر مجموعه آیتم مزبور مشتمل باشند (همه آیتم‌های موجود در مجموعه آیتم مزبور در تراکنش به کار رفته باشند) بشماریم و مجموعه آیتم‌هایی را که تعداد تکرار آنها در پایگاه تراکنش کافی (ازحد آستانه‌ای بیشتر) باشد، مشخص نماییم. بدیهی است که با توجه به مرتبه نمایی تعداد مجموعه آیتم‌ها، و از آنجا که پایگاه‌های تراکنش مورد استفاده ممکن است مشتمل بر میلیون‌ها آیتم باشد، چنین روشی از نظر محاسباتی بسیار زمان‌گیر خواهد بود و نمی‌تواند در بازه قابل قبولی پاسخ را به دست آورد. فضای جستجوی همه مجموعه آیتم‌ها را می‌توان با یک شبکه بندی زیرمجموعه‌ای[۱۲] نشان داد. در این شبکه بندی، مجموعه آیتم تهی در راس این شبکه بندی قرار می‌گیرد و مجموعه آیتمی که شامل همه آیتم‌هاست، در پایین‌ترین سطح است. به عنوان مثال شکل (۲) نشان دهنده شبکه بندی مجموعه‌ای پایگاه تراکنشی است که مشتمل بر ۵ آیتم A، B، C، D و E است.

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

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

  • الگوریتم‌های مبتنی بر جستجوی اول سطح

معروف‌ترین الگوریتم اول سطح، Apriori نام دارد. الگوریتم Apriori به روش زیر عمل می‌کند.

  • پایگاه تراکنش را یک بار پویش کن تا ، یعنی مجموعه همه الگوهای یک آیتمی، را پیدا کن.
  • به ازای  عملیات زیر را تکرار کن:
  •  مجموعه کاندیداهای k آیتمی یعنی  را تولید کن. مجموعه آیتم k-آیتمی X در  خواهد بود. اگر و تنها اگر هر زیرمجموعه k-1 عضوی از X در  باشد.
  •  اگر  است به مرحله ۳ برو.
  •  برای شمارش تعداد هر یک از مجموعه آیتم های موجود در ، پایگاه تراکنش را یک بار پویش کن.
  •  قرار بده :.

    مقدار  را بازگردان.

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

  • تعداد کاندیداهایی که برای یافتن مجموعه آیتم‌های متناوب در این روش ساخته می‌شود، می‌تواند فوق‌العاده زیاد باشد مخصوصا اگر طول مجموعه آیتم‌های متناوب بزرگ باشد. به عنوان مثال برای کاوش الگوی متناوبی با طول ۱۰۰ باید  کاندیدای یک آیتمی،  کاندیدای دو آیتمی و…  کاندیدای صد آیتمی ساخته شود. بنابراین روش فوق در مجموع  کاندیدا تولید می‌نماید. هزینه تولید مزبور، هزینه ذاتی تولید کاندیداها است و به الگوریتمی که آن را پیاده‌سازی می‌کند ربطی ندارد.
  • پویش مکرر پایگاه تراکنش‌ها و چک کردن مجموعه بسیار بزرگی از کاندیداها برای تست انطباق الگوها، بسیار زمان‌گیر است و این موضوع به خصوص در مورد کاوش الگوهای بزرگ صادق است.

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

  • الگوریتم‌های مبتنی بر جستجوی اول عمق

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

 الگوریتم FP-Growth از یک ساختار درختی به نام FP-tree برای ذخیره اطلاعات مرتبط با مجموعه آینم‌های متناوب استفاده می‌کند. هر مسیری که از ریشه این درخت آغاز گردد و به یکی از برگ‌های آن ختم شود، نشان دهنده یکی از تراکنش‌های موجود در پایگاه تراکنش خواهد بود. آیتم‌ها به ترتیب نزولی تعداد تکرارشان در پایگاه تراکنش، در درخت سازمان می‌یابند طوریکه آیتم‌هایی که تعداد تکرارشان بیشتر باشد نزدیک‌تر به ریشه قرار می‌گیرند. FP-tree یک جدول سرآیند دارد که همه آیتم‌های متناوب موجود در پایگاه تراکنش (به همراه تعداد تکرار هر یک) را در خود دارد. این جدول با Header(T) نشان داده می‌شود. هر رکورد موجود در جدول سرآیند نقطه آغاز لیستی است که همه نودهای FP-tree را که حاوی آیتم این رکورد جدول سرآیند هستند را به هم پیوند می‌دهد.

  در اینجا مثالی از نحوه ساخت FP-tree ارائه می‌دهیم و در قالب این مثال به شرح چگونگی و مراحل ساخت FP-tree می‌پردازیم. فرض کنید که شکل (۳) نشان دهنده یک پایگاه تراکنش فرضی باشد و هدف ما یافتن مجموعه آیتم‌هایی است که تعداد تکرار آنها از ۳ بار بیشتر باشد (به بارت دیگر حد آستانه در این مساله برابر ۳ است).

  • ابتدا با یک بار پویش پایگاه تراکنش آیتم‌های متناوب و تعداد تکرار هر یک از آیتم‌های متناوب را مشخص می‌کنیم. برای پایگاه داده مورد نظر در این مثال خواهیم داشت:  که اگر آیتم‌های متناوب را به ترتیب نزولی تعداد تکرار آنها مرتب نماییم حاصل به صورت زیر خواهد بود:

این ترتیب مهم است زیرا شاخه‌های درخت FP-tree نیز همین ترتیب را دنبال خواهند نمود.

  • دومین پویشی که بر روی پایگاه تراکنش انجام می‌شود درخت FP-tree را خواهد ساخت. به ازای هر تراکنش، ابتدا آیتم‌های متناوب موجود در آن تراکنش به ترتیب نزولی تعداد تکرار مرتب می‌شوند (همانطور که در ستون سوم جدول شکل (۳) دیده می‌شود)، و سپس به عنوان یک شاخه به درخت افزوده می‌گردند. به جز زمانی که درخت تهی باشد، در سایر موارد، برای افزودن، مسیر مشترکی از آیتم‌های تراکنش که در درخت موجود است مورد استفاده قرار می‌گیرد و تنها به شمارنده آیتم‌های مسیر مشترک مزبور یکی افزوده می‌گردد. قسمت (الف) از شکل (۴) افزودن ۵ تراکنش شکل (۳)  به یک FP-tree خالی را نمایش می‌دهد.

در خلال افزودن یک تراکنش به FP-tree، هرگاه نود جدیدی ساخته شود، نود مزبور به لیست پیوندی آیتم خود که توسط جدول سرآیند نگهداری می‌شود افزوده می‌گردد. درخت FP-tree کامل ساخته شده از روی پایگاه تراکنش شکل (۳)، در قسمت (ب) از شکل (۴) مشاهده می‌شود.

پس از آنکه FP-tree ساخته شد به روش تقسیم و حل به کاوش آن می‌پردازیم.

اگر  مجموعه‌ای از مجموعه آیتم‌ها و i یک آیتم باشد. عملگر  را اینگونه تعریف می‌کنیم:

کاوش یک درخت FP-tree مانند T با استفاده از الگوریتم FP-Growth را می‌توان به صورت تابع F() با تعریف زیر فرموله کرد که در این فرمول T درخت FP-tree پایگاه تراکنش و P(i,T) نشان دهنده پایگاه داده تصویر شده i باشد.

Function F(T)

begin

if (T is a chain) return set of all combinations of elements in T

else return ;

end;

پایگاه تراکنش تصویر شده P(i,T) شامل تراکنش‌هایی از پایگاه تراکنش اصلی است که i را در خود داشته‌اند. برای قرار گرفتن در P(i,T)، آیتم i و همه آیتم‌هایی که تعداد تکرار آنها از i کمتر باشد از این تراکنش‌ها حذف می‌گردند و آنچه از تراکنش باقی می‌ماند در P(i,T) قرار می‌گیرد. به ازای آیتم i از جدول سرآیند، با تعقیب لیست پیوندی i همه نودهایی از درخت که محتوی i باشند، ملاقات می‌شوند. بنابراین تعقیب شاخه‌ها از نودهای i به سمت ریشه باعث به وجود آمدن پایگاه داده تصویر شده i  می‌گردد. آیتم‌هایی که در پایگاه داده تصویر شده، ظاهر می‌شوند به ترتیب تعداد تکرارشان مرتب شده هستند و به این ترتیب تراکنش‌ها در پایگاه داده تصویر شده نیز با ساختار FP-tree سازمان می‌یابند با این تفاوت که در اینجا آیتم‌های غیرمتناوب حذف شده است. همان حد آستانه‌ای مساله اصلی که توسط کاربر داده شده، به عنوان حد آستانه‌ای پایگاه داده تصویر شده نیز به کار می‌رود. به عنوان مثال اگر بخواهیم پایگاه داده تصویر شده m از مثال قبل را بیابیم، آیتم b در این پایگاه تصویر شده حضور نخواهد داشت زیرا در پایگاه داده تصویر شده m متناوب نیست.

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

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

  • الگوریتم‌های سریال برای کاوش الگوهای توالی

مساله کاوش الگوهای توالی از مساله کاوش مجموعه آیتم‌های متناوب پیچیده‌تر است زیرا آیتم‌های موجود در الگوهای توالی مرتب شده هستند و یک آیتم ممکن است چندین بار (در رویدادهای مختلف) در یک الگوی توالی ظاهر شوند.

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

برای نمونه، اگر مجموعه داده دارای سه آیتم a، b و c باشد، فضای جستجو برای کاوش الگوهای توالی به صورت شبکه‌بندی زیرتوالی نشان داده شده در شکل (۵) خواهد بود.

 هنگامی که از بالای شبکه بندی به سوی پایین حرکت می‌کنیم، طول توالی‌ها در هر سطح یکی افزایش می‌یابد. توالی‌های موجود در سطح L زیرتوالی‌های توالی‌های سطح  L+1 شبکه هستند. آیتم‌های موجود در یک رویداد براساس ترتیب معین و ثابتی ارائه می‌گردند. مثلا در شکل ۵ از ترتیب الفبایی به این منظور استفاده کرده‌ایم.

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

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

الگوریتم GSP از یک رویکرد تولید و تست چندگذری کاندیداها استفاده می‌کند. پویش اول همه توالی‌های متناوب تک آیتمی را می‌یابد. هر گذر بعدی با مجموعه الگوهای توالی یافته شده در گذر قبلی آغاز می‌گردد و توالی های کاندیدای جدید را بر مبنای این اصل که «ابر الگوهای یک الگوی نامتناوب لزوما نامتناوب هستند»، تولید می‌کند. هنگامی که هیچ الگوی توالی جدیدی در یک گذر یافت نشود یا هیچ توالی کاندیدی قابل تولید نباشد، الگوریتم پایان می‌یابد.

الگوریتم PrefixSpan یک الگوریتم جستجوی اول عمق برای کاوش الگوهای توالی است که فلسفه عملکرد آن مشابه الگوریتم FP-Growth برای مجموعه آیتم‌های متناوب می‌باشد. ثابت شده است که PrefixSpan یکی از کارآمدترین الگوریتم ها برای کاوش الگوهای توالی است.

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

در اینجا مثالی برای نشان دادن نحوه عملکرد الگوریتم ارائه می‌دهیم. فرض کنید که می‌خواهیم الگوهای توالی موجود در پایگاه توالی SDB که در شکل (۶)  ارائه شده را بیابیم.

اگر یک رویداد تنها شامل یک آیتم باشد، پرانتزها را حذف می‌کنیم. حد آستانه‌ای نیز ۲ فرض می‌شود.

ابتدا الگوریتم پایگاه توالی‌ها را یکبار پیمایش می‌کند تا آیتم‌های متناوب و تعداد تکرار آنها را بیابد. آیتم‌ها عبارتند از :

سپس پایگاه‌های داده تصویرسازی شده برای ۶ آیتم متناوب پیدا شده مشخص می‌گردد که در شکل (۷) نشان داده شده است.

دو راه برای رشد دادن الگوهای توالی وجود دارد: گسترش میان رویدادی و گسترش درون رویدادی. اولی به گسترش الگوها با افزودن یک آیتم جدید به آخرین رویداد الگوها اشاره دارد در حالیکه دومی به معنای افزودن یک رویداد مجزا که شامل یک تک آیتم جدید است به انتهای الگو می‌باشد. برای آنکه بتوانیم بین دو نوع گسترش یک آیتم i تمایز قائل شویم، از i برای نمایش گسترش درون رویدادی و از _i برای گسترش میان رویدادی استفاده می‌کنیم.

فرض کنید که (E) یک رویداد باشد. عملگر  را تعریف می کنیم:

  •  نشان می‌دهد که i با عنوان رویداد (i) به دنباله (E) اضافه شده است. یعنی .
  •  نشان می‌دهد که i به رویداد (E) اضافه شده است. یعنی .

فرض کنید که S یک توالی، (E)آخرین رویداد توالی S، و S’ پیشوند (E) باشد. در آن صورت داریم:

 و.

به عنوان مثال داریم:

 و  دو الگوی متفاوت هستند که به ترتیب با گسترش میان رویدادی و گسترش درون رویدادی الگوی به دست آمده‌اند.

پایگاه داده تصویر شده SDB بر روی i را با P(i, SDB, Q) نمایش می‌دهیم که در آن Q سرجمع شده پیشوند الگوها است. از آنجا که در ابتدای کار پیشوند الگوها سرجمع نشده‌اند، وقتی SDB کل مجموعه داده باشد (یعنی هیچ پایگاه تصویر شده‌ای از کل مجموعه داده ساخته نشده باشد)، مقدار Q برابر NULL است.

وقتی Q برابر NULL نباشد، در هنگام تصویرسازی نیازمند استفاده از هردو نوع گسترش (میان رویدادی و درون رویدادی) هستیم. فرض کنید PDB یک مجموعه داده، j یک آیتم، و  پیشوند الگوهایی باشد که قبل از ساختن تصویر PDB بر روی j سرجمع شده باشد. فرض کنید که X آخرین رویداد  باشد. به ازای آیتم j، لازم است هر دو تصویرسازی j و _j ساخته شود تا بتوانیم گسترش‌های میان رویدادی و درون رویدادی  را کاوش کنیم.

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

تصویرسازی  نیز مجموعه‌ای از زیرتوالی‌ها است که شامل:

  • زیرتوالی‌های PDB است که نخستین رخداد _j از هر توالی حذف شده باشد.
  • زیرتوالی‌های PDB است که پیشوند قبل از نخستین رخداد  در هرتوالی حذف شده باشد.

به عنوان مثال در پایگاه شکل (۷) تصویر کل مجموعه داده بر روی a به صورت زیر است:

تصویر سازی آیتم b در مجموعه داده  نتایج زیر را در بر دارد:

فرض کنید که S یک توالی و i یک آیتم باشد. عملگر  را تعریف می‌کنیم طوری که  به معنای اتصال i و S باشد به نحوی که i پیشوند باشد. اگر (H) را نخستین رویداد S در نظر بگیریم  به صورت زیر تعریف می‌شود:

  • اگر(H) با «_» شروع شده باشد، i به صورت (iH) با (H) ادغام می‌شود.
  •  اگر(H) با «_» شروع نشده باشد، i به عنوان یک رویداد جدید قبل از (H) اضافه می‌شود.

 مجموعه‌ای از توالی‌ها است. داریم

در PrefixSpan کاوش یک مجموعه داده مانند SDB را می‌توان به صورت تابع (F) با تعریف زیر فرموله کرد.

Function F(SDB, Q)

begin

if (SDB is a set of empty sets) return NULL

else return ;

end;

در حالت کلی پیچیدگی زمانی الگوریتم PrefixSpan در بدترین حالت برابر  است که در آن N تعداد آیتم‌های موجود در مجموعه داده و L طول بزرگترین تراکنش آن است.

  • الگوریتم‌های سریال برای کاوش الگوهای توالی بسته

مجموعه الگوهای توالی بسته، زیرمجموعه‌ای از مجموعه همه الگوهای توالی است مساله کاوش الگوهای توالی بسته از مساله کاوش همه الگوهای توالی پیچیده‌تر است.

دو رویکرد برای کاوش الگوهای توالی بسته وجود دارد.

۱-     یافتن مجموعه کاندیداهای الگوی توالی بسته برای هر الگوی جدید کاوش شده و چک کردن الگوی قبلی یافته شده برای اینکه ببینیم آیا الگوی جدید بسته است یا خیر. الگوریتم سریالی که از این روش استفاده می کند، CloSpan نام دارد.

۲-     یافتن مجموعه نهایی الگوهای توالی بسته با استفاده از روش آزمند. این الگوریتم را BIDE می نامند.

CloSpan از رویکرد نگهداری و تست کاندیداها از میان مجموعه کاندیداهای الگوی توالی بسته است که قبلا کاوش شده است. الگوریتم مزبور از این مجموعه برای هرس کردن فضای جستجو استفاده می کند و چک می کند که آیا الگوی توالی که جدیدا یافته شده بسته است یا خیر. از آنجا که تعداد زیاد الگوهای توالی بسته (یا حتی کاندیداها به تنهایی) فضای حافظه بسیار زیادی اشغال می کنند، استفاده از  CloSpanبرای حدآستانه ای بسیار کوچک یا کاوش توالی های بزرگ، بسیار هزینه بر است. مطالعه کارایی ها نشان می دهد که الگوریتم BIDE کارامدتر از CloSpan است.

BIDE در حقیقت توسعه یافته الگوریتم PrefixSpan است. به ازای هر الگوی توالی یافته شده، الگوریتم BIDE چک می کند که آیا این الگو بسته است یا خیر. این چک کردن توسط یک شمای بستاری انجام می شود. نیازی به نگهداری الگوهای کاندید در این روش وجود ندارد.

نحوه عملکرد الگوریتم BIDE به صورت زیر است:

ابتدا یک پویش بر روی SDB انجام می شود که نتیجه آن یافتن مجموعه توالی های یک آیتمی متناوب است. پس از آن دومین پویش پایگاه های داده تصویر شده برای هر یک از توالی های یک آیتمی متناوب را می سازد. یک پایگاه داده تصویر شده (تصویر) تصویر یک توالی مانند i که به صورت P(i, SDB) نشان داده می شود، مجموعه ای از زیرتوالی ها است که از توالی های مشتمل بر i از SDB تشکیل می شود که پیشوند پیش از نخستین رخداد i آنها حذف شده باشد.

کاوش SDB با BIDE را می توان با تابع F() به صورت زیر تعریف نمود.           

 Function F(SDB, Q)

begin

if (SDB is a set of empty sets) return NULL

else

{

            ;

;

            return(S);

}

end;

در این تابع Freq(SDB) نشان دهنده آیتم های متناوب SDB می باشد. تابع Check(S) توالی هایی از S را باز می گرداند که می تواند چک بستاری توسعه یافته دو سویه را به درستی بگذراند. نتیجه الگوهای توالی بسته متناوب در مجموعه C ذخیره می گردد.

ارتباط و مشاوره با شما ۰۹۳۶۷۹۳۸۰۱۸ در واتس اپ

صفحه اینستاگرام ما را دنبال کنید

دیدگاه‌ها (4)

*
*


پاسخ من را به ایمیلم ارسال کن

    شیما مهمان 19 دی 1396 پاسخ

    سلام و ممنون
    اول جسارتا هیچکدام ازمعادله های ریاضی نشان داده نمیشوند
    دوم سوالی داشتم در مورد الگوهای توالی که آیا میشه با fp tree انها را کاوش نمود؟؟

      مهدي مقيمي مدیر کل 27 دی 1396 پاسخ

      سلام الان باز کردم باز شد

    الهه مهمان 28 آبان 1397 پاسخ

    سلام
    من دانشجو ارشد هستم پایان نامه من برای استخراج الگوهای متناوب از روش اپریوری استفدا کرده برای پیشنهاد و ایده می تونم برای استخراج الگو از hash table استفاده کنم یا از زوش pattern growth
    روشی جدید دیگه های نمی دونم چی می تونم ارائه بدم

      مهدي مقيمي مدیر کل 5 آذر 1397 پاسخ

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

loader
error: با عرض پوزش؛ لطفا از مطالعه مطالب لذت ببرید.