CSC 440 Programming Project .ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CSC 440 Programming Project\n",
    "-- Student: Yangxin Fan\n",
    "-- NetID: yfan24"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data preprocessing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Read UCI Adult Census Dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "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>age</th>\n",
       "      <th>workclass</th>\n",
       "      <th>fnlwgt</th>\n",
       "      <th>education</th>\n",
       "      <th>educational-num</th>\n",
       "      <th>marital-status</th>\n",
       "      <th>occupation</th>\n",
       "      <th>relationship</th>\n",
       "      <th>race</th>\n",
       "      <th>gender</th>\n",
       "      <th>capital-gain</th>\n",
       "      <th>capital-loss</th>\n",
       "      <th>hours-per-week</th>\n",
       "      <th>native-country</th>\n",
       "      <th>income</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>25</td>\n",
       "      <td>Private</td>\n",
       "      <td>226802</td>\n",
       "      <td>11th</td>\n",
       "      <td>7</td>\n",
       "      <td>Never-married</td>\n",
       "      <td>Machine-op-inspct</td>\n",
       "      <td>Own-child</td>\n",
       "      <td>Black</td>\n",
       "      <td>Male</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>40</td>\n",
       "      <td>United-States</td>\n",
       "      <td>&lt;=50K</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>38</td>\n",
       "      <td>Private</td>\n",
       "      <td>89814</td>\n",
       "      <td>HS-grad</td>\n",
       "      <td>9</td>\n",
       "      <td>Married-civ-spouse</td>\n",
       "      <td>Farming-fishing</td>\n",
       "      <td>Husband</td>\n",
       "      <td>White</td>\n",
       "      <td>Male</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>50</td>\n",
       "      <td>United-States</td>\n",
       "      <td>&lt;=50K</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>28</td>\n",
       "      <td>Local-gov</td>\n",
       "      <td>336951</td>\n",
       "      <td>Assoc-acdm</td>\n",
       "      <td>12</td>\n",
       "      <td>Married-civ-spouse</td>\n",
       "      <td>Protective-serv</td>\n",
       "      <td>Husband</td>\n",
       "      <td>White</td>\n",
       "      <td>Male</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>40</td>\n",
       "      <td>United-States</td>\n",
       "      <td>&gt;50K</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>44</td>\n",
       "      <td>Private</td>\n",
       "      <td>160323</td>\n",
       "      <td>Some-college</td>\n",
       "      <td>10</td>\n",
       "      <td>Married-civ-spouse</td>\n",
       "      <td>Machine-op-inspct</td>\n",
       "      <td>Husband</td>\n",
       "      <td>Black</td>\n",
       "      <td>Male</td>\n",
       "      <td>7688</td>\n",
       "      <td>0</td>\n",
       "      <td>40</td>\n",
       "      <td>United-States</td>\n",
       "      <td>&gt;50K</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>18</td>\n",
       "      <td>?</td>\n",
       "      <td>103497</td>\n",
       "      <td>Some-college</td>\n",
       "      <td>10</td>\n",
       "      <td>Never-married</td>\n",
       "      <td>?</td>\n",
       "      <td>Own-child</td>\n",
       "      <td>White</td>\n",
       "      <td>Female</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>30</td>\n",
       "      <td>United-States</td>\n",
       "      <td>&lt;=50K</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>48837</th>\n",
       "      <td>27</td>\n",
       "      <td>Private</td>\n",
       "      <td>257302</td>\n",
       "      <td>Assoc-acdm</td>\n",
       "      <td>12</td>\n",
       "      <td>Married-civ-spouse</td>\n",
       "      <td>Tech-support</td>\n",
       "      <td>Wife</td>\n",
       "      <td>White</td>\n",
       "      <td>Female</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>38</td>\n",
       "      <td>United-States</td>\n",
       "      <td>&lt;=50K</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>48838</th>\n",
       "      <td>40</td>\n",
       "      <td>Private</td>\n",
       "      <td>154374</td>\n",
       "      <td>HS-grad</td>\n",
       "      <td>9</td>\n",
       "      <td>Married-civ-spouse</td>\n",
       "      <td>Machine-op-inspct</td>\n",
       "      <td>Husband</td>\n",
       "      <td>White</td>\n",
       "      <td>Male</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>40</td>\n",
       "      <td>United-States</td>\n",
       "      <td>&gt;50K</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>48839</th>\n",
       "      <td>58</td>\n",
       "      <td>Private</td>\n",
       "      <td>151910</td>\n",
       "      <td>HS-grad</td>\n",
       "      <td>9</td>\n",
       "      <td>Widowed</td>\n",
       "      <td>Adm-clerical</td>\n",
       "      <td>Unmarried</td>\n",
       "      <td>White</td>\n",
       "      <td>Female</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>40</td>\n",
       "      <td>United-States</td>\n",
       "      <td>&lt;=50K</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>48840</th>\n",
       "      <td>22</td>\n",
       "      <td>Private</td>\n",
       "      <td>201490</td>\n",
       "      <td>HS-grad</td>\n",
       "      <td>9</td>\n",
       "      <td>Never-married</td>\n",
       "      <td>Adm-clerical</td>\n",
       "      <td>Own-child</td>\n",
       "      <td>White</td>\n",
       "      <td>Male</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>20</td>\n",
       "      <td>United-States</td>\n",
       "      <td>&lt;=50K</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>48841</th>\n",
       "      <td>52</td>\n",
       "      <td>Self-emp-inc</td>\n",
       "      <td>287927</td>\n",
       "      <td>HS-grad</td>\n",
       "      <td>9</td>\n",
       "      <td>Married-civ-spouse</td>\n",
       "      <td>Exec-managerial</td>\n",
       "      <td>Wife</td>\n",
       "      <td>White</td>\n",
       "      <td>Female</td>\n",
       "      <td>15024</td>\n",
       "      <td>0</td>\n",
       "      <td>40</td>\n",
       "      <td>United-States</td>\n",
       "      <td>&gt;50K</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>48842 rows × 15 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "       age     workclass  fnlwgt     education  educational-num  \\\n",
       "0       25       Private  226802          11th                7   \n",
       "1       38       Private   89814       HS-grad                9   \n",
       "2       28     Local-gov  336951    Assoc-acdm               12   \n",
       "3       44       Private  160323  Some-college               10   \n",
       "4       18             ?  103497  Some-college               10   \n",
       "...    ...           ...     ...           ...              ...   \n",
       "48837   27       Private  257302    Assoc-acdm               12   \n",
       "48838   40       Private  154374       HS-grad                9   \n",
       "48839   58       Private  151910       HS-grad                9   \n",
       "48840   22       Private  201490       HS-grad                9   \n",
       "48841   52  Self-emp-inc  287927       HS-grad                9   \n",
       "\n",
       "           marital-status         occupation relationship   race  gender  \\\n",
       "0           Never-married  Machine-op-inspct    Own-child  Black    Male   \n",
       "1      Married-civ-spouse    Farming-fishing      Husband  White    Male   \n",
       "2      Married-civ-spouse    Protective-serv      Husband  White    Male   \n",
       "3      Married-civ-spouse  Machine-op-inspct      Husband  Black    Male   \n",
       "4           Never-married                  ?    Own-child  White  Female   \n",
       "...                   ...                ...          ...    ...     ...   \n",
       "48837  Married-civ-spouse       Tech-support         Wife  White  Female   \n",
       "48838  Married-civ-spouse  Machine-op-inspct      Husband  White    Male   \n",
       "48839             Widowed       Adm-clerical    Unmarried  White  Female   \n",
       "48840       Never-married       Adm-clerical    Own-child  White    Male   \n",
       "48841  Married-civ-spouse    Exec-managerial         Wife  White  Female   \n",
       "\n",
       "       capital-gain  capital-loss  hours-per-week native-country income  \n",
       "0                 0             0              40  United-States  <=50K  \n",
       "1                 0             0              50  United-States  <=50K  \n",
       "2                 0             0              40  United-States   >50K  \n",
       "3              7688             0              40  United-States   >50K  \n",
       "4                 0             0              30  United-States  <=50K  \n",
       "...             ...           ...             ...            ...    ...  \n",
       "48837             0             0              38  United-States  <=50K  \n",
       "48838             0             0              40  United-States   >50K  \n",
       "48839             0             0              40  United-States  <=50K  \n",
       "48840             0             0              20  United-States  <=50K  \n",
       "48841         15024             0              40  United-States   >50K  \n",
       "\n",
       "[48842 rows x 15 columns]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "D = pd.read_csv(\"Adult.csv\")\n",
    "D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us analyze all categorical attributes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "D = np.array(D)\n",
    "D = D[:,[1,3,5,6,7,8,9,13,14]]\n",
    "tran_set = D.tolist()\n",
    "min_sup = 20000"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find all items in transactions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "item_set = []\n",
    "for tran in tran_set:\n",
    "    item_set = list(set().union(item_set,tran))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithm I: Apriori [AS94b]\n",
    "Find frequent itemsets using an iterative level-wise approach based on candidate generation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Find frequent 1-itemset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['<=50K', 'White', 'United-States', 'Male', 'Private', 'Married-civ-spouse']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def find_frequent_1_itemsets(tran_set, item_set, min_sup):\n",
    "    frequent_1_itemsets = []\n",
    "    for item in item_set:\n",
    "        count = 0\n",
    "        for tran in tran_set:\n",
    "            if item in tran: \n",
    "                count+=1\n",
    "        if count >= min_sup:\n",
    "            frequent_1_itemsets.append(item)\n",
    "    return frequent_1_itemsets\n",
    "\n",
    "import itertools\n",
    "from itertools import combinations\n",
    "L = find_frequent_1_itemsets(tran_set, item_set, min_sup)\n",
    "L"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function has_infrequent: Find whether a candidate itemset has a infrequent subset, if it has, \n",
    "then I would not be added (superset of an infrequent itemset must be infrequent)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "from itertools import combinations\n",
    "\n",
    "def has_infrequent(c,L,k):\n",
    "    subset = list(map(set, itertools.combinations(c, k-1)))\n",
    "    for sub in subset:\n",
    "        if all(sub != set(l) for l in L):\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function apriori_gen: generate candidates of frequent itemsets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def apriori_gen(L,k):\n",
    "    C = []\n",
    "    if k==2:\n",
    "        C = list(itertools.combinations(L, 2))\n",
    "    else:\n",
    "        for p in L:\n",
    "            for q in L:\n",
    "                p.sort()\n",
    "                q.sort()\n",
    "                length = len(p)\n",
    "                if all(p[i]==q[i] for i in range(length-1)) and p[length-1]<q[length-1]:\n",
    "                    c = set(set().union(p,q))\n",
    "                    if has_infrequent(list(c), L, k) is False:\n",
    "                        C.append(list(c))\n",
    "    return C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Generate a list of frequent itemsets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['<=50K',\n",
       " 'White',\n",
       " 'United-States',\n",
       " 'Male',\n",
       " 'Private',\n",
       " 'Married-civ-spouse',\n",
       " ['<=50K', 'White'],\n",
       " ['<=50K', 'United-States'],\n",
       " ['<=50K', 'Male'],\n",
       " ['<=50K', 'Private'],\n",
       " ['United-States', 'White'],\n",
       " ['Male', 'White'],\n",
       " ['Private', 'White'],\n",
       " ['Married-civ-spouse', 'White'],\n",
       " ['Male', 'United-States'],\n",
       " ['Private', 'United-States'],\n",
       " ['Married-civ-spouse', 'United-States'],\n",
       " ['Male', 'Private'],\n",
       " ['<=50K', 'United-States', 'White'],\n",
       " ['<=50K', 'Male', 'United-States'],\n",
       " ['<=50K', 'Private', 'White'],\n",
       " ['<=50K', 'Private', 'United-States'],\n",
       " ['Male', 'United-States', 'White'],\n",
       " ['Private', 'United-States', 'White'],\n",
       " ['<=50K', 'Private', 'United-States', 'White']]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequent_list = []\n",
    "k = 2\n",
    "#print (L)\n",
    "frequent_list = frequent_list + L\n",
    "while k < len(item_set) and len(L)>0:\n",
    "    C = apriori_gen(L, k)\n",
    "    #print(C)\n",
    "    L = []\n",
    "    #print(k)\n",
    "    for candidate in C:\n",
    "        count = 0\n",
    "        for tran in tran_set:\n",
    "            if set(candidate).issubset(set(tran)):\n",
    "                count+=1\n",
    "        if count >= min_sup and candidate not in L:\n",
    "            L.append(list(candidate))\n",
    "    #print (L)\n",
    "    frequent_list = frequent_list + L\n",
    "    k = k+1\n",
    "frequent_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithm II: FP-growth [HPY00]\n",
    "Mine frequent itemsets using an FP-tree by pattern fragment growth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Acquire a list of frequent items and their support counts and sort it by counts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First database scan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'United-States': 43832,\n",
       " 'White': 41762,\n",
       " '<=50K': 37155,\n",
       " 'Private': 33906,\n",
       " 'Male': 32650,\n",
       " 'Married-civ-spouse': 22379}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F = {}\n",
    "for item in item_set:\n",
    "    count = 0\n",
    "    for tran in tran_set:\n",
    "        if item in tran: \n",
    "            count+=1\n",
    "    if count >= min_sup:\n",
    "        F[item] = count\n",
    "        \n",
    "sorted_F = sorted(F.items(), key=lambda x: (-x[1],x[0]))\n",
    "item_dict = {}\n",
    "for pair in sorted_F:\n",
    "    item_dict[pair[0]] = pair[1] \n",
    "item_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Construct FP-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define the structure of the FP-Tree node "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class fpTreeNode:\n",
    "    def __init__(self, name, freq, parent):\n",
    "        self.name = name # contains the name of the item\n",
    "        self.freq = freq # contains frequency of the item in the dataset\n",
    "        self.parent = parent # contains the parent node\n",
    "        self.child = OrderedDict() # contains all the children node information\n",
    "        self.link = None # for linking to nodes with same name"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Second scan D and create a sorted items list according to counts and a similary item dictionary that \n",
    "could link different nodes with same item together"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'United-States': None,\n",
       " 'White': None,\n",
       " '<=50K': None,\n",
       " 'Private': None,\n",
       " 'Male': None,\n",
       " 'Married-civ-spouse': None}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted_F = sorted(F.items(), key=lambda x: (-x[1],x[0]))\n",
    "sorted_keys = []\n",
    "similar_item_dict = {}\n",
    "for key in sorted_F:\n",
    "        similar_item_dict[key[0]] = None # Initially all the values are 'None'\n",
    "        sorted_keys.append(key[0])\n",
    "similar_item_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Go through each transaction and grow FP-tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fp_tree_create_and_update(init_node, trans, similar_item_dict):\n",
    "    # if child is present, we increment its count\n",
    "    if trans[0] in init_node.child:\n",
    "        init_node.child[trans[0]].freq += 1\n",
    "    # else, create a new node for the child and link it to its parent\n",
    "    else:\n",
    "        init_node.child[trans[0]] = fpTreeNode(trans[0], 1, init_node)\n",
    "        # for every newly created node, the Similar-Item table is updated\n",
    "        if similar_item_dict[trans[0]] == None:\n",
    "            # for the 1st node, replace the 'None' value with the node\n",
    "            similar_item_dict[trans[0]] = init_node.child[trans[0]]\n",
    "        else:\n",
    "            # traverse till the last similar node, and update the new node\n",
    "            similar_item_table_update(similar_item_dict[trans[0]],\\\n",
    "                                      init_node.child[trans[0]])\n",
    "    # recursively called for every item in a transaction\n",
    "    if len(trans) > 1:\n",
    "        fp_tree_create_and_update(init_node.child[trans[0]], trans[1::],\\\n",
    "                                  similar_item_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def similar_item_table_update(similar_item, present_node): \n",
    "    while (similar_item.link != None):\n",
    "        similar_item = similar_item.link\n",
    "    similar_item.link = present_node"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use function similar_item_table_update, fp_tree_create_and_update to link nodes and update counts of nodes\n",
    "and use class fpTreeNode to create new nodes \n",
    "Eventually, to build a FP-Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import OrderedDict\n",
    "root = fpTreeNode('Root',1,None)\n",
    "for tr in tran_set:\n",
    "    # delete all items whose frequency are below the minimum support\n",
    "    tran = []\n",
    "    for item in tr:\n",
    "        if item in item_dict:\n",
    "            tran.append(item)\n",
    "    ordered_trans = []\n",
    "    for item in sorted_keys:\n",
    "        if item in tran:\n",
    "            ordered_trans.append(item)\n",
    "    if len(ordered_trans)!= 0:\n",
    "        fp_tree_create_and_update(root, ordered_trans, similar_item_dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'United-States': <__main__.fpTreeNode at 0x119019b20>,\n",
       " 'White': <__main__.fpTreeNode at 0x10de26610>,\n",
       " '<=50K': <__main__.fpTreeNode at 0x1190196d0>,\n",
       " 'Private': <__main__.fpTreeNode at 0x10de266d0>,\n",
       " 'Male': <__main__.fpTreeNode at 0x10de26f70>,\n",
       " 'Married-civ-spouse': <__main__.fpTreeNode at 0x10de26bb0>}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "similar_item_dict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mining FP-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create conditional pattern base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_cond_base(similar_item_dict, threshold, tran_set):\n",
    "    final_cond_base = []\n",
    "    # go through every key-value pair present in the Similar-Item Table\n",
    "    for key,value in similar_item_dict.items():\n",
    "        final_cond_base_key = []\n",
    "        condition_base = []\n",
    "        leaf_item_freq = OrderedDict()\n",
    "        # within each key, traverse through every linked node value till the end\n",
    "        while value != None:\n",
    "            path = []\n",
    "            leaf_node = value\n",
    "            leaf_freq = value.freq\n",
    "            # within each node, traverse till the parent node and append details\n",
    "            while leaf_node.parent != None:\n",
    "                leaf_details = [leaf_node.name, leaf_freq]\n",
    "                path.append(leaf_details) # append the name and value\n",
    "                leaf_node = leaf_node.parent # Go to the parent of that node\n",
    "            # insert the whole path to condition_base\n",
    "            condition_base.insert(0,path)\n",
    "            # once the  particular node is finished, increment to value.link\n",
    "            # then traverse for the next node with same name\n",
    "            value = value.link\n",
    "        # a frequent item-set dictionary is created for every leaf node\n",
    "        for row in condition_base:\n",
    "            for col in row:\n",
    "                if col[0] not in leaf_item_freq:\n",
    "                    leaf_item_freq[col[0]] = col[1]\n",
    "                else:\n",
    "                    leaf_item_freq[col[0]] += col[1]\n",
    "        # items below threshold are removed before creating the conditional base\n",
    "        leaf_item_freq = {k:v for k,v in leaf_item_freq.items() \\\n",
    "                          if v >= threshold}\n",
    "        # for every transaction in the condition_base, the items are stored\n",
    "        for row in condition_base:\n",
    "            temp = []\n",
    "            temp_tree = []\n",
    "            for col in row:\n",
    "                if col[0] in leaf_item_freq:\n",
    "                    temp.append(col[0]) # stores only the name of the item\n",
    "                    temp_tree.append(col) # stores both name and frequency\n",
    "            # contains all the frequent items for a particular conditional leaf\n",
    "            final_cond_base.append(temp) # used for question 2A\n",
    "            final_cond_base_key.append(temp_tree) # used for question 2B\n",
    "            \n",
    "        cond_leaf = key\n",
    "        cond_root = fpTreeNode('Root',1,None)\n",
    "        # creates the conditional tree from the above conditonal pattern base\n",
    "        for row in final_cond_base_key:\n",
    "            conditional_fptree(cond_leaf,cond_root,row)\n",
    "    # removes any duplicate rows having the same itemset\n",
    "    unique_cond_base_set = set(map(tuple,final_cond_base))\n",
    "    unique_cond_base_list =list(unique_cond_base_set)\n",
    "    unique_cond_base = map(list,unique_cond_base_list)\n",
    "    unique_cond_base_list.sort(key=lambda \\\n",
    "                               unique_cond_base_list:unique_cond_base_list[0])\n",
    "    unique_cond_base = map(list,unique_cond_base_list)\n",
    "    L = []\n",
    "    for item_set in unique_cond_base_list:\n",
    "        count = 0\n",
    "        for tran in tran_set:\n",
    "            if set(item_set).issubset(set(tran)):\n",
    "                count+=1\n",
    "        if count >= threshold:\n",
    "            L.append(item_set)\n",
    "    return L\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def conditional_fptree(name,init_node,data):\n",
    "\n",
    "    if data[0][0] == name:\n",
    "        # skip the conditional tree if no extra frequent items are occuring\n",
    "        if len(data)>1:\n",
    "            conditional_fptree(name,init_node,data[1::])\n",
    "    if data[0][0] != name:\n",
    "        # if the item is present as a child, increment its count\n",
    "        if data[0][0] in init_node.child:\n",
    "            init_node.child[data[0][0]].freq += data[0][1]\n",
    "        # else, create a new child node and update its frequency\n",
    "        else:\n",
    "            init_node.child[data[0][0]] = fpTreeNode(data[0][0],data[0][1],\\\n",
    "                           init_node)\n",
    "        # continue to recursively create the conditional FP-Tree for each item\n",
    "        if len(data) >1:\n",
    "            conditional_fptree(name,init_node.child[data[0][0]],data[1::])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create a set of frequent itemsets. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('<=50K',),\n",
       " ('<=50K', 'United-States'),\n",
       " ('<=50K', 'White'),\n",
       " ('<=50K', 'White', 'United-States'),\n",
       " ('Male',),\n",
       " ('Male', '<=50K'),\n",
       " ('Male', '<=50K', 'United-States'),\n",
       " ('Male', 'Private'),\n",
       " ('Male', 'United-States'),\n",
       " ('Male', 'White'),\n",
       " ('Male', 'White', 'United-States'),\n",
       " ('Married-civ-spouse',),\n",
       " ('Married-civ-spouse', 'United-States'),\n",
       " ('Married-civ-spouse', 'White'),\n",
       " ('Private',),\n",
       " ('Private', '<=50K'),\n",
       " ('Private', '<=50K', 'United-States'),\n",
       " ('Private', '<=50K', 'White'),\n",
       " ('Private', '<=50K', 'White', 'United-States'),\n",
       " ('Private', 'United-States'),\n",
       " ('Private', 'White'),\n",
       " ('Private', 'White', 'United-States'),\n",
       " ('United-States',),\n",
       " ('White',),\n",
       " ('White', 'United-States')}"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "minimal_freq_list = create_cond_base(similar_item_dict, min_sup, tran_set)\n",
    "frequent_itemsets = set()\n",
    "for item in minimal_freq_list:\n",
    "    for i in range(1,len(item)+1):\n",
    "        for set_freq in itertools.combinations(item, i):\n",
    "            frequent_itemsets.add(set_freq)\n",
    "frequent_itemsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithm III: Improving the Efficiency of Apriori Using Transaction Reduction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "D = np.array(pd.read_csv(\"Adult.csv\"))\n",
    "min_sup = 20000\n",
    "D = D[:,[1,3,5,6,7,8,9,13,14]]\n",
    "tran_set = D.tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "item_set = []\n",
    "for tran in tran_set:\n",
    "    item_set = list(set().union(item_set,tran))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_frequent_1_itemsets(tran_set, item_set, min_sup):\n",
    "    frequent_1_itemsets = []\n",
    "    for item in item_set:\n",
    "        count = 0\n",
    "        for tran in tran_set:\n",
    "            if item in tran: \n",
    "                count+=1\n",
    "        if count >= min_sup:\n",
    "            frequent_1_itemsets.append(item)\n",
    "    return frequent_1_itemsets\n",
    "\n",
    "import itertools\n",
    "from itertools import combinations\n",
    "L = find_frequent_1_itemsets(tran_set, item_set, min_sup)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "from itertools import combinations\n",
    "\n",
    "# pass p, q to has_infrequent, in subset we do not consider these 2 subsets (already frequent)\n",
    "def has_infrequent(c,L,k,p,q):\n",
    "    subset = list(map(set, itertools.combinations(c, k-1)))\n",
    "    \n",
    "    # --- added part start\n",
    "    subset.remove(set(p))\n",
    "    subset.remove(set(q))\n",
    "    # --- added part end\n",
    "    \n",
    "    for sub in subset:\n",
    "        if all(sub != set(l) for l in L):\n",
    "            return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def apriori_gen(L,k):\n",
    "    C = []\n",
    "    if k==2:\n",
    "        C = list(itertools.combinations(L, 2))\n",
    "    else:\n",
    "        for p in L:\n",
    "            for q in L:\n",
    "                p.sort()\n",
    "                q.sort()\n",
    "                length = len(p)\n",
    "                if all(p[i]==q[i] for i in range(length-1)) and p[length-1]<q[length-1]:\n",
    "                    c = set(set().union(p,q))\n",
    "                    if has_infrequent(list(c), L, k, p, q) is False:\n",
    "                        C.append(list(c))\n",
    "    return C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Remove a transaction if it does not contain any frequent k-itemsets so we do not need \n",
    "to scan such a transaction when finding the count of k+1 candidate itemsets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['<=50K',\n",
       " 'White',\n",
       " 'United-States',\n",
       " 'Male',\n",
       " 'Private',\n",
       " 'Married-civ-spouse',\n",
       " ['<=50K', 'White'],\n",
       " ['<=50K', 'United-States'],\n",
       " ['<=50K', 'Male'],\n",
       " ['<=50K', 'Private'],\n",
       " ['United-States', 'White'],\n",
       " ['Male', 'White'],\n",
       " ['Private', 'White'],\n",
       " ['Married-civ-spouse', 'White'],\n",
       " ['Male', 'United-States'],\n",
       " ['Private', 'United-States'],\n",
       " ['Married-civ-spouse', 'United-States'],\n",
       " ['Male', 'Private'],\n",
       " ['<=50K', 'United-States', 'White'],\n",
       " ['<=50K', 'Male', 'United-States'],\n",
       " ['<=50K', 'Private', 'White'],\n",
       " ['<=50K', 'Private', 'United-States'],\n",
       " ['Male', 'United-States', 'White'],\n",
       " ['Private', 'United-States', 'White'],\n",
       " ['<=50K', 'Private', 'United-States', 'White']]"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "frequent_list = []\n",
    "k = 2\n",
    "frequent_list = frequent_list + L\n",
    "while k < len(item_set) and len(L)>0:\n",
    "    \n",
    "    # --- added part start\n",
    "    for tran in tran_set:\n",
    "        count = 0\n",
    "        for freq_item in L:\n",
    "            if k == 2:\n",
    "                if freq_item in tran:\n",
    "                    count+=1\n",
    "            else:\n",
    "                if set(freq_item).issubset(set(tran)):\n",
    "                    count+=1   \n",
    "        if count==0:\n",
    "            tran_set.remove(tran)\n",
    "    # --- added part end\n",
    "            \n",
    "    C = apriori_gen(L, k)\n",
    "    L = []\n",
    "    \n",
    "    for candidate in C:\n",
    "        count = 0\n",
    "        # --- added part start\n",
    "        for tran in tran_set:\n",
    "            if len(tran)<len(candidate):\n",
    "                tran_set.remove(tran)\n",
    "        # --- added part end\n",
    "            \n",
    "        for tran in tran_set:\n",
    "            if set(candidate).issubset(set(tran)):\n",
    "                count+=1\n",
    "        if count >= min_sup and candidate not in L:\n",
    "            L.append(list(candidate))\n",
    "    frequent_list = frequent_list + L\n",
    "    k = k+1\n",
    "frequent_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary of improved Apriori with three improvements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Less scan of transactions in database: removing a transaction if it does not contain any frequent k-itemsets \n",
    "so we do not need to scan such a transaction when finding the count of k+1 candidate itemsets\n",
    "2. When pruning candidate itemsets, we do not need to check two itemsets where a particular itemset generated\n",
    "from since they are already frequent itemsets\n",
    "3. Delete transactions where their length less than the length of candidate itemset we want to check for frequency\n",
    "\n",
    "Reference:\n",
    "https://towardsdatascience.com/understand-and-build-fp-growth-algorithm-in-python-d8b989bab342"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}