فرمت : WORD                                                                         تعداد صفحه :243

 

مقدمه

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

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

 

 

 

1-2-عامل مسبب پیدایش داده کاوی

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

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

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

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

?1

-3-داده کاوی و مفهوم  اکتشاف دانش    (K.D.D) 

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

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

1- پاکسازی داده ها  : در این فاز داده های اضافی و نامربوط از مجموعه داده ها حذف می شوند.(داده های ناکامل) [2]

 2-یکپارچه سازی داده ها[4] : چندین منبع داده ترکیب می شوند،

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

   4-تبدیل داده ها : هنگامی که داده های مورد نیاز انتخاب شدند و داده های مورد کاوش مشخص گردیدند، معمولا به تبدیلات خاصی روی داده ها نیاز است. نوع تبدیل به عملیات و تکنیک داده کاوی مورد استفاده بستگی دارد، تبدیلاتی ساده همچون تبدیل نوع داده ای به نوع دیگر تا تبدیلات پیچیده تر همچون تعریف صفات جدید با انجام عملیاتهای ریاضی و منطقی روی صفات موجود.

 5-داده کاوی : بخش اصلی فرایند ، که در آن با استفاده از روش ها و تکنیک های خاص ، استخراج الگو های مفید ،  دانش استخراج می شود.

 6-زیابی الگو[5]  : مشخص کردن الگوهای صحیح و مورد نظر به وسیله معیارهای اندازه گیری.

 7-زنمایی دانش :  در این  بخش به منظور ارائه دانش استخراج شده به کاربر ، از یک سری ابزارهای بصری سازی استفاده می گردد.

 

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

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

• داده کاوی عبارت است از فرایند استخراج اطلاعات معتبر ، از پیش ناشناخته  قابل فهم و قابل اعتماد از پایگاه داده های بزرگ که شامل بهره گیری از بزارهای آنالیز داده ها، برای کشف الگوهای موجود و روابط ناشناخته‌ی میان داده ها در حجمی وسیع می باشد. و استفاده از آن درتصمیم گیری فعالیتهای تجاری مهم.   
• اصطلاح داده کاوی به فرایند نیم خودکار تجزیه و تحلیل پایگاه داده های بزرگ به منظور یافتن الگوهای مفید اطلاق می شود [3].
• داده کاوی یعنی جستجو در یک پایگاه داده ها برای یافتن الگوهایی میان داده ها [4].
• داده کاوی یعنی استخراج دانش کلان ، قابل استناد و جدید از پایگاه داده ها ی بزرگ .
• داده کاوی یعنی تجزیه و تحلیل مجموعه داده های قابل مشاهده برای یافتن روابط مطمئن بین داده ها .

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

 

1-3-2- فرآیند داده‌کاوی

 می‌توان فرآیند داده‌کاوی را طی مراحل زیر به صورت نمودار نشان داد.

 

استخراج، ترجمه

 

و فراخوانی

 

مهیا کردن داده‌ها

 

کشف الگو

 

شکل 1-1فرآیند داده‌کاوی

 

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

 

1-3-3- قابلیت های داده کاوی

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

 1-3-4-چه نوع داده‌هایی مورد کاوش قرار می گیرند؟  

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

• فایلهای ساده (FLAT FILES):

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

• پایگاههای داده ای رابطه ای(RDBMS):

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

یک درخت تصمیم یک ساختار سلسله مراتبی می‌باشدکه در آن، گره‌های میانی برای تست یک خصیصه[18] به کار می روند. شاخه‌ها نشانگر خروجی تست بوده، برگ‌ها برچسب کلاس[19] و یا همان طبقه  را مشخص می‌نمایند. نکات اساسی برای هر درخت تصمیم به شرح زیر هستند: [10]

•  ملاک استفاده شده برای ساخت درخت چه عواملی هستند؟ یعنی کدام متغیر باید برای شکستن انتخاب گردد و این متغیر چگونه باید شکسته شود؟
• ملاک برای متوقف کردن رشد درخت کدام‌ها هستند؟ یعنی چه موقعی باید عمل شاخه شاخه شدن یک نود باید متوقف شود؟
• چگونه باید شاخه‌های درخت بدست آمده هرس شوند تا بیشترین کارایی را در کلاسه‌‌بندی داشته باشیم؟    

 

