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

الگوریتم    Aprior TID

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

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

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

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

سپس برای هر تراکنش 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 مي باشند را مشخص مي كنيم.

 

بخش2  t(a)={400,500,601}                       بخش1t(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  بناميم، مجموعه å به صورت زير ايجاد مي شود:

å=å1Èå2È…Èå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مجموعه اقلام بزرگ جديد هستند.(يك سطح بالاتر).

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

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

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

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

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