مریم امیری

خوشه‌‌بندی یکی از مهم‌ترین مباحث در زمینه‌ی داد‌ه‌کاوی و یادگیری ماشین است. هدف از خوشه-بندی تفکیک داده‌ها است به‌گونه‌ای که داده‌های موجود در یک خوشه بیشترین شباهت را به یکدیگر و کمترین شباهت را با اعضای خوشه‌های دیگر داشته باشند. یکی از مهم‌ترین الگوریتم‌های خوشه‌بندی الگورریتم K-means می‌باشد. در این الگوریتم ابتدا به تعداد خوشه‌ها به‌صورت تصادفی از داده‌های اصلی مراکز خوشه اولیه انتخاب می‌شوند و سپس عملیات یافتن خوشه‌ها اجرا می‌شود. الگوریتم K-means به دلایل زیادی همچون پیاده‌سازی ساده، ترجیح افراد برای استفاده از یک الگوریتم شناخته‌شده با نقاط ضعف معلوم به‌جای استفاده از یک روش با عملکرد بالقوه بهتر و نقاط ضعف پنهان و همچنین عملکرد محلی بسیارعالی یکی از پرطرفدارترین الگوریتم‌های خوشه‌بندی است. چالش اصلی در K-means انتخاب مراکز خوشه‌ها به‌صورت بهینه است؛ زیرا اگر مراکزخوشه‌ها به درستی انتخاب نشوند این الگوریتم در بهینه‌ی محلی گیر می‌افتد. درگذشته پژوهش‌های متعددی در زمینه انتخاب مراکز اولیه خوشه‌ها در الگوریتم K-means صورت گرفته است. این پژوهش‌ها به شش دسته تقسیم می‌شوند: روش‌های مبتنی بر نقاط تصادفی، روش‌های اکتشافی دورترین نقطه، روش‌های اکتشافی مرتب‌سازی، روش‌های مبتنی بر چگالی، روش‌های مبتنی بر طرح‌ریزی و روش‌های مبتنی بر تکنیک تقسیم. در این پایان‌نامه برای نخستین بار روش جدیدی برای انتخاب مراکز خوشه‌ها مبتنی بر الگوکاوی به نام DOMAIN ( a new centroiD initializatiOn Method for K-means bAsed on Itemset miNing) ارائه می‌شود. DOMAIN در دسته روش‌های مبتنی برچگالی قرار می‌گیرد. در DOMAIN ابتدا برای کاهش حجم داده‌ها، انتخاب ‌ویژگی با استفاده از معیار DBIndex روی داده‌ها اعمال می‌شود؛ سپس با استفاده از الگوریتم APRIORI الگوهای پرتکرار استخراج و برپایه‌ی این الگوها مراکز اولیه خوشه‌ها مشخص می‌شود. در نهایت الگوریتم K-means روی داده‌ها اجرا می‌شود تا خوشه‌های نهایی به‌دست آیند. DOMAIN علاوه بر الگوریتم‌های پایه K-means و K-means++ با دو روش جدید BDD و MKMDKM بر روی 17 مجموعه‌داده با ابعاد گوناگون ارزیابی می-شود. نتایج به‌دست آمده نشان می‌دهد در اغلب موارد، DOMAIN عملکرد بهتری نسبت به سایر روش‌ها دارد.