LMVSC_Handwritten-QP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Large-scale Multi-view Subspace Clustering in Linear Time (Handwritten Digits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**References:**\n",
    "1. Main Paper: https://arxiv.org/pdf/1911.09290.pdf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import math\n",
    "from scipy import linalg\n",
    "from sklearn.cluster import KMeans\n",
    "import pandas as pd\n",
    "from cvxpy.atoms.elementwise.power import power\n",
    "import cvxpy as cp\n",
    "from qpsolvers import solve_qp\n",
    "from sklearn.utils.extmath import randomized_svd\n",
    "from sklearn.decomposition import TruncatedSVD\n",
    "from scipy.optimize import linear_sum_assignment\n",
    "from sklearn.preprocessing import MinMaxScaler\n",
    "from sklearn.preprocessing import normalize\n",
    "from sklearn.preprocessing import StandardScaler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "d1 = np.load('dig_fac.npy')\n",
    "d2 = np.load('dig_fou.npy')\n",
    "d3 = np.load('dig_kar.npy')\n",
    "d4 = np.load('dig_mor.npy')\n",
    "d5 = np.load('dig_pix.npy')\n",
    "d6 = np.load('dig_zer.npy')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# d1 = (d1 - d1.min(axis=0))/(d1.max(axis=0) - d1.min(axis=0))\n",
    "# d2 = (d2 - d2.min(axis=0))/(d2.max(axis=0) - d2.min(axis=0))\n",
    "# d3 = (d3 - d3.min(axis=0))/(d3.max(axis=0) - d3.min(axis=0))\n",
    "# d4 = (d4 - d4.min(axis=0))/(d4.max(axis=0) - d4.min(axis=0))\n",
    "# d5 = (d5 - d5.min(axis=0))/(d5.max(axis=0) - d5.min(axis=0))\n",
    "# d6 = (d6 - d6.min(axis=0))/(d6.max(axis=0) - d6.min(axis=0))\n",
    "d1 = (d1 - d1.min())/(d1.max() - d1.min())\n",
    "d2 = (d2 - d2.min())/(d2.max() - d2.min())\n",
    "d3 = (d3 - d3.min())/(d3.max() - d3.min())\n",
    "d4 = (d4 - d4.min())/(d4.max() - d4.min())\n",
    "d5 = (d5 - d5.min())/(d5.max() - d5.min())\n",
    "d6 = (d6 - d6.min())/(d6.max() - d6.min())\n",
    "# d1 = (d1 - d1.mean())/d1.std()\n",
    "# d2 = (d2 - d2.mean())/d2.std()\n",
    "# d3 = (d3 - d3.mean())/d3.std()\n",
    "# d4 = (d4 - d4.mean())/d4.std()\n",
    "# d5 = (d5 - d5.mean())/d5.std()\n",
    "# d6 = (d6 - d6.mean())/d6.std()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Loading the data from the 6 views of Caltech_7 dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = []\n",
    "X.append(d1)\n",
    "X.append(d2)\n",
    "X.append(d3)\n",
    "X.append(d4)\n",
    "X.append(d5)\n",
    "X.append(d6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As in the above case, there are $6$ views."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "V = len(X) # V is the number of views\n",
    "k = 10 # k is the number of clusters\n",
    "alpha = 1 # alpha is the regularisation term in the convex optimisation problem\n",
    "m = 100 # here m is the number of anchors for each view\n",
    "n = X[0].shape[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Setting up the anchor graph representation for all the views"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "A=[]\n",
    "for v in range(V):\n",
    "    k_means = KMeans(random_state=25, n_clusters=m)\n",
    "    k_means.fit(X[v].T)\n",
    "    A.append(k_means.cluster_centers_.T)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The dimension for each of the $A_i$'s is $\\mathbb{R}^{d_i x m}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "View 0\n",
      "View 1\n",
      "View 2\n",
      "View 3\n",
      "View 4\n",
      "View 5\n"
     ]
    }
   ],
   "source": [
    "for v in range(V):\n",
    "    print(f'View {v}')\n",
    "    AA = 2 * alpha * np.eye(m) + 2 * A[v].T @ A[v]\n",
    "    AA = (AA + AA.T) / 2\n",
    "    B = X[v]\n",
    "    \n",
    "    d = B.shape[0]\n",
    "    ff = -2 * (B[:,0].reshape(d,1)).T @ A[v]\n",
    "    q = (ff.T).reshape((m,))\n",
    "    G = -1 * np.eye(m)\n",
    "    h = np.zeros((m, 1)).reshape((m,))\n",
    "    #h = np.array([0., 0., 0., 0., 0., 0., 0., 0., 0., 0.]).reshape((m,))\n",
    "    #l = 1e-3\n",
    "    #h = np.array([l, l, l, l, l, l, l]).reshape((m,))\n",
    "    #AI = np.array([1., 1., 1., 1., 1., 1., 1., 1., 1., 1.])\n",
    "    AI = np.ones((m, 1)).reshape((m,))\n",
    "    b = np.array([1.])\n",
    "    Z = solve_qp(AA, q, G, h, AI, b).reshape(m,1)\n",
    "    \n",
    "    for j in range(1, n):\n",
    "        ff = -2 * (B[:,j].reshape(d,1)).T @ A[v]\n",
    "        q = (ff.T).reshape((m,))\n",
    "        \n",
    "        z = solve_qp(AA, q, G, h, AI, b).reshape(m,1)\n",
    "        Z = np.concatenate((Z,z),axis=1)\n",
    "        \n",
    "    D = np.diag(np.divide(1, np.sqrt(np.sum(Z, axis=1))))\n",
    "    Zc = (Z.T @ D).T\n",
    "    \n",
    "    if v == 0:\n",
    "        Sbar = Zc / np.sqrt(V)\n",
    "    else:\n",
    "        Sbar = np.concatenate((Sbar, (1/np.sqrt(V))*Zc), axis=0)\n",
    "        \n",
    "#     if v == 0:\n",
    "#         Sbar = Z / np.sqrt(V)\n",
    "#     else:\n",
    "#         Sbar = np.concatenate((Sbar, (1/np.sqrt(V))*Z), axis=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "U, _, _ = randomized_svd(Sbar.T, n_components = k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2000, 10)"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "U.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "KMeans(n_clusters=10, random_state=25)"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "k_means2 = KMeans(random_state=25, n_clusters=k)\n",
    "k_means2.fit(U)\n",
    "#k_means2.labels_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "np.set_printoptions(threshold=sys.maxsize)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "#k_means2.labels_ + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2000"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Create true labels\n",
    "orig = []\n",
    "for i in range(10):\n",
    "    for j in range(200):\n",
    "        orig.append(i)\n",
    "len(orig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "orig = np.array(orig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "pred = k_means2.labels_\n",
    "#orig = np.load('cal7_labels.npy')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate Performance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Hungarian(A):\n",
    "    _, col_ind = linear_sum_assignment(A)\n",
    "    return col_ind"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BestMap(L1, L2):\n",
    "    L1 = L1.flatten(order='F').astype(float)\n",
    "    L2 = L2.flatten(order='F').astype(float)\n",
    "    if L1.size != L2.size:\n",
    "        sys.exit('size(L1) must == size(L2)')\n",
    "    Label1 = np.unique(L1)\n",
    "    nClass1 = Label1.size\n",
    "    Label2 = np.unique(L2)\n",
    "    nClass2 = Label2.size\n",
    "    nClass = max(nClass1, nClass2)\n",
    "\n",
    "    # For Hungarian - Label2 are Workers, Label1 are Tasks.\n",
    "    G = np.zeros([nClass, nClass]).astype(float)\n",
    "    for i in range(0, nClass2):\n",
    "        for j in range(0, nClass1):\n",
    "            G[i, j] = np.sum(np.logical_and(L2 == Label2[i], L1 == Label1[j]))\n",
    "\n",
    "    c = Hungarian(-G)\n",
    "    newL2 = np.zeros(L2.shape)\n",
    "    for i in range(0, nClass2):\n",
    "        newL2[L2 == Label2[i]] = Label1[c[i]]\n",
    "    return newL2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ARI = 0.8450742702718328\n",
      "NMI = 0.8658205055732388\n"
     ]
    }
   ],
   "source": [
    "from sklearn.metrics import adjusted_rand_score\n",
    "from sklearn.metrics import normalized_mutual_info_score\n",
    "print(\"ARI = \" + str(adjusted_rand_score(orig, pred)))\n",
    "print(\"NMI = \" + str(normalized_mutual_info_score(orig, pred)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy = 0.9255\n"
     ]
    }
   ],
   "source": [
    "pred_ord = BestMap(orig, pred)\n",
    "Missrate = float(np.sum(orig != pred_ord)) / orig.size\n",
    "print(f'Accuracy = {1 - Missrate}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[194,   0,   0,   0,   1,   0,   0,   0,   5,   0],\n",
       "       [  0, 180,   0,   0,   7,   0,   0,   8,   2,   3],\n",
       "       [  0,   0, 192,   1,   0,   0,   0,   4,   0,   3],\n",
       "       [  0,   1,   0, 176,   3,  11,   0,   9,   0,   0],\n",
       "       [  0,   3,   0,   0, 194,   1,   1,   0,   0,   1],\n",
       "       [  0,   0,   0,   6,   2, 187,   0,   3,   1,   1],\n",
       "       [  0,   1,   0,   1,   3,   0, 180,   0,  15,   0],\n",
       "       [  0,   0,   0,   0,   0,   0,   0, 162,   0,  38],\n",
       "       [  1,   0,   0,   0,   3,   0,   0,   0, 196,   0],\n",
       "       [  0,   2,   0,   0,   0,   1,   0,   2,   5, 190]], dtype=int64)"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from sklearn.metrics import confusion_matrix\n",
    "conf_mat = confusion_matrix(orig, pred_ord)\n",
    "conf_mat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Purity = 0.9255\n"
     ]
    }
   ],
   "source": [
    "purity = np.sum(np.max(conf_mat, axis=1))/n\n",
    "print(\"Purity = \" + str(purity))"
   ]
  },
  {
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}