机器学习常见的算法面试题总结_深圳光环大数据人工智能培训

光环大数据--大数据培训&人工智能培训机器学习常见的算法面试题总结_深圳光环大数据人工智能培训朴素贝叶斯P(A∩B)=P(A)*P(B|A)=P(B)*P(A|B)所以有：P(A|B)=P(B|A)*P(A)/P(B)对于给出的待分类项，求解在此项出现的条件下各个目标类别出现的概率，哪个最大，就认为此待分类项属于哪个类别工作原理假设现在有样本x=(a1,a2,a3,„an)这个待分类项(并认为x里面的特征独立)再假设现在有分类目标Y={y1,y2,y3,y4..yn}那么max(P(y1|x),P(y2|x),P(y3|x)..P(yn|x))中的最大者就是最终的分类类别而P(yi|x)=p(x|yi)*P(yi)/P(x)因为x对于每个分类目标来说都一样，所以就是求max(P(x|yi)*p(yi))P(x|yi)*p(yi)=p(yi)*PI(P(ai|yi))(PI表示连乘)而具体的p(ai|yi)和p(yi)都是能从训练样本中统计出来p(ai|yi)表示该类别下该特征出现的概率p(yi)表示全部类别中这个这个类别出现的概率好的，就是这么工作的^_^光环大数据--大数据培训&人工智能培训工作流程准备阶段确定特征属性，并对每个特征属性进行适当划分，然后由人工对一部分待分类项进行分类，形成训练样本。训练阶段计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计应用阶段使用分类器进行分类，输入是分类器和待分类样本，输出是样本属于的分类类别属性特征特征为离散值时直接统计即可（表示统计概率）特征为连续值的时候假定特征符合高斯分布:g(x,n,u)那么p(ak|yi)=g(xk,ni,ui)Laplace校准(拉普拉斯校验)当某个类别下某个特征划分没有出现时，会有P(a|y)=0，就是导致分类器质量降低，所以此时引入Laplace校验，就是对没类别下所有划分的计数加1。遇到特征之间不独立问题参考改进的贝叶斯网络，使用DAG来进行概率图的描述光环大数据--大数据培训&人工智能培训优缺点优点：对小规模的数据表现很好，适合多分类任务，适合增量式训练。缺点：对输入数据的表达形式很敏感（离散、连续，值极大极小之类的）。逻辑回归和线性回归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))，则costfunction=-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分解）BFGSL-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的多分类：softmaxsoftmax:假设离散型随机变量Y的取值集合是{1,2,..,k},则多分类的LR为P(Y=a|x)=exp(wa*x)/(1-1到k求和(wk*x))1ak这里会输出当前样本下属于哪一类的概率，并且满足全部概率加起来=1关于softmax和k个LR的选择如果类别之间是否互斥（比如音乐只能属于古典音乐、乡村音乐、摇滚月的一种）就用softmax否则类别之前有联系（比如一首歌曲可能有影视原声，也可能包含人声，或者是舞曲），这个时候使用k个LR更为合适优缺点：Logistic回归优点：实现简单；分类时计算量非常小，速度很快，存储资源低；缺点：容易欠拟合，一般准确度不太高只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；光环大数据--大数据培训&人工智能培训算法给一个训练数据集和一个新的实例，在训练数据集中找出与这个新实例最近的k个训练实例，然后统计最近的k个训练实例中所属类别计数最多的那个类，就是新实例的类三要素：k值的选择距离的度量（常见的距离度量有欧式距离，马氏距离等）分类决策规则（多数表决规则）k值的选择k值越小表明模型越复杂，更加容易过拟合但是k值越大，模型越简单，如果k=N的时候就表明无论什么点都是训练集中类别最多的那个类所以一般k会取一个较小的值，然后用过交叉验证来确定这里所谓的交叉验证就是将样本划分一部分出来为预测样本，比如95%训练，5%预测，然后k分别取1，2，3，4，5之类的，进行预测，计算最后的分类误差，选择误差最小的kKNN的回归在找到最近的k个实例之后，可以计算这k个实例的平均值作为预测值。或者还可以给这k个实例添加一个权重再求平均值，这个权重与度量距离成反比（越近权重越大）。光环大数据--大数据培训&人工智能培训优缺点：KNN算法的优点：思想简单，理论成熟，既可以用来做分类也可以用来做回归；可用于非线性分类；训练时间复杂度为O(n)；准确度高，对数据没有假设，对outlier不敏感；缺点：计算量大；样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；需要大量的内存；KD树KD树是一个二叉树，表示对K维空间的一个划分，可以进行快速检索（那KNN计算的时候不需要对全样本进行距离的计算了）构造KD树在k维的空间上循环找子区域的中位数进行划分的过程。假设现在有K维空间的数据集T={x1,x2,x3,„xn},xi={a1,a2,a3..ak}首先构造根节点，以坐标a1的中位数b为切分点，将根结点对应的矩形局域划分为两个区域，区域1中a1b构造叶子节点，分别以上面两个区域中a2的中位数作为切分点，再次光环大数据--大数据培训&人工智能培训将他们两两划分，作为深度1的叶子节点，（如果a2=中位数，则a2的实例落在切分面）不断重复2的操作，深度为j的叶子节点划分的时候，索取的ai的i=j%k+1，直到两个子区域没有实例时停止KD树的搜索首先从根节点开始递归往下找到包含x的叶子节点，每一层都是找对应的xi将这个叶子节点认为是当前的“近似最近点”递归向上回退，如果以x圆心，以“近似最近点”为半径的球与根节点的另一半子区域边界相交，则说明另一半子区域中存在与x更近的点，则进入另一个子区域中查找该点并且更新”近似最近点“重复3的步骤，直到另一子区域与球体不相交或者退回根节点最后更新的”近似最近点“与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)=