大数据经典算法解析(1)一C4.5算法
1. 决策树模型：
决策树是一种通过对特征属性的分类对样本进行分类的树形结构，包括有向边与三类节点：
- 根节点（root node），表示第一个特征属性，只有出边没有入边；
- 内部节点（internal node），表示特征属性，有一条入边至少两条出边；
- 叶子节点（leaf node），表示类别，只有一条入边没有出边。
上图给出了（二叉）决策树的示例。决策树具有以下特点：
- 对于二叉决策树而言，可以看作是if-then规则集合，由决策树的根节点到叶子节点对应于一条分类规则；
- 分类规则是互斥并且完备的，所谓互斥即每一条样本记录不会同时匹配上两条分类规则，所谓完备即每条样本记录都在决策树中都能匹配上一条规则。
2. 决策树算法：
- 特征选择：指选择最大化所定义目标函数的特征。下面给出如下三种特征（Gender, Car Type, Customer ID）分裂的例子：图中有两类类别（C0, C1），C0: 6是对C0类别的计数。直观上，应选择Car Type特征进行分裂，因为其类别的分布概率具有更大的倾斜程度，类别不确定程度更小。
- 信息增益与信息增益比：为了衡量类别分布概率的倾斜程度，定义决策树节点的不纯度，其满足：不纯度越小，则类别的分布概率越倾斜；下面给出不纯度的的三种度量：其中，p(ck|t)表示对于决策树节点t的类别ck的概率。这三种不纯度的度量是等价的，在等概率分布是达到最大值。特别地，ID3算法选取熵值作为不纯度的度量，则cc指父节点对应所有样本记录的类别；AA表示选择的特征属性，即aiai的集合。那么，决策树学习中的信息增益ΔΔ等价于训练数据集中类与特征的互信息，表示由于得知特征AA的信息训练数据集cc不确定性减少的程度。C4.5算法流程与ID3相类似，只不过将信息增益改为信息增益比。
3. 决策树剪枝：
- 过拟合：生成的决策树对训练数据会有很好的分类效果，却可能对未知数据的预测不准确，即决策树模型发生过拟合——训练误差（training error）很小、泛化误差（generalization error，亦可看作为test error）较大。
- 剪枝策略：为了解决过拟合，C4.5通过剪枝以减少模型的复杂度。[2]中提出一种简单剪枝策略，通过极小化决策树的整体损失函数（loss function）或代价函数（cost function）来实现，决策树TT的损失函数为：其中，C(T)表示决策树的训练误差，α为调节参数，|T|为模型的复杂度。当模型越复杂时，训练的误差就越小。上述定义的损失正好做了两者之间的权衡。如果剪枝后损失函数减少了，即说明这是有效剪枝。具体剪枝算法可以由动态规划等来实现。
4. 参考资料：
- [1] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introduction to Data Mining .
- [2] 李航，《统计学习方法》.
- [3] Naren Ramakrishnan, The Top Ten Algorithms in Data Mining.
决策树是一种通过对特征属性的分类对样本进行分类的树形结构，包括有向边与三类节点：
- 根节点（root node），表示第一个特征属性，只有出边没有入边；
- 内部节点（internal node），表示特征属性，有一条入边至少两条出边；
- 叶子节点（leaf node），表示类别，只有一条入边没有出边。
上图给出了（二叉）决策树的示例。决策树具有以下特点：
- 对于二叉决策树而言，可以看作是if-then规则集合，由决策树的根节点到叶子节点对应于一条分类规则；
- 分类规则是互斥并且完备的，所谓互斥即每一条样本记录不会同时匹配上两条分类规则，所谓完备即每条样本记录都在决策树中都能匹配上一条规则。
2. 决策树算法：
- 特征选择：指选择最大化所定义目标函数的特征。下面给出如下三种特征（Gender, Car Type, Customer ID）分裂的例子：图中有两类类别（C0, C1），C0: 6是对C0类别的计数。直观上，应选择Car Type特征进行分裂，因为其类别的分布概率具有更大的倾斜程度，类别不确定程度更小。
- 信息增益与信息增益比：为了衡量类别分布概率的倾斜程度，定义决策树节点的不纯度，其满足：不纯度越小，则类别的分布概率越倾斜；下面给出不纯度的的三种度量：其中，p(ck|t)表示对于决策树节点t的类别ck的概率。这三种不纯度的度量是等价的，在等概率分布是达到最大值。特别地，ID3算法选取熵值作为不纯度的度量，则cc指父节点对应所有样本记录的类别；AA表示选择的特征属性，即aiai的集合。那么，决策树学习中的信息增益ΔΔ等价于训练数据集中类与特征的互信息，表示由于得知特征AA的信息训练数据集cc不确定性减少的程度。C4.5算法流程与ID3相类似，只不过将信息增益改为信息增益比。
3. 决策树剪枝：
- 过拟合：生成的决策树对训练数据会有很好的分类效果，却可能对未知数据的预测不准确，即决策树模型发生过拟合——训练误差（training error）很小、泛化误差（generalization error，亦可看作为test error）较大。
- 剪枝策略：为了解决过拟合，C4.5通过剪枝以减少模型的复杂度。[2]中提出一种简单剪枝策略，通过极小化决策树的整体损失函数（loss function）或代价函数（cost function）来实现，决策树TT的损失函数为：其中，C(T)表示决策树的训练误差，α为调节参数，|T|为模型的复杂度。当模型越复杂时，训练的误差就越小。上述定义的损失正好做了两者之间的权衡。如果剪枝后损失函数减少了，即说明这是有效剪枝。具体剪枝算法可以由动态规划等来实现。
4. 参考资料：
- [1] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, Introduction to Data Mining .
- [2] 李航，《统计学习方法》.
- [3] Naren Ramakrishnan, The Top Ten Algorithms in Data Mining.