WorksComputer Science
Inference-Time Prior Adaptation for Imbalanced Data Streams under Concept Drift
Abstract
Data stream classification under concept drift and class imbalance requires models to adapt continuously while maintaining strong minority-class performance. Many existing approaches rely on active memory management, in- cluding instance removal, memory restructuring, resampling, and synthetic data generation. We present PAI-KNN, a k-nearest neighbor classifier that adapts via inference-time prior adjustment rather than memory modification. PAI-KNN main- tains a simple sliding-window buffer and dynamically adjusts its decision rule using class prior estimates derived from recent observations. Evaluated on a mul- titude of synthetic data streams covering various imbalance and drift scenarios, PAI-KNN achieves competitive performance with state-of-the-art methods, per- forming particularly well under scenarios involving dynamic class imbalance and concept drift. These findings highlight the potential of inference-time adaptation in challenging non-stationary environments and suggest that adaptation in memory- based stream classifiers need not rely exclusively on memory modification.
Introduction
Data stream classification [18] often requires models to operate under two simultaneous challenges: concept drift and class imbalance. As data distributions evolve over time, classifiers must continuously adapt to changing data while maintaining reliable performance on underrepresented classes. This problem arises in numerous real-world applications, including fraud detection, network monitoring, and predictive maintenance.
Existing approaches address concept drift and class imbalance in different ways. Many stream classifiers are model-based, maintaining either a single evolving model [10], [20] or a pool of models that are continuously updated, reweighted, or replaced over time [5], [13], [8], [21], often combined with drift detectors like ADWIN [4]. K-nearest neighbor (KNN) classifiers, in contrast, are instance-based or lazy learners that maintain explicit memories of previously observed instances and perform prediction directly from stored observations. Several KNN-based stream classifiers have been proposed that address concept drift and class imbalance through increasingly sophisticated active memory management mechanisms [14, 1]. Adaptation is typically achieved through instance removal, restructuring, compression, or balancing operations. While effective, active buffer-management strategies increase algorithmic complexity and may prematurely alter or discard useful information. In this paper, we investigate whether adaptation in KNN-based stream classifiers must occur through memory modification. We propose PAI-KNN, a -nearest neighbor classifier that maintains a simple sliding-window memory and adapts through inference-time prior adjustment. By shifting adaptation from memory management to inference, PAI-KNN responds to changing class distributions without the need for expensive memory management mechanisms. We evaluate PAI-KNN on a benchmark of synthetic data streams [2] covering diverse imbalance and drift scenarios. Despite its simplicity, PAI-KNN achieves competitive performance with state-of-the-art methods and performs particularly well under scenarios involving high class imbalance and concept drift. These findings suggest that inference-time prior adaptation can provide a simple and effective alternative to complex memory management by avoiding structural assumptions. The rest of the paper is organized as follows: § 2 introduces the preliminaries and basic concepts. Related work is discussed in § 3. In § 4, we present our proposed method PAI-KNN. The experimental evaluation is detailed in § 5. Conclusions and outlook are provided in § 6.
Preliminaries and basic concepts
A data stream is a potentially infinite sequence of instances where denotes a -dimensional feature vector arriving at time . Under the standard prequential evaluation protocol, an observation is first classified, producing a prediction . The true label is revealed subsequently and can be used to update the classifier. Instance-label pairs are assumed to be sampled from evolving data distributions . Concept drift [7] may hence arise from class priors , likelihoods , or posteriors changing.
For classification problems, the imbalance ratio quantifies the class-prior distribution and is defined as the (potentially infinite) ratio of majority to minority class frequencies over a set of instance labels (in case of multi-class problems, ratio of largest to smallest class). Consequently, changes in class priors are directly reflected in changes in the imbalance ratio. Since PAI-KNN adapts through dynamic prior adjustment, such changes are of particular interest in this work. In many real-world streams, class frequencies do not only exhibit strong imbalance but may also change over time, resulting in dynamic imbalance ratios. Depending on the speed of change, such shifts may occur either suddenly or gradually. Due to the potentially infinite nature of data streams and processing speed requirements, memory-based classifiers typically maintain only a bounded subset of previously observed instances (also known as buffer).
Related work
We divide related work into three parts: classifiers for imbalanced data streams (§ 3.1), KNN classifiers for data streams (§ 3.2) and KNN classifiers for imbalanced static data (§ 3.2.1).
Imbalanced stream classifiers
Tree-based methods and their ensembles remain the dominant approach to stream classification. For imbalanced streams, numerous methods have been proposed that combine drift detection and adaptation with resampling, cost-sensitive learning, or imbalance-aware ensemble construction [2]. For the purpose of this work, the distinction between inference-based interventions (adjustments to the prediction rule) and data-based interventions (modifications of the data presented to the learner) is particularly important.
We therefore restrict our comparison for such methods to two representative state-of-the-art methods selected due to their performance [2]: Cost-sensitive Adaptive Random Forest (CSARF) [13] introduces a cost matrix to tackle imbalanced performance using adaptive random forests at inference time. Synthetic Minority Oversampling Technique with Online Bagging (SMOTE-OB) [3] is the best-performing method among methods heavily influenced by the SMOTE [6] algorithm, generating synthetic data on subsets of features, which are then used to continually update an ensemble of tree learners.
KNN-based stream classifiers
Self-Adjusting Memory KNN (SAM-KNN) [14] addresses concept drift through active memory management. The method maintains a short-term memory (STM) containing recent observations and a long-term memory (LTM) storing compressed historical information. As the stream evolves, SAM-KNN continuously restructures these memories based on the label consistency of stored instances with recent observations. Following drift detection, instances that remain consistent with the STM are retained, whereas inconsistent instances may be permanently removed. Adaptation is therefore achieved through active modifications of the stored memory.
Drift-Aware Multi-Memory Model (DAM3) [1] extends SAM-KNN to handle class-imbalanced streams. To improve minority-class performance, DAM3 introduces a third Working Memory (WM) and explicitly maintains a balanced class representation while identifying and removing class inconsistencies in the stored data. As in SAM-KNN, adaptation is achieved through active management of the underlying memories.
Both approaches achieve adaptation through active buffer management, i.e., modifications of the stored memories. SAM-KNN and DAM3 continuously inspect, restructure, and curate stored instances to maintain memory consistency and adapt to changing stream characteristics. While effective, such mechanisms require ongoing memory interventions and may permanently alter or discard information based on potentially uncertain evidence of change. This is particularly consequential in evolving streams, where instances initially regarded as outliers or noise may later prove representative of a changing class distribution or decision boundary [15]. Prematurely discarding them may therefore remove valuable evidence of concept evolution.
As our proposed adjustment is independent of the metric, we consider metric-learning approaches [12, 19] and extensions as orthogonal to this work’s focus point.
Static inference-time prior-adjusted KNN
An inference-time prior-adjusted KNN for static imbalanced learning was proposed in [9]. The method adjusts the decision rule rather than the data to compensate for class imbalance and achieves performance comparable to data-level interventions such as SMOTE [6] at a substantially lower computational cost.
In this formulation, KNN classification is viewed as a maximum-a-posteriori (MAP) estimator, where the class priors are estimated from the data and the likelihood is approximated by . Here is the number of instances of class among the nearest neighbors of an instance , is the total number of instances of class in the dataset, is the total number of instances, will denote the number of classes, and is the volume of the neighborhood.
Under mild assumptions, and using Bayes’ theorem, the posterior can then be written as:
To improve performance on underrepresented classes, the prior estimate is substituted by a uniform prior: . The new decision rule then becomes: .
In this work, we extend such inference-time prior adjustment from static imbalanced learning to non-stationary data streams with evolving class priors.
PAI-KNN: Inference-Time Prior Adaptation KNN
Motivated by the promising results of the prior-adjusted static KNN [9] for static imbalance learning and by the prevalence of increasingly sophisticated active memory management mechanisms in KNN-based stream classifiers, we investigate whether adaptation can be achieved through inference-time prior adjustment rather than active memory management. To this end, we extend the concept of inference-time prior adjustment to non-stationary data streams.
An overview of the proposed approach is shown in Figure 1. Relative to a vanilla KNN classifier, PAI-KNN augments prediction with a prior-adjustment mechanism that adapts the decision rule to changing class distributions over time. § 4.1 introduces the model components, followed by the update and inference steps in § 4.2. Computational complexity is discussed in § 4.3.

