机器学习常见的算法面试题总结

参考:https://bbs.aliyun.com/read.php?spm=5176.100258.100258.9.8icSkL&tid=294564&displayMode=1&page=1&toread=1#tpc朴素贝叶斯P(A∩B)=P(A)*P(B|A)=P(B)*P(A|B)所以有:P(A|B)=P(B|A)*P(A)/P(B)对于给出的待分类项,求

参考:https://bbs.aliyun.com/read.php?spm=5176.100258.100258.9.8icSkL&tid=294564&displayMode=1&page=1&toread=1#tpc

朴素贝叶斯



P(A∩B)=P(A)*P(B|A)=P(B)*P(A|B)
所以有:P(A|B)=P(B|A)*P(A)/P(B)
对于给出的待分类项,求解在此项出现的条件下各个目标类别出现的概率,哪个最大,就认为此待分类项属于哪个类别

工作原理
  1. 假设现在有样本x=(a1,a2,a3,…an)这个待分类项(并认为x里面的特征独立)
  2. 再假设现在有分类目标Y={y1,y2,y3,y4..yn}
  3. 那么max(P(y1|x),P(y2|x),P(y3|x)..P(yn|x))中的最大者就是最终的分类类别
  4. 而P(yi|x)=p(x|yi)*P(yi)/P(x)
  5. 因为x对于每个分类目标来说都一样,所以就是求max(P(x|yi)*p(yi))
  6. P(x|yi)*p(yi)=p(yi)*PI(P(ai|yi)) (PI表示连乘)
  7. 而具体的p(ai|yi)和p(yi)都是能从训练样本中统计出来
    p(ai|yi)表示该类别下该特征出现的概率
    p(yi)表示全部类别中这个这个类别出现的概率
  8. 好的,就是这么工作的^_^


工作流程
  1. 准备阶段
    确定特征属性,并对每个特征属性进行适当划分,然后由人工对一部分待分类项进行分类,形成训练样本。
  2. 训练阶段
    计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计
  3. 应用阶段
    使用分类器进行分类,输入是分类器和待分类样本,输出是样本属于的分类类别


属性特征
  1. 特征为离散值时直接统计即可(表示统计概率)
  2. 特征为连续值的时候假定特征符合高斯分布:g(x,n,u)
    那么p(ak|yi)=g(xk,ni,ui)


Laplace校准(拉普拉斯校验)
当某个类别下某个特征划分没有出现时,会有P(a|y)=0,就是导致分类器质量降低,所以此时引入Laplace校验,就是对没类别下所有划分的计数加1。

遇到特征之间不独立问题
参考改进的贝叶斯网络,使用DAG来进行概率图的描述

优缺点
朴素贝叶斯的优点:
  1. 对小规模的数据表现很好,适合多分类任务,适合增量式训练。
    缺点:
  2. 对输入数据的表达形式很敏感(离散、连续,值极大极小之类的)。

http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html



逻辑回归和线性回归


LR回归是一个线性的二分类模型,主要是计算在某个样本特征下事件发生的概率,比如根据用户的浏览购买情况作为特征来计算它是否会购买这个商品,抑或是它是否会点击这个商品。然后LR的最终值是根据一个线性和函数再通过一个sigmod函数来求得,这个线性和函数权重与特征值的累加以及加上偏置求出来的,所以在训练LR时也就是在训练线性和函数的各个权重值w。

关于这个权重值w一般使用最大似然法来估计,比如yi=1的概率是pi,则yi=0的概率是1-pi,那么观测概率为p(yi)=pi^yi*(1-pi)^(1-yi)这个这个最大似然函数为(hw(xi)^yi*(1-hw(xi))^(1-yi))连乘,对这个似然函数取对数之后就会得到的表达式L(w)=sigma(yi*log(hw(xi))-(1-yi)log(1-hw(xi)))=sigma(yi*(w*xi)-log(1+exp(w*xi))),估计这个L(w)的极大值就可以得到w的估计值。
所以求解问题就变成了这个最大似然函数的最优化问题,这里通常会采样随机梯度下降法和拟牛顿迭代法来进行优化


