1.前言
image.png
众所周知，电影可以按照题材分类，然而题材本身是如何定义的？由谁来判定某部电影属于哪个题材？也就是说同一题材的电影具有哪些公共特征？这些都是在进行电影分类时必须要考虑的问题。
我们知道爱情片中的亲吻镜头更多，动作片中的打斗场景也更频繁，基于此类场景在某部电影中出现的次数可以进行电影分类。
本文就基于电影中出现的亲吻、打斗出现的次数，使用k-近邻算法构造程序，自动划分电影的题材类型。之后，我们学习如何在其他系统上使用k-近邻算法。
2.k-近邻算法概述
简单的说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。
优点：精度高、对异常值不敏感、无数据输入假定。
缺点：计算复杂度高、空间复杂度高。
适用数据范围：数值型和标称型。
它的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。
一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
3.案例实践
现在我们回到前面电影分类的例子，使用k-近邻算法分类爱情片和动作片。有人曾经统计过很多电影的打斗镜头和接吻镜头。下图显示了6部电影的打斗和接吻镜头数：
image.png
下图中问号位置是该未知电影出现的镜头图形化展示：
image.png
即使不知道未知电影属于哪种类型，我们也可以通过某种方法计算出来。首先计算未知电影与样本集中其他电影的距离，具体计算方法为欧氏距离:
image.png
例如：未知电影与样本1：California Man的距离：
image.png
全部计算距离如下表：
image.png
现在我们得到了样本集中所有电影与未知电影的距离，按照距离递增排序，可以找到k个距离最近的电影。假定k=3，则三个最靠近的电影依次是He's Not Really into Dudes、Beautiful Woman和California Man。k-近邻算法按照距离最近的三部电影的类型，决定未知电影的类型，而这三部电影全是爱情片，因此我们判定未知电影是爱情片。
下面我们用代码实现：
from numpy import *
import operator
def createdataset(): #构建电影数据集
group = array([[3, 104], [2, 100], [1, 81], [101, 10],[99,5]，[98,2]])
labels=['love_movie','love_movie','love_movie','action_movie','action_movie','action_movie']
return group,labels
def classify0(inx,dataset,labels,k):
datasetsize=dataset.shape[0]
diffmat=tile(inx,(datasetsize,1))-dataset
sqdiffmat=diffmat**2
sqdistances=sqdiffmat.sum(axis=1)
distances=sqdistances**0.5
sorteddistindicies=distances.argsort()
classcount={}
for i in range(k):
voteilabel=labels[sorteddistindicies[i]]
classcount[voteilabel]=classcount.get(voteilabel,0)+1
sortedclasscount=sorted(classcount.items(),key=operator.itemgetter(1),reverse=True)
return sortedclasscount[0][0]
if __name__ == '__main__':
group,labels=createdataset()
print(classify0([18,90],group,labels,3))#输入测试数据，k取3
4.小结
k-近邻算法的一般流程：
（1）收集数据：可以使用任何方法
（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式。
（3）分析数据：可以使用任何方法。
（4）训练算法：此步骤不适用k-近邻算法。
（5）测试算法：计算错误率。
（6）使用算法：首先需要输入样本数据和结构化的输出结果，然后运行k-近邻算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续的处理。
网友评论