[数据结构与算法]k-近邻算法 （facebook预测入住位置）

1.举个例子：

（1）我想定位我自己的位置，我可以询问五个人在哪些地方和我们之间的距离判断

通过邻居来判断自己的距离

（2）给了七部电影，判断是爱情片还是动作片，一个电影与其它电影之间的距离，判别属于哪个类型。

通过与未知电影的距离，来判断属于什么类型的电影，所以我们求的重点就在于距离如何去求？

2.定义：

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

计算距离公式：欧式距离平方求和求根

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PyxItsaE-1641829375181)(C:\Users\DELL\AppData\Roaming\Typora\typora-user-images\image-20220110194719036.png)]

相似的样本，特征之间的值应该都是相近的。

注意：k近邻算法需要做标准化处理，避免某一个特征对整体影响太大。

3.api

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

n_neighbors=5:默认邻居数 [ 会影响结果 ]

algorithm：默认使用的算法

4.k临近算法实例——预测一个人要登记的地方

（1）实例：预测入住位置【分类问题】

需求：预测一个人要登记的地方。

特征值：x,y坐标，定位准确性，时间

目标值：place_id(入住位置的id)

（2）处理：

由于数据量大，xy缩小节省时间

时间戳进行处理（年月日周时分秒）当做新的特征

几千—几万，少于指定签到人数的位置删除

（3）代码

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler

def knncls():
    '''
    K-近邻预测用户签到位置
    :return:None
    '''
    # 读取数据
    # 1.缩小数据 数据筛选
    data = pd.read_csv('./data/train.csv')
    print(data.head(10))
    # 处理数据
    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(n_neighbors=5)
    # 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()

5.总结：

问题：

k值取多大？有什么影响？

k值取很小：容易受异常点影响

k值取很大：容易受k值数量（类别）的波动

性能问题？

时间复杂度很高

优点：易于理解，无需估计参数（算法里面的参数），无需训练不需要迭代

缺点：计算内存开销都大，指定k值，k值选择不当分类精度不能保证

使用场景：小数据场景，几千到几万