Abstract
Clustering analysis, an automatic process to find similar groups of objects from a database, has been studied for many years. With the increasing data size generated recently, clustering large databases poses a challenging task that must satisfy both the requirements of the computation efficiency and result quality. Among the existing clustering algorithms, grid-based algorithms generally have a fast processing time, which first employ a uniform grid to collect the regional statistic data and, then, perform the clustering on the grid, instead of the database directly. The performance of grid-based approach normally depends on the size of the grid which is usually much less than the database. However, for highly irregular data distributions, using a single uniform grid may not be sufficient to obtain a required clustering quality or fulfill the time requirement. In this paper, we propose a grid-based clustering algorithm using adaptive mesh refinement technique that can apply higher resolution grids to the denser regions. With the hierarchical AMR tree constructed from the multi-grain meshes, this algorithm can perform clustering at different levels of resolutions and dynamically discover nested clusters. Our experimental results also show the efficiency and effectiveness of the proposed algorithm compared to the methods using single uniform grids
چکیده
آنالیز خوشه بندی، پردازش اتوماتیک برای یافتن گروه‌های موضوعات مشابه در پایگاه داده، سالها مورد مطالعه قرار گرفته است. اخیرا با زیاد شدن اندازه داده‌های تولید شده، خوشه بندی پایگاه داده‌های بزرگ با چالشی مواجه شده است که باید نیازهای بازدهی محاسبات و کیفیت نتایج را جبران کند. از میان الگوریتمهای خوشه بندی موجود، الگوریتمهای شبکه‌ای اصولا زمان پردازش سریعتری دارند که ابتدا یک شبکه یکنواخت را برای جمع‌آوری داده‌های منطقه‌ای آماری را مهیا می‌کنند سپس به جای اینکه به طور مستقیم بر روی پایگاه داده کاری انجام دهند، به خوشه بندی شبکه می‌پردازند. البته برای توزیع داده‌های بسیار بی‌نظم استفاده از یک شبکه یکنواخت برای بدست آوردن کیفیت دسته‌بندی یا محدودیت زمانی مورد نیاز ممکن است کافی نباشد. در این مقاله ما تکنیک الگوریتم دسته‌بندی شبکه‌ای با استفاده از مش بندی سازگار را که می‌تواند شبکه‌های با رزولوشن بیشتر را در مناطق متراکمتر به کار ببرد پیشنهاد می‌دهیم. با درخت AMR مرتبه‌ای ایجادشده از مشهای دانه‌دانه‌ای این الگوریتم می‌تواند خوشه بندی با رزولوشن‌های متفاوت را انجام دهد و به طور پویا دسته‌‌های تودرتو را بیابد. نتایج آزمایشگاهی ما نیز بازدهی و تاثیرگذاری الگوریتم پیشنهاد شده را در مقایسه با روشهایی که از یک شبکه یکنواخت استفاده می‌کنند را نشان می‌دهد.
1-مقدمه
دسته‌بندی، فرآیندی برای یافتن گروه‌های مشابه از موضوعات موجود در پایگاه داده است که می‌تواند به توصیف کردن پراکندگی اطلاعات کمک کند. تحلیل دسته‌بندی سالها مورد مطالعه قرار گرفته است، مخصوصا در زمینه موضوعات مربوط به فواصل سه بعدی. در کل الگوریتمهای دسته‌بندی موجود به چهار مقوله تقسیم می‌شوند: روش تفکیکی، روش پلکانی، روش تراکمی و روش شبکه‌ای...