【ML算法学习】核K均值聚类Kernel K-Means Clustering（KKMC）

核K均值聚类Kernel K-Means Clustering（KKMC）

1. 理论基础回顾

（1）核函数定义（统计学习方法定义7.6）

• 定义内容：假设有输入空间$\mathcal{X}$（$\mathcal{X}\in R^n$）和特征空间$\mathcal{H}$（希尔伯特空间），若存在一个从$\mathcal{X}$到$\mathcal{H}$的映射$\varphi (x):\mathcal{X}\to \mathcal{H}$，使得对所有样本$x,z\in \mathcal{X}$，有函数$K(x,z)$满足条件$K(x,z)=\varphi (x)\cdot \varphi (z)$（内积），则称$K(x,z)$为核函数，$\varphi (x)$为映射函数。

• 核技巧思路：在学习和预测中只定义核函数$K(x,z)$，而不显式地定义映射函数$\varphi (\cdot )$，因为通常直接计算$K(x,z)$比较容易，而由$\varphi (x)$和$\varphi (z)$来计算$K(x,z)$比较困难（$\varphi (\cdot )$是输入空间$\mathcal{X}$到特征空间$\mathcal{H}$的映射，特征空间一般是高维甚至无穷维的）。此外，对于给定的核函数$K(x,z)$，特征空间$\mathcal{H}$和映射函数$\varphi (\cdot )$的取法不唯一，即便是在同一特征空间内也能取不同的映射。

• 例：假设输入空间$\mathcal{X}\in R^2$，核函数为$K(x,z)=(x\cdot z{)}^2$，试找出其相关的特征空间$\mathcal{H}$和映射$\varphi (\cdot ):R^2\to \mathcal{H}$。

  • 法1：取特征空间$\mathcal{H}=R^3$，记$x={\left(x^{(1)},x^{(2)}\right)}^{\mathrm{T}}$， $z={\left(z^{(1)},z^{(2)}\right)}^{\mathrm{T}}$，核函数为
    $$(x\cdot z{)}^2={\left(x^{(1)}{z}^{(1)}+x^{(2)}{z}^{(2)}\right)}^2={\left(x^{(1)}{z}^{(1)}\right)}^2+2x^{(1)}{z}^{(1)}{x}^{(2)}{z}^{(2)}+{\left(x^{(2)}{z}^{(2)}\right)}^2$$

    所以可以取映射$\varphi (x)={\left({\left(x^{(1)}\right)}^2,\sqrt{2}{x}^{(1)}{x}^{(2)},{\left(x^{(2)}\right)}^2\right)}^{\mathrm{T}}$，易验证$\varphi (x)\cdot \varphi (z)=(x\cdot z{)}^2=K(x,z)$。

  • 法2：取$\mathcal{H}=R^3$以及$\varphi (x)=\frac{1}{\sqrt{2}}{\left({\left(x^{(1)}\right)}^2-{\left(x^{(2)}\right)}^2,2x^{(1)}{x}^{(2)},{\left(x^{(1)}\right)}^2+{\left(x^{(2)}\right)}^2\right)}^{\mathrm{T}}$同样满足条件。

  • 法3：取$\mathcal{H}=R^4$以及$\varphi (x)={\left({\left(x^{(1)}\right)}^2,x^{(1)}{x}^{(2)},x^{(1)}{x}^{(2)},{\left(x^{(2)}\right)}^2\right)}^T$满足条件。

• 通俗理解：核方法将数据映射到更高维的空间，希望在这个更高维的空间中，数据可以变得更容易分离或更好的结构化。

（2）期望最大算法（Expectation Maximization Algorithm）

• EM 算法是一种迭代算法，用于含有隐变量（Hidden Variable）的概率参数模型的最大似然估计或极大后验概率估计。其核心思想非常简单，分为两步：Expection-Step（期望步长）和 Maximization-Step（最大化步长）。

  • E-Step 主要通过观察数据和现有模型来估计参数，然后用这个估计的参数值来计算似然函数的期望值；
  • M-Step 是寻找似然函数最大化时对应的参数。

  由于算法会保证在每次迭代之后似然函数都会增加，所以函数最终会收敛。

