第二章 机器学习基础

​ 机器学习起源于上世纪50年代，1959年在IBM工作的Arthur Samuel设计了一个下棋程序，这个程序具有学习的能力，它可以在不断的对弈中提高自己。由此提出了“机器学习”这个概念，它是一个结合了多个学科如概率论，优化理论，统计等，最终在计算机上实现自我获取新知识，学习改善自己的这样一个研究领域。机器学习是人工智能的一个子集，目前已经发展出许多有用的方法，比如支持向量机，回归，决策树，随机森林，强化方法，集成学习，深度学习等等，一定程度上可以帮助人们完成一些数据预测，自动化，自动决策，最优化等初步替代脑力的任务。本章我们主要介绍下机器学习的基本概念、监督学习、分类算法、逻辑回归、代价函数、损失函数、LDA、PCA、决策树、支持向量机、EM算法、聚类和降维以及模型评估有哪些方法、指标等等。

2.1 基本概念

2.1.1 大话理解机器学习本质

​ 机器学习(Machine Learning, ML)，顾名思义，让机器去学习。这里，机器指的是计算机，是算法运行的物理载体，你也可以把各种算法本身当做一个有输入和输出的机器。那么到底让计算机去学习什么呢？对于一个任务及其表现的度量方法，设计一种算法，让算法能够提取中数据所蕴含的规律，这就叫机器学习。如果输入机器的数据是带有标签的，就称作有监督学习。如果数据是无标签的，就是无监督学习。

2.1.2 什么是神经网络

​ 神经网络就是按照一定规则将多个神经元连接起来的网络。不同的神经网络，具有不同的连接规则。例如全连接(Full Connected, FC)神经网络，它的规则包括：

（1）有三种层：输入层，输出层，隐藏层。

（2）同一层的神经元之间没有连接。

（3）fully connected的含义：第 N 层的每个神经元和第 N-1 层的所有神经元相连，第 N-1 层神经元的输出就是第 N 层神经元的输入。

（4）每个连接都有一个权值。

神经网络架构
​ 图2-1就是一个神经网络系统，它由很多层组成。输入层负责接收信息，比如一只猫的图片。输出层是计算机对这个输入信息的判断结果，它是不是猫。隐藏层就是对输入信息的传递和加工处理。

​ 图2-1 神经网络系统

2.1.3 各种常见算法图示

​ 日常使用机器学习的任务中，我们经常会遇见各种算法，图2-2是各种常见算法的图示。

回归算法	聚类算法	正则化方法

决策树学习	贝叶斯方法	基于核的算法

聚类算法	关联规则学习	人工神经网络

深度学习	降低维度算法	集成算法

​ 图2-2 各种常见算法图示

2.1.4 计算图的导数计算

​ 计算图导数计算是反向传播，利用链式法则和隐式函数求导。

​ 假设 $z = f(u,v)$ 在点 $(u,v)$ 处偏导连续，$(u,v)$是关于 $t$ 的函数，在 $t$ 点可导，求 $z$ 在 $t$ 点的导数。

根据链式法则有

​ 链式法则用文字描述:“由两个函数凑起来的复合函数，其导数等于里边函数代入外边函数的值之导数，乘以里边函数的导数。
​ 为了便于理解，下面举例说明：

​ 则:

2.1.5 理解局部最优与全局最优

​ 笑谈局部最优和全局最优

​ 柏拉图有一天问老师苏格拉底什么是爱情？苏格拉底叫他到麦田走一次，摘一颗最大的麦穗回来，不许回头，只可摘一次。柏拉图空着手出来了，他的理由是，看见不错的，却不知道是不是最好的，一次次侥幸，走到尽头时，才发现还不如前面的，于是放弃。苏格拉底告诉他：“这就是爱情。”这故事让我们明白了一个道理，因为生命的一些不确定性，所以全局最优解是很难寻找到的，或者说根本就不存在，我们应该设置一些限定条件，然后在这个范围内寻找最优解，也就是局部最优解——有所斩获总比空手而归强，哪怕这种斩获只是一次有趣的经历。
​ 柏拉图有一天又问什么是婚姻？苏格拉底叫他到树林走一次,选一棵最好的树做圣诞树，也是不许回头，只许选一次。这次他一身疲惫地拖了一棵看起来直挺、翠绿，却有点稀疏的杉树回来，他的理由是，有了上回的教训，好不容易看见一棵看似不错的，又发现时间、体力已经快不够用了，也不管是不是最好的，就拿回来了。苏格拉底告诉他：“这就是婚姻。”

​ 优化问题一般分为局部最优和全局最优。其中，

（1）局部最优，就是在函数值空间的一个有限区域内寻找最小值；而全局最优，是在函数值空间整个区域寻找最小值问题。

（2）函数局部最小点是它的函数值小于或等于附近点的点，但是有可能大于较远距离的点。

（3）全局最小点是那种它的函数值小于或等于所有的可行点。

2.1.5 大数据与深度学习之间的关系

首先来看大数据、机器学习及数据挖掘三者简单的定义：

大数据通常被定义为“超出常用软件工具捕获，管理和处理能力”的数据集。
机器学习关心的问题是如何构建计算机程序使用经验自动改进。
数据挖掘是从数据中提取模式的特定算法的应用，在数据挖掘中，重点在于算法的应用，而不是算法本身。

机器学习和数据挖掘之间的关系如下：
数据挖掘是一个过程，在此过程中机器学习算法被用作提取数据集中的潜在有价值模式的工具。
大数据与深度学习关系总结如下：

（1）深度学习是一种模拟大脑的行为。可以从所学习对象的机制以及行为等等很多相关联的方面进行学习，模仿类型行为以及思维。

（2）深度学习对于大数据的发展有帮助。深度学习对于大数据技术开发的每一个阶段均有帮助，不管是数据的分析还是挖掘还是建模，只有深度学习，这些工作才会有可能一一得到实现。

（3）深度学习转变了解决问题的思维。很多时候发现问题到解决问题，走一步看一步不是一个主要的解决问题的方式了，在深度学习的基础上，要求我们从开始到最后都要基于一个目标，为了需要优化的那个最终目标去进行处理数据以及将数据放入到数据应用平台上去，这就是端到端（End to End）。

（4）大数据的深度学习需要一个框架。在大数据方面的深度学习都是从基础的角度出发的，深度学习需要一个框架或者一个系统。总而言之，将你的大数据通过深度分析变为现实，这就是深度学习和大数据的最直接关系。

2.2 机器学习学习方式

​ 根据数据类型的不同，对一个问题的建模有不同的方式。依据不同的学习方式和输入数据，机器学习主要分为以下四种学习方式。

2.2.1 监督学习

​ 特点：监督学习是使用已知正确答案的示例来训练网络。已知数据和其一一对应的标签，训练一个预测模型，将输入数据映射到标签的过程。

​ 常见应用场景：监督式学习的常见应用场景如分类问题和回归问题。

​ 算法举例：常见的有监督机器学习算法包括支持向量机(Support Vector Machine, SVM)，朴素贝叶斯(Naive Bayes)，逻辑回归(Logistic Regression)，K近邻(K-Nearest Neighborhood, KNN)，决策树(Decision Tree)，随机森林(Random Forest)，AdaBoost以及线性判别分析(Linear Discriminant Analysis, LDA)等。深度学习(Deep Learning)也是大多数以监督学习的方式呈现。

2.2.2 非监督式学习

​ 定义：在非监督式学习中，数据并不被特别标识，适用于你具有数据集但无标签的情况。学习模型是为了推断出数据的一些内在结构。

​ 常见应用场景：常见的应用场景包括关联规则的学习以及聚类等。

​ 算法举例：常见算法包括Apriori算法以及k-Means算法。

2.2.3 半监督式学习

​ 特点：在此学习方式下，输入数据部分被标记，部分没有被标记，这种学习模型可以用来进行预测。

​ 常见应用场景：应用场景包括分类和回归，算法包括一些对常用监督式学习算法的延伸，通过对已标记数据建模，在此基础上，对未标记数据进行预测。

​ 算法举例：常见算法如图论推理算法（Graph Inference）或者拉普拉斯支持向量机（Laplacian SVM）等。

2.2.4 弱监督学习

​ 特点：弱监督学习可以看做是有多个标记的数据集合，次集合可以是空集，单个元素，或包含多种情况（没有标记，有一个标记，和有多个标记）的多个元素。 数据集的标签是不可靠的，这里的不可靠可以是标记不正确，多种标记，标记不充分，局部标记等。已知数据和其一一对应的弱标签，训练一个智能算法，将输入数据映射到一组更强的标签的过程。标签的强弱指的是标签蕴含的信息量的多少，比如相对于分割的标签来说，分类的标签就是弱标签。

​ 算法举例：举例，给出一张包含气球的图片，需要得出气球在图片中的位置及气球和背景的分割线，这就是已知弱标签学习强标签的问题。

​ 在企业数据应用的场景下， 人们最常用的可能就是监督式学习和非监督式学习的模型。 在图像识别等领域，由于存在大量的非标识的数据和少量的可标识数据， 目前半监督式学习是一个很热的话题。

2.2.5 监督学习有哪些步骤

​ 监督学习是使用已知正确答案的示例来训练网络，每组训练数据有一个明确的标识或结果。想象一下，我们可以训练一个网络，让其从照片库中（其中包含气球的照片）识别出气球的照片。以下就是我们在这个假设场景中所要采取的步骤。

步骤1：数据集的创建和分类
​ 首先，浏览你的照片（数据集），确定所有包含气球的照片，并对其进行标注。然后，将所有照片分为训练集和验证集。目标就是在深度网络中找一函数，这个函数输入是任意一张照片，当照片中包含气球时，输出1，否则输出0。

步骤2：数据增强（Data Augmentation）
​ 当原始数据搜集和标注完毕，一般搜集的数据并不一定包含目标在各种扰动下的信息。数据的好坏对于机器学习模型的预测能力至关重要，因此一般会进行数据增强。对于图像数据来说，数据增强一般包括，图像旋转，平移，颜色变换，裁剪，仿射变换等。

步骤3：特征工程（Feature Engineering）
​ 一般来讲，特征工程包含特征提取和特征选择。常见的手工特征(Hand-Crafted Feature)有尺度不变特征变换(Scale-Invariant Feature Transform, SIFT)，方向梯度直方图(Histogram of Oriented Gradient, HOG)等。由于手工特征是启发式的，其算法设计背后的出发点不同，将这些特征组合在一起的时候有可能会产生冲突，如何将组合特征的效能发挥出来，使原始数据在特征空间中的判别性最大化，就需要用到特征选择的方法。在深度学习方法大获成功之后，人们很大一部分不再关注特征工程本身。因为，最常用到的卷积神经网络(Convolutional Neural Networks, CNNs)本身就是一种特征提取和选择的引擎。研究者提出的不同的网络结构、正则化、归一化方法实际上就是深度学习背景下的特征工程。

步骤4：构建预测模型和损失
​ 将原始数据映射到特征空间之后，也就意味着我们得到了比较合理的输入。下一步就是构建合适的预测模型得到对应输入的输出。而如何保证模型的输出和输入标签的一致性，就需要构建模型预测和标签之间的损失函数，常见的损失函数(Loss Function)有交叉熵、均方差等。通过优化方法不断迭代，使模型从最初的初始化状态一步步变化为有预测能力的模型的过程，实际上就是学习的过程。

步骤5：训练
​ 选择合适的模型和超参数进行初始化，其中超参数比如支持向量机中核函数、误差项惩罚权重等。当模型初始化参数设定好后，将制作好的特征数据输入到模型，通过合适的优化方法不断缩小输出与标签之间的差距，当迭代过程到了截止条件，就可以得到训练好的模型。优化方法最常见的就是梯度下降法及其变种，使用梯度下降法的前提是优化目标函数对于模型是可导的。

步骤6：验证和模型选择
​ 训练完训练集图片后，需要进行模型测试。利用验证集来验证模型是否可以准确地挑选出含有气球在内的照片。
​ 在此过程中，通常会通过调整和模型相关的各种事物（超参数）来重复步骤2和3，诸如里面有多少个节点，有多少层，使用怎样的激活函数和损失函数，如何在反向传播阶段积极有效地训练权值等等。

步骤7：测试及应用
​ 当有了一个准确的模型，就可以将该模型部署到你的应用程序中。你可以将预测功能发布为API（Application Programming Interface, 应用程序编程接口）调用，并且你可以从软件中调用该API，从而进行推理并给出相应的结果。

2.8 分类算法

​ 分类算法和回归算法是对真实世界不同建模的方法。分类模型是认为模型的输出是离散的，例如大自然的生物被划分为不同的种类，是离散的。回归模型的输出是连续的，例如人的身高变化过程是一个连续过程，而不是离散的。

​ 因此，在实际建模过程时，采用分类模型还是回归模型，取决于你对任务（真实世界）的分析和理解。

2.8.1 常用分类算法的优缺点？

​ 接下来我们介绍常用分类算法的优缺点，如表2-1所示。

​ 表2-1 常用分类算法的优缺点

2.8.2 分类算法的评估方法

​ 分类评估方法主要功能是用来评估分类算法的好坏，而评估一个分类器算法的好坏又包括许多项指标。了解各种评估方法，在实际应用中选择正确的评估方法是十分重要的。

• 几个常用术语
  ​ 这里首先介绍几个常见的模型评价术语，现在假设我们的分类目标只有两类，计为正例（positive）和负例（negative）分别是：
  1) True positives(TP): 被正确地划分为正例的个数，即实际为正例且被分类器划分为正例的实例数；
  2) False positives(FP): 被错误地划分为正例的个数，即实际为负例但被分类器划分为正例的实例数；
  3) False negatives(FN):被错误地划分为负例的个数，即实际为正例但被分类器划分为负例的实例数；
  4) True negatives(TN): 被正确地划分为负例的个数，即实际为负例且被分类器划分为负例的实例数。　

  ​ 表2-2 四个术语的混淆矩阵

表2-2是这四个术语的混淆矩阵，做以下说明：
1）P=TP+FN表示实际为正例的样本个数。
2）True、False描述的是分类器是否判断正确。
3）Positive、Negative是分类器的分类结果，如果正例计为1、负例计为-1，即positive=1、negative=-1。用1表示True，-1表示False，那么实际的类标=TF*PN，TF为true或false，PN为positive或negative。
4）例如True positives(TP)的实际类标=1*1=1为正例，False positives(FP)的实际类标=(-1)*1=-1为负例，False negatives(FN)的实际类标=(-1)*(-1)=1为正例，True negatives(TN)的实际类标=1*(-1)=-1为负例。

• 评价指标
  1) 正确率（accuracy）

  正确率是我们最常见的评价指标，accuracy = (TP+TN)/(P+N)，正确率是被分对的样本数在所有样本数中的占比，通常来说，正确率越高，分类器越好。
  

  2) 错误率（error rate)

  错误率则与正确率相反，描述被分类器错分的比例，error rate = (FP+FN)/(P+N)，对某一个实例来说，分对与分错是互斥事件，所以accuracy =1 -  error rate。
  

  3) 灵敏度（sensitivity）

  sensitivity = TP/P，表示的是所有正例中被分对的比例，衡量了分类器对正例的识别能力。
  

  4) 特异性（specificity)

  specificity = TN/N，表示的是所有负例中被分对的比例，衡量了分类器对负例的识别能力。
  

  5) 精度（precision）

  precision=TP/(TP+FP)，精度是精确性的度量，表示被分为正例的示例中实际为正例的比例。
  

  6) 召回率（recall）

  召回率是覆盖面的度量，度量有多个正例被分为正例，recall=TP/(TP+FN)=TP/P=sensitivity，可以看到召回率与灵敏度是一样的。
  

  7) 其他评价指标

  计算速度：分类器训练和预测需要的时间；
  鲁棒性：处理缺失值和异常值的能力；
  可扩展性：处理大数据集的能力；
  可解释性：分类器的预测标准的可理解性，像决策树产生的规则就是很容易理解的，而神经网络的一堆参数就不好理解，我们只好把它看成一个黑盒子。
  

  8) 精度和召回率反映了分类器分类性能的两个方面。如果综合考虑查准率与查全率，可以得到新的评价指标F1-score，也称为综合分类率：$F1=\frac{2 \times precision \times recall}{precision + recall}​$。

    为了综合多个类别的分类情况，评测系统整体性能，经常采用的还有微平均F1（micro-averaging）和宏平均F1（macro-averaging ）两种指标。
  
    （1）宏平均F1与微平均F1是以两种不同的平均方式求的全局F1指标。
  
    （2）宏平均F1的计算方法先对每个类别单独计算F1值，再取这些F1值的算术平均值作为全局指标。
  
    （3）微平均F1的计算方法是先累加计算各个类别的a、b、c、d的值，再由这些值求出F1值。
  
    （4）由两种平均F1的计算方式不难看出，宏平均F1平等对待每一个类别，所以它的值主要受到稀有类别的影响，而微平均F1平等考虑文档集中的每一个文档，所以它的值受到常见类别的影响比较大。
  

• ROC曲线和PR曲线

    如图2-3，ROC曲线是（Receiver Operating Characteristic Curve，受试者工作特征曲线）的简称，是以灵敏度（真阳性率）为纵坐标，以1减去特异性（假阳性率）为横坐标绘制的性能评价曲线。可以将不同模型对同一数据集的ROC曲线绘制在同一笛卡尔坐标系中，ROC曲线越靠近左上角，说明其对应模型越可靠。也可以通过ROC曲线下面的面积（Area Under Curve, AUC）来评价模型，AUC越大，模型越可靠。
  

​ 图2-3 ROC曲线

​ PR曲线是Precision Recall Curve的简称，描述的是precision和recall之间的关系，以recall为横坐标，precision为纵坐标绘制的曲线。该曲线的所对应的面积AUC实际上是目标检测中常用的评价指标平均精度（Average Precision, AP）。AP越高，说明模型性能越好。

2.8.3 正确率能很好的评估分类算法吗

​ 不同算法有不同特点，在不同数据集上有不同的表现效果，根据特定的任务选择不同的算法。如何评价分类算法的好坏，要做具体任务具体分析。对于决策树，主要用正确率去评估，但是其他算法，只用正确率能很好的评估吗？
​ 答案是否定的。
​ 正确率确实是一个很直观很好的评价指标，但是有时候正确率高并不能完全代表一个算法就好。比如对某个地区进行地震预测，地震分类属性分为0：不发生地震、1发生地震。我们都知道，不发生的概率是极大的，对于分类器而言，如果分类器不加思考，对每一个测试样例的类别都划分为0，达到99%的正确率，但是，问题来了，如果真的发生地震时，这个分类器毫无察觉，那带来的后果将是巨大的。很显然，99%正确率的分类器并不是我们想要的。出现这种现象的原因主要是数据分布不均衡，类别为1的数据太少，错分了类别1但达到了很高的正确率缺忽视了研究者本身最为关注的情况。

2.8.4 什么样的分类器是最好的

​ 对某一个任务，某个具体的分类器不可能同时满足或提高所有上面介绍的指标。
​ 如果一个分类器能正确分对所有的实例，那么各项指标都已经达到最优，但这样的分类器往往不存在。比如之前说的地震预测，既然不能百分百预测地震的发生，但实际情况中能容忍一定程度的误报。假设在1000次预测中，共有5次预测发生了地震，真实情况中有一次发生了地震，其他4次则为误报。正确率由原来的999/1000=99.9下降为996/1000=99.6。召回率由0/1=0%上升为1/1=100%。对此解释为，虽然预测失误了4次，但真的地震发生前，分类器能预测对，没有错过，这样的分类器实际意义更为重大，正是我们想要的。在这种情况下，在一定正确率前提下，要求分类器的召回率尽量高。

2.9 逻辑回归

2.9.1 回归划分

广义线性模型家族里，依据因变量不同，可以有如下划分：

（1）如果是连续的，就是多重线性回归。

（2）如果是二项分布，就是逻辑回归。

