1.前言

image.png

眾所周知，電影可以按照題材分類，然而題材本身是如何定義的？由誰來判定某部電影屬于哪個題材？也就是說同一題材的電影具有哪些公共特征？這些都是在進行電影分類時必須要考慮的問題。

我們知道愛情片中的親吻鏡頭更多，動作片中的打斗場景也更頻繁，基于此類場景在某部電影中出現(xiàn)的次數(shù)可以進行電影分類。

本文就基于電影中出現(xiàn)的親吻、打斗出現(xiàn)的次數(shù)，使用k-近鄰算法構(gòu)造程序，自動劃分電影的題材類型。之后，我們學習如何在其他系統(tǒng)上使用k-近鄰算法。

2.k-近鄰算法概述

簡單的說，k-近鄰算法采用測量不同特征值之間的距離方法進行分類。

優(yōu)點：精度高、對異常值不敏感、無數(shù)據(jù)輸入假定。
缺點：計算復雜度高、空間復雜度高。
適用數(shù)據(jù)范圍：數(shù)值型和標稱型。

它的工作原理是：存在一個樣本數(shù)據(jù)集合，也稱作訓練樣本集，并且樣本集中每個數(shù)據(jù)都存在標簽，即我們知道樣本集中每一數(shù)據(jù)與所屬分類的對應關(guān)系。輸入沒有標簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個特征與樣本集中數(shù)據(jù)對應的特征進行比較，然后算法提取樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標簽。

一般來說，我們只選擇樣本數(shù)據(jù)集中前k個最相似的數(shù)據(jù)，這就是k-近鄰算法中k的出處，通常k是不大于20的整數(shù)。最后，選擇k個最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類。

3.案例實踐

現(xiàn)在我們回到前面電影分類的例子，使用k-近鄰算法分類愛情片和動作片。有人曾經(jīng)統(tǒng)計過很多電影的打斗鏡頭和接吻鏡頭。下圖顯示了6部電影的打斗和接吻鏡頭數(shù)：

image.png

下圖中問號位置是該未知電影出現(xiàn)的鏡頭圖形化展示：

image.png

即使不知道未知電影屬于哪種類型，我們也可以通過某種方法計算出來。首先計算未知電影與樣本集中其他電影的距離，具體計算方法為歐氏距離:

image.png

例如：未知電影與樣本1：California Man的距離：

image.png

全部計算距離如下表：

image.png

現(xiàn)在我們得到了樣本集中所有電影與未知電影的距離，按照距離遞增排序，可以找到k個距離最近的電影。假定k=3，則三個最靠近的電影依次是He's Not Really into Dudes、Beautiful Woman和California Man。k-近鄰算法按照距離最近的三部電影的類型，決定未知電影的類型，而這三部電影全是愛情片，因此我們判定未知電影是愛情片。

下面我們用代碼實現(xiàn)：

from numpy import *
import operator

def createdataset():    #構(gòu)建電影數(shù)據(jù)集
      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))#輸入測試數(shù)據(jù)，k取3

4.小結(jié)

k-近鄰算法的一般流程：

（1）收集數(shù)據(jù)：可以使用任何方法
（2）準備數(shù)據(jù)：距離計算所需要的數(shù)值，最好是結(jié)構(gòu)化的數(shù)據(jù)格式。
（3）分析數(shù)據(jù)：可以使用任何方法。
（4）訓練算法：此步驟不適用k-近鄰算法。
（5）測試算法：計算錯誤率。
（6）使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運行k-近鄰算法判定輸入數(shù)據(jù)分別屬于哪個分類，最后應用對計算出的分類執(zhí)行后續(xù)的處理。