0%

聚类

Posted on Edited on

聚类

定义

把数据集分成若干个互不相交的簇(一坨数据集)，使簇间相似度尽量的小，簇内相似度尽量的大

性能度量

外部指标

  • 将聚类结果和某个参考模型进行比较

与外部模型的比较

假设样本在聚类中是ai，在模型中是bi

$a=|SS|，SS+{(i,j)|a_i=a_j,b_i=b_j,i<j}$

$b=|SD|，SS+{(i,j)|a_i=a_j,b_i!=b_j,i<j}$

$c=|DS|，SS+{(i,j)|a_i!=a_j,b_i=b_j,i<j}$

$d=|DD|，SS+{(i,j)|a_i!=a_j,b_i!=b_j,i<j}$

指标

Jaccard系数

$JC=\frac{a}{a+b+c}$

FM指数

$FMI=\sqrt{\frac{a}{a+b}\frac{a}{a+c}}$

Rand指数

$RI=\frac{2(a+d)}{m(m-1)}$

上述指标都是越大越好

内部指标

  • 不使用参考模型将聚类结果进行比较

内部比较

$avg(C)=\frac{2}{|C|(|C|-1)}\sum_{1<=i<j<=|C|}dist(i,j)$

$diam(C)=max_{1<=i<j<=|C|}dist(i,j)$

$d_{min}(C_i,C_j)=min_{x\in C_i,y\in C_j}dist(i,j)$

$d_{cen}(C_i,C_j)=dist(\mu_i,\mu_j)$

$\mu$是簇的中心点

指数

DB指数，简称DBI

$$DBI=\frac{1}{k}sum_{i=1}^kmax_{j!=i}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(\mu_i,\mu_j)})$$

Dunn指数，简称DI

$DI=\min_{1<=i<=k}(min_{j!=i}(\frac{d_{min}(C_i,C_j)}{max_{1<=l<=k}diam(C_l)}))$

DBI越小越好，DI越大越好

距离度量

对于有序属性—连续值

各种距离

对于无序属性—离散值

VDM(Value Difference Metric)

  • $m_{u,a}$表示在属性u上取值为a的样本数
  • $m_{u,a,i}$表示在第i个样本簇中在属性u上取值为a 的样本数
  • k为簇数

则属性u上两个离散值a与b之间的VDM距离为

$$VDM_{p(a,b)}=\sum_{i=1}^k|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}|^p$$

上面的两者结合可以处理混合属性

原型聚类

  • 基于原型的聚类方法，假设聚类结构能通过一组原型进行刻画。
  • 算法先对原型进行初始化，然后不断的迭代更新……

k-均值聚类

  • 目的是最小化平方误差

$$
E=\sum_{i=1}^k\sum_{x\in C_i}|x-\mu_i|^2
$$

$\mu_i$是簇i的均值向量

由于这是一个NP难问题，所以我们用贪心的方式解决

  • 1、随机初始化均值向量
    • 2、根据均值向量分类
    • 3、重新分配每个样本所属哪个簇
    • 4、更新均值向量
    • 5、重复上面的三个过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def kMeansCluster(self):
    dataSet = self.dataSet
    K = self.K
    bz = 1; n, m = dataSet.shape
    self.dataBe = mat(zeros((n,1)))
    while bz:
        bz = 0
        for i in range(n):
            minn, minx = self.findMin(dataSet[i])
            if (minx != self.dataBe[i]): bz = 1
            self.dataBe[i] = minx
        for i in range(K):
            datK = dataSet[nonzero(self.dataBe[:, 0] == i)[0]]
            if (datK.shape[0] == 0): continue
            self.cen[i, :] = mean(datK, axis=0)
    for i in range(K):
        labK = []
        for j in range(n):
            if (self.dataBe[j, 0] == i): labK.append(self.labelSet[j])
        self.cenbz.append(self.majority(labK))

学习向量量化(LVQ)

  • 与k-均值分类的原理类似，也是最小化平方误差，但是它是已知各个样本的标签的。

  • 假设每个样本的特征是向量x，标记是y，$y \in Y$，簇的个数是q

  • 目标：我们试图对每个簇搞出一个向量，向量的长度与特征数是一样的，同时也有一个簇标记t

