\dbsp
Chapter \ref{discretization} describes a variety of data mining preprocessing methods that are used to convert continuous or numeric data, with potentially unlimited possible values, into a finite set of nominal values. 

Section \ref{gen-disc} describes the general concepts of discretization.  \sect{EWD}, \sect{EFD}, and \sect{binlog} describe a few simple discretization methods. Section \ref{fi} describes entropy-based approach to discretization. Section \ref{pkid} describes proportional k-interval discretization. \sect{WPKID} describes an update to PKID to handle small data sets, while \sect{NDD} describes Non-Disjoint Discretization.  \sect{WNDD} describes how the creation of WPKID provided a modification to Non-Disjoint Discretization to get the benefits of decreased error rates in small data sets.  We briefly discuss why we don't discuss in detail other discretization methods provided in some of the related papers on the subject in \sect{otherdisc}. Section \ref{discT} describes the contribution of this thesis, discretization using a randomized binary search tree as the basic storage and organizing data structure.

\ssp

\section{General Discretization}
\label{gen-disc}

\dbsp
Data from the real world is collected in a variety of forms.  Nominal data, such as a choice from the limited set of possible eye colors {blue, green, brown, grey}, usually describe qualitative values that can not easily be numerically described.  Ordinal or discrete data, such as a score from a set {1, 2,..., 5} as used to rate service in a hotel or restaurant, have relationships such as "better" or "worse" between their vales, yet because these relationships can not be quantified such data are typically treated as or in similar fashion to nominal values.  Numeric or quantitative values, such as the number of inches of rainfall this year or month, can take on an unlimited number of values.  \fig{unsorted} illustrates two such continuous attributes from a previously mentioned data set.

\begin{figure}[!ht]%[!t]
\label{fig:unsorted}
\begin{center}
\small \ssp
\begin{tabular}{|c|cccccccccccccc|}\cline{1-15}
Instance& 		1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14\\\hline
temperature&	85& 80& 83& 70& 68& 65& 64& 72& 69& 75& 75& 72& 81& 71\\\hline
humidity&		85& 90& 86& 96& 80& 70& 65& 95& 70& 80& 70& 90& 75& 91\\\hline
play&		no& no& yes& yes& yes& no& yes& no& yes& yes& yes& yes& yes& no\\\hline
%\cline{1-15}
\end{tabular}
\end{center}
\caption{The Continuous Attribute Values, Unsorted, of the WEATHER Data Set}
\end{figure}

\normalsize \dbsp

Yet, while a variety of data types occur, and while many learners are often quite happy to deal with numeric, nominal, and discrete data, there are problems that may arise as a result of this mixed data approach.  One instance where this can be easily illustrated is in decision tree induction.  Selection of a numeric attribute as the root of the tree may seem to be a very good decision from the stand point that while many branches will be created from that root, many of those branches may contain only one or two instances and most are very likely to be pure.  As a result, the tree would be quickly induced, but would result mostly in a "lookup table" for class decision based on previous values \cite{det02}.  If the training data is not representative, the training data contains noise, or a data value in the training examples that normally is representative of one class instead takes on a different class value and is induced into the tree, the created decision tree could then perform very poorly.  Thus, using a continuous value when inducing trees may not be wise and should be avoided.  This idea can be carried over into various learners, including the Na\"{i}ve Bayes Classifier, where the assumption of a normal distribution may be very incorrect for some data sets and leaving this data in continuous form may result in an erroneous classification concept.

As a result of the threat to the accuracy and thus usability of the classifiers when continuous data is used, a method of preprocessing these values to make them usable is frequently part of the learning task.  \textit{Data discretization} involves converting the possibly infinite, usually sparse values of a continuous, numeric attribute into a finite set of ordinal values. This is usually accomplished by associating several continuous to a single discrete value.  Generally, discretization transitions a quantitative attribute $X_{i}$ to a qualitative, representative attribute $X^{*}_{i}$.  It does so by associating each value of $X^{*}_{i}$ to a range or interval of values in $X_{i}$ \cite{yw03}.  The values of $X_{i}^{*}$ are then used to replace the values of $X_{i}$ found in the original data file. The resulting discrete data for each attribute is then used in place of the continuous values when the data is provided to the classifier.

Discretization can generally be described as a process of assigning data attribute instances to bins or buckets that they fit in according to their value or some other score.  The general concept for discretization as a binning process is dividing up each instance of an attribute to be discretized into a number distinct buckets or bins.  The number of bins is most often a user-defined, arbitrary value; however, some methods use more advanced techniques to determine an ideal number of bins to use for the values while others use the user-defined value as a starting point and expand or contract the number of bins that are actually used based upon the number of data instances being placed in the bins.  Each bin or bucket is assigned a range of the attribute values to contain, and discretization occurs when the values that fall within a particular bucket or bin are replaced by identifier for the bucket into which they fall.

While discretization as a process can be described generally as converting a large continuous range of data into a set of finite possible values by associating chunks or ranges of the original data with a single value in the discrete set, it is a very varied field in terms of the type of methodologies that are used to perform this association.  As a result, discretization is often discussed in terms of at least three different axes.  The axis discussed must often is \textit{supervised vs. unsupervised} \cite{fw2,det02,dou95}. Two other axes of frequent discussion are \textit{global vs. local}, and \textit{dynamic vs. static} \cite{dou95, det02}.  A fourth axis is also sometime discussed, considering \textit{top-down or bottom-up} construction of the discretization structure\cite{det02}.

Some discretization methods construct their discretization structure without using the class attribute of the instance while making the determination of where in the discretization structure the attribute instance belongs \cite{fw2, det02, dou95}.  This form of discretization allows for some very simple methods of discretization, including several binning methods, and is called \textit{unsupervised discretization}.  However, a potential weaknesses exists in that two data ranges of the discretization structure in the unsupervised discretization method may have some overlap one way or another in regard to attributes with the same class attribute value being on both sides of the range division or \textit{cut point}.  If the discretization method had some knowledge of the class attribute or use of the class attribute, the cut points could be adjusted so that the ranges are more accurate and values of the same class reside within the same range rather than being split in two.  Methods making use of the class attribute as part of the decision about how a value should be placed in the discretization structure are referred to as \textit{supervised discretization } methods \cite{fw2, dou95, det02}.  

Some classifiers include a method of discretization as part of their internal structure, including the C.45 decision tree learner \cite{dou95}.  These methods employ discretization on a subset of the data that falls into a particular part of the learning method, for example branch of a decision tree.  The data in this case is not discretized as a whole, but rather particular local instances of interest are discretized if their attribute is used as a cut point. This typically learner-internal method of discretization is called \textit{local discretization} \cite{dou95, det02}.    Opposite to this is the idea of batch or \textit{global discretization}.  These methods of discretization transform all the instances of the data set as part of a single operation.  Such methods are often run as external components in the learning task, such as a separate script that then provides data to the learner or even calls the learner on the discretized data.

