分类算法-K近邻算法（KNN）_用cuda设计一个knn分类算法(k近邻算法)程序。在特征空间中查找k个最相似或者距离

• 定义：如果一个样本在特征空间中的 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值取值影响

1. 选择较小的 K 值，就相当于用较小的领域中的训练实例进行预测，“学习”的近似误差(对现有训练集的训练误差)会减小，只有与输入实例较近或相似的训练实例才会对预测结果起作用，与此同时带来的 问题是“学习”的估计误差(对测试集的测试误差)会增大
2. 选择较大的 K 值，就相当于用较大领域中的训练实例进行预测，其优点是可以减少"学 习"的估计误差，但缺点是"学习"的近似误差会增大
3. K=N（N 为训练样本个数），则完全不足取，因为此时无论输入实例是什么，都只是 简单的预测它属于在训练实例中最多的类，模型过于简单，忽略了训练实例中大量有用信息
4. 在实际应用中，K 值一般取一个比较小的数值，例如采用交叉验证法（简单来说，就是 把训练数据在分成两组:训练集和验证集）来选择最优的 K 值

k-近邻算法优缺点

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

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

导入数据

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
2
3
4
5
6
7
8
9
10
11
12
13

处理数据

# 1、缩小数据,查询数据,为了减少计算时间
data = data.query("x > 1.0 &  x < 1.25 & y > 2.5 & y < 2.75")
# 2、处理时间的数据
time_value = pd.to_datetime(data['time'], unit='s') #把time转为时间类型将时间精确到秒
time_value = pd.DatetimeIndex(time_value) #设置为时间索引
data.insert(data.shape[1], 'day', time_value.day) #data.shape[1]是代表插入到最后的意思
data.insert(data.shape[1], 'hour', time_value.hour)
data.insert(data.shape[1], 'weekday', time_value.weekday)
data = data.drop(['time'], axis=1) # 把时间戳特征删除

# 3、把签到数量少于n个目标位置删除
place_count = data.groupby('place_id').count()
#只选择去的人大于3的数据，认为1,2,3的是噪音，这个地方去的人很少，不用推荐给其他人
tf = place_count[place_count.row_id > 3].reset_index() #reset_index()重新排索引
# 根据设定的地点目标值，对原本的样本进行过滤
data = data[data['place_id'].isin(tf.place_id)]

# 4、取出数据当中的特征值和目标值
y = data['place_id']
# 删除目标值，保留特征值，
x = data.drop(['place_id'], axis=1)
# 删除无用的特征值
x = x.drop(['row_id'], axis=1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

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

网格搜索进行调参

knn = KNeighborsClassifier()
knn.fit(x_train, y_train)


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

结果：
在测试集上准确率： 0.47966903073286055
在交叉验证当中最好的结果： 0.4596467484726366
选择最好的模型是： KNeighborsClassifier(n_neighbors=10)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

预测结果

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