jupyter-notebooks/vmsp-mining.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "92c917cf-7c48-44b3-9138-28b063e912b9",
   "metadata": {},
   "source": [
    "**VMSP algorithm to find maximal sequence patterns**"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43cd5360-85d1-4e95-876c-7df82fe42d40",
   "metadata": {},
   "source": [
    "VMSP (Vertical maximal sequence patterns) is, well a pattern mining algorithm to find _maximal_ sequential patterns from a dataset containing event sequences. The original paper is present at [link](https://www.philippe-fournier-viger.com/spmf/VMSP_maximal_sequential_patterns_2014.pdf).\n",
    "\n",
    "Some glossary:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f326f556-352e-48f9-8b2f-e9d7bc0819ac",
   "metadata": {},
   "source": [
    "**Event sequence** - an ordered list of event objects. Each event specifies an event type, though could also have other attributes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f8f2ecad-d199-47f2-a750-1938773aa13c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# tennis shot by shot data\n",
    "data = [\n",
    "    [\n",
    "        {\"typ\": \"serve\", \"player\": 1, \"winner\": False},\n",
    "        {\"typ\": \"backhand\", \"player\": 2, \"winner\": False},\n",
    "        {\"typ\": \"backhand\", \"player\": 1, \"winner\": True},\n",
    "    ],\n",
    "    [\n",
    "        {\"typ\": \"serve\", \"player\": 1, \"winner\": True},\n",
    "    ],\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b7e5ee3-0ee7-4db6-9fe9-2c6e89339524",
   "metadata": {},
   "source": [
    "**Subsequence** - A subset of the events in a sequence; doesn't need to be contiguous but retains the order in the original sequence. \n",
    "\n",
    "**Pattern** - also specified as a list of events. If a sequence has a subsequence matching each event in the pattern, it is a match. \n",
    "\n",
    "**Support** - number of sequences in the dataset that match against a pattern. \n",
    "\n",
    "**Maximal pattern** - a pattern is maximal if no other pattern obtained by appending events to it has a support greater than the threshold minimum support."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd671ac2-ea6c-4e17-b4bf-80af7643730f",
   "metadata": {},
   "source": [
    "The core algorithm is pretty straightforward, and works by extending the current set of frequent patterns with more events. A number of heuristics are used to prune alternatives that won't result in maximal patterns. \n",
    "\n",
    "We implement it first with regular python objects. Sequences are list of strings, and the dataset is a list of sequences. \n",
    "\n",
    "NOTE: We deviate somewhat from the full algorithm, in that the general algorithm works with `itemsets`, which are sets of events instead of a single event at each index of the sequence. The sequences looks like `{A}-{A,B}-{C}-{A,B}` instead of `A-B-A-C-B-B`. We stick to single event at an index sequences. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a105ec67-d699-4850-8532-f214b166d490",
   "metadata": {
    "tags": []
   },
   "source": [
    "## regular python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "00887960-e5a6-4f48-bafa-3b6a884615f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = [\n",
    "    [\"a\", \"b\", \"c\", \"d\"],\n",
    "    [\"b\", \"c\", \"d\", \"e\"],\n",
    "    [\"c\", \"d\", \"e\", \"f\"],\n",
    "    [\"d\", \"e\", \"f\", \"g\"],\n",
    "    [\"e\", \"f\", \"g\", \"h\"],\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "c4846b2a-e9ad-422b-a728-0d03ca61fc2c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def match_seq(seq: list[str], pat: list[str]) -> bool:\n",
    "    \"\"\"find out if the pattern matches the sequence\"\"\"\n",
    "    if len(pat) == 0:\n",
    "        return True\n",
    "    for i in range(len(seq)):\n",
    "        if seq[i] == pat[0]:\n",
    "            return match_seq(seq[i + 1 :], pat[1:])\n",
    "    return False\n",
    "\n",
    "\n",
    "def calc_support(pat: list[str]) -> int:\n",
    "    \"\"\"find the num of sequences that match this pattern\"\"\"\n",
    "    count = 0\n",
    "    for seq in dataset:\n",
    "        if match_seq(seq, pat):\n",
    "            count += 1\n",
    "    return count\n",
    "\n",
    "\n",
    "def search(\n",
    "    result: list[list[str]], pat: list[str], extend_set: set[str], min_sup: int\n",
    ") -> None:\n",
    "    \"\"\"try to extend the input pattern and check if it is maximal\"\"\"\n",
    "    next_extend_set: set[str] = set()\n",
    "    for evt in extend_set:\n",
    "        if calc_support([*pat, evt]) >= min_sup:\n",
    "            next_extend_set.add(evt)\n",
    "\n",
    "    # recurse on the next set of candidate patterns\n",
    "    for evt in next_extend_set:\n",
    "        search(result, [*pat, evt], next_extend_set, min_sup)\n",
    "\n",
    "    # if no extended patterns are frequent, the current pattern might be maximal\n",
    "    if len(next_extend_set) == 0:\n",
    "        for pat_i in result:\n",
    "            # we gotta check if any existing pattern is a super pattern to this one\n",
    "            if len(pat_i) > len(pat) and match_seq(pat_i, pat):\n",
    "                return\n",
    "\n",
    "        result.append(pat)\n",
    "        # also cut out any existing patterns that are sub patterns to this one\n",
    "        cut_indices = []\n",
    "        for i, pat_i in enumerate(result):\n",
    "            if len(pat_i) < len(pat) and match_seq(pat, pat_i):\n",
    "                cut_indices.append(i)\n",
    "        for i in cut_indices:\n",
    "            result.pop(i)\n",
    "\n",
    "\n",
    "def enumerate_patterns(min_sup: int):\n",
    "    \"\"\"find all patterns that match at least `min_sup` number of sequences\"\"\"\n",
    "    # find the most frequent events, cut out the ones below the threshold\n",
    "    event_counts = dict()\n",
    "    for seq in dataset:\n",
    "        for evt in seq:\n",
    "            if evt in event_counts:\n",
    "                event_counts[evt] += 1\n",
    "            else:\n",
    "                event_counts[evt] = 1\n",
    "\n",
    "    result: list[list[str]] = []\n",
    "    extend_set = set(e for e, c in event_counts.items() if c >= min_sup)\n",
    "    for evt in extend_set:\n",
    "        search(result, [evt], extend_set, min_sup)\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6cfdfab1-bdcd-4767-8983-6968feb450fd",
   "metadata": {},
   "source": [
    "For ex, to find patterns with minimum support of 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "da6e6035-59c1-460a-bca2-523a10cbe9d4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['d', 'e'], ['c', 'd'], ['e', 'f']]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enumerate_patterns(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0c084be-afdd-4ad2-9ede-3dfaa261e8a3",
   "metadata": {},
   "source": [
    "We expect to see some interesting patterns from mining, though not too many. Further, longer patterns likely convey more information than a prefix of them. This makes maximal patterns a reasonable set to work with. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10033e87-c8e3-497c-bf7d-d7f7f9993dbc",
   "metadata": {},
   "source": [
    "### Optimizing the search"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71f96e7b-54df-4ddc-a741-271eb349c78b",
   "metadata": {},
   "source": [
    "The problem size grows with:\n",
    "* dataset with large num of sequences\n",
    "* sequences with long list of events\n",
    "\n",
    "The primitives that get called a lot:\n",
    "1. calculating support for pattern (calls match-sequence for each sequence in the dataset)\n",
    "2. match-sequence to check if one pattern is a super/sub pattern of another"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c08fba2e-992b-46a9-9737-e22b70819e92",
   "metadata": {},
   "source": [
    "The original paper uses a bunch of heuristics to reduce time spent doing both. \n",
    "\n",
    "* For 1, create a data structure called `id-list` for each event type, that records all instances of the event across all sequences as `(sequence-id, index-of-event-in-sequence)` tuples. Support for any pattern can now be calculated by _joining_ these id-lists for the events in it.\n",
    "* For 2, use a heap like container to store maximal patterns and cut down on these function calls. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6d770f0c-3873-43e2-af6e-4cb86a57fded",
   "metadata": {},
   "source": [
    "What we implement:\n",
    "* I like databases. Duckdb provides really quick range joins, which we can use to implement 1. \n",
    "* I don't like fancy data structures. For large datasets, 2 might not be that big a factor anyway since 1 probably consumes most cycles. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cd916650-7eaf-476d-9dbe-a977dbbbb0a4",
   "metadata": {},
   "source": [
    "## Foursquare dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "879717b4-5653-47ba-9488-8d871c5d6cad",
   "metadata": {},
   "source": [
    "We use the foursquare NYC check-ins dataset to test the algorithm (inspired by the MAQUI [paper](https://www.zcliu.org/maqui/)). We want to look at the sequences of places a user visits within a full day."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6546c075-2c0d-4fc3-a445-c350feb015a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "import duckdb as db\n",
    "import numpy as np\n",
    "import pyarrow as pa\n",
    "import pyarrow.parquet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f2f105dd-a6f9-468d-8c98-973914018f92",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "userId: int64\n",
       "venueId: string\n",
       "venueCategoryId: string\n",
       "venueCategory: string\n",
       "latitude: double\n",
       "longitude: double\n",
       "timezoneOffset: int64\n",
       "utcTimestamp: timestamp[ms, tz=UTC]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ds = pa.parquet.read_table(\"../assets/foursquare_nyc.parquet\")\n",
    "ds.schema"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "927476b4-d347-4426-93ad-f30276573dab",
   "metadata": {},
   "outputs": [],
   "source": [
    "# some math to get the timestamp in local timezone, so we can segment event sequences by day.\n",
    "local_times = pa.array(\n",
    "    ds[\"utcTimestamp\"] + ds[\"timezoneOffset\"].to_numpy().astype(\"timedelta64[m]\"),\n",
    "    pa.timestamp(\"s\", tz=None),\n",
    ")\n",
    "\n",
    "# The event identifier we want to use is the `venueCategory`. Could dictionary encode it so we only have integers to work wt\n",
    "venue_dict_ids = pa.compute.dictionary_encode(ds[\"venueCategory\"]).combine_chunks()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "227f9eed-f3c0-47b5-a55b-35e7be1bbafc",
   "metadata": {},
   "outputs": [],
   "source": [
    "venue_categories = venue_dict_ids.dictionary.tolist()\n",
    "ds = (\n",
    "    ds.remove_column(ds.column_names.index(\"utcTimestamp\"))\n",
    "    .append_column(\"localTimestamp\", local_times)\n",
    "    .remove_column(ds.column_names.index(\"venueCategoryId\"))\n",
    "    .append_column(\"venueCategoryId\", venue_dict_ids.indices)\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "3a545784-bde5-4164-adb4-e6c34e4fdc68",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<duckdb.DuckDBPyConnection at 0x106c52cb0>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "conn = db.connect()\n",
    "conn.register(\"raw_events\", ds)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "076c4990-c559-4b3f-97cb-b2a33f89dc33",
   "metadata": {},
   "source": [
    "We are good to query the duckdb dataset now."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "8d1cc803-71de-4d30-b718-4db7b66ef0ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "# ds.column_names"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "502de03a-ec03-4c54-a903-a742a5a29077",
   "metadata": {},
   "outputs": [],
   "source": [
    "def read_category(cat_id: int) -> str:\n",
    "    return venue_categories[cat_id]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "7108c642-7454-4ed6-931b-e8d0d1aa606b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<duckdb.DuckDBPyConnection at 0x106c52cb0>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "conn.execute(\n",
    "    \"\"\"\n",
    "CREATE OR REPLACE TABLE \n",
    "    events_binned \n",
    "AS\n",
    "SELECT \n",
    "    userId, \n",
    "    \"localTimestamp\",\n",
    "    DATE_PART('epoch', \"localTimestamp\") / 86400 AS dateBin,\n",
    "    venueCategoryId,\n",
    "    ROW_NUMBER() OVER (\n",
    "        PARTITION BY \n",
    "            userId, \n",
    "            DATE_PART('epoch', \"localTimestamp\") / 86400\n",
    "        ORDER BY \n",
    "            \"localTimestamp\" ASC\n",
    "    ) AS seqIndex\n",
    "FROM\n",
    "    raw_events\n",
    "\"\"\"\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "2fd50bcc-f92a-426b-8090-938176b78857",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('Home (private)', 'Coffee Shop')"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "read_category(2), read_category(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af2cf56b-8fbc-4a87-8962-36dd48051125",
   "metadata": {},
   "source": [
    "Lets look for sequences when users were at home and visited the coffee shop after, on some day."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "c7819f1a-3aed-42b8-aa8e-127af0158701",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(270,)]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "conn.execute(\n",
    "    \"\"\"\n",
    "WITH \n",
    "evt1 AS (\n",
    "    SELECT * \n",
    "    FROM events_binned\n",
    "    WHERE venueCategoryId = 2\n",
    "),\n",
    "evt2 AS (\n",
    "    SELECT * \n",
    "    FROM events_binned\n",
    "    WHERE venueCategoryId = 6\n",
    ")\n",
    "SELECT COUNT(*)\n",
    "FROM (\n",
    "    SELECT DISTINCT evt1.userId, evt1.dateBin\n",
    "    FROM evt1\n",
    "    INNER JOIN evt2\n",
    "    ON\n",
    "        evt1.userId = evt2.userId AND\n",
    "        evt1.dateBin = evt2.dateBin AND\n",
    "        evt1.seqIndex < evt2.seqIndex\n",
    ")\n",
    "\"\"\"\n",
    ")\n",
    "conn.fetchall()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2729436b-f13b-4259-afa1-5ab7d1521aac",
   "metadata": {},
   "source": [
    "pretty neat! This could be extended to longer sequences of events but we gotta construct those queries programatically. \n",
    "\n",
    "NOTE: A further optimization could be to construct a separate table for each event category noting all the `seqIndex` values for it. That would be exactly the same data structure as the `id-list` in the original paper. Duckdb filters are pretty quick though, so we skip it. \n",
    "\n",
    "NOTE #2: If a sequence contains multiple instances of a pattern, we still count it once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "ff509d03-50a1-40ef-8be5-4d69830cfc53",
   "metadata": {},
   "outputs": [],
   "source": [
    "def assemble_support_query(pat_sequence: list[int]) -> str:\n",
    "    cte_clauses = []\n",
    "    for i, evt_id in enumerate(pat_sequence):\n",
    "        lines = []\n",
    "        lines.append(f\"view_{i} AS (\")\n",
    "        lines.append(\"\\t\" + \"SELECT t.userId, t.dateBin, min(t.seqIndex) AS seqIndex\")\n",
    "        lines.append(\"\\t\" + \"FROM events_binned AS t\")\n",
    "\n",
    "        if i != 0:\n",
    "            lines.append(\"\\t\" + f\"INNER JOIN view_{i-1}\")\n",
    "            lines.append(\n",
    "                \"\\t\"\n",
    "                + f\"ON view_{i-1}.userId = t.userId AND view_{i-1}.dateBin = t.dateBin AND view_{i-1}.seqIndex < t.seqIndex\"\n",
    "            )\n",
    "\n",
    "        lines.append(\"\\t\" + f\"WHERE t.venueCategoryId = {pat_sequence[i]}\")\n",
    "        lines.append(\"\\t\" + \"GROUP BY t.userId, t.dateBin\")\n",
    "        lines.append(\")\")\n",
    "        cte_clauses.append(\"\\n\".join(lines))\n",
    "    cte_string = \"WITH\\n\" + \",\\n\".join(cte_clauses)\n",
    "\n",
    "    select_string = f\"SELECT COUNT(*) FROM view_{i}\"\n",
    "    return cte_string + \"\\n\" + select_string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "6d0fb125-1089-4dc0-b934-0253d0c74519",
   "metadata": {},
   "outputs": [],
   "source": [
    "# print(assemble_support_query([2, 6, 10]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91e9190d-6ba4-4f87-900c-b184950dc7fa",
   "metadata": {},
   "source": [
    "Let's look for the most frequent event categories."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "cc5dc9e7-7555-4790-9a52-d3d77eb77a9b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bar - 15978\n",
      "Home (private) - 15382\n",
      "Office - 12740\n",
      "Subway - 9348\n",
      "Gym / Fitness Center - 9171\n",
      "Coffee Shop - 7510\n",
      "Food & Drink Shop - 6596\n",
      "Train Station - 6408\n",
      "Park - 4804\n",
      "Neighborhood - 4604\n",
      "Bus Station - 4474\n",
      "Deli / Bodega - 4214\n",
      "Residential Building (Apartment / Condo) - 4185\n",
      "Other Great Outdoors - 4134\n",
      "American Restaurant - 3701\n",
      "College Academic Building - 3479\n",
      "Building - 3474\n",
      "Medical Center - 3366\n",
      "Road - 3207\n",
      "Clothing Store - 2976\n"
     ]
    }
   ],
   "source": [
    "conn.execute(\n",
    "    \"\"\"\n",
    "SELECT \n",
    "    venueCategoryId, COUNT(*) \n",
    "FROM events_binned \n",
    "GROUP BY venueCategoryId\n",
    "ORDER BY COUNT(*) DESC\n",
    "LIMIT 20\n",
    "\"\"\"\n",
    ")\n",
    "res = conn.fetchall()\n",
    "for i, count in res:\n",
    "    print(f\"{read_category(i)} - {count}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3635d124-1bce-49bf-9940-26b0c93c26de",
   "metadata": {},
   "source": [
    "Bars are visited as often as homes. Reasonable. \n",
    "\n",
    "To find out maximal patterns, we need a min support value. The total num of sequences can be counted as"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "6266c4c9-1a38-4334-bb69-0b3660a1a4eb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(93862,)]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "conn.execute(\n",
    "    \"\"\"SELECT COUNT(*) FROM (SELECT DISTINCT userId, dateBin FROM events_binned)\"\"\"\n",
    ")\n",
    "conn.fetchall()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1157c8c3-f36d-48b0-a81c-2a58ee5561de",
   "metadata": {},
   "source": [
    "Lets work with a min support value of 3000."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8784fb9f-b9f2-461c-aa83-a3fcbf75627e",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Rewriting the search routine"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "dd2c6328-37c3-41ac-b536-2e4a91a78e9f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_frequent_events(sup: int):\n",
    "    q = \"\"\"\n",
    "SELECT \n",
    "    venueCategoryId, COUNT(*) AS count\n",
    "FROM events_binned \n",
    "GROUP BY venueCategoryId\n",
    "HAVING COUNT(*) > {sup}\n",
    "\"\"\".format(\n",
    "        sup=sup\n",
    "    )\n",
    "\n",
    "    conn.execute(q)\n",
    "    res = conn.fetchall()\n",
    "    return [row[0] for row in res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "ecb09ee5-79b1-4ff4-98ae-c57986b0574b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def match_seq(seq: list[int], pat: list[int]) -> bool:\n",
    "    \"\"\"find out if the pattern matches the sequence\"\"\"\n",
    "    if len(pat) == 0:\n",
    "        return True\n",
    "    for i in range(len(seq)):\n",
    "        if seq[i] == pat[0]:\n",
    "            return match_seq(seq[i + 1 :], pat[1:])\n",
    "    return False\n",
    "\n",
    "\n",
    "def calc_support(pat: list[int]) -> int:\n",
    "    \"\"\"find the num of sequences that match this pattern\"\"\"\n",
    "    # we replaced the iteration over all sequences with a SQL query to count it\n",
    "    assert len(pat) > 0\n",
    "    conn.execute(assemble_support_query(pat))\n",
    "    return conn.fetchone()[0]\n",
    "\n",
    "\n",
    "def search(\n",
    "    result: list[list[int]], pat: list[int], extend_set: set[int], min_sup: int\n",
    ") -> None:\n",
    "    \"\"\"try to extend the input pattern and check if it is maximal\"\"\"\n",
    "    next_extend_set: set[int] = set()\n",
    "    for evt in extend_set:\n",
    "        if calc_support([*pat, evt]) >= min_sup:\n",
    "            next_extend_set.add(evt)\n",
    "\n",
    "    # recurse on the next set of candidate patterns\n",
    "    for evt in next_extend_set:\n",
    "        search(result, [*pat, evt], next_extend_set, min_sup)\n",
    "\n",
    "    # if no extended patterns are frequent, the current pattern might be maximal\n",
    "    if len(next_extend_set) == 0:\n",
    "        for pat_i in result:\n",
    "            # we gotta check if any existing pattern is a super pattern to this one\n",
    "            if len(pat_i) > len(pat) and match_seq(pat_i, pat):\n",
    "                return\n",
    "\n",
    "        result.append(pat)\n",
    "        # also cut out any existing patterns that are sub patterns to this one\n",
    "        cut_indices = []\n",
    "        for i, pat_i in enumerate(result):\n",
    "            if len(pat_i) < len(pat) and match_seq(pat, pat_i):\n",
    "                cut_indices.append(i)\n",
    "        for i in cut_indices:\n",
    "            result.pop(i)\n",
    "\n",
    "\n",
    "def enumerate_patterns(min_sup: int):\n",
    "    \"\"\"find all patterns that match at least `min_sup` number of sequences\"\"\"\n",
    "    # find the most frequent events, cut out the ones below the threshold\n",
    "    extend_set = set(get_frequent_events(min_sup))\n",
    "    result: list[list[int]] = []\n",
    "    for evt in extend_set:\n",
    "        search(result, [evt], extend_set, min_sup)\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "d35459a4-0b26-40a4-af4d-a0899d324e45",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Home (private)--Bar\n",
      "Home (private)--Home (private)--Home (private)\n",
      "Home (private)--Office\n",
      "Home (private)--Other Great Outdoors\n",
      "Home (private)--Subway\n",
      "Food & Drink Shop--Home (private)\n",
      "Food & Drink Shop--Food & Drink Shop\n",
      "Coffee Shop--Bar\n",
      "Coffee Shop--Office\n",
      "Bus Station--Home (private)\n",
      "Bus Station--Bus Station\n",
      "Office--Subway\n",
      "Office--Bar\n",
      "Office--Home (private)\n",
      "Office--Office\n",
      "Other Great Outdoors--Home (private)\n",
      "Subway--Subway--Subway\n",
      "Subway--Home (private)\n",
      "Subway--Office\n",
      "Subway--Train Station\n",
      "Road--Road\n",
      "Neighborhood--Home (private)\n",
      "Neighborhood--Neighborhood\n",
      "College Academic Building--College Academic Building\n",
      "Deli / Bodega--Home (private)\n",
      "Gym / Fitness Center--Bar\n",
      "Train Station--Subway\n",
      "Train Station--Office\n",
      "Train Station--Train Station\n",
      "Bar--Bar\n",
      "Bar--Home (private)\n",
      "CPU times: user 22.6 s, sys: 181 ms, total: 22.8 s\n",
      "Wall time: 14 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "patterns_mined = enumerate_patterns(500)\n",
    "for pat in patterns_mined:\n",
    "    if len(pat) > 1:\n",
    "        print(\"--\".join(read_category(x) for x in pat))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06a75295-4823-44ce-a979-93438cdbad8c",
   "metadata": {},
   "source": [
    "Hmm, this was not super quick, but also not that slow. By caching the ids for sequences that match a pattern, we can speed up calculating support for sequences created by extending it. \n",
    "\n",
    "We get too few patterns that are not singletons since the venue categories are too diffused. For instance, there are like 20 different types of restaurant. To get a better look at daily traffic, we should probably cluster similar categories. [TODO]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "af506b52-7649-4c79-8fb1-a978ca4e6e29",
   "metadata": {},
   "source": [
    "### Quicker mining"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63605cca-4c71-4125-b26d-3631733a4ef8",
   "metadata": {},
   "source": [
    "Instead of using SQL operations to look for sequences of events, we aggregate all the events in each sequence one time. And then run a numba jitted routine to check for patterns. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "9dbc18f0-e52c-4577-9d99-9de7b86e525e",
   "metadata": {},
   "outputs": [],
   "source": [
    "import awkward as ak\n",
    "import numba as nb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "5af6af74-30eb-4d8a-a600-e73f35877706",
   "metadata": {},
   "outputs": [],
   "source": [
    "conn.execute(\n",
    "    \"\"\"\n",
    "CREATE OR REPLACE TABLE\n",
    "    events_concat \n",
    "AS\n",
    "SELECT \n",
    "    userId, \n",
    "    dateBin, \n",
    "    list(venueCategoryId ORDER BY seqIndex) AS list_events\n",
    "FROM\n",
    "    events_binned\n",
    "GROUP BY \n",
    "    userId, \n",
    "    dateBin\n",
    "\"\"\"\n",
    ")\n",
    "events_concat = conn.table(\"events_concat\").to_arrow_table()\n",
    "awk_data = ak.from_arrow(events_concat)\n",
    "list_events = ak.fill_none(awk_data[\"list_events\"], -1, axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "b94d8f6c-393f-4960-9208-460af9ebf9b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "@nb.njit\n",
    "def _calc_support(list_events: ak.Array, pat: list[int]) -> int:\n",
    "    \"\"\"find the num of sequences that match this pattern\"\"\"\n",
    "    num_pat = len(pat)\n",
    "    count = 0\n",
    "    for events in list_events:\n",
    "        idx_pat = 0\n",
    "        for evt in events:\n",
    "            if evt == pat[idx_pat]:\n",
    "                idx_pat += 1\n",
    "                if idx_pat == num_pat:\n",
    "                    count += 1\n",
    "                    break\n",
    "    return count\n",
    "\n",
    "\n",
    "def calc_support_numba(pat: list[int]) -> int:\n",
    "    \"\"\"find the num of sequences that match this pattern\"\"\"\n",
    "    # we replaced the iteration over all sequences with a SQL query to count it\n",
    "    assert len(pat) > 0\n",
    "    return _calc_support(list_events, np.array(pat))\n",
    "\n",
    "\n",
    "def match_seq(seq: list[int], pat: list[int]) -> bool:\n",
    "    \"\"\"find out if the pattern matches the sequence\"\"\"\n",
    "    if len(pat) == 0:\n",
    "        return True\n",
    "    for i in range(len(seq)):\n",
    "        if seq[i] == pat[0]:\n",
    "            return match_seq(seq[i + 1 :], pat[1:])\n",
    "    return False\n",
    "\n",
    "\n",
    "def search(\n",
    "    result: list[list[int]], pat: list[int], extend_set: set[int], min_sup: int\n",
    ") -> None:\n",
    "    \"\"\"try to extend the input pattern and check if it is maximal\"\"\"\n",
    "    next_extend_set: set[int] = set()\n",
    "    for evt in extend_set:\n",
    "        if calc_support_numba([*pat, evt]) >= min_sup:\n",
    "            next_extend_set.add(evt)\n",
    "\n",
    "    # recurse on the next set of candidate patterns\n",
    "    for evt in next_extend_set:\n",
    "        search(result, [*pat, evt], next_extend_set, min_sup)\n",
    "\n",
    "    # if no extended patterns are frequent, the current pattern might be maximal\n",
    "    if len(next_extend_set) == 0:\n",
    "        for pat_i in result:\n",
    "            # we gotta check if any existing pattern is a super pattern to this one\n",
    "            if len(pat_i) > len(pat) and match_seq(pat_i, pat):\n",
    "                return\n",
    "\n",
    "        result.append(pat)\n",
    "        # also cut out any existing patterns that are sub patterns to this one\n",
    "        cut_indices = []\n",
    "        for i, pat_i in enumerate(result):\n",
    "            if len(pat_i) < len(pat) and match_seq(pat, pat_i):\n",
    "                cut_indices.append(i)\n",
    "        for i in cut_indices:\n",
    "            result.pop(i)\n",
    "\n",
    "\n",
    "def enumerate_patterns(min_sup: int):\n",
    "    \"\"\"find all patterns that match at least `min_sup` number of sequences\"\"\"\n",
    "    # find the most frequent events, cut out the ones below the threshold\n",
    "    extend_set = set(get_frequent_events(min_sup))\n",
    "    result: list[list[int]] = []\n",
    "    for evt in extend_set:\n",
    "        search(result, [evt], extend_set, min_sup)\n",
    "\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "579659a4-615a-4c41-b9fb-fe109bfc7773",
   "metadata": {},
   "source": [
    "All the other routines are copied over from the previous section since I don't want to modularize the code etc. Lets see if we get any quicker! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "a254067d-62a5-4421-bc3f-3f76ac15d068",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Home (private)--Bar\n",
      "Home (private)--Home (private)--Home (private)\n",
      "Home (private)--Office\n",
      "Home (private)--Other Great Outdoors\n",
      "Home (private)--Subway\n",
      "Food & Drink Shop--Home (private)\n",
      "Food & Drink Shop--Food & Drink Shop\n",
      "Coffee Shop--Bar\n",
      "Coffee Shop--Office\n",
      "Bus Station--Home (private)\n",
      "Bus Station--Bus Station\n",
      "Office--Subway\n",
      "Office--Bar\n",
      "Office--Home (private)\n",
      "Office--Office\n",
      "Other Great Outdoors--Home (private)\n",
      "Subway--Subway--Subway\n",
      "Subway--Home (private)\n",
      "Subway--Office\n",
      "Subway--Train Station\n",
      "Road--Road\n",
      "Neighborhood--Home (private)\n",
      "Neighborhood--Neighborhood\n",
      "College Academic Building--College Academic Building\n",
      "Deli / Bodega--Home (private)\n",
      "Gym / Fitness Center--Bar\n",
      "Train Station--Subway\n",
      "Train Station--Office\n",
      "Train Station--Train Station\n",
      "Bar--Bar\n",
      "Bar--Home (private)\n",
      "CPU times: user 5.46 s, sys: 33.9 ms, total: 5.49 s\n",
      "Wall time: 5.53 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "patterns_mined = enumerate_patterns(500)\n",
    "for pat in patterns_mined:\n",
    "    if len(pat) > 1:\n",
    "        print(\"--\".join(read_category(x) for x in pat))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "93c6331d-d928-4fe8-bd6f-fef66abbf091",
   "metadata": {},
   "source": [
    "Half the time, not bad!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b1ce297e-6e6f-40c9-a2f0-cd38b45fd7ee",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "ebba2cc0-7747-4987-b679-75f9867e773d",
   "metadata": {
    "tags": [],
    "toc-hr-collapsed": true
   },
   "source": [
    "### Appendix"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79873293-e33f-4909-915d-431b56e4750c",
   "metadata": {},
   "source": [
    "Code snippets besides the main line. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "3840c736-e7a7-4edc-827b-7ccec3df0436",
   "metadata": {},
   "outputs": [],
   "source": [
    "# import time\n",
    "\n",
    "# for i in range(2, 10):\n",
    "#     st = time.time()\n",
    "#     q = assemble_support_query([24] * i)\n",
    "#     conn.execute(q)\n",
    "#     print(int((time.time() - st) * 1000))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7d7d3bb6-3bf2-49f7-984a-adcfc46411c0",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.9.5 ('base')",
   "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.5"
  },
  "vscode": {
   "interpreter": {
    "hash": "bee13da5dfd8cc2ab21d09493523ce7a17f20d31f50093ee24dd9a0766090f17"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}