%\documentclass[draftcls,onecolumn]{IEEEtran}% \textheight 
\documentclass[technote,9pt]{IEEEtran}
\newcommand{\aive}{a\"{\i}ve}
\newcommand{\given}{\/\,|\,}
\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
With Bayes Classifiers
Scales Very Well for Data With ``Early Plateaus''}
\author{Tim~Menzies, {\em Member,IEEE,} 
\thanks{Manuscript received XXX, 2004, revised August YYY, 2004.}
\thanks{Tim Menzies is with 
Computer Science, Portland State University;
\protect\url{tim@barmag.net}. Dr. Menzies' web
site is \protect\url{http://barmag.net}}
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. Further, this approach
supports forgetting old theories after concept drift and learning faster
when concepts drift back to a context seen previously.
\end{abstract}

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

\section{Introduction}

Our goal is intelligent adapative runtime monitoring of procedural
programs augmented with temporal logic invariants. We seek
data mining methods that can control Monte Carlo simulations of those
programs and intelligently constrain input ranges to increase the odds
that the invariants will be violated. 
To this end, this paper explores how to simplify the task of scaling up
induction to very large data sets. Such data sets are readily obtainable
in our domain: just run the Monte Carlo simulations on all the spare
CPUs left behind once our co-workers go home for the night.

Standard  classifiers are 
not designed to handle
very large data sets: they usually
assume 
that the data will be represented as a single, memory-resident table~\cite{provost99survey}.
Nevertheless, for data sets that exhibit {\em early plateaus} 
we show here that the following combination tools can
scale to very large data sets:
\bi
\item
a N\aive Bayes classifier;
\item an incremental discretizer called SPADE;
\item
a simple windowing sampling policy called SAWTOOTH.
\ei

\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 cross validation experiments
on soybean. 10 repeats. 10 divisions per repeat.
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. \fig{summ} shows such an early plateau in the
soybean~\cite{Blake+Merz:1998} data set. \fig{summ} is a {\em
incremental R*N-way cross-validation} experiment. For $R=10$
repeats, data was randomly shuffled.  The data in each random ordering
was then divided {\em N=10} ways. Two learners, J48 and nbk\footnote{ Both
learners come from the WEKA toolkit~\cite{witten99}.  J48 is release
eight of C4.5~\cite{quinlan92} ported to JAVA and nbk is a N\aive
Bayes classifier using John and Langley's kernel estimation
method~\cite{john95}}, were then trained using the first $i$ divisions
and tested using remaining {\em N-i} divisions.
 As might be expected, as more data is used for training
(i.e. running for 
{\em i=1\ldots(N-1))},  the accuracy of the learned theory
increased. For the soybean data set, this increase peaked 88\%/91\% for J48/nbk
respectively 
after seeing 60\% of the data
(409 instances). 


Other data sets can plateau even earlier than 
soybean.
\fig{sim1} shows the  plateaus found by four learners
(J48,nbk, LSR, and M5'\footnote{LSR and M5' come from the WEKA~\cite{witten99}.
LSR/M5' assumes 
values can be fitted to one/many (respectively)
 n-dimensional linear models~\cite{quinlan92b}.}) in 20
data sets (soybean appears in those results as the  ``J'' data set)
Those plateaus were found
before seeing most of the data:
usually, after seeing 50\%, and
mostly before after seeing 60\% (exceptions: E and F).
For any learner in \fig{sim1}, in $\frac{8}{10}$ths of the data sets, learning
did not improve significantly (computed using t-tests with $\alpha=0.05$)
after seeing 200 instances.

\fig{sim1}
suggests that, for many data sets and many learners,
learning could proceed
 in {\em windows}
of a few hundred instances.
Learning could be disabled once performance peaks within those
windows. If the learner's performance
falls off the plateau (i.e. due to concept drift),
the learner could start afresh to learn a new
theory. Given early plateaus like those in \fig{sim1}, this new learning
should take only a few more hundred instances.
Further, 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{center}
\includegraphics[width=1.6in]{plateauktnbk.pdf}
\includegraphics[width=1.6in]{plateaumsm5.pdf}\\
\includegraphics[width=1.6in]{plateauktj48.pdf}
\includegraphics[width=1.6in]{plateaumslsr.pdf}
\end{center}
\caption{{\em R=10*N=10} incremental cross validation
experiments on 20 UCI data sets~\cite{Blake+Merz:1998}.  A:heart-c,
B:zoo; C:vote; D:heart-statlog; E:lymph, F:autos. G:ionosphere,
H:diabetes, I:balance-scale, J:soybean, K:bodyfat. L:cloud,
M:fishcatch, N:sensory, O:pwLinear, Q:strike, R:pbc, S:autoMpg,
T:housing. Data sets A..J have discrete classes while Data sets K..T
have continuous classes. Data sets are sorted according to how many
instances were required.  to reach plateau using nbk (left-hand side)
or M5' (right-hand side).}
\label{fig:sim1}
\end{figure}


This paper tests that speculation. For numerous UCI data sets, some
KDD cup data, and in a aircraft flight simulator, this combination of
Bayes+SAWTOOTH+SPADE performs comparatively well, uses less memory,
and is simple to implement.  Our conclusion is twofold. Firstly, early
plateaus are common and hence very simple methods can scale to
numerous very large data sets. Secondly, at least some of the recent
advances in scaling up data mining are not be due to the
sophistication of the data miner.  Rather, they may be due to the
simplicity of the data in the test cases.

\section{Related Work}

Provost and Kolluri~\cite{provost99survey} 
note that while the performance of
some learners level off quite early,
other learners continue to
show accuracy increases as data set size increases.
However, that improvement 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}.

\fig{sim1} is not the first report
of early plateaus in the data mining literature
(though, to the best of our knowledge, it is the first report
of early plateaus in M5' and LSR).
Oates and Jensen found plateaus in 19 UCI data sets using five
variants of C4.5 (each with a different 
pruning method)~\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. 
Note that 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.

We are not motivated to
explore different methods for detecting start-of-plateau. 
The results below show that learning using our start-of-plateau
detector can produce adequate classifiers that scale
to very large data sets.


Assuming early plateaus,
then very simple learners should scale to large
data sets.
Our reading of the literature is that Bayes+SAWTOOTH+SPADE is much
simpler than other methods for scaling up data mining.  
Provost and Kolluri
distinguish three  general types of scale-up methods.
Firstly, there are {\em relational representation}
methods that reject the assumption that we should
learn  from a single memory-resident table. 
Secondly, there are {\em faster algorithms}
that (e.g.)
exploits {\em parallelism}.
Thirdly there are {\em data partitioning} methods to
learn  from (e.g.)  
some {\em subset of the attributes}.
SAWTOOTH is a {\em windowing} data partitioning scheme
where 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 is used in many systems
including FLORA~\cite{widmer96learning} and SAWTOOTH.
If the window size
$W$ is small relative to the rate of concept drift, then
windowing
guarantees the maintenance of a a theory relevant to the
last $W$ examples.  However, if $W$ is too small, the learning may
never have find an adequate characterization of the target concept.
Similarly, if $W$ is too large, then the this will slow the learner's
reaction to concept drift.
 
Like many windowing systems,
SAWTOOTH and FLORA 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 simple t-test to determine window size and,
in all our experiments, have kept parameters
of those tests constant (at $\alpha=0.01$).
A SAWTOOTH window is some integer
number of $era$s of size $E$; i.e. $W=nE$ (default: {\em E=100} 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.
In each era $k$, there
are $S_k$ successful classifications. 
The current era $j$ is different to
the proceedings eras $1...,i$ at confidence $\alpha=0.01$ if 
\[
-z(\alpha=0.01)=-2.326\le\frac{\mu_j - \mu}{\frac{\sigma}{\sqrt{E}}}=
\frac{\frac{S_j}{E} - \frac{\sum_i S_x}{\sum_i E}}{
\frac{\sqrt{E*\frac{S_j}{E}*\left(1-\frac{S_j}{E}\right)}}{\sqrt{E}}}
\]
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}
\begin{alltt}
{\scriptsize
\input{class.txt}}
\end{alltt}
\caption{A Bayes Classifier.
``?'' denotes ``missing values''.
In {\tt classify},
the probabilities are multiplied together using logarithms  to stop numeric
errors when handling very small numbers.
The $m$ and $k$ variables handle 
low frequencies counts using
Laplace and M-estimates~\cite[\S3.1]{yang02}.
This code computes $L(H\given E)$; i,e. class {\em likelihoods} not probabilities.
Likelihoods become probabilities when they are normalized over the sum
of all likelihoods. However, since maximum probability comes from
maximum likelihood, this code only needs to return the class
with maximum $L(H\given E)$.
}
\label{fig:class}
\end{figure}

One problem with  
windowing systems 
is the 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.

Apart from rapid updates, 
N\aive Bayes classifiers have other advantages.
Such classifiers use Bayes' Theorem:
\[
P(H\given E)=\frac{P(H)}{P(E)}\prod_iP(E_i\given H)
\]
That is, given fragments of evidence $E_i$ and a prior probability for
a class $P(H)$, a posterior probability $P(H\given E)$ is calculated
for the hypothesis given the evidence. 
The Bayes classifier returns
the class with highest probability.
Such 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.  

More importantly,
Bayes classifiers need very little
memory and hence can scale to very large problems.
These learners only need
the memory required for the frequency counts
plus a
buffer just large enough to hold a single instance. 
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}. 

Many kernel estimation and discretization methods violate the {\em one scan} 
requirement of a data miner;
i.e. learning needs 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.
Similarly, John and Langley's kernel estimation method 
can't build its distribution
until {\em after} seeing all the data.
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 is like {\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}).
\begin{figure}
\begin{center}
\includegraphics[width=2.4in]{spade.pdf}
\end{center}
\caption{Comparing SPADE and kernel estimation.
Data sets: 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}

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),
then 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.


