یک الگوریتم خوشه بندی سلسله مراتبی ترکیبی برپایه روش مبتنی بر تراکم

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشگاه تربیت دبیر شهید رجایی، دانشجوی کارشناسی ارشد

2 دانشگاه تربیت دبیر شهید رجائی، دکتری مهندسی کامپیوتر

چکیده

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

کلیدواژه‌ها


عنوان مقاله [English]

A combinational hierarchical clustering algorithm on the basis of density-based methods

نویسندگان [English]

  • Alireza Latifi Pakdehi 1
  • Negin Daneshpour 2
چکیده [English]

Clustering is one of the most important field of data mining that aims to divide data into meaningful
subsets which are called clusters. This technique involves the process of finding natural groupings in the
data set based on the similarities and di similarities which a little or no information about data are
available. Over the decades, many clustering algorithms are created in different approaches or a
combination of them. In this paper, an algorithm based on density and hierarchical approaches is
presented. DBSCAN is one of the algorithms presented in the density-based approach. This algorithm
requires two parameters that its determination is a great challenge. In the proposed method, DBSCAN
algorithm parameters can be set without user involvement, so that potential clusters are found
automatically. The clusters which are so close to each other are merged together until the quality of the
final clusters to be enhanced properly. Thus, clusters could be more accurate and high quality. Finally, in
order to test the new proposed algorithm, the real dataset in the UCI machine learning repository was
used. The results indicate that the new algorithm is more efficient and accurate, and its speed is better
than previous methods.

کلیدواژه‌ها [English]

  • data mining
  • combinational clustering
  • hierarchical clustering
  • density-based clustering
دوره 9، شماره 1 - شماره پیاپی 33
شماره 32 و 33 بهار 1397
خرداد 1397
صفحه 133-143
  • تاریخ دریافت: 15 شهریور 1396
  • تاریخ بازنگری: 09 مرداد 1397
  • تاریخ پذیرش: 15 مهر 1397
  • تاریخ اولین انتشار: 15 مهر 1397