聚类

1.在无监督学习(unsupervised learning)中，训练样本的标记信息是未知的。

2.无监督学习的目标：通过对无标记训练样本的学习来揭露数据的内在性质以及规律。

3.一个经典的无监督学习任务：寻找数据的最佳表达(representation)。常见的有：

        低维表达：试图将数据（位于高维空间）中的信息尽可能压缩在一个较低维空间中。

        稀疏表达：将数据嵌入到大多数项为零的一个表达中。该策略通常需要进行维度扩张。

        独立表达：使数据的各个特征相互独立。

4.无监督学习应用最广的是聚类(clustering) 。

5.聚类的作用：

        可以作为一个单独的过程，用于寻找数据内在的分布结构。

        也可以作为其他学习任务的前驱过程。如对数据先进行聚类，然后对每个簇单独训练模型。

6.聚类问题本身是病态的。即：没有某个标准来衡量聚类的效果。

        可以简单的度量聚类的性质，如每个聚类的元素到该类中心点的平均距离。

        但是实际上不知道这个平均距离对应于真实世界的物理意义。

        可能很多不同的聚类都很好地对应了现实世界的某些属性，它们都是合理的。

        如：在图片识别中包含的图片有：红色卡车、红色汽车、灰色卡车、灰色汽车。可以聚类成：红色一类、灰色一类；也可以聚类成：卡车一类、汽车一类。

---

原型聚类

        原型聚类prototype-based clustering假设聚类结构能通过一组原型刻画。

        常用的原型聚类有：

                1.k均值算法k-means。

                2.学习向量量化算法Learning Vector Quantization:LVQ。

                3.高斯混合聚类Mixture-of-Gaussian。

密度聚类

    1.密度聚类density-based clustering假设聚类结构能够通过样本分布的紧密程度确定。

    2.密度聚类算法从样本的密度的角度来考察样本之间的可连接性，并基于可连接样本的不断扩张聚类簇，从而获得最终的聚类结果。

层次聚类

    层次聚类hierarchical clustering 试图在不同层次上对数据集进行划分，从而形成树形的聚类结构。

---

k-means 算法

定义

1.    给定样本集，假设一个划分为。

        定义该划分的平方误差为： 

                                

        其中是簇的均值向量。

        err刻画了簇类样本围绕簇均值向量的紧密程度，其值越小，则簇内样本相似度越高

        k-means 算法的优化目标为：最小化 err

2.k-means 的优化目标需要考察D的所有可能的划分，这是一个NP难的问题。实际上k-means 采用贪心策略，通过迭代优化来近似求解。

        首先假设一组均值向量。

        然后根据假设的均值向量给出了D的一个划分。

        再根据这个划分来计算真实的均值向量：

        如果真实的均值向量等于假设的均值向量，则说明假设正确。根据假设均值向量给出的D一个划分确实是原问题的解。

        如果真实的均值向量不等于假设的均值向量，则可以将真实的均值向量作为新的假设均值向量，继续迭代求解。

3.这里的一个关键就是：给定一组假设的均值向量，如何计算出  的一个簇划分？

        k均值算法的策略是：样本离哪个簇的均值向量最近，则该样本就划归到那个簇

优点

        1.计算复杂度低，为O(N*K*q)  ，其中q为迭代次数。

            通常 K和q要远远小于 N，此时复杂度相当于O(N) 。

        2.思想简单，容易实现。

缺点

        1.需要首先确定聚类的数量 K 。

        2.分类结果严重依赖于分类中心的初始化。

        3.通常进行多次k-means，然后选择最优的那次作为最终聚类结果。

        4.结果不一定是全局最优的，只能保证局部最优。

        5.对噪声敏感。因为簇的中心是取平均，因此聚类簇很远地方的噪音会导致簇的中心点偏移。

        6.无法解决不规则形状的聚类。

        7.无法处理离散特征，如：国籍、性别 等。

性质

        1. k-means 实际上假设数据是呈现球形分布，实际任务中很少有这种情况。

        2.与之相比，GMM 使用更加一般的数据表示，即高斯分布。

        3.k-means 假设各个簇的先验概率相同，但是各个簇的数据量可能不均匀。

        4.k-means 使用欧式距离来衡量样本与各个簇的相似度。这种距离实际上假设数据的各个维度对于相似度的作用是相同的。

        5.k-means 中，各个样本点只属于与其相似度最高的那个簇，这实际上是硬分簇。

---

sklearn中的k-means

1.随机创建一些二维数据作为训练集，选择二维特征数据，主要是方便可视化

2.分别分为2，3，4簇的，查看聚类效果