DecisionTree
Version 3.4.3,   2016-May-14


DecisionTree.py
Version:  3.4.3
Author:  Avinash Kak (kak@purdue.edu)
Date:  2016-May-14

Download Version 3.4.3:     gztar    bztar



         Total number of downloads (all versions) from this website: 9425
            This count is automatically updated at every rotation of
          the weblogs (normally once every two to four days)
          Last updated: Mon Mar 18 06:05:01 EDT 2024
View the main module file in your browser  
View the bagging code in your browser  
View the boosting code in your browser  
View the randomized trees code in your browser  
View the regression tree code in your browser  


CONTENTS:

  CHANGES
  USAGE
  INTRODUCTION
  WHAT PRACTICAL PROBLEM IS SOLVED BY THIS MODULE?
  SYMBOLIC FEATURES VERSUS NUMERIC FEATURES
  FEATURES WITH NOT SO "NICE" STATISTICAL PROPERTIES
  TESTING THE QUALITY OF YOUR TRAINING DATA
  HOW TO MAKE THE BEST CHOICES FOR THE CONSTRUCTOR PARAMETERS
  SOLVING NEEDLE-IN-A-HAYSTACK AND BIG DATA PROBLEMS
  DECISION TREE INTROSPECTION
  METHODS
  THE INTROSPECTION API
  BULK CLASSIFICATION OF DATA RECORDS
  HOW THE CLASSIFICATION RESULTS ARE DISPLAYED
  USING BAGGING
  USING BOOSTING
  USING RANDOMIZED DECISION TREES
  CONSTRUCTING REGRESSION TREES
  GENERATING SYNTHETIC TRAINING DATA
  THE Examples DIRECTORY
  THE ExamplesBagging DIRECTORY
  THE ExamplesBoosting DIRECTORY
  THE ExamplesRandomizedTrees DIRECTORY
  THE ExamplesRegression DIRECTORY
  INSTALLATION
  BUGS
  ACKNOWLEDGMENTS
  ABOUT THE AUTHOR
  COPYRIGHT
 
 
