Catalog
  1. 1. KNN算法
  2. 2. KNN模型
    1. 2.1 距离度量
    2. 2.2 $k$值的选择
    3. 2.3 分类决策规则
  3. 3. KNN的实现:kd树
  4. 4. 实现
    1. *Distinguish: KNN和Kmeans
《统计学习方法》(CH03 KNN)

1. KNN算法

$k$近邻法$(k-nearest neighbor, k-NN)$ 是一种基本分类与回归方法

2. KNN模型

三个基本要素:距离度量、k值(点数)的选择和分类决策规则

模型示意,距离度量,每个训练的实例点与距离它更近的所有点组成一个单元(cell):

003 knn

2.1 距离度量

设特征空间X是n维实数向量空间$R^n$ , $x_i, x_j$的$L_p$距离定义为

$$L_p(x_i, x_j)=\left(\sum_{l=1}^{n}{\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^p}\right)^{\frac{1}{p}}$$

  • $p=1$ 对应 曼哈顿距离
  • $p=2$ 对应 欧氏距离
  • 任意$p$ 对应 闵可夫斯基距离

如图所示:

004 距离

2.2 $k$值的选择

  • 如果选择较小的$k$值,
  • 如果选择较大的$k$值
  • 如果$k = N$

TIPS:在应用中k值一般选择比较小的数

2.3 分类决策规则

Majority Voting Rule

误分类率

$\frac{1}{k}\sum_{x_i\in N_k(x)}{I(y_i\ne c_i)}=1-\frac{1}{k}\sum_{x_i\in N_k(x)}{I(y_i= c_i)}$

如果分类损失函数是0-1损失,误分类率最低即经验风险最小。

3. KNN的实现:kd树

  • 用kd树的最近邻搜索

  • 给定一个范围,问其中有多少点。比较常见的应用是GIS类应用,使用者附近多大半径内包含多少单车,多少酒店等。

    实际上为了实现快速搜索, 在空间数据的存储结构上要有考虑。

4. 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from sklearn import datasets # 提供样本数据,iris
from collections import Counter # 为了做投票,选择距离最短的N个样本
from sklearn.model_selection import train_test_split
import numpy as np

# 导入iris数据

iris = datasets.load_iris()
X = iris.data #特征
y = iris.target #标签
# 分成训练集、测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=2003)

# 欧式距离
def euc_dis(instance1, instance2):
"""
计算两个样本instance1和instance2之间的欧式距离
instance1: 第一个样本, array型
instance2: 第二个样本, array型
"""
# TODO
dist = np.sqrt(sum((instance1 - instance2)**2))
return dist


def knn_classify(X, y, testInstance, k):
# distances测试样本和所有样本的距离
distances = [euc_dis(x, testInstance) for x in X]
# 所有距离排序
kneighbors = np.argsort(distances)[:k]
# 如果选择k=4,则统计前4个样本出现最多的标签
count = Counter(y[kneighbors])
return count.most_common()[0][0]

# 预测结果,k=3时
predictions = [knn_classify(X_train, y_train, data, 3) for data in X_test]
correct = np.count_nonzero((predictions==y_test)==True)
print ("k=3时,Accuracy is: %.3f" %(correct/len(X_test)))
k=3时,Accuracy is: 0.921
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from sklearn.model_selection  import cross_val_score
import matplotlib.pyplot as plt
k_range = range(1, 31)
k_error = []
#循环,取k=1到k=31,查看误差效果
for k in k_range:
predictions = [knn_classify(X_train, y_train, data, k) for data in X_test]
correct = np.count_nonzero((predictions==y_test)==True)
k_error.append(1 - correct/len(X_test))

#画图,x轴为k值,y值为误差值
plt.plot(k_range, k_error)
plt.xlabel('Value of K for KNN')
plt.ylabel('Error')
plt.show()

![png](/images/统计学习方法三/001 k值.png)

可以看出K值取多少的时候误差最小

1
2
3
4
5
import matplotlib.pyplot as plt

plt.figure(figsize=(6, 4))
plt.scatter(X_test[:,0], X_test[:,2], c=predictions)
plt.savefig("KNN.png")

![png](/images/统计学习方法三/002 画图.png)

*Distinguish: KNN和Kmeans

相同:

  • K值都是重点
  • 都需要计算平面中点的距离

相异:

  • KNN的最终目的是分类,有监督学习,
  • Kmeans的目的是给所有距离相近的点分配一个类别,也就是聚类,无监督学习。

简单说,就是画一个圈,KNN是让进来圈子里的人变成自己人,Kmeans是让原本在圈内的人归成一类人。

Donate
  • 微信
  • 支付寶

Comment