K-means 与KNN

尽管K-means与KNN都是K字辈的算法，但这两个算法是完全不同的。KNN为监督学习中的一种分类算法，K-means为非监督学习中的聚类算法。

两者相同之处是均利用近邻信息来标注类别。但本质上还是有巨大的差别的。

引言

在实际工作中，我们常会遇到这样一类问题:给机器输入大量的特征数据，并期望机器通过学习找到数据中存在的某种共性特征或者结构，亦或是数据之间存在的某种关联。例如在推荐系统中的根据用户的行为，对用户进行分组。这类问题被称为”非监督学习”问题。它并不像监督学习那样希望预测出某种输出结果。相比于监督学习，非监督学习的输入数据没有标签信息，需要通过算法模型来挖掘数据内在的结构和模式。非监督学习主要包含两大类学习方法：数据聚类和特征变量关联。其中，聚类算法往往是通过多次迭代找到数据的最优分割，而特征变量关联则是利用各种相关性分析方法来找到变量之间的关系。

K-means 基本算法

简述K-means算法的具体步骤
K-means算法的核心目标是给定的数据集划分成K个簇，并给出每个数据对应的簇中心点。算法具体步骤：
（1）数据预处理,如归一化、离群点处理等
（2）随机选取K个簇中心，记为$\mu_1^{(0)},\mu_2^{(0)},…,\mu_K^{(0)}$
（3）定义代价函数：$J(c,\mu)=min_{\mu}min_{c}\sum_{i=1}^M||x_i-\mu_{c_i}||^2$
（4）令t=0,1,2,…为迭代步数，重复下面过程直到J收敛：

对于每个样本$x_i$，将其分配到距离最近的簇 $c_i^{(t)}\leftarrow argmin_k||x_i-\mu_k^{(t)}||^2$
对于每个类簇k,重新计算该类簇的中心 $\mu_k^{(t+1)}\leftarrow argmin_{\mu}\sum_{i:c_i^{(t)=k}}||x_i-\mu||^2$

K均值算法在迭代时，假设当前J没有达到最小值，那么首先固定簇中心$\{\mu_k\}$,调整每个样例$x_i$所属的类别$c_i$来让J函数减少；然后固定$\{c_i\}$,调整簇中心$\{\mu_k\}$使J减小。这两个过程交替循环，J单调递减:当J递减到最小值时，$\{\mu_k\}$和$\{c_i\}$也同时收敛。

坐标下降法(Coordinate descent)
坐标下降法属于一种 非梯度优化的方法 ，它在每步迭代中沿一个坐标方向进行搜索，通过循环使用不同的坐标方法来达到目标函数的局部极小值。
算法过程：
假设目标函数是求解f(x)的极小值，其中$\vec{x}=(x_1,x_2,…,x_n)$是一个n维的向量，我们从初始点x^0开始(x^0是我们猜想的一个初始值)对k进行循环：

$x_1^{(k)}=arg min_{x_1}f(x_1,x_2^{(k-1)},...,x_n^{(k-1)})$ $x_2^{(k)}=arg min_{x_2}f(x_2^{(k)},x_2,...,x_n^{(k-1)})$

…..

$x_n^{(k)}=arg min_{x_n}f(x_1^{(k)},x_2^{(k)},...,x_n)$

相当于每次迭代都只是更新$\vec{x}$的一个维度，把该维度视为变量，剩下的n-1个维度的值当作常量，最小化f(x),找到该维度对应的新的值。坐标下降法就是通过不断地迭代构造序列$x^0,x^1,…$来求解问题，即最终点收敛到期望的局部最小值点

$f(x^{(0)})＞f(x^{(1)})＞.....$

很显然，K-means这里用到的就是坐标下降法。

在SVM中,我们也有用到坐标下降法，SMO中有出现。

K_means

K-means存在缺点

K-means是 局部最优 的，容易受到初始质心的影响;比如在下图中，因选择初始质心不恰当而造成次优的聚类结果
同时K值得选取也会直接影响聚类结果，最优聚类得K值应与样本数据本身得结构信息相吻合，而这种结构信息很难去掌握，因此选取最优k值是非常困难的

如何选择K值

K值得选择一般基于经验和多次实验结果。可以尝试不同的K值，并将不同K值所对应的损失函数画成折线，横轴为K的取值，纵轴为误差平方和所定义的损失函数。由此可以找到一个最佳点。但是这种方法的缺点就是不够自动化。（手肘法）

Gap Statistic方法：
不需要肉眼判断，而只需要找到最大的Gap Statistic所对应的K即可。因此该方法也适用于批量化作业。在这里我们继续使用上面的损失函数，当分为K簇时，对应的损失函数记为$D_k$。Gap Statistic定义为：

