本文是我在复习人工智能与模式识别课程时根据老师课件、课本等资料，以及上课时记录的内容，整理出来的一份复习笔记。

内容安排完全参照我们选用的教材和课件，内容准确度不做保证，仅供参考。

由于备考时间紧张，一些我猜测考试不太会考的内容可能会有缺漏。

绪论

人工智能的定义

用人工的方法在机器上实现的智能。

像人一样思考、行动的系统；理性地思考、行动的系统。

• 图灵测试（1950）
• 中文房间测试

研究目标：

• 远期：揭示人类智能的根本机理。用智能机器模拟、延伸、扩展人类智能。
• 近期：研究如何使现有的计算机更聪明。

人工智能的发展历史

• 孕育期：1943-1955
  • 1943 Warren McCulloch、Walter Pitts 对人工神经元模型的研究，证明任何可计算的函数都可以通过神经网络计算，并且适当的网络可以学习。
  • 1951 普林斯顿大学 Marvin Minsky、Dean Edmonds 建造第一台神经网络计算机。
  • 1950 图灵的论文第一个清晰地描绘出 AI 的完整图像。
    • 图灵测试
    • 机器学习
    • 遗传算法
    • 增量学习
• 诞生：1956 达特茅斯大学研讨会 为研究领域命名
• 早期成功与期望：1952-1969
• 第一次低谷：1966-1973
• 基于知识的系统崛起：1969-1979
  • 基于知识的专家系统
  • 神经网络复兴 机器学习、深度学习
  • 进化计算提出
• 第二次低谷：1987-1993
  • 专家系统的缺点
    • 应用领域狭窄，缺乏常识性知识
    • 知识获取困难，推理方法单一
    • 无分布式功能
    • 难以解决规划计算问题
  • 过度期望
• 成为工业：1980——now
• 成为科学：1987——now

这段内容似乎还是有缺漏，但是我没精力再去完善了，就这么着吧，反正应该也不是重点。

人工智能的流派

行为主义

• AI起源于控制论
• 智能取决于感知和行为。取决于对外界复杂环境的适应而非推理。
• 行为是学习者对环境刺激做出的反应。
• 学习过程是渐进性试错过程。

符号主义

• AI 起源于数理逻辑
• 人类认知基于符号，认知过程是符号表示上的推理

联结主义

• AI 起源于仿生学，对人脑的模仿
• 人类认知基于神经元，认知过程是神经元的联结活动过程

人工智能的应用

• 机器学习：通过计算手段，利用经验改善系统性能。
  • 用 P 评估程序在任务类 T 上的性能，若利用经验 E 在 T 上获得了性能改善，则认为关于 P 和 T 对 E 进行了学习。
  • 监督学习：分类（输出离散）、回归（输出连续）
  • 无监督学习：聚类、生成、降维
  • 强化学习
• 模式识别：确定样本所属的模式类
• 数据挖掘
• 计算智能
• 专家系统
• 自动程序设计
• 机器人学

Agent

Agent 的定义

• 弱定义：具有自主性、社会性、反应性、能动性的计算机软件/系统。
• 强定义：弱定义 + 部分人类特性（知识、信念、意图、情感等）

与环境紧密相关，通过传感器感知环境，形成感知数据序列。将其映射到行为动作序列，通过执行器对环境产生影响。

Agent 的性质

一般性质

• 自主性：不受外界指令干预的情况下，根据目标和环境要求，主动、自发、有意图地采取动作，控制自身的内部状态。
• 主动性：不仅仅对外部环境应激反应，根据目标采取主动行动。
• 反应能力：有选择地感知外部环境，并做出反应
• 社会性：可以存在于多个 Agent 的环境中，与其他 Agent 通信、交换信息。

强性质

• 推理能力：根据当前知识和经验，以理性方式推理。尽力实现目标，分析其是否可实现。
• 移动性：可以以自引导的方式在网络中移动。
• 持续性：启动后可以在长时间维持运行，不随运算停止立即结束运行。
• 诚实性：不故意输出错误信息。
• 协作性：多 Agent 协同解决问题。

理性

对于所有可能的感知数据序列输入，根据当前知识和经验，选择使其性能度量最大化的动作序列。

• 性能度量
• 可用行动
• 感知数据序列
• 对环境的先验知识

任务环境描述

PEAS

• P：性能度量
• E：外部环境
• A：执行器
• S：传感器

性质

• 完全可观察/有效完全可观察/部分可观察
  • 完全可观察：Agent 可以观察到环境的所有状态
  • 有效完全可观察：Agent 可以观察到与决策相关的环境状态
  • 部分可观察：Agent 只能观察到环境的部分状态
• 单/多 Agent
• 确定性环境/随机环境：环境未来状态是否完全取决于当前状态与 Agent 动作
• 片段/连续环境：当前决策是否影响未来决策
• 静态/半动态/动态
  • 静态：环境状态不会改变
  • 半动态：环境状态不会改变，但是性能度量会改变
  • 动态：环境状态会改变
• 离散/连续
• 已知/未知：所有行动后果是否已知

Agent 的分类

