دانلود مقاله بهبود روش رتبهبندی چندتایی در قوانین دادهکاوی

بخشی از مقاله

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

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

می دهد که الگوریتم بهبود یافته نسبت به الگوریتم قبلی رتبهبندی دقیق تری را تامین کرده است. کلید واژه- رتبهبندی قوانین، قوانین دستهبندی، رتبهبندی چندتایی قوانین، رتبهبندی تکی قوانین

-1 مقدمه

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

شده اند،[7-5] که هدف این روشها جلوگیری از overfitting و ایجاد درختان عمومی تر بوده است. اما برای دسته بنـدی کننـده های مبتنی بر قانون رویکرد های کمی برای کاهش قـوانین ارائـه شــده اســت.[9 ,8] هــدف از ایــن مقالــه رتبــه بنــدی قــوانین دستهبندی می باشد. الگوریتم های رتبه بندی قوانین بـر اسـاس معیارهایی بین قوانین تمایز قائل می شوند و یک ترتیب خطی از قوانین را ارائه می دهند. الگوریتم های رتبه بنـدی قواعـد بـه دو دسته رتبه بندی تکی و رتبه بندی چندتایی تقسـیم مـی شـوند. در روش های رتبه بندی تکی، قوانین بصورت فردی و بـر اسـاس معیار شایستگی شان رتبه بندی می شوند اما در روش رتبهبندی چندتایی قوانین با هم مـورد ارزیـابی قـرار مـی گیرنـد و رتبـه و انتخاب قانون ها بستگی به قانون های کاراتر انتخاب شده قبل از خودش دارد.[4] دراین مقاله بهبودی بر روی الگوریتم رتبه بندی چندتایی انجام شده است، بطوریکه الگوریتم بهبـود یافتـه دقـت رتبه بندی بالاتری را تامین کـرده اسـت. در ادامـه ی مقالـه ، در بخش دوم به مفاهیم پایـه کـه شـامل دو بخـش تعریـف قـوانین دسته بندی و معیارهای جذابیت آنها است، پرداختـه مـی شـود. بخش سوم روشهای رتبه بندی تکی و روش رتبه بندی چندتایی قوانین را شرح می دهـد. در بخـش چهـارم روش پیشـنهادی مـا

1

n fire corr

C  (c1,...,cN ) مشخص کننـده
پانزدهمین کنفرانس دانشجویی مهندسی برق ایران دانشگاه کاشان، 9-7 شهریور 1391

برای رتبه بندی چندتایی قوانین شرح داده مـی شـود. در بخـش پنجم آزمایشات تجربی و مقایسه بین روش ها و در بخش ششـم نتیجه گیری از این مقاله آورده شده است.

-2 مفاهیم پایه

-1-2 تعریف قوانین دسته بندی

یـــک قـــانون دســـته بنـــدی مفهـــومی بـــه شـــکل
X1 op x1, X 2 op x2,...,X n op xn Y  y اســت کــه در آن
X i هــا صــفت هــای شــرطی، xi مقــادیر مربــوط بــه دامنــه هــر X i ، Y صفت کلاس و y مقدار آن کلاس می باشد. op نیـز یـک عملگر رابطه ای مثل , ,,, , می باشد. بطور مثال قانون

Job  Yes, Annualincome  50000  Credit  Good ×

یک قانون دسته بندی است که می گویـد کسـی کـه کـار دارد و درآمد سالیانه آن بـیش از 50000 دلار اسـت در دسـته کسـانی قرار می گیرد که اعتبار خوبی دارند.[1]

