硬核机器学习干货,手把手教你写KNN! (2)

  k-近邻算法(k-Nearest Neighbour algorithm),又称为KNN算法,是数据挖掘技术中原理最简单的算法。KNN的工作原理:给定一个已知标签类别的训练数据集,输入没有标签的新数据后,在训练数据集中找到与新数据最邻近的k个实例,如果这k个实例的多数属于某个类别,那么新数据就属于这个类别。可以简单理解为:由那些离X最近的k个点来投票决定X归为哪一类。

图1

图1中有红色三角和蓝色方块两种类别,我们现在需要判断绿色圆点属于哪种类别

当k=3时,绿色圆点属于红色三角这种类别;

当k=5时,绿色圆点属于蓝色方块这种类别。

 

  举个简单的例子,可以用k-近邻算法分类一个电影是爱情片还是动作片。(打斗镜头和接吻镜头数量为虚构)

电影名称打斗镜头接吻镜头电影类型
无问西东   1   101   爱情片  
后来的我们   5   89   爱情片  
前任3   12   97   爱情片  
红海行动   108   5   动作片  
唐人街探案   112   9   动作片  
战狼2   115   8   动作片  
新电影   24   67    
表1 每部电影的打斗镜头数、接吻镜头数和电影分类

  表1就是我们已有的数据集合,也就是训练样本集。这个数据集有两个特征——打斗镜头数和接吻镜头数。除此之外,我们也知道每部电影的所属类型,即分类标签。粗略看来,接吻镜头多的就是爱情片,打斗镜头多的就是动作片。以我们多年的经验来看,这个分类还算合理。如果现在给我一部新的电影,告诉我电影中的打斗镜头和接吻镜头分别是多少,那么我可以根据你给出的信息进行判断,这部电影是属于爱情片还是动作片。而k-近邻算法也可以像我们人一样做到这一点。但是,这仅仅是两个特征,如果把特征扩大到N个呢?我们人类还能凭经验“一眼看出”电影的所属类别吗?想想就知道这是一个非常困难的事情,但算法可以,这就是算法的魅力所在。

  我们已经知道k-近邻算法的工作原理,根据特征比较,然后提取样本集中特征最相似数据(最近邻)的分类标签。那么如何进行比较呢?比如表1中新出的电影,我们该如何判断他所属的电影类别呢?如图2所示。

图2 电影分类

  我们可以从散点图中大致推断,这个未知电影有可能是爱情片,因为看起来距离已知的三个爱情片更近一点。k-近邻算法是用什么方法进行判断呢?没错,就是距离度量。这个电影分类例子中有两个特征,也就是在二维平面中计算两点之间的距离,就可以用我们高中学过的距离计算公式:

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwdwpw.html