第3章
k 
近邻算法：近朱者赤、近墨者黑

君君,臣臣,父父,子子。
———《论语·颜渊》

3.1　“君君臣臣”传达的分类思想
在《论语·颜渊》篇中,有这么一段著名的对话: 

齐景公问政于孔子。

孔子对曰:“ 君君,臣臣,父父,子子。” 

公曰:“ 善哉! 信如君不君、臣不臣,父不父、子不子,虽有粟,吾得而

食诸?” 
其大意是这样的: 
齐景公问孔子如何治理国家。孔子说:“ 做君主的,要有像君的样子; 

做臣子的,要有像臣子的样子;做父亲的,要有像父亲的样子;做儿子的,要
有像儿子的样子。”齐景公说:“ 讲得好呀! 如果君不像君,臣不像臣,父不
像父,子不像子,虽然有粮食,我能吃得上吗?” 

一些人在批评儒家主张尊卑森严的等级制度时,上面一段话是常见的
“证据”。

但在这里,我们不去评价孔子(见图3-1)时代的价值观,而是想强调这
个“像”字:“做君主的要‘像’君的样子,做臣子的要‘像’臣的样子,做父亲
的要‘像’父亲的样子,做儿子的要‘像’儿子的样子。” 

图3-1孔子的君臣伦理与分类思想

88人工智能极简入门
为什么要强调这个“像”字呢?“像”即为“相似”。相似性为归类之要义[1]。
在第1章中,我们也提到,孟子曾说“智者是非之心也”,是非之心就是“智”①。人工
智能要想实现“智”,就得有“是非之心”,即要明白“伦理”。有了正确的伦理,就很接近人
的智能了[2]。
那什么是“伦理”呢? 从古希腊角度来看,伦是分类,分类的道理就是伦理。而要正
确地分类就要解决如何评估“像”的问题。
于剑教授曾有一个非常精彩的总结[3],归(“) 哪类,像哪类。像哪类,归哪类。上(”) 面的
描述看似重复,其实不然。“归哪类,像哪类”说得是“归纳”,即发现模式,总结规律,而像(“) 哪类,归哪类”说的是“演绎”,也就是“预测”。
铺陈至此,你应该明白,本章讨论的议题就是机器学习中的分类算法。分类算法中
最简单的莫过于
k 
近邻(-aretNeighbr,算法。它虽简单, 位列

kNesokNN) 但非常经典, 
十大数据挖掘算法之中[4],值得我们去掌握②。

3.2　
k 
近邻算法的核心思想
在《孔子家语·六本》里,有这样的说法:“ 不知其子视其父,不知其人视其友,不知其
君观其所使,不知其地视其草木。简(”) 单来说,这句话说的是,如果你拿不准某个人咋样? 
就靠近看看这个人所侵染的环境就可以了,因为人和其周遭具有相似性(即具有同
质性)。

傅玄《太子少傅箴》中也有言,“近朱者赤,近墨者黑。”这句话说的意思和《孔子家
语·六本》是一样的,如果你的邻居多是“朱红”的,那你想不“红”都难。类似地,如果你
的朋友多是混迹于江湖的黑道,那你想“出污泥而不染”也很难。

不论是《孔子家语·六本》,还是《太子少傅箴》,都表明一个哲理,那就是用与你最亲
的几个(设为
k 
个)近邻来给你打标签,进而分组归类,是一种比较靠谱的行为。
上述思想如果被机器学习领域采用,那就是本章要学习的
k 
近邻算法,这里
k 
表示
邻居的个数。

①用机器学习的术语来说,“是非”也可以看作一种“二分类”。
② 根据吴信东等教授的研究,十大算法分别为C4.5,K-Means、SVM 、Apriori、EM 、PageRank、AdaBoost、kNN 、NaiveBayes和
CART 。

第3章　k近邻算法：近朱者赤、近墨者黑89
k 
近邻算法是经典的监督学习算法①,它不仅可以用于分类,还可以用于回归分析。
作为分类算法,简单描述如下:给定某个待分类的测试

