深入理解机器学习——k近邻（kNN k-Nearest Neighbor）算法：算法定义

分类目录：《深入理解机器学习》总目录

k近邻算法简单、直观：给定一个训练数据集 D D D，对新的输入实例，在训练数据集中找到与该实例最邻近的 k k k个实例，这 k k k个实例的多数属于某个类，就把该输入实例分为这个类。下面先叙述 k k k近邻算法，然后再讨论其细节：

k近邻（k-Nearest Neighbor）算法

输入：

\qquad 训练集： D = ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) D = {(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)} D=(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)

输出：

\qquad 实例 x x x所属的类 y y y

算法：.

（ 1 ） 根据给定的距离度量，在训练集 D D D中找出与 x x x最邻近的 k k k个点，涵盖这 k k k个点的 x x x的邻域记作 N k ( x ) N_k(x) Nk​(x)

（ 2 ） 在 N k ( x ) N_k(x) Nk​(x)中根据分类决策规则（如多数表决）决定 x x x的类别 y y y：

y = arg max ⁡ c j I ( y i = c j ) y=\argmax_{c_j}{I(y_i=c_j)} y=cj​argmax​I(yi​=cj​)

k近邻法的特殊情况是 k = 1 k=1 k=1的情形，称为最近邻算法。对于输入的实例点（特征向量） x x x，最近邻法将训练数据集中与 x x x最邻近点的类作为 x x x的类。