（3）如果是泊松（Poisson）分布，就是泊松回归。

（4）如果是负二项分布，就是负二项回归。

（5）逻辑回归的因变量可以是二分类的，也可以是多分类的，但是二分类的更为常用，也更加容易解释。所以实际中最常用的就是二分类的逻辑回归。

2.9.2 逻辑回归适用性

逻辑回归可用于以下几个方面：

（1）用于概率预测。用于可能性预测时，得到的结果有可比性。比如根据模型进而预测在不同的自变量情况下，发生某病或某种情况的概率有多大。

（2）用于分类。实际上跟预测有些类似，也是根据模型，判断某人属于某病或属于某种情况的概率有多大，也就是看一下这个人有多大的可能性是属于某病。进行分类时，仅需要设定一个阈值即可，可能性高于阈值是一类，低于阈值是另一类。

（3）寻找危险因素。寻找某一疾病的危险因素等。

（4）仅能用于线性问题。只有当目标和特征是线性关系时，才能用逻辑回归。在应用逻辑回归时注意两点：一是当知道模型是非线性时，不适用逻辑回归；二是当使用逻辑回归时，应注意选择和目标为线性关系的特征。

（5）各特征之间不需要满足条件独立假设，但各个特征的贡献独立计算。

2.9.3 逻辑回归与朴素贝叶斯有什么区别

逻辑回归与朴素贝叶斯区别有以下几个方面：

（1）逻辑回归是判别模型， 朴素贝叶斯是生成模型，所以生成和判别的所有区别它们都有。

（2）朴素贝叶斯属于贝叶斯，逻辑回归是最大似然，两种概率哲学间的区别。

（3）朴素贝叶斯需要条件独立假设。

（4）逻辑回归需要求特征参数间是线性的。

2.9.4 线性回归与逻辑回归的区别

线性回归与逻辑回归的区别如下描述：

（1）线性回归的样本的输出，都是连续值，$ y\in (-\infty ,+\infty )$，而逻辑回归中$y\in (0,1)$，只能取0和1。

（2）对于拟合函数也有本质上的差别：

​ 线性回归：$f(x)=\theta ^{T}x=\theta {1}x {1}+\theta {2}x {2}+…+\theta {n}x {n}$

​ 逻辑回归：$f(x)=P(y=1|x;\theta )=g(\theta ^{T}x)$，其中，$g(z)=\frac{1}{1+e^{-z}}$

​ 可以看出，线性回归的拟合函数，是对f(x)的输出变量y的拟合，而逻辑回归的拟合函数是对为1类样本的概率的拟合。

​ 那么，为什么要以1类样本的概率进行拟合呢，为什么可以这样拟合呢？

​ $\theta ^{T}x=0$就相当于是1类和0类的决策边界：

​ 当$\theta ^{T}x>0$，则y>0.5；若$\theta ^{T}x\rightarrow +\infty $，则$y \rightarrow 1 $，即y为1类;

​ 当$\theta ^{T}x<0$，则y<0.5；若$\theta ^{T}x\rightarrow -\infty $，则$y \rightarrow 0 $，即y为0类;

这个时候就能看出区别，在线性回归中$\theta ^{T}x$为预测值的拟合函数；而在逻辑回归中$\theta ^{T}x$为决策边界。下表2-3为线性回归和逻辑回归的区别。

​ 表2-3 线性回归和逻辑回归的区别

下面具体解释一下：

1. 拟合函数和预测函数什么关系呢？简单来说就是将拟合函数做了一个逻辑函数的转换，转换后使得$y^{(i)} \in (0,1)$;
2. 最小二乘和最大似然估计可以相互替代吗？回答当然是不行了。我们来看看两者依仗的原理：最大似然估计是计算使得数据出现的可能性最大的参数，依仗的自然是Probability。而最小二乘是计算误差损失。

2.10 代价函数

2.10.1 为什么需要代价函数

1. 为了得到训练逻辑回归模型的参数，需要一个代价函数，通过训练代价函数来得到参数。
2. 用于找到最优解的目的函数。

2.10.2 代价函数作用原理

​ 在回归问题中，通过代价函数来求解最优解，常用的是平方误差代价函数。假设函数图像如图2-4所示，当参数发生变化时，假设函数状态也会随着变化。

​ 图2-4 $h(x) = A + Bx$函数示意图

​ 想要拟合图中的离散点，我们需要尽可能找到最优的$A$和$B$来使这条直线更能代表所有数据。如何找到最优解呢，这就需要使用代价函数来求解，以平方误差代价函数为例，假设函数为$h(x)=\theta_0x$。
​ 平方误差代价函数的主要思想就是将实际数据给出的值与拟合出的线的对应值做差，求出拟合出的直线与实际的差距。在实际应用中，为了避免因个别极端数据产生的影响，采用类似方差再取二分之一的方式来减小个别数据的影响。因此，引出代价函数：

​ 最优解即为代价函数的最小值$\min J(\theta_0, \theta_1)$。如果是1个参数，代价函数一般通过二维曲线便可直观看出。如果是2个参数，代价函数通过三维图像可看出效果，参数越多，越复杂。
当参数为2个时，代价函数是三维图像，如下图2-5所示。

​ 图2-5 代价函数三维图像

2.10.3 为什么代价函数要非负

​ 目标函数存在一个下界，在优化过程当中，如果优化算法能够使目标函数不断减小，根据单调有界准则，这个优化算法就能证明是收敛有效的。
​ 只要设计的目标函数有下界，基本上都可以，代价函数非负更为方便。

2.10.4 常见代价函数

（1）二次代价函数（quadratic cost）：

​ 其中，$J$表示代价函数，$x$表示样本，$y$表示实际值，$a$表示输出值，$n$表示样本的总数。使用一个样本为例简单说明，此时二次代价函数为：

​ 假如使用梯度下降法（Gradient descent）来调整权值参数的大小，权值$w$和偏置$b$的梯度推导如下：

其中，$z​$表示神经元的输入，$\sigma​$表示激活函数。权值$w​$和偏置$b​$的梯度跟激活函数的梯度成正比，激活函数的梯度越大，权值$w​$和偏置$b​$的大小调整得越快，训练收敛得就越快。

注：神经网络常用的激活函数为sigmoid函数，该函数的曲线如下图2-6所示：

​ 图2-6 sigmoid函数曲线

如上图所示，对0.88和0.98两个点进行比较：
​ 假设目标是收敛到1.0。0.88离目标1.0比较远，梯度比较大，权值调整比较大。0.98离目标1.0比较近，梯度比较小，权值调整比较小。调整方案合理。
​ 假如目标是收敛到0。0.88离目标0比较近，梯度比较大，权值调整比较大。0.98离目标0比较远，梯度比较小，权值调整比较小。调整方案不合理。
​ 原因：在使用sigmoid函数的情况下, 初始的代价（误差）越大，导致训练越慢。

（2）交叉熵代价函数（cross-entropy）：

其中，$J$表示代价函数，$x$表示样本，$y$表示实际值，$a$表示输出值，$n$表示样本的总数。
权值$w$和偏置$b​$的梯度推导如下：

当误差越大时，梯度就越大，权值$w$和偏置$b$调整就越快，训练的速度也就越快。
二次代价函数适合输出神经元是线性的情况，交叉熵代价函数适合输出神经元是S型函数的情况。

（3）对数似然代价函数（log-likelihood cost）：
对数似然函数常用来作为softmax回归的代价函数。深度学习中普遍的做法是将softmax作为最后一层，此时常用的代价函数是对数似然代价函数。
对数似然代价函数与softmax的组合和交叉熵与sigmoid函数的组合非常相似。对数似然代价函数在二分类时可以化简为交叉熵代价函数的形式。
在tensorflow中：
与sigmoid搭配使用的交叉熵函数：tf.nn.sigmoid_cross_entropy_with_logits()。
与softmax搭配使用的交叉熵函数：tf.nn.softmax_cross_entropy_with_logits()。
在pytorch中：
与sigmoid搭配使用的交叉熵函数：torch.nn.BCEWithLogitsLoss()。
与softmax搭配使用的交叉熵函数：torch.nn.CrossEntropyLoss()。

2.10.5 为什么用交叉熵代替二次代价函数

（1）为什么不用二次方代价函数
由上一节可知，权值$w$和偏置$b$的偏导数为$\frac{\partial J}{\partial w}=(a-y)\sigma’(z)x$，$\frac{\partial J}{\partial b}=(a-y)\sigma’(z)$， 偏导数受激活函数的导数影响，sigmoid函数导数在输出接近0和1时非常小，会导致一些实例在刚开始训练时学习得非常慢。

（2）为什么要用交叉熵
交叉熵函数权值$w$和偏置$b$的梯度推导为：

由以上公式可知，权重学习的速度受到$\sigma{(z)}-y$影响，更大的误差，就有更快的学习速度，避免了二次代价函数方程中因$\sigma’{(z)}$导致的学习缓慢的情况。

2.11 损失函数

2.11.1 什么是损失函数

​ 损失函数（Loss Function）又叫做误差函数，用来衡量算法的运行情况，估量模型的预测值与真实值的不一致程度，是一个非负实值函数，通常使用$
L(Y, f(x))​$来表示。损失函数越小，模型的鲁棒性就越好。损失函数是经验风险函数的核心部分，也是结构风险函数重要组成部分。

2.11.2 常见的损失函数

​ 机器学习通过对算法中的目标函数进行不断求解优化，得到最终想要的结果。分类和回归问题中，通常使用损失函数或代价函数作为目标函数。
​ 损失函数用来评价预测值和真实值不一样的程度。通常损失函数越好，模型的性能也越好。
​ 损失函数可分为经验风险损失函数和结构风险损失函数。经验风险损失函数指预测结果和实际结果的差别，结构风险损失函数是在经验风险损失函数上加上正则项。
​ 下面介绍常用的损失函数：

（1）0-1损失函数
如果预测值和目标值相等，值为0，如果不相等，值为1。

一般的在实际使用中，相等的条件过于严格，可适当放宽条件：

（2）绝对值损失函数
和0-1损失函数相似，绝对值损失函数表示为：

（3）平方损失函数

这点可从最小二乘法和欧几里得距离角度理解。最小二乘法的原理是，最优拟合曲线应该使所有点到回归直线的距离和最小。

（4）对数损失函数

​ 常见的逻辑回归使用的就是对数损失函数，有很多人认为逻辑回归的损失函数是平方损失，其实不然。逻辑回归它假设样本服从伯努利分布（0-1分布），进而求得满足该分布的似然函数，接着取对数求极值等。逻辑回归推导出的经验风险函数是最小化负的似然函数，从损失函数的角度看，就是对数损失函数。

（6）指数损失函数
指数损失函数的标准形式为：

例如AdaBoost就是以指数损失函数为损失函数。

（7）Hinge损失函数
Hinge损失函数的标准形式如下：

统一的形式：

其中y是预测值，范围为(-1,1)，t为目标值，其为-1或1。

在线性支持向量机中，最优化问题可等价于

上式相似于下式

其中$l(wx_i+by_i)$是Hinge损失函数，$\Vert w\Vert ^2$可看做为正则化项。

2.11.3 逻辑回归为什么使用对数损失函数

假设逻辑回归模型

假设逻辑回归模型的概率分布是伯努利分布，其概率质量函数为：

其似然函数为：

对数似然函数为：

对数函数在单个数据点上的定义为：

则全局样本损失函数为：

由此可看出，对数损失函数与极大似然估计的对数似然函数本质上是相同的。所以逻辑回归直接采用对数损失函数。

2.11.4 对数损失函数是如何度量损失的

​ 例如，在高斯分布中，我们需要确定均值和标准差。
​ 如何确定这两个参数？最大似然估计是比较常用的方法。最大似然的目标是找到一些参数值，这些参数值对应的分布可以最大化观测到数据的概率。
​ 因为需要计算观测到所有数据的全概率，即所有观测到的数据点的联合概率。现考虑如下简化情况：

（1）假设观测到每个数据点的概率和其他数据点的概率是独立的。

（2）取自然对数。
假设观测到单个数据点$x_i(i=1,2,…n)$的概率为：

（3）其联合概率为：

​ 对上式取自然对数，可得：

根据对数定律，上式可以化简为：

然后求导为：

​ 上式左半部分为对数损失函数。损失函数越小越好，因此我们令等式左半的对数损失函数为0，可得：

同理，可计算$\sigma ​$。

2.12 梯度下降

2.12.1 机器学习中为什么需要梯度下降

梯度下降是机器学习中常见优化算法之一，梯度下降法有以下几个作用：

（1）梯度下降是迭代法的一种，可以用于求解最小二乘问题。

（2）在求解机器学习算法的模型参数，即无约束优化问题时，主要有梯度下降法（Gradient Descent）和最小二乘法。

（3）在求解损失函数的最小值时，可以通过梯度下降法来一步步的迭代求解，得到最小化的损失函数和模型参数值。

（4）如果我们需要求解损失函数的最大值，可通过梯度上升法来迭代。梯度下降法和梯度上升法可相互转换。

（5）在机器学习中，梯度下降法主要有随机梯度下降法和批量梯度下降法。

2.12.2 梯度下降法缺点

梯度下降法缺点有以下几点：

（1）靠近极小值时收敛速度减慢。

（2）直线搜索时可能会产生一些问题。

（3）可能会“之字形”地下降。

梯度概念也有需注意的地方：

（1）梯度是一个向量，即有方向有大小。

（2）梯度的方向是最大方向导数的方向。

（3）梯度的值是最大方向导数的值。

2.12.3 梯度下降法直观理解

梯度下降法经典图示如下图2.7所示：

​ 图2.7 梯度下降法经典图示

​ 形象化举例，由上图2.7所示，假如最开始，我们在一座大山上的某处位置，因为到处都是陌生的，不知道下山的路，所以只能摸索着根据直觉，走一步算一步，在此过程中，每走到一个位置的时候，都会求解当前位置的梯度，沿着梯度的负方向，也就是当前最陡峭的位置向下走一步，然后继续求解当前位置梯度，向这一步所在位置沿着最陡峭最易下山的位置走一步。不断循环求梯度，就这样一步步地走下去，一直走到我们觉得已经到了山脚。当然这样走下去，有可能我们不能走到山脚，而是到了某一个局部的山势低处。
​ 由此，从上面的解释可以看出，梯度下降不一定能够找到全局的最优解，有可能是一个局部的最优解。当然，如果损失函数是凸函数，梯度下降法得到的解就一定是全局最优解。

核心思想归纳：

（1）初始化参数，随机选取取值范围内的任意数；

（2）迭代操作：
a）计算当前梯度；
b）修改新的变量；
c）计算朝最陡的下坡方向走一步；
d）判断是否需要终止，如否，返回a）；

（3）得到全局最优解或者接近全局最优解。

2.12.4 梯度下降法算法描述

梯度下降法算法步骤如下：

（1）确定优化模型的假设函数及损失函数。
​ 举例，对于线性回归，假设函数为：

其中，$\theta_i,x_i(i=0,1,2,…,n)$分别为模型参数、每个样本的特征值。
对于假设函数，损失函数为：

（2）相关参数初始化。
​ 主要初始化${\theta}_i$、算法迭代步长${\alpha} $、终止距离${\zeta} $。初始化时可以根据经验初始化，即${\theta} $初始化为0，步长${\alpha} $初始化为1。当前步长记为${\varphi}_i $。当然，也可随机初始化。

（3）迭代计算。

​ 1）计算当前位置时损失函数的梯度，对${\theta}_i $，其梯度表示为：

​ 2）计算当前位置下降的距离。

​ 3）判断是否终止。
​ 确定是否所有${\theta}_i$梯度下降的距离${\varphi}_i$都小于终止距离${\zeta}$，如果都小于${\zeta}$，则算法终止，当然的值即为最终结果，否则进入下一步。
​ 4）更新所有的${\theta}_i$，更新后的表达式为：

​ 5）令上式$x^{(j)}_0=1$，更新完毕后转入1)。
​ 由此，可看出，当前位置的梯度方向由所有样本决定，上式中 $\frac{1}{m}​$、$\alpha \frac{1}{m}​$ 的目的是为了便于理解。

2.12.5 如何对梯度下降法进行调优

实际使用梯度下降法时，各项参数指标不能一步就达到理想状态，对梯度下降法调优主要体现在以下几个方面：

（1）算法迭代步长$\alpha$选择。
在算法参数初始化时，有时根据经验将步长初始化为1。实际取值取决于数据样本。可以从大到小，多取一些值，分别运行算法看迭代效果，如果损失函数在变小，则取值有效。如果取值无效，说明要增大步长。但步长太大，有时会导致迭代速度过快，错过最优解。步长太小，迭代速度慢，算法运行时间长。

（2）参数的初始值选择。
初始值不同，获得的最小值也有可能不同，梯度下降有可能得到的是局部最小值。如果损失函数是凸函数，则一定是最优解。由于有局部最优解的风险，需要多次用不同初始值运行算法，关键损失函数的最小值，选择损失函数最小化的初值。

（3）标准化处理。
由于样本不同，特征取值范围也不同，导致迭代速度慢。为了减少特征取值的影响，可对特征数据标准化，使新期望为0，新方差为1，可节省算法运行时间。

2.12.6 随机梯度和批量梯度区别

​ 随机梯度下降（SDG）和批量梯度下降（BDG）是两种主要梯度下降法，其目的是增加某些限制来加速运算求解。
下面通过介绍两种梯度下降法的求解思路，对其进行比较。
假设函数为：

损失函数为：

其中，$m​$为样本个数，$j​$为参数个数。

1、 批量梯度下降的求解思路如下：
a) 得到每个$ \theta ​$对应的梯度：

b) 由于是求最小化风险函数，所以按每个参数 $ \theta ​$ 的梯度负方向更新 $ \theta_i ​$ ：

c) 从上式可以注意到，它得到的虽然是一个全局最优解，但每迭代一步，都要用到训练集所有的数据，如果样本数据很大，这种方法迭代速度就很慢。
相比而言，随机梯度下降可避免这种问题。

2、随机梯度下降的求解思路如下：
a) 相比批量梯度下降对应所有的训练样本，随机梯度下降法中损失函数对应的是训练集中每个样本的粒度。
损失函数可以写成如下这种形式，

b）对每个参数 $ \theta​$ 按梯度方向更新 $ \theta​$：

c) 随机梯度下降是通过每个样本来迭代更新一次。
随机梯度下降伴随的一个问题是噪音较批量梯度下降要多，使得随机梯度下降并不是每次迭代都向着整体最优化方向。

小结：
随机梯度下降法、批量梯度下降法相对来说都比较极端，简单对比如下：

下面介绍能结合两种方法优点的小批量梯度下降法。

3、 小批量（Mini-Batch）梯度下降的求解思路如下
对于总数为$m$个样本的数据，根据样本的数据，选取其中的$n(1< n< m)$个子样本来迭代。其参数$\theta$按梯度方向更新$\theta_i$公式如下：

2.12.7 各种梯度下降法性能比较

​ 下表简单对比随机梯度下降（SGD）、批量梯度下降（BGD）、小批量梯度下降（Mini-batch GD）、和Online GD的区别：

BGD、SGD、Mini-batch GD，前面均已讨论过，这里介绍一下Online GD。

​ Online GD于Mini-batch GD/SGD的区别在于，所有训练数据只用一次，然后丢弃。这样做的优点在于可预测最终模型的变化趋势。

​ Online GD在互联网领域用的较多，比如搜索广告的点击率（CTR）预估模型，网民的点击行为会随着时间改变。用普通的BGD算法（每天更新一次）一方面耗时较长（需要对所有历史数据重新训练）；另一方面，无法及时反馈用户的点击行为迁移。而Online GD算法可以实时的依据网民的点击行为进行迁移。

2.14 线性判别分析（LDA）

2.14.1 LDA思想总结

​ 线性判别分析（Linear Discriminant Analysis，LDA）是一种经典的降维方法。和主成分分析PCA不考虑样本类别输出的无监督降维技术不同，LDA是一种监督学习的降维技术，数据集的每个样本有类别输出。

