工作原理：(近朱者赤，近墨者黑)
存在一個(gè)樣本數(shù)據(jù)集合，也稱作訓(xùn)練樣本集，并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽途戒，即我們知道樣本集中每一數(shù)據(jù)與所屬分類的對(duì)應(yīng)關(guān)系。輸入沒有標(biāo)簽的新數(shù)據(jù)后僵驰，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對(duì)應(yīng)的特征進(jìn)行比較然后算法提取樣本集中特征最相近數(shù)據(jù)（最近鄰）的分類標(biāo)簽。我們只選擇樣本數(shù)據(jù)集中前k個(gè)最相似的數(shù)據(jù)，這也是為什么叫k-近鄰算法的出處蒜茴。最后星爪，選擇k個(gè)最相似的數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類粉私。簡化說就是在樣本空間當(dāng)中找到與樣本A最接近的k個(gè)樣本顽腾，假設(shè)在這個(gè)k個(gè)樣本絕大多數(shù)屬于C分類，則樣本A也屬于分類C
算法偽代碼描述：
- 計(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)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測分類漓摩。
計(jì)算兩個(gè)向量點(diǎn)之間的距離采用歐氏距離公式：
sqrt((xa - xb)2 + (ya - yb)2)
python代碼實(shí)現(xiàn):
def classify0(inX, dataSet, labels, k):
# shape 返回一個(gè)整型數(shù)字的元組，元組中的每個(gè)元素表示相應(yīng)的數(shù)組每一維的長度
dataSetSize = dataSet.shape[0]
diffMat = tile(inX, (dataSetSize, 1)) - dataSet
sqDiffMat = diffMat ** 2
# axis=1是將一個(gè)矩陣的每一行向量相加
sqDistances = sqDiffMat.sum(axis=1)
distances = sqDistances ** 0.5
# 返回從小到大排序的索引
sortedDistIndicies = distances.argsort()
# 創(chuàng)建一個(gè)字典入客，用于存儲(chǔ)前K個(gè)點(diǎn)所出現(xiàn)的頻率
classCount = {}
for i in range(k):
voteLabel = labels[sortedDistIndicies[i]]
classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
# 排序后返回的是一個(gè)List管毙，而原字典中的鍵值對(duì)被轉(zhuǎn)換為了list中的元組。
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
但由于計(jì)算距離的時(shí)桌硫，數(shù)字差值最大的屬性對(duì)計(jì)算的結(jié)果影響最大夭咬，但每個(gè)特征是同等重要的，在處理這種不同取值范圍的特征值時(shí)铆隘，我們通常采用的方法是將數(shù)值歸一化卓舵，如將取值范圍處理為0到1或者-1到1之間。下面的公式可以將任意取值范圍的特征值轉(zhuǎn)化為0到1區(qū)間內(nèi)的值：
newValue = (oldValue - minValue) / (maxValue - minValue)
python代碼實(shí)現(xiàn)：
# 數(shù)據(jù)歸一化：newValue = (oldValue - minValue) / (maxValue - minValue)
def autoNorm(dataSet):
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals # (maxValue - minValue)
normDataSet = zeros(shape(dataSet))
m = dataSet.shape[0] # return number of line
normDataSet = dataSet - tile(minVals, (m, 1)) # (oldValue - minValue)
normDataSet = normDataSet / tile(ranges, (m, 1)) # (oldValue - minValue) / (maxValue - minValue)
return normDataSet, ranges, minVals
k-近鄰算法是分類數(shù)據(jù)最簡單最有效的算法膀钠，k-近鄰算法是基于實(shí)例的學(xué)習(xí)掏湾，使用算法時(shí)我們必須有接近實(shí)際數(shù)據(jù)的訓(xùn)練樣本數(shù)據(jù)。k-近鄰算法必須保存全部數(shù)據(jù)集托修，如果訓(xùn)練數(shù)據(jù)集很大忘巧，必須使用大量的存儲(chǔ)空間。此外睦刃，由于必須對(duì)數(shù)據(jù)集中每個(gè)數(shù)據(jù)計(jì)算距離值砚嘴，實(shí)際使用時(shí)可能非常耗時(shí)。
