Open Access

ARTICLE

Improved Data Stream Clustering Method: Incorporating KD-Tree for Typicality and Eccentricity-Based Approach

Dayu Xu^1,#, Jiaming Lü^1,#, Xuyao Zhang², Hongtao Zhang^1,*

1 College of Mathematics and Computer Science, Zhejiang A&F University, Hangzhou, 311300, China
2 College of Economics and Management, Zhejiang A&F University, Hangzhou, 311300, China

* Corresponding Author: Hongtao Zhang. Email:
# These authors contributed to the work equally and should be regarded as co-first authors

Computers, Materials & Continua 2024, 78(2), 2557-2573. https://doi.org/10.32604/cmc.2024.045932

Received 12 September 2023; Accepted 26 December 2023; Issue published 27 February 2024

Abstract

Data stream clustering is integral to contemporary big data applications. However, addressing the ongoing influx of data streams efficiently and accurately remains a primary challenge in current research. This paper aims to elevate the efficiency and precision of data stream clustering, leveraging the TEDA (Typicality and Eccentricity Data Analysis) algorithm as a foundation, we introduce improvements by integrating a nearest neighbor search algorithm to enhance both the efficiency and accuracy of the algorithm. The original TEDA algorithm, grounded in the concept of “Typicality and Eccentricity Data Analytics”, represents an evolving and recursive method that requires no prior knowledge. While the algorithm autonomously creates and merges clusters as new data arrives, its efficiency is significantly hindered by the need to traverse all existing clusters upon the arrival of further data. This work presents the NS-TEDA (Neighbor Search Based Typicality and Eccentricity Data Analysis) algorithm by incorporating a KD-Tree (K-Dimensional Tree) algorithm integrated with the Scapegoat Tree. Upon arrival, this ensures that new data points interact solely with clusters in very close proximity. This significantly enhances algorithm efficiency while preventing a single data point from joining too many clusters and mitigating the merging of clusters with high overlap to some extent. We apply the NS-TEDA algorithm to several well-known datasets, comparing its performance with other data stream clustering algorithms and the original TEDA algorithm. The results demonstrate that the proposed algorithm achieves higher accuracy, and its runtime exhibits almost linear dependence on the volume of data, making it more suitable for large-scale data stream analysis research.

---

Keywords

---