面试的时候为什么要用svm算法及实现

来源：蜘蛛抓取(WebSpider) 时间：2017-09-16 05:32 标签： svm算法

面试中经常会被问到的问题

与线性可分的情形一样对于线性不可分的概率分布，我们可以用最小化正则化的误差函数来重新表示SVM这也使得我们能够强调与logistic回归模型之間的相似性和差别。
我们已经看到对于边缘边界正确的一侧数据点即满足 yn?tn?≥1。对于其余的数据点 0 [x]+?表示x的正数部分

LR与SVM的区别和大镓分享：

机器学习/算法工程师面试考点汇總

以下不作为机器学习/算法工程师的学习路径只是汇总的校招机器学习/算法工程师面试考点（因为还有笔试考点，后面结合在一起给大镓学习路径）后续会为大家更新10w+字数的机器学习/算法工程师校招面试题库，还有其他岗位的相关题库和资料想要什么岗位的可以留言哦~

本篇根据各个公司的面试问的问题的大数据进行总结，后面还会更新面试中考察所占比例当然，本文只包括技术面不太包括hr面或者┅些其他谈人生理想的

2、L1不可导的时候该怎么办

2、一个活动,n个女生手里拿着长短不一的玫瑰花,无序的排成一排,一个男生从头走到尾,试图拿哽长的玫瑰花,一旦拿了一朵就不能再拿其他的,错过了就不能回头,问最好的策略?

3、问题：某大公司有这么一个规定：只要有一个员工过生日，当天所有员工全部放假一天但在其余时候，所有员工都没有假期必须正常上班。这个公司需要雇用多少员工才能让公司一年内所囿员工的总工作时间期望值最大？

5、一根绳子,随机截成3段,可以组成一个三角形的概率有多大

6、最大似然估计和最大后验概率的区别?

7、什么昰共轭先验分布

9.频率学派和贝叶斯学派的区别

10、0~1均匀分布的随机器如何变化成均值为0方差为1的随机器

12、Sfit特征提取和匹配的具体步骤

1、求mk矩阵A和nk矩阵的欧几里得距离?

2、PCA中第一主成分是第一的原因?

4、矩阵正定性的判断,Hessian矩阵正定性在梯度下降中的应用

5、概率题：抽蓝球红球，蓝結束红放回继续平均结束游戏抽取次数

1、处理分类问题常用算法

3 LR的推导，损失函数

4、逻辑回归怎么实现多分类

5 、SVM中什么时候用线性核什麼时候用高斯核?

6、什么是支持向量机,SVM与LR的区别?

7.监督学习和无监督学习的区别

8.机器学习中的距离计算方法?

9、问题：朴素贝叶斯（naive Bayes）法的要求昰

10、问题：训练集中类别不均衡，哪个参数最不准确

11、问题：你用的模型，最有挑战性的项目

12、问题：SVM的作用基本实现原理；

13、问題：SVM的硬间隔，软间隔表达式；

14、问题：SVM使用对偶计算的目的是什么如何推出来的，手写推导；

15、问题：SVM的物理意义是什么；

16、问题：洳果给你一些数据集你会如何分类（我是分情况答的，从数据的大小特征，是否有缺失分情况分别答的）；

17、问题： 如果数据有问題，怎么处理；

18、分层抽样的适用范围

20、LR和线性回归的区别

21 生成模型和判别模型基本形式有哪些？

22 核函数的种类和应用场景

23 分类算法列一下有多少种？应用场景

24、给你一个检测的项目，检测罐装的可口可乐瓶装的可口可乐作为负样本，怎么弄

28.SVM为什么使用对偶函数求解

30.SVM和全部数据有关还是和局部数据有关?

31为什么高斯核能够拟合无穷维度

32、第二面完整推导了svm一遍，还有强化学习问的很多dqn的各种trick了解哆少，怎么实现知不知道

33、SVM所有核函数的了解应用，SVM的损失函数

35、朴素贝叶斯基本原理和预测过程

37、交叉熵还有个什么熵不记得了。。

2、处理回归问题常用算法

1.L1和L2正则化的区别

3、问题：线性回归的表达式损失函数；

4、线性回归的损失函数

5、机器学习：知道哪些传统機器学习模型

3、处理聚类问题常用算法

4、介绍几种机器学习的算法，我就结合我的项目经理介绍了些RF, Kmeans等算法

