مقاله الگوریتم از برترین های داده کاوی

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

 الگوريتم از برترين هاي داده کاوي
چکيده - داده کاوي يکي از پيشرفتهاي اخير در حوزه کامپيوتر براي اکتشاف عمقي داده هاست . داده کاوي ، اطلاعات پنهاني که براي برنامه ريزيهاي استراتژيک ميتواند حياتي باشد را آشکار مي سازد. اين مقاله به بررسي ١٠ الگوريتم برتر داده کاوي منتخب کنفرانس بين المللي داده کاوي (ICDM) مي پردازد. الگوريتم هاي , PageRank, AdaBoost, KNN, Apriori, CART , k-Means, SVM, C45 , Navie beys, EM اين ١٠ الگوريتم برتر در زمره پرقدرت ترين الگوريتم هايي هستند که در تحقيقات مورد استفاده قرار ميگيرند. اين الگوريتم ها حوزه هاي clustering, statistical learning, association analysis, link mining, و classification ر پوشش ميدهند که همگي ازمباحث بسيار مهم در تحقيقات داده کاوي محسوب ميشوند. سعي بر آن است که اين الگوريتم ها توضيح داده شده ، نقاط قوت و ضعف آن ها نيز مورد بررسي قرار گيرد.
کلمات کليدي - داده کاوي ,Navie beys,EM ,PageRank, AdaBoost KNN, Apriori, CART , k-Means, SVM, C45 ,classification, clustering

مقدمه :
در دنياي امروزي، اطلاعات بعنوان يکي از فاکتورهاي توليدي مهم پديدار شده است . در نتيجه تلاش براي استخراج اطلاعات از داده ها توجه بسياري از افراد دخيل در صنعت اطلاعات را به خود جلب نموده است .
پيشرفتهاي حاصله در علم اطلاع رساني و تکنولوژي اطلاعات ، فنون و ابزارهاي جديدي را براي غلبه بر رشد مستمر و تنوع بانکهاي اطلاعاتي تامين مي کنند. اين پيشرفتها هم در بعد سخت افزاري و هم نرم افزاري حاصل شده اند.
داده کاوي يکي از پيشرفتهاي اخير در راستاي فن آوريهاي مديريت داده هاست . داده کاوي مجموعه اي از فنون است که به شخص امکان ميدهد تا وراي داده پردازي معمولي حرکت کند و به استخراج اطلاعاتي که در انبوه داده ها مخفي و يا پنهان است کمک مي کند. براي داده کاوي الگوريتم هاي بسياري معرفي شده است ولي موضوع مورد نظر انتخاب ده الگوريتم از اين تعداد الگوريتم و توصيفي مختصري از انهاست .
در نحوه انتخاب اين الگوريتم ها بايد گفت که ابتدا در کنفرانس بين المللي داده کاوي تلاشي صورت گرفت تا الگوريتم هاي مطرح و پرقدرتي که در مبحث داده کاوي مورد استفاده قرار ميگيرند شناسايي شوند و در مرحله بعد از يکسري کساني که جوايز IEEE را در تحقيقات و نوآوري کسب کرده بودند دعوت شد تا حداکثر ١٠ الگوريتم قوي ومطرح در داده کاوي را بعنوان کانديدا معرفي کنند در نتيجه الگوريتم ها در ده سرفصل زير دسته بندي شدند :

