DBSCAN（基于密度的聚类）
/ DEE-bee-skan /
DBSCAN靠「跟着人群走」来找簇：一个簇，无非就是点密密麻麻挤在一起的一片区域，与其他簇之间隔着稀疏、空旷的地带。想想一张夜间国家的卫星照片——城市像一团团稠密的光斑亮着，之间是漆黑的乡野。DBSCAN把那些明亮斑块的边界勾勒出来，无论它们是什么形状；而且关键在于，它把黑暗中那些零散、孤单的点标为噪声，而不是把它们硬塞进一座它们并不属于的城市。
它靠两个设定运作：一个半径（多近才算「邻近」），以及把一处称为「拥挤」所需的最少邻居数。一个点若在它半径内有足够多的邻居，就是核心点，是一个簇的心脏。算法从一个核心点出发，贪心地把它的每个邻居、以及邻居的邻居都吸纳进来，蜿蜒着穿过稠密的区域向外延伸，直到密度跌落。位于稀薄边缘的点被拉进来；真正孤立的点则被撂在一旁、打上离群点的标记。簇就这样有机地长成密度所赋予的任何形状。
它最突出的两份天赋，恰好正是k均值失手之处：它自己把簇的数目找出来（你从不需要指定），而且它能描出又长、又弯、又不规则的形状——两弯相互勾连的月牙、一条螺旋——这些是「圆形簇」方法做不到的。它是空间数据、异常检测和杂乱的真实世界点云的心头好。诚实的局限是：当不同的簇密度悬殊时它会吃力（一个半径套不住两者），而选那个半径又很挑剔——设错了，你要么把一切融成一团，要么把它碎成齑粉。
两个相互勾连的月牙形点阵，外加几粒散落的斑点。k均值会用一条直线把两弯月牙各劈成两半。DBSCAN顺着密度走，把每弯月牙都完美地描成一个簇——并把那几粒孤单的斑点标为噪声，谁都不属于。无需告诉它原本有两个组。
由密度界定的、任意形状的簇——还有把一个点称作「噪声」的自由。
DBSCAN的杀手锏，是它能把点标为噪声，而不必把每一个都硬塞进某个簇——这对找离群点再合适不过。但它假设各簇密度相近；当它们并不相近时，单一的半径设定就照顾不了所有人。