聚類與最近鄰方法只依賴一個輸入:兩個觀測值相距多遠,或有多相似。質心方法需要平方歐氏距離(Euclidean distance),階層聚類需要所有點對之間的距離,k 最近鄰分類則按距離為訓練樣本排序。距離或特徵尺度一變,這些方法給出的答案可以完全不同,所以選擇必須明確交代並有所理據。本節列出標準的度量、其中哪些是真正的度量,以及令數值特徵可以互相比較的預處理。
度量與常用量度
定義 14.1.1
(度量與 Minkowski 族)
集合 上的函數 是度量,若對所有 :; 當且僅當 ;;以及 (三角不等式)。對 定義
它們分別是曼哈頓距離(Manhattan distance)、歐氏距離與切比雪夫(Chebyshev)距離。
定理 14.1.2
(三種距離都是度量)
、 與 都是 上的度量。
證明
(證明)
非負性、對稱性,以及「 只在每個座標都相等時成立」,都可直接由公式看出。至於 與 的三角不等式,對每個座標使用 ,再求和或取最大值;和的最大值不超過最大值的和。對 ,令 ,。由柯西–施瓦茨(Cauchy–Schwarz)不等式 ,得 。兩邊開方即得 。
證明透視
柯西–施瓦茨在歐氏三角不等式中的位置
只有三角不等式需要想法,而對 來說,想法就是取平方。令 、,要證的就是 。兩邊都非負,所以它等價於 。展開後只剩一個交叉項 ,而柯西–施瓦茨是唯一不屬例行的一步:它把該項限制在 以內。當 與 是同一向量的非負倍數時等號成立,也就是 落在 至 的線段上。
最後的開方,才把平方後的不等式還原為 的不等式。對 ,同樣的展開需要 ,即 ;在共線的點 上,、,這並不成立。
平方歐氏距離不是度量:數線上的點 有 。然而 k-means 目標用的正是這個量。
概念視角幾何
三種單位球
從幾何看,三種距離的分別在於「與中心的距離不超過一」的點集形狀。在平面上,這個單位球對 是菱形,對 是圓盤,對 是邊與座標軸平行的正方形。由於 逐點成立,菱形包含於圓盤之內,圓盤又包含於正方形之內。以 為中心時,點 的三個距離分別是 、 和 :它在菱形的邊界上,卻遠在正方形之內。
定義 14.1.3
(餘弦相似度、Jaccard 相似度與 Hamming 距離)
對非零的 ,餘弦相似度為 ,餘弦相異度為 。對不同時為空的有限集合 ,Jaccard 相似度為 ,Jaccard 距離為 。對兩個等長字串,Hamming 距離是它們不同位置的個數。
餘弦相似度不理會向量長度,適合比較長度不同的文件的詞數向量: 與 的餘弦相似度為 ,但歐氏距離為 。
命題 14.1.4
(單位向量上的餘弦與歐氏距離)
若 ,則 。因此在單位向量之中,以固定單位向量 為基準,按歐氏距離由小至大排序,與按餘弦相似度由大至小排序結果相同。
證明
(展開平方範數)
,而兩個範數都是 1,所以 。映射 嚴格遞減,所以它把餘弦值的次序反轉。
反例模式
餘弦相異度不是度量
它非負而且對稱,所以有人可能聲稱 是度量。取 、、。則 ,所以 ,而 給出 。因為 ,三角不等式不成立。同一性公理也不成立: 與 是不同的點, 卻為 。方向之間的夾角 避開了這兩個問題。
夾角 本身則是方向之間的度量,但此處不證明。Jaccard 距離與 Hamming 距離都是度量;我們不加證明地引用這個標準事實。
縮放數值特徵
歐氏距離把各特徵的平方差相加,所以數值範圍大的特徵會主導總和。兩種常見補救方法,是用訓練數據分別重新縮放每個特徵。
定義 14.1.5
(最小最大縮放與標準化)
設某特徵的訓練值最小為 ,最大為 ,均值為 ,總體標準差為 。最小最大縮放把值 變為 ,使訓練範圍落在 。標準化(z 分數)把 變為 ,使訓練值均值為 、方差為 。常數特徵有 及 ,必須剔除或不縮放,因為公式沒有定義。
常數 只用訓練數據擬合,之後原封不動地套用於驗證與測試數據。若在合併的數據上計算,測試資訊會影響變換,這是一種洩漏,會令評估過於樂觀。落在訓練範圍之外的測試值會被映射到 之外,這是正確的行為,不應不聲不響地截斷。
例題
例題 14.1.6
(縮放可以改變最近鄰)
四位客戶的(年齡,收入)為 、、、。未縮放時,從 出發的歐氏距離為 、、,故最近鄰是 :收入一列主導了距離,而 最近,只因它的收入與 相同。
以訓練範圍作最小最大縮放:年齡 至 ,收入 至 。縮放後的點為 、、、。從 出發的距離, 為 , 為 , 為 。現在最近的是 。兩個答案在抽象意義上都沒有「正確」與否;縮放後的版本把任一特徵上一個全範圍的差異視為同樣大,這是建模選擇,應有意為之。
例題 14.1.7
(以訓練統計量標準化,以及集合與向量度量)
某訓練特徵的值為 。均值 ,平方偏差為 ,總和 ,所以總體方差為 ,。標準化後的訓練值為 。測試值 以訓練的 與 變為 。若把 計入再重算統計量,均值會變為 ,並在不知不覺間改變每一個變換後的值。
對集合 與 ,,,所以 ,Jaccard 距離為 。
例題 14.1.8
(最小最大縮放下的離群值與常數特徵)
某特徵的訓練值為 。則 、、,縮放後的值為 ,約為 。若沒有離群值,範圍是 ,四個普通值會映射到 。現在普通點之間相差一個單位,只對縮放後的座標貢獻 ,而不是 ,所以這個特徵幾乎不影響它們之間的距離。
第二個特徵在每個訓練行都取 。則 , 是 ,標準化的 。這個特徵無法區分訓練行,所以縮放前須先移除(或不縮放),並預先訂明處理方針。
常見錯誤與細節
常見錯誤
(縮放並非沒有代價,距離也必須配合數據類型)
把本來已在有意義的共同尺度上的特徵標準化,可能抹去有用的資訊。最小最大縮放對單一離群值很敏感,它會拉大 ,把其餘所有值壓縮。把二元指示特徵寫成 與 並用歐氏距離,等於暗中計算不匹配的個數;這是否合用,應當決定,而非假設。最後,三角不等式之所以重要,是因為有些算法(例如剪枝鄰居搜尋的算法)只對度量才正確;未經檢查,不要在那裏改用餘弦相異度。
練習
快速檢查
(1. 比較三種距離)
計算 與 之間的 。
解答 · 解答 1
各座標差為 。所以 ,,。
快速檢查
(2. 縮放一個測試值)
某特徵的訓練值為 。以訓練統計量,求新測試值 的最小最大值與 z 分數。
解答 · 解答 2
訓練最小值與最大值為 與 ,故最小最大值為 ,如預期落在 之外。以 、 計,z 分數為 。
快速檢查
(3. Jaccard 距離)
計算 與 的 Jaccard 距離。
解答 · 解答 3
有 個元素, 有 個。所以 ,距離為 。
快速檢查
(4. 單位向量上的餘弦與歐氏距離)
設 ,。驗證兩者都是單位向量,計算 與 ,並核對恆等式 。
解答 · 解答 4
,。餘弦為 。又 ,而 ,與恆等式一致。