\dbsp
Chapter \ref{background} provides background information on data mining, specifically the topics of data and classification.  It provides information about some of the common classification methods and explains our selection of the Na\"{i}ve Bayes classifier as a test platform for discretization.

Section \ref{d&dm} describes the use of data in data mining, including types of data and a basic explanation of the format of the data used in this thesis.  Section \ref{classification} describes the machine learning process of classification and discusses a sampling of various classifiers, including decision tree and Na\"{i}ve Bayes classifiers.  
Section \ref{summary} explains the usefulness of the information of this Chapter and how it leads to our selection of a classification method for the experiments in this document and the justification for that selection.

\ssp

\section{Data and Data Mining}
\label{d&dm}
\subsection{Data}
\label{data}
\dbsp
In this modern age, almost everything we do is a source of data.  Prompt payment of bills is recorded by credit agencies to maintain or increase a credit score or credit limit, while late payments may decrease it or decrease future credit opportunities.  Purchases from websites are recorded to determine other items or services that the company or its business partners might offer or to send reminders when a service needs renewed or an item replaced.  Grades, standardized test scores, extra-curricular involvement, and student personal information are all collected by colleges and universities to be analyzed for admission and scholarships.  Almost any imaginable piece of information is useful to someone, and most of it can and does get recorded as data in electronic databases.  

Data captured from the real world comes in a variety of forms.  Values may arrive as a series of selections, such as a choice of favorite color from the set {blue, red, green, yellow, orange, pink, purple}, or a choice of marital status from the set {single, married, divorced, widowed}.  Such qualitative data, where the values are chosen from a finite set of distinct possible values, is called \textit{nominal} or \textit{categorical} data.  Ordinal data, where the fixed categories have some sort of relation to each other, such as age ranges {0 to 9, 10 to 19, ... ,110 to 120} where "older" and "younger" ranges can be discussed, may also be referred to as \textit{discrete} data \cite{fw2}.  However, because there exists no concept of distance between ordinal data values - that is, you can not add two of such values to obtain a third or subtract one from another and be left with a third - they are often treated like nominal values.  Other data may arrive as measurements, such as the monthly rainfall of a city, the average rushing yards per touch of a football player, or a person's average weekly spending at the grocery store.  These measurements, which make take on an almost unlimited number of quantitative values, are called \textit{numeric} or \textit{continuous} data, and may includes both real (decimal) and integer values \cite{fw2}.

Data is most often stored in files or databases.  The basic unit of these storage structures is the record, or one data \textit{instance}.  Each instance can be considered to be a line in a data file or a row in a database table.  Each instance is made up of values for the various \textit{attributes} that comprise it.  The attributes or \textit{features} of each instance, the columns of our database table or file, are the information we wish to know for each instance.  From the previous example about student admissions and financial aid data, a student instance might be comprised of a SAT score attribute, an ACT score attribute, a class ranking attribute, a GPA attribute, a graduation year attribute, and an attribute that denotes whether the college or university collecting that information gave that student financial aid.  Instances often consist of mixed format data; that is, an instance will often have some nominal or discrete attributes and some continuous attributes \cite{det02}.  Another example of a set of instances can be found in \fig{weather}.  Each record or instance is a row in the table and is labeled here with a number that is not part of the data set for reference purposes.  Each column has the name of the attribute that it represents at the top.  

\begin{figure}[ht]%[!t]
\begin{center}
\small \ssp
\begin{tabular}{|r|ccccc|}\cline{1-6}
\multicolumn{1}{|c|}{\textit{Instance}}&\multicolumn{4}{c}{\textit{Attributes}}&\multicolumn{1}{c|}{\textit{Class}}\\
  & outlook&	temperature&	humidity&	windy&	play\\\hline
 1&	sunny&		85&	85&	false&	no\\
 2&	sunny&		80&	90&	true& 	no\\
 3&	overcast&	83&	86&	false&	yes\\
 4&	rainy&		70&	96&	false&	yes\\
 5&	rainy&		68&	80&	false&	yes\\
 6&	rainy&		65&	70&	true&		no\\
 7&	overcast&	64&	65&	true&		yes\\
 8&	sunny&		72&	95&	false&	no\\
 9&	sunny&		69&	70&	false&	yes\\
10&	rainy&		75&	80&	false&	yes\\
11&	sunny&		75&	70&	true&		yes\\
12&	overcast&	72&	90&	true&		yes\\
13&	overcast&	81&	75&	false&	yes\\
14&	rainy&		71&	91&	true&		no\\
\cline{1-6}
\end{tabular}
\end{center}
\caption{The WEATHER data set, with both nominal and continuous values}
\label{fig:weather}
\end{figure}

\normalsize \dbsp

While advances in storage technology have allowed the collection and storage of the vast amount of data now available, the explosion of available data does not always mean that the collected data is being used to its full potential.  Often, the pure massiveness of the data collected can overwhelm those who have requested it be stored.  They may find themselves staring at a mountain of data that they didn't expect and don't know how they will ever analyze.  Even if they do manage to view it all, they may only see the facts that are obvious in the data, and sometimes may even miss these.  Fortunately, the same computers that are storing the collected data can aid these data-swamped users in their analysis.

