انواع الگوریتم های داده کاوی

الگوریتم    Aprior TID

در این الگوریتم (Agrawal & Srikant ,1994)در ابتدا فضای جستجو پایگاه داده اولیه است که هر تراکنش آن را به عنوان مجموعه ای از مجموعه قلم های تک عضوی می بینیم:

به این معنی که تراکنش ((۱۰۰ l 1,2,3 به صورت (۱۰۰ l{1}{2}{3})در نظر گرفته می شود

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

همانند الگوریتمapriori با استفاده ازعناصر مجموعه آیتمهای ۱عضوی بزرگ، مجموعه آیتمهای دو عضوی را ایجاد می کنیم.(چون هر مجموعه آیتم k عضوی از ترکیب دو مجموعه  k-1 عضوی تشکیل شده است برای شمردن تعداد تکرار یک مجموعه kعضوی در پایگاه می توان در هر تراکنش به دنبال مجموعه آیتمهایk-1 عضوی تولید کننده آن مجموعه آیتم، گشت. یعنی مثلا برای شمردن تکرار مجموعه آیتم {۱,۲,۳}در هر تراکنش باید ببینیم آیا (۱,۲)و(۱,۳)در مجموعه هست یا نه.)

سپس برای هر تراکنش TIDمربوطه را به همراه تمامی مجموعه آیتمهای kعضوی که در تراکنش هست[تولید کننده های k-1عضوی اش در تراکنش هست] به عنوان تراکنش پایگاه جدید اضافه می کنیم.(برای آستفاده مجموعه آیتمهای k+1)                         پایگاه جدید        Ĉk →

وتراکنشهایی که هیچ مجموعه آیتم kعضوی را پوشش ندهند به پایگاه جدید راه پیدا نمی کنند.سپس مجموعه اقلام k+1عضوی را با استفاذه از مجموعه اقلام kعضوی بزرگ ایجاد می کنیم ودر پایگاه داده جدید به دنبال تعداد تکرارهای این مجموعه اقلام می گردیم.[در واقع برای هر مجموعه آیتمk+1عضوی در هر تراکنش جستجو می کنیم ببینیم آیا دو مجموعه kعضوی تولید کننده اش در تراکنش است یا نه.]

سپس TIDاین تراکنش به همراه تمامی  مجموعه آیتمهای k+1عضوی که پوشش میدهد به پایگاه داده جدید دیگری اضافه می کنیم،                                        پایگاه داده جدید     →  Ĉk+1

و این کار را به ازای تمامی تراکنشها تکرار می کنیم.

عملیات بالا را زمانی که پایگاه داده جدید ایجاد شده (Ĉk )تهی نباشد ادامه می دهیم.

 

الگوریتم partition   

این الگوریتم)  Savasere &Navathe & Omiecinski,1995) برای بدست آوردن مجموعه آیتمهای بزرگ از دو قسمت تشکیل شده است. در قسمت اول این الگوریتم پایگاه داده را به چندین بخش مجزا از نظر منطقی تقسیم می کند وهمهً مجموعه آیتمهای بزرگ محلی (مجموعه آیتمهایی که تعداد تکرار آنها از  minsupp  محلی که برای هر بخش در نظر گرفته شده بیشتر است) برای هر بخش بطور مجزا تولید می شود .

سپس در انتهای مرحله یک ، همه مجموعه اقلام بزرگ در هر بخش باهم مجموعه اقلام بزرگ بالقوه در سطح کل پایگاه داده را تشکیل می دهند (مجموعه Σ). درقسمت دوم، پوشش (تعداد تکرار ) هر مجموعه آیتم در مجموعه اقلام بالقوه (Σ) در کل پایگاه داده شمارش می شود و مجموعه اقلام بزرگ واقعی محاسبه می شوند .

توجه: برای هر بخش یک minsupp محلی در نظر گرفته می شود و یک minsupp کلی برای کل پایگاه داده نیز داریم.

