聚类浅谈

聚类允许有损压缩，因而有助于通信。生物学家能这样为一个朋友指路：“走到右边的第三棵树，然后向右转”（而不是说“经过有红色浆果的大的绿东西，然后经过有荆棘的大的绿东西，然后。。。”）。显然，类名称“树“是有用的。同样地，在有损图像压缩中，目标是用尽可能少的传输比特来合理地再现图像；完成这一任务的一种方法是把图像分成N个小片，并对每个小片在K个图像模板快组成的符号表中寻找一个最接近的匹配；然后通过发送一列匹配模板的标记$k_{1},k_{2},...,k_{N}$，发送与图像最接近的匹配。构建一个好的图像模板库的任务就等价于选择一组聚类中心。这种类型的聚类被叫做“矢量量化”（vector quantification）。

矢量量化器

分配规则 $x\rightarrow k(x)$把数据点$x$分配给$K$个代码名之一，重构规则$k\rightarrow m^{(k)}$的目标是选择函数$k(x)$和$m^{(k)}$已使期望失真最小化

$D=\sum_{x}P(x)\frac{1}{2}[m^{(k)}-x]^{2}$

在矢量量化中，不必认为模板$m^{(k)}$有任何自然意义，它们只是完成任务的工具。注意将矢量量化的分配规则（编码器）的相似性传递到对一个纠错码进行译码时的译码问题。

 Clustering Algorithms分类

1. Partitioning approach:
建立数据的不同分割，然后用相同标准评价聚类结果。（比如最小化平方误差和）
典型算法：K-Means, K-Medoids

2. Model-based:
对于每个类假定一个分布模型，试图找到每个类最好的模型
典型算法：GMM（混合高斯）

3. Dimensionality Reduction Approach:
先降维，再聚类
典型算法：Spectral clustering，Ncut

参考资料：

1）http://blog.csdn.net/abcjennifer/article/details/8170687

EM相关

2）http://blog.csdn.net/abcjennifer/article/details/8198352

3）http://blog.csdn.net/abcjennifer/article/details/8170378

4）http://www.cnblogs.com/jerrylead/archive/2011/04/06/2006936.html