K邻近算法(KNN)

2019-05-08 本文已影响0人陨星落云

K邻近算法(KNN)

kNN 可以说是最简单的监督学习分类器了。想法也很简单，就是找出测试数据在特征空间中的最近邻居。我们将使用下面的图片介绍它。

knn.png

上图中的对象可以分成两组，蓝色方块和红色三角。每一组也可以称为一个类。我们可以把所有的这些对象看成是一个城镇中房子，而所有的房子分别属于蓝色和红色家族，而这个城镇就是所谓的特征空间。
现在城镇中来了一个新人，他的新房子用绿色圆盘表示。我们要根据他房子的位置把他归为蓝色家族或红色家族。我们把这过程成为分类。我们应该怎么做呢？因为我们正在学习看 kNN，那我们就使用一下这个算法吧。一个方法就是查看他最近的邻居属于那个家族，从图像中我们知道最近的是红色三角家族。所以他被分到红色家族。这种方法被称为简单近邻，因为分类仅仅决定与它最近的邻居。
但是这里还有一个问题。红色三角可能是最近的，但如果他周围还有很多蓝色方块怎么办呢？此时蓝色方块对局部的影响应该大于红色三角。所以仅仅检测最近的一个邻居是不足的。所以我们检测 k 个最近邻居。谁在这 k 个邻居中占据多数，那新的成员就属于谁那一类。如果 k 等于 3，也就是在上面图261像中检测 3 个最近的邻居。他有两个红的和一个蓝的邻居，所以他还是属于红色家族。但是如果 k 等于 7 呢？他有 5 个蓝色和 2 个红色邻居，现在他就会被分到蓝色家族了。k 的取值对结果影响非常大。更有趣的是，如果 k 等于 4呢？两个红两个蓝。这是一个死结。所以 k 的取值最好为奇数。这中根据 k 个最近邻居进行分类的方法被称为 kNN。

工作原理

存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每个数据与所属分类的对应关系。
输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的距离特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签
一般来说，只选择样本数据集中前N个最相似的数据。K一般不大于20，最后，选择k个中出现次数最多的分类，作为新数据的分类.

距离度量
$x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(n)}\right)^{T}$

Lp距离：
$L_{p}\left(x_{i}, x_{j}\right)=\left(\sum_{i=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{p}\right)^{\frac{1}{p}}$
欧式距离:
$L_{2}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{2}\right)^{\frac{1}{2}}$
曼哈顿距离:
$L_{1}\left(x_{i}, x_{j}\right)=\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|$
L∞距离:

$L_{\infty}\left(x_{i}, x_{j}\right)=\max _{l}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|$

K值的选择

如果选择较小的K值
“学习”的近似误差（approximation error)会减小，但 “学习”的估计误差（estimation error) 会增大，
噪声敏感
K值的减小就意味着整体模型变得复杂，容易发生过拟合.
如果选择较大的K值，
减少学习的估计误差，但缺点是学习的近似误差会增大.
K值的增大就意味着整体的模型变得简单.
一般情况下，K 会倾向选取较小的值，并使用交叉验证法选取最优 K 值。

K-Nearest Neighbors算法特点

适用数据范围: 数值型和标称型

优点	缺点
精度高	计算复杂度高
对异常值不敏感	空间复杂度高
无数据输入假定

sklearn.neighbors.KNeighborsClassifier
创建一个K近邻分类器，主要参数有：
• n_neighbors：用于指定分类器中K的大小(默认值为5，注意与kmeans的区别)
• weights：设置选中的K个点对分类结果影响的权重（默认值为平均权重“uniform”，可以选择“distance”代表越近的点权重越高，或者传入自己编写的以距离为参数的权重计算函数）

• algorithm：设置用于计算临近点的方法，因为当数据量很大的情况下计算当前点和所有点的距离再选出最近的k各点，这个计算量是很费时的，所以（选项中有ball_tree、kd_tree和brute，分别代表不同的寻找邻居的优化算法，默认值为auto，根据训练数据自动选择）

• n_jobs：int，可选（默认= 1),用于邻居搜索的并行作业数。如果-1，则将作业数设置为CPU内核数。

• p: int, 可选当p=1时,为曼哈顿距离;默认p=2,欧式距离.

k邻近分类

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

# 加载iris数据
iris = load_iris()
# 将数据分为训练集和测试集,一般test_size设为0.25,这里设置为3个测试样本便于观察结果.
X_train,X_test,y_train,y_test = train_test_split(iris.data,iris.target,test_size=3,random_state=1) 

# 进行标准化
std = StandardScaler()
X_train = std.fit_transform(X_train)
X_test = std.transform(X_test)
# estimator流程
knn = KNeighborsClassifier(n_neighbors=5,weights='uniform', algorithm='auto',  p=2, metric='minkowski', n_jobs=1)
# 得出模型
knn.fit(X_train,y_train)
#进行预测并得出精度
y_predict = knn.predict(X_test)
print('测试集预测结果：{}'.format(y_predict))
print('测试集预测结果名称：{}'.format(iris.target_names[y_predict]))
print('测试集目标值名称：{}'.format(iris.target_names[y_test]))
print('训练集精度：{:.2f}'.format(knn.score(X_train,y_train)))
score = knn.score(X_test,y_test)
print('测试集精度：{:.2f}'.format(score)) # 等价于print(np.mean(y_predict==y_test))

测试集预测结果：[0 1 1]
测试集预测结果名称：['setosa' 'versicolor' 'versicolor']
测试集目标值名称：['setosa' 'versicolor' 'versicolor']
训练集精度：0.96
测试集精度：1.00

参考资料：
《python机器学习教程》《python机器学习应用》《OpenCV-Python-Toturial》《统计学习方法》《sklearn官方文档》

K邻近算法(KNN)

K邻近算法(KNN)

猜你喜欢

热点阅读