asgn04.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "d0b4eb6157394135130c7d83e8e393ef",
     "grade": false,
     "grade_id": "cell-8e42a94857e3371d",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# Document Analysis Assignment 4: Node Label Prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Your Information\n",
    "Please fill in the following information:\n",
    "\n",
    "- **Name**:    [You Li]\n",
    "\n",
    "- **Uni id**:  [u6430173]\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "23eacc2bc1aea76c612fe4d4c282e680",
     "grade": false,
     "grade_id": "cell-4354c03bddb73da9",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## Overview\n",
    "The task in `Assignment 4` is to train a document classifier which predicts the label of documents, **while taking into account the network structure between documents**.\n",
    "\n",
    "You are given a dataset of 2708 textual documents (i.e. academic papers), as well as the citation relation between them.\n",
    "We can therefore organize the documents as a network in which each node represents a document, and the directed edge between node $u_i$ and node $u_j$ occurs when the paper $u_i$ cites $u_j$.\n",
    "Each document is labeled with one of the seven possible classes (i.e. publication venues), denoted as `1`, `2`, ..., `7`.\n",
    "\n",
    "You are provided with the textual content of the 2707 documents in the dataset (the abstracts of the papers), and the citation relations between documents.\n",
    "You are also provided with the labels of 2167 documents in the train set.\n",
    "Your task is to predict the labels of the 543 documents in the test set.\n",
    "You need to take into account both the textual content of documents, as well as the structure of their network.\n",
    "\n",
    "Searching for solutions for how to embed network structure is part of the assignment.\n",
    "We outline hereafter several possible solutions, ordered from easier to more difficult, and from lower achieved score to higher score.\n",
    "The easiest solution is outlined in more detail.\n",
    "\n",
    "### 1. Matrix factorization-based solution\n",
    "\n",
    "This solution is based on constructing an embedding of each document (node) in the network, based on the outputs of Singular Value Decomposition (SVD).\n",
    "In broad strokes, SVD decomposes a matrix $A$ of size $m \\times n$ into a product of three matrices $U$, $\\Sigma$ and $V$ so that $A = U \\Sigma V^*$, where:\n",
    "- $U$ is an $m \\times m$ unitary matrix ,\n",
    "- $\\Sigma$ is a diagonal $m \\times n$ matrix with non-negative real numbers on the diagonal,\n",
    "- $V$ is an $n \\times n$ unitary matrix, and $V^∗$ is the conjugate transpose of $V$.\n",
    "\n",
    "To solve the assignment using this method, you will need to follow the following steps:\n",
    "1. Read and preprocess the training and testing dataset in order to extract text feature (note the dataset structure here after);\n",
    "2. Construct the adjacency matrix $A$ representing the relations between documents in the network;\n",
    "3. Apply SVD on matrix $A$ to obtain matrices $U$, $\\Sigma$ and $V$;\n",
    "4. Construct network embeddings: use the rows of the matrix $U \\Sigma$ or the columns of $\\Sigma V$ as network features for each document;\n",
    "5. Obtain a document vectorial description by concatenating the network representation and the textual representation;\n",
    "6. Train and test classifier.\n",
    "\n",
    "**Notes:**\n",
    "1. this is a simplistic approach and unlikely to be competitive compared to the assignment's upper bound;\n",
    "2. for a more powerful algorithm based on SVD, consult the paper \"1. Matrix factorization\" in the papers folder;\n",
    "3. you can reuse code given in the tutorial or in your own solutions for the previous assignments, especially for treating the text of the documents.\n",
    "\n",
    "For more information on SVD please check this [MIT tutorial](http://web.mit.edu/be.400/www/SVD/Singular_Value_Decomposition.htm) and the [Wikipedia page for SVD](https://en.wikipedia.org/wiki/Singular-value_decomposition).\n",
    "\n",
    "### 2. Other solutions\n",
    "\n",
    "There are many other solutions to this problem, based on several paradigms, out of which we enumerate the following:\n",
    "- **Label propagation** uses a statistical machine learning to give a label probability for each vertex, then propagates part of the label probability to all of its neighbours. The propagation steps are repeated until all label probabilities converge. Check the paper \"2. Label propagation\" in the papers folder;\n",
    "- **node2vec** constructs for each node a multi-dimensional embedding by performing random walks starting with that node; it can learn continuous feature representations for the nodes, which can then be used for various downstream machine learning tasks. More details in the paper \"3. Node2vec embedding\" and on [the project's website](https://snap.stanford.edu/node2vec/);\n",
    "- **deep neural network** generate hidden representations from both attributes of vertices and representations of neighbouring vertices via recursive neural networks. This is the most difficult solution to implement, but has the potential of delivering the best results. More details in the paper \"4. Deep Neural Networks\".\n",
    "\n",
    "## Dataset and provided files\n",
    "\n",
    "#### links.txt: The structure of the network of documents\n",
    "Every line is in the format of \"`X` `Y`\", meaning that document `X` cites `Y`. `X` and `Y` are document ids.\n",
    "\n",
    "#### content.txt: The textual content of each document\n",
    "Every line is in the format \"`id` `f1` `f2` `f3` ...\", where `id` is the document id, and the rest of the line contains the tokens (words) of the document.\n",
    "A word appears only once in a document.\n",
    "You can apply any textual technique that you know to transform the text of each document in a vectorial format.\n",
    "\n",
    "#### label.train.csv: The labels of the training set.\n",
    "Each line provides the pair \"`id`, `label`\", where `id` is a document id, and the label is a value between 1 and 7 giving the class corresponding to the document.\n",
    "\n",
    "#### label.test.csv: Document ids to be predicted by you\n",
    "Each line contains a document id. For each document in the test set, you need to predict its class (a number from 1 to 7), based on its textual content and its network structure.\n",
    "\n",
    "### Evaluation\n",
    "\n",
    "The performance of your prediction will be evaluated automatically on Kaggle using the Categorization Accuracy (the percentage of correct predictions).\n",
    "\n",
    "Your score will be computed using a lower bound and an upper bound, which will be shown on the Kaggle leader board. \n",
    "Achieving a Categorization Accuracy score equal to the lower bound amount to a grade of zero, while achieving the upper bound amounts to the full points (here 7 points, see score distribution here below).\n",
    "Consequently, your score for this competition task will be calculated based on:\n",
    "\n",
    "$$\n",
    "    \\operatorname{Your\\_Score} = \\frac{Your\\_Performance - Lower\\_Bound}{Upper\\_Bound - Lower\\_Bound} * 7\n",
    "$$\n",
    "\n",
    "Notes about the lower bound and upper bounds predictors:\n",
    "\n",
    "* The **lower bound** was obtained by predicting document class using the textual features only (i.e. as in the ML assignment). Any successful embedding of network structure should earn you marks;\n",
    "* The **upper bound** was obtained using the deep learning approach presented here above.\n",
    "\n",
    "If you obtain a better performance than the upper bound, you will obtain a grade higher than 7 points for the coding part. This can be useful to compensate for any lost points for the written questions.\n",
    "Note however, that the total grade of this assignment is capped at 10 marks.\n",
    "\n",
    "## For the Kaggle competition\n",
    "\n",
    "- Join the competition [here](https://www.kaggle.com/t/04f0a26914c844ab946f50cdb96d6f1d);\n",
    "- Before submitting the result, first go to team menu and change your team name as your university id. **Note** that submissions not associated with a university id will not be taken into account;\n",
    "- You need to upload the generated result file to Kaggle. The result file should be in the following format:\n",
    "```\n",
    "id,label\n",
    "324123,1\n",
    "312312,2\n",
    "43431,3\n",
    "...\n",
    "```\n",
    "**Note**: there should NOT be any blank space after comma, otherwise the label will not be recognised by kaggle correctly (e.g. `324123,1` instead of `324123, 1` )\n",
    "- Note that you are only allowed to upload **20 copies** of your results to Kaggle per day. Make every upload count, and don't waste your opportunities!\n",
    "- You should use cross-validation instead of relying on the public set - this is what the daily limit is for!\n",
    "- For detailed submission instructions, check the end of this notebook.\n",
    "\n",
    "Score distribution (total 10 points):\n",
    "\n",
    "- Kaggle competition: 7 points\n",
    "- Written part Q1: 2 points\n",
    "- Written part Q2: 1 point\n",
    "\n",
    "After completion, please rename this notebook to **`your_uid.ipynb` (e.g. `u6000001.ipynb`)** and submit this file to Wattle. Do not upload any other files to Wattle except this notebook file.\n",
    "\n",
    "**Note:** you need to fill in the cell below with your code. Failure to provide your code nullifies your Kaggle grade (meaning you get zero for the coding part)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "def3328bc9db05261a0450a6022f15a8",
     "grade": false,
     "grade_id": "cell-a46ba2805e2b46f6",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## 1. Code for solving the assignment\n",
    "\n",
    "Please paste here below the code which is the solution to your assignment, including any package imports.\n",
    "Note that, upon request, you may be required to show (on your own machine) that the code included in the submitted notebook actually generates the results submitted to Kaggle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "440a0dc19d1b1eb1b5402a9120126bee",
     "grade": true,
     "grade_id": "cell-d8b7796e3cd82200",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "outputs": [],
   "source": [
    "from io import open\n",
    "import numpy as np\n",
    "\n",
    "from sklearn.feature_extraction.text import CountVectorizer\n",
    "from sklearn import datasets, linear_model, decomposition, svm, neighbors\n",
    "from sklearn.metrics import mean_squared_error, r2_score\n",
    "from sklearn.feature_extraction.text import TfidfTransformer\n",
    "from sklearn.pipeline import Pipeline\n",
    "import math\n",
    "from sklearn.preprocessing import LabelEncoder\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.neighbors import * \n",
    "from sklearn.neural_network import MLPClassifier\n",
    "from sklearn.ensemble import *\n",
    "from sklearn.feature_selection import *\n",
    "from sklearn.gaussian_process import *\n",
    "from sklearn.naive_bayes import *\n",
    "from sklearn.tree import *\n",
    "from sklearn.linear_model import *\n",
    "# Setp1\n",
    "# Read and preprocess the training and testing dataset in order to extract text feature (note the dataset structure here after);\n",
    "\n",
    "fp = open(\"./ass4data/label.train.csv\", 'r')\n",
    "train_text = fp.read()\n",
    "fp.close()\n",
    "\n",
    "fp = open(\"./ass4data/label.test.csv\", 'r')\n",
    "test_text = fp.read()\n",
    "fp.close()\n",
    "\n",
    "train_doc_id = []\n",
    "train_doc_label = []\n",
    "test_doc_id = []\n",
    "for line in train_text.split(\"\\n\"):\t\n",
    "\ttemp = line.split(\",\")\n",
    "\tif (temp[0] != ''):\t\n",
    "\t\tif (temp[0]!= \"id\"):\n",
    "\t\t\ttrain_doc_id.append(int(temp[0]))\n",
    "\t\tif (temp[1]!= \"label\"):\n",
    "\t\t\ttrain_doc_label.append(int(temp[1]))\n",
    "\n",
    "for line in test_text.split(\"\\n\"):\t\n",
    "\ttemp = line.split(\",\")\n",
    "\tif (temp[0] != ''):\t\n",
    "\t\tif (temp[0]!= \"id\"):\n",
    "\t\t\ttest_doc_id.append(int(temp[0]))\n",
    "\n",
    "print (np.shape(train_doc_id))\n",
    "print (np.shape(train_doc_label))\n",
    "print (np.shape(test_doc_id))\n",
    "# Step2\n",
    "# Construct the adjacency matrix A representing the relations between documents in the network;\n",
    "\n",
    "links = np.loadtxt('./ass4data/links.txt')\n",
    "\n",
    "\n",
    "# Step 3: \n",
    "# Construct network embeddings using node2vec: \n",
    "\n",
    "links_matrix1 = np.loadtxt('./ass4data/links_matrix1.txt')\n",
    "links_matrix2 = np.loadtxt('./ass4data/links_matrix2.txt')\n",
    "links_matrix3 = np.loadtxt('./ass4data/links_matrix3.txt')\n",
    "links_matrix4 = np.loadtxt('./ass4data/links_matrix4.txt')\n",
    "links_matrix5 = np.loadtxt('./ass4data/links_matrix5.txt')\n",
    "links_matrix6 = np.loadtxt('./ass4data/links_matrix6.txt')\n",
    "links_matrix7 = np.loadtxt('./ass4data/links_matrix7.txt')\n",
    "links_matrix8 = np.loadtxt('./ass4data/links_matrix8.txt')\n",
    "links_matrix9 = np.loadtxt('./ass4data/links_matrix9.txt')\n",
    "links_matrix10 = np.loadtxt('./ass4data/links_matrix10.txt')\n",
    "\n",
    "links_matrix = links_matrix2\n",
    "docIndex = []\n",
    "matrix_n2v = np.zeros([2708, 128])\n",
    "for line in links_matrix:\n",
    "    docIndex.append(line[0])\n",
    "    for i in range(1,len(line)):\n",
    "        matrix_n2v[docIndex.index(line[0]), i-1] = line[i]\n",
    "\n",
    "\n",
    "# Setp 5:\n",
    "# Obtain a document vectorial description by concatenating the network representation and the textual representation;\n",
    "\n",
    "fp = open(\"./ass4data/content.txt\", 'r')\n",
    "content_text = fp.readlines()\n",
    "fp.close()\n",
    "\n",
    "word = []\t\n",
    "for line in content_text:\n",
    "\tline = line.strip()\n",
    "\tline = line.split(\" w\")\n",
    "\tfor i in range (1, len (line)):\n",
    "  \t\tif int(line[i]) not in word:  word.append(int(line[i]))\n",
    "word.sort()\n",
    "\n",
    "content_matrix = np.zeros([2708, len(word)])\n",
    "for line in content_text:\n",
    "\tline = line.strip()\n",
    "\tline = line.split(' w')\n",
    "\tfor i in range (1, len(line)):\n",
    "\t\tcontent_matrix[docIndex.index(int(line[0])), word.index (int(line[i]))]= 1\n",
    "\n",
    "feature_matrix = np.hstack((matrix_n2v, content_matrix))\n",
    "\n",
    "feature_train = []\n",
    "feature_pred = []\n",
    "train_label = []\n",
    "pred_label = []\n",
    "\n",
    "searchIndex_train = []\n",
    "searchIndex_test = []\n",
    "\n",
    "for id in train_doc_id:\n",
    "\tfor node in links_matrix: \n",
    "\t\tif id == node[0]:\n",
    "\t\t\tsearchIndex_train.append(node[1])\n",
    "\n",
    "for search_index in searchIndex_train:\n",
    "\tfor feature in feature_matrix:\n",
    "\t\tif search_index == feature[0]:\n",
    "\t\t\tfeature_train.append(feature)\n",
    "\n",
    "# rearrange the predict features with test id\n",
    "for id in test_doc_id:\n",
    "\tfor node in links_matrix: \n",
    "\t\tif id == node[0]:\n",
    "\t\t\tsearchIndex_test.append(node[1])\n",
    "\n",
    "for search_index in searchIndex_test:\n",
    "\tfor feature in feature_matrix:\n",
    "\t\tif search_index == feature[0]:\n",
    "\t\t\tfeature_pred.append(feature)\n",
    "\n",
    "train_X = feature_train\n",
    "train_Y = train_doc_label\n",
    "pred_X = feature_pred\n",
    "\n",
    "\n",
    "\n",
    "mlp = GradientBoostingClassifier(\n",
    "\t# loss = 'exponential', \n",
    "\tlearning_rate = 0.001,\n",
    "\tn_estimators = 700,\n",
    "    max_leaf_nodes = 7\n",
    "\t)\n",
    "mlp.fit(train_X, train_Y)\n",
    "\n",
    "pred_Y = mlp.predict(pred_X)   \n",
    "\n",
    "\n",
    "def write_output(output_file):\n",
    "    with open(output_file, 'w') as output:\n",
    "        output.write(u'id,label\\n')  \n",
    "        for i in range(0, len(pred_Y)):\n",
    "            index = test_doc_id[i]\n",
    "            label = pred_Y[i]\n",
    "            output.write(u'{},{}\\n'.format(index,label))\n",
    "           \n",
    "output_file = 'output.csv'\n",
    "write_output(output_file)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "ec82645eb3cf65f5cb213e4b975c9879",
     "grade": false,
     "grade_id": "cell-5675e41756e1913b",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "## 2. Written part\n",
    "\n",
    "Answer briefly and concisely the following questions, based on your implementation.\n",
    "Provide answers using bullet list with 2~3 items.\n",
    "Check [this](https://sourceforge.net/p/jupiter/wiki/markdown_syntax/#md_ex_lists) if you are not familiar with markdown syntax."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "7c0fba64b74f091aa9c42e2732a981a8",
     "grade": false,
     "grade_id": "cell-600fab2c95932362",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 1 (2pts)\n",
    " \n",
    "How do you use the network structure in your classification? (1 mark) Why does your method work on this task? (1 mark)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "9812c1e1601975b42c065d06aa143663",
     "grade": true,
     "grade_id": "cell-5796bfbe4fb99745",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "* Using node2vec to train the link.txt an embedding feature\n",
    "* The performance on seperatting links as SVD matrix is low performance up to 0.7. Then transfer the networks structure which represent the citation relations with $u_i$ to $u_j$ using nodes to vectors would be a proproate solution for representing the node structure. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "2ade4fd8de14cba788e638ea6c34c72b",
     "grade": false,
     "grade_id": "cell-1990ba6d5b6c9edd",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "### Question 2 (1pt)\n",
    "\n",
    "How do you incorporate text features?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "nbgrader": {
     "checksum": "503bc062d547dbe71518a43a8bc4d331",
     "grade": true,
     "grade_id": "cell-b00b94e1856fc087",
     "locked": false,
     "points": 0,
     "schema_version": 1,
     "solution": true
    }
   },
   "source": [
    "* The text features were read as a matrix which represents the occurence with 0 and 1.\n",
    "\n",
    "* Then this matrix was appended with the links features matrix using np.hstack().\n",
    "\n",
    "* The combined text features were used as train_X for classification, where train_Y is the label.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": false,
    "editable": false,
    "nbgrader": {
     "checksum": "acd6d5e94bc59e8796b3a36d53e4d829",
     "grade": false,
     "grade_id": "cell-c2ebd75ee43d1be0",
     "locked": true,
     "schema_version": 1,
     "solution": false
    }
   },
   "source": [
    "# Upload output file to Kaggle competition site\n",
    "\n",
    "Once you generate `output.csv` file, you can upload your result on Kaggle competition site. To upload and evaluate your result\n",
    "\n",
    "1. Go to Kaggle competition site: [Click here](https://www.kaggle.com/t/04f0a26914c844ab946f50cdb96d6f1d).\n",
    "1. Sign up for Kaggle if you do not have an account. Go back to the [original kaggle page](https://www.kaggle.com/t/04f0a26914c844ab946f50cdb96d6f1d).\n",
    "1. Before submitting the result, first go to `team` menu and change **your team name as your university id**.\n",
    "![ChangeUID](images/changeuid.png)\n",
    "1. Time to submit your own result. Click `submit predictions` in the menu, you may need to agree the competition rules before submitting your result.\n",
    "1. Upload your output csv file, you can write additional description of your submission in the description box.\n",
    "    Note that you are only allowed to submit **3 results per day**. Do not upload an arbitrary result and think which algorithm or parser will perform the best.\n",
    "1. If your output format is correct, the system will generate your score automatically.\n",
    "1. Go to `Leaderboard` menu. The leaderboard will show the current score of the other students.\n",
    "![Leaderboard](images/leaderboard.png)\n",
    "\n",
    "\n",
    "Note that you can check all of your submission from `my submission` menu. Please select one best performing submission before the assignment due. The selected submission will be used to measure the performance of *hidden* test case (see below for details).\n",
    "![Check](images/check.png)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}