机器学习笔记

置顶

微信关于机器学习有两个收藏,需要选择性汇总
特征选择、公式推导、调参等,公式包括FN召回率等
七月的试题,微信收藏的试题,需要解决


理解矩阵

有人说,矩阵的本质就是线性方程式,两者是一一对应关系
链接:http://www.ruanyifeng.com/blog/2015/09/matrix-multiplication.html

也有人说,矩阵的本质是运动的描述。简而言之,就是在线性空间中选定基之后,向量刻画对象,矩阵刻画对象的运动,用矩阵与向量的乘法施加运动。
链接:https://pan.baidu.com/s/1BLyrQH5_VAw832jKkCgpBA 密码:ljwq


机器学习定义

机器学习是一门从数据中研究算法的学科。就是根据已有数据,进行算法选择,并基于算法和数据建模,对未来预测。

美国卡内基梅隆大学机器学习研究领域著名教授 Tom Mitchell 对机器学习的经典定义:对于某给定的任务T,在合理的性能度量方案P的前提下,某计算机程序可以自主学习任务T的经验E; 随着提供合适、优质、大量的经验E,该程序对于任务T的性能逐步提高

其中重要的机器学习对象:任务Task T,一个或多个、经验Experience E、度量性能Performance P。
即:随着任务的不断执行,经验的累积会带来计算机性能的提升。


机器学习项目开发流程

1 抽象成数学问题
机器学习的训练过程很耗时,胡乱尝试时间成本太高,所以明确问题是进行机器学习的第一步。
抽象成数学问题,指的明确我们可以获得什么样的数据,目标问题属于分类、回归还是聚类,如果都不是,如何转换为其中的某类问题。

2 获取数据
数据决定了机器学习结果的上限,而算法只是尽可能逼近这个上限。
数据要有代表性,否则必然会过拟合。而且对于分类问题,数据偏斜不能过于严重,不同类别的数据数量不要有数个数量级的差距。
对数据的量级有一个评估,多少个样本,多少个特征,可以估算出其对内存的消耗程度,判断训练过程中内存是否能够放得下。如果放不下就得考虑改进算法或者使用一些降维的技巧了。如果数据量实在太大,那就要考虑分布式了。

3 特征预处理与特征选择
良好的数据要能够提取出良好的特征才能真正发挥效力。
特征预处理、数据清洗是很关键的步骤,往往能够使得算法的效果和性能得到显著提高。归一化、离散化、因子化、缺失值处理、去除共线性等,数据挖掘过程中很多时间就花在它们上面。这些工作简单可复制,收益稳定可预期,是机器学习的基础必备步骤。

筛选出显著特征、摒弃非显著特征,需要机器学习工程师反复理解业务。这对很多结果有决定性的影响。特征选择好了,非常简单的算法也能得出良好、稳定的结果。这需要运用特征有效性分析的相关技术,如相关系数、卡方检验、平均互信息、条件熵、后验概率、逻辑回归权重等方法。

4 训练模型与调优
直到这一步才用到我们上面说的算法进行训练。现在很多算法都能够封装成黑盒供人使用。但是真正考验水平的是调整这些算法的(超)参数,使得结果变得更加优良。这需要我们对算法的原理有深入的理解。理解越深入,就越能发现问题的症结,提出良好的调优方案。

5 模型诊断
如何确定模型调优的方向与思路呢这就需要对模型进行诊断的技术。
过拟合、欠拟合 判断是模型诊断中至关重要的一步。常见的方法如交叉验证,绘制学习曲线等。过拟合的基本调优思路是增加数据量,降低模型复杂度。欠拟合的基本调优思路是提高特征数量和质量,增加模型复杂度。

误差分析,也是机器学习至关重要的步骤。通过观察误差样本,全面分析误差产生误差的原因:是参数的问题还是算法选择的问题,是特征的问题还是数据本身的问题……
诊断后的模型需要进行调优,调优后的新模型需要重新进行诊断,这是一个反复迭代不断逼近的过程,需要不断地尝试, 进而达到最优状态。

6 模型融合
一般来说,模型融合后都能使得效果有一定提升。而且效果很好。
工程上,主要提升算法准确度的方法是分别在模型的前端(特征清洗和预处理,不同的采样模式)与后端(模型融合)上下功夫。因为他们比较标准可复制,效果比较稳定。而直接调参的工作不会很多,毕竟大量数据训练起来太慢了,而且效果难以保证。

7 上线运行
这一部分内容主要跟工程实现的相关性比较大。工程上是结果导向,模型在线上运行的效果直接决定模型的成败。 不单纯包括其准确程度、误差等情况,还包括其运行的速度(时间复杂度)、资源消耗程度(空间复杂度)、稳定性是否可接受。


有监督、无监督与半监督学习

  • 有监督学习
    对有标记的训练样本进行学习,对训练样本外的数据进行预测。
    如 LR(Logistic Regression),SVM(Support Vector Machine),RF(RandomForest),GBDT(Gradient Boosting Decision Tree),感知机(Perceptron)、BP神经网络(Back Propagation)等。

  • 无监督学习
    对未标记的样本进行训练学习,试图发现样本中的内在结构。
    如聚类(KMeans)、降维、文本处理、DL。

  • 半监督学习(Semi-Supervised Learning,SSL)
    主要考虑如何利用少量的标注样本和大量的未标注样本进行训练和分类,是有监督学习和无监督学习的结合。
    半监督学习对于减少标注代价,提高学习机器性能具有重大实际意义。


判别式模型与生成式模型

判别式模型(Discriminative Model):直接对条件概率p(y|x)进行建模,常见判别模型有:
线性回归、决策树、支持向量机SVM、k近邻、神经网络等;

生成式模型(Generative Model):对联合分布概率p(x,y)进行建模,常见生成式模型有:
隐马尔可夫模型HMM、朴素贝叶斯模型、高斯混合模型GMM、LDA等;

