Korean, Edit

第 6 章. 分类算法

推荐阅读：【算法】(https://jb243.github.io/pages/1278)

1. 概述

2.类型1. 线性分类器

3.类型2. K-最近邻算法

4.类型 3. 决策树

5.类型 4. 基本分类器

6。类型5. 域适应分类

7. 类型 6.** 基于深度学习的分类

8. 其他算法

a. Github (R, Python)

b. 校准分类模型

1.概述

⑴ 定义

① y ~ X （其中 | { y } | ＜ ∞ ）

② 属于有监督算法范畴

⑵【标定分类模型】(https://jb243.github.io/pages/1769)

2.类型 1. 线性分类器

⑴ 概述

①利用非线性回归分析

② 缺点1. 线性分类器每个类只能学习一个模板

③ 缺点2. 线性分类器只能实现决策边界中的线性决策边界

④（参考）超平面：表示超越 3D 的多维曲面，用于多元回归

⑵ 1-1. 【SVM（支持向量机）】(https://jb243.github.io/pages/1776)

① 概述

○ 定义： 一种找到能够将 N 维空间分成两个 (N-1) 维半空间的超平面的分类方法。

○ 一种传统的二元分类技术，通过在高维（甚至无限维）空间中最大化间隔来设置最佳超平面（称为最大间隔超平面 (MMH)），从而将数据点分为两类。

图 1. SVM 和超平面

○ 可以有多个支持向量：设置多个超平面可以将点分为多个集合

○ 线性不可分的分类问题可以通过从原始空间映射到高维空间来解决

○ 优点

○ 经常使用且有完善研究的方法。

○ 与其他模型相比，抗过拟合能力强。

○ 精度高。

○ 不论维度如何均可推广。

○ 不受噪音影响。

○ 缺点

○ 监督学习：需要标记数据集（即提供的训练/测试集）。

○ 计算密集型：比其他模型慢。

○ 内核选择并不简单，因此需要进行实验。

○ 对数据缩放敏感。

② 公式

图 2. SVM 公式

○ 最终公式的意义：优化算法很容易应用，并且可以通过应用核扩展到不可线性分离的分类问题。

○ 通过引入松弛变量 xi_i = 1 - y_i (wx_i + b)，允许一些违反约束的数据点。

③ SVM中使用的核» ○ Linear Kernel：基本类型的核，一维，比其他函数更快

○ 多项式核：线性核的广义公式，在有效性和准确性方面效率较低

○ Gaussian Kernel：一般使用的kernel，在没有数据先验知识的情况下使用

○ 高斯 RBF 核：最常用的核，通常用于非线性数据。在下面的等式中，向量 ℓ 表示一个地标（例如，数据点的中心）。

○ Sigmoid Kernel：人工神经网络中首选的内核

④ R中的实现

受保护_0

⑶ 1-2. nu-SVM

⑷ 1-3. 【概率回归模型】(https://jb243.github.io/pages/1633)：LPM、probit、logit等。

①R代码

受保护_1

3。类型 2. K-最近邻算法 (K-NN)

⑴ 概述

①一种使用K个最近的训练数据点来标记给定测试数据点的方法

② 示例：YouTube推荐系统

③ 超过 5 维时效果不佳

⑵ 步骤1. 数据加载和架构设计

受保护_2

⑶ 步骤2. NN类设计

受保护_3

① 训练阶段仅仅是数据存储阶段

② 因子1. 设计距离函数

○ 距离函数(距离函数，度量)：定义距离

○ 1-1. L1 距离

○ 1-2. L2 距离：使用毕达哥拉斯定理的欧几里得距离（标准）

○ 1-3. p-范数

○ 1-4. 点积

○ 1-5. KL 距离（Kullback-Leibler 散度）(Kullback-Leibler 散度)

○ 1-6. 其他距离函数

○ L1 和 L2 距离的结果相似：L1 38.6%，L2 35.4%

③ 因子 2. 1-NN 与 k-NN

○ 随着 k 的增加，每个区域的边缘变得更加平滑

○ 如果 k 太小，则鲁棒性不强，并且在标记时可能会对异常值或噪声做出响应

○ 随着 k 的增加出现模糊区域

⑷ 步骤 3. 超参数调整：尝试各种 k 值并选择产生最佳结果的值

受保护_4

⑸ 步骤4. 改进

① 缺点

○ 在像素级别使用 KNN 可能不会产生真正的相似性，从而导致性能不佳

○ 测试时间很慢

○ 维数诅咒：随着维数的增加，保持样例间距离相同所需的数据量呈几何级数增加

○ 示例中的示例过于稀疏可能会导致分类结果马虎

② 改进

○ 数据标准化：将数据标准化为平均值为 0、标准差为 1

○ 降维：PCA、NCA、随机投影等技术。

○ 交叉验证：计算量大，常用的方法有3倍、5倍、10倍交叉验证

○ 近似最近邻：降低精度但提高速度（例如 FLANN）

③ 尽管有这些改进，KNN 在实践中很少使用

⑹ 2-1. 相互最近邻算法

⑺ K-NN 与 K-Means 聚类的比较

表 1. K-NN 和 K-Means 聚类的比较

4。类型 3. 决策树

⑴ 概述

① 针对给定输入值预测输出值的模型，包括单树和回归树模型

② 利用分类函数绘制带有决策规则的决策树进行分析的技术

图3. 由二叉树组成的决策树

③ 子节点的纯度相比父节点的纯度有所提高

④ 计算结果直接显示在决策树中

⑤ 缺点：由于连续变量被视为不连续值，因此在分离边界点附近预测误差很大

⑵ 3-1. 简单决策树

① 概述

○ 优点 1. 给定数据的良好表示

○ 优点2. 可解释且快速

○ 优点3. 轻松处理以下数据：分类数据、混合数据、缺失数据、多类

○ 缺点 1. 存在过度拟合的可能性，这意味着它容易受到异常值的影响。

○ 缺点2. 树变得太深。

○ 缺点3. 难以处理连续数值数据

○ 缺点4. 优化难点

○ 解决方案：树木修剪

② 术语

○ 根节点

○ 内部节点（Node）：形成属性的条件语句

○ 分支：根据属性值从内部节点分裂出来

○ 叶子节点（终端节点、决策节点）：输出（类分配）

③ 学习决策树

○ 条件1. 不能太大或太小

○ 条件2. 奥卡姆剃刀理论：简单就是最好

○ 条件 3. 复杂性取决于深度

○ 学习最小最简单的决策树是一个 NP 完全问题 (Hyafil & Rivest (1976))

○ 可以使用启发式方法贪婪地学习决策树

受保护_5

○ 步骤 1. 对所有分组进行评分

○ 步骤2. 贪心寻找信息增益最大的条件

○ 步骤 3. 根据该条件划分数据集，并在每个子树中递归执行 步骤 1 和 步骤 2

○ 步骤 4. 停止标准

④ R代码

受保护_6

⑤ 应用1：修剪

⑥ 应用2：信息增益比

⑶ 3-2. 装袋（Bootstrap Aggregation）

①定义：通过投票放回抽样确定不同数据集的分类结果

图 4. 装袋示意图

② Bootstrap：启动后自动进行的一系列过程，不限于决策树

③ 优点1. 减少树等不稳定过程的方差，提高可预测性

④ 优点2. 平滑决策树的边界

⑷ 3-3. 随机森林

①定义：利用每个子数据集中随机选择的m个特征进行bagging» ○ 示例：学习时，在各个特征中只随机选择一些特征，如城市、人口、平均收入、新生儿数、新婚夫妇数等

② 特征1. 去相关：仅使用部分特征来增加每个子数据集的个性化

③ 特征2. 每个子数据集中未使用的数据集可用于验证样本外错误

④ 性能：随机森林＞装袋＞决策树

○ 准确度：与 Adaboost 相当或更高

○ 鲁棒性：对于异常值和噪声具有相对鲁棒性

○ 速度：比装袋、升压更快

○ 简单且易于并行化

○ 目前分类算法研究中表现最好的算法

⑤ R 代码

受保护_7

⑸ 3-4. C4.5 和 C5.0

① 澳大利亚研究员 J. Ross Quinlan 开发

② 最初版本于1986年开发为ID 3（Iterative Dichotomizer 3）

③ 使用剪枝时使用训练数据

④ 使用熵指数作为离散因变量的杂质度量

⑹ 3-5. 柴德

① 在决策树算法中使用卡方统计量并采用多路分割

⑺ 3-6. CART（分类和回归树）

① 通过对每个自变量重复分叉形成二叉树来进行分类

⑻ 3-7. AdaBoost

⑼ 3-8. 任务

⑽ 3-9. K-D树

①定义：用于组织k维空间中的点的空间划分数据结构。

② K-D 树的结构：通过沿 x 轴和 y 轴交替定位中点，对每个分区进行空间迭代划分。

图 5. K-D 树的结构

③ 使用K-D树计算最短距离：

○ 第一步：从根节点开始查找。

○ 步骤2： 根据每个分区的分裂轴，选择给定坐标（coord）可能所属的子节点，并在树中向下移动。

○ 步骤3：重复步骤2，直到到达最有可能包含给定坐标的叶节点。

○ 步骤4： 计算叶节点中的点与给定坐标之间的欧氏距离。

○ 步骤5： 根据叶子节点中找到的最短距离，评估父节点和兄弟节点是否可以包含更近的邻居。如果兄弟节点值得探索，请重复该节点的距离计算。

○ 第6步： 利用K-D Tree的空间分区特性来跳过不必要的节点（剪枝）。

④Python代码

受保护_8

5。类型 4. 基础分类器

⑴ 朴素贝叶斯分类器

① 概述

○ 一种将类别的先验信息与从数据中提取的信息相结合并使用贝叶斯定理对给定数据点是否属于特定类别进行分类的算法。

○ 假设数据中的特征之间条件独立。

○ 快速处理大规模数据。

○ 可用作文本分类任务的解决方案，其中基于贝叶斯估计将文档判断为属于多个类别之一（例如垃圾邮件、经济、体育、情感分析、推荐系统等）。

② 形式化

○ 前提：有 K 个类 C₁、C₂、···、C_K。

○ 目的：给定一个由多个特征组成的新样本 x = (x₁, ···, x_N)，判断它属于哪一类。

○ 形式化：类似于MLE（最大似然估计）。

③ 局限性

○ 违反条件独立性：如果特征之间存在显着相关性（例如年龄和心脏病史），则相关变量可能会被乘以多次，从而导致对其影响的高估。

○ 无法排除不相关特征的影响。

○ 解决方案：通过使用PCR或mRMR等方法丢弃不必要的变量并仅保留必要的变量，可以减轻这些限制。

⑵ 贝叶斯网络

6。类型 5. 领域适应分类

⑴ 概述

①定义：从一个领域获得普遍知识并将其应用到另一个领域。

② 一域：指源域、切向域等。数据集规模大。

③ 另一个领域：称为目标领域、特定领域等。数据集规模较小。

④ 与概括的差异

○ 领域适配分类：源和目标之间在格式、数据结构等方面的差异。

○ 泛化：源和目标之间的格式、数据结构等相同。

⑵ 种类

① UDA（无监督域适应）：当目标域中没有标签时。

图 6. UDA 示意图

○ 换句话说，将从源域获得的特征直接应用到目标域的结构。

② SSL（Supervised Domain Adaptation）：当目标域中有标签时。

③ SSDA（半监督域适应）：当目标域仅具有某些情况的标签时。

图7. SSDA图

○ 过程1：增强

○ 过程2：随机logit插值

○ 流程 3： 分布对齐

○ 过程4：相对置信度阈值

○ 过程5： 损失函数

○ 成为最先进（SOTA）的原因：由于权衡，可以在链接的“动机”部分中确认。

⑶ 目标函数

① 旨在减少域之间的差异。

② 差异的类型

○ MMD（最大平均差异）

○ DANN（领域对抗神经网络）

○ MCD（最大分类器差异）

⑷ 【应用】(https://towardsdatascience.com/understanding-domain-adaptation-5baa723ac71f)

① 发散域适应

② 对抗域适应

○ 定义：域鉴别器和特征提取器相互竞争以最小化源域和目标域之间的差异的方法。

○ 生成对抗网络（GAN）

○ 定义：两个人工智能系统在相互竞争的同时学习（游戏学习）。

○ 生成模型：利用基于现有数据的各种特征学到的知识来生成新数据。

○ 判别模型：评估生成的新数据与现有数据的相似程度。

○ 通过生成模型和判别模型之间交换想法，自动创建接近现实的结果。

③ 重构域适配

7.类型 6. 基于深度学习的分类

⑴ 深度学习（第1部分、第2部分、第3部分)

⑵ 6-1. 1D CNN

## 8.其他算法

⑴费斯

① Meta于2023年开发的基于相似度的搜索和密集向量聚类算法。

② 快速搜索算法：能够获得最近邻和第k最近邻。

③ 允许一次搜索多个向量（批处理）。

④ 精度和速度之间需要权衡。

⑤ 不是最小化欧氏距离，而是通过最大化最大内积来计算。

⑥ 返回给定半径内包含的所有元素。

输入：2021.12.12 11:37