【西瓜书】第9章聚类

2019-07-02 本文已影响0人一杭oneline

文章内容主要摘自 https://blog.csdn.net/u011826404/article/details/70991604，吴恩达老师k-means聚类的讲课，并根据自己的理解进行补充完善

聚类算法

聚类是一种经典的无监督学习方法，无监督学习的目标是通过对无标记训练样本的学习，发掘和揭示数据集本身潜在的结构与规律，即不依赖于训练数据集的类标记信息。聚类则是试图将数据集的样本划分为若干个互不相交的类簇，从而每个簇对应一个潜在的类别。

周志华老师对聚类的定位

1.聚类既能作为一个单独的过程，用于寻找数据内的分布结构，也能作为分类等其他学习任务的前驱过程。

2.聚类结果的“簇内相似度”高且簇间相似度低，这个意思就是圈里面的基本一致，两个圈之间关系不是很大。

3.聚类性能大致分为两类，一是有外部参考模型的，叫做“外部指标”；一类是没有参考模型的，靠人来判断的，叫做“内部指标”。

聚类直观上来说是将相似的样本聚在一起，从而形成一个类簇（cluster）。那首先的问题是如何来度量相似性（similarity measure）呢？这便是距离度量，在生活中我们说差别小则相似，对应到多维样本，每个样本可以对应于高维空间中的一个数据点，若它们的距离相近，我们便可以称它们相似。那接着如何来评价聚类结果的好坏呢？这便是性能度量，性能度量为评价聚类结果的好坏提供了一系列有效性指标。

S表示Same D表示different

内部指标

其中，|C|（|C|-1）/2是样本的总数

距离度量

谈及距离度量，最熟悉的莫过于欧式距离了，从年头一直用到年尾的距离计算公式：即对应属性之间相减的平方和再开根号。度量距离还有其它的很多经典方法，通常它们需要满足一些基本性质：

最常用的距离度量方法是“闵可夫斯基距离”（Minkowski distance)：

当p=1时，闵可夫斯基距离即曼哈顿距离（Manhattan distance）：

当p=2时，闵可夫斯基距离即欧氏距离（Euclidean distance）：

我们知道属性分为两种：连续属性和离散属性（有限个取值）。对于连续值的属性，一般都可以被学习器所用，有时会根据具体的情形作相应的预处理，例如：归一化等；而对于离散值的属性，需要作下面进一步的处理：

若属性值之间存在序关系，则可以将其转化为连续值，例如：身高属性“高”“中等”“矮”，可转化为{1, 0.5, 0}。

若属性值之间不存在序关系，则通常将其转化为向量的形式，例如：性别属性“男”“女”，可转化为{（1,0），（0,1）}。onehot独热编码

在进行距离度量时，易知连续属性和存在序关系的离散属性都可以直接参与计算，因为它们都可以反映一种程度，我们称其为“有序属性”；而对于不存在序关系的离散属性，我们称其为：“无序属性”，显然无序属性再使用闵可夫斯基距离就行不通了。

对于无序属性，我们一般采用VDM进行距离的计算，例如：对于离散属性的两个取值a和b，定义：

VDM

u表示u个特征，a表示u=a的，i为第i个簇，k表示样本数

VDM

于是，在计算两个样本之间的距离时，我们可以将闵可夫斯基距离和VDM混合在一起进行计算：

若我们定义的距离计算方法是用来度量相似性，例如下面将要讨论的聚类问题，即距离越小，相似性越大，反之距离越大，相似性越小。

这时距离的度量方法并不一定需要满足前面所说的四个基本性质，这样的方法称为：非度量距离（non-metric distance）。

原型聚类

原型聚类即“基于原型的聚类”（prototype-based clustering），原型表示模板的意思，就是通过参考一个模板向量或模板分布的方式来完成聚类的过程，常见的K-Means便是基于簇中心来实现聚类，混合高斯聚类则是基于簇分布来实现聚类。

K-Means

K-Means的思想十分简单，首先随机指定类中心，根据样本与类中心的远近划分类簇，接着重新计算类中心，迭代直至收敛。但是其中迭代的过程并不是主观地想象得出，事实上，若将样本的类别看做为“隐变量”（latent variable），类中心看作样本的分布参数，这一过程正是通过EM算法的两步走策略而计算出，其根本的目的是为了最小化平方误差函数E：

目标函数

K-Means的算法流程如下所示：

k-means

算法主要是通过初始化聚类中心，计算所有样本距中心的距离，选择距离最小的那个中心作为该样本的簇，再计算这个簇内的样本均值，再以这个均值为中心，计算各样本距这个均值的距离，从而反复进行更新。

吴恩达老师在聚类内容上主要讲解了k-means，补充一些内容：

随机初始化，就是随机找几个点作为簇的中心，在执行算法中，多进行几次初始化，从几次初始化中寻找结果比较好的，避免陷入局部最优解.

学习向量量化（LVQ）

LVQ也是基于原型的聚类算法，与K-Means不同的是，LVQ使用样本真实类标记辅助聚类，首先LVQ根据样本的类标记，从各类中分别随机选出一个样本作为该类簇的原型，从而组成了一个原型特征向量组，接着从样本集中随机挑选一个样本，计算其与原型向量组中每个向量的距离，并选取距离最小的原型向量所在的类簇作为它的划分结果，再与真实类标比较。

若划分结果正确，则对应原型向量向这个样本靠近一些

若划分结果不正确，则对应原型向量向这个样本远离一些

高斯混合聚类

现在可以看出K-Means与LVQ都试图以类中心作为原型指导聚类，高斯混合聚类则采用高斯分布来描述原型。现假设每个类簇中的样本都服从一个多维高斯分布，那么空间中的样本可以看作由k个多维高斯分布混合而成。

对于多维高斯分布，其概率密度函数如下所示：

多元高斯分布

接着定义高斯混合分布为：

高斯混合分布

α称为混合系数，所有 $\alpha$ 的和是1。

（1）先选择一个类簇（高斯分布），

（2）再根据对应高斯分布的密度函数进行采样，

这时候贝叶斯公式又能大展身手了：

此时只需要选择 $P_{m}$ 最大时的类簇并将该样本划分到其中，看到这里很容易发现：这和那个传说中的贝叶斯分类不是神似吗，都是通过贝叶斯公式展开，然后计算类先验概率和类条件概率。但遗憾的是：这里没有真实类标信息，对于类条件概率，并不能像贝叶斯分类那样通过最大似然法美好地计算出来，因为这里的样本可能属于所有的类簇，这里的似然函数变为：

可以看出：简单的最大似然法根本无法求出所有的参数，这样PM也就没法计算。这里就要召唤出之前的EM大法，首先对高斯分布的参数及混合系数进行随机初始化，计算出各个PM（即γji，第i个样本属于j类），再最大化似然函数（即LL（D）分别对α、u和∑求偏导），对参数进行迭代更新。

对LL（D）求偏导：

解ui的

由：

得出：

对协方差求偏导：

注：例如x是变量，μ是均值，协方差矩阵等于E[(x-μ)(x-μ)^t]，物理意义是这样的，例如x=(x1,x2,,xi)那么协方差矩阵的第m行n列的数为xm与xn的协方差，若m=n，则是xn的方差。如果x的元素之间是独立的，那么协方差矩阵只有对角线是有值，因为x独立的话对于m≠n的情况xm与xn的协方差为0。

其中：