\textit{Static discretization} involves discretization based upon some user provided parameter \textit{k} to determine the number of subranges created or cut points found in the data.  The method then performs a pass over the data and finds appropriate points at which to split that data into \textit{k} ranges.  It treats each attribute independently, splitting each into its own subranges accordingly \cite{dou95}.  While the ranges themselves are obviously not determined ahead of time, a fixed, predetermined number of intervals will be derived from the data.  \textit{Dynamic discretization} involves performing the discretization operation using a metric to compare various possible numbers of cut point locations, allowing \textit{k} to take on numerous values and using the value which scores best on the metric in order to perform the final discretization.

Finally, discretization can be discussed in terms of the approach used to create the discretization structure.  Some methods start by sorting the data of the attribute being discretized and treating each instance as a cut point.  It then progresses through this data and "merges" instances and groups of instances by removing the cut points between them according to some metric. When some stop point has been reached or no more merges can occur, the substitution for values occurs.  Such an approach is said to be \textit{bottom-up discretization} \cite{det02}, as it starts directly with the data to be discretized with no framework already in place around it and treating each item as an individual to be split apart.  Alternatively, discretization can begin with a single range for all the values of the continuous data attribute and use some approach by which to decide additional points at which to split the range.  This approach is called \textit{top-down discretization} \cite{det02} and involves starting with the large frame of the entire range and breaking it into smaller pieces until a stopping condition is met.

Many different methods of discretization exist and others are still being created.  The rest of this Chapter will discuss some of the commonly used discretization methods, provide information about some of the state-of-the-art methods, and share the new discretization method we have created.  The "temperature" attribute of the WEATHER data set has been provided in sorted form in \fig{sorted} in order to provide for illustration of future methods

\begin{figure}[!ht]%[!t]
\label{fig:sorted}
\begin{center}
\small \ssp
\begin{tabular}{|c|cccccccccccccc|}\cline{1-15}
Instance& 		7& 6& 5& 9& 4& 14& 12& 8& 10& 11& 2& 13& 3& 1\\\hline
temperature&	64& 65& 68& 69& 70& 71& 72& 72& 75& 75& 80& 81& 83& 85\\\hline
play&		yes& no& yes& yes& yes& no& yes& no& yes& yes& no& yes& yes& no\\\hline
%\cline{1-15}
\end{tabular}
\end{center}
\caption{The "temperature" Attribute Values, Sorted, of the WEATHER Data Set}
\end{figure}

\normalsize \dbsp

\ssp

\section{Equal Width Discretization (EWD)}
\label{EWD}

\dbsp

Equal Width Discretization, also called Equal Interval Width Discretization \cite{dou95}, Equal Interval Discretization , Fixed k-Interval Discretization \cite{yw01}, or EWD, is a binning method considered to be the simplest form of discretization \cite{dou95}.  EWD involves determining the minimum and maximum values of the data attribute to be discretized, and then dividing the continuous range contained by $[\textit{minval}, \textit{maxval}]$ into \textit{k} distinct continuous subranges of size $z = \frac{maxval-minval}{k}$ where the first subrange would contain the values in the range $minval \leq x < z$, the second subrange would contain values in the range $z \leq x < 2z$, etc.  The final subrange would contain values in the range $(k-l)z \leq x \leq maxval$.  According to \cite{yw01}, \textit{k} is most often set to be either 5 or 10.  

As an example of how this method works, consider setting \textit{k}=5 and processing the data from \fig{sorted}.  This method would identify a minimum value of 64 and a maximum value of 85.  Calculating $z~=~\frac{min-max}{k}~=~\frac{64-85}{5}~= ~4.2$.  Using this result, we derive the ranges and their contents as seen in \fig{k5EWD}

\begin{figure}[!ht]
\small \ssp
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}\cline{1-6}
\textit{Range}& 	[64, 68.2)& [68.2, 72.4)& [72.4, 76.6)& [76.6, 80.8)& [80.8,85]\\\hline
\textit{Values}&	64&	69&	75&	80&	81\\
	&		65& 	70&	75&	&		83\\
	&		68&   71& 	&		&		85\\
	&		&		72& 	&		&		  \\
	&		&		72& 	&		&		  \\
\cline{1-6}
\end{tabular}
\end{center}
\caption{A Sample of EWD as Run on the "temperature" Attribute of the WEATHER Data Set with \textit{k}=5}
\label{fig:k5EWD}
\end{figure}

\normalsize \dbsp

This method may endure problems because of uneven distribution of instances; some subranges may contain a large number or a majority of the instances, while others may contain very few or no instances at all \cite{fw2}.  This is illustrated in \fig{k5EWD}, where the range $68.2 \leq x < 72.4$ contains 5 instances - over one third of the instances in the original data - while the range $76.6 \leq x < 80.8$ contains only one instance from the data set.  Additionally, outliers have been found to be capable of drastically skewing the initial range and the subranges that would result from dividing it \cite{dou95}.

For our experiment, we will use a Equal Width Discretization method we have called tenbins, which sets $\textit{k}=10$.  This method is implemented using a script created in the GAWK programming language.  The source code for our implementation can be found in Appendix \ref{a:tenbins}.

\ssp

\section{Equal Frequency Discretization(EFD)}
\label{EFD}

\dbsp

Equal Frequency Discretization (EFD) is similar to Equal Width Discretization, except that the user-defined value \textit{k} is used to delineate the number of instances that should fall in each of the variably-sized ranges.  Each of \textit{n} data instance is read and the ranges computed by counting across the values so that a break occurs after each $\frac{n}{k}$ instance.  The final interval may be slightly smaller or larger depending on the size of the dataset and how the rounding of $\frac{n}{k}$ is handled.  
Binning using this method is referred to as histogram binning, because plotting the number of values in each subspace against the number of values in each other subspace will result in a flat histogram \cite{fw2}.  

As an example of this method, again consider the temperature data and allow \textit{k}=5.  Starting from the original 14 instances, computing the number of instances per interval would result in an interval size of $\frac{14}{5}$ or 2.8 instances.  To allow for a countable number of instances, we will round up to 3.   In such a case, the instances might be split as illustrated in \fig{k5EFD}.

\begin{figure}[!ht]
\small \ssp
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}\cline{1-6}
\textit{Instances}& 	3& 3& 3& 3& 2\\\hline
\textit{Values}&	64&	69&	72&	75&	83\\
					&	65&	70&	72&	80&	85\\
					&	68&	71&	75&	81&	\\
\cline{1-6}
\end{tabular}
\end{center}
\caption{A Sample of EFD as Run on the "temperature" Attribute of the WEATHER Data Set with \textit{k}=5}
\label{fig:k5EFD}
\end{figure}

