CSCI3230 L05 · Part 1/5 Clustering basics

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2026T1 本讲：L05，第 1 部分 / 共 5 部分 · 原件 L05-Clustering-2026T1.pdf（本地课件） p.1–15 定位：先确定相似的含义，再讨论分组。前后：下一份 K-Means

整讲导航：

1. Clustering basics：p.1–15。
2. K-Means：p.16–33。
3. Density-based clustering：p.34–53。
4. Agglomerative hierarchical clustering：p.54–77。
5. Summary：p.78–80。

从样本到相似性

封面与路线（p.1–3）

假设桌上有一些没有标签的卡片，每张记录一个人的两个特征。我们想把“比较像”的卡片放在一起，但没人预先告诉我们正确分组。聚类（clustering）要解决的正是这种问题。 它先需要一个相似标准，然后才能谈怎样分组。

本篇只需要会坐标、加减乘除和平方根。后面出现的向量并不神秘：它就是按固定顺序排好的一组数。p.1 是封面，p.2 列出全讲路线，p.3 是基础部分的分节页。先学本篇的“如何比远近”，再学 K-Means 的中心、DBSCAN 的邻居和层次聚类的合并。

数据点（p.4）

p.4 Each sample can be called a Data Point.

数据点是一个样本在特征空间中的表示。补充自取例：把一次购买记录为“面包数量、牛奶数量”，买 1 个面包与 2 瓶奶就是 $a=(1,2)$ 。第一个位置永远是面包，第二个永远是牛奶；另一张卡片 $b=(2,1)$ 用同样顺序。若交换一张卡片的顺序再比较，算术虽没错，比较的对象却错了。

一般写 $a\in\mathbb{R}^n$ ，意思是 $a$ 有 $n$ 个实数特征； $a_j$ 是第 $j$ 个特征。 $n$ 是一张卡片有几个数，样本数是有几张卡片，两者不同。把很多点摆成数据表时，通常一行一个样本、一列一种特征。

p.4的sample还有抽样含义：个体或对象来自某个总体，并经明确程序收集或选取。样本点不是算法凭空产生的点；收集程序决定哪些对象被看见，进而影响聚类可代表的范围。

标签与簇回答不同问题（p.5–7）【延伸 L01 p.68–71】

分类拿着已知标签学习，例如已经标好的猫和狗照片。聚类训练时不靠每点的正确类别，先根据特征找分组。分出的“簇 1”只是编号，不自带“猫”这个语义。把簇 1 与簇 2 的编号交换，分组本身没有变。

图（p.7）：同样八点的四种着色。元素：四幅图点的位置不变，一幅左右两团颜色不同，一幅只把一个点分出去，一幅按上下分，一幅按其他组合分。看什么：数据的位置不能自动规定唯一标签；算法和相似标准共同决定哪些结构被强调。

为准确读出p.5–7：p.5以红色表示Class 0、绿色表示Class 1。p.7四图则展示没有已知标签时的不同候选划分。按位置记左团上排为L1、L2，下排为L3、L4，右团上方两点为R1、R2、下方为R3、R4：第一图红色是全部L点，绿色是全部R点；第二图只L1为绿，其余为红；第三图四个上方点为红、四个下方点为绿；第四图L1、L2、L3、R1、R2为红，L4、R3、R4为绿。这些位置记号是为了文字复现原图，不是课件新增的数据坐标。

补充自取例：按面包和牛奶的购买数量， $(1,2)$ 与 $(2,1)$ 可能很像；但如果任务只看“更偏好牛奶还是面包”，这两人方向不同。先写下业务问题，再选择特征和距离，才不会把“算法分好了”误当“问题回答对了”。无监督不是无需人为选择：距离、尺度和超参数仍由人决定。

欧氏与曼哈顿距离（p.8–9）【新】

先用课件同一对点 $a=(1,2)$ 、 $b=(2,1)$ 算。逐坐标相减得到 $(-1,1)$ ：第一个特征差 1，第二个也差 1。直接相加会得到 0，把正负误差抵消掉，因此不能这样量远近。

欧氏距离先平方、再求和、最后开根号。二维时这是勾股定理的斜边长度：

\begin{aligned} d_2(a,b)&=\sqrt{(a_1-b_1)^2+(a_2-b_2)^2}\\ &=\sqrt{(1-2)^2+(2-1)^2}\\ &=\sqrt{1+1}=\sqrt{2}. \end{aligned}

