2_Plagiarism_Feature_Engineering.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Plagiarism Detection, Feature Engineering\n",
    "\n",
    "In this project, you will be tasked with building a plagiarism detector that examines an answer text file and performs binary classification; labeling that file as either plagiarized or not, depending on how similar that text file is to a provided, source text. \n",
    "\n",
    "Your first task will be to create some features that can then be used to train a classification model. This task will be broken down into a few discrete steps:\n",
    "\n",
    "* Clean and pre-process the data.\n",
    "* Define features for comparing the similarity of an answer text and a source text, and extract similarity features.\n",
    "* Select \"good\" features, by analyzing the correlations between different features.\n",
    "* Create train/test `.csv` files that hold the relevant features and class labels for train/test data points.\n",
    "\n",
    "In the _next_ notebook, Notebook 3, you'll use the features and `.csv` files you create in _this_ notebook to train a binary classification model in a SageMaker notebook instance.\n",
    "\n",
    "You'll be defining a few different similarity features, as outlined in [this paper](https://s3.amazonaws.com/video.udacity-data.com/topher/2019/January/5c412841_developing-a-corpus-of-plagiarised-short-answers/developing-a-corpus-of-plagiarised-short-answers.pdf), which should help you build a robust plagiarism detector!\n",
    "\n",
    "To complete this notebook, you'll have to complete all given exercises and answer all the questions in this notebook.\n",
    "> All your tasks will be clearly labeled **EXERCISE** and questions as **QUESTION**.\n",
    "\n",
    "It will be up to you to decide on the features to include in your final training and test data.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Read in the Data\n",
    "\n",
    "The cell below will download the necessary, project data and extract the files into the folder `data/`.\n",
    "\n",
    "This data is a slightly modified version of a dataset created by Paul Clough (Information Studies) and Mark Stevenson (Computer Science), at the University of Sheffield. You can read all about the data collection and corpus, at [their university webpage](https://ir.shef.ac.uk/cloughie/resources/plagiarism_corpus.html). \n",
    "\n",
    "> **Citation for data**: Clough, P. and Stevenson, M. Developing A Corpus of Plagiarised Short Answers, Language Resources and Evaluation: Special Issue on Plagiarism and Authorship Analysis, In Press. [Download]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "# NOTE:\n",
    "# you only need to run this cell if you have not yet downloaded the data\n",
    "# otherwise you may skip this cell or comment it out\n",
    "\n",
    "#!wget https://s3.amazonaws.com/video.udacity-data.com/topher/2019/January/5c4147f9_data/data.zip\n",
    "#!unzip data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "# import libraries\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import os"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This plagiarism dataset is made of multiple text files; each of these files has characteristics that are is summarized in a `.csv` file named `file_information.csv`, which we can read in using `pandas`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>File</th>\n",
       "      <th>Task</th>\n",
       "      <th>Category</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>g0pA_taska.txt</td>\n",
       "      <td>a</td>\n",
       "      <td>non</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>g0pA_taskb.txt</td>\n",
       "      <td>b</td>\n",
       "      <td>cut</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>g0pA_taskc.txt</td>\n",
       "      <td>c</td>\n",
       "      <td>light</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>g0pA_taskd.txt</td>\n",
       "      <td>d</td>\n",
       "      <td>heavy</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>g0pA_taske.txt</td>\n",
       "      <td>e</td>\n",
       "      <td>non</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             File Task Category\n",
       "0  g0pA_taska.txt    a      non\n",
       "1  g0pA_taskb.txt    b      cut\n",
       "2  g0pA_taskc.txt    c    light\n",
       "3  g0pA_taskd.txt    d    heavy\n",
       "4  g0pA_taske.txt    e      non"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "csv_file = 'data/file_information.csv'\n",
    "plagiarism_df = pd.read_csv(csv_file)\n",
    "\n",
    "# print out the first few rows of data info\n",
    "plagiarism_df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Types of Plagiarism\n",
    "\n",
    "Each text file is associated with one **Task** (task A-E) and one **Category** of plagiarism, which you can see in the above DataFrame.\n",
    "\n",
    "###  Tasks, A-E\n",
    "\n",
    "Each text file contains an answer to one short question; these questions are labeled as tasks A-E. For example, Task A asks the question: \"What is inheritance in object oriented programming?\"\n",
    "\n",
    "### Categories of plagiarism \n",
    "\n",
    "Each text file has an associated plagiarism label/category:\n",
    "\n",
    "**1. Plagiarized categories: `cut`, `light`, and `heavy`.**\n",
    "* These categories represent different levels of plagiarized answer texts. `cut` answers copy directly from a source text, `light` answers are based on the source text but include some light rephrasing, and `heavy` answers are based on the source text, but *heavily* rephrased (and will likely be the most challenging kind of plagiarism to detect).\n",
    "     \n",
    "**2. Non-plagiarized category: `non`.** \n",
    "* `non` indicates that an answer is not plagiarized; the Wikipedia source text is not used to create this answer.\n",
    "    \n",
    "**3. Special, source text category: `orig`.**\n",
    "* This is a specific category for the original, Wikipedia source text. We will use these files only for comparison purposes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Pre-Process the Data\n",
    "\n",
    "In the next few cells, you'll be tasked with creating a new DataFrame of desired information about all of the files in the `data/` directory. This will prepare the data for feature extraction and for training a binary, plagiarism classifier."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### EXERCISE: Convert categorical to numerical data\n",
    "\n",
    "You'll notice that the `Category` column in the data, contains string or categorical values, and to prepare these for feature extraction, we'll want to convert these into numerical values. Additionally, our goal is to create a binary classifier and so we'll need a binary class label that indicates whether an answer text is plagiarized (1) or not (0). Complete the below function `numerical_dataframe` that reads in a `file_information.csv` file by name, and returns a *new* DataFrame with a numerical `Category` column and a new `Class` column that labels each answer as plagiarized or not. \n",
    "\n",
    "Your function should return a new DataFrame with the following properties:\n",
    "\n",
    "* 4 columns: `File`, `Task`, `Category`, `Class`. The `File` and `Task` columns can remain unchanged from the original `.csv` file.\n",
    "* Convert all `Category` labels to numerical labels according to the following rules (a higher value indicates a higher degree of plagiarism):\n",
    "    * 0 = `non`\n",
    "    * 1 = `heavy`\n",
    "    * 2 = `light`\n",
    "    * 3 = `cut`\n",
    "    * -1 = `orig`, this is a special value that indicates an original file.\n",
    "* For the new `Class` column\n",
    "    * Any answer text that is not plagiarized (`non`) should have the class label `0`. \n",
    "    * Any plagiarized answer texts should have the class label `1`. \n",
    "    * And any `orig` texts will have a special label `-1`. \n",
    "\n",
    "### Expected output\n",
    "\n",
    "After running your function, you should get a DataFrame with rows that looks like the following: \n",
    "```\n",
    "\n",
    "        File\t     Task  Category  Class\n",
    "0\tg0pA_taska.txt\ta\t  0   \t0\n",
    "1\tg0pA_taskb.txt\tb\t  3   \t1\n",
    "2\tg0pA_taskc.txt\tc\t  2   \t1\n",
    "3\tg0pA_taskd.txt\td\t  1   \t1\n",
    "4\tg0pA_taske.txt\te\t  0\t   0\n",
    "...\n",
    "...\n",
    "99   orig_taske.txt    e     -1      -1\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read in a csv file and return a transformed dataframe\n",
    "def numerical_dataframe(csv_file='data/file_information.csv'):\n",
    "    '''Reads in a csv file which is assumed to have `File`, `Category` and `Task` columns.\n",
    "       This function does two things: \n",
    "       1) converts `Category` column values to numerical values \n",
    "       2) Adds a new, numerical `Class` label column.\n",
    "       The `Class` column will label plagiarized answers as 1 and non-plagiarized as 0.\n",
    "       Source texts have a special label, -1.\n",
    "       :param csv_file: The directory for the file_information.csv file\n",
    "       :return: A dataframe with numerical categories and a new `Class` label column'''\n",
    "    \n",
    "    # your code here\n",
    "    \n",
    "    df = pd.read_csv(csv_file)\n",
    "    df = df.replace({\"Category\":     {\"non\": 0, \"heavy\": 1, \"light\": 2, \"cut\": 3, \"orig\": -1}})\n",
    "    conditions = [(df.Category == 0), (df.Category < 0), (df.Category > 0)]\n",
    "    vals = [0, -1, 1]\n",
    "    df['Class'] = np.select(conditions, vals)\n",
    "    \n",
    "    return df\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test cells\n",
    "\n",
    "Below are a couple of test cells. The first is an informal test where you can check that your code is working as expected by calling your function and printing out the returned result.\n",
    "\n",
    "The **second** cell below is a more rigorous test cell. The goal of a cell like this is to ensure that your code is working as expected, and to form any variables that might be used in _later_ tests/code, in this case, the data frame, `transformed_df`.\n",
    "\n",
    "> The cells in this notebook should be run in chronological order (the order they appear in the notebook). This is especially important for test cells.\n",
    "\n",
    "Often, later cells rely on the functions, imports, or variables defined in earlier cells. For example, some tests rely on previous tests to work.\n",
    "\n",
    "These tests do not test all cases, but they are a great way to check that you are on the right track!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>File</th>\n",
       "      <th>Task</th>\n",
       "      <th>Category</th>\n",
       "      <th>Class</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>g0pA_taska.txt</td>\n",
       "      <td>a</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>g0pA_taskb.txt</td>\n",
       "      <td>b</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>g0pA_taskc.txt</td>\n",
       "      <td>c</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>g0pA_taskd.txt</td>\n",
       "      <td>d</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>g0pA_taske.txt</td>\n",
       "      <td>e</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>g0pB_taska.txt</td>\n",
       "      <td>a</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>g0pB_taskb.txt</td>\n",
       "      <td>b</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>g0pB_taskc.txt</td>\n",
       "      <td>c</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>g0pB_taskd.txt</td>\n",
       "      <td>d</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>g0pB_taske.txt</td>\n",
       "      <td>e</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             File Task  Category  Class\n",
       "0  g0pA_taska.txt    a         0      0\n",
       "1  g0pA_taskb.txt    b         3      1\n",
       "2  g0pA_taskc.txt    c         2      1\n",
       "3  g0pA_taskd.txt    d         1      1\n",
       "4  g0pA_taske.txt    e         0      0\n",
       "5  g0pB_taska.txt    a         0      0\n",
       "6  g0pB_taskb.txt    b         0      0\n",
       "7  g0pB_taskc.txt    c         3      1\n",
       "8  g0pB_taskd.txt    d         2      1\n",
       "9  g0pB_taske.txt    e         1      1"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# informal testing, print out the results of a called function\n",
    "# create new `transformed_df`\n",
    "transformed_df = numerical_dataframe(csv_file ='data/file_information.csv')\n",
    "\n",
    "# check work\n",
    "# check that all categories of plagiarism have a class label = 1\n",
    "transformed_df.head(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed!\n",
      "\n",
      "Example data: \n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>File</th>\n",
       "      <th>Task</th>\n",
       "      <th>Category</th>\n",
       "      <th>Class</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>g0pA_taska.txt</td>\n",
       "      <td>a</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>g0pA_taskb.txt</td>\n",
       "      <td>b</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>g0pA_taskc.txt</td>\n",
       "      <td>c</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>g0pA_taskd.txt</td>\n",
       "      <td>d</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>g0pA_taske.txt</td>\n",
       "      <td>e</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             File Task  Category  Class\n",
       "0  g0pA_taska.txt    a         0      0\n",
       "1  g0pA_taskb.txt    b         3      1\n",
       "2  g0pA_taskc.txt    c         2      1\n",
       "3  g0pA_taskd.txt    d         1      1\n",
       "4  g0pA_taske.txt    e         0      0"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# test cell that creates `transformed_df`, if tests are passed\n",
    "\n",
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "\n",
    "# importing tests\n",
    "import problem_unittests as tests\n",
    "\n",
    "# test numerical_dataframe function\n",
    "tests.test_numerical_df(numerical_dataframe)\n",
    "\n",
    "# if above test is passed, create NEW `transformed_df`\n",
    "transformed_df = numerical_dataframe(csv_file ='data/file_information.csv')\n",
    "\n",
    "# check work\n",
    "print('\\nExample data: ')\n",
    "transformed_df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Text Processing & Splitting Data\n",
    "\n",
    "Recall that the goal of this project is to build a plagiarism classifier. At it's heart, this task is a comparison text; one that looks at a given answer and a source text, compares them and predicts whether an answer has plagiarized from the source. To effectively do this comparison, and train a classifier we'll need to do a few more things: pre-process all of our text data and prepare the text files (in this case, the 95 answer files and 5 original source files) to be easily compared, and split our data into a `train` and `test` set that can be used to train a classifier and evaluate it, respectively. \n",
    "\n",
    "To this end, you've been provided code that adds  additional information to your `transformed_df` from above. The next two cells need not be changed; they add two additional columns to the `transformed_df`:\n",
    "\n",
    "1. A `Text` column; this holds all the lowercase text for a `File`, with extraneous punctuation removed.\n",
    "2. A `Datatype` column; this is a string value `train`, `test`, or `orig` that labels a data point as part of our train or test set\n",
    "\n",
    "The details of how these additional columns are created can be found in the `helpers.py` file in the project directory. You're encouraged to read through that file to see exactly how text is processed and how data is split.\n",
    "\n",
    "Run the cells below to get a `complete_df` that has all the information you need to proceed with plagiarism detection and feature engineering."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>File</th>\n",
       "      <th>Task</th>\n",
       "      <th>Category</th>\n",
       "      <th>Class</th>\n",
       "      <th>Text</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>g0pA_taska.txt</td>\n",
       "      <td>a</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>inheritance is a basic concept of object orien...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>g0pA_taskb.txt</td>\n",
       "      <td>b</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>pagerank is a link analysis algorithm used by ...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>g0pA_taskc.txt</td>\n",
       "      <td>c</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>the vector space model also called term vector...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>g0pA_taskd.txt</td>\n",
       "      <td>d</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>bayes theorem was names after rev thomas bayes...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>g0pA_taske.txt</td>\n",
       "      <td>e</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>dynamic programming is an algorithm design tec...</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             File Task  Category  Class  \\\n",
       "0  g0pA_taska.txt    a         0      0   \n",
       "1  g0pA_taskb.txt    b         3      1   \n",
       "2  g0pA_taskc.txt    c         2      1   \n",
       "3  g0pA_taskd.txt    d         1      1   \n",
       "4  g0pA_taske.txt    e         0      0   \n",
       "\n",
       "                                                Text  \n",
       "0  inheritance is a basic concept of object orien...  \n",
       "1  pagerank is a link analysis algorithm used by ...  \n",
       "2  the vector space model also called term vector...  \n",
       "3  bayes theorem was names after rev thomas bayes...  \n",
       "4  dynamic programming is an algorithm design tec...  "
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "import helpers \n",
    "\n",
    "# create a text column \n",
    "text_df = helpers.create_text_column(transformed_df)\n",
    "text_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sample processed text:\n",
      "\n",
      " inheritance is a basic concept of object oriented programming where the basic idea is to create new classes that add extra detail to existing classes this is done by allowing the new classes to reuse the methods and variables of the existing classes and new methods and classes are added to specialise the new class inheritance models the is kind of relationship between entities or objects  for example postgraduates and undergraduates are both kinds of student this kind of relationship can be visualised as a tree structure where student would be the more general root node and both postgraduate and undergraduate would be more specialised extensions of the student node or the child nodes  in this relationship student would be known as the superclass or parent class whereas  postgraduate would be known as the subclass or child class because the postgraduate class extends the student class  inheritance can occur on several layers where if visualised would display a larger tree structure for example we could further extend the postgraduate node by adding two extra extended classes to it called  msc student and phd student as both these types of student are kinds of postgraduate student this would mean that both the msc student and phd student classes would inherit methods and variables from both the postgraduate and student classes  \n"
     ]
    }
   ],
   "source": [
    "# after running the cell above\n",
    "# check out the processed text for a single file, by row index\n",
    "row_idx = 0 # feel free to change this index\n",
    "\n",
    "sample_text = text_df.iloc[0]['Text']\n",
    "\n",
    "print('Sample processed text:\\n\\n', sample_text)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Split data into training and test sets\n",
    "\n",
    "The next cell will add a `Datatype` column to a given DataFrame to indicate if the record is: \n",
    "* `train` - Training data, for model training.\n",
    "* `test` - Testing data, for model evaluation.\n",
    "* `orig` - The task's original answer from wikipedia.\n",
    "\n",
    "### Stratified sampling\n",
    "\n",
    "The given code uses a helper function which you can view in the `helpers.py` file in the main project directory. This implements [stratified random sampling](https://en.wikipedia.org/wiki/Stratified_sampling) to randomly split data by task & plagiarism amount. Stratified sampling ensures that we get training and test data that is fairly evenly distributed across task & plagiarism combinations. Approximately 26% of the data is held out for testing and 74% of the data is used for training.\n",
    "\n",
    "The function **train_test_dataframe** takes in a DataFrame that it assumes has `Task` and `Category` columns, and, returns a modified frame that indicates which `Datatype` (train, test, or orig) a file falls into. This sampling will change slightly based on a passed in *random_seed*. Due to a small sample size, this stratified random sampling will provide more stable results for a binary plagiarism classifier. Stability here is smaller *variance* in the accuracy of classifier, given a random seed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>File</th>\n",
       "      <th>Task</th>\n",
       "      <th>Category</th>\n",
       "      <th>Class</th>\n",
       "      <th>Text</th>\n",
       "      <th>Datatype</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>g0pA_taska.txt</td>\n",
       "      <td>a</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>inheritance is a basic concept of object orien...</td>\n",
       "      <td>train</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>g0pA_taskb.txt</td>\n",
       "      <td>b</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>pagerank is a link analysis algorithm used by ...</td>\n",
       "      <td>test</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>g0pA_taskc.txt</td>\n",
       "      <td>c</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>the vector space model also called term vector...</td>\n",
       "      <td>train</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>g0pA_taskd.txt</td>\n",
       "      <td>d</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>bayes theorem was names after rev thomas bayes...</td>\n",
       "      <td>train</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>g0pA_taske.txt</td>\n",
       "      <td>e</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>dynamic programming is an algorithm design tec...</td>\n",
       "      <td>train</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>g0pB_taska.txt</td>\n",
       "      <td>a</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>inheritance is a basic concept in object orien...</td>\n",
       "      <td>train</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>g0pB_taskb.txt</td>\n",
       "      <td>b</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>pagerank pr refers to both the concept and the...</td>\n",
       "      <td>train</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>g0pB_taskc.txt</td>\n",
       "      <td>c</td>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>vector space model is an algebraic model for r...</td>\n",
       "      <td>test</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>g0pB_taskd.txt</td>\n",
       "      <td>d</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>bayes theorem relates the conditional and marg...</td>\n",
       "      <td>train</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>g0pB_taske.txt</td>\n",
       "      <td>e</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>dynamic programming is a method for solving ma...</td>\n",
       "      <td>test</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             File Task  Category  Class  \\\n",
       "0  g0pA_taska.txt    a         0      0   \n",
       "1  g0pA_taskb.txt    b         3      1   \n",
       "2  g0pA_taskc.txt    c         2      1   \n",
       "3  g0pA_taskd.txt    d         1      1   \n",
       "4  g0pA_taske.txt    e         0      0   \n",
       "5  g0pB_taska.txt    a         0      0   \n",
       "6  g0pB_taskb.txt    b         0      0   \n",
       "7  g0pB_taskc.txt    c         3      1   \n",
       "8  g0pB_taskd.txt    d         2      1   \n",
       "9  g0pB_taske.txt    e         1      1   \n",
       "\n",
       "                                                Text Datatype  \n",
       "0  inheritance is a basic concept of object orien...    train  \n",
       "1  pagerank is a link analysis algorithm used by ...     test  \n",
       "2  the vector space model also called term vector...    train  \n",
       "3  bayes theorem was names after rev thomas bayes...    train  \n",
       "4  dynamic programming is an algorithm design tec...    train  \n",
       "5  inheritance is a basic concept in object orien...    train  \n",
       "6  pagerank pr refers to both the concept and the...    train  \n",
       "7  vector space model is an algebraic model for r...     test  \n",
       "8  bayes theorem relates the conditional and marg...    train  \n",
       "9  dynamic programming is a method for solving ma...     test  "
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_seed = 1 # can change; set for reproducibility\n",
    "\n",
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "import helpers\n",
    "\n",
    "# create new df with Datatype (train, test, orig) column\n",
    "# pass in `text_df` from above to create a complete dataframe, with all the information you need\n",
    "complete_df = helpers.train_test_dataframe(text_df, random_seed=random_seed)\n",
    "\n",
    "# check results\n",
    "complete_df.head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Determining Plagiarism\n",
    "\n",
    "Now that you've prepared this data and created a `complete_df` of information, including the text and class associated with each file, you can move on to the task of extracting similarity features that will be useful for plagiarism classification. \n",
    "\n",
    "> Note: The following code exercises, assume that the `complete_df` as it exists now, will **not** have its existing columns modified. \n",
    "\n",
    "The `complete_df` should always include the columns: `['File', 'Task', 'Category', 'Class', 'Text', 'Datatype']`. You can add additional columns, and you can create any new DataFrames you need by copying the parts of the `complete_df` as long as you do not modify the existing values, directly.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Similarity Features \n",
    "\n",
    "One of the ways we might go about detecting plagiarism, is by computing **similarity features** that measure how similar a given answer text is as compared to the original wikipedia source text (for a specific task, a-e). The similarity features you will use are informed by [this paper on plagiarism detection](https://s3.amazonaws.com/video.udacity-data.com/topher/2019/January/5c412841_developing-a-corpus-of-plagiarised-short-answers/developing-a-corpus-of-plagiarised-short-answers.pdf). \n",
    "> In this paper, researchers created features called **containment** and **longest common subsequence**. \n",
    "\n",
    "Using these features as input, you will train a model to distinguish between plagiarized and not-plagiarized text files.\n",
    "\n",
    "## Feature Engineering\n",
    "\n",
    "Let's talk a bit more about the features we want to include in a plagiarism detection model and how to calculate such features. In the following explanations, I'll refer to a submitted text file as a **Student Answer Text (A)** and the original, wikipedia source file (that we want to compare that answer to) as the **Wikipedia Source Text (S)**.\n",
    "\n",
    "### Containment\n",
    "\n",
    "Your first task will be to create **containment features**. To understand containment, let's first revisit a definition of [n-grams](https://en.wikipedia.org/wiki/N-gram). An *n-gram* is a sequential word grouping. For example, in a line like \"bayes rule gives us a way to combine prior knowledge with new information,\" a 1-gram is just one word, like \"bayes.\" A 2-gram might be \"bayes rule\" and a 3-gram might be \"combine prior knowledge.\"\n",
    "\n",
    "> Containment is defined as the **intersection** of the n-gram word count of the Wikipedia Source Text (S) with the n-gram word count of the Student  Answer Text (S) *divided* by the n-gram word count of the Student Answer Text.\n",
    "\n",
    "$$ \\frac{\\sum{count(\\text{ngram}_{A}) \\cap count(\\text{ngram}_{S})}}{\\sum{count(\\text{ngram}_{A})}} $$\n",
    "\n",
    "If the two texts have no n-grams in common, the containment will be 0, but if _all_ their n-grams intersect then the containment will be 1. Intuitively, you can see how having longer n-gram's in common, might be an indication of cut-and-paste plagiarism. In this project, it will be up to you to decide on the appropriate `n` or several `n`'s to use in your final model.\n",
    "\n",
    "### EXERCISE: Create containment features\n",
    "\n",
    "Given the `complete_df` that you've created, you should have all the information you need to compare any Student  Answer Text (A) with its appropriate Wikipedia Source Text (S). An answer for task A should be compared to the source text for task A, just as answers to tasks B, C, D, and E should be compared to the corresponding original source text.\n",
    "\n",
    "In this exercise, you'll complete the function, `calculate_containment` which calculates containment based upon the following parameters:\n",
    "* A given DataFrame, `df` (which is assumed to be the `complete_df` from above)\n",
    "* An `answer_filename`, such as 'g0pB_taskd.txt' \n",
    "* An n-gram length, `n`\n",
    "\n",
    "### Containment calculation\n",
    "\n",
    "The general steps to complete this function are as follows:\n",
    "1. From *all* of the text files in a given `df`, create an array of n-gram counts; it is suggested that you use a [CountVectorizer](https://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.CountVectorizer.html) for this purpose.\n",
    "2. Get the processed answer and source texts for the given `answer_filename`.\n",
    "3. Calculate the containment between an answer and source text according to the following equation.\n",
    "\n",
    "    >$$ \\frac{\\sum{count(\\text{ngram}_{A}) \\cap count(\\text{ngram}_{S})}}{\\sum{count(\\text{ngram}_{A})}} $$\n",
    "    \n",
    "4. Return that containment value.\n",
    "\n",
    "You are encouraged to write any helper functions that you need to complete the function below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'in object oriented programming inheritance is a way to form new classes instances of which are called objects using classes that have already been defined the inheritance concept was invented in 1967 for simula  the new classes known as derived classes take over or inherit attributes and behavior of the pre existing classes which are referred to as base classes or ancestor classes  it is intended to help reuse existing code with little or no modification  inheritance provides the support for representation by categorization in computer languages categorization is a powerful mechanism number of information processing crucial to human learning by means of generalization what is known about specific entities is applied to a wider group given a belongs relation can be established and cognitive economy less information needs to be stored about each specific entity only its particularities  inheritance is also sometimes called generalization because the is a relationships represent a hierarchy between classes of objects for instance a fruit is a generalization of apple  orange  mango and many others one can consider fruit to be an abstraction of apple orange etc conversely since apples are fruit i e  an apple is a fruit  apples may naturally inherit all the properties common to all fruit such as being a fleshy container for the seed of a plant  an advantage of inheritance is that modules with sufficiently similar interfaces can share a lot of code reducing the complexity of the program inheritance therefore has another view a dual called polymorphism which describes many pieces of code being controlled by shared control code inheritance is typically accomplished either by overriding replacing one or more methods exposed by ancestor or by adding new methods to those exposed by an ancestor  complex inheritance or inheritance used within a design that is not sufficiently mature may lead to the yo yo problem '"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "complete_df.loc[complete_df['Task'] == 'a'].loc[complete_df['Class'] == -1]['Text'].item()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.feature_extraction.text import CountVectorizer\n",
    "\n",
    "# Calculate the ngram containment for one answer file/source file pair in a df\n",
    "def calculate_containment(df, n, answer_filename):\n",
    "    '''Calculates the containment between a given answer text and its associated source text.\n",
    "       This function creates a count of ngrams (of a size, n) for each text file in our data.\n",
    "       Then calculates the containment by finding the ngram count for a given answer text, \n",
    "       and its associated source text, and calculating the normalized intersection of those counts.\n",
    "       :param df: A dataframe with columns,\n",
    "           'File', 'Task', 'Category', 'Class', 'Text', and 'Datatype'\n",
    "       :param n: An integer that defines the ngram size\n",
    "       :param answer_filename: A filename for an answer text in the df, ex. 'g0pB_taskd.txt'\n",
    "       :return: A single containment value that represents the similarity\n",
    "           between an answer text and its source text.\n",
    "    '''\n",
    "    \n",
    "    # your code here\n",
    "    a_text = df.loc[df['File'] == answer_filename]['Text'].item()\n",
    "    task = df.loc[df['File'] == answer_filename]['Task'].item()\n",
    "    s_text = df.loc[df['Task'] == task].loc[df['Class'] == -1]['Text'].item()\n",
    "    counts = CountVectorizer(analyzer='word', ngram_range=(n,n))\n",
    "    \n",
    "    # create array of n-gram counts for the answer and source text\n",
    "    ngrams = counts.fit_transform([a_text, s_text])\n",
    "\n",
    "    # row = the 2 texts and column = indexed vocab terms (as mapped above)\n",
    "    ngram_array = ngrams.toarray()\n",
    "    \n",
    "    \n",
    "    intersect=0\n",
    "    for col in range(np.shape(ngram_array)[1]):\n",
    "        if np.all(ngram_array[:,col]):\n",
    "            intersect += min(ngram_array[:,col])\n",
    "        \n",
    "    return intersect / sum(ngram_array[0])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test cells\n",
    "\n",
    "After you've implemented the containment function, you can test out its behavior. \n",
    "\n",
    "The cell below iterates through the first few files, and calculates the original category _and_ containment values for a specified n and file.\n",
    "\n",
    ">If you've implemented this correctly, you should see that the non-plagiarized have low or close to 0 containment values and that plagiarized examples have higher containment values, closer to 1.\n",
    "\n",
    "Note what happens when you change the value of n. I recommend applying your code to multiple files and comparing the resultant containment values. You should see that the highest containment values correspond to files with the highest category (`cut`) of plagiarism level."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original category values: \n",
      " [0, 3, 2, 1, 0]\n",
      "\n",
      "3-gram containment values: \n",
      " [0.009345794392523364, 0.9641025641025641, 0.6136363636363636, 0.15675675675675677, 0.031746031746031744]\n"
     ]
    }
   ],
   "source": [
    "# select a value for n\n",
    "n = 3\n",
    "\n",
    "# indices for first few files\n",
    "test_indices = range(5)\n",
    "\n",
    "# iterate through files and calculate containment\n",
    "category_vals = []\n",
    "containment_vals = []\n",
    "for i in test_indices:\n",
    "    # get level of plagiarism for a given file index\n",
    "    category_vals.append(complete_df.loc[i, 'Category'])\n",
    "    # calculate containment for given file and n\n",
    "    filename = complete_df.loc[i, 'File']\n",
    "    c = calculate_containment(complete_df, n, filename)\n",
    "    containment_vals.append(c)\n",
    "\n",
    "# print out result, does it make sense?\n",
    "print('Original category values: \\n', category_vals)\n",
    "print()\n",
    "print(str(n)+'-gram containment values: \\n', containment_vals)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed!\n"
     ]
    }
   ],
   "source": [
    "# run this test cell\n",
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "# test containment calculation\n",
    "# params: complete_df from before, and containment function\n",
    "tests.test_containment(complete_df, calculate_containment)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### QUESTION 1: Why can we calculate containment features across *all* data (training & test), prior to splitting the DataFrame for modeling? That is, what about the containment calculation means that the test and training data do not influence each other?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** In transformations like normalizing or scaling, it is important to fit the transformer only to the training data before applying it to the train and test sets. This is done to prevent data leakage. For this case, however, calculating containment does not require any knowledge aggregated across the student answers. It only requires the knowledge gained from comparing each answer text with its corresponding source text.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Longest Common Subsequence\n",
    "\n",
    "Containment a good way to find overlap in word usage between two documents; it may help identify cases of cut-and-paste as well as paraphrased levels of plagiarism. Since plagiarism is a fairly complex task with varying levels, it's often useful to include other measures of similarity. The paper also discusses a feature called **longest common subsequence**.\n",
    "\n",
    "> The longest common subsequence is the longest string of words (or letters) that are *the same* between the Wikipedia Source Text (S) and the Student Answer Text (A). This value is also normalized by dividing by the total number of words (or letters) in the  Student Answer Text. \n",
    "\n",
    "In this exercise, we'll ask you to calculate the longest common subsequence of words between two texts.\n",
    "\n",
    "### EXERCISE: Calculate the longest common subsequence\n",
    "\n",
    "Complete the function `lcs_norm_word`; this should calculate the *longest common subsequence* of words between a Student Answer Text and corresponding Wikipedia Source Text. \n",
    "\n",
    "It may be helpful to think of this in a concrete example. A Longest Common Subsequence (LCS) problem may look as follows:\n",
    "* Given two texts: text A (answer text) of length n, and string S (original source text) of length m. Our goal is to produce their longest common subsequence of words: the longest sequence of words that appear left-to-right in both texts (though the words don't have to be in continuous order).\n",
    "* Consider:\n",
    "    * A = \"i think pagerank is a link analysis algorithm used by google that uses a system of weights attached to each element of a hyperlinked set of documents\"\n",
    "    * S = \"pagerank is a link analysis algorithm used by the google internet search engine that assigns a numerical weighting to each element of a hyperlinked set of documents\"\n",
    "\n",
    "* In this case, we can see that the start of each sentence of fairly similar, having overlap in the sequence of words, \"pagerank is a link analysis algorithm used by\" before diverging slightly. Then we **continue moving left -to-right along both texts** until we see the next common sequence; in this case it is only one word, \"google\". Next we find \"that\" and \"a\" and finally the same ending \"to each element of a hyperlinked set of documents\".\n",
    "* Below, is a clear visual of how these sequences were found, sequentially, in each text.\n",
    "\n",
    "<img src='notebook_ims/common_subseq_words.png' width=40% />\n",
    "\n",
    "* Now, those words appear in left-to-right order in each document, sequentially, and even though there are some words in between, we count this as the longest common subsequence between the two texts. \n",
    "* If I count up each word that I found in common I get the value 20. **So, LCS has length 20**. \n",
    "* Next, to normalize this value, divide by the total length of the student answer; in this example that length is only 27. **So, the function `lcs_norm_word` should return the value `20/27` or about `0.7408`.**\n",
    "\n",
    "In this way, LCS is a great indicator of cut-and-paste plagiarism or if someone has referenced the same source text multiple times in an answer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LCS, dynamic programming\n",
    "\n",
    "If you read through the scenario above, you can see that this algorithm depends on looking at two texts and comparing them word by word. You can solve this problem in multiple ways. First, it may be useful to `.split()` each text into lists of comma separated words to compare. Then, you can iterate through each word in the texts and compare them, adding to your value for LCS as you go. \n",
    "\n",
    "The method I recommend for implementing an efficient LCS algorithm is: using a matrix and dynamic programming. **Dynamic programming** is all about breaking a larger problem into a smaller set of subproblems, and building up a complete result without having to repeat any subproblems. \n",
    "\n",
    "This approach assumes that you can split up a large LCS task into a combination of smaller LCS tasks. Let's look at a simple example that compares letters:\n",
    "\n",
    "* A = \"ABCD\"\n",
    "* S = \"BD\"\n",
    "\n",
    "We can see right away that the longest subsequence of _letters_ here is 2 (B and D are in sequence in both strings). And we can calculate this by looking at relationships between each letter in the two strings, A and S.\n",
    "\n",
    "Here, I have a matrix with the letters of A on top and the letters of S on the left side:\n",
    "\n",
    "<img src='notebook_ims/matrix_1.png' width=40% />\n",
    "\n",
    "This starts out as a matrix that has as many columns and rows as letters in the strings S and O **+1** additional row and column, filled with zeros on the top and left sides. So, in this case, instead of a 2x4 matrix it is a 3x5.\n",
    "\n",
    "Now, we can fill this matrix up by breaking it into smaller LCS problems. For example, let's first look at the shortest substrings: the starting letter of A and S. We'll first ask, what is the Longest Common Subsequence between these two letters \"A\" and \"B\"? \n",
    "\n",
    "**Here, the answer is zero and we fill in the corresponding grid cell with that value.**\n",
    "\n",
    "<img src='notebook_ims/matrix_2.png' width=30% />\n",
    "\n",
    "Then, we ask the next question, what is the LCS between \"AB\" and \"B\"?\n",
    "\n",
    "**Here, we have a match, and can fill in the appropriate value 1**.\n",
    "\n",
    "<img src='notebook_ims/matrix_3_match.png' width=25% />\n",
    "\n",
    "If we continue, we get to a final matrix that looks as follows, with a **2** in the bottom right corner.\n",
    "\n",
    "<img src='notebook_ims/matrix_6_complete.png' width=25% />\n",
    "\n",
    "The final LCS will be that value **2** *normalized* by the number of n-grams in A. So, our normalized value is 2/4 = **0.5**.\n",
    "\n",
    "### The matrix rules\n",
    "\n",
    "One thing to notice here is that, you can efficiently fill up this matrix one cell at a time. Each grid cell only depends on the values in the grid cells that are directly on top and to the left of it, or on the diagonal/top-left. The rules are as follows:\n",
    "* Start with a matrix that has one extra row and column of zeros.\n",
    "* As you traverse your string:\n",
    "    * If there is a match, fill that grid cell with the value to the top-left of that cell *plus* one. So, in our case, when we found a matching B-B, we added +1 to the value in the top-left of the matching cell, 0.\n",
    "    * If there is not a match, take the *maximum* value from either directly to the left or the top cell, and carry that value over to the non-match cell.\n",
    "\n",
    "<img src='notebook_ims/matrix_rules.png' width=50% />\n",
    "\n",
    "After completely filling the matrix, **the bottom-right cell will hold the non-normalized LCS value**.\n",
    "\n",
    "This matrix treatment can be applied to a set of words instead of letters. Your function should apply this to the words in two texts and return the normalized LCS value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Compute the normalized LCS given an answer text and a source text\n",
    "def lcs_norm_word(answer_text, source_text):\n",
    "    '''Computes the longest common subsequence of words in two texts; returns a normalized value.\n",
    "       :param answer_text: The pre-processed text for an answer text\n",
    "       :param source_text: The pre-processed text for an answer's associated source text\n",
    "       :return: A normalized LCS value'''\n",
    "    \n",
    "    # your code here\n",
    "    a = [0]+answer_text.split()\n",
    "    s = [0]+source_text.split()\n",
    "    matrix = np.zeros((len(s),len(a)), dtype=int)\n",
    "    for col in range(1,len(a)):\n",
    "        for row in range(1,len(s)):\n",
    "            if a[col] == s[row]:\n",
    "                matrix[row][col]=matrix[row-1][col-1]+1\n",
    "            else:\n",
    "                matrix[row,col]=max(matrix[row-1][col], matrix[row][col-1])\n",
    "    return matrix[len(s)-1][len(a)-1] / (len(a)-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test cells\n",
    "\n",
    "Let's start by testing out your code on the example given in the initial description.\n",
    "\n",
    "In the below cell, we have specified strings A (answer text) and S (original source text). We know that these texts have 20 words in common and the submitted answer is 27 words long, so the normalized, longest common subsequence should be 20/27.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "LCS =  0.7407407407407407\n",
      "Test passed!\n"
     ]
    }
   ],
   "source": [
    "# Run the test scenario from above\n",
    "# does your function return the expected value?\n",
    "\n",
    "A = \"i think pagerank is a link analysis algorithm used by google that uses a system of weights attached to each element of a hyperlinked set of documents\"\n",
    "S = \"pagerank is a link analysis algorithm used by the google internet search engine that assigns a numerical weighting to each element of a hyperlinked set of documents\"\n",
    "\n",
    "# calculate LCS\n",
    "lcs = lcs_norm_word(A, S)\n",
    "print('LCS = ', lcs)\n",
    "\n",
    "\n",
    "# expected value test\n",
    "assert lcs==20/27., \"Incorrect LCS value, expected about 0.7408, got \"+str(lcs)\n",
    "\n",
    "print('Test passed!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This next cell runs a more rigorous test."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed!\n"
     ]
    }
   ],
   "source": [
    "# run test cell\n",
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "# test lcs implementation\n",
    "# params: complete_df from before, and lcs_norm_word function\n",
    "tests.test_lcs(complete_df, lcs_norm_word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, take a look at a few resultant values for `lcs_norm_word`. Just like before, you should see that higher values correspond to higher levels of plagiarism."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original category values: \n",
      " [0, 3, 2, 1, 0]\n",
      "\n",
      "Normalized LCS values: \n",
      " [0.1917808219178082, 0.8207547169811321, 0.8464912280701754, 0.3160621761658031, 0.24257425742574257]\n"
     ]
    }
   ],
   "source": [
    "# test on your own\n",
    "test_indices = range(5) # look at first few files\n",
    "\n",
    "category_vals = []\n",
    "lcs_norm_vals = []\n",
    "# iterate through first few docs and calculate LCS\n",
    "for i in test_indices:\n",
    "    category_vals.append(complete_df.loc[i, 'Category'])\n",
    "    # get texts to compare\n",
    "    answer_text = complete_df.loc[i, 'Text'] \n",
    "    task = complete_df.loc[i, 'Task']\n",
    "    # we know that source texts have Class = -1\n",
    "    orig_rows = complete_df[(complete_df['Class'] == -1)]\n",
    "    orig_row = orig_rows[(orig_rows['Task'] == task)]\n",
    "    source_text = orig_row['Text'].values[0]\n",
    "    \n",
    "    # calculate lcs\n",
    "    lcs_val = lcs_norm_word(answer_text, source_text)\n",
    "    lcs_norm_vals.append(lcs_val)\n",
    "\n",
    "# print out result, does it make sense?\n",
    "print('Original category values: \\n', category_vals)\n",
    "print()\n",
    "print('Normalized LCS values: \\n', lcs_norm_vals)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "# Create All Features\n",
    "\n",
    "Now that you've completed the feature calculation functions, it's time to actually create multiple features and decide on which ones to use in your final model! In the below cells, you're provided two helper functions to help you create multiple features and store those in a DataFrame, `features_df`.\n",
    "\n",
    "### Creating multiple containment features\n",
    "\n",
    "Your completed `calculate_containment` function will be called in the next cell, which defines the helper function `create_containment_features`. \n",
    "\n",
    "> This function returns a list of containment features, calculated for a given `n` and for *all* files in a df (assumed to the the `complete_df`).\n",
    "\n",
    "For our original files, the containment value is set to a special value, -1.\n",
    "\n",
    "This function gives you the ability to easily create several containment features, of different n-gram lengths, for each of our text files."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "# Function returns a list of containment features, calculated for a given n \n",
    "# Should return a list of length 100 for all files in a complete_df\n",
    "def create_containment_features(df, n, column_name=None):\n",
    "    \n",
    "    containment_values = []\n",
    "    \n",
    "    if(column_name==None):\n",
    "        column_name = 'c_'+str(n) # c_1, c_2, .. c_n\n",
    "    \n",
    "    # iterates through dataframe rows\n",
    "    for i in df.index:\n",
    "        file = df.loc[i, 'File']\n",
    "        # Computes features using calculate_containment function\n",
    "        if df.loc[i,'Category'] > -1:\n",
    "            c = calculate_containment(df, n, file)\n",
    "            containment_values.append(c)\n",
    "        # Sets value to -1 for original tasks \n",
    "        else:\n",
    "            containment_values.append(-1)\n",
    "    \n",
    "    print(str(n)+'-gram containment features created!')\n",
    "    return containment_values\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Creating LCS features\n",
    "\n",
    "Below, your complete `lcs_norm_word` function is used to create a list of LCS features for all the answer files in a given DataFrame (again, this assumes you are passing in the `complete_df`. It assigns a special value for our original, source files, -1.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "# Function creates lcs feature and add it to the dataframe\n",
    "def create_lcs_features(df, column_name='lcs_word'):\n",
    "    \n",
    "    lcs_values = []\n",
    "    \n",
    "    # iterate through files in dataframe\n",
    "    for i in df.index:\n",
    "        # Computes LCS_norm words feature using function above for answer tasks\n",
    "        if df.loc[i,'Category'] > -1:\n",
    "            # get texts to compare\n",
    "            answer_text = df.loc[i, 'Text'] \n",
    "            task = df.loc[i, 'Task']\n",
    "            # we know that source texts have Class = -1\n",
    "            orig_rows = df[(df['Class'] == -1)]\n",
    "            orig_row = orig_rows[(orig_rows['Task'] == task)]\n",
    "            source_text = orig_row['Text'].values[0]\n",
    "\n",
    "            # calculate lcs\n",
    "            lcs = lcs_norm_word(answer_text, source_text)\n",
    "            lcs_values.append(lcs)\n",
    "        # Sets to -1 for original tasks \n",
    "        else:\n",
    "            lcs_values.append(-1)\n",
    "\n",
    "    print('LCS features created!')\n",
    "    return lcs_values\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## EXERCISE: Create a features DataFrame by selecting an `ngram_range`\n",
    "\n",
    "The paper suggests calculating the following features: containment *1-gram to 5-gram* and *longest common subsequence*. \n",
    "> In this exercise, you can choose to create even more features, for example from *1-gram to 7-gram* containment features and *longest common subsequence*. \n",
    "\n",
    "You'll want to create at least 6 features to choose from as you think about which to give to your final, classification model. Defining and comparing at least 6 different features allows you to discard any features that seem redundant, and choose to use the best features for your final model!\n",
    "\n",
    "In the below cell **define an n-gram range**; these will be the n's you use to create n-gram containment features. The rest of the feature creation code is provided."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1-gram containment features created!\n",
      "2-gram containment features created!\n",
      "3-gram containment features created!\n",
      "4-gram containment features created!\n",
      "5-gram containment features created!\n",
      "6-gram containment features created!\n",
      "LCS features created!\n",
      "\n",
      "Features:  ['c_1', 'c_2', 'c_3', 'c_4', 'c_5', 'c_6', 'lcs_word']\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Define an ngram range\n",
    "ngram_range = range(1,7)\n",
    "\n",
    "\n",
    "# The following code may take a minute to run, depending on your ngram_range\n",
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "features_list = []\n",
    "\n",
    "# Create features in a features_df\n",
    "all_features = np.zeros((len(ngram_range)+1, len(complete_df)))\n",
    "\n",
    "# Calculate features for containment for ngrams in range\n",
    "i=0\n",
    "for n in ngram_range:\n",
    "    column_name = 'c_'+str(n)\n",
    "    features_list.append(column_name)\n",
    "    # create containment features\n",
    "    all_features[i]=np.squeeze(create_containment_features(complete_df, n))\n",
    "    i+=1\n",
    "\n",
    "# Calculate features for LCS_Norm Words \n",
    "features_list.append('lcs_word')\n",
    "all_features[i]= np.squeeze(create_lcs_features(complete_df))\n",
    "\n",
    "# create a features dataframe\n",
    "features_df = pd.DataFrame(np.transpose(all_features), columns=features_list)\n",
    "\n",
    "# Print all features/columns\n",
    "print()\n",
    "print('Features: ', features_list)\n",
    "print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>c_1</th>\n",
       "      <th>c_2</th>\n",
       "      <th>c_3</th>\n",
       "      <th>c_4</th>\n",
       "      <th>c_5</th>\n",
       "      <th>c_6</th>\n",
       "      <th>lcs_word</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>0.398148</td>\n",
       "      <td>0.079070</td>\n",
       "      <td>0.009346</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.191781</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1.000000</td>\n",
       "      <td>0.984694</td>\n",
       "      <td>0.964103</td>\n",
       "      <td>0.943299</td>\n",
       "      <td>0.922280</td>\n",
       "      <td>0.901042</td>\n",
       "      <td>0.820755</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>0.869369</td>\n",
       "      <td>0.719457</td>\n",
       "      <td>0.613636</td>\n",
       "      <td>0.515982</td>\n",
       "      <td>0.449541</td>\n",
       "      <td>0.382488</td>\n",
       "      <td>0.846491</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>0.593583</td>\n",
       "      <td>0.268817</td>\n",
       "      <td>0.156757</td>\n",
       "      <td>0.108696</td>\n",
       "      <td>0.081967</td>\n",
       "      <td>0.060440</td>\n",
       "      <td>0.316062</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>0.544503</td>\n",
       "      <td>0.115789</td>\n",
       "      <td>0.031746</td>\n",
       "      <td>0.005319</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.242574</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>0.329502</td>\n",
       "      <td>0.053846</td>\n",
       "      <td>0.007722</td>\n",
       "      <td>0.003876</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.161172</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>0.590308</td>\n",
       "      <td>0.150442</td>\n",
       "      <td>0.035556</td>\n",
       "      <td>0.004464</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.000000</td>\n",
       "      <td>0.301653</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>0.765306</td>\n",
       "      <td>0.709898</td>\n",
       "      <td>0.664384</td>\n",
       "      <td>0.625430</td>\n",
       "      <td>0.589655</td>\n",
       "      <td>0.553633</td>\n",
       "      <td>0.621711</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>0.759777</td>\n",
       "      <td>0.505618</td>\n",
       "      <td>0.395480</td>\n",
       "      <td>0.306818</td>\n",
       "      <td>0.245714</td>\n",
       "      <td>0.195402</td>\n",
       "      <td>0.484305</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>0.884444</td>\n",
       "      <td>0.526786</td>\n",
       "      <td>0.340807</td>\n",
       "      <td>0.247748</td>\n",
       "      <td>0.180995</td>\n",
       "      <td>0.150000</td>\n",
       "      <td>0.597458</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "        c_1       c_2       c_3       c_4       c_5       c_6  lcs_word\n",
       "0  0.398148  0.079070  0.009346  0.000000  0.000000  0.000000  0.191781\n",
       "1  1.000000  0.984694  0.964103  0.943299  0.922280  0.901042  0.820755\n",
       "2  0.869369  0.719457  0.613636  0.515982  0.449541  0.382488  0.846491\n",
       "3  0.593583  0.268817  0.156757  0.108696  0.081967  0.060440  0.316062\n",
       "4  0.544503  0.115789  0.031746  0.005319  0.000000  0.000000  0.242574\n",
       "5  0.329502  0.053846  0.007722  0.003876  0.000000  0.000000  0.161172\n",
       "6  0.590308  0.150442  0.035556  0.004464  0.000000  0.000000  0.301653\n",
       "7  0.765306  0.709898  0.664384  0.625430  0.589655  0.553633  0.621711\n",
       "8  0.759777  0.505618  0.395480  0.306818  0.245714  0.195402  0.484305\n",
       "9  0.884444  0.526786  0.340807  0.247748  0.180995  0.150000  0.597458"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# print some results \n",
    "features_df.head(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Correlated Features\n",
    "\n",
    "You should use feature correlation across the *entire* dataset to determine which features are ***too*** **highly-correlated** with each other to include both features in a single model. For this analysis, you can use the *entire* dataset due to the small sample size we have. \n",
    "\n",
    "All of our features try to measure the similarity between two texts. Since our features are designed to measure similarity, it is expected that these features will be highly-correlated. Many classification models, for example a Naive Bayes classifier, rely on the assumption that features are *not* highly correlated; highly-correlated features may over-inflate the importance of a single feature. \n",
    "\n",
    "So, you'll want to choose your features based on which pairings have the lowest correlation. These correlation values range between 0 and 1; from low to high correlation, and are displayed in a [correlation matrix](https://www.displayr.com/what-is-a-correlation-matrix/), below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>c_1</th>\n",
       "      <th>c_2</th>\n",
       "      <th>c_3</th>\n",
       "      <th>c_4</th>\n",
       "      <th>c_5</th>\n",
       "      <th>c_6</th>\n",
       "      <th>lcs_word</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>c_1</th>\n",
       "      <td>1.00</td>\n",
       "      <td>0.94</td>\n",
       "      <td>0.90</td>\n",
       "      <td>0.89</td>\n",
       "      <td>0.88</td>\n",
       "      <td>0.87</td>\n",
       "      <td>0.97</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>c_2</th>\n",
       "      <td>0.94</td>\n",
       "      <td>1.00</td>\n",
       "      <td>0.99</td>\n",
       "      <td>0.98</td>\n",
       "      <td>0.97</td>\n",
       "      <td>0.96</td>\n",
       "      <td>0.98</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>c_3</th>\n",
       "      <td>0.90</td>\n",
       "      <td>0.99</td>\n",
       "      <td>1.00</td>\n",
       "      <td>1.00</td>\n",
       "      <td>0.99</td>\n",
       "      <td>0.98</td>\n",
       "      <td>0.97</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>c_4</th>\n",
       "      <td>0.89</td>\n",
       "      <td>0.98</td>\n",
       "      <td>1.00</td>\n",
       "      <td>1.00</td>\n",
       "      <td>1.00</td>\n",
       "      <td>0.99</td>\n",
       "      <td>0.95</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>c_5</th>\n",
       "      <td>0.88</td>\n",
       "      <td>0.97</td>\n",
       "      <td>0.99</td>\n",
       "      <td>1.00</td>\n",
       "      <td>1.00</td>\n",
       "      <td>1.00</td>\n",
       "      <td>0.95</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>c_6</th>\n",
       "      <td>0.87</td>\n",
       "      <td>0.96</td>\n",
       "      <td>0.98</td>\n",
       "      <td>0.99</td>\n",
       "      <td>1.00</td>\n",
       "      <td>1.00</td>\n",
       "      <td>0.94</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>lcs_word</th>\n",
       "      <td>0.97</td>\n",
       "      <td>0.98</td>\n",
       "      <td>0.97</td>\n",
       "      <td>0.95</td>\n",
       "      <td>0.95</td>\n",
       "      <td>0.94</td>\n",
       "      <td>1.00</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "           c_1   c_2   c_3   c_4   c_5   c_6  lcs_word\n",
       "c_1       1.00  0.94  0.90  0.89  0.88  0.87      0.97\n",
       "c_2       0.94  1.00  0.99  0.98  0.97  0.96      0.98\n",
       "c_3       0.90  0.99  1.00  1.00  0.99  0.98      0.97\n",
       "c_4       0.89  0.98  1.00  1.00  1.00  0.99      0.95\n",
       "c_5       0.88  0.97  0.99  1.00  1.00  1.00      0.95\n",
       "c_6       0.87  0.96  0.98  0.99  1.00  1.00      0.94\n",
       "lcs_word  0.97  0.98  0.97  0.95  0.95  0.94      1.00"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "# Create correlation matrix for just Features to determine different models to test\n",
    "corr_matrix = features_df.corr().abs().round(2)\n",
    "\n",
    "# display shows all of a dataframe\n",
    "display(corr_matrix)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## EXERCISE: Create selected train/test data\n",
    "\n",
    "Complete the `train_test_data` function below. This function should take in the following parameters:\n",
    "* `complete_df`: A DataFrame that contains all of our processed text data, file info, datatypes, and class labels\n",
    "* `features_df`: A DataFrame of all calculated features, such as containment for ngrams, n= 1-5, and lcs values for each text file listed in the `complete_df` (this was created in the above cells)\n",
    "* `selected_features`: A list of feature column names,  ex. `['c_1', 'lcs_word']`, which will be used to select the final features in creating train/test sets of data.\n",
    "\n",
    "It should return two tuples:\n",
    "* `(train_x, train_y)`, selected training features and their corresponding class labels (0/1)\n",
    "* `(test_x, test_y)`, selected training features and their corresponding class labels (0/1)\n",
    "\n",
    "** Note: x and y should be arrays of feature values and numerical class labels, respectively; not DataFrames.**\n",
    "\n",
    "Looking at the above correlation matrix, you should decide on a **cutoff** correlation value, less than 1.0, to determine which sets of features are *too* highly-correlated to be included in the final training and test data. If you cannot find features that are less correlated than some cutoff value, it is suggested that you increase the number of features (longer n-grams) to choose from or use *only one or two* features in your final model to avoid introducing highly-correlated features.\n",
    "\n",
    "Recall that the `complete_df` has a `Datatype` column that indicates whether data should be `train` or `test` data; this should help you split the data appropriately."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "ename": "AttributeError",
     "evalue": "'DataFrame' object has no attribute 'toarray'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAttributeError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-92-0a363b1368cd>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0mcomplete_df\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mloc\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mcomplete_df\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'Datatype'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m==\u001b[0m\u001b[0;34m'test'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtoarray\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m~/anaconda3/envs/amazonei_mxnet_p36/lib/python3.6/site-packages/pandas/core/generic.py\u001b[0m in \u001b[0;36m__getattr__\u001b[0;34m(self, name)\u001b[0m\n\u001b[1;32m   5272\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_info_axis\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_can_hold_identifiers_and_holds_name\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mname\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   5273\u001b[0m                 \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mname\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 5274\u001b[0;31m             \u001b[0;32mreturn\u001b[0m \u001b[0mobject\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__getattribute__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mname\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   5275\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   5276\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m__setattr__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mname\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0mstr\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m->\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mAttributeError\u001b[0m: 'DataFrame' object has no attribute 'toarray'"
     ]
    }
   ],
   "source": [
    "complete_df.loc[complete_df['Datatype']=='test'].values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Takes in dataframes and a list of selected features (column names) \n",
    "# and returns (train_x, train_y), (test_x, test_y)\n",
    "def train_test_data(complete_df, features_df, selected_features):\n",
    "    '''Gets selected training and test features from given dataframes, and \n",
    "       returns tuples for training and test features and their corresponding class labels.\n",
    "       :param complete_df: A dataframe with all of our processed text data, datatypes, and labels\n",
    "       :param features_df: A dataframe of all computed, similarity features\n",
    "       :param selected_features: An array of selected features that correspond to certain columns in `features_df`\n",
    "       :return: training and test features and labels: (train_x, train_y), (test_x, test_y)'''\n",
    "    \n",
    "    # get the training features\n",
    "    train_x = features_df.loc[complete_df['Datatype']=='train'][selected_features].values\n",
    "    # And training class labels (0 or 1)\n",
    "    train_y = complete_df.loc[complete_df['Datatype']=='train']['Class'].values\n",
    "    \n",
    "    # get the test features and labels\n",
    "    test_x = features_df.loc[complete_df['Datatype']=='test'][selected_features].values\n",
    "    test_y = complete_df.loc[complete_df['Datatype']=='test']['Class'].values\n",
    "    \n",
    "    return (train_x, train_y), (test_x, test_y)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test cells\n",
    "\n",
    "Below, test out your implementation and create the final train/test data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tests Passed!\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "test_selection = list(features_df)[:2] # first couple columns as a test\n",
    "# test that the correct train/test data is created\n",
    "(train_x, train_y), (test_x, test_y) = train_test_data(complete_df, features_df, test_selection)\n",
    "\n",
    "# params: generated train/test data\n",
    "tests.test_data_split(train_x, train_y, test_x, test_y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## EXERCISE: Select \"good\" features\n",
    "\n",
    "If you passed the test above, you can create your own train/test data, below. \n",
    "\n",
    "Define a list of features you'd like to include in your final mode, `selected_features`; this is a list of the features names you want to include."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Training size:  70\n",
      "Test size:  25\n",
      "\n",
      "Training df sample: \n",
      " [[0.39814815 0.         0.19178082]\n",
      " [0.86936937 0.38248848 0.84649123]\n",
      " [0.59358289 0.06043956 0.31606218]\n",
      " [0.54450262 0.         0.24257426]\n",
      " [0.32950192 0.         0.16117216]\n",
      " [0.59030837 0.         0.30165289]\n",
      " [0.75977654 0.1954023  0.48430493]\n",
      " [0.51612903 0.         0.27083333]\n",
      " [0.44086022 0.         0.22395833]\n",
      " [0.97945205 0.74468085 0.9       ]]\n"
     ]
    }
   ],
   "source": [
    "# Select your list of features, this should be column names from features_df\n",
    "# ex. ['c_1', 'lcs_word']\n",
    "selected_features = ['c_1', 'c_6', 'lcs_word']\n",
    "\n",
    "\n",
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "\n",
    "(train_x, train_y), (test_x, test_y) = train_test_data(complete_df, features_df, selected_features)\n",
    "\n",
    "# check that division of samples seems correct\n",
    "# these should add up to 95 (100 - 5 original files)\n",
    "print('Training size: ', len(train_x))\n",
    "print('Test size: ', len(test_x))\n",
    "print()\n",
    "print('Training df sample: \\n', train_x[:10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Question 2: How did you decide on which features to include in your final model? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Answer:** According to the correlation matrix, all of the features are pretty heavily correlated with one another. I just tried my best to pick the 3 that were least correlated with one another.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Creating Final Data Files\n",
    "\n",
    "Now, you are almost ready to move on to training a model in SageMaker!\n",
    "\n",
    "You'll want to access your train and test data in SageMaker and upload it to S3. In this project, SageMaker will expect the following format for your train/test data:\n",
    "* Training and test data should be saved in one `.csv` file each, ex `train.csv` and `test.csv`\n",
    "* These files should have class  labels in the first column and features in the rest of the columns\n",
    "\n",
    "This format follows the practice, outlined in the [SageMaker documentation](https://docs.aws.amazon.com/sagemaker/latest/dg/cdf-training.html), which reads: \"Amazon SageMaker requires that a CSV file doesn't have a header record and that the target variable [class label] is in the first column.\"\n",
    "\n",
    "## EXERCISE: Create csv files\n",
    "\n",
    "Define a function that takes in x (features) and y (labels) and saves them to one `.csv` file at the path `data_dir/filename`.\n",
    "\n",
    "It may be useful to use pandas to merge your features and labels into one DataFrame and then convert that into a csv file. You can make sure to get rid of any incomplete rows, in a DataFrame, by using `dropna`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_csv(x, y, filename, data_dir):\n",
    "    '''Merges features and labels and converts them into one csv file with labels in the first column.\n",
    "       :param x: Data features\n",
    "       :param y: Data labels\n",
    "       :param file_name: Name of csv file, ex. 'train.csv'\n",
    "       :param data_dir: The directory where files will be saved\n",
    "       '''\n",
    "    # make data dir, if it does not exist\n",
    "    if not os.path.exists(data_dir):\n",
    "        os.makedirs(data_dir)\n",
    "    \n",
    "    \n",
    "    # your code here\n",
    "    matrix = np.concatenate((np.array([y]).T,np.array(x)), axis = 1)\n",
    "    df = pd.DataFrame(matrix)\n",
    "    df.to_csv(data_dir+'/'+filename, index = False, header = False)\n",
    "    # nothing is returned, but a print statement indicates that the function has run\n",
    "    print('Path created: '+str(data_dir)+'/'+str(filename))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test cells\n",
    "\n",
    "Test that your code produces the correct format for a `.csv` file, given some text features and labels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path created: test_csv/to_delete.csv\n",
      "Tests passed!\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "fake_x = [ [0.39814815, 0.0001, 0.19178082], \n",
    "           [0.86936937, 0.44954128, 0.84649123], \n",
    "           [0.44086022, 0., 0.22395833] ]\n",
    "\n",
    "fake_y = [0, 1, 1]\n",
    "\n",
    "make_csv(fake_x, fake_y, filename='to_delete.csv', data_dir='test_csv')\n",
    "\n",
    "# read in and test dimensions\n",
    "fake_df = pd.read_csv('test_csv/to_delete.csv', header=None)\n",
    "\n",
    "# check shape\n",
    "assert fake_df.shape==(3, 4), \\\n",
    "      'The file should have as many rows as data_points and as many columns as features+1 (for indices).'\n",
    "# check that first column = labels\n",
    "assert np.all(fake_df.iloc[:,0].values==fake_y), 'First column is not equal to the labels, fake_y.'\n",
    "print('Tests passed!')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [],
   "source": [
    "# delete the test csv file, generated above\n",
    "! rm -rf test_csv"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you've passed the tests above, run the following cell to create `train.csv` and `test.csv` files in a directory that you specify! This will save the data in a local directory. Remember the name of this directory because you will reference it again when uploading this data to S3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path created: plagiarism_data/train.csv\n",
      "Path created: plagiarism_data/test.csv\n"
     ]
    }
   ],
   "source": [
    "# can change directory, if you want\n",
    "data_dir = 'plagiarism_data'\n",
    "\n",
    "\"\"\"\n",
    "DON'T MODIFY ANYTHING IN THIS CELL THAT IS BELOW THIS LINE\n",
    "\"\"\"\n",
    "\n",
    "make_csv(train_x, train_y, filename='train.csv', data_dir=data_dir)\n",
    "make_csv(test_x, test_y, filename='test.csv', data_dir=data_dir)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Up Next\n",
    "\n",
    "Now that you've done some feature engineering and created some training and test data, you are ready to train and deploy a plagiarism classification model. The next notebook will utilize SageMaker resources to train and test a model that you design."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "conda_amazonei_mxnet_p36",
   "language": "python",
   "name": "conda_amazonei_mxnet_p36"
  },
  "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.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}