Gerçek zamanlı akan veri probleminde ağaç veri yapısı ve mikro kümeler ile düzensiz kümeler oluşturmak
Defining irregular clusters by using tree data structure and microclusters in real time streaming data problem
Yazar: BERFİN ERDİNÇ
Danışman: DR. ÖĞR. ÜYESİ MAHMUT KAYA ; DR. ÖĞR. ÜYESİ ALİ ŞENOL
Siirt Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2023
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Akan veri kümeleme, akan verileri işlemek ve gerçek zamanlı olarak anlamlı bilgiler çıkarmak için popüler bir alandır. Akan veri kümeleme, benzerlik kriterlerine dayalı olarak kümelerin tanımlanması ve güncellenmesi için verimli yaklaşımlar sağlar. Bu alandaki en önemli problemlerden birisi dairesel olmayan kümeleri tanımlamaktır. Bununla beraber, akan veri kümeleme alanlarındaki aykırı değerler ve gürültülü veriler, kümeleme performansını önemli ölçüde düşürebilir. Buna karşın, dairesel olmayan kümeler tanımlayabilen yöntemler, algoritmaların kümeleme kalitesini iyileştirebilir. Bu problemlere çözüm olarak, bu çalışmada MCMSTStream adlı yeni bir akan veri kümeleme yaklaşımı önerilmiştir. Önerilen algoritma, yüksek kümeleme başarısı elde etmek için k-boyutlu ağaç tarafından tanımlanan mikro küme yapısını ve Minimum Kapsayan Ağacı (MKA) tabanlı yöntemleri birleştirmektedir. Önerilen algoritmamız 5 aşamadan oluşmaktadır. Bunlar: k-boyutlu ağaç tabanlı mikro küme oluşturma, tanımlanmış mikro kümelere MKA uygulayarak makro kümeler oluşturma, yeni veri gelmesi sonucu mikro kümelerin tanımlanması veya veri sayısının eşik değeri N'nin altına düşmesi sonucu verinin ömrünü tamamlaması nedeniyle mikro kümelerin silinmesidir. Sonrasında makro kümelere yeni mikro kümelerin atanması veya sahip oldukları mikro küme sayısı n_micro'nun altına düştüğünde makro kümelerin silinmesidir. Son olarak tüm sistemin bilgilerinin güncellenmesi de önerilen algorimanın son aşamasını oluşturmaktadır. Bu çalışmada önerilen MCMSTStream algoritması, aykırı değerlere ve gürültülü verilere karşı dayanıklıdır ve keyfi şekilli kümeleri tanımlayabilme kabiliyetine sahiptir. Ayrıca, önerilen algoritma hızlı ve yüksek boyutlu verileri işleme yeteneğine de sahiptir. MCMSTStream algoritmasının başarısı hem Adjusted Rand Index (ARI) hem de Saflık (Purity) indeksleri kullanılarak ölçülmüştür. Algoritmamızın verimliliğini ortaya koymak için, bu alandaki başarılı algoritmalardan DenStream, DBSTREAM ve KDAR Stream algoritmaları ile karşılaştırılmıştır. Bulgular tablo ve grafiklerle ayrıntılı olarak sunulmuştur. Sonuçlar, önerilen algoritmanın karşılaştırılan akan veri kümeleme algoritmalarından daha iyi performans gösterdiğini ortaya koymaktadır. Ayrıca, çalışmanın zamanı karmaşıklığı da oldukça tatmin edicidir.

Abstract:
Streaming data clustering is a popular field for processing and extracting meaningful information from data streams in real-time. Streaming data clustering offers efficient approaches for defining and updating clusters based on similarity criteria. One of the significant challenges in streaming data clustering is identifying non- spherical clusters. However, outliers and noisy data in the streaming data clustering area can significantly degrade clustering performance. In contrast, methods capable of defining non-spherical clusters can enhance the clustering quality. As a solution to these problems, this study proposes a new streaming data clustering approach called MCMSTStream. The proposed algorithm combines the KD-Treebased micro-cluster and Minimum Spanning Tree (MST) based methods to achieve high clustering performance. Our proposed algorithm consists of five stages, which include defining KD-Tree-based microclusters, and then forming macro-clusters by applying MST to defined micro-clusters, defining new microclusters when new data arrives or deleting micro-clusters when the number of data falls below the threshold value of N, assigning new micro-clusters to macro-clusters or deleting macro-clusters when the number of micro-clusters falls below n_micro. As the last step, all system information is updated. The MCMSTStream algorithm that is proposed in this study is robust against outliers and noisy data and can detect arbitraryshaped clusters. Additionally, the proposed algorithm is fast and capable of handling high-dimensional data. In this study, the proposed algorithm's clustering success is measured using the Adjusted Rand Index (ARI) and Purity indices. To demonstrate the efficiency of our algorithm, we conducted experimental studies on state-of-the-art algorithms such as DenStream, DBSTREAM, and KD-AR Stream algorithms. The findings are presented in tables and graphs in detail. The results indicated that the proposed algorithm outperformed the compared algorithms. Furthermore, the time complexity of the algorithm is quite satisfactory.