الگوی الگوریتم های شرطی داده کاوی

الگوي شرطي:

براي روشن مفهوم فوق (الگوي شرطي) شكل را در نظر بگيريد.آيتم p را در نظر بگيريد.مطابق شكل شاخه هاي  پيشوند هاي p در درخت عبارتند از <f:4,c:3,a:3,m:2> و زير شاخه. <c:1,b:1> به اين معني كه مجموعه آيتم هاي پيشوندي در پايگاه داده عبارتند از <c:1,b:1>,<f:2,c:2,a:2,m:2> كه به اين دو الگوي هاي شرطي ميگوييم.

 

  Fp-tree شرطي :

در صورتيكه با الگوهاي شرطي, از نو يك fp-tree درست كنيم و نود مربوط به  آيتم هايي كه تعداد تكرار كمتر از   دارند  را حذف كنيم, درخت حاصل fp-tree  شرطي ناميده ميشود.و به صورت(fp-tree|p) نمايش داده مي شود ) كه p آيتم مربوطه است)

(fp-tree|m) در شكل زير مشخص است.

الگوريتم ايجاد مجموعه آيتم هاي بزرگ بوسيله درخت fp-tree

روش كار به اين صورت است كه ابتدا به ازاي هر آيتم بزرگ مثل {a} كارهاي زير را تكرار مي كنيم :

1-     temp =λ

2-اگر  , aÈtemp را به مجموعه آيتم هاي بزرگ اضافه كن

T1=(fp-tree|a) را در درخت ايجاد ميكنيم و (temp=a).

دوباره درداخل اين  fp-treeجديد(T1)  به ازاي هرآيتم بزرگ دراين  fp-treeمثل a’ در صورتيكه  (تكراردردرخت T1)}È temp, ‌  {a’ به مجموعه آيتم هاي بزرگ اضافه مي شودو دوباره همين كار را براي ( T2 =(T1|a’ حاصل از درخت T1 تكرار مي كنيم.

(مقدار  temp قبل از فراخواني تابع (T1|a’) برابرست با : temp=a’ È temp’)

الگوريتم برداري

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

لذا  دسترسی مجدد به پايگاه داده اوليه  نیازی نیست و محاسبات نیز بسیار سریعتر از الگوریتمهای قبل می‌باشد.

   الگوریتم ارائه شده:

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

(بردار فشرده‌ی یک آیتم مشخص می‌کند که این آیتم در کدام تراکنش‌ها رخ داده است)

در الگوریتم(Tseng,2000) دو پایگاه داده داریم بنامهای Support DB  و feature DB:

feature DB  : بردارهای مربوط به آیتم‌ها را مشخص می‌کند. (هرخانه آن بردار مربوط به یک آیتم است)

Support DB: پوشش هر آیتم را در بر دارد.

هنگامی که کاربر یک تقاضا مبتنی بر کشف قوانین وابستگی بین آیتمهای IT (که ) با حداقل پوشش minsupp و حداقل درجه اطمینان minconf می دهد، در این روش ابتدا چک می‌کنیم ببینیم ,   آیا     feature   DB  , Support DB وجود دارند یا نه در صورتیکه وجود نداشته باشند

آن ها را می‌سازد. ساخت feature DB  ,  Support DB احتیاج به یک دور خواندن کل پایگاه داده دارد.

در طول خواندن پایگاه داده، Feature DB ، Support DB برای آیتمهای مشخص شده توسط کاربر نیز ساخته می‌شود. پس از اینکه Feature DB Support DB, ساخته شدند در ديسك

مي گيرند.

لذا , را نيز با دسترسی مستقیم به Support DB مشخص کنیم , بجای خواندن کل پایگاه داده.

پس از مشخص شدن ، بردار هر مجموعه آیتم مورد نیاز نیز با عملیات AND به سرعت انجام می‌شود.

1) IF (SupportDB is empty)

Scan the database to build SupportDB and determine , and build Feature DB for interested items;

ELSE

Retrieve SupportDB and determine and build FeatureDB for non-existent items;

2) k=2

3) Generate candidate large itemsetfrom;

4) IF  is not empty

Optain the count for each itemset in   by bitwise AND operators on the  items’ feature vectors and get;

go to step 3;

5) Answer= union of all;

مرحله ساخت بردار  برای آیتم d به صورت زیر است:

بردار یک بردار است به طول تعداد تراکنشهای پایگاه داده. در صورتیکه آیتم d در یک تراکنش با شناسه‌ی j باشددر غیر اینصورت . (فرض بر این است که شناسه‌ها در پایگاه داده از 1 تا1-  nطول پایگاه داده” است) مثلاً اگرآیتم a در یک پایگاه داده‌ی 10 عضوی فقط در رکوردهای 10,5,4 رخ دهد, داریم:

 

1	2	3	4	5	6	7	8	9	10
0	0	0	1	1	0	0	0	0	1

 

به این ترتیب با داشتن بردار هر آیتم برای مشخص کردن بردار هر مجموعه آیتم مثل  داریم :

بدیهی است که تعداد 1 ها در بردار هر مجموعه آیتم برابر پوشش آن مجموعه آیتم است.

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

واضح است که در یک بردار مقادیر زیادی صفر وجود دارد که فضای زیادی را اشغال می‌کنند. برای رفع این مشکل می‌توان در صورتیکه چندین (بیشتر از 8) 0 پشت سر هم وجود داشت تعداد آنها را بشماریم و در یک index ِ شمارنده ذخیره کنیم. با ذخیره بردار هر آیتم دسترسی به پایگاه داده به حداقل می‌رسد.

یک راه حل دیگر اینست که برای هر آیتم فقط شماره رکوردهایی را که آیتم در آنها رخ داده را ذخیره کنیم یعنی به عنوان مثال اگر آیتم a در رکوردهای شماره  220,201,100 رخ داده بردار آن به شکل زیر است:

در اینصورت برای هر مجموعه آیتم X بردار به شکل زیر است:

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

و تنها برای محاسبه‌ی بردارهای هر آیتم, پایگاه داده را در ابتداي كار يك دور می‌زنیم.

يك الگوريتم جديد براي پايگاه داده هاي پويا

پویایی پایگاه داده را از دو جنبه می توان بررسی کرد :

1. هنگامی که داده ها تغییر کنند (یک رکورد تغییر کند) یا داده ها از پایگاه داده حذف شوند .
2. هنگامی که داده ای ( رکورد جدید ) به پایگاه داده اضافه شود .

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

الگوریتم    Zhang &Etal,2003)  )    از نوع الگوریتم کاهشی است . یعنی ورودی را بررسی میکنیم که میخواهیم داده کاوی را در یک پایگاه داده که داده هایش دائما حذف  شده و یا تغییر کرده اند انجام میدهیم و قاعدتا انتظار داریم که الگوریتم در فواصل مختلف زمانی که پایگاه داده مورد تغییر (یا حذف)  قرار می گیرد با بکارگیری الگوهای حاصل از داده کاوی قبلی از هزینه زمانی خوبی برخوردار باشد .

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

لذا کاربر باید دوباره الگوریتم داده کاوی را برای پایگاه داده جدید با تولید تمام الگوها از اول بکار گیرد که این کار بسیار پر هزینه است .

–1آیتم هایی که توسط کاربر مشخص می شود.

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

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

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

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

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