例题
K-means 算法是一种基于______的聚类算法
答案：基于样本集合划分
解释：数据划分为 k 个不同类别的算法。划分的依据是：每个样本被归类到距离其最近的簇中心（即均值点）。
主成分分析（PCA）的主要目的是______。
答案：降维
解释：PCA 的目的是通过线性变换将高维数据转换为低维数据，同时尽可能保留数据的主要特征。
在模型评估中，______曲线用于评估二分类模型的性能。
答案：ROC
解释：ROC 曲线绘制了不同分类阈值下的真阳性率 (TPR) 和假阳性率 (FPR)，用以评估模型的分类性能。
感知机的输入为实例的______，输出为实例的类别，取 +1 和 -1 二值。
答案：特征
解释：感知机是一种线性分类器，输入为特征向量，输出为二分类标签。
在线性回归中，如果数据集中的特征数量远大于样本数量，可能导致______问题。
答案：过拟合
解释：当特征过多时，模型容易记住训练数据中的噪声，而不能很好地推广到新数据。
在评估分类模型时，混淆矩阵中的真正例（True Positive, TP）表示______。
答案：被正确预测为正类的样本数量
解释：TP 是实际为正类且被模型正确分类为正类的样本数。
PCA 通过______方式实现数据降维。
答案：线性变换
解释：PCA 通过计算数据协方差矩阵的特征向量和特征值，找到数据的主成分，进而实现降维。
在随机森林中，每个决策树都是在______的样本集上训练的。
答案：有放回采样（Bootstrap Sampling）
解释：随机森林通过在训练集中有放回采样生成多个子样本，每棵树在不同子样本上训练。
梯度提升（Gradient Boosting）方法通过逐步构建多个弱学习器，每个新的学习器都试图纠正前一个学习器的______。
答案：误差
解释：梯度提升算法通过迭代方式减少前一轮模型的残差，从而提升整体模型的性能。
1. 什么是过拟合，并给出两种防止过拟合的方法
过拟合：
过拟合是指模型在训练数据上表现很好，但在测试数据或新数据上的泛化能力较差。它通常是由于模型过于复杂，能够“记住”训练数据中的噪声和细节，而不是学习到数据的通用模式。
防止过拟合的方法：
- 正则化：使用 L1或 L2正则化（如 Ridge 或 Lasso 回归）增加损失函数中的惩罚项，限制模型复杂度。
- 数据增强：对训练数据进行增强（如图像旋转、翻转、缩放等），增加样本多样性，提升模型的泛化能力。
2. 简述 K 折交叉验证与留一法的基本思想及其特点
-
K 折交叉验证：
将数据集分为 K个子集，每次用其中 K−1 个子集作为训练集，剩下的 1 个子集作为验证集，重复 K次，最终取验证结果的平均值作为模型的评估结果。特点：适用于数据量较大的情况，能平衡训练和验证的样本比例，计算效率较高。 -
留一法（LOO，Leave-One-Out）：
每次只将一个样本作为验证集，剩下的样本作为训练集，重复 N 次（N是样本数）。特点：适用于小样本数据，验证结果较为稳定，但计算开销较大。
3. 简述线性回归与逻辑回归的区别
-
模型目标：
- 线性回归：用于预测连续变量，通过最小化残差平方和拟合线性模型。
- 逻辑回归：用于分类问题，通过 sigmoid 函数将线性模型的输出映射为概率，解决二分类或多分类问题。
-
损失函数：
- 线性回归：使用均方误差 (MSE)。
- 逻辑回归：使用对数损失函数（Log Loss）。
-
输出范围：
- 线性回归：输出为任意实数。
- 逻辑回归：输出为 [0, 1] 的概率值。
4. 简述 K 近邻 (KNN) 算法的基本原理
KNN 是一种基于实例的监督学习算法，用于分类或回归。
原理：
- 给定测试样本，计算它与训练集中所有样本的距离（如欧几里得距离）。
- 选择距离最近的 K 个样本。
- 分类任务：根据 K 个最近邻样本的多数类别，确定测试样本的类别。
- 回归任务：计算 K 个最近邻样本的平均值作为预测结果。
5. 什么是梯度下降法？它如何工作？
梯度下降法：
梯度下降是一种优化算法，用于最小化目标函数（如损失函数）。
工作原理：
- 从随机初始化的参数出发，计算损失函数对参数的梯度。
- 沿梯度下降的方向（即负梯度方向）更新参数：
其中 a是学习率，∇J(θ)是损失函数的梯度。 - 迭代更新直到损失函数收敛或达到最大迭代次数。
6. 简述深度学习中的反向传播算法
反向传播算法用于计算神经网络中各层参数的梯度，从而更新权重以最小化损失函数。
步骤：
- 前向传播：计算网络输出及损失函数值。
- 误差计算：根据目标值和输出值计算误差。
- 反向传播：从输出层开始，按层反向计算损失函数对每个权重的梯度，误差反向传播
- 参数更新：使用梯度下降等优化方法更新参数。
7. 简述决策树算法的优点和缺点
优点：
- 易于理解和解释，具有可视化特性。
- 能处理数值型和分类型数据，适应性强。
- 不需要特征标准化或归一化，且能捕捉非线性关系。
缺点：
- 容易过拟合，特别是树结构过深时。
- 对小数据集或少量噪声数据敏感，可能导致不稳定性。
- 单独使用时精度不高，通常与集成方法（如随机森林）结合使用。
8. 简述 KNN 算法的优点和缺点
优点：
- 简单直观，无需模型训练。
- 能够处理多分类问题，适用于小规模数据集。
- 可直接使用距离度量方法处理非线性分布的数据。
缺点：
- 对高维数据不友好（维度灾难问题）。
- 计算开销大（特别是样本数据量较大时）。
- 对噪声数据敏感，易受异常值影响。
- 类别不平衡准确率低
第一章 机器学习及监督学习概论
机器学习基本过程:
- 数据收集与预处理
- 特征选择
- 模型选择与训练
- 模型预测与评估
- 模型部署
统计学习和机器学习：
- 研究方法差异 ：
统计学研究形式化和推导
机器学习更容忍一些新方法
- 维度差异
统计学强调低维空间问题的统计推导（confidence intervals, hypothesis tests, optimal estimators）
机器学习强调高维预测问题
- 统计学和机器学习各自更关心的领域：
统计学: survival analysis, spatial analysis, multiple testing, minimax theory, deconvolution, semiparametric inference, bootstrapping, time series.
机器学习: online learning, semisupervised learning, manifold learning, active learning, boosting.
分类（按数据是否带有标注）
监督学习(Supervised Learning)
半监督学习(Semi-Supervised Learning)
无监督学习(Un-supervised Learning)
强化学习(Reinforcement Learning, RL)
主动学习（Active Learning）
机器学习概念和名词约定
联合概率分布
- 假设输入与输出的随机变量X和Y遵循联合概率分布P(X,Y)。P(X,Y)表示了给定 X 和 Y 同时取某些值的概率。在监督学习中，训练数据集的样本通常认为是根据这个联合概率分布 P(X,Y)独立同分布地生成的。
- P(X,Y)为分布函数（离散随机变量）或分布密度函数（连续随机变量）
- 对于学习系统来说，联合概率分布是未知的。（因此需要通过训练数据来估计）
- 训练数据和测试数据被看作是依联合概率分布P(X,Y)独立同分布产生的
假设空间
- 监督学习目的是学习一个由输入到输出的映射，称为模型
- 由输入空间到输出空间的映射的集合，也就是模型的集合就是假设空间（hypothesis space）
- 概率模型：条件概率分布P(Y|X)，在给定输入 X的情况下，输出 Y 的概率分布。学习的目标是通过模型估计这个条件概率分布。决策函数：Y=f(X)，通过训练数据学习到的输入到输出的映射，它用于做出预测。
问题的形式化
机器学习监督学习和无监督学习的任务
监督学习
- 回归(regression)：使用计算机学习出的模型进行预测输出尽可能符合真实值，得到的是连续值。 等价于函数拟合。
- 分类(classification)：使用计算机学习出的模型进行预测得到的是离散值。 二分类、多分类
无监督学习
- 聚类任务：将具有相似性质的样本组成一个簇，聚类样本是不带标注的样本。
- 降维任务：减少数据的维度，对数据进行降噪、去冗余，方便计算和训练。
其他学习的介绍
强化学习
用于描述和解决智能体（agent）在与环境的交互过程中通过学习策略 以达成回报最大化或实现特定目标的问题。
半监督学习
- 少量标注数据，大量未标注数据
- 利用未标注数据的信息，辅助标注数据，进行监督学习
- 较低成本
主动学习
- 机器主动给出实例，教师进行标注
- 利用标注数据学习预测模型
机器学习的分类
按算法分类：
在线学习（online learning）
批量学习（batch learning）
按技巧分类：
贝叶斯学习（Bayesian learning）
核方法（Kernel method）
机器学习方法三要素
方法 = 模型 + 策略 + 算法
1.模型
概率模型
- 决策树
- 朴素贝叶斯
- 隐马尔科夫模型
- 高斯混合模型
非概率模型
按判别函数是否线性，可分为线性模型与非线性模型：
线性模型
- 感知机
- 线性支持向量机
- K近邻（KNN）
- K-means
非线性模型
- 核支持向量机（SVM）
- AdaBoost
- 神经网络
2.策略
损失函数 (Loss Function)
一次预测的好坏，损失函数用于度量模型预测结果与真实结果之间的差异。它通常是针对单次预测的好坏进行评估。
风险函数 (Risk Function)
平均意义下模型预测的好坏。风险函数是损失函数的期望，即在整个数据分布上，损失函数的平均表现。
经验风险 (Empirical Risk)：计算所有训练样本上的损失的平均值。
经验风险最小化与结构风险最小化
当样本容量很小时，经验风险最小化学习的效果未必很好，会产生“过拟合over-fitting”
结构风险最小化 structure risk minimization，为防止过拟合提出的策略，等价于正则化（regularization），加入正则化项regularizer，或罚项 penalty term
3.算法
学习模型的具体计算方法
如果最优化问题有显式的解析式，算法比较简单
但通常解析式不存在，就需要数值计算的方法
模型评估与模型选择
泛化能力：模型对未知数据的预测能力。常采用的办法是通过测试误差来评价学习方法的泛化能力，依赖于测试数据集。
测试误差是对真实误差的可靠估计，最重要的条件是：
- 测试集样本与训练集样本独立；
- 测试集样本与未来样本独立同分布；
- 测试集样本数量足够大。
过拟合与模型选择
过拟合是指学习时选择的模型所包含的参数过多，以至于出现这一模型对已知数据预测的很好，但对未知数据预测得很差的现象。
模型评估
混淆矩阵：评估分类模型性能的工具
混淆矩阵包含四部分的信息：
1) 真阴率（TN）表明实际是负样本预测成负样本的样本数。
2) 假阳率（FP）表明实际是负样本预测成正样本的样本数。
3) 假阴率（FN）表明实际是正样本预测成负样本的样本数。
4) 真阳率（TP）表明实际是正样本预测成正样本的样本数。
精确度 (Precision)
一句话速记:预测中的真正比例
召回率 (Recall)
一句话速记:真实中的真正比例
准确率 (Accuracy)
一句话速记:对角线/所有
F1 分数 (F1 Score)
一句话速记:2pr/(r+p)
特异度 (Specificity)
一句话速记:真实中的假的比例
ROC的曲线绘制步骤：
1、将全部样本按概率递减排序
2、阈值从1至0变更，计算各阈值下对应的（FPR,TPR）数值对，
其中TPR也是召回率，这是x轴；TPR是1-特异度，这是y轴
3、将数值对绘制直角坐标系中
举个列子：
阈值=1时
| T | F | |
| P | 0 | 0 |
| N | 5 | 5 |
FPR=负的预测为正的数量/原本为负的数量 = 0 / 5 = 0 (样本3、6、7、8、10)
TPR=正的预测为正的数量/原本为正的数量 = 0 / 5 = 0 (样本1、2、4、5、9) 此时得到一个点（0,0），即为ROC曲线的第一个点。
阈值=0.95时
| T | F | |
| P | 1 | 0 |
| N | 4 | 5 |
FPR=负的预测为正的数量/原本为负的数量=0/5 = 0 (样本3、6、7、8、10)
TPR=正的预测为正的数量/原本为正的数量=1(样本1)/5 = 0.2 (样本1、2、4、5、9) 此时得到一个点（0,0.2），即为ROC曲线的第二个点。
ROC曲线和PR曲线的适用场景：
ROC适用 1. 样本分布较为均匀的情况，可以稳定地反映模型在不同阈值下的整体性能。 2.在需要评估分类器在不同分类阈值下的敏感性和特异性时，ROC曲线特别有用。 3.在医疗诊断、信用评分、欺诈检测等领域广泛应用，帮助用户选择合适的分类阈值以实现风险控制的平衡。
PR适用 1. 不平衡数据集：当数据集中正类样本远少于负类样本时，PR曲线能够更准确地反映模型在少数类别上的性能。 2.在信息检索、推荐系统、异常检测等领域，PR曲线被用来评估搜索结果的质量、推荐算法的效果以及模型对异常样本的识别能力。
监督学习的两大方法
-
生成方法 (Generative Methods)
生成方法学习数据的生成分布，目标是建模输入与输出之间的联合概率分布 P(X,Y)，从而生成新的数据样本。常见的生成模型包括高斯混合模型（GMM）和朴素贝叶斯分类器。 -
判别方法 (Discriminative Methods)
判别方法关注的是输入数据如何映射到输出类别标签，直接学习条件概率分布 P(Y∣X)。常见的判别方法有K近邻法、感知机、决策树、logistic回归模型、最大熵模型、支持向量机、提升方法和条件随机场。
各自优缺点：
生成方法：可还原出联合概率分布P(X,Y), 而判别方法不能。生成方法的收敛速度更快，当样本容量增加的时候，学到的模型可以更快地收敛于真实模型；当存在隐变量时，仍可以使用生成方法，而判别方法则不能用。
判别方法：直接学习到条件概率或决策函数，直接进行预测，往往学习的准确率更高；由于直接学习Y=f(X)或P(Y|X),可对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习过程。
第二章 感知机
梯度下降法求解最优化问题
注意：这个x是x1、x2，所以这个w0=（0，0）。y的值只有两个+1、-1.
初识深度神经网络
激活函数
为什么使用激活函数？
a. 不使用激活函数，每一层输出都是上层输入的线性函数，无论神经网络有多少层，输出都是输入的线性组合。
b. 使用激活函数，能够给神经元引入非线性因素，使得神经网络可以任意逼近任何非线性函数，这样神经网络就可以利用到更多的非线性模型中。
激活函数需要具备什么样的性质呢？
1. 连续并可导（允许少数点上不可导）的非线性函数。可导的激活函数可以直接利用数值优化的方法来学习网络参数。
2. 激活函数及其导函数要尽可能的简单，有利于提高网络计算效率。
3. 激活函数的导函数的值域要在一个合适的区间内，不能太大也不能太小，否则会影响训练的效率和稳定性。
Sigmoid函数
缺点： 梯度消失：当输入值非常大或非常小时，Sigmoid函数的梯度（导数）接近于0，这会导致在反向传播过程中权重更新非常缓慢，甚至停止学习。 非零中心化：Sigmoid函数的输出不是以0为中心的，这会导致后续层的输入也非零中心化，从而影响权重更新的效率。
Tanh（双曲正切）函数
与Sigmoid函数相比，Tanh函数的优点包括： 零中心化：Tanh函数的输出是以0为中心的，这有助于改善权重更新的效率。 更大的梯度：虽然Tanh函数在输入值非常大或非常小时也会出现梯度接近0的情况，但其梯度在大部分情况下比Sigmoid函数要大，这有助于缓解梯度消失的问题。
然而缺点，Tanh函数仍然存在梯度消失的问题，特别是在深层网络中。
ReLU（修正线性单元）函数
优点： 计算简单：ReLU函数只需要进行简单的阈值判断，计算速度快。 缓解梯度消失：在正区间内，ReLU函数的梯度为常数1，这有助于缓解梯度消失的问题。 促进稀疏性：ReLU函数使得部分神经元的输出为0，这有助于网络的稀疏性，从而减少计算量并可能防止过拟合。
缺点： 死亡ReLU问题：当输入值小于0时，ReLU函数的输出始终为0，这可能导致部分神经元永远不会被激活，从而影响网络的性能。
设计 MLP 时的一些关键考虑点
-
层数（隐藏层数量）：
- 至少一个隐藏层：MLP至少需要一个隐藏层，以引入非线性变换，增加模型的表达能力。
- 增加层数：更多的隐藏层可以使网络具有更强的非线性拟合能力，但也可能导致过拟合和训练困难。因此，需要根据数据的复杂性和任务需求来决定隐藏层的数量。
- 超参数搜索：最佳的层数通常需要通过实验来确定，如使用交叉验证等方法来选择最佳的网络结构。
-
每层神经元数量（隐藏层大小）：
- 输入层神经元：通常与输入数据的特征数量相同。
- 隐藏层神经元：选择隐藏层神经元数量时，常用的一种经验法则是：隐藏层神经元数量 ≈ (输入层神经元数量 + 输出层神经元数量) * 2 / 3。这一法则并非固定，实际选择时可以根据任务复杂度和数据集的特征进行调整。
- 过多的神经元：会导致计算开销增加、训练时间变长、甚至可能引发过拟合。
- 过少的神经元：可能无法捕捉到数据中的复杂模式，导致模型表现不佳。
- 权重初始化 -- 随机初始化、He初始化、Glorot初始化
优化策略 -- 为提高MLP的性能，可以采用正则化、Dropout、批量归一化等优化策略来防 止过拟合、加快训练速度和提高训练稳定性。同时，也可以通过超参数调优来 找到最优的网络结构和训练参数组合。
BP（反向传播）算法训练中可能遇到的一些问题包括：
-
易陷入局部最小值：由于BP算法的优化过程是基于梯度下降的，可能会在某些局部最小值或鞍点停留，从而影响最终的优化效果。
-
训练时间长，收敛速度慢：尤其在处理大规模数据时，梯度下降的训练过程可能非常缓慢。收敛速度与学习率的设置、网络结构以及样本复杂度密切相关。
-
隐节点的选取缺乏理论指导：隐层节点数和网络层数的选择通常依赖经验，缺少明确的理论指导，容易导致过拟合或欠拟合。
-
过拟合问题：模型在训练集上表现良好，但在测试集或未知数据上表现较差，说明模型在训练数据上过度拟合，导致泛化能力差。
-
梯度消失/梯度爆炸：深度网络中，梯度在传播过程中可能会变得极小（梯度消失）或过大（梯度爆炸），从而导致训练难以进行。
可能的原因：
- 网络结构或激活函数问题：不合适的网络结构或激活函数会影响梯度传播的效率。
- 训练样本不充分或不合适：样本过少或样本的代表性不足，导致网络难以学习到有效的特征。
- 初始值不合适，学习率不合适：初始权重设置不当或学习率过大/过小都会影响模型的训练效果。
- 缺乏恰当的预处理：如特征未归一化或标准化，导致训练过程中梯度下降不稳定。
- 需要更好的训练策略：训练过程中没有合适的优化方法，导致收敛速度慢或停滞。
- 运气问题：初始值的随机性、优化过程中的偶然因素，可能会对结果产生影响。
- 问题提出的有问题：数据本身可能没有真正的关系或模型假设不成立。
改进BP算法的可能策略：
-
激活函数选择：
常见的激活函数有Sigmoid、tanh和ReLU等。选择合适的激活函数可以有效缓解梯度消失问题。 -
特征尺度调整或归一化：
对输入特征进行归一化或标准化，使得各个特征的尺度相对一致，避免某些特征对训练过程的影响过大。 -
目标值调整：
在二分类问题中，可以用0.1对0.9替代0对1，避免目标值不均衡影响训练效果。 -
引入“伪样本”增大训练样本集：
通过数据增强（如加噪、引入不变性特征的样本，平衡类别样本等）来增加训练集的多样性。 -
隐层节点数和层数调整：
根据样本规模和问题复杂度，合理选择隐层的数量和每层节点数。如果网络过大，可能会导致过拟合；过小则可能导致欠拟合。网络剪枝：减少冗余节点或层数，降低模型复杂度。
神经网络的主要优缺点：
优点
- 并行处理能力
- 自适应性、学习能力强
- 非线性映射能力
- 鲁棒性和容错性
应用领域广泛：图像识别、语音识别、自然语言处理、推荐系统
缺点:
- “黑匣子”问题
- 耗费时间和算力
- 需要大量的训练数据
- 过拟合问题
第三章 k近邻法（KNN）
K-Nearest Neighbors算法原理：
如图，假设已经获取一些动物的特征，且已知这些动物的类别。现在需要识别一只新动物，判断它是哪类动物。首先找到与这个物体最接近的k个动物。假设k=3，则可以找到2只猫和1只狗。由于找到的结果中大多数是猫，则把这个新动物划分为猫类。
K-Nearest Neighbors算法特点
优点
- 精度高
- 对异常值不敏感
- 无数据输入假定
缺点
- 计算复杂度高
- 空间复杂度高
- 适用数据范围
- 数值型和标称型
工作原理
存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每个数据与所属分类的对应关系。
输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。
一般来说，只选择样本数据集中前K个最相似的数据。K一般不大于20，最后，选择k个中出现次数最多的分类，作为新数据的分类。
KNN方法三个核心要素：k值的选择、距离度量、分类决策规则
K值的选择
如果选择较小的K值
- “学习”的近似误差（approximation error)会减小，但 “学习”的估计误差（estimation error) 会增大
- 噪声敏感
- K值的减小就意味着整体模型变得复杂，容易发生过拟合.
如果选择较大的K值
- 减少学习的估计误差，但缺点是学习的近似误差会增大.
- K值的增大就意味着整体的模型变得简单.
K值一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。
距离度量
特征空间中两个实例点的距离是两个实例点相似程度的反映。
常用的距离是欧式距离，此外还有更一般的LP距离、余弦距离、球面距离等。
不同的距离度量所确定的近邻点不同。
KNN分类决策规则
分类结果的确定往往采用多数表决原则，即由输入实例的k个最邻近的训练实例中的多数类决定输入实例的类别。
KNN面临的挑战：
- 特征选择与表示
- 距离度量与相似度计算
- K值的选择
- 样本不平衡问题
- 噪声和异常值
- 可扩展性和实时性
KD树
其中：k是维度，j是树的深度（0开始），T={（x1，x2）……}
深度为0，l=0%2+1=1 所以选择x1为切分的坐标轴
按照x1排序：{(2,3)(4,7)(5,4)(7,2)(8,1)(9,6)},选择中位数作为中位数为切分节点(7,2)。
深度为1，l=1%2+1=2 所以选择x2为切分的坐标轴
然后看左边(2,3)(4,7)(5,4)，右边(8,1)(9,6)
按照x2排序左边{(2,3)(5,4)(4,7)},选择中位数作为中位数为切分节点(5,4)。右边{(8,1)(9,6)}选择(9,6).
深度为2。。。。。
KD树搜索
算法：kd树的最近邻搜索
输入：已构造的kd树，目标点x；
输出：x的最近邻。
在kd树中找出包含目标点x的叶结点：从根结点出发，递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。（什么是当前维度，交替比较（x1，x2，x1……）
星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行相关的‘回溯'操作。也就是说，算法首先沿搜索路径反向查找是否有距离查询点更近的数据点。
查询（2.1,3.1）为例：
二叉树搜索：先从（7,2）点开始进行二叉查找，然后到达（5,4），最后到达（2,3），此时搜索路径中的节点为<(7,2)，(5,4)，(2,3)>，首先以（2,3）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为0.1414，
回溯查找：在得到（2,3）为查询点的最近点之后，回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如下图所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中(图中灰色区域)去搜索；
最后，再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。
查询点（2，4.5）
同样先进行二叉查找，先从（7,2）查找到（5,4）节点，在进行查找时是由y = 4为分割超平面的，由于查找点为y值为4.5，因此进入右子空间查找到（4,7）。
形成搜索路径<(7,2)，(5,4)，(4,7)>，但（4,7）与目标查找点的距离为3.202，而（5,4）与查找点之间的距离为3.041，所以（5,4）为查询点的最近点；
以（2，4.5）为圆心，以3.041为半径作圆，如下图所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找，也就是将（2,3）节点加入搜索路径中得<(7,2)，(2,3)>；于是接着搜索至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5；
回溯查找至（5,4），直到最后回溯到根结点（7,2）的时候，以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如下图所示。至此，搜索路径回溯完，返回最近邻点（2,3），最近距离1.5。
第四章 朴素贝叶斯法
假设待识别的特征为X，样本分为n类，各类的先验概率和各类的类条件密度均已知， 由Bayes公式可知后验概率为：
朴素贝叶斯算法（极大似然估计）
一般题型，给出一个样本的几个特征
输出：实例x的分类
例题
使用朴素贝叶斯分类预测一个未知样本的分类，数据样本用属性“天气”，“气温”，“湿度”和“风力”指述。目标分类属性“是否适合打网球”具有两个不同值(即“是”，“否”)。设C1对位于分类“是否适合打网球”=“是”，而C2对应于分类“是否话合打网球”=“否”
我们的预测样本为x=(“天气”=“雨”，“气温”=“凉”，“湿度”=“高”，“风力”=“弱“)， 根据朴素贝叶斯算法计算出X的属于不同分类目标值的概率，判断最终的预测结果
第一步计算两个类别的先验概率：每一类样本整体出现的概率。
图中是14个样本，9个"是"，5个"否"
p(c1)=9/14 p(c2)=5/14
第二步 计算条件概率：某一类中的某样本特征出现的概率
| p(天气=雨|c1)=3/9 | p(天气=雨|c2)=2/5 |
| p(“气温”=“凉”|c1)=3/9 | p(“气温”=“凉”|c2)=2/5 |
| p(“湿度”=“高”|c1)=3/9 | p(“湿度”=“高”|c2)=4/5 |
| p(“风力”=“弱“|c1)=5/9 | p(“风力”=“弱“|c2)=2/5 |
第三步 全部相*比较大小判断类别是c1 or c2
p(天气=雨|c1)p(“气温”=“凉”|c1)p(“湿度”=“高”|c1)p(“风力”=“弱“|c1)
p(天气=雨|c2)p(“气温”=“凉”|c2)p(“湿度”=“高”|c2)p(“风力”=“弱“|c2)
第五章 决策树
决策树学习包括三个步骤：特征选择、决策树的生成、决策树的修剪
理想的决策树有三种：
(1)叶子结点数最少：这意味着我们希望决策树尽量少的分支最终达到决策结果；
(2)叶子结点深度最小；
(3)叶子结点数最少且叶子结点深度最小。
决策树ID3算法
ID3算法的核心是在决策树各个结点上应用最大信息增益准则选择特征，递归地构建决策树。
信息增益(Information gain)表示得知特征X的信息而使得类Y的信息的不确定性(不纯度)减少的程度
熵是表示随机变量不确定性(不纯度)的度量。
例题
有下列样本数据，要用决策树算法进行分类，请计算相关变量。
(1)计算经验熵H(D)
(2)分别以A1、A2、A3表示性别、车型、村衣尺码这三个特征，试计算这三个特征各自对应的信息增益。
(3)三个特征中哪一个是最优特征？
(4)求特征A1的基尼系数。
解：
（1）有20个样本，10个c0，10个c1
=-(10/20log_2 10/20 +10/20log_2 10/20)
=1
(2)
A1性别信息增益=1--[10/20 H(D_男)+10/20 H(D_女)]
=1--[10/20 (6/10 log_2 6/10+4/10 log_2 4/10)+10/20 (4/10 log_2 4/10+6/10 log_2 6/10)
（3）
最优特征是g(D，A)最大的特征
（4）A1的基尼系数
如何计算基尼系数：
先画图，比如特征车型
| 类别 | 数量 |
|---|---|
| 豪华 C1 | 7 |
| 豪华 C0 | 1 |
| 家用 C1 | 3 |
| 家用 C0 | 1 |
| 运动 C1 | 0 |
| 运动 C0 | 8 |
gini(D,A=豪华)=(7+1)/20 [2* 7/8 *1/8] + (20-8)/20 [2* 3/12 * 9/12]
豪华 非豪华
gini(D,A=家用)=
gini(D,A=运动)=
如果gini最小说明这个特征是最优特征，A=xxx是最优切分点。
以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多但并不一定对分类有重要贡献的特征的问题。
这个计算类似经验熵，比如H_A1(D)=-(10/20log_2 10/20 +10/20log_2 10/20)
男 女
和经验熵区别在于经验熵是y的c0 c1，而这里是是看x。
CART与ID3的不同
二元划分： 二叉树不易产生数据碎片，精确度往往也会高于多叉树
- ID3: ID3算法使用多叉树（每个节点可以有多个子节点），即在每个节点上根据属性的不同值进行划分，通常适用于分类问题。
CART中选择变量的不纯性度量：
分类目标：Gini指标、Towing、order Towing
连续目标：最小平方残差、最小绝对残差
- ID3: 主要使用信息增益来衡量每个属性的划分效果，信息增益衡量的是划分后数据集的不确定性减少的程度。
树的建立：
如果目标变量是标称（分类）的，并且是具有两个以上的类别，则CART可能考虑将目标类别合并成两个超类别（双化）；
如果目标变量是连续的，则CART算法找出一组基于树的回归方程来预测目标变量。
- ID3：ID3主要用于分类问题，适用于离散的目标变量（例如，分类标签）。
树的生成方式
- ID3：ID3通过选择信息增益最大的属性来进行树的划分，递归地生成树直到满足停止条件（如树的深度或节点纯度）。
- CART：CART通过不断选择最能减少不纯度的属性和切分点来划分数据，使用二叉划分并递归生成树，直到满足停止条件（如节点的样本数或不纯度阈值）。
减枝
预剪枝对于何时停止决策树的生长有以下几种方法：
（1）当树到达一定深度的时候，停止树的生长；
（2）当到达当前结点的样本数量小于某个阈值的时候，停止树的增长；
（3）计算每次分裂对测试集的准确度提升，当小于某个阈值时，不再继续扩展。
后剪枝：在已生成的过拟合决策树上进行剪枝，得到简化版的剪枝决策树。
核心思想： 先让算法生成一棵完全生长的决策树，然后从最底层向上计算是否剪枝。剪枝过程是将子树删除，用一个叶子结点代替。如果剪枝过后准确率有所提升，则进行剪枝，否则保留。
比较：
时间开销： 预剪枝：训练时间开销降低，测试时间开销降低 后剪枝：训练时间开销增加，测试时间开销降低
过/欠拟合风险： 预剪枝：过拟合风险降低，欠拟合风险增加（虽然在当前的划分会导致测试集准确率降低，但在之后的划分中，准确率可能会有显著提升） 后剪枝：过拟合风险降低，欠拟合风险基本不变
泛化性能 后剪枝通常优于预剪枝
第六章 线性模型
损失函数
使用梯度下降时，要注意特征归一化。
特征归一化的好处： 1）提升模型的收敛速度。 2）提升模型精度。
这在涉及一些距离计算的算法时效果显著。
防止过拟合
线性回归模型评估指标
多项式回归
多项式回归本质还是线性回归的思路。关键在于为原来的数据集增加新的特征，新的特征是对原有特征进行多项式组合。采用这种方式，可以解决一些非线性问题。
逻辑回归
Logistic函数的优点：
1）输出范围有限
2）连续性和光滑性：优化过程中（如梯度下降）表现稳定，不会出现跳跃或不稳定的情况。
3）严格单调递增：有助于模型的稳定性和可解释性。
4）易于求导：计算梯度变得非常简单高效，有助于加快模型的训练速度。
5）对称性：有助于模型的泛化能力。
6）数学性质丰富
多类分类器
用两类分类器实现多类分类器的策略:
一对一(One vs. One, OvO)
把多类问题拆分成多个二分类问题，每次只比较两类。
例如，有3个类别A、B、C，就会创建3个分类器：
- A vs. B
- A vs. C
- B vs. C
怎么做？
每个分类器只需要学会区分两类。当要预测新样本时，所有分类器都会投票，得票最多的类别被选为最终结果。
一对一拆分： 拆分阶段 N个类别样本两两配对，形成N(N-1)/2个二分类任务 学习各个二分类任务分类器 测试阶段 新样本提交给所有分类器预测， N(N-1)/2个分类结果 投票产生最终分类结果，得票最多的类别为最终类别
优点：每个分类器只需要在包含两个类别的部分数据上训练，训练速度可能相对较快（尤其是在类别数较多且训练集较大时）。
缺点：需要构建的分类器数量较多，可能导致存储和计算资源的消耗较大。
一对其余(One vs. Rest, OvR)
把多类问题拆成多个“某一类 vs. 其他类”的二分类问题。
例如，有3个类别A、B、C，就会创建3个分类器：
- A vs. (B + C)
- B vs. (A + C)
- C vs. (A + B)
每个分类器专注于判断“某一类是否正确”。预测新样本时，每个分类器输出一个分数，分数最高的类别为最终结果。
某一类样本为正例，其余类样本作为反例，形成N个二分类任务 学习各个二分类任务分类器
优点：需要构建的分类器数量较少，存储和计算资源的消耗相对较小。
缺点：每个分类器都需要在整个数据集（或大部分数据集）上进行训练，可能导致训练速度较慢。此外，由于是一个类别对多个类别（1:N的关系），在训练时可能会更偏向多类别的一方。
多对多(Many vs. Many, MvM)
将多类问题拆成多个包含多类的子问题，每个分类器区分一组类别
。例如，有4个类别A、B、C、D，可以这样分：
- 分类器1: A+B vs. C+D
- 分类器2: A+C vs. B+D
- 分类器3: A+D vs. B+C
怎么做？
每个分类器预测属于哪一组，最终通过投票或其他方法整合结果，决定样本的类别。
优点：纠错能力强，即使某个分类器预测错误，也可能通过比较编码距离来得到正确的分类结果。
缺点：需要设计的分类器数量较多，且编码和解码过程可能相对复杂。
第八章 提升方法
集成学习(ensemble learning)，并不是一个单独的机器学习算法，而是通过构建并结合多个机器学习器(基学习器，base learner)来完成学习任务，以提高整体预测的准确性、稳定性和鲁棒性。 对于训练集数据，通过训练若干个个体弱学习器，通过一定的结合策略（如投票、平均等），就可以最终形成一个强学习器，以达到博采众长的目的。
通常生成一个完整的集成学习算法的步骤可以大致分成两步：
构建基学习器：生成一系列基学习器，这个过程可以是并行的，也可以是顺序的。
组合基学习器：将基学习器以某种策略组合起来。常见的组合方法有多数投票法、加权平均法、学习组合器等。
同质基学习器：使用同样的基学习算法生成的基学习器。
异质基学习器：使用不同的基学习算法生成的基学习器。
要想获得较好的集成性能，基分类器需要满足两个基本条件：
（1）基分类器要有一定的性能，至少不差于随机猜测的性能，即基分类器准确率不低于50%。 （2）基学习器要具有多样性，即基学习器间要有差异性。
集成学习算法主要有三大类：
Bagging模型、Boosting模型、Stacking模型。
Bagging模型
Bagging：训练多个分类器取平均，个体学习器之间不存在强依赖关系，一系列个体学习器可以并行生成。代表算法：随机森林(Random Forest)。
自助采样 (Bootstrap)
如果训练集规模足够大，平均分成t份即可。如果训练集规模不大，怎么办？
自助采样(Boot strap)有放回地随机抽取k个新的自助样本集。
具体做法是：
- 从原始数据中有放回地随机抽取样本，组成一个新的训练集。
- 因为是有放回，所以一个样本可以被多次抽取，也可能完全没被抽到。
- 剩下没被抽到的样本可以用作测试集。
举例说明
假设你有 5 条数据，分别是：A, B, C, D, E。
直接分组（训练集规模足够大时）
可以直接分成 2 组：
- 训练集：
A, B, C - 测试集：
D, E
自助采样（训练集规模不够大时）
有放回随机抽取 5 次：
- 第 1 次抽到
A - 第 2 次抽到
C - 第 3 次抽到
C - 第 4 次抽到
E - 第 5 次抽到
B
新的训练集是：A, C, C, E, B
剩下的没被抽到的样本 D 可以作为测试集。
代表算法：随机森林(Random Forest)
随机森林有两种方法保证所有树的不同原因：
1.数据集不一样，随机选择用于构造树的数据点（自助取样法），新样本集与原始数据集数量相同；
2.随机选择一个特征子集，在树的每个节点处，随机选择特征的一个子集，每个节点中特征子集的选择是相互独立的。
关键因素：每棵树选择特征的数量m 减小特征数量m，树的相关性越小，基分类器差异性越大，但分类能力越低。 增大特征数量m，树的相关性越大，基分类器差异性越小，但分类能力越强。
随机森林构造过程如下：
（1）原始训练集为N，应用自助取样法(bootstrap)有放回地随机抽取k个新的自助样本集(新样本集与原始数据集数量相同)，并由此构建k棵决策树，每次未被抽到的样本组成袋外数据；
（2）设有M个特征，则在每一棵树的每个节点处随机抽取m个变量(m < M)，然后在m个特征中选择一个最具有分类能力的特征值，构建决策树；
（3）每棵树都会完整成长而不会剪枝；
（4）将生成的多棵分类树组成随机森林，用随机森林分类器对新的数据进行判别与分类，分类结果按树分类器的投票多少而定。
优点： 两个随机性的引入，使得随机森林不容易陷入过拟合； 两个随机性的引入，使得随机森林具有很好的抗噪声能力； 对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化且能够有效地运行在大数据集上； 能够处理具有高维特征的输入样本，而且不需要降维； 对于缺失值问题也能够获得很好的结果。
缺点： 对小量数据集和低维数据集的分类效果可能不佳； 训练时间较长； 结果不够直观； 对分类不平衡的数据集表现可能不佳； 可能受到取值划分较多的属性的影响。
Boosting模型
Boosting：通过分步迭代的方式来构建模型。先前基学习器做错的样本在后续会被赋予更大的权值，然后基于调整后的样本分布来训练下一个基学习器，一直反复进行，直到达到指定值。个体学习器之间存在强依赖关系，必须使用串行的方式去学习。代表算法：AdaBoost、GBDT、XGBoost。
简单来说：提升方法是一个迭代的过程。通过对上一轮错分的数据增加权重，使错分的数据在下一轮迭代中起到更大的作用。
AdaBoost
该算法的自适应性主要表现在自动提升被错误预测样本的权重，自动减少被正确预测样本的权重，使得弱学习器训练过程能够根据模型预测性能自动进行调整。
两个问题如何解决：
- 每一轮如何改变训练数据的权值或概率分布？
提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类样本的权值。
- 如何将弱分类器组合成一个强分类器？
加权多数表决，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。
Stacking模型
Stacking：分阶段聚合多个弱学习器。先用n个基分类器（Base-learner）进行学习和拟合，然后将n个基分类器预测得到的结果作为下一层分类器的输入,下一层分类器得到的结果作为最终的预测结果。
第十四章 聚类方法
无监督学习是从无标注的数据中学习数据的统计规律或者内在结构的机器学习，主要包括聚类、降维、概率估计。
无监督学习可以用于数据分析或者监督学习的预处理。
无监督学习的基本想法是对给定数据（矩阵数据）进行某种“压缩”，从而找到数据的潜在结构。假定损失最小的压缩得到的结果就是最本质的结构。
聚类
聚类(clustering)是将样本集合中相似的样本（实例）分配到相同的类，不相似的样本分配到不同的类。
如果一个样本只能属于一个类或类的交集为空集，则称为硬聚类(hard clustering)
如果一个样本可以属于多个类或类的交集不为空集，则称为软聚类(soft clustering)
降维
从高维到低维的降维中，要保证样本中的信息损失最小。
概率估计
概率模型估计：假设训练数据由一个概率模型生成，由训练数据学习概率模型的结构和参数。 概率模型包括混合模型、概率图模型等。
在“无监督学习”任务中研究最多、应用最广。
目标：根据给定样本，依据它们特征的相似度或距离，将其归并到若干个通常不相交的“类”或“簇”。
样本之间的相似度或距离起着重要作用，直接影响聚类的结果。因此相似度或距离的选择是聚类的根本问题。
性能度量
外部指标：聚类结果与某个“参考模型”进行比较，如Jaccard系数，FM指数等
内部指标：直接考察聚类结果而不用任何参考模型，如DB指标等。
基本思想：簇内相似度高，且簇间相似度低
层次聚类
层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。
层次聚类又有聚合或自下而上聚类、分裂或自上而下聚类两种方法。
- 聚合聚类：开始将每个样本各自分到一个类，之后将相距最近的两类合并，建立一个新的类，重复此操作直到满足停止条件，得到层次化的类别。
- 分裂聚类：开始将所有样本分到一个类，之后将已有类中相距最远的样本分到两个新的类，重复此操作直到满足停止条件，得到层次化的类别。
层次聚类需要预先确定三个要素： (1) 距离或相似度 (2) 合并规则 (3) 停止条件
K均值聚类
k均值聚类是基于样本集合划分的聚类算法。 k均值聚类将样本集合划分为k个子集，构成k个类，将n个样本分到k个类中，每个样本到其所属类的中心的距离最小。 这是一个组合优化问题，n个样本分到k类。事实上，k均值聚类的最优解求解问题是NP难问题，因此实际上采用迭代的方法求解。
算法特性：
基于划分的聚类方法；(DBSCAN算法是典型的基于密度的聚类算法。可以发现任意形状的簇。)
类别数k事先指定；
以欧氏距离平方表示样本之间的距离，
以中心或样本的均值表示类别；
以样本和其所属类的中心之间的距离的总和为最优化的目标函数；
得到的类别是平坦的、非层次化的；
算法是迭代算法，不能保证得到全局最优；
收敛性；
选择不同的初始中心，会得到不同的聚类结果；
聚类结果的质量可以用类的平均直径来衡量。
优点 简单，快速，适合常规数据集
缺点 K值难确定 复杂度与样本呈线性关系 很难发现任意形状的簇
例子
对于x3=(1,0)
d(x3,m_1^0)= 1+4=5
d(x3,m_2^0)= 0+1=1,所以讲x3分到G_2^0
对于x4=(5,0)
d(x4,m_1^0)= 25+4=29
d(x4,m_2^0)= 0+25=25,所以讲x3分到G_2^0
对于x5=(5,2)
d(x5,m_1^0)= 25+0=25,所以讲x3分到G_1^0
d(x5,m_2^0)= 4+25=29,
由于得到的新的类没有改变，聚类停止。得到聚类结果G_1^2,G_2^2.
参考推荐资料：
【小萌五分钟】机器学习 | 模型评估: ROC曲线与AUC值_哔哩哔哩_bilibili
机器学习算法（二十五）：KD树详解及KD树最近邻算法_kdtree最近邻算法-CSDN博客