LDA分类思想简单总结如下：

1. 多维空间中，数据处理分类问题较为复杂，LDA算法将多维空间中的数据投影到一条直线上，将d维数据转化成1维数据进行处理。
2. 对于训练数据，设法将多维数据投影到一条直线上，同类数据的投影点尽可能接近，异类数据点尽可能远离。
3. 对数据进行分类时，将其投影到同样的这条直线上，再根据投影点的位置来确定样本的类别。

如果用一句话概括LDA思想，即“投影后类内方差最小，类间方差最大”。

2.14.2 图解LDA核心思想

​ 假设有红、蓝两类数据，这些数据特征均为二维，如下图所示。我们的目标是将这些数据投影到一维，让每一类相近的数据的投影点尽可能接近，不同类别数据尽可能远，即图中红色和蓝色数据中心之间的距离尽可能大。

左图和右图是两种不同的投影方式。

​ 左图思路：让不同类别的平均点距离最远的投影方式。

​ 右图思路：让同类别的数据挨得最近的投影方式。

​ 从上图直观看出，右图红色数据和蓝色数据在各自的区域来说相对集中，根据数据分布直方图也可看出，所以右图的投影效果好于左图，左图中间直方图部分有明显交集。

​ 以上例子是基于数据是二维的，分类后的投影是一条直线。如果原始数据是多维的，则投影后的分类面是一低维的超平面。

2.14.3 二类LDA算法原理

​ 输入：数据集 $D={(\boldsymbol x_1,\boldsymbol y_1),(\boldsymbol x_2,\boldsymbol y_2),…,(\boldsymbol x_m,\boldsymbol y_m)}​$，其中样本 $\boldsymbol x_i ​$ 是n维向量，$\boldsymbol y_i \epsilon {0, 1}​$，降维后的目标维度 $d​$。定义

​ $N_j(j=0,1)$ 为第 $j$ 类样本个数；

​ $X_j(j=0,1)$ 为第 $j$ 类样本的集合；

​ $u_j(j=0,1)​$ 为第 $j​$ 类样本的均值向量；

​ $\sum_j(j=0,1)$ 为第 $j$ 类样本的协方差矩阵。

​ 其中

​ 假设投影直线是向量 $\boldsymbol w$，对任意样本 $\boldsymbol x_i$，它在直线 $w$上的投影为 $\boldsymbol w^Tx_i$，两个类别的中心点 $u_0$, $u_1 $在直线 $w$ 的投影分别为 $\boldsymbol w^Tu_0$ 、$\boldsymbol w^Tu_1$。

​ LDA的目标是让两类别的数据中心间的距离 $| \boldsymbol w^Tu_0 - \boldsymbol w^Tu_1 |^2_2$ 尽量大，与此同时，希望同类样本投影点的协方差$\boldsymbol w^T \sum_0 \boldsymbol w$、$\boldsymbol w^T \sum_1 \boldsymbol w$ 尽量小，最小化 $\boldsymbol w^T \sum_0 \boldsymbol w + \boldsymbol w^T \sum_1 \boldsymbol w​$ 。
​ 定义
​ 类内散度矩阵

​ 类间散度矩阵 $S_b = (u_0 - u_1)(u_0 - u_1)^T$

​ 据上分析，优化目标为

​ 根据广义瑞利商的性质，矩阵 $S^{-1}{w} S_b$ 的最大特征值为 $J(\boldsymbol w)$ 的最大值，矩阵 $S^{-1}{w} S_b$ 的最大特征值对应的特征向量即为 $\boldsymbol w$。

2.14.4 LDA算法流程总结

LDA算法降维流程如下：

​ 输入：数据集 $D = { (x_1,y_1),(x_2,y_2), … ,(x_m,y_m) }$，其中样本 $x_i $ 是n维向量，$y_i \epsilon {C_1, C_2, …, C_k}$，降维后的目标维度 $d$ 。

​ 输出：降维后的数据集 $\overline{D} $ 。

步骤：

1. 计算类内散度矩阵 $S_w$。
2. 计算类间散度矩阵 $S_b​$ 。
3. 计算矩阵 $S^{-1}_wS_b​$ 。
4. 计算矩阵 $S^{-1}_wS_b$ 的最大的 d 个特征值。
5. 计算 d 个特征值对应的 d 个特征向量，记投影矩阵为 W 。
6. 转化样本集的每个样本，得到新样本 $P_i = W^Tx_i​$ 。
7. 输出新样本集 $\overline{D} = { (p_1,y_1),(p_2,y_2),…,(p_m,y_m) }​$

2.14.5 LDA和PCA区别

2.14.6 LDA优缺点

2.15 主成分分析（PCA）

2.15.1 主成分分析（PCA）思想总结

1. PCA就是将高维的数据通过线性变换投影到低维空间上去。
2. 投影思想：找出最能够代表原始数据的投影方法。被PCA降掉的那些维度只能是那些噪声或是冗余的数据。
3. 去冗余：去除可以被其他向量代表的线性相关向量，这部分信息量是多余的。
4. 去噪声，去除较小特征值对应的特征向量，特征值的大小反映了变换后在特征向量方向上变换的幅度，幅度越大，说明这个方向上的元素差异也越大，要保留。
5. 对角化矩阵，寻找极大线性无关组，保留较大的特征值，去除较小特征值，组成一个投影矩阵，对原始样本矩阵进行投影，得到降维后的新样本矩阵。
6. 完成PCA的关键是——协方差矩阵。协方差矩阵，能同时表现不同维度间的相关性以及各个维度上的方差。协方差矩阵度量的是维度与维度之间的关系，而非样本与样本之间。
7. 之所以对角化，因为对角化之后非对角上的元素都是0，达到去噪声的目的。对角化后的协方差矩阵，对角线上较小的新方差对应的就是那些该去掉的维度。所以我们只取那些含有较大能量(特征值)的维度，其余的就舍掉，即去冗余。

2.15.2 图解PCA核心思想

​ PCA可解决训练数据中存在数据特征过多或特征累赘的问题。核心思想是将m维特征映射到n维（n < m），这n维形成主元，是重构出来最能代表原始数据的正交特征。

​ 假设数据集是m个n维，$(\boldsymbol x^{(1)}, \boldsymbol x^{(2)}, \cdots, \boldsymbol x^{(m)})$。如果$n=2$，需要降维到$n’=1$，现在想找到某一维度方向代表这两个维度的数据。下图有$u_1, u_2$两个向量方向，但是哪个向量才是我们所想要的，可以更好代表原始数据集的呢？

从图可看出，$u_1$比$u_2$好，为什么呢？有以下两个主要评价指标：

1. 样本点到这个直线的距离足够近。
2. 样本点在这个直线上的投影能尽可能的分开。

如果我们需要降维的目标维数是其他任意维，则：

1. 样本点到这个超平面的距离足够近。
2. 样本点在这个超平面上的投影能尽可能的分开。

2.15.3 PCA算法推理

下面以基于最小投影距离为评价指标推理：

​ 假设数据集是m个n维，$(x^{(1)}, x^{(2)},…,x^{(m)})$，且数据进行了中心化。经过投影变换得到新坐标为 ${w_1,w_2,…,w_n}$，其中 $w$ 是标准正交基，即 $| w |_2 = 1$，$w^T_iw_j = 0$。

​ 经过降维后，新坐标为 ${ w1,w_2,…,w_n }$，其中 $n’$ 是降维后的目标维数。样本点 $x^{(i)}$ 在新坐标系下的投影为 $z^{(i)} = \left(z^{(i)}_1, z^{(i)}_2, …, z^{(i)}{n’} \right)$，其中 $z^{(i)}_j = w^T_j x^{(i)}$ 是 $x^{(i)} ​$ 在低维坐标系里第 j 维的坐标。

​ 如果用 $z^{(i)} $ 去恢复 $x^{(i)} $ ，则得到的恢复数据为 $\widehat{x}^{(i)} = \sum^{n’}_{j=1} x^{(i)}_j w_j = Wz^{(i)}$，其中 $W$为标准正交基组成的矩阵。

​ 考虑到整个样本集，样本点到这个超平面的距离足够近，目标变为最小化 $\sum^m_{i=1} | \hat{x}^{(i)} - x^{(i)} |^2_2$ 。对此式进行推理，可得：

​ 在推导过程中，分别用到了 $\overline{x}^{(i)} = Wz^{(i)}$ ，矩阵转置公式 $(AB)^T = B^TA^T$，$W^TW = I$，$z^{(i)} = W^Tx^{(i)}$ 以及矩阵的迹，最后两步是将代数和转为矩阵形式。
​ 由于 $W$ 的每一个向量 $wj$ 是标准正交基，$\sum^m{i=1} x^{(i)} \left( x^{(i)} \right)^T$ 是数据集的协方差矩阵，$\sum^m{i=1} \left( x^{(i)} \right)^T x^{(i)} $ 是一个常量。最小化 $\sum^m{i=1} | \hat{x}^{(i)} - x^{(i)} |^2_2$ 又可等价于

利用拉格朗日函数可得到

​ 对 $W$ 求导，可得 $-XX^TW + \lambda W = 0 $ ，也即 $ XX^TW = \lambda W $ 。 $ XX^T $ 是 $ n’ $ 个特征向量组成的矩阵，$\lambda$ 为$ XX^T $ 的特征值。$W$ 即为我们想要的矩阵。
​ 对于原始数据，只需要 $z^{(i)} = W^TX^{(i)}$ ，就可把原始数据集降维到最小投影距离的 $n’$ 维数据集。

​ 基于最大投影方差的推导，这里就不再赘述，有兴趣的同仁可自行查阅资料。

2.15.4 PCA算法流程总结

输入：$n​$ 维样本集 $D = \left( x^{(1)},x^{(2)},…,x^{(m)} \right)​$ ，目标降维的维数 $n’​$ 。

输出：降维后的新样本集 $D’ = \left( z^{(1)},z^{(2)},…,z^{(m)} \right)$ 。

主要步骤如下：

1. 对所有的样本进行中心化，$ x^{(i)} = x^{(i)} - \frac{1}{m} \sum^m_{j=1} x^{(j)} $ 。
2. 计算样本的协方差矩阵 $XX^T​$ 。
3. 对协方差矩阵 $XX^T$ 进行特征值分解。
4. 取出最大的 $n’ $ 个特征值对应的特征向量 ${ w1,w_2,…,w{n’} }$ 。
5. 标准化特征向量，得到特征向量矩阵 $W$ 。
6. 转化样本集中的每个样本 $z^{(i)} = W^T x^{(i)}$ 。
7. 得到输出矩阵 $D’ = \left( z^{(1)},z^{(2)},…,z^{(n)} \right)​$ 。
   注：在降维时，有时不明确目标维数，而是指定降维到的主成分比重阈值 $k(k \epsilon(0,1])​$ 。假设 $n​$ 个特征值为 $\lambda1 \geqslant \lambda_2 \geqslant … \geqslant \lambda_n​$ ，则 $n’​$ 可从 $\sum^{n’}{i=1} \lambdai \geqslant k \times \sum^n{i=1} \lambda_i ​$ 得到。

2.15.5 PCA算法主要优缺点

2.15.6 降维的必要性及目的

降维的必要性：

1. 多重共线性和预测变量之间相互关联。多重共线性会导致解空间的不稳定，从而可能导致结果的不连贯。
2. 高维空间本身具有稀疏性。一维正态分布有68%的值落于正负标准差之间，而在十维空间上只有2%。
3. 过多的变量，对查找规律造成冗余麻烦。
4. 仅在变量层面上分析可能会忽略变量之间的潜在联系。例如几个预测变量可能落入仅反映数据某一方面特征的一个组内。

降维的目的：

1. 减少预测变量的个数。
2. 确保这些变量是相互独立的。
3. 提供一个框架来解释结果。相关特征，特别是重要特征更能在数据中明确的显示出来；如果只有两维或者三维的话，更便于可视化展示。
4. 数据在低维下更容易处理、更容易使用。
5. 去除数据噪声。
6. 降低算法运算开销。

2.15.7 KPCA与PCA的区别

​ 应用PCA算法前提是假设存在一个线性超平面，进而投影。那如果数据不是线性的呢？该怎么办？这时候就需要KPCA，数据集从 $n$ 维映射到线性可分的高维 $N >n$，然后再从 $N$ 维降维到一个低维度 $n’(n’<n<N)$ 。

