Data Discretization Simplified:

Randomized Binary Search Trees for Data Preprocessing

Donald Joseph Boland Jr.

Thesis submitted to the

College of Engineering and Mineral Resources

at West Virginia University in partial fulfillment of the requirements

for the degree of

Master of Science in

Computer Science

Tim Menzies, Ph.D, Chair Roy Nutter, Ph.D Cindy Tanner, M.S.

Lane Department of Computer Science and Electrical Engineering

Morgantown, West Virginia 2007

Keywords: Data Mining, Discretization, Randomized Binary Search Trees

Copyright \begin{matrix}c \\ ◯ \end{matrix} 2007 Donald Joseph Boland Jr.

Abstract

Data Discretization Simplified: Randomized Binary Search Trees for Preprocessing

Donald Joseph Boland Jr.

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

Dedication

To My Wife Kelly To My Family

Acknowledgments

ii

Contents

iii

List of Figures

iv

Chapter 1

Introduction

Today’s modern societies are built on information. Computers and the Internet can make information available quickly to anyone looking for it. More importantly, computers can process that information more quickly than many humans. They can also provide information about how best to make a decision that normally would have been made previously by a human being with imperfect knowledge built on their individual education and experience but not necessarily the best information. Computer can thus aid us in making the right decisions at the right moment using the best information available. This thesis deals with helping to refine the way computers decide which information is most pertinent and make, or help their human users make, decisions based upon it.

Chapter 1 provides background information about this thesis, specifically discussing the motivation behind the research herein, the purpose of this thesis, contributions that this thesis makes to the field of computer science and more specifically the topic area of data mining. Finally, this chapter explains the layout for the rest of this document.

Section 1.1 describes the problem that motivated this thesis, specifically discretization and the search for a simple solution that performs at about the same level as existing methods.

Section 1.2 states the purpose of the research of this thesis.

Section 1.3 states the contributions of this thesis to related research.

Section 1.4 explains the layout of the rest of this document and what can be expected in the following chapters.

1.1 Motivation

Data mining is the process of analyzing data in order to find undiscovered patterns in the data and solve real world problems [?]. It may be data about historic trends in beach erosion to help a local community determine how much sand needs dredged and replaced each year, or survey data about when people begin their Christmas shopping in order to help retailers determine the best time of year to begin setting up Christmas displays and ordering seasonal merchandise. Data about a set of tests that identify cancer might be analyzed to determine which tests are most capable of identifying the cancer and allow doctors to use these tests earlier in the cancer screening process, or data about fuel purchases or consumption analyzed and used as a basis for vendors to know how much fuel they should have on hand at a particular time of year, how often they should be restocked, and specific amounts of each fuel grade or type might be needed. Data mining can be used to analyze a vast variety of data in order to solve the problems faced by our society or provide more information to help people make the best decisions.

Real world data such as that collected for the problems above can provide a variety of issues for data miners, but one of the chief problems involved in preparing data for the learner is ensuring that data can be easily read and manipulated by the learner. One of the most common difficulties that learners have is dealing with numeric values. Most learners require data to take on a value belonging to a small, fixed set, which is often unobtainable with raw numeric values that can fall in large or infinite ranges and take on many possible values even when constrained by a range. The process of transitioning raw numeric values to a form that can be easily read and manipulated by learners is called discretization [?]. Numerous researchers report that discretization leads to better, more accurate learning, especially in Naïve Bayes Classifiers. However, they very often disagree about which method of discretization works best. Because of how useful discretization can be for classification, yet because questions remain about whether there is one best method to use, discretization will be the subject of this thesis.

1.2 Statement of Thesis

While data discretization is an important topic in data mining, it is one burdened with a vast variety of methods, most of which take on complex data structures and require a search over the entire data set to determine how a value should be discretized. We believe that there should be a simpler approach that works similarly to these methods. To that end, we have implemented a discretization method based on a randomized binary search tree as the underlying storage data structure. We contend that this method uses the properties of randomized binary search trees to avoid a search over the entire data set performing discretization and do so with a simple structure that can be understood by most. We believe that this method should have performance statistics close to or on par with other discretization methods.

1.3 Contributions

The contributions of this thesis are:

• The DiscTree algorithm that is implemented to create the DiscTree discretization method;

• A review of a variety of currently existing discretization methods; and,

• An experimental comparison of some common discretization methods against the implemented DiscTree discretization method.

A surprise finding of this comparison is that many discretization methods perform at very similar levels. *** I know you wanted something else said here but I am missing a note on what that was ***

The results of the comparison leads us to the belief that discretization is a simpler task than it is made out to be in some of the literature. The DiscTree algorithm is simple in comparison to many of the state-of-the-art methods and performs just as well as some methods that claim superiority in the field of discretization. We believe that while various methods exist for discretization and some may perform better on a specific data sets than others, that in general simple methods perform well and can be just as useful as and used in place of complex methods.

1.4 About This Document

The rest of the chapters of this thesis are laid out as follows:

Chapter 2 provides an explanation of the premise of data and how it is used in data mining. It also provides a review of various learners in data mining. It examines several possible learning methods and explains why we have chosen to use the Naïve Bayes Classifier for our experimentation with discretization methods.

Chapter 3 provides a review of common data mining discretization methods. It highlights the methods commonly found in the literature on discretization and specifically reviews the methods we will compare in our experiment.

Chapter 4 explains the experimental design used to test the variety of data discretization techniques described in Chapter 3. It also explains our methods for generating and comparing results.

Chapter 5 contains the results of the experiment, relevant tables and data plots, and a explanation of those results.

Chapter 6 explains conclusions derived from the results of the experiment. It discusses the key findings and areas of future work that could expand upon this thesis. It also provides a summary of this document.

Background: Data and Learners

Chapter 2 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ïve Bayes classifier as a test platform for discretization.

Section 2.1 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 2.2 describes the machine learning process of classification and discusses a sampling of various classifiers, including decision tree and Naïve Bayes classifiers. Section 2.3 explains our selection of a classification method for the experiments in this document and the justification for that selection.

2.1 Data and Data Mining

2.1.1 Data

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 nominal or 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 discrete data [?]. 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 numeric or continuous data, and may includes both real (decimal) and integer values [?].

Data is most often stored in files or databases. The basic unit of these storage structures is the record, or one data 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 attributes that comprise it. The attributes or 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 [9]. Another example of a set of instances can be found in Figure 2.1. 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.

Instance  Attributes  Class
outlook temperature humidity windy play
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

Figure 2.1: The WEATHER data set, with both nominal and continuous values

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.

2.1.2 Data Mining

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 data mining. More precisely, data mining is the extraction of implicit, previously unknown, and potentially useful information about data [?].

The technical basis of data mining is called machine learning [?]. 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 [?,?]. 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 [?].

2.2 Classification

Classification, also referred to as classification learning, is a type of data mining whereby a computer program called a 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 [?]. 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 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 Figure 2.1, the class attribute, play, takes on the values of yes and 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 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 [?]. The method by which the learner determines the concept it will use on future examples differs based upon the type of classification learner used. A wide variety of classification learners exist, but among the most popular are decision tree learners, rule-generating learners, and Naïve Bayes classifiers.

2.2.1 Decision Tree Learners

Decision tree learners use a method called 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 Section 3.7.1) 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 [?, ?]. 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. Figure ?? provides an example of a decision tree.

Figure 2.2: A Sample Decision Tree

An example of a decision tree learner is J48. J48 is a JAVA implementation of Quinlan’s C4.5 (version 8) algorithm [?]. 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 best split is the one that 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:

entropy(p_{1},p_{2},...,p_{n}) = −p_{1}log(p_{1}) − p_{2}log(p_{2}) − ... − p_{n}log(p_{n})  (2.1)
or

entropy(p_{1},p_{2},...,p_{n}) = −∑_{i=1}^{n} p_{i}logp_{i}

info([x,y,z]) = entropy(\frac{x}{x + y + z} , \frac{y}{x + y + z} , \frac{z}{x + y + z} )  (2.2)
gain(attribute) = info(current) − avg. info(proposed)  (2.3)

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.

Equation 2.1 defines the 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. Equation 2.2 allows the calculation of that amount of information. For example, if the leaf node contained 5 example instances, 3 of class yes and 2 of class no, then the information needed to specify the class of a new example that reached that leaf node would be:

info([3,2]) = entropy(\frac{3}{5}, \frac{2}{5}) = −\frac{3}{5} log \frac{3}{5} − \frac{2}{5} log \frac{2}{5} ≈ 0.971 bits

The information gain, defined in Equation 2.3, 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) yes instances and seven no instances. A proposed attribute value test would split the instances into three branches; one containing only seven yes instances and one noinstances, the second five yes and one no, and the third the remaining instances. The information of the original split is calculated, info([13,7]) ≈ 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 Equation 2.4:

E(attribute) = \frac{|S_{1}|}{|S|}entropy(S_{1}) + ... + \frac{|S_{n}|}{|S|}entropy(S_{n})|  (2.4)

Where S_{1} through S_{n} are the subsets created when attribute takes on n unique values and thus creates 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:

info([7,1]) ≈ 0.544 bits
info([5,1]) ≈ 0.650 bits
info([1,5]) ≈ 0.650 bits

E([7,1],[5,1],[1,5]) = \frac{8}{20} ∗ .544 + \frac{6}{20} ∗ .650 + \frac{6}{20} ∗ .650 ≈ 0.413 bits

Then the information gain for the proposed split would be:

gain(attribute) = info([13,7]) − avg. info([7,1],[5,1],[1,5]) = 0.934 bits − 0.413 bits = 0.521 bits

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 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 gain ratio [?]. 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:

gain(attribute) = 0.521 bits

info([8,6,6]) = entropy([\frac{8}{20}, \frac{6}{20}, \frac{6}{20}])

= − \frac{8}{20} log \frac{8}{20} − \frac{6}{20} log \frac{6}{20} − \frac{6}{20} log \frac{6}{20}

info([8,6,6]) ≈ 1.571 bits

gain ratio = \frac{gain((attribute))}{info([8,6,6])}= \frac{0.521 bits}{1.571 bits} ≈ 0.332 bits

(2.5)

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 overfitting 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 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.

2.2.2 Naive Bayes

Naïve Bayes classifiers are highly studied statistical method used for classification. Originally used as a straw man [?, 6] - 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ïve Bayes classifiers are called naïve because of what is called the 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ïve Bayes classifier and could result in incorrect classification of an instance. When a data set containing such relationships is used with the Naï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 [6]. This explains the repeated empirical result that, on average, Naïve Bayes classifiers perform as well as other seemingly more sophisticated schemes. For more on the Domingos and Pazzani result, see Section 2.3

A Naïve Bayes classifier is based on Bayes’ Theorem. Informally, the theorem says next = old ∗ new; in other words, what we’ll believe next is determined by how new evidence affects old beliefs. More formally:

P(H|E) = \frac{P(H)}{P(E)}∏_{i} P(E_{i}|H)  (2.6)

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).

Equation 2.6 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 Equation 2.6 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ï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 [?, ?] to use an 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:

P(H) = \frac{N(H) + m}{I + m · C}  (2.7)

Here m is a small non-zero constant (often, m = 2). Three special cases of Equation 2.7 are:

• For high frequency hypothesis in large training sets, N(H) and I are much larger than m and m · C, so Equation 2.7 simplifies to P(H) = \frac{N(H)}{I}, as one might expect.

