Search_for_keyword_cluster-Greedy.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "from py2neo import Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "graph = Graph(auth=('neo4j', 'shekhor'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 135,
   "metadata": {},
   "outputs": [],
   "source": [
    "phrase = \"sump pump on switch\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instead of returning all cliques of a given size,\n",
    "group all cliques by commonUrl,\n",
    "and return the largest group.\n",
    "\n",
    "From that group, select the first cluster.\n",
    "\n",
    "That way, in the next iteration, we have build on the clique that has the largest potential for expansion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def keywords_up_to(n):\n",
    "    return ', '.join(['k'+str(i) for i in range(1,n+1)])\n",
    "\n",
    "def relationships_up_to(n):\n",
    "    return ', '.join(['r'+str(i) for i in range(1,n+1)])\n",
    "\n",
    "def all_vars(n):\n",
    "    return ', '.join([keywords_up_to(n+1), relationships_up_to(n)])\n",
    "\n",
    "def uncollect(n):\n",
    "    vars = all_vars(n)\n",
    "    return ', '.join([f'group[{i}] as {var}' for i,var in enumerate(vars.split(', '))])\n",
    "\n",
    "def construct_greedy_query(phrase, min_n_keywords = 3, n_common_urls = 4):\n",
    "    \"\"\"\n",
    "    Iteratively build cliques of min_n_keywords where all edges have more than n_common_urls\n",
    "    \"\"\"\n",
    "    # Find keyword\n",
    "    match_phrase = 'MATCH (k1:Keyword {{keyword: \"{phrase}\"}})-[r1:ASSOCIATED_WITH]-(k2:Keyword)\\n'\\\n",
    "                   'WHERE size(r1.urls) > {n_common_urls}\\n'\\\n",
    "                   'WITH *\\n'\\\n",
    "                    .format(phrase=phrase, n_common_urls=n_common_urls)\n",
    "    find_next_keyword = ''\n",
    "    for n in range(2,min_n_keywords):\n",
    "        # Find k_n+1: k_n's neighbors that share at least n_common_urls urls with k_1, k_2, ..., k_n\n",
    "        find_next_keyword += '\\n'\n",
    "        find_next_keyword += 'MATCH (k{n})-[r{n}:ASSOCIATED_WITH]-(k{nplus1})\\n'\\\n",
    "                             'WHERE NOT k{nplus1} in [{keywords_up_to_n}]\\n'\\\n",
    "                             'WITH *,reduce(intersect = r1.urls, r IN [{relationships_up_to_n}] | apoc.coll.intersection(intersect, r.urls)) AS commonUrls\\n'\\\n",
    "                             'WHERE size(commonUrls) > 4\\n'\\\n",
    "                             .format(n=n,nplus1=n+1,keywords_up_to_n=keywords_up_to(n),relationships_up_to_n=relationships_up_to(n),n_common_urls=n_common_urls)\n",
    "        # Find the biggest group of clusters that share the same urls and select the top cluster\n",
    "        select_best_clique = 'WITH commonUrls, collect([{all_vars}]) as groups ORDER BY size(groups) DESC LIMIT 1\\n'\\\n",
    "                             'UNWIND groups as group\\n'\\\n",
    "                             'WITH {uncollect} LIMIT 1\\n'\\\n",
    "                             .format(all_vars=all_vars(n), uncollect=uncollect(n))\n",
    "        find_next_keyword += select_best_clique\n",
    "    return_keywords = ', '.join(['k'+str(i) for i in range(1,min_n_keywords+1)])\n",
    "    # return the keywords\n",
    "    return_query = 'RETURN [k in [{return_keywords}] | k.keyword] AS group\\n'\\\n",
    "                    .format(return_keywords=return_keywords)\n",
    "    return match_phrase + find_next_keyword + return_query"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_largest_keyword_cluster(phrase, min_n_keywords = 3, n_common_urls = 4, range_min = 15, range_max = 30):\n",
    "    # run binary search\n",
    "    # start with pivot = 15\n",
    "    def run_query(n_keywords):\n",
    "        return graph.run(construct_greedy_query(phrase, min_n_keywords = n_keywords, n_common_urls = n_common_urls)).to_table()\n",
    "    \n",
    "    while range_max - range_min > 2:\n",
    "        query_lo = run_query(range_min)\n",
    "        query_hi = run_query(range_max)\n",
    "        if query_lo and query_hi:\n",
    "            # set range to query_hi, query_hi*2\n",
    "            range_min = range_max\n",
    "            range_max = range_max*2\n",
    "        elif not query_lo and not query_hi:\n",
    "            # set range to query_lo//2, query_lo\n",
    "            range_max = range_min\n",
    "            range_min = range_min//2\n",
    "        else:\n",
    "            pivot = (range_min + range_max)//2\n",
    "            query = run_query(pivot)\n",
    "            if query:\n",
    "                range_min = pivot\n",
    "            else:\n",
    "                range_max = pivot\n",
    "    results = run_query((range_min + range_max)//2)    \n",
    "    if results:\n",
    "        return results\n",
    "    else:\n",
    "        return run_query(range_min)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n",
      "30\n",
      "22\n",
      "30\n",
      "22\n",
      "30\n",
      "26\n",
      "30\n",
      "26\n",
      "30\n",
      "26\n",
      "28\n",
      "27\n"
     ]
    }
   ],
   "source": [
    "foo = find_largest_keyword_cluster(phrase)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><th>group</th></tr><tr><td style=\"text-align:left\">[&#039;sump pump on switch&#039;, &#039;turn sump pump off in winter&#039;, &#039;sump pump cover install&#039;, &#039;watchdog sump pump float switch&#039;, &#039;20 year old sump pump&#039;, &#039;cost to replace sump pump in basement&#039;, &#039;pit boss sump pump&#039;, &#039;sump pump problem solving&#039;, &#039;sump pump preventative maintenance&#039;, &#039;my sump pump smells like sewage&#039;, &#039;sump pump cooling oil&#039;, &#039;what does it cost for a sump pump&#039;, &#039;difference between sump pump and well pump&#039;, &#039;zoeller m53 sump pump float adjustment&#039;, &#039;rain barrel sump pump discharge&#039;, &#039;small sump pump with internal float&#039;, &#039;diy sump pump install crawl space&#039;, &#039;back up sump pump cost&#039;, &#039;sump pump tuyauterie&#039;, &#039;can you drain a shower into a sump pump&#039;, &#039;my sump pump is making a loud noise&#039;, &#039;sump pump backup systems water pressure&#039;, &#039;sump pump power pack&#039;, &#039;why does sump pump need a vent hole&#039;, &#039;how to drain water from sump pump&#039;, &#039;sump pump lid gasket&#039;]</td></tr></table>"
      ],
      "text/plain": [
       " group                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               \n",
       "-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n",
       " ['sump pump on switch', 'turn sump pump off in winter', 'sump pump cover install', 'watchdog sump pump float switch', '20 year old sump pump', 'cost to replace sump pump in basement', 'pit boss sump pump', 'sump pump problem solving', 'sump pump preventative maintenance', 'my sump pump smells like sewage', 'sump pump cooling oil', 'what does it cost for a sump pump', 'difference between sump pump and well pump', 'zoeller m53 sump pump float adjustment', 'rain barrel sump pump discharge', 'small sump pump with internal float', 'diy sump pump install crawl space', 'back up sump pump cost', 'sump pump tuyauterie', 'can you drain a shower into a sump pump', 'my sump pump is making a loud noise', 'sump pump backup systems water pressure', 'sump pump power pack', 'why does sump pump need a vent hole', 'how to drain water from sump pump', 'sump pump lid gasket'] "
      ]
     },
     "execution_count": 157,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "foo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "28"
      ]
     },
     "execution_count": 152,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(30+26)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 3.48 ms, total: 3.48 ms\n",
      "Wall time: 77.5 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "foo = graph.run(construct_greedy_query(phrase, min_n_keywords = 26)).to_table()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><th>group</th></tr><tr><td style=\"text-align:left\">[&#039;sump pump on switch&#039;, &#039;turn sump pump off in winter&#039;, &#039;sump pump cover install&#039;, &#039;watchdog sump pump float switch&#039;, &#039;20 year old sump pump&#039;, &#039;cost to replace sump pump in basement&#039;, &#039;pit boss sump pump&#039;, &#039;sump pump problem solving&#039;, &#039;sump pump preventative maintenance&#039;, &#039;my sump pump smells like sewage&#039;, &#039;sump pump cooling oil&#039;, &#039;what does it cost for a sump pump&#039;, &#039;difference between sump pump and well pump&#039;, &#039;zoeller m53 sump pump float adjustment&#039;, &#039;rain barrel sump pump discharge&#039;, &#039;small sump pump with internal float&#039;, &#039;diy sump pump install crawl space&#039;, &#039;back up sump pump cost&#039;, &#039;sump pump tuyauterie&#039;, &#039;can you drain a shower into a sump pump&#039;, &#039;my sump pump is making a loud noise&#039;, &#039;sump pump backup systems water pressure&#039;, &#039;sump pump power pack&#039;, &#039;why does sump pump need a vent hole&#039;, &#039;how to drain water from sump pump&#039;, &#039;sump pump lid gasket&#039;]</td></tr></table>"
      ],
      "text/plain": [
       " group                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               \n",
       "-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n",
       " ['sump pump on switch', 'turn sump pump off in winter', 'sump pump cover install', 'watchdog sump pump float switch', '20 year old sump pump', 'cost to replace sump pump in basement', 'pit boss sump pump', 'sump pump problem solving', 'sump pump preventative maintenance', 'my sump pump smells like sewage', 'sump pump cooling oil', 'what does it cost for a sump pump', 'difference between sump pump and well pump', 'zoeller m53 sump pump float adjustment', 'rain barrel sump pump discharge', 'small sump pump with internal float', 'diy sump pump install crawl space', 'back up sump pump cost', 'sump pump tuyauterie', 'can you drain a shower into a sump pump', 'my sump pump is making a loud noise', 'sump pump backup systems water pressure', 'sump pump power pack', 'why does sump pump need a vent hole', 'how to drain water from sump pump', 'sump pump lid gasket'] "
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "foo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "query = construct_greedy_query(phrase, min_n_keywords = 26)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "pos = query.rfind('LIMIT 1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "metadata": {},
   "outputs": [],
   "source": [
    "query = query[:pos] + query[pos + len('LIMIT 1'):]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 0 ns, sys: 2.36 ms, total: 2.36 ms\n",
      "Wall time: 442 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "foo = graph.run(query).to_table()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><th>group</th></tr><tr><td style=\"text-align:left\">[&#039;sump pump on switch&#039;, &#039;turn sump pump off in winter&#039;, &#039;sump pump cover install&#039;, &#039;watchdog sump pump float switch&#039;, &#039;20 year old sump pump&#039;, &#039;cost to replace sump pump in basement&#039;, &#039;pit boss sump pump&#039;, &#039;sump pump problem solving&#039;, &#039;sump pump preventative maintenance&#039;, &#039;my sump pump smells like sewage&#039;]</td></tr></table>"
      ],
      "text/plain": [
       " group                                                                                                                                                                                                                                                                                                               \n",
       "---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n",
       " ['sump pump on switch', 'turn sump pump off in winter', 'sump pump cover install', 'watchdog sump pump float switch', '20 year old sump pump', 'cost to replace sump pump in basement', 'pit boss sump pump', 'sump pump problem solving', 'sump pump preventative maintenance', 'my sump pump smells like sewage'] "
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "foo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(foo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(foo[1][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3.75 ms, sys: 0 ns, total: 3.75 ms\n",
      "Wall time: 4.42 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "foo = graph.run(construct_greedy_query(phrase, min_n_keywords = 25)).to_table()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><th>group</th></tr><tr><td style=\"text-align:left\">[&#039;myers battery backup sump pump manual&#039;, &#039;rain barrel sump pump discharge&#039;, &#039;diy sump pump install crawl space&#039;, &#039;sump pump power pack&#039;, &#039;sump pump cooling oil&#039;, &#039;what does it cost for a sump pump&#039;, &#039;difference between sump pump and well pump&#039;, &#039;zoeller m53 sump pump float adjustment&#039;, &#039;sump pump use basement&#039;, &#039;sump pump on switch&#039;, &#039;turn sump pump off in winter&#039;, &#039;small sump pump with internal float&#039;, &#039;why does sump pump need a vent hole&#039;, &#039;pit boss sump pump&#039;, &#039;sump pump problem solving&#039;, &#039;sump pump preventative maintenance&#039;, &#039;my sump pump smells like sewage&#039;, &#039;sump pump backup systems water pressure&#039;, &#039;sump pump cover install&#039;, &#039;watchdog sump pump float switch&#039;, &#039;20 year old sump pump&#039;, &#039;cost to replace sump pump in basement&#039;, &#039;sump pump water shut off&#039;, &#039;sump pump window well&#039;, &#039;sump pump lid gasket&#039;]</td></tr></table>"
      ],
      "text/plain": [
       " group                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              \n",
       "----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n",
       " ['myers battery backup sump pump manual', 'rain barrel sump pump discharge', 'diy sump pump install crawl space', 'sump pump power pack', 'sump pump cooling oil', 'what does it cost for a sump pump', 'difference between sump pump and well pump', 'zoeller m53 sump pump float adjustment', 'sump pump use basement', 'sump pump on switch', 'turn sump pump off in winter', 'small sump pump with internal float', 'why does sump pump need a vent hole', 'pit boss sump pump', 'sump pump problem solving', 'sump pump preventative maintenance', 'my sump pump smells like sewage', 'sump pump backup systems water pressure', 'sump pump cover install', 'watchdog sump pump float switch', '20 year old sump pump', 'cost to replace sump pump in basement', 'sump pump water shut off', 'sump pump window well', 'sump pump lid gasket'] "
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "foo"
   ]
  },
  {
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}