前言
眾所周知趟咆，電影可以按照題材分類，那么如何判定某部電影屬于某個(gè)題材呢渺蒿？同一題材的電影具有那些公共特征痢士？這是需要在分類電影時(shí)考慮的問題。
那么動(dòng)作片具有哪些公共特征茂装？又與愛情片存在哪些明顯差別呢怠蹂？動(dòng)作片也存在親吻鏡頭，愛情片也存在打斗鏡頭少态，所以不能單純從是否存在打斗或者親吻鏡頭來判斷城侧。但愛情片親吻鏡頭比動(dòng)作片多，同樣動(dòng)作片打斗鏡頭更多彼妻。下面將基于電影中出現(xiàn)的親吻嫌佑、打斗次數(shù)，使用kNN（k-Nearest-Neighbor侨歉，k-近鄰） 算法劃分電影題材類型屋摇。
kNN容易理解掌握，本文首先使用電影分類講解kNN算法的基本概念为肮，了解其基本理論摊册。在最后會(huì)利用實(shí)際例子講解如何用kNN改進(jìn)約會(huì)配對(duì)和手寫數(shù)字識(shí)別。
kNN概述
- 優(yōu)點(diǎn)：精度高颊艳、對(duì)異常值不敏感茅特、無數(shù)據(jù)輸入假定
- 缺點(diǎn)：計(jì)算復(fù)雜度高、空間復(fù)雜度高
- 適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型
kNN算法通過測(cè)量不同特征值之間的距離來進(jìn)行分類棋枕。
工作原理：存在一個(gè)已知類別的訓(xùn)練集（即每個(gè)數(shù)據(jù)都存在標(biāo)簽）白修。輸入沒有標(biāo)簽的新數(shù)據(jù)，將新數(shù)據(jù)的每個(gè)特征與訓(xùn)練集每個(gè)數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較重斑，計(jì)算距離兵睛，選擇前k個(gè)最相似的數(shù)據(jù)（k-近鄰中k的出處），提取分類標(biāo)簽窥浪，選擇k個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類祖很，作為新數(shù)據(jù)的分類。
用中國(guó)俗語(yǔ)解釋就是“近朱者赤近墨者黑”漾脂。
現(xiàn)在回到電影分類的例子假颇，有人曾統(tǒng)計(jì)過很多電影的打斗鏡頭和親吻鏡頭，如下表顯示了6部電影的打斗和親吻鏡頭數(shù)骨稿，還有一部只知道鏡頭數(shù)的未知電影笨鸡。
| 電影名稱 | 打斗鏡頭 | 親吻鏡頭 | 電影類型 |
|---|---|---|---|
| California Man | 3 | 104 | 愛情片 |
| He's Not Really into Dudes | 2 | 100 | 愛情片 |
| Beautiful Woman | 1 | 81 | 愛情片 |
| Kevin Longblade | 101 | 10 | 動(dòng)作片 |
| Robo Slayer 30000 | 99 | 5 | 動(dòng)作片 |
| Amped II | 98 | 2 | 動(dòng)作片 |
| 姜钳？ | 18 | 90 | 未知 |
接下來，我們將使用kNN來對(duì)未知電影進(jìn)行分類形耗。首先計(jì)算未知電影與其他電影的距離哥桥，如下表。
| 電影名稱 | 與未知電影的距離 |
|---|---|
| California Man | 20.5 |
| He's Not Really into Dudes | 18.7 |
| Beautiful Woman | 19.2 |
| Kevin Longblade | 115.3 |
| Robo Slayer 30000 | 117.4 |
| Amped II | 118.9 |
得到樣本集中所有電影與未知電影的距離后激涤，按距離遞增排序拟糕，找到k個(gè)距離最近的電影。假定k=3昔期，則三個(gè)最接近的電影是California Man已卸、He's Not Really into Dudes和Beautiful Woman佛玄，而這三部電影都是愛情片硼一，因此我們判定未知電影類型是愛情片。
現(xiàn)在我們大概了解了kNN的工作原理梦抢。接下來就是代碼實(shí)踐了般贼。
kNN算法代碼實(shí)現(xiàn)
import numpy as np
import operator
def classify0(inX, dataSet, labels, k):
'''
inX：未知分類的輸入向量
dataSet：訓(xùn)練樣本集
labels：訓(xùn)練集的標(biāo)簽向量
k：最近鄰居的數(shù)目
'''
dataSetSize = dataSet.shape[0]
# 距離計(jì)算
# tile：重復(fù)inX
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
sqDistances = sqDiffMat.sum(axis = 1)
distances = sqDistances ** 0.5
# 排序，返回排序后index
sortedDistIndicies = distances.argsort()
classCount = {}
# 選擇距離最小的k個(gè)點(diǎn)
for i in range(k):
voteIlabel = labels[sortedDistIndicies[I]]
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# 根據(jù)出現(xiàn)次數(shù)排序
sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse=True)
# 返回出現(xiàn)頻率最高的標(biāo)簽
return sortedClassCount[0][0]
代碼中的距離計(jì)算使用歐式距離公式奥吩，計(jì)算A和B兩個(gè)點(diǎn)之間的距離：
接下來就是應(yīng)用這個(gè)kNN分類器哼蛆，看看它的分類效果如何。
示例：約會(huì)網(wǎng)站的配對(duì)
樣本主要有三個(gè)特征：
- 每年獲得的飛行诚己眨客里程數(shù)
- 玩視頻游戲所耗時(shí)間百分比
- 每周消費(fèi)的冰淇淋公升數(shù)
import numpy as np
# 加載數(shù)據(jù)
def loadDataSet(filename):
fr = open(filename)
arrayOLines = fr.readlines()
numberOfLines = len(arrayOLines) # 數(shù)據(jù)行數(shù)
returnMat = np.zeros((numberOfLines, 3))
classLabelVector = []
index = 0
# 解析文件數(shù)據(jù)
for line in arrayOLines:
line = line.strip().split('\t')
returnMat[index, :] = line[0:3]
classLabelVector.append(int(line[-1]))
index += 1
return returnMat, classLabelVector
使用matplotlib創(chuàng)建散點(diǎn)圖
# 數(shù)據(jù)展示
import matplotlib.pyplot as plt
# 解決中文圖例亂碼
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus']=False
datingDataMat, datingLabels = loadDataSet('datingTestSet2.txt')
x1, y1 = [],[]
x2, y2 = [],[]
x3, y3 = [],[]
for i in range(datingDataMat.shape[0]):
if datingLabels[i] == 1:
x1.append(datingDataMat[i,0])
y1.append(datingDataMat[i,1])
elif datingLabels[i] == 2:
x2.append(datingDataMat[i,0])
y2.append(datingDataMat[i,1])
else:
x3.append(datingDataMat[i,0])
y3.append(datingDataMat[i,1])
fig = plt.figure()
ax = fig.add_subplot(111)
type1 = ax.scatter(x1, y1, s=20, c='red')
type2 = ax.scatter(x2, y2, s=30, c='green')
type3 = ax.scatter(x3, y3, s=50, c='blue')
ax.legend([type1, type2, type3], ["不喜歡", "魅力一般", "極具魅力"], loc=2)
ax.axis([-5000,100000,-2,25])
plt.xlabel('每年獲取的飛行橙椋客里程數(shù)')
plt.ylabel('玩視頻游戲所耗時(shí)間百分比')
plt.show()
歸一化數(shù)據(jù)
下表給出樣本集中的兩組數(shù)據(jù)。
| 每年獲得的飛行扯怂ィ客里程數(shù) | 玩視頻游戲所耗時(shí)間百分比 | 每周消費(fèi)的冰淇淋公升數(shù) | 樣本分類 |
|---|---|---|---|
| 5914 | 2.216246 | 0.587095 | 2 |
| 14851 | 14.305636 | 0.632317 | 3 |
兩組數(shù)據(jù)距離的計(jì)算式為
我們很容易發(fā)現(xiàn)叠洗，上述式子中數(shù)字差值最大的屬性對(duì)計(jì)算結(jié)果影響最大，但實(shí)際上這三種特征是同等重要的旅东。在處理這種不同取值范圍的特征值時(shí)灭抑，我們通常是將數(shù)值歸一化，如將取值范圍處理為0到1或者-1到1之間抵代。
import numpy as np
# 將數(shù)值范圍轉(zhuǎn)化為0到1
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = np.zeros(dataSet.shape)
m = dataSet.shape[0]
normDataSet = dataSet - np.tile(minVals, (m,1))
normDataSet = normDataSet/np.tile(ranges, (m,1))
return normDataSet, ranges, minVals
測(cè)試算法
def datingClassTest():
# 用于劃分測(cè)試集和訓(xùn)練集的比例
hoRatio = 0.1
datingDataMat, datingLabels = loadDataSet('datingTestSet2.txt')
normMat, ranges, minVals = autoNorm(datingDataMat)
m = normMat.shape[0]
# 測(cè)試集數(shù)目
numTestVecs = int(m * hoRatio)
errorCount = 0
for i in range(numTestVecs):
classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
if classifierResult != datingLabels[I]:
errorCount += 1
print("分類器返回結(jié)果：", classifierResult, "實(shí)際結(jié)果：", datingLabels[I])
print("錯(cuò)誤率為：", (errorCount/float(numTestVecs)))
datingClassTest()首先使用loadDataSet和autoNorm從文件中讀取數(shù)據(jù)并進(jìn)行歸一化腾节。然后計(jì)算測(cè)試集的數(shù)量，將測(cè)試集和訓(xùn)練集輸入到kNN分類器classify0荤牍。最后計(jì)算錯(cuò)誤率并輸出結(jié)果案腺。執(zhí)行結(jié)果如下。
分類器返回結(jié)果： 3 實(shí)際結(jié)果： 2
分類器返回結(jié)果： 3 實(shí)際結(jié)果： 1
分類器返回結(jié)果： 3 實(shí)際結(jié)果： 1
分類器返回結(jié)果： 2 實(shí)際結(jié)果： 3
分類器返回結(jié)果： 3 實(shí)際結(jié)果： 1
錯(cuò)誤率為： 0.05
示例：手寫識(shí)別系統(tǒng)
為了簡(jiǎn)單起見康吵，這里只能識(shí)別數(shù)字0到9劈榨。
將圖像轉(zhuǎn)換為測(cè)試向量
實(shí)際圖像存儲(chǔ)在兩個(gè)目錄內(nèi)，目錄trainingDigits包含大約2000個(gè)例子涎才，每個(gè)例子如上圖所示鞋既；目錄testDigits包含900個(gè)測(cè)試數(shù)據(jù)力九。
為了方便計(jì)算，需要將32x32的二進(jìn)制圖像矩陣轉(zhuǎn)換成1x1024的向量邑闺。
import numpy as np
# 將圖像轉(zhuǎn)換為向量
def img2vector(filename):
returnVect = np.zeros((1,1024))
fr = open(filename)
for i in range(32):
lineStr = fr.readline()
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect
測(cè)試算法：使用kNN識(shí)別手寫數(shù)字
import numpy as np
from os import listdir
def handwritingClassTest():
hwLabels = []
trainingFileList = listdir('trainingDigits') # 獲取目錄內(nèi)容
m = len(trainingFileList) # 文件數(shù)
trainingMat = np.zeros((m,1024))
for i in range(m):
# 從文件名中解析分類數(shù)字
fileNameStr = trainingFileList[I]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
hwLabels.append(classNumStr)
trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
testFileList = listdir('testDigits')
errorCount = 0
mTest = len(testFileList)
for i in range(mTest):
fileNameStr = testFileList[I]
fileStr = fileNameStr.split('.')[0]
classNumStr = int(fileStr.split('_')[0])
vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
if (classifierResult != classNumStr):
errorCount += 1
print("分類器返回結(jié)果：", classifierResult, "實(shí)際結(jié)果：", classNumStr)
print('總錯(cuò)誤數(shù)：', errorCount)
print('錯(cuò)誤率：', errorCount/float(mTest))
所有文件按照規(guī)則命名跌前，如文件7_34.txt的分類是7，是數(shù)字7的第34個(gè)實(shí)例陡舅，可以利用這個(gè)規(guī)則提取分類數(shù)字抵乓，然后存儲(chǔ)在hwLabels中。
手寫識(shí)別這里不需要用到歸一化靶衍，因?yàn)橹抵挥?和1灾炭。
執(zhí)行代碼，可以得到如下結(jié)果：
分類器返回結(jié)果： 1 實(shí)際結(jié)果： 8
分類器返回結(jié)果： 3 實(shí)際結(jié)果： 8
分類器返回結(jié)果： 7 實(shí)際結(jié)果： 9
分類器返回結(jié)果： 9 實(shí)際結(jié)果： 3
分類器返回結(jié)果： 1 實(shí)際結(jié)果： 8
分類器返回結(jié)果： 1 實(shí)際結(jié)果： 9
分類器返回結(jié)果： 1 實(shí)際結(jié)果： 8
分類器返回結(jié)果： 7 實(shí)際結(jié)果： 1
分類器返回結(jié)果： 6 實(shí)際結(jié)果： 5
分類器返回結(jié)果： 3 實(shí)際結(jié)果： 5
分類器返回結(jié)果： 6 實(shí)際結(jié)果： 8
總錯(cuò)誤數(shù)： 11
錯(cuò)誤率： 0.011627906976744186
kNN算法識(shí)別手寫數(shù)字的錯(cuò)誤率為1.2%颅眶。通過改變k值蜈出、訓(xùn)練集和測(cè)試集的數(shù)目，都會(huì)對(duì)錯(cuò)誤率產(chǎn)生影響涛酗。
小結(jié)
kNN是分類數(shù)據(jù)最簡(jiǎn)單有效的算法铡原。
kNN必須保存全部數(shù)據(jù)集，如果訓(xùn)練集很大商叹，必須使用大量的存儲(chǔ)空間燕刻。
由于必須對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)計(jì)算距離，實(shí)際使用會(huì)非常耗時(shí)剖笙。
都看到最后了卵洗，要不~點(diǎn)個(gè)贊？加波關(guān)注弥咪？
