理论上二者越高越好，但实际中在某些情况下是矛盾的，因此需要在不同场合具体判断。

P-R曲线：以召回率R为横轴，P为纵轴，P-R曲线越靠近右上角越好。计算曲线面积AP分数可以比较不同模型的精度，但是不方便计算，后面设计了一些指标。

F1：是精确率和召回率的调和平均值。
F值可以泛化为加权调和

• 2 准确率
  

• 3 ROC和AUC
  ? ? ? 许多模型输出的是预测概率，需要设置一个判定阈值，当预测概率大于阈值时，判定为正预测，否则为负预测。因此需要引入一个超参数，并且超参数会影响的模型的泛化能力。
  接收者操作特征（receiverOperating Characteristic，ROC）
  
  ? ? ? ROC曲线与P-R曲线有些类似。ROC曲线越靠近左上角性能越好。左上角坐标为(0.1)，即 FPR=0，TPR=1。根据FPR和TPR公式可以得知，此时FN=0，FP=0模型对所有样本分类正确。
  绘制ROC曲线：
  ? ? ? 首先对所有样本按预测概率排序，以每条样本的预测概率为阈值，计算对应的FPR和TPR，然后用线段连接。当数据量少时，绘制的ROC曲线不平滑;当数据量大时，绘制的ROC曲线会趋于平滑。

  • AUC
    ? ? ? 就是ROC曲线的面积，取值越大说明模型越有可能将正样本排在负样本前面。AUC=随机挑选一个正样本和负样本，分类器将正样本排在负样本前面的概率。AUC常常被用来作为模型排序好坏的指标，原因在于AUC可以看做随机从正负样本中选取一对正负样本，其中正样本的得分大于负样本的概率。所以，AUC常用在排序场景的模型评估，比如搜索和推荐等场景。

    基尼指数的联系:Gini +1= 2*AUC

    计算方法：
    

• 4 对数损失
  

2、回归问题（regression）
? ? ? 回归用于预测输入变量（自变量）和输出变量（因变量）之间的关系，回归模型正是表示从输入变量到输出变量之间映射的函数。

• 1 平均绝对误差
  

• 2 平均绝对百分误差
  

• 3 均方误差
  ? ? ? 均方误差（MSE）是最常用的回归损失函数。MSE是目标变量与预测值之间距离平方之和。
  

• 4 均方根误差
  

3、排序指标

• 1 平均准确率均值
  
• 2 NDCG，归一化贴现累计收益
  

2.3.2 过拟合

过拟合Def：
? ? ? 一味的追求提高模型对训练数据的预测结果，所选模型的复杂度可能会更高，由此出现了对训练数据拟合效果很好，但对于未知的数据效果不一定好的现象，就称为过拟合。

过拟合的解决方法：

• 正则化
• 减少特征数量
• 交叉验证
• 增加数据

2.3.3 正则化（模型选择方法）

可以看这里：L1，L2正则化详解

1、结构风险 = 经验风险+正则化项，下面是结构风险最小化模型