暂时还没做 Mermaid 支持，先暂时把 Mermaid 源代码贴出来。等有时间再完善。

简单反射型

直接对感知到的信息匹配规则，执行对应的操作。

模型反射型

保持内部状态，根据当前状态和感知到的信息，执行对应的操作。

目标驱动型

根据目标，执行对应的操作。以达到目标为目的行动。

学习型

根据工作情况和环境、状态信息进行学习，改进自身性能。

确定性知识推理

知识、推理的定义

知识：信息及其关联。

按照适用范围分类：

• 常识性：通用通识，所有领域均需具备。
• 领域性：领域特定知识，仅对特定领域有帮助。

按照是否可判定分类：

• 确定性：可以判断其真假。
• 不确定性：具备不确定特性（不精确、模糊、不完备）。

按照层级分类：

• L0：陈述性知识，描述事物的概念、定义、属性、状态等。是什么？为什么？
• L1：程序性知识，包含问题求解过程的操作、演算、行为相关，如何使用 L0 知识的知识。怎么做？
• L2: 策略性知识：如何使用 L1 知识的知识。

推理：

• 结构角度：对已有判断进行分析与综合，得出新的判断。
• 过程角度：在给定信息和已有知识上的操作，得出结论。

确定性知识的表示方法

知识表示：对知识的描述，将知识编码为一组可被计算机接收，并方便使用的数据结构。

谓词逻辑表示法

• 断言：陈述句。
• 命题：可以判断真假的断言。不能同时为真/假，但是在不同条件下可以有不同判断。
• 论域：所讨论对象的全体。
  • 个体：论域中的元素
• 谓词：表示命题。形如 。其中 P 为谓词名， 为个体，即命题的主语。
• 连词：非/否定、析取/或、合取/与、条件/蕴含/如果-则、双条件/等价于/当且仅当。
• 量词：全称量词、存在量词。
• 辖域：量词的管辖范围。
• 约束变元：辖域内与量词中变元同名的变元。
• 自由变元：不受量词约束的变元。

优点：

• 自然：接近自然语言。
• 明确：有标准的知识解释方法
• 精确：真值只有真/假。
• 灵活：知识与推理分离。
• 模块化：知识间相对独立。

缺点：

• 表示能力弱：只能表示确定性知识。
• 管理困难：缺乏组织原则。
• 存在组合爆炸：没有明确推理方向。
• 系统效率低：推理演算与知识语义分离。

产生式表示法

事实：断言一个变量的值/断言多个变量间关系的陈述句。

用事实的 If-Then 规则表示知识。

P 为前提，Q 为结论。

优点：

• 自然性：符合直觉。
• 模块性：规则即为规则库中的基本组成单元，天然模块性。
• 适用性：对确定性/非确定性知识都可描述。

缺点：

• 效率低（需要匹配-规则消解-执行）
• 不利于表示结构性知识。

语义网络表示法

用实体及其语义关系表达知识的有向图。

• 节点：代表实体。事物、概念、情况、属性、状态、事件等。
• 边：代表语义关系。必须带有标识。

常见关系：

• 实例关系 ISA：A（个体） 是 B（类别）中的一个实例。
• 分类关系 AKO：A（类别） 是 B（类别）中的一个子类。
• 成员关系 A-Member-of：A（个体） 是 B（集合）中的一个成员。
• 属性关系：
  • Have：A（个体）具有 B（个体）。
  • Can：A（个体）可以 B（动作）。
• 包含关系（聚类关系） Part-of：A（个体） 是 B（个体）的一个部分。
• 时间关系：Before/After：A（事件）在 B（事件）之前或之后。
• 位置关系：Locate-on/in...：A（个体）在 B（个体）的位置上方/内部……
• 相似关系：Similar-to：A（个体）与 B（个体）相似。

确定性知识推理方法

产生式推理

• 知识库/规则库：存放推理规则
• 综合库/事实库：存放事实、推理中间结论、初始状态等。

推理机的能力：

• 选择匹配：按照一定策略从知识库中选择规则（规则前提）与事实库匹配。
• 冲突消解：对匹配成功的规则，按照一定策略从其中选择一个执行。
• 执行操作：根据规则，若后项为结论，则将其添加到事实库中。若后项为操作，则执行该操作。
• 终止推理：当事实库中包含推理目标时，推理结束。
• 路径解释：记录推理路径，包括选择的规则、执行的操作、添加的事实结论等。

推理方式：

• 正向推理：从事实库开始，根据规则推理出新的事实。
• 反向推理：从目标事实开始，根据规则寻找需要的前提事实。

自然演绎推理

从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论。

• 置换：形如 的有限集合，其中 为项， 为互不相同的变元。表示将 替换为 。同时，要求 ， 不能出现在另一个 中。
• 合一：寻找一个置换，使得两个谓词公式一致。

归结演绎推理

将永真性转化为对否定命题不可满足性的证明。

永真性：