\ssp
\subsection{Data Mining}
\label{dm}

\dbsp
Data analysis may seem trivial when data sets consist of a few records consisting of few attributes.  However, human analysis quickly becomes impossible when datasets become large and complex, consisting of thousands of records with possibly hundreds of attributes.  Instead, computers can be used to process all of these records quickly and with very little human interaction.  The process of using computers to extract needed, useful, or interesting information from the often large pool of available data is called \textit{data mining}.  More precisely, data mining is the extraction of implicit, previously unknown, and potentially useful information about data \cite{fw2}.  

The technical basis of data mining is called \textit{machine learning} \cite{fw2}.  A field within artificial intelligence, it provides many of the algorithms and tools used to prepare data for use, examine that data for patterns, and provide a theory based on that data by which to either explain previous results or predicting future ones \cite{fw2, ao04}.  These tools provide the information they gather to analysts, who can then use the results to make decisions based on the data patterns, anticipate future results, or refine their own models.  Data mining thus becomes a tool for descriptive prediction, explanation, and understanding of data that might otherwise be lost within the ever growing sea of information \cite{fw2}.

\ssp

\section{Classification}
\label{classification}

\dbsp

\textit{Classification}, also referred to as \textit{classification learning}, is a type of data mining whereby a computer program called a \textit{learner} is provided with a set of pre-classified example instances from which it is expected to learn a way to classify future, unseen, unclassified instances \cite{fw2}.  Most often, the pre-classified examples are prepared by experts or are real, past examples which are supposed to represent the known or accepted rules about the data.  The learner is provided with these in order to then form its own rules for how to treat future instances.  It does this, in general, by examining the attributes of the example instances to determine how they are related to that instances \textit{class}.  The class of an instance is an attribute which denotes the outcome for the instance.  From the previous student financial aid example, if we were using a classifier to determine whether students should receive student aid, this class attribute would be the attribute denoting whether the student received financial aid or not.  In the data set in \fig{weather}, the class attribute, play, takes on the values of \textit{yes} and \textit{no}, denoting a decision as to whether some decision is made based on the weather.  The learner would examine the set of example instances and build a \textit{concept} by which it relates the other attributes to the class attribute to make a set of rule for how to decide which class future instances will be assigned \cite{fw2}.  The method by which the learner determines the concept it will use on future examples differs based upon the type of \textit{classification learner} used.  A wide variety of classification learners exist, but among the most popular are decision tree learners, rule-generating learners, and Na\"{i}ve Bayes classifiers.  

\ssp

\subsection{Decision Tree Learners}
\label{decision-tree}

\dbsp

Decision tree learners use a method called \textit{decision tree induction} in order to construct its concept for classification.  In decision tree induction, an attribute is placed at the root of the tree (see \sect{trees}) being created and a branch from that root is created for each value of that attribute.  This process is then repeated recursively for each branch, using only the instances that are present in the created branch \cite{ao04, fw2}.  The process stops when either too few examples fall into a created branch to justify splitting it further or when the branch contains a pure set of instances (i.e. the class of each example in the branch is the same).  Once a decision tree has been built using training examples, test examples can be classified by starting at the root of the tree and using the attribute and conditional tests at each internal node and branch to reach a leaf node that provides a class for examples that reach the given leaf.  Decision trees are thus trees whose leaf nodes provide classifications to examples who reach those leaves by meeting the conditional statements of the preceding branches of the tree. \fig{sampledtree} provides an example of a decision tree.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.50]{wdt.png}
\end{center}
\caption{A Sample Decision Tree}
\label{fig:sampledtree}
\end{figure}

An example of a decision tree learner is J48.  J48 is a JAVA implementation of Quinlan's C4.5 (version 8) algorithm \cite{quinlan93}.  J48/C4.5 treat numeric attributes using a binary-chop at any level, splitting the attribute into two parts that can later be chopped again if necessary (i.e. in this case an attribute may be reused).  C4.5/J48 uses information theory to assess candidate attributes in each tree level: the attribute that causes the {\em best split} is the one that {\em most simplifies} the target concept.  Concept simplicity is measured using information theory and the results are measured in bits.  It does this using the following equations:

\begin{eqnarray}
\label{eq:entropy}
entropy(p_{1}, p_{2}, ..., p_{n})=-p_{1}log(p_{1})-p_{2}log(p_{2})-...-p_{n}\log(p_{n})\\
\nonumber or \\
\nonumber entropy(p_{1}, p_{2}, ..., p_{n})=-\sum_{i=1}^{n}p_{i}\log{p_{i}}
\end{eqnarray}

\begin{equation}\label{eq:info}
info([x,y,z])=entropy(\frac{x}{x+y+z},\frac{y}{x+y+z},\frac{z}{x+y+z})
\end{equation}