? ? ? 正则化项r(d）可以采用数学里面的范数表示，以下是范数的概念。

• L0范数
  
• L1范数
  
• L2范数
  

2、 一般采用L1和L2范数进行正则，称为L1正则化和L2正则化

question：怎样才可以避免过拟合？
answer：

??我们一般认为参数数值小的可以适用于更一般的模型，因为参数数值大的话，稍微一点数值干扰就会对结果造成很大的偏差，因此。参数越小的模型，就越简单。所以尽可能使得模型的参数降低。

question：为什么L1范数和L2范数可以避免过拟合？
answer：

? ? ? 加入正则化项就是在原来目标函数的基础上加入了约束。当目标函数的等高线和L1,L2范数函数第一次相交时，得到最优解。

L1范数：

? ? ? L1范数符合拉普拉斯分布，是不完全可微的。表现在图像上会有很多角出现。这些角和目标函数的接触机会远大于其他部分。就会造成最优值出现在坐标轴上，因此就会导致某一维的权重为0，产生稀疏权重矩阵，进而防止过拟合。

L2范数：

? ? ? L2范数符合高斯分布，是完全可微的。和L1相比，图像上的棱角被圆滑了很多。一般最优值不会在坐标轴上出现。在最小化正则项时，可以是参数不断趋向于0.最后活的很小的参数。

2.3.4 交叉验证（模型选择方法）

? ? ? 如果给定的样本数据充足，进行模型选择的一种简单方法是随机地将数据集切分成三部分，分别为训练集（training set）、验证集（validation set）和测试集（test set）。

• 训练集用来训练模型
• 验证集用于模型的选择
• 测试集用于最终对学习方法的评估

? ? ? 但是，在许多实际应用中数据是不充足的。为了选择好的模型，可以采用交叉验证方法。交叉验证的基本想法是重复地使用数据；把给定的数据进行切分，将切分的数据集组合为训练集与测试集，在此基础上反复地进行训练、测试以及模型选择。

• 1 简单交叉验证
  

• 2 S折交叉验证（应用最多）
  

• 3 留一交叉验证(当S=N)
  

2.4 泛化能力

1 定义

学习方法的泛化能力（generalizationability）是指由该方法学习到的模型对未知数据的预测能力，是学习方法本质上重要的性质。

现实中采用最多的办法是通过测试误差来评价学习方法的泛化能力.事实上，泛化误差就是所学习到的模型的期望风险。

? ? ? 但这种评价是依赖于测试数据集的。因为测试数据集是有限的，很有可能由此得到的评价结果是不可靠的。统计学习理论试图从理论上对学习方法的泛化能力进行分析。

2 泛化误差上界
? ? ? 学习方法的泛化能力分析往往是通过研究泛化误差的概率上界进行的，简称为泛化误差上界（generalization error bound）。具体来说，就是通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。

特性：

• 它是样本容量的函数，当样本容量增加时，泛化上界趋于0，效果越好。
• 它是假设空间容量（capacity）的函数，假设空间容量越大，模型就越难学，泛化误差上界就越大。

? ? ? 下面给出一个简单的泛化误差上界的例子：二类分类问题的泛化误差上界。
考虑二类分类问题。已知训练数据集T＝{(x1，y 1),(x2，y 2),…,(xN,yN)}，它是从联合概率分布P(X,Y)独立同分布产生的，X?Rn，Y?{-1,+1}。假设空间是函数的有限集合＝{f1，f2,…,fd}，d是函数个数。设f是从 中选取的函数。损失函数是0-1损失。关于f的期望风险和经验风险分别是：


经验风险最小化（ERM)

则FN的泛化能力：

泛化误差上界定理

? ? ? 对于二分类问题，假设空间是有限个函数的集合，对于任何一个函数，至少以1-delta的概率成立以下不等式：

? ? ? 其中：

2.5 生成模型和判别模型

1. 监督学习的任务就是学习一个模型，应用这一模型，对给定的输入预测相应的输出。这个模型的一般形式为决策函数：Y＝f(X)或者条件概率分布：P(Y|X)。
2. 监督学习方法又可以分为生成方法（generative approach）和判别方法（discriminative approach）。所学到的模型分别称为生成模型（generative model）和判别模型（discriminative model）

2.5.1 生成模型

? ? ? 生成方法根据数据学习联合概率分布P（X,Y），然后求出条件概率分布P（Y|X）作为预测模型。典型的生成模型有朴素贝叶斯和隐马尔科夫模型。

2.5.2 判别模型

? ? ? 判别方法是直接学习决策函数F（x）或者条件概率分布P（Y|X） 作为预测的模型，即判别模型。主要关心对于给定的输出，应该预测怎样的输出问题。典型的判别模型有KNN，感知机，决策树，逻辑回归，最大熵模型，SVM，提升方法和条件随机场等等。