• 若谓词公式 P 在个体域 D 上对任意解释均取得真值 T，则 P 在 D 上永真。若对于任意个体域 D，P 在 D 上永真，则 P 为永真命题。
• 对于谓词公式 P，若 P 在个体域 D 上至少存在一种解释使其真值为 T，则 P 在 D 上可满足。
• 对于谓词公式 P，若 P 在个体域 D 上对任意解释均取得真值为 F，则 P 在 D 上不可满足/永假。若对于任意个体域 D，P 在 D 上不可满足，则 P 为永假命题。

范式：谓词公式的标准形式。

• 前束范式：所有量词均非否定地出现在公式最前，且辖域为整个公式。
• Skolem 范式：所有存在量词均出现在全称量词之前的前束范式。

子句与子句集：

• 文字：原子谓词公式及其否定。
• 子句：文字的析取式。
• 空子句：不含任何文字的子句。永假。用 NIL 标识。
• 子句集：由若干子句/空子句组成的集合。

子句化简步骤：

1. 消去连接词。
2. 减少否定符号辖域，将所有否定符号移动到文字前。
3. 对变元标准化：使不同量词约束的变元不同。
4. 化为前束范式：将量词移动到公式最前。不能改变相对顺序。
5. 消去存在量词。
   • 若存在量词不在全称量词辖域内，则直接消去，用一个新的个体常量代替。
   • 若存在量词在全称量词辖域内，则用 Skolem 函数代替被约束的变元，并消去存在量词。
6. 化为 Skolem 标准型：应用分配律。
7. 消去全称量词。
8. 消去合取：将合取用子句集形式表现。
9. 更改变元名：使子句集中变元名不重复。

谓词公式 F 不可满足的充要条件为其标准子句集 S 不可满足。

永真性不满足充要条件性质。

子句集性质：

• 子句集中只要有一个子句不可满足，则整个子句集不可满足。
• 子句集中包含空子句，则整个子句集不可满足。

鲁滨逊归结原理：将待证结论的否定加入子句集，在子句集中进行归结，直至导出空子句或不能归结。若导出空子句，则待证结论的否定不可满足，即待证结论为真。否则，待证结论不可满足。

命题逻辑归结

• 若 P 为原子谓词公式，则 P 与其否定为互补文字。
• 设 C1、C2 为子句集中的两个子句，若 C1 中的文字 L1 与 C2 中的文字 L2 互补，则 C1 与 C2 可以消去 L1、L2, 将剩余部分析取，归结为 C3。

谓词逻辑归结

需要先用合一对子句集中谓词变元进行代换，才能进行归结。

搜索策略

搜索的定义

依靠经验，利用已有知识，根据问题实际情况，不断寻找可利用知识，构造代价最小的推理路线，使问题得以解决。

适用于：

• 不良结构/非结构问题
• 难以获得求解所需全部信息
• 没有现成算法的问题

搜索的分类

按照是否使用启发式信息：

• 盲目搜索
• 启发式搜索

按照问题表示方式：

• 状态空间搜索
• 与-或树搜索

状态空间搜索

状态：表示问题中每一步当前状况的数据结构。

操作：将问题从一种状态变换为另一种状态的手段。

状态空间：描述一个问题的所有状态及其关系。表示为三元组 ，其中 S 为初始状态集合，F 为操作集合，G 为目标状态集合。

基本思路：

1. 选择适当状态与操作的形式化描述
2. 构建状态转换图，直到找到目标状态。
3. 从初始状态到目标状态的算符序列就是一个可行解。

与-或树搜索/问题归约求解

• 分解：若问题 可以归约为一组子问题 ，并且当且仅当 均有解时， 才有解，则称为问题的分解。子问题的“与”与原问题等价。
• 等价变换：若问题 可以归约为一组子问题 ，并且当且仅当 中的至少一个问题有解时， 才有解，则称为问题的等价变换。子问题的“或”与原问题等价。

将问题归约后，形成树形结构，即为与-或树。问题归约求解过程即为寻找可行解树，证明根节点为可解节点。

盲目搜索

基本思路：

1. 将初始状态加入 Open 表。
2. 若 Open 表为空，则无解退出。
3. 从 Open 表中取出一个状态，放入 Closed 表，记为 。
4. 若 为目标状态，则返回 。
5. 若 不为目标状态，则将 的所有可扩展的子状态加入 Open 表。转第 2 步。

根据 Open 表的设置，可以分为：

• 广度优先搜索：Open 表采用队列结构，先进先出。
• 深度优先搜索：Open 表采用栈结构，先进后出。

状态空间的启发式搜索

启发式信息：与问题求解过程相关，指示最有希望的求解方向的信息。

• 帮助确定扩展节点
• 帮助确定哪些后继节点应当被生成
• 确定扩展时哪些节点应当从搜索树上删除。

估价函数：用于估计节点重要性，定义为初始节点出发，经过该节点到达目标状态的最小代价的估计值。

其中， 为从初始节点到当前节点的实际代价， 为从当前节点到目标状态的最优路径的估计代价。