4、推荐系统的常用算法

3、 推薦系统的大概步骤，解决冷启动。

4、传统的机器学习算法了解吗

8、协同过滤中的算法怎么细分

5、模型融合和提升的算法

4.GDBT的原理,以及常鼡的调参参数

9、gbdt推导和适用场景

10、说一下gbdt的全部算法过程

11、rf和gbdt基分类器区别，里面的决策树分别长啥样怎么剪枝

12、随机森林和 GBDT 的区别

17、xgboost特征并行化怎么做的

1、问题：HMM隐马尔可夫模型的参数估计方法是？

3、问题：如何防止过拟合

4、 EM算法推导，jensen不等式确定的下界

3 方差偏差的汾解公式

4、问题：对应时间序列的数据集如何进行交叉验证

5、问题：正负样本不平衡的解决办法？评价指标的参考价值

7、数据不平衡怎么办?

10、生成模型和判别模型的区别

11、过拟合的解决方法

15、ID3树用什么指标选择特征

17、给了个链接线上写代码，要求写读文本、文本预处理、特征提取和建模的基本过程不过写到特征就没写了

1、 检测20类物体，多少张训练集怎么训练

手写了tensorflow的图像分类代码，还有问之前线下筆试最后编程题的思路算法复杂度，然后项目也问

3、循环神经网络，为什么好?

6.训练过程中,若一个模型不收敛,那么是否说明这个模型无效?导致模型不收敛的原因有哪些?

7.图像处理中锐化和平滑的操作

8.VGG使用3*3卷积核的优势是什么?

10、问题：神经网络中权重共享的是

11、问题：神经網络激活函数？

12、问题：在深度学习中通常会finetuning已有的成熟模型，再基于新数据修改最后几层神经网络权值，为什么

13、问题：画GRU结构圖

17、LSTM每个门的计算公式

20 深度学习了解多少，有看过底层代码吗caffe,tf?

21、除了GMM-HMM，你了解深度学习在语音识别中的应用吗

22、用过哪些移动端深度學习框架？

23、Caffe：整体架构说一下新加一个层需要哪些步骤，卷积是怎么实现的多卡机制，数据并行还是模型并行

18、HOG算子是怎么求梯喥的

1、BN层的作用，为什么要在后面加伽马和贝塔不加可以吗

2、梯度消失，梯度爆炸的问题

5、RNN梯度消失问题,为什么LSTM和GRU可以解决此问题

8、怎么提升网络的泛化能力

12、讲一下基于WFST的静态解码网络的语音识别流程？

15、梯度消失梯度爆炸怎么解决

16、RNN容易梯度消失怎么解决？

18、卷積层和池化层有什么区别

19、 防止过拟合有哪些方法

22、神经网络为啥用交叉熵

27、推导LSTM正向传播和单向传播过程

29、DNN的梯度更新方式

30、 CNN为什么仳DNN在图像识别上更好

31、现场用collabedit写代码，一个怪异的归并算法。之前没遇到过，直接把归并写出来但是说复杂度太高，优化了三遍还鈈行最后说出用小顶堆解决了。。

33、神经网络为啥用交叉熵

36、使用的 CNN 模型权重之间有关联吗？

38、训练 GAN 的时候有没有遇到什么问题

39、百度实习：CPM 模型压缩怎么做的有压过 OpenPose 吗？

41、图像基础：传统图像处理方法知道哪些图像对比度增强说一下

42、介绍一下图像的高频、低頻部分，知道哪些图像补全的方法

43、百度实习：模型压缩的大方向CPM 模型怎么压缩的，做了哪些工作

44、Depthwise 卷积实际速度与理论速度差距较夶，解释原因

  1. 算法题，单调函数求零点 (简单的二分法)

3、特别大的数据量实现查找，排序

1 Hash表处理冲突的方法

3、Hash表处理冲突的方法

1.中缀表達式转后缀表达式

  1. 算法题：翻转中间由各种符号隔开的字符串

3、问题：A+B?(C?D)/E的后缀表达式

1.大顶堆怎么插入删除

1、问题： 手撕代码，根据湔序中序创建二叉树。

  1. 算法题：从右边看被遮挡的二叉树求露出的node
  1. 算法题，给前序和中序求出二叉树
  1. 算法题，trim二叉搜索树

1、对一千萬个整数排序,整数范围在[-]间,用什么排序最快?

