Nearest Neighbor Ensembles: An Effective Method
for Difficult Problems in Streaming Classification
with Emerging New Classes
Xin-Qiang Cai1,2 , Peng Zhao1,2 , Kai-Ming Ting3 , Xin Mu1,2 , Yuan Jiang1,212National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China
Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing 210023, China
3
School of Engineering and Information Technology, Federation University, Australia
Email: 1,2 {caixq, zhaop, mux, jiangy}@lamda.nju.edu.cn 3 kaiming.ting@federation.edu.au

Abstract—This paper re-examines existing systems in streaming classification with emerging new classes (SENC) problems,
where new classes that have not been used to train a classifier
may emerge in a data stream. We identify that existing systems
have an unspecified assumption that emerging new classes aregeometrically far from known classes, or instances of knownclasses are densely distributed, in the feature space. Using a classseparation indicator α, we refine the SENC problem into an αSENC problem, where α indicates a geometric distance between
two classes in the feature space. We show that while most existing
systems work well in high-α SENC problems (i.e., a new classis geometrically far from a known class or instances of knownclasses are densely distributed), they perform poorly in lowα SENC problems. To solve low-α SENC problems effectively,
we propose an approach using nearest neighbor ensembles or
SENNE. We demonstrate that SENNE is able to handle both the
low-α and high-α SENC problems which can appear at different
times in a single data stream.
Index Terms—classification, data stream, new class, ensemble
method, open and dynamic environments

I. I NTRODUCTION
In many real-world applications, data are often gathered
over time, and thus one cannot access the whole dataset andthen train the model. Meanwhile, in open and dynamic environments, there may continuously emerge instances belonging
to previously unseen new classes in the data stream [1], [2],[3], [4]. Therefore, the Streaming classification with Emerging
New Classes (SENC) problem has drawn much attention
recently [5], [6]. In the literature, there are many studies that
propose different algorithms to handle SENC problems, andsome representatives are ECSMiner [5], SENCForest [6], andSENCMaS [7].
While existing approaches have shown promising results,
one key weakness is that the SENC problem is assumed tohave instances of new classes which are geometrically far
from those of known classes, and instances of known classes
are densely distributed—thus easy to detect. In this paper,
we show that the SENC problem has different degrees ofdifficulty. If the emerging new class is significantly different
from known classes, then detecting the new class would beeasy. On the contrary, it would be much harder if the new classis similar to known classes (in terms of feature characteristics).

Known Classes

New ClassStream A

Stream B

Fig. 1: Illustrative examples in detecting new emerging digits in data
streams A and B using images in the MNIST dataset.

Figure 1 gives a digit identification example of two streams.
For the known classes of digits 2 and 3 in stream A, detecting
the emerging new class of digit 0 is easy because the feature
characteristics of new class and known classes are significantly
different. By contrast, for known classes of digits 4 and 7 instream B, it is much harder to detect the emerging new classof digit 9 because there are a lot of similarities within each of
the two pairs: 4-9 and 7-9.
To measure the difficulty of SENC problems, we propose
a new indicator α, and refine the SENC problem into an αSENC problem (α is defined in Section II-B). We remark thatboth low-α and high-α new classes may occur in the same data
stream in different time periods, where low-α new classes are
more similar to known classes than high-α new classes.
The emerging low-α new classes poses two challenges:
First, it becomes more difficult to distinguish low-α newclasses from known classes. This makes it challenging for both
new class detection and known classes classification. Second,the occurrence of both low-α and high-α new classes in thesame stream imposes complications in updating models along
the stream that can lead to poor performance.
To address these issues, we propose to handle the α-SENC
problem by using a nearest neighbor ensemble approach, or
SENNE. It has dual functions: a classifier for the knownclasses and a detector for the new class; and it is capable ofdetecting both high-α new class and low-α new class which
may appear in close succession in a data stream.
The main contributions are summarized as follows:

