\input{fig/exampleTree}
A rule tree classifier called Ripple Down Rules(RDR) was proposed by
Paul Compton in his 1991 paper titled ``Ripple Down Rules:
Possibilities and Limitations''\cite{rdr}. A basic Ripple Down Rule
tree is defined as a binary tree where each node contains:
\bi
\item A classification
\item A predicate function
\item A true branch
\item A false branch
\ei
The true and false branches are other nodes that may or may not
exist. The true and false branches are followed depending on the
outcome of the predicate function during testing. The true and false
nodes are created on demand, and are patches to the tree. Ripple Down Rule
trees are human maintainable and explainable.

With Clump, if the amount of entropy\footnote{Entropy is used to
represent a mix of different classes in a general sense, not in the
standard entropy calculation} in a node exceeds a threshold value, a
patch is created to reduce the intra-node entropy. Like Ripple Down
Rule trees, the clusters made by Clump are also human
maintainable.  \fig{exampleTree} shows a sample rule tree generated by
Clump.

Clump differs from standard clusterers. Most clustering algorithms group
rows based on the Euclidean distance between two rows or cluster
centroids\cite{KMeans,BallTrees,CoverTrees,KDTrees}. This Euclidean
distance (\eq{standard}) is determined by the combined absolute value
of the delta between the two rows or the row and the centroid.
\begin{equation}
\displaystyle\sum_{x=0}^k \Delta(\left| row_1[attribute_x] -
row_2[attribute_x]\right|)
\label{eq:standard}
\end{equation}
Clump accomplishes its clustering, not by Euclidean distance, but by how
relevant a particular feature is in splitting the data. The exact
equations used in determining the relevancy of a give attribute are
shown in \tion{training} \eq{scoring} - \eq{scoringLast}. Grouping
data by relevancy accomplishes much the same as grouping data by
Euclidean distance. It provides several benefits as well. There is an
explanation as to why a particular instance belongs to a particular
cluster. Also, the standard $n^2$ runtime of clustering algorithms is
avoided because decisions made in generating the tree are made in
respect to each row as its being examined, not to every row as each
row is being examined.

One goal of Clump is to create rule trees that are maintainable. The
maintenance can be accomplished in two ways. First, if a rule tree is
small enough, a human to look at the tree, and remember most if not
all of it by recall. This allows the human to notice
additions/subtractions that could be made to the tree by utilizing
domain specific knowledge. Second, a tree can be built during initial
training, and while being used with real-time data, can be patched to
adapt to the changing data.  A second goal of Clump is to form the
nearest neighbor structure from the data in linear or low order
polynomial time.

Rule trees offer a significant advantage to frequency count learners
such as Naive Bayes:
\begin{quote}
Rule trees offer not just answers, they offer explanation.
\end{quote}

Unlike Ripple Down Rules, Clump is not used for
classification, but for clustering. Clump is used to find the structure
within the data while avoiding the standard $O(n^2)$ clustering
algorithms. While testing, Naive Bayes is used to do the classifying
once the data has been limited by Clump as a clusterer.

This paper will explore the Clump/Naive Bayes combination while using 7
datasets from the Promise Data Repository\cite{ourmine}. The chosen
datasets focus on software defect prediction.
