{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practical Topic Finding for Short-Sentence Texts\n",
    "\n",
    "## 1. Introduction\n",
    "\n",
    "Many analysis applications involve finding topics in corpora of short sentences, such as tweets, short messages, logs and comments. On one hand, the direct insights provided in these topics will serve as the basis of many further analysis, e.g., sentiment scoring or document classificaition. On the other hand, those short texts have some unique characterics that deserve more attentions when applying the traditional topic-finding algorithms to them. Some challenges are\n",
    "- Short texts usually have higher language variability, where the same meaning can be phrased in various ways [[1]](http://www.aclweb.org/anthology/S12-1005). For example, \"dollars\", \"\\$\", \"$$\", \"fee\", \"charges\" may all have similar meanings; but this is harder to capture in shorter sentences due to the limited information of surrounding contexts of each word.\n",
    "- Unlike longer articles such as wiki pages, short comments or tweets may each have a single topic. At first glance it may look like a simplification. But practically it poses challenges when the algorithms to be applied assume a mixture of topics in each document. Forcing a sparse representation usually comes with a price, either computational or performance-related.\n",
    "\n",
    "To make it even more complicated, topic-finding is a multiple-step process, involving preprocessing of texts, vectorization, topic-mining and finally topic representations in keywords. Each step has multiple choices in practice and the different combinations may generate very different results.\n",
    "\n",
    "This article explores the pros and cons of differnet algorithmic decisions in topic-finding, by considering the natures of short texts discussed above. Instead of providing a bird's-eye view of theoritical comparisons, I want to highlight how a practical decision should be made based on the structure of your data and the structure of your topics. A good theoritical review can be found in [[2]](http://anthology.aclweb.org/D/D12/D12-1087.pdf).\n",
    "\n",
    "In the following I use \"toy-like\" artificial data to make those \"blackbox\" models transparent. All the models compared below are implemented in Python [scikit-learn](http://scikit-learn.org/stable/) package. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Topic Finding Models\n",
    "\n",
    "I look into three topic-finding models, namely Latent Dirichlet Allocation ([LDA](https://www.cs.princeton.edu/~blei/papers/BleiNgJordan2003.pdf)), Non-Negative Matrix Factorization ([NMF](http://epubs.siam.org/doi/pdf/10.1137/1.9781611972740.45)), and Truncated Singular Value Decomposition ([SVD](http://scikit-learn.org/stable/modules/generated/sklearn.decomposition.TruncatedSVD.html)). There are many extensions of these traditional models and different implementations. I pick those from [scikit-learn](http://scikit-learn.org/stable/) package. \n",
    "\n",
    "Besides the three traditional topic models, another related approach in finding text structures is document clustering. One of its implementation [KMeans Clustering](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html) has also been included in this comparison although it is usually not considered as a topic model approach. You can find interesting discussions on the differences of the models [online](https://www.quora.com/search?q=nmf+vs+lda). The code comments below also provide addtional information on why an implementation decision is made in that way."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer\n",
    "from sklearn.decomposition import TruncatedSVD, NMF, LatentDirichletAllocation\n",
    "from sklearn.cluster import KMeans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before diving into models, let's prepare some sample texts below. Here I generated four artificial corpora for topic-finding. \n",
    "- `clearcut topics`: texts clearly with 2 topics - \"berger-lovers\" and \"sandwich-haters\". It shouldn't be a problem for most methods.\n",
    "- `unbalanced topics`: it has the same 2 topics as above, but the topic distributions are skewed. A real scenario would be finding *outlier* messages or comments from a haystack of normal ones.\n",
    "- `semantic topics`: the corpus has four topics, each for both berger/sandwich lovers and haters. However, in addition to structuring the texts this way, there is another potential dimension that can group \"berger\" vs \"sandwich\" as \"foods topic\" and \"hate\" v.s. \"love\" as \"feelings topic\". Is there any setup that can find topics in this new perspective?\n",
    "- `noisy topics`: as discussed above, short texts may have language variability due to different terms for the same meaning, or even typos. This corpus simulates texts with different typos for two topics. The number of texts in this corpus is smaller than others, so that we can test how the models deal with these ambigurities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def generate_clearcut_topics():\n",
    "    ## for demostration purpose, don't take it personally : )\n",
    "    return np.repeat([\"we love bergers\", \"we hate sandwiches\"], [1000, 1000])\n",
    "\n",
    "def generate_unbalanced_topics():\n",
    "    return np.repeat([\"we love bergers\", \"we hate sandwiches\"], [10, 1000])\n",
    "\n",
    "def generate_semantic_context_topics():\n",
    "    return np.repeat([\"we love bergers\"\n",
    "                      , \"we hate bergers\"\n",
    "                      , \"we love sandwiches\"\n",
    "                      , \"we hate sandwiches\"], 1000)\n",
    "\n",
    "def generate_noisy_topics():\n",
    "    def _random_typos(word, n):\n",
    "        typo_index = np.random.randint(0, len(word), n)\n",
    "        return [word[:i]+\"X\"+word[i+1:] for i in typo_index]\n",
    "    t1 = [\"we love %s\" % w for w in _random_typos(\"bergers\", 15)]\n",
    "    t2 = [\"we hate %s\" % w for w in _random_typos(\"sandwiches\", 15)]\n",
    "    return np.r_[t1, t2]\n",
    "\n",
    "sample_texts = {\n",
    "     \"clearcut topics\": generate_clearcut_topics()\n",
    "    , \"unbalanced topics\": generate_unbalanced_topics()\n",
    "    , \"semantic topics\": generate_semantic_context_topics()\n",
    "    , \"noisy topics\": generate_noisy_topics()\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "noisy topics\n",
      "[('we love bergXrs', 5), ('we love bergerX', 3), ('we hate sandXiches', 3), ('we love Xergers', 2), ('we hate sanXwiches', 2), ('we hate sandwiXhes', 2), ('we hate sandwicXes', 2), ('we hate Xandwiches', 2), ('we love bergeXs', 2), ('we love berXers', 1), ('we hate sandwicheX', 1), ('we hate sandwXches', 1), ('we love bXrgers', 1), ('we hate saXdwiches', 1), ('we love beXgers', 1), ('we hate sXndwiches', 1)]\n",
      "\n",
      "clearcut topics\n",
      "[('we love bergers', 1000), ('we hate sandwiches', 1000)]\n",
      "\n",
      "unbalanced topics\n",
      "[('we hate sandwiches', 1000), ('we love bergers', 10)]\n",
      "\n",
      "semantic topics\n",
      "[('we love bergers', 1000), ('we love sandwiches', 1000), ('we hate sandwiches', 1000), ('we hate bergers', 1000)]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "from collections import Counter\n",
    "for desc, texts in sample_texts.items():\n",
    "    print desc\n",
    "    print Counter(texts).most_common()\n",
    "    print \"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's first take a step back and consider what makes a \"good\" topic modelling. Although the standard should depend on the nature of the analysis, there are usually some common understanding. For many cases, the keywords in each topic should be \n",
    "- frequent enough to appear in more than a few documents/sentences. Topics covering only a few examples may not be interesting, unless outlier detection is the purpose. \n",
    "- representative enough to distinguish one topic from another. This sometimes implies *orthogonality* or *independence* among the topics. \n",
    "\n",
    "Some research [[2]](http://anthology.aclweb.org/D/D12/D12-1087.pdf) also propose other criteria such as \n",
    "- co-occurrence of keywords in the same topic should be high, which implies they are coming from the same contexts.\n",
    "- semantic meanings of keywords in a topic should be close, e.g., \"apples\" and \"oranges\" in \"fruits topic\", \"love\" and \"hate\" in \"emotions topic\".\n",
    "\n",
    "Now let's take a look at the implementation of the models to be compared. The four models, namely `NMF`, `SVD`, `LDA` and `KMEANS` are implemented with a single interface `find_topic` below. Each topic model can be combined with two `vectorization` methods, i.e., term-frequence (TF) and term-frequence-inverse-document-frequence ([TFIDF](https://en.wikipedia.org/wiki/Tf%E2%80%93idf)). In general, you should choose TFIDF over TF if you have a lot of common words shared by many texts. Those common words are considered as \"noise\" (or stop-words) that may impair the expressness of real important words in topics. However, this difference between TF and TFIDF is not significant for applications on short sentences, because there is less chance for a word to become \"dominant\" out of many short sentences. Finding other possible vector representations of documents is an active research area. For example, vectorizations based on [word embedding](http://colah.github.io/posts/2014-07-NLP-RNNs-Representations/) models, e.g. [word2vec](https://en.wikipedia.org/wiki/Word2vec) and [doc2vec](http://eng.kifi.com/from-word2vec-to-doc2vec-an-approach-driven-by-chinese-restaurant-process/) have become popular. \n",
    "\n",
    "The following implementation chooses the keywords of topics as the most frequent words in a ***topic-word distribution***, which is usually generated by the topic models or clustering algorithms. However for some models such as SVD or KMEANS clustering, the topic-word matrix could have both positive and negative values, which makes it difficult to be explained as a \"distribution\" and thus choosing the keywords for topics is more ambiguous. For demostration, I choose to pick the keywords as those with significant absolute values and keep the signs with these keywords - the negative words would be prefixed with a ***\"^\"***, such as ***\"^bergers\"***."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def find_topic(texts, topic_model, n_topics, vec_model=\"tf\", thr=1e-2, **kwargs):\n",
    "    \"\"\"Return a list of topics from texts by topic models - for demostration of simple data\n",
    "    texts: array-like strings\n",
    "    topic_model: {\"nmf\", \"svd\", \"lda\", \"kmeans\"} for LSA_NMF, LSA_SVD, LDA, KMEANS (not actually a topic model)\n",
    "    n_topics: # of topics in texts\n",
    "    vec_model: {\"tf\", \"tfidf\"} for term_freq, term_freq_inverse_doc_freq\n",
    "    thr: threshold for finding keywords in a topic model\n",
    "    \"\"\"\n",
    "    ## 1. vectorization\n",
    "    vectorizer = CountVectorizer() if vec_model == \"tf\" else TfidfVectorizer()\n",
    "    text_vec = vectorizer.fit_transform(texts)\n",
    "    words = np.array(vectorizer.get_feature_names())\n",
    "    ## 2. topic finding\n",
    "    topic_models = {\"nmf\": NMF, \"svd\": TruncatedSVD, \"lda\": LatentDirichletAllocation, \"kmeans\": KMeans}\n",
    "    topicfinder = topic_models[topic_model](n_topics, **kwargs).fit(text_vec)\n",
    "    topic_dists = topicfinder.components_ if topic_model is not \"kmeans\" else topicfinder.cluster_centers_\n",
    "    topic_dists /= topic_dists.max(axis = 1).reshape((-1, 1))   \n",
    "    ## 3. keywords for topics\n",
    "    ## Unlike other models, LSA_SVD will generate both positive and negative values in topic_word distribution,\n",
    "    ## which makes it more ambiguous to choose keywords for topics. The sign of the weights are kept with the\n",
    "    ## words for a demostration here\n",
    "    def _topic_keywords(topic_dist):\n",
    "        keywords_index = np.abs(topic_dist) >= thr\n",
    "        keywords_prefix = np.where(np.sign(topic_dist) > 0, \"\", \"^\")[keywords_index]\n",
    "        keywords = \" | \".join(map(lambda x: \"\".join(x), zip(keywords_prefix, words[keywords_index])))\n",
    "        return keywords\n",
    "    \n",
    "    topic_keywords = map(_topic_keywords, topic_dists)\n",
    "    return \"\\n\".join(\"Topic %i: %s\" % (i, t) for i, t in enumerate(topic_keywords))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 SVD: orthogonal decomposition of text variances\n",
    "The [truncated SVD implementation in sklearn](http://scikit-learn.org/stable/modules/generated/sklearn.decomposition.TruncatedSVD.html) is intuitively similiar to PCA algorithm, which tries to find ***orthogonal*** directions that explains the largest ***variances*** in the texts. \n",
    "\n",
    "When applying SVD with TF and TFIDF on the clearcut-topic texts, we got the results below. As discussed, one unique signature of SVD's results is that the words in topics can be both positive and negative. For simple cases, they can be understood as **including** and **excluding** the corresponding word in the topic. \n",
    "\n",
    "For example `\"Topic 1: bergers | ^hate | love | ^sandwiches\"` can be \"intuitively\" explained as the texts that include \"love bergers\" and exclude \"hate sandwiches\". \n",
    "\n",
    "Depending on the random state, your topic results may be different. In the results below, we don't see clear indications of the two topics \"love bergers\" and \"hate sandwiches\". However, it does have topics such as `Topic 3: ^bergers | love`, which means \"love\" but NOT \"bergers\". \n",
    "\n",
    "Interestingly, we may also generate topics such as `Topic 3: bergers | ^hate | ^love | sandwiches`, which captures \"bergers\" and \"sandwiches\" as a \"food\" topic."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergers | hate | love | sandwiches | we\n",
      "Topic 1: bergers | ^hate | love | ^sandwiches\n",
      "Topic 2: bergers | hate | love | sandwiches | ^we\n",
      "Topic 3: ^bergers | love\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"clearcut topics\"], \"svd\", 4, vec_model=\"tf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergers | hate | love | sandwiches | we\n",
      "Topic 1: bergers | ^hate | love | ^sandwiches\n",
      "Topic 2: bergers | hate | love | sandwiches | ^we\n",
      "Topic 3: bergers | ^hate | ^love | sandwiches\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"clearcut topics\"], \"svd\", 4, vec_model=\"tfidf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above examples, we set a larger number of topics than expected on purpose, because most of time you don't have the prior knowledge of how many topics there are in your texts. If we explicitly set the topic number = 2. We get the following result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergers | hate | love | sandwiches | we\n",
      "Topic 1: bergers | ^hate | love | ^sandwiches\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"clearcut topics\"], \"svd\", 2, vec_model=\"tfidf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When explaining the result of SVD, it's important to contrast each topic with previous ones, instead of looking at them separately. So the result above can be explained as *that the major difference in the texts are (1) including \"love bergers\" and (2) excluding \"hate sandwiches\".*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try SVD on the unbalanced topic texts, to see how it performs on detecting minor groups - it performs quite well on this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: hate | sandwiches | we\n",
      "Topic 1: bergers | ^hate | love | ^sandwiches | we\n",
      "Topic 2: bergers | hate | love | sandwiches | ^we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"unbalanced topics\"], \"svd\", 3, vec_model=\"tf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, it did poorly on texts with noises - SVD treats each form of the same meaning differently and fails to capture any semantic connections."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergerx | bergexs | bergxrs | bexgers | bxrgers | hate | love | sandwicxes | sandwixhes | sandwxches | sandxiches | sanxwiches | saxdwiches | sxndwiches | we | xandwiches | xergers\n",
      "Topic 1: ^bergerx | ^bergexs | ^bergxrs | ^bexgers | ^bxrgers | hate | ^love | sandwicxes | sandwixhes | sandwxches | sandxiches | sanxwiches | saxdwiches | sxndwiches | we | xandwiches | ^xergers\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"noisy topics\"], \"svd\", 2, vec_model=\"tf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In summary,\n",
    "\n",
    "- SVD finds \"topics\" using the words that explain most of the text variances.\n",
    "- The topics may not be the most explainable based on human standards, because it doesn't enforce a probability. And the keywords within the same topics don't necessarily have high co-occurrences.  \n",
    "- However, the topics are \"complementary\" to each other as there is no duplicate and they capture most information in texts when put together.\n",
    "- This usually makes its result very useful as a representation of documents for other analysis purposes, e.g., document classification. \n",
    "- SVD is also capable of finding topics in unbalanced distributions. \n",
    "- There is an upper limit of the # of topics generated by SVD due to its computation algorithm - using other vectorization method, such as tf/idf for n-grams or word embeddings may help.\n",
    "- ***SVD may have problems if you have texts that are mostly similiar to each other but their slight differences actually determine their topics. ***\n",
    "- This can be observed in SVD's result on \"noisy topics\" texts above, where the difference between \"love bergers\" and \"hate sandwiches\" are blurred by the more dominant variaty of different spellings."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 LDA: gluing similar words based on their co-occurrences\n",
    "\n",
    "[LDA](https://en.wikipedia.org/wiki/Latent_Dirichlet_allocation) is one of the most mentioned topic-finding models, due to its good performances on many different types of texts, and its intuitive interpretation as a \"generative\" process.\n",
    "\n",
    "Intuitively, LDA finds topics as a group of words that have high co-occurrences among different documents. On the other side, documents from the similiar mixture of topics should also be similiar, such that they can be described by these topics in a \"compact\" way. So ideally the similiarity in the latent ***topic space*** would imply the the similiarity in both the observed ***word space*** as well as the ***document space*** - this is where the word \"latent\" in the name come from.\n",
    "\n",
    "The LDA algorithms has two main parameters controlling \n",
    "1. how sparse the topics are in terms of the distribution of keywords in each topic \n",
    "2. how sparse the documents are in terms of the distribution of topics in each document\n",
    "\n",
    "Later we will see how these parameters help with fining minor topics in a skewed distribution. Finding the right parameter values is mostly based on experimental experiences. \n",
    "\n",
    "(***TODO: make it clearer on this part***)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compared to SVD, the topics found by LDA is much more human understandable. This is shown as the results on the clearcut-topic texts below. Within each topic, there is a clear indication of the keywords' connections based on their co-occurrence. This is different from what we observed in the results of SVD, specially,\n",
    "- the topics from LDA can be duplicated.\n",
    "- different topics can share keywords if they co-appear frequently enough with other keywords in different topics. e.g., the word \"we\" have been repeated in all the topics below simply because it co-occurs with all the other words in each sentence.\n",
    "\n",
    "There is also a difference in combining it with different vectorizations - `tfidf` if you don't want to see too many common words in the topics."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergers | love | we\n",
      "Topic 1: bergers | love | we\n",
      "Topic 2: love | we\n",
      "Topic 3: hate | sandwiches | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"clearcut topics\"], \"lda\", 4, vec_model=\"tf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergers | love | we\n",
      "Topic 1: bergers | love | we\n",
      "Topic 2: hate | sandwiches | we\n",
      "Topic 3: bergers | love | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"clearcut topics\"], \"lda\", 4, vec_model=\"tfidf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I have introduced how to tune the topic-skewness parameter to deal with unbalanced topic modelling. In the sklearn implementation, this parameter is `topic_word_prior`. (and the other one is `doc_topic_prior` that controls the sparseness of topics in each doc). \n",
    "\n",
    "The default value of `topic_word_prior` is $\\frac{1}{n\\_topics} $. which assumes an even distribution of topics. A smaller value will make it more \"uneven\". This is illustrated in the results below."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***The minor topic `we love bergers` have been \"glued\" to a bigger one if the topic distribution is assumed to be symmetric.***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: hate | sandwiches | we\n",
      "Topic 1: bergers | hate | love | sandwiches | we\n",
      "Topic 2: bergers | hate | love | sandwiches | we\n",
      "Topic 3: hate | sandwiches | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"unbalanced topics\"], \"lda\", 4, vec_model=\"tf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Using a smaller `topic_word_prior` value will help capture the minor topics, because now the topics are forced to be more sparse in choosing keywords.***"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: hate | sandwiches | we\n",
      "Topic 1: bergers | love | we\n",
      "Topic 2: hate | sandwiches | we\n",
      "Topic 3: hate | sandwiches | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"unbalanced topics\"], \"lda\", 4, vec_model=\"tf\", topic_word_prior=1e-5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Noisy texts is also a challenge for LDA. From below we can see LDA's result on noisy-topics is not clear because there is no clear connections between the different typos of the same words."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergerx | bergexs | bergxrs | berxers | bexgers | bxrgers | hate | love | sandwichex | sandwicxes | sandwixhes | sandwxches | sandxiches | sanxwiches | saxdwiches | sxndwiches | we | xandwiches | xergers\n",
      "Topic 1: bergerx | bergexs | bergxrs | berxers | bexgers | bxrgers | hate | love | sandwichex | sandwicxes | sandwixhes | sandwxches | sandxiches | sanxwiches | saxdwiches | sxndwiches | we | xandwiches | xergers\n",
      "Topic 2: bergerx | bergexs | bergxrs | berxers | bexgers | bxrgers | hate | love | sandwichex | sandwicxes | sandwixhes | sandwxches | sandxiches | sanxwiches | saxdwiches | sxndwiches | we | xandwiches | xergers\n"
     ]
    }
   ],
   "source": [
    "print find_topic(sample_texts[\"noisy topics\"],\"lda\",3, vec_model = \"tfidf\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In summary,\n",
    "\n",
    "- Topics generated by LDA is close to human understanding, in terms of grouping co-occuring words together.\n",
    "- However, these topics may not necessarily be the ones that distinguish different groups of documents - sometimes enforcing the documents to be sparse and specific in topics may help. \n",
    "- For example, in a suboptimal parameter setting, the minor topics could be \"obsorbed\" into a major one, if they happen to have shared keywords.\n",
    "- This is different from SVD's results, where the topics are generated to be far away (orthogonal) from each other as much as possible.\n",
    "- As a result, topics generated by LDA may not necessarily optimal for representing the documents for other purposes, such as document classifications.\n",
    "- A good understanding of your text data is the key to good performance of LDA. But usually you don't have this knowledge at the beginning. LDA is usually expensive to run. There are other ways to help understand the structure of data before using LDA."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 NMF: an LDA-like decomposition\n",
    "\n",
    "NMF has been discussed as a [special case of LDA](https://www.quora.com/What-are-the-pros-and-cons-of-LDA-and-NMF-in-topic-modeling#). The theory behind their link might be complicated to understand. But in practice, NMF can be mostly seen as a LDA of which the parameters have been fixed to enforce a sparse solution. So it may not be as flexible as LDA if you want to find multiple topics in single documents, e.g., from long articles. But it could work very well out of box for corpora of short texts. This makes NMF attractive for short text analysis because its computation is usually much cheaper than LDA. \n",
    "\n",
    "On the other hand, the most discussed weakness of NMF is the inconsistency of its results - when you set the number of topics to be too high than the reality in texts, NMF might generate some rubbish out of nowhere. LDA is more robust to a big variety of different topic numbers."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's first see an example of NMF being inconsistent. For clearcut topics texts, when we set topic number = 5, which is close to reality (= 2), the generated topics are of good quality."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: hate | sandwiches | we\n",
      "Topic 1: hate | sandwiches | we\n",
      "Topic 2: bergers | love | we\n",
      "Topic 3: hate | sandwiches | we\n",
      "Topic 4: hate | sandwiches | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"clearcut topics\"], \"nmf\", 5, vec_model=\"tf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, when we increase the number of topics to 25 (much larger than 2), some werid topics have started to jump out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: hate | sandwiches | we\n",
      "Topic 1: hate | sandwiches | we\n",
      "Topic 2: bergers | love | we\n",
      "Topic 3: we\n",
      "Topic 4: hate | sandwiches | we\n",
      "Topic 5: sandwiches\n",
      "Topic 6: bergers | love | we\n",
      "Topic 7: hate\n",
      "Topic 8: love | we\n",
      "Topic 9: we\n",
      "Topic 10: bergers\n",
      "Topic 11: hate | sandwiches | we\n",
      "Topic 12: hate | sandwiches | we\n",
      "Topic 13: hate\n",
      "Topic 14: bergers | love | we\n",
      "Topic 15: hate | sandwiches | we\n",
      "Topic 16: love | we\n",
      "Topic 17: hate | sandwiches | we\n",
      "Topic 18: bergers | love | we\n",
      "Topic 19: hate | sandwiches | we\n",
      "Topic 20: sandwiches | we\n",
      "Topic 21: hate | sandwiches\n",
      "Topic 22: we\n",
      "Topic 23: bergers | love | we\n",
      "Topic 24: hate | sandwiches | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"clearcut topics\"], \"nmf\", 25, vec_model=\"tf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Running the same experiment on LDA, the results is much more consistent."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergers | love | we\n",
      "Topic 1: bergers | love | we\n",
      "Topic 2: bergers | love | we\n",
      "Topic 3: hate | sandwiches | we\n",
      "Topic 4: hate | sandwiches | we\n",
      "Topic 5: bergers | hate | love | sandwiches | we\n",
      "Topic 6: bergers | love | we\n",
      "Topic 7: hate | sandwiches | we\n",
      "Topic 8: bergers | love | we\n",
      "Topic 9: bergers | love | we\n",
      "Topic 10: bergers | love | we\n",
      "Topic 11: bergers | love | we\n",
      "Topic 12: bergers | love | we\n",
      "Topic 13: bergers | hate | love | sandwiches | we\n",
      "Topic 14: bergers | hate | love | sandwiches | we\n",
      "Topic 15: bergers | love | we\n",
      "Topic 16: bergers | hate | love | sandwiches | we\n",
      "Topic 17: bergers | love | we\n",
      "Topic 18: bergers | love | we\n",
      "Topic 19: bergers | love | we\n",
      "Topic 20: bergers | love | we\n",
      "Topic 21: bergers | love | we\n",
      "Topic 22: bergers | love | we\n",
      "Topic 23: hate | sandwiches | we\n",
      "Topic 24: bergers | love | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"clearcut topics\"], \"lda\", 25, vec_model=\"tf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Set with an appropriate # of topics, NMF is also good at finding unbalanced topic distributions. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: hate | sandwiches | we\n",
      "Topic 1: hate | sandwiches | we\n",
      "Topic 2: bergers | love | we\n",
      "Topic 3: hate | sandwiches | we\n",
      "Topic 4: hate | sandwiches | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"unbalanced topics\"], \"nmf\", 5, vec_model=\"tfidf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Impressively, NMF seems to be the only topic-finding model that can deal with \"noisy texts\" without a lot of fine-tuning. This is very useful for the first round of exploration of your data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergxrs | berxers | bexgers | bxrgers | love | we\n",
      "Topic 1: hate | sandwichex | sandwicxes | sandwixhes | sandwxches | sanxwiches | saxdwiches | sxndwiches | we | xandwiches\n",
      "Topic 2: bergerx | berxers | bexgers | bxrgers | love | we\n",
      "Topic 3: hate | sandwichex | sandwxches | sandxiches | saxdwiches | sxndwiches | we\n",
      "Topic 4: bergexs | berxers | bexgers | bxrgers | love | we | xergers\n"
     ]
    }
   ],
   "source": [
    "print find_topic(sample_texts[\"noisy topics\"],\"nmf\",5, vec_model = \"tfidf\",)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In summary,\n",
    "- NMF seems to work very well with short texts out-of-box. \n",
    "- One possible explaination is that its assumption has a good match with the nature of short texts that we discussed above.\n",
    "- NMF is usually cheaper in computation compared to LDA.\n",
    "- The main cons of NMF is its gradual inconsistency of results when keep increasing number of topics."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 KMeans: cheap and powerful\n",
    "\n",
    "Clustering method such as KMeans can group documents based on their vector representations (or even directly based on their distance matrices). However it is not usually seen as a topic-finding method because it is hard to explain its results as groups of keywords.\n",
    "\n",
    "However, when used together with tf/tfidf, the centers of the clusters can be interpreted as a probability over words in the same way as in LDA and NMF."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: hate | sandwiches | we\n",
      "Topic 1: bergers | love | we\n",
      "Topic 2: hate | sandwiches | we\n",
      "Topic 3: bergers | love | we\n",
      "Topic 4: bergers | love | we\n",
      "Topic 5: bergers | love | we\n",
      "Topic 6: bergers | love | we\n",
      "Topic 7: bergers | love | we\n",
      "Topic 8: bergers | love | we\n",
      "Topic 9: bergers | love | we\n"
     ]
    }
   ],
   "source": [
    "print find_topic(sample_texts[\"clearcut topics\"],\"kmeans\",10, vec_model = \"tf\",)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: hate | sandwiches | we\n",
      "Topic 1: bergers | love | we\n",
      "Topic 2: hate | sandwiches | we\n",
      "Topic 3: hate | sandwiches | we\n",
      "Topic 4: hate | sandwiches | we\n",
      "Topic 5: hate | sandwiches | we\n",
      "Topic 6: hate | sandwiches | we\n",
      "Topic 7: hate | sandwiches | we\n",
      "Topic 8: hate | sandwiches | we\n",
      "Topic 9: hate | sandwiches | we\n"
     ]
    }
   ],
   "source": [
    "print find_topic(sample_texts[\"unbalanced topics\"],\"kmeans\",10, vec_model = \"tf\",)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergerx | berxers | bexgers | bxrgers | love | we\n",
      "Topic 1: hate | sandwichex | sandwxches | saxdwiches | sxndwiches | we\n",
      "Topic 2: bergxrs | love | we\n",
      "Topic 3: hate | sandwicxes | we\n",
      "Topic 4: bergexs | love | we\n",
      "Topic 5: hate | sandxiches | we\n",
      "Topic 6: hate | sanxwiches | we\n",
      "Topic 7: love | we | xergers\n",
      "Topic 8: hate | sandwixhes | we\n",
      "Topic 9: hate | we | xandwiches\n"
     ]
    }
   ],
   "source": [
    "print find_topic(sample_texts[\"noisy topics\"],\"kmeans\",10, vec_model = \"tf\",)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In summary,\n",
    "\n",
    "Just like NMF, KMeans also performs well on different types of short texts, including finding unbalanced topic distributions and dealing with noisy data. Even better, its results seem more consistent than NMF's to the setting of number of topics.\n",
    "\n",
    "Furthermore, its computation is usually cheap and there are [implementations that can scale up to very large datasets](http://scikit-learn.org/stable/modules/generated/sklearn.cluster.MiniBatchKMeans.html). Unlike LDA, the integration of clustering with other document-vectoization methods is much easier to implement. For example, if external large corpus is available to train a word-embedding model, topic-finding via clustering can be easily extended by using the word vectors that convey more semantic meanings. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5 Finding topics with high semantic coherence\n",
    "\n",
    "Lastly, I want to briefly discuss another perspective of topic finding. In most cases we are interested in grouping documents according to their topic distributions and finding describing keywords for each topic. Another way to look at the topics is to see whether they can group \"semantically connected\" words into the same groups. \n",
    "\n",
    "Most researchers agree that the \"semantic\" of a word is defined by its contexts, i.e., other words surrounding it. For example, \"love\" and \"hate\" can be seen as semantically connected because both words can be used in the same context \"I _ apples.\" In fact, one of the most important focus of word embedding research is to find vector representations of the words, phrases, or even documents such that their semantic closeness is retained in the vector space. \n",
    "\n",
    "Finding topics grouping \"semantically similiar\" words may not necessarily be the same as grouping words that co-occur frequently. From the results below, we can see that most methods discussed are generating co-occurance oriented topics instead of semantic ones. Only SVD shed some lights on it - both \"bergers vs sandwiches\" and \"love vs hate\" groups are generated. \n",
    "\n",
    "But please bear in mind that these results are only based on very simple toy-like texts. I include them here only to further highlight the differences of models from another perspective.   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergers | hate | love | sandwiches | we\n",
      "Topic 1: bergers | ^sandwiches\n",
      "Topic 2: ^hate | love\n",
      "Topic 3: ^bergers | ^hate | ^love | ^sandwiches | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"semantic topics\"], \"svd\", 4, vec_model=\"tfidf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: hate | sandwiches | we\n",
      "Topic 1: bergers | love | we\n",
      "Topic 2: bergers | we\n",
      "Topic 3: love | sandwiches | we\n",
      "Topic 4: hate | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"semantic topics\"], \"nmf\", 5, vec_model=\"tfidf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: bergers | love | we\n",
      "Topic 1: bergers | hate | we\n",
      "Topic 2: love | sandwiches | we\n",
      "Topic 3: bergers | love | we\n",
      "Topic 4: bergers | love | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"semantic topics\"], \"lda\", 5, vec_model=\"tfidf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Topic 0: hate | sandwiches | we\n",
      "Topic 1: love | sandwiches | we\n",
      "Topic 2: bergers | hate | we\n",
      "Topic 3: bergers | love | we\n",
      "Topic 4: hate | sandwiches | we\n"
     ]
    }
   ],
   "source": [
    "print(find_topic(sample_texts[\"semantic topics\"], \"kmeans\", 5, vec_model=\"tfidf\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Summary\n",
    "\n",
    "- Corpora of short texts have some unique characteristics that need to be considered when doing topic finding.\n",
    "- Choice of a method depends on the definition of \"topics\" (high co-occurance, semantic-similarity) and the purpose of topic finding (representation of docs, summarization, outlier detection and etc.)\n",
    "- It's usually a good idea to start with ***KMeans*** or ***NMF***, and to quickly get a better understaning of the structures of texts, including but not limited to,\n",
    "    - sparseness of words in topics\n",
    "    - sparseness of topics in documents\n",
    "    - number of topics\n",
    "    - number of words in each topic\n",
    "    - what does co-occurance imply in your data\n",
    "- ***LDA*** is flexible for different types of tasks. But its parameter tunning should be based on a good understanding of the data. So if you want to try LDA, keep at least another model such as KMeans or NMF as a baseline.\n",
    "- ***SVD*** is mostly useful to capture the variances in the texts. For example, if your data is semi-structured, e.g., forms of a template, screenshots, html tables, SVD might be useful in analyzing them when used together with regular expressions.\n",
    "\n",
    "***Thank you for reading. I am sure there will be mistakes, inaccuracies. Please feel free to PR at my [github](https://github.com/dolaameng/tutorials.git).***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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
}