\begin{equation}\label{eq:gain}
gain(\textit{attribute})= info(\textit{current}) - avg.~info(\textit{proposed})
\end{equation}

A good split is defined as one most decreases the number of classes contained in each branch.  This helps to ensure that each subsequent tree split results in smaller trees requiring fewer subsequent splits.

\eq{entropy} defines the \textit{entropy} - the degree of randomness of classes in a split.  The smaller the entropy is - the closer it is to zero - the less even the class distribution in the split; the larger the entropy - the closer it is to one - the more evenly divided the classes in the split.  

Information, measured in bits, specifies the purity of a branch in the decision tree.  The information measure of a given leaf node of a decision tree specifies how much information would be necessary to specify how a new example should be classified at the should the given example reach the given leaf node in the tree.  \eq{info} allows the calculation of that amount of information.  For example, if the leaf node contained 5 example instances, 3 of class \textit{yes} and 2 of class \textit{no}, then the information needed to specify the class of a new example that reached that leaf node would be:
\begin{eqnarray}
\nonumber info([3,2])=entropy(\frac{3}{5},\frac{2}{5})
\nonumber =-\frac{3}{5}\log\frac{3}{5}-\frac{2}{5}\log\frac{2}{5}
\nonumber \approx 0.971~bits
\end{eqnarray}

The \textit{information gain}, defined in \eq{gain}, of a split is the decrease of information needed to specify the class in a branch of the tree after a proposed split is implemented.  For example, consider a tree with twenty(20) training instances with an original class distribution of thirteen(13) \textit{yes} instances and seven \textit{no} instances.  A proposed attribute value test would split the instances into three branches; one containing only seven \textit{yes} instances and one \textit{no}instances, the second five \textit{yes} and one \textit{no}, and the third the remaining instances.  The information of the original split is calculated, $info([13,7])\approx 0.934 ~bits$.  Each of the information measures for the splits that would be created are also generated, and an average value derived.  This average value is the class information entropy of the attribute, a formula for which an be found in \eq{cie}:

\begin{equation}
E(attribute) = \frac{|S_{1}|}{|S|}entropy(S_{1}) + ... + \frac{|S_{n}|}{|S|}entropy(S_{n})
\label{eq:cie}
\end{equation}

Where $S_{1}$ through $S_{n}$ are the subsets created when \textit{attribute} takes on \textit{n} unique values and thus creates \textit{n} branches if used as the split point in the tree; S is the original distribution of classes for this split; and $|S_{i}|$ is the size - number of instances - in $S_{i}$.  Applying this formula to our previous example, we get:

\begin{eqnarray}
\nonumber info([7,1]) \approx~0.544~bits \\
\nonumber info([5,1]) \approx~0.650~bits \\
\nonumber info([1,5]) \approx~0.650~bits \\
\nonumber E([7,1],[5,1],[1,5]) = \frac{8}{20}*.544+\frac{6}{20}*.650+\frac{6}{20}*.650 \approx~0.413~bits
\end{eqnarray} 

Then the information gain for the proposed split would be:
\begin{eqnarray}
\nonumber gain(\textit{attribute})=info([13,7])-E([7,1],[5,1],[1,5])
\nonumber = 0.934~bits~-~0.413~bits=0.521~bits
\end{eqnarray}

The gain for each attribute that might be used as the splitting attribute at this level of the tree would be compared and the one that maximizes this gain would be used as the split; in the case of a tie an arbitrary choice could be made.  However, simply using gain can present an issue in the case of highly branching attributes, such as an unique ID code assigned to each instance.  Such an attribute would create a separate branch for each attribute and have an extremely small (zero) information score that would result in a very high gain.  While such a split attribute would be desired using just the gain measure, it would not be desired in a tree split because it would lead to an issue of \textit{over-fitting}.  Over-fitting occurs when a few, very specific values are used in the creation of a classification concept, that results in a concept that always or most often will result in a misclassification during testing.  The ID code attribute would cause such a problem to occur, most likely never predicting instances incorrect that did not appear in the training set.  In order to avoid this, another measure is used that takes into account both the number and size of child nodes of a proposed split.  This measure is called the \textit{gain ratio} \cite{fw2}.  To calculate gain ratio, we start with the gain calculated previously, and divide it by the information that is derived from the number of instances (the sum of the number of instances of each class) in each split.  From the previous example, we could calculate the gain ratio as follows:

\begin{eqnarray}
\nonumber gain(\textit{attribute})~=~0.521~bits \\
\nonumber info([8,6,6])~=~entropy([\frac{8}{20},\frac{6}{20},\frac{6}{20}])\\
\nonumber =~-\frac{8}{20}\log\frac{8}{20}~-~\frac{6}{20}\log\frac{6}{20}~-~\frac{6}{20}\log\frac{6}{20}\\
\nonumber info([8,6,6])~\approx~1.571~bits \\
\nonumber gain~ratio=\frac{gain(\textit(attribute))}{info([8,6,6])}=\frac{0.521~bits}{1.571~bits}~\approx~0.332~bits \\
\end{eqnarray}

