统计学习方法之k近邻法

统计学习方法之k近邻法

1. k近邻算法

$Input:$

$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为实例的特征向量$$y_i\in \mathcal{Y}=\left\{c_1,c_2,\cdots ,c_K\right\}为实例的别，i=1,2,\cdots ,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近邻法的结果产生重大影响

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

2.3 分类决策规则

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

分类函数为： $$f:R^n\to \{c_1,c_2,...,c_k\}$$

误分类概率： $$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)label05.13.51.40.2014.93.01.40.2024.73.21.30.2034.63.11.50.2045.03.61.40.20..................1456.73.05.22.321466.32.55.01.921476.53.05.22.021486.23.45.42.321495.93.05.11.82

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.])