\documentclass[12pt]{report}
\topmargin=0in
\headheight=0in
\headsep=0in
\oddsidemargin=0in
\evensidemargin=0in
\textwidth=6.5in
\textheight=9in

\usepackage{graphicx}
\usepackage{algorithmic,cite,footmisc,multirow,url}
\usepackage{listings}
\usepackage{color}
\usepackage{pslatex}
\usepackage{fullpage}
\usepackage{float}
%\usepackage{epsfig}
\newcommand{\dbsp}{\linespread{1.5} \rm}
\newcommand{\ssp}{\linespread{1.0} \rm}


%\usepackage{amsmath, amsthm, amssymb}

%Dr. Menzies-style commands
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\hyp}[1]{Hypothesis~\ref{hyp:#1}}

\newcommand{\app}[1]{Appendix~\ref{a:#1}}
\newcommand{\sect}[1]{Section~\ref{#1}}
\newcommand{\chap}[1]{Chapter~\ref{#1}}
\newcommand{\nbc}{Na\"{i}ve Bayes classifiers}
\definecolor{listinggray}{gray}{0.9}

\begin{document}
\thispagestyle{empty}

\title{\large Data Discretization Simplified: \\ Randomized Binary Search Trees for Data Preprocessing}
\author{\normalsize Donald Joseph Boland Jr. \vspace{3.2ex} \\
\normalsize Thesis submitted to the \\
\normalsize College of Engineering and Mineral Resources \\
\normalsize at West Virginia University \\
\normalsize in partial fulfillment of the requirements \\
\normalsize for the degree of \vspace{3.2ex} \\
\normalsize Master of Science \\
\normalsize in \\
\normalsize Computer Science \vspace{3.2ex} \\
\normalsize Tim Menzies, Ph.D, Chair \\
\normalsize Roy S. Nutter, Jr., Ph.D \\
\normalsize Cynthia Tanner, M.S. \vspace{1.4ex} \\
\normalsize Lane Department of Computer Science and Electrical Engineering \vspace{3.2ex} \\
\normalsize Morgantown, West Virginia \\
\normalsize 2007 \vspace{3.2ex} \\
\normalsize Keywords: Data Mining, Discretization, Randomized Binary Search Trees \vspace{1.4ex}\\
\normalsize Copyright \copyright 2007 Donald Joseph Boland Jr.
}

\date{}
\maketitle

\begin{abstract}
\begin{center}
Data Discretization Simplified: \\ Randomized Binary Search Trees for Preprocessing \vspace{1.5ex} \\
Donald Joseph Boland Jr.
\end{center}
Data discretization is a commonly used preprocessing method in data mining.  Several authors have put forth claims that a particular method they have written performs better than other competing methods in this field.  Examining these methods we have found that they rely upon unnecessarily complex data structures and techniques in order to perform their preprocessing. They also typically involve sorting each new record to determine its location in the preceding data.  We describe what we consider to be a simple discretization method based upon a randomized binary search tree that provides the sorting routine as one of the properties of inserting into the data structure.  We then provide an experimental design to compare our simple discretization method against common methods used prior to learning with Na\"{i}ve Bayes Classifiers. We find very little variation between the performance of commonly used methods for discretization.  Our findings lead us to believe that while there is no single best method of discretization for Na\"{i}ve Bayes Classifiers, simple methods perform as well or nearly as well as complex methods and are thus viable methods for future use.
\end{abstract}

\chapter*{Dedication}
\renewcommand{\thepage}{\roman{page}}
\setcounter{page}{3}
\dbsp
\begin{center}
\textit{To My Wife Kelly} \\
\textit{To My Family} \\
\end{center}
\ssp

\chapter*{Acknowledgments}
\dbsp

I would like to first express my truest and sincerest thanks to Dr. Tim Menzies.  Over the past year and a half of working together, he has provided me with the guidance and support necessary to complete this project and grow as a student, researcher, and computer scientist.  He has provided the inspiration to approach problems in computer science with a degree of curiosity which I had not previously experienced and taught me a variety of useful skills that I do not think I would have adopted otherwise, most specifically SWP: Script When Possible, which made completing this thesis bearable and easily changeable and repeatable when new ideas or wrinkles were introduced.  My life is now encapsulated in a Subversion Repository where nothing can be easily lost and many things can travel easily, and I would not have adopted such a lifestyle without having the opportunity to work with Dr. Menzies.  His interest in his student's success, his dedication to research and teaching, and his faith in my abilities have been a great inspiration in allowing me to complete this work.  It has been a great honor and privilege to know and work with him.

I would also like to thank the other members of my committee, Dr. Roy Nutter and Professor Cindy Tanner for their support both in this project and working with me during my tenure at West Virginia University.  Dr. Nutter's vast interests, from computer forensics to electric cars and everything in between has only helped to increase my interest in studying a variety of fields and not just isolating myself in one particular interest or field.  His willingness to serve as an advisor while I searched for an area of interest at West Virginia University allowed me to reach this point. Professor Tanner, my first supervisor as a teaching assistant at West Virginia University, afforded me the opportunity to work with students as an instructor and mentor in her CS 111 labs.  It is an opportunity that has allowed me to get a taste of what being a college instructor could be like and also has afforded me skills like being able to speak comfortably in front of groups, answer questions on the fly, and quickly adopt and understand programming languages well enough to instruct on them.  I greatly appreciate her willingness to work with me and provide me with the latitude to learn these skills.

I would like to thank Lane Department of Computer Science and specifically Dr. John Atkins for expressing an interest in having me attend West Virginia University and for providing a variety of opportunities over the last few years so that I could pursue this graduate education.  I have had the opportunity to study and work with so many great professors only because of the opportunities that were created by the teaching and research assistantships made available by West Virginia University.

I would like to thank my family for their continuing support and encouragement.  Without their interest in my continuing success, their help in keeping me motivated, and their good humor when I my mood needed lightened, I would not have been able to achieve any of the successes involved with completing this document nor been able to stand finishing it.

Last, but far from least, I would like to thank my wife, Kelly.  Her continuing love, patience, and willingness to play our lives by ear, along with the her unending support, made it possible to complete this project while getting married in the middle of it.  I greatly appreciate her support in help me to maintain my sanity and other interests in the process.  I look forward to spending more time with her and less time in front of my computer as this project comes to a close and our life together really begins.

\ssp

\tableofcontents
\listoffigures
%\listoftables
\pagebreak

\chapter{Introduction}
\setcounter{page}{1}
\renewcommand{\thepage}{\arabic{page}}
\label{introduction}
\input{introduction}

\chapter{Background: Data and Learners}
\label{background}
\input{background}

\chapter{Discretization}
\label{discretization}
\input{discretization}

\chapter{Experiment}
\label{experiment}
\input{experiment}

\chapter{Experimental Results}
\label{results}
\input{results}

\chapter{Conclusion}
\label{conclusion}
\input{conclusion}

\appendix

\ssp

\chapter{disctree Source Code}
\label{a:dtsc}
\input{dtsource}

\ssp

\chapter{crossval Source Code}
\label{a:xval}
\input{xvalsource}

\ssp

\chapter{tenbins Source Code}
\label{a:tenbins}
\input{tenbinssource}

\ssp

\chapter{Script for PKID}
\label{a:pkidsource}
\input{pkidsource}

\ssp

\chapter{Entropy-Minimization Method Script}
\label{a:fayyadIranisource}
\input{fayyadIranisource}

\ssp

\chapter{Performance Measure $U$-test Tables}
\label{a:perfmeasuretables}
\input{perfmeasuretables}

\ssp

\bibliography{MS}
\bibliographystyle{plain}

\pagebreak
\thispagestyle{empty}

\end{document}
