其实没什么必要单独讲，思想不算很难，看看能不能合并到哪篇里吧

KNN算法概述

参考
Python—KNN分类算法
 K-近邻算法： k-nearest neighbor classification (kNN) 详细介绍
 一文掌握KNN

KNN（K Nearest Neighbors）算法是一种基于距离的分类算法，原理是通过比较待预测点与训练集中每个点的距离，选取最近的个邻居点来判断该点所属的类别。

通过遍历训练集中的每一个点，然后计算与预测点的距离，最后选取距离最小的k个点，判断哪种类型占比最大就把这个预测点归于那个类别(计算量其实挺大的)。

距离度量

欧氏距离（Euclidean Distance）
直线距离

曼哈顿距离（Manhattan Distance）
沿着坐标轴方向的总距离

切比雪夫距离（Chebyshev Distance）
任一维度上最大的差异

余弦相似度（Cosine Similarity）
方向上的相似度，值越接近1表示越相似

其中，是向量的点积，和是它们的模（欧几里得范数）。

KD树（K-dimensional Tree）

怎么确定还没加上，虽然划分可以加速但是在交界的影响会怎么样还是值得考虑的……有兴趣再做吧做机器学习也不用深入那么多，何况这个现在很少用了

KD树是一种用于加速 KNN 搜索的空间划分方法，通过二叉树的结构递归地划分数据点，减少不必要的距离计算，从而提高查询效率。

选择维度：在构建树时，轮流选择每个维度来进行切分。通常选择当前维度的中位数来划分数据。例如，第一层选择维，第二层选择维，依此类推。
选择中位数：每次选择当前维度的中位数作为切分点，保证树的平衡性，使得每个子树大小大致相等。
递归划分：通过递归构建子树，直到每个节点的区域足够小。

通过构建KD树，KNN查询时可以快速定位到可能包含最近邻的子树，减少了计算距离的次数，提高查询速度。

KNN是一种非参的、惰性的算法模型。什么是非参，什么是惰性呢？

非参的意思并不是说这个算法不需要参数，而是意味着这个模型不会对数据做出任何的假设，与之相对的是线性回归（我们总会假设线性回归是一条直线）。也就是说 KNN 建立的模型结构是根据数据来决定的，这也比较符合现实的情况，毕竟在现实中的情况往往与理论上的假设是不相符的。

惰性又是什么意思呢？想想看，同样是分类算法，逻辑回归需要先对数据进行大量训练（tranning），最后才会得到一个算法模型。而 KNN 算法却不需要，它没有明确的训练数据的过程，或者说这个过程很快。
此类学习技术在训练阶段仅仅是把样本保存起来，训练时间开销为零，待收到测试样本后再进行处理

KNN模型优化

由于KNN是基于距离计算的，当数据的量纲不统一时，会导致某些维度对距离的影响过大，从而影响模型的效果。因此，在使用KNN时，需要对数据进行归一化处理，使得所有特征的尺度一致。

权重加权

在KNN算法中，常见的优化方法是对每个最近邻点的影响进行加权，权重通常设置为距离的倒数。这样距离较近的点对分类结果的影响更大，远离的点影响较小。

注意，关于模型的优化方法只是在理论上优化会提升模型判别效力，但实际应用过程中最终能否发挥作用，本质上取决于优化方法和实际数据情况的契合程度，如果数据本身存在大量异常值点，则采用距离远近作为惩罚因子则会有较好的效果，反之则不然。

选择K值

K值的选择对KNN算法的性能有重要影响。较小的K值会使模型过拟合，较大的K值则可能使模型欠拟合。可以通过交叉验证方法来选择最优的K值，即将数据集分为训练集和验证集，测试不同的K值，选择性能最佳的K值(可以看图像粗判)。

决策树

参考
决策树原理详解
 机器学习算法系列（十七）-决策树学习算法

决策树是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系，以树形数据结构来展示决策规则和分类结果。树中每个节点表示某个对象，而每个分叉路径则代表某个可能的属性值，而每个叶节点则对应从根节点到该叶节点所经历的路径所表示的对象的值。

基本思想是通过一系列条件判断将数据从根节点逐步划分到叶子节点。每个节点代表一个特征或属性，每个分支代表一个特征的取值。决策树通过不断选择特征来“分裂”数据集，使得每个子集的纯度（或不纯度）逐渐提高。

选择当前条件下的最优属性划分

信息增益（Information Gain）

