Initial testing - 1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "##random sampling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#creates sample table of specified size\n",
    "def create_sample_table (nrow, data):\n",
    "    sample_table = np.empty(shape=(nrow, data.shape[1]))\n",
    "    for c in range (0,sample_table.shape[1]):\n",
    "        sample_table[:,c] = np.random.choice (data[:,c], nrow, replace = False)\n",
    "    return sample_table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#get the MSE for one dataset, aggregate, and sample table size\n",
    "def MSE_one_example (sample_table_nrows, data, aggregate, quantile):\n",
    "    sample_table = create_sample_table (sample_table_nrows, data)\n",
    "    MSE = 0\n",
    "    for c in range (0,sample_table.shape[1]):\n",
    "        if (quantile != 0):\n",
    "            actual = aggregate(data[:,c], quantile)\n",
    "            sample = aggregate(sample_table[:,c], quantile)\n",
    "            MSE += (actual-sample)**2\n",
    "        else:\n",
    "            actual = aggregate(data[:,c])\n",
    "            sample = aggregate(sample_table[:,c])\n",
    "            MSE += (actual-sample)**2 \n",
    "    MSE = MSE/sample_table.shape[1]\n",
    "    return MSE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#prints MSE results for different sample table sizes\n",
    "def get_results (sample_table_sizes, data, aggregate, i, dataset_size):    \n",
    "    aggregate_mse = []\n",
    "    for sample_table_ratio in sample_table_sizes:\n",
    "        aggregate_mse.append(MSE_one_example (round(sample_table_ratio*data.shape[0]), data, aggregate, quantile = i))\n",
    "    print (\"***New Example***\")\n",
    "    print (\"dataset size: \")\n",
    "    print(dataset_size)\n",
    "    print (\"aggregate: \")\n",
    "    print(aggregate)\n",
    "    print (\"quantile: \")\n",
    "    print (i)\n",
    "    print (\"sample table sizes: \")\n",
    "    print(sample_table_sizes)\n",
    "    print (\"MSE values: \")\n",
    "    print(aggregate_mse)\n",
    "    plt.plot (sample_table_sizes, aggregate_mse)\n",
    "    plt.pause(0.05)\n",
    "    plt.show()\n",
    "    print (\"********\") "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#takes in list of dataset sizes, list of aggregates, list of sample table sizes and plots MSE vs. sample table\n",
    "#size for each dataset\n",
    "#***dataset is ~N(0,1)\n",
    "#@param dataset_sizes (list of tuples)\n",
    "#@param aggregates (list of numpy aggregates on one column)\n",
    "#@param sample_table_sizes (list of numbers representing ratios of sample table size to data table size)\n",
    "#@param outliers (whether to do simple outliers test)\n",
    "def eval_random_sampling_MSE (dataset_sizes, aggregates, sample_table_sizes, outliers, stdev):\n",
    "    for dataset_size in dataset_sizes:\n",
    "        data = np.random.normal(loc = 0, scale = stdev, size=dataset_size)\n",
    "        if (outliers):\n",
    "            for c in range (0, data.shape[1]):\n",
    "                for r in range (0, data.shape[0]):\n",
    "                    if (r%200 == 0):\n",
    "                        data [r, c] += 100   \n",
    "        for aggregate in aggregates:\n",
    "            if (aggregate == np.quantile):\n",
    "                for i in [.1, .25, .5, .75]:\n",
    "                    get_results (sample_table_sizes, data, aggregate, i, dataset_size)\n",
    "            else:\n",
    "                get_results (sample_table_sizes, data, aggregate, 0, dataset_size)\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Test on some examples\n",
    "dataset_sizes = [(100, 100), (250, 250), (500, 500), (1000, 1000), (2500, 2500), (5000, 5000)]\n",
    "aggregates = [np.mean, np.std, np.amax, np.quantile]\n",
    "sample_table_sizes = [.01, .05, .1, .25, .5, .75, .9]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_random_sampling_MSE (dataset_sizes, aggregates, sample_table_sizes, False, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Test with outliers.  Notice much more variation for smaaller sample table sizes\n",
    "eval_random_sampling_MSE (dataset_sizes, aggregates, sample_table_sizes, True, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Test with high stdev - notice error scales proportionally\n",
    "eval_random_sampling_MSE (dataset_sizes, aggregates, sample_table_sizes, True, 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Test on categorical dataset.  Cat1 = 0:.25, Cat2 = .25:.5, Cat3 = . .5:.75, Cat4 =.75:1 \n",
    "\n",
    "#Save results\n",
    "sum_one_category_MSE = []\n",
    "\n",
    "data = np.random.normal(loc = 0, scale = 1, size=(1000,1000))\n",
    "sample_table_sizes = [50, 100, 250, 500, 750, 900]\n",
    "\n",
    "for i in range(0,len(sample_table_sizes)):\n",
    "    sample_table_size = sample_table_sizes[i]\n",
    "    sample_table = create_sample_table (sample_table_size, data)\n",
    "    MSE = 0\n",
    "    for c in range (0,sample_table.shape[1]):\n",
    "        num_Cat1_sample = 0\n",
    "        num_Cat1_actual = 0\n",
    "        for i in range (0, sample_table.shape[0]):\n",
    "            if (sample_table[i,c] <= .25):\n",
    "                num_Cat1_sample += 1\n",
    "        for i in range (0, data.shape[0]):\n",
    "            if (data[i,c] <= .25):\n",
    "                num_Cat1_actual += 1\n",
    "        sample = num_Cat1_sample/sample_table.shape[0]\n",
    "        actual = num_Cat1_actual/data.shape[0]\n",
    "        MSE += (actual-sample)**2\n",
    "    MSE = MSE/sample_table.shape[1]\n",
    "    sum_one_category_MSE.append(MSE)\n",
    "   \n",
    "plt.plot (sample_table_sizes, sum_one_category_MSE)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Second exploration: a quantile approximation algorithm \n",
    "#https://pdfs.semanticscholar.org/3593/8dc843cb7ce95be5007ec40e3967ab6bfae8.pdf\n",
    "def Agrawal_Swami_generic (X, k, p):\n",
    "    H = []\n",
    "    tau = p*len(X)\n",
    "    for x in X:\n",
    "        contains_x = False\n",
    "        for e_i in H:\n",
    "            if (e_i[0] == x):\n",
    "                e_i[1] += 1\n",
    "                contains_x = True\n",
    "                break\n",
    "        if (contains_x == False):     \n",
    "            if (len(H) < k):\n",
    "                if (len(H)==0):\n",
    "                    H.insert (0, [x,1])\n",
    "                else:\n",
    "                    #insert (x,1) maintaining sorted order\n",
    "                    append = True\n",
    "                    for i in (range(0,len(H))):\n",
    "                        if (H[i][0] > x):\n",
    "                            H.insert (i, [x, 1])\n",
    "                            append = False\n",
    "                            break      \n",
    "                    if (append):\n",
    "                        H.append ([x,1])\n",
    "            elif (x < H[0][0]):\n",
    "                N_1_H = np.sum([entry[1] for entry in H])\n",
    "                if (N_1_H < tau):\n",
    "                    H[len(H)-2][1] = H[len(H)-2][1] + H[len(H)-1][1]\n",
    "                    del H[len(H)-1]\n",
    "                    #insert (x,1)\n",
    "                    append = True\n",
    "                    for i in (range(0,len(H))):\n",
    "                        if (H[i][0] > x):\n",
    "                            H.insert (i, [x, 1])\n",
    "                            append = False\n",
    "                            break\n",
    "                    if (append):\n",
    "                        H.append ([x,1])\n",
    "            else:\n",
    "                for i in range(0,len(H)-1):\n",
    "                    if (H[len(H)-1-i][0]<x):\n",
    "                        H[len(H)-1-i][1] += 1\n",
    "                        break\n",
    "        N_2_H = np.sum([entry[1] for entry in H[1:]])\n",
    "        if(N_2_H>=tau):\n",
    "            del H[0]\n",
    "    return H[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#test on some examples with relative error\n",
    "X = np.random.randint (0, 1000, (1,100000))[0]\n",
    "k_sizes = [10, 50, 100, 250, 500]\n",
    "p_vals = [.5]\n",
    "for p in p_vals:\n",
    "    relative_errors = []\n",
    "    for k in k_sizes:\n",
    "        approximate_median = Agrawal_Swami_generic(X, k, p)\n",
    "        median = np.median(X)\n",
    "        relative_error = abs(approximate_median-median)/approximate_median\n",
    "        relative_errors.append(relative_error)\n",
    "    print (\"p_val: \")\n",
    "    print (p)\n",
    "    plt.plot(k_sizes, relative_errors)\n",
    "    plt.pause(0.05)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Another quantile summary: http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf\n",
    "#this is an e-quantile summary\n",
    "X = np.random.randint (0, 1000, (1,100000))[0]\n",
    "\n",
    "#an ordered sequence of tuples which correspond to a subset of the observations seen thus far\n",
    "summary_structure = []\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Pseudocode\n",
    "def GK_summary (data, e, S):\n",
    "    for n in range (0,len(data)):\n",
    "        if (n%(1/2e) == 0):\n",
    "            compress(S)\n",
    "        insert(data[n]) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quantile (q, e, data):\n",
    "    n = len(data) \n",
    "    #load t_i into T\n",
    "    s=0\n",
    "    S = tree with just root node R\n",
    "    GK_summary(data, e, S):\n",
    "    r = ceiling (q*n)\n",
    "    find i s/t both (r-r_min(v_i))<=e*n and (r_max(v_i)-r)<=e*n\n",
    "    return v_i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert (v)\n",
    "    find the smallest i s/t v_(i-1) <= v < v_i\n",
    "    insert tuple (v, 1, floor(2*e*n)) between t_(i-1) and t_i\n",
    "    if (v = min or max seen):\n",
    "        insert (v, 1, 0)\n",
    "    else:\n",
    "\n",
    "    s +=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def delete (v_i, v_(i+1)):\n",
    "    replace (v_i, g_i, delta_i) and (v_(i+1),g_(i+), delta_(i+1) with \n",
    "                                     new (v_(i+1),g_i + g_(i+), delta_(i+1))\n",
    "    s=s-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compress(delta_t, e, n, ):\n",
    "    for i in range (s-2,0):\n",
    "        if (band(delta_i,2*e*n)<= band (delta_(i+1), 2*e*n) and (g_i_star + g_(i+1) + delta _(i_1))<2*e*n )\n",
    "            delete all descendents of t_i and t_i"
   ]
  }
 ],
 "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
}