​ KPCA用到了核函数思想，使用了核函数的主成分分析一般称为核主成分分析(Kernelized PCA, 简称KPCA）。

假设高维空间数据由 $n​$ 维空间的数据通过映射 $\phi​$ 产生。

​ $n$ 维空间的特征分解为：

​ 其映射为

​ 通过在高维空间进行协方差矩阵的特征值分解，然后用和PCA一样的方法进行降维。由于KPCA需要核函数的运算，因此它的计算量要比PCA大很多。

2.16 模型评估

2.16.1 模型评估常用方法？

​ 一般情况来说，单一评分标准无法完全评估一个机器学习模型。只用good和bad偏离真实场景去评估某个模型，都是一种欠妥的评估方式。下面介绍常用的分类模型和回归模型评估方法。

分类模型常用评估方法：

回归模型常用评估方法：

2.16.2 误差、偏差和方差有什么区别和联系

在机器学习中，Bias(偏差)，Error(误差)，和Variance(方差)存在以下区别和联系：

对于Error ：

• 误差（error）：一般地，我们把学习器的实际预测输出与样本的真是输出之间的差异称为“误差”。

• Error = Bias + Variance + Noise，Error反映的是整个模型的准确度。

对于Noise:

噪声：描述了在当前任务上任何学习算法所能达到的期望泛化误差的下界，即刻画了学习问题本身的难度。

对于Bias：

• Bias衡量模型拟合训练数据的能力（训练数据不一定是整个 training dataset，而是只用于训练它的那一部分数据，例如：mini-batch），Bias反映的是模型在样本上的输出与真实值之间的误差，即模型本身的精准度。
• Bias 越小，拟合能力越高（可能产生overfitting）；反之，拟合能力越低（可能产生underfitting）。
• 偏差越大，越偏离真实数据，如下图第二行所示。

对于Variance：

• 方差公式：$S{N}^{2}=\frac{1}{N}\sum{i=1}^{N}(x_{i}-\bar{x})^{2}$

• Variance描述的是预测值的变化范围，离散程度，也就是离其期望值的距离。方差越大，数据的分布越分散，模型的稳定程度越差。

• Variance反映的是模型每一次输出结果与模型输出期望之间的误差，即模型的稳定性。
• Variance越小，模型的泛化的能力越高；反之，模型的泛化的能力越低。
• 如果模型在训练集上拟合效果比较优秀，但是在测试集上拟合效果比较差劣，则方差较大，说明模型的稳定程度较差，出现这种现象可能是由于模型对训练集过拟合造成的。 如下图右列所示。

2.16.3 经验误差与泛化误差

经验误差（empirical error）：也叫训练误差（training error），模型在训练集上的误差。

泛化误差（generalization error）：模型在新样本集（测试集）上的误差称为“泛化误差”。

2.16.4 图解欠拟合、过拟合

根据不同的坐标方式，欠拟合与过拟合图解不同。

1. 横轴为训练样本数量，纵轴为误差

如上图所示，我们可以直观看出欠拟合和过拟合的区别：

​ 模型欠拟合：在训练集以及测试集上同时具有较高的误差，此时模型的偏差较大；

​ 模型过拟合：在训练集上具有较低的误差，在测试集上具有较高的误差，此时模型的方差较大。

​ 模型正常：在训练集以及测试集上，同时具有相对较低的偏差以及方差。

1. 横轴为模型复杂程度，纵轴为误差

​ 红线为测试集上的Error,蓝线为训练集上的Error

​ 模型欠拟合：模型在点A处，在训练集以及测试集上同时具有较高的误差，此时模型的偏差较大。

​ 模型过拟合：模型在点C处，在训练集上具有较低的误差，在测试集上具有较高的误差，此时模型的方差较大。

​ 模型正常：模型复杂程度控制在点B处为最优。

1. 横轴为正则项系数，纵轴为误差

​ 红线为测试集上的Error,蓝线为训练集上的Error

​ 模型欠拟合：模型在点C处，在训练集以及测试集上同时具有较高的误差，此时模型的偏差较大。

​ 模型过拟合：模型在点A处，在训练集上具有较低的误差，在测试集上具有较高的误差，此时模型的方差较大。 它通常发生在模型过于复杂的情况下，如参数过多等，会使得模型的预测性能变弱，并且增加数据的波动性。虽然模型在训练时的效果可以表现的很完美，基本上记住了数据的全部特点，但这种模型在未知数据的表现能力会大减折扣，因为简单的模型泛化能力通常都是很弱的。

​ 模型正常：模型复杂程度控制在点B处为最优。

2.16.5 如何解决过拟合与欠拟合

如何解决欠拟合：

1. 添加其他特征项。组合、泛化、相关性、上下文特征、平台特征等特征是特征添加的重要手段，有时候特征项不够会导致模型欠拟合。
2. 添加多项式特征。例如将线性模型添加二次项或三次项使模型泛化能力更强。例如，FM（Factorization Machine）模型、FFM（Field-aware Factorization Machine）模型，其实就是线性模型，增加了二阶多项式，保证了模型一定的拟合程度。
3. 可以增加模型的复杂程度。
4. 减小正则化系数。正则化的目的是用来防止过拟合的，但是现在模型出现了欠拟合，则需要减少正则化参数。

如何解决过拟合：

1. 重新清洗数据，数据不纯会导致过拟合，此类情况需要重新清洗数据。
2. 增加训练样本数量。
3. 降低模型复杂程度。
4. 增大正则项系数。
5. 采用dropout方法，dropout方法，通俗的讲就是在训练的时候让神经元以一定的概率不工作。
6. early stopping。
7. 减少迭代次数。
8. 增大学习率。
9. 添加噪声数据。
10. 树结构中，可以对树进行剪枝。
11. 减少特征项。

欠拟合和过拟合这些方法，需要根据实际问题，实际模型，进行选择。

2.16.6 交叉验证的主要作用

​ 为了得到更为稳健可靠的模型，对模型的泛化误差进行评估，得到模型泛化误差的近似值。当有多个模型可以选择时，我们通常选择“泛化误差”最小的模型。

​ 交叉验证的方法有许多种，但是最常用的是：留一交叉验证、k折交叉验证。

2.16.7 理解k折交叉验证

1. 将含有N个样本的数据集，分成K份，每份含有N/K个样本。选择其中1份作为测试集，另外K-1份作为训练集，测试集就有K种情况。
2. 在每种情况中，用训练集训练模型，用测试集测试模型，计算模型的泛化误差。
3. 交叉验证重复K次，每份验证一次，平均K次的结果或者使用其它结合方式，最终得到一个单一估测，得到模型最终的泛化误差。
4. 将K种情况下，模型的泛化误差取均值，得到模型最终的泛化误差。
5. 一般$2\leqslant K \leqslant10$。 k折交叉验证的优势在于，同时重复运用随机产生的子样本进行训练和验证，每次的结果验证一次，10折交叉验证是最常用的。
6. 训练集中样本数量要足够多，一般至少大于总样本数的50%。
7. 训练集和测试集必须从完整的数据集中均匀取样。均匀取样的目的是希望减少训练集、测试集与原数据集之间的偏差。当样本数量足够多时，通过随机取样，便可以实现均匀取样的效果。

2.16.8 混淆矩阵

第一种混淆矩阵:

第二种混淆矩阵:

2.16.9 错误率及精度

1. 错误率（Error Rate）：分类错误的样本数占样本总数的比例。
2. 精度（accuracy）：分类正确的样本数占样本总数的比例。

2.16.10 查准率与查全率

将算法预测的结果分成四种情况：

1. 正确肯定（True Positive,TP）：预测为真，实际为真
2. 正确否定（True Negative,TN）：预测为假，实际为假
3. 错误肯定（False Positive,FP）：预测为真，实际为假
4. 错误否定（False Negative,FN）：预测为假，实际为真

则：

查准率（Precision）=TP/（TP+FP）

理解：预测出为阳性的样本中，正确的有多少。区别准确率（正确预测出的样本，包括正确预测为阳性、阴性，占总样本比例）。
例，在所有我们预测有恶性肿瘤的病人中，实际上有恶性肿瘤的病人的百分比，越高越好。

查全率（Recall）=TP/（TP+FN）

理解：正确预测为阳性的数量占总样本中阳性数量的比例。
例，在所有实际上有恶性肿瘤的病人中，成功预测有恶性肿瘤的病人的百分比，越高越好。

2.16.11 ROC与AUC

​ ROC全称是“受试者工作特征”（Receiver Operating Characteristic）。

​ ROC曲线的面积就是AUC（Area Under Curve）。

​ AUC用于衡量“二分类问题”机器学习算法性能（泛化能力）。

​ ROC曲线，通过将连续变量设定出多个不同的临界值，从而计算出一系列真正率和假正率，再以假正率为横坐标、真正率为纵坐标绘制成曲线，曲线下面积越大，推断准确性越高。在ROC曲线上，最靠近坐标图左上方的点为假正率和真正率均较高的临界值。

​ 对于分类器，或者说分类算法，评价指标主要有Precision，Recall，F-score。下图是一个ROC曲线的示例。

ROC曲线的横坐标为False Positive Rate（FPR），纵坐标为True Positive Rate（TPR）。其中

​ 下面着重介绍ROC曲线图中的四个点和一条线。
​ 第一个点(0,1)，即FPR=0, TPR=1，这意味着FN（False Negative）=0，并且FP（False Positive）=0。意味着这是一个完美的分类器，它将所有的样本都正确分类。
​ 第二个点(1,0)，即FPR=1，TPR=0，意味着这是一个最糟糕的分类器，因为它成功避开了所有的正确答案。
​ 第三个点(0,0)，即FPR=TPR=0，即FP（False Positive）=TP（True Positive）=0，可以发现该分类器预测所有的样本都为负样本（Negative）。
​ 第四个点(1,1)，即FPR=TPR=1，分类器实际上预测所有的样本都为正样本。
​ 经过以上分析，ROC曲线越接近左上角，该分类器的性能越好。

​ ROC曲线所覆盖的面积称为AUC（Area Under Curve），可以更直观的判断学习器的性能，AUC越大则性能越好。

2.16.12 如何画ROC曲线

​ 下图是一个示例，图中共有20个测试样本，“Class”一栏表示每个测试样本真正的标签（p表示正样本，n表示负样本），“Score”表示每个测试样本属于正样本的概率。

步骤：
1、假设已经得出一系列样本被划分为正类的概率，按照大小排序。
2、从高到低，依次将“Score”值作为阈值threshold，当测试样本属于正样本的概率大于或等于这个threshold时，我们认为它为正样本，否则为负样本。举例来说，对于图中的第4个样本，其“Score”值为0.6，那么样本1，2，3，4都被认为是正样本，因为它们的“Score”值都大于等于0.6，而其他样本则都认为是负样本。
3、每次选取一个不同的threshold，得到一组FPR和TPR，即ROC曲线上的一点。以此共得到20组FPR和TPR的值。
4、根据3、中的每个坐标点，画图。

2.16.13 如何计算TPR，FPR

1、分析数据
y_true = [0, 0, 1, 1]；scores = [0.1, 0.4, 0.35, 0.8]；
2、列表

3、将截断点依次取为score值，计算TPR和FPR。
当截断点为0.1时：
说明只要score>=0.1，它的预测类别就是正例。 因为4个样本的score都大于等于0.1，所以，所有样本的预测类别都为P。
scores = [0.1, 0.4, 0.35, 0.8]；y_true = [0, 0, 1, 1]；y_pred = [1, 1, 1, 1]；
正例与反例信息如下：

由此可得：
TPR = TP/(TP+FN) = 1； FPR = FP/(TN+FP) = 1；

当截断点为0.35时：
scores = [0.1, 0.4, 0.35, 0.8]；y_true = [0, 0, 1, 1]；y_pred = [0, 1, 1, 1];
正例与反例信息如下：

由此可得：
TPR = TP/(TP+FN) = 1； FPR = FP/(TN+FP) = 0.5；

当截断点为0.4时：
scores = [0.1, 0.4, 0.35, 0.8]；y_true = [0, 0, 1, 1]；y_pred = [0, 1, 0, 1]；
正例与反例信息如下：

由此可得：
TPR = TP/(TP+FN) = 0.5； FPR = FP/(TN+FP) = 0.5；

当截断点为0.8时：
scores = [0.1, 0.4, 0.35, 0.8]；y_true = [0, 0, 1, 1]；y_pred = [0, 0, 0, 1]；

正例与反例信息如下：

由此可得：
TPR = TP/(TP+FN) = 0.5； FPR = FP/(TN+FP) = 0；

4、根据TPR、FPR值，以FPR为横轴，TPR为纵轴画图。

2.16.14 如何计算AUC

• 将坐标点按照横坐标FPR排序 。
• 计算第$i$个坐标点和第$i+1$个坐标点的间距$dx$ 。
• 获取第$i$或者$i+1$个坐标点的纵坐标y。
• 计算面积微元$ds=ydx$。
• 对面积微元进行累加，得到AUC。

2.16.15 为什么使用Roc和Auc评价分类器

​ 模型有很多评估方法，为什么还要使用ROC和AUC呢？
​ 因为ROC曲线有个很好的特性：当测试集中的正负样本的分布变换的时候，ROC曲线能够保持不变。在实际的数据集中经常会出现样本类不平衡，即正负样本比例差距较大，而且测试数据中的正负样本也可能随着时间变化。

2.16.16 直观理解AUC

​ 下图展现了三种AUC的值：

​ AUC是衡量二分类模型优劣的一种评价指标，表示正例排在负例前面的概率。其他评价指标有精确度、准确率、召回率，而AUC比这三者更为常用。
​ 一般在分类模型中，预测结果都是以概率的形式表现，如果要计算准确率，通常都会手动设置一个阈值来将对应的概率转化成类别，这个阈值也就很大程度上影响了模型准确率的计算。
​ 举例：
​ 现在假设有一个训练好的二分类器对10个正负样本（正例5个，负例5个）预测，得分按高到低排序得到的最好预测结果为[1, 1, 1, 1, 1, 0, 0, 0, 0, 0]，即5个正例均排在5个负例前面，正例排在负例前面的概率为100%。然后绘制其ROC曲线，由于是10个样本，除去原点我们需要描10个点，如下：

​ 描点方式按照样本预测结果的得分高低从左至右开始遍历。从原点开始，每遇到1便向y轴正方向移动y轴最小步长1个单位，这里是1/5=0.2；每遇到0则向x轴正方向移动x轴最小步长1个单位，这里也是0.2。不难看出，上图的AUC等于1，印证了正例排在负例前面的概率的确为100%。

​ 假设预测结果序列为[1, 1, 1, 1, 0, 1, 0, 0, 0, 0]。

​ 计算上图的AUC为0.96与计算正例与排在负例前面的概率0.8 × 1 + 0.2 × 0.8 = 0.96相等，而左上角阴影部分的面积则是负例排在正例前面的概率0.2 × 0.2 = 0.04。

​ 假设预测结果序列为[1, 1, 1, 0, 1, 0, 1, 0, 0, 0]。

​ 计算上图的AUC为0.88与计算正例与排在负例前面的概率0.6 × 1 + 0.2 × 0.8 + 0.2 × 0.6 = 0.88相等，左上角阴影部分的面积是负例排在正例前面的概率0.2 × 0.2 × 3 = 0.12。

2.16.17 代价敏感错误率与代价曲线

不同的错误会产生不同代价。以二分法为例，设置代价矩阵如下：

当判断正确的时候，值为0，不正确的时候，分别为$Cost{01}​$和$Cost{10}​$ 。

$Cost_{10}$:表示实际为反例但预测成正例的代价。

$Cost_{01}$:表示实际为正例但是预测为反例的代价。

代价敏感错误率=样本中由模型得到的错误值与代价乘积之和 / 总样本。
其数学表达式为：

$D^{+}、D^{-}​$分别代表样例集的正例子集和反例子集，x是预测值，y是真实值。

代价曲线：
在均等代价时，ROC曲线不能直接反应出模型的期望总体代价，而代价曲线可以。
代价曲线横轴为[0,1]的正例函数代价：

其中p是样本为正例的概率。

代价曲线纵轴维[0,1]的归一化代价：

其中FPR为假阳率，FNR=1-TPR为假阴率。

注：ROC每个点，对应代价平面上一条线。

例如，ROC上(TPR,FPR),计算出FNR=1-TPR，在代价平面上绘制一条从(0,FPR)到(1,FNR)的线段，面积则为该条件下期望的总体代价。所有线段下界面积，所有条件下学习器的期望总体代价。

2.16.18 模型有哪些比较检验方法

正确性分析：模型稳定性分析，稳健性分析，收敛性分析，变化趋势分析，极值分析等。
有效性分析：误差分析，参数敏感性分析，模型对比检验等。
有用性分析：关键数据求解，极值点，拐点，变化趋势分析，用数据验证动态模拟等。
高效性分析：时空复杂度分析与现有进行比较等。

2.16.19 为什么使用标准差

方差公式为：$S^2{N}=\frac{1}{N}\sum{i=1}^{N}(x_{i}-\bar{x})^{2}​$

标准差公式为：$S{N}=\sqrt{\frac{1}{N}\sum{i=1}^{N}(x_{i}-\bar{x})^{2}}​$

样本标准差公式为：$S{N}=\sqrt{\frac{1}{N-1}\sum{i=1}^{N}(x_{i}-\bar{x})^{2}}​$

与方差相比，使用标准差来表示数据点的离散程度有3个好处：
1、表示离散程度的数字与样本数据点的数量级一致，更适合对数据样本形成感性认知。

2、表示离散程度的数字单位与样本数据的单位一致，更方便做后续的分析运算。

3、在样本数据大致符合正态分布的情况下，标准差具有方便估算的特性：68%的数据点落在平均值前后1个标准差的范围内、95%的数据点落在平均值前后2个标准差的范围内，而99%的数据点将会落在平均值前后3个标准差的范围内。

2.16.20 类别不平衡产生原因

​ 类别不平衡（class-imbalance）是指分类任务中不同类别的训练样例数目差别很大的情况。

产生原因：

​ 分类学习算法通常都会假设不同类别的训练样例数目基本相同。如果不同类别的训练样例数目差别很大，则会影响学习结果，测试结果变差。例如二分类问题中有998个反例，正例有2个，那学习方法只需返回一个永远将新样本预测为反例的分类器，就能达到99.8%的精度；然而这样的分类器没有价值。

2.16.21 常见的类别不平衡问题解决方法

  防止类别不平衡对学习造成的影响，在构建分类模型之前，需要对分类不平衡性问题进行处理。主要解决方法有：

1、扩大数据集

​ 增加包含小类样本数据的数据，更多的数据能得到更多的分布信息。

2、对大类数据欠采样

​ 减少大类数据样本个数，使与小样本个数接近。
​ 缺点：欠采样操作时若随机丢弃大类样本，可能会丢失重要信息。
​ 代表算法：EasyEnsemble。其思想是利用集成学习机制，将大类划分为若干个集合供不同的学习器使用。相当于对每个学习器都进行欠采样，但对于全局则不会丢失重要信息。

3、对小类数据过采样

​ 过采样：对小类的数据样本进行采样来增加小类的数据样本个数。

​ 代表算法：SMOTE和ADASYN。

​ SMOTE：通过对训练集中的小类数据进行插值来产生额外的小类样本数据。

​ 新的少数类样本产生的策略：对每个少数类样本a，在a的最近邻中随机选一个样本b，然后在a、b之间的连线上随机选一点作为新合成的少数类样本。
​ ADASYN：根据学习难度的不同，对不同的少数类别的样本使用加权分布，对于难以学习的少数类的样本，产生更多的综合数据。 通过减少类不平衡引入的偏差和将分类决策边界自适应地转移到困难的样本两种手段，改善了数据分布。

4、使用新评价指标

​ 如果当前评价指标不适用，则应寻找其他具有说服力的评价指标。比如准确度这个评价指标在类别不均衡的分类任务中并不适用，甚至进行误导。因此在类别不均衡分类任务中，需要使用更有说服力的评价指标来对分类器进行评价。

5、选择新算法

​ 不同的算法适用于不同的任务与数据，应该使用不同的算法进行比较。

6、数据代价加权

​ 例如当分类任务是识别小类，那么可以对分类器的小类样本数据增加权值，降低大类样本的权值，从而使得分类器将重点集中在小类样本身上。

7、转化问题思考角度

​ 例如在分类问题时，把小类的样本作为异常点，将问题转化为异常点检测或变化趋势检测问题。 异常点检测即是对那些罕见事件进行识别。变化趋势检测区别于异常点检测在于其通过检测不寻常的变化趋势来识别。

8、将问题细化分析

​ 对问题进行分析与挖掘，将问题划分成多个更小的问题，看这些小问题是否更容易解决。

2.17 决策树

2.17.1 决策树的基本原理

​ 决策树（Decision Tree）是一种分而治之的决策过程。一个困难的预测问题，通过树的分支节点，被划分成两个或多个较为简单的子集，从结构上划分为不同的子问题。将依规则分割数据集的过程不断递归下去（Recursive Partitioning）。随着树的深度不断增加，分支节点的子集越来越小，所需要提的问题数也逐渐简化。当分支节点的深度或者问题的简单程度满足一定的停止规则（Stopping Rule）时, 该分支节点会停止分裂，此为自上而下的停止阈值（Cutoff Threshold）法；有些决策树也使用自下而上的剪枝（Pruning）法。

2.17.2 决策树的三要素？

​ 一棵决策树的生成过程主要分为下3个部分：

​ 1、特征选择：从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准，从而衍生出不同的决策树算法。

​ 2、决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则决策树停止生长。树结构来说，递归结构是最容易理解的方式。

​ 3、剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

2.17.3 决策树学习基本算法

2.17.4 决策树算法优缺点

决策树算法的优点：

1、决策树算法易理解，机理解释起来简单。

2、决策树算法可以用于小数据集。

3、决策树算法的时间复杂度较小，为用于训练决策树的数据点的对数。

4、相比于其他算法智能分析一种类型变量，决策树算法可处理数字和数据的类别。

5、能够处理多输出的问题。

6、对缺失值不敏感。

7、可以处理不相关特征数据。

8、效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。

决策树算法的缺点：

1、对连续性的字段比较难预测。

2、容易出现过拟合。

3、当类别太多时，错误可能就会增加的比较快。

4、在处理特征关联性比较强的数据时表现得不是太好。

5、对于各类别样本数量不一致的数据，在决策树当中，信息增益的结果偏向于那些具有更多数值的特征。

2.17.5 熵的概念以及理解

​ 熵：度量随机变量的不确定性。
​ 定义：假设随机变量X的可能取值有$x{1},x{2},…,x{n}$，对于每一个可能的取值$x{i}$，其概率为$P(X=x{i})=p{i},i=1,2…,n$。随机变量的熵为：

​ 对于样本集合，假设样本有k个类别，每个类别的概率为$\frac{|C{k}|}{|D|}$，其中 ${|C{k}|}{|D|}$为类别为k的样本个数，$|D|​$为样本总数。样本集合D的熵为：

2.17.6 信息增益的理解

​ 定义：以某特征划分数据集前后的熵的差值。
​ 熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。 ​ 假设划分前样本集合D的熵为H(D)。使用某个特征A划分数据集D，计算划分后的数据子集的熵为H(D|A)。
​ 则信息增益为：

​ 注：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。
​ 思想：计算所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。
​ 另外这里提一下信息增益比相关知识：
​ $信息增益比=惩罚参数\times信息增益$
​ 信息增益比本质：在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。
​ 惩罚参数：数据集D以特征A作为随机变量的熵的倒数。

2.17.7 剪枝处理的作用及策略

​ 剪枝处理是决策树学习算法用来解决过拟合问题的一种办法。

​ 在决策树算法中，为了尽可能正确分类训练样本， 节点划分过程不断重复， 有时候会造成决策树分支过多，以至于将训练样本集自身特点当作泛化特点， 而导致过拟合。 因此可以采用剪枝处理来去掉一些分支来降低过拟合的风险。

​ 剪枝的基本策略有预剪枝（pre-pruning）和后剪枝（post-pruning）。

​ 预剪枝：在决策树生成过程中，在每个节点划分前先估计其划分后的泛化性能， 如果不能提升，则停止划分，将当前节点标记为叶结点。

​ 后剪枝：生成决策树以后，再自下而上对非叶结点进行考察， 若将此节点标记为叶结点可以带来泛化性能提升，则修改之。

2.18 支持向量机

2.18.1 什么是支持向量机

​ 支持向量：在求解的过程中，会发现只根据部分数据就可以确定分类器，这些数据称为支持向量。

​ 支持向量机（Support Vector Machine，SVM）：其含义是通过支持向量运算的分类器。

​ 在一个二维环境中，其中点R，S，G点和其它靠近中间黑线的点可以看作为支持向量，它们可以决定分类器，即黑线的具体参数。

​ 支持向量机是一种二分类模型，它的目的是寻找一个超平面来对样本进行分割，分割的原则是边界最大化，最终转化为一个凸二次规划问题来求解。由简至繁的模型包括：

​ 当训练样本线性可分时，通过硬边界（hard margin）最大化，学习一个线性可分支持向量机；

​ 当训练样本近似线性可分时，通过软边界（soft margin）最大化，学习一个线性支持向量机；

​ 当训练样本线性不可分时，通过核技巧和软边界最大化，学习一个非线性支持向量机；

2.18.2 支持向量机能解决哪些问题

线性分类

​ 在训练数据中，每个数据都有n个的属性和一个二分类类别标志，我们可以认为这些数据在一个n维空间里。我们的目标是找到一个n-1维的超平面，这个超平面可以将数据分成两部分，每部分数据都属于同一个类别。

​ 这样的超平面有很多，假如我们要找到一个最佳的超平面。此时，增加一个约束条件：要求这个超平面到每边最近数据点的距离是最大的，成为最大边距超平面。这个分类器即为最大边距分类器。

非线性分类

​ SVM的一个优势是支持非线性分类。它结合使用拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件，以及核函数可以生成非线性分类器。

2.18.3 核函数特点及其作用

​ 引入核函数目的：把原坐标系里线性不可分的数据用核函数Kernel投影到另一个空间，尽量使得数据在新的空间里线性可分。
​ 核函数方法的广泛应用，与其特点是分不开的：

1）核函数的引入避免了“维数灾难”，大大减小了计算量。而输入空间的维数n对核函数矩阵无影响。因此，核函数方法可以有效处理高维输入。

2）无需知道非线性变换函数Φ的形式和参数。

3）核函数的形式和参数的变化会隐式地改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。

4）核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这两部分的设计可以单独进行，并可以为不同的应用选择不同的核函数和算法。

2.18.4 SVM为什么引入对偶问题

1，对偶问题将原始问题中的约束转为了对偶问题中的等式约束，对偶问题往往更加容易求解。

2，可以很自然的引用核函数（拉格朗日表达式里面有内积，而核函数也是通过内积进行映射的）。

3，在优化理论中，目标函数 f(x) 会有多种形式：如果目标函数和约束条件都为变量 x 的线性函数，称该问题为线性规划；如果目标函数为二次函数，约束条件为线性函数，称该最优化问题为二次规划；如果目标函数或者约束条件均为非线性函数，称该最优化问题为非线性规划。每个线性规划问题都有一个与之对应的对偶问题，对偶问题有非常良好的性质，以下列举几个：

​ a, 对偶问题的对偶是原问题；

​ b, 无论原始问题是否是凸的，对偶问题都是凸优化问题；

​ c, 对偶问题可以给出原始问题一个下界；

​ d, 当满足一定条件时，原始问题与对偶问题的解是完全等价的。

2.18.5 如何理解SVM中的对偶问题

在硬边界支持向量机中，问题的求解可以转化为凸二次规划问题。

​ 假设优化目标为

step 1. 转化问题：

上式等价于原问题，因为若满足(1)中不等式约束，则(2)式求max时,$\alpha_i(1 - y_i(\boldsymbol w^T\boldsymbol x_i+b))$必须取0，与(1)等价；若不满足(1)中不等式约束，(2)中求max会得到无穷大。 交换min和max获得其对偶问题:

交换之后的对偶问题和原问题并不相等，上式的解小于等于原问题的解。

step 2.现在的问题是如何找到问题(1) 的最优值的一个最好的下界?

若方程组(3)无解， 则v是问题(1)的一个下界。若(3)有解， 则

由逆否命题得：若

则(3)无解。

那么v是问题

(1)的一个下界。
要求得一个好的下界，取最大值即可

step 3. 令

$p^$为原问题的最小值，对应的$w,b$分别为$w^,b^*$,则对于任意的$a>0$:

则 $\min_{\boldsymbol w, b} L(\boldsymbol w, b,\boldsymbol a)$是问题（1）的一个下界。

此时，取最大值即可求得好的下界，即

2.18.7 常见的核函数有哪些

2.18.9 SVM主要特点

特点：

(1) SVM方法的理论基础是非线性映射，SVM利用内积核函数代替向高维空间的非线性映射。
(2) SVM的目标是对特征空间划分得到最优超平面，SVM方法核心是最大化分类边界。
(3) 支持向量是SVM的训练结果，在SVM分类决策中起决定作用的是支持向量。
(4) SVM是一种有坚实理论基础的新颖的适用小样本学习方法。它基本上不涉及概率测度及大数定律等，也简化了通常的分类和回归等问题。
(5) SVM的最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了“维数灾难”。
(6) 少数支持向量决定了最终结果，这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单，而且具有较好的“鲁棒性”。这种鲁棒性主要体现在：
​ ①增、删非支持向量样本对模型没有影响;
​ ②支持向量样本集具有一定的鲁棒性;
​ ③有些成功的应用中，SVM方法对核的选取不敏感
(7) SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。而其他分类方法（如基于规则的分类器和人工神经网络）都采用一种基于贪心学习的策略来搜索假设空间，这种方法一般只能获得局部最优解。
(8) SVM通过最大化决策边界的边缘来控制模型的能力。尽管如此，用户必须提供其他参数，如使用核函数类型和引入松弛变量等。
(9) SVM在小样本训练集上能够得到比其它算法好很多的结果。SVM优化目标是结构化风险最小，而不是经验风险最小，避免了过拟合问题，通过margin的概念，得到对数据分布的结构化描述，减低了对数据规模和数据分布的要求，有优秀的泛化能力。
(10) 它是一个凸优化问题，因此局部最优解一定是全局最优解的优点。

2.18.10 SVM主要缺点

(1) SVM算法对大规模训练样本难以实施
​ SVM的空间消耗主要是存储训练样本和核矩阵，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。
​ 如果数据量很大，SVM的训练时间就会比较长，如垃圾邮件的分类检测，没有使用SVM分类器，而是使用简单的朴素贝叶斯分类器，或者是使用逻辑回归模型分类。

(2) 用SVM解决多分类问题存在困难

​ 经典的支持向量机算法只给出了二类分类的算法，而在实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗糙集理论结合，形成一种优势互补的多类问题的组合分类器。

(3) 对缺失数据敏感，对参数和核函数的选择敏感

​ 支持向量机性能的优劣主要取决于核函数的选取，所以对于一个实际问题而言，如何根据实际的数据模型选择合适的核函数从而构造SVM算法。目前比较成熟的核函数及其参数的选择都是人为的，根据经验来选取的，带有一定的随意性。在不同的问题领域，核函数应当具有不同的形式和参数，所以在选取时候应该将领域知识引入进来，但是目前还没有好的方法来解决核函数的选取问题。

2.18.11 逻辑回归与SVM的异同

相同点：

• LR和SVM都是分类算法。
• LR和SVM都是监督学习算法。
• LR和SVM都是判别模型。
• 如果不考虑核函数，LR和SVM都是线性分类算法，也就是说他们的分类决策面都是线性的。
  说明：LR也是可以用核函数的.但LR通常不采用核函数的方法。（计算量太大）

不同点：

1、LR采用log损失，SVM采用合页(hinge)损失。
逻辑回归的损失函数：

支持向量机的目标函数:

​ 逻辑回归方法基于概率理论，假设样本为1的概率可以用sigmoid函数来表示，然后通过极大似然估计的方法估计出参数的值。
​ 支持向量机基于几何边界最大化原理，认为存在最大几何边界的分类面为最优分类面。

2、LR对异常值敏感，SVM对异常值不敏感。

​ 支持向量机只考虑局部的边界线附近的点，而逻辑回归考虑全局。LR模型找到的那个超平面，是尽量让所有点都远离他，而SVM寻找的那个超平面，是只让最靠近中间分割线的那些点尽量远离，即只用到那些支持向量的样本。
​ 支持向量机改变非支持向量样本并不会引起决策面的变化。
​ 逻辑回归中改变任何样本都会引起决策面的变化。

3、计算复杂度不同。对于海量数据，SVM的效率较低，LR效率比较高

​ 当样本较少，特征维数较低时，SVM和LR的运行时间均比较短，SVM较短一些。准确率的话，LR明显比SVM要高。当样本稍微增加些时，SVM运行时间开始增长，但是准确率赶超了LR。SVM时间虽长，但在可接受范围内。当数据量增长到20000时，特征维数增长到200时，SVM的运行时间剧烈增加，远远超过了LR的运行时间。但是准确率却和LR相差无几。(这其中主要原因是大量非支持向量参与计算，造成SVM的二次规划问题)

4、对非线性问题的处理方式不同

​ LR主要靠特征构造，必须组合交叉特征，特征离散化。SVM也可以这样，还可以通过核函数kernel（因为只有支持向量参与核计算，计算复杂度不高）。由于可以利用核函数，SVM则可以通过对偶求解高效处理。LR则在特征空间维度很高时，表现较差。

5、SVM的损失函数就自带正则。
​ 损失函数中的1/2||w||^2项，这就是为什么SVM是结构风险最小化算法的原因！！！而LR必须另外在损失函数上添加正则项！！！**

6、SVM自带结构风险最小化，LR则是经验风险最小化。

7、SVM会用核函数而LR一般不用核函数。

2.19 贝叶斯分类器

2.19.1 图解极大似然估计

极大似然估计的原理，用一张图片来说明，如下图所示：

​ 例：有两个外形完全相同的箱子，1号箱有99只白球，1只黑球；2号箱有1只白球，99只黑球。在一次实验中，取出的是黑球，请问是从哪个箱子中取出的？

​ 一般的根据经验想法，会猜测这只黑球最像是从2号箱取出，此时描述的“最像”就有“最大似然”的意思，这种想法常称为“最大似然原理”。

2.19.2 极大似然估计原理

​ 总结起来，最大似然估计的目的就是：利用已知的样本结果，反推最有可能（最大概率）导致这样结果的参数值。

​ 极大似然估计是建立在极大似然原理的基础上的一个统计方法。极大似然估计提供了一种给定观察数据来评估模型参数的方法，即：“模型已定，参数未知”。通过若干次试验，观察其结果，利用试验结果得到某个参数值能够使样本出现的概率为最大，则称为极大似然估计。

​ 由于样本集中的样本都是独立同分布，可以只考虑一类样本集$D$，来估计参数向量$\vec\theta$。记已知的样本集为：

似然函数（likelihood function）：联合概率密度函数$p(D|\vec\theta )$称为相对于$\vec x{1},\vec x{2},…,\vec x_{n}$的$\vec\theta$的似然函数。

如果$\hat{\vec\theta}$是参数空间中能使似然函数$l(\vec\theta)$最大的$\vec\theta$值，则$\hat{\vec\theta}$应该是“最可能”的参数值，那么$\hat{\vec\theta}​$就是$\theta$的极大似然估计量。它是样本集的函数，记作：

$\hat{\vec\theta}(\vec x{1},\vec x{2},…,\vec x_{n})$称为极大似然函数估计值。

2.19.3 贝叶斯分类器基本原理

​ 贝叶斯决策论通过相关概率已知的情况下利用误判损失来选择最优的类别分类。
假设有$N$种可能的分类标记，记为$Y={c_1,c_2,…,c_N}$，那对于样本$\boldsymbol{x}$，它属于哪一类呢？

计算步骤如下：

step 1. 算出样本$\boldsymbol{x}$属于第i个类的概率，即$P(c_i|x)​$；

step 2. 通过比较所有的$P(c_i|\boldsymbol{x})$，得到样本$\boldsymbol{x}$所属的最佳类别。

step 3. 将类别$c_i$和样本$\boldsymbol{x}$代入到贝叶斯公式中，得到：

​ 一般来说，$P(c_i)$为先验概率，$P(\boldsymbol{x}|c_i)$为条件概率，$P(\boldsymbol{x})$是用于归一化的证据因子。对于$P(c_i)$可以通过训练样本中类别为$c_i$的样本所占的比例进行估计；此外，由于只需要找出最大的$P(\boldsymbol{x}|c_i)$，因此我们并不需要计算$P(\boldsymbol{x})$。
​ 为了求解条件概率，基于不同假设提出了不同的方法，以下将介绍朴素贝叶斯分类器和半朴素贝叶斯分类器。

2.19.4 朴素贝叶斯分类器

​ 假设样本$\boldsymbol{x}$包含$d$个属性，即$\boldsymbol{x}={ x_1,x_2,…,x_d}$。于是有：

这个联合概率难以从有限的训练样本中直接估计得到。于是，朴素贝叶斯（Naive Bayesian，简称NB）采用了“属性条件独立性假设”：对已知类别，假设所有属性相互独立。于是有：

这样的话，我们就可以很容易地推出相应的判定准则了：

条件概率$P(x_j|c_i)​$的求解

如果$x_j$是标签属性，那么我们可以通过计数的方法估计$P(x_j|c_i)$

其中，$#(xj,c_i)$表示在训练样本中$x_j$与$c{i}$共同出现的次数。

如果$xj​$是数值属性，通常我们假设类别中$c{i}​$的所有样本第$j​$个属性的值服从正态分布。我们首先估计这个分布的均值$μ​$和方差$σ​$，然后计算$x_j​$在这个分布中的概率密度$P(x_j|c_i)​$。

2.19.5 举例理解朴素贝叶斯分类器

使用经典的西瓜训练集如下：

对下面的测试例“测1”进行 分类：

首先，估计类先验概率$P(c_j)$，有

然后，为每个属性估计条件概率（这里，对于连续属性，假定它们服从正态分布）

于是有

由于$0.063>6.80\times 10^{-5}$，因此，朴素贝叶斯分类器将测试样本“测1”判别为“好瓜”。

2.19.6 半朴素贝叶斯分类器

​ 朴素贝叶斯采用了“属性条件独立性假设”，半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息。独依赖估计（One-Dependence Estimator，简称ODE）是半朴素贝叶斯分类器最常用的一种策略。顾名思义，独依赖是假设每个属性在类别之外最多依赖一个其他属性，即：

其中$pa_j$为属性$x_i$所依赖的属性，成为$x_i$的父属性。假设父属性$pa_j$已知，那么可以使用下面的公式估计$P(x_j|c_i,{\rm pa}_j)$

2.20 EM算法

2.20.1 EM算法基本思想

​ 最大期望算法（Expectation-Maximization algorithm, EM），是一类通过迭代进行极大似然估计的优化算法，通常作为牛顿迭代法的替代，用于对包含隐变量或缺失数据的概率模型进行参数估计。

​ 最大期望算法基本思想是经过两个步骤交替进行计算：

​ 第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然估计值；

​ 第二步是最大化（M），最大化在E步上求得的最大似然值来计算参数的值。

​ M步上找到的参数估计值被用于下一个E步计算中，这个过程不断交替进行。

2.20.2 EM算法推导

​ 对于$m$个样本观察数据$x=(x^{1},x^{2},…,x^{m})$，现在想找出样本的模型参数$\theta$，其极大化模型分布的对数似然函数为：

如果得到的观察数据有未观察到的隐含数据$z=(z^{(1)},z^{(2)},…z^{(m)})$，极大化模型分布的对数似然函数则为：

由于上式不能直接求出$\theta$，采用缩放技巧：

上式用到了Jensen不等式：

并且引入了一个未知的新分布$Q_i(z^{(i)})$。

此时，如果需要满足Jensen不等式中的等号，所以有：

由于$Q_i(z^{(i)})$是一个分布，所以满足

综上，可得：

如果$Q_i(z^{(i)}) = P( z^{(i)}|x^{(i)};\theta)$ ，则第(1)式是我们的包含隐藏数据的对数似然的一个下界。如果我们能极大化这个下界，则也在尝试极大化我们的对数似然。即我们需要最大化下式：

简化得：

以上即为EM算法的M步，$\sum\limits_{z^{(i)}}Q_i(z^{(i)})log{P(x^{(i)}, z^{(i)};\theta)}​$可理解为$logP(x^{(i)}, z^{(i)};\theta) $基于条件概率分布$Q_i(z^{(i)}) $的期望。以上即为EM算法中E步和M步的具体数学含义。

2.20.3 图解EM算法

​ 考虑上一节中的（a）式，表达式中存在隐变量，直接找到参数估计比较困难，通过EM算法迭代求解下界的最大值到收敛为止。

​ 图片中的紫色部分是我们的目标模型$p(x|\theta)$，该模型复杂，难以求解析解，为了消除隐变量$z^{(i)}$的影响，我们可以选择一个不包含$z^{(i)}$的模型$r(x|\theta)$，使其满足条件$r(x|\theta) \leqslant p(x|\theta) $。

求解步骤如下：

（1）选取$\theta_1$，使得$r(x|\theta_1) = p(x|\theta_1)$，然后对此时的$r$求取最大值，得到极值点$\theta_2$，实现参数的更新。

（2）重复以上过程到收敛为止，在更新过程中始终满足$r \leqslant p $.

2.20.4 EM算法流程

输入：观察数据$x=(x^{(1)},x^{(2)},…x^{(m)})$，联合分布$p(x,z ;\theta)$，条件分布$p(z|x; \theta)$，最大迭代次数$J$

1）随机初始化模型参数$\theta$的初值$\theta^0$。

2）$for \ j \ from \ 1 \ to \ j$：

​ a） E步。计算联合分布的条件概率期望：

​ b） M步。极大化$L(\theta, \theta^{j})$，得到$\theta^{j+1}$:

​ c） 如果$\theta^{j+1}$收敛，则算法结束。否则继续回到步骤a）进行E步迭代。

输出：模型参数$\theta​$。

2.21 降维和聚类

2.21.1 图解为什么会产生维数灾难

​ 假如数据集包含10张照片，照片中包含三角形和圆两种形状。现在来设计一个分类器进行训练，让这个分类器对其他的照片进行正确分类（假设三角形和圆的总数是无限大），简单的，我们用一个特征进行分类：

​ 图2.21.1.a

​ 从上图可看到，如果仅仅只有一个特征进行分类，三角形和圆几乎是均匀分布在这条线段上，很难将10张照片线性分类。那么，增加一个特征后的情况会怎么样：

​ 图2.21.1.b

增加一个特征后，我们发现仍然无法找到一条直线将猫和狗分开。所以，考虑需要再增加一个特征：

​ 图2.21.1.c

​ 图2.21.1.d

​ 此时，可以找到一个平面将三角形和圆分开。

​ 现在计算一下不同特征数是样本的密度：

​ （1）一个特征时，假设特征空间时长度为5的线段，则样本密度为$10 \div 5 = 2$。

​ （2）两个特征时，特征空间大小为$ 5\times5 = 25$，样本密度为$10 \div 25 = 0.4$。

​ （3）三个特征时，特征空间大小是$ 5\times5\times5 = 125$，样本密度为$10 \div 125 = 0.08$。

​ 以此类推，如果继续增加特征数量，样本密度会越来越稀疏，此时，更容易找到一个超平面将训练样本分开。当特征数量增长至无限大时，样本密度就变得非常稀疏。

​ 下面看一下将高维空间的分类结果映射到低维空间时，会出现什么情况？

​ 图2.21.1.e

​ 上图是将三维特征空间映射到二维特征空间后的结果。尽管在高维特征空间时训练样本线性可分，但是映射到低维空间后，结果正好相反。事实上，增加特征数量使得高维空间线性可分，相当于在低维空间内训练一个复杂的非线性分类器。不过，这个非线性分类器太过“聪明”，仅仅学到了一些特例。如果将其用来辨别那些未曾出现在训练样本中的测试样本时，通常结果不太理想，会造成过拟合问题。

​ 图2.21.1.f

​ 上图所示的只采用2个特征的线性分类器分错了一些训练样本，准确率似乎没有图2.21.1.e的高，但是，采用2个特征的线性分类器的泛化能力比采用3个特征的线性分类器要强。因为，采用2个特征的线性分类器学习到的不只是特例，而是一个整体趋势，对于那些未曾出现过的样本也可以比较好地辨别开来。换句话说，通过减少特征数量，可以避免出现过拟合问题，从而避免“维数灾难”。

​ 上图从另一个角度诠释了“维数灾难”。假设只有一个特征时，特征的值域是0到1，每一个三角形和圆的特征值都是唯一的。如果我们希望训练样本覆盖特征值值域的20%，那么就需要三角形和圆总数的20%。我们增加一个特征后，为了继续覆盖特征值值域的20%就需要三角形和圆总数的45%($0.452^2\approx0.2$)。继续增加一个特征后，需要三角形和圆总数的58%($0.583^3\approx0.2$)。随着特征数量的增加，为了覆盖特征值值域的20%，就需要更多的训练样本。如果没有足够的训练样本，就可能会出现过拟合问题。

​ 通过上述例子，我们可以看到特征数量越多，训练样本就会越稀疏，分类器的参数估计就会越不准确，更加容易出现过拟合问题。“维数灾难”的另一个影响是训练样本的稀疏性并不是均匀分布的。处于中心位置的训练样本比四周的训练样本更加稀疏。

​ 假设有一个二维特征空间，如上图所示的矩形，在矩形内部有一个内切的圆形。由于越接近圆心的样本越稀疏，因此，相比于圆形内的样本，那些位于矩形四角的样本更加难以分类。当维数变大时，特征超空间的容量不变，但单位圆的容量会趋于0，在高维空间中，大多数训练数据驻留在特征超空间的角落。散落在角落的数据要比处于中心的数据难于分类。

2.21.2 怎样避免维数灾难

有待完善！！！

解决维度灾难问题：

主成分分析法PCA，线性判别法LDA

奇异值分解简化数据、拉普拉斯特征映射

Lassio缩减系数法、小波分析法、

2.21.3 聚类和降维有什么区别与联系

​ 聚类用于找寻数据内在的分布结构，既可以作为一个单独的过程，比如异常检测等等。也可作为分类等其他学习任务的前驱过程。聚类是标准的无监督学习。

​ 1）在一些推荐系统中需确定新用户的类型，但定义“用户类型”却可能不太容易，此时往往可先对原有的用户数据进行聚类，根据聚类结果将每个簇定义为一个类,然后再基于这些类训练分类模型,用于判别新用户的类型。

​ 2）而降维则是为了缓解维数灾难的一个重要方法，就是通过某种数学变换将原始高维属性空间转变为一个低维“子空间”。其基于的假设就是，虽然人们平时观测到的数据样本虽然是高维的，但是实际上真正与学习任务相关的是个低维度的分布。从而通过最主要的几个特征维度就可以实现对数据的描述，对于后续的分类很有帮助。比如对于Kaggle（数据分析竞赛平台之一）上的泰坦尼克号生还问题。通过给定一个乘客的许多特征如年龄、姓名、性别、票价等，来判断其是否能在海难中生还。这就需要首先进行特征筛选，从而能够找出主要的特征，让学习到的模型有更好的泛化性。

​ 聚类和降维都可以作为分类等问题的预处理步骤。

​ 但是他们虽然都能实现对数据的约减。但是二者适用的对象不同，聚类针对的是数据点，而降维则是对于数据的特征。另外它们有着很多种实现方法。聚类中常用的有K-means、层次聚类、基于密度的聚类等；降维中常用的则PCA、Isomap、LLE等。

2.21.4 有哪些聚类算法优劣衡量标准

不同聚类算法有不同的优劣和不同的适用条件。可从以下方面进行衡量判断：
1、算法的处理能力：处理大的数据集的能力，即算法复杂度；处理数据噪声的能力；处理任意形状，包括有间隙的嵌套的数据的能力；
2、算法是否需要预设条件：是否需要预先知道聚类个数，是否需要用户给出领域知识；

​ 3、算法的数据输入属性：算法处理的结果与数据输入的顺序是否相关，也就是说算法是否独立于数据输入顺序；算法处理有很多属性数据的能力，也就是对数据维数是否敏感，对数据的类型有无要求。

2.21.5 聚类和分类有什么区别

聚类（Clustering）
聚类，简单地说就是把相似的东西分到一组，聚类的时候，我们并不关心某一类是什么，我们需要实现的目标只是把相似的东西聚到一起。一个聚类算法通常只需要知道如何计算相似度就可以开始工作了，因此聚类通常并不需要使用训练数据进行学习，在机器学习中属于无监督学习。

分类（Classification）

​ 分类，对于一个分类器，通常需要你告诉它“这个东西被分为某某类”。一般情况下，一个分类器会从它得到的训练集中进行学习，从而具备对未知数据进行分类的能力，在机器学习中属于监督学习。

2.21.6 不同聚类算法特点性能比较

2.21.7 四种常用聚类方法之比较

​ 聚类就是按照某个特定标准把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起，不同类数据尽量分离。
​ 主要的聚类算法可以划分为如下几类：划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法。下面主要对k-means聚类算法、凝聚型层次聚类算法、神经网络聚类算法之SOM,以及模糊聚类的FCM算法通过通用测试数据集进行聚类效果的比较和分析。

2.21.8 k-means聚类算法

k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。
k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。k-means算法的处理过程如下：首先，随机地 选择k个对象，每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算每个簇的平均值。 这个过程不断重复，直到准则函数收敛。通常，采用平方误差准则，其定义如下：

　这里E是数据中所有对象的平方误差的总和，p是空间中的点，$m_i$是簇$C_i$的平均值[9]。该目标函数使生成的簇尽可能紧凑独立，使用的距离度量是欧几里得距离，当然也可以用其他距离度量。

算法流程：
​ 输入：包含n个对象的数据和簇的数目k；
​ 输出：n个对象到k个簇，使平方误差准则最小。
​ 步骤：
　　(1) 任意选择k个对象作为初始的簇中心；
　　(2) 根据簇中对象的平均值，将每个对象(重新)赋予最类似的簇；
　　(3) 更新簇的平均值，即计算每个簇中对象的平均值；
　　(4) 重复步骤(2)、(3)直到簇中心不再变化；

2.21.9 层次聚类算法

​ 根据层次分解的顺序是自底向上的还是自上向下的，层次聚类算法分为凝聚的层次聚类算法和分裂的层次聚类算法。
　凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。

算法流程：

注：以采用最小距离的凝聚层次聚类算法为例：

　(1) 将每个对象看作一类，计算两两之间的最小距离；
　(2) 将距离最小的两个类合并成一个新类；
　(3) 重新计算新类与所有类之间的距离；
　(4) 重复(2)、(3)，直到所有类最后合并成一类。

2.21.10 SOM聚类算法

​ SOM神经网络[11]是由芬兰神经网络专家Kohonen教授提出的，该算法假设在输入对象中存在一些拓扑结构或顺序，可以实现从输入空间(n维)到输出平面(2维)的降维映射，其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。

​ SOM网络包含输入层和输出层。输入层对应一个高维的输入向量，输出层由一系列组织在2维网格上的有序节点构成，输入节点与输出节点通过权重向量连接。 学习过程中，找到与之距离最短的输出层单元，即获胜单元，对其更新。同时，将邻近区域的权值更新，使输出节点保持输入向量的拓扑特征。

算法流程：

​ (1) 网络初始化，对输出层每个节点权重赋初值；
​ (2) 从输入样本中随机选取输入向量并且归一化，找到与输入向量距离最小的权重向量；
​ (3) 定义获胜单元，在获胜单元的邻近区域调整权重使其向输入向量靠拢；
​ (4) 提供新样本、进行训练；
​ (5) 收缩邻域半径、减小学习率、重复，直到小于允许值，输出聚类结果。

2.21.11 FCM聚类算法

​ 1965年美国加州大学柏克莱分校的扎德教授第一次提出了‘集合’的概念。经过十多年的发展，模糊集合理论渐渐被应用到各个实际应用方面。为克服非此即彼的分类缺点，出现了以模糊集合论为数学基础的聚类分析。用模糊数学的方法进行聚类分析，就是模糊聚类分析[12]。
​ FCM算法是一种以隶属度来确定每个数据点属于某个聚类程度的算法。该聚类算法是传统硬聚类算法的一种改进。
​ 设数据集$X={x1,x_2,…,x_n}$,它的模糊$c$划分可用模糊矩阵$U=[u{ij}]$表示，矩阵$U$的元素$u{ij}$表示第$j(j=1,2,…,n)$个数据点属于第$i(i=1,2,…,c)$类的隶属度，$u{ij}$满足如下条件：

目前被广泛使用的聚类准则是取类内加权误差平方和的极小值。即：

其中$V$为聚类中心，$m$为加权指数，$d_{ij}(x_j,v_i)=||v_i-x_j||$。

算法流程：

　(1) 标准化数据矩阵；
　(2) 建立模糊相似矩阵，初始化隶属矩阵；
　(3) 算法开始迭代，直到目标函数收敛到极小值；
　(4) 根据迭代结果，由最后的隶属矩阵确定数据所属的类，显示最后的聚类结果。

2.21.12 四种聚类算法试验

​ 选取专门用于测试分类、聚类算法的国际通用的UCI数据库中的IRIS数据集，IRIS数据集包含150个样本数据，分别取自三种不同 的莺尾属植物setosa、versicolor和virginica的花朵样本,每个数据含有4个属性，即萼片长度、萼片宽度、花瓣长度、花瓣宽度，单位为cm。 在数据集上执行不同的聚类算法，可以得到不同精度的聚类结果。基于前面描述的各算法原理及流程，可初步得如下聚类结果。

注：

(1) 聚错样本数：总的聚错的样本数，即各类中聚错的样本数的和；
(2) 运行时间：即聚类整个过程所耗费的时间，单位为s；
(3) 平均准确度：设原数据集有k个类,用$ci$表示第i类，$n_i$为$c_i$中样本的个数，$m_i$为聚类正确的个数,则$m_i/n_i$为 第i类中的精度，则平均精度为：$avg=\frac{1}{k}\sum{i=1}^{k}\frac{m{i}}{n{i}}$。

参考文献

[1] Goodfellow I, Bengio Y, Courville A. Deep learning[M]. MIT press, 2016.
[2] 周志华. 机器学习[M].清华大学出版社, 2016.
[3] Michael A. Nielsen. “Neural Networks and Deep Learning”, Determination Press, 2015.
[4] Suryansh S. Gradient Descent: All You Need to Know, 2018.
[5] 刘建平. 梯度下降小结,EM算法的推导, 2018
[6] 杨小兵．聚类分析中若干关键技术的研究[D]． 杭州：浙江大学, 2005.
[7] XU Rui, Donald Wunsch 1 1． survey of clustering algorithm[J]．IEEE．Transactions on Neural Networks, 2005, 16(3)：645-67 8.
[8] YI Hong, SAM K． Learning assignment order of instances for the constrained k-means clustering algorithm[J]．IEEE Transactions on Systems, Man, and Cybernetics, Part B：Cybernetics,2009,39 (2)：568-574.
[9] 贺玲, 吴玲达, 蔡益朝．数据挖掘中的聚类算法综述[J]．计算机应用研究, 2007, 24(1):10-13．
[10] 孙吉贵, 刘杰, 赵连宇．聚类算法研究[J]．软件学报, 2008, 19(1)：48-61．
[11] 孔英会, 苑津莎, 张铁峰等．基于数据流管理技术的配变负荷分类方法研究．中国国际供电会议, CICED2006．
[12] 马晓艳, 唐雁．层次聚类算法研究[J]．计算机科学, 2008, 34(7)：34-36．
[13] FISHER R A． Iris Plants Database https://www.ics.uci.edu/vmlearn/MLRepository.html, Authorized license．
[14] Quinlan J R. Induction of decision trees[J]. Machine learning, 1986, 1(1): 81-106.
[15] Breiman L. Random forests[J]. Machine learning, 2001, 45(1): 5-32.

数组

寻找数组中第k大的元素

思路1：堆。创建一个大根堆，将所有数组中的元素加入堆中，并保持堆的大小小于等于k。这样，堆中就保留了前k个最大的元素。

1
2
3
4
5
6

def findKthLargest(self, nums: List[int], k: int) -> int:
        import heapq
        if k>len(nums):
            return 0
        res = heapq.nlargest(k, nums)
        return res[-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def findKthLargest(self, nums: List[int], k:int) -> int:
    def partition(nums, left, right):
        pivot = nums[left]
        j = left
        for i in range(left+1, right+1):
            if nums[i] < pivot:
                j += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[left], nums[j] = nums[j], nums[left]
        return j
    size = len(nums)
    target = size - k
    left, right = 0, size - 1
    while True:
        minIndex = partition(nums, left, right)
        if minIndex == target:
            return nums[minIndex]
        elif minIndex < target:
            left = minIndex + 1
        else:
            right = minIndex - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
public:
    void swap(vector<int>& nums, int left, int right){
        int temp = nums[right];
        nums[right] = nums[left];
        nums[left] = temp;
    }

    int partition(vector<int>& nums, int left, int right){
        
        int pivot = nums[left];
        int j = left;
        for(int i=left+1; i<=right; i++){
            if (nums[i] <pivot){
                j++;
                swap(nums, i, j);
            }
        }
        swap(nums, left, j);
        return j;
    }
    int findKthLargest(vector<int>& nums, int k) {
        int size = nums.size();
        int target = size - k;
        int left = 0;
        int right = size-1;
        while(true){
            int midIndex = partition(nums, left, right);
            if(midIndex == target){
                return nums[midIndex];
            }
            else{
                if(midIndex < target){
                    left  = midIndex + 1;
                }
                else{
                    right = midIndex - 1;
                }
            }
        }
        return 0;
    }
};

寻找两个有序数组的中位数

思路1：合并两个有序数组，遍历第len/2+1个元素即中位数。由于两队列之和是偶数时，中位数为数组中间左右两个数之和的平均，故需要一个变量保存前一次遍历时的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def findMedianSortedArrays(nums1, nums2):
    l1 = len(nums1)
    l2 = len(nums2)
    l = l1 + l2
    pre, cur = -1, -1
    p1, p2 = 0, 0
    for i in range(l // 2 + 1):
        pre = cur
        if p1 < l1 and (p2 >= l2 or nums1[p1] < nums2[p2]):
            cur = nums1[p1]
            p1 += 1
        else:
            cur = nums2[p2]
            p2 += 1
    if l % 2 == 0:
        return (pre + cur) / 2.0
    else:
        return cur

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def findMedianSortedArraysII(nums1, nums2):
    if len(nums1)>len(nums2):
        nums1, nums2 = nums2, nums1
    l1, l2 = len(nums1), len(nums2)
    mid = (l1+l2+1)//2
    left, right = 0, l1
    while left<right:
        mid1 = left+(right-left)//2
        mid2 = mid - mid1
        if nums1[mid1]<nums2[mid2-1]:
            left = mid1+1
        else:
            right = mid1
    mid1 = left
    mid2 = mid - mid1
    if mid1 == 0:
        max_out_left = nums2[mid2-1]
    elif mid2 == 0:
        max_out_left = nums1[mid1-1]
    else:
        max_out_left = max(nums1[mid1-1], nums2[mid2-1])
    if (l1+l2)%2 == 1:
        return max_out_left
    if mid1 == l1:
        min_out_right = nums2[mid2]
    elif mid2 == l2:
        min_out_right = nums1[mid1]
    else:
        min_out_right = min(nums1[mid1], nums2[mid2])
    return (max_out_left+min_out_right)/2.0

连续子数组的最大和

思路：数组有正有负的情况，这时我们遍历数组，累计求和total, 如果total小于0，则直接舍弃前面的和，重新从0开始计算，确保子数组和最大。

1
2
3
4
5
6
7
8
9
10
11
12

def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        nsum = 0
        ans = float("-inf")
        for num in nums:
            if nsum>=0:
                nsum += num
            else:
                nsum = num
            ans = max(ans, nsum)
        return ans

最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续的递增序列。
输入：[1,3,5,4,7]，最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
思路：从 0 位置开始遍历，遍历时根据前后元素状态判断是否递增，递增则 count++，递减则 count=1。如果 count>ans，则更新 ans，直到循环结束。

1
2
3
4
5
6
7
8
9
10
11

def findLengthOfLCIS(self, nums: List[int]) -> int:
    if len(nums)<=1:
        return len(nums)
    ans, count = 1, 1
    for i in range(len(nums)-1):
        if nums[i+1]>nums[i]:
            count += 1
        else:
            count = 1
        ans = max(ans, count)
    return ans

最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。
输入：[10,9,2,5,3,7,101,18]，最长的上升子序列是 [2,3,7,101]，它的长度是 4。
思路一：动态规划
dp[i] 的值代表 nums 前i个数字的最长子序列长度。当 nums[i] > nums[j] 时： nums[i] 可以接在 nums[j] 之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j] + 1 ；实现方式为遍历 j 时，每轮执行 dp[i] = max(dp[i], dp[j] + 1)。

1
2
3
4
5
6
7
8
9

def lengthOfLIS(self, nums: List[int]) -> int:
    if not nums:
        return 0
    dp = [1]*len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j]<nums[i]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def lengthOfLIS(self, nums: List[int]) -> int:
    n = len(nums)
    if n<2:
        return n
    res = [nums[0]]
    for num in nums[1:]:
        if num>res[-1]:
            res.append(num)
            continue
        left, right = 0, len(res)-1
        while left<right:
            mid = left+(right-left)//2
            if res[mid]<num:
                left = mid+1
            else:
                right = mid
        res[left] = num
    return len(res)

