KNN即K-NearestNeighbor，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻近值来代表。



1 KNN算法

1.1 定义

如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

1.2 距离公式

两个样本的距离可以通过如下公式计算，又叫欧式距离。

欧氏距离计算公式如下：

 



比如存在点a(x1, y1, z1)， b(x2, y2, z2)两个点，则a到b的距离为 :



2 电影类型分析

假设我们又现在几部电影：



其中问号电影不知道类别，如何去预测？我们可以利用K近邻算法的思想 。



假设我们选定离未知电影距离最近的三个电影为评判标准(即选择k等于3)，从上图可以看出，离未知类别电影距离最近的电影分别为He's not Really into dues、Beautiful Woman、California Man，三个距离均为爱情片，即算法推断未知电影类型为爱情片。假设此处3个电影类别为两个爱情片、一个动作片，算法计算的结果也为爱情片(即投票法，少数服从多数)。

3 KNN算法API

sklearn.neighbors.KNeighborsClassifier(n_neighbors=5,algorithm='auto')

n_neighbors：int,可选（默认= 5），k_neighbors查询默认使用的邻居数
	
algorithm：{‘auto’，‘ball_tree’，‘kd_tree’，‘brute’}，可选用于计算最近邻居的算法：‘ball_tree’将会使用 BallTree，‘kd_tree’将使用 KDTree。‘auto’将尝试根据传递给fit方法的值来决定最合适的算法。 (不同实现方式影响效率)
（sklearn官网:https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html#sklearn.neighbors.KNeighborsClassifier）

4 案例：预测标签位置（kaggle）



数据介绍：将根据用户的位置，准确性和时间戳预测用户正在查看的业务。

train.csv，test.csv 

row_id：登记事件的ID
	
xy：坐标
	
准确性：定位准确性 
	
时间：时间戳
	
place_id：业务的ID，这是您预测的目标
数据网址:https://www.kaggle.com/navoshta/grid-knn/data

4.1 分析

对于数据做一些基本处理（这里所做的一些处理不一定达到很好的效果，我们只是简单尝试，有些特征我们可以根据一些特征选择的方式去做处理）
缩小数据集范围 DataFrame.query()
	
删除没用的日期数据 DataFrame.drop（可以选择保留）
	
将签到位置少于n个用户的删除place_count = data.groupby('place_id').count()、tf = place_count[place_count.row_id > 3].reset_index()、data = data[data['place_id'].isin(tf.place_id)]
分割数据集
	
标准化处理
	
knn预测
4.2 代码

def knncls():
    """
    K近邻算法预测入住位置类别
    :return:
    """
    # 一、处理数据以及特征工程
    # 1、读取收，缩小数据的范围
    data = pd.read_csv("./train.csv")

    # 数据逻辑筛选操作 df.query()
    data = data.query("x > 1.0 & x < 1.25 & y > 2.5 & y < 2.75")

    # 删除time这一列特征
    data = data.drop(['time'], axis=1)

    print(data)

    # 删除入住次数少于三次位置
    place_count = data.groupby('place_id').count()

    tf = place_count[place_count.row_id > 3].reset_index()

    data = data[data['place_id'].isin(tf.place_id)]

    # 3、取出特征值和目标值
    y = data['place_id']
    # y = data[['place_id']]

    x = data.drop(['place_id', 'row_id'], axis=1)

    # 4、数据分割与特征工程?

    # （1）、数据分割
    x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.3)

    # (2)、标准化
    std = StandardScaler()

    # 队训练集进行标准化操作
    x_train = std.fit_transform(x_train)
    print(x_train)

    # 进行测试集的标准化操作
    x_test = std.fit_transform(x_test)

    # 二、算法的输入训练预测
    # K值：算法传入参数不定的值    理论上：k = 根号(样本数)
    # K值：后面会使用参数调优方法，去轮流试出最好的参数[1,3,5,10,20,100,200]
    knn = KNeighborsClassifier(n_neighbors=1)

    # 调用fit()
    knn.fit(x_train, y_train)

    # 预测测试数据集，得出准确率
    y_predict = knn.predict(x_test)

    print("预测测试集类别：", y_predict)

    print("准确率为：", knn.score(x_test, y_test))

    return None

5. KNN总结

优点：简单，易于理解，易于实现，无需训练
	
缺点：1.懒惰算法，对测试样本分类时的计算量大，内存开销大
                  2.必须指定K值，K值选择不当则分类精度不能保证

使用场景：小数据场景，几千～几万样本，具体场景具体业务去测试
 

 

 

 

 

转载自https://www.cnblogs.com/jyroy/p/9427977.html

作者：JYRoy
一、KNN算法概述
邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。Cover和Hart在1968年提出了最初的邻近算法。KNN是一种分类(classification)算法，它输入基于实例的学习（instance-based learning），属于懒惰学习（lazy learning）即KNN没有显式的学习过程，也就是说没有训练阶段，数据集事先已有了分类和特征值，待收到新样本后直接进行处理。与急切学习（eager learning）相对应。
KNN是通过测量不同特征值之间的距离进行分类。
思路是：如果一个样本在特征空间中的k个最邻近的样本中的大多数属于某一个类别，则该样本也划分为这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

　　

