بخشی از مقاله
چکیده
خوشهبندی از روشهای مهم در دادهکاوی میباشد که به دلیل نزدیک بودن با مسائل طبیعی در بسیاری از
زمینهها مورد توجه قرار گرفته است. یکی از مهمترین الگوریتمهای خوشهبندی که به طور گسترده به کار
میرود الگوریتم k-means میباشد. الگوریتم k-means کاربردهای بسیاری در حیطههای مختلف علمی و صنعتی دارد. با وجود سادگی و آسان بودن قابلیت پیاده سازی این الگوریتم، چالشهایی نیز دارد، که این چالشها در سالهای اخیر با به کارگیری k-means به صورت ترکیبی با سایر الگوریتمهای فرا
مکاشفهای برطرف شده است. در این مقاله یک دستهبندی از روشهای فرا مکاشفهای جدیدی که به
منظور برطرف سازی معایب الگوریتم k-means، به طور ترکیبی به کار رفتهاند، صورت گرفته است.
واژههای کلیدی: خوشهبندی - الگوریتم - k-means الگوریتم ترکیبی - روشهای فرامکاشفهای
1
1ـ مقدمه
در انواع مختلف تحقیقات علمی و تقریباً در تمامی کوششهای عملی که در حین انجام آنها شواهد و مدارک گوناگون جمع-آوری میشود، با یک مسئلهی مهم مواجه هستیم: فهم و درک دادههای در دسترس. عصر فناوری اطلاعات که جلوهی بارز آن حجم وسیع دادهها میباشد، اهمیت مسئله مذکور را افزایش داده و برخورد با آن را دشوارتر ساخته است. جمعآوری مقادیر عظیم
دادهها در هر زمان و در هر مکان، به یک واقعیت انکارناشدنی در زندگی امروز تبدیل شده است.
دانش نوین دادهکاوی از جمله دانشهای در حال توسعهای است که در سالهای اخیر در تمامی عرصهها جایگاه خود را
تثبیت کرده است به گونهای که رشد آن در مقایسه با سایر دانشهای برتر بسیار فزاینده است. هدف دادهکاوی در یک حیطه معین علمی، عبارت است از ایجاد درک از حجم زیادی از دادههایی که در اغلب موارد به صورت بدون نظارت جمعآوری شدهاند. دادهکاوی عبارت است از اقتباس یا استخراج دانش از مجموعهای از دادهها و به بیان دیگر، دادهکاوی فرآیندی است که با استفاده از تکنیکهای هوشمند، دانش را از مجموعهای از دادهها استخراج میکند .[1] در این میان، خوشهبندی در قالب مفهوم و
الگوریتمی غنی جهت تحلیل و تفسیر دادهها مطرح شده است. خوشهبندی، به دنبال کشف ساختار در دادههای جمعآوری شده
میباشد.
الگوریتم k-means از مهمترین الگوریتمهای خوشهبندی محسوب میشود که کاربردهای بسیاری در حیطههای مختلف علمی و صنعتی دارد. این الگوریتم با وجود برخورداری از مزایایی همچون سادگی، آسان بودن قابلیت پیاده سازی، سرعت بالا و
مناسب بودن برای مجموعه داده های بزرگ، چالشهایی نیز دارد. از معایب این الگوریتم میتوان نیاز داشتن به تعیین تعداد خوشه
ها (k) از ابتدا، حساس بودن به داده های نویزی و پرت، وابستگی نتایج نهایی به مقداردهی مراکز اولیه مراکز و تعداد خوشه ها، گیر کردن الگوریتم در بهینه ی محلی و هم گرایی زودرس را نام برد. این چالشها در سالهای اخیر با به کارگیری k-means به صورت ترکیبی با الگوریتمهای فرا مکاشفهای به میزان قابل ملاحظهای بر طرف شده است. از مهمترین الگوریتم های فرا مکاشفهای که به صورت ترکیبی با k-means به کار رفتهاند، میتوان الگوریتم بهینهسازی اجتماع ذرات (PSO)، الگوریتم
2
همایش منطقه ای علوم کامپیوتر ، مهندسی کامپیوتر و فناوری اطلاعات دانشگاه آزاد اسلامی واحد دورود،خرداد ماه 1391
بهینهسازی کلونی مورچهها (ACO)، الگوریتم ژنتیک (GA) و الگوریتم سیستم ایمنی مصنوعی (AIS) را نام برد. از مهمترین مزایای این الگوریتمهای ترکیبی در کاربرد خوشهبندی، نیاز نداشتن به مشخص بودن خوشه ها از ابتدا، کشف خوشه ها با اشکال
دلخواه، یافتن پاسخ بهینه سراسری و کاهش میزان محاسبات میباشد.
در ادامه این مقاله ابتدا الگوریتم خوشهبندی k-means معرفی شده و سپس مرور مختصری بر الگوریتمهای فرا مکاشفهای
میشود و بعد از آن برخی از مهمترین روشهای ترکیبی الگوریتم k-means و الگوریتمهای فرا مکاشفهای در زمینه خوشه-
بندی به منظور برطرف سازی مشکلات k-means معرفی میشود، و در نهایت نتیجه گیری از مطالب ارائه شده بیان میگردد.
-2 الگوریتم k-means
الگوریتم k-Means از سادهترین الگوریتمهای یادگیری بدون نظارت است که مسائل خوشهبندی معروف را حل
میکند. این الگوریتم اولین بار توسط استارد لوید در سال 1957، ارائه شده است. الگوریتم k-means در حوزههای مختلفی از جمله پردازش تصاویر، شناسایی الگو، بازیابی اطلاعات، تشخیص گفتار و دادهکاوی کاربرد دارد. خوشهبندی در دادهکاوی برای کشف اطلاعات و ساختار جدید از دادههای موجود به کار میرود.
الگوریتم k-means از یک شیوه ساده برای بخشبندی یک مجموعه داده به یک تعدادِ از پیش تعیین شده (k)
خوشه، استفاده میکند. ایده اصلی، تعریف k مرکز برای هر یک از خوشه ها میباشد. این مراکز بایستی با دقت زیاد انتخاب شوند، زیرا مراکز مختلف، نتایج مختلف را در پی دارند. بنابراین بهترین انتخاب قرار دادن مراکز در فاصله هر چه بیشتر از یکدیگر میباشد. گام بعدی تخصیص هر الگو به نزدیکترین مرکز میباشد. وقتی همه نقاط به مراکز موجود تخصیص داده شدند، مرحله اول تکمیل شده است و یک گروهبندی اولیه انجام میشود. در این مرحله نیاز است که k مرکز جدید برای خوشه های مرحله قبل محاسبه شود. بعد از تعیین kمرکز جدید، مجدداً دادهها به مراکز مناسب
تخصیص داده میشود. این مراحل آنقدر تکرار میشود تا اینکه k مرکز، جابجا نشوند. روال این الگوریتم همواره
درصدد کمینه کردن یک تابع هدف، که تابع مربع خطا میباشد، است،. الگوریتم k-means علیرغم سادگی یک روش پایه برای بسیاری از روشهای خوشهبندی دیگر (مانند خوشهبندی فازی) محسوب میشود. این روش، روشی انحصاری
3
و افرازبندی محسوب میشود. برای اندازهگیری مشابهت و نزدیکی نقاط از فاصلهی اقلیدسی، (1) به عنوان تابع هدف k-means استفاده می شود.