آنچه که در اين مقاله به آن مي پردازيم ده الگوريتم از برترين هاي انتخاب شده کنفرانس بين المللي داده کاوي است .
١. الگوريتم CART
١- مقدمه
درخت تصميم گيري CART١ در سال ١٩٨٤ بطور مشترک توسط لئو بريمن ٢، ژئوم فريدمن ٣ ، ريچارد اولشن
4 و چارلز استون ٥ نوشته شد که اين امر يک گام مهم در زمينه پيشرفت هوش مصنوعي ، سيستم يادگيري ، آمار غير پارامتري و استخراج داده ، را به بار آورد . CART به دليل سادگي مطالعه درختان تصميم گيري ، ابتکارات فني ارائه شده بوسيله آن ، مباحث پيچيده و پيشرفته بررسي داده هاي درختي شکل ، و نگرش توانمندانه آن به تئوري نمونه هاي وسيع براي درختان حائز اهميت است . با اينکه CART را مي توان تقريبا در هر حوزه اي يافت ولي به طور وسيع در زمينه هايي مانند مهندسي الکترونيک ، زيست شناسي ، مطالعات پزشکي و مباحث اقتصادي يافت مي شود . مثلا در تحقيقات بازاريابي يا اجتماعي .
٢- توصيف الگوريتم
درخت تصميم گيري CART يک روش تقسيم بندي بازگشتي باينري است . داده ها در اين الگوريتم بصورت خام استفاده مي شوند و هيچگونه پاکسازي نه نياز است نه پيشنهاد مي شود . درختان بدون استفاده از يک قانون متوقف کننده به رشد حداکثري خود مي رسند و سپس اصلاح مي شوند (که اين کار قسمت به قسمت انجام مي شود .) اصلاح تا ريشه ادامه دارد و با اصلاح پيچيدگي کار بالا مي رود. قسمت بعدي براي اصلاح بخشي است که کمترين کمک را به کارکرد کلي درخت در پردازش اطلاعات مي کند (و ممکن است در يک زمان بيشتر از يک بخش حذف شود). هدف مکانيزم CART توليد تنها يک درخت نيست بلکه توليد يک سري درختان اصلاح شده تو در توست که همه آن درختان بهينه داوطلب هستند . درخت با اندازه مناسب يا "درخت درست " به وسيله رزش گذاري عملکرد پيشگويانه هر درخت در توالي اصلاح ، شناخته مي شود . CART هيچگونه اندازه عملکرد داخلي براي انتخاب درخت براساس پردازش اطلاعات پيشنهاد نمي کند زيرا اين اندازه ها قابل اطمينان نيستند . به جاي آن عملکرد درخت در آزمايش داده هاي جداگانه (يا از طريق تائيد ميانه ) اندازه گيري مي شود و انتخاب درخت تنها پس از ارزشيابي آزمايش داده ها صورت مي گيرد . اگر هيچ آزمايش داده اي وجود نداشته باشد و تائيديه مياني انجام نشده باشد CART نمي تواند بهترين درخت توالي را مشخص کند . اين با روش هايي مانند C4.5 که مدل هاي برتر را بر اساس اندازه هاي پردازش داده ايجاد مي کنند کاملا در تضاد است .
مکانيزم CART شامل متعادل سازي رديف اتوماتيک (اختياري) و استفاده اتوماتيک از ارزش مفقود است و اجازه يادگيري حساس به هزينه ، ساخت خصوصيات ديناميک و تخمين احتمال درخت را مي دهد. CART همچنين زمينه جديدي براي نمايش چگونگي امکان استفاده از تائيديه ميانه براي تعيين عملکرد هر درخت در توالي اصلاح موجود، ارائه کرد که نشان ميدهد درختان در دسته هاي CV مختلف ممکن است با تعداد گره هاي نهايي هم تراز نباشند.
الگوريتم Apriori
١- مقدمه
بسياري از الگوريتم هاي الگو ياب ازقبيل الگوريتم هايي که براي ساختن درخت تصميم گيري ؛ استنتاج قوانين دسته بندي و جمع بندي داده ها که زياد در استخراج اطلاعات استفاده مي شوند ؛ در جامعه تحقيق يادگيري ماشين گسترش يافته اند . الگوي تکرار شونده و استخراج قوانين مرتبط يکي از معدود استثنائات اين شيوه است و معرفي اين روش در گذشته ؛ تحقيق براي استخراج را پيش برد.
الگوريتمهاي پايه اي ساده اند و به آساني قابل اجرا هستند . از آنجاييکه استقرا ء بسيار مهم بوده و شکل مجموعه داده به بازار معامله آن بستگي دارد فعاليتهاي زيادي براي بهبود کيفيت مناسبات ؛ يافتن بسته هاي کوچکتر ارائه و بسط انواع داده که مي تواند کنترل شود انجام گرفته است .
٢- توصيف الگوريتم
يکي از محبوب ترين ديد گاههاي استخراج اطلاعات ؛ يافتن يک مجموعه ارقام تکرار شونده از يک مجموعه داده اجرايي و استخراج قوانين مرتبط است . مشکل بطور رسمي در حالت زير ارائه شده است . اگر يک مجموعه از ارقام باشد و D يک مجموعه از معادله باشد که در آن هر عضو t يک مجموعه از ارقام است که هر عضو، يک شناساگر منحصر بفرد دارد که TID نام دارد .
يک عضو t شامل X که مجموعه اي از تعدادي از ارقام از مجموعه I است . در صورتيکه يک قانون مرتبط بمعني است که و در مورد D با ضريب C نيز صدق مي کند در صورتيکه تقسيم اعضا شامل Y نيز هستند . با وجود تعدادي از اعضاي D مشکل استخراج قوانين مرتبط ؛ همه قوانين مرتبطي که حمايت و اطمينان آنها کمتر از حداقل حمايت مخصوص استفاده کننده بنام MINSUP نيست را توليد مي کند و بدنبال آن حداقل اطمينان ( MINCONF) را ايجاد مي کند . يافتن مجموعه ارقام وسيع ( مجموعه ارقامي با فراواني برابر يا بيشتر از MINSUP ) ساده نيست و اين بدليل پيچيدگي محاسبات حاصل از انفجارهاي ترکيبي است . وقتي يک بار مجموعه ارقام وسيع کسب شوند ؛ ايجاد قوانين مرتبط با اطمينان برابر يا بيشتر از حداقل اطمينان (MINCONF) آسان خواهد بود. Apriori و AprioriTid که توسط R.AGRAWAL ,R.SRIKANT پيشنهاد شده اند ؛ الگوريتمهاي اصلي هستند که براي کار در مجموع ه هاي داده وسيع طراحي شده اند .
الگوريتم EM
١- مقدمه
الگوريتم بيشينه سازي مورد انتظار٦ در زمينه هايي چون ميانگين داده ، ماشين يادگيري و شناسايي، بسيار 7 کاربرد داشته است . برآورد درستنمايي ماکسيمم و استنباط درست نمايي در مرکز اهميت قضييه آماري و تجزيه و تحليل داده هستند . براورد درستنمايي ماکسيمم يک روش همه منظوره با خصوصيات قابل توجه است .
ترکيب توابع تعميم يافته ي متناهي يک روش انعطاف پذير رياضي را براي مدل سازي و دسته بندي داده هايي که به عنوان پديده تصادفي مشاهده شده اند را ارائه مي دهد.
در اينجا بر استفاده ي EM جهت پردازش ترکيب توابع تعميم يافته ي متناهي از طريق روش حداکثر احتمال تمرکز مي شود.
٢-توصيف الگوريتم :
الگوريتم EMيک الگوريتم تکراري است که در تکرار آن دو مرحله وجود دارد ، مرحله انتظار (مرحله E) و مرحله حداکثرسازي (مرحله M). در چارچوب داده هاي ناقص الگوريتم EM ، نشان دهنده بردار داده هاي مشاهده شده و z نشان دهنده بردار داده هاي ناقص است ، بردار هاي کامل به اين صورت بيان مي شود :

