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

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