\normalsize \dbsp

This method may result in instances with the same numeric value ending up in different bins or values that have the same class and small value differences being placed in different bins \cite{fw2, dou95}.  In the example provided by \fig{k5EFD}, the two instance values of 75 occur in two separate bins due to the size limitations on each bin.

\ssp

\section{Bin Logging}
\label{binlog}
\dbsp

Bin Logging is a special case of Equal Width Discretization where the value \textit{k}, is set to the maximum of 1 and $2\cdot\log(\textit{l})$ (\textit{max}(1, $2\cdot\log(\textit{1})))$, where \textit{l} is the number of distinct - unique - values of the attribute to be discretized.  The Bin Logging discretization method was derived from a histogram binning method in the statistics program called S-Plus \cite{dou95, hhw03}.  This was one of the methods that was used by Dougherty et al. that showed the accuracy of Na\"{i}ve Bayes Classifiers benefited from the use of discretization \cite{dou95}.

%Results for a sample run of bin logging against the "temperature" data from the %WEATHER data set can be found in \fig{binlogs}.  I was going to generate this %but there appears to be an error in our implementation.   If binlog is applied %to 12, then there should be 2 bins, with each of the two bins having a size of %10.5.  However, if our current implementation is used, it groups the value 75 %with the first bin.  This does not make sense, since it should be on the upper %side of the split point that would occur at 74.5

%\begin{figure}[h]
%\small
%\begin{center}
%\begin{tabular}{|c|c|c|}\cline{1-3}
%\textit{Range}& 	[64, 74.5)&	[74.5, 85]\\\hline
%\textit{Values}&	64&	75\\
%	&					65& 	75\\
%	&					68&   80\\
%	&					69&	81\\
%	&					70&	83\\
%	&					71&	85\\
%	&					72&	\\
%	&					72&	\\
%\cline{1-3}
%\end{tabular}
%\end{center}
%\caption{A Sample of Bin Logging as Run on the "temperature" Attribute of the WEATHER Data Set}
%\label{fig:binlogs}
%\end{figure}

\ssp

\section{Entropy-based Discretization}
\label{fi}
\dbsp

As discussed previously, entropy is a measure of the randomness of class distribution in a split of data.  The more instances of each class that exist in a given split, the higher the entropy.  On the other hand, if a single class is the majority or all of a split, the entropy measure is much lower, and can reach 0 if only one class is contained in a split.  The lower the entropy of a split, the higher the likelihood of a correct decision about the classification of a data point found in that split.

Examining this effect in decision trees, Fayyad and Irani proposed a method of discretization based on the entropy measure \cite{fi92}.  Called a entropy minimization heuristic, this approach to discretization begins by first sorting all the instance values of an attribute in ascending order.  It then identifies potential \textit{cut points} by examining the class of each instance; if the class value changes between two instances values, then the midpoint between those values can be considered as a potential cut point.  After completing a list of potential cut points, it then evaluates each potential cut point using \eq{entropy}.  The cut point that minimizes the result of \eq{entropy} is the "best" split and used to separate the initial set of values into two subsets.  The process is then repeated recursively on each of the halves and continues until the algorithm reaches a stopping criterion.  

The stopping criterion for method the method in \cite{fi92} is the \textit{minimum description length principle} (MDLP) \cite{det02, dou95, fw2, hhw03}.  This principle believes that the best theory is the one that minimizes the size of the theory and any information necessary to note the exceptions to the theory \cite{fw2}.  It will stop discretization only if the best split at the given level results in a lower information gain than the amount of information it would cost to encode the theory being created by the new split.  This can be calculated using \eq{mdlp}, where \textit{N} is the number of instances, \textit{c} is the number of classes, \textit{E} is the measure of entropy for the existing split, $E_{1}$ and $E_{2}$ measure the entropy in the proposed splits, with $c_{1}$ and $c_{2}$ as the number of classes in the proposed splits.

\begin{equation}
\textit{gain} < \frac{\log(N-1)}{N} + \frac{\log(3^{c}-2)-cE+c_{1}E_{1}+c_{2}E_{2}}{N}
\label{eq:mdlp}
\end{equation}

If the \textit{gain} calculated with \eq{gain} is less than the resulting calculation, no new intervals are created from the split currently being considered.

While entropy-based discretization was originally developed for decision tree learners (see \sect{decision-tree}), it has been shown to be successful in working with Na\"{i}ve Bayes classifiers \cite{dou95}.  Several authors \cite{ao04, yw01} note that because of its initial purpose for use with decision trees, the entropy-minimization approach typically creates nominal value attributes with few values (few splits with many instances), which while useful in the decision tree environment may not be necessary for the Na\"{i}ve bayes classifier, which does not suffer from the fragmentation and over-fitting issues that cause problems for the decision trees.  However, the creation of a few attributes has not been shown to decrease this method's performance; rather, in \cite{dou95} found the entropy-minimization method to be the most method which most improved the accuracy of Na\"{i}ve Bayes classifiers.

In attempting to run the entropy based method over the temperature data from the WEATHER dataset, the entropy-minimization heuristic found that all the data should be part of one range and did not split it beyond that range.  

For our experiment, we will use the \textit{WEKA} implementation of the entropy-minimization heuristic, a supervised, attribute filter called \textit{Discretize}.  It will be called from a BASH command-line program that can be found in \app{fayyadIranisource} and was provided by Dr. Tim Menzies of West Virginia University's Lane Department of Computer Science (tim@menzies.us).

\ssp

\section{Proportional k-Interval Discretization}
\label{pkid}
\dbsp
Proportional k-Interval Discretization, or PKID, is a method of discretization proposed specifically for use with a Na\"{i}ve Bayes Classifier \cite{yw01}.  It seeks to find a balance between \textit{discretization bias} and \textit{discretization variance}.  

Classification or probability estimation bias is error that occurs as a result of a flaw in the learned classification strategy that causes the classifier to incorrectly classify instances \cite{yw03-2}.  Discretization bias is defined as the effect that applying a particular discretization method to data for the classifier has on that classifier's classification bias.  As interval sizes in discretization methods grow large, they contain less information about each individual value they contain, leading to a higher discretization bias \cite{yw01, yw03-2}.   A higher discretization bias leads to higher bias in classification bias.

Classification variance is error that arises from random variation in training data and random behavior of the algorithm used in learning.  Classification variance can thus be said to be a measure of how sensitive an algorithm is to changes in the training data \cite{yw03-2}.  Discretization variance is the effect that a discretization method has on the classification variance of an algorithm to which its discretized data is provided.  Discretization variance is lowered by increasing interval size in order to ensure that the interval contains a large number of instances.  

