SDM/python-jupyter/011-apriori-logcluster.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Apriori and LogCluster\n",
    "\n",
    "See:\n",
    "* http://ristov.github.io/logcluster/\n",
    "* https://github.com/ristov/logcluster\n",
    "* https://github.com/markuskont/kirka/blob/master/algorithms/LogCluster.py\n",
    "\n",
    "## Apriori\n",
    "\n",
    "Apriori is an algorithm for frequent itemset mining on transactional databases. In other words, it is used to find data elements that commonly occur together given a user-defined support value $S$. First, lets define some data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 356,
   "metadata": {},
   "outputs": [],
   "source": [
    "transactions = [\n",
    "    [\"apple\", \"beer\", \"rice\", \"meat\"],\n",
    "    [\"apple\", \"beer\", \"rice\"],\n",
    "    [\"apple\", \"beer\"],\n",
    "    [\"apple\", \"pear\"],\n",
    "    [\"milk\", \"beer\", \"rice\", \"meat\"],\n",
    "    [\"milk\", \"beer\", \"rice\"],\n",
    "    [\"milk\", \"beer\"],\n",
    "    [\"milk\", \"pear\"]\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to know the occurrence count of all items, along with total number of transactions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 357,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'apple': 4, 'beer': 6, 'meat': 2, 'milk': 4, 'pear': 2, 'rice': 4}"
      ]
     },
     "execution_count": 357,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "counters = {}\n",
    "for t in transactions:\n",
    "    for item in t:\n",
    "        if item not in counters:\n",
    "            counters[item] = 1\n",
    "        else:\n",
    "            counters[item] += 1\n",
    "counters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This allows us to calculate support values for each item, relative to total number of transactions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 358,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 358,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "total = len(transactions)\n",
    "total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 359,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'apple': 0.5,\n",
       " 'beer': 0.75,\n",
       " 'meat': 0.25,\n",
       " 'milk': 0.5,\n",
       " 'pear': 0.25,\n",
       " 'rice': 0.5}"
      ]
     },
     "execution_count": 359,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "support = {}\n",
    "for k, v in counters.items():\n",
    "    support[k] = v/total\n",
    "    \n",
    "support"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we will need to find likelyhoods that two items appear together, or confidence values for items $\\{X -> Y\\}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 360,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "df = pd.DataFrame(0, columns = support.keys(), index = support.keys())\n",
    "np.fill_diagonal(df.values, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 361,
   "metadata": {},
   "outputs": [],
   "source": [
    "for x in support.keys():\n",
    "    xy = []\n",
    "    for y in support.keys():\n",
    "        count = 0\n",
    "        for t in transactions:\n",
    "            if x != y:\n",
    "                if x in t and y in t:\n",
    "                    count += 1\n",
    "            #else:\n",
    "            #    count = None\n",
    "        xy.append(count)\n",
    "    df[x] = xy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 362,
   "metadata": {},
   "outputs": [],
   "source": [
    "totals = list(counters.values())\n",
    "confidence = df.divide(totals, axis = \"index\")\n",
    "s = list(support.values())\n",
    "supports_mult = pd.DataFrame(0, columns = support.keys(), index = support.keys())\n",
    "\n",
    "support_outer = np.outer(np.array(s), np.array(s))\n",
    "support_outer = pd.DataFrame(support_outer, columns = support.keys(), index = support.keys())\n",
    "\n",
    "lift = df / support_outer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Subsequently, infrequent itemsets that do not meet support criterium can be dropped."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Logfile clustering\n",
    "\n",
    "This core idea can be extended to identify frequently appearing patterns in unstructured event log messages. Firstly, we will read a syslog file and generate word counter not unlike \"bag of words\" that is used for text data mining."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 446,
   "metadata": {},
   "outputs": [],
   "source": [
    "src = \"/home/jovyan/data/SDM/logs/pacman.log\"\n",
    "splitOn = \"\\s+|\\.|/|\\\"|\\(|\\)|:\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 447,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 448,
   "metadata": {},
   "outputs": [],
   "source": [
    "words = {}\n",
    "lines = 0\n",
    "with open(src) as f:\n",
    "    for line in f:\n",
    "        lines =+ 1\n",
    "        for w in re.split(splitOn, line):\n",
    "            if w != \"\":\n",
    "                if w not in words:\n",
    "                    words[w] = 1\n",
    "                else:\n",
    "                    words[w] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 449,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1979"
      ]
     },
     "execution_count": 449,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 450,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function matplotlib.pyplot.show>"
      ]
     },
     "execution_count": 450,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAY4AAAEKCAYAAAAFJbKyAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAHVZJREFUeJzt3XuUXWWZ5/HvL1W5GC4mIRXEXEjAIIOOI6HE2N4QWm6jhFGxyVLJQnpl7EFbx3EpjGs1ji5XQ3critq40hKBbhqkASXTEwczeEG7uRURCFdTxpgUCUmRQBKoVKrqnGf+2G8lh8qpok5RZ59Lfp+1zjr7vPs9ez+169R5ar/vfveriMDMzGy0JtQ6ADMzayxOHGZmVhEnDjMzq4gTh5mZVcSJw8zMKuLEYWZmFXHiMDOzijhxmJlZRZw4zMysIq21DqAaZs6cGfPnz691GGZmDeWhhx56LiLaXqleUyaO+fPn09HRUeswzMwaiqQ/jqaem6rMzKwiThxmZlYRJw4zM6uIE4eZmVXEicPMzCrixGFmZhVx4jAzs4o4cZiZNYnbH+ri5gc2VX0/VUscklZK2i7psSHln5H0tKTHJf1NSfnlkjrTurNKys9OZZ2SLqtWvGZmje4nDz/DrR2bq76fao4cvx74LnDjYIGk9wFLgLdExD5Js1L5ScCFwJuA1wP/T9IJ6W3fA94PdAEPSloVEU9UMW4zMxtB1RJHRNwjaf6Q4r8AroyIfanO9lS+BLgllf9BUidwalrXGREbACTdkuo6cZiZlaEc9pF3H8cJwLsl3S/pV5LelspnA6XnV12pbLhyMzMbIiKf/eR9k8NWYDqwGHgbcKuk4yifJIPyia3soZG0HFgOMG/evHEJ1sys0UjVP+fI+4yjC7gjMg8ARWBmKp9bUm8OsGWE8oNExIqIaI+I9ra2V7wrsJmZjVHeieMnwOkAqfN7EvAcsAq4UNJkSQuAhcADwIPAQkkLJE0i60BflXPMZmYNIco3yIy7qjVVSboZOA2YKakLuAJYCaxMl+j2AcsiIoDHJd1K1uk9AFwaEYW0nU8DdwEtwMqIeLxaMZuZNbo8OsereVXV0mFWfXyY+l8Hvl6mfDWwehxDMzNrSnl1jnvkuJlZE8mhb9yJw8ysWfiMw8zMKqYcejmcOMzMmkReV1U5cZiZNRP3cZiZWb1x4jAzaxLuHDczs4o1491xzcysSnI64XDiMDNrJh4AaGZmo+c+DjMzq5QHAJqZ2ah5AKCZmVXMfRxmZlZ3nDjMzJpEww8AlLRS0vY029/QdV+QFJJmpteSdI2kTkmPSlpUUneZpPXpsaxa8ZqZNYNGb6q6Hjh7aKGkucD7gU0lxeeQzTO+EFgOXJvqziCbcvbtwKnAFZKmVzFmM7OG1fADACPiHmBnmVVXA1/k5T/jEuDGyNwHTJN0DHAWsCYidkbE88AayiQjMzPLNN3luJLOA56JiEeGrJoNbC553ZXKhisvt+3lkjokdXR3d49j1GZmjSFy6uTILXFImgp8GfircqvLlMUI5QcXRqyIiPaIaG9raxt7oGZmDazR+ziGOh5YADwiaSMwB1gr6XVkZxJzS+rOAbaMUG5mZkM0fB/HUBGxLiJmRcT8iJhPlhQWRcSzwCrgonR11WJgV0RsBe4CzpQ0PXWKn5nKzMysRqp5Oe7NwL3AGyV1SbpkhOqrgQ1AJ/APwH8DiIidwNeAB9Pjq6nMzMxqpLVaG46Ipa+wfn7JcgCXDlNvJbByXIMzM2tCDT8A0MzM8qccesedOMzMmkTTdY6bmVn1ec5xMzMbvWYbAGhmZtXXbAMAzcysitzHYWZmFXMfh5mZ1R0nDjOzJuEBgGZmVjEPADQzs1GLnLrHnTjMzJqIO8fNzGzU3MdhZmYV8wBAMzMbtYY/45C0UtJ2SY+VlP2tpKckPSrpx5Kmlay7XFKnpKclnVVSfnYq65R0WbXiNTNrDo19VdX1wNlDytYAb46ItwC/Ay4HkHQScCHwpvSev5fUIqkF+B5wDnASsDTVNTOzIRr+liMRcQ+wc0jZzyJiIL28D5iTlpcAt0TEvoj4A9kUsqemR2dEbIiIPuCWVNfMzMpo9j6OTwI/Tcuzgc0l67pS2XDlZmZWIzVJHJK+DAwANw0WlakWI5SX2+ZySR2SOrq7u8cnUDOzBhLNOh+HpGXAB4CPxYGfsguYW1JtDrBlhPKDRMSKiGiPiPa2trbxD9zMrAE03QBASWcDXwLOi4ieklWrgAslTZa0AFgIPAA8CCyUtEDSJLIO9FV5xmxmZi/XWq0NS7oZOA2YKakLuILsKqrJwJp0I677IuJTEfG4pFuBJ8iasC6NiELazqeBu4AWYGVEPF6tmM3MGl0eneNVSxwRsbRM8XUj1P868PUy5auB1eMYmplZU2r4AYBmZpY/NfgAQDMzy5Fvq25mZhVr9gGAZmbWgJw4zMyahDvHzcysYm6qMjOzUWv4u+OamVn+fDmumZmNWtPe5NDMzKrIfRxmZjZa7uMwM7OKNd1t1c3MrPE5cZiZNQsPADQzs0ophxGAVUscklZK2i7psZKyGZLWSFqfnqenckm6RlKnpEclLSp5z7JUf32adtbMzMpohs7x64Gzh5RdBtwdEQuBu9NrgHPIpotdCCwHroUs0ZDNHPh24FTgisFkY2ZmB2vozvGIuAfYOaR4CXBDWr4BOL+k/MbI3AdMk3QMcBawJiJ2RsTzwBoOTkZmZkbzDgA8OiK2AqTnWal8NrC5pF5XKhuu3MzMyjiUbnJY7keNEcoP3oC0XFKHpI7u7u5xDc7MrBE0Qx9HOdtSExTpeXsq7wLmltSbA2wZofwgEbEiItojor2trW3cAzczawQN3ccxjFXA4JVRy4A7S8ovSldXLQZ2paasu4AzJU1PneJnpjIzM6uR1mptWNLNwGnATEldZFdHXQncKukSYBNwQaq+GjgX6AR6gIsBImKnpK8BD6Z6X42IoR3uZmZGfjMAVi1xRMTSYVadUaZuAJcOs52VwMpxDM3MrGk19ABAMzPLV+TUPe7EYWbWRJqxc9zMzKokrz4OJw4zs2ZyCA0ANDOzV6muzjgk3T2aMjMzq53dvf0cOWVi1fcz4uW4kqYAU8nGYkznwEnQkcDrqxybmZmNUn+hyJ7eAWYcNqnq+3qlcRz/FfgcWZJ4iAOJYzfwvSrGZWZmFRgoZO1UE1uq3wMxYuKIiG8D35b0mYj4TtWjMTOzMSmmDo4c8sboRo5HxHck/Qkwv/Q9EXFjleIyM7MKFFLimJDDyPFRJQ5J/wgcDzwMFFJxAE4cZmZ1IIrZc90kDqAdOCnyml7KzMwqUtx/xlH9fY22Newx4HXVDMTMzMZuf1NVDpljtGccM4EnJD0A7BssjIjzqhKVmZlVpFhvfRzAV6oZhJmZvTrFeuvjiIhfjedOJf134M/JOtjXkU3cdAxwCzADWAt8IiL6JE0m64Q/BdgB/FlEbBzPeMzMGl3d9XFI2iNpd3r0SipI2j2WHUqaDfwl0B4RbwZagAuBq4CrI2Ih8DxwSXrLJcDzEfEG4OpUz8zMShRz7OMYVeKIiCMi4sj0mAJ8GPjuq9hvK/AaSa1ktzTZCpwO3JbW3wCcn5aXpNek9WcojymuzMwaSJ5NVWMaYxgRPyH7oh/Le58B/o5szvGtwC6y25m8EBEDqVoXMDstzwY2p/cOpPpHjWXfZmbNqu5Gjkv6UMnLCWTjOsY0piPdLHEJsAB4AfgX4JwyVQe3Xy59HrRvScuB5QDz5s0bS2hmZg2r7kaOAx8sWR4ANpJ9+Y/FnwJ/iIhuAEl3AH8CTJPUms4q5gBbUv0uYC7QlZq2XgvsHLrRiFgBrABob2/3QEUzO6QMjs/OoyV/tFdVXTyO+9wELJY0FdgLnAF0AL8APkJ2ZdUy4M5Uf1V6fW9a/3OPYDcze7li+lZsqZc+DklzJP1Y0nZJ2yTdLmnOWHYYEfeTdXKvJbsUdwLZmcKXgM9L6iTrw7guveU64KhU/nngsrHs18ysmRWK+V2OO9qmqh8C/wxckF5/PJW9fyw7jYgrgCuGFG8ATi1Tt7dkv2ZmVkbdXY4LtEXEDyNiID2uB9qqGJeZmVVgsAG/ni7HfU7SxyW1pMfHyUZxm5lZHcizqWq0ieOTwEeBZ8nGXnyE7DYhZmZWB/JsqhptH8fXgGUR8TyApBlkg/g+Wa3AzMxs9PK8O+5ozzjeMpg0ACJiJ3BydUIyM7NKFff3cVR/X6NNHBPSiG9g/xnHaM9WzMysyoopc+QxjmO0X/7fAP5d0m1kt/v4KPD1qkVlZmYVKdThyPEbJXWQ3dhQwIci4omqRmZmZqM2eDluSx11jpMShZOFmVkdqruJnMzMrL4NjuPIo6nKicPMrAnk2VTlxGFm1gTqceS4mZnVsXocAGhmZnWsWIc3OTQzszp24F5V1d+XE4eZWRMo5DhyvCaJQ9I0SbdJekrSk5LeIWmGpDWS1qfn6amuJF0jqVPSo5IW1SJmM7N61jdQBGBSa/W/1mt1xvFt4P9GxInAfwKeJJsS9u6IWAjczYEpYs8BFqbHcuDa/MM1M6tvfYUmThySjgTeQ5pTPCL6IuIFYAlwQ6p2A3B+Wl4C3BiZ+4Bpko7JOWwzs7q2/4yjpQkTB3Ac0A38UNJvJf1A0mHA0RGxFSA9z0r1ZwObS97flcpeRtJySR2SOrq7u6v7E5iZ1Zlmb6pqBRYB10bEycBLHGiWKqdcT08cVBCxIiLaI6K9rc3ToZvZoWXdM7uA5k0cXUBXRNyfXt9Glki2DTZBpeftJfXnlrx/DrAlp1jNzBrCQLGJm6oi4llgs6Q3pqIzyO66uwpYlsqWAXem5VXARenqqsXArsEmLTMzy/T0FXjLnNfWz3wcVfAZ4CZJk4ANwMVkSexWSZcAm4ALUt3VwLlAJ9CT6pqZWYmefQWmTmrJZV81SRwR8TDQXmbVGWXqBnBp1YMyM2tgPf0DtB0+OZd9eeS4mVkTGCgEE3Po3wAnDjOzpjBQDFpbcrinOk4cZmZNoVAMWvO4wyFOHGZmTaG/UKQ1j1mccOIwM2sKhWLkMm0sOHGYmTWFrI/DTVVmZjZKA26qMjOzSgy4qcrMzCpRKAYTfTmumZmN1kAhaPHluGZmNloDRfdxmJnZKBWLQTHwyHEzMxudgWI2t53POMzMbFQKKXG4j8PMzEZlcPa/pr+qSlKLpN9K+tf0eoGk+yWtl/SjNMkTkian151p/fxaxWxmVo8GCoNnHE2eOIDPAk+WvL4KuDoiFgLPA5ek8kuA5yPiDcDVqZ6ZmSX7+zia+ZYjkuYA/xn4QXot4HTgtlTlBuD8tLwkvSatP0N5TKprZtYg+gupqarJzzi+BXwRKKbXRwEvRMRAet0FzE7Ls4HNAGn9rlTfzMyAnr4CAK/Jac7x3BOHpA8A2yPiodLiMlVjFOtKt7tcUoekju7u7nGI1MysMexNiWPqpNZc9leLM453AudJ2gjcQtZE9S1gmqTBn3oOsCUtdwFzAdL61wI7h240IlZERHtEtLe1tVX3JzAzqyM9fVljzdRmPeOIiMsjYk5EzAcuBH4eER8DfgF8JFVbBtyZllel16T1P4+Ig844zMwOVT39Td5UNYIvAZ+X1EnWh3FdKr8OOCqVfx64rEbxmZnVpQNNVfkkjnwaxIYREb8EfpmWNwCnlqnTC1yQa2BmZg1ksHN86sTm7eMwM7NxtDf1cRyKTVVmZjYGPTk3VTlxmJk1uP3jOCY6cZiZ2Sjs7S8wZeIEJjT5yHEzMxsnPX0DuQ3+AycOM7OG19NXyK2ZCpw4zMwa3t6+Qm4d4+DEYWbW8HqcOMzMrBJ7+wq5jeEAJw4zs4bX0+/OcTMzq0DPPp9xmJnZKG3b3cvGHS8xe9prctunE4eZWQPb0P0SxYD3LMxvHiInDjOzBrbumRcAeP20Kbnt04nDzKyBPfbMbmYdMZnj2g7PbZ+1mHN8rqRfSHpS0uOSPpvKZ0haI2l9ep6eyiXpGkmdkh6VtCjvmM3M6tXGHS/xxtcdkes+a3HGMQD8j4j4D8Bi4FJJJ5HN7Hd3RCwE7ubATH/nAAvTYzlwbf4hm5nVp719BQ7L8VJcqM2c41sjYm1a3gM8CcwGlgA3pGo3AOen5SXAjZG5D5gm6ZicwzYzq0t9hSKTJ+b7VV7TPg5J84GTgfuBoyNiK2TJBZiVqs0GNpe8rSuVmZkd8voGikxqOUQSh6TDgduBz0XE7pGqlimLMttbLqlDUkd3d/d4hWlmVtf6BopMaj0EEoekiWRJ46aIuCMVbxtsgkrP21N5FzC35O1zgC1DtxkRKyKiPSLa29ryu57ZzKxWIoLe/kLzJw5JAq4DnoyIb5asWgUsS8vLgDtLyi9KV1ctBnYNNmmZmR3K/rijh5f6CrleiguQb1d85p3AJ4B1kh5OZf8TuBK4VdIlwCbggrRuNXAu0An0ABfnG66ZWX3auOMlAE46Jt/LcXNPHBHxG8r3WwCcUaZ+AJdWNSgzswb00r4CAIdPnpjrfj1y3MysQT2xdRdArpM4gROHmVnDWr/tRQDajpic636dOMzMGlCxGDywcScfOWUOUyb6jMPMzF7Bbze/wAs9/bzrDTNz37cTh5lZA7rlgU1I8N4T8h+35sRhZtZgOjbu5Pa1XZx2QhvTD5uU+/6dOMzMGkjfQJEv3f4o06ZO4ttLT65JDLUYAGhmZmPw3Iv7eN/f/ZI9vQN85YMnceSUfMdvDHLiMDNrAP2FIn+9+in29A7wtfPfzCcWH1uzWJw4zMzq3L91PseVP32Kdc/s4i9OO76mSQOcOMzM6lqxGFx+xzo27ezhW3/2Vs4/ufbTETlxmJnVqdXrtnLN3evZtLOHqz78H+siaYATh5lZXfrO3ev5xprfAbD8Pcfx0fa5r/CO/DhxmJnVkV17+/lf//tx7lj7DOe8+XV8Z+nJtOY8NewrceIwM8vZ8y/1sW+guP/17t5+Vq/bytpNL/Cb9d0UAy44ZQ5XfvgttEwYbhaK2mmYxCHpbODbQAvwg4i4ssYhmZmNSrEYPLF1N2s3Pc9v1j/Hz57YVrbeCUcfzuknzuJjbz+W9504K+coR68hEoekFuB7wPvJ5iB/UNKqiHiitpGZmWUKxWDHi/vYtLOHDc+9xJ7eATZ0v8jTz+5h444enntxHwCTWifwoUWzedv8GfvfO0FwyrHTecOsfGfyG6uGSBzAqUBnRGwAkHQLsARw4jA7hAwUiuzpHRjz+3sHCux4sW/EOrv29rOnt3//6x0v9bG3r7D/9d6+Ajt7+ugbKLJt9z627e5lT28/z+7upbe/+LJtTZk4gTe9/rWccuw0Tj9xFu3zZ3DczMOQ6q/5qRKNkjhmA5tLXncBbx/vnbzQ08cF3793vDdrlrsAtu/uZaAYtQ5lXPUXivQXav8zHT65lQmCo4+cQtsRk3n9tCmc9sZZzJn+GubNmMpxbYcxbeokZkydxIQ67KN4tRolcZQ78i/79EhaDiwHmDdv3ph2MmGCWHj04WN6r1m9aT92OkdMaZQ/8dGZIDHryCm0jPG7eMIEMeuIKSN2OE9qnUDb4ZMZPCmYOqnlZXegbZE4bHJzHddKNcpP3wWUXsQ8B9hSWiEiVgArANrb28f0L8mRUyby9x87ZawxmpkdEurr4uDhPQgslLRA0iTgQmBVjWMyMzskNcQZR0QMSPo0cBfZ5bgrI+LxGodlZnZIaojEARARq4HVtY7DzOxQ1yhNVWZmViecOMzMrCJOHGZmVhEnDjMzq4gTh5mZVUQRtR++P94kdQN/fBWbmAk8N07hjKd6jQvqN7Z6jQvqNzbHVbl6ja3SuI6NiLZXqtSUiePVktQREe21jmOoeo0L6je2eo0L6jc2x1W5eo2tWnG5qcrMzCrixGFmZhVx4ihvRa0DGEa9xgX1G1u9xgX1G5vjqly9xlaVuNzHYWZmFfEZh5mZVcSJo4SksyU9LalT0mU573uupF9IelLS45I+m8q/IukZSQ+nx7kl77k8xfq0pLOqHN9GSetSDB2pbIakNZLWp+fpqVySrkmxPSppUZViemPJcXlY0m5Jn6vVMZO0UtJ2SY+VlFV8jCQtS/XXS1pWpbj+VtJTad8/ljQtlc+XtLfk2H2/5D2npM9AZ4r9VU9tN0xsFf/+xvtvd5i4flQS00ZJD6fyvI/ZcN8V+X3WIsKPrLmuBfg9cBwwCXgEOCnH/R8DLErLRwC/A04CvgJ8oUz9k1KMk4EFKfaWKsa3EZg5pOxvgMvS8mXAVWn5XOCnZDM3Lgbuz+n39yxwbK2OGfAeYBHw2FiPETAD2JCep6fl6VWI60ygNS1fVRLX/NJ6Q7bzAPCOFPNPgXOqdMwq+v1V42+3XFxD1n8D+KsaHbPhvity+6z5jOOAU4HOiNgQEX3ALcCSvHYeEVsjYm1a3gM8STbX+nCWALdExL6I+APQSfYz5GkJcENavgE4v6T8xsjcB0yTdEyVYzkD+H1EjDTws6rHLCLuAXaW2Wclx+gsYE1E7IyI54E1wNnjHVdE/CwiBtLL+8hm1RxWiu3IiLg3sm+dG0t+lnGNbQTD/f7G/W93pLjSWcNHgZtH2kYVj9lw3xW5fdacOA6YDWwued3FyF/cVSNpPnAycH8q+nQ6xVw5ePpJ/vEG8DNJDymb3x3g6IjYCtmHGZhVo9ggmxWy9A+5Ho4ZVH6MahHjJ8n+Ix20QNJvJf1K0rtT2ewUS15xVfL7y/uYvRvYFhHrS8pqcsyGfFfk9llz4jigXNtj7pecSTocuB34XETsBq4FjgfeCmwlO0WG/ON9Z0QsAs4BLpX0nhHq5hqbsumEzwP+JRXVyzEbyXCx5H3svgwMADeloq3AvIg4Gfg88M+Sjsw5rkp/f3n/Xpfy8n9SanLMynxXDFt1mDjGHJ8TxwFdwNyS13OALXkGIGki2Qfhpoi4AyAitkVEISKKwD9woGkl13gjYkt63g78OMWxbbAJKj1vr0VsZMlsbURsSzHWxTFLKj1GucWYOkM/AHwsNaWQmoF2pOWHyPoOTkhxlTZnVS2uMfz+8jxmrcCHgB+VxJv7MSv3XUGOnzUnjgMeBBZKWpD+g70QWJXXzlO76XXAkxHxzZLy0r6B/wIMXuWxCrhQ0mRJC4CFZB1x1YjtMElHDC6Tdaw+lmIYvBJjGXBnSWwXpas5FgO7Bk+hq+Rl/wHWwzErUekxugs4U9L01ERzZiobV5LOBr4EnBcRPSXlbZJa0vJxZMdoQ4ptj6TF6bN6UcnPMt6xVfr7y/Nv90+BpyJifxNU3sdsuO8K8vysvdoe/mZ6kF198Duy/xi+nPO+30V2mvgo8HB6nAv8I7Aula8Cjil5z5dTrE8zDldrjBDbcWRXqjwCPD54bICjgLuB9el5RioX8L0U2zqgvYqxTQV2AK8tKavJMSNLXluBfrL/5i4ZyzEi63PoTI+LqxRXJ1n79uBn7fup7ofT7/gRYC3wwZLttJN9if8e+C5pAHEVYqv49zfef7vl4krl1wOfGlI372M23HdFbp81jxw3M7OKuKnKzMwq4sRhZmYVceIwM7OKOHGYmVlFnDjMzKwiThxmdULSaZL+tdZxmL0SJw6zGhkcNGbWaJw4zMZA0hcl/WVavlrSz9PyGZL+SdJSZfMwPCbpqpL3vSjpq5LuB96hbB6JpyT9huxWFoP13qsD8zv8dnDkvlk9cOIwG5t7yO6SCtno4MPT/YPeRTZy9yrgdLIb9b1N0uAtrg8jm7vh7UAH2b2YPpi29bqS7X8BuDQi3prW7a3uj2M2ek4cZmPzEHBKOhPYB9xLlkDeDbwA/DIiuiOb8+ImsomBAApkN6cDOBH4Q0Ssj+wWDv9Usv1/A76ZzmqmxYG5M8xqzonDbAwiop9sVsSLgX8Hfg28j+x24JtGeGtvRBRKNzXM9q8E/hx4DXCfpBPHIWyzceHEYTZ295A1Kd1Dljg+RXbDufuA90qamTrAlwK/KvP+p8gmADo+vV46uELS8RGxLiKuImvScuKwuuHEYTZ2vyab//neyOYC6QV+Hdktqy8HfkG6Y2pEHHQ77YjoBZYD/yd1jpdOe/u51LH+CFn/xk+Hvt+sVnx3XDMzq4jPOMzMrCJOHGZmVhEnDjMzq4gTh5mZVcSJw8zMKuLEYWZmFXHiMDOzijhxmJlZRf4/R4uYfbTzTsQAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7fb3b4349a20>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "plt.plot(sorted(list(words.values())))\n",
    "plt.ylabel('count')\n",
    "plt.xlabel('words')\n",
    "plt.show"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "After counting distinct words, we see that majority of the words are infrequent. So we will define a threshold and drop those words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 451,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "84"
      ]
     },
     "execution_count": 451,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sup = 50\n",
    "for word in list(words.keys()):\n",
    "    if words[word] < sup:\n",
    "        del words[word]\n",
    "        \n",
    "fwords = list(words.keys())\n",
    "len(fwords)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we will need to do a second pass over input file to create cluster candidates. Only frequent words will be kept in cluster candidates while infrequent words are replaced by wildcards."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 452,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json\n",
    "import hashlib\n",
    "\n",
    "candidates = {}\n",
    "lines = 0\n",
    "with open(src) as f:\n",
    "    for line in f:\n",
    "        lines += 1\n",
    "        candidate = []\n",
    "        wildcards = []\n",
    "        noWildcards = 0\n",
    "        for w in re.split(splitOn, line):\n",
    "            if w != \"\" and w in fwords:\n",
    "                candidate.append(w)\n",
    "                wildcards.append(noWildcards)\n",
    "                noWildcards = 0\n",
    "            else:\n",
    "                noWildcards += 1\n",
    "        ident = hashlib.md5(json.dumps(sorted(candidate)).encode()).hexdigest()\n",
    "        \n",
    "        if ident not in candidates:\n",
    "            candidates[ident] = {\n",
    "                \"count\": 1,\n",
    "                \"words\": candidate,\n",
    "                \"wildcards\": wildcards\n",
    "            }\n",
    "        else:\n",
    "            candidates[ident][\"count\"] += 1\n",
    "        \n",
    "        #if lines%1000==0:\n",
    "        #    print(ident)\n",
    "        #    print(wildcards)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 453,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1151"
      ]
     },
     "execution_count": 453,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(candidates)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 454,
   "metadata": {},
   "outputs": [],
   "source": [
    "counts = []\n",
    "for k, v in candidates.items():\n",
    "    counts.append(v[\"count\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 455,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function matplotlib.pyplot.show>"
      ]
     },
     "execution_count": 455,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYkAAAEKCAYAAADn+anLAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAGI5JREFUeJzt3X2UXXV56PHvk5kkE14CiYQYXmJAsxS0CN5cFkLrqqCIFIVSamHpNSpd6erti962q8Llri5b26q9rdZ6XbVc36KXKhahULTlYgTRqwsIgsirRJR3SHjLREgmc+Y894+9JzlM5pDJZPbsfWa+n7Vmzd777DPn+WVP9jO/l/37RWYiSdJ45tQdgCSpuUwSkqSuTBKSpK5MEpKkrkwSkqSuTBKSpK5MEpKkrkwSkqSuTBKSpK766w5gIg466KBcsWJF3WFIUk+55ZZbnszMJXvzM3oiSaxYsYL169fXHYYk9ZSIeGBvf0alSSIifg5sAUaAVmauiojFwKXACuDnwDsy85kq45AkTc509Em8MTOPzcxV5f4FwLrMXAmsK/clSQ1UR8f1mcDacnstcFYNMUiSJqDqJJHA/42IWyJiTXlsaWY+BlB+P7jiGCRJk1R1x/VJmfloRBwMXBsR90z0jWVSWQOwfPnyquKTJL2ISmsSmflo+X0jcAVwPPBERCwDKL9v7PLeizNzVWauWrJkr0ZwSZImqbIkERH7RsT+o9vAqcAdwFXA6vK01cCVVcUgSdo7VTY3LQWuiIjRz/nnzPyPiLgZ+FpEnA88CPxmhTFIUk+65/FBvnH7Y7znxBW8ZL/5tcVRWZLIzPuB145z/CnglKo+V5Jmgnsf38Knvr2BM489tNYk4dxNktRgc6Lmz6/34yVJ42lnAlA22dfGJCFJDVTmCGquSJgkJKmJdiQJm5skSWONNjfNsblJkjRW1h1AySQhSU1kc5MkqZvE5iZJUhdtaxKSpG52DoG1JiFJGmO0ucmahCRpFz4nIUnqKken5bC5SZI01uhzEtYkJEm7cO4mSVJX6bQckqRufE5CktTVjj4JO64lSWPtGN1U813aJCFJDWTHtSSpq51PXNvcJEkaw5qEJKmr0Y5rh8BKknYxunypQ2AlSbvIhqxfapKQpAazJiFJ2oXTckiSumo7ukmS1M3ORYesSUiSxhh9mG6OfRKSpLHa1iQkSV01ZAysSUKSGiipf/grTEOSiIi+iLg1Iq4u94+IiBsj4r6IuDQi5lUdgyT1msz6h7/C9NQk3g/c3bH/MeATmbkSeAY4fxpikKSe0s6sffgrVJwkIuIw4NeAz5b7AZwMXFaeshY4q8oYJKkXzZbmpr8H/hRol/svAZ7NzFa5/zBw6HhvjIg1EbE+ItZv2rSp4jAlqVky61+6FCpMEhFxBrAxM2/pPDzOqeN24WfmxZm5KjNXLVmypJIYJampkmxETaK/wp99EvD2iDgdGAAWUtQsDoyI/rI2cRjwaIUxSFJPypzhzU2ZeWFmHpaZK4BzgW9n5juB64BzytNWA1dWFYMk9arMnNnNTS/ig8AfRcQGij6Kz9UQgyQ1WjEEtu4oqm1u2iEzrweuL7fvB46fjs+VpF7Vzvqn5ACfuJakRkpmwXMSkqTJyaT+xSQwSUhSY82WaTkkSXuonc14TsIkIUkNVDxxXT+ThCQ1UPHEdf1pwiQhSQ3UlOckTBKS1EDF8qX1ZwmThCQ1kh3XkqQubG6SJHXVnsUT/EmSdsOahCSpq5F0CKwkqYtM6GtAVcIkIUkN1M60uUmSNL6RdjrBnyRpfJkwpwFVCZOEJDWQzU2SpK5sbpIkddVOFx2SJHWRmcxpwB26ASFIksYaSZubJEld2NwkSeoqHd0kSerG0U2SpK7amT5MJ0kaX9upwiVJ3bRtbpIkddN2CKwkqZu2E/xJkrpxgj9JUlczvrkpIgYi4qaI+FFE3BkRf14ePyIiboyI+yLi0oiYV1UMktSr2u2Z/8T1EHByZr4WOBY4LSJOAD4GfCIzVwLPAOdXGIMk9aQZ39yUhV+Uu3PLrwROBi4rj68FzqoqBknqVTO+uQkgIvoi4jZgI3At8FPg2cxslac8DBza5b1rImJ9RKzftGlTlWFKUuO0E/oaUJWoNElk5khmHgscBhwPHDXeaV3ee3FmrsrMVUuWLKkyTElqnHY7aUBFYnpGN2Xms8D1wAnAgRHRX750GPDodMQgSb1kxjc3RcSSiDiw3F4AvAm4G7gOOKc8bTVwZVUxSFKvakpzU//uT5m0ZcDaiOijSEZfy8yrI+Iu4KsR8ZfArcDnKoxBknrSSEOamypLEpl5O3DcOMfvp+ifkCR1sWXbMPvPr/Lv+InxiWtJaph2O9ky1OKABXPrDsUkIUlNs2WoRSYsNElIksYa3DoM9FCSiIh1EzkmSdp7m8sk0YTmphftFYmIAWAf4KCIWASM9rUvBA6pODZJmpV21CQGGp4kgN8BPkCREG5hZ5IYBD5dYVySNGsNbuuRmkRmfhL4ZET8QWZ+appikqRZbXBrMb3d/gP1D4GdUASZ+amIOBFY0fmezPxSRXFJ0qw11BoBYMG8vpojmWCSiIgvAy8HbgNGysMJmCQkaYoNjxTznvb30LQcq4CjM3PcGVslSVNnpF3capswd9NEn5O4A3hplYFIkgqt9mhNov5H2SZakzgIuCsibqJYlhSAzHx7JVFJ0iw20m4D0N9Xf01iokniQ1UGIUnaabQm0deAaWAnOrrpO1UHIkkqjLSTOQFzGtAnMdHRTVvYuczoPGAu8FxmLqwqMEmarVrtbER/BEy8JrF/535EnIVrQkhSJUba2YiRTTDJWWAz81+Bk6c4FkkSMDzSbsQzEjDx5qazO3bnUDw34TMTklSBkXbS14CRTTDx0U1v69huAT8HzpzyaCRJZZ9EDyWJzHxv1YFIkgojI83puJ7ookOHRcQVEbExIp6IiK9HxGFVBydJs1GrBzuuvwBcRbGuxKHAv5XHJElTbKTdbsTT1jDxJLEkM7+Qma3y64vAkgrjkqRZqxdrEk9GxLsioq/8ehfwVJWBSdJs1RppTsf1RJPE+4B3AI8DjwHnAHZmS1IFhlojDMytf8EhmPgQ2A8DqzPzGYCIWAz8LUXykCRNoW3Dbeb399DoJuCY0QQBkJlPA8dVE5IkzW5DrRHm9zejJjHRJDEnIhaN7pQ1ifpX6JakGWio1WZgbjNqEhO90f8d8P2IuIxiOo53AH9VWVSSNIsNtdqNqUlM9InrL0XEeopJ/QI4OzPvqjQySZqliuam3qpJUCYFE4MkVWxouM38hjQ3NSMKSdIO24Z7r+N6j0XE4RFxXUTcHRF3RsT7y+OLI+LaiLiv/L5odz9LkmaLdjvZMtRi4UAzxgZVWZNoAX+cmUcBJwC/FxFHAxcA6zJzJbCu3JckAb/Y3iITFi6YW3coQIVJIjMfy8wflttbgLspJgc8E1hbnrYWOKuqGCSp12x+fhiYBUmiU0SsoHj47kZgaWY+BkUiAQ6ejhgkqRcMbiuTxMAsSRIRsR/wdeADmTm4B+9bExHrI2L9pk2bqgtQkhpk89YiSRwwG2oSETGXIkFckpmXl4efiIhl5evLgI3jvTczL87MVZm5askSZyWXNDsMbm0BsHDBDO+4jogAPgfcnZkf73jpKmB1ub0auLKqGCSp1wxubVZzU5Wp6iTgvwA/jojbymP/Hfgo8LWIOB94EPjNCmOQpJ5wyY0P8JdX383wSBuAA/aZ4UkiM79HMYXHeE6p6nMlqRfd8UjRZXv+Lx/B4Yv3mRU1CUnSBLVG2izaZy4Xnn5U3aG8gNNySFIDDI+06e9r3i25eRFJ0iw03E7m9jVjXetOJglJaoDhVpu51iQkSeNptdMkIUkaX9EnYXOTJGkcwyM2N0mSuhgeseNaktRFy5qEJKmb7SNJ/5zm3ZKbF5EkzUKtkTbz+m1ukiSNY+vwCPP7++oOYxcmCUlqgMGtw41ZaKiTSUKSatZuJ1uGWo1Z17qTSUKSarZlqEUmLBxo3sTcJglJqtlgw9a17mSSkKSabR5dstQkIUkaq2nrWncySUhSzb634UnA5iZJ0ji+9IMHAHjpAQM1R7Irk4Qk1SgzeX57i/OOX87ifefVHc4uTBKSVKOtwyO0E5Yv3qfuUMZlkpCkGg1ubQHN7I8Ak4Qk1Wrn8NfmPUgHJglJqtXgtuY+SAcmCUmq1ebnm/uMBJgkJKlWTz+3HbAmIUkax6XrHwJgUQOHv4JJQpJq1RfB4n3nWZOQJO1qcNswq162qO4wujJJSFJNMpOnn9veyNlfR5kkJKkmF3z9x2zcMsSifWZhkoiIz0fExoi4o+PY4oi4NiLuK783t44lSRW7/ZHNALz79SvqDeRFVFmT+CJw2phjFwDrMnMlsK7cl6RZacu2Yc4+7lAOb+i8TVBhksjMG4Cnxxw+E1hbbq8Fzqrq8yWp6TZvHW50fwTAdE8WsjQzHwPIzMci4uBp/nxJqtVnv3s/F99wPwBbtrVMEpMVEWuANQDLly+vORpJmhrf2/AkI+3k1FcvZU4EZx17SN0hvajpThJPRMSyshaxDNjY7cTMvBi4GGDVqlU5XQFKUpUGtw5z1LKFfOTsY+oOZUKmewjsVcDqcns1cOU0f74k1aroh2hsI84uqhwC+xXgB8ArI+LhiDgf+Cjw5oi4D3hzuS9Js8IHL7udh57e2tgpOMZTWTrLzPO6vHRKVZ8pSU21bXiES9c/xJFL9uWMY5rdD9HJJ64laRqMLi703hNXcNIrDqo5mokzSUjSNBhdy7rpQ17H6p3eE0nqQY88u5W/u+ZeNm4ZAnovSViTkKQKXX/vRi6/9REefuZ5jjnsAI5etrDukPaINQlJqtBoM9O/v/8NLJjXV3M0e86ahCRVaPPWYeb1zWFgbm/ebq1JSFIFtrfafOY7P+WGn2xi4YJ+IqLukCbFJCFJFbj1wWf4+LU/YV7/HE55Ve/OZWqSkKQKPLu1eC7i8t89kdccekDN0UxebzaSSVLDDZZJopem4BiPNQlJmiKZyb/d/hhP/2KIG39WrLm2cMAkIUkCHnp6K3/4lVt37B+8/3z2G+jt22xvRy9JDfLUc8VT1f9w3nH8yisOYp/5ffTN6c1RTaNMEpI0RQa3FQ/OHXrgAIv2nVdzNFPDJCFJk7S91eYH9z/F9lYbgPUPFP0Qvd5Z3ckkIUmT9B93Pv6CPgiA/jnBkv0Gaopo6pkkJGmSNg5uA+Cra05gv/nF7XTRvvM4YB9rEpI06w1uaxEBx69YzJwe76DuxiQhSWM8+NTzbBka3u15Dzz1HPvP75+xCQJMEpL0Aj95YgunfuKGCZ//8iX7VhhN/UwSktThkWe3AnDBW1/FEQftPgGsPHi/qkOqlUlCkjqMzrn0pqOW8ooZngAmwiQhaUYaao2wdfvIHr/viXLE0kx61mFvmCQkzTjbW21O/Mi3eeq57ZN6/5yAhQu8PYJJQtIM9Ozz23nque2cccwy/tPLFu3x+5cv3of5/b23HnUVTBKSZpzBbUW/wlte/VLe9tpDao6mt7nokKQZZ3PZ+bzQfoW9Zk1CUle3PvgM7/3izTsmsOsVrXYCdj5PBZOEpK7ufHSQZ58f5l0nLGfB3N5qo184MJfXHLKw7jB6nklCUlejbfv/49eOZqDHkoSmhn0SkrravHWYef1zTBCz2IyuSVx0xY+5qVyMXNKe27hliIUDtuvPZrUkiYg4Dfgk0Ad8NjM/WsXnHHLgAlYu9bF6abJWLt2P/7xicd1hqEbTniQiog/4NPBm4GHg5oi4KjPvmurP+r03vmKqf6QkzSp19EkcD2zIzPszczvwVeDMGuKQJO1GHUniUOChjv2Hy2OSpIapI0mMt4RT7nJSxJqIWB8R6zdt2jQNYUmSxqojSTwMHN6xfxjw6NiTMvPizFyVmauWLFkybcFJknaqI0ncDKyMiCMiYh5wLnBVDXFIknZj2kc3ZWYrIn4fuIZiCOznM/PO6Y5DkrR7tTwnkZnfBL5Zx2dLkibOaTkkSV1F5i4DixonIjYBD0zy7QcBT05hOE1gmXqDZeoNM7lML8vMvRr50xNJYm9ExPrMXFV3HFPJMvUGy9QbLNOLs7lJktSVSUKS1NVsSBIX1x1ABSxTb7BMvcEyvYgZ3ychSZq82VCTkCRN0oxOEhFxWkTcGxEbIuKCuuOZiIg4PCKui4i7I+LOiHh/eXxxRFwbEfeV3xeVxyMi/qEs4+0R8bp6S9BdRPRFxK0RcXW5f0RE3FiW6dJymhYiYn65v6F8fUWdcXcTEQdGxGURcU95vV7f69cpIv5b+Xt3R0R8JSIGeu06RcTnI2JjRNzRcWyPr0tErC7Pvy8iVtdRlo5YxivT/yx/926PiCsi4sCO1y4sy3RvRLyl4/ie3xMzc0Z+UUz58VPgSGAe8CPg6LrjmkDcy4DXldv7Az8Bjgb+BrigPH4B8LFy+3Tg3ylm1z0BuLHuMrxI2f4I+Gfg6nL/a8C55fZngN8tt/8r8Jly+1zg0rpj71KetcBvl9vzgAN7+TpRTNn/M2BBx/V5T69dJ+ANwOuAOzqO7dF1ARYD95ffF5XbixpWplOB/nL7Yx1lOrq8380Hjijvg32TvSfWfkEr/Ed9PXBNx/6FwIV1xzWJclxJsYrfvcCy8tgy4N5y+5+A8zrO33Fek74oZvtdB5wMXF3+p3yy45d8x/WimNfr9eV2f3le1F2GMeVZWN5QY8zxnr1O7FzrZXH573418JZevE7AijE31D26LsB5wD91HH/BeU0o05jXfh24pNx+wb1u9DpN9p44k5uben5xo7L6fhxwI7A0Mx8DKL8fXJ7WK+X8e+BPgXa5/xLg2cxslfudce8oU/n65vL8JjkS2AR8oWxC+2xE7EsPX6fMfAT4W+BB4DGKf/db6O3rNGpPr0vjr9cY76OoEcEUl2kmJ4kJLW7UVBGxH/B14AOZOfhip45zrFHljIgzgI2ZeUvn4XFOzQm81hT9FNX/f8zM44DnKJoxuml8mcp2+jMpmigOAfYF3jrOqb10nXanWxl6pmwRcRHQAi4ZPTTOaZMu00xOEhNa3KiJImIuRYK4JDMvLw8/ERHLyteXARvL471QzpOAt0fEzynWND+ZomZxYESMzkTcGfeOMpWvHwA8PZ0BT8DDwMOZeWO5fxlF0ujl6/Qm4GeZuSkzh4HLgRPp7es0ak+vSy9cL8oO9TOAd2bZhsQUl2kmJ4meXNwoIgL4HHB3Zn6846WrgNERFqsp+ipGj7+7HKVxArB5tFrdFJl5YWYelpkrKK7DtzPzncB1wDnlaWPLNFrWc8rzG/VXXGY+DjwUEa8sD50C3EUPXyeKZqYTImKf8vdwtEw9e5067Ol1uQY4NSIWlTWsU8tjjRERpwEfBN6emc93vHQVcG45+uwIYCVwE5O9J9bdwVRxR8/pFKODfgpcVHc8E4z5lymqgLcDt5Vfp1O09a4D7iu/Ly7PD+DTZRl/DKyquwy7Kd+vsnN005HlL+8G4F+A+eXxgXJ/Q/n6kXXH3aUsxwLry2v1rxSjYHr6OgF/DtwD3AF8mWKETE9dJ+ArFH0qwxR/PZ8/metC0c6/ofx6bwPLtIGij2H0PvGZjvMvKst0L/DWjuN7fE/0iWtJUlczublJkrSXTBKSpK5MEpKkrkwSkqSuTBKSpK5MEtIeiogPRcSflNt/ERFvGuecX41yttsX+TnHRsTpVcUpTYX+3Z8iqZvM/LO9ePuxwCrgm1MUjjTlrEloxouId5dz7v8oIr4cEW8r1z+4NSK+FRFLy/M+VM7bf31E3B8Rf9jxMy4q5+H/FvDKjuNfjIhzyu3Tyvn9vwec3XHO8RHx/fLzvh8RryyfeP0L4Lci4raI+K2I2Lf8/JvLc8+crn8jqRtrEprRIuLVFE+fnpSZT0bEYoon2k/IzIyI36aYnfaPy7e8CngjxVoe90bEPwLHUExhcBzF/5kfUsyO2vk5A8D/ppiXagNwacfL9wBvyMxW2TT115n5GxHxZxRP+P5++TP+mmJqi/eVC8jcFBHfysznpvrfRZook4RmupOByzLzSYDMfDoifgm4tJzobR7FuhCjvpGZQ8BQRGwElgK/AlyR5fw4ETHefDevopgc777ynP8DrClfOwBYGxErKRLU3C6xnkoxEeKflPsDwHLg7kmUW5oSNjdppgt2nQ75U8D/ysxfAn6H4mY8aqhje4Sdf0hNZP6abud8GLguM18DvG3M542N9Tcy89jya3lmmiBUK5OEZrp1wDsi4iVQrHVM8Zf9I+XrE1m7+Abg1yNiQUTsT3GjH+se4IiIeHm5f17Ha52f956O41somrVGXQP8QTkDKxFx3ARikyplktCMlpl3An8FfCcifgR8HPgQ8C8R8V2KJTd39zN+SNHHcBvFOh/fHeecbRTNS98oO64f6Hj5b4CPRMT/o1hneNR1wNGjHdcUNY65wO1RLHj/4T0srjTlnAVWktSVNQlJUlcmCUlSVyYJSVJXJglJUlcmCUlSVyYJSVJXJglJUlcmCUlSV/8fWmkDCrxIl+gAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7fb3b4146ac8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.plot(sorted(counts))\n",
    "plt.ylabel('count')\n",
    "plt.xlabel('candidate')\n",
    "plt.show"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can observe a similar case for candidate counters as we did for words - only a small subset of candidates occur most amount of time. We can now use the same support values as before, or define a new one to repeat dropping infrequent items."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 456,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "40"
      ]
     },
     "execution_count": 456,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sup = 10\n",
    "for k in list(candidates.keys()):\n",
    "    v = candidates[k]\n",
    "    if v[\"count\"] < sup:\n",
    "        del candidates[k]\n",
    "clusters = candidates\n",
    "len(clusters)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 457,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2017-12-21 20 29] [ALPM] installed \n",
      "[2017-12-21 20 29] [ALPM] installed 2 ** \n",
      "[2017-12-21 20 29] [ALPM] installed 1 ** \n",
      "[2017-12-21 20 29] [ALPM-SCRIPTLET] \n",
      "[2017-12-21 20 29] [ALPM-SCRIPTLET] -> Running build hook \n",
      "[2017-12-21 20 39] [ALPM] installed 0 ** \n",
      "[2017-12-21 20 39] [ALPM] installed 1 ** \n",
      "[2017-12-21 20 39] [ALPM] installed 1 ** 0 \n",
      "[2017-12-21 20 39] [ALPM] installed 2 ** 0 \n",
      "[2017-12-21 20 39] [ALPM] installed 2 ** \n",
      "[2017-12-21 20 39] [ALPM-SCRIPTLET] \n",
      "[2017-12-21 20 39] [ALPM] installed 1 ** 1 \n",
      "[2017-12-21 20 39] [ALPM] installed 1 ** 2 \n",
      "[2017-12-21 20 39] [ALPM] installed \n",
      "[2017-12-21 20 39] [ALPM] installed 3 ** 26 \n",
      "[2017-12-21 20 39] [ALPM-SCRIPTLET] -> Running build hook \n",
      "[2017-12-21 20 40] [ALPM] running hook' * \n",
      "[2017-12-21 21 [PACMAN] * Running 'pacman -Sy \n",
      "[2017-12-21 21 [PACMAN] * synchronizing package lists \n",
      "[2017-12-22 21 [ALPM-SCRIPTLET] * -> Running build hook \n",
      "[2017-12-23 16 22] [ALPM-SCRIPTLET] \n",
      "[2017-12-30 00 11] [ALPM-SCRIPTLET] -> Running build hook \n",
      "[2018-01-02 17 [ALPM-SCRIPTLET] * -> Running build hook \n",
      "[2018-01-03 16 09] [ALPM] installed 0 ** \n",
      "[2018-01-03 16 09] [ALPM] installed 1 ** \n",
      "[2018-01-03 16 09] [ALPM] installed 6 ** \n",
      "09 * [ALPM-SCRIPTLET] * -> Running build hook \n",
      "[2018-01-08 09 37] [ALPM-SCRIPTLET] -> Running build hook \n",
      "[2018-01-09 21 50] [ALPM-SCRIPTLET] -> \n",
      "[2018-01-11 09 40] [ALPM-SCRIPTLET] -> Running build hook \n",
      "[2018-01-11 22 [ALPM-SCRIPTLET] * -> Running build hook \n",
      "[2018-01-16 15 14] [ALPM] upgraded 1 ** -> ** 1 \n",
      "[2018-01-16 15 14] [ALPM-SCRIPTLET] -> Running build hook \n",
      "[2018-01-16 15 [ALPM] * running hook' * \n",
      "[2018-01-24 09 45] [ALPM-SCRIPTLET] -> Running build hook \n",
      "[2018-01-26 09 40] [ALPM] running hook' * \n",
      "[2018-01-26 09 40] [ALPM-SCRIPTLET] -> Running build hook \n",
      "[2018-02-03 01 05] [ALPM-SCRIPTLET] -> Running build hook \n",
      "[2018-02-08 09 45] [ALPM] running hook' * \n",
      "[2018-02-08 09 45] [ALPM-SCRIPTLET] -> Running build hook \n"
     ]
    }
   ],
   "source": [
    "for cluster in list(clusters.values()):\n",
    "    i = 0\n",
    "    wildcards = cluster['wildcards']\n",
    "    for word in cluster['words']:\n",
    "        wc = wildcards[i]\n",
    "        print(word, end=' ')\n",
    "        if wc > 0:\n",
    "            print('*'*wc, end=' ')\n",
    "        i += 1\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now run another pass over the data to report all infrequent log messages as outliers.\n",
    "\n",
    "> Note that this is an extremley simplified version of the algorithm. Refer to links in the beginning of this notebook for more thorough explanation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}