الگوريتم EMبه مشکل حل عمليات اطلاعات ناقص معادله ممکن نزديک مي شود. اين کار را غير مستقيم و با پيشرفت تکراري ، با توجه به عمليات ممکن " داده هاي کامل " يا عمليات انجام مي دهد . از آنجايي که اين کار به وضوح به داده هاي غير قابل مشاهده z بستگي دارد، مرحله
E طوري صورت مي گيرد که در آن لگاريتم توسط عمليات Q جايگزين مي شود و از اندازه اخير استفاده مي کند . به طور ويژه در (١+k) امين تکرار الگوريتم EM ، مرحله E به اين صورت عمل مي کند :

که در آن نتظار را با استفاده از بردار واحد نشان مي دهد . مرحله M تخمين را بوسيله ارزش که در عمليات با توجه به بر فضاي واحد ، به حداکثر مي رساند را به روز مي کند . مراحل Mو E به طور متوالي جابجا مي شوند تا تغييرات ارزش هاي الگوريتم متحمل کمتر از برخي آستانه هاي مشخص شده باشند. همانطور که در بخش قبل اشاره شد الگوريتم EMبراي افزايش تکرار هر يک از EMهاي ارزش محتمل ثابت و بصورت زير است :

مي توان نشان داد که مراحل Mو E شکل هاي ساده اي دارند در حاليکه عمليات چگالي محتمل داده هاي کامل از يک خانواده نمايي است . معمولا در عمل ، راه حل مرحله M به شکل محدود وجود دارد . در آن نمونه ها که اين راه حل وجود ندارد ممکن است نتوان ، براي يافتن ارزش که در کل عمليات را حداکثر مي کند ، تلاش کرد . براي چنين شرايطي ممکن است يک الگوريتم EM کلي (GEM) انتخاب شود که در آن مرحله M نيازمند اين است که طوري انتخاب شود که عمليات Q را بر ارزش موجود در افزايش دهد .
يعني

