入门demo1 k临近算法

1、k-近邻法简介

k近邻法(k-nearest neighbor, k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。

它的工作原理是：存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。

输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。

一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。

最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

2、距离度量

我们已经知道k-近邻算法根据特征比较，然后提取样本集中特征最相似数据(最邻近)的分类标签。

那么，如何进行比较呢？比如，我们还是以表1.1为例，怎么判断红色圆点标记的电影所属的类别呢？ 如下图所示。

我们可以从散点图大致推断，这个红色圆点标记的电影可能属于动作片，因为距离已知的那两个动作片的圆点更近。

k-近邻算法用什么方法进行判断呢？没错，就是距离度量。这个电影分类的例子有2个特征，也就是在2维实数向量空间，

可以使用我们高中学过的两点距离公式计算距离，

通过计算可知，红色圆点标记的电影到动作片 (108,5)的距离最近，为16.55。

如果算法直接根据这个结果，判断该红色圆点标记的电影为动作片，这个算法就是最近邻算法，

而非k-近邻算法。那么k-近邻算法是什么呢？k-近邻算法步骤如下：

1. 计算已知类别数据集中的点与当前点之间的距离；
2. 按照距离递增次序排序；
3. 选取与当前点距离最小的k个点；
4. 确定前k个点所在类别的出现频率；
5. 返回前k个点所出现频率最高的类别作为当前点的预测分类。

比如，现在我这个k值取3，那么在电影例子中，按距离依次排序的三个点分别是动作片(108,5)、动作片(115,8)、爱情片(5,89)。

在这三个点中，动作片出现的频率为三分之二，爱情片出现的频率为三分之一，所以该红色圆点标记的电影为动作片。这个判别过程就是k-近邻算法。

3、Python3代码实现

(1) 准备数据集合

对于表1.1中的数据，我们可以使用numpy直接创建，代码如下：

结果内容如下。

(2)k-近邻算法

根据两点距离公式，计算距离，选择距离最小的前k个点，并返回分类结果。

数据输出结果：

group [[  1 101]
 [  5  89]
 [108   5]
 [115   8]]
labels ['爱情片', '爱情片', '动作片', '动作片']
datasetsize 4
diffmat  [[100 -81]
 [ 96 -69]
 [ -7  15]
 [-14  12]]
sqdiffmat [[10000  6561]
 [ 9216  4761]
 [   49   225]
 [  196   144]]
sqdistances [16561 13977   274   340]
distances [ 128.68954892  118.22436297   16.55294536   18.43908891]
sortedDistIndices [2 3 1 0]
 voteIlabel 0 动作片
classCount[voteIlabel]  1
 voteIlabel 1 动作片
classCount[voteIlabel]  2
 voteIlabel 2 爱情片
classCount[voteIlabel]  1
sortedClassCount [('动作片', 2), ('爱情片', 1)]
动作片

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！