一、KNN算法思想：
在训练样本集中，每个数据与其对应的所属分类的对应关系是已知的。即每个数据都有一个已知的且确定的标签。
通过对比测试数据每个特征和训练样本集中的每个特征的相似度（距离），提取样本集中最相似数据（最近邻）的分类标签。
一般，我们只取样本数据集中前k个最相似的数据，通常k不大于20
最后，选取k个最相似数据中出现次数最多的分类，作为新数据的分类
二、主要算法实现思路
def classify0(inX,dataSet,labels,k):
dataSetSize=dataSet.shape[0] # 求dataset的长度，训练样本数
diffMat=np.tile(inX,(dataSetSize,1))-dataSet # tile(A,B) 重复A 重复B次
sqDiffMat=diffMat**2
sqDistance=sqDiffMat.sum(axis=1) # 将矩阵的每一行向量相加
distance=sqDistance**0.5
print (distance)
sortedDistIndicies=distance.argsort() # 将distance从小到大排列,返回索引
print (sortedDistIndicies)
classCount={}
for i in range(k):
voteIlabel=labels[sortedDistIndicies[i]]
classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
sortedClassCount=sorted(classCount.items(),key=op.itemgetter(1),reverse=True)
print (sortedClassCount)
return sortedClassCount[0][0]
2.1、测试算法
classify0([0,0],group,labels,3)
三、实例一：网站配对
3.1准备数据：数据解析
def file2matrix(filename):
fr=open(filename) # 打开文件
arrayOLines=fr.readlines() # 读取文件
numberOfLines=len(arrayOLines) # 获取文件行数
returnMat=np.zeros((numberOfLines,3)) # 创建一个行数等于文件行数，列数为3的矩阵
classLabelVector=[]
index=0
for line in arrayOLines: # 对文件中每一行，执行如下操作
line=line.strip() # 移出字符串收尾字符
listFromLine=line.split('\\t') # 按照换行符进行分割
returnMat[index,:]=listFromLine[0:3] # 将每一行的第0到第3（不包含）个值 赋值给 returnMat矩阵的第index行，每个列的值
try:
classLabelVector.append(int(listFromLine[-1])) # 标签为listFromLine的最后一个值
except ValueError:
pass
index+=1 # 行数+1
return returnMat,classLabelVector # 返回标准训练集矩阵，以及 对应的标签数据集
3.2使用matplotlib创建散点图
import matplotlib
import matplotlib.pyplot as plt
fig=plt.figure() # 创建视图
ax=fig.add_subplot(211) # 创建子视图，每个subplot创建一个子图(2*1大小的视图，在第一个位置/ 2行1列，第一个位置)
ax.scatter(datingDataMat[:,1],datingDataMat[:,2]) # 使用训练集的第二列、第三列数据作为横纵坐标
ax2=fig.add_subplot(212) # 创建视图（2*1大小的视图，在第二个位置/2行1列，第二个位置）
ax2.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*np.array(datingLabels),15.0*np.array(datingLabels)) # 绘制散点图时增加颜色和尺寸
plt.show()
3.3归一化数值
def autoNorm(dataSet):
minVals=dataSet.min(0) # 每列的最小值
maxVals=dataSet.max(0) # 每列的最大值
ranges=maxVals-minVals
normalDataSet=np.zeros(np.shape(dataSet))
m=dataSet.shape[0]
normalDataSet=dataSet-np.tile(minVals,(m,1))
normalDataSet=normalDataSet/np.tile(ranges,(m,1))
return normalDataSet,ranges,minVals
3.4测试算法
def datingClassTest():
hoRatio=0.10
datingDataMat,datingLabels=file2matrix('datingTestSet.txt')
normMat,ranges,minVals=autoNorm(datingDataMat)
m=normMat.shape[0]
print(m)
numTestVecs=int(m*hoRatio)
print(numTestVecs)
errorCount=0.0
for i in range(numTestVecs):
classifiterResult = KNN.classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
print ("the classifier came back with : %s, the real answer is: %s" % (classifierResult,datingLabels[i]))
if(calssifierResult !=datingLabels[i]):
errorCount+=1
print ("the total error rate is: %f" %(errorCount/float(numTestVecs)))
3.5构建完整可用算法
def classifyPerson():
resultList = ['not at all', 'in small doses', 'in large doses']
percentTats = float(input("percentage of time spent playing videa games?"))
ffMiles = float(input("frequent flier miles earned per year?"))
iceCream = float(input("liters of ice cream consumed per year?"))
datingDataMat, datingLabels = file2matrix("datingTestSet2.txt")
normMat, ranges, minVals = autoNorm(datingDataMat)
inArr = np.array([ffMiles, percentTats, iceCream])
classifierResult = classify0((inArr - minVals) / ranges, normMat, datingLabels, 3)
print("you will probably like this person: ", resultList[int(classifierResult) - 1])
四、使用算法
classifyPerson()
完整代码请查看：https://github.com/AdaSundaner/Tyro/tree/master/MachineLearingInAction/KNN
