CSCI3230 L05 · Part 3/5 Density-based clustering

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2026T1 本讲：L05，第 3 部分 / 共 5 部分 · 原件 L05-Clustering-2026T1.pdf（本地课件） p.34–53 定位：局部邻居数量决定能否继续扩张。 前后：上一份 K-Means · 下一份 Agglomerative hierarchical clustering

邻域、核心与连通

p.34 是分节页。这篇接着回答 K-Means 留下的问题：如果一组点沿着弯曲道路密密排开，一个中心不容易代表它，能否只靠局部邻居把整条道路认出来？DBSCAN 就从“附近是否足够密集”开始。读前只需会欧氏距离、集合和计数；不要一上来背四个相似的英文术语。

密集区域与两个参数（p.35–37）【新】

DBSCAN全名是Density-Based Spatial Clustering of Applications with Noise（带噪声的基于密度的空间聚类）。p.35用“密度相连点的极大集合”定义簇：极大表示不能在仍满足相应连通条件时再添点，并非一定是全数据中人数最多的集合。其目标可以容纳不同形状、大小的密集区域。

先做一个补充自取的一维例子：五个点 $A=0,B=1,C=2,D=3,E=7$。把每点看作数轴上的一个人。“附近”定义为距离不超过 1，成为可继续招募邻居的点至少需要附近有 3 人，包括自己。

这两个约定就是算法输入：半径 $\epsilon=1$，最低点数 $\mathrm{MinPts}=3$。它们不是预先要求输出几组；最后有几组要由数据的密集连通结构决定。

p.37 including the point itself

正式把点 $p$ 的邻域写为

左边是一个点的集合；$p$ 是当前中心点，$q$ 是待检查的任一点，$d(p,q)$ 是两个点的距离。大括号里的条件表示“只留下满足距离不超过半径的点”。自身距离为 0，所以在 $\epsilon\ge0$ 时被计入。恰好等于半径也算，不是严格小于。

半径越大，邻域越大；MinPts 越大，成为密集位置的要求越高。这两个旋钮改变不同东西：一个改观察范围，一个改数量门槛。

三种身份怎样判（p.38–40）

继续刚才的五点，逐一列邻域：

为什么 A 和 E 都不够 3 个邻居，身份却不同？这就是三个定义要分步检查的原因：

1. 核心点（core）：自己邻域的人数至少是 MinPts。B、C 达标。
2. 边界点（border）：自己不达标，但在至少一个核心点的邻域内。A 靠近 B，D 靠近 C，可以被接纳。
3. 噪声点（noise）：既非核心，也没有核心邻居。E 距离所有核心都太远。

先一次判完所有核心，再检查其余点是否靠近核心。不要把“点少”直接译成噪声，也不要让边界去招募其他边界。

图（p.39–40）：p.39 以半径 1 和 MinPts=4 画圆辨认三种身份；p.40 将原点图分成绿核心、蓝边界、红噪声。 元素：点与半径圆、核心内部、稀疏边缘及远离团块的点。 看什么：圆圈只是局部观察窗口，最终簇可以沿一串核心延伸，比任何一个圆都大。

有向可达与术语校正（p.41–42）

先用动作理解“直接密度可达”：出发点是核心，终点在出发点邻域内。在五点例中，B 可以接纳 A；A 不是核心，所以不能反过来从 A 扩张。几何距离对称，不代表这个附加了“出发点须核心”的关系也对称。

图（p.41）：p 的圆内至少 4 点，q 的圆内较少。 元素：两个相交邻域，p 为核心，q 为非核心。 看什么：q 从 p 直接密度可达，反方向不成立，限制来自点的身份。

“密度可达”允许走多步。例如 A 从 C 可达：先 C→B，再 B→A。每个发出下一步的点必须是核心，最后接收到的点可以是边界。p.42 的图用 q→p1→p2→p 展示相同机制，终点 p 的非核心身份使反向链无法启动。

