This section is a collection of different ideas and experiments in the realm of machine learning.  It focuses mainly on the different types of
properties that software defect detection experiments and data tend to have.  \sect{arffformat} discusses the properties of a special data format
that is used throughout this thesis.  \sect{samplingpolicies} discusses the different sampling policies that have been used in the past and
created for this work that this thesis uses in its varying experiments.  \sect{classical} discusses details about the different machine learners
that either this thesis has used in experiments or other experiments have used. \sect{rocnrule} covers various comparison methods for the
different heuristics of learners as well as defines a few core concepts in the performance evaluation of machine learners.  \sect{xval} discusses
the main method of dividing up the data sets into a train and a test set that nearly all of the experiments do.  \sect{relatedevaluation} discusses
the different types of comparison methods that are used in the various experiments throughout this thesis. \sect{pareto} explains a common
phenomenon in the distribution of faults that has been discovered in several different data sets. \sect{previousexp} covers some of the
previous work that has been done in the field of automatic defect detection.

\section{The ARFF Format}
\label{arffformat}
\begin{figure}[!ht]
\ssp
\scriptsize
\lstset{language=Python}
\lstset{backgroundcolor=\color{listinggray}}
\lstset{frameround=tttt}
\lstset{basicstyle=\scriptsize}
\lstset{showstringspaces=false, showspaces=false, showtabs=false}
\begin{center}
\begin{lstlisting}[frame=trBL]{}
	@relation weather.nominal

	@attribute outlook {sunny, overcast, rainy}
	@attribute temperature {hot, mild, cool}
	@attribute humidity {high, normal}
	@attribute windy {TRUE, FALSE}
	@attribute play {yes, no}

	@data
	sunny,hot,high,FALSE,no 
	sunny,hot,high,TRUE,no  
	overcast,hot,high,FALSE,yes
	rainy,mild,high,FALSE,yes
	rainy,cool,normal,FALSE,yes
	rainy,cool,normal,TRUE,no
	overcast,cool,normal,TRUE,yes
	sunny,mild,high,FALSE,no
	sunny,cool,normal,FALSE,yes
	rainy,mild,normal,FALSE,yes
	sunny,mild,normal,TRUE,yes
	overcast,mild,high,TRUE,yes
	overcast,hot,normal,FALSE,yes 
	rainy,mild,high,TRUE,no
\end{lstlisting}
\end{center}
\normalsize
\caption{Example ARFF File, Data Taken from UCI Repository\cite{uci}.}
\label{fig:examplearff}
\dbsp
\end{figure}
The Attribute$-$Relation File Format, or ARFF, was developed for use with the wEka\cite{weka}.  This format is used by all of the machine
learners that the wEka implements, as well as the Which learner described in \chap{which}.  ARFF can be broken up into two specific regions,
the header and the body. The ``\%'' symbol is used as a comment in an ARFF file and can occur anywhere on a line and in both sections.  ARFF
files are case$-$insensitive.  An example ARFF file can be seen in \fig{examplearff}.

\subsection{Header}
\label{arffheader}
The header contains the meta$-$data that the machine learner reading the file can use to set up the required structures for reading in and
understanding the data.  This meta$-$data can also be used to check the data to make sure it is correct.  The first part of the header file is
a line that starts with ``@releation $<description>$''.  This keyword is meant to describe the type of data this file represents.  The $<description>$
portion can contain spaces, but must be surrounded by quotes if it does.  Following the @relation keyword, a series of ``@attribute $<name>$ $<type>$''
lines appear, as can be shown in \fig{examplearff}.  There are a few types of attributes that can be used and they are described in \tab{arfftypes}.

\begin{table}[!ht]
\begin{center}
\begin{tabular}{|r|l|} \hline
	Numeric & Used to define values that fall into the real numbers. \\ \hline
	String & Used to define values that are strings. \\ \hline
	Date & Used to define dates.  A date format is also required \\ \hline
	Nominal & Used to define discrete $-$valued attributes. \\ \hline
\end{tabular}
\caption{Description of Possible Data Types for Attributes in ARFF.}
\label{tb:arfftypes}
\end{center}
\end{table}

As is mentioned in \tab{arfftypes}, the date attribute type needs a date format as well.  This format is by default in the ISO$-$8601 format of
``$yyy-mm-dd'T'HH:mm:ss$.''  This can be altered to allow for different representations.  The format described in the declaration of the date
attribute must be adhered to in the body section of the ARFF file.

The nominal type, as described in \tab{arfftypes}, is used to define discrete$-$valued attributes.  The word \textit{nominal} does not actually,
appear in the ARFF file, however.  Instead the possible values of this attribute are declared after the attribute name and surrounded by ``$\{\}$''.
An example of this is the variable \textit{outlook} in \fig{examplearff}.  Outlook can have three possible values, sunny, overcast and rainy.  All
discrete$-$valued attributes must be defined in this way and all possible values must be defined.

The final attribute in the ARFF file has special meaning.  This attribute is considered the \textit{class} of the data file and is what is used in
the wEka as the target for prediction.  The class attribute can be any of the types listed in \tab{arfftypes}.  The class need not be called class, and
in the example in \fig{examplearff} it is called \textit{play}.

\subsection{Body}
\label{arffbody}
The body of the ARFF file is designated by a line with ``@data'' written on it.  After this point no new meta$-$data can be declared.  The body
is just a series of comma seperated values that represent the attributes in order.  Each row in the body portion of the ARFF file is called an
\textit{instance}.  An instance is considered one specific case of data that was recorded.  Each instance must contain one value for each
of the attributes listed in the header portion and these attribute$-$values must be in the same order the attributes were declared in, thus
ending with the class always.  It is possible for ``?'' to appear in the body as values without being specifically declared as a possible value
for an attribute in the header section.  The ``?'' stands for an unknown.  Different learners handle unknowns in different ways.

\section{Sampling Policies}
\label{samplingpolicies}
A sampling policy in terms of data mining is a method of altering the data in order to allow machine learners to perform better on a given
data set.  There are several different type of sampling policies.  Below is an explaination of the different kinds of sampling policies that
are used in the experiments of this thesis, found in \chap{experiments}.

\subsection{Discretization}
\label{samplingdisc}
Discretization is the process of converting a real$-$valued attribute into a discrete$-$valued one. There are many ways to achieve this 
effect and \cite{djboland} did several experiments to illustrate the effectiveness of the different policies. Three of the the most common
methods used are equal interval, equal frequency,  and FayyadIrani\cite{fayyadirani}.  A comparison of these discretization methods, with others
can be found in \cite{dougherty95supervised}.  This comparison is done by using the discretization methods as a preprocessor and then running the
\nbc machine learner on the data and comparing the results.  More information on the \nbc learner can be found in \sect{bayes}.
There are at least two reasons for discretization.  The first reason is that several machine learners only work on discretized data, or that certain
types of machine learners can perform better on discretized data\cite{discretization2}. A second reason is that discretizing the data can simplify
the search process by limiting the range of the attributes to smaller range.  This second reason can not only allow the machine learner to perform
better by having less space to search, but can also decrease the run time of the application.

As an example of the first reason for converting continuous attributes into discrete ones could be an example of \nbc.  As is 
discussed in \sect{bayes}, \nbc uses a table to store the frequencies of each attribute value that appears in the data set\cite{bayes}.  
Using continuous values could result in a very sparse look$-$up table, as many of the values could only appear once in the entirety of the data set.
Also, using this continously ranged look$-$up table would result in values that have not been seen in the train set not having a frequency in the
test set.  As will be explained in the section on \nbc, this would result in the instance containing the new value not being classified.

Another example of the first reason for converting continuous attributes into discrete ones is an example of a decision tree machine learner, 
like j48 discussed in \sect{j48}.  As a brief introduction, a decision tree learner makes its classification criteria by choosing an attribute
to split into partitions based on some splitting criteria.  If attributes were continuous, splitting on an attribute that is continuous
could lead to many of the branches to be pure in that there is only one instance of data that contains that continuous value\cite{discretization2}.
In contrast, using a discretization method to either lump together continuous ranges as a single value for the attribute can prevent this problem
from happening.

The current idea behind discretization is that the values in each bin of the discretization are continuous values.  That is there will never
be a bin that contains two disjoint ranges of numbers.  A potential bin that is generated from a discretization policy could be $[0,10)$, whereas
a bin such as $[0,5)\wedge[8,10)$ is not traditionally created.  In \chap{which} this idea of disjoint combinations of attributes is discussed
and an idea of using Which to create a discretizer is further elaborated on in \chap{conclusion}.  The three discretization policies discussed here
use the idea of discrete bins of continuous attributes always containing continuous ranges.

\subsubsection{Equal Interval}
\label{equalintervalsect} 
Equal interval discretization is an \textit{unsupervised} discretization policy.  This means that each attribute is discretized in isolation, or that
the process of discretization is done independantly of the class or any other attributes in the data set.  This type of discretization is not
done in any of our experiments, but it is a part of the Which source code and an option.  For further information on the use of the Which
program, please see \app{usingwhich}.  Equal interval discretization is considered to be the simplest discretization method\cite{discretization1}, 
as it takes nothing about the data into account and the bins have a variable number of items in them\cite{discretization1}.

Equal interval discretization is a two phase process.  The first phase is to go over the entire range of the data set and find the minimum and
maximum values the attribute can have.  The second phase involves using \eq{equalintervalbineqn} with val being the value of the attribute
for each instance of data to calculate which bin this value should be in.  This method of discretization creates $n$ bins each containing
the same interval length.  However, each bin does not necessarily have to have the same number of numbers in it.  In fact, it is entirely
possible for some of the bins to be completely empty\cite{discretization1}.  A histogram of a possible configuration of bins can be seen in 
\fig{equalintervalhist}\cite{discretization1}.

