<center>
<img src = "https://i.imgur.com/AnodR5I.jpg">
</center>

## Prerequisite

$k$ nearest neighbors (KNN) 採用向量空間模型來分類，具有相同類別的案例，彼此的相似度高，可以藉由計算與已知類別案例之相似度，來預測未知類別案例可能的分類。

### Eigenvector / Eigenvalue

在線性代數中，對於一個方形矩陣 $A$，其特徵向量 (Eigenvector) $v$ 經過線性轉換後，其得到的新向量與原先 $v$ 保持同一直線上

$Av=\lambda v$，其中 $\lambda$ 為純量，即特徵向量的長度在該線性轉換下縮放的比例，$\lambda$ 也稱為特徵值 (Eigenvalue)

以下影片有更詳細介紹

<iframe width="100%" height="400" src="https://www.youtube.com/embed/PFDu9oVAE-g?si=2QDc5KEfk-ZZnSyj" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>

### Euclidean distance

歐幾里得空間中兩點之間的歐幾里得距離是指連接這兩點的線段的長度，歐幾里得空間可以被擴展來應用於任何有限維度，而這種空間叫做 $n$ 維歐幾里得空間。

而如何計算歐幾里得距離，這裡先假設 $n$ 維點，點 $x = (x_1, \dots, x_n)$ 和 $y = (y_1, \dots, y_n)$，而其歐氏距離為

$$
d(x, y) = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + \dots + (x_n - y_n)^2}
$$

### Hamming distance

一般情況下，距離度量會使用歐氏距離，但是這只適用於連續變數。

在離散變數情況下，Hamming distance 可以用來作為度量。

兩個等長字符串之間的 Hamming distance 是兩個字符串對應位置的不同字符的個數。

<style>
.red {
color: red;
}
</style>

<p>Ex: 10<span class="red">1</span>1<span class="red">1</span>01 和 10<span class="red">0</span>1<span class="red">0</span>01 之間的 Hamming distance 是 2</p>

換句話說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。

## Goal

透過 KNN，我們可以藉由實例的學習，或者是局部近似和將所有計算推遲到分類之後。

## Background

### Algorithm

在訓練階段時，我們將每個範例加入到 Training list 中，範例可以 $x$ 和 $x$ 的類別被表示

在進行分類任務時，我們可以觀察到所有 class $V$，$V = \{ v_1, \dots, v_l \}$

接著若我們要預測的範例 $x_q$ 要被分類時，我們必須執行以下步驟：
- 藉由超參數 $k$，我們將計算鄰近 $k$ 個範例中，所有 $X = \{ x_1, \dots, x_k \}$ 跟其接近的範例
- 根據這 $k$ 個範例，我們會以投票的方式給予這 $\forall i : 1, \dots, l$ 的類別投票，$vote = \{ x \in X \mid class(x) = v_i \}$
- 回傳最多票的類別 $v_i$

> :bulb: **如何取 $k$ ?**
> 如何選擇一個最佳的 $k$ 值取決於資料。
> 一般情況下，在分類時較大的 $k$ 值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。
> 在二元（兩類）分類問題中，選取 $k$ 為奇數有助於避免兩個分類平票的情形。

### 改進現有 KNN

**距離加權 KNN**

對於每個範例，我們給予它一個權重 $w_{ni}$，其中 $\sum_{i=1}^n w_{ni} = 1$

最常見的方法是使用距離的倒數作為權重，即 $w_{ni} = \frac{1}{{d_i}}$，其中 $d_i$ 是第 $i$ 個最近鄰的距離。

距離加權 KNN 是 KNN 的一個強大變體，可以更好地處理不同鄰居對預測的貢獻，並在某些情況下提高模型的性能。

但它也需要謹慎的調參和權重計算來實現最佳結果。

## Implementation

[KNN From Scratch](https://www.kaggle.com/code/fareselmenshawii/knn-from-scratch)

## From Scratch

## More example

[Spaceship Titanic](https://www.kaggle.com/competitions/spaceship-titanic/overview)

Code [titanic-better-imputation-with-knn](https://www.kaggle.com/code/danb91/titanic-better-imputation-with-knn)

## Reference

歡迎更仔細閱讀以下相關內容以了解本篇知識

- [K-近鄰演算法](https://zh.wikipedia.org/wiki/K-%E8%BF%91%E9%82%BB%E7%AE%97%E6%B3%95)
- [特徵值和特徵向量](https://zh.wikipedia.org/zh-tw/%E7%89%B9%E5%BE%81%E5%80%BC%E5%92%8C%E7%89%B9%E5%BE%81%E5%90%91%E9%87%8F)
- [机器学习算法之——K最近邻(k-Nearest Neighbor，KNN)分类算法原理讲解](https://zhuanlan.zhihu.com/p/110913279)