%\documentclass[ignorenonframetext,handout]{beamer}
\documentclass{beamer}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{algorithmic,cite,footmisc,multirow,url}
\usepackage{listings}
\usepackage{color}
\usepackage{amsfonts}
%\usepackage{pslatex}
%\usepackage{fullpage}
%\usepackage{float}

\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{\bo}[1]{\textbf{#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}

\newcommand{\dbsp}{\linespread{1.5} \rm}
\newcommand{\ssp}{\linespread{1.0} \rm}

\usetheme{classic}
\setbeamertemplate{footline}[frame number]
\title{Thesis Defense}
\subtitle{Data Discretization Simplified:\\ Randomized Binary Search Trees for Data Preproccessing}
\author{Donald Joseph Boland Jr.}
\date{December 10th, 2007}

\begin{document}

% outline slides (if wanted)
%\AtBeginSection[]
%{
% \begin{frame}
%  \frametitle{Current Section}
%  \begin{center}
%    \small
%    \tableofcontents[currentsection,hideothersubsections]
%    \normalsize
%  \end{center}
% \end{frame}
%}

\dbsp

\frame{\titlepage}

\ssp

\section[Introduction]{Introduction}

\dbsp

\begin{frame}{Sound Bites}
\bi
\item<+-> \bo{Classification} is a Useful Field in Data Mining.
\item<+-> \bo{Discretization} Helps to Minimize Classifier Confusion from Numeric Data and Increase Accuracy.
\item<+-> \bo{DiscTree} is a New Discretization Algorithm Based on a \bo{Randomized Binary Search Tree}.
\item<+-> This Thesis Implements DiscTree and Compares it to Other Frequently Used Discretization Methods.
\item<+-> Results Lead to the Conclusion that There is No Single Best Method In All Cases.
\ei
\end{frame}

\ssp

\section[Classification]{Classification}

\dbsp
\begin{frame}{Glossary}
\bi
\item<+-> \bo{Instance} refers to one occurence in the data
%such as one student, one patient.
\item<+-> \bo{Attribute} refers to one facet of an instance
%such as one test score for a student, one measurement for a patient
\item<+-> \bo{Class} refers to the decision made for the instance
%such as admit student to school or which condition a patient has
\ei
\end{frame}
\begin{frame}{What is Classification?}
\bi 
\item<+-> Start With a Set of Pre-Classified Example Instances
\item<+-> Create a Theory/Concept for How Attributes Relate to Classes
\item<+-> Use/Test Theory on Future, Unforseen Instances
\ei
\end{frame}
\begin{frame}{Useful Classification}
\bi 
\item<+-> Student Data Used to Make Automated Financial Aid/Scholarship/Admissions Decisions
\item<+-> Part Measurements Used to Make Accept/Reject Decision \\ in Automated Manufacturing
\item<+-> Medical Test Data Used to Diagnose Specific Diseases/Conditions
\ei 
\end{frame}
\begin{frame}{Classification Methods}
\bi 
\item <+-> Many Forms of Classification Methods Exist$^*$, Including:
\bi 
\item Decision Tree Learners (J48, C4.5)
%Which Create Trees of Attributes from Which They Make A Decision
\item Rule-Generating Learners (PRISM, RIPPER)
%Which Create Rules and Sets of Rules Used to Make A Decision
\item Instance-Based Learners (Nearest Neighbor, K-Means)
%Which measure distance from nearest neighbors and associate new instances with closest class/group
\ei 
\item<+-> However, for Controlled Experimental Purposes, Only One Classifer Used: Na\"{i}ve Bayes Classifier
\ei 
\begin{flushright}
\tiny $^*$For Further Explanation of Other Methods, see Thesis Document
\end{flushright}
\end{frame}

\ssp

\section[NBCs]{Na\"{i}ve Bayes Classifiers}

\dbsp

\begin{frame}{The Basics}
\bi
\item<+-> Highly Studied Statistical Method of Classification
\item<+-> Originally a \textit{Straw Man} Method
\item<+-> Assumes Independence of Attributes
\item<+-> Easily Handles Missing Attribute Values
\item<+-> Small Memory Footprint (only Keeps Value and Class Frequency Counts)
\item<+-> Makes Decisions Using Bayes' Theorem
\ei
\end{frame}
\begin{frame}{Bayes' Theorem}
\bi 
\item<+-> Simple View: $next = old \times new$
\item<+-> More Formally:
\begin{equation} \label{eq:nb}
\nonumber P(H|E)=\frac{P(H)}{P(E)}\prod_iP(E_i|H)
\end{equation}
Where $H$ is the class/hypothesis being considered and \\ $E$ is the evidence of Current Conditions
\ei 
\end{frame}
\begin{frame}{Bayes' Theorem Explained}
\begin{center}
\footnotesize
\begin{equation} \label{eq:nbsmall}
\nonumber P(H|E)=\frac{P(H)}{P(E)}\prod_iP(E_i|H)
\end{equation}
\normalsize
\end{center}
\bi 
\item<+-> Where $P(H)$ represents the prior probability of the class $H$;
\item<+-> $E_i$ represents the current evidence (attribute value);
\item<+-> $P(E_i|H)$ represents the probability of attribute value $E_I$ occuring with class $H$; and
\item<+-> $P(H|E)$ represents the probability of class $H$ given all the current evidence $E$, and is called the posterior probability.
\ei 
\end{frame}
\begin{frame}{Used for Classification}
\bi
\item<+-> For Each Instance, use its attribute values in the equation
\item<+-> Each Class is Used in the Equation to Calculate its Posterior Probability 
\item<+-> The Class with the Largest Posterior Probability is Selected as the Classification of the Instance
\ei
\end{frame}
\begin{frame}{Why Choose Na\"{i}ve Bayes}
\bi 
\item<+-> Dougherty et. al Found that Each Form of Discretization Tried on \nbc~ Increased Performances
\item<+-> Domingos and Pazzani Found \nbc~ with Discretization Out-Performed Other Methods and that the Attribute Independence Assumption did not Greatly Degrade Perfromance when used with Strongly Related Data
\ei
\end{frame}
\begin{frame}{Why Choose Na\"{i}ve Bayes}
Many of the Most Recent Proposals for new Discretization have Been Proposed for \nbc~; Specifically, Webb puts Forth Many Methods Specifically for the \nbc~.  We Test Against one Called PKID.
\end{frame}

\ssp

\section[Discretization]{Data Discretization}

\dbsp

\begin{frame}{What is Discretization}
\bi 
\item<+-> Data comes in several forms
\bi 
\item \bo{Nominal} or qualitative data
\item \bo{Ordinal} or nonquantitative ranked data
\item \bo{Continuous}, numeric, or quantitative data
\ei
\item<+-> Quantitative Data can Cause Problems for Classifiers
\item<+-> Discretization Converts Numeric Data into Nominal Form\\
\item<+-> More Specifically, Discretization Replaces Numeric Values with Possibly Infite Values 
			 with a Fixed Set of Nominal Values.
\ei
\end{frame}
\begin{frame}{How It Works}
\bi
\item Numeric Values are read, sorted, and placed in "buckets"
\item Buckets or Bins Store to a fixed Range of Continuous Values.
\item Data Values are Replaced by the Name of the Bucket They are Placed In
\ei 
\end{frame}
\begin{frame}{Methods}
While Several Methods of Discretization are Reviewed$^*$, We Experiment With Four:
\bi 
\item<+-> Equal Interval Width Discretization (EWD)
\item<+-> Entropy-Minimization Discretization
\item<+-> Propotional K-Interval Discretization (PKID)
\item<+-> DiscTree
\ei 
We Also Test Provide Results from Undiscretized data using the \textit{cat} command
\begin{flushright}
\tiny $^*$For More Details on Discretization and Specific Methods, see Thesis Document
\end{flushright}
\end{frame}

\ssp

\section[DiscTree]{Discretization from Randomized Binary Search Trees}

\dbsp

\begin{frame}{Randomized Binary Search Trees}
\begin{figure}
\begin{center}
\includegraphics[scale=0.20]{binarysearchtree.png}
\end{center}
\end{figure}
\bi 
\item<+-> Like Binary Search Trees, But INSERT is Randomized
\item<+-> At Root of Each Subtree, New Value Has $\frac{1}{T}$ Chance of Becoming Root, Where T is the Number of Instances at or Below Tested Node
\ei
\end{frame}
\begin{frame}{DiscTree Premise}
\bi 
\item<+-> Discretization Using Randomized Binary Search Trees as Base Data Structure
\item<+-> Tree Nodes Store a Value and Frequency Counts for Classes at and below Node
\item<+-> Nodes with at Least $\sqrt{N}$, where $N$ is the Number of Training Instances, at or below them can be substituted for continuous values.
\ei 
\end{frame}

\ssp

\section[Experiment]{Experimental Design}

\dbsp

\begin{frame}{Cross-Validation}
\bi 
\item Cross-validation is a Statistical Method to Divide Data into a Fixed Number of Partitions, with Part for Training and Part for Testing
\item Used to Generate Many Results of Classifier Runs, Rather than Relying on just One Run Each
\item Performance is Averaged Across Several Runs, Preventing one Standout Result from Causing a Conclusion
\item Experiment Utilized 10 by 10-fold Cross-validation, Generating 100 Results per Class per Discretization Method
\ei 
\end{frame}

\begin{frame}{Cross-Validation Explanation}
Because We Used 24 Data Sets, We Generated Quite a Bit of Data.  For a Data Set with Three Classes, For Example,
\begin{center}
\small
\ssp
\begin{eqnarray}
\nonumber 5~Discretization~Methods \times 100~Results \times 3~Classes \\
\nonumber = 300~Results~per~Discretization~Method \\\nonumber= 1500~Total~Results
\end{eqnarray}
\normalsize
\dbsp
\end{center}
This Means that for the Letter Data Set, with 26 Classes, We Generated 2600 Results per Discretization Method, for a Total of 13000 Results.
\end{frame}

\begin{frame}{Performance Measures}
\bi 
\item<+-> \bo{Accuracy}, or \bo{acc}, Describes the Percentage of Cases Where The Learner/Method Pair makes the Correct Identification of a Instance's Class.
\item<+-> \bo{Probability of Detection}, or \bo{pd}, Describes the Percentage of the Target Class that is Correctly Identified.
\item<+-> \bo{Probability of not False Alarm}, or \bo{npf}, Describes The Percentage of the identified cases where an Identification of the Target Class is Correct
\ei 
\end{frame}
\begin{frame}{Performance Measures}
\bi 
\item<+-> \bo{Precision}, or \bo{prec}, Describes the Proportion of Cases where Instances Identified as Being of a Particular Class actually Belong to that Class
\item<+-> \bo{Balance}, or \bo{bal}, Describes the balance of Probability of Detection and Probability of False Alarm.  A Higher Balance means the Learner is Identifying Most Instances Correctly Without Risking False Alarms to be Correct.
\ei 
\end{frame}
\begin{frame}{Mann-Whitney $U$-test}
\bi 
\item Non-parametric Measure to Compare Learner/Method Pair
\item Makes No Assumptions about Shape of Data
\item Allows Comparison of Results With Differing Number of Values
\item Requires no Post-Processing to Explain Results
\ei 
\end{frame}

\ssp

\section[Results]{Experimental Results}
%\subsection{DiscTree Implementations}

\dbsp

\begin{frame}{DiscTree Comparison Results}
\bi
\item<+-> Two Features of DiscTree were Questioned During Implementation
\bi 
\item<+-> Nominal Value Discretization
\item<+-> Garbage Collection
\ei 
\item<+-> To Determine Best Method, Coded Each and Compared Using Described Experimental Design
\ei 
\end{frame}
\begin{frame}{DiscTree Comparison Results}
\bi
\item<+-> Methods Performed Vary Similarly; However,
\bi 
\item<+-> \bo{disctree3}, the method using just Garbage Collection, performed most accurately
\item<+-> \bo{disctree3} and \bo{disctree4} (which implemented neither Garbage Collection nor Nominal Discretization) beat \bo{disctree2} which implemented both.
\ei 
\item<+-> Because it Acquired the Most $U$-test Wins, \bo{disctree3} was Selected for use in the General Comparsion.
\ei
\end{frame}

\ssp

%\subsection{Discretization Method Comparision}

\dbsp

\begin{frame}{Method Comparison Results}
\begin{figure}
\begin{center}
\begin{tabular}{c|ccccc|}\cline{2-6}
\multicolumn{1}{c|}{}& acc& bal& npf& pd& prec\\\cline{2-6}
cat&	0&	0&	0&	0&	0\\
disctree3&	1&	2&	0&	2&	1\\
fayyadIrani&	4&	4&	4&	4&	4\\
pkid&	1&	2&	0&	2&	1\\
tbin&	1&	1&	3&	0&	1\\\cline{2-6}
\end{tabular}
\end{center}
\caption{Summary of $U$-test Results}
\end{figure}
\end{frame}

\begin{frame}{Method Comparison Results}
\begin{figure}
\begin{center}
\begin{tabular}{cc}
\includegraphics[scale=0.41]{letter-acc.pdf}&
\includegraphics[scale=0.41]{auto-mpg-acc.pdf}\\
\end{tabular}
\end{center}
\caption{Sample Normal(left) and Standout(right) Results}
\end{figure}
\end{frame}

\begin{frame}{Method Comparison Results}
\begin{figure}
\begin{center}
\begin{tabular}{cccc}
\includegraphics[scale=0.15]{waveform-5000-acc.pdf}&
\includegraphics[scale=0.15]{breast-cancer-prec.pdf}&
\includegraphics[scale=0.15]{splice-acc.pdf}&
\includegraphics[scale=0.15]{kr-vs-kp-pd.pdf}\\
\includegraphics[scale=0.15]{waveform-5000-pd.pdf}&
\includegraphics[scale=0.15]{breast-cancer-acc.pdf}&
\includegraphics[scale=0.15]{segment-acc.pdf}&
\includegraphics[scale=0.15]{kr-vs-kp-acc.pdf}\\
\includegraphics[scale=0.15]{mushroom-acc.pdf}&
\includegraphics[scale=0.15]{splice-bal.pdf}&
\includegraphics[scale=0.15]{waveform-5000-acc.pdf}&
\includegraphics[scale=0.15]{heart-h-pd.pdf}\\
\includegraphics[scale=0.15]{soybean-prec.pdf}&
\includegraphics[scale=0.15]{mushroom-prec.pdf}&
\includegraphics[scale=0.15]{heart-h-acc.pdf}&
\includegraphics[scale=0.15]{letter-npf.pdf}\\
\end{tabular}
\end{center}
\end{figure}
\end{frame}

\dbsp

\section{Conclusions}
%\subsection{Future Work}

\dbsp

\begin{frame}{Possible Future Work Areas}
\bi 
\item<+-> Convert DiscTree Algorithm to an Incremental Discretization Method
\item<+-> Implementing DiscTree Algorithm on Other Tree Data Structures
\item<+-> Addition of Additional Data Preprocessing
\item<+-> Reexamination of DiscTree Algorithm for "Best Values"
\ei 
\end{frame}

\ssp

%\subsection{Conclusion}

\dbsp

\begin{frame}{Conclusions From This Thesis}
\bi 
\item<+-> Across All Performance Measures, Entropy-Minimization out performs the competition according to $U$-test Results.
\item<+-> However, in Most Cases, Other Methods Perform Very Nearly as well as the Entropy-Minimization Method.
\item<+-> DiscTree Performs Second-Best in Each Performance Measure
\ei 
\end{frame}
\begin{frame}{Conclusions from This Thesis}
Results Lead Us to Believe:
\bi 
\item<+-> There is No Single Best Method of Discretization in All Cases;
\item<+-> However, Discretization Almost Always Increases Accuracy and Other Performance Measures in \nbc, with simple methods performing nearly as well; and, 
\item<+-> Perhaps the Energy Spent Continuing to Study Batch Discretization Might Be Better Spent Elsewhere.
\ei 
\end{frame}

\section{Questions}
\begin{frame}
\begin{center}
Questions?
\end{center}
\end{frame}

\end{document}