نحوه تولید مجموعه اقلام بزرگ در هر بخش به صورت زیر است:

• ابتدا به ازای هر آیتم a در مجموعه I ( آیتم ها ) ، ID تراکنش هایی در بخش مربوطه از DB که شامل آیتم a می باشند را مشخص می کنیم.

 

بخش۲  t(a)={400,500,601}                       بخش۱t(a)={100,300}

 

سپس همانند الگوریتم apriori ، ابتدا مجموعه اقلام یک عضوی بزرگ را ایجاد می کنیم . سپس از روی آنها مجموعه اقلام بزرگ دو عضوی را ایجاد میکنیم و …

با این تفاوت که در این الگوریتم برای محاسبه پوشش (تعداد وقوع ) هر مجموعه آیتم مثل

A={i1,i3,i5}                i1,i3,i5 Î I

تعداد اعضای مجموعه   t(A)=t(i1)Çt(i3)Çt(i5)را می شماریم (به جای خواندن دوبارهDB )، که t(x) مجموعه ID تراکنش های شامل x است (در همان بخش).

پس از اینکه تمام مجموعه اقلام بزرگ(مجموعه اقلامی که تعداد تکرار آنها در این بخش از DB بزرگتر از minsupp محلی است ) را بدست آوردیم همین کار را برای بخش های دیگر تکرار می کنیم .

در صورتیکه مجموعه اقلام بزرگ  برای بخش i را ، åi  بنامیم، مجموعه å به صورت زیر ایجاد می شود:

å=å۱Èå۲È…Èån

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

در صورتیکه پوشش A ازminsup،عمومی بزرگتر باشد .یک مجموعه قلم بزرگ است.

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

 

 الگوریتم های MaxEclat,Eclat

در این الگوریتم ها(Zaki,1997) نیز همانند partition ابتدا مجموعهt(ai) به ازای هر ai متعلق I (مجموعه اقلام کلی)تولید می شود.(t(ai)  شناسه تراکنشهایی را دارد که شامل ai  هستند.)

ولذا پس از ایجاد هر مجموعه آیتم k عضوی (از مجموعه های k-1 عضوی) مثل A={a1,a2,a3} برای محاسبه پوشش A در پایگاه داده تعداد اعضای مجموعه  ∩ t(a2) ∩ t(a3)   t(A)=t(a1) را شمارش می کنیم.

با توجه به اینکه تعداد مقادیر میانی با انجام این کار (اشتراک ها) بسیار زیاد می شود، فضای حافظه اصلی جوابگو نیست و لذا راه حل زیر ارائه شد.

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

در شکل زیر ، زیر شبکه مربوط به آیتم [A] را مشاهده می کنیم که شامل اعضایی است که با A شروع می شوند. به نودهایی که مستقیما‍‌ با [A] در ارتباطند ’اتم’ها می گوییم.

درهرزیرشبکه با داشتن اتمهای مربوطه میتوان استراتژیهای پایین به بالا (partition,apriori ) ویا بالا به پایین را برای جستجوی مجموعه اقلام بزرگ بکار برد.(در شکل جستجوی پایین به بالا را مشاهده می کنیم).

S در الگوریتم فوق مجموعه اتمهای زیر شبکه است و F مجموعه اقلام بزرگ نهایی است و     Tiمجموعه اقلام بزرگ جدید هستند.(یک سطح بالاتر).

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

فریلنسر هستم و مهارت انجام پروژه ای را دارم!

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

نحوه سفارش پروژه در سایت کافه پروژه :

اگر پروژه ای دارید که میخواهید آن را برون سپاری کنید کافی است در سایت کافه پروژه ثبت نام کنید و پروژه خود را ثبت نمایید.پروژه شما هر چه که باشد حتما مجری برای آن وجود دارد.جهت ثبت نام و ثبت سفارش پروژه خود برروی دکمه زیر کلیک نمایید.