\dbsp
Today's modern societies are built on information.  Computers and the Internet can make information available quickly to anyone looking for it.  More importantly, computers can process that information more quickly than many humans.  They can also provide information about how best to make a decision that normally would have been made previously by a human being with imperfect knowledge built on their individual education and experience but not necessarily the best information.  Computer can thus aid us in making the right decisions at the right moment using the best information available.  This thesis deals with helping to refine the way computers decide which information is most pertinent and make, or help their human users make, decisions based upon it.   We will discuss methods of automatically extracting patterns from large amounts of data, and methods by which we can improve the ways in which they perform.  Specifically, we will explore a novel \textit{discretization} method for continuous data.  Such discretization is a common preprocessing method that is known to improve various data mining approaches. We will offer a new method based upon the \textit{randomized binary search tree} data structure and compare its performance with existing state of the art discretization methods.

Chapter \ref{introduction} provides background information about this thesis, specifically discussing the motivation behind the research herein, the purpose of this thesis, contributions that this thesis makes to the field of computer science and more specifically the topic area of data mining.  Finally, this chapter explains the layout for the rest of this document. 

Section \ref{motivation} describes the problem that motivated this thesis, specifically discretization and the search for a simple solution that performs at about the same level as existing methods.  

Section \ref{thesis} states the purpose of the research of this thesis.  

Section \ref{contributions} states the contributions of this thesis to related research.  

Section \ref{about} explains the layout of the rest of this document and what can be expected in the following chapters.

\ssp

\section{Motivation}
\label{motivation}
\dbsp

\textit{Data mining} is the process of analyzing data in order to find undiscovered patterns in the data and solve real world problems \cite{fw2}.  It may be data about historic trends in beach erosion to help a local community determine how much sand needs dredged and replaced each year, or survey data about when people begin their Christmas shopping in order to help retailers determine the best time of year to begin setting up Christmas displays and ordering seasonal merchandise.  Data about a set of tests that identify cancer might be analyzed to determine which tests are most capable of identifying the cancer and allow doctors to use these tests earlier in the cancer screening process, or data about fuel purchases or consumption analyzed and used as a basis for vendors to know how much fuel they should have on hand at a particular time of year, how often they should be restocked, and specific amounts of each fuel grade or type might be needed.  Data mining can be used to analyze a vast variety of data in order to solve the problems faced by our society or provide more information to help people make the best decisions. 

Real world data such as that collected for the problems above can provide a variety of issues for data miners, but one of the chief problems involved in preparing data for the learner is ensuring that data can be easily read and manipulated by the learner.  One of the most common difficulties that learners have is dealing with numeric values.  Most learners require data to take on a value belonging to a small, fixed set, which is often unobtainable with raw numeric values that can fall in large or infinite ranges and take on many possible values even when constrained by a range.  The process of transitioning raw numeric values to a form that can be easily read and manipulated by learners is called \textit{discretization} \cite{fw2}.  Numerous researchers report that discretization leads to better, more accurate learning, especially in Na\"{i}ve Bayes Classifiers.  However, they very often disagree about which method of discretization works best.  Because of how useful discretization can be for classification, yet because questions remain about whether there is one best method to use,  discretization will be the subject of this thesis.

\ssp

\section{Statement of Thesis}
\label{thesis}
\dbsp

While data discretization is an important topic in data mining, it is one burdened with a vast variety of methods, most of which take on complex data structures and require a search over the entire data set to determine how a value should be discretized.  We believe that there should be a simpler approach that works similarly to these methods.  To that end, we have implemented a discretization method based on a randomized binary search tree as the underlying storage data structure.  We contend that this method uses the properties of \textit{randomized binary search trees} to avoid a search over the entire data set performing discretization and do so with a simple structure that can be understood by most.

\ssp

\section{Contributions}
\label{contributions}
\dbsp

The contributions of this thesis are:
\begin{itemize}
\item The DiscTree algorithm that is implemented to create the DiscTree discretization method;

\item A review of a variety of currently existing discretization methods; and,

\item An experimental comparison of some common discretization methods against the implemented DiscTree discretization method.  

\end{itemize}
A surprise finding of this comparison is that many discretization methods perform at very similar levels. 

The results of the comparison leads us to the belief that discretization is a simpler task than it is made out to be in some of the literature.  The DiscTree algorithm is simple in comparison to many of the state-of-the-art methods and performs just as well as some methods that claim superiority in the field of discretization.  We believe that while various methods exist for discretization and some may perform better on a specific data sets than others, that in general simple methods perform well and can be just as useful as and used in place of complex methods.

\ssp

\section{About This Document}
\label{about}
\dbsp
The rest of the chapters of this thesis are laid out as follows:

Chapter \ref{background} provides an explanation of the premise of data and how it is used in data mining.  It also provides a review of various learners in data mining. It examines several possible learning methods and explains why we have chosen to use the Na\"{i}ve Bayes Classifier for our experimentation with discretization methods.  

Chapter \ref{discretization} provides a review of common data mining discretization methods.  It highlights the methods commonly found in the literature on discretization and specifically reviews the methods we will compare in our experiment.  

Chapter \ref{experiment} explains the experimental design used to test the variety of data discretization techniques described in Chapter \ref{discretization}.  It also explains our methods for generating and comparing results.  

Chapter \ref{results} contains the results of the experiment, relevant tables and data plots, and a explanation of those results.  

Chapter \ref{conclusion} explains conclusions derived from the results of the experiment.  It discusses the key findings and areas of future work that could expand upon this thesis.  It also provides a summary of this document. 

\ssp
