K近邻算法是一种基于距离度量的数据分类模型，其基本做法是首先确定输入实例的[插图]个最近邻实例，然后利用这[插图]个训练实例的多数所属的类别来预测新的输入实例所属类别。
k最近邻（k-nearest neighbors，KNN）算法是一种基本的分类和回归算法。其基本原理如下：
1. 训练阶段：将训练样本集中的数据和对应的标签存储起来，构建一个训练模型。
2. 预测阶段：对于一个新的测试样本，计算它与训练样本集中所有样本的距离（通常使用欧氏距离或其他距离度量方法）。
3. 选择k个最近邻：根据距离计算结果，选择与测试样本距离最近的k个训练样本。
4. 进行投票或计算平均值：对于分类任务，根据k个最近邻的标签进行投票，将得票最多的标签作为测试样本的预测标签。对于回归任务，根据k个最近邻的标签或值进行平均计算，将计算结果作为测试样本的预测值。
KNN算法的关键是选择合适的k值和距离度量方法。k值的选择会影响算法的性能，较小的k值可能会导致过拟合，较大的k值可能会导致欠拟合。距离度量方法的选择应根据具体问题和数据特点进行合理选择。
KNN算法的优点包括简单易懂、易于实现、适用于多分类和回归问题。然而，KNN算法的缺点是计算复杂度高，对于大规模数据集的预测速度较慢。此外，KNN算法对于特征空间的维度敏感，需要进行特征选择或降维等预处理操作。
# 导入相关模块
import numpy as np
from collections import Counter
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.utils import shuffle
### 定义欧氏距离
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)
"""
>>> import numpy as np
>>> a = np.array([[1,2,3],[4,5,6]])
>>> np.sum(a)
21
>>> np.sum(a, axis=0)
array([5, 7, 9])
>>> np.sum(a, axis=1)
array([ 6, 15])
X = np.array([[1, 2, 3],
[4, 5, 6],
[7, 8, 9]])
==>np.square(X).sum(axis=1) 结果为 [14 77 194]
"""
# 训练样本矩阵平方
tr = np.square(X_train).sum(axis=1)
# 计算欧式距离
dists = np.sqrt(-2 * M + tr + np.matrix(te).T) # 自己可以简单推导下 的确如此
return dists
### 定义预测函数
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
"""
>>> x = np.array([3, 1, 2])
>>> np.argsort(x)
array([1, 2, 0])
# 创建计数对象
>>> c = Counter('abcdeabcdabcaba')
# 取计数前三的元素
>>> c.most_common(3)
[('a', 5), ('b', 4), ('c', 3)]
"""
# 导入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)
dists = compute_distances(X_test, X_train)
# 测试集预测结果
y_test_pred = predict_labels(y_train, dists, k=10)
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('KNN Accuracy based on NumPy: ', accuracy)
# 导入KNeighborsClassifier模块
from sklearn.neighbors import KNeighborsClassifier
# 创建k近邻实例
neigh = KNeighborsClassifier(n_neighbors=10)
# k近邻模型拟合
neigh.fit(X_train, y_train)
# k近邻模型预测
y_pred = neigh.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('KNN Accuracy based on sklearn: ', accuracy)
运行结果：
X_train= (105, 4)
X_test= (45, 4)
y_train= (105, 1)
y_test= (45, 1)
KNN Accuracy based on NumPy: 0.9777777777777777
KNN Accuracy based on sklearn: 0.9777777777777777
其中，计算举例的可以使用下面更加简洁的函数：
def compute_distances(X, X_train):
num_test = X.shape[0]
num_train = X_train.shape[0]
dists = np.zeros((num_test, num_train))
for i in range(num_test):
for j in range(num_train):
dists[i, j] = np.sqrt(np.sum(np.square(X[i] - X_train[j])))
return dists
predict我自己写的话，是下面这样：
def predict_labels(y_train, dists, k=1):
num_test = dists.shape[0]
y_pred = np.zeros(num_test)
for i in range(num_test):
sorted_indices = np.argsort(dists[i])
closest_y = y_train[sorted_indices[:k]].flatten()
y_pred[i] = Counter(closest_y).most_common()[0][0]
return y_pred