CHANGES:
 
  Version 3.4.3
 
    This version reintroduces 'csv_cleanup_needed' as an optional parameter in
    the module constructor.  This was done in response to several requests
    received from the user community.  (Previously, all line records from a
    CSV file were processed by the 'cleanup_csv()' function no matter what.)
    The main point made by the users was that invoking 'cleanup_csv()'
    when there was no need for CSV clean-up extracted a performance penalty
    when ingesting large database files with tens of thousands of line
    records.  In addition to making 'csv_cleanup_needed' optional, I have 
    also tweaked up the code in the 'cleanup_csv()' method in order to extract
    data from a larger range of messy CSV files.
 
  Version 3.4.2
 
    As with the previous version, all the changes made are confined to the
    part of the code that deals with the calculation of the regression
    coefficients.  Besides general code clean up, I have fixed a couple of
    bugs in this part of the code.  With regard to the new constructor
    parameter 'jacobian_choice' introduced in the previous version, setting
    it to 0 is the best choice for most cases, which causes the regression
    coefficients to be estimated through linear least-squares minimization.
 
  Version 3.4.1
 
    All the changes made in this version relate to the construction of
    regression trees.  I have improved the code that estimates the
    regression coefficients using a combination of linear least-squares and
    gradient descent.  The RegressionTree class now has a new constructor
    parameter called 'jacobian_choice'.
 
  Version 3.4.0
 
    In addition to constructing decision trees, this version of the module
    also allows you to construct regression trees. The regression tree
    capability has been packed into a separate subclass, named
    RegressionTree, of the main DecisionTree class.  The subdirectory
    ExamplesRegression in the main installation directory illustrates how
    you can use this new functionality of the module.
 
  Version 3.3.2:
 
    This version fixes the problem encountered by people when using pickle
    to save a decision tree to a disk file.  The problem was solved by
    moving the nested class DTNode to the module level.
 
  Version 3.3.1:
 
    This version removes certain inefficiencies that had crept into file
    I/O operations in Version 3.3.0.
 
  Version 3.3.0
 
    This version incorporates four very significant upgrades/changes to the
    DecisionTree module: (1) The CSV cleanup is now the default. So you do
    not have to set any special parameters in the constructor calls to
    initiate CSV cleanup. (2) In the form of a new Python class named
    RandomizedTreesForBigData, this module provides you with an easy-to-use
    programming interface for attempting needle-in-a-haystack solutions for
    the case when your training data is overwhelmingly dominated by a
    single class.  You need to set the constructor parameter
    'looking_for_needles_in_haystack' to invoke the logic that constructs
    multiple decision trees, each using the minority class samples along
    with samples drawn randomly from the majority class.  The final
    classification is made through a majority vote from all the decision
    trees.  (3) Assuming you are faced with a big-data problem --- in the
    sense that you have been given a training database with a very large
    number of training records --- the class RandomizedTreesForBigData will
    also let you construct multiple decision trees by pulling training data
    randomly from your training database (without paying attention to the
    relative populations of the classes).  The final classification
    decision for a test sample is based on a majority vote from all the
    decision trees thus constructed.  See the ExamplesRandomizedTrees
    directory for how to use these new features of the module. And,
    finally, (4) Support for the old-style '.dat' training files has been
    dropped in this version.
 
  Version 3.2.4
 
    This version makes it easier to use a CSV training file that violates
    the assumption that a comma be used only to separate the different
    field values in a line record.  Some large econometrics databases use
    double-quoted values for fields, and these values may contain commas
    (presumably for better readability).  This version also allows you to
    specify the leftmost entry in the first CSV record that names all the
    fields. Previously, this entry was required to be an empty
    double-quoted string.  I have also made some minor changes to the
    'get_training_data_from_csv()' method to make it more user friendly for
    large training files that may contain tens of thousands of records.
    When pulling training data from such files, this method prints out a
    dot on the terminal screen for every 10000 records it has processed.
    See the script 'dt_example_involving_csv_cleanup.py' in the Examples
    directory for how to invoke the added functionality for CSV files.
 
  Version 3.2.3
 
    Cleanup of the HTML page for the module.  The implementation code
    and the API remain unchanged.
 
  Version 3.2.2
 
    Incorporates a fix for a minor bug related to exception handling for
    the case when the training data file named in the constructor has an
    incorrect suffix.  Also incorporated in this version is a general
    cleanup of the exception handling code.
 
  Version 3.2.1
 
    Contains a bugfix for a probability calculator function. The bug was
    triggered when a feature did not take on any values whatsoever in all
    of the training data samples for a class --- a condition likely to be
    encountered only rarely, but nonetheless important.
 
  Version 3.2.0
 
    This version brings the boosting capability to the DecisionTree module.
 
  Version 3.0.1
 
    This is a minor revision that smooths out the documentation at a couple
    of important places.  I have also fixed the typos that I discovered
    after the previous version was released.
 
  Version 3.0
 
    Version 3.0 adds bagging to the DecisionTree module. If your training
    dataset is large enough, you can ask the module to construct multiple
    decision trees using data bags extracted from your dataset.  The module
    can show you the results returned by the individual decision trees and
    also the results obtained by taking a majority vote of the
    classification decisions made by the trees.  You can specify any
    arbitrary extent of overlap between the data bags.
 
  Version 2.3.4
 
    There was an error in the packaging of version 2.3.3 of this module.
    The error related to how the `packages' keyword was specified in
    setup.py.  This version fixes that error.
 
  Version 2.3.3:
 
    The purpose of this version is merely to mention that you do NOT need
    to double-quote the entries in your CSV training files. The older
    versions of this module required the rows of a CSV file to be in the
    following sort of a format:
 
  Version 2.3.2:
 
    The introspection capability in this version packs more of a punch.
    For each training data sample, you can now figure out not only the
    decision-tree nodes that are affected directly by that sample, but also
    those nodes that are affected indirectly through the generalization
    achieved by the probabilistic modeling of the data.  The Examples
    directory of this version includes additional scripts that illustrate
    these enhancements to the introspection capability.  See the section
    "The Introspection API" for a declaration of the introspection related
    methods, old and new.
 
  Version 2.3.1:
 
    This version has a bug fix for the decision-tree introspection
    capability that was added to the module in Version 2.3. Also changed in
    this version are the names of the two scripts in the Examples directory
    that illustrate introspection.  The new names are "introspection_at_one
    _node.py" and "introspection_in_a_loop.py".
 
  Version 2.3:
 
    In response to requests from several users, this version includes a new
    capability: You can now ask the module to introspect about the
    classification decisions returned by the decision tree.  Toward that
    end, the module includes a new class named DTIntrospection.  Perhaps
    the most important bit of information you are likely to seek through DT
    introspection is the list of the training samples that fall directly in
    the portion of the feature space that is assigned to a node.  CAVEAT:
    When training samples are non-uniformly distributed in the underlying
    feature space, IT IS POSSIBLE FOR A NODE TO EXIST EVEN 
    WHEN NO TRAINING SAMPLES FALL IN THE PORTION OF THE 
    FEATURE SPACE ASSIGNED TO THE NODE.  (This is the entire 
    point of the generalization achieved by probabilistic modeling of the 
    training data.)  For additional information related to DT introspection, 
    see the section titled "DECISION TREE INTROSPECTION" in this 
    documentation page.
 
  Version 2.2.6:
 
    Removed a serious bug in the method get_training_data_from_dat() that
    is used to read the training data from `.dat' files.  The class naming
    convention internally in the code is that it is a concatenation of the
    header of the column that contains the class labels and the actual
    class name as mentioned in each row of the training data. There was a
    problem with this concatenation. Another very important bug fix was in
    the method probability_of_feature_value(). The probability calculation
    in the previous versions was erroneous for those features that acquired
    zero values.  The users of this module may not have noticed this error
    in the past if the zero values for the features occurred relatively
    infrequently.  This error has now been fixed.
 
  Version 2.2.5:
 
    If you are not using the synthetic data generation feature of this
    module, the changes made in this version do not affect you. The code
    that was changed is all in the class TrainingDataGeneratorNumeric.  The
    changes to this class remove an important bug related to the ordering
    of the feature names that are read from a user-supplied parameter
    file. The basic Decision Tree construction and classification code
    remains unchanged.
 
  Version 2.2.4:
 
    This version should prove more robust when the probability distribution
    for the values of a feature is expected to be heavy-tailed; that is,
    when the supposedly rare observations can occur with significant
    probabilities.  A new option in the DecisionTree constructor lets the
    user specify the precision with which the probability distributions
    are estimated for such features.
 
  Version 2.2.3:
 
    This version fixes a bug that was caused by the explicitly set zero
    values for numerical features being misconstrued as "false" in the
    conditional statements in some of the method definitions.
 
  Version 2.2.2:
 
    In response to requests from users, this version includes scripts in
    the Examples directory that demonstrate how to carry out bulk
    classification of all your test data records placed in a CSV file in
    one fell swoop.  Also included are scripts that demonstrate the same
    for the data records placed in the old-style `.dat' files.  The main
    module code remains unchanged.
 
  Version 2.2.1:
 
    The changes made are all in the part of the module that is used for
    evaluating the quality of training data through a 10-fold cross
    validation test.  The previous version used the default values for the
    constructor parameters when constructing the decision trees in each
    iteration of the test. The new version correctly uses the user-supplied
    values.
 
  Version 2.2:
 
    This version fixes a bug discovered in the best feature calculator
    function. This bug was triggered by certain conditions related to the
    distribution of values for the features in a training data file.
    Additionally, and VERY IMPORTANTLY, Version 2.2 allows you 
    to test the quality of your training data by running a 10-fold
    cross-validation test on the data.  This test divides all of the
    training data into ten parts, with nine parts used for training a
    decision tree and one part used for testing its ability to classify
    correctly. This selection of nine parts for training and one part for
    testing is carried out in all of the ten different possible ways.  This
    testing functionality in Version 2.2 can also be used to find the best
    values to use for the constructor parameters entropy_threshold,
    max_depth_desired, and symbolic_to_numeric_cardinality_threshold.
 
  Version 2.1:
 
    This is a cleaned up version of v. 2.0 of the module. Should run more
    efficiently for large training data files that contain both numeric and
    symbolic features.
 
  Version 2.0:
 
    This was a major rewrite of the DecisionTree module.  This revision was
    prompted by a number of users wanting to see numeric features
    incorporated in the construction of decision trees.  So here it is!
    This version allows you to use either purely symbolic features, or
    purely numeric features, or a mixture of the two. (A feature is numeric
    if it can take any floating-point value over an interval.)
 
  Version 1.7.1:
 
    This version includes a fix for a bug that was triggered by certain
    comment words in a training data file.  This version also includes
    additional safety checks that are useful for catching errors and
    inconsistencies in large training data files that do not lend
    themselves to manual checking for correctness.  As an example, the new
    version makes sure that the number of values you declare in each sample
    record matches the number of features declared at the beginning of the
    training data file.
 
  Version 1.7:
 
    This version includes safety checks on the consistency of the data you
    place in your training data file.  When a training data file contains
    thousands of records, it is difficult to manually check that you used
    the same class names in your sample records that you declared at the
    top of your training file or that the values you have for your features
    are legal vis-a-vis the earlier declarations regarding such values in
    the training file.  Another safety feature incorporated in this version
    is the non-consideration of classes that are declared at the top of the
    training file but that have no sample records in the file.
 
  Version 1.6.1:
 
    Fixed a bug in the method that generates synthetic test data.
 
  Version 1.6:
 
    This version includes several upgrades: The module now includes code
    for generating synthetic training and test data for experimenting with
    the DecisionTree classifier.  Another upgrade in the new version is
    that, after training, a decision tree can now be used in an interactive
    mode in which the user is asked to supply answers for the feature tests
    at the nodes as the classification process descends down the tree.
 
  Version 1.5:
 
    This is a Python 3.x compliant version of the DecisionTree module.
    This version should work with both Python 2.x and Python 3.x.
 
  Version 1.0:
 
    This is a Python implementation of the author's Perl module
    Algorithm::DecisionTree, Version 1.41.  The Python version should work
    faster for large decision trees since it uses probability and entropy
    caching much more extensively than Version 1.41 of the Perl module.
    (Note: I expect my next release of the Perl module to catch up with
    this Python version in terms of performance.)
 
 
USAGE:
 
    If your training data includes numeric features (a feature is numeric
    if it can take any floating point value over an interval), you are
    expected to supply your training data through a CSV file and your call
    for constructing an instance of the DecisionTree class will look like:
 
        training_datafile = "stage3cancer.csv"
 
        dt = DecisionTree.DecisionTree
                        training_datafile = training_datafile,
                        csv_class_column_index = 2,
                        csv_columns_for_features = [3,4,5,6,7,8],
                        entropy_threshold = 0.01,
                        max_depth_desired = 8,
                        symbolic_to_numeric_cardinality_threshold = 10,
                        csv_cleanup_needed = 1,
             )
 
    The constructor option `csv_class_column_index' informs the module as
    to which column of your CSV file contains the class label.  THE 
    COLUMN INDEXING IS ZERO BASED.  The constructor option
    `csv_columns_for_features' specifies which columns are to be used for
    feature values.  The first row of the CSV file must specify the names
    of the features.  See examples of CSV files in the `Examples'
    subdirectory.
 
    The option `symbolic_to_numeric_cardinality_threshold' is also
    important.  For the example shown above, if an ostensibly numeric
    feature takes on only 10 or fewer different values in your training
    datafile, it will be treated like a symbolic feature.  The option
    `entropy_threshold' determines the granularity with which the entropies
    are sampled for the purpose of calculating entropy gain with a
    particular choice of decision threshold for a numeric feature or a
    feature value for a symbolic feature.  
 
    The option `csv_cleanup_needed' is by default set to 0.  If you set it
    to 1, that would cause all line records in your CSV file to be
    "sanitized" before they are used for constructing a decision tree.  You
    need this option if your CSV file uses double-quoted field names and
    field values in the line records and if such double-quoted strings are
    allowed to include commas for, presumably, better readability.
 
    After you have constructed an instance of the DecisionTree class as
    shown above, you read in the training data file and initialize the
    probability cache by calling:
 
        dt.get_training_data()
        dt.calculate_first_order_probabilities()
        dt.calculate_class_priors()
 
    Next you construct a decision tree for your training data by calling:
 
        root_node = dt.construct_decision_tree_classifier()
 
    where root_node is an instance of the DTNode class that is also defined
    in the module file.  Now you are ready to classify a new data record.
    Let's say that your data record looks like:
 
        test_sample  = ['g2 = 4.2',
                        'grade = 2.3',
                        'gleason = 4',
                        'eet = 1.7',
                        'age = 55.0',
                        'ploidy = diploid']
 
    You can classify it by calling:
 
        classification = dt.classify(root_node, test_sample)
 
    The call to `classify()' returns a reference to a hash whose keys are
    the class names and the values the associated classification
    probabilities.  This hash also includes another key-value pair for the
    solution path from the root node to the leaf node at which the final
    classification was carried out.
 
    A decision tree can quickly become much too large (and much too slow to
    construct and to yield classification results) if the total number of
    features is large and/or if the number of different possible values for
    the symbolic features is large.  You can control the size of the tree
    through the constructor options `entropy_threshold' and
    `max_depth_desired'. The latter option sets the maximum depth of your
    decision tree to max_depth_desired value.  The parameter
    `entropy_threshold' sets the granularity with which the entropies are
    sampled.  Its default value is 0.001.  The larger the value you choose
    for entropy_threshold, the smaller the tree.
 
 
INTRODUCTION:
 
    DecisionTree is a Python module for constructing a decision tree from a
    training data file containing multidimensional data in the form of a
    table. In one form or another, decision trees have been around for over
    fifty years. From a statistical perspective, they are closely related
    to classification and regression by recursive partitioning of
    multidimensional data. Early work that demonstrated the usefulness of
    such partitioning of data for classification and regression can be
    traced to the work of Terry Therneau in the early 1980's in the
    statistics community, and to the work of Ross Quinlan in the mid 1990's
    in the machine learning community,
 
    For those not familiar with decision tree ideas, the traditional way to
    classify multidimensional data is to start with a feature space whose
    dimensionality is the same as that of the data.  Each feature measures
    a specific attribute of an entity.  You use the training data to carve
    up the feature space into different regions, each corresponding to a
    different class.  Subsequently, when you try to classify a new data
    sample, you locate it in the feature space and find the class label of
    the region to which it belongs.  One can also give the data point the
    same class label as that of the nearest training sample. This is
    referred to as the nearest neighbor classification. There exist
    hundreds of variations of varying power on these two basic approaches
    to the classification of multidimensional data.
 
    A decision tree classifier works differently.  When you construct a
    decision tree, you select for the root node a feature test that
    partitions the training data in a way that causes maximal
    disambiguation of the class labels associated with the data.  In terms
    of information content as measured by entropy, such a feature test
    would cause maximum reduction in class entropy in going from all of the
    training data taken together to the data as partitioned by the feature
    test.  You then drop from the root node a set of child nodes, one for
    each partition of the training data created by the feature test at the
    root node. When your features are purely symbolic, you'll have one
    child node for each value of the feature chosen for the feature test at
    the root.  When the test at the root involves a numeric feature, you
    find the decision threshold for the feature that best bipartitions the
    data and you drop from the root node two child nodes, one for each
    partition.  Now at each child node you pose the same question that you
    posed when you found the best feature to use at the root: Which feature
    at the child node in question would maximally disambiguate the class
    labels associated with the training data corresponding to that child
    node?
 
    As the reader would expect, the two key steps in any approach to
    decision-tree based classification are the construction of the decision
    tree itself from a file containing the training data, and then using
    the decision tree thus obtained for classifying new data.
 
    What is cool about decision tree classification is that it gives you
    soft classification, meaning it may associate more than one class label
    with a given data record.  When this happens, it may mean that your
    classes are indeed overlapping in the underlying feature space.  It
    could also mean that you simply have not supplied sufficient training
    data to the decision tree classifier.  For a tutorial introduction to
    how a decision tree is constructed and used, see
 
    https://engineering.purdue.edu/kak/Tutorials/DecisionTreeClassifiers.pdf
 
 
WHAT PRACTICAL PROBLEM IS SOLVED BY THIS MODULE?
 
    If you are new to the concept of a decision tree, their practical
    utility is best understood with an example that only involves symbolic
    features.  However, as mentioned earlier, versions 2.0 and higher of
    this module handle both symbolic and numeric features.
 
    Consider the following scenario: Let's say you are running a small
    investment company that employs a team of stockbrokers who make
    buy/sell decisions for the customers of your company.  Assume that your
    company has asked the traders to make each investment decision on the
    basis of the following five criteria:
 
            price_to_earnings_ratio   (P_to_E)
 
            price_to_sales_ratio      (P_to_S)
 
            return_on_equity          (R_on_E)
 
            market_share              (M_S)
 
            sentiment                 (S)
 
    Since you are the boss, you keep track of the buy/sell decisions made
    by the individual traders.  But one unfortunate day, all of your
    traders decide to quit because you did not pay them enough.  So what
    are you to do?  If you had a module like the one here, you could still
    run your company and do so in such a way that your company would, on
    the average, perform better than any of the individual traders who
    worked for you previously.  This is what you would need to do: You
    would pool together the individual trader buy/sell decisions you
    accumulated during the last one year.  This pooled information is
    likely to look like:
 
      example      buy/sell     P_to_E     P_to_S     R_on_E     M_S     S
      ====================================================================
 
      example_1     buy          high       low        medium    low    high
      example_2     buy          medium     medium     low       low    medium
      example_3     sell         low        medium     low       high   low
      ....
      ....
 
    This would constitute your training data. Assuming CSV formatting for
    the data in a file called 'training.csv', you would need to feed this
    file into the module by calling:
 
        dt = DecisionTree( training_datafile = "training.csv", .... )
 
        dt.get_training_data()
 
        dt.calculate_first_order_probabilities()
 
        dt.calculate_class_priors()
 
    Subsequently, you would construct a decision tree by calling:
 
        root_node = dt.construct_decision_tree_classifier()
 
    Now you and your company (with practically no employees) are ready to
    service the customers again. Suppose your computer needs to make a
    buy/sell decision about an investment prospect that is best described
    by:
 
        price_to_earnings_ratio   =  low
        price_to_sales_ratio      =  very_low
        return_on_equity          =  none
        market_share              =  medium    
        sentiment                 =  low
 
    All that your computer would need to do would be to construct a data
    record like
 
        test_case = [ 'P_to_E=low', 
                      'P_to_S=very_low', 
                      'R_on_E=none',
                      'M_S=medium',
                      'S=low'  ]
 
    and call the decision tree classifier you just constructed by
 
        classification = dt.classify(root_node, test_case)
 
        print "Classification: ", classification
 
    The answer returned will be 'buy' and 'sell', along with the associated
    probabilities.  So if the probability of 'buy' is considerably greater
    than the probability of 'sell', that's what you should instruct your
    computer to do.
 
    The chances are that, on the average, this approach would beat the
    performance of any of your individual traders who worked for you
    previously since the buy/sell decisions made by the computer would be
    based on the collective wisdom of all your previous traders.
    DISCLAIMER: There is obviously a lot more to good investing than what
    is captured by the silly little example here. However, it does convey
    the sense in which the current module can be used.
 
 
SYMBOLIC FEATURES VERSUS NUMERIC FEATURES:
 
    A feature is symbolic when its values are compared using string
    comparison operators.  By the same token, a feature is numeric when its
    values are compared using numeric comparison operators.  Having said
    that, features that take only a small number of numeric values in the
    training data can be treated symbolically provided you are careful
    about handling their values in the test data.  At the least, you have
    to set the test data value for such a feature to its closest value in
    the training data.  For those numeric features that the module is
    allowed to treat symbolically, this snapping of the values of the
    features in the test data to the small set of values in the training
    data is carried out automatically by the module.  That is, after a user
    has told the module which numeric features to treat symbolically, the
    user need not worry about how the feature values appear in the test
    data.
 
    The constructor parameter symbolic_to_numeric_cardinality_threshold
    lets you tell the module when to consider an otherwise numeric feature
    symbolically. Suppose you set this parameter to 10, that means that all
    numeric looking features that take 10 or fewer different values in the
    training datafile will be considered to be symbolic features.
    
    See the tutorial at
 
    https://engineering.purdue.edu/kak/Tutorials/DecisionTreeClassifiers.pdf
 
    for further information on the implementation issues related to the
    symbolic and numeric features.
 
 
FEATURES WITH NOT SO "NICE" STATISTICAL PROPERTIES:
 
    For the purpose of estimating the probabilities, it is necessary to
    sample the range of values taken on by a numerical feature. For
    features with "nice" statistical properties, this sampling interval is
    set to the median of the differences between the successive feature
    values in the training data.  (Obviously, as you would expect, you
    first sort all the values for a feature before computing the successive
    differences.)  This logic will not work for the sort of a feature
    described below.
 
    Consider a feature whose values are heavy-tailed, and, at the same
    time, the values span a million to one range.  What I mean by
    heavy-tailed is that rare values can occur with significant
    probabilities.  It could happen that most of the values for such a
    feature are clustered at one of the two ends of the range. At the same
    time, there may exist a significant number of values near the end of
    the range that is less populated.  (Typically, features related to
    human economic activities --- such as wealth, incomes, etc. --- are of
    this type.)  With the logic described in the previous paragraph, you
    could end up with a sampling interval that is much too small, which
    could result in millions of sampling points for the feature if you are
    not careful.
 
    Beginning with Version 2.2.4, you have two options in dealing with such
    features.  You can choose to go with the default behavior of the
    module, which is to sample the value range for such a feature over a
    maximum of 500 points.  Or, you can supply an additional option to the
    constructor that sets a user-defined value for the number of points to
    use.  The name of the option is "number_of_histogram_bins".  The
    following script
 
          construct_dt_for_heavytailed.py
 
    in the Examples directory shows an example of how to call the
    constructor of the module with the "number_of_histogram_bins" option.
 
 
TESTING THE QUALITY OF YOUR TRAINING DATA:
 
    Starting with version 2.2, the module includes a new class named
    EvalTrainingData, derived from the main class DecisionTree, that runs a
    10-fold cross-validation test on your training data to test its ability
    to discriminate between the classes mentioned in the training file.
 
    The 10-fold cross-validation test divides all of the training data into
    ten parts, with nine parts used for training a decision tree and one
    part used for testing its ability to classify correctly. This selection
    of nine parts for training and one part for testing is carried out in
    all of the ten different possible ways.  
 
    The following code fragment illustrates how you invoke the testing
    function of the EvalTrainingData class:
 
        training_datafile = "training3.csv"
        eval_data = DecisionTree.EvalTrainingData(
                        training_datafile = training_datafile,
                        csv_class_column_index = 1,
                        csv_columns_for_features = [2,3],
                        entropy_threshold = 0.01,
                        max_depth_desired = 3,
                        symbolic_to_numeric_cardinality_threshold = 10,
                        csv_cleanup_needed = 1,
                    )
 
        eval_data.get_training_data()
        eval_data.evaluate_training_data()
 
    The last statement above prints out a Confusion Matrix and the value of
    Training Data Quality Index on a scale of 100, with 100 designating
    perfect training data.  The Confusion Matrix shows how the different
    classes were misidentified in the 10-fold cross-validation test.
 
    This testing functionality can also be used to find the best values to
    use for the constructor parameters entropy_threshold,
    max_depth_desired, and symbolic_to_numeric_cardinality_threshold.
 
    The following two scripts in the Examples directory illustrate the use
    of the EvalTrainingData class for testing the quality of your data:
 
        evaluate_training_data1.py
 
        evaluate_training_data2.py
 
    IMPORTANT: These data evaluation scripts produce reliable indicators of
    the quality of your data only when there is a rough parity between the
    number of training samples available for the different data classes.
 
 
HOW TO MAKE THE BEST CHOICES FOR THE CONSTRUCTOR PARAMETERS:
 
    Assuming your training data is good, the quality of the results you get
    from a decision tree would depend on the choices you make for the
    constructor parameters entropy_threshold, max_depth_desired, and
    symbolic_to_numeric_cardinality_threshold.  You can optimize your
    choices for these parameters by running the 10-fold cross-validation
    test that is made available in Versions 2.2 and higher through the new
    class EvalTrainingData that is included in the module file.  A
    description of how to run this test is in the section titled "TESTING
    THE QUALITY OF YOUR TRAINING DATA" of this document.
 
 
SOLVING NEEDLE-IN-A-HAYSTACK AND BIG DATA PROBLEMS:
 
    Machine learning algorithms, in general, run into difficulties when
    there is gross imbalance in how many training samples are available for
    the different data classes --- especially when the different data
    classes are not linearly separable in the underlying feature
    space. Starting with Version 3.3.0 of this module, you can try to use
    the new Python class RandomizedTreesForBigData for solving such
    problems provided you set the following two constructor parameters:
 
        looking_for_needles_in_haystack
 
        how_many_trees
 
    At the moment, RandomizedTreesForBigData is programmed for just binary
    classification. It first figures out the population imbalance between
    the majority data class and the minority data class in your dataset.
    Subsequently, by mixing the minority training samples with randomly
    drawn samples from the majority data class, it constructs a collection
    of training datasets for 'how_many_trees' number of decision trees.  A
    new data sample to be classified is fed to each of these decision trees
    and the final classification based on majority voting by all the trees.
    You must set 'looking_for_needles_in_haystack = 1' in the constructor
    call for this logic to work.  You'd also want to experiment with with
    the option 'how_many_trees' to figure out the best value for this
    parameter.  Searching for a needle in a haystack is obviously a good
    metaphor for these types of data classification problems.
 
    The RandomizedTreesForBigData class can also be used for solving big
    data problems if you have access to a very large training database.
    You can solve such problems by constructing multiple decision trees,
    each based on a training dataset drawn randomly from the large training
    database (without paying attention to population imbalances).
    Subsequently, the final classification for a new data sample can be
    based on majority voting by all the trees.  In order to use this
    functionality, you need to set the following two constructor parameters
    of this class:
 
        how_many_training_samples_per_tree
 
        how_many_trees
 
 
DECISION TREE INTROSPECTION:
 
    Starting with Version 2.3, you can ask the DTIntrospection class of the
    module to explain the classification decisions made at the different
    nodes of the decision tree.
 
    Perhaps the most important bit of information you are likely to seek
    through DT introspection is the list of the training samples that fall
    directly in the portion of the feature space that is assigned to a
    node.
 
    However, note that, when training samples are non-uniformly distributed
    in the underlying feature space, it is possible for a node to exist
    even when there are no training samples in the portion of the feature
    space assigned to the node.  That is because the decision tree is
    constructed from the probability densities estimated from the training
    data.  When the training samples are non-uniformly distributed, it is
    entirely possible for the estimated probability densities to be
    non-zero in a small region around a point even when there are no
    training samples specifically in that region.  (After you have created
    a statistical model for, say, the height distribution of people in a
    community, the model may return a non-zero probability for the height
    values in a small interval even if the community does not include a
    single individual whose height falls in that interval.)
 
    That a decision-tree node can exist even where there are no training samples in
    the portion of the feature space that belongs to that node is an important
    indication of the generalization ability of a decision-tree based classifier.
 
    In light of the explanation provided above, before the DTIntrospection
    class supplies any answers at all, it asks you to accept the fact that
    features can take on non-zero probabilities at a point in the feature
    space even though there are zero training samples at that point (or in
    a small region around that point).  If you do not accept this
    rudimentary fact, the introspection class will not yield any answers
    (since you are not going to believe the answers anyway).
 
    The point made above implies that the path leading to a node in the
    decision tree may test a feature for a certain value or threshold
    despite the fact that the portion of the feature space assigned to that
    node is devoid of any training data.
 
    See the following three scripts in the Examples directory for how to
    carry out DT introspection:
 
        introspection_in_a_loop_interactive.py
 
        introspection_show_training_samples_at_all_nodes_direct_influence.py
 
        introspection_show_training_samples_to_nodes_influence_propagation.py
 
    The first script places you in an interactive session in which you will
    first be asked for the node number you are interested in.
    Subsequently, you will be asked for whether or not you are interested
    in specific questions that the introspection can provide answers
    for. The second script descends down the decision tree and shows for
    each node the training samples that fall directly in the portion of the
    feature space assigned to that node.  The third script shows for each
    training sample how it affects the decision-tree nodes either directly
    or indirectly through the generalization achieved by the probabilistic
    modeling of the data.
 
    The output of the script introspection_show_training_samples_at_all_
    nodes_direct_influence.py looks like:
 
        Node 0: the samples are: None
        Node 1: the samples are: ['sample_46', 'sample_58']
        Node 2: the samples are: ['sample_1', 'sample_4', 'sample_7', .....]
        Node 3: the samples are: []
        Node 4: the samples are: []
        ...
        ...            
    
    The nodes for which no samples are listed come into existence through
    the generalization achieved by the probabilistic modeling of the data.
 
    The output produced by the script introspection_show_training_samples_
    to_nodes_influence_propagation.py looks like
 
        sample_1:                                                                 
           nodes affected directly: [2, 5, 19, 23]                                
           nodes affected through probabilistic generalization:                   
                2=> [3, 4, 25]                                                    
                    25=> [26]                                                     
                5=> [6]                                                           
                    6=> [7, 13]                                                   
                        7=> [8, 11]                                               
                            8=> [9, 10]                                           
                            11=> [12]                                             
                        13=> [14, 18]                                             
                            14=> [15, 16]                                         
                                16=> [17]                                         
                19=> [20]                                                         
                    20=> [21, 22]                                                 
                23=> [24]                                                         
                                 
        sample_4:                                                                 
           nodes affected directly: [2, 5, 6, 7, 11]                              
           nodes affected through probabilistic generalization:                   
                2=> [3, 4, 25]                                                    
                    25=> [26]                                                     
                5=> [19]                                                          
                    19=> [20, 23]                                                 
                        20=> [21, 22]                                             
                        23=> [24]                                                 
                6=> [13]                                                          
                    13=> [14, 18]                                                 
                        14=> [15, 16]                                             
                            16=> [17]                                             
                7=> [8]                                                           
                    8=> [9, 10]                                                   
                11=> [12]                                                         
                                                                                  
        ...                                                                       
        ...  
        ...
    
    For each training sample, the display shown above first presents the
    list of nodes that are directly affected by the sample.  A node is
    affected directly by a sample if the latter falls in the portion of the
    feature space that belongs to the former.  Subsequently, for each
    training sample, the display shows a subtree of the nodes that are
    affected indirectly by the sample through the generalization achieved
    by the probabilistic modeling of the data.  In general, a node is
    affected indirectly by a sample if it is a descendant of another node
    that is affected directly.
 
    Also see the section titled "The Introspection API" regarding how to
    invoke the introspection capabilities of the module in your own code.
 
 
METHODS:
 
    The module provides the following methods for constructing a decision
    tree from training data in a disk file, and for data classification with
    the decision tree.
 
 
    Constructing a decision tree:
 
            dt = DecisionTree
                       training_datafile = training_datafile,
                       csv_class_column_index = 2,
                       csv_columns_for_features = [3,4,5,6,7,8],
                       entropy_threshold = 0.01,
                       max_depth_desired = 8,
                       symbolic_to_numeric_cardinality_threshold = 10,
                       csv_cleanup_needed = 1,
                 )
    
        This yields a new instance of the DecisionTree class.  For this
        call to make sense, the training data in the training datafile must
        conform to the traditional CSV format.  For example, the first
        record must list the features to be used for classification.  The
        first column for all rows must carry a unique integer identifier
        for each data record.
    
        The constructor option csv_class_column_index supplies to the
        module zero-based index of the column that contains the class label
        for the training data records. In the example shown above, the
        class labels are in the third column.  The option
        csv_columns_for_features tells the module which of the features are
        supposed to be used for decision tree construction.  The
        constructor option max_depth_desired sets the maximum depth of the
        decision tree. The parameter entropy_threshold sets the granularity
        with which the entropies are sampled.  The parameter
        symbolic_to_numeric_cardinality_threshold allows the module to
        treat an otherwise numeric feature symbolically if it only takes a
        small number of different values in the training data file.  For
        the constructor call shown above, if a feature takes on only 10 or
        fewer different values in the training data file, it will be
        treated like a symbolic feature.
    
 
    The constructor parameters:
 
        training_datafile:
    
            This parameter supplies the name of the file that contains the
            training data.  This must be a CSV file if your training data
            includes both numeric and symbolic features. 
    
        csv_class_column_index:
    
            When using a CSV file for your training data, this parameter
            supplies the zero-based column index for the column that contains
            the class label for each data record in the training file.
 
        csv_cleanup_needed:
 
            You need to set this parameter to 1 if your CSV file has double
            quoted strings (which may include commas) as values for the
            fields and if such values are allowed to include commas for,
            presumably, better readability.
    
        csv_columns_for_features:
    
            When using a CSV file for your training data, this parameter
            supplies a list of columns corresponding to the features you wish
            to use for decision tree construction.  Each column is specified by
            its zero-based index.
    
        entropy_threshold:
    
            This parameter sets the granularity with which the entropies are
            sampled by the module.  For example, a feature test at a node in
            the decision tree is acceptable if the entropy gain achieved by the
            test exceeds this threshold.  The larger the value you choose for
            this parameter, the smaller the tree.  Its default value is 0.001.
    
        max_depth_desired:
    
            This parameter sets the maximum depth of the decision tree.  For
            obvious reasons, the smaller the value you choose for this
            parameter, the smaller the tree.
    
        symbolic_to_numeric_cardinality_threshold:
    
            This parameter allows the module to treat an otherwise numeric
            feature symbolically if the number of different values the feature
            takes in the training data file does not exceed the value of this
            parameter.
    
        number_of_histogram_bins:
    
            This parameter gives the user the option to set the number of
            points at which the value range for a feature should be sampled
            for estimating the probabilities.  This parameter is especially
            effective for those features that occupy a large value range
            and whose probability distributions are heavy tailed.  THIS
            PARAMETER IS ALSO IMPORTANT WHEN YOU HAVE A 
            VERY LARGE TRAINING DATASET: In general, the larger 
            the dataset, the smaller the smallest difference between any
            two values for a numeric feature in relation to the overall
            range of values for that feature. In such cases, the module may
            use too large a number of bins for estimating the probabilities
            and that may slow down the calculation of the decision tree.
            You can get around this difficulty by explicitly giving a value
            to the 'number_of_histogram_bins' parameter.
 
        You can choose the best values to use for the constructor parameters by
        running a 10-fold cross-validation test on your training data through
        the embedded class EvalTrainingData that comes with Versions 2.2 and
        higher of this module.  See the section "TESTING THE QUALITY OF YOUR
        TRAINING DATA" of this document page.
    
 
    Reading in the training data:
 
        After you have constructed a new instance of the DecisionTree class,
        you must now read in the training data that is contained in the file
        named above.  This you do by:
    
            dt.get_training_data()
    
        IMPORTANT: The training data file must be in a format that makes sense
        to the decision tree constructor.  If you use numeric features, you
        must use a CSV file for supplying the training data.  The first row of
        such a file must name the features and it must begin with the empty
        string `""' as shown in the `stage3cancer.csv' file in the Examples
        subdirectory.  The first column for all subsequent rows must carry a
        unique integer identifier for each training record.
    
 
    Initializing the probability cache:
 
        After a call to the constructor and the get_training_data() method, you
        must call the following methods for initializing the probabilities:
 
            dt.calculate_first_order_probabilities()
            dt.calculate_class_priors()
    
 
    Displaying the training data:
 
        If you wish to see the training data that was just digested by the
        module, call
 
            dt.show_training_data() 
 
 
    Constructing a decision-tree classifier:
 
        After the training data is ingested, it is time to construct a decision
        tree classifier.  This you do by
 
            root_node = dt.construct_decision_tree_classifier()
    
        This call returns an instance of type DTNode.  The DTNode class is
        defined within the main package file, at its end.  So, don't forget,
        that root_node in the above example call will be instantiated to an
        instance of type DTNode.
    
 
    Displaying the decision tree:
 
        You display a decision tree by calling
 
            root_node.display_decision_tree("   ")
    
        This displays the decision tree in your terminal window by using a
        recursively determined offset for each node as the display routine
        descends down the tree.
    
        I have intentionally left the syntax fragment root_node in the above
        call to remind the reader that display_decision_tree() is NOT called on
        the instance of the DecisionTree we constructed earlier, but on the
        Node instance returned by the call to
        construct_decision_tree_classifier().
    
 
    Classifying new data:
 
        You classify new data by first constructing a new data record:
 
            test_sample  = ['g2 = 4.2',
                            'grade = 2.3',
                            'gleason = 4',
                            'eet = 1.7',
                            'age = 55.0',
                            'ploidy = diploid']
    
        and calling the classify() method as follows:
 
            classification = dt.classify(root_node, test_sample)
    
        where, again, root_node is an instance of type Node that was returned
        by calling construct_decision_tree_classifier().  The variable
        classification is a dictionary whose keys are the class labels and
        whose values the associated probabilities.  You can print it out by
 
            print "Classification: ", classification
    
 
    Displaying the number of nodes created:
 
        You can print out the number of nodes in a decision tree by calling
 
            root_node.how_many_nodes()
    
 
    Using the decision tree interactively:
 
        Starting with Version 1.6 of the module, you can use the DecisionTree
        classifier in an interactive mode.  In this mode, after you have
        constructed the decision tree, the user is prompted for answers to the
        questions regarding the feature tests at the nodes of the tree.
        Depending on the answer supplied by the user at a node, the classifier
        takes a path corresponding to the answer to descend down the tree to
        the next node, and so on.  The following method makes this mode
        possible.  Obviously, you can call this method only after you have
        constructed the decision tree.
 
            dt.classify_by_asking_questions(root_node)
 
    
