KNN算法
1. KNN算法原理
k近邻方法是一种惰性学习算法，可以用于回归和分类，它的主要思想是投票机制，对于一个测试实例x, 我们在有标签的训练数据集上找到和最相近的k个数据，用他们的label进行投票，分类问题则进行表决投票，回归问题使用加权平均或者直接平均的方法。
1.1 K值选择
kNN中的k是一个超参数，需要我们进行指定，一般情况下这个k和数据有很大关系，都是交叉验证进行选择，但是建议使用交叉验证的时候，k∈[2,20]，使用交叉验证得到一个很好的k值。需注意最好K的取值为奇数，防止出现平票而无法分类的情况。
k值还可以表示我们的模型复杂度，k值越小，意味着模型复杂度变大，更容易过拟合(用极少数的样例来绝对这个预测的结果，很容易产生偏见，这就是过拟合)。k值越大，学习的估计误差越小，但是学习的近似误差就会增大，容易造成欠拟合。
1.2 距离计算
样本之间的距离的计算，我们一般使用对于一般使用Lp距离进行计算。当p=1时候，称为曼哈顿距离(Manhattan distance)，当p=2时候，称为欧氏距离(Euclidean distance)，当p=∞时候，称为极大距离(infty distance), 表示各个坐标的距离最大值,另外也包含夹角余弦等方法。
一般采用欧式距离较多，但是文本分类则倾向于使用余弦来计算相似度。
对于两个向量
(
x
i
,
x
j
)
(x_i,x_j)
(xi,xj),一般使用
L
p
L_p
Lp距离进行计算。 假设特征空间
X
X
X是n维实数向量空间
R
n
R^n
Rn , 其中,
x
i
,
x
j
∈
X
x_i,x_j \in X
xi,xj∈X,
x
i
=
(
x
i
(
1
)
,
x
i
(
2
)
,
…
,
x
i
(
n
)
)
x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \ldots, x_{i}^{(n)}\right)
xi=(xi(1),xi(2),…,xi(n)),
x
j
=
(
x
j
(
1
)
,
x
j
(
2
)
,
…
,
x
j
(
n
)
)
x_{j}=\left(x_{j}^{(1)}, x_{j}^{(2)}, \ldots, x_{j}^{(n)}\right)
xj=(xj(1),xj(2),…,xj(n))
x
i
，
x
j
x_i，x_j
xi，xj的
L
p
L_p
Lp距离定义为:
L
p
(
x
i
,
x
j
)
=
(
∑
l
=
1
n
∣
x
i
(
l
)
−
x
j
(
l
)
∣
p
)
1
p
L_{p}\left(x_{i}, x_{j}\right)=\left(\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right|^{p}\right)^{\frac{1}{p}}
Lp(xi,xj)=(l=1∑n∣∣∣xi(l)−xj(l)∣∣∣p)p1
这里的 p ≥ 1 p\geq1 p≥1. 当 p = 2 p=2 p=2时候，称为欧氏距离(Euclidean distance)：
L 2 ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ 2 ) 1 2 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}} L2(xi,xj)=(l=1∑n∣∣∣xi(l)−xj(l)∣∣∣2)21
当 p = 1 p=1 p=1时候，称为曼哈顿距离(Manhattan distance)：
L 1 ( x i , x j ) = ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ L_{1}\left(x_{i}, x_{j}\right)=\sum_{l=1}^{n}\left|x_{i}^{(l)}-x_{j}^{(l)}\right| L1(xi,xj)=l=1∑n∣∣∣xi(l)−xj(l)∣∣∣
当 p = ∞ p=\infty p=∞时候，称为极大距离(infty distance), 表示各个坐标的距离最大值：
L p ( x i , x j ) = max l n ∣ x i ( l ) − x j ( l ) ∣ L_{p}\left(x_{i}, x_{j}\right)=\max _{l} n\left|x_{i}^{(l)}-x_{j}^{(l)}\right| Lp(xi,xj)=lmaxn∣∣∣xi(l)−xj(l)∣∣∣
1.3 算法优缺点
优点：
- 算法简单，容易理解
- 对于边界不规则的数据效果较好，效果优于线性分类器。
缺点：
- 预测时需用到全部现有数据集，因此只适用于小数据集。
- 非平衡数据预测效果较差。
- 不适合特征维度太多的数据。