梯度下降法
如果hw(x)=1/(1-e^(-wx)),
则cost function=-1/m* sigma(yi*log(hw(xi)+(1-yi)*log(1-hw(xi)))=j(w)
这里就成了就min(j(w))
所以更新w的过程为
w:=w-lamea*j(w)’ (求导)
w:=w-lamea* 1/m\*sigma[m](hw(xi)-yi)*xi)
直到j(w)不能再的时候停止
梯度下降法的最大问题就是会陷入局部最优,并且每次在对当前样本计算cost的时候都需要去遍历全部样本才能得到cost值,这样计算速度就会慢很多(虽然在计算的时候可以转为矩阵乘法去更新整个w值)
所以现在好多框架(mahout)中一般使用随机梯度下降法,它在计算cost的时候只计算当前的代价,最终cost是在全部样本迭代一遍之求和得出,还有他在更新当前的参数w的时候并不是依次遍历样本,而是从所有的样本中随机选择一条进行计算,它方法收敛速度快(一般是使用最大迭代次数),并且还可以避免局部最优,并且还很容易并行(使用参数服务的方式进行并行)
这里SGD可以改进的地方就是使用动态的梯度值alpha=0.04*(1.0+n+i)+Rate

其他优化方法
  • 拟牛顿法(记得是需要使用Hessian矩阵和cholesky分解)
  • BFGS
  • L-BFGS
优缺点:无需选择学习率α,更快,但是更复杂


关于LR的过拟合问题:
如果我们有很多的特性,在训练集上拟合得很好,但是在预测集上却达不到这种效果
  • 1. 减少feature个数(人工定义留多少个feature、算法选取这些feature)
  • 2. 正则化(留下所有的feature,但对于部分feature定义其parameter非常小),在cost上加 lamea(sigma(w^2)),同时w的更新变为w:=w-rate* 1/m\*sigma[m](hw(xi)-yi)*xi+ (lamea/m)*w。注意:这里的w0不受正则化影响


关于LR的多分类:softmax
softmax:假设离散型随机变量Y的取值集合是{1,2,..,k},则多分类的LR为
P(Y=a|x)=exp(wa*x)/(1-1到k求和(wk*x)) 1<a<k
这里会输出当前样本下属于哪一类的概率,并且满足全部概率加起来=1

关于softmax和k个LR的选择
如果类别之间是否互斥(比如音乐只能属于古典音乐、乡村音乐、摇滚月的一种)就用softmax
否则类别之前有联系(比如一首歌曲可能有影视原声,也可能包含人声,或者是舞曲),这个时候使用k个LR更为合适

优缺点:
Logistic回归优点:
  1. 实现简单;
  2. 分类时计算量非常小,速度很快,存储资源低;

缺点:
  1. 容易欠拟合,一般准确度不太高
  2. 只能处理两分类问题(在此基础上衍生出来的softmax可以用于多分类),且必须线性可分;

http://www.cnblogs.com/biyeymyhjob/archive/2012/07/18/2595410.html
http://blog.csdn.net/abcjennifer/article/details/7716281
http://ufldl.stanford.edu/wiki/index.php/Softmax%E5%9B%9E%E5%BD%92




KNN算法        

给一个训练数据集和一个新的实例,在训练数据集中找出与这个新实例最近的k个训练实例,然后统计最近的k个训练实例中所属类别计数最多的那个类,就是新实例的类

三要素:

  1. k值的选择
  2. 距离的度量(常见的距离度量有欧式距离,马氏距离等)
  3. 分类决策规则 (多数表决规则)


k值的选择

  1. k值越小表明模型越复杂,更加容易过拟合
  2. 但是k值越大,模型越简单,如果k=N的时候就表明无论什么点都是训练集中类别最多的那个类

所以一般k会取一个较小的值,然后用过交叉验证来确定
这里所谓的交叉验证就是将样本划分一部分出来为预测样本,比如95%训练,5%预测,然后k分别取1,2,3,4,5之类的,进行预测,计算最后的分类误差,选择误差最小的k


KNN的回归


在找到最近的k个实例之后,可以计算这k个实例的平均值作为预测值。或者还可以给这k个实例添加一个权重再求平均值,这个权重与度量距离成反比(越近权重越大)。

优缺点:


KNN算法的优点:
  1. 思想简单,理论成熟,既可以用来做分类也可以用来做回归;
  2. 可用于非线性分类;
  3. 训练时间复杂度为O(n);
  4. 准确度高,对数据没有假设,对outlier不敏感;

缺点:
  1. 计算量大;
  2. 样本不平衡问题(即有些类别的样本数量很多,而其它样本的数量很少);
  3. 需要大量的内存;


KD树


KD树是一个二叉树,表示对K维空间的一个划分,可以进行快速检索(那KNN计算的时候不需要对全样本进行距离的计算了)

构造KD树


在k维的空间上循环找子区域的中位数进行划分的过程。
假设现在有K维空间的数据集T={x1,x2,x3,…xn},xi={a1,a2,a3..ak}
  1. 首先构造根节点,以坐标a1的中位数b为切分点,将根结点对应的矩形局域划分为两个区域,区域1中a1b
  2. 构造叶子节点,分别以上面两个区域中a2的中位数作为切分点,再次将他们两两划分,作为深度1的叶子节点,(如果a2=中位数,则a2的实例落在切分面)
  3. 不断重复2的操作,深度为j的叶子节点划分的时候,索取的ai 的i=j%k+1,直到两个子区域没有实例时停止


