KNN—K近邻算法
工作原理
Training set中每个样本都存在标签（分类信息），输入的新数据没有标签。计算新数据与Training set中各个样本数据的距离，距离越近相似度越高。选择Training set中前k个最相似的数据（k通常不大于20），新数据的分类为k个最相似数据中出现次数最多的分类；若标签为数值型，则为k个最相似数据的平均值。
计算原理
欧式数据公式：
测试分类器
使用已知答案的数据，向分类器输入隐藏答案后的数据，计算错误率。
示例一：创建KNN分类器
1. 导入数据
def CreateDataset():
group = np.array([[1,1.1],[1,1],[0,0],[0,0.1]])
labels = ['A','A','B','B']
return group,labels
group,labels = CreateDataset()
2. 实现KNN算法
import numpy as np
import collections
def KNN(inX,dataSet,label,k):
rowNum = dataSet.shape[0]
diffMat = np.tile(inX,(rowNum,1)) - dataSet
sqMat = diffMat ** 2
distMat = sqMat.sum(axis = 1)
distance = distMat ** 0.5
sortMat = distance.argsort()
classCount = {}
for i in range(k):
l = labels[sortMat[i]]
classCount[l] = classCount.get(l,0) + 1
sort_result = sorted(classCount.items(),key = lambda x:x[1],reverse = True)
return classCount
示例二：改进约会网站配对效果
样本特征
每年获得飞行常客里程数：数值分布为1000-90000
玩视频游戏所耗时间比：数值分布为0-14
每周消费的冰激凌公升数：数值分布为0-1
样本标签
不喜欢：1
魅力一般：2
极具魅力：3
(1)将文本记录转换为numpy矩阵
import numpy as np
import os
os.chdir('C://Users/lenovo/Desktop/MLiA_SourceCode/machinelearninginaction/')
def file2matrix(filename):
file = open(filename)
arrayLine = file.readlines()
NumOfLine = len(arrayLine)
returnMat = np.zeros((NumOfLine,3))
labelVector = []
index = 0
for line in arrayLine:
line = line.strip().split("\t")
returnMat[index,:] = line[:3]
labelVector.append(int(line[-1]))
index += 1
return returnMat,labelVector
datingDataMat,datingLabels = file2matrix("./Ch02/datingTestSet2.txt")
(2) 分析数据：使用Matplotlib 创建散点图
import matplotlib
import matplotlib.pyplot as plt
plt.scatter(datingDataMat[:,1],datingDataMat[:,2],s = 150*datingLabels,c = 15*np.array(datingLabels))
plt.show()
(3) 准备数据：归一化数值
三个特征的数值范围有很大区别，导致三个特征不是等权重的。需要对数值进行归一化，将原始数据转换为0到1区间的内的值。
def autoNorm(dataSet):
maxFea = dataSet.max(axis = 0 )
minFea = dataSet.min(axis = 0 )
rangeFea = maxFea - minFea
returnMat = (dataSet - np.tileminFea) / rangeFea
return returnMat
autoNorm(datingDataMat)
(4) 测试算法
def datingclassTest():
testRatio = 0.1
rowNum = normMat.shape(0)
numTestVec = testRatio * rowNum
errorCount = 0
for i in range(numTestVec):
classifierResult = KNN(normMat[i,:],normMat[numTestVec:rowNum,:],datingLabels[numTestVec:rowNum,:],3)
if (classifierResult != datingLabels[i]): errorCount += 1
print ("The total error rate is %f %%" % (errorCount/numTestVec))