PaperlayerView exact revision on arXiv

Source-linked AI summary

Classification under Streaming Emerging New Classes: A Solution using Completely Random Trees

Xin Mu, Kai Ming Ting, Zhi-Hua Zhou

arXiv:1605.09131v1cs.LG

TL;DR

Streaming emerging new classes (SENC) requires detecting new classes, classifying known classes, and updating models in streams. This paper uses completely random trees as a shared core for those tasks; SENCForest outperforms eight existing methods, including when the stream provides no true labels after deployment.

  • Problem

    SENC must handle emerging classes in streams, while existing class-incremental learning work is described as batch-mode and often assumes labels become available after deployment.

    Source: §2 · pp. 6, 8

  • Method

    SENCForest uses completely random trees as a shared core for detecting emerging classes, classifying known classes, and updating models.

    Source: §1.2 · pp. 5–6

  • Results

    SENCForest outperforms eight existing methods, despite receiving no true class labels throughout the stream, and works effectively on long streams under limited memory.

    Source: §6 · p. 32

  • Takeaways & Limitations

    The evaluation reports that one completely-random-tree core can support detection, known-class classification, and efficient model updates in data streams.

    Source: §1.2 · pp. 5–6

    The detector assumes anomalies of known classes are more normal than outlying anomalies from emerging classes.

    Source: §1.1 · p. 4

Abstract

from arXiv · show

This paper investigates an important problem in stream mining, i.e., classification under streaming emerging new classes or SENC. The common approach is to treat it as a classification problem and solve it using either a supervised learner or a semi-supervised learner. We propose an alternative approach by using unsupervised learning as the basis to solve this problem. The SENC problem can be decomposed into three sub problems: detecting emerging new classes, classifying for known classes, and updating models to enable classification of instances of the new class and detection of more emerging new classes. The proposed method employs completely random trees which have been shown to work well in unsupervised learning and supervised learning independently in the literature. This is the first time, as far as we know, that completely random trees are used as a single common core to solve all three sub problems: unsupervised learning, supervised learning and model update in data streams. We show that the proposed unsupervised-learning-focused method often achieves significantly better outcomes than existing classification-focused methods.

1. The intuition

The paper distinguishes emerging-class instances from anomalies of known classes, then uses completely random trees as a shared core for detection, classification, and model updates. Its related-work review frames SENC around four streaming challenges and reports that SENCForest meets all four.

1.1. Detecting emerging new classes

  • Emerging-class instances are treated as “outlying” anomalies, distinct from known-class anomalies assumed to be more normal.The detector must distinguish the two anomaly types because it is trained using only known-class instances.Source: §1.1 · p. 4
  • The anomaly region is subdivided into an anomaly subregion and a farther “outlying” anomaly subregion for identifying emerging-class instances.The proposed construction assumes anomaly regions can be identified, for example by thresholding anomaly scores.Source: §1.1 · pp. 4–5

1.2. Classification and efficient model update

  • Completely random trees provide a shared core for detection and classification, with training labels recorded in each leaf to support classification.The trees generated for anomaly detection are reused for classification.Source: §1.2 · pp. 5–6
  • The shared tree core supports updates after enough emerging-class instances are detected, with retiring and growing mechanisms used to manage model size.The approach aims to update efficiently while keeping model complexity reasonable.Source: §1.2 · p. 6

2. Related work

  • SENC requires detecting emerging classes, immediately predicting each incoming instance, storing no stream data permanently, and updating models quickly.The review describes class-incremental learning as modifying a trained classifier to handle emerging classes, while noting that existing approaches often leave detection to another mechanism [DYZ14, KOC13].Source: §2 · pp. 6–7
  • Prior work addresses parts of SENC: change-point detection omits classification and updates, while stream classifiers omit emerging-class detection.LACU-SVM is batch-mode and requires storing all training data; ECSMiner assumes delayed labels for new classes.Source: §2 · pp. 7–8
  • SENCForest is the only listed algorithm that meets all four SENC challenges; ECSMiner meets only Challenge #3 among existing algorithms.The review also notes that existing algorithms assume true labels become available after deployment.Source: §2 · p. 8, Table 1 · p. 8

