Apriori.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Reading and Preprocessing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "from itertools import combinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Specify the input file here \n",
    "File needs to be a **csv** of the following format:\n",
    "\n",
    "```\n",
    "item1, item2, item3, ... so on\n",
    " , t, ...\n",
    "t, t, t,...\n",
    "t, t, ...\n",
    "... so on...```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.read_csv(\"test1.csv\", low_memory=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>handphone</th>\n",
       "      <th>laptop</th>\n",
       "      <th>charger</th>\n",
       "      <th>powerbank</th>\n",
       "      <th>tablet</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>t</td>\n",
       "      <td>t</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>t</td>\n",
       "      <td>t</td>\n",
       "      <td>t</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>t</td>\n",
       "      <td>t</td>\n",
       "      <td>t</td>\n",
       "      <td>t</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>t</td>\n",
       "      <td>t</td>\n",
       "      <td>NaN</td>\n",
       "      <td>NaN</td>\n",
       "      <td>t</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>t</td>\n",
       "      <td>NaN</td>\n",
       "      <td>t</td>\n",
       "      <td>NaN</td>\n",
       "      <td>t</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  handphone laptop charger powerbank tablet\n",
       "0         t      t     NaN       NaN    NaN\n",
       "1         t      t       t       NaN    NaN\n",
       "2         t      t       t         t    NaN\n",
       "3         t      t     NaN       NaN      t\n",
       "4         t    NaN       t       NaN      t"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Indexing each item from the header of the data file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'handphone': 1, 'laptop': 2, 'charger': 3, 'powerbank': 4, 'tablet': 5}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_list = list(df.columns)\n",
    "item_dict = dict()\n",
    "\n",
    "for i, item in enumerate(item_list):\n",
    "    item_dict[item] = i + 1\n",
    "\n",
    "item_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extracting the transactions from the data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{1, 2},\n",
       " {1, 2, 3},\n",
       " {1, 2, 3, 4},\n",
       " {1, 2, 5},\n",
       " {1, 3, 5},\n",
       " {4, 5},\n",
       " {1, 2, 3, 5},\n",
       " {1, 3},\n",
       " {1, 4},\n",
       " {2, 3, 4}]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transactions = list()\n",
    "\n",
    "for i, row in df.iterrows():\n",
    "    transaction = set()\n",
    "    \n",
    "    for item in item_dict:\n",
    "        if row[item] == 't':\n",
    "            transaction.add(item_dict[item])\n",
    "    transactions.append(transaction)\n",
    "    \n",
    "transactions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Utility Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**get_support** function evaluates the support value for a set given all the transactions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_support(transactions, item_set):\n",
    "    match_count = 0\n",
    "    for transaction in transactions:\n",
    "        if item_set.issubset(transaction):\n",
    "            match_count += 1\n",
    "            \n",
    "    return float(match_count/len(transactions))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "**self_join** performs join based on the last level valid sets. It joins each sets together by performing union and if the length exceeds the current level, it will skip that set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def self_join(frequent_item_sets_per_level, level):\n",
    "    current_level_candidates = list()\n",
    "    last_level_items = frequent_item_sets_per_level[level - 1]\n",
    "    \n",
    "    if len(last_level_items) == 0:\n",
    "        return current_level_candidates\n",
    "    \n",
    "    for i in range(len(last_level_items)):\n",
    "        for j in range(i+1, len(last_level_items)):\n",
    "            itemset_i = last_level_items[i][0]\n",
    "            itemset_j = last_level_items[j][0]\n",
    "            union_set = itemset_i.union(itemset_j)\n",
    "            \n",
    "            if union_set not in current_level_candidates and len(union_set) == level:\n",
    "                current_level_candidates.append(union_set)\n",
    "                \n",
    "    return current_level_candidates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "**pruning** function prunes the candidate sets evaluated after completing the self-join part. For each itemset, it finds all its subsets by dropping a single elements from it and checks if that subset was present in the previous level or not. If that subset was not present in the previous level, then the current set is not valid and must not be used, and is thus pruned."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_single_drop_subsets(item_set):\n",
    "    single_drop_subsets = list()\n",
    "    for item in item_set:\n",
    "        temp = item_set.copy()\n",
    "        temp.remove(item)\n",
    "        single_drop_subsets.append(temp)\n",
    "        \n",
    "    return single_drop_subsets\n",
    "\n",
    "def is_valid_set(item_set, prev_level_sets):\n",
    "    single_drop_subsets = get_single_drop_subsets(item_set)\n",
    "    \n",
    "    for single_drop_set in single_drop_subsets:\n",
    "        if single_drop_set not in prev_level_sets:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def pruning(frequent_item_sets_per_level, level, candidate_set):\n",
    "    post_pruning_set = list()\n",
    "    if len(candidate_set) == 0:\n",
    "        return post_pruning_set\n",
    "    \n",
    "    prev_level_sets = list()\n",
    "    for item_set, _ in frequent_item_sets_per_level[level - 1]:\n",
    "        prev_level_sets.append(item_set)\n",
    "        \n",
    "    for item_set in candidate_set:\n",
    "        if is_valid_set(item_set, prev_level_sets):\n",
    "            post_pruning_set.append(item_set)\n",
    "            \n",
    "    return post_pruning_set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Apriori Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def apriori(min_support):\n",
    "    frequent_item_sets_per_level = defaultdict(list)\n",
    "    print(\"level : 1\", end = \" \")\n",
    "    \n",
    "    for item in range(1, len(item_list) + 1):\n",
    "        support = get_support(transactions, {item})\n",
    "        if support >= min_support:\n",
    "            frequent_item_sets_per_level[1].append(({item}, support))\n",
    "        \n",
    "    for level in range(2, len(item_list) + 1):\n",
    "        print(level, end = \" \")\n",
    "        current_level_candidates = self_join(frequent_item_sets_per_level, level)\n",
    "\n",
    "        post_pruning_candidates = pruning(frequent_item_sets_per_level, level, current_level_candidates)\n",
    "        if len(post_pruning_candidates) == 0:\n",
    "            break\n",
    "\n",
    "        for item_set in post_pruning_candidates:\n",
    "            support = get_support(transactions, item_set)\n",
    "            if support >= min_support:\n",
    "                frequent_item_sets_per_level[level].append((item_set, support))\n",
    "                \n",
    "    return frequent_item_sets_per_level"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Specify the **minimum support** value here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "level : 1 2 3 4 5 "
     ]
    }
   ],
   "source": [
    "min_support = 0.005\n",
    "frequent_item_sets_per_level = apriori(min_support)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Debug print statements to check the number of frequent sets calculated for each level."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "10\n",
      "7\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "for level in frequent_item_sets_per_level:\n",
    "    print(len(frequent_item_sets_per_level[level]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Debug statement to check the frequent sets calculated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[({1}, 0.8), ({2}, 0.6), ({3}, 0.6), ({4}, 0.4), ({5}, 0.4)]\n",
      "[({1, 2}, 0.5), ({1, 3}, 0.5), ({1, 4}, 0.2), ({1, 5}, 0.3), ({2, 3}, 0.4), ({2, 4}, 0.2), ({2, 5}, 0.2), ({3, 4}, 0.2), ({3, 5}, 0.2), ({4, 5}, 0.1)]\n",
      "[({1, 2, 3}, 0.3), ({1, 2, 4}, 0.1), ({1, 2, 5}, 0.2), ({1, 3, 4}, 0.1), ({1, 3, 5}, 0.2), ({2, 3, 4}, 0.2), ({2, 3, 5}, 0.1)]\n",
      "[({1, 2, 3, 4}, 0.1), ({1, 2, 3, 5}, 0.1)]\n"
     ]
    }
   ],
   "source": [
    "for level in frequent_item_sets_per_level:\n",
    "    print(frequent_item_sets_per_level[level])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Generating Association Rules\n",
    "\n",
    "Prepare input for calculating association rules: Create a dictionary of each frequent itemset against its support value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "item_support_dict = dict()\n",
    "item_list = list()\n",
    "\n",
    "key_list = list(item_dict.keys())\n",
    "val_list = list(item_dict.values())\n",
    "\n",
    "for level in frequent_item_sets_per_level:\n",
    "    for set_support_pair in frequent_item_sets_per_level[level]:\n",
    "        for i in set_support_pair[0]:\n",
    "            item_list.append(key_list[val_list.index(i)])\n",
    "        item_support_dict[frozenset(item_list)] = set_support_pair[1]\n",
    "        item_list = list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Debug statement to check the values in the dictionary created."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{frozenset({'handphone'}): 0.8,\n",
       " frozenset({'laptop'}): 0.6,\n",
       " frozenset({'charger'}): 0.6,\n",
       " frozenset({'powerbank'}): 0.4,\n",
       " frozenset({'tablet'}): 0.4,\n",
       " frozenset({'handphone', 'laptop'}): 0.5,\n",
       " frozenset({'charger', 'handphone'}): 0.5,\n",
       " frozenset({'handphone', 'powerbank'}): 0.2,\n",
       " frozenset({'handphone', 'tablet'}): 0.3,\n",
       " frozenset({'charger', 'laptop'}): 0.4,\n",
       " frozenset({'laptop', 'powerbank'}): 0.2,\n",
       " frozenset({'laptop', 'tablet'}): 0.2,\n",
       " frozenset({'charger', 'powerbank'}): 0.2,\n",
       " frozenset({'charger', 'tablet'}): 0.2,\n",
       " frozenset({'powerbank', 'tablet'}): 0.1,\n",
       " frozenset({'charger', 'handphone', 'laptop'}): 0.3,\n",
       " frozenset({'handphone', 'laptop', 'powerbank'}): 0.1,\n",
       " frozenset({'handphone', 'laptop', 'tablet'}): 0.2,\n",
       " frozenset({'charger', 'handphone', 'powerbank'}): 0.1,\n",
       " frozenset({'charger', 'handphone', 'tablet'}): 0.2,\n",
       " frozenset({'charger', 'laptop', 'powerbank'}): 0.2,\n",
       " frozenset({'charger', 'laptop', 'tablet'}): 0.1,\n",
       " frozenset({'charger', 'handphone', 'laptop', 'powerbank'}): 0.1,\n",
       " frozenset({'charger', 'handphone', 'laptop', 'tablet'}): 0.1}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "item_support_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Utility Function\n",
    "\n",
    "**find_subset** finds all the subsets of the given itemset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_subset(item, item_length):\n",
    "    combs = []\n",
    "    for i in range(1, item_length + 1):\n",
    "        combs.append(list(combinations(item, i)))\n",
    "        \n",
    "    subsets = []\n",
    "    for comb in combs:\n",
    "        for elt in comb:\n",
    "            subsets.append(elt)\n",
    "            \n",
    "    return subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**association_rules** generates the association rules in accordance with the given *minimum confidence* value and the provided dictionary of itemsets against their support values. For itemsets of more than one element, it first finds all their subsets. For every subset A, it calculates the set B = itemset-A. If B is not empty, the confidence of B is calculated. If this value is more than *minimum confidence* value, the rule *A->B* is added to the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def association_rules(min_confidence, support_dict):\n",
    "    rules = list()\n",
    "    for item, support in support_dict.items():\n",
    "        item_length = len(item)\n",
    "       \n",
    "        if item_length > 1:\n",
    "            subsets = find_subset(item, item_length)\n",
    "           \n",
    "            for A in subsets:\n",
    "                B = item.difference(A)\n",
    "               \n",
    "                if B:\n",
    "                    A = frozenset(A)\n",
    "                    \n",
    "                    AB = A | B\n",
    "                    \n",
    "                    confidence = support_dict[AB] / support_dict[A]\n",
    "                    if confidence >= min_confidence:\n",
    "                        rules.append((A, B, confidence))\n",
    "    \n",
    "    return rules"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Specify Minimum confidence value here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "association_rules = association_rules(min_confidence = 0.6, support_dict = item_support_dict)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "### Printing the output in the required format"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of rules:  19 \n",
      "\n",
      "{'laptop'} -> {'handphone'} <confidence: 0.8333333333333334>\n",
      "{'handphone'} -> {'laptop'} <confidence: 0.625>\n",
      "{'charger'} -> {'handphone'} <confidence: 0.8333333333333334>\n",
      "{'handphone'} -> {'charger'} <confidence: 0.625>\n",
      "{'tablet'} -> {'handphone'} <confidence: 0.7499999999999999>\n",
      "{'charger'} -> {'laptop'} <confidence: 0.6666666666666667>\n",
      "{'laptop'} -> {'charger'} <confidence: 0.6666666666666667>\n",
      "{'charger', 'laptop'} -> {'handphone'} <confidence: 0.7499999999999999>\n",
      "{'charger', 'handphone'} -> {'laptop'} <confidence: 0.6>\n",
      "{'laptop', 'handphone'} -> {'charger'} <confidence: 0.6>\n",
      "{'tablet', 'laptop'} -> {'handphone'} <confidence: 1.0>\n",
      "{'tablet', 'handphone'} -> {'laptop'} <confidence: 0.6666666666666667>\n",
      "{'charger', 'tablet'} -> {'handphone'} <confidence: 1.0>\n",
      "{'tablet', 'handphone'} -> {'charger'} <confidence: 0.6666666666666667>\n",
      "{'charger', 'powerbank'} -> {'laptop'} <confidence: 1.0>\n",
      "{'laptop', 'powerbank'} -> {'charger'} <confidence: 1.0>\n",
      "{'charger', 'powerbank', 'handphone'} -> {'laptop'} <confidence: 1.0>\n",
      "{'laptop', 'powerbank', 'handphone'} -> {'charger'} <confidence: 1.0>\n",
      "{'charger', 'tablet', 'laptop'} -> {'handphone'} <confidence: 1.0>\n"
     ]
    }
   ],
   "source": [
    "print(\"Number of rules: \", len(association_rules), \"\\n\")\n",
    "\n",
    "for rule in association_rules:\n",
    "    print('{0} -> {1} <confidence: {2}>'.format(set(rule[0]), set(rule[1]), rule[2]))"
   ]
  }
 ],
 "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.9.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}