Clump is a rule based decision tree clusterer. At its core, it is a
binary tree with nodes that can have $0 - 2$ children. Each node
consists of a rule, its true and false conditions (if any), and a
collection of training data that has reached that node. When testing,
a testing example travels down the tree until it reaches a point
where there are no children nodes for it to follow. The data that
stored in that node is then passed to a naive bayes classifier for
final classification.

Most clustering algorithms use the nearest neighbor calculation to
determine which cluster a record belongs to. This record by record
comparison takes $O(n^2)$ comparisons, each record must be compared
against every other record to minimize the dissimilarity. Clump creates
it's clusters, not by minimum dissimilarity, but by grouping records
with similar attributes. Grouping by similar attributes leads to
decreased run-times. Frequency counts can be gathered, and cached,
which leads to decreased run-times. Frequency counts can be used to
determine which attribute value pair to split on because of the types
of rules created by Clump.

When training, Clump produces greedy rules, adding one attribute to the
rule at each level of the tree. Clump performs local feature subset
selection as it creates the rules, only considering attributes that
have not been considered further up the tree. The most important
feature, determined by the reduction in entropy, is chosen for the
splitting criteria at each branch of the tree. When choosing the
splitting criteria, the standard entropy calculation is not used. The
entropy is determined by the frequency of the different classes
represented in the training rows at each branch of the tree, relative
to the overall frequency of each class. This allows some features that
might only be important under specific circumstances to be used when
needed, and ignored in the other parts of the tree.

\input{figures/pseudoCode}

\subsection{Training}\label{tion:training}
Training, like most tree building algorithms is a recursive
process. Initially, a root node is made and populated with the entire
training set. The default class is also set to the majority
class. This root node is then passed to the training function. The
training function looks at the data in the node, and if there are
$\leq 15$ rows in the data, training terminates. If there are $\geq
15$ rows in the data, an optimal splitting criteria is chosen. Two
resultant nodes are created and added as children of the generating
node. All data from the generating node that satisfies the optimal
splitting criteria is added to the true child node, and all that does
not is added to the false child node. The process then recurses until
all nodes are created.

The optimal splitting criteria is used to create the rule, and split the data
into two groups: the data that satisfies the splitting criteria, and
the data that does not satisfy the splitting criteria. Each rule
created is conditional on the node's parent's rule.

\subsubsection{Scoring Function}\label{tion:scoring}
When choosing the optimal splitting criteria, all possible splitting
criteria for both positive and negative classes at a node are
explored. Each possible split receives a score based on the relative
frequency of the positive and negative records as described in
\eq{scoring} - \eq{scoringLast}.
\begin{equation}\label{eq:scoring}
  P_{true} = \frac{F_{true} \mid v}{F_{true}}
\end{equation}
\begin{equation}
  P_{false} = \frac{F_{false} \mid v}{F_{false}}
\end{equation}
\begin{equation}
  Score_{true} = \frac{P_{true}}{P_{true} + P_{false}}
\end{equation}
\begin{equation}\label{eq:scoringLast}
  Score_{false} = \frac{P_{false}}{P_{ture} + P_{false}}
\end{equation}

This scoring function removes the bias to choose classes with more
overall support. This is done by normalizing the frequency of the
class at a node by representing it as the percentage of all examples
of class $C$ present in the node. Comparing the relative frequency of
the true versus the false nodes this way can show the presence or lack
thereof of a bias towards one class versus the other.

\subsubsection{Dependent/Independent Attributes}
An attribute is independent\cite{dependance} when the attribute value
is disassociated from the class attribute. A
dependent\cite{dependance} attribute is when the attribute value is
considered in conjunction with the class attribute. Most clustering
algorithms\cite{GAC,08Turhan,KMeans,EM} consider independent attributes, building clusters without
considering the classes of the intra node instances. Clump builds its
clusters by reducing intra node entropy. To accomplish this, an
attribute value is chosen according to the process
is \tion{scoring}. The attribute chosen will create two sub clusters
each containing a higher frequency of one class than the combine
parent cluster.

\subsubsection{Boosting}\label{tion:boosting}
Traditional boosting\cite{Boosting} is where the training instances
that fail classification with one learner will be used to train a
second learner. This process can be repeated many times, resulting in
a chain of learners that can then be pooled for final
classification. This is commonly referred to as ``toilet learning,'' as
each successive learner is trained off of the dregs of the learner
before it. Clump represents boosting by creating sub clusters of data
when the data added to a cluster becomes too diverse. Clump creates
sub clusters that have a lesser combined mean degree of diversity
within each other than within the parent cluster.

