پایان نامه داده کاوی (Data Mining)

پایان نامه مقطع کارشناسی ناپیوسته

رشته کامپیوتر

سال 1387

چکیده:

در دو دهه قبل توانايي­های فنی بشر برای توليد و جمع­ آوری داده‌ها به سرعت افزايش يافته است. عواملی نظير استفاده گسترده از بارکد برای توليدات تجاری، به خدمت گرفتن کامپيوتر در کسب­ و­کار، علوم، خدمات­ دولتی و پيشرفت در وسائل جمع­ آوری داده، از اسکن کردن متون و تصاوير تا سيستمهای سنجش از دور ماهواره­ای، در اين تغييرات نقش مهمی دارند.

              بطور کلی استفاده همگانی از وب و اينترنت به عنوان يک سيستم اطلاع رسانی جهانی ما را مواجه با حجم زیادی از داده و اطلاعات می‌کند. اين رشد انفجاری در داده‌های ذخيره شده، نياز مبرم وجود تکنولوژی­های جديد و ابزارهای خودکاری را ايجاد کرده که به صورت هوشمند به انسان ياری رسانند تا اين حجم زياد داده را به اطلاعات و دانش تبديل کند. داده­ کاوی به عنوان يک راه حل برای اين مسائل مطرح مي باشد. در يک تعريف غير رسمی داده ­کاوی فرآيندی است، خودکار برای استخراج الگوهايی که دانش را بازنمايی مي­کنند، که اين دانش به صورت ضمنی در پايگاه داده­ های عظيم، انباره­ داده[1] و ديگر مخازن بزرگ اطلاعات، ذخيره شده است.

                به لحاظ اینکه در چند سال اخیر مبحث داده­ کاوی و اکتشاف دانش موضوع بسیاری از مقالات و کنفرانسها قرار گرفته و نرم­افزار­های آن در بازار به شدت مورد توجه قرار گرفته، از اینرو در مقاله سعی بر آن شده تا گذری بر آن داشته باشیم.

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

                در فصل 2 یکی از شیوه­های داده ­کاوی که از سبد خرید گرفته شده­ است توضیح داده شده است . در این فصل به شرح قوانین ارتباطی خواهیم پرداخت که در آن بعد از دسته­ بندی الگوریتمها ، الگوریتم Apriori ( که یک الگوریتم پایه در این زمینه است ) و الگوریتم FP-Growth ( یک الگوریتم جدید میباشد) را با شرح یک مثال توضیح می­دهیم و در آخر آن دو را با هم مقایسه می­کنیم .

                در فصل 3 مباحث وب­کاوی و متن­کاوی را که در بسیاری از مراجع جزء کاربردهای داده­ کاوی به حساب می­آید شرح داده خواهد شد.

[1] Data  warehouses

فصل 1

مروری بر داده­کاوی

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

با استفاده از پرسش‌های ساده در SQL و ابزارهای گوناگون گزارش‌گیری معمولی، می‌توان اطلاعاتی را در اختیار کاربران قرار داد تا بتوانند به نتیجه‌گیری در مورد داده‌ها و روابط منطقی میان آنها بپردازند. امّا وقتی که حجم داده‌ها بالا باشد، کاربران هرچند زبر­دست و با­تجربه باشند نمی‌توانند الگوها مفید را در میان حجم انبوه داده‌ها تشخیص دهند و یا اگر قادر به این کار هم باشند، هزینه عملیات از نظر نیروی انسانی و مادی بسیار بالا است. از سوی دیگر، کاربران معمولاً فرضیه‌ای را مطرح می‌کنند و سپس بر­اساس گزارشات مشاهده شده به اثبات یا رد فرضیه می‌پردازند، در حالی که امروزه نیاز به روشهایی است که اصطلاحاً به کشف دانش [1] بپردازند یعنی با کمترین دخالت کاربر و بصورت خودکار الگوها و رابطه‌های منطقی را بیان نمایند.

