CS583_Proj1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CS 583 Project 1\n",
    "\n",
    "### Fangda Fan, Xiaohan Liu\n",
    "\n",
    "- Implement: MS-Apriori (excluding rule generation)\n",
    "- Consider: multiple minimum supports, support difference constraint, and item constraints\n",
    "- Item constraints: Two types\n",
    "    - Cannot–be-together: sets of items cannot be in the same itemsets (pairwise), \n",
    "        - e.g., {1, 2, 3} and {6, 7, 9, 10}\n",
    "    - Must-have: every itemset must have, \n",
    "        - e.g., (1 or 2)\n",
    "- Deadline: Feb 9, 2017 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import scipy.sparse as sp\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Read Data and Arguments"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read Arguments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def input_args(file_args):\n",
    "    ms_i = []\n",
    "    ms_val = []\n",
    "    sdc = 1\n",
    "    x_cannot = []\n",
    "    x_must = []\n",
    "    for i in open(file_args, \"r\"):\n",
    "        i = i.rstrip(\"\\n\")\n",
    "        if i.startswith(\"MIS\"):\n",
    "            j = i.split(\" = \")\n",
    "            ms_i.append(j[0][4:-1])\n",
    "            ms_val.append(float(j[1]))\n",
    "        elif i.startswith(\"SDC\"):\n",
    "            sdc = float(i.split(\"=\")[1])\n",
    "        elif i.startswith(\"cannot_be_together\"):\n",
    "            x_cannot = [j.split(\", \") for j in i.split(\": \")[1][1:-1].split(\"}, {\")]\n",
    "        elif i.startswith(\"must\"):\n",
    "            x_must = [j for j in i.split(\": \")[1].split(\" or \")]\n",
    "    ms_sort = np.argsort(ms_val)\n",
    "    op = {\"ms_i\": np.array(ms_i)[ms_sort], \"ms_val\": np.array(ms_val)[ms_sort], \"sdc\": sdc, \"x_cannot\": x_cannot, \"x_must\": x_must}\n",
    "    return(op)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'ms_i': array(['30', '40', '20', '140', '90', '100', '60', '120', '70', '80', '50',\n",
       "        '10'], \n",
       "       dtype='<U3'),\n",
       " 'ms_val': array([ 0.02,  0.09,  0.12,  0.13,  0.16,  0.19,  0.23,  0.24,  0.27,\n",
       "         0.54,  0.62,  0.8 ]),\n",
       " 'sdc': 0.05,\n",
       " 'x_cannot': [['30', '60'], ['10', '30'], ['100', '20'], ['10', '30', '40']],\n",
       " 'x_must': ['10', '20', '30', '80', '120']}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "file_args = \"proj1_parameter-file_2.txt\"\n",
    "file_data = \"proj1_input-data_2.txt\"\n",
    "\n",
    "args = input_args(file_args)\n",
    "args"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Index-item dictionary: ['30' '40' '20' '140' '90' '100' '60' '120' '70' '80' '50' '10']\n",
      "MIS index [ 0.02  0.09  0.12  0.13  0.16  0.19  0.23  0.24  0.27  0.54  0.62  0.8 ]\n",
      "Cannot-be-Together index: [(0, 6), (0, 11), (2, 5), (0, 1, 11)]\n",
      "Must-have: [11, 2, 0, 9, 7]\n"
     ]
    }
   ],
   "source": [
    "id_dict = {i[1]: i[0] for i in enumerate(args[\"ms_i\"])}\n",
    "x_must = [id_dict[i] for i in args[\"x_must\"]]\n",
    "x_cannot = [tuple(np.sort([id_dict[j] for j in i])) for i in args[\"x_cannot\"]]\n",
    "print(\"Index-item dictionary:\", args[\"ms_i\"])\n",
    "print(\"MIS index\", args[\"ms_val\"])\n",
    "print(\"Cannot-be-Together index:\",  x_cannot)\n",
    "print(\"Must-have:\", x_must)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read Transaction Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def input_data(file_data, columns):\n",
    "    s = pd.read_csv(file_data, header = None, sep = \"\\t\",squeeze = True)\n",
    "    op = s.str.strip(\"{} \").str.get_dummies(sep = \", \").reindex(columns = columns, fill_value = 0)\n",
    "    return(op)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>30</th>\n",
       "      <th>40</th>\n",
       "      <th>20</th>\n",
       "      <th>140</th>\n",
       "      <th>90</th>\n",
       "      <th>100</th>\n",
       "      <th>60</th>\n",
       "      <th>120</th>\n",
       "      <th>70</th>\n",
       "      <th>80</th>\n",
       "      <th>50</th>\n",
       "      <th>10</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>17</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>18</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>19</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>20</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>21</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    30  40  20  140  90  100  60  120  70  80  50  10\n",
       "0    1   0   1    0   1    0   0    0   1   1   1   0\n",
       "1    0   0   1    0   0    0   0    0   1   1   0   1\n",
       "2    0   0   1    0   0    0   0    0   0   1   0   1\n",
       "3    1   0   1    0   0    0   0    0   0   1   0   0\n",
       "4    0   0   1    0   0    0   0    0   0   1   0   0\n",
       "5    1   0   1    1   1    1   0    1   1   1   1   0\n",
       "6    1   0   1    0   1    0   0    0   0   1   0   0\n",
       "7    0   0   1    0   0    0   0    0   1   1   0   1\n",
       "8    0   0   1    1   0    0   0    1   0   0   0   1\n",
       "9    0   1   0    0   0    0   1    0   1   0   0   1\n",
       "10   0   0   1    0   1    1   0    0   0   0   0   0\n",
       "11   0   0   1    1   1    0   0    1   1   0   0   0\n",
       "12   0   0   0    1   0    1   1    1   0   0   0   1\n",
       "13   1   0   0    1   0    1   0    1   1   1   0   0\n",
       "14   1   1   1    0   0    0   1    0   0   0   1   1\n",
       "15   0   0   0    1   1    1   0    0   0   0   0   0\n",
       "16   1   0   0    1   0    1   1    0   0   0   0   0\n",
       "17   0   0   0    0   1    1   0    1   0   1   0   0\n",
       "18   0   0   0    0   0    1   0    1   0   0   0   0\n",
       "19   0   0   0    1   1    1   0    1   0   0   0   0\n",
       "20   1   0   0    1   0    1   0    1   0   0   1   0\n",
       "21   1   0   1    1   1    1   1    1   1   0   0   0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "da = input_data(file_data, args[\"ms_i\"])\n",
    "X = da.values\n",
    "da"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def sup(xL):\n",
    "    op = np.mean([X[:, i].all(axis = 1) for i in xL], axis = 1)\n",
    "    return(op)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([(0,), (1,), (2,), (3,), (4,), (5,), (6,), (7,), (8,), (9,), (10,), (11,)],\n",
       " {(0,): 0.40909090909090912,\n",
       "  (1,): 0.090909090909090912,\n",
       "  (2,): 0.59090909090909094,\n",
       "  (3,): 0.45454545454545453,\n",
       "  (4,): 0.40909090909090912,\n",
       "  (5,): 0.5,\n",
       "  (6,): 0.22727272727272727,\n",
       "  (7,): 0.45454545454545453,\n",
       "  (8,): 0.36363636363636365,\n",
       "  (9,): 0.45454545454545453,\n",
       "  (10,): 0.18181818181818182,\n",
       "  (11,): 0.31818181818181818})"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "I = [(i,) for i, ival in enumerate(args[\"ms_val\"])]\n",
    "Isup = sup(I)\n",
    "sup_dict = dict(zip(I, Isup))\n",
    "I, sup_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Candidate Generation\n",
    "### Level 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0,\n",
       " [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],\n",
       " [[(0,), (1,), (2,), (3,), (4,), (5,), (7,), (8,)]])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Li = (Isup >= args[\"ms_val\"]).argmax()\n",
    "L = [i for i in range(Li, len(args[\"ms_val\"])) if Isup[i] >= args[\"ms_val\"][Li]]\n",
    "F = [[(i,) for i in np.where(Isup >= args[\"ms_val\"])[0]]]\n",
    "Li, L, F"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Level $\\geq$ 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def pair_sup_mis(x):\n",
    "    x_t = x[:, np.newaxis]\n",
    "    x_sup = sup(x_t)\n",
    "    x_mis = [args[\"ms_val\"][i] for i in x]\n",
    "    x_sup_t = x_sup[:, np.newaxis]\n",
    "    iL = sp.coo_matrix(np.triu((x_sup_t >= x_mis).T & (np.abs(x_sup_t - x_sup) <= args[\"sdc\"]), 1)).nonzero()\n",
    "    op = list(zip(x[iL[0]], x[iL[1]]))\n",
    "    return(op)\n",
    "def frequent(xL):\n",
    "    op = []\n",
    "    if xL:\n",
    "        x_sup = sup(xL)\n",
    "        sup_dict.update(dict(zip(xL, x_sup)))\n",
    "        op += [xL[j] for j in np.where(x_sup >= [args[\"ms_val\"][i[0]] for i in xL])[0]]\n",
    "        xL_dropfirst = set(tuple(i[1:]) for i in xL)\n",
    "        sup_dict.update(dict(zip(xL_dropfirst, sup(xL_dropfirst))))\n",
    "    return(op)\n",
    "def append_set(xL, x_base):\n",
    "    op = []\n",
    "    if len(xL):\n",
    "        op += [tuple(i) for i in np.hstack([np.tile(x_base, (len(xL), 1)), xL])]\n",
    "    return(op)\n",
    "def prune_candidate(xL):\n",
    "    op = []\n",
    "    if xL:\n",
    "        op += [xL[l] for l in np.where(np.all([[any(set(k).issubset(j) for k in F[-1]) for j in np.delete(xL, i, axis = 1)] for i in range(1, len(xL[0]))], axis = 0))[0]]\n",
    "    return(op)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 3),\n",
       " (0, 4),\n",
       " (0, 7),\n",
       " (0, 8),\n",
       " (0, 9),\n",
       " (3, 4),\n",
       " (3, 5),\n",
       " (3, 7),\n",
       " (3, 9),\n",
       " (4, 7),\n",
       " (4, 8),\n",
       " (4, 9),\n",
       " (5, 7),\n",
       " (5, 9),\n",
       " (7, 9),\n",
       " (8, 11)]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C = [i for i in pair_sup_mis(np.array(L)) if i[0] in np.array(F[0]).T[0]]\n",
    "C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 3),\n",
       " (0, 4),\n",
       " (0, 7),\n",
       " (0, 8),\n",
       " (0, 9),\n",
       " (3, 4),\n",
       " (3, 5),\n",
       " (3, 7),\n",
       " (4, 7),\n",
       " (4, 8),\n",
       " (4, 9),\n",
       " (5, 7)]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F_last = frequent(C)\n",
    "F_last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(0,), (1,), (2,), (3,), (4,), (5,), (7,), (8,)],\n",
       " [(0, 3),\n",
       "  (0, 4),\n",
       "  (0, 7),\n",
       "  (0, 8),\n",
       "  (0, 9),\n",
       "  (3, 4),\n",
       "  (3, 5),\n",
       "  (3, 7),\n",
       "  (4, 7),\n",
       "  (4, 8),\n",
       "  (4, 9),\n",
       "  (5, 7)],\n",
       " [(0, 3, 4),\n",
       "  (0, 3, 7),\n",
       "  (0, 3, 9),\n",
       "  (0, 4, 7),\n",
       "  (0, 4, 8),\n",
       "  (0, 4, 9),\n",
       "  (0, 7, 9),\n",
       "  (3, 4, 7),\n",
       "  (3, 5, 7)],\n",
       " [(0, 3, 4, 7), (0, 3, 4, 9), (0, 3, 7, 9), (0, 4, 7, 9)],\n",
       " [(0, 3, 4, 7, 9)]]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "while F_last:\n",
    "    F.append(F_last)\n",
    "    Ls = pd.DataFrame(F[-1])\n",
    "    C = sum([append_set(pair_sup_mis(group.values), name) for name, group in Ls.groupby(list(range(len(F)-1)))[len(F)-1]], [])\n",
    "    C = prune_candidate(C)\n",
    "    F_last = frequent(C)\n",
    "F"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prune with Item Constraints"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[(0,), (2,), (7,)],\n",
       " [(0, 3), (0, 4), (0, 7), (0, 8), (0, 9), (3, 7), (4, 7), (4, 9), (5, 7)],\n",
       " [(0, 3, 4),\n",
       "  (0, 3, 7),\n",
       "  (0, 3, 9),\n",
       "  (0, 4, 7),\n",
       "  (0, 4, 8),\n",
       "  (0, 4, 9),\n",
       "  (0, 7, 9),\n",
       "  (3, 4, 7),\n",
       "  (3, 5, 7)],\n",
       " [(0, 3, 4, 7), (0, 3, 4, 9), (0, 3, 7, 9), (0, 4, 7, 9)],\n",
       " [(0, 3, 4, 7, 9)]]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F_prune = [[j for j in i if any(k in j for k in x_must) & ~any(set(k).issubset(j) for k in x_cannot)] for i in F]\n",
    "F_prune"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Item Supports for Association Rule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(0,): 0.40909090909090912,\n",
       " (0, 3): 0.22727272727272727,\n",
       " (0, 3, 4): 0.090909090909090912,\n",
       " (0, 3, 4, 7): 0.090909090909090912,\n",
       " (0, 3, 4, 7, 9): 0.045454545454545456,\n",
       " (0, 3, 4, 9): 0.045454545454545456,\n",
       " (0, 3, 7): 0.18181818181818182,\n",
       " (0, 3, 7, 9): 0.090909090909090912,\n",
       " (0, 3, 9): 0.090909090909090912,\n",
       " (0, 4): 0.18181818181818182,\n",
       " (0, 4, 7): 0.090909090909090912,\n",
       " (0, 4, 7, 9): 0.045454545454545456,\n",
       " (0, 4, 8): 0.13636363636363635,\n",
       " (0, 4, 9): 0.13636363636363635,\n",
       " (0, 7): 0.18181818181818182,\n",
       " (0, 7, 9): 0.090909090909090912,\n",
       " (0, 8): 0.18181818181818182,\n",
       " (0, 9): 0.22727272727272727,\n",
       " (1,): 0.090909090909090912,\n",
       " (2,): 0.59090909090909094,\n",
       " (3,): 0.45454545454545453,\n",
       " (3, 4): 0.22727272727272727,\n",
       " (3, 4, 7): 0.18181818181818182,\n",
       " (3, 4, 7, 9): 0.045454545454545456,\n",
       " (3, 4, 9): 0.045454545454545456,\n",
       " (3, 5): 0.36363636363636365,\n",
       " (3, 5, 7): 0.27272727272727271,\n",
       " (3, 7): 0.36363636363636365,\n",
       " (3, 7, 9): 0.090909090909090912,\n",
       " (3, 9): 0.090909090909090912,\n",
       " (4,): 0.40909090909090912,\n",
       " (4, 7): 0.22727272727272727,\n",
       " (4, 7, 9): 0.090909090909090912,\n",
       " (4, 8): 0.18181818181818182,\n",
       " (4, 9): 0.18181818181818182,\n",
       " (5,): 0.5,\n",
       " (5, 7): 0.36363636363636365,\n",
       " (5, 9): 0.13636363636363635,\n",
       " (6,): 0.22727272727272727,\n",
       " (7,): 0.45454545454545453,\n",
       " (7, 9): 0.13636363636363635,\n",
       " (8,): 0.36363636363636365,\n",
       " (8, 11): 0.13636363636363635,\n",
       " (9,): 0.45454545454545453,\n",
       " (10,): 0.18181818181818182,\n",
       " (11,): 0.31818181818181818}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sup_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Frequent 1-itemsets\n",
      "\n",
      "\t9 : {30}\n",
      "\t13 : {20}\n",
      "\t10 : {120}\n",
      "\n",
      "Total number of frequent 1-itemsets = 3\n",
      "\n",
      "\n",
      "Frequent 2-itemsets\n",
      "\n",
      "\t5 : {30, 140}\n",
      "Tailcount = 10\n",
      "\t4 : {30, 90}\n",
      "Tailcount = 9\n",
      "\t4 : {30, 120}\n",
      "Tailcount = 10\n",
      "\t4 : {30, 70}\n",
      "Tailcount = 8\n",
      "\t5 : {30, 80}\n",
      "Tailcount = 10\n",
      "\t8 : {140, 120}\n",
      "Tailcount = 10\n",
      "\t5 : {90, 120}\n",
      "Tailcount = 10\n",
      "\t4 : {90, 80}\n",
      "Tailcount = 10\n",
      "\t8 : {100, 120}\n",
      "Tailcount = 10\n",
      "\n",
      "Total number of frequent 2-itemsets = 9\n",
      "\n",
      "\n",
      "Frequent 3-itemsets\n",
      "\n",
      "\t2 : {30, 140, 90}\n",
      "Tailcount = 5\n",
      "\t4 : {30, 140, 120}\n",
      "Tailcount = 8\n",
      "\t2 : {30, 140, 80}\n",
      "Tailcount = 2\n",
      "\t2 : {30, 90, 120}\n",
      "Tailcount = 5\n",
      "\t3 : {30, 90, 70}\n",
      "Tailcount = 4\n",
      "\t3 : {30, 90, 80}\n",
      "Tailcount = 4\n",
      "\t2 : {30, 120, 80}\n",
      "Tailcount = 3\n",
      "\t4 : {140, 90, 120}\n",
      "Tailcount = 5\n",
      "\t6 : {140, 100, 120}\n",
      "Tailcount = 8\n",
      "\n",
      "Total number of frequent 3-itemsets = 9\n",
      "\n",
      "\n",
      "Frequent 4-itemsets\n",
      "\n",
      "\t2 : {30, 140, 90, 120}\n",
      "Tailcount = 4\n",
      "\t1 : {30, 140, 90, 80}\n",
      "Tailcount = 1\n",
      "\t2 : {30, 140, 120, 80}\n",
      "Tailcount = 2\n",
      "\t1 : {30, 90, 120, 80}\n",
      "Tailcount = 2\n",
      "\n",
      "Total number of frequent 4-itemsets = 4\n",
      "\n",
      "\n",
      "Frequent 5-itemsets\n",
      "\n",
      "\t1 : {30, 140, 90, 120, 80}\n",
      "Tailcount = 1\n",
      "\n",
      "Total number of frequent 5-itemsets = 1\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "def output_frequent(F):\n",
    "    op = []\n",
    "    ms_i_int = args[\"ms_i\"].astype(\"int\")\n",
    "    for i, ival in enumerate(F):\n",
    "        if ival:\n",
    "            op.append(\"Frequent {}-itemsets\\n\".format(i+1))\n",
    "            if i == 0:\n",
    "                op += [\"\\t{} : {}\".format(int(sup_dict[j]*len(X)), {ms_i_int[j]}) for j in ival]\n",
    "            else:\n",
    "                op += [\"\\t{} : {}\\nTailcount = {}\".format(int(sup_dict[j]*len(X)), list(ms_i_int[[j]]), int(sup_dict[j[1:]]*len(X))) for j in ival]\n",
    "            op.append(\"\\nTotal number of frequent {}-itemsets = {}\\n\\n\".format(i+1, len(ival)))\n",
    "    print(\"\\n\".join(op).replace(\"[\", \"{\").replace(\"]\", \"}\"))\n",
    "output_frequent(F_prune)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}