cs.LGMar 6, 2026

Single-pass Possibilistic Clustering with Damped Window Footprints

Authors: Jeffrey Dale, James Keller, Aquila Galusha

Organizations: Electrical Engineering and Computer Science Department, University of Missouri, Columbia, MO 65211

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Streaming clustering is a domain that has become extremely relevant in the age of big data, such as in network traffic analysis or in processing continuously-running sensor data. Furthermore, possibilistic models offer unique benefits over approaches from the literature, especially with the introduction of a "fuzzifier" parameter that controls how quickly typicality degrades as one gets further from cluster centers. We propose a single-pass possibilistic clustering (SPC) algorithm that is effective and easy to apply to new datasets. Key contributions of SPC include the ability to model non-spherical clusters, closed-form footprint updates over arbitrarily sized damped windows, and the employment of covariance union from the multiple hypothesis tracking literature to merge two cluster mean and covariance estimates. SPC is validated against five other streaming clustering algorithm on the basis of cluster purity and normalized mutual information.

Figures & tables

Fig. 1 : Motivation for using a possibilistic model over a probabilistic model in SPC demonstrated on a synthetic dataset of two near-overlapping circles.
Fig. 2 : Illustration of why covariance union is needed to combined covariance matrices of two structures with unequal means.
Figure 3 - Aggregation Dataset
Parameternnγ\gammaβ\betammε\varepsilonwminw_{min}NLTmaxNLT_{max}
Value300.00.01.50.950.013
Table 1: Parameter values used for SPC experiments in this manuscript.
Fig. 3 : SPC performance on the synthetic clustering dataset of Gionis et al. [ 9 ] .
Fig. 4 : Nonstationary synthetic dataset of three sine waves illustrating the utility of SPC’s forgetting factor in modeling newer data with finer detail. Old points are still modeled, but with less granularity. Here, SPC was run with a high forgetting factor of γ=0.1\gamma=0.1 .
Fig. 5 : SPC performance on an overlapping cluster dataset.
Fig. 6 : Comparison of streaming clustering algorithms on a high dimensional dataset [ 8 ] of 1024 points from 16 Gaussian clusters in R1024\mathbb{R}^{1024} with respect to cluster purity and normalized mutual information (NMI).
More in this topic

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 342 papers

Explore similar work

CardsList

  1. Scalable Model-Based Clustering with Sequential Monte Carlo

    Apr 16, 2026Connie Trojan, Pavel Myshkov, Paul Fearnhead +3Clustering

    Lancaster University · Microsoft Research

  2. Feature Incremental Clustering with Generalization Bounds

    Mar 23, 2026Jing Zhang, Chenping HouClusteringGeneralization Bounds

    Key Laboratory of Computing and Stochastic Mathematics (Ministry of Education), School of Mathematics and Statistics, Hunan Normal University, Changsha, Hunan 410081, P. R. China. · College of Liberal Arts and Sciences, National University of Defense Technology, Changsha, Hunan, 410073, China.

  3. Persistent Multiscale Density-based Clustering

    Dec 18, 2025Daniël Bot, Leland McInnes, Jan AertsClusteringUnsupervised Clustering

    1UHasselt, Data Science Institute (DSI) · 2Tutte Institute for Mathematics and Computing · 3KU Leuven, Augmented Intelligence for Data Analytics Lab, Department of Biosystems