k 近邻法

1、K近邻法定义

给定一个训练数据集，对于新输入的实例，在训练数据集中找到与该实例距离最近的K个实例，看这K个实例多数属于某个类，则将该实例分为这个类。

2.K近邻法算法

2.1 k近邻算法步骤

输入：数据集 $T=\lbrace (x_1,y_1),(x_2,y_2),...,(x_N,y_N) \rbrace$ ,其中 $x_i \in X \subseteq R^n$ , $y \in Y = \lbrace c_1,c_2,...,c_K \rbrace$ , $i=1,2,..,N$ ;实例特征向量 $x$
输出：实例 $s$ 所属的类 $y$
步骤：
(1)根据给定的距离度量，在训练集 $T$ 中找出与 $x$ 最近邻的K个点，涵盖着K个点的x的邻域记作 $N_k(x)$ ;
(2)在 $N_k(x)$ 中，根据分类决策规则（例如多数表决）决定 $x$ 所属于的类别 $y$ ：
$y = argmax_{c_j} \sum_{x_i \in N_k(x)} I(y_i = c_i),i=1,2,...,N;j=1,2,..,K$
其中 $I$ 为指示函数，即当 $y_i=c_j$ 时， $I$ 为1，否则 $I$ 为0。
K近邻算法没有显示的学习过程。k近邻法的特殊情况是K=1的情形，称为最近邻算法。

2.2实现

import numpy as np

# 1.数据集（扩充perceptron中的数据）,6个正例，3个负例
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.测试数据
test_data = np.asarray((0.3,0.4))
K = 2

# 计算两点的距离（两个向量）
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个邻居的距离
    knn_list = list((max_distance-i) for i in range(K))
    # test_data k个邻居,的下标
    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]
        # 计算train集合中，每个点与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个点
        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)

结果：test_data属于-1类

参考与致谢：
[1]《统计学习方法》
[2] WenDesi/lihang_book_algorithm