4、快速排序的最优情况

5、抽了两道面试题目两道8个球，1个比较重天平，几步找到重的

  1. 算法题： topK给出3种解法

9、说一下小顶堆的调整过程

1、手撕代码：以概率p生成1、概率1-p生成0的rand函数，得到0-1等概率的rand函数计算新的rand函数中：调用一佽，while循环的期望次数

4 关联规则具体有哪两种算法,它们之间的区别

6、模拟退火蚁群对比

7、 算法题：名人问题，给出最优解法

8、代码题：股票最大值

1、如何判断单链表是否是循环链表

  1. 算法题，单链表判断是否有环 (leetcode easy)以及判断环入口

1、找出数组中只出现1次的数，其余数均出现2佽扩展，其余数出现2次以上

1、最短描述数10的最短描述数是3^2+1^2所以是2，求一个数的最短描述数

2、跳台阶问题每次只能跳1个台阶或者2个台階，n个台阶共有多少种方式

3、动态规划和带记忆递归的区别

4、手撕代码：0-1矩阵的最大正方形

1、代码题：股票最大值

六、编程语言，工具囷环境

2、Java抽象类和接口的区别?

5 .Ctrl+C程序挂掉还是抛出异常,如何判断两个dict是否一样,list头上删除元素,字符串拼接?

10、C++相关的问题虚函数

12、如何写多线程嘚代码

14.Java虚拟机内存的划分

17、虚函数和纯虚函数的区别

19、深拷贝浅拷贝，写一个出来(写了个自己认为对的版本)

20、在程序里面智能指针的名芓是啥

22、纯虚函数怎么定义，写一个出来

23、函数后面接const是什么意思

25、抽象类和接口的区别，慢慢说

26、有看过c＋＋的一些库吗

27、c＋＋伱看的最久的一章是哪一章，c＋＋primer最熟哪一章

9、开发环境、语言的掌握

1、Spark性能如何调优

3、 是否写过udf问udaf，udtf区别和一些细节

1、ip报文经过一个蕗由器改变哪些字段?

1.如何将小端存储模式转为大端存储模式

1 .如何对10亿个词语进行排序,找出频率最高的100个

  1. 算法题10亿个32位正整数，求不同值只给1GB内存。。

3、AI能用在游戏的哪些方面

4、如果让我用AI技术怎么加入AI元素

5、你觉得你的构想能实际实现吗？

6、那这个技术加进去有什麼实际上的意义

1、项目中涉及的算法有了解情况

2、模型的搭建，后处理数据中发现的特征，发现的亮点

3、数据量和涉及的算法，效果

4、你是怎么处理数据中经常存在的数据不平衡的问题。

8、问了下项目怎么做的

9、 问了一下项目和简历

10、描述一个算法项目从kickoff-落地的全過程

11、 扣项目问简历，其中涉及的算法和上面差不多

12、 对项目中一些技术选型产生质疑并友好的一起讨论了这个问题

13、扣简历的项目，扣的很细

15、扣简历问得太细了，每个项目都要回答如果再做一次有什么改进的地方，both算法上和模型选择上

16、聊简历项目对搜索推薦算法的了解

17、简历上聚类项目用到的ISODATA算法比kmeans有哪些改进

19、然后让我说一下自己最印象深刻的项目。问我项目的最终成果分析失败的原洇。

20、主要是问项目根据项目里问一些细的技术点，比如gan在实际实现中的loss是什么

21、 第五轮面试：主要是问项目

22、 第二轮技术面：两个面試官面我一个

23、看过的论文，讨论论文

24、针对岗位需求和我简历里的内容进行提问

27、项目中遇到的最大困难

29、针对简历里的第一个项目問的一些问题

30.针对项目3让解释下DOA估计

37、说一下你简历里的图像识别的项目

38、来问我现在在做什么项目，然后我说OCR然后介绍了一下

40、项目经历详细介绍：两种预测方式区别，pair的预测方式整体项目有哪些可以提升的，遇到的困难之类的整个项目用了哪些库？

41、看过的论攵讨论论文

44、英特尔实习：项目介绍：台球识别和分类使用的方法，Hough 变换原理、后处理

45、Kaggle 比赛：背景介绍数据清洗、数据增强、类别岼衡，最终成绩与前几名差距在哪，有没有尝试集成的方法

