决策树

基础算法

1. 决策树如何决定在哪个特征处分割？ 根据不同的方法来选择划分属性，从而衍生出不同的决策树算法。
   • ID3：用信息增益来进行决策树的划分属性的选择（使用信息增益的缺点：对取值数目较多的属性有所偏好，为减少这种影响，引入 C4.5），信息增益越大，纯度提升越大
   • C4.5：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选取增益率最高的 \(\begin{array}{c}{\text { Gain ratio }(D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)}} \\其中 ： {\operatorname{IV}(a)=-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \log _{2} \frac{\left|D^{v}\right|}{|D|}}\end{array}\)

• CART：选择使得划分后基尼指数最小的属性作为最优划分属性

  数据集 D 的纯度使用基尼值来度量，基尼值公式： \(\begin{aligned} \operatorname{Gini}(D) &=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_{k} p_{k^{\prime}} \\ &=1-\sum_{k=1}^{|\mathcal{Y}|} p_{k}^{2} \end{aligned}\) 属性 a 的基尼指数： \(\operatorname{index}(D, a)=\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Gini}\left(D^{v}\right)\)

以上不同算法不同的是他们对纯度的定义。

优化算法

减枝（pruning）是决策树学习算法对付“过拟合”的主要手段

1. 预减枝（prepruning）

2. 后减枝（postpruning）

缺失值处理

1. 权重（无缺失比）

决策树自写计算增益函数：

一些问题

1. 训练决策树时的参数是什么？

2. 在决策树的节点处分割的标准是什么？

3. 熵的公式是什么？

$H(X)=-\sum_{i=1}^{n}p_{i}log_{2}p_{i}$

1. 你如何用数学计算收集来的信息？你确定吗？
2. 随机森林的优点有哪些？
3. 介绍一下boosting算法。
4. gradient boosting如何工作？
5. 关于AdaBoost算法，你了解多少？它如何工作？
6. SVM中用到了哪些核？SVM中的优化技术有哪些？
7. SVM如何学习超平面？用数学方法详细解释一下。
8. 介绍一下无监督学习，算法有哪些？
9. 在K-Means聚类算法中，如何定义K？
10. 告诉我至少3中定义K的方法。