1、kNN算法（K 最近邻(k-Nearest Neighbors)）描述
简单地说，k-近邻算法采用测量不同特征值之间的距离方法进行分类。
k-近邻算法
是一种基本
分类与回归
方法；它是是
监督学习
中分类方法的一种，属于
懒散学习法
（惰性学习方法）。
给定一个
训练集D
和一个
测试对象z
,该测试对象是一个由
属性值
和一个
未知的类别标签
组成的向量，该算法需要计算z和每个训练对象之间的距离（或相似度），这样就可以确定最近邻的列表。然后将最近邻中实例数量占优的类别赋给z。（
主要思想
是如果一个样本在特征空间中的k个最近的样本中的大多数都属于某个类别，则该样本属于这个类别，并具有这个类别上的特性 ）。
注释：
（1）所谓
监督学习
与
非监督学习
，是指训练数据是否有标柱类别，若有则为监督学习，否则为非监督学习。 监督学习是指根据训练数据学习一个模型，然后能对后来的输入做预测。在监督学习中，输入变量和输出变量可以是连续的，也可以是离散的。若输入变量和输出变量均为连续变量，则称为
回归
；输出变量为有限个离散变量，则称为
分类
。
（2）
懒散学习法
在训练过程中不需要做许多处理。只有当新的未被分类的数据输入时，这类算法才会去做分类。
积极学习
法则会在训练中建立一个分类模型，当新的未分类数据输入时，这类学习器会把新数据也提供给这个分类模型。
2.KNN算法的工作原理：
存在一个样本数据集合，也称作为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据(最近邻)的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，
通常k是不大于20的整数
。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。
3、KNN算法的一般流程
（1）
收集数据
：可以使用任何方法。
（2）
准备数据
：距离计算所需要的数值，最好是结构化的数据格式。
（3）
分析数据
：可以使用任何方法。
（4）
训练算法
：此步骤不适用于k-近邻算法。
（5）
测试算法
：计算错误率。
（6）
使用算法
：首先需要输入样本数据和结构化的输出结果，然后运行KNN算法判定输入数据分别属于哪个分类，最后应用对计算出的分类执行后续处理
注释：
距离度量公式有
：欧几里得距离，明可夫斯基距离，曼哈顿距离，切比雪夫距离，马氏距离等；
相似度的度量公式有
：余弦相似度，皮尔森相关系数，Jaccard相似系数。
补充
：欧几里得距离度量会受特征不同单位刻度的影响，所以一般需要先进行标准化处理。
类别的判断方法
：（1）
投票决定
：少数服从多数，近邻中哪个类别的点最多就分为该类。
（2）
加权投票法
：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大。 knn还可用于回归，目标样本的属性值是k个邻居属性值的平均值。
4、KNN算法的优点和缺点
优点：
简单，易于理解，易于实现，无需估计参数，无需训练（不需要花费任何时间做模型的构造）， 特别适合多分类问题，适合对稀有事件进行分类，
精度高
，
对异常值不敏感
，
无数据输入假定
。
缺点：
消极学习法， 需要大量的存储空间（需要保存全部数据集）， 耗时（需计算目标样本与训练集中每个样本的值），可解释性差；即该算法的存储复杂度是O(n)，其中n为训练对象的数量，时间复杂度也是O(n)（
计算复杂度高，空间复杂度高
）
注释：
积极学习法
：先根据训练集构造出分类模型，根据分类模型对测试集分类。
消极学习法
（基于实例的学习法）：推迟建模，当给定训练元组时，简单地存储训练数据，一直等到给定一个测试样本。
适用数据范围：
数值型和标称型。（
标称型：
一般在有限的数据中取，而且只存在‘是’和‘否’两种不同的结果（一般用于分类）；
数值型：
可以在无限的数据中取，而且数值比较具体化，例如4.02,6.23这种值（一般用于回归分析））
5、应用KNN的常见问题
（1）k值设定为多大？
k太小，分类结果易受噪声的影响；k太大，近邻中又可能包含太多的其它类别的点。（对距离加权，可以降低k值设定的影响）。
k值通常是采用交叉检验来确定（以k=1为基准）。
经验规则：k一般低于训练样本数的平方根
（2）类别如何判定最合适？
投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。
（3）如何选择合适的距离衡量？
高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。
变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。
（4）训练样本是否要一视同仁？
在训练集中，有些样本可能是更值得依赖的。
可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。（如何判断样本可信不可信）
（5）能否大幅减少训练样本量，同时又保持分类精度？
浓缩技术(condensing)
编辑技术(editing)
6、KNN与推荐系统
利用KNN进行推荐的方法分为：
（1）user-based: 先利用KNN算法找到与目标用户兴趣相似的k个用户，再根据这些相似用户的兴趣为目标用户进行推荐。
（2）item-based: 利用KNN计算与目标用户喜欢的物品相似的k个物品，然后推荐给目标用户
7、KNN算法的应用领域
字符识别、文本分类、图像识别、改进约会网站、手写识别系统、电影分类
KNN算法简单实战：简单的电影分类
需要模块：numpy（科学计算包），operator（运算符模块）；
欧式距离公式：
环境：python3.6 ，Pycharm
kNN.py
import
numpy
as
np
import
operator
'''
函数说明
:
创建数据集
Parameters:
无
Returns:
group -
数据集
labels -
分类标签
'''
def
createDataSet():
group=np.
array
([[
1
,
101
],[
5
,
89
],[
108
,
5
],[
115
,
8
]])
#
数据集，四组二维特征
labels=[
'
爱情片
'
,
'
爱情片
'
,
'
动作片
'
,
'
动作片
'
]
#
分类标签，四组特征的标签
return
group,labels
"""
函数说明
:kNN
算法
,
分类器
Parameters:
inX -
用于分类的数据
(
测试集
)
dataSet -
用于训练的数据
(
训练集
)
labes -
分类标签
k - kNN
算法参数
,
选择距离最小的
k
个点
Returns:
sortedClassCount[0][0] -
分类结果
"""
def classify0(inX,dataSet,labels,k):
# numpy函数shape[0]返回dataSet的行数
dataSetSize=dataSet.shape[0]
# b = tile(a,(m,n)):即是把a数组里面的元素复制n次放进一个数组c中，然后再把数组c复制m次放进一个数组b中
diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
# 二维特征相减后平方
sqDiffMat = diffMat ** 2
# sum()所有元素相加，sum(0)列相加，sum(1)行相加
sqDistances = sqDiffMat.sum(axis=1)
# 开方，计算出距离
distances = sqDistances ** 0.5
# 返回distances中元素从小到大排序后的索引值
sortedDistIndices = distances.argsort()
# 定一个记录类别次数的字典
classCount = {}
for i in range(k):
# 取出前k个元素的类别
voteIlabel = labels[sortedDistIndices[i]]
# dict.get(key,default=None),字典的get()方法,返回指定键的值,如果值不在字典中返回默认值。
# 计算类别次数
classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
# python3中用items()替换python2中的iteritems()
# key=operator.itemgetter(1)根据字典的值进行排序
# key=operator.itemgetter(0)根据字典的键进行排序
# reverse降序排序字典
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
# 返回次数最多的类别,即所要分类的类别
return sortedClassCount[0][0]
if __name__ == '__main__':
#创建数据集
group, labels = createDataSet()
#测试集
test = [101,20]
#kNN分类
test_class = classify0(test, group, labels, 3)
#打印分类结果
print(test_class)
注意：numpy函数shape[0]、tile()的用法、sum(axis=1)、argsort()
参考资料：《机器学习实战》
博客网站：
http://cuijiahua.com/