The attribute with the highest gain ration is then used as the split point.  Additionally, certain other tests may be included in some decision tree induction schemes to ensure that the highly branching attribute described previously is not even considered as a possible splitting attribute.  As described previously, the splitting process in decision tree induction continues in each of the created branches until some stopping criterion is reached, be it too few instances left in a branch to justify splitting, a pure branch, or some other test.

Trees created by C4.5/J48 are pruned back after they are completely built in order to avoid \textit{over-fitting error}, where a specific branch of the tree is too specific to one or a few training examples that might cause an error when used against the testing data.  This methodology uses a \textit{greedy} approach, setting some threshold by which the accuracy of the tree in making classifications is allowed to degrade and removing the branches in reverse order until that threshold is met.  This ensures that branches do not become over-fitted for a specific instance, which could decrease the accuracy of the tree - especially if the one training instance that fell into that branch was an extreme outlier, had been corrupted by noise in the data, or was simply a random occurrence that got grouped into the training set.

Quinlan implemented C4.5 decision tree post-processor called C4.5rules.  This post-processor generates succinct rules from cumbersome decision tree branches via (a)~a greedy pruning algorithm that removes statistically unnecessary rules followed by (b)~removal of duplicate rules and finally (c)~exploring subsets of the rules relating to the same class~\cite{quinlan93}. It is similar to the rule-learners discussed in \sect{rulelearn}

\ssp

%\subsection{Rule-Generating Learners}
%\label{rule-generators}
%\dbsp
%Two types of rules can be constructed by learners: classification rules and %association rules.  
%\ssp

%\subsubsection{Classification Rules}
%\label{class-rules}
%\dbsp
%A popular alternative to decision trees, \textit{classification rules} are %easily readable and understood by a general user \cite{fw2}.  A simple rule %might take the form found in \fig{SimpleRule}.
%\ssp
%\begin{figure}[h]
%\begin{center}
%If $z=2$ and $y=1$ then $class=t$
%\end{center}
%\caption{Example of a Classification Rule}
%\label{fig:SimpleRule}
%\end{figure}
%\dbsp
%In decision rules, the precondition for the rule - referred to as the %\textit{antecedent} - is a test or tests that are performed against the %attribute values of an instance.  The precondition for the rule is found on the %rule's left hand side, immediately following the "If" that begins the rule.  %For example, the antecedent of the rule in Figure \ref{SimpleRule} would be the %tests \textit{z=2 and y=1}.  The classification decision or conclusion for the %rule - called a \textit{consequent} - is found on the right hand side of the %rule, following the "then" that separates it from the antecedent.  In the rule %in \fig{SimpleRule} the consequent is \textit{class=t}.

%\ssp

%\subsubsection{Association Rules}
%\label{assoc-rules}
%\dbsp
%Association rules are very similar to classification rules.  They share the %same general form in terms of a test (antecedent) that, if passed, results in a %conclusion (consequent).  However, unlike classification rules that predict %only for the class of an instance, association rules can predict for any %attribute or combination of attributes.  Thus, a rule might consist of a test %that tests one attribute value and, if passed, predicts the value for one of %the instances other attributes.  
%\ssp

%\subsubsection{Apriori}
%\label{apri}
%\dbsp
%\ssp

\subsection{Naive Bayes}
\label{nb}
\dbsp

Na\"{i}ve Bayes classifiers are highly studied statistical method used for classification.  Originally used as a \textit{straw man} \cite{dompaz97, yw03} - a method thought to be simple and that new methods should be compared against in order to determine their usefulness in terms of improved accuracy, reduced error, etc - it has since been shown to be a very useful learning method and has become one of the frequently used learning algorithms. 

Na\"{i}ve Bayes classifiers are called na\"{i}ve because of what is called the \textit{independent attribute assumption}.  The classifier assumes that each attribute of an instance is unrelated to any other attribute of the instance.  This is a simplifying assumption used to make the mathematics used by the classifier less complicated, requiring only the maintenance of frequency counts for eacy attribute.  However, real world data instances may contain two or more related attributes whose relationship could affect the class of a testing instance.  Because of the independent attribute assumption, that relationship would most likely be ignored by the Na\"{i}ve Bayes classifier and could result in incorrect classification of an instance.  When a data set containing such relationships is used with the Na\"{i}ve Bayes classifier, it can cause the classifier to skew towards a particular class and cause a decrease in performance.  Domingos and Pazzani show theoretically that the independence assumption is a problem in a vanishingly small percent of cases~\cite{dompaz97}. This explains the repeated empirical result that, on average, Na\"{i}ve Bayes classifiers perform as well as other seemingly more sophisticated schemes.  For more on the Domingos and Pazzani result, see \sect{selection}

A Na\"{i}ve Bayes classifier is based on Bayes' Theorem. Informally, the theorem says $next=old*new$; in other words, what we'll believe {\em next} is determined by how {\em new} evidence affects {\em old} beliefs.  More formally:

