عنوان : تحقيق در مورد نگاهي بر داده کاوي و کشف قوانين وابستگي در word
قیمت : 29,400 تومان
توضیحات در پایین همین صفحه

درگاه 1

توجه : دریافت شماره تلفن همراه و آدرس ایمیل صرفا جهت پشتیبانی می باشد و برای تبلیغات استفاده نمی شود

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

توضیحات پروژه

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

 تحقيق در مورد نگاهي بر داده کاوي و کشف قوانين وابستگي در word دارای 25 صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد تحقيق در مورد نگاهي بر داده کاوي و کشف قوانين وابستگي در word  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

این پروژه توسط مرکز مرکز پروژه و مقالات آماده و تنظیم شده است

توجه : در صورت  مشاهده  بهم ريختگي احتمالي در متون زير ،دليل ان کپي کردن اين مطالب از داخل فایل ورد مي باشد و در فايل اصلي تحقيق در مورد نگاهي بر داده کاوي و کشف قوانين وابستگي در word،به هيچ وجه بهم ريختگي وجود ندارد


بخشی از متن تحقيق در مورد نگاهي بر داده کاوي و کشف قوانين وابستگي در word :

(داده كاوی)
تعریف :
Data Mining represents a process developed to examine large amounts of
data routinely collected. The term also refers to a collection of tools used to
perform the process. Data mining is used in most areas where data are
collected-marketing, health, communications, etc.

داده كاوی فرآیند بكارگیری یك یا چند تكنیك آموزش كامپیوتر، برای تحلیل و استخراج داده های یك پایگاه داده می باشد.در واقع هدف داده كاوی یافتن الگوهایی در داده هاست.
دانش كسب شده از فرآیند داده كاوی بصورت مدل یا تعمیمی از داده ها نشان داده می شود.
چندین روش داده كاوی وجود دارد با این وجود همه روشها “ آموزش بر مبنای استنتاج “ را بكار می برند.
آموزش بر مبنای استنتاج، فرآیند شكل گیری تعاریف مفهوم عمومی از طریق مشاهده مثالهای خاص از مفاهیمی كه آموزش داده شده اند، است.

مثال زیر نمونه ای از دانش بدست امده از طریق فرایند اموزش بر مبنای استنتاج است:
آیا تا كنون فكر كرده اید، فروشگاههای بزرگ اینترنتی در mail های خود به مشتریان از چه تبلیغاتی استفاده می كنند؟ و آیا این تبلیغات برای همه مشتریان یكسان است؟
پاسخ این است كه از روی دانش كسب شده از اطلاعات خرید افراد و نتیجه گیری از این دانش، این كار را انجام می دهند.مثلا در نظر بگیرید یك قانون در پایگاه داده بصورت زیر استخراج می شود:
دقت = 80% : سیگار می خرند ^ نان می خرند كسانی كه شیر می خرند

از روی این قانون فروشگاه می تواند به تمام كسانی كه شیر می خرند تبلیغات سیگار و انواع نان را نیز بفرستد.همچنین این قانون در چیدن قفسه های فروشگاه نیز بی تاثیر نخواهد بود.
{شیر و نان و سیگار در قفسه های كنار هم چیده شوند}

كشف دانش در پایگاه داده 1

KDD یا كشف دانش در پایگاه داده اصطلاحی است كه مكررا بجای داده كاوی بكار می رود. از نظر تكنیكی، KDD كاربردی از روشهای علمی داده كاوی است.
بعلاوه برای انجام داده كاوی فرایند KDD شامل :
1- یك روش برای تهیه داده ها و استخراج داده ها ،

2- تصمیم گیری درباره عملی كه پس از داده كاوی باید انجام شود ، می باشد.

آیا داده كاوی برای حل مسائل ما مناسب است؟
تصمیم گیری در مورد اینكه آیا داده كاوی را به عنوان استراتژی حل مساله بكار ببریم یا نه، یك مساله دشوار است.
اما به عنوان نقطه شروع چهار سؤال عمومی را باید در نظر بگیریم :
1 آیا به وضوح می توانیم مساله را تعریف كنیم ؟
2 آیا بطور بالقوه داده با معنی وجود دارد ؟
3 آیا داده ها شامل “ دانش پنهان” هستند یا فقط برای هدف گزارشگری مناسبند ؟
4 آیا هزینه پردازش داده (برای داده كاوی) كمتر از سود حاصل از دانش پنهان بدست آمده از پروژه داده كاوی است ؟