生成式模型更普适,判别式模型更直接,目标性更强。
生成式模型关注数据是如何产生的,寻找的是数据分布模型。
判别式模型关注的数据的差异性,寻找的是分类面。
由生成式模型可以产生判别是模型,但是由判别式模式没法形成生成式模型


各算法损失函数汇总

首先区分一个概念,损失函数针对的是单个样本,代价函数或者成本函数针对的是全体样本。
待总结。


简单说说特征工程

大部分复杂模型的算法精进都是数据科学家在做,应用型工程师主要是直接运用现有的模型与算法。而具体项目开发过程中,特征工程的时间很可能占比70%。

特征选择有很多方法,包括卡方检验,互信息,皮尔逊,TFIDF等。
其中tf-idf倾向于选择区有文档区分度的词,而卡方倾向于选择有类别区分度的词。


机器学习中,有哪些特征选择的工程方法

数据和特征决定了机器学习的上限,而模型和算法只是逼近这个上限而已

  • 计算每一个特征与响应变量的相关性
    工程上常用的手段有计算皮尔逊系数互信息系数皮尔逊系数只能衡量线性相关性,而**互信息系数能够很好地度量各种相关性,但是计算相对复杂一些,好在很多toolkit里边都包含了这个工具(如sklearn的MINE),得到相关性之后就可以排序选择特征了;

  • 构建单个特征的模型,通过模型的准确性为特征排序,借此来选择特征;

  • 通过L1正则项来选择特征
    L1正则方法具有稀疏解的特性,因此天然具备特征选择的特性,但是要注意,L1没有选到的特征不代表不重要,原因是两个具有高相关性的特征可能只保留了一个,如果要确定哪个特征重要应再通过L2正则方法交叉检验;

  • 训练能够对特征打分的预选模型
    RandomForest和Logistic Regression等都能对模型的特征打分,通过打分获得相关性后再训练最终模型;

  • 通过特征组合后再来选择特征
    如对用户id和用户特征最组合来获得较大的特征集再来选择特征,这种做法在推荐系统和广告系统中比较常见,这也是所谓亿级甚至十亿级特征的主要来源,原因是用户数据比较稀疏,组合特征能够同时兼顾全局模型和个性化模型。

  • 通过深度学习来进行特征选择
    目前这种手段正在随着深度学习的流行而成为一种手段,尤其是在计算机视觉领域,原因是深度学习具有自动学习特征的能力,这也是深度学习又叫unsupervised feature learning的原因。从深度学习模型中选择某一神经层的特征后就可以用来进行最终目标模型的训练了。


如何进行特征选择

特征选择是一个重要的数据预处理过程,主要有两个原因:一是减少特征数量、降维,使模型泛化能力更强,减少过拟合;二是增强对特征和特征值之间的理解

常见的特征选择方式:

  • 去除方差较小的特征,比如PCA
  • 正则化。1正则化能够生成稀疏的模型。L2正则化的表现更加稳定,由于有用的特征往往对应系数非零。
  • 随机森林,对于分类问题,通常采用基尼不纯度或者信息增益,对于回归问题,通常采用的是方差或者最小二乘拟合。一般不需要feature engineering、调参等繁琐的步骤。它的两个主要问题,1是重要的特征有可能得分很低(关联特征问题),2是这种方法对特征变量类别多的特征越有利(偏向问题)。
  • 稳定性选择。是一种基于二次抽样和选择算法相结合较新的方法,选择算法可以是回归、SVM或其他类似的方法。它的主要思想是在不同的数据子集和特征子集上运行特征选择算法,不断的重复,最终汇总特征选择结果,比如可以统计某个特征被认为是重要特征的频率(被选为重要特征的次数除以它所在的子集被测试的次数)。理想情况下,重要特征的得分会接近100%。稍微弱一点的特征得分会是非0的数,而最无用的特征得分将会接近于0。

你知道有哪些数据处理和特征工程的处理


数据预处理

1、特征向量的缺失值处理:
1)缺失值较多.直接将该特征舍弃掉,否则可能反倒会带入较大的noise。
2)缺失值较少,其余的特征缺失值都在10%以内,我们可以采取很多的方式来处理:

  • 把NaN直接作为一个特征,假设用0表示;
  • 连续值,用均值填充;
  • 用随机森林等算法预测填充;

2、连续值:离散化。有的模型(如决策树)需要离散值
3、对定量特征二值化。核心在于设定一个阈值,大于阈值的赋值为1,小于等于阈值的赋值为0。如图像操作
4、皮尔逊相关系数,去除高度相关的列


请简要介绍下SVM的原理和推导

SVM,全称是support vector machine,中文名叫支持向量机。SVM是一个面向数据的分类算法,它的目标是确定一个分类超平面,将不同的数据分开

此外,这里有个视频也是关于SVM的推导:《纯白板手推SVM》,链接:http://www.julyedu.com/video/play/18/429


支持向量机通俗导论(理解SVM的三层境界)

在线阅读链接:http://blog.csdn.net/v_july_v/article/details/7624837
网盘下载地址:https://pan.baidu.com/s/1htfvbzI 密码:qian
建议下载网盘里的pdf阅读,文档附带完整书签。


说说你知道的核函数

通常人们会从一些常用的核函数中选择(根据问题和数据的不同,选择不同的参数,实际上就是得到了不同的核函数),例如:
多项式核,显然刚才我们举的例子是这里多项式核的一个特例(R = 1,d = 2)。虽然比较麻烦,而且没有必要,不过这个核所对应的映射实际上是可以写出来的,该空间的维度是,其中是原始空间的维度。
高斯核,这个核就是最开始提到过的会将原始空间映射为无穷维空间的那个家伙。不过,如果选得很大的话,高次特征上的权重实际上衰减得非常快,所以实际上(数值上近似一下)相当于一个低维的子空间;反过来,如果选得很小,则可以将任意的数据映射为线性可分——当然,这并不一定是好事,因为随之而来的可能是非常严重的过拟合问题。不过,总的来说,通过调控参数,高斯核实际上具有相当高的灵活性,也是使用最广泛的核函数之一。下图所示的例子便是把低维线性不可分的数据通过高斯核函数映射到了高维空间:

