\dbsp

Chapter \ref{experiment} describes the experimental approach used to compare the discretization techniques.
\sect{mydata} explains the data used to perform this comparison.
Section \ref{crossval} explains the cross-validation method used to generate the results from the learner.
Section \ref{measures} explains the different measures used to compare the effects of discretization on the Na\"{i}ve Bayes classifier.
Section \ref{mann-whit} explains the Mann-Whitney approach used to compare the results of each discretization method against its competitors.

\ssp

\section{Test Data}
\label{mydata}
\dbsp

In order to perform the comparison between the various discretization methods, we sought to use a variety of data sets of both small - under 1000 instances - and large data sets.  We also sought data sets that used varying numbers of classes.  We have decided to use 24 data sets from the UCI machine learning repository \cite{an07} which contain varying numbers of numeric and discrete attributes but each has a discrete class attribute making it an easy candidate for classifier learning.  The data sets we have elected to use and their describe features can be found in \fig{mydatatable}.

\newpage
\begin{figure}[!ht]
\begin{center}
\footnotesize \ssp
\begin{tabular}{|c|c|c|c|c|c|}\cline{1-6}
\textit{Data Set}& \textit{Instances}& \textit{Attributes}& \textit{Numeric}& \textit{Nominal}& \textit{Classes}\\\hline
hayes-roth& 132& 5& 1& 4& 3\\
iris& 150& 4& 4& 0& 3\\
hepatitis& 155& 19& 6& 13& 2\\
wine& 178& 13& 13& 0& 3\\
flag& 194& 28& 10& 18& 4\\
imports-85& 205& 25& 15& 10& 5\\
audiology& 226& 69& 0& 69& 24\\
breast-cancer& 286& 9& 0& 9& 2\\
heart-h& 294& 13& 6& 7& 5\\
heart-c& 303& 13& 6& 7& 5\\
ecoli& 336& 7& 7& 0& 8\\
auto-mpg& 398& 7& 5& 2& 3\\
wdbc& 569& 30& 30& 0& 2\\
soybean& 683& 35& 0& 35& 19\\
credit-a& 690& 15& 0& 15& 2\\
breast-cancer-wisconsin& 699& 9& 0& 9& 2\\
diabetes& 768& 8& 8& 0& 2\\
vowel& 990& 13& 10& 3& 11\\
segment& 2310& 19& 19& 0& 7\\
splice& 3190& 61& 0& 61& 3\\
kr-vs-kp& 3196& 36& 0& 36& 2\\
%sick& 3772& 29& 7& 22& 2\\
waveform-5000& 5000& 40& 40& 0& 3\\
mushroom& 8124& 22& 0& 22& 2\\
letter& 20000& 16& 16& 0& 26\\
\cline{1-6}
\end{tabular}
\end{center}
\caption{Data Sets Used for Discretization Method Comparison.  The attributes column refers to the number of non-class attributes that exist in the data set; the data set would have one more nominal attribute if the class were counted.}
\label{fig:mydatatable}
\end{figure}
\clearpage

\normalsize \dbsp
\ssp

\section{Cross-Validation}
\label{crossval}

\dbsp

\textit{Cross-validation} is a statistical method that divides data into a fixed \textit{n} \textit{folds}, or partitions, of approximately the same size \cite{fw2}, for example, three folds each containing one-third of the data.  The first fold is then used for classifier testing, while the remaining \textit{n-1} folds are used for classifier training.  The process is repeated so that each of the \textit{n} folds is used for testing.  The resulting process is known as \textit{n}fold cross-validation.  This process can be combined with \textit{stratification}, or random sampling to create the folds so as to guarantee that each class is represented evenly in both the testing and training sets, which results in approximately the same class distribution across folds.  The result is called \textit{stratified nfold cross-validation}.

Tenfold stratified cross-validation is a standard way of measuring the error rate or accuracy of a learning scheme on a particular dataset \cite{det02, fw2, jl95}.  In this form of cross-validation, the data is divided randomly into ten subsets of approximately the same size.  The classifier is run ten times. Each run, the classifier uses a different subset as the testing set while the other subsets are combined to use as the training set.  This results in ten different accuracy/error estimates for the learner that can be averaged to provide an overall accuracy/error estimate.  