• 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.

• For very small data sets, I is small and N(H) is even smaller. In this case, Equation 2.7 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.

The prior probability calculated in Equation 2.7 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

P(E_{i}|H) = \frac{N(f = v|H) + l · P(H)}{N(H) + l}  (2.8)

Here, l is the L-estimate, or Laplace-estimate and is set to a small constant (Yang &Webb [?, ?] recommend l = 1). Two special cases of are:

• 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 Equation 2.8 approaches \frac{N(f=v|H)}{N(H)} , as one might expect.

• In the case of very little evidence for a rare hypothesis, N(f = v|H) and N(H) are small and Equation 2.8 approaches \frac{l·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.

For numeric attributes it is common practice for Naïve Bayes classifiers to use the Gaussian probability density function [?]:

g(x) = \frac{1}{\sqrt{2π}σ} e^{− \frac{(x−μ)^{2}}{2σ^{2}}}  (2.9)

where {μ,σ} 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 ± ϵ/2, is ϵ × g(x). Since ϵ 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 kernel estimation technique [8]. 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 σ = \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ïve Bayes classifiers can also be handled using a technique called discretization, discussed in Chapter 3. This has been the topic of many studies ( [?, ?, ?, ?, 3, 11]) and has been shown to deal well with numeric attributes, as seen in [6] where a Naïve Bayes classifier using a simple method of discretization outperformed both so-called state-of-the-art classification methods and a Naïve Bayes classifier using the Gaussian approach.

Naï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.

2.2.3 Other Classification Methods

1-R

One of the simplest learners developed was 1-R [?, 10]. 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 2.2.3:

For each a t t r i b u t e :
For each v a l u e of t h a t a t t r i b u t e , make a r u l e as f o l l o w s :
Count how o f t e n each c l a s s a p p e a r s
Determine t h e most f r e q u e n t c l a s s
Make a r u l e such t h a t a s s i g n s t h e given v a l u e t h e most f r e q u e n t c l a s s
C a l c u l a t e t h e e r r o r r a t e of t h e r u l e s f o r t h e a t t r i b u t e
Compare t h e e r r o r r a t e s , d e t e r m i n e which a t t r i b u t e has t h e s m a l l e s t e r r o r r a t e
Choose t h e a t t r i b u t e whose r u l e s had t h e s m a l l e s t e r r o r r a t e
[figure]

Figure 2.3: 1-R Pseudo-Code

The 1-R classifier is very simple and handles both missing values and continuous attributes. Continuous attributes are handled using discretization, discussed in Chapter 3. It specifically uses a method similar to EWD, defined in Section 3.2. Missing values are dealt with by creating a branch in the one-level decision tree for a 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 [?].

2.3 Classifier Selection

A variety of literature exists comparing many of these classifier methods and how discretization works for them. In [11], three discretization methods are used on both the C4.5 decision tree induction algorithm and the Naïve Bayes Classifier. The authors of that paper find that each form of discretization they tested improved the performance of the Naïve Bayes Classifier in at least some cases. Specifically:

Our Experiments reveal that all discretization methods for the Naive-Bayes classifier lead to a large average increase in accuracy.

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ï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, [6] compared the performance of the Naï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ï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ïve Bayes that uses Equal Width Discretization (see Section 3.2) as a preprocessor to handle any continuous data instances. It found that the simple Naï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ï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ï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ïve Bayes classifier. The most modern discretization method used in our experiment, aside from the DiscTree method implementation, is the PKID discretization method (see Section 3.5). This method was derived with the specific intent of it being used with the Naï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ïve Bayes as well, specifically in [?,?,?,?,?]. 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ï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ïve Bayes classifier will provide the best comparison point due to its use to derive the most recent compared results [?] and is the learner where the benefits of discretization have been most analyzed and best displayed, as seen in [11]. While it does make assumptions about the data attributes being independent, we feel that based on [6] 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ïve Bayes classifier will provide an acceptable base for our experimental comparison of discretization methods.

Discretization

Chapter 3 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 3.1 describes the general purpose of discretization. Section 3.2, Section 3.3, and Section 3.4 describe a few simple discretization methods based on the binning concept. Section 3.5 describes proportional k-interval discretization. Section 3.6 describes entropy-based approach to discretization. Section 3.7 describes the contribution of this thesis, discretization using a randomized binary search tree as the basic storage and organizing data structure. [?]

3.1 General Discretization

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.

Figure 3.1 illustrates two such continuous attributes from a previously mentioned data set.

Instance  1 2 3 4 5 6 7 8 9 10 11 12 13 14
temperature 85 80 83 70 68 65 64 72 69 75 75 72 81 71
humidity 85 90 86 96 80 70 65 95 70 80 70 90 75 91
play  no no yes yes yes no yes no yes yes yes yes yes no

Figure 3.1: The Continuous Attribute Values, Unsorted, of the WEATHER Data Set

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 [9]. 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ï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. 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} [?]. 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 supervised vs. unsupervised [?, 9, 11]. Two other axes of frequent discussion are global vs. local, and dynamic vs. static [9, 11]. A fourth axis is also sometime discussed, considering top-down or bottom-up construction of the discretization structure [9].

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 [?,9,11]. This form of discretization allows for some very simple methods of discretization, including several binning methods, and is called 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 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 supervised discretization methods [?, 9, 11].

Some classifiers include a method of discretization as part of their internal structure, including the C.45 decision tree learner [11]. 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 local discretization [9, 11]. Opposite to this is the idea of batch or 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.

Static discretization involves discretization based upon some user provided parameter 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 k ranges. It treats each attribute independently, splitting each into its own subranges accordingly [11]. While the ranges themselves are obviously not determined ahead of time, a fixed, predetermined number of intervals will be derived from the data. Dynamic discretization involves performing the discretization operation using a metric to compare various possible numbers of cut point locations, allowing 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 bottom-up discretization [9], 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 top-down discretization [9] 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 Figure 3.1 in order to provide for illustration of future methods

Instance  7 6 5 9 4 14 12 8 10 11 2 13 3 1
temperature 64 65 68 69 70 71 72 72 75 75 80 81 83 85
play  yes no yes yes yes no yes no yes yes no yes yes no

Figure 3.2: The ”temperature” Attribute Values, Sorted, of the WEATHER Data Set

3.2 Equal Width Discretization (EWD)

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

As an example of how this method works, consider setting k=5 and processing the data from Figure 3.1. 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 Figure 3.3

Range [64, 68.2) [68.2, 72.4) [72.4, 76.6) [76.6, 80.8) [80.8,85]
Values  64  69  75  80  81
65  70  75  83
68  71  85

72 72

Figure 3.3: A Sample of EWD as Run on the ”temperature” Attribute of the WEATHER Data Set with k=5

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 [?]. This is illustrated in Figure 3.3, where the range 68.2 ≤ x < 72.4 contains 5 instances - over one third of the instances in the original data - while the range 76.6 ≤ 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 [11].

For our experiment, we will use a Equal Width Discretization method we have called tenbins, which sets 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 C.

3.3 Equal Frequency Discretization(EFD)

Equal Frequency Discretization (EFD) is similar to Equal Width Discretization, except that the user-defined value k is used to delineate the number of instances that should fall in each of the variably-sized ranges. Each of 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 [?].

As an example of this method, again consider the temperature data and allow 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 Figure 3.4.

Instances 3 3 3 3 2
Values 64 69 72 75 83
65 70 72 80 85
68 71 75 81

Figure 3.4: A Sample of EFD as Run on the ”temperature” Attribute of the WEATHER Data Set with k=5

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 [?,11]. In the example provided by Figure 3.4, the two instance values of 75 occur in two separate bins due to the size limitations on each bin.

3.4 Bin Logging

Bin Logging is a special case of Equal Width Discretization where the value k, is set to the maximum of 1 and 2·log(l) (max(1, 2·log(1))), where 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 [3, 11]. This was one of the methods that was used by Dougherty et al. that showed the accuracy of Naïve Bayes Classifiers benefited from the use of discretization [11].

3.5 Proportional k-Interval Discretization

Proportional k-Interval Discretization, or PKID, is a method of discretization proposed specifically for use with a Naïve Bayes Classifier [?]. It seeks to find a balance between discretization bias and 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 [?]. 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 [?, ?]. 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 [?]. 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ïve Bayes Classifiers, [?] proposes to provide equality to both discretization bias and variance. The proposed method is to function similar to Equal Interval Discretization (see Section 3.2); 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 N training instances for which there are known attribute values, PKID creates \sqrt{N} intervals, each which should contain approximately \sqrt{N} instances. It is in this way that PKID provides for equal consideration of size and number of intervals and thus to both discretization bias and variance.

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 sqrtN size; thus, the actual size of each interval may vary slightly from the sqrtN proposed size depending on the number of identical values of an attribute. Finally, the standard size of an interval should be ⌊\sqrt{n}⌋ (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 [?] have size between ⌊\sqrt{N}⌋ and ⌊\sqrt{N}⌋. As part of the final rule, a statement is made that no interval may be smaller than ⌊\sqrt{N}⌋. However, in testing the implementation provided in the 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ï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 Section 3.6). 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 Figure 3.5. 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.

For our experiment, we will use the WEKA implementation of PKID, a filter called PKIDiscretize. It will be called from a BASH command-line program that can be found in Appendix D.

Range (-infinity, 70.5) [70.5, 77.5) [77.5, infinity)
Instances  5  5  4
Values  64  71  80
65  72  81
68  72  83
69  75  85
70  75

Figure 3.5: A Sample of PKID as Run on the ”temperature” Attribute of the WEATHER Data Set

3.6 Entropy-based Discretization

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 [7]. 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 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 Equation 2.1. The cut point that minimizes the result of Equation 2.1 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 [7] is the minimum description length principle (MDLP) [?, 3, 9, 11]. 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 [?]. 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 Equation 3.1, where N is the number of instances, c is the number of classes, 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.

gain < \frac{log(N − 1)}{N} + \frac{log(3^{c}− 2) − cE + c_{1}E_{1}+ c_{2}E_{2}}{N}  (3.1)

If the gain calculated with Equation 2.3 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 Section 2.2.1), it has been shown to be successful in working with Naïve Bayes classifiers [11]. Several authors [?,?] note that because of its initial purpose for use with decision trees, the entropyminimization 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ï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 [11] found the entropy-minimization method to be the most method which most improved the accuracy of Naï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 WEKA implementation of the entropy-minimization heuristic, a supervised, attribute filter called Discretize. It will be called from a BASH command-line program that can be found in Appendix E and was provided by Dr. Tim Menzies of West Virginia University’s Lane Department of Computer Science (tim@menzies.us).

3.7 Disctree

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.

3.7.1 Trees

A commonly discussed data structure in computer science is that of a 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 [?, 1085-1093].

A tree, by definition, is a connected, acyclic, undirected graph [?]. 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.

A tree can be structured in such a way that it becomes ”rooted” [?]. 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 root or root node of the tree, and is referred to by the character r. A parameter of the tree T that is root(T)which should store the current root node of the tree.