线性核,这实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了(意思是说,咱们有的时候,写代码,或写公式的时候,只要写个模板或通用表达式,然后再代入不同的核,便可以了,于此,便在形式上统一了起来,不用再分别写一个线性的,和一个非线性的)。


带核的SVM为什么能分类非线性问题

核函数的本质是两个函数的內积,通过核函数,SVM将低维数据隐射到高维空间,在高维空间,非线性问题转化为线性问题, SVM得到的超平面是高维空间的线性分类平面, 如图:

其分类结果也视为低维空间的非线性分类结果, 因而带核的SVM就能分类非线性问题。


在k-means或kNN,我们是用欧氏距离来计算最近的邻居之间的距离。为什么不用曼哈顿距离

闵可夫斯基距离(Minkowski)
(1)当p为1的时候是曼哈顿距离(Manhattan)(城市街区距离)
(2)当p为2的时候是欧式距离(Euclidean)(又称欧几里得度量,最常见的两点之间或多点之间的距离表示法)
(3)当p为无穷大的时候是切比雪夫距离(Chebyshev)

不用曼哈顿距离,因为它只计算水平或垂直距离,有维度的限制。而欧氏距离可用于任何空间的距离计算。因为数据点可以存在于任何空间,所以欧氏距离是更可行的选择。

欧氏距离也有明显的缺点。它将样本不同属性(即各指标或各变量量纲)之间的差别等同看待,这一点有时不能满足实际要求。

曼哈顿距离和欧式距离一般用途不同,无相互替代性。


逻辑回归公式推导


http://blog.csdn.net/oldbai001/article/details/49872433
http://blog.csdn.net/programmer_wei/article/details/52072939


过拟合?欠拟合?

欠拟合:算法不太符合样本的数据特征
过拟合:算法太符合样本的数据特征,对实际生产中的数据特征却无法拟合

过拟合(overfitting)具体现象体现为,随着训练过程的进行,模型复杂度增加,在训练集上的错误率渐渐减小,但是在验证集上的错误率却渐渐增大。

特征过多,特征数量级过大,训练数据过少,都可能导致过度拟合。过拟合会让模型泛化能力变差。


防止过拟合的方法

降低过拟合的办法一般如下:

  • 特征选择/特征降维:特征过多或者过复杂都会导致过拟合

  • 数据集扩增:原有数据增加、原有数据加随机噪声、重采样

  • 交叉验证

  • 正则化(Regularization)

    • L2正则化:目标函数中增加所有权重w参数的平方之和, 逼迫所有w尽可能趋向零但不为零. 因为过拟合的时候, 拟合函数需要顾忌每一个点, 最终形成的拟合函数波动很大, 在某些很小的区间里, 函数值的变化很剧烈, 也就是某些w非常大. 为此, L2正则化的加入就惩罚了权重变大的趋势.
    • L1正则化:目标函数中增加所有权重w参数的绝对值之和, 逼迫更多w为零(也就是变稀疏. L2因为其导数也趋0, 奔向零的速度不如L1给力了). 大家对稀疏规则化趋之若鹜的一个关键原因在于它能实现特征的自动选择。一般来说,xi的大部分元素(也就是特征)都是和最终的输出yi没有关系或者不提供任何信息的,在最小化目标函数的时候考虑xi这些额外的特征,虽然可以获得更小的训练误差,但在预测新的样本时,这些没用的特征权重反而会被考虑,从而干扰了对正确yi的预测。稀疏规则化算子的引入就是为了完成特征自动选择的光荣使命,它会学习地去掉这些无用的特征,也就是把这些特征对应的权重置为0。
  • 随机失活(dropout)
    在训练的运行的时候,让神经元以超参数p的概率被激活(也就是1-p的概率被设置为0), 每个w因此随机参与, 使得任意w都不是不可或缺的, 效果类似于数量巨大的模型集成。

  • 逐层归一化(batch normalization)
    这个方法给每层的输出都做一次归一化(网络上相当于加了一个线性变换层), 使得下一层的输入接近高斯分布. 这个方法相当于下一层的w训练时避免了其输入以偏概全, 因而泛化效果非常好.

  • 提前终止(early stopping)
    理论上可能的局部极小值数量随参数的数量呈指数增长, 到达某个精确的最小值是不良泛化的一个来源. 实践表明, 追求细粒度极小值具有较高的泛化误差。这是直观的,因为我们通常会希望我们的误差函数是平滑的, 精确的最小值处所见相应误差曲面具有高度不规则性, 而我们的泛化要求减少精确度去获得平滑最小值, 所以很多训练方法都提出了提前终止策略. 典型的方法是根据交叉叉验证提前终止: 若每次训练前, 将训练数据划分为若干份, 取一份为测试集, 其他为训练集, 每次训练完立即拿此次选中的测试集自测. 因为每份都有一次机会当测试集, 所以此方法称之为交叉验证. 交叉验证的错误率最小时可以认为泛化性能最好, 这时候训练错误率虽然还在继续下降, 但也得终止继续训练了.


kmeans的复杂度

时间复杂度:O(tKmn),其中,t为迭代次数,K为簇的数目,m为记录数,n为维数
空间复杂度:O((m+K)n),其中,K为簇的数目,m为记录数,n为维数


对所有优化问题来说, 有没有可能找到比現在已知算法更好的算法