最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。
输入: [100, 4, 200, 1, 3, 2]，最长连续序列是 [1, 2, 3, 4]，它的长度为 4。
思路：对每个元素进行判断，是不是序列的开始。即nums[i]-1是否在哈希表中（O（1）的时间）。
如果nums[i]-1在set中，说明不是序列的开始，则跳过。
如果nums[i]-1不在，说明nums[i]是序列的开始。判断nums[i]+1是否在哈希集合中，直到没有出现在集合中，判断此时的长度cur_len。和最长序列长度进行比较，max_len = max(curr_len,max_len)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def longestConsecutive(self, nums: List[int]) -> int:
    if not nums:
        return 0
    s = set(nums)
    maxlen = 0
    for num in s:
        curlen = 1
        if num-1 in s:
            continue
        while num+1 in s:
            num += 1
            curlen += 1
        maxlen = max(maxlen, curlen)
    return maxlen

滑动窗口

什么是滑动窗口？其实就是一个队列，比如题目无重复字符的最长子串中的abcabcbb，进入这个队列（窗口）为abc满足题目，当再进入a，队列就变成了abca，这时候不满足要求。所以，我们就要移动这个队列。我们只要把队列的左边元素移出就行，直到满足题目要求。
例题1：leetcode3.无重复字符的最长子串(滑窗模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def lengthOfLongestSubstring(s):
    from collections import defaultdict
    if not s:
        return 0
    if len(s)==1:
        return 1
    left, right, counter= 0, 0, 0
    maxLen = 0
    windows = defaultdict(int)
    while right<len(s):
        if windows[s[right]]>0:
            counter += 1
        windows[s[right]] += 1
        right += 1
        while counter>0:        # 窗口条件决定左边元素是否移出
            if windows[s[left]]>1:
                counter -= 1
            windows[s[left]] -= 1
            left += 1
        maxLen = max(maxLen, right-left)
    return maxLen

二叉树

前序

递归

1
2
3
4
5
6

def preOrder(node):
    if not node:
        return None
    print(node.val)
    preOrder(node.left)
    preOrder(node.right)

1
2
3
4
5
6
7
8
9

def preOrder(node):
    stack = [node]
    while stack:
        print(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
        node = stack.pop()

中序遍历

递归

1
2
3
4
5
6

def inorder(node):
    if not node:
        return None
    inorder(node.left)
    print(node.val)
    inorder(node.right)

1
2
3
4
5
6
7
8
9

def inorder(node):
    stack = []
    while node or len(stack)>0:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        print(node.val)
        node = node.right

后序遍历

递归

1
2
3
4
5
6

def postOrder(node):
    if not node:
        return None
    postOrder(node.left)
    postOrder(node.right)
    print(node.val)

1
2
3
4
5
6
7
8
9
10
11
12

def postOrder(node):
    stack = [node]
    stack2 = []
    while len(stack)>0:
        node = stack.pop()
        stack2.append(node)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    while len(stack2)>0:
        print(stack2.pop().val)

层次遍历

1
2
3
4
5
6
7
8
9
10
11

if not node:
    return None
queue = []
queue.append(node)
while len(queue)>0:
    node = queue.pop(0)
    print(node.val)
    if node.left:
        queue.append(node.left)
    if node.right:
        queue.append(node.right)

验证二叉搜索树

买卖股票

1）给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），求获得的最大利润。
思路1：只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。

1
2
3
4
5
6
7

def maxProfit(self, prices: List[int]) -> int:
    minprice = float("inf")
    maxprofit = 0
    for price in prices:
        maxprofit = max(price - minprice, maxprofit)
        minprice = min(price, minprice)
    return maxprofit

1
2
3
4
5
6
7
8
9
10
11

def maxProfit(prices):
    if len(prices)<2:
        return 0
    n = len(prices)
    dp = [[0]*n for _ in range(2)]
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][1], -prices[i])
    return dp[-1][0]

