Canlapan_Inah_HW1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1. Concept Questions\n",
    "Code below is for 1.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "A = np.array([[0,1,1,0,0], [1,0,1,0,0], [1,1,0,0,0], [0,0,0,0,1], [0,0,0,1,0]])\n",
    "D = np.array([[2,0,0,0,0], [0,2,0,0,0], [0,0,2,0,0], [0,0,0,1,0], [0,0,0,0,1]])\n",
    "L = D-A\n",
    "\n",
    "# Eigenvalue decomposition\n",
    "s, v = np.linalg.eig(L)\n",
    "\n",
    "# Get index of eigenvalues that are 0\n",
    "zero_evalue_index =  [i for i, x in enumerate(np.around(s,1)) if x == 0]\n",
    "print(\"Eigenvalues: \" + str(np.around(s,1)))\n",
    "print(\"Indexes of 0 eigenvalues: \" + str(zero_evalue_index))\n",
    "\n",
    "# Columns corresponding to the eigenvalues that are 0\n",
    "print(\"Eigenvectors: \")\n",
    "print(str(v))\n",
    "print(\"Cluster Assignment:\")\n",
    "print(str(v[:, zero_evalue_index]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Based on the resulting matrix, I can conclude that nodes 1, 2 and 3 are connected in one cluster while nodes 4 and 5 are connected in another. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Image Compression Using Clustering"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import imageio  \n",
    "import matplotlib.image\n",
    "import random \n",
    "import numpy as np\n",
    "import time\n",
    "from datetime import timedelta\n",
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "###### Define Functions ######\n",
    "def assign_cluster(pxl, c, norm=2):\n",
    "    \"\"\"\n",
    "    Calculates distance between single pixel and list of centroids.\n",
    "\n",
    "    Input:\n",
    "        pxl = pixel [R,G,B]\n",
    "        c = list of centroids\n",
    "        norm = L1 or L2, default is L2\n",
    "    Output:\n",
    "        Cluster Index\n",
    "    \n",
    "    Author's Note: \n",
    "    This function is what takes the longest when I run the code. \n",
    "    I couldn't figure out how to optimize, but it still works! \n",
    "    \n",
    "    \"\"\"    \n",
    "    min_distance = 0\n",
    "    cluster_index = 0\n",
    "    \n",
    "    # Loop through list of centroids\n",
    "    for i in range(len(c)):\n",
    "        x = pxl-c[i]\n",
    "\n",
    "        if norm==1:\n",
    "            distance = np.linalg.norm(x, 1)\n",
    "        else:\n",
    "            distance = np.linalg.norm(x, 2)\n",
    "            \n",
    "        if i == 0:\n",
    "            min_distance = distance\n",
    "            cluster_index = i\n",
    "        else:\n",
    "            if distance < min_distance:\n",
    "                cluster_index = i\n",
    "                min_distance = distance            \n",
    "    \n",
    "    return cluster_index\n",
    "\n",
    "def adjust_centroids(pixel, cluster_assign, centroids, norm=2):\n",
    "    \"\"\"\n",
    "    Adjusts the centroids based on mean (L2 norm) or median (L1 norm)\n",
    "    \n",
    "    Input\n",
    "        pixel = RGB representation of image\n",
    "        cluster_assign = cluster assignment\n",
    "        centroids = current list of centroids\n",
    "    Output\n",
    "        adjusted centroid list \n",
    "    \"\"\"\n",
    "        \n",
    "    m = pixel.shape[0]\n",
    "    n = pixel.shape[1]\n",
    "    d = pixel.shape[2]\n",
    "    \n",
    "    new_centroids = defaultdict()\n",
    "    centroid_list = []\n",
    "    final_centroids = []\n",
    "    \n",
    "    # Loop through pixels in image. Add pixel to corresponding cluster list\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            pxl = pixel[i,j]\n",
    "            cluster = cluster_assign[i,j] \n",
    "            \n",
    "            if cluster not in new_centroids:\n",
    "                new_centroids[cluster] = list()\n",
    "                \n",
    "            new_centroids[cluster].append(pxl)  \n",
    "            \n",
    "    # Calculate the new list of centroids\n",
    "    for cluster in new_centroids:\n",
    "        centroid_list = np.array(new_centroids[cluster])\n",
    "        \n",
    "        if norm==1:\n",
    "            updated_centroid = np.median(centroid_list, axis=0).astype(np.uint8)\n",
    "        else:\n",
    "            updated_centroid = np.around(centroid_list.sum(axis=0)/len(centroid_list)).astype(np.uint8)\n",
    "        \n",
    "        final_centroids.append(updated_centroid.tolist())\n",
    "    \n",
    "    return final_centroids \n",
    "\n",
    "def run_kmeans(pixel, k, norm=2):\n",
    "    \"\"\"\n",
    "    Runs the kmeans algorithm.\n",
    "    \n",
    "    Input:\n",
    "        pixel = RGB representation of image\n",
    "        k = number of desired clusters\n",
    "        norm = distance measure, can be 1 or 2\n",
    "    \n",
    "    Output:\n",
    "        cluster labels\n",
    "        new centroids \n",
    "        compressed image \n",
    "        number of iterations \n",
    "        run time\n",
    "    \"\"\"    \n",
    "    start_time = time.monotonic()\n",
    "    \n",
    "    m = pixel.shape[0] \n",
    "    n = pixel.shape[1] \n",
    "    d = pixel.shape[2] \n",
    "    cluster_assign = np.empty(shape=(m,n),dtype='object')\n",
    "    \n",
    "    np.random.seed(206)\n",
    "    \n",
    "    # Initialize random centroids\n",
    "    c_r = np.random.randint(0, 255, size = k)\n",
    "    c_g = np.random.randint(0, 255, size = k)\n",
    "    c_b = np.random.randint(0, 255, size = k)\n",
    "    centroids = np.array(list(zip(c_r, c_g, c_b))).tolist()\n",
    "    centroids.sort()\n",
    "    \n",
    "    # Initialize the clusters\n",
    "    cluster_assign = np.empty(shape=(m,n),dtype='object')\n",
    "\n",
    "    iter_count = 1\n",
    "\n",
    "    # Assign the cluster to each pixel for the first time\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            pxl = pixel[i][j]\n",
    "            cluster_assign[i,j] = assign_cluster(pxl, centroids, norm)\n",
    "        \n",
    "    # Get new centroids\n",
    "    new_centroids = adjust_centroids(pixel, cluster_assign, centroids, norm) \n",
    "    new_centroids.sort()\n",
    "    \n",
    "    while centroids != new_centroids: # Keep looping until the new centroids are equal to the old centroids\n",
    "        iter_count += 1\n",
    "        \n",
    "        centroids = new_centroids\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pxl = pixel[i][j]\n",
    "                cluster_assign[i,j] = assign_cluster(pxl, centroids, norm)\n",
    "                        \n",
    "        # Get new centroids\n",
    "        new_centroids = adjust_centroids(pixel, cluster_assign, centroids, norm) \n",
    "        new_centroids.sort()\n",
    "        \n",
    "    # Time Calculation\n",
    "    end_time = time.monotonic()\n",
    "    time_diff = timedelta(seconds=end_time - start_time).seconds\n",
    "    \n",
    "    # Create compressed image\n",
    "    final_image = np.empty(shape=(m,n,d),dtype='object')\n",
    "    for row in range(m):\n",
    "        for col in range(n):\n",
    "            pxl = cluster_assign[row][col] \n",
    "            final_image[row,col] = np.array(new_centroids[pxl])   \n",
    "    \n",
    "    # Final Outputs\n",
    "    cluster_labels = cluster_assign+1\n",
    "    final_image = np.reshape(final_image, (pixel.shape))\n",
    "    \n",
    "    return cluster_labels, new_centroids, final_image, iter_count, time_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Loop through pictures and k values using norm = 2\n",
    "\n",
    "k_vals = [2,4,8,16]\n",
    "\n",
    "image = ['data/GeorgiaTech.bmp', 'data/football.bmp', 'data/beach.jpg']\n",
    "\n",
    "for k in k_vals:\n",
    "    for pic in image:  \n",
    "        \n",
    "        # Read image\n",
    "        original_image =  imageio.imread(pic)\n",
    "        \n",
    "        # Run kmeans\n",
    "        cluster_label, cluster_center, comp_image, iterations, run_time = run_kmeans(original_image, k, norm=2)\n",
    "        \n",
    "        # Export file\n",
    "        pic_name = pic.split('/')[1].split('.')[0]\n",
    "        matplotlib.image.imsave('Q2_output/'+pic_name+'_'+str(k)+'.png', comp_image.astype(np.uint8))\n",
    "        \n",
    "        print(pic_name + ', k = ' + str(k) + ', Iterations = ' + str(iterations) + ', Run Time = ' + str(run_time) + ' secs.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Loop through pictures and k values using norm = 1\n",
    "k_vals = [2,4,8,16]\n",
    "\n",
    "image = ['data/GeorgiaTech.bmp', 'data/football.bmp', 'data/beach.jpg']\n",
    "\n",
    "for k in k_vals:\n",
    "    for pic in image:  \n",
    "        \n",
    "        # Read image\n",
    "        original_image =  imageio.imread(pic)\n",
    "        \n",
    "        # Run kmeans\n",
    "        cluster_label, cluster_center, comp_image, iterations, run_time = run_kmeans(original_image, k, norm=1)\n",
    "        \n",
    "        # Export file\n",
    "        pic_name = pic.split('/')[1].split('.')[0]\n",
    "        matplotlib.image.imsave('Q2_output/Part_2/'+pic_name+'_'+str(k)+'.png', comp_image.astype(np.uint8))\n",
    "        \n",
    "        print(pic_name + ', k = ' + str(k) + ', Iterations = ' + str(iterations) + ', Run Time = ' + str(run_time) + ' secs.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Loop through pictures and k values using norm = 1\n",
    "\n",
    "k_vals = [16]\n",
    "\n",
    "image = ['data/beach.jpg', 'data/football.bmp' ]\n",
    "\n",
    "for k in k_vals:\n",
    "    for pic in image:  \n",
    "        \n",
    "        # Read image\n",
    "        original_image =  imageio.imread(pic)\n",
    "        \n",
    "        # Run kmeans\n",
    "        cluster_label, cluster_center, comp_image, iterations, run_time = run_kmeans(original_image, k, norm=1)\n",
    "        \n",
    "        # Export file\n",
    "        pic_name = pic.split('/')[1].split('.')[0]\n",
    "        matplotlib.image.imsave('Q2_output/Part_2/'+pic_name+'_'+str(k)+'.png', comp_image.astype(np.uint8))\n",
    "        \n",
    "        print(pic_name + ', k = ' + str(k) + ', Iterations = ' + str(iterations) + ', Run Time = ' + str(run_time) + ' secs.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Political Blogs Dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import csv\n",
    "from sklearn.cluster import KMeans\n",
    "from collections import defaultdict\n",
    "from statistics import mode\n",
    "\n",
    "##### Define Functions #####\n",
    "def run_spec(L, k):\n",
    "    \"\"\"\n",
    "    Performs eigenvalue/eigenvector decomposition and performs kmeans based on value of k.\n",
    "    \n",
    "    Input:\n",
    "        L = Laplacian \n",
    "        k = number of clusters\n",
    "    Output:\n",
    "        kmeans object\n",
    "        cluster labels   \n",
    "        \n",
    "    Author's Note:\n",
    "    Code was borrowed from test_football.py\n",
    "    \n",
    "    \"\"\"\n",
    "    # Eigenvector Decomposition\n",
    "    v, x = np.linalg.eig(L)\n",
    "    idx = np.argsort(v)\n",
    "    x = np.real(x[:, idx[-k:]]) # select the k largest eigenvectors\n",
    "    x = x/np.repeat(np.sqrt(np.sum(x*x, axis=1).reshape(-1, 1)), k, axis=1) # ensure all vectors are of unit length\n",
    "    \n",
    "    # Run kmeans\n",
    "    kmeans = KMeans(n_clusters=k).fit(x)\n",
    "    c_idx = kmeans.labels_\n",
    "\n",
    "    return kmeans, c_idx\n",
    "\n",
    "def calc_metrics(nodes, labels):\n",
    "    \"\"\"\n",
    "    Calculates majority labels and mismatch rates for clusters.\n",
    "    \n",
    "    Input:\n",
    "        Nodes = node list\n",
    "        Labels = cluster labels (output from run_spec)\n",
    "    Output:\n",
    "        majority = dictionary, {cluster: majority political orientation}\n",
    "        mismatch = dictionary, {cluster: mismatch rate}\n",
    "    \"\"\"\n",
    "    \n",
    "    num_nodes = nodes.shape[0]\n",
    "    cluster_groups = defaultdict()\n",
    "    majority = {}\n",
    "    mismatch = {}\n",
    "    \n",
    "    # Collect political orientation of blogs associated with each cluster\n",
    "    for i in range(num_nodes):\n",
    "        node = nodes[i]\n",
    "        group = node[2].astype(int)\n",
    "        cluster = labels[i]\n",
    "        \n",
    "        if cluster not in cluster_groups:\n",
    "            cluster_groups[cluster] = list()\n",
    "        \n",
    "        cluster_groups[cluster].append(group)\n",
    "            \n",
    "    # Majority Label\n",
    "    for key in cluster_groups.keys():\n",
    "        majority[key]=mode(cluster_groups[key])\n",
    "    \n",
    "    # Calculate Match Rate\n",
    "    for key in cluster_groups.keys():\n",
    "        value = cluster_groups[key]\n",
    "        most_common = majority[key]\n",
    "        \n",
    "        total = len(value)\n",
    "        count = 0\n",
    "        \n",
    "        # Calculate Mismatch Rate\n",
    "        for i in range(total):\n",
    "            if value[i] == most_common:\n",
    "                count += 1\n",
    "                        \n",
    "        # Return mismatch rate to dictionary\n",
    "        mismatch[key] = float(format(1 - count/total, '.4f'))\n",
    "        \n",
    "    return majority, mismatch "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load txt files\n",
    "# Source: https://stackoverflow.com/questions/16989647/importing-large-tab-delimited-txt-file-into-python/16999000\n",
    "\n",
    "with open('data/nodes.txt') as f:\n",
    "    reader = csv.reader(f, delimiter=\"\\t\")\n",
    "    nodes0 = list(reader)  # Schema = [\"Node\", \"Site\", \"Orientation\", \"Tags\"]\n",
    "\n",
    "with open('data/edges.txt') as f:\n",
    "    reader = csv.reader(f, delimiter=\"\\t\")\n",
    "    edges0 = list(reader) # Schema = Start, End\n",
    "\n",
    "# Change data types\n",
    "edges = np.array(edges0).astype(int)\n",
    "\n",
    "nodes = nodes0\n",
    "for i in range(len(nodes0)):   \n",
    "    nodes[i][0] = int(nodes0[i][0])\n",
    "    nodes[i][2] = int(nodes0[i][2])\n",
    "\n",
    "# Create Adjacency Matrix \n",
    "n = len(nodes)\n",
    "A = np.zeros(shape=(n,n),dtype='object')\n",
    "\n",
    "for edge in edges:\n",
    "    i = (edge-1)[0]\n",
    "    j = (edge-1)[1]\n",
    "    A[i,j] = 1\n",
    "    A[j,i] = 1\n",
    "\n",
    "# Create Degree matrix\n",
    "d_i = A.sum(axis=0)\n",
    "D = np.diagflat(d_i)\n",
    "\n",
    "# Get index of nodes that don't have any connections\n",
    "del_list = []\n",
    "\n",
    "for i in range(len(d_i)):\n",
    "    if d_i[i] == 0:\n",
    "        del_list.append(i)\n",
    "        \n",
    "# Remove corresponding rows and columns from D, A and nodes\n",
    "A = np.delete(A, del_list, 0)\n",
    "A = np.delete(A, del_list, 1)\n",
    "D = np.delete(D, del_list, 0)\n",
    "D = np.delete(D, del_list, 1)\n",
    "nodes = np.delete(nodes, del_list, 0)\n",
    "\n",
    "# Calculate Laplacian: L = D-A\n",
    "L = (D-A).astype(float)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Loop through different values of k\n",
    "k_vals = [2,5,10,20]\n",
    "\n",
    "for k in k_vals:\n",
    "    kmeans_obj, labels = run_spec(L, k)\n",
    "    majority, mismatch = calc_metrics(nodes, labels)\n",
    "    \n",
    "    avg = mean(mismatch.values())\n",
    "    min_rate = min(mismatch.values())\n",
    "    max_rate = max(mismatch.values())\n",
    "    \n",
    "    print(\"k = \" + str(k))\n",
    "    print(\"Majority: \" + str(dict(sorted(majority.items()))))\n",
    "    print(\"Mismatch Rates: \" + str(dict(sorted(mismatch.items()))))\n",
    "    print(\"Average of Mismatch Rates = \" + str(avg))\n",
    "    print(\"Spread of Mismatch Rates = (\" + str(min_rate) + \", \" + str(max_rate) + \") = \" + str(max_rate-min_rate))\n",
    "    print(\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for k in range(2,10):\n",
    "    kmeans_obj, labels = run_spec(L, k)\n",
    "    majority, mismatch = calc_metrics(nodes, labels)\n",
    "    \n",
    "    avg = mean(mismatch.values())\n",
    "    min_rate = min(mismatch.values())\n",
    "    max_rate = max(mismatch.values())\n",
    "    \n",
    "    print(\"k = \" + str(k))\n",
    "    print(\"Majority: \" + str(dict(sorted(majority.items()))))\n",
    "    print(\"Mismatch Rates: \" + str(dict(sorted(mismatch.items()))))\n",
    "    print(\"Average of Mismatch Rates = \" + str(avg))\n",
    "    print(\"Spread of Mismatch Rates = (\" + str(min_rate) + \", \" + str(max_rate) + \") = \" + str(max_rate-min_rate))\n",
    "    print(\"\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}