k 近鄰法
1森瘪、K近鄰法定義
給定一個(gè)訓(xùn)練數(shù)據(jù)集，對(duì)于新輸入的實(shí)例渊涝，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例距離最近的K個(gè)實(shí)例，看這K個(gè)實(shí)例多數(shù)屬于某個(gè)類稳其，則將該實(shí)例分為這個(gè)類驶赏。
2.K近鄰法算法
2.1 k近鄰算法步驟
輸入：數(shù)據(jù)集,其中
,
,
;實(shí)例特征向量
輸出：實(shí)例所屬的類
步驟：
(1)根據(jù)給定的距離度量，在訓(xùn)練集中找出與
最近鄰的K個(gè)點(diǎn)既鞠，涵蓋著K個(gè)點(diǎn)的x的鄰域記作
;
(2)在中煤傍，根據(jù)分類決策規(guī)則（例如多數(shù)表決）決定
所屬于的類別
：
其中為指示函數(shù)，即當(dāng)
時(shí)嘱蛋，
為1蚯姆，否則
為0。
K近鄰算法沒有顯示的學(xué)習(xí)過程洒敏。k近鄰法的特殊情況是K=1的情形龄恋，稱為最近鄰算法。
2.2實(shí)現(xiàn)
import numpy as np
# 1.數(shù)據(jù)集（擴(kuò)充perceptron中的數(shù)據(jù)）,6個(gè)正例凶伙，3個(gè)負(fù)例
data_coord = np.asarray(((3, 3), (4, 3), (5, 5), (4.5), (5, 4), (3, 5),
(1, 1), (0.0), (1, -1)))
data_label = np.asarray((1, 1, 1, 1, 1, 1,
-1, -1, -1))
# 2.測(cè)試數(shù)據(jù)
test_data = np.asarray((0.3,0.4))
K = 2
# 計(jì)算兩點(diǎn)的距離（兩個(gè)向量）
def get_dis(a,b):
return np.linalg.norm(a - b)
# knn
def knn(test_data, train_data,train_label, K):
max_distance = np.Inf
# test_data k個(gè)鄰居的距離
knn_list = list((max_distance-i) for i in range(K))
# test_data k個(gè)鄰居,的下標(biāo)
label_list = list(-1 for i in range(K))
label = 0
for i in range(len(train_label)):
vec_train = train_data[i]
label_train = train_label[i]
# 計(jì)算train集合中郭毕，每個(gè)點(diǎn)與test_data的距離
test_train_dist = get_dis(test_data, vec_train)
curr_max_knn = np.argmax(knn_list)
curr_max_dist = knn_list[curr_max_knn]
# 找到train集合中，跟test_data距離最近的K個(gè)點(diǎn)
if test_train_dist < curr_max_dist:
knn_list[curr_max_knn] = curr_max_dist
label_list[curr_max_knn] = label_train
# 在knn_list中函荣，“投票表決”
print("label_list = ",label_list)
outcome = np.sum(label_list)
if outcome > 0:
label = 1
elif outcome < 0:
label = -1
print("label = ",label)
return label;
# run it
knn(test_data = test_data,train_data=data_coord,train_label=data_label,K=K)
結(jié)果：test_data屬于-1類
參考與致謝：
[1]《統(tǒng)計(jì)學(xué)習(xí)方法》
[2] WenDesi/lihang_book_algorithm