• 数学推导过程：

  1. 给定数据集，假设样本间相互独立，我们想要拟合模型$p\left(x;\theta \right)$的参数，根据分布可以得到如下似然函数：
     1. 第一步是对极大似然函数取对数；
     2. 第二步是对每个样本的每个可能的类别 $z$求联合概率分布之和。(如果这个 z 是已知的数，那么使用极大似然法会很容易。但如果 z 是隐变量，我们就需要用 EM 算法来求。)

  $$\begin{array}{rl}L(\theta )& =\sum _{i=1}^n\log p\left(x_i;\theta \right)\\ & =\sum _{i=1}^n\log \sum _{z}p\left(x_i,z;\theta \right)\end{array}$$

  2. 对于每一个样本$i$，我们用$Q_i(z)$表示样本$i$隐含变量$z$的某种分布，且$Q_i(z)$满足（${\sum }_z^Z{Q}_i(z)=1,Q_i(z)\ge 0$）。则上式可写为：
     $$\begin{array}{rl}\sum _i^n\log p\left(x_i;\theta \right)& =\sum _i^n\log \sum _{z}p\left(x_i,z;\theta \right)\\ & =\sum _i^n\log \sum _z^Z{Q}_i(z)\frac{p\left(x_i,z;\theta \right)}{Q_i(z)}\\ & \ge \sum _i^n\sum _z^Z{Q}_i(z)\log \frac{p\left(x_i,z;\theta \right)}{Q_i(z)}\end{array}$$
     上面式子中，第一步是求和每个样本的所有可能的类别 z 的联合概率密度函数，但是这一步直接求导非常困难，所以将其分子分母同乘以函数$Q_i(z)$ ，转换到第二步。从第二步到第三步是利用 Jensen 不等式。

  3. 通过上述推导，得到关于$L(\theta )$的不等式关系，通过不断提高不等式的右侧，就可以使得$L(\theta )$不断提高，达到最大化对数似然函数的目的。

（3）K均值聚类算法

• 输入：包含n个样本的数据集合，聚类形成的簇的个数k。

• 算法步骤：

  1. 选择初始化的k个样本，作为初始聚类中心$a=a_1,a_2,\dots a_k$；
  2. 针对数据集中每个样本$x_i$，计算它到 k 个聚类中心的距离，并将其分到距离最小的聚类中心所对应的类中；
  3. 重新计算聚类中心$a_j=\frac{1}{|c_j|}{\sum }_{x\in c_j}x$（$c_j$为第$j$类样本数），即将每个类别中所有样本的均值作为新的中心；
  4. 重复上述步骤2和3，直到达到某个中止条件（迭代次数、最小误差变化等）。