没有免费的午餐定理:

  • 对于训练样本(黑点),不同的算法A/B在不同的测试样本(白点)中有不同的表现,这表示:对于一个学习算法A,若它在某些问题上比学习算法 B更好,则必然存在一些问题,在那里B比A好。
  • 也就是说:对于所有问题,无论学习算法A多聪明,学习算法 B多笨拙,它们的期望性能相同。
  • 但是:没有免费午餐定力假设所有问题出现几率相同,实际应用中,不同的场景,会有不同的问题分布,所以,在优化算法时,针对具体问题进行分析,是算法优化的核心所在。

请问(决策树、Random Forest、Booting、Adaboot)GBDT和XGBoost的区别是什么

集成学习的集成对象是学习器. Bagging和Boosting属于集成学习的两类方法. Bagging方法有放回地采样同数量样本训练每个学习器, 然后再一起集成(简单投票); Boosting方法使用全部样本(可调权重)依次训练每个学习器, 迭代集成(平滑加权).
决策树属于最常用的学习器, 其学习过程是从根建立树, 也就是如何决策叶子节点分裂. ID3/C4.5决策树用信息熵计算最优分裂, CART决策树用基尼指数计算最优分裂, xgboost决策树使用二阶泰勒展开系数计算最优分裂.
下面所提到的学习器都是决策树:
Bagging方法:
学习器间不存在强依赖关系, 学习器可并行训练生成, 集成方式一般为投票;
Random Forest属于Bagging的代表, 放回抽样, 每个学习器随机选择部分特征去优化;
Boosting方法:
学习器之间存在强依赖关系、必须串行生成, 集成方式为加权和;
Adaboost属于Boosting, 采用指数损失函数替代原本分类任务的0/1损失函数;
GBDT属于Boosting的优秀代表, 对函数残差近似值进行梯度下降, 用CART回归树做学习器, 集成为回归模型;
xgboost属于Boosting的集大成者, 对函数残差近似值进行梯度下降, 迭代时利用了二阶梯度信息, 集成模型可分类也可回归. 由于它可在特征粒度上并行计算, 结构风险和工程实现都做了很多优化, 泛化, 性能和扩展性都比GBDT要好。
关于决策树,这里有篇《决策树算法》(链接:http://blog.csdn.net/v_july_v/article/details/7577684)。而随机森林Random Forest是一个包含多个决策树的分类器。至于AdaBoost,则是英文”Adaptive Boosting”(自适应增强)的缩写,关于AdaBoost可以看下这篇文章《Adaboost 算法的原理与推导》。GBDT(Gradient Boosting Decision Tree),即梯度上升决策树算法,相当于融合决策树和梯度上升boosting算法。

xgboost类似于gbdt的优化版,不论是精度还是效率上都有了提升。与gbdt相比,具体的优点有:
1.损失函数是用泰勒展式二项逼近,而不是像gbdt里的就是一阶导数
2.对树的结构进行了正则化约束,防止模型过度复杂,降低了过拟合的可能性
3.节点分裂的方式不同,gbdt是用的gini系数,xgboost是经过优化推导后的


说说常见的损失函数

对于给定的输入X,由f(X)给出相应的输出Y,这个输出的预测值f(X)与真实值Y可能一致也可能不一致(要知道,有时损失或误差是不可避免的),用一个损失函数来度量预测错误的程度。损失函数记为L(Y, f(X))。

常用的损失函数有以下几种(基本引用自《统计学习方法》):

如此,SVM有第二种理解,即最优化+损失最小,或如@夏粉_百度所说“可从损失函数和优化算法角度看SVM,boosting,LR等算法,可能会有不同收获”。

关于SVM的更多理解请参考:,链接:


协方差和相关性有什么区别

相关性是协方差的标准化格式。协方差本身很难做比较。例如:如果我们计算工资($)和年龄(岁)的协方差,因为这两个变量有不同的度量,所以我们会得到不能做比较的不同的协方差。

为了解决这个问题,我们计算相关性来得到一个介于-1和1之间的值,就可以忽略它们各自不同的度量。


谈谈判别式模型和生成式模型

判别方法:由数据直接学习决策函数 Y = f(X),或者由条件分布概率 P(Y|X)作为预测模型,即判别模型。
生成方法:由数据学习联合概率密度分布函数 P(X,Y),然后求出条件概率分布P(Y|X)作为预测的模型,即生成模型。
由生成模型可以得到判别模型,但由判别模型得不到生成模型。
常见的判别模型有:K近邻、SVM、决策树、感知机、线性判别分析(LDA)、线性回归、传统的神经网络、逻辑斯蒂回归、boosting、条件随机场
常见的生成模型有:朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型(LDA)、限制玻尔兹曼机


线性分类器与非线性分类器的区别以及优劣

线性和非线性是针对,模型参数和输入特征来讲的;比如输入x,模型y=ax+ax^2那么就是非线性模型,如果输入是x和X^2则模型是线性的。
线性分类器可解释性好,计算复杂度较低,不足之处是模型的拟合效果相对弱些。
非线性分类器效果拟合能力较强,不足之处是数据量不足容易过拟合、计算复杂度高、可解释性不好。
常见的线性分类器有:LR,贝叶斯分类,单层感知机、线性回归
常见的非线性分类器:决策树、RF、GBDT、多层感知机
SVM两种都有(看线性核还是高斯核)


当你用搜索引擎搜索一个不正确的单词时,系统会猜测你的意图,并提示你相关的正确单词,这叫做拼写检查。请问如何用贝叶斯算法实现拼写检查


为什么朴素贝叶斯如此“朴素”

朴素贝叶斯模型(Naive Bayesian Model)的朴素(Naive)的含义是很简单地假设样本特征彼此独立. 这个假设现实中基本上不存在, 但特征相关性很小的实际情况还是很多的, 所以这个模型仍然能够工作得很好。


请大致对比下plsa和LDA的区别



更多请参见:《通俗理解LDA主题模型》(链接:http://blog.csdn.net/v_july_v/article/details/41209515)。


请简要说说EM算法



本题解析来源:@tornadomeet,链接:http://www.cnblogs.com/tornadomeet/p/3395593.html


KNN中的K如何选取的

关于什么是KNN,可以查看此文:《从K近邻算法、距离度量谈到KD树、SIFT+BBF算法》(链接:http://blog.csdn.net/v_july_v/article/details/8203674)。KNN中的K值选取对K近邻算法的结果会产生重大影响。如李航博士的一书「统计学习方法」上所说:

如果选择较小的K值,就相当于用较小的领域中的训练实例进行预测,“学习”近似误差会减小,只有与输入实例较近或相似的训练实例才会对预测结果起作用,与此同时带来的问题是“学习”的估计误差会增大,换句话说,K值的减小就意味着整体模型变得复杂,容易发生过拟合;
如果选择较大的K值,就相当于用较大领域中的训练实例进行预测,其优点是可以减少学习的估计误差,但缺点是学习的近似误差会增大。这时候,与输入实例较远(不相似的)训练实例也会对预测器作用,使预测发生错误,且K值的增大就意味着整体的模型变得简单。
K=N,则完全不足取,因为此时无论输入实例是什么,都只是简单的预测它属于在训练实例中最多的累,模型过于简单,忽略了训练实例中大量有用信息。

在实际应用中,K值一般取一个比较小的数值,例如采用交叉验证法(简单来说,就是一部分样本做训练集,一部分做测试集)来选择最优的K值。


什么最小二乘法


对了,最小二乘法跟SVM有什么联系呢请参见《支持向量机通俗导论(理解SVM的三层境界)》(链接:http://blog.csdn.net/v_july_v/article/details/7624837)。


简单说说贝叶斯定理


所以,贝叶斯公式可以直接根据条件概率的定义直接推出。即因为P(A,B) = P(A)P(B|A) = P(B)P(A|B),所以P(A|B) = P(A)P(B|A) / P(B)。


优化Kmeans

Kmeans总结:
https://www.processon.com/view/link/5ad81e5be4b046910642bc4b

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


KMeans初始类簇中心点的选取。

k-means++算法选择初始seeds的基本思想就是:初始的聚类中心之间的相互距离要尽可能的远。

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

解释对偶的概念

一个优化问题可以从两个角度进行考察,一个是primal 问题,一个是dual 问题,就是对偶问题,一般情况下对偶问题给出主问题最优值的下界,在强对偶性成立的情况下由对偶问题可以得到主问题的最优下界,对偶问题是凸优化问题,可以进行较好的求解,SVM中就是将primal问题转换为dual问题进行求解,从而进一步引入核函数的思想。


机器学习和统计里面的auc的物理意义是啥

解析链接:https://www.zhihu.com/question/39840928


观察增益gain, alpha和gamma越大,增益越小

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

第一项是假设分割的左孩子的权重分数, 第二项为右孩子, 第三项为不分割总体分数, 最后一项为引入一个节点的复杂度损失
由公式可知, gama越大gain越小, lamda越大, gain可能小也可能大.
原问题是alpha而不是lambda, 这里paper上没有提到, xgboost实现上有这个参数. 上面是我从paper上理解的答案,下面是搜索到的:
https://zhidao.baidu.com/question/2121727290086699747.html?fr=iks&word=xgboost+lamda&ie=gbk
lambda[默认1]权重的L2正则化项。(和Ridge regression类似)。 这个参数是用来控制XGBoost的正则化部分的。虽然大部分数据科学家很少用到这个参数,但是这个参数在减少过拟合上还是可以挖掘出更多用处的。11、alpha[默认1]权重的L1正则化项。(和Lasso regression类似)。 可以应用在很高维度的情况下,使得算法的速度更快。
gamma[默认0]在节点分裂时,只有分裂后损失函数的值下降了,才会分裂这个节点。Gamma指定了节点分裂所需的最小损失函数下降值。 这个参数的值越大,算法越保守。


数据不平衡问题

  • 采样,对小样本加噪声采样,对大样本进行下采样
  • 数据生成,利用已知样本生成新的样本
  • 进行特殊的加权,如在Adaboost中或者SVM中
  • 采用对不平衡数据集不敏感的算法
  • 改变评价标准:用AUC/ROC来进行评价
  • 采用Bagging/Boosting/ensemble等方法
  • 在设计模型的时候考虑数据的先验分布

图片数据增强(Data augmentation):

  • 水平翻转
  • 随机裁剪
  • 样本不平衡, 进行 Label shuffle
  • 其他
    平移变换;
    旋转/仿射变换;
    高斯噪声、模糊处理
    对颜色的数据增强:图像亮度、饱和度、对比度变化

特征比数据量还大时,选择什么样的分类器

线性分类器,因为维度高的时候,数据一般在维度空间里面会比较稀疏,很有可能线性可分。


常见的分类算法有哪些

SVM、神经网络、随机森林、逻辑回归、KNN、贝叶斯


说说常见的优化算法及其优缺点

温馨提示:在回答面试官的问题的时候,往往将问题往大的方面去回答,这样不会陷于小的技术上死磕,最后很容易把自己嗑死了。
简言之
1)随机梯度下降
优点:可以一定程度上解决局部最优解的问题
缺点:收敛速度较慢
2)批量梯度下降
优点:容易陷入局部最优解
缺点:收敛速度较快
3)mini_batch梯度下降
综合随机梯度下降和批量梯度下降的优缺点,提取的一个中和的方法。
4)牛顿法
牛顿法在迭代的时候,需要计算Hessian矩阵,当维度较高的时候,计算 Hessian矩阵比较困难。
5)拟牛顿法
拟牛顿法是为了改进牛顿法在迭代过程中,计算Hessian矩阵而提取的算法,它采用的方式是通过逼近Hessian的方式来进行求解。

