首页 > Python机器学习 阅读数:56

Python sklearn实现k-近邻算法

k-近邻算法的工作机制并不复杂:给定某个待分类的测试样本,基于某种距离(如欧氏距离)度量,找到训练集中与测试样本最接近的 k 个训练样本,然后基于这 k 个最近的“邻居”(k 为正整数,通常较小)进行预测分类。

预测策略通常采用的是多数表决的“投票法”。也就是说,将这 k 个训练样本中出现最多的类别,标记为预测结果,如下列公式所示:

这里,v 表示分类标签,yi 表示第 i 个训练样本的分类标签,I(□) 是一个指示函数(Indicator Function),如果预测结果属于某个分类,则返回为 1,否则返回 0(实际上就是分类投票)。'y 表示的就是预测结果,哪个类的得票数最多,它就归属于哪个类。

k-近邻算法示意图如图 1 所示。

k-近邻算法示意图
图 1:k-近邻算法示意图

k-近邻算法是一种基于实例的学习,也是惰性学习的典型代表。所谓惰性学习(Lazy Learning)是指,没有显式的训练过程。此方法在训练阶段仅将样本保存起来,所以训练时间为零。待收到测试样本后才开始处理。与之相反的是在训练阶段就“火急火燎”地从训练样本中建模、调参的学习方法—急切学习(Eager Learning)。

k-近邻算法算法虽然简单易用,但也有不足之处。首先,“多数表决”分类会在类别分布偏斜时出现缺陷。也就是说,k 的选取非常重要,因为出现频率较高的样本将会主导对测试样本的预测结果。从图 1 中可见,k 取值不同时,分类的结果明显不同。当 k=1 时,待分类的样本属于第 1 类(即方块类);而当 k=3 时,遵循“少数服从多数”原则,待分类的样本属于第 2 类(三角形类)。自然,当继续扩大 k 值时,样本归属类也可能发生变化。

其次,“少数服从多数”原则也容易产生“多数人的暴政”(tyranny of the majority)问题。什么是“多数人的暴政”呢?最早提出“多数人的暴政”概念的是法国历史学家托克维尔(Tocqueville),他将这种以多数人名义行使无限权力的情况,称为“多数人的暴政”。

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

类似地,k-近邻算法算法如果简单地实施“众(数据)点平等”的“少数服从多数”原则,也可能误判新样本的类别归属。那么,怎样才能缓解这一不利趋势呢?俗话说得好,远亲不如近邻。事实上,我们需要给不同的“投票人”赋予不同的权重,轻重有别,越靠近数据点的投票权重越高,这样才能在投票原则下更为准确地预测数据的类别。

最后,距离的表示方式也会显著影响谁是它的“最近邻”,从而显著影响分类结果。常用的距离表示方式有欧几里得距离(Euclidean Distance,也称欧氏距离)、马哈拉诺比斯距离(Mahalanobis Distance,也称马氏距离)、海明距离(Hamming Distance)等。

影响k-近邻算法性能的因素

影响 k-近邻算法性能的因素有很多,其中比较重要的有四个:k 值的选取、特征数据的归一化、邻居距离的度量及分类原则的制定。下面分别对进行简单介绍。

k值的选取

k 值的选取,对 k-近邻算法的分类性能有很大影响。如果 k 值选取较小,相当于利用较小邻域训练实例进行预测,“学习”而得的近似误差较小,但预测的结果对训练样本非常敏感。也就是说,k 值较小,分类算法的鲁棒性也较差,很容易发生过拟合现象。

倘若 k 值较大,则相当于在较大邻域中训练实例进行预测,它的分类错误率的确会有所下降,即学习的估计误差会有所降低。但随着 k 值的增大,分类错误率又会很快回升。这是因为,k 值增大带来的鲁棒性很快就会被多出来的邻居—“裹挟而来”的噪声点所抑制,也就是说,学习的近似误差会增大。

此外,在样本空间中,相对较远的近邻所在的区域,很可能已经被其他类所占据,这样也会导致 k-近邻算法分类失准。对于 k 值的选取,过犹不及。通常,人们采取交叉验证(Cross Validation,CV)的方式来选取最优的 k 值,即对于每一个 k 值都做若干次交叉验证,然后计算出它们各自的平均误差,最后择其小者定之。

特征数据的归一化

计算不同样本之间的距离,需要考虑不同特征的取值范围。不同特征对距离计算的影响可谓大相径庭。比如,对于灰度而言,245 和 255 之间相差 10。对于气温而言,37°C 和 27°C 之间也相差 10。但这两个 10 实际的差距幅度是大不相同的。这是因为,灰度的值域是 0~255,而气温的年平均值在 -40°C~40°C,前者的差距幅度是 10/256=3.9%,而后者的差距幅度是 10/80=12.5%。

为了公平起见,通常需要对样本的特征值进行数据预处理,归一化(Normalization)就是常见的处理方法之一,它会把所有特征值映射到 [0,1] 范围之内进行处理。归一化机制有很多,最简单的方法是,对于给定的特征,首先找到它的最大值(MAX)和最小值(MIN),然后对于某一个特征值 x,它的归一化值 'x 可用如下公式表示。


下面用一个简单的例子来说明这个归一化值的求解过程。假设训练集中某个特征的值分别为 6、2、24、-6、10。我们使用如下 Python 程序,可方便求解它的归一化值。
In [1]:
01    import numpy as np
02    X_train = np.array([6, 2, 24, -6, 10])       #构建一个矩阵
03    X_min,X_max = X_train.min(), X_train.max()   #求得最小值、最大值
04    print(X_min, X_max)
Out[1]: -6 24
In [2]:
01    X_nomal=(X_train - X_min) / (X_max - X_min)   #求得归一化矩阵
02    print(X_nomal)
Out[2]:[0.4  0.267  1.  0.  0.533]
从输出的结果可以看出,所有的值都落入 [0,1] 区间,这样就完成了归一化操作。

