4.9 更多关于k近邻算法的思考
2019-07-03 本文已影响0人
逆风的妞妞
4.9 更多关于k近邻算法的思考
K近邻算法是解决分类问题，天然可以解决多分类问题。不仅如此，思想简单，效果强大。使用Ｋ近邻算法还可以解决回归问题。比如预测下一个学生考试的分数，股票的趋势等。在scikit-learn中封装了一个类叫KNeighborsRegressor就是使用k近邻解决回归问题。
但是k近邻算法也有很多缺点：
- 最大的缺点就是效率低下。如果训练有m个样本，n个特征，则预测每一个新的数据，需要O(m*n)的时间复杂度，即使我们可以进行优化，使用树结构：KD-Tree,Ball-Tree,但是效率还是十分低的。
- 高度数据相关，对outliner更为敏感
- 预测的结果不具有可解释性
- 维数灾难：随着维度的增加，“看似相近”的两个点之间的距离越来越大。解决办法：降维
举例说明
| 1维 | 0-1的距离 | 1 |
|---|---|---|
| 2维 | (0,0)到(1,1)的距离 | 1.414 |
| 3维 | (0,0,0)到(1,1,1)的距离 | 1.73 |
| 64维 | (0,0,...0)到(1,1,...1)的距离 | 8 |
| 100维 | (0,0,...0)到(1,1,...1)的距离 | 100] |
image
