COMP30027ASS1_detailed-6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The University of Melbourne, School of Computing and Information Systems\n",
    "# COMP30027 Machine Learning, 2022 Semester 1\n",
    "\n",
    "## Assignment 1: Naive Bayes Leaner for Adult Database\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Student Name(s):** `Truong Giang Hoang`\n",
    "<br>\n",
    "**Student ID(s):** `1166323`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "Marking will be applied on the four functions that are defined in this notebook, and to your responses to the questions at the end of this notebook.\n",
    "\n",
    "## General info\n",
    "\n",
    "<b>Due date</b>: Friday, 8 April 2022 7pm\n",
    "\n",
    "<b>Submission method</b>: Canvas submission\n",
    "\n",
    "<b>Submission materials</b>: This iPython notebook is a template which you will use for your Assignment 1 submission. You need to only submitted the completed copy of this iPython notebook.\n",
    "\n",
    "<b>Late submissions</b>: -10% per day up to 5 days (both weekdays and weekends count). Submissions more than 5 days late will not be accepted (resul in a mark of 0).\n",
    "<ul>\n",
    "    <li>one day late, -1.0;</li>\n",
    "    <li>two days late, -2.0;</li>\n",
    "    <li>three days late, -3.0;</li>\n",
    "    <li>four days late, -4.0;</li>\n",
    "    <li>five days late, -5.0;</li>\n",
    "</ul>\n",
    "\n",
    "<b>Extensions</b>: Students who are demonstrably unable to submit a full solution in time due to medical reasons or other trauma, may apply for an extension.  In these cases, you should email <a href=\"mailto:ni.ding@unimelb.edu.au\">Ni Ding</a> as soon as possible after those circumstances arise. If you attend a GP or other health care service as a result of illness, be sure to provide a Health Professional Report (HPR) form (get it from the Special Consideration section of the Student Portal), you will need this form to be filled out if your illness develops into something that later requires a Special Consideration application to be lodged. You should scan the HPR form and send it with the extension requests.\n",
    "\n",
    "<b>Marks</b>: This assignment will be marked out of 20, and make up 20% of your overall mark for this subject.\n",
    "\n",
    "<b>Materials</b>: Use Jupyter Notebook and Python page on Canvas for information on the basic setup required for this class, including an iPython notebook viewer and the python packages NLTK, Numpy, Scipy, Matplotlib, Scikit-Learn. You can use any Python built-in packages, but do not use any other 3rd party packages; if your iPython notebook doesn't run on the marker's machine, you will lose marks. <b> You should use Python 3</b>.  \n",
    "\n",
    "\n",
    "<b>Evaluation</b>: Your iPython notebook should run end-to-end without any errors in a reasonable amount of time, and you must follow all instructions provided below, including specific implementation requirements and instructions for what needs to be printed (please avoid printing output we don't ask for). You should edit the sections below where requested, but leave the rest of the code as is. You should leave the output from running your code in the iPython notebook you submit, to assist with marking. The amount each section is worth is given in parenthesis after the instructions. \n",
    "\n",
    "You will be marked not only on the correctness of your methods, but also the quality and efficency of your code: in particular, you should be careful to use Python built-in functions and operators when appropriate and pick descriptive variable names that adhere to <a href=\"https://www.python.org/dev/peps/pep-0008/\">Python style requirements</a>. If you think it might be unclear what you are doing, you should comment your code to help the marker make sense of it. We reserve the right to deduct up to 2 marks for unreadable or exessively inefficient code.\n",
    "\n",
    "8 of the marks available for this Project will be assigned to whether the four specified Python functions work in a manner consistent with the materials from COMP30027. Any other implementation will not be directly assessed (except insofar as it is required to make these five functions work correctly).\n",
    "\n",
    "12 of the marks will be assigned to your responses to the questions, in terms of both accuracy and insightfulness. We will be looking for evidence that you have an implementation that allows you to explore the problem, but also that you have thought deeply about the data and the behaviour of the Naive Bayes classifier.\n",
    "\n",
    "<b>Updates</b>: Any major changes to the assignment will be announced via Canvas. Minor changes and clarifications will be announced on the discussion board (ED -> Assignments -> A1); we recommend you check it regularly.\n",
    "\n",
    "<b>Academic misconduct</b>: For most people, collaboration will form a natural part of the undertaking of this homework, and we encourge you to discuss it in general terms with other students. However, this ultimately is still an individual task, and so reuse of code or other instances of clear influence will be considered cheating. Please check the <a href=\"https://canvas.lms.unimelb.edu.au/courses/124196/modules#module_662096\">CIS Academic Honesty training</a> for more information. We will be checking submissions for originality and will invoke the University’s <a href=\"http://academichonesty.unimelb.edu.au/policy.html\">Academic Misconduct policy</a> where inappropriate levels of collusion or plagiarism are deemed to have taken place.\n",
    "\n",
    "**IMPORTANT**\n",
    "\n",
    "Please carefully read and fill out the <b>Authorship Declaration</b> form at the bottom of the page. Failure to fill out this form results in the following deductions: \n",
    "<UL TYPE=”square”>\n",
    "<LI>missing Authorship Declaration at the bottom of the page, -5.0\n",
    "<LI>incomplete or unsigned Authorship Declaration at the bottom of the page, -3.0\n",
    "</UL>\n",
    "**NOTE: COMPLETE AND SUBMIT THIS FILE. YOU SHOULD IMPLEMENT FOUR FUNCTIONS AND INCLUDE YOUR ANSWERS TO THE QUESTIONS IN THIS FILE ONLY. NO OTHER SUBMISSION IS REQUIRED.**\n",
    "\n",
    "**Keep your code clean. Adding proper comments to your code is MANDATORY.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1: Base code [8 marks]\n",
    "\n",
    "Instructions\n",
    "1. Do **not** shuffle the data set\n",
    "2. Treat the attributes as they are(e.g., do **not** convert numeric attributes to categorical or categorical to numeric). Implement a Naive Bayes classifier with appropriate likelihood function for each attribute.\n",
    "3. You should implement the Naive Bayes classifier from scratch. Do **not** use existing implementations/learning algorithms.\n",
    "4. You CANNOT have more than one train or predict function. Both continuous numeric attributes and categorical ones should be trained in one `train()` function, similarly for the `predict()`.  \n",
    "5. Apart from the instructions in point 3, you may use libraries to help you with data reading, representation, maths or evaluation\n",
    "6. Ensure that all and only required information is printed, as indicated in the final three code cells. Failure to adhere to print the required information will result in **[-1 mark]** per case. *(We don't mind details like you print a list or several numbers -- just make sure the information is displayed so that it's easily accessible)\n",
    "7. You may change the prototypes of these functions, and you may write other functions, according to your requirements. We would appreciate it if the required functions were prominent/easy to find. \n",
    "8. You should add adequate comments to make your code easily comprehendible.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "from collections import defaultdict\n",
    "import re\n",
    "from math import sqrt\n",
    "from math import pi\n",
    "from math import exp\n",
    "from math import log\n",
    "import sklearn.naive_bayes as nb\n",
    "from sklearn.naive_bayes import GaussianNB, MultinomialNB, BernoulliNB\n",
    "from sklearn.model_selection import train_test_split\n",
    "from collections import defaultdict as dd\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This function should prepare the data by reading it from a file and converting it into a useful format for training and testing\n",
    "# and implement 90-10 splitting as specified in the project description.\n",
    "def preprocess(filename):\n",
    "    X = []\n",
    "    y = []\n",
    "    data = []\n",
    "    num_instances = 0\n",
    "    with open(filename, 'r') as f:\n",
    "        attribute = f.readline().strip().split(\",\")\n",
    "        for line in f.readlines():\n",
    "            num_instances += 1\n",
    "            line = line.strip().split(\",\")\n",
    "            line[0] = float(line[0]) #age\n",
    "            line[3] = float(line[3]) #education num\n",
    "            line[-3] = float(line[-3]) #hours per week\n",
    "            X.append(line[:-1])\n",
    "            y.append(line[-1])\n",
    "    num_lbl = len(set(y))\n",
    "\n",
    "    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.10, shuffle = False)\n",
    "    \n",
    "    return X_train, X_test, y_train, y_test, num_instances, attribute, num_lbl\n",
    "X_train, X_test, y_train, y_test, num_instances, attribute, num_lbl = preprocess(\"dataset/adult.csv\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#find which row corresponds to which class label, return 2 lists\n",
    "def row_of_each_class(y_train):\n",
    "    at_most_50K = []\n",
    "    more_than_50K = []\n",
    "    for i in range(len(y_train)):\n",
    "        if y_train[i] == \" <=50K\":\n",
    "            at_most_50K.append(i)\n",
    "        else: \n",
    "            more_than_50K.append(i)\n",
    "    return at_most_50K, more_than_50K"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#implementation of Gaussian Naive Bayes\n",
    "def probability(x, mean, std):\n",
    "    exponent = exp(-((x-mean)**2 / (2 * std**2 )))\n",
    "    return (1 / (sqrt(2 * pi) * std)) * exponent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#calculate prior probability\n",
    "def prior(y_train):\n",
    "    # this is probability of class\n",
    "    list1, list2 = row_of_each_class(y_train)\n",
    "    return len(list1)/len(y_train), len(list2)/len(y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#find which attribute is numeric or nominal\n",
    "def attribute_is_numeric(X_train):\n",
    "    attribute_is_numeric = [] #numeric or nominal, \n",
    "    for i in range (len(X_train[0])):\n",
    "        if isinstance(X_train[0][i], float):\n",
    "            attribute_is_numeric.append(1)\n",
    "        else:\n",
    "            attribute_is_numeric.append(0)\n",
    "    return attribute_is_numeric"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This function should calculate prior probabilities and likelihoods (conditional probabilities) from the training data and using\n",
    "# to build a naive Bayes model\n",
    "\n",
    "def train(X_train, y_train, attribute):\n",
    "    prior_less, prior_more = prior(y_train)\n",
    "    list1, list2 = row_of_each_class(y_train)\n",
    "    is_numeric = attribute_is_numeric(X_train) #numeric or nominal, \n",
    "    att_len = len(is_numeric)\n",
    "    data_len = len(X_train)\n",
    "    label_dict = defaultdict(dict)\n",
    "    at_most_50K_dict = defaultdict(dict)\n",
    "    more_than_50K_dict = defaultdict(dict)\n",
    "    for i in range(att_len):\n",
    "        at_most_50K_dict[attribute[i]] = defaultdict(float)\n",
    "        more_than_50K_dict[attribute[i]] = defaultdict(float)\n",
    "    for i in range(att_len):\n",
    "        if not is_numeric[i]:\n",
    "            for j in range(data_len):\n",
    "                at_most_50K_dict[attribute[i]][X_train[j][i]] = 0\n",
    "                more_than_50K_dict[attribute[i]][X_train[j][i]] = 0\n",
    "            for j in range(data_len):\n",
    "                if y_train[j] == \" <=50K\":\n",
    "                    at_most_50K_dict[attribute[i]][X_train[j][i]] += 1.0\n",
    "                    #print(X_train[j][i])\n",
    "                else:\n",
    "                    more_than_50K_dict[attribute[i]][X_train[j][i]] += 1.0\n",
    "                    #print(X_train[j][i])\n",
    "            # apply Laplace smoothing\n",
    "            at_most_50K_dict[attribute[i]] = {k: v+1 for (k,v) in at_most_50K_dict[attribute[i]].items()}\n",
    "            more_than_50K_dict[attribute[i]] = {k: v+1 for (k,v) in more_than_50K_dict[attribute[i]].items()}\n",
    "            \n",
    "            sum1 = sum([x for x in at_most_50K_dict[attribute[i]].values()])\n",
    "            sum2 = sum([x for x in more_than_50K_dict[attribute[i]].values()])\n",
    "            at_most_50K_dict[attribute[i]] = {k: v/sum1 for (k,v) in at_most_50K_dict[attribute[i]].items()}\n",
    "            more_than_50K_dict[attribute[i]] = {k: v/sum2 for (k,v) in more_than_50K_dict[attribute[i]].items()}\n",
    "        else:\n",
    "            at_most_50K_values = []\n",
    "            more_than_50K_values = []\n",
    "            for j in list1:\n",
    "                at_most_50K_values.append(X_train[j][i])\n",
    "            for g in list2:\n",
    "                more_than_50K_values.append(X_train[g][i])\n",
    "            at_most_50K_dict[attribute[i]]['mean'] = np.mean(at_most_50K_values)\n",
    "            at_most_50K_dict[attribute[i]]['std'] = np.std(at_most_50K_values)\n",
    "            at_most_50K_dict[attribute[i]]['values'] = at_most_50K_values\n",
    "            more_than_50K_dict[attribute[i]]['mean'] = np.mean(more_than_50K_values)\n",
    "            more_than_50K_dict[attribute[i]]['std'] = np.std(more_than_50K_values)\n",
    "            more_than_50K_dict[attribute[i]]['values'] = more_than_50K_values\n",
    "                \n",
    "                \n",
    "    label_dict[\" <=50K\"] = at_most_50K_dict\n",
    "    label_dict[\" >50K\"] = more_than_50K_dict\n",
    "    return label_dict, prior_less, prior_more"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This function should predict classes for new items in the testing data\n",
    "def predict(trained_data, test_data, att, att_is_numeric):\n",
    "    less_dict = trained_data[0][\" <=50K\"]\n",
    "    more_dict = trained_data[0][\" >50K\"]\n",
    "    prior_1, prior_2 = trained_data[1], trained_data[2]\n",
    "    less_than_50K_prob = log(prior_1)\n",
    "    more_than_50K_prob = log(prior_2)\n",
    "    for i in range(len(att_is_numeric)):\n",
    "        if not att_is_numeric[i]:\n",
    "            less_than_50K_prob += log(less_dict[att[i]][test_data[i]])\n",
    "            more_than_50K_prob += log(more_dict[att[i]][test_data[i]])\n",
    "        else:\n",
    "            if test_data[i] == \" ?\":\n",
    "                less_than_50K_prob += log(probability(less_dict[att[i]]['mean'], less_dict[att[i]]['mean'], less_dict[att[i]]['std']))\n",
    "                more_than_50K_prob += log(probability(more_dict[att[i]]['mean'], more_dict[att[i]]['mean'], more_dict[att[i]]['std']))\n",
    "            else:\n",
    "                less_than_50K_prob += log(probability(test_data[i], less_dict[att[i]]['mean'], less_dict[att[i]]['std']))\n",
    "                more_than_50K_prob += log(probability(test_data[i], more_dict[att[i]]['mean'], more_dict[att[i]]['std']))\n",
    "    prob = less_than_50K_prob if less_than_50K_prob > more_than_50K_prob else more_than_50K_prob\n",
    "    return prob, \" <=50K\" if less_than_50K_prob > more_than_50K_prob else \" >50K\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This function should evaliate the prediction performance by comparing your model’s class outputs to ground\n",
    "# truth labels, return and output accuracy, confusion matrix and F1 score.\n",
    "\n",
    "def evaluate(y_test, result):\n",
    "    positive = \" <=50K\"\n",
    "    negative = \" >50K\"\n",
    "    true_positive = 0\n",
    "    true_negative = 0\n",
    "    false_positive = 0\n",
    "    false_negative = 0\n",
    "    for i in range(len(y_test)):\n",
    "        if result[i] == positive and y_test[i] == positive:\n",
    "            true_positive += 1\n",
    "        elif result[i] == positive and y_test[i] == negative:\n",
    "            false_positive += 1\n",
    "        elif result[i] == negative and y_test[i] == negative:\n",
    "            true_negative += 1\n",
    "        else:\n",
    "            false_negative += 1\n",
    "    #print(true_positive, false_positive, true_negative, false_negative)\n",
    "    precision = true_positive / (true_positive + false_positive)\n",
    "    recall = true_positive / (true_positive + false_negative)\n",
    "    F1 = 2 * precision * recall / (precision + recall)\n",
    "    accuracy = (true_positive + true_negative) / (true_positive + true_negative + false_positive + false_negative)\n",
    "    specificity = true_negative / (true_negative + false_positive)\n",
    "    actual = pd.Series(y_test, name='Actual')\n",
    "    predicted = pd.Series(result, name='Predicted')\n",
    "    confusion_matrix = pd.crosstab(actual, predicted)\n",
    "    \n",
    "    return confusion_matrix, precision, recall, F1, accuracy, specificity\n",
    "\n",
    "\n",
    "# X_train, X_test, y_train, y_test, num_instances, attribute, num_lbl = preprocess(\"dataset/adult.csv\")\n",
    "# trained = train(X_train, y_train, attribute)\n",
    "# trained\n",
    "# result = []\n",
    "# for test in X_test:\n",
    "#     result.append(predict(trained, test, attribute, attribute_is_numeric(X_train))[1])\n",
    "# print(evaluate(y_test, result)[0])\n",
    "# print(evaluate(y_test, result)[1])\n",
    "# print(evaluate(y_test, result)[2])\n",
    "# print(evaluate(y_test, result)[3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Confusion matrix:\n",
      " Predicted   <=50K   >50K\n",
      "Actual                  \n",
      " <=50K         69      8\n",
      " >50K           6     17\n",
      "Precision:  0.92\n",
      "Recall:  0.8961038961038961\n",
      "F1 score:  0.9078947368421053\n",
      "Accuracy:  0.86\n",
      "Attribute vectors of instances [0, 1, 2]:  [68.0, ' ?', ' 1st-4th', 2.0, ' Divorced', ' ?', ' Not-in-family', ' White', ' Female', 20.0, ' United-States'] [39.0, ' State-gov', ' Bachelors', 13.0, ' Never-married', ' Adm-clerical', ' Not-in-family', ' White', ' Male', 40.0, ' United-States'] [50.0, ' Self-emp-not-inc', ' Bachelors', 13.0, ' Married-civ-spouse', ' Exec-managerial', ' Husband', ' White', ' Male', 13.0, ' United-States']\n",
      "\n",
      "Number of instances (N):  1000\n",
      "Number of attributes (F):  11\n",
      "Number of labels (L):  2\n",
      "\n",
      "\n",
      "Predicted class probabilities for instance N-3:  9.046250456197061e-08\n",
      "Predicted class ID for instance N-3:  >50K\n",
      "\n",
      "Predicted class probabilities for instance N-2:  2.6275771202149037e-09\n",
      "Predicted class ID for instance N-2:  >50K\n",
      "\n",
      "Predicted class probabilities for instance N-1:  1.2516683116526255e-10\n",
      "Predicted class ID for instance N-1:  >50K\n"
     ]
    }
   ],
   "source": [
    "# This cell should act as your \"main\" function where you call the above functions \n",
    "# on the full ADULT data set, and print the evaluation score. [0.33 marks]\n",
    "\n",
    "\n",
    "\n",
    "# First, read in the data and apply your NB model to the OBJECTIVITY data\n",
    "X_train, X_test, y_train, y_test, num_instances, attribute, num_lbl = preprocess(\"dataset/adult.csv\")\n",
    "trained = train(X_train, y_train, attribute)\n",
    "\n",
    "\n",
    "\n",
    "# Second, print the full evaluation results from the evaluate() function\n",
    "result = []\n",
    "prob = []\n",
    "for test in X_test:\n",
    "    prob.append(predict(trained, test, attribute, attribute_is_numeric(X_train))[0])\n",
    "    result.append(predict(trained, test, attribute, attribute_is_numeric(X_train))[1])\n",
    "print(\"Confusion matrix:\\n\", evaluate(y_test, result)[0])\n",
    "print(\"Precision: \",evaluate(y_test, result)[1])\n",
    "print(\"Recall: \",evaluate(y_test, result)[2])\n",
    "print(\"F1 score: \",evaluate(y_test, result)[3])\n",
    "print(\"Accuracy: \", evaluate(y_test, result)[4])\n",
    "# result = [lbl.strip() for lbl in result]\n",
    "\n",
    "\n",
    "\n",
    "# Third, print data statistics and model predictions, as instructed below \n",
    "# N is the total number of instances, F the total number of attributes, L the total number of labels\n",
    "# The \"class probabilities\" may be unnormalized\n",
    "# The \"predicted class ID\" must be in range (0, L)\n",
    "\n",
    "print(\"Attribute vectors of instances [0, 1, 2]: \", X_train[0], X_train[1], X_train[2])\n",
    "\n",
    "print(\"\\nNumber of instances (N): \", num_instances)\n",
    "print(\"Number of attributes (F): \", len(attribute[:-1]))\n",
    "print(\"Number of labels (L): \", num_lbl)\n",
    "\n",
    "#N-3 will be instance number 97 out of 100 instances in test set\n",
    "print(\"\\n\\nPredicted class probabilities for instance N-3: \", exp(prob[96]))\n",
    "print(\"Predicted class ID for instance N-3: \", result[96][1:])\n",
    "\n",
    "#N-2 will be instance number 98 out of 100 instances in test set\n",
    "print(\"\\nPredicted class probabilities for instance N-2: \", exp(prob[97]))\n",
    "print(\"Predicted class ID for instance N-2: \", result[97][1:])\n",
    "\n",
    "#N-1 will be instance number 99 out of 100 instances in test set\n",
    "print(\"\\nPredicted class probabilities for instance N-1: \", exp(prob[98]))\n",
    "print(\"Predicted class ID for instance N-1: \", result[98][1:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2: Conceptual questions [8 marks for groups of 1] / [16 marks for groups of 2]\n",
    "\n",
    "\n",
    "If you are in a group of 1, you should respond to Q1 and Q2.\n",
    "\n",
    "If you are in a group of 2, you should respond to Q1, Q2, Q3 and Q4.\n",
    "\n",
    "A response to a question should take about 100–250 words. You may need to develope codes or functions to help respond to the question here. \n",
    "\n",
    "#### NOTE: We strongly recommend <u>including figures or tables, etc.</u> to support your responses. The figures and tables inserted in Markdown cells must be reproducable by your code."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1 [4 marks]\n",
    "<u>Sensitivity</u> and <u>specificity</u> are two model evaluation metrics.  A good model should have both sensitivity and specificity high. Use the $2 \\times 2$ confusion matrix returned by `evaluate()` to calculate the sensitivity and specificity. Do you see a difference between them? If so, what causes this difference? Provide suggestions to improve the model performance. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sensitivity:  0.92\n",
      "Specificity:  0.68\n"
     ]
    }
   ],
   "source": [
    "# Write additional code here, if necessary (you may insert additional code cells)\n",
    "confusion_matrix = evaluate(y_test, result)[0]\n",
    "positive = \" <=50K\"\n",
    "negative = \" >50K\"\n",
    "sensitivity = confusion_matrix[positive][positive] / (confusion_matrix[positive][positive] + confusion_matrix[positive][negative])\n",
    "specificity = confusion_matrix[negative][negative] / (confusion_matrix[negative][negative] + confusion_matrix[negative][positive])\n",
    "print(\"Sensitivity: \", sensitivity)\n",
    "print(\"Specificity: \", specificity)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is a considerable difference between the sensitivity and specificity derived from this dataset, where sensitivity is much higher.\n",
    "\n",
    "Since sensitivity works with true positives and false positives, and specificity works with true negatives and false negatives, one explanation would be that the numbers of instances of each label in the training dataset aren't equal.\n",
    "\n",
    "To be specific, the given dataset has a particular imbalance between \" <=50K\" and \" >50K\" class labels. The \" <=50K\" class label takes up 76.89% the number of instances in the test data, while the rest belong to the \" >50K\" class.\n",
    "\n",
    "One suggestion would be to find more instances of the \" >50K\" class label and include them in the training dataset for a more balanced learning process. The model will then not be biased towards any class label that has considerably more instances."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2 [4 marks]\n",
    "You can adopt different methods for training and/or testing, which will produce different results in model evaluation. \n",
    "\n",
    "(a) Instead of Gaussian, <u>implement KDE</u> for  $P(X_i|c_j)$ for numeric attributes $X_i$. Compare the evaluation results with Gaussian. Which one do you think is more suitable to model $P(X_i|c_j)$, Gaussian or KDE? Observe all numeric attributes and justify your answer.\n",
    "\n",
    "You can choose an arbitrary value for kernel bandwidth $\\sigma$ for KDE, but a value between 3 and 15 is recommended. You should write code to implement KDE, not call an existing function/method such as `KernelDensity` from `scikit-learn`.\n",
    "\n",
    "(b) Implement <u>10-fold and 2-fold cross-validations</u>.  \n",
    "\tObserve the evaluation results in each fold and the average accuracy, recall and specificity over all folds. \n",
    "\tComment on what is the effect by changing the values of $m$ in $m$-fold cross validation. (You can choose either Gaussian or KDE Naive Bayes.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part A is as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write additional code here, if necessary (you may insert additional code cells)\n",
    "def KDE(x, dataset, bandwidth):\n",
    "    prob = []\n",
    "    prob = [probability(x - dataset[i], 0, bandwidth) for i in range (len(dataset))]\n",
    "    return np.sum(prob)/len(dataset)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def KDE_predict(trained_data, test_data, att, att_is_numeric, bandwidth):\n",
    "    less_dict = trained_data[0][\" <=50K\"]\n",
    "    more_dict = trained_data[0][\" >50K\"]\n",
    "    prior_1, prior_2 = trained_data[1], trained_data[2]\n",
    "    less_than_50K_prob = log(prior_1)\n",
    "    more_than_50K_prob = log(prior_2)\n",
    "    for i in range(len(att_is_numeric)):\n",
    "        if not att_is_numeric[i]:\n",
    "            less_than_50K_prob += log(less_dict[att[i]][test_data[i]])\n",
    "            more_than_50K_prob += log(more_dict[att[i]][test_data[i]])\n",
    "        else:\n",
    "            if test_data[i] == \" ?\":\n",
    "                less_than_50K_prob += log(KDE(less_dict[att[i]]['mean'], less_dict[att[i]]['values'], bandwidth))\n",
    "                more_than_50K_prob += log(KDE(more_dict[att[i]]['mean'], more_dict[att[i]]['values'], bandwidth))\n",
    "            else:\n",
    "                less_than_50K_prob += log(KDE(test_data[i], less_dict[att[i]]['values'], bandwidth))\n",
    "                more_than_50K_prob += log(KDE(test_data[i], more_dict[att[i]]['values'], bandwidth))\n",
    "    prob = less_than_50K_prob if less_than_50K_prob > more_than_50K_prob else more_than_50K_prob\n",
    "    return prob, \" <=50K\" if less_than_50K_prob > more_than_50K_prob else \" >50K\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bandwidth:  3\n",
      "Accuracy:  0.85\n",
      "\n",
      "\n",
      "Bandwidth:  4\n",
      "Accuracy:  0.84\n",
      "\n",
      "\n",
      "Bandwidth:  5\n",
      "Accuracy:  0.82\n",
      "\n",
      "\n",
      "Bandwidth:  6\n",
      "Accuracy:  0.82\n",
      "\n",
      "\n",
      "Bandwidth:  7\n",
      "Accuracy:  0.82\n",
      "\n",
      "\n",
      "Bandwidth:  8\n",
      "Accuracy:  0.82\n",
      "\n",
      "\n",
      "Bandwidth:  9\n",
      "Accuracy:  0.82\n",
      "\n",
      "\n",
      "Bandwidth:  10\n",
      "Accuracy:  0.83\n",
      "\n",
      "\n",
      "Bandwidth:  11\n",
      "Accuracy:  0.82\n",
      "\n",
      "\n",
      "Bandwidth:  12\n",
      "Accuracy:  0.82\n",
      "\n",
      "\n",
      "Bandwidth:  13\n",
      "Accuracy:  0.82\n",
      "\n",
      "\n",
      "Bandwidth:  14\n",
      "Accuracy:  0.82\n",
      "\n",
      "\n",
      "Bandwidth:  15\n",
      "Accuracy:  0.82\n",
      "\n",
      "\n",
      "Max accuracy with KDE:  0.85\n",
      "Accuracy with Gaussian:  0.86\n"
     ]
    }
   ],
   "source": [
    "X_train, X_test, y_train, y_test, num_instances, attribute, num_lbl = preprocess(\"dataset/adult.csv\")\n",
    "trained_data = train(X_train, y_train, attribute)\n",
    "max_accuracy = 0\n",
    "Gaussian = [predict(trained, test, attribute, attribute_is_numeric(X_train))[1] for test in X_test]\n",
    "for i in range (3,16):\n",
    "    result = []\n",
    "    prob = []\n",
    "    for test in X_test:\n",
    "        prob.append(KDE_predict(trained, test, attribute, attribute_is_numeric(X_train),i)[0])\n",
    "        result.append(KDE_predict(trained, test, attribute, attribute_is_numeric(X_train),i)[1])\n",
    "    #print(\"Confusion matrix:\\n\", evaluate(y_test, result)[0])\n",
    "    print(\"Bandwidth: \", i)\n",
    "#     print(\"Precision: \",evaluate(y_test, result)[1])\n",
    "#     print(\"Recall: \",evaluate(y_test, result)[2])\n",
    "#     print(\"F1 score: \",evaluate(y_test, result)[3])\n",
    "    print(\"Accuracy: \",evaluate(y_test, result)[4])\n",
    "    if evaluate(y_test, result)[4] > max_accuracy:\n",
    "        max_accuracy = evaluate(y_test, result)[4]\n",
    "    print(\"\\n\")\n",
    "print(\"Max accuracy with KDE: \", max_accuracy)\n",
    "print(\"Accuracy with Gaussian: \", evaluate(y_test, Gaussian)[4])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "source": [
    "I implement KDE for bandwidths in the range from 3 to 15, and achieve a max accuracy of 0.85 or 85%. This is lower than the accuracy obtained with the Gaussian method (0.86 or 86%).\n",
    "\n",
    "The Gaussian method performs better in this dataset, but in order to do so, it's made an assumption that data are normally distributed. KDE, on the other hand, performs worse for all bandwidths from 3 to 15, but makes no assumption regarding what distribution data points follow.\n",
    "\n",
    "For a dataset this small (900 training instances and 1000 instances as a whole), it's better to not make any assumptions about the distribution of instances. Therefore, KDE is a good candidate for calculating conditional probability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part B is as follows:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We need to split data into n equal chunks. After than, I'm going to proceed with Gaussian Naive Bayes for the cross validation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(filename, n):\n",
    "    X = []\n",
    "    y = []\n",
    "    data = []\n",
    "    num_instances = 0\n",
    "    with open(filename, 'r') as f:\n",
    "        attribute = f.readline().strip().split(\",\")\n",
    "        for line in f.readlines():\n",
    "            num_instances += 1\n",
    "            line = line.strip().split(\",\")\n",
    "            line[0] = float(line[0]) #age\n",
    "            line[3] = float(line[3]) #education num\n",
    "            line[-3] = float(line[-3]) #hours per week\n",
    "            X.append(line[:-1])\n",
    "            y.append(line[-1])\n",
    "    num_lbl = len(set(y))\n",
    "    total = len(X)\n",
    "    partition_X = []\n",
    "    partition_y = []\n",
    "    for i in range(n):\n",
    "        partition_X.append(X[int(i*total/n) : int((i+1)*total/n)])\n",
    "        partition_y.append(y[int(i*total/n) : int((i+1)*total/n)])\n",
    "    return partition_X, partition_y, num_instances, attribute, num_lbl"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cross_validation(filename, n):\n",
    "    X, y = partition(filename, n)[0], partition(filename, n)[1]\n",
    "    att = partition(filename, n)[3]\n",
    "    precision = []\n",
    "    recall = []\n",
    "    specificity = []\n",
    "    accuracy = []\n",
    "    for i in range(n):\n",
    "        print(\"Fold \", i+1)\n",
    "        print(\"\\n\")\n",
    "        X_test = X[i]\n",
    "        y_test = y[i]\n",
    "        \n",
    "        X_train = [instance for sublist in (X[0:i] + X[i+1:]) for instance in sublist]\n",
    "        y_train = [instance for sublist in (y[0:i] + y[i+1:]) for instance in sublist]\n",
    "        trained_data = train(X_train, y_train, att)\n",
    "        result = []\n",
    "        prob = []\n",
    "        for test in X_test:\n",
    "            prob.append(predict(trained, test, att, attribute_is_numeric(X_train))[0])\n",
    "            result.append(predict(trained, test, att, attribute_is_numeric(X_train))[1])\n",
    "        precision.append(evaluate(y_test, result)[1])\n",
    "        recall.append(evaluate(y_test, result)[2])\n",
    "        accuracy.append(evaluate(y_test, result)[4])\n",
    "        specificity.append(evaluate(y_test, result)[5])\n",
    "        print(\"Precision: \",evaluate(y_test, result)[1])\n",
    "        print(\"Recall: \",evaluate(y_test, result)[2])\n",
    "        print(\"Accuracy: \", evaluate(y_test, result)[4])\n",
    "        print(\"Specificity: \", evaluate(y_test, result)[5])\n",
    "        print(\"\\n\")\n",
    "    print(\"Average precision: \", np.mean(precision))\n",
    "    print(\"Average recall: \", np.mean(recall))\n",
    "    print(\"Average accuracy: \", np.mean(accuracy))\n",
    "    print(\"Average specificity: \", np.mean(specificity))\n",
    "    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cross validation for n = 10\n",
      "\n",
      "Fold  1\n",
      "\n",
      "\n",
      "Precision:  0.953125\n",
      "Recall:  0.8133333333333334\n",
      "Accuracy:  0.83\n",
      "Specificity:  0.88\n",
      "\n",
      "\n",
      "Fold  2\n",
      "\n",
      "\n",
      "Precision:  0.9552238805970149\n",
      "Recall:  0.8205128205128205\n",
      "Accuracy:  0.83\n",
      "Specificity:  0.8636363636363636\n",
      "\n",
      "\n",
      "Fold  3\n",
      "\n",
      "\n",
      "Precision:  0.8904109589041096\n",
      "Recall:  0.8441558441558441\n",
      "Accuracy:  0.8\n",
      "Specificity:  0.6521739130434783\n",
      "\n",
      "\n",
      "Fold  4\n",
      "\n",
      "\n",
      "Precision:  0.9436619718309859\n",
      "Recall:  0.8701298701298701\n",
      "Accuracy:  0.86\n",
      "Specificity:  0.8260869565217391\n",
      "\n",
      "\n",
      "Fold  5\n",
      "\n",
      "\n",
      "Precision:  0.925\n",
      "Recall:  0.925\n",
      "Accuracy:  0.88\n",
      "Specificity:  0.7\n",
      "\n",
      "\n",
      "Fold  6\n",
      "\n",
      "\n",
      "Precision:  0.9295774647887324\n",
      "Recall:  0.8354430379746836\n",
      "Accuracy:  0.82\n",
      "Specificity:  0.7619047619047619\n",
      "\n",
      "\n",
      "Fold  7\n",
      "\n",
      "\n",
      "Precision:  0.8933333333333333\n",
      "Recall:  0.8701298701298701\n",
      "Accuracy:  0.82\n",
      "Specificity:  0.6521739130434783\n",
      "\n",
      "\n",
      "Fold  8\n",
      "\n",
      "\n",
      "Precision:  0.8513513513513513\n",
      "Recall:  0.8289473684210527\n",
      "Accuracy:  0.76\n",
      "Specificity:  0.5416666666666666\n",
      "\n",
      "\n",
      "Fold  9\n",
      "\n",
      "\n",
      "Precision:  0.8888888888888888\n",
      "Recall:  0.8767123287671232\n",
      "Accuracy:  0.83\n",
      "Specificity:  0.7037037037037037\n",
      "\n",
      "\n",
      "Fold  10\n",
      "\n",
      "\n",
      "Precision:  0.92\n",
      "Recall:  0.8961038961038961\n",
      "Accuracy:  0.86\n",
      "Specificity:  0.7391304347826086\n",
      "\n",
      "\n",
      "Average precision:  0.9150572849694416\n",
      "Average recall:  0.8580468369528493\n",
      "Average accuracy:  0.8290000000000001\n",
      "Average specificity:  0.73204767133028\n",
      "\n",
      "\n",
      "\n",
      "Cross validation for n = 2\n",
      "\n",
      "Fold  1\n",
      "\n",
      "\n",
      "Precision:  0.9323943661971831\n",
      "Recall:  0.8552971576227391\n",
      "Accuracy:  0.84\n",
      "Specificity:  0.7876106194690266\n",
      "\n",
      "\n",
      "Fold  2\n",
      "\n",
      "\n",
      "Precision:  0.896457765667575\n",
      "Recall:  0.8612565445026178\n",
      "Accuracy:  0.818\n",
      "Specificity:  0.6779661016949152\n",
      "\n",
      "\n",
      "Average precision:  0.9144260659323791\n",
      "Average recall:  0.8582768510626784\n",
      "Average accuracy:  0.829\n",
      "Average specificity:  0.7327883605819709\n"
     ]
    }
   ],
   "source": [
    "print(\"Cross validation for n = 10\\n\")\n",
    "cross_validation(\"dataset/adult.csv\", 10)\n",
    "print(\"\\n\\n\")\n",
    "print(\"Cross validation for n = 2\\n\")\n",
    "cross_validation(\"dataset/adult.csv\", 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bigger m tends to yield less noise compared to smaller m. Also, for bigger values of m, we can train and test the data in different scenarios, and as long as there is an even distribution of instances of each class throughout the dataset, bigger m would allow for greater generalisation and perform better when encountering new instances.\n",
    "\n",
    "One disadvantage of using a large m value is total running time. We're essentially re-training and re-predict m times, so for a dataset of considerable size, this whole process would take long to finish. However, given our dataset of 1000 instances, 10-fold cross validation would still be a better candidate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q3 [4 marks]\n",
    "In `train()`, you are asked to treat the missing value of nominal attributes as a new category. There is another option (as suggested in Thu lecture in week 2): <u>ignoring the missing values</u>. \n",
    "Compare the two methods in both large and small datasets. Comment and explain your observations.\n",
    "You can extract the first 50 records to construct a small dataset.Use Gaussian Naive Bayes only for this question."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write additional code here, if necessary (you may insert additional code cells)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Provide your text answer of 150-200 words in this cell."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q4 [4 marks]\n",
    "In week 4, we have learned how to obtain information gain (IG) and gain ratio (GR) to choose an attribute to split a node in a decision tree. We will see how to apply them in the Naive Bayes classification.\n",
    "\n",
    "(a) Compute the GR of each attribute $X_i$, relative to the class distribution. In the Na\\\"ive Bayes classifier, remove attributes in the ascending order of GR: first, remove $P(X_i|c_j)$ such that $X_i$ has the least GR; second, remove $P(X_{i'}|c_j)$ such that $X_{i'}$ has the second least GR,......, until there is only one $X_{i*}$ with the largest GR remaining in the maximand $P(c_j) P(X_{i^*} | c_j)$. Observe the <u>change of the accuracy for both Gaussian and KDE</u> (Choose bandwidth $\\sigma=10$ for KDE).\n",
    "\n",
    "(b) Compute the IG between each pair of attributes. Describe and explain your observations. Choose an attribute and implement an estimator to predict the value of `education num`. Explain why you choose this attribute. Enumerate two other examples that an attribute can be used to estimate the other and explain the reason.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Write additional code here, if necessary (you may insert additional code cells)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### (a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Provide your text answer to **Question 4.a** of 100-150 words in this cell."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### (b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Provide your text answer to **Question 4.b** of 150-200 words in this cell."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>Authorship Declaration</b>:\n",
    "\n",
    "   (1) I certify that the program contained in this submission is completely\n",
    "   my own individual work, except where explicitly noted by comments that\n",
    "   provide details otherwise.  I understand that work that has been developed\n",
    "   by another student, or by me in collaboration with other students,\n",
    "   or by non-students as a result of request, solicitation, or payment,\n",
    "   may not be submitted for assessment in this subject.  I understand that\n",
    "   submitting for assessment work developed by or in collaboration with\n",
    "   other students or non-students constitutes Academic Misconduct, and\n",
    "   may be penalized by mark deductions, or by other penalties determined\n",
    "   via the University of Melbourne Academic Honesty Policy, as described\n",
    "   at https://academicintegrity.unimelb.edu.au.\n",
    "\n",
    "   (2) I also certify that I have not provided a copy of this work in either\n",
    "   softcopy or hardcopy or any other form to any other student, and nor will\n",
    "   I do so until after the marks are released. I understand that providing\n",
    "   my work to other students, regardless of my intention or any undertakings\n",
    "   made to me by that other student, is also Academic Misconduct.\n",
    "\n",
    "   (3) I further understand that providing a copy of the assignment\n",
    "   specification to any form of code authoring or assignment tutoring\n",
    "   service, or drawing the attention of others to such services and code\n",
    "   that may have been made available via such a service, may be regarded\n",
    "   as Student General Misconduct (interfering with the teaching activities\n",
    "   of the University and/or inciting others to commit Academic Misconduct).\n",
    "   I understand that an allegation of Student General Misconduct may arise\n",
    "   regardless of whether or not I personally make use of such solutions\n",
    "   or sought benefit from such actions.\n",
    "\n",
    "   <b>Signed by</b>: Truong Giang Hoang - 1166323\n",
    "   \n",
    "   <b>Dated</b>: 4/4/2022"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}