1) Introducing a class separation indicator α to measure thedegree of difficulty in detecting an emerging new class;and leading to the α-SENC problem;2) Proposing an effective approach to address the α-SENC
problem by using nearest neighbor ensembles;3) Conducting comprehensive experiments to validate theeffectiveness of the proposed approach in both low-α andhigh-α SENC scenarios.
The rest of the paper is organized as follows. Section II
introduces the α-SENC problem. Section III proposes ourapproach. Section IV provides key differences between the
proposed approach and closely related methods. Sections V
describes experimental settings and Section VI reports theresults. Finally, Section VII concludes the paper.
II. SENC P ROBLEM AND α-SENC P ROBLEM
We first review preliminary concepts in SENC [6]. Then,
we refine it as the α-SENC problem.
A. SENC Problem
Definition 1 (Streaming Emerging New Classes, SENC).
d
Given the training data D = {(xi , yi )}m
i=1 , where xi ∈ R
is an instance and yi ∈ Y = {1, 2, . . . K} is the associatedd0class label; data stream S = {(x0t , yt0 )}∞t=1 , where xt ∈ R
00
and yt ∈ Y = {1, 2, . . . , K, K + 1, . . . , M } with M > K.
The goal is to learn an initial model f from the training
data D; then f is used as a detector for emerging new classand a classifier for known classes. The model f is updated
timely such that it maintains accurate predictions for known
and emerging new classes on the data stream S.
Most of existing approaches for the SENC problem [5],[6] assume that the data space can be partitioned into three
regions, i.e., region of known classes A, region of anomalies ofknown classes B, and region of new classes Q. An illustrationof these regions is given in Figure 2(a), where the intuition isthat differences between new classes and known classes arelarger than that between anomalies and known classes.
B. α-SENC Problem
Here we refine the SENC problem as the α-SENC problem,
where α is an indicator reflecting the separation between
known classes and a new class of the problem.
For an instance x, let ηx be its nearest neighbor in the sameclass, and let τ (x) denote their distance, i.e., τ (x) = kx−ηx k.
We define the class separation indicator α as follows.
Definition 2 (Class Separation Indicator). The class separation
indicator α of a known class dataset DK and the newclass dataset DN is the ratio of the following two terms:
M (DK , DN ): the minimum distance of the two datasets; andC(DK ): the compactness of the known class dataset DK ,namely,M (DK , DN )α(DK , DN ) =(1)
C(DK )
where M (DK , DN ) =min0
kx − x0 k and
x∈D
,
x
∈D
K
N
P
1
C(D) = |D|x∈D τ (x).

Fig. 2: The left figure shows three regions of data space: region of
the known class A, region of the anomalies of known classes B,
and region of the new classes Q; and the right figure represents
an example SENNE model with two known classes (blue circle
and orange triangle) and its predictions on two instances (green
rectangles) in the data stream.

The indicator α ∈ (0, ∞) essentially measures the separation between a known class and the new class: it has
small value if the new class is close to the known class(i.e., M (DN , DK ) is small); or instances of the known classare sparsely distributed (i.e., C(DK ) is large). Therefore, αquantifies the level of ease in detecting a new class: the smaller(larger) the value of α is, the harder (easier) the α-SENC
problem will be.
Previous methods ignore scenarios that have (a) close
proximity between new class and known classes (whenM (DN , DK ) is small); and (b) sparsely distributed instancesof known classes (when C(DK ) is large). Thus, they are only
suitable for α-SENC problems with a large value of α, andbehave poorly in the low-α scenarios.
To handle new classes with high-α as well as low-α in a data
stream, we introduce a new approach called SENNE based onnearest neighbor ensembles. Note that α is an indicator todenote the level of difficulty of the SENC problem only, and
it is not used in the proposed approach.
III. T HE P ROPOSED A PPROACH : SENNESENNE has three major steps:(1) Building Model: The procedure is based on nearest
neighbor ensembles from a given training set. The samemodel is used for both new classes detection and knownclasses classification.
(2) Prediction in a Data Stream: Detect the new class andclassify known classes according to the new-class scoreand known-class score. A buffer is used to temporarily
store instances detected as the new class.
(3) Model Update: The current model is updated using instances in the buffer when the buffer is full.
A. Building SENNE Model
For the k-th known class dataset D(k) with k = 1, . . . , K(where K is the number of known classes), we randomly
subsample ψ instances, and repeat p times to generate subsets(k)(k)
Di satisfying |Di | = ψ with i = 1, . . . , p.
SENNE follows the same procedure as that of iNNE [8] inbuilding a model of K ensembles. Specifically, an ensemble isdefined as p sets of isolation heperspheres derived from D(k) ,and each set consists of ψ isolation heperspheres. The rigor
definitions are presented as follows.

