16023

16023

ارائه الگوريتمي مقياس‌پذير براي خوشه‌بندي داده‌ها

كارشناسي ارشد

نرم‌افزار

اسفند ماه 1394

اسفند ماه 1394

دكتر حسن نادري

كامپيوتر

چكيده خوشه‌بندي اسناد متني در زمينه‌هاي مختلف مانند داده‌كاوي متون اخبار و يا پردازش پايگاه‌‌هاي داده اينترنتي كاربرد گسترده‌اي دارد. در اين تحقيق، يك الگوريتم كارآمد مبتني بر خلاصه‌سازي براي خوشه‌بندي متون ارائه شده است. به منظور افزايش عملكرد اين الگوريتم در خوشه‌بندي پايگاه‌هاي متني مختلف، سه پارامتر ميزان خلاصه‌سازي متن (آلفا)، حذف كلمات با تعداد تكرار كمتر از بتا و يا بيشتر از گاما در پايگاه داده تعريف شد كه مقدار بهينه آنها براي هر پايگاه قابل تنظيم بود. الگوريتم پيشنهادي در اين تحقيق بر خلاف تحقيقات ديگر در زمينه متن‌كاوي، پيش‌پردازش ساده‌اي دارد و از يك تنظيم‌كننده لاپلاسين براي كاهش تنكي ماتريس ويژگي‌ها كه يكي از محدوديت‌هاي موجود در زمينه پردازش داده‌هاي متني است، بهره گرفته شده است. عملكرد الگوريتم بر روي سه پايگاه داده مرجع 20Newsgroups، Reuters-21578 و Reuters-50-50 با استفاده از خوشه‌بندهاي K ميانگين، C ميانگين فازي و ماشين بردار پشتيبان مورد ارزيابي قرار گرفت كه نتايج نشان دادند خوشه‌بند ماشين بردار پشتيبان در مقايسه با خوشه‌بندهاي ديگر دقت مناسب‌تري دارد. دقت خوشه‌بندي مبتني بر برچسب براي اين پايگاه‌هاي داده با استفاده از اين خوشه‌بند به ترتيب 1/64 ٪، 0/71 ٪، و 9/69٪ بود. هم‌چنين، ميزان خلاصه‌سازي هر يك از اين پايگاه‌ داده‌ها براي دستيابي به دقت بهينه، به ترتيب 40٪، 50٪، و 30٪ به دست آمد كه دقت خوشه‌بندي مبتني برچسب الگوريتم پيشنهادي به ازاي اين سطوح خلاصه‌سازي براي اين پايگاه‌هاي داده به ترتيب 54٪، 55٪ و 61٪ بود و در اين حالت، زمان پردازش در مقايسه با شرايطي كه از تمام كلمات كليدي براي خوشه‌بندي استفاده مي‌شد، به طور معناداري كاهش يافت. هم‌چنين تاثير پارامترهاي بتا و گاما بر روي دقت خوشه‌بندي و زمان پردازش مورد بررسي قرار گرفت و مقادير بهينه آن براي هر يك از پايگاه‌هاي داده گزارش شد. به نظر مي‌رسد با تعريف كلمات بازدارنده فارسي بتوان الگوريتم پيشنهادي را به طور كارآمد براي خوشه‌بندي متون فارسي نيز تعميم بخشيد. روش‌هاي قبلي‌ ارائه شده در اين زمينه به صورت متمركز و مقياس پذير مي‌‌باشد. اما روش پيشنهادي در اين پايان نامه به صورت متمركز و مقياس پذير است. اين به اين معني‌ است كه زماني‌ كه داده به حدي مي‌‌رسد كه ديگر در حافظه جا نمي‌‌شود، با خلاصه سازي داده و كاهش حجم آن به طوري كه در حافظه جا شود و بتوان به صورت متمركز و در يك سيستم عمليات خوشه بندي را با روي آن انجام داد. واژه‌هاي كليدي: خوشه‌بندي متمركز ، مقياس پذير ، خلاصه‌سازي، روش ماشين بردار پشتيبان