داده کاوی[2] یکی از مهمترین این روشها است که به الگوهای مفید در داده‌ها با حداقل دخالت کاربران شناخته می‌شوند واطلاعاتی را در اختیار کاربران و تحلیل گران قرار می‌دهند تا براساس آن تصمیمات مهم و حیاتی در سازمانها اتخاذ شوند.

اصطلاح داده­ کاوی زمانی بکار برده می‌شود که با حجم بزرگی از داده‌ها، در حد مگا یا ترابایت، مواجه باشیم. در تمامی منابع داده­کاوی بر این مطلب تأکید شده است. هرچه حجم داده‌ها بیشتر و روابط آنها پیچیده­تر باشد دسترسی به اطلاعات نهفته در میان داده­ها مشکل­تر می‌شود و نقش داده ­کاوی بعنوان یکی از روش­های کشف دانش، روشن‌تر می‌گردد.

داده­ کاوی بطور همزمان از چندین رشته علمی بهره می‌برد نظیر: تکنولوژی پایگاه داده، هوش مصنوعی، یادگیری ماشین، شبکه‌های عصبی، آمار، الگو، سیستم‌های مبتنی بر دانش[3]، حصول دانش[4]، بازیابی اطلاعات[5]، محاسبات سرعت بالا[6] و بازنمایی بصری داده[7].

1-1: تعریف داده­کاوی:

اصطلاح Data Mining همانطور که از ترجمه آن به داده­ کاوی مشخص می­شود، به مفهوم استخراج اطلاعات نهان و یا الگوها و روابط مشخص در حجم زیادی از داده‌های یک یا چند بانک اطلاعاتی بزرگ است. اطلاعات استخراج شده در تعریف Data Mining بطور ضمنی به معنی اطلاعاتی است که بر اساس آن بتوان به نتایجی دست یافت که بطور معمول ملموس نیستند. در این تعریف بر بزرگ بودن بانکهای اطلاعاتی و یا حجم زیاد داده‌های مورد پردازش تاکید می‌شود. علت این است که از نظر آماری و تئوری اطلاعات، تجزیه و تحلیل داده‌ها و یا آنطور که در این اصطلاح تعبیر می‌شود، کاوش در حجم کم داده­های یک بانک به نتایج قابل قبولی منجر نمی‌شود. به کمک ابزارهای Data Mining می‌توان مقادیر متغیرهای را پیش­بینی و توصیف نمود. این ابزارها در فرایندهای تصمیم‌گیری متکی بر اطلاعات و دانش [8] کاربر فراوان دارند و فعالیت­های تجاری نوین و مدرن امروزه به شدت بر آن متکی است. فرایند Data Mining را نباید با روش‌های متداول آنالیز داده و اطلاعات و سیستم­های تصمیم‌گیری معمولی یکی دانست. به کمک روش‌های Data Mining می‌توان به پرسش­هایی (عمدتاً تجاری) پاسخ گفت که بطور سنتی عملاً امکان وجود ندارد.

در متون آکادمیک تعاریف گوناگونی برای داده کاوی ارائه شده‌اند. در برخی از این تعاریف داده­کاوی در حد ابزاری که کاربران را قادر به ارتباط مستقیم با حجم عظیم داده­ها می‌سازد معرفی گردیده است و در برخی دیگر، تعاریف دقیقتر که در آنها به کاوش در داده­ها توجه می‌شود موجود است. برخی از این تعاریف عبارتند از:

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

·        اصطلاح داده­ کاوی به فرایند نیم خودکار تجزیه و تحلیل پایگاه داده­های بزرگ به منظور یافتن الگوهای مفید اطلاق می‌شود.

·        داده­کاوی یعنی جستجو در یک پایگاه داده ­ها برای یافتن الگوهایی میان داده­ها.

·        داده­کاوی عبارتست از فرایند یافتن دانش از مقادیر عظیم داده­های ذخیره شده در پایگاه داده، انباره داده و یا دیگر مخازن اطلاعات.

·        داده­کاوی یعنی استخراج دانش کلان، قابل استناد و جدید از پایگاه داده­های بزرگ.

·        داده­کاوی یعنی تجزیه و تحلیل مجموعه داده­های قابل مشاهده برای یافتن روابط مطمئن بین داده­ها.