As nodes are discussed relatively to r, relationships can be said to exist between the nodes. Consider a node x in a tree with root r. A node y that exists on the path from r to x, denoted (r,x), is called an ancestor of x. Alternatively, x can be referred to as a descendant of y ( and y a descendant of x). If node y is the ancestor immediately preceding node x in the tree - that is, there x and y share an edge then node y is said to be the parent of x. In such a situation, node x is also referred to as a child of node y. If two nodes share a parent, then they may be called sibling nodes. Any node x at the end of a path from the root, (r,x), and having no children is said to be an external or leaf node. Any node with children is called an internal node. Parameters should exist for implementations of the tree data structure that store the parent for a given node x (we will call this parameter parent(x)). Child nodes of a node x can be stored in a variety of ways to maintain ordering, and as we are not specifically interested in this abstract level of trees in this thesis we will not discuss their specific implementations.

Trees can be said to contain subtrees. A subtree is a branch of a tree that itself is a tree. For example, consider a tree rooted at r that has children x and y, each with a variety of children and other descendants. The subtree rooted at x would be the tree containing the descendants of x with x at the root, while the subtree rooted at y would contain all the descendants of y with y as its root.

3.7.2 Binary Trees

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 empty or 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.

Figure 3.6: Illustrations of Binary Trees.

Children of a binary tree that are themselves empty or null trees are said to be missing or absent.

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 x such that leftchild(x) returns the node that is the left child of x and rightchild(x)returns the right child of x. If node x does not have either child, the parameter for that child would have the value NULL.

Sample binary trees can be found in Figure 3.6.

A relevant concept in binary trees is the concept of completeness or fullness. A complete or 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.

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.

3.7.3 Binary Search Trees

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 binary search tree property. For each node created in the tree, a key value is assigned to the node, such that for a value v to be placed in the tree, a node d is created for which key(d) = v. Suppose there existed a binary search tree rooted at x, and y is identified as the left child of x. Then the key(y)≤ key(x). Suppose instead that y is a right child of x. Then the key(y)≥ key(x). An example of Binary Search Trees can be found in Figure 3.7.

Figure 3.7: Illustrations of Binary Search Trees

A BST can be walked in numerous orders in order to retrieve the key values it stores. An inorder tree walk or 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 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 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 Figure ??.

F u n c t i o n inOrderTreeWalk\ l e f t (x\ r i g h t ) :
i f x \neq NULL t h e n
inOrderTreeWalk\ l e f t (\ t e x t i t { l e f t c h i l d }\ l e f t (x\ r i g h t )\ r i g h t )
p r i n t \ t e x t i t {key}\ l e f t \[\ t e x t i t {x}\ r i g h t \]
inOrderTreeWalk\ l e f t (\ t e x t i t { r i g h t c h i l d }\ l e f t (x\ r i g h t )\ r i g h t )
[figure]

Figure 3.8: In-Order Walk Pseudo Code

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 Figure ??, 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 z are treeMinimum(z), treeMaximum(z), treePredecessor(z), and treeSuccessor(z)respectively.

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

F u n c t i o n t r e e S e a r c h \ l e f t (x , k\ r i g h t ) :
i f x \neq NULL or k = \ t e x t i t {key\ l e f t (x\ r i g h t )} t h e n
return x
i f k < key\ l e f t (x\ r i g h t )
s e a r c h T r e e\ l e f t (\ t e x t i t { l e f t c h i l d }\ l e f t (x\ r i g h t ) ,k\ r i g h t )

e l s e

s e a r c h T r e e\ l e f t (\ t e x t i t { r i g h t c h i l d }\ l e f t (x\ r i g h t ) ,k\ r i g h t )
[figure]

Figure 3.9: BST Search Pseudo Code

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 Figure 3.10, where T is the tree (BST) into which node z is being inserted.

F u n c t i o n t r e e I n s e r t (T, z ) :
y = NULL
x = r o o t [T]
while x \neq NULL:
y=x
i f \ t e x t i t {key\ l e f t ( z\ r i g h t )} < \ t e x t i t {key\ l e f t (x\ r i g h t )} t h e n
x=\ t e x t i t { l e f t c h i l d \ l e f t (x\ r i g h t )}

e l s e