\begin{figure}[!b]
{\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{figure}

\begin{figure*}
\begin{center}
\begin{minipage}{.6\linewidth}
\begin{center}
{\scriptsize
\begin{tabular}{r@{~}r|@{~}l|l@{}c@{~}l@{~}c@{~}l@{}c@{}lc@{}r|}\cline{3-9}
\multicolumn{2}{c}{}& \multicolumn{1}{|c|}{incremental} &\multicolumn{6}{c|}{batch}\\\cline{3-9}
data set & \#instances & SAWTOOTH & NB & & nbk&&j48\\\hline
\input{data/10way.dat}
\end{tabular}}
\end{center}
\end{minipage}\hfill
\begin{minipage}{.35\linewidth}
\begin{center}
\includegraphics[width=2in]{data/10way.pdf}
~\\
~\\~\\~\\
{\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}
%~\newline~\newline
}\end{center}
\end{minipage}
\end{center}
\caption{$mean \pm standard\; deviations$
seen in 10*10-way cross validation
experiments on UCI Irvine data sets.
``NB'' and ``nbk'' denote  N\aive Bayes
classifiers that use gaussians 
model continuous attributes.  ``NB'' uses a single
gaussian while ``nbk'' uses a sum of gaussians in the method
recommended by John and Langley~\cite{john95}.
The plot top-right sorts the differences in the accuracies
found by SAWTOOTH and all the other learners.
Some of those differences  aren't statistically significant:
the  ``+'' or ``-'' in the left-hand-side table denote 
mean differences that are significantly different
to SAWTOOTH 
at the $\alpha=0.05$ level.
The significant differences between
all the learners are shown in
the win-loss statistics of the bottom-right table.
 }\label{fig:uci}