46、GAN 小论文：做了什么，最终效果

47、GAN 小论文做了哪些工作，详细公式推一丅对 GAN 的具体应用有了解吗？

  1. 简历上项目为何适用xgboost和lr对比其他分类算法的场景优势。

49、GAN小论文你做了什么，有哪些改进在哪些数据集上做过实验，分辨率是多少

50、英特尔实习：1）项目背景。台球检测和分类方法球杆检测方法，球杆遮挡问题怎么处理不用分类器，直接分割或计算图像差值会怎样

51、有什么问题想了解一下

3.你有什么跟别人不一样的？

6.搞技术的你怎么很能说啊

9.如果你面试失败，你會怎么办

10.菜鸟跟你相关的部门？

14.如果你的岗位有冲突你会怎么处理？

15.实习时间具体什么时候可以开始？

16.你有什么想问的吗

17、有没囿男朋友呀，意向地点是哪

18、对公司有哪些了解

19、兴趣爱好、意向地点

20、hr面就是常见的问题，城市啊薪资待遇啊，对部门的评价对總监的评价

  1. 自我评价优缺点，怎么改进

22、hr抠了简历细节问了笔试试卷相关的问题（为什么工科生要选择做文案卷，笔试题目印象比较深嘚是什么等等）还有自己的职业规划等

24、考研还是保研为什么考到这个学校

25、研究生期间最大的改变是什么

27、讨论下工作地点和期望薪資

28、你三年的职业规划是什么？

29、你和周围的人比你的优势在哪举个例子

30、考研的还是保研的？为什么没有保研

31、家庭成员？家里人對你的工作地点有要求吗

32、平时喜欢运动吗？

35、平时刷题吗你刷过最有意思的题是啥，说一哈

36、我看你之前还做过销售聊一下

37、hr面:確定并不是二面说的转岗，而是去做数据挖掘

1、开放题:预测一位学生期末是否挂科需要挖掘哪些信息。

1、如果有同学要学机器学习你會建议他们从哪里做起

2、个人发展，以及对自己项目的深入思考还有深度学习的发展之类的。

3、讲很多关于深度学习以及机器学习的具體应用与实现也谈到了自己在实际工作中遇到的困难。

4、之后面试官问了些我对人工智能的看法以及相关竞赛的情况

6、为什么选择做語音方向？

7、为什么选择实习而不是在学校做研究？

　　找工作时（IT行业）除了常見的软件开发以外，机器学习岗位也能够当作是一个选择不少计算机方向的研究生都会接触这个，假设你的研究方向是机器学习/数据挖掘之类且又对其非常感兴趣的话，能够考虑考虑该岗位毕竟在机器智能没达到人类水平之前，机器学习能够作为一种重要手段而随著科技的不断发展，相信这方面的人才需求也会越来越大

　　纵观IT行业的招聘岗位。机器学习之类的岗位还是挺少的国内大点的公司裏百度，阿里腾讯。网易搜狐。华为（华为的岗位基本都是随机分配机器学习等岗位基本面向的是博士）等会有相关职位。另外一些国内的中小型企业和外企也会招一小部分当然了，当中大部分还是百度北京要人最多上百人。

阿里的算法岗位非常大一部分也是搞機器学习相关的另外本人有幸签约了网易杭州研究院的深度学习算法岗位，打算从事机器学习领域至少5年

非常感谢小易收留了我。

　　以下是本人在找机器学习岗位工作时总结的常见机器学习算法（主要是一些常规分类器）大概流程和主要思想，希望对大家找机器学習岗位时有点帮助实际上在面试过程中，懂这些算法的基本思想和大概流程是远远不够的那些面试官往往问的都是一些公司内部业务Φ的课题，往往要求你不仅要懂得这些算法的理论过程并且要非常熟悉如何使用它，什么场合用它算法的优缺点。以及调參经验等等说白了，就是既要会点理论也要会点应用。既要有点深度也要有点广度。否则运气不好的话非常easy就被刷掉由于每一个面试官爱好鈈同。

　　有以下几个地方须要注意：

　　1. 假设给出的特征向量长度可能不同这是须要归一化为通长度的向量（这里以文本分类为例），比方说是句子单词的话则长度为整个词汇量的长度。相应位置是该单词出现的次数

　　2. 计算公式例如以下：

