摘要：鄰近算法算法背景假設(shè)我們要給一堆音樂(lè)分類(lèi)，我們可以分成搖滾，民謠，戲曲等等，搖滾的音樂(lè)激昂，節(jié)奏快。這種基于某一特征出現(xiàn)的次數(shù)來(lái)區(qū)分事物的算法，我們使用鄰近算法。

假設(shè)我們要給一堆mp3音樂(lè)分類(lèi)，我們可以分成搖滾，民謠，戲曲等等，搖滾的音樂(lè)激昂，節(jié)奏快。民謠舒緩節(jié)奏慢，但是搖滾中也有可能存在舒緩節(jié)奏慢點(diǎn)旋律， 同理民謠中也會(huì)有激昂，快的旋律。那么如何區(qū)分他們呢， 我們可以根據(jù)出現(xiàn)的頻率來(lái)， 比如舒緩慢節(jié)奏的旋律多的是民謠， 激昂快多的旋律是搖滾。so這種基于某一特征出現(xiàn)的次數(shù)來(lái)區(qū)分事物的算法，我們使用k-鄰近算法。

k-鄰近算法就是采用測(cè)量不同特征值之間的距離方法進(jìn)行分類(lèi)
優(yōu)點(diǎn): 精度高， 對(duì)異常值不敏感， 無(wú)數(shù)據(jù)輸入假定
缺點(diǎn): 計(jì)算復(fù)雜度高，空間復(fù)雜度高
適用范圍: 數(shù)值型和表稱(chēng)行

假設(shè)我們我們每個(gè)mp3時(shí)常 180秒
根據(jù)快慢節(jié)奏來(lái)做特征和一組已有數(shù)據(jù)集統(tǒng)計(jì)：

編號(hào) - 慢節(jié)奏(秒) - 快節(jié)奏（秒） - 分類(lèi) -

1 - 100 - 80 - 民謠 -

2 - 140 - 40 - 民謠 -

3 - 20 - 160 - 搖滾 -

4 - 110 - 70 - 民謠 -

5 - 30 - 150 - 搖滾 -
。。。。。。。。。

現(xiàn)在我們有一個(gè)未知分類(lèi)的mp3序號(hào)為x
其慢節(jié)奏時(shí)長(zhǎng)為 103 快節(jié)奏時(shí)長(zhǎng)為77
我們可以根據(jù)某種方法算出x與樣本數(shù)據(jù)其他mp3的距離得到如下：

編號(hào) - 與x的距離

1 - 10.1

2 - 20.5

3 - 90.3

4 - 15.7

5 - 80.2

按照距離遞增我們排序然后找到k個(gè)距離最近的樣本， 假定k = 3，
這三個(gè)樣本依次序號(hào)為： 1， 4， 2
然后我們分析這三個(gè)全部是民謠， 于此我們斷定x的分類(lèi)為民謠

搜集數(shù)據(jù)

準(zhǔn)備數(shù)據(jù)

分析數(shù)據(jù)

訓(xùn)練算法

測(cè)試算法

使用算法

創(chuàng)建kNN.py

# 科學(xué)技術(shù)包
from numpy import *
# 運(yùn)算符模塊
import Operator

# 創(chuàng)建數(shù)據(jù)集
def createDataSet():
    group = array([1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1])
    labels = ["A", "A", "B", "B"]
    return group, labels 

接下來(lái)我們終端進(jìn)入python交互模式

import kNN
group, labels = kNN.createDataSet( )

group是擁有四組數(shù)據(jù)的數(shù)組， 每組數(shù)據(jù)擁有兩個(gè)特征， labels是數(shù)據(jù)的標(biāo)簽。我們將以有數(shù)據(jù)畫(huà)在平面直角坐標(biāo)系中如圖：

當(dāng)拿到一組位置屬性的數(shù)據(jù)時(shí)，我們需要一次做如下操作：

計(jì)算已有數(shù)據(jù)集中各個(gè)點(diǎn)與當(dāng)前未知數(shù)據(jù)點(diǎn)的距離

