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

الگوريتم با ساختار trie

در اين الگوريتم(Amir & Feldman & Kashi,1998) از يك ساختار داده بنام trie  براي توليد مجموعه اقلام بزرگ استفاده مي كنيم . به كار گيري اين ساختارها  ما را قادر مي سازد تا مجموعه اقلام بزرگ را به طور كارا توليد كنيم.( حتي با وجود minsupp هاي بسيار كوچك) رشته S=S[1]…S [n] را در نظر بگيريد براي افزودن اين رشته به درخت trie ابتدا از ريشه درخت trie شروع مي كنيم (current-node= root) و نگاه مي كنيم , بينيم آيا يالي از

current-node با بر ‌چسپ S [1] وجود دارد يا خير .

اگر چنين يالي وجود داشت , از طريق آن يال به نود فرزند مي رويم و ) نود فرزند=(current node سپس دوباره اعمال بالا را براي current-node جديد و كاراكتر بعدي (S[2]) تكرار مي كنيم.

در غير اين صورت ( يالي با بر چسب S[1]  وجود نداشت ) , يالي با برچسب S[1]  از current-node   ايجاد مي كنيم و فرزند ايجاد شده از طريق اين يال , current-node   مرحله بعدي است .

حال بايد كار را براي S[2]  و current-node   جديد تكرار كنيم .

اين كار را آنقدر تكراركنيم تا رشته تمام شود, در صورتيكه تمام رشته را چك كرديم و كار را براي S[n]  و current-node مربو طه اش چك كرديم شمارنده مربوط به نود فرزند

( Currentنود آخر از طريق يال S[n]  )  رامي افزاييم.

 

الگوريتم مربوطه:

در اين الگوريتم فقط يك دور پايگاه داده را مي خوانيم و به ازاي هر تراكنش مثل  ,T تمام زير مجموعه هاي T  را به درخت (trie)   مي افزاييم .

مثلا براي ‍{1,2,5}  زير مجموعه هاي ‍{1,2,5},{2,5},{1,5},{1,2},{5},{2},{1} يكي يكي به درخت trie افزوده مي شوند.

در نهايت شمارنده مربوطه به هر نود در درخت (trie) تعداد وقوع مجموعه آيتم نود مربوطه را در بر دارد.

 

نكته :اين الگوريتم براي حالات خاصي كه طول هر تراكنش بسيار كم است در نظر گرفته شده است و در هنگامي كه طول تراكنش ها كم باشد , مي توان نتيجه گرفت كه طول مجموعه اقلام بزرگ نيز از يك حدي

( طول M ) بيشتر نخواهد بود,لذا براي هر تراكنش فقط زير مجموعه هاي 1 تا M عضوي را توليد وبه درخت اضافه مي كنيم.

 

الگوريتم fp-grow

در اين الگوريتم (Han &Pei &Yin,2000)با استفاده از ساختاري فشرده به نام

frequent pattern tree(fp-tree) كل فضاي پايگاه داده را به فضاي كمي در حافظه اصلي نگاشت مي كنيم و موقع شمردن پوشش مجموعه آيتم ها درپايگاه داده از fp- tree  استفاده مي كنيم.به اين ترتيب زمان ناشي از خواندن پايگاه داده (DB) در دفعات كاهش مي يابد.

تعريف:

1_ يك fp- tree يك درخت است كه ريشه آن null است و يك مجموعه از زير درخت هاي پيشوندي آيتم به عنوان فرزندان ريشه هستند, يك جدول سرايند آيتم هاي بزرگ هم وجود دارد.

2_هر نود در درخت   fp- tree شامل سه مولفه است:

الف: نام آيتم: آ يتمي كه نود مشخص مي كند.

ب: تعداد : تعداد تراكنش در پايگاه داده, كه شامل بخشي  از شاخه درخت از ريشه تا آن نود هستند.

ج: link : اشاره گري به نود بعدي در درخت كه شامل همين آيتم است , يا مقدارnull دارد.

3 _ هر ورودي در جدول سرايند از دو فيلد تشكيل شده:

1-نام آيتم                   2- اشاره گري به اولين نود حامل آيتم

 

ساخت fp- tree :

براي ساخت fp tree  ازپايگاه داده , ابتدا يك دور پايگاه داده را مي خوانيم تا پوشش هر آيتم مشخص شود . . (Supp (a))

سپس قبل از افزودن هر تراكنش به درخت fp tree , مجموعه آيتم هاي آن تراكنش را, ابتدا بر اساس supp  (پوشش) مرتب مي كنيم و سپس به درخت مي افزاييم.

 

الگوريتم ساخت fp- tree  

ورودي : يك پايگاه داده شامل تراكنش ها و يك حد مينيمم براي پوشش )(

خروجي : درخت fp tree مربوطه.

الگوريتم :

1- يكبار پايگاه داده را بخوانيد.مجموعه F شامل آيتم هاي بزرگ( با تكرار كافي در پايگاه داده) و پوشش هر يك را بدست آوريد.سپس F مرتب كنيد و L بناميد.

2_ ريشه fp-tree (T)را null بگذاريد و براي هر تراكنش در پايگاه داده , به ترتيب زير عمل كنيد:

ابتدا آيتم هاي بزرگ در تراكنش را انتخاب نماييد و مطابق مجموعه L مرتب كنيد( به ترتيب پوشش) فرض كنيد مجموعه آيتم هاي بزرگ مرتب شده  حاصل از اين تراكنش به صورت [p|P] كه p اولين آيتم در اين مجموعه است و P بقيه آيتم هاست , تابع  insert tree ( [p|P] ,T) را فراخواني كنيد.

اين تابع به شكل زير كار ميكند كه اگر T فرزندي مثل N دارد كه

N.itemname=p.itemname  آنگاه شمارنده (count)   نود N يكي افزايش مي يابد و گرنه يك نود جديد N مي سازيم و شما رنده آن را يك مي كنيم .

Link پدربراي اين نود به T اشاره مي كندو node-link اين نود به نودي با همين item-name

در همين درخت اشاره مي كندو اگر P تهي نيست insert-tree(P,N) را فراخواني كنيد.

شكل صفحه  بعد مثالي را نشان مي دهد كه fp tree براي جدول 2 رسم شده است و header table نيز آدرس اولين نود را براي هر آيتم بزرگ را دارد.

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

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

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

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

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