• 数学过程：

  1. 首先确定损失函数为：$J={\sum }_{i=1}^C{\sum }_{j=1}^N{r}_{ij}\cdot \nu \left(x_j,{\mu }_i\right)$，其中$\nu \left(x_j,{\mu }_i\right)={\Vert x_j-{\mu }_i\Vert }^2$表示样本到各聚类中心的距离，$r_{nk}=\{\begin{array}{ll}1& \text{ if }{x}_n\in k\\ 0& \text{ else }\end{array}$用于筛选样本到最近聚类中心的距离。

  2. 为了使得损失函数达到极小值，对损失函数求偏导数且等于 0，即$\frac{\partial J}{\partial {\mu }_k}=2{\sum }_{i=1}^N{r}_{ik}\left(x_i-{\mu }_k\right)=0$，更新所有聚类中心${\mu }_k=\frac{{\sum }_{i=1}^N{r}_{ik}{x}_i}{{\sum }_{i=1}^N{r}_{ik}}$。

  3. 再对所有样本计算到各聚类中心的距离以更新参数$r_{nk}$。

  4. 重复上述过程即可得到所有类别的中心（K-means 聚类的迭代算法实际上是 EM 算法）。

2. Kernel K-Means Clustering

（1）使用背景

• 基于欧式距离的 K-means 假设了各个数据簇的数据具有一样的的先验概率并呈现球形分布，但这种分布在实际生活中并不常见。
• 面对非凸的数据分布形状时，可以引入核函数来优化，这时算法又称为核 K-means 算法，是核聚类方法的一种。
• 核聚类方法的主要思想是通过一个非线性映射，将输入空间中的数据点映射到高位的特征空间中，并在新的特征空间中进行聚类。非线性映射增加了数据点线性可分的概率，从而在经典的聚类算法失效的情况下，通过引入核函数可以达到更为准确的聚类结果。

（2）模型

• 现有输入空间$\mathcal{X}$为$\left\{x^1,x^2,x^3,\cdots ,x^M\right\}$（$x^i\in R^n$，$i=1,2,\cdots ,M$），假设依据Mercer定理存在一个从$\mathcal{X}$到特征空间$\mathcal{H}$的映射$\varphi (x):\mathcal{X}\to \mathcal{H}$，使得核函数$K(x^i,x^j)=\varphi (x^i)\cdot \varphi (x^j)$。KKMC就是讨论特征空间$\mathcal{H}$里数据集$\left\{\varphi (x^1),\varphi (x^2),\varphi (x^3),\cdots ,\varphi (x^M)\right\}$的聚类情况。

• 与上述理论类似地有损失：
  $$\begin{gathered} J=\sum _{i=1}^M\sum _{k=1}^K{r}_{ik}\cdot {\Vert \varphi (x^i)-{\mu }_k\Vert }^2 \\ {r}_{ik}=\{\begin{array}{ll}1& \text{ if }{x}_i\in kclass\\ 0& \text{ else }\end{array} \end{gathered}$$

（3）算法

• 初始化：$a_{ik}\ge 0,(i=1,2,\cdots ,M),(k=1,2,\cdots ,K)$，其中对于所有类别$k$都有${\sum }_{i=1}^M{a}_{ik}=1$，计算初始聚类中心：
  $${\mu }_k=\sum _{i=1}^M{a}_{ik}\varphi \left(x^i\right),k=1,2,\cdots ,K$$

• Expection-Step：

  • 计算$r_{ik}$:
    $${\bar{\gamma }}_{ik}=\{\begin{array}{lc}1& k=={\mathrm{argmin}}_j\Vert \varphi \left(x^i\right)-{\mu }_j{\Vert }^2\\ 0& \text{ otherwise }\end{array}$$

  • 其中对映射$\varphi (\cdot )$的计算可以转化为对核函数$K(x^i,x^j)$的计算，具体过程如下：
    $$\begin{array}{rl}\Vert \varphi \left(x^i\right)-{\mu }_j{\Vert }^2& ={\Vert \varphi \left(x^i\right)-\sum _{n=1}^M{a}_{nj}\varphi \left(x^n\right)\Vert }^2\\ & =K\left(x^i,x^i\right)-2\sum _{n=1}^M{a}_{nj}K\left(x^i,x^n\right)+\sum _{m,n=1}^M{a}_{mj}{a}_{nj}K\left(x^m,x^n\right)\\ & ,(j=1,2,\cdots ,K)\end{array}$$

• Maximization-Step:

  固定$r_{ik}$，计算$a_{ik}$：
  $$\begin{array}{c}\frac{\partial J}{\partial {\mu }_k}=-2\sum _{i=1}^M{r}_{ik}\left(\varphi (x^i)-{\mu }_k\right)=0,\\ {\mu }_k=\frac{{\sum }_{i=1}^M{r}_{ik}\varphi \left(x^i\right)}{{\sum }_{i=1}^M{r}_{ik}},\\ a_{ik}=\frac{r_{ik}}{{\sum }_{i=1}^M{r}_{ik}},\\ (k=1,2,\cdots ,K)\end{array}$$

• 迭代E-Step和M-Step直至收敛。

3. 补充

• 本人才疏学浅，欢迎批评、指导和交流；
• 侵权必删