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

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

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

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

編號 - 慢節(jié)奏(秒) - 快節(jié)奏（秒） - 分類 -

1 - 100 - 80 - 民謠 -

2 - 140 - 40 - 民謠 -

3 - 20 - 160 - 搖滾 -

4 - 110 - 70 - 民謠 -

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

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

編號 - 與x的距離

1 - 10.1

2 - 20.5

3 - 90.3

4 - 15.7

5 - 80.2

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

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

準備數(shù)據(jù)

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

訓練算法

測試算法

使用算法

創(chuàng)建kNN.py

# 科學技術(shù)包
from numpy import *
# 運算符模塊
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 

接下來我們終端進入python交互模式

import kNN
group, labels = kNN.createDataSet( )

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

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

計算已有數(shù)據(jù)集中各個點與當前未知數(shù)據(jù)點的距離

按照距離遞增排序

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

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

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

程序?qū)嵗?:

# inX（需要預測分類的向量） dataSet（數(shù)據(jù)集） labels(標簽集) 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ù)集的維度)詳細點擊
diffMat = tile(inX, (dataSetSize, 1)) - dataSet() （在行方向上重復dataSetSize次， 列方向上重復1此， 然后舉證相減）詳細介紹
假設(shè)inx向量為(x, y), 此時相當于數(shù)學上的矩陣相減:

[ 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 (將矩陣每個值平方) 相當于數(shù)學上的

[(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) （將矩陣按照行的方向相加) 詳細點擊
次操作相當于數(shù)學上的：

[(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 (將矩陣的每個元素開0.5次方也就是 開平方)
相當于數(shù)學的：

[√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)]

細心的朋友就會發(fā)現(xiàn)算到這里其實我們采用了初中所學習過兩點之間球距離的公式

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

下一節(jié)學習 k鄰近算法應用實例(一)