یك مدل پردازش داده كاوی ساده :
در یك دید كلی ، ما می توانیم داده كاوی را به عنوان یك فرآیند چهار مرحله ای تعریف كنیم :
1 جمع آوری یك مجموعه از داده ها برای تحلیل
2 ارائه این داده ها به برنامه نرم افزاری داده كاوی
3 تفسیر نتایج

4 بكارگیری نتایج برای مساله یا موقعیتهای جدید

شكل فوق یك دیاگرام از فرآیند داده كاوی را نشان می دهد.

– جمع آوری داده ها :
فرآیند داده كاوی احتیاج به دسترسی به داده ها دارد. داده ممكن است در تعدادی ركورد، در چندین فایل پایگاه داده ذخیره شود و یا ممكن است داده فقط شامل چند صد ركورد در یك فایل ساده باشد.

با توجه به اینكه معمولا داده های واقعی شامل چندین هزار ركورد می باشند، اولین گام در داده كاوی تهیه زیر مجموعه مناسبی از داده برای پردازش است. گاهی این مرحله احتیاج به تلاش انسانهای بسیاری دارد. در كل سه راه متداول برای دستیابی فرآیند داده كاوی به داده وجود دارد :
1 ذخیره داده در “ انبار داده 1 ”
2 ذخیره داده در پایگاه داده رابطه ای
3 ذخیره داده در فایل ساده

– داده كاوی :
همانطور كه در شكل مشخص است مرحله بعد داده كاوی است. با این حال قبل از ارائه داده به ابزار داده كاوی ، چندین انتخاب داریم:
1 یادگیری باید تحت كنترل باشد یا بدون كنترل ؟
2 كدام نمونه ها در داده ها ی جمع آوری شده برای ساخت مدل بكار میروند و كدامها برای تست مدل ؟

3 كدام صفتها از صفتهای موجود انتخاب می شوند ؟
و ;.

– تفسیر نتایج :
در این مرحله خروجیهای مرحله داده كاوی آزمایش می شوند تا مشخص شود كه آیا این نتایج قابل استفاده و جالب هستند یا نه؟ همانطور كه در شكل می بینیم اگر نتایج بهینه نباشد می توانیم فرآیند داده كاوی را با صفات و نمونه های جدید تكرار كنیم. همچنین ما می توانیم به” انبار داده “ مراجعه كنیم و فرآیند استخراج دانش را تكرار كنیم.

ـ بكارگیری نتایج :
هدف نهایی ما بكارگیری نتایج برای موقعیتهای جدید است. به عنوان مثال دانشی كه در یك پایگاه داده فروشگاه بیان می كند كسانی كه مجله ورزشی می خرند همچنین سیگار هم می خرند؛ در شكل گیری استراتژیهای فروشگاه در چیدن قفسه ها ، تهیه كاتالوگ ها و ; تاثیر می گذارد.

استراتژیهای داده كاوی :
همانطور كه در شكل زیر می بینیم استراتژیهای داده كاوی بطور كلی می توانند به دو دسته “ تحت كنترل ” یا “ بدون كنترل ” تقسیم می شوند. آموزش تحت كنترل مدلهایی را با بكارگیری صفات ورودی برای تشخیص مقدار صفت خروجی می سازد. حتی برخی از الگوریتمهای ” آموزش تحت كنترل” امكان تشخیص چندین صفت خروجی را به ما می دهند. به صفات خروجی ، صفات وابسته نیز
می گوییم. زیرا مقدار آنها به مقدار یك یا چند صفت ورودی بستگی دارد. به همین ترتیب به صفات ورودی، صفات مستقل نیز می گوییم.
هنگامی كه “ آموزش بدون كنترل ” را بكار می بریم تمامی صفات ورودی هستند و صفت خروجی نداریم.
آموزش تحت كنترل با توجه به اینكه صفات خروجی مقوله ای هستند یا عددی و آیا مدلهای ایجاد شده برای مشخص كردن موقعیت كنونی ایجاد شدند یا پیش بینی خروجیهای آینده ، به چندین قسمت تقسیم می شوند. (منظور از صفات مقوله ای ، صفاتی هستند كه مقدار آنها تعداد محدود و مشخصی است، مثل صفاتی كه مقدار آنها Boolean است كه دو مقدار {true, false} دارد).

طبقه بندی1 :
طبقه بندی احتمالا از همه استراتژیهای داده كاوی قابل درك تر است. طبقه بندی سه خصوصیت دارد :
1 آموزش تحت كنترل است.
2 متغیر وابسته ، مقوله ای است.
3 تاكید بر روی ساخت مدلهایی است كه قادر به اختصاص نمونه های جدید به یكی از كلاسهای تعریف شده باشند.