همانگونه که در تعاریف گوناگون داده­کاوی مشاهده می­شود، تقریباً در تمامی تعاریف به مفاهیمی چون استخراج دانش، تحلیل و یافتن بین داده­ها اشاره شده است.

واژه های «داده ­کاوی» و «کشف دانش در پایگاه داده»[9] اغلب بصورت مترادف یکدیگر مورد استفاده قرار می‌گیرد. کشف دانش در پایگاه داده فرایند شناسایی درست، ساده، مفید و  نهایتا الگوها و مدلهای قابل فهم در داده­ها می‌باشد. داده­کاوی، مرحله‌ای از فرایند کشف دانش می‌باشد و شامل الگوریتم­های مخصوص داده­ کاوی است، بطوریکه تحت محدودیت­های مؤثر محاسباتی قابل قبول، الگوها و یا مدلها را در داده کشف می‌کند.

داده­ها اغلب حجیم امّا بدون ارزش می‌باشند، داده به تنهایی قابل استفاده نیست، بلکه دانش نهفته در داده­ها قابل استفاده می‌باشد. به این دلیل به داده­کاوی، تحلیل داده‌ای ثانویه[10] گفته می‌شود.

2-1: تاریخچه داده­کاوی

اخیرا داده­کاوی موضوع بسیاری از مقالات، کنفرانس‌ها و رساله‌های عملی شده است، امّا این واژه تا اوایل دهه نود مفهومی نداشت و به کاربرده نمی‌شد.

در دهه شصت و پیش از آن زمینه‌هایی برای ایجاد سیستم‌های جمع‌آوری و مدیریت داده­ها ایجاد شد و تحقیقاتی در این زمینه انجام پذیرفت که منجر به معرفی و ایجاد سیستم­های مدیریت پایگاه داده ­ها گردید.

ایجاد و توسعه مدلهای داده‌ای برای پایگاه سلسله مراتبی، شبکه‌ای و بخصوص رابطه‌ای در دهه هفتاد، منجر به معرفی مفاهیمی همچون شاخص­گذاری و سازمادهی داده‌ها و در نهایت ایجاد زبان پرسش SQL در اوایل دهه هشتاد گردید تا کاربران بتوانند گزارشات و فرم­های اطلاعاتی موردنظر خود را ، از این طریق ایجاد نمایند.

توسعه سیستم‌های پایگاهی پیشرفته در دهه هشتاد و ایجاد پایگاه­ها شی‌گرا، کاربرد گرا[11] و فعال[12] باعث توسعه همه جانبه و کاربردی شدن این سیستم‌ها در سراسر جهان گردید. بدین ترتیب DBMS­هایی همچون Oracle, DB2,­ Sybase, ... ایجاد شدند و حجم زیادی از اطلاعات با استفاده از این سیستم‌ها مورد پردازش قرار گرفتند. شاید بتوان مهمترین جنبه در معرفی داده­کاوی را مبحث کشف دانش از پایگاه داده‌ها (KDD)[13] دانست بطوریکه در بسیاری موارد DM [14]  و KDD بصورت مترادف مورد استفاده قرار می‌گیرند.

همانطور که در تعریف داده­کاوی ذکر شد، هدف جستجو و کشف الگوهایی در پایگاه داده ها و استفاده از آنها در اخذ تصمیمات حیاتی است، بنابراین می‌توان گفت که DM بخشی از فرایند KDD است که در نهایت به ایجاد سیستم‌های DSS [15] می‌شود. شکل 1-1 نقش داده کاوی در فرایند کشف دانش از پایگاه داده ها را نشان می‌دهد.

برای اولین بار مفهوم داده­کاوی در کارگاه IJCAI[16] در زمینه KDD توسّط Shapir مطرح گردید. به دنبال آن در سالهای 1991 تا 1994 ، کارگاههای KDD مفاهیم جدیدی را در این شاخه علم ارائه کردند بطوریکه بسیاری از علوم و مفاهیم با آن مرتبط گردیدند.

3-1- چه چیزی سبب پیدایش داده­کاوی شده است؟

