• 定义：如果一个样本在特征空间中的 k 个最相似(即特征空间中最邻近)的样本中的大多数属 于某一个类别，则该样本也属于这个类别。
  • 计算两个样本的距离：欧式距离 （也可以是其它距离）
  • sklearn k-近邻算法 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 方法的值来决定最合适的算法。 (不同实现方式影响效率)

      KNN 分类算法的计算过程

  1. 计算待分类点与已知类别的点之间的距离
  2. 按照距离递增次序排序
  3. 选取与待分类点距离最小的 K 个点
  4. 确定前 K 个点所在类别的出现次数

  5. 返回前 K 个点出现次数最高的类别作为待分类点的预测分类

    K值取值影响

  6. 选择较小的 K 值，就相当于用较小的领域中的训练实例进行预测，“学习”的近似误差(对现有训练集的训练误差)会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的 问题是“学习”的估计误差(对测试集的测试误差)会增大

  7. 选择较大的 K 值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少”学 习”的估计误差，但缺点是”学习”的近似误差会增大
  8. K=N（N 为训练样本个数），则完全不足取，因为此时无论输入实例是什么，都只是 简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用信息

  9. 在实际应用中，K 值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是 把训练数据在分成两组:训练集和验证集）来选择最优的 K 值

    k-近邻算法优缺点

  10. 优点

    1. 算法简单，理论成熟，既可以用来做分类也可以用来做回归
    2. 可用于非线性分类
    3. 没有明显的训练过程，而是在程序开始运行时，把数据集加载到内 存后，不需要进行训练，直接进行预测，所以训练时间复杂度为 0
  11. 缺点
    1. 需要算每个测试点与训练集的距离，当训练集较大时，计算量相当 大，时间复杂度高，特别是特征数量比较大的时候
    2. 需要大量的内存，空间复杂度高
    3. 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量 很少），对稀有类别的预测准确度低
    4. 是 lazy learning 方法，基本上不学习，导致预测时速度比起逻辑回 归之类的算法慢

      k 近邻算法实例-预测入住位置

      导入数据

      ```python data = pd.read_csv(“./data/FBlocation/train.csv”) print(data.head()) print(data.shape)

结果： row_id x y accuracy time place_id 0 0 0.7941 9.0809 54 470702 8523065625 1 1 5.9567 4.7968 13 186555 1757726713 2 2 8.3078 7.0407 74 322648 1137537235 3 3 7.3665 2.5165 65 704587 6567393236 4 4 4.0961 1.1307 31 472130 7440663949

(29118021, 6)

  1. <a name="ku7Oq"></a>
  2. ## 处理数据
  3. ```python
  4. # 1、缩小数据,查询数据,为了减少计算时间
  5. data = data.query("x > 1.0 &  x < 1.25 & y > 2.5 & y < 2.75")
  6. # 2、处理时间的数据
  7. time_value = pd.to_datetime(data['time'], unit='s') #把time转为时间类型将时间精确到秒
  8. time_value = pd.DatetimeIndex(time_value) #设置为时间索引
  9. data.insert(data.shape[1], 'day', time_value.day) #data.shape[1]是代表插入到最后的意思
  10. data.insert(data.shape[1], 'hour', time_value.hour)
  11. data.insert(data.shape[1], 'weekday', time_value.weekday)
  12. data = data.drop(['time'], axis=1) # 把时间戳特征删除
  14. # 3、把签到数量少于n个目标位置删除
  15. place_count = data.groupby('place_id').count()
  16. #只选择去的人大于3的数据，认为1,2,3的是噪音，这个地方去的人很少，不用推荐给其他人
  17. tf = place_count[place_count.row_id > 3].reset_index() #reset_index()重新排索引
  18. # 根据设定的地点目标值，对原本的样本进行过滤
  19. data = data[data['place_id'].isin(tf.place_id)]
  21. # 4、取出数据当中的特征值和目标值
  22. y = data['place_id']
  23. # 删除目标值，保留特征值，
  24. x = data.drop(['place_id'], axis=1)
  25. # 删除无用的特征值
  26. x = x.drop(['row_id'], axis=1)

分割训练集和测试集并标准化

  1. x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.25, random_state=1)
  2. std = StandardScaler()
  3. # 对测试集和训练集的特征值进行标准化,分类模型的目标值不用标准化
  4. x_train = std.fit_transform(x_train)
  5. x_test = std.transform(x_test) #transfrom不再进行均值和方差的计算，是在原有的基础上去标准化

网格搜索进行调参

  1. knn = KNeighborsClassifier()
  2. knn.fit(x_train, y_train)
  5. param = {"n_neighbors": [3, 5, 10, 12, 15]} #构造一些参数的值进行搜索
  6. gc = GridSearchCV(knn, param_grid=param, cv=3) #进行网格搜索，cv=3是3折交叉验证，用其中2折训练，1折验证
  7. gc.fit(x_train, y_train)
  8. print("在测试集上准确率：", gc.score(x_test, y_test))
  9. print("在交叉验证当中最好的结果：", gc.best_score_)
  10. print("选择最好的模型是：", gc.best_estimator_)
  12. 结果：
  13. 在测试集上准确率： 0.47966903073286055
  14. 在交叉验证当中最好的结果： 0.4596467484726366
  15. 选择最好的模型是： KNeighborsClassifier(n_neighbors=10)

预测结果

  1. knn = KNeighborsClassifier(n_neighbors=10) #取参数为10
  2. knn.fit(x_train, y_train) #训练
  3. y_predict = knn.predict(x_test) #预测
  4. print("预测的目标签到位置为：", y_predict)
  5. print("预测的准确率:", knn.score(x_test, y_test))