K-近鄰算法（KNN）是分類數(shù)據(jù)最簡(jiǎn)單最有效的算法。

核心思想

采用不同特征值之間的距離方法進(jìn)行分類
首先：

我們有一個(gè)樣本集（也稱訓(xùn)練樣本集）惹想，樣本中的每個(gè)數(shù)據(jù)都存在標(biāo)簽片任，即樣本集中每一個(gè)數(shù)據(jù)對(duì)應(yīng)與所屬分類的對(duì)應(yīng)關(guān)系稿茉。

之后：

輸入沒有標(biāo)簽的新數(shù)據(jù)時(shí)，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)的特征進(jìn)行比較拳亿，（一般是計(jì)算歐氏距離）然后算法提取樣本集中特征最相近數(shù)據(jù)（最近鄰）的分類標(biāo)簽

附：一本只選擇樣本數(shù)據(jù)集中前K個(gè)最相近的數(shù)據(jù)，這就是k近鄰中的k愿伴。k一般不超過20的整數(shù)

KNN算法的過程為:

• 選擇一種距離計(jì)算方式, 通過數(shù)據(jù)所有的特征計(jì)算新數(shù)據(jù)與已知類別數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)的距離
• 按照距離遞增次序進(jìn)行排序肺魁，選取與當(dāng)前距離最小的k個(gè)點(diǎn)
• 對(duì)于離散分類，返回k個(gè)點(diǎn)出現(xiàn)頻率最多的類別作預(yù)測(cè)分類公般；對(duì)于回歸則返回k個(gè)點(diǎn)的加權(quán)值作為預(yù)測(cè)值

kNN的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：簡(jiǎn)單有效
缺點(diǎn)：
一是必須有接近實(shí)際數(shù)據(jù)的訓(xùn)練樣本數(shù)據(jù)万搔，且要保存全部數(shù)據(jù)集，占用存儲(chǔ)空間且計(jì)算耗時(shí)官帘；
二是無法給出任何數(shù)據(jù)的急促結(jié)構(gòu)信息瞬雹，無法知曉平均實(shí)例樣本和典型實(shí)例樣本具有什么特征。使用概率測(cè)量方法可以解決這個(gè)問題

算法實(shí)例

創(chuàng)建kNN.py
(1)創(chuàng)建數(shù)據(jù)集

#創(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

有四個(gè)數(shù)據(jù)刽虹，其標(biāo)簽分別為（A,A,B,B）
(2) 構(gòu)照kNN分類器

#第一個(gè)kNN分類器  
#inX-測(cè)試數(shù)據(jù) dataSet-樣本數(shù)據(jù)  labels-標(biāo)簽 k-鄰近的k個(gè)樣本
def classify0(inX,dataSet,labels,k):  
    dataSetSize = dataSet.shape[0]  #dataSet.shape[0]是第一維的數(shù)目    
    '''
    計(jì)算與所有點(diǎn)的距離酗捌，并進(jìn)行排序
    '''
    diffMat = tile(inX,(dataSetSize,1)) - dataSet #要分類的新數(shù)據(jù)與原始數(shù)據(jù)做差 
    sqDiffMat = diffMat**2  #求差的平方  
    sqDistance = sqDiffMat.sum(axis=1)  #求差的平方的和    
    distances = sqDistance**0.5 #求標(biāo)準(zhǔn)差   
    sortDistIndicies = distances.argsort() #距離排序    
    classCount = {}  #定義元字典   
    '''
    遍歷前k個(gè)元素,選擇距離最小的k個(gè)點(diǎn)
    '''
    for i in range(k):  
        voteIlabel = labels[sortDistIndicies[i]]  #獲得前k個(gè)元素的標(biāo)簽 
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1#計(jì)算前k個(gè)數(shù)據(jù)標(biāo)簽出現(xiàn)的次數(shù)   
    '''
    排序
    '''
    sortedClassCount =sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse = True) #對(duì)得到的標(biāo)簽字典按降序排列   
    return sortedClassCount[0][0] #返回出現(xiàn)次數(shù)最多的標(biāo)簽  

結(jié)果測(cè)試

