本章我们简要介绍下机器学习（Machine Learning）的基本概念。主要介绍机器学习算法的应用，监督学习和无监督学习（supervised-unsupervised learning）的应用场景，训练和测试数据的用法，学习效果评估方式。最后，对scikit-learn进行一些简单的介绍。

自计算机问世以来，计算机可以学习和模仿人类智慧的观点，可谓“引无数英雄竞折腰”。像Arthur C. Clarke的HAL（Heuristically programmed ALgorithmic computer）和Isaac Asimov的Sonny那样的人工智能已经成为共识，通过学习经验获得新知识和技能的软件程序也变得越来越多。我们用这机器学习程序发现我们会喜欢的新音乐，快速找出我们想网购的鞋子。机器学习程序让我们通过命令控制手机，让恒温器自动调节温度。比人类更准确的识别出潦草的手写邮箱地址，更安全的保护信用卡防止诈骗。从新药品调查到从网页寻找头条新闻，机器学习软件逐渐成为许多产业的核心工具。机器学习已经进入长期以来一直被认为只有人类才能胜任的领域，如杜克大学UNC(Duke)篮球队输给了北卡（UNC）的体育报道。

机器学习是设计和研究能够根据过去的经验来为未来做决策的软件，它是通过数据进行研究的程序。机器学习的基础是归纳（generalize），就是从已知案例数据中找出未知的规律。机器学习的典型案例就是垃圾邮件过滤。通过对数千份已经打上是否为垃圾标签的邮件进行观察经验，对新邮件进行过滤。

人工智能研究领域的计算机科学家Arthur Samuel说，机器学习是“研究如何让计算机可以不需要明确的程序也能具有学习能力”。在20世纪五六十年代，Samuel开发了下象棋程序。程序的规则非常简单，要打败专业对手需要复杂的策略，但是通过几千局游戏的训练，程序学会了复杂的策略，可以打败很多人类棋手。

计算机科学家Tom Mitchell对机器学习的定义更正式，“一个程序在完成任务T后获得了经验E，其表现为效果P，如果它完成任务T的效果是P ，那么会获得经验E”。例如，假设你有一些图片，每个图片里是一条狗或一只猫。程序可以通过观察图片来学习，然后它可以通过计算图片正确分类比例来评估学习效果。

我们将使用Mitchell的定义来组织这一章的内容。首先，我们要介绍经验的类型，包括监督学习和无监督学习。然后，我们介绍机器学习系统可以处理的常见任务。最后，我们介绍机器学习系统效果评估方式。

从经验中学习

机器学习系统通常被看作是有无人类监督学习两种方式。监督学习问题是，从成对的已经标记好的输入和输出经验数据作为一个输入进行学习，用来预测输出结果，是从有正确答案的例子中学习。而无监督学习是程序不能从已经标记好的数据中学习。它需要在数据中发现一些规律。假如我们获取了人的身高和体重数据，非监督学习的例子就是把数据点分成组别。一种程序可能是把数据分成男人与女人，儿童与成人等不同组别。

再假设数据都标记了人的性别。那么，一种监督学习方式就是基于一个人的身高和体重数据来预测这个人是男是女。后面我们会介绍监督学习与非监督学习的算法和案例。

监督学习与非监督学习可以看作机器学习的两端。还有一些中间类型，称为半监督学习，既包含监督数据也有非监督数据，这类问题可以看作是介于监督学习与非监督学习之间的学习。半监督机器学习案例是一种增强学习(Reinforcement Learning)，问题可以通过决策来获得反馈，但是反馈与某一个决策可能没有直接关系。例如，一个增强学习程序学习玩超级玛丽游戏，让它完成一级或超过一定分数会获得奖励，如果失败一次会受到惩罚。但是，监督反馈与具体要执行的决策无关，避开板栗仔（Goombas）或者跳过火轮圈。本书讨论的半监督学习将集中于监督与非监督学习，因为这些类型包括机器学习的绝大多数问题。下一章，我们会介绍监督学习与非监督学习的更多细节。