具体而言
从每个batch的数据来区分
梯度下降:每次使用全部数据集进行训练
优点:得到的是最优解
缺点:运行速度慢,内存可能不够
随机梯度下降:每次使用一个数据进行训练
优点:训练速度快,无内存问题
缺点:容易震荡,可能达不到最优解
Mini-batch梯度下降
优点:训练速度快,无内存问题,震荡较少
缺点:可能达不到最优解

从优化方法上来分:
随机梯度下降(SGD)
缺点
选择合适的learning rate比较难
对于所有的参数使用同样的learning rate
容易收敛到局部最优
可能困在saddle point
SGD+Momentum
优点:
积累动量,加速训练
局部极值附近震荡时,由于动量,跳出陷阱
梯度方向发生变化时,动量缓解动荡。
Nesterov Mementum
与Mementum类似,优点:
避免前进太快
提高灵敏度
AdaGrad
优点:
控制学习率,每一个分量有各自不同的学习率
适合稀疏数据
缺点
依赖一个全局学习率
学习率设置太大,其影响过于敏感
后期,调整学习率的分母积累的太大,导致学习率很低,提前结束训练。
RMSProp
优点:
解决了后期提前结束的问题。
缺点:
依然依赖全局学习率
Adam
Adagrad和RMSProp的合体
优点:
结合了Adagrad善于处理稀疏梯度和RMSprop善于处理非平稳目标的优点
为不同的参数计算不同的自适应学习率
也适用于大多非凸优化 - 适用于大数据集和高维空间
牛顿法
牛顿法在迭代的时候,需要计算Hessian矩阵,当维度较高的时候,计算 Hessian矩阵比较困难
拟牛顿法
拟牛顿法是为了改进牛顿法在迭代过程中,计算Hessian矩阵而提取的算法,它采用的方式是通过逼近Hessian的方式来进行求解。


