%XXX general note. 
%windowing is also sub-sampling. get rid of the clumsy page 5 note.

%\documentclass[draftcls,onecolumn]{IEEEtran}% \textheight 
\documentclass[technote,9pt]{IEEEtran}
\newcommand{\aive}{a\"{\i}ve}
\newcommand{\given}{\/\,|\,}
\usepackage{amssymb}
\usepackage{alltt,cite,graphicx,url,amsmath,subfigure,wrapfig}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}
\begin{document}
\title{ Incremental Discretization and 
 Bayes Classifiers Handles Concept Drift and Scales Very Well}
\author{Tim~Menzies, {\em Member,IEEE,} 
\thanks{Manuscript received March, 2005, revised  YYY, 2005.}
\thanks{Tim Menzies is with 
Computer Science, Portland State University;
\protect\url{tim@menzies.us}. Dr. Menzies' web
site is \protect\url{http://menzies.us}}
Andres Orrego
\thanks{Andres Orrego is with Computer Science,
West Virginia University, USA;
\protect\url{Andres.S.Orrego@ivv.nasa.gov}}}
\markboth{IEEE Transactions on Knowledge and Data Engineering,~Vol.~X, 
No.~Y,~August~2005}{Menzies \& Orrego: Scalable Learning in Low Frequency Domains}
\maketitle


\begin{abstract}
Many data sets exhibit an {\em early plateau}
where the performance of a learner peeks after seeing
a few hundred (or less) instances.
When concepts drift is slower than the time to find that plateau,
then a simple windowing
policy and  an incremental discretizer lets standard learners like
N\aive Bayes classifiers to scale to very large data sets. 
Our tookit is simple to implment;
can scale to millions of instances;
 works 
as many other data mining schemes;
and, with trivial  modifications,
can be used to detect concept drift; to repair a theory
after concept drift; can reuse old knowledge when
old contexts re-occur
and can detect novel inputs during unsupervised learning.
\end{abstract}

\begin{keywords}
data mining, concept drift, scale up, N\aive 
Bayes classifiers, incremental, discretization,
SAWTOOTH, SPADE, novelty detection
\end{keywords}

\section{Introduction}

Holte argue for {\em simplicity-first} approach to data mining;
i.e. researchers should try simpler methods before complicating
existing algorithms~\cite{holte93}.  In their review of methods for
scaling up inductive algorithms, Provost and Kolluri endorse this
``simplicity-first'' approach.  However, they add that ``it is not
clear now much {\em leverage} can be obtained through the use of
simpler classifiers to guide subsequent search to address {\em
specific deficiencies} in their
performance''~\cite[p32]{provost99survey}.

This paper is a simplicity-first approach to scaling up data
miners. 
Consider what {\em leverage} a simple N\aive Bayes classifier
offers for scaling up induction. 
Such classifiers have two desirable features for
scalable induction: fast
updates and small memory footprints.
N\aive Bayes classifiers summarize the
training data in one frequncy table per class.  Hence,
they consume very little memory and they can quickly and
incrementally modify their knowledge by incrementing the frequency
count of attribute ranges seen in new training examples. 

However, simple N\aive Bayes classifiers have {\em specific
deficiencies}.  
When learning from a large data set, it is common for the data
generating phenomenon to change and standard N\aive Bayes classifiers
have no mechanisms for adapting to such {\em concept drift}.
Also,
when
processing very large datasets, it can be impossible
to scan it multiple times or store it all in 
in main memory.
Unfortunately, like many classifiers, N\aive Bayes assumes that all
the data is held in a single memory-resident
table~\cite[p32]{provost99survey}.  Also, N\aive Baues
handles numeric attributes via
either {\em discretization} or 
{\em kernel estimation} methods. 
Most known discretization and estimation methods
for N\aive Bayes require multiple passes through the 
data~\cite{john95,dou95,YanWeb02Comparative}.   
  
This paper reports an experiment in applying Holte's simplicity first
approach to resolving these specific deficiencies.  Experiments with
{\em incremental cross-validation}, discussed below, showed that many
data sets have a {\em early plateau} effect where classification
accuracy plateaus after a relatively small number of examples (just a
few hundred).  This motivated scale-up experiments with a {\em
windowing} scheme called SAWTOOTH that enables classification only
when performance is rising or falling from a plateau.  In accordance
with the Holte doctrine, SAWTOOTH was build by considering multiple
implementation options, then always implementing the simplest one. For
example, the windowing scheme was added to a simple N\aive Bayes
classifier. Also, our {\em
incremental discretization method}, called SPADE,
was based on the simplest
discretization method that we could find.
 
The experiment was quite successful.
SAWTOOTH/SPADE can execute via one scan of the data;
can scale to millions of instances; and works as well as many other
schemes for scaling up data mining.  With trivial modifications,
SAWTOOTH/SPADE can also detect concept drift; repair a theory after
concept drift; reuse old knowledge when old contexts re-occur; and
could detect novel inputs during unsupervised learning.

SAWTOOTH/SPADE can be used as a simple {\em baseline} system
to comparatively evaluate the merits of
seemingly more sophisticated implementations.
This evaluation has lead to the abandonment
of certain lines of research.
Elsewhere, we have explored novelty detection in unsupervised learning
using a variety of complex methods: association rules to learn
expected patterns in attribute values~\cite{me03b}; or SVDDs to
recognize boundaries between expected and novel inputs~\cite{me03p}.
SAWTOOTH/SPADE has now replaced those prior
implementations, which we now view as needlessly complex.




The rest of this paper describes the early plateau effect,
offers some background notes on N\aive Bayes, SAWTOOTH/SPADE,
then described experiments with numerous UCI data sets,
some KDD cup data, and an aircraft flight simulator. 


\section{Early Plateau}
%\begin{wrapfigure}{r}{1.8in}
%\begin{center}
%\includegraphics[width=1.8in]{soybean_ALL_accuracy.png}
%\includegraphics[width=1.6in]{graphs/iris_ALL_accuracy_changes.png}
%\end{center}
%\caption{Incremental 10*10 cross validation experiments
%on {\em soybean}. 
%Error bars show ${\pm}1$ standard deviations for the
%accuracies over the repeats.}\label{fig:summ}
%\end{wrapfigure}


A data set exhibits {\em early plateaus} when the peak performance of
a learner requires just a few hundred instances.  For datasets with
plateaus, learning could proceed in {\em windows} of a few hundred
instances.  After a small number of windows, performance would peak
and learning could be disabled.  If the learner's performance falls
off the plateau (i.e. due to concept drift), the learner could start
afresh.  Since learning only ever has to process
a few hundred instances at a time, this approach should scale to very
large data sets.

\begin{figure}[!t]
%\begin{wrapfigure}{r}{3in}
\begin{center}
\includegraphics[width=2.7in]{plateaudotsD.pdf}
\end{center}
\caption{{\em 10*10} incremental cross validation
experiments with 
J48 and NaiveBayes (with kernel estimation) on \{A:heart-c,
B:zoo; C:vote; D:heart-statlog; E:lymph, F:autos. G:ionosphere,
H:diabetes, I:balance-scale, J:soybean\};
M5 and LSR on \{K:bodyfat. L:cloud,
M:fishcatch, N:sensory, O:pwLinear, Q:strike, R:pbc, S:autoMpg,
T:housing\}. All data sets 
from the UCI repository~\cite{Blake+Merz:1998}.
Data sets A..J have discrete classes and are scored
via the {\em accuracy} of the learned theory; i.e 
\% successful classifications.
Data sets K..T
have continuous classes and are scored by the {\em PRED(30)} of the learned
theory; i.e. what \% of the estimated values are within 30\% of the actual 
value.}
\label{fig:sim1}
%\end{wrapfigure}
\end{figure}


One way to find plateaus is via incremental R*N-way cross-validation.
For $R=10$ repeats, the order of the data is randomly shuffled.  For
each random ordering, the data is then divided {\em N=10} ways.
Training is then conducted using the first $1\le i < N$ divisions and
tested using remaining {\em N-i} divisions.  As the size of the
training set grows, the accuracy of the learned theory improves.  At
the plateau point, this improvement flattens out.  After all the $R$
repeats, this plateau point can be identified when learning on
$\frac{Y}{10}$th of the data does not result in significantly greater
accuracies than using $\frac{\{1..X|X<Y\}}{10}$ of the data (computed
using t-tests with $\alpha=0.05$).

The y-axis of \fig{sim1} show the plateau points seen in R*N-way cross
validation experiments on 20 UCI data sets ($R=N=10$) using four
different learners: J48; NBK: N\aive Bayes with kernel estimation; M5,
and LSR\footnote{All learners come from the WEKA~\cite{witten99}.
LSR/M5' assumes values can be fitted to one/many (respectively)
n-dimensional linear models~\cite{quinlan92b}.  J48 is a JAVA
implementation of Quinlan's C4.5 decision tree
learner~\cite{quinlan92}.}.  In all the experiments, a plateau was
reached well before all the training instances were used.  Most of the
experiments ($\frac{33}{40}$) reached plateau in 200 instances or
less. Further, only a handful ($\frac{3}{40}$) of experiments needed
more than 300 instances to find their plateau.

This plateaus effect has been have been reported before (although this
may be first report of early plateaus in M5' and LSR).  Provost and
Kolluri~\cite{provost99survey} make the general comment that the
performance of some learners levels off quite early, without
specifying exactly how
early that might happen.  
They add that while some further accuracy
improvements are seen as data set size increases, those improvements
can be quite small.  For example, Catlett reports differences of less
than 1\% (on average) between theories learned from 5000 or 2000
randomly selected instances in ten different data
sets~\cite{catlett91}.

In another study, Oates and Jensen found plateaus in 19 UCI data sets
using five variants of C4.5~\cite{oates97}.  In their results, six of
their runs plateaued after seeing 85 to 100\% of the data.  This is
much later than \fig{sim1} where none of our data sets needed more
than 70\% of the data.  One possible reason for our earlier plateaus
is the method used to identify start-of-plateau.  \fig{sim1} detected
plateaus using t-tests to compare performance scores seen in theories
learned from $M$ or $N$ examples ($M<N$) and reported start-of-plateau
if no significant ($\alpha$=0.05) difference was detected between the
$N$ and the last $M$ with a significant change. On the other hand,
Oates and Jensen scanned the accuracies learned from $5,10,15\%$
etc. of the data looking for three consecutive accuracy scores that
are within 1\% of the score gained from a theory using all the
available data.  That is, \fig{sim1} shows the point where accuracies
stop {\em improving} as training sets {\em grow} while Oates and
Jensen report when accuracies start {\em degrading} as training sets
{\em shrink}. Given sufficiently large standard deviations, our method
will terminate on smaller training sets than Oates and Jensen.

The results below show that learning using our start-of-plateau
detector can produce adequate classifiers that scale to very large
data sets.  Hence, at this time,
we are not motivated to explore different methods
for detecting start-of-plateau.  In any case, regardless of {\em
where} they found plateaus, Oates and Jensen's results endorse our
general thesis that, often, learning need not process all the
available examples.
Rather, learning can jump through the available
data in windows of a few hundred instances at a time.





\section{Windowing}

In a
windowing system like SAWTOOTH, newly arrived
examples are pushed into the start of sliding window of size $W$ while
the same number of older examples are popped from the end.  
Windowing systems need to select an appropriate window size $W$.  If
$W$ is small relative to the rate of concept drift, then windowing
guarantees the maintenance of a theory relevant to the last $W$
examples.  However, if $W$ is too small, learning may never have find
an adequate characterization of the target concept.  Similarly, if $W$
is too large, then this will slow the learner's reaction to concept
drift.
 
Many windowing systems like SAWTOOTH and FLORA~\cite{widmer96learning}
select the window size dynamically: $W$ grows till stable performance
is reached; remains constant while performance is stable; then shrinks
when concept drift occurs and performance drops.  FLORA changes $W$
using heuristics based on accuracy and other parameters that take into
account the number of literals in the learnt theory. FLORA's authors
comment that their heuristics are ``very sensitive to the description
language used''. Hence, they claim that ``it seems hopeless (or at
least difficult) to make it completely free of parameters''.  This has
not been our experience: SAWTOOTH uses the simple standardized test
statistic of \eq{stab} to determine window size.  In all our
experiments we have kept parameters of those tests constant.
\begin{equation}\label{eq:stab}
-z(\alpha=0.01)=-2.326\le\frac{\mu_j - \mu}{\frac{\sigma}{\sqrt{E}}}=
\frac{S_j - (\frac{\sum_i S_i}{\sum_i E}*E)}{
\frac{\sqrt{E*\frac{S_j}{E}*\left(1-\frac{S_j}{E}\right)}}{\sqrt{E}}}
\end{equation}
\eq{stab} needs some explanation.
A SAWTOOTH window is some integer
number of $era$s of size $E$; i.e. $W=nE$ (default: {\em E=150} instances).
SAWTOOTH windows
grow until performance has not changed significantly
in a  $Stable$ (default: 2) number of eras.
Each era is viewed as a binomial  trial and each window is a record
of trail results in the eras $1,...i,j$
where era=$j$ is the current era and era=1 is the first report of instability.
Each era $k$ holds
$S_k$ successful classifications and
\eq{stab} checks if the current era $j$ is different to
the proceedings eras $1...,i$.



On stability, 
SAWTOOTH disables theory updates, but keeps 
collecting the $S$ statistics (i.e. keeps classifying new
examples using the frozen theory). 
If stability changes to instability, SAWTOOTH 
shrinks  $W$ back to one era's worth of data and 
learning is then re-enabled.

\begin{figure}[!b]
%\begin{wrapfigure}{r}{3in}
\begin{alltt}
\renewcommand{\baselinestretch}{1} 
{\scriptsize
\input{class.txt}}
\end{alltt}
\caption{A Bayes Classifier.
``?'' denotes ``missing values''.
Probabilities are multiplied together using logarithms  to stop numeric
errors when handling very small numbers.
The $m$ and $k$ variables handle 
low frequencies counts in the manner
recommended by Yang and Webb~\cite[\S3.1]{yang02}.
}
\label{fig:class}
%\end{wrapfigure}
\end{figure}


\section{N\aive Bayes}

One problem with  
windowing systems 
is  the computational cost of continually re-learning.
Hence SAWTOOTH uses a learner that can update
its knowledge very quickly. \fig{class} shows the
N\aive Bayes classifier used by SAWTOOTH.
The function {\tt update} in that figure illustrates
the simplicity of re-learning for a Bayes classifier:
just increment a frequency table $F$ holding counts
of the attribute values
seen in the new training examples.

In terms of scaling up induction, the most
important property of \fig{class} is the {\tt F} data structure
that holds the frequency counts.  
A Bayes classifier only needs the memory
required for the {\tt F} frequency counts
plus a
buffer just large enough to hold the {\tt test}
instance passed to \fig{class}'s {\tt classify} function.


N\aive Bayes classifiers are based on Bayes' Theorem. Informally, the
theorem says $next=old*new$ i.e. what we'll believe {\em next} comes
from how {\em new} evidence effects {\em old} beliefs.  More formally:
\[
P(H\given E)=\frac{P(H)}{P(E)}\prod_iP(E_i\given H)
\]
i.e. given fragments of evidence $E_i$ and a prior probability for
a class $P(H)$, the theorem lets us calcuate a  posteri probability
$P(H\given E)$. 
Technically, a Bayes classifier should return
the class with highest probability.
However, 
\fig{class}
actually, computes class {\em likelihoods}
not probabilities.
Likelihoods become probabilities when they are normalized over the sum
of all likelihoods. Since maximum probability comes from
maximum likelihood, this code only needs to return the class
with maximum likelihood. 
Note that unlikely instances have lower frequency counts and hence
lower likelihoods. 
In the sequel, we will
use this property of  likelihoods to 
recognizing novel instances in unsupervised learning.

Bayes  classifiers are called {\em {n\aive}} since they assume that
the frequencies of different attributes are independent.  In
practice~\cite{webb00a}, the absolute values of the classification
probabilities computed by Bayes classifiers are often inaccurate.
However, the relative ranking of classification probabilities is
adequate for the purposes of classification.
Many studies
(e.g.~\cite{hall03,dou95}) have reported that, in many domains, this
simple Bayes classification scheme exhibits excellent performance
compared to other learners.  



Other researchers have explored incremental Bayes classifiers
using modifications to the standard Bayes classifier: e.g. Gama alters the
frequency counts in the summary tables according the success rate of
the last $N$ classifications~\cite{gama00} while Chai et.al. updates
the priors via feedback from the examples seen up till
now~\cite{chai02bayesian}.  In contrast, we use standard Bayes
classifiers {\em without} modification.



Bayes classifiers can be extended to numeric attributes
using {\em kernel estimation} methods. 
The standard estimator assumes the central limit theorem and models each
numeric attribute using a single gaussian.
Other methods don't assume a single
gaussian; e.g. John and Langley's gaussian  kernel
estimator models distributions of any shape as the sum of multiple gaussians~\cite{john95}.
Other, more
sophisticated methods are well-established~\cite{FayIra93Multi},
but several studies report that even simple {\em discretization methods} suffice for
adapting Bayes classifiers to numeric
variables~\cite{dou95,YanWeb02Comparative}. 

John and Langley comment that their method
must access all the individual numeric values to build their
kernel estimator and this is impractical for large data sets.
Many discretization methods violate the  {\em one scan} 
requirement of a data miner: i.e. execute using only
one scan (or less)
of the data since there many not be time or memory
to go back and look at a store of past instances.
For example, 
Dougherty et.al.'s~\cite{dou95}  {\em straw man} discretization method
is {\em 10-bins} which divides attribute $a_i$ into bins of size $\frac{MAX(a_i)-MIN(a_i)}{10}$.
If MAX and MIN are calculated incrementally along  a stream of data, then instance data
may have to be cached and re-discretized if the bin sizes change. 
An alternative is to calculate MAX and MIN after seeing {\em all} the data.
Both cases require two scans through the data,
with the second scan doing the actual
binning. Many  other discretization methods (e.g. all the methods
discussed by Dougherty et.al.~\cite{dou95} and 
Yang and Webb~\cite{YanWeb02Comparative}) suffer from this two-scan problem.

An incremental one scan (or less) discretization method is needed for
scaling up induction. SAWTOOTH uses the SPADE method described below.

\section{Handling Numeric Attributes with SPADE}



Discretization converts continuous ranges
to a set of bins storing the tally of numbers that 
fall into that bin.
In order to process infinite streams of data, 
we developed a one-pass discretization method called SPADE (\underline{S}ingle
\underline{PA}ss \underline{D}ynamic \underline{E}numeration).

SPADE only scans the input data once and,
at anytime during the processing
of $X$ instances, SPADE's bins are available. 
Further, if it ever adjusts bins (e.g. when merging bins with very small tallies),
the information used for that merging comes
from the bins themselves, and not some second scan of the instances.
Hence, it can be used  for the incremental processing of very
large data sets. 

Unlike
standard
N\aive Bayes classifiers, SPADE
makes no assumptions about the underlying
numeric distributions.
SPADE is similar to {\em 10-bins} but the MIN and MAX change incrementally. 
The first value $N$ creates one bin and sets \{MIN=N,MAX=N\}. 
If a subsequent new value arrives inside the current
\{MIN,MAX\} range,
the bins from MIN to MAX are searched
for an appropriate bin.
Otherwise,  
a $SubBins$  number of new bins are created (default: SubBins=5)
and 
MIN/MAX is extended to the new value. 
For example, here are four bins:

{\scriptsize\[\begin{array}{r|c|c|c|c|c|c}\cline{2-5}
i   &              1&  2&  3 &  4 &                    min& max\\
border    &        10& 20& 30 & 40&                    10 &  40\\\cline{2-5}
\end{array}\]}
Each bin is specified by its lower {\em border}
value.
A  variable $N$ maps to the first/last bin if it is the current \{MIN,MAX\} value
(respectively). Otherwise it
maps to bin $i$ where $border_i < N \le border_{i+1}$.
Assuming $SubBins=5$, then if a new value $N=50$ arrives, five new bins
added above the old MAX to a new MAX=50:

{\scriptsize
\[\begin{array}{r|c|c|c|c|c|c|c|c|c|c|c}\cline{2-10}
i      &           1 & 2 & 3 &  4&  5&   6 & 7 & 8 &     9             &       min& max\\
border         &   10& 20& 30 & 40& 42& 44& 46& 48   &  50     &            10 &  50\\\cline{2-10}
\end{array}\]}
If the newly created number of bins exceeds a {\em MaxBins}  parameter
(default=the square root of all the instances seen to date)
then adjacent bins with a tally less than {\em MinInst}
(default: same as {\em MaxBins}) are merged
if the tally in the merged  bins is less than a {\em MaxInst} parameter (default: 2*{\em MinInst}).
Preventing the creation of very few bins with big tallies is essential
for a practical 
incremental discretizer.
Hence, SPADE checks for merges only occasionally (at the end of each era),
thuss allowing for the generation of multiple bins before they are merged. 

%\end{wrapfigure}
SPADE runs as a pre-processor to {\tt update} to N\aive Bayes. Newly arrived
numerics get placed into bins and it is this   bin number that is used
as the $value$ passed to {\tt update} or \fig{class}. Also, when SPADE 
merges bins, this causes a similar merging in frequncy tables entries
(the $F$ variable of \fig{class}). 

The opposite of merging would be to {\em split} bins with unusually
large tallies.  SPADE has no split operator since we did not know how
to best divide up a bin {\em without} keeping per-bin kernel
estimation data (which would be memory-expensive).  
Our early experiments suggested that adding
$SubBins=5$ new bins between old ranges and newly arrived out-of-range
values was enough to adequately divide the range. Our subsequent
experiments (see below) were so encouraging that we are not motivated
to add a split operator.




\fig{spade} compares results from SPADE and John and Langley's kernel estimation method
using the display format proposed by Dougherty, Kohavi and Sahami~\cite{dou95}.
In that figure,
a 10*10-way cross
validation  used three learners:
(a)~N\aive Bayes
with a single gaussian for every numeric; (b)~N\aive Bayes with
John and Langley's kernel estimation method
(c)~the \fig{class}
N\aive Bayes classifier using data pre-discretized by SPADE. 
Mean classification accuracies were collected and
shown  in \fig{spade}, sorted by the means $(c-a)-(b-a)$; 
that is, by the difference
in the improvement seen in SPADE 
{\em or} kernel estimation 
{\em over and above} a simple single gaussian scheme.
Hence, the left-hand-side
data sets of \fig{spade} show examples
where kernel estimation work comparatively better than SPADE while
the right-hand-side shows results
where SPADE did comparatively better.



Three features of \fig{spade} are noteworthy. Firstly, in a
finding consistent with those of Dougherty et.al.~\cite{dou95}, discretization can
sometimes dramatically improve classification the accuracy of a N\aive
Bayes classifier (by up to 9\% to 15\% in data sets C,F,M,0).  Secondly, Dougherty
et.al. found that even simple discretization schemes (e.g. 10-bins)
can be competitive with more sophisticated schemes. We see the same
result here where, in $\frac{13}{15}$ of these experiments, SPADE's mean
improvement was within 3\% of John and Langley's kernel estimation method. 
Thirdly, in two cases, SPADE's one scan
method lost information  and performed worse than assuming a single gaussian.
In data set A, the loss was minimal (-1\%) and in data set B SPADE's results
were still within 3\% of kernel estimation.
In our view, the advantages
of SPADE (incremental, one scan processing, distribution independent) compensates 
for its occasional performing worse
than state-of-the-art alternatives which require far more memory.




\section{Experiments}

%\begin{wrapfigure}{r}{3in}
\begin{figure}
\begin{center}
\includegraphics[width=2.4in]{spade.pdf}
\end{center}
\caption{Comparing SPADE and kernel estimation.
Data sets: {\em \{A=vowel,
B=iris,
C=ionosphere,
D=echo,
E=horse-colic,
F=anneal,
G=hypothyroid,
H=hepatitis,
I=heart-c,
J=diabetes,
K=auto-mpg,
L=waveform-5000,
M=vehicle,
N=labor,
O=segment\}}.}\label{fig:spade}
\end{figure}

\newcommand{\upp}{$\blacktriangle$}
\newcommand{\downn}{$\blacktriangledown$}

In all the following
experiments,
SPADE was run continuously on all incoming
data while SAWTOOTH worked on windows containing a
variable number of 
eras. Also,  when SAWTOOTH
accuracies
are reported, they are the accuracies seen on new instances 
{\em before} those instances update the frequency tables
of the N\aive Bayes classifier. That is, all the
SAWTOOTH accuracies reported
below  come from data {\em not} (yet) used to train the classifier.

\subsection{KDD'99 Data}


\begin{figure}[!t]
%\begin{wrapfigure}{r}{3in}
{\scriptsize
\begin{center}
\includegraphics[width=1.4in]{data/kdd.pdf}~~~~
\includegraphics[width=1.4in]{data/kddbands.pdf}
\end{center}}
\caption{SAWTOOTH and the KDD'99 data}\label{fig:kdd99}
%\end{wrapfigure}
\end{figure}
In order to stress test our system, we ran it on the 5,300,000
instances used in the 1999 KDD
cup\footnote{\url{http://www.ai.univie.ac.at/~bernhard/kddcup99.html}}.
KDD'99 dealt with network intrusion detection and was divided
into a training set of about five million instances and a {\em test
set} of 311,029 instances.  The data comprised 6 discrete attributes,
34 continuous attributes, and 38 classes which fell into four main
categories: {\em normal} (no attack); {\em probe} (surveillance and
other probing); {\em DOS} (denial-of-service); {\em U2R} (unauthorized
access to local super-user privileges); and {\em R2L} (unauthorized
access from a remote machine).

The 24 KDD'99 cup entrants ran their learners to generated a matrix
$M[i,j]$ showing the number of times class $i$ was classified
$j$. Entries were scored by computing the mean $M[i,j]*C[i,j]$ value
where $C[i,j]$ was the cost of mis-classifying (e.g.) unauthorized
access to super-user as (e.g.) just a simple probe.  Note that $M*C$
are {\em mis-classification} scores so a {\em lower} score is better.

\fig{kdd99} shows all the sorted {\em mean M*C scores}
from the KDD'99 entrants.  
Also shown in that figure is  SAWTOOTH's mean \mbox{$M*C$} result.
SAWTOOTH's results 
were close to the winning score of entrant \#1; very similar to
entrants 10,11,12,13,14,15,16; and much better than entrants
18,19,20,21,22,23,24.  These results are encouraging since SAWTOOTH is
a much simpler tool that many of the other
entries. For example, the winning entrant 
took several runs to divide the data into smaller
subsets and buid an ensemble of 50x10 C5 decision trees using an
intricate cost-sensitive bagged boosting technique.  This took more
than a day to terminate on a dual-processor 2x300MHz Ultra-Sparc2
machine with 512MB of RAM using the commercially available
implementation of C5, written in ``C''.  In contrast, our toolkit
written in interpreted scripting langauges (gawk/bash),
processed
all 5,300,000 instances in one scan of  the data using less than 3.5
Megabytes of memory. This took  11.5 hours on a 2GHz Pentium 4, with 500MB of
RAM, runing Windows/Cygwin
and we conjecture that that this 
runtime could be greatly reduced by porting our toolkit to ``C''.

Another encouraging result is the {\em \# attributes with X bins} plot of
\fig{kdd99}. One concern with SPADE is that several of its internal
parameters are linked to the number of processed instances; e.g. {\em
MaxBins} is the square root of the number of instances.  The 5,300,000
instances of KDD'99 could therefore generate an impractically large number 
of bins for each numeric attribute. This worst-case scenario
would occur if each consecutive group of $SubBins$ number of numeric
values has different values from the previously seen groups {\em and}
they are sorted in ascending or descending order. If this
unlikely combination of events does {\em not} occur then the resulting
bins would have tallies than
$MinInst$, encouraging it to merge with the next bin.  
In all our experiments,
we have never seen this worst-case behavior. 
In KDD'99, for example,
SPADE only ever generated 2 bins for 20 of the 40 attributes. Also,
for only two of the attributes, did SPADE generate more than 50
bins. Further, SPADE never generated more than 100 bins for any attribute.





Attempts to test our system using  other KDD cup data were not successful, for a variety
of reasons\footnote{The KDD'04 evaluation portal was off-line
during the period when SAWTOOTH was being developed.
The KDD'03 problem required feature
extration from free text- something that is
beyond the scope of this research.
The data for KDD'02 is no longer on-line.
The KDD'01 had data with 130,000 attributes
and we don't yet know how to extend our technqie to
such a large attribute space.
We had trouble following the  KDD'00 documentation.}.



\subsection{UCI Data}




\fig{kdd99} explored SAWTOOTH's competencies
on one large data set.
\fig{uci} explores SAWTOOTH's competency on many smaller
data sets from the standard UCI database:
{\em \{anneal, audiology, auto-mpg, diabetes, echo, heart-c, hepatitis, horse-colic,
hypothyroid, ionosphere, iris, labor, letter, primary-tumor, segment, soybean, vehicle,
vote, vowel, waveform-500\}}.  Those data sets ranged in size 
from {\em labor}'s 57 instances
to {\em letter}'s 20,000 instances.
A standard 10*10 cross-validation experiment was conducted
using SAWTOOTH/SPADE (using the \fig{class} code);
or the J48 decision tree learner;
or two N\aive Bayes classifiers
that used either a single gaussian to
model continuous attributes (the ``NB'' learner)
or  a sum of gaussians
(the ``NBK'' learner proposed by John and Langley~\cite{john95}).



\begin{figure}[!t]
%\begin{wrapfigure}{r}{3in}
\begin{center}
\renewcommand{\baselinestretch}{1} 
{\scriptsize
\begin{tabular}{|c|c|c|c|c|c|c|} \hline
learner & win - loss & win & loss & ties \\ \hline
J48        &     10 &     25 &     15 & 20 \\
NBK        &      8 &     17 &      9  & 34\\
SAWTOOTH        &     -6 &     12 &     18 & 30\\
NB        &    -12 &      9 &     21 & 30 \\
\hline
\end{tabular}}

\includegraphics[width=2in]{data/10way.pdf}
\end{center}
\caption{SAWTOOTH exeucting on UCI data. }\label{fig:uci}
%\end{wrapfigure}
\end{figure}
Using t-tests, significant differences ($\alpha=0.05$)
between the mean performance of each learner on the 20 data sets
could be detected. Win/loss/ties statistics for each pair of
learners on each data set was then collected.
The results, shown top of \fig{uci} shows
SAWTOOTH performing
marginally better than NB
classifier but worse that both J48 and NBK.
This is not surprising:
Provost and Kolluri~\cite[p22]{provost99survey}
comment that 
sequential learning strategies like windowing
usually performs worse than learning from the total
set. 

However, what is encouraging is the {\em size}
of the difference in mean accuracies
SAWTOOTH and the other learners. The plot shown
bottom of \fig{uci} sorts all those differences. In 80\% of our
experiments, SAWTOOTH performed within $\pm5\%$ of other methods.



\subsection{Data with Concept Drift}

\begin{figure}[!t]
%\begin{wrapfigure}{r}{3in}
\begin{center}
\includegraphics[width=3.2in]{data/recurrent.pdf}
\end{center}
\caption{SAWTOOTH and concept drift}\label{fig:flight}
%\end{wrapfigure}
\end{figure}
\fig{kdd99} and
\fig{uci} showed SAWTOOTH processing static data.
\fig{flight} shows SAWTOOTH running on data
with concept drift.
To generate that figure,
a flight simulator was executed where
a airplane moved from a nominal mode to one of
five error conditions (labeled {\em a,b,c,d,e}).
Data was taken from the simulator in eras of size
100 instances. Each error mode lasted two eras
and each such mode was encountered twice.
The top of \fig{flight} shows the results
of SAWTOOTH's stability tests as well as when
SAWTOOTH enabled or disabled learning. Each error mode 
introduced a period of instability which, in turn,
enabled a new period of learning.

The {\em first} time SAWTOOTH saw a new error mode
(at eras 15,23,31,39,and 47), the accuracy drops 
sharply and after each mode, accuracy returns to a high level
(usually, over 80\%).
The {\em second} time SAWTOOTH returned to a prior  error
mode  (at eras 63,71,79,87 and 95),
the accuracies drop, but only very slightly. 

Two features of \fig{flight} are worthy of mention.
Firstly, the large drop in accuracy when entering  a new
context means SAWTOOTH can be used to recognize new
contexts (watch for the large drops). 
In terms of certifying
an adaptive system, this is a very useful result:
learning systems can alert their uses when they are {\em
leaving
the region of their past competency}.
Secondly, and most importantly, there is
no such large drop when SAWTOOTH returns to old contexts.
That is, SAWTOOTH can  {\em retain knowledge of old contexts} 
and reuse that knowledge {\em when contexts re-occur}.

\subsection{Unsupervised Learning}

\fig{kdd99}, \fig{uci}, and \fig{flight}  were all examples of 
{\em supervised learning}.  In supervised learning (when each instance
is stamped with a class symbol), handling concept drift means {\em
recognizing} when the underlying data generating phenomenum has
changed; and {\em repairing} the current classifier to cope with that
change.

\begin{wrapfigure}{r}{1.8in}
\begin{center}
\includegraphics[width=1.8in]{data/avglhall.pdf}
\end{center}
\caption{Learning normal flight (eras 1 to 8); 
monitoring five different
flights a,b,..e 
(eras 9 to 16); injecting errors into eras 15,16.}\label{fig:avglhall}
\end{wrapfigure}
\fig{avglhall} shows
an {\em unsupervised learning} experiment
(where instances lack any class symbol). In unsupervised learning,
it no longer makes sense to {\em repair} the classifier since there
are no classes to classify. However, the problem of {\em recognizing}
novel situations remains. 

In the \fig{avglhall} experiment, the class of all instances were
replaced with a single label: $class0$.  Eras one to eight of that
figure show SAWTOOTH processing eight eras (of 100 instances) of
nominal flight simulator data.  Updating the frequency tables was then
disabled and the system watched over five entirely different flights,
each ending with one of our errors {\em a,b,c,d,e}.  The {\tt
classify} routine of \fig{class} was modified to return the
classification with the maximum likelihood {\em as well as} that
maximum likelihood value. \fig{avglhall} shows the average maximum
likelihood seen in each era.  In all cases, the era 15,16 errors
dramatically changed the likelihoods: they dropped by {\em two orders
of magnitude} from the pre-error values and they dropped {\em below}
the liklihooods seen during training (eras 1 to 8).

This sudden drop in average maximum likelihoods could be used
to recognize novel situations.
Such a novelty detector could monitor (e.g.)
an adapative controller for a jet fighter and propose switching to
manual control (or bailing out) if the inputs are
radically different to what has been seen before.


\section{Limitations}

The premise of our system is that the dataset being processed
comes from a data generating phenomena that with context
drifts
that are slower than the time required to reach plateau.
If a particular data sets does not contain early
plateaus then our simple toolkit should be exchanged for a more
sophisticated scheme. Also, our toolkit is inappropriate
if concept drift is occurring
{\em faster} than the time required to collect enough
instances to find the plateau.

 
Another drawback with out toolkit is that we can't guarantee 
that our learner operates in
small
constant time per incoming instance.
Several of SPADE's internal parameters are functions
of the total number of instances. In the worst case,
this could lead to runaway generation of bins. 
On a more optimistic note, we note that this
worst case behavior has yet to be observed in our experiments:
usually, the number number of generated bins is quite small
(see \fig{kdd99}).

Note that our scheme is designed for {\em
large} data sets
and so does not perform as well as other commonly used schemes
when used on {\em smaller} data sets
(but often achieves accuracy on small data sets within
$\pm5\%$ of other learners schemes-
see \fig{uci}).



\section{Conclusion}

Before implementing seemingly
more sophisticated schemes, it can be valuable to first build the simplest
possible initial implementation.
SAWTOOTH/SPACE were
designed in accordance with Holte's
simplicity-first methodology.   SAWTOOTH/SPADE
is much simpler than other data miners such
as FLORA, the winner of KDD'99, or the SVDDs we used previously for
detecting novel inputs~\cite{me03p}.  
Despite its simplicity, the system performs remarkably well.
SPADE, plus SAWTOOTH
executes via one scan
of the data. 
\fig{kdd99} shows one example where this method scales to millions of
instances while working as well as many other schemes for scaling up
data mining. 

The system has other advantages:
\bi
\item
In \fig{spade}, the SPADE discretizer
was  applied to standard small UCI data sets.
This discretizer
performed nearly as well as other discretization
methods {\em without} requiring
multiple passes through the data.
\item
\fig{avglhall} traced SAWTOOTH's behavior when used for
novelty detection in unsupervised learning.  Without even knowing the
target classes of a system, a V\&V agent could monitor the average
maximum likelihood of the input examples. If that likelihood suddenly
drops by orders of magnitude, then the agent could raise an alert that
it is unlikely that the adaptative system is seeing inputs similar to
what is has handled previously.
\ei




% if have a single appendix:
%\appendix[Proof of the Zonklar Equations]
% or
%\appendix  % for no appendix heading
% do not use \section anymore after \appendix, only \section*
% is possibly needed

% use appendices with more than one appendix
% then use \section to start each appendix
% you must declare a \section before using any
% \subsection or using \label (\appendices by itself
% starts a section numbered zero.)
%
% Use this command to get the appendices' numbers in "A", "B" instead of the
% default capitalized Roman numerals ("I", "II", etc.).
% However, the capital letter form may result in awkward subsection numbers
% (such as "A-A"). Capitalized Roman numerals are the default.
%\useRomanappendicesfalse
%
\section*{Acknowledgment}
% optional entry into table of contents (if used)
%\addcontentsline{toc}{section}{Acknowledgment}
This research was 
conducted at West Virginia University, Portland State University,
partially
sponsored by the NASA
Office of Safety and Mission Assurance under the Software Assurance
Research Program led by the NASA IV\&V Facility.  Reference herein to
any specific commercial product, process, or service by trade name,
trademark, manufacturer, or otherwise, does not constitute or imply
its endorsement by the United States Government.
% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section
% NOTE: BibTeX documentation can be easily obtained at:
% http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/

% can use a bibliography generated by BibTeX as a .bbl file
% standard IEEE bibliography style from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/supported/IEEEtran/
\bibliographystyle{IEEEbib}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{../../refs}
\bibliography{refs}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)

% biography section
% 
% If you had an eps/pdf photo file (graphicx package needed)
% the extra braces prevent the LaTeX parser from getting confused
% when it sees the complicated \includegraphics command within an
% optional argument. You can create your own macro to make things
% simpler here.
%\begin{biography}[{\includegraphics[width=1in,height=1.25in,clip,keepaspectratio]{mshell.eps}}]{Michael Shell}
% or if you just want to reserve a space for a photo:

% You can push biographies down or up by placing
% a \vfill before or after them. The appropriate
% use of \vfill depends on what kind of text is
% on the last page and whether or not the columns
% are being equalized.

%\vfill

% Can be used to pull up biographies so that the bottom of the last one
% is flush with the other column.
%\enlargethispage{-5in}

% that's all folks
\end{document}


SAWTOOTH's 
windowing policy is also an implicit
{\em stratified sampling policy}.
In {\em
straified sampling}, instances are sampled according to the relative
frequency of their classes; e.g. instances from the minority classes
are selected with a higher frequency that instances from the majority
classes.
Consider a run containing windows 1,2,\ldots,50 where
all the instances come from class1 except 
in windows 10,11 which contain
class2. If 
plateau is reached after two windows, then, at most,
SAWTOOTH
would only use two windows of class2 data (since that is
all there is) and four windows of class1 data (the first two
eras
after the start and two more eras after the class2 eras).
This means that SAWTOOTH
would under-sample the majority class
and ignore 88\% of the class1 data.
