KNN-K近邻算法

一、背景

​ 电影可以按照题材分类,然而题材本身是如何定义的?由谁来判定某部电影属于哪个题材?也就是说同一题材的电影具有哪些公共特征?这些都是在进行电影分类时必须要考虑的问题。没有哪个电影人会说自己制作的电影和以前的某部电影类似,但我们确实知道每部电影在风格上的确有可能会和同题材的电影相近。那么动作片具有哪些共有特征,使得动作片之间非常类似,而与爱情片存在着明显的差别呢?动作片中也会存在接吻镜头,爱情片中也会存在打斗场景,我们不能单纯依靠是否存在打斗或者亲吻来判断影片的类型。 但是爱情片中的亲吻镜头更多,动作片中的打斗场景也更频繁,基于此类场景在某部电影中出现的次数可以用来进行电影分类。

二、k-邻近算法概述

​ 存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般来说,我们只选择样本数据集中前k个最相似的数据,这就是k-近邻算法中k的出处,通常k是不大于20的整数。最后,选择k个最相似数据中出现次数最多的类,作为新数据的分类。

​ 还是以电影举例,下表表示了几个电影的打斗镜头和接吻镜头数量以及电影类型:

电影名称打斗镜头接吻镜头电影类型
a3104爱情片
b2100爱情片
c181爱情片
d10110动作片
e995动作片
f982动作片

(电影是数据,电影类型是分类,打斗镜头和接吻镜头是特征)

​ 那么,现在有个新的电影x,它的打斗镜头和接吻镜头分别为1890,问它应该是什么类型电影?

直接分别计算电影x和上表电影的距离,距离计算如下:

以x和a举例:
$$\sqrt{(3-18)^2+(104-90)^2}=20.5$$
所有算出结果为:

电影名称与电影x的距离
a20.5
b18.7
c19.2
d115.3
e117.4
f118.9

​ 然后按距离递增的顺序排序,找到k个距离最近的电影 。这里设k=4,距离最近的4个电影为:bcad。k近邻算法按照距离最近的四部电影的类型,决定未知电影的类型,而这四部电影中有三部是爱情片,因此我们判定电影x是爱情片。

三、k近邻算法的一般流程

  1. 收集数据: 可以使用任何方法。
  2. 准备数据: 距离计算所需要的数值,最好是结构化的数据格式
  3. 分析数据: 可以使用任何方法。
  4. 训练算法: 此步骤不适用于k近邻算法。
  5. 测试算法: 计算错误率。
  6. 使用算法: 首先需要输入样本数据和结构化的输出结果,然后运行k近邻算法判定输入数据分别属于哪个分类,最后应用对计算出的分类执行后续的处理。

四、python实例

from numpy import *
import operator


def createdataset():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels

先导入numpy包和运算符模块,

createdataset()函数创建数据集和标签:grouplabels

def classify0(inX, dataset, labels, k):
    dataset_size = dataset.shape[0]
    # (以下)距离计算
    diff_mat = tile(inX, (dataset_size, 1)) - dataset  # 做差
    sq_diff_mat = diff_mat**2 # 平方
    sq_distances = sq_diff_mat.sum(axis=1)  # 求和
    distances = sq_distances**0.5  # 开根号
    sorted_dist_ind = distances.argsort()
    class_count = {}
    #(以下)选择距离最小的k个点
    for i in range(k):
        votellabel = labels[sorted_dist_ind[i]]
        class_count[votellabel] = class_count.get(votellabel, 0) + 1
    sorted_class_count=sorted(class_count.items(),key=operator.itemgetter(1),
                              reverse=True)
    return sorted_class_count[0][0]


group, labels = createdataset()
print(classify0([0, 0], group, labels, 3))

classify0()函数有4个输入参数:用于分类的输入向量是inX,输入的训练样本集为dataset,标签向量为labels, 最后的参数k表示用于选择最近邻居的数目,其中标签向量的元素数目和矩阵dataset的行数相同。

grouplabels作为数据和标签,下面我以实际数据解释代码。

group的结果是:

image-20191105173527404

labels的结果为:

image-20191105173623894

dataset.shape 用于取出行数,即数据个数。在这里等于4。

tile函数目的在于构造出新的数组与dataset维度保持一致,tile函数的用法具体见:tile的用法

tile(inX, (dataset_size, 1))的结果为:

image-20191105174125487

接下来对数组求平方,求和,开根号得到距离。
class_count.get(votellabel, 0)get函数用来获取键votellabel的值,如果不存在,设置为0。
sorted排序,itemgetter(1)表示按值排序,reverse=True表示反向排序。

本文作者:Author:     文章标题:KNN-K近邻算法
本文地址:https://www.ningcaichen.top/archives/82.html     
版权说明:若无注明,本文皆为“宁采晨's Blog”原创,转载请保留文章出处。
Last modification:2019 年 11 月 13 日 09 : 51 AM

Leave a Comment

召唤看板娘