1
2
3
4
5
6
7
8
9
10
11

def maxProfit2(prices):
    n = len(prices)
    if n<2:
        return 0
    dp = [0]*2
    dp[0] = 0
    dp[1] = -prices[0]
    for i in range(1, n):
        dp[0] = max(dp[0], dp[1]+prices[i])
        dp[1] = max(dp[1], -prices[i])
    return dp[0]

1
2
3
4
5
6
7
8
9
10
11

def maxProfitII(prices):
    n = len(prices)
    if n<2:
        return 0
    dp = [[0]*2 for _ in range(n)]
    dp[0][0] = 0
    dp[0][1] = -prices[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
    return dp[-1][0]

3）最多可以完成两笔交易。
注：必须在再次购买前出售掉之前的股票
思路：重新定义状态方程
dp[i][0]表示未交易
dp[i][1]表示第一次买入一支股票
dp[i][2]表示第一次卖出一支股票
dp[i][3]表示第二次买入一支股票
dp[i][4]表示第二次卖出一支股票
状态转移方程见代码
初始化：第0天初始化为前两个状态，而状态3（第二次持股）只能赋值为一个不可能的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def maxProfitIII(prices):
    n = len(prices)
    if n<2:
        return 0
    dp = [[0]*5 for _ in range(n)]
    dp[0][1] = -prices[0]
    for i in range(n):
        dp[i][3] = float("-inf")
    for i in range(1, n):
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
        dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
        dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
        dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
    # 最大值只发生在不持股的时候
    return max(0, dp[-1][2], dp[-1][4])

4）最多可以完成 k 笔交易
注：必须在再次购买前出售掉之前的股票

5）在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
a) 必须在再次购买前出售掉之前的股票;
b) 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)
思路：增加一个状态，j取三个值：
0表示不持股，1表示持股，2表示冷冻期
状态转移方程：
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][2]-prices[i])
dp[i][2] = dp[i-1][0]