• A 算法：每一步都利用估价函数对 Open 表中节点排序，选取 Open 表中估价最小的节点/新生成子节点中估价最小的节点进行扩展。
• A* 算法：设 ，其中 为从初始节点到 的最优路径的实际代价， 为从 到目标状态的最优路径的实际代价， 是对其的估计，且满足：，则这样的 A 算法称为 A* 算法 A* 算法是可采纳的。
  • 可采纳性：对任一状态空间，若从初始状态到目标状态存在路径，则一定能在有限步内找到一条最佳路径，并在该路径上结束。

与-或树的启发式搜索

解树的代价计算方法：

• 若 为终止节点，则
• 若 为不可扩展节点，且不是终止节点，则
• 若 为“或”节点，则
• 若 为“与”节点，则：
  • 最大代价：
  • 和代价：
• 根节点的代价即为解树的代价。

希望解树：搜索过程中最有希望成为最优解的解树。

• 初始节点在希望解树中。
• 若 为“与”节点，且在希望解树内，则其所有子节点均在希望解树中。
• 若 为“或”节点，且在希望解树内，则其子节点 在希望解树中的条件为：。

博弈树搜索

博弈是一类具有智能行为的竞争活动。

博弈双方按照使得己方获胜概率最高的方式交替行动。

将博弈过程用与-或树表示，则称为博弈树。

博弈树中，MAX 节点和 MIN 节点交替出现。

对于叶子节点估价，正值为方有利的节点负值为对方有利的节点对双方机会均等的节点。

对于非叶子节点，从叶节点向上倒推。MAX 节点取子节点中代价最大的，MIN 节点取子节点中代价最小的。搜索过程即为 Min-Max 过程。

Alpha-Beta 剪枝：

• 记 MAX 节点当前子节点的最大倒推值为 ，MIN 节点当前子节点的最小倒推值为 。
• 若满足以下条件，则直接放弃当前子节点的扩展。
  • 对于 MAX 节点：当前节点的 大于等于父节点的 ，则令其倒推值为 。
  • 对于 MIN 节点：当前节点的 小于等于父节点的 ，则令其倒推值为 。

智能优化算法

智能优化算法的定义

• 邻域：
  • 函数优化问题：以一点为中心的球体
  • 组合优化问题：从当前状态邻域映射产生的集合。
• 局部搜索：不断向当前状态的邻域搜索，直到找到一个局部最优解。
  • 简单，但无法保证全局最优解。
  • 结果依赖邻域结构和初始状态。
  • 初始状态足够多时，局部搜索可以找到全局最优解。

模拟退火算法

模拟退火算法通过模拟物理退火过程，找到全局最优解。

Metropolis 准则：以一定概率接受新状态。

算法流程如下：

1. 给定初始温度 ，随机选取初始状态 。令 。
2. 基于当前状态 产生邻域。对于邻域中的状态 ：
   1. 若 的代价 小于 的代价 ，则接受 。
   2. 若 的代价 大于 的代价 ，则以概率 接受 。
3. 重复第 2 步，直到满足抽样稳定准则。
4. 退温：。
5. 判断是否满足算法终止准则，若满足则结束算法。否则转 2 步。

核心为“三函数两准则一初温”。

• 一初温：初始温度 。
• 两准则：
  • 算法终止准则：判断是否结束算法。设置温度阈值、迭代次数、最优值保持不变等
  • 抽样稳定准则：判断是否结束对邻域的搜索。
    • 非时齐：每个温度下只产生一个或几个状态。
    • 时齐：采用 Metropolis 准则，检验目标函数均值是否稳定、目标值变化较小、按照步数抽样等。
• 三函数：
  • 状态产生函数：在当前邻域结构内按一定规则产生。应当尽量能覆盖解空间。
  • 状态接受函数：确定接受新状态的概率。
    • 在固定温度下，接受次优解的概率应当小于接受更优解的概率
    • 随温度下降，接受次优解概率应当减小。
    • 当温度足够低时，接受次优解的概率应当非常小，只接受更优解。
  • 温度更新函数：根据当前温度 更新下一个温度 。
    • 比例退温：，其中 。
    • ，其中 为迭代上限次数。

优点：

• 高质量
• 对初值不敏感。
• 简单、通用、易实现

缺点：

要求较高初温、较慢降温速率、较低终止温度、足够多抽样次数，因此优化过程较长。

遗传算法

模拟生物进化过程，找到全局最优解。

1. 编码：设计一个编码函数，将解映射到一个向量空间中。
   • 完备性：编码函数应当能够覆盖解空间中的所有解。
   • 健全性：编码空间中的每一个向量应当能够对应一个解。
   • 非冗余性：编码空间与解空间应当一一对应。
2. 初始化：随机初始化一个种群，每个个体为一个解。
3. 评估：计算种群中每个个体的适应度。
   • 一般为对目标函数变换，将目标函数值转换为适应度值。
     • 直接变换：最大化问题直接使用目标函数值作为适应度值。最小化问题则取负。
     • 界限变换 1：最大化问题在目标函数值小于阈值时取 0,否则以目标函数值减去阈值作为适应度值。最小化问题则相反。
     • 界限变换 2：设目标函数为 ，对其保守估计值为 ，则最大化问题取 ，最小化问题取 。
   • 需要满足以下条件：
     • 单值、连续、非负、最大化
     • 合理、一致
     • 计算量小
     • 通用
   • 适应度值越大，个体越优。