**监督学习是通过一个输入产生一个带标签的输出的经验数据对中进行学习。**机器学习程序中输出结果有很多名称，一些属于机器学习领域，另外一些是专用术语。本书中，我们把输出结果称为响应值（response variable），不过输出结果还有其他名称，如因变量（dependent variables），回归值（regressands），标准变量（criterion variables），测得变量（measured variables），解释变量（explained variables），结果变量（outcome variables），实验变量（experimental variables），标签（labels），和输出变量（output variables）。同理，输入变量也有很多名称。本书把输入变量作为特征（features），它们测量的现象作为解释变量（explanatory variables）。输入变量的其他名称有，预测值（predictors），解释变量（regressors），控制变量（controlled variables），操作便利（manipulated variables）和显现变量（exposure variables）。响应变量和解释变量可能需要真实的或不相关的数值。

构成监督学习经验的案例集合称为训练集（training set）。评估程序效果的案例集合称为测试集（test set）。响应变量可以看成是解释变量构成问题的答案。监督学习问题从不同问题结合中学习，就是说，监督学习程序输入是正确的答案，需要对类似的问题作出正确的反馈。

机器学习任务

常见的监督式机器学习任务就是分类（classification）和回归（regression）。分类认为需要学会从若干变量约束条件中预测出目标变量的值，就是必须预测出新观测值的类型，种类或标签。分类的应用包括预测股票的涨跌，新闻头条是政治新闻还是娱乐新闻。回归问题需要预测连续变量的数值，比如预测新产品的销量，或者依据工作的描述预算工资水平等。与分类方式类似，回归问题需要监督学习。

常见的无监督式机器学习任务是通过训练数据发现相关观测值的组别，称为类（clusters）。对应的任务称为聚类（clustering），通过一些相似性度量方法把一些观测值分成同一类。聚类常用来分析数据集。比如有一些影评数据，聚类算法可以分辨积极的和消极的影评。系统是不能给类加上“积极”或“消极”的标签的；没有监督，系统只能通过相似性度量方法把观测值分成两类。聚类分析的应用场景是用市场产品销售数据为客户分级。通过挖掘一组用户的共同属性，销售人员可以为这类客户提供定制服务。聚类还被用于互联网广播服务，比如有一些歌曲，聚类算法能够按风格流派把歌曲分组。通过不同的相似性度量方法，同样的聚类算法可能通过关键词来分组，也可能通过使用的乐器来分组。

降维（Dimensionality reduction）是另一个常见的无监督学习任务。有些问题可能包含成千上万个解释变量，处理起来非常麻烦。另外，有些解释变量属于噪音，也有些完全是无边的变量，这些影响都会降低程序的归纳能力。降维是发现对响应变量影响最大的解释变量的过程。降维可以更容易的实现数据可视化。如不同面积房子的价格数据可视化，房子的面积可以画在x轴，其价格可以画在y轴，很容易实现可视化。再加一个解释变量，也很容易可视化房屋价格的回归问题，比如房间里卫生间的数量可以画在z轴。但是，几千个解释变量的问题是不可能可视化的。

训练数据和测试数据

训练集里面的观测值构成了算法用来学习的经验数据。在监督学习问题中，每个观测值都由一个响应变量和若干个解释变量组成。

测试集是一个类似的观测值集合，用一些度量标准来评估模型的运行效果。需要注意的是，测试集的数据不能出现在训练集中。否则，很难评价算法是否从训练集中学到了归纳能力，或者仅仅只是简单的记录了结果。归纳很好的程序能够用新数据有效地完成任务。相反，一个通过记忆训练数据来学习复杂模型的程序，可能通过训练集准确预测响应变量的值，但是在处理新问题的时候由于没有归纳能力会预测失败。

训练集的记忆称为过度拟合（over-fitting）。一个记住了观测值的程序不一定能够很好的完成工作，因为它在记忆关系和结果的时候，把噪声也同时记住了。平衡记忆能力与归纳能力，或者说是过度拟合与拟合不够，是许多机器学习算法面对的共同问题。后面的章节，我们会介绍正则化（regularization），可以用来减轻许多模型的过度拟合程度。

除了训练集和测试集，还有一个观测值集合称为验证集（validation set或 hold-out set），有时候需要用到。验证集用来调整超参数（hyperparameters）变量，这类变量控制模型是如何学习的。这个程序也通过测试集来评估其真实的效果，验证集的效果不能用于评估其真实的效果，由于程序参数已经用验证数据调整过了。通常会把监督学习的观测值分成训练、验证和测试集三部分。各部分的大小没有要求，按实际观测值的规模来定。一般把50%以上的数据作为训练集，25%的数据做测试集，剩下的作为验证集。