k 
近邻算法的工作机制并不复杂, 
样本,在特征空间(FeatureSpace)中,基于某种距离(如欧几里得距离)度量,找到训练集
合中与其距离最近的
k 
个训练样本。然后再基于这
k 
个最近的“邻居”
k 
为正整数, 
常较小),对目标对象进行预测分类。
(通

预测策略通常采用的是多数表决的“投票法”。也就是说,对于待分类的新样本,它
的
k 
个最近的“邻居”多数属于哪一个类,它“随大流”就归属于哪个类。例如,在图3-2 
中,当k=1时,距离待分样本最近的一个邻居是方块,因此待分样本的组别自然就属于
第1类(即方块类);再如,当k=3时,遵循“少数服从多数”原则,待分样本则归属为第2 
类(即三角类。它的三个最近邻居的组成为1个方块,2个三角形,1∶2,三角形类胜出)。
自然,当继续扩大
k 
值时,待分样本的归属又可能发生变化。


k=3表示距离最近的
3个邻居,自然也是包
括最近的1个邻居,就
好比班级成绩前3名, 
也包括班级第1名一
样。

图3-
2 k 
近邻分类示意图

k 
近邻是一种基于实例的学习模型,也是惰性学习的典型代表。所谓惰性学习(LazyLearning)是指,它没有显式的训练过程,它对训练数据完全不做处理或只做少量预处理。

此类学习方法在训练阶段仅仅将样本保存起来,所以训练阶段的时间开销为零。待
收到测试样本时,才正式启动算法流程。与之相反的是,如果在训练阶段就“火急火燎” 
地从训练样本中建模型、调参数的学习方法,称为“急切学习(EagerLearning)”。

① CoverTM,HartP.Nearestneighborpaternclasification[J].IEEETransactionsonInformationTheory,1967,13(1):21-27. 

90人工智能极简入门
最后,距离计算的方式不同,也会显著影响谁是它的“最近邻”,从而也会显著影响分

类结果。常用的距离计算方式有欧几里得距离(EuclideanDistance)、马氏距离

(MahalanobisDistance)及汉明距离(HammingDistance)等。

3.3　
k 
近邻算法的数学基础
机器学习算法的计算离不开数学知识,特别是离不开线性代数的知识。下面结合
k 
近邻算法的所需,简单回顾一下该算法所需的数学知识。

3.1　特征向量与矩阵
3.
首先要说明的概念就是向量(vector)。直观上来看,向量横着的一排数字,如果其内
的每一个数字代表一个维度的特征值,那么这样的向量,就称为特征向量。

对同样的事物,我们可以提取出各种各样的特征。比如说,衡量“做臣子的要像臣子
的样子(即臣臣)”,需要考虑n(=5)个维度的特征,如忠诚、智谋、武功、财富、相貌①,分
别给每个特征打个分,放在一起就构成一个特征向量,记为x1 

这里,
x1=[6,9,1,2,8] 

x1 表示编号为1的大臣的特征向量。
当然,庙堂之上的大臣不止一个。于是,就用x2 表示第2个大臣的特征向量: 
x2=[7,8,3,4,5] 
类似地,第3个大臣的特征向量为
x3=[9,5,7,3,6] 
以此类推,第
m 
个大臣的特征向量为
xm 
=[5,8,6,1,2] 

如果齐景公日理万机,该如何管理这些臣子呢? 也就是说,这么多特征向量放在一
起,怎么呈现比较好呢? 最直观的方式,莫过于把它们一行行堆叠起来,这就形成了一个
有
m 
行
n 
列的矩阵(
n 
表示不同特征的个数)。这就是矩阵(matrix)的由来,我们用
X 

① 读者先不要质疑“相貌”这个特征能否成为评价一个合格臣子的合理性。这是因为,一方面存在特征选择问题,并不是每个特征
都会被用作分类。另一方面,还可以给每个特征分配对应的权值。如果这个特征真的无效,那么这个对应的权值会很小,甚至为负数。

第3 章　k 近邻算法：近朱者赤、近墨者黑 91 
表示: 
X= 
6 9 1 2 8 
7 8 3 4 5 
9 5 7 3 6 
5 8 6 1 2 
.
è
..... 
.
.
÷÷÷÷÷ 
m ×n 
为了简化起见,这里m =4,n=5。于是,矩阵X 中的某个元素xij 表示第i 个臣子
的第j 个特征。
有了特征向量表示之后,进一步地,可以把特征向量表示在直角坐标系中。比如
x1=(6,9,1,2,8)就可以看成是直角坐标系中的一个点。这些表示特征向量的点,被称
为特征点。而所有这些特征点构成的空间被称为特征空间(featurespace),如图3-3所示
(为绘图方便,我们仅挑选了前3个特征)。① 
图3-3 特征空间
目前,臣子有5个特征:忠诚、智谋、武功、财富、相貌。如和你以前的疑惑一样,有些
特征对分类任务(比如判断是否为一个合格的臣子)是没有多少用处的。比如说,对齐景
公来说,或许他只看重前三个:忠诚、智谋、武功。这种从众多特征中,仅选取部分特征服
① Python源代码详见范例3-1(3d-scatter.py)。代码仅供有编程基础的读者参考。对于没有编程基础的读者,通常并不影响正文理
解。全书同。

92人工智能极简入门
务于任务这种行为就叫特征选择(n)。

featureselectio

过拟合是指过于精确特征选择在机器学习中特别重要。合适的特征选择,可以达到如下效果:①模型得
地匹配特定数据集,以以简化,使之更易于被用户理解;②缩短训练时间;③改善通用性,降低过拟合
至于无法良好地拟合(overfiting)。

其他数据的现象。相同维度的特征向量是可以实施运算操作的。比如,如果齐景公看到了大臣们的特
征矩阵X,按捺不住自己“指点江山”的兴致,对各个臣子的每个特征做了各种期许, 
如,他对第1个大臣x1 的期许是这样的:忠诚(+1,表示忠诚不够,还要加1)、智谋(+(比) 0,表示已经够聪明了,无须改变)、武功(+2,表示还需加强军事训练,还需要提升2)、健
康(+4,表示身体太弱,需要较大幅度提升身体素质)、相貌(-3,表示长得太帅,影响朝
政,不需要每次上朝都打扮得光鲜亮丽)。

于是,这些期许放在一起,也搞成了一个向量,记为y1: 

2,3]

