机器学习之Knn（C语言描述）_knnc语言代码

《统计学习方法2》

第二章 K 近邻法

前言

最近拜读了机器学习领域，经典书籍，李航老师的《统计学习方法》，深受裨益。现实现算法，记录分享。

一、$k$-NN 是什么？

$k$ 近邻法是一种基本的分类与回归方法。它的输入是实例的特征向量，对应于特征空间的点，输出是实例的类别，可以是多分类。计算输入实例特征向量，与训练集中每个实例特征向量的欧式距离，得到距离最接近的 $k$ 个实例，使用投票的方式预测输入实例的类别。

二、$k$-NN 算法

1、假设有训练集：
$$T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\}$$
其中，$x_i⊊X\subseteq R^n$ 为实例的特征向量， y i ⊊ Y = { c 1 , c 2 , . . c k } y_i\subsetneq Y = \{c_1, c_2, ..c_k\} yi​⊊Y={c1​,c2​,..ck​} 为实例的类别。

2、计算输入实例与训练集中的实例欧式距离：
$$L_2=(\sum _{l=1}^n|x_i^{(l)}-x_j^{(l)}|{)}^{\frac{1}{2}}$$

3、取前 $k$ 个最小的实例，根据它对应的类别进行投票，其结果将预测输入实例的类别。

三、上代码

以下是 $k$-NN 伪代码

// C 式伪代码
int knn_predict（matrix_t* data, matrix_t* label, matrix_t* _Input, int K）
{
	//定义K个最近的 neighbor 数组。
	float neighbor_dist[K];
	// 定义K个最近 neighbor 类别的数组。
	int neighbor_cls[k];
	
	for (i : data->rows) {
		// 获取第 i 个实例
		matrix_t* Xi = data[i];
		// 获取第 i 个实例的类别
		float dist = calculate_distance(Xi, _Input);
		int cls    = label[i];
		
		//把 dist 与 type 插入并且排序。
		insert_sort(neighbor_dist, neighbor_cls, dist, cls);
	}
	// 投票输出 _Input 的类别。
	int class = vote_class(neighbor_cls);
	return class;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

源码：https://github.com/zuweie/boring-code/blob/main/src/statistical_learning/knn.c

总结

$k$-NN 应该算是所有的机器学习方法中最简单的算法。其算法的有点是，训练即推理，使用简单，开箱即用，缺点是慢，因为每次推理等于是再训练一次。

完