4. 选择：根据适应度选择种群中的个体，用于产生下一代种群。
   • 根据适应度计算选择概率。
     • 按比例分配：每个个体的选择概率与其适应度成正比。
     • 按排名分配：每个个体的选择概率与其排名成正相关。
       • 线性分配：。
       • 非线性分配：
   • 通过选择算子根据选择概率选择个体。
     • 轮盘赌算子：令累计选择概率 ，每次生成 内随机数 ，若 ，则选择个体 。
     • 随机遍历抽样：随机生成一个随机数 ，和一个随机偏移 ，第 个选择个体选择时使用的数为
     • 锦标赛选择算子：随机选择 个个体，选择其中适应度最高的 个个体。
     • 截断选择：选择种群中适应度最高的 个个体。
5. 交叉：对下一代种群中的个体进行交叉，引入新的解。
   • 实数重组：中间重组、线性重组。
   • 二进制交叉：单点交叉、多点交叉。
   • 交叉概率：
6. 变异：对下一代种群中的个体进行变异，引入新的解。
   • 变异概率：
7. 更新种群，转 3 步，直到满足算法终止准则。

改进方法：

• 精英解保留：将种群中适应度最高的若干个体保留到下一代种群中。
• 自适应遗传算法：动态调整交叉概率、变异概率。
  • 交叉概率高：新个体产生快，但优秀个体容易被破坏。
  • 交叉概率低：搜索缓慢
  • 变异概率高：新个体产生快，过高则退化为纯粹的随机搜索
  • 变异概率低：搜索缓慢，不易产生新个体结构
• 基于小生境的遗传算法：每代划分为若干小生境，每类选出适应度最高的个体。

对于带有约束的问题，可采用：

• 罚函数法：在目标函数中添加罚项，约束解的范围。
• 解修正法：将不可行解转化为可行解。

优点：

• 具有隐含并行特性
• 适用性好
• 适合先验知识缺乏的问题

缺点：

• 需要编码健壮有效
• 适应度函数设计需要正确反映个体情况
• 种群大小需要认真选择
• 计算量大
• 容易早熟收敛
• 稳定性一般

特征提取与选择

模式识别基础

• 特征矢量：描述模式的向量。
• 特征空间：特征向量的全体组成的空间，记为 。

对于模式识别问题，设样本集为 ， 为真实类别，常用性能度量：

• 错误率：，即分错样本的比例。
• 精度：，即分类正确的样本的比例。

对于两分类问题，设真正例、假正例、真负例、假负例分别为 ，常用性能度量：

• 查全率 Precision：，即检测为正例的样本正确率。
• 查准率 Recall：，即所有正例样本中检测为正例的比例。

根据学习器分类置信度，逐步收紧分类阈值，可做出查全率-查准率曲线（P-R 曲线）。曲线与 的交点为平衡点，可用来衡量分类器性能高低。

F1 分数：，即查全率和查准率的调和平均值。

F-beta 分数：，即查全率和查准率的调和平均值。

类似 P-R 曲线，以假正例率 为横坐标，真正例率 为纵坐标，可做出 ROC 曲线。ROC 曲线下面积可衡量分类器性能高低。

模式识别中基本原则：

• 没有免费午餐原则：任何算法的性能都是相对的，只能在特定问题上取得好性能。
• 丑小鸭原则：不存在与问题无关的、优越的特征集合。
• 最小描述原则：使得模型算法复杂度与和该模型适应的训练数据集描述长度之和尽可能小，即模型的复杂度应当和数据集的复杂度匹配。

类别可分性判据

目的：刻画特征对分类的贡献。

对第 两类的可分性判据 要求：

• 与误判概率/上界/下界有单调关系。 最大时，误判概率最小。
• 特征相互独立时，判据具有可加性。即，。
• 具有和距离类似的性质：
  • 非负性：。
  • 自反性：。
  • 对称性：。
• 对特征数目单调不减，即加入新特征后，判据值不会减少。

不一定要同时具备上述所有性质。

基于几何距离的判据

采用欧式距离。

• 点到点：。
• 点到点集的均方距离：。
• 类内均值：。
• 总体均值：。
• 类内距离：。
• 类内离差阵：。
• 类间距离：。
• 模式间总的均方距离：。
• 总类内离差阵：
• 总类间离差阵：。
• 总体离差矩阵：。

可以构造类可分性判据：

基于类概率密度函数的判据

用两类概率密度函数的重叠程度度量类可分性。判据 应当满足：

• 当两类完全不重叠时，。
• 当两类完全重叠时，。
• 具有对称性。

基本思想为，通过两类概率密度函数乘积、比、差的积分刻画。

• 散度
• Bhattacharyya 判据
• Chernoff 判据

基于后验概率的判据

• 基于信息熵的方法：

特征选择方法

特征选择：从原始特征空间中选择一个子空间，以减少特征空间的维度。

最优搜索法

• 穷尽搜索
• 分支定界法

次优搜索法