THE INTROSPECTION API:
 
    To construct an instance of DTIntrospection, you call
 
        introspector = DecisionTree.DTIntrospection(dt)
 
    where you supply the instance of the DecisionTree class you used for
    constructing the decision tree through the parameter dt.  After you
    have constructed an instance of the introspection class, you must
    initialize it by
 
        introspector.initialize()
 
    on the introspector instance. Subsequently, you can invoke either of
    the following methods:
 
        introspector.explain_classification_at_one_node(node)
 
        introspector.explain_classifications_at_multiple_nodes_interactively()
 
    depending on whether you want introspection at a single specified node
    or inside an infinite loop for an arbitrary number of nodes.
 
    If you want to output a tabular display that shows for each node in the
    decision tree all the training samples that fall in the portion of the
    feature space that belongs to that node, call
 
        introspector.display_training_samples_at_all_nodes_direct_influence_only()
 
    If you want to output a tabular display that shows for each training
    sample a list of all the nodes that are affected directly AND
    indirectly by that sample, call
 
        introspector.display_training_training_samples_to_nodes_influence_propagation()
 
    A training sample affects a node directly if the sample falls in the
    portion of the features space assigned to that node. On the other hand,
    a training sample is considered to affect a node indirectly if the node
    is a descendant of a node that is affected directly by the sample.
 
 