$Gap(K)=E(logD_k)-logD_k$

其中$E(logD_k)$是$log(D_k)$的期望，一般通过蒙特卡洛模拟产生.我们在样本所在的区域内按照均匀分布随机地产生和原始样本数一样多地随机样本，并对这个随机样本做K均值，得到$D_k$；重复多次就可以计算处$E(logD_k)$的近似值。那么Gap(K)的物理意义是什么呢？它们可以视为随机样本的损失与实际样本的损失之差。试想实际样本对应的最佳簇数为K,那么实际样本的损失应该相对较小，从而Gap(K)取得最大值所对应的K值就是最佳的簇数。

K-means++算法

总结一下K-means的缺点
(1)需要人工预先确定初始K值，且该值和真实的数据分布未必吻合
(2)K均值智能收敛到局部最优，效果受到初始值很大影响
(3)易受噪声点影响
(4)样本点只能被划分到单一的类中

K-means++的思路：
假设已经选取了n个初始聚类中心(0＜n＜K),则在选取第n+1个聚类中心时，距离当前n个聚类中心越远的点会有更高的概率被选为第n+1个聚类中心。在选取第1个聚类中心(n=1)时同样通过随机的方法，可以说这也符合我们的直觉，聚类中心当然是互相离得越远越好。当选择完初始点后，K-means++后续的执行和经典K-means算法相同。

ISODATA算法

当K值大小不确定时，可以使用ISODATA算法，ISODATA算法的全称是迭代自组织数据分析法。在K-means算法中，聚类个数K的值需要预先人为确定;并且在整个算法过程中无法更改。而当遇到高纬度、海量的数据集时，人们往往很难准确地估计出K的大小。ISODATA算法就是针对这个问题进行改进的，它的思想也很直观。当属于某个类别的样本数过少时，把该类别去除;当属于某个类别的样本数过多、分散程度较大时，把该类别分为两个子类别。ISODATA算法在K均值算法的基础之上增加了两个操作，一是分裂操作，对应着增加聚类中心数;二是合并操作，对应着减少聚类中心数。ISODATA算法是一个比较常见的算法，其缺点是需要指定的参数比较多，不仅仅需要一个参考的聚类数量$K_0$,还需要制定3个阈值。下面介绍ISODATA算法的各个输入参数。

下面介绍ISODATA算法的各个输入参数
(1)预期的聚类中心个数$K_0$.在ISODATA运行过程中聚类中心可以变化，$K_0$是一个用户指定的参考值，该算法的聚类中心数目变动范围也由其决定。具体地，最终输出的聚类中心数目常见范围是从$K_0$的一半，到两倍$K_0$
(2)每个类所要求的最小样本数目$N_min$。若果分裂后会导致某个子类别所包含样本数目小于该阈值，就不会对该类别进行分裂操作
(3)最大方差Sigma。用于控制某个类别中样本的分散程度，当样本的分散程度超过这个阈值时，且分裂后满足(1),进行分裂操作
(4)每个聚类中心之间所允许最小距离$D_{min}$.如果两个类靠得非常近(即这两个类别对应聚类中心之间的距离非常小)，小于该阈值时，则对这两个类进行合并操作。

坐标下降法(Coordinate Descent,CD)

比较一下梯度下降法(SGD)和坐标下降法(CD)
相同点:
SGD和CD都是优化损失函数的一种方法.都沿着某个方向对参数不断迭代更新,计算量为O(mn),
其中m为特征数目,n为样本数目.

不同点:
SGD是沿着负梯度方向对损失函数进行参数更新（又叫最速下降法）
CD是沿着坐标轴下降方向进行参数更新,这一特点决定了两者应用场景不同.

例:
如果在LR(逻辑回归)算法中加入L1正则项,由于L1正则项是参数值绝对值之和,所以在使用SGD进行参数更新时,会使损失函数中出现不可导的点,所以此时不能再用SGD、牛顿法、拟牛顿法等,应该用CD(坐标下降法)进行参数更新。

CD进行参数更新的思想:每次只变换一个维度$x_i$,其他维度都用该参数当前值$w_{k-1}$进行计算,这样每次都得到一个该维度下的最新值$w_k$,循环迭代计算,直到$w_k$与$w_{k-1}$差别不大时停止迭代。

CD的数学依据是:当一个可微凸函数F(w),在某一坐标轴上的解$w=(w_1,w_2,…,w_n)$都达到最小值时,那么此时$w=(w_1,w_2,…,w_n)$即为F(w)的全局最小值.

另,坐标上升和坐标下降都是一个原理,只不过一个求最大,一个求最小.