聚类算法Kmeans与梯度算法Meanshift

Kmeans 与 Meanshift、 EM 算法的关系 Kmeans 算法是一种经典的聚类算法，在模式识别中得到了广泛的应用，基于Kmeans 的变种算法也有很多，模糊Kmeans、分层Kmeans 等。 Kmeans 和应用于混合高斯模型的受限EM 算法是一致的。高斯混合模型广泛用于数据挖掘、模式识别、机器学习、统计分析。Kmeans 的迭代步骤可以看成E 步和M 步，E：固定参数类别中心向量重新标记样本，M：固定标记样本调整类别中心向量。K 均值只考虑（估计）了均值，而没有估计类别的方差，所以聚类的结构比较适合于特征协方差相等的类别。 Kmeans 在某种程度也可以看成Meanshitf 的特殊版本，Meanshift 是一种概率密度梯度估计方法（优点：无需求解出具体的概率密度，直接求解概率密度梯度。），所以Meanshift 可以用于寻找数据的多个模态（类别），利用的是梯度上升法。在06 年的一篇CVPR 文章上，证明了Meanshift 方法是牛顿拉夫逊算法的变种。Kmeans 和 EM 算法相似是指混合密度的形式已知（参数形式已知）情况下，利用迭代方法，在参数空间中搜索解。而Kmeans 和 Meanshift 相似是指都是一种概率密度梯度估计的方法，不过是Kmean选用的是特殊的核函数（uniform kernel），而与混合概率密度形式是否已知无关，是一种梯度求解方式。PS： 两种Kmeans 的计算方法是不同的。 Vector quantization 也称矢量量化:指一个向量用一个符号K 来代替。比如有10000 个数据，用 Kmeans聚成100 类即最有表征数据意义的向量，使得数据得到了压缩，以后加入的数据都是用数据的类别来表示存储，节约了空间，这是有损数据压缩。数据压缩是数据聚类的一个重要应用，也是数据挖掘的主要方法。 混 合高斯模型是一系列不同的高斯模型分量的线性组合。在最大似然函数求极值时，直接求导存在奇异点的问题，即有时一个分量只有一个样本点，无法估计其协方 差，导致其似然函数趋于无穷，无法求解。另一个问题是，用代数法求得的解是不闭合的，即求解的参数依赖于参数本身的值，变成一个鸡生蛋，蛋生鸡的问题。这 些问题看似无解，但是可以使用迭代的方法如EM， k 均值等，预先设置一些参数，然后迭代求解。PS： 也有用基于梯度的方法求解的。在求解混合模型时，有一个重要的概念即模型的可辨识性（如果无论样本的数量为多少都无法求出模型参数的唯一解，则称模型是不可辨识的）， 这是EM 算法的前提。在实际应用时，由于EM 算法的复杂度比K 均值高，所...