k-近鄰算法
先來(lái)一個(gè)簡(jiǎn)單的例子，我們?nèi)绾蝸?lái)區(qū)分動(dòng)作類電影與愛(ài)情類電影呢？動(dòng)作片中存在很多的打斗鏡頭，愛(ài)情片中可能更多的是親吻鏡頭，所以我們姑且通過(guò)這兩種鏡頭的數(shù)量來(lái)預(yù)測(cè)這部電影的主題。簡(jiǎn)單的說(shuō)，k-近鄰算法采用了測(cè)量不同特征值之間的距離方法進(jìn)行分類。
優(yōu)點(diǎn)：精度高、對(duì)異常值不敏感、無(wú)數(shù)據(jù)輸入假定 缺點(diǎn)：計(jì)算復(fù)雜度高、控件復(fù)雜度高 適用數(shù)據(jù)范圍：數(shù)值型和標(biāo)稱型
首先我們來(lái)理解它的工作原理：
存在一個(gè)樣本數(shù)據(jù)集（訓(xùn)練集），并且我們知道每一數(shù)據(jù)與目標(biāo)變量的對(duì)應(yīng)關(guān)系，輸入沒(méi)有標(biāo)簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較，然后算法提取樣本集中最相近的分類標(biāo)簽，一般來(lái)說(shuō)，我們只選擇樣本集中前k個(gè)最相似的數(shù)據(jù)，通常k為不大于20的整數(shù)，最后，選擇k個(gè)最相似數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類。
現(xiàn)在我們回到文章開(kāi)頭所提到的電影的例子，根據(jù)下表如何確定未知的電影類型呢？
電影名稱打斗鏡頭接吻鏡頭電影類型電影13104愛(ài)情電影22100愛(ài)情電影3181愛(ài)情電影410110動(dòng)作電影5995動(dòng)作電影6982動(dòng)作電影71890未知？該如何計(jì)算電影7的電影類型呢？計(jì)算電影7與樣本集中其他電影的距離，然后我們假定k=3，看一下最近的3部電影是什么類型即可預(yù)測(cè)出電影7的電影類型。
流程介紹
- 收集數(shù)據(jù)
- 準(zhǔn)備數(shù)據(jù)：距離計(jì)算所需要的值，最好是結(jié)構(gòu)化的數(shù)據(jù)格式
- 分析數(shù)據(jù)
- 測(cè)試算法：計(jì)算錯(cuò)誤率
- 使用算法
開(kāi)始工作
使用python導(dǎo)入數(shù)據(jù)
首先，創(chuàng)建名為kNN.py的Python模塊，在構(gòu)造算法之前，我們還需要編寫一些通用的函數(shù)等，我們先寫入一些簡(jiǎn)單的代碼：
from numpy import *import operatordef createDataSet(): group = array([ [1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1] ]) labels = ["A", "A", "B", "B"] return group, labels
然后將終端改變到代碼文件目錄，輸入命令python進(jìn)入到交互界面：
>>> import kNN>>> group, labels = kNN.createDataSet()>>> grouparray([[ 1. , 1.1], [ 1. , 1. ], [ 0. , 0. ], [ 0. , 0.1]])>>> labels['A', 'A', 'B', 'B']
這里有4組數(shù)據(jù)，每組數(shù)據(jù)有2個(gè)我們已知的特征值，上面的group矩陣每行為一條數(shù)據(jù)，對(duì)于每個(gè)數(shù)據(jù)點(diǎn)我們通常使用2個(gè)特征（所以特征的選擇很重要），向量labels包含了每個(gè)數(shù)據(jù)點(diǎn)的標(biāo)簽信息，labels的維度等于矩陣的行數(shù)，這里我們將[1, 1,1]定為類A，[0, 0.1]定為類B，接下來(lái)我們進(jìn)行算法的編寫：
- 計(jì)算已知數(shù)據(jù)集中點(diǎn)到當(dāng)前點(diǎn)之間的距離
- 按照距離遞增次序排序
- 選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn)
- 確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率
- 返回前k個(gè)點(diǎn)中頻次最高的類別作為預(yù)測(cè)類別
接著定義函數(shù)：