x=\ t e x t i t { r i g h t c h i l d \ l e f t (x\ r i g h t )}
\ t e x t i t { p a r e n t \ l e f t ( z\ r i g h t ) ˜ = ˜ y}
i f y == NULL t h e n ∗∗∗ SPECIAL CASE, TREE EMPTY ∗∗∗
\ t e x t i t { r o o t \ l e f t (T\ r i g h t ) = z

e l s e

i f \ t e x t i t {key\ l e f t ( z\ r i g h t )} < \ t e x t i t {key\ l e f t (y\ r i g h t )} t h e n
\ t e x t i t { l e f t c h i l d \ l e f t (x\ r i g h t )}= z

e l s e

\ t e x t i t { r i g h t c h i l d \ l e f t (x\ r i g h t )}= z
[figure]

Figure 3.10: BST INSERT Pseudo Code

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 z:

• z is a leaf node and has no children. In this case, DELETE is simple - we simply remove the node z and its parent’s reference to it as a child.

• z has one child. In this case, the parent(z) has the child that corresponds to node z set equal to the child of z and z is effectively spliced out of the tree.

• z has two children. In this case, the successor of z(called node y), is spliced out of the tree and its information is placed in the node that holds z’s information.

Pseudo code for the BST’s DELETE algorithm can be found in Figure 3.11.

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 unbalanced, where a 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 randomzied binary search tree.

3.7.4 Randomized Binary Search Trees

*** NEED BIBLIOGRAPHICAL INFO OF JAVA BOOK ***

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 n instances, that the current instance x has a \frac{1}{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 x belongs in, with a chance to insert at that root equal to \frac{1}{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 Figure 3.10.

F u n c t i o n t r e e D e l e t e (T, z ) :
i f \ t e x t i t { l e f t c h i l d \ l e f t ( z\ r i g h t )} == NULL OR \ t e x t i t { r i g h t t c h i l d \ l e f t ( z\ r i g h t )} == NULL t h e n
y˜ = ˜ z

e l s e

y˜ = ˜ t r e e S u c c e s s o r \ l e f t ( z\ r i g h t )
i f \ t e x t i t { l e f t c h i l d \ l e f t (y\ r i g h t )} \neq NULL t h e n
x˜ = ˜ \t e x t i t { l e f t c h i l d \ l e f t (y\ r i g h t )}

e l s e

x˜ = ˜ \t e x t i t { r i g h t c h i l d \ l e f t (y\ r i g h t )}
i f \ t e x t i t {x} \neq NULL t h e n
\ t e x t i t { p a r e n t \ l e f t (x\ r i g h t ) } ˜ = ˜ \t e x t i t { p a r e n t \ l e f t (y\ r i g h t )}
i f \ t e x t i t { p a r e n t \ l e f t (y\ r i g h t )} == NULL t h e n
\ t e x t i t { r o o t \ l e f t (T\ r i g h t ) } ˜ = ˜ x

e l s e

i f y == \ t e x t i t { l e f t c h i l d \ l e f t ( p a r e n t \ l e f t (y\ r i g h t )\ r i g h t )} t h e n
\ t e x t i t { l e f t c h i l d \ l e f t ( p a r e n t \ l e f t (y\ r i g h t )\ r i g h t ) } ˜ = ˜ x

e l s e

\ t e x t i t { r i g h t c h i l d \ l e f t ( p a r e n t \ l e f t (y\ r i g h t )\ r i g h t ) } ˜ = ˜ x
i f y \neq z t h e n
\ t e x t i t {key\ l e f t ( z\ r i g h t ) } ˜ = ˜ \t e x t i t {key\ l e f t (y\ r i g h t )}
copy node y ’ s d a t a i n t o node z
r e t u r n y
[figure]

Figure 3.11: BST DELETE Pseudo Code

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. This approach reorganizes the tree without the complications of trying to split and rejoin the tree as has been proposed in [13]. Our implementation can be found in the portion of Appendix ?? noted as bst.awk. Function 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 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.

3.7.5 DiscTree

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 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 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 [?] 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 Equation 3.2, allowing that maxsize is equal to the current maximum tree size and 2^{i} is the current largest power of 2 that can be subtracted from maxsize without a negative result.

maxsize= maxsize+ 2^{(}i + 1)  (3.2)

Which, when applied to the value 15, would result in:

maxsize= 15 + 2^{3+1} = 15 + 2^{4} = 15 + 16 = 31

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 n is the number of non-unknown data values seen for the attribute. This is akin to Webb’s PKID discretization method [?], 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{/textitn}requirement. When this is done, the data is considered discretized.

The DiscTree Algorithm as a whole can be described by the pseudo code in Figure ??

Pass 1 :
For each i n s t a n c e :
For each a t t r i b u t e :
I n s e r t each i n s t a n c e ’ s v a l u e i n t o t h a t a t t r i b u t e ’ s RBST
I f s p e c i f i e d number of r e c o r d s seen , allow t r e e s i z e t o grow
I f s p e c i f i e d number of r e c o r d s seen , Garbage C o l l e c t .
Pass 2 :
Garbage C o l l e c t each RBST t r e e t o e n s u r e s i z e r e q u i r e m e n t b e f o r e d i s c r e t i z a t i o n
For each a t t r i b u t e :
Replace t h e a t t r i b u t e ’ s v a l u e t y p e with t h e l i s t of t r e e nodes t h a t meet t h e s i z e r e q u i r e m e n t
For each i n s t a n c e :
For each a t t r i b u t e :
Find t h e t r e e v a l u e t h a t most c l o s e l y matches t h e c u r r e n t v a l u e and meets s i z e r e q u i r e m e n t
Replace t h e c u r r e n t v a l u e with t h e name of t h e chosen node
[figure]

Figure 3.12: DiscTree Algorithm Pseudo Code

As with previous examples, we provide the following discretized values for the temperature attribute of the WEATHER data set

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 for the script is located in Appendix A.

Node temperature#2 temperature#5 temperature#7 temperature#9 temperature#14
Instances  2  3  3  2  4
Values  64  68  71  75  80
65  69  72  75  81
70  72  83

85

Figure 3.13: A Sample of the DiscTree Algorithm as Run on the ”temperature” Attribute of the WEATHER Data Set

Experiment

Chapter 4 describes the experimental approach used to compare the discretization techniques. Section 4.1 explains the data used to perform this comparison. Section 4.2 explains the cross-validation method used to generate the results from the learner. Section 4.3 explains the different measures used to compare the effects of discretization on the Naïve Bayes classifier. Section 4.4 explains the Mann-Whitney approach used to compare the results of each discretization method against its competitors.

4.1 Test Data

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 25 data sets from the UCI machine learning repository [1] 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 Figure 4.1

Data Set  Instances Attributes Numeric Nominal Classes
hayes-roth  132  5  1  4  3
iris  150  4  4  0  3
hepatitis  155  19  6  13  2
1ine  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

Figure 4.1: 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.

4.2 Cross-Validation

Cross-validation is a statistical method that divides data into a fixed n folds, or partitions, of approximately the same size [?], for example, three folds each containing one-third of the data. The first fold is then used for classifier testing, while the remaining n-1 folds are used for classifier training. The process is repeated so that each of the n folds is used for testing. The resulting process is known as nfold cross-validation. This process can be combined with 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 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 [?,8,9]. 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 [?] 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 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ïve Bayes Classifier to complete a ten x ten fold cross validation. The results are then compared as described in 4.4.

It is worth noting that one of the results we seek to compare against is that from [?]. The authors of that paper, and in all of their other papers comparing discretization methods that we are aware of ( [?, ?, ?, ?]), 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.

The source code for our cross-validation method was written as a BASH script and is available for review in Appendix B.

4.3 Classifier Performance Measurement

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

Allow that 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 Figure 4.2.

instance of desired class?

no  yes
identified as no  A (true negative) B (false negative)
desired class? yes  C (false positive) D (true positive)

Figure 4.2: A Tabular Explanation of A, B, C, & D

The following measures can be calculated from the values of 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%.

accuracy = acc = \frac{A + D}{A + B + C + D}  (4.1)
probability of detection = pd = recall = \frac{D}{B + D}  (4.2)
probability of false alarm = pf = \frac{C}{C + A}  (4.3)
not probability of false alarm = !pf = 1 − pf  (4.4)
precision = prec = \frac{D}{D + C}  (4.5)
balance = bal = 1 − \begin{matrix}√ & \overline{(0 − pf) ^{2}+ (1 − pd)^{2}} \\ √ & \overline{2} \end{matrix}  (4.6)

Equation 4.1 describes the 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.

Equation 4.2 describes the probability of detection of the desired class. It is also referred to as recall. This equation measures how much of the desired class is found and correctly identified.

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

Equation 4.5 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.

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

4.4 Mann-Whitney

Many papers comparing results of classification compare those results using standard parametric statistical tests, such as the 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 t-test, that assumption is that the distribution takes on a curve similar to N(0,1), the normal curve between 0 and 1 [4]. 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 [5] argues that non-Gaussian populations are common enough to require a methodological change in data mining.

Demsar [5] offers a definition of standard methods in data mining. In his study of four years of proceedings from the 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 Section 4.2). Such t-tests assume that the distributions being studied are Gaussian. However, as [5] 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, [5] advocates the use of the 1945 Wilcoxon [?] signed-rank test that compares the ranks for the positive and negative differences (ignoring the signs). Writing five years earlier, [2] 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, [5] augments Wilcoxon with the Friedman test.

One test not studied by [5] is Mann and Whitney’s 1947 modification [12] to Wilcoxon ranksum test (proposed along with his signed-rank test). We prefer this test since:

• 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.

• 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.

Non-parametric tests such as the U test proposed by Mann and Whitney [12] mitigate the outlier problem. The U test uses 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:

Samples A A B B A B A B A B B
Values 0 2 2 3 4 4 5 6 7 7 8

Figure 4.3: Sorted Values of Method A and Method B

On ranking, averages are used when values are the same:

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.

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

Figure 4.4: Sorted, Ranked Values of Method A and Method B

Figure 4.5 shows the U test for the two treatments A and B discussed in Figure 4.3 and Figure 4.4. The test concludes that these methods are not statistically different (at the 95% significance level). As defined in Figure 4.5, 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 wins most.

The sum and median of A’s ranks is

\begin{aligned}sum_{A} & = & 1 + 2.5 + 5.5 + 7 + 9.5 = 25.5 \\ median_{A} & = & 5.5 \end{aligned}

and the sum and median of B’s ranks is

\begin{aligned}sum_{B} & = & 2.5 + 4 + 5.5 + 8 + 9.5 + 11 = 40.5 \\ median_{B} & = & 6.75 \end{aligned}

The U statistic is calculated from U_{x} = sum_{x}− (N_{x}(N_{x}+ 1))/2 :

\begin{matrix}U_{A}= 25.5 − 5 ∗ 6/2 = 10.5 \\ U_{B} = 40.5 − 6 ∗ 7/2 = 19.5 \end{matrix}

These can be converted to a Z-curve using:

\begin{aligned}μ & = & (N_{1}N_{2})/2 & = & 516.4 \\ σ & = & \sqrt{\frac{N_{1}N_{2}(N_{1}+N_{2}+1)}{12}} & = & 5.477 \\ Z_{A} & = & (U_{A}− μ)/σ & = & −0.82 \\ Z_{B} & = & (U_{B}− μ)/σ & = & 0.82 \end{aligned}

(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), higher values are better since we are comparing errors. Hence:

• If median_{A}> median_{B} add 1 to both wins_{A}& losses_{B}.
• Else if median_{A}< median_{B} add 1 to both losses_{A}& wins_{B}.
• Else, add 1 to both ties_{A}& ties_{B}.

Figure 4.5: An example of the Mann-Whitney U test.

Chapter 5 Experimental Results

Chapter 5 shares and briefly explains the results of the experimental comparison of the discretization methods used with a Naïve Bayes classifier.

Conclusion

Chapter 6 begins with section 6.1 which is a broad overview of the previous content of this document. Section 6.2 describes conclusions reached based on the results of the experiments described previously in this document. Section 6.3 proposes additional open research questions which have been brought to light by the work and experimental results of this thesis.

6.1 Overview

In this thesis we have reviewed the broad field of data mining. We identified classification as a useful tool to predict future occurrences based on current evidence and previous information. We reviewed classification methods, including decision tree learners and Naïve Bayes classifiersin order to discuss the differences between available methods of performing this useful task. We then identified Naïve Bayes classifiersas the ideal method for comparing discretization methods, as previous results from numerous sources have shown them to be prone to vast improvement when used with discretization.

We discussed numerous methods of discretization, identifying their strengths and weaknesses and selecting a few of them for comparison against our newly proposed method, the DiscTree algorithm. We introduced this algorithm in this paper and have implemented it. We proposed comparing it to the previously described and selected methods in order to determine how it performed relative to them. We discussed our experimental method, specifically using each of the selected discretization methods and the raw data from 25 data sets in a ten by ten-fold stratified cross-valdiation to obtain the classifier performance measures of acc, bal, pd, !pf, and prec. We then compared the results of each of these performance measures across each classifier to obtain the results provided in the form of win-loss tables.

We will now discuss our conclusions based on the results collected and provide possible future avenues to continue this research.

6.2 Conclusions

6.3 Future Work

Our research has led us to a few possible future paths for research in this area.

An immediate possibility from our work would be the modification of DiscTree discretization method to create an iterative method of discretization. Iterative discretization involves data being discretized.... Iterative discretization methods are very useful because they can be used on streams of data as well as on the files of instances used with the current batch method. For instance, iterative discretization methods could be used as part of a learning mechanism in a problem that involves collecting data online or from a real time source and analyzing it as it arrives, rather than performing the learning operations on static, previously created files stored on a disk.

A second possible area of future research would be in expanding the DiscTree algorithm to examine other possible tree structures that may improve some aspect of the DiscTree algorithm’s performance. Specifically, we have identified splay trees and AVL trees as possible alternatives for the base data structure in the DiscTree algorithm. The implementation of a Randomized Binary Search Tree was the easiest to implement at the inception of this idea of a base sorting data structure behind the discretization and performed fairly well when compared to some recommended methods. It is likely that such other data structures would have similar or better performance. Splay trees may be most interesting because their re-balancing of the tree in accordance with the most accessed values may help to prevent any useful nodes from being pruned during the garbage collection activities of the DiscTree algorithm.

A third possible area of future research would be combining the DiscTree algorithm with some additional forms of data preprocessing, such as attribute subset selection. This technique involves using machine learning algorithm to determine the best combinations of attributes and pruning the data to only contain those attributes. This might be useful because experimental results have shown that learners may become confused or distracted in their classification schemes by irrelevant attributes [?]. Pruning the data prior to running it through the DiscTree algorithm would not increase the method’s performance in terms of classification results. It would, however, save the algorithm time spent in building trees for the unused attributes. Another option for preprocessing prior to use of the DiscTree algorithm would be a review of over-sampling and under-sampling techniques for the data provided to the discretization method. In either case the data is examined for notable instances. In over-sampling, those instances are then repeated numerous times in the data used by the discretization method/classifier. In under-sampling, the instances of interest are used to prune instances from the data set to avoid or minimize their affect on the discretization method/classifier. Both could be potential boons for DiscTree if they could be harnessed to remove the worst or multiply the best examples that DiscTree should learn from. Thus, improvements with additional preprocessing might be made to make DiscTree perform better.

A final possible area of future research would be examining the DiscTree Algorithm to determine if there is a way to best decide the ”cludged” values that algorithm, including:

• The number of instances required between garbage collects

• The maximum allowable tree size

• The number of instances required between increments of maximum allowable tree size

• The number of instances per node/subtree required to make it worthy of being used in the discretization.

It is possible that finding optimum values for these items could improve the performance of DiscTree against its competition.

Appendix A disctree Source Code

# ! /u s r /b i n /gawk − f
#/ ∗ vim: s e t f i l t e y p e=awk : ∗ / −∗− awk −∗−
# A Design f o r A Randomized Binary
# Search Tree D i s c r e t i z a t i o n Method
# By DJ Boland
# M u l t i p u r p o s e i m p l e m e n t a t i o n . Allows dynamic t r e e s i z i n g , t r e e s i z e , and
# v a r i a b l e node s i z e r e q u i r e m e n t f o r s u b s t i t u t i o n

#−

BEGIN{
FS=” ∗, ∗”;  # F i e l d s s e p e r a t e d by a comma and i t s p r e c e e d i n g
OFS=” ,”;  # and t r a i l i n g s p a c e s .
SUBSEP=”#”  #An pound s i g n w i l l be used as t h e d e f a u l t s e p e r a t o r
IGNORECASE=1;  #S e t i n t e r p r e t e r t o be case− i n s e n s i t i v e
Val=”v a l ”;  # S u b s t i t u t e t h e s t r i n g ” v a l” where Val used
L e f t=” l e f t ”;  # S u b s t i t u t e t h e s t r i n g ” l e f t” where L e f t used
Right=” r i g h t ”;  # S u b s t i t u t e t h e s t r i n g ” r i g h t ” where R i g h t used
Here=”h e r e ”;  # S u b s t i t u t e t h e s t r i n g ” here ” where Here used
A l l=” a l l ”;  # S u b s t i t u t e t h e s t r i n g ” a l l ” where A l l used
Min=”min”;  # S u b s t i t u t e t h e s t r i n g ”min” where Min used
Max=”max”;  # S u b s t i t u t e t e h s t r i n g ”max” where Max used
srand ( ) ;  #Randomize t h e seed used t o g e n e r a t e random numbers
B u i l d T r e e =0;  #By d e f a u l t , don ’ t add r e c o r d s t o t h e t r e e s
#0 − don ’ t add ; 1 − add .
C u r r e n t R e c o r d =0;  #Record c u r r e n t l y being a c c e s s e d
Pass =0;  #C o n t a i n s t h e c u r r e n t pass being made through data
L a s t L i n e=””;  #C o n t a i n s l a s t l i n e seen from t h e f i l e being read
MaxSize=7;  #The maximum s i z e t o allow t h e t r e e t o grow t o
ReqRecs=35;  #The minimum number o f r e c o r d s t h a t must be seen
#between garbage c o l l e c t i o n s
Csize =0;  # S i z e f o t h e t r e e c u r r e n t l y being m a n i p u l a t e
Mode=0;
RecordsIn =0;  #Number o f r e c o r d s seen t h u s f a r
I n c S i z e =75;  #Number o f r e c o r d s r e q u i r e d b e f o r e t r e e s i z e grows
GrowthMult =1;

#  S p e c i a l  # I f s p e c i a l e q u a l s 1 , p r i n t Trees on d i s c r e t i z a t i o n f i n i s h
DynTree=0;  #DynTree = 1 a l l o w s dynamic t r e e s i z e ; e l s e s t a t i c
S i z e C h o i c e =0;  #S i z e C h o i c e = 1 use s i z e req o f n / 3 ; e l s e s q r t (n)

}

#S k i p blank and comment l i n e s
{sub ( / \ % . ∗ / ,””)}  # S u b s t i t u t e comments w i t h b l a n k s
{gsub ( / [ \ ’ \”\ ‘ ] / ,”” ,$0)} #Remove any s i n g l e or double q u o t e s from t h i s l i n e
{gsub ( ” ’ ” , ”” , $0)}  #Remove any s i n g l e q u o t e s
/ ˆ [ \ t ]∗$ / {n e x t}  #When blank l i n e observed , go t o t h e n e x t l i n e

#PROCESS RELATION LINES
/@RELATION / {sub ( /@RELATION / , ”@ r e l a t i o n ”)}
/@ r e l a t i o n / {
B u i l d T r e e =0; #S e t f l a g f o r p a r s i n g l i n e s t o remember ( add t o t r e e ) t o f a l s e
A t t r =0;  #S e t a t t r i b u t e c o u n t e r t o z e r o
L a s t L i n e=””; #S e t t h e L a s t L i n e seen t o n o t h i n g
RecordsIn =0;
i f ( Pass ==2){
f o r ( I i n Trees )
{
i f ( C u r r e n t S i z e [ I ] > MaxSize )
{
g a r b a g e C o l l e c t ( C u r r e n t R o o t [ I ] , Rbst , MaxSize )
}
}
p r i n t $0

}

#COMMENTED CODE can be used t o v e r i f y t h a t t h e f i r s t p a s s c r e a t e d t h e BSTs f o r t h e numeric
# a t t r i b u t e s and t h a t i t m a i n t a i n e d c l a s s c o u n t s . I t p r i n t s t h e t r e e t o t h e s c r e e n f o r review
# i f ( Pass ==2){
#  f o r ( I i n Numeric )
#  {
#  a l l v a l u e s =””
#  f o r ( J i n C l a s s e s ){ a l l v a l u e s = a l l v a l u e s ” ” C l a s s e s [ J ]}
#  p r i n t ”C l a s s e s a r e : [ ” a l l v a l u e s ”] ”
#  p r i n t t r e e ( C u r r e n t R o o t [ I ] , Rbst , ”” ,”” , C l a s s e s )
#  p r i n t ””
#  }

#}

}

#PROCESS ATTRIBUTE LINES
/@ATTRIBUTE / {sub ( /@ATTRIBUTE / , ”@ a t t r i b u t e ”)}
/@ a t t r i b u t e / {
#On t h e f i r s t pass , d e t e r m i n e which a t t r i b u t e s s h o u l d be p u t i n t o t r e e s
#while p r e v e n t i n g t h e c l a s s a t t r i b u t e from being p u t i n t o t h e t r e e .
i f ( Pass ==1)

{

i f ( L a s t L i n e != ””)

{

A t t r ++;  #For each new a t t r i b u t e , i n c r e a s e a t t r i b u t e c o u n t e r

# Obtain t h e name of each a t t r i b u t e and
# s t o r e t o t h e Names a r r a y
s p l i t ( LastLine ,a , ” ”)
Names[ A t t r ]= a [ 2 ]

#C r e a t e a l i s t of t h e f i e l d s t h a t s h o u l d be p u t i n t o t r e e s
A t t r s [ A t t r ]=1
#  i f ( ( match ( LastLine , /numeric / ) > 0) | | ( match ( LastLine , /r e a l / ) > 0) | | ( match ( LastLine , /i n t e g e r / ) > 0 ) )

{

Trees [ A t t r ]=1

} }

L a s t L i n e=$0 #M a i n t a i n a copy of t h e l a s t a t t r i b u t e read , as i f t h e @data
#symbol i s seen t h e n t h e L a s t L i n e a t t r i b u t e i s t h e c l a s s
# a t t r i b u t e

n e x t }

#On t h e second pass , r e p l a c e t h e o r i g i n a l a t t r i b u t e v a l u e s with an
# a c c u r a t e l i s t of t h e d i s c r e t i z e d c l a s s e s
i f ( Pass ==2)

{

i f ( L a s t L i n e != ””)

{

A t t r++
i f ( A t t r i n Trees )

{

o u t c l a s s e s = ””
i f ( S i z e C h o i c e ==1)

{

o u t c l a s s e s = d i s c C l a s s e s ( Rbst , C u r r e n t R o o t [ A t t r ] , i n t ( ( Rbst [ C u r r e n t R o o t [ A t t r ] , A l l ] ) / 3 ) , o u t c l a s s e s )

} e l s e {

o u t c l a s s e s = d i s c C l a s s e s ( Rbst , C u r r e n t R o o t [ A t t r ] , i n t ( s q r t ( Rbst [ C u r r e n t R o o t [ A t t r ] , A l l ] ) ) , o u t c l a s s e s )

}

sub ( LastLine , ”@ a t t r i b u t e ” Names[ A t t r ] ” {”o u t c l a s s e s ”}” , L a s t L i n e )

}

p r i n t L a s t L i n e

}

L a s t L i n e=$0

n e x t }

}

#PREPARE TO PROCESS DATA
/@DATA / {sub ( /@DATA / , ”@data ”)}
/@data / {
B u i l d T r e e =1;  #The p o i n t has been r e a c h e d where d a t a s h o u l d be p u t i n t r e e
C u r r e n t R e c o r d =1; #The n e x t nonblank l i n e r e a d w i l l be t h e f i r s t r e c o r d
#On f i r s t pass , d e t e r m i n e t h e t h e c l a s s e s and s e t up t h e t r e e s
i f ( Pass ==1)

{

#P a r s e l a s t l i n e t o o b t a i n c l a s s e s s
sub ( / \ }$ / , ”” , L a s t L i n e )  #Prune c l o s i n g b r a c k e t from c l a s s
sub ( /@ a t t r i b u t e / ,”” , L a s t L i n e )  #Prune @ a t t r i b u t e sybmol from c l a s s
sub ( / ˆ [ [ :alnum : ] [ : blank : ] ] ∗ \ { / , ”” , L a s t L i n e ) #Prune c l a s s name and opening b r a c k e t from c l a s s e s
gsub ( / [ \ t \n ] ∗ / , ”” , L a s t L i n e )  #Prune any e x t r a n e o u s s p a c e s from c l a s s e s
s p l i t ( LastLine , myClasses , ” ,”)  # S p l i t r e m a i n i n g i n f o r m a t i o n i n t o d i f f e r e n t c l a s s e s
#  COMMENTED CODE p r i n t s each c l a s s and c r e a t e s a l i s t of a l l t h e c l a s s e s and p r i n t s i t

#  f o r ( J i n myClasses ){ p r i n t myClasses [ J ]}
#  a l l v a l s = ””
#  f o r ( J i n myClasses ){ i f ( a l l v a l s == ””){ a l l v a l s =myClasses [ J ]} e l s e { a l l v a l s = a l l v a l s ” ” myClasses [ J ]}}
#  p r i n t a l l v a l s
# I n i t i a l i z e t h e r o o t s of each t r e e t o s y b o l i z e an empty t r e e , and new r e c o r d s f o r each t r e e t o 0
f o r ( I i n Trees ){ C u r r e n t R o o t [ I ] = ”?”; C u r r e n t S i z e [ I ] = 0 ; NewRecords [ I ]=0}

}

#When o u t p u t t i n g pruned d a t a s e t , e n s u r e keeping t h e @data l i n e
i f ( Pass ==2) { p r i n t L a s t L i n e ; p r i n t $0}
#Do n o t want t o proceed t o p u t t h e @data symbol i n t h e t r e e , so go t o t h e n e x t l i n e

n e x t }

#PROCESS DATA / BUILD TREES FROM DATA
#PASS ONE c r e a t e s t h e b i n a r y s e a r c h t r e e f o r each ( numeric ) a t t r i b u t e
Pass==1 && B u i l d T r e e && NF >1{
f o r ( I i n Trees )  #For each non− c l a s s a t t r i b u t e

{

NewRecords [ I ]++  #Add one t o t h e number of r e c o r d s seen s i n c e l a s t garbage c o l l e c t
f i e l d = $I ;  # f i e l d s e t t o t h e v a l u e of t h e a t t r i b u t e i n t h e row c u r r e n t l y being p r o c e s s e d
CSize= C u r r e n t S i z e [ I ]  # s e t CSize t o t h e s i z e of t h e c u r r e n t t r e e
# I f m i s s i n g data , d e c r e a s e new r e c o r d count and go t o n e x t f i e l d
i f ( f i e l d ˜ / ? / ) {NewRecords [ I]−−; c o n t i n u e }
#Otherwise , d a t a i s v a l i d , i n s e r t i n t o t h e t r e e
e l s e r e t u r n v a l u e s= r b s t i n s e r t ( C u r r e n t R o o t [ I ] , Rbst , f i e l d , Names[ I ] , CurrentRecord ,$NF, myClasses , CSize )
# S p l i t t h e r e t u r n e d v a l u e i n t o t h e c u r r e n t r o o t and s i z e of t h e t r e e
# t h a t was j u s t p r o c e s s e d
s p l i t ( r e t u r n v a l u e s , v a l s , SUBSEP)
C u r r e n t R o o t [ I ]= v a l s [ 1 ] SUBSEP v a l s [ 2 ]
C u r r e n t S i z e [ I ]= v a l s [ 3 ]
# I f t h e t r e e exceeds t h e Maximum s i z e and t h e minumum numer of r e c o r d s
#between garbage c o l l e c t i o n s has been seen , Garbage C o l l e c t !
i f ( ( C u r r e n t S i z e [ I ] > MaxSize ) && ( NewRecords [ I ] >=ReqRecs ) )

{

g a r b a g e C o l l e c t ( C u r r e n t R o o t [ I ] , Rbst , MaxSize )
NewRecords [ I ]=0

}

RecordsIn ++;
i f ( DynTree==1)

{

i f ( RecordsIn >= ( I n c S i z e ∗ GrowthMult ) )

{

GrowthMult++;
MaxSize= MaxSize + 2ˆ (2+GrowthMulti )

} }

}

# I n c r e a s e t h e c o u n t e r of t h e number of r e c o r d s t h a t have been p r o c e s s e d
C u r r e n t R e c o r d ++;

}

#PASS TWO s u b s t i t u t e s t h e d i s c r e t i z e d v a l u e from t h e s e a r c h t r e e f o r each v a l u e /a t t r i b u t e
Pass==2 && B u i l d T r e e && NF >1{
f o r ( I i n Trees )  # f o r each non− c l a s s a t t r i b u t e

{

f i e l d = $I  # f i e l d s e t t o t h e v a l u e of t h e a t t r i b u t e i n t h e row c u r r e n t l y being p r o c e s s e d
R o o t I n s t a n c e= C u r r e n t R o o t [ I ] #S e t R o o t I n s t a n c e t o t h e r o o t i n s t a n c e of t h e a t t r i b u t e c u r r e n t l y being p r o c e s s e d
i f ( f i e l d ˜ / ? / ) c o n t i n u e  # I f m i s s i n g d a t a ( symbolized by ? ) , go t o t h e n e x t f i e l d
#Otherwise , d a t a i s v a l i d , d e t e r m i n e what d i s c r e t e v a l u e t o s u b s t i t u t e with

e l s e {

i f ( S i z e C h o i c e ==1)

{

$I= subwith ( i n t ( ( Rbst [ R o o t I n s t a n c e , A l l ] ) / 3 ) ,f i e l d , Rbst , C u r r e n t R o o t [ I ] )

} e l s e {

$I= subwith ( i n t ( s q r t ( Rbst [ R o o t I n s t a n c e , A l l ] ) ) , f i e l d , Rbst , C u r r e n t R o o t [ I ] )

} }

}

# P r i n t t h e p a r s e d l i n e s
p r i n t $0

}

END{
i f ( S p e c i a l ==1)

{

f o r ( I i n Trees )

{

p r i n t ””
a l l v a l s = ””
f o r ( J i n myClasses ){ i f ( a l l v a l s == ””){ a l l v a l s =myClasses [ J ]} e l s e { a l l v a l s = a l l v a l s ” ” myClasses [ J ]}}
p r i n t ”C l a s s e s a r e : [ ” a l l v a l s ”] ”
p r i n t t r e e ( C u r r e n t R o o t [ I ] , Rbst , ”” ,”” , myClasses )
p r i n t ””

} }

}

#∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗

# b s t .awk
#DJ’ s Binary Search Tree F u n c t i o n s
# I n s e r t a a new node a t t h e r o o t of t h e t r e e
f u n c t i o n i n s e r t R ( R o o t I n s t a n c e , Tree , Value , A t t r , Rec , Class , C l a s s e s , C u r r e n t S i z e )

{

i f ( R o o t I n s t a n c e == ”?”)

{

r e t u r n newtree ( A t t r SUBSEP Rec , Tree , Value , Class , C l a s s e s , C u r r e n t S i z e )

}

Tree [ R o o t I n s t a n c e , A l l ]++

Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s ]++
i f ( Value == Tree [ R o o t I n s t a n c e , Val ] )

{

Tree [ R o o t I n s t a n c e , Here]++
Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s ]++
r e t u r n R o o t I n s t a n c e SUBSEP C u r r e n t S i z e

}

i f ( Value < Tree [ R o o t I n s t a n c e , Val ] )

{

r e t u r n v a l s= i n s e r t R ( Tree [ R o o t I n s t a n c e , L e f t ] , Tree , Value , A t t r , Rec , Class , C l a s s e s , C u r r e n t S i z e )
s p l i t ( r e t u r n v a l s , v a l s , SUBSEP)
Tree [ R o o t I n s t a n c e , L e f t ]= v a l s [ 1 ] SUBSEP v a l s [ 2 ]
C u r r e n t S i z e= v a l s [ 3 ]
R o o t I n s t a n c e = r o t a t e R ( R o o t I n s t a n c e , Tree , C l a s s e s )

} e l s e {

r e t u r n v a l s= i n s e r t R ( Tree [ R o o t I n s t a n c e , Right ] , Tree , Value , A t t r , Rec , Class , C l a s s e s , C u r r e n t S i z e )
s p l i t ( r e t u r n v a l s , v a l s , SUBSEP)
Tree [ R o o t I n s t a n c e , Right ]= v a l s [ 1 ] SUBSEP v a l s [ 2 ]
C u r r e n t S i z e= v a l s [ 3 ]
R o o t I n s t a n c e = r o t a t e L ( R o o t I n s t a n c e , Tree , C l a s s e s )

}

r e t u r n R o o t I n s t a n c e SUBSEP C u r r e n t S i z e

}

