$$ \def\Ent{\mathrm{Ent}} \def\Gain{\mathrm{Gain}} \def\DOG{\mathrm{DOG}} \def\CAT{\mathrm{CAT}} \def\Gender{\mathrm{Gender}} \def\Tail{\mathrm{Tail}} \def\Weight{\mathrm{Weight}} \def\age{\mathrm{age}} \def\income{\mathrm{income}} \def\student{\mathrm{student}} \def\Class{\mathrm{Class}} \def\yes{\mathrm{yes}} \def\attri{\mathrm{attri}} $$
摘要
本文是 2024Fall-数据仓库与知识发现 的期末复习提纲，根据复习课录音和往年卷整理，以供复习参考。
本文中提到的“教材”是指《数据挖掘：概念与技术（第 3 版）》。
本文在时错佬的博客基础上改进：南京大学软件学院-2023-数据仓库（研究生）期末复习参考 - 知乎。
本 pdf 文档是博客的纸质版，博客将持续更新。原博客链接：https://eaglebear2002.github.io/55721/。
本博客提供 pdf 文档，点击链接可直接打印：数据仓库与知识发现-期末复习.pdf。
点击链接下载 I(S1,S2) 速查表：I(S1,S2)速查.pdf。
感谢唐国柱同学提供的 I(S1,S2,S3) 速查表，点击链接下载：I(S1,S2,S3)速查.pdf。
感谢时错佬提供的分数速查表，点击链接下载：分数速查.pdf。
感谢时错佬提供的信息熵速查表，点击链接下载：信息熵速查.pdf。
如果认为文档对您有帮助，请动动手指进入博客扫码打赏一下吧~
[toc]
考试题型
开卷考试。
一共五道大题：数仓一道，数据挖掘四个方向各一道。
面向往年卷复习即可。
数据仓库及实现技术：数据结构和索引
关于数据仓库，详细内容可参考贝佳老师的课程内容：分类: 2022Fall-商务智能 | EagleBear2002 的博客。
【2012】【2013】数据仓库及其实现技术
- 简述数据仓库在知识发现过程中的作用和地位。
- 为何 B 树等在数据库中广泛使用的索引技术无法被直接引入数据仓库？
- 试采用 BITMAP 索引方式对维度表进行索引。
| ID | SKU | TYPE | PRICE |
|---|---|---|---|
| 01 | BK-6573 | BOOK | High |
| 02 | CD-7189 | CD | Low |
| 03 | SW-8761 | SOFTWARE | High |
| 04 | BK-7651 | BOOK | Middle |
| 05 | CD-3413 | CD | Middle |
| 06 | BK-9861 | BOOK | Free |
| 07 | CD-6573 | CD | Free |
| 08 | SW-9871 | SOFTWARE | Middle |
| 09 | CD-7123 | CD | Low |
| 10 | BK-7123 | BOOK | High |
数据仓库在知识发现过程中的作用和地位
- 数据集成和存储: 数据仓库作为一个集中式的数据存储系统，能够整合来自不同数据源的数据，例如企业内部的事务处理系统、外部数据源、互联网数据等。这种集成确保了数据的一致性和完整性，为知识发现提供了一个可靠和全面的数据基础。
- 数据清洗和预处理: 在数据被存储到数据仓库之前，通常会经过清洗和预处理的步骤，以去除不一致性和错误，提升数据质量。高质量的数据是知识发现的关键，因为知识发现的结果很大程度上依赖于数据的准确性和完整性。
- 数据历史性和时序性: 数据仓库中存储的数据通常包括了时间维度，这使得用户能够进行历史数据分析和趋势预测。在知识发现过程中，时间维度的数据能够提供洞察历史趋势和模式的能力。
- 支持复杂的查询和分析: 数据仓库设计用来支持复杂的查询操作和分析工具，如数据挖掘和在线分析处理（OLAP）。这些工具使得从大量数据中提取有价值的信息变得可能。
- 决策支持: 数据仓库提供的历史、整合、质量高的数据，加上强大的查询和分析工具，为企业提供了有力的决策支持。通过分析这些数据，企业能够发现重要的业务趋势和模式，从而制定更有效的策略和决策。
综上所述，数据仓库在知识发现过程中扮演着至关重要的角色，它不仅是数据存储和管理的中心，也是支持数据分析和知识提取的关键基础设施。
数据仓库不引入 B 树的原因
B 树及其变体（如 B+树）是数据库中广泛使用的索引技术，它们提供高效的数据检索和插入性能。然而，在数据仓库环境中，这些技术无法被直接引入，主要基于以下几个原因：
- 查询模式的不同: 传统数据库系统（如在线事务处理系统，OLTP）和数据仓库在查询模式上有显著的不同。OLTP 系统通常处理大量的短小事务，如插入、更新和删除，这些操作涉及到少量记录。B 树等索引非常适合这种类型的快速查找和修改。然而，数据仓库主要用于在线分析处理（OLAP），其特点是少量的查询，但每次查询涉及大量数据，并且查询通常是复杂的，涉及到多表连接和聚合操作，这种情况下 B 树的效率并不高。
- 数据更新频率: 数据仓库中的数据通常是预处理和加载的，而不是实时更新的。这意味着数据仓库中的数据变化频率远低于 OLTP 系统。因此，数据仓库中不太需要针对频繁更新优化的索引结构。
- 大规模扫描的需要: 数据仓库的查询通常涉及对大量数据的扫描。在这种情况下，传统的 B 树索引可能不如其他针对批量读取优化的技术，如位图索引或列式存储。
- 存储空间的考量: B 树索引占用相对较多的存储空间。在数据仓库中，由于数据量本身就很大，因此额外的索引可能会导致存储空间的显著增加。 列式存储的兴起: 数据仓库领域的一个重要趋势是列式存储的使用，这对于执行大规模分析查询更为有效。列式存储与 B 树这种基于行的索引方法在概念上有所不同，更适合数据仓库的使用场景。
综上所述，尽管 B 树等索引技术在传统数据库中非常有效，但由于数据仓库与传统数据库在数据处理和查询需求上有本质的区别，使得这些技术并不适合直接应用于数据仓库环境。相反，数据仓库倾向于使用其他类型的索引和存储结构，以满足其特定的性能和存储需求。
BITMAP 索引
位图（BITMAP）索引是一种特别适合数据仓库和决策支持系统的索引结构，尤其对于那些具有低基数（即列中不同值的数量较少）的列。在构建位图索引时，每个不同的值都会对应一个位图，位图中的每一位表示一行记录。如果某行记录含有该值，则相应的位设置为 1；否则为 0。
下面是基于给定的产品维度表创建的 TYPE 列的位图索引：
| ID | 原表中 TYPE | BOOK | CD | SOFTWARE |
|---|---|---|---|---|
| 01 | BOOK | 1 | 0 | 0 |
| 02 | CD | 0 | 1 | 0 |
| 03 | SOFTWARE | 0 | 0 | 1 |
| 04 | BOOK | 1 | 0 | 0 |
| 05 | CD | 0 | 1 | 0 |
| 06 | BOOK | 1 | 0 | 0 |
| 07 | CD | 0 | 1 | 0 |
| 08 | SOFTWARE | 0 | 0 | 1 |
| 09 | CD | 0 | 1 | 0 |
| 10 | BOOK | 1 | 0 | 0 |
【2014】【2015】BITMAP 索引和 Join Index 索引
- 试采用 BITMAP 索引方式对图 1 中的维度表进行索引；
- 试采用 Join Index 对图 1 中的事实表和维表进行索引。
BITMAP
很简单，略
Join Index
参照下图建表即可，很简单，本题不提供答案。
【2019】数据仓库概念题
- 数据立方体是什么？什么是数据立方体的多层和多维度？
- 数仓数据存储设计中，表合并、表冗余、表分割这三个的原理
数据立方体是什么
数据立方体（Data Cube）是一种用于表示和处理多维数据的数据结构。在数据库和数据仓库系统中，它是一个常用的概念，特别是在在线分析处理（OLAP）和多维数据分析中。数据立方体使得用户可以从多个维度（如时间、地区、产品类型等）分析数据，支持复杂的数据查询和汇总操作。 以下是数据立方体的几个关键特点：
- 多维视图：数据立方体提供多维的视图，使用户能够从不同的角度和维度分析数据。
- 聚合操作：它支持聚合操作，如求和、平均、最大值和最小值等，以便对数据进行汇总分析。
- 切片和切块操作：用户可以进行切片（Slice）和切块（Dice）操作，以便查看数据的特定部分。切片是指在某个维度上进行数据的筛选，而切块是指在多个维度上同时进行筛选。
- 数据钻取：数据立方体允许用户在不同层级上钻取数据，比如从年度数据钻取到季度或月度数据。
- 灵活性和可扩展性：数据立方体设计灵活，可以根据需要进行扩展，以包含更多维度或数据。
在实际应用中，数据立方体能够帮助企业和组织快速获取关键的业务洞察，支持决策制定过程。通过数据立方体，用户可以轻松地执行复杂的数据查询，无需进行复杂的数据库编程。
数据立方体是一种多维数据模型，主要有星形模式、雪花模式和事实星座模式。
- 星形模式 它是最常见的模式，它包括一个大的中心表（事实表），包含了大批数据但是不冗余；一组小的附属表（维表），每维一个。如下所示，从 item、time、branch、location 四个维度去观察数据，中心表是 Sales Fact Table，包含了四个维表的标识符（由系统产生）和三个度量。每一维使用一个表表示，表中的属性可能会形成一个层次或格。
- 雪花模式它是星模式的变种，将其中某些表规范化，把数据进一步的分解到附加的表中，形状类似雪花。
- 事实星座：允许多个事实表共享维表，可以看作是星形模式的汇集。如下所示，Sales 和 Shipping 两个事实表共享了 time、item、location 三个维表。
在数据仓库中多用事实星座模式，因为它能对多个相关的主题建模；而在数据集市流行用星形或雪花模式
什么是数据立方体的多层和多维度
数据立方体的“多层”和“多维度”是两个关键的概念，它们在多维数据分析中起着重要的作用。让我们一一解释这两个概念：
多维度（Multidimensionality）
定义：在数据立方体中，多维度是指数据可以沿着多个不同的维度进行组织和分析。每个维度代表数据的一个特定方面或分类。
例子：常见的维度包括时间（例如年、月、日）、地理位置（如国家、城市）、产品类别等。例如，一个零售业务的数据立方体可能包含时间、产品类别和地区三个维度。
作用：多维度使得用户能够从不同角度查看和分析数据，以便更全面地理解业务情况和趋势。
多层（Multilevel）
定义：在数据立方体中，多层指的是每个维度内部的层次结构。一个维度可以被分解成不同的层次，每个层次提供不同粒度的数据视图。
例子：以时间维度为例，时间可以被分解为年、季、月、日等层次。用户可以选择查看年度总结数据，也可以深入到月度或日度数据进行更详细的分析。
作用：多层结构允许用户在不同的粒度级别上进行数据分析，从而进行更深入的数据挖掘和洞察。
在实际应用中，数据立方体的多维度和多层特性使其成为一个强大的工具，用于支持复杂的数据分析和决策制定过程。用户可以通过在不同维度和层次上进行分析，获得更深入、更全面的业务洞察。
表合并，表冗余，表分割
在数据仓库存储设计中，表合并、表冗余和表分割是三个关键的概念，它们各自基于不同的原理，旨在优化数据存储、查询性能和数据整合。下面我将详细解释每一个概念：
表合并（Table Merging）
- 原理：表合并是将多个相关的表合并为一个更大的表的过程。这通常发生在维度表与事实表之间，或者是当多个维度表具有高度相关性时。例如，在一个销售数据仓库中，可以将产品信息、供应商信息和价格信息合并为一个大表。
- 目的：主要目的是为了简化查询，通过减少需要进行连接操作的表的数量来提高查询效率。这对于需要频繁访问多个表的数据分析尤为重要。
- 优点：减少了查询时的表连接操作，简化了查询逻辑，提高了查询效率。
- 缺点：可能导致数据冗余和存储空间的增加。
表冗余（Table Redundancy）
- 原理：表冗余是指在一个或多个表中故意存储重复数据的做法。在数据仓库中，这通常意味着某些数据在多个地方被复制和存储。
- 目的：主要是为了优化查询性能，尤其是在分布式系统中，通过本地化数据来减少查询时的网络延迟。
- 优点：提高了数据检索的速度，减少了复杂的表连接和数据聚合操作。
- 缺点：增加了存储需求，可能导致数据一致性维护的复杂性增加。
表分割（Table Partitioning）
- 原理：表分割是将一个大表分割成多个更小的、管理起来更容易的部分。这可以是水平分割（根据行），也可以是垂直分割（根据列）。
- 目的：旨在提高大数据集的管理效率和查询性能。分割后，查询可以仅针对相关的数据分区进行，而不是整个表。
- 优点：提高了大型表的管理效率，优化了查询性能，降低了维护成本。
- 缺点：如果分割策略设计不当，可能会导致数据分布不均匀，影响查询性能。
综上所述，这三种策略在数据仓库设计中都扮演着重要角色。选择哪种策略取决于特定的数据特征、查询需求和系统架构。正确地应用这些策略可以显著提高数据仓库的性能和效率。
【2014】【2015】特征：区分喵喵和汪汪
给定下图目标集（DOG）和对比集（CAT），使用信息增益计算各个属性与当前概念描述任务之间的相关性。并采用 T = 0.1 作为阈值，对属性进行筛选。
背景知识：信息增益
看教材 $\S 8.2.2$。
“各个属性与当前概念描述任务之间的相关性”指的是每个属性（如 $\Gender$、$\Tail$、$\Weight$）对目标集（汪汪，$\DOG$）和对比集（喵喵，$\CAT$）的区分能力或解释能力。换句话说，就是这些属性在多大程度上能够帮助区分或描述 $\DOG$ 和 $\CAT$ 两个类别。
具体来说，通过计算信息增益（$\Gain$），我们可以量化某个属性在划分数据时所带来的不确定性减少程度。信息增益越大，说明该属性对数据集的划分效果越好，也就意味着该属性对描述或区分目标集 $\DOG$ 和对比集 $\CAT$ 更加重要，即相关性更高。
关于使用信息增益构造决策树的 ID3 算法，参考：决策树系列【2】ID3 算法信息增益（源码已经同步到 git）_哔哩哔哩_bilibili。
信息熵（entropy）是度量样本集合“纯度”最常用的一种指标。
假定当前样本集合 D 中第 k 类样本所占的比例为 pk，则 D 的信息熵定义为：
$$ \Ent(D) = - \sum_{k=1}^{|Y|} p_k \log_2 p_k $$
计算信息熵时约定：若 p = 0，则 plog2p = 0。
$\Ent(D)$ 的最小值为 0，最大值为 log2|Y|。$\Ent(D)$ 的值越小，则 D 的纯度越高。
信息增益直接以信息熵为基础，计算当前划分对信息熵所造成的变化。
离散属性 a 的取值：$\set{a^1, a^2, \ldots, a^V}$。Dv: D 中在 a 上取值为 av 的样本集合。
以属性 a 对数据集 D 进行划分所获得的信息增益为：
$$ \Gain(D, a) = \Ent(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} \Ent(D^v) $$
其中，$\Ent(D)$ 表示划分前的信息熵，$\Ent(D^v)$ 表示划分后的信息熵。而 $\frac{|D^v|}{D}$ 表示这一项的权重，样本越多越重要。
对于二元分类（即 |Y| = 2）的某个属性取值 Dv 下，样本被分为大小为 S1, S2 的两组，上式中的
$$ \begin{align*} \Ent(D^v) = - (\frac{S_1}{S_1 + S_2}\log_2\frac{S_1}{S_1 + S_2} + \frac{S_2}{S_1 + S_2}\log_2\frac{S_2}{S_1 + S_2}) \end{align*} $$
为了便于查表计算，定义二元函数：
$$ I(S_1, S_2) = - (\frac{S_1}{S_1 + S_2}\log_2\frac{S_1}{S_1 + S_2} + \frac{S_2}{S_1 + S_2}\log_2\frac{S_2}{S_1 + S_2}) $$
于是只要查表获得 I(S1,S2)，就可以避免对数计算。
I(S1,S2) 函数有如下性质：
$$ \begin{align*} \text{对称性：} & I(m, n) = I(n, m) & \text{ 例如：} I(3,4) = I(4,3) \\ \text{缩放性：} & I(kn,km) = I(n, m) & \text{ 例如：} I(4,2) = I(6,3) = I(8,4) \\ \text{零值性：} & I(n,0) = 0 & (n > 0) \text{ 取到最小值，这意味着当前属性可以完全分类} \\ \text{最大值：} & I(n,n) = \log_2 2 = 1 & (n > 0) \text{ 取到最大值，这意味着当前属性对分类完全没有贡献} \\ \text{值域：} & I(n,0) = 0 \le I(m,n) \le I(n,n) = 1 (n > 0) & \\ \end{align*} $$
点击本文摘要中的链接可下载 I(S1,S2) 速查表。
如果以上内容看不懂，欢迎直接进入下面的计算部分，用实践对照理论。
以上关于 I(S1,S2) 函数的性质是笔者自己总结，欢迎补充和交换意见。
计算总熵
目标集和对比集是两个类别：$\DOG$ 和 $\CAT$。我们将基于目标集和对比集的计数计算总熵。
| DOG | CAT | 总数 | |
|---|---|---|---|
| 数目 | 15 | 10 | 25 |
总熵：
$$ \begin{align*} \Ent(D) = & I(10, 15) \\ = & 0.971 \end{align*} $$
按 $\Gender$ 划分
| $\Gender$ | DOG | CAT | 总数 |
|---|---|---|---|
| M | 9 | 3 | 12 |
| F | 6 | 7 | 13 |
| 总数 | 15 | 10 | 25 |
$$ \begin{align*} \Gain(\Gender) = & \Ent(D) - \frac{12}{25}I(9,3) - \frac{13}{25}I(6,7) \\ \approx & 0.0638 < 0.1 \end{align*} $$
按 $\Tail$ 划分
| $\Tail$ | DOG | CAT | 总数 |
|---|---|---|---|
| Long | 8 | 4 | 12 |
| Middle | 4 | 2 | 6 |
| Short | 3 | 4 | 7 |
| 总数 | 15 | 10 | 25 |
$$ \begin{align*} \Gain(\Tail) = & \Ent(D) - \frac{12}{25}I(8,4) - \frac{6}{25}I(4,2) - \frac{7}{25}I(3,4) \\ \approx & 0.971 - \frac{12}{25} \times 0.9183 - \frac{6}{25} \times 0.9183 - \frac{7}{25} \times 0.9852 \\ \approx & 0.034 < 0.1 \end{align*} $$
按 $\Weight$ 划分
| $\Weight$ | DOG | CAT | 总数 |
|---|---|---|---|
| 0-5 | 3 | 5 | 8 |
| 5-10 | 5 | 5 | 10 |
| 10-15 | 4 | 0 | 4 |
| 15-20 | 3 | 0 | 3 |
| 总数 | 15 | 10 | 25 |
$$ \begin{align*} \Gain(\Weight) = & \Ent(D) - \frac{8}{25} I(3,5) - \frac{10}{25} I(5,5) - \frac{4}{25} I(4,0) - \frac{3}{25} I(3,0)\\ \approx & 0.971 - \frac{8}{25} \times 0.9544 - \frac{10}{25} \times 1 \\ \approx & 0.266 > 0.1 \end{align*} $$
在三种属性中，只有 $\Weight$ 的信息增益大于 T = 0.1。因此，通过 $\Weight$ 来区分喵喵和汪汪是最靠谱的。
关联：发掘经常被一起购买的商品组
- 【2012】针对图 2 的交易事务数据，采用 Apriori 算法求取频繁项集，假设最小支持度为 ≥ 30%；
- 【2013】【2014】【2015】针对图 2 的交易事务数据，采用 FP 增长算法求取频繁项集，假设最小支持度为 ≥ 30%；
- 【2012】【2013】【2014】【2015】基于上述频繁项集，构造关联规则，要求最小置信度 ≥ 50%。
| 事务 ID | 购买项 |
|---|---|
| 1 | $\set{a, b, d, e}$ |
| 2 | $\set{b, c, d}$ |
| 3 | $\set{a, b, d, e}$ |
| 4 | $\set{a, c, d, e}$ |
| 5 | $\set{b, c, d, e}$ |
| 6 | $\set{b, d, e}$ |
| 7 | $\set{c, d}$ |
| 8 | $\set{a, b, c}$ |
| 9 | $\set{a, d, e}$ |
| 10 | $\set{b, d}$ |
【2012】Apriori 算法
按照 Apriori 算法，本题构造频繁项集的过程如下。
$$ \begin{align*} C_1/L_1: & \quad \set{a}:5, \set{b}:7, \set{c}:5, \set{d}:9, \set{e}:6 \\ C_2: & \quad \set{a,b}:5, \set{a,c}:2, \set{a,d}:4, \set{a,e}:4, \set{b,c}:3, \set{b,d}:6, \set{b,e}:4, \set{c,d}:4, \set{c,e}:2, \set{d,e}:6\\ L_2: & \quad \set{a,b}:5, \set{a,d}:4, \set{a,e}:4, \set{b,c}:3, \set{b,d}:6, \set{b,e}:4, \set{c,d}:4, \set{d,e}:6\\ C_3: & \quad \set{a,b,d}:2, \set{a,b,e}:2, \set{a,d,e}:4, \set{b,c,d}:2, \set{b,d,e}:4 \\ L_3: & \quad \set{a,d,e}:4, \set{b,d,e}:4 \\ C_4/L_4: & \quad none \end{align*} $$
Apriori 算法的构造过程可参考教材 $\S 6.2.3$。
【2013】【2014】【2015】FP 增长算法
本题构造的 FP 增长树如下：
graph TD
null --> d:9 --> b:6 --> e:4 --> a:2
e:4 --> c1[c:1]
b:6 --> c1A[c:1]
d:9 --> e2 --> a2A[a:2] --> c1B[c:1]
d:9 --> c1C[c:1]
null --> b:1 --> a1A[a:1] --> c1D[c:1]
构造算法参考教材 $\S 6.2.4$。
【2012】【2013】【2014】【2015】构造关联规则
本题的关联规则很好计算，不再给出答案。
由频繁项集产生关联规则的算法，可参考教材 $\S 6.2.2$。
数据预处理与分类：预测顾客的手机价格
- 【2012】【2013】【2014】【2015】针对图 3 中训练数据集进行离散化处理。要求采用等宽分桶的方式将 $\age$ 和 $\income$ 属性离散到 3 个区间。
- 【2012】依据训练集，采用信息增益作为指标构造决策树。
- 【2012】采用构造出的决策树，分类未知元组（24, 75000, yes）。
- 【2013】【2014】【2015】依据训练集，采用朴素贝叶斯方法分类未知元组（24,
75000, yes），对分类属性
Clas: buys_MP进行预测。
| ID | $\age$ | $\income$ | $\student$ | Class:buys_MP |
|---|---|---|---|---|
| 1 | 23 | 68000 | no | >2000 |
| 2 | 49 | 36000 | no | 1000..2000 |
| 3 | 55 | 22000 | no | 1000..2000 |
| 4 | 34 | 30000 | yes | <1000 |
| 5 | 38 | 15000 | yes | <1000 |
| 6 | 57 | 75000 | no | >2000 |
| 7 | 21 | 52000 | no | 1000..2000 |
| 8 | 31 | 45000 | yes | 1000..2000 |
| 9 | 66 | 58000 | no | 1000..2000 |
| 10 | 34 | 12000 | yes | <1000 |
| 11 | 40 | 40000 | yes | 1000..2000 |
| 12 | 50 | 78000 | no | >2000 |
| 13 | 29 | 20000 | yes | 1000..2000 |
| 14 | 25 | 70000 | no | <1000 |
| 15 | 61 | 55000 | no | >2000 |
| 16 | 45 | 65000 | no | >2000 |
【2012】【2013】【2014】【2015】等宽分桶
等宽分桶、等深分桶和 3-4-5 原则分桶是数据处理中用于数据分桶（binning）的不同方法。这些方法通常用于将连续型数据转换为分类型数据，以便于分析和可视化。下面是这三种方法的详细解释：
- 等宽分桶（Equal-width binning）：在等宽分桶中，数据的范围被分割成宽度相等的区间。每个区间的宽度由数据的最大值和最小值决定。这种方法的优点是实现简单，但缺点是可能不会很好地处理数据中的异常值或非均匀分布。
- 等深分桶（Equal-frequency binning）：等深分桶将数据分割成包含大致相同数量数据点的区间。这意味着每个桶的宽度可能会不同，但每个桶中的数据点数量相似。这种方法对于处理有偏分布的数据较为有效，但可能会导致区间的界限不够明确。
- 3-4-5 原则分桶：这是一种更加定性的分桶方法，通常用于商业和市场分析。它基于这样一个观察：人类倾向于更好地记住和理解 3 到 5 个类别。在应用这个原则时，数据被分割成 3 到 5 个区间，以使结果更容易被人理解和记忆。这种方法更多地依赖于业务理解和目标，而不是严格的数学规则。
下面是本题的等宽分桶计算过程：
对于年龄，桶宽 $d = \frac{66 - 21}{3} = 15$。则分为三组：
A = [21, 36), B = [36, 51), C = [51,66]
对于收入，桶宽 $d = \frac{78000-12000}{3} = 22000$。分为三组：
A = [12000, 34000), B = [34000, 56000), C = [56000,78000]
将 $\age$ 和 $\income$ 分组填入下方。考试时写每组的元组 ID 即可。为了方便后续查找，本表按照 Class:buys_MP 排序。
| ID | $\age$ | $\income$ | $\student$ | Class:buys_MP |
|---|---|---|---|---|
| 4 | A | A | yes | <1000 |
| 5 | B | A | yes | <1000 |
| 10 | A | A | yes | <1000 |
| 14 | A | C | no | <1000 |
| 2 | B | B | no | 1000..2000 |
| 3 | C | A | no | 1000..2000 |
| 7 | A | B | no | 1000..2000 |
| 8 | A | B | yes | 1000..2000 |
| 9 | C | C | no | 1000..2000 |
| 11 | B | B | yes | 1000..2000 |
| 13 | A | A | yes | 1000..2000 |
| 1 | A | C | no | >2000 |
| 6 | C | C | no | >2000 |
| 12 | B | C | no | >2000 |
| 15 | C | B | no | >2000 |
| 16 | B | C | no | >2000 |
【2012】信息增益决策树
信息增益和二元分类参考本文的 $\S 3$。
对于本题中的三元分类，令 S = S1 + S2 + S3，设计新的 I(S1,S2,S3) 函数：
$$ \begin{align*} I(S_1, S_2, S_3) =& - (\frac{S_1}{S}\log_2\frac{S_1}{S} + \frac{S_2}{S}\log_2\frac{S_2}{S} + \frac{S_3}{S}\log_2\frac{S_3}{S}) \end{align*} $$
I(S1,S2,S3) 函数有如下性质：
$$ \begin{align*} \text{对称性：} & I(m, n, p) = I(p, m, n) = I(n, m, p) & \text{ 例如：} I(3,4,2) = I(4,3,2) \\ \text{缩放性：} & I(kn,km,kp) = I(n, m, p) & \text{ 例如：} I(4,2,1) = I(8,4,2) \\ \text{零值降维性：} & I(n,m,0) = I(n,m) & \text{ 这意味着当前属性可以完全排除第 3 种结果} \\ \text{最大值：} & I(n,n,n) = \log_2 3 \approx 1.5845 & (n > 0) \text{ 这意味着当前属性对分类完全没有贡献} \\ \text{值域：} & I(n,0,0) = 0 \le I(m,n,p) \le I(n,n,n) = \log_2 3 \approx 1.5845 & (n > 0) \\ \end{align*} $$
感谢唐国柱同学提供的 I(S1,S2,S3) 速查表，可以点击摘要中的链接下载。
以上关于 I(S1,S2,S3) 函数的性质是笔者自己总结，欢迎补充和交换意见。
构造第一层节点
计算总熵
在本题中，我们分别用 M、N、P 表示 <1000、1000..2000、>2000
| Class:buys_MP | M | N | P | 总数 |
|---|---|---|---|---|
| 数目 | 4 | 7 | 5 | 16 |
$$ \Ent(D) = I(4,7,5) \approx 1.5462 $$
按照 $\age$ 划分
| $\age$ | M | N | P | 总数 |
|---|---|---|---|---|
| A | 3 | 3 | 1 | 7 |
| B | 1 | 2 | 2 | 5 |
| C | 0 | 2 | 2 | 4 |
| 数目 | 4 | 7 | 5 | 16 |
$$ \begin{align*} \Gain(\age) = & \Ent(D) - \frac{7}{16}I(3,3,1) - \frac{5}{16}I(1,2,2) - \frac{4}{16}I(0,2,2) \\ \approx & 1.5462 - \frac{7}{16} \times 1.4488 - \frac{5}{16} \times 1.5219 - \frac{4}{16} \times 1 \\ \approx & 0.1868 \end{align*} $$
按照 $\income$ 划分
| $\income$ | M | N | P | 总数 |
|---|---|---|---|---|
| A | 3 | 2 | 0 | 5 |
| B | 0 | 4 | 1 | 5 |
| C | 1 | 1 | 4 | 6 |
| 数目 | 4 | 7 | 5 | 16 |
$$ \begin{align*} \Gain(\income) = & \Ent(D) - \frac{5}{16}I(3,2,0) - \frac{5}{16}I(0,4,1) - \frac{6}{16}I(1,1,4) \\ \approx & 1.5462 - \frac{5}{16} \times 0.971 - \frac{5}{16} \times 0.7219 - \frac{6}{16} \times 1.2516 \\ \approx & 0.5478 \end{align*} $$
按照 $\student$ 划分
| $\student$ | M | N | P | 总数 |
|---|---|---|---|---|
| yes | 3 | 3 | 0 | 6 |
| no | 1 | 4 | 5 | 10 |
| 数目 | 4 | 7 | 5 | 16 |
$$ \begin{align*} \Gain(\income) = & \Ent(D) - \frac{6}{16}I(3,3,0) - \frac{10}{16}I(1,4,5) \\ \approx & 1.5462 - \frac{6}{16} \times 1 - \frac{10}{16} \times 1.3610 \\ \approx & 0.3206 \end{align*} $$
第一层节点构造完毕
决策树第一层按照信息增益最大的 $\income$ 分类。参考下图画出决策树，即可完成决策树的第一层。
构造第二层节点
按照上述方法，重新计算每个子树中 $\age$ 和 $\student$ 的信息增益，继续构造第二层节点即可。
本文不给出第二层计算方案了。
毕竟机器学习，应该让机器来学习，而不是人。
【2013】【2014】【2015】朴素贝叶斯方法
带拉普拉斯修正的贝叶斯分类：7.6 拉普拉斯修正_哔哩哔哩_bilibili。
目标是预测未知元组（24, 75000, yes）的分类属性
Class: buys_MP。
离散化之后，待预测元组转化为 (A,C,yes)。
计算先验概率
从表格中统计各分类的数量：
| 手机价格分类 | M | N | P |
|---|---|---|---|
| 数量 | 4 | 7 | 5 |
| 先验概率（带拉普拉斯修正） | $\frac{5}{19}$ | $\frac{8}{19}$ | $\frac{6}{19}$ |
条件概率
针对未知元组 $(A, C, \yes)$ 的每个属性值，使用贝叶斯定理计算每个属性取值下，在各分类的条件概率。
| $P(\attri=? \mid \Class=?)$（带拉普拉斯修正） | M | N | P |
|---|---|---|---|
| $\age = A$ | $\frac{4}{7}$ | $\frac{4}{10}$ | $\frac{2}{8}$ |
| $\income = C$ | $\frac{2}{7}$ | $\frac{2}{10}$ | $\frac{5}{8}$ |
| $\student = \text{yes}$ | $\frac{4}{6}$ | $\frac{4}{9}$ | $\frac{1}{7}$ |
后验概率
根据朴素贝叶斯公式：
$$ \begin{align*} P(\Class = X \land (A, C, \yes)) = & P(A, C, \yes) \cdot P(\Class = X \mid (A, C, \yes)) \\ = & P(\Class = X) \cdot P(\age = A \mid X) \cdot P(\income = C \mid X) \cdot P(\student = \text{yes} \mid X) \end{align*} $$
为了简化计算，使用 ∝ 表示正比关系。计算后验概率：
$$ $$
其中，$P(\Class = M \mid (A, C, \yes))$ 最大。
最终，未知元组 $(A, C, \yes)$ 被分类为：$M: \Class = <1000$。
聚类：给平面上的点分分类
聚类的考试范围应该是教材上的所有算法。
- 【2012】【2013】【2014】【2015】针对下图的数据，采用曼哈顿距离作为距离函数，给出对应的相异矩阵。
- 【2012】采用 K-平均点方法对该数据集进行聚类，其中 K=3，起始中心点 ID=1，ID=2，ID=3，即，(3, 5); (2, 6); (3, 8)。
- 【2013】采用凝聚式层次式方法对该数据集进行聚类。聚类间的距离使用聚类中数据的平均曼哈顿距离进行度量。即：给定聚类 Ci, Cj，它们之间的平均曼哈顿距离距为：$d(C_i, C_j) = \frac{1}{|n_i \times n_j|} \sum_{p \in C_i} \sum_{p' \in C_j} |p - p'|$ 其中：|p−p′| 为对象 p 和 p′ 之间的曼哈顿距离，ni 是聚类 Ci 中对象的数目。
- 【2014】【2015】采用凝聚式层次式方法对该数据集进行聚类。聚类间的距离使用聚类中数据之间的最大距离进行度量。
- 【2024Fall】
| ID | x | y |
|---|---|---|
| 1 | 3 | 5 |
| 2 | 2 | 6 |
| 3 | 3 | 8 |
| 4 | 3 | 4 |
| 5 | 7 | 7 |
| 6 | 4 | 5 |
| 7 | 9 | 1 |
| 8 | 4 | 10 |
| 9 | 1 | 6 |
| 10 | 6 | 8 |
| 11 | 5 | 2 |
| 12 | 4 | 2 |
| ID | x | y |
|---|---|---|
| 1 | 3 | 8 |
| 2 | 2 | 7 |
| 3 | 4 | 8 |
| 4 | 3 | 4 |
| 5 | 4 | 5 |
【2012】【2013】【2014】【2015】相异矩阵
看教材 $\S 2.4.1$。
相异矩阵（Dissimilarity Matrix），也称为距离矩阵或差异矩阵，是多维数据分析和机器学习中的一种工具，用于量化数据集中对象之间的不相似程度。在该矩阵中，每个元素代表一对对象之间的相异度（dissimilarity）或距离（distance）。相异矩阵通常是对称的，并且对角线上的值为零，因为每个对象与自身的相异度为零。
【2012】部分相异矩阵如下：
$$ D = \begin{bmatrix} 0 & & & & & & & & & & & \\ 2 & 0 & & & & & & & & & & \\ 3 & 3 & 0 & & & & & & & & & \\ 1 & 3 & 4 & 0 & & & & & & & & \\ & & & & 0 & & & & & & & \\ & & & & & 0 & & & & & & \\ & & & & & & 0 & & & & & \\ & & & & & & & 0 & & & & \\ & & & & & & & & 0 & & & \\ & & & & & & & & & 0 & & \\ & & & & & & & & & & 0 & \\ & & & & & & & & & & & 0 \\ \end{bmatrix} $$
【2012】K-平均点方法
看教材 $\S 10.2.1$。
K-平均点方法（K-Means）是一种常见的无监督学习算法，用于将数据集划分为 k 个簇。其核心思想是最小化簇内样本与簇中心之间的距离，目标是找到簇的最优划分，使得簇内样本相似度高，簇间样本差异大。
算法步骤
- 选择簇数 k：根据需求指定簇的数量。
- 初始化簇中心：随机选择或指定 k 个点作为初始簇中心。
- 分配数据点到最近的簇中心：计算每个数据点到簇中心的距离，将其分配到最近的簇。
- 更新簇中心：计算每个簇内数据点的均值，将其作为新的簇中心。
- 迭代：重复分配和更新簇中心的步骤，直到簇中心不再发生变化或达到最大迭代次数。
【2012】数据聚类结果
| ID | x | y | 簇 |
|---|---|---|---|
| 1 | 3 | 5 | 2 |
| 2 | 2 | 6 | 2 |
| 3 | 3 | 8 | 3 |
| 4 | 3 | 4 | 2 |
| 5 | 7 | 7 | 3 |
| 6 | 4 | 5 | 2 |
| 7 | 9 | 1 | 1 |
| 8 | 4 | 10 | 3 |
| 9 | 1 | 6 | 2 |
| 10 | 6 | 8 | 3 |
| 11 | 5 | 2 | 1 |
| 12 | 4 | 2 | 1 |
【2013】【2014】【2015】凝聚式层次式方法
看教材 $\S 10.3.1$。
凝聚式层次聚类（Agglomerative Hierarchical Clustering）是一种自底向上的层次聚类方法。它从每个数据点作为一个独立的簇开始，逐步合并最相似（或距离最短）的两个簇，直到所有数据点合并成一个簇或达到预设的簇数量。
答题过程中应该写出每次聚类操作之后的聚类。
【2013】使用平均曼哈顿距离，【2014】【2015】使用数据之间的最大距离，两种距离不影响聚类过程和结果。四次聚类操作示意图（纵轴以平均曼哈顿距离为例）如下：
基于密度的方法：DBSCAN
DBSCAN 算法三分钟速通：动画机器学习 6/聚类算法 DBSCAN/史上最简单的三分钟讲解视频/_哔哩哔哩_bilibili。
看教材 $\S 10.4.1$。
【2024Fall】2-中心点算法
看教材 $\S 10.2.2$。
