决策树和随机森林

随机森林和GBDT算法的基础是决策树

而建立决策树的算法由很多，ID3，C4.5,CART等，

• ID3：
  ID3算法的基本流程是：首先找出最有判别力的属性，把样例分成多个子集，每个子集又选择最有判别力的属性进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。
  而这个最有判别力的就是信息增益，我们用熵（entropy）这个概念来表示数据的不确定性

其中P（Ui）即是P(ui)是类别i出现概率，而计算整个属性的信息增益则是：

具体表示为代码：

''' 数据是一组特征值加一个lable'''
def entropy(class_probabilities):
    return sum(-p * math.log(p, 2)
        for p in class_probabilities 
        if p)

def class_probabilities(labels):
    total_count = len(labels)
    return [count / total_count
        for count in Counter(labels).values()
        ]

def data_entropy(labeled_data):        
    labels = [label for _, label in labeled_data]
    probabilities = class_probabilities(labels)
    return entropy(probabilities)

def partition_entropy(subsets):
    """find the entropy from this partition of data into subsets""" 
    total_count = sum(len(subset) for subset in subsets)
    return sum( data_entropy(subset) * len(subset) / total_count
                for subset in subsets )

然后根据取数据的信息增益最大的作为数的root节点，将其他属性进行分支，若该分支中存在不同lable，则递归计算最大信息增益。

c4.5是ID3的一种改进，既能处理标称型数据，又能连续型数据。为了处理连续型数据，该算法在相应的节点使用一个属性的阈值，利用阈值将样本划分成两部分，还有就是可以处理缺失某属性的数据，属性值缺失的样本在计算熵增益时被忽略。再就是分类完成后进行剪枝。

不同于c4.5和ID3：

• CART本质是对特征空间进行二元划分
• 剪枝:在CART过程中第二个关键的思想是用独立的验证数据集对训练集生长的树进行剪枝。

随机森林

随机森林是一种统计学习理论，其随机有两个方面：首先在训练的每一轮中，都是对原始样本集有放回的抽取固定数目的样本点，形成k 个互不相同的样本集。第二个点是：对于每一个决策树的建立是从总的属性中随机抽取一定量的属性作为分裂属性集，这样对于k个树分类器均是不相同的。由随机生成的k个决策树组成了随机森林。

对于每一个决策树来说，其分裂属性是不断地选取具有最大信息增益的属性进行排列。整个随机森林建立后，最终的分类标准采用投票机制得到可能性最高的结果。

随机森林是一个最近比较火的算法，它有很多的优点

• 在数据集上表现良好
• 在当前的很多数据集上，相对其他算法有着很大的优势
• 它能够处理很高维度（feature很多）的数据，并且不用做特征选择
• 在训练完后，它能够给出哪些feature比较重要
• 在创建随机森林的时候，对generlization error使用的是无偏估计
• 训练速度快
• 在训练过程中，能够检测到feature间的互相影响
• 容易做成并行化方法
  我们采用sklearn的RandomForestClassifier实际例子在我的上一篇文章中

在建立每一棵决策树的过程中，有两点需要注意 - 采样与完全分裂。首先是两个随机采样的过程，random forest对输入的数据要进行行、列的采样。对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting。然后进行列采样，从M个feature中，选择m个(m << M)。之后就是对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向的同一个分类。一般很多的决策树算法都一个重要的步骤 - 剪枝，但是这里不这样干，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。
按这种算法得到的随机森林中的每一棵都是很弱的，但是大家组合起来就很厉害了。我觉得可以这样比喻随机森林算法：每一棵决策树就是一个精通于某一个窄领域的专家（因为我们从M个feature中选择m让每一棵决策树进行学习），这样在随机森林中就有了很多个精通不同领域的专家，对一个新的问题（新的输入数据），可以用不同的角度去看待它，最终由各个专家，投票(vote)得到结果。
需要注意的是，随机森林中的单个决策树是没有意义的。

GBDT

GBRT(Gradient Boost Regression Tree)是一个应用很广泛的算法，可以用来做分类、回归。在很多的数据上都有不错的效果。我们下次接着共同学习。