事实上,sklearn 提供了非常多数据预处理操作。导入相应的模块,我们就可以很方便地对数据进行适当的加工。
In [3]:
01    from sklearn.preprocessing import MinMaxScaler
02    import numpy as np
03    X_train = np.array([[6, 2, 24, -6, 10]]).reshape(-1,1)
在上面代码中,第 1 行导入了 sklearn 中的极大极小归一化方法 MinMaxScaler。

但需要注意的是,这个方法在计算极大较小归一化时,是以列为方向(axis=0)来计算的。
X_std = (X - X.min(axis=0)) / (X.max(axis=0) - X.min(axis=0))

所以,对于前面提供的数据 [6 ,2, 24, -6, 10],我们必须将其转置。此外,MinMaxScaler 操纵的数据必须是二维数组,所以我们必须“投其所好”,把数据提前转换为 sklearn 喜欢的模样。

上面代码第 03 行的 reshape(-1,1) 值得说明一下,它表示将数据进行变形。其中第 2 个参数表示数据列数,因此“1”表示数据变形后只有 1 列。而第 1 个参数“-1”并不表示通常意义上的倒数第 1 个,而是表示当 n-1 维度的信息确定后,决定让系统自动计算剩余 n 维数值。这是程序员常用的比较“讨巧”的方法。

针对上述代码,reshape(-1,1) 和 reshape(5,1) 是完全等价的。现在的数据维度较小,你可以输出“5”这个维度的信息。当数据维度非常大时,你就可以感受到这种方法的好处。

事实上,针对上述第 03 行代码,它在功能上等价于如下代码:
03    X_train = np.array([[6, 2, 24, -6, 10]]).T
每个 NumPy 数组对象都有一个转置(transposition,简称为 T)操作,可以直接使用。

在数据加工之后,我们就可以实施转换,将其转换为适合 sklearn 的样式。在 sklearn 中,如果要做一件事,基于面向对象编程的特征,你必须先生成做这件事情的对象。极大极小归一化也是这样。
In [4]: min_max_scaler = MinMaxScaler()

在上述代码中,min_max_scaler 就是要“做事”的对象,只有当这个对象存在,我们才可以调用它对应的方法来实施操作。
In [5]: min_max_scaler.fit(X_train)
Out[5]: MinMaxScaler(copy=True, feature_range=(0, 1))
在 sklearn 中,凡是想从数据中提取参数的操作,在宏观上都叫作拟合(fit),所以在上面代码的 In [5] 处,虽然也用了 fit( ) 这个方法,但并不是前面案例中的模型训练,而是求数据最大值和最小值的方法。

有了这两个值,我们就可以利用归一化公式进行操作,sklearn 中将这种改变原始数据大小的行为,称为变换(transform)。
In [6]: min_max_scaler.transform(X_train)
Out[6]:
array([[0.4 ],
       [0.267],
       [1.  ],
       [0.  ],
       [0.533]])

可以看出,这个输出结果已经和我们自己动手编写的 Python 程序的输出结果非常类似了。只要稍微做一下转置即可获得一样的结果。
In [7]: X_nomal = min_max_scaler.transform(X_train).T
In [8]: X_nomal
Out[8]:[[0.4  0.267  1.  0.  0.533]]

如果我们不需要拟合过程中的参数,那么拟合和变换可以合并为一个方法:fit_transform。因此上述代码可以凝练为一行:
In [9]: min_max_scaler.fit_transform(X_train).T
Out[9]: array([[0.4,  0.267,  1. , 0 .  ,  0.533]])
从上面的操作可以看出,凡事有利必有弊,当我们想使用某个框架时,有时也需要付出代价,那就是必须“削足适履”,把数据转换为框架所需的模样,否则就无法利用框架的优势。

邻居距离的度量

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

在特征空间上,某两个点之间的距离也是它们相似度的反映。距离计算方式不同,也会显著影响谁是它的“最近邻”,从而显著影响分类结果。

一般情况下,我们常采用欧氏距离作为距离的度量指标。但如果不做归一化处理,欧氏距离很容易受量纲的影响,这时我们还可以采用马氏距离。马氏距离是由印度统计学家马哈拉诺比斯(P.C.Mahalanobis)提出的,它可以很方便地表示数据的协方差距离,也是一种有效呈现两个未知样本集相似度的方法。

在文本分类中,对于非连续变量,欧式距离、马氏距离就表现出了一定的局限性。在这种情况下,海明距离应用得更广。简单来说,海明距离就是两个字符串对应位置的不同字符的个数。换句话说,它表示将一个字符串变换成另外一个字符串所需要替换的字符个数。

在实际应用中,我们要根据不同的应用场景选择不同的距离进行度量。只有这样才能让基于距离计算的 k-近邻算法表现得更好。

分类原则的制定

k-近邻算法的分类原则通常有两类。一类是平等投票表决原则,投票多者从之。但这种“众生平等”的投票表决方式可能会产生问题。想象一下,假设让众多人投票判决“你是好人还是坏人”(此处的分类为好人或坏人),那么对你知根知底的人和与对你完全陌生的人,有一样的投票权,是不是对你很不公平呢?因此,多数人投票出来的结果,未必是最理想的。

为了纠正这种偏差,我们要对这些“邻居”赋予不同的投票权重,这也就是第二类分类原则—加权投票原则。对于距离越近的邻居,他的权重越大。