BULK CLASSIFICATION OF DATA RECORDS:
 
    For large test datasets, you would obviously want to process an entire
    file of test data at a time. The following scripts in the Examples
    directory illustrate how you can do that:
 
        classify_test_data_in_a_file_numeric.py 
        classify_test_data_in_a_file_symbolic.py
 
    These scripts require three command-line arguments, the first argument
    names the training datafile, the second the test datafile, and the
    third the file in which the classification results are to be deposited.
    The first script above is for the case of numeric/symbolic features and
    the second for the purely symbolic features.  An important point to
    remember when using these scripts for bulk classification is that the
    test file must have a column for class labels.  In real-life
    situations, obviously, the entries in that column in the test file will
    be just the empty string "".
 
    The other examples directories, ExamplesBagging, ExamplesBoosting, and
    ExamplesRandomizedTrees, also contain scripts that illustrate how to
    carry out bulk classification of data records when you wish to take
    advantage of bagging, boosting, or tree randomization.  In their
    respective directories, these scripts are named:
                                                                                                                    
        bagging_for_bulk_classification.pl                                                                              
        boosting_for_bulk_classification.pl                                                                             
        classify_database_records.pl 
 
 
HOW THE CLASSIFICATION RESULTS ARE DISPLAYED:
 
    It depends on whether you apply the classifier at once to all the data
    records in a file, or whether you feed one data record at a time into
    the classifier.
 
    In general, the classifier returns soft classification for a test data
    record.  What that means is that, in general, the classifier will list
    all the classes to which a given data record could belong and the
    probability of each such class label for the data record. Run the
    examples scripts in the Examples directory to see how the output of
    classification can be displayed.
    
    With regard to the soft classifications returned by this classifier, if
    the probability distributions for the different classes overlap in the
    underlying feature space, you would want the classifier to return all
    of the applicable class labels for a test data record along with the
    corresponding class probabilities.  (However, keep in mind the fact
    that the decision tree classifier may associate significant
    probabilities with multiple class labels for a given test data record
    if the training file contains an inadequate number of training samples
    for one or more classes.)  The good thing is that the classifier would
    not lie to you (unlike, say, a hard classification rule that would
    return a single class label corresponding to the partitioning of the
    underlying feature space).  The decision tree classifier will give you
    the best classification that can be made given the training data you
    feed into it.
 
 
