第10章 模式识别系统的评价.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第十章 模式识别系统的评价\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 二轮总结笔记\n",
    "\n",
    "\n",
    "### 一、监督模式识别方法的错误率估计\n",
    "\n",
    "#### 1. 测试错误率\n",
    "\n",
    "##### (1) 先验概率$P(\\omega_1)$，$P(\\omega_2)$未知——随机抽样\n",
    "\n",
    "1. 错误率：测试集中有$N$个样本，错分了$k$个，则测试错误率$\\displaystyle\\hat\\varepsilon = \\frac{k}{N}$。\n",
    "2. 性质：\n",
    "+ 测试错误率是真实错误率的**最大似然估计**。\n",
    "+ 测试错误率的期望$E[\\hat\\varepsilon]=\\varepsilon$，是真实错误率的无偏估计。\n",
    "+ 测试错误率的方差$\\displaystyle D[\\hat\\varepsilon]=\\frac{\\varepsilon(1-\\varepsilon)}{N}$。\n",
    "+ $N$越**大**，测试错误率的置信区间越**小**，测试错误率越**可信**。\n",
    "\n",
    "##### (2) 先验概率$P(\\omega_1)$，$P(\\omega_2)$已知——选择性抽样\n",
    "\n",
    "1. 错误率：在两类中按照先验概率比例进行抽样，$N_1=P(\\omega_1)N$，$N_2=P(\\omega_2)N$，两类分别错分了$k_1$和$k_2$个，则测试错误率$\\displaystyle\\hat\\varepsilon = P(\\omega_1)\\frac{k_1}{N_1} + P(\\omega_2)\\frac{k_2}{N_2} = \\frac{k_1+k_2}{N}$。\n",
    "2. 性质：\n",
    "+ 测试错误率是真实错误率的**最大似然估计**。\n",
    "+ 测试错误率的期望$E[\\hat\\varepsilon]=\\varepsilon$，是真实错误率的无偏估计。\n",
    "+ 测试错误率的方差$\\displaystyle D[\\hat\\varepsilon] = \\frac{1}{N}\\left[P(\\omega_1)\\frac{k_1}{N_1}\\left(1-\\frac{k_1}{N_1}\\right)+P(\\omega_2)\\frac{k_2}{N_2}\\left(1-\\frac{k_2}{N_2}\\right)\\right]$，方差比前一种方法**小**。\n",
    "\n",
    "#### 2. 交叉验证（cross-validation，CV）\n",
    "\n",
    "##### (1) 分类\n",
    "\n",
    "1. k轮n倍交叉验证（n-fold cross-validation）：偏差大，方差小。\n",
    "2. 留一法交叉验证（leave-one-out cross-validation）：适用于样本少的情况，偏差小，方差大。\n",
    "\n",
    "##### (2) 性质\n",
    "\n",
    "1. 临时测试集较小，错误率估计接近全部样本，多轮实验平均可以减少错误率方差。\n",
    "2. 可以用于选择分类器参数，用交叉验证错误率最小的参数在全部样本上训练分类器。\n",
    "\n",
    "#### 3. 自举法和.632估计\n",
    "\n",
    "##### (1) 自举估计\n",
    "\n",
    "对样本进行$B$次自举重采样，重采样后的样本作为训练集，没有抽到的样本作为测试集，得到的错误率的平均。\n",
    "\n",
    "##### (2) .632估计\n",
    "\n",
    "1. $\\text{B}.632=0.368\\times \\text{AE} + 0.632\\times\\text{B1}$。其中$\\text{AE}$是训练错误率（视在错误率），$\\text{B1}$是自举错误率。\n",
    "2. .632估计是对错误率更好的估计。\n",
    "\n",
    "\n",
    "### 二、有限样本下错误率的区间估计问题\n",
    "\n",
    "#### 1. 问题的提出\n",
    "\n",
    "##### (1) 标准数据集\n",
    "\n",
    "1. 一套数据多次划分成训练集和测试集。\n",
    "2. 固定划分。\n",
    "3. 同时统计错误率的平均值和方差。\n",
    "\n",
    "##### (2) 性质\n",
    "\n",
    "1. 各次实验不是独立的，估计的错误率区间会偏小。\n",
    "2. 仅基于交叉验证，不存在错误率估计量方差的无偏估计。\n",
    "\n",
    "#### 2. 用扰动重采样估计SVM错误率的置信区间\n",
    "\n",
    "##### (1) 性质\n",
    "\n",
    "1. 考虑了测试样本的不确定性和现有训练样本的不确定性，能够得到性能的全面评价。\n",
    "2. 适用于样本数目趋于无穷大，但是有限样本下表现依然较好。\n",
    "3. 只适用于线性核。\n",
    "\n",
    "\n",
    "### 三、特征提取与选择对分类器性能估计的影响\n",
    "\n",
    "#### 1. CV1\n",
    "\n",
    "##### (1) 定义\n",
    "\n",
    "对所有样本进行特征选择核提取，然后进行交叉验证。\n",
    "\n",
    "##### (2) 性质\n",
    "\n",
    "1. 对分类器性能估计偏乐观，训练集用了测试集的信息。\n",
    "2. 当初始特征维数高，样本数目小时过学习问题明显。\n",
    "\n",
    "#### 2. CV2\n",
    "\n",
    "##### (1) 定义\n",
    "\n",
    "只对训练集进行特征选择和提取，然后进行交叉验证。\n",
    "\n",
    "##### (2) 性质\n",
    "\n",
    "1. 能得到分类器性能的真实估计。\n",
    "2. 需要设计出唯一的特征选择和提取方案。可以全部样本重新特征选择和提取，也可以在CV2过程中的特征选择和提取中综合。\n",
    "\n",
    "\n",
    "### 四、从分类的显著性推断特征与类别的关系\n",
    "\n",
    "#### 1. 随机置换法\n",
    "\n",
    "##### (1) 如何得到空分布\n",
    "\n",
    "1. 保持原有样本中两类样本比例不变的情况下，随机打乱样本的类别标号。\n",
    "2. 用原有的特征选择和提取和分类方法进行分类。\n",
    "\n",
    "##### (2) 如何判断显著性\n",
    "\n",
    "用真实分类器性能和空分布比较，通常以小于$0.05$作为参考。\n",
    "\n",
    "\n",
    "### 五、非监督模式识别系统性能的评价\n",
    "\n",
    "#### 1. 紧致性（compactness）/一致性（homogeneity）\n",
    "\n",
    "##### (1) 公式\n",
    "\n",
    "$$\n",
    "V(C) = \\sqrt{\\frac{1}{N}\\sum_{C_k\\in C}\\sum_{i\\in C_k}\\delta(i,\\mu_k)}\n",
    "$$\n",
    "\n",
    "##### (2) 性质\n",
    "\n",
    "越小越好，取值范围$[0,\\infty]$。\n",
    "\n",
    "#### 2. 连接性质（connectedness）/连接度（connectivity）\n",
    "\n",
    "##### (1) 公式\n",
    "\n",
    "$$\\begin{aligned}\n",
    "\\text{Conn}(C) &= \\sum_{i=1}^N\\sum_{j=1}^Lx_{i,nn_{\\scriptstyle i(j)}} \\\\\n",
    "x_{i,nn_{\\scriptstyle i(j)}} &= \\begin{cases}\\displaystyle \\frac{1}{j}&第i个样本和其第j个近邻不在同一个聚类\\\\0&在同一个聚类\\end{cases}\n",
    "\\end{aligned}$$\n",
    "\n",
    "##### (2) 性质\n",
    "\n",
    "越小越好，取值范围$[0,\\infty]$。\n",
    "\n",
    "#### 3. 分离度（separation）\n",
    "\n",
    "##### (1) 性质\n",
    "\n",
    "越大越好。\n",
    "\n",
    "#### 4. Silhouette宽度\n",
    "\n",
    "##### (1) 公式\n",
    "\n",
    "$$\\begin{aligned}\n",
    "S(i) &= \\frac{b_i-a_i}{\\max(b_i,a_i)} \\\\\n",
    "a_i &= 样本i到和它\\textbf{同类}的所有样本的\\textbf{平均距离}\\\\\n",
    "b_i &= 样本i到其他聚类中\\textbf{最近}的一个聚类的所有样本的\\textbf{平均距离}\n",
    "\\end{aligned}$$\n",
    "\n",
    "##### (2) 性质\n",
    "\n",
    "越大越好，取值范围$[-1,1]$。\n",
    "\n",
    "#### 5. Dunn指数（Dunn index）\n",
    "\n",
    "##### (1) 公式\n",
    "\n",
    "$$\\begin{aligned}\n",
    "D(C) &= \\min\\limits_{C_k\\in C}\\left(\\min\\limits_{C_l\\in C}\\frac{\\text{dist}(C_k,C_l)}{\\displaystyle\\max\\limits_{C_m\\in C}\\text{diam}(C_m)}\\right)\\\\\n",
    "\\text{dist}(C_k,C_l) &= C_k,C_l两类中距离最近的样本间的距离\\\\\n",
    "\\text{diam}(C_m) &= C_m中最大的类内距离\n",
    "\\end{aligned}$$\n",
    "\n",
    "##### (2) 性质\n",
    "\n",
    "越大越好，取值范围$[0,\\infty]$。\n",
    "\n",
    "#### 6. 预测效力\n",
    "\n",
    "##### (1) 算法\n",
    "\n",
    "将样本随机分为两份，各自进行聚类，用一份得到的聚类结果作为临时训练样本，对另一份进行最近邻法分类。\n",
    "\n",
    "##### (2) 性质\n",
    "\n",
    "重合程度越大聚类结果越稳定。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## 一轮学习笔记（包含代码实现）\n",
    "\n",
    "这一章介绍了大多数其他教材放在第一章的内容，即分类算法的检验方法。\n",
    "\n",
    "教材的重点放在了检验方法得出的错误率的理论分析上面，即从概率论的角度分析错误率的期望和方差。这部分都是数学推导，不需要写代码。\n",
    "\n",
    "而教材中提到的计算错误率的检验方法实现起来都很非常简单，而且在sklearn中都有库可以很方便的调用。\n",
    "\n",
    "只有扰动重采样估计SVM错误率的置信区间非常复杂，但是这个算法其实不重要，作者把它放在教材上主要还是因为这个算法是作者自己发的文章。\n",
    "\n",
    "下面我只实现一下bootstrap .632估计。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.utils import resample\n",
    "from sklearn.svm import LinearSVC\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面用手写数字识别的数据集。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.load(\"./data/digit_0_1_X.npy\")\n",
    "y = np.load(\"./data/digit_0_1_y.npy\")\n",
    "X = X[:1000]\n",
    "y = y[:1000] #前一千个是0和1，后面是其他数字\n",
    "y = y.reshape(1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "先计算自举错误率B1。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bootstrap第1次，自举样本集中包含了原始样本集62.5%的样本。\n",
      "本次训练错误率为：0.002666666666666706\n",
      "bootstrap第2次，自举样本集中包含了原始样本集61.8%的样本。\n",
      "本次训练错误率为：0.010471204188481686\n",
      "bootstrap第3次，自举样本集中包含了原始样本集62.2%的样本。\n",
      "本次训练错误率为：0.002645502645502673\n",
      "bootstrap第4次，自举样本集中包含了原始样本集64.3%的样本。\n",
      "本次训练错误率为：0.0028011204481792618\n",
      "bootstrap第5次，自举样本集中包含了原始样本集62.9%的样本。\n",
      "本次训练错误率为：0.0\n",
      "bootstrap第6次，自举样本集中包含了原始样本集61.199999999999996%的样本。\n",
      "本次训练错误率为：0.002577319587628857\n",
      "bootstrap第7次，自举样本集中包含了原始样本集63.800000000000004%的样本。\n",
      "本次训练错误率为：0.002762430939226568\n",
      "bootstrap第8次，自举样本集中包含了原始样本集62.9%的样本。\n",
      "本次训练错误率为：0.0026954177897574594\n",
      "bootstrap第9次，自举样本集中包含了原始样本集64.60000000000001%的样本。\n",
      "本次训练错误率为：0.0028248587570621764\n",
      "bootstrap第10次，自举样本集中包含了原始样本集64.7%的样本。\n",
      "本次训练错误率为：0.0\n",
      "自举平均错误率B1 = 0.002944452102250539\n"
     ]
    }
   ],
   "source": [
    "# 下面计算十次bootstrap样本集在线性支持向量机上的错误率\n",
    "b1 = 0\n",
    "for i in range(10):\n",
    "    bootstrap_index = []\n",
    "    test_index = set(range(X.shape[0]))\n",
    "    X_bootstrap = resample(X)\n",
    "    for x in X_bootstrap:\n",
    "        for j in range(X.shape[0]):\n",
    "            if (X[j] == x).all():\n",
    "                bootstrap_index.append(j)\n",
    "                if j in test_index:\n",
    "                    test_index.remove(j)\n",
    "                break\n",
    "    test_index = list(test_index)\n",
    "    y_bootstrap = y[bootstrap_index]\n",
    "    X_test = X[test_index]\n",
    "    y_test = y[test_index]\n",
    "    print(\"bootstrap第\", i + 1, \"次，自举样本集中包含了原始样本集\",\n",
    "          (1 - len(test_index) / X.shape[0]) * 100, \"%的样本。\", sep=\"\")\n",
    "    lsvc = LinearSVC()\n",
    "    lsvc.fit(X_bootstrap, y_bootstrap)\n",
    "    err = 1 - lsvc.score(X_test, y_test)\n",
    "    b1 += err\n",
    "    print(\"本次训练错误率为：\", err,sep=\"\")\n",
    "b1 /= 10\n",
    "print(\"自举平均错误率B1 =\", b1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "再计算全部样本上的训练错误率（视在错误率）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "全部样本上的训练错误率AE = 0.0\n"
     ]
    }
   ],
   "source": [
    "lsvc = LinearSVC()\n",
    "lsvc.fit(X, y)\n",
    "ae = 1 - lsvc.score(X, y)\n",
    "print(\"全部样本上的训练错误率AE =\", ae)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "接下来计算B.632错误率。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "B.632错误率 = 0.0018608937286223406\n"
     ]
    }
   ],
   "source": [
    "print(\"B.632错误率 =\", 0.368 * ae + 0.632 * b1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.16"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}