KD树的搜索

  1. 首先从根节点开始递归往下找到包含x的叶子节点,每一层都是找对应的xi
  2. 将这个叶子节点认为是当前的“近似最近点”
  3. 递归向上回退,如果以x圆心,以“近似最近点”为半径的球与根节点的另一半子区域边界相交,则说明另一半子区域中存在与x更近的点,则进入另一个子区域中查找该点并且更新”近似最近点“
  4. 重复3的步骤,直到另一子区域与球体不相交或者退回根节点
  5. 最后更新的”近似最近点“与x真正的最近点


KD树进行KNN查找


通过KD树的搜索找到与搜索目标最近的点,这样KNN的搜索就可以被限制在空间的局部区域上了,可以大大增加效率。

KD树搜索的复杂度


当实例随机分布的时候,搜索的复杂度为log(N),N为实例的个数,KD树更加适用于实例数量远大于空间维度的KNN搜索,如果实例的空间维度与实例个数差不多时,它的效率基于等于线性扫描。



SVM、SMO


对于样本点(xi,yi)以及svm的超平面:wix+b=0
  • 函数间隔:yi(wxi+b)
  • 几何间隔:yi(wxi+b)/||w||,其中||w||为w的L2范数,几何间隔不会因为参数比例的改变而改变

svm的基本想法就是求解能正确划分训练样本并且其几何间隔最大化的超平面。


线性SVM问题


yi(wxi+b)/||w||>=d (使用几何间隔)
求max(d)
那么假设d’=d||w||
则将问题转为:yi(wxi+b)>=1,max(d’/||w||)
由于d’的成比例增减不会影响实际间距,所以这里的取d’=1,又因为max(1/||w||)=min(1/2\||w||^2)
所以最终的问题就变为了
yi(wxi+b)>=1,min(1/2*||w||^2)
这样就变成了一个凸的二次规划化,可以将其转换为拉格朗日函数,然后使用对偶算法来求解

对偶求解