In order to ensure that variation in randomization or classifiers do not cause invalid or unreliable results in a tenfold cross-validation, it is recommended in \cite{fw2} that the tenfold cross-validation process be repeated ten times, resulting in running the learning algorithm 100 times on a dataset.  The results are then averaged to obtain the accuracy/error rate for the learning algorithm.

In our experiment, we will use this \textit{ten by tenfold cross-validation} (10 x 10fold) process to compare the results of each discretization method.  We will first run each discretization method for this experiment on the data, creating a total of five data sets to test - the original data set, the data set discretized using PKID, the data set discretized using the entropy-based method, the data set discretized using the tenbins equal width discretization method, and the data set discretized using the DiscTree algorthim.  Each of the five data sets is then used with a Na\"{i}ve Bayes Classifier to complete a ten x ten fold cross validation.  The results are then compared as described in \ref{mann-whit}.

It is worth noting that one of the results we seek to compare against is that from \cite{yw01}.  The authors of that paper, and in all of their other papers comparing discretization methods that we are aware of (\cite{yw02, yw03, yw03-2, yw03-3}), use a ten by threefold cross-validation (10x3).  We put forth that we are provide more runs for comparison using our ten by tenfold cross-validation approach and that, as a result, we can be confident that our results are comparable to the previous results because they used fewer runs, each of which would have a larger affect on the average result used to compare discretization methods.

We implemented cross-validation as a BASH script.  The source code for is available for review in \app{xval}.

\ssp


\section{Classifier Performance Measurement}
\label{measures}

\dbsp
As part of the cross-validation script we have created, we have provided a means of calculating several discretization method/classifier \textit{performance measures}.  These methods are described as follows:

Allow that {\textit{A, B, C, D}} denote, in order, the true negatives, false negatives, false positives, and true positives found by a binary detector.  True negative denotes when the detector does not identify the class of an instance as the desired class because it is truly not of the desired class; false negatives, on the other hand, denote when the detector does not identify the class of an instance as the desired class despite the fact that it is of the desired class.  False positives denote when the detector believes an instance does belong to the desired class but, in fact, it does not.  Finally, true positives are those instances where the detector determines the class of the instance is of the desired class and it is, in fact, of that class.  These definitions are illustrated in \fig{expltable}.

\begin{figure} [!ht]
\begin{center}
\begin{tabular}{c|p{1.5cm}|c|c|}
\multicolumn{2}{c}{}&\multicolumn{2}{c }{instance of desired class?}\\\cline{3-4} \multicolumn{2}{c|}{}&no&yes\\\cline{2-4}
identified as &no &A (true negative)  &B (false negative)\\\cline{2-4}
desired class?&yes &C (false positive) &D (true positive)\\\cline{2-4}
\end{tabular}
\end{center}
\caption{A Tabular Explanation of \textit{A, B, C, \& D}}
\label{fig:expltable}
\end{figure}

The following measures can be calculated from the values of \textit{A, B, C, \& D}.  Each of the results falls between 0 and 1; when multiplied by 100, the scores produced can be discussed as percentages between 0 and 100\%.  

\begin{center}
\small
\begin{equation}
\textit{accuracy}~=~\textit{acc}~=~\frac{\textit{A~+~D}}{\textit{A~+~B~+~C~+~D}}
\label{eq:acc}
\end{equation}
\begin{equation}
\textit{probability of detection} ~=~ \textit{pd} ~=~ \textit{recall} ~=~ \frac{\textit{D}}{\textit{B~+~D}}
\label{eq:pd}
\end{equation}
\begin{equation}
\textit{probability of false alarm} ~=~ \textit{pf} ~=~ \frac{\textit{C}}{\textit{C~+~A}}
\label{eq:pf}
\end{equation}
\begin{equation}
\textit{not probability of false alarm} ~=~ \textit{!pf} ~=~ 1 ~-~ \textit{pf}
\label{eq:!pf}
\end{equation}
\begin{equation}
\textit{precision} ~=~ \textit{prec} ~=~ \frac{\textit{D}}{\textit{D~+~C}}
\label{eq:prec}
\end{equation}
\begin{equation}
\textit{balance} ~=~ \textit{bal} ~=~ 1 - \frac{\sqrt{\left(0-pf\right)^{2}+\left(1-pd\right)^{2}}}{\sqrt{2}}
\label{eq:bal}
\end{equation}
\normalsize
\end{center}