y1=[1,0,4,

如果大臣x1 达到齐景公的期许了,会变成什么样子的呢? 实际上,这就涉及向量的
加法,其结果记为z1: 

z1=x1+y1 
=[6,9,1,2,8]
+ 
[1,0,2,4,-3] 
=[7,9,3,6,5] 

向量的加法实施规则是,丁(“) 对丁,卯对卯”,对应位置的元素两两相加,如图3-4 
所示。


图3-
4 
向量加法

类似地,齐景公对第2个大臣x2 的期许是这样的:忠诚(+2 )、智谋(+1 )、武功
(+4 )、健康(+4 )、相貌(-2)。于是,这些期许也搞成了一个向量,记为y2: 

4,2]

y2=[2,1,4,


第3 章　k 近邻算法：近朱者赤、近墨者黑 93 
如果大臣x2 达到齐景公的期许了,其结果可记为z2: 
z2 =x2 +y2 
=[7,8,3,4,5]+[2,1,4,4,-2] 
=[9,9,7,8,3] 
或许,你也感觉出来了,如果都这么处理,效率太低。能不能把齐景公对臣子的期许
汇集在一起,形成一个矩阵Y,Y 和X 等大,也是m ×n 维: 
Y= 
1 0 2 4 -3 
2 1 4 4 -2 
0 3 2 4 -1 
4 1 2 7 2 
.
è
..... 
.
.
÷÷÷÷÷ 
这样一来,就可以批量地把Y 迭代到X 上,这就是矩阵的加法: 
Z =X +Y 
= 
6 9 1 2 8 
7 8 3 4 5 
9 5 7 3 6 
5 8 6 1 2 
.
è
..... 
.
.
÷÷÷÷÷ 
+ 
1 0 2 4 -3 
2 1 4 4 -2 
0 3 2 4 -1 
4 1 2 7 2 
.
è
..... 
.
.
÷÷÷÷÷ 
= 
7 9 3 6 5 
9 9 7 8 3 
9 8 9 7 5 
9 9 8 8 4 
.
è
..... 
.
.
÷÷÷÷÷ 
从上面分析可知,在本质上,矩阵就是一个人们虚构出来的一种代数工具,利用这种
工具,人们能够让计算从单个处理,变成批量处理。相比矩阵加法,矩阵的乘法用途更
大。我们先来说说一个矩阵和一个向量如何相乘,然后再扩展到矩阵和矩阵的乘法。
前面我们提到,对于齐景公来说,臣子的某些特征对他有用(比如说忠诚、智谋、武
功),而有些特征如财富、相貌等对他用途不大,于是齐景公对这5个特征给出了不同的
权重,比如说,忠诚(0.5)、智谋(0.2)、武功(0.2)、财富(0.05)、相貌(0.05),为了便于处理, 
那么这些权重也可以汇集起来,形成一个权值向量,记为W : 
W =[0.5,0.2,0.2,0.05,0.05] 
有时,为了表述方便,人们会把这个行向量通过转置(Transpose,T),得到一个列

94 人工智能极简入门
向量: 
WT= 
0.5 
0.2 
0.2 
0.05 
0.05 
é
.
êêêêêêê 
ù
.
úúúúúúú 
有时为了方便,在说明是列向量的情况下WT 上的T也省略了。
如果齐景公觉得每次看一堆数据很麻烦,能不能给每个臣子在整体上打个分数呢, 
于是,就用到了矩阵与向量的乘法: 
图3-5 矩阵与向量的乘积
以第1个臣子为例,他综合的分数为:忠诚(7×0.5)+智谋(9×0.2)+武功(3×0.2) 
+财富(6×0.05)+相貌(5×0.05)=6.45。也就是说,矩阵第一行每一个数字,分别与列
向量的每一个数字相乘之后再相加求和。类似地,第2个臣子的综合分数为:忠诚(9× 
0.5)+智谋(9×0.2)+武功(7×0.2)+财富(8×0.05)+相貌(3×0.05)=8.25,以此
类推①。
或许,有读者会说,这不就是算术中加权相乘后的连加求和吗,为什么要搞出矩阵这
样一个工具? 是的,如果只有5个维度,可能不需要用矩阵,人们心算或许就能得到结
果,但如果需要计算的数据是1万维、100万维,人们通常就想不清楚了,而用矩阵运算, 
就非常直观,使用它既方便又不容易出错。
在图3-5中,大臣们的各个特征的权值都是一样的。假设齐景公“审时度势”,和平时
给大臣们的各个品性一个权值分配,战争时是另外一个权值体系,心血来潮时又是其他
一套玩法,那么又将如何呢? 
① 矩阵操作的Python程序,可参见随书源代码范例3-2:mat_mul.py。

第3 章　k 近邻算法：近朱者赤、近墨者黑 95 
如果将这些权值都汇集起来,就会形成一个权值矩阵。现在我们想要知道齐景公在各
个时期对大臣的整体评估分数,这就需要涉及矩阵与矩阵的乘法运算了,如图3-6所示。
图3-6 矩阵乘法
计算矩阵的Python代码如下所示。 
01 import numpy as np #导入NumPy 模块
02 X =np.array([[7, 9, 3, 6, 5], #构造特征矩阵X 
03 [9, 9, 7, 8, 3], 
04 [9, 8, 9, 7, 5], 
05 [9, 9, 8, 8, 4]]) 
06 W =np.array([ #构造权值矩阵S 
07 [0.5, 0.4, 0.3], 
08 [0.2, 0.2, 0.3], 
09 [0.2, 0.4, 0.1], 
10 [0.05, 0.0, 0.1], 
11 [0.05, 0.0, 0.2] 
12 ]) 
13 S =np.dot(X,W) #计算矩阵乘法X*W 
14 print("矩阵与矩阵相乘:\n",S) #输出运算结果
我们并没有打算给读者讲解有关矩阵运算的Python语法,这里之所以给出代码,是
想让读者有个感性认知,上述代码中,除了数据准备(第02~12行),核心代码就一行,第
13行的矩阵运算。在这个矩阵运算里,你并没有看到任何for循环的迹象。也就是说,

96人工智能极简入门
在计算矩阵时,通常并不是一个一个元素串行运算的,而是在NumPy① 等计算框架下做
了优化,以向量的形式批量计算。事实上,这种向量化的批量处理操作,在多核CPU 和
众核GPU 的环境下,性能的提升尤其明显,而规整化的矩阵,为大规模向量运算提供了
“物资(数据)基础”。

3.2　特征向量的归一化
3.
我们知道,数据点) 样本可能有多个

