k-means 等质心方法假设每个簇都紧密围绕一个中心,并把每个观测值硬塞进某个簇。层次聚类则产生整棵树,让用户自行决定在哪里切开。DBSCAN 的看法不同:簇是空间中观测值密集聚集的区域,由稀疏的空间与其他这类区域隔开;落在稀疏空间的观测值被判为噪声,而非强行归入某簇。这个方法需要一种距离,所以上一节关于距离与缩放的内容直接适用;它的结果取决于两个参数,我们会仔细研究。
定义
定义 15.1.1
(邻域、核心点、边界点与噪声点)
设 为带度量 的有限集合,含 个点,并固定半径 及整数 (称为 minPts)。点 的 邻域为 ,它必含 本身。若 ,则 为核心点。若 是核心点且 ,则称 由 直接密度可达。若存在链 (),其中每个 都由 直接密度可达,则称 由 密度可达;因此 都是核心点。若非核心点由某个核心点密度可达,则称为边界点;其余各点都是噪声。
核心点条件中的计数包括该点本身。不同教材与软件的约定并不一致,若不把该点计入,所说的 minPts 数值就有不同含义,所以必须连同参数一并记录所用的约定。
算法
- 把所有点标为未标记,并设簇计数 。
- 按固定次序逐点 处理:若 已被标记或不是核心点,跳过。否则令 加一,把 标为 ,并把 放入队列。
- 队列非空时,取出一点 。对每个尚未标记的 ,标为 ;若 是核心点,则加入队列。
- 结束时,仍未标记的点为噪声。
定理 15.1.2
(核心簇有明确定义,而且 DBSCAN 找到它们)
密度可达限制在核心点上是等价关系。设 为其等价类,它们正是以核心点为顶点、当 时 与 连边所得图的连通分量。DBSCAN 至多进行 次入队后终止;同一类的核心点得到相同标签,不同类得到不同标签;每个边界点得到某个类的标签,该类含有一个与它相距不超过 的核心点。噪声点始终未标记。核心点的划分与处理次序无关;只有靠近多个类的边界点所得的标签可能与次序有关。
证明
(证明)
自反性由长度为零的链得到。对称性:设 为核心点, 为一条链。每个 的 按定义是核心点,而 按假设是核心点,所以每对相邻点都是距离不超过 的两个核心点;因 对称且每项都是核心点,反向的链同样有效。传递性由连接两条链得到。因此这些等价类恰是核心点上 图的连通分量。
终止性:点只在获得标签时才入队,而每点至多被标记一次,所以至多 次入队,每个内层循环都有限。不变式:由核心点 开启的一轮中,每个已标记的点都由 密度可达,而且这一轮中已标记的核心点都已被扫描,或在队列中等待扫描。队列变空时, 所在类的所有核心点都已被标记,因为从 出发的任何核心点链都可以逐步追随。其他类的核心点不可能被到达,否则它就属于 的类。核心点除非被较早种子的一轮标记过,否则不会因"已标记"而被跳过,所以每个类恰得到一个标签。边界点只在处于某个被扫描的核心点的邻域内时才被标记;噪声点不在任何核心点的邻域内,所以不会被标记。
证明透视
假设在证明中的用处
这个证明有一步结构性的转化,以及一处容易放错假设的地方。结构性的一步,是把密度可达换成核心点上 图的连通性;此后与次序无关便自动成立,因为连通分量不取决于搜索访问它们的次序。队列的作用就像广度优先搜索:恰好访问一个连通分量,连同与之相邻的非核心点。
对称性正是使用假设之处。 的对称性使步骤 可以反过来走成 ;而链上除最后一点外都必须是核心点的要求,使反向的步骤合法,因为一步只能从核心点出发。若终点 也是核心点,反向的链仍是链。若 是边界点,最后一步 无法反向,所以在核心点之外密度可达并不对称,命题必须限制在核心点上。
论证得以完结,是因为每点至多被标记一次,并且只在被标记时入队,所以队列在至多 次入队后变空。与两个类相邻的边界点确实可从两者到达,所以它的标签与核心点的划分不同,可能取决于次序。
成本:若每个点的邻域只计算一次并保存下来,核心点判定与第 3 步合计只需每点一次邻域查询,即 次,每次扫描所有点。因此朴素实现需要 次距离计算。空间索引在低维时可使每次查询更廉价,但一般而言最坏情况没有改善,维度升高时好处也会消失。
概念视角几何
把簇看成球的并集
从几何上看,一个簇(核心类与边界点合起来)落在以该类核心点为中心、半径为 的闭球的并集之内。反过来, 中位于这个并集内的每个点,不是该类的核心点,就是边界点,而边界点可能已先被另一个簇标记。所以簇就是一串相互重叠的球,噪声点恰好是不在任何核心点的球内的点。在第一个例题中, 周围的球覆盖 ,其中含有边界点 和 。
例题
例题 15.1.3
(一条直线上的两个簇与噪声)
取点 ,,。各邻域为 、、、、、、、、。核心点为 与 。核心点 属同一类,因为 。点 与 是这一类的边界点, 与 是类 的边界点。点 是噪声。两个簇为 与 ;它们没有合并,因为 ,而 不是核心点。
现在在 下改变 。 时,每个邻域都只有一点,所以所有点都是噪声。 时,点 的 成为核心点, 的 也是;两个簇合并为 ,而 仍是噪声,因为最近的点相距 。
例题 15.1.4
(属于两个簇的边界点)
取点 ,,。按所列次序,邻域大小为 ;例如 、、。核心点为 与 。两组属不同的类,因为它们之间唯一的联系是非核心点 ,而它不能延长链。点 与 各自是一个类的边界点。点 同时是两个类的边界点:它与核心点 及核心点 的距离都是 。若按递增次序扫描,以 为种子的一轮先进行,并把 标为左簇成员;若以 为种子的一轮先进行, 就会加入右簇。两种情况下核心点的划分相同,但 的标签取决于次序。若改用 , 本身就是核心点,并把所有点连成一个簇。
例题 15.1.5
(边界情形:距离恰为 与点数太少)
取点 ,,。由于邻域是闭的,、、、。核心点为 与 ;它们相距 ,所以属同一类,而 与 是这一类的边界点。唯一的簇是 。若邻域改用严格不等式 ,每个邻域都只有一点,四个点全是噪声,可见边界处的约定会改变答案。
再取只有两个点 与 ,。每个邻域至多两点,所以没有核心点,不形成簇,两点都是噪声。一般而言,若 ,就不可能形成任何簇。
常见错误与细节
常见错误
(DBSCAN 并非没有参数,也不能处理密度不一的数据)
不同的 给出不同的聚类,如参数研究所示;单一的 也无法描述同时含有密集簇与稀疏得多的簇的数据:小得足以分开密集簇的半径,会把稀疏的一组判为噪声;大得足以保留稀疏簇的半径,又会把密集簇合并。边界点的归属既不对称,也没有标准答案。DBSCAN 的结果亦非概率陈述:噪声只表示在所选参数下该点不是密度可达。最后要记得,距离必须有意义,所以未缩放的特征可以像最近邻方法那样扭曲邻域。
下一项是定义本身的具体失效情形,而不是泛泛的忠告。
反例模式
边界点使密度可达失去对称性
命题:若 由 密度可达,则 也由 密度可达,于是可以在所有点上形成密度相连的集合。取三个点 ,,。则 有两点, 有三点, 有两点,所以只有 是核心点。点 由 直接密度可达,因为 是核心点且 。但 不由 密度可达:从 出发、 的链要求 是核心点,而它不是,所以从 出发的链只有平凡的一条,只能到达 。命题不成立,失效的原因正是 是边界点。修正后的陈述就是定理中的陈述:密度可达在核心点上对称,边界点是通过某个核心点归入一个类,而不是靠对称性。
用手算应用定义时,还有两种常见的错误。
常见错误
(计算邻域时不把该点本身计入)
在第一个例题中, 有三点,所以对 , 是核心点。若只计其他的点, 只有两个邻居而通不过测试;事实上该例中没有任何一点在距离 内有三个其他的点,因此所有点都会变成噪声。按定义,计数包括该点本身。与软件对照时,要查明它采用哪种约定:不计该点本身而取 minPts 的软件,相当于这里的 。
常见错误
(让边界点延长簇)
链只能经过核心点。在边界点例题中, 与 到点 的距离都不超过 ,但 的邻域只有三点,对 不是核心点,所以不能连接两组。把 当作桥梁,会把 DBSCAN 保持分开的两个簇合并起来。
练习
快速检查
(对点 ,取 、,手算 DBSCAN。列出核心点、簇与噪声。)
先算出各个邻域。
解答 · 答案
各邻域为 、、、、、、、。核心点为 、 与 。簇为 与 ,因为 与 相距不超过 。点 是噪声。
快速检查
(证明:若 对 是核心点,则对任何 及相同的 , 仍是核心点。)
比较两个邻域。
解答 · 答案
若 ,则 蕴含 ,故 。因此 。
快速检查
(对边界点例题中的十一个点,取 、,会得到多少个簇与噪声点?)
数一数每个邻域有多少点。
解答 · 答案
邻域大小为 ,全部不小于 ,所以每个点都是核心点。点 连接 与 (与两者距离都是 ),因此唯一的类含有全部十一个点:一个簇,没有噪声。
练习 15.1.6
(证明:当 时没有噪声点,而簇就是把距离不超过 的点相连所得图的连通分量。把它应用于点 (),并与 比较。)
核心证明
提示(1)
每个邻域都含该点本身。
解答(4)
- 1
证明每个点都是核心点
边界点是非核心点,噪声点是不可密度到达的非核心点,所以在 时两者都不存在。
依据: 的邻域含有 ,所以 。
- 2
确定簇
关键一步
所有点都是核心点,所以簇就是把距离不超过 的点相连所得图的连通分量。
依据: 核心簇就是核心点上 图的连通分量。
- 3
计算这八个点的连通分量
取 ,相邻点之间的间距依次为 。连通分量为 、 与 :三个簇。
- 4
与 m=2 比较
∎时,点 的邻域只有它自己,所以是噪声。其余每个点在距离 内都有邻居,仍是核心点,所以前两个簇不变:两个簇和一个噪声点。