تخمین2 :
مشابه طبقه بندی ، هدف یك مدل تخمین نیز مشخص كردن مقدار برای یك صفت خروجی است؛ اما بر خلاف طبقه بندی صفات خروجی برای مساله تخمین، عددی است بجای مقوله ای .
بعنوان یك مثال برای تخمین ، پایگاه داده ای را در نظر بگیرید كه هر ركورد آن اطلاعاتی را راجع به شخصی دارد مثل : محل زندگی، غذای روزانه در اغلب روزها، نوع ماشین شخصی ، درآمد ماهانه و ;.
هدف الگوریتم تخمین در این مثال ایجاد مدلی برای تشخیص درآمد ماهانه نمونه های جدید (ركوردهای جدید) می باشد.{كه بقیه صفات آنها بجز درآمد ماهانه مشخص است}.
بیشترتكنیكهای تحت كنترل قادرند كه یا مسائل طبقه بندی را حل كنند یا تخمین ، اما نه هردورا.

پیش گویی Perdiction :
تشخیص تفاوت بین پیش گویی و طبقه بند ی یا تخمین كار ساده ای نیست. با این حال هدف یك مدل پیش گویی ، برخلاف طبقه بندی یا تخمین، بجای مشخص كردن رفتار كنونی، مشخص كردن خروجیهای آینده است. بیشتر روشهای داده كاوی كه برای طبقه بندی یا تخمین مناسبند، برای ساخت مدلهای پیش گویی نیز بكار میروند. عملا این طبیعت داده است كه مشخص می كند یك مدل برای تخمین مناست است یا طبقه بندی ویا پیش گویی.

:Unsupervised Clustering دسته بندی بدون كنترل
در دسته بندی بدون كنترل، ما دیگر صفات خروجی نداریم كه ما را در فرآیند یادگیری راهنمایی كند، در عوض برنامه مربوطه ساختارهای دانش را با بكارگیری معیارهای “ كیفیت دسته” برای گروه بندی داده ها به دو یا چند كلاس (دسته)، بدست می آورد.

.
یك هدف اساسی دسته بندی بدون كنترل، كشف ساختارهای مفهومی در داده است.
كاربردهای متداول دسته بندی بدون نظارت عبارتند از :
– مشخص می كند كه آیا ارتباطات با معنی در شكل مفاهیم می تواند در داده ما پیدا شود یا نه ؟
– كارآیی روش آموزش تحت كنترل را مشخص می كند.
– بهترین صفات ورودی برای آموزش تحت كنترل را مشخص می كند.
– شناسایی از حد خارج شده ها (outlier)

تحلیل سبد بازاری Market Basket Analyse :
هدف این مرحله پیدا كردن ارتباطات جالب میان محصولات (خرده فروشی) است. خروجی این مرحله به فروشندگان كمك می كند تا بهتر بتوانند قفسه ها را بچینند یا كاتالوگها را تنظیم كنندو نیز در ایجاد استراتژیهای فروشگاه نیز كارا است. مثالی از دانش این مرحله به فرم زیر است (در یك فروشگاه)
سیگار می خرند كسانی كه قهوه می خرند

:Supervised Data Mining تكنیكهای داده كاوی تحت كنترل
تكنیكهای داده كاوی برای بكارگیری استراتژی داده كاوی برای یك مجموعه داده بكار می رود. یك تكنیك داده كاوی از دو قسمت تشكیل شده است:
1 الگوریتم.
2 ساختار دانش مربوطه مثل درخت یا یك مجموعه قوانین درخت تصمیم كه در قسمتهای قبلی توضیح دادیم.
در اینجا چندین روش دیگر برای داده كاوی نظارت شده ارائه می دهیم :

1 شبكه عصبی :
یك شبكه عصبی مجموعه ای از نودهای به هم پیوسته است كه طراحی می شوند تا رفتار مغز انسان را شبیه سازی كنند.
چون مغز انسان از بیلیونها عصب تشكیل شده و شبكه های عصبی كمتر از صد نود دارند مقایسه یك شبكه عصبی و رفتار مغز كمی غیر متعارف است. با این وجود شبكه های عصبی با موفقیت ، برای حل مسائل بكار برده می شوندو برای داده كاوی نیز كاملا ابزار مناسبی است .

