Hierarchical_mnist.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hierarchical Clustering\n",
    "\n",
    "- An alternative approach to K-means clustering\n",
    "- Does not require the user to specify the number of clusters\n",
    "- Data points can be dynamically clustered based on user's choice at various levels of abstraction\n",
    "\n",
    "Example of Hierarchical clustering\n",
    "\n",
    "Villages -> Taluks -> Districts -> States -> Countries -> Continents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Step by Step hierarchical clustering\n",
    "\n",
    "## Bottom-up or agglomerative clustering\n",
    "\n",
    "Start with N clusters where N is the number of data points\n",
    "\n",
    "The below link shows a step by step approach to a simple agglomerative clustering algorithm\n",
    "\n",
    "https://home.deib.polimi.it/matteucc/Clustering/tutorial_html/hierarchical.html\n",
    "\n",
    "\n",
    "For more details on Hierarchical clustering refer to: \n",
    "\n",
    "https://cse.buffalo.edu/~jing/cse601/fa12/materials/clustering_hierarchical.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Dendrogram\n",
    "\n",
    "Consider the synthetic data below which is generated from three different distributions. The points are shown in three distinct colours and indicate the presence of three different classes of data. However, here we will ignore the classes and just use the 2d data for clustering\n",
    "\n",
    "![](./SyntheticData.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The below figure shows the dendrogram representation of the synthetic data and how to cluster these data\n",
    "\n",
    "![](./Synthetic_dendrogram.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interpreting dendrograms\n",
    "\n",
    "![](interpret_dendrogram.png 'Interpreting Dendrograms')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "show the clustering step wise\n",
    "\n",
    "## Similarity between data points (Dissimilarity measure)\n",
    "\n",
    "We can use any of the distance measures as dissimilarity measure between points\n",
    "\n",
    "But what about dissmilarity between clusters?\n",
    "\n",
    "There are different methods\n",
    "- Complete: Uses the maximum distance among all pairwise distances\n",
    "- Single: Uses the minimum distance among all pairwise distances between clusters\n",
    "- Average: Uses average distance\n",
    "- Centroid: Uses distance between the centroid of the two clusters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Clustering on MNIST dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import sklearn\n",
    "from scipy.cluster.hierarchy import linkage, dendrogram\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Fetch MNIST handwritten digit dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pickle\n",
    "with open('/home/meenu/Desktop/DL/Assignment/Assignment1/train_data.obj', 'rb') as fp:\n",
    "    X = pickle.load(fp)\n",
    "with open('/home/meenu/Desktop/DL/Assignment/Assignment1/train_labels.obj', 'rb') as fp:\n",
    "    y = pickle.load(fp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Select sample images from the dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_samples = 20\n",
    "unique, counts = np.unique(y[60000:], return_counts=True)\n",
    "counts = [0] + counts\n",
    "target_nums = [1,3,7]\n",
    "features_nums = np.zeros((n_samples*len(target_nums),784))\n",
    "targets_nums = np.zeros((n_samples*len(target_nums),))\n",
    "X_test = X[60000:,:]\n",
    "y_test= y[60000:]\n",
    "for i,k in enumerate(target_nums):\n",
    "    features_nums[i*n_samples:(i+1)*n_samples,:] = X_test[np.sum(counts[:k]):np.sum(counts[:k])+ n_samples,:]\n",
    "    targets_nums[i*n_samples:(i+1)*n_samples,] = y_test[np.sum(counts[:k]):np.sum(counts[:k])+ n_samples,]\n",
    "print(targets_nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Extract HOG features from the selected sample images"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from skimage.feature import hog,corner_fast\n",
    "features_nums = features_nums.reshape(-1,28,28)\n",
    "\n",
    "hog_features = [hog(features_nums[n,:,:],pixels_per_cell=(5,5)) for n in range(features_nums.shape[0])]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### flatten the HOG features and shuffle data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "hog_features = np.stack(hog_features,0)\n",
    "hog_features = hog_features.reshape(60,-1)\n",
    "hog_features.shape\n",
    "\n",
    "shuffle_idx = np.random.permutation(targets_nums.shape[0])\n",
    "\n",
    "features_shuffle = hog_features[shuffle_idx,:]\n",
    "target_shuffle = targets_nums[shuffle_idx]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Perform clustering and plot the dendrogram"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "plt.rcParams['figure.figsize'] = [50, 25]\n",
    "mergings = linkage(features_shuffle, method='complete')\n",
    "dendrogram(mergings,\n",
    "           truncate_mode='none',\n",
    "           labels=target_shuffle,\n",
    "           leaf_rotation=90,\n",
    "           leaf_font_size=32,\n",
    ")\n",
    "plt.ylabel('distance',fontsize=64)\n",
    "plt.yticks(fontsize=32)\n",
    "plt.show()"
   ]
  },
  {
   "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}