Geri Dön

Mst-based cluster analysis: A New algorithm for determining inconsistent edges

Mst tabanlı küme analizi: Tutarsız kenarları belirlemek için yeni bir algoritma

PDF İndir

  1. Tez No: 780706
  2. Yazar: FADİ ŞAAR
  3. Danışmanlar: YRD. DOÇ. DR. AHMET ERCAN TOPCU
  4. Tez Türü: Doktora
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2021
  8. Dil: İngilizce
  9. Üniversite: Ankara Yıldırım Beyazıt Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Bilimleri Bilim Dalı
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

Son yıllarda grafik tabanlı veri kümeleme algoritmaları, orta nokta tabanlı bölümleme yerine bağlantı tabanlı gerçekleştirdikleri için popüler hale gelmektedir. Minimum yayılma ağacı (MST) tabanlı veri kümelemeyle ilgili yöntemler, MST grafiklerinden tutarsız kenarları ortadan kaldırarak rastgele kümelerin şekillerini tanıyabilen grafik tabanlı algoritma türleridir. Tüm MST tabanlı veri kümeleme algoritmalarında, tutarsız kenarların tanımlanması, ele alınması gereken ana sorundur. MST grafiklerinde en uzun kenarlar, ideal koşullar altında tutarsız kenarlar olarak kabul edilmektedir. Bununla birlikte, aykırı değerler gerçek veri kümelerinde genellikle bulunmakta ve bu da en uzun kenarları hatalı küme ayırma göstergeleri yapmaktadır. Bu çalışmada, MST ve kritik mesafe yöntemi kullanılarak yeni bir veri kümeleme algoritması önerilmektedir. Önerilen algoritma, MST tabanlı veri kümelemesinin ana sorununu, yani veri kümesinin bazı aykırı değerler içermesi durumunda bile kümeleri elde etmek için tutarsız kenarları tanımlama ve kaldırma sorununu çözmektedir. MST'yi Öklid mesafesine dayalı olarak belirli bir ağırlıklı grafik üzerinde inşa ederek başlar ve ardından kritik mesafeyi bir eşik olarak kullanarak tutarsız kenarları ortadan kaldırarak grafiği kümelere ayırmaktadır. Optimal kümeleri elde etmek için hem MST hem de kritik mesafe metodolojisinin avantajlarının entegrasyonu, bu çalışmanın ana katkısıdır. Farklı veri kümeleri kullanılarak gerçekleştirilen deneysel analiz ve sonuçlar, önerilen kümeleme algoritmamızın en yaygın veri kümeleme algoritmalarına kıyasla daha iyi genel performans sağladığını kanıtlamaktadır.

Özet (Çeviri)

In recent years, graph-based data clustering algorithms have become popular as they perform connectivity-based rather than centroid-based partitioning. Methods related to minimum spanning tree (MST)-based data clustering are types of graph-based algorithms that can recognize arbitrary shapes of clusters by eliminating inconsistent edges from MST graphs. In all MST-based data clustering algorithms, definition of inconsistent edges is the main problem that needs to be addressed. The longest edges in MST graphs are considered as inconsistent edges under ideal conditions. Nevertheless, outliers often exist in real-world tasks, which makes the longest edges inaccurate cluster separation indicators. In this study, we propose a new data clustering algorithm using MST and a critical distance method. The proposed algorithm solves the main issue of MST-based data clustering, namely identifying and removing inconsistent edges to obtain clusters even in the event that the dataset contains some outliers. It begins by constructing the MST over a given weighted graph based on Euclidean distance and then splits up the graph into clusters by eliminating inconsistent edges using critical distance as a threshold. Integration of the advantages of both MST and critical distance methodology to obtain optimal clusters is the main contribution of this work. The conducted experimental analysis and results using different datasets prove that our proposed clustering algorithm yields better overall performance compared with the most common data clustering algorithms.

Geri Dön