#R o t a t e t h e c u r r e n t r o o t ’ s l e f t s u b c h i l d t o r i g h t t o make i t become t h e c u r r e n t r o o t
f u n c t i o n r o t a t e R ( R o o t I n s t a n c e , Tree , C l a s s e s ,  temp )

{

temp = Tree [ R o o t I n s t a n c e , L e f t ]
Tree [ R o o t I n s t a n c e , L e f t ] = Tree [ temp , Right ]
Tree [ temp , Right ] = R o o t I n s t a n c e
Tree [ temp , A l l ] = Tree [ R o o t I n s t a n c e , A l l ]
f o r (M i n C l a s s e s )

{

Tree [ temp , ”A” SUBSEP C l a s s e s [M] ] = Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ]

}

i f ( ( Tree [ R o o t I n s t a n c e , L e f t ] != ”?”) && ( Tree [ R o o t I n s t a n c e , Right ] != ”?” ) )

{

Tree [ R o o t I n s t a n c e , A l l ]= Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , A l l ]+ Tree [ Tree [ R o o t I n s t a n c e , Right ] , A l l ]+ Tree [ R o o t I n s t a n c e , Here ]
f o r (M i n C l a s s e s )

{

Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ] = Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , ”A” SUBSEP C l a s s e s [M] ] + Tree [ Tree [ R o o t I n s t a n c e , Right ] , ”A” SUBSEP C l a s s e s [M] ] + Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ]

} } e l s e {

i f ( ( Tree [ R o o t I n s t a n c e , L e f t ] != ”?” ) )

{

Tree [ R o o t I n s t a n c e , A l l ] = Tree [ R o o t I n s t a n c e , Here]+ Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , A l l ]
f o r (M i n C l a s s e s )

{

Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ] = Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ] + Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , ”A” SUBSEP C l a s s e s [M] ]

} } e l s e {

i f ( ( Tree [ R o o t I n s t a n c e , Right ] != ”?” ) )

{

Tree [ R o o t I n s t a n c e , A l l ] = Tree [ R o o t I n s t a n c e , Here]+ Tree [ Tree [ R o o t I n s t a n c e , Right ] , A l l ]
f o r (M i n C l a s s e s )

{

Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ] = Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ] + Tree [ Tree [ R o o t I n s t a n c e , Right ] , ”A” SUBSEP C l a s s e s [M] ]

} } e l s e {

Tree [ R o o t I n s t a n c e , A l l ] = Tree [ R o o t I n s t a n c e , Here ]
f o r (M i n C l a s s e s )

{

Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ] = Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ]

} }

} }