\end{figure*}

\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 or 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) compensates for its occasional performing worse
than state-of-the-art alternatives which require far more memory.






\section{Experiments}


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}

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}}.
The KDD data 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 the {\em mean M*C scores}
for  SAWTOOTH and the  KDD'99 entrants. 
SAWTOOTH's mean $M*C$ 
results were 
close to the winning
score of entrant \#1;
very similar to entrants 10,11,12,13,14,15,16; and 
better than 
entrants 18,19,20,21,22,23,24.
These results are encouraging since SAWTOOTH is a much simpler tool that the winning
entry (which classified the security incidents using
an ensemble of decision trees built from a 50*10 cross-val).

Another encouraging result  is the {\em \# bins with tally=X}
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, in the worst case,
generate thousands of bins for each numeric attribute. 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. Lastly,
SPADE never generated more than 100 bins.


\begin{figure*}[!t]
\begin{center}
\includegraphics[width=6in]{data/recurrent.pdf}
\end{center}
\caption{SAWTOOTH and Concept Drift}\label{fig:flight}
\end{figure*}


\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. The large table on the left shows the mean
and standard deviations of the accuracy seen in  10*10 cross-validation
experiments.
The win-loss table (bottom-right of \fig{uci}) use t-tests
to compare the performance of our learners. SAWTOOTH performs
marginally better than a simple N\aive Bayes
classifier but is out-performed by both J48 and nbk.
This is not surprising:
Provost and Kolluri~\cite[p22]{provost99survey}
comment that 
sequential learning strategies like windowing
usually performs worse that 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
top-right of \fig{uci} sorts all those differences. In 80\% of our
experiments, SAWTOOTH performed within $\pm5\%$ of other methods.

\subsection{Data with Concept Drift}

\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 three times, the simulator returned to each error mode.
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. 

Three 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 significant result:
learning systems can alert their uses when they are {\em
leaving
the region of their past competency}.  Secondly, 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}.
Thirdly, between concept drifts, the accuracy stabilizes and
SAWTOOTH mostly disables the learner.  That is,
for much of \fig{flight} the SAWTOOTH ``learner'' is 
{\em doing
no learning at all}. 


