前面的筆記把分類視為選擇一條由特徵向量映射至標籤的規則,亦用距離量度兩個觀測值相隔多遠。 近鄰(kNN)分類器直接連接這兩個想法:要為新點分類,便找出距離它最近的訓練觀測值,讓它們投票。
想法雖然簡單,細節卻不能忽略。kNN 規則取決於訓練樣本、距離、 的值、距離相同時的排序、票數相同時的處理方法,以及特徵所經過的每一步預處理。若這些選擇沒有訂明,「kNN 預測」未必是唯一的標籤。本節會先固定所有選擇,再探討分類器能夠和不能夠保證甚麼。
動機
假設特徵相近的觀測值,其標籤也傾向相近,那麼為新點猜測標籤時,附近訓練點中最常見的標籤就是合理選擇。kNN 不對決策邊界的形狀作參數化假設;邊界由局部投票結果決定。
這種靈活性也有代價。「附近」是否有意義取決於距離與特徵的尺度,而不是標籤。此外,少量鄰居的投票是一個有雜訊的摘要,不能自動視作概率。
精確定義規則
固定有限訓練樣本 ,其中 ,;索引 表示觀測值在樣本中的原來位置。固定整數 和 上的距離 。除非另有說明,使用歐幾里得(Euclid)距離 。
定義 5.5.1
(採用固定平手規則的 kNN 分類器)
對查詢點 :
- 計算 ,。
- 按數對 的字典順序排列索引:距離較小者在前;距離相等時,原索引較小者在前。記排序為 。
- 鄰居集合為 。
- 鄰居分數為
- 若 ,預測 ;若 ,則預測 。
第 5 步在票數相同時選擇類別 ;這只可能在 為偶數時發生。其他約定也可以,例如選類別 ,或改用最近的 個鄰居。重要的是在查看任何測試標籤之前選定規則,並始終一致地使用。
要區分兩種平手:
- 票數平手指 。取奇數 可以避免。
- 距離平手指多個訓練點與 距離相同。若其中一組橫跨第 個位置,鄰居集合便取決於平手時的排序。奇數 並不能避免這種情況。
定理 5.5.2
(確定性與 的兩個極端值)
固定訓練樣本、距離、 和上述平手規則。
(a) 對每個查詢 ,預測 都是唯一確定的標籤。
(b) 若 ,則每個 的 都是全體樣本的多數標籤;恰有一半標籤為 時選類別 。
(c) 設 , 是一個訓練點。若所有位置恰為 的訓練點都帶有標籤 ,則 。沒有這條件,結論可能不成立。
證明
(各部分為何成立)
(a) 數對 的第二個座標各不相同,因此數對互異。字典順序在這些數對上給出嚴格全序,故 唯一,、 和按閾值決定的標籤也唯一。
(b) 時,不論 是甚麼,鄰居集合都包含所有索引。因此 等於標籤 的整體比例;閾值規則給出所述多數標籤,包括平手時選 。
(c) 在 查詢。所有位於 的訓練點距離均為 ,其餘點的距離均為正。所以 是位於 的點中最小的索引。根據假設,該點的標籤是 。如果兩點位置相同而標籤不同,該位置所有訓練點中索引最小的點決定兩者的預測,因此兩個衝突標籤中至少有一個被錯分,見最後一道練習。
(a) 只說明確定性:樣本及查詢點固定後,輸出也固定。規則定義清楚,並不代表分數已經過校準。
一維例子
例題 5.5.3
(數線上的五個訓練點)
訓練樣本按索引列出:
| 索引 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
查詢 。 距離 依次為 。按 排序得 。當 ,鄰居集合是 ,三個標籤都是 ,故 ,。
查詢 。 距離依次為 。索引 和 的距離均為 。當 ,索引規則把 排在前面,故 。若平手時選較大索引,預測便是 。單靠數據和距離不能唯一決定 的 1NN 預測;平手規則也是分類器的一部分。
同一查詢,。 完整排序是 ,因為索引 和 的距離同為 。第三個位置落在這組平手之內。索引規則選出 ,得到標籤 ,所以 ,預測為 。若選較大索引,便選出 ,得到標籤 ,預測為 。此處 是奇數,不可能有票數平手,預測卻仍取決於距離平手的處理。
。 五個標籤中有三個是 ,所以每個查詢點,包括 ,都被分類為 。 附近的點帶標籤 這項局部資訊已被捨棄。
距離、尺度與特徵
單調變換。 若以 取代 ,其中 嚴格遞增,則所有比較 和所有等式 均保持不變。因此排序與預測不變;這也是可以用歐幾里得距離平方代替歐幾里得距離的原因。同樣,對分數 作嚴格遞增變換會保留各查詢點按分數的排名,但決策閾值也必須一併變換。
特徵縮放不同。 把其中一個座標乘以常數會改變幾何關係,可能重新排列鄰居。
反例模式
縮放一個特徵可令最近鄰改變
取查詢點 、類別 的訓練點 和類別 的訓練點 。它們到查詢點的距離平方分別為 和 ,所以 1NN 預測類別 。
現在把第一個座標乘以 。類別 的點變為 ,查詢點不變。距離平方變成 和 ,故 1NN 預測類別 。
快速檢查
(在上述縮放反例中,若把**兩個**座標都乘以 ,1NN 預測會否改變?)
比較兩個距離如何改變。
解答 · 答案
不會。兩個座標同時乘以 ,每個距離都乘以 ,這是 的嚴格遞增變換,所以次序保持不變:距離平方變為 和 ,1NN 仍預測類別 。只有相對其他座標單獨縮放某一座標,才會改變幾何關係。
因此,轉換特徵的量度單位或將特徵標準化,都是建模決定,並非中性的記帳程序。
無關特徵。 即使某座標與標籤無關,它仍會影響每個距離。若其散布程度與有資訊的座標相若或更大,它可能近乎隨機地改變鄰居排序,令預測趨近於任意訓練點的投票結果。
其他距離。 曼哈頓(Manhattan)距離 或加權歐幾里得距離,分別表達了對哪些差異重要的不同判斷。沒有一種距離可以脫離問題而獨立地被稱為正確;比較距離應透過驗證作決定。
例題 5.5.4
(歐幾里得距離與曼哈頓距離意見不一)
取查詢點 、類別 的點 和類別 的點 。以歐幾里得距離,,所以 1NN 預測類別 。以曼哈頓距離, 的距離為 , 為 ,所以 1NN 預測類別 。歐幾里得距離偏好差異分散在兩個座標的點;曼哈頓距離則把每個座標的差異全數計入。兩個答案都沒有錯,它們是不同的分類器。
高維情況。 例如,若查詢點和固定有限數目的訓練點之所有座標均為相互獨立的標準高斯(Gauss)變量,則隨 增大,距離會相對集中:最遠距離與最近距離之比依概率趨近 。在這情況下,相對距離差異縮小。這是特定分布的性質,並非對所有高維數據成立的定理;集中在低維結構附近的數據可以有好得多的表現。
計算
對單個查詢,以暴力方法精確計算 kNN 的成本如下:
- 計算全部 個距離需 。
- 完整排序 紀錄需 。只要遵守同一字典順序,選擇算法可以期望 時間找出首 個紀錄。
- 點算票數需 。
- 算法儲存訓練數據需 記憶體;這個完整排序版本還需 空間儲存距離及索引紀錄。
樹狀或雜湊索引可減少查詢時間,但效益取決於維度及數據分布,也可能退化至接近暴力搜尋的成本。近似搜尋以精確性換取速度,其輸出可能不同於上述精確規則,因此是另一個分類器。
加權 kNN 用例如 的權重取代等權投票。當 時此權重沒有定義,故須訂明處理方法。一個約定是:若有鄰居的距離為 ,只讓距離為 的鄰居以相等權重投票。
例題 5.5.5
(加權可以翻轉投票,也需要零距離規則)
取訓練點 ,標籤 ,。在查詢點 ,距離為 。不加權的分數是 ,預測為 。若用權重 ,類別 的加權比例為 ,預測為 。
在查詢點 ,第一個權重會是 。按上述約定只有索引 投票,預測為 。若沒有訂明約定,加權規則恰好在訓練點上沒有定義;這正是最可能被拿來檢查預測的邊界情況。
有限樣本的雜訊反例
一種誘人的推論是:1NN 能擬合每個訓練點,因此表現必定好。下一個結果顯示,即使在最簡單的情況下,這推論也不成立。
定理 5.5.6
(純標籤雜訊下的 1NN 錯誤率)
設 幾乎必然成立,,其中 。訓練配對 ()是 的獨立同分布副本;查詢 亦是獨立副本。使用索引平手規則的 1NN 測試錯誤率為
而較佳常數分類器所達到的貝葉斯(Bayes)錯誤率為 。
證明
(計算兩個錯誤率)
所有特徵值均為 ,故所有距離都是 。不論數據如何,索引規則都選索引 ,預測是 。
查詢標籤 與 獨立,兩者均服從 Bernoulli。因此
由於 不提供資訊,最佳分類器是常數。預測 的錯誤概率為 ,預測 的錯誤概率為 ,故貝葉斯錯誤率為 。
令 、。由 ,得 ;只有 時等號成立。
證明透視
獨立性在何處用上
退化的特徵只做一件事:令所有距離都是 ,於是不論標籤如何,索引規則都選索引 。預測 因而是訓練數據的一個固定函數,在看見任何標籤之前已經選定。
其餘由查詢與訓練樣本的獨立性完成:它把 變成乘積計算。若查詢改為訓練點本身,例如 ,同一規則的錯誤率便是 ;這正是擬合訓練集與預測新個案之間的差距。
假設 使比較 有意義:兩個錯誤率都為正,而且除非 ,不等式是嚴格的。當 或 ,兩個錯誤率都是 。
當 ,1NN 錯誤概率為 ,貝葉斯錯誤率則為 。
快速檢查
(設 幾乎必然成立,。計算 1NN 風險和貝葉斯風險。)
以 套用定理。
解答 · 答案
1NN 風險為 。最佳常數分類器預測 ,錯誤概率為 ,所以 1NN 的風險高出 。
有兩個教訓。第一,在訓練點的預測不是對獨立查詢的預測。本例中每個訓練預測都等於 ,所以只有當所有訓練標籤相同時,分類器才完全擬合訓練集; 時未必如此。第二, 小不代表測試錯誤率小。這個結果並沒有肯定或否定其他假設下 kNN 的漸近行為;它只是一個精確的有限樣本例子。
如何影響擬合。 較大的 對更多標籤取平均,降低了對個別雜訊標籤的敏感度,卻會模糊邊界。沒有確定性的有限樣本保證指出準確率必隨 單調增加或減少。正如例子所示,極端情況 完全忽略特徵。
釐清誤解:分數未經證明是概率
常見錯誤
(把五個鄰居中有四個讀成概率 0.8)
「五個鄰居之中有四個屬於類別 1,所以 。」這結論並不成立。分數 只能取 中的值,取決於平手規則和縮放方法,而且由有限樣本計算得出。
在上述雜訊例子中, 時每個分數都是 或 ,但真正的條件概率處處都是 。分數可以用於排名;把它解讀為概率之前,應用留起的數據評估校準程度,例如按分數將留起的個案分組,比較每組平均分數和觀察到的標籤 頻率。這提供校準程度的證據,並非校準的證明。
避免數據洩漏的驗證
選擇 、距離或特徵都是模型選擇,必須遵守相同的驗證紀律:
- 所有依賴數據的預處理步驟都只在訓練摺上學習,包括縮放用的平均值和標準差、缺失值填補數值,以及特徵選擇;然後才把學到的轉換套用到留起的數據行。
- 在所有選擇固定前,不要使用最終測試集。
- 隨機獨立同分布劃分假設各行可交換。群組數據,例如同一人有多條紀錄,需要考慮群組的劃分;時間序列數據需要尊重時間先後。若分布發生偏移,驗證表現未必能轉移至實際部署的人群。
常見錯誤
(留一驗證前只標準化一次)
先用全部 行擬合縮放器或填補器,再進行留一驗證,會讓每個留起的數據行影響它自己的預處理。必須在擬合任何預處理之前移除留起的觀測值;對每個留起的個案,用其餘 行重新擬合縮放器和填補器。
練習
練習 5.5.7
(對上述例子的數據集,求查詢 的 2NN 預測,並討論其他票數平手處理方法。)
基礎
解答(3)
- 1
套用既定規則
排序首兩項為 ,距離均為 ;標籤 、,故 ,映射至類別 。
- 2
比較其他票數平手方法
若平手時選類別 ,預測便為 。若退回使用 個鄰居,便使用索引 並預測 。若擴展至 個鄰居,就會遇到例子中索引 和 的距離平手,結果也取決於距離平手規則。
- 3
結論
各方法均可有合理理由,但可能產生不同分類器,故必須事先選定。
練習 5.5.8
(訓練數據為 、,取 和索引平手規則。求訓練預測及留一預測,並討論數據洩漏。)
核心
解答(4)
- 1
計算訓練預測
在 ,索引 和 的距離均為 ,索引 排先,所以兩個重複位置的數據行都預測為 ,第 2 行被錯分。沒有任何 1NN 規則能同時擬合位置相同但標籤不同的兩行。在 ,預測為 。訓練錯誤率為 。
- 2
計算留一預測
關鍵一步
留起第 1 行時,索引 在距離 處,預測 ,真實標籤為 。留起第 2 行時,索引 預測 ,真實標籤為 。留起第 3 行時,索引 和 在距離 處平手,選索引 ,預測 ,真實標籤為 。留一錯誤率為 。
- 3
檢查預處理
每次留一時,任何標準化器或填補器都必須在不包含留起行的數據上重新擬合。只有一個特徵時,正數倍縮放不會改變鄰居順序。不過留起第 3 行時,餘下的數值 的標準差為 ,因此標準化器必須明確訂定如何處理此情況。
- 4
討論重複紀錄
若第 1、2 行是同一病人的兩條紀錄,隨機劃分可能把一條放進訓練集,另一條放進留起的數據。評估量度的便是對該病人的記憶,而非對新病人的泛化能力。把同一病人的所有紀錄放進同一摺,可以防止這種重疊。
相關筆記
- 分類規則與錯分風險
- 距離與特徵標準化
- 交叉驗證及留起測試
- 分類分數的校準