\eq{acc} describes the \textit{accuracy} of a classifier (or in our case, a discretization method/classifier pair). By this, we mean the percentage of cases in which the classifier accurately identifies the true positives and true negatives; that is, it correctly identifies when an instance belongs to the desired class and when it does not.  

\eq{pd} describes the probability of detection of the desired class.  It is also referred to as \textit{recall}.  This equation measures how much of the desired class is found and correctly identified.  

\eq{pf} describes the probability of false alarm, where an instance is identified as belonging to the desired class when it, in fact, does not.  \eq{!pf} identifies the proportion of cases that were not false alarms.  This measure is most often used, as opposed to the \eq{pf} as it allows for positive comparison of the methods; that is, the desired score \textit{!pf} would be a high score like those desired for \textit{pd} or \textit{acc}, where as the desire when dealing with \eq{pf} is to find the method with the smallest result.

\eq{prec} describes the precision of the method used.  The precision of a method identifies the proportion of instances which were identified as being of the desired class that are actually of the desired class.  A high precision is desired over a lower one.

\eq{bal} describes the method's balance between \textit{pd} and \textit{pf}.  While the desired balance would be \textit{pd}$=1$ and \textit{pf}$=0$, this does not occur in practice, with methods instead often taking on \textit{risk-adverse} balances - with a high \textit{pf} in order to ensure a high \textit{pd} - or \textit{cost-adverse} balances - where in order to keep from having too many costly alarms, the method accepts a low \textit{pd} in order to ensure a low \textit{pf}.  Higher \textit{bal} scores mean that the method performs closer to the ideal balance and thus a higher score is desired.

\ssp

\section{Mann-Whitney}
\label{mann-whit}

\dbsp

Many papers comparing results of classification compare those results using standard parametric statistical tests, such as the \textit{t}-test, to determine whether the results for one classifier differ significantly from the results of other classifiers.  In the case that the test does find statistical significance, a classifier may be said to significantly better or worse than another classifier. The problem with this approach is that it assumes a specific distribution for the data being examined for significance; for example, in the case of a \textit{t}-test, that assumption is that the distribution takes on a curve similar to \textit{N(0,1)}, the normal curve between 0 and 1 \cite{mm2}.  Unfortunately, data can not be guaranteed to fit a specific curve, and outliers in the data can cause the mean and standard deviation measured used for parametric measures to become greatly skewed from the actual bulk of the data.  As a result, it is considered prudent that nonparametric tests be used to compare results.

The problem of comparatively assessing $L$ learners (or $L$ discretization methods on one learner) run on multiple sub-samples of $D$ data sets has been extensively studied in the data mining community. T-tests that assume Gaussian distributions are becoming deprecated.  Demsar~\cite{jd06} argues that non-Gaussian populations are common enough to require a methodological change in data mining. 

Demsar~\cite{jd06} offers a definition of \textit{standard methods} in data mining.  In his study of four years of proceedings from the \textit{International Conference on Machine Learning}, he found that the standard method of comparative assessment were t-tests over some form of repeated sub-sampling such as cross-validation (see \sect{crossval}).  Such t-tests assume that the distributions being studied are Gaussian. However, as \cite{jd06} warns, results can be highly non-Gaussian when the presence of one or more outliers skews the distribution of the results. Thus calculations performed by such tests using Gaussian assumptions should be avoided.

After reviewing a wide range of comparisons methods, \cite{jd06} advocates the use of the 1945 Wilcoxon~\cite{wc45} signed-rank test that compares the ranks for the positive and negative differences (ignoring the signs). Writing five years earlier, \cite{kitc01} commented that the Wilcoxon test has its limitations, specifically that the sample sizes must be the same to be compared by the Wilcoxon test. Demsar's report offers the same conclusion. To fix this problem, \cite{jd06} augments Wilcoxon with the Friedman test.

One test not studied by \cite{jd06} is Mann and Whitney's 1947 modification ~\cite{mw47} to Wilcoxon rank-sum test (proposed along with his signed-rank test). We prefer this test since:
\bi
\item
The Mann-Whitney U test does not require that the sample sizes are the same.
So, in a single U test, a learner $L_1$ can be compared to all its rivals. 
\item
The U test does not require any post-processing (such as the Friedman test) to conclude if the median rank of one population (the results of learner $L_1$)
is greater than, equal to, or less than the median rank of another (the results of learner $L_2,L_3,..,L_x$).  In our specific case, we will be applying the U-test to a discretization method/learner pair, although all other aspects remain the same.
\ei