\begin{equation}\label{eq:nb}
P(H|E)=\frac{P(H)}{P(E)}\prod_iP(E_i|H)
\end{equation}

That is, given fragments of evidence regarding current conditions $E_i$ and a prior probability for a class $P(H)$, the theorem lets us calculate a posterior  probability $P(H|E)$ of that class occurring under the current conditions.  Each class (hypothesis) has its posterior probability calculated in turn and compared.  The classification is the hypothesis $H$ with the highest posterior $P(H|E)$.

\eq{nb} offers a simple method for handling missing values. Generating a
posterior probability means tuning a prior probability to new evidence. If that evidence is missing, then no tuning is needed. In this case \eq{nb} sets $P(E_i|H)=1$ which, in effect, makes no change to $P(H)$.  This is very useful, as real world data often contains missing attribute values for certain instances;  take, for instance, the student data mentioned previously.  Not all students will take a particular standardized test, so using both the ACT and SAT scores in classification might be harmed in other methods if a missing value were to occur.  However, with Na\"{i}ve Bayes, this missing value does not harm or help the chance of classification, making it ideal for data that may having missing attribute values.

When estimating the prior probability of hypothesis $H$, it is common practice~\cite{yw02, yw03-2} to  use  an {\em M-estimate} as follows.
Given that the total number of classes/hypothesis is $C$, the total number of training instances is $I$, and  $N(H)$ is the frequency of hypothesis $H$ within $I$, then:

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

Here $m$ is a small non-zero constant (often, $m=2$). Three special cases of \eq{b} are:
\bi
\item
For high frequency hypothesis in large training sets, $N(H)$ and $I$ are much larger than $m$ and $m\cdot C$, so  \eq{b} simplifies to $P(H)= \frac{N(H)}{I}$, as one might expect. 
\item
For low frequency classes in large training sets, $N(H)$ is small, $I$ is large,
and the prior probability for a rare class is never less than $\frac{1}{I}$;
i.e. the inverse of the number of instances. If this were not true, rare classes would never appear in predictions.  
\item
For very small data sets, $I$ is small and $N(H)$ is even smaller.
In this case, \eq{b} approaches the inverse of the number of classes; i.e. $\frac{1}{C}$.  This is a useful approximation when learning from very small data sets when all the data relating to a certain class has not yet been seen.
\ei

The prior probability calculated in \eq{b} is a 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\begin{equation}\label{eq:laplace}
P(E_i|H) = \frac{N(f=v|H) +l\cdot P(H)}{N(H) + l}  \end{equation} Here, $l$ is the \textit{L-estimate}, or \textit{Laplace-estimate} and is set to a small constant (Yang \&Webb~\cite{yw02, yw03-2} recommend $l=1$).  Two special cases of are:
\bi
\item
A common situation is when there are many examples of an hypothesis 
and numerous observations have been made for a particular value. In that situation, $N(H)$ and $N(f=v|H)$ are large and \eq{laplace}
approaches \mbox{$\frac{N(f=v|H)}{N(H)}$}, as one might expect. 
\item
In the case of very little evidence for a rare hypothesis, \mbox{$N(f=v|H)$} and $N(H)$ are small and \eq{laplace} approaches $\frac{l\cdot P(H)}{l}$; i.e. the default frequency of an observation in a hypothesis is a fraction of
the probability of that hypothesis. This is a useful approximation when very
little data is available. 
\ei

For numeric attributes it is common practice for Na\"{i}ve Bayes classifiers
to use the Gaussian probability density function~\cite{fw2}:
\begin{equation}\label{eq:normal}
g(x) =
\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}\end{equation} where
$\{\mu,\sigma\}$ are the attributes's \{mean,standard
deviation\}, respectively. To be precise, the probability of a continuous (numeric) attribute having exactly the  value $x$ is zero, but the probability that it lies within a small region, say $x \pm \epsilon/2$, is $\epsilon \times g(x)$.  Since $\epsilon$ is a constant that weighs across all possibilities, it cancels out and needs not be computed.  Yet, while the Gaussian assumption may perform nicely with some numeric data attributes, other times it does not and does so in a way that could harm the accuracy of the classifier.

One method of handling non-Gaussians is Johns and Langley's {\em kernel estimation} technique~\cite{jl95}. This technique approximates a continuous distribution sampled by $n$ observations $\{ob_1, ob_2,...,ob_n\}$ as  the sum of multiple Gaussians with means $\{ob_1, ob_2,...,ob_n\}$ and standard deviation $\sigma=\frac{1}{\sqrt{n}}$. In this approach, to create a highly
skew distribution, multiple Gaussians would be added together.  Conclusions are made by asking all the Gaussians which class they believe is most likely.  

