بهبود سرعت همسایگی الگوریتم خوشه‌بندیdbscan

خوشه بندی به علت رشد روز افزون متن های تحت وب، پیکره های متنی، مقالات و غیره از اهمیت خاصی برخوردار است. خوشه بندی می تواند در بهبود نتایج به دست آمده از جستجوی ماشین های جستجو و دسته بندی اطلاعات موثر واقع شود. خوشه بندی مناسب امکان جستجوی ساده تر و دسترسی مناسب تری را برای استفاده از اطلاعات فراهم می کند. از آنجا که الگوریتم dbscan یکی از پرکاربردترین الگوریتم های خوشه بندی مبتنی بر چگالی می باشد، پس نیاز است تا مشکلات این الگوریتم به نحوی برطرف گردد. الگوریتم dbscan را می توان در جایی که نیاز به خوشه بندی داشت به کار برد که به عنوان مثال می توان در خوشه بندی متن، تصویر و نقشه برداری استفاده کرد. الگوریتم dbscan به دلیل سرعت پایینی که دارد کار بر روی این عنوان ها را کند و به تاخیر می اندازد و بعضی اوقات مجبور به انتخاب الگوریتمی دیگر به دلیل کندی در این الگوریتم هستیم. در اینجا سعی در بهبود سرعت این الگوریتم داریم که بتوان بیش از پیش از این الگوریتم در کاربردهای بیشتری بهره بگیریم. در این مقاله بهبودی برای الگوریتم dbscan ارائه شده است. یکی از چالش های حاظر در این الگوریتم محاسبات زیاد آن برای پرس و جو بین همه نقاط موجود در دیتاست است. در روش پیشنهادی زمانی که یک نقطه انتخاب می شود، دایره ای فرضی به شعاع eps در نظر گرفته می شود و این دایره به 16 قسمت مساوی تقسیم می شود. دورترین نقطه از نقطه مرکزی را در هر قسمت به عنوان نقطه بعدی برای بررسی در نظر می گیریم و روی مابقی نقاط که با یکدیگر هم پوشانی دارند برای گسترش خوشه، بررسی انجام نخواهیم داد. این کار باعث کاهش محاسبات در الگوریتم dbscan می شود و سرعت اجرای آن افزایش پیدا می کند. از دو معیار زمان اجرا و محاسبه کیفیت خوشه بندی بر اساس معیار cd استفاده شده است. نتایج ارزیابی روش پیشنهادی نشان دهنده عملکرد بهتری نسبت به روش دیگر است.