1
2
3
4
5
6
7
8
9
10
11

def maxProfitV(prices):
    n = len(prices)
    if n<2:
        return 0
    dp = [[0]*3 for _ in range(n)]
    dp[0][1] = -prices[0]
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][2]-prices[i])
        dp[i][2] = dp[i-1][0]
    return max(dp[-1][0], dp[-1][2])

1
2
3
4
5
6
7
8
9
10

def maxProfitVI(prices, fee):
    n = len(prices)
    if n<2:
        return 0
    dp = [[0]*2 for _ in range(n)]
    dp[0][1] = -prices[0]-fee
    for i in range(1, n):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]-fee)
    return dp[-1][0]

动态规划

最长回文子串

给定一个字符串s，找到s中最长的回文子串。
例：输入：”babad”，输出为：”bab”。
思路：设dp[i][j]表示子串s[i,j]是否为回文子串，则状态转移方程为：dp[i][j] = (s[i]==s[j]) and dp[i+1][j-1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def longestPalindrome(self, s: str) -> str:
    if not s or len(s)==1:
        return s
    n = len(s)
    dp = [[0]*n for _ in range(n)]
    left, right = 0, 0
    maxLen = 0
    for j in range(n):
        dp[j][j] = 1
        for i in range(j):
            if s[i]==s[j] and (j-i<2 or dp[i+1][j-1]==1):
                dp[i][j] = 1
            else:
                dp[i][j] = 0
            if dp[i][j]==1 and maxLen<j-i+1:
                maxLen = j-i+1
                left, right = i, j
    return s[left:right+1]

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
实例：输入text1 = “abcde”, text2 = “ace” ，输出3。最长公共子序列是 “ace”，它的长度为 3。
思路：设dp[i][j]是text1[:i]和text2[:j]的最长公共子序列长度，则状态转移方程为：dp[i][j] = dp[i-1][j-1]+1 if text1[i]==text2[j] else max(dp[i-1][j], dp[i][j-1])。

1
2
3
4
5
6
7
8
9
10

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[-1][-1]

最长公共子串

给出两个字符串str1,str2返回该两个字符串的最长公共子串。
实例：输入str1 = “1AB2345CD”,str2 = “12345EF”，输出“2345”。
思路：dp[i][j]的含义为以str1[i]和str2[j]结尾的最长公共子串，则状态转移方程为dp[i][j]=dp[i-1][j-1]+1 if str1[i]==str2[j] else 0.

1
2
3
4
5
6
7
8
9
10

def longestCommonSubstring(self, str1: str, str2: str) -> int:
    m, n = len(str1), len(str2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = 0
    return dp[-1][-1]

编辑距离

给你两个单词word1和word2，请你计算出将word1转换为word2所使用的最少操作数。
你可以对一个单词进行如下三种操作：
1）插入一个字符；2）删除一个字符；3）替换一个字符。
示例：输入word1 = “horse”, word2 = “ros”，输出为3。
思路：dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数。所以，当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def minDistance(self, word1: str, word2: str) -> int:
    n1, n2 = len(word1), len(word2)
    dp = [[0]*(n2+1) for _ in range(n1+1)]
    for j in range(1, n2+1):
        dp[0][j] = dp[0][j-1]+1
    for i in range(1, n1+1):
        dp[i][0] = dp[i-1][0]+1
    for i in range(1, n1+1):
        for j in range(1, n2+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
    return dp[-1][-1]

让字符串成为回文串的最少插入次数

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。请你返回让 s 成为回文串的 最少操作次数 。
示例：输入s = “mbadm”，输出为2。字符串可变为 “mbdadbm” 或者 “mdbabdm” 。
思路：是最长公共子序列的变形。当前字符串要变成回文,那只要把不一样的找出来就好了。即:求出反过来的字符串和当前字符串的最长公共子序列,然后用字符串长度减去最长公共子序列长度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13

def minInsertions(self, s: str) -> int:
    n = len(s)
    t = s[::-1]
    if s==t:
        return 0
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return n-dp[-1][-1]

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
示例：输入coins = [1, 2, 5], amount = 11，输出3。11可拆分成5+5+1。
思路：

回溯：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

    def coinChange(self, coins: List[int], amount: int) -> int:
        if not coins:
            return -1
        res = [float("inf")]
        def dfs(coins, amount, count, res):
            if amount == 0:
                res[0] = min(res[0], count)
            for coin in coins:
                diff = amount-coin
                if diff<0:
                    break
                dfs(coins, diff, count+1, res)
        dfs(coins, amount, 0, res)
        return res[0] if res[0]!=float("inf") else -1
``` 
在回溯法中，如果含有很多的重复的计算的时候，就可以使用记忆化的搜索，将可能出现的重复计算大状态使用一个数组来保存其值，在进行重复的计算的时候，就可以直接的调用数组中的值，较少了不必要的递归。使用了记忆化搜索后，一般还可以进行优化，在记忆化搜索的基础上，变成 自底而上 的动态规划。
若包含当前的 coins[i]，那么剩余钱就是 i-coins[i]，这种操作要兑换的硬币数是 memo[i-coins[j]] + 1。
```Python
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float("inf")]*(amount+1)
        dp[0] = 0
        for i in range(1,amount+1):
            for coin in coins:
                if i >= coin:
                    dp[i] = min(dp[i], dp[i-coin]+1)
        return dp[-1] if (dp[-1]!=float("inf")) else -1

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？
思路：令 dp[i][j] 是到达 i, j 最多路径，则动态转移方程为：dp[i][j] = dp[i-1][j] + dp[i][j-1]。
对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1。

1
2
3
4
5
6
7
8
9
10

def uniquePaths(self, m: int, n: int) -> int:
    dp = [[0]*n for _ in range(m)]
    for i in range(1, m):
        dp[i][0] = 1
    for i in range(1, n):
        dp[0][i] = 1
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j]+dp[i][j-1]
    return dp[-1][-1]

1
2
3
4
5
6

def uniquePaths(self, m: int, n: int) -> int:
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] = dp[j]+dp[j-1]
    return dp[-1]

礼物的最大价值

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
思路：令dp[i][j]为位置[i,j]的礼物价值，则动态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i][j-1])+gift[i][j]。

1
2
3
4
5
6
7
8
9
10
11
12

def maxValue(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for i in range(1, m):
        dp[i][0] = dp[i-1][0]+grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1]+grid[0][j]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])+grid[i][j]
    return dp[-1][-1]

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
思路：和拿糖果问题类似。设dp[i]为抢劫第i间房间的最大金额，np[i]为不抢劫第i间房间的最大金额。则动态转移方程为：dp[i]=np[i]+nums[i],np[i] = max(np[i-1], dp[i-1])

1
2
3
4
5
6
7
8
9
10
11
12
13

def rob(self, nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums)==1:
        return nums[0]
    n = len(nums)
    dp = [0]*n
    np = [0]*n
    dp[0] = nums[0]
    for i in range(1, n):
        dp[i] = np[i-1]+nums[i]
        np[i] = max(np[i-1], dp[i-1])
    return max(dp)

1
2
3
4
5
6
7
8
9
10
11

def rob(self, nums: List[int]) -> int:
    if not nums:
        return 0
    if len(nums)==1:
        return nums[0]
    n = len(nums)
    dp = [0]*(n+1)
    dp[1] = nums[0]
    for i in range(2, n+1):
        dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
    return dp[-1]

打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
思路：此题中的房间是环状排列的（即首尾相接），环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房间子问题：
1）在不偷窃第一个房子的情况下（即 nums[1:]），最大金额是p1；
2）在不偷窃最后一个房子的情况下（即 nums[:n-1]），最大金额是 p2。
设dp[i] 代表前 i 个房子在满足条件下的能偷窃到的最高金额，则dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])。我们发现 dp[n] 只与 dp[n-1] 和 dp[n-2] 有关系，因此我们可以设两个变量 cur和 pre 交替记录，将空间复杂度降到 O(1)。

1
2
3
4
5
6
7
8
9

def rob(self, nums: List[int]) -> int:
    def robCore(nums):
        cur, pre = 0, 0
        for num in nums:
            cur, pre = max(cur, pre+num), cur
        return cur
    if len(nums)==1:
        return nums[0]
    return max(robCore(nums[:-1]), robCore(nums[1:]))

打家劫舍III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
思路：假设func(root)为问题的解，即能从以root为根节点的树中盗窃到的最大金额。那么以root房子开始分析，可以选择偷窃root房子，也可以选择不偷窃。如果偷窃root房子，那么func(root) = root->val + func(root->left)->unrob + func(root->left)->unrob。
如果不偷窃root房子，那么func(root) = func(root->left)->robed + func(root->right)->robed。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def rob(self, root: TreeNode) -> int:
    def robCore(root):
        if not root:
            return [0, 0]
        left = robCore(root.left)
        right = robCore(root.right)
        robed = root.val+left[1]+right[1]
        unrob = left[0]+right[0]
        return [max(robed, unrob), unrob]
    if not root:
        return 0
    # res[0]偷窃该节点的金额，res[1]不偷窃该节点的金额
    res = robCore(root)
    return res[0]

递归

全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。
思路：回溯法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def permute(self, nums: List[int]) -> List[List[int]]:
    if len(nums)<=1:
        return [nums]
    res, stack = [], []
    def backtrack(nums, stack):
        if not nums:
            res.append(stack[:])
            return
        for i in range(len(nums)):
            stack.append(nums[i])
            backtrack(nums[:i]+nums[i+1:], stack)
            stack.pop()
    backtrack(nums, stack)
    return res

全排列II

给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例：输入[1,1,2]，输出[[1,1,2],[1,2,1],[2,1,1]]
思路：先排序，然后回溯+剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    res = []
    nums.sort()
    def backtrack(nums, tmp):
        if not nums:
            res.append(tmp[:])
            return
        for i in range(len(nums)):
            if i>0 and nums[i]==nums[i-1]:
                continue
            tmp.append(nums[i])
            backtrack(nums[:i]+nums[i+1:], tmp)
            tmp.pop()
    backtrack(nums, [])
    return res

组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。解集不能包含重复的组合。
示例：输入candidates=[2,3,6,7]，target=7，输出[[7],[2,2,3]]
思路：回溯+剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    def dfs(nums, target, start, tmp, res):
        if target==0:
            res.append(tmp[:])
            return
        for i in range(start, len(nums)):
            diff = target-nums[i]
            if diff<0:
                break
            tmp.append(nums[i])
            dfs(nums, diff, i, tmp, res)
            tmp.pop()
    res = []
    dfs(candidates, target, 0, [], res)
    return res

组合总和II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。解集不能包含重复的组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    def dfs(nums, target, start, tmp, res):
        if target==0:
            res.append(tmp[:])
            return
        for i in range(start, len(nums)):
            diff = target-nums[i]
            if diff<0:
                break
            if i>start and nums[i]==nums[i-1]:
                continue
            tmp.append(nums[i])
            dfs(nums, diff, i+1, tmp, res)
            tmp.pop()
    res = []
    candidates.sort()
    dfs(candidates, target, 0, [], res)
    return res

组合总和III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
示例：输入k=3,n=7，输出[[1,2,4]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    def dfs(target, k, start, path, res):
        if len(path)==k and target==0:
            res.append(path[:])
            return
        for i in range(start, 10):
            diff = target-i
            if diff<0:
                continue
            path.append(i)
            dfs(diff, k, i+1, path, res)
            path.pop()
    
    if k<=0 or n<k:
        return []
    res = []
    dfs(n, k, 1, [], res)
    return res

组合总和IV

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例：输入nums=[1,2,3]，target=4，所有的可能组合为：(1, 1, 1, 1),(1, 1, 2),(1, 2, 1),(1, 3),(2, 1, 1),(2, 2),(3, 1)。
因此输出为7。
思路：背包问题，动态规划
状态转移方程：dp[i]= dp[i - nums[0]] + dp[i - nums[1]] + dp[i - nums[2]] + …，值得注意的是：dp[0] = 1，表示，如果那个硬币的面值刚刚好等于需要凑出的价值，这个就成为 1 种组合方案。

1
2
3
4
5
6
7
8
9
10

def combinationSum4(self, nums: List[int], target: int) -> int:
    if not nums or target<=0:
        return 0
    dp = [0 for _ in range(target+1)]
    dp[0] = 1
    for i in range(1, target+1):
        for num in nums:
            if i >= num:
                dp[i] += dp[i-num]
    return dp[-1]

子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。
示例：输入nums = [1,2,3]，输出[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]

1
2
3
4
5
6
7
8
9
10

def subsets(self, nums: List[int]) -> List[List[int]]:
    def dfs(nums, start, tmp, res):
        res.append(tmp[:])
        for i in range(start, len(nums)):
            tmp.append(nums[i])
            dfs(nums, i+1, tmp, res)
            tmp.pop()
    res = []
    dfs(nums, 0, [], res)
    return res

子集II

定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。
示例：输入[1,2,2]，输出[[2],[1],[1,2,2],[2,2],[1,2],[]]

1
2
3
4
5
6
7
8
9
10
11
12
13

def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    def dfs(nums, start, tmp, res):
        res.append(tmp[:])
        for i in range(start, len(nums)):
            if i>start and nums[i]==nums[i-1]:
                continue
            tmp.append(nums[i])
            dfs(nums, i+1, tmp, res)
            tmp.pop()
    res = []
    nums.sort()
    dfs(nums, 0, [], res)
    return res

N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例：输入4，输出2，即存在两种不同的解法
思路：回溯法，存在约束条件：一行只可能有一个皇后且一列也只可能有一个皇后。对于所有的主对角线有 行号 + 列号 = 常数，对于所有的次对角线有 行号 - 列号 = 常数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def totalNQueens(self, n: int) -> int:
    def dfs(n, row, col, master, slave, path, res):
        if row == n:
            res[0] += 1
            return
        for i in range(n):
            if i not in col and row+i not in slave and row-i not in master:
                path.append(i)
                col.add(i)
                master.add(row-i)
                slave.add(row+i)
                dfs(n, row+1, col, master, slave, path, res)
                slave.remove(row+i)
                master.remove(row-i)
                col.remove(i)
                path.pop()
    if n == 0:
        return 0
    res = [0]
    col, master, slave = set(), set(), set()
    dfs(n, 0, col, master, slave, [], res)
    return res[0]

岛屿数量

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
输入：
11110
11010
11000
00000
输出：1
思路：深度优先遍历，将遍历过的相邻岛屿修改为0，计算矩阵中不相邻的1的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def numIslands(self, grid: List[List[str]]) -> int:
    def dfs(grid, row, col, rows, cols):
        if not 0<=row<rows or not 0<=col<cols or grid[row][col]=='0':
            return
        grid[row][col] = '0'
        dfs(grid, row+1, col, rows, cols)
        dfs(grid, row-1, col, rows, cols)
        dfs(grid, row, col+1, rows, cols)
        dfs(grid, row, col-1, rows, cols)
    if not grid:
        return 0
    ans = 0
    m, n = len(grid), len(grid[0])
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                ans += 1
                dfs(grid, i, j, m, n)
    return ans

岛屿的最大面积

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
思路：深度优先遍历。在一个土地上，以 4 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    def dfs(grid, seen, row, col, rows, cols):
        if 0<=row<rows and 0<=col<cols and grid[row][col]==1 and seen[row][col]==False:
            seen[row][col] = True
            up = dfs(grid, seen, row-1, col, rows, cols)
            down = dfs(grid, seen, row+1, col, rows, cols)
            left = dfs(grid, seen, row, col-1, rows, cols)
            right = dfs(grid, seen, row, col+1, rows, cols)
            return up+down+left+right+1
        else:
            return 0
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    seen = [[False]*n for _ in range(m)]
    maxArea = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j]==1:
                curArea = dfs(grid, seen, i, j, m, n)
                maxArea = max(maxArea, curArea)
    return maxArea

最大正方形面积

给定01矩阵
0 1 0 1 1 1
1 0 1 1 1 0
1 1 0 1 1 1
输出最大正方形面积，上面的例子面积是4。

1
2
3
4
5
6
7
8
9
10
11
12
13

def findMaxSquare(nums):
    if not nums or not nums[0]:
        return 0
    rows = len(nums)
    cols = len(nums[0])
    l = 0
    dp = [[0]*(cols+1) for _ in range(rows+1)]
    for i in range(1, rows+1):
        for j in range(1, cols+1):
            if nums[i-1][j-1] == 1:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
                l = max(dp[i][j], l)
    return l*l

Python

常用的Python标准库有哪些？

常用的标准库：os操作系统，time时间，random随机，pymysql连接数据库，math数学，threading线程，multiprocessing进程，queue队列
第三方库：django和flask，requests，virtualenv，hashlib，md5
常用的科学计算库：Numpy,Scipy,Pandas等。

Python有哪些特点和优点？

作为一门编程入门语言，Python主要有以下特点和优点：
1）可解释
2）具有动态特性
3）面向对象
4）简明简单
5）开源
6）具有强大的社区支持

深拷贝和浅拷贝之间的区别是什么？

深拷贝就是将一个对象拷贝到另一个对象中，这意味着如果你对一个对象的拷贝做出改变时，不会影响原对象。在Python中，我们使用函数deepcopy()执行深拷贝。

1
2

import copy
b = copy.deepcopy(a)

1

b = copy.copy(a)

列表和元组之间的区别是？

二者的主要区别是列表是可变的，而元组是不可变的。

在Python中如何实现多线程？

Python中的GIL（全局解释器锁）确保一次执行单个线程。一个线程保存GIL并在将其传递给下个线程之前执行一些操作，这会让我们产生并行运行的错觉。但实际上，只是线程在CPU上轮流运行。

在Python中是如何管理内存的？

Python有一个私有堆空间来保存所有的对象和数据结构。作为开发者，我们无法访问它，是解释器在管理它。但是有了核心API后，我们可以访问一些工具。Python内存管理器控制内存分配。另外，内置垃圾回收器会回收使用所有的未使用内存，所以使其适用于堆空间。

当退出Python时，是否释放全部内存？

不会。循环引用其它对象或引用自全局命名空间的对象的模块，在Python退出时并非完全释放。另外，也不会释放C库保留的内存部分。

Python中的命名空间是什么？

命名空间是一个命名系统，用于确保名称是唯一性，以避免命名冲突。

什么是PYTHONPATH？

它是导入模块时使用的环境变量。每当导入模块时，也会查找PYTHONPATH以检查各个目录中是否存在导入的模块。解释器使用它来确定要加载的模块。

什么是init?

init是Python中的方法或者结构。在创建类的新对象/实例时，将自动调用此方法来分配内存。所有类都有init方法。

Python中的self是什么？

self是类的实例或对象。在Python中，self包含在第一个参数中。但是，Java中的情况并非如此，它是可选的。它有助于区分具有局部变量的类的方法和属性。init方法中的self变量引用新创建的对象，而在其他方法中，它引用其方法被调用的对象。

什么是python迭代器？

迭代器是可以遍历或迭代的对象。

什么是python中的装饰器？

装饰器本质上是一个 Python 函数或类，它可以让其他函数或类在不需要做任何代码修改的前提下增加额外功能，装饰器的返回值也是一个函数/类对象。它经常用于有切面需求的场景，比如：插入日志、性能测试、事务处理、缓存、权限校验等场景。有了装饰器，我们就可以抽离出大量与函数功能本身无关的雷同代码到装饰器中并继续重用。概括的讲，装饰器的作用就是为已经存在的对象添加额外的功能。

os和sys的区别

