Fork me on GitHub

大厂面试题分享:K 近邻、kmeans 聚类算法、随机森林、SVM 算法

问题1:介绍下K近邻、kmeans聚类算法

K近邻算法也称为knn算法。

**
**

knn算法的核心思想是未标记样本的类别,由距离其最近的k个邻居投票来决定。

具体的,假设我们有一个已标记好的数据集。此时有一个未标记的数据样本,我们的任务是预测出这个数据样本所属的类别。knn的原理是,计算待标记样本和数据集中每个样本的距离,取距离最近的k个样本。待标记的样本所属类别就由这k个距离最近的样本投票产生。

假设X_test为待标记的样本,X_train为已标记的数据集,算法原理如下:

  • 遍历X_train中的所有样本,计算每个样本与X_test的距离,并把距离保存在Distance数组中。
  • 对Distance数组进行排序,取距离最近的k个点,记为X_knn。
  • 在X_knn中统计每个类别的个数,即class0在X_knn中有几个样本,class1在X_knn中有几个样本等。
  • 待标记样本的类别,就是在X_knn中样本个数最多的那个类别。

算法优缺点

优点: 准确性高,对异常值和噪声有较高的容忍度。

缺点: 计算量较大,对内存的需求也较大。

算法参数

其算法参数是k,参数选择需要根据数据来决定。

k值越大,模型的偏差越大,对噪声数据越不敏感,当k值很大时,可能造成欠拟合;

k值越小,模型的方差就会越大,当k值太小,就会造成过拟合。

kmeans聚类算法

K-means算法的基本思想是:以空间中k个点为中心进行聚类,对最靠近他们的对象归类。通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果。

假设要把样本集分为k个类别,算法描述如下:

(1)适当选择k个类的初始中心,最初一般为随机选取;

(2)在每次迭代中,对任意一个样本,分别求其到k个中心的欧式距离,将该样本归到距离最短的中心所在的类;

(3)利用均值方法更新该k个类的中心的值;

(4)对于所有的k个聚类中心,重复(2)(3),类的中心值的移动距离满足一定条件时,则迭代结束,完成分类。

Kmeans聚类算法原理简单,效果也依赖于k值和类中初始点的选择。

问题2:介绍下随机森林和SVM算法

随机森林是一种基于bagging的分类算法,它通过自助法(bootstrap)重采样技术,从原始训练样本集N中有放回地重复随机抽取n个样本生成新的训练样本集合训练决策树,然后按以上步骤生成m棵决策树组成随机森林,新数据的分类结果按分类树投票多少形成的分数而定。

随机森林大致过程如下:

  1. 从样本集中有放回随机采样选出n个样本;
  2. 从所有特征中随机选择k个特征,对选出的样本利用这些特征建立决策树(一般是CART,也可是别的或混合);
  3. 重复以上两步m次,即生成m棵决策树,形成随机森林;
  4. 对于新数据,经过每棵树决策,最后投票确认分到哪一类。

2.随机森林特点:

随机森林有很多优点:

  1. 每棵树都选择部分样本及部分特征,一定程度避免过拟合;
  2. 每棵树随机选择样本并随机选择特征,使得具有很好的抗噪能力,性能稳定;
  3. 能处理很高维度的数据,并且不用做特征选择;
  4. 适合并行计算;
  5. 实现比较简单;

缺点:

  1. 参数较复杂;
  2. 模型训练和预测都比较慢。

SVM算法:

是一种二分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机。

SVM可分为三种:

  • 线性可分SVM

当训练数据线性可分时,通过最大化硬间隔(hard margin)可以学习得到一个线性分类器,即硬间隔SVM。

  • 线性SVM

当训练数据不能线性可分但是近似线性可分时,通过最大化软间隔(soft margin)也可以学习到一个线性分类器,即软间隔SVM。

  • 非线性SVM

当训练数据线性不可分时,通过使用核技巧(kernel trick)和最大化软间隔,可以学习到一个非线性SVM。

SVM的的学习策略就是间隔最大化,可形式化为一个求解凸二次规划的问题,也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。


8月14日(本周五),金融风控竞赛实战直播课程就要开课啦!

本次课程针对图计算感兴趣想要应用到实际的比赛或者业务中的同学,通过项目实战了解GNN在风控领域的应用。还配有课程全套代码 + 课件 + 直播答疑!

课程链接:https://www.julyedu.com/course/getDetail/330


本文地址:https://www.6aiq.com/article/1628621702505
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出