r e t u r n temp

}

#R o t a t e t h e c u r r e n t r o o t s r i g h t s u b c h i l d up t o t h e r o o t ( by r o t a t i n g i t t o t h e l e f t )
f u n c t i o n r o t a t e L ( R o o t I n s t a n c e , Tree , C l a s s e s ,  temp )

{

temp = Tree [ R o o t I n s t a n c e , Right ]
Tree [ R o o t I n s t a n c e , Right ] = Tree [ temp , L e f t ]
Tree [ temp , L e f t ] = R o o t I n s t a n c e
Tree [ temp , A l l ] = Tree [ R o o t I n s t a n c e , A l l ]
f o r (M i n C l a s s e s )

{

Tree [ temp , ”A” SUBSEP C l a s s e s [M] ] = Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ]

}

i f ( ( Tree [ R o o t I n s t a n c e , L e f t ] != ”?”) && ( Tree [ R o o t I n s t a n c e , Right ] != ”?” ) )

{

Tree [ R o o t I n s t a n c e , A l l ]= Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , A l l ]+ Tree [ Tree [ R o o t I n s t a n c e , Right ] , A l l ]+ Tree [ R o o t I n s t a n c e , Here ]
f o r (M i n C l a s s e s )

{

Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ] = Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , ”A” SUBSEP C l a s s e s [M] ] + Tree [ Tree [ R o o t I n s t a n c e , Right ] , ”A” SUBSEP C l a s s e s [M] ] + Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ]

} } e l s e {

i f ( ( Tree [ R o o t I n s t a n c e , L e f t ] != ”?” ) )

{

Tree [ R o o t I n s t a n c e , A l l ] = Tree [ R o o t I n s t a n c e , Here]+ Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , A l l ]
f o r (M i n C l a s s e s )

{

Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ] = Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ] + Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , ”A” SUBSEP C l a s s e s [M] ]

} } e l s e {

i f ( ( Tree [ R o o t I n s t a n c e , Right ] != ”?” ) )

{

Tree [ R o o t I n s t a n c e , A l l ] = Tree [ R o o t I n s t a n c e , Here]+ Tree [ Tree [ R o o t I n s t a n c e , Right ] , A l l ]
f o r (M i n C l a s s e s )

{

Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ] = Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ] + Tree [ Tree [ R o o t I n s t a n c e , Right ] , ”A” SUBSEP C l a s s e s [M] ]

} } e l s e {

Tree [ R o o t I n s t a n c e , A l l ] = Tree [ R o o t I n s t a n c e , Here ]
f o r (M i n C l a s s e s )

{

Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ] = Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ]

} }

} }

r e t u r n temp

}

#F u n c t i o n t o i n s e r t a new node i n t o t h e t r e e
f u n c t i o n newtree ( R o o t I n s t a n c e , Tree , Value , Class , C l a s s e s , C u r r e n t S i z e )

{

Tree [ R o o t I n s t a n c e , L e f t ]= ”?”
Tree [ R o o t I n s t a n c e , Right ]= ”?”
Tree [ R o o t I n s t a n c e , Val]= Value
Tree [ R o o t I n s t a n c e , A l l ]=1
Tree [ R o o t I n s t a n c e , Here]=1
# I n i t i a l i z e t h e h e r e and A l l c l a s s c o u n t s f o r each c l a s s
f o r (M i n C l a s s e s )

{

Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ] = 0
Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ] = 0

}

Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s ]=1
Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s ]=1
C u r r e n t S i z e++
r e t u r n R o o t I n s t a n c e SUBSEP C u r r e n t S i z e

}

#F u n c t i o n t o p r i n t t h e c u r r e n t t r e e
f u n c t i o n p r i n t t r e e ( R o o t I n s t a n c e , Tree , b4 , i n d e n t , C l a s s e s ,  a l l c l a s s e s , t r e e c l a s s e s )

{

a l l c l a s s e s =””
t r e e c l a s s e s =””
f o r (M i n C l a s s e s )

{

i f ( a l l c l a s s e s == ””){ a l l c l a s s e s =Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ] }
e l s e a l l c l a s s e s = a l l c l a s s e s ” ” Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s e s [M] ]
i f ( t r e e c l a s s e s == ””){ t r e e c l a s s e s =Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ] }
e l s e t r e e c l a s s e s = t r e e c l a s s e s ” ” Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s e s [M] ]

}

p r i n t i n d e n t b4 R o o t I n s t a n c e ” = ” Tree [ R o o t I n s t a n c e , Val ] ” [ h e r e=” Tree [ R o o t I n s t a n c e , Here ] ”] [ a l l =” Tree [ R o o t I n s t a n c e , A l l ] ”] ”
p r i n t i n d e n t b4 R o o t I n s t a n c e ” C l a s s e s h e r e a r e : [ ” a l l c l a s s e s ”] , a l l : [ ” t r e e c l a s s e s ”] ”

i f ( Tree [ R o o t I n s t a n c e , L e f t ] != ”?”)
p r i n t t r e e ( Tree [ R o o t I n s t a n c e , L e f t ] , Tree , ”< ” , i n d e n t ”|  ” , C l a s s e s ,x)
i f ( Tree [ R o o t I n s t a n c e , Right ] != ”?”)
p r i n t t r e e ( Tree [ R o o t I n s t a n c e , Right ] , Tree , ”> ” , i n d e n t ”|  ” , C l a s s e s ,x)

}