شبكه های عصبی در شكلها و فرمهای گوناگونی وجود دارند و هم برای آموزش تحت كنترل و هم دسته بندی بدون كنترل بكار می روند. درهمه موارد ، مقادیر ورودی برای شبكه عصبی باید عددی باشند. شبكه feed-forward یك نوع شبكه عصبی مناسب برای مسائل آموزش تحت كنترل می باشد.

2 برگشت آماری1 :
برگشت آماری یكی از روشهای آموزش تحت كنترل است كه یك مجموعه از داده های عددی را توسط ایجاد معادلات ریاضی مرتبط با یك یا چند صفت ورودی به یك صفت خروجی عددی نسبت
می دهد.
یك مدل “ برگشت خطی ” توسط یك صفت خروجی كه مقدارش بوسیله :
“ جمع مقادیر صفت های ورودی × یك وزن مشخص “ مشخص می شود.
مثلا اگر یك پایگاه داده شامل صفات ورودی A , B, C , D و صفت خروجی E باشد، رابطه زیر
می تواند یك مدل برگشت خطی باشد :
E = 0.5 C – 02 B + A + 0.32
میبینیم كه E صفت خروجی است كه مقدارش توسط تركیب خطی صفات A , B , C تعیین می گردد.
همانند شبكه عصبی ، در این روش نیز همه ورودیها باید عددی باشند و در صورتیكه داده ها در پایگاه داده مقوله ای باشند باید آنها را به داده های عددی تبدیل كنیم.

3 قوانین وابستگی2 :
به تفصیل در بخشهای بعد مورد بحث قرار می گیرد.
قوانین پیوستگی:
یکی از مهمترین بخشهای داده کاوی، کشف قوانین وابستگی در پایگاه داده است.این قوانین، لزوم وقوع برخی صفات(آیتم ها) را در صورت وقوع برخی دیگر از آیتمها، تضمین می کند.
برای روشن شدن مطلب یک فروشگاه خرده فروشی را در نظر بگیرید. مشخصات اجناس خریده شده توسط هر مشتری در یک رکورد پایگاه داده ذخیره می شود.به هر رکورد یک شناسه (TID) نسبت داده می شود.فرض کنید که مجموعه I شامل تمام آیتمها(اجناس) فروشگاه باشد.

اگر I x,y و xy= آنگاه x=>y یک قانون وابستگی است که بیان میکند اگریک مشتری اجناس مجموعه x را بخرد، اجناس مجموعه y را هم می خرد. این چنین قوانین، تأثیر مهمی در تایین استراتژیهای فروش، بخش بندی مشتریان، تنظیم کاتالوگها و; دارد. همچنین کشف قوانین وابستگی، کاربردهای بسیاری در علوم مختلف نیز دارد.
تعریف مسأله:
مجموعه آیتم: به هر زیر مجموعه از مجموعه آیتمها I)) ‘ یک مجموعه آیتم ‘ میگوییم.
در بیشتر الگوریتمها مساله کشف قوانین پیوستگی به دو زیر مساله تقسیم می شود:
1پیدا کردن تمامی زیر مجموعه های مجموعه I [مجموعه آیتمها] که تکرار (وقوع) آنها در پایگاه بیشتر از یک حد تایین شده است.

به مجموعه آیتمهایی که تعداد وقوع آنها در پایگاه بزرگتر(یا مساوی)حد تایین شده است
‘ مجموعه آیتمهای بزرگ’، وبه بقیه’ مجموعه آیتمهای کوچک’ می گوییم.
2بکارگیری مجموعه آیتمهای بزرگ برای تولید قوانین مطلوب.
تعریف:
پوشش2: مجموعه I شامل تمام آیتمها و مجموعه آیتم x را در نظر بگیرید ، می گوییم پوشش x در پایگاه داده برابر است با اگر و فقط اگر تعداد وقوع مجموعه آیتم x در پایگاه داده برابر با باشد.
Support(x)=
درجه اطمینان:3 مجموعه I شامل تمامی اقلام و مجموعه آیتمهای x و y مفروضند. درجه اطمینان قانون x=>yبرابر است با : xy=