\begin{center}
\begin{equation}
	bin = \lfloor\frac{val-min}{max-min}\rfloor * n
\label{eq:equalintervalbineqn}
\end{equation}
\end{center}

\begin{figure}[!ht]
\begin{center}
	\includegraphics{figures/chapter2/equalintervalhist.png}
\caption{A Histogram of an Example Bin Layout for Equal Interval Discretization.}
\label{fig:equalintervalhist}
\end{center}
\end{figure}

\fig{equalintervalexample} provides an example of how equal interval discretization would create the bins for a simple attribute range that contains
20 numbers.  In this example,the minimum value is 0 and the maximum value is 200 and $n=10$.

\begin{figure}[!ht]
\begin{center}
	\begin{tabular}{|c|c|c|} \hline
		\textbf{Bin Number} & \textbf{Range} & \textbf{Number of} \\
							&				 & \textbf{Items in Bin} \\ \hline \hline
		1 & $[0,20)$ & 2 \\ \hline
		2 & $[20,40)$ & 5 \\ \hline
		3 & $[40,60)$ & 1 \\ \hline
		4 & $[60,80)$ & 1 \\ \hline
		5 & $[80,100)$ & 0 \\ \hline
		6 & $[100,120)$ & 2 \\ \hline
		7 & $[120,140)$ & 1 \\ \hline
		8 & $[140,160)$ & 5 \\ \hline
		9 & $[160,180)$ & 1 \\ \hline
		10& $[180,200]$ & 2 \\ \hline
	\end{tabular}
	$Values = 0~19~24~27~27~30~32~52~65~100~110~123~145~146~149~150~155~170~180~200$
\caption{Example of Equal Interval Discretization.}
\label{fig:equalintervalexample}
\end{center}
\end{figure}

\subsubsection{Equal Frequency}
\label{equalfrequencysect}
Equal frequency discretization is similiar in some ways to equal interval discretization.  First of all equal frequency discretization is an
\textit{unsupervised} process.  Also, at least in the implementations used in this thesis, equal frequency discretization is done as a preprocessor
to the actual learning, and each of the continuous attributes are discretized into the same amount of bins.  Equal Frequency Discretization
is the natural type of internal discretization for the Which machine learner discussed in \chap{which} and is used in experiments in 
\sect{defectexp}, \sect{turkeydata}, \sect{atntdata}, and \sect{micro}.  Unlike equal interval discretization, equal frequency discretization
creates a histogram, seen in \fig{equalfrequencyhist}, that is completely flat.  This is because all of the bins contain the exact same
number of items in them.

The process of equal frequency discretization is a done in two phases.  The first phase requires sorting the values of the attribues in ascending
order.  The second phase is to divide this sorted list into $n$ bins with each bin containing the same \textit{amount} of values.  What this does,
unlike equal interval discretization, is create a flat histogram\cite{discretization1}.  Each of the $n$ bins have the same amount of items in them.
In the case where the number if instances is not divisible by the number of bins, one of the bins, in our implementation this is the last bin, will
have the least number of items in it.  \fig{equalfrequencyexample} is an example of the result of equal frequency discretization on the same
distribution of 20 numbers that were used in \fig{equalintervalexample} on equal interval discretization.

\begin{figure}[!ht]
\begin{center}
	\includegraphics{figures/chapter2/equalfrequencyhist.png}
\caption{A Histogram Example Bin Layout for Equal Frequency Discretization.}
\label{fig:equalfrequencyhist}
\end{center}
\end{figure}

\begin{figure}[!ht]
\begin{center}
	\begin{tabular}{|c|c|c|} \hline
		\textbf{Bin Number} & \textbf{Range} & \textbf{Number of} \\
							&				 & \textbf{Items in Bin} \\ \hline \hline
		1 & $[0,19]$ & 2 \\ \hline
		2 & $[24,27]$ & 2 \\ \hline
		3 & $[27,30]$ & 2 \\ \hline
		4 & $[32,52]$ & 2 \\ \hline
		5 & $[65,100]$ & 2 \\ \hline
		6 & $[110,123]$ & 2 \\ \hline
		7 & $[145,146]$ & 2 \\ \hline
		8 & $[149,150]$ & 2 \\ \hline
		9 & $[155,170]$ & 2 \\ \hline
		10& $[180,200]$ & 2 \\ \hline
	\end{tabular}
	$Values = 0~19~24~27~27~30~32~52~65~100~110~123~145~146~149~150~155~170~180~200$
\caption{Example of Equal Frequency Discretization.}
\label{fig:equalfrequencyexample}
\end{center}
\end{figure}

In the example in \fig{equalfrequencyexample}, the second and third bins both contain the value of $27$.  This is due to the nature of the equal
frequency discretization.  In the example, each bin contains exactly $2$ items, regardless of their value.  The two values of $27$ happen to lie
on a cutoff point in the binning algorithm, so they fall into different bins.  In contrast to the result of the number of items in each bin
varying but the range of each bin being constant in equal interval discretization, the number of items in each bin are constant but the range
of each bin is varying in equal interval discretization.  As will be discussed briefly in \sect{defectdesign}, it is entirely possible for
an attribute to have an exponential distribution.  Using equal frequency discretization on this type of distribtion will result in lower numbered
bins having the same range, or in fact that same values with no range, and the final few bins having a very large range.

\subsubsection{FayyadIrani}
\label{FayyadIrani}
Unlike the previous two discretization methods, FayyadIrani\cite{fayyadirani} is a \textit{supervised} process.  This means that the method of
deciding both the number of bins and the values that go into the bins is determined by some criteria involving the class makeup.  This process
is considerably more complex in terms of how it decides the bins, but is not overly complex in that it drastically alters the time required to
discretize, at least in our experiments in \sect{multiclass}.  The FayyadIrani method of discretization was used in the experiments of
\sect{t3} and \sect{multiclass}.  In these experiments, the implemention of FayyadIrani that was used is part of the wEka\cite{weka} distribution
of data mining tools.  It is under the listing of \textit{weka.filters.supervised.attribute.Discretize}.

FayyadIrani first will sort the data in ascending order based on the continuous attribute to be discretized.  It will then, using an evaluation method
called information entropy, determine the best possible split to create two new bins of the data.  Everything greater than the split becomes the
second bin and everything below the split becomes the first bin.  After doing this, the process will then take only the instances of data contained
in bin one and repeat this information entropy assessment to determine the next reasonable splitting point.  The same process is done on the upper
bin as well.  This process of splitting the bins into smaller bins is continued until one of two critera are met.  The first criteria is that the
bin is \textit{pure}, or that only one value of the class is associated with all instances in the bin.  The second criteria is called the
\textit{minimum description length principle}\cite{discretization2,dougherty95supervised,discretization1} and can be seen in \eq{mindesclenprin}.
This equation illustrates the if the gain from a split is not greater than this number, no new splits are considered.  In \eq{mindesclenprin},
$N$ is the number of instances, $c$ is the number of classes in the current bin, $E$ is entropy of the current bin, $c_1$ and $c_2$ are the number
of classes in the potential resulting bins, and $E_1$ and $E_2$ are the entropies of the potential resulting bins.  The variable called $gain$ in
this equation is elaborated further in \sect{j48} with \eq{gaineqn}.

\begin{center}
\begin{equation}
	gain < \frac{log(N-1)}{N} + \frac{log(3^c-2)-cE+c_1E_1+c_2E_2}{N}
\label{eq:mindesclenprin}
\end{equation}
\end{center}

Since this discretization process is done per attribute and based on the distribution of the $(range,class)$ tuples, it can be easily seen that the
number of bins for each attribute do not necessarily have to be a constant over all of them.  Another interesting idea of this entropy$-$based
discretization is that it is entirely possible for an attribute to only have one bin\cite{djboland}.  Having an attribute in a data file that contains
only one value is completely useless as that attribute tells the learner nothing about the underlying class distribution.  In fact, the wEka maching
learning package\cite{weka}, will not allow a data set to contain attributes to have only one value.  This behavior of FayyadIrani is not to be
considered a con against the discretization policy.  The fact that an attribute was only allowed to have one bin most likely means that the attribute
is too noisy and should not be considered in the overall data set at all.

