基本概念
KNN是分類算法。
數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型靠胜。
工作原理
存在一個(gè)訓(xùn)練樣本集胰苏，并且訓(xùn)練樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽，即知道訓(xùn)練樣本集中每一條數(shù)據(jù)與所屬分類對(duì)應(yīng)關(guān)系岸更。輸入沒(méi)有標(biāo)簽的新數(shù)據(jù)后鸵膏，與訓(xùn)練樣本集中數(shù)據(jù)對(duì)應(yīng)的特征做比較，然后提取樣本集中特征最相似數(shù)據(jù)（最臨近怎炊，用距離公式谭企，距離最近）的分類標(biāo)簽廓译。一般來(lái)說(shuō)，我們只取訓(xùn)練樣本集中前k個(gè)最相似的數(shù)據(jù)债查，這就是k的出處非区。通常k是不大于20的整數(shù)。
距離公式
49b476ef-7c62-4da0-8648-5a1c5715d4ab
多特征時(shí)盹廷，如(1,0,0,1)和(7, 6, 9, 4)
d3b42a96-1c5a-4eac-83cb-d4041a242464
分類算法
from numpy import *
import operator
from os import listdir
def classify0(inX, dataSet, labels, k):
# inX為待分類數(shù)據(jù)
# dataSet為訓(xùn)練數(shù)據(jù)集
# labels對(duì)應(yīng)dataSet每一行數(shù)據(jù)的標(biāo)簽(類型)
# 有多少行數(shù)據(jù) shape反回一個(gè)元組征绸。(行, 列)
dataSetSize = dataSet.shape[0]
# tile(inX, (dataSetSize,1)) 創(chuàng)建一個(gè)numpy的array，dataSetSize行俄占，每行數(shù)據(jù)是inX
# - dataSet 矩陣減法 m*n矩陣A - m*n矩陣B
diffMat = tile(inX, (dataSetSize,1)) - dataSet
# 矩陣的每個(gè)值平方
sqDiffMat = diffMat**2
# 橫向求和管怠，得到一個(gè)一維數(shù)組，每個(gè)值都是和
sqDistances = sqDiffMat.sum(axis=1)
# 數(shù)組中每個(gè)值開(kāi)根
distances = sqDistances**0.5
# 得到排序后的下標(biāo)數(shù)組
sortedDistIndicies = distances.argsort()
classCount={}
# 只取前k個(gè)
for i in range(k):
# 找到下標(biāo)對(duì)應(yīng)的標(biāo)簽
voteIlabel = labels[sortedDistIndicies[i]]
# 如果找到相同標(biāo)簽利用map來(lái)計(jì)數(shù)
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
# 排序加反轉(zhuǎn)
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
print sortedClassCount
# 把計(jì)數(shù)最大的值所對(duì)應(yīng)的標(biāo)簽返回出去
return sortedClassCount[0][0]
數(shù)據(jù)歸一化
如果某個(gè)特征值數(shù)量級(jí)特別大缸榄，比如A特征是5位數(shù)渤弛，而其他特征是個(gè)位數(shù)。那么就會(huì)發(fā)現(xiàn)A特征的值大大會(huì)影響最終結(jié)果甚带。所以需要把每個(gè)特征值都?xì)w到0-1這個(gè)范圍她肯。
數(shù)據(jù)歸一化算法
9061c50-3104-11e7-8aca-e882fa09a8a8
def autoNorm(dataSet):
# 每一列最小值
minVals = dataSet.min(0)
# 每一列最大值
maxVals = dataSet.max(0)
# 每一列的差
ranges = maxVals - minVals
# 復(fù)制矩陣 dataSet的行，列鹰贵。值都是0
normDataSet = zeros(shape(dataSet))
# 得到多少行
m = dataSet.shape[0]
# tile(minVals, (m,1)) 創(chuàng)建datSet的行列的矩陣晴氨，每一個(gè)值都是minVals。
# dataSet - 矩陣相減
normDataSet = dataSet - tile(minVals, (m,1))
# tile(ranges, (m,1)) 創(chuàng)建datSet的行列的矩陣砾莱，每一個(gè)值都是ranges瑞筐。
# 并非矩陣除法凄鼻，而是對(duì)應(yīng)位置的值相除
normDataSet = normDataSet / tile(ranges, (m,1))
return normDataSet, ranges, minVals
實(shí)際使用
def datingClassTest():
# 預(yù)留出10%來(lái)做測(cè)試數(shù)據(jù)驗(yàn)證準(zhǔn)確率
hoRatio = 0.10
# 讀取數(shù)據(jù)和標(biāo)簽
datingDataMat,datingLabels = file2matrix('Ch02/datingTestSet.txt') #load data setfrom file
# 把數(shù)據(jù)歸一化處理
normMat, ranges, minVals = autoNorm(datingDataMat)
# 取到數(shù)據(jù)有多少行
m = normMat.shape[0]
# 取出測(cè)試數(shù)據(jù)的長(zhǎng)度
numTestVecs = int(m*hoRatio)
# 錯(cuò)誤計(jì)數(shù)
errorCount = 0.0
for i in range(numTestVecs):
# normMat[i,:] 取出第i行的 所有數(shù)據(jù)
# normMat[numTestVecs:m,:] 取出numTestVecs之后到m的每行數(shù)據(jù)
# datingLabels[numTestVecs:m] 取出numTestVecs之后到m的每行的標(biāo)簽
classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
print "the classifier came back with: %d, the real answer is: %d" % (classifierResult, datingLabels[i])
# 如果結(jié)果不一致腊瑟，則錯(cuò)誤+1
if (classifierResult != datingLabels[i]): errorCount += 1.0
# 最后打印出錯(cuò)誤率和錯(cuò)誤數(shù)
print "the total error rate is: %f" % (errorCount/float(numTestVecs))
print errorCount
優(yōu)點(diǎn)
- 分類算法中最簡(jiǎn)單最有效的算法
缺點(diǎn)
- 必須保存全部訓(xùn)練集，如果訓(xùn)練集樣本很大會(huì)使用大量存儲(chǔ)空間
- 計(jì)算距離時(shí)可能非常耗時(shí)
- 無(wú)法給出任何數(shù)據(jù)的基礎(chǔ)結(jié)構(gòu)信息块蚌，無(wú)法得知平均實(shí)例樣本和典型實(shí)例樣本具有什么特征
