廢話
在實(shí)際工作中，我們經(jīng)常會(huì)碰到需要對(duì)一些數(shù)據(jù)進(jìn)行簡(jiǎn)單分類，舉幾個(gè)例子：
- 我們經(jīng)常會(huì)對(duì)一些評(píng)論內(nèi)容進(jìn)行情感分析，分析出評(píng)論內(nèi)容是高興、悲傷、表?yè)P(yáng)或是批評(píng)；
- 在醫(yī)療行業(yè)我們會(huì)對(duì)一些患者的醫(yī)學(xué)影響進(jìn)行分析，分析出該患者是幾級(jí)傷殘、是否患有癌癥、癌癥程度等等；
- 在音樂(lè)方面我們要對(duì)音樂(lè)進(jìn)行歸類，分析出該音樂(lè)屬于經(jīng)典、民謠、流行、傷感中的哪一種；
- 垃圾郵件過(guò)濾；
- 在電影方面我們要對(duì)電影屬于愛(ài)情片、動(dòng)作片、科幻片中的哪一種進(jìn)行分類；
- 在視頻直播中需要對(duì)視頻直播中的內(nèi)容進(jìn)行分類，以更加準(zhǔn)確的監(jiān)控直播內(nèi)容的合法性；
那么今天給大家介紹的k-近鄰算法是分類數(shù)據(jù)最簡(jiǎn)單、最基礎(chǔ)、最有效的算法。
概述
k-近鄰即kNN（k-NearestNeighbor）k個(gè)最近的鄰居的意思，說(shuō)的是每個(gè)樣本都可以用它最接近的k個(gè)鄰居來(lái)代表。
kNN算法的核心思想是如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別，并具有這個(gè)類別上樣本的特性。該方法在確定分類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。 kNN方法在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。由于kNN方法主要靠周?chē)邢薜泥徑臉颖荆皇强颗袆e類域的方法來(lái)確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，kNN方法較其他方法更為適合。
場(chǎng)景
我們回到上面將電影分類的例子中， 我們想一想愛(ài)情片和動(dòng)作片中哪些特點(diǎn)會(huì)有明顯的不同。kiss鏡頭數(shù)、打斗鏡頭數(shù)是兩種類型電影里很明顯的差異，那么我們將kiss鏡頭數(shù)和打斗鏡頭數(shù)作為區(qū)分兩種類型影片的依據(jù)之一。
數(shù)據(jù)準(zhǔn)備
有了上面的場(chǎng)景分析，我們要對(duì)兩種類型的電影進(jìn)行區(qū)分，就需要對(duì)大量的已知分類電影數(shù)據(jù)進(jìn)行標(biāo)注，形成我們的標(biāo)注數(shù)據(jù)。
| 電影名稱 | 打斗鏡頭數(shù) | kiss鏡頭數(shù) | 電影類型 |
|---|---|---|---|
| California Man | 3 | 104 | 愛(ài)情片 |
| He 's Not Really into Dudes | 2 | 100 | 愛(ài)情片 |
| Beautiful Woman | 1 | 81 | 愛(ài)情片 |
| Kevin Longblade | 101 | 10 | 動(dòng)作片 |
| RoboSlayer 3000 | 99 | 5 | 動(dòng)作片 |
| Amped II | 98 | 2 | 動(dòng)作片 |
| ？ | 18 | 90 | ？ |
通過(guò)以上表格很清晰的發(fā)現(xiàn)，愛(ài)情片中kiss鏡頭數(shù)明顯較多，而動(dòng)作片中打斗鏡頭數(shù)明顯較多，同時(shí)我們要分析的則是打斗鏡頭數(shù)為18，kiss鏡頭數(shù)為90的影片類型是什么？
代碼實(shí)現(xiàn)
1.首先進(jìn)行數(shù)據(jù)準(zhǔn)備
'''
基礎(chǔ)數(shù)據(jù)
'''
def createDataSet():
group = arry([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]])
labels = ['愛(ài)情片','愛(ài)情片','愛(ài)情片','動(dòng)作片','動(dòng)作片','動(dòng)作片']
return group,labels
'''
分類算法
:param inX:分類輸入向量，即[18,90]
:param dataSet:準(zhǔn)備的矩陣數(shù)據(jù)集
:param labels:對(duì)應(yīng)影片類型
:param k:最鄰近數(shù)目
: return:分類類型
'''
def classify(inX,dataSet,labels,k) :
dataSetSize = dataSet.shape[0]#獲取矩陣長(zhǎng)度6
#1.在列方向上重復(fù)6次，行上一次，即arry([[18,90],[18,90],[18,90],[18,90],[18,90],[18,90]])
#2.兩個(gè)矩陣相減
diffMat = tile(inX,(dataSet,1))-dataSet
sqDiffMat = diffMat**2
sqDistances = sqDiffMat.sum(axis=1)#矩陣的平方
distances = sqDistances**0.5#開(kāi)根號(hào)
sortedDistIndicies = distances.argsort()#返回distances從小到大的索引值
classCount = {}
#選擇距離最小的幾個(gè)點(diǎn)
for i in range(k) :
voteILabel = labels[sortedDistIndicies[i]]#輸出對(duì)應(yīng)索引的類型
classCount[voteILabel] = classCount.get(voteILabel,0)+1#向字典添加該類型
sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
return sortedClassCount[0][0] #返回前3個(gè)近鄰對(duì)應(yīng)類型出現(xiàn)最多的類型名稱
group,labels=createDataSet()
print(classify([18,90],group,labels,3))
###輸出結(jié)果為“愛(ài)情片”
在classify函數(shù)中影片距離是通過(guò)了歐式距離公式進(jìn)行計(jì)算,當(dāng)然計(jì)算距離的方式還有“編輯距離“、“余弦相似度”等等，根據(jù)應(yīng)用場(chǎng)景選擇相應(yīng)的計(jì)算公式。
歐式距離公式 ：d = √(x1-x2)2 +(y1-y2)2
| 電影名稱 | 與未知電影距離 |
| :-----------: | :------------: | :-------------: | :----------------: |
| California Man | 20.5 |
| He 's Not Really into Dudes | 18.7 |
| Beautiful Woman | 19.2 |
| Kevin Longblade | 115.3 |
| RoboSlayer 3000 | 117.4 |
| Amped II | 118.9 |
總結(jié)
在分類算法中，kNN是最簡(jiǎn)單也是最有效的算法，但也有很多缺點(diǎn)，我們?cè)谑褂脮r(shí)必須有接近實(shí)際數(shù)據(jù)的訓(xùn)練樣本數(shù)據(jù)，同時(shí)訓(xùn)練數(shù)據(jù)過(guò)大時(shí)會(huì)消耗大量的計(jì)算時(shí)間，因?yàn)橐總€(gè)數(shù)據(jù)進(jìn)行距離的計(jì)算。所以每種算法在時(shí)間或空間上都有自己的優(yōu)缺點(diǎn)，大家在選擇分類算法時(shí)還得根據(jù)具體的業(yè)務(wù)場(chǎng)景和需要選擇適合的算法。
