Knn和K-means

kNN就是k近邻算法,用于监督式分类,kNN中的k代表距离最近的k个样本。K-means是聚类算法,非监督式,k-means中的k代表聚类的个数.两者唯一的相似点时均利用近邻信息来标注类别。

K近邻算法

原理

输入: 训练数据集:

$$T={(x_1,y_1),(x_2,y_2),...(x_N,y_N)}$$

其中$x_i \in R^n$为特征向量,$y \in {c_1,c_2,…c_K}$为类别
输出: 实例$x$对应的类$y$

1. 根据给定的距离度量,在训练集中找出与$x$最近的K个点
2. 在这K个点中多数投票原则决定$x$的类别.
   当K=1的时候称为最近邻原则,即距离谁最近就分到谁的那一类中.
   步骤很简单,但是有两个关键问题:距离度量和计算最近点

距离度量

一般距离度量使用$L_p$距离：

$$L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^l-x_j^l|^p)^{\frac{1}{p}} \quad (p>=1)$$

当$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=\infty$时时各个坐标距离的最大值:

$$L_{\infty}(x_i,x_j)=\max_l|x_i^l-x_j^l|$$

这个需要证明:

$$\max_l|x_i^l-x_j^l|<=(\sum_{l=1}^n|x_i^l-x_j^l|^p)^{\frac{1}{p}}<=(n \times \max_l|x_i^l-x_j^l|^p)^{\frac{1}{p}}=n^{\frac{1}{p}} \times \max_l|x_i^l-x_j^l|$$

而

$$\lim_{p \to +\infty} n^{\frac{1}{p}}=1$$

故由夹逼定理即可得出.

计算最近点

可以线性扫描,但是非常耗时,一般采用$kd$树的方式。

K-means

传统K-means

原理

K-Means算法的思想很简单，对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大。
如果用数据表达式表示，假设簇划分为$(C1,C2,…Ck)$则我们的目标是最小化平方误差$E$:

$$E=\sum_{i=1}^k\sum_{x \in C_i} distance(x_i,\mu_i) \tag{1}$$

其中$\mu_i$是$(C1,C2,…Ck)$每个簇的质心:

$$\mu_i=\frac{1}{|C_i|}\sum_{x \in C_i}x \tag{2}$$

算法流程

1. 在训练样本${x_1,x_2,...,x_N}$中随机初始化K(提前确定)个质心$\mu_{i,1},\mu_{i,2},...,\mu_{i,K}$。
2. 计算训练样本与各个质心的距离
3. 根据上诉距离划分K个簇(对于一个点$x_i$到各个质心$\mu_j$的距离,该点距离哪个$\mu_j$近就归到哪一类中)
4. 根据公式(2)重新计算每个簇的质心,更新为$\mu_{i+1,1},\mu_{i+1,2},...,\mu_{i+1,K}$
5. 重复步骤2~4,直到$\mu_{i+1,1},\mu_{i+1,2},...,\mu_{i+1,K}=\mu_{i,1},\mu_{i,2},...,\mu_{i,K}$

K-means++

传统K-means最大的缺陷在于初始化$\mu_1,\mu_2,…,\mu_K$的选择很重要,K_means++就是在输出化质心的选择上面做文章

1. 随机选取一个质心$\mu_1$
2. 计算训练样本${x_1,x_2,…,x_N}$中所有样本到当前已经确定的初始质心的距离的最小值,记作$d_1,d_2,…d_k$(k表示当前已知的质点数.比如说现在已经确定的质心有两个$\mu_1,\mu_2$,先计算所有样本到$\mu_1$的距离,取距离最小的那个样本记作$d_1$,在计算所有样本到$\mu_2$的距离,取距离最小的那个样本记作$d_2$)。
3. 计算上诉得到的样本被选择的概率: $$P(x_i)=\frac{d_i}{\sum_i d_i}$$ 也就是说最小距离大的点有更大的概率被选择
4. 重复1~3,直到选够K个质心作为初始质心.