A new hybrid method based on partitioning-based DBSCAN and ant clustering

 

a b s t r a c t

Clustering problem is an unsupervised learning problem. It is a procedure that partition data objects into matching clusters. The data objects in the same cluster are quite similar to each other and dissimilar in the other clusters. Density-based clustering algorithms find clusters based on density of data points in a region. DBSCAN algorithm is one of the density-based clustering algorithms. It can discover clusters with arbitrary shapes and only requires two input parameters. DBSCAN has been proved to be very effective for analyzing large and complex spatial databases. However, DBSCAN needs large volume of memory support and often has difficulties with high-dimensional data and clusters of very different densities. So, partitioning-based DBSCAN algorithm (PDBSCAN) was proposed to solve these problems. But PDBSCAN will get poor result when the density of data is non-uniform. Meanwhile, to some extent, DBSCAN and PDBSCAN are both sensitive to the initial parameters. In this paper, we propose a new hybrid algorithm based on PDBSCAN. We use modified ant clustering algorithm (ACA) and design a new partitioning algorithm based on ‘point density’ (PD) in data preprocessing phase. We name the new hybrid algorithm PACA-DBSCAN. The performance of PACA-DBSCAN is compared with DBSCAN and PDBSCAN on five data sets. Experimental results indicate the superiority of PACA-DBSCAN algorithm.

 

 دانلود رایگان مقاله انگلیسی1.34 MB

 

چکیده
مسئله خوشه بندی یک مسئله یادگیری نظارت نشده است که روالی است که شی های داده ای را در خوشه های منطبق پارتیشن بندی می کند. شی های داده ای موجود در خوشه یکسان شباهت زیادی به یکدیگر دارند و با خوشه های دیگر شباهتی ندارند. الگوریتم های خوشه بندی مبتنی بر چگالی، خوشه ها را بر اساس چگالی نقاط داده ای موجود در یک منطقه پیدا می کنند. الگوریتم DBSCAN یکی از الگوریتم های خوشه بندی مبتنی بر چگالی است. می تواند خوشه هایی با شکل های دلخواه را کشف کند و تنها به دو پارامتر ورودی نیاز دارد. ثابت شده است که DBSCAN برای آنالیز پایگاه داده های فضایی بزرگ و پیچیده موثرتر است. با اینحال، DBSCAN به حجم بالایی از پشتیبانی حافظه نیاز دارد و اغلب در رابطه با داده هایی با ابعاد زیاد و خوشه هایی با چگالی های خیلی متفاوت با مشکلاتی مواجه می شود. بنابراین، الگوریتم DBSCAN مبتنی بر پارتیشن بندی (PDBSCAN) جهت حل این مسائل پیشنهاد شده است. ولی PDBSCAN به نتیجه ضعیفی دست خواهد یافت زمانیکه چگالی داده ها غیریکنواخت است. در ضمن، تاحدی، DBSCAN و PDBSCAN هر دو به پارامترهای اولیه حساس هستند. در این مقاله، یک الگوریتم ترکیبی جدید مبتنی بر PDBSCAN پیشنهاد می کنیم. از الگوریتم خوشه بندی مورچه ی اصلاح شده (ACA) استفاده می کنیم و یک الگوریتم پارتیشن بندی جدید بر مبنای چگالی نقطه ای (PD) در فاز پیش پردازش داده ها طراحی می کنیم. الگوریتم ترکیبی جدید را PACA-DBSCAN می نامیم. کارایی PACA-DBSCAN با DBSCAN و PDBSCAN روی پنج مجموعه داده مقایسه می شود. نتایج تجربی، برتری الگوریتم PACA-DBSCAN را نشان می دهند.

 

 تعداد صفحات مقاله انگلیسی:   9  صفحه

 تعداد صفحات فارسی مقاله ترجمه شده :    28  صفحه

 قالب بندی فایل: فایل ورد (Word)

اضافه کردن نظر