#F u n c t i o n f o r i n s e r t i n g a v a l u e i n t o t h e t r e e . I f t h e v a l u e i s n o t a t t h e r o o t ,
# t h i s f u n c t i o n w i l l , with a 1 /n chance , i n s e r t t h e node a t t h e c u r r e n t r o o t .
f u n c t i o n r b s t i n s e r t ( R o o t I n s t a n c e , Tree , Value , A t t r , Rec , Class , C l a s s e s , C u r r e n t S i z e )

{

i f ( R o o t I n s t a n c e == ”?”)

{

r e t u r n newtree ( A t t r SUBSEP Rec , Tree , Value , Class , C l a s s e s , C u r r e n t S i z e )

}

i f ( Value == Tree [ R o o t I n s t a n c e , Val ] )

{

Tree [ R o o t I n s t a n c e , Here]++
Tree [ R o o t I n s t a n c e , A l l ]++
Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s ]++
Tree [ R o o t I n s t a n c e , ”h” SUBSEP C l a s s ]++
r e t u r n R o o t I n s t a n c e SUBSEP C u r r e n t S i z e

}

e l s e {

i f ( ( rand ( ) ∗ Tree [ R o o t I n s t a n c e , A l l ] ) < 1 . 0 )

{

r e t u r n i n s e r t R ( R o o t I n s t a n c e , Tree , Value , A t t r , Rec , Class , C l a s s e s , C u r r e n t S i z e )

}

i f ( Value < Tree [ R o o t I n s t a n c e , Val ] )

{

r e t u r n v a l s= r b s t i n s e r t ( Tree [ R o o t I n s t a n c e , L e f t ] , Tree , Value , A t t r , Rec , Class , C l a s s e s , C u r r e n t S i z e )
s p l i t ( r e t u r n v a l s , v a l s , SUBSEP)
Tree [ R o o t I n s t a n c e , L e f t ]= v a l s [ 1 ] SUBSEP v a l s [ 2 ]
C u r r e n t S i z e= v a l s [ 3 ]

} e l s e {

r e t u r n v a l s= r b s t i n s e r t ( Tree [ R o o t I n s t a n c e , Right ] , Tree , Value , A t t r , Rec , Class , C l a s s e s , C u r r e n t S i z e )
s p l i t ( r e t u r n v a l s , v a l s , SUBSEP)
Tree [ R o o t I n s t a n c e , Right ]= v a l s [ 1 ] SUBSEP v a l s [ 2 ]
C u r r e n t S i z e= v a l s [ 3 ]

}

Tree [ R o o t I n s t a n c e , A l l ]++
Tree [ R o o t I n s t a n c e , ”A” SUBSEP C l a s s ]++
r e t u r n R o o t I n s t a n c e SUBSEP C u r r e n t S i z e

} }

#F u n c t i o n t h a t d e t e r m i n e s which t r e e node t o s u b s t i t u t e f o r a given v a l u e
#For a t r e e node t o be chosen as a v i a b l e s u b s t i t u t e , i t must have a t l e a s t
#minSize nodes a t i n i t s e l f and /or i n i t s c h i l d r e n .
f u n c t i o n subwith ( minSize , Value , Tree , R o o t I n s t a n c e )

{

# p r i n t ”This i n s t a n c e i s : ” Value ” and i t i s being compared t o : ” Tree [ R o o t I n s t a n c e , Val ]
i f ( ( ( Value == Tree [ R o o t I n s t a n c e , Val ] ) | | ( Value ˜ Tree [ R o o t I n s t a n c e , Val ] ) ) && ( Tree [ R o o t I n s t a n c e , A l l ] >= minSize ) )

{

#  p r i n t ”They a r e e q u a l ”
r e t u r n R o o t I n s t a n c e

}

# p r i n t ”n o t e q u a l ”
i f ( Value < Tree [ R o o t I n s t a n c e , Val ] )

{

i f ( Tree [ R o o t I n s t a n c e , L e f t ] ! = ”?”)

{

i f ( Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , A l l ] >= minSize )

{

r e t u r n subwith ( minSize , Value , Tree , Tree [ R o o t I n s t a n c e , L e f t ] )

}

e l s e r e t u r n R o o t I n s t a n c e

}

e l s e r e t u r n R o o t I n s t a n c e

}

i f ( Value > Tree [ R o o t I n s t a n c e , Val ] )

{

i f ( Tree [ R o o t I n s t a n c e , Right ] != ”?”)

{

i f ( Tree [ Tree [ R o o t I n s t a n c e , Right ] , A l l ] >= minSize )

{

r e t u r n subwith ( minSize , Value , Tree , Tree [ R o o t I n s t a n c e , Right ] )

}

e l s e r e t u r n R o o t I n s t a n c e

}

e l s e r e t u r n R o o t I n s t a n c e

} e l s e {

i f ( i n t (2∗ rand ( ) ) > 1)

{

i f ( Tree [ R o o t I n s t a n c e , Right ] != ”?”)

{

i f ( Tree [ Tree [ R o o t I n s t a n c e , Right ] , A l l ] >= minSize )

{

r e t u r n subwith ( minSize , Value , Tree , Tree [ R o o t I n s t a n c e , Right ] )

}

e l s e r e t u r n R o o t I n s t a n c e

}

e l s e r e t u r n R o o t I n s t a n c e

} e l s e {

i f ( Tree [ R o o t I n s t a n c e , L e f t ] ! = ”?”)

{

i f ( Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , A l l ] >= minSize )

{

r e t u r n subwith ( minSize , Value , Tree , Tree [ R o o t I n s t a n c e , L e f t ] )

}

e l s e r e t u r n R o o t I n s t a n c e

}

e l s e r e t u r n R o o t I n s t a n c e

}

} }

#F u n c t i o n t o o b t a i n t h e l i s t s of d i s c r e t i z e d c l a s s e s
#To be a p a r t of t h i s l i s t , t h e given node must
#be of a t l e a s t minSize
f u n c t i o n d i s c C l a s s e s ( Tree , R o o t I n s t a n c e , minSize , myClasses )

{

i f ( Tree [ R o o t I n s t a n c e , L e f t ] != ”?”)

{

myClasses= d i s c C l a s s e s ( Tree , Tree [ R o o t I n s t a n c e , L e f t ] , minSize , myClasses )

}

i f ( Tree [ R o o t I n s t a n c e , A l l ] >= minSize )

{

i f ( myClasses != ””)

{

myClasses = myClasses ” , ” R o o t I n s t a n c e

}

e l s e

{

myClasses = R o o t I n s t a n c e

} }

i f ( Tree [ R o o t I n s t a n c e , Right ] != ”?”)

{

myClasses= d i s c C l a s s e s ( Tree , Tree [ R o o t I n s t a n c e , Right ] , minSize , myClasses )

}

r e t u r n myClasses

}

#F u n c t i o n t o prune t r e e t o an a p p r o p r i a t e s i z e /keep i t from e x c e e d i n g memory a v a i l a b i l i t y
f u n c t i o n g a r b a g e C o l l e c t ( R o o t I n s t a n c e , Tree , MaxSize ,  low , high , s i z e )

{

#S e t up a s e t t o t r a c k t h e t r e e nodes t h a t have been ”touched by t h e b r e a d t h f i r s t s e a r c h
s i z e =0;
high =1;
low=0;
NodeSet [ 0 ] = R o o t I n s t a n c e

#F u n c t i o n u s e s a breadth − f i r s t approach t o span t h e t r e e , adding nodes t o t h e s e t l e f t t o r i g h t
#a c r o s s each l e v e l and t h e n moving down t o t h e f o l l o w i n g one . When t h e max s i z e o f t h e t r e e i s reached ,
#t h e nodes remaining i n t h e s e t are removed , along w i t h any o f t h e i r c h i l d r e n t h a t were n o t d i s c o v e r e d .
while ( high != low )

{

i f ( Tree [ NodeSet [ low ] , L e f t ] != ”?”)

{

NodeSet [ high ]= Tree [ NodeSet [ low ] , L e f t ] ;
high ++;

}

i f ( Tree [ NodeSet [ low ] , Right ] != ”?”)

{

NodeSet [ high ]= Tree [ NodeSet [ low ] , Right ] ;
high ++;

}

s i z e ++;
low++;

i f ( s i z e == MaxSize )

{

high = high −1;
while ( low <= high )

{

removeVal ( R o o t I n s t a n c e , Tree , pruneNode ( NodeSet [ high ] , Tree ) )
high = high − 1 ;

} }

} }

#F u n c t i o n t o remove a g i v e n node and any o f i t s c h i l d r e n from t h e t r e e
f u n c t i o n pruneNode ( R o o t I n s t a n c e , Tree )

{

# I f t h i s node has a l e f t c h i l d , remove t h a t l e f t c h i l d b e f o r e t h i s node
i f ( Tree [ R o o t I n s t a n c e , L e f t ] != ”?”)

{

pruneNode ( Tree [ R o o t I n s t a n c e , L e f t ] , Tree )

}

# I f t h i s node has a r i g h t c h i l d , remove t h a t r i g h t c h i l d b e f o r e t h i s node
i f ( Tree [ R o o t I n s t a n c e , Right ] != ”?”)

{

pruneNode ( Tree [ R o o t I n s t a n c e , Right ] , Tree )

}

#S e t a l l r e l e v a n t v a l u e s o f t h i s t r e e t o z e r o and d i s c o n n e c t t h e c h i l d r e n s nodes
Tree [ R o o t I n s t a n c e , L e f t ]= ”?”
Tree [ R o o t I n s t a n c e , Right ]= ”?”
Tree [ R o o t I n s t a n c e , A l l ]=0
Tree [ R o o t I n s t a n c e , Here]=0
return Tree [ R o o t I n s t a n c e , Val ]

}

#F u n c t i o n t o remove a node from t h e t r e e based on i t s v a l u e
# S t a r t i n g r o o t node w i l l n o t be removed u s i n g t h i s method
f u n c t i o n removeVal ( R o o t I n s t a n c e , Tree , myVal)

{

i f ( Tree [ R o o t I n s t a n c e , Val ] > myVal)

{

i f ( Tree [ Tree [ R o o t I n s t a n c e , L e f t ] , Val ] == myVal)

{

Tree [ R o o t I n s t a n c e , L e f t ]= ”?”

} e l s e {

removeVal ( Tree [ R o o t I n s t a n c e , L e f t ] , Tree , myVal)

} } e l s e {

i f ( Tree [ Tree [ R o o t I n s t a n c e , Right ] , Val ] == myVal)

{

Tree [ R o o t I n s t a n c e , Right ]= ”?”

} e l s e {

removeVal ( Tree [ R o o t I n s t a n c e , Right ] , Tree , myVal)

}

}

} [figure]

Appendix B crossval Source Code