　　当中一项条件概率能够通过朴素贝叶斯条件独立展开。要注意一点就是 的计算方法而由朴素贝叶斯的前提假设可知， = 因此一般有两种，一种是在类别为ci嘚那些样本集中找到wj出现次数的总和，然后除以该样本的总和；另外一种方法是类别为ci的那些样本集中找到wj出现次数的总和，然后除鉯该样本中全部特征出现次数的总和

　　3. 假设 中的某一项为0，则其联合概率的乘积也可能为0即2中公式的分子为0，为了避免这种现象出現普通情况下会将这一项初始化为1。当然为了保证概率相等分母应相应初始化为2（这里由于是2类，所以加2假设是k类就须要加k，术语仩叫做laplace光滑, 分母加k的原因是使之满足全概率公式）

　　朴素贝叶斯的长处：

　　对小规模的数据表现非常好。适合多分类任务适合增量式训练。

　　对输入数据的表达形式非常敏感

　　决策树中非常重要的一点就是选择一个属性进行分枝，因此要注意一下信息增益的計算公式并深入理解它。

　　信息熵的计算公式例如以下:

　　当中的n代表有n个分类类别（比方假设是2类问题那么n=2）。分别计算这2类样夲在总样本中出现的概率p1和p2这样就能够计算出未选中属性分枝前的信息熵。

　　如今选中一个属性xi用来进行分枝此时分枝规则是：假設xi=vx的话，将样本分到树的一个分支假设不相等则进入还有一个分支。非常显然分支中的样本非常有可能包括2个类别。分别计算这2个分支的熵H1和H2,计算出分枝后的总信息熵H’=p1*H1+p2*H2.则此时的信息增益ΔH=H-H’。以信息增益为原则把全部的属性都測试一边，选择一个使增益最大的属性作为本次分枝属性

　　计算量简单。可解释性强比較适合处理有缺失属性值的样本，能够处理不相关的特征；

　　easy过拟合（兴许出現了随机森林减小了过拟合现象）；

　　Logistic是用来分类的，是一种线性分类器须要注意的地方有：

　　2. logsitc回归方法主要是用最大似然预计來学习的，所以单个样本的后验概率为：

　　到整个样本的后验概率：

　　通过对数进一步化简为：

　　2、分类时计算量非常小速度非瑺快。存储资源低；

　　1、easy欠拟合一般精确度不太高

　　2、仅仅能处理两分类问题（在此基础上衍生出来的softmax能够用于多分类）。且必须線性可分

　　线性回归才是真正用于回归的，而不像logistic回归是用于分类其基本思想是用梯度下降法对最小二乘法形式的误差函数进行优囮，当然也能够用normal equation直接求得參数的解结果为：

　　而在LWLR（局部加权线性回归）中，參数的计算表达式为:

　　由于此时优化的是：

　　由此可见LWLR与LR不同LWLR是一个非參数模型，由于每次进行回归计算都要遍历训练样本至少一次

　　实现简单，计算简单；

　　不能拟合非线性數据；

　　KNN即近期邻算法其主要过程为：

　　1. 计算训练样本和測试样本中每一个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；

　　2. 对上面全部的距离值进行排序；

　　3. 选前k个最小距离的样本

　　4. 依据这k个样本的标签进行投票。得到最后的分类类别

　　洳何选择一个最佳的K值，这取决于数据普通情况下。在分类时较大的K值能够减小噪声的影响但会使类别之间的界限变得模糊。一个较恏的K值可通过各种启示式技术来获取比方，交叉验证另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。

　　近邻算法具有较强的一致性结果随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率

　　注：马氏距离一定要先给出样本集的统计性质，比方均值向量协方差矩阵等。关于马氏距离的介绍例如以丅：

　　KNN算法的长处：

　　1. 思想简单理论成熟，既能够用来做分类也能够用来做回归；

　　2. 可用于非线性分类；

　　3. 训练时间复杂度为O(n)；

　　4. 精确度高对数据没有假设，对outlier不敏感

　　2. 样本不平衡问题（即有些类别的样本数量非常多。而其他样本的数量非常少）；

　　3. 須要大量的内存

　　要学会如何使用libsvm以及一些參数的调节经验，另外须要理清楚svm算法及实现的一些思路：

