The performance of Clump will be compared to several different learners
in \tion{experiment} and \tion{results}. Among these learners will be:
\begin{itemize}
\item RIpple DOwn Rules, also known as Ridor\cite{ridor}
\item j48\footnote{This is a Java representation of J. Quinlan's c4.5
  learner.\cite{c4.5}}
\item jRip\footnote{This is a Java representation of W. Cohen's RIPPER
  learner.\cite{RIPPER}}
\item OneR\cite{OneR}
\item Naive Bayes\cite{NB}
\item Locally Weighted Learning\cite{LWL}
\end{itemize}

Four of the learners listed above are all rule based learners. Ridor
is a version of a Ripple Down Rule tree. j48/C4.5 is an extended
version of Quinlan's ID3 tree. jRip/RIPPER is an optimized version of
Cohen's IREP. OneR is a 1R algorithm; as soon as one rule is matched,
the processing stops. Locally Weighted Learning is Naive Bayes
augmented by weighting training instances by their nearness to the
test instance.

\subsection{Classifier Algorithms}
\input{fig/classifiers}
\input{classifiers}

\subsection{Clustering Algorithms}
Clustering algorithms attempt to reduce the time needed to search for
nearest neighbors. They accomplish this by forming a tree of the
nodes in the training set. The children of each node contain the
other nodes that share some ``nearness'' to the parent.  The speedup
in searching time needs to be balanced with the time necessary to
create and maintain this tree.

\input{clusterers}
\input{fig/clusterers}
\subsection{Burak Filter}
The Burak filter was designed to aid in Cross Company defect
prediction. As noted by Turhan et al., when Cross Company data was
used in defect prediction, the recall and false alarm rates both
increased drastically\cite{BurakFilter}. They determined that this
was caused by the increase defect examples, both pertinent and
extraneous. To remove the extraneous examples, the training data is
filtered with respect to the testing data.

This filter used the Euclidean distance between the testing and
training examples to find the k nearest neighbors per test
instance. The nearest neighbors for each test instance are combined to
form the training set. Any training instances that are within the k
nearest neighbors of more than one test instance are only included
once in the final training set. By training on only the nearest
neighbors to the test instances, theoretically only the relevant
training instances are examined.

The cost associated with generating this nearest neighbor information
is exponential, in the order of $O(N_{train}N_{test})$. For large
datasets, this preprocessing runtime is impractical as the neighbor
information must be recalculated for each testing example. Clump is
is proposed as an alternative to to Burak filter.

\subsubsection{Clump versus Burak filter}
Clump and the Burak filter\cite{08Turhan} both are used as a clustering
algorithm designed to aid a classifier. The Burak filter finds the k
nearest neighbors, based on Euclidean distance, to each testing
instance. This information is then passed to a classifier for final
classification. Like the Burak filter, Clump also finds the nearest
neighbors. The neighbors for Clump are determined by the training rows
left in the various nodes of the Clump tree. The testing instances are
run down the tree, and the resultant data is gathered. This process is
described in more detail in \tion{testing}.

The main difference between Clump and the Burak filter, run-times aside,
is in the amount of data returned. The Burak filter finds the k
nearest neighbors. Enforcing a value of k can cause unwanted data to
be gathered, or useful data to be set aside. If the testing row falls
in a very specific region of the n dimensional space where few other
instances fall, rows that are distant from the testing example can be
included in training the final classifier. Likewise, if the testing
row falls in a highly populated area, many useful rows can be left
behind. Clump overcomes this by including only the rows which are
similar to the testing row according to the rule tree generated during
training.
