1.KNN分类算法原理

1.1 概述

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

来源：KNN算法最早是由Cover和Hart提出的一种分类算法

KNN算法的指导思想是“近朱者赤，近墨者黑”，由你的邻居来推断出你的类别

 

1.2 算法图示

从训练集中找到和新数据最接近的k条记录，然后根据多数类来决定新数据类别。算法涉及3个主要因素： 训练数据集距离或相似度的计算衡量 k的大小

算法描述：

已知两类“先验”数据，分别是蓝方块和红三角，他们分布在一个二维空间中有一个未知类别的数据（绿点），需要判断它是属于“蓝方块”还是“红三角”类考察离绿点最近的3个（或k个）数据点的类别，占多数的类别即为绿点判定类别

1.3 算法要点

1.3.1 计算步骤

步骤如下：

   1）算距离：给定测试对象，计算它与训练集中的每个对象的距离

    2）找邻居：圈定距离最近的k个训练对象，作为测试对象的近邻

    3）做分类：根据这k个近邻归属的主要类别，来对测试对象分类

1.3.2 相似度的衡量

距离越近应该意味着这两个点属于一个分类的可能性越大。 但是距离不能代表一切，有些数据的相似度衡量并不适合用距离相似度衡量方法：包括欧式距离、夹角余弦等。

（简单应用中，一般使用欧氏距离，但对于文本分类来说，使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适）

1.3.3 类别的判定

简单投票法：少数服从多数，近邻中哪个类别的点最多就分为该类。加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）

1.4 算法不足之处

1.样本不平衡容易导致结果错误

如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。改善方法：对此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。

2.计算量较大

因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。改善方法：事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。

该方法比较适用于样本容量比较大的类域的分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

 

2 KNN分类算法python实战

from sklearn.model_selection import train_test_split, GridSearchCV from sklearn.neighbors import KNeighborsClassifier from sklearn.preprocessing import StandardScaler import pandas as pd def knncls(): """ K-近邻预测用户签到位置 :return:None """ # 读取数据 data = pd.read_csv("./data/FBlocation/train.csv") # print(data.head(10)) # 处理数据 # 1、缩小数据,查询数据晒讯 data = data.query("x > 1.0 & x < 1.25 & y > 2.5 & y < 2.75") # 处理时间的数据 time_value = pd.to_datetime(data['time'], unit='s') print(time_value) # 把日期格式转换成 字典格式 time_value = pd.DatetimeIndex(time_value) # 构造一些特征 data['day'] = time_value.day data['hour'] = time_value.hour data['weekday'] = time_value.weekday # 把时间戳特征删除 data = data.drop(['time'], axis=1) print(data) # 把签到数量少于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)] # 取出数据当中的特征值和目标值 y = data['place_id'] x = data.drop(['place_id'], axis=1) # 进行数据的分割训练集合测试集 x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.25) # 特征工程（标准化） std = StandardScaler() # 对测试集和训练集的特征值进行标准化 x_train = std.fit_transform(x_train) x_test = std.transform(x_test) # 进行算法流程 # 超参数 knn = KNeighborsClassifier() # # fit， predict,score knn.fit(x_train, y_train) # # 得出预测结果 y_predict = knn.predict(x_test) print("预测的目标签到位置为：", y_predict) # # 得出准确率 print("预测的准确率:", knn.score(x_test, y_test)) return None if __name__ == "__main__": knncls() from sklearn.model_selection import train_test_split, GridSearchCV from sklearn.neighbors import KNeighborsClassifier from sklearn.preprocessing import StandardScaler import pandas as pd def knncls(): """ K-近邻预测用户签到位置 :return:None """ # 读取数据 data = pd.read_csv("./data/FBlocation/train.csv") # print(data.head(10)) # 处理数据 # 1、缩小数据,查询数据晒讯 data = data.query("x > 1.0 & x < 1.25 & y > 2.5 & y < 2.75") # 处理时间的数据 time_value = pd.to_datetime(data['time'], unit='s') print(time_value) # 把日期格式转换成 字典格式 time_value = pd.DatetimeIndex(time_value) # 构造一些特征 data['day'] = time_value.day data['hour'] = time_value.hour data['weekday'] = time_value.weekday # 把时间戳特征删除 data = data.drop(['time'], axis=1) print(data) # 把签到数量少于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)] # 取出数据当中的特征值和目标值 y = data['place_id'] x = data.drop(['place_id'], axis=1) # 进行数据的分割训练集合测试集 x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.25) # 特征工程（标准化） std = StandardScaler() # 对测试集和训练集的特征值进行标准化 x_train = std.fit_transform(x_train) x_test = std.transform(x_test) # 进行算法流程 # 超参数 knn = KNeighborsClassifier() # 构造一些参数的值进行搜索 param = {"n_neighbors": [3, 5, 10]} # 进行网格搜索 gc = GridSearchCV(knn, param_grid=param, cv=2) gc.fit(x_train, y_train) # 预测准确率 print("在测试集上准确率：", gc.score(x_test, y_test)) print("在交叉验证当中最好的结果：", gc.best_score_) print("选择最好的模型是：", gc.best_estimator_) print("每个超参数每次交叉验证的结果：", gc.cv_results_) return None if __name__ == "__main__": knncls()

 

3 KNN算法补充

3.1、k值设定为多大？

k太小，分类结果易受噪声点(异常点)影响；k太大，近邻中又可能包含太多的其它类别的点。

（对距离加权，可以降低k值设定的影响）

k值通常是采用交叉检验来确定（以k=1为基准）

经验规则：k一般低于训练样本数的平方根

 

3.2、类别如何判定最合适？

投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。而具体如何加权，需要根据具体的业务和数据特性来探索

 

3.3、如何选择合适的距离衡量？

高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。

变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。

 

3.4、训练样本是否要一视同仁？

在训练集中，有些样本可能是更值得依赖的。

也可以说是样本数据质量的问题

可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。

 

3.5、性能问题？

kNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找k个近邻）。

懒惰的后果：构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。

已经有一些方法提高计算的效率，例如压缩训练样本量等。

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