2.5.3 生成模型和判别模型比较

1. 生成方法的特点：
   • 生成方法可以还原出联合概率分布P(X,Y)，而判别方法则不能；
   • 生成方法的学习收敛速度更快，即当样本容量增加的时候，学到的模型可以更快地收敛于真实模型；
   • 当存在隐变量时，仍可以用生成方法学习，此时判别方法就不能用。
2. 判别方法的特点：
   • 判别方法直接学习条件概率P(Y|X)或决策函数f(X)，直接面对预测，往往学习的准确率更高；
   • 由于直接学习P(Y|X)或f(X)，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。

3 感知机（Perception）

• 感知机1957年由Rosenblatt提出，是神经网络与支持向量机的基础。
• 感知机（perceptron）是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和–1二值。
• 感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。
• 导入基于误分类的损失函数；
• 利用梯度下降法对损失函数进行极小化。
• 具有简单而易于实现的优点，分为原始形式和对偶形式。

3.1 感知机模型

3.2 感知机模型的几何解释

3.3 感知机模型的损失函数

3.4 感知机模型的对偶形式

4 K近邻法（k-nearest neighbor，k-NN）

4.1 K近邻定义

1、一句话定义：
? ? ? 给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个类，就把该输入实例分为这个类。

2、三要素：距离度量，k值的选取，分类决策规则的选取。

1. 距离度量一般采用欧氏距离，也可以是其他距离（Lp距离）
2. k值选取将会对结果产生巨大的影响。如果k值较小，整体模型变的复杂，容易发生过拟合；如果k值过大，不相关的点也对预测产生影响，导致预测精度较低。一般可以采用交叉验证进行k值得选取。
3. 分类决策规则：往往是多数表决。

4.2 k近邻的实现-kd树

? ? ? 实现k近邻法时，主要考虑的问题是如何对训练数据进行快速k近邻搜索。这点在特征空间的维数大及训练数据容量大时尤其必要。最简单是的就是线性扫描，但对于高维数据不可取，因此采用特殊的存储结构kd树进行搜索。

4.2.1 kd树的构建

更多详情请见：kd树构建详解

? ? ? kd树是二叉树，和分治法思想一样，利用已有数据进行空间切分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个k维超矩形区域。
? ? ? 需要注意的是，每一刀都要切在数据点上面。主要考虑切分域和切分点的选择（分别使用方差最大优先和中位优先）
算法流程：

对于例子：构造一个平衡kd树。

结果如下：

4.2.2 ball tree 和其他树类型介绍

? ? ? 在kd tree 中，我们看到一个导致性能下降的最核心因素是因为kd树的平面是一个个的方形，求最近邻时使用的是圆形。方形平面跟圆形相交的可能性是极高的，如果方形的交汇点多的话，圆形和几个平面相交的可能性就变得更大。这样，凡是相交的平面，都需要进行检查，大大的降低运行效率。

? ? ? 为了解决这一个问题，ball tree抛弃了kd树画的方形，而建立球形，去掉棱角。简而言之，就是使用超球面而不是超矩形划分区域。

4.3 搜索kd树

? ? ? 用目标数据在kd树中寻找最近邻时，最核心的两个部分是：

1. 寻找近似点-寻找最近邻的叶子节点作为目标数据的近似最近点。

2. 回溯-以目标数据和最近邻的近似点的距离沿树根部进行回溯和迭代。

5 朴素贝叶斯法（Naive Bayesian Model，NBM）

? ? ? 贝叶斯分类算法是统计学的一种分类方法，其分类原理就是利用贝叶斯公式根据某对象的先验概率计算出其后验概率，然后选择具有最大后验概率的类作为该对象所属的类。

? ? ? 之所以称之为”朴素”，是因为贝叶斯分类只做最原始、最简单的假设:

• 所有的特征之间是统计独立的（假设某样本x有a1,…,aM个属性,那么有P(x)=P(a1,…,aM) = P(a1)*…*P(aM);）