Obviously there is a degree of conflict between minimizing discretization variance and discretization bias.  Variance reduction would require fewer intervals, each large and containing many instances.  On the other hand, bias reduction requires more intervals in order to maintain more distinguishing information about the values contained in each interval.  This thus creates the issue of a "trade-off" between bias and variance, where increasing or decreasing one has the opposite affect on the other.  

In proposing Proportional k-Interval Discretization(PKID) for Na\"{i}ve Bayes Classifiers, \cite{yw01} proposes to provide equality to both discretization bias and variance.  The proposed method is to function similar to Equal Interval Discretization (see \sect{EWD}); however, rather than having a fixed number of intervals be created (such as k=5 or k=10 in EWD), the method instead determines the number of intervals given the number of available training instances. Assuming there are \textit{N} training instances for which there are known attribute values, PKID creates \textit{s} = $\sqrt{N}$ intervals, each which should contain approximately \textit{t} = $\sqrt{N}$ instances.  These rules are restated in \eq{PKID}, where $N$ is the number of training instances, $s$ is the number of intervals to place them in, and $t$ is the number of training instances per interval.  By providing a nearly identical number of intervals and instances per interval, PKID provides for equal consideration of size and number of intervals and thus to both discretization bias and variance.  

\begin{center}
\begin{eqnarray}\label{eq:PKID}
\nonumber s \times t = N \\
s = t
\end{eqnarray}
\end{center}

PKID has certain special rules by which it performs the discretization.  First, it only deals with known values for numeric attributes - unknown or missing values are simply ignored.  Second, all identical values are kept in a single interval rather than being split among intervals to maintain the $sqrt{N}$ size; thus, the actual size of each interval may vary slightly from the $sqrt{N}$ proposed size depending on the number of identical values of an attribute.  Finally, the standard size of an interval should be $\lfloor\sqrt{N}\rfloor$ (an integer value).  Larger size is only allowed when identical values of an attribute occur in the interval, or if that interval is the last interval, which according to \cite{yw01} have size between $\lfloor\sqrt{N}\rfloor$ and $\lfloor\sqrt{N}\rfloor$.  As part of the final rule, a statement is made that no interval may be smaller than $\lfloor\sqrt{N}\rfloor$.  However, in testing the implementation provided in the \textit{WEKA} learning toolkit, an interval may be smaller if duplicate values occur that prevent enough instances from being available to fall into that interval.  

In the initial experiment with PKID and Na\"{i}ve Bayes classifiers, it was found to have a lower error rate than EWD and the method proposed by Fayyad and Irani dealing with entropy (see \sect{fi}).  It also reacts to increases in the number of examples available during training, something not done by either of the other methods studied.

A sample run of the PKID algorithm on the temperature attribute of the WEATHER data set can be found in \fig{PKIDs}.  Note that for the 14 instances in that case, $\sqrt{n}=\sqrt{14}=3.742$.  However, the output from PKID produces only 3 intervals, each with four or five instances; this number of intervals is smaller than expected but is probably caused by the duplicate values of 72 and 75 found in the data.

\begin{figure}[!ht]
\small \ssp
\begin{center}
\begin{tabular}{|c|c|c|c|}\cline{1-4}
\textit{Range}&	(-infinity, 70.5)& [70.5, 77.5)&	[77.5, infinity)\\\hline
\textit{Instances}& 	5& 5& 4\\\hline
\textit{Values}&	64&	71&	80\\
					&	65&	72&	81\\
					&	68&	72&	83\\
					&	69&	75&	85\\
					&	70&	75&	\\
\cline{1-4}
\end{tabular}
\end{center}
\caption{A Sample of PKID as Run on the "temperature" Attribute of the WEATHER Data Set}
\label{fig:PKIDs}
\normalsize
\end{figure}

\normalsize \dbsp

While PKID has been shown to perform well with large data sets, it has also been shown to perform sub-optimally when faced with learning from a small training data set \cite{yw03-2}.  It has proposed that this is due to the equal weighting of discretization bias and variance reduction; where as in small data sets discretization variance reduction may be more important.

For our experiment, we will use the \textit{WEKA} implementation of PKID, a filter called \textit{PKIDiscretize}.  It will be called from a BASH command-line program that can be found in \app{pkidsource}.

\ssp


\section{Weighted Proportional k-Interval Discretization (WPKID)}
\label{WPKID}

\dbsp

A solution for the PKID problem of sub-optimal performance on small training data set was
proposed in the WPKID algorithm. For smaller datasets, discretization variance reduction has a bigger impact on a \nbc performance than discretization bias \cite{yw03-2}. WPKID weights discretization variance reduction more than bias for small training sets. This is accomplished by setting a minimum interval size of at least \textit{m} instances so that the probability estimation always has a certain degree of reliability. 

Going back to the equations for PKID, WPKID replaces \eq{PKID} with \eq{WPKID}.

\begin{center}
\begin{eqnarray}\label{eq:WPKID}
\nonumber s \times t = N \\
s - m = t
\end{eqnarray}
\end{center}

Where m = 30, because, according to \cite{yw03-2} it is commonly assumed the minimum sample space from which reliable statistical inferences should be drawn.  This new approach should remove the disadvantage on smaller data sets by establishing a bias-variance trade-off that is appropriately adjusted to the size of the available training data.

An implementation of this algorithm was unavailable for public testing when this thesis was completed.

\ssp
  
\section{Non-Disjoint Discretization (NDD)}
\label{NDD}

\dbsp

In suggesting Non-Disjoint Discretization, \cite{yw02, yw02-02} note that when substituting a range ($a$, $b$] for a continuous value $v$, more reliable results are obtained if $v$ is closer to the middle of the interval than if the value false close to either boundary.  As a result, NDD creates a series of overlapping intervals for each attribute, locating a value of $v_i$ toward the middle of the corresponding interval ($a_i$, $b_i$].

NDD uses a sizing strategy similar to the strategy employed by PKID; specifically, it assigns $s$ - the number of intervals - and $t$ - the number of training instances per interval - according to \eq{PKID}.  It then identifies \textit{$t^{'}$ atomic intervals}, ($a^{'}_{1}$, $b^{'}_{1}$], ($a^{'}_{2}$, $b^{'}_{2}$], ..., ($a^{'}_{t}$, $b^{'}_{t}$], each of size \textit{$s^{'}$}.  \eq{NDD} describes the equations used to determine the size and number of atomic intervals.

