决策树，逻辑回归，PCA-算法面经

决策树

简述决策树原理？

决策树是一种自上而下，对样本数据进行树形分类的过程，由节点和有向边组成。节点分为内部节点和叶节点，其中每个内部节点表示一个特征或属性，叶节点表示类别。从顶部节点开始，所有样本聚在一起，经过根节点的划分，样本被分到不同的子节点中，再根据子节点的特征进一步划分，直至所有样本都被归到某个类别。

为什么要对决策树进行减枝？如何进行减枝？

Datawhale优秀回答者：Cassiel

剪枝是决策树解决过拟合问题的方法。在决策树学习过程中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，于是可能将训练样本学得太好，以至于把训练集自身的一些特点当作所有数据共有的一般特点而导致测试集预测效果不好，出现了过拟合现象。因此，可以通过剪枝来去掉一些分支来降低过拟合的风险。

决策树剪枝的基本策略有“预剪枝”和“后剪枝”。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

预剪枝使得决策树的很多分支都没有"展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降?但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于"贪心"本质禁止这些分支展开，给预剪枝决策树带来了欠拟含的风险。

后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树 。但后剪枝过程是在生成完全决策树之后进行的 并且要白底向上对树中的所有非叶结点进行逐 考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

简述决策树的生成策略？

Datawhale优秀回答者：立言

决策树主要有ID3、C4.5、CART，算法的适用略有不同，但它们有个总原则，即在选择特征、向下分裂、树生成中，它们都是为了让信息更“纯”。

举一个简单例子，通过三个特征：是否有喉结、身高、体重，判断人群中的男女，是否有喉结把人群分为两部分，一边全是男性、一边全是女性，达到理想结果，纯度最高。通过身高或体重，人群会有男有女。上述三种算法，信息增益、增益率、基尼系数对“纯”的不同解读。如下详细阐述：

综上，ID3采用信息增益作为划分依据，会倾向于取值较多的特征，因为信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着不确定性更高。C4.5对ID3进行优化，通过引入信息增益率，对特征取值较多的属性进行惩罚。

PCA

简述主成分分析PCA工作原理，以及PCA的优缺点？

PCA旨在找到数据中的主成分，并利用这些主成分表征原始数据，从而达到降维的目的。

工作原理可由两个角度解释，第一个是最大化投影方差（让数据在主轴上投影的方差尽可能大）；第二个是最小化平方误差（样本点到超平面的垂直距离足够近）。

做法是数据中心化之后，对样本数据协方差矩阵进行特征分解，选取前d个最大的特征值对应的特征向量，即可将数据从原来的p维降到d维，也可根据奇异值分解来求解主成分。

优点：

1.计算简单，易于实现

2.各主成分之间正交，可消除原始数据成分间的相互影响的因素

3.仅仅需要以方差衡量信息量，不受数据集以外的因素影响

4.降维维数木有限制，可根据需要制定

缺点：

1.无法利用类别的先验信息

2.降维后，只与数据有关，主成分各个维度的含义模糊，不易于解释

3.方差小的非主成分也可能含有对样本差异的重要信息，因降维丢弃可能对后续数据处理有影响

4.线性模型，对于复杂数据集难以处理（可用核映射方式改进）

参考链接：

https://www.jianshu.com/p/487818da5de3

PCA中有第一主成分、第二主成分，它们分别是什么，又是如何确定的？

Datawhale优秀回答者：孙洪杰

主成分分析是设法将原来众多具有一定相关性（比如P个指标），重新组合成一组新的互相无关的综合指标来代替原来的指标。主成分分析，是考察多个变量间相关性一种多元统计方法，研究如何通过少数几个主成分来揭示多个变量间的内部结构，即从原始变量中导出少数几个主成分，使它们尽可能多地保留原始变量的信息，且彼此间互不相关，通常数学上的处理就是将原来P个指标作线性组合，作为新的综合指标。