Definition 3 (Isolation Hypersphere). Given the k-th known(k)class data subset Di , an isolation hypersphere B(c) centeredat c with radius τ (c) = kc−ηc k is defined to be {x : kx−ck ≤(k)τ (c)}, where x ∈ Rd ; c, ηc ∈ Di ; ηc is the nearest neighborof c in the same class.
Definition 4 (Ensemble for Known Class). Given the k-th
known class dataset D(k) , an ensemble B(k) contains p sets,
and each set consists of ψ hyperspheres. B(k) is defined by(k)
B(k) = {B(c) : c ∈ Di } : i = 1, . . . , p(2)
A SENNE model f initially consists of K ensembles after
training from a dataset of K known classes. An example isshown in Figure 2(b): the SENNE model with two knownclasses is in a two-dimensional scenario, where ψ = 5 for eachclass. Note that the hyperspheres are large in sparse regions
and they are small in dense regions—a characteristic of thismodel. In this example, the SENNE model will predict the top
left test instance (green rectangle) as belonging to one of the
known classes, i.e., the blue circle class; and the bottom righttest instance is predicted as a new class instance.
Note that though the model building of SENNE and iNNE
are the same, they differ in the scoring functions, which will
be described later. (The differences are shown in Section IV.)
B. Prediction in Data Stream
The predictive function for each instance in a data stream
has two components: one is to detect whether an instancebelongs to the new class; and the other is to classify it into
one of the known classes if it is not a new class instance.
We propose the following new-class score N (k) and knownclass score P (k) , where k = 1, . . . , K.
SENNE classifies a test instance as belonging to a new class(NC) if all of its new-class scores with respect to all knownclasses are larger than a threshold t; otherwise, it is categorized
as one of the known classes 1, . . . , K, namely,NC,
if N (k) (x) ≥ t, ∀k = 1, . . . , K
f (x) = arg max P (k) (x) otherwise
k=1,...,K(3)
Definitions of new-class score N (k) and known-class score
P (k) are given as follows.
Definition 5 (New-Class Score). For the k-th known classdataset D(k) , the new-class score is defined byp

N (k) (x) =1 X (k)N (x),
p i=1 i(4)(k)
where Ni (x) is the new-class score of point x based on(k)subset Di , and is defined byhiS 1 − τ (ηcnn(x) ), if x ∈ c∈D(k) B(c)(k)
kx−cnn(x)ki+
Ni (x) =1,otherwise(5)

Algorithm 1 SENNE.Detector
Input: Data stream S = {x1 , . . .}; number of known classes
K; buffer B with size s; new-class score threshold t.
Output: Prediction for each new instance in the data stream.
1: function P REDICT (S, B, K, t)
2:
Build model f by the dataset with K known classes
3:
B←∅. Initialize buffer4:
while HasNext(S) do
5:
Calculate N (k) (x) by Eq. (4) for k = 1, . . . , K
6:
if N (k) (x) > t, ∀k = 1, . . . , K then7:y ← NC. New Class
8:B ← B ∪ {x}9:if |B| = s then10:f ← U PDATE M ODEL(K, B, f )11:
B ← ∅ and K ← K + 1
12:
end if13:else
14:y ← P REDICT C LASS(x, K, f , t)
15:
end if16:
end while
17:
return y ∈ {1, 2, . . . , K, NC}
18: end function
Algorithm 2 SENNE.PredictClass
Input: Instance x; number of known classes K; new-class
score threshold t; model f .
Output: Prediction y.
1: function P REDICT C LASS(x, K, t, f )2:
Calculate P (k) (x) for k = 1, . . . , K by Eq. (6)3:y ← arg maxk=1,...,K P (k) (x)4:
return y
5: end function