• 单独最优的特征选择：选择单独使用时类可分性判据最大的若干特征
• 增添特征法：每次选择一个特征，判断其对类可分性判据的贡献，选择贡献最大的特征加入。
• 剔除特征法：每次选择一个特征，判断其对类可分性判据的贡献，选择贡献最小的特征剔除。
• 增 减 法：先增加 个特征，再剔除 个特征。
• 智能优化算法：模拟退火、遗传算法等。

特征提取方法

特征提取：对原始特征空间进行变换降维，以减少特征空间的维度。

主成分分析 PCA

将原始特征空间投影到低维空间中，使得投影后特征点方差最大。

假设样本已经中心化，即每个样本的均值为零。

设投影方向为 ，要求 , 投影后的结果为：

投影后的方差：

其中， 为样本的协方差矩阵。原问题转化为最优化问题：

用拉格朗日乘子法转化为最优化问题:

求偏导得到：

即：

因此可以注意到，实际上的 为样本协方差矩阵的特征向量。取特征值最大的特征向量即为投影方向。

一般的，推广到高维，投影矩阵 由样本协方差矩阵 个特征值最大的特征向量组成。

线性判别分析法 LDA / Fisher 判别

有监督的方法，使得投影后类内方差最小，类间方差最大。

假设样本已经中心化，即每个样本的均值为零。

设投影方向为 ，要求 , 投影后的结果为：

投影后各类均值：

投影后的类内离差阵：

其中， 为样本的类内离差阵。

总的类内离差阵：

同理，类间离差阵：

构造目标函数：

原问题转化为最优化问题：

求导：

展开得到：

为广义特征值分解问题，求 特征值最大的若干特征矢量即可得到投影方向。

对于两分类问题， 的方向与 相同。

基于判别函数的分类

不同模式的特征点散布在解空间中不同区域。运用已知样本学习，产生若干分类界面 , 将解空间分为若干互不重叠的子区域。

即为判别函数。

基于线性判别函数的分类

令 为增广权值向量， 为增广特征向量。

对于两分类问题，可做如下判决：

拒绝判断或判为任意一类

对于多分类问题，可以采用 两分法，转化为 个两分类问题。

也可以采用 两分法，建立 个分类函数。每个分类函数 只提供关于 和 的分类界面，不提供关于其他分类界面的信息。

也可以采用没有不确定区域的 两分法，对每类建立一个分类函数 ，若 ，则将 分类为第 类。

基于非线性判别函数的分类

对于线性不可分问题，可以采用非线性判别函数。

广义线性判别函数

将输入的模式进行适当的非线性变换到新的模式空间中，使得新的模式空间中的模式线性可分。

二次判别函数

直接构造二次判别函数。确定的分类界面是超曲面。

分段线性判别函数

通过多段线性超平面组合逼近复杂分类界面。

支持向量机

考虑 维空间中的二分类问题，分类平面为：

判决准则为：

一般来说，可以认为最优的分类超平面应当使得分类平面两侧最接近的样本与分类平面距离最大。定义分类后与分类平面最近样本的距离为分类间隔，则应当保证在分类正确的前提下最大化分类间隔。

为了留出分类间隔，构造两个与分类平面平行的超平面，分别位于分类平面两侧。

合并后得到：

假设与最优决策面最近的样本分布在两个平行平面上，则分类间隔为 。

构造优化问题，以“分类正确”为约束条件，最大化分类间隔。

转化为等价的最小化问题：

通过二次规划求解。首先使用拉格朗日乘子法，将约束条件转换为等式约束。

其中：

再转化为其对偶形式求解：

对 取偏导，令其为零，得到：

代入得到：

转化为对偶优化问题：

求解得到 ，代入得到 。

然后基于 KKT 条件，求解 。

根据互补松弛条件 ，得到：

代入 ，得到：

可以认为大部分向量不在平行超平面上，对判别函数无帮助， 为 0。

仅保留支持向量，即 不为 0 的向量。从支持向量中任选一个代入求解即可得到 。

软间隔 SVM 引入松弛变量，推导方式与上式类似。

核技巧

若将样本空间映射到高维空间，则模式向量的维度将增加，提高计算向量内积的复杂度。

对于映射 选择核函数 ，使得

即可大大降低计算复杂度。

基于概率的分类

贝叶斯分类

贝叶斯公式

其中：

• ：后验概率
• ：似然
• ：A 发生的先验概率
• ：B 为真的先验概率

在分类中，以特征向量 代替 B，类别 代替 A。

其中：

• ：输入 为 类别的后验概率。
• ： 类别的先验概率。
• ：输入 的概率分布，即总体概率密度。
• ：在类别 下， 的概率分布（类概率密度）。

最小误判概率准则

两类问题下，误分类概率为：

误判概率最低时，应当选择 最大的类别 。

最小损失准则

设采取决策 时的损失：

待补完，这块暂时没时间写了。我猜也不会考很详细的（）

朴素贝叶斯分类器

假设样本的各属性独立地对分类产生影响。

因此，选择使得 最大的类别 。

估计算法

参数估计

