KNN算法介绍
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。
K最近邻算法(KNN)
如果K = 3，绿色圆点的最近的3个邻居是2个红色小三角形和1个蓝色小正方形，少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于红色的三角形一类。
转载请注明出处：Michael孟良
如果K = 5，绿色圆点的最近的5个邻居是2个红色三角形和3个蓝色的正方形，还是少数从属于多数，基于统计的方法，判定绿色的这个待分类点属于蓝色的正方形一类。
对于未知类别属性数据集中的点
计算已知类别数据集中的点与当前点的距离
按照距离一次排序
选取与当前点距离最小的K个点
确定前K个点所在类别的出现概率
返回前K个点出现频率最高的类别作为当前点预测分类
复杂度：
KNN 分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)
K 值的选择，距离度量和分类决策规则是该算法的三个基本要素
问题：该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的 K 个邻居中大容量类的样本占多数
数据
有一堆射箭运动员的数据，第一列是一年射箭的箭数，第二列是之前运动员升磅的磅数， 第三列是每个月射箭时间与工作时间的比值，第四列就是一个结果，1代表输，2代表平，3代表赢。
40920 8.326976 0.953952 3
14488 7.153469 0.673904 2
26052 1.441871 0.805124 1
75136 13.147394 0.428964 1
38344 1.669788 0.134296 1
......
代码（Python）
# coding:utf-8
import numpy as np
import operator
# matplotlib 绘图模块
import matplotlib.pyplot as plt
# from array import array
# from matplotlib.font_manager import FontProperties
# normData 测试数据集的某行， dataSet 训练数据集 ，labels 训练数据集的类别，k k的值
def classify(normData, dataSet, labels, k):
# 计算行数
dataSetSize = dataSet.shape[0]
# print ('dataSetSize 长度 =%d'%dataSetSi ； vzvz ze)
# 当前点到所有点的坐标差值 ,np.tile(x,(y,1)) 复制x 共y行 1列
diffMat = np.tile(normData, (dataSetSize, 1)) - dataSet
# 对每个坐标差值平方
sqDiffMat = diffMat ** 2
# 对于二维数组 sqDiffMat.sum(axis=0)指 对向量每列求和，sqDiffMat.sum(axis=1)是对向量每行求和,返回一个长度为行数的数组
# 例如：narr = array([[ 1., 4., 6.],
# [ 2., 5., 3.]])
# narr.sum(axis=1) = array([ 11., 10.])
# narr.sum(axis=0) = array([ 3., 9., 9.])
sqDistances = sqDiffMat.sum(axis=1)
# 欧式距离 最后开方
distance = sqDistances ** 0.5
# x.argsort() 将x中的元素从小到大排序，提取其对应的index 索引，返回数组
# 例： tsum = array([ 11., 10.]) ---- tsum.argsort() = array([1, 0])
sortedDistIndicies = distance.argsort()
# classCount保存的K是魅力类型 V:在K个近邻中某一个类型的次数
classCount = {}
for i in range(k):
# 获取对应的下标的类别
voteLabel = labels[sortedDistIndicies[i]]
# 给相同的类别次数计数
classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
# sorted 排序 返回新的list
# sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
sortedClassCount = sorted(classCount.items(), key=lambda x: x[1], reverse=True)
return sortedClassCount[0][0]
def file2matrix(filename):
fr = open(filename, "rb")
# readlines:是一次性将这个文本的内容全部加载到内存中(列表)
arrayOflines = fr.readlines()
numOfLines = len(arrayOflines)
# print "numOfLines = " , numOfLines
# numpy.zeros 创建给定类型的数组 numOfLines 行 ，3列
returnMat = np.zeros((numOfLines, 3))
# 存结果的列表
classLabelVector = []
index = 0
for line in arrayOflines:
# 去掉一行的头尾空格
line = line.decode("utf-8").strip()
listFromline = line.split('\t')
returnMat[index, :] = listFromline[0:3]
classLabelVector.append(int(listFromline[-1]))
index += 1
return returnMat, classLabelVector
# 将数据归一化
def autoNorm(dataSet):
# dataSet.min(0) 代表的是统计这个矩阵中每一列的最小值 返回值是一个矩阵1*3矩阵
# 例如： numpyarray = array([[1,4,6],
# [2,5,3]])
# numpyarray.min(0) = array([1,4,3]) numpyarray.min(1) = array([1,2])
# numpyarray.max(0) = array([2,5,6]) numpyarray.max(1) = array([6,5])
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
# dataSet.shape[0] 计算行数， shape[1] 计算列数
m = dataSet.shape[0]
# print '行数 = %d' %(m)
# print maxVals
# normDataSet存储归一化后的数据
# normDataSet = np.zeros(np.shape(dataSet))
# np.tile(minVals,(m,1)) 在行的方向上重复 minVals m次 即复制m行，在列的方向上重复munVals 1次，即复制1列
normDataSet = dataSet - np.tile(minVals, (m, 1))
normDataSet = normDataSet / np.tile(ranges, (m, 1))
return normDataSet, ranges, minVals
def archeyClassM():
rate = 0.1
archeyDataMat, archeyLabels = file2matrix('./archeyTestSet.txt')
# 将数据归一化
normMat, ranges, minVals = autoNorm(archeyDataMat)
# m 是 ： normMat行数 = 1000
m = normMat.shape[0]
# print 'm =%d 行'%m
# 取出100行数据测试
numTestVecs = int(m * rate)
errorCount = 0.0
for i in range(numTestVecs):
# normMat[i,:] 取出数据的第i行,normMat[numTestVecs:m,:]取出数据中的100行到1000行 作为训练集，
# archeyLabels[numTestVecs:m] 取出数据中100行到1000行的类别，4是K
classifierResult = classify(normMat[i, :], normMat[numTestVecs:m, :], archeyLabels[numTestVecs:m], 4)
print('模型预测值: %d ,真实值 : %d' % (classifierResult, archeyLabels[i]))
if (classifierResult != archeyLabels[i]):
errorCount += 1.0
errorRate = errorCount / float(numTestVecs)
print('正确率 : %f' % (1 - errorRate))
return 1 - errorRate
def classifyperson():
resultList = ['输', '平', '赢']
#你自己的数据
# input_man = [20000, 10, 2.8]
input_man = [17934,0.000000,0.147573]
archeyDataMat, archeyLabels = file2matrix('archeyTestSet.txt')
normMat, ranges, minVals = autoNorm(archeyDataMat)
result = classify((input_man - minVals) / ranges, normMat, archeyLabels, 5)
print('你这场比赛的预测结果是:%s' % resultList[result - 1])
if __name__ == '__main__':
# createScatterDiagram观察数据的分布情况
# createScatterDiagram()
acc = archeyClassM()
if (acc > 0.9):
classifyperson()
代码分析
首先拿到archeyTestSet.txt这份数据，然后通过autoNorm方法对所有的数据进行个归一化，就说如果某列值太大， 会影响点的空间分布，这时需要写个autoNorm方法将所有数据通过那一列的百分比生成一个0到1的数， 让点的分布更均匀。
def autoNorm(dataSet):
然后写个classify的方法
def classify(normData, dataSet, labels, k):
normData 测试数据集的某行， dataSet 训练数据集 ，labels 训练数据集的类别，k 的值。通过这个方法， 将normData 到dataSet 的所有距离测出来， 选择最近的K个，这K个label最多是哪个，就将normData 定义为哪一类。
input_man = [17934,0.000000,0.147573]
将自己的三维数据放到这个空间中，看它输入哪一类。
结果
模型预测值: 2 ,真实值 : 2
模型预测值: 2 ,真实值 : 1
模型预测值: 1 ,真实值 : 1
正确率 : 0.960000
你这场比赛的预测结果是:平
测试样本和代码链接
https://github.com/MichaelYipInGitHub/PythonTest/blob/master/com/test/knn/archeyTestSet.txt
https://github.com/MichaelYipInGitHub/PythonTest/blob/master/com/test/knn/KNNArcheyTest.py
结语
上述案例仅供娱乐，因为即便这个训练模型相当精确， 你知道自己的胜负后依然要硬着头皮去比赛。 淘汰赛是和自己比，比如你的水平是27， 而你打到28，你已经是问心无愧，即便那场比赛输了你也是赢了！
网友评论