　　1. svm中的最优分类面是对全部樣本的几何裕量最大（为什么要选择最大间隔分类器请从数学角度上说明？网易深度学习岗位面试过程中有被问到答案就是几何间隔與样本的误分次数间存在关系： ，当中的分母就是样本到分类间隔距离分子中的R是全部样本中的最长向量值），即：

　　经过一系列推導可得为优化以下原始目标：

　　2. 以下来看看拉格朗日理论：

　　能够将1中的优化目标转换为拉格朗日的形式（通过各种对偶优化KKD条件），最后目标函数为：

　　我们仅仅须要最小化上述目标函数当中的α为原始优化问题中的不等式约束拉格朗日系数。

　　3. 对2中最后的式子分别w和b求导可得：

　　由上面第1式子能够知道，假设我们优化出了α，则直接能够求出w了即模型的參数搞定。而上面第2个式子能够莋为兴许优化的一个约束条件

　　4. 对2中最后一个目标函数用对偶优化理论能够转换为优化以下的目标函数：

　　而这个函数能够用经常使用的优化方法求得α。进而求得w和b。

　　5. 依照道理svm简单理论应该到此结束。只是还是要补充一点即在预測时有：

　　那个尖括号我們能够用核函数取代，这也是svm经常和核函数扯在一起的原因

　　6. 最后是关于松弛变量的引入，因此原始的目标优化公式为：

　　此时相應的对偶优化公式为：

　　与前面的相比仅仅是α多了个上界。

　　可用于线性/非线性分类也能够用于回归；

　　对參数和核函数的选擇比較敏感；

　　原始的SVM仅仅比較擅好处理二分类问题；

　　主要以Adaboost为例。首先来看看Adaboost的流程图例如以下：

　　从图中能够看到，在训練过程中我们须要训练出多个弱分类器（图中为3个）每一个弱分类器是由不同权重的样本（图中为5个训练样本）训练得到（当中第一个弱分类器相应输入样本的权值是一样的），而每一个弱分类器对终于分类结果的作用也不同是通过加权平均输出的，权值见上图中三角形里面的数值那么这些弱分类器和其相应的权值是如何训练出来的呢？

　　以下通过一个样例来简单说明

　　书中（machine learning in action）假设的是5个训練样本，每一个训练样本的维度为2在训练第一个分类器时5个样本的权重各为0.2. 注意这里样本的权值和终于训练的弱分类器组相应的权值α是不同的。样本的权重仅仅在训练过程中用到，而α在训练过程和測试过程都实用到。

　　如今假设弱分类器是带一个节点的简单决策树該决策树会选择2个属性（假设仅仅有2个属性）的一个，然后计算出这个属性中的最佳值用来分类

　　Adaboost的简单版本号训练步骤例如以下：

　　1. 训练第一个分类器。样本的权值D为同样的均值通过一个弱分类器。得到这5个样本（请相应书中的样例来看依然是machine learning in action）的分类预測标簽。

与给出的样本真实标签对照就可能出现误差(即错误)。

假设某个样本预測错误则它相应的错误值为该样本的权重，假设分类正确則错误值为0. 最后累加5个样本的错误率之和，记为ε。

　　2. 通过ε来计算该弱分类器的权重α，公式例如以下：

　　3. 通过α来计算训练下一个弱分类器样本的权重D假设相应样本分类正确，则减小该样本的权重公式为：

　　假设样本分类错误，则增加该样本的权重公式为：

　　4. 循环步骤1,2,3来继续训练多个分类器，仅仅是其D值不同而已

　　測试步骤例如以下：

　　输入一个样本到训练好的每一个弱分类中。則每一个弱分类都相应一个输出标签然后该标签乘以相应的α，最后求和得到值的符号即为预測标签值。

　　easy实现。分类准确率较高沒有太多參数能够调；

　　对outlier比較敏感。

　　依据聚类思想划分：

　　1. 基于划分的聚类:

　　k-means是使以下的表达式值最小：

　　（1）k-means算法是解決聚类问题的一种经典算法算法简单、高速。

　　（2）对处理大数据集该算法是相对可伸缩的和高效率的。由于它的复杂度大约是O(nkt)當中n是全部对象的数目，k是簇的数目,t是迭代的次数通常k<<n。这个算法通常局部收敛

　　（3）算法尝试找出使平方误差函数值最小的k个划汾。

当簇是密集的、球状或团状的且簇与簇之间区别明显时，聚类效果较好

　　（1）k-平均方法仅仅有在簇的平均值被定义的情况下才幹使用。且对有些分类属性的数据不适合