5.1 概率公式复习

1. 先验概率： 由经验和数据可以直接得到的概率。比如根据统计历史数据，得到北京今天下雨概率。
2. 似然函数： 根据已知结果推算固定情况下的可能性。比如下雨时有乌云的概率。类条件概率
3. 后验概率：根据今天有乌云，结合先验概率和似然函数，得到今天下雨的概率。通过贝叶斯公式计算
4. 全概率公式：
   
5. 联合概率和条件概率满足：

6. 贝叶斯公式：

5.2 朴素贝叶斯

5.2.1 条件独立性假设

? ? ? 由于这是一个较强的假设，朴素贝叶斯法也由此得名.

5.2.2 朴素贝叶斯分类器（公式推导）

? ? ? 根据贝叶斯公式：

? ? ? 将条件独立性公式带入贝叶斯公式中：

? ? ? 于是，贝叶斯分类器可以表示为：

? ? ? 由于分母对所有Ck都是相同的，故可以简化为：

? ? ? 这就是朴素贝叶斯分类器。

5.2.3 后验概率最大化准则：

5.3 朴素贝叶斯法的参数估计

5.3.1 极大似然估计（Maximum Likelihood Estimate，MLE）

? ? ? 朴素贝叶斯的参数主要有两个，

? ? ? 其对应的极大似然估计分别为：

5.3.2 贝叶斯估计

? ? ? 用极大似然估计可能会出现所要估计的概率值为0的情况。这时会影响到后验概率的计算结果，使分类产生偏差。解决这一问题的方法是采用贝叶斯估计。
先验概率和类条件概率的贝叶斯估计为：

? ? ? 其中，等价于在随机变量各个取值的频数上赋予一个正数 namuda>0。当namuda ＝0时就是极
大似然估计。常取 1，这时称为拉普拉斯平滑（Laplace smoothing）。

5.4 朴素贝叶斯分类器优缺点

优点：

• 不受孤立的噪声点影响。因为从数据中计算条件概率时，这些孤立点被平均掉了。
• 面对无关属性Xi,分类器不受影响。因为P（xi|Y）几乎成为了均匀分布，Xi的类条件概率不会对后面的总的后验概率计算造成影响。
• 结果容易解释

缺点：

• 相关属性可能降低qtd能，因为有可能导致条件独立性不成立。
• 分类决策有一定的错误
• 对数据的

6 决策树（Decision Tree）

• 决策树（decision tree）是一种基本的分类与回归方法。
• 决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪。
• 这些决策树学习的思想主要来源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART算法。

6.1 决策树模型与学习

? ? ?决策树解决分类问题的一般方法

6.1.1 决策树模型

? ? ? 定义：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。

6.1.2 决策树与if-then规则

? ? ?可以将决策树看成一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。

? ? ?决策树的路径或其对应的if-then规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。

6.1.3 决策树与条件概率分布

6.1.4 决策树学习

? ? ?决策树学习本质上是从训练数据集中归纳出一组分类规则，与训练数据集不相矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个也没有。从另一个角度看，决策树学习是由训练数据集估计条件概率模型。基于特征空间划分的类的条件概率模型有无穷多个。我们选择的条件概率模型应该不仅对训练数据有很好的拟合，而且对未知数据有很好的预测。
? ? ?决策树的损失函数是正则化的极大似然函数。当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优（sub-optimal）的。
? ? ?决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。如果这些子集已经能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去；如果还有子集不能被基本正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。如此递归地进行下去，直至所有训练数据子集被基本正确分类，或者没有合适的特征为止。最后每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。
? ? ?以上方法生成的决策树可能对训练数据有很好的分类能力，但对未知的测试数据却未必有很好的分类能力，即可能发生过拟合现象。我们需要对已生成的树自下而上进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，就是去掉过于细分的叶结点，使其回退到父结点，甚至更高的结点，然后将父结点或更高的结点改为新的叶结点。