下标 2 表示用二次方这一种距离，不是第 2 个点。推广到 $n$ 维，只是把两个坐标的平方和改成所有坐标的平方和：

d_2(a,b)=\sqrt{\sum_{j=1}^{n}(a_j-b_j)^2}.

$\sum$ 表示把 $j=1$ 到 $n$ 的各项加起来。输入是两个 $n$ 维向量，输出是一个非负数。越小表示在这套几何下越近。

曼哈顿距离像沿横竖街道走路，分别走完每个方向的差，再相加：

d_1(a,b)=\sum_{j=1}^{n}\lvert a_j-b_j\rvert=1+1=2.

绝对值把负差变成正长度，和平方消符号的方法不同。两种距离算得不同，并不是其中一种错了：一种量直线，另一种量分方向的路程。

补充自取：单位检查。 若第一个特征是月消费额、第二个是次数， $(1000,1)$ 到 $(1100,2)$ 的原始欧氏距离约为 100，几乎只看钱。金额改用千元后，同一两人变成 $(1,1)$ 与 $(1.1,2)$ ，距离约 1.005。算法不是对单位免疫。是否标准化，要由“哪类差异应当更重要”决定，不能机械把任何数据都同样缩放。

切比雪夫与统一形式（p.10–11）

切比雪夫距离问“最大的单项差异有多大”：

d_{\infty}(a,b)=\max_j\lvert a_j-b_j\rvert.

对原来两个点，最大差为 1；对课件的 $a=(1,2)$ 、 $c=(3,1)$ ，两项差为 2、1，所以最大值是 2。这个输出没有把两项累加。

Minkowski 距离把前面几种形式写到一起：

d_p(a,b)=\left(\sum_{j=1}^{n}\lvert a_j-b_j\rvert^p\right)^{1/p},\qquad p\ge1.

其中 $p$ 是人为选的指数， $n$ 是维数，不能混淆。代 $p=1$ 就是绝对差之和；代 $p=2$ 就是平方和开平方。 $p$ 变大时，大的坐标差比小的坐标差更占优势。

想理解 $p$ 趋于无穷为何只剩最大差，可以先让 $M$ 表示最大的绝对差：每一项不超过 $M^p$ ，其中至少一项等于它。因此

M^p\le\sum_j\lvert a_j-b_j\rvert^p\le nM^p.

两边开 $p$ 次方得到 $M\le d_p\le n^{1/p}M$ 。维数 $n$ 固定， $p$ 越大， $n^{1/p}$ 越接近 1，夹在中间的距离便趋向 $M$ 。这是补充推导，第一次读可以先理解三个特例。

余弦看方向（p.12）

前面量两个点的位置差，余弦相似度改问“两个向量指向是否一致”。它常用于更看重比例而非总量的表示，不能默认适用于所有特征。

s(a,b)=\frac{a^Tb}{\lVert a\rVert_2\lVert b\rVert_2}.

这里 $a^Tb=\sum_j a_jb_j$ 是对应坐标相乘再相加的点积； $\lVert a\rVert_2$ 是从原点到 $a$ 的欧氏长度；分母用两长度的乘积消除总量影响。两个输入都必须非零，否则分母为零。

课件的 $a=(1,2)$ 、 $b=(2,1)$ ：分子 $1\times2+2\times1=4$ ；两长度都为 $\sqrt5$ ，分母为 5，所以相似度 0.8。这次越大越像，与距离越小越近相反。p.12 虽把函数名写成 dist，实际算的是相似度。

补充自取： $(1,2)$ 和 $(10,20)$ 方向完全相同，余弦为 1；但位置差为 $(9,18)$ ，欧氏距离是 $\sqrt{405}$ 。这正说明“买得多十倍但比例相同”在两种任务中会有不同解释。余弦范围为 $[-1,1]$ ；正倍数保持方向，负倍数把方向反转。

小检查： 两点的坐标差为 $(3,-4)$ ，三种距离各是多少？若两个非零向量互为正倍数，余弦是多少？

参考答案

欧氏距离为 $\sqrt{9+16}=5$ ；曼哈顿为 $3+4=7$ ；切比雪夫为 4。互为正倍数时余弦为 1，但欧氏距离未必为零。先说清在比较“位置”还是“方向”，再选公式。

补充 · 距离的单位会决定谁成为邻居（通识讲解；演示数据不属于原题）。