有的训练集只包含几百个观测值，有的可能有几百万。随着存储成本越来越便宜，网络连接范围不断扩大，内置传感器的智能手机的普及，以及对隐私数据态度的转变都在为大数据新动力，千万甚至上亿级别的训练集成为可能。本书不会涉及这类需要上百个机器并行计算才能完成的任务，许多机器学习算法的能力会随着训练集的丰富变得更强大。但是，机器学习算法也有句老话“放入的是垃圾，出来的也是垃圾”。一个学习了一大堆错误百出的教材的学生不会比只读一点好书的学生考得好。同理，对一堆充满噪声、没有关联、或标签错误的数据进行学习的算法，也不会比只学习一小部分更有代表性的训练集的算法效果更好。

许多监督学习的训练集都是手工准备的，或者半自动处理。建一个海量监督数据集需要耗费许多资源。好在scikit-learn有些数据集，可以让开发者直接验证自己的模型。在开发阶段，尤其是训练集不够的时候，交叉验证（cross-validation ）的方法可以用相同的数据对算法进行多次训练和检验。在交叉验证中，训练数据是分成N块的。算法用N-1块进行训练，再用最后一块进行测试。每块都被算法轮流处理若干次，保证算法可以在训练和评估所有数据。下图就是5块数据的交叉验证方法：

数据集被等分成5块，从A标到E。开始的时候，模型用B到E进行训练，在A上测试。下一轮，在A，C，D和E上训练，用B进行测试。依次循环，直到每一块都测试过。交叉验证为模型的效果评估提供了比只有一个数据集更准确的方法。

效果评估，偏差，方差

许多度量方法可以用于评估一个程序是否学会了有效处理任务。在监督学习问题中，很多效果度量标准用来评估预测误差。有两种基本的预测误差：模型的偏差（bias）和方差（variance）。假设你有很多训练集都是不一样的，但是都具有代表性。一个高偏差的模型会产生类似的误差，无论它使用哪个训练集。模型偏离自己对真实关系假设的误差超过了模型在训练集训练的结果。模型有高偏差是固定不变的，但是模型有高方差可能是灵活的，因为模型发觉了训练集里面的噪音部分。就是说，高方差的模型是过度拟合了训练集数据，而一个模型有高偏差的时候，其实是拟合不够的表现。

偏差和方差就像飞镖射到靶子上。每个飞镖就是从不同数据集得出的预测结果。高偏差、低误差的模型就是把飞镖扔到了离靶心很远的地方，但是都集中在一个位置。而高偏差、高误差的模型就是把飞镖扔到了靶子上，但是飞镖离靶心也很远，而且彼此间很分散。低偏差、高误差的模型就是把飞镖扔到了离靶心很近的地方，但是聚类效果不好。最后就是低偏差、低误差的模型，把飞镖扔到了离靶心很近的地方，聚类效果也很好。如下图所示：

在理想情况下，模型具有低偏差和低误差，但是二者具有背反特征，即要降低一个指标的时候，另一个指标就会增加。这就是著名的偏差-方差均衡(Bias-Variance Trade-off)。后面我们会介绍很多模型的偏差-方差均衡特点。

无监督学习问题没有误差项要评估，其效果的是评估数据结构的一些属性。

大多数效果评估方法只能用于具体的任务。机器学习系统应该可以这样评估：用系统在真实世界中发生错误的代价来表示效果评估方法。这看起来很明显，下面例子描述的是适用于一般任务而不只是具体任务的效果评估方法。

有一个对肿瘤数据进行观察的机器学习系统分类任务，需要预测肿瘤是恶性的（malignant）还是良性的（benign）。准确度，或者是正确分类的比例，就是对程序效果评价的直观度量方法。准确度能够评价程序效果，不过它不能区分出，误把良性肿瘤分为恶性肿瘤，和误把恶性肿瘤分为良性肿瘤的效果差异。在一些应用里，发生不同类型错误的代价是相同的。但是，在这个问题里面，没有识别出恶性肿瘤的代价要比误把良性肿瘤分为恶性肿瘤的代价要大的多。

