图谱

可访问图谱列表

• 图的基础 - draft

  contrasts: 确定性有限自动机. 二者都使用圆点和箭头，但图的基础描述对象之间的关系，而 DFA 图描述有限记忆状态和带输入标签的转移。

  prerequisite: 广度优先搜索. BFS 会反复查看每个节点的直接邻居，因此需要节点、边和邻接关系这些图的基础。

• 广度优先搜索 - draft

  generalizes: Dijkstra 算法. Dijkstra 保留 BFS 的前沿和距离思想，但按当前暂定总代价最小来选择下一个节点，而不是按先进先出的队列顺序。

• Dijkstra 算法 - draft
• 最近点对分治 - draft

  contrasts: Graham 扫描. 二者都是几何算法，但最近点对分治依赖递归合并，Graham 扫描依赖排序和栈不变量。

  contrasts: Bentley-Ottmann 扫描线. 二者都在几何问题中避免朴素的成对检查，但最近点对使用递归空间过滤，而 Bentley-Ottmann 使用动态扫描线。

• Graham 扫描 - draft

  motivates: Bentley-Ottmann 扫描线. Graham 扫描引入几何排序和局部转向测试；Bentley-Ottmann 将这种思想扩展为随事件变化而维护的动态顺序。

• Bentley-Ottmann 扫描线 - draft
• P 与 NP - draft

  prerequisite: 多项式时间归约. 归约用多项式时间来比较判定问题，因此学习者需要先理解 P 与 NP 中的判定问题和多项式时间算法。

  uses: 电路可满足性. 电路可满足性使用了 P 与 NP 中“候选赋值可作为多项式时间可检查证书”的思想。

• 多项式时间归约 - draft

  prerequisite: NP-Hardness. NP-hardness 定义为 NP 的每个问题都向目标问题的多项式时间归约。

  prerequisite: 从 Circuit-SAT 到 SAT 的归约. 该归约是多项式时间归约在 SAT 方向上的第一处具体实现。

• NP-Hardness - draft

  prerequisite: 电路可满足性. 电路可满足性是在一般 NP-hardness 定义之后的第一个具体源问题。

• 电路可满足性 - draft

  prerequisite: 从 Circuit-SAT 到 SAT 的归约. 该归约从具体的 Circuit-SAT 源实例出发，产生一个 SAT 公式。

  motivates: 布尔可满足性（SAT）. SAT 询问的仍是“是否存在一个满足赋值”，但对象从门电路换成了布尔公式。

• 从 Circuit-SAT 到 SAT 的归约 - draft
• 布尔可满足性（SAT） - draft

  prerequisite: 从 Circuit-SAT 到 SAT 的归约. 在介绍这一具体归约前，先有 SAT 的目标语言与可满足性形式框架。

• 混淆矩阵 - draft

  uses: 精确率. 精确率使用混淆矩阵中预测为正类的部分，询问正类预测里有多少是真的。

  uses: 召回率. 召回率使用混淆矩阵中真实正类这一行，询问真实正类里有多少被抓住。

  uses: Rand 指数. Rand 指数复用了混淆矩阵思想，但计数对象是样本对，而不是单个分类样本。

• 精确率 - draft

  contrasts: 召回率. 精确率评估正类预测是否可信，召回率评估真实正类是否被覆盖。

  uses: F1 分数. F1 将精确率作为调和均值的一侧。

• 召回率 - draft

  uses: F1 分数. F1 将召回率作为另一侧输入。

• F1 分数 - draft
• 纯度 - draft

  contrasts: Rand 指数. 纯度按每个簇的多数参考标签计分，而 Rand 指数检查样本对的放一起/分开决策。

• Rand 指数 - draft

  generalizes: 调整 Rand 指数. 调整 Rand 指数保留 Rand 式成对一致性，再减去由簇和类别边际产生的机会一致性。

  contrasts: Fowlkes-Mallows 指数. 二者都使用聚类样本对计数，但 Fowlkes-Mallows 不使用真负例，而是平衡成对精确率和成对召回率。

• 调整 Rand 指数 - draft

  contrasts: Fowlkes-Mallows 指数. ARI 根据边际规模调整机会一致性，而 FMI 聚焦正向同簇决策，不做机会调整。

• Fowlkes-Mallows 指数 - draft

  contrasts: 轮廓系数. Fowlkes-Mallows 是外部指标，因为它需要参考标签；轮廓系数是内部指标，因为它只判断距离和簇分配。

• 轮廓系数 - draft

  contrasts: Calinski-Harabasz 指数. 轮廓系数逐点比较最近竞争簇，而 Calinski-Harabasz 用全局质心离散度做摘要。

  motivates: Davies-Bouldin 指数. 逐点理解簇内紧密与簇间分离之后，Davies-Bouldin 在簇质心层面提出类似问题。

  motivates: Dunn 指数. 轮廓系数平均点级对比；Dunn 将同样的分离思想变成极值间隔测试。

  applied-in: K-Means 聚类. K-Means 给出硬聚类之后，轮廓系数等内部指标常用于评估结果。