group, labels = kNN.createDataSet( )
kNN.classfy0([0,0],group,labels,3)

結(jié)果為B

(3)讀取文本文件中的數(shù)據(jù)

def file2matrix(filename):

    fr = open(filename)# 打開文件
    numberOfLines = len(fr.readlines()) # 計(jì)算文本文件的行數(shù)
    returnMat = zeros((numberOfLines,3))# 創(chuàng)建返回的數(shù)據(jù)矩陣
    classLabelVector = []# 創(chuàng)建類標(biāo)簽
    fr = open(filename) # 打開文件
    index = 0 # 定義索引
    # 讀取文件的每一行并處理
    for line in fr.readlines():
        line = line.strip()# 去除行的尾部的換行符
        listFromLine = line.split('\t') # 將一行數(shù)據(jù)按空進(jìn)行分割
        returnMat[index,:] = listFromLine[0:3] # 0：3列為數(shù)據(jù)集的數(shù)據(jù)
        classLabelVector.append((listFromLine[-1])) # 最后一列為數(shù)據(jù)的分類標(biāo)簽
        index += 1# 索引加1
   
    return returnMat,classLabelVector # 返回?cái)?shù)據(jù)集和對(duì)應(yīng)的類標(biāo)簽

(4)顯示散點(diǎn)圖

import matplotlib.pyplot as plt
fig = plt.figure()
ax1 = fig.add_subplot(111)
datingDataMat,datingLabels = kNN.file2matrix('datingTestSet.txt')
#ax.scatter(datingDataMat[:,1], datingDataMat[:,2])

ax1.scatter(datingDataMat[:, 1], datingDataMat[:, 2], 15.0*array(datingLabels), 15.0*array(datingLabels))

ax.axis([-2, 25, -0.2, 2.0])
plt.xlabel(u"玩游戲視頻所耗時(shí)間百分比")
plt.ylabel(u"每周消費(fèi)的冰淇淋公升數(shù)")
plt.show()

(5)歸一化數(shù)值
為了防止特征值數(shù)量的差異對(duì)預(yù)測(cè)結(jié)果的影響(比如計(jì)算距離，量值較大的特征值影響肯定很大)涌哲，我們將所有的特征值都?xì)w一化到[0,1]

def autoNorm(dataSet):
    minVals = dataSet.min(0) # 求數(shù)據(jù)矩陣每一列的最小值
    maxVals = dataSet.max(0)# 求數(shù)據(jù)矩陣每一列的最大值
    ranges = maxVals - minVals# 求數(shù)據(jù)矩陣每一列的最大最小值差值
    #normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0] # 返回?cái)?shù)據(jù)矩陣第一維的數(shù)目
    normDataSet = dataSet - tile(minVals, (m, 1)) # 求矩陣每一列減去該列最小值胖缤，得出差值
    normDataSet = normDataSet / tile(ranges, (m, 1)) # 用求的差值除以最大最小值差值，即數(shù)據(jù)的變化范圍阀圾，即歸一化
    return normDataSet, ranges, minVals # 返回歸一化后的數(shù)據(jù)哪廓，最大最小值差值，最小值

附：numpy函數(shù)小結(jié)

#coding=utf-8
__author__ = 'Administrator'
from numpy import *

a = array([[0, 1, 0], [1, 1, 2]])
print a

aSize = a.shape[0] #可以認(rèn)為是輸出列數(shù)
print aSize

b = arange(7, dtype=uint16) #dtype為數(shù)據(jù)類型對(duì)象
print b

'''
tile
將數(shù)組a重復(fù)n次
'''
c = array([0, 1])
d = tile(c, (3, 1))
print d

c = zeros((3, 1), dtype=int)
print c

輸出結(jié)果

[[0 1 0]
[1 1 2]]
2
[0 1 2 3 4 5 6]
[[0 1]
[0 1]
[0 1]]
[[0]
[0]
[0]]

參考文獻(xiàn)：

http://www.aichengxu.com/yejie/512129.htm
http://blog.csdn.net/quincuntial/article/details/50471423
http://blog.csdn.net/suipingsp/article/details/41964713