{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一.距离度量\n",
    "对于聚类，其实之前已经有算法涉及了，比如GMM，这一章开始再次做系统介绍。聚类的核心思想套用一句俗语：“物以类聚，人与群分”，这里面首先有一个“距离”的概念，“聚”是因为“距离近”，“分”是因为“距离远”，下面将常用的“距离”罗列一下，首先定义，样本$x_i=(x_{i1},x_{i2},...,x_{in})$与样本点$x_j=(x_{j1},x_{j2},...,x_{jn})$\n",
    "\n",
    "#### 明科夫斯基距离\n",
    "\n",
    "$$\n",
    "d_{ij}=(\\sum_{k=1}^n \\left|x_{ik}-x_{jk}\\right|^p)^{\\frac{1}{p}}\n",
    "$$ \n",
    "\n",
    "这里，$p\\geq 1$，当$p=2$时称为欧氏距离，$p=1$称为曼哈顿距离，$p=\\infty$称为切比雪夫距离，这时：   \n",
    "\n",
    "$$\n",
    "d_{ij}=\\max_{k}\\left|x_{ik}-x_{jk}\\right|\n",
    "$$\n",
    "\n",
    "#### 马氏距离\n",
    "\n",
    "$$\n",
    "d_{ij}=\\left[(x_i-x_j)^TS^{-1}(x_i-x_j)\\right]^{\\frac{1}{2}}\n",
    "$$  \n",
    "\n",
    "这里，$S$为整个样本集$X=(x_{ij})_{m\\times n}$的协方差矩阵\n",
    "\n",
    "#### 相关系数\n",
    "$$\n",
    "r_{ij}=\\frac{(x_i-\\bar{x_i})^T(x_j-\\bar{x_j})}{[(x_i-\\bar{x_i})^T(x_i-\\bar{x_i})\\cdot (x_j-\\bar{x_j})^T(x_j-\\bar{x_j})]^{\\frac{1}{2}}},\\bar{x_i}=\\frac{1}{n}\\sum_{k=1}^nx_{ik},\\bar{x_j}=\\frac{1}{n}\\sum_{k=1}^nx_{jk}\\\\\n",
    "d_{ij}=1-r_{ij}\n",
    "$$\n",
    "#### 夹角余弦\n",
    "$$\n",
    "s_{ij}=\\frac{x_i^Tx_j}{[x_i^Tx_i\\cdot x_j^Tx_j]^{\\frac{1}{2}}}\\\\\n",
    "d_{ij}=1-s_{ij}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二.类的定义\n",
    "\n",
    "有了“距离”的定义，我们就可以进一步定义类了，设$T$为给定的正数，若样本集合$G$中任意两个样本$x_i,x_j$，有：   \n",
    "\n",
    "$$\n",
    "d_{ij}\\leq T\n",
    "$$  \n",
    "\n",
    "则称$G$为一个类（簇）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三.性能评估\n",
    "接下来，我们继续考虑聚类效果的好坏评估标准，显然需要符合我们期望的“物以类聚，人以群分”，有了“距离”的定义之后，我们可以换一个表述：类内距离尽可能小，类间距离尽可能大，所以我们进一步需要对类内距离和类间距离做一个定义\n",
    "\n",
    "#### 类内距离\n",
    "\n",
    "##### 类内最大距离\n",
    "类中任意两个样本之间的最大距离\n",
    "$$\n",
    "diam(G)=\\max_{x_i,x_j\\in G}d_{ij}\n",
    "$$\n",
    "\n",
    "##### 类内平均距离\n",
    "类内任意两样本之间距离的均值\n",
    "\n",
    "$$\n",
    "avg(G)=\\frac{1}{n_G(n_G-1)}\\sum_{x_i\\in G}\\sum_{x_j\\in G}d_{ij}\n",
    "$$\n",
    "\n",
    "##### 散布矩阵\n",
    "$$\n",
    "A_G=\\sum_{i=1}^{n_G}(x_i-\\bar{x_G})(x_i-\\bar{x_G})^T,\\bar{x_G}=\\sum_{i=1}^{n_G}x_i\n",
    "$$\n",
    "##### 协方差矩阵\n",
    "$$\n",
    "S_G=\\frac{1}{n-1}A_G\n",
    "$$  \n",
    "\n",
    "这里，$n$为样本的维数\n",
    "\n",
    "#### 类间距离\n",
    "设两类分别为$G_q$和$G_p$\n",
    "##### 最短距离\n",
    "$$\n",
    "d_{min}(G_p,G_q)=\\min\\{d_{ij}\\mid x_i\\in G_p,x_j\\in G_q\\}\n",
    "$$\n",
    "##### 最长距离\n",
    "$$\n",
    "d_{max}(G_p,G_q)\\max\\{d_{ij}\\mid x_i\\in G_p,x_j\\in G_q\\}\n",
    "$$\n",
    "##### 中心距离\n",
    "$$\n",
    "d_{cen}(G_p,G_q)=d_{\\bar{x}_p\\bar{x}_q}\n",
    "$$\n",
    "这里，$\\bar{x}_p$和$\\bar{x}_q$分别为类$G_p$和$G_q$的中心点\n",
    "\n",
    "##### 平均距离\n",
    "$$\n",
    "d_{avg}(G_p,G_q)=\\frac{1}{n_{G_p}n_{G_q}}\\sum_{x_i\\in G_p}\\sum_{x_j\\in G_q}d_{ij}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 性能评估\n",
    "所以，我们在此基础上可以构造既能反映类内距离，又能反映类间距离的指标\n",
    "#### DB 指数\n",
    "\n",
    "$$\n",
    "DBI=\\frac{1}{k}\\sum_{i=1}^k\\max_{j\\neq i}(\\frac{avg(G_i)+avg(G_j)}{d_{cen}(G_i,G_j)})\n",
    "$$   \n",
    "\n",
    "显然，DBI越小越好\n",
    "#### Dunn指数  \n",
    "\n",
    "$$\n",
    "DI=\\min_{1\\leq i\\leq k}\\left\\{\\min_{j\\neq i}(\\frac{d_{min}(G_i,G_j)}{\\max_{1\\leq l\\leq k}diam(G_l)})\\right \\}\n",
    "$$  \n",
    "\n",
    "显然，DI越大越好\n",
    "\n",
    "#### 轮廓系数\n",
    "\n",
    "$$\n",
    "SCI=\\frac{1}{m}\\sum_{i=1}^m\\frac{b(x_i)-a(x_i)}{max(b(x_i),a(x_i))}\n",
    "$$  \n",
    "\n",
    "其中，$a(\\cdot)$表示当前样本与簇内其他样本的平均距离，所以$a(\\cdot)$越小，反映了该簇越聚集，$b(\\cdot)$表示当前样本与其他簇的平均距离的最小值，所以$b(\\cdot)$越大，表示与其他簇越分离，而轮廓系数SCI便是所有样本轮廓系数的均值，可以看出SCI越大越好"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}