KNN 簡明教程

【導讀】本文是 Devin Soni 撰寫的博文，主要介紹 k - 近鄰算法（KNN）的工作原理和常見應用。KNN 可以說是機器學習算法中最普遍、最簡單的分類方法了，其擁有思想簡單、易於實現等優點，但是也存在若干缺點，如需要計算量大、耗費計算資源等。因此 KNN 適用於小樣本分類任務。本文簡明扼要地介紹了 KNN 的原理和若干要點，相信對於機器學習初學者能有幫助。

Introduction to k-Nearest-Neighbors

KNN 簡介

k - 最近鄰（kNN）分類方法是機器學習中最簡單的算法之一，並且是機器學習和分類入門的算法之一。最基本的，它是通過在訓練數據中找到最相似的數據點進行分類，並根據他們的分類做出有根據的猜測。雖然 KNN 理解和實現起來非常簡單，但是這種方法在很多領域都有廣泛的應用，例如推薦系統，語義搜索和異常檢測。

正如我們在其他機器學習問題中需要的那樣，我們必須首先找到一種將數據點表示爲特徵向量的方法。特徵向量是我們對數據的數學表示，並且由於我們的數據的期望特徵可能不是固有數值，因此可能需要預處理和特徵工程來構建這些向量。給定具有 N 個特徵的數據，特徵向量將是長度爲 N 的向量，其中向量的入口 I 代表特徵 I 的數據點值。因此，每個特徵向量可以被認爲是 R ^ N 中的點。

現在，與大多數其他分類方法不同，kNN 屬於惰性學習，這意味着在分類之前沒有明確的訓練階段。相反，任何對數據進行概括或抽象的嘗試都是在分類時進行的。雖然這確實意味着我們可以立即開始分類，但是這種類型的算法存在一些固有的問題。我們必須能夠將整個訓練集保存在內存中，除非我們利用某種方法對數據集進行一定的減少，並且執行分類可能在需要耗費巨大的計算量，因爲算法需要通過每個分類的所有數據點進行解析。因此，kNN 往往適用於特徵不多的小型數據集。

一旦我們形成了我們的訓練數據集，表示爲 M×N 矩陣，其中 M 是數據點的數量，N 是特徵的數量，我們現在可以開始分類。對於每個分類，kNN 方法的要點是：

• 計算要分類的樣本與訓練數據集中的每個樣本之間的距離值

• 選取 k 個最近的數據點（k 個最低距離的項目）

• 在這些數據點之間進行 “多數投票” - 該樣本範圍中的主要類別被確定爲最終分類。

在進行分類前必須確定兩個超參數的值。一個是將要使用的 k 的值; 這可以任意決定，也可以嘗試交叉驗證以找到最佳值。接下來也是最複雜的是將要使用的距離度量。

有很多不同的方法來計算距離，因爲它是一個相當模糊的概念，並且最好的距離計算方式總是由數據集和分類任務決定。兩種比較流行的是歐幾里得距離和餘弦相似性。

歐幾里得距離最廣爲人知; 它通過從待分類點減去訓練數據點而得到向量。

另一個常用指標是餘弦相似度。餘弦相似性使用兩個向量之間的方向差來計算量值。

選擇度量標準通常會非常棘手，最好使用交叉驗證來決定，除非您有一些先前的知識能清楚地瞭解一種肯定比另一種好。例如，對於詞向量，您可能會使用餘弦相似度，因爲詞的方向比分量值的大小更有意義。一般來說，這兩種方法的運行時間所差無幾，並且都會受到高維數據的影響。

在完成上述所有步驟並確定度量之後，kNN 算法的結果是將 R ^ N 劃分爲多個部分的決策邊界。每個部分（在下面明顯着色）表示分類問題中的一個類。邊界不需要與實際的訓練樣例一起形成 - 而是使用距離度量和可用的訓練點來計算邊界。通過在（小）塊中取 R ^ N，我們可以計算出該區域內假設數據點的最可能類別，因此我們將該塊標記爲該類的區域。

這個信息是實現算法必需的，這樣做應該相對簡單。當然，有很多方法可以改進這個基本算法。常見的修改包括加權、特定的預處理，以減少計算和減少噪聲，例如各種算法的特徵提取和減少尺寸。

此外，kNN 方法也被用於迴歸任務，雖然不太常見，它的操作方式與分類器非常相似。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/xrLc0O239TCBPaS1ze0F-w