3. Terminology Definition

This section introduces formal definitions for concepts used in the paper.

3. Terminology Definition

  • The paper introduces formal definitions for concepts used in its algorithm description.The passage does not specify the definitions themselves.Source: §3 · p. 9

a training data set D = {(xi, yi)}L

The SENC task learns an initial model from known-class data, then uses and updates it on a stream that may contain emerging classes.

a training data set D = {(xi, yi)}L

  • The goal is to learn a model from initial data that detects emerging classes, classifies known classes, and updates for accurate stream predictions.The passage defines the stream and data symbols only in fragments.Source: a training data set D = {(xi, yi)}L · p. 9
  • The hardest SENC condition provides no true labels after initial training, while label availability at intervals is described as an easier variation.The paper states it addresses the hardest condition and some easier conditions.Source: a training data set D = {(xi, yi)}L · p. 9
  • Model f assigns a score to a test instance to determine whether it belongs to a known class or an emerging new class.The supplied definition is truncated after introducing “outlying” anomalies.Source: a training data set D = {(xi, yi)}L · p. 9

anomaly.)

The score threshold divides feature space into known-class and anomaly regions, and the anomaly region is further divided to distinguish known-class anomalies from emerging-class instances.

anomaly.)

  • Known-class regions have scores at or above threshold τ̂, while anomaly regions have scores below τ̂.The threshold divides feature space based on model scores.Source: anomaly.) · p. 9
  • Anomalies of known classes lie within a ball around the center of training instances in an anomaly region.The ball’s radius is defined by the distance from that center to the nearest training instance from the known class.Source: anomaly.) · p. 9
  • Instances of emerging new classes are defined as the anomaly region outside that ball, Q = A\B.Source: anomaly.) · p. 9

4. The Proposed Algorithm

SENCForest reframes streaming emerging-new-class classification as new-class detection, using an unsupervised anomaly detector as the basis for both detection and known-class classification. Its overview builds a detector from completely random trees and subdivides anomaly regions to distinguish known-class anomalies from emerging classes.

4. The Proposed Algorithm

  • SENCForest treats SENC as a new-class detection problem, using an unsupervised anomaly detector as the basis for both unsupervised and supervised learning.The method is composed of SENCTrees and assigns each stream instance either an emerging-new-class label or a known-class label.Source: §4 · p. 10

4.1. SENCForest: An Overview

  • The overview trains an iForest, determines a path-length threshold, then builds a ball around training instances in each region.The training procedure ignores class information while building the detector.Source: §4.1 · p. 10
  • Within each anomaly region, the ball-covered area is treated as known-class anomalies, while instances outside it are treated as emerging classes.An iTree's axis-parallel regions are further partitioned by a ball; the outside portion is the “outlying” anomaly subregion.Source: §4.1 · pp. 10–11

2. Using known class information to build a classifier from a detector. Once the above

SENCForest derives a known-class classifier from the regions of its anomaly detector, then uses buffered emerging-class instances to update the model. Its training combines tree-based anomaly detection, a path-length threshold, and outlying anomaly subregions.

2. Using known class information to build a classifier from a detector. Once the above

  • Once the buffer fills, buffered instances grow subtrees at existing leaves; the update can also retire trees to maintain model size.The procedure replaces leaves whose instance count exceeds a set limit after incorporating buffered instances.Source: §2 · p. 11

4.2. SENCForest: Training process

  • Each tree uses completely random attribute and cut-point partitions to isolate training instances, and an ensemble of trees forms an iForest.At test time, average path length across trees serves as the anomaly score; shorter paths indicate greater likelihood of anomaly.Source: §4.2 · p. 12
  • The threshold separates short-path anomaly regions from long-path normal regions by minimizing the difference between the standard deviations of two path-length sublists.The threshold is determined automatically and does not require training data.Source: §4.2 · p. 13
  • After balls are built in anomaly regions, SENCForest is ready to detect emerging-class instances; an instance in an anomaly region but outside its ball is outlying.This separates anomalies of known classes from outlying anomalies associated with emerging classes.Source: §4.2 · pp. 13–14
  • SENCForest records known-class label frequencies in normal and ball-covered regions, making each region a classifier that predicts its majority class.This is the only training step that requires class labels.Source: §2 · p. 11, §4.2 · p. 14