اتفاق بيفتد . برخي موانع الگوريتم EMهستند (a)که اين خود بخود اندازه ماتريس واريانس اندازه هاي واحد را توليد نمي کند . با اين حال اين شکل را مي توان به سادگي با استفاده از روش درست مربوط به الگوريتم EM از بين برد. (b) گاهي اوقات همگرايي بسيار آهسته صورت مي گيرد و (c) در برخي مشکلات مراحل Eو M مي توانند با بررسي جدا شوند.
الگوريتم KNN
١-مقدمه
يکي از ساده ترين و به نسبت طبقه بندي کننده هاي بديهي , طبقه بندي کننده Rote است که کل داده هاي تعليمي را به خاطر مي سپارد و طبقه بندي را فقط اگر نسبتهاي موضوع آزمايش بطور دقيق با صفات يکي از موضوعات آزمايش مطابقت کرد, طبقه بندي را اجرا ميکند.
يک مشکل بديهي اين راه اين است که بسياري از گزارشهاي آزمايش ، طبقه بندي نخواهند شد زيرا آنها بطور دقيق با هيچ کدام از گزارشات آموزشي مطابقت نميکند. موضوع ديگر, موقعي که دو يا چند گزارش آموزش داراي نسبتهاي مشابه اما برچسبهاي متفاوت رديف يا سري باشند, بوجود مي آيد.
در ساده ترين شکل , KNN ميتواند يک موضوع از رديفي که نزديکترين همسايگان يا اکثريت آنها در حال واگذاري هستنددرگير کند. بطور کلي KNN يک مورد ويژه علم است که وابسته به نمونه و مثل است . اين شامل منطق وابسته به مورد و نمونه است که در مورد داده هاي نمادين بحث ميکند. همچنين به علت سادگي آن KNN براي اصلاح و تغيير مسائل پيچيده طبقه بندي شده آسان است .
براي مثال , KNN بصورت ويژه براي طبقات با کيفيت چندگانه مناسب است درست بخوبي تقاضاهايي که در يک موضوع ميتواند در بسياري از طبقه بندي هاي اين کلاس داشته باشد. برخي از محققان دريافتند که KNN يک وسيله بردار حمايتي ابزاري را پشت سر گذاشته که يک طرح طبقه بندي بسيار پيچيده و ماهرانه است .
٢- توصيف الگوريتم
الگوريتم ١ يک خلاصه با سطح بالايي از روش طبقه بندي نزديکترين مجاور را فراهم ميکند. يک مجموعه آموزشي D و يک موضوع آزمايش Z داده شده است که يک بردار ارزشهاي صفات است و يک طبقه بندي رديف ناشناخته دارد. اين الگوريتم فاصله يا تشابه بين Z و همه موضوعات آموزشي را براي تعيين ليست نزديکترين مجاور به آن محاسبه ميکند. سپس يک طبقه را با بردن اکثريت موضوعات مجاور رديف به Z منتقل ميکند. روابط در يک روش نامشخص شکسته مي شود.

