K近邻算法概述
K近邻（k-Nearest Neighbor，简称KNN）学习是一种常用的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个邻居的信息来进行预测。简单的说，K近邻算法采用不同特征值之间的距离方法进行分类。
优点：精度高、对异常值不敏感、无数据输入假定
缺点：计算复杂度高、空间复杂度高。
适用数据范围：数值型和标称型。
K近邻算法工作原理
- 假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
- 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
- 计算新数据与样本数据集中每条数据的距离
- 对求得的所有距离进行排序（从小到大，越小表示越相似）
- 取前k个数据中出现次数最多的分类标签作为新数据的分类
- 求k个数据中出现次数最多的分类标签作为新数据的分类。
通俗理解：给定一个训练数据集，对新的输入实例，在训练集中找到与该实例最邻近的k个实例，这k个实例的多数属于某个分类，就把该输入实例分为这个类。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中K的出处，通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
image.png
KNN 改进约会网站的配对效果项目案例
项目来自机器学习实战一书，代码参考
项目概述
海伦一直使用在线约会网站寻找适合自己的约会对象。经过一番总结，她发现曾经交往过三种类型的人：
- 不喜欢的人
- 魅力一般的人
- 极具魅力的人
海伦收集约会数据已经有了一段时间，他把这些数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共有1000行。海伦的样本主要包含以下三种特征：
- 每年获得的飞行常客里程数
- 玩视频游戏所耗时间百分比
- 每周消费的冰激凌公升数
海伦希望：
- 周一到周五约会那些魅力一般的人
- 周末与那些极具魅力的人为伴
程序实现
1、将特征数据的该死改变成分类器可以接受的格式。将文本记录转换到NumPy的解析程序
文本内容示例
40920 8.326976 0.953952 3
14488 7.153469 1.673904 2
26052 1.441871 0.805124 1
75136 13.147394 0.428964 1
38344 1.669788 0.134296 1
72993 10.141740 1.032955 1
.....
从文件中加载数据
import numpy as np
# 导入科学计算包numpy和运算符模块operator
import operator
from os import listdir
from collections import Counter
def file2matrix(filename):
fr = open(filename)
# 获得文件中的数据行的行数
numberOfLines = len(fr.readlines())
# 生成对应的空矩阵，例如：zeros(2，3)就是生成一个 2*3的矩阵，各个位置上全是 0
returnMat = np.zeros((numberOfLines,3))
classLabelVector = []
index = 0
fr = open(filename)
for line in fr.readlines():
line = line.strip()
listFromLine = line.split('\t')
# 每列的属性数据
returnMat[index,:] = listFromLine[0:3]
# 每列的类别数据，就是 label 标签数据
classLabelVector.append(int(listFromLine[-1]))
index +=1
return returnMat,classLabelVector
归一化特征值
def autoNorm(dataSet):
"""
归一化特征值，消除属性之间量级不同导致的影响
param dataSet: 数据集
return 归一化后的数据集normDataSet
归一化公式：
Y = (X-Xmin)/(Xmax-Xmin)
其中的 min 和 max 分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征值转化为0到1的区间。
"""
minVals = dataSet.min(0)
maxVals = dataSet.max(0)
ranges = maxVals - minVals
normDataSet = np.zeros(np.shape(dataSet))
m = dataSet.shape[0]
#numpy.tile(A,reps)tile共有2个参数，A指待输入数组，reps则决定A重复的次数。整个函数用于重复数组A来构建新的数组。
## 生成与最小值之差组成的矩阵
normDataSet = dataSet - np.tile(minVals, (m,1))
# 将最小值之差除以范围组成矩阵
normDataSet = normDataSet / np.tile(ranges,(m,1))
return normDataSet
K近邻算法，使用欧氏距离
n维空间公式
image.png
```K-近邻算法
inX:用于分类的输入向量
dataSet:训练样本集
labels:标签向量
k:用于选择最近邻居的数目```
def classify0(inX,dataSet,labels,k):
#计算两个向量点xA和xB之间的距离
dataSetSize = dataSet.shape[0]
diffMat = np.tile(inX,(dataSetSize,1)) - dataSet
sqDiffMat = diffMat**2
#axis =0 普通相加，axis=1 每一行向量相加
sqDistances = sqDiffMat.sum(axis=1)
#开方
distances = sqDistances **0.5
#分类距离的索引 将x中的元素从小到大排列，提取其对应的index(索引)，然后输出到sortedDistIndicies
sortedDistIndicies = distances.argsort()
classCount = {}
#选择最小距离点，确定前k个距离最小元素所在的主要分类
for i in range(k):
#找到该样本的类型
voteIlabel = labels[sortedDistIndicies[i]]
# 在字典中将该类型加一
classCount[voteIlabel] = classCount.get(voteIlabel,0)+1
# 按照第二个元素的次序对元祖进行排序 reverse True降序 ； 默认False 升序
sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse=True)
#获取第一个元素的键
return sortedClassCount[0][0]
对约会网站的测试方法
def datingClassTest():
# 设置测试数据的的一个比例（训练数据集比例=1-hoRatio）
hoRatio = 0.10
# 从文件中加载数据
datingDataMat,datingLabels = file2matrix('../input/2.KNN/datingTestSet2.txt')
# 归一化数据
normMat = autoNorm(datingDataMat)
# m 表示数据的行数，即矩阵的第一维
m = normMat.shape[0]
# 设置测试的样本数量， numTestVecs:m表示训练样本的数量
numTestVecs = int(m*hoRatio)
errorCount = 0.0
for i in range(numTestVecs):
# 对数据测试
classifierResult = classify0(normMat[i,:], normMat[numTestVecs:m,:], datingLabels[numTestVecs:m], 3)
if (classifierResult != datingLabels[i]) : errorCount += 1.0
print("the total error rate is: %f" % (errorCount / float(numTestVecs)))
the total error rate is: 0.050000