\paragraph{AdaBoost}\label{tion:adaboost}
Clump shows some similarity to a boosting algorithm called AdaBoost\cite{adaboost}. AdaBoost repeatedly iterates over the model, modifying distributions at each iteration to reduce the overall error on the training set. Internally, a simple classification algorithm is used. This algorithm, called the WeakLearn, must only consistently perform better than random guessing. Through many iterations, the error rate is reduced. The main difference between Clump and AdaBoost is the branching associated with Clump. Data is split at each decision, meaning Clump is working with less and less data at each branch.

\input{figures/pseudoCode-testing}
\subsection{Testing}\label{tion:testing}
When testing, one or more testing rows are combined to form a chunk of
rows. Each row from a chunk is sent down the tree, and the data stored
at the node where the row stops is combined. The row of data continues
its travel down the tree, following the true and false branches as
necessary until a leaf node is reached. The row then travels back up
the tree until the last satisfied rule is reached. While combining the
data, any duplicates are ignored\footnote{A duplicate is defined as a
specific training instance, not the combination of attribute
values}. This combined training data is then passed to a Naive Bayes
classifier. Each row in the testing chunk is then passed to the Naive
Bayes classifier for final classification.

When gathering the data for the Naive Bayes classifier, each node is
marked if the data should be used in classification. Each node will
only be included once, even if multiple chunk rows fall to that
node. Some data may be included more than once because if a row stops
at a parent node and another row stops at a child node, the data in
the child node is also included in the parent node. After all the nodes have been marked, the tree is iterated through a second time to gather the final training dataset.

\subsection{Discretization}
The rules are based on which bin the discretized attributes belong
in. Rather than rules reading: ``If $\text{attribute}_x
< \text{value}$ then ...'', the rules for Clump read: ``If
$\text{attribute}_x \text{ is in bin } x$ then ...''. Discretizing is
done using equal width discretization\cite{EWD}. Each attribute range
is broken up into three different bins, with each bin having the same
width, or the same distance between the minimum and maximum values for
the bin. Three bins were chosen by experimental testing.

Equal width discretization was chosen above other options such as Equal frequency discretization\cite{EFD} and Fayyad \& Irani's MDL discretizer\cite{FayyadIrani}. These other options were tried, and showed no noticeable performance improvement, while adding complexity to the algorithm.


\input{figures/complexity}
\subsection{Runtime Complexity}
The theoretical runtime of Clump while training is O$((3kn + k) *
log_{kn})$ where k is the number of columns in the dataset, and n is
the number of rows. When training, each record is examined to determine
which bin it belongs to (O$(1kn)$). To create the bins, the minimum
and maximum values of each attribute must be found (O$(1kn)$). Next, a
Naive Bayes classification table is built with a runtime cost of
O$(1kn)$. If the data requires, a patch is created by examining the
frequency count tables for an attribute value pair that will reduce
the mixuped-ness of the data. This is repeated at each level of the
tree with the amount of data, in both the row count and the column
count, decreasing at each level of the tree.

With the current built-in classifier of Naive Bayes, the theoretical
maximum runtime for testing is O$(nkd)$, where d is the depth of the
tree. This worst case scenario occurs when all the data is contained
in a single cluster. The current maximum depth is limited to 15
levels. The theoretical minimum runtime for testing is
O$(\frac{nk}{d})$. This best case scenario occurs when the data is
evenly distributed across n-dimensional space, causing each node in
the tree to contain an equal number of rows.

\input{figures/numberOfRules}
\input{figures/numberOfConditions}
\subsection{Rule Complexity}\label{tion:clump-rule-complexity}
The number of rules for Clump, Ridor, and Ripper are shown in \tbl{numberOfRules}. The size of the rule tree generated by Clump is similar to the number of rules in Ridor and Ripper. When looking at within company tests, Clump has, on average, an extra 0.5 rules. In the Cross Company tests though, Clump generates the between same number of rules to twice the number of rules in Ridor and Ripper. Typically because of the increased number of training instance, Cross Company tests result in more complex models being learned. Clump, on the other hand, has the same theory complexity when looking at Cross Company as Within Company. The difference in the complexity of these three algorithms' models is apparent in \tbl{numberOfConditions}. \tbl{numberOfConditions} shows not just the number of rules generated by each algorithms, but the number of attribute value comparisons made in each learned model. In the Within Company tests, Ripper and Clump have approximately the same complexity: 1 comparison per rule. Ridor on the other hand has 2 comparisons per rule. These numbers start to really climb when looking at the Cross Company tests. Ripper and Ridor have between 3 and 5 comparisons per rule, while Clump still remains at 1 comparison per rule.
The simple theories learned by Clump help to provide a clear explanation for the theories learned.