术语边界必须单独记。 课件 p.42 把间接 density-reachable 与 density-connected 并称。但标准定义的 density-connected（密度相连） 是：存在共同出发点，使两个点都从它密度可达。这个定义是对称的。五点例中的 A、D 都从 B 可达，因此相连；它们却都不能作为核心向外扩张。不要把课件此页“不对称”的结论误记到标准的 density-connected 上。

这项用词区别可对照 DBSCAN 原论文第 3 节 Definitions 3–4。计算时先写出核心条件和允许的箭头，再使用术语，能减少纯背名词造成的混淆。

算法与边界冲突（p.43–45）

手算可以把算法分成四个动作：判身份；只把相邻核心之间连起来；找每个互相可到达的核心团；最后吸纳各团附近的边界，余下点标噪声。

在补充五点例中，B 与 C 相距 1，都是核心，所以连接。A 由 B 接纳、D 由 C 接纳，得到一簇 A、B、C、D；E 为噪声。该簇两端 A、D 相距 3，远大于半径 1，完全合法。半径约束每一步，不约束整簇直径。

图（p.44）：原点 → 核心/边界/噪声身份 → 最终不同颜色的簇。 看什么：中间图的绿色表示“核心这种类型”，最终图的不同颜色表示“所属簇”。类型和簇编号是两套信息，不能混着读。

p.43 写边界归最近核心的簇，p.45 又允许共享边界任意归其中一簇。这是两种分配约定；基础 DBSCAN 常随访问顺序决定共享边界。若题目指定最近核心，就照该规则；若没指定而结果有歧义，要说明约定。

p.45的四条原则在上述流程中各有对应：每簇至少有一个核心；相邻的两个核心必须属于同簇；同时接触多簇的边界只分给其中一个；噪声不属于任何簇。p.43“先消除噪声”应理解为在全体核心与邻域已明确后确定最终噪声，不能在顺序扫描时把尚未发现核心邻居的点永久删除。

边界不能当桥。 两团核心之间即使有两个相邻的边界，也不能仅靠边界到边界的联系把两团并起来，因为路径中那个边界没有继续扩张的资格。下面课堂十三点例会实际用到这条规则。

补充 · 顺序改变时，哪些部分应稳定（通识讲解；演示数据不属于原题）。

固定距离、半径、MinPts和邻域是否含自身以后，每一点是否核心只由邻域计数决定，不该随遍历顺序变化。核心点之间以合法邻接连成的团也由数据决定。容易受顺序影响的是同时邻近两个不同核心团的边界点：它自己没有资格继续扩张，却可能先被其中一团接纳。

调试时据此分层比较两次输出。若只是簇编号从0变成1，成员集合相同，不是实质差异；若某个共享边界点归属不同，要检查访问约定；若核心身份都变了，则优先检查半径边界、浮点比较、自身计数或数据预处理。不要先把任何差异都归咎于“DBSCAN随机”。这里保留标准算法的边界归属歧义，不把它误写成可以任意合并两团。

补充：共享边界点为何不能把两个核心团粘起来

自编一维数据：左侧四点 $-2,-1.9,-1.8,-1$，右侧四点 $1,1.8,1.9,2$，中间另有0。设 $\epsilon=1$，MinPts=4，邻域含自身，距离等于1也纳入。左四点相互间距离均不超过1，所以全是核心；右四点也全是核心。任意左右核心间的最小距离为2，因而没有直接核心邻接。

点0只邻近−1、0、1，共3点，不是核心，却同时在左右各一个核心的邻域中，因此是共享边界点。遍历左团在先时，它可能归左；右团在先时，它可能归右。但不能经由0继续扩张，把−1连到1，因为继续扩张要求当前中继是核心，而0没有达到门槛。

邻域计数表由数据决定，不随访问顺序改变；核心团因此保持两个。可能变化的是边界0的簇归属。若误把“只要相距不超过半径就连通”应用于所有点，会把两团错误合并。若把MinPts改成3，0就成为核心，这时桥接才合法，得到一团。两种结果差在明确的密度条件，并非图画得像不像一条链。

