یک معیار شباهت مبتنی بر محبوبیت برای بهبود کارایی خوشه بندی طیفی

روش های خوشه بندی طیفی، به دلیل قابلیتی که در تشخیص خوشه های با شکل های مختلف دارند، بسیار مورد توجه قرار گرفته اند. کارایی این روش ها وابستگی شدیدی به نحوه تعریف شباهت بین نمونه ها دارد. بنابراین، تلاش ها برای بهبود کارایی این الگوریتم ها بر روی ارایه معیار شباهت مناسب تر متمرکز بوده است. در این مقاله، به هر نمونه شاخصی تحت عنوان شاخص محبوبیت نسبت می دهیم که بیانگر میزان مرکزیت آن نمونه در مجموعه داده است. همچنین، معیار شباهت جدیدی مبتنی بر محبوبیت نمونه ها پیشنهاد و بر پایه آن الگوریتم خوشه بندی طیفی مبتنی بر محبوبیت را پیشنهاد می دهیم. از آنجا که شاخص محبوبیت پیشنهادی مستقل از چگالی محلی خوشه هاست، الگوریتم پیشنهادی می تواند در خوشه بندی داده های با چگالی های متفاوت موفق عمل کند. معیار پیشنهادی ویژگی سودمند دیگری نیز دارد؛ شباهت نمونه ها در معیار پیشنهادی با توجه به محبوبیت آنها و جایگاه یک نمونه در لیست همسایگان نمونه دیگر محاسبه می شود. این ویژگی به جداسازی خوشه های با همپوشانی بالا کمک بسیاری می کند. به دلیل سادگی تعریف پیشنهادی برای شاخص محبوبیت، الگوریتم محاسبه ماتریس شباهت پیشنهادی پیچیدگی محاسباتی بسیار پایینی دارد. برای مطالعه و مقایسه کارایی الگوریتم خوشه بندی پیشنهادی با همتاهای آن، از منظر معیار انطباق NMI، آزمایش هایی بر روی شش مجموعه داده مصنوعی و پانزده مجموعه داده واقعی انجام داده ایم. نتایج نشان می دهد که الگوریتم خوشه بندی پیشنهادی و معیار شباهت مطرح در آن کارایی بهتری نسبت به روش های همتای آن از جمله معیار شباهت مبتنی بر میانگین محلی، معیار خود- تنظیم و معیار شباهت محلی مبتنی بر همسایه های مشترک دارد و در اغلب موارد بهترین عملکرد را به دست می آورد.

Keywords:

خوشه بندی طیفی , شاخص محبوبیت , معیار شباهت مبتنی بر محبوبیت , گراف همسایگی , ماتریس شباهت