前言
本文旨在學(xué)習(xí)和記錄，如需轉(zhuǎn)載，請(qǐng)附出處http://www.itdecent.cn/p/ea566512b04f
KNN
原理
K近鄰(K-nearest neighbor) 是一種基本的分類(lèi)和回歸的算法，在cs231中只介紹了分類(lèi)算法。KNN分類(lèi)算法的思想：給定一批帶標(biāo)簽的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，在對(duì)未知標(biāo)簽的數(shù)據(jù)進(jìn)行分類(lèi)時(shí)，根據(jù)其K個(gè)最近鄰訓(xùn)練數(shù)據(jù)的標(biāo)簽，采取多數(shù)表決的方法進(jìn)行預(yù)測(cè)。KNN中訓(xùn)練不花時(shí)間，預(yù)測(cè)時(shí)需要采取特定的距離的度量方式來(lái)進(jìn)行最近鄰的尋找，如果待預(yù)測(cè)的樣本很多，其預(yù)測(cè)時(shí)間也會(huì)相應(yīng)的增加。
距離度量
距離度量一般采取Minkowski距離，其公式為：
- 當(dāng)p = 2時(shí)，就是我們常用的歐式距離；
- 當(dāng)p = 1時(shí)，就是曼哈頓距離；
- 當(dāng)p=
時(shí)，該距離就表示為各個(gè)坐標(biāo)系中最大的距離：
當(dāng)然，還有許多距離，比如遙感應(yīng)用中的光譜角距離，這里就不一一介紹了。
K值的選擇
- 如果K值很?。ㄗ钚?），這種預(yù)測(cè)只在一個(gè)很小的領(lǐng)域中進(jìn)行預(yù)測(cè)，會(huì)很大程度的依賴近鄰點(diǎn)，這在深度學(xué)習(xí)中表現(xiàn)就是容易過(guò)擬合，K值太小模型太復(fù)雜；
- 如果K值很大（最大為訓(xùn)練集的數(shù)目），這是不可取的，忽略了大量有用的信息，容易預(yù)測(cè)錯(cuò)誤，模型過(guò)于簡(jiǎn)單。
所以K值需要精心調(diào)節(jié)選取。 -
在cs231實(shí)驗(yàn)中，采用了X折交叉驗(yàn)證的方法來(lái)選擇K值；
其做法是將訓(xùn)練集切成X份，每次拿一份來(lái)驗(yàn)證，剩下的X-1份組成新的訓(xùn)練集，這樣就會(huì)存在X組不同的情況，然后再選擇幾個(gè)K值（比如1，3，5，7，9等）；通過(guò)計(jì)算每一個(gè)K值下X組不同情況下的驗(yàn)證集的精度的均值，來(lái)尋找最優(yōu)的K值。
cs231實(shí)驗(yàn)
cs231實(shí)驗(yàn)中選擇的數(shù)據(jù)為cifar10數(shù)據(jù)。
距離矩陣計(jì)算
實(shí)驗(yàn)中介紹了計(jì)算距離矩陣的幾種方法，two-loop,one-loop, no-loop(該方法采取矩陣向量的操作)，這里只介紹no-loop的代碼：
X_test_2 = np.square(X).sum(axis = 1)
X_train_2 = np.square(self.X_train).sum(axis = 1)
dists = np.sqrt(-2*np.dot(X,self.X_train.T)+X_train_2+np.matrix(X_test_2).T)###(5000,) and (500,1) broadcast
# print(dists.shape)
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
return np.array(dists)
注意：這里采取的numpy中加法的broadcast機(jī)制
Two loop version took 146.657845 seconds
One loop version took 89.948750 seconds
No loop version took 1.911102 seconds
no-loop計(jì)算距離矩陣的效率明顯高于loop！
KNN預(yù)測(cè)
def predict_labels(self, dists, k=1):
num_test = dists.shape[0]
y_pred = np.zeros(num_test)
for i in range(num_test):
closest_y = []
closest_y = self.y_train[np.argsort(dists[i,:])[:k]]# 排序
if np.shape(np.shape(closest_y))[0] !=1:
closest_y=np.squeeze(closest_y)
y_pred[i] = np.argmax(np.bincount(closest_y)) # 計(jì)數(shù)找出次數(shù)最多的標(biāo)簽
return y_pred
交叉驗(yàn)證
num_folds = 5
X_train_folds = np.array_split(X_train,num_folds)
y_train_folds = np.array_split(y_train,num_folds)
for k in k_choices:#find the best k-value
for i in range(num_folds):
X_train_cv = np.vstack(X_train_folds[:i]+X_train_folds[i+1:])
X_test_cv = X_train_folds[i]
y_train_cv = np.hstack(y_train_folds[:i]+y_train_folds[i+1:])
y_test_cv = y_train_folds[i]
# print(y_train_cv)
classifier.train(X_train_cv, y_train_cv)
dists_cv = classifier.compute_distances_no_loops(X_test_cv)
y_test_cv_pred = classifier.predict_labels(dists_cv, k)
num_correct = np.sum(y_test_cv_pred == y_test_cv)
accuracy = float(num_correct) / y_test_cv.shape[0]
# print(accuracy)
k_to_accuracies[k].append(accuracy)
參考
cs231課件
.
