sample/nlp-3_basic_distance_measurement_in_text_mining.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://cdn-images-1.medium.com/max/800/0*IeVJrm09xE3mrRr6.jpg)\n",
    "Photo Credit: https://pixabay.com/en/hong-kong-night-light-rail-city-2288999/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3 basic Distance Measurement in Text Mining\n",
    "In NLP, we also want to find the similarity among sentence or document. Text is not like number and coordination that we cannot compare the different between \"Apple\" and \"Orange\" but similarity score can be calculated."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Why?\n",
    "Since we cannot simply subtract between \"Apple is fruit\" and \"Orange is fruit\" so that we have to find a way to convert text to numeric in order to calculate it. Having the score, we can understand how similar among two objects."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# When?\n",
    "In my data science work, I tried:\n",
    "- Compare whether 2 article are describing same news\n",
    "- Identifying similar documents\n",
    "- Classifying the category by giving product description"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How?\n",
    "In this article, we will go through 4 basic distance measurements:\n",
    "Euclidean Distance\n",
    "Cosine Distance\n",
    "Jaccard Similarity\n",
    "\n",
    "Before any distance measurement, text have to be tokenzied. If you do not familiar with word tokenization, you can visit this [article](https://medium.com/@makcedward/nlp-pipeline-word-tokenization-part-1-4b2b547e6a3)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import nltk\n",
    "import sklearn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "    News headline get from \n",
    "    \n",
    "    https://www.reuters.com/article/us-musk-tunnel/elon-musks-boring-co-to-build-high-speed-airport-link-in-chicago-idUSKBN1JA224\n",
    "    http://money.cnn.com/2018/06/14/technology/elon-musk-boring-company-chicago/index.html\n",
    "    https://www.theverge.com/2018/6/13/17462496/elon-musk-boring-company-approved-tunnel-chicago\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "news_headline1 = \"Elon Musk's Boring Co to build high-speed airport link in Chicago\"\n",
    "news_headline2 = \"Elon Musk's Boring Company to build high-speed Chicago airport link\"\n",
    "news_headline3 = \"Elon Musk’s Boring Company approved to build high-speed transit between downtown Chicago and O’Hare Airport\"\n",
    "news_headline4 = \"Both apple and orange are fruit\"\n",
    "\n",
    "news_headlines = [news_headline1, news_headline2, news_headline3, news_headline4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Preprocessing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tokenize headline to list of words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First 7 tokens from news headlines:  ['Elon', 'Musk', \"'s\", 'Boring', 'Co', 'to', 'build']\n",
      "First 7 tokens from news headlines:  ['Elon', 'Musk', \"'s\", 'Boring', 'Company', 'to', 'build']\n",
      "First 7 tokens from news headlines:  ['Elon', 'Musk', '’', 's', 'Boring', 'Company', 'approved']\n",
      "First 7 tokens from news headlines:  ['Both', 'apple', 'and', 'orange', 'are', 'fruit']\n"
     ]
    }
   ],
   "source": [
    "news_headline1_tokens = nltk.word_tokenize(news_headline1)\n",
    "news_headline2_tokens = nltk.word_tokenize(news_headline2)\n",
    "news_headline3_tokens = nltk.word_tokenize(news_headline3)\n",
    "news_headline4_tokens = nltk.word_tokenize(news_headline4)\n",
    "\n",
    "for words in [news_headline1_tokens, news_headline2_tokens, news_headline3_tokens, news_headline4_tokens]:\n",
    "    print('First 7 tokens from news headlines: ', words[:7])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "All Tokens:\n",
      "['Elon', 'Musk', \"'s\", 'Boring', 'Co', 'to', 'build', 'high-speed', 'airport', 'link', 'in', 'Chicago', 'Elon', 'Musk', \"'s\", 'Boring', 'Company', 'to', 'build', 'high-speed', 'Chicago', 'airport', 'link', 'Elon', 'Musk', '’', 's', 'Boring', 'Company', 'approved', 'to', 'build', 'high-speed', 'transit', 'between', 'downtown', 'Chicago', 'and', 'O', '’', 'Hare', 'Airport', 'Both', 'apple', 'and', 'orange', 'are', 'fruit']\n",
      "\n",
      "Original Input: ['Elon', 'Musk', \"'s\", 'Boring', 'Co', 'to', 'build', 'high-speed', 'airport', 'link', 'in', 'Chicago']\n",
      "Encoded by Label Encoder: [ 7  9  0  2  5 25 17 20 11 22 21  4]\n",
      "Encoded by OneHot Encoder:\n",
      "  (0, 7)\t1.0\n",
      "  (1, 9)\t1.0\n",
      "  (2, 0)\t1.0\n",
      "  (3, 2)\t1.0\n",
      "  (4, 5)\t1.0\n",
      "  (5, 25)\t1.0\n",
      "  (6, 17)\t1.0\n",
      "  (7, 20)\t1.0\n",
      "  (8, 11)\t1.0\n",
      "  (9, 22)\t1.0\n",
      "  (10, 21)\t1.0\n",
      "  (11, 4)\t1.0\n",
      "\n",
      "Original Input: ['Elon', 'Musk', \"'s\", 'Boring', 'Company', 'to', 'build', 'high-speed', 'Chicago', 'airport', 'link']\n",
      "Encoded by Label Encoder: [ 7  9  0  2  6 25 17 20  4 11 22]\n",
      "Encoded by OneHot Encoder:\n",
      "  (0, 7)\t1.0\n",
      "  (1, 9)\t1.0\n",
      "  (2, 0)\t1.0\n",
      "  (3, 2)\t1.0\n",
      "  (4, 6)\t1.0\n",
      "  (5, 25)\t1.0\n",
      "  (6, 17)\t1.0\n",
      "  (7, 20)\t1.0\n",
      "  (8, 4)\t1.0\n",
      "  (9, 11)\t1.0\n",
      "  (10, 22)\t1.0\n",
      "\n",
      "Original Input: ['Elon', 'Musk', '’', 's', 'Boring', 'Company', 'approved', 'to', 'build', 'high-speed', 'transit', 'between', 'downtown', 'Chicago', 'and', 'O', '’', 'Hare', 'Airport']\n",
      "Encoded by Label Encoder: [ 7  9 27 24  2  6 14 25 17 20 26 16 18  4 12 10 27  8  1]\n",
      "Encoded by OneHot Encoder:\n",
      "  (0, 7)\t1.0\n",
      "  (1, 9)\t1.0\n",
      "  (2, 27)\t1.0\n",
      "  (3, 24)\t1.0\n",
      "  (4, 2)\t1.0\n",
      "  (5, 6)\t1.0\n",
      "  (6, 14)\t1.0\n",
      "  (7, 25)\t1.0\n",
      "  (8, 17)\t1.0\n",
      "  (9, 20)\t1.0\n",
      "  (10, 26)\t1.0\n",
      "  (11, 16)\t1.0\n",
      "  (12, 18)\t1.0\n",
      "  (13, 4)\t1.0\n",
      "  (14, 12)\t1.0\n",
      "  (15, 10)\t1.0\n",
      "  (16, 27)\t1.0\n",
      "  (17, 8)\t1.0\n",
      "  (18, 1)\t1.0\n",
      "\n",
      "Original Input: ['Both', 'apple', 'and', 'orange', 'are', 'fruit']\n",
      "Encoded by Label Encoder: [ 3 13 12 23 15 19]\n",
      "Encoded by OneHot Encoder:\n",
      "  (0, 3)\t1.0\n",
      "  (1, 13)\t1.0\n",
      "  (2, 12)\t1.0\n",
      "  (3, 23)\t1.0\n",
      "  (4, 15)\t1.0\n",
      "  (5, 19)\t1.0\n"
     ]
    }
   ],
   "source": [
    "from numpy import argmax\n",
    "\n",
    "def transform(headlines):\n",
    "    tokens = [w for s in headlines for w in s ]\n",
    "    print()\n",
    "    print('All Tokens:')\n",
    "    print(tokens)\n",
    "\n",
    "    results = []\n",
    "    label_enc = sklearn.preprocessing.LabelEncoder()\n",
    "    onehot_enc = sklearn.preprocessing.OneHotEncoder()\n",
    "    \n",
    "    encoded_all_tokens = label_enc.fit_transform(list(set(tokens)))\n",
    "    encoded_all_tokens = encoded_all_tokens.reshape(len(encoded_all_tokens), 1)\n",
    "    \n",
    "    onehot_enc.fit(encoded_all_tokens)\n",
    "    \n",
    "    for headline_tokens in headlines:\n",
    "        print()\n",
    "        print('Original Input:', headline_tokens)\n",
    "        \n",
    "        encoded_words = label_enc.transform(headline_tokens)\n",
    "        print('Encoded by Label Encoder:', encoded_words)\n",
    "        \n",
    "        encoded_words = onehot_enc.transform(encoded_words.reshape(len(encoded_words), 1))\n",
    "        print('Encoded by OneHot Encoder:')\n",
    "        print(encoded_words)\n",
    "\n",
    "        results.append(np.sum(encoded_words.toarray(), axis=0))\n",
    "    \n",
    "    return results\n",
    "\n",
    "transformed_results = transform([\n",
    "    news_headline1_tokens, news_headline2_tokens, news_headline3_tokens, news_headline4_tokens])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Euclidean Distance\n",
    "\n",
    "![](https://cdn-images-1.medium.com/max/800/0*Bd8VtxN8ql4qw4vo)\n",
    "\n",
    "Photo Credit: http://dataaspirant.com/2015/04/11/five-most-popular-similarity-measures-implementation-in-python/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comparing the shortest distance among two objects. It uses Pythagorean Theorem which learnt from secondary school.\n",
    "\n",
    "Score means the distance between two objects. If it is 0, it means that both objects are identical. The following example shows score when comparing the first sentence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Master Sentence: Elon Musk's Boring Co to build high-speed airport link in Chicago\n",
      "-----\n",
      "Score: 0.00, Comparing Sentence: Elon Musk's Boring Co to build high-speed airport link in Chicago\n",
      "-----\n",
      "Score: 1.73, Comparing Sentence: Elon Musk's Boring Company to build high-speed Chicago airport link\n",
      "-----\n",
      "Score: 4.36, Comparing Sentence: Elon Musk’s Boring Company approved to build high-speed transit between downtown Chicago and O’Hare Airport\n",
      "-----\n",
      "Score: 4.24, Comparing Sentence: Both apple and orange are fruit\n"
     ]
    }
   ],
   "source": [
    "print('Master Sentence: %s' % news_headlines[0])\n",
    "for i, news_headline in enumerate(news_headlines):\n",
    "    score = sklearn.metrics.pairwise.euclidean_distances([transformed_results[i]], [transformed_results[0]])[0][0]\n",
    "    print('-----')\n",
    "    print('Score: %.2f, Comparing Sentence: %s' % (score, news_headline))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cosine Similarity\n",
    "\n",
    "![](https://i2.wp.com/dataaspirant.com/wp-content/uploads/2015/04/cosine.png)\n",
    "\n",
    "Photo Credit: http://dataaspirant.com/2015/04/11/five-most-popular-similarity-measures-implementation-in-python/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Determine the angle between two objects is the calculation method to the find similarity. The range of score is 0 to 1. If score is 1, it means that they are same in orientation (not magnitude). The following example shows score when comparing the first sentence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Master Sentence: Elon Musk's Boring Co to build high-speed airport link in Chicago\n",
      "-----\n",
      "Score: 1.00, Comparing Sentence: Elon Musk's Boring Co to build high-speed airport link in Chicago\n",
      "-----\n",
      "Score: 0.87, Comparing Sentence: Elon Musk's Boring Company to build high-speed Chicago airport link\n",
      "-----\n",
      "Score: 0.44, Comparing Sentence: Elon Musk’s Boring Company approved to build high-speed transit between downtown Chicago and O’Hare Airport\n",
      "-----\n",
      "Score: 0.00, Comparing Sentence: Both apple and orange are fruit\n"
     ]
    }
   ],
   "source": [
    "print('Master Sentence: %s' % news_headlines[0])\n",
    "for i, news_headline in enumerate(news_headlines):\n",
    "    score = sklearn.metrics.pairwise.cosine_similarity([transfaormed_results[i]], [transformed_results[0]])[0][0]\n",
    "    print('-----')\n",
    "    print('Score: %.2f, Comparing Sentence: %s' % (score, news_headline))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Jaccard Similarity\n",
    "![](https://i0.wp.com/dataaspirant.com/wp-content/uploads/2015/04/jaccard_similariyt.png?resize=768%2C307)\n",
    "Photo Credit: http://dataaspirant.com/2015/04/11/five-most-popular-similarity-measures-implementation-in-python/\n",
    "\n",
    "The measurement is refer to number of common words over all words. More commons mean both objects should be similarity.\n",
    "Jaccard Similarity = (Intersection of A and B) / (Union of A and B)\n",
    "The range is 0 to 1. If score is 1, it means that they are identical. There is no any common word between the first sentence and the last sentence so the score is 0. The following example shows score when comparing the first sentence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Master Sentence: Elon Musk's Boring Co to build high-speed airport link in Chicago\n",
      "-----\n",
      "Score: 1.00, Comparing Sentence: Elon Musk's Boring Co to build high-speed airport link in Chicago\n",
      "-----\n",
      "Score: 0.67, Comparing Sentence: Elon Musk's Boring Company to build high-speed Chicago airport link\n",
      "-----\n",
      "Score: 0.17, Comparing Sentence: Elon Musk’s Boring Company approved to build high-speed transit between downtown Chicago and O’Hare Airport\n",
      "-----\n",
      "Score: 0.00, Comparing Sentence: Both apple and orange are fruit\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "    Finding the posistion (from lookup table) of word instead of using 1 or 0\n",
    "    to prevent misleading of the meaning of \"common\" word\n",
    "\"\"\"\n",
    "\n",
    "def calculate_position(values):\n",
    "    x = []\n",
    "    for pos, matrix in enumerate(values):\n",
    "        if matrix > 0:\n",
    "            x.append(pos)\n",
    "    return x\n",
    "\n",
    "\"\"\"\n",
    "    Since scikit-learn can only compare same number of dimension of input. \n",
    "    Add padding to the shortest sentence.\n",
    "\"\"\"\n",
    "def padding(sentence1, sentence2):\n",
    "    x1 = sentence1.copy()\n",
    "    x2 = sentence2.copy()\n",
    "    \n",
    "    diff = len(x1) - len(x2)\n",
    "    \n",
    "    if diff > 0:\n",
    "        for i in range(0, diff):\n",
    "            x2.append(-1)\n",
    "    elif diff < 0:\n",
    "        for i in range(0, abs(diff)):\n",
    "            x1.append(-1)\n",
    "    \n",
    "    return x1, x2    \n",
    "\n",
    "y_actual = calculate_position(transformed_results[0])\n",
    "\n",
    "print('Master Sentence: %s' % news_headlines[0])\n",
    "for i, news_headline in enumerate(news_headlines):\n",
    "    y_compare = calculate_position(transformed_results[i])\n",
    "    x1, x2 = padding(y_actual, y_compare)\n",
    "    score = sklearn.metrics.jaccard_similarity_score(x1, x2)\n",
    "    print('-----')\n",
    "    print('Score: %.2f, Comparing Sentence: %s' % (score, news_headline))\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Conclusion\n",
    "Three methods also have same assumption which is the document (or sentence) are \n",
    "__similar if having common words\n",
    "__. This idea is very straight forward and simple. It fits some basic cases such as comparing first 2 sentence. However, the score is relative low by comparing first sentence and third sentence although both of them describe same news. \n",
    "\n",
    "Another limitation is that above methods __does not handle synonym scenario__. For example buy and purchase, it should have same meaning (in some cases) but above methods will treat both words are difference. \n",
    "\n",
    "So what is the cue? You may consider to use Word Embedding which introduced by Tomas Mikolov in 2013."
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}