\subsection{Class Distribution Altering Methods}
\label{overundermicrosampling}
Class distribution altering methods involve the processes of removing instances from or inserting copied instances into the data set.  Like discretization
methods having two classes of these methods, \textit{unsupervised} and \textit{supervised}, these distribution altering methods also have two
classes.  They are \textit{unstructured} and \textit{structured}.  The types of distribution altering methods that are used in the experiments of
\chap{experiments} are structured methods of class distribution altering.  Unstructured methods include randomly copying or removing
instances from the data set with no concept of which instances are actually being copied and reduced.  These methods were not used in this thesis
and further discussion of them is not in the scope of this thesis.  The following consists of three sections that discuss the different types
of structured distribution altering methods.  Only one of these methods was used in our experiments, but we feel that over$-$sampling and
under$-$sampling explainations lead to better understanding of how micro$-$sampling works.
\subsubsection{Over$-$Sampling}
\label{oversampling}
Over$-$sampling is the process of selecting a class from a data set and increasing its distribution in that set up to a desired percentage.  This
is done by randomly copying instances of the class in the data set multiple times until the desired distribution is met.  In essence, this
process is meant to make a rare class more common by artificially adding copies of instances of that class into the data set.  This results in larger
data sets and in the case where the desired class to be over sampled is very rare, these data sets can become very large and unmanageable.
\tab{overexample} is an example of the size increase of the data file being dependant on the original distribution.  In the first example, weather,
only 4 instances needed to be added to aquire the desired final distribtion of 50\%.  However, in the second example, pc1, 769 examples needed to be
added to aquire the same desired final distribution.  It can easily be inferred that if the distribution is even smaller and the original instance
count is high, an even larger explosion in the size of the data set will occur.  These two examples were taken from data files containing two classes
for ease of computation.  This explosion is even greater if there are more than two classes in the data file.
\begin{table}[!ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
	\textbf{File Name} & \textbf{Class} & \textbf{Original Distribution} & \textbf{Original Instances} & \textbf{Final Instances} \\ \hline \hline
	Weather & no & 35.7\% & 14 & 18 \\ \hline
	pc1 & true & 6.94\% & 1109 & 1878\\ \hline
\end{tabular}
\caption{Example Size Increases Due to Over$-$Sampling with Distribution Set to 50\%.}
\label{tb:overexample}
\end{center}
\end{table}

\cite{subsampling} performs several tests using C4.5\cite{c45}, which is the C implementation for which j48, a Java implementation, is based on, with
over and under$-$sampling.  These tests show that over$-$sampling can actually hurt the performance of a machine learner.  This is most likely caused
by the fact that over$-$sampling creates exact copies of instances already in the data set and most machine learners use some measure of support, or
how many instances are covered by this decision, as an evaluation criteria.
\subsubsection{Under$-$Sampling}
\label{undersampling}
Under$-$sampling is the opposite process of over$-$sampling.  That is instead of copying instances of the desired class to better enhance its distribution
in the data set, under$-$sampling removes instances of the other classes at random to acheive the same effect.  As stated, this has the same desired
effect as over$-$sampling, but achieves it by actually removing available information that the learner could have used.  As a result of this removal
process, the data files are smaller.

In the same paper by Chris Drummond and Robert Holte\cite{subsampling}, their results conclude that under$-$sampling does not significantly lower
or raise the performance of C4.5.  Initially, this result may seem to mean that under$-$sampling has no use in the field, however, considering that
under$-$sampling actually makes the data file to be used smaller, this process can have uses in areas where the learning application's running time
is dependant on the size of the data set in some significant way.
\subsubsection{Micro$-$Sampling}
\label{microsampling}
Micro$-$sampling\cite{micro} is a type of data sampling policy that is related to the sampling policy of under$-$sampling\cite{subsampling}.  There is one
key difference in micro$-$sampling, and that is the removal of the desired class as well.  The idea behind micro$-$sampling is to always create
an even $50-50$ spread amongst the classes.  As a note, the micro$-$sampling process is only meant to be used on two classes data sets.  This is
because micro$-$sampling was meant to be a method of boosting performance of the classic machine learners in the field of software defect detection.
Software defect detection is discussed heavily in \sect{previousexp}.

Micro$-$sampling's approach to altering the class distribution is to make the data set a fixed size, as well as a fixed distribution.  For instance, 
in the weather data example given in \fig{examplearff}, a micro$-$sampling of $2$ would end with a data file that contained only 4 instances.  In
\cite{micro}, they used micro$-$sampling sizes of $size>=25$ for their experiments and concluded that the micro$-$sampled data sets performed
just as well as the data sets that were left alone.  The method that micro$-$sampling uses is to simply take $n$ instances of the desired class
as well as $n$ instances of the other class, and create a new data set that only contains $2n$ instances.  Experiments with micro$-$sampling can
be seen \chap{experiments}.
\section{Machine Learners}
\label{classical}
\subsection{j48}
\label{j48}
J48 is a decision tree learner that is a Java implementation of Quinlan's C4.5\cite{c45}.  Decision tree learners work by the divide$-$and$-$conquer
method.  That is, they attempt to split up the data into smaller, more managable parts.  Decision trees do this by singling out candidate attributes
to split on.  In other words, a decision tree learner starts out by determining which attribute is best suited to work as the root of the tree.  Once
this is done, the data is divided into $n$ portions where $n$ is the number of values this attribute can have.  In the case of a continuous attribute,
some form of discretization or other decision process must be made to determine the splits.  In j48, this discretization is handled by creating
a binary chop, I.E. finding some division that makes it a good split.  If an attribute needs to be further divided, this is handled at a lower
level in the tree.  Once this splitting has happened, this decision of calculating the best splitting attribute is decided again on the subset
of data.  \fig{j48tree} gives an example of running the j48 algorithm on the ARFF file illustrated in \fig{examplearff}.  It can be seen here
that the initial split was determined to be outlook, so one node is created for each possible value of outlook: sunny, overcast, and rainy.  So the
subsets of data that are passed to each node are the ones that contain only the specified values of outlook.  There are three main processes that
all decision tree learners implement in order to build their finished tress.  This processes are grow, stop, and prune.  J48 is found in the
wEka\cite{weka} under \textit{weka.classifiers.trees.J48}.

\begin{figure}[!ht]
\begin{center}
	\resizebox{100mm}{!}{\includegraphics{figures/chapter2/j48treeweather.png}}
\caption{Example J48 Decision Tree Using Data from \fig{examplearff}.}
\label{fig:j48tree}
\end{center}
\end{figure}

\subsubsection{Grow}
\label{j48grow}
The method of determining a split in J48 is called \textit{information gain}.  The attribute that, when selected for a split, gives the best
information gain is the one that will split.  If this is the first split, this attribute will be the root of the tree.  It can be seen in
\fig{j48tree} that outlook  was the attribute that has the highest information gain.  Information gain is calculated by using a formula
to determine the number of bits required to encode the class distribution of subset.  This calculation is called \textit{entropy}.
\eq{entropyeqn} illustrates the equation for entropy.  If an attribute$-$value$-$class couple does not appear, the fraction in the $log_2$ will
be zero.  Since this is undefined, we say that if an attribute$-$value$-$class couple does not appear, its entropy is zero.

\begin{center}
\begin{eqnarray}
	\nonumber entropy(x_1, x_2, ..., x_n) = -x_1log_2(x_1) + -x_2log_2(x_2) + ... + -x_nlog_2(x_n) \\
	=> entropy(x_1, x_2, ..., x_n) = -\sum_{i=1}^n x_ilog_2(x_i)
\label{eq:entropyeqn}
\end{eqnarray}
\end{center}

\begin{center}
\begin{equation}
	info([x_1, x_2, ..., x_n]) = entropy\left(\frac{x_1}{\sum_{i=1}^n x_i}, \frac{x_2}{\sum_{i=1}^n x_i}, ..., \frac{x_n}{\sum_{i=1}^n x_i}\right)
\label{eq:infogaineqn}
\end{equation}
\end{center}

\begin{center}
\begin{equation}
	gain = info(current) - info(proposed)
\label{eq:gaineqn}
\end{equation}
\end{center}

Using the example in \fig{examplearff}, we can see that this data set consists of $14$ insances with $5$ of them being no and $9$ being yes.
Using \eq{entropyeqn} and \eq{infogaineqn}, we can calculate the number of bits required to encode the natural class distribtion.
\begin{center}
$info([5,9]) = entropy\left(\frac{5}{14},\frac{9}{14}\right) = \frac{5}{14}log_2(\frac{5}{14}) - \frac{9}{14}log_2(\frac{9}{14}) \approx 0.950683515~bits$
\end{center}

The entropy defined in \eq{entropyeqn} defines the entropy for an attribute$-$value pair.  In order to calculate the overall attribute entropy, 
a different equation is used.  Each attribute can be broken up into $n$ subsets where $n$ is the number of possible attributes this value can have.
If we consider the idea that the entropy of \eq{entropyeqn} is the entropy of that one subset, $S_i$, then we can calculate the entropy of the entire
attribute via \eq{attentropyeqn}.  This is a weighted sum where each component of the summation is the fraction of the entire set, $S$ this subset
contains multiplied by the number of bits required to encode this subset.

\begin{center}
\begin{equation}
	E(attribute) = \sum_{i=1}^n \frac{|S_i|}{|S|}entropy(S_i)
\label{eq:attentropyeqn}
\end{equation}
\end{center}

The following is an example calculation using the outlook attribute taken from \fig{examplearff}.  The outlook attribute contains $3$ values, these
are sunny, overcast, and rainy.  It can been seen from the example that sunny appears with $3$ no instances and $2$ yes instances, overcast
appears with $4$ yes instances and no no instances, and rainy appears with $2$ no instances and $3$ yes instances.  Combining all of these and
using \eq{attentropyeqn}, it can be shown that encoding outlook requires approximately $0.624182525$~bits.

\begin{center}
\begin{tabular}{l}
	$E(outlook) = E([3,2],[0,4],[2,3])$ \\
	$entropy([3,2]) = -\frac{3}{5}log_2\frac{3}{5} - \frac{2}{5}log_2\frac{2}{5} \approx 0.970950594~bits$ \\
	$entropy([0,4]) = -\frac{0}{4}log_2\frac{0}{4} - \frac{4}{4}log_2\frac{4}{4} \approx 0~bits$ \\
	$entropy([2,3]) = -\frac{2}{5}log_2\frac{2}{5} - \frac{3}{5}log_2\frac{3}{5} \approx 0.970950594~bits$ \\
	$=> \frac{5}{14}*0.970950594~bits + \frac{4}{14}*0~bits + \frac{5}{14}*0.970950594~bits \approx 0.624182525~bits$
\end{tabular}
\end{center}

J48 does this process for each of the attributes and then uses \eq{gaineqn} to calculate the information gain that would be gained by using this
attribute for the next split.  In the case of outlook, the example solution below demonstrates the information gain of choosing it.
\begin{center}
	$gain = entropy(whole) - entropy(outlook) = 0.950683515~bits - 0.624182525~bits = 0.32650099~bits$
\end{center}

\subsubsection{Stop}
\label{j48stop}
This process is continued for each of the subsets that result at each splitting point until a stopping condition is met.  J48 uses two different
stopping conditions.  The first of these stopping conditions is met if the current node is pure.  This means that the number of bits required
to encode the subset of data this node is meant to split on is zero.  In other words, only once class exists in this subset.  The second stopping
condition is met when the support for any more splits is too low.  This is an over$-$fitting avoidance measure that means if the current subset
has too few instances in it, no more splitting will occur.  In the event that the first stopping condition is met, the class that is contained
in the subset is reported. as a classification if that node is reached.  In the event the second stopping condition is met, the majority class
contained in the subset is reported as the classification if that node is reached.

\subsubsection{Prune}
\label{j48prune}
Pruning is a method that is meant to avoid over$-$fitting as well as make the decision trees smaller.  This process consists of randomly removing
leaves, thus making that leaf's parent the new leaf and testing the overall error increase that is incurred from that removal.  If the removal
of a leaf increases the overall error of the tree by something less than a specified amount, the leaf is permanently removed.  This process is
recursed for all leaves of the tree and continues until the overall error of the removals becomes too great.

\subsection{Ripper}
\label{ripper}
Ripper, or Repeated incremental pruning to produce error reduction, is a rule based learner.  It was originally proposed by William Cohen\cite{ripper}
for two reasons.  Firstly, in his proposal he makes the claim that rule based learners did not scale well with increases in sample size as well
as with data sets that contained a lot of noisy data\cite{ripper2}.  A rule based learner typically produces a set of rules in the form of
$x_i=a \wedge x_2=b \wedge ... \wedge x_n=z \rightarrow C$ where $x_1$ through $x_n$ are attributes and $a$ through $z$ are the values
that the attributes have.  $C$ in the rule is the class that rule classifies.  An instance of data is considered to be class $C$ if it matches
all clauses in the rule.  A rule learner will typically create more than one rule to attempt to best classify the data.  A very simple 
\textit{straw$-$man} rule learner is zeroR.  ZeroR will only produce one rule, that rule is simply report the majority class in the data set.
An extension to zeroR is oneR. OneR works similiary to zeroR but instead of simply reporting the majority class, it will select an attribute
that has the best prediction rate and report a class for each one of the that attribute's possible values.  As was stated about zeroR, oneR
is also meant to be a \textit{straw$-$man}.  OneR would only perform well if the attribute that it picked was very highly correlated to the
class attribute.

Rule based learning is different from the decision tree learning described in \sect{j48} in a few ways.  Firstly as was discussed in the
decision tree learning section, decision tree learning works on a divide$-$and$-$conquer method.  This involves splitting up the data and
individually processing those halves recursively until a final tree is created.  The method most rule learners, Ripper included, use is called
seperate$-$and$-$conquer.  This is different than the other method because it involves creating a rule that \textit{covers} specific instances
in the data set and then removing those covered instances from that set and repeating the process until some stopping condition is met or there
are no more instances to process.  It is because of this method that rule learners are sometimes refered to as covering algorithms.  Another
difference between rule learning and decision tree learner is that in decision tree learning it is only possible to traverse down one possible
path in the tree, that is each split must be unambiguous.  In rule learning it is entirely possible for rules to overlap and what class the
instance is classified is up to the implementation, some learners will report one of them at random whereas others will report all rules
that are fired.

The implementation of Ripper that is used in this thesis is called jRip and is a Java implementation of the Ripper machine learner that is found
in the wEka\cite{weka}.  Ripper can be found in the wEka under \textit{weka.classifiers.rules.JRip}.  Also, zeroR and oneR can be found in the
wEka under \textit{weka.classifiers.rules.ZeroR} and \textit{weka.classifiers.rules.OneR} respectively.

Ripper uses a unique process of creating and testing rules in order to come up with the final rule list.  It can be subdivided into two distinct parts
the IREP* algorithm, which is used to grow and create rule sets, and the RIPPER$_k$ algorithm, which creates competing rules and is meant to
optimize the error rate of the rules generated by IREP*.

\subsubsection{IREP*}
\label{ripperirep}
IREP* is the final procedure that Cohen came up with in his initial proposal of the Ripper algorithm\cite{ripper}, IREP.  IREP, or incremental
reduced error pruning, was developed by F\"{u}rnkranz and Widmer\cite{irep}.  IREP is a seperate$-$and$-$conquer rule learning algorithm
that takes the training set that is given to it and divides it into two sets, the \textit{growing$-$set} and the \textit{pruning$-$set}.
In Cohen's Ripper implementation, the growing$-$set $\frac{2}{3}$ of the instances and the pruning$-$set gets $\frac{1}{3}$ of the instances.
IREP will work in seperate$-$and$-$conquer by greedily growing a rule set using the growing$-$set and then removing conditions from the
rule that maximize the function given \eq{irepmaxeqn}\cite{ripper}. In \eq{irepmaxeqn}, P and N are the total number of positive and negative
examples in the pruning$-$set respectively and PrunePos and PruneNeg are the number of positive and negative examples in the pruning$-$set 
covered by the rule respectively.

\begin{center}
\begin{equation}
	v\left(Rule,PrunePos,PruneNeg\right) = \frac{P+\left(N-n\right)}{P+N}
\label{eq:irepmaxeqn}
\end{equation}
\end{center}

IREP* is an improvement to this process in two major ways, changing \eq{irepmaxeqn} to \eq{irepsmaxeqn} and adding a stopping condition
to the greedy growing phase of IREP.  The reasons for changing the function to maximize is because the original would tend to pick
rules that covered a lot of one class, even though a large amount of the other class was also covered.

\begin{center}
\begin{equation}
	v\left(Rule,PrunePos,PruneNeg\right) = \frac{p-n}{p+n}
\label{eq:irepsmaxeqn}
\end{equation}
\end{center}

The current stopping of IREP was to stop if a rule generated had an error rate of higher than $50\%$, it would stop creating rules.  This is a problem
because if a rule is created that has low coverage, the variance of the error is very large and it is quite likely that it can have an error
rate exceding the maximum.  Cohen decided to create a new stopping condition that involves the entire current rule set instead of just the rule
currently being created. After each rule is created, a \textit{description length} of the rule set and the covered examples is computed.  IREP* will
stop adding rules with this description length is $d$ bits larger than the smallest overall description length. Cohen's implementation of IREP*
uses $d=64~bits$\cite{ripper}.

\subsubsection{RIPPER$_k$}
\label{ripperripperk}
RIPPER$_k$ is a process that works in concert with IREP* to create optimized rules\cite{ripper}.  RIPPER$_k$ will take as input the rule set
generated by IREP* and create two new rules for each rule in the set.  The first rule RIPPER$_k$ creates a rule that is formed by growing and pruning
a rule where the rule is pruned in order to minimize the entire rule set, replacing the rule that is currently being inspected by this new rule.
The second rule that is created is formed by greedily adding conditions to the current rule being inspected.  After this is done, for each original
rule in the rule set, it is determined which of the three rules will be in the final set.  This is done by determining which rule induces the best
performance of the overall set.  After this process is complete, RIPPER$_k$ generates rules to cover the remaining positive examples in the set.

RIPPER$_k$ has the subscript k because it is an incremental process.  This process of taking the rule set and creating competing rules can
be done multiple times.  The version that the results in \cite{ripper} were produced with were RIPPER$_2$.

\subsection{\nbc}
\label{bayes}
\nbc is a classifier that uses a probalistic model to classify its instances.  Unlike the other models described in this chapter, there is no
process of creating trees or rules.  In fact, the \nbc classifier only requires one pass over the entire data set to construct a look$-$up table
of frequencies.  From that point on, \nbc will use that look$-$up table, coupled with a modified Bayesian probability equation to predict which
class an instance of data is.  The \nbc classifier was originally meant to be a \textit{straw$-$man} classifier in that it was supposed to be a
baseline learner to compare other learners against\cite{bayes, bayes2}.  One of the reasons behind this was because the look$-$up table that \nbc 
generates over the data makes no assumptions about any correlations between attributes that exist.  In data sets where the attributes are highly 
correlated, this nuance of the classifier should be seen and performance should be poor.  However, Domingos and Pizzani show that this
performance problem is actually only a problem in a vanishingly small number of cases\cite{bayes}.
The \nbc classifier is implemented in the wEka\cite{weka} under \textit{weka.classifiers.bayes.NaiveBayes}.

\begin{table}[!ht]
\begin{center}
\begin{tabular}{|c|c|}\hline
	\textbf{Attribute} & \textbf{Frequencies} \\ \hline \hline
	Play & $\left(\frac{5}{14},\frac{9}{14}\right)$ \\ \hline
	Outlook & $\left(\frac{3}{5},\frac{2}{5}\right),~\left(\frac{0}{4},\frac{4}{4}\right),~\left(\frac{2}{5},\frac{3}{5}\right)$ \\ \hline
	Temperature & $\left(\frac{2}{4},\frac{2}{4}\right),~\left(\frac{2}{5},\frac{3}{5}\right),~\left(\frac{1}{3},\frac{2}{3}\right)$ \\ \hline
	Humidity & $\left(\frac{4}{7},\frac{3}{7}\right),~\left(\frac{1}{7},\frac{6}{7}\right)$ \\ \hline
	Windy & $\left(\frac{2}{8},\frac{6}{8}\right),~\left(\frac{3}{6},\frac{3}{6}\right)$ \\ \hline
\end{tabular}
\caption{Look$-$up Table Generated by \nbc using the data given from \fig{examplearff}.}
\label{tb:bayeslookup}
\end{center}
\end{table}

Using the data set illustrated in \fig{examplearff}, \nbc will construct a look$-$up table that can be seen in \tab{bayeslookup}.  Each tuple under
the frequencies column in the data stands for $(freqency~of~no,frequency~of~yes)$ and there is one tuple for each attribute$-$value.  It can be
seen here that this frequency look$-$up table approach will not work on continuous values because there would be no real way to compute these
frequencies.  As can be seen from \tab{bayeslookup}, the $outlook=overcast=>play=no$ frequency is zero.  This can create a problem because
if the instance we are trying to classify contains $outlook=overcast$, the probability no will be zero.  To counter this effect, a small
decimal number is added to each of the probabilities.  Exactly what this small number is is discussed later in this section.

\begin{center}
\begin{equation}
	p(H|E) = \frac{p(H)}{p(E)}\prod_i P(E_i|H)
\label{eq:bayeseqn}
\end{equation}
\end{center}

The modified Bayesian probability equation can be seen in \eq{bayeseqn}.  This equation can be put into simpler terms as $next = old * new$.
We can calculate the current instance of data to be classified by using information about the probabilities of each attribute appearing in
instances we have already seen, coupled with the new information we have just gained.

Using the example data set illustrated in \fig{examplearff}, we shall attempt to classify the instance $i=(rainy,cool,high,TRUE)$.  In order to do
this, we must compute the above equation to get the probability the instance is yes and the probability the instance is no.  Comparing these
two probabilities, we can classify this new instance.  Since $p(i|yes) > p(i|no)$, \nbc will classify this new instance as yes.  Note that
$p(i|yes) + p(i|no) < 1$, this is because \eq{bayeseqn} has been simplified to allow for easier computation.  There are transformations that can
be done to aquire the actual probabilities for each of the classes, but they are beyond the scope of this thesis.

\begin{center}
\begin{tabular}{l}
	$p(i|yes)=p(yes)*p(rainy|yes)*p(cool|yes)*p(high|yes)*p(TRUE|yes)$ \\
	$= \frac{9}{14} * \frac{3}{5} * \frac{2}{3} * \frac{6}{7} * \frac{6}{8}$ \\
	$= 0.165$\\
	$p(i|no)=p(no)*p(rainy|no)*p(cool|no)*p(high|no)*p(TRUE|no)$ \\
	$= \frac{5}{14} * \frac{2}{5} * \frac{1}{3} * \frac{1}{7} * \frac{2}{8}$ \\
	$= 0.0017$
\end{tabular}
\end{center}

As was stated earlier, in the data set of \fig{examplearff}, the frequency for $outlook=overcast=>play=no$ is zero.  There a few techniques
for countering this\cite{mestimate1,mestimate2}.  The first is the m$-$estimate, seen in \eq{mestimateeqn}.  In \eq{mestimateeqn}, $I$ is the
total number of training instances in the set, $C$ is the total number of classes in the set $I$, $N(H)$ is the frequency of the hypothesis, 
$H$, within I, and $m$ is a small, non$-$zero constant, often $m=2$.

\begin{center}
\begin{equation}
	P(H) = \frac{N(H)+m}{I+m*C}
\label{eq:mestimateeqn}
\end{equation}
\end{center}

There are three special cases of \eq{mestimateeqn}.  These are:
\begin{itemize}
	\item When it is a high frequency hypothesis in large training sets. $N(H)$ and $I$ are the dominant terms in the \eq{mestimateeqn} and much
	largerthan the other terms.  As such, the equation can be simplified to $P(H)=\frac{N(H)}{I}$.
	
	\item When the frequency of the class is very rare in a very large training set, $N(H)$ is small and $I$ is large.  In this case, 
	the \eq{mestimateeqn} can be simplified to $P(H)=\frac{1}{I}$.  If this were not the case, rare classes would never appear in prediction.
	
	\item When the data set is very small \eq{mestimateeqn} approaches the inverse of the number of classes, or $P(H)=\frac{1}{C}$.  This is very
	useful in situations discribed above where an attribute$-$class combination has not been seen yet.
\end{itemize}

The probabilities calculated using \eq{mestimateeqn} is a very useful lower bound for $P(E_i|H)$.  If some value $v$ is seen $N(f=v|H)$ times in
feature $f$'s observations for hypothesis $H$, then the lower bound can be calulated using \eq{laplaceestimate}.

\begin{center}
\begin{equation}
	P(E_i|H) = \frac{N(f=v|H)+l*P(H)}{N(H)+l}
\label{eq:laplaceestimate}
\end{equation}
\end{center}

Here, $l$ is the \textit{Laplace$-$estimate} and is set to a small constant\cite{mestimate1,mestimate2}.  As with \eq{mestimateeqn}, there are some
special cases of \eq{laplaceestimate}.
\begin{itemize}
	\item When there are many examples of a hypothesis $H$ and a number of observations have been made for a value $v$, $N(H)$ and $N(f=v|H)$
	are large and \eq{laplaceestimate} approaches $\frac{N(f=v|H)}{N(H)}$.
	
	\item When there is very little evidence for a rare hypothesis, $N(f=v|H)$ and $N(H)$ are small, \eq{laplaceestimate} approaches
	$\frac{l*P(H)}{l}$, or that the default observation of an hypothesis is a fraction of the probability of that hypothesis.  This
	estimation is appropriate when very little data is available.
\end{itemize}

\subsection{Random Forests}
\label{randforests}
Random forests are a classifier that uses decision tree classifiers internally.  Random Forests were first proposed by Leo Breiman in 
\cite{randomforestsorig}. The random forest will, when given an instance of data to classify, poll the decision trees in its forest and take the 
majority vote given by the forest as the classfication of the instance.  In order to create this forest of decision trees, each tree is given a 
column$-$pruned subset of the data.  This is, each tree is given a different look at the data in that certain attribute are removed from the data
set before being given to the tree.  This causes the trees to build completely different classification models about the data.  Also, the trees in
the random forest are grown \textit{greedily}, or without the minimum support stopping criteria described in \sect{j48stop} as well as without the
pruning process described \sect{j48prune}.  The idea behind this is that if any tree is too over$-$fit on the data it was given, the resulting
vote of the other trees should be too great for this to effect the overall classification of the instance.  Also, since the random forest is
growing an exponential number of trees, removing the process of pruning altogether would incur a significant speed improvement.
Random forests are implemented in the wEka\cite{weka} under \textit{weka.classifiers.trees.RandomForest}.

The method of selecting which attribute are removed from each file is, as the name of the classifier says, random.  Essentially there are $2^n$
possible combinations of attributes for each data set, where $n$ is the number of attributes in the set.  In our example in \fig{examplearff},
there are 4 attributes, so a total of $2^4=16$ possible trees could be created.  Generally, there is some minimum number of attributes required
for a tree to learn on.  The word used to describe the set of attributes a given tree in the learner is meant to use to grow the tree is called
a \textit{vector}.  A vector is essentially a boolean list that contains only zeros and ones.  An example vector for the data set described in
\fig{examplearff} could be $a=[1~0~1~0]$.  This would mean the tree is only given the attributes of outlook and humidity to learn on, and should
ignore the rest or that the rest are to be removed prior to the tree learning the data set.

Random forests were not used in any of our experiments, however, they were used in an experiment by Lan Guo et al.\cite{randomforest} in the field of defect detection.
\sect{defectmdp}, \sect{turkeydata}, and \sect{atntdata} are all experiments on defect detection, so we felt it was necessary, since their experimental
results are reported in \sect{previousexp}, to briefly discuss the random forest classification model.

\subsection{TAR3}
\label{tar3}
TAR3 is the third machine learner in a line of machine learners that are fundamentally different than the classic learners of j48, Ripper, and \nbc.
First of all, TAR3 is not a classification learner, it is a lift learner.  Lift learning, or treatment learning as it is sometimes called, is a
process of learning that involves creating a rule to \textit{lift} the overall value of a data set up.  A lift learner typically will
output several rules that are not meant to be used like the rule$-$sets described in \sect{ripper}.  Instead of being taken as a collection
of rules meant to classify an instance of data, lift rules are a collection of rules that are meant to isolate one specific class of data.  The
TAR3 learner will report several rules that are isolated form each other.  They all are meant to be able to classify one specific class, but that
class is the same class.  In instances where a data set only consists of two classes, like \fig{examplearff}, treatments can act as classifiers
by simply adding an else clause.  For instance, if a treatment for the data of \fig{examplearff} was $outlook=sunny$, then we could create the rule
set $outlook=sunny \rightarrow yes, else \rightarrow no$.  This idea only works for two class data sets however, and further discussion on
using treatment learning for in two class systems can be seen in \chap{experiments}.

To better explain, we will use the data set illustrated with \fig{examplearff}.  There are two classes values in this data set, yes and no.  Let us
suppose that we want to know what attributes best predict what days we will play.  It is entirely possible to take the output of a decision
tree learner and parse the branches that end in play to come up with what attributes best predict play, but this process on large trees would be
very cumbersome.  Lift learning is meant to isolate those attributes that best predict one class, or higher valued classes.  What TAR3 does is
rank these class values from worst to best.  It does this by assigning a number to each class value. In our above example, no would be given the
value $2^1=2$ and yes would be given the value $2^2=4$.  This creates a seperation of the classes.  The method of calculating the value of a class
value is illustrated with \eq{lifteqn}. In this equation, $n$ is the number of classes, in ranked order, in the data set,  $f(i)$ is the number of
times that class appears, or the frequency of that class, ${S_R}_x$ is the subset this treatement rule covers, and $lift_{all}$ is the lift of the
normal data set. What lift learners then attempt to do is create rules that maximize the overall value
of the data set.  In \fig{examplearff}, the overall value of the unlifted data set is $\frac{5*2^1+9*2^2}{14} \approx 3.286$.  If we were to
create the treatment $outlook=overcast$ would we have a new data set to compute the lift of, by removing the subset that is covered by this
treatment.  This new data set has a lift of $\frac{4*2^4}{4*3.286} \approx 1.217$.  This number must be greater than one for it
to be an acceptable rule.  This is because if it is less than one than it actually produces a new subset that contains less of the best class
values than the original.

\begin{center}
\begin{equation}
	{lift_R}_x = \frac{\sum_{i=1}^n f(i)*2^i}{|{S_R}_x|*lift_{all}}
\label{eq:lifteqn}
\end{equation}
\end{center}

TAR3 has several parameters that can be changed alter the behavior of the learner.  This parameters will be used throughout the description
of TAR3 and can be found in \tab{tar3param}.

\begin{table}[!ht]
\begin{center}
\begin{tabular}{|r|l|} \hline
	\textbf{Parameter} & \textbf{Description} \\ \hline \hline
	granularity & Number of bins used for equal frequency discretizations. \\ \hline
	maxNumber & Number of treatments to keep at each iteration. \\ \hline
	maxSize & Largest number of attribute$-$value pairs a treatment can have. \\ \hline
	randomTrails & Number of iterations of treatment building. \\ \hline
	futileTrails & Number of iterations allowed to happen without new treatments \\
				 & being created. \\ \hline
	bestClass & Support measurement.  Treatment must select this percentage of \\
	          & the best class to be acceptable. \\ \hline
\end{tabular}
\caption{Configurable Parameters for TAR3.}
\label{tb:tar3param}
\end{center}
\end{table}

TAR3 will attempt to build treatments almost entirely at random.  It will first generate a number $N$ from one to maxSize.  This is the number
of conjunctions this treatment $R_x$ is going to have.  The method of selecting the attributes to be used in $R_x$ is done by scoring
each attribute$-$value pair in isolation.  Essentially, TAR3 computes the \textit{lift} of each attribute$-$value pair.  It then randomly
selects one of these pairs as the first conjunction, weighting the chances to pick a high$-$scoring pair.  It randomly selects
the $N$ conjunctions before testing the treatment.  After all $N$ pairs have been picked the rule's lift is gotten via \eq{lifteqn}.
Rules that have a lift less than one are promptly forgotten.  This process of creating rules is done randomTrails number of times.  After a 
randomTrails number of treatments are created, maxNumber of the best treatments are selected and the process is repeated.  This process is repeated
indefinitely or until futileTrails number of trails occur in a row where no new treatment is generated.

\section{Isometric Space Evaluation of Performance Heuristics}
\label{rocnrule}
F\"{u}rnkranz et al. proposed a novel method of comparing the evaluation heuristics in machine learners in \cite{rocnrule}.  In order to
understand their method of comparison, a few evaluation properties must first be understood.

\subsection{Probabilities of Detection and False Alarm}
\label{pdpf}
Probability of Detection, or PD, and Probability of False Alarm, or PF, are two statistics that are commonly taken about the performance of
detectors created by machine learners.  Both of these methods are meant for the two class case, but can be extended to multiple classes fairly
easily.  The PD of a detector is the probability that a detector will correctly detect a member of the positive class.  \eq{pdeqn} is the
equation that is used to calculate PD.  $p$ in this equation is the number of positive classes that were detected by a detector and $P$ is
the total number of positive classes in the data set.  The PF of a detector is the probability that a detector will misclassify an instance
of the negative class as an instance of the positive class.  \eq{pfeqn} is the equation used to calculate PF.  $n$ in this equaition is
the number of negative examples classified as positive by the detector and $N$ is the total number of negative examples in the data set.

\begin{center}
\begin{eqnarray}
	PD = \frac{p}{P} \\
	\label{eq:pdeqn}
	PD = \frac{n}{N}
	\label{eq:pfeqn}
\end{eqnarray}
\end{center}

The most common represention of a learner's performance is the \textit{confusion matrix}.  A confusion matrix is a table of classes that
represents how the class values in the data set were classified by the detector. \fig{conmat} represents a confusion matrix of five classes, 
A, B, C, D, and E.  The diagonal from $(A,A)$ to $(E,E)$ represents to number of times the detector classified the class correctly.  PD and PF
cannot be calculated directly from this matrix.  As was stated, PD and PF can only be calculated for a two class data set.  In order to do this
the confusion matrix must be transformed to one that consists of $+$ and $-$ classes.  The $+$ class consists of all of the positive instances
of a chosen class.  The $-$ class consists of all other instances in the data set.

\begin{figure}[!ht]
\begin{center}
	\begin{tabular}{|c|c|c|c|c|c|} \hline
		  & A & B & C & D & E \\ \hline
		A & 9 & 1 & 0 & 2 & 2 \\ \hline
		B & 4 & 8 & 2 & 3 & 1 \\ \hline
		C & 2 & 0 & 9 & 0 & 0 \\ \hline
		D & 0 & 0 & 0 & 9 & 6 \\ \hline
		E & 0 & 1 & 2 & 3 & 5 \\ \hline
	\end{tabular}
\caption{Example Confusion Matrix}
\label{fig:conmat}
\end{center}
\end{figure}

As an example, let us choose $+ = A$ and construct a confusion matrix from this that we can calculate the PD and PF for A from. \fig{aconmat}
represents this constructed confusion matrix for just A as the $+$ class.  Adding together the rows first row will result in the total number
of positive class in the data set, or $P$ in \eq{pdeqn}, adding together the second row will result in the total number of the negative class
in the data set, or $N$ in \eq{pfeqn}. $p$ and $n$ can be retrieved by taking the square marked $(+,+)=p$ and $(-,+4)=n$.  We can see from this
example that $pd = \frac{9}{15} = 0.6$ and $pf = \frac{4}{47} = 0.09$.  It can be seen from this example that PD and PF are not complementary of 
each other.

\begin{figure}[!ht]
\begin{center}
	\begin{tabular}{|c|c|c|} \hline
		    & $+$ & $-$ \\ \hline
		$+$ &  9  &   4 \\ \hline
		$-$ &  6  &  47 \\ \hline
	\end{tabular}
\caption{Confusion Matrix for A from Confusion Matrix in \fig{conmat}.}
\label{fig:aconmat}
\end{center}
\end{figure}

These values of PD and PF can be calculated for each class in the confusion matrix to get the overall performance of the detector.

\subsection{Receiver Operating Characteristic Curves}
\label{roccurves}
Receiver operating characteristic, or ROC, curves, are a method of visualizing the probability of detection and probability of false alarm.
A ROC curve is a two dimensional plot with a domain of $(0,1)$ and a range of $(0,1)$.  A ROC curve has several interesting areas about it that
are illustrated with \fig{rocfig}.

\begin{figure}[!ht]
\begin{center}
	\resizebox{100mm}{!}{\includegraphics{figures/chapter2/roccurve.png}}
\caption{Illustration of Different Areas of the ROC Curve.}
\label{fig:rocfig}
\end{center}
\end{figure}

There are several interesting properties of these curves.  The ideal place for a detector to be is at the point $(0,1)$, this means that
the detector has a $100\%$ detection rate and a $0\%$ probability of false alarm rate.  In practice, this type of performance cannot be met, so
different sacrifices can be made to better accommodate the task.  The area marked as \textit{risk adverse} in \fig{rocfig} explains an area
of the curve that has a very high PD but also a very high PF.  This could be equated to a mission critical situation.  Airport security is
a good example of detectors that need to be in the risk adverse region.  An airport employee may check thousands of people a day and generally
none of them are of any threat, however, letting the threats through security for the convenience of the non$-$threatening passengers is not an
option.  The opposite end of the spectrum is the cost$-$adverse region.  An example of this might be the filling of cereal boxes in a factory.
The amount of money saved from not checking the weights of every box far outweighs the several under and overweight boxes that slip through
the system.  The diagonal line in \fig{rocfig} represents the line of no information.  A detector that falls on this line has no better
performance than randomly guessing at every instance.  The prefered curve is a curve that is above the line and the prefered position on that
curve is the one closest to the optimum point.

\subsection{Isometric Space}
\label{isospace}
Isometric Space was developed by F\"{u}rnkranz et al. as a visual means to compare the performance heuristics of machine learners\cite{rocnrule}.
A detailed explanation of ROC spaces and Isometric spaces can be found at \cite{rocnrule2}.

Isometric space is similar to the ROC space that was described in \sect{roccurves} in that it takes into account number of positve and
negative examples found in the data set.  Unlike ROC space, isometric space is not normalized, that is the domain is the number of 
negative examples in the data set and the range is the number of positive examples in the data set.  Also, unlike ROC curves, isometric curves
do not illustrate the performance of a detector, instead they illustrate where a detector would be in this space.  That is, each point in
isometric space represents a detector generated by a machine learner and each curve in isometric space represents a connection between all
detectors that a learner would give the same score. \eq{j48eqn} through \eq{baleqn} give different scoring heuristics for several different
machine learners.  By visualizing these in isometric space it is easy to see how different heuristics behave as the probability of detection
and probability of false alarm change. \fig{isofigs} illustrates some of these heuristics.

\begin{center}
\begin{eqnarray}
	H_{j48} = -log_2\left(\frac{p}{p+n}\right) \\
	\label{eq:j48eqn}
	H_{precision} = \frac{p}{p+n} \\
	\label{eq:preqn}
	H_{ripper} = \frac{p-n}{p+n} = 2 * H_{precision} - 1 \\ 
	\label{eq:ripeqn}
	H_{balance} = \frac{\sqrt{pd^2*\alpha + (1-pf)^2*\beta}}{\alpha + \beta}
	\label{eq:baleqn}
\end{eqnarray}
\end{center}

\begin{figure}[!ht]
\begin{center}
\begin{tabular}{cc}
	\resizebox{60mm}{!}{\includegraphics{figures/chapter2/isoprecision.png}} &
	\resizebox{60mm}{!}{\includegraphics{figures/chapter2/isoj48.png}} \\
	\resizebox{60mm}{!}{\includegraphics{figures/chapter2/isobalance.png}} &
\end{tabular}
\caption{Isometrics of Precision, J48, and Balance.}
\label{fig:isofigs}
\end{center}
\end{figure}

\section{Cross Validation}
\label{xval}
The experiments of \sect{t3}, \sect{multiclass}, \sect{defectmdp}, \sect{turkeydata}, and \sect{micro} all use the ARFF file described in
\sect{arffformat}.  The files were taken from two different repositories, UCI\cite{uci} and PROMISE\cite{promise}.  There is a problem in
testing the perfomance of a machine learner on files in this form.  If the file were to be left alone and used as both the train and the
test set for performance, an over$-$estimation of the performance would exist because the learners are given the unreal advantage of using
the same information they will be tested on to learn their detection sets.  In order to prevent this from happening in our tests, we
use a method of dividing the data up into a set of train data and a set of test data called cross validation\cite{c45}.

Cross Validation is a method of testing a machine learner when only one, flat data set exists \cite{c45}.  The purpose of cross validation is to
allow a learner to be tested on data it has not trained on when two distinct sets do not exists.  Cross validation is a purely test based approach
to evaluating machine learners.  Cross Validation is a two step process that allows for a strong evaluation of a learner.

Cross Validation has an inner and an outter phase that each consist of a variable number of steps.  The inner phase involves breaking up the 
data set into two sets that are completely disjoint.  A typical approach to this is to put 90\% of the data into the \textit{train} set and 
the remaining 10\% in the \textit{test} set.  This process is repeated 10 times so once it is complete there will be 10 train and 10 test 
sets where each test set has completely unique data instances. This number 10 is typically refered to as $N$.  The outter phase randomizes
the data a set number of times, usually 10, and repeats the inner phase for each randomization.  This outter phase count is typically refered to
$M$.  The reason for randomizing the data every pass is to remove the potential for there to be patterns in the data file itself.
Overall, this method runs the learner $MxN$ times.  This large number of runs allows different evaluation methods to determine how well the learner
works overall.

For the purposes of the MDP and Turkey data sets refered to in \sect{defectmdp} and \sect{turkeydata} respectively, a M value of 10 and an
N value of 3 was used.  The reason 3 was used for N was because some of the data files have very few defects in them and breaking up the
data into 10 train$-$test sets causes some test sets to have no defects in them.  This caused erroneous reporting of the probability of 
detection of the learners in some sets.  Using this setup, each learner was ran and tested 30 times for each data file.

\section{Evaluation Processes}
\label{relatedevaluation}
\subsection{Sum of Differences}
\label{sod}
The sum of differences evaluation process is used in \sect{t3} with the experiments that compare the performance of the TAR3 learner to the
performance of the Which learner described in \sect{tar3} and \chap{which} respectively.  It is a simple process of comparing the score
of the detectors generated by each of the learners for each data set they are given.  Essentially, each learner will report one rule with one
score for each instance of the data set after cross validation.  These numbers are compared and the winner gets a point.  In the event where the
learners tie, they are given a tie point.  The tables that are used in \sect{t3} give the results in the form of Which compared to Tar3.  \fig{sodfig}
will be used as a reference for the following example.

\begin{figure}[!ht]
\begin{center}
\begin{tabular}{cccc}
	\textbf{Win} & \textbf{Loss} & \textbf{Tie} & \textbf{Sum} \\
	\hline
	100 & 30 & 100 & 70 \\
\end{tabular}
\caption{Example Row in a Sum of Differences Chart.}
\label{fig:sodfig}
\end{center}
\end{figure}

In \fig{sodfig}, there are four different columns.  These columns refer to: the number of times Which $>$ Tar4, the number of times Which $<$ Tar3,
the number of times Which $=$ Tar3, and $Win-Loss$. If the final column is negative, it means that the Which learner did worse than Tar3 overall.
It is important to note that in the example of \fig{sodfig}, there were a total of $win+loss+tie=100+30+100=230$ total trails and that Which won
$\frac{100}{230} \approx 43.4\%$ of them, lost $\frac{30}{230} \approx 13\%$ of them, and tied $\frac{100}{230} \approx 43.4\%$ of them.  In our
evaluation, we consider any positive number in the final column to be a win, but a large number of ties implies that generally, both learners 
performed the same.

\subsection{Quartile Charts}
\label{quartilecharts}
Quartile Charts have been used in several different experiments as a means of measuring and comparing the performance of different machine
learners\cite{staticlearn,micro}.  The quartile chart is a method of summarizing a large amount of results into a simple graph.  Also, it is
very easy to see standout performance results amongst the different learners being compared.
\begin{figure}[!ht]
\begin{center}
	$0\%$~\boxplot{4}{11}{40}{70}{20}~$100\%$
\caption{Example Quartile Chart.}
\label{fig:egqtc}
\end{center}
\end{figure}

\fig{egqtc} is an example of the quartile charts used to report many of the experimental results in \chap{experiments}.  They consist
of five defining characteristics.  The first is the circle, this stands for the position of the median of the distribution of numbers.
The white space in between the left of the circle the left$-$most horizontal line is the second quartile. The white space
between the right of the circle and the right$-$most line is the third quartile, the left$-$most horizontal line represents the
first quartile, and the right$-$most horizontal line represents the fourth quartile. The vertical line in the middle stands for the $50\%$ mark.
This type of performance method is meant to be used for normalized numbers in the range of $(0,100)$.  The process of determining the
the different quartile$-$ranges is done by sorting the numbers in ascending order and placing the numbers into four groups, each group represents
a different quartile. The quartile chart example of \fig{egqtc} used the following distribution of scores for generation.

\begin{center}
	$(4,7,15)~~(20,30)~~~40~~~(52,64)~~(70,81,90)$
\end{center}

We use quartile charts to report the results in a variety of our experiments.  They are nice because in many of our experiments we have
thousands of resulting scores to compare and a simple table of quartile charts, one for each learner, is able to effectively display the overall
performance of each learner in a very succinct way.  Also, quartile charts make no assumptions about the underlying distribtion of the
results, like t$-$tests do\cite{ttest}.

\subsection{MannWhitney U$-$Tests}
\label{mwutests}
MannWhitney U$-$Tests are non$-$parametric method of ranking different distributions\cite{mwu}.  In many of our experiments, we use the MannWhitney
U$-$Tests in conjunction with the quartile charts of \sect{quartilecharts} to report the results.  U$-$Tests are similar to t$-$tests in that
one can supply a desired confidence level to establish whether one learner performs better than another learner at that confidence level.

The main process that was used in our experiments with the MannWhitney U$-$Test is one of ranking the performance of our learners when
compared to each other.  This process of ranking is done by combining the two distributions to be compared into one distribution and sorting these
distributions in ascending order.  From there, each value is given an integer rank based on its position in the sorted list.  The rank is the
positions.  After this, all values in the distribution that are the same are given a new rank that is the average of all of their ranks.  Then, these
ranks are appplied and the sum of these rankings and their median rank is calculated.  From there, their $U-$statistics are calculated via
\eq{mwuustat}.  In all of the equations in this section, $N_i$ is the number of values in the $i^{th}$ distribution

\begin{center}
\begin{equation}
	U_x = sum_x - N_1(N_1+1)/2
	\label{eq:mwuustat}
\end{equation}
\begin{equation}
	\mu = \frac{N_1N_2}{2}
	\label{eq:mwumean}
\end{equation}
\begin{equation}
	\sigma = \sqrt{\frac{N_1N_2(N_1+N_2+1)}{12}}
	\label{eq:mwustd}
\end{equation}
\begin{equation}	
	Z_x = \frac{(U_x - \mu)}{\sigma}
	\label{eq:mwuzcurve}
\end{equation}
\end{center}

Using the $U-$statistic, a $Z-$curve is calculated via \eq{mwumean}, \eq{mwustd}, and \eq{mwuzcurve}.  At the $95\%$ confidence level, 
$|Z_x| > 1.96$ in order for the two distributions to be considered different.  Using this method of comparing two distributions, $Z_1 = -Z_2$.
\fig{mwuexample} illustrates an example of this process in detail for two distributions, $A$ and $B$.

\begin{figure}[!ht]
	\begin{tabular}{|p{0.95\linewidth}|} 
	\hline
		The distributions and their combinations are: \\
		\[\begin{array}{rcl}
			A & = & 4~6~8~9~40~100 \\
			B & = & 1~3~5~7~9 \\
			A \cap B & = & 1~3~4~5~6~7~8~9~9~40~100 \\
			A \cap B & = & 1~2~3~4~5~6~7~8.5~8.5~10~11\\
			A_{rank} & = & 3~5~7~8.5~10~11 \\
			B_{rank} & = & 1~2~4~6~8.5 \\
		\end{array}\]
		The sum and median statistics are: \\
		\[\begin{array}{rcl}
			sum_A & = & 3+5+7+8.5+10+11 = 44.5 \\
			sum_B & = & 1+2+4+6+8.5 = 21.5 \\
			median_A & = & 7.75 \\
			median_B & = &  4 \\
		\end{array}\]
		The U$-$Statistic can then be calculated: \\
		\[\begin{array}{rcl}
			U_A & = & sum_A - \frac{6*7}{2} = 23.5 \\
			U_B & = & sum_B - \frac{5*6}{2} = 6.5 \\
		\end{array}\]
		Frome these variables, the Z$-$Curve values can be found: \\
		\[\begin{array}{rcl}
			\mu & = & 15 \\
			\sigma & \approx & 5.477 \\
			Z_A & \approx & 1.55 \\
			Z_B & \approx & -1.55 \\
		\end{array}\]
		$($Note that $Z_A = -Z_B$.  This was discussed earlier and will always be the case.$)$  As was stated,
		we compare $abs(Z) > 1.96$.  Since this is false, both $A$ and $B$ get a tie.  In other words, they cannot
		be distinguished from each other.\\
	\hline
	\end{tabular}
\caption{Example of Using MannWhitney U$-$Tests on Two Distributions.}
\label{fig:mwuexample}
\end{figure}

The MannWhitney U$-$Test was designed as a non$-$parametric test that ignores the underlying distribution of the values entirely.  This test also
does not require the distributions be the same size either, which can be seen in \fig{mwuexample}.  This test was also designed to determine
of two distributions were different from each other.  This is not enough for our evaluation purposes because saying the scores of one
learner are different from the scores of the other learner does not tell us which one is better.  In order to do that, Menzies et al. devised
a method of using the MannWhitney results coupled with an additional test afterwards\cite{mwuimprove}.  Once the MannWhitney test has been run, if
the two distributions are the same, both of them get a tie point.  However, if they are not the same a comparison is made between the medians
of the ranks of the two distributions.  For the purposes of our experiments, we are using distributions of scores, the higher the score the better.
For this case, we can say:
\begin{itemize}
	\item If $median_A > median_B$, then $wins_A$ and $losses_B$ get points; else,
	
	\item If $median_A < median_B$, then $wins_B$ and $losses_A$ get points; else,
	
	\item $ties_A$ and $ties_B$ get points.
\end{itemize}


\section{The Pareto Distribution}
\label{pareto}
The Pareto distribution was originally developed by Vilfredo Pareto to describe the distribution of wealth in society\cite{lorenz}.  This
distribution occurs very profoundly when looking at the distribution of faulty modules or files in software projects.  Several
other researchers in the field of defect detection have reported this same type of distribution appearing in the software projects they had
researched on\cite{paretosrc1,paretosrc2,paretosrc3,korusupt1,analysis}.  An example plot of the Pareto distribution is seen in \fig{paretofig}.

\begin{figure}[!ht]
\begin{center}
	\resizebox{100mm}{!}{\includegraphics{figures/chapter2/pareto.png}}
\caption{Example Pareto Distribution.}
\label{fig:paretofig}
\end{center}
\end{figure}

The Pareto distribution has a more common name of the ``$80-20$'' rule, or in terms of the economic portion of society, $80\%$ of the wealth
is controlled by $20\%$ of the population.  Our Koru diagrams of \sect{korudiagram} are specifically layed out the way they are to exploit
this same phenomenon in the software projects that we explore.  We have recognized this distribution occuring in our experiments of
\sect{defectmdp}, \sect{turkeydata} and \sect{atntdata}.  For these sections, we define what we call the \textit{oracle}, the oracle is the plot
of all of the defective modules that exist in the project sorted by their lines of code.  In all of these plots, the oracle follows the same
curve as the Pareto distribution curve in \fig{paretofig}.

\section{Previous Experiments}
\label{previousexp}
Many of our experiments in \chap{experiments} deal with the problem of trying to select which modules or files in a software project are likely
to be defective.  There have been several different approaches in the past to attempt to use the more classic learners to solve this problem
\cite{randomforest,staticlearn,blindspot,testless} and also the use of some statistical models instead of classic learners
\cite{ostrand1,ostrand2,detectingfaultprone,javalegacy}.

\subsection{Classic Machine Learners}
\label{prevclassics}
\cite{randomforest} use the random forest machine learner described in \sect{randforests} to predict defects on some of the MDP data sets that
were used in \sect{defectmdp}. Their results were very promising in that the reported scores of $(PD,PF) = (0.87,0.25)$  They also applied the
random forest approach as a method of selecting the most important attributes in these data sets and selected five attributes from each.  Their
results in this area showed that none of the attribtues were equally as important per data set.  For a description of the attributes see
\tab{mdpdatadesctable}.  While their results were promising in terms of PD and PF, the paper did not study the effects of adding in the amount
of code needed to be searched, or \textit{effort}, into their evaluation.  Effort can be defined by \eq{efforteqn}.  In other words, given a
detector, effort is the total lines of code instances that the detector classifies as defective contain over the total number of lines of
code all instances in the set contain.

\begin{center}
\begin{equation}
	effort=\frac{\sum_{i=1}^D LOC_i}{\sum_{j=1}^N LOC_j}
\label{eq:efforteqn}
\end{equation}
\end{center}

\cite{staticlearn} discusses the performance of the classic machine learners of \nbc, j48, and oneR on the MDP data sets discussed in 
\sect{defectmdp}.  \nbc and j48 were discussed in detail \sect{bayes} and \sect{j48} respectively and oneR was discussed breifly \sect{ripper}.
They also compared the learners with each other and with themselves using no preprocessing and a preprocessor that takes the logarithm of the
attributes.  Their conclusions were that \nbc with the preprocessor performed outstandingly better than the other five preprocessor$-$learner
configurations.  They report average performance results of $(PD,PF) = (0.71,0.25)$ for \nbc.  Like the previously discussed experiment, these
performance results to not take into account the amount of code that needs to be searched in their evaluations.

\cite{blindspot,testless} both use a learner called ROCKY to report their results on the MDP data sets described in \sect{defectmdp}.  ROCKY
is a machine learner that has a very simple rule learning policy.  ROCKY will create rules of length one that are tuned for not only the detection
of defective modules but also to minimize the amount of effort these modules use.  Essentially, attempt to detect as many of the fault modules
as possible under some effort constraints. 

\cite{testless} creates a commercial scenario as well as a mission critical scenario and give different results for each.
With a commercial scenario they arrive at $(PD,PF,effort) = (0.37,0.37,0.43)$ and in the mission critical scenario they arrive at 
$(PD,PF,effort) = (1.0,0.75,-)$, where effort is not a factor that matters.  This project was meant to be a comprehensive study of the effects
the different Halstead\cite{halstead} and McCabe\cite{mccabe} attributes have on the performance measures of PD, PF, and effort.

\cite{blindspot} creates an experiment to further the testing of ROCKY on the MDP data to discuss the different performances of ROCKY on sets of
the attributes.  They divide these sets up into three parts.  These are the same divisions that are described \tab{mdpdatadesctable}.  These
are thh Halstead, McCabe, and LinesOf attributes.  These experiments conclude with three different behavioral facts about the relationship of PD, PF
effort, and accuracy. These are that PD rises with effort, but rarely exceeds it, PD and PF rise together and that PD, PF, and effort can vary
significantly while accuracy is uneffected.

\subsection{Statistical Models}
\label{prevstatistics}
\cite{ostrand1,ostrand2} discuss the use of a statistic model called negative binomial regression to provide a sort order to inspect the modules.
They do not explicitly discuss the line of code style effort in their work, but instead use a percentage files to evaluate the performance of their
tool.  While this is not an exact correlation to lines of code, it still gives some estimate of the effort their model requires to produce
the detection rates.  The two experiments of these authors use a the same tool on two different projects and in both projects report finding
$80\%$ of the defects in $20\%$ of the files.  These experiments use the \att data described in \tab{attinfo} to evaluate their model.

\cite{detectingfaultprone} uses a type of linear model called discriminant analysis on static code attributes to order them much in the way
the previous two experiments did.  They report results of being able to classify between $62\%$ and $72\%$ of the modules that they they used this
model on.  This experiment does not take any form of effort into account during the evaluation.

\cite{javalegacy} created statistical models for the use of a Java legacy system.  As a result their model attempting to detect fault prone
Java classes as opposed to the module and file based approaches described previously.  Much like the work in \cite{staticlearn}, the authors saw
that the attribute's distribution was heavily skewed to the right and applied a logarithm transformation to the data before using the model.  They
use a statistical model of logistic regression to achieve similar effects in detecting the fault prone classes.  While they do not give any
explicit numbers for PD, they do give a PF rate of less than $20\%$ and a false negative rate of less than $20\%$.

\section{Summary}
\label{relatedsummary}
\chap{related} has been a broad overview of the different aspects of this very diverse field.  The remaining portion of this thesis will cover
these specific aspects of this field:
\begin{itemize}
	\item The introduction of a stochastic best$-$first rule learner, Which;
	
	\item The performance of Which when compared to the treatment learner, TAR3;
	
	\item The effects of treatment learning when applied to differing train and test sets;
	
	\item The performance of Which in the realm of classification accuracy;
	
	\item A novel form of evaluating the performance of defect detectors, the Koru Diagram;
	
	\item Two manual searching methods of defect data;
	
	\item The effects of treatment learning when applied to heurisitics other than lift;
	
	\item The performance of the classic learners in the realm of defect detection;
	
	\item The performance of the manual methods;
	
	\item The performance of Which in the realm of defect detection; and,
	
	\item Creating external validity for the subsampling process of micro$-$sampling;
\end{itemize}