مروری بر روش های داده کاوی در پایگاه داده های بزرگ

[برای مشاهده لینک ها شما باید عضو سایت باشید برای عضویت در سایت بر روی اینجا کلیک بکنید]

امروزه به دلیل وجود ابزار های مختلف برای جمع آوری داده ها و پیشرفت قابل قبول تكنولوژی پایگاه داده ، حجم انبوهی از اطلاعات در انبار داده های مختلف ذخیره شده است . این رشد انفجاری داده ها ، احتیاج به یك سری تكنیك ها و ابزار های جدید كه توانایی پردازش هوشمندانه اطلاعات را دارا باشند ، نمایان می سازد .
داده كاوی با پیدا كردن مجموعه ای از الگوهای جالب از دل داده های موجود در انباره ها ، می تواند چنین نیازی را مرتفع كند .
در حال حاضر داده كاوی در پایگاه داده های بزرگ ، توسط بسیاری از محققان به عنوان یك موضوع تحقیقاتی مهم به شمار می آید .
محققان در بسیاری از رشته ها نظیر پایگاه داده ها ، یادگیری ماشین و آمار ، این موضوع را پیگیری كرده و تكنیك های مختلفی را برای داده كاوی ، تكنیك ها و روش های مختلف ارائه شده در این زمینه را معرفی كرده و آنها را طبقه بندی كند .
داده كاوی یكی از مهم ترن مراحل فرایند استخراج دانش در پایگاه داده به حساب می آید . مراحل مختلف استخراج دانش در پایگاه داده ها به شرح ذیل است :
۱. درك دامنه مسئله : شامل دانش های موجود و اهداف مسئله .
۲. استخراج یك مجموعه داده : شامل انتخاب یك مجموعه داده ای و تمركز ر روی قسمتی از داده ها .
۳. آماده سازی و پاكسازی داده ها : شامل عملیات پایه ای نظیر حذف و تغییر داده های دارای اشكال .
۴. یكپارچه سازی داده ها : شامل یكپارچه كردن منابع داده ای ناهمگون .
۵. كاهش و تغییر شكل داده ها : شامل روش هایی برای تغییر شكل و كاهش ابعاد داده ها .
۶. انتخاب نوع كاوش داده ها : شامل تعمیم و تقلیل ، طبقه بندی ، رگرسیون ، گروه بندی ، وب كاوی ، بازیابی تصویر ، كشف قوانین پیوندی و وابستگی های تابعی ، استخراج قوانین و یا تركیبی از اینها .
۷. انتخاب الگوریتم كاوش داده ها : شامل انتخاب متدهایی برای جست و جوی الگوها .
۸. كاوش داده ها : شامل جست و جوی الگوهای جالب .
۹. تفسیر : شامل تفسیر ، بازنمایی و آنالیز الگوی كشف شده .
۱۰. استفاده از دانش كشف شده : شامل پیاده سازی دانش كشف شده در سیستم های اجرایی و اتخاذ تصمیماتی برپایه دانش مراحل مختلف كشف دانش .
● تكنیك های مختلف داده كاوی .
تكنیك های مختلف داده كاوی را می توان بر اساس نوع عملیاتی كه انجام می دهند به دو دسته « پیش بینی كننده » و « تشریح كننده » تقسیم كرد . تكنیك های پیش بینی كننده با ساخت مدلی برای پیگاه داده ، وظیفه پیش بینی موارد ناشناخته را بر عهده دارند . در حالی كه تكنیك های تشریح كننده ، الگوهایی قابل فهم از داده ها را برای انسان كشف می كنند .
● طبقه بندی .
هدف از طبقه بندی ، مشخص كردن ویژگی هایی است كه بتوان توسط آن ، كلاس های مختلف را از یكدیگر متمایز كرد طبقه بندی در داده كاوی طی دو مرحله انجام می گیرد .
ابتدا از روی داده های قدیمی ، كلاس های مختلف تشخیص داده شده و سپس تعلق داشتن داده های جدید به كلاس های موجود ، پیش بینی می شود . طبقه بندی جزو تكنیك های یادگیری با ناظر است زیرا با در اختیار داشتن یك مجموعهداده آموزشی ( به عنوان راهنما ) ، داده های جدید را طبقه بندی می كند .
این روش جزو روش های پیش بینی كننده نیز به شمار می آید .
در ادامه به روش های مختلف طبقه بندی داده ها می پردازیم .
● درخت تصمیم .
متد طبقه بندی بر اساس تولید درخت تصمیم ، یكی از روش های یادگیری ماشین به حساب می آید كه به دلیل استفاده از یك مجموعه آموزشی اولیه ، جزو روش های یادگیری با ناظر است .
برای تولید درخت تصمیم ، ابتدا یك مجموعه اولیه در نظر گرفته می شود و درخت تصمیم آن ساخته می شود . چنانچه این درخت پاسخگوی همه حالات نبود ، با انتخاب مجموعه ای دیگر ، درخت توسعه داده می شود . این فرایند تا تكمیل درخت برای پاسخگویی به همه حالات ادامه می یابد . درخت تصمیم تولید شده ، درختی است كه برگ های آن كلاس های مختلف و گره های میانی ، ویژگی ها و حالات مختلف آنها را نشان می دهد .
● شبكه های عصبی .
شبكه عصبی نیز از جمله روش های یادگیری ماشین برای انجام طبقه بندی است . در این روش یك نگاشت از ورودی به خروجی به صورت غیر خطی انجام می گیرد . هدف اصلی در این روش ، پیدا كردن مجموعه وزن های مناسب برای شبكه به نحوی است كه كلیه داده های آموزشی اولیه را به صورت صحیح طبقه بندی كند .
از مزایای این روش می توان به دقت پیش بینی بالا و توان مقاومت در بابر خطاهای داده های آموزشی اشاره كرد . زمان یادگیری طولانی و مشكل بودن فهم تابع یاد گرفته شده توسط شبكه نیز از معایب این روش به حساب می آید .
● تئوری بیز .
تئوری بیز یكی از روش های آماری برای طبقه بندی به شمار می آید . در این روش كلاس های مختلف ، هر كدام به شكل یك فرضیه دارای احتمال در نظر گرفته می شوند .
هر ركورد آموزشی جدید ، احتمال درست بودن فرضیه های پیشین را افزایش و یا كاهش می دهد و در نهایت ، فرضیاتی كه دارای بالاترین احتمال شوند ، به عنوان یك كلاس در نظر گرفته شده و برچسبی بر آنها زده می شود . این تكنیك با تركیب تئوری بیز و رابطه سببی بین داده ها ، به طبقه بندی می پردازد .
● رگرسیون .
رگرسیون نیز یكی از روش های آماری برای طبقه بندی به شمار می آید . هدف از رگرسیون ، پیش بینی مقدار یك متغیر پیوسته بر اساس مقادیر متغیر های دیگر است . رگرسیون به دو دسته خطی و غیر خطی تقسیم می شود .
برای مثال می توان پیش بینی میزان فروش یك محصول جدید را بر اساس میزان تبلیغات صورت گرفته بر روی آن ، از روش رگرسیون انجام داد .
به جز روش های ذكر شده ، روش های دیگری نیز برای طبقه بندی موجود است كه می توان به K_ Nearest Neighborhood ، Case_ Based Reasoning و الگوریتم ژنتیك اشاره كرد .
● گروه بندی داده ها .
به فرایند دسته بندی اشیای فیزیكی یا انتزاعی به كلاس هایی از اشیاء متشابه ، گروه بندی ( طبقه بندی بدون ناظر ) می گویند .
گروه بندی جزو روش های تشریح كننده به حساب می آید . این روش با تفكر تقسیم و حل ، به دسته بندی داده های موجود در یك سیستم بزرگ پرداخته و آنها را به مولفه های كوچك تر تقسیم می كند .
یك گروه بندی را زمانی مناسب گویند كه اشیای داده ای درون هر گروه بسیار به یكدیگر شبیه بوده و با اشیای گروه های دیگر تفاوت بسیار داشته باشند . معیار شباهت و تفاوت بین اشیای داده ای توسط یك تابع فاصله مشخص می شود . بسته به نوع داده ، توابع فاصله متفاوتی موجود است كه از آن جمله می توان به تابع فاصله Minkowski ، تابع فاصله اقلیدسی ضریب Jaccark اشاره كرد . در ادامه به روش های مختلف برای گروه بندی داده ها پرداخته می شود.
● بخش بندی
در این تكنیك یك بخش بندی از پایگاه داده D با n شیء به k گروه انجام می گیرد . این كار توسط معیاری كه برای گروه بندی در نظر گرفته شده ، انجام می شود . روش های مختلفی از جمله K_ means ، K_ medoids ، PAM ، CLARA و CLARANS برای دسته بندی موجود است .
● سلسله مراتبی .
این تكنیك از فاصله ماتریسی به عنوان شرط گروه گروه بندی استفاده می كند . این روش به جای مشخص كردن تعداد گروه ها در ابتدای كار ، احتیاج به یك شرط خاتمه برای پایان دادن به عملیات گروه بندی دارد .
روش های مختلفی نیز برای این تكنیك مطرح شده است كه از آن جمله می توان به روش AGNES ، DLANA ، BLRCH ، CURE و CHAMELEON اشاره كرد .
● گروه بندی بر اساس تراكم .
در این تكنیك ، گروه بندی بر اساس میزان تراكم نقاط به هم پیوسته مشخص می شود . دو پارامتر Eps و MinPts در این تكنیك در نظر گرفته می شود كه Eps مشخص كننده ماكزیمم شعاع همسایگی و MinPts مشخص كننده مینمم تعداد نقاط درون همسایگی Eps است .
روش های مختلفی نظیر DBSCAN ، OPTLCS ، DENCLUE و CLlQUE نیز در این تكنیك مورد مطالعه قرار گرفته است.● كاوش قوانین پیوندی .
یكی دیگر از تكنیك های داده كاوی ، كاوش قوانین پیوندی است .
از جمله كارهایی كه كاوش قوانین پیوندی برای ما انجام می دهد می توان به پیدا كردن وابستگی ها و همبستگی ها و همبستگی های موجود در بین داده ها ، یافتن الگوهایی كه غالبا در بین داده ها وجود دارند و همچنین پیدا كردن یك سری ساختار سببی در بین آیتم ها و اشیای موجود در پایگاه داده های تعاملی و رابطه ای اشاره كرد . قبل ازمعرفی الگوریتم های مربوط به كاوش قوانین پیوندی ، نیاز به معرفی یك سری مفاهیم پایه است .
۱. مجموعه آیتم های موجود در یك پایگاه اطلاعاتی با {...،X۲ ،X۱ } = ltemSet نمایش داده می شوند .
۲. برای هر قانون به شكل Y -> X است ، دو مقدار Support و Confidence مشخص می شود .
۳. Support احتمال وجود همزمان X و Y به صورت توام در تراكنش است .
۴. Confidence احتمال شرطی است برای ‎آنكه تراكنش دارای X ، دارای Y نیز باشد .
بنابراین قانون Y -> X با ( S=۵۰% و C=۶۶.۷% ) بدین معنی است كه X و Y به صورت توام در ۵۰ درصداز كل تراكنش ها وجود دارند و در ۷/۶۶ درصد از تراكنش ها ، هر جا X در تراكنش حضور داشته ، Y نیز حضور داشته است . كاوش قوانین پیوندی در پایگاه داده ها شامل دو مرحله زیر است :
۱. كشف بزرگ ترین مجموعه آیتم ها ( مجموعه آیتم هایی كه دارای مقدار Support بالاتر از یك مقدار خاص باشند ) .
۲. استفاده از مجموعه آیتم های كشف شده در مرحله قبل و ساخت قوانین پیوندی .
به طور كلی بیشتر كارها برای بهینه كردن اجرای مرحله اول یعنی كشف بزرگ ترین مجموعه آیتم انجام می گیرد ، زیرا با داشتن بزرگ ترین مجموعه آیتم ، پیدا كردن قوانین به صورت مستقیم ، ممكن می شود . در ادامه به معرفی الگوریتم های مختلف ارائه شده برای كشف بزرگ ترین مجموعه آیتم می پردازیم .
● Apriori
هدف در این الگوریتم ، پیدا كردن بزرگ ترین مجموعه آیتم است كه حداقل Support و Confidence را رعایت كند . دو فرض زیر در این الگوریتم در نظر گرفته می شود :
۱. هر زیر مجموعه از یك مجموعه آیتم تكرار شونده ، تكرار شونده است . ( یعنی اگر فرضاً مجموعه { c ، b ، a } تكرار شونده باشد ، آنگاه مجموعه { b ، a } نیز تكرار شونده است .)
۲. هر فوق مجموعه از یك مجموعه آیتم تكرار نشونده ، است . ( یعنی اگر فرضاً مجموعه { b ، a } تكرار شونده نباشد ، آنگاه مجموعه { c ، b ، a } نیز تكرار شونده نیست . )
الگوریتم Apriori به این صورت است كه در هر بار ، یك سری مجموعه آیتم بزرگ با طول K+۱ را از روی مجموعه آیتم های كاندید با طول K می سازد و این كار را تا رسیدن به یك مجموعه آیتم با بیشترین طول انجام می دهد . مجموعه آیتم های كاندید در هر دفعه با ضرب مجموعه كاندید در خودش به دست می آید از مشكلات این روش می توان به حجم بسیار بالای تراكنش های موجود در پایگاه داده ، طولانی بودن زمان جست و جوی آنها در هر بار و تعداد زیاد كاندیدها در هر مرحله اشاره كرد . ایده های مطرح شده برای بهینه سازی الگوریتم Apriori عبارتند از :
۱. كاهش تعداد دفعات جست و جو در پایگاه داده تراكنشی .
۲. كاهش تعداد كاندیدها .
۳. ساده كردن شمارش برای Support .
● DHP
این روش مشابه با الگوریتم Apriori بوده و تنها تفاوت آن در ایجاد مجموعه كاندید در هر مرحله است . در روش Apriori مجموعه كاندید ، با ضرب مجموعه آیتم بزرگ به دست آمده تا این مرحله در خودش ، به وجود آمد . اما در روش DHP برای ساخت مجموعه كاندید در هر مرحله ، از یك جدول hash استفاده می شود و تنها یك سری از مجموعه آیتم های موجود در حاصلضرب به عنوان مجموعه كاندید پذیرفته می شود .
( مجموعه آیتم هایی كه دارای Support بالاتری هستند .)
الگوریتم DHP با استفاده از كاهش تعداد كاندیدها ، الگوریتم Apriori را بهبود می بخشد . روش های دیگری نیز برای بهبود الگوریتم Apriori مطرح شده اند ؛ روش DlC تعداد جست و جو ها را كاهش می دهد ، روش Partition پایگاه داده را به دو قسمت تقسیم كرده و درهر كدام به دنبال بزرگ ترین مجموعه آیتم محلی می گردد و در نهایت بر اساس آنها بزرگ ترین مجموعه آیتم كلی را پیدا می كند .
روش Sampling هر دفعه یك مجموعه آیتم را به عنوان نمونه انتخاب كرده و بزرگ ترین مجموعه آیتم را پیدا می كند و سپس مرزهای مجموعه را بررسی كرده و پایگاه را برای مجموعه آیتم های بزرگ تر ، جست و جو می كند .
●خلاصه سازی و كلی نگری داده ها در سطوح مختلف .
یكی دیگر از روش های داده كاوی ، خلاصه سازی و كلی نگری داده ها در سطوح مختلف است . به طور كلی اغلب داده های موجود در پایگاه داده دارای جزئیات فراوانی هستند . برای مثال در پایگاه داده فروش ، رابطه كالا شامل فیلدهای اطلاعاتی نظیر شماره كالا ، نام كالا ، سال ساخت ، قیمت و غیره است . جزئیات زیاد سبب پایین آمدن سطح ادراكی می شود و برای تصمیم گیری بر اساس اطلاعات قبلی ، نیاز به سطوح ادراكی بالاتری است .
داده كاوی با انجام خلاصه سازی و كلی نگری در داده ها در سطوح مختلف به كمك شتافته و سطوح ادراكی بالاتری را ایجاد می كند . در ادامه رهیافت های مختلف ارائه شده برای این كار ، مورد بررسی قرار گرفته است .
● رهیافت هرم داده ها .
ایده اصلی در این رهیافت ، جمع آوری نتایج محاسبات پرهزینه ای است كه اغلب مورد درخواست بوده و نگهداری از آنها در یك ساختار چند بعدی به نام هرم داده ها صورت می گیرد . این محاسبات معمولا شامل توابعی نظیر مجموع ، میانگین ، ماكزیمم و غیره بر روی مجموعه صفات خاصه است . هرم داده ها معمولا بر روی پایگاه داده تحلیلی ایجاد می گردد . برای كلی نگری و ویژه نگری داده ها به ترتیب می توان Roll_Up و Drill_Down را بر روی هرم داده ها انجام داد . در بیشتر مواقع هرم داده ها دارای سه بعد بوده كه دو بعد آن معمولاً زمان و مكن و بعد دیگر یك آیتم اطلاعاتی است .
برای مثال میزان فروش آیتم X در مهر ماه سال قبل در منطقه شمال تهران ، می توان نمایش دهنده یك درخواست كه غالباً مورداستفاده قرار می گیرد ، باشد . از مشكلات این روش می توان به محدود بودن محاسبات فقط بر روی انواع داده ای ساده و همچنین استفاده از توابع محاسبات ساده اشاره كرد .
● رهیافت استنتاج بر اساس صفت خاصه .
در رهیافت هرم داده ها ، محاسبات بر روی پایگاه داده تحلیلی به صورت offline انجام می گیرد . برای حل این مشكل ، رهیافت استنتاج بر اساس صفت خاصه ابتدا یك درخواست داده كاوی را به صورت DMQL مشخص می كند . سپس یك پرس و جو از روی DMQL داده شده می سازد و از پایگاه داده به صورت ONLINE درخواست می كند . سپس بر روی داده های به دست آمده ، تكنیك های كلی نگری داده ها نظیر حذف صفت خاصه ، بالا رفتن از درخت ادراك و غیره را اعمال می كند .
●● نتیجه گیری .
داده كاوی یك گرایش تحقیقاتی است كه به سرعت در حال پیشرفت بوده و پژوهش های بسیاری بر روی آن انجام شده است . محققان و برنامه نویسان رشته های مختلف ، در هنر داده كاوی با هم شریك هستند ، از این رو مهیا كردن یك بررسی كلی نسبت به متدهای داده كائی ، كار دشواری است .
در هر صورت این مقاله سعی كرد ، یك بررسی اجمالی بر روی تكنیك های مختلف داده كاوی انجام داده و روش های مختلف ارائه شده را مورد معرفی و مقایسه قرار دهد .

منبع : [برای مشاهده لینک ها شما باید عضو سایت باشید برای عضویت در سایت بر روی اینجا کلیک بکنید]