基本概念
KNN是分类算法。
数据类型：数值型和标称型。
工作原理
存在一个训练样本集，并且训练样本集中每个数据都存在标签，即知道训练样本集中每一条数据与所属分类对应关系。输入没有标签的新数据后，与训练样本集中数据对应的特征做比较，然后提取样本集中特征最相似数据（最临近，用距离公式，距离最近）的分类标签。一般来说，我们只取训练样本集中前k个最相似的数据，这就是k的出处。通常k是不大于20的整数。
距离公式
49b476ef-7c62-4da0-8648-5a1c5715d4ab
多特征时，如(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为待分类数据
# dataSet为训练数据集
# labels对应dataSet每一行数据的标签(类型)
# 有多少行数据 shape反回一个元组。(行, 列)
dataSetSize = dataSet.shape[0]
# tile(inX, (dataSetSize,1)) 创建一个numpy的array，dataSetSize行，每行数据是inX
# - dataSet 矩阵减法 m*n矩阵A - m*n矩阵B
diffMat = tile(inX, (dataSetSize,1)) - dataSet
# 矩阵的每个值平方
sqDiffMat = diffMat**2
# 横向求和，得到一个一维数组，每个值都是和
sqDistances = sqDiffMat.sum(axis=1)
# 数组中每个值开根
distances = sqDistances**0.5
# 得到排序后的下标数组
sortedDistIndicies = distances.argsort()
classCount={}
# 只取前k个
for i in range(k):
# 找到下标对应的标签
voteIlabel = labels[sortedDistIndicies[i]]
# 如果找到相同标签利用map来计数
classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
# 排序加反转
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
print sortedClassCount
# 把计数最大的值所对应的标签返回出去
return sortedClassCount[0][0]
数据归一化
如果某个特征值数量级特别大，比如A特征是5位数，而其他特征是个位数。那么就会发现A特征的值大大会影响最终结果。所以需要把每个特征值都归到0-1这个范围。
数据归一化算法
9061c50-3104-11e7-8aca-e882fa09a8a8
def autoNorm(dataSet):
# 每一列最小值
minVals = dataSet.min(0)
# 每一列最大值
maxVals = dataSet.max(0)
# 每一列的差
ranges = maxVals - minVals
# 复制矩阵 dataSet的行，列。值都是0
normDataSet = zeros(shape(dataSet))
# 得到多少行
m = dataSet.shape[0]
# tile(minVals, (m,1)) 创建datSet的行列的矩阵，每一个值都是minVals。
# dataSet - 矩阵相减
normDataSet = dataSet - tile(minVals, (m,1))
# tile(ranges, (m,1)) 创建datSet的行列的矩阵，每一个值都是ranges。
# 并非矩阵除法，而是对应位置的值相除
normDataSet = normDataSet / tile(ranges, (m,1))
return normDataSet, ranges, minVals
实际使用
def datingClassTest():
# 预留出10%来做测试数据验证准确率
hoRatio = 0.10
# 读取数据和标签
datingDataMat,datingLabels = file2matrix('Ch02/datingTestSet.txt') #load data setfrom file
# 把数据归一化处理
normMat, ranges, minVals = autoNorm(datingDataMat)
# 取到数据有多少行
m = normMat.shape[0]
# 取出测试数据的长度
numTestVecs = int(m*hoRatio)
# 错误计数
errorCount = 0.0
for i in range(numTestVecs):
# normMat[i,:] 取出第i行的 所有数据
# normMat[numTestVecs:m,:] 取出numTestVecs之后到m的每行数据
# datingLabels[numTestVecs:m] 取出numTestVecs之后到m的每行的标签
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])
# 如果结果不一致，则错误+1
if (classifierResult != datingLabels[i]): errorCount += 1.0
# 最后打印出错误率和错误数
print "the total error rate is: %f" % (errorCount/float(numTestVecs))
print errorCount
优点
- 分类算法中最简单最有效的算法
缺点
- 必须保存全部训练集，如果训练集样本很大会使用大量存储空间
- 计算距离时可能非常耗时
- 无法给出任何数据的基础结构信息，无法得知平均实例样本和典型实例样本具有什么特征