USING BAGGING:
 
    Starting with Version 3.0, you can use the class
    DecisionTreeWithBagging that comes with the module to incorporate
    bagging in your decision tree based classification.  Bagging means
    constructing multiple decision trees for different (possibly
    overlapping) segments of the data extracted from your training dataset
    and then aggregating the decisions made by the individual decision
    trees for the final classification.  The aggregation of the
    classification decisions can average out the noise and bias that may
    otherwise affect the classification decision obtained from just one
    tree.
 
    Whether or not you get any benefits from bagging depends on: (1) If
    your original training dataset is large enough and sufficiently varied
    to capture all of the real-world statistical variations within and
    between the classes; and (2) no single feature is too dominant in
    establishing inter-class discriminations.
 
    Calling the bagging constructor:
 
        A typical call to the constructor for the DecisionTreeWithBagging
        class looks like:
    
            import DecisionTreeWithBagging
    
            dtbag = DecisionTreeWithBagging.DecisionTreeWithBagging( 
                            training_datafile = training_datafile,
                            csv_class_column_index = 2,
                            csv_columns_for_features = [3,4,5,6,7,8],
                            entropy_threshold = 0.01,
                            max_depth_desired = 8,
                            symbolic_to_numeric_cardinality_threshold = 10,
                            how_many_bags = 4,
                            bag_overlap_fraction = 0.20,
                            csv_cleanup_needed = 1,
                    )
    
        Note in particular the following two constructor parameters:
 
            how_many_bags
    
            bag_overlap_fraction
    
        where, as the name implies, the parameter how_many_bags controls
        how many bags (and, therefore, how many decision trees) will be
        constructed from your training dataset; and where the parameter
        bag_overlap_fraction controls the degree of overlap between the
        bags.  To understand what exactly is achieved by setting the
        parameter bag_overlap_fraction to 0.2 in the above example, let's
        say that the non-overlapping partitioning of the training data
        between the bags results in 100 training samples per bag. With
        bag_overlap_fraction set to 0.2, additional 20 samples drawn
        randomly from the other bags will be added to the data in each bag.
    
        Here are the methods defined for the DecisionTreeWithBagging class;
    
    get_training_data_for_bagging():
 
        This method reads your training datafile, randomizes it, and then
        partitions it into the specified number of bags.  Subsequently, if
        the constructor parameter bag_overlap_fraction is non-zero, it adds
        to each bag additional samples drawn at random from the other bags.
        The number of these additional samples added to each bag is
        controlled by the constructor parameter bag_overlap_fraction.  If
        this parameter is set to, say, 0.2, the size of each bag will grow
        by 20% with the samples drawn from the other bags.
    
    show_training_data_in_bags()
 
        Shows for each bag the names of the training data samples in that
        bag.
 
    calculate_first_order_probabilities()
 
        Calls on the appropriate methods of the main DecisionTree class to
        estimate the first-order probabilities from the samples in each
        bag.
 
    calculate_class_priors()
 
        Calls on the appropriate method of the main DecisionTree class to
        estimate the class priors for the training data samples in each
        bag.
 
    construct_decision_trees_for_bags()
 
        Calls on the appropriate method of the main DecisionTree class to
        construct a decision tree from the training data samples in each
        bag.
 
    display_decision_trees_for_bags()
 
        Displays separately the decision tree for each bag.
 
    classify_with_bagging( test_sample )
 
        Calls on the appropriate methods of the main DecisionTree class to
        classify the argument test sample.
 
    display_classification_results_for_each_bag()
 
        Displays separately the classification decision made by the
        decision tree constructed for each bag.
 
    get_majority_vote_classification()
 
        Using majority voting, this method aggregates the classification
        decisions made by the individual decision trees into a single
        decision.
 
    See the example scripts in the ExamplesBagging directory for how to
    call the methods listed above for classifying individual data samples
    and for bulk classification when you place all your test samples in a
    single file.
 
 
USING BOOSTING:
 
    Starting with Version 3.2.0, you can use the class BoostedDecisionTree
    for constructing a boosted decision-tree classifier.  Boosting results
    in a cascade of decision trees in which each decision tree is
    constructed with samples that are mostly those that are misclassified
    by the previous decision tree.  To be precise, you create a probability
    distribution over the training samples for the selection of samples for
    training each decision tree in the cascade.  To start out, the
    distribution is uniform over all of the samples. Subsequently, this
    probability distribution changes according to the misclassifications by
    each tree in the cascade: if a sample is misclassified by a given tree
    in the cascade, the probability of its being selected for training the
    next tree is increased significantly.  You also associate a trust
    factor with each decision tree depending on its power to classify
    correctly all of the training data samples.  After a cascade of
    decision trees is constructed in this manner, you construct a final
    classifier that calculates the class label for a test data sample by
    taking into account the classification decisions made by each
    individual tree in the cascade, the decisions being weighted by the
    trust factors associated with the individual classifiers.  These
    boosting notions --- generally referred to as the AdaBoost algorithm
    --- are based on a now celebrated paper "A Decision-Theoretic
    Generalization of On-Line Learning and an Application to Boosting" by
    Yoav Freund and Robert Schapire that appeared in 1995 in the
    Proceedings of the 2nd European Conf. on Computational Learning Theory.
    For a tutorial introduction to AdaBoost, see
 
    https://engineering.purdue.edu/kak/Tutorials/AdaBoost.pdf
 
    Keep in mind the fact that, ordinarily, the theoretical guarantees
    provided by boosting apply only to the case of binary classification.
    Additionally, your training dataset must capture all of the significant
    statistical variations in the classes represented therein.
 
 
    Calling the BoostedDecisionTree constructor:
 
        If you'd like to experiment with boosting, a typical call to the
        constructor for the BoostedDecisionTree class looks like:
 
            import BoostedDecisionTree
            training_datafile = "training6.csv"
 
            boosted = BoostedDecisionTree.BoostedDecisionTree(
                            training_datafile = training_datafile,
                            csv_class_column_index = 1,
                            csv_columns_for_features = [2,3],
                            entropy_threshold = 0.01,
                            max_depth_desired = 8,
                            symbolic_to_numeric_cardinality_threshold = 10,
                            how_many_stages = 4,
                            csv_cleanup_needed = 1,
                      )
    
        Note in particular the constructor parameter:
 
            how_many_stages
    
        As its name implies, this parameter controls how many stages will
        be used in the boosted decision tree classifier.  As mentioned
        above, a separate decision tree is constructed for each stage of
        boosting using a set of training samples that are drawn through a
        probability distribution maintained over the entire training
        dataset.
 
    get_training_data_for_base_tree()
 
        This method reads your training datafile, creates the data structures
        from the data ingested for constructing the base decision tree.
 
    show_training_data_for_base_tree()
 
        Writes to the standard output the training data samples and also
        some relevant properties of the features used in the training
        dataset.
 
    calculate_first_order_probabilities_and_class_priors()
 
        Calls on the appropriate methods of the main DecisionTree class to
        estimate the first-order probabilities and the class priors.
 
    construct_base_decision_tree()
 
        Calls on the appropriate method of the main DecisionTree class to
        construct the base decision tree.
 
    display_base_decision_tree()
 
        Displays the base decision tree in your terminal window. (The
        textual form of the decision tree is written out to the standard
        output.)
 
    construct_cascade_of_trees()
 
        Uses the AdaBoost algorithm to construct a cascade of decision
        trees.  As mentioned earlier, the training samples for each tree in
        the cascade are drawn using a probability distribution over the
        entire training dataset. This probability distribution for any
        given tree in the cascade is heavily influenced by which training
        samples are misclassified by the previous tree.
        
    display_decision_trees_for_different_stages()
 
        Displays separately in your terminal window the decision tree
        constructed for each stage of the cascade. (The textual form of the
        trees is written out to the standard output.)
 
    classify_with_boosting( test_sample )
 
        Calls on each decision tree in the cascade to classify the argument
        test sample.
 
    display_classification_results_for_each_stage()
 
        You can call this method to display in your terminal window the
        classification decision made by each decision tree in the cascade.
        The method also prints out the trust factor associated with each
        decision tree.  It is important to look simultaneously at the
        classification decision and the trust factor for each tree ---
        since a classification decision made by a specific tree may appear
        bizarre for a given test sample.  This method is useful primarily
        for debugging purposes.
 
    show_class_labels_for_misclassified_samples_in_stage( stage_index )
 
        As with the previous method, this method is useful mostly for
        debugging. It returns class labels for the samples misclassified by
        the stage whose integer index is supplied as an argument to the
        method.  Say you have 10 stages in your cascade.  The value of the
        argument stage_index would go from 0 to 9, with 0 corresponding to
        the base tree.
 
    trust_weighted_majority_vote_classifier()
 
        Uses the "final classifier" formula of the AdaBoost algorithm to
        pool together the classification decisions made by the individual
        trees while taking into account the trust factors associated with
        the trees.  As mentioned earlier, we associate with each tree of
        the cascade a trust factor that depends on the overall
        misclassification rate associated with that tree.
 
 
    See the example scripts in the ExamplesBoosting subdirectory for how to
    call the methods listed above for classifying individual data samples
    with boosting and for bulk classification when you place all your test
    samples in a single file.
 
 
USING RANDOMIZED DECISION TREES:
 
    As mentioned earlier, the new RandomizedTreesForBigData class allows
    you to solve the following two problems: (1) Data classification using
    the needle-in-a-haystack metaphor, that is, when a vast majority of
    your training samples belong to just one class.  And (2) You have
    access to a very large database of training samples and you wish to
    construct an ensemble of decision trees for classification.
 
    Here is how you'd call the RandomizedTreesForBigData constructor for
    needle-in-a-haystack classification:
 
            import RandomizedTreesForBigData
            training_datafile = "MyLargeDatabase.csv"
            rt = RandomizedTreesForBigData.RandomizedTreesForBigData(
                            training_datafile = training_datafile,
                            csv_class_column_index = 48,
                            csv_columns_for_features = [39,40,41,42],  
                            entropy_threshold = 0.01,
                            max_depth_desired = 8,
                            symbolic_to_numeric_cardinality_threshold = 10,
                            looking_for_needles_in_haystack = 1,
                            how_many_trees = 5,
                            csv_cleanup_needed = 1,
                 )
    
    Note in particular the constructor parameters:
 
            looking_for_needles_in_haystack
 
            how_many_trees
 
    The first of these parameters, looking_for_needles_in_haystack, invokes
    the logic for constructing an ensemble of decision trees, each based on
    a training dataset that uses all of the minority class samples, and a
    random drawing from the majority class samples.
 
    Here is how you'd call the RandomizedTreesForBigData constructor for a
    more general attempt at constructing an ensemble of decision trees,
    with each tree trained with randomly drawn samples from a large
    database of training data:
 
            import RandomizedTreesForBigData
            training_datafile = "MyLargeDatabase.csv"
            rt = RandomizedTreesForBigData.RandomizedTreesForBigData(
                            training_datafile = training_datafile,
                            csv_class_column_index = 48,
                            csv_columns_for_features = [39,40,41,42],  
                            entropy_threshold = 0.01,
                            max_depth_desired = 8,
                            symbolic_to_numeric_cardinality_threshold = 10,
                            how_many_training_samples_per_tree = 150,
                            how_many_trees = 5,
                            csv_cleanup_needed = 1,
                 )
    
    Note in particular the constructor parameters:
 
            how_many_training_samples_per_tree
 
            how_many_trees
 
    NOTE: When you set the 'how_many_training_samples_per_tree' parameter,
    you are not allowed to also set the 'looking_for_needles_in_haystack'
    parameter, and vice versa.
 
    Here is a list of the methods defined for the RandomizedTreesForBigData
    class that you can call in your own scripts:
 
    get_training_data_for_N_trees()
 
        What this method does depends on which of the two constructor
        parameters --- 'looking_for_needles_in_haystack' or
        'how_many_training_samples_per_tree' --- is set.  When the former
        is set, it creates a collection of training datasets for
        'how_many_trees' number of decision trees, with each dataset being
        a mixture of the minority class and sample drawn randomly from the
        majority class.  However, when the latter option is set, all the
        datasets are drawn randomly from the training database with no
        particular attention given to the relative populations of the two
        classes.
 
    show_training_data_for_all_trees()
 
        As the name implies, this method shows the training data being
        used for all the decision trees.  This method is useful for
        debugging purposes using small datasets.
 
    calculate_first_order_probabilities()
 
        Calls on the appropriate method of the main DecisionTree class to
        estimate the first-order probabilities for the training dataset to
        be used for each decision tree.
        
    calculate_class_priors()
 
        Calls on the appropriate method of the main DecisionTree class to
        estimate the class priors for the training dataset to be used for
        each decision tree.
 
    construct_all_decision_trees()
 
        Calls on the appropriate method of the main DecisionTree class to
        construct the decision trees.
 
    display_all_decision_trees()
 
        Displays all the decision trees in your terminal window. (The
        textual form of the decision trees is written out to the standard
        output.)
 
    classify_with_all_trees( test_sample )
 
        The test_sample is sent to each decision tree for classification.
 
    display_classification_results_for_all_trees()
 
        The classification decisions returned by the individual decision
        trees are written out to the standard output.
 
    get_majority_vote_classification()
 
        This method aggregates the classification results returned by the
        individual decision trees and returns the majority decision.
 
 
