{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Permutation Test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An implementation of a permutation test for hypothesis testing -- testing the null hypothesis that two different groups come from the same distribution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> `from mlxtend.evaluate import permutation_test`    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Overview"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Permutation tests (also called exact tests, randomization tests, or re-randomization tests) are nonparametric test procedures to test the null hypothesis that two different groups come from the same distribution. A permutation test can be used for significance or hypothesis testing (including A/B testing) without requiring to make any assumptions about the sampling distribution (e.g., it doesn't require the samples to be normal distributed).\n",
    "\n",
    "\n",
    "Under the null hypothesis (treatment = control), any permutations are equally likely. (Note that there are (n+m)! permutations, where *n* is the number of records in the treatment sample, and *m* is the number of records in the control sample). For a two-sided test, we define the alternative hypothesis that the two samples are different (e.g., treatment != control). \n",
    "\n",
    "1. Compute the difference (here: mean) of sample x and sample y\n",
    "2. Combine all measurements into a single dataset\n",
    "3. Draw a permuted dataset from all possible permutations of the dataset in 2.\n",
    "4. Divide the permuted dataset into two datasets x' and y' of size *n* and *m*, respectively\n",
    "5. Compute the difference (here: mean) of sample x' and sample y' and record this difference\n",
    "6. Repeat steps 3-5 until all permutations are evaluated\n",
    "7. Return the p-value as the number of times the recorded differences were more extreme than the original difference from 1. and divide this number by the total number of permutations\n",
    "\n",
    "Here, the p-value is defined as the probability, given the null hypothesis (no difference between the samples) is true, that we obtain results that are at least as extreme as the results we observed (i.e., the sample difference from 1.).\n",
    "\n",
    "More formally, we can express the computation of the p-value as follows ([2]):\n",
    "\n",
    "$$p(t > t_0) = \\frac{1}{(n+m)!} \\sum^{(n+m)!}_{j=1} I(t_j > t_0),$$\n",
    "\n",
    "where $t_0$ is the observed value of the test statistic (1. in the list above), and $t$ is the t-value, the statistic computed from the resamples (5.) $t(x'_1, x'_2, ..., x'_n, y'_1, y'_2, ..., x'_m) = |\\bar{x'} - \\bar{y'}|$, and *I* is the indicator function.\n",
    "\n",
    "\n",
    "Given a significance level that we specify prior to carrying out the permutation test (e.g., alpha=0.05), we fail to reject the null hypothesis if the p-value is greater than alpha.\n",
    "\n",
    "Note that if the number of permutation is large, sampling all permutation may not computationally be feasible. Thus, a common approximation is to perfom *k* rounds of permutations (where *k* is typically a value between 1000 and 2000)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### References\n",
    "\n",
    "- [1]  Efron, Bradley and Tibshirani, R. J., An introduction to the bootstrap, Chapman & Hall/CRC Monographs on Statistics & Applied Probability, 1994.\n",
    "- [2] Unpingco, José. Python for probability, statistics, and machine learning. Springer, 2016.\n",
    "- [3] Pitman, E. J. G., Significance tests which may be applied to samples from any population, Royal Statistical Society Supplement, 1937, 4: 119-30 and 225-32"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 1 -- Two-sided permutation test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Perform a two-sided permutation test to test the null hypothesis that two groups, \"treatment\" and \"control\" come from the same distribution. We specify alpha=0.01 as our significance level."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "treatment = [ 28.44,  29.32,  31.22,  29.58,  30.34,  28.76,  29.21,  30.4 ,\n",
    "              31.12,  31.78,  27.58,  31.57,  30.73,  30.43,  30.31,  30.32,\n",
    "              29.18,  29.52,  29.22,  30.56]\n",
    "control = [ 33.51,  30.63,  32.38,  32.52,  29.41,  30.93,  49.78,  28.96,\n",
    "            35.77,  31.42,  30.76,  30.6 ,  23.64,  30.54,  47.78,  31.98,\n",
    "            34.52,  32.42,  31.32,  40.72]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since evaluating all possible permutations may take a while, we will use the approximation method (see the introduction for details):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0066\n"
     ]
    }
   ],
   "source": [
    "from mlxtend.evaluate import permutation_test\n",
    "\n",
    "p_value = permutation_test(treatment, control,\n",
    "                           method='approximate',\n",
    "                           num_rounds=10000,\n",
    "                           seed=0)\n",
    "print(p_value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since p-value < alpha, we can reject the null hypothesis that the two samples come from the same distribution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 2 -- Calculating the p-value for correlation analysis (Pearson's R)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: this is a one-sided hypothesis testing as we conduct the permutation test as \"how many times obtain a correlation coefficient that is greater than the observed value?\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Observed pearson R: 0.81\n",
      "P value: 0.09\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "from mlxtend.evaluate import permutation_test\n",
    "\n",
    "x = np.array([1, 2, 3, 4, 5, 6])\n",
    "y = np.array([2, 4, 1, 5, 6, 7])\n",
    "\n",
    "print('Observed pearson R: %.2f' % np.corrcoef(x, y)[1][0])\n",
    "\n",
    "\n",
    "p_value = permutation_test(x, y,\n",
    "                           method='exact',\n",
    "                           func=lambda x, y: np.corrcoef(x, y)[1][0],\n",
    "                           seed=0)\n",
    "print('P value: %.2f' % p_value)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## API"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "## permutation_test\n",
      "\n",
      "*permutation_test(x, y, func='x_mean != y_mean', method='exact', num_rounds=1000, seed=None)*\n",
      "\n",
      "Nonparametric permutation test\n",
      "\n",
      "**Parameters**\n",
      "\n",
      "- `x` : list or numpy array with shape (n_datapoints,)\n",
      "\n",
      "    A list or 1D numpy array of the first sample\n",
      "    (e.g., the treatment group).\n",
      "\n",
      "- `y` : list or numpy array with shape (n_datapoints,)\n",
      "\n",
      "    A list or 1D numpy array of the second sample\n",
      "    (e.g., the control group).\n",
      "\n",
      "- `func` : custom function or str (default: 'x_mean != y_mean')\n",
      "\n",
      "    function to compute the statistic for the permutation test.\n",
      "    - If 'x_mean != y_mean', uses\n",
      "    `func=lambda x, y: np.abs(np.mean(x) - np.mean(y)))`\n",
      "    for a two-sided test.\n",
      "    - If 'x_mean > y_mean', uses\n",
      "    `func=lambda x, y: np.mean(x) - np.mean(y))`\n",
      "    for a one-sided test.\n",
      "    - If 'x_mean < y_mean', uses\n",
      "    `func=lambda x, y: np.mean(y) - np.mean(x))`\n",
      "    for a one-sided test.\n",
      "\n",
      "- `method` : 'approximate' or 'exact' (default: 'exact')\n",
      "\n",
      "    If 'exact' (default), all possible permutations are considered.\n",
      "    If 'approximate' the number of drawn samples is\n",
      "    given by `num_rounds`.\n",
      "    Note that 'exact' is typically not feasible unless the dataset\n",
      "    size is relatively small.\n",
      "\n",
      "- `num_rounds` : int (default: 1000)\n",
      "\n",
      "    The number of permutation samples if `method='approximate'`.\n",
      "\n",
      "- `seed` : int or None (default: None)\n",
      "\n",
      "    The random seed for generating permutation samples if\n",
      "    `method='approximate'`.\n",
      "\n",
      "**Returns**\n",
      "\n",
      "p-value under the null hypothesis\n",
      "\n",
      "**Examples**\n",
      "\n",
      "For usage examples, please see\n",
      "    [http://rasbt.github.io/mlxtend/user_guide/evaluate/permutation_test/](http://rasbt.github.io/mlxtend/user_guide/evaluate/permutation_test/)\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "with open('../../api_modules/mlxtend.evaluate/permutation_test.md', 'r') as f:\n",
    "    s = f.read() \n",
    "print(s)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}