وابستگی
چکیده:
با افزایش سیستمهای کامپیوتر و گسترش تکنولوژی اطلاعات , بحث اصلی در علم کامپیوتر از چگونگی جمع آوری اطلاعات به نحوه استفاده از اطلاعات منتقل شده است . سیستمهای داده کاوی ,این امکان را به کاربر می دهند که بتواند انبوه داده های جمع آوری شده را تفسیر کنند و دانش نهفته در آن را استخراج نمایند .
داده کاوی به هر نوع کشف دانش و یا الگوی پنهان در پایگاه داده ها اطلاق می شود . امروزه داده کاوی به عنوان یکی از مهمترین مسائل هوش مصنوعی و پایگاه داده ، محققان بسیاری را به خود جذب کرده است . در این تحقیق ابتدا نگاه کلی بر داده کاوی ، استراتژیهای داده کاوی و... داریم ، سپس مسأله کشف قوانین وابستگی در پایگاه داده را به تفضیل بررسی کردیم و نگاهی به الگوریتمهای موجود برای آن داشتیم . سپس مسأله کشف قوانین وابستگی در پایگاه داده های پویا را مورد بحث قرار دادیم و الگوریتم های ارائه شده مربوطه را مطرح کردیم .
مقدمه :
هدف از این اراِئه و تحقیق بررسی روشهای مطرح داده کاوی است .داده کاوی هر نوع استخراج دانش و یا الگواز داده های موجود در پایگاه داده است که این دانشها و الگوها ضمنی و مستتر در داده ها هستند ,از داده کاوی می توان جهت امور رده بندی (Classification ) و تخمین (Estimation) ,پیش بینی (Prediction) و خوشه بندی (Clustering)استفاده کرد .داده کاوی دارای محاسن فراوانی است . از مهمترین آن محاسن کشف کردن دانش نهفته در سیستم است که به شناخت بهتر سیستم کمک می کند .به عنوان مثال می توان به استفاده ترکیبی از روش خوشه بندی جهت تخصیص بودجه به دسته های مختلف از کتب اشاره کرد .
سیستمهای داده کاوی تقریبا از اوایل دهه 1990 مورد توجه قرار گرفتند . علت این امر نیز آن بود که تا آن زمان سازمانها بیشتر در پی ایجاد سیستمهای عملیاتی کامپیوتری بودند که به وسیله آنها بتوانند داده های موجود در سازمان خود را سازماندهی کنند . پس از ایجاد این سیستمها ,روزانه حجم زیادی از اطلاعات جمع آوری میشد که تفسیر کردن آنها از عهده انسان خارج بود . به همین دلیل , نیاز به تکنیکی بود که از میان انبوه داده معنی استخراج کند و داده کاوی به همین منظور ایجاد و رشد یافت .
بنابر این هدف اصلی از داده کاوی ,کشف دانش نهفته در محیط مورد بررسی است که این دانش می تواند شکلهای گوناگونی داسته باشد . دانش استخراج شده می تواند به فرم الگوهای موجود در داده ها باشد که کشف این الگوها منجر به شناخت بهتر سیستم نیز می شود . الگوهای استخراجی عموما بیانگر روابط بین ویژگیهای سیستم هستند بعنوان مثال در سیستم تجاری یک الگو می تواند بیانگر رابطه بین نوع کالا و میزان تقاضای آن باشد .
در این تحقیق داده کاوی مورد بحث قرار می گیرد . علل استفاده از داده کاوی و منابعی که داده کاوی بر روی آنها اعمال می شود ,علاوه بر این خلاصه ای از روشهای رایج داده کاوی ارائه شده است . تکنیکهای داده کاوی و قوانین وابستگی و الگوریتمهای موجود (Apriori , Aprior TID, Partition, Eclat ,Max Eclat , Vector ) و الگوریتم با ساختار Trie وfp grow و الگوریتمهای کاهشی مورد بررسی قرار می گیرند و در هر مورد مثالها , موارد کاربرد ,تکنیکها و نقاط قوت و ضعف مورد بررسی قرار گرفته اند .
Data mining(داده کاوی)
تعریف :
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 – 0.2 B + A + 0.32
میبینیم که E صفت خروجی است که مقدارش توسط ترکیب خطی صفات A , B , C تعیین می گردد.
همانند شبکه عصبی ، در این روش نیز همه ورودیها باید عددی باشند و در صورتیکه داده ها در پایگاه داده مقوله ای باشند باید آنها را به داده های عددی تبدیل کنیم.
3. قوانین وابستگی2 :
به تفصیل در بخشهای بعد مورد بحث قرار می گیرد.
قوانین پیوستگی:
یکی از مهمترین بخشهای داده کاوی، کشف قوانین وابستگی در پایگاه داده است.این قوانین، لزوم وقوع برخی صفات(آیتم ها) را در صورت وقوع برخی دیگر از آیتمها، تضمین می کند.
برای روشن شدن مطلب یک فروشگاه خرده فروشی را در نظر بگیرید. مشخصات اجناس خریده شده توسط هر مشتری در یک رکورد پایگاه داده ذخیره می شود.به هر رکورد یک شناسه (TID) نسبت داده می شود.فرض کنید که مجموعه I شامل تمام آیتمها(اجناس) فروشگاه باشد. اگر I x,y و x∩y=ø آنگاه x=>y یک قانون وابستگی است که بیان میکند اگریک مشتری اجناس مجموعه x را بخرد، اجناس مجموعه y را هم می خرد. این چنین قوانین، تأثیر مهمی در تایین استراتژیهای فروش، بخش بندی مشتریان، تنظیم کاتالوگها و... دارد. همچنین کشف قوانین وابستگی، کاربردهای بسیاری در علوم مختلف نیز دارد.
تعریف مسأله:
مجموعه آیتم: به هر زیر مجموعه از مجموعه آیتمها I)) ' یک مجموعه آیتم ' میگوییم.
در بیشتر الگوریتمها مساله کشف قوانین پیوستگی به دو زیر مساله تقسیم می شود:
1.پیدا کردن تمامی زیر مجموعه های مجموعه I [مجموعه آیتمها] که تکرار (وقوع) آنها در پایگاه بیشتر از یک حد تایین شده است.
به مجموعه آیتمهایی که تعداد وقوع آنها در پایگاه بزرگتر(یا مساوی)حد تایین شده است
' مجموعه آیتمهای بزرگ'، وبه بقیه' مجموعه آیتمهای کوچک' می گوییم.
2.بکارگیری مجموعه آیتمهای بزرگ برای تولید قوانین مطلوب.
فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد
تعداد صفحات این مقاله 22 صفحه
پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید
دانلودمقاله نگاهی بر داده کاوی و کشف قوانین وابستگی