\section{Conclusion}

Holte argue for {\em simplicity-first} approach to data mining;
i.e. researchers should try simpler methods before complicating
existing algorithms~\cite{holte93}.  While Provost and Kolluri endorse
``simplicity-first'', they note in their review of methods for scaling
up inductive algorithms 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 has been a simplicity-first approach to scaling up data
miners. We have {\em levered} two features of N\aive Bayes classifiers
that make them good candidates for handling large datasets: fast
updates of the current theory and small memory foot print. Several
{\em deficiencies} with N\aive Bayes classifiers have been addressed:
incremental discretization and dynamic windowing means that 
Bayes classifiers
need not
 hold all the data in RAM at one time. 

Our Bayes+SAWTOOTH+SPADE toolkit works via one scan of the data and
can scale to millions of instances.  Our toolkit is much simpler than
other scale-up methods such as FLORA or the winner of KDD'99.  Even so
it performs as well as many other data mining schemes (see
\fig{kdd99}). Also when used on smaller data sets, it performs within
$\pm5\%$ of other commonly used schemes (see
\fig{uci}).
Further, the same toolkit
without any modifications
can be used to detect concept drift, to repair a theory
after concept drift, and can reuse old knowledge when
old contexts re-occur (see \fig{flight}).

A 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}).

Why can such a simple toolkit like Bayes+SAWTOOTH+SPADE be so
competent for both small and large data sets? Our answer is that many
data sets (such as all those processed in our experiments) exhibit
early plateaus and such early plateaus can be exploited to build very
simple learners.  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.

Finally, we recommend that other data mining
researchers check for early plateaus in their data sets.
If such plateaus are a widespread phenmema, then
{\em very simple tools} (like Bayes+SAWTOOTH+SPADE)
should be adequate for the
purposes of scaling up induction. 


% 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}
%
% <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}


