exercises/Week-4-Subspace-Clustering-23.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Week 4: Subspace Clustering and projected clustering"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 1: Theoretical questions\n",
    "\n",
    "1. Why is traditional clustering ill-suited for high dimensional data?\n",
    "1. What is the goal of subspace clustering and projected clustering?\n",
    "1. Why is exhaustive subspace cluster search infeasible in practice?\n",
    "1. Give a definition of what a subspace cluster is according to the models proposed by Subclu, Clique and Proclus. How are they similar and where do they differ?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 2: CLIQUE\n",
    "1. What is a subspace cluster in CLIQUE?\n",
    "1. How is monotonicity used in CLIQUE?\n",
    "1. Use the CLIQUE algorithm to compute the hidden subspace clusters in the following 6 dimensional data set.\n",
    "    Compute the first step of the CLIQUE algorithm to detect dense cells. Use 3 equal intervals\n",
    "    per dimension in the domain 0...100 (number of intervals $\\xi = 3$) and consider a cell as dense\n",
    "    if it contains at least 5 objects (density threshold $\\tau = 21\\%$).\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Dim1 Dim2 Dim3 Dim4 Dim5 Dim6\n",
    "X = np.array([\n",
    "    [6, 23, 22, 21, 31, 49],\n",
    "    [7, 22, 21, 20, 51, 76],\n",
    "    [26, 85, 75, 52, 53, 50],\n",
    "    [28, 94, 76, 63, 76, 87],\n",
    "    [29, 45, 93, 51, 54, 51],\n",
    "    [35, 73, 76, 51, 52, 50],\n",
    "    [38, 23, 22, 21, 33, 61],\n",
    "    [41, 22, 21, 21, 32, 99],\n",
    "    [56, 15, 66, 39, 36, 66],\n",
    "    [58, 1, 14, 53, 52, 51],\n",
    "    [66, 1, 40, 19, 86, 13],\n",
    "    [70, 90, 25, 32, 70, 65],\n",
    "    [71, 23, 21, 20, 3, 81],\n",
    "    [80, 19, 42, 23, 57, 1],\n",
    "    [82, 80, 6, 54, 81, 81],\n",
    "    [82, 81, 38, 35, 81, 82],\n",
    "    [82, 81, 77, 57, 81, 82],\n",
    "    [82, 83, 44, 59, 81, 83],\n",
    "    [82, 81, 35, 86, 81, 81],\n",
    "    [84, 80, 66, 10, 81, 81],\n",
    "    [86, 33, 59, 51, 54, 50],\n",
    "    [89, 34, 36, 53, 54, 51],\n",
    "    [92, 25, 27, 40, 14, 22]\n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 3: PROCLUS\n",
    "\n",
    "Consider the following four-dimensional data set:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.array([\n",
    "    ( 15 , 12 , 16 ,  9 ),  # A\n",
    "    ( 14 , 13 , 18 ,  3 ),  # B\n",
    "    ( 12 , 14 , 14 , 15 ),  # C \n",
    "    ( 16 , 13 , 19 , 19 ),  # D \n",
    "    (  5 ,  6 ,  9 ,  4 ),  # E \n",
    "    (  4 , 11 , 10 , 18 ),  # F \n",
    "    (  6 , 17 ,  8 , 13 ),  # G \n",
    "    (  6 ,  9 , 14 , 16 ),  # H \n",
    "    ( 14 , 19 , 13 , 15 ),  # I \n",
    "    ( 19 ,  3 , 15 , 14 ),  # J \n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculate the following steps of a PROCLUS clustering using $k=3$ clusters. \n",
    "Please use the complete data set in the Algorithm (no sample; $A=\\frac{10}{3}$).\n",
    "\n",
    "1. Compute a set of four medoids M.\n",
    "1. Use the first three medoids and compute the locality and $Z_{ij}$ values for each medoid.\n",
    "1. Determine the optimal dimension set $D_i$ for each medoid $m_i$ (use $l=3$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 4: OPTICS \n",
    "Draw the OPTICS plot for the following 2-d data set using Manhattan distance, $minpts=6$, $\\epsilon = 2$. \n",
    "Start with $o = (0,4)$, then, once the ControlList is empty, restart with $p = (2,0)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = np.array([ \n",
    "    (2,0),(2,0),(3,0),(3,0),(3,0),(3,0),(4,0),(4,0),(3,1),(3,1),(3,1),\n",
    "    (4,1),(4,1),(4,1),(0,4),(0,4),(0,5),(0,5),(1,4),(1,4),(1,5),(1,5),\n",
    "    (2,4),(3,4),(3,4),(3,5),(3,5),(3,5),(4,4),(4,4),(4,5),(4,5),(4,5)\n",
    "])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "![](graphics/W4.Q5.png)\n",
    "\n",
    "Note: you do not need to do the\n",
    "actual computation, but you may\n",
    "refer to the figure for reading off\n",
    "the reachability and core distances,\n",
    "respectively.\n",
    "Given the resulting OPTICS plot, which two settings $\\epsilon=1,2$ correspond to a DBSCAN that outputs\n",
    "two and three clusters, respectively?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 5: BIRCH/CF-Tree\n",
    "Insert the following points into an empty CF-Tree and compute the micro clusters and associated cluster features (use the diameter D = 2R).\n",
    "\n",
    "1. $P_1=(5,5)$ \n",
    "1. $P_2=(2,2)$\n",
    "1. $P_3=(4,5)$\n",
    "1. $P_4=(1,4)$\n",
    "1. $P_5=(2,1)$.\n",
    "\n",
    "The tree parameters are: $B=2$, $L=2$, $T=2$\n",
    "\n",
    "\n",
    "<img src=\"graphics/formulas.png\" width=\"1000\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Optional Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 6: SUBCLU\n",
    "1. What is a subspace cluster in SUBCLU?\n",
    "1. How is the monotonicity used in SUBCLU?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 7: Proving Property of BIRCH \n",
    "In BIRCH [1], they claim that the the _average intra-cluster distance_ $D3$ can be computed efficiently and exactly from the clustering feature (CF) of two clusters. \n",
    "We aim to prove that claim here.\n",
    "\n",
    "The average intra-cluster distance is defined as follows. \n",
    "Given $N_1$ d-dimensional data points in cluster: $C_1 = \\{ X_i \\}$ where $i = 1, \\dots, N_1$, and $N_2$ datapoints in another cluster: $C_2 = \\{ X_j \\}$ where $j = N_1 + 1, \\dots, N_1 + N_2$, \n",
    "\n",
    "$$\n",
    "D3(C1, C2) =\\left(\\frac{\\sum_{i=1}^{N_{1}+N_{2}} \\sum_{j=1}^{N_{1}+N_{2}}\\left(X_{i}-X_{j}\\right)^{2}}{\\left(N_{1}+N_{2}\\right)\\left(N_{1}+N_{2}-1\\right)}\\right)^{\\frac{1}{2}} \\qquad\\quad\\quad (1)\n",
    "$$\n",
    "\n",
    "and the CF for cluster $i$ is defined as a triple $CF_i = (N_i, LS_i, SS_i)$, where $LS_i = \\sum_{j=1}^{N_i} X_j$ and $SS_i = \\sum_{j=1}^{N_i} X_j^2$.\n",
    "\n",
    "1. Given two CFs, $CF_1$ and $CF_2$, for clusters $C_1$ and $C_2$, respectively, show that $D3(C_1, C_2)$ can becomputed only from information in $CF_1$ and $CF_2$.\n",
    "2. Compare the running times of Equation (1) and you derived algorithm. Which one is faster?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you want, you could test your derived formula here. Look for the _TODO_ below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# D3 the slow way\n",
    "import time\n",
    "from tqdm import tqdm\n",
    "fast = True\n",
    "# Cluster statistics\n",
    "def D3_slow(C1, C2): # Slow algorithm\n",
    "    C = np.concatenate([C1, C2], axis=0)\n",
    "    s = 0.\n",
    "    \n",
    "    N1, d = C1.shape\n",
    "    N2, _ = C2.shape\n",
    "    N,  _ = C.shape\n",
    "    \n",
    "    if fast: # Fast version of the slow algorithm\n",
    "        C_ = C.reshape(N, 1, d)\n",
    "        C  = C.reshape(1, N, d)\n",
    "        D  = (C_ - C).reshape(N*N, 1, d)\n",
    "        s  = (D @ D.reshape(N*N, d, 1)).sum()\n",
    "    else: # Slow version of the slow algorithm\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                s += np.dot((C[i] - C[j]), (C[i] - C[j]))\n",
    "\n",
    "    s = s / ((N1 + N2)*(N1 + N2 -1))\n",
    "    return np.sqrt(s)\n",
    "\n",
    "# Statistics for fast implementation\n",
    "LS = lambda C: np.sum(C, axis=0)\n",
    "SS = lambda C: np.sum(C ** 2)\n",
    "\n",
    "# TODO implement your fast algorithm here.\n",
    "def D3_fast(C1, C2):\n",
    "    N1, _ = C1.shape\n",
    "    N2, _ = C2.shape\n",
    "    LS1, SS1 = LS(C1), SS(C1)\n",
    "    LS2, SS2 = LS(C2), SS(C2)\n",
    "\n",
    "    return 0 # TODO return DS3\n",
    "\n",
    "## FROM HERE ON IS JUST TESTING AND PLOTTING. YOU DO NOT NEED TO CODE ANYTHING ## \n",
    "\n",
    "# Generate random samples in two different clusters.\n",
    "# Check that the two algorithms give the same result.\n",
    "size = 4\n",
    "C1 = np.random.randn(size, 2) * 0.5 \n",
    "C2 = np.random.randn(size, 2) * 0.5 + 2\n",
    "assert np.allclose(D3_slow(C1, C2), D3_fast(C1, C2))\n",
    "\n",
    "## TEST running time for the two algorithms\n",
    "repeats     = 20   # Average running time over `repeats` time.\n",
    "size_from   = 10   # Data set size from\n",
    "size_to     = 1010  # Dataset size to\n",
    "size_step   = 100   # Step size\n",
    "data_sizes  = range(size_from, size_to + 1, size_step) # Test sizes\n",
    "\n",
    "def test(fn):\n",
    "    times = []\n",
    "    results = []\n",
    "    \n",
    "    for size in data_sizes:\n",
    "        C1 = np.random.randn(size, 2) * 0.5 \n",
    "        C2 = np.random.randn(size, 2) * 0.5 + 2\n",
    "        \n",
    "        t0 = time.time()\n",
    "        for _ in range(repeats): \n",
    "              print(f'\\rSize {size}: {1+_}/{repeats}', end=\"\")\n",
    "              t = fn(C1, C2)\n",
    "        td = time.time() - t0\n",
    "        print(f\"\\rSize {size}: \\t{td / repeats:.6f} secs.\")\n",
    "        results.append(t)\n",
    "        times.append(td / repeats)\n",
    "    return times, results\n",
    "\n",
    "print(\"Testing slow algorithm\")\n",
    "slows = test(D3_slow)\n",
    "print(\"Testing fast algorithm\")\n",
    "fasts = test(D3_fast)\n",
    "\n",
    "print(\"\\n|  i  | %-9s | %-9s |\" % ('Fast', 'Slow'))\n",
    "print(\"-\"*31)\n",
    "for i, st, ft in zip(data_sizes, slows, fasts):\n",
    "    print(\"| %3i | %9.5f | %9.5f |\" % (i, ft, st))\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "fig, ax = plt.subplots(1,1)\n",
    "ax.plot(data_sizes, fasts, 'r-o', label=\"Fast\")\n",
    "ax.plot(data_sizes, slows, 'b--o', label=\"Slow\")\n",
    "ax.set_ylabel('Seconds')\n",
    "ax.set_xlabel('# Data rows')\n",
    "ax.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### References:\n",
    "[1] Zhang, T., Ramakrishnan, R. and Livny, M., 1996. BIRCH: an efficient data clustering method for very large databases. ACM Sigmod Record, 25(2), pp.103-114."
   ]
  }
 ],
 "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.9.13"
  },
  "vscode": {
   "interpreter": {
    "hash": "b0fa6594d8f4cbf19f97940f81e996739fb7646882a419484c72d19e05852a7e"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}