• Calinski-Harabasz 指数 - draft

  contrasts: Davies-Bouldin 指数. CH 是越高越好的全局离散度比例，而 DB 是越低越好的每个簇最坏邻居平均值。

  contrasts: Dunn 指数. CH 使用平方质心离散度；Dunn 使用成对距离极值，因此对桥接点或离群点更敏感。

• Davies-Bouldin 指数 - draft

  contrasts: Dunn 指数. DB 平均最坏质心相似度，而 Dunn 使用单个最近跨簇间隔和最大簇内直径。

• Dunn 指数 - draft
• K-Means 聚类 - draft

  contrasts: K-Medoids 聚类. K-Means 使用平均质心；K-Medoids 要求中心是真实样本点，从而修补这个假设。

  contrasts: DBSCAN. K-Means 寻找中心形状的划分，而 DBSCAN 扩张连通稠密区域并可标记噪声。

  generalizes: GMM 的 EM. GMM 的 EM 保留 K-Means 的交替更新味道，但用概率责任度替代硬性的最近质心分配。

• K-Medoids 聚类 - draft
• DBSCAN - draft

  generalizes: OPTICS. OPTICS 保留 DBSCAN 的密度可达思想，但记录跨距离尺度的排序，而不是固定一个 epsilon。

  generalizes: HDBSCAN. HDBSCAN 从层级中选择稳定分支，而不是使用单一固定密度切分，从而扩展了密度聚类。

• OPTICS - draft

  motivates: HDBSCAN. OPTICS 暴露多尺度密度结构；HDBSCAN 将相关层级转化为被选择的稳定簇。

• HDBSCAN - draft
• GMM 的 EM - draft
• 特征映射 - draft

  motivates: 核函数. 特征映射让映射后内积的问题变得具体，而核函数直接回答这个问题。

  uses: 多项式核. 先看到显式的多项式特征映射，才能更容易理解多项式核。

  motivates: 主成分分析. 特征映射说明输入可以被改写成新的表示；PCA 则从数据本身学到一个线性表示。

• 核函数 - draft

  prerequisite: 线性核. 在线性核之前，需要先知道一般核函数的定义。

  prerequisite: RBF 核. RBF 是一种具名核，它的相似度来自距离衰减，而不是原始点积对齐。

  prerequisite: Sigmoid 核. Sigmoid 核并非在所有参数下都有效，因此需要先理解一般核函数的有效性边界。

• 线性核 - draft

  generalizes: 多项式核. 多项式核从线性核的点积出发，加入幂次项和交互特征。

  contrasts: RBF 核. 线性相似度奖励基于原点的方向对齐；RBF 相似度奖励局部距离接近。

  uses: Sigmoid 核. Sigmoid 核压缩的正是线性核所用点积的仿射变换。

• 多项式核 - draft

  contrasts: RBF 核. 多项式核加入有限次数交互；RBF 则表现得像更丰富的局部特征空间。

• RBF 核 - draft
• Sigmoid 核 - draft
• 主成分分析 - draft

  contrasts: 多维尺度分析. PCA 在旋转后保留坐标方差，而 MDS 从成对距离出发并尝试保留这些距离。

  contrasts: 线性判别分析. PCA 忽略标签并保留高方差方向；LDA 使用标签来保留能分开类别的方向。

• 多维尺度分析 - draft

  generalizes: Isomap. Isomap 保留 MDS 的距离表布局步骤，但用邻居图最短路距离替代原始距离。

• Isomap - draft

  contrasts: 随机邻居嵌入. Isomap 保留图测地距离，而 SNE 保留局部邻居概率。

  contrasts: UMAP. 二者都构造邻居图，但 Isomap 使用最短路距离，而 UMAP 匹配模糊局部成员关系。

• 线性判别分析 - draft

  generalizes: 二次判别分析. QDA 放松 LDA 的共享协方差假设，让每个类别保留自己的协方差形状。

• 二次判别分析 - draft

  contrasts: 随机邻居嵌入. QDA 是监督式分类几何；SNE 回到无监督的局部邻域可视化。

• 随机邻居嵌入 - draft

  generalizes: t-SNE. t-SNE 保留 SNE 的邻居概率匹配，并用低维重尾相似度修补拥挤问题。

• t-SNE - draft

  contrasts: UMAP. 二者都是用于可视化的局部邻居嵌入，但 UMAP 将问题表述为带吸引和排斥的模糊图匹配。

• UMAP - draft
• B 树 - draft

  motivates: B+ 树. B+ 树保留 B 树适合页读取的浅层搜索形状，再把记录放到相连的叶子中，让范围扫描更高效。

• B+ 树 - draft
• 确定性有限自动机 - draft

  prerequisite: 非确定性有限自动机. 先理解 DFA 后更容易学习 NFA：DFA 只有一个当前状态，而 NFA 把转移推广为一组可能的当前状态。

• 非确定性有限自动机 - draft