where cnn(x) = arg minc∈D(k) {τ (c) : x ∈ B(c)} denotesithe center of the smallest hypersphere covering point x.
Besides, [a]+ equals a if a ≥ 0; and 0 otherwise.
Definition 6 (Known-Class Score). The known-class score is(k)defined as the probability of Ni (x) < t:
p

P

(k)

1X
(k)
(x) =
I[Ni (x) < t], for k = 1, . . . , K,
p i=1

(6)

where I[·] is the indicator function which takes 1 if · is true,and 0 otherwise.
The final prediction of test instance x is assigned to the
known class k with the highest known-class score P (k) .
The procedures of SENNE and classification of knownclasses are given in Algorithms 1 and 2, respectively.
C. Model Update
We set a buffer to store the test instances that are classified
as new class. When the buffer is full, we need to update
the model to accommodate the new class in the buffer asa new known class. To this end, we utilize the data therein

Algorithm 3 SENNE.UpdateModel
Input: Number of known classes K; buffer B with size s;model f .
Output: Updated model f ; number of known classes K.
1: function U PDATE M ODEL (K, B, f )2:
Build B(K+1) , an ensemble of p sets of ψ hypersphereswith instances in B, as described in Section III-A
3:
Label the class of instances in B as K + 1
4:f ← f ∪ B(K+1)
5:
return f
6: end function

to construct an ensemble of p sets of hyperspheres for the
new class, and then incorporate this ensemble into the existingmodel. After that the buffer will be emptied, and the updated
model is ready for the next instance. The procedure of model
update is described in Algorithm 3.
IV. K EY D IFFERENCES WITH C LOSELY R ELATED W ORK
In this section, we discuss relationships and differences withrelated work iNNE [8].
Although both SENNE and iNNE [8] share the same
training process, they employ individual scores due to different
aims. Specifically, iNNE employs the isolation score since it
has the sole purpose of detecting anomalies. On the contrary,
SENNE uses new-class score (cf. Eq. (5)) which is designed
to differentiate emerging new classes from known classes in
the SENC context. The new class detection accuracy would be
low if the isolation score is naively used to detect new classes.
This is because anomalies of known classes could be mistaken
as emerging new classes in a data stream. For example,iNNE yields 0.723, 0.703, 0.764, 0.701, 0.744 accuracy on theForest Cover, HAR, MNIST, Fashion-MNIST, and NYTimes
datasets; but SENNE achieves 0.871, 0.804, 0.784, 0.737,
and 0.768 respectively (see Section VI-B). The win/tie/loss
compares with iNNE is 5/0/0. This is because the isolation
score categorizes anomalies of known classes into new class(leading to false positives) in this SENC context. In contrast,
the proposed new-class score is designed to reduce this kindof false positives.
A similar phenomenon occurs in SENClof (which simply
employs local outlier factor or lof [9] in the SENC context), when lof—an anomaly detection approach—is naively
extended to identify new classes. This approach tends tomisclassify anomalies of known classes as belonging to newclass, especially in low-α scenarios. The empirical results,
shown in Section VI, validate that SENClof is not suitable
for the α-SENC problem.
V. E XPERIMENTAL S ETTINGSIn this section, we describe experimental settings, including
datasets, simulation, evaluation, and contenders. All experiments are implemented in MATLAB on Intel Core CPU
machine with 24 GB memory and 3.2 GHz clock speed.

