KNN导读
KNN
算法是机器学习中最简单的算法,一句经典的总结:物以类聚
k-近邻算法
k-nearest neighbor, kNN
是一种基本分类和回归的算法。k
近邻算法中的输入为实例的特征向量,输出为实例的类别,类别可以有多类。算法主要思想:
-
给定一个训练集的数据,实例的类别已定
-
对于新的实例,根据
k
个最近邻的训练实例的类别,经投票表决等方式进行预测 -
算法不具有显式的学习过程,实际上利用训练集对特征向量空间进行划分。
KNN三要素
k
的选择:k
值如何选择?越大越好吗?奇偶性如何?经验值是多少?- 距离度量:选择什么距离来进行度量新实例和训练集上点的距离?
- 分类决策规则:选择怎样的规则来对距离进行分类,从而判断新实例属于哪个类?
k近邻算法
直观解释:给定一个训练数据集,对于新输入的实例,在训练集数据中找出和该实例最邻近的k个实例。这k个实例中的多数属于某个类,就将新实例划分为这个类别。
输入训练数据集
$$
T={(x_1,y_1),(x_2,y_2),…(x_i,y_i)…(x_N,y_N)}
$$
其中,xi为实例特征向量,yi为实例的类别;i=1,2,3,…N。输出:实例x所属的类别y
-
根据给定的距离度量,在训练集
T
中找出与x
最近邻的k
个点,涵盖这个k
个点的x
的邻域记作:Nk(x) -
在邻域Nk(x)中根据分类规则决定x的类别y
$$
y = \mathop {arg max}\limits_{c_j}\sum_{x_i\in{N_k(x)}}I(y_i=c_j), i=1,2…,N;j=1,2,…K
$$
上式中,I为指示函数,即当:yi=cj是为1,不等则为0
k=1
称之为最近邻算法。对于输入的新实例,将训练集中离x最近点的所属类作为x
的类别
k近邻模型
k近邻算法的模型主要有三个要素:
- 距离度量
k
值的选择- 分类决策规则的规定
距离度量
特征空间中两个实例点的距离是两个实例点相似度的反映。
k
近邻模型的特征空间一般是n
维实数向量空间$R^n$。一般使用的欧式距离,也可以是其他距离,如:$L_p$距离或者Minkowski
距离。
假设特征空间$X$是n维实数向量空间$R^n$,${x_i,x_j}\in X$,其中$x_i=(x_i{(1)},x_i{(2)},…,x_i^{(n)})$,
$x_j=(x_j{(1)},x_j{(2)},…,x_j^{(n)})$
$x_i,x_j$的$L_p$的距离定义为
$$
L_p(x_i,x_j)=(\sum_{l=1}{n}|x_i{(l)}-x_j{(l)}|p)^\frac{1}{p}
$$
此距离实际上就是明科夫斯基距离
规定:$p\geq1$
-
当
p=2
时,即为欧式距离,即:
$$
L_2(x_i,x_j)=(\sum_{l=1}{n}|x_i{(l)}-x_j{(l)}|2)^\frac{1}{2}
$$ -
当
p=1
时,即为曼哈顿距离,即:
$$
L_1(x_i,x_j)=\sum_{l=1}{n}|x_i{(l)}-x_j^{(l)}|
$$ -
当$p$趋于无穷,它是各个坐标距离的最大值:
$$
L_{\infty}(x_i,x_j)=\mathop {max}\limits_{l}|x_i{(l)}-x_j{(l)}|
$$
k值选择
k值较小
- 用较小的邻域中的实例进行预测
- 近似误差减小,估计误差增大
- 预测结果对近邻的实例点非常敏感;如果近邻点恰好是噪声,预测出错
k值较大
- 用较大的邻域中的实例点进行预测
- 减少学习的估计误差,但是近似误差增大
- 与输入实例较远的点的训练实例也会起预测作用
- k值增大意味着整个模型变得简单
k值一般选取较小的值,一般是奇数值;通过交叉验证来选取最优的k值
分类决策的规则
k
近邻法中分类决策通常采取的是多数表决,即输入实例的k个近邻的训练实例中的多数列决定输入实例的类。如果分类的损失函数是0-1分类,分类函数是
$$
f:R^n—>{c_1,…,c_n}
$$
误分类的概率是
$$
P(Y\neq {f(X)})=1-P(Y=f(X))
$$
多数表决规则等价于经验风险最小化。
数据归一化处理
将所有的数据映射到同一个尺度上
-
最值归一化:数据映射到0-1上面
$$
X_{scale}= \frac{x-x_{min}}{x_{max}-x_{min}}
$$- 适合分布明显边界的情况:比如考试分数,像素边界
- 缺点:受
outlier
影响,比如收入没有边界
-
均值方差归一化
standardization
:均值为0
,方差为1
的分布中
$$
x_{scale}=\frac{x-{x_{mean}}}{s}
$$- 数据分布没有明显边界
- 可能存在极端数据
1 | # 调用用于均值归一化的类 |
TTS
将导入的样本数据分成训练集
train
和测试集test
两类,一般是2:8
- 分成训练集和测试集
- 需要设置随机种子
seed
1 | from sklearn.model_selection import train_test_split |
网格搜索
- 超参数之间可能存在相互的制约关系
- 比如,
p
只有在method
为distance
的条件下才有意义
1 | import numpy as np |
1 | # 导入数据集 |
1 | from sklearn.model_selection import train_test_split |
1 | # 导入的类就是KNN算法 |
1 | 0.9888888888888889 |
网格搜索参数设置
1 | # 具体参数的设置 |
1 | # 实例化类 |
1 | from sklearn.model_selection import GridSearchCV |
1 | %%time |
1 | GridSearchCV(cv='warn', error_score='raise-deprecating', |
1 | grid_search.best_estimator_ |
1 | KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski', |
1 | # 查看准确率 |
1 | # 查看最终形成的最好参数 |
1 | # 查看测试数据的准确度 |
核数和输出信息显示
1 | # n_jobs几个核,加快速度;verbose:进行算法信息的输出 |
1 | c:\users\admin\venv\lib\site-packages\sklearn\model_selection\_split.py:1978: FutureWarning: The default value of cv will change from 3 to 5 in version 0.22. Specify it explicitly to silence this warning. |
1 | Fitting 3 folds for each of 60 candidates, totalling 180 fits |
1 | [Parallel(n_jobs=1)]: Done 1 out of 1 | elapsed: 0.5s remaining: 0.0s |
1 | [CV] ................... n_neighbors=1, weights=uniform, total= 0.6s |
1 | GridSearchCV(cv='warn', error_score='raise-deprecating', |