k 
近邻免不了计算不同邻居( 之间的距离。然而, 
特征,不同特征亦有不同的定义域和取值范围,它们对距离计算的影响可谓大相径庭。

比如,对于颜色而言,245 和255 之间相差10 。但对于天气的温度,37°C和27°C之
间也相差10 。这两个距离都是10,但相差的幅度却大不相同。这是因为,颜色的值域是
0~255,而通常气温的年平均值在-40°C~40°C,这样,前者的差距幅度在10/256= 

而后者的差距幅度是10/805% 。因此,为了公平起见,样本的不同特征需要
做归一化(Normalization)处理,即把特征值映射到[0,1]范围之内处理。

3.9%, =12.

归一化机制有很多,最简单的方法莫过于MIN-MAX 缩放,其过程是这样的:对于
给定的特征,首先找到它的最大值(MAX)和最小值(MIN), 然后对于某个特征值x,它的
归一化值x~ 
可用式(3-1)表示,图3-7演示了这个过程。

x-MIN x(~) = 
MAX-MIN (3-1) 


图3-
7 
MIN-MAX 
缩放示意图

下面用一个简单的例子来说明这个归一化值的求解。假设训练集合中有5个样例, 

其中某个特征的值分别为[6,9,1,2,8]。为了降低读者的实践门槛,我们用Excel来

演示它的运算过程(Python版本代码参见范例3-3:max-min.

py )。

① NumPy是Python语言的一个扩展程序库,支持高维度数组与矩阵运算。

第3章　k近邻算法：近朱者赤、近墨者黑97
首先,在Excel中第一列(A)依次输入需要归一化的向量。然后在单元格B2(表示请注意:对于公式,请
第B列和第2行的交界处)输入公式:=MAX(A2:A6), 这里需要简单说明的是,在不要用全角公式或冒
Excel中,“=”是输入公式的标记符,MAX 是Excel的内置公式,A2:A6 表示数据来源号和等号,全书同。
是第A列的第2行到第6行。“:”是数据起止范围的分隔符。公式输入完毕后,按回车
键即可得到向量的最大值9。


图3-
8 
极大极小归一化(Excel实践) 

类似地,在C2 单元格输入公式“=MIN(A2:A6)”即可得到向量的最小值1。归一化
要用到最大值和最小值,然后在D2 单元格中输入公式“=(A2-$C$2)/($B$2$C$2)” 625( 

即可算得向量6对应的归一化数值0.见图39)。然后将鼠标移至D2 单元
格的右下角,鼠标变为一个“十”字模样,压住鼠标左键拖动鼠标至D6 。


图3-
9 
计算极大极小值的过程

默认情况下,单元格引用是相对引用。在拖动鼠标时,从单元格D2 到D6 时,公式
就变为=(A6-$C$2)/($B$2-$C$2 )。我们知道,最大值(B2)和最小值(C2)是
全局的,在拖动鼠标下拉时,我们不希望它的编号发生变化,于是可以在单元格对应的列

在Excel中,行或列的
编号前面添加美元符
号$,表示绝对公式标
记,它表示在拖动单元
格,有该标识的单元格
被“锁定”,单元格中的
内容不会随鼠标拖动
而发生变化。


98人工智能极简入门
号和行号前面添加美元符号($), 表示绝对引用。这样一来,就可以很方便地得到图3-8 
所示的计算结果。

从图3-8输出的结果可以看出,所有的值都落入区间[0,1], 这样就完成了归一化操
作。如果每个特征都做归一化处理,那么不同量纲的特征,就不会因为量纲的差异而对
计算距离产生重大偏差。

从上面的实践中可以看到,人工智能其实是一门实践性很强的学科。“纸上得来终
觉浅,绝知此事要躬行。读(”) 者需要创造条件,动手实践,以便能更为深刻地理解一些
概念。

常用的特征归一化操作还有“方差缩放”。它的操作流程是这样的:特征值减去该特
征的均值,再除以方差: 

x-mean(x)x(~) = 
sqrt(var(x)) (3-2) 

通过“方差缩放”,数据特征的均值为0,方差为1。如果初始特征值服从正态分布, 
那么缩放后的特征值同样也服从正态分布,不过是方差和均值发生了变化。关于“方差
缩放”的归一化实践,就留给读者自行完成吧。

3.4　
k 
近邻算法的三个要素
言归正传,回到
k 
近邻算法的讨论上来。我们知道,

k 
近邻算法有三个核心要素:
k 
值的选取、邻居距离的度量和分类决策的制订。下面分别对它们进行简单介绍。

3.1　
k 
值的选取
4.
k 
近邻算法的优点很明显,简单易用,可解释性强,但也有其不足之处。例如,“多数
表决”会在类别分布不均匀时浮现缺陷。也就是说,出现频率较多

k 
值的选取非常重要
,
的样本将会主导测试点的预测结果
。


从图3-
k 
值的选取,

2中可见,对
k 
近邻算法的分类性能有很大影响。如果
k 
值选取
较小,相当于利用较小邻域的训练实例去预测分类,“学习”的近似误差较小,但预测的结
果对训练样例非常敏感。如果这个近邻恰好就是噪声,那么预测就会出错。也就是说,
值较小,分类算法的健壮性较差。
k 


第3章　k近邻算法：近朱者赤、近墨者黑99
倘若
k 
值较大,则相当于在较大邻域中训练实例进行预测,它的分类错误率的确有
所下降,即学习的估计误差有所降低。但随着
k 
值的增大,分类错误率又会很快回升。
这是因为,很快就会被多出来的邻居“ 的噪声点所抑

k 
值增大带来的健壮性, 裹挟而来” 
制,也就是说,学习的近似误差会增大。

换句话说,对于
k 
值的选取,过犹不及。通常,人们采取交叉验证(Cros 
Validation, 
CV)①的方式来选取最优的
k 
值,即对于每一个
k 
值(k=1,2,3,…),都做若干次交叉验
证,然后计算出它们各自的平均误差,最后择其小者定之。

3.2　邻居距离的度量
4.
不量化,无以度量远近。
k 
近邻算法要计算“远亲近邻”,就要求样本的所有特征都能
做到可比较的量化。如果样本数据的某些特征是非数值类型的,那也要想办法将其量
化。比如颜色,不同的颜色(如红、绿、蓝)就是非数值类型的,它们之间好像没有什么距
离可言。但如果将颜色(这种非数值类型)转换为灰度值(数值类型:0~255),那么就可
以计算不同颜色之间的距离(或说差异度)。

在特征空间上,某两个点之间的距离也是它们相似度的反映。距离计算的方式不
同,也会显著影响谁是它的“最近邻”,从而也会显著影响分类结果。假设有如下训练集: 
yi),2,…,