流程

  • 1、初始化每个向量的类别标记，$t_{1..q}$，和每个向量的值，还有学习率$\eta$
  • 2、直到满足条件则停止(收敛,更新到小于阈值)
    • 1、从样本中随机选取一些样本
    • 2、计算这些样本与每个簇向量的距离
    • 3、找出对于每个样本x最近的簇向量i
      • a、假如样本x的标签和簇向量i的标签是一样的—–>则我们希望他们更近
      • b、假如样本x的标签和簇向量i的标签不一样—->则我们希望他们更远
      • 更远和更近:向量$p=p±\eta(x-p)$

高斯混合聚类

定义

就是有很多个高斯分布搞在一起，然后要把他划分出来

例：假如有一组升高数据，不知道性别，然后拿一个数据出来问你性别的概率

答：假设是由两个高斯分布混合在一起的，高斯混合聚类可解

一维高斯分布到n维的高斯分布

一维：
$$
一维f(x)=\frac{1}{\sqrt{2\pi}\delta}e^{-\frac{(x-\mu)^2}{2\delta^2}}=
$$

$上面的x$~$N(\mu,\delta^2)$

多维：

$$
n维f(x)=\frac{1}{(2\pi)^{\frac{n}{2}}|\sum|^{1\over 2}}e^{-{1\over 2}(x-\mu)^{T}\sum^{-1}(x-\mu)}
$$

$上面x$~$N(\mu,\sum)$，$\sum表示协方差矩阵,|\sum|表示行列式，\sum^{-1}表示逆矩阵，x是一个向量，上诉得到一个向量$

$一维的\delta—->n维的\sum^{1\over 2}$

  • 高维就是把方差(一维相关性)转化成协方差矩阵(多维相关性)，所以我们只用考虑一维如何求解就能推到到多维

显然，我们假设已经知道了一个概率模型，我们需要知道系数—–>极大似然估计

  • 不过问题是，我们在对数似然估计后的求导难以求出解，因为它会有一些不知道的变量——>EM算法

EM算法

思想来源

概率模型中有

  • 观测变量：就是已经知道的数据 //如果只有这种数据的时候，我们可以直接进行极大似然估计(求导、梯度下降、牛顿迭代……)或者直接套用贝叶斯分析模型
  • 隐变量或潜在变量：比如你自己建立了一个概率模型，然后会引入一下未知量。在聚类学习中就会引入，这个时候我们就不能直接用上面的方法了
  • 综上所述：EM算法就是在有隐变量的情况下做极大似然估计
一般流程

  • (1) 得到数据：观测变量数据Y，隐变量数据Z，联合概率$P(Y,Z|\theta)$，条件概率$P(Y|Z,\theta)$

  • (2) 得到参数的初始值，模型$\theta^0$的各种值

  • (3) 开始迭代，对i+1时

    • E步：根据第i步的各个参数，得到Q函数：$Q(\theta,\theta^i)$，Q函数就是对极大对数似然函数的期望期望最大化函数

    $$
    Q(\theta,\theta^i)=E_z(logP(Y,Z|\theta)|Y,\theta^i)
    $$

    $$
    =\sum_Z(logP(Y,Z|\theta)P(Z|Y,\theta^i))
    $$

    • M步：极大化Q函数
    • 在给定观测数据Y和当前参数$\theta^i$下对未观测数据Z的条件概率分布的期望称为Q函数

    $$
    \theta^{i+1}=argmax_{\theta}(Q(\theta,\theta^i))
    $$

  • 重复上两步直到收敛，判断收敛条件$|Q(\theta^{i+1},\theta^i)-Q(\theta^i,\theta^i)|<\varepsilon$

    所以，每次迭代的目的相当于不断的极值化Q函数

EM算法的导出

$$
L(\theta)=log(\sum_{Z}P(Y|Z,\theta)P(Z|\theta))
$$

  • 我们注意到求这个极大化的困难就是数据中有隐变量并有包含和(积分)的对数

实际上，我们的EM算法是通过迭代逐步近似极大化的$L(\theta)$，所以每次迭代的时候我们希望$L(\theta)>L(\theta^i)$