اصلی­ترین دلیلی که باعث شد داده­کاوی کانون توجهات در صنعت اطلاعات قرار بگیرد، مساله در دسترس بودن حجم وسیعی از داده­ها و نیاز شدید به اینکه از این داده­ها  اطلاعات و دانش سودمند استخراج کنیم. اطلاعات و دانش بدست آمده در کاربردهای وسیعی از مدیریت کسب و کار و کنترل تولید و تحلیل بازار تا طراحی مهندسی و تحقیقات علمی مورد استفاده قرار می‌گیرد.

[1] - Knowledge Discovery

[2] - Data Mining

[3] - Knowledge-based system

[4] - Knowledge- acquisition

[5] - information retrieval

[6] - High-performance computing

[7] - Data visualization

[8] - Data and Knowledge driven

[9] - Knowledge Discovery in Database

[10] - Secondary Data Analysis

[11] - Application Oriented

[12] - Active DBMS

[13] - Knowledge Discovery From Database

[14] - Data Mining

[15] - Decision Support System

[16] - Workshop

داده کاوی را می‌توان حاصل سیر تکاملی طبیعی تکنولوژی اطلاعات دانست، که این سیر تکاملی ناشی از یک سیر تکاملی در صنعت پایگاه داده می‌باشد، نظیر عملیات: جمع‌آوری داده­ها و ایجاد پایگاه داده، مدیریت داده و تحلیل و فهم داده‌ها. در شکل 2-1 این روند تکاملی در پایگاه‌های داده نشان داده شده است.

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

ابزارهای داده­کاوی داده ها را آنالیز می‌کنند و الگوهای داده‌ای را کشف می‌کنند که می‌توان از آن در کاربردهایی نظیر: تعیین استراتژی برای کسب و کار، پایگاه دانش[1] و تحقیقات علمی و پزشکی، استفاده کرد. شکاف موجود بین داده­ها و اطلاعات سبب ایجاد نیاز برای ابزارهای داده­کاوی شده است تا داده‌های بی‌ارزش را به دانشی ارزشمند تبدیل کنیم.

بطور ساده داده­کاوی به معنای استخراج یا «معدن­کاری»[2] دانش از مقدار زیادی داده خام است. البته این نامگذاری برای این فرایند تا حدی نامناسب است، زیرا بطور مثال عملیات معدن­کاری برای استخراج طلا از صخره و ماسه را طلا­کاوی می­نامیم، نه ماسه­کاوی یا صخره­کاوی. بنابراین بهتر بود به این فرایند نامی شبیه به «استخراج دانش از داده» می‌دادیم که متأسفانه بسیار طولانی است. «دانش­کاوی» بعنوان یک عبارت کوتاهتر بعنوان جایگزین، نمی‌تواند بیانگر تأکید و اهمیت بر معدن­کاری مقدار زیاد داده باشد. معدن­کاری عبارتی است که بلافاصله انسان را به یاد فرایندی می‌اندازد که به دنبال یافتن مجموعه‌ کوچکی از قطعات ارزشمند از حجم بسیار زیادی از مواد خام هستیم.

با اینکه این فرایند تا حدی دارای نامگذاری ناقص است ولی این نامگذاری یعنی داده­کاوی بسیار عمومیت پیدا کرده است. البته اسامی دیگر نیز برای این فرایند پیشنهاد شده که بعضا بسیار متفاوت با واژه داده­کاوی است، نظیر: استخراج دانش از پایگاه داده، استخراج دانش[3]، آنالیز داده/ الگو، باستان شناسی داده[4]، و لایروبی داده‌ها[5].

شکل 2-1 سیر تکاملی صنعت پایگاه داده

4-1- اجزای سیستم داده­کاوی:

با توجه به مطالب عنوان شده،  یکی از تعاریف عنوان شده برای داده­کاوی چنین بود:

«داده­کاوی عبارت است از فرایند یافتن دانش از مقادیر عظیم داده‌های ذخیره شده در پایگاه داده، انباره داده و یا دیگر مخازن اطلاعات»

