统计学习方法之k近邻法

1. k近邻算法

$Input:$

• T={(x1,y1),(x2,y2),⋯ ,(xN,yN)}其中，xi∈X⊆Rn为实例的特征向量T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\} 其中， x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n} 为实例的特征向量T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}其中，xi​∈X⊆Rn为实例的特征向量
• yi∈Y={c1,c2,⋯ ,cK}为实例的别，i=1,2,⋯ ,Ny_{i} \in \mathcal{Y}=\left\{c_{1}, c_{2}, \cdots, c_{K}\right\} 为实例的别， i=1,2, \cdots, Nyi​∈Y={c1​,c2​,⋯,cK​}为实例的别，i=1,2,⋯,N
• $实例特征向量x$

$Output:$

• $实例x所属的类y$

$Algorithm:$

• 根据给定的距离度量，在训练集$T$中找出与$x$最近邻的$k$个点，涵盖这$k$个点的$x$的邻域记作$N_k(x)$
• 在$N_k(x)$中根据分类决策规则决定$x$的类别$y$

$$y=\arg \underset{c_j}{\max }\sum _{x_i\in N_k(x)}I\left(y_i=c_j\right),i=1,2,\cdots ,N;j=1,2,\cdots ,K$$

2. k近邻模型

2.1 距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。

• 闵可夫斯基距离距离：

$$L_p\left(x_i,x_j\right)={\left(\sum _{l=1}^n{\left|x_i^{(l)}-x_j^{(l)}\right|}^p\right)}^{\frac{1}{p}}$$

• 欧式距离：

$$L_{p2}\left(x_i,x_j\right)={\left(\sum _{l=1}^n{\left|x_i^{(l)}-x_j^{(l)}\right|}^2\right)}^{\frac{1}{2}}$$

• 曼哈顿距离：

$$L_1\left(x_i,x_j\right)=\sum _{l=1}^n\left|x_i^{(l)}-x_j^{(l)}\right|$$

• 切比雪夫距离：

$$L_{\infty }\left(x_i,x_j\right)=\underset{l}{\max }\left|x_i^{(l)}-x_j^{(l)}\right|$$

2.2 k值的选择

k值的选择会对k近邻法的结果产生重大影响

1. k值的减小就意味着整体模型变得复杂，容易发生过拟合。
2. k值的增大就意味着整体的模型变得简单，容易使预测发生错误。
3. 在应用中，一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值

2.3 分类决策规则

k近邻法中的分类决策规则一般为多数表决。

分类函数为：
f:Rn→{c1,c2,...,ck}f:R^n \rightarrow\{c_1,c_2,...,c_k\}f:Rn→{c1​,c2​,...,ck​}

误分类概率：
$$P(Y\ne f(X))=1-P(Y=f(X))$$

实例 $x\in \mathcal{X}$；最近邻的k个训练实例点构成集合$N_k(x)$。如果涵盖$N_k(x)$区域的类别为$c_j$，那么误分类率为:
$$\frac{1}{k}\sum _{x_i\in N_k(x)}I\left(y_i\ne c_j\right)=1-\frac{1}{k}\sum _{x_i\in N_k(x)}I\left(y_i=c_j\right)$$

要使误分类率最小即经验风险最小，就要使$\frac{1}{k}{\sum }_{x_i\in N_k(x)}I\left(y_i=c_j\right)$最大，也就是多数表决。

3. 算法实现

# 导入所需的库
import numpy as np 
import pandas as pd 
import matplotlib.pyplot as plt 

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# 加载数据
iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['label'] = iris.target

df

	sepal length (cm)	sepal width (cm)	petal length (cm)	petal width (cm)	label
0	5.1	3.5	1.4	0.2	0
1	4.9	3.0	1.4	0.2	0
2	4.7	3.2	1.3	0.2	0
3	4.6	3.1	1.5	0.2	0
4	5.0	3.6	1.4	0.2	0
...	...	...	...	...	...
145	6.7	3.0	5.2	2.3	2
146	6.3	2.5	5.0	1.9	2
147	6.5	3.0	5.2	2.0	2
148	6.2	3.4	5.4	2.3	2
149	5.9	3.0	5.1	1.8	2

150 rows × 5 columns

# 展示数据
x_idx = iris.feature_names[0]
y_idx = iris.feature_names[1]
plt.scatter(df[:50][x_idx], df[:50][y_idx], label='0')
plt.scatter(df[50:100][x_idx], df[50:100][y_idx], label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
plt.show()

# 准备数据
data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:,:-1], data[:,-1]
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

test_point = [[6, 3]]

plt.scatter(df[:50][x_idx], df[:50][y_idx], label='0')
plt.scatter(df[50:100][x_idx], df[50:100][y_idx], label='1')
plt.plot(test_point[0][0], test_point[0][1], 'bo', label='test_point')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend()
plt.show()

from sklearn.neighbors import KNeighborsClassifier

clf = KNeighborsClassifier()
clf.fit(X_train, y_train)

clf.predict(test_point)

array([1.])