确定绿点属于哪个颜色（红色或者蓝色），要做的就是选出距离目标点距离最近的k个点，看这k个点的大多数颜色是什么颜色。当k取3的时候，我们可以看出距离最近的三个，分别是红色、红色、蓝色，因此得到目标点为红色。
算法的描述：
1）计算测试数据与各个训练数据之间的距离；
2）按照距离的递增关系进行排序；
3）选取距离最小的K个点；
4）确定前K个点所在类别的出现频率；
5）返回前K个点中出现频率最高的类别作为测试数据的预测分类
二、关于K的取值
K：临近数，即在预测目标点时取几个临近的点来预测。
K值得选取非常重要，因为：
如果当K的取值过小时，一旦有噪声得成分存在们将会对预测产生比较大影响，例如取K值为1时，一旦最近的一个点是噪声，那么就会出现偏差，K值的减小就意味着整体模型变得复杂，容易发生过拟合；
如果K的值取的过大时，就相当于用较大邻域中的训练实例进行预测，学习的近似误差会增大。这时与输入目标点较远实例也会对预测起作用，使预测发生错误。K值的增大就意味着整体的模型变得简单；
如果K==N的时候，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了；
K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。
K的取法：
常用的方法是从k=1开始，使用检验集估计分类器的误差率。重复该过程，每次K增值1，允许增加一个近邻。选取产生最小误差率的K。
一般k的取值不超过20，上限是n的开方，随着数据集的增大，K的值也要增大。
三、关于距离的选取
距离就是平面上两个点的直线距离
关于距离的度量方法，常用的有：欧几里得距离、余弦值（cos）, 相关度 （correlation）, 曼哈顿距离 （Manhattan distance）或其他。
四、总结
KNN算法是最简单有效的分类算法，简单且容易实现。当训练数据集很大时，需要大量的存储空间，而且需要计算待测样本和训练数据集中所有样本的距离，所以非常耗时
KNN对于随机分布的数据集分类效果较差，对于类内间距小，类间间距大的数据集分类效果好，而且对于边界不规则的数据效果好于线性分类器。
KNN对于样本不均衡的数据效果不好，需要进行改进。改进的方法时对k个近邻数据赋予权重，比如距离测试样本越近，权重越大。
KNN很耗时，时间复杂度为O(n)，一般适用于样本数较少的数据集，当数据量大时，可以将数据以树的形式呈现，能提高速度，常用的有kd-tree和ball-tree。

一、kNN算法概述
       kNN是k-Nearest Neighbour的缩写，这是一种非常简单且易于理解的分类算法。回想我们从小到大在认知事物的过程当中，我们是如何判断一种事物是属于哪种类别的？通常的一种思路就是，分析当前这个事物与我们之前所知道的类别特征进行比对，找出最接近的一类，然后就可以把这个东西归属于这一个类别。kNN算法大致就是这么一个思路，直接通过测量不同特征值之间的距离来达到分类的目的。
       kNN中的k是指在分类过程中，我们选择样本数据中前k个最相似的数据，以出现次数最多的分类，作为新数据的分类。这里的k通常是不大于20的正整数，k取3或者5的情况比较常见。

二、kNN算法的原理
       首先是训练模型。对kNN而言，在编码过程中训练模型实际上就是记录训练集的所有数据，所以我们常说kNN没有训练模型这一过程。
       接着是测试模型。测试过程有以下几个步骤：
依次计算测试集数据与训练集各个数据之间的距离；
对计算处理的距离进行递增排序；
选择距离最小的k个数据；
选择这k个数据中出现频率最高的类别作为测试数据的预测分类。
       最后是评价模型。根据测试结果计算模型预测分类的准确率。   
     整个过程看上去非常简单、直观、明了。需要说明的是，文中一直提到的距离这个概念，指的是闵可夫斯基距离（Minkowski distance），对应数学上的Lp范数。

      当p=1时，为曼哈顿距离（Manhattan distance），也称L1距离；
      当p=2时，为欧式距离（Euclidean distance），也称L2距离；
      当p=∞时，为切比雪夫距离（distance）。
      在我们使用kNN算法时，常用L1距离和L2距离，且以L2距离使用更多。

三、算法评价
优点：kNN是最简单、最有效的分类器；精度高；对异常值（边缘值）不敏感。
缺点：需要记录所有训练集的数据，空间复杂度高；需要进行大量的计算，计算复杂度高；无法提取出数据内涵的结构信息。
注意点：由于计算距离时使用的是离散型数据，所以kNN算法常用于特征值为数值型和标称型的数据。如果数据特征值为连续值，则需要根据实际情况，对特征值进行离散采样或者采用其他算法模型。