按照距離遞增排序

選取與未知點(diǎn)距離最近的k組數(shù)據(jù)

確定這k組數(shù)據(jù)的各標(biāo)簽出現(xiàn)的頻率

返回這k組數(shù)據(jù)出現(xiàn)頻率最高的標(biāo)簽作為未知點(diǎn)的標(biāo)簽

程序?qū)嵗?:

# inX（需要預(yù)測(cè)分類(lèi)的向量） dataSet（數(shù)據(jù)集） labels(標(biāo)簽集) k(鄰近算法系數(shù))
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistance = sqDiffMat.sum(axis=1)
    distance = sqDistance**0.5
    sortedDistIndicies = distance.argsort()
    classCount={}
    for i in range(k):
        voteIlable = labels[sortedDistIndicies[i]]
        classCount[voteIlable] = classCount.get(voteIlable, 0) + 1
    sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]    

我們逐句分析下：
dataSetSize = dataSet.shape[0] (獲取數(shù)據(jù)集的維度)詳細(xì)點(diǎn)擊
diffMat = tile(inX, (dataSetSize, 1)) - dataSet() （在行方向上重復(fù)dataSetSize次， 列方向上重復(fù)1此， 然后舉證相減）詳細(xì)介紹
假設(shè)inx向量為(x, y), 此時(shí)相當(dāng)于數(shù)學(xué)上的矩陣相減:

[ x, y]      [1.0, 1.1]     [x-1, y-1.1]
[ x, y]      [1.0, 1.0]     [x-1, y-1]
[ x, y]  -   [0, 0]      =  [x-0, y-0]
[ x, y]      [0, 0.1]       [x-0, y-0.1]      

sqDiffMat = diffMat**2 (將矩陣每個(gè)值平方) 相當(dāng)于數(shù)學(xué)上的

[(x-10)2, (y-1.1)2]
[(x-1)2, (y-1)2]
[(x-0)2, (y-0)2]
[(x-0)2, (y-0.1)2] 

sqDistance = sqDiffMat.sum(axis=1) （將矩陣按照行的方向相加) 詳細(xì)點(diǎn)擊
次操作相當(dāng)于數(shù)學(xué)上的：

[(x-10)2 + (y-1.1)2]
[(x-1)2 + (y-1)2]
[(x-0)2 + (y-0)2]
[(x-0)2 + (y-0.1)2]

distance = sqDistance**0.5 (將矩陣的每個(gè)元素開(kāi)0.5次方也就是 開(kāi)平方)
相當(dāng)于數(shù)學(xué)的：

[√2((x-10)2 + (y-1.1)2)]
[√2((x-1)2 + (y-1)2)]
[√2((x-0)2 + (y-0)2)]
[√2((x-0)2 + (y-0.1)2)]

細(xì)心的朋友就會(huì)發(fā)現(xiàn)算到這里其實(shí)我們采用了初中所學(xué)習(xí)過(guò)兩點(diǎn)之間球距離的公式

sortedDistIndicies = distance.argsort() （將所得的距離進(jìn)行排序）
classCount={} (新建一個(gè)字典)
for i in range(k): (以k鄰近算法系數(shù)k循環(huán))
voteIlable = labels[sortedDistIndicies[i]] (依次取出距離最近的k組數(shù)據(jù)對(duì)應(yīng)的標(biāo)簽)
classCount[voteIlable] = classCount.get(voteIlable, 0) + 1 （以標(biāo)簽為健，以出現(xiàn)的次數(shù)為值）
sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1), reverse=True) (將字典按照值的大小排序) 詳細(xì)點(diǎn)擊
return sortedClassCount[0][0] (最后返回出現(xiàn)次數(shù)最多的標(biāo)簽)
接下來(lái)我們實(shí)驗(yàn)一下，
我們進(jìn)入終端

下一節(jié)學(xué)習(xí) k鄰近算法應(yīng)用實(shí)例(一)