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 比較
∎時,點 的鄰域只有它自己,所以是雜訊。其餘每個點在距離 內都有鄰居,仍是核心點,所以前兩個群組不變:兩個群組和一個雜訊點。