　　（2）要求用户必须事先给出要生成的簇的数目k。

　　（3）对初值敏感对于不同的初始值，可能会导致不同的聚类结果

　　（4）不适合于发现非凸面形状的簇，或者大小区别非常大的簇

　　（5）对于"噪声"和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响

　　2. 基于层次的聚类：

　　自底向上的凝聚方法，比方AGNES

　　自上向下的分裂方法，比方DIANA

　　3. 基于密度的聚类：

　　4. 基于网格的方法：

　　5. 基于模型的聚类：

　　以上这些算法的简单介绍可參考

　　推荐系统的实现主要分为兩个方面：基于内容的实现和协同滤波的实现。

　　不同人对不同电影的评分这个样例能够看做是一个普通的回归问题，因此每部电影嘟须要提前提取出一个特征向量(即x值)然后针对每一个用户建模，即每一个用户打的分值作为y值利用这些已有的分值y和电影特征值x就能夠训练回归模型了(最常见的就是线性回归)。这样就能够预測那些用户没有评分的电影的分数

（值得注意的是需对每一个用户都建立他自巳的回归模型）

　　从还有一个角度来看。也能够是先给定每一个用户对某种电影的喜好程度（即权值）然后学出每部电影的特征，最後採用回归来预測那些没有被评分的电影

　　当然还能够是同一时候优化得到每一个用户对不同类型电影的热爱程度以及每部电影的特征。详细能够參考Ng在coursera上的ml教程：

　　基于协同滤波的实现：

　　协同滤波（CF）能够看做是一个分类问题也能够看做是矩阵分解问题。协哃滤波主要是基于每一个人自己的喜好都类似这一特征它不依赖于个人的基本信息。

比方刚刚那个电影评分的样例中预測那些没有被評分的电影的分数仅仅依赖于已经打分的那些分数，并不须要去学习那些电影的特征

　　SVD将矩阵分解为三个矩阵的乘积，公式例如以下所看到的：

　　中间的矩阵sigma为对角矩阵对角元素的值为Data矩阵的神秘值(注意神秘值和特征值是不同的)，且已经从大到小排列好了即使去掉特征值小的那些特征，依然能够非常好的重构出原始矩阵例如以下图所看到的：

　　当中更深的颜色代表去掉小特征值重构时的三个矩阵。

　　果m代表商品的个数n代表用户的个数，则U矩阵的每一行代表商品的属性如今通过降维U矩阵（取深色部分）后，每一个商品的屬性能够用更低的维度表示（假设为k维）这样当新来一个用户的商品推荐向量X，则能够依据公式X'*U1*inv(S1)得到一个k维的向量然后在V’中寻找最類似的那一个用户（类似度測量可用余弦公式等），依据这个用户的评分来推荐（主要是推荐新用户未打分的那些商品）详细样例能够參考网页：。

　　另外关于SVD分解后每一个矩阵的实际含义能够參考google吴军的《数学之美》一书（只是个人感觉吴军解释UV两个矩阵时好像弄反叻不知道大家如何觉得）。或者參考machine learning in action当中的svd章节

　　pLSA由LSA发展过来，而早期LSA的实现主要是通过SVD分解pLSA的模型图例如以下：

　　公式中的意义例如以下：

　　主题模型。概率图例如以下：

　　和pLSA不同的是LDA中假设了非常多先验分布且一般參数的先验分布都假设为Dirichlet分布，其原洇是共轭分布时先验概率和后验概率的形式同样

它在被提出之初就和SVM一起被觉得是泛化能力（generalization)较强的算法。近些年更由于被用于搜索排序的机器学习模型而引起大家关注

　　GBDT是回归树。不是分类树其核心就在于，每一棵树是从之前全部树的残差中来学习的

为了防止過拟合。和Adaboosting一样也增加了boosting这一项。

　　关于GDBT的介绍能够能够參考：

　　作用是（网易电话面试时有问到）：

　　1. 数值上更easy求解。

　　2. 特征数目太大时更稳定；

　　3. 控制模型的复杂度光滑性。复杂性越小且越光滑的目标函数泛化能力越强

而增加规则项能使目标函数复雜度减小，且更光滑

　　4. 减小參数空间；參数空间越小，复杂度越低

　　5. 系数越小，模型越简单而模型越简单则泛化能力越强（Ng宏觀上给出的解释）。

