精华内容
下载资源
问答
  • 【校招面经】机器学习与数据挖掘常见面试题整理 part2 2018年07月25日 12:36:40稻蛙阅读数:150 三十、随机森林如何评估特征重要性 衡量变量重要性的方法有两种,Decrease GINI 和 Decrease ...

    【校招面经】机器学习与数据挖掘常见面试题整理 part2

    三十、随机森林如何评估特征重要性

    衡量变量重要性的方法有两种,Decrease GINI 和 Decrease Accuracy: 1) Decrease GINI: 对于回归问题,直接使用argmax(VarVarLeftVarRight)作为评判标准,即当前节点训练集的方差Var减去左节点的方差VarLeft和右节点的方差VarRight。 2) Decrease Accuracy:对于一棵树Tb(x),我们用OOB样本可以得到测试误差1;然后随机改变OOB样本的第j列:保持其他列不变,对第j列进行随机的上下置换,得到误差2。至此,我们可以用误差1-误差2来刻画变量j的重要性。基本思想就是,如果一个变量j足够重要,那么改变它会极大的增加测试误差;反之,如果改变它测试误差没有增大,则说明该变量不是那么的重要

     

    三十一、常见的损失函数

    对于给定的输入X,由f(X)给出相应的输出Y,这个输出的预测值f(X)与真实值Y可能一致也可能不一致(要知道,有时损失或误差是不可避免的),用一个损失函数来度量预测错误的程度。损失函数记为L(Y, f(X))。 常用的损失函数有以下几种(基本引用自《统计学习方法》):

    如此,SVM有第二种理解,即最优化+损失最小,或如@夏粉_百度所说“可从损失函数和优化算法角度看SVM,boosting,LR等算法,可能会有不同收获”。 关于SVM的更多理解请参考:支持向量机通俗导论(理解SVM的三层境界),链接:http://blog.csdn.net/v_july_v/article/details/7624837

     

    三十二、什么是OOB?随机森林中OOB是如何计算的,它有什么优缺点?

    bagging方法中Bootstrap每次约有1/3的样本不会出现在Bootstrap所采集的样本集合中,当然也就没有参加决策树的建立,把这1/3的数据称为袋外数据oob(out of bag),它可以用于取代测试集误差估计方法。 袋外数据(oob)误差的计算方法如下: 对于已经生成的随机森林,用袋外数据测试其性能,假设袋外数据总数为O,用这O个袋外数据作为输入,带进之前已经生成的随机森林分类器,分类器会给出O个数据相应的分类,因为这O条数据的类型是已知的,则用正确的分类与随机森林分类器的结果进行比较,统计随机森林分类器分类错误的数目,设为X,则袋外数据误差大小=X/O;这已经经过证明是无偏估计的,所以在随机森林算法中不需要再进行交叉验证或者单独的测试集来获取测试集误差的无偏估计。

     

    三十三、什么样的模型对缺失值更敏感

     

    三十四、生成模型与判别模型的区别是什么

    生成模型可以产生数据,判别模型只能根据数据做判断。

    常见的判别式模型有: Logistic regression(logistical 回归) Linear discriminant analysis(线性判别分析) Supportvector machines(支持向量机) Boosting(集成学习) Conditional random fields(条件随机场) Linear regression(线性回归) Neural networks(神经网络) 常见的生成式模型有: Gaussian mixture model and othertypes of mixture model(高斯混合及其他类型混合模型) Hidden Markov model(隐马尔可夫) NaiveBayes(朴素贝叶斯) AODE(平均单依赖估计) Latent Dirichlet allocation(LDA主题模型) Restricted Boltzmann Machine(限制波兹曼机) 生成式模型是根据概率乘出结果,而判别式模型是给出输入,计算出结果。

     

     

    三十五、SMOTE过采样算法

      JAIR'2002的文章《SMOTE: Synthetic Minority Over-sampling Technique》提出了一种过采样算法SMOTE。概括来说,本算法基于“插值”来为少数类合成新的样本。下面介绍如何合成新的样本。

            设训练集的一个少数类的样本数为 T ,那么SMOTE算法将为这个少数类合成 NT 个新样本。这里要求 N 必须是正整数,如果给定的 N<1 那么算法将“认为”少数类的样本数T=NT ,并将强制 N=1 。

          考虑该少数类的一个样本 i ,其特征向量为 xi,i∈{1,...,T} :

          1. 首先从该少数类的全部 T 个样本中找到样本 xi 的 k 个近邻(例如用欧氏距离),记为 xi(near),near∈{1,...,k} ;

          2. 然后从这 k 个近邻中随机选择一个样本 xi(nn) ,再生成一个 0 到 1 之间的随机数ζ1 ,从而合成一个新样本 xi1 :

    xi1=xi+ζ1⋅(xi(nn)−xi)

          3. 将步骤2重复进行 N 次,从而可以合成 N 个新样本:xinew,new∈1,...,N。

          那么,对全部的 T 个少数类样本进行上述操作,便可为该少数类合成 NT 个新样本。

          如果样本的特征维数是 2 维,那么每个样本都可以用二维平面上的一个点来表示。SMOTE算法所合成出的一个新样本 xi1 相当于是表示样本 xi 的点和表示样本 xi(nn) 的点之间所连线段上的一个点。所以说该算法是基于“插值”来合成新样本。

     

    三十六、流形学习是什么

    流形学习(manifold learning)是机器学习、模式识别中的一种方法,在维数约简方面具有广泛的应用。它的主要思想是将高维的数据映射到低维,使该低维的数据能够反映原高维数据的某些本质结构特征。流形学习的前提是有一种假设,即某些高维数据,实际是一种低维的流形结构嵌入在高维空间中。流形学习的目的是将其映射回低维空间中,揭示其本质。

    以下图为例[1],左边是一个三维数据的分布,右边是降低到二维后的结果。我们可以发现二维的数据更能直观地表示其流形结构。

     

    通过流形学习来实现降维的方法有很多,其基本思想也类似:假设数据在高维具有某种结构特征,希望降到低维后,仍能保持该结构。

    比较常见的有

    1. 局部改线嵌入(Local Linear Embedding, LLE)[1]

    假设数据中每个点可以由其近邻的几个点重构出来。降到低维,使样本仍能保持原来的重构关系,且重构系数也一样。

    2. 拉普拉斯特征映射(Laplacian Eigenmaps, LE)[2]

    将数据映射到低维,且保持点之间的(相似度)距离关系。即在原空间中相距较远的点,投影到低维空间中,希望它们之间仍相距较远。反之亦然。

    3. 局部保持投影(LPP)[3]

    4. 等距映射(Isomap)[4]

    等等。。。

    浙江大学何晓飞老师有个关于流形学习的报告,有兴趣可以看下。

    http://www.cad.zju.edu.cn/reports/%C1%F7%D0%CE%D1%A7%CF%B0.pdf

    [1] Roweis, Sam T and Saul, Lawrence K. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500). 2000: 2323-2326.

    [2] Belkin, Mikhail and Niyogi, Partha. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation. 15(6). 2003:1373-1396.

    [3] He, Xiaofei and Niyogi, Partha. Locality preserving projections. NIPS. 2003:234-241.

    [4] Tenenbaum, Joshua B and De Silva, Vin and Langford, John C. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500). 2000: 2319-2323.

     

    三十七、深度学习SparseAutoEncoder

    AutoEncoder:AutoEncoder的结构与神经网络的隐含层相同,由输入L1,输出 L2组成,中间则是权重连接。Autoencoder通过L2得到输入的重构L3,最小化L3与L1的差别 进行训练得到权重。在这样的权重参数下,得到的L2可以尽可能的保存L1的信息。 Autoencoder的输出L2的维度由输出的神经元个数决定。当输出维度大于L1时,则需要在训练目标函数中加入sparse 惩罚项,避免L2直接复制L1(权重全为1)。所以称为sparseAutoencoder( Andrew Ng提出的)。

     

    三十八、线性分类器最佳准则

    线性分类器有三大类:感知器准则函数、SVM、Fisher准则。

    1. 感知器准则函数:代价函数J=-(W*X+w0),分类的准则是最小化代价函数。感知器是神经网络(NN)的基础,网上有很多介绍。

    2. SVM:支持向量机也是很经典的算法,优化目标是最大化间隔(margin),又称最大间隔分类器,是一种典型的线性分类器。(使用核函数可解决非线性问题)

    3. Fisher准则:更广泛的称呼是线性判别分析(LDA),将所有样本投影到一条远点出发的直线,使得同类样本距离尽可能小,不同类样本距离尽可能大,具体为最大化“广义瑞利商”。

     

    三十九、数据清理中,处理缺失值的方法是

    由于调查、编码和录入误差,数据中可能存在一些无效值和缺失值,需要给予适当的处理。常用的处理方法有:估算,整例删除,变量删除和成对删除。

    1. 估算(estimation)。最简单的办法就是用某个变量的样本均值、中位数或众数代替无效值和缺失值。这种办法简单,但没有充分考虑数据中已有的信息,误差可能较大。另一种办法就是根据调查对象对其他问题的答案,通过变量之间的相关分析或逻辑推论进行估计。例如,某一产品的拥有情况可能与家庭收入有关,可以根据调查对象的家庭收入推算拥有这一产品的可能性。

    2. 整例删除(casewise deletion)是剔除含有缺失值的样本。由于很多问卷都可能存在缺失值,这种做法的结果可能导致有效样本量大大减少,无法充分利用已经收集到的数据。因此,只适合关键变量缺失,或者含有无效值或缺失值的样本比重很小的情况。

    3. 变量删除(variable deletion)。如果某一变量的无效值和缺失值很多,而且该变量对于所研究的问题不是特别重要,则可以考虑将该变量删除。这种做法减少了供分析用的变量数目,但没有改变样本量。

    4. 成对删除(pairwise deletion)是用一个特殊码(通常是9、99、999等)代表无效值和缺失值,同时保留数据集中的全部变量和样本。但是,在具体计算时只采用有完整答案的样本,因而不同的分析因涉及的变量不同,其有效样本量也会有所不同。这是一种保守的处理方法,最大限度地保留了数据集中的可用信息。

    采用不同的处理方法可能对分析结果产生影响,尤其是当缺失值的出现并非随机且变量之间明显相关时。因此,在调查中应当尽量避免出现无效值和缺失值,保证数据的完整性。

     

    四十、神经网络之损失函数

    来源:https://blog.csdn.net/xmdxcsj/article/details/50210451

    1. quadratic+sigmoid (平方损失函数) 

    2. cross entropy + sigmoid (交叉熵损失函数) 

    3. softmax + log-likelihood

     

    一、quadratic+sigmoid (平方损失函数)

    (1)定义 

    平方和损失函数定义 C=0.5*(y−a)^2,其中y是期望输出,a是实际输出。 

    (2)收敛特性 

    不幸的是,使用平方和作为损失函数的神经单元不具备这种性质,即当误差越大的时候,收敛(学习)速度应该越快。你可以按照下面的列子验证一下。

    z=wx+b a=δ(z)

    • 1
    • 2

    根据链式法则,求C对于w的偏导数

    ∂C/∂w=(δ(z)−y)δ′(z)x ∂C/∂b=(δ(z)−y)δ′(z)

    • 1
    • 2

    如果激活函数使用的是sigmoid函数的话,根据激活函数的形状和特性可知,当δ(z)趋近于0或者趋近于1的时候,δ′(z)会趋近于0,当δ(z)趋近于0.5的时候,δ′(z)会最大。 

    比如说,取y=0,当δ(z)=1的时候,期望值和实际值的误差δ(z)−y达到最大,此时,δ′(z)会趋近于0,所以就会发生收敛速度慢的问题。

    二、cross entropy + sigmoid (交叉熵损失函数)

    (1)定义 

    为了解决当误差大时,收敛速度大的问题,引入交叉熵损失函数。

    C=−(ylna+(1−y)ln(1−a))

    • 1

    (2)特点 

    要想成为loss function,需要满足两点要求: 

    1. 非负性 

    2. 预测值和期望值接近时,函数值趋于0 

    显然,quadratic cost function满足以上两点。cross entropy同样也满足以上两点,所以其可以成为一个合格的cost function。

    (3)收敛特性

    z=wx+b a=δ(z)

    • 1
    • 2

    依旧根据链式法则,可以求得对应的偏导数

    ∂C/∂w={(δ(z)−y)/δ(z)((1−δ(z))}δ′(z)x

    • 1

    对于sigmoid函数,有δ′(z)=δ(z)(1−δ(z))对上式子进行替换和约分有∂C/∂w=(δ(z)−y)x 

     

    ∂C/∂b同理,∂C/∂b=(δ(z)−y)x。 

    可以看到梯度(∂C/∂w)正比与误差(δ(z)−y),满足我们最初的目标! 

    (4)含义 

    交叉熵是用来衡量两个概率分布之间的差异。交叉熵越大即信息量越大,两个分布之间的差异越大,越对实验结果感到意外,反之,交叉熵越小,两个分布越相似,越符合预期。如抛掷两枚硬币,如果确定出现某一面其信息量不大,而正反面都是以1/2的概率出现,这个时候信息熵最大。下面以离散分布为例讨论。 

    q(x)表示估计x的概率分布,p(x)表示真实x的概率分布,交叉熵定义如下:

    H(p(x),q(x))=H(p(x))+D(p(x)||q(x))

    • 1

    其中,H(p(x))表示p(x)的熵,定义如下:

    H(p(x))=−∑p(x)logp(x)

    • 1

    D(p(x)||q(x))表示p(x)和q(x)的KL距离(Kullback-Leibler divergence),也叫作相对熵,定义如下:

    D(p(x)||q(x))=∑p(x)log(p(x)/q(x))

    • 1

    由H(p(x))和D(p(x)||q(x))可得H(p,q)=−∑p(x)logq(x)

    对于神经网络的二值输出(0或者1),假设神经网络输出a表示是输出1的概率(此时对应的y=1),那么1−a表示输出0的概率(此时对应的1−y=0),所以交叉熵可以定义成如下形式: 

    C=−(ylna+(1−y)ln(1−a))

    三、softmax + log-likelihood

    (1)softmax多分类器定义

    zj=∑wx+b aj=ej/∑ek (原来此处是sigmoid函数)

    • 1
    • 2

    (2)loss的计算公式

    C=−lnay

    • 1

    ay表示类别y对应的预测概率,如果预测好的话,ay会趋近于1,C会趋近于0,反之,ay趋近于0,C趋近于极大。 

    (3)梯度计算

    ∂C/∂w=(a−1)∗x ∂C/∂b=a−1

    • 1
    • 2

    当aj预测不好时,误差会很大,收敛会变快。

    四、结论

    (一)sigmoid

    在激活函数使用sigmoid的前提之下,相比于quadratic cost function, cross entropy cost function具有收敛速度快和更容易获得全局最优(至于为什么更容易获得全局最优,个人感觉有点类似于动量的物理意义,增加收敛的步长,加快收敛的速度,更容易跳过局部最优)的特点。 

    因为我们一般使用随机值来初始化权重,这就可能导致一部分期望值和预测值相差甚远。所以选择sigmoid作为激活函数的时候,推荐使用cross entropy。如果激活函数不是sigmoid,quadratic cost function就不会存在收敛速度慢的问题。 

    (二)softmax

    对于分类问题,如果希望输出是类别的概率,那么激活函数选择使用softmax,同时使用log-likelihood作为损失函数。

    转载于:https://www.cnblogs.com/yumoye/p/10354137.html

    展开全文
  • 【校招面经】机器学习与数据挖掘常见面试题整理 part8 2018年08月04日 21:46:27稻蛙阅读数:266 七十六、t-SNE from:http://www.datakit.cn/blog/2017/02/05/t_sne_full.html t-SNE(t-...

    【校招面经】机器学习与数据挖掘常见面试题整理 part8

    七十六、t-SNE

    from:http://www.datakit.cn/blog/2017/02/05/t_sne_full.html

    t-SNE(t-distributed stochastic neighbor embedding)是用于降维的一种机器学习算法,是由 Laurens van der Maaten 和 Geoffrey Hinton在08年提出来。此外,t-SNE 是一种非线性降维算法,非常适用于高维数据降维到2维或者3维,进行可视化。

     

    SNE是通过仿射(affinitie)变换将数据点映射到概率分布上,主要包括两个步骤:

    • SNE构建一个高维对象之间的概率分布,使得相似的对象有更高的概率被选择,而不相似的对象有较低的概率被选择。
    • SNE在低维空间里在构建这些点的概率分布,使得这两个概率分布之间尽可能的相似。

    我们看到t-SNE模型是非监督的降维,他跟kmeans等不同,他不能通过训练得到一些东西之后再用于其它数据(比如kmeans可以通过训练得到k个点,再用于其它数据集,而t-SNE只能单独的对数据做操作,也就是说他只有fit_transform,而没有fit操作)

     

    主要不足有四个:

    • 主要用于可视化,很难用于其他目的。比如测试集合降维,因为他没有显式的预估部分,不能在测试集合直接降维;比如降维到10维,因为t分布偏重长尾,1个自由度的t分布很难保存好局部特征,可能需要设置成更高的自由度。
    • t-SNE倾向于保存局部特征,对于本征维数(intrinsic dimensionality)本身就很高的数据集,是不可能完整的映射到2-3维的空间
    • t-SNE没有唯一最优解,且没有预估部分。如果想要做预估,可以考虑降维之后,再构建一个回归方程之类的模型去做。但是要注意,t-sne中距离本身是没有意义,都是概率分布问题。
    • 训练太慢。有很多基于树的算法在t-sne上做一些改进

     

    七十七、奇异值分解(SVD)

    from:http://www.cnblogs.com/go-go/p/9372863.html

    奇异值往往对应着矩阵中隐含的重要信息,且重要性和奇异值大小正相关。每个矩阵A都可以表示为一系列秩为1的“小矩阵”之和,而奇异值则衡量了这些“小矩阵”对于A的权重。

    奇异值分解(Singular Value Decomposition,以下简称SVD)是在机器学习领域广泛应用的算法,它不光可以用于降维算法中的特征分解,还可以用于推荐系统,以及自然语言处理等领域。是很多机器学习算法的基石。本文就对SVD的原理做一个总结,并讨论在在PCA降维算法中是如何运用运用SVD的。

    1. 回顾特征值和特征向量

        我们首先回顾下特征值和特征向量的定义如下:

    Ax=λx

        其中A是一个n×n的矩阵,x是一个n维向量,则我们说λ是矩阵A的一个特征值,而x是矩阵A的特征值λ所对应的特征向量。

        求出特征值和特征向量有什么好处呢? 就是我们可以将矩阵A特征分解。如果我们求出了矩阵A的n个特征值λ1≤λ2≤...≤λn,以及这n个特征值所对应的特征向量{w1,w2,...wn},那么矩阵A就可以用下式的特征分解表示:

    A=WΣW−1

        其中W是这n个特征向量所张成的n×n维矩阵,而Σ为这n个特征值为主对角线的n×n维矩阵。

        一般我们会把W的这n个特征向量标准化,即满足||wi||2=1, 或者说wTiwi=1,此时W的n个特征向量为标准正交基,满足WTW=I,即WT=W−1, 也就是说W为酉矩阵。

        这样我们的特征分解表达式可以写成

    A=WΣWT

        注意到要进行特征分解,矩阵A必须为方阵。那么如果A不是方阵,即行和列不相同时,我们还可以对矩阵进行分解吗?答案是可以,此时我们的SVD登场了。

    2.  SVD的定义

        SVD也是对矩阵进行分解,但是和特征分解不同,SVD并不要求要分解的矩阵为方阵。假设我们的矩阵A是一个m×n的矩阵,那么我们定义矩阵A的SVD为:

    A=UΣVT

        其中U是一个m×m的矩阵,Σ是一个m×n的矩阵,除了主对角线上的元素以外全为0,主对角线上的每个元素都称为奇异值,V是一个n×n的矩阵。U和V都是酉矩阵,即满足UTU=I,VTV=I。下图可以很形象的看出上面SVD的定义:

        那么我们如何求出SVD分解后的U,Σ,V这三个矩阵呢?

        如果我们将A的转置和A做矩阵乘法,那么会得到n×n的一个方阵ATA。既然ATA是方阵,那么我们就可以进行特征分解,得到的特征值和特征向量满足下式:

    (ATA)vi=λivi

        这样我们就可以得到矩阵ATA的n个特征值和对应的n个特征向量v了。将ATA的所有特征向量张成一个n×n的矩阵V,就是我们SVD公式里面的V矩阵了。一般我们将V中的每个特征向量叫做A的右奇异向量。

        如果我们将A和A的转置做矩阵乘法,那么会得到m×m的一个方阵AAT。既然AAT是方阵,那么我们就可以进行特征分解,得到的特征值和特征向量满足下式:

    (AAT)ui=λiui

        这样我们就可以得到矩阵AAT的m个特征值和对应的m个特征向量u了。将AAT的所有特征向量张成一个m×m的矩阵U,就是我们SVD公式里面的U矩阵了。一般我们将U中的每个特征向量叫做A的左奇异向量。

        U和V我们都求出来了,现在就剩下奇异值矩阵Σ没有求出了。由于Σ除了对角线上是奇异值其他位置都是0,那我们只需要求出每个奇异值σ就可以了。

        我们注意到:

    A=UΣVT⇒AV=UΣVTV⇒AV=UΣ⇒Avi=σiui⇒σi=Avi/ui

         这样我们可以求出我们的每个奇异值,进而求出奇异值矩阵Σ。

        上面还有一个问题没有讲,就是我们说ATA的特征向量组成的就是我们SVD中的V矩阵,而AAT的特征向量组成的就是我们SVD中的U矩阵,这有什么根据吗?这个其实很容易证明,我们以V矩阵的证明为例。

    A=UΣVT⇒AT=VΣUT⇒ATA=VΣUTUΣVT=VΣ2VT

        上式证明使用了:UTU=I,ΣT=Σ。可以看出ATA的特征向量组成的的确就是我们SVD中的V矩阵。类似的方法可以得到AAT的特征向量组成的就是我们SVD中的U矩阵。

        进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方,也就是说特征值和奇异值满足如下关系:

    σi=λi−−√

        这样也就是说,我们可以不用σi=Avi/ui来计算奇异值,也可以通过求出ATA的特征值取平方根来求奇异值。

    3. SVD计算举例

        这里我们用一个简单的例子来说明矩阵是如何进行奇异值分解的。我们的矩阵A定义为:

    A=⎛⎝⎜011110⎞⎠⎟

        我们首先求出ATA和AAT

    ATA=(011110)⎛⎝⎜011110⎞⎠⎟=(2112)

    AAT=⎛⎝⎜011110⎞⎠⎟(011110)=⎛⎝⎜110121011⎞⎠⎟

         进而求出ATA的特征值和特征向量:

    λ1=3;v1=(1/2–√1/2–√);λ2=1;v2=(−1/2–√1/2–√)

        接着求AAT的特征值和特征向量:

    λ1=3;u1=⎛⎝⎜1/6–√2/6–√1/6–√⎞⎠⎟;λ2=1;u2=⎛⎝⎜1/2–√0−1/2–√⎞⎠⎟;λ3=0;u3=⎛⎝⎜1/3–√−1/3–√1/3–√⎞⎠⎟

     

        利用Avi=σiui,i=1,2求奇异值:

    ⎛⎝⎜011110⎞⎠⎟(1/2–√1/2–√)=σ1⎛⎝⎜1/6–√2/6–√1/6–√⎞⎠⎟⇒σ1=3–√

    ⎛⎝⎜011110⎞⎠⎟(−1/2–√1/2–√)=σ2⎛⎝⎜1/2–√0−1/2–√⎞⎠⎟⇒σ2=1

    当然,我们也可以用σi=λi−−√直接求出奇异值为3–√和1.

     最终得到A的奇异值分解为:

    A=UΣVT=⎛⎝⎜1/6–√2/6–√1/6–√1/2–√0−1/2–√1/3–√−1/3–√1/3–√⎞⎠⎟⎛⎝⎜3–√00010⎞⎠⎟(1/2–√−1/2–√1/2–√1/2–√)

          

    4. SVD的一些性质 

        上面几节我们对SVD的定义和计算做了详细的描述,似乎看不出我们费这么大的力气做SVD有什么好处。那么SVD有什么重要的性质值得我们注意呢?

        对于奇异值,它跟我们特征分解中的特征值类似,在奇异值矩阵中也是按照从大到小排列,而且奇异值的减少特别的快,在很多情况下,前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说,我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说:

    Am×n=Um×mΣm×nVTn×n≈Um×kΣk×kVTk×n

        其中k要比n小很多,也就是一个大的矩阵A可以用三个小的矩阵Um×k,Σk×k,VTk×n来表示。如下图所示,现在我们的矩阵A只需要灰色的部分的三个小矩阵就可以近似描述了。

        由于这个重要的性质,SVD可以用于PCA降维,来做数据压缩和去噪。也可以用于推荐算法,将用户和喜好对应的矩阵做特征分解,进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法,比如潜在语义索引(LSI)。下面我们就对SVD用于PCA降维做一个介绍。

    5. SVD用于PCA

        在主成分分析(PCA)原理总结中,我们讲到要用PCA降维,需要找到样本协方差矩阵XTX的最大的d个特征向量,然后用这最大的d个特征向量张成的矩阵来做低维投影降维。可以看出,在这个过程中需要先求出协方差矩阵XTX,当样本数多样本特征数也多的时候,这个计算量是很大的。

        注意到我们的SVD也可以得到协方差矩阵XTX最大的d个特征向量张成的矩阵,但是SVD有个好处,有一些SVD的实现算法可以不求先求出协方差矩阵XTX,也能求出我们的右奇异矩阵V。也就是说,我们的PCA算法可以不用做特征分解,而是做SVD来完成。这个方法在样本量很大的时候很有效。实际上,scikit-learn的PCA算法的背后真正的实现就是用的SVD,而不是我们我们认为的暴力特征分解。

        另一方面,注意到PCA仅仅使用了我们SVD的右奇异矩阵,没有使用左奇异矩阵,那么左奇异矩阵有什么用呢?

        假设我们的样本是m×n的矩阵X,如果我们通过SVD找到了矩阵XXT最大的d个特征向量张成的m×d维矩阵U,则我们如果进行如下处理:

    X′d×n=UTd×mXm×n

        可以得到一个d×n的矩阵X‘,这个矩阵和我们原来的m×n维样本矩阵X相比,行数从m减到了k,可见对行数进行了压缩。也就是说,左奇异矩阵可以用于行数的压缩。相对的,右奇异矩阵可以用于列数即特征维度的压缩,也就是我们的PCA降维。    

    6. SVD小结 

        SVD作为一个很基本的算法,在很多机器学习算法中都有它的身影,特别是在现在的大数据时代,由于SVD可以实现并行化,因此更是大展身手。SVD的原理不难,只要有基本的线性代数知识就可以理解,实现也很简单因此值得仔细的研究。当然,SVD的缺点是分解出的矩阵解释性往往不强,有点黑盒子的味道,不过这不影响它的使用。

     

    七十八、势函数

     

    七十九、word2vec原理_CBOW与Skip-Gram模型基础

    from:https://www.cnblogs.com/pinard/p/7160330.html

     word2vec是google在2013年推出的一个NLP工具,它的特点是将所有的词向量化,这样词与词之间就可以定量的去度量他们之间的关系,挖掘词之间的联系。虽然源码是开源的,但是谷歌的代码库国内无法访问,因此本文的讲解word2vec原理以Github上的word2vec代码为准。本文关注于word2vec的基础知识。

    1. 词向量基础

        用词向量来表示词并不是word2vec的首创,在很久之前就出现了。最早的词向量是很冗长的,它使用是词向量维度大小为整个词汇表的大小,对于每个具体的词汇表中的词,将对应的位置置为1。比如我们有下面的5个词组成的词汇表,词"Queen"的序号为2, 那么它的词向量就是(0,1,0,0,0)。同样的道理,词"Woman"的词向量就是(0,0,0,1,0)。这种词向量的编码方式我们一般叫做1-of-N representation或者one hot representation.

         One hot representation用来表示词向量非常简单,但是却有很多问题。最大的问题是我们的词汇表一般都非常大,比如达到百万级别,这样每个词都用百万维的向量来表示简直是内存的灾难。这样的向量其实除了一个位置是1,其余的位置全部都是0,表达的效率不高,能不能把词向量的维度变小呢?

        Dristributed representation可以解决One hot representation的问题,它的思路是通过训练,将每个词都映射到一个较短的词向量上来。所有的这些词向量就构成了向量空间,进而可以用普通的统计学的方法来研究词与词之间的关系。这个较短的词向量维度是多大呢?这个一般需要我们在训练时自己来指定。

        比如下图我们将词汇表里的词用"Royalty","Masculinity", "Femininity"和"Age"4个维度来表示,King这个词对应的词向量可能是(0.99,0.99,0.05,0.7)。当然在实际情况中,我们并不能对词向量的每个维度做一个很好的解释。

     

        有了用Dristributed representation表示的较短的词向量,我们就可以较容易的分析词之间的关系了,比如我们将词的维度降维到2维,有一个有趣的研究表明,用下图的词向量表示我们的词时,我们可以发现:

    King→−Man→+Woman→=Queen→

         可见我们只要得到了词汇表里所有词对应的词向量,那么我们就可以做很多有趣的事情了。不过,怎么训练得到合适的词向量呢?一个很常见的方法是使用神经网络语言模型。

    2. CBOW与Skip-Gram用于神经网络语言模型

        在word2vec出现之前,已经有用神经网络DNN来用训练词向量进而处理词与词之间的关系了。采用的方法一般是一个三层的神经网络结构(当然也可以多层),分为输入层,隐藏层和输出层(softmax层)。

        这个模型是如何定义数据的输入和输出呢?一般分为CBOW(Continuous Bag-of-Words 与Skip-Gram两种模型。

        CBOW模型的训练输入是某一个特征词的上下文相关的词对应的词向量,而输出就是这特定的一个词的词向量。比如下面这段话,我们的上下文大小取值为4,特定的这个词是"Learning",也就是我们需要的输出词向量,上下文对应的词有8个,前后各4个,这8个词是我们模型的输入。由于CBOW使用的是词袋模型,因此这8个词都是平等的,也就是不考虑他们和我们关注的词之间的距离大小,只要在我们上下文之内即可。

        这样我们这个CBOW的例子里,我们的输入是8个词向量,输出是所有词的softmax概率(训练的目标是期望训练样本特定词对应的softmax概率最大),对应的CBOW神经网络模型输入层有8个神经元,输出层有词汇表大小个神经元。隐藏层的神经元个数我们可以自己指定。通过DNN的反向传播算法,我们可以求出DNN模型的参数,同时得到所有的词对应的词向量。这样当我们有新的需求,要求出某8个词对应的最可能的输出中心词时,我们可以通过一次DNN前向传播算法并通过softmax激活函数找到概率最大的词对应的神经元即可。

        

        Skip-Gram模型和CBOW的思路是反着来的,即输入是特定的一个词的词向量,而输出是特定词对应的上下文词向量。还是上面的例子,我们的上下文大小取值为4, 特定的这个词"Learning"是我们的输入,而这8个上下文词是我们的输出。

        这样我们这个Skip-Gram的例子里,我们的输入是特定词, 输出是softmax概率排前8的8个词,对应的Skip-Gram神经网络模型输入层有1个神经元,输出层有词汇表大小个神经元。隐藏层的神经元个数我们可以自己指定。通过DNN的反向传播算法,我们可以求出DNN模型的参数,同时得到所有的词对应的词向量。这样当我们有新的需求,要求出某1个词对应的最可能的8个上下文词时,我们可以通过一次DNN前向传播算法得到概率大小排前8的softmax概率对应的神经元所对应的词即可。

        以上就是神经网络语言模型中如何用CBOW与Skip-Gram来训练模型与得到词向量的大概过程。但是这和word2vec中用CBOW与Skip-Gram来训练模型与得到词向量的过程有很多的不同。

        word2vec为什么 不用现成的DNN模型,要继续优化出新方法呢?最主要的问题是DNN模型的这个处理过程非常耗时。我们的词汇表一般在百万级别以上,这意味着我们DNN的输出层需要进行softmax计算各个词的输出概率的的计算量很大。有没有简化一点点的方法呢?

    3. word2vec基础之霍夫曼树

        word2vec也使用了CBOW与Skip-Gram来训练模型与得到词向量,但是并没有使用传统的DNN模型。最先优化使用的数据结构是用霍夫曼树来代替隐藏层和输出层的神经元,霍夫曼树的叶子节点起到输出层神经元的作用,叶子节点的个数即为词汇表的小大。 而内部节点则起到隐藏层神经元的作用。

        具体如何用霍夫曼树来进行CBOW和Skip-Gram的训练我们在下一节讲,这里我们先复习下霍夫曼树。

        霍夫曼树的建立其实并不难,过程如下:

        输入:权值为(w1,w2,...wn)的n个节点

        输出:对应的霍夫曼树

        1)将(w1,w2,...wn)看做是有n棵树的森林,每个树仅有一个节点。

        2)在森林中选择根节点权值最小的两棵树进行合并,得到一个新的树,这两颗树分布作为新树的左右子树。新树的根节点权重为左右子树的根节点权重之和。

        3) 将之前的根节点权值最小的两棵树从森林删除,并把新树加入森林。

        4)重复步骤2)和3)直到森林里只有一棵树为止。

        下面我们用一个具体的例子来说明霍夫曼树建立的过程,我们有(a,b,c,d,e,f)共6个节点,节点的权值分布是(16,4,8,6,20,3)。

        首先是最小的b和f合并,得到的新树根节点权重是7.此时森林里5棵树,根节点权重分别是16,8,6,20,7。此时根节点权重最小的6,7合并,得到新子树,依次类推,最终得到下面的霍夫曼树。

        那么霍夫曼树有什么好处呢?一般得到霍夫曼树后我们会对叶子节点进行霍夫曼编码,由于权重高的叶子节点越靠近根节点,而权重低的叶子节点会远离根节点,这样我们的高权重节点编码值较短,而低权重值编码值较长。这保证的树的带权路径最短,也符合我们的信息论,即我们希望越常用的词拥有更短的编码。如何编码呢?一般对于一个霍夫曼树的节点(根节点除外),可以约定左子树编码为0,右子树编码为1.如上图,则可以得到c的编码是00。

        在word2vec中,约定编码方式和上面的例子相反,即约定左子树编码为1,右子树编码为0,同时约定左子树的权重不小于右子树的权重。

        我们在下一节的Hierarchical Softmax中再继续讲使用霍夫曼树和DNN语言模型相比的好处以及如何训练CBOW&Skip-Gram模型

     

    转载于:https://www.cnblogs.com/yumoye/p/10354159.html

    展开全文
  • 【校招面经】机器学习与数据挖掘常见面试题整理 part1 2018年07月23日 00:12:13稻蛙阅读数:938 注:以下是本人春招时看面经时收集的常见面试题,答案部分是由网上多个信息源整理而成,部分是个人...

    【校招面经】机器学习与数据挖掘常见面试题整理 part1

    注:以下是本人春招时看面经时收集的常见面试题,答案部分是由网上多个信息源整理而成,部分是个人解答。当时整理时只是自己看的,很多没有注明来源地址,后续有时间补上来源,如有侵权请告知。

     

    一、PCA为什么要中心化

    因为要算协方差。

    单纯的线性变换只是产生了倍数缩放,无法消除量纲对协方差的影响,而协方差是为了让投影后方差最大。

     

    二、PCA的主成分是什么

    统计学中,主成分分析(PCA)是一种简化数据集的技术。它是一个线性变换。这个变换把数据变换到一个新的坐标系统中,使得任何数据投影的第一大方差在第一个坐标(称为第一主成分)上,第二大方差在第二个坐标(第二主成分)上,依次类推。主成分分析经常用减少数据集的维数,同时保持数据集的对方差贡献最大的特征。这是通过保留低阶主成分,忽略高阶主成分做到的。这样低阶成分往往能够保留住数据的最重要方面。但是,这也不是一定的,要视具体应用而定。

    主成分分析的原理是设法将原来变量重新组合成一组新的相互无关的几个综合变量,同时根据实际需要从中可以取出几个较少的综合变量尽可能多地反映原来变量的信息的统计方法叫做主成分分析或称主分量分析,也是数学上处理降维的一种方法。主成分分析是设法将原来众多具有一定相关性(比如P个指标),重新组合成一组新的互相无关的综合指标来代替原来的指标。通常数学上的处理就是将原来P个指标作线性组合,作为新的综合指标。最经典的做法就是用F1(选取的第一个线性组合,即第一个综合指标)的方差来表达,即Va(rF1)越大,表示F1包含的信息越多。因此在所有的线性组合中选取的F1应该是方差最大的,故称F1为第一主成分。如果第一主成分不足以代表原来P个指标的信息,再考虑选取F2即选第二个线性组合,为了有效地反映原来信息,F1已有的信息就不需要再出现再F2中,用数学语言表达就是要求Cov(F1,F2)=0,则称F2为第二主成分,依此类推可以构造出第三、第四,……,第P个主成分。

     

    三、为什么KNN可以避免样本不平衡

    KNN只是取了最近的几个样本点做平均而已,离预测数据较远的训练数据对预测结果不会造成影响,但是svm、Bayes和NN每一个训练样本果都会对预测结果产生影响,于是如果样本不平衡的话KNN的效果最好,举个极端一点例子:答案只有A与B,但是训练样本中A的个数占99%,而B只有1%,svm、Bayes和NN训练出来的结果,恐怕预测任何数据给出的答案都是A,但是KNN不会。

     

    四、Padding,Kernel-size,stride关系公式

    像素宽度W,

    Padding size:P,

    Kernel size:K,

    Stride : S,

    n表示轮次,

    公式为:Wn+1=(Wn+P∗2−K)/S+1

     

    五、gini

    信息增益偏向于多值属性。尽管增益率调整了这种偏倚,但是它倾向于产生不平衡的划分,其中一个分区比其他分区小得多。基尼指数偏向于多值属性,并且当类的数量很大时会有困难。它还倾向于导致相等大小的分区和纯度。尽管是有偏的,但是这些度量在实践中产生相当好的结果。

     

    六、kmeans初始点的选择

     1. 选择批次距离尽可能远的K个点

      首先随机选择一个点作为第一个初始类簇中心点,然后选择距离该点最远的那个点作为第二个初始类簇中心点,然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点,以此类推,直至选出K个初始类簇中心点。

    2. 选用层次聚类或者Canopy算法进行初始聚类,然后利用这些类簇的中心点作为KMeans算法初始类簇中心点。

      常用的层次聚类算法有BIRCH和ROCK,在此不作介绍,下面简单介绍一下Canopy算法,主要摘自Mahout的Wiki:

      首先定义两个距离T1和T2,T1>T2.从初始的点的集合S中随机移除一个点P,然后对于还在S中的每个点I,计算该点I与点P的距离,如果距离小于T1,则将点I加入到点P所代表的Canopy中,如果距离小于T2,则将点I从集合S中移除,并将点I加入到点P所代表的Canopy中。迭代完一次之后,重新从集合S中随机选择一个点作为新的点P,然后重复执行以上步骤。

      Canopy算法执行完毕后会得到很多Canopy,可以认为每个Canopy都是一个Cluster,与KMeans等硬划分算法不同,Canopy的聚类结果中每个点有可能属于多个Canopy。我们可以选择距离每个Canopy的中心点最近的那个数据点,或者直接选择每个Canopy的中心点作为KMeans的初始K个类簇中心点。

     

    七、kmeans++

    k-means++算法选择初始seeds的基本思想就是:初始的聚类中心之间的相互距离要尽可能的远。 1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心 2. 对于数据集中的每一个点x,计算它与最近聚类中心(指已选择的聚类中心)的距离D(x) 3. 选择一个新的数据点作为新的聚类中心,选择的原则是:D(x)较大的点,被选取作为聚类中心的概率较大 4. 重复2和3直到k个聚类中心被选出来 5. 利用这k个初始的聚类中心来运行标准的k-means算法

     

    八、xgb中的贡献度(importance)是什么

    根据结构分数的增益情况计算出来选择哪个特征的哪个分割点,某个特征的重要性,就是它在所有树中出现的次数之和。

    (树模型特征重要性评估可参考:https://blog.csdn.net/u013382288/article/details/80838732

     

    九、xgboost怎么处理缺失值

    xgboost处理缺失值的方法和其他树模型不同,xgboost把缺失值当做稀疏矩阵来对待,本身的在节点分裂时不考虑的缺失值的数值。缺失值数据会被分到左子树和右子树分别计算损失,选择较优的那一个。如果训练中没有数据缺失,预测时出现了数据缺失,那么默认被分类到右子树。

     

    十、xgb和lgb的区别

    1. xgboost采用的是level-wise的分裂策略,而lightGBM采用了leaf-wise的策略,区别是xgboost对每一层所有节点做无差别分裂,可能有些节点的增益非常小,对结果影响不大,但是xgboost也进行了分裂,带来了务必要的开销。 leaft-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂,如此递归进行,很明显leaf-wise这种做法容易过拟合,因为容易陷入比较高的深度中,因此需要对最大深度做限制,从而避免过拟合。
    2. lightgbm使用了基于histogram的决策树算法,这一点不同与xgboost中的 exact 算法,histogram算法在内存和计算代价上都有不小优势。
    3. 内存上优势:很明显,直方图算法的内存消耗为(#data* #features * 1Bytes)(因为对特征分桶后只需保存特征离散化之后的值),而xgboost的exact算法内存消耗为:(2 * #data * #features* 4Bytes),因为xgboost既要保存原始feature的值,也要保存这个值的顺序索引,这些值需要32位的浮点数来保存。
    4. 计算上的优势,预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值,时间为(#data),而直方图算法只需要遍历桶就行了,时间为(#bin)
    5. 直方图做差加速
    6. 一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到,从而加速计算。
    7. lightgbm支持直接输入categorical的feature
    8. 在对离散特征分裂时,每个取值都当作一个桶,分裂时的增益算的是”是否属于某个category“的gain。类似于one-hot编码。
    9. 但实际上xgboost的近似直方图算法也类似于lightgbm这里的直方图算法,为什么xgboost的近似算法比lightgbm还是慢很多呢?
    10. xgboost在每一层都动态构建直方图, 因为xgboost的直方图算法不是针对某个特定的feature,而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图,而lightgbm中对每个特征都有一个直方图,所以构建一次直方图就够了。
    11. lightgbm做了cache优化
    12. feature parallel:一般的feature parallel就是对数据做垂直分割(partiion data vertically,就是对属性分割),然后将分割后的数据分散到各个workder上,各个workers计算其拥有的数据的best splits point, 之后再汇总得到全局最优分割点。但是lightgbm说这种方法通讯开销比较大,lightgbm的做法是每个worker都拥有所有数据,再分割?(没懂,既然每个worker都有所有数据了,再汇总有什么意义?这个并行体现在哪里??)
    13. data parallel:传统的data parallel是将对数据集进行划分,也叫 平行分割(partion data horizontally), 分散到各个workers上之后,workers对得到的数据做直方图,汇总各个workers的直方图得到全局的直方图。 lightgbm也claim这个操作的通讯开销较大,lightgbm的做法是使用”Reduce Scatter“机制,不汇总所有直方图,只汇总不同worker的不同feature的直方图(原理?),在这个汇总的直方图上做split,最后同步。

     

    十一、xgb的gamma,alpha,lambda等参数

    1. alpha[默认1]权重的L1正则化项。(和Lasso regression类似)。 可以应用在很高维度的情况下,使得算法的速度更快。

    2. lambda权重的L2正则化项(和Ridge regression类似)。 这个参数是用来控制XGBoost的正则化部分的 3. gamma[默认0]在节点分裂时,只有分裂后损失函数的值下降了,才会分裂这个节点。Gamma指定了节点分裂所需的最小损失函数下降值。 这个参数的值越大,算法越保守。

    xgboost寻找分割点的标准是最大化gain. 考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低,xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者,然后从候选者中计算Gain按最大值找出最佳的分割点。它的计算公式分为四项, 可以由正则化项参数调整(lamda为叶子权重平方和的系数, gama为叶子数量): 第一项是假设分割的左孩子的权重分数, 第二项为右孩子, 第三项为不分割总体分数, 最后一项为引入一个节点的复杂度损失 由公式可知, gamma越大gain越小, lamda越大, gain可能小也可能大

     

    十二、rf与gbdt之间的区别

    1)相同点:都是由多棵树组成,最终的结果都是由多棵树一起决定。 2)不同点: a 组成随机森林的树可以分类树也可以是回归树,而GBDT只由回归树组成 b 组成随机森林的树可以并行生成,而GBDT是串行生成 c 随机森林的结果是多数表决表决的,而GBDT则是多棵树累加之和 d 随机森林对异常值不敏感,而GBDT对异常值比较敏感 e 随机森林是减少模型的方差,而GBDT是减少模型的偏差 f 随机森林不需要进行特征归一化。而GBDT则需要进行特征归一化

     

    十三、nlp中常用的距离

    1. 莱文斯坦距离:莱文斯坦距离(LD)用于衡量两个字符串之间的相似度。 以下我们称这两个字符串分别为 a (原字符串) 和 b (目标字符串)。莱文斯坦距离被定义为''将字符串 a 变换为字符串 b 所需的删除、插入、替换操作的次数''。

     

    十四、lr与dt的区别

    1. lr是线性的,dt可以处理非线性

    2. lr不能有缺失值,dt可以缺失值

    3. dt是贪心的,可能陷入局部最优

    4. lr特征一定要标准化,dt可以不用

    5. lr特征间要尽量独立,dt无所谓

     

    十五、lr损失函数

     

    十六、lr和svm的区别

    1. svm只由支持向量绝对划分平面,lr是所有样本都参与决策面的更新

    2. svm对异常值不敏感,更稳健

     

    十七、为什么gbdt需要归一化

    1. 自身是梯度的过程,归一化加快收敛

    2. 避免给样本加权的时候过度偏向一些范围大的特征的样本

     

    十八、gbdt和xgb的差异

    1.损失函数是用泰勒展式二项逼近,而不是像gbdt里的就是一阶导数 2.对树的结构进行了正则化约束,防止模型过度复杂,降低了过拟合的可能性 3.节点分裂的方式不同,gbdt是用的gini系数,xgboost是经过优化推导后的gain 引用自:@Xijun LI

     

    十九、熵与gini

    既然这两个都可以表示数据的不确定性,不纯度。那么这两个有什么区别那?

    1. Gini 指数的计算不需要对数运算,更加高效;

    2. Gini 指数更偏向于连续属性,熵更偏向于离散属性。

     

    二十、正负样本失衡问题

    1. 上下采样方法,会影响样本的分布。上采样可以用SMOTE。

    2. 正样本比较少,可以把负样本分成多个,每个和正样本训练一个模型,然后把多个模型ensemble

    3. 公交卡发现小偷的案例(https://blog.csdn.net/u013382288/article/details/79301372),正负样本严重不平衡,那么先聚类,把正常的类拿掉,用剩下可能异常的样本训练模型

     

    二十一、余弦距离与欧式距离求相似度的差别

    1. 欧氏距离能够体现个体数值特征的绝对差异,所以更多的用于需要从维度的数值大小中体现差异的分析,如使用用户行为指标分析用户价值的相似度或差异。

    余弦距离更多的是从方向上区分差异,而对绝对的数值不敏感,更多的用于使用用户对内容评分来区分兴趣的相似度和差异,同时修正了用户间可能存在的度量标准不统一的问题(因为余弦距离对绝对数值不敏感)。

    2. 从几何意义上来说,n维向量空间的一条线段作为底边和原点组成的三角形,其顶角大小是不确定的。也就是说对于两条空间向量,即使两点距离一定,他们的夹角余弦值也可以随意变化。

    感性的认识,当两用户评分趋势一致时,但是评分值差距很大,余弦相似度倾向给出更优解。举个极端的例子,两用户只对两件商品评分,向量分别为(3,3)和(5,5),这两位用户的认知其实是一样的,但是欧式距离给出的解显然没有余弦值合理。

    3. 余弦夹角可以有效规避个体相同认知中不同程度的差异表现,更注重维度之间的差异,而不注重数值上的差异;反过来思考,当向量夹角的余弦值较小(差异很大)时,欧氏距离可以很小(差异很小),如(0,1)和(1,0)两个点,所以如果要对电子商务用户做聚类,区分高价值用户和低价值用户,用消费次数和平均消费额,这个时候用余弦夹角是不恰当的,因为它会将(2,10)和(10,50)的用户算成相似用户,但显然后者的价值高得多,因为这个时候需要注重数值上的差异,而不是维度之间的差异。

     

    二十二、优化kmeans计算速度

    使用kd树或者ball tree 将所有的观测实例构建成一颗kd树,之前每个聚类中心都是需要和每个观测点做依次距离计算,现在这些聚类中心根据kd树只需要计算附近的一个局部区域即可

     

    二十三、协同过滤与聚类推荐的区别

    1. 原理上:协同过滤实际上是图的搜索算法,找到某个节点的邻域;聚类是图的分解算法,将节点分入几个类中

    2. 使用上:协同过滤可以得到推荐排序,千人千面;聚类得到的是千人k面

    3. 如果只使用人的属性或物品的属性,聚类可以冷启动,协同过滤不行

    4. 计算上:协同过滤计算量大,大数据集下聚类会快一些。可以结合两者做,如先对用户进行聚类,然后用聚类代表做协同过滤

     

    二十四、为什么lr用sigmoid

    1. 因为是二分类问题,认为分类满足伯努利分布

    2. 求导快

    3. 值域[0-1],单调递增

     

    二十五、为什么xgboost要用泰勒展开,优势在哪里?

    xgboost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了xgboost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。

     

    二十六、为什么l1容易得到0解,l2容易得到更多接近0的解

    1. 图像法解释

           可以看到,L1-ball 与L2-ball 的不同就在于L1在和每个坐标轴相交的地方都有“角”出现,而目标函数的测地线除非位置摆得非常好,大部分时候都会在角的地方相交。注意到在角的位置就会产生稀疏性,例如图中的相交点就有w1=0,而更高维的时候(想象一下三维的L1-ball 是什么样的?)除了角点以外,还有很多边的轮廓也是既有很大的概率成为第一次相交的地方,又会产生稀疏性。

           相比之下,L2-ball 就没有这样的性质,因为没有角,所以第一次相交的地方出现在具有稀疏性的位置的概率就变得非常小了。这就从直观上来解释了为什么L1-regularization 能产生稀疏性,而L2-regularization 不行的原因了。

           总结:L1会趋向于产生少量的特征,而其他的特征都是0,而L2会选择更多的特征,这些特征都会接近于0。Lasso在特征选择时候非常有用,而Ridge就只是一种规则化而已。

    2. 导数法解释:L1和L2的差别,为什么一个让绝对值最小,一个让平方最小,会有那么大的差别呢?看导数一个是1一个是w便知, 在靠进零附近, L1以匀速下降到零, 而L2则完全停下来了. 这说明L1是将不重要的特征(或者说, 重要性不在一个数量级上)尽快剔除, L2则是把特征贡献尽量压缩最小但不至于为零. 两者一起作用, 就是把重要性在一个数量级(重要性最高的)的那些特征一起平等共事(简言之, 不养闲人也不要超人)。

     

    二十七、为什么ReLu要好过于tanh和sigmoid function

    第一,采用sigmoid等函数,算激活函数时(指数运算),计算量大,反向传播求误差梯度时,求导涉及除法,计算量相对大,而采用Relu激活函数,整个过程的计算量节省很多。

    第二,对于深层网络,sigmoid函数反向传播时,很容易就会出现梯度消失的情况(在sigmoid接近饱和区时,变换太缓慢,导数趋于0,这种情况会造成信息丢失,参见@Haofeng Li 答案的第三点),从而无法完成深层网络的训练。

    第三,Relu会使一部分神经元的输出为0,这样就造成了网络的稀疏性,并且减少了参数的相互依存关系,缓解了过拟合问题的发生

    作者:Begin Again

    链接:https://www.zhihu.com/question/29021768/answer/43488153

     

    二十八、梯度提升方法Gradient Boosting

    梯度提升算法初看起来不是很好理解,但我们和线性回归加以类比就容易了。回忆一下线性回归是希望找到一组参数使得残差最小化。如果只用一次项来解释二次曲线一定会有大量残差留下来,此时就可以用二次项来继续解释残差,所以可在模型中加入这个二次项。

    同样的,梯度提升是先根据初始模型计算伪残差,之后建立一个基学习器来解释伪残差,该基学习器是在梯度方向上减少残差。再将基学习器乘上权重系数(学习速率)和原来的模型进行线性组合形成新的模型。这样反复迭代就可以找到一个使损失函数的期望达到最小的模型。在训练基学习器时可以使用再抽样方法,此时就称之为随机梯度提升算法stochastic gradient boosting。

     

    二十九、随机梯度下降

    1. target function一般是用估计出的模型计算所有训练数据估计label和真实label的差距之和,随机梯度就是随机取样一些训练数据,替代整个训练集,在其上作target function的梯度下降。

    2. 因为只用少量样本,所以每一次比较快

    3. 比梯度下降更能应付鞍点问题

     

    三十、随机森林如何评估特征重要性

    衡量变量重要性的方法有两种,Decrease GINI 和 Decrease Accuracy: 1) Decrease GINI: 对于回归问题,直接使用argmax(VarVarLeftVarRight)作为评判标准,即当前节点训练集的方差Var减去左节点的方差VarLeft和右节点的方差VarRight。 2) Decrease Accuracy:对于一棵树Tb(x),我们用OOB样本可以得到测试误差1;然后随机改变OOB样本的第j列:保持其他列不变,对第j列进行随机的上下置换,得到误差2。至此,我们可以用误差1-误差2来刻画变量j的重要性。基本思想就是,如果一个变量j足够重要,那么改变它会极大的增加测试误差;反之,如果改变它测试误差没有增大,则说明该变量不是那么的重要

     

    转载于:https://www.cnblogs.com/yumoye/p/10354135.html

    展开全文
  • 【校招面经】机器学习与数据挖掘常见面试题整理 part9 2018年08月04日 22:10:31稻蛙阅读数:203 八十、SVM的核函数 from:https://blog.csdn.net/lihaitao000/article/details/51173459 SVM核...

    【校招面经】机器学习与数据挖掘常见面试题整理 part9

    八十、SVM的核函数

    from:https://blog.csdn.net/lihaitao000/article/details/51173459

    SVM核函数包括线性核函数、多项式核函数、径向基核函数、高斯核函数、幂指数核函数、拉普拉斯核函数、ANOVA核函数、二次有理核函数、多元二次核函数、逆多元二次核函数以及Sigmoid核函数. 核函数的定义并不困难,根据泛函的有关理论,只要一种函数 K ( x i , x j ) 满足Mercer条件,它就对应某一变换空间的内积.对于判断哪些函数是核函数到目前为止也取得了重要的突破,得到Mercer定理和以下常用的核函数类型: (1)线性核函数 K ( x , x i ) = x ⋅ x i (2)多项式核 K ( x , x i ) = ( ( x ⋅ x i ) + 1 ) d (3)径向基核(RBF) K ( x , x i ) = exp ( − ∥ x − x i ∥ 2 σ 2 ) Gauss径向基函数则是局部性强的核函数,其外推能力随着参数 σ 的增大而减弱。多项式形式的核函数具有良好的全局性质。局部性较差。 (4)傅里叶核 K ( x , x i ) = 1 − q 2 2 ( 1 − 2 q cos ( x − x i ) + q 2 ) (5)样条核 K ( x , x i ) = B 2 n + 1 ( x − x i ) (6)Sigmoid核函数 K ( x , x i ) = tanh ( κ ( x , x i ) − δ ) 采用Sigmoid函数作为核函数时,支持向量机实现的就是一种多层感知器神经网络,应用SVM方法,隐含层节点数目(它确定神经网络的结构)、隐含层节点对输入节点的权值都是在设计(训练)的过程中自动确定的。而且支持向量机的理论基础决定了它最终求得的是全局最优值而不是局部最小值,也保证了它对于未知样本的良好泛化能力而不会出现过学习现象。 核函数的选择 在选取核函数解决实际问题时,通常采用的方法有: 一是利用专家的先验知识预先选定核函数; 二是采用Cross-Validation方法,即在进行核函数选取时,分别试用不同的核函数,归纳误差最小的核函数就是最好的核函数.如针对傅立叶核、RBF核,结合信号处理问题中的函数回归问题,通过仿真实验,对比分析了在相同数据条件下,采用傅立叶核的SVM要比采用RBF核的SVM误差小很多. 三是采用由Smits等人提出的混合核函数方法,该方法较之前两者是目前选取核函数的主流方法,也是关于如何构造核函数的又一开创性的工作.将不同的核函数结合起来后会有更好的特性,这是混合核函数方法的基本思想

     

    八十一、SVM-点到超平面的距离

    from:https://blog.csdn.net/denghecsdn/article/details/77313758

    前提知识:已知法线的情况下,求点到平面的距离:

    d=| ( n*PA) / n | (n为法向量,P为该点,A为平面内任意一点)

    n*PA是向量的点乘

    —————————————————————————————

    样本空间中的任意一点 x,到超平面(w,b)的距离,可以表示为

                                               

            后来有同学评论说,点到超平面上的点为什么这么计算呢?我在这里再具体说一下。推导过程并不繁琐(这里以三维空间为例)。

          对于超平面A

    ,假设 x‘ 为超平面上任意一点,那么,显然满足:

                                               

     

    对于空间上任意一点 x, 到平面 A  的距离 H,等于 x 到超平面的法向量长度,也就是 向量 xx' 在垂直方向上(即法向量)上的投影。而计算投影,将 xx' 乘以法向量 w 即可。并且,我们不光要投影,还要计算单位,即使用单位为 1 的投影。也就是在分母除以 || w ||。所以,距离 H 可以表示为:

                                          

     

    又因为:

                                                   

     

    所以,距离为:

                        

     

    八十二、SVM中,高斯核为什么会把原始维度映射到无穷多维?

    from:https://blog.csdn.net/u013382288/article/details/80978456

    1)先将高斯函数泰勒展开

    2)将x和x'分离,发现它们长得一样

    3)高斯函数里藏着无限多维的转换

     

    八十三、SVM中的C和gamma

    from:https://blog.csdn.net/u013382288/article/details/80978456

    1. C

    1)C越大,越不能容忍分类误差样本存在,也就是hard-margin SVM,容易出现曲线边,容易过拟合

    2)C越小,不关心分类是否正确,而关心间隔是否够大,容易欠拟合

     

    2. gamma:gamma是选择RBF函数作为kernel后,该函数自带的一个参数。隐含地决定了数据映射到新的特征空间后的分布,

    1)gamma越大,支持向量越少,容易欠拟合

    2)gamma值越小,支持向量越多,容易过拟合

    支持向量的个数影响训练与预测的速度

     

    八十四、SVM的原问题和对偶问题

    from:https://blog.csdn.net/diligent_321/article/details/53396682

    SVM原问题

      SVM的几何意义是寻找一个最优分隔超平面,使其能把数据空间的两类点分开。记超平面方程为wTx+b=0,任意一点xi到超平面的距离公式为

    di=|wTxi+b|||w||

      所以,目标函数为

    maxw,bmini∈{1,...,N}|wTxi+b|||w||

      约束条件为

    yi(wTxi+b)>0,i∈{1,...,N}

      ,这样便可以保证所有点都被正确分类。 

      观察上述规划问题可知,将w, b同时放大或者缩小相同的倍数,不影响结果,即w, b存在多组解。为了得到唯一的一组w, b, 不妨令“函数间隔”为1,即令样本集满足

    mini∈{1,...,N}|wTxi+b|=1

      ,那么可以转化为新问题如下,

    maxw,b1||w||=minw,b12||w||2s,t    yi(wTxi+b)≥1,i∈{1,...,N}

    SVM对偶问题

      对于SVM而言,原问题

    minwθp(w)=minwmaxα,β,αi≥0L(w,α,β)

      不易求解,但由于原问题为二次规划问题,满足“strong duality”关系,故可解其对偶问题。

    maxα,β,αi≥0minwL(w,α,β)=maxα,αi≥0minw,b{12||w||2−∑i=1Nαi[yi(wTxi+b)−1]}

      求解偏导数得

    ∂L(w,α)∂w=w−∑i=1Nαiyixi∂L(w,α)∂b=−∑i=1Nαiyi

      ,若令∂L(w,α)∂w=0,∂L(w,α)∂b=0,则可解之得

    w∗=∑i=1Nαiyixi,  ∑i=1Nαiyi=0

      ,于是,对偶问题转化为

    maxα{∑i=1Nαi−12∑i,j=1Ny(i)y(j)αiαj<x(i),x(j)>}s,t  αi≥0,  i∈{1,...,N}∑i=1Nαiyi=0

      ,求解出α,则w∗,b∗也就得到了。决策方程可以表示为

    (w∗)Tx+b=(∑i=1Nαiyixi)Tx+b=∑i=1Nαiyi<xi,x>+b

      ,上式中,看上去是对所有训练样例和测试样例做内积,计算量大,其实不然,从KKT条件可知,对偶问题解出的α参数,仅support vectors的αi非零,其余全0。 

      此外,引入对偶问题,除了简化“无约束”最优化过程外,还为核函数做了铺垫,而kernel function可以将原始样本映射到高维空间,使其变得“更有可能线性可分”(根据常识,数据越稀疏越可分)

    转载于:https://www.cnblogs.com/yumoye/p/10354160.html

    展开全文
  • 【校招面经】机器学习与数据挖掘常见面试题整理 part7 2018年08月04日 21:32:43稻蛙阅读数:182 七十、势函数法 from:https://www.cnblogs.com/huadongw/p/4106290.html 势函数主要用于确定...
  • 【校招面经】机器学习与数据挖掘常见面试题整理 part4 2018年07月25日 12:43:21稻蛙阅读数:149 五十一、Hinge loss Hinge loss 的叫法来源于其损失函数的图形,为一个折线,通用的函数表达式为...
  • 【校招面经】机器学习与数据挖掘常见面试题整理 part5 2018年08月04日 15:58:45稻蛙阅读数:105 五十九、计量经济学中的平稳性 六十、高斯混合分布 1. 生成模型 2. 认为点是由多个高斯...
  • 数据挖掘笔试面试(5)

    千次阅读 2019-02-06 21:44:00
    数据挖掘笔记_16(常见面试之机器学习算法思想简单梳理)  前言:  找工作时(IT行业),除了常见的软件开发以外,机器学习岗位也可以当作是一个选择,不少计算机方向的研究生都会接触这个,如果你的研究...
  • 本文来自:http://analyticscosm.com/machine-learning-interview-questions-for-data-scientist-interview/ 希望大家...自己敲代码,跑数据,理解业务关系! The Machine Learning part of the interview is us...
  • 数据挖掘面试笔试题(附答案)

    万次阅读 多人点赞 2018-09-18 09:40:35
    1、( D )的目的缩小数据的取值范围,使其更适合于数据挖掘算法的需要,并且能够得到和原始数据相同的分析结果。 A.数据清洗 B.数据集成 C.数据变换 D.数据归约 2、某超市研究销售纪录数据后发现,买啤酒的人很...
  • 超全数据挖掘面试笔试题(附答案) 2017年09月18日 20:31:35SZU_ZNG阅读数:24700 一、单选题(共80题) ( D )的目的缩小数据的取值范围,使其更适合于数据挖掘算法的需要,并且能够得到和原始...
  • 作者:白宁超2016年10月16日13:44:06摘要:正值找工作之际,数据挖掘150道面试题涵盖很多基础知识点,如果你针对求职提前针对性准备,可以以此为为参照检查自己水平,如果你不为求职,也可以针对这些基础佐以巩固,...
  • 2015年校园招聘之腾讯(数据挖掘)笔试面试题目 笔试时间: 2014年9月20日上午10点 地址:广州大学城华南理工大学 笔试:腾讯 笔试岗位:基础研究(数据挖掘方向) 笔试内容: 1.二叉树遍历:已...
  • 百度数据挖掘工程师实习生笔试面试
  • 【校招面经】机器学习与数据挖掘常见面试题整理 part3 2018年07月25日 12:41:35稻蛙阅读数:189 四十一、请简要说说EM算法 有时候因为样本的产生和隐含变量有关(隐含变量是不能观察的),而求...
  • 数据挖掘面试题库

    2015-06-16 12:01:09
    数据挖掘面试题库, 包含了大量数据挖掘笔试面试题目。
  • 超全数据挖掘面试笔试题(附答案)

    万次阅读 多人点赞 2017-09-18 20:31:35
    ( D )的目的缩小数据的取值范围,使其更适合于数据挖掘算法的需要,并且能够得到和原始数据相同的分析结果。 A.数据清洗 B.数据集成 C.数据变换 D.数据归约 某超市研究销售纪录数据后发现,买啤酒的人很大概率...
  • ( D )的目的缩小数据的取值范围,使其更适合于数据挖掘算法的需要,并且能够得到和原始数据相同的分析结果。 A.数据清洗 B.数据集成 C.数据变换 D.数据归约 某超市研究销售纪录数据后发现,买啤酒的人很大概率...
  • Baidu数据挖掘 笔试题: 一、简答题30分 1. extern”C”{}的作用好应用场景; 2.写出两者你熟悉的设计模式,及应用场景,可以给出伪代码; 3.TCP中time_wait是表示那种状态,及应用场景,以及起好处和坏处; ...
  • ( D )的目的缩小数据的取值范围,使其更适合于数据挖掘算法的需要,并且能够得到和原始数据相同的分析结果。 A.数据清洗 B.数据集成 C.数据变换 D.数据归约 某超市研究销售纪录数据后发现,买啤酒的人很大概率也...
  • 转自: ... ...笔试题: ...1. 有一个任务执行机,任务数N,该机器每次只能执行一个任务,而任务之间存在依赖关系, ...这是今年3月份阿里招聘数据分析师实习生的笔试试题,答案仅供参考!–by wr-chow
  • 2011百度数据挖掘研发工程师实习生笔试面试题 投稿人/作者: 网络转载 发布时间:2012-04-30 11:48:45  投稿到ChinaKDD 笔试题: 一、简答题30分 1. extern”C”{}的作用好应用场景; 2.写出两者你熟悉...
  • 志愿一:数据挖掘 志愿二:大数据研发 笔试 首先,笔试的话,题目非常多,题型也很宽泛,我印象中是分了三到四个部分,每个部分都有时间限制,然后整体的话是两个小时, 第一部分主要是常规的数值计算、图形推理...
  • 转自: ...笔试题: 一、简答题30分 1. extern”C”{}的作用和应用场景;...这是今年3月份阿里招聘数据分析师实习生的笔试试题,答案仅供参考!–by wr-chow 转载于:https://blog.51cto.com/9492221/1565008
  • 美团网2016校招,笔试面试

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 146
精华内容 58
关键字:

数据挖掘笔试面试