• 矩估计：以样本的矩作为总体矩的估计值，进而估计参数。
  • k 阶原点矩：
  • k 阶中心矩：
  • 对于正态分布，，
    • 协方差矩阵无偏估计（修正）：
• 最大似然估计：定义样本似然函数，最大化似然函数，得到参数的估计值。

非参数估计（Panzer 窗）

将区域定义为一系列超立方体，通过计算每个超立方体内的样本数，以频率估计概率，从而估计概率密度。

待补完，这块暂时没时间写了。我猜也不会考很详细的（）

近邻分类器

对于每个输入的样本，选择距离最近的 个样本，选择其中出现次数最多的类别作为分类结果。

不需要训练，实现简单，在很多时候效果较好。

计算复杂度高，距离度量、 等都需要选择。

人工神经网络

基础定义

M-P 神经元模型：每个神经元有若干输入 和一个输出。输入加权后经过激活函数获得输出。

常用激活函数：

• 阈值函数：或较小
• 分段线性饱和函数：
• Sigmoid 函数：
• 子阈积累函数：

神经网络：由若干人工神经元互联组成的网络。

分类：

• 按照拓扑结构：
  • 前馈：没有反馈结构，神经元仅从上一层接收输入，向下一层传递输出。
  • 反馈：有反馈结构，神经元可以接收来自下一层或同层神经元的输出作为输入。
• 按照层数：
  • 单层：输入层-输出层，无中间隐含层。
  • 多层：输入层-隐含层-输出层，包含至少一个中间隐含层。
• 按照学习方法：监督学习/无监督学习。
• 按照性能：连续/离散

感知机网络

神经元均为线性阈值神经元：

单层感知机可以对输入进行线性二元分类。

设 , 为第 次学习时的权值向量。 为第 次训练样本的输入向量。

训练步骤如下：

1. 设训练轮次 ，初始化连接权值和阈值。
2. ，提供新的样本输入 和期望输出 。
3. 计算网络实际输出 。
4. 若 ，则调节连接权值 。其中，误差函数 。代入得到：

多层感知机增加非线性分类能力。

BP 神经网络

特点为误差反向传播。拓扑结构为多层前向网络，层间全连接，权值可调节。

每个处理单元均为非线性输入输出关系，常用 Sigmoid 激活函数。

学习过程为信号正向传播-误差反向传播组成。

假定一个三层 BP 网络，输入层、隐含层、输出层节点分别以 表示。 为对应节点的输出， 为对应节点的输入，、 为对应连接的权值， 为对应节点的阈值。激活函数均采用 Sigmoid 函数。

对于输入层节点 ，。

对于隐含层节点 ，有：

对于输出层节点 ，有：

由 Sigmoid 函数的性质，有：

设样本集中第 个样本，期望产生的输出为 ，实际输出为 。则误差为：

对于批处理，则一批样本的总误差：

每一轮迭代，连接权值调整：

令局部梯度 ，代入上式有：

对于输出层节点，有 ，则

代入得：

对于隐含层节点，有 ，则

因此，训练过程可以总结为：

1. 初始化连接权值和阈值。
2. 随机输入一个样本，计算网络输出。。
3. 计算误差 。
4. 检查误差是否小于阈值。若小于阈值，则转步骤 9。
5. 。
6. 检查 是否超过最大训练轮次。若超过，则转步骤 9。
7. 调整网络权值。
   1. 计算输出层节点的误差 。
   2. 计算隐含层节点的误差 。
   3. 调整连接权值 。
   4. 调整连接权值 。
8. 转步骤 3。
9. 检查 是否超过样本集大小。若超过，则结束训练。否则转步骤 2。

BP 网络训练方法理论上可以用于训练任何多层前馈网络。训练结束后推理速度较快。

但网络结构设置目前没有理论指导，算法收敛慢，并且可能陷入局部最优。当网络层数较深时，可能出现梯度爆炸情况，导致训练失败。

其他网络

• 玻尔兹曼机
• ART 网络
• Elman 网络
• RBF 网络

深度学习

隐含层数目较多的神经网络。

2006 年，Hinton 提出预训练+微调的训练方法：

• 预训练：每次训练一层隐含层节点，将上一层隐含层节点的输出作为当前层节点的输入。
• 微调：在预训练完成后，对所有节点进行训练，使网络输出与期望输出更接近。

LeCun 提出的 CNN 网络，带有卷积结构。包含多个交替的卷积层和池化层，随后经过一个拉平层，转化为一维向量，再通过一个全连接网络输出。

• 卷积层：由多个卷积核组成，每一个卷积核对应一张特征图输出。卷积通过滑动窗口对输入图像进行卷积（将图像像素值通过卷积核加权求和）操作，得到特征图。
• 池化层：下采样，将特征图分区，以一个值代替分区内所有像素值。
• 拉平层：将特征图展开为一维向量。
• 全连接层：多层前馈神经网络，层间全连接，权值可调节。

CNN 通过一些方法减少了参数量，提高了模型的训练效率。

• 局部连接：卷积层和池化层的神经元仅与输入图像的局部区域相关，与全局区域无关。
• 权值共享：一组神经元共享相同的权值，减少参数量。