演示两个特征为身高和考试分数。A=(170厘米,80分)，B=(180厘米,80分)，C=(170厘米,85分)。直接算欧氏距离，AB=10、AC=5，于是 C 更近；若只把身高改用米，A=(1.70,80)、B=(1.80,80)，则 AB=0.10、AC仍为5，变成 B 更近。现实对象没变，未经处理的数值距离却换了排序。

所以聚类之前先决定每一维差多少才算重要，单位标准化或领域权重是在表达这种选择，不是纯粹清理格式。即使两维标准差相同，也不能自动说明它们对任务同等重要。另一个边界是零向量：它的长度为零，余弦分母无法直接计算；不能把软件随意返回的零值当成定义本身。

应用、算法家族与评价（p.13–15）

图（p.13）：建筑、门和雕像的原图与分割结果并列。元素：同一原图有多种灰绿色块或色区划分。看什么：参数变化会改变分割，不是每个颜色自动对应一个已知物体名称。

p.14 列出中心型、密度型、层次型方法，也点名 GMM 与谱聚类；本讲后面详细展开的是 K-Means、DBSCAN 与凝聚层次聚类。先掌握这三者，不需要在这一页同时学完每个名称。

p.14的完整分类关系是：划分型（partitional）下面列中心型、密度型、Gaussian Mixture Models（高斯混合模型）和Spectral Clustering（谱聚类）；中心型以中心向量代表簇，把近点分配给该中心，例子是K-Means；密度型把高密度区域看作簇、稀疏区域看作噪声或边界，例子是DBSCAN。层次型（hierarchical）另分自底向上的agglomerative和自顶向下的divisive。本讲列出GMM与谱聚类的名字，但没有在这一页给它们的训练推导。

p.15 的 cohesion 是簇内紧密，具体用成员到簇中心的接近程度解释；separation 是簇间分开，具体用不同簇中心之间应较远解释。补充自取：数轴上的 0、1 与 10、11，分成两组后簇内最大差 1、组间最小差 9，直观上既紧又分开。然而一条弯曲密集带可能离单个中心很远，依然是有意义的一组。因此评价必须与算法假设、任务目的相配，不能只记“越紧越好”一句。

p.15配图把三个紧凑且分离的点团标为Good Clustering；另一图用一大团、一条细长团和孤立单点表示Bad Clustering，说明只“分成三组”不等于结构合理。原页最后强调多数应用仍需专家判断。这里判断的是该示意数据与任务，不能由图推广成“所有细长簇都不好”，后面的DBSCAN恰能表示有意义的弯曲簇。

补充：平方距离与余弦“不相似度”并不都是度量

这里把两个常用计算量与严格的距离公理区分开。自编数轴点0、1、2，平方欧氏量从0到2为4，而两段为1与1； $4>1+1$ ，所以平方距离不满足三角不等式。K-means仍能用平方距离作为目标，算法需要的目标函数不必自动是数学意义上的度量。

余弦相似度对非零向量定义为点积除以长度乘积。取 $a=(1,0),b=(1,1),c=(0,1)$ ，则 $1-\cos(a,c)=1$ ，另两段各为 $1-1/\sqrt2\approx0.2929$ ，相加约0.5858，小于1，所以这种余弦不相似度也不满足三角不等式。它强调方向， $a$ 与 $2a$ 的不相似度为0，尽管两向量不同。

零向量还会使分母为0，必须由数据处理或实现说明如何处理，不能写成余弦0便默认解决。理解这些边界的用处是：若后来某个加速算法依赖三角不等式，就不能把任意“越小越像”的公式无条件塞进去；而单纯按某个分数排序近邻则是另一件事。

本讲核心考点

先决定样本、特征与相似性，再谈聚类结果（p.4–7）。
从同一对点分别算 L1、L2、最大坐标差与余弦，说明大小方向（p.8–12）。
区分簇内紧密、簇间分离与应用用途（p.13–15）；以上为讲义知识点，不预测考试。

附录

先完成正文的小检查；无需借助额外考试题才能理解本节。

来源与证据

原件：L05-Clustering-2026T1.pdf（本地课件）；对应页区间见文件头及各节标题。本页正文按 PDF 实际页号阅读；L05 当前文件共 80 页。
数字演示凡非课件原例均明确标为“补充自取”；这些例子用于理解，不是教师布置的作业。
附录中的历史题面保留其文件名、年份和题号，与当前作业区分；它们不能证明本学期考试范围。正文的学习检查是通识练习，不作出题预测。