os模块负责程序与操作系统的交互，提供了访问操作系统底层的接口;sys模块负责程序与python解释器的交互，提供了一系列的函数和变量，用于操控python的运行时环境。

什么是负指数，功能是什么？

Python中的序列是索引的，它由正数和负数组成。积极的数字使用’0’作为第一个索引，’1’作为第二个索引，进程继续使用。
负数的索引从’-1’开始，表示序列中的最后一个索引，’ - 2’作为倒数第二个索引，序列像正数一样前进。

什么是猴子补丁？

在运行期间动态修改一个类或模块。

请解释使用args和*kwargs的含义

当我们不知道向函数传递多少参数时，比如我们向传递一个列表或元组，我们就使用args。
在我们不知道该传递多少关键字参数时，使用*kwargs来收集关键字参数。

解释一下Python中的身份运算符

通过身份运算符‘is’和‘is not’，我们可以确认两个值是否相同。

为何不建议以下划线作为标识符的开头

因为Python并没有私有变量的概念，所以约定速成以下划线为开头来声明一个变量为私有。所以如果你不想让变量私有，就不要使用下划线开头。

range＆xrange有什么区别？

在大多数情况下，xrange和range在功能方面完全相同。它们都提供了一种生成整数列表的方法，唯一的区别是range返回一个Python列表对象，x range返回一个xrange对象。这就表示xrange实际上在运行时并不是生成静态列表。它使用称为yielding的特殊技术根据需要创建值。该技术与一种称为生成器的对象一起使用。因此如果你有一个非常巨大的列表，那么就要考虑xrange。

Pytorch、Tensorflow

tensorflow

Linux系统

linux常用指令

Git

git常见问题

Java

Java常见问题

2020年快手Y-tech面经

一面:

1、PCA原理，应用
PCA原理是在原有n维特征的基础上重新构造出k维全新的正交特征，PCA的工作就是从原始空间顺序中到一组互相正交的坐标轴，第一个坐标轴选择就是原始数据中方差最大的方向，第二个新坐标轴选取是与第一个坐标轴正交的平面中使方差最大的，第三个轴是与第1、2个轴正交的平面中方差最大的。依次类推可以得到n个这样的坐标轴。通过这种方式获得的新坐标轴，我们发现大部分方差都包含在前面k个坐标轴中，后面的坐标轴所含的方差几乎为0。于是我们可以忽略余下的坐标轴，只保留前面k个含有大部分方差的坐标轴。
PCA的应用范围有：1）数据压缩。数据压缩或者数据降维首先能够减少内存的使用，其次，数据降维能够加快机器学习的速度。2）数据可视化。在很多情况下，可能我们需要查看样本特征，但是高维度的特征根本无法观察，这个时候我们可以将样本的特征维数降到2个特征或3个特征，这样就可以采用可视化观察数据。3）去除数据噪声。
如何得到这些包含最大差异性的主成分方向呢？通过计算数据矩阵的协方差矩阵，然后得到协方差矩阵的特征值特征向量，选择特征值最大（即方差最大）的k个特征所对应的特征向量组成的矩阵。这样就可以将数据矩阵转换到新的空间中，实现数据特征的降维。得到协方差矩阵的特征值向量有两种方法：特征值分解协方差矩阵、奇异值分解协方差矩阵。
2、SVD原理，应用
SVD推导过程
3、SVM
SVM是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔大使它有别于普通的感知机，通过核技巧隐式的在输入空间直接求解映射空间中特征向量的内积，使其成为一个非线性分类器。SVM的学习策略是间隔最大化，可形式化为一个求解凸二次规划问题。
（重点）SVM算法推导过程
4、BN 优缺点 IN
BN的基本思想相当直观：因为深层神经网络在做非线性变换前的激活输入值随着网络深度加深或者在训练过程中，其分布逐渐发生偏移或变动，之所以训练收敛慢，一般是整体分布逐渐往非线性函数的取值区域的上下限两端靠近，所以这导致反向传播时低层神经网络的梯度消失，这是训练深层神经网络收敛越来越慢的本质原因。而BN就是通过一定的规范化手段，把层神经网络任意神经元这个输入值的分布强行拉回到均值为0方差为1的标准正态分布，其实就是把越来越偏的分布强制拉回到标准的分布，这样使得激活输入值落在非线性函数对输入比较敏感的区域，这样输入的小变化就是导致损失函数较大的变化。
BatchNorm的优点：1）极大提升了训练速度，使得收敛过程大大加快；2）还能增加分类效果，一种解释是这类似于Dropout的一种防止过拟合的正则化表达方式，所以不用Dropout也能达到相当的效果；3）调参过程也简单了，对于初始化要求没那么高，可以使用大的学习率。4）可以代替LRN
缺点：需要计算均值与方差，不适合动态网络或者RNN。计算均值方差依赖每批次，因此数据最好足够打乱。
IN的计算就是把每张图片的HW维度单独拿出来归一化处理，不受通道和batchsize 的影响
5、cross entropy和mse区别，求导
交叉熵是用来评估当前训练得到的概率分布于真实分布的差异情况，减少交叉熵损失就是在提高模型的预测准确率。交叉熵通常用作分类问题的代价函数。
均方误差是指参数估计值与真实值之差的平方的期望值，MSE可以评价数据的变化程度，MSE的值越小，说明预测模型描述实验数据具有更好的精度。通常用来做回归问题的代价函数。
6、sigmoid, softmax用途，区别
Sigmoid函数或Softmax函数可以将分类器的原始输出值映射为概率。Sigmoid函数会分别处理各个原始输出值，因此其结果相互独立，概率总和不一定为1。相反，Softmax函数的输出值相互关联，其概率的总和始终为1。
Sigmoid = 多标签分类问题 = 多个正确答案 = 非独占输出
Softmax = 多类别分类问题 = 只有一个正确答案 = 互斥输出
如果模型输出为非互斥类别，且可以同时选择多个类别，则采用Sigmoid函数计算该网络的原始输出值。
如果模型输出为互斥类别，且只能选择一个类别，则采用Softmax函数计算该网络的原始输出值。
7、单链表快排思想
8、概率题，a服从均匀分布(0,1)，b服从均匀分布(0,1),求max(a,b)的期望，拓展为n个独立变量，求max期望

二面:

1、cross entropy和mse能否互相替换？
不能。参见问题（为什么分类问题用 cross entropy，而回归问题用 MSE?）
2、多标签分类是否了解, 多标签分类激活函数?
解答
3、单链表快排实现

2019 海康威视

一面

1、faster-rcnn的整个从输入到输出的框架流程？
参见深度学习基础知识.faster rcnn
2、说一下rpn的原理
参见深度学习基础知识.faster rcnn
3、针对小目标的解决措施
（待解决）
4、如何解决样本不均衡的问题
参考答案
5、focal loss原理
参考解答

2019 旷视

一面

1、讲一下SENet的模块，为什么有性能提升，有什么好处
2、讲一下Focal loss 的2个参数有什么作用
3、讲一下FPN为什么能提升小目标的准确率
4、对One-stage的模型有没有了解
5、说一说One-stage和Two-stage两者有什么特点
6、说一说SSD具体是怎么操作的
7、算法题：leetcode.754。一个人从原点出发，可以往左走可以往右走，每次走的步数递增1，问能不能到达一个位置x？如果能，给出走的步数最少的方案？

蚂蚁金服

二面

1、分类和定位的不一致具体是什么
分类是给定一张图片或一段视频判断里面是否包含某种类别的目标
定位是标注出图片中这个目标的位置
检测是标注出这个目标的位置并知道目标的类别是什么
分割是解决每一个像素属于哪个目标物体或场景。
2、Faster-RCNN比起RCNN有什么改进的地方
3、Faster-RCNN如何进行一次计算
4、RoI Pooling如何操作
根据输入的图片，将ROI映射到feature map对应的位置，映射的规则就是把各个坐标除以输入图片与feature map的大小比值，得到feature map上的box坐标。然后将映射的区域划分为相同大小的sections，对每个sections进行max pooling的操作。
5、如果有很长，很小，或者很宽的目标，应该如何处理
采用FPN网络的多尺度预测方式，将高层特征和低层特征进行融合，增强特征的表达能力。
6、FPN具体是怎么操作的
将高层的特征进行两倍上采样和前一层的特征进行逐元素求和，然后将融合的特征输入3x3卷积（消除上采样的混叠效应）得到最后的特征。
7、FPN的特征融合具体是怎么做的
element-wise逐元素求和
8、FPN的特征融合为什么是相加操作呢
add操作可以看做是加入一种先验知识，通过add操作，网络会得到新的特征，这个心特征会反映原始特征的一些特性，但是原始特征的一些信息也会在这个过程中损失。但是concate就是讲原始的特征直接拼接，让网络学习如何融合特征，这个过程中信息不会损失，但是concate会带来的计算量较大，在明确原始特征的关系可以使用add操作，可以节省计算资源。
9、Soft-NMS是如何操作的
10、Softmax是什么，公式是什么样的
参考答案
11、Softmax的梯度是什么
12、BN原理
13、Pytorch的卷积是如何实现的
解答
14、还知道哪些传统计算机视觉的算法
(待解决)
15、SIFT原理，SIFT如何保持尺度不变性的
(待解决)

三面

1、说一个比较熟悉的网络
（项目中需准备）
2、对移动端的网络有没有什么了解
（待解决）
3、Focal loss怎么操作的
4、IoUNet怎么操作的
（待解决）
5、Soft-NMS怎么操作的
6、FPN的相加操作有没有尝试其他操作
7、对SSD和YOLO有没有什么了解？对SSD做过什么实验
8、对attention有什么了解
9、对跟踪有没有什么了解

四面

1、说一下focal loss的原理
2、介绍一下目标检测有哪些方向，最近的一些新的进展
3、说一下Soft-NMS的原理
4、说一下视觉的attention
5、平常是如何学习的
6、python多线程有了解吗
（待解决）
7、引用和指针的区别
（待解决）整理python相关问题
8、有什么想问的

五面

1、说比赛
2、比赛的数据集数量是怎么分布的
3、小目标占比如何
4、为什么说SENet泛化性好
5、SENet为什么效果好
6、FPN是怎么提升小目标检出率的
7、项目是一个什么问题呢
8、大目标如果有2个候选框和gt重合应该怎么处理
9、BN是解决什么问题的
10、BN为什么有效
11、什么时候开始接触这个方向的
12、学过哪些课程
13、学过机器学习吗

商汤

一面

1、InceptionV1为什么能提升性能
2、RPN哪里也可以提升小目标检出率
3、为什么说resnet101不适用于目标检测
4、小目标在FPN的什么位置检测
5、sigmoid和softmax的区别
6、detnet原理
7、一道算法题：输入一个文件，等概率输出某一行，只能顺序遍历
8、手写nms
(参考答案)[https://zhuanlan.zhihu.com/p/64423753]

二面

1、项目：最大的创新点是什么
2、SENet原理
3、Focal Loss 原理
4、Faster RCNN原理
5、用的roi pooling 还是roi align
6、IoUNet的原理
7、有了解过单阶段的检测器
8、说一下SSD的原理
9、还知道哪些轻量级的检测器
10、知道大网络用来学习小网络的方法吗
11、对分割有没有了解
12、用的什么机器(GPU)
13、比赛排名多少
14、用的什么模型

三面

1、什么时候开始接触CV课程
2、有没有上过CV的相关课程
3、SENet原理
4、SENet接在ResNet还有Inception的什么位置呢
5、IOUNet能有多少提升
6、NMS和soft-NMS原理
7、比赛遇到了什么不work的地方
8、假如一个图片中有一个很大的目标还有一个很小的目标，你会怎么处理呢
9、多尺度训练如何设置
10、为什么设置长边为固定的1600呢
11、介绍一下SSD和Faster-RCNN，说一下异同点
12、Faster-RCNN的回归目标是如何定义的
13、Faster-RCNN用的什么loss
14、smooth L1 loss为什么更有效
15、SGD、Adam之类优化的原理
16、BN、IN、LN、GN原理，BN为什么有效
17、Python有哪些常用的库报一遍
18、说一下使用Pytorch对cifar10数据集分类的整个代码流程，构建模型的过程是怎么样的
19、会C++吗
20、github的常用操作：上传、合并、分支之类的
（待整理）
21、linux的常用操作：查看文件大小、删除文件、查看文件行数、假如文件中有很多文件，每个文件中又有很多文件，如何删除全部文件
（待整理）
22、SiamRPN原理
23、轻量级模型
（待解决）

精锐视觉上海研究院

二面

算法题：1、给定一个乱序的数组，给定一个整数target，要求找出数组中所有和为该target的两个数。2、给定一张100元纸币，兑换为20，5，1元的纸币，要求将100元纸币正好兑换为上述面额的纸币，且每种面额不少于一张，写代码实现总共有多少种兑换方法。
2、生成式模型和判别式模型
（待解决）
3、解释最大似然估计和最大后验概率以及区别
4、神经网络中激活层的作用
5、faster rcnn中为什么要用3x3的巻积核代替5x5和7x7的巻积核。
6、防止过拟合的方式有哪些，请写出不少于五种。
7、请用深度学习的方法设计一套手写签名的识别方案。（不会）
8、请自主设计一套人脸识别方案，详述数据集、backbone、训练策略、模型测试等。
9、opencv的cascade级联分类器的工作原理以及具体的实现方式，训练级联分类器的注意事项。
（待解决）
10、HOG，LBP，Haar特征
（待解决）
11、简单介绍一下deep_sort算法

三面

1、问了一个深度学习的项目，项目简介，自己负责的部分，技术原理细节，创新点，难点。后续改进方案。
2、详细介绍一下deepsort算法，以及和传统跟踪方法的区别。
3、faster rcnn原理
4、详细解释deep_sort算法，与online track的方法有什么区别，目标跟踪丢失怎么办

聚时科技

一面

1、图像处理，中值滤波和平滑滤波的区别
2、说几个机器学习常用的算法，SVM的目标函数是什么，是如何实现分类的，KNN的原理以及分类流程
3、常见的目标分类的基础网络有哪些，mobilenet和shufflenet是如何实现卷积加速的。

二面

1、给了一个7x7的灰度图像和一个2x2的卷积核，分别写出腐蚀和膨胀运算后的图像。
2、手写代码实现二维卷积过程，不得调用TF、Keras等深度学习库。
3、手写代码实现一个8邻接连通域算法，不得调用opencv等图像处理库。
4、写出三个常用的机器学习算法，并介绍其原理和使用场景。
5、请写出如些解决样本不平衡问题。

腾讯

1、YOLO V2 V3你对哪个熟悉，讲一下细节实现
2、多尺度问题
3、anchor基础知识
4、人脸识别现在常用算法
5、语义分割到实例分割怎么做
6、GAN是否了解，如何通俗的讲其原理
7、PCA原理LDA原理
8、SVM+HOG
9、XGBoost
10、CNN、RCNN、FRCNN，有可能问你其中一个细节的关键
11、TensorFlow这些框架你谈一下看法以及对其他框架的了解
12、现在机器学习、深度学习这么火，你有什么看法
13、机器学习、深度学习你对他们的理解是什么
14、Relu比Sigmoid使用多的原因
15、Loss不升反降的原因，如何解决
16、SSD细节
17、Linux 权限的意义
18、块操作的操作的步骤以及快捷方式

搜狗

一面

1、RCNN系列的算法流程和区别；
2、Fast RCNN中 bbox 回归的损失函数什么；
3、解释 ROI Pooling 和 ROI Align；
4、Mask RCNN中 mask branch 如何接入 Faster RCNN中；
5、解释 FPN （没细看，面完补的）；
6、优化算法举例和他们的区别（SGD、SGDM、RMSprop、Adam）；
7、训练不收敛的原因有哪些；
8、简述 Inception v1-v4；
9、简述 CNN 的演变；
10、BN 的作用和缺陷，以及针对batch_size小的情况的改进（GN）

旷世CV岗

1.自我介绍，项目介绍
2.FCN结构介绍，上采样的具体操作
3.空洞卷积原理，deeplab v1 v2的改进
4.focal loss介绍, lovasz loss数学原理
5.一道题，计算卷积操作的浮点计算量，比较简单
6.介绍下RPN的原理
7.mobile net
8.unet的缺点

选择排序

算法过程：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素就和自己交换）。然后在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，知道整个数组排序。

1
2
3
4
5
6
7
8

def selectionSort(nums):
    for i in range(len(nums)-1):
        minIndex = i
        for j in range(i+1, len(nums)):
            if nums[j]<nums[minIndex]:
                minIndex = j
        nums[i], nums[minIndex] = nums[minIndex], nums[i]
    return nums

插入排序

算法过程：1）从数组第2个元素开始抽取元素。2）把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较，知道遇到不必它大的元素，然后插入到这个元素的右边。3）继续选取第3,4,…,n个元素，重复步骤2，选择适当的位置插入。

1
2
3
4
5
6
7
8

def insertionSort(nums):
    for i in range(len(nums)-1):
        curNum, preIndex = nums[i+1], i
        while preIndex>=0 and curNum<nums[preIndex]:
            nums[preIndex+1] = nums[preIndex]
            preIndex -= 1
        nums[preIndex+1] = curNum
    return nums

冒泡排序

算法过程：1）把第一个元素和第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着比较第二个与第三个元素，如果第二个比第三个大，则交换它们的位置…。这样一趟比较交换之后，排在最右的就会是最大的数。2）除去最右的数，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成。

1
2
3
4
5
6

def bubblesort(nums):
    for i in range(len(nums)-1, 0, -1):
        for j in range(0, i):
            if nums[j]>nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

1
2
3
4
5
6
7
8
9
10
11
12

def bubblesort2(nums):
    if not nums:
        return
    for i in range(len(nums)-1, 0, -1):
        swapped = False
        for j in range(0, i):
            if nums[j]>nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                swapped = True
        if not swapped:
            break
    return nums

希尔排序

希尔排序可以说是插入排序的一种变种，无论是插入排序还是冒泡排序，如果数组的最大值刚好是在第一位，要将它挪到正确的位置就需要n-1次移动。也就是说原数组的一个元素如果距离它正确的位置很远，则需要与相邻元素交换很多次才能到达正确的位置，这是相对比较花时间了。
希尔排序就是为了加快速度简单地改进插入排序，交换不相邻的元素对数组的局部进行排序。基本思想是：先将整个待排序列分割成为若干子序列分别进行插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。希尔排序的核心在于间隔序列的设定，既可以提前设定好间隔序列，也可以动态地定义间隔序列。

1
2
3
4
5
6
7
8
9
10
11
12
13

def shellSort(nums):
    gap = 1
    while gap<len(nums)//3:
        gap = gap*3+1
    while gap>0:
        for i in range(gap, len(nums)):
            curNum, preIndex = nums[i], i-gap
            while preIndex>=0 and curNum<nums[preIndex]:
                nums[preIndex+gap] = nums[preIndex]
                preIndex -= gap
            nums[preIndex+gap] = curNum
        gap //= 3
    return nums

归并排序

归并排序使用递归分治的思想，其基本思想是：把待排序列看成两个有序的子序列，然后合并两个子序列，接着把子序列再看成两个有序的子子序列，…，以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def mergeSort(nums):
    if len(nums)<=1:
        return nums
    # 归并过程
    def merge(left, right):
        result = []
        i = j = 0
        while i<len(left) and j<len(right):
            if left[i]<=right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result = result + left[i:] + right[j:]
        return result
    # 递归过程
    mid = len(nums)//2
    left = mergeSort(nums[:mid])
    right = mergeSort(nums[mid:])
    return merge(left, right)

1
2
3
4
5
6
7
8
9
10
11
12

def mergeSort2(nums):
    i = 1  # i是步长
    while i<len(nums):
        left = 0
        while left<len(nums):
            mid = left+i
            right = min(left+2*i, len(nums))
            if mid<right:
                nums[left:right]=merge(nums[left:mid], nums[mid:right])
            left += 2*i
        i *= 2
    return nums