ID3, C4.5 and Cart trees
"TLDR: This is a blog post on the implementation of DecisionTree algorithm using C++."
C4.5 is a very classic decision tree algorithm, modified based on the ID3 algorithm.
Disadvantages of ID3:
-
The attribute selection method based on information gain will be biased towards selecting attributes with many categories.
-
Cannot handle continuous attributes
Improvements to C4.5:
-
Use gain rate (information gain ratio) as a metric to select optimal features to prevent the algorithm from being biased towards features with a larger number of categories.
-
By discretizing continuous attributes (note that the processing here is preprocessing, discretizing the partitions in advance), and then calculating the information gain ratio
-
In
C4.5, you can also choose the average or mode to fill in missing values through data statistics. -
In
ID3, there is a tendency to build a complete decision tree, which will lead to overfitting problems. InC4.5, pre-pruning and post-pruning are used to suppress the growth of the tree.
Cart tree is better than C4.5, mainly in the following aspects:
-
The Cart tree uses the Gini index as the metric: , a total of K categories
-
For continuous values, C4.5 discretizes the data in advance, while Cart directly finds the optimal dividing point for the continuous data.
-
Cart trees can also handle regression problems by using variance minimization as the splitting criterion.
There are a lot of theories here and there, why not just draw a Cart tree with your hands:
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
struct TreeNode {
int feature_index;
double threshold;
std::string value;
TreeNode* left = nullptr;
TreeNode* right = nullptr;
TreeNode(int index, double thresh, std::string val) : feature_index(index), threshold(thresh), value(val) {}
};
class DecisionTree {
public:
DecisionTree(double min_samples_split, double max_depth)
: m_min_samples_split(min_samples_split), m_max_depth(max_depth) {}
void train(const std::vector<std::vector<double>>& features, const std::vector<int>& labels);
int predict(const std::vector<double>& sample);
private:
TreeNode* build_tree(const std::vector<std::vector<double>>& features, const std::vector<int>& labels, int depth);
std::pair<double, double> find_best_split(const std::vector<std::vector<double>>& features, const std::vector<int>& labels, int feature_index);
double gini_impurity(const std::vector<int>& labels);
double weighted_gini_impurity(const std::vector<int>& left_labels, const std::vector<int>& right_labels);
int majority_vote(const std::vector<int>& labels);
double m_min_samples_split;
double m_max_depth;
};
void DecisionTree::train(const std::vector<std::vector<double>>& features, const std::vector<int>& labels) {
if (features.size() == 0 || features[0].size() == 0) {
std::cerr << "Error: Features or labels are empty." << std::endl;
return;
}
m_root = build_tree(features, labels, 0);
}
TreeNode* DecisionTree::build_tree(const std::vector<std::vector<double>>& features, const std::vector<int>& labels, int depth) {
if (labels.size() <= m_min_samples_split || depth >= m_max_depth) {
return new TreeNode(-1, -1, std::to_string(majority_vote(labels)));
}
int best_feature_index = -1;
double best_threshold = -1;
double best_impurity = 1.0; // Maximum impurity
for (int i = 0; i < features[0].size(); ++i) {
auto [threshold, impurity] = find_best_split(features, labels, i);
if (impurity < best_impurity) {
best_feature_index = i;
best_threshold = threshold;
best_impurity = impurity;
}
}
if (best_feature_index == -1) {
return new TreeNode(-1, -1, std::to_string(majority_vote(labels)));
}
std::vector<std::vector<double>> left_features;
std::vector<int> left_labels;
std::vector<std::vector<double>> right_features;
std::vector<int> right_labels;
for (int i = 0; i < features.size(); ++i) {
if (features[i][best_feature_index] < best_threshold) {
left_features.push_back(features[i]);
left_labels.push_back(labels[i]);
} else {
right_features.push_back(features[i]);
right_labels.push_back(labels[i]);
}
}
TreeNode* node = new TreeNode(best_feature_index, best_threshold, "");
node->left = build_tree(left_features, left_labels, depth + 1);
node->right = build_tree(right_features, right_labels, depth + 1);
return node;
}
std::pair<double, double> DecisionTree::find_best_split(const std::vector<std::vector<double>>& features, const std::vector<int>& labels, int feature_index) {
std::vector<double> values;
for (const auto& feature : features) {
values.push_back(feature[feature_index]);
}
std::sort(values.begin(), values.end());
double best_threshold = -1;
double best_impurity = 1.0; // Maximum impurity
for (int i = 0; i < values.size() - 1; ++i) {
double threshold = (values[i] + values[i + 1]) / 2.0;
std::vector<int> left_labels, right_labels;
for (int j = 0; j < features.size(); ++j) {
if (features[j][feature_index] < threshold) {
left_labels.push_back(labels[j]);
} else {
right_labels.push_back(labels[j]);
}
}
double impurity = weighted_gini_impurity(left_labels, right_labels);
if (impurity < best_impurity) {
best_threshold = threshold;
best_impurity = impurity;
}
}
return {best_threshold, best_impurity};
}
double DecisionTree::gini_impurity(const std::vector<int>& labels) {
std::map<int, int> label_counts;
for (int label : labels) {
label_counts[label]++;
}
double impurity = 1.0;
for (const auto& pair : label_counts) {
double p = static_cast<double>(pair.second) / labels.size();
impurity -= p * p;
}
return impurity;
}
double DecisionTree::weighted_gini_impurity(const std::vector<int>& left_labels, const std::vector<int>& right_labels) {
double total = left_labels.size() + right_labels.size();
double left_impurity = gini_impurity(left_labels);
double right_impurity = gini_impurity(right_labels);
return (left_labels.size() * left_impurity + right_labels.size() * right_impurity) / total;
}
int DecisionTree::majority_vote(const std::vector<int>& labels) {
std::map<int, int> label_counts;
for (int label : labels) {
label_counts[label]++;
}
int most_common_label = 0;
int max_count = 0;
for (const auto& pair : label_counts) {
if (pair.second > max_count) {
max_count = pair.second;
most_common_label = pair.first;
}
}
return most_common_label;
}
int DecisionTree::predict(const std::vector<double>& sample) {
TreeNode* current_node = m_root;
while (current_node->left != nullptr && current_node->right != nullptr) {
if (sample[current_node->feature_index] < current_node->threshold) {
current_node = current_node->left;
} else {
current_node = current_node->right;
}
}
return std::stoi(current_node->value);
}
//Example usage
int main() {
std::vector<std::vector<double>> features = {{2.5, 0.5}, {2.5, 0.75}, {2.5, 1.0}, {2.5, 1.25}, {2.5, 1.5}, {2.5, 1.75}, {1.0, 1.0}, {1.0, 1.5}, {1.0, 2.0}, {1.0, 2.5}, {0.5, 1.0}, {0.5, 1.5}, {0.5, 2.0}, {0.5, 2.5}};
std::vector<int> labels = {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1};
DecisionTree tree(2, 10);
tree.train(features, labels);
std::vector<double> test_sample = {1.5, 1.0};
std::cout << "Prediction: " << tree.predict(test_sample) << std::endl;
return 0;
}