　　6. 能够看成是权值的高斯先验

　　能够预计样本的密度函数，对于新样本直接计算其密度假设密度值小于某一閾值，则表示该样本异常而密度函数一般採用多维的高斯分布。假设样本有n维则每一维的特征都能够看作是符合高斯分布的，即使这些特征可视化出来不太符合高斯分布也能够对该特征进行数学转换让其看起来像高斯分布。比方说x=log(x+c), x=x^(1/c)等

异常检測的算法流程例如以下：

 　　当中的ε也是通过交叉验证得到的，也就是说在进行异常检測时，前面的p(x)的学习是用的无监督后面的參数ε学习是用的有监督。那么为什么不全部使用普通有监督的方法来学习呢（即把它看做是一个普通的二分类问题）？主要是由于在异常检測中异常的样本数量非常少洏正常样本数量非常多，因此不足以学习到好的异常行为模型的參数由于后面新来的异常样本可能全然是与训练样本中的模式不同。

　　另外上面是将特征的每一维看成是相互独立的高斯分布，事实上这种近似并非最好的可是它的计算量较小。因此也常被使用更好嘚方法应该是将特征拟合成多维高斯分布，这时有特征之间的相关性但随之计算量会变复杂，且样本的协方差矩阵还可能出现不可逆的凊况（主要在样本数比特征数小或者样本特征维数之间有线性关系时）。

　　上面的内容能够參考Ng的

　　有时候由于样本的产生和隐含變量有关（隐含变量是不能观察的）而求模型的參数时一般採用最大似然预计，由于含有了隐含变量所以对似然函数參数求导是求不絀来的，这时能够採用EM算法来求模型的參数的（相应模型參数个数可能有多个）EM算法一般分为2步：

　　E步：选取一组參数，求出在该參數下隐含变量的条件概率值；

　　M步：结合E步求出的隐含变量条件概率求出似然函数下界函数（本质上是某个期望函数）的最大值。

　　反复上面2步直至收敛

　　公式例如以下所看到的：

　　M步公式中下界函数的推导过程：

　　EM算法一个常见的样例就是GMM模型。每一个样夲都有可能由k个高斯产生仅仅只是由每一个高斯产生的概率不同而已。因此每一个样本都有相应的高斯分布（k个中的某一个）此时的隱含变量就是每一个样本相应的某个高斯分布。

　　GMM的E步公式例如以下（计算每一个样本相应每一个高斯的概率）：

　　更详细的计算公式为：

　　M步公式例如以下（计算每一个高斯的比重均值。方差这3个參数）：

　　关于EM算法能够參考 或者网易公开课：

　　Apriori是关联分析中比較早的一种方法，主要用来挖掘那些频繁项集合

　　1. 假设一个项目集合不是频繁集合，那么不论什么包括它的项目集合也一定不昰频繁集合；

　　2. 假设一个项目集合是频繁集合那么它的不论什么非空子集也是频繁集合。

　　Aprioir须要扫描项目表多遍从一个项目開始掃描。舍去掉那些不是频繁的项目得到的集合称为L，然后对L中的每一个元素进行自组合生成比上次扫描多一个项目的集合，该集合称為C接着又扫描去掉那些非频繁的项目，反复…

　　假设每一个步骤不去掉非频繁项目集则其扫描过程的树形结构例如以下：

　　在当Φ某个过程中，可能出现非频繁的项目集将其去掉（用阴影表示）为：

　　FP Growth是一种比Apriori更高效的频繁项挖掘方法。它仅仅须要扫描项目表2佽当中第1次扫描获得当个项目的频率，去掉不符合支持度要求的项并对剩下的项排序。第2遍扫描是建立一颗FP-Tree(frequent-patten tree)

　　接下来的工作就是茬FP-Tree上进行挖掘。

　　它所相应的FP_Tree例如以下：

　　然后从频率最小的单项P開始找出P的条件模式基。用构造FP_Tree同样的方法来构造P的条件模式基嘚FP_Tree在这棵树上找出包括P的频繁项集。

　　依次从m,b,a,c,f的条件模式基上挖掘频繁项集有些项须要递归的去挖掘，比較麻烦比方m节点，详细嘚过程能够參考博客：里面讲得非常详细。

我要回帖

更多关于 svm算法 的文章

 

随机推荐