Datasets. We adopt three kinds of datasets, i.e., synthetic,
benchmark, and real-world textual data stream.
For synthetic datasets, we simulate data stream with different degrees of difficulty based on various values of α.
Each dataset contains three classes with 2000 two dimensional
instances. For benchmark datasets, we adopt 4 datasets: Forest
Cover [10], HAR [11], MNIST, and Fashion-MNIST [12]. In
addition, we include a real-world data stream, which is crawlednews from the website between 2014 and 2017 using the
New York Times API1 , and contains 35,000 latest news items.
Each news item is classified into six categories, namely, ‘Arts’,‘Business Day’, ‘Sports’, ‘U.S.’, ‘Technology’, and ‘World’.
Each news story is converted into an 100-dim vector using theword2vec technique [13].
Data characteristics of benchmark and real-world textual
datasets are summarized in the first four columns of Table I.
Stream Simulation. In the training stage, an initial training
set consists of m1 instances per known class. In the testingstage, the simulation is conducted in two periods for all
datasets, except the synthetic datasets which are conductedin one period. Each period contains one new class, and eachclass consists of m2 instances. For each of these instances,the model is to make a prediction, either classifying a knownclass or identifying the new class.
There are two setups, including the varying and fixed αSENC scenarios, on benchmark and real-world datasets. Also
we set the buffer for all approaches in the comparison withthe same buffer size.
In the varying α-SENC scenario, as the new class is
randomly selected from the whole class set, the data stream
will have a mixture of high and low-α new classes. The initial
dataset has two classes, except the NYTimes dataset contains
five classes. For all the benchmark datasets, m1 = 2000
(m1 = 800 for HAR because it has a small data size),m2 = 500, and the buffer size s = 300 are conducted. For
real-world dataset NYTimes, m1 = 5000, m2 = 5000, ands = 3000 are set to simulate a long data stream.
In each of the α-SENC experiments with a fixed α, there
is only one period in the whole data stream. We calculate thevalues of α between every two classes, and select two knownclasses and one new class with the lowest/highest value of α
to simulate the lowest/highest-α SENC problems. The valuesof m1 , m2 and s are the same as that used in the varying αSENC experiments. We conduct 10 trials of stream simulationfor each dataset, and report the average result.
Evaluation metric. We use the accuracy to evaluate theperformance of each approach, namely, Acc = (n1 + n2 )/n,where n1 is the number of known classes instances classified
correctly; n2 denotes the number of instances belonging to the
new class which are detected successfully in the data stream;
and n is the total number of instances in data stream.
Contenders. We compare SENNE with four contenders:(a) SENClof, an adaptation of local outlier factor algorithm [9] from the original anomaly detection algorithm to
1 http://developer.nytimes.com/

VI. E XPERIMENTAL R ESULTS
We present results in three subsections: (a) experiments on
synthetic datasets scenario; (b) experiments on benchmark andreal-world datasets; and (c) runtime comparisons.
A. Results on Synthetic Datasets
This experiment highlights performances of different approaches in α-SENC scenarios with a decreasing value of α.
Figure 3(a) shows accuracies of four approaches as αdecreases. We can observe that SENNE is the most robustalgorithm among all the contenders, in the sense that its
accuracy does not drop much with the decrease of α. In
particular, SENNE significantly outperforms other methods
in the scenarios with the lowest α. ECSMiner is the second
best, followed by SENClof; and SENCForest has an undesired
performance. Note that since SENCMaS is designed for highdimensional data, it is not included on 2D synthetic datasets.
The superiority of SENNE comes from the new-class score,
which is a relative score using test point’s local neighborhood
information, and thus it can detect the appearance of lowα new class more effectively. On the contrary, depth of thetrees employed by SENCForest, which does not consider
test point’s local neighborhood, so it fails to detect low-α
new classes. Also it is invalid to apply a similar score to
SENCForest due to different basic models—SENNE employs
isolation hyperspheres while SENCForest uses isolation trees.
B. Results on Real-world Datasets
In this section, we present results on real-world datasets on
both low-α and high-α SENC scenarios.
Table I reports performance comparisons on 5 real-world
datasets. The result shows that SENNE achieves the best
performance on 3 out of 5 datasets. On the other two datasets,
it ranks the second and is competitive with the best one(SENCForest).
As NYTimes dataset is used as a long data stream simulation, we also plot the accuracy curves regarding time stampsof different approaches, as reported in Figure 3(b).
The results illustrate that ECSMiner behaves poorly. Meanwhile, SENCForest and SENCMaS achieve a comparably
satisfying performance, and SENNE is always better than theother approaches. SENClof is a naively extended method from
LOF [9] to solve SENC problems, whose performance is toopoor to present since it tends to treat anomalies of knownclasses as new class, so we omit its results here. The empiricalstudies on NYTimes dataset validates the efficacy of SENNEin real-world data stream applications.
In order to examine the effect of high-α and low-α on theperformances of all approaches, and to understand the reason