1. انواع درخت‌های تصمیم

 

    درخت‌های تصمیم بر دو نوعند:

• درختان تصمیم دودویی که در هر نود، فقط دو شاخه‌ی انشعابی از آن را داریم، مانند CART.
• درختان تصمیم خطی[20]، که هر نود می‌‌تواند به چند شاخه منشعب شود، مثل CHAID. که اگر ضریب انشعاب دو باشد به درخت تصمیم دودویی تبدیل می‌شود.

 

1-4-3-1-4-   نحوه‌ی هرس کردن درخت

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

  تابع g(t) (تابع Strength) رابرای هر نود غیر برگ حساب می‌‌کنیم. سپس می‌‌توان زیر درختی را که دارای کمترین g(t) می‌‌باشد از درخت هرس کرد.

       (2.1)

که در آن:

 

	مجموع الگوهای موجود در گره‌ی T	)	تعداد الگوهای با کلاس j  در گره‌ی T	R(t) = Maxi
	مجموع الگوهای موجود در داده‌های آموزشی		مجموع الگوهای موجود در گره‌ی T

 

تعداد گره‌های برگ در زیر درخت با ریشه‌ی T = T"

 

 1-4-3-2- نزدیکترین همسایگی_ K [21]

 

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

 

شکل 1-4: محدوده همسایگی (بیستر همسایه ها در دسته X قرار گرفته اند)

 

   اولین مورد برای بکاربردن (K_NN) یافتن معیاری برای فاصله بین صفات در داده­ها و محاسبه آن است. در حالیکه این عمل برای داده­های عددی آسان است، متغیرهای دسته­ای نیاز به برخورد خاصی دارند. هنگامیکه فاصله بین موارد مختلف را توانستیم اندازه گیریم، می­توانیم از مجموعه مواردی که قبلا دسته­بندی شده­اند را بعنوان پایه دسته­بندی موارد جدید استفاده کنیم، فاصله همسایگی را تعیین کنیم، و تعیین کنیم که خود همسایه­ها را چگونه بشماریم.

(K_NN) بار محاسباتی زیادی را روی کامپیوتر قرار می­دهد زیرا زمان محاسبه بصورت فاکتوریلی از تمام نقاط افزایش می­یابد. درحالیکه بکاربردن درخت تصمیم یا شبکه عصبی برای یک مورد جدید فرایند سریعی است، (K_NN) نیاز به محاسبه جدیدی برای هر مورد جدید دارد. برای افزایش سرعت (K_NN)معمولا تمام داده­ها در حافظه نگهداری می­شوند.

   فهم مدل های (K_NN) هنگامیکه تعداد متغیرهای پیش­بینی کننده کم است بسیار ساده است. آنها همچنین برای ساخت مدلهای شامل انواع داده غیر استاندارد هستند، مانند متن بسیار مفیدند. تنها نیاز برای انواع داده جدید وجود معیار مناسب است.[5]

 

1-4-3-3-بیزی

 

   اهمیت استدلال بیزی داده کاوی را می‌توان به دو دلیل عمده نسبت داد. اول اینکه ، الگوریتم‌های یادگیری بیزی که به طور صریح بر روی احتمالات فرض‌های مختلف کار می‌کنند‌، مانند naive Bayes classifier که از جمله کاراترین وعملی‌ترین الگوریتم‌های ممکن برای برخی مسائل یادگیری می‌باشد. به عنوان مثال Michie  (1994) مقایسه کاملی بین این الگوریتم و سایر الگوریتم‌ها مانند درخت تصمیم و شبکه عصبی انجام داده است . این محقق نشان می‌دهد که الگوریتم naive Bayes classifier قابل رقابت با سایر الگوریتم‌ها و در برخی موارد بهتر از آنها عمل می‌کند.

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

 

---