k-近邻法
k-近邻算法
k-近邻法 (k-nearest neighbor, k-NN) 是一种基本分类与回归方法. k-近邻不具有显示的学习过程, 实际上是利用训练数据集对特征向量空间进行划分, 并作为其分类的模型. 算法步骤如下 :
- 输入 : 训练数据集 \(T = \{ (\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \cdots, (\mathbf{x}_N, y_N) \}\), 其中 \(\mathbf{x}_i \in \mathcal{X} \subset \mathbb{R}^n\) 为训练集实例的特征向量, \(y_i \in \mathcal{Y} = \{ c_1, c_2, \cdots, c_K \}\) 为训练集实例的类别, \(i = 1, 2, \cdots, N\); 实例特征向量 \(\mathbf{x}\).
- 输出 : 实例 \(\mathbf{x}\) 所属的类别 \(y\).
- 根据给定的距离度量, 在训练集 \(T\) 中找出与 \(\mathbf{x}\) 距离最邻近的 \(k\) 个点, 涵盖这 \(k\) 个点的 \(\mathbf{x}\) 的邻域记作 \(N_k(x)\).
- 在 \(N_k(x)\) 中根据分类决策规则 (如多数表决) 决定 \(\mathbf{x}\) 的类别 \(y\) :
\[y = \arg \max_{c_j} \sum _{\mathbf{x}_i \in N_k(\mathbf{x})} I(y_i = c_j), \ i = 1,2,\cdots, N; \ j = 1,2,\cdots, K
\]
其中 \(I\) 为指示函数. 分类决策规则的含义是 : 对于每个样本实例 \(\mathbf{x}\), 找出离样本最近的 \(k\) 个点, 其类别预测为这里面有最多类别数的类别.
KNN 做分类预测时一般选择多数表决法, 即将样本类别预测为训练集里离该样本点最近的 \(k\) 个点中拥有最多数目的类别. 而 KNN 做回归时, 一般选择平均法, 即将最近的 \(k\) 个样本的平均值作为回归预测值.
k-近邻法的特殊情况是 \(k=1\) 的情况, 称为最近邻算法. 对于输入的实例的特征向量 \(\mathbf{x}\), 最近邻法将训练集中与 \(\mathbf{x}\) 最近邻点的类作为 \(\mathbf{x}\) 的类.
注意最近邻算法中, 对于训练集中的每一个实例, 将距离该点比其他点更近的所有点组成一个区域, 称为单元 (cell), 可以表示为一个 Voronoi 图. 对于样本集 \(\{ \mathbf{x}_1,, \mathbf{x}_2, \cdots, \mathbf{x}_N \}\), 它的 Voronoi 区域 \(R_k\) 定义为 :
\[R_k = \{ \mathbf{x} \in X | d(\mathbf{x}, \mathbf{x}_i) < d(\mathbf{x}, \mathbf{x}_j), \ j = 0,1,\cdots,N, \ j \neq i \}
\]
k 值的选择
在应用中一般根据样本的分布, 选择一个较小的值, 然后通过交叉验证选择一个合适的 \(k\) 值. \(k\) 值的选择会对 \(k\) 近邻法的结果产生重大影响.
- 选择较小的 \(k\) 值, 就相当于用较小的邻域中的训练实例进行预测, 训练误差会减小, 只有与输入实例较近或相似的训练实例才会对预测结果起作用, 与此同时带来的问题是泛化误差会增大. 预测结果对近邻的实例点非常敏感, 例如是噪声预测就会出错, \(k\) 值的减小就意味着整体的模型变得复杂, 容易发生过拟合.
- 选择较大的 \(k\) 值, 就相当于用较大邻域中的训练实例进行预测, 其优点是可以减少泛化误差, 但缺点是训练误差会增大. 这时与输入实例较远 (不同类) 的训练实例也会对预测起作用, 使预测发生错误. \(k\) 值的增大就意味着整体的模型变得简单, 容易发生欠拟合. 一个极端是 \(k\) 等于样本数 \(N\), 则完全没有分类, 此时无论输入实例是什么, 都只是简单的预测它属于在训练实例中最多的类, 模型过于简单.
分类决策规则
\(k\) 近邻法中的分类决策规则一般是多数表决, 多数表决 (majority voting rate) 有如下解释 : 如果分类的损失函数为 0-1 损失函数, 分类函数为
\[f: \mathbb{R}^n \rightarrow \{c_1, c_2, \cdots, c_K\}
\]
那么误分类概率为
\[P(Y \neq f(X)) = 1 - P(Y = f(X))
\]
对于给定的实例 \(\mathbf{x} \in \mathcal{X}\), 其最近邻的 \(k\) 个训练实例点构成集合 \(N_k(x)\), 若涵盖 \(N_k(\mathbf{x})\) 区域的类别是 \(c_j\) (由此得到实例 \(\mathbf{x}\) 的类别也是 \(c_j\)), 那么误分类率为 :
\[\frac{1}{k} \sum _{\mathbf{x}_i \in N_k(\mathbf{x})} I(y_i \neq c_j) = 1 - \frac{1}{k} \sum _{\mathbf{x}_i \in N_k(\mathbf{x})} I(y_i = c_j)
\]
误分类率最小即经验风险最小, 等价于 \(\sum _{\mathbf{x}_i \in N_k(\mathbf{x})} I(y_i = c_j)\) 最大 (多数表决规则).
kd 树实现 k-近邻算法
首先定义 kd 树的节点 :
# -*- coding: utf-8 -*-
class Node:
def __init__(self, point: List[int], axis: int,
left: "Node" = None, right: "Node" = None):
"""
:param point: 该节点保存的样本点特征向量(features)与相应的类别(label)
:param axis: 划分区域所对应的坐标轴下标
:param left: 左子节点
:param right: 右子节点
"""
self.point = point
self.axis = axis
self.left = left
self.right = right
然后构造平衡 kd 树 :
# -*- coding: utf-8 -*-
from Node import *
import numpy as np
class KDTree:
def __init__(self, sample):
"""
:param sample: 样本点集合(特征向量+类别)
"""
self.sample = sample
def build_kd_tree(self):
# 返回 kd 树根节点
return self._build_kd_tree(self.sample)
def _build_kd_tree(self, sample, depth: int = 0):
"""递归式地构建 kd 树
:param sample: 样本点集合(特征向量+类别)
:param depth: 树中节点的当前深度, 默认为 0
:return: kd 树的根节点 root
"""
if len(sample) == 0:
return None
# 由树的当前深度(≥0)确定待切分的坐标轴, 注意最后一个是 label 无需计算
axis = depth % (len(sample[0]) - 1)
# 排序后根据中位数得到切分点构造平衡 kd 树
# sample.sort(key=lambda point: point[axis])
sample = sample[np.argsort(sample[:, axis])]
median = len(sample) // 2
# 由中位数切分点构造根节点与左右子树
root = Node(sample[median], axis)
root.left = self._build_kd_tree(sample[:median], depth + 1)
root.right = self._build_kd_tree(sample[median + 1:], depth + 1)
return root
找离样本最近的 \(k\) 个点 :
# -*- coding: utf-8 -*-
import heapq
class KNearestNeighbor:
def find_nearest_k(self, root: "Node", target, k: int):
"""找到 target 的 k 近邻
:param root:
:param target:
:param k:
:return:
"""
node_stack = []
self._search_leaf(node_stack, root, target)
# 用一个含 k 个元素的大根堆表示 k 近邻
# 为了方便遍历kd树与堆中最大值比较, 在 python 中用负值小根堆代替
# 初始化 k 近邻堆为空
heap_k_nearest = []
# 保存最近邻
nearest = [float("-inf"), None]
while node_stack:
[node, is_dir_left] = node_stack.pop()
# 计算节点处值与 target 的欧式距离
dist = np.linalg.norm(node.point - target)
# 堆内元素少于 k 则直接加入
if len(heap_k_nearest) < k:
heap_k_nearest.append((-dist, node))
# 如果该节点到 target 距离小于堆顶元素保存的距离
elif -dist > heap_k_nearest[0][0]:
heapq.heappop(heap_k_nearest)
heapq.heappush(heap_k_nearest, (-dist, node))
# 更新最近邻
if -dist > nearest[0]:
nearest[0] = -dist
nearest[1] = node
# 跳过当前节点为叶子节点
if not node.left and not node.right:
continue
# 如果节点另一子树区域与超球体相交或者堆未满
# 堆顶元素保存距离
if abs(node.point[node.axis] - nearest[1].point[node.axis]) \
< nearest[0] or len(heap_k_nearest) < k:
if is_dir_left:
self._search_leaf(node_stack, node.right, target)
else:
self._search_leaf(node_stack, node.left, target)
nearest_k = []
for item in heap_k_nearest:
nearest_k.append(item[1].point)
return nearest_k
def _search_leaf(self, node_stack, root: "Node", target: List[int]):
# 从根节点出发, 在 kd 树中找出包含 target 节点
# 一直走到叶子节点并入栈
node = root
while node:
if target[node.axis] >= node.point[node.axis]:
node_next = node.right
# 表示已经访问过右子树
is_dir_left = False
else:
node_next = node.left
# 表示已经访问过左子树
is_dir_left = True
node_stack.append([node, is_dir_left])
node = node_next
测试 :
from KNearestNeighbor import *
from KDTree import *
sample = np.array([[2, 3, 0], [5, 4, 1], [9, 6, 1], [4, 7, 0], [8, 1, 0], [7, 2, 1]])
kd_tree = KDTree(sample)
root = kd_tree.build_kd_tree()
knn = KNearestNeighbor()
target = [4, 6, 1]
k = 3
nearest_k = knn.find_nearest_k(root, target, k)
print(nearest_k)
这里的算法没有考虑到下面的情况:
- 多个数据点在同一个超平面上
- 有多个数据点跟目标节点的距离相同
KNN 实例: 约会网站的配对效果
Example: improving matches from a dating site with kNN
# -*- coding: utf-8 -*-
import numpy as np
from matplotlib import pyplot as plt
import matplotlib.lines as mlines
def classify0(inx, dataset, labels, k):
# distance calculation
data_size = dataset.shape[0]
diff_mat = np.tile(inx, (data_size, 1)) - dataset
sq_diff_mat = diff_mat ** 2
sq_distance = sq_diff_mat.sum(axis=1)
distance = sq_distance ** 0.5
# distance sorting
sorted_dist_index = distance.argsort()
# voting with lowest k distances
class_count = {}
for i in range(k):
vote_label = labels[sorted_dist_index[i]]
class_count[vote_label] = class_count.get(vote_label, 0) + 1
# sort dictionary class_count
sorted_class_count = sorted(class_count.items(),
key=lambda item: item[1], reverse=True)
return sorted_class_count[0][0]
def file2matrix(filename):
fr = open(filename)
number_of_line = len(fr.readlines())
return_mat = np.zeros((number_of_line, 3))
class_label_vector = []
fr = open(filename)
index = 0
for line in fr.readlines():
line = line.strip()
line = line.split("\t")
return_mat[index, :] = line[:3]
if line[-1] == "didntLike":
class_label_vector.append(1)
elif line[-1] == "smallDoses":
class_label_vector.append(2)
elif line[-1] == "largeDoses":
class_label_vector.append(3)
index += 1
return return_mat, class_label_vector
def show_data(dating_data, dating_labels):
number_of_labels = len(dating_labels)
label_colors = []
for i in dating_labels:
if i == 1:
label_colors.append("black")
elif i == 2:
label_colors.append("orange")
elif i == 3:
label_colors.append("red")
# 设置 3 个子图
fig, axes = plt.subplots(1, 3, sharex=False, sharey=False, figsize=(18, 6))
fig.suptitle("Demo")
# subplot 0
axes[0].scatter(x=dating_data[:, 0], y=dating_data[:, 1],
color=label_colors, s=15, alpha=0.5)
axes[0].set_xlabel("Number of frequent flyer miles earned per year")
axes[0].set_ylabel("Percentage of time spent playing video games")
# subplot 1
axes[1].scatter(x=dating_data[:, 0], y=dating_data[:, 2],
color=label_colors, s=15, alpha=0.5)
axes[1].set_xlabel("Number of frequent flyer miles earned per year")
axes[1].set_ylabel("Liters of ice cream consumed per week")
# subplot 2
axes[2].scatter(x=dating_data[:, 1], y=dating_data[:, 2],
color=label_colors, s=15, alpha=0.5)
axes[2].set_xlabel("Percentage of time spent playing video games")
axes[2].set_ylabel("Liters of ice cream consumed per week")
# legend
didntLike = mlines.Line2D([], [], color='black', marker='.',
markersize=6, label='didntLike')
smallDoses = mlines.Line2D([], [], color='orange', marker='.',
markersize=6, label='smallDoses')
largeDoses = mlines.Line2D([], [], color='red', marker='.',
markersize=6, label='largeDoses')
axes[0].legend(handles=[didntLike, smallDoses, largeDoses])
# save and show
plt.savefig("./dating_example.png", dpi=200, transparent=True)
plt.show()
if __name__ == "__main__":
filename = "datingTestSet.txt"
dating_data, dating_labels = file2matrix(filename)
show_data(dating_data, dating_labels)
def dating_class_test():
filename = "datingTestSet.txt"
dating_data, dating_labels = file2matrix(filename)
norm_data = auto_norm(dating_data)
ratio_test = 0.10
m = dating_data.shape[0]
num_test = int(m * ratio_test)
error_count = 0
k = 3
for i in range(num_test):
classifier_result = classify0(norm_data[i, :], norm_data[num_test:m, :],
dating_labels[num_test:m], k)
print("the classifier result: %d, the real answer: %d"
% (classifier_result, dating_labels[i]))
if classifier_result != dating_labels[i]:
error_count += 1
print("the total err rate is: %f" % (error_count/float(num_test)))
if __name__ == "__main__":
dating_class_test()
...
the classifier result: 1, the real answer: 1
the classifier result: 3, the real answer: 1
the total err rate is: 0.050000
KNN 实例: 鸢尾花数据集 (sklearn)
Scikit-learn 包中的 KNN 算法.
def KNeighborsClassifier(n_neighbors = 5,
weights='uniform',
algorithm = '',
leaf_size = '30',
p = 2,
metric = 'minkowski',
metric_params = None,
n_jobs = None
)
"""
- n_neighbors: 这个值就是指 KNN 中的 K 了, 通过调整 K 值, 算法会有不同的效果.
- weights (权重): 一般的 KNN 算法无论距离如何, 权重都一样. weight 参数有三个可选参数的值, 决定了如何分配权重, 参数选项如下:
'uniform': 不管远近权重都一样, 就是最普通的 KNN 算法的形式.
'distance': 权重和距离成反比, 距离预测目标越近具有越高的权重.
自定义函数: 自定义一个函数, 根据输入的坐标值返回对应的权重, 达到自定义权重的目的.
- algorithm: 在 sklearn 中, 要构建 KNN 模型有三种构建方式: 1. 暴力法, 就是直接遍历计算距离存储比较. 2. 使用 kd 树构建 KNN 模型. 3. 使用球树构建. 其中暴力法适合数据较小的方式, 否则效率会比较低. 如果数据量比较大一般会选择用 KD 树构建 KNN 模型, 而当 KD 树也比较慢的时候, 则可以试试球树来构建 KNN. 参数选项如下:
'brute': 蛮力实现
'kd_tree': KD 树实现 KNN
'ball_tree': 球树实现 KNN
'auto': 默认参数, 自动选择合适的方法构建模型
不过当数据较小或比较稀疏时, 无论选择哪个最后都会使用 'brute'
- leaf_size: 如果是选择蛮力实现, 那么这个值是可以忽略的, 当使用 KD 树或球树, 它就是是停止建子树的叶子节点数量的阈值. 默认30, 但如果数据量增多这个参数需要增大, 否则速度过慢不说, 还容易过拟合.
- p: 和 metric 结合使用的, 当 metric 参数是 "minkowski" 的时候, p=1 为曼哈顿距离, p=2 为欧式距离. 默认为 p=2.
- metric: 指定距离度量方法, 一般都是使用欧式距离.
'euclidean': 欧式距离
'manhattan': 曼哈顿距离
'chebyshev': 切比雪夫距离
'minkowski': 闵可夫斯基距离, 默认参数
- n_jobs: 指定多少个 CPU 进行运算, 默认是-1, 也就是全部都算.
"""
利用 KNN 对鸢尾花数据集进行分类, 判断鸢尾花卉属于 Setosa, Versicolour, Virginica 三个种类中的哪一类.
首先使用 sklearn 中的交叉验证方法决定 \(k\) 值, 代码如下:
from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
from sklearn.neighbors import KNeighborsClassifier
import matplotlib.pyplot as plt
# 读取鸢尾花数据集
iris = load_iris()
x = iris.data
y = iris.target
# 选择 30 个 k 值
num_k = 30
k_error = []
# 循环查看误差结果
cv_num = 6
for k in range(1, num_k + 1):
# 指定算法, 仅更改 k 取值, 其余默认
knn = KNeighborsClassifier(n_neighbors=k)
# 交叉验证, 分别对每一个参数 k, 在 cv 组训练/测试集上进行 cv 次训练和测试
# 最终返回这 k 个测试结果scoring
# cv 参数确定数据集划分比例, cv fold, 即按照 (cv-1):1 划分训练集和测试集
# scoring 指定评价方法, 例如这里的分类任务中 'accuracy' 表示被分类器分类正确的比例
scores = cross_val_score(knn, x, y, cv=cv_num, scoring="accuracy")
# 返回了 cv 个 score, 需要取平均值作为参数 k 的评价值
k_error.append(1 - scores.mean())
# 画图, 横轴为 k 值, 纵轴为误差
plt.plot(range(1, num_k + 1), k_error)
plt.title("cross validation with cv=%i" % cv_num)
plt.xlabel("value of k for KNN")
plt.ylabel("error rate")
plt.savefig("./knn_iris_data.png", dpi=200)
plt.show()
看到取 \(k\) 值为 \(12\) 最佳, 然后应用此 \(k\) 值运行 KNN 算法, 并绘制伪彩色分类图:
import matplotlib.pyplot as plt
import numpy as np
from matplotlib.colors import ListedColormap
from sklearn import neighbors, datasets
n_neighbors = 12
# 导入 iris 数据
iris_data = datasets.load_iris()
# iris_data.shape=(150, 4)
x = iris_data.data[:, 0:2]
y = iris_data.target
# 创建分类伪彩图
h = .05 # 绘图网格中的步长
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF'])
cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
# 绘制两种权重参数下 KNN 的效果图
for weights in ['uniform', 'distance']:
# 创建一个 knn 分类器的实例, 并拟合数据
clf = neighbors.KNeighborsClassifier(n_neighbors, weights=weights)
clf.fit(x, y)
# 绘制决策边界, 将为每个分配一个颜色
# 绘制网格中的点 [x_min, x_max]x[y_min, y_max]
x_min, x_max = x[:, 0].min() - 1, x[:, 0].max() + 1
y_min, y_max = x[:, 1].min() - 1, x[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
# 将结果放入一个彩图中
zz = z.reshape(xx.shape)
plt.figure()
plt.pcolormesh(xx, yy, zz, cmap=cmap_light)
# 绘制训练点
plt.scatter(x[:, 0], x[:, 1], c=y, cmap=cmap_bold)
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
plt.title("3-Class classification (k = %i, weights = '%s')"
% (n_neighbors, weights))
save_name = "knn_iris_k"+str(n_neighbors)+"_weights"+str(weights)
plt.savefig(save_name, dpi=200)
plt.show()