پيچيدگي ذخيره سازي الگوريتم است که در آن n تعداد موضوعات آموزش است . زمان پيچيدگي هم است . KNN از اکثر روشهاي طبقه بندي ديگر متفاوت است .
الگوريتم Naive Bayes
١- مقدمه
هدف ما در اين بخش ايجاد قانونيست که قادرمان سازد اعضاي بعدي را در يک دسته قرار دهيم و اينکار را تنها با داشتن بردارهايي از متغيرهاي توصيف کننده اجسام بعدي مي توانيم انجام دهيم . مشکلاتي از اين نوع که دسته بندي نظارت شده نام دارندهمه جا وجود دارند و روشهاي بسياري براي ايجاد چنين قوانيني بوجود آمده اند. يک روش بسيار مهم روش بيز ساده است که بيز سطحي,بيز ساده , و بيز مستقل نيز ناميده ميشود. اين روش به دلايل متعددي اهميت دارد. ساخت آن بسيار ساده است و نيازي به برنامه هاي تخمين پارامتر تکرارشونده پيچيده ندارد. يعني ميتوان از آن براي مجموعه داده هاي بسيار وسيع استفاده کرد و در نهايت اين روش معمولا فوق العاده عمل ميکند. ممکن است بهترين دسته بندي کننده ممکن ،در يک کاربرد خاص نباشد اما اغلب ميتوان به قوي بودن و عملکرد عالي آن اطمينان کرد.
٢-قوانين اصلي
براي راحتي تفسير در اينجا دو دسته را در نظر ميگيريم که بصورت رتبه بندي ميشود. هدف ما استفاده از يک مجموعه اعضاي اوليه با عضويتهاي دسته شناخته شده (مجموعه آموزشي) براي ايجاد يک امتياز است بطوريکه امتيازات بالاتر با اعضاي دسته ١ مرتبطند و امتيازات کوچکتر با اعضاي دسته ٠ در ارتباطند. بنابراين دسته بندي با مقايسه اين امتيازات با يک آستانه بدست مي آيد. اگر ما را اين احتمال تعريف کنيم که يک عضو با بردار مکان به دسته i تعلق داشته باشد هر عملکرد يکنواخت يک امتياز مناسب ايجاد خواهد کرد. بطور ويژه نسبت مناسب خواهد بود.
احتمال ابتدايي به ما ميگويد که را به نسبت تجزيه کنيم که در آن توزيع شرطي x براي اجسام دسته i است و احتمال تعلق يک عضو به دسته i است درصورتيکه ما چيز بيشتري درباره آن ندانيم (احتمال اوليه دسته i ). يعني نسبت به اين صورت در مي آيد:

براي استفاده از اين نسبت در دسته بندي ها ما نياز به تخمين داريم . اگر مجموعه آموزشي يک نمونه تصادفي از جمعيت کل باشد را ميتوان مستقيما از جمعيت اجسام دسته i محاسبه کرد. براي محاسبه روش بيز ساده اينطور در نظر ميگيرد که اعضاي x مستقلند, سپس هر يک از توزيعات يکنواخت را