hoeffding.h

C4.5的简化版本是一个决策树的算法

/* Dimension.H
 *
 * Each example that we want to place in the decision tree has a value for
 * each attribute. An attribute together with all the possible values for
 * the attribute we call a dimension. The dimension class stores an
 * attribute and its possible values, which is handy for various reasons.
 */

const int MAX_VALUES = 40;    // Same as MAX_CHILDREN for a node.(v)
const int MAX_CHILDREN = 40;  // Cannot be more than MAX_VALUES for a dimension
const int MAX_ATTRS = 40;     // number of distinct attributes(d)
const int MAX_STRING = 100;   //max string length
const int MAX_CLASSES = 20;  // The maximum number of classes allowed

class Node;
class Example;
class Dimension {
friend istream& operator>>(istream &i, Dimension &d); //read a dimension from a file
                                   //usually defined at the beginning of the file
char attribute[MAX_STRING]; //attribute name 

public:
   int num_values;            // How many values this dimension has
   char values[MAX_VALUES][MAX_STRING];  // The names of all values

   int lookup(char temp[]);   // Lookup the index of a given value name
   char *get_attribute();     // Return attribute name
   Dimension();               // Construct a Dimension object
   ~Dimension();              // Destroy this dimension

   Dimension *next;           // List of unused attributes
};
/* Example.H
 *
 * An example is an assignment of values to each possible attribute.
 * An example has a classification value(classlabel).
 */

class Example {
friend ostream& operator<<(ostream &o, Example &e);  // Print out the example
  // char name[MAX_STRING];   // The name of this example
   int *values;  // Array of values. We use numbers to index
                 // into the symbols in the dimensions.
   int my_class; // Which of the valid classifications this is.

public:
   Example(istream& in); // Construct an example from a file
   ~Example();   // Destroy this example
   int get_class();  // Get the class index of this example
   int get_value(int dim);  // Get the value for a certain dimension.

   Example *next;               // The next example in a linked list.
};
/* Decision.H
 *
 * This class is a container class for some globally available values,
 * such as the valid dimensions and classes for this problem.
 */

class Decision {
friend ostream& operator<<(ostream &o, Decision &d);  // Print out the tree
public:
   static int num_classes;          // The number of classes for this run
   static char classes[MAX_CLASSES][MAX_STRING];   // Names for all classes
   static int lookup_class(char temp[]);  // Get the class index given the name
   static int majority_class;      // majority class in examples--------???????how to predict if
                                   //the stream can't be seen at the start time

   static int num_dimensions;          // The number of dimensions for this run
   static Dimension **dimensions;      // Array of dimensions
   static int lookup_attribute(int x, char temp[]); // Get the dimension index

   Node *root;                     // The top of the decision tree

   Decision(char *filename);       // Construct a Decision given an info file
   ~Decision();                    // Destroy the decision tree

   void build_tree();              // Build the decision tree
};
/* Node.H
 *
 * The decision tree is built from nodes.
 *
 * To classify an example, we start at the node of the decision tree
 * and work our way down until we reach a yes or no answer. Each
 * node has some question to ask, and depending on the answer to that
 * question, we choose one of the children. This "question" is called
 * an attribute. We store a dimension with the node, because this lets
 * us know the name of the attribute as well as all the possible values.
 * Each different value as an "answer" to the attribute question would
 * direct the search to a different child.
 *
 * Each node is also associated with one or more examples, if it is
 * a leaf node. These examples are previous data that helped to build
 * the tree.
 */

class Example;
class Dimension;
class Node {
   Example *examples;               // Start of a linked list of examples.
   int num_examples;                // The number of examples

   int num_attrs;                    // Number of such attributes (as below)
   int attributes[MAX_ATTRS];        // Attributes remaining for this subtree

   int attribute;                   // The "question" for this node.
   int major_class;                 // This node's class (LBH 3/96)

   int num_children;
   Node *children[MAX_CHILDREN];    // The children under this node

   int splitter();                  // Which dimension will node be split on?
   double evaluate(int dim);        // Metric for deciding splitting dimension
   double disorder(int dim, int value);  // Another metric, used by evaluate
   void print_distribution();       // Print out the class distribution here
   void partition();                // Break up the node given the split

public:
   Node();                          // Construct a node
   ~Node();                         // Destroy a node
   void add_example(Example *example);   // Add an example to this node's set
   void add_attribute(int attr);    // Add attr to node's set (LBH 3/96)
   void build_tree(int default_class); // Build decision subtree from this node
   double disorder(int value);      // Calculate a metric for disorder
   void print(int depth);           // Print the node with "depth" indentation
};