1

0.85

0.95

0.8

0.9

Accuracy

Accuracy

the SENC setting; (b) ECSMiner [5], an approach basedon k-nearest neighbors; (c) SENCForest [6] is based oncompletely random trees; (d) SENC-MaS [7] approximatesoriginal information by a dynamic low-dimensional structure
via matrix sketching. For compared approaches, we set default
parameters as suggested in their papers or codes.

0.85

0.8

0.75

0.7
14

SENClof
ECSMiner
SENCForest
SENNE

0.75

0.7

ECSMiner
SENCForest
SENCMaS
SENNE

0.65

0.6
12

10

8

6

4

2

0

0.5

1

1.5

2

Data Stream

2.5

3

3.5
10 4

Fig. 3: The left figure reports the accuracy of four approaches as αdecreases.; and the right one denotes accuracy curves on NYTimes
dataset of different approaches. We omit results of SENClof, which
are too poor to be presented.

why SENNE outperforms its contenders, we select specificknown classes and new class in each dataset to simulate highα and low-α SENC scenarios.
Table II demonstrates that most approaches are effective
in high-α SENC problems. However, when it comes to the
low-α scenarios, the accuracy of all the methods decreases
in different degrees. SENNE evidently has the least accuracy
degradation and achieves the best performance.
The experiments using two subsets of digits {2, 3, 0} and{4, 7, 9} on the MNIST dataset are shown in Table II, which
is used as an example of low-α and high-α SENC problems
in Section I. The results validate that the class separation
indicator α indeed has the ability to measure the difficultyof SENC problems, since the α value of {2, 3, 0} is 1.01,
which is larger than 0.75, the α value of {4, 7, 9}. This also
accords to the intuition that detecting the new class of digit
0 is easy (when known classes are 2 and 3); while detecting
digit 9 is much harder (when known classes are 4 and 7).
Note that SENNE achieves the best performance on MNIST
dataset in the high-α situation. This is mainly because thehighest α on the MNIST dataset is still lower than that onother datasets. This means that MNIST dataset is more difficult
than others even in the high-α SENC scenario. On NYTimes
dataset, the accuracies of all approaches do not decrease muchregardless of the α value (SENClof is the exeption). The
reason is that the lowest α value on NYTimes dataset is 1.53,
much higher than those of other datasets. Thus, this dataset is
not that hard even in the low-α scenario.
C. Runtime Comparison
Figure 4 reports runtime comparisons. SENClof and
SENNE run faster than the other approaches, and SENNE
is the only one that ran one order of magnitude faster than
SENCForest on the large-scale dataset (NYTimes). We remarkthat SENNE is fast due to the one-step characteristics in thesense that it directly performs new class detection. This is
in contrast with previous studies including SENCForest and
SENCMaS, as they require detecting anomalies of knownclasses first. On the other hand, the procedures of detection andclassification through isolation hyperspheres (the basic modelof SENNE) are faster than that through other models. Notethat the y-axis in Figure 4 is in the logarithmic scale.

