DBSCAN（基於密度的聚類）
/ DEE-bee-skan /
DBSCAN靠「跟著人群走」來找簇：一個簇，無非就是點密密麻麻擠在一起的一片區域，與其他簇之間隔著稀疏、空曠的地帶。想想一張夜間國家的衛星照片——城市像一團團稠密的光斑亮著，之間是漆黑的鄉野。DBSCAN把那些明亮斑塊的邊界勾勒出來，無論它們是什麼形狀；而且關鍵在於，它把黑暗中那些零散、孤單的點標為雜訊，而不是把它們硬塞進一座它們並不屬於的城市。
它靠兩個設定運作：一個半徑（多近才算「鄰近」），以及把一處稱為「擁擠」所需的最少鄰居數。一個點若在它半徑內有足夠多的鄰居，就是核心點，是一個簇的心臟。演算法從一個核心點出發，貪心地把它的每個鄰居、以及鄰居的鄰居都吸納進來，蜿蜒著穿過稠密的區域向外延伸，直到密度跌落。位於稀薄邊緣的點被拉進來；真正孤立的點則被撂在一旁、打上離群點的標記。簇就這樣有機地長成密度所賦予的任何形狀。
它最突出的兩份天賦，恰好正是k均值失手之處：它自己把簇的數目找出來（你從不需要指定），而且它能描出又長、又彎、又不規則的形狀——兩彎相互勾連的月牙、一條螺旋——這些是「圓形簇」方法做不到的。它是空間資料、異常檢測和雜亂的真實世界點雲的心頭好。誠實的局限是：當不同的簇密度懸殊時它會吃力（一個半徑套不住兩者），而選那個半徑又很挑剔——設錯了，你要麼把一切融成一團，要麼把它碎成齏粉。
兩個相互勾連的月牙形點陣，外加幾粒散落的斑點。k均值會用一條直線把兩彎月牙各劈成兩半。DBSCAN順著密度走，把每彎月牙都完美地描成一個簇——並把那幾粒孤單的斑點標為雜訊，誰都不屬於。無需告訴它原本有兩個組。
由密度界定的、任意形狀的簇——還有把一個點稱作「雜訊」的自由。
DBSCAN的殺手鐧，是它能把點標為雜訊，而不必把每一個都硬塞進某個簇——這對找離群點再合適不過。但它假設各簇密度相近；當它們並不相近時，單一的半徑設定就照顧不了所有人。