机器学习中,为何要经常对数据做归一化

  • 归一化后加快了梯度下降求最优解的速度
  • 归一化有可能提高精度。

如上图所示,蓝色的圈圈图代表的是两个特征的等高线。其中左图两个特征X1和X2的区间相差非常大,X1区间是[0,2000],X2区间是[1,5],其所形成的等高线非常尖。当使用梯度下降法寻求最优解时,很有可能走“之字型”路线(垂直等高线走),从而导致需要迭代很多次才能收敛;

而右图对两个原始特征进行了归一化,其对应的等高线显得很圆,在梯度下降进行求解时能较快的收敛(消除了量纲的影响)。

至于为什么能提高精度,比如一些分类器需要计算样本之间的距离(如欧氏距离),例如KNN。如果一个特征值域范围非常大,那么距离计算就主要取决于这个特征,从而与实际情况相悖(比如这时实际情况是值域范围小的特征更重要)。


特征向量的归一化方法有哪些

  • 线性归一化(Min-Max Normalization),表达式如下:
    也称为离差标准化,是对原始数据的线性变换,使结果值映射到[0 - 1]之间
    y=(x-MinValue)/(MaxValue-MinValue)
    这种归一化方法比较适用在数值比较集中的情况。这种方法有个缺陷,如果max和min不稳定,很容易使得归一化结果不稳定,使得后续使用效果也不稳定。实际使用中可以用经验常量值来替代max和min。

  • Z-score标准化,减去均值,除以方差:
    经过处理的数据符合标准正态分布,即均值为0,标准差为1,其转化函数为
    y=(x-means)/ variance

  • 非线性归一化。经常用在数据分化比较大的场景,有些数值很大,有些很小。通过一些数学函数,将原始值进行映射。该方法包括 log、指数,正切等。需要根据数据分布的情况,决定非线性函数的曲线,比如log(V, 2)还是log(V, 10)等。

    • 对数函数转换,表达式如下: y=log10 (x)
    • 反余切函数转换 ,表达式如下: y=arctan(x)*2/PI

哪些机器学习算法不需要做归一化处理

概率模型不需要归一化,因为它们不关心变量的值,而是关心变量的分布和变量之间的条件概率,树形结构就属于概率模型,如决策树、rf。

而像adaboost、svm、lr、KNN、KMeans之类的最优化问题就需要归一化。

归一化和标准化主要是为了使计算更方便,加快求解最优解的速度。比如两个变量的量纲不同,可能一个的数值远大于另一个,那么他们同时作为变量的时候,可能会造成数值计算问题,比如说求矩阵的逆可能很不精确,或者梯度下降法的收敛比较困难,还有如果需要计算欧式距离的话可能,量纲也需要调整。


对于树形结构为什么不需要归一化

数值缩放,不影响分裂点位置。因为第一步都是按照特征值进行排序的,排序的顺序不变,那么所属的分支以及分裂点就不会有不同。

对于线性模型,比如说LR,我有两个特征,一个是(0,1)的,一个是(0,10000)的,这样运用梯度下降时候,损失等高线是一个椭圆的形状,这样我想迭代到最优点,就需要很多次迭代,但是如果进行了归一化,那么等高线就是圆形的,那么SGD就会往原点迭代,需要的迭代次数较少。

另外,注意树模型是不能进行梯度下降的,因为树模型是阶跃的,阶跃点是不可导的,并且求导没意义,所以树模型(回归树)寻找最优点事通过寻找最优分裂点完成的。


标准化与归一化的区别

简单来说,归一化是依照特征矩阵的行处理数据,其目的在于样本向量在点乘运算或其他核函数计算相似性时,拥有统一的标准,也就是说都转化为“单位向量”。

