ITDS-分类
Classification，KNN
分类
将输入值与离散的输出值进行映射
$$
y = f(x) = argmax_c p(y=c|x)
$$
假设数据属于 $C$ 个类别，$x$ 是输入值，$y$ 是输出值，在所有可能的类别中，选择使条件概率 $p(y=c|x)$ 最大的类别作为预测结果。
K 邻近
K-Nearest Neighbors 是一种监督式学习算法，可用于 分类 和 回归。它的核心思想是 一个样本所属的类别，通常和它周围（最邻近）的样本类别相似。
$$
p(Y = c | x) = \frac{1}{K} \sum_{i \in N_K} I(y_i = c)
$$
- $I(y_i = c)$ 是指示函数，当 $y_i = c$ 时取 1，否则取 0。
- $N_K$ 是距离 $x$ 最近的 $K$ 个样本的集合。
- $p(Y = c | x)$ 是在给定输入 $x$ 的情况下，样本属于类别 $K$ 的概率。
- $K$ 是一个超参数，表示选择多少个邻近样本进行投票。
简而言之，它对 K 个最近邻居进行遍历，然后得到样本属于 c 类别的概率。
但其实它需要用欧几里得距离（也就是直线距离）计算所有点的距离，然后选取 K 个最近的点。
计算的时候可能出现平局的情况，也就是有两个或多个概率相同，这时候可以适当加减 K 以便得到一个更好的结果。
评估优化
回归模型是基于参数模型的方法。而 KNN 是非参数模型，它并非没有参数，而是其参数数量不固定，或不受预先设定的参数形式限制。
当数据量较小且数据分布较为规则时，参数模型可能表现较好。而当数据量较大、数据分布复杂且难以用简单的参数形式描述时，非参数模型可能更具优势。
最简单实现使用直线距离，设有 p 个特征，n 个样本，则时间与空间复杂度都是 $O(n \cdot p)$。
KD 树
我们可以使用 K-Dimensional Tree（K-D 树）来加速 KNN 的计算。K-D 树是一种空间划分数据结构，可以在 $O(n \log n)$ 的时间内构建，并在 $O(\log n)$ 的时间内查询最近邻，适合低维数据。
- 从第 1 维特征开始，把数据按中位数分成两半
- 形成树的根节点，左子树是小于中位数的，右子树是大于中位数的
- 递归处理左右子树，但换用下一维特征（循环使用维度）
- 最终形成一颗平衡的二叉树
Ball Tree
我们还可以使用 Ball Tree 来加速 KNN 的计算。其是一种基于球体划分的树形数据结构，适合高维数据。
- 每个节点是一个球，用质心和半径来表示一个数据子集的边界
- 递归划分数据，使每个球体内部的数据尽量相似
- 构成树形结构，每个叶子节点包含少量数据点
选择 K
$$
Err = \frac{1}{n} \sum_{i=1}^n I(y_i \neq \hat{y}_i)
$$
错误率越低，K 越好，我们可以绘制错误率与 1/K 的关系图，选择错误率最低的 K。
标准化
我们一定要对数据进行标准化处理，因为 KNN 是基于距离的算法，特征值的大小会影响距离计算。未标准化时距离计算受大尺度特征主导。
其他
最优贝叶斯分类器是理论上错误率最低的分类器，它知道所有类别的先验概率和在每类下，数据出现的条件概率分布。但是它基本上不能实现，因为我们无法知道所有的先验概率和条件概率分布（无限数据和上帝视角）。
我们还有 Weighted KNN，离目标点越近的邻居，对结果的影响越大。标准 KNN 所有邻居投票权重相同，而 Weighted KNN 则是根据距离的倒数来加权投票。比标准 KNN 效果更好（特别是在类边界模糊时）。
Logistic Regression 逻辑回归实际上是一个用于二分类的分类算法，不是回归算法。使用一个 Sigmoid 函数，将线性回归的输出映射为 0 到 1 之间的概率值，然后根据概率进行分类。
它使用一个线性函数 $h(x) = w^T x + b$，然后通过 Sigmoid 函数将其映射到 0 到 1 之间的概率值：
$$
h(x) = \frac{1}{1 + e^{-h(x)}}
$$
如果 $h(x) \geq 0.5$，则预测为正类；否则预测为负类。
其中 $w$ 是权重向量，$b$ 是偏置项。我们可以使用梯度下降法来优化 $w$ 和 $b$，使得损失函数最小化。