قوانین دسته بندی برای داده کاوی پیشگویانه کاربرد دارنـد. یک مجموعه داده که در آن هر کدام از نقاط داده در یک دسـته قرار گرفته اند و همه ی آنها شامل یـک سـری صـفات مشـخص میباشند یک پایگاه داده دسته بندی هست. هدف از داده کـاوی پیشگویانه، ایجاد مدلی است که بتوانیم برای نقاط داده جدید بـا صــفات مشــخص، دســته ی آنهــا را پــیش بینــی کنــیم. یکــی از روشهای قدیمی ایجاد درختان تصمیم اسـت کـه قـدیمی تـرین الگوریتم در این زمینه ID3 می باشـد کـه در اواخـر دهـه 70 و اوایل دهه ی 80 مـیلادی توسـط کـوئینلن معرفـی شـد.[2] بـر اساس درختان تصمیم مـی تـوان قـوانین را بـه وجـود آورد کـه دستهی نقاط داده را پیش بینی کرد. در فاصله کوتاهی الگـوریتم C4.5 نیز توسـط کـوئینلین ابـداع گردیـد.[3] ایـن الگـوریتم از مفاهیم اطلاعات کسب شده و کاهش بـی نظمـی بـرای انتخـاب تقسیم بندی های مناسب و ایجـاد قـوانین دسـته بنـدی از یـک مجموعه داده استفاده می کند. بـا توجـه بـه عمومیـت الگـوریتم C5.0 در مباحث مربـوط بـه درخـت تصـمیم، در ایـن مقالـه از الگوریتم C5.0 در نرم افـزارSPSS Clementine 2012 کـه آخرین نسخه از الگوریتم C4.5 می باشد ، برای استخراج قوانین از پایگاه داده استفاده شده است.

-2-2 معیارهای جذابیت قوانین دسته بندی

برای برتری و تمایز بین قواعد اسـتخراج شـده از معیارهـای جــذابیت اســتفاده مــی شــود. 3 معیــار مهــم بــرای یــک قــانون

دستهبنـدی معیارهـای پشـتیبان ، اطمینـان و پوشـش هسـتند. روشهای رتبه بندی تکی بر اساس هر ترکیبی از این معیار ها بـه قوانین امتیازی نسبت می دهند کـه ایـن امتیـاز باعـث انتخـاب قوانین برتـر از میـان تمـام قـوانین مـی شـود. فـرض کنیـد کـه D ( X , C )یـــک مجموعـــه جفتـــی از ( X  (x1,...,xN و C  (c1,...,cN ) باشــد. کــه ( X  (x1,...,xN مشــخص کننــده
نقاط داده چند بعدی از xi ها و

دسته بـرای نقـاط داده در X باشـد. آنگـاه مـا از n1,...,nP بـرای نمایش تعداد نقاط داده در دسـته ی1 تـا P و از N بـرای نمـایش تعـــداد کـــل نقـــاط داده اســـتفاده مـــی کنـــیم. بـــرای یـــک قانون r ، n fire (r, D) تعداد نقاط داده ای در D اسـت کـه توسـط
قانون r ارضـا مـی شـوند و (r, D) تعـداد نقـاط داده

در D است که توسط قانون r به درستی ارضا می شوند یعنی تالی قانون r با دسته ی نقطه داده ارضا شده یکی باشد. با توجه به این متغیــــر هــــا 3 معیــــار پشــــتیبان ( Support )، اطمینــــان ( Confidence ) و پوشش ( ( Coverage به ترتیب در (1) ، (2) و (3) تعریف شده اند.[4]
(1) n fire (r, D) Support(r, D) 

N
(2) n fire corr (r, D) Confidence(r, D) 
n fire (r, D)

(3) n fire corr (r, D) Coverage(r, D) 
ni

معیار (1) Support کسری از تعداد رکورد هایی که شـرایط مقدم قانون را ارضا می کنند، نسبت به کل رکوردهـا مـی باشـد. معیار (2) Confidence کسری از تعداد رکورد هـایی کـه شـرایط مقدم قانون را ارضا می کنند و کلاس آن هـا هـم صـحیح باشـد، نسبت به کل رکوردهایی که شرایط مقدم قانون را ارضا می کنند است و معیار (3) Coverage کسری از تعـداد رکـورد هـایی کـه شرایط مقدم قانون را ارضا می کنند و کلاس آن ها هـم صـحیح باشد، نسبت به کل رکورد های داخل آن کلاس می باشد. مـا در این مقاله از این سه معیار برای تمایز و رتبه بنـدی بـین قـوانین استفاده می کنیم.

-3 روشهای رتبه بندی و کارهای انجام شده

-1-3 رتبه بندی تکی قوانین دسته بندی

چندین رویکرد برای رتبه بندی تکی قوانین در نوشته هـای قبلی وجود داشته است.[4] سه تا از این روشها بر اساس ترکیـب های متفاوتی از اطمینان و پوشش یک قانون، جذابیت یک قانون

2