代码
继上篇博客Kaggle竞赛（一）预测泰坦尼克号幸存者 数据导入和预处理。现在正式进入机器学习的算法部分，我想介绍的第一个是决策树Decision Tree。
1
2
3
4
5
6
7# Decision Tree
score=[]
for i in range(1,20):
clf_dt = tree.DecisionTreeClassifier(max_depth=i)
clf_dt.fit (X_train, y_train)
score.append(clf_dt.score (X_test, y_test))
plt.bar(range(1,20),score)
我们看出来3层是最好的深度。然后我们用cross-validation来算20次随机分配后的准确度。
1
2
3
4
5
6clf_dt = tree.DecisionTreeClassifier(max_depth=3)
shuffle_validator = cross_validation.ShuffleSplit(len(X), n_iter=20, test_size=0.2, random_state=0)
def test_classifier(clf):
scores = cross_validation.cross_val_score(clf, X, y, cv=shuffle_validator)
print("Accuracy: %0.4f (+/- %0.2f)" % (scores.mean(), scores.std()))
test_classifier(clf_dt)
Accuracy: 0.8149 (+/- 0.03)
最后，3层决策树的准确度大概是81.49%。
如果已有基础，只想知道怎么写代码，怎么将它应用到泰坦尼克数据上，可以只看到这。
原理
- 优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特 征数据。
- 缺点：可能会产生过度匹配问题。
- 适用数据类型：数值型和标称型。
决策树的构造
在构造决策树时，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征。完成测试之后，原始数据集就被划分为几个数据子集。
ID3算法
我们用ID3算法划分数据集，该算法处理如何划分数据集，何时停止划分数据集，进一步的信息可以参见wikipedia。每次划分数据集时我们只选取一个特征属性，如果训练集中存在20个特征，第一次我们选择哪个特征作为划分的参考属性呢？
下面数据包含5个海洋动物，特征包括：不浮出水面是否可以生存，以及是否有脚蹼。我们可以将这些动物分成两类：鱼类和非鱼类。现在我们想要决定依据第一个特征还是第二个特征划分数据。在回答这个问题之前，我们必须采用量化的方法判断如何划分数据。下一小节将详细讨论这个问题。
| 不浮出水面是否可以生存No surfacing? | 是否有脚蹼Flippers? | 属于鱼类Fish? | |
|---|---|---|---|
| 1 | 是 | 是 | 是 |
| 2 | 是 | 是 | 是 |
| 3 | 是 | 否 | 否 |
| 4 | 否 | 是 | 否 |
| 5 | 否 | 是 | 否 |
信息增益
熵定义为信息的期望值。一个系统越是有序，信息熵就越低；反之，一个系统越是混乱，信息熵就越高。在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号xi的信息定义为 $$ l(x_i)=-log_2 p(x_i) $$ 其中是 $ p(x_i) $选择该分类的概率。
为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到： $$ H=-\sum^n_{i=1}p(x_i)log_2p(x_i) $$ 其中n 是分类的数目。
ID3(Iterative Dichotomiser 3 迭代二叉树3代)划分特征使用的就是信息增益IG（Information Gain）。一个属性的信息增益越大，表明属性对样本的熵减少的能力就更强，该属性使得数据所属类别的不确定性变为确定性的能力越强。信息增益在统计学中称为互信息，互信息是条件概率与后验概率的比值，化简之后就可以得到信息增益。所以说互信息其实就是信息增益。计算方法【互信息=熵-条件熵】。
首先计算特征A对数据集D的经验条件熵H(D|A),在数学上就是条件概率分布（Condition Probability）. $$ H(D|A)=\sum_j \frac{D_j}{D} \times H(D_j), \frac{D_j}{D}是第j个分区的权重 $$ 引入条件熵，在信息论中主要是为了消除结果的不确定性。然后计算信息增益 $$ Gain(A)=H(D)-H(D|A) $$ 在上面的例子中， $$ H(D)=-\frac{2}{5} log_2\frac{2}{5}-\frac{3}{5} log_2\frac{3}{5}=0.971位 $$
$$ H(D|No\ surfacing)=\frac{3}{5}(-\frac{2}{3}log_2\frac{2}{3}-\frac{1}{3}log_2\frac{1}{3})+\frac{2}{5}(-\frac{2}{2}log_2\frac{2}{2}-\frac{0}{2}log_2\frac{0}{2})=0.551位 $$
$$ H(D|Flippers)=\frac{4}{5}(-\frac{2}{4}log_2\frac{2}{4}-\frac{2}{4}log_2\frac{2}{4})+\frac{1}{5}(-\frac{0}{1}log_2\frac{0}{1}-\frac{1}{1}log_2\frac{1}{1})=0.8位 $$
$$ Gain(No \ Surfacing)=0.971-0.551=0.42位 $$
$$ Gain(Flippers)=0.971-0.8=0.171位 $$
由于No Surfacing在属性中具有最高的信息增益，所以它被选作根节点的分裂特征。下面再进行递归计算信息增益，在此就不展示了。
C4.5算法
与ID3算法类似，我们还可以用C4.5（使用增益率）
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。另外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
另外，无论是ID3还是C4.5最好在小数据集上使用，决策树分类一般只试用于小数据。当属性取值很多时最好选择C4.5算法，ID3得出的效果会非常差，因为使用信息增益划分时它倾向于取值多的属性。
首先要计算分裂信息： $$ Split_H(D|A)=-\sum \frac{|D_j|}{D} \times log_2(\frac{|D_j|}{D}) $$ 再计算信息增益率： $$ IG Rate(A)=\frac{Gain(A)}{Split_H(D|A)} $$ 选择最大增益率的特征作为分裂特征。
CART算法
在CART算法，我们将用到基尼指数，sklearn中决策树和随机森林中默认的属性划分标准也是它。Gini index划分是二元的，它度量的是数据分区或训练元组集D的不纯度，表示的是一个随机选中的样本在子集中被分错的可能性。 $$ Gini(D)=1-\sum p_i^2，其中，p_i是D中元组数以C_i类的概率，对m个类计算和 $$ Gini指数越大，不纯度越大，越不容易区分。假设A有v个不同的值出现在特征D中，它的二元划分有2v−22v−2种（除去自己和空集）。当考虑二元划分裂时，计算每个结果分区的不纯度加权和。比如A有两个值，则特征D被划分成D1和D2,这时Gini指数为： $$ Gini_A(D)=\frac{D_1}{D}Gini(D_1)+\frac{D_2}{D}Gini(D_2) $$ 对于每个属性，考虑每种可能的二元划分，对于离散值属性，选择该属性产生最小Gini指数的自己作为它的分裂信息。
参考文献
- 刘帝伟的博客 http://www.csuldw.com/2015/05/08/2015-05-08-decision%20tree
- Machine Learning in action https://www.manning.com/books/machine-learning-in-action