\begin{center}
\begin{eqnarray}\label{eq:NDD}
\nonumber s^{'} = \frac{s}{\alpha}\\
s^{'} * t^{'} = N
\end{eqnarray}
\end{center}

Where $\alpha$ is any odd number and does not vary between intervals.  \cite{yw02} suggests that $\alpha = 3$.

An interval is formed from each set of three consecutive \textit{atomic intervals} such that the interval \textit{k}, where $1 \leq k \leq t^{'}-2$, denoted by ($a_{k}$, $b_{k}$] satisfies $a_{k}=a^{'}_{k}$ and $b_{k}=b^{'}_{k+2}$.

With the atomic intervals, when a value $v$ is seen, it is assigned to the interval ($a^{'}_{i-1}$, $b^{'}_{i+1}$] where i is the index of the atomic interval which contains $v$. This means $v$ will always fall towards the middle of the interval, except when $i = 1$ in which case $v$ is assigned to the interval ($a^{'}_{1}$, $b^{'}_{3}$], and when $i = t^{'}$ in which case $v$ is assigned to ($a^{'}_{t^{'}-2}$, $b^{'}_{t^{'}}$]. Grouping atomic intervals to form discretization values produces overlapping intervals, resulting in the name non-disjoint.

An implementation of this algorithm was unavailable for public use when this thesis was completed.  As a result, this method is not compared to the other methods described herein.

\ssp

\section{Weighted Non-Disjoint Discretization (WNDD)}
\label{WNDD}

\dbsp

WNDD \cite{yw02} is performed the same way as NDD, creating atomic intervals so that values will occur, in most cases, toward the middle of the interval used to replace them.  However, WNDD adds the additional restriction of the minimum interval size imposed by WPKID, specifically \eq{WPKID}. As explained before, the minimum interval size parameter prevents the discretization algorithm from forming intervals with too few examples for reliable probability estimation.

An implementation of this algorithm has not yet been released for use, and thus this method was not tested as part of our comparison.

\ssp

\section{Other Methods}
\label{otherdisc}

\dbsp

While other methods of discretization do exist, we have listed and explained the ones commonly cited methods in some of the more recent examinations of discretization for Na\"{i}ve Bayes Classifiers.  Other methods such as \textit{Iterative Discretization}, \textit{Fuzzy Discretization}, and \textit{Lazy Discretization} are noted in \cite{yw02}; however, each is shown to perform worse (slower, less accurately) than the methods discussed herein.  Additionally, their implementations are not widely available and they could not be tested as part of this experiment.

\ssp

\section{DiscTree Algorithm}
\label{discT}

\dbsp

In the course of reviewing other methods of discretization, we discovered that many of the methods involved sorting the values of a continuous data attribute from smallest to largest as one of the number of steps in deciding to which subrange of the data an individual instance belongs.  This approach often involves using a binary sorting method for deciding the ordering of data.  As the sorting approach adds additional steps on top of actually constructing the discretization structure, we wondered if there wasn't an approach that could sort the data as it built the discretization structure, thus removing an individual step.

An additional interest was whether the structure we would identify for our discretization method could be simple to explain to others.  Discretization methods are often not easy to explain due to their complicated structures or the methods they use to establish the continuous ranges related to the individual discrete values created.   We wanted to identify a structure that could be easily understood and explained to people who might use it.  We decided to base our discretization method on the general data structure of a tree; more specifically, we proposed to implement a discretization method using a randomized binary search tree as the discretization method's underlying data structure.

To explain our choice more clearly, we'll explain the general tree data structure and build from it up to the randomized binary search tree and our method.

\ssp

\subsection{Trees}
\label{trees}

\dbsp

A commonly discussed data structure in computer science is that of a \textit{tree}. We seek here to explain the basic premises of that data structure so to explain how we used a type of tree for our work.  Full explanations of the tree data structure can be found in a variety of sources, including books, articles, and on the Internet.  If you would like to review a comprehensive discussion of trees, we recommend a review of \cite[1085-1093]{clrs01}.

A tree, by definition, is a connected, acyclic, undirected graph \cite{clrs01}.  Every two points in the graph are connected by one unique path.  A point, or node, in the tree can be connected to any number of other nodes in the tree so long as their connection does not create  a circular path from one node to the other and back to the first.  \fig{simpletree} illustrates a simple tree with nodes and the paths between them.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.50]{simpletree.png}
\end{center}
\caption{A Simple Tree}
\label{fig:simpletree}
\end{figure}

A tree can be structured in such a way that it becomes "rooted" \cite{clrs01}.  This occurs when one node is distinguished from the others as a starting point from which all other points can be discussed relatively.  This starting point is referred to as the \textit{root} or \textit{root node} of the tree, and is referred to by the character \textit{r}.  A parameter of the tree \textit{T} that is \textit{root$\left(T\right)$} which should store the current root node of the tree.  \fig{rootedtree} is an example of a rooted tree, the node labeled $7$ as the root.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.50]{rootedtree.png}
\end{center}
\caption{A Rooted Tree}
\label{fig:rootedtree}
\end{figure}

As nodes are discussed relatively to \textit{r}, relationships can be said to exist between the nodes.  Consider a node \textit{x} in a tree with root \textit{r}.  A node \textit{y} that exists on the path from \textit{r} to \textit{x}, denoted (r,x), is called an \textit{ancestor} of \textit{x}. For example, in \fig{rootedtree} the node labeled $9$ is an ancestor of the node labeled $8$. Alternatively, \textit{x} can be referred to as a \textit{descendant} of \textit{y} ( and \textit{y} a descendant of \textit{x}).  In \fig{rootedtree}, the node labeled $9$ is also a descendent of the node labeled $7$.  If node \textit{y} is the ancestor immediately preceding node \textit{x} in the tree - that is, there x and y share an edge then node \textit{y} is said to be the \textit{parent} of \textit{x}.  The node labeled $7$ is also the parent of the node labeled $9$ in \fig{rootedtree}.  In such a situation, node \textit{x} is also referred to as a \textit{child} of node \textit{y}.  Thus the node labeled $9$ is a child of the node labeled $7$.    If two nodes share a parent, then they may be called sibling nodes, such as the nodes labeled $12$, $17$, and $9$ in \fig{rootedtree}.  Any node \textit{x} at the end of a path from the root, (r,x), and having no children is said to be an \textit{external} or \textit{leaf} node, such as the node labeled $2$.  Any node with children is called an \textit{internal} node, such as the node labeled $17$ in \fig{rootedtree}.

Trees can be said to contain \textit{subtrees}.  A \textit{subtree} is a branch of a tree that itself is a tree.  For example, consider a tree rooted at \textit{r} that has children \textit{x} and \textit{y}, each with a variety of children and other descendants.  The \textit{subtree rooted at x} would be the tree containing the descendants of \textit{x} with \textit{x} at the root, while the subtree rooted at \textit{y} would contain all the descendants of \textit{y} with \textit{y} as its root.  Again consider \fig{rootedtree}.  In that tree, we could discuss the subtree rooted at the node labeled $9$, for example.

Parameters should exist for implementations of the tree data structure that store the parent for a given node \textit{x} (we will call this parameter \textit{parent$\left(x\right)$}).  Calling \textit{parent}($9$) would return the node labeled $7$.   Child nodes of a node \textit{x} can be stored in a variety of ways to maintain ordering including the use of arrays or matrices. We are not specifically interested in this abstract level of trees in this thesis we will not discuss the specific implementations of these methods.

\ssp

\subsection{Binary Trees}
\label{BT}

\dbsp

A special case of traditional trees are called Binary Trees. A recursive definition describes how they function.  Each Binary Tree contains either no nodes - and is thus, in fact, the \textit{empty} or \textit{null} tree - or contains three distinct sets of nodes: a root node, a left subtree that is also a binary tree that meets this definition, and a right subtree that is also a binary tree that meets this definition.  Children of a binary tree that are themselves empty or null trees are said to be \textit{missing} or \textit{absent}.  A sample binary tree can be found in \fig{binaryT}.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.50]{binarytree.png}
\end{center}
\caption{Illustrations of a Binary Tree.}
\label{fig:binaryT}
\end{figure}

In regard to the child node(s) of a root node in the binary tree that are not absent, they must exist either as the left child or the right child of the root node.  That is, if the root node has only one child, that child node could be either a left or right child, but is either one or the other.  When the root node has two children, one node is distinguished as the left child node and the other as the right child node.  Parameters should exist for each node \textit{x} such that \textit{leftchild$\left(x\right)$} returns the node that is the left child of \textit{x} and \textit{rightchild$\left(x\right)$} returns the right child of \textit{x}.  For example, from \fig{binaryT}, \textit{leftchild}(7) would return the node labeled $17$, while \textit{rightchild}(7) would return the node labeled $9$.  If node \textit{x} does not have either child, the parameter for that child would have the value NULL; this would be the case with \textit{leftchild}(34) and \textit{rightchild}(34), each of which would return NULL.

A relevant concept in binary trees is the concept of \textit{completeness} or \textit{fullness}.  A \textit{complete} or \textit{full} binary tree is one in which each node is either a leaf node or has exactly two child nodes.  If one node in the tree (including the root node) has only one child, then the binary tree is not considered to be complete.  For example, \fig{binaryT} does not display a complete tree because the node labeled $72$ has a left child but no right child.

While the position of a value in the binary tree does not denote anything in regard to its relative value to other nodes (and thus the right child of a node could be positioned there with no known relation to the left child of that node), the concept of left and right subtrees are very important for a related branch of computer science data structures, the binary search tree.

\ssp

\subsection{Binary Search Trees}
\label{BST}

\dbsp

\textit{Binary Search Trees} (BSTs) uses the organizational structure of a binary tree to create a data structure that can allow for quick and easy sorting and searching of the data inserted into it. The binary search tree maintains the \textit{binary search tree property}.  For each node created in the tree, a key value is assigned to the node, such that for a value \textit{v} to be placed in the tree, a node \textit{d} is created for which \textit{key$\left(d\right)$}~=~\textit{v}.  Suppose there existed a binary search tree rooted at \textit{x}, and \textit{y} is identified as the left child of \textit{x}.  Then the \textit{key$\left(y\right)$~$\leq$~key$\left(x\right)$}.  
Suppose instead that \textit{y} is a right child of \textit{x}.  Then the \textit{key$\left(y\right)$~$\geq$~key$\left(x\right)$}.  An example of a Binary Search Tree can be found in \fig{BST} - this is, in fact, the binary tree in \fig{binaryT} reorganized to meet the binary search tree property.

\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.50]{binarysearchtree.png}
\end{center}
\caption{Illustration of a Binary Search Trees}
\label{fig:BST}
\end{figure}

A BST can be walked in numerous orders in order to retrieve the key values it stores.  An \textit{in-order tree walk} or \textit{in-order traversal} visits each node in the tree, printing the root of each subtree of the tree after it has printed the key values of left subtree from that root and before it prints the key values of the right subtree.  An \textit{pre-order tree walk} prints the key of the root of each subtree prior to printing the values of the left and then right subtrees.  Finally, a \textit{post-order tree walk} prints the key of the root of a subtree after the key values for both the left and then the right subtree of that root are printed.  Pseudo code for an in-order walk is provided in \fig{inorder}.

\begin{figure}[!ht]
\ssp
\lstset{language=Python}
\lstset{backgroundcolor=\color{listinggray}}
\lstset{frameround=tttt}
\lstset{basicstyle=\scriptsize}
\lstset{showstringspaces=false, showspaces=false, showtabs=false}
\begin{center}
\begin{lstlisting}[frame=trBL]{}
Function inOrderTreeWalk(x):
	if x != NULL then
		inOrderTreeWalk(leftchild(x))
		print key(x)
		inOrderTreeWalk(rightchild(x))
\end{lstlisting}
\end{center}
\caption{In-Order Walk Pseudo Code}
\label{fig:inorder}
\dbsp
\end{figure}

Because of their organization based on key value, the binary search tree provides a very useful mechanism for searching trees.  In addition to a general search routine, whose pseudo code can be found in \fig{BSTSearch}, the binary search tree can easily find the minimum and maximum values of the data set (the leftmost and rightmost leaf nodes respectively), and also determine the preceding and succeeding key values of a node.  The function names for determining the minimum, maximum, predecessor, or successor of the a node \textit{z} are \textit{treeMinimum$\left(z\right)$}, \textit{treeMaximum$\left(z\right)$}, \textit{treePredecessor$\left(z\right)$}, and \textit{treeSuccessor$\left(z\right)$} respectively.


\begin{figure}[!ht]
\ssp
\lstset{language=Python}
\lstset{backgroundcolor=\color{listinggray}}
\lstset{frameround=tttt}
\lstset{basicstyle=\scriptsize}
\lstset{showstringspaces=false, showspaces=false, showtabs=false}
\begin{center}
\begin{lstlisting}[frame=trBL]{}
Function treeSearch(x, k):
	if x != NULL OR k = key(x) then
		return x
	if k < key(x)
		searchTree(leftchild(x),k)
	else
		searchTree(rightchild(x),k)
\end{lstlisting}
\end{center}
\caption{BST Search Pseudo Code}
\label{fig:BSTSearch}
\dbsp
\end{figure}

Two of the most important functions of a Binary Search Tree are the INSERT and DELETE functions.  As one might imagine, INSERT places a new value into the binary search tree after assigning it a key.  DELETE removes node with the specified key from the tree.  Both functions modify the structure of the tree but in doing so maintain the binary search tree property.  INSERT is fairly straightforward, having only one special case when the tree first node is being added to the tree. Essentially, it approaches the insertion of the new node by allowing the node to fall all the way down into the tree to become a leaf node and either a left or right child node to a node that currently exists in the tree (unless the tree is empty, in which case the node is added as the root of the tree).  Pseudo code for a BST INSERT can be found in \fig{BSTINS}, where \textit{T} is the tree (BST) into which node \textit{z} is being inserted.

\begin{figure}[!ht]
\ssp
\lstset{language=Python}
\lstset{backgroundcolor=\color{listinggray}}
\lstset{frameround=tttt}
\lstset{basicstyle=\scriptsize}
\lstset{showstringspaces=false, showspaces=false, showtabs=false}
\begin{center}
\begin{lstlisting}[frame=trBL]{}
Function treeInsert(T, z):
	y = NULL
	x = root[T]
	while x != NULL:
		y=x
		if key(z) < key(x) then
			x=leftchild(x)
		else
			x=rightchild(x)
	parent(z)=y
	if y == NULL then *** SPECIAL CASE, TREE EMPTY ***
		root(T) = z
	else
		if key(z) < key(y) then
			leftchild(x)=z
		else
			rightchild(x)=z
\end{lstlisting}
\end{center}
\caption{BST INSERT Pseudo Code}
\label{fig:BSTINS}
\dbsp
\end{figure}

While INSERT is straightforward, DELETE presents a few difficulties.  Specifically, the algorithm must handle the deletion of a node that may have children and must ensure that those children are reconnected back to the tree when their parent node is removed.  Essentially, we are presented with three possible situations to handle with DELETE when we wish to remove node \textit{z}:
\bi
\item 
\textit{z} is a leaf node and has no children.  In this case, DELETE is simple - we simply remove the node \textit{z} and its parent's reference to it as a child.
\item
\textit{z} has one child.  In this case, the \textit{parent$\left(z\right)$} has the child that corresponds to node \textit{z} set equal to the child of \textit{z} and \textit{z} is effectively spliced out of the tree.
\item
\textit{z} has two children.  In this case, the successor of \textit{z}(called node \textit{y}), is spliced out of the tree and its information is placed in the node that holds \textit{z}'s information.  
\ei

Pseudo code for the BST's DELETE algorithm can be found in \fig{BSTDEL}.

\begin{figure}[!ht]
\ssp
\lstset{language=Python}
\lstset{backgroundcolor=\color{listinggray}}
\lstset{frameround=tttt}
\lstset{basicstyle=\scriptsize}
\lstset{showstringspaces=false, showspaces=false, showtabs=false}
\begin{center}
\begin{lstlisting}[frame=trBL]{}
Function treeDelete(T, z):
	if leftchild(z) == NULL OR righttchild(z) == NULL then
		y=z
	else
		y=treeSuccessor(z)
	if leftchild(y} != NULL then
		x=leftchild(y)
	else
		x=rightchild(y)
	if x != NULL then
		parent(x)=parent(y)
	if parent(y) == NULL then
		root(T)=x
	else
		if y == leftchild(parent(y)) then
			leftchild(parent(y))=x
		else
			rightchild(parent(y))=x
	if y != z then
		key(z)=key(y)
		copy node y's data into node z
	return y
\end{lstlisting}
\end{center}
\caption{BST DELETE Pseudo Code}
\label{fig:BSTDEL}
\dbsp
\end{figure}

While binary search trees are useful for their organization and ease of search, they can suffer from an instability issue caused by insertion in which instead of growing a full binary search tree, the insert begins with either the maximum value or minimum value at the root and only builds a right or left subtree.  Such a tree would be very \textit{unbalanced}, where a \textit{balanced} tree, with equal or near equal height in both subtrees, is desired to minimize search times.  One proposed solution to help balance the tree is the \textit{randomzied binary search tree}.

\ssp
\subsection{Randomized Binary Search Trees}
\label{RBST}
\dbsp

Randomized Binary Search Trees (RBSTs) take their name from the randomization of the INSERT function used to add new data to the tree.  In adding randomization to this approach, we allow that, given an existing tree that contains \textit{n} instances, that the current instance \textit{x} has a $\frac{1}{\textit{n}}$ chance of becoming the root node of the tree; what is more, even if the node is not selected to be the root node of the overall tree, this random insert is attempted at the root of each subtree that \textit{x} belongs in, with a chance to insert at that root equal to $\frac{1}{\textit{size of subtree}}$.   If the new node does not ever get selected as a root of the tree or its subtrees, then it is simply added as a node in the tree as it would be using the INSERT function described in \fig{BSTINS}.  

Randomized Binary Search Tree provide some protection against unbalanced problems that can occur as a result of doing a BST insert on sorted data or on data that starts with the minimum or maximum value of the tree.  Because of the random nature of the tree, it is expected that the tree should be somewhat balanced or at least not so heavily skewed as the ordinary BST when provided with the data that causes the deficiency.  It is because of this protection that we select to use the randomized binary search tree as our base data structure when creating the DiscTree algorithm.

Our implementation of the RBST insert is based upon the idea of always inserting a new node as a leaf of the tree and "bubbling up" the inserted value to its decided place in the tree using rotations of keys in the tree \cite{sedgewick02}.  This approach reorganizes the tree without the complications of trying to split and rejoin the tree as has been proposed in \cite{mr98}.  Pseudo code for our implementation can be found in the portion of \fig{RBSTINS}.  Function \textit{rbstinsert} draws a random number to determine whether to insert the new value at the root of the current subtree; if it decides in favor of inserting it at the root, it calls function \textit{insertR} to insert at the root of the current subtree by rotating the new value up from its initial insertion point as a leaf node to its place as the root of the decided-upon subtree.  If the new node is not found to be the root of a subtree, it is inserted simply as a leaf node as it would in the binary search tree.  


\begin{figure}[!ht]
\ssp
\lstset{language=Python}
\lstset{backgroundcolor=\color{listinggray}}
\lstset{frameround=tttt}
\lstset{basicstyle=\scriptsize}
\lstset{showstringspaces=false, showspaces=false, showtabs=false}
\begin{center}
\begin{lstlisting}[frame=trBL]{}
Function insertR(h, x):
	if h == NULL then
		return new Node(x)
	if(x.key() == h.item.key())
		updateNode(h)
	if(x.key() < h.item.key())
		leftchild(h) = RBSTInsert(leftchild(h), x)
		h = rotateR(h)
	else
		rightchild(h) = RBSTInsert(rightchild(h), x)
		h = rotateL(h)
	return h

Function rbstinsert(h, x):
	if h == NULLthen
		return newNode(x)
	if(x.key() == h.item.key())
		updateNode(h)
	if( rand() * h.all() < 1.0)
		return insertR(h, x)
	else
		if(x.key() < h.item.key())
			rbstinsert(leftchild(h), x)
		else
			rbstinsert(rightchild(h), x)
	h = insertT(h, x)

Function rotateR(h):
	x = leftchild(h)
	leftchild(h) = rightchild(x)
	rightchild(x) = h
	return x

Function rotateL(h):
	x = rightchild(h)
	rightchild(h) = leftchild(x)
	leftchild(x) = h
	return x

Function newNode(x):
	y.item = x
	leftchild(y) = NULL
	rightchild(y) = NULL
	y.count = 1
	//initialize other values as necessary
	return y

Function updateNode(h):
	h.count = h.count + 1
	return h

\end{lstlisting}
\end{center}
\caption{RBST INSERT Functions Pseudo Code}
\label{fig:RBSTINS}
\dbsp
\end{figure}

\ssp

\subsection{DiscTree}
\label{DiscTree}

\dbsp

The DiscTree Algorithm makes use of the organization of the randomized binary search tree by using such trees to create a storage and discretization structure for each attribute.  For each of the attributes of the data set, a separate RBST is created and each value from the data set is inserted into its attribute's RBST.  At specific intervals, the tree is garbage-collected to ensure that it does not grow boundlessly.  Additionally, as the DiscTree algorithm becomes aware of additional data - beyond the current expected training size - it increases the allowable size of that attribute's tree to allow for more possible nodes in the tree after a garbage-collect.  The specific details of the algorithm will be explained here.

The DiscTree algorithm performs discretization in two passes.  The first pass builds randomized binary search trees for each (numeric) attribute in the provided data set.  In order to build the tree, each instance is inserted into the tree in the form of a node that contains the information depicted in figure \textit{DTNode}.  Repeated values that already exist in the tree increment the counters of the existing node; the repeated values can also result in moving the node up in the tree if it is decided during the \textit{rbstinsert} of the value that it should be higher in the tree than it currently is.  Missing values (depicted in our input as question marks (?))are ignored; it is expected that the classifier will handle any such values.  

During insertion, a garbage collection mechanism may be called.  Garbage collection occurs, if the tree has reached or exceeded its maximum allowable size, after every 35 non-missing instances are read.  This is value we have chosen to use and have not examined a particular justification for.  It works for the data we are dealing with but might be an area of future concentration..  Garbage collection occurs as follows:  Tree nodes are "visited" in Breadth-First Search \cite{clrs01} order.  Each visited node is counted, and when the count meets the maximum size limit, any additional nodes are then pruned from the tree.  This Breadth-First approach is taken to help preserve the target of a balanced/full search tree.  

The tree begins with a maximum allowable size of 7 nodes.  This size is allowed to grow as the tree is provided with more and more training instances.  Specifically, after each 75 nodes of training data, we allow the tree size to grow by a power of 2 such that, if the initial number of allowable nodes is initially 7, then the allowable number of nodes $7+2^{(2+1)}=7+2^3=7+8=15$.  More generally, the tree size increases as seen in \eq{newsize}, allowing that \textit{maxsize} is equal to the current maximum tree size and $2^i$ is the current largest power of 2 that can be subtracted from \textit{maxsize} without a negative result.   

\begin{center}
\begin{equation}
\textit{maxsize}=\textit{maxsize}+2^{(i+1)}
\label{eq:newsize}
\end{equation}
\end{center}

Which, when applied to the value 15, would result in:
\begin{center}
\begin{eqnarray}
\nonumber \textit{maxsize} = 15 + 2^{(3+1)} = 15+2^4 = 15+16 = 31
\end{eqnarray}
\end{center}
Again, 75 instances was a value we chose without any experimental testing to determine an optimum value.  This may be another area that could be improved upon with further study.  We have attempted some brief experiments on tree-size start points and found performance to be very similar for trees of size 7 and 15 and that those models tended to perform at about the same level.  Future work could be conducted in that area as well to determine a best starting size and growth rate.

After each attribute value of each instance is read and inserted into that attribute's RBST, the discretization method begins a second pass.  It begins it by garbage collecting any trees that are larger than their maximum allowable size.  It then determines which nodes and subtrees contain enough instances within them to be used a discretization points for the data set.  It makes this determination by examining the nodes to determine which nodes contain at least $\sqrt{N}$ instances, where \textit{N} is the number of non-unknown data values seen for the attribute.  This is akin to Webb's PKID discretization method ~\cite{yw01}, which requires each bin of their discretization method to contain at least $\sqrt{N}$.  However, beyond that justification we have identified no other reason to support the $\sqrt{N}$ instances per bin imposition; this may, like the number of instances between garbage collect and tree size, be an area where this algorithm could be improved in the future.  When the nodes and subtrees have been determined, they are substituted into the data in place of the original possible values for the data.  This is done by examining each instance again, and replacing each attribute's value in that instance with the node or subtree which most closely matches the value of the attribute value of the instance that meets the $\sqrt{N}$ requirement.  When this is done, the data is considered discretized.  As with previous examples, we provide the discretized values for the temperature attribute of the WEATHER data set.  This information is available in \fig{DiscTreeRun}

The DiscTree Algorithm as a whole can be described by the pseudo code in \fig{DiscTreePseudo}

\begin{figure}[!ht]
\ssp
\lstset{language=Python}
\lstset{backgroundcolor=\color{listinggray}}
\lstset{frameround=tttt}
\lstset{basicstyle=\scriptsize}
\lstset{showstringspaces=false, showspaces=false, showtabs=false}
\begin{center}
\begin{lstlisting}[frame=trBL]{}
Pass 1:
For each instance:
	For each attribute:
		Insert each instance's value into that  attribute's RBST
		If specified number of records seen, allow tree size to grow
		If specified number of records seen, Garbage Collect.

Pass 2:
Garbage Collect each RBST tree to ensure size requirement before discretization
For each attribute:
	Replace the attribute's value type with the list of tree nodes that meet size requirement
For each instance:
	For each attribute:
		Find the tree value that:
			(a) most closely matches the current value and 
			(b) meets size requirement
		Replace the current value with the name of the chosen node
\end{lstlisting}
\end{center}
\caption{DiscTree Algorithm Pseudo Code}
\label{fig:DiscTreePseudo}
\dbsp
\end{figure}

\dbsp

\begin{figure}[!ht]
\small \ssp
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}\cline{1-6}
\textit{Node}&	temperature\#2& temperature\#5&	temperature\#7& temperature\#9& temperature\#14\\\hline
\textit{Instances}& 	2& 3& 3& 2& 4\\\hline
\textit{Values}&	64&	68&	71&	75&	80\\
					&	65&	69&	72&	75&	81\\
					&	&		70&	72&	&		83\\
					&	&		&		&		&		85\\
\cline{1-6}
\end{tabular}
\end{center}
\caption{A Sample of the DiscTree Algorithm as Run on the "temperature" Attribute of the WEATHER Data Set}
\label{fig:DiscTreeRun}
\end{figure}

\dbsp \normalsize

We implemented the DiscTree algorithm using a GAWK script in order to implement the data processing and randomized binary search tree data structure.  The source code is located in \app{dtsc}.  

\ssp
