Activity-classification-1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# kNN Classification using k-mer frequency representation of text\n",
    "\n",
    "In this project, we will create a program to transform text into vectors using a slightly different technique than previously learned, and then perform kNN based classification on the resulting vectors. We will be using the badges UCI dataset (https://archive.ics.uci.edu/ml/machine-learning-databases/badges/badges.data), which contains names of some conference attendees along with a \"+\" or \"-\" class for each name. We will first make the text lowercase and separate the class from the badge name for each object, e.g., \"+ Naoki Abe\" should be turned into the object \"naoki abe\" with class \"+\". We will keep track of the original name (\"Naoki Abe\") associated with the vector.\n",
    "\n",
    "Our program will have two input parameters, c and k. Given the input parameter c, for each name, it will construct a vector of c-mer terms (usually called k-mers, but I am calling them c-mers since the input variable k is being used for kNN) of the required c length, by enumerating all subsequences of length c within the name. For example, if c=3, “naoki abe” becomes < “nao”, “aok”, “oki”, “ki “, “i a”, “ ab”, “abe” >. Finally, we will use the same technique we learned for word-based terms to construct sparse term-frequency vectors for each of the objects.\n",
    "\n",
    "Using the constructed vectors and their associated classes, given the input parameter k, we will construct a program that should perform kNN based classification using cosine similarity and 10-fold cross-validation and report the average classification accuracy among all tests. The class of the test sample should be chosen by majority vote, with ties broken in favor of the class with the highest average similarity. In the rare case that the test sample does not have any neighbors (no features in common with any training samples), we will assign a predicted class label by drawing a random value from a uniform distribution over [0,1) and classifying the test sample as “+” if the value is greater than 0.5 and “-“ otherwise.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import scipy.sparse as sp\n",
    "from numpy.linalg import norm\n",
    "from collections import Counter, defaultdict\n",
    "from scipy.sparse import csr_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code below reads the badges dataset into the variable `df` and extracts the string data associated with each person in the `vals` variable. Write code to split the strings in vals into their component names and classes. The `names` and `cls` lists should hold those components such that the $i$th person's name will be in `names[i]` and their associated class in `cls[i]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# read in the dataset\n",
    "df = pd.read_csv(\n",
    "    filepath_or_buffer='data/badges.data', \n",
    "    header=None, \n",
    "    sep=',')\n",
    "\n",
    "# separate names from classes\n",
    "vals = df.ix[:,:].values\n",
    "\n",
    "### FILL IN THE BLANKS ###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a function that, given a name and a `c-mer` length parameter `c`, will create the list of `c-mers` for the name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cmer(name, c=3):\n",
    "    r\"\"\" Given a name and parameter c, return the vector of c-mers associated with the name\n",
    "    \"\"\"\n",
    "    name = name.lower()\n",
    "    \n",
    "    ### FILL IN THE BLANKS ###\n",
    "    \n",
    "    v = []\n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "    return v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The following functions will be useful in later tasks. Study them carefully."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_matrix(docs):\n",
    "    r\"\"\" Build sparse matrix from a list of documents, \n",
    "    each of which is a list of word/terms in the document.  \n",
    "    \"\"\"\n",
    "    nrows = len(docs)\n",
    "    idx = {}\n",
    "    tid = 0\n",
    "    nnz = 0\n",
    "    for d in docs:\n",
    "        nnz += len(set(d))\n",
    "        for w in d:\n",
    "            if w not in idx:\n",
    "                idx[w] = tid\n",
    "                tid += 1\n",
    "    ncols = len(idx)\n",
    "        \n",
    "    # set up memory\n",
    "    ind = np.zeros(nnz, dtype=np.int)\n",
    "    val = np.zeros(nnz, dtype=np.double)\n",
    "    ptr = np.zeros(nrows+1, dtype=np.int)\n",
    "    i = 0  # document ID / row counter\n",
    "    n = 0  # non-zero counter\n",
    "    # transfer values\n",
    "    for d in docs:\n",
    "        cnt = Counter(d)\n",
    "        keys = list(k for k,_ in cnt.most_common())\n",
    "        l = len(keys)\n",
    "        for j,k in enumerate(keys):\n",
    "            ind[j+n] = idx[k]\n",
    "            val[j+n] = cnt[k]\n",
    "        ptr[i+1] = ptr[i] + l\n",
    "        n += l\n",
    "        i += 1\n",
    "            \n",
    "    mat = csr_matrix((val, ind, ptr), shape=(nrows, ncols), dtype=np.double)\n",
    "    mat.sort_indices()\n",
    "    \n",
    "    return mat\n",
    "\n",
    "def csr_info(mat, name=\"\", non_empy=False):\n",
    "    r\"\"\" Print out info about this CSR matrix. If non_empy, \n",
    "    report number of non-empty rows and cols as well\n",
    "    \"\"\"\n",
    "    if non_empy:\n",
    "        print(\"%s [nrows %d (%d non-empty), ncols %d (%d non-empty), nnz %d]\" % (\n",
    "                name, mat.shape[0], \n",
    "                sum(1 if mat.indptr[i+1] > mat.indptr[i] else 0 \n",
    "                for i in range(mat.shape[0])), \n",
    "                mat.shape[1], len(np.unique(mat.indices)), \n",
    "                len(mat.data)))\n",
    "    else:\n",
    "        print( \"%s [nrows %d, ncols %d, nnz %d]\" % (name, \n",
    "                mat.shape[0], mat.shape[1], len(mat.data)) )\n",
    "\n",
    "def csr_l2normalize(mat, copy=False, **kargs):\n",
    "    r\"\"\" Normalize the rows of a CSR matrix by their L-2 norm. \n",
    "    If copy is True, returns a copy of the normalized matrix.\n",
    "    \"\"\"\n",
    "    if copy is True:\n",
    "        mat = mat.copy()\n",
    "    nrows = mat.shape[0]\n",
    "    nnz = mat.nnz\n",
    "    ind, val, ptr = mat.indices, mat.data, mat.indptr\n",
    "    # normalize\n",
    "    for i in range(nrows):\n",
    "        rsum = 0.0    \n",
    "        for j in range(ptr[i], ptr[i+1]):\n",
    "            rsum += val[j]**2\n",
    "        if rsum == 0.0:\n",
    "            continue  # do not normalize empty rows\n",
    "        rsum = 1.0/np.sqrt(rsum)\n",
    "        for j in range(ptr[i], ptr[i+1]):\n",
    "            val[j] *= rsum\n",
    "            \n",
    "    if copy is True:\n",
    "        return mat\n",
    "        \n",
    "def namesToMatrix(names, c):\n",
    "    docs = [cmer(n, c) for n in names]\n",
    "    return build_matrix(docs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare the sparse matrix statistics (via `csr_info`) for c-mer representations of the names given $c\\in\\{1,2,3\\}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll now define a function to search for the top-$k$ neighbors for a given name (one of the objects the dataset), where proximity is computed via cosine similarity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findNeighborsForName(name, c=1, k=1):\n",
    "    # first, find the document for the given name\n",
    "    id = -1\n",
    "    for i in range(len(names)):\n",
    "        if names[i] == name:\n",
    "            id = i\n",
    "            break\n",
    "    if id == -1:\n",
    "        print(\"Name %s not found.\" % name)\n",
    "        return []\n",
    "    # now, compute similarities of name's vector against all other name vectors\n",
    "    mat = namesToMatrix(names, c)\n",
    "    csr_l2normalize(mat)\n",
    "    x = mat[id,:]\n",
    "    dots = x.dot(mat.T)\n",
    "    dots[0,id] = -1 # invalidate self-similarity\n",
    "    sims = list(zip(dots.indices, dots.data))\n",
    "    sims.sort(key=lambda x: x[1], reverse=True)\n",
    "    return [names[s[0]] for s in sims[:k] if s[1] > 0 ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let c=2 and k=5. Which are the closest neighbors for “Michael Kearns”, in decreasing order of similarity?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we'll define a couple functions to perform $d$-fold cross-validation, defaulting to $d=10$. Double-check the code for errors. What does the line\n",
    "```python\n",
    "tc = Counter(clstr[s[0]] for s in sims[:k]).most_common(2)\n",
    "```\n",
    "do?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def splitData(mat, cls, fold=1, d=10):\n",
    "    r\"\"\" Split the matrix and class info into train and test data using d-fold hold-out\n",
    "    \"\"\"\n",
    "    n = mat.shape[0]\n",
    "    r = int(np.ceil(n*1.0/d))\n",
    "    mattr = []\n",
    "    clstr = []\n",
    "    # split mat and cls into d folds\n",
    "    for f in range(d):\n",
    "        if f+1 != fold:\n",
    "            mattr.append( mat[f*r: min((f+1)*r, n)] )\n",
    "            clstr.extend( cls[f*r: min((f+1)*r, n)] )\n",
    "    # join all fold matrices that are not the test matrix\n",
    "    train = sp.vstack(mattr, format='csr')\n",
    "    # extract the test matrix and class values associated with the test rows\n",
    "    test = mat[(fold-1)*r: min(fold*r, n), :]\n",
    "    clste = cls[(fold-1)*r: min(fold*r, n)]\n",
    "\n",
    "    return train, clstr, test, clste\n",
    "    \n",
    "def classifyNames(names, cls, c=3, k=3, d=10):\n",
    "    r\"\"\" Classify names using c-mer frequency vector representations of the names and kNN classification with \n",
    "    cosine similarity and 10-fold cross validation\n",
    "    \"\"\"\n",
    "    docs = [cmer(n, c) for n in names]\n",
    "    mat = build_matrix(docs)\n",
    "    # since we're using cosine similarity, normalize the vectors\n",
    "    csr_l2normalize(mat)\n",
    "    \n",
    "    def classify(x, train, clstr):\n",
    "        r\"\"\" Classify vector x using kNN and majority vote rule given training data and associated classes\n",
    "        \"\"\"\n",
    "        # find nearest neighbors for x\n",
    "        dots = x.dot(train.T)\n",
    "        sims = list(zip(dots.indices, dots.data))\n",
    "        if len(sims) == 0:\n",
    "            # could not find any neighbors\n",
    "            return '+' if np.random.rand() > 0.5 else '-'\n",
    "        sims.sort(key=lambda x: x[1], reverse=True)\n",
    "        tc = Counter(clstr[s[0]] for s in sims[:k]).most_common(2)\n",
    "        if len(tc) < 2 or tc[0][1] > tc[1][1]:\n",
    "            # majority vote\n",
    "            return tc[0][0]\n",
    "        # tie break\n",
    "        tc = defaultdict(float)\n",
    "        for s in sims[:k]:\n",
    "            tc[clstr[s[0]]] += s[1]\n",
    "        return sorted(tc.items(), key=lambda x: x[1], reverse=True)[0][0]\n",
    "        \n",
    "    macc = 0.0\n",
    "    for f in range(d):\n",
    "        # split data into training and testing\n",
    "        train, clstr, test, clste = splitData(mat, cls, f+1, d)\n",
    "        # predict the class of each test sample\n",
    "        clspr = [ classify(test[i,:], train, clstr) for i in range(test.shape[0]) ]\n",
    "        # compute the accuracy of the prediction\n",
    "        acc = 0.0\n",
    "        for i in range(len(clste)):\n",
    "            if clste[i] == clspr[i]:\n",
    "                acc += 1\n",
    "        acc /= len(clste)\n",
    "        macc += acc\n",
    "        \n",
    "    return macc/d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given $c \\in \\{1,\\ldots,4\\}$ and  $k \\in \\{1,\\ldots,6\\}$, which meta-parameters result in the highest accuracy?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}