1. 從基本原理出發
分類器是一條規則:它接收一個物件的描述,然後回傳一個標籤。有些分類器會擬合一個精簡的模型,例如一條直線、一棵樹或一張概率表。基本的暴力式最近鄰分類則不同,它保留已標籤的樣本,並把基於距離的預測延後至查詢出現時才進行。要為一個新物件加上標籤,它會在所選的距離下找出最接近的訓練物件,然後讓它們投票。
這個方法建基於一個平滑性假設:在特徵空間中彼此接近的物件,往往有相同的標籤。當這個假設對所選特徵大致成立時,kNN 無需擬合固定維度的參數化決策函數也能表現良好。當假設不成立時,kNN 的表現就會變差。典型原因包括無關的特徵、尺度不當的特徵,或特徵數目過多。理解這些失效情況,是理解此方法的重要部分。
2. 設定與記號
我們有一個由 個已標籤樣本組成的訓練集 ,每個樣本有 個數值特徵。
- 每個 是由 d 個數值特徵組成的向量,。
- 每個 是取自一個有限集合的類別標籤。
- 查詢是一個新的特徵向量 q,我們想預測它的標籤。
- 整數 k 滿足 ,並預先固定。
3. 歐氏距離
相似度以距離來量度。在本筆記中,我們一律使用歐氏距離(Euclidean distance):
這是兩點之間的直線長度,即畢氏定理(Pythagoras' theorem)推廣至 d 維。以下兩個事實會反覆用到。
命題 3.4.1
(距離平方給出相同的鄰居次序)
對固定查詢 及訓練點 , 當且僅當 。因此按距離平方排列,與按距離排列所得的次序完全相同,平手情況亦然。
證明
(平方的單調性)
距離非負,而 在 上嚴格遞增,所以它同時保持 與 。因此實作時可以省略平方根。
其次,每個座標貢獻其差的平方。數值上差距較大的特徵會主導總和,不論它是否提供更多資訊。這正是特徵縮放一節所述的尺度問題的根源。
4. 算法及其約定
定義 3.4.2
(帶平手約定的 k 近鄰預測)
給定 q 和 k:
- 對每個訓練樣本 i = 1, ..., n,計算 。
- 按距離由小至大排列樣本。
- 距離平手約定: 若兩個樣本的距離完全相同,索引 i 較小者排先。
- 這使 k 個最近鄰的集合得以唯一確定,即使平手情況橫跨第 k 個位置亦然。
- 按此次序取首 k 個樣本。每個樣本為自己的標籤投一票(不加權多數決)。
- 預測得票最多的標籤。
- 投票平手約定: 若多個標籤同時得到最高票數,則在平手的標籤中,選擇其最接近的入選鄰居離 q 最近的那個標籤。
- 若仍然平手,則按一個固定且已列明的標籤次序(例如按字母次序),選擇排首位的標籤。
為何用奇數 k? 若恰好只有兩個類別,奇數 k 使投票不可能平手,因為奇數張票無法平均分開。這就是為何在二分類問題中常用 1、3、5 等奇數值。奇數 k 有兩個局限:
- 它不能消除距離平手,所以第 2 步仍需要一條規則。
- 若有三個或以上類別,它亦不能消除投票平手:5 票可以分成 2–2–1。
反例模式
奇數 k 不能確定預測
有人可能以為,只有兩個類別而 k 是奇數時,預測完全由數據和查詢決定。取一個特徵,查詢 ,,兩個訓練樣本為 (R)與 (B)。兩者的距離都是 1,所以距離無法決定唯一的鄰居。索引規則選樣本 1,預測 R;若把同樣兩個樣本按相反次序列出,則預測 B。奇數 k 只消除投票平手;橫跨第 k 個位置的距離平手,仍需要第 2 步的約定。
上述規則是約定,而非數學真理。任何確定性規則都可接受,只要在計算前列明,並一致地應用即可。
選擇 k。 取捨是雙向的。
- k 較小時會緊貼訓練數據,對個別有雜訊的點十分敏感。當 時,預測只是照抄單一鄰居的標籤。
- k 較大時決策較平滑,但可能被較大的類別或較遠的點淹沒。當 時,所有訓練標籤都會投票。若某個標籤的總數是唯一最大,該標籤必定勝出;若最高票數平手,則所列明的最近鄰平手規則可能使答案取決於查詢。
選擇 k 時,應使用從訓練部分抽取的驗證數據,絕不可使用最終測試集。
5. 例題
例題 3.4.3
(泥土樣本的最近鄰,以及 k 的影響)
一個溫室項目把泥土樣本標籤為 R(需要重新灌溉)或 B(狀況良好)。它使用兩個已在可比較尺度上量度的特徵: = 乾燥指數, = 鹽分指數。
| 索引 | 標籤 | ||
|---|---|---|---|
| 1 | 1 | 2 | R |
| 2 | 2 | 1 | R |
| 3 | 4 | 4 | B |
| 4 | 5 | 3 | B |
| 5 | 3 | 5 | B |
| 6 | 2 | 3 | R |
查詢為 。我們使用 、歐氏距離及算法一節的約定。
第 1 步:距離。 對每個樣本,把特徵減去查詢,將每個差平方,把平方相加,再取平方根。
| 索引 | 距離平方 | 距離 | 標籤 | |
|---|---|---|---|---|
| 1 | (−2, −1) | 4 + 1 = 5 | R | |
| 2 | (−1, −2) | 1 + 4 = 5 | R | |
| 3 | (1, 1) | 1 + 1 = 2 | B | |
| 4 | (2, 0) | 4 + 0 = 4 | 2 | B |
| 5 | (0, 2) | 0 + 4 = 4 | 2 | B |
| 6 | (−1, 0) | 1 + 0 = 1 | 1 | R |
第 2 步:排序。 完整排列為:
6 (1), 3 (1.414), 4 (2), 5 (2), 1 (2.236), 2 (2.236)。
這裏有兩組距離平手。樣本 4 和 5 的距離都是 2,所以按索引規則 4 排在 5 之前。樣本 1 和 2 的距離都是 ,所以 1 排在 2 之前。
第 3 步:選取並投票。 最近的三個樣本是 6 (R)、3 (B) 和 4 (B)。票數為 B = 2,R = 1。
第 4 步:預測。 預測結果為 B。
第三個位置涉及平手:樣本 4 和 5 的距離都是 2,但在 之下只能容納其中一個。在此兩者的標籤都是 B,所以預測不受平手規則影響。但在一般情況下可能會受影響,這正是規則必須預先固定的原因。
在同一排序下改變 k,很有啟發性:
- : 只用到樣本 6,所以預測為 R。單一最接近的樣本是一個需要重新灌溉的個案。
- : 用到樣本 6、3、4、5 和 1(樣本 1 憑索引勝過樣本 2)。票數為 B = 3,R = 2,所以預測為 B。
預測在 與 之間改變了。兩個結果都不是計算錯誤,而是反映了不同程度的平滑。只有留出數據的證據才能提示哪個選擇對這類數據較為有效,而六個點遠遠不足以解答這個問題。
快速檢查
(沿用上面的泥土數據,取查詢 及 。所列規則預測甚麼?)
解答 · 答案
樣本 1 至 6 的距離平方為 。得票是 R (樣本 1、2、6)與 B ,投票平手。入選的 R 樣本中最近者的距離平方為 1,比 B 樣本中最近者的 8 更近,所以預測 R。
6. 特徵縮放如何改變距離
歐氏距離把各特徵的平方差相加,就好像每個特徵的一個單位都同等重要。當特徵以不同單位量度時,這很少成立。
例題 3.4.4
(原始距離與最小–最大縮放距離選出不同的鄰居)
考慮一個手機月費計劃數據集,它有兩個特徵:
- = 每月數據用量(MB);在訓練數據中,其範圍由 0 至 1000。
- = 致電客戶服務的次數;在訓練數據中,其範圍由 0 至 10。
使用以下完整的四名客戶訓練集及一個查詢:
| 點 | (MB) | (次數) | 標籤 |
|---|---|---|---|
| P | 180 | 1 | S(留下) |
| Q | 260 | 8 | T(離開) |
| U | 0 | 0 | S(留下) |
| V | 1000 | 10 | T(離開) |
| 查詢 | 200 | 8 | ? |
原始距離。
- 至 P:差為 (20, 7),所以 400 + 49 = 449,距離 。
- 至 Q:差為 (60, 0),所以 3600 + 0 = 3600,距離為 60。
- 至 U:距離平方 。
- 至 V:距離平方 。
四個訓練點都已檢查;當 時,預測為 S。在這裏,數據用量決定了結果:Q 的 60 MB 差距為其距離平方貢獻了 3,600,比 P 的整個距離平方 449 還要大。這個貢獻取決於兩個特徵所選用的單位。
最小–最大縮放後的距離。 用訓練數據的最小值和最大值重新縮放每個特徵,即 。在此即 變為 , 變為 。縮放後的點為 、 及查詢 。
- 至 P:差為 (0.02, 0.7),所以 0.0004 + 0.49 = 0.4904,距離 。
- 至 Q:差為 (0.06, 0),所以為 0.0036,距離為 0.06。
- U 和 V 分別縮放為 (0, 0) 和 (1, 1);兩者與查詢的距離平方都是 0.68。
在全部四個點之中,最近鄰是 Q,預測為 T。客戶本身沒有任何改變,改變的只是量度差距所用的單位。因此,縮放並非表面功夫:它是相似度定義的一部分。
快速檢查
(在手機月費計劃例子中,以表中次序作索引次序,求 時原始距離與最小–最大縮放後的預測。)
解答 · 答案
原始次序是 P、Q、U、V,所以鄰居 P(S)、Q(T)、U(S)給出 S。縮放後的距離平方是 Q 為 、P 為 ,U 與 V 都是 。索引規則取 U(S),得票為 S 、T ,預測 S。若改取 V,則會預測 T,所以這裏平手規則有影響。
兩種常見選擇是最小–最大縮放和標準化,。兩者各自隱含一個建模假設。例如,最小–最大縮放會給每個非常數特徵一個同樣大小的縮放區間。若某個擬合集的範圍或標準差為零,公式就會除以零:應預先訂立處理方針,例如在該擬合摺中捨棄該特徵,並把同一已擬合的方針應用於其驗證數據。被捨棄的特徵無法反映日後出現的變化。若領域知識指出某個特徵較為重要,應刻意地表達這一點,例如使用特徵權重,而不是任由單位的偶然選擇來決定。
7. 數據洩漏:只在訓練數據上擬合預處理
縮放有參數:最小值和最大值,或平均值和標準差。這些參數是從數據學習得來的,所以它們是已訓練模型的一部分。規則如下:
- 先把數據分為外層訓練部分和最終測試(留出)部分。
- 在外層訓練部分內作驗證分割時,只在擬合子集上擬合縮放器,然後原封不動地把它應用於該子集及其驗證子集。在交叉驗證中,對每一摺分別重複此步驟。每個候選 k 都必須不大於最小擬合摺中的樣本數目,使它在每一摺中都有效。
- 根據這些驗證結果選擇 k。在完整的外層訓練部分上重新擬合縮放器,然後把這個已擬合的縮放器原封不動地應用於最終測試集及日後的查詢。
常見錯誤
(在分割前於整個數據集上擬合縮放器)
假設你反而在分割之前,就在整個數據集上計算最小值和最大值。那麼測試點的資訊就已進入模型,因為測試點參與了決定如何量度距離。由此得出的測試準確度,不再衡量對真正未見過數據的表現,因為真正未見過的數據不可能影響縮放器。在個別情況下影響可大可小,但評估已不再誠實。
這有兩個實際後果。
- 測試值可能落在訓練範圍之外,使縮放值小於 0 或大於 1。這是正確的行為;不要為了修正它而重新擬合縮放器。
- 同一規則亦適用於選擇 k。如果你嘗試多個 k 值,並保留測試分數最好的那個,測試集就已被用於訓練。應在訓練數據內用驗證分割或交叉驗證來選擇 k,並在每一摺內重新擬合縮放器。然後在最後才使用測試集一次。
快速檢查
(縮放器在某個訓練特徵上擬合,最小值為 10,最大值為 50。縮放測試值 60 與訓練值 30。若重新擬合時包括該測試值,會有甚麼改變?)
解答 · 答案
縮放值是 與 。1.25 是合理的。若重新擬合時包括 60,範圍會變成 ,訓練值會移到 ,即測試數據改變了訓練點的幾何。
8. 訓練與預測的成本
計算模型。 我們假設以下各項:
- 在單一處理器上執行暴力式 kNN。
- 每個算術運算和每次比較各算一個單位。
- n 個訓練樣本、d 個特徵、k 個鄰居及 m 個查詢。
- 鄰居按歐氏距離平方排列,所以不取平方根。
訓練。 基本 kNN 只儲存數據。這需要 記憶體,而除了複製之外,基本上不需要計算。擬合最小–最大縮放器會增加兩項成本,所以擬合整體為 :
- 找出每個特徵的最小值和最大值,每個特徵約需 2(n − 1) 次比較。
- 變換已儲存的數據約需 2nd 個運算(每個值一次減法和一次除法)。
單一查詢的預測。 成本分為三部分。
- 距離。 一個距離平方需要 d 次減法、d 次乘法和 次加法,即 個運算。對所有訓練點而言,共 。
- 選取。 找出 k 個最小距離,用比較排序需 ,用有界堆積需 ,用適當的隨機化選取算法則需 期望時間。當索引平手規則有影響時,應比較
(distance, index)配對。 - 投票。 使用常數時間、以標籤為索引的計數器,點票需 ;同時記錄每個標籤最近的入選樣本,亦可支援所列明的投票平手規則。
命題 3.4.5
(暴力式預測成本)
在上述模型中,一個查詢計算距離平方需 個運算,用有界堆積選出 個最小者需 ,投票需 。每個查詢的總成本為 , 個查詢則為 。
證明
(把三個階段相加)
各階段依次進行,所以成本相加。 個樣本各需 個運算;由於 ,投票的 被其他項吸收。各查詢互相獨立,所以單一查詢的成本乘以 。
例題 3.4.6
(計算距離運算次數)
當 、 時,一個距離平方需 個運算,所以一個查詢需 個距離運算, 個查詢需 個。在邊界情況 時,一個距離平方是一次減法與一次乘法,即 個運算,一個查詢的次數為 。 的值不影響距離階段。
kNN 顛倒了一般的模式:訓練便宜而預測昂貴,因為每次預測都要重新掃描已儲存的數據。索引結構(k-d 樹、球樹)或近似搜尋可在低維度下降低預測成本。它們不屬於基本方法,而且隨著 d 增大,其效用可能下降,視乎數據和查詢而定。
9. 需要另訂規則的變體
上述方法使用不加權多數決投票。兩種常見變化會改變規則,必須另行列明。
- 距離加權投票。 每個鄰居的票會被加權,通常以 1/d 為權重。這需要為距離為 0 的鄰居(除以零)另訂約定,並為加權總和相等的情況另訂平手規則。加權結果可能與上述不加權結果不同,兩者不應混用。
- 類別不平衡。 當某一類別遠較常見時,它往往會主導鄰域,所以多數決投票可能很少預測出少數類別。可行做法包括類別特定權重、對訓練數據重新抽樣,或(對二元分類器而言)調整施加於正類別得票比例的閾值。每種補救方法都定義了一個不同的分類器,必須明確指明。
10. 局限
- 無關的特徵。 每個特徵都會貢獻於距離,所以雜訊特徵會沖淡有用的特徵。
- 高維度。 對某些分布和距離模型而言,隨著 d 增大,相對距離會趨於集中,使最近點與最遠點較難區分。這並非普遍成立:相關性和數據的幾何結構都有影響。
- 如上所述,只適用於數值特徵。 類別特徵需要編碼或使用另一種距離。
- 解釋能力有限。 kNN 可以顯示用了哪些樣本,但它不能精簡地概括特徵與標籤之間的關係。
11. 總結
對於一個固定的已標籤訓練集及上述所列明的不加權投票規則,kNN 透過找出最接近查詢的 k 個訓練樣本並進行投票來作出預測。另外四項選擇必須列明:
- 距離;
- 預處理;
- k 的值;
- 平手規則。
任何預處理都只可在訓練數據上擬合,而選擇 k 時亦不可觸碰測試集。便宜的訓練,是以昂貴的預測作為代價。