Trace-Clustering-with-Python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation result of article : Trace Clustering based on Conserved Patterns: Towards Achieving Better Process Models"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Maximal Pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "MPS [{'a': 3, 'b': 3, 'bc': 2, 'bcd': 2, 'c': 2, 'cd': 2, 'd': 2}, {'d': 2, 'da': 2, 'dab': 2, 'dabc': 2, 'a': 2, 'ab': 2, 'abc': 2, 'b': 4, 'bc': 2, 'c': 2}, {'b': 6, 'bb': 4, 'bbb': 2, 'bbbc': 2, 'bbc': 2, 'bc': 2, 'c': 3, 'a': 2}, {'a': 4, 'aa': 2, 'b': 2, 'c': 3, 'cc': 2}, {'a': 4, 'aa': 2, 'c': 6, 'cd': 2, 'cdc': 2, 'd': 6, 'dc': 3, 'b': 5, 'cb': 2, 'db': 2, 'e': 2, 'bd': 2}]\n"
     ]
    }
   ],
   "source": [
    "#dictionnary of Maximal Pair\n",
    "MPS = []\n",
    "Voisinages = []\n",
    "Log = [\"faabcdbbcda\", \"dabcdabcbb\", \"bbbcdbbbccaa\", \"aaadabbccc\", \"aaacdcdcbedbccbadbdebdcg\"]\n",
    "\n",
    "for Trace in Log:\n",
    "    MP = dict()\n",
    "    Seqs = []\n",
    "    k = 0\n",
    "    Voisinage = []\n",
    "    for i in range(len(Trace)):\n",
    "        for j in range(len(Trace)):\n",
    "            seq = Trace[i:j+1]\n",
    "            Seqs.append(seq)\n",
    "            if(j+1>=len(Trace)):\n",
    "                vd = \"\"\n",
    "            else:\n",
    "                vd = Trace[j+1]\n",
    "            if(i-1<0):\n",
    "                vg = \"\"\n",
    "            else: \n",
    "                vg = Trace[i-1]\n",
    "            if(seq!=\"\"):\n",
    "                Voisinage.append([seq])\n",
    "                Voisinage[k].append([vg , vd])\n",
    "                k+= 1\n",
    "            if(Seqs.count(seq)>=2 and seq!=\"\"):\n",
    "                MP[seq] = int(Seqs.count(seq))\n",
    "    MPS.append(MP)\n",
    "    Voisinages.append(Voisinage)\n",
    "\n",
    "print(\"MPS\", MPS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Maximal Repeat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "MRS [{'a', 'b', 'bcd'}, {'dabc', 'b'}, {'bb', 'bbbc', 'a', 'b', 'c'}, {'a', 'b', 'c', 'aa', 'cc'}, {'bd', 'cdc', 'e', 'a', 'd', 'b', 'db', 'c', 'aa', 'dc', 'cb'}]\n"
     ]
    }
   ],
   "source": [
    "MRS = []\n",
    "l = 0 \n",
    "for MP in MPS:\n",
    "    MR = {k for k, v in MP.items() if v == MP[max(MP, key=MP.get)]}\n",
    "    for i in range(len(Voisinages[l])):\n",
    "        cd = True\n",
    "        for j in  range(len(Voisinages[l])):\n",
    "            if(Voisinages[l][i][0]==Voisinages[l][j][0] and i!=j and Voisinages[l][i][0] not in MR):\n",
    "                if(Voisinages[l][i][1][0] == Voisinages[l][j][1][0] or Voisinages[l][i][1][1] == Voisinages[l][j][1][1]):\n",
    "                    break\n",
    "                MR.add(Voisinages[l][i][0])\n",
    "    MRS.append(MR)\n",
    "    l+=1\n",
    "\n",
    "print(\"MRS\",MRS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Super Maximal Repeat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SMRS [{'a', 'bcd'}, {'dabc'}, {'bbbc', 'a'}, {'aa', 'b', 'cc'}, {'bd', 'cdc', 'e', 'db', 'aa', 'cb'}]\n"
     ]
    }
   ],
   "source": [
    "SMRS = []\n",
    "for e in MRS:\n",
    "    SMR = e.copy()\n",
    "    for i in e:\n",
    "        for j in e:\n",
    "            if(i!=j):\n",
    "                if(i in j and i in SMR):\n",
    "                    SMR.remove(i)\n",
    "    SMRS.append(SMR)\n",
    "                \n",
    "print(\"SMRS\",SMRS)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Near Super Maximal Repeat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "NSMR [{'a', 'b', 'bcd'}, {'dabc', 'b'}, {'bbbc', 'a', 'c'}, {'a', 'b', 'c', 'aa', 'cc'}, {'bd', 'a', 'cdc', 'e', 'd', 'db', 'c', 'aa', 'dc', 'cb'}]\n"
     ]
    }
   ],
   "source": [
    "NSMR = []\n",
    "l = 0 \n",
    "for Trace in Log:\n",
    "    nt = Trace\n",
    "    NSM = SMRS[l].copy()\n",
    "    for i in SMRS[l]:\n",
    "        nt = nt.replace(i,\"\")\n",
    "    for i in MRS[l]:\n",
    "        if(i in nt):\n",
    "            NSM.add(i)\n",
    "    NSMR.append(NSM)\n",
    "    l+=1\n",
    "\n",
    "print(\"NSMR\",NSMR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "---------------------------------------------------------------------------------------------------------------------------\n",
      "|ID|   Trace               |     Maximal Repeat Set      |  Super Maximal Repeat Set |   Near Super Maximal Repeat Set     |\n",
      "|--+-----------------------+-----------------------------+---------------------------+-------------------------------------|\n",
      "|T1|  faabcdbbcda          |        {'a', 'b', 'bcd'}    |      {'a', 'bcd'}         |          {'a', 'b', 'bcd'}          |\n",
      "|T2|    dabcdabcbb         |         {'dabc', 'b'}       |      {'dabc'}             |           {'dabc', 'b'}             |\n",
      "|T3|  bbbcdbbbccaa         |{'bb', 'bbbc', 'a', 'b', 'c'}|     {'bbbc', 'a'}         |           {'bbbc', 'a', 'c'}        |\n",
      "|T4|  aaadabbccc           | {'a', 'b', 'c', 'aa', 'cc'} |     {'aa', 'b', 'cc'}     |      {'a', 'b', 'c', 'aa', 'cc'}    |\n",
      "---------------------------------------------------------------------------------------------------------------------------\n"
     ]
    }
   ],
   "source": [
    "print(\"---------------------------------------------------------------------------------------------------------------------------\")\n",
    "print(\"|ID|   Trace               |     Maximal Repeat Set      |  Super Maximal Repeat Set |   Near Super Maximal Repeat Set     |\")\n",
    "print(\"|--+-----------------------+-----------------------------+---------------------------+-------------------------------------|\")\n",
    "print(\"|\", end=\"\")\n",
    "print(\"T1|  \"+str(Log[0])+\"          |        \"+str(MRS[0])+\"    |      \"+str(SMRS[0])+\"         |          \"+str(NSMR[0])+\"          |\")\n",
    "print(\"|\", end=\"\")\n",
    "print(\"T2|    \"+str(Log[1])+\"         |         \"+str(MRS[1])+\"       |      \"+str(SMRS[1])+\"             |           \"+str(NSMR[1])+\"             |\")\n",
    "print(\"|\", end=\"\") \n",
    "print(\"T3|  \"+str(Log[2])+\"         |\"+str(MRS[2])+\"|     \"+str(SMRS[2])+\"         |           \"+str(NSMR[2])+\"        |\")\n",
    "print(\"|\", end=\"\")\n",
    "print(\"T4|  \"+str(Log[3])+\"           | \"+str(MRS[3])+\" |     \"+str(SMRS[3])+\"     |      \"+str(NSMR[3])+\"    |\")\n",
    "print(\"---------------------------------------------------------------------------------------------------------------------------\")\n",
    "\n",
    "#print(\"T5|\"+str(Log[4])+\"| \"+str(MRS[4])+\"|\"+str(SMRS[4])+\" |  \"+str(NSMR[4])+\"|\")\n"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}