بر­اساس این دیدگاه یک سیستم داده­کاوی بطور نمونه دارای اجزای اصلی زیر است که شکل   3-1 بیانگر معماری سیستم است.

شکل 3-1 معماری یک نمونه سیستم داده­کاوی

1- پایگاه داده، انباره­ داده (Data warehouse) یا دیگر مخازن اطلاعات:

که مجموعه‌ای از پایگاه داده‌ها، انبار داده، صفحه گسترده[6]، یا دیگر انواع مخازن اطلاعات.

2- سرویس دهنده پایگاه داده یا انبار داده:

که مسئول بازیابی داده‌های مرتبط براساس نوع درخواست داده­کاوی کاربر می‌باشد.

3- پایگاه دانش:

این پایگاه از دانش زمینه[7] تشکیل شده تا به جستجو کمک کند، یا برای ارزیابی الگوهای یافته شده از آن استفاده می‌شود.

4- موتور داده­کاوی[8]

این موتور جزء اصلی از سیستم داده­کاوی است و بطور ایدآل شامل مجموعه‌ای از پیمانه[9] هایی نظیر توصیف[10] ، ارتباط[11]، کلاسبندی[12]، آنالیز خوشه‌ها[13] و آنالیز تکامل و انحراف[14] است.

5- پیمانه ارزیابی الگو[15]

این جزء معیارهای جذابیت[16]  را بکار می‌بندد و با پیمانه‌ی داده­کاوی تعامل می‌کند، بدینصورت که تمرکز آن بر جستجو بین الگوهای جذاب می‌باشد، و از یک حد آستانه جذابیت استفاده می‌کند تا الگوهای کشف شده را ارزیابی کند.

6- واسط کاربر گرافیکی[17]: این پیمانه بین کاربر و سیستم داده­کاوی ارتباط برقرار می‌کند، به کاربر اجازه می‌دهد تا با سیستم داده­کاوی از طریق پرس وجو[18] ارتباط برقرار کند، این جزء به کاربر اجازه می‌دهد تا شمای پایگاه داده یا انبار داده را مرور کرده، الگوهای یافته شده را ارزیابی کرده و الگوها را در فرمهای بصری گوناگون بازنمایی کند.

با انجام فرایند داده­کاوی، دانش، ارتباط یا اطلاعات سطح بالا از پایگاه داده استخراج می‌شود و قابل مرور از دیدگاههای مختلف خواهد بود. دانش کشف شده در سیستم‌های تصمیم­یار، کنترل فرایند، مدیریت اطلاعات پردازش پرس و جو[19] قابل استفاده خواهد بود.

[1] - Knowledge base

[2] - Mining

[3] - Knowledge extraction

[4] - Data archaeology

[5] - Data dredging

[6] - Spread sheets

[7] - Domain knowledge

[8] - Data mining engine

[9] - Module

[10] - Characterization

[11] - Association

[12] - Classification

[13] -Cluster analysis

[14] - Evolution and deviation analysis

[15] - Pattern evaluation module

[16] - Interesting measures

[17] - Graphical User Interface

[18] - Query

[19] - Query processing

مراجع

[1] داده­کاوی (Data Mining)، تالیف مهمد کانتاردزیک، ترجمه امیر علیخانزاده، 1385، ویرایش اول

[2] Introduction to Data Mining and Knowledge Discovery، Two Crows Corporation، 1999

[3] Data Mining: Concepts and Techniques، M.Kamber and J.Han، 2001

[4] مقاله Algorithms for Association Rule Mining – A General Survey and comparison نوشته Jochen Hipp و Gholamreza Nakhaeizadeh ، در کنفرانس ACM SIGKDD July 2000

[5] مقاله Comparative Study of Association Rules Mining Algorithms نوشته Stefan Holban (http://www.bmf.hu/conferences/saci04/Gyorodi.pdf)

[6]

http://ece.ut.ac.ir/DBRG/seminars/Keykhah/Data Mining/Data mining.doc

http://ece.ut.ac.ir/DBRG/seminars/Ghadimi-Abbasi-Pashaei/Document/datamining_Introduction.doc