Finally, numeric attributes for Na\"{i}ve Bayes classifiers can also be handled using a technique called \textit{discretization}, discussed in \chap{discretization}.  This has been the topic of many studies (\cite{dou95, hhw03, yw01, yw02, yw03, yw03-2}) and has been shown to deal well with numeric attributes, as seen in \cite{dompaz97} where a Na\"{i}ve Bayes classifier using a simple method of discretization outperformed both so-called state-of-the-art classification methods and a Na\"{i}ve Bayes classifier using the Gaussian approach.

Na\"{i}ve Bayes classifiers are frustrating tools in the data mining arsenal. 
They exhibit excellent performance, but offer few clues about the structure of their models.  Yet, because their performance remains so competitive with other learning methods their structures, this complaint is often overlooked in favor of their use.

\ssp

\subsection{Other Classification Methods}
\label{others}
\dbsp

\ssp

\subsubsection{1-R}
\label{1R}
\dbsp
One of the simplest learners developed was 1-R \cite{holte93, fw2}.  1-R examines a training dataset and generates a one-level decision tree for an attribute in that data set.  It then bases its classification decision on the one-level tree.  It makes a decision by comparing a testing instance's value for the attribute that the tree was constructed against the decision tree values.  It classifies the test instance as being a member of the class that occurred most frequently in the training data with the attribute value.  If several classes occurred with equal frequency for the attribute value then a random decision is used at the time of final tree construction to set the class value that will be used for future classification.

The 1-R classifier decides which attribute to use for future classification by first building a set of rules for each attribute, with one rule being generated for each value of that attribute seen in the training set.  It then tests the rule set of each attribute against the training data and calculates the error rate of the rules for each attribute. Finally, it selects the attribute with the lowest error - in the case of a tie the attribute is decided arbitrarily - and uses the one-level decision tree for this attribute when handling the testing instances.  Pseudo code for 1-R can be found in Figure \ref{1RPseudo}:

\begin{figure}[!ht]
\label{1RPseudo}
\ssp \small
\lstset{language=Python}
\lstset{backgroundcolor=\color{listinggray}}
\lstset{frameround=tttt}
\lstset{basicstyle=\footnotesize}
\lstset{showstringspaces=false, showspaces=false, showtabs=false}
\begin{center}
\begin{lstlisting}[frame=trBL]{}
For each attribute:
     For each value of that attribute, make a rule as follows:
          Count how often each class appears
          Determine the most frequent class 
          Make a rule such that assigns the given value the most frequent class 
     Calculate the error rate of the rules for the attribute
Compare the error rates, determine which attribute has the smallest error rate
Choose the attribute whose rules had the smallest error rate
\end{lstlisting}
\end{center}
\caption{1-R Pseudo-Code}
\dbsp
\end{figure}

The 1-R classifier is very simple and handles both missing values and continuous attributes.  Continuous attributes are handled using discretization, discussed in Chapter \ref{discretization}.  It specifically uses a method similar to \textit{EWD}, defined in Section \ref{EWD}.  Missing values are dealt with by creating a branch in the one-level decision tree for a \textit{missing} value.  This branch is used when missing values occur.  

Because of its simplicity, 1-R often serves a "straw-man" classification method, used as a baseline for performance for new classification algorithms.  While 1-R sometimes has classification accuracies on par with modern learners - thus suggesting that the structures of some real-world data are very simple - it also sometimes performs poorly, giving researchers a reason to extend beyond this simple classification scheme \cite{ao04}.  

\ssp

\subsubsection{Rule Learners}
\label{rulelearn}
\dbsp

Rather than patch an opaque learner like \nbc with a post-processor to make them more understandable  to the average user, it may be better to build learners that directly generate succinct, easy to understand, high-level descriptions of a domain. For example, RIPPER~\cite{cohen95}  is one of the fastest \textit{rule learners} in the available literature.  The generated rules are of the form
\mbox{$condition \longrightarrow conclusion$}:
\[
\underbrace{Feature_1 = Value_1 \wedge Feature_2 = Value_2 \wedge \ldots }_{condition} \longrightarrow
\underbrace{Class}_{conclusion}\]
The rules generated by RIPPER perform as well as C45rules - a method which creates rules from C4.5 decision trees - yet are much smaller and easier to read~\cite{cohen95}.

Rule learners like RIPPER and PRISM ~\cite{cend87} generate small, easier to understand, symbolic representations of the patterns in a data set. PRISM is a less sophisticated learner than RIPPER and is no longer widely used. It is still occasionally used to provide a lower bound on the possible performance. However, as illustrated below, it can still prove to be surprisingly effective.
\begin{figure}[!ht]
\footnotesize \ssp
\begin{center}
\lstset{language=awk}
\lstset{backgroundcolor=\color{listinggray}}
\lstset{frameround=tttt}
\lstset{basicstyle=\footnotesize}
\lstset{showstringspaces=false, showspaces=false, showtabs=false}
\begin{lstlisting}[frame=trBL]{}
(1) Find the majority class C
(2) Create a R with an empty condition that predicts for class C.
(3) Until R is perfect (or there are no more features) do
	(a) For each feature F not mentioned in R
	(b) For each value v in F, consider adding F = v to the condition of R
	(c) Select F and v to maximize p/t where t is 
	    total number of examples of class C and p is the number
       of examples of class C selected by F=v.
       Break ties by choosing the condition with the largest p.
   (d) Add F = v to R
