为面试整理：常见机器学习算法

亦凉 2022-02-26 01:42 348阅读 1赞

**1.KNN**

**思想：**已知带有标签的训练集数据，给定一个测试数据，计算这个测试数据到训练集中各个点的距离并进行排序，选出距离这个测试数据最近的的K个点，然后看这k个点中，那个类别的数据多，那么这个测试数据就属于哪一类。

**优缺点：**思想简单，但是计算量比较大，并且数据集中的各个类型的数据量时平均的，例如A类1000个，B类100个，那么无论如何A类的数据是占优势的。

**2.决策树**

**2.1 ID3**

**熵：**随机变量的不确定度，表示分类的纯度。

**条件熵：**代表在某一个条件下，随机变量的不确定度。

**信息增益：**代表在一个条件下，随机变量的不确定度会减少多少。

**思想：**选择分裂后信息增益最大的属性作为分裂节点

**不足：**计算效率低，具有属性多值偏向性，对噪声敏感，处理连续数据有困难

**2.2 C4.5**

**思想：**在选择最优分裂属性时选择信息增益率最高的属性

**优点：**减少信息增益准则对取值较多的属性带来的影响，能对连续性的值进行离散化，在建立过程中能进行剪枝操作

**缺点：**计算效率低，忽略了条件属性的相关性，处理数据集的形式有限

**2.3 CART**

**思想：**选择基尼指数小的作为分裂属性

**决策树的优化：**决策树对训练数据往往分类准确率较高，但是对未知的数据准确率却不高，也就是容易出现过拟合的现象。解决方法可以剪枝处理，或者使用随机森林。

**3 随机森林（RF）**

**思想：**决策树为基分类器，对于每个基分类器，随机有放回的（bootstrap）抽取样本集，随机选取特征，最后用简单平均法复简单投票法对基分类器的结果进行融合。

**优点：**基分类器之间无依赖关系，可以实现并行处理；能处理高维数据，并且不用进行特征选择，训练完成后能对特征进行排名；每棵树尽最大可能的生长，不用剪枝；由于引进了两个随机，不容易过拟合

**缺点：**（有网友说：在噪声比较大的数据集上容易过拟合）训练时间较长

**为什么随机森林选三分之二的样本构建树：**因为随机森林采用bootstrap的采样方法，对于有m个样本的数据集需要进行有放回的采样m次，得到有m个样本的数据集，这样在m次中，没有被抽到的样本的概率就是（1-1/m)^m，去极限后等于1/e，约等于1/3，多以随机森林选择三分之二的样本构建树。

**4 GBDT**

**思想：**决策树为基分类器，每棵树模型是建立在之前模型残差和之上，也就是沿着残差梯度下降。网上看的一个例子：假设有三个树集成，某个人的真实年龄是18岁，第一棵树预测为12岁，那残差就是6，那第二棵树把某人的年龄设为6去学习，如果第二棵树真能把6分到叶子结点，那么累计两棵树的年龄就是某人的真实年龄。

**优点：**性能比RF好

**缺点：**不能进行并行处理

**5 xgboost**

**思想：**使用训练集训练第一棵树，然后使用测试集得到测试结果，测试结果与真实结果之间的差值为残差，并且将其作为第二棵树的标准答案，以此类推。

**xgboost与GBDT对比：**①GBDT是一种机器学习算法，而xgboost是工程实现；②GBDT的基分类器是决策树，xgboost可以是决策树可以是线性分类器；③xgboost在目标函数中加入了正则化项，包括叶子结点的个数及叶子结点得分的L2模的平方和，能有效的防止过拟合；④xgboost在模型训练时，对目标函数进行二阶泰勒展开，同时使用了一阶和二阶导数，而GBDT在训练过程中只对目标函数进行了一阶求导；⑤GBDT不支持样本的随机抽样和特征的随机抽样，但是xgboost可以和RF一样，对数据进行特征的随机抽样；⑥GBDT中没有对缺失值的处理，xgboost中加入了缺失值额处理策略。

**6 AdaBoost**

**思想：**用第一个基分类器对等权重的数据集进行分类，然后根据分类结果的对错，对数据集中的数据赋予不同的权重，用以下一轮的基分类器的训练，以此类推，最后将结果进行加权融合。

**优点：**具有较低的泛化误差，基分类器选择灵活，不易过拟合

**缺点：**对异常值比较敏感，因为异常值容易获得较大的权重，对分类结果有影响

**7 svm**

**思想：**对于数据集上的点，期望找到一个超平面，能将数据集中的点分成两类，同时，使得离超平面最近的点的几何间隔最大。

**支持向量：**在wT+b=1和wT+b=-1两个超平面上的点就是支持向量，支持向量确定了分离超平面wT+b=0，将其他点去掉也不影响结果

**核函数**：在对某点进行预测时，实际是求这个点与训练集中是支持向量的点的内积。在非线性情况下，需要将低维数据映射到高维，变成线性可分，如果直接将低维映射到高维，数据维数会增长特别多，所以就引入了核函数的思想，这个函数可以使在低维空间中进行的计算等于高维空间中计算内积的结果相同，这样就避开了高维空间的复杂计算

**核函数与超平面的关系：**在处理非线性问题时，需要通过核函数把数据从低维映射到高维，然后找到一个分离超平面，使数据集中的点线性可分

**超平面是如何确定的：**将优化问题转成拉格朗日函数，利用拉格朗日对偶性，使用SMO算法求解

**转成对偶问题的好处：**方便求解，方便引入核函数