Figure 1. Model components (B),(P),(C). Target labels are received after prediction
Model definition
PAI-KNN augments a standard sliding-window KNN classifier with a prior-adjustment module that estimates class priors from recent observations and incorporates them into the prediction rule. Concretely, PAI-KNN consists of three components explained hereafter:
a buffer of size
a prior-adjustment module , which estimates class priors from recent stream history
a KNN classifier , which combines neighborhood information with the estimated priors during inference.
Buffer : The buffer is implemented as a FIFO queue and stores recent observations from the stream.
Prior-adjuster : The prior-adjustment module estimates the current class prior distribution from recent stream observations. To do so, PAI-KNN maintains multiple sliding windows of different sizes. The multiple windows allow the classifier to adaptively select the longest statistically consistent history for prior estimation, thereby limiting responsiveness to statistically significant changes. Class prior estimates are then obtained from the label frequencies within the selected window and incorporated into the prediction rule.
Concretely, we use sliding windows that store the latest labels, which can be effectively implemented using the existing buffer queue. The largest window is chosen to match the buffer size, i.e., , and is recommended for efficient hypothesis testing. At time , the sliding windows are given by
The module further maintains a significance threshold used to compare label distributions across windows. During inference, a test is used to assess whether two windows are plausibly generated from the same distribution.
The KNN classifier : The KNN classifier operates on the buffer and is associated with the typical KNN hyperparameters: the number of neighbors and the distance function . In addition, includes a parameter , interpolating between uniform priors and the observed class priors. This interpolation provides a direct trade-off between overall accuracy and minority-class performance, with corresponding to classical KNN and optimizing for recall on the minority class, as in knn-BPP [9].
Model update and inference
Update step: it only consists of queue insertions of into the buffer , and an insertion of the label into the sliding windows . Inference step: For an instance , the classifier determines for every class the number of instances among the nearest neighbors of . The prior-adjustment module selects the longest statistically consistent history and uses the corresponding label frequencies to estimate the current class priors. In particular, provides for every class the number of samples in the longest consistent sliding window , where
With all and determined that way, adjusts the prior using to effectively choose the sensitivity to imbalance and calculates the following posterior:
The class label of is the one that maximizes the posterior.
Computational Complexity
The time complexity of the update step is effectively negligible as only a queue insertion takes place. Time complexity in the inference step is dominated by the neighborhood search and hence worst-case complexity naively scales with , where is the buffer size and is the feature space dimensionality.
Compared to active buffer management methods, worst-case complexity is therefore significantly faster. For example, SAM-KNN scales slightly worse than [14]. The space complexity of our method scales with .
Experiments
We evaluate PAI-KNN on a benchmark of synthetic data streams against state-of-the-art competitors. Section 5.1 describes the evaluation design, datasets, competitors, metrics, and experimental protocol before presenting comparative results (§ 5.2) and a parameter analysis (§ 5.4) with respect to the prior-adjustment trade-off parameter , and the neighborhood size .
Evaluation design
Datasets:
We adopt the synthetic stream benchmark [2]. Streams consist of 200.000 instances, and are generated using multiple random generators to evaluate methods across different feature spaces. We restrict analysis to (five) binary generators producing only numerical features to avoid the need to craft distance functions on categorical features. Benchmark scenarios fall into four categories: i) static imbalance ratio, ii) dynamic imbalance ratio, iii) instance-level difficulties, and iv) concept drift. Competitors: We compare our approach to the competitor methods discussed in § 3: CSARF [13], SMOTE-OB [3], and SAM-KNN [14]. For DAM3 ([1]), the available online implementations struggled with long stream sizes. For CSARF and SMOTE-OB, we use results and hyperparameters from a recent survey [2], where they are set according to their self-reported standard configuration. For SAM-KNN, experiments were performed using the reference implementation in [17]. To validly compare against our own method, buffer size was set to 1024.1 For PAI-KNN, we chose , sliding windows in the prior adjuster ranging from size 64 to 1024, as a statistical significance threshold and . was chosen, thereby prioritizing G-Mean performance. Although the choice of distance function can have an important impact, it is orthogonal to this work. We therefore use the norm throughout to avoid confounding the effects of the prior intervention with those of the chosen metric.
Evaluation Setup: We run all experiments using River [16], with data streams generated using the code of [2]. In line with their work [2], we report the median obtained from running methods on 5 streams generated with different random seeds. Evaluation metrics for each run are calculated by taking the arithmetic mean over sliding windows of size 500. We aggregate metrics over groups of different synthetic streams, using the arithmetic mean. Code is available.2
Evaluation Metrics: Performance is evaluated using Accuracy, Cohen’s Kappa, and G-Mean. Accuracy measures overall correctness, Kappa accounts for chance agreement, and G-Mean emphasizes balanced performance across classes. We do not report detailed computational costs as these are very platform and implementation dependent [11]. To give some reference nonetheless, our not-optimized Python implementation of PAI-KNN processes approximately 1000 instances in two seconds, depending on the dimensionality of the feature space.
Predictive performance
To better understand the behavior of PAI-KNN under changing imbalance ratios, we plot in Figure 2 the performance for PAI-KNN, SAM-KNN, and a baseline KNN method (operating on a FIFO buffer without any prior adjustment, with , ) for a concrete scenario in which the imbalance ratio reverses twice over time (reflipping). We see that SAM-KNN’s imbalanced performance deteriorates notably more quickly than the baseline KNN method for high imbalance ratios. On the other hand, PAI-KNN maintains a high G-Mean level throughout even significant gradual changes. We interpret this as follows: maintaining buffer consistency is detrimental if streams change significantly and rapidly enough.