最经典的做法就是用F1（选取的第一个线性组合，即第一个综合指标）的方差来表达，即Var(F1)越大，表示F1包含的信息越多。因此在所有的线性组合中选取的F1应该是方差最大的，故称F1为第一主成分。如果第一主成分不足以代表原来P个指标的信息，再考虑选取F2即选第二个线性组合，为了有效地反映原来信息，F1已有的信息就不需要再出现在F2中，用数学语言表达就是要求Cov(F1, F2)=0，则称F2为第二主成分，依此类推可以构造出第三、第四，……，第P个主成分。

逻辑回归

逻辑回归是线性模型么，说下原因？

Datawhale优秀回答者：梦大大

逻辑回归是广义线性模型，原因如下：

狭义线性模型的前提是因变量误差是正态分布，但很多情况下这并不满足，比如对足球比分的预测显然用泊松分布是更好的选择。而广义的”广”在于引入了联系函数，于是误差变成了只要满足指数分布族就行了，因此适用性更强。

简单来说广义线性模型分为两个部分，第一个部分是描述了自变量和因变量的系统关系，也就是”线性”所在；第二个部分是描述了因变量的误差，这可以建模成各种满足指数分布族的分布。而联系函数就是把这两个部分连接起来的桥梁，也就是把因变量的期望表示为了自变量线性组合的函数。而像逻辑回归这样的简单广义线性模型，实际是将自变量的线性组合变成了联系函数的自然参数，这类联系函数也可以叫做正则联系函数。

逻辑回归算法为什么用的是sigmoid函数而不用阶跃函数？

阶跃函数虽然能够直观刻画分类的错误率，但是由于其非凸、非光滑的特点，使得算法很难直接对该函数进行优化。而sigmoid函数本身的特征（光滑无限阶可导），以及完美的映射到概率空间，就用于逻辑回归了。解释上可从三个方面：- 最大熵定理- 伯努利分布假设- 贝叶斯理论

其他

分析KNN与K-means中k值如何进行选取并解释两者之间的区别？

knn的k是指选择与目标最近k个数量样本来进行预测。可以用多次交叉检验迭代对比后选择最优。kmeans的k是指簇中心数量，也就是聚类的数量。可以用肘部法，也是通过不同的k值，每次都计算所有样本与距离自己最近簇中心的距离之和，最后用k值和对应的距离画散点图，寻找一个最优的拐点。手肘法是个经验学习，所以不够自动化，然后提出了Gap Statistic方法。

对于数据异常值，我们一般如何处理？

1.视为无效信息（噪声点）：结合异常值检测算法，检测出后直接丢弃；

2.视为有效信息（信号点）：

作为缺失值，用缺失值的方式处理；

3.用平均值（中位数）等统计特征进行修正，结合前后观测值；

4.不处理，直接在具有异常值的数据上进行数据挖掘；

什么是特征选择，为什么要进行特征选择，以及如何进行？

Datawhale优秀回答者：Summer

特征选择是通过选择旧属性的子集得到新属性，是一种维规约方式。

Why：

应用方面：提升准确率，特征选择能够删除冗余不相关的特征并降低噪声，避免维灾难。在许多数据挖掘算法中，维度较低，效果更好；

执行方面：维度越少，运行效率越高，同时内存需求越少。

How，有三种标准的特征选择方法

1.嵌入方法，算法本身决定使用哪些属性和忽略哪些属性。即特征选择与训练过程融为一体，比如L1正则、决策树等；

2.过滤方法，独立于算法，在算法运行前进行特征选择。如可以选择属性的集合，集合内属性对之间的相关度尽可能低。常用对特征重要性（方差，互信息，相关系数，卡方检验）排序选择；可结合别的算法（随机森林，GBDT等）进行特征重要性提取，过滤之后再应用于当前算法。

3.包装方法，算法作为黑盒，在确定模型和评价准则之后，对特征空间的不同子集做交叉验证，进而搜索最佳特征子集。深度学习具有自动化包装学习的特性。总之，特征子集选择是搜索所有可能的特性子集的过程，可以使用不同的搜索策略，但是搜索策略的效率要求比较高，并且应当找到最优或近似最优的特征子集。一般流程如下图：