**函数间隔与几何间隔**：y(wx+b)，如果这个式子大于零，分类正确，小于零，分类错误，表示了分类结果的正确性，同时，如果wx+b的模越大，说明分类的可信度就越高。但是如果w和b同时缩小几倍，虽然超平面没有变化，但是函数间隔y(wx+b)会发生变化，由此引出了几何间隔，本质是将w的大小固定为1，y(wx/||w||+b/||w||)

**8 HMM**

**思想：**隐马尔科夫是一个双重的随机过程，第一个随机过程是马尔科夫链，可以用π和A描述，表示状态序列和状态之间的转移，第二个随机过程可以用B来描述，表示观察序列

**HMM解决的三个问题：**①概率计算问题：已知模型参数和观测序列，求观测序列出现的概率，使用前向后向算法；②学习问题：已知观测序列，求模型的参数，使用极大似然法估计参数；③预测问题：已知模型参数和观测序列，求最可能的状态序列。

**9 朴素贝叶斯**

**思想：**假设各属性特征之间是相互独立的，根据贝叶斯公式求解

**优点：**简单易懂

**缺点：**假设各属性之间相互独立，在实际问题中往往不存在

**10 k-means**

**思想:**  首先需要选择k个初始中心点，计算数据集中的点到中心点的距离，并将其归到距离较近的一类，然后计算每一类中的平均值作为新的中心点，以此类推，直至中心点不再变化为止。

**k的选择：**①可以对数据进行可视化，观察聚成几类比较合适；②从k=2,...,10尝试，使轮廓系数最大的K值；

**初始中心的确定：**①多次选取初始中心进行实验，选择使损失函数较小的；②尽量选择距离较远的作为初始中心，任意选择初始中心A，计算点到A的距离，找到距离A最远的k个点，作为初始中心；③特别的，对于文本这种高稀疏向量，可以选择k个两辆正交的向量为初始中心点

如果类中心一直在变化，如何停止迭代：（不确定）①是不是可以设置一个阈值；②是不是可以设置最大迭代次数；

**11 谱聚类**

**思想：**对数据集中的点构建加权无向图，然后将无向图切成几个子图，使不同子图间的权重和尽可能低，子图内的权重和尽可能高。

**优点：**可以对任意形状的数据进行最优划分；由于使用了降维，处理高维数据时的效率比传统聚类算法高

**缺点：**聚类的效果依赖于相似矩阵，相似矩阵选取的不好，最终的聚类结果也有影响

**12 PCA**

**思想：**PCA是将原始的n维特征投影到k维新空间，使投影误差和最小，也就是寻找方差最大的方向，这k维向量就叫做主成分。目标函数选择最小化投影误差，通过对数据矩阵的协方差矩阵进行特征分解，得到的前k个特征值代表方差大小，特征值对应的特征向量，也就是各个方差对应的方向。用原始数据矩阵与前k个特征向量组成的矩阵相乘，得到降维后的特征。降维后的特征能最大程度的保留原始数据的特征

**PCA异常点检测：**PCA在做特征值分解之后得到的特征向量反映了数据方差变化程度不同的方向，特征值为数据对应方向上的方差大小，最大特征值为数据方差最大的方向，最小特征值为数据方差最小的方向，数据在不同方向上的变化特点反应了其内在特征，如果单个样本与整体样本的表现出的特点不一致，比如在某个方向的偏离较大，说明该点是异常点。（计算每个样本在所有方向上的投影误差和，然后设定一个阈值，对于新的数据点，计算它的投影误差和，并与阈值相比较，大于阈值，判断为异常点）

**其他问题：**

**1. 样本中类别不平衡问题（imblearn包）**

**①过采样方法（over\_sampling）:增加少数类样本的数量。**

**            随机过采样（RandomOverSampler）:在少数类样本集中随机选取样本，加入到数据集中，缺点是有许多重复样本，容易过拟合**

**            SMOTE（**Synthetic Minority Oversampling即合成少数类过采样技术**）： 对于少数类中的每一个样本，计算少数类样本集中到这个点的距离，得到她的k近邻，然后在这个样本点与k近邻点的连线上随机选择一个点。优点是没有样本的复制，提高了泛化性，但是在生成新样本的时候回产生样本重叠问题，同时，生成新样本是在样本点与k邻近点之间插值，插值时没有考虑周围点的分布，可能导致新的样本点分到多数类中**

**②欠采样（under\_sampling）：减少多数类样本的数量**

**             随机欠采样（****RandomUnderSampler****）：在多数类样本中随机选取样本，移除，缺点是移除了部分样本，可能导致部分信息的缺失**

**              EasyEnsemble: 在多数样本中随机采样n次，每次采样的样本数与少数类中的样本数相近，然后将这n个样本集分别与少数类样本集训练，最后得到n个模型，最终结果是这n个模型结果的平均。**

** ③过采样与欠采样结合：使用SMOTE过采样后悔产生一些噪音点数据，再对其进行清洗  
             SMOTET与SMOTEENN**

**2 衡量模型质量**

①准确率：分类正确的样本数量与总样本数量的比值

②F1-SCORE：衡量二分类的常用指标，兼顾了精确度和召回率，最大值1，最小值0，越大越好。精确度是正样本数量与模型预测到的正样本数量的比值，召回率是正样本数量与模型应该正确预测的正样本数量的比值

③混淆矩阵：横纵坐标是实际类别标签与预测类别标签，正负类别样本数量不平衡，可以用这个看

④ROC曲线下的AUC面积，ROC曲线的横纵坐标是假阳率（预测出的错误正样本数与真实负样本数的比值）和真阳率（预测出的正样本数与真实正样本数的比值）