L(w,b,a)=1/2*||w||^2-sigma(ai*yi(wxi+b))+sigma(ai) 其中a={a1,a2..an}为拉格朗日向量
根据对偶性质 原始问题就是求对偶问题的极大极小max[a]min[w,b]L(w,b,a)
先求L对w,b的极小,再求对a的极大
求min[w,b]L(w,b,a):
L’(w)=w-sigma(aiyixi)=0
L’(b)=sigma(aiyi)=0;
代入后可得min[w,b]L(w,b,a)=-1/2*sigma(sigma(aiajyiyj(xi·xj)))+sigma(ai)
求min[w,b]L(w,b,a)对a的极大
max[a] -1/2*sigma(sigma(aiajyiyj(xi·xj)))+sigma(ai)
sigma(aiyi)=0
转成等价的对偶形式就是
min[a] 1/2*sigma(sigma(aiajyiyj(xi·xj)))-sigma(ai)
sigma(aiyi)=0
假如求解出来的a为a^=(a1,a2,…an)
则得到最优的w,b分别为
w^=sigma(aiyixi)
b^=yj-sigma(aiyi(xi·xj))
所以,最终的决策分类面为
f=sign(sigma(aiyi(x·xi))+b^
也就是说,分类决策函数只依赖于输入x与训练样本的输入的内积

与分离超平面最近的样本点称为支持向量


损失函数


经验损失函数:sigma(1-yi(wxi+b)) (注意,如果该值小于0时直接取0即可)
合页损失函数:sigma(1-yi(wi+b)) + leama||w||^2 后面的是L2正则项

为什么要引入对偶算法

  1. 对偶问题往往更加容易求解(结合拉格朗日和kkt条件)
  2. 可以很然的引用核函数(拉格朗日表达式里面有内积,而核函数也是通过内积进行映射的)


核函数


将输入特征x(线性不可分)映射到高维特征R空间,可以在R空间上让SVM进行线性可以变,这就是核函数的作用
  • 多项式核函数:K(x,z)=(x*z+1)^p
  • 高斯核函数:K(x,z)=exp(-(x-z)^2/a^2) a为均值
  • 字符串核函数:好像用于文本匹配、检索之类的,不懂


SVM优缺点


优点:
  1. 使用核函数可以向高维空间进行映射
  2. 使用核函数可以解决非线性的分类
  3. 分类思想很简单,就是将样本与决策面的间隔最大化
  4. 分类效果较好

缺点:
  1. 对大规模数据训练比较困难,因为它是用二次规划来求解的
  2. 无法直接支持多分类,但是可以使用间接的方法来做


SMO


SMO是用于快速求解SVM的
它选择凸二次规划的两个变量,其他的变量保持不变,然后根据这两个变量构建一个二次规划问题,这个二次规划关于这两个变量解会更加的接近原始二次规划的解,通过这样的子问题划分可以大大增加整个算法的计算速度,关于这两个变量:
  1. 其中一个是严重违反KKT条件的一个变量
  2. 另一个变量是根据自由约束确定,好像是求剩余变量的最大化来确定的。


SVM多分类问题

  1. 直接法
    直接在目标函数上进行修改,将多个分类面的参数求解合并到一个最优化问题中,通过求解该优化就可以实现多分类(计算复杂度很高,实现起来较为困难)
  2. 间接法一对多
    其中某个类为一类,其余n-1个类为另一个类,比如A,B,C,D四个类,第一次A为一个类,{B,C,D}为一个类训练一个分类器,第二次B为一个类,{A,C,D}为另一个类,按这方式共需要训练4个分类器,最后在测试的时候将测试样本经过这4个分类器f1(x),f2(x),f3(x)和f4(x),取其最大值为分类器(这种方式由于是1对M分类,会存在偏置,很不实用)
  3. 一对一(libsvm实现的方式)
    任意两个类都训练一个分类器,那么n个类就需要n*(n-1)/2个svm分类器。
    还是以A,B,C,D为例,那么需要{A,B},{A,C},{A,D},{B,C},{B,D},{C,D}为目标共6个分类器,然后在预测的将测试样本通过这6个分类器之后进行投票选择最终结果。(这种方法虽好,但是需要n*(n-1)/2个分类器代价太大,不过有好像使用循环图来进行改进)


决策树

决策树是一颗依托决策而建立起来的树。

ID3

  1. 首先是针对当前的集合,计算每个特征的信息增益
  2. 然后选择信息增益最大的特征作为当前节点的决策决策特征
  3. 根据特征不同的类别划分到不同的子节点(比如年龄特征有青年,中年,老年,则划分到3颗子树)
  4. 然后继续对子节点进行递归,直到所有特征都被划分

S(C,ai)=-sigma(pilog(pi)) 一个属性中某个类别的熵 pi=P(yi|ai) pi表示ai情况下发生yi的概率,也即是统计概率
S(C,A)=sigma(P(A=ai)\S(ai)) 整个属性的熵,为各个类别的比例与各自熵的加权求和
Gain(C,A)=S(C)-S(C,A) 增益表示分类目标的熵减去当前属性的熵,增益越大,分类能力越强
(这里前者叫做经验熵,表示数据集分类C的不确定性,后者就是经验条件熵,表示在给定A的条件下对数据集分类C的不确定性,两者相减叫做互信息,决策树的增益等价于互信息)
比如说当前属性是是否拥有房产,分类是是否能偿还债务
现在:
  • 有用房产为7个,4个能偿还债务,3个无法偿还债务
  • 然后无房产为3个,其中1个能偿还债务,2个无法偿还债务

然后S(有房产)=-(4/7*log4/7+3/7*log3/7)
S(无房产)=-(1/3*log1/3+2/3*log2/3)
其中S(分类)=-(5/10*log5/10+5/10*log5/10)
最终的增益=S(分类)-(7/10*S(有房产)+3/10*S(无房产)) 最大越好
关于损失函数
设树的叶子节点个数为T,t为其中一个叶子节点,该叶子节点有Nt个样本,其中k类的样本有Ntk个,H(t)为叶子节点上的经验熵,则损失函数定义为
Ct(T)=sigma(Nt*H(t))+ lamdba |T|
其中H(t)=sigma(Ntk/Nt*log(Ntk/Nt))
代入可以得到Ct(T)=sigma(sigma(Ntk*log(Ntk/Nt)))+lamdba|T|
最终有Ct(T)=C(T)+ lamdba|T|
lamdba|T|为正则化项,leama是用于调节比率
决策树的生成只考虑了信息增益

C4.5


  • 发表于 2019-11-26 09:43
  • 阅读 ( 15 )
  • 分类:机器学习

0 条评论

请先 登录 后评论
不写代码的码农
xbmatrix _csdn

0 篇文章

作家榜 »

  1. AI君 10 文章
  2. Tzung-Wen Liau 0 文章
  3. blairan 0 文章
  4. rookie 0 文章
  5. 陈凯 0 文章
  6. huanxue 0 文章
  7. admin 0 文章
  8. Lzs1998_csdn 0 文章