以下均為自己看視訊做的筆記，自用，侵删！
K最近鄰(k-Nearest Neighbor，KNN)分類算法，該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數屬于某一個類别，則該樣本也屬于這個類别。
K-近鄰算法步驟：
對于未知類别屬性資料集中的點：
- 計算已知類别資料集中的點與目前點的距離
- 按照距離依次排序
- 選取與目前點距離最小的K個點
- 确定前K個點所在類别的出現機率
- 傳回前K個點出現頻率最高的類别作為目前點預測分類。
概述：
- KNN 算法本身簡單有效，它是一種 lazy-learning 算法。
- 分類器不需要使用訓練集進行訓練，訓練時間複雜度為0。
- KNN 分類的計算複雜度和訓練集中的文檔數目成正比，也就是說，如果訓練集中文檔總數為 n，那麼 KNN 的分類時間複雜度為O(n)。
K 值的選擇，距離度量和分類決策規則是該算法的三個基本要素。
問題 該算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導緻當輸入一個新樣本時，該樣本的 K 個鄰居中大容量類的樣本占多數。
解決 不同的樣本給予不同權重項
如何計算：
結果 利用K-近鄰（距離為矩陣差異值累加和），不理想。
最近鄰代碼：
import numpy as np
class NearestNeighbor(object):
def __init__(self):
pass
def train(self, X, y):
#X是NXD的數組，其中每一行代表一個樣本，Y是N行的一維數組，對應X的标簽
# 最近鄰分類器就是簡單的記住所有的資料
self.Xtr = X
self.ytr = y
def predict(self, X):
#X是NXD的數組，其中每一行代表一個圖檔樣本
#看一下測試資料有多少行
num_test = X.shape[0]
# 确認輸出的結果類型符合輸入的類型
Ypred = np.zeros(num_test, dtype = self.ytr.dtype)
# 循環每一行，也就是每一個樣本
for i in xrange(num_test):
# 找到和第i個測試圖檔距離最近的訓練圖檔
# 計算他們的L1距離
distances = np.sum(np.abs(self.Xtr - X[i,:]), axis = 1)
min_index = np.argmin(distances) # 拿到最小那個距離的索引
Ypred[i] = self.ytr[min_index] # 預測樣本的标簽，其實就是跟他最近的訓練資料樣本的标簽
return Ypred
上一個是用L1：曼哈頓距離，絕對值裡兩個樣本相減, L2：計算歐氏距離
distances = np.sqrt(np.sum(np.square(self.Xtr - X[i,:]), axis = 1))
超參數的選取
問題：
1.對于距離如何設定？
2.對于K近鄰的K該如何選擇？
3.如果有的話，其它的超參數該怎麼設定呢？
測試集非常寶貴，隻能最終的時候才能使用（所有模型的參數都确定下來之後）。（不能每次訓練完之後，用測試集來調一下參數）
# 假設我們之前有 Xtr_rows, Ytr, Xte_rows, Yte 這幾份資料
# Xtr_rows 是 50,000 x 3072 的矩陣
Xval_rows = Xtr_rows[:1000, :] # 抽取前1000張作為評估集
Yval = Ytr[:1000]
Xtr_rows = Xtr_rows[1000:, :] # 其餘的4900張作為訓練集
Ytr = Ytr[1000:]
# 找到在評估集上表現做好的超參數
validation_accuracies = []
for k in [1, 3, 5, 10, 20, 50, 100]:
# 使用确定的k值作用在評估集上
nn = NearestNeighbor()
nn.train(Xtr_rows, Ytr)
# 這裡假設我們有一個最近鄰的類，可以把k值作為輸入
Yval_predict = nn.predict(Xval_rows, k = k)
acc = np.mean(Yval_predict == Yval)
print 'accuracy: %f' % (acc,)
# 記錄在評估集上每個k對應的準确率
validation_accuracies.append((k, acc))
交差驗證
（将訓練集再分成兩部分：一部分當作訓練集，另一部分當作驗證集，測試集最後用！），通過5次疊代的結果求平均，交差驗證可以消除一些偏高或偏低的結果。
不同交差驗證次數，得到的結果：
背景主導：
因為背景的作用，導緻圖像分類的不準确，是以我們不能用K-近鄰來完成圖像分類。因為不同的變化和原圖具有相同的L2距離。
使用K-近鄰：
- 選取超參數調優的正确方法是：将原始訓練集分為 訓練集和 驗證集 ，我們在驗證集上嘗試不同的超參數，最後保留表現最好那個。
- 如果訓練資料量不夠： 使用交叉驗證 交叉驗證方法，它能幫助我們在選取最優超參數的時候減少噪音。
- 一旦找到最優的超參數： 就讓算法以該參數在測試集跑且隻跑一次，并根據測試結果評價算法。
- 最近鄰分類器能夠在CIFAR-10上得到将近40%的準确率。該算法簡單易實作，但需要存儲所有訓練資料，并且在測試的時候過于耗費計算能力。
- 最後，我們知道了僅僅使用L1和L2範數來進行像素比較是不夠的，圖像更多的是按照背景和顔色被分類，而不是語義主體分身。
使用注意：
- 預處理你的資料：對你資料中的 特征進行歸一化（normalize），讓其具有 零平均值（zero mean）和 機關方差（unit variance）。
- 如果資料是高維資料，考慮使用降維方法，比如PCA。
- 将資料随機分入訓練集和驗證集。按照一般規律，70%-90% 資料作為訓練集。
- 在驗證集上調優，嘗試足夠多的k值，嘗試L1和L2兩種範數計算方式。
本文參考：https://www.cnblogs.com/douzujun/p/9035923.html