Homeworks/HW-2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 2\n",
    "\n",
    "In this homework, we are going to play with Twitter data.\n",
    "\n",
    "The data is represented as rows of of [JSON](https://en.wikipedia.org/wiki/JSON#Example) strings.\n",
    "It consists of [tweets](https://dev.twitter.com/overview/api/tweets), [messages](https://dev.twitter.com/streaming/overview/messages-types), and a small amount of broken data (cannot be parsed as JSON).\n",
    "\n",
    "For this homework, we will only focus on tweets and ignore all other messages.\n",
    "\n",
    "# UPDATES\n",
    "\n",
    "## Announcement\n",
    "\n",
    "**We changed the test files size and the corresponding file paths.**\n",
    "\n",
    "In order to avoid long waiting queue, we decided to limit the input files size for the Playground submissions. Please read the following files to get the input file paths:\n",
    "    * 1GB test: `../Data/hw2-files-1gb.txt`\n",
    "    * 5GB test: `../Data/hw2-files-5gb.txt`\n",
    "    * 20GB test: `../Data/hw2-files-20gb.txt`\n",
    "\n",
    "**We updated the json parsing section of this notebook.**\n",
    "\n",
    "Python built-in json library is too slow. In our experiment, 70% of the total running time is spent on parsing tweets. Therefore we recommend using [ujson](https://pypi.python.org/pypi/ujson) instead of json. It is at least 15x faster than the built-in json library according to our tests.\n",
    "\n",
    "\n",
    "## Important Reminders\n",
    "\n",
    "1. The tokenizer in this notebook contains UTF-8 characters. So the first line of your `.py` source code must be `# -*- coding: utf-8 -*-` to define its encoding. Learn more about this topic [here](https://www.python.org/dev/peps/pep-0263/).\n",
    "2. The input files (the tweets) contain UTF-8 characters. So you have to correctly encode your input with some function like `lambda text: text.encode('utf-8')`.\n",
    "3. `../Data/hw2-files-<param>` may contain multiple lines, one line for one input file. You can use a single textFile call to read multiple files: `sc.textFile(','.join(files))`.\n",
    "4. The input file paths in `../Data/hw2-files-<param>` contains trailing spaces (newline etc.), which may confuse HDFS if not removed. \n",
    "5. Your program will be killed if it cannot finish in 5 minutes. The running time of last 100 submissions (yours and others) can be checked at the \"View last 100 jobs\" tab. For your information, here is the running time of our solution:\n",
    "   * 1GB test:  53 seconds,\n",
    "   * 5GB test:  60 seconds,\n",
    "   * 20GB test: 114 seconds.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Tweets\n",
    "\n",
    "A tweet consists of many data fields. [Here is an example](https://gist.github.com/arapat/03d02c9b327e6ff3f6c3c5c602eeaf8b). You can learn all about them in the Twitter API doc. We are going to briefly introduce only the data fields that will be used in this homework.\n",
    "\n",
    "* `created_at`: Posted time of this tweet (time zone is included)\n",
    "* `id_str`: Tweet ID - we recommend using `id_str` over using `id` as Tweet IDs, becauase `id` is an integer and may bring some overflow problems.\n",
    "* `text`: Tweet content\n",
    "* `user`: A JSON object for information about the author of the tweet\n",
    "    * `id_str`: User ID\n",
    "    * `name`: User name (may contain spaces)\n",
    "    * `screen_name`: User screen name (no spaces)\n",
    "* `retweeted_status`: A JSON object for information about the retweeted tweet (i.e. this tweet is not original but retweeteed some other tweet)\n",
    "    * All data fields of a tweet except `retweeted_status`\n",
    "* `entities`: A JSON object for all entities in this tweet\n",
    "    * `hashtags`: An array for all the hashtags that are mentioned in this tweet\n",
    "    * `urls`: An array for all the URLs that are mentioned in this tweet\n",
    "\n",
    "\n",
    "## Data source\n",
    "\n",
    "All tweets are collected using the [Twitter Streaming API](https://dev.twitter.com/streaming/overview).\n",
    "\n",
    "\n",
    "## Users partition\n",
    "\n",
    "Besides the original tweets, we will provide you with a Pickle file, which contains a partition over 452,743 Twitter users. It contains a Python dictionary `{user_id: partition_id}`. The users are partitioned into 7 groups."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 0: Load data to a RDD"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The tweets data is stored on AWS S3. We have in total a little over 1 TB of tweets. We provide 10 MB of tweets for your local development. For the testing and grading on the homework server, we will use different data.\n",
    "\n",
    "## Testing on the homework server\n",
    "In the Playground, we provide three different input sizes to test your program: 1 GB, 10 GB, and 100 GB. To test them, read files list from `../Data/hw2-files-1gb.txt`, `../Data/hw2-files-5gb.txt`, `../Data/hw2-files-20gb.txt`, respectively.\n",
    "\n",
    "For final submission, make sure to read files list from `../Data/hw2-files-final.txt`. Otherwise your program will receive no points.\n",
    "\n",
    "## Local test\n",
    "\n",
    "For local testing, read files list from `../Data/hw2-files.txt`.\n",
    "Now let's see how many lines there are in the input files.\n",
    "\n",
    "1. Make RDD from the list of files in `hw2-files.txt`.\n",
    "2. Mark the RDD to be cached (so in next operation data will be loaded in memory) \n",
    "3. call the `print_count` method to print number of lines in all these files\n",
    "\n",
    "It should print\n",
    "```\n",
    "Number of elements: 2193\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_count(rdd):\n",
    "    print 'Number of elements:', rdd.count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1: Parse JSON strings to JSON objects"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python has built-in support for JSON.\n",
    "\n",
    "**UPDATE:** Python built-in json library is too slow. In our experiment, 70% of the total running time is spent on parsing tweets. Therefore we recommend using [ujson](https://pypi.python.org/pypi/ujson) instead of json. It is at least 15x faster than the built-in json library according to our tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{u'id': 1,\n",
       " u'name': u'A green door',\n",
       " u'price': 12.5,\n",
       " u'tags': [u'home', u'green']}"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import ujson\n",
    "\n",
    "json_example = '''\n",
    "{\n",
    "    \"id\": 1,\n",
    "    \"name\": \"A green door\",\n",
    "    \"price\": 12.50,\n",
    "    \"tags\": [\"home\", \"green\"]\n",
    "}\n",
    "'''\n",
    "\n",
    "json_obj = ujson.loads(json_example)\n",
    "json_obj"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Broken tweets and irrelevant messages\n",
    "\n",
    "The data of this assignment may contain broken tweets (invalid JSON strings). So make sure that your code is robust for such cases.\n",
    "\n",
    "In addition, some lines in the input file might not be tweets, but messages that the Twitter server sent to the developer (such as [limit notices](https://dev.twitter.com/streaming/overview/messages-types#limit_notices)). Your program should also ignore these messages.\n",
    "\n",
    "*Hint:* [Catch the ValueError](http://stackoverflow.com/questions/11294535/verify-if-a-string-is-json-in-python)\n",
    "\n",
    "\n",
    "(1) Parse raw JSON tweets to obtain valid JSON objects. From all valid tweets, construct a pair RDD of `(user_id, text)`, where `user_id` is the `id_str` data field of the `user` dictionary (read [Tweets](#Tweets) section above), `text` is the `text` data field."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import ujson\n",
    "\n",
    "def safe_parse(raw_json):\n",
    "    # your code here\n",
    "    pass\n",
    "\n",
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(2) Count the number of different users in all valid tweets (hint: [the `distinct()` method](https://spark.apache.org/docs/latest/programming-guide.html#transformations)).\n",
    "\n",
    "It should print\n",
    "```\n",
    "The number of unique users is: 2083\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_users_count(count):\n",
    "    print 'The number of unique users is:', count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2: Number of posts from each user partition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load the Pickle file `../Data/users-partition.pickle`, you will get a dictionary which represents a partition over 452,743 Twitter users, `{user_id: partition_id}`. The users are partitioned into 7 groups. For example, if the dictionary is loaded into a variable named `partition`, the partition ID of the user `59458445` is `partition[\"59458445\"]`. These users are partitioned into 7 groups. The partition ID is an integer between 0-6.\n",
    "\n",
    "Note that the user partition we provide doesn't cover all users appear in the input data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(1) Load the pickle file."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(2) Count the number of posts from each user partition\n",
    "\n",
    "Count the number of posts from group 0, 1, ..., 6, plus the number of posts from users who are not in any partition. Assign users who are not in any partition to the group 7.\n",
    "\n",
    "Put the results of this step into a pair RDD `(group_id, count)` that is sorted by key."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(3) Print the post count using the `print_post_count` function we provided.\n",
    "\n",
    "It should print\n",
    "\n",
    "```\n",
    "Group 0 posted 81 tweets\n",
    "Group 1 posted 199 tweets\n",
    "Group 2 posted 45 tweets\n",
    "Group 3 posted 313 tweets\n",
    "Group 4 posted 86 tweets\n",
    "Group 5 posted 221 tweets\n",
    "Group 6 posted 400 tweets\n",
    "Group 7 posted 798 tweets\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def print_post_count(counts):\n",
    "    for group_id, count in counts:\n",
    "        print 'Group %d posted %d tweets' % (group_id, count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Part 3:  Tokens that are relatively popular in each user partition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "In this step, we are going to find tokens that are relatively popular in each user partition.\n",
    "\n",
    "We define the number of mentions of a token $t$ in a specific user partition $k$ as the number of users from the user partition $k$ that ever mentioned the token $t$ in their tweets. Note that even if some users might mention a token $t$ multiple times or in multiple tweets, a user will contribute at most 1 to the counter of the token $t$.\n",
    "\n",
    "Please make sure that the number of mentions of a token is equal to the number of users who mentioned this token but NOT the number of tweets that mentioned this token.\n",
    "\n",
    "Let $N_t^k$ be the number of mentions of the token $t$ in the user partition $k$. Let $N_t^{all} = \\sum_{i=0}^7 N_t^{i}$ be the number of total mentions of the token $t$.\n",
    "\n",
    "We define the relative popularity of a token $t$ in a user partition $k$ as the log ratio between $N_t^k$ and $N_t^{all}$, i.e. \n",
    "\n",
    "\\begin{equation}\n",
    "p_t^k = \\log \\frac{C_t^k}{C_t^{all}}.\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "You can compute the relative popularity by calling the function `get_rel_popularity`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(0) Load the tweet tokenizer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# %load happyfuntokenizing.py\n",
    "#!/usr/bin/env python\n",
    "\n",
    "\"\"\"\n",
    "This code implements a basic, Twitter-aware tokenizer.\n",
    "\n",
    "A tokenizer is a function that splits a string of text into words. In\n",
    "Python terms, we map string and unicode objects into lists of unicode\n",
    "objects.\n",
    "\n",
    "There is not a single right way to do tokenizing. The best method\n",
    "depends on the application.  This tokenizer is designed to be flexible\n",
    "and this easy to adapt to new domains and tasks.  The basic logic is\n",
    "this:\n",
    "\n",
    "1. The tuple regex_strings defines a list of regular expression\n",
    "   strings.\n",
    "\n",
    "2. The regex_strings strings are put, in order, into a compiled\n",
    "   regular expression object called word_re.\n",
    "\n",
    "3. The tokenization is done by word_re.findall(s), where s is the\n",
    "   user-supplied string, inside the tokenize() method of the class\n",
    "   Tokenizer.\n",
    "\n",
    "4. When instantiating Tokenizer objects, there is a single option:\n",
    "   preserve_case.  By default, it is set to True. If it is set to\n",
    "   False, then the tokenizer will downcase everything except for\n",
    "   emoticons.\n",
    "\n",
    "The __main__ method illustrates by tokenizing a few examples.\n",
    "\n",
    "I've also included a Tokenizer method tokenize_random_tweet(). If the\n",
    "twitter library is installed (http://code.google.com/p/python-twitter/)\n",
    "and Twitter is cooperating, then it should tokenize a random\n",
    "English-language tweet.\n",
    "\n",
    "\n",
    "Julaiti Alafate:\n",
    "  I modified the regex strings to extract URLs in tweets.\n",
    "\"\"\"\n",
    "\n",
    "__author__ = \"Christopher Potts\"\n",
    "__copyright__ = \"Copyright 2011, Christopher Potts\"\n",
    "__credits__ = []\n",
    "__license__ = \"Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License: http://creativecommons.org/licenses/by-nc-sa/3.0/\"\n",
    "__version__ = \"1.0\"\n",
    "__maintainer__ = \"Christopher Potts\"\n",
    "__email__ = \"See the author's website\"\n",
    "\n",
    "######################################################################\n",
    "\n",
    "import re\n",
    "import htmlentitydefs\n",
    "\n",
    "######################################################################\n",
    "# The following strings are components in the regular expression\n",
    "# that is used for tokenizing. It's important that phone_number\n",
    "# appears first in the final regex (since it can contain whitespace).\n",
    "# It also could matter that tags comes after emoticons, due to the\n",
    "# possibility of having text like\n",
    "#\n",
    "#     <:| and some text >:)\n",
    "#\n",
    "# Most imporatantly, the final element should always be last, since it\n",
    "# does a last ditch whitespace-based tokenization of whatever is left.\n",
    "\n",
    "# This particular element is used in a couple ways, so we define it\n",
    "# with a name:\n",
    "emoticon_string = r\"\"\"\n",
    "    (?:\n",
    "      [<>]?\n",
    "      [:;=8]                     # eyes\n",
    "      [\\-o\\*\\']?                 # optional nose\n",
    "      [\\)\\]\\(\\[dDpP/\\:\\}\\{@\\|\\\\] # mouth      \n",
    "      |\n",
    "      [\\)\\]\\(\\[dDpP/\\:\\}\\{@\\|\\\\] # mouth\n",
    "      [\\-o\\*\\']?                 # optional nose\n",
    "      [:;=8]                     # eyes\n",
    "      [<>]?\n",
    "    )\"\"\"\n",
    "\n",
    "# The components of the tokenizer:\n",
    "regex_strings = (\n",
    "    # Phone numbers:\n",
    "    r\"\"\"\n",
    "    (?:\n",
    "      (?:            # (international)\n",
    "        \\+?[01]\n",
    "        [\\-\\s.]*\n",
    "      )?            \n",
    "      (?:            # (area code)\n",
    "        [\\(]?\n",
    "        \\d{3}\n",
    "        [\\-\\s.\\)]*\n",
    "      )?    \n",
    "      \\d{3}          # exchange\n",
    "      [\\-\\s.]*   \n",
    "      \\d{4}          # base\n",
    "    )\"\"\"\n",
    "    ,\n",
    "    # URLs:\n",
    "    r\"\"\"http[s]?://(?:[a-zA-Z]|[0-9]|[$-_@.&+]|[!*\\(\\),]|(?:%[0-9a-fA-F][0-9a-fA-F]))+\"\"\"\n",
    "    ,\n",
    "    # Emoticons:\n",
    "    emoticon_string\n",
    "    ,    \n",
    "    # HTML tags:\n",
    "     r\"\"\"<[^>]+>\"\"\"\n",
    "    ,\n",
    "    # Twitter username:\n",
    "    r\"\"\"(?:@[\\w_]+)\"\"\"\n",
    "    ,\n",
    "    # Twitter hashtags:\n",
    "    r\"\"\"(?:\\#+[\\w_]+[\\w\\'_\\-]*[\\w_]+)\"\"\"\n",
    "    ,\n",
    "    # Remaining word types:\n",
    "    r\"\"\"\n",
    "    (?:[a-z][a-z'\\-_]+[a-z])       # Words with apostrophes or dashes.\n",
    "    |\n",
    "    (?:[+\\-]?\\d+[,/.:-]\\d+[+\\-]?)  # Numbers, including fractions, decimals.\n",
    "    |\n",
    "    (?:[\\w_]+)                     # Words without apostrophes or dashes.\n",
    "    |\n",
    "    (?:\\.(?:\\s*\\.){1,})            # Ellipsis dots. \n",
    "    |\n",
    "    (?:\\S)                         # Everything else that isn't whitespace.\n",
    "    \"\"\"\n",
    "    )\n",
    "\n",
    "######################################################################\n",
    "# This is the core tokenizing regex:\n",
    "    \n",
    "word_re = re.compile(r\"\"\"(%s)\"\"\" % \"|\".join(regex_strings), re.VERBOSE | re.I | re.UNICODE)\n",
    "\n",
    "# The emoticon string gets its own regex so that we can preserve case for them as needed:\n",
    "emoticon_re = re.compile(regex_strings[1], re.VERBOSE | re.I | re.UNICODE)\n",
    "\n",
    "# These are for regularizing HTML entities to Unicode:\n",
    "html_entity_digit_re = re.compile(r\"&#\\d+;\")\n",
    "html_entity_alpha_re = re.compile(r\"&\\w+;\")\n",
    "amp = \"&amp;\"\n",
    "\n",
    "######################################################################\n",
    "\n",
    "class Tokenizer:\n",
    "    def __init__(self, preserve_case=False):\n",
    "        self.preserve_case = preserve_case\n",
    "\n",
    "    def tokenize(self, s):\n",
    "        \"\"\"\n",
    "        Argument: s -- any string or unicode object\n",
    "        Value: a tokenize list of strings; conatenating this list returns the original string if preserve_case=False\n",
    "        \"\"\"        \n",
    "        # Try to ensure unicode:\n",
    "        try:\n",
    "            s = unicode(s)\n",
    "        except UnicodeDecodeError:\n",
    "            s = str(s).encode('string_escape')\n",
    "            s = unicode(s)\n",
    "        # Fix HTML character entitites:\n",
    "        s = self.__html2unicode(s)\n",
    "        # Tokenize:\n",
    "        words = word_re.findall(s)\n",
    "        # Possible alter the case, but avoid changing emoticons like :D into :d:\n",
    "        if not self.preserve_case:            \n",
    "            words = map((lambda x : x if emoticon_re.search(x) else x.lower()), words)\n",
    "        return words\n",
    "\n",
    "    def tokenize_random_tweet(self):\n",
    "        \"\"\"\n",
    "        If the twitter library is installed and a twitter connection\n",
    "        can be established, then tokenize a random tweet.\n",
    "        \"\"\"\n",
    "        try:\n",
    "            import twitter\n",
    "        except ImportError:\n",
    "            print \"Apologies. The random tweet functionality requires the Python twitter library: http://code.google.com/p/python-twitter/\"\n",
    "        from random import shuffle\n",
    "        api = twitter.Api()\n",
    "        tweets = api.GetPublicTimeline()\n",
    "        if tweets:\n",
    "            for tweet in tweets:\n",
    "                if tweet.user.lang == 'en':            \n",
    "                    return self.tokenize(tweet.text)\n",
    "        else:\n",
    "            raise Exception(\"Apologies. I couldn't get Twitter to give me a public English-language tweet. Perhaps try again\")\n",
    "\n",
    "    def __html2unicode(self, s):\n",
    "        \"\"\"\n",
    "        Internal metod that seeks to replace all the HTML entities in\n",
    "        s with their corresponding unicode characters.\n",
    "        \"\"\"\n",
    "        # First the digits:\n",
    "        ents = set(html_entity_digit_re.findall(s))\n",
    "        if len(ents) > 0:\n",
    "            for ent in ents:\n",
    "                entnum = ent[2:-1]\n",
    "                try:\n",
    "                    entnum = int(entnum)\n",
    "                    s = s.replace(ent, unichr(entnum))\t\n",
    "                except:\n",
    "                    pass\n",
    "        # Now the alpha versions:\n",
    "        ents = set(html_entity_alpha_re.findall(s))\n",
    "        ents = filter((lambda x : x != amp), ents)\n",
    "        for ent in ents:\n",
    "            entname = ent[1:-1]\n",
    "            try:            \n",
    "                s = s.replace(ent, unichr(htmlentitydefs.name2codepoint[entname]))\n",
    "            except:\n",
    "                pass                    \n",
    "            s = s.replace(amp, \" and \")\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from math import log\n",
    "\n",
    "tok = Tokenizer(preserve_case=False)\n",
    "\n",
    "def get_rel_popularity(c_k, c_all):\n",
    "    return log(1.0 * c_k / c_all) / log(2)\n",
    "\n",
    "\n",
    "def print_tokens(tokens, gid = None):\n",
    "    group_name = \"overall\"\n",
    "    if gid is not None:\n",
    "        group_name = \"group %d\" % gid\n",
    "    print '=' * 5 + ' ' + group_name + ' ' + '=' * 5\n",
    "    for t, n in tokens:\n",
    "        print \"%s\\t%.4f\" % (t, n)\n",
    "    print"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(1) Tokenize the tweets using the tokenizer we provided above named `tok`. Count the number of mentions for each tokens regardless of specific user group.\n",
    "\n",
    "Call `print_count` function to show how many different tokens we have.\n",
    "\n",
    "It should print\n",
    "```\n",
    "Number of elements: 8979\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(2) Tokens that are mentioned by too few users are usually not very interesting. So we want to only keep tokens that are mentioned by at least 100 users. Please filter out tokens that don't meet this requirement.\n",
    "\n",
    "Call `print_count` function to show how many different tokens we have after the filtering.\n",
    "\n",
    "Call `print_tokens` function to show top 20 most frequent tokens.\n",
    "\n",
    "It should print\n",
    "```\n",
    "Number of elements: 52\n",
    "===== overall =====\n",
    ":\t1386.0000\n",
    "rt\t1237.0000\n",
    ".\t865.0000\n",
    "\\\t745.0000\n",
    "the\t621.0000\n",
    "trump\t595.0000\n",
    "x80\t545.0000\n",
    "xe2\t543.0000\n",
    "to\t499.0000\n",
    ",\t489.0000\n",
    "xa6\t457.0000\n",
    "a\t403.0000\n",
    "is\t376.0000\n",
    "in\t296.0000\n",
    "'\t294.0000\n",
    "of\t292.0000\n",
    "and\t287.0000\n",
    "for\t280.0000\n",
    "!\t269.0000\n",
    "?\t210.0000\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(3) For all tokens that are mentioned by at least 100 users, compute their relative popularity in each user group. Then print the top 10 tokens with highest relative popularity in each user group. In case two tokens have same relative popularity, break the tie by printing the alphabetically smaller one.\n",
    "\n",
    "**Hint:** Let the relative popularity of a token $t$ be $p$. The order of the items will be satisfied by sorting them using (-p, t) as the key.\n",
    "\n",
    "It should print\n",
    "```\n",
    "===== group 0 =====\n",
    "...\t-3.5648\n",
    "at\t-3.5983\n",
    "hillary\t-4.0484\n",
    "bernie\t-4.1430\n",
    "not\t-4.2479\n",
    "he\t-4.2574\n",
    "i\t-4.2854\n",
    "s\t-4.3309\n",
    "are\t-4.3646\n",
    "in\t-4.4021\n",
    "\n",
    "===== group 1 =====\n",
    "#demdebate\t-2.4391\n",
    "-\t-2.6202\n",
    "clinton\t-2.7174\n",
    "&\t-2.7472\n",
    "amp\t-2.7472\n",
    ";\t-2.7980\n",
    "sanders\t-2.8745\n",
    "?\t-2.9069\n",
    "in\t-2.9615\n",
    "if\t-2.9861\n",
    "\n",
    "===== group 2 =====\n",
    "are\t-4.6865\n",
    "and\t-4.7055\n",
    "bernie\t-4.7279\n",
    "at\t-4.7682\n",
    "sanders\t-4.9449\n",
    "in\t-5.0395\n",
    "donald\t-5.0531\n",
    "a\t-5.0697\n",
    "#demdebate\t-5.1396\n",
    "that\t-5.1599\n",
    "\n",
    "===== group 3 =====\n",
    "#demdebate\t-1.3847\n",
    "bernie\t-1.8535\n",
    "sanders\t-2.1793\n",
    "of\t-2.2356\n",
    "t\t-2.2675\n",
    "clinton\t-2.4179\n",
    "hillary\t-2.4203\n",
    "the\t-2.4330\n",
    "xa6\t-2.4962\n",
    "that\t-2.5160\n",
    "\n",
    "===== group 4 =====\n",
    "hillary\t-3.8074\n",
    "sanders\t-3.9449\n",
    "of\t-4.0199\n",
    "what\t-4.0875\n",
    "clinton\t-4.0959\n",
    "at\t-4.1832\n",
    "in\t-4.2095\n",
    "a\t-4.2623\n",
    "on\t-4.2854\n",
    "'\t-4.2928\n",
    "\n",
    "===== group 5 =====\n",
    "cruz\t-2.3344\n",
    "he\t-2.6724\n",
    "will\t-2.7705\n",
    "are\t-2.7796\n",
    "the\t-2.8522\n",
    "is\t-2.8822\n",
    "that\t-2.9119\n",
    "this\t-2.9542\n",
    "for\t-2.9594\n",
    "of\t-2.9804\n",
    "\n",
    "===== group 6 =====\n",
    "@realdonaldtrump\t-1.1520\n",
    "cruz\t-1.4657\n",
    "n\t-1.4877\n",
    "!\t-1.5479\n",
    "not\t-1.8904\n",
    "xa6\t-1.9172\n",
    "xe2\t-1.9973\n",
    "/\t-2.0238\n",
    "x80\t-2.0240\n",
    "it\t-2.0506\n",
    "\n",
    "===== group 7 =====\n",
    "donald\t-0.6471\n",
    "...\t-0.7922\n",
    "sanders\t-1.0380\n",
    "what\t-1.1178\n",
    "trump\t-1.1293\n",
    "bernie\t-1.2044\n",
    "you\t-1.2099\n",
    "-\t-1.2253\n",
    "if\t-1.2602\n",
    "clinton\t-1.2681\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "(4) (optional, not for grading) The users partition is generated by a machine learning algorithm that tries to group the users by their political preferences. Three of the user groups are showing supports to Bernie Sanders, Ted Cruz, and Donald Trump. \n",
    "\n",
    "If your program looks okay on the local test data, you can try it on the larger input by submitting your program to the homework server. Observe the output of your program to larger input files, can you guess the partition IDs of the three groups mentioned above based on your output?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Change the values of the following three items to your guesses\n",
    "users_support = [\n",
    "    (-1, \"Bernie Sanders\"),\n",
    "    (-1, \"Ted Cruz\"),\n",
    "    (-1, \"Donald Trump\")\n",
    "]\n",
    "\n",
    "for gid, candidate in users_support:\n",
    "    print \"Users from group %d are most likely to support %s.\" % (gid, candidate)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}