Figure 2. G-Mean and Accuracy over time - HyperplaneGenerator, gradual reflipping
This observation is reflected in the results shown in Figure 3, where we plot G-Mean and Accuracy for four different scenarios of imbalance ratio changes, with changes occurring either gradually or suddenly, and results aggregating over streams from different generators. PAI-KNN performs on par with ensemble competitors in terms of G-Mean, while underperforming in Accuracy. Sudden changes describe an instantaneous and significant shift in the data generating distribution, which for gradual changes is prolonged through interpolation over several thousands timesteps.

Figure 3. G-Mean and Accuracy per method for streams with dynamic IR
CSARF, similarly to us, excels in terms of G-Mean at the sacrifice of Accuracy, showcasing the natural conflict arising from cost-sensitive adjustments.
Concept Drift
We limit analysis to streams with both gradual and sudden feature space concept drift, for different, static imbalance ratios. We plot in Figure 4 performance by drift type and imbalance ratio, and aggregated across generators. We see that in terms of G-Mean, we outperform competitors for gradual changes, and high imbalance ratios. Again, a very clear data-intrinsic tradeoff can be recognized that is resolved in favor of G-Mean for PAI-KNN and CSARF, whereas performance for SAM-KNN correlates more strongly with SMOTE-OB.

Figure 4. G-Mean and Kappa per method for concept drift streams
Static Imbalance Ratio Streams in this category have no intrinsic temporal component; both feature and label distribution remain fixed over time. Here, the ability to retain and add information over time drives performance, whereas the ability to forget—a focus point of PAI-KNN—is irrelevant. As a result, PAI-KNN performs generally worse than competitors, but robust to very high (Figure 5).

Figure 5. G-Mean and Kappa per method for static streams with varying
Instance Level Difficulties Streams with instance level difficulties (ILD) incorporate one or multiple challenges to differentiate data: Imbalance ratios changes, class-specific concept drift, many instances in borderline regions or in rare locations. For those ILD streams involving concept drift we plot results in Figure 6.

Figure 6. G-Mean and Accuracy per method for ILD streams with concept drift
In terms of G-Mean, we keep up with state of the art competitors in this case despite the generator synthesizing the ILD streams producing distributions not particularly well-suited to a distance function.
We observe that SAM-KNN performs very well for the scenario involving rare instances. This is in line with our understanding that the buffer cleaning and management mechanism can perform very well when underlying assumptions are met and retaining information is important. PAI-KNN on the other hand performs more evenly across ILD scenarios: due to imposing only weak assumptions, we remain agnostic to different setups.

Figure 7. Effects of and per Experiment Group
Parameter Effect
We evaluate parameter effects using a subset of 36 streams, grouped by scenario class. For the trade-off parameter , maximizes accuracy, while optimizes G-Mean. Notably, G-Mean performance declines only slightly up to , offering a beneficial tradeoff. For streams exhibiting instance level difficulties (ILD), G-Mean even slightly improves up to , which showcases that under the right conditions, significant accuracy gains can be achieved using PAI-KNN without sacrificing on imbalanced performance. For the neighborhood size , we again fix . Low values of show higher accuracy while G-Mean benefits from larger . Again, the optimal tradeoff is both dependent on performance preferences and stream characteristics.
Conclusion
We presented PAI-KNN, a KNN-based stream classifier that introduces inference-time adaptation for jointly addressing concept drift and class imbalance. Unlike existing approaches that adapt primarily by modifying stored instances, PAI-KNN maintains a simple sliding-window memory and adapts predictions through dynamic class-prior adjustment. Our experimental evaluation demonstrated that PAI-KNN achieves competitive performance across a wide range of imbalance and drift scenarios, while performing particularly well under dynamic class imbalance and concept drift. These results indicate that effective adaptation in KNN-based stream classification does not require continuous expensive memory operations.
Instead, shifting adaptation to inference offers a simple and responsive mechanism for handling rapidly changing stream conditions.
More broadly, our findings suggest that adaptation in memory-based stream classifiers need not rely exclusively on increasingly sophisticated modifications to stored instances. The simplicity of PAI-KNN allows it to react quickly in highly dynamic settings without permanently altering the stored evidence. Actively managed memories, by contrast, can improve information retention over longer horizons when the assumptions underlying their management mechanisms hold, but may prematurely modify or discard instances based on uncertain evidence of change. Memory-based and inference-time adaptations should therefore be viewed as complementary design choices, with memory adaptations offering benefits for information preservation over long horizons and inference adaptations better equipped to tackle dynamic imbalance ratio shifts.
Future work will extend inference-time adaptation beyond class-prior adjustment by exploring feature-aware drift signals, and dynamic neighborhood selection, as well as its integration with memory-based adaptation.
Disclosure of Interests. The authors have no competing interests to declare that are relevant to the content of this article.
References
- [1]Abolfazli, A., Ntoutsi, E.: Drift-aware multi-memory model for imbalanced data streams. In: 2020 IEEE International Conference on Big Data (Big Data). pp. 878–885 (2020). https://doi.org/10.1109/BigData50022.2020.9378101
- [2]Aguiar, G., Krawczyk, B., Cano, A.: A survey on learning from imbalanced data streams: taxonomy, challenges, empirical study, and reproducible experimental framework. Machine Learning 113(7), 4165–4243 (Jul 2024). https://doi.org/10.1007/s10994-023-06353-6
- [3]Bernardo, A., Valle, E.D.: Smote-ob: Combining smote and online bagging for continuous rebalancing of evolving data streams. In: 2021 IEEE International Conference on Big Data (Big Data). pp. 5033–5042 (2021). https://doi.org/10.1109/BigData52589.2021.9671609
- [4]Bifet, A., Gavaldà, R.: Learning from time-changing data with adaptive windowing. In: Proceedings of the 2007 SIAM International Conference on Data Mining (SDM). pp. 443–448. https://doi.org/10.1137/1.9781611972771.42
- [5]Cano, A., Krawczyk, B.: Rose: robust online self-adjusting ensemble for continual learning on imbalanced drifting data streams. Machine Learning 111(7), 2561–2599 (Jul 2022). https://doi.org/10.1007/s10994-022-06168-x
- [6]Chawla, N.V., Bowyer, K.W., Hall, L.O., Kegelmeyer, W.P.: SMOTE: Synthetic Minority Over-sampling Technique. Journal of Artificial Intelligence Research 16, 321–357 (Jun 2002). https://doi.org/10.1613/jair.953
- [7]Gama, J., Žliobaitė, I., Bifet, A., Pechenizkiy, M., Bouchachia, A.: A survey on concept drift adaptation. ACM Comput. Surv. 46(4) (Mar 2014). https://doi.org/10.1145/2523813, https://doi.org/10.1145/2523813
- [8]Gomes, H.M., Bifet, A., Read, J., Barddal, J.P., Enembreck, F., Pfahringer, B., Holmes, G., Abdessalem, T.: Adaptive random forests for evolving data stream classification. Machine Learning 106(9), 1469–1495 (Oct 2017). https://doi.org/10.1007/s10994-017-5642-8
- [9]Gøttcke, J.M.N., Zimek, A.: Handling class imbalance in k-nearest neighbor classification by balancing prior probabilities. In: Similarity Search and Applications: 14th International Conference, SISAP 2021, Dortmund, Germany, September 29 – October 1, 2021. Proceedings, p. 247–261. Springer-Verlag, Berlin, Heidelberg (2021). https://doi.org/10.1007/978-3-030-89657-7_19
- [10]Hulten, G., Spencer, L., Domingos, P.: Mining time-changing data streams. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. p. 97–106. KDD ’01, Association for Computing Machinery, New York, NY, USA (2001). https://doi.org/10.1145/502512.502529, https://doi.org/10.1145/502512.502529
- [11]Kriegel, H.P., Schubert, E., Zimek, A.: The (black) art of runtime evaluation: Are we comparing algorithms or implementations? Knowledge and Information Systems 52(2), 341–378 (Aug 2017). https://doi.org/10.1007/s10115-016-1004-2
- [12]Kummert, J., Schulz, A., Hammer, B.: Metric Learning with Self-Adjusting Memory for Explaining Feature Drift. SN Computer Science 4(4), 376 (May 2023)DOI
- [13]Loezer, L., Enembreck, F., Barddal, J.P., de Souza Britto, A.: Cost-sensitive learning for imbalanced data streams. In: Proceedings of the 35th Annual ACM Symposium on Applied Computing. p. 498–504. SAC ’20, Association for Computing Machinery, New York, NY, USA (2020). https://doi.org/10.1145/3341105.3337949
- [14]Losing, V., Hammer, B., Wersing, H.: Knn classifier with self adjusting memory for heterogeneous concept drift. In: 2016 IEEE 16th International Conference on Data Mining (ICDM). pp. 291–300 (2016). https://doi.org/10.1109/ICDM.2016.0040
- [15]Masud, M., Gao, J., Khan, L., Han, J., Thuraisingham, B.M.: Classification and novel class detection in concept-drifting data streams under time constraints. IEEE Transactions on Knowledge and Data Engineering 23(6), 859–874 (2011). https://doi.org/10.1109/TKDE.2010.61
- [16]Montiel, J., Halford, M., Mastelini, S.M., Bolmier, G., Sourty, R., Vaysse, R., Žouitine, A., Gomes, H.M., Read, J., Abdessalem, T., Bifet, A.: River: machine learning for streaming data in python. J. Mach. Learn. Res. 22(1) (Jan 2021)arxiv.org/abs/2012.04740
- [17]Montiel, J., Read, J., Bifet, A., Abdessalem, T.: Scikit-multiflow: A multi-output streaming framework. Journal of Machine Learning Research 19(72), 1–5 (2018)DOI
- [18]Read, J., Zliobaite, I.: Supervised learning from data streams: An overview and update. ACM Comput. Surv. 57(12) (Jul 2025). https://doi.org/10.1145/3737279
- [19]Rivero Perez, J.L., Ribeiro, B., Perez, C.M.: Mahalanobis distance metric learning algorithm for instance-based data stream classification. In: 2016 International Joint Conference on Neural Networks (IJCNN). pp. 1857–1862 (2016). https://doi.org/10.1109/IJCNN.2016.7727425
- [20]Wagner, S., Zimmermann, M., Ntoutsi, E., Spiliopoulou, M.: Ageing-based multinomial naive bayes classifiers over opinionated data streams. In: Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2015, Porto, Portugal, September 7-11, 2015, Proceedings, Part I 15. pp. 401–416. Springer (2015)DOI
- [21]Wang, S., Minku, L.L., Yao, X.: Dealing with multiple classes in online class imbalance learning. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. pp. 2118–2124. IJCAI’16, AAAI Press, New York, New York, USA (Jul 2016)