bowbowbow/DecisionTree — 58 Stars

Topics

#algorithm #cpp #data-science #decision-trees #machine-learning

Language breakdown

C++ 98.3%

Makefile 1.7%

▸ Files click to expand

README

Decision Tree Assignment ==================

C++ Implementation of Decision Tree Algorithm

To run the implementation =========================

Keep project files in one folder.

Compile using command make.

To compile without using the makefile, type the following command.

>

g++ -std=c++11 decision_tree.cpp -o dt.exe

>

(Note that -std=c++11 option must be given in g++.)

Run using following command.

./dt.exe [dttrain.txt] [dttest.txt] [dt_result.txt]

Summary of the algorithm ============

This algorithm is used for automatic decision tree generation.

Input:

1. Data partition: D, which is a set of training tuples and their associated class labels.

2. Attribute_list: The set of candidate attributes

3. Attributeselectionmethod: A procedure to determine the splitting criterion that "best" partitions the data tuples into individual classes. This criterion consists of a splitting_attribute and, possibly, either a split-point or splitting subset.

>

Output: A decision tree.

Basic Algorithm (a greedy algorithm)

Tree is constructed in a top-down, recursive, divide-and-conquer manner.
At start, all the training examples are at the root.
Attributes are categorical. (Note that if continuous-valued, they are discretized in advance)
Test attributes are selected on the basis of a heuristic or statistical measure.

Conditions for stopping partitioning

All samples for a given node belong to the same class
There are no remaining attributes for further partitioning - majority voting is employed for classifying the leaf
There are no sample left

Attribute Selection Measure : Information GainRatio

$$$GainRatio(A$ &space;=&space;\frac&space;{Gain(A)}{SplitInfo(A)}&space;$$)

$$$SplitInfo<em>{A}(D$ &space;=&space;-&space;\sum&space;{&space;j=1&space;}^{&space;v&space;}&space;\frac&space;{&space;\left|&space;{&space;D&space;}{&space;j&space;}&space;\right|&space;}{&space;\left|&space;D&space;\right|&space;}&space;log{2}(\frac&space;{&space;\left|&space;{&space;D&space;}_{&space;j&space;}&space;\right|&space;}{&space;\left|&space;D&space;\right|&space;})$$)

$$$Gain(A$ &space;=&space;info(D)&space;-&space;info_{A}(D)$$)

$$$info<em>{A}(D$ &space;=&space;\sum&space;{&space;j=1&space;}^{&space;v&space;}&space;\frac&space;{&space;\left|&space;{&space;D&space;}{&space;j&space;}&space;\right|&space;}{&space;\left|&space;D&space;\right|&space;}&space;info({&space;D&space;}{&space;j&space;})$$)

$$$info(D$ &space;=&space;-&space;\sum&space;{&space;i=1&space;}^{&space;m&space;}{&space;{&space;p&space;}{&space;i&space;}{&space;log&space;}{&space;2&space;}({&space;p&space;}{&space;i&space;})&space;}&space;$$)