CONSTRUCTING REGRESSION TREES:
 
    Decision tree based modeling requires that the class labels be
    distinct.  That is, the training dataset must contain a relatively
    small number of discrete class labels for all of your data records if
    you want to model the data with one or more decision trees.  However,
    when one is trying to understand all of the associational
    relationships that exist in a large database, one often runs into
    situations where, instead of discrete class labels, you have a
    continuously valued variable as a dependent variable whose values are
    predicated on a set of feature values.  It is for such situations that
    you will find useful the new class RegressionTree that is now a part of
    the DecisionTree module.  The RegressionTree class has been programmed
    as a subclass of the main DecisionTree class.
 
    You can think of regression with a regression tree as a powerful
    generalization of the very commonly used Linear Regression algorithms.
    Although you can certainly carry out polynomial regression with
    run-of-the-mill Linear Regression algorithms for modeling
    nonlinearities between the predictor variables and the dependent
    variable, specifying the degree of the polynomial is often tricky.
    Additionally, a polynomial can inject continuities between the
    predictor and the predicted variables that may not really exist in the
    real data.  Regression trees, on the other hand, give you a piecewise
    linear relationship between the predictor and the predicted variables
    that is freed from the constraints of superimposed continuities at the
    joins between the different segments.  See the following tutorial for
    further information regarding the standard linear regression approach
    and the regression that can be achieved with the RegressionTree class
    in this module:
 
    https://engineering.purdue.edu/kak/Tutorials/RegressionTree.pdf
 
    The RegressionTree class in the current version of the module assumes
    that all of your data is numerical.  That is, unlike what is possible
    with the DecisionTree class (and the other more closely related classes
    in this module) that allow your training file to contain a mixture of
    numerical and symbolic data, the RegressionTree class requires that ALL
    of your data be numerical.  I hope to relax this constraint in future
    versions of this module.  Obviously, the dependent variable will always
    be numerical for regression.
 
    See the example scripts in the directory ExamplesRegression if you wish
    to become more familiar with the regression capabilities of the module.
 
    Here is how you'd call the RegressionTree constructor:
 
            import RegressionTree
            training_datafile = "gendata6.csv"
            rt = RegressionTree.RegressionTree( 
                                    training_datafile = training_datafile,
                                    dependent_variable_column = 3,
                                    predictor_columns = [1,2],
                                    mse_threshold = 0.01,
                                    max_depth_desired = 2,
                                    jacobian_choice = 0,
                                    csv_cleanup_needed = 1,
                 )
    
    Note in particular the constructor parameters:
 
        dependent_variable
        predictor_columns
        mse_threshold
        jacobian_choice
 
    The first of these parameters, dependent_variable, is set to the column
    index in the CSV file for the dependent variable.  The second
    constructor parameter, predictor_columns, tells the system as to which
    columns contain values for the predictor variables.  The third
    parameter, mse_threshold, is for deciding when to partition the data at
    a node into two child nodes as a regression tree is being constructed.
    If the minmax of MSE (Mean Squared Error) that can be achieved by
    partitioning any of the features at a node is smaller than
    mse_threshold, that node becomes a leaf node of the regression tree.
 
    The last parameter, jacobian_choice, must be set to either 0 or 1 or 2.
    Its default value is 0. When this parameter equals 0, the regression
    coefficients are calculated using the linear least-squares method and
    no further "refinement" of the coefficients is carried out using
    gradient descent.  This is the fastest way to calculate the regression
    coefficients.  When jacobian_choice is set to 1, you get a weak version
    of gradient descent in which the Jacobian is set to the "design matrix"
    itself. Choosing 2 for jacobian_choice results in a more reasonable
    approximation to the Jacobian.  That, however, is at a cost of much
    longer computation time.  NOTE: For most cases, using 0 for
    jacobian_choice is the best choice.  See my tutorial "Linear Regression
    and Regression Trees" for why that is the case.
 
    Here is a list of the methods defined for the RegressionTree class that
    you can call in your own scripts:
 
    get_training_data_for_regression()
 
        Only CSV training datafiles are allowed. Additionally, the first
        record in the file must list the names of the fields, and the first
        column must contain an integer ID for each record.
 
    construct_regression_tree()
 
        As the name implies, this is the method that construct a regression
        tree.
 
    display_regression_tree("     ")
 
        Displays the regression tree, as the name implies.  The white-space
        string argument specifies the offset to use in displaying the child
        nodes in relation to a parent node.
 
    prediction_for_single_data_point( root_node, test_sample )
 
        You call this method after you have constructed a regression tree
        if you want to calculate the prediction for one sample.  The
        parameter root_node is what is returned by the call
        construct_regression_tree().  The formatting of the argument bound
        to the test_sample parameter is important.  To elaborate, let's say
        you are using two variables named xvar1 and xvar2 as your predictor
        variables. In this case, the test_sample parameter will be bound to
        a Python list that will look like 
            ['xvar1 = 23.4', 'xvar2 = 12.9'] 
        Arbitrary amount of white space, including none, on the two sides
        of the equality symbol is allowed in the construct shown above.  A
        call to this method returns a dictionary with two key-value pairs.
        One of the keys is called 'solution_path' and the other
        'prediction'.  The value associated with key 'solution_path' is the
        path in the regression tree to the leaf node that yielded the
        prediction.  And the value associated with the key 'prediction' is
        the answer you are looking for.
 
    predictions_for_all_data_used_for_regression_estimation( root_node )
 
        This call calculates the predictions for all of the predictor
        variables data in your training file.  The parameter root_node is
        what is returned by the call to construct_regression_tree().  The
        values for the dependent variable thus predicted can be seen by
        calling display_all_plots(), which is the method mentioned below.
 
    display_all_plots()
 
        This method displays the results obtained by calling the prediction
        method of the previous entry.  This method also creates a hardcopy
        of the plots and saves it as a '.png' disk file. The name of this
        output file is always "regression_plots.png".
 
    mse_for_tree_regression_for_all_training_samples( root_node )
 
        This method carries out an error analysis of the predictions for
        the samples in your training datafile.  It shows you the overall
        MSE (Mean Squared Error) with tree-based regression, the MSE for
        the data samples at each of the leaf nodes of the regression tree,
        and the MSE for the plain old Linear Regression as applied to all
        of the data.  The parameter root_node in the call syntax is what is
        returned by the call to construct_regression_tree().
 
    bulk_predictions_for_data_in_a_csv_file(root_node, filename, columns)
 
        Call this method if you want to apply the regression tree to all
        your test data in a disk file.  The predictions for all of the test
        samples in the disk file are written out to another file whose name
        is the same as that of the test file except for the addition of
        '_output' in the name of the file.  The parameter 'filename' is the
        name of the disk file that contains the test data. And the
        parameter 'columns' is a Python list of the column indices for the
        predictor variables in the test file.
 
 
GENERATING SYNTHETIC TRAINING DATA:
 
    To generate synthetic training data, you first construct an instance of
    the class TrainingDataGenerator that is incorporated in the
    DecisionTree module.  A call to the constructor of this class will look
    like:
 
        parameter_file = "param_numeric.txt"
        output_csv_file = "training.csv";
        training_data_gen = TrainingDataGeneratorNumeric(
                              output_csv_file   = output_csv_file,
                              parameter_file    = parameter_file,
                              number_of_samples_per_class = some_number,
                            )
        training_data_gen.read_parameter_file_numeric()
        training_data_gen.gen_numeric_training_data_and_write_to_csv()
 
    The training data that is generated is according to the specifications
    described in the parameter file.  The structure of this file must be as
    shown in the file `param_numeric.txt' for the numeric training data and
    as shown in `param_symbolic.txt' for the case of symbolic training
    data.  Both these example parameter files are in the 'Examples'
    subdirectory.  The parameter file names the classes, the features for
    the classes, and the possible values for the features.
 
    If you want to generate purely symbolic training data, here is the
    constructor call to make:
 
        parameter_file = "param_symbolic.txt"
        output_data_file = "training_symbolic2.csv";
        training_data_gen = TrainingDataGeneratorSymbolic(
                              output_datafile   = output_data_file,
                              parameter_file    = parameter_file,
                              write_to_file     = 1,
                              number_of_training_samples = some_number,
                            )
        training_data_gen.read_parameter_file_symbolic()
        training_data_gen.gen_symbolic_training_data()
        training_data_gen.write_training_data_to_file()
 
 
