# 决策树

## 决策树相关理论

$$C_k$$代表某一类,$$\frac{|C_k|}{|D|}$$代表这个集合中样本是第k类的概率。

1. 对于当前根节点Root，对现有的样本集D，对所有的特征$$A_i$$的所有可能取值$$a_j$$计算基尼指数，选择使基尼指数最小的$$A_i$$和$$a_j$$，根据样本点对$$A_i=a_j$$的测试为“是”或“否”将D分为$$D_1$$和$$D_2$$。
2. $$D_1$$作为根节点Root的左子树的根节点Root_L的样本集，$$D_2$$作为根节点Root的右子树的根节点Root_R的样本集。
3. 重复1,2直到结点中样本个数小于阈值，或样本集基本属于同一类，或者没有更多特征（代表已经将所有的特征都过一遍了）。

CART剪枝

## 决策树的c++实现

### 实现

pair<int, double> DecisionTree::createSplitFeature(vector<vector<double >>& valRange){
priority_queue<pair<double, pair<int, double>>, vector<pair<double, pair<int, double>>>, std::greater<pair<double, pair<int, double>>>> minheap;
//pair<double, pair<int, double>> first value is Gini value, second pair (pair<int, double>) first value is split
//axis, second value is split value
vector<map<double, int>> dataDivByFeature(indim);  //vector size is num of axis, map‘s key is the value of feature, map‘s value is
//num belong to feature‘value
vector<set<double>> featureVal(indim);  //store value for each axis
vector<map<pair<double, double>, int>> datDivByFC(indim);  //vector size is num of axis, map‘s key is the feature value and class value, map‘s value is
//num belong to that feature value and class
set<double> cls;  //store num of class
for(const auto& featureId:features) {
if (featureId<0)
continue;
map<pair<double, double>, int> dtDivFC;
set<double> fVal;
for (auto& data:valRange){  //below data[featureId] is the value of one feature axis, data.back() is class value
cls.insert(data.back());
fVal.insert(data[featureId]);
else
if (dtDivFC.count(std::make_pair(data[featureId], data.back())))
dtDivFC[std::make_pair(data[featureId], data.back())] += 1;
else
dtDivFC[std::make_pair(data[featureId], data.back())] = 0;
}
featureVal[featureId] = fVal;
datDivByFC[featureId] = dtDivFC;
}
for (auto& featureId: features) {  // for each feature axis
if (featureId<0)
continue;
for (auto& feVal: featureVal[featureId]){  //for each feature value
double gini1 = 0 ;
double gini2 = 0 ;

double prob2 = 1 - prob1;
for (auto& c : cls){  //for each class
gini1 += pro1*(1-pro1);
int numC = 0;
for (auto& feVal2: featureVal[featureId])
numC += datDivByFC[featureId][std::make_pair(feVal2, c)];
gini2 += pro2*(1-pro2);
}
double gini = prob1*gini1+prob2*gini2;

minheap.push(std::make_pair(gini, std::make_pair(featureId, feVal)));
}
}
features[minheap.top().second.first]=-1;
return minheap.top().second;
}

## 统计学习方法笔记（1）——统计学习方法概论

1.统计学习 统计学习是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科,也称统计机器学习.统计学习是数据驱动的学科.统计学习是一门概率论.统计学.信息论.计算理论.最优化理论及计算机科学等多个领域的交叉学科. 统计学习的对象是数据,它从数据出发,提取数据的特征,抽象出数据的模型,发现数据中的知识,又回到对数据的分析与预测中去.统计学习关于数据的基本假设是同类数据具有一定的统计规律性,这是统计学习的前提. 统计学习的目的就是考虑学习什么样的模型和如何学习模型. 统计学习