KNN

引入

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

分类

分类问题是机器学习中两大主流问题之一，在深度学习没有像今天一样火爆的时候，大家是怎样进行分类学习的呢？

本文介绍第一个机器学习算法： k-近邻算法，它非常有效而且易于掌握。首先，我们将探讨k-近邻算法的基本理论，以及如何使用距离测量的方法分类物品

介绍

简单地说，KNN算法是度量输入与样本之间的距离来进行分类的一种算法，主要思想是“近朱者赤，近墨者黑”，离得近，则就认为是同一类。

对于一个电影，我们可以对它的特征——亲吻场面次数、打斗场面次数进行统计，显然在爱情片和动作片上二者的表现不应该是完全相同的，而且很大可能是呈现出“各执一词”的状态。

算法实现

  • 生成训练样本和标签
  • 计算输入和每一个样本之间的距离
  • 取距离最大的前 k 个
  • 看这k个中对应的自己的类别都是谁
  • 区类别出现频率最高的

我们可以认为的思考上述方法的合理性，离得近就认为是同一类，进而出现的次数多就认为是某一类，是合乎情理的，接下来我们来验证一下，简单起见，我们使用简单的数据集进行象征性描述

  • 两个维度分别记录一部电影打斗和亲吻的次数
  • 标签记录该电影的类别
1
2
3
4
def create_dataset():
    train = np.array([[3, 104], [2, 100], [1, 81], [101, 10], [99, 5], [98, 2]])
    labels = ['Love', 'Love', 'Love', 'Fight', 'Fight', 'Fight']
    return train, labels
  • 进行分类
  • 将输入扩充，方便和每一个样本求距离
  • 对距离的下标进行排序
  • 对于距离最近的 k 个样本
  • 记录对应类别的个数
  • 返回最多的类别
1
2
3
4
5
6
7
8
9
10
11
12
def classify(inx, dataset, labels, k):
    n, most = dataset.shape[0], 0
    dis = (((np.tile(inx, (n, 1)) - dataset) ** 2).sum(axis=1)) ** 0.5
    idx = dis.argsort()
    cnt = {}
    for i in range(k):
        label = labels[idx[i]]
        cnt[label] = cnt.get(label, 0) + 1
        most = max(most, cnt[label])
    for x in cnt:
        if cnt[x] == most:
            return x
  • 测试，输入 <80, 5> ，预期结果应该是 Fight
1
2
3
4
5
6
7
def main():
    train, labels = create_dataset()
    print(classify([60, 1], train, labels, 3))


if __name__ == '__main__':
    main()