THE Examples DIRECTORY:
 
    See the 'Examples' directory in the distribution for how to construct a
    decision tree, and how to then classify new data using the decision
    tree.  To become more familiar with the module, run the scripts
 
        construct_dt_and_classify_one_sample_case1.py
        construct_dt_and_classify_one_sample_case2.py
        construct_dt_and_classify_one_sample_case3.py
        construct_dt_and_classify_one_sample_case4.py
 
    The first script is for the purely symbolic case, the second for the
    case that involves both numeric and symbolic features, the third for
    the case of purely numeric features, and the last for the case when the
    training data is synthetically generated by the script
    generate_training_data_numeric.py
 
    Next, run the following script as it is for bulk classification of data
    records placed in a CSV file:
 
      classify_test_data_in_a_file.py  training4.csv  test4.csv  out4.csv
 
    The script first constructs a decision tree using the training data in
    the first-argument file, `training4.csv'.  Subsequently, the script
    calculates the class labels for each of the test records in the file
    `test4.csv'.  The class labels are written out the file `out4.csv'.  An
    important thing to note here that your test file --- in this case
    `test4.csv' --- must have a column for the class labels.  Obviously, in
    real-life situations, there will be no class labels in this column.
    When that is the case, you can place the empty string "" for each data
    record in this column.  A demonstration of that is give by the
    following variation of the above call:
 
      classify_test_data_in_a_file.py  training4.csv  test4_no_class_labels.csv  out4.csv 
 
    The following script in the 'Examples' directory 
 
        classify_by_asking_questions.py
 
    shows how you can use a decision-tree classifier interactively.  In
    this mode, you first construct the decision tree from the training data
    and then the user is prompted for answers to the feature tests at the
    nodes of the tree.
 
    If your training data has a feature whose values span a large range
    and, at the same time, are characterized by a heavy-tail distribution,
    you should look at the script 
 
        construct_dt_for_heavytailed.py
 
    to see how to use the option number_of_histogram_bins in the call to
    the constructor.  This option was introduced in Version 2.2.4 for
    dealing with such features.  If you do not set this option, the module
    will use the default value of 500 for the number of points at which to
    sample the value range for such a feature.
 
    The 'Examples' directory also contains the following scripts:
 
        generate_training_data_numeric.py
        generate_training_data_symbolic.py
 
    that show how you can use the module to generate synthetic training
    data.  Synthetic training and test data are generated according to the
    specifications laid out in a parameter file.  There are constraints on
    how the information is laid out in the parameter file.  See the files
    `param_numeric.txt' and `param_symbolic.txt' in the 'Examples'
    directory for how to structure these files.
 
    The Examples directory of Versions 2.2 and higher of the DecisionTree
    module also contains the following two scripts:
 
       evaluate_training_data1.py
       evaluate_training_data2.py
 
    that illustrate how the Python class EvalTrainingData can be used to
    evaluate the quality of your training data (as long as it resides in a
    `.csv' file.)  This new class is a subclass of the DecisionTree class
    in the module file.  See the README in the Examples directory for
    further information regarding these two scripts.
 
    The Examples directory of Versions 2.3.2 and higher of the module
    contains the following three scripts:
 
        introspection_in_a_loop_interactive.py
 
        introspection_show_training_samples_at_all_nodes_direct_influence.py
 
        introspection_show_training_samples_to_nodes_influence_propagation.py
 
    The first script illustrates how to use the DTIntrospection class of
    the module interactively for generating explanations for the
    classification decisions made at the nodes of the decision tree.  In
    the interactive session you are first asked for the node number you are
    interested in.  Subsequently, you are asked for whether or not you are
    interested in specific questions that the introspector can provide
    answers for. The second script generates a tabular display that shows
    for each node of the decision tree a list of the training samples that
    fall directly in the portion of the feature space assigned that node.
    (As mentioned elsewhere in this documentation, when this list is empty
    for a node, that means the node is a result of the generalization
    achieved by probabilistic modeling of the data.  Note that this module
    constructs a decision tree NOT by partitioning the set of training
    samples, BUT by partitioning the domains of the probability density
    functions.)  The third script listed above also generates a tabular
    display, but one that shows how the influence of each training sample
    propagates in the tree.  This display first shows the list of nodes
    that are affected directly by the data in a training sample. This list
    is followed by an indented display of the nodes that are affected
    indirectly by the training sample.  A training sample affects a node
    indirectly if the node is a descendant of one of the nodes affected
    directly.
 
    The latest addition to the Examples directory is the script:
 
        get_indexes_associated_with_fields.py
 
    As to why you may find this script useful, note that large database
    files may have hundreds of fields and it is not always easy to figure
    out what numerical index is associated with a given field.  At the same
    time, the constructor of the DecisionTree module requires that the
    field that holds the class label and the fields that contain the
    feature values be specified by their numerical zero-based indexes.  If
    you have a very large database and you are faced with such a problem,
    you can run this script to see the zero-based numerical index values
    associated with the different columns of your CSV file.
 
 
THE ExamplesBagging DIRECTORY:
 
    The ExamplesBagging subdirectory in the main installation directory
    contains the following scripts:
 
        bagging_for_classifying_one_test_sample.py
 
        bagging_for_bulk_classification.py
 
    As the names of the scripts imply, the first shows how to call the
    different methods of the DecisionTreeWithBagging class for classifying
    a single test sample.  When you are classifying a single test sample,
    you can also see how each bag is classifying the test sample.  You can,
    for example, display the training data used in each bag, the decision
    tree constructed for each bag, etc.
 
    The second script is for the case when you place all of the test
    samples in a single file.  The demonstration script displays for each
    test sample a single aggregate classification decision that is obtained
    through majority voting by all the decision trees.
 
 
THE ExamplesBoosting DIRECTORY:
 
    The ExamplesBoosting subdirectory in the main installation directory
    contains the following three scripts:
 
        boosting_for_classifying_one_test_sample_1.py
 
        boosting_for_classifying_one_test_sample_2.py
 
        boosting_for_bulk_classification.py
 
    As the names of the first two scripts imply, these show how to call the
    different methods of the BoostedDecisionTree class for classifying a
    single test sample.  When you are classifying a single test sample, you
    can see how each stage of the cascade of decision trees is classifying
    the test sample.  You can also view each decision tree separately and
    also see the trust factor associated with the tree.
 
    The third script is for the case when you place all of the test samples
    in a single file.  The demonstration script outputs for each test
    sample a single aggregate classification decision that is obtained
    through trust-factor weighted majority voting by all the decision
    trees.
 
 
THE ExamplesRandomizedTrees DIRECTORY:
 
    The ExamplesRandomizedTrees subdirectory in the main installation
    directory shows example scripts that you can use to become more
    familiar with the RandomizedTreesForBigData class for solving
    needle-in-a-haystack and big-data data classification problems. These
    scripts are:
 
        randomized_trees_for_classifying_one_test_sample_1.py
 
        randomized_trees_for_classifying_one_test_sample_2.py
 
        classify_database_records.py
 
    The first script shows the constructor options to use for solving a
    needle-in-a-haystack problem --- that is, a problem in which a vast
    majority of the training data belongs to just one class.  The second
    script shows the constructor options for using randomized decision
    trees for the case when you have access to a very large database of
    training samples and you'd like to construct an ensemble of decision
    trees using training samples pulled randomly from the training
    database.  The last script illustrates how you can evaluate the
    classification power of an ensemble of decision trees as constructed by
    RandomizedTreesForBigData by classifying a large number of test samples
    extracted randomly from the training database.
 
 
THE ExamplesRegression DIRECTORY:
 
    The ExamplesRegression subdirectory in the main installation directory
    shows example scripts that you can use to become familiar with
    regression trees and how they can be used for nonlinear regression.  If
    you are new to the concept of regression trees, start by executing the
    following scripts without changing them and see what sort of output is
    produced by them:
 
        regression4.py
 
        regression5.py
 
        regression6.py
 
        regression8.py
 
    With all these scripts, you may wish to try all three values, 0, 1, or
    2, for the constructor parameter jacobian_choice to see the difference
    made by including gradient descent in the calculation of the regression
    coefficients.  Recall, when jacobian_choice is 0, which is the default,
    you get no gradient descent.
 
    The 'regression4.py' script involves only one predictor variable and
    one dependent variable. The training data for this exercise is drawn
    from the file 'gendata4.csv'.  This data file contains strongly
    nonlinear data.  When you run the script regression4.py, you will see
    how much better the result from tree regression is compared to what you
    can get with linear regression.
 
    The 'regression5.py' script is essentially the same as the previous
    script except for the fact that the training datafile used in this
    case, 'gendata5.csv', consists of three noisy segments, as opposed to
    just two in the previous case.
 
    The script 'regression6.py' deals with the case when we have two
    predictor variables and one dependent variable.  You can think of the
    data as consisting of noisy height values over an (x1,x2) plane.  The
    data used in this script is drawn from the csv file 'gen3Ddata1.csv'
 
    Finally, the script 'regression8.py' shows how you can carry out bulk
    prediction for all your test data records in a disk file.  The script
    writes all the calculated predictions into another disk file whose name
    is derived from the name of the test data file.
 
 
INSTALLATION:
 
    The DecisionTree class was packaged using setuptools.  For
    installation, execute the following command-line in the source
    directory (this is the directory that contains the setup.py file after
    you have downloaded and uncompressed the package):
 
            sudo python setup.py install
 
    and/or
 
            sudo python3 setup.py install
 
    On Linux distributions, this will install the module file at a location
    that looks like
 
             /usr/local/lib/python2.7/dist-packages/
 
    and for Python3 at a location like
 
             /usr/local/lib/python3.4/dist-packages/
 
    If you do not have root access, you have the option of working directly
    off the directory in which you downloaded the software by simply
    placing the following statements at the top of your scripts that use
    the DecisionTree class:
 
            import sys
            sys.path.append( "pathname_to_DecisionTree_directory" )
 
    To uninstall the module, simply delete the source directory, locate
    where the DecisionTree module was installed with "locate DecisionTree"
    and delete those files.  As mentioned above, the full pathname to the
    installed version is likely to look like
    /usr/local/lib/python2.7/dist-packages/DecisionTree*
 
    If you want to carry out a non-standard install of the DecisionTree
    module, look up the on-line information on Disutils by pointing your
    browser to
 
              http://docs.python.org/dist/dist.html
 
 
BUGS:
 
    Please notify the author if you encounter any bugs.  When sending
    email, please place the string 'DecisionTree' in the subject line.
 
 
ACKNOWLEDGMENTS:
 
    The importance of the 'sentiment' feature in the "What Practical Problem
    is Solved by this Module" section was mentioned to the author by John
    Gorup.  Thanks John.
 
    Thanks go to Wenshuai Hou for discovering and reporting the bug that
    resulted in Version 2.2.3.  I should also thank Wenshuai for sending me
    a training data file with heavy-tailed values for one of the
    features. This datafile became the reason for the modifications to the
    code that are incorporated in Version 2.2.4.
 
    I owe many thanks to Eugene Kolotinsky for the bug discovery whose fix
    was the primary reason for Version 2.2.6.  This bug related to the
    erroneous calculation of the probability of a feature acquiring a
    certain value if the training data contained zeros for the feature
    values.
 
    The bug whose fix led to Version 3.2.2 was reported by Erez Segal. He
    noticed that I had left out the keyword "raise" in the "else" clause
    when checking for the allowed suffixes in the name of the
    user-specified training data file. Thanks, Erez!
 
    With regard to Version 3.3.2, I wish to thank Alexandre Drouin-Picaro
    for bringing to my attention the problem created by the nested class
    DTNode when using pickle to save a decision tree to a disk file.
 
 
ABOUT THE AUTHOR:
 
    The author, Avinash Kak, recently finished a 17-year long "Objects
    Trilogy Project" with the publication of the book "Designing with
    Objects" by John-Wiley. If interested, visit his web page at Purdue to
    find out what this project was all about. You might like "Designing
    with Objects" especially if you enjoyed reading Harry Potter as a kid
    (or even as an adult, for that matter).
 
    For all issues related to this module, contact the author at
    kak@purdue.edu
 
    If you send email, please place the string "DecisionTree" in your
    subject line to get past the author's spam filter.
 
 
COPYRIGHT:
 
    Python Software Foundation License
 
    Copyright 2016 Avinash Kak
 
@endofdocs

 
Imported Modules
       
functools
itertools
math
operator
os
re
string
sys

 
Classes
       
__builtin__.object
DTIntrospection
DTNode
DecisionTree
EvalTrainingData
TrainingDataGeneratorNumeric
TrainingDataGeneratorSymbolic

 
class DTIntrospection(__builtin__.object)
    Instances constructed from this class can provide explanations for the
classification decisions at the nodes of a decision tree.  
 
When used in the interactive mode, the decision-tree introspection made possible
by this class provides answers to the following three questions: (1) List of the
training samples that fall in the portion of the feature space that corresponds
to a node of the decision tree; (2) The probabilities associated with the last
feature test that led to the node; and (3) The class probabilities predicated on
just the last feature test on the path to that node.
 
CAVEAT: It is possible for a node to exist even when there are no training
samples in the portion of the feature space that corresponds to the node.  That
is because a decision tree is based on the probability densities estimated from
the training data. When training data is non-uniformly distributed, it is
possible for the probability associated with a point in the feature space to be
non-zero even when there are no training samples at or in the vicinity of that
point.
 
For a node to exist even where there are no training samples in the portion of
the feature space that belongs to the node is an indication of the generalization
ability of decision-tree based classification.
 
When used in a non-interactive mode, an instance of this class can be used to
create a tabular display that shows what training samples belong directly to the
portion of the feature space that corresponds to each node of the decision tree.
An instance of this class can also construct a tabular display that shows how the
influence of each training sample propagates in the decision tree.  For each
training sample, this display first shows the list of nodes that came into
existence through feature test(s) that used the data provided by that sample.
This list for each training sample is followed by a subtree of the nodes that owe
their existence indirectly to the training sample. A training sample influences a
node indirectly if the node is a descendant of another node that is affected
directly by the training sample.
 
  Methods defined here:
__init__(self, dt)
display_training_samples_at_all_nodes_direct_influence_only(self)
display_training_samples_to_nodes_influence_propagation(self)
explain_classification_at_one_node(self, node_id)
explain_classifications_at_multiple_nodes_interactively(self)
extract_feature_op_val(self, feature_value_combo)
get_samples_for_feature_value_combo(self, feature_value_combo)
initialize(self)
recursive_descent(self, node)
recursive_descent_for_sample_to_node_influence(self, node_serial_num, nodes_already_accounted_for, offset)
recursive_descent_for_showing_samples_at_a_node(self, node)

Data descriptors defined here:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)

 
class DTNode(__builtin__.object)
    The nodes of a decision tree are instances of this class:
 
  Methods defined here:
__init__(self, feature, entropy, class_probabilities, branch_features_and_values_or_thresholds, dt, root_or_not=None)
add_child_link(self, new_node)
delete_all_links(self)
display_decision_tree(self, offset)
display_node(self)
get_branch_features_and_values_or_thresholds(self)
get_children(self)
get_class_names(self)
get_class_probabilities(self)
get_feature(self)
Returns the feature test at the current node
get_next_serial_num(self)
get_node_entropy(self)
get_serial_num(self)
how_many_nodes(self)
set_class_names(self, class_names_list)
set_feature(self, feature)
set_node_creation_entropy(self, entropy)

Data descriptors defined here:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)

 
class DecisionTree(__builtin__.object)
     Methods defined here:
__init__(self, *args, **kwargs)
best_feature_calculator(self, features_and_values_or_thresholds_on_branch, existing_node_entropy)
This is the heart of the decision tree constructor.  Its main job is to figure
out the best feature to use for partitioning the training data samples that
correspond to the current node.  The search for the best feature is carried
out differently for symbolic features and for numeric features.  For a
symbolic feature, the method estimates the entropy for each value of the
feature and then averages out these entropies as a measure of the
discriminatory power of that features.  For a numeric feature, on the other
hand, it estimates the entropy reduction that can be achieved if we were to
partition the set of training samples at each possible threshold for that
numeric feature.  For a numeric feature, all possible sampling points
relevant to the node in question are considered as candidates for thresholds.
calculate_class_priors(self)
calculate_first_order_probabilities(self)
class_entropy_for_a_given_sequence_of_features_and_values_or_thresholds(self, array_of_features_and_values_or_thresholds)
class_entropy_for_greater_than_threshold_for_feature(self, array_of_features_and_values_or_thresholds, feature, threshold)
class_entropy_for_less_than_threshold_for_feature(self, array_of_features_and_values_or_thresholds, feature, threshold)
class_entropy_on_priors(self)
classify(self, root_node, features_and_values)
Classifies one test sample at a time using the decision tree constructed from
your training file.  The data record for the test sample must be supplied as
shown in the scripts in the `Examples' subdirectory.  See the scripts
construct_dt_and_classify_one_sample_caseX.py in that subdirectory.
classify_by_asking_questions(self, root_node)
If you want classification to be carried out by engaging a human user in a
question-answer session, this is the method to use for that purpose.  See the
script classify_by_asking_questions.py in the Examples subdirectory for an
illustration of how to do that.
construct_decision_tree_classifier(self)
Construct the root node object and set its entropy value as derived from the priors
associated with the different classes.
determine_data_condition(self)
This method estimates the worst-case fan-out of the decision tree taking into
account the number of values (and therefore the number of branches emanating
from a node) for the symbolic features.
entropy_scanner_for_a_numeric_feature(self, feature)
find_bounded_intervals_for_numeric_features(self, arr)
Given a list of branch attributes for the numeric features of the form, say,
['g2<1','g2<2','g2<3','age>34','age>36','age>37'], this method returns the
smallest list that is relevant for the purpose of calculating the
probabilities.  To explain, the probability that the feature `g2' is less
than 1 AND, at the same time, less than 2, AND, at the same time, less than
3, is the same as the probability that the feature less than 1. Similarly,
the probability that 'age' is greater than 34 and also greater than 37 is the
same as `age' being greater than 37.
get_class_names(self)
get_training_data(self)
interactive_recursive_descent_for_classification(self, node, answer, scratchpad_for_numerics)
prior_probability_for_class(self, class_name)
probability_of_a_class_given_sequence_of_features_and_values_or_thresholds(self, class_name, array_of_features_and_values_or_thresholds)
probability_of_a_sequence_of_features_and_values_or_thresholds(self, array_of_features_and_values_or_thresholds)
This method requires that all truly numeric types only be expressed as '<' or '>'
constructs in the array of branch features and thresholds
probability_of_a_sequence_of_features_and_values_or_thresholds_given_class(self, array_of_features_and_values_or_thresholds, class_name)
This method requires that all truly numeric types only be expressed as '<' or '>'
constructs in the array of branch features and thresholds
probability_of_feature_less_than_threshold(self, feature_name, threshold)
probability_of_feature_less_than_threshold_given_class(self, feature_name, threshold, class_name)
probability_of_feature_value(self, feature_name, value)
probability_of_feature_value_given_class(self, feature_name, feature_value, class_name)
recursive_descent(self, node)
After the root node of the decision tree is constructed by the previous method, we
find  at that node the feature that yields the greatest reduction in class entropy
from the entropy based on just the class priors. The logic for finding this
feature is different for symbolic features and for numeric features (that logic is
built into the best feature calculator). We then invoke this method recursively to 
create the rest of the tree.
recursive_descent_for_classification(self, node, feature_and_values, answer)
show_training_data(self)

Data descriptors defined here:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)

 
class EvalTrainingData(DecisionTree)
    
