聚类/3. k-means 算法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**k均值**（k-means）算法最初由 MacQueen 在 1967 年提出，是最著名的原型聚类算法之一。假设样本集被划分为 k 类 $\\{C_1, C_2, \\dots, C_k\\}$，我们可以计算出每个类的均值向量，也就是类的中心位置：\n",
    "\n",
    "$$\n",
    "\\mu_i = \\frac{\\sum_{x \\in C_i}x}{|C_i|}\n",
    "$$\n",
    "\n",
    "得到每个类的均值向量后，可以计算出每个样本到均值向量的平方误差之和：\n",
    "\n",
    "$$\n",
    "E(C_i) = \\sum_{x \\in C_i} \\|x-\\mu_i\\|^2_2\n",
    "$$\n",
    "\n",
    "将 k 个类的平方误差之和累加起来，就是 k 均值聚类算法的损失函数：\n",
    "\n",
    "$$\n",
    "E(C) = \\sum_{i=1}^k E(C_i)\n",
    "$$\n",
    "\n",
    "函数 $E(C)$ 也称为能量，它表示簇内样本围绕簇均值向量的紧密程度，E 值越小，表示簇内样本相似度越高，k 均值算法就是试图最小化该函数。不过要计算该函数的最小值，必须计算出样本集所有可能的簇划分，这是一个 NP 难问题，因此 k 均值算法采用贪心策略，通过迭代优化来近似求解。\n",
    "\n",
    "k 均值算法流程如下：\n",
    "\n",
    "* 从样本集 D 中随机选择 k 个样本作为初始簇，每个样本的值就是该簇的均值向量\n",
    "* 计算每个样本到均值向量的距离，选择距离最近的均值向量将每个样本划分到相应的簇里\n",
    "* 根据每个簇里的样本，重新计算每个簇的均值向量\n",
    "* 不断重复上述过程，直到迭代收敛或达到停止条件\n",
    "\n",
    "k 均值聚类算法的时间复杂度是 O(mnk)，其中 m 是样本维数，n 是样本个数，k 是类别个数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 学习向量量化\n",
    "\n",
    "**学习向量量化**（Learning Vector Quantization，简称 LVQ）和 k-means 一样，也是一种原型聚类算法。不过 LVQ 假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。\n",
    "\n",
    "首先随机初始化一组原型向量 $\\{p_1, p_2, \\dots, p_q\\}$，q 是一个超参数，代表簇的个数，然后从样本集中随机选择一个样本 $(x_j, y_j)$，计算样本 $x_j$ 和 原型向量中每个向量的距离，找出和 $x_j$ 距离最近的向量 $p_{i^*}$，如果样本 $x_j$ 的类别 $y_j$ 和 原型向量 $p_{i^*}$ 的类别相同，则使用下面的公式更新原型向量：\n",
    "\n",
    "$$\n",
    "p' = p_{i^*} + \\eta \\cdot (x_j - p_{i^*})\n",
    "$$\n",
    "\n",
    "如果样本 $x_j$ 的类别 $y_j$ 和 原型向量 $p_{i^*}$ 的类别不同，则使用下面的公式更新原型向量：\n",
    "\n",
    "$$\n",
    "p' = p_{i^*} - \\eta \\cdot (x_j - p_{i^*})\n",
    "$$\n",
    "\n",
    "直观上看，如果样本和原型向量类别相同，就让原型向量向样本靠拢，否则就远离样本。\n",
    "\n",
    "重复上面的迭代步骤，一直到满足停止条件为止（达到最大迭代次数，或者原型向量更新幅度很小甚至不再更新）。\n",
    "\n",
    "最终学的原型向量可以实现对样本空间的簇划分，将每个样本划入与其距离最近的原型向量即可，也就是说每个原型向量对应一个划分区域，在这个区域里，每个样本和原型向量的距离不大于它和其他原型向量的距离，这样的划分通常称为 **Voronoi 剖分**（Voronoi tessellation）。\n",
    "\n",
    "如果使用原型向量来表示划分区域中的样本，则可以实现数据的 **有损压缩**（lossy compression），这称为 **向量量化**（vector quantization），这就是 LVQ 名字的由来。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}