TABLE I: Data characteristics and accuracy in the varying α-SENC problem, where new classes are randomly selected from the whole classset. • (◦) indicates that SENNE is significantly better (worse) than the compared method (paired t-tests at 95% significance level).
Dataset#class#attribute#instance

SENClof

ECSMiner

SENCForest

SENCMaS

SENNE

Forest Cover
HAR
MNIST
Fashion-MNIST
NYTimes

7
6
10
10
6

10
561
784
784
100

581,012
10,29960,00060,000156,6830.724 ± 0.070 •0.601 ± 0.024 •0.678 ± 0.019 •0.710 ± 0.016 •0.398 ± 0.023 •0.787 ± 0.076 •0.654 ± 0.055 •0.722 ± 0.060 •0.737 ± 0.047
0.741 ± 0.005 •0.791 ± 0.045 •0.755 ± 0.043 •0.757 ± 0.025 •0.745 ± 0.035 ◦
0.772 ± 0.004

0.752 ± 0.059 •0.736 ± 0.044 •0.757 ± 0.036 •
0.716 ± 0.047 •0.767 ± 0.023

0.871 ± 0.066
0.804 ± 0.032
0.784 ± 0.032
0.737 ± 0.027
0.768 ± 0.025

SENNE w/t/l

−

−

−

5/ 0/ 04/ 1/ 03/ 1/ 1

4/ 1/ 0rank first 3/ 5

TABLE II: Accuracy in fixed α-SENC problems. The top and bottom blocks are for high-α and low-α SENC problems on each real-world
dataset, respectively. In the “classes” column, the three digits denote the selected classes, in which the first two digits represent known classes
and the third one is new class. We omit Fashion-MNIST since α values of Fashion-MNIST are similar to those of MNIST.
Datasetclassesα

SENClof

ECSMiner

SENCForest

SENCMaS

SENNE

HAR
Forest Cover
MNIST
NYTimes

1, 2, 63, 4, 72, 3, 05, 3, 6

2.10
19.0
1.01
2.75

0.769 ± 0.013 •0.719 ± 0.034 •
0.805 ± 0.012 •0.698 ± 0.014 •0.813 ± 0.017 •
0.905 ± 0.009 •0.793 ± 0.010 •0.912 ± 0.010

0.921 ± 0.006
0.946 ± 0.010
0.839 ± 0.008 •0.936 ± 0.007 ◦0.880 ± 0.011 •0.952 ± 0.017
0.847 ± 0.011 •0.924 ± 0.007

0.919 ± 0.015
0.947 ± 0.050
0.895 ± 0.010
0.916 ± 0.018

HAR
Forest Cover
MNIST
NYTimes5, 6, 43, 4, 64, 7, 91, 2, 4

0.89
0.58
0.75
1.53

0.563 ± 0.018 •0.689 ± 0.013 •0.642 ± 0.013 •0.341 ± 0.009 •0.564 ± 0.024 •0.828 ± 0.010 •0.651 ± 0.019 •0.875 ± 0.016 •0.668 ± 0.002 •0.766 ± 0.012 •0.625 ± 0.014 •0.904 ± 0.009 •0.670 ± 0.014 •0.743 ± 0.009 •0.736 ± 0.016 •0.903 ± 0.012 •0.718 ± 0.014
0.840 ± 0.013
0.787 ± 0.009
0.912 ± 0.030

SENNE w/t/l−−

8/ 0/ 07/ 1/ 05/ 2/ 1

6/ 2/ 0rank first 5/ 8

R EFERENCES
T im e ( C P U s e c o n d s )

1 0 4

1 0 3

S E N CE C S MS E N CS E N CS E N Nlo fin e rF o re s t
M a S
E

1 0 2

1 0 1

S y n th e tic

F o re s t C o v e r

H A R

M N IS T

F a s h io n - M N IS T

N Y T im e s

Fig. 4: The runtime comparisons.