选参数与失效情形（p.46–48）

p.46 先对每一点找到第 $k$ 近邻有多远，再把这些距离从小到大排列作图。直觉是：密集团中找够邻居只需小半径，孤立点却要走远。图上的弯折处可作为半径的候选；原图标出约 7–10，而不是精确唯一答案。必须先统一近邻是否包含自己，否则“第 4 个”可能指不同对象。

p.46原图横轴为按第4近邻距离排好序的点（约0–3000），纵轴为4th Nearest Neighbor Distance（约0–50），标MinPts=4；曲线大部分缓升，尾部陡升，箭头在约7–10处提示 $\epsilon$。排序横坐标不是空间坐标，尾部陡升表示少数点要走很远才能找够邻居。读者可以按“逐点求第k近邻距离→排序→画曲线→找转折候选→检查聚类稳定性”复现思路，但原页没有提供生成此图的原数据，不能还原每个折点的精确数值。

用五点例看参数变化：若半径仍为 1、MinPts 从 3 改成 4，所有点都不够门槛，全变噪声。若 MinPts=3、半径增到 4，D 的邻域可以触及 E，结构会扩大。具体结果仍须重新列邻域，不能以为只是把边缘描粗一点。

p.47 说明优点：不必预给簇数、能沿核心连接得到弯曲形状、允许把噪声留在簇外。p.48 则展示不同密度难用一个半径兼顾：让稀疏团有足够邻居的半径，可能把本来分开的稠密团连接起来。高维特征中的距离也未必有足够辨别力。无需 K 不等于无需参数，允许噪声不等于知道噪声真实原因。

p.48还指出这里的“密度”估计很简化：它并未拟合一个连续概率密度函数，而是用邻域计数形成密度可达/相连的图结构。因此DBSCAN输出成员与噪声，不能直接把核心点邻居数解释成归一化概率；高维与不同密度的困难也与这种固定半径计数有关。

课堂十三点题（p.49–51）

题面（L05-Clustering-2026T1.pdf，p.49–50）：

p.49 Apply the DBSCAN clustering method to group the following data points: $a_1(0,0),a_2(1,0),a_3(2,0),a_4(3,0),a_5(1,1),a_6(2,1),a_7(4,1),a_8(6,0),a_9(5,2),a_{10}(6,3),a_{11}(7,3),a_{12}(6,4),a_{13}(7,4)$.

p.50 Assume that parameters $\epsilon=\sqrt{2}$ and MinPts=4 (use Euclidean distance) Please answer the following questions.

1. What is the $\epsilon$-neighbor of $a_1$?

p.50 的原题选项：A 为 $\{a_1\}$；B 为 $\{a_2,a_5\}$；C 为 $\{a_2,a_5,a_6\}$；D 为 $\{a_1,a_2,a_5\}$。

公式按原件重排。图（p.49）在二维平面上标出十三点；左团 a1–a6，右上团 a10–a13，中间散布 a7、a8、a9。坐标决定距离，不能凭图上“看起来碰到圆边”来舍入。

先只算 a1：到自身距离 0；到 a2 是 1；到 a5 是 $\sqrt2$；到 a3 是 2，已经超范围。其余点也超范围，所以邻域为 a1、a2、a5，原题选 D。数量只有 3，小于 4，因此 a1 不是核心。这时还没资格判它为噪声，要等检查邻近的 a2 是否核心。

完成两簇判断（p.52–53）

题面（同讲义 · Quiz · p.52）：

p.52 Assume that parameters $\epsilon=\sqrt{2}$ and MinPts=4 (use Euclidean distance) Please answer the following question.

2. What are final cluster results?

A. $\{a_1,a_2,a_3,a_4,a_5,a_6,a_7\}$, and $\{a_9,a_{10},a_{11},a_{12},a_{13}\}$

B. $\{a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8\}$, and $\{a_9,a_{10},a_{11},a_{12},a_{13}\}$

C. $\{a_1,a_2,a_3,a_4,a_5,a_6,a_7\}$, and $\{a_8,a_9,a_{10},a_{11},a_{12},a_{13}\}$

