sequence_rule_mining.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sequential Rule Mining Using SPMF\n",
    "\n",
    "This practical note introduces you to sequential rule mining using SPMF. SPMF is a Java library implemented by Philippe Fournier Viger containing 150 pattern mining algorithms, such as frequent pattern mining, association rules, frequent sequences and of course, sequential rule mining. We will use SPMF as there are no mature library in Python that implement sequential rule mining to the extend of SPMF.\n",
    "\n",
    "You can find information about SPMF here http://www.philippe-fournier-viger.com/spmf/index.php and you can download SPMF here http://www.philippe-fournier-viger.com/spmf/index.php?link=download.php. Put the `spmf.jar` file into the same directory with this Jupyter notebook.\n",
    "\n",
    "As SPMF is implemented in Java, you need to install Java to run the `.jar` file. We will not discuss how to do that, there are many tutorials on the Internet. To check if you have installed Java correctly for this practical, open your terminal/CMD and type `java`.\n",
    "\n",
    "To demonstrate how to use SPMF through Python, we will use the `bank.csv` dataset used in the past practical. Import it through pandas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>ACCOUNT</th>\n",
       "      <th>SERVICE</th>\n",
       "      <th>VISIT</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>500026</td>\n",
       "      <td>CKING</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>500026</td>\n",
       "      <td>SVG</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>500026</td>\n",
       "      <td>ATM</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>500026</td>\n",
       "      <td>ATM</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>500075</td>\n",
       "      <td>CKING</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>500075</td>\n",
       "      <td>MMDA</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>500075</td>\n",
       "      <td>SVG</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>500075</td>\n",
       "      <td>ATM</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>500075</td>\n",
       "      <td>TRUST</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>500075</td>\n",
       "      <td>TRUST</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   ACCOUNT SERVICE  VISIT\n",
       "0   500026   CKING      1\n",
       "1   500026     SVG      2\n",
       "2   500026     ATM      3\n",
       "3   500026     ATM      4\n",
       "4   500075   CKING      1\n",
       "5   500075    MMDA      2\n",
       "6   500075     SVG      3\n",
       "7   500075     ATM      4\n",
       "8   500075   TRUST      5\n",
       "9   500075   TRUST      6"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "df = pd.read_csv('datasets/bank.csv')\n",
    "\n",
    "df.head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Different from association mining, to get sequential rules, there must be information of order of the target. In this dataset, the order is given in `VISIT` column. As this dataset is already ordered by `VISIT`, simple group and apply list will produce sequences in order. In other datasets, you will have to perform some preprocessing to ensure this ordering is correct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['CKING', 'SVG', 'ATM', 'ATM'], ['CKING', 'MMDA', 'SVG', 'ATM', 'TRUST', 'TRUST'], ['CKING', 'SVG', 'IRA', 'ATM', 'ATM'], ['CKING', 'SVG', 'CKCRD', 'CKCRD'], ['CKING', 'SVG', 'CKCRD', 'CKCRD']]\n"
     ]
    }
   ],
   "source": [
    "transactions = df.groupby(['ACCOUNT'])['SERVICE'].apply(list)\n",
    "sequences = transactions.values.tolist()\n",
    "\n",
    "# show the first 5 sequences\n",
    "print(sequences[:5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once you have sequences ordered correctly, you could simply run the following function to get sequential rules and their respective support and confidence. In general, the function below will write your sequences into a file called `seq_rule_input.txt` in SPMF accepted format, run SPMF to generate sequential rules, read the output file and return a Pandas dataframe. Detailed comments is provided in the function source code."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "import subprocess\n",
    "import re\n",
    "\n",
    "''' Uses SPMF to find association rules in supplied transactions '''\n",
    "def get_association_rules(sequences, min_sup, min_conf):\n",
    "    # step 1: create required input for SPMF\n",
    "    \n",
    "    # prepare a dict to uniquely assign each item in the transactions to an int ID\n",
    "    item_dict = defaultdict(int)\n",
    "    output_dict = defaultdict(str)\n",
    "    item_id = 1\n",
    "    \n",
    "    # write your sequences in SPMF format\n",
    "    with open('seq_rule_input.txt', 'w+') as f:\n",
    "        for sequence in sequences:\n",
    "            z = []\n",
    "            for itemset in sequence:\n",
    "                # if there are multiple items in one itemset\n",
    "                if isinstance(itemset, list):\n",
    "                    for item in itemset:\n",
    "                        if item not in item_dict:\n",
    "                            item_dict[item] = item_id\n",
    "                            item_id += 1\n",
    "\n",
    "                        z.append(item_dict[item])\n",
    "                else:\n",
    "                    if itemset not in item_dict:\n",
    "                        item_dict[itemset] = item_id\n",
    "                        output_dict[str(item_id)] = itemset\n",
    "                        item_id += 1\n",
    "                    z.append(item_dict[itemset])\n",
    "                    \n",
    "                # end of itemset\n",
    "                z.append(-1)\n",
    "            \n",
    "            # end of a sequence\n",
    "            z.append(-2)\n",
    "            f.write(' '.join([str(x) for x in z]))\n",
    "            f.write('\\n')\n",
    "    \n",
    "    # run SPMF with supplied parameters\n",
    "    supp_param = '{}%'.format(int(min_sup * 100))\n",
    "    conf_param = '{}%'.format(int(min_conf * 100))\n",
    "    subprocess.call(['java', '-jar', 'spmf.jar', 'run', 'RuleGrowth', 'seq_rule_input.txt', 'seq_rule_output.txt', '10%', '10%'], shell=True)\n",
    "    \n",
    "    # read back the output rules\n",
    "    outputs = open('seq_rule_output.txt', 'r').read().strip().split('\\n')\n",
    "    output_rules = []\n",
    "    for rule in outputs:\n",
    "        left, right, sup, conf = re.search(pattern=r'([0-9\\,]+) ==> ([0-9\\,]+) #SUP: ([0-9]+) #CONF: ([0-9\\.]+)', string=rule).groups()\n",
    "        sup = int(sup) / len(sequences)\n",
    "        conf = float(conf)\n",
    "        output_rules.append([[output_dict[x] for x in left.split(',')], [output_dict[x] for x in right.split(',')], sup, conf])\n",
    "    \n",
    "    # return pandas DataFrame\n",
    "    return pd.DataFrame(output_rules, columns = ['Left_rule', 'Right_rule', 'Support', 'Confidence'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can run the function on sequences from the `bank.csv` dataset using the command below. In here, we are using `min_supp` of 0.1 and `min_conf` of 0.1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Left_rule</th>\n",
       "      <th>Right_rule</th>\n",
       "      <th>Support</th>\n",
       "      <th>Confidence</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>[CKING]</td>\n",
       "      <td>[SVG]</td>\n",
       "      <td>0.541734</td>\n",
       "      <td>0.631510</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>[CKING]</td>\n",
       "      <td>[SVG, ATM]</td>\n",
       "      <td>0.248530</td>\n",
       "      <td>0.289716</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>[CKING]</td>\n",
       "      <td>[SVG, CD]</td>\n",
       "      <td>0.142535</td>\n",
       "      <td>0.166156</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>[CKING]</td>\n",
       "      <td>[SVG, HMEQLC]</td>\n",
       "      <td>0.111500</td>\n",
       "      <td>0.129978</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>[CKING]</td>\n",
       "      <td>[ATM]</td>\n",
       "      <td>0.361907</td>\n",
       "      <td>0.421882</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>[CKING, SVG]</td>\n",
       "      <td>[ATM]</td>\n",
       "      <td>0.248530</td>\n",
       "      <td>0.458766</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>[CKING]</td>\n",
       "      <td>[MMDA]</td>\n",
       "      <td>0.155800</td>\n",
       "      <td>0.181619</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>[CKING]</td>\n",
       "      <td>[CKCRD]</td>\n",
       "      <td>0.113002</td>\n",
       "      <td>0.131729</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>[CKING]</td>\n",
       "      <td>[CD]</td>\n",
       "      <td>0.209861</td>\n",
       "      <td>0.244639</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>[CKING, SVG]</td>\n",
       "      <td>[CD]</td>\n",
       "      <td>0.142535</td>\n",
       "      <td>0.263109</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>[CKING]</td>\n",
       "      <td>[CCRD]</td>\n",
       "      <td>0.148542</td>\n",
       "      <td>0.173158</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>[CKING]</td>\n",
       "      <td>[HMEQLC]</td>\n",
       "      <td>0.164685</td>\n",
       "      <td>0.191977</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>[CKING, SVG]</td>\n",
       "      <td>[HMEQLC]</td>\n",
       "      <td>0.111500</td>\n",
       "      <td>0.205821</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>[SVG]</td>\n",
       "      <td>[ATM]</td>\n",
       "      <td>0.256914</td>\n",
       "      <td>0.415251</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>[SVG]</td>\n",
       "      <td>[CD]</td>\n",
       "      <td>0.157177</td>\n",
       "      <td>0.254045</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>15</th>\n",
       "      <td>[SVG]</td>\n",
       "      <td>[CCRD]</td>\n",
       "      <td>0.102240</td>\n",
       "      <td>0.165251</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>[SVG]</td>\n",
       "      <td>[HMEQLC]</td>\n",
       "      <td>0.111500</td>\n",
       "      <td>0.180218</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       Left_rule     Right_rule   Support  Confidence\n",
       "0        [CKING]          [SVG]  0.541734    0.631510\n",
       "1        [CKING]     [SVG, ATM]  0.248530    0.289716\n",
       "2        [CKING]      [SVG, CD]  0.142535    0.166156\n",
       "3        [CKING]  [SVG, HMEQLC]  0.111500    0.129978\n",
       "4        [CKING]          [ATM]  0.361907    0.421882\n",
       "5   [CKING, SVG]          [ATM]  0.248530    0.458766\n",
       "6        [CKING]         [MMDA]  0.155800    0.181619\n",
       "7        [CKING]        [CKCRD]  0.113002    0.131729\n",
       "8        [CKING]           [CD]  0.209861    0.244639\n",
       "9   [CKING, SVG]           [CD]  0.142535    0.263109\n",
       "10       [CKING]         [CCRD]  0.148542    0.173158\n",
       "11       [CKING]       [HMEQLC]  0.164685    0.191977\n",
       "12  [CKING, SVG]       [HMEQLC]  0.111500    0.205821\n",
       "13         [SVG]          [ATM]  0.256914    0.415251\n",
       "14         [SVG]           [CD]  0.157177    0.254045\n",
       "15         [SVG]         [CCRD]  0.102240    0.165251\n",
       "16         [SVG]       [HMEQLC]  0.111500    0.180218"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_association_rules(sequences, 0.1, 0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first rule is `CKING` => `SVG` for 0.54 support and 0.63 confidence. This is a strong rule, as it implies 54% of customers bought `SVG` after `CKING` (support) and if customer bought `CKING`, the probability of them buying `SVG` after is 63%.\n",
    "\n",
    "You can now use the function to perform web log mining in the assignment."
   ]
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}