VII. C ONCLUSION
In this paper, we re-examine the SENC problem, namely, thestreaming classification with emerging new classes problem.
We identify that SENC problems have different degrees ofdifficulties, and thus refine it as the α-SENC problem byproposing a class separation indicator α to measure the difficulty. Then, we introduce a new approach called SENNE toaddress this problem effectively by utilizing nearest neighborensembles. The effectiveness and superiority of SENNE arevalidated on both synthetic and real-world datasets. We showthat α-SENC problems with high degree of difficulty are common in real-world applications; and SENNE has comparable
or higher accuracy than three existing state-of-the-art methods(SENCForest, SENCMaS, and ECSMiner), and it runs up to
one order of magnitude faster.
In reality, both new class and distribution change may occur
simultaneously in the data stream [14], [15], [16], and we will
investigate this more challenging problem in the future work.
Acknowledgment: This research was supported by the
NSFC (61673201).

[1] T. Tommasi, F. Orabona, and B. Caputo, “Learning categories from few
examples with multi model knowledge transfer,” IEEE TPAMI, vol. 36,
no. 5, pp. 928–941, 2014.
[2] Y. Zhu, K. M. Ting, and Z.-H. Zhou, “Multi-label learning with emerging
new labels,” in ICDM, 2016, pp. 1371–1376.
[3] Q. Da, Y. Yu, and Z.-H. Zhou, “Learning with augmented class by
exploiting unlabeled data,” in AAAI, 2014, pp. 1760–1766.
[4] Y. Zhu, K. M. Ting, and Z.-H. Zhou, “Discover multiple novel labels
in multi-instance multi-label learning,” in AAAI, 2017, pp. 2977–2984.
[5] M. M. Masud, J. Gao, L. Khan, J. Han, and B. M. Thuraisingham,“Classification and novel class detection in concept-drifting data streams
under time constraints,” IEEE TKDE, vol. 23, no. 6, pp. 859–874, 2011.
[6] X. Mu, K. M. Ting, and Z.-H. Zhou, “Classification under streaming
emerging new classes: A solution using completely-random trees,” IEEE
TKDE, vol. 29, no. 8, pp. 1605–1618, 2017.
[7] X. Mu, F. Zhu, J. Du, E.-P. Lim, and Z.-H. Zhou, “Streaming classification with emerging new class by class matrix sketching,” in AAAI,
2017, pp. 2373–2379.
[8] T. R. Bandaragoda, K. M. Ting, D. Albrecht, F. T. Liu, Y. Zhu, andJ. R. Wells, “Isolation-based anomaly detection using nearest-neighborensembles,” Computational Intelligence, vol. 34, no. 4, pp. 968–998,
2018.
[9] M. M. Breunig, H. Kriegel, R. T. Ng, and J. Sander, “LOF: identifying
density-based local outliers,” in SIGMOD, 2000, pp. 93–104.
[10] J. Gama, R. Rocha, and P. Medas, “Accurate decision trees for mining
high-speed data streams,” in KDD, 2003, pp. 523–528.
[11] C. C. Aggarwal, “A survey of stream clustering algorithms,” in Data
Clustering: Algorithms and Applications, 2013, pp. 231–258.
[12] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image
dataset for benchmarking machine learning algorithms,” CoRR, vol.
abs/1708.07747, 2017.
[13] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation ofword representations in vector space,” in ICLR, 2013.
[14] J. Gama, I. Zliobaite, A. Bifet, M. Pechenizkiy, and A. Bouchachia, “Asurvey on concept drift adaptation,” ACM Computing Surveys, vol. 46,
no. 4, pp. 44:1–44:37, 2014.
[15] Z.-H. Zhou, “Learnware: on the future of machine learning,” Frontiers
Computer Science, vol. 10, no. 4, pp. 589–590, 2016.
[16] P. Zhao, X. Wang, S. Xie, L. Guo, and Z.-H. Zhou, “Distribution-free
one-pass learning,” IEEE TKDE, 2019.