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

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

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

假設我們我們每個mp3時常 180秒
根據快慢節奏來做特征和一組已有數據集統計：

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

1 - 100 - 80 - 民謠 -

2 - 140 - 40 - 民謠 -

3 - 20 - 160 - 搖滾 -

4 - 110 - 70 - 民謠 -

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

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

編號 - 與x的距離

1 - 10.1

2 - 20.5

3 - 90.3

4 - 15.7

5 - 80.2

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

搜集數據

準備數據

分析數據

訓練算法

測試算法

使用算法

創建kNN.py

# 科學技術包
from numpy import *
# 運算符模塊
import Operator

# 創建數據集
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是擁有四組數據的數組， 每組數據擁有兩個特征， labels是數據的標簽。我們將以有數據畫在平面直角坐標系中如圖：

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

計算已有數據集中各個點與當前未知數據點的距離

按照距離遞增排序

選取與未知點距離最近的k組數據

確定這k組數據的各標簽出現的頻率

返回這k組數據出現頻率最高的標簽作為未知點的標簽

程序實例1:

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

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

[(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-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次方也就是 開平方)
相當于數學的：

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

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

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

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