标准化是依照特征矩阵的列处理数据,其通过求z-score的方法,将样本的特征值转换到同一量纲下。


模型评估指标

有时候为了更好更快的评估模型,我们需要设置评估指标。常见的评估指标有:准确率/召回率/精准率/F值
1)准确率(Accuracy) = 预测正确的样本数/总样本数
2)召回率(Recall) = 预测为正确的正例样本数/样本中的全部正例样本数
3)精准率(Precision) = 预测为正确的正例样本数/预测为正例的样本数
4)F值 = PrecisionRecall2 / (Precision+Recall) (即F值为正确率和召回率的调和平均值)


ROC与AUC

对于分类器,或者说分类算法,评价指标主要有精准率(Precision),召回率(Recall),F-score1,以及现在所说的ROC和AUC。
ROC、AUC相比准确率、召回率、F-score这样的评价指标,有这样一个很好的特性当测试集中正负样本的分布变化的时候,ROC曲线能够保持不变。在实际的数据集中经常会出现类不平衡(class imbalance)现象,即负样本比正样本多很多(或者相反),而且测试数据中的正负样本的分布也可能随着时间变化。

ROC曲线的纵轴是“真正例率”(True Positive Rate 简称TPR),横轴是“假正例率” (False Positive Rate 简称FPR)。
ROC曲线反映了FPR与TPR之间权衡的情况,通俗地来说,即在TPR随着FPR递增的情况下,谁增长得更快,快多少的问题。TPR增长得越快,曲线越往上屈,AUC就越大,反映了模型的分类性能就越好。当正负样本不平衡时,这种模型评价方式比起一般的精确度评价方式的好处尤其显著。

AUC(Area Under Curve)被定义为ROC曲线下的面积,显然这个面积的数值不会大于1。又由于ROC曲线一般都处于y=x这条直线的上方,所以AUC的取值范围在0.5和1之间。使用AUC值作为评价标准是因为很多时候ROC曲线并不能清晰的说明哪个分类器的效果更好,而AUC作为数值可以直观的评价分类器的好坏,值越大越好。
1)AUC = 1,是完美分类器,采用这个预测模型时,不管设定什么阈值都能得出完美预测。绝大多数预测的场合,不存在完美分类器。
2)0.5 < AUC < 1,优于随机猜测。这个分类器(模型)妥善设定阈值的话,能有预测价值。
3)AUC = 0.5,跟随机猜测一样(例:丢铜板),模型没有预测价值。
4)AUC < 0.5,比随机猜测还差;但只要总是反预测而行,就优于随机猜测。

至于ROC曲线具体是如何画出来的,这里推荐一篇文章:ROC和AUC介绍以及如何计算AUC

机器学习和统计里面的auc怎么理解?为什么比accuracy更常用?


常见的目标损失函数


除了MSE,还有哪些模型效果判断方法?区别是什么

  • SSE(The sum of squares due to error)
    和方差、误差平方和。计算的是拟合数据和原始数据对应点的误差的平方和,越趋近于0表示模型越拟合训练数据。
    $$SSE=\sum_{t=1}^{N}(observed_t-predicted_t)^2 $$

  • MSE(Mean squared error):
    均方差、均方误差、方差。计算的是预测数据和原始数据对应点误差的平方和的均值,越趋近于0表示模型越拟合训练数据。
    $$MSE=\frac{1}{N}\sum_{t=1}^{N}(observed_t-predicted_t)^2 $$

  • RMSE(Root mean squared error):
    均方根,也叫回归系统的拟合标准差,是MSE的平方根
    $$RMSE=\sqrt{\frac{1}{N}\sum_{t=1}^{N}(observed_t-predicted_t)^2}$$

  • MAE(Mean Absolute Error):
    平均绝对误差是绝对误差的平均值。平均绝对误差能更好地反映预测值误差的实际情况.
    $$MAE={\frac{1}{N}\sum_{i=1}^{N}\lvert(observed_t-predicted_t)\rvert}$$

  • SD(standard Deviation):
    标准差是方差的算术平方根。标准差能反映一个数据集的离散程度。平均数相同的两组组数据,标准差未必相同。
    $$SD=\sqrt{\frac{1}{N}\sum_{i=1}^{N}(x_i-u)^2}$$

  • $R^2$ :取值范围(负无穷,1],值越大表示模型越拟合训练数据;最优解是1;
    当模型预测为随机值的时候,有可能为负;若预测值恒为样本期望,$R^2$ 为0

  • TSS(Total Sum of Squares):总平方和,TSS表示样本之间的差异情况,是伪方差的m倍

  • RSS(Residual Sum of Squares):残差平方和,RSS表示预测值和样本值之间的差异情况,是MSE的m倍


试证明样本空间任意点x到超平面(w,b)的距离为(6.2)


请说说常用核函数及核函数的条件


什么是共线性, 跟过拟合有什么关联

共线性:多变量线性回归中,变量之间由于存在高度相关关系而使回归估计不准确。
共线性会造成冗余,导致过拟合。
解决方法:排除变量的相关性/加入权重正则。

本题解析来源:@抽象猴,链接:https://www.zhihu.com/question/41233373/answer/145404190


用贝叶斯机率说明Dropout的原理

回想一下使用Bagging学习,我们定义 k 个不同的模型,从训练集有替换采样 构造 k 个不同的数据集,然后在训练集上训练模型 i。

Dropout的目标是在指数 级数量的神经网络上近似这个过程。Dropout训练与Bagging训练不太一样。在Bagging的情况下,所有模型是独立 的。

在Dropout的情况下,模型是共享参数的,其中每个模型继承的父神经网络参 数的不同子集。参数共享使得在有限可用的内存下代表指数数量的模型变得可能。 在Bagging的情况下,每一个模型在其相应训练集上训练到收敛。
在Dropout的情况下,通常大部分模型都没有显式地被训练,通常该模型很大,以致到宇宙毁灭都不 能采样所有可能的子网络。取而代之的是,可能的子网络的一小部分训练单个步骤,参数共享导致剩余的子网络能有好的参数设定。