我们考虑对他做差
$$
L(\theta)-L(\theta^i)=log(\sum_ZP(Y|Z,\theta^i)\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Y|Z,\theta^i)})-logP(Y|\theta^i)
$$

$$
=log(\sum_ZP(Y|Z,\theta^i)\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Y|Z,\theta^i)P(Y|\theta^i)})
$$
根据Jensen不等式$log(\sum aibi)>=\sum ailog(bi)，其中ai>=0且\sum ai =1$

因为$\sum_Z P(Y|Z,\theta^i)=1$

所以
$$
=\sum_ZP(Y|Z,\theta^i)log(\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Y|Z,\theta^i)P(Y|\theta^i)})
$$

$$
设B(\theta,\theta^i)近似于L(\theta^i)+\sum_ZP(Y|Z,\theta^i)log(\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Y|Z,\theta^i)P(Y|\theta^i)})
$$
我们并不用求确切的差值，只用满足$L(\theta)≥B(\theta,\theta^i)$，找到这个下界即可

有上式可知$L(\theta^i)=B(\theta^i,\theta^i)$

因此，任何能使B函数增大的$\theta$都能使$L(\theta)$增大，所以我们要求
$$
\theta^{i+1}=argmax_{\theta}B(\theta,\theta^i)
$$

$$
= argmax_{\theta}(L(\theta^i)+\sum_ZP(Y|Z,\theta^i)log(\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Y|Z,\theta^i)P(Y|\theta^i)}))
$$
由于$\theta^i$是常量，我们可以省去一部分常量
$$
= argmax_{\theta}(\sum_ZP(Y|Z,\theta^i)log(P(Y|Z,\theta)P(Z|\theta))
$$

$$
= argmax_{\theta}(\sum_ZP(Y|Z,\theta^i)log(P(Y,Z|\theta))
$$

$$
= argmax_{\theta}Q(\theta,\theta^i)
$$

  • 上面几行的推导最后又饶了回来，目的是证明，我们极大化Q函数的方法是不断的求解下界来逼近的，并保证每次迭代的时候是单调增长的(假如没有隐函数，我们直接通过求导在函数上逼近，而现在我们不断确定下界逼近)
EM算法在非监督学习上的应用
  • 监督学习对每个样本X是有分类的Y，而非监督学习是没有分类的
  • 然而虽然非监督学习没有分类，但是模型还是联合概率$P(X,Y)$
  • X是观测数据，Y是未观测数据(隐变量)

EM算法在高斯混合模型上的应用

一维的高斯混合分模型如下
$$
P(x|\theta)=\sum_{k=1}^K\alpha_k\phi(x|\theta_k)
$$

$$
\phi(x|\theta_k)=\frac{1}{\sqrt{2\pi}\delta_k}e^{-\frac{(x-\mu_k)^2}{2\delta_k^2}}
$$

K是簇的个数,$\phi_k$是第k个簇的高斯分布模型，$\alpha_k$(≥0)是第k个簇的系数满足$\sum \alpha=1$，就是划分系数

一、明确隐变量，写出完全数据的对数似然函数

我们现在有k个簇，那么就有k个标签了

由于我们不知道每个样本属于哪个标签，所以我们定义$g_{ik}表示第i个样本属于第k个簇的概率$，g不是0就是1，且$\sum_{k=1}^Kg_{ik}=1$

那么现在的概率模型为,一下的$g_{ik}$的定义为是0还是1，这样就能作为次幂乘起来
$$
P(X,g|\theta)=\prod_{i=1}^nP(g_{i1},g_{i2},…,g_{iK}|\theta)
$$

$$
=\prod_{i=1}^n\prod_{k=1}^K[\alpha_k\phi(x_i|\theta_k)]^{g_{ik}}
$$

$$
=\prod_{k=1}^K\alpha_k^{n_k}\prod_{i=1}^n[\frac{1}{\sqrt{2\pi}\delta_k}e^{-\frac{(x_i-\mu_k)^2}{2\delta_k^2}}]
$$

所以完全数的对数似然函数为
$$
log(X,g|\theta)=\sum_{k=1}^Kn_klog\alpha_k+\sum_{i=1}^ng_{ik}[log(\frac{1}{\sqrt{2\pi}})-log\delta_k-\frac{(x_i-\mu_k)^2}{2\delta_k^2}]
$$

$$
n_k=\sum_{i=1}^ng_{ik}，\sum_{k=1}^Kn_k=N(这里就是每个样本只有一个地方是1)
$$

二、EM算法的E步：确实Q函数

$$
Q(\theta,\theta^i)=E(logP(X,G|\theta)|X,\theta^i)
$$
把期望函数带入和隐函数相关的变量中
$$
log(X,g|\theta)=\sum_{k=1}^K(\sum_{i=1}^n(Eg_{ik})log\alpha_k+\sum_{i=1}^n(Eg_{ik})[log(\frac{1}{\sqrt{2\pi}})-log\delta_k-\frac{(x_i-\mu_k)^2}{2\delta_k^2}])
$$
由于现在g的值还没有确定，所以我们要确定了g的值才能确定g函数

  • 由上式g的函数被转化成g的期望
    $$
    \hat g_{ik}=E(g_{ik}|X,\theta)=P(g_{ik}=1|X,\theta)
    $$

$$
=\frac{P(g_{ik}=1,x_i|\theta)}{\sum_{k=1}^KP(g_{ik},x_i|\theta)}
$$
上下同时乘$P(g_{ik}=1|\theta)$，转化乘联合概率$P(X,g|\theta)$（完全数据的概率）
$$
=\frac{P(g_{ik}=1,x_i|\theta)P(g_{ik}=1|\theta)}{\sum_{k=1}^KP(g_{ik},x_i|\theta)P(g_{ik}=1|\theta)}
$$

$$
=\frac{\alpha_k\phi(x_i|\theta_k)}{\sum_{k=1}^K\alpha_k\phi(x_i|\theta_k)}
$$
我们通过对g的期望计算g，然后确定出Q函数

  • EM算法在确定Q函数的时候大致如此，用隐函数的最大期望来得到
三、EM算法的M步：极大化Q函数

我们在确定出Q函数的时候，就能求极值了，如果不能直接求极值,可以用梯度下降或牛顿迭代来求

对于每个变量偏导使其等于0

高斯分布一维的情况
$$
\mu_knew=\frac{\sum_{i=1}^n\hat g_{ik}x_i}{\sum_{i=1}^n\hat g_{ik}}
$$

$$
\delta^2_knew=\frac{\sum_{i=1}^n\hat g_{jk}(x_i-\mu_k new)^2}{\sum_{i=1}^n\hat g_{ik}}
$$
$\alpha$是用拉格朗日乘数法推出来的
$$
\alpha_k new=\frac{n_k}{n}=\frac{\sum_{i=1}^ng_{ik}}{n}
$$

重复以上步骤直到收敛

收敛条件，由于Q的值与$\alpha$有关系，当$\alpha$的变化小于阈值时，则收敛

PCA降维

要分散

  • 对于一组二维的数据点，我们要投影到一维的话，那么最后的方式就是找到一条直线，使得这些点在直线上的投影尽量的分散。
  • 而要分散，就是可以数值化为方差尽量的大

协方差矩阵

  • 协方差所表示的是两个向量的同步程度。

  • 而协方差矩阵也有类似的作用。协方差矩阵的所表示的超空间的凸起的地方就是最同步的地方，而我们沿着折最同步的地方垂直分解就能造成所谓的尽量的离散。

矩阵的特征向量

  • 特征向量的性质就是，特征向量一直点乘矩阵，最后总是在特征向量的方向做变换。
  • 意义上就相当于这个矩阵所表示的坐标系的最伸长的地方，特征值就相当于这个度

步骤

  • 1、求解所有数据的协方差矩阵
  • 2、然后根据这个协方差矩阵求解他们的特征向量和特征值
  • 3、然后根据得到的特征值从大到小排序，将排序后的特征向量拼接成一个转移矩阵
  • 4、然后整个数据点乘这个转移矩阵，得到投影后的矩阵
  • 5、计算最适宜的分解维度，计算每一维的总方差，然后如果前k维的总方差大于一个阈值threshVal 的话，那么这个k就是最适宜分解的维度，一般threshVal可以设置在0.9左右