信息增益是决策树算法（如 ID3）中的关键指标，用于衡量一个特征对样本集合的分类能力。其计算公式如下：

其中：

是特征的信息增益。
是当前的数据集，是某个特征，是特征的所有可能取值。
是在特征取值为时的数据子集。
是数据集的信息熵。

随机变量的不确定性（也就是混乱程度）。

增益比（Gain Ratio）

信息增益虽然在理论上可以找到最优的划分属性，但在某些情况下会存在问题。信息增益比较偏好可取值较多的属性，比如我们的样本有一个属性叫序号，每一个样本都具有一个单独的序号，因此使用序号划分后，每个子结点只有一个样本，熵为0。这样的话信息增益最大，算法就会以此属性作为最优划分属性。这显然与我们的意愿不同。因此引申出了增益比的思想。
可以这么说，增益比就是为了矫正信息增益偏好的问题。为了使算法不偏向可取值较多的属性。

决策树的增益比（Gain Ratio）是一种用于评估特征选择质量的度量，主要用于改进经典的信息增益（Information Gain）方法。信息增益在构建决策树时用于选择最优的划分特征，但它有一个缺点：偏向选择取值数目较多的特征。增益比通过引入一个归一化步骤来解决这个问题，使得特征选择更加公平和合理。

信息增益是决策树算法（如 ID3）中的关键指标，用于衡量一个特征对样本集合的分类能力。

增益比通过对信息增益进行归一化，来避免偏向取值较多的特征。它的计算方式是：

其中：

是特征的信息增益。
是特征的分割信息，衡量特征对数据集的划分复杂度。它的计算公式为：

基尼指数（Gini Index）

基尼指数衡量一个数据集的纯度（或不纯度）。如果数据集的基尼指数越小，意味着数据集中的样本越趋向于属于同一类别。基尼指数的值范围是，其中：

0 表示完全纯净的节点（即所有样本属于同一类别）。
1 表示最大的不纯度（即每个样本的类别完全随机）。

基尼指数的计算公式如下：

其中：

是数据集的基尼指数。
是数据集中类别的数量。
是类别在数据集中的概率（即类别样本数占数据集总样本数的比例）。

基尼指数用于决策树构建

在决策树的构建过程中，基尼指数常用于评估每个特征的划分效果。具体步骤如下：

对于每个特征的每个取值，我们计算该特征划分后的子集的基尼指数。
然后，我们计算加权平均基尼指数（加权平均是基于每个子集的样本数），选择基尼指数最小的特征作为分裂点。

这种方法用于 CART（Classification and Regression Trees） 算法中的分类任务。

决策树回归（Decision Tree Regression）

决策树回归是基于决策树的一种回归方法，与分类决策树的原理类似，区别在于目标变量是连续的而不是离散的类别。决策树回归通过递归地分割数据集，并在每个叶子节点预测目标值的平均值，最终实现对连续目标变量的预测。

决策树回归的基本原理

递归划分：决策树通过在特征空间中选择最佳分裂点，将数据集分割成若干个子集。
叶子节点输出：每个叶子节点的输出值是该区域内样本目标值的均值。
目标：预测目标变量的连续值。

决策树回归的损失函数

决策树回归通常使用 均方误差（MSE） 来评估每个分裂点的好坏。MSE 的公式如下：

其中：

是第个样本的真实值。
是第个样本的预测值，通常是该节点所有样本的平均值。

决策树回归算法步骤

选择最佳分裂点：选择一个特征和该特征的某个取值作为分裂点，划分数据集，使得每个子集内目标变量的均值最接近该子集的所有样本目标值。
递归划分：对每个子集继续递归地选择最佳分裂点，直到满足某个停止条件（如树的最大深度、叶子节点样本数目最小等）。
预测：对于一个新的样本，决策树会根据它的特征值找到它所在的叶子节点，并输出该节点的预测值。

优缺点

优点

非线性建模：决策树能够处理非线性关系，而不像线性回归只适用于线性数据。
无需特征缩放：决策树不依赖于特征的缩放或归一化。
易于理解和解释：决策树的结构简单，可以清晰地展示特征与输出之间的关系。

缺点

过拟合：决策树容易过拟合，尤其是在数据中存在噪声时。
对噪声敏感：噪声可能导致树结构过于复杂，影响泛化能力。
局部最优：决策树每次分裂选择局部最优的特征，容易陷入局部最优，影响性能。