机器学习——K-NN算法
目录
一. KNN的原理
KNN(K近邻算法)是机器学习中常用于分类的机器学习算法。我们先思考一个问题,即假设有两个类别,即类别A和类别B。此时我们有一个新的数据点x1,那么我们要把这个新的数据点x1分到哪一类呢?是分到A还是分到B呢?问题如下图所示。
用KNN的来分类的步骤一般如下:
- step1:选择邻居的数量K
- step2:计算所有点与新数据点的欧式距离
- step3:根据计算出的欧氏距离取K个最近邻的点
- step4:统计K个最近邻的点中各个类别的点的数量
- step5:将数据点分配给邻居数量最大的类别
根据上面的KNN的原理,我们来对上面的问题求解:
- 首先,我们将邻居数量K设置为K = 5。
- 接着,我们计算数据点和所有点之间的欧式距离
A点与B点欧式距离为
- 通过计算新数据点与所有点的欧式距离,我们得到与数据点最近的K(K = 5)个点
- 如图,通过统计K近邻点的类别,我们得出靠近数据点的K(K = 5)个近邻点中,A类有3个,B类有2个,最后我们将数据点划分给A类。
二. K-NN算法的注意事项
1. 如何选取K值
(1)K是一个超参数,是根据经验或启发来人为给定的。因此,我们无法确定“K”的最佳值,因此在实现的过程中我们会尝试改变K值来找到最优的结果。在工程上,我们一般用交叉验证的方式来选取K值。
(2)非常低的K值(如K = 1或K=2)可能会导致模型容易受噪声和异常值的影响,会表现出过拟合。
(3)K值太大会对结果造成较大的影响,导致分类的偏差变大,距离过远的点也会对数据点的分类造成影响,即结果会表现出欠拟合。
2. K-NN算法的优点
(1)实现起来简单。
(2)对嘈杂的训练数据具有鲁棒性,对异常值不敏感。
(3)训练数据越大越有效,精度高。
3. K-NN算法的缺点
(1)需要认为确定K值,K值不同对结果的影响也不同。
(2)计算成本高,即需要计算所有训练的数据与数据点之间的欧式距离。
三. 算法的Python实现
(1)用原理实现K-NN
首先,导入相关的模块,导入了鸢尾花数据集,并对数据进行处理,划分好训练集以及测试集:
# 导入相关模块
import numpy as np
from collections import Counter
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.utils import shuffle
# 导入sklearn iris数据集
iris = datasets.load_iris()
# 打乱数据后的数据与标签
X, y = shuffle(iris.data, iris.target, random_state=13)
# 数据转换为float32格式
X = X.astype(np.float32)
# 训练集与测试集的简单划分,训练-测试比例为7:3
offset = int(X.shape[0] * 0.7)
X_train, y_train = X[:offset], y[:offset]
X_test, y_test = X[offset:], y[offset:]
# 将标签转换为竖向量
y_train = y_train.reshape((-1,1))
y_test = y_test.reshape((-1,1))
# 打印训练集和测试集大小
print('X_train=', X_train.shape)
print('X_test=', X_test.shape)
print('y_train=', y_train.shape)
print('y_test=', y_test.shape)
下面的代码定义了计算欧式距离的函数,算出各个测试样本与所有训练样本的欧氏距离:
### 定义欧氏距离
def compute_distances(X, X_train):
'''
输入:
X:测试样本实例矩阵
X_train:训练样本实例矩阵
输出:
dists:欧式距离
'''
# 测试实例样本量
num_test = X.shape[0]
# 训练实例样本量
num_train = X_train.shape[0]
# 基于训练和测试维度的欧氏距离初始化
dists = np.zeros((num_test, num_train))
# 测试样本与训练样本的矩阵点乘
M = np.dot(X, X_train.T)
# 测试样本矩阵平方
te = np.square(X).sum(axis=1)
# 训练样本矩阵平方
tr = np.square(X_train).sum(axis=1)
# 计算欧式距离
dists = np.sqrt(-2 * M + tr + np.matrix(te).T)
return dists
dists = compute_distances(X_test, X_train)
plt.imshow(dists, interpolation='none')
plt.show();
下面的代码定义了预测函数,并对结果进行预测:
### 定义预测函数
def predict_labels(y_train, dists, k=1):
'''
输入:
y_train:训练集标签
dists:测试集与训练集之间的欧氏距离矩阵
k:k值
输出:
y_pred:测试集预测结果
'''
# 测试样本量
num_test = dists.shape[0]
# 初始化测试集预测结果
y_pred = np.zeros(num_test)
# 遍历
for i in range(num_test):
# 初始化最近邻列表
closest_y = []
# 按欧氏距离矩阵排序后取索引,并用训练集标签按排序后的索引取值
# 最后拉平列表
# 注意np.argsort函数的用法
labels = y_train[np.argsort(dists[i, :])].flatten()
# 取最近的k个值
closest_y = labels[0:k]
# 对最近的k个值进行计数统计
# 这里注意collections模块中的计数器Counter的用法
c = Counter(closest_y)
# 取计数最多的那一个类别
y_pred[i] = c.most_common(1)[0][0]
return y_pred
# 测试集预测结果
y_test_pred = predict_labels(y_train, dists, k=1)
y_test_pred = y_test_pred.reshape((-1, 1))
# 找出预测正确的实例
num_correct = np.sum(y_test_pred == y_test)
# 计算准确率
accuracy = float(num_correct) / X_test.shape[0]
print('Got %d/%d correct=>accuracy:%f'% (num_correct, X_test.shape[0], accuracy))
最终模型预测的准确率为0.977778,45个中分类正确44个。
(2)调用sk-learn实现K-NN
上面的代码是我们根据原理直接写的python实现的代码。在一般的工程中,我们也会直接调用sk-learn里面的模块来直接求解分类问题。
# 导入KneighborsClassifier模块
from sklearn.neighbors import KNeighborsClassifier
# 创建k近邻实例
knn_model = KNeighborsClassifier(n_neighbors=10)
# k近邻模型拟合
knn_model.fit(X_train, y_train)
# k近邻模型预测
y_pred = knn_model.predict(X_test)
# 预测结果数组重塑
y_pred = y_pred.reshape((-1, 1))
# 统计预测正确的个数
num_correct = np.sum(y_pred == y_test)
# 计算准确率
accuracy = float(num_correct) / X_test.shape[0]
print('Got %d / %d correct => accuracy: %f' % (num_correct, X_test.shape[0], accuracy))
直接调用sk-learn的KNeighborsClassifier分类器得到的结果和我们直接用原理求解的结果是一模一样的。