Conf(x=>y) = support(xUy) support(x)
الگوریتم : Apriori این الگوریتم(Agrawal & Srikant ,1994) برای تولید مجموعه اقلام بزرگ به این ترتیب عمل می کند:
ابتدا با یک دور خواندن پایگاه داده مجموعه اقلام بزرگ یک عضوی ((1-itemsetرا مشخص می کنیم.[مجموعه اقلام 1 عضوی که تعداد تکرار آنها در DB از حد تایین شده(minsup) بیشتر است.]
سپس با استفاده ازمجموعه اقلام بزرگ یک عضوی، مجموعه اقلام دو عضوی را ایجاد می کنیم و برای تایین پوشش مجموعه اقلام دو عضوی یک بار دیگر کل پایگاه داده را می خوانیم تا مجموعه اقلام بزرگ دو عضوی را تایین کنیم.

به همین ترتیب با استفاده از مجموعه اقلام بزرگ دو عضوی مجموعه اقلام سه عضوی را ایجاد کرده و با خواندن دوباره پایگاه داده پوشش هر مجموعه قلم سه عضوی را مشخص کرده و مجموعه اقلام بزرگ سه عضوی تولید می شوند و این کار را برای مجموعه های 4عضوی و ; انجام میدهیم تا مرحله ای که هیچ مجموعه آیتم بزر الگوریتم:
L1= { larg-1-itemset }
for ( k=2; Lk-1 0;k+1 ) do
begin
C k=apriori – gen(Lk-1 ) //عضوی k عضوی با استفاده از اقلام بزرگ1-k ساخت زیر مجموعه های
for all transaction lD do
begin
C t=subset(Ck,l); // رخ دادند. عضوی در تراکنش k تست اینکها کدام مجموعه آیتمهای
for all candidate cCt do
c.count++;
end
Lk={ cCk l c.count minsup}
end;
Answer=Uk Lk

(تبصره : اگر یک مجموعه آیتم بزرگ باشد[تکرارش درپایگاه داده بیشتر از minsupباشد] تمامی زیرمجموعه های آن نیز بزرگ هستند.)
چون هدف، تولید مجموعه اقلام بزرگ است، در الگوریتم aprioriدر هر مرحله پس از ایجاد مجموعه اقلامk عضوی از مجموعه اقلام بزرگ k-1 عضوی قبل از خواندن پایگاه داده برای تشخیص پوشش مجموعه اقلام k عضوی،

ابتدا باید برای هر مجموعه قلم ببینبم آیا زیر مجموعه k-1 عضوی اش بزرگ هستند یا نه، اگر حتی یک زیر مجموعه k-1 عضوی اش هم بزرگ نباشد، آن مجموعه قلم k عضوی نمی تواند بزرگ باشد.(طبق قضیه) و آن را حذف می کنیم.
برای روشن تر شدن الگوریتم به مثال زیر توجه کنید:

minsup=3 Database:
Items TID
1 3 4 5 100
2 3 5 200
1 2 3 5 300
2 5 400
1 3 4 5 500

گام1:ایجاد مجموعه اقلام 1 عضوی:
L 1مجموعه آیتمهای بزرگ: مجموعه آیتمهای 1 عضوی:
{1}=3 {1}=3
{2}=3 {2}=3
{3}=4 {3}=4
{5}=5 {4}=2
{5}=4
گام2: ایجاد مجموعه آیتمهای دو عضوی با استفاده از مجموعه آیتمهای بزرگ 1 عضوی:
L2مجموعه آیتمهای بزرگ دو عضوی: مجموعه آیتمهای 2 عضوی:
{1,3}=3 {1,2}=1
{2,5}=3 {1,3}=3
{3,5}=3 {1,5}=3
{1,5}=3 {2,3}=2
{2,5}=3
{3,5}=4
گام3:ایجاد مجموعه آیتمهای سه عضوی با استفاده از مجموعه آیتمهای بزرگ دو عضوی:
مجموعه آیتمهای بزرگ سه عضوی: مجموعه آیتمهای 3عضوی:L3
{1,3,5}=3 {1,3,5}=3

Answer=L1 U L2 U L3={{1} {2} {3} {5} {1,3} {2,5} {3,5} {1,5} {1,3,5}}

الگوریتم : 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 كلی برای كل پایگاه داده نیز داریم.
نحوه تولید مجموعه اقلام بزرگ در هر بخش به صورت زیر است:

1- ابتدا به ازای هر آیتم 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 بنامیم، مجموعه به صورت زیر ایجاد می شود:
=12…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مجموعه اقلام بزرگ جدید هستند.(یك سطح بالاتر).

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

بجز روش بالا به پایین و پایین به بالا روش دیگری به نام hybrid كه تركیب دو روش بالا به پایین و پایین به بالا می باشد نیز وجود دارد كه این روش را در شكل زیر نشان دادیم.

برای دریافت پروژه اینجا کلیک کنید


دانلود تحقيق در مورد نگاهي بر داده کاوي و کشف قوانين وابستگي در word
قیمت : 29,400 تومان

درگاه 1

Copyright © 2014 icbc.ir