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

الگوریتم با ساختار 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 ) بیشتر نخواهد بود,لذا برای هر تراکنش فقط زیر مجموعه های ۱ تا M عضوی را تولید وبه درخت اضافه می کنیم.

 

الگوریتم fp-grow

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

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

تعریف:

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

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

الف: نام آیتم: آ یتمی که نود مشخص می کند.

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

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

۳ _ هر ورودی در جدول سرایند از دو فیلد تشکیل شده:

۱-نام آیتم                   ۲- اشاره گری به اولین نود حامل آیتم

 

ساخت fp- tree :

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

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

 

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

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

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

الگوریتم :

۱- یکبار پایگاه داده را بخوانید.مجموعه 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 برای جدول ۲ رسم شده است و header table نیز آدرس اولین نود را برای هر آیتم بزرگ را دارد.

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

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

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

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

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