(4) Print R
(5) Remove the examples covered by R.
(6) If there are examples left, loop back to (1)
\end{lstlisting}
\end{center}
\caption{PRISM pseudo-code.}\label{fig:prism}
\end{figure}
\normalsize \dbsp

Like RIPPER, PRISM is a \textit{covering} algorithm that runs over the data in multiple passes. As
shown in the pseudo-code of \fig{prism}, PRISM learns one rule at each pass for the \textit{majority class} 
(e.g. in \fig{weather}, at pass 1, the majority class is $yes$). All the examples that satisfy the condition are marked as \textit{covered} and removed from the data set currently begin considered for a rule. PRISM then recurses on the remaining data.

The output of PRISM is an ordered \textit{decision list} of rules where $rule_j$ is only tested on instance \textit{x} if all conditions in $rule_{i:i<j}$ fail to cover \textit{x}.  PRISM returns the conclusion of the first rule with a satisfied condition.

One way to visualize a covering algorithm is to imagine the data as a table on a piece of paper. If there exists a clear pattern between the features and the class, define that pattern as a rule and cross out all the rows covered by that rule. As covering recursively explores the remaining data, it keeps splitting the data into:
\bi
\item
What is easiest to explain during this pass, and
\item
Any remaining ambiguity that requires a more detailed analysis.
\ei

PRISM is a na\"{i}ve covering algorithm and has problems with \textit{residuals} and \textit{over-fitting} similar to the decision tree algorithms. If there are rows with similar patterns and similar
frequencies occur in different classes, then:
\bi
\item
These \textit{residual} rows are the \textit{last} to be removed for each class;
\item 
so the \textit{same} rule can be generated for \textit{different} classes.  For example, the following rules might be generated: \mbox{if \textit{x} then class=\textit{yes}} and \mbox{if \textit{x} then class=\textit{no}}.
\ei

As mentioned in the discussion on decision tree learners, in \textit{over-fitting}, a learner
fixates on rare cases that do not predict for the target class. PRISM's over-fitting arises from
part 3.a of \fig{prism} where  the algorithm loops through all features. If some feature is poorly measured, it might be noisy (contains spurious signals/data that may confuse the learner). Ideally, a rule learner knows how to skip over noisy features.