\textit{Non-parametric tests} such as the U test proposed by Mann and Whitney~\cite{mw47} mitigate the outlier problem. The U test uses \textit{ranks}, not precise numeric values. For example, if method $A$ generates $N_1=5$ values \{5,7,2,0,4\} and method $B$ generates $N_2=6$ values \{4,8,2,3,6,7\}, then these sort as follows:

\begin{figure}[!ht]
\begin{center}
{\small \ssp
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c}
Samples& A & A & B & B & A & B & A & B & A & B & B\\
Values & 0 & 2 & 2 & 3 & 4 & 4 & 5 & 6 & 7 & 7 & 8\\
\end{tabular}}\end{center}
\caption{Sorted Values of Method $A$ and Method $B$}
\label{fig:sortedunranked}
\normalsize \dbsp
\end{figure}

On ranking, averages are used when values are the same:
\begin{figure}[!ht]
\begin{center}
{\small \ssp
\begin{tabular}{c|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c}
Samples& A&  A  &B&  B&  A & B  &A&  B&  A&  B & B\\
Values&  0  &2  &2&  3&  4 & 4  &5&  6&  7&  7 & 8\\
Ranks&   1 &2.5&2.5 &4& 5.5&5.5 &7&  8& 9.5&9.5& 11\\
\end{tabular}}\end{center}
\caption{Sorted, Ranked Values of Method $A$ and Method $B$}
\label{fig:sortedranked}
\normalsize \dbsp
\end{figure}

Note that, when ranked in this manner, the largest value (8 in this case) gets the same rank even if it was ten to a hundred times larger. Because of this, such rank tests are less susceptible to large outliers.

\fig{mw} shows the U test for the two treatments $A$ and $B$ discussed in \fig{sortedunranked} and \fig{sortedranked}. The test concludes that these methods are not statistically different (at the 95\% significance level). As defined in \fig{mw}, this test counts the $wins$, $ties$, and $losses$ for $A$ and $B$ (where $A$ and $B$ are single or groups of methods).  In most cases, we will seek the method which \textit{wins} most.  
\newpage

\begin{figure}[!ht]
\begin{tabular}{|p{.95\linewidth}|}\hline
\footnotesize
The sum and median of A's ranks is
\[\begin{array}{ccl}
sum_A &=& 1 + 2.5 + 5.5 + 7 + 9.5 = 25.5\\
median_A& =&5.5
\end{array}\]
and the sum and median of B's ranks is
\[\begin{array}{ccl}
sum_B&=& 2.5 + 4 + 5.5 + 8 + 9.5 + 11 = 40.5\\
median_B&=& 6.75
\end{array}\]
The $U$ statistic is calculated from 
\mbox{$U_x=sum_x-(N_x(N_x+1))/2$}:
\[\begin{array}{c}
U_A = 25.5 - 5*6/2 = 10.5\\
U_B = 40.5 - 6*7/2 = 19.5
\end{array}\]
These can be converted to a Z-curve using:
\[
\begin{array}{rclcl}
\mu&= &(N_1N_2)/2&=&516.4\\
\sigma & = & \sqrt{\frac{N_1N_2(N_1 + N_2 + 1)}{12}}&=&5.477\\
Z_A & = & (U_A - \mu)/\sigma&=&-0.82\\
Z_B & = & (U_B - \mu)/\sigma&=&0.82\\
\end{array}
\]
(Note that $Z_A$ and $Z_B$ have the same absolute value.
In all case, these will be the same, with opposite signs.)

If $abs(Z) < 1.96$ then the samples $A$ and $B$ have the same median rankings (at
the 95\% significance level). In this case, we add one to both $ties_A$ \& $ties_B$.
most cases of this work (accuracy, pd, balance, precision), \textit{higher} values are better since we are comparing errors. Hence:
\bi
\item
If $median_A > median_B$ add 1 to both $wins_A$ \& $losses_B$.
\item
Else if $median_A < median_B$ add 1 to both $losses_A$ \& $wins_B$.
\item
Else, add 1 to both $ties_A$ \& $ties_B$. 
\ei
\\\hline
\end{tabular}
\caption{An example of the Mann-Whitney U test.}\label{fig:mw}
\normalsize
\end{figure}
\clearpage

\ssp