Algorithm 1 Build SENCForest

The algorithm takes input data, a tree count, and a subsample size to build SENCForest. The resulting model assigns stream instances a known-class label or NewClass.

Algorithm 1 Build SENCForest

4.3. Deployment in data stream

  • For a test instance x, SENCForest outputs a known-class label or NewClass.The known labels are b1 through bm, where m is the number of known classes thus far.Source: §4.3 · p. 14

Algorithm 2 SENCTree

SENCForest buffers instances labeled NewClass and uses the buffer to update its detector and classifier. Updates grow subtrees or adjust class frequencies at existing leaves.

Algorithm 2 SENCTree

  • The paper focuses on updating for one new class in one period, while allowing different new classes to emerge in different periods.Instances from any number of emerging classes can be detected, but they are grouped as one new class for model update.Source: Algorithm 2 SENCTree · p. 15
  • SENCForest outputs the majority class across its trees; a tree returns NewClass for an instance in an anomaly region but outside the ball.Otherwise, the tree outputs the majority class recorded for the region.Source: Algorithm 2 SENCTree · p. 15
  • Instances labeled NewClass enter a buffer, and a full buffer is used to update both the classifier and detector before being reset.Source: Algorithm 2 SENCTree · pp. 15–16

4.4.1. Growing Mechanism

  • Each existing leaf is updated using ψ instances randomly selected from the buffer, either by replacing it with a subtree or updating class frequencies.The frequency update can add the new class bm+1.Source: §4.4.1 · p. 16

Algorithm 4 Update SENCForest

Algorithm 4 updates a SENCForest by replacing affected leaves with subtrees trained on new-class instances and pseudo-instances for known classes. Multiple forests combine predictions, while retirement rules remove forests that are no longer useful or are displaced at the preset limit.

Algorithm 4 Update SENCForest

  • Each affected leaf is replaced by a subtree trained on pseudo-instances representing its known classes and new-class instances that fell into that leaf.Pseudo-instances use the leaf centre’s attribute values, with counts recorded per class; the process is repeated for every affected leaf.Source: Algorithm 4 Update SENCForest · p. 18
  • Model updates retain the original tree structure and keep pseudo-instances together in one new leaf, so known-class predictions are not altered.Source: Algorithm 4 Update SENCForest · p. 18

4.4.2. Prediction using Multiple SENCForests

  • The final prediction is NewClass only when every SENCForest predicts NewClass; otherwise, it is the known class with the highest pi.When a forest reaches the user-defined class limit ρ, another SENCForest is grown for the next ρ emerging classes.Source: Algorithm 4 Update SENCForest · p. 18, §4.4.2 · p. 19

4.4.3. Retiring Mechanism

  • A SENCForest is retired after a period without known-class predictions; if the forest limit is reached and none qualifies, the least-used forest is selected for retirement.Usage is measured by the number of known-class predictions in the last period.Source: §4.4.3 · pp. 19–20

5. Experiment

The experiments evaluate SENCForest against state-of-the-art methods on simulated emerging-class streams, including long-stream and two-new-classes-per-period settings. They report new-class detection and predictive accuracy alongside model memory and update-time behavior.

5.1. Experimental Setup

  • Trials simulated streams with two initially known classes and new classes emerging in later periods; SENCForest alone required neither stream-time true labels, stored initial training data, nor extra unlabelled training data.The experiments averaged ten trials; competing methods could require true labels for model updates, and LACU-SVM additionally required unlabelled data.Source: §5.1 · pp. 24–26