RIPPER addresses residuals and over-fitting problem three techniques: \textit{pruning}, \textit{description length} and \textit{rule-set optimization}.  For a full description of these techniques, which are beyond the scope of this thesis, please see \cite{dietterich97}. To provide a quick summary of these methods:
\bi
\item  \textit{Pruning:}
After building a \textit{rule}, RIPPER performs a back-select in a \textit{greedy} manner to see what parts of a \textit{condition} can be deleted, without degrading the performance of the rule.
Similarly, after building a \textit{set of rules}, RIPPER performs a back-select in a \textit{greedy} manner to see what \textit{rules} can be deleted, without degrading the performance of the rule set.  These back-selects remove features/rules that add little to the overall performance.  For example, back pruning could remove the residual rules.
\item \textit{Description Length:}
The learned rules are built while minimizing their \textit{description length}.
This is an information theoretic measure computed from the size of the learned rules,
as well as the rule errors. If a rule set is over-fitted, the error rate increases,
the description length grows, and RIPPER applies a rule set pruning operator.
\item \textit{Rule Set Optimizaton:}
tries replacing rules with straw-man alternatives (i.e. rules grown very quickly by some
na\"{i}ve method).
\ei

\ssp

\subsubsection{Instance-Based Learning}
\label{instancelearn}
\dbsp

Instance-based learners perform classification in a \textit{lazy} manner, waiting until a new instance is inserted to determine a classification.  Each new added instance is compared with those already in the data set using a \textit{distance metric}.  In some instance-based learning methods, the existing instance closest to the newly added instance is used to assign a "group" or classification to the new instance.  Such methods are called \textit{nearest-neighbor} classification methods.  If instead the method used the majority class, or a distance-weighted average majority class, of the \textit{k} closest existing instances, the classification method is instead called a \textit{k-nearest-neighbor} classification method. 

While such methods are interesting to explore, their full and complete explanation is beyond the scope of this thesis.  This introduction is provided as a simple basis for the idea of instance-based learning rather than specific details about specific methods.  For more information about instance-based classification methods, we recommend starting with \cite{fw2}, which provides an excellent overview and explores specific instance-based methods such as \textit{k-means, ball trees, and kD-trees}.

\ssp

\section{Summary}
\label{summary}
\dbsp

\subsection{Data Mining and Classification}
\label{dm&c}
Data Mining is a large field, with many areas to study.  This chapter has touched primarily on classification and classifiers.  Classification is a very useful tool for a variety of industries.  Classifiers can review a variety of medical test data to make a decision about whether a patient is at high risk for a particular disease.  They can be used by retailers to determine which customers might be ideal for special offers.  They could also be used by colleges and universities to determine which students they should admit, which students to spend time recruiting, or which students should be provided financial aid.  These are just a few of the very large number of instances where classification could be used to the benefit of the organization who choses to use it.

Because classification is of such use to so many organizations, many people have studied it.  The result of that study is the variety of different classification methods discussed in this chapter, from rule-based and instance-based learning to decision tree induction methods and \nbc.  The goal of all this research is to find a better classifier, one that performs quickly and more accurately than previous classifiers.  Yet, other data mining methods exist that can help to extend the accuracy of current methods, enabling them to be more accurate without additional manipulation of the classifier itself.  These methods are often preprocessing steps in the data mining process, better preparing the data for use by the classifier.  One such method is \textit{discretization}.  Discretization, in general, removes numeric data - which can often cause concept confusion, over-fitting, and decrease in accuracy - from the original data and substitutes a nominal attribute and corresponding values in its place.  Discretization is discussed in detail in \chap{discretization}.  Because of its usefulness as a preprocessing method to classification, we propose to examine the effects of several methods of discretization on a classifier.  But which classifier would best serve as a testing platform?

\ssp

\subsection{Classifier Selection}
\label{selection}
\dbsp

A variety of literature exists comparing many of these classifier methods and how discretization works for them.  In \cite{dou95}, three discretization methods are used on both the C4.5 decision tree induction algorithm and the Na\"{i}ve Bayes Classifier.  The authors of that paper find that each form of discretization they tested improved the performance of the Na\"{i}ve Bayes Classifier in at least some cases.  Specifically:\begin{quote}
Our Experiments reveal that all discretization methods for the Naive-Bayes classifier lead to a large average increase in accuracy.
\end{quote}

On the other hand, when the same methods were used on the C4.5 learner only two datasets saw significant improvement.  This result leads us to believe that Na\"{i}ve Bayes classifiers truly provides a platform for discretization methods to improve results and have a true, measurable impact on the classifier.

In addition to that study, \cite{dompaz97} compared the performance of the Na\"{i}ve Bayes classifiers against C4.5 decision tree induction, PEBLS 2.1 instance-based learning, and CN2-rule induction.  It compared those methods against both a Gaussian-assumption Na\"{i}ve Bayes classifier, which uses an assumption that all continuous features fit in a normal distribution to handle such values, and a version of Na\"{i}ve Bayes that uses Equal Width Discretization (see \sect{EWD}) as a preprocessor to handle any continuous data instances.  It found that the simple Na\"{i}ve Bayes classifier using EWD performed the best out of the compared methods, even compared against methods considered to be state-of-the-art, and that the Na\"{i}ve Bayes classifier with the Gaussian-assumption performed nearly as well.  The paper also went on to test whether violating the attribute independence assumption caused the classifier to significantly degrade, and found that the Na\"{i}ve Bayes classifier still performed well when strong attribute dependencies or relationships were present in the data.  

Finally, some of the most recent developments in discretization have been proposed specifically for use with the Na\"{i}ve Bayes classifier.  The most modern discretization method used in our experiment, aside from the DiscTree method implementation, is the PKID discretization method (see \sect{pkid}).  This method was derived with the specific intent of it being used with the Na\"{i}ve Bayes classifier, and in order to provide a comparison with the results of the study performed with its implementation, we believe it necessary to perform a comparison using that classifier.  The same author has proposed numerous other methods of discretization for Na\"{i}ve Bayes as well, specifically in \cite{yw01, yw02, yw03, yw03-2, yw03-3}.  This leads us to believe that we too may be able to improve the performance of this classifier.

As a result, we propose to use the Na\"{i}ve Bayes classifier for our experimental comparison of discretization methods, despite all the other types of available learners.  We feel it is necessary to choose one learner with which to compare the discretization methods in order to provide for easy comparison of the discretization methods without fear that the classifier is providing some or all of any notable performance differences.   We feel the Na\"{i}ve Bayes classifier will provide the best comparison point due to its use to derive the most recent compared results \cite{yw01} and is the learner where the benefits of discretization have been most analyzed and best displayed, as seen in \cite{dou95}.  While it does make assumptions about the data attributes being independent, we feel that based on \cite{dompaz97} we can reasonably move forward that this assumption will have a minimal affect on the data, and because we are not comparing across classification methods but rather between various discretization methods used on the same classifier, that this assumption will equally affect all results if present and can thus be discounted.  Thus, we are confident that the simple Na\"{i}ve Bayes classifier will provide an acceptable base for our experimental comparison of the discretization methods that will now be presented.

For the purposes of our experiment, we will use the Na\"{i}ve Bayes Classifier implemented in the 
\textit{Waikato Environment for Knowledge Analysis}, or \textit{WEKA}\cite{fw2}.  The learner is called using the wttp script in \app{xval}. and is called weka.classifiers.bayes.NaiveBayes.

\ssp
