Course4_assignment3_FreqItems_Heikel.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import itertools\n",
    "from time import time\n",
    "import itertools\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.read_csv('groceries.csv', sep='delimiter', header=None, engine='python')\n",
    "l = [m.values[0].split(',') for ii, m in df.iterrows()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prepdata(l,k=2,  report=False):\n",
    "    C_k = []\n",
    "    b = 0\n",
    "    \n",
    "    pairs = []\n",
    "    for line in l:\n",
    "        for c in itertools.combinations(line, k):\n",
    "            yield frozenset(c)\n",
    "\n",
    "        C_k = []\n",
    "        # report progress\n",
    "        # print every 1000th element to reduce clutter\n",
    "        if report:\n",
    "            if b % 1000 == 0:  \n",
    "                print('processing bin ', b)\n",
    "            b += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "frozenset({'semi-finished bread', 'citrus fruit'})\n",
      "frozenset({'margarine', 'citrus fruit'})\n",
      "frozenset({'ready soups', 'citrus fruit'})\n",
      "frozenset({'margarine', 'semi-finished bread'})\n",
      "frozenset({'ready soups', 'semi-finished bread'})\n",
      "frozenset({'ready soups', 'margarine'})\n",
      "frozenset({'tropical fruit', 'yogurt'})\n",
      "frozenset({'tropical fruit', 'coffee'})\n",
      "frozenset({'yogurt', 'coffee'})\n",
      "frozenset({'yogurt', 'pip fruit'})\n",
      "frozenset({'pip fruit', 'cream cheese'})\n",
      "frozenset({'pip fruit', 'meat spreads'})\n",
      "frozenset({'yogurt', 'cream cheese'})\n",
      "frozenset({'yogurt', 'meat spreads'})\n",
      "frozenset({'meat spreads', 'cream cheese'})\n",
      "frozenset({'whole milk', 'other vegetables'})\n",
      "frozenset({'condensed milk', 'other vegetables'})\n",
      "frozenset({'long life bakery product', 'other vegetables'})\n",
      "frozenset({'condensed milk', 'whole milk'})\n",
      "frozenset({'whole milk', 'long life bakery product'})\n"
     ]
    }
   ],
   "source": [
    "nitems = 20\n",
    "for C_k in prepdata(l):\n",
    "    print(C_k)\n",
    "    \n",
    "    nitems -= 1\n",
    "    if nitems == 0: \n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2981 items with >10 occurances which took 0.19280409812927246 seconds\n",
      "605 items with >50 occurances which took 0.146162748336792 seconds\n",
      "207 items with >100 occurances which took 0.14271783828735352 seconds\n"
     ]
    }
   ],
   "source": [
    "# Naive Approach\n",
    "for s in [10, 50, 100]: # support threshold\n",
    "    t = time()\n",
    "    \n",
    "    C2 = {}\n",
    "    for key in prepdata(l, k=2):\n",
    "        if key not in C2:\n",
    "            C2[key] = 1\n",
    "        else:\n",
    "            C2[key] += 1\n",
    "            \n",
    "    L2 = {}\n",
    "    for key, n in C2.items():\n",
    "        if n >= s:\n",
    "            L2[key] = n\n",
    "    t2 = time()\n",
    "    print('{} items with >{} occurances which took {} seconds'.format(len(L2), s, t2-t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see an improvement in time the stronger the filter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "207 items with >10 occurances which took 0.34893083572387695 seconds\n",
      "207 items with >50 occurances which took 0.21812891960144043 seconds\n",
      "207 items with >100 occurances which took 0.20238089561462402 seconds\n"
     ]
    }
   ],
   "source": [
    "# Apriori\n",
    "\n",
    "for s in [10, 50, 100]:\n",
    "    t = time()\n",
    "    # find frequent 1-tuples (individual items)\n",
    "    C1 = {}\n",
    "    for key in prepdata(l, k=1, report=False):\n",
    "        if key not in C1:\n",
    "            C1[key] = 1\n",
    "        else:\n",
    "            C1[key] += 1    \n",
    "\n",
    "    #print(\"{} items\".format(len(C1)))\n",
    "\n",
    "    # filter stage\n",
    "    L1 = {}\n",
    "    for key, count in C1.items():\n",
    "        if count >= s:\n",
    "            L1[key] = count\n",
    "\n",
    "    C2_items = set([a.union(b) for a in L1.keys() for b in L1.keys()]) # List comprehensions in python\n",
    "\n",
    "    # find frequent 2-tuples\n",
    "    C2 = {}\n",
    "    for key in prepdata(l, k=2):\n",
    "        # filter out non-frequent tuples\n",
    "        if key not in C2_items:\n",
    "            continue\n",
    "\n",
    "        # record frequent tuples\n",
    "        if key not in C2:\n",
    "            C2[key] = 1\n",
    "        else:\n",
    "            C2[key] += 1\n",
    "    t2 = time()\n",
    "    print('{} items with >{} occurances which took {} seconds'.format(len(L2), s, t2-t))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see an improvement in time for higher thresholds. While initially slower than naive, improvements in time are more drastic using a priori"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1346"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(5*1000000-673) - (5*1000000+673)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def run_hash(x=1, N=100, k=2):\n",
    "    '''x=1 means that there are 2 hash tables, 0 based index'''\n",
    "    t = time()\n",
    "    mx_hash = [5*1000000-673,\n",
    "               5*1000000+673, \n",
    "               5*1000000+673+1346, \n",
    "               5*(1000000+673*5),  \n",
    "               5*(1000000+673*7)]\n",
    "    \n",
    "    hash_dict = {'max_hash':  mx_hash,\n",
    "          'H': [np.zeros((h,), dtype=np.int) for h in mx_hash],\n",
    "         'hash_cell':[]}\n",
    "\n",
    "    for key in prepdata(l, k=k):\n",
    "        for y in range(x):\n",
    "            hash_dict['hash_cell'].append(hash(key) % hash_dict['max_hash'][y])\n",
    "            hash_dict['hash_cell'][y] += 1\n",
    "\n",
    "    H_good = [set(np.where(hash_dict['H'][n] >= N)[0]) for n in range(x)]\n",
    "    hash_dict.pop('H')\n",
    "\n",
    "    C2 = {}\n",
    "    for key in prepdata(l, k=k):\n",
    "        for y in range(x):\n",
    "            hash_dict['hash_cell'].append(hash(key) % hash_dict['max_hash'][y])\n",
    "            if hash_dict['hash_cell'][y] not in H_good[y]:\n",
    "                continue\n",
    "\n",
    "        # record frequent tuples\n",
    "        if key not in C2:\n",
    "            C2[key] = 1\n",
    "        else:\n",
    "            C2[key] += 1\n",
    "\n",
    "\n",
    "    # filter stage\n",
    "    L2 = {}\n",
    "    for key, count in C2.items():\n",
    "        if count >= N:\n",
    "            L2[key] = count\n",
    "    t2 = time()\n",
    "    print('With {} tables and k={}: found {} items with >{} occurances and took {} seconds'.format(x+1,k,  len(L2), N, t2-t))\n",
    "    \n",
    "    return L2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "With 2 tables and k=2: found 2981 items with >10 occurances and took 0.4437587261199951 seconds\n",
      "With 2 tables and k=2: found 605 items with >50 occurances and took 0.43692612648010254 seconds\n",
      "With 2 tables and k=2: found 207 items with >100 occurances and took 0.47879695892333984 seconds\n"
     ]
    }
   ],
   "source": [
    "for N in [10, 50, 100]:\n",
    "    run_hash(N=N)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Wit an increasing threshold (S) the number of item sets decreased, there was also a marginal decrease in time required."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "With 1 tables and k=2: found 207 items with >100 occurances and took 0.27523303031921387 seconds\n",
      "With 2 tables and k=2: found 207 items with >100 occurances and took 0.4901449680328369 seconds\n",
      "With 3 tables and k=2: found 207 items with >100 occurances and took 0.6596391201019287 seconds\n",
      "With 4 tables and k=2: found 207 items with >100 occurances and took 0.7746970653533936 seconds\n",
      "With 5 tables and k=2: found 207 items with >100 occurances and took 0.9956839084625244 seconds\n"
     ]
    }
   ],
   "source": [
    "for x in range(5):\n",
    "    run_hash(x=x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With more tables the time increased (became slower) but performance did not change."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "With 2 tables and k=3: found 6831 items with >10 occurances and took 1.500154972076416 seconds\n",
      "With 2 tables and k=4: found 3137 items with >10 occurances and took 5.2792885303497314 seconds\n",
      "With 2 tables and k=5: found 376 items with >10 occurances and took 18.97327160835266 seconds\n"
     ]
    }
   ],
   "source": [
    "for k in [3, 4, 5]:\n",
    "    run_hash(k=k, N=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obviously, with increased k fewer items were found and the analysis took exponentially longer. There are occurances with k=5 but at very low frequencies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1-NN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "With 2 tables and k=4: found 12 items with >50 occurances and took 4.1445770263671875 seconds\n"
     ]
    }
   ],
   "source": [
    "results = run_hash(k=4, N=50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "dict_res = {}\n",
    "for comb in list(results.keys()):\n",
    "    a = np.array(list(comb))\n",
    "    a.sort()\n",
    "    for item in a:\n",
    "        if item not in dict_res:\n",
    "            dict_res[item] = []\n",
    "            dict_res[item].append(list(a[a!=item]))\n",
    "            continue\n",
    "            \n",
    "        if list(a[a!=item]) not in dict_res[item]:\n",
    "                dict_res[item].append(list(a[a!=item]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "root vegetables:\n",
      "\n",
      "[['tropical fruit', 'whole milk', 'yogurt'], ['other vegetables', 'whole milk', 'yogurt'], ['other vegetables', 'tropical fruit', 'whole milk'], ['other vegetables', 'pip fruit', 'whole milk'], ['other vegetables', 'whipped/sour cream', 'whole milk'], ['other vegetables', 'rolls/buns', 'whole milk'], ['citrus fruit', 'other vegetables', 'whole milk']]\n",
      "\n",
      "tropical fruit:\n",
      "\n",
      "[['root vegetables', 'whole milk', 'yogurt'], ['other vegetables', 'root vegetables', 'whole milk'], ['other vegetables', 'whole milk', 'yogurt']]\n",
      "\n",
      "whole milk:\n",
      "\n",
      "[['root vegetables', 'tropical fruit', 'yogurt'], ['other vegetables', 'root vegetables', 'yogurt'], ['fruit/vegetable juice', 'other vegetables', 'yogurt'], ['other vegetables', 'root vegetables', 'tropical fruit'], ['other vegetables', 'tropical fruit', 'yogurt'], ['other vegetables', 'pip fruit', 'root vegetables'], ['other vegetables', 'pip fruit', 'yogurt'], ['other vegetables', 'root vegetables', 'whipped/sour cream'], ['other vegetables', 'whipped/sour cream', 'yogurt'], ['other vegetables', 'rolls/buns', 'root vegetables'], ['other vegetables', 'rolls/buns', 'yogurt'], ['citrus fruit', 'other vegetables', 'root vegetables']]\n",
      "\n",
      "yogurt:\n",
      "\n",
      "[['root vegetables', 'tropical fruit', 'whole milk'], ['other vegetables', 'root vegetables', 'whole milk'], ['fruit/vegetable juice', 'other vegetables', 'whole milk'], ['other vegetables', 'tropical fruit', 'whole milk'], ['other vegetables', 'pip fruit', 'whole milk'], ['other vegetables', 'whipped/sour cream', 'whole milk'], ['other vegetables', 'rolls/buns', 'whole milk']]\n",
      "\n",
      "other vegetables:\n",
      "\n",
      "[['root vegetables', 'whole milk', 'yogurt'], ['fruit/vegetable juice', 'whole milk', 'yogurt'], ['root vegetables', 'tropical fruit', 'whole milk'], ['tropical fruit', 'whole milk', 'yogurt'], ['pip fruit', 'root vegetables', 'whole milk'], ['pip fruit', 'whole milk', 'yogurt'], ['root vegetables', 'whipped/sour cream', 'whole milk'], ['whipped/sour cream', 'whole milk', 'yogurt'], ['rolls/buns', 'root vegetables', 'whole milk'], ['rolls/buns', 'whole milk', 'yogurt'], ['citrus fruit', 'root vegetables', 'whole milk']]\n",
      "\n",
      "fruit/vegetable juice:\n",
      "\n",
      "[['other vegetables', 'whole milk', 'yogurt']]\n",
      "\n",
      "pip fruit:\n",
      "\n",
      "[['other vegetables', 'root vegetables', 'whole milk'], ['other vegetables', 'whole milk', 'yogurt']]\n",
      "\n",
      "whipped/sour cream:\n",
      "\n",
      "[['other vegetables', 'root vegetables', 'whole milk'], ['other vegetables', 'whole milk', 'yogurt']]\n",
      "\n",
      "rolls/buns:\n",
      "\n",
      "[['other vegetables', 'root vegetables', 'whole milk'], ['other vegetables', 'whole milk', 'yogurt']]\n",
      "\n",
      "citrus fruit:\n",
      "\n",
      "[['other vegetables', 'root vegetables', 'whole milk']]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for key in dict_res:\n",
    "    print(f'{key}:')\n",
    "    print()\n",
    "    print(dict_res[key])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I did approach with various Ks and thresholds, I decided to focus on K=4 and a threshold of 50 as it is easy to digest the outcome. Looking at the items shown in the 1-NN seem to largely consist of staple foods. These would likely be of little interest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[('whole milk', 2513),\n",
       " ('other vegetables', 1903),\n",
       " ('rolls/buns', 1809),\n",
       " ('soda', 1715),\n",
       " ('yogurt', 1372),\n",
       " ('bottled water', 1087),\n",
       " ('root vegetables', 1072),\n",
       " ('tropical fruit', 1032),\n",
       " ('shopping bags', 969),\n",
       " ('sausage', 924),\n",
       " ('pastry', 875),\n",
       " ('citrus fruit', 814),\n",
       " ('bottled beer', 792),\n",
       " ('newspapers', 785),\n",
       " ('canned beer', 764),\n",
       " ('pip fruit', 744),\n",
       " ('fruit/vegetable juice', 711),\n",
       " ('whipped/sour cream', 705),\n",
       " ('brown bread', 638),\n",
       " ('domestic eggs', 624)]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C = []\n",
    "for key in prepdata(l, k=1):\n",
    "    C.append(list(key)[0])\n",
    "from collections import Counter\n",
    "Counter(C).most_common(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Indeed, all of the item sets observed are found in a list of the 20 most common items (out of 169 unique items), which means that they are probably not of much interest as sets considering that their occurances are high otherwise."
   ]
  },
  {
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}