D. $\{a_1,a_2,a_3,a_4,a_5,a_6\}$, and $\{a_7,a_9,a_{10},a_{11},a_{12},a_{13}\}$

集合记号按讲义重排，沿用 p.49 的全部十三点坐标。第二问要求最终簇。先把十三点邻域列全。由于半径是 $\sqrt2$，比较距离平方是否不超过 2 比使用小数 1.414 更安全。

挑最容易卡住的一行算：a4=(3,0) 到 a6=(2,1) 的距离平方为 $1+1=2$，到 a7=(4,1) 同样为 2；再算上 a3 与自己，共 4 个，恰等于门槛就算核心。a7 只有 a4、自己、a9 三个邻居，因此仍是边界。

核心 a2、a3、a4、a5、a6 连成左团；a10、a11、a12、a13 连成右团。a1、a7 被左团接纳，a9 被右团接纳，a8 没有任何核心邻居而留作噪声。最终左簇 a1–a7，右簇 a9–a13，噪声 a8，与 p.53 的选项 A 一致。核对 $7+5+1=13$，没有漏点或双计。

小检查： a7 与 a9 距离正好是半径，为什么不能把左右簇接通？若先访问 a1，暂记“非核心/噪声”，后面能不能改为边界？

想换一组旧作业坐标练习，可见附录 A1，仍按“邻域 → 核心 → 核心连通 → 边界”的顺序。

本讲核心考点

• 闭邻域包含自身及恰在半径上的点（p.37）。
• 数量不足还要检查核心邻居，才能区分边界和噪声（p.38–40）。
• 可达路径的出发步骤须为核心，边界不能桥接（p.41–45、49–53）。
• 区分课件术语与标准 density-connected 定义；不把调参线索当最优证明（p.42、46–48）。

附录

A1 作业/往年题演练（非讲义内容）：HW02 Q3(b–d)：全邻域核验

这道历史题的数据较多，但不需要更高级的公式。先画一张“每点邻域”表；例如判断两个点相距是否不超过 2，只需比较坐标差的平方和是否不超过 4。把核心列完成后再考虑路径：每走一步都检查发出这一步的点是不是核心。核对最终簇与噪声的总人数必须等于 15。下方的箭头链是按此规则得到，不是仅凭点的相邻关系。

题面（HW02-2025T1-题目.pdf · Q3(b)–(d) · p.3；坐标图视觉读取）

p.3 3. Consider the following data and perform the K-means and DBSCAN algorithms using the Euclidean distance between points:

(b) Use DBSCAN to perform the clustering. Assume that $\epsilon=2$ and minpts = 3. List all the core points, border points, noise points. (Remember to include the point itself when calculating the $\epsilon$-Neighbor) (10%)

(c) Based on (b), is h density reachable from b? Show the intermediate points on the chain or the point where the chain breaks of DBSCAN model. (5%)

(d) Based on (b), show the density-based clusters of DBSCAN model. (5%)

公式按原题重排。另有 (a) K-means 问，见上一 Part 附录；本部分重新列全坐标以便独立阅读。

来源：HW02-2025T1-题目.pdf p.3，A 级。题面： 使用Q3图中15点a(1,2),b(2,3),c(2,4),d(6,5),e(3,1),f(3,3),g(4,4),h(7,6),i(8,8),j(8,9),k(9,4),l(5,9),m(4,7),n(6,8),o(6,4)，取欧氏距离ε=2、MinPts=3。(b)找核心、边界、噪声；(c)判断h是否从b密度可达并解释；(d)给最终簇。

b→c→g→o→d→h的步长分别1、2、2、1、√2，且所有发出步骤的点都是核心，故h从b密度可达。反向从边界h出发不成立。

第一簇{a,b,c,d,e,f,g,h,o}，第二簇{i,j,l,n}，噪声{k,m}。核对9+4+2=15，并检查m到n为√5>2，不能把m误纳入第二簇。返回正文

来源与证据

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