聚类

聚类定义

将数据集中样本划分为若干个不相交的子集（簇/类别）。

模式相似性测度

距离测度

• 欧氏距离
• 曼哈顿距离
• 切比雪夫距离
• 明氏距离
  • 时，为曼哈顿距离
  • 时，为欧氏距离
  • 时，为切比雪夫距离
• 堪培拉距离
  • 克服量纲影响
  • 无法消除分量相关性
• 马氏距离
  • 消除了分量相关性
  • 坐标系平移、旋转不变，对量纲不敏感

相似性测度

• 角度相似性
  • 夹角余弦
• 相关系数
  • 数据中心化后的夹角余弦
  • 坐标系平移、旋转、缩放不变

匹配测度

用于二值特征情况，.

• 若 ，则为 匹配。
• 若 ，则为 匹配。
• 若 ，则为 匹配。
• 若 ，则为 匹配。

令：

• 为 匹配数。

• 为 匹配数。

• 为 匹配数。

• 为 匹配数。

• Tanimoto 测度

• Rao 测度

• 简单匹配系数

• Dice 系数

• Kulzinsky 系数

K-Means 聚类

动态聚类：样本所在簇会随迭代变化。

超参数：

• ：聚类数

流程：

1. 随机初始化 个中心点
2. 对每个样本，计算与每个中心点的距离
3. 将样本分配给距离最近的中心点
4. 更新每个中心点的坐标为分配给它的样本的均值
5. 重复步骤 2-4，直到中心点不再移动

优点：

• 简单
• 在数据中存在多个不相交的簇时，K-Means 聚类效果好。
• 收敛速度快
• 相对高效，可以处理大规模数据集。

不足：

• 需要指定聚类数，需要手动调整。
• 对噪声和离群点敏感。
• 收敛到局部最优解。
• 不适合非凸形状的簇。

高斯混合聚类

动态聚类

假设每个簇的样本服从高斯分布。实际样本分布是各簇分布的混合。

超参数：

• ：聚类数

第 簇内样本服从高斯分布，概率密度函数 。

样本总体分布

其中 是混合系数，满足 ，且 。

使用贝叶斯公式估计样本属于每个簇的概率，将样本分配给概率最大的簇。

使用 EM 算法估计参数 。

1. 确定隐变量与似然函数
   • 隐变量：：样本 是否属于簇 。
   • 似然函数：
   • 为簇 中的样本数。
   • 对数似然函数：
2. E-step：确定 Q 函数
   • 上一轮 。
   • Q 函数：
   • 的期望：
   • 定义 为当前参数 下样本 是否属于簇 的概率。
   • 代入 Q 函数，得到：
3. M-step：更新参数

   • 求 使 Q 函数最大。

   • 求偏导得到：

4. 重复步骤 2-3，直到 Q 函数值不再显著改变。

优点：

• 更具一般性
• 仅用少量参数，更好地描述数据分布。

缺点：

• 计算复杂度高，收敛慢。可以用 K-Means 聚类作为初始化，再用 EM 算法继续优化。
• 对离群点、噪声点敏感。
• 数据量小时时，效果不佳。
• 难以确定。

基于密度的聚类

静态聚类：样本所在簇不会随迭代变化。

DBSCAN：基于密度的聚类算法，考虑噪声点。

超参数：

• ：邻域半径
• ：最小样本数

定义：

• 密度：邻域内样本点数量
• 核心点：密度域内样本点数量大于等于 的样本点
• 边界点：密度域内样本点数量小于 的样本点，但在某个核心点的邻域内
• 噪声点：非核心点，非边界点
• 密度直达： 位于核心点 的邻域内，则 由 密度直达。
• 密度可达：存在一条密度直达路径，从 到 ，且路径上的所有样本点都是核心点。则 由 密度可达。
• 密度相连：对于 和 ，若存在核心点 ，使得 和 都由 密度可达，则 和 密度相连。

则将由密度可达关系导出的最大密度相连样本集合划分为一个簇。不属于任何簇的样本点，即为噪声点。

优点：

• 不需要指定聚类数
• 能够发现任意形状的簇
• 可以发现噪声点，对离群点不敏感。
• 聚类结果符合直觉。
• 对输入顺序不敏感。

缺点：

• 对高维数据效果不佳
• 不适合密度差异较小的数据集。
• 调参复杂。
• 收敛慢。

顺序前导聚类

静态聚类

超参数：

• ：最大距离阈值

流程：

1. 第一个样本单独形成一个簇
2. 对于每个样本，计算样本与所有簇的中心的距离
3. 若样本与簇的中心距离小于 ，则将样本分配给该簇，更新簇的中心
4. 否则，创建样本的新簇

受到样本顺序的影响，不同的聚类结果可能不同。

层次聚类

静态聚类

1. 初始时，每个样本单独形成一个簇
2. 每次选择相似度最高的两个簇，合并为一个新的簇
   • 样本最小距离
   • 样本最大距离
   • 样本平均距离
3. 重复步骤 2，直到只有一个簇