{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <img style=\"float: left; padding-right: 10px; width: 45px\" src=\"https://raw.githubusercontent.com/Harvard-IACS/2018-CS109A/master/content/styles/iacs.png\"> CS109B Data Science 2: Advanced Topics in Data Science \n",
    "## Homework 2 - Clustering\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**Harvard University**<br/>\n",
    "**Spring 2020**<br/>\n",
    "**Instructors**: Mark Glickman, Pavlos Protopapas, & Chris Tanner \n",
    "\n",
    "\n",
    "<hr style=\"height:2pt\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Homework 2 is due February 20th"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style>\n",
       "blockquote { background: #AEDE94; }\n",
       "h1 { \n",
       "    padding-top: 25px;\n",
       "    padding-bottom: 25px;\n",
       "    text-align: left; \n",
       "    padding-left: 10px;\n",
       "    background-color: #DDDDDD; \n",
       "    color: black;\n",
       "}\n",
       "h2 { \n",
       "    padding-top: 10px;\n",
       "    padding-bottom: 10px;\n",
       "    text-align: left; \n",
       "    padding-left: 5px;\n",
       "    background-color: #EEEEEE; \n",
       "    color: black;\n",
       "}\n",
       "\n",
       "div.exercise {\n",
       "\tbackground-color: #ffcccc;\n",
       "\tborder-color: #E9967A; \t\n",
       "\tborder-left: 5px solid #800080; \n",
       "\tpadding: 0.5em;\n",
       "}\n",
       "\n",
       "span.sub-q {\n",
       "\tfont-weight: bold;\n",
       "}\n",
       "div.theme {\n",
       "\tbackground-color: #DDDDDD;\n",
       "\tborder-color: #E9967A; \t\n",
       "\tborder-left: 5px solid #800080; \n",
       "\tpadding: 0.5em;\n",
       "\tfont-size: 18pt;\n",
       "}\n",
       "div.gc { \n",
       "\tbackground-color: #AEDE94;\n",
       "\tborder-color: #E9967A; \t \n",
       "\tborder-left: 5px solid #800080; \n",
       "\tpadding: 0.5em;\n",
       "\tfont-size: 12pt;\n",
       "}\n",
       "p.q1 { \n",
       "    padding-top: 5px;\n",
       "    padding-bottom: 5px;\n",
       "    text-align: left; \n",
       "    padding-left: 5px;\n",
       "    background-color: #EEEEEE; \n",
       "    color: black;\n",
       "}\n",
       "header {\n",
       "   padding-top: 35px;\n",
       "    padding-bottom: 35px;\n",
       "    text-align: left; \n",
       "    padding-left: 10px;\n",
       "    background-color: #DDDDDD; \n",
       "    color: black;\n",
       "}\n",
       "</style>\n",
       "\n"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#PLEASE RUN THIS CELL \n",
    "import requests\n",
    "from IPython.core.display import HTML\n",
    "styles = requests.get(\"https://raw.githubusercontent.com/Harvard-IACS/2018-CS109A/master/content/styles/cs109.css\").text\n",
    "HTML(styles)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### INSTRUCTIONS\n",
    "\n",
    "- This is individual homework - No collaboration/Groups\n",
    "- Problem 1 + Problem 2 = 75 points ; Problem 3 = 25 points\n",
    "- To submit your assignment, please follow the instructions on Canvas.\n",
    "- Please restart the kernel and run the entire notebook again before you submit.\n",
    "\n",
    "<hr style=\"height:2pt\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Please use the libraries below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "%matplotlib inline \n",
    "import matplotlib.pyplot as plt\n",
    "import scipy.cluster.hierarchy as hac\n",
    "from scipy.spatial.distance import pdist\n",
    "from sklearn.preprocessing import StandardScaler\n",
    "from sklearn.cluster import DBSCAN\n",
    "\n",
    "from sklearn.cluster import KMeans\n",
    "from gap_statistic import OptimalK\n",
    "#from sklearn.datasets.samples_generator import make_blobs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "<hr style=\"height:2pt\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"theme\">*Handy* Algorithms </div>\n",
    "\n",
    "\n",
    "    \n",
    "In this assignment, you will be working with data collected from a motion capture camera system. The system was used to record 14 different users performing 5 distinct hand postures with markers attached to a left-handed glove. A set of markers on the back of the glove was used to establish a local coordinate system for the hand, and 8 additional markers were attached to the thumb and fingers of the glove. A total of 24 features were collected based on observations from the camera system. Two other variables in the dataset were the ID of the user and the posture that the user made.\n",
    "\n",
    "These data have been preprocessed, including transformation to the local coordinate system of the record, removal of outliers, and removal of missing data.\n",
    "\n",
    "The dataset `postures_clean.csv` contains 38,943 rows and 26 columns. Each row corresponds to a single frame as captured by the camera system. The data are represented in the following manner:\n",
    "\n",
    "`Class (type: Integer). The hand posture of the given observation, with`\n",
    "\n",
    "`1 = Fist (with thumb out)`\n",
    "\n",
    "`2 = Stop (hand flat)`\n",
    "\n",
    "`3 = Point1 (point with index finger)`\n",
    "\n",
    "`4 = Point2 (point with index and middle fingers)`\n",
    "\n",
    "`5 = Grab (fingers curled as if to grab)`\n",
    "\n",
    "`User (type: Integer). The ID of the user that contributed the record.`\n",
    "\n",
    "`X0, Y0, Z0, X1, Y1, Z1,..., X7, Y7, Z7 (type: Real). The x-coordinate, y-coordinate, and z-coordinate of the eight unlabeled marker positions.`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Start by reading the dataset into a pandas data frame."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class='exercise'>Problem 1: Clustering with k-means </div>\n",
    "\n",
    "(a) After appropriate pre-processing (but not scaling) run the k-means clustering algorithm, using the `KMeans` class from sklearn.cluster, with the number of clusters corresponding to the number of users, `n_init` of 46, and 109 as the random seed. Add the result as a new column called `Cluster14` to your data frame."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) Use the function below to visualize the results for k-means on a random sample of 2,000 observations (it will take the sample for you). Does 14 clusters seem to make sense?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.decomposition import PCA\n",
    "\n",
    "def plot_clusters(full_data, group_col, scaling_mode):\n",
    "    marker_types = [\".\", \"v\", \"1\", \"^\", \"s\", \"p\", \"P\", \"3\", \"H\", \"<\", \"|\", \"_\", \"x\", \"*\"]\n",
    "    marker_colors = np.concatenate([np.array(plt.cm.tab10.colors),np.array(plt.cm.Pastel1.colors)])\n",
    "    \n",
    "    feature_columns = [colname for colname in list(full_data.columns) if colname not in {'Class','User','Cluster14','Cluster5'}]\n",
    "    features_only = full_data[feature_colummns]\n",
    "    \n",
    "    # make a scaled df if needed, (but don't scale cluster labels)\n",
    "    if scaling_mode == True:\n",
    "        scaler = StandardScaler()\n",
    "        scaled_features = pd.DataFrame(scaler.fit_transform(features_only), columns=feature_colummns)\n",
    "    elif scaling_mode == False:\n",
    "        scaled_features = features_only\n",
    "    else:\n",
    "        raise ValueError(\"Unexpected value for scaling_mode\")\n",
    "\n",
    "    # fit PCA to the whole scaled data\n",
    "    fitted_pca = PCA().fit(scaled_features)\n",
    "\n",
    "    # take a sample of the whole scaled data\n",
    "    scaled_sample = scaled_features.sample(2000, random_state=109)\n",
    "\n",
    "    # apply the PCA transform on the sample\n",
    "    pca_sample = pd.DataFrame(fitted_pca.transform(scaled_sample), columns = [\"PCA{}\".format(i) for i in range(len(scaled_sample.columns.values))])\n",
    "    \n",
    "    \n",
    "    # re-include a cluster label for the pca data\n",
    "    if 'Cluster14' in full_data.columns.values:\n",
    "        pca_sample['Cluster14'] = full_data.loc[pca_sample.index, \"Cluster14\"]\n",
    "    if 'Cluster5' in full_data.columns.values:\n",
    "        pca_sample['Cluster5'] = full_data.loc[pca_sample.index, \"Cluster5\"]\n",
    "    \n",
    "    plt.figure(figsize=(11,8.5))\n",
    "    for i, (cluster_id, cur_df) in enumerate(pca_sample.groupby([group_col])):\n",
    "\n",
    "        pca1_scores = cur_df.iloc[:,0]\n",
    "        pca2_scores = cur_df.iloc[:,1]\n",
    "        plt.scatter(pca1_scores, pca2_scores, label=cluster_id, c=marker_colors[i].reshape(1,-1), marker=marker_types[i])\n",
    "\n",
    "    plt.xlabel(\"PC1 ({}%)\".format(np.round(100*fitted_pca.explained_variance_ratio_[0],1)))\n",
    "    plt.ylabel(\"PC2 ({}%)\".format(np.round(100*fitted_pca.explained_variance_ratio_[1],1)))\n",
    "    plt.legend()\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "your response here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) Plot the silhouette scores using the function below, from lecture. Give it a 10% sample of the data to speed the visualization. How reasonable does the clustering seem based on this plot? How does it compare to the information in the plot above?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics import silhouette_samples, silhouette_score\n",
    "import matplotlib.cm as cm\n",
    "#modified code from http://scikit-learn.org/stable/auto_examples/cluster/plot_kmeans_silhouette_analysis.html\n",
    "\n",
    "def silplot(X, cluster_labels, clusterer, pointlabels=None):\n",
    "    n_clusters = clusterer.n_clusters\n",
    "    \n",
    "    # Create a subplot with 1 row and 2 columns\n",
    "    fig, (ax1, ax2) = plt.subplots(1, 2)\n",
    "    fig.set_size_inches(11,8.5)\n",
    "\n",
    "    # The 1st subplot is the silhouette plot\n",
    "    # The silhouette coefficient can range from -1, 1 but in this example all\n",
    "    # lie within [-0.1, 1]\n",
    "    ax1.set_xlim([-0.1, 1])\n",
    "    \n",
    "    # The (n_clusters+1)*10 is for inserting blank space between silhouette\n",
    "    # plots of individual clusters, to demarcate them clearly.\n",
    "    ax1.set_ylim([0, len(X) + (n_clusters + 1) * 10])\n",
    "\n",
    "    # The silhouette_score gives the average value for all the samples.\n",
    "    # This gives a perspective into the density and separation of the formed\n",
    "    # clusters\n",
    "    silhouette_avg = silhouette_score(X, cluster_labels)\n",
    "    print(\"For n_clusters = \", n_clusters,\n",
    "          \", the average silhouette_score is \", silhouette_avg,\".\",sep=\"\")\n",
    "\n",
    "    # Compute the silhouette scores for each sample\n",
    "    sample_silhouette_values = silhouette_samples(X, cluster_labels)\n",
    "\n",
    "    y_lower = 10\n",
    "    for i in range(0,n_clusters+1):\n",
    "        # Aggregate the silhouette scores for samples belonging to\n",
    "        # cluster i, and sort them\n",
    "        ith_cluster_silhouette_values = \\\n",
    "            sample_silhouette_values[cluster_labels == i]\n",
    "\n",
    "        ith_cluster_silhouette_values.sort()\n",
    "\n",
    "        size_cluster_i = ith_cluster_silhouette_values.shape[0]\n",
    "        y_upper = y_lower + size_cluster_i\n",
    "\n",
    "        color = cm.nipy_spectral(float(i) / n_clusters)\n",
    "        ax1.fill_betweenx(np.arange(y_lower, y_upper),\n",
    "                          0, ith_cluster_silhouette_values,\n",
    "                          facecolor=color, edgecolor=color, alpha=0.7)\n",
    "\n",
    "        # Label the silhouette plots with their cluster numbers at the middle\n",
    "        ax1.text(-0.05, y_lower + 0.5 * size_cluster_i, str(i))\n",
    "\n",
    "        # Compute the new y_lower for next plot\n",
    "        y_lower = y_upper + 10  # 10 for the 0 samples\n",
    "\n",
    "    ax1.set_title(\"The silhouette plot for the various clusters.\")\n",
    "    ax1.set_xlabel(\"The silhouette coefficient values\")\n",
    "    ax1.set_ylabel(\"Cluster label\")\n",
    "\n",
    "    # The vertical line for average silhouette score of all the values\n",
    "    ax1.axvline(x=silhouette_avg, color=\"red\", linestyle=\"--\")\n",
    "\n",
    "    ax1.set_yticks([])  # Clear the yaxis labels / ticks\n",
    "    ax1.set_xticks([-0.1, 0, 0.2, 0.4, 0.6, 0.8, 1])\n",
    "\n",
    "    # 2nd Plot showing the actual clusters formed\n",
    "    colors = cm.nipy_spectral(cluster_labels.astype(float) / n_clusters)\n",
    "    ax2.scatter(X[:, 0], X[:, 1], marker='.', s=200, lw=0, alpha=0.7,\n",
    "                c=colors, edgecolor='k')\n",
    "    xs = X[:, 0]\n",
    "    ys = X[:, 1]\n",
    "    \n",
    "    if pointlabels is not None:\n",
    "        for i in range(len(xs)):\n",
    "            plt.text(xs[i],ys[i],pointlabels[i])\n",
    "\n",
    "    # Labeling the clusters\n",
    "    centers = clusterer.cluster_centers_\n",
    "    # Draw white circles at cluster centers\n",
    "    ax2.scatter(centers[:, 0], centers[:, 1], marker='o',\n",
    "                c=\"white\", alpha=1, s=200, edgecolor='k')\n",
    "\n",
    "    for i, c in enumerate(centers):\n",
    "        ax2.scatter(c[0], c[1], marker='$%d$' % int(i), alpha=1,\n",
    "                    s=50, edgecolor='k')\n",
    "\n",
    "    ax2.set_title(\"The visualization of the clustered data.\")\n",
    "    ax2.set_xlabel(\"Feature space for the 1st feature\")\n",
    "    ax2.set_ylabel(\"Feature space for the 2nd feature\")\n",
    "\n",
    "    plt.suptitle((\"Silhouette analysis for KMeans clustering on sample data \"\n",
    "                  \"with n_clusters = %d\" % n_clusters),\n",
    "                 fontsize=14, fontweight='bold')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "your response here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(d) Repeat all of the above steps, but attempting to group by posture rather than by user. That is : \n",
    "\n",
    "(i) Run the k-means algorithm with 5 centroids instead of 14, creating a variable named `Cluster5` and adding it to the dataset. \n",
    "\n",
    "(ii) Visualize the results for k-means. Does 5 clusters seem to make sense from this plot?\n",
    "\n",
    "(iii) Plot the silhouette scores on a 10% sample of the data. How reasonable does the clustering seem based on this plot?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "your response here\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "your response here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(e) What do the results suggest? Does this make sense in the context of what we know about the problem?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "your response here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class='exercise'> <b> Problem 2: Other Ks  </b> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the previous problem, we examined the results of running k-means with 5 and 14 centroids on the postures data. In this problem, we will investigate a broader range of possible cluster sizes, with a borader range of metrics. \n",
    "\n",
    "**For all of these questions, you should work with a sample of 2,000 data points drawn with `pd.sample` and a random seed of 109.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(a) Use the elbow method to evaluate the best choice of the number of clusters, plotting the total within-cluster variation against the number of clusters, for k-means clustering with $k \\in \\{1,2,...,15\\}.$\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(b) Use the average silhouette to evaluate the choice of the number of clusters for k-means clustering with $k \\in \\{1,2,...,15\\}$. Plot the results. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(c) Use the gap statistic to evaluate the choice of the number of clusters for k-means clustering with $k \\in \\{1,2,..,15\\}$. Plot the results. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(d) After analyzing the plots produced by all three of these measures, discuss the number of k-means clusters that you think is the best fit for this dataset. Defend your answer with evidence from the previous parts of this question, the three graphs produced here, and what you surmise about this dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "your response here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class='exercise'> <b> Problem 3: Alternative Algorithms  </b> </div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(e) Run DBSCAN on the data. How many clusters are found, and how well does this clustering perform on e.g. silhouette score, excluding the points not assigned to any cluster?  \n",
    "*Note*: Do not use a sample of the data. Running the algorithm may take up to 5-10 minutes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(f) Hierarchical clustering. Run agglomerative clustering (using Ward's method), and plot the result using a dendrogram. Interpret the results, and describe the cluster size(s) the plot suggests. What level of aggregation is suggested by the sihoutte score?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "your response here"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "#your code here\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "your response here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(g) Overall, what do you conclude about the number and kind of clusters in this data set?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "your response here\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
