پروژه Data Mining ( داده کاوی )

پروژه کارشناسی رشته نرم­ افزار

چکیده:

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

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

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

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

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

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

فصل 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- چه چیزی سبب پیدایش داده­کاوی شده است؟

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

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

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

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

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

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