Method resolution order:
EvalTrainingData
DecisionTree
__builtin__.object

Methods defined here:
__init__(self, *args, **kwargs)
evaluate_training_data(self)

Methods inherited from DecisionTree:
best_feature_calculator(self, features_and_values_or_thresholds_on_branch, existing_node_entropy)
This is the heart of the decision tree constructor.  Its main job is to figure
out the best feature to use for partitioning the training data samples that
correspond to the current node.  The search for the best feature is carried
out differently for symbolic features and for numeric features.  For a
symbolic feature, the method estimates the entropy for each value of the
feature and then averages out these entropies as a measure of the
discriminatory power of that features.  For a numeric feature, on the other
hand, it estimates the entropy reduction that can be achieved if we were to
partition the set of training samples at each possible threshold for that
numeric feature.  For a numeric feature, all possible sampling points
relevant to the node in question are considered as candidates for thresholds.
calculate_class_priors(self)
calculate_first_order_probabilities(self)
class_entropy_for_a_given_sequence_of_features_and_values_or_thresholds(self, array_of_features_and_values_or_thresholds)
class_entropy_for_greater_than_threshold_for_feature(self, array_of_features_and_values_or_thresholds, feature, threshold)
class_entropy_for_less_than_threshold_for_feature(self, array_of_features_and_values_or_thresholds, feature, threshold)
class_entropy_on_priors(self)
classify(self, root_node, features_and_values)
Classifies one test sample at a time using the decision tree constructed from
your training file.  The data record for the test sample must be supplied as
shown in the scripts in the `Examples' subdirectory.  See the scripts
construct_dt_and_classify_one_sample_caseX.py in that subdirectory.
classify_by_asking_questions(self, root_node)
If you want classification to be carried out by engaging a human user in a
question-answer session, this is the method to use for that purpose.  See the
script classify_by_asking_questions.py in the Examples subdirectory for an
illustration of how to do that.
construct_decision_tree_classifier(self)
Construct the root node object and set its entropy value as derived from the priors
associated with the different classes.
determine_data_condition(self)
This method estimates the worst-case fan-out of the decision tree taking into
account the number of values (and therefore the number of branches emanating
from a node) for the symbolic features.
entropy_scanner_for_a_numeric_feature(self, feature)
find_bounded_intervals_for_numeric_features(self, arr)
Given a list of branch attributes for the numeric features of the form, say,
['g2<1','g2<2','g2<3','age>34','age>36','age>37'], this method returns the
smallest list that is relevant for the purpose of calculating the
probabilities.  To explain, the probability that the feature `g2' is less
than 1 AND, at the same time, less than 2, AND, at the same time, less than
3, is the same as the probability that the feature less than 1. Similarly,
the probability that 'age' is greater than 34 and also greater than 37 is the
same as `age' being greater than 37.
get_class_names(self)
get_training_data(self)
interactive_recursive_descent_for_classification(self, node, answer, scratchpad_for_numerics)
prior_probability_for_class(self, class_name)
probability_of_a_class_given_sequence_of_features_and_values_or_thresholds(self, class_name, array_of_features_and_values_or_thresholds)
probability_of_a_sequence_of_features_and_values_or_thresholds(self, array_of_features_and_values_or_thresholds)
This method requires that all truly numeric types only be expressed as '<' or '>'
constructs in the array of branch features and thresholds
probability_of_a_sequence_of_features_and_values_or_thresholds_given_class(self, array_of_features_and_values_or_thresholds, class_name)
This method requires that all truly numeric types only be expressed as '<' or '>'
constructs in the array of branch features and thresholds
probability_of_feature_less_than_threshold(self, feature_name, threshold)
probability_of_feature_less_than_threshold_given_class(self, feature_name, threshold, class_name)
probability_of_feature_value(self, feature_name, value)
probability_of_feature_value_given_class(self, feature_name, feature_value, class_name)
recursive_descent(self, node)
After the root node of the decision tree is constructed by the previous method, we
find  at that node the feature that yields the greatest reduction in class entropy
from the entropy based on just the class priors. The logic for finding this
feature is different for symbolic features and for numeric features (that logic is
built into the best feature calculator). We then invoke this method recursively to 
create the rest of the tree.
recursive_descent_for_classification(self, node, feature_and_values, answer)
show_training_data(self)

Data descriptors inherited from DecisionTree:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)

 
class TrainingDataGeneratorNumeric(__builtin__.object)
    See the example script generate_training_data_numeric.py on how to use this class
for generating your numeric training data.  The training data is generator in
accordance with the specifications you place in a parameter file.
 
  Methods defined here:
__init__(self, *args, **kwargs)
gen_numeric_training_data_and_write_to_csv(self)
After the parameter file is parsed by the previous method, this method calls
on `numpy.random.multivariate_normal()' to generate the training data
samples. Your training data can be of any number of of dimensions, can have
any mean, and any covariance.
read_parameter_file_numeric(self)
The training data generated by an instance of the class
TrainingDataGeneratorNumeric is based on the specs you place in a parameter
that you supply to the class constructor through a constructor variable
called `parameter_file.  This method is for parsing the parameter file in
order to order to determine the names to be used for the different data
classes, their means, and their variances.

Data descriptors defined here:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)

 
class TrainingDataGeneratorSymbolic(__builtin__.object)
    See the sample script generate_training_data_symbolic.py for how to use this
class for generating symbolic training data.  The data is generated according to
the specifications you place in a parameter file.
 
  Methods defined here:
__init__(self, *args, **kwargs)
gen_symbolic_training_data(self)
This method generates training data according to the specifications
placed in a parameter file that is read by the previous method.
read_parameter_file_symbolic(self)
Read a parameter file for generating symbolic training data. See the script
generate_training_data_symbolic.py in the Examples directory for how to pass
the name of the parameter file to the constructor of the
TrainingDataGeneratorSymbolic class.
write_training_data_to_file(self)

Data descriptors defined here:
__dict__
dictionary for instance variables (if defined)
__weakref__
list of weak references to the object (if defined)

 
Functions
       
cleanup_csv(line)
closest_sampling_point(value, arr)
convert(value)
deep_copy_array(array_in)
Meant only for an array of scalars (no nesting):
minimum(arr)
Returns simultaneously the minimum value and its positional index in an
array. [Could also have used min() and index() defined for Python's
sequence types.]
sample_index(sample_name)
When the training data is read from a CSV file, we assume that the first column
of each data record contains a unique integer identifier for the record in that
row. This training data is stored in a dictionary whose keys are the prefix
'sample_' followed by the identifying integers. The purpose of this function is to
return the identifying integer associated with a data record.

 
Data
  __author__ = 'Avinash Kak (kak@purdue.edu)'
__copyright__ = '(C) 2016 Avinash Kak. Python Software Foundation.'
__date__ = '2016-May-14'
__url__ = 'https://engineering.purdue.edu/kak/distDT/DecisionTree-3.4.3.html'
__version__ = '3.4.3'
 
Author
  Avinash Kak (kak@purdue.edu)