我们可以通过对每一种可能的预测结果进行评估来建立分类系统效果的不同评价方法。当系统正确地识别出一个恶性肿瘤，这个预测叫真阳性(True positive)；如果把一个良性肿瘤分成了一个恶性肿瘤，叫假阳性(False positive）；正确地识别出一个良性肿瘤叫真阴性(True negative)；把一个恶性肿瘤分成了一个良性肿瘤，叫假阴性(False negative）。这四个结果可以用来计算分类系统效果的评价体系，包括准确率（accuracy），精确率（precision）和召回率（recall）三项指标。

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

朴素贝叶斯：

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

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’=p1H1+p2H2.，则此时的信息增益ΔH=H-H’。以信息增益为原则，把所有的属性都测试一边，选择一个使增益最大的属性作为本次分枝属性。

决策树的优点：

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

缺点：

容易过拟合（后续出现了随机森林，减小了过拟合现象）；

Logistic回归：

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

1. logistic函数表达式为：

其导数形式为：

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

到整个样本的后验概率：

其中：

通过对数进一步化简为：

3. 其实它的loss function为-l(θ)，因此我们需使loss function最小，可采用梯度下降法得到。梯度下降法公式为:

Logistic回归优点：

1、实现简单；

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

缺点：

1、容易欠拟合，一般准确度不太高

2、只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；

线性回归：

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

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

因为此时优化的是：

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

线性回归优点：

实现简单，计算简单；

缺点：

不能拟合非线性数据；

KNN算法：

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

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

2. 对上面所有的距离值进行排序；

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

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

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

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

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

KNN算法的优点：

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

2. 可用于非线性分类；

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

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

缺点：

1. 计算量大；

2. 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；

3. 需要大量的内存；

SVM算法：

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

1. svm中的最优分类面是对所有样本的几何裕量最大（为什么要选择最大间隔分类器，请从数学角度上说明？网易深度学习岗位面试过程中有被问到。答案就是几何间隔与样本的误分次数间存在关系：

，其中的分母就是样本到分类间隔距离，分子中的R是所有样本中的最长向量值），即：

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

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

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

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

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

由上面第1式子可以知道，如果我们优化出了α，则直接可以求出w了，即模型的参数搞定。而上面第2个式子可以作为后续优化的一个约束条件。

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

而这个函数可以用常用的优化方法求得α，进而求得w和b。

5. 按照道理，svm简单理论应该到此结束。不过还是要补充一点，即在预测时有：

那个尖括号我们可以用核函数代替，这也是svm经常和核函数扯在一起的原因。

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

此时对应的对偶优化公式为：

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

SVM算法优点：

可用于线性/非线性分类，也可以用于回归；

低泛化误差；

容易解释；

计算复杂度较低；

缺点：

对参数和核函数的选择比较敏感；

原始的SVM只比较擅长处理二分类问题；

Boosting算法：

主要以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值不同而已。

测试过程如下：

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

Boosting算法的优点：

低泛化误差；

容易实现，分类准确率较高，没有太多参数可以调；

缺点：

对outlier比较敏感；

聚类：

根据聚类思想划分：

1. 基于划分的聚类:

K-means, k-medoids(每一个类别中找一个样本点来代表),CLARANS.

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

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. 基于密度的聚类：

DBSACN,OPTICS,BIRCH(CF-Tree),CURE.

4. 基于网格的方法：

STING, WaveCluster.

5. 基于模型的聚类：

EM,SOM,COBWEB.

以上这些算法的简介可参考聚类（百度百科）。

推荐系统：

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

基于内容的实现：

不同人对不同电影的评分这个例子，可以看做是一个普通的回归问题，因此每部电影都需要提前提取出一个特征向量(即x值)，然后针对每个用户建模，即每个用户打的分值作为y值，利用这些已有的分值y和电影特征值x就可以训练回归模型了(最常见的就是线性回归)。这样就可以预测那些用户没有评分的电影的分数。（值得注意的是需对每个用户都建立他自己的回归模型）

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

当然还可以是同时优化得到每个用户对不同类型电影的热爱程度以及每部电影的特征。具体可以参考Ng在coursera上的ml教程：https://www.coursera.org/course/ml

基于协同滤波的实现：

协同滤波（CF）可以看做是一个分类问题，也可以看做是矩阵分解问题。协同滤波主要是基于每个人自己的喜好都类似这一特征，它不依赖于个人的基本信息。比如刚刚那个电影评分的例子中，预测那些没有被评分的电影的分数只依赖于已经打分的那些分数，并不需要去学习那些电影的特征。

SVD将矩阵分解为三个矩阵的乘积，公式如下所示：

中间的矩阵sigma为对角矩阵，对角元素的值为Data矩阵的奇异值(注意奇异值和特征值是不同的)，且已经从大到小排列好了。即使去掉特征值小的那些特征，依然可以很好的重构出原始矩阵。如下图所示：

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

果m代表商品的个数，n代表用户的个数，则U矩阵的每一行代表商品的属性，现在通过降维U矩阵（取深色部分）后，每一个商品的属性可以用更低的维度表示（假设为k维）。这样当新来一个用户的商品推荐向量X，则可以根据公式X’U1inv(S1)得到一个k维的向量，然后在V’中寻找最相似的那一个用户（相似度测量可用余弦公式等），根据这个用户的评分来推荐（主要是推荐新用户未打分的那些商品）。具体例子可以参考网页：SVD在推荐系统中的应用。

另外关于SVD分解后每个矩阵的实际含义可以参考google吴军的《数学之美》一书（不过个人感觉吴军解释UV两个矩阵时好像弄反了，不知道大家怎样认为）。或者参考machine learning in action其中的svd章节。

pLSA:

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

公式中的意义如下：

具体可以参考2010龙星计划：机器学习中对应的主题模型那一讲

LDA：

主题模型，概率图如下：

和pLSA不同的是LDA中假设了很多先验分布，且一般参数的先验分布都假设为Dirichlet分布，其原因是共轭分布时先验概率和后验概率的形式相同。

GDBT：

GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，好像在阿里内部用得比较多（所以阿里算法岗位面试时可能会问到），它是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的输出结果累加起来就是最终答案。它在被提出之初就和SVM一起被认为是泛化能力（generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。

GBDT是回归树，不是分类树。其核心就在于，每一棵树是从之前所有树的残差中来学习的。为了防止过拟合，和Adaboosting一样，也加入了boosting这一项。

关于GDBT的介绍可以可以参考：GBDT（MART） 迭代决策树入门教程 | 简介。

Regularization:

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

1. 数值上更容易求解；

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

3. 控制模型的复杂度，光滑性。复杂性越小且越光滑的目标函数泛化能力越强。而加入规则项能使目标函数复杂度减小，且更光滑。

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

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

6. 可以看出是权值的高斯先验。

异常检测：

可以估计样本的密度函数，对于新样本直接计算其密度，如果密度值小于某一阈值，则表示该样本异常。而密度函数一般采用多维的高斯分布。如果样本有n维，则每一维的特征都可以看作是符合高斯分布的，即使这些特征可视化出来不太符合高斯分布，也可以对该特征进行数学转换让其看起来像高斯分布，比如说x=log(x+c), x=x^(1/c)等。异常检测的算法流程如下：

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

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

上面的内容可以参考Ng的https://www.coursera.org/course/ml

EM算法：

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

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

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

重复上面2步直至收敛。

公式如下所示：

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

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

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

更具体的计算公式为：

M步公式如下（计算每个高斯的比重，均值，方差这3个参数）：

关于EM算法可以参考Ng的cs229课程资料 或者网易公开课：斯坦福大学公开课 ：机器学习课程。

Apriori:

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

1. 如果一个项目集合不是频繁集合，那么任何包含它的项目集合也一定不是频繁集合；

2. 如果一个项目集合是频繁集合，那么它的任何非空子集也是频繁集合；

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

看下面这个例子：

元素项目表格：

如果每个步骤不去掉非频繁项目集，则其扫描过程的树形结构如下：

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

上面的内容主要参考的是machine learning in action这本书。

FP Growth:

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节点，具体的过程可以参考博客：Frequent Pattern 挖掘之二(FP Growth算法)，里面讲得很详细。