http://bi.dataguru.cn/article-10459-1.html


对于维度极低的特征,选择线性还是非线性分类器

非线性分类器,低维空间可能很多特征都跑到一起了,导致线性不可分。

  1. 如果Feature的数量很大,跟样本数量差不多,这时候选用LR或者是Linear Kernel的SVM
  2. 如果Feature的数量比较小,样本数量一般,不算大也不算小,选用SVM+Gaussian Kernel
  3. 如果Feature的数量比较小,而样本数量很多,需要手工添加一些feature变成第一种情况。

什么是ill-condition病态问题

训练完的模型,测试样本稍作修改就会得到差别很大的结果,就是病态问题,模型对未知数据的预测能力很差,即泛化误差大。


简述KNN最近邻分类算法的过程

  1. 计算训练样本和测试样本中每个样本点的距离(常见的距离度量有欧式距离,马氏距离等);
  2. 对上面所有的距离值进行排序;
  3. 选前k个最小距离的样本;
  4. 根据这k个样本的标签进行投票,得到最后的分类类别;

常用的聚类划分方式有哪些列举代表算法。

  1. 基于划分的聚类:K-means,k-medoids,CLARANS。
  2. 基于层次的聚类:AGNES(自底向上),DIANA(自上向下)。
  3. 基于密度的聚类:DBSACN,OPTICS,BIRCH(CF-Tree),CURE。
  4. 基于网格的方法:STING,WaveCluster。
  5. 基于模型的聚类:EM,SOM,COBWEB。

LR和SVM的联系与区别

联系:
1、LR和SVM都可以处理分类问题,且一般都用于处理线性二分类问题(在改进的情况下可以处理多分类问题)
2、两个方法都可以增加不同的正则化项,如l1、l2等等。所以在很多实验中,两种算法的结果是很接近的。
区别:
1、LR是参数模型,SVM是非参数模型。
2、从目标函数来看,区别在于逻辑回归采用的是logistical loss,SVM采用的是hinge loss,这两个损失函数的目的都是增加对分类影响较大的数据点的权重,减少与分类关系较小的数据点的权重。
3、SVM的处理方法是只考虑support vectors,也就是和分类最相关的少数点,去学习分类器。而逻辑回归通过非线性映射,大大减小了离分类平面较远的点的权重,相对提升了与分类最相关的数据点的权重。
4、逻辑回归相对来说模型更简单,好理解,特别是大规模线性分类时比较方便。而SVM的理解和优化相对来说复杂一些,SVM转化为对偶问题后,分类只需要计算与少数几个支持向量的距离,这个在进行复杂核函数计算时优势很明显,能够大大简化模型和计算。
5、logic 能做的 svm能做,但可能在准确率上有问题,svm能做的logic有的做不了。
本题解析来源:@朝阳在望http://blog.csdn.net/timcompp/article/details/62237986


SVM、LR、决策树的对比

  • 模型复杂度:SVM支持核函数,可处理线性非线性问题; LR模型简单,训练速度快,适合处理线性问题; 决策树容易过拟合,需要进行剪枝.
  • 损失函数:SVM hinge loss; LR L2正则化; adaboost 指数损失
  • 数据敏感度:SVM添加容忍度对outlier不敏感,只关心支持向量,且需要先做归一化; LR对远点敏感
  • 数据量:数据量大就用LR,数据量小且特征少就用SVM非线性核

请比较下EM算法、HMM、CRF

这三个放在一起不是很恰当,但是有互相有关联,所以就放在这里一起说了。注意重点关注算法的思想。
(1)EM算法
  EM算法是用于含有隐变量模型的极大似然估计或者极大后验估计,有两步组成:E步,求期望(expectation);M步,求极大(maxmization)。本质上EM算法还是一个迭代算法,通过不断用上一代参数对隐变量的估计来对当前变量进行计算,直到收敛。
  注意:EM算法是对初值敏感的,而且EM是不断求解下界的极大化逼近求解对数似然函数的极大化的算法,也就是说EM算法不能保证找到全局最优值。对于EM的导出方法也应该掌握。
(2)HMM算法
  隐马尔可夫模型是用于标注问题的生成模型。有几个参数(π,A,B):初始状态概率向量π,状态转移矩阵A,观测概率矩阵B。称为马尔科夫模型的三要素。
马尔科夫三个基本问题:
概率计算问题:给定模型和观测序列,计算模型下观测序列输出的概率。–》前向后向算法
学习问题:已知观测序列,估计模型参数,即用极大似然估计来估计参数。–》Baum-Welch(也就是EM算法)和极大似然估计。
预测问题:已知模型和观测序列,求解对应的状态序列。–》近似算法(贪心算法)和维比特算法(动态规划求最优路径)
(3)条件随机场CRF
  给定一组输入随机变量的条件下另一组输出随机变量的条件概率分布密度。条件随机场假设输出变量构成马尔科夫随机场,而我们平时看到的大多是线性链条随机场,也就是由输入对输出进行预测的判别模型。求解方法为极大似然估计或正则化的极大似然估计。
  之所以总把HMM和CRF进行比较,主要是因为CRF和HMM都利用了图的知识,但是CRF利用的是马尔科夫随机场(无向图),而HMM的基础是贝叶斯网络(有向图)。而且CRF也有:概率计算问题、学习问题和预测问题。大致计算方法和HMM类似,只不过不需要EM算法进行学习问题。
(4)HMM和CRF对比
  其根本还是在于基本的理念不同,一个是生成模型,一个是判别模型,这也就导致了求解方式的不同。


RF与GBDT之间的区别与联系

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