T={(xi,i=1,n} (33) 

式(33) xi为第
i 
个样本的特征向量,1,c}

-中,yi 
∈{2,…,为类别标签。对于一个新
样本(x,它在训练集合中的最近邻标记为(xh 
,可用式(3-4)来选取它的最近邻:

y), yh 
), 

xh 
)ii(x,(

d(x,=mnd(xi)) 34) 

式(34) d(xi) 之间的距离。于是,

-中,x,表示新样本
x 
和训练集中的样本xi 
新样本
的类别就被预测为距离它最近的
k 
个邻居的标签,记作yyh

^=。
很显然,式(3-4)的核心所在,是如何度量任意两个样本之间的距离。对于
m 
维样本
xi和样本xj 
之间的距离Lp 
,通常可以用欧几里得距离(EuclideanDistance,简称欧氏距
离)表示: 

① 交叉验证,亦称循环估计,是一种统计学上将数据样本切割成较小子集的实用方法。算法先在一个子集上做分析,而其他子集则
用来做后续对此分析的确认及验证。

1 00 人工智能极简入门
d(xi,xj)= Σm 
s=1 (x(s) i -x(s) ( j )2 ) 1/2 (3-5) 
当m =2时,对于二维平面两点x1与x2间的欧几里得距离可表示为
d(x1,x2)= (x1(1)-x2(1))2 + (x1(2)-x2(2))2 (3-6) 
当然,度量距离的方式并非仅限于欧几里得距离,比如还可以是曼哈顿距离
(ManhattanDistance)、切比雪夫距离(Chebyshevdistance)、汉明距离(Hamming 
Distance)、余弦相似度、皮尔逊相关系数、KL 散度等。在实际应用中,要根据不同的应用
场景选择不同的距离度量。只有这样才能让基于距离计算的k 近邻算法表现得更好。
3.4.3　分类决策的制订
本质上,分类器就是一个由特征向量到预测类别的映射函数。k 近邻算法的分类流
程大致按如下三步走。
(1)计算待测试样本与训练集合中每一个样本的欧几里得距离。
(2)对每一个距离从小到大排序。
(3)选择前k 个距离最短的样本,分类任务采用“少数服从多数”的表决规则。k 近
邻回归的任务的实现逻辑也不复杂,它可采用k 个近邻的平均值作为预测值。
k 近邻的损失函数为0-1损失函数: 
L(Y,f(X ))= 1, Y ≠f(X ) 
{0, y =f(X ) (3-7) 
分类函数为
f:Rn → {c1,c2,…,cK } (3-8) 
那么,分类错误的概率为
P(Y ≠f(X ))=1-P(Y =f(x)) (3-9) 
对给定实例x∈χ,其最近邻的k 个样本点构成一个小集合,记作Nk(x)。如果涵盖
Nk(x)的区域的类别为cj(虽然这个有待判定的分类未知大小,但肯定在{c1,c2,…,cK } 
之列),那么分类错误率为

第 3章　k近邻算法：近朱者赤、近墨者黑101
1 I()1 I() (

Σ yi 
≠cj=1-Σ yi=cj3-10)

kxi∈Nk(x) kxi∈Nk(x) 

分类错误率,其实就是训练数据的经验风险。如果要使得经验风险最小,那么就得

让分类正确率最大,即kxi∈Nk(x) 
yi=)最大化。对于特定
k 
近邻分类器而言,rgmax(f(x))是使得

为常数,因此可得
1ΣI(cjk 
可视f(x(a) )取得最大值所对
cj 
=argmaxΣI(yi=cj) (3-11) 应的变量点x(或
x 
的
cj 
xi∈Nk(x) 集合)。

式(3-11)描述的其实就是
k 
近邻的分类规则———“少数服从多数”。式(3-11)中
,
IndicatorFunctio


I(·)是一个指示函数(n),表示其中有哪些元素属于某一子集,这里如
果参数为真,则返回值为1,否则返回值为0(实际上就是分类投票)。cj 
表示的就是分类
器预测的类别标签。

3.4　苏格拉底之死与
k 
近邻之弊
4.
从上面的分析可知,“多数表决”是
k 
近邻分类算法的显著特点,由前面分析可知,它
可等价为经验风险(即分类误差) 因此算法具有分类准确性高的优点。此外,

最小, 
k 
近邻
算法的优点还在于,对异常值和噪声有较高的容忍度等,这是因为“多数表决”的策略对
异常值或噪音有平滑作用。由此带来的副作用还是
k 
近邻算法的计算量比较大,内存消
耗量也大。

其实,容易产生“ 问题。通过

k 
近邻分类带来的最大副作用可能在于, 多数人的暴政” 
学习历史知识,我们知道,如果某个君王刚愎自用,听不进他人的谏言,不察民情,导致民
不聊生的现象,可谓“寡人暴政”。那什么又是“多数人的暴政”呢? 最早提出“多数人的
暴政”概念的是法国历史学家托克维尔(
le),他将这种以多数人名义行使无限
权力的情况,称为“多数人的暴政”。
Tocquevi

多(“) 数人的意见虽然代表了大多数人的利益,但‘多数’可能恰恰就是平庸的多数,精
英永远是少数。大众民主,并不能保证人类社会向最正确的方向发展”“多数人的暴政” 
的历史渊源,最早可以追溯到古希腊时代的“苏格拉底之死”,如此智慧之人的死刑判决, 
竟然是由雅典人一人一票的多数人表决出来的(见图3-10 )。

“众生平等”式投票的问题在于,当
k 
近邻分类算法中的
k 
过大时,由于距离当前测试
样本点“八竿子打不着”的“邻居”,也具有同等的发言权,这反而会导致分类正确率的下降。


102人工智能极简入门
图3-10 
“少数服从多数”的投票规则导致苏格拉底之死

3.5　瑞·达里奥的“话份
4.
那么,该如何做才能缓解上述不利的投票规则呢? 俗话说得好,“远亲不如近邻”。
事实上,可以给不同的“邻居”赋予不同的投票权重,轻重有别,越靠近待测样本点的投票
权重越高,越远离待测样本点的投票权重越低,甚至为零,只有这样,才能确保在多数投
票原则下更为准确地预测其类别。比如,就有学者提出了可调整权重的
k 
最近邻法
(weightedk-NearestNeighbor,wkNN),以促进分类效果①。

机器学习的很多算法,在现实生活中都能找到对应的影子,
k 
近邻算法也不例外。
瑞·达里奥(RayDalio)是桥水基金的创始人。他的公司桥水资本管理着1600亿美元资
金,是过去十年最成功的对冲基金。2017年年底,瑞·达里奥出版他的著作《原则:如何
创造出完美独特的自己》[5],副标题是中国某出版社为吸引眼球添加的,英文版书名就是
Principles(原则),书中记载了瑞·达里奥管理自己和公司的各种原则和规范。

他一直用一种看似极端的原则来管理自己的公司。其中一个决策原则叫作beleaiiy

ivbltweightedideameritocracy,直译过来就是“可信度加权的想法唯贤是举体制”。专业术语
说起来很拗口,其实用大白话来说,就是“话份”(即说话的分量)。人人都有话份,但话份
有差别。

某人水平高,决策效果的历史表现好,他的话份就大,反之话份就小。当决策遇到分

① HechenbichlerK,SchliepK.Weightedk-nearest-neighbortechniquesandordinalclasification. 

第3章　k近邻算法：近朱者赤、近墨者黑103
歧时,不是按“一人一票”均等投票,而是按“不同意见×话份”来解决分歧。每次决策都
有记录,随后根据决策效果反馈,随时更新每个人的话份。所以你看看,瑞·达里奥的决
策思想,其实和前面提到的可调整权重的
k 
最近邻投票法殊途同归。

那如何合理地动态调整每个人的“话份”呢? 请注意瑞·达里奥的一个原则细节, 根(“) 据决策效果反馈,随时更新”,这其实就是“贝叶斯算法”,我们会在后面的章节中详细
讲解,这里不做展开。

3.5　用Excel 
完成
k 
近邻算法实战
k 
近邻算法用公式描述起来比较抽象,难以理解。前面已经提到,实战对理解抽象概
念的重要性,下面就利用Excel来逐步演示
k 
近邻算法的运行过程,以增强读者的感性认
识(详见随书文件:knsmpexs

n-il.lx)。

3.1　分类任务与数据准备
5.
鸢尾花属下的三个亚属,分别是山鸢尾(a)、变色鸢尾(和维
吉尼亚鸢尾(IrisVirginica), 如图3-11 所示。人们往往会根据物体具有的一些特点来区
分它们,比如辨别不同鸢尾花品种时,依据的是鸢尾花的花瓣特征。

IrisSetosIrisVersicolor) 


图3-11 
鸢尾花卉的三个品种

经过尝试,人们发现花瓣的花萼长度(sepallength)、花萼宽度(sepalwidth)、花瓣长
度(petallength)和花瓣宽度(petalwidth)可作为区分鸢尾花类别的特征,这些特征也符
合人们根据鸢尾花花瓣的大小来区分花卉种类的生活经验。


104人工智能极简入门
我们的分类任务就是,给定一个新样本(新采集的鸢尾花)的4个特征,预测出它的
亚属类别。分类器就是前面学习的
k 
近邻算法。使用的数据集为经典的鸢尾花卉数据
集,而该数据集最初是由美国植物学家埃德加·安德森(EdgarAnderson)整理出来的。
在加拿大加斯帕半岛上,通过观察,埃德加·安德森采集了因地理位置不同而导致鸢尾
属花朵形状发生变异的外显特征数据。这个鸢尾花卉数据集共包含150个样本,读者朋
友可以从UCI(加州大学埃文分校)的机器学习库中下载这个数据集①。

3.2　可视化图展现
5.
一图胜千言。为获取更多感性认识,下面我们还是用可视化的方式,来显示这个数
据集合的部分特征分布情况。对于二维空间,选择两个特征比较容易进行可视化表达。
这里抽取训练样本的第1个特征———花萼长度(sepallength)和第3个特征———花瓣长
度(petallength),来做二维散点图,运行结果如图3-12所示(绘图源代码参考范例3-4: 
get-data-scater.

py)②。


图3-12 
鸢尾花卉样本聚类图

①下载网址为htps://acieisuieu/m/mahn-erigdtbss/rs/rsdta。
rhv.c.c.dlcielann-aaaeiiii.a

② 请注意,Python代码中的变量不支持空格,所以sepallength表示为sepal_length。

第3章　k近邻算法：近朱者赤、近墨者黑105
3.3　计算相似性
5.
在
k 
近邻算法中,距离就代表相似性(similarity)。二者离得越近,说明相似度就越
高。为了找到“最近”的邻居,需要找到衡量邻居的标准。简单起见,这里还是利用传统
的欧几里得距离作为衡量相似性的标准。对于本例而言,每一个样本实例有4个特征, 
每个特征的度量单位都是厘米,量纲一致,所以欧几里得距离是适用的。

欧几里得距离比较容易通过计算得到。一般来说,先求得每对样本间的不同特征的
差异值,然后求差值的平方和,最后再求这个和的平方根,即得欧几里得距离。

2

2+ 
(2+ 
(2+ 
(

z)z1)z3)(

Dist(x,
= 
(x1-x2-z2)x3-x4-z4)3-12) 

式中,
x 
和
z 
为两个数据点,xi和zi分别为
x 
和
z 
的第
i 
(1≤i≤4)个特征。

简单起见,从150 个样本点中随机挑选20 个点来说明kNN 算法的运行过程。这20 
个样本点的属性值如图3-13 所示。


图3-13 
鸢尾花数据集


1 06 人工智能极简入门
给定一个新预测的样本点(5.5,3.5,1.3,0.2),我们的任务就是预测它属于鸢尾花的
哪一亚属类(为节省篇幅,把这个样本点的4个特征依次在同一列给出)。
在Excel中,很容易绘制出数据的散点图(为了绘图方便,同样仅选择第1个和第3 
个特征),同时把需要预测的样本点也绘制出来,如图3-14所示。为了便于处理,分别将
三类鸢尾花用数字代号进行标记:Iris-setosa:0、Iris-versicolor:1、Iris-virginica:2。
图3-14 鸢尾花样本点与预测样本点
观察图3-14可大致预测,需要预测的样本点(带有方框标识的数据点)属于第0类
(即Iris-setosa),因为它周围的邻居大多都属于第0类。下面用k 近邻算法来验证我们
的直觉。
首先来计算样本点与其他点之间的欧几里得距离。在K2输入如下公式(见图3-15)。
SQRT函数的功能是求给定数值的平方根,该公式实际上就是式(3-12)的Excel版本。 
=SQRT(($H$2-B2)^2+($H$3-C2)^2+($H$4-D2)^2+($H$5-E2)^2) 
在上述Excel公式中,由于待分类的样本点的4个坐标值(即H2~H5)是固定的,所