{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**聚类**（clustering） 是一种无监督学习算法（unsupervised learning），训练样本的标记信息通常是未知的，它试图对无标记的训练样本进行学习，找到数据的内在性质和规律，将数据集划分成若干个通常是不相交的子集，这些子集被称为 **簇**（cluster）。通过这样的划分，每个簇可能对应一个潜在的概念，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇所对应的概念语义需要由使用者把握和命名。\n",
    "\n",
    "## 聚类模型的评估\n",
    "\n",
    "如何评估聚类模型的好坏，也就是如何对聚类的性能进行度量，这也被称为 **有效性指标**（validity index）。直观上看，我们希望同一簇的样本尽可能的彼此相似，不同簇的样本尽可能的不同，也就是我们常说的 “物以类聚”。\n",
    "\n",
    "评估方法一般有两种，一种是将聚类结果和某个**参考模型**（reference model）进行比较，这称作**外部指标**（external index）；另一种是直接考察聚类结果本身，称作**内部指标**（internal index）。\n",
    "\n",
    "### 外部指标\n",
    "\n",
    "外部指标的计算首先要定义几个变量，假定通过聚类算法给出的簇划分为 $C = \\{C_1, C_2, ..., C_k\\}$，而根据参考模型给出的簇划分为 $C^* = \\{C_1^*, C_2^*, ..., C_s^*\\}$，也就是说聚类算法将数据划分为 k 类，参考模型将数据划分为 s 类，一般情况下 $k \\neq s$。然后将样本两两进行配对得到组合 $(x_i, x_j)$，其中 $i < j$。一共可以得到 $m(m-1)/2$ 个组合，并且只会有四种不同的情况：\n",
    "\n",
    "* $x_i$ 和 $x_j$ 在 $C$ 中属于相同簇，在 $C^*$ 中也属于相同簇，一共有 a 个组合\n",
    "* $x_i$ 和 $x_j$ 在 $C$ 中属于相同簇，在 $C^*$ 中属于不同簇，一共有 b 个组合\n",
    "* $x_i$ 和 $x_j$ 在 $C$ 中属于不同簇，在 $C^*$ 中属于相同簇，一共有 c 个组合\n",
    "* $x_i$ 和 $x_j$ 在 $C$ 中属于不同簇，在 $C^*$ 中也属于不同簇，一共有 d 个组合\n",
    "\n",
    "很显然：\n",
    "\n",
    "$$\n",
    "a + b + c + d = m(m-1)/2\n",
    "$$\n",
    "\n",
    "根据这四个变量，就可以定义出下面这些常用的外部指标：\n",
    "\n",
    "* **Jaccard 系数**（Jaccard Coefficient，简称 JC）\n",
    "\n",
    "$$\n",
    "JC = \\frac{a}{a+b+c}\n",
    "$$\n",
    "\n",
    "* **FM 指数**（Fowlkes and Mallows Index，简称 FMI）\n",
    "\n",
    "$$\n",
    "FMI = \\sqrt {\\frac{a}{a+b} \\cdot \\frac{a}{a+c}}\n",
    "$$\n",
    "\n",
    "* **Rand 指数**（Rand Index，简称 RI）\n",
    "\n",
    "$$\n",
    "RI = \\frac{2(a+d)}{m(m-1)}\n",
    "$$\n",
    "\n",
    "这些指标值的范围都在 0 - 1 之间，值越大说明聚类结果越准。\n",
    "\n",
    "### 内部指标\n",
    "\n",
    "在定义内部指标之前，也首先定义几个变量，假定通过聚类算法给出的簇划分为 $C = \\{C_1, C_2, ..., C_k\\}$，样本 $x_i$ 和 $x_j$ 之间的距离记为 $dist(x_i, x_j)$，可以得到簇内样本间的平均距离：\n",
    "\n",
    "$$\n",
    "avg(C) = \\frac{2}{|C|(|C|-1)} \\sum_{1 \\leqslant i \\leqslant j \\leqslant |C|} dist(x_i, x_j)\n",
    "$$\n",
    "\n",
    "簇内样本间的最远距离：\n",
    "\n",
    "$$\n",
    "diam(C) = max_{1 \\leqslant i \\leqslant j \\leqslant |C|} dist(x_i, x_j)\n",
    "$$\n",
    "\n",
    "簇 $C_i$ 和 簇 $C_j$ 最近样本间的距离：\n",
    "\n",
    "$$\n",
    "d_{min}(C_i, C_j) = min_{x_i \\in C_i, x_j \\in C_j} dist(x_i, x_j)\n",
    "$$\n",
    "\n",
    "簇 C 的中心点：\n",
    "\n",
    "$$\n",
    "\\mu = \\frac{1}{|C|} \\sum_{1 \\leqslant i \\leqslant |C|} x_i\n",
    "$$\n",
    "\n",
    "簇 $C_i$ 和 簇 $C_j$ 中心点间的距离：\n",
    "\n",
    "$$\n",
    "d_{cen}(C_i, C_j) = dist(\\mu_i, \\mu_j)\n",
    "$$\n",
    "\n",
    "从而得到下面这些常用的内部指标：\n",
    "\n",
    "* **DB 指数**（Davies-Bouldin Index，简称 DBI）\n",
    "\n",
    "$$\n",
    "DBI = \\frac{1}{k} \\sum_{1}^k \\mathop \\max _{j \\neq i} ( \\frac{avg(C_i) + avg(C_j)}{d_{cen}(C_i, C_j)} )\n",
    "$$\n",
    "\n",
    "* **Dunn 指数**（Dunn Index，简称 DI）\n",
    "\n",
    "$$\n",
    "DI = \\mathop \\min_{1 \\leqslant i \\leqslant k} \\Big \\{ \\mathop \\min_{j \\neq i} \\Big ( \\frac{d_{min}(C_i,C_j)}{\\mathop \\max_{1 \\leqslant l \\leqslant k}diam(C_l)} \\Big ) \\Big \\}\n",
    "$$\n",
    "\n",
    "## 距离的度量\n",
    "\n",
    "聚类的核心概念是 **距离**（distance）或 **相似度**（similarity），距离或相似度的定义多种多样，选择合适的距离度量方法是聚类的关键。\n",
    "\n",
    "* 闵可夫斯基距离（闵氏距离）\n",
    "  * 欧式距离\n",
    "  * 曼哈顿距离\n",
    "  * 切比雪夫距离\n",
    "* 马哈拉诺比斯距离（马氏距离）\n",
    "* 相关系数\n",
    "* 夹角余弦\n",
    "\n",
    "参考 [kNN 距离度量方法](../kNN/02.%20距离度量方法.ipynb)"
   ]
  }
 ],
 "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
}