统计学习方法笔记(一)-k近邻算法原理及python实现

输入：训练集
$$T={(x_1,y_1),(x_2,y_2),...,(x_N,y_N)}$$
其中,$x_iin mathcal {X} subseteq mathcal{R^n}$为实例的特征向量,$y_i in mathcal {Y}={c_1,c_2,...,c_K}$为实例的类别，$i=1,2,...,N$;实例特征向量$x$;

输出：实例$x$所属的类$y$.
(1)根据给定的距离度量，在训练集$T$中找出与$x$最邻近的$k$个点,涵盖这$k$个点的$x$的邻域基座$N_k(x)$;
(2)在$N_k(x)$中根据分类决策规则(如多数表决）决定$x$的类别$y$:
$$y=arg max_{cj} sum_{x_i in N_k(x)} I(y_i=c_i),i=1,2,...,N;j=1,2,...,K$$

上式中，$I$为指数函数，即当$y_i=c_i$时$I$为1,否则$I$为0.

注：当$k=1$时，$k$近邻法又称为最近邻算法，它是$k$近邻算法的特殊情况。

import math
from itertools import combinations

#定义距离
def Distance(x,y,p=2):
    if len(x)==len(y) and len(x)>1:
        sum=0
        for i in range(len(x)):
            sum+=math.pow(abs(x[i]-y[i]),p)
        return math.pow(sum,1/p)
    else:
        return 0