目录
1、kNN算法（K 最近邻(k-Nearest Neighbors)）描述
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算法的应用领域
字符识别、文本分类、图像识别、改进约会网站、手写识别系统、电影分类
8、KNN算法实战：电影分类
需要模块：numpy（科学计算包），operator（运算符模块）；
欧式距离公式：
环境：python3.6 ，Pycharm
kNN.py
import numpy as np
import operator
'''
函数说明: 创建数据集
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()
参考资料：《机器学习实战》
博客：https://blog.csdn.net/c406495762/article/category/7029976
京公网安备 11010502036488号