Decision Trees
正如我们可以通过在 SVM 中选择非线性核来完成非线性可分数据的分类，Decision Tree 可以在每一步采用线性分割的方式将非线性可分的数据分类分解成一系列的子任务。
在决策树的建立过程中，一个很重要的概念是熵，其数学定义为：
- Entropy = -Σp(i)log2p(i)，其中 p(i) 代表第 i 个分类在样本集中的比例
在熵的定义中之所以取对数是由于对于多个概率乘积，很容易造成下溢，因此可以通过取对数的方式将其进行规整，进一步地，公式前面的负号是为了使得最终的结果为一个正数值。
这个概念衡量的是数据的掺杂程度 Level of impurity，在物理和化学中这个概念衡量的是混乱的程度。当一个数据集的熵为 0 时，代表其中所包含的数据的信息是确定的。
相对应的还可以定义信息增益:
- Information Gain = Change in Entropy = entropy(parent) - weighted_average(entropy(children))
在建立决策树时选择 Information Gain 最大的特征作为每一层的决策基础，在此基础上进行分割。在样本特征较多时决策树算法容易过拟合，因此在使用时需要特别注意。
决策树的超参数包括：
树的最大深度 Maximum depth
每一个分支包含的最小样本数 Minimum samples per leaf
每一个待拆分节点所包含的最少样本的数量 Minimum samples to split
最大特征数：当样本中包含的特征过多时，如果每一步分裂都检查每一个特征，那么决策树的建立将非常耗时，此时可以限制每一次分裂过程中需要检查的特征数量
Random Forest
鉴于决策树对于过拟合的倾向性，在实际使用中可以选择在每一次的决策树建立时，随机的选择样本集中的多个特征建立决策树（这里实际采用的是 Bagging 的思想），此时由于样本部分特征的选择可以有多种组合形式，因此会构建多个决策树。此后在对新的样本进行分类时，可以用这多个树对其进行投票，选择票数最多的分类作为最终的结果。这种基于随机特征选择的多个决策树的分类方法称为随机森林 Random Forest。
在 scikit-learn 中使用决策树分类器的方法如下：
from sklearn import tree
X = [[0, 0], [1, 1]]
Y = [0, 1]
classifier = tree.DecisionTreeClassifier()
classifier = classifier.fit(X, Y)
classifier.predict([[2., 2.]])