# ! /b i n /bash
DESTDIR=${DESTDIR=”/s r v /bronze /d j ”}
MyHome=${MyHome=${HOME}} #${HOME}}
# Q0: where w i l l t h e o u t p u t be s t o r e d
Safe=${Safe=${DESTDIR} /v a r /weka}
BinDir=${BinDir=${MyHome} /b i n}
# Q1: where i s your data ?
Data=${Data=${MyHome} /v a r /d a t a /d i s c r e t e }
# Q2: what data s e t s w i l l we run ?
Datums=${Datums=”a2b /a u d i o l o g y a2b /auto−mpg
a2b /b r e a s t − c a n c e r a2b /b r e a s t − cancer− w i s c o n s i n
c2d /c r e d i t − a c2d /d i a b e t e s e 2 i /e c o l i e 2 i /f l a g e 2 i /hayes− r o t h
e 2 i /h e a r t− c e 2 i /h e a r t− h e 2 i /h e p a t i t i s e 2 i /imports −85
e 2 i /i r i s j 2 p /kr− vs− kp j 2 p /l e t t e r j 2 p /mushroom
q2s /segment q2s /s i c k q2s /s p l i c e q2s /soybean t 2 z /vowel
t 2 z /wine t 2 z /wdbc t 2 z /waveform−5000 ”}
# Q3: what l e a r n e r s w i l l you t r y ?
L e a r n e r s=${L e a r n e r s=”bayes nbk”}
bayes ( ) { wttp $1 $2 $wBayes | gotwant ; }
nbk ( )  { wttp $1 $2 $wNbk | gotwant ; }
[ − f ”$ F u n c t i o n s ” ] && . $ F u n c t i o n s
# Q4 : what pre− p r o c e s s o r s w i l l you use
Preps=${Preps=”c a t d i s c t r e e a d i s c t r e e b d i s c t r e e c d i s c t r e e d f a y y a d I r a n i pkid t b i n ”}
d i s c t r e e a ( ) { d t r e e 2 Pass=1 $1 Pass=2 $1 ; }
d i s c t r e e b ( ) { d t r e e 2 DynTree=1 Pass=1 $1 Pass=2 $1 ; }
d i s c t r e e c ( ) { d t r e e 2 S i z e C h o i c e=1 Pass=1 $1 Pass=2 $1 ; }
d i s c t r e e d ( ) { d t r e e 2 DynTree=1 S i z e C h o i c e=1 Pass=1 $1 Pass=2 $1 ; }
t b i n ( ) { t e n b i n s Pass=1 $1 Pass=2 $1 Pass=3 $1 ; }
pkid ( ) { wpkid $1 ; }
# Q5: how many r e p e a t s ?
Repeats=${Repeats=10}

# Q6: how many b i n s?
Bins=${Bins=10}

# A l l r i g h t t h e n . L e t s go !
mkdir − p $Safe  # e n s u r e s a f e p l a c e e x i s t s
Tmp= ‘ mktemp − d ‘  # make a sandbox where o n l y you w i l l p l a y
trap ”rm − r f $Tmp” 0 1 2 3 15 # l e a v e n o t h i n g behind when you q u i t
cd $Tmp  # go t o t h e sandbox

main ( ) {
s e t − x
f o r datum i n $Datums

do

echo ”#data , l e a r n e r , prep , t r a i n , t e s t , r e p e a t s , bin , goal ,a ,b ,c ,d , accuracy ,pd , pf , p r e c i s i o n , b a l ”
f o r prep i n $Preps

do

$prep ${Data } /${datum }. a r f f > d a t a . a r f f
f o r ( ( r e p e a t s =1; r e p e a t s<=$Repeats ; r e p e a t s ++))

do

seed=$RANDOM
f o r ( ( b i n =1; bin<=${Bins }; b i n ++))

do

c a t d a t a . a r f f | someArff − seed $seed − b i n s $Bins − b i n $bin
g o a l s = ‘ c a t d a t a . a r f f | c l a s s e s − b r i e f ‘
n1= ‘ i n s t a n c e s t r a i n . a r f f ‘
n2= ‘ i n s t a n c e s t e s t . a r f f ‘
f o r l e a r n i n $ L e a r n e r s

do

$ l e a r n t r a i n . a r f f t e s t . a r f f > r e s u l t s . csv
cp r e s u l t s . csv $Safe /r e s u l t s . csv
f o r g o a l i n $ g o a l s

do

b4=”$datum , $ l e a r n , $prep , $n1 , $n2 , $ r e p e a t s , $bin , $goal ”;
c a t r e s u l t s . csv | ${BinDir } /abcd − g ”$goal ” − p ”${b4}” − d 1 | t a i l − n 1
#abcd P r e f i x=” ${b4}” False =” ${one}” True=” ${two}”

done

done ; done ; done ; done ; done

}

Log=$$
S t a r t = ‘ d a t e +% H:% M:% S% t%m/%d/%Y‘
( main | t e e $Safe /x v a l . $Log ) 2> $Safe /x v a l . e r r . $Log
c a t $Safe /x v a l . $Log | s o r t − t , − n − k 17 ,17 | malign > $Safe /m y r e s u l t s . $Log . csv

echo ”Computing acc comparison”
w i n l o s s t i e − i n p u t $Safe /m y r e s u l t s . $Log . csv − f i e l d s 17 − perform 13 − key 3 −−95 − high > $Safe /crossvalaccmw . $Log . csv
echo ”Computing pd comparison”
w i n l o s s t i e − i n p u t $Safe /m y r e s u l t s . $Log . csv − f i e l d s 17 − perform 14 − key 3 −−95 − high > $Safe /crossvalpdmw . $Log . csv
echo ”Computing p r e c comparison”
w i n l o s s t i e − i n p u t $Safe /m y r e s u l t s . $Log . csv − f i e l d s 17 − perform 16 − key 3 −−95 − high > $Safe /crossvalprecmw . $Log . csv
echo ”Computing b a l comparison”
w i n l o s s t i e − i n p u t $Safe /m y r e s u l t s . $Log . csv − f i e l d s 17 − perform 17 − key 3 −−95 − high > $Safe /crossvalbalmw . $Log . csv

End= ‘ d a t e +% H:% M:% S% t%m/%d/%Y‘
echo $ S t a r t ”t o ” $End
echo $ S t a r t ”t o ” $End >> m y r e s u l t s . $Log . csv
echo $Safe /x v a l . $Log
[figure]

Appendix C tenbins Source Code

# ! /u s r /b i n /gawk − f
# / ∗ vim: s e t f i l e t y p e=awk : ∗ / −∗− awk −∗−
# O r i g i n a l S c r i p t by Dr . Tim Menzies as n b i n s
# M o d i f i e d f o r use as t e n b i n s by DJ Boland , January 2007
### p a t t e r n s 0 : i n i t i a l i z a t i o n s t u f f
BEGIN{
BinLog=0; # i f non− zero , use b i n l o g g i n g a f t e r rounding numbers
Bins =10;
FS=OFS=” ,”;
IGNORECASE=1;
I n f =10∗∗32;

}

# s k i p b l a n k s and comments
{sub ( / \ % . ∗ / ,””)}
/ ˆ [ \ t ]∗$ / {next }
# r e a c t t o keywords
/@ r e l a t i o n / { Header =1; Data =0; A t t r =0; }
/@data /  { Header =0; Data =1; }
/@ a t t r i b u t e / { A t t r ++; }
# F i r s t pass
# r e a c t t o keywords and i n i t i a l i z e a t t r i b u t e v a l u e s
Pass==1 && /@ a t t r i b u t e / && ( /numeric / | | /r e a l / | | /i n t e g e r / ) {
Numeric [ A t t r ]= 1 ;
Max[ A t t r ]  = −1∗ I n f ;
Min[ A t t r ]  = I n f ;

}

# handle t h e data s e c t i o n f o r pass one
# d e t e r m i n e i f c u r r e n t i n s t a n c e has new min or max f o r t h e a t t r i b u t e
Pass==1 && Data && NF > 1{
f o r ( I i n Numeric ) {
i f ( $I ˜ / ? / ) continue ;
i f ( $I > Max[ I ] ) Max[ I ]= $I ;
i f ( $I < Min[ I ] ) Min[ I ]= $I ;
Seen [ I , $I ] + + ;
}

}

### second pass
# i n i t i a l i z a t i o n s o f second pass
Pass==2 && /@ r e l a t i o n / {
f o r ( I i n Numeric ) {
Div [ I ]= Bins
Bin [ I ] = (Max[ I]− Min[ I ] ) / Div [ I ] ;
p r i n t ”% a t t r i b u t e : ” I ”=−= min : ”Min[ I ] ”=−= max: ”Max[ I ] \
”=−= b i n s : ”Div [ I ] ”=−= s t e p s : ”Bin [ I ]}

}

# handle t h e a t t r i b u t e keywords
Pass==2 && /@ a t t r i b u t e / {
i f ( ( A t t r i n Numeric ) && A t t r != MaxAttr ) {
Names=””;
f o r ( I =2; I<=Div [ A t t r ] ; I ++) Names=Names” , ”I
sub ( /i n t e g e r | numeric | r e a l / ,”{ 1”Names”}” ) ;
}

}

# handle t h e data s e c t i o n f o r pass two
# r e w r i t e t h e numeric f i e l d s on t h e l i n e
Pass==2 && Data && NF> 1{
f o r ( I i n Numeric ) {
i f ( I == MaxAttr ) continue ;
i f ( $I ˜ / ? / )  continue ;
$I=” ”l a b e l ( I , $I ) };

}

# p r i n t t h e r e w r i t t e n r e c o r d
Pass==2 {p r i n t $0}

# f u n c t i o n s
f u n c t i o n round (x) { return i n t (x + (x<0 ? −0.5 : 0 . 5 ) ) }
f u n c t i o n l a b e l ( i , val , x) {
i f ( Bin [ i ]==0 ) return 1 ;
x=round ( ( val− Min[ i ] ) /Bin [ i ] ) ;
i f (x==0) {return 1} e l s e {return x};

} [figure]

Appendix D Script for PKID

PKID Call BASH Script

Usage: pkid datafile

# ! /b i n /bash
myJava=${myJava=”j a v a − Xmx1024M − cp /home/donaldb /b i n /weka . j a r ”}
m y F i l t e r=${ m y F i l t e r=”weka . f i l t e r s . u n s u p e r v i s e d . a t t r i b u t e . P K I D i s c r e t i z e ”}
i n F i l e=${ i n F i l e=”− i ” $1}
myOpts=${myOpts=”−R f i r s t − l a s t − c l a s t ”}
command =${command = $myJava $ m y F i l t e r $ i n F i l e }
$command > o u t . d a t a
p r u n e j a v a o u t . d a t a > out2 . d a t a
c a t out2 . d a t a
rm o u t . d a t a
rm out2 . d a t a
[figure]

Prunejava GAWK Script

# ! /u s r /b i n /gawk − f
#/ ∗ vim: s e t f i l t e y p e=awk : ∗ / −∗− awk −∗−
BEGIN{
FS = ” ∗, ∗”;

}

#S k i p blank and comment l i n e s
{sub ( / \ % . ∗ / ,””)}  # S u b s t i t u t e comments w i t h b l a n k s
{gsub ( / [ \ ’ \”\ ‘ ] / ,”” ,$0)} #Remove any s i n g l e or double q u o t e s from t h i s l i n e
{gsub ( ” ’ ” , ”” , $0)}  #Remove any s i n g l e q u o t e s

/ ˆ [ \ t ]∗$ / {n e x t}  #When blank l i n e observed , go t o t h e n e x t l i n e

/ ˆ j a v a / {n e x t}

{ p r i n t $0} [figure]

Appendix E Script for Entropy-Minimization Heuristic Method

usage: fayyadIrani datafile

# ! /b i n /bash
j a v a − cp $wJar weka . f i l t e r s . s u p e r v i s e d . a t t r i b u t e . D i s c r e t i z e − i $1 − c l a s t
[figure]

Where $wJar is an environmental variable set to the location of the weka.jar file and $1 represents the file presented to the script for discretization.