5.2. Empirical results

  • Across five datasets, SENCForest achieved the highest new-class detection F-measure, and SENCForest and SENCForest+SVM achieved the highest accuracy.SENCForest’s detection advantage was significant over all contenders except LACU-SVM on MNIST and ECSMiner on Forest Cover; for accuracy, it significantly outperformed other contenders on three datasets, with exceptions involving LACU-SVM.Source: §5.2 · pp. 26–27, Figure 9 · p. 27
  • Despite additional unlabelled training data, LACU-SVM was significantly worse than SENCForest on F-measure in four datasets, while label-assisted ECSMiner was significantly worse on both measures in four of five datasets.SENCForest and SENCForest+SVM share the same detector; the latter’s accuracy requires storing all instances, whereas SENCForest alone achieves comparable accuracy without storing data.Source: §5.2 · pp. 28–29

5.3. SENCForest in long data streams

  • In the MNIST long-stream simulation, SENCForest maintained its model size within a preset limit of three forests by retiring forests no longer in use, enabling operation on infinite streams.The simulation used twelve emerging classes, and classes were reused when no longer active; the stream was limited to MNIST because it required many classes.Source: §5.3 · pp. 29–30, Figure 10 · p. 30
  • SENCForest maintains good predictive accuracy over long streams, and its improvement from true class labels increases as Q increases.The passage also reports that ECSMiner and LACU-SVM predictive accuracy continued to decrease; the supplied text does not specify the condition.Source: §5.3 · p. 30
  • SENCForest training time grows as the stream progresses, while ECSMiner has the least model-update time because its k-nearest-neighbor base learner only builds buffer clusters.ECSMiner must save each cluster's summary in memory.Source: §5.3 · p. 30

5.4. Multiple new classes in a period

  • SENCForest performs well with two emerging new classes per period by treating them as a single new class.The evaluated stream has three periods, each with 2,000 instances and four classes: two emerging and two known.Source: §5.4 · p. 31
  • To identify each emerging class separately, a clustering algorithm can be applied before model update.SENCForest is designed for one emerging new class per period, so this clustering step is an option when separate class identification is important.Source: §5.4 · p. 31

6. Conclusions and future work

The conclusion presents SENCForest as an integrated solution for emerging-class detection, known-class classification, and model updates, with detection treated as central to the task. Its evaluation reports stronger results than existing methods, while the authors identify concept drift and multiple emerging classes as future extensions.

6. Conclusions and future work

  • The paper decomposes SENC into three subproblems and argues that effective emerging-class detection is crucial to solving the whole problem.It presents an unsupervised-anomaly-detection-focused approach using completely random trees as a complete solution, in contrast to classification-focused approaches.Source: §6 · pp. 31–32
  • SENCForest’s strength is high-accuracy emerging-class detection, which the authors link to differentiating known-class anomalies from new-class instances.They argue existing supervised and semi-supervised methods fall short on detection because they focus on classification.Source: §6 · p. 32
  • Completely random trees provide a shared core that can be converted into a classifier and updated by model adjustment rather than retraining.The authors describe these trees as competitive with state-of-the-art classifiers, particularly where streams demand fast updates and classification.Source: §6 · p. 32
  • SENCForest outperformed eight existing methods without receiving true class labels during the stream, while the other methods received labels at each update.The authors also report that it works effectively on long streams with emerging classes under limited memory.Source: §6 · p. 32
  • Future work will address concept drift and distinguishing two or more emerging classes before model updates.Source: §6 · p. 33

7. appendices

The appendices document experiment parameter settings and describe the synthetic and MHAR data sets.

7.1. Parameter settings

  • The experiments use 10-fold cross-validation on the training set to select settings for SVM algorithms; LOF follows, and ECSMiner uses K-means with K=5.The parameter settings are provided in Table 5.Source: §7.1 · p. 33, Table 5 · p. 33

7.2. Descriptions of data sets

  • The synthetic stream contains 20,000 instances from four overlapping Gaussian distributions, with two known classes followed by blue and red emerging classes in successive periods.Source: §7.2 · pp. 33–34
  • MHAR contains 10,299 instances across six activities, collected